Непрерывное вейвлет-преобразование
- 1 year ago
- 0
- 0
В численном и функциональном анализе дискретные вейвлет-преобразования (ДВП) относятся к вейвлет-преобразованиям, в которых вейвлеты представлены дискретными сигналами (выборками).
Первое ДВП было придумано венгерским математиком Альфредом Хааром . Для входного сигнала, представленного массивом 2 n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно для образования следующего уровня разложения. В итоге получается 2 n −1 разность и 1 общая сумма.
Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование можно выполнить за операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование — возможную альтернативу обычному быстрому преобразованию Фурье . При принятии условия случайности сигнала Х спектральную плотность его амплитуд Y вычисляют на основе алгоритма Ийетса: matrix Y =matrix(± X ), верно и обратное matrix X =matrix(± Y ).
Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.
Другие формы дискретного вейвлет-преобразования включают непрореженное вейвлет-преобразование (где не выполняется прореживания сигналов), преобразование Ньюлэнда (где ортонормированный базис вейвлетов выводится из специальным образом построенных фильтров типа «top-hat» в частотной области). Пакетные вейвлет-преобразования также связаны с ДВП. Другая форма ДВП — комплексное вейвлет-преобразование.
У дискретного вейвлет-преобразования много приложений в естественных науках, инженерном деле, математике (включая прикладную). Наиболее широко ДВП используется в кодировании сигналов, где свойства преобразования используются для уменьшения избыточности в представлении дискретных сигналов, часто — как первый этап в компрессии данных.
ДВП сигнала получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом , и получается свёртка :
Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра . В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).
Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова , отсчёты сигналов можно проредить в 2 раза:
Такое разложение вдвое уменьшило разрешение по времени в силу прореживания сигнала. Однако каждый из получившихся сигналов представляет половину частотной полосы исходного сигнала, так что частотное разрешение удвоилось.
С помощью оператора прореживания
вышеупомянутые суммы можно записать короче:
Вычисление полной свёртки с последующим прореживанием — это излишняя трата вычислительных ресурсов.
Схема лифтинга является оптимизацией, основанной на чередовании этих двух вычислений.
Это разложение можно повторить несколько раз для дальнейшего увеличения частотного разрешения с дальнейшим прореживанием коэффициентов после НЧ и ВЧ-фильтрации. Это можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. Это дерево представляет структуру .
На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания длина сигнала должна быть кратна , где — число уровней разложения.
Например, для сигнала из 32 отсчётов с частотным диапазоном от 0 до трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:
Уровень | Частоты | Длина сигнала |
---|---|---|
3 | … | 4 |
… | 4 | |
2 | … | 8 |
1 | … | 16 |
Пример быстрого одномерного вейвлет-преобразования, используя вейвлет Хаара , для массива исходных данных размером 2 N (число каскадов фильтров, соответственно, равно N) на языке C#:
public static List<Double> DirectTransform(List<Double> SourceList)
{
if (SourceList.Count == 1)
return SourceList;
List<Double> RetVal = new List<Double>();
List<Double> TmpArr = new List<Double>();
for (int j = 0; j < SourceList.Count - 1; j+=2)
{
RetVal.Add((SourceList[j] - SourceList[j + 1]) / 2.0);
TmpArr.Add((SourceList[j] + SourceList[j + 1]) / 2.0);
}
RetVal.AddRange(DirectTransform(TmpArr));
return RetVal;
}
Аналогично, пример обратного вейвлет-преобразования:
public static List<Double> InverseTransform(List<Double> SourceList)
{
if (SourceList.Count == 1)
return SourceList;
List<Double> RetVal = new List<Double>();
List<Double> TmpPart = new List<Double>();
for (int i = SourceList.Count / 2; i < SourceList.Count; i++)
TmpPart.Add(SourceList[i]);
List<Double> SecondPart = InverseTransform(TmpPart);
for (int i = 0; i < SourceList.Count / 2; i++)
{
RetVal.Add(SecondPart[i] + SourceList[i]);
RetVal.Add(SecondPart[i] - SourceList[i]);
}
return RetVal;
}
При разработке нового стандарта JPEG-2000 для сжатия изображения было выбрано вейвлет-преобразование. Само вейвлет-преобразование не сжимает данные, но позволяет таким образом преобразовать входное изображение, что без заметного ухудшения качества изображения можно сократить его избыточность.