Cohen–Daubechies–Feauveau wavelet

Ett exempel på 2D wavelet-transform som används i JPEG2000

Cohen–Daubechies–Feauveau wavelets är en familj av biortogonala wavelets som gjordes populär av Ingrid Daubechies . Dessa är inte samma som de ortogonala Daubechies-vågorna och inte heller särskilt lika i form och egenskaper. Deras konstruktionsidé är dock densamma.

JPEG 2000- kompressionsstandarden använder den biortogonala Le Gall–Tabatabai (LGT) 5/3 wavelet (utvecklad av D. Le Gall och Ali J. Tabatabai) för förlustfri komprimering och en CDF 9/7 wavelet för förlustfri komprimering .

Egenskaper

Primalgeneratorn är en B-spline om den enkla faktoriseringen $q_{\text{prim}}(X)=1$ (se nedan) väljs.
Den dubbla generatorn har det högsta möjliga antalet jämnhetsfaktorer för sin längd.
Alla generatorer och wavelets i denna familj är symmetriska.

Konstruktion

För varje positivt heltal A finns det ett unikt polynom $Q_{A}(X)$ av grad A − 1 som uppfyller identiteten

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

Detta är samma polynom som används i konstruktionen av Daubechies wavelets . Men istället för en spektral faktorisering försöker vi här faktorisera

Q_{A}(X)=q_{\text{prim}}(X)\,q_{\text{dual}}( X),

där faktorerna är polynom med reella koefficienter och konstant koefficient 1. Då

a_{\text{prim}}(Z)=2Z^{d}\, \left({\frac {1+Z}{2}}\right)^{A}\,q_{\text{prim}}\left(1-{\frac {Z+Z^{-1}} {2}}\right)

och

a_{\text{dual}}(Z)=2Z^{d}\, \left({\frac {1+Z}{2}}\right)^{A}\,q_{\text{dual}}\left(1-{\frac {Z+Z^{-1}} {2}}\right)

bildar ett biortogonalt par av skalningssekvenser. d är något heltal som används för att centrera de symmetriska sekvenserna vid noll eller för att göra motsvarande diskreta filter kausala.

Beroende på rötterna till $Q_{A}(X)$ , kan det finnas upp till $2^{A-1}$ olika faktoriseringar. En enkel faktorisering är $q_{\text{prim}}(X)=1$ och $q_{\text{dual} }(X)=Q_{A}(X)$ , då är den primära skalningsfunktionen B-spline av ordningen A − 1. För A = 1 får man den ortogonala Haar-vågen .

Tabeller över koefficienter

Cohen–Daubechies–Feauveau wavelet 5/3 används i JPEG 2000 standard

För A = 2 får man på detta sätt LeGall 5/3-wavelet :

A	Q _A ( X )	q _prim ( X )	q _dubbel ( X )	a _prim ( Z )	en _dubbel ( Z )
2	$1+X$	1	$1+X$	${\frac {1}{2}}(1+Z)^{2}\,Z$	${\frac {1}{2}}(1+Z)^{2}\,\left(-{ \frac {1}{2}}+2\,Z-{\frac {1}{2}}\,Z^{2}\right)$

För A = 4 får man 9/7-CDF-vågen . Man får $Q_{4}(X)=1+2X+{\tfrac {5}{2}}X^{2 }+{\tfrac {5}{2}}X^{3}$ , detta polynom har exakt en reell rot, så det är produkten av en linjär faktor $1-cX$ och en kvadratisk faktor. Koefficienten c , som är inversen av roten, har ett ungefärligt värde på −1,4603482098.

A	Q _A ( X )	q _prim ( X )	q _dubbel ( X )
4	$1+2X+{\tfrac {5}{2}}X^{2}+{\tfrac {5}{2}}X^{3 }$	$1-cX$	$1+(c+2)X+(c^{2}+2c+{\tfrac {5}{2}} )X^{2}$

För koefficienterna för den centrerade skalningen och wavelet-sekvenserna får man numeriska värden i en implementeringsvänlig form

k	Analys lågpassfilter (1/2 en _dubbel )	Analys högpassfilter ( b _dubbel )	Syntes lågpassfilter ( en _prim )	Syntes högpassfilter (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

Numrering

Det finns två överensstämmande numreringsscheman för wavelets av CDF-familjen:

antalet jämnhetsfaktorer för lågpassfiltren, eller ekvivalent antalet försvinnande moment för högpassfiltren, t.ex. "2, 2";
storlekarna på lågpassfiltren, eller ekvivalent storleken på högpassfiltren, t.ex. "5, 3".

Den första numreringen användes i Daubechies bok Tio föreläsningar om vågor . Ingen av dessa numrering är unik. Antalet försvinnande ögonblick berättar inte om den valda faktoriseringen. En filterbank med filterstorlekarna 7 och 9 kan ha 6 och 2 försvinnande moment när man använder trivial faktorisering, eller 4 och 4 försvinnande moment som det är fallet för JPEG 2000 wavelet. Samma wavelet kan därför hänvisas till som "CDF 9/7" (baserat på filterstorlekarna) eller "biortogonal 4, 4" (baserat på försvinnningsmomenten). På liknande sätt kan samma wavelet därför hänvisas till som "CDF 5/3" (baserat på filterstorlekarna) eller "biortogonal 2, 2" (baserat på försvinnningsmomenten).

Lyftande sönderdelning

För de trivialt faktoriserade filterbankerna kan en lyftande sönderdelning uttryckligen anges.

Jämnt antal jämnhetsfaktorer

Låt $n$ vara antalet jämnhetsfaktorer i B-spline-lågpassfiltret, som ska vara jämnt.

Definiera sedan rekursivt

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

Lyftfiltren är

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

Avgörande är de mellanliggande resultaten av lyftet

{\begin{aligned}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{aligned}}

som leder till

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

Filtren $x_{n/2}$ och $x_{n/2-1}$ utgör CDF- n ,0 filterbanken.

Udda antal jämnhetsfaktorer

Låt nu $n$ vara udda.

Definiera sedan rekursivt

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

Lyftfiltren är

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

Avgörande är de mellanliggande resultaten av lyftet

{\begin{aligned }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{aligned}}

som leder till

x_{(n+1)/2}(z)\sim (1+z)^{n},

där vi försummar översättningen och den konstanta faktorn.

Filtren $x_{(n+1)/2}$ och $x_{(n-1)/2}$ utgör CDF:n - n ,1 filterbank.

Ansökningar

Cohen–Daubechies–Feauveau wavelet och andra biortogonala wavelets har använts för att komprimera fingeravtrycksskanningar för FBI . En standard för att komprimera fingeravtryck på detta sätt utvecklades av Tom Hopper (FBI), Jonathan Bradley ( Los Alamos National Laboratory ) och Chris Brislawn (Los Alamos National Laboratory). Genom att använda wavelets kan ett komprimeringsförhållande på cirka 20 till 1 uppnås, vilket innebär att en 10 MB bild kan reduceras till så lite som 500 kB samtidigt som den klarar igenkänningstest.

externa länkar

^ Cohen, A.; Daubechies, I.; Feauveau, J.-C. (1992). "Biortogonala baser av kompakta vågor". Meddelanden om ren och tillämpad matematik . 45 (5): 485–560. doi : 10.1002/cpa.3160450502 .
^ Daubechies, Ingrid (1992). Tio föreläsningar om wavelets . SIAM. doi : 10.1137/1.9781611970104 . ISBN 978-0-89871-274-2 .
^ Sullivan, Gary (8–12 december 2003). "Allmänna egenskaper och designöverväganden för temporal subbandsvideokodning" . ITU-T . Expertgrupp för videokodning . Hämtad 13 september 2019 .
^ Bovik, Alan C. (2009). Den grundläggande guiden till videobearbetning . Akademisk press . sid. 355. ISBN 9780080922508 .
^ Gall, D. Le; Tabatabai, Ali J. (1988). "Subbandskodning av digitala bilder med symmetriska korta kärnfilter och aritmetiska kodningstekniker". ICASSP-88., Internationell konferens om akustik, tal och signalbehandling : 761–764 vol.2. doi : 10.1109/ICASSP.1988.196696 . S2CID 109186495 .
^ Thielemann, Henning (2006). "avsnitt 3.2.4" . Optimalt matchade wavelets (PhD-avhandling).
^ ^a ^b ^c Cipra, Barry Arthur (1994). Vad händer i de matematiska vetenskaperna (Vol. 2) Parlez-vous Wavelets? . American Mathematical Society. ISBN 978-0821889985 .

[1] Cohen, A.; Daubechies, I.; Feauveau, J.-C. (1992). "Biortogonala baser av kompakta vågor". Meddelanden om ren och tillämpad matematik . 45 (5): 485–560. doi : 10.1002/cpa.3160450502 .

[2] Daubechies, Ingrid (1992). Tio föreläsningar om wavelets . SIAM. doi : 10.1137/1.9781611970104 . ISBN 978-0-89871-274-2 .

[3] Sullivan, Gary (8–12 december 2003). "Allmänna egenskaper och designöverväganden för temporal subbandsvideokodning" . ITU-T . Expertgrupp för videokodning . Hämtad 13 september 2019 .

[4] Bovik, Alan C. (2009). Den grundläggande guiden till videobearbetning . Akademisk press . sid. 355. ISBN 9780080922508 .

[5] Gall, D. Le; Tabatabai, Ali J. (1988). "Subbandskodning av digitala bilder med symmetriska korta kärnfilter och aritmetiska kodningstekniker". ICASSP-88., Internationell konferens om akustik, tal och signalbehandling : 761–764 vol.2. doi : 10.1109/ICASSP.1988.196696 . S2CID 109186495 .

[6] Thielemann, Henning (2006). "avsnitt 3.2.4" . Optimalt matchade wavelets (PhD-avhandling).

[cipra94-7] Cipra, Barry Arthur (1994). Vad händer i de matematiska vetenskaperna (Vol. 2) Parlez-vous Wavelets? . American Mathematical Society. ISBN 978-0821889985 .