Быстрое вейвлет-преобразование - Fast wavelet transform

В Быстрое вейвлет-преобразование это математический алгоритм разработан, чтобы превратить форма волны или сигнал в область времени в последовательность коэффициентов на основе ортогональный базис малых конечных волн, или вейвлеты. Преобразование может быть легко расширено до многомерных сигналов, таких как изображения, где временная область заменена пространственной. Этот алгоритм был представлен в 1989 г. Стефан Малла.^[1]

В качестве теоретической основы он имеет устройство конечно порожденного ортогонального анализ с несколькими разрешениями (MRA). В приведенных здесь терминах выбирается шкала выборки. J с частота выборки из 2^J на единицу интервала и проецирует данный сигнал ж в космос ${\displaystyle V_{J}}$; теоретически путем вычисления скалярные произведения

${\displaystyle s_{n}^{(J)}:=2^{J}\langle f(t),\phi (2^{J}t-n)\rangle ,}$

куда ${\displaystyle \phi }$ это функция масштабирования выбранного вейвлет-преобразования; на практике любой подходящей процедурой выборки при условии, что сигнал сильно передискретизирован, поэтому

${\displaystyle P_{J}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\phi (2^{J}x-n)}$

это ортогональная проекция или, по крайней мере, хорошее приближение к исходному сигналу в ${\displaystyle V_{J}}$.

MRA характеризуется последовательностью масштабирования

${\displaystyle a=(a_{-N},\dots ,a_{0},\dots ,a_{N})}$ или, как Z-преобразование, ${\displaystyle a(z)=\sum _{n=-N}^{N}a_{n}z^{-n}}$

и его вейвлет-последовательность

${\displaystyle b=(b_{-N},\dots ,b_{0},\dots ,b_{N})}$ или же ${\displaystyle b(z)=\sum _{n=-N}^{N}b_{n}z^{-n}}$

(некоторые коэффициенты могут быть нулевыми). Они позволяют вычислять вейвлет-коэффициенты ${\displaystyle d_{n}^{(k)}}$, хоть какой-то диапазон к = М, ..., J-1, без необходимости аппроксимировать интегралы в соответствующих скалярных произведениях. Вместо этого можно напрямую, с помощью операторов свертки и децимации, вычислить эти коэффициенты из первого приближения. ${\displaystyle s^{(J)}}$.

Форвард DWT

Для дискретное вейвлет-преобразование (DWT), вычисляется рекурсивно, начиная с последовательности коэффициентов ${\displaystyle s^{(J)}}$ и отсчитывая от к = J-1 некоторым M ,

однократное применение банка вейвлет-фильтров с фильтрами g = a^*, h = b^*

${\displaystyle s_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}a_{m}s_{2n+m}^{(k+1)}}$ или же ${\displaystyle s^{(k)}(z):=(\downarrow 2)(a^{*}(z)\cdot s^{(k+1)}(z))}$

и

${\displaystyle d_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}b_{m}s_{2n+m}^{(k+1)}}$ или же ${\displaystyle d^{(k)}(z):=(\downarrow 2)(b^{*}(z)\cdot s^{(k+1)}(z))}$,

за k = J-1, J-2, ..., M и все ${\displaystyle n\in \mathbb {Z} }$. В обозначении Z-преобразования:

рекурсивное применение банка фильтров

• В оператор понижающей дискретизации ${\displaystyle (\downarrow 2)}$ сводит бесконечную последовательность, заданную ее Z-преобразование, который просто Серия Laurent, к последовательности коэффициентов с четными индексами, ${\displaystyle (\downarrow 2)(c(z))=\sum _{k\in \mathbb {Z} }c_{2k}z^{-k}}$.
• Звездчатый полином Лорана ${\displaystyle a^{*}(z)}$ обозначает сопряженный фильтр, она имеет обращенный во времени сопряженные коэффициенты, ${\displaystyle a^{*}(z)=\sum _{n=-N}^{N}a_{-n}^{*}z^{-n}}$. (Сопряжение действительного числа - это само число, комплексного числа - его сопряжение, вещественной матрицы - транспонированная матрица, к комплексной матрице - ее эрмитово сопряженное число).
• Умножение - это полиномиальное умножение, которое эквивалентно свертке последовательностей коэффициентов.

