автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Обобщенные вейвлет-преобразования Хаара и их применение к компрессии изображений

На правах рукописи

БЕЛОВ Александр Михайлович

ОБОБЩЕННЫЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ХААРА И ИХ ПРИМЕНЕНИЕ К КОМПРЕССИИ ИЗОБРАЖЕНИЙ

Специальность 05 13 17 -

Теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

□03059083

САМАРА - 2007

003059083

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С П Королева» и в Институте систем обработки изображений РАН

Научный руководитель

Официальные оппопепты.

Ведущее предприятие

доктор физико-математических наук В М Чернов

доктор физико-математических наук, профессор А И Жданов

кандидат физико-математических наук, доцент В П Цветов

ГОУ ВПО «Омский государственный университет имени Ф М Достоевского»

Защита состоится 25 мая 2007 г в 15 часов на заседании диссертационного совета Д212 215 07 при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С П Королева» по адресу 443086, Самара, Московское шоссе, 34

С диссертацией можно ознакомиться в библиотеке СГАУ

Автореферат разослан 24 апреля 2007 г

Ученый секретарь диссертационного совета дтн, профессор

р^ ' ИВ Белоконов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Самой ранней работой, которую можно отнести к прототипам вейвлет-теории, принято считать работу Хаара (Haar) 1910 г, в этой работе показано, что можно построить кусочно-постоянную функцию у, такую, что ее растяжения и сдвиги

порождают ортонормированный базис в L2(R) Однако, как впоследствии показано в работе Стремберга (Stromberg), кусочно-постоянные приближения для гладких функций далеки от оптимальных Так, например, кусочно-линейное приближение дает меньшую погрешность аппроксимации, что стимулировало дальнейшие исследования Следующим шагом развития вейвлет-теории стало построение Стрембергом такой кусочно-линейной функции ц/, которая также порождает ортонормированный базис и дает лучшие приближения для гладких функций Далее Мейером (Meyer) было построено целое семейство ортонормированных вейвлет-базисов, порожденных бесконечно дифференцируемыми функциями ц/ Это дало новый импульс исследованиям, что привело к открытию знаменитых вейвлетов Добеши (Daubechies) с компактным носителем Систематизированная теория построения ортонормированных вей влет-базисов была создана Мейером и Малла (Mallat), благодаря разработке теории кратномасштабного анализа (КМА) сигнала В основу этой теории легли идеи, развитые в задачах компьютерной визуализации Бартом (Burt) и Адельсоном (Adelson) при анализе изображений на нескольких уровнях разрешения В 1992 году в своей работе Грбхениг (Grochenig) и Мадич (Madych) охарактеризовали неразделимые вейвлеты, которые представляют собой многомерные аналоги базиса Хаара Такой вейвлет-базис был определен, как вейвлет-базис над l}{R") с компактным носителем, соответствующий кратномасштабному

щшшзу, порожденному масштабирующей функцией вида ф = %q(x) - где Xq(.x) -

Характеристическая функция (индикатор) компактною множества С>с R", образующего интегральное самоподабное покрытие К ° После опубликования этой работы интерес к проблеме построения неразделимых вейалетов существенно возрос, и множество авторов (Эндрюс (Andrews), Бе лога й (Betogay), Лагриас (Lagrias), Ванг (Wang). Стрииартс (Strieharlz) и др.) рассматривали в своих работах построение неразделимых вбйвлет-базисов на целочисленных решетках. Однако вопрос о разработке общего подхода к определению носителей, пригодных для построения таких базисов, оставался открытым. В 1999 г. и позже в 2002 г. Мендевиль (Mendcvil) к [Мае (Piché), исходя из критериев, предложенных Грёхенигом и Мадичем, Предложили использовать в качестве носителя фундаментальные области систем счисления с целыми гауссовыми основаниями. В дальнейшем была показана эффективность применения введенных вейплет-бязисов в задаче компрессии изображений.

Компрессия (сжатие), как и большинство других задач обработки изображений, является двумерной задачей. Двумерные вей влез-преобразования, применяемые в обработке изображений, как правило, являются разделимыми, т.е. представляют собой суперпозицию двух одномерных преобразований. Вей влет-сжатие, в силу квантования коэффициентов разложения, является сжатием с потерями, и поэтому неизбежно возникновение артефактов на восстановленном изображении. Использование разделимых вейатетов приводит к появлению блочных и линейных артефактов на изображении, что является нежелательным, поскольку именно к таким ошибкам зрительная система человека наиболее восприимчива (рис. 1).

(а) (б)

Рис. 1. Артефакты восстановленных изображений для алгоритмов на основе разделимого (а) и неразделимого (6) базисов

Причиной возникновения таких артефактов является то, что разделимые вейвлеты имеют прямоугольные носители, именно на границах этих прямоугольных блоков и возникают линейные артефакты Неразделимые же вейвлеты имеют своими носителями «фрактальные» области с непрямоугольными границами, что позволяет избежать возникновения линейных артефактов Этот факт, наряду с возможностью адаптивного выбора базиса, является основной мотивацией для использования неразделимых вейвлетов на непрямоугольных носителях в задачах компрессии изображений Однако, в прототипных работах Мендевиля и Пише, задача адаптивного выбора вейвлет-базиса не исследовалась, поскольку авторы опирались на узкий класс систем счисления с целым гауссовым основанием После разработки венгерскими математиками Катай (Ка1ш) и Ковачем (Котасэ) теории канонических систем счислений (КСС) для произвольных квадратичных полей, стало возможным обобщение результатов работ Мендевиля и Пише на случай фундаментальных областей существенно более общего вида

Теория канонических систем счислений, как самостоятельная математическая теория, возникла относительно недавно В 1969 г в монографии Кнута (КпиЙ1) было упомянуто со ссылкой на работу Пити (Р1Ш), что любое комплексное число с цеточисленными компонентами (целое гауссово число) представимо в виде конечной суммы степеней основания с коэффициентами из алфавита {0,1} Кг)

