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

На правах рукописи УДК 621.391

Нго Хыу Фук (СРВ)

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

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата физико-математических наук

Москва 2005 г.

Работа выполнена на кафедре вычислительной математикой и программирования факультета прикладной математики и физики Московского авиационного института (государственный технический университет).

Научный руководитель: кандидат физико-математических наук, доцент

Крылов Сергей Сергеевич

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

доктор технических наук Тузов Александр Дмитриевич доктор физико-математических наук, профессор Исаев Вячеслав Константинович

Ведущая организация: Институт проблем информатики РАН

Защита диссертации состоится "......."... 2005 года в часов на за-

седании диссертационного совета Д 212.125.04 в Московском авиационном институте по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Московский авиационный институт (государственный технический университет).

С диссертацией можно ознакомиться в библиотеке Научно-исследовательского вычислительного центра МАИ.

Автореферат разослан " ¡НШ&А. 2005 г.

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

Ротанина М. В.

аооьн HWXQ

1&&67

Общая характеристика работы. Актуальность темы.

Вейвлет-преобразование (wavelet transformation) в настоящее время является одним из наиболее распространенных методов обработки сигналов. Первое упоминание о вейвлетах появилось в литературе по цифровой обработке и анализу сейсмических сигналов (работы А.Гроссмана и Ж.Морлета1). Так как интерес авторов заключался в анализе сигналов, набор базисных функций был избыточным. Далее, математик И.Мейер2 показал существование вейвлетов, образующих ортонормальный базис в L2(R). Дискретизация вейвлет-преобразования была описана в статье И.Добеши3, которая перекинула мост между математиками и специалистами в области обработки сигналов. Добеши разработала семейство вейвлет-фильтров, имеющих максимальную гладкость для данной длины фильтра.

И И.Добеши, и С.Маллат4 показали, что практическое выполнение вейвлет-преобразования осуществляется посредством двухполосного банка фильтров анализа-синтеза, известного ранее в теории субполосного кодирования. Эта теория может быть описана в терминах вейвлетов. Главное различие между этими двумя направлениями заключается в критериях построения фильтров, как это будет показано далее.

При анализе дискретных двумерных сигналов большую роль играет вычисление моменгных инвариантов, не зависящих от сдвига, масштабирования и поворота. Моменты Лежандра (работы C.W. Chong, P. Raveendran5) с ядром в виде полиномов Лежандра, принадлежащие классу ортогональных моментов, используются для выявления независимых характеристик сигнала. Основываясь на существующем методе вычисление моментов Лежандра, в работе вводится и

A Grossman and J Morlet Decomposition offunctions into wavelets of constant shape, and related transforms In L Streit, editor Mathematics and Physics Lectures on Recent Results World Scientific, Smgapose, 1985 2 Yves Meyer Ondelettes et fonctions splines Technical report, Seminaire EDP, Ecole Polytechnique, Pans, 1986 5 Ingrid Daubechies Ten Lectures on Wavelets SIAM, Philadelphia, 1992

4 Stephane Mallat Multiresolution representation andwavekts Pli D tlitii^ IJIJveiMiy Of^lqisylvania, 1988 5C W Chong, P Raveendran, "Translation and scale invat

используется новые инварианты моментов Лежандра, относительно сдвига, масштабирования и поворота.

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

Цели работы.

1. Исследовать вейвлет-преобразования в обработке дискретных сигналов.

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

3. Исследовать и предложить способы вычисления инвариантных моментов, ба-зированых на полиномах Лежандра.

Общая методика.

1. Изучение существующих видов ортогонального вейвлет-преобразования.

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

3. Исследование и предложение способа вычисления лежандровых моментных характеристик, инвариантных относительно сдвига, поворота и масштабирования.

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

В работе получены следующие основные результаты:

1. Исследованы способы вейвлет-преобразования в обработке дискретных сигналов.

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

3. Предложен способ вычисления Лежандровых моментных характеристик, инвариантных относительно сдвига, поворота и масштабирования.

Научная новизна.

Все основные научные результаты диссертации являются новыми. Практическая и теоретическая ценность.

В результате проведенных исследований, выработаны способы выполнения параллельно-рекурсивного вейвлет-преобразования двумерных дискретных сигналов и вычисления моментных инвариантов Лежандра, которые могут быть использованы на практике.

Апробация работы.

Результаты диссертации докладывались на научных конференциях, семинарах кафедры вычислительной математикой и программирования факультета прикладной математики и физики МАИ.

Публикации.

Основные результаты работы изложены в 4 работах, перечисленных в конце автореферата.

Структура и объем диссертации.

Диссертация состоит из введения, 4 глав, заключения и списка литературы, включающего 77 наименований. Текст диссертации изложен на 165 страницах.

Содержание работы.

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

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

