Lifting

Lifting je výpočetní schéma diskrétní vlnkové transformace (DWT). Toto schéma je obvykle rychlejší než naivní výpočet pomocí konvoluce se dvěma zrcadlovými filtry. Tento algoritmus poprvé předvedl Wim Sweldens.

Jakákoli DWT s konečnými filtry může být faktorizována (např. pomocí Eukleidova algoritmu) do posloupností ${\displaystyle N}$ párů predikčních ${\displaystyle P_{n}}$ a aktualizačních ${\displaystyle U_{n}}$ konvolučních operátorů. Každý predikční operátor ${\displaystyle P_{n}}$ odpovídá filtru ${\displaystyle p_{i}^{(n)}}$ a každý aktualizační operátor ${\displaystyle U_{n}}$ filtru ${\displaystyle u_{i}^{(n)}}$.

${\displaystyle P_{n}(z)=\sum _{i}p_{i}^{(n)}z^{-i}}$

${\displaystyle U_{n}(z)=\sum _{i}u_{i}^{(n)}z^{-i}}$

Tato faktorizace není unikátní. Pro symetrické filtry může být tato neunikátnost využita k udržení symetrie kroků liftingu.

Prvním krokem při výpočtu liftingu je rozdělení signálu na sudé a liché vzorky (${\displaystyle s^{(0)},d^{(0)}}$). Následuje sekvence predikcí a aktualizací pomocí výše definovaných operátorů. Predikce ${\displaystyle P_{n}}$ v kroku ${\displaystyle n}$ se počítá nad vzorky ${\displaystyle s^{(n)}}$ a její výsledek se odečte od ${\displaystyle d^{(n)}}$, čímž vzniká ${\displaystyle d^{(n+1)}}$. Následná aktualizace ${\displaystyle U_{n}}$ s počítá nad upravenými ${\displaystyle d^{(n+1)}}$ a přičte se k ${\displaystyle s^{(n)}}$, čímž vzniká ${\displaystyle s^{(n+1)}}$. Výsledkem jsou prokládané koeficienty podpásem L (odpovídá ${\displaystyle s^{(n)}}$) a H (odpovídá ${\displaystyle d^{(n)}}$) diskrétní vlnkové transformace.

Využití

• Reverzibilní integer-to-integer transformace – Přidáním zaokrouhlovacího operátoru může lifting mapovat celá čísla na celá čísla. To může je užitečné pro bezeztrátovou kompresi obrazu.
• Edge-avoiding wavelets (EAW) – Varianta DWT, ve které je oddělena informace o hranách od vlnkových koeficientů.
• JPEG 2000 – Systém pro kódování obrazu je definuje transformace pomocí liftingu (ztrátová i bezeztrátová komprese).
• Red-Black Wavelets – Neseparabilní obrazová transformace, ve které je lifting aplikován nad mřížkou quincunx namísto klasického separabilního rozkladu.
• Celočíselná rychlá Fourierova transformace (IntFFT) – reverzibilní (integer-to-integer) forma rychlé Fourierovy transformace.

Příklad

Standard JPEG 2000 definuje reverzibilní aproximaci transformace s vlnkou CDF 5/3, která mapuje celá čísla na celá čísla, pomocí schématu lifting následovně.

${\displaystyle x(2n+1)=x(2n+1)-\left\lfloor {\frac {x(2n)+x(2n+2)}{2}}\right\rfloor }$ (predikce)

${\displaystyle x(2n)=x(2n)+\left\lfloor {\frac {x(2n-1)+x(2n+1)+2}{4}}\right\rfloor }$ (aktualizace)

Po těchto dvou krocích budou sudé vzorky ${\displaystyle x(2n)}$ odpovídat podpásmu L a liché vzorky ${\displaystyle x(2n+1)}$ podpásmu H.

Související články

• diskrétní vlnková transformace
• Feistelova šifra – šifrovací algoritmus využívající podobné schéma

Reference

• SWELDENS, Wim. The lifting scheme: A custom-design construction of biorthogonal wavelets. Applied and Computational Harmonic Analysis. 1996, roč. 3, čís. 2, s. 186–200. Dostupné online. 
• DAUBECHIES, Ingrid; SWELDENS, Wim. Factoring Wavelet Transforms into Lifting Steps. Journal of Fourier Analysis and Applications. 1998, roč. 4, čís. 3, s. 245–267. Dostupné online. 
• MALLAT, Stéphane. A Wavelet Tour of Signal Processing: The Sparse Way. With contributions from Gabriel Peyré. 3. vyd. [s.l.]: Academic Press, 1998. xx, 805 s. Dostupné online. ISBN 9780123743701. 

Externí odkazy

• Lifting Scheme Archivováno 3. 1. 2017 na Wayback Machine. – stručný popis algoritmu pro faktorizaci