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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Second_generation_wavelet_transform.svg/220px-Second_generation_wavelet_transform.svg.png)
Jakákoli DWT s konečnými filtry může být faktorizována (např. pomocí Eukleidova algoritmu) do posloupností párů predikčních a aktualizačních konvolučních operátorů. Každý predikční operátor odpovídá filtru a každý aktualizační operátor filtru .
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 (). Následuje sekvence predikcí a aktualizací pomocí výše definovaných operátorů. Predikce v kroku se počítá nad vzorky a její výsledek se odečte od , čímž vzniká . Následná aktualizace s počítá nad upravenými a přičte se k , čímž vzniká . Výsledkem jsou prokládané koeficienty podpásem L (odpovídá ) a H (odpovídá ) diskrétní vlnkové transformace.
Využití
editovat- 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
editovatStandard JPEG 2000 definuje reverzibilní aproximaci transformace s vlnkou CDF 5/3, která mapuje celá čísla na celá čísla, pomocí schématu lifting následovně.
- (predikce)
- (aktualizace)
Po těchto dvou krocích budou sudé vzorky odpovídat podpásmu L a liché vzorky podpásmu H.
Související články
editovat- diskrétní vlnková transformace
- Feistelova šifra – šifrovací algoritmus využívající podobné schéma
Reference
editovat- 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
editovat- Lifting Scheme Archivováno 3. 1. 2017 na Wayback Machine. – stručný popis algoritmu pro faktorizaci