Фрактальные дискретные косинусные преобразования на предфрактальных областях, ассоциированных с фундаментальными областями канонических систем счисления

Одним из важнейших дискретных ортогональных преобразований (ДОП), применяемых в цифровой обработке изображений, является дискретное косинусное преобразование и его различные версии. Это связано , в частности, с тем, что базисные функции дискретного косинусного преобразования (ДКП) для многих классов сигналов близки к базисным функциями преобразования Карунена–Лоэва. Тем не менее, несмотря на известные преимущества ДКП, при блочном кодировании изображения всё же возникают артефакты на границах квадратных блоков , достаточно визуально различимые именно из-за их структурированности. Возможной альтернативой классического ДКП, свободной от указанного недостатка, являлось бы ДОП, подобное ДКП, но определённое на блоках неправильной формы, которые образуют покрытие области определения изображения. Возможным преобразованием, удовлетворяющим сформулированным свойствам, является одномерное ДКП, базисные функции которого определены на некоторой траектории-развёртке двумерной области. Такие преобразования рассматривались в [1]. В настоящей работе вводится и исследуется новое ДОП – «фрактальное ДКП», связанное с фурьепо-добными преобразованиями, определёнными на фрактальных областях специфического вида (фундаментальные области КСС в мнимых квадратичных полях), таким же образом, как и обычное ДКП связано с дискретным преобразованием Фурье (ДПФ).

1. Канонические системы счисления

Приведём краткие сведения о канонических системах счисления (КСС) в мнимых квадратичных поля [2]–[4].

Определение 1. Пусть Q ( Jd ) есть квадратичное поле: Q ( d ) = { z = a + b4d ; a , b e Q } , d — целое число, свободное от квадратов.

Если для элемента z = a + b4d e Q ( 4d ) норма и след есть целые числа,

Norm ( z ) = ( a + b4d )( a - b4d ) ,                (1)

Tr (z ) = ( a + b4d) + (a - bld),                 (2)

то элемент называется целым алгебраическим элементом поля Q (V d ) . Целые элементы образуют ре-

шётку на комплексной плоскости.

Определение 2. Целое алгебраическое число а = A + dd называется основанием канонической си-

стемы счисления в кольце целых элементов поля Q (V d ) , если любой целый элемент этого поля однозначно представим в форме конечной суммы k ( z )

z = £ z j-O^5,

j =0

zj e N = { 0,1,---,| Norm ( o)|- 1 } .

Пара { а , N } называется канонической системой счисления (КСС) в кольце целых элементов поля Q ( 4d ) .

В работе рассматривается только случай d <  0, то есть мнимые квадратичные поля. Приведём несколько примеров канонических систем счисления с различными нормами.

Пример 1. Пусть Norm ( а ) = 2, тогда в силу (3) N = { 0,1 } . В работе [2] показано, что существует

ровно три мнимых квадратичных поля для

d = - 1, - 2, - 3, в кольцах целых элементов которых

существуют бинарные КСС, а именно:

кольцо целых Гауссовых чисел Z ( i ) e Q ( i ) с ос

нованиями, равными а = - 1 ± i ;

кольцо S (i V? )e Q (i V?)

- 1 ± i V? ми а =-------;

кольцо S ( i V2) e Q ( i^ ) ми а = ± i 41 .

с основаниями, равны-

с основаниями, равны-

Пример 2. При Norm ( а ) = 7 существуют сле-

дующие мнимые квадратичные поля, в кольцах целых элементов которых существуют семеричные канонические системы счисления, а именно:

1) поле Q ( i V6 ) с основанием a = - 1 ± i V6 ;

поле

Q (i V3)

с основанием a =

- 5 ± i ^

поле Q ( i V19 )

- 3 ± iV19

с основанием a =

Если в формуле (3) k фиксировано, то множество элементов, представимых k -членной суммой, представляет собой ограниченное множество на комплексной плоскости, которое будем называть k -фундаментальной областью, примеры таких областей изображены на рис. 1 a – в .

- 3 ± i У19

Оттенки серого цвета на приведённых рисунках подчёркивают самоподобный «характер» k -фундаментальных областей при растущем k .

В работе [3] приводится классификационная теорема для КСС в мнимых квадратичных полях, устанавливающая явную связь между параметрами a , d , N .

Теорема 1.

(а) Пусть d < - 2 , d ^ 1(mod4). Пара { a , N } является канонической системой счисления в кольце Q ( iVd ) тогда и только тогда, когда a = A ± Vd , 0 <- 2 A <  A ² - d >  2; A e Z .

