Дискретное вейвлет-преобразование
Материал из Википедии — свободной энциклопедии
В численном анализе и функциональном анализе дискретные вейвлет-преобразования (ДВП) относятся к вейвлет-преобразованиям, в которых вейвлеты представлены дискретными сигналами (выборками).
Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно (в случае чётной длины последовательности сумм) для образования следующего уровня разложения. В итоге получается 2n - 1 разность и 1 общая сумма.
Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование (один уровень) можно выполнить за O(n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временну́ю область, т. е. моменты возникновения тех или иных частот в сигнале. Вместе, эти свойства характеризуют быстрое вейвлет-преобразование — альтернативу обычному быстрому преобразованию Фурье.
Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета, с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.
Другие формы дискретного вейвлет-преобразования включают непрореженное вейвлет-преобразование (где не выполняется прореживания сигналов), преобразование Ньюлэнда (где ортонормированный базис вейвлетов выводится из специальным образом построенных фильтров типа "top-hat" в частотной области). Пакетные вейвлет-преобразования также связаны с ДВП. Другая форма ДВП - комплексное вейвлет-преобразование.
У дискретного вейвлет-преобразования много приложений в естественных науках, инженерном деле, математике (включая прикладную). Наиболее широко ДВП используется в кодировании сигналов, где свойства преобразования используются для уменьшения избыточности в представлении дискретных сигналов, часто - как первый этап в компрессии данных.
Содержание |
[править] Определение
[править] Один уровень преобразования
ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g, и получается свёртка:
![y[n] = (x * g)[n] = \sum\limits_{k = - \infty }^\infty {x[k] g[n - k]}](http://upload.wikimedia.org/math/a/a/4/aa462c8562ac1ff461a35748842698b6.png)
Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра h. В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).
Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза:
![y_{\mathrm{low}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] g[2n - k]}](http://upload.wikimedia.org/math/7/0/0/700a893a4906241bfbaa4a31f7c5a712.png)
![y_{\mathrm{high}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] h[2n - k]}](http://upload.wikimedia.org/math/0/b/4/0b41876799c2fd135d2c8d4568f9a217.png)
Такое разложение вдвое уменьшило разрешение по времени в силу прореживания сигнала. Однако каждый из получившихся сигналов представляет половину частотной полосы исходного сигнала, так что частотное разрешение удвоилось.
(схемы на русском — тут)
С помощью оператора прореживания 
![(y \downarrow k)[n] = y[k n]](http://upload.wikimedia.org/math/7/7/f/77f3ee841b4d246f00271c89c6571f0a.png)
вышеупомянутые суммы можно записать короче:
Вычисление полной свёртки x * g с последующим прореживанием — это излишняя трата вычислительных ресурсов.
Схема лифтинга является оптимизацией, основанной на чередовании этих двух вычислений.
[править] Каскадирование и банки фильтров
Это разложение можно повторить несколько раз для дальнейшего увеличения частотного разрешения, с дальнейшим прореживанием коэффициентов после НЧ и ВЧ-фильтрации. Это можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. Это дерево представляет структуру банка (гребенки) фильтров.
На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания, длина сигнала должна быть кратна 2n, где n — число уровней разложения.
Например, для сигнала из 32 отсчётов с частотным диапазоном от 0 до fn трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:
| Уровень | Частоты | Длина сигнала |
|---|---|---|
| 3 | 0 ... fn / 8 | 4 |
| fn / 8 ... fn / 4 | 4 | |
| 2 | fn / 4 ... fn / 2 | 8 |
| 1 | fn / 2 ... fn | 16 |
[править] Пример программы
Ниже приведён пример ДВП-разложения (один уровень), показывающий простоту его вычисления.
Это вейвлет Хаара (Haar wavelet), написанный на Java:
public static int[] invoke(int[] input){
//WARNING: This will destroy the contents of the input array
//This function assumes input.length=2^n, n>1
int[] output = new int[input.length];
for(int length = input.length >> 1; ; length >>= 1){
//length=2^n, WITH DECREASING n
for(int i = 0; i < length; i++) {
int sum = input[i*2]+input[i*2+1];
int difference = input[i*2]-input[i*2+1];
output[i] = sum;
output[length+i] = difference;
}
if (length == 1)
return output;
//Swap arrays to do next iteration
System.arraycopy(output, 0, input, 0, length<<1);
}
}
Реализацию быстрого лифтинга дискретного биортогонального CDF 9/7 вейвлета на C, используемого в алгоритме сжатия изображений JPEG-2000, можно найти здесь.
[править] Литература
Stéphane Mallat, A Wavelet Tour of Signal Processing
