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

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

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

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

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

Основы

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

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

$P(z)={\begin{bmatrix}h_{\text{even}}(z)&g_{\text{even}}(z)\\h_{\text{odd}}(z)&g_{\text{odd}}(z)\end{bmatrix}},$

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

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

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

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

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

$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 требуется всего четыре шага подъема: два шага прогнозирования и два шага обновления.Факторизация подъема приводит к следующей последовательности шагов фильтрации.

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

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

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

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

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

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

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

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

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

Ускорение

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

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

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

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

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

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

Общий лифтинг

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

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

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

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

Определение

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

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

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

   $g_{j+1}[n]=P(f_{j}^{o}[n];f_{j}^{e}[n]).$

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

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

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

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

Дизайн

Некоторые проекты были разработаны для картирования этапов прогнозирования. Разработка этапа обновления не рассматривалась столь тщательно, поскольку еще предстоит ответить, насколько именно полезен этап обновления. Основное применение этого метода — сжатие изображений. Там есть некоторые интересные ссылки, такие как: и.

Приложения

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

См. также

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

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

• Lifting Scheme – краткое описание алгоритма факторинга
• Введение в схему подъема
• Быстрое подъемное вейвлет-преобразование