Схема подъема - Lifting scheme

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

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

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

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

Основы

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

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

{ Displaystyle P (z) = { begin {bmatrix} h _ { text {even}} (z) & g _ { text {even}} (z) h _ { text {odd}} (z) & g_ { text {odd}} (z) end {bmatrix}},}

куда ${ Displaystyle Det P (Z) = z ^ {- m}}$ .

Многофазная матрица представляет собой матрицу 2 × 2, содержащую анализируемые фильтры нижних и верхних частот, каждый из которых разделен на свои четные и нечетные полиномиальные коэффициенты и нормализован. Отсюда матрица факторизуется в серию 2 × 2 верхнетреугольных и нижнетреугольных матриц, каждая с диагональными элементами, равными 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 a}$ - коэффициент для шага прогноза, а ${ displaystyle b}$ - коэффициент для шага обновления.

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

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

CDF 9/7 фильтр

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

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

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

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

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

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

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

Характеристики

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

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

Ускорение

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

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

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

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

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

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

Общий подъем

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

Приложения

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

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

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

внешняя ссылка

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

[Sweldens1997-1] Свелденс, Вим (1997). «Схема подъема: построение вейвлетов второго поколения» (PDF). Журнал математического анализа. 29 (2): 511–546. Дои:10.1137 / S0036141095289051.

[Mallat2009-2] Маллат, Стефан (2009). Вейвлет-тур по обработке сигналов. Академическая пресса. ISBN 978-0-12-374370-1.

[Daubechies1998-3] а ^б Добеши, Ингрид; Свелденс, Вим (1998). «Факторинг преобразования вейвлета в шаги подъема» (PDF). Журнал анализа Фурье и приложений. 4 (3): 247–269. Дои:10.1007 / BF02476026.

[Oraintara2002-4] Орайнтара, Сунторн; Чен, Ин-Цзюй; Нгуен, Чыонг К. (2002). «Целочисленное быстрое преобразование Фурье» (PDF). Транзакции по обработке сигналов. 50 (3): 607–618. Дои:10.1109/78.984749.

[Thielemann2004-5] Тилеманн, Хеннинг (2004). «Оптимально согласованные вейвлеты». Труды по прикладной математике и механике. 4: 586–587. Дои:10.1002 / pamm.200410274.

[Fattal2009-6] Фаттал, Раанан (2009). "Вейвлеты, избегающие краев, и их приложения". Транзакции ACM на графике. 28 (3): 1. CiteSeerX 10.1.1.205.8462. Дои:10.1145/1531326.1531328.

[Uytterhoeven1998-7] Уттерховен, Герт; Bultheel, Adhemar (1998). Красно-черное вейвлет-преобразование. Симпозиум по обработке сигналов (IEEE Benelux). С. 191–194.

[1]

[2]

[3]

[4]

[5]

[6]

[7]