Непрерывное вейвлет-преобразование (CTWT - Continuous-time wavelet transform) есть скалярное произведение f(x) и базисных функций

Базисные функции ц/а Ь е ¡}(К) являются вещественными и колеблются вокруг оси абсцисс. Они определены на некотором интервале. Данные функции называются вейвлетами (в вольном переводе — короткие волны) и могут рассматриваться как масштабированные и сдвинутые версии функции-прототипа у/(х).

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

(1)

так что

(2)

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

Теория кратномасштабного анализа базируется на теории функциональных пространств.

В большинстве приложений мы имеем дело с дискретными сигналами. Поэтому с точки зрения практики представляют интерес дискретные аналоги CTWT и CTWS, которые преобразуют дискретный сигнал в непрерывный и дискретный сигналы, соответственно. К сожалению, формулы для вейвлет-преобразования и рядов вейвлетов дискретного времени (DTWT - Discrete time Wavelet transform и DTWS) нельзя получить простой дискретизацией соответствующих формул для непрерывного времени. Также невозможно определить кратномас-штабный анализ для дискретных сигналов, так как не существует базисных функций, масштабированные и смещенные версии которых давали бы нам базис пространства L2(R), пространства квадратично суммируемых последовательностей бесконечной длины.

Во многих областях можно ожидать существенно лучших результатов за счет использования вейвлетов. Перечислим некоторые из них.

■ Применение вейвлет-преобразования для сжатия сигналов.

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

■ Применение вейвлет-преобразования для поверхности.

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

• Вейвлеты успешно применяются в квантовой физике, при изучении строения атома, в лазерной технике.

■ Задачи анализа нестационарных сигналов. Такого рода задачи возникают в медицине (томография, электрокардиография), гидроакустике и других областях.

■ Очистка от шума зашумленных сигналов.

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

Выводы первого раздела:

• В этом разделе представлена теория вейвлет-преобразования. В ней рассмотрены непрерывное и дискретное вейвлет-преобразования, ряды вейвлетов, быстрые алгоритмы вычислений. Также обсуждается свойство гладкости базисных вейвлет-функций. '

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

Во втором разделе представляются параллельно-рекурсивные методы выполнения вейвлет-преобразования для одномерных и двумерных сигналов. Методы выполнения вейвлет-преобразования, которые были представлены в первом разделе, являются последовательными и не позволяют реализовать преимущества распределенной обработки данных (на рис.1 и рис.2 приведены сравнения между параллельно-рекурсивными методами и линейным методам на параллельной системе 8Р2). Существует много методов на параллельном вейвлет-преобразовании, однако в большинстве из них используются вейвлеты Хаара. В 1 этой главе мы рассмотрим параллельно-рекурсивные методы выполнения вейв-лет-преобразования для одномерных и двумерных сигналов для различных видов вейвлет-преобразований, например вейвлет Хаара, Добеши-4, Добеши-6 и т.д.

Поэтому, во втором разделе предлагаются способы параллельно-рекурсивных методов выполнения вейвлет-преобразования. Алгоритм параллельно-рекурсивных вейвлетов основан на принципе «разделяй и властвуй». Абсо-

6 Alian Fournier, Wavelets and their Applications m Computer Graphics, Siggraph'95

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

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

Пусть tiu„ - время, которое требуется, чтобы начать коммуникации.

tont сотт - время, которое требуется, чтобы послать одно двойное число другому

процессору.

'от_сотр ~ время, которое требуется, чтобы вычислить одну операцию с плавающей запятой на данном компьютере.

а. Временные затраты на вычисления: Пусть в системе D процессоров, на каждом шаге каждый процессор работает на протяжении времени Т(к) ГО, где к: О... log 2 (N) - log 2 (size) +1. Время работы алгоритма составляет как:

= 7хо) m т = пюч m

compute j-y q j-y one _comp \ /

где Z^log^A^-logjCs^ + l; T(N)- время выполнения вейвлет-преобразования на одном процессоре.

б. Временные затраты на обмен данными между процессорами: время коммуникаций между процессорами системы составляет как:

tctmmumcalon = O0Og Щ ~ С * tom ^^ (4)

7

Tanaka Nobuatsu, Parallel processing of Haar-wavelet-preconditioned conjugate gradient methods, Transactions of JSCES, Paper No 2001003

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

в. Временные затраты для полного преобразования составляют как:

TjuU — ¿compute ^ (f соттимсайен ^ Hart) (5)

Пример, пусть вычислить вейвлет-преобразование на компьютере IBM SP2 с '„аг, =200f/s, to„, ci,„„=0,2fis и tcm a>mp=6ns:

Время работы стандартного метода вейвлет-преобразования на параллельной системе (Исходный сигнал -^■M}>'_o;D=2;size=4 (вейвлет Добеши-4)) -

