Схема подъема

редактировать

методика вейвлет-анализа

Последовательность подъема, состоящая из двух шагов

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

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

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

Содержание

1 Основы
2 Фильтр CDF 9/7
3 Свойства
- 3.1 Идеальная реконструкция
- 3.2 Ускорение
- 3.3 Нелинейности
- 3.4 Увеличение исчезающих моментов, стабильность, и регулярность
4 Обобщенный подъем
5 Приложения
6 См. также
7 Ссылки
8 Внешние ссылки

Основы

Простейшая версия прямого вейвлет-преобразования, выраженная Схема подъема представлена на рисунке выше. $P {\ displaystyle P}$ $P$ означает шаг прогнозирования, который будет рассматриваться отдельно. На этапе прогнозирования вычисляется вейвлет-функция в вейвлет-преобразовании. Это фильтр верхних частот. На этапе обновления вычисляется функция масштабирования, что приводит к более гладкой версии данных.

Как упомянуто выше, схема подъема является альтернативной техникой для выполнения DWT с использованием биортогональных вейвлетов. Чтобы выполнить DWT с использованием схемы подъема, соответствующие шаги подъема и масштабирования должны быть получены из биортогональных вейвлетов. Фильтры анализа ( $g, h {\ displaystyle g, h}$ $g, h$ ) конкретного вейвлета сначала записываются в многофазную матрицу

P (z) = [h even (z) g even (z) час нечетный (z) g нечетный (z)], {\ displaystyle P (z) = {\ begin {bmatrix} h _ {\ text {even}} (z) g _ {\ text {even}} (z) \\ h _ {\ text {odd}} (z) g _ {\ text {odd}} (z) \ end {bmatrix}},}

{\ Displaystyle P (Z) = {\ begin {bmatri x} h _ {\ text {even}} (z) g _ {\ text {even}} (z) \\ h _ {\ text {odd}} (z) g _ {\ text {odd}} (z) \ end {bmatrix}},}

где $det P (z) = z - m { \ displaystyle \ det P (z) = z ^ {- m}}$ ${\ displaystyle \ det P (z) = z ^ {- m}}$ .

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

P (z) = [1 a (1 + z - 1) 0 1] [1 0 b (1 + z) 1], {\ displaystyle P (z) = { \ begin {bmatrix} 1 a (1 + z ^ {- 1}) \\ 0 1 \ end {bmatrix}} {\ begin {bmatrix} 1 0 \\ b (1 + z) 1 \ end {bmatrix}},}

{\ displaystyle P (z) = {\ begin {bmatrix} 1 a (1 + z ^ {- 1}) \\ 0 1 \ end { bmatrix}} {\ begin {bmatrix} 1 0 \\ b (1 + z) 1 \ end {bmatrix}},}

, где $a {\ displaystyle a}$ $a$ - коэффициент для шага прогнозирования, а $b {\ displaystyle b}$ $b$ - коэффициент для шага обновления.

Пример более сложного извлечения, имеющего несколько шагов прогнозирования и обновления, а также шаги масштабирования, показан ниже; $a {\ displaystyle a}$ $a$ - коэффициент для первого шага прогнозирования, $b {\ displaystyle b}$ $b$ - коэффициент для первого шага обновления, $c {\ displaystyle c}$ $c$ - коэффициент для второго шага прогнозирования, $d {\ displaystyle d}$ $d$ - коэффициент для второго шага обновления, $k 1 {\ displaystyle k_ {1}}$ $k_ {1}$ - коэффициент масштабирования для нечетной выборки, а $k 2 {\ displaystyle k_ {2}}$ $k_ {2}$ - коэффициент масштабирования для четной выборки. :

