Cohen – Daubechies – Feauveau wavelet - Cohen–Daubechies–Feauveau wavelet - Wikipedia

Příklad 2D vlnkové transformace, která se používá v JPEG2000

Cohen – Daubechies – Feauveau vlnky jsou rodina biortogonální vlnky který si oblíbil Ingrid Daubechies.^[1]^[2] Ty nejsou stejné jako ortogonální Vlnky daubechies, a také nejsou příliš podobné tvarem a vlastnostmi. Jejich konstrukční myšlenka je však stejná.

The JPEG 2000 komprese standard používá biortogonální vlnovku LeGall-Tabatabai (LGT) 5/3 (vyvinutý D. Le Gall a Ali J. Tabatabai)^[3]^[4]^[5] pro bezztrátová komprese a vlnku CDF 9/7 pro ztrátová komprese.

Vlastnosti

The primární generátor je B-spline pokud jednoduchá faktorizace ${ displaystyle q _ { text {prim}} (X) = 1}$ (viz níže).
The duální generátor má nejvyšší možný počet faktorů hladkosti pro svou délku.
Všechny generátory a vlnky v této rodině jsou symetrické.

Konstrukce

Pro každé kladné celé číslo A existuje jedinečný polynom ${ displaystyle Q_ {A} (X)}$ stupně A - 1 uspokojující totožnost

{ displaystyle left (1 - { frac {X} {2}} right) ^ {A} , Q_ {A} (X) + left ({ frac {X} {2}} right ) ^ {A} , Q_ {A} (2-X) = 1.}

Jedná se o stejný polynom, jaký se používá při konstrukci Vlnky daubechies. Ale místo spektrální faktorizace se zde snažíme faktorovat

{ displaystyle Q_ {A} (X) = q _ { text {prim}} (X) , q _ { text {dual}} (X),}

kde faktory jsou polynomy se skutečnými koeficienty a konstantním koeficientem 1. Pak

{ displaystyle a _ { text {prim}} (Z) = 2Z ^ {d} , vlevo ({ frac {1 + Z} {2}} vpravo) ^ {A} , q _ { text {prim}} vlevo (1 - { frac {Z + Z ^ {- 1}} {2}} vpravo)}

a

{ displaystyle a _ { text {dual}} (Z) = 2Z ^ {d} , vlevo ({ frac {1 + Z} {2}} vpravo) ^ {A} , q _ { text {dual}} left (1 - { frac {Z + Z ^ {- 1}} {2}} right)}

tvoří biortogonální pár škálovacích sekvencí. d je celé číslo, které se používá k vycentrování symetrických sekvencí na nulu nebo k vytvoření kauzálních odpovídajících samostatných filtrů.

V závislosti na kořenech ${ displaystyle Q_ {A} (X)}$ , může jich být až ${ displaystyle 2 ^ {A-1}}$ různé faktorizace. Jednoduchá faktorizace je ${ displaystyle q _ { text {prim}} (X) = 1}$ a ${ displaystyle q _ { text {dual}} (X) = Q_ {A} (X)}$ , pak je primární funkcí změny měřítka B-spline řádu A - 1. Pro A = 1 získá ortogonální Haarova vlnka.

Tabulky koeficientů

Cohen – Daubechies – Feauveau wavelet 5/3 použitý ve standardu JPEG 2000

Pro A = 2 takto získá LeGall 5/3-wavelet:

A	Q_A(X)	q_prim(X)	q_dvojí(X)	A_prim(Z)	A_dvojí(Z)
2	${ displaystyle 1 + X}$	1	${ displaystyle 1 + X}$	${ displaystyle { frac {1} {2}} (1 + Z) ^ {2} , Z}$	${ displaystyle { frac {1} {2}} (1 + Z) ^ {2} , vlevo (- { frac {1} {2}} + 2 , Z - { frac {1} {2}} , Z ^ {2} vpravo)}$

Pro A = 4 jeden získá Vlnka 9/7-CDF. Jeden dostane ${ displaystyle Q_ {4} (X) = 1 + 2X + { tfrac {5} {2}} X ^ {2} + { tfrac {5} {2}} X ^ {3}}$ , tento polynom má přesně jeden skutečný kořen, je tedy produktem lineárního faktoru ${ displaystyle 1-cX}$ a kvadratický faktor. Koeficient C, což je inverzní hodnota kořene, má přibližnou hodnotu −1,4603482098.

A	Q_A(X)	q_prim(X)	q_dvojí(X)
4	${ displaystyle 1 + 2X + { tfrac {5} {2}} X ^ {2} + { tfrac {5} {2}} X ^ {3}}$	${ displaystyle 1-cX}$	${ displaystyle 1+ (c + 2) X + (c ^ {2} + 2c + { tfrac {5} {2}}) X ^ {2}}$

Pro koeficienty centrovaného měřítka a waveletových sekvencí získáme číselné hodnoty ve formě vhodné pro implementaci

k	Analýza dolní propusti (1/2 A_dvojí)	Analýza horního filtru (b_dvojí)	Syntetický dolní propust (A_prim)	Syntetický horní propust (1/2 b_prim)
−4	0.026748757411	0	0	0.026748757411
−3	−0.016864118443	0.091271763114	−0.091271763114	0.016864118443
−2	−0.078223266529	−0.057543526229	−0.057543526229	−0.078223266529
−1	0.266864118443	−0.591271763114	0.591271763114	−0.266864118443
0	0.602949018236	1.11508705	1.11508705	0.602949018236
1	0.266864118443	−0.591271763114	0.591271763114	−0.266864118443
2	−0.078223266529	−0.057543526229	−0.057543526229	−0.078223266529
3	−0.016864118443	0.091271763114	−0.091271763114	0.016864118443
4	0.026748757411	0	0	0.026748757411

Číslování

Pro vlnky rodiny CDF existují dvě souběžná schémata číslování:

počet faktorů hladkosti dolních propustí nebo ekvivalentně počet mizející okamžiky filtrů horní propusti, např. „2, 2“;
velikosti dolnoprůchodových filtrů nebo ekvivalentně velikosti hornoprůchodových filtrů, např. „5, 3“.

První číslování bylo použito v Daubechiesově knize Deset přednášek o vlnkách. Ani jedno z těchto číslování není jedinečné. Počet mizejících momentů neříká o zvolené faktorizaci. Banka filtrů s velikostí filtrů 7 a 9 může mít 6 a 2 mizející momenty při použití triviální faktorizace nebo 4 a 4 mizející momenty, jak je tomu u vlnky JPEG 2000. Stejná vlnka může být proto označována jako „CDF 9/7“ (na základě velikostí filtru) nebo „biortogonální 4, 4“ (na základě úběžných momentů). Podobně lze tedy stejnou vlnu označovat jako „CDF 5/3“ (na základě velikostí filtru) nebo „biortogonální 2, 2“ (na základě úběžných momentů).

Zvedací rozklad

Pro triviálně faktorizované filtrační banky a zvedání rozkladu lze výslovně uvést.^[6]

Sudý počet faktorů hladkosti

Nechat ${ displaystyle n}$ je počet faktorů hladkosti ve filtru dolní propusti B-spline, který musí být sudý.

Pak definujte rekurzivně

{ displaystyle { begin {aligned} a_ {0} & = { frac {1} {n}}, a_ {m} & = { frac {1} {(n ^ {2} -4 cdot m ^ {2}) cdot a_ {m-1}}}. end {zarovnáno}}}

Zvedací filtry jsou

{ displaystyle s_ {m} (z) = a_ {m} cdot (2 cdot m + 1) cdot (1 + z ^ {(- 1) ^ {m}}).}

Průběžné výsledky zvedání jsou přesvědčivé

{ displaystyle { begin {zarovnáno} x _ {- 1} (z) & = z, x_ {0} (z) & = 1, x_ {m + 1} (z) & = x_ {m -1} (z) + a_ {m} cdot (2 cdot m + 1) cdot (z + z ^ {- 1}) cdot z ^ {(- 1) ^ {m}} cdot x_ {m} (z), end {zarovnáno}}}

což vede k

{ displaystyle x_ {n / 2} (z) = 2 ^ {- n / 2} cdot (1 + z) ^ {n} cdot z ^ {n / 2 { bmod {2}} - n / 2}.}

Filtry ${ displaystyle x_ {n / 2}}$ a ${ displaystyle x_ {n / 2-1}}$ tvoří CDF-n, 0 filtrační banka.

Zvláštní počet faktorů hladkosti

Teď, pojďme ${ displaystyle n}$ být zvláštní.

Pak definujte rekurzivně

{ displaystyle { begin {aligned} a_ {0} & = { frac {1} {n}}, a_ {m} & = { frac {1} {(n ^ {2} - (2 cdot m-1) ^ {2}) cdot a_ {m-1}}}. end {zarovnáno}}}

Zvedací filtry jsou

{ displaystyle s_ {m} (z) = a_ {m} cdot ((2 cdot m + 1) + (2 cdot m-1) cdot z) / z ^ {m { bmod {2} }}.}

Závěrečné jsou průběžné výsledky zvedání

{ displaystyle { begin {zarovnáno} x _ {- 1} (z) & = z, x_ {0} (z) & = 1, x_ {1} (z) & = x _ {- 1} (z) + a_ {0} cdot x_ {0} (z), x_ {m + 1} (z) & = x_ {m-1} (z) + a_ {m} cdot ((2 cdot m + 1) cdot z + (2 cdot m-1) cdot z ^ {- 1}) cdot z ^ {(- 1) ^ {m}} cdot x_ {m} (z), end {zarovnáno}}}

což vede k

{ displaystyle x _ {(n + 1) / 2} (z) sim (1 + z) ^ {n},}

kde zanedbáváme překlad a konstantní faktor.

Filtry ${ displaystyle x _ {(n + 1) / 2}}$ a ${ displaystyle x _ {(n-1) / 2}}$ tvoří CDF-n, 1 filtrační banka.

Aplikace

Ke kompresi byly použity vlnky Cohen – Daubechies – Feauveau a další biortogonální vlnky otisk prstu vyhledá FBI.^[7] Standard pro kompresi otisků prstů tímto způsobem vyvinuli Tom Hopper (FBI), Jonathan Bradley (Národní laboratoř Los Alamos ) a Chris Brislawn (Národní laboratoř Los Alamos).^[7] Použitím waveletů lze dosáhnout kompresního poměru kolem 20 ku 1, což znamená, že obraz 10 MB může být snížen na pouhých 500 kB, zatímco stále prochází testy rozpoznávání.^[7]

externí odkazy

Reference

^ Cohen, A .; Daubechies, I .; Feauveau, J.-C. (1992). "Biortogonální základny kompaktně podporovaných waveletů". Sdělení o čisté a aplikované matematice. 45 (5): 485–560. doi:10,1002 / cpa. 3160450502.
^ Daubechies, Ingrid (1992). Deset přednášek o vlnkách. SIAM. doi:10.1137/1.9781611970104. ISBN 978-0-89871-274-2.
^ Sullivan, Gary (8. – 12. Prosince 2003). "Obecné charakteristiky a konstrukční úvahy pro kódování dočasného subpásmového videa". ITU-T. Skupina odborníků na kódování videa. Citováno 13. září 2019.
^ Bovik, Alan C. (2009). Základní průvodce zpracováním videa. Akademický tisk. p. 355. ISBN 9780080922508.
^ Gall, D. Le; Tabatabai, Ali J. (1988). "Částečné pásmové kódování digitálních obrázků pomocí symetrických filtrů s krátkými jádry a technik aritmetického kódování". ICASSP-88., Mezinárodní konference o akustice, řeči a zpracování signálu: 761–764 vol.2. doi:10.1109 / ICASSP.1988.196696. S2CID 109186495.
^ Thielemann, Henning (2006). „oddíl 3.2.4“. Optimálně přizpůsobené vlnky (Disertační práce).
^ ^A ^b ^C Cipra, Barry Arthur (1994). Co se děje v Mathematical Sciences (Vol. 2) Parlez-vous Wavelets?. Americká matematická společnost. ISBN 978-0821889985.

[1] Cohen, A .; Daubechies, I .; Feauveau, J.-C. (1992). "Biortogonální základny kompaktně podporovaných waveletů". Sdělení o čisté a aplikované matematice. 45 (5): 485–560. doi:10,1002 / cpa. 3160450502.

[2] Daubechies, Ingrid (1992). Deset přednášek o vlnkách. SIAM. doi:10.1137/1.9781611970104. ISBN 978-0-89871-274-2.

[3] Sullivan, Gary (8. – 12. Prosince 2003). "Obecné charakteristiky a konstrukční úvahy pro kódování dočasného subpásmového videa". ITU-T. Skupina odborníků na kódování videa. Citováno 13. září 2019.

[4] Bovik, Alan C. (2009). Základní průvodce zpracováním videa. Akademický tisk. p. 355. ISBN 9780080922508.

[5] Gall, D. Le; Tabatabai, Ali J. (1988). "Částečné pásmové kódování digitálních obrázků pomocí symetrických filtrů s krátkými jádry a technik aritmetického kódování". ICASSP-88., Mezinárodní konference o akustice, řeči a zpracování signálu: 761–764 vol.2. doi:10.1109 / ICASSP.1988.196696. S2CID 109186495.

[6] Thielemann, Henning (2006). „oddíl 3.2.4“. Optimálně přizpůsobené vlnky (Disertační práce).

[cipra94-7] A ^b ^C Cipra, Barry Arthur (1994). Co se děje v Mathematical Sciences (Vol. 2) Parlez-vous Wavelets?. Americká matematická společnost. ISBN 978-0821889985.

[1]

[2]

[3]

[4]

[5]

[6]

[7]