г = а+Ьг= X ^(-1 + гУ, ={0,1}, а,Ьег,

J=0

то есть, в кольце целых гауссовых чисел существуют «бинарные» системы счисления с основанием (-1+0 Произвольное комплексное число представимо в виде бесконечной суммы степеней основания с коэффициентами из алфавита Кг)

г=а+Ы= £ , ={0,1}, а.ЬеК

Позже, в 1981 г Катай и Ковач представили исчерпывающее описание канонических систем счисления в квадратичных полях и дали аналитический критерий их существования для произвольного квадратичного поля

Использование теории КСС дает возможность обобщить результаты прототипных работ Мендевиля и Пише на все канонические системы в мнимых квадратичных

полях, что и послужило мотивацией для постановки указанной выше цели работы и определило задачи диссертационного исследования и структуру работы Задачи диссертационной работы.

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

2 Синтез алгоритмов вейвлет-декомпозиции и вейвлет-реконструкции сигналов на основе предложенного подхода

3 Разработка методов, алгоритмов и программных средств компрессии цифровых изображений на основе синтезированных преобразований

4 Экспериментальные исследования предложенных алгоритмов компрессии, сравнение с алгоритмом компрессии на основе разделимого вейвлет-преобразования Хаара

Методы исследований В диссертационной работе используются методы абстрактной алгебры, теории чисел, функционального анализа, теории цифровой обработки сигналов и изображений Научная новизна работы.

1 Сформулирована и доказана теорема о построении масштабирующих функций кратномасштабного анализа, ассоциированного с фундаментальными областями канонических систем счисления в мнимых квадратичных полях

2 Разработан метод построения обобщенных неразделимых вейвлет-базисов Хаара

3 Для введенных вейвлет-базисов разработаны алгоритмы вейвлет-декомпозиции и вейвлет-реконструкции сигнала с полным и частичным деревом декомпозиции

4 Для задачи компрессии полутоновых изображений на основе синтезированных неразделимых двумерных вейвлет-базисов разработаны и программно реализованы методы компрессии и декомпрессии изображений

5 Экспериментально показана эффективность предложенного подхода к адаптивному выбору обобщенных неразделимых вейвлет-базисов Практическая значимость работы Практическая значимость работы состоит в

том, что разработанные методы дают возможность адаптивного выбора вейвлет-преобразований для повышения качества решения различных задач цифровой обработки сигналов (в частности, задачи компрессии изображений) и представляют теоретическое обоснование перспективных методов решения других задач обработки цифровых изображений (фильтрация, синтез текстур)

Реализация результатов работы. Вое разработанные алгоритмы реализованы программно, произведен анализ качества решения задачи компрессии предложенным методом в сравнении с алгоритмом компрессии на основе разделимого преобразования Хаара

Апробация работы Основные результаты диссертации докладывались на следующих научных конференциях

- 2-й летней школе молодых ученых по дифракционной оптике и обработке изображений, Самара, 2004,

- международной конференции «Automation, Control, and Information Technologies» (АСГГ), Новосибирск, 2005,

- 3-й летней школе молодых ученых по дифракционной оптике и обработке изображений, Самара, 2005,

- научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ПИТ), Самара, 2006

Исс1едования по теме диссертационной работы выполнялись при поддержке РФФИ (проекты №№ 00-01-00600, 03-01-00736, 06-01-00736), Американского фонда гражданских исследований и развития (проект SA-014-02) в рамках российско-американской программы "Фундаментальные исследования и высшее образование", министерства образования и науки Самарской области (грант 2006 года студентам, аспирантам и молодым ученым)

Публикации По теме диссертации опубликовано 6 работ Все работы выполнены соискателем без соавторства

Структура диссертации Диссертационная работа, содержащая 102 стр (без приложений), состоит из введения, четырех глав, заключения и списка использованной литературы, составляющего 85 наименований IIа защиту выносятся

1 Теоретическое обоснование и метод синтеза обобщенных неразделимых вейвлет-преобразований, ассоциированных с каноническими системами счисления в мнимых квадратичных полях

2 Алгоритмы вейвлет-декомпозиции и вейвлет-реконструкции изображения с полным и частичным деревом декомпозиции для синтезированных вейвлет-базисов

3 Методы и программные средства компрессии полутоновых изображений на основе алгоритмов с полным и частичным деревом декомпозиции

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В первой главе диссертации приведены необходимые теоретические сведения из теории кратномасштабного анализа и теории канонических систем счислений Эта глава не содержит новых результатов, включенные в нее сведения приведены для удобства ссылок и замкнутости изложения

Дапее в автореферате нумерация определений, лемм и георем соответствует нумерации в тексте диссертационной работы

Определение 1 3 Линейное преобразование А, определенное на множестве И2 называется допустимым растяжением для некоторой решетки Г над Я2, если оно удовлетворяет следующим >словиям

1) ЛГсГ,где АТ = {у у = Ах,хеТ},

2) для всех собственных чисел X, преобразования А выполняется неравенство |Л|>1

Введенное выше понятие допустимого растяжения А приводит к понятию унитарных операторов растяхсения иА 1?{И2), и4 /(х)Н>д~и2/(А~'х), где

4 = ^ ^ и сдвига ту I?(И2) ->I?(II:2), гу /(*)/(х-у), где у е Г

Пусть ¡ег, ^еГ Положим ^ тогда /г (*) = д'/2/(А'х-^,

хвП2

Определение 14 Кратпомасиипабным анализом, ассоциированным с парой

2 1

(Г,А), называется множество замкнутых векторных подпространств из Ь (И ) с условиями

1) с^с^сК^с

/ \

2) 1ш1 У} = Замыкание ^У =Ь2(К2),

] Ыг /

3) 1ш1 У,= Г\У,={ 0},

у—>-00 уег

4) / (х) е VJ, тогда и только тогда, когда / (Ах) еС;+],те V = 17У0, у 6 I,

5) У0 инвариантно к оператору сдвига г у, те если /(х)еУ0, тогда /(х-у)еУ0, Ууе Г,

6) Существует функция феУ0, называемая масштабирующей функцией, такая, что семейство \гуф, у е г} образует базис Рисса подпространства У0

Для функции ф справедливо равенство

ф-ЩЬ^^еТ, з

где У/еГ и =1 Коэффициенты называют фильтр-

уег

коэффициентами маситгабирующей функции

