Применение канонических систем счисления в задаче построения неразделимых Хааро-подобных вейвлетов

В настоящее время вейвлет-преобразование нашло широкое применение в обработке изображений, особенно в задачах компрессии цифровых изображений. Большинство вейвлетов, используемых в обработке изображений являются разделимыми, что влечет появление различных артефактов на изображении, включая блочные и линейные, к которым глаз человека особенно чувствителен [1]. В связи с этим, возникает вопрос о необходимости, разработки методики построения неразделимых вейвлет базисов.

В работе [2] был рассмотрен вопрос о конструировании многомерных неразделимых аналогов базиса Хаара. Такой вейвлет был определен, как вейвлет-базис над L ² (R ⁿ ) с компактным носителем, соответствующий кратномасштабному анализу, порожденному масштабирующей функцией вида, где X q ( x ) характеристическая (индикаторная) функция компактного множества Q :

[ 1 x е Q ,

XQ ( x ) = L     л

^Q      [ 0 x e Q .

В этой же работе показано, что такой вейвлет-базис над L ² (R ⁿ ) может быть построен на основе характеристической функции x q ( x ) компактного множества Q , только тогда, когда Q – интегральное самоподобное покрытие R ⁿ с единичной мерой Лебега.

Построение таких преобразований, а именно отыскание масштабирующей функции является довольно сложной задачей, что затрудняет использование этого метода. В работах [1], [3] был предложен эффективный и простой метод построения таких вейвлет-базисов над L ²(R²) с использованием результатов теории канонических систем счисления (КСС). В этой работе была рассмотрена возможность построения таких вейвлет-базисов, только для систем счисления, основаниями которых являются целые Гауссовы числа.

В настоящей работе представлено обобщение метода построения неразделимых Хааро-подобных вейвлет-преобразований для всех мнимых квадратичных полей, в которых существуют позиционные системы счисления.

Структура статьи следующая. В разделе 2 будут даны необходимые определения из теорий кратномасштабного анализа [2] (КМА). В разделе 3 представлены сведения из теории канонических систем счисления. Далее, в разделе 4 приведено теоретическое обоснование предложенного обобщения метода построения неразделимых вейвлет-преобразований. Методика построения неразделимых хааро-подоб-ных вейвлет-базисов для произвольной системы счисления приведена в разделе 5. В разделе 6 приведены примеры.

2.    Некоторые определения из теории кратномасштабного анализа

Определение 1 : Линейное преобразование A , определенное на множестве R ⁿ , является допустимым растяжением для решетки Г = Z² на множестве R ⁿ если оно удовлетворяет следующим условиям: 1) A Z² с Z², где A Г = { y : y = Ax , x е Z² } ;

• 2)    Для всех собственных чисел Xi преобразование выполняется |Xi| > 1.

3.    Канонические системы счисления в квадратичных полях

Другими словами, матрица преобразования A должна быть целочисленной матрицей расширяющего преобразования.

Определение 2 : Вейвлет-базис B , связанный с матрицей допустимого растяжения A , это семейство функций, из L ²(R²) , членами которого являются A – растяжения и Z ⁿ – сдвиги конечного ортонор-мированного множества

5 = ( v ¹ — V m } с L (R n ), где m е N ⁺ .

Пусть Q( d ) есть квадратичное поле Q( 4d ) = { z = a + b4d ; a,b е q } , d е Z, свободно от квадратов. В работе будем рассматривать мнимые квадратичные поля, т.е. d < - 1.

Определение 3: Если для элемента z = a + bld e Q(Vd) норма и след – целые числа:

Norm ( z ) = ( a + bld )( a - bld ) = = a ² - db ² e Z,

Tr ( z ) = ( a + bld ) + ( a - b[d ) = 2 a e Z,        (2)

то элемент называется целым алгебраическим числом поля Q( d ) . Целое алгебраическое число z = a + bid называется целым Гауссовым числом, если a e Z и b e Z .

В работах [5], [6] введено понятие канонической системы счисления в кольце S( d ) целых элементов поля Q( d ).

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

k ( z )

z = ^ z j a j , z j e D = { o,1, . , Norm ( a )| - 1 } . j = o

Определение 5: Пара ( a , D ) называется канонической системой счисления в кольце S( d ) целых поля Q( d ) .

Иногда для представления некоторого числа z в КСС ( a , D ) используют, так называемую позиционную запись: Z = ⁽ z k ( z ) , z k ( z ) - _ 2 o ) a , где z j ^e D .