Следует, что

${\displaystyle P_{k}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\phi (2^{k}x-n)}$

ортогональная проекция исходного сигнала ж или хотя бы в первом приближении ${\displaystyle P_{J}[f](x)}$ на подпространство ${\displaystyle V_{k}}$, то есть с частотой дискретизации 2^k на единицу интервала. Разница в первом приближении определяется выражением

${\displaystyle P_{J}[f](x)=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x)}$,

где сигналы разности или детализации вычисляются из детальных коэффициентов как

${\displaystyle D_{k}[f](x):=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}x-n)}$,

с ${\displaystyle \psi }$ обозначая материнский вейвлет вейвлет-преобразования.

Обратный DWT

Учитывая последовательность коэффициентов ${\displaystyle s^{(M)}}$ для некоторых M и все разностные последовательности ${\displaystyle d^{(k)}}$, к = М, ..., J-1, вычисляется рекурсивно

${\displaystyle s_{n}^{(k+1)}:=\sum _{k=-N}^{N}a_{k}s_{2n-k}^{(k)}+\sum _{k=-N}^{N}b_{k}d_{2n-k}^{(k)}}$ или же ${\displaystyle s^{(k+1)}(z)=a(z)\cdot (\uparrow 2)(s^{(k)}(z))+b(z)\cdot (\uparrow 2)(d^{(k)}(z))}$

за к = J-1, J-2, ..., M и все ${\displaystyle n\in \mathbb {Z} }$. В обозначении Z-преобразования:

• В оператор передискретизации ${\displaystyle (\uparrow 2)}$ создает пустоты с нулевым заполнением внутри заданной последовательности. То есть каждый второй элемент результирующей последовательности является элементом данной последовательности, каждый второй элемент равен нулю или ${\displaystyle (\uparrow 2)(c(z)):=\sum _{n\in \mathbb {Z} }c_{n}z^{-2n}}$. Этот линейный оператор находится в Гильбертово пространство ${\displaystyle \ell ^{2}(\mathbb {Z} ,\mathbb {R} )}$, сопряженный к оператору понижающей дискретизации ${\displaystyle (\downarrow 2)}$.

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

• Схема подъема
• Быстрое преобразование Фурье

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

1. «Алгоритм быстрого вейвлет-преобразования (FWT)». MathWorks. Получено 2018-02-20.

• С.Г. Маллат "Теория разложения сигналов с разными разрешениями: представление вейвлетов" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, вып. 7. Июль 1989 г.
• А.Н. Акансу Субоптимальный дизайн PR-QMF без умножения Proc. SPIE 1818, Визуальные коммуникации и обработка изображений, стр. 723, ноябрь 1992 г.
• А.Н. Акансу Банки двухполосных квадратурных зеркальных фильтров без умножителя (PR-QMF) с идеальной реконструкцией Патент США 5420891, 1995 г.
• А.Н. Акансу Квадратурные зеркальные фильтры PR без умножения для кодирования поддиапазонов изображений IEEE Trans. Обработка изображений, стр. 1359, сентябрь 1996 г.
• M.J. Mohlenkamp, M.C. Перейра Вейвлеты, их друзья и что они могут для вас сделать (2008 EMS) стр. 38
• Б. Б. Хаббард Мир согласно вейвлетам: история создания математической техники (Питерс, 1998) с. 184
• С.Г. Маллат Вейвлет-тур по обработке сигналов (1999 Academic Press) стр. 255
• А. Теолис Вычислительная обработка сигналов с помощью вейвлетов (1998 Birkhäuser) стр. 116
• Ю. Нивергельт Вейвлеты - это просто (1999 Springer) стр. 95

дальнейшее чтение

Г. Бейлкин, Р. Койфман, В. Рохлин, «Быстрые вейвлет-преобразования и численные алгоритмы» Comm. Pure Appl. Математика., 44 (1991) с. 141–183. Дои:10.1002 / cpa.3160440202 (Эта статья процитирована более 2400 раз.)