Содержание к диссертации
Введение
ГЛАВА 1. Предварительные теоретические сведения .. 15
1.1. Необходимые сведения из теории кратномасштабного анализа 15
1.2. Необходимые сведения из теории канонических систем счисления 22
1.2.1. Целые элементы в квадратичных полях 22
1.2.2. Канонические системы счисления в квадратичных полях 22
1.2.3. Примеры канонических систем счисления и соответствующих им фундаментальных областей 28
1.2.4. Решетки над кольцами целых алгебраических чисел 33
1.3. Критерии существования двумерных аналогов базиса Хаара 34
1.4. Метод построения двумерных аналогов вейвлетов Хаара 35
ГЛАВА 2. Обобщенный метод построения неразделимых вейвлетов на основании фундаментальных областей канонических систем счисления 37
2.1. Теоретическое обоснование обобщения метода построения двумерных аналогов базиса Хаара 37
2.2. Обобщенный метод построения двумерных неразделимых вейвлетов Хаара 46
Основные результаты главы 2 50
ГЛАВА 3. Алгоритмы компрессии изображений основанные на неразделимых вейвлет-преобразованиях с носителями на фундаментальных областях КСС 51
3.1. Уравнения вейвлет-декомпозиции и вейвлет-реконструкции 51
3.2. Одномерные развертки двумерных сигналов 52
3.3. Описание алгоритмов декомпозиции и реконструкции сигнала на основе обобщенных вейвлет-базисов Хаара 55
3.3.1. Общая идея алгоритмов декомпозиции сигнала 55
3.3.2. Алгоритм декомпозиции сигнала с полным деревом 56
3.3.3. Алгоритм декомпозиции сигнала с частичным деревом 60
3.3.4. Алгоритм реконструкции сигнала с полным деревом декомпозиции 62
3.3.5. Алгоритм реконструкции сигнала с частичным деревом декомпозиции 64
3.4. Метод компрессии полутоновых цифровых изображений 65
3.5. Метод декомпрессии полутоновых цифровых изображений 66
3.6. Программная реализация методов компрессии и декомпрессии
полутоновых изображений 67
Основные результаты главы 3 71
ГЛАВА 4. Экспериментальные исследования 72
4.1. Компрессия синтезированных изображений 73
4.1.1. Изображения «градиент» 73
4.1.2. Изображения «линии» 77
4.2. Компрессия реальных изображений 80
4.2.1. Изображения из набора «Waterloo Grey Set» 80
4.2.2. Текстурные изображения 84
4.2.3. Дактилограммы 90
Основные результаты главы 4 92
Заключение 93
Список использованных источников
- Необходимые сведения из теории канонических систем счисления 22
- Примеры канонических систем счисления и соответствующих им фундаментальных областей
- Теоретическое обоснование обобщения метода построения двумерных аналогов базиса Хаара
- Описание алгоритмов декомпозиции и реконструкции сигнала на основе обобщенных вейвлет-базисов Хаара
Введение к работе
Цель работы. Целью работы является разработка методов синтеза и исследование характеристик обобщенных неразделимых двумерных вейвлет-преобразований Хаара в приложении к задачам обработки цифровых изображений.
Актуальность темы. Вейвлет-преобразования широко используются в задачах обработки изображений, в частности, в задаче компрессии цифровых изображений [1, 2, 10, 15, 18, 19, 22, 24, 25, 31, 34, 35, 36, 37, 38, 39, 40, 85]. В отличие от других методов компрессии с преобразованием [27, 45], вейвлет-методы сжатия используют информацию об избыточности изображения при различных масштабах, что позволяет добиться высокой их эффективности [25, 34,35, 69, 83, 84].
Самой ранней работой, которую можно отнести к прототипам вейвлет теории принято считать работу Хаара (Нааг) [54]. В этой работе было показано, что можно построить кусочно-постоянную функцию 1, JC є [0,1/2), i//(x) = -\, х є [1/2,1), 0, [0,1), растяжения и сдвиги, которой, порождают ортонормированный базис в L (R). Однако, как впоследствии показано в работе Стрёмберга (Stromberg) [77], кусочно-постоянные приближения для гладких функций далеки от оптимальных. Так, например, в работе [68] было показано, что кусочно-линейное приближение дает меньшую погрешность аппроксимации, что стимулировало дальнейшие исследования. Следующим шагом развития вейвлет-теории стало построение Стрёмбергом [77] такой кусочно-линейной функции у/, которая также порождает ортонормированный базис и дает лучшие приближения для гладких функций. Далее Мейером (Meyer) [30, 71, 72] было построено целое семейство ортонормированных вейвлет-базисов, порожденных бесконечно дифференцируемыми функциями у/. Это дало новый импульс исследованиям, что привело к открытию знаменитых вейвлетов Добеши (Daubechies) [46] с компактным носителем. Систематизированная теория построения ортонормированных вейвлет-базисов была создана Мейером и Малла (Mallat), благодаря разработке теории кратномасштабного анализа сигнала (КМА) [68, 69]. В основу этой теории легли идеи, развитые Бартом (Burt) и Адельсоном (Adelson) [44] при анализе изображений на нескольких уровнях разрешения.
В 1992 году в работе [52] Грёхениг (Grochenig) и Мадич (Madych) охарактеризовали неразделимые вейвлеты, которые представляют собой многомерные аналоги базиса Хаара. Такой вейвлет-базис был определен, как вейвлет-базис над L (R") с компактным носителем, соответствующий кратномасштабному анализу, порожденному масштабирующей функцией вида ф(х) = XQ(X)- гДе ZQ(X) характеристическая функция (индикатор) компактного множества QczR", образующего интегральное самоподобное покрытие [53, 59, 65, 66, 67, 79] пространства R". После опубликования этой работы интерес к проблеме построения неразделимых вейвлетов существенно возрос, и множество авторов [42, 43, 62, 63, 64, 76, 78, 79] рассматривали в своих работах построение таких вейвлет-базисов на целочисленных решетках. Однако, вопрос о разработке общего подхода к определению носителей, пригодных для Построения таких базисов, оставался открытым.
В 1999 г. в работе [74] и позже в [75] Мендевиль (Mendevil) и Пише (Piche), исходя из критериев предложенных Грёхенигом и Мадичем, предложили метод построения двумерных аналогов базиса Хаара. Опираясь на тот факт, что носитель масштабирующей функции (множество Q) должен являться интегральным самоподобным покрытием плоскости, они предложили использовать в качестве носителя фундаментальные области [57, 73, 82] систем счисления с целыми гауссовыми основаниями. В дальнейшем была показана эффективность применения введенных вейвлет-базисов в задаче компрессии изображений [42, 64, 70, 76, 78].
Идея вейвлет-сжатия такова: к изображению применяется вейвлет-преобразование, затем коэффициенты преобразованного изображения квантуются, к оставшимся коэффициентам может быть применено статистическое кодирование. Сжатое изображение восстанавливается путем декодирования коэффициентов и применения обратного преобразования к результату. Предполагается, что в процессе квантования коэффициентов разложения, потери информации невелики. Таким образом, вейвлет-сжатие, как и другие методы компрессии с преобразованием, включает три основных этапа [80]:
1) разложение исходного сигнала по ортогональному базису;
2) квантование коэффициентов разложения;
3) кодирование квантованных отсчетов.
Процесс квантования, позволяет значительно сократить объем памяти требуемый для хранения изображений, но при этом и вносит основную погрешность. Искажение восстановленного сигнала можно минимизировать различными путями, в том числе и посредством адаптивного выбора наиболее подходящего для данного класса изображений вейвлет-базиса.
Компрессия (сжатие), как и большинство других задач обработки изображений, является двумерной задачей. Двумерные вейвлет-преобразования, применяемые в обработке изображений, как правило, являются разделимыми, т.е. представляют собой суперпозицию двух одномерных преобразований (например, сначала обработка по столбцам, затем по строкам) [34, 45, 69]. Вейвлет-сжатие, в силу квантования коэффициентов разложения, является сжатием с потерями, и поэтому неизбежно возникновение артефактов на восстановленном изображении. Использование разделимых вейвлетов приводит к появлению блочных и
Теория канонических систем счислений, как самостоятельная математическая теория, возникла относительно недавно. В 1969 г. в монографии Кнута (Knuth) [60] было упомянуто, со ссылкой на работу Питти (Pitti), что любое комплексное число с целочисленными компонентами (целое гауссово число) представимо в виде конечной суммы степеней основания с коэффициентами из алфавита {0,1}: к z = a + bi= Y,zj(-l±i)J,Zj={0,l},a,bEZ, j=0 с некоторым k = k(z), зависящим от z. Другими словами, в кольце целых гауссовых чисел существуют «бинарные» системы счисления с основанием (-1±/). В 1975 г. Катай и Сабо (Szabo) в работе [55] доказали существование 1 4 систем счисления вида {-В ± і, {0.. .В }), В є Z и показано, что любое целое гауссово число представимо в виде конечной суммы: к z = a + bi= Jrzj(-B±i)j, zje ...B2\, a,beZ,BeZ+, j=0 с некоторым k = k(z), зависящим от z. Произвольное комплексное число представимо в виде бесконечной суммы степеней основания с коэффициентами из алфавита: к z = a + bi=JTzj(-B±i)j ,ZjE ...B2\,a,bER,BeZ+, -00 с некоторым к = k(z), зависящим ОТ Z.
В этой же этой же работе впервые введен термин каноническая система счисления. Теме систем счисления с целым гауссовым основанием посвятил ряд работ [47, 48, 49, 50, 51] Гилберт (Gilbert), в основном они затрагивают проблемы арифметики и представления чисел в таких системах.
Позже, Катай и Ковач в работах [56, 58, 61] представили исчерпывающее описание канонических систем счисления в квадратичных полях и дали аналитический критерий их существования для произвольного квадратичного поля Q(4d).
Использование теории КСС дает возможность обобщить результаты прототипных работ [74, 75] на все канонические системы в мнимых квадратичных полях, что и послужило мотивацией для постановки указанной выше цели работы и определило задачи диссертационного исследования и структуру работы.
Задачи диссертационной работы.
1. Теоретическое обоснование возможности построения обобщенных неразделимых вейвлет-преобразований Хаара и разработка метода синтеза таких преобразований.
2. Синтез алгоритмов вейвлет-декомпозиции и вейвлет-реконструкции сигналов на основе предложенного подхода.
3. Разработка методов, алгоритмов и программных средств компрессии цифровых изображений на основе синтезированных преобразований.
4. Экспериментальные исследования предложенных алгоритмов компрессии, сравнение с алгоритмом компрессии на основе разделимого вейвлет-преобразования Хаара.
Краткое содержание диссертации. Диссертационная работа, содержащая 101 страницу (без приложений), состоит из введения, четырех глав, заключения и списка использованной литературы, составляющего 85 наименований.
В первой главе диссертации приведены необходимые теоретические сведения из теории кратномасштабного анализа и теории канонических систем счислений. Эта глава не содержит новых результатов; включенные в нее сведения приведены для удобства ссылок и замкнутости изложения.
Во второй главе диссертации сконцентрированы основные теоретические результаты диссертационной работы. Здесь приведено теоретическое обоснование возможности построения обобщенных двумерных вейвлет-базисов Хаара. Центральным результатом этой главы является доказанная теорема, о том, что характеристическая функция фундаментальной области произвольной КСС является масштабирующей функцией соответствующего КМА.
Теорема 2.1. Пусть (a,D) - каноническая система счисления в кольце
S(V ), a = a + b4d - ее основание, D = Q,di,d2...d\Norm,a _A - ее алфавит и
T(a,D) = \ YJdjaj .djeD\
- фундаментальная область этой КСС Пусть Г§, / ч -решетка над кольцом
S(4d)
fa bd\
А =
\b а J
тогда функция ф = Хт(а,В) является масштабирующей функцией кратномасштабного анализа ассоциированного с парой (Г§, п\, А).
Из теоремы 2.1 следует метод построения двумерных аналогов вейвлет-базисов Хаара.
Так как для любой КСС (a,D) в кольце существует КМА, ассоциированный с парой (Г§, г \, А), и функция ф = Хт(а,П) является масштабирующей функцией этого КМА, то: 1) функции вейвлет-базиса определяются равенством: 7=1 где м,у - элементы унитарной матрицы с/, в которой ми= ,j = \...q, \i-\)(2j-\)K U; ; = J—COS , i = 2..,q, j = \...q, dj eD, q = \detA\ ч 2q 2) коэффициенты фильтра для преобразования с базисом у/ определяются равенствами: hj=uu J = l- 1 Si=hj i = 2...q,j = \...q.
В третьей главе диссертации рассматривается применение предложенных вейвлет-базисов к задаче компрессии изображений. Здесь синтезируются алгоритмы декомпозиции и реконструкции сигнала на основе введенных во второй главе вейвлет-базисов. Рассмотрено два случая:
1) изображение полностью покрывается фундаментальной областью КСС, для этого случая предложены алгоритмы декомпозиции и реконструкции с полным деревом декомпозиции (FDT - Full Decomposition Tree);
2) изображение покрывается фрагментом фундаментальной области КСС, для этого случая предложены алгоритмы декомпозиции и реконструкции с частичным деревом декомпозиции (PDT - Partial Decomposition Tree).
Также разработаны методы компрессии и декомпрессии изображений на основе синтезированных алгоритмов.
В четвертой главе диссертации представлены результаты экспериментов и сравнительный анализ предложенных алгоритмов с алгоритмом компрессии на основе разделимого вейвлет-базиса Хаара с точки зрения качества решения задачи компрессии. Качество компрессии оценивалось по следующим параметрам:
Коэффициент компрессии: k - где Vj - объем исходного изображения в байтах, Vaj - объем архива (компрессированного изображения) в байтах. Отношение сигнал/шум по мощности (PSNR):
( \
255 -2
j М N
PSNR = \0hgl0
{і{т,п)-ї{т,п)у
Шт=0п=0
где М, N- размеры изображения, 1(т,п) - отсчеты исходного изображения, !(т,п) - отсчеты восстановленной из архива аппроксимации исходного изображения [16].
Методы исследований. В диссертационной работе используются методы абстрактной алгебры, теории чисел, функционального анализа, теории цифровой обработки сигналов и изображений.
Практическая значимость работы. Практическая значимость работы состоит в том, что разработанные методы дают возможность адаптивного выбора вейвлет-преобразований для повышения качества решения различных задач цифровой обработки сигналов (в частности, задачи компрессии изображений) и представляют теоретическое обоснование перспективных методов решения других задач обработки цифровых изображений (фильтрация, синтез текстур).
Реализация результатов работы. Все разработанные алгоритмы реализованы программно, произведен анализ качества решения задачи компрессии предложенным методом в сравнении с алгоритмом компрессии на основе разделимого преобразования Хаара.
Апробация работы. Основные результаты диссертации докладывались на следующих научных конференциях:
- 2-й летней школе молодых ученых по дифракционной оптике и обработке изображений, Самара, 2004;
- международной конференции «Automation, Control, and Information Technologies» (ACIT), Новосибирск, 2005;
3-й летней школе молодых ученых по дифракционной оптике и обработке изображений, Самара, 2005;
- научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ПИТ), Самара, 2006.
Исследования по теме диссертационной работы выполнялись при поддержке РФФИ (проекты №№ 00-01-00600, 03-01-00736, 06-01-00736), Американского фонда гражданских исследований и развития (проект SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование", министерства образования и науки Самарской области (грант 2006 года студентам, аспирантам и молодым ученым).
Публикации. По теме диссертации опубликовано 6 работ. Все работы выполнены соискателем без соавторства. В тексте диссертации ссылки на работы автора помечены звездочками ( ).
Необходимые сведения из теории канонических систем счисления 22
В работах [55, 56, 58] введено понятие канонической системы счисления в кольце целых элементов квадратичного поля Q{4d). Определение 1.6. Целое алгебраическое число a = a±b4d называется основанием канонической системы счисления в кольце целых элементов ПОЛЯ Q(Vd), если любой целый элемент поля однозначно представим в виде конечной суммы: к z = Y,zia) у zj eD = {0,\,...,\Norm(a)\-\}, Norm(a) = a2-b2d, (1.8) с некоторым k = k(z), зависящим от z. Далее кольцо целых элементов поля Q(4d) будем обозначать S(4d). Нетрудно видеть, что кольцо S(V-l) соответствует кольцу целых гауссовых чисел. Определение 1.7. Пара (a,D) называется канонической системой счисления в кольце S(v ) целых элементов поля Q(Vd). Далее множество D = {0,l,...,M?rm(a)-l} будем называть алфавитом или множеством цифр КСС.
Лемма 1.1. Пусть поле Q(-Jd) - мнимое, и d = 2,3 (mod 4). Тогда целое алгебраическое число а = А ± 4d является основанием канонической системы счисления в кольце S(-Jd) тогда и только тогда, когда 0 -2A A2-d 2, где А - целое рациональное число [55, 58]. Лемма 1.2. Пусть поле Q(4d) - мнимое, и d = 1 (mod4). Тогда целое алгебраическое число a = —{B + 4d) является основанием канонической системы счисления в кольце S(Vflf) тогда и только тогда, когда 0 -B -(B2-d) 2,
где В - нечетное целое рациональное число [55, 58].
Замечание 1.2. Отметим, что представление целых алгебраических чисел в канонических системах счисления не требует указания знака числа. И положительные и отрицательные числа мнимого квадратичного поля записываются в «беззнаковой» форме.
Рассмотрим построение систем счислений с заданным числом цифр на примере четверичных систем счислений:
Пример 1.3. Пусть требуемое число цифр алфавита равно 4. Найдем КСС, удовлетворяющие этому условию.
Из неравенства (1.6) получим систему неравенств -2 Л 0, d = A2 -4, решив которую в целых числах, с учетом того, что d - свободно от квадратов, получим единственное решение A = -l,d = -3. Из неравенства (1.7) получим систему неравенств -4 В 0, d = B2-\6, решив которую в целых числах, с учетом того, что d - свободно от квадратов, получим два решения B = -3,d = -7 и B = -\,d = -\5. Таким образом, существует три четвертичных КСС: (-1 + іД {0,1,2,3}), 2 ЛІ\ {0,1,2,3} -1 + /л/Ї5 ) "3 + /л/7-, {0,1,2,3)1, в кольцах 8(лРЗ), S( 7), 8(-7= ) соответственно.
Введем понятие фундаментальной области КСС. Пусть задана система счисления (a,D), тогда произвольное комплексное число zeC, будет иметь вид [50]: k(z) -і z= zjaJ+ ZjaJ ,ZjD, (1.9) где первой сумме соответствует «целая» часть z, а второй - «дробная» часть числа z.
Определение 1.8. Фундаментальной областью T(a,D)czC канонической системы счисления (a,D) в кольце S(-vd) целых элементов поля Q(-\[d), назовем множество комплексных чисел с нулевой целой частью, т.е.: T(a,D) = «j z = J Zj-aJ,Zj єD ,/=-00 cC. (1.10) Замечание 1.3 Определим отображение в: С - R , так, что в:г = х + уі\-: (х,у). Обозначим через Т (a,D) образ фундаментальной области T(a,D)при отображении в: T\a,D) = 0(T(a,D)). (1.11) Примеры образов фундаментальных областей Т (a,D) двоичных, троичных, четвертичных и пятеричных КСС в мнимых квадратичных полях представлены в разделе 1.2.3. на рисунках 1.2-1.5. Рассмотрим вектор (zk(z) zk(z)-\---4) коэффициентов формулы (1.8) представления числа zeS(-4d) в канонической системе счисления (a,D). Будем называть эту последовательность адресом числа zeS(4d) в КСС
Примеры канонических систем счисления и соответствующих им фундаментальных областей
Обычно, двумерный дискретный сигнал (в частном случае -изображение) интерпретируется, как функция, заданная на двумерной целочисленной решетке, т.е. на множестве вида Г2 ={0(1,0) + [(0,1)}, 0,і є Z и при этом каждый пиксель изображения имеет две целочисленные координаты. В данном разделе рассмотрены решетки на множествах целых алгебраических чисел.
Согласно определению 1.1 решетка однозначно определяется выбором базиса, определим решетки над кольцом , следующим образом: Лемма 1.4. Решетки Г, п. над кольцами целых алгебраических чисел S(4d) порождаются базисами: 1) а = ((1,0), (0,4d)\ при d = 2,3(mod4); 2) а = ф0),(0,р , при J = l(mod4), компоненты 0 и элементов решетки имеют одинаковую четность.
Замечание 1.3. Предложенные решетки s( fd) изоморфны целочисленной решетке Г2 и элементы целочисленной решетки (хj) 6 Г2 однозначно преобразуются в элементы решетки над кольцом целых алгебраических чисел (У,/) є Г, ч посредством линейного оператора Р: (х,у)Т: 1) Р:Гъ Г8 уР:(х,у) (I 0 Ї и 0 Jd\ (Х,У)Т. ( і -П 2) Р:Гх Г8( уР:(х,у) v vi і vi \j
Ввиду замечания 1.3 исходный двумерный сигнал может интерпретироваться как заданный на решетке Г, ч.
В данном разделе приведены основные теоремы из работы [52], сформулированные для двумерного случая, которые являются критериями возможности построения КМА ассоциированного с целочисленной матрицей преобразования А и целочисленной решеткой Z .
Теорема 1.2. Пусть А допустимое растяжение для Z и Q - измеримое подмножество R . Тогда функция ф = \0\ XQ является масштабирующей функцией КМА ассоциированного с парой (Z ,А) тогда и только тогда, когда выполняются условия: 1) Q покрывает R посредством целочисленных сдвигов; 2) AQ= \J(Q + k) для некоторой полной системы вычетов К для кєК Z2/AZ2. Теорема 1.3. Пусть К - полная система вычетов для множества классов 2 2 эквивалентности Z / АЪ . Тогда любое интегрируемое решение уравнения ф(х)= ф(Ах-к) кєК единственно с точностью до умножения на константу и имеет носитель в компактном множестве вида Q= A- ki-.kiEK (1.14) 2
Теорема 1.4. Пусть А допустимое растяжение для Z и Q с R . Тогда функция Ф-XQ является масштабирующей функцией КМА ассоциированного с парой (Z ,А) тогда и только тогда, когда //(0 = 1 и Q имеет вид, данный в теореме 1.3 для некоторой полной системы вычетов 2 о множества классов эквивалентности Z / АЪ . Таким образом, вейвлет-базис пространства L (R ) может быть построен на основе характеристической функции ZQ(X) компактного множества Q, тогда и только тогда, когда множество Q имеет вид, данный в теореме 1.3, образует непересекающееся покрытие R посредством целочисленных сдвигов и имеет единичную двумерную меру Лебега.
Метод построения двумерных аналогов вейвлетов Хаара
В данном разделе приведен метод построения неразделимых двумерных вейвлетов Хаара, предложенный в работе [74]. Рассмотрим этот метод подробнее:
Пусть задана система счисления {a, D), ее основание целое гауссово число a = a + bi, a,beZ и T(a,D) - ее фундаментальная область. Матрица умножения произвольного числа z є С на основание системы счисления а, будет матрицей допустимого растяжения А для Z , и имеет вид: (а -Ь) А = {Ь а)
Согласно определению 1.4, имея матрицу допустимого растяжения А, положив T = Z2, можно построить КМА, ассоциированный с парой (Z \Л), причем масштабирующей функцией будет характеристическая функция фундаментальной области заданной системы счисления - ф = %т,а щ.
Множество D = p,\,---,\Norm(a)\-\] цифр системы счисления (a,D), образует полную систему вычетов mod а. Пусть det A\ = q, тогда, как показано в [74], вейвлет-базис искомого преобразования будет задаваться следующим соотношением:
Теоретическое обоснование обобщения метода построения двумерных аналогов базиса Хаара
Рассмотрим линейное ( 1 -О преобразование Р = і і и множество Т (a,D) = P\T {a,D)J. При таком преобразовании, аддитивные целочисленные сдвиги множества Т (a,D) образуют непересекающееся покрытие пространства R , тогда в соответствии со сформулированной леммой 1 работы [52], плоская мера Лебега множества Т (a,D) равна 1. Поэтому мера множества Т (a,D) в ( \ Ц\Т (а D)) Jd пространстве R равна /л\Г Покажем, что фундаментальная область произвольной КСС представима в виде (1.14). Лемма 2.6. Пусть задана каноническая система счисления (a, D) в кольце S(4d), тогда ее фундаментальная область представима в виде: Q= оо ЕЛ" ,-: kteK\, /=1 где А - матрица допустимого растяжения для некоторой решетки Г, К -полная система вычетов для множества классов эквивалентности Г/ AY.
Доказательство. Положим решетку Г, как решетку над кольцом s(V ), определенную условием леммы 1.4, т.е. Г=Г(.Х/\- Матрица А, ассоциированная с операцией умножения произвольного числа z є S( [d) на основание системы счисления, согласно лемме 2.2 является матрицей допустимого растяжения для решетки r( )- Построим множество К = \k0,k\...k\Norm,a\\_xj, по правилу ki=d[GD, тогда, согласно лемме2.3 оно является полной системой вычетов для множества классов эквивалентности s(4d) S(sfd) 45 Рассмотрим выражение, определяющее фундаментальную область КСС (a,D): T(a,D) = YjdjCtJ :dj eD\ l;=-oo Согласно замечанию 2.1, с умножением произвольного числа z є S(4d) на основание системы счисления ассоциирована матричная операция умножения, следовательно, а} может быть записано как А]. Далее, положив d[ = к{ и заменив индекс суммирования, получим вид, требуемый в утверждении леммы.
Теперь, с учетом доказанных лемм и критериев построения двумерных аналогов базисов Хаара, представленных в разделе 1.3, сформулируем и докажем основную теорему: Теорема 2.1. Пусть задана каноническая система счисления (a, D) в кольце S(4d), а = а + ЬлШ - ее основание, D = Q,diid2...d\Norm,a _lj - ее алфавит и T(a,D) = YjdjCti :dj GD\ - фундаментальная область этой КСС. Пусть Г, п. - решетка над кольцом п (a bd\ S(V« ) и матрица А определена как А = , тогда функция ф = %Т{а т \Ъ а) является масштабирующей функцией кратномасштабного анализа ассоциированного с парой (Г, п. ,А).
Доказательство. Согласно лемме 2.2 матрица А, ассоциированная с операцией умножения произвольного числа z є S(4d) на основание системы СЧИСЛеНИЯ, ЯВЛЯеТСЯ Матрицей ДОПУСТИМОГО раСТЯЖеНИЯ ДЛЯ решеТКИ s(Jj) Согласно лемме 2.3 алфавит D - полная система вычетов для множества классов эквивалентности S(4d)/AS(4d). Согласно лемме 2.6, фундаментальная область T(a,D) удовлетворяет виду (1.14). Согласно лемме 2.4, сдвиги фундаментальной области на элементы решетки Г5, г образуют непересекающееся покрытие плоскости R . Согласно лемме 2.5 мера множества Т (a,D) определяется соотношением (2.1), а множество Т (a,D) имеет единичную меру Лебега. Тогда по теоремам 1.2, 1.3 и 1.4 следует утверждение доказываемой теоремы.
Таким образом, согласно теореме 2.1, для любой канонической системы счисления (a, D), в кольце существует кратномасштабный анализ, ассоциированный с парой (Г,у \,Л). Причем масштабирующая функция этого КМА, есть характеристическая функция ф = Хт{а,П) фундаментальной области Т(а, D), этой КСС.
1. Доказано, что со всеми каноническими системами счислений в кольцах целых элементов мнимых квадратичных полей ассоциирован кратномасштабный анализ, причем его масштабирующая функция -характеристическая функция фундаментальной области системы счисления.
2. Разработан метод построения неразделимых вейвлет-базисов Хаара для кратномасштабного анализа, ассоциированного с каноническими системами счисления в кольцах целых элементов мнимых квадратичных полей.
Описание алгоритмов декомпозиции и реконструкции сигнала на основе обобщенных вейвлет-базисов Хаара
Пусть задана КСС с основанием aeS(4d), Norm(a) = q, и набор масштабирующих s L и вейвлет-коэффициентов wk L. Известно число уровней декомпозиции - L и размеры исходного изображения MxN. ШагО: Рассчитываются фильтры hd, gd, d є Z), согласно (2.3,2.4). Шаг 1: Строится множество t , состоящее из всех адресов а а чисел к + l-Jd, для которых справедливо 0 к М,0 1 N.
Для всех l = l...L строится множество ) : Шаг 2: Для всех / = 1-1...0 и для всех s , fn і таких, что (f)a(a,D) G D согласно (3.5) выполняется вейвлет-реконструкция: и к к к-\ ШагЗ: Имеем множество масштабирующих коэффициентов sn і V a(a,D)
Каждому адресу a\a,D)є DL, согласно определению КСС, ставятся в соответствие числа решетки S(-Jd), т.е. a(a,D) к+1 или a(a,D) {kj)- Трактуя исходное изображение как заданное на решетке S(Jd), осуществляется переход от одномерной индексации отсчетов изображения к двумерной, т.е. 1(к,1) -» 1{а а щ).
Шаг 4: Зная размеры исходного изображения, получим аппроксимацию исходного сигнала, посредством переупорядочивания отсчетов изображения заданного на решетке S{4d): I(kJ) о /(w,«).
Данный алгоритм позволяет получить аппроксимацию исходного изображения по частичному набору коэффициентов декомпозиции.
В данном разделе приведены основные шаги метода компрессии изображения на основе обобщенных вейвлет-базисов Хаара. Компрессия изображения в архив включает следующие этапы: 1. Производится предобработка изображения: вычитание среднего по изображению, из всех его отсчетов. 2. Выбирается КСС {a, D), определяющая структуру кратномасштабного анализа, масштабирующей функцией ф которого является характеристическая функция фундаментальной области Т(а, D) данной КСС. 3. Цифровое изображение интерпретируется, как заданное на решетке Ysn. Пиксели исходного изображения формируют множество X. 4. Находятся адреса для каждого пикселя из множества X. Длину наибольшего из минимальных адресов обозначим, как Lx a D . Адреса меньшей длины дополняются нулями слева до длины LX(aDy Полученные адреса формируют множество адресов Ах. 5. Строится вейвлет-базис согласно (2.2) и рассчитываются фильтр коэффициенты преобразования согласно (2.3-2.4). 6. Выполняется вейвлет-декомпозиция изображения (одним из представленных алгоритмов). На каждом уровне декомпозиции длина адресов уменьшается на один разряд (слева). Алгоритм декомпозиции завершается, когда длина адресов становится равной нулю, или число уровней декомпозиции достигнет требуемого значения. 7. Выполняется квантование коэффициентов разложения. 8. Выполняется кодирование квантованных коэффициентов, с использованием методов статистического кодирования. 9. Сохранение кодированных коэффициентов разложения, параметров КСС и алгоритма компрессии в архив.
В данном разделе приведены основные шаги метода декомпрессии изображения на основе обобщенных вейвлет-базисов Хаара. Декомпрессия аппроксимации исходного изображения из архива включает следующие основные этапы: 1. Чтение кодированных коэффициентов разложения, параметров КСС и алгоритма компрессии из архива. 2. Декодирование коэффициентов разложения. 3. Деквантование коэффициентов разложения. 4. Построение вейвлет-базиса согласно (2.2-2.3) и расчет фильтр коэффициентов преобразования согласно (2.4-2.5). 5. Реконструкция отсчетов аппроксимации исходного сигнала (одним из представленных алгоритмов). Алгоритм реконструкции завершается, после получения масштабирующих коэффициентов нулевого уровня. 6. Постобработка изображения: прибавление среднего по изображению, ко всем его отсчетам. 7. Формирование аппроксимации исходного сигнала.