На основе определения кратномасштабного анализа, определяется подпространство Щ как ортогональное дополнение V, до У1+1, Согласно

результату Мейера существуют (д-1) функций у1, у/9'1 {материнский вейвлет), таких, что их сдвиги образуют ортонормированный базис 1У0,и семейство функций

fejJ.eZ.yer, / = 1,

2 2 1

является базисом пространства 1г(К ) Для у/ справедливо равенство

7 е Г,

з

где g! = {у1 ,ф\ V) е Г Коэффициенты называются фильтр-коэффициентами еейвлет-фунщии

Определение 1 б Целое алгебраическое число а-а± называется

основанием канонической системы счисления в кольце ) целых элементов

квадратичного поля <2(л/5) , если любой целый элемент г поля однозначно представим в форме конечной суммы

2 = Т, гза1 > 23 е ° - Р'1' ,\Могт(а)\ -1}, Т4оЫ<х) = а2- <1Ь2

3=0

Определение 1 7 Пара (а,О) называется канонической системой счисления (КСС)

п кольце 8(л[с1) целых элементен ноля Множество V = {ОД, .,|М»7я(а:)|-1}

называется алфавитом КСС

Пусть задана система счисления (а,Г)), тогда произвольное комплексное число г е С представимо в виде

вд -1 2 = Х2./6^ + ^г/х1, 2;ЕО,

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

Определение 1 8 Фундаментальной областью Т(а,0) е С для КСС (а,С) в

кольце ) целых элементов поля называется множество комплексных

чисел с нулевой «целой» частью, т е

Г(а,С) = ]

Пусть отображение в С-> И2, такое, что в г = х + угь^>(х,у) Введем образ фундаментальной области Т(а,0), как Т*{а,П) = в(Т(а,0))

Во второй главе сконцентрированы основные теоретические результаты диссертационной работы Здесь приведено теоретическое обоснование возможности построения обобщенных двумерных вейвлетов-базисов Хаара Центральным результатом этой главы является доказанная теорема, о том, что характеристическая функция фундаментальной области произвольной КСС яатяетея масштабирующей функцией соответствующего КМА Доказатечьство теоремы предварено доказательством ряда лемм

Лемма 2 2 Пусть (а,П) - каноническая система счисления 8(\/с7), а = а + Ь\[с1, а е , тогда матрица

(а Ье{\

А\Ь а

ассоциированная с операцией умножения произвольного числа z е Sна основание системы счисления а, будет являться матрицей допустимого растяжения для решетки Tg^j

Лемма 23 Пусть (a,D) - каноническая система счисления в кольце S(yfd), а-а D = ]d0,d¡,d2 d\norn(ci)\-\)■ тогда множество D, состоящее из

ИогЫа) элементов, будет полной системой вычетов для множества классов эквивалентности

Лемма 2 4 Пусть задана КСС (а,П) в кольце 8(л/<7), тогда аддитивные сдвиги фундаментальной области Т(а,ТУ) этой КСС на слагаемое из кольца образуют непересекающееся покрытие комплексной плоскости С, те выполняются следующие теоретико-множественные соотношения

2) (Т{а,В)+зх)[\{Т(а,и) + з2) = <3, при л, * ,?2, е

Лемма 2 5 Пусть (а, £>) есть каноническая система счисления в кольце ,

Т{а,Ц) = |г = 2 й}а> ¿,е£>|сС

есть ее фундаментальная область, тогда множество Т*(а,Т)) измеримо и справедливо соотношение

при с1 з 23(тос14),

И

(Т'(а,0))=

^ при с! з l(шod4),

где /л - плоская (двумерная) мера Лебега.

Из доказанных лемм и результатов работы Грехенига и Мадича, следует основная теорема

Теорема 21 Пусть (се, О) - каноническая система счисления в кольце а - а + - ее основание, О = Ц,, , ¿¡г } - ее алфавит и

-1

- фундаментальная область этой КСС Пусть Г^-^ - решетка над кольцом

(а Ъс£\

тогда функция ф = хТ(а В) является масштабирующей функцией кратномасиипабного анализа ассоциированного с парой (Г

Из теоремы 2 1 следует метод построения двумерных аналогов вейвлет-базисов Хаара

Так как для любой КСС (a,D) в кольце S(\'i7) су1цествует КМА, ассоциированный с парой (Fs ^jjyA), и функция Ф = Хт{.ащ является

масштабирующей функцией этого КМА, то

1) функции вейвлет-базиса определяются равенством

У" = flu,+iA i, >

м

где и - элементы унитарной матрицы U, в которой uiJ=q~ln,j = 1 q,

9,J=1 q.d^D.q-l deM|,

2) коэффициенты фильтра для преобразования с базисом у/' определяются равенствами

hj ='V =1

г = 2 9,7=1 9

В третьей главе диссертации рассматривается применение предложенных вейвлет-базисов к задаче компрессии изображений Здесь синтезируются алгоритмы декомпозиции и реконструкции сигнала на основе введенных во второй главе вейвлет-базисов Рассмотрено два случая

1) изображение полностью покрывается фундаментальной областью КСС, для этого случая предаожены алгоритмы декомпозиции и реконструкции с полным деревом декомпозиции (FDT- Full Decomposition Tree),

2) изображение покрываегся фрагментом фундаментальной области КСС, для этого случая предложены алгоритмы декомпозиции и реконструкции с частичным деревом декомпозиции (PDT—Partial Decomposition Tiee)

Также разработаны методы компрессии и декомпрессии изображений на основе синтезированных алгоритмов

В четвертой главе диссертации представлены результаты экспериментов и сравнительный анализ предложенных алгоритмов с алгоритмом компрессии на основе разделимого вейвлет-базиса Хаара с точки зрения качества решения задачи компрессии Качество компрессии оценивалось по следующим параметрам

Коэффициент компрессии 1сс = ^, где У; - объем исходного изображения в байтах, Уа, - объем архива (компрессированного изображения) в байтах Отношение сигнал шум (Р81Ш)

PÄV7? = 101og10

2552

1 М N ,

Л™ т=0п=0

где М, N- размеры изображения, 2 (от,и) - отсчеты исходного изображения, /(от,и) -отсчеты восстановленной из архива аппроксимации исходного изображения

