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

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

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

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

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

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

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

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

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

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

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

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

Форвардный дедвейт

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

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

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

и

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

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

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

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

Отсюда следует, что

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

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

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

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

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

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

Обратный дедвейт

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

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

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

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

См. также

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

Ссылки

• С. Г. Маллат «Теория разложения сигнала с несколькими разрешениями: вейвлет-представление» Транзакции IEEE по анализу шаблонов и машинному интеллекту, том. 2, нет. 7. Июль 1989 года.
• Добеши И. «Десять лекций о вейвлетах». СИАМ, 1992 год.
• А.Н. Акансу Субоптимальное проектирование PR-QMF без множителей . SPIE 1818, Визуальные коммуникации и обработка изображений, с. 723, ноябрь 1992 г.
• AN Akansu 2-полосный квадратурный зеркальный фильтр с идеальной реконструкцией без умножителя (PR-QMF), патент США Бэнкса 5 420 891, 1995 г.
• AN Akansu Квадратурные зеркальные фильтры PR без умножителя для поддиапазонного кодирования изображения IEEE Trans. Обработка изображений, с. 1359, сентябрь 1996 г.
• MJ Mohlenkamp, ​​MC Pereyra Wavelets, их друзья и что они могут для вас сделать (2008 EMS), с. 38
• Б.Б. Хаббард. Мир согласно вейвлетам: история создания математической техники (Питерс, 1998), с. 184
• С.Г. Маллат. Вейвлет-тур по обработке сигналов (Academic Press, 1999), стр. 255
• А. Теолис Вычислительная обработка сигналов с помощью вейвлетов (1998 Биркхойзер) с. 116
• Ю. Нивергельт Вейвлеты стали проще (Springer, 1999), с. 95

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

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