Дискретное вейвлет-преобразование - Википедия - Discrete wavelet transform

Пример двумерного дискретного вейвлет-преобразования, который используется в JPEG2000. Исходное изображение подвергается высокочастотной фильтрации, в результате чего получаются три больших изображения, каждое из которых описывает локальные изменения яркости (деталей) исходного изображения. Затем он подвергается фильтрации нижних частот и масштабируется, давая приближенное изображение; это изображение подвергается высокочастотной фильтрации для получения трех изображений с меньшей детализацией и низкочастотной фильтрации для получения окончательного приближенного изображения в верхнем левом углу.^{[требуется разъяснение ]}

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

Примеры

Вейвлеты Хаара

Первый DWT был изобретен венгерским математиком. Альфред Хаар. Для ввода, представленного списком ${ Displaystyle 2 ^ {п}}$ числа, Вейвлет Хаара Преобразование может рассматриваться как объединение входных значений в пары, сохранение разницы и передача суммы. Этот процесс повторяется рекурсивно, объединяя суммы в пары, чтобы доказать следующую шкалу, что приводит к ${ displaystyle 2 ^ {n} -1}$ различия и окончательная сумма.

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

Наиболее часто используемый набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком. Ингрид Добешис в 1988 году. Эта формулировка основана на использовании повторяющиеся отношения генерировать постепенно более мелкие дискретные выборки неявной материнской вейвлет-функции; каждое разрешение вдвое больше предыдущего масштаба. В своей основополагающей статье Добеши выводит семейство вейвлеты, первым из которых является вейвлет Хаара. С тех пор интерес к этой области резко возрос, и было разработано множество вариаций оригинальных вейвлетов Добеши.^[1][2]

Комплексное вейвлет-преобразование двойного дерева (DℂWT)

Комплексное вейвлет-преобразование с двойным деревом (ℂWT) является относительно недавним усовершенствованием дискретного вейвлет-преобразования (DWT) с важными дополнительными свойствами: оно почти инвариантно относительно сдвига и избирательно по направлению в двух и более измерениях. Это достигается с коэффициентом избыточности только ${ displaystyle 2 ^ {d}}$, существенно ниже недецимированного DWT. Многомерное (M-D) двойное дерево ℂWT неразделимо, но основано на вычислительно эффективном банке разделяемых фильтров (FB).^[3]

Другие

Другие формы дискретного вейвлет-преобразования включают вейвлет ЛеГалла-Табатабаи (LGT) 5/3, разработанный Дидье Ле Галлом и Али Дж. Табатабаи в 1988 году (используемый в JPEG 2000 ),^[4][5][6] в Биномиальный QMF разработан Али Наси Акансу в 1990 г.,^[7] в установить разделение в иерархических деревьях (SPIHT) алгоритм, разработанный Амиром Саидом совместно с Уильямом А. Перлманом в 1996 году,^[8] в не- или недесиммированное вейвлет-преобразование (где понижающая дискретизация опущена), а Преобразование Ньюленда (где ортонормированный основа вейвлетов формируется из правильно построенных цилиндрические фильтры в частотное пространство ). Преобразования вейвлет-пакетов также связаны с дискретным вейвлет-преобразованием. Комплексное вейвлет-преобразование это другая форма.

Характеристики

DWT Хаара иллюстрирует желательные свойства вейвлетов в целом. Во-первых, это можно сделать в ${ Displaystyle О (п)}$ операции; во-вторых, он фиксирует не только представление о частотном содержании входных данных, исследуя его в различных масштабах, но также и временное содержание, то есть время, в которое эти частоты встречаются. В совокупности эти два свойства делают Быстрое вейвлет-преобразование (FWT) альтернатива обычному быстрое преобразование Фурье (БПФ).

Проблемы со временем

Благодаря операторам изменения скорости в банке фильтров, дискретный WT не инвариантен во времени, но на самом деле очень чувствителен к выравниванию сигнала во времени. Для решения нестационарной проблемы вейвлет-преобразований Маллат и Чжун предложили новый алгоритм для вейвлет-представления сигнала, который инвариантен к временным сдвигам.^[9] В соответствии с этим алгоритмом, который называется TI-DWT, только параметр масштаба выбирается вдоль диадической последовательности 2 ^ j (j∈Z), и вейвлет-преобразование вычисляется для каждого момента времени.^[10][11]

Приложения