Далее, для удобства обозначений, алгоритмы компрессии на основе алгоритмов с полным деревом декомпозиции для КМА, ассоциированного с КСС (a,D), обозначены FDT (а), а алгоритм на основе разделимого преобразования Хаара — Haar На примере текстурных изображений была исследована эффективность предложенного подхода к адаптивному выбору вейвлет-базиса Исследовалась выборка из 130 полутоновых текстурных изображений размером 512x512 пикселей, из атласа «Brodatz» По этому множеству изображений были вычислены параметры PSNR и кс для следующих алгоритмов БГ>Т(-1+г), FDT(i\/2), FDT(-l + iv/3) и Haar, при ширине интервала квантования <5 = 10 Эксперименты показали, что исходная выборка изображений может быть разбита на 4 класса, в каждом из которых наиболее эффективен только один из рассмотренных алгоритмов Распределение исходной выборки по классам представлено в таблице 1 (таблица 4 2 в тексте диссертации)

Таблица 1 Распределение исходной выборки по классам

Класс Число изображений Процентное соотношение

К-Нааг 60 46%

KpDTi-Ы) 13 10%

1Г per {¡St 41 32 5%

ЪГ 15 11 5%

В диссертационной работе проводились исследования зависимости эффективности алгоритмов от ширины интервала квантования 3 По классам изображений > ^И5Г(г72)> кют(~\+1^1з) были Рассчитаны усредненные значения

параметров PSNR и кс дчя алгоритмов FDT(-1 + /), FDT(iV2), FDT(-1 + /-V3) и Haar, при значениях интервала квантования S = 2 20 Эксперименты показали, что все рассмотренные алгоритмы эффективны в «своих» классах при всех рассмотренных интервалах квантования Графики зависимостей представлены на рисунках 2, 3 (рисунки 4 9, 4 11 в тексте диссертации)

PSNR

Рис 2 Зависимость PSNR от кс для класса Kt

PSNR

Рис 3 Зависимость PSNR от к. для класса ,

с /гШ(-1+( \/3)

Длл bc.cn исследованных алгоритмов был рассчитан относительный коэффициент сжатия, как отношение к коэффициенту сжатия алюритма на основе разделимого вейвле1-преобразования Хаара. Зависимость относительного коэффициента сжатия от ширины интервала квантования, для исследованных алгоритмов, представлена на рисунке 4 (рисунок 4 12 в тексте диссертации)

1 15 1 1 1 05

1 .......

2 4 6 8 10 12 14 16 18 20 8

Рис 4 Зависимость относительного кс от ширины интервала квантования S

Вопрос эффективности адаптивного выбора алгоритмов на основе обобщенных вей влет-базисов Хаара. в задачах компрессии исследовался также на классе дактилоскопических изображений Задача компрессии решалась для алгоритмов FDT(-l+0, FDT(гл/2), ГОТ (—1 + 1л/з) и Haar па выборке из 40 изображений дактилограмм, размером 256x256 пикселей, при ширине интервала квантования <5 = 10 Усредненные по выборке результаты представлены в таблице 2 (таблица 4 4 в тексте диссертации)

Таблица 2 Средние значения PSNR и кс для изображений дактилограмм

FDT (-1+1) ГОТ0л/2) ГОТ(-1 + 1л/3) Haar

PSNR 36 729 36 938 31 920 33 909

К 6461 6 395 4 555 6 258

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

2 Разработан метод построения неразделимых вейвлет-базисов Хаара для кратномасштабного анализа, ассоциированного с каноническими системами счисления в кольцах целых элементов мнимых квадратичных полей

3 Для предложенных вейвлет-базисов Хаара синтезированы алгоритмы вейвлет-декомпозиции и вейвлет-реконструкции сигнала

* ...... FDT(-l + i) - ГОТ(/л/2) -- FDT(-1+,^)

% ^

4 Экспериментально показано, что применение разработанных алгоритмов компрессии на основе введенных и исследованных вейвлет-преобразований, позволяет избежать возникновения блочных и линейных линейных артефактов

5 Показано, что алгоритмы компрессии на основе разработанных вейвлет-преобразований повышают качество решения задачи компрессии за счет возможности адаптивного выбора вей влет-базиса

Основные положения диссертации отражены в публикациях

1 Белов А М "Применение канонических систем счисления в задаче построения неразделимого вейвлет-преобразования" //Тезисы второй летней школы молодых ученых по дифракциониой огпике и обработке изображений - Самара, СГАУ, 2004 - С 51-53

2 Be'ov А, "Non-separable Haar-type wavelets and canonical number systems" //Proceedings of the Second IASTED International Multi-Conference on ACIT - Signal and Inage Processing - Novosibirsk, ACTA press, 2005 -Pp 286-289

3 Белов А M "Неразделимые вейвлеты Хаара и канонические системы счисления" //Тезисы третей летней школы молодых ученых по дифракционной оптике и обработке изображений - Самара,СГАУ, 2005 -С 26-28

4 Белов А М "Применение канонических систем счисления в задаче построения неразделимых хааро-подобных вейвлетов" //Компьютерная оптика, №28, Самара -Москва, ИСОИ РАН, СГАУ, 2006 - С 119 - 123

5 Белов А М "Реализация рейвлет-декомпозиции для неразделимых вейвлетов на фундаментальных областях канонических систем счислений" //Тезисы докладов международной научно-технической конференции ПИТ-2006 - Самара, СГАУ, 2006 - Том 2 С 81 - 85

6 Белов А М "Алгоритмы декомпозиции сигнала на основе неразделимых вейвлет-преобразований Хаара" //Компьютерная оптика - Самара - Москва, ИСОИ РАН, СГАУ, 2007 - Том 31, Хг 1 С 63-66

Подписано в печать 20 04 07 Формат 60x84 1/16 Бумага офсетная, уел печ л 1,0 Тираж 100 экз Заказ

Перечень сокращений и основных обозначений.

ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.

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

1.2. Необходимые сведения из теории канонических систем счисления

1.2.1. Целые элементы в квадратичных полях.

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

1.2.3. Примеры канонических систем счисления и соответствующих им фундаментальных областей.

1.2.4. Решетки над кольцами целых алгебраических чисел.

1.3. Критерии существования двумерных аналогов базиса Хаара.

1.4. Метод построения двумерных аналогов вейвлетов Хаара.

ГЛАВА 2. ОБОБЩЕННЫЙ МЕТОД ПОСТРОЕНИЯ НЕРАЗДЕЛИМЫХ ВЕЙВЛЕТОВ НА ОСНОВАНИИ ФУНДАМЕНТАЛЬНЫХ ОБЛАСТЕЙ КАНОНИЧЕСКИХ СИСТЕМ СЧИСЛЕНИЯ.

2.1. Теоретическое обоснование обобщения метода построения двумерных аналогов базиса Хаара.

2.2. Обобщенный метод построения двумерных неразделимых вейвлетов Хаара.

Основные результаты главы 2.

ГЛАВА 3. АЛГОРИТМЫ КОМПРЕССИИ ИЗОБРАЖЕНИЙ ОСНОВАННЫЕ НА НЕРАЗДЕЛИМЫХ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯХ С НОСИТЕЛЯМИ НА ФУНДАМЕНТАЛЬНЫХ ОБЛАСТЯХ КСС.

3.1. Уравнения вейвлет-декомпозиции и вейвлет-реконструкции.

3.2. Одномерные развертки двумерных сигналов.

3.3. Описание алгоритмов декомпозиции и реконструкции сигнала на основе обобщенных вейвлет-базисов Хаара.

3.3.1. Общая идея алгоритмов декомпозиции сигнала.

3.3.2. Алгоритм декомпозиции сигнала с полным деревом.

3.3.3. Алгоритм декомпозиции сигнала с частичным деревом.

3.3.4. Алгоритм реконструкции сигнала с полным деревом декомпозиции.

3.3.5. Алгоритм реконструкции сигнала с частичным деревом декомпозиции.

3.4. Метод компрессии полутоновых цифровых изображений.

3.5. Метод декомпрессии полутоновых цифровых изображений.

3.6. Программная реализация методов компрессии и декомпрессии полутоновых изображений.

Основные результаты главы 3.

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

4.1. Компрессия синтезированных изображений.

4.1.1. Изображения «градиент».

4.1.2. Изображения «линии».

4.2. Компрессия реальных изображений.

4.2.1. Изображения из набора «Waterloo Grey Set».

4.2.2. Текстурные изображения.

4.2.3. Дактилограммы.

Основные результаты главы 4.

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

Актуальность темы. Вейвлет-преобразования широко используются в задачах обработки изображений, в частности, в задаче компрессии цифровых изображений [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].

Самой ранней работой, которую можно отнести к прототипам вейвлет-теории принято считать работу Хаара (Haar) [54]. В этой работе было показано, что можно построить кусочно-постоянную функцию

1, jce [0,1/2), у/(х) = <-1, Х€ [1/2,1), 0, х g [0,1), растяжения и сдвиги, которой, порождают ортонормированный базис в L (R). Однако, как впоследствии показано в работе Стрёмберга (Strömberg) [77], кусочно-постоянные приближения для гладких функций далеки от оптимальных. Так, например, в работе [68] было показано, что кусочно-линейное приближение дает меньшую погрешность аппроксимации, что стимулировало дальнейшие исследования. Следующим шагом развития вейвлет-теории стало построение Стрёмбергом [77] такой кусочно-линейной функции \f/, которая также порождает ортонормированный базис и дает лучшие приближения для гладких функций. Далее Мейером (Meyer) [30, 71,

72] было построено целое семейство ортонормированных вейвлет-базисов, порожденных бесконечно дифференцируемыми функциями у/. Это дало новый импульс исследованиям, что привело к открытию знаменитых вейвлетов Добеши (Daubechies) [46] с компактным носителем. Систематизированная теория построения ортонормированных вейвлет-базисов была создана Мейером и Малла (Mallat), благодаря разработке теории кратномасштабного анализа сигнала (КМА) [68, 69]. В основу этой теории легли идеи, развитые Бартом (Burt) и Адельсоном (Adelson) [44] при анализе изображений на нескольких уровнях разрешения.

В 1992 году в работе [52] Грёхениг (Grochenig) и Мадич (Madych) охарактеризовали неразделимые вейвлеты, которые представляют собой многомерные аналоги базиса Хаара. Такой вейвлет-базис был определен, как л вейвлет-базис над L (R") с компактным носителем, соответствующий кратномасштабному анализу, порожденному масштабирующей функцией вида ф{х) = Xq(x)-> гДе Zg(x) ~ характеристическая функция (индикатор) компактного множества Q czR", образующего интегральное самоподобное покрытие [53, 59, 65, 66, 67, 79] пространства R". После опубликования этой работы интерес к проблеме построения неразделимых вейвлетов существенно возрос, и множество авторов [42, 43, 62, 63, 64, 76, 78, 79] рассматривали в своих работах построение таких вейвлет-базисов на целочисленных решетках. Однако, вопрос о разработке общего подхода к определению носителей, пригодных для Построения таких базисов, оставался открытым.

В 1999 г. в работе [74] и позже в [75] Мендевиль (Mendevil) и Пише (Piché), исходя из критериев предложенных Грёхенигом и Мадичем, предложили метод построения двумерных аналогов базиса Хаара. Опираясь на тот факт, что носитель масштабирующей функции (множество Q) должен являться интегральным самоподобным покрытием плоскости, они предложили использовать в качестве носителя фундаментальные области [57,

73, 82] систем счисления с целыми гауссовыми основаниями. В дальнейшем была показана эффективность применения введенных вейвлет-базисов в задаче компрессии изображений [42, 64, 70, 76, 78].

Идея вейвлет-сжатия такова: к изображению применяется вейвлет-преобразование, затем коэффициенты преобразованного изображения квантуются, к оставшимся коэффициентам может быть применено статистическое кодирование. Сжатое изображение восстанавливается путем декодирования коэффициентов и применения обратного преобразования к результату. Предполагается, что в процессе квантования коэффициентов разложения, потери информации невелики. Таким образом, вейвлет-сжатие, как и другие методы компрессии с преобразованием, включает три основных этапа [80]:

1) разложение исходного сигнала по ортогональному базису;

2) квантование коэффициентов разложения;

3) кодирование квантованных отсчетов.

