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

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

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

Примеры

Вейвлеты для волос

Основная статья: Вейвлет для волос

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

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

Основная статья: вейвлет Добеши

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

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

Основная статья: Комплексное вейвлет-преобразование

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

Другие

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

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

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

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

Из-за операторов изменения скорости в банке фильтров дискретный WT не является инвариантным во времени, но на самом деле очень чувствителен к выравниванию сигнала во времени. Чтобы решить проблему вейвлет-преобразований, изменяющихся во времени, Маллат и Чжун предложили новый алгоритм вейвлет-представления сигнала, который инвариантен к временным сдвигам. Согласно этому алгоритму, который называется TI-DWT, в двоичной последовательности 2^j (jεZ) выбирается только параметр масштаба, а для каждого момента времени рассчитывается вейвлет-преобразование.

Приложения

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

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

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

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

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

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

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

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

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

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

См. также: Дискретное преобразование Фурье.

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

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

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

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

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

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

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

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

${\begin{aligned}(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}}\end{aligned}}$

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

${\begin{aligned}&\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 truncation}}\\&\left(1,0,0,0\right)\end{aligned}}$

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

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

${\begin{aligned}&\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-term truncation}}\\&\left(1,0,0,0\right)\end{aligned}}$

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

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

Определение

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

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

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

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

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

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

$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]}$

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

С оператором подвыборки $\downarrow$

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

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

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

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

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

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

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

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

Трехуровневый банк фильтров.

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

Например, сигнал с 32 выборками, диапазон частот от 0 до $f_{n}$ и 3 уровня декомпозиции, создаются 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}}/2$ к $f_{n}$	16

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

Связь с материнским вейвлетом

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

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

где $j$ является параметром масштаба и $k$ — параметр сдвига, оба из которых являются целыми числами.

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

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

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

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

Временная сложность

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

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

$T(N)=2N+T\left({\frac {N}{2}}\right)$

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

Например, дискретное вейвлет-преобразование Хаара является линейным, поскольку в этом случае $h[n]$ и $g[n]$ имеют постоянную длину 2.

$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).

Другие преобразования

• Алгоритм Adam7 , используемый для чересстрочной развертки в формате Portable Network Graphics (PNG), представляет собой многомасштабную модель данных, похожую на DWT с вейвлетами Хаара . В отличие от DWT, он имеет определенный масштаб — он начинается с блока 8×8 и осуществляет субдискретизацию изображения, а не децимацию ( фильтрация нижних частот , затем субдискретизация). Таким образом, он предлагает худшее частотное поведение, демонстрируя артефакты ( пикселизацию ) на ранних стадиях, в обмен на более простую реализацию.
  См. Также: алгоритм Adam7.
• Мультипликативное (или геометрическое) дискретное вейвлет-преобразование это вариант, который применяется к модели наблюдения ${\bf {y}}=f{\bf {X}}$ с участием взаимодействий положительной регулярной функции $f$ и мультипликативный независимый положительный шум $X$, с $\mathbb {E} X=1$. Обозначим ${\cal {W}}$, вейвлет-преобразование. С $f{\bf {X}}=f+{f({\bf {X}}-1)}$, то стандартное (аддитивное) дискретное вейвлет-преобразование ${\cal {W^{+}}}$ таков, что ${\cal {W^{+}}}{\bf {y}}={\cal {W^{+}}}f+{\cal {W^{+}}}{f({\bf {X}}-1)},$ где коэффициенты детализации ${\cal {W^{+}}}{f({\bf {X}}-1)}$ вообще нельзя считать разреженным из-за вклада $f$ в последнем выражении. В мультипликативной структуре вейвлет-преобразование таково, что ${\cal {W^{\times }}}{\bf {y}}=\left({\cal {W^{\times }}}f\right)\times \left({\cal {W^{\times }}}{\bf {X}}\right).$ Это «вложение» вейвлетов в мультипликативную алгебру включает в себя обобщенные мультипликативные приближения и операторы детализации: например, в случае вейвлетов Хаара, тогда с точностью до коэффициента нормализации $\alpha$, стандарт ${\cal {W^{+}}}$ приближения ( среднее арифметическое ) $c_{k}=\alpha (y_{k}+y_{k-1})$ и детали ( арифметические разности ) $d_{k}=\alpha (y_{k}-y_{k-1})$ становятся соответственно средними геометрическими аппроксимациями $c_{k}^{\ast }=(y_{k}\times y_{k-1})^{\alpha }$ и геометрические различия (детали) $d_{k}^{\ast }=\left({\frac {y_{k}}{y_{k-1}}}\right)^{\alpha }$ при использовании ${\cal {W^{\times }}}$.

Пример кода

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

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

public static int[] discreteHaarWaveletTransform(int[] input) {
    // This function assumes that input.length=2^n, n>1
    int[] output = new int[input.length];

    for (int length = input.length / 2; ; length = length / 2) {
        // length is the current length of the working area of the output array.
        // length starts at half of the array size and every iteration is halved until it is 1.
        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);
    }
}

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

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

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

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

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

См. также

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

Внешние ссылки

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