Дискретное вейвлет-преобразование имеет огромное количество приложений в науке, технике, математике и информатике. В частности, он используется для кодирование сигнала, чтобы представить дискретный сигнал в более избыточной форме, часто как предварительное условие для Сжатие данных. Практическое применение также можно найти в обработке сигналов ускорения для анализа походки,^[12] обработка изображений,^[13] в цифровых коммуникациях и многое другое.^[14][15][16]

Показано, что дискретное вейвлет-преобразование (дискретное по масштабу и сдвигу и непрерывное во времени) успешно реализовано в качестве банка аналоговых фильтров при обработке биомедицинских сигналов для разработки маломощных кардиостимуляторов, а также в сверхширокополосной (СШП) беспроводной связи.^[17]

Пример обработки изображений

Изображение с гауссовым шумом.

Изображение с удаленным гауссовым шумом.

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

Первый шаг - выбрать тип вейвлета и уровень разложения N. В этом случае биортогональный Было выбрано 3,5 вейвлета с уровнем N, равным 10. Биортогональные вейвлеты обычно используются при обработке изображений для обнаружения и фильтрации белого гауссовского шума.^[18] из-за их высокого контраста значений интенсивности соседних пикселей. Используя эти вейвлеты вейвлет-преобразование выполняется на двухмерном изображении.

Следующим шагом после декомпозиции файла изображения является определение пороговых значений для каждого уровня от 1 до стратегии Н. Бирже-Массарта.^[19] - довольно распространенный метод выбора этих пороговых значений. С помощью этого процесса устанавливаются индивидуальные пороги для N = 10 уровней. Применение этих пороговых значений составляет большую часть фактической фильтрации сигнала.

Последний шаг - восстановить изображение по измененным уровням. Это достигается с помощью обратного вейвлет-преобразования. Полученное изображение без белого гауссовского шума показано под исходным изображением. При фильтрации любой формы данных важно количественно оценить соотношение сигнал шум результата.^{[нужна цитата ]} В этом случае SNR шумного изображения по сравнению с оригиналом составлял 30,4958%, а SNR шумоподавленного изображения - 32,5525%. В результате улучшение вейвлет-фильтрации дает прирост отношения сигнал / шум 2,0567%.^[20]

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

Сравнение с преобразованием Фурье

Чтобы проиллюстрировать различия и сходства между дискретным вейвлет-преобразованием с дискретное преобразование Фурье, рассмотрим DWT и DFT следующей последовательности: (1,0,0,0), a единичный импульс.

ДПФ имеет ортогональный базис (Матрица ДПФ ):

${ displaystyle { begin {bmatrix} 1 & 1 & 1 & 1 1 & -i & -1 & i 1 & -1 & 1 & -1 1 & i & -1 & -i end {bmatrix}}}$

в то время как DWT с вейвлетами Хаара для данных длиной 4 имеет ортогональный базис в строках:

${ displaystyle { begin {bmatrix} 1 & 1 & 1 & 1 1 & 1 & -1 & -1 1 & -1 & 0 & 0 0 & 0 & 1 & -1 end {bmatrix}}}$

(Для упрощения записи используются целые числа, поэтому основания ортогональный но нет ортонормированный.)

Предварительные наблюдения включают:

• Синусоидальные волны различаются только своей частотой. Первый не завершает никаких циклов, второй завершает один полный цикл, третий завершает два цикла, а четвертый завершает три цикла (что эквивалентно завершению одного цикла в противоположном направлении). Различия в фазах можно представить, умножив заданный базисный вектор на комплексную константу.
• Вейвлеты, напротив, имеют и частоту, и местоположение. Как и раньше, первый завершает нулевые циклы, а второй - один цикл. Однако у третьего и четвертого одинаковая частота, в два раза больше, чем у первого. Они отличаются не по частоте, а по место расположения - третий ненулевой по первым двум элементам, а четвертый ненулевой по вторым двум элементам.

Разложение последовательности по этим основаниям дает:

${ displaystyle { begin {align} (1,0,0,0) & = { frac {1} {4}} (1,1,1,1) + { frac {1} {4}} (1,1, -1, -1) + { frac {1} {2}} (1, -1,0,0) qquad { text {Haar DWT}} (1,0,0 , 0) & = { frac {1} {4}} (1,1,1,1) + { frac {1} {4}} (1, i, -1, -i) + { frac {1} {4}} (1, -1,1, -1) + { frac {1} {4}} (1, -i, -1, i) qquad { text {DFT}} конец {выровнен}}}$

DWT демонстрирует локализацию: член (1,1,1,1) дает среднее значение сигнала, (1,1, –1, –1) помещает сигнал в левую часть домена, а (1 , –1,0,0) помещает его в левую часть левой части, а усечение на любом этапе дает субдискретизированную версию сигнала:

