Дискретное вейвлет-преобразование

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

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

Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно для образования следующего уровня разложения. В итоге получается 2n−1 разность и 1 общая сумма.

Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование можно выполнить за n \log_2(n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование — возможную альтернативу обычному быстрому преобразованию Фурье. При принятии условия случайности сигнала Х спектральную плотность его амплитуд Y вычисляют на основе алгоритма Ийетса: matrixY=matrix(±X), верно и обратное matrixX=matrix(±Y).

Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies) в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. С тех пор интерес к этой области быстро возрос, что привело к созданию многочисленных потомков исходного семейства вейвлетов Добеши.

Другие формы дискретного вейвлет-преобразования включают непрореженное вейвлет-преобразование (где не выполняется прореживания сигналов), преобразование Ньюлэнда (где ортонормированный базис вейвлетов выводится из специальным образом построенных фильтров типа «top-hat» в частотной области). Пакетные вейвлет-преобразования также связаны с ДВП. Другая форма ДВП — комплексное вейвлет-преобразование.

У дискретного вейвлет-преобразования много приложений в естественных науках, инженерном деле, математике (включая прикладную). Наиболее широко ДВП используется в кодировании сигналов, где свойства преобразования используются для уменьшения избыточности в представлении дискретных сигналов, часто — как первый этап в компрессии данных.

Определение[править | править исходный текст]

Один уровень преобразования[править | править исходный текст]

ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g, и получается свёртка:

y[n] = (x * g)[n] = \sum\limits_{k =  - \infty }^\infty {x[k] g[n - k]}

Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра h. В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).

Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза:

y_{\mathrm{low}} [n] = \sum\limits_{k =  - \infty }^\infty  {x[k] g[2n - k]}
y_{\mathrm{high}} [n] = \sum\limits_{k =  - \infty }^\infty  {x[k] h[2n - k]}

Такое разложение вдвое уменьшило разрешение по времени в силу прореживания сигнала. Однако каждый из получившихся сигналов представляет половину частотной полосы исходного сигнала, так что частотное разрешение удвоилось.

Схема разложения сигнала в ДВП[1]

С помощью оператора прореживания \downarrow

(y \downarrow k)[n] = y[k n]

вышеупомянутые суммы можно записать короче:

y_{\mathrm{low}} = (x*g)\downarrow 2
y_{\mathrm{high}} = (x*h)\downarrow 2

Вычисление полной свёртки x*g с последующим прореживанием — это излишняя трата вычислительных ресурсов.

Схема лифтинга является оптимизацией, основанной на чередовании этих двух вычислений.

Каскадирование и банки фильтров[править | править исходный текст]

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

Трехуровневый банк (гребёнка) фильтров

На каждом уровне вышеприведённой диаграммы сигнал раскладывается на низкие и высокие частоты. В силу двукратного прореживания длина сигнала должна быть кратна 2^n, где n — число уровней разложения.

Например, для сигнала из 32 отсчётов с частотным диапазоном от 0 до f_n трёхуровневое разложение даст 4 выходных сигнала в разных масштабах:

Уровень Частоты Длина сигнала
3 0{{f_n}}/8 4
{{f_n}}/8{{f_n}}/4 4
2 {{f_n}}/4{{f_n}}/2 8
1 {{f_n}}/2f_n 16
Представление ДВП в частотной области

Пример программы[править | править исходный текст]

Алгоритм Малла[править | править исходный текст]

Пример быстрого одномерного вейвлет-преобразования, используя вейвлет Хаара, для массива исходных данных размером 2N (число каскадов фильтров, соответственно, равно 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; 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 для сжатия изображения было выбрано вейвлет-преобразование. Само вейвлет-преобразование не сжимает данные, но позволяет таким образом преобразовать входное изображение, что без заметного ухудшения качества изображения можно сократить его избыточность.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  • Естественная фильтрация ( случайных процессов)

Литература[править | править исходный текст]

  • Stéphane Mallat. A Wavelet Tour of Signal Processing
  • Захаров С. И., Холмская А. Г. Повышение эффективности обработки сигналов вибрации и шума при испытаниях механизмов // Вестник машиностроения : журнал. — М.: Машиностроение, 2001. — № 10. — С. 31—32. — ISSN 0042-4633.

Ссылки[править | править исходный текст]

  • Сенсор виброакустики и вибродиагностики изделий: пат №95116U1, МПК G 01 H 1/08.
  • Fast discrete biorthogonal CDF 9/7 wavelet forward and inverse transform (lifting implementation) — реализация на Си для быстрого лифтинга дискретного биортогонального CDF 9/7 вейвлета, используемого в алгоритме сжатия изображений JPEG-2000.
  • Новая тенденция в преобразовании данных от датчиков механических и физических величин. М: Машиностроение//Вестник машиностроения,2004, №4,стр.78.
  • Юэн Ч., Бичем К., Робинсон Дж. Микро-процессорные системы и их применение при обработке сигналов. М: Радио и связь.1986. 296 с.
  • Дхонсон Н., Лион Ф. Статистика и планирование экспериментов в технике и науке. Методы планирования экспериментов. М: Мир. 1981. 512 с.
  • Брох Е. Т. Применение измерительных систем фирмы "Брюль и Къер" к анализу механических колебаний и ударов. Сёборг; Ларсен и сын. 1973. 235 с.
  • Буте П.-А. Измерение ударных (шоковых) импульсов. Новый метод контроля состояния подшипников качения в процессе эксплуатации. Доклад. Фирма SKF. 1971. 7с.
  • Харкевич А. А. Спектры и анализ. М: Физматгиз.1963. 432 с.