Процесс квантования, позволяет значительно сократить объем памяти требуемый для хранения изображений, но при этом и вносит основную погрешность. Искажение восстановленного сигнала можно минимизировать различными путями, в том числе и посредством адаптивного выбора наиболее подходящего для данного класса изображений вейвлет-базиса.

Компрессия (сжатие), как и большинство других задач обработки изображений, является двумерной задачей. Двумерные вейвлет-преобразования, применяемые в обработке изображений, как правило, являются разделимыми, т.е. представляют собой суперпозицию двух одномерных преобразований (например, сначала обработка по столбцам, затем по строкам) [34, 45, 69]. Вейвлет-сжатие, в силу квантования коэффициентов разложения, является сжатием с потерями, и поэтому неизбежно возникновение артефактов на восстановленном изображении. Использование разделимых вейвлетов приводит к появлению блочных и линейных артефактов на изображении [42, 74], что является нежелательным, поскольку именно к таким ошибкам зрительная система человека наиболее восприимчива (рис. В.1). а) (б)

Рис. В. 1. Артефакты восстановленных изображений для алгоритмов на основе разделимого (а) и неразделимого (б) базисов

Причиной возникновения таких артефактов является то, что разделимые вейвлеты имеют прямоугольные носители, именно на границах этих прямоугольных блоков и возникают линейные артефакты. Неразделимые же вейвлеты имеют своими носителями «фрактальные» области с непрямоугольными границами, что позволяет избежать возникновения блочных и линейных артефактов [42, 74]. Этот факт, наряду с возможностью адаптивного выбора базиса, является основной мотивацией для использования неразделимых вейвлетов на непрямоугольных носителях в задачах компрессии изображений. Однако, в прототипных работах [74, 75], задача адаптивного выбора вейвлет-базиса не исследовалась, поскольку авторы рассматривали лишь узкий класс систем счисления с целым гауссовым основанием. После разработки венгерскими математиками Катай (КгйаО и Ковачем (КоуасБ) теории канонических систем счислений (КСС) для произвольных квадратичных полей, стало возможным обобщение результатов работ Мендевиля и Пише на случай фундаментальных областей существенно более общего вида.

Теория канонических систем счислений, как самостоятельная математическая теория, возникла относительно недавно. В 1969 г. в монографии Кнута (Knuth) [60] было упомянуто, со ссылкой на работу Питти (Pitti), что любое комплексное число с целочисленными компонентами (целое гауссово число) представимо в виде конечной суммы степеней основания с коэффициентами из алфавита {0,1}: к z = a + bi = 2>у(-1 ± i)J , zj = {0,1}, a,b е Z, j=0 с некоторым k = k(z), зависящим от z. Другими словами, в кольце целых гауссовых чисел существуют «бинарные» системы счисления с основанием (-1±/).

В 1975 г. Катай и Сабо (Szabo) в работе [55] доказали существование

1 + систем счисления вида {-В ± i, {0.В }), В е Z и показано, что любое целое гауссово число представимо в виде конечной суммы: z = a + bi= Y,Zj(~B±i)J , zy е{о.Я2|, a,beZ, BeZ+, j=0 с некоторым к = k(z), зависящим от z. Произвольное комплексное число представимо в виде бесконечной суммы степеней основания с коэффициентами из алфавита: z = a + bi=^zj(-B±i)j , zje jo.52}, a,be R, Be Z+,

-00 с некоторым к = k(z), зависящим от z.

В этой же этой же работе впервые введен термин каноническая система счисления. Теме систем счисления с целым гауссовым основанием посвятил ряд работ [47, 48, 49, 50, 51] Гилберт (Gilbert), в основном они затрагивают проблемы арифметики и представления чисел в таких системах.

Позже, Катай и Ковач в работах [56, 58, 61] представили исчерпывающее описание канонических систем счисления в квадратичных полях и дали аналитический критерий их существования для произвольного квадратичного поля ).

