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

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

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

$sn\; (J):\; =\; 2\; J\; ⟨f\; (t),\; \varphi \; (2\; J\; t\; -\; n)⟩,\; \{\backslash \; displaystyle\; s\_\; \{n\}\; ^\; \{(J)\}\; :\; =\; 2\; ^\; \{J\}\; \backslash \; langle\; f\; (t),\; \backslash \; phi\; (2\; ^\; \{J\}\; tn)\; \backslash \; rangle,\}$

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

$PJ\; [f]\; (x):\; =\; \sum \; n\; \in \; Z\; sn\; (J)\; \varphi \; (2\; J\; x\; -\; n)\; \{\backslash \; displaystyle\; P\_\; \{J\}\; [f]\; (x):\; =\; \backslash \; sum\; \_\; \{n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}\; s\_\; \{n\}\; ^\; \{(J)\}\; \backslash ,\; \backslash \; phi\; (2\; ^\; \{J\}\; xn)\}$

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

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

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

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

$b\; =\; (b\; -\; N,\dots ,\; b\; 0,\dots ,\; b\; N)\; \{\backslash \; displaystyle\; b\; =\; (b\; \_\; \{-\; N\},\; \backslash \; точек,\; b\_\; \{0\},\; \backslash \; dots,\; b\_\; \{N\})\}$или $b\; (z)\; =\; \sum \; n\; =\; -\; NN\; bnz\; -\; n\; \{\backslash \; displaystyle\; b\; (z)\; =\; \backslash \; sum\; \_\; \{n\; =\; -N\}\; ^\; \{N\}\; b\_\; \{n\}\; z\; ^\; \{-\; n\}\}$

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

• 1 Forward DWT
• 2 Обратный DWT
• 3 См. Также
• 4 Ссылки
• 5 Дополнительная литература

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

$sn\; (k):\; =\; 1\; 2\; \sum \; m\; =\; -\; NN\; ams\; 2\; n\; +\; m\; (k\; +\; 1)\; \{\backslash \; displaystyle\; s\_\; \{n\}\; ^\; \{(k)\}:\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; sum\; \_\; \{m\; =\; -N\}\; ^\; \{N\}\; a\_\; \{m\}\; s\_\; \{2n\; +\; m\}\; ^\; \{(k\; +\; 1)\}\}$или $s\; (k)\; (z):\; =\; (\downarrow \; 2)\; (a\; \ast \; (z)\; \cdot \; s\; (k\; +\; 1)\; (z))\; \{\backslash \; displaystyle\; s\; ^\; \{(\; k)\}\; (z):\; =\; (\backslash \; downarrow\; 2)\; (a\; ^\; \{*\}\; (z)\; \backslash \; cdot\; s\; ^\; \{(k\; +\; 1)\}\; (z))\}$

и

$dn\; (k):\; Знак\; равно\; 1\; 2\; \sum \; м\; знак\; равно\; -\; NN\; bms\; 2\; N\; +\; м\; (к\; +\; 1)\; \{\backslash \; displaystyle\; d\_\; \{n\}\; ^\; \{(k)\}:\; =\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; sum\; \_\; \{m\; =\; -\; N\}\; ^\; \{N\}\; b\_\; \{m\}\; s\_\; \{2n\; +\; m\}\; ^\; \{(k\; +\; 1)\}\}$или $d\; (k)\; (z):\; =\; (\downarrow \; 2)\; (b\; \ast \; (z)\; \cdot \; s\; (k\; +\; 1)\; (z))\; \{\backslash \; displaystyle\; d\; ^\; \{(k)\}\; (z):\; =\; (\backslash \; downarrow\; 2)\; (b\; ^\; \{*\}\; (z)\; \backslash \; cdot\; s\; ^\; \{(k\; +\; 1)\}\; (z))\}$,

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

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

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

$P\; k\; [f]\; (x):\; =\; \sum \; n\; \in \; Z\; sn\; (k)\; \varphi \; (2\; kx\; -\; n)\; \{\backslash \; displaystyle\; P\_\; \{k\}\; [\; f]\; (x):\; =\; \backslash \; sum\; \_\; \{n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}\; s\_\; \{n\}\; ^\; \{(k)\}\; \backslash ,\; \backslash \; phi\; (2\; ^\; \{k\}\; xn)\}$

- ортогональная проекция исходного сигнала f или, по крайней мере, первого приближения $PJ\; [f]\; (x)\; \{\backslash \; displaystyle\; P\_\; \{J\}\; [f]\; (x)\}$на подпространство $V\; k\; \{\backslash \; displaystyle\; V\_\; \{k\}\}$, то есть с частотой дискретизации 2 на единичный интервал. Разница в первом приближении определяется следующим образом:

$PJ\; [f]\; (x)\; =\; P\; k\; [f]\; (x)\; +\; D\; k\; [f]\; (x)\; +\; \cdots \; +\; DJ\; -\; 1\; [f]\; (x)\; \{\; \backslash \; Displaystyle\; P\_\; \{J\}\; [f]\; (x)\; =\; P\_\; \{k\}\; [f]\; (x)\; +\; D\_\; \{k\}\; [f]\; (x)\; +\; \backslash \; dots\; +\; D\_\; \{J-1\}\; [f]\; (x)\; \}$,

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

$D\; k\; [f]\; (x):\; =\; \sum \; n\; \in \; Z\; dn\; (k)\; \psi \; (2\; kx\; -\; n)\; \{\backslash \; displaystyle\; D\_\; \{\; k\}\; [f]\; (x):\; =\; \backslash \; sum\; \_\; \{n\; \backslash \; in\; \backslash \; mathbb\; \{Z\}\}\; d\_\; \{n\}\; ^\; \{(k)\}\; \backslash ,\; \backslash \; psi\; (2\; ^\; \{k\}\; xn)\}$,

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

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

$sn\; (k\; +\; 1):\; =\; \sum \; k\; =\; -\; NN\; aks\; 2\; N\; -\; К\; (К)\; +\; \sum \; К\; знак\; равно\; -\; NN\; BKD\; 2\; N\; -\; К\; (К)\; \{\backslash \; Displaystyle\; s\_\; \{n\}\; ^\; \{(k\; +\; 1)\}:\; =\; \backslash \; sum\; \_\; \{k\; =\; -N\}\; ^\; \{N\}\; a\_\; \{k\}\; s\_\; \{2n-k\}\; ^\; \{(k)\}\; +\; \backslash \; 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\; (к)\; (z))\; \{\backslash \; displaystyle\; s\; ^\; \{(k\; +\; 1)\}\; (z)\; =\; a\; (z)\; \backslash \; cdot\; (\backslash \; uparrow\; 2)\; (s\; ^\; \{(k)\}\; (z))\; +\; b\; (z)\; \backslash \; cdot\; (\backslash \; uparrow\; 2)\; (d\; ^\; \{(k)\}\; (z))\}$

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

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

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

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

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