Schéma zvedání

Lifting Scheme je technika jak pro vlnkový design , tak pro diskrétní vlnkové transformace . Co je skutečně nutné, je zkombinovat tyto kroky a navrhnout vlnky paralelně s vlnkovou transformací. Toto se nazývá vlnková transformace druhé generace . Tuto technologii poprvé navrhl Wim Sweldens . Při diskrétní vlnkové transformaci je na jeden signál aplikováno několik filtrů. Ve zvedacím obvodu je signál rozdělen jako zip. Poté se se signálem provede série naskládaných konvolučních operací .

Obecná myšlenka

Nechť je signál . Lze to rozdělit na signály a nějaký filtr s decimací vzorků dvakrát. Obecně platí, že signály a jsou do značné míry vzájemně korelovány, takže nemá smysl přenášet oba signály, můžete přenášet jeden ze signálů ( ) a na jeho základě provést predikci druhého signálu pomocí filtru . Prostorová korelace je tedy do určité míry odstraněna. Existují však problémy ve frekvenční oblasti, protože signál se získává jednoduchou decimací vzorku. Aktuální průměr signálů a neodpovídá. K odstranění tohoto je zaveden druhý filtr , který aktualizuje signál odpovídajícím způsobem na základě ( ). $F$ $L1$ $Y1$ $s$ $L1$ $Y1$ $L1$ $P$ $Y2=Y1-P(L1)$ $L1$ $L1$ $F$ $U$ $L1$ $Y2$ $L2=L1+U(Y2)$

Příklad

Vezměme si signál z prvků . Jako filtr bereme jednoduché rozdělení na sudé a liché vzorky: $F$ $x_{i}$

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

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

Predikcí signálu může být například statistický průměr sousedních prvků $Y1$ $L1$

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

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

Pro upřesnění signálu přidejte polovinu průměru předchozí a následující hodnoty . V tomto případě bude více konzistentní se signálem než . $L1$ $Y2$ $L2$ $F$ $L1$

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

resp.

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

Znát jak z a , je možné obnovit . $L2$ $Y2$ $U$ $P$ $S^{{-1}}$ $F$

Základy

Hlavní myšlenka liftingu je následující: pokud je pár filtrů doplňkový , pak pro jakýkoli filtr poskytuje pár , kde , také možnost úplného obnovení signálu. To samozřejmě platí i pro každý pár , kde . Platí i obrácené tvrzení: pokud se filtr nastaví a umožní vám zcela obnovit signál, pak existuje takový jedinečný filtr, pro který . Každá taková transformace banky filtrů (nebo odpovídající operace vlnkové transformace) se nazývá zvedací krok. Sekvence zdvihacích kroků se skládá ze střídavých zdvihů, to znamená, že po upevnění dolní propusti a výměně horní propusti se v dalším kroku zafixuje horní propust a vymění se dolní propust. Postupné kroky ve stejném směru lze kombinovat. $(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)$

Vlastnosti

Bezztrátové zotavení.
- Každá transformace schématu zdvihu může být obrácena.
- Každou sadu plně rekonstrukčních filtrů lze rozdělit na zdvihací kroky pomocí Euklidova algoritmu .
- To znamená, že "rozdělitelná zvedací sada filtrů" a "plně reverzní zvedací sada filtrů" jsou totéž.
Jakékoli dvě plně rekonstrukční filtrační banky mohou být transformovány z jedné na druhou sadou kroků zvedání ( jsou -li a polyfázové matice se stejným diskriminantem, pak sekvence zvedání od do je stejná jako z „líné“ polyfázové matice do . ) $P$ $Q$ $P$ $Q$ $já$ $P^{-1}\cdot Q$
Zrychlete dvakrát. To je možné pouze proto, že zvedání lze provádět pouze s plně regeneračními filtračními sadami. To znamená, že lze říci, že lifting vybírá redundanci způsobenou možností úplného zotavení.
Na místě: Převod lze provést okamžitě v paměti vstupních dat, pouze pomocí ní a paměti pouze pro čtení.
Nelinearita: Konvoluční operace mohou být nahrazeny jakoukoli jinou. Pro úplné zotavení je pouze nutné, aby operace byly reverzibilní. Tímto způsobem mohou být chyby zaokrouhlení reprezentovány v konvoluci, což umožňuje bitově přesné zotavení. Navzdory tomu mohou nelinearity vést ke snížení numerické stability. To je třeba vzít v úvahu, pokud je převedený signál zpracováván jako při ztrátové kompresi.

Ačkoli každá rekonstruovaná banka filtrů může být reprezentována sadou zdvihacích kroků, obecný popis zdvihacích kroků není z popisu skupiny vlnek zřejmý. Nicméně například pro jednoduché případy vlnky Cohen-Daubechi-Fovo existuje přesný vzorec pro kroky zvedání. (viz související článek)

Generalizované zvedání

Generalized Lifting Scheme je odvozenina z Lifting Scheme . V tomto schématu jsou operace sčítání a odečítání převedeny na kroky aktualizace a predikce. Tyto kroky mohou být libovolné (reverzibilní) mapování, díky kterému je obvod obecnější.

Aplikace

Waveletová transformace s celými čísly: WAILI
Bitová přesná Fourierova transformace: Soontorn Oraintara, Ying-Jui Chen, Truong Q. Nguyen: Rychlá celočíselná Fourierova transformace
Návrh vlnek s daným stupněm filtrace a počtem mizejících momentů
Design vlnky pro daný model: Henning Thielemann: Optimálně sladěné vlnky
Použití diskrétní vlnkové transformace na JPEG2000

Viz také

Schéma Feistel v kryptologii využívá téměř stejnou myšlenku sdílení informací a střídání aplikace funkcí s přidáváním. To se používá pro symetrické ko- a dekódování ve schématech Feistel i Lifting.

Externí odkazy

Komplexní úvod do Fast Lifting Wavelet Transform
Ingrid Daubechies, Wim Sweldens: Factoring Wavelet se promění ve zvedací kroky
Lifting wavelet Kroky transformace: [1]
Zvedací schéma: Konstrukce vlnek druhé generace