P (z) = [1 a (1 + z - 1) 0 1] [1 0 b (1 + z) 1] [1 c (1 + z - 1) 0 1] [1 0 d (1 + z) 1] [k 1 0 0 k 2]. {\ Displaystyle P (z) = {\ begin {bmatrix} 1 a (1 + z ^ {- 1}) \\ 0 1 \ end {bmatrix}} {\ begin {bmatrix} 1 0 \\ b (1 + z) 1 \ end {bmatrix}} {\ begin {bmatrix} 1 c (1 + z ^ {- 1}) \\ 0 1 \ end {bmatrix}} {\ begin {bmatrix} 1 0 \\ d (1 + z) 1 \ end {bmatrix}} {\ begin {bmatrix} k_ {1} 0 \\ 0 k_ {2} \ end {bmatrix}}.}

{\ displaystyle P (z) = {\ begin {bmatrix} 1 a (1 + z ^ {- 1}) \\ 0 1 \ end {bmatrix}} {\ begin {bmatrix} 1 0 \\ b (1 + z) 1 \ end {bmatrix}} {\ begin {bmatrix} 1 c (1 + z ^ {- 1}) \\ 0 1 \ end {bmatrix}} {\ begin {bmatrix} 1 0 \\ d (1 + z) 1 \ end {bmatrix}} {\ begin {bmatrix} k_ {1} 0 \\ 0 k_ {2} \ end {bmatrix}}.}

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

Фильтр CDF 9/7

Для выполнения преобразования CDF 9/7 требуется в общей сложности четыре шага подъема: два прогнозирующих и два шага обновления. Факторизация подъема приводит к следующей последовательности шагов фильтрации.

dl = dl + a (sl + sl + 1), {\ displaystyle d_ {l} = d_ {l} + a (s_ {l} + s_ { l + 1}),}

{\ displaystyle d_ {l} = d_ {l} + a (s_ {l} + s_ {l + 1}),}

sl = sl + b (dl + dl - 1), {\ displaystyle s_ {l} = s_ {l} + b (d_ {l} + d_ {l-1}),}

{\ displaystyle s_ {l} = s_ {l} + b (d_ {l} + d_ {l-1}),}

dl = dl + c (sl + sl + 1), {\ displaystyle d_ {l} = d_ {l} + c (s_ {l} + s_ {l + 1}),}

{\ displaystyle d_ {l} = d_ {l} + c (s_ {l} + s_ {l + 1}),}

sl = sl + d (dl + dl - 1), {\ displaystyle s_ {l} = s_ {l} + d (d_ {l} + d_ {l-1}),}

{\ displaystyle s_ {l} = s_ {l} + d (d_ {l} + d_ {l-1}),}

dl = k 1 дл, {\ displaystyle d_ {l} = k_ {1} d_ {l},}

{\ displaystyle d_ {l} = k_ {1} d_ {l},}

sl = k 2 sl. {\ displaystyle s_ {l} = k_ {2} s_ {l}.}

{\ displaystyle s_ {l} = k_ {2} s_ {l}.}

Свойства

Идеальная реконструкция

Любое преобразование по схеме поднятия можно инвертировать. Каждый банк фильтров безупречной реконструкции можно разложить на этапы подъема с помощью алгоритма Евклида. То есть «набор фильтров с подъемно-разложением» и «набор фильтров с точным восстановлением» обозначают одно и то же. Каждые два банка фильтров с идеальной реконструкцией можно преобразовать друг в друга с помощью последовательности шагов подъема. Для лучшего понимания, если $P {\ displaystyle P}$ $P$ и $Q {\ displaystyle Q}$ $Q$ являются многофазными матрицами с тем же определителем, то последовательность подъема от $P {\ displaystyle P}$ $P$ до $Q {\ displaystyle Q}$ $Q$ такая же, как и в ленивой многофазной матрице $I {\ displaystyle I}$ $I$ до $P - 1 ⋅ Q {\ displaystyle P ^ {- 1} \ cdot Q}$ $P ^ {{- 1}} \ cdot Q$ .

Ускорение

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

Преобразование может быть выполнено немедленно в памяти входных данных (на месте, на месте) только с постоянными накладными расходами памяти.

