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

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

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

Содержание

• 1 Примеры
  • 1.1 Вейвлеты Хаара
  • 1.2 Вейвлеты Добеши
  • 1.3 Комплексное вейвлет-преобразование двойного дерева (DℂWT)
  • 1.4 Прочее
• 2 Свойства
  • 2.1 Время проблемы
• 3 Приложения
• 4 Пример обработки изображений
• 5 Сравнение с преобразованием Фурье
• 6 Определение
  • 6.1 Один уровень преобразования
  • 6.2 Каскадные блоки и банки фильтров
• 7 Связь с материнский вейвлет
• 8 Временная сложность
• 9 Другие преобразования
• 10 Пример кода
  • 10.1 Пример приведенного выше кода
• 11 См. также
• 12 Ссылки
• 13 Внешние ссылки

Примеры

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

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

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

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

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

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

Другое

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

Свойства

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

$[1\; 1\; 1\; 1\; 1\; -\; i\; -\; 1\; i\; 1\; -\; 1\; 1\; -\; 1\; 1\; я\; -\; 1\; -\; я]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; -i\; -1\; i\; \backslash \backslash \; 1\; -1\; 1\; -1\; \backslash \backslash \; 1\; i\; -1\; -i\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[1\; 1\; 1\; 1\; 1\; 1\; -\; 1\; -\; 1\; 1\; -\; 1\; 0\; 0\; 0\; 0\; 1\; -\; 1]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 1\; 1\; -1\; -1\; \backslash \backslash \; 1\; -1\; 0\; 0\; \backslash \backslash \; 0\; 0\; 1\; -1\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

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

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

$(1,\; 0,\; 0,\; 0)\; =\; 1\; 4\; (1,\; 1,\; 1,\; 1)\; +\; 1\; 4\; (1,\; 1,\; -\; 1,\; -\; 1)\; +\; 1\; 2\; (1,\; -\; 1,\; 0,\; 0)\; Хаара\; DWT\; (1,\; 0,\; 0,\; 0)\; =\; 1\; 4\; (1,\; 1,\; 1,\; 1)\; +\; 1\; 4\; (1,\; i,\; -\; 1,\; -\; i)\; +\; 1\; 4\; (1,\; -\; 1,\; 1,\; -\; 1)\; +\; 1\; 4\; (1,\; -\; i,\; -\; 1,\; i)\; ДПФ\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; (1,0,0,0)\; =\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,1,1,1)\; +\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,1,\; -1,\; -1)\; +\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; (1,\; -1,0,0)\; \backslash \; qquad\; \{\backslash \; text\; \{\; Хаара\; DWT\}\}\; \backslash \backslash \; (1,0,0,0)\; =\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,1,1,1)\; +\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,\; i,\; -1,\; -i)\; +\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,\; -1,1,\; -1)\; +\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; (1,\; -i,\; -1,\; i)\; \backslash \; qquad\; \{\backslash \; text\; \{DFT\}\}\; \backslash \; end\; \{align\}\}\}$

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

$(1\; 4,\; 1\; 4,\; 1\; 4,\; 1\; 4)\; (1\; 2,\; 1\; 2,\; 0,\; 0)\; 2-членное\; усечение\; (1,\; 0,\; 0,\; 0)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; right)\; \backslash \backslash \; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{2\}\},\; \{\backslash \; frac\; \{1\}\; \{2\}\},\; 0,0\; \backslash \; right)\; \backslash \; qquad\; \{\backslash \; text\; \{2-членное\; усечение\}\}\; \backslash \backslash \; \backslash \; left\; (1,0,0,0\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

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

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

$(1\; 4,\; 1\; 4,\; 1\; 4,\; 1\; 4)\; (3\; 4,\; 1\; 4,\; -\; 1\; 4,\; 1\; 4)\; 2-членное\; усечение\; (1,\; 0,\; 0,\; 0)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\})\; \},\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; right)\; \backslash \backslash \; \backslash \; left\; (\{\backslash \; frac\; \{3\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\},\; -\; \{\backslash \; frac\; \{1\}\; \{4\}\},\; \{\backslash \; frac\; \{1\}\; \{4\}\}\; \backslash \; right)\; \backslash \; qquad\; \{\backslash \; text\; \{2-ter\; m\; усечение\}\}\; \backslash \backslash \; \backslash \; left\; (1,0,0,0\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

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

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

Определение

Один уровень преобразования

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

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

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

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

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

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

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

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

С помощью оператора подвыборки $\downarrow \; \{\backslash \; displaystyle\; \backslash \; downarrow\}$

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

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

$ylow\; =\; (x\; \ast \; g)\; \downarrow \; 2\; \{\backslash \; displaystyle\; y\; \_\; \{\backslash \; mathrm\; \{low\}\}\; =\; (x\; *\; g)\; \backslash \; downarrow\; 2\}$

$yhigh\; =\; (x\; \ast \; h)\; \downarrow \; 2\; \{\backslash \; displaystyle\; y\_\; \{\; \backslash \; mathrm\; \{high\}\}\; =\; (x\; *\; h)\; \backslash \; downarrow\; 2\}$

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

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

Группы каскадирования и фильтров

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

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

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

Например, сигнал с 32 отсчетами, диапазон частот от 0 до $fn\; \{\backslash \; displaystyle\; f\_\; \{n\}\}$и 3 уровня разложения, создаются 4 шкалы вывода:

Уровень	Частоты	Образцы
3	$0\; \{\backslash \; displaystyle\; 0\}$до $fn\; /\; 8\; \{\backslash \; displaystyle\; \{f\_\; \{n\}\}\; /\; 8\}$	4
	$fn\; /\; 8\; \{\backslash \; displaystyle\; \{f\_\; \{n\}\}\; /\; 8\}$to $fn\; /\; 4\; \{\backslash \; displaystyle\; \{f\_\; \{n\}\}\; /\; 4\}$	4
2	$fn\; /\; 4\; \{\; \backslash \; displaystyle\; \{f\_\; \{n\}\}\; /\; 4\}$to $fn\; /\; 2\; \{\backslash \; displaystyle\; \{f\_\; \{n\}\}\; /\; 2\}$	8
1	$fn\; /\; 2\; \{\backslash \; displaystyle\; \{f\_\; \{n\}\; \}\; /\; 2\}$to $fn\; \{\backslash \; displaystyle\; f\_\; \{n\}\}$	16

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В качестве примера дискретное преобразование вейвлета Хаара является линейным, поскольку в этом случае $h\; [n]\; \{\backslash \; displaystyle\; h\; [n]\}$и $g\; [n]\; \{\backslash \; displaystyle\; g\; [n]\}$имеют постоянную длину 2.

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

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

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

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

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

Пример кода

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

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

public static int discteHaarWaveletTransform (int input) {// Эта функция предполагает, что input.length = 2 ^ n, n>1 int output = new int [input.length]; for (int length = input.length / 2;; length = length / 2) {// длина - текущая длина рабочей области выходного массива. // длина начинается с половины размера массива, и каждая итерация уменьшается вдвое, пока не станет 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, Добеши, Coiflet и Legendre вейвлеты доступны из проекта с открытым исходным кодом: JWave. Кроме того, реализация быстрого подъема дискретного биортогонального CDF 9/7 вейвлет-преобразования в C, используемого в стандарте сжатия изображений JPEG 2000, можно найти здесь ( архивировано 5 марта 2012 г.).

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

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

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

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

См. также

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

Ссылки

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

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