Лемма 1: Пусть D – множество цифр некоторой КСС в кольце S( d ) целых элементов поля Q( d ), a - ее основание, тогда D - полная система вычетов по модулю a для кольца S( d ) и содержит Norm ( a ) элементов.

Доказательство: Согласно определению КСС, любое число представимо в форме t z = ^ ajaj, aj e D , тогда z = a0 mod(a), следова-j=o тельно, множество D является системой вычетов по модулю a . Покажем, что эта система является полной: предположим, что существуют такие c, d e D , такие, что c * d но c = d mod(a). Возьмем

t e = ^ ajaj, aj- e D, такое, что c - d = ea, тогда j=o

( c ) _a и ( a t ... a ₀ d ) _a - две различные записи числа c в позиционной КСС, что противоречит однозначности представления чисел в системе счисления.

Лемма 2: Пусть (a, D) - КСС в кольце S(Vd), ее основание - число a = a + bVd , a, b e Q а множест- во

a)

b)

D = { d o , d 1 , d 2 ... d Norm ( _a)|- j } ^- набор цифр, тогда:

( a bd )

матрица умножения A =         произвольного

(b a )

числа z e S( d ) на основание системы счисления a будет являться матрицей допустимого растяжения для Z² , либо сводится к таковой умножением на 2;

множество K = { k o , k_x . k N_{orm ( a )}| - 1 } , состоящее из Norm ( a ) элементов и построенное по правилу k l = d l , будет полной системой вычетов для множества классов эквивалентности Z²/ A Z².

Доказательство:

• a)    Покажем, что элементы матрицы A целые числа. Пусть d = 2, 3 mod(4), тогда из (1) и (2) следует что a e Z. Перепишем (1) в виде b ² d = Norm ( a ) - a ², здесь правая часть - целое число, следовательно, левая часть также должна быть целым числом. Так как b e Q , то

m b = —, m e Z, n e N . Переписав равенство, получим

n

mm

-d d = Norm (a) - a . Левая часть — d будет це- n

n

лой, только когда n ² | d , поскольку, нию КСС, число d – свободно от единственно возможный случай:

по определе-квадратов, то n = 1. Тогда

m

b = — = m, m e Z .

Пусть d = 1mod(4), тогда из (1) и (2) следует, что 2 a e Z. Перепишем (1) в виде 4 b ² d = 4 Norm ( a ) - 4 a 2 , здесь правая часть - целое число, следовательно, левая часть также должна быть целым числом. Так как b e Q , то

m b = —, m e Z, n e N . Переписав равенство, получим

n

^m               2 ^m

4— :2- d = 4 Norm ( a ) - 4 a . Левая часть 4— d будет

n

n

целой, только когда n2 |4d, поскольку по определению КСС число d - свободно от квадратов, то возможны только два случая:   n = 1, тогда mm b = — = m, m e Z и n = 2, тогда b = —, m e Z.

Для обоих рассмотренных случаев матрица ^A – либо целочисленная, либо сводится к таковой умножением всех элементов на два.

Покажем, что матрица A – матрица расширяю-

Рассмотрим

преобразования.

щего

det( A ) = a ² - b ² d = Norm ( a ) >  2. Собственные значения матрицы определяются из уравнения

0 = det( A - X I ) = ( a -X )² - b ² d =

= ( X - ( a + b4d ))( X - ( a - bjd ))

и равны X = a ± b4d . Так как Norm ( a ) >  2, то λ= a ± bd > 1. Нетрудно видеть, что для матрицы A' = 2 A , это неравенство также справедливо, т.к. для этого случая X = 2( a ± b4d ) и, следовательно, |X| >  1.

Таким образом, матрица A - целочисленная матрица расширяющего преобразования, следовательно, является матрицей допустимого растяжения согласно определению 1 .