Нелинейности

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

Увеличение исчезающих моментов, стабильности и регулярности

Лифтинг изменяет биортогональные фильтры, чтобы увеличить количество исчезающих моментов получаемых биортогональных вейвлетов и, надеюсь, их стабильность и регулярность. Увеличение числа исчезающих моментов уменьшает амплитуду вейвлет-коэффициентов в областях, где сигнал является регулярным, что дает более разреженное представление. Однако увеличение количества исчезающих моментов с подъемом также увеличивает поддержку вейвлета, что является неблагоприятным эффектом, который увеличивает количество больших коэффициентов, создаваемых изолированными сингулярностями. Каждый шаг подъема поддерживает биортогональность фильтра, но не обеспечивает управления границами Рисса и, следовательно, стабильностью полученного биортогонального базиса вейвлета. Когда базис ортогонален, дуальный базис равен исходному базису. Следовательно, наличие дуальной основы, аналогичной исходной, является показателем устойчивости. В результате стабильность обычно повышается, когда двойные вейвлеты имеют столько же исчезающих моментов, сколько исходные вейвлеты, и опору аналогичного размера. Вот почему процедура лифтинга также увеличивает количество исчезающих моментов двойных вейвлетов. Это также может улучшить регулярность двойного вейвлета. Расчет подъема рассчитывается путем корректировки количества исчезающих моментов. Стабильность и регулярность полученных биортогональных вейвлетов измеряется апостериори в надежде на лучшее. Это основная слабость данной процедуры проектирования вейвлетов.

Обобщенный подъем

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

Приложения

Вейвлет-преобразования, которые преобразуют целые числа в целые
преобразование Фурье с точным побитовым восстановлением
Построение вейвлетов с необходимым количеством коэффициентов гладкости и исчезающими моментами
Построение вейвлетов, согласованных с заданным шаблоном
Реализация дискретного вейвлет-преобразования в JPEG 2000
Преобразования, управляемые данными, например, избегание краев вейвлеты
Вейвлет-преобразования на неразделимых решетках, например, красно-черные вейвлеты на решетке квинконса

См. также

Схема Фейстеля в криптологии использует во многом ту же идею разделение данных и применение функции чередования с добавлением. И в схеме Фейстеля, и в схеме подъема это используется для симметричного кодирования и декодирования.

Ссылки

^Sweldens, Wim (1997). «Схема подъема: построение вейвлетов второго поколения» (PDF). Журнал математического анализа. 29 (2): 511–546. doi : 10.1137 / S0036141095289051.
^Маллат, Стефан (2009). Вейвлет-обзор обработки сигналов. Академическая пресса. ISBN 978-0-12-374370-1.
^ Добешис, Ингрид ; Свелденс, Вим (1998). «Факторинг преобразования вейвлета в шаги подъема» (PDF). Журнал анализа и приложений Фурье. 4 (3): 247–269. doi : 10.1007 / BF02476026.
^Орайнтара, Сунторн; Чен, Ин-Цзюй; Нгуен, Чыонг К. (2002). «Целочисленное быстрое преобразование Фурье» (PDF). Сделки по обработке сигналов. 50 (3): 607–618. doi : 10.1109 / 78.984749.
^Тилеманн, Хеннинг (2004). «Оптимально согласованные вейвлеты». Труды по прикладной математике и механике. 4 : 586–587. doi : 10.1002 / pamm.200410274.
^Фаттал, Раанан (2009). "Вейвлеты, избегающие краев, и их приложения". Транзакции ACM на графике. 28 (3): 1. CiteSeerX 10.1.1.205.8462. doi : 10.1145 / 1531326.1531328.
^Уттерховен, Герт; Bultheel, Adhemar (1998). Красно-черное вейвлет-преобразование. Симпозиум по обработке сигналов (IEEE Benelux). С. 191–194.

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

Схема подъема - краткое описание алгоритма факторинга
Введение в схему подъема