(б) Пусть d <- 2. Пара { a , N } является канонической системой счисления в кольце Q ( iVd ) тогда и

только тогда, когда a =

-1 <- B < 4 (B2 - d)

Рис. 1а. к = 6, a =

Рис. 1б. k = 10, a = - 1 + iV2

Рис. 1в. k = 16, a = - 1 + i

2 (B ± Vd),

> 2; B e Z и нечётное.

2. Фрактальное дискретное ортогональное преобразование

Следуя работе [5], дискретное преобразование

Фурье (ДПФ) длины N = 2 t

N -1

X (m) = ^x (n) exp n=0

m = 0,..., N - 1 запишем в форме

X (m) = ^x (n) E (m • n), me G = {0,_,N-1}.

Базисные функции ДПФ обладают свойствами:

1)    E (n • m ) = E (n) + E (m); 2)    E (N ) = E (0) = 1; 3)    E (pk-1 ) = exp 12N1, N = p.

Введём ДОП на k -фундаментальной области G_k со свойствами базисных функций Л _к , аналогичными свойствам базисных функций ДПФ:

• 1)    ^Л _к ⁽ m ⁺ n ) = ^Л к ⁽ m ) •Л к ⁽ n );

• 2)    Л к ( a ^к ) = 1, Л к (0) = 1;

nm

2 п i

N

^Л к ^{( a к - 1)} = ^exP ‘

2 • п • i

Norm ( a ) ^к

^{4) Л} к ^{( a x} ) = ^Л к -1 ^{( x} ).

В работе [5] показано, что функция Л _к имеет вид:

Л _к ( x ) = exp { C 1 • x + C ₂ • x } , где

C =     -2-K' i •“ k,

¹ Norm ( a ^t ) ^ ( a-a )

C =     2-ni •a t.

² Norm ( a ^t ) - ( a-a )

Тогда фрактальное дискретное преобразование Фурье (ФДПФ) будет иметь вид:

X (m ) = S x (n )‘Л t (m • n), m e Gk■(5)

ⁿ e G_t

В работе [5] показано, что справедлива теорема:

Теорема 2. Пусть a - основание канонической системы счисления с Norm ( a ) >  2, множество G k -

k -фундаментальная область, тогда преобразование (5) с базисными функциями Л _t ( n ) = exp { C 1 • n + C ₂ • n } ,

где n e G k и

C =

C 2 =

- 2 • я • i •a ^t Norm ( a ^t ) " ( a-a ) 2 • я • i •a ^t Norm ( a ^t ) • ( a-a )

является ортогональным.

Учитывая коэффициенты (4), выражение для Л _t ( x ) может быть преобразовано к виду:

^Л t ( ^x ) = ^exP

П‘ i • Im ( a ^t • x ) Norm ( a ^{t - 1} ) • Im ( a )

3. Фрактальное дискретное косинусное преобразование

Как известно [6]–[8], ДКП имеет вид

N -1

X ( m ) = X ( m ) S x ( n )

n =0

• cos

Гя- ^m • ( ^{2 n} + 1 ) )

I     2 N     )

где % ( n ) =<

' 1, n = 0

N

—, n ^ 0

N

Пользуясь тем, что

.

Гя* n • ( 2 x + 1 ) ) 1 cos ---—--- = -

