Учебный курс Введение в вейвлет-анализ Леонид Левкович-Маслюк icon

Учебный курс Введение в вейвлет-анализ Леонид Левкович-Маслюк


Смотрите также:
Учебный курс Введение в вейвлет-анализ...
Учебный курс Введение в вейвлет-анализ...
Учебный курс Вейвлет-анализ и его приложения...
Учебный курс Вейвлет-анализ и его приложения...
В. К. Буторин введение в системный анализ...
Курс 1 2 курс 2 3 курс 4 4 курс 6 5 курс 8 1 курс Введение в специальность курсовая работа...
В современной акушерско-гинекологической патологии важ­ную роль играют различные инфекции...
Курс 4 4 курс 6 5 курс 8 1 курс Введение в специальность курсовая работа...
Учебный курс «введение в специальность пр» (Связи с общественностью, 1-й курс)...
Исследование систем управления Введение Учебный курс "Исследование систем управления"...
Учебный план в координатах «Зачетные единицы семестры» 1 курс 2 курс...
Вейвлет-анализ – новые возможности для неразрушающего контроля энергетических установок...



Загрузка...
скачать


9-я Международная Конференция
по Компьютерной Графике и Машинному Зрению
ГрафиКон’99
Москва, 26 августа - 1 сентября 1999 г.

Учебный курс


Введение в вейвлет-анализ

Леонид Левкович-Маслюк,

ИПМ РАН, Москва,

levkovl@spp.keldysh.ru

Антон Переберин,

ИПМ РАН, Москва,

avpereb@cs.msu.su


Лекция 2

Квадратурные зеркальные фильтры, вейвлет-пакеты, сжатие изображений.


  • Квадратурные зеркальные фильтры

  • Конструкция ортогональных вейвлетов Добеши (Daubechies)

  • Вейвлет-пакеты

  • Двумерные вейвлеты и сжатие изображений
^

Квадратурные зеркальные фильтры


Кратномасштабный анализ – это математическая конструкция, синтезирующая две идеи обработки сигналов. Первая идея – разложение сигнала по поддиапазонам (subband decomposition) при помощи квадратурных зеркальных фильтров (quadrature mirror filters) – появилась в задаче сжатия речи. Вторая идея – пирамидное представление (pyramid representation) – в задаче сжатия изображений. Обе идеи связаны с применением к сигналу фильтров специального вида. В первом случае теория строилась в терминах Фурье-преобразования сигнала, во втором – в терминах исходного сигнала.

Рассмотрим сигнал – последовательность чисел x=. Для сглаживания сигнала, подавления шума и других целей часто используют фильтры – преобразования свертки вида:

.

Сигнал y= получается «локальным усреднением» сигнала x с помощью набора «весов» :

y: ... ... ... ...










x: ... ...

В дальнейшем нам понадобятся следующие понятия.

Дискретное преобразование Фурье (ДПФ) сигнала: (формальная сумма).

z-преобразование сигнала: (формальная сумма).

Преобразование Фурье функции имеет вид .

В этих терминах применение фильтра записывается так:

, (1)

или

(1')

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

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

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

Пусть z-преобразование одной из компонент. Перед кодированием она прореживается вдвое, а перед восстановлением исходного сигнала доводится до исходной длины вставкой нулей между соседними значениями. При этом z-преобразование из превращается в . Подставим сюда (1’) для каждого из фильтров, и получим z-преобразования компонент перед восстановлением



z-преобразования транспонированных фильтров имеют вид и . Сигнал восстановится с их помощью точно, если:

.

Получаем условия точного восстановления (perfect reconstruction, PR):



В матричной форме они записываются так:

,

где



Подставив , получим условия на ДПФ искомых фильтров:

  • (2)



Допустим, что мы нашли такой, что

(2’)

Тогда, положив

(3)

мы видим, что (2) выполняется. Задача свелась к нахождению тригонометрического многочлена , удовлетворяющего (2’). На методах построения таких многочленов мы остановимся в следующем разделе. Фильтры и , удовлетворяющие (2), называются квадратурными зеркальными фильтрами (quadrature mirror filters, QMF). На рис.1, (a) и (b), показаны ДПФ такой пары фильтров и , а также исходный сигнал до и после фильтрации (без прореживания).

Рисунок 1a.



Рисунок 1b.

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

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

Конструкция ортогональных вейвлетов Добеши (Daubechies)


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



^ Рис. 2. Кусочно-линейный «вейвлет Франклина».

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

Обозначим . Должно выполняться условие:

. (4)

Ищем решение в виде: , – многочлен. Тогда . Положим , тогда

, (5)


и (2.3) превращается в

(6)

Требуется: а) найти многочлен , удовлетворяющий (6) и такой, что при , и б) извлечь из него квадратный корень в смысле (5). Ответ на а) предъявляется:

