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

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

Схема подъема - это метод как для разработки вейвлетов, так и для выполнения дискретного вейвлет-преобразования (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}$

Ускорение [ править ]

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

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

Нелинейности [ править ]

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

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

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

Обобщенный подъем [ править ]

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

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

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

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

Определение [ править ]

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

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

1. Выполняет обратное чередование входных данных в поток сэмплов с четными номерами и другой поток сэмплов с нечетными номерами. Иногда это называют « ленивым вейвлет-преобразованием» .
2. Вычисляет прогнозное отображение . Этот шаг пытается предсказать нечетные выборки с учетом четных (или наоборот). Есть отображение пространства сэмплов в пространстве сэмплов в . В этом случае образцы (из ), выбранные для справки , называются контекстом . Это можно было бы выразить как:${\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])}$

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

   ${\displaystyle \textstyle f_{j+1}[n]=U(f_{j}^{e}[n];g_{j+1}[n])}$

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

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

Дизайн [ править ]

Некоторые схемы были разработаны для отображения шага предсказания. Дизайн шага обновления не был рассмотрен так тщательно, потому что еще предстоит ответить, насколько именно этот шаг обновления полезен. Основное применение этой техники - сжатие изображений. Есть несколько интересных ссылок, таких как, ^{[5] [6] [7]} и. ^[8]

Приложения [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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