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

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

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

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

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

Основы

Самый простой вариант прямого вейвлет-преобразования, выраженный в схеме подъема, показан на рисунке выше. означает шаг прогнозирования, который будет рассматриваться изолированно. На этапе прогнозирования вычисляется вейвлет-функция в вейвлет-преобразовании. Это фильтр верхних частот. На этапе обновления вычисляется функция масштабирования, что приводит к более гладкой версии данных. ${\ 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, может быть разложена на множители, как описано выше. Поэтому каждое вейвлет-преобразование с конечными фильтрами можно разложить на серию шагов подъема и масштабирования. Добеши и Свелденс более подробно обсуждают ступенчатую экстракцию.

CDF 9/7 фильтр

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

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

Ускорение

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

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

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

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

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

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

Обобщенный лифтинг

Блок-схема преобразования схемы (прямого) подъема

Обобщенная схема подъема была разработана Joel Solé и Филипп Salembier и опубликовала в докторской диссертации подошвы в. Он основан на классической схеме подъема и обобщает ее, устраняя ограничение, скрытое в структуре схемы. Классическая схема подъема имеет три вида операций:

Ленивый вейвлет - преобразование расколы сигнала в двух новых сигналах: с нечетными отсчетами сигнала обозначаются и четные выборки сигнала обозначается . ${\ displaystyle f_ {j} [n]}$ ${\ displaystyle f_ {j} ^ {o} [n]}$ ${\ displaystyle f_ {j} ^ {e} [n]}$
На этапе прогнозирования вычисляется прогноз для нечетных выборок на основе четных выборок (или наоборот). Это предсказание вычитается из нечетных выборок, создавая сигнал ошибки . ${\ displaystyle g_ {j + 1} [n]}$
На этапе обновления выполняется повторная калибровка низкочастотной ветви с удалением части энергии во время субдискретизации. В случае классического подъема это используется для «подготовки» сигнала к следующему шагу прогнозирования. Он использует предсказанные нечетные выборки для подготовки четных (или наоборот). Это обновление вычитается из четных выборок, создавая сигнал, обозначенный как . ${\ displaystyle g_ {j + 1} [n]}$ ${\ displaystyle f_ {j} ^ {e} [n]}$ ${\ displaystyle f_ {j + 1} [n]}$

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

Определение

Блок-схема преобразования (прямой) Generalized Lifting Scheme.

Обобщенная схема подъема - это диадическое преобразование, которое следует следующим правилам:

Выполняет обратное перемежение ввода в поток сэмплов с четным номером и другой поток сэмплов с нечетным номером. Это иногда называют « ленивым вейвлет-преобразованием» .
Вычисляет прогнозное отображение . Этот шаг пытается предсказать нечетные выборки с учетом четных (или наоборот). Есть отображение пространства сэмплов в пространстве сэмплов в . В этом случае образцы (из ), выбранные для справки , называются контекстом . Это можно было бы выразить как: ${\ displaystyle f_ {j} ^ {e} [n]}$ ${\ displaystyle g_ {j + 1} [n]}$ ${\ displaystyle f_ {j} ^ {e} [n]}$ ${\ displaystyle f_ {j} ^ {o} [n]}$
${\ displaystyle \ textstyle g_ {j + 1} [n] = P (f_ {j} ^ {o} [n]; f_ {j} ^ {e} [n])}$
Вычисляет отображение обновлений . На этом этапе делается попытка обновить четные выборки с учетом предсказанных нечетных выборок. Это было бы своего рода подготовкой к следующему шагу предсказания, если таковой будет. Это можно было бы выразить как:
${\ displaystyle \ textstyle f_ {j + 1} [n] = U (f_ {j} ^ {e} [n]; g_ {j + 1} [n])}$

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

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

дизайн

Некоторые схемы были разработаны для отображения шага предсказания. Дизайн шага обновления не был рассмотрен так тщательно, потому что еще предстоит ответить, насколько именно этот шаг обновления полезен. Основное применение этой техники - сжатие изображений. Есть несколько интересных ссылок, таких как, и.

Приложения

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

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

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

использованная литература

^ Sweldens, Wim (1997). «Схема подъема: построение вейвлетов второго поколения» (PDF) . Журнал математического анализа . 29 (2): 511–546. DOI : 10.1137 / S0036141095289051 .
^ Маллат, Стефан (2009). Вейвлет-тур по обработке сигналов . Академическая пресса. ISBN 978-0-12-374370-1 .
^ ^a ^b Добеши, Ингрид ; Свелденс, Вим (1998). «Факторизация преобразований вейвлета в шаги подъема» (PDF) . Журнал анализа и приложений Фурье . 4 (3): 247–269. DOI : 10.1007 / BF02476026 .
^ Ph.D. Диссертация: Оптимизация и обобщение схем подъема: применение к сжатию изображений без потерь .
^ Ролон, JC; Салембье, П. (7–9 ноября 2007 г.). "Обобщенный подъем для представления и кодирования разреженных изображений" . Симпозиум по кодированию изображений, PCS 2007 .
^ Ролон, JC; Salembier, P .; Аламеда, X. (12–15 октября 2008 г.). «Сжатие изображений с обобщенным поднятием и частичным знанием сигнала pdf» (PDF) . Международная конференция по обработке изображений, ICIP'08 .
^ Ролон, JC; Ортега, А .; Салембье П. «Моделирование контуров в вейвлетной области для обобщенного сжатия подъемных изображений» (PDF) . ICASSP 2009 (представлен) .
^ Ролон, JC; Mendonça, E .; Салембье, П. Обобщенный подъем с адаптивной локальной оценкой PDF для кодирования изображений (PDF) .
^ Орайнтара, Сунторн; Чен, Ин-Цзюй; Нгуен, Чыонг К. (2002). «Целочисленное быстрое преобразование Фурье» (PDF) . Сделки по обработке сигналов . 50 (3): 607–618. DOI : 10.1109 / 78.984749 .
^ Тилеманн, Хеннинг (2004). «Оптимально согласованные вейвлеты» . Труды по прикладной математике и механике . 4 : 586–587. DOI : 10.1002 / pamm.200410274 .
^ Фаттал, Raanan (2009). «Вейвлеты, избегающие края и их приложения» . Транзакции ACM на графике . 28 (3): 1. CiteSeerX 10.1.1.205.8462 . DOI : 10.1145 / 1531326.1531328 .
^ Uytterhoeven, Geert; Bultheel, Adhemar (1998). Красно-черное вейвлет-преобразование . Симпозиум по обработке сигналов (IEEE Benelux). С. 191–194.

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

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

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

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

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

[4] Ph.D. Диссертация: Оптимизация и обобщение схем подъема: применение к сжатию изображений без потерь .

[5] Ролон, JC; Салембье, П. (7–9 ноября 2007 г.). "Обобщенный подъем для представления и кодирования разреженных изображений" . Симпозиум по кодированию изображений, PCS 2007 .

[6] Ролон, JC; Salembier, P .; Аламеда, X. (12–15 октября 2008 г.). «Сжатие изображений с обобщенным поднятием и частичным знанием сигнала pdf» (PDF) . Международная конференция по обработке изображений, ICIP'08 .

[7] Ролон, JC; Ортега, А .; Салембье П. «Моделирование контуров в вейвлетной области для обобщенного сжатия подъемных изображений» (PDF) . ICASSP 2009 (представлен) .

[8] Ролон, JC; Mendonça, E .; Салембье, П. Обобщенный подъем с адаптивной локальной оценкой PDF для кодирования изображений (PDF) .

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

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

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

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

Languages

In other projects