28 х 4 х tomcomp + 24 х +3 х 11Ш„,

и время работы алгоритма параллельно-рекурсивного метода вейвлет-преобразования (Исходный сигнал -^„}^;D=2;size=4 (вейвлет Добеши-4)) -14х 4х/ „„ + 28х/ „+3х* .

one _ comp one _ сотш start

Количество процессоров

- параллельно-рекурсивный метод

---- идеальный

Рис I: Сравнение между стандартом и параллельно-рекурсивными методами (вейвлет Добеши-4).

20 40 60

Количества процессоров

параллелькнжкурсивмый метод идеальный метод Тенаки (42) линейный метод

Рис. 2: Сравнение между параллельно-рекурсивными методами (вейвлет Хаара)

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

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

соо с0.1 С0,2 со,з с<м С0.5 С0.6 С0,7 С0,8 С0.9 со,ю со.м С0,12 С0,|3 С0,14 С0,15

--.= -

С1.0 с1,1 С1.2 си С1,4 С.,5 с1.6 С1,7 1 ¿1,0 ¿и ¿1.2 ¿.,3 ¿1,4 ¿,.5 ¿1,6 ¿.,7

С2,0 С2,1 С2.2 С2,3 ¿2.0 ¿2.1 ¿2.2 ¿2.3 ¿1,0 ¿и ¿1,2 ¿и ¿,.4 ¿1,5 ¿.,6 ¿1,7

сзо С3,1 ¿3,0 ¿3, ¿2.0 ¿2! ¿2 2 ¿2,3 ¿ю ¿11 ¿1,2 ¿1.3 ¿,.4 ¿1,5 ¿1,6 ¿1.7

Рис.3: Работа стандартного метода вейвлет-преобразования на параллельной системе; Исходный сигнал (вейвлет Добеши-4)

Количество бездействующих процессоров: 3;

Количество коммуникаций: 28+0+0=28.

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

Выводы второго раздела:

• В этом разделе исследованы параллельно-рекурсивные методы выполнения вейвлет-преобразования для одномерных и двумерных сигналов.

• Также рассмотрено их применение для обработки дискретных сигналов. Алгоритм параллельно-рекурсивных методов выполнения вейвлет-

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

С0,0 С0,1 С0,2 С0,3 С0.4 Со 5 С0.6 С0.7 со.к С0.9 С0,10 С0,11 С0Д2 С0,13 С0Д5

^^ ^¿¡^

с1,о ¿1.0 си ¿и си ¿,2 си ¿и см ¿,.4 <=1.5 ¿..5 С1,6 ¿,.6 С1,7 ¿,.7

с2.а ¿ю ¿2,0 4,. С2,1 ¿,2 ¿2, ¿..з С2,2 ¿М ¿2.2 ¿,.5 С2.3 ¿.,6 ¿2.3 ¿и

сз.о ¿1,0 ^2.0 ¿и ¿з,о ¿.,2 ¿2,, ¿,з С3.1 ¿,.4 ¿2.2 ¿.,5 ¿з, ¿.,6 ¿2.3 ¿..7

С4,0 ¿1.0 ^2.0 ¿и ¿3.0 ¿,2 ¿2., ¿■.з ¿4 0 ¿..4 ¿2.2 ¿и ¿3,. ¿.,6 ¿2.3 ¿..7

Рис. 4: Работа алгоритма параллельно-рекурсивного метода вейвлет-преобразования; исходный сигнал - {с0 Д5^; ¿)=2/ З1ге=2(вейвлет Хаара);

Количество бездействующих процессоров: 0; Количество коммуникаций: 2.

Рис.5: Работа алгоритма параллельно-рекурсивного метода вейвлет-преобразования; Исходный сигнал (вейвлет Добеши-4)

Количество бездействующих процессоров: 0; Количество коммуникаций: 8+8+8=24.

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

Для системы обработки сигналов существенны:

■ инвариантность к шумовым и динамическим искажениям; • инвариантность к искажениям амплитуды сигнала;

■ инвариантность к масштабированию;

■ инвариантность к повороту плоскости сигнала;

■ инвариантность к сдвигу плоскости сигнала;

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

Основным достоинством моментных инвариантов является нечувствительность к поворотам сигнала. Кроме того, путем несложных преобразований на базе моментных инвариантов формируются признаки, устойчивые к преобразованиям подобия. В этом разделе, описаны:

■ формализация общего алгоритма синтеза функционально независимых моментных инвариантов произвольного порядка.

■ исследованы и предложены 2Б моментные характеристики, инвариантные к повороту.

Моменты Лежандра принадлежат к классу ортогональных моментов, и они используются для выделения характеристик сигнала.

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