Использование теории КСС дает возможность обобщить результаты прототипных работ [74, 75] на все канонические системы в мнимых квадратичных полях, что и послужило мотивацией для постановки указанной выше цели работы и определило задачи диссертационного исследования и структуру работы.

Задачи диссертационной работы.

1. Теоретическое обоснование возможности построения обобщенных неразделимых вейвлет-преобразований Хаара и разработка метода синтеза таких преобразований.

2. Синтез алгоритмов вейвлет-декомпозиции и вейвлет-реконструкции сигналов на основе предложенного подхода.

3. Разработка методов, алгоритмов и программных средств компрессии цифровых изображений на основе синтезированных преобразований.

4. Экспериментальные исследования предложенных алгоритмов компрессии, сравнение с алгоритмом компрессии на основе разделимого вейвлет-преобразования Хаара.

Краткое содержание диссертации. Диссертационная работа, содержащая 101 страницу (без приложений), состоит из введения, четырех глав, заключения и списка использованной литературы, составляющего 85 наименований.

Основные результаты диссертационной работы, выносимые на защиту

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

2. Алгоритмы вейвлет-декомпозиции и вейвлет-реконструкции изображения с полным и частичным деревом декомпозиции для синтезированных вейвлет-базисов.

3. Методы и программные средства компрессии полутоновых изображений на основе алгоритмов с полным и частичным деревом декомпозиции.

Заключение

В диссертации предложен и теоретически обоснован метод построения обобщенных неразделимых вейвлет-базисов Хаара, на основе фундаментальных областей канонических систем счисления в мнимых квадратичных полях. Синтезированы алгоритмы вейвлет-декомпозиции и вейвлет-реконструкции сигналов, для предложенных обобщенных вейвлет-базисов. На примере решения задачи компрессии полутоновых изображений, рассмотрено применение предложенных обобщенных вейвлет-базисов и синтезированных алгоритмов в задачах обработки изображений. Проведены экспериментальные исследования предложенных алгоритмов и их сравнение с алгоритмом на основе разделимого вейвлет-базиса Хаара.