• b)    Покажем, что K будет полной системой вычетов для множества классов эквивалентности Z² / A Z². Пусть v = ( x , y ) ^T е Z², где T - символ транспонирования, тогда z = x + y4d е S( 4d ). Так как ( a , D ) - КСС, то D - полная система вычетов для множества S( 4d )/ α S( Jd ), согласно лемме 1 . Тогда существует единственное d l е D , такое, что, z = m a + d l для некоторого m = s + tVd е S(V d ), поэтому v = A ( s , t ) ^T + k₁ , k_t е K и число k l уникально. Если это не выполняется, то должен существовать элемент d p е D , d p * d l , такой, что z = n a + d p , для некоторого n е S( 4d ), что противоречит однозначности представления z в системе счисления ( a , D ).

Пусть задана система счисления ( a , D ), тогда произвольное комплексное число z е C будет иметь вид [7]:

k ( z )        .        - 1

z = Z z j a j + Z z j a j , Z j е D , j = 0         j =-»

где первой сумме соответствует целая часть z , а второй - дробная часть z .

Определение 6: Фундаментальной областью T ( a , D ) е C КСС ( a , D ) в кольце S( 4d ) целых элементов поля Q( 4d ), назовем множество комплексных чисел с нулевой целой частью, т.е:

- 1

T ( a , D ) = Z d j a j , d j е D . j =-∞

Так, например, в кольцах S(V-1), S(V-2), S( V-7) существуют бинарные системы счисления, основания которых, соответственно: a = - 1 + i , .            -1 + i 77

a = iV2 и a =---—. Фундаментальные области этих систем счисления представлены на рис. 1.

а)                               б)

в)

Рис. 1. Фундаментальные области, бинарных канонических систем счисления: a) a = - 1 + i б) a = i41 в) a = ¹ + 2 7

Покажем, что фундаментальные области КСС образуют непересекающееся самоподобное покрытие комплексной плоскости:

Теорема 1: Пусть пара ( a , D ) КСС - в кольце S( 4d ) целых элементов поля Q( 4d ) , тогда сдвиги фундаментальной области T ( a , D ) этой КСС на слагаемое из кольца S( 4d ), образуют непересе-кающееся покрытие комплексной плоскости C , т.е. выполняется следующее:

^C = U s е S( v d ) ( T ( a , ^D ) + s )

(T (a, D) + s^p (T (a, D) + s 2) = 0, s1 * s2, s1,s2 е S(4d).

Доказательство : Любое число z е C представимо в КСС ( a , D ) в виде бесконечной суммы и может быть представлено в виде k ( z )

z = Z z j a j + T ( a , D ), z j - е D . Следовательно, варь- j = 0

k ( z )

ируя целую часть Z z j - a j , z j - е D , можем покрыть j = 0

сдвигами фундаментальной области T ( a , D ) всю комплексную плоскость C . Поскольку k ( z )

Z z j a j , z j е D есть запись целого числа j = 0

s е S(4d), получим, что T(a, D) покрывает комплексную плоскость C посредством сдвигов на слагаемое из S(4d). Исходя из единственности пред- ставления числа z е C в КСС (a, D), можем утверждать, что фундаментальные области не пересекаются, т.к. предположение обратного приводит к противоречию.

• 4.    Теоретическое обоснование обобщения метода построения неразделимого вейвлет-преобразования

1) В работе [3] сформулированы следующие три теоремы, которые можно рассматривать как критерии построения КМА, ассоциированного с парой (Z ⁿ , A ) :

Теорема 2: [3] Пусть A допустимое растяжение для Z ⁿ и Q – измеримое подмножество R ⁿ . Тогда функция ф = | Q | ¹ х q является масштабирующей функцией КМА ассоциированного с парой (Z ⁿ , A ), и только если выполняются условия:

• 1)    Q покрывает R ⁿ посредством целочисленных сдвигов;

• 2)    AQ = U ( Q ⁺ к ) Для некоторой полной системы к е K

вычетов K для Z ⁿ / A Z ⁿ ;

Теорема 3: [3] Пусть K – полная система вычетов для множества классов эквивалентности Z ⁿ / A Z ⁿ . Тогда любое интегрируемое решение уравнения ф ( x ) = E k _е K ф ( Ax - к ) единственно вплоть до умножения на константу и имеет носитель в компактном множестве вида