поворота, распространяющий использование центральных моментов Лежандра для асимметричных и симметрических матриц сигнала. Решена проблема, связанная с исчезновением моментов Лежандра нечетного порядка для симметрических данных. Инвариантность относительно масштабирования достигнута путем алгебраического устранения коэффициента масштабирования, содержавшегося в формуле моментов Лежандра. Масштабные инварианты сохраняются для удлиненных и отраженных объектов. Инвариантность относительно поворотов тоже получена на основе центральных моментов Лежандра. Они также обобщены на случай произвольных дискретных сигналов. Также решена проблема, связанная с изменением размера анализируемой области двумерного сигнала. Введено новое понятие полутонового сигнала для моментов Лежандра в случае двумерного сигнала.

N-1

N-1

Рис. 6: Основание Ю моментов Лежандра - отображение от блока (О, N-1; О, N-1) к блоку единицы (0,1; 0,1)

Предполагается, что масштабы объекта по осям х и у - а и Ъ, соответственно, п Инварианты 20 моментов Лежандра для аффинных преобразований могут быть получены следующим образом: (2т + 1)(2л+1)1 '

л'-'/ =

хе (Л-{о»

(6)

Уравнение (5) формирует ядро инвариантов Ю моментов Лежандра. Инварианты обозначены как х„„- Эти моменты получены следующим образом:

Нормализованные инварианты 2Б моментов Лежандра, определены как: а>1= ; ш,п = 0,1,2 ;ап<15 = 1,2... (8)

Выводы третьего раздела:

■ исследованы требования построения моментных инвариантов.

• рассмотрены несколько тип моментов: нормальные моментные инварианты, аффинные инварианты.

• исследованы математические основы инвариантов 2Э моментов Лежандра.

■ исследованы и предложены инварианты 2Б момента Лежандра, относительно аффинных преобразований, основанные на полиномах Лежандра.

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

Цель настоящего раздела - предложить использование параллельно-рекурсивного вейвлет-преобразования, для выявления особенностей и характера сигналов.

Несколько применений параллельно-рекурсивного вейвлет-преобразования представлены в этом разделе. Перечислим некоторые из них:

■ использование параллельно-рекурсивного вейвлет-преобразования в задаче подавления шума;

■ использование параллельно-рекурсивного вейвлет-преобразования в задаче обнаружения особенностей сигналов;

В этом разделе описаны критерии качества сигналов и погрешности их дискретного представления.

Критерии качества сигналов определяются:

■ критерий визуального восприятия.

■ среднеквадратичный критерий.

• критерий максимальной ошибки.

■ погрешности дискретного представления сигналов измерили по методам:

• оценки погрешностей квантования параметра по уровню.

■ общей погрешности цифрового представления сигналов.

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

Алгоритмы моделирования параметров входного сигнала и его обработки реализованы на алгоритмическом языке высокого уровня Си++ и ОЬ|есЛРа5са1, а программа обработки результатов исследований и сбор статистики реализована в математической среде МаЛСАО 2001.

Цель настоящего раздела - демонстрация полученных в ходе диссертационного исследования результатов.

В этом разделе описаны:

■ формализация общего алгоритма синтеза функционально независимых моментных инвариантов произвольного порядка;

■ способ формирования на базе степенных моментов аффинных инвариантов - признаков сигнала, инвариантных к аффинным преобразованиям -по материалам работ.

Выводы четвертого раздела:

■ исследованы критерии качества сигналов и погрешности их дискретного представления.

■ продемонстрированы несколько модельных примеров применения параллельно-рекурсивного вейвлет-преобразования.

Заключение

В диссертационной работе получены следующие основные результаты:

1. исследованы способы вейвлет-преобразования в обработке дискретных сигналов.

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

3. предложены инварианты Ю момента Лежандра, относительно поворота преобразований, основанные на полиномах Лежандра.

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

Работы автора по теме диссертации

1. Нго Хыу Фук, "Применение вейвлет-преобразования для анализа информативности двумерных сигналов", V международная конференция по неравновесным процессам в соплах и струях (NPNJ-2004), Самара, 2004..

2. Нго Хыу Фук, "Алгоритм параллельно-рекурсивного вейвлет-преобразования", международная конференция "Ломоносов 2005", -М: Изд-во МГУ, 2005.

3. Нго Хыу Фук, "Translation, scale and rotation invariant of 2D Legendre moment: Mathematical foundation and applications", 8th International Conference on Pattern Recognition and Information Processing (PRIP'05), Минск, 2005.

4. Нго Хыу Фук, "Применение параллельно-рекурсивных методов вейвлет-преобразования для обработки двумерных сигналов", Труды МАИ.

»21980

РНБ Русский фонд

2006-4 18667

t

ВВЕДЕНИЕ.

ГЛАВА 1: ОБЗОР ИСПОЛЬЗОВАНИЯ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ В

ОБРАБОТКЕ ДИСКРЕТНЫХ СИГНАЛОВ.

Введение.

1.1. Основы теории вейвлет-преобразования.

1.1.1. Непрерывное вейвлет-преобразование.

1.2. Кратномасштабное представление функций.

1.2.1. Представление функций при помощи вейвлетов.

1.3. Вейвлет-ряды дискретного времени.

1.4. Дискретное вейвлет-преобразование.

1.4.1. Матричное описание Э\¥Т.

1.4.2. Описание DWT посредством блоков фильтров.

1.5. Гладкость базисных функций.

1.6. Обзор использования вейвлет-преобразования в обработке дискретных сигналов.

1.6.1. Применение вейвлет-преобразования для сжатия данных.

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

1.6.3. Применение вейвлет-преобразования для поверхности.

1.6.4. Другие применения вейвлет-преобразования.

1.7. Выводы.

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

СИГНАЛОВ.

Введение.

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

2.1.1. Алгоритм параллельно-рекурсивных вейвлетов.

2.1.1.1. Разбиение сигнала.

2.1.1.2. Выполнение вейвлета в каждом разделении.

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

2.1.3. Модифицирование алоритма параллельно-рекурсивных вейвлетов

2.1.4. Обратное вейвлет-преобразование.

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

2.2.1. Стандартные параллельно-рекурсивные методы выполнения вейвлет-преобразования.

2.2.2. Нестандартные параллельно-рекурсивные методы выполнения вейвлет-преобразования.

2.2.3. Анализ функций двумерного преобразования.

2.3. Выводы.

ГЛАВА 3: ПРИМЕНЕНИЕ 2В МОМЕНТОВ ЛЕЖАНДРА В ЗАДАЧАХ

ОБРАБОТКИ ДИСКРЕТНЫХ СИГНАЛОВ.

Введение.

3.1. Моментные инварианты как характеристики двумерных дискретных сигналов.

3.1.1. Моментные инварианты функции двух аргументов.

3.1.2. Метод построения моментных инвариантов произвольного порядка

3.1.3. Аффинные инварианты.

3.2. 2Т> моменты Лежандра, математическая основа и применения.

3.2.1. Математическая основа. а. Центр масс. б. Ориентация. в. Рабочий прямоугольник.

3.2.2. Инварианты 20 моментов Лежандра относительно сдвига. а. Теоретическая основа. б. Экспериментальные результаты.

3.2.3. Масштабные инварианты 20 моментов Лежандра. а. Теоретическая основа. б. Экспериментальные результаты.

3.2.4. Инварианты 20 моментов Лежандра относительно преобразования поворота. а. Теоретическая основа. б. Экспериментальные результаты.

3.3. Практическое использование Ю Моментных характеристик Лежандра при обработке двумерных дискретных сигналов.

3.3.1. Задача анализа изображений.

3.3.1.1. Формирование признаков по изображению.

3.3.1.2. Основные требования к признакам, вычисляемым по изображениям.

3.3.1.3. Нормализация изображений при вычислении признаков используется в работе (в программе). а. Яркостная нормализация. б. Нормализация масштаба объекта. в. Нормализация положения объекта. г. Нормализация ориентации объекта.

3.4. Выводы.

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНО-1 , РЕКУРСИВНОГО МЕТОДА ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ И ЕЕ г ПРИМЕНЕНИЕ ДЛЯ АНАЛИЗА СИГНАЛОВ.

Введение.

4.1. Критерии качества изображений и погрешности их дискретного представления.

4.1.1. Критерии качества изображений.

4.1.1.1. Критерий визуального восприятия.

4.1.1.2. Среднеквадратичный критерий.

4.1.1.3. Критерий максимальной ошибки (равномерного приближения)

4.1.2. Погрешности дискретного представления изображений.

4.1.2.1. Оценка погрешностей квантования параметра по уровню.

4.1.2.2. Общая погрешность цифрового представления изображений

4.2. Использование параллельно-рекурсивного вейвлет-преобразования в задаче уменьшения шума на изображениях.

4.2.1. Статистическое испытание значения.

4.2.2. Методы фильтрации.

1. Жесткий и мягкий порог.

2. Пороговая обработка k-сигмы.

3. Повторяющееся фильтрование.

4. Универсальный порог.

5. CAO пороговая обработка.

4.2.3. Удаление шума с помощью вейвлет методов.

4.2.4. Использование параллельно-рекурсивного вейвлет-преобразования в анализе изображений.

4.3. Разработка пользовательского интерфейса.

4.3.1. Общая структура программы моделирования.

4.3.2. Программирование входных изображений.

4.3.3. Программирование алгоритма параллельно-рекурсивного вейвлет-преобразования

4.3.4. Программирование удаления шума с помощью вейвлет методов

4.4. Разработка оконного графического интерфейса.

4.5. Выводы.

Вейвлет-преобразование (wavelet transformation) в настоящее время является одним из наиболее распространенных методов обработки сигналов. Первое упоминание о вейвлетах появилось в литературе по цифровой обработке и анализу сейсмических сигналов (работы А.Гроссмана и Ж.Морлета[8]). Так как интерес авторов заключался в анализе сигналов, набор базисных функций был избыточным. Далее, математик И.Мейер[49] показал существование вейвлетов, образующих ортонормальный базис в L2(R). Дискретизация вейвлет-преобразования была описана в статье И.Добеши[16], которая перекинула мост между математиками и специалистами в области обработки сигналов. Добеши разработала семейство вейвлет-фильтров, имеющих максимальную гладкость для данной длины фильтра[16,21,29].

И И.Добеши, и С.Маллат[63] показали, что практическое выполнение вейвлет-преобразования осуществляется посредством двухполосного банка фильтров анализа-синтеза, известного ранее в теории субполосного кодирования. Эта теория может быть описана в терминах вейвлетов. Главное различие между этими двумя направлениями заключается в критериях построения фильтров, как это будет показано далее.

При анализе дискретных двумерных сигналов большую роль играет вычисление моментных инвариантов, не зависящих от сдвига, масштабирования и вращения. Моменты Лежандра (работы C.W. Chong, P. Raveen-dran[12]) с ядром в виде полиномов Лежандра, принадлежащие классу ортогональных моментов, используются для выявления независимых характеристик сигнала. Основываясь на существующем методе вычисление моментов Лежандра, в работе вводятся и используются новые инварианты моментов Лежандра, относительно сдвига, масштабирования и поворота.

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

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

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

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

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

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

4.5. ВЫВОДЫ

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

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

ЗАКЛЮЧЕНИЕ

Итак, в диссертации были рассмотрены основные положения теории и практики вейвлет-преобразования. В ней также рассмотрены непрерывное и дискретное вейвлет-преобразования, ряды вейвлетов, быстрые алгоритмы вычислений.

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

В качестве практического применения параллельно-рекурсивного вейвлет-преобразования рассмотрены: использование параллельно-рекурсивного вейвлет-преобразования в задаче подавления шума; использование параллельно-рекурсивного вейвлет-преобразования в задаче обнаружения особенностей сигналов;

Для системы обработки изображений рассмотрены моменты, основанные на полиномах Лежандра и их инварианты относительно аффинного преобразования. Предложен новый метод построения моментных характеристик Лежандра, инвариантных относительно поворота.

В диссертации получены следующие основные результаты:

• предложена и программно реализована схема параллельно-рекурсивного дискретного вейвлет-преобразования для двумерных сигналов. предложены инварианты Ю момента Лежандра, относительно поворота.

• предложен и программно реализован способ применения инвариантов 20 момента Лежандра в задаче обработки двумерных сигналов.

1. A. Cohen, I. Daubechies, and J. C. Feauveau. "Biorthogonal bases of compactly supported wavelets". Communications on Pure and Applied Mathematics, 45(5):485-500, June 1992.

2. A. Fournier, " Wavelets and their Applications in Computer Graphics", 1995.

3. A. Grossman and J. Morlet. "Decomposition of functions into wavelets of constant shape, and related transforms". In L. Streit, editor. Mathematics and Physics: Lectures on Recent Results. World Scientific, Singapore, 1985.

4. A. S. Lewis, G. Knowles, " Video compression using 3D wavelet transformsr", Electronics Letters, 26(6):396-398, 15 March 1990.

5. Andrew Certain, Jovan Popovic, Tony DeRose, Tom Duchamp, David Salesin, Werner Stuetzle, "Interactive multiresolution surface viewing". In Proceeding of SIGGRAPH '96. ACM, NewYork, 1996.

6. Anil K. Jain, "Digital Image Processing", 1989 Prentice-Hall International.

7. W. Chong, P. Raveendran, "Translation and scale invariants of Legendre moments", 2003.

8. Charles K. Chui, "An Introduction to Wavelets", Academic Press, Boston, 1992.

9. H.Christian Cenker, " Wavelet Packets and Optimization in Pattern RecognitionProc. of the 21st international workshop of the AAPR, Hallstatt, Austria, May 1997, pp. 49-58.

10. Daubechies I. "Orthonormal Bases of Compactly Supported Wavelets". Communication on Pure Applied Mathematics, 1988, vol.41.P. 906-966.

11. Daubechies I. "Ten Lectures on Wavelets". SI AM, Philadelphia, 1992

12. Daubechies I. "The wavelet transform, time-frequency localization and signal analysis". IEEE Trans. Inform. Theory, 1990, №5. P.961-1005.

13. David J. Heeger, James R. Bergen, "Pyramid-based texture analysis/synthesis", In Proceeding of SIGGRAPH '95, p. 229-238, ACM, NewY-ork, 1995.

14. David Meyers, "Multiresolution tiling', Computer Graphics Forum, 13(5):325-340, December 1994.

15. David Meyers, "Reconstruction of surfaces from planar contours", Ph.D. thesis, University of Washington, 1994.

16. David Neary B.Sc., " Wavelet transform in image processing", website Dublin City University School of Electronic Engineering, website http://www.redbrick.dcu.ie/~bolsh/thesis/node53.html:

17. G. Beylkin, R. Coifinan and V. Rokhlin, "Fast wavelet transforms and numerical algorithms", Communication on Pure and Applied Mathematics, 44(2), pp. 141-183, March 1991.

18. Gerald Farin, "Curves and Surfaces for Computer Aided Geometric DesignAcademic Press, Boston, third edition, 1993.

19. Image Analysis and Understanding, Lecture Materials: Shape representation and description, websitehttp://www.icaen.uiowa.edu/~dip/LECTURE/lecture.html.

20. J. R. Packer, "Algorithms for Image Processing and Computer Vision ", 1997.

21. Jawerth B., Sweldens W. "An overview of wavelet based multiresolution analysis". SIAMRev., 1994, №3. P.377-412.

22. Josef Hoschek, Dieter Lasser, "Fundamentals of Computer Aided Geometric Design", A. K. Peters, Wellesley, MA, third edition, 1993.

23. L. A. Torres-Méndez, J. C. Ruiz-Suárez, L. E. Sucar, G. Gómez, "Translation, Rotation and Scale Invariant Object Recognition", website http://www.mor.itesm.mx/~giovani/ieee/nodel.html.

24. Mallat S. "A theory for multiresolution signal decomposition: the wavelet representation". IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, P.674-693.

25. Mallat, Zhong, "Characterization ofSighnals from Multiscale Edges", 1992.

26. Max Fomitchev, "Введение в вейвлеты и вейвлет-преобразования", 1998, website http://www.smolensk.m/user/sgma/MMORPH/N-4-html/l.htm.

27. Michael J. Andrews, " Moment Representation of Blobs in 2-D Intensity Images", website http://www.gweep.net/~rocko/Moment/paper.html.

28. Nira Dyn, David Levin, "The subdivision experience", In P.-J. Laurent, A. Le Mehaute, L. L. Schumaker, editor, "Wavelets, Images, and Surface Fitting", p. 229-244. A. K. Peters, Wellesley, MA, 1994.

29. Rioul O., Vetterli M. " Wavelets and signal processing". IEEE Signal Processing Magazine, 1991, №10. P. 14-38.

30. Roberto Hirata Junior, "Multiresolution Design of Aperture Operators", 2002 Journal of Mathematical Imaging and Vision.

31. Schumaker L., Webb G., editors.11 Recent Advances in Wavelet Analysis". Academic Press, New York, 1993.480 p.

32. Shigeru Muraki, " Volume data and wavelet transforms", IEEE Computer Graphics and Applications, 13(4):50-56, July 1993.

33. Stephane Mallat, "Multiresolution representation signal decomposition: The wavelet representation", IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(7): 674-693, July 1989.

34. Stephane Mallat, Sifen Zhong," Wavelet transform maxima and multiscale edges", In M. B. Ruskai et al., editor, Wavelets and Their Applications, p. 67-104, Jones and Bartlett, Boston, 1992.

35. Steven J. Gortler, Michael F. Cohen, "Hierarchical and variational geometric modeling with wavelets", In Proceeding of the 1995 Symposium on Interactive 3D Graphics, p. 35-42, ACM, NewYork, 1995.

36. Strang G. "Wavelets and dilation equations: A brief introduction". SIAM Rev., 1989, №4. P.614-627.

37. Tanaka Nobuatsu, "Parallel processing of Haar-wavelet-preconditioned conjugate gradient methodsTransactions of JSCES, Paper No.2001003.

38. Taswell, C. "Handbook of Wavelet Transform Algorithms", Boston, MA: Birkhâuser, 1996.

39. Teolis, A. "Computational Signal Processing with Wavelets", Boston, MA: Birkhâuser, 1997.

40. Tony D. DeRose, Michael Lounsbery, Leena Maija Reissell, "Curvers and surfacesIn Alain Fourier, editor, SIGGRAPH '95 Course Notes 26: Wavelets and Their Applications in Computer Graphics, p. 123-154, ACM, NewYork, 1995.

41. Tudor Barbu, "A pattern recognition approach to image segmentation", Proceedings of the Romanian Academy, Series A, Volume 4, number 2/2003.

42. Vetterli M., Herley C. " Wavelets and Filter Banks: Theory and Design". IEEE Transactions on Signal Processing, 1992, v.40. P. 2207-2232.

43. Winser E. Alexander, Douglas S. Reeves, Clay S. Gloster JR, "Parallel Image Processing with the Block Data Parallel Architecture", IBM J. RES. DEVELOP Vol. 44, No. 5, September 2000.

44. Yves Meyer. "Ondelettes et fonctions splines". Technical report, Séminaire EDP, Ecole Polytechnique, Paris, 1986.

45. Yves Meyer, " Wavelets: Algorithms and Applications", SIAM, Philadelphia, 1993, Translated by Robert D. Ryan.

46. Астафьева H.M. "Вейвлет-анализ: основы теории и некоторые приложенияУспехи физических наук, 1996, №11. С. 1145-1170.

47. В.А. Сойфера, "Методы компьютерной обработки изображений 2003.

48. Желудев В.А. "О вейвлетах на базе периодических сплайновДокл. 1994, №1. С. 9- 13.

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

50. Л. Левкович-Маслюк, А. Переберин, "Дв<я курса по вейвлет-анализу website AlgoList.Manual.ru,http://algolist.manual.ru/compress/image/leo lev/lecturel/wavl l.php.

51. Н. X. Фук, "Translation, scale and rotation invariant of2DLegendre moment: Mathematical foundation and applications", 8 International Conference on Pattern Recognition and Information Processing (PRIP'05), C. 1317.

52. H. X. Фук,"Алгоритм параллельно-рекурсивного вейвлет-преобразо-вания", международная конференция "Ломоносов 2005", С. 43-44.

53. Н. X. Фук, "Применение вейвлет-преобразования для анализа информативности двумерных сигналов", V международная конференция по неравновесным процессам в соплах и струях (NPNJ-2004), С. 155-156.

54. Н. X. Фук, "Применение параллельно-рекурсивных методов вейвлет-преобразования для обработки двумерных сигналов", Труды МАИ.

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

56. С. Гудман, С. Хидетниеми, "Введение в разработку и анализ алгоритмов", издательство "МИР" Москва 1981.

57. Э. Столниц, Т. ДеРоуз, Д. Салезин, "Вейвлеты в компьютерной графике: теория и приложения", Москва, Ижевск, 2002.

58. Stephane Mallat. "Mult ¡resolution representation and wavelets", Ph.D. thesis, University of Pennsylvania, 1988.

59. Е.Ковачевич, руководителя подразделения лаборатории Bell, занимающегося вейвлетами: website: http://cm.bell-labs.com/who/jelena/papers/papers.html.

60. М. Teague, "Image analysis via the general theory of moments", J. Opt, Soc, Am. 70 (8) (1980) pp. 920-930.

61. M.K. Mandal, T. Aboulnasr, S. Panchanathan, "Image indexing using moments and wavelets", IEEE Trans. Consumer Electron. 42 (3) (1996), pp. 557-565.

62. J. Haddadnia, K. Faez, P. Moallem, "Neural network based face recognition with moment invariant', Proceedings of International Conference on Image Processing, Vol. 1, 2001, pp. 1018-1021.

63. H. Qjidaa, L. Radouane, "Robust line fitting in a noisy image by the method of moments", IEEE Trans. Pattern Anal. Mach. Intell. 21 (11) (1999), pp. 1216-1223.

64. R. Mukundan, K.R. Ramakrishnan, "Moment Functions in Image Analysis", Theory and Applications, World Scientific, Singapore, 1998.

65. Анисимов Б.В., Курганов В.Д., Злобин В.К., "Распознавание и цифровая обработка изображений", (М.: высшая школа, 1983).

66. Abu-Mostafa У., Psaltis D., IEEE Trans. Pattern Anal. Mach. Intell. PAMI-7(1)46(1985).

67. Maghsoodi R., Rezaie В., "Methods of Handling and Processing Imagery", SPIE 757 58(1987).

68. Abu-Mostafa Y., Psaltis D., IEEE Trans. Pattern Anal. Mach. Intell. PAMI-6(6) 698 (1984).

69. Буреев В.А. и др. "Зарубежная радиоэлектроника", 4 52 (1980).

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

71. A. Lega, Н. Sholl, J. М. Alimi, A. Bijaoui, and P. Bury, "A parallel algorithm for structure detetion based on wavelet and segmentation analysis", Parallel Computing, 21: 265-285, April 1995.

72. Robert Lang and Andrew Spray, "The 2d wavelet transform on a massively parallel machine", In Proceedings of the Australasion Conference on Parallel and Real-Time Systems, pages 325-332, Freemantle, Western Australia, 28-29 September 1995.