Rychlá waveletová transformace - Fast wavelet transform

Fast Wavelet Transform je matematický algoritmus navržen tak, aby otočit průběh nebo signál v časové oblasti do posloupnosti koeficientů založených na ortogonální bázi malých konečných vln nebo vlnky . Transformaci lze snadno rozšířit na vícerozměrné signály, jako jsou obrázky, kde je časová doména nahrazena doménou prostoru. Tento algoritmus zavedl v roce 1989 Stéphane Mallat .

Má jako teoretický základ zařízení konečně generované ortogonální multirezoluční analýzy (MRA). Z uvedených podmínek se vybere vzorkovací stupnice J se vzorkovací frekvencí 2 ^J na jednotkový interval a promítne daný signál f do prostoru ; teoreticky výpočtem skalárních součinů${\ displaystyle V_ {J}}$

${\ displaystyle s_ {n} ^ {(J)}: = 2 ^ {J} \ langle f (t), \ phi (2 ^ {J} tn) \ rangle,}$

kde je škálovací funkce vybrané vlnkové transformace; v praxi jakýmkoli vhodným postupem vzorkování za podmínky, že je signál vysoce převzorkován, tak ${\ displaystyle \ phi}$

${\ displaystyle P_ {J} [f] (x): = \ součet _ {n \ v \ mathbb {Z}} s_ {n} ^ {(J)} \, \ phi (2 ^ {J} xn) }$

je ortogonální projekce nebo alespoň nějaká dobrá aproximace původního signálu v . ${\ displaystyle V_ {J}}$

MRA se vyznačuje svou škálovací sekvencí

${\ displaystyle a = (a _ {- N}, \ tečky, a_ {0}, \ tečky, a_ {N})}$nebo, jako Z-transformace ,${\ displaystyle a (z) = \ součet _ {n = -N} ^ {N} a_ {n} z ^ {- n}}$

a jeho vlnková sekvence

${\ displaystyle b = (b _ {- N}, \ tečky, b_ {0}, \ tečky, b_ {N})}$ nebo ${\ displaystyle b (z) = \ součet _ {n = -N} ^ {N} b_ {n} z ^ {- n}}$

(některé koeficienty mohou být nulové). Umožňují vypočítat vlnkové koeficienty , alespoň v určitém rozsahu k = M, ..., J-1 , aniž by bylo nutné aproximovat integrály v odpovídajících skalárních součinech. Místo toho lze přímo pomocí konvolučních a decimačních operátorů vypočítat tyto koeficienty z první aproximace . ${\ displaystyle d_ {n} ^ {(k)}}$${\ displaystyle s ^ {(J)}}$

Předat DWT

Jeden počítá rekurzivně , počínaje sekvencí koeficientů a odpočítáváním od k = J-1 do některých M <J , ${\ displaystyle s ^ {(J)}}$

jednorázová aplikace banky vlnkových filtrů s filtry g = a ^* , h = b ^*

${\ displaystyle s_ {n} ^ {(k)}: = {\ frac {1} {2}} \ součet _ {m = -N} ^ {N} a_ {m} s_ {2n + m} ^ { (k + 1)}}$ nebo ${\ displaystyle s ^ {(k)} (z): = (\ downarrow 2) (a ^ {*} (z) \ cdot s ^ {(k + 1)} (z))}$

a

${\ displaystyle d_ {n} ^ {(k)}: = {\ frac {1} {2}} \ součet _ {m = -N} ^ {N} b_ {m} s_ {2n + m} ^ { (k + 1)}}$nebo ,${\ displaystyle d ^ {(k)} (z): = (\ downarrow 2) (b ^ {*} (z) \ cdot s ^ {(k + 1)} (z))}$

pro k = J-1, J-2, ..., M a vše . V notaci Z-transformace: ${\ displaystyle n \ in \ mathbb {Z}}$

rekurzivní aplikace banky filtrů

• Převzorkování operátor snižuje nekonečnou posloupnost, danou jeho Z-transformace , který je jednoduše série Laurent , na posloupnosti koeficientů s ještě indexů .${\ displaystyle (\ downarrow 2)}$${\ displaystyle (\ downarrow 2) (c (z)) = \ součet _ {k \ v \ mathbb {Z}} c_ {2k} z ^ {- k}}$
• Úlohy označené Laurent-polynomiální označuje adjoint filtr , má časově reversní adjoint koeficientů . (Adjunktem reálného čísla je číslo samotné, komplexního čísla jeho konjugát, reálné matice transponovaná matice, komplexní matice jeho hermitovské adjoint).${\ displaystyle a ^ {*} (z)}$${\ displaystyle a ^ {*} (z) = \ součet _ {n = -N} ^ {N} a _ {- n} ^ {*} z ^ {- n}}$
• Násobení je polynomiální násobení, které je ekvivalentní konvoluci sekvencí koeficientů.

