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

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) Для проверки данной статьи необходимы дополнительные цитаты .Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены. Найти источники:  "Быстрое вейвлет-преобразование" – новости  · газеты  · книги  · ученый  · JSTOR ( январь 2010 г. )( Узнайте, как и когда удалить это сообщение ) В статье содержится список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты .Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Февраль 2018 )( Узнайте, как и когда удалить это сообщение ) ( Узнайте, как и когда удалить это сообщение )

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

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

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

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

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

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

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

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

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

${\displaystyle b=(b_{-N},\точки ,b_{0},\точки ,b_{N})}$или${\displaystyle b(z)=\sum _{n=-N}^{N}b_{n}z^{-n}}$

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

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

${\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 и всех . В нотации Z-преобразования:${\displaystyle n\in \mathbb {Z}}$

• Оператор понижения частоты дискретизации сводит бесконечную последовательность, заданную ее Z-преобразованием , которая является просто рядом Лорана , к последовательности коэффициентов с четными индексами, .${\displaystyle (\downarrow 2)}$${\displaystyle (\downarrow 2)(c(z))=\sum _{k\in \mathbb {Z} }c_{2k}z^{-k}}$
• Многочлен Лорана со звездочкой обозначает сопряженный фильтр , он имеет обращенные во времени сопряженные коэффициенты, (сопряжённый фильтр действительного числа — это само число, комплексного числа — его сопряжённая матрица, действительной матрицы — транспонированная матрица, комплексной матрицы — её эрмитово сопряжённая матрица).${\displaystyle а^{*}(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)}\,\varphi (2^{k}x-n)}$

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

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

${\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))}$

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

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

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

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