. (7)

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

Показатель в (6) определяет степени полиномов, которые «убиваются» разложением по построенному таким образом вейвлет-базису:

.

Эта величина называется количеством нулевых моментов (number of vanishing moments). В классической конструкции Добеши длина фильтров , а количество нулевых моментов . На практике это означает, что фильтр подавляет полиномиальную составляющую сигнала вида , которая остается только в крупномасштабной версии. Например, для вейвлетов Хаара , и применение фильтра убивает постоянную составляющую сигнала.

Вейвлет-пакеты


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

Р
ис. 3.


Разложение по вейвлет-пакетам.


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

Можно нарисовать произвольное бинарное дерево разложения, и ему будет соответствовать набор подпространств с базисами, построенными по аналогичному рецепту. Функции, порождающие эти базисы, и называются вейвлет-пакетами (wavelet-packets).

На практике (при сжатии данных, например) мы имеем дело только с фильтрами. За счет выбора оптимального дерева для данного сигнала или класса сигналов иногда можно существенно (в несколько раз) повысить эффективность сжатия. Для выбора [квази]оптимального дерева разработан ряд методов. Все они основаны на введении некоторой функции («энтропии»), позволяющей оценить «информативность» набора коэффициентов. Стратегия такова: сначала строится полное дерево разложения, затем снизу вверх анализируются пары узлов, имеющих общий корень. Если при переходе от корня к узлам энтропия не уменьшается, эта пара заменяется на корень. Упрощенный вариант – подобрать оптимальный уровень, т.е. высоту полного дерева, при которой энтропия минимальна.
^

Двумерные вейвлеты и сжатие изображений


Для работы с графикой необходимо обрабатывать двумерные массивы данных. Кратномасштабный анализ должен строиться в пространстве функций двух переменных. Существует несколько способов обобщить изложенные ранее конструкции на функции нескольких переменных (мы будем говорить только о функциях двух переменных).

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

.

Вместо одного вейвлета возникает три:



(L означает низкую частоту, H – высокую частоту). Пространства порождаются сдвигами скейлинг – функции на одном и том же масштабе:



пространства деталей имеют вид:



Соответствующие проекции находятся применением фильтров (в очевидных обозначениях):

,

где x – двумерный сигнал. Классическая схема Малла предполагает рекурсивное применение той же процедуры к низкочастотной составляющей. На рисунке 4 показаны результаты двух шагов этого процесса для фотографии Ингрид Добеши (Ingrid Daubechies) (внесшей выдающийся вклад в теорию вейвлет-анализа). Коэффициенты расположены по правилу:

LL

HL

LH

HH

Например, LH означает, что в этом квадранте стоит результат применения фильтра низких частот к столбцам, высоких частот – к строчкам исходной матрицы, и прореживания вдвое по каждому направлению. На рисунке 4а более ярким цветом обозначены коэффициенты большей амплитуды. Четко видно, что их положение указывает на резкие перепады яркости. Такие перепады являются наиболее информативными при беглом просмотре любого изображения. Вейвлет-представление позволяет их локализовать путем последовательного уточнения, начиная с более крупных масштабов. Кроме того, коэффициенты проекции на различные пространства деталей отвечают за перепады яркости различной ориентации: например, если фильтр высоких частот применялся к строчкам, то в соответствующем квадранте ярче выделены вертикальные перепады. Это хорошо видно на рисунке 4б.

Самый простой подход к сжатию изображений при помощи вейвлет-преобразования состоит в следующем:

  • Выполнить вейвлет-преобразование.

  • Упорядочить коэффициенты .

  • Отбросить “хвост” упорядоченного массива, энергия которого равна допустимой (по условиям задачи) величине.

  • Запомнить сохраненные коэффициенты и их положение в массиве исходных коэффициентов.

  • При восстановлении заменять отброшенные коэффициенты нулями.

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


LL HL

LH HH







^ Рисунок 4а.

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