1. Астафьева Н. М. Вейвлет-преобразования. Основные свойства и примеры применения-М.: ИКИ РАН. 1994.-№ 1891. 56 с.

2. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения. //Успехи физических наук.-1998.-Т. 166. С. 1145-1170.

3. Ахмед Н., Pao К.Р. Ортогональные преобразования при обработке цифровых сигналов.-М.: Связь, 1980, 248 с.

4. Балашов К.Ю. Сжатие информации: анализ методов и подходов-Минск, 2000, 42 с.

5. BelovA., "Non-separable Haar-type' wavelets and canonical number systems" //Proceedings of the Second IASTED International MultiConference on ACIT Signal and Image Processing. - Novosibirsk, ACTA press, 2005.-Pp. 286-289.

6. Белов A.M. "Неразделимые вейвлеты Xaapa и канонические системы счисления" //Тезисы третей летней школы молодых ученых по дифракционной оптике и обработке изображений. Самара, СГАУ, 2005.-С. 26-28.

7. Белов A.M. "Применение канонических систем счисления в задаче построения неразделимых хааро-подобных вейвлетов" //Компьютерная оптика, №28, Самара Москва, ИСОИ РАН, СГАУ, 2006. - С. 119 — 123.

8. Белов A.M. "Реализация вейвлет-декомпозиции для неразделимых вейвлетов на фундаментальных областях канонических систем счислений" //Тезисы докладов международной научно-технической конференции ПИТ-2006. Самара, СГАУ, 2006. - Том 2. С. 81 - 85.

9. Белов A.M. "Алгоритмы декомпозиции сигнала на основе неразделимых вейвлет-преобразований Хаара" //Компьютерная оптика. Самара -Москва, ИСОИ РАН, СГАУ, 2007. - Том 31, № 1. С. 63 - 66.

10. Блаттер К. Вейвлет анализ. Основы теории.-М.: Техносфера. 2004, 280 с.

11. Боревич З.И., Шафаревич И.Р. Теория чисел.-М.: Наука, 1985, 504 с.

12. ВатолинД., РатушнякА., Смирнов М., ЮкинВ. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: Диалог-МИФИ, 2002, 384 с.

13. Ван Дер Варден Б.Л. Алгебра.-М: Наука, 1976, 648 с.

14. Виттих В. А., Сергеев В. В., Сойфер В. А. Обработка изображений в автоматизированных системах научных исследований.-М.: Наука, 1982, 214 с.

15. Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования.-СПб.: ВУС, 1999. 208 с.

16. ГонсалесР., Вудс Р. Цифровая Обработка Изображений. М.: Техносфера, 2005,1072 с.

17. Добеши И. Десять лекций по вейвлетам.-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001,464 с.

18. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование. //Успехи физических наук.-2001.-Т. 171, С. 465-501.

19. Дьяконов В.А. Вейвлеты. От теории к практике.-М.: Солон. 2005, 400 с.

20. Ильин В.А., Поздняк Э.Г. Линейная Алгебра. М.: Физматлит. - 2004, 278 с.

21. Касселс Дж.В. Введение в геометрию чисел.-М.: Мир, 1965.-428 с.

22. Кашин Б.С., Саакян А.А. Ортогональные ряды.-М.: АФЦ, 1999-Глава 7. Введение в теорию всплесков. С. 244-296.

23. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа.-М: Физматлит, 2004, 570 с.

24. Кравченко В.Ф., Рвачев В.А., Пустовойт В.И. Ортонормированные системы типа wavelet на основе атомарных функций. //Доклады РАН-1996.-351, № 1, сс. 16-18.

25. Мала С. Вэйвлеты в обработке сигналов.-М.: Мир, 2005, 672 с.

26. Мановцев А. П. Основы теории радиотелеметрии.-М.: Энергия, 1973, 592 с.

27. Методы компьютерной обработки изображений. Под редакцией Сойфера В.А. М.: Физматлит, 2001, 784 с.

28. Мюррей Д., Райпер У. Энциклопеция форматов графических файлов: пер. с англ.-К.: Издательская группа BHV, 1997, 672 с.

29. Никольский Н.К. Лекции об операторе сдвига.-М.: Наука, 1980. 384 с.

30. Новиков И. Я., Онделетты И. Мейера оптимальный базис в С0,1. //Математические заметки.-1992.-52, № 6, сс. 935-938.

31. Петухов А.П. Периодические дискретные всплески. //Алгебра и анализ.-1996. 8, № 3, сс. 151-183.

32. Прэтт У. К., Сакрисон Д. Д., Мусманн X. Г. Д. и др. Методы передачи изображений. Сокращение избыточности.-М.: Радио и связь, 1983, 264 с.

33. Столниц Э., Де Роуз Т., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения.-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2002,272 с.

34. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии-М.: Триумф, 2003, 320 с.

35. Харатишвили Н.Г. Пирамидальное кодирование.-М.: Мысль, 1997. 160 с.

36. Харатишвили Н.Г., Чхеидзе И.М., Ронсен Д., Инджия Ф.И. Пирамидальное кодирование изображений.-М.: Радио и связь, 1996. 192 с.

37. Чуй К. Введение в вэйвлеты. Пер. с англ-М.: Мир, 2001. 412 с.

38. Штарк Г.Г. Применение вейвлетов для ЦОС.-М.: Техносфера, 2007, 192 с.

39. Яковлев А.Н. Основы вейвлет-преобразования сигналов.-М.: Физматлит, 2003.176 с.

40. Ярославский J1. П. Введение в цифровую обработку изображений.-М.: Советское радио, 1979,312с.

41. Andrews R., Nguyen D.T. Separable Versus Quincunx Wavelet Transforms For Image Compression, Technical Report, Department of Electrical Engeneering and Computer Science, University of Tasmania, 2002.

42. Belogay E., Wang Y., Arbitrarily smooth orthogonal nonseparable wavelets in R2, SIAM J, Math. Anal., Vol. 30, 3, pp. 678-697.

43. Burt P.J., Adelson E.H. The Laplacian pyramid as a compact image code. //IEEE Trans. Commun.-1983.-V 31, № 4. pp. 533-540.