[Я' n • ( 2 x + 1 ) 1 ^exp I ' N i l ⁺

2 N

[ я* n • ( 2 x + 1 ) 1

exp-------- -1

2 N

)

,

определим базисные функции фрактального аналога ДКП, связанные с базисными функциями фрактального ДПФ, таким же образом, что и классическое ДКП связано с классическим ДПФ:

^Л COS t ( ⁿ , ^x ) = 2 ( ^Л t +1 ( ⁿ • ( ^x + ^в ) ) + ^Л t +1 ( ⁿ • ( ^{x + e} ) ) ) .⁽⁷⁾

С учётом соотношений (6)–(7) получим:

Л COS k ( n , x ) = cos

Я' Im ( a ^{t + 1} • n • ( x + в ) ) Norm ( a ^t ) • Im ( a )

.

В отличие от базисных функций классического ДКП, в котором параметр сдвига в равен 2, для вводимого преобразования в зависит от длины преобразования и нормы основания, т.е. конкретного квадратичного расширения.

Найдём значение в , например, для Norm ( a ) = 2 . Параметр в будем подбирать из соображений ортогональности:

S Л COS k ( p , x ) • Л COS k ( q , x ) = 0, p ^ q .

x ^e G t

Подставив вместо каждого Л COS_t ( p , x ) (7), получим:

Л COS k ( p , x ) •Л COS k ( q , x ) =

^Л t +1 ( p ( ^{x +в} ) ) ^+Л t +1 ( p ( ^{x +в} ) ) ^Л t +1 ( q ( ^{x +в} ) ) ^+Л t +1 ( q ( x ^+e ) ) —

^Л t +1 ( p ( ^{x +e} )M t +1 ( q ( ^{x +в} ) ) ^+Л t +1 ( p ( x ^+в ) ) ^ ^Л t +1 ( q ( x ^+e ) ) ^{+ +Л} t +1 ( p ( ^{x +e} )M t +1 ( q ( ^{x +в} ) ) ^+Л t +1 ( p ( ^{x +e} )M t +1 ( q ( ^{x +e} ) )

Используя свойства ФДПФ, получим:

S Л t+1 ((p+q)(x+в))+Л t+1 ((p+q)(x+e)) =0, xe Gt

Л t+1 (e( p+q)) S Л t+1 (x (p+q))+ xe Gt

^+Л t +1 ( ^e ( p ⁺ q ) ) S "^ t +1 ( ^x ( p ⁺ q ) ) = ⁰.

x e G t

Если p + q = 0 (mod a ), то, полагая p + q = a T , получим первое уравнение:

Л t+1 (ea T )• S Л t+1 (xa T)+ xeGt

+Л t +1 ( ea T ) • S Л t +1 ( x a T ) = 0.

x ^e G t

Так как Л _t ( a • x ) = Л _t -1 ( x ), то получим:

Л t ( в T ) • S Л t ( xT ) + Л t ( в T ) • S Л t ( xT ) = 0. x e G_k                            x e G_k

В силу теоремы 2:

S Л t ( xT ) = 0 и S Л t ( xT ) = 0.

x e G_k                      x e G_k

Таким образом, при p + q = 0(mod а ) параметр р не может быть определён однозначно.

Если p + q = 1 (mod а),    то, очевидно, p + q = 1 + аT можно заменить на 1, и тогда сумма

|     | n- m • ( 2 • x + 1 ) |

B™ = < cos ------------- ; m = 0,

² N  II     2 N    I

2 N - 1 ^

примет вид:

^Л k +i ( Р ) • Е ^Л k +i ( x ) ^+Л k +i ( Р ) • Е ^Л k +i ( x ) = ⁰. ⁽⁸⁾ x е G_k                           x е G_k

Так как мы проводим рассуждения для

Norm ( a ) = 2, то можно сумму Е Л k _{+ 1} ( x ) разделить ^{x е} G k

образует базис 2 N -мерного пространства, который, как известно, не является ортогональным (функции

cos

Г ^n- m ( ² x ⁺ 1 ) )

V ² N I

и

cos

^{Г n-} k ^{( 2 x +} 1 ) 1

V ² N I

при

на две суммы:

Е Л k .1 ( x ) = Е ( Л k + ( a x ) + Л _{k + 1} ( a x + 1 ) )       (9)

x е G_k                x е G_k - 1

для k > 1.

Подставив в (8) правую часть (9), получим:

Е (Лk+1 (ax) + Лk+1 (“x + 1)) = x eGk-1

m + k = 2 N не являются ортогональными). Однако N функций

Г п- m • ( 2 x + 1 ) 1

cos -------------- ; m = 0,..., N - 1 >

I 2 N I

Л k +1 ( P )

Л k +1 ( P )

Е Л k +1 ( x ) .

^{x е} G k

Последующие итерации процесса приводят к ра-

венству:

k+1                        A f R ^ k+1 / \

П(1+Л(1))=-Л4;вт П+Л,(1)

i =2                      ^Л k +1 ^{( Р )} i =2

Так как справедливо очевидное равенство

(1+Л<1>)=(1+Л?’ то равенство (10) преобразуется: k+1

. +1                          П ( 1 +Л ( 1 ) )

П(1+Л (1))=-Л k+1 (-w

¹=²                            П л ( 1 )

=2

образуют ортогональный базис N -мерного пространства.

Аналогичная ситуация возникает и в рассмотренном случае. Функции Л COS_k ( p , x ) и Л COS_k ( q , x ) неортогональны при p + q = 0 (mod a ^{k + 1}). В отличие от классического ДКП определение целого алгебраического числа – номера «парной неортогональной» функции представляет некоторые трудности при его аналитическом определении, однако этот элемент может быть определён алгоритмически.

Алгоритм 1.

for p, q е Gk+1 do mtrGram[p,q] = Е ЛCOSk (p,x) •ЛCOSk (q,x)

x е Gk end for

D k = {}

BadNumbers = {}

Полученное равенство позволяет определить р :

k +1

П л , ( 1 ) = -Л k +1 ( - 2 Р ) .

i =2

Воспользовавшись свойствами функций ФДПФ, получаем тождество, которое и помогает определить в :

^Л k +1 ( Р ) - Е ^Л k +1 ( ^x ) ^+Л k +1 ( Р ) - Е ^Л k +1 ( ^x ) = 0,

xе Gk k-1    A

x ^e G k

^Л k +1 | Е ^a i I= ^Л k +1 ( ^{a k} ) ^-Л k +1 ( ^{- 2 p} ) ,

V i =0     7

. ( “ k ^- 1¹ .                                   _

Л_к 11------ I = Л. . ( a - 2 p ) , следовательно,

V a- 1 I ^x '

a ^{k + 1} - 2 a ^k + 1

2( a- 1)

4. Ортогональность базисных функций

Множество

for p е Gk+1 do if p е BadNumbers then continue end if if mtrGram[p, p] = 0 then

BadNumbers = BadNumbers и {p} continue end if

Dk = Dk u {p} for q е Gk+1 n p do if mtrGram[p, q] <> 0 then

BadNumbers = BadNumber и q end if end for end for

Данный алгоритм разбивает множество из Norm ( a ) k ^{+ 1} номеров на два подмножества: множество номеров D_k и множество номеров D_k ^* , для которых функции Л COS k не ортогональны функциям Л COS k с номерами из D_k . На рис. 2 а – в изображены область преобразования, на которой определён входной сигнал, и область, в которой лежит спектр. Центр каждого квадратика соответствует алгебраическому целому

числу. Изображённые области соответствуют основа-

- 1 + i 4l

ниям a 1

- 1 + i , ^ 2 — — i42 и ^ 7 —

Алгоритм 1 позволяет найти множество D_k , элементами которого занумерованы ортогональные базисные функции. Это позволяет дать основное определение.

Определение 3. Фрактальным дискретным косинусным преобразованием (ФДКП) называется преоб- разование:

X ( m ) —X ( m ) ^ x ( n ) -Л COS k ( n , m ),          (13)

ne G где m e Dk,

% ( m ) - нормирующий коэффициент:

% ( m ) —

k у Norm (a) '

у Norm ( a )

, m + m = 0 (mod a ^k )

, m + m ^ 0(mod a ^k )

Из доказанной ортонормированности преобразования легко следует формула обратного преобразования.

□□□□■■■■  □■□□■■□□□□□□■■■■  □□□□■■■■□□ ■■     ■□ ■□

Рис. 2а. a 1 — - 1 + i

■■■■□□□□ ■□□■□□■■

■■■■□□□□ ■□□□□□□□

■■■■□□□□ ■□■■□□□■

■■■■□□□□ ■■■■□■■■

Рис. 2б. a ₂ — - i42

Рис. 2в. a ₇

- 1 + i 41

Определение 4. Обратным фрактальным дискретным косинусным преобразованием (ОФДКП) называется преобразование:

x (m)— ^ ^( n )• X (n )-Л COSk (n, m),         (14)

ne D, где m e Gk,

% ( n ) - нормирующий коэффициент:

% ( n ) ^—

Norm (af ‘

k у Norm (a)

, n + n = 0 (mod a ^k )

, n + n ^ 0(mod a ^k )

Нормирующий коэффициент для разных длин преобразований и разных оснований канонических систем счисления будет разным.

Заключение

В работе синтезированы ФДКП – аналоги ДКП на предфрактальной области, ассоциированной с КСС. Важной особенностью ДКП является существование для них быстрых алгоритмов вычисления, полученных различными методами: кронекеровская факторизация [6], обобщённое полиномиальное преобразование [9], сведение преобразования к умножению элементов прямых сумм конечномерных пространств. Ряд этих подходов либо неприменим, либо перенесение на рассматриваемый случай представляется весьма сложным. Таким образом, синтез быстрых алгоритмов рассмотренных преобразований методами, отличными от сведения вычисления ФДКП к вычислению ФДПФ, представляется актуальной задачей.

Работа выполнена при поддержке Российского фонда фундаментальных исследований (гранты 12-01-00822-а, 13-01-97007-р_поволжье_а).