WikiSort.ru - Не сортированное

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

Общая идея

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

Пример

Возьмем сигнал ${\displaystyle f}$ из элементов ${\displaystyle x_{i}}$ . В качестве фильтра возьмем простое разделение на четные и нечетные отсчеты:

${\displaystyle L1_{i}=x_{2i}}$ ;

${\displaystyle Y1_{i}=x_{2i+1}}$ .

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

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

${\displaystyle Y2_{i}=Y1_{i}-{(L1_{i}+L1_{i+1}) \over 2}}$ .

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

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

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

${\displaystyle L2_{i}=L1_{i}+{(Y2_{i-1}+Y2_{i}) \over 4}}$ .

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

Основы

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

Свойства

• Восстановление без потерь.
  • Каждое преобразование схемы лифтинга можно обратить.
  • Каждый набор полностью восстанавливающих фильтров можно разбить на шаги лифтинга с помощью алгоритма Евклида.
  • Это значит, что «разбиваемый набор фильтров лифтинга» и «полностью обращающий набор фильтров лифтинга» – это одно и то же.
• Любые два полностью восстанавливающие набора фильтров можно преобразовать один в другой набором шагов лифтинга (Если ${\displaystyle P}$ и ${\displaystyle Q}$ являются многофазными матрицами с одним и тем же дискриминантом, то последовательность лифтинга от ${\displaystyle P}$ до ${\displaystyle Q}$ такая же, как от «ленивой» многофазной матрицы ${\displaystyle I}$ до ${\displaystyle 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 :
• The Lifting Scheme: A Construction of Second Generation Wavelets