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

Диссертация на соискание ученой степени кандидата физико-математических наук. Москва - 2005

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.
ВВЕДЕНИЕ
Вейвлет-преобразование (wavelet transformation) в настоящее время является одним из наиболее распространенных методов обработки сигналов. Первое упоминание о вейвлетах появилось в литературе по цифровой обработке и анализу сейсмических сигналов (работы А.Гроссмана и Ж.Морлета[8]). Так как интерес авторов заключался в анализе сигналов, набор базисных функций был избыточным. Далее, математик И.Мейер[49] показал существование вейвлетов, образующих ортонормальный базис в
( Дискретизация вейвлет-преобразования была описана в статье И.Добеши[16],
которая перекинула мост между математиками и специалистами в области г обработки сигналов. Добеши разработала семейство вейвлет-фильтров,
имеющих максимальную гладкость для данной длины фильтра[16,21,29].
И И.Добеши, и С.Маллат[63] показали, что практическое выполнение вейвлет-преобразования осуществляется посредством двухполосного банка фильтров анализа-синтеза, известного ранее в теории субполосного кодиро-
Ч вания. Эта теория может быть описана в терминах вейвлетов. Главное разли
чие между этими двумя направлениями заключается в критериях построения фильтров, как это будет показано далее.
При анализе дискретных двумерных сигналов большую роль играет вычисление моментных инвариантов, не зависящих от сдвига, масштабирования и вращения. Моменты Лежандра (работы C.W. Chong, Р. Raveen-
dran[12]) с ядром в виде полиномов Лежандра, принадлежащие классу v
ортогональных моментов, используются для выявления независимых харак-теристик сигнала. Основываясь на существующем методе вычисление мо-
8 ментов Лежандра, в работе вводятся и используются новые инварианты мо, ментов Лежандра, относительно сдвига, масштабирования и поворота.
В настоящее время перспективным направлением повышения эффективности вейвлет-преобразований является параллельно-рекурсивные методы вычисления вейвлетов[42,57,59]. Эти методы могут быть использованы на многопроцессорных системах.
Диссертация состоит из четырех глав. Первая глава посвящена теоретическому анализу общих свойств и разновидностей вейвлет-преобразования и обзора использования вейвлет-преобразования в обработке дискретных
S сигналов. В ней рассмотрены непрерывное и дискретное вейвлет
преобразования, ряды вейвлетов, быстрые алгоритмы вычислений. Также об-суждается свойство гладкости базисных вейвлет-функций.
Во второй главе представляются параллельно-рекурсивные методы і
выполнения вейвлет-преобразования для одномерных и двумерных сигналов.
Методы выполнения вейвлет-преобразования, которые были представлены в г
первом разделе, являются последовательными и не позволяют реализовать преимущества распределенной обработки данных.
В третьей главе представляются моменты, основанные на полиномах Лежандра, и ряд теоретических и практических результатов в области стати- ц стического распознавания образов, ориентированных на особенности и ха
рактер анализируемой информации - сигналов.
В четвертой главе представлены варианты использования параллельно-рекурсивных методов выполнения вейвлет-преобразования для обработки сигналов и описана программная реализация параллельно-рекурсивного ме-тода вейвлет-преобразования и обзор возможных практических применений метода.
В заключении приведены основные результаты диссертационной работы и намечены направления дальнейшего исследования.

ВВЕДЕНИЕ 6
ГЛАВА 1: ОБЗОР ИСПОЛЬЗОВАНИЯ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ В ОБРАБОТКЕ ДИСКРЕТНЫХ СИГНАЛОВ 8
Введение 8
1.1. Основы теории вейвлет-преобразования 8
1.1.1. Непрерывное вейвлет-преобразование 9
1.2. Кратномасштабное представление функций 12
1.2.1. Представление функций при помощи вейвлетов 16
1.3. Вейвлет-ряды дискретного времени 19
1.4. Дискретное вейвлет-преобразование 21
1.4.1. Матричное описание DWT 22
1.4.2. Описание DWT посредством блоков фильтров 24
1.5. Гладкость базисных функций 26
1.6. Обзор использования вейвлет-преобразования в обработке дискретных
сигналов 29
1.6.1. Применение вейвлет-преобразования для сжатия данных 30
1.6.2. Применение вейвлет-преобразования для кратномасштабных
кривых 33
1.6.3. Применение вейвлет-преобразования для поверхности 34
1.6.4. Другие применения вейвлет-преобразования 37
1.7. Выводы 38
ГЛАВА 2: ПАРАЛЛЕЛЬНО-РЕКУРСИВНЫЕ МЕТОДЫ ВЫПОЛНЕНИЯ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ ДЛЯ ОДНОМЕРНЫХ И ДВУМЕРНЫХ СИГНАЛОВ 39
Введение 39
2.1. Параллельно-рекурсивные методы выполнения вейвлет
преобразования для одномерных сигналов 39
2.1.1. Алгоритм параллельно-рекурсивных вейвлетов 42
2.1.1.1. Разбиение сигнала 44
2.1.1.2. Выполнение вейвлета в каждом разделении 45
2.1.2. Работа алгоритма параллельно-рекурсивных вейвлетов 46
а. Временные затраты на вычисления 47
б. Временные затраты на обмен данными между процессорами 47
Л в. Временные затраты для полного преобразования 47
2.1.3. Модифицирование алоритма параллельно-рекурсивных вейвлетов
Ц 48
2.1.4. Обратное вейвлет-преобразование 53
2.2. Параллельно-рекурсивные методы выполнения вейвлетпреобразования для двумерных сигналов 55
2.2.1. Стандартные параллельно-рекурсивные методы выполнения
вейвлет-преобразования 55
2.2.2. Нестандартные параллельно-рекурсивные методы выполнения вейвлет-преобразования 57
2.2.3. Анализ функций двумерного преобразования 60
2.3. Выводы 63
ГЛАВА 3: ПРИМЕНЕНИЕ 2D МОМЕНТОВ ЛЕЖАНДРА В ЗАДАЧАХ ОБРАБОТКИ ДИСКРЕТНЫХ СИГНАЛОВ 64
Введение 64
3.1. Моментные инварианты как характеристики двумерных дискретных сигналов 64
3.1.1. Моментные инварианты функции двух аргументов 64
3.1.2. Метод построения моментных инвариантов произвольного порядка 66
3.1.3. Аффинные инварианты 68
3.2. 2D моменты Лежандра, математическая основа и применения 71
3.2.1. Математическая основа 72
а. Центр масс 74
б. Ориентация 75
в. Рабочий прямоугольник 75
3.2.2. Инварианты 2D моментов Лежандра относительно сдвига 76
а. Теоретическая основа 76
б. Экспериментальные результаты 78
3.2.3. Масштабные инварианты 2D моментов Лежандра 79
у а. Теоретическая основа 79
б. Экспериментальные результаты 81
Ц 3.2.4. Инварианты 2D моментов Лежандра относительно преобразования
поворота 81
а. Теоретическая основа 81
б. Экспериментальные результаты 82
У 3.3. Практическое использование 2D Моментных характеристик Лежандра
при обработке двумерных дискретных сигналов 84
3.3.1. Задача анализа изображений 85
3.3.1.1. Формирование признаков по изображению 87
3.3.1.2. Основные требования к признакам, вычисляемым по
изображениям 87
3.3.1.3. Нормализация изображений при вычислении признаков
используется в работе (в программе) 90
а. Яркостная нормализация 90
б. Нормализация масштаба объекта 93
в. Нормализация положения объекта 94
г. Нормализация ориентации объекта 95
, 3.4. Выводы 97
ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНОРЕКУРСИВНОГО МЕТОДА ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ И ЕЕ ПРИМЕНЕНИЕ ДЛЯ АНАЛИЗА СИГНАЛОВ 99
Введение 99
4.1. Критерии качества изображений и погрешности их дискретного представления 99
4.1.1. Критерии качества изображений 99
4.1.1.1. Критерий визуального восприятия 100
4.1.1.2. Среднеквадратичный критерий 101
4.1.1.3. Критерий максимальной ошибки (равномерного приближения) 102
4.1.2. Погрешности дискретного представления изображений 103
4.1.2.1. Оценка погрешностей квантования параметра по уровню 104
4.1.2.2. Общая погрешность цифрового представления изображений 106
4.2. Использование параллельно-рекурсивного вейвлет-преобразования в
I задаче уменьшения шума на изображениях 108
4.2.1. Статистическое испытание значения 109
4.2.2. Методы фильтрации 110
1. Жесткий и мягкий порог 110
2. Пороговая обработка к-сигмы 110
3. Повторяющееся фильтрование 110
4. Универсальный порог 111
, 5. С АО пороговая обработка 111
4.2.3. Удаление шума с помощью вейвлет методов 112
4.2.4. Использование параллельно-рекурсивного вейвлет-преобразования
в анализе изображений 112
4.3. Разработка пользовательского интерфейса 115
4.3.1. Общая структура программы моделирования 117
4.3.2. Программирование входных изображений 119
' . 4.3.3. Программирование алгоритма параллельно-рекурсивного вейвлет
преобразования 119
4.3.4. Программирование удаления шума с помощью вейвлет методов 120
4.4. Разработка оконного графического интерфейса 120
4.5. Выводы 126
ЗАКЛЮЧЕНИЕ 127
СПИСОК ЛИТЕРАТУРЫ 128
ПРИЛОЖЕНИЕ 134