Вейвлеты Добеши

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 03:56, 27 мая 2016.
Open book.svg Авторство
Чичварин Н. В.
Согласовано: 06.05.2016
Статья по учебной дисциплине
Название дисциплины:

Обнаружение и распознавание сигналов

Раздел:

2. Анализ регулярных сигналов

Глава:

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

Преподаватель:

Чичварин Н. В.

Вейвлеты Добеши — семейство ортогональных вейвлетов с компактным носителем, вычисляемым итерационным путем. Названы в честь Ингрид Добеши, математика из США, первой построившей данное семейство.

Алгоритм вейвлет – преобразования Добеши

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

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

Рис. 1. Результат вейвлет-преобразования изображения

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

Алгоритмы JPEG и MPEG, в отличие от вейвлетного, сжимают по отдельности каждый блок исходного изображения размером 8 на 8 пикселов. В результате, за счёт потери данных при сжатии, на восстановленном изображении может быть заметна блочная структура. При вейвлетном сжатии такой проблемы не возникает, но могут появляться искажения другого типа, имеющие вид «призрачной» ряби вблизи резких границ. Считается, что такие артефакты в среднем меньше бросаются в глаза наблюдателю, чем «квадратики», создаваемые JPEG.

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

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

Предположим, что имеем изображение размером (рис. 1 а). Первоначально каждая из N строк изображения делится (фильтруется) на низкочастотную (НЧ) и высокочастотную (ВЧ) половины. В результате получается два изображения размером N×N/ 2 (рис. 1 б). Далее каждый столбец делится точно также, в итоге получается четыре изображения размером (рис. 1 a): низкие частоты по горизонтали и вертикали (НЧНЧ1), высокие частоты по горизонтали и вертикали (ВЧВЧ1), низкие частоты по горизонтали и высокие частоты по вертикали (НЧВЧ1) и высокие частоты по горизонтали и низкие частоты по вертикали (ВЧНЧ1). Первое из указанных выше изображений делится аналогичным образом на следующем шаге (уровне) преобразования (рис. 1 г) и т.д.

На рис. 2 даны реальное изображение (слева) и результат первого уровня его вейвлет-анализа, т.е. четыре изображения (слева направо, сверху вниз): НЧНЧ1, ВЧНЧ1, НЧВЧ1 и ВЧВЧ1.

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

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

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

Пусть, например, фильтр имеет носитель длиной 4 (т.е. описывается четырьмя коэффициентами в дискретном случае (Добеши 4)). Представим сигнал в виде вектора длиной N, где N – количество отсчетов. Тогда процесс преобразования сигнала можно записать в матричном виде:

Здесь означают коэффициенты фильтра длиной 4, значения отсчетов сигнала, символ операция умножения матрицы на вектор. Коэффициенты в последних четырех строках матицы означают, что сигнал продолжается на всей числовую прямой периодическим образом (т.е. после значения снова идет значение ). В результате умножения матрицы размерностью на вектор длиной получается вектор такой же длины, а с учетом того, что в преобразовании участвуют два фильтра, даже два вектора длины вместо одного – казалось бы, никакого выигрыша мы не получили. Однако вейвлеты Добеши обладают следующим свойством: как сглаженное представление сигнала (т.е. обработанное масштабирующей функцией), так и его локальные особенности (полученные в результате вейвлет-преобразования) обладают избыточностью в два раза. Другими словами, для вейвлета длиной результат преобразования сигнала в каждой точке представляет собой некоторое "усреднение" сигнала и набор "деталей", отличающих исходный сигнал от усредненного – причем усредненный сигнал является в 2 раза "более гладким", чем исходный. Таким образом, каждый четный или каждый нечетный отсчет преобразования может быть исключен из рассмотрения, и в результате преобразования получаются два вектора вдвое меньшей длины, один из которых содержит сглаженную версию сигнала (или представление сигнала в половинном масштабе), а другой – набор локальных особенностей (то есть помехи на данном уровне детализации)! Что это дает? Во-первых, анализ сглаженного сигнала упрощает выявление его характерных свойств (например, нейросети гораздо лучше обучаются на сигналах, очищенных от шума, чем на зашумленных). Во-вторых, анализ локальных особенностей сигнала позволяет не только определить характер и параметры помех, но и четко локализовать "особые точки" сигнала: выбросы, пропущенные значения, резкие скачки уровня и т.д. Более того, если полученный сигнал все еще недостаточно очищен от помех, мы можем повторно применить к нему вейвлет-преобразование и получить еще более гладкую версию сигнала (уже в четыре раза короче, чем исходный) и локальные особенности сигнала уже на следующем уровне детализации.

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


Для нахождения значений коэффициентов можно использовать следующие свойства вейвлетов Добеши:

  1. Сдвиги вейвлета образуют ортонормированный базис пространства, т.е. другими словами, при попарном перемножении строк матрицы преобразования, должен получиться 0, а при умножении строки на саму себя – 1. Свойство ортогонормированности базиса означает, что матрица обратного преобразования представляет собой просто транспонированную матрицу прямого преобразования.
  2. Вейвлет длиной четное имеет нулевых начальных моментов, т.е. Поскольку начальные моменты вейвлета инвариантны относительно сдвига вдоль его области определения, можно взять произвольные последовательные значения например, . Количество нулевых моментов вейвлета означает, что если аппроксимировать исходный сигнал полиномиальными сплайнами степени , то вейвлет-преобразование "погасит" все полиномиальные составляющие степени от до (т.е. вейвлет-преобразование полинома определенной "гладкости" будет давать нулевой отклик).

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

Решением этой системы являются следующие значения:

или

Соответственно, в случае вейвлета Добеши длиной 6 (3 нулевых момента) будем иметь 6 коэффициентов и 6 уравнений для их нахождения: 3 уравнения, вытекающих из условия ортогональности, и 3 уравнения нулевых моментов. Решение такой системы может быть представлено в виде:

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

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

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

В результате первого уровня разложения изображений получают:

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

Если сигнал имел размерность , то коэффициенты первого уровня разложения будут иметь размерность .

Поиск ведется по 20 максимальным детализирующим коэффициентам (горизонтальным, вертикальным и диагональным).

Обратное преобразование

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

где - нормализующий коэффициент:

Условие конечности ограничивает класс функций, которые можно использовать в качестве вейвлетов. В частности, при , для обеспечения сходимости интеграла в нуле, значение должно быть равно нулю. Это обеспечивает условие компактности Фурье-образа вейвлета в спектральной области с локализацией вокруг некоторой частоты – средней частоте вейвлетной функции. Следовательно, функция должна иметь нулевое среднее значение по области его определения (интеграл функции по аргументу должен быть нулевым):

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

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

где индексом обозначен ортогональный "двойник" базиса.

Таким образом, непрерывное вейвлет-преобразование представляет собой разложение сигнала по всем возможным сдвигам и сжатиям/растяжениям некоторой локализованной финитной функции - вейвлета. При этом переменная ' a ' определяет масштаб вейвлета и эквивалентна частоте в преобразованиях Фурье, а переменная ' b ' – сдвиг вейвлета по сигналу от начальной точки в области его определения, шкала которого полностью повторяет временную шкалу анализируемого сигнала. Отсюда следует, что вейвлетный анализ является частотно-пространственным анализом сигналов.

См. также