44. Digital signal processing handbook, Madisetti V.K, Douglas B.W. (eds). Chapman & Hall/CRC net base. 1998.- p. 1690.

45. Daubechies I. Orthonormal bases of compactly supported wavelets. Pure and Appl. Math., 41,1988, pp. 909-996.

46. Gilbert W.J., Green R. J. Negative based number systems, Math. Magazine, 52,1979, pp. 240-244.

47. Gilbert W.J. Fractal Geometry Derived from Complex Bases, The Mathematical Intelligencer, Vol. 4,1982, pp. 78-86.

48. Gilbert W.J. Complex bases and fractal similarity, Ann. sei. math., Vol. 11,1, 1987, pp. 65-77.

49. Gilbert W. Complex Based Number Systems (Manuscript). Ontario, Canada: University of Waterloo, 2002.

50. Gilbert. W. Radix representations of quadratic fields. J. Math. Anal. Appl-1981.-№83.-pp 264-274.

51. Grochenig K., Madych W.R. Multiresolution Analysis, Haar Bases, and Self-Similar Tilings of Rn // IEEE Trans. Inform. Theory, 1992, 38, pp. 556 568.

52. Gröochenig K., Haas. A. Self-similar lattice tilings. J. Fourier Anal. Appl-1994-VI, №2.-pp.131 170.

53. Haar A. Zur theorie der orthogonalen fiinktionensysteme. Math. Anal., 69, 1910, pp. 331-371.

54. Katai I., Kovacs B. Canonical number systems in imaginary quadratic fields, Acta Math. Acad. Sei. Hungaricae, 1981, 37, pp. 159 164.

55. Katai I., Szabo J. Canonical number systems for complex integers, Acta Sei. Math, Szeged, 1975, 37, pp. 255-260.

56. Katai I. Number systems and fractal geometry, preprint.

57. Katai I., Kovacs B. Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen Zahlen, Acta Sei. Math. (Szeged) .- 1980 .-B.42.- p.p. 99-107.

58. Kenyon. R. elf-replicating tilings. In Symbolic Dynamics and its Applications, Contemporary Mathematics, P. Walters (ed). Amer. Math. Soc- 1992. p. 239-263.

59. Knuth D.E. The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969.

60. Kovacs, A. Generalized binary number systems. Annales Univ. Sci. Budapest, Sect. Comp., 20, 2001, pp. 195-206.

61. Lagrias J. C., Wang Y., Self affine tiles in Rn, Advances in math, 121, 1996, pp. 21-49.

62. Lagrias J. C., Wang Y., Haar-type Orthonormal Wavelet Bases in R2, J. Fourier Anal. Appl., 2, 1995, pp. 1-14.

63. Lagrias J. C., Wang Y., Haar Bases for L2(Rn) and Algebraic Number Theory, Number Theory, 57,1996, pp. 181-197.

64. Lagrias J. C., Wang Y., Integral self-affine tiles in Rn. I Standart and nonstandard digitsets. J. London Math. Soc. 1996. - №54. - pp. 161-179.

65. Lagrias J. C., Wang Y., Integral self-affine tiles in Rn. II Lattice tilings. J. Fourier Anal. Appl. -1997. №3. - pp. 83-102.

66. Lewellen G.B. Self-similarity. Rocky Mountain Journal of Mathematics-1993.-V 23, №3.-pp. 1023-1040.

67. Mallat S. Multiresolution analysis and wavelets, Trans. Amer. Math. Soc., 1989, 315, pp. 69-88.

68. Mallat. S. A Wavelet Tour of Signal Processing. Academic Press, London, second edition 1999. - p. 852.

69. Mendevil F. The application of a fast non-separable discrete periodic wavelet transform to fractal image compression. //Proc.Fractals in Engineereng-1999.-pp. 56-68.

70. Meyer Y. Principe d'incertitude, bases hilbertiennes et algebras d'operateurs, Séminaire Bourbaki, Vol. 662, Paris, 1986.

71. Meyer Y. Ondelettes, functions splines et analyses graduees, Lectures given at the University of Torino, Italy, 1986.

72. Muller W., Thuswardener J.M. Fractal properties of number systems. preprint.

73. Mendivil F., Piche D. Two Alghoritms for Non-Separable Wavelet Transforms and Applications to Image Compression, Fractals: Theory and Applications in Engineering, Springer-Verlag, 1999

74. Piche D. Complex Bases, Number Systems and Their Application to Fractal-Wavelet Image Coding //PhD in Applied Mathematics thesis. Ontario,

75. Canada: University of Waterloo, 2002.i

76. Piche D. Wavelet representation and compression of images on fractal tilings. //Proc.Fractals in Engineereng 1999. - pp. 82-96.

77. Strômberg J.O. A modified Franklin system and higher order spline systems on Rn as unconditional bases for Hardy Spaces, Proc. Conf. in honor of Antoni Zygmund, Vol. 2, New-York, Wadsworth, 1981, pp. 475-493.

78. Strichartz R.S. Wavelets and self-affine tilings. Constr. 1993. - №9. - pp. 327-346.

79. Strichartz R.S., Wang Y.Geometry self-affine tiles. Math. J. Indiana Univ-1999.-№48.-pp. 1-23.

80. Sweldens W., Schroder P. Building your own wavelets at home. In Wavelets in Computer Graphics, ACM SIGGRAPH Course Notes-1996. pp. 15-87.

81. Thuswardener J.M. Elementary property of canonical number systems In Quadratic fields, in Applications of Fibonacci numbers, Numpers G.E., Philippou A.N., Horadam A.F. (Eds). Kluwer.-1998.-V 7. pp. 405^14.

82. Thuswardener J.M. Fractal dimensions of sets induced by bases of imaginary quadratic fields. Math. Slovaca. 1998. -№48. - pp. 191-213.

83. Wallace G. K. Overview of the JPEG (ISO/CCITT) still image compression standard. Image Processing Algorithms and Techniques //Proceedings of the SPIE, 1990,1244, pp. 220-233.

84. Wallace G. K. The JPEG still picture compression standard. //Communications of the ACM, Vol. 34, 1991, 4, pp. 31- 44.

85. Walter G. G. Wavelets and Other Orthogonal Systems with Applications-CRC Press, 1994.