Рисунок 4б.

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


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

  • Коэффициенты вейвлет-преобразования квантуются и записываются целыми числами.

  • Строится упорядоченная таблица коэффициентов: сначала идут те, у которых в старшем двоичном разряде 1, затем – те, у которых в старшем разряде 0, но в следующем – 1, и т.д. В битовом представлении таблица выглядит так:




s

s

s

s

s

s

s

s

s

s

1

1

0

0

0

0

0

0

0

0..




1

1

1

1

1

0

0

0..




1

1

1..

..............................................................................


В первой строке стоят знаки коэффициентов, во второй – старшие биты, и т.д. Ясно, что для воспроизведения исходного изображения достаточно запомнить (передать) только те биты, которые стоят в клетках, помеченных стрелками, а также длину стрелок и положение самих коэффициентов в исходном двумерном массиве коэффициентов. При передаче битов в таком порядке сначала передается самая существенная информация (старшие биты самых больших коэффициентов), потом менее существенная, и т.д. Этот процесс можно оборвать, дойдя до той части таблицы, где стоят «маленькие» коэффициенты. Проблема в том, как компактно передать таблицу положений сохраненных коэффициентов. Заметим, что полностью упорядочивать массив коэффициентов (по абсолютной величине) не надо, достаточно найти разбиение на группы, показанные в таблице, т.е на такие группы, что для фиксированного n

(8)

Пусть все множество коэффициентов разбито на некоторые подмножества .

Фиксируем n, и начинаем по очереди просматривать на наличие значимых коэффициентов – т.е., удовлетворяющих (8). Если в есть значимые коэффициенты, это множество разбивается на некоторые подмножества, и они опять проверяются на значимость, и т.д. Хорошо было бы построить разбиение так, чтобы значимые множества состояли (почти всегда) из единственного элемента, а незначимые были большими.

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



^ Рис. 5.

Структура деревьев, на которые распадается множество вейвлет-коэффициентов.

Верхний левый квадрант распадается на четверки коэффициентов. В каждой четверке три коэффициента (кроме закрашенного черным) имеют «потомков» – четверки коэффициентов на нижних уровнях; каждый из коэффициентов в этих четверках имеет своих отпрысков, и т.д. Узлу (i,j) соответствуют потомки с координатами (2i,2j), (2i,2j+1), (2i+1,2j), (2i+1,2j+1). В качестве изначального разбиения берется именно этот набор поддеревьев. Многие из них действительно состоят только из несущественных коэффициентов, так как малые значения на верхних уровнях почти всегда соответствуют малым значениям на нижних уровнях (если двигаться по направлению стрелок на рис. 5). Не углубляясь в дальнейшие подробности, отметим еще одну особенность этого красивого алгоритма: передается (запоминается) не таблица положений коэффициентов, а ключевые шаги процесса сортировки, что существенно компактнее (при декодировании этот процесс фактически воспроизводится в обратном порядке). Так как обычно многие поддеревья оказываются “нулевыми”, шагов сортировки будет не очень много.

Литература


  1. I. Daubechies, Ten Lectures on Wavelets. SIAM, 1992.

  2. И.Я.Новиков, С.Б.Стечкин, Основные конструкции всплесков, Фундаментальная и прикладная математика, т. 3, вып. 4, стр.999-1028, 1997.

  3. S. G. Mallat, A Wavelet Tour of Signal Processing, 1998.

  4. B.Jawerth, W.Sweldens, An overview of wavelet based multiresolution analyses, SIAM Review, v. 36, p. 377-412, 1994.

  5. А. Said, W.Pearlman, A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Trans. on Circuits and Systems for Video Technology, V.6, June 1996.

  6. “Всплеск” (подборка популярных статей о теории и приложениях вейвлет-анализа), Компьютерра, №8 (236), 2 марта 1998, стр. 28-53 (http://www.computerra.ru/1998/8/).

  7. http://www.mathsoft.com/ - электронная библиотека по теории и приложениям вейвлетов.

  8. http://www.wavelet.org/ - электронный вейвлет-дайджест (Wavelet Digest), выходит с 1992 года.

  9. http://playfair.stanford.edu/~wavelab WAVELAB, бесплатная библиотека вейвлетных программ на языке Matlab.

  10. http://www.cs.dartmouth.edu/~gdavis – Программы (на Си) Джеффри Дэвиса (Geoffrey Davis) для экспериментов с вейвлетным сжатием изображений.







Скачать 121.91 Kb.
оставить комментарий
Дата29.09.2011
Размер121.91 Kb.
ТипУчебный курс, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх