4.6. Преобразование DWT

Информация, которая производится и анализируется в повседневной жизни, является дискретной. Она чаще поступает в виде чисел, а не в форме каких-то непрерывных функций. Поэтому на практике чаще применяются дискретные вейвлетные преобразования (DWT).

Конечно, непрерывные вейвлетные преобразования (CWT, см., например, [Lewalle 95] и [Rao, Bopardikar 98]) также интенсивно изучаются, поскольку это позволяет лучше понять действие DWT.

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

На практике преобразование DWT вычисляется с помощью масштабирующих множителей, которые равны отрицательным степеням двойки, и временных сдвигов, которые равны положительным степеням числа 2. На рис. 4.24 показана так называемая двухчленная решетка, которая иллюстрирует такой выбор. Используемые вейвлеты порождают ортонормальные (или биортонормальные) базисы.

Рис. 4.24. Двухчленная решетка. Связь масштаба со сдвигами по времени.

Основное направление исследования вейвлетов состоит в поисках семейств вейвлетов, которые образуют ортогональный базис. Среди этих вейвлетов предпочтение отдается вейвлотам с компактным носителем, поскольку они позволяют делать преобразования DWT с конечным импульсным откликом (FIR, finite impulse response).

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

.

Эта матрица имеет размер 2х2. С ее помощью порождаются два коэффициента преобразования: среднее и разность. (Заметим, что эти среднее и разность не равны в точности полусумме и полуразности, поскольку вместо 2 используется знаменатель . Более точными терминами были бы, соответственно, выражения «грубые детали» и «тонкие деталь»). В общем случае, DWT может использовать любое число фильтров, но все они вычисляются с помощью этого метода независимо от вида фильтров.

Сначала мы рассмотрим один из самых популярных вейвлетов, а именно вейвлет Добеши, который принято обозначать D4. Из этого обозначения видно, что он основан на четырех коэффициентах фильтра , ,  и , значения которых приведены в (4.12). Матрица  преобразования равна (ср. с матрицей  из (4.1))

.

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

Аналогично вторая строка матрицы  порождает величину , а все остальные четные строки матрицы определяют подобные свертки. Каждое число  называется детальным коэффициентом, а все вместе они образуют фильтр . Фильтр  не является сглаживающим. На самом деле, его коэффициенты подобраны так, чтобы фильтр  выдавал на выход маленькие числа, когда данные  коррелированы. Все вместе,  и  называются квадратурными зеркальными фильтрами (QMF, quadrature mirror filters).

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

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

.

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

, ,

, .                       (4.12)

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

Рис. 4.25. Одномерное прямое DWT (Matlab).

На рис. 4.25 показана программа Matlab, которая делает эти вычисления. Функция fwt1(dat,coarse,filter), аргументом dat которой является исходный вектор из  элементов, а аргументом filter служит фильтр, который вычисляет первые грубые уровни дискретного вейвлетного преобразования и записывает их в переменную coarse.

Простой тест для функции fwt1:

На рис. 4.26 приведена программа одномерного дискретного вейвлетного преобразования, которое вычисляется с помощью функции iwt1(wc,coarse,filter). Ниже приведен простой тест для ее проверки.

Рис. 4.26. Одномерное обратное DWT (Matlab).

Простой тест для функции iwt1:

Для читателей, которые потрудились разобраться с одномерными функциями fwt1 и iwt1 (рис. 4.25 и 4.26), мы приводим двумерные аналоги этих функций fwt2 и iwt2 (см. рис. 4.27 и 4.28), для которых также приведена простая тестовая программа.

Кроме семейства фильтров Добеши (между прочим, вейвлет Хаара порождает фильтр Добеши степени 2) существует множество других семейств вейвлетов, имеющие другие полезные свойства. Вот некоторые известные фильтры: фильтр Белкина, фильтр Койфмана, симметричный фильтр.

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

Рис. 4.27. Двумерное прямое DWT (Matlab).

Рис. 4.28. Двумерное обратное DWT (Matlab).

Простой тест для функций fwt2 и iwt2:

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

,

,

,

,                       (4.13)

,

.

В каждой последовательности этого семейства число коэффициентов на два больше, чем в предыдущей, причем они являются более гладкими. Происхождение этих функций обсуждается в [Daubechies 88], [DeVore и др. 92] и [Vetterli, Kovacevic 95].