Схема лифтинга

Последовательность лифтинга из двух шагов

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

Общая идея

Пусть есть сигнал сигнал $f$. Его можно разделить на сигналы $L1$ и $Y1$ некоторым фильтром $s$ с прореживанием отсчетов в два раза. В общем случае сигналы $L1$ и $Y1$ в большой степени коррелированы между собой, поэтому нет смысла передавать оба сигнала, можно передать один из сигналов ($L1$) и сделанное на основе него с помощью фильтра $P$ предсказание второго сигнала $Y2=Y1 - P(Y2)$. Таким образов в некоторой степени убирается пространственная корреляция. Однако возникают проблемы в частотной области, поскольку сигнал $L1$ получается простым прореживанием отсчетов. Текущее среднее сигналов $L1$ и $f$ не совпадает. Для устранения этого вводят второй фильтр $U$, соответствующим образом обновляющий сигнал $L1$ на основе $Y2$ ( $L2 = L1 + U(Y2)$ ).

Пример

Возьмем сигнал $f$ из элементов $x_i$. В качестве фильтра возьмем простое разделение на четные и нечетные отсчеты:

$L1_i = x_{2i}$;

$Y1_i = x_{2i+1}$.

Предсказанием сигнала $Y1$ может, например, быть среднее статистическое соседних элементов $L1$

$P(i)= {(L1_i+ L1_{i+1}) \over 2}$;

$Y2_i = Y1_i - {(L1_i + L1_{i+1}) \over 2}$.

Для уточнения сигнала $L1$ следует добавить половину от среднестатистического предыдущего и следующего значений $Y2$. В этом случае $L2$ будет более соответствовать сигналу $f$, чем $L1$.

$U(i)= {(Y2_{i-1}+Y2_i) \over 4}$.

Соответственно,

$L2_i = L1_i + {(Y2_{i-1} + Y2_i) \over 4}$.

Зная $L2$ и $Y2$ по $U$, $P$ и $S^{-1}$ можно восстановить $f$.

Основы

Основная идея лифтинга заключается в следующем: если пара фильтров $(h,g)$ являются дополнительными, то для любого фильтра $s$ пара $(h',g)$, где $h'(z) = h(z) + s(z^2)\cdot g(z)$, также обеспечивает возможность полного восстановления сигнала. Естественно, это верно и для каждой пары $(h,g')$, где $g'(z) = g(z) + t(z^2)\cdot h(z)$. Обратное утверждение также верно: если наборы фильтров $(h,g)$ и $(h',g)$ позволяют полностью восстановить сигнал, то есть такой единственный фильтр $s$, при котором $h'(z) = h(z) + s(z^2)\cdot g(z)$. Каждое такое преобразование набора фильтров (или соответствующая операция преобразования вейвлет) называется шагом лифтинга. Последовательность шагов лифтинга состоит из чередующихся лифтов, то есть после фиксации фильтра низких частот и изменения фильтра высоких частот на следующем шаге фиксируется фильтр верхних частот и изменяется фильтр низких частот. Последовательные шаги в одном направлении можно объединять.

Свойства

• Восстановление без потерь.
  • Каждое преобразование схемы лифтинга можно обратить.
  • Каждый набор полностью восстанавливающих фильтров можно разбить на шаги лифтинга с помощью алгоритма Евклида.
  • Это значит, что «разбиваемый набор фильтров лифтинга» и «полностью обращающий набор фильтров лифтинга» – это одно и тоже.
• Любые два полностью восстанавливающие набора фильтров можно преобразовать один в другой набором шагов лифтинга (Если $P$ и $Q$ являются многофазными матрицами с одним и тем же дискриминантом, то последовательность лифтинга от $P$ до $Q$ такая же, как от «ленивой» многофазной матрицы $I$ до $P^{-1}\cdot Q$.)
• Ускорение в два раза. Это возможно только потому, что лифтинг можно делать только полностью восстанавливающими наборами фильтров. То есть, можно сказать, что лифтинг выбирает избыточность, вызваную возможностью полного восстановления.
• На месте: Преобразование можно осуществить сразу в памяти вводных данных, используя только ее и постоянную память.
• Нелинейность: Операции свертки можно заменить любыми другими. Для полного восстановления необходимо лишь, чтобы операции были обратимыми. Так можно представлять ошибки округления при свертке, что делает возможным точное побитовое восстановление. Несмотря на это, нелинейности могут привести к уменьшению числовой стабильности. Это следует учитывать, если преобразованный сигнал обрабатывается как при сжатии с потерями.

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

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

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

Применение

• Вейвлет преобразование с целыми числами: WAILI
• Преобразование фурье с точным побитовым восстановлением: Soontorn Oraintara, Ying-Jui Chen, Truong Q. Nguyen: Целочисленное быстрое преобразование фурье
• Проектирование вейвлетов с заданной степенью фильтра и количеством исчезающих моментов
• Проектирование вейвлетов зааданной модели: Henning Thielemann: Optimally matched wavelets
• Применение Дискреного Вейвлет-преобразования в JPEG2000

См. также

• В схеме Фейстеля в криптологии используется почти такая же идея разделения информации и чередующемся применении функций с добавлением. Это используется для симметричного ко- и декодирования как в в схеме Фейстеля, так и в схеме Лифтинга.

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

• A comprehensive introduction to the Fast Lifting Wavelet Transform
• Ingrid Daubechies, Wim Sweldens: Factoring Wavelet Transforms into Lifting Steps
• Lifting wavelet Transform steps : [1]
• The Lifting Scheme: A Construction of Second Generation Wavelets