${ displaystyle { begin {align} & left ({ frac {1} {4}}, { frac {1} {4}}, { frac {1} {4}}, { frac { 1} {4}} right) & left ({ frac {1} {2}}, { frac {1} {2}}, 0,0 right) qquad { text {2 усечение -term}} & left (1,0,0,0 right) end {align}}}$

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

ДПФ, напротив, выражает последовательность интерференцией волн разных частот - таким образом, усечение ряда дает фильтр нижних частот версия серии:

${ displaystyle { begin {align} & left ({ frac {1} {4}}, { frac {1} {4}}, { frac {1} {4}}, { frac { 1} {4}} right) & left ({ frac {3} {4}}, { frac {1} {4}}, - { frac {1} {4}}, { frac {1} {4}} right) qquad { text {2-членное усечение}} & left (1,0,0,0 right) end {выровнено}}}$

Примечательно, что среднее приближение (2-членное) отличается. С точки зрения частотной области это лучшее приближение, но с точки зрения временной области у него есть недостатки - он демонстрирует недолет - одно из значений отрицательное, хотя исходный ряд везде неотрицательный - и звон, где правая часть не равна нулю, в отличие от вейвлет-преобразования. С другой стороны, приближение Фурье правильно показывает пик, и все точки находятся в пределах ${ displaystyle 1/4}$ их правильного значения, хотя все точки имеют ошибку. Вейвлет-приближение, напротив, помещает пик в левой половине, но не имеет пика в первой точке, и, хотя это точно верно для половины значений (отражающих местоположение), оно имеет ошибку ${ displaystyle 1/2}$ для других значений.

Это иллюстрирует виды компромиссов между этими преобразованиями и то, как в некоторых отношениях DWT обеспечивает предпочтительное поведение, особенно для моделирования переходных процессов.

Определение

Один уровень трансформации

DWT сигнала ${ displaystyle x}$ рассчитывается путем пропускания через серию фильтров. Сначала образцы проходят через фильтр нижних частот с импульсивный ответ ${ displaystyle g}$ в результате свертка из двух:

${ Displaystyle у [п] = (х * г) [п] = сумма пределы _ {к = - infty} ^ { infty} {х [к] г [п-к]}}$

Сигнал также разлагается одновременно с использованием фильтр высоких частот ${ displaystyle h}$. Выходы дают детальные коэффициенты (из фильтра высоких частот) и коэффициенты аппроксимации (из фильтра низких частот). Важно, чтобы эти два фильтра были связаны друг с другом и назывались квадратурный зеркальный фильтр.

Блок-схема анализа фильтров

Однако, поскольку половина частот сигнала теперь удалена, половина отсчетов может быть отброшена в соответствии с правилом Найквиста. Выходной сигнал фильтра нижних частот ${ displaystyle g}$ на диаграмме выше тогда подвыборка на 2 и далее обрабатывается, пропуская его снова через новый фильтр нижних частот ${ displaystyle g}$ и фильтр высоких частот ${ displaystyle h}$ с половиной частоты среза предыдущего, то есть:

${ displaystyle y _ { mathrm {low}} [n] = sum limits _ {k = - infty} ^ { infty} {x [k] g [2n-k]}}$

${ displaystyle y _ { mathrm {high}} [n] = sum limits _ {k = - infty} ^ { infty} {x [k] h [2n-k]}}$

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

С оператор подвыборки ${ displaystyle downarrow}$

${ displaystyle (y downarrow k) [n] = y [kn]}$

приведенное выше суммирование можно записать более кратко.

${ displaystyle y _ { mathrm {low}} = (x * g) downarrow 2}$

${ displaystyle y _ { mathrm {high}} = (x * h) downarrow 2}$

Однако вычисление полной свертки ${ displaystyle x * g}$ с последующим понижением дискретизации приведет к потере времени вычислений.

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

Каскадные и фильтровальные банки

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

3-х уровневый блок фильтров

На каждом уровне на приведенной выше диаграмме сигнал разбивается на низкие и высокие частоты. Из-за процесса разложения входной сигнал должен быть кратным ${ Displaystyle 2 ^ {п}}$ куда ${ displaystyle n}$ количество уровней.

Например, сигнал с 32 отсчетами, диапазон частот от 0 до ${ displaystyle f_ {n}}$ и 3 уровня декомпозиции, производятся 4 шкалы вывода:

Уровень	Частоты	Образцы
3	${ displaystyle 0}$ к ${ displaystyle {f_ {n}} / 8}$	4
	${ displaystyle {f_ {n}} / 8}$ к ${ displaystyle {f_ {n}} / 4}$	4
2	${ displaystyle {f_ {n}} / 4}$ к ${ displaystyle {f_ {n}} / 2}$	8
1	${ displaystyle {f_ {n}} / 2}$ к ${ displaystyle f_ {n}}$	16

Представление DWT в частотной области

Отношение к материнскому вейвлету

Реализацию набора фильтров вейвлетов можно интерпретировать как вычисление вейвлет-коэффициентов дискретный набор дочерних вейвлетов для данного материнского вейвлета ${ Displaystyle psi (т)}$. В случае дискретного вейвлет-преобразования материнский вейвлет сдвигается и масштабируется по степени двойки.

${ displaystyle psi _ {j, k} (t) = { frac {1} { sqrt {2 ^ {j}}}} psi left ({ frac {t-k2 ^ {j}}) {2 ^ {j}}} right)}$

куда ${ displaystyle j}$ параметр масштаба и ${ displaystyle k}$ - параметр сдвига, оба целые числа.

Напомним, что вейвлет-коэффициент ${ displaystyle gamma}$ сигнала ${ Displaystyle х (т)}$ это проекция ${ Displaystyle х (т)}$ на вейвлет, и пусть ${ Displaystyle х (т)}$ быть сигналом длины ${ displaystyle 2 ^ {N}}$. В случае дочернего вейвлета в дискретной семье выше,

${ displaystyle gamma _ {jk} = int _ {- infty} ^ { infty} x (t) { frac {1} { sqrt {2 ^ {j}}}} psi left ( { frac {t-k2 ^ {j}} {2 ^ {j}}} right) dt}$

Теперь исправим ${ displaystyle j}$ в определенном масштабе, так что ${ displaystyle gamma _ {jk}}$ является функцией ${ displaystyle k}$ Только. В свете приведенного выше уравнения ${ displaystyle gamma _ {jk}}$ можно рассматривать как свертка из ${ Displaystyle х (т)}$ с расширенной, отраженной и нормализованной версией материнского вейвлета, ${ displaystyle h (t) = { frac {1} { sqrt {2 ^ {j}}}} psi left ({ frac {-t} {2 ^ {j}}} right)}$, отобранные в точках ${ displaystyle 1,2 ^ {j}, 2 ^ {2j}, ..., 2 ^ {N}}$. Но именно это дают коэффициенты детализации на уровне ${ displaystyle j}$ дискретного вейвлет-преобразования. Поэтому при соответствующем выборе ${ Displaystyle ч [п]}$ и ${ Displaystyle г [п]}$, детальные коэффициенты банка фильтров точно соответствуют вейвлет-коэффициенту дискретного набора дочерних вейвлетов для данного материнского вейвлета ${ Displaystyle psi (т)}$.

В качестве примера рассмотрим дискретный Вейвлет Хаара, чей материнский вейвлет ${ displaystyle psi = [1, -1]}$. Тогда расширенная, отраженная и нормализованная версия этого вейвлета имеет вид ${ displaystyle h [n] = { frac {1} { sqrt {2}}} [- 1,1]}$, который действительно является фильтром разложения верхних частот для дискретного вейвлет-преобразования Хаара.

Сложность времени

Реализация набора фильтров дискретного вейвлет-преобразования занимает только O (N) в некоторых случаях по сравнению с O (N бревноN) для быстрое преобразование Фурье.

Обратите внимание, что если ${ Displaystyle г [п]}$ и ${ Displaystyle ч [п]}$ оба имеют постоянную длину (т.е. их длина не зависит от N), то ${ displaystyle x * h}$ и ${ displaystyle x * g}$ каждый дубль O (N) время. Банк вейвлет-фильтров выполняет каждое из этих двух O (N) свертки, затем разбивает сигнал на две ветви размером N / 2. Но он только рекурсивно разбивает верхнюю ветвь, свернутую с ${ Displaystyle г [п]}$ (в отличие от БПФ, которое рекурсивно разделяет как верхнюю, так и нижнюю ветви). Это приводит к следующему отношение повторения

${ Displaystyle Т (N) = 2N + Т влево ({ гидроразрыва {N} {2}} вправо)}$

что приводит к O (N) время на всю операцию, как может быть показано геометрическая серия расширение указанного выше отношения.

Например, дискретный Вейвлет Хаара преобразование линейно, так как в этом случае ${ Displaystyle ч [п]}$ и ${ Displaystyle г [п]}$ имеют постоянную длину 2.

${ displaystyle h [n] = left [{ frac {- { sqrt {2}}} {2}}, { frac { sqrt {2}} {2}} right] g [n] = left [{ frac { sqrt {2}} {2}}, { frac { sqrt {2}} {2}} right]}$

Локальность всплесков вместе с O (N) сложности, гарантирует, что преобразование может быть вычислено онлайн (на потоковой основе). Это свойство резко контрастирует с БПФ, которое требует доступа ко всему сигналу сразу. Это также применимо к многомасштабному преобразованию, а также к многомерному преобразованию (например, 2-D DWT).^[21]

Другие трансформации

В Алгоритм Adam7, используется для переплетение в Переносимая сетевая графика (PNG) - это многомасштабная модель данных, аналогичная DWT с Вейвлеты Хаара.

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

Пример кода

В своей простейшей форме DWT удивительно легко вычислить.

В Вейвлет Хаара в Ява:

общественный статический int[] дискретныйHaarWaveletTransform(int[] Вход) {    // Эта функция предполагает, что input.length = 2 ^ n, n> 1    int[] выход = новый int[Вход.длина];    за (int длина = Вход.длина / 2; ; длина = длина / 2) {        // длина - текущая длина рабочей области выходного массива.        // длина начинается с половины размера массива, и каждая итерация уменьшается вдвое, пока не станет равной 1.        за (int я = 0; я < длина; ++я) {            int сумма = Вход[я * 2] + Вход[я * 2 + 1];            int разница = Вход[я * 2] - Вход[я * 2 + 1];            выход[я] = сумма;            выход[длина + я] = разница;        }        если (длина == 1) {            возвращаться выход;        }        // Поменять местами массивы для следующей итерации        Система.arraycopy(выход, 0, Вход, 0, длина);    }}

Полный код Java для 1-D и 2-D DWT с использованием Хаар, Добеши, Coiflet, и Legendre вейвлеты доступны из проекта с открытым исходным кодом: JWave.Кроме того, реализация быстрого лифтинга дискретных биортогональных CDF 9/7 вейвлет-преобразование в C, используемый в JPEG 2000 стандарт сжатия изображений можно найти здесь (архивировано 5 марта 2012 г.).

Пример приведенного выше кода

Пример вычисления дискретных вейвлет-коэффициентов Хаара для звукового сигнала человека, говорящего «Я люблю вейвлеты». Исходная форма волны показана синим в верхнем левом углу, а вейвлет-коэффициенты показаны черным в правом верхнем углу. Внизу показаны три увеличенные области вейвлет-коэффициентов для разных диапазонов.

На этом рисунке показан пример применения вышеуказанного кода для вычисления вейвлет-коэффициентов Хаара для звуковой волны. В этом примере выделяются два ключевых свойства вейвлет-преобразования:

• Естественные сигналы часто имеют некоторую степень плавности, что делает их редкими в области вейвлета. В этом примере значимых компонентов в вейвлет-области гораздо меньше, чем во временной области, и большинство значимых компонентов относятся к более грубым коэффициентам слева. Следовательно, естественные сигналы сжимаются в вейвлетной области.
• Вейвлет-преобразование представляет собой полосовое представление сигнала с несколькими разрешениями. Это можно увидеть непосредственно из определения набора фильтров дискретного вейвлет-преобразования, данного в этой статье. Для сигнала длины ${ displaystyle 2 ^ {N}}$, коэффициенты в диапазоне ${ displaystyle [2 ^ {N-j}, 2 ^ {N-j + 1}]}$ представляют собой версию исходного сигнала, который находится в полосе пропускания ${ displaystyle left [{ frac { pi} {2 ^ {j}}}, { frac { pi} {2 ^ {j-1}}} right]}$. Вот почему увеличение этих диапазонов вейвлет-коэффициентов выглядит так похоже по структуре на исходный сигнал. Ближе к левому краю (больший ${ displaystyle j}$ в обозначениях выше) являются более грубым представлением сигнала, а диапазоны справа представляют более мелкие детали.

Смотрите также

• Дискретное косинусное преобразование (DCT)
• Вейвлет
• Серия вейвлетов
• Вейвлет-сжатие
• Список преобразований, связанных с вейвлетами

Рекомендации

внешняя ссылка

• Стэнфордский WaveLab в Matlab
• libdwt, кроссплатформенная библиотека DWT, написанная на C
• Краткое введение в вейвлеты Рене Пушингер