Z toho vyplývá, že

${\ displaystyle P_ {k} [f] (x): = \ součet _ {n \ v \ mathbb {Z}} s_ {n} ^ {(k)} \, \ phi (2 ^ {k} xn) }$

je ortogonální projekce původního signálu f nebo alespoň první aproximace do podprostoru , tj. se vzorkovací frekvencí 2 ^k na jednotku intervalu. Rozdíl oproti první aproximaci je dán vztahem ${\ displaystyle P_ {J} [f] (x)}$ ${\ displaystyle V_ {k}}$

${\ displaystyle P_ {J} [f] (x) = P_ {k} [f] (x) + D_ {k} [f] (x) + \ tečky + D_ {J-1} [f] (x )}$,

kde jsou signály rozdílu nebo detailů počítány z koeficientů detailu jako

${\ displaystyle D_ {k} [f] (x): = \ součet _ {n \ v \ mathbb {Z}} d_ {n} ^ {(k)} \, \ psi (2 ^ {k} xn) }$,

s označením mateřské vlnky waveletové transformace. ${\ displaystyle \ psi}$

Inverzní DWT

Vzhledem k posloupnosti koeficientů pro některé M <J a všechny rozdílné posloupnosti , k = M, ..., J-1 , se počítá rekurzivně ${\ displaystyle s ^ {(M)}}$${\ displaystyle d ^ {(k)}}$

${\ displaystyle s_ {n} ^ {(k + 1)}: = \ součet _ {k = -N} ^ {N} a_ {k} s_ {2n-k} ^ {(k)} + \ součet _ {k = -N} ^ {N} b_ {k} d_ {2n-k} ^ {(k)}}$ nebo ${\ Displaystyle s ^ {(k + 1)} (z) = a (z) \ cdot (\ uparrow 2) (s ^ {(k)} (z)) + b (z) \ cdot (\ uparrow 2 ) (d ^ {(k)} (z))}$

pro k = J-1, J-2, ..., M a vše . V notaci Z-transformace: ${\ displaystyle n \ in \ mathbb {Z}}$

• Operátor Převzorkování vytváří nulový injekční otvory uvnitř dané sekvenci. To znamená, že každý druhý prvek výsledné sekvence je prvkem dané sekvence, každý druhý druhý prvek je nula nebo . Tento lineární operátor je v Hilbertově prostoru adjunktem k operátoru převzorkování .${\ displaystyle (\ uparrow 2)}$${\ displaystyle (\ uparrow 2) (c (z)): = \ součet _ {n \ v \ mathbb {Z}} c_ {n} z ^ {- 2n}}$ ${\ displaystyle \ ell ^ {2} (\ mathbb {Z}, \ mathbb {R})}$${\ displaystyle (\ downarrow 2)}$

Viz také

• Zvedací schéma

Reference

• SG Mallat „Teorie multirezolučního rozkladu signálu: reprezentace waveletů“ IEEE Transaction on Pattern Analysis and Machine Intelligence, sv. 2, č. 7. července 1989.
• AN Akansu Multiplierless Suboptimal PR-QMF Design Proc. SPIE 1818, Vizuální komunikace a zpracování obrazu, s. 723, listopad 1992
• AN Akansu Multiplierless 2-band Perfect Reconstruction Quadrature Mirror Filter (PR-QMF) Banks US Patent 5420 891, 1995
• AN Akansu multiplikátorové PR kvadraturní zrcadlové filtry pro subpásmové kódování obrazu IEEE Trans. Zpracování obrazu, str. 1359, září 1996
• MJ Mohlenkamp, MC Pereyra Wavelets, jejich přátelé a co pro vás mohou udělat (EMS 2008) str. 38
• BB Hubbard Svět podle waveletů: Příběh matematické techniky při výrobě (1998 Peters) str. 184
• SG Mallat A Wavelet Tour of Signal Processing (1999 Academic Press) str. 255
• A. Teolis Výpočetní zpracování signálu s vlnkami (1998 Birkhäuser) str. 116
• Y. Nievergelt Wavelets Made Easy (1999 Springer) str. 95

Další čtení

G. Beylkin, R. Coifman, V. Rokhlin, „Rychlé vlnkové transformace a numerické algoritmy“ Comm. Pure Appl. Matematika. , 44 (1991), str. 141–183