Matematika | Felsőoktatás » Gegesy Zsombor - Waveletek az idősor elemzésben

Waveletek az id®sor elemzésben Diplomamunka Írta: Gegesy Zsombor Matematikus szak Témavezet®: Pröhle Tamás Eötvös Lóránd Tudományegyetem Természettudományi Kar 2006 Tartalomjegyzék 1. Kezdetek 1.1 3 Rövid Id®tartamú Fourier Analízis (STFT) . 3 2. Dení iók 4 3. Változó felbontás sorozat 5 3.1 Skála függvény meghatározása dilatá iós együtthatókból . 7 3.2 Különbség tér . 7 4. Wavelet függvény 8 4.1 Skála függvény Riesz bázisból . 4.2 Ortogonalitás dilatá iós együtthatókból 4.3 Ortogonalitás wavelet együtthatókból 9 . 10 . 10 4.4 Dilatá iós és wavelet együtthatók közötti összefüggés . 11 4.5 Wavelet függvény tulajdonságai . 12 4.6 Gyors Ortogonális Wavelet Transzformá ió 12 . 5. Biortogonális waveletek 14 5.1 Együtthatók közötti összefüggés

. 16 5.2 Cohen-Daube hies-Feauveau biortogonális wavelet konstruk ió . 16 5.21 17 5.3 Biortogonális spline waveletek . Tökéletes visszaállítás 5.31 . 17 Vetterli tétele . 18 6. Wavelet lifting 21 6.1 Polifázis reprezentá ió . 22 6.2 Lifting . 23 6.3 Laurent polinom felbontás . 25 6.4 Faktorizá iós algoritmus . 26 6.41 27 Haar wavelet felbontása 2 . 1. Kezdetek Az id®sor analízisnek eme területével el®ször Haar Alfréd foglalkozott a XX. század elején, ® vizsgálta a kés®bb Haar-waveletnek nevezett függvény ortogonalitását ([6℄) . Az 1930-as években Paul Levy használta a Haar-wavelet alapú bázist a Brown mozgás vizsgálatára. Az 1940-es években Gábor Dénes kutatásai során kerültek el® hasonló fogalmak. Ugyanis

függvények -avagy jelsorozatok vizsgálatakor olyan jellemz®ket akart vizsgálni, amelyek tranziensek, változóak Ekkor a Fourier transzformá iónak azon tulajdonsága, hogy a transzformá ió eredménye egy egy változós függvény, ami az intenzitást mutatja a frekvenia függvényében. Azaz, elvész az id® informá ió, azaz, nem lehet meghatározni, hogy egy adott esemény mikor is történt. Amennyiben a szignál tulajdonságai az id®vel nem változnak - ezt sta ionárius jelnek nevezik - akkor ez a hátrány nem jelent®s. De a legtöbb érdekl®désre számot tartó jel tartalmaz nem-sta ionárius, átmeneti jellemz®ket is, a szignál sodródhat, trendek gyelhet®k meg benne, vagy váratlan ugrásokat produkálhat. Ezek a jellegzetességek gyakran a legfontosabb részei a jelnek, s a Fourier analízis nem alkalmas a felderítésükre Ekkor egy olyan m¶velet, amely egy id®sorból egyszerre adja vissza az id® és frekvenia kap solatát, nagyon hasznos lenne. Erre a

problémára adnak megoldást, a Waveletek. 1.1 Rövid Id®tartamú Fourier Analízis (STFT)1 Az el®bb említett hiányosság kiküszöbölésére Gábor Dénes (1946) úgy adaptálta a Fourier transzformá iót, hogy az mindig Formálisan vett egy w (t) sak egy rövid szakaszát analizálja. 2 kompakt, sima függvényt , s vizsgálta az alábbi kife- jezést: X(τ, ω) = Z ∞ −∞ x(t)w (t − τ ) e−iωt dt. Ez a szignálból egy olyan két dimenziós függvényt készít, amely az id® és frekven ia tartományból képez. Viszont az STFT -nek egy nagy hátránya van, hogy el®re lerögzített felbontással dolgozik, azaz az ablak függvény tartójának hosszától függ®en érzékeny a frekven iára. Egy szélesebb ablak pontosabb informá iót szolgáltat a jelben megbújó frekven iákról, viszont az id® felbontása kevésbé 1 Short-Time Fourier Transformation 2 ilyen ablak függvény lehet például egy [−1 . 1]-ra korlátozott Gauss görbe( w (t)

= e−t 2 /2 ), vagy a Hann-ablak függvény ( w(t) = 0.5 ∗ (1 − cos 2πT )) 3 pontos. Míg egy sz¶kebb ablakkal kisebb frekven ia tartományról lehet pontos értékeket kapni, viszont id®ben jobban el tudjuk helyezni. Erre a problémára nyújt egy megoldást a wavelet transzformá ió, ahol a x ablak méret - felbontás helyett a frekven iától függ® felbontást lehet alkalmazni. Azaz magas frekven iák esetén jobb id®-érzékenységet, míg ala sonyabb frekven iájú változások esetén kevésbé pontos id®beli lokalizá iót kaphatunk. 2. Dení iók A továbbiakban a következ® jelöléseket használjuk a konziszten ia kedvéért: a[n]-nel jelöljük a sorozatokat, Fourier transzformáltját fˆ-vel, n∈ Z, egy míg a[n] a(n)-nel, ha n ∈ R. Egy sorozat megfordítottját f függvény ā[n] = a[−n]- nel, valamint legyen x̌[n] =  0 n = 2p + 1 x[n] L n = 2p egy id® invariáns lineáris operátor, ha egy p-vel eltolt,

mintára, a kimenet is eltoltja lesz: fp [n] = f [n − p] Lfp [n] = Lf [n − p] Impulzus válasz - minden f [n] szignál ként: felírható eltolt Dira +∞ X f [n] = p=−∞ Legyen h[n] := Lδ[n] függvények összege- f [p]δ[n − p] a diszkrét impulzus válasz, az L linearitása és id® invari- an iája miatt: Lf [n] = +∞ X p=−∞ f [p]h[n − p] = f ⋆ h[n] Azaz, egy diszkrét id® invariáns operátor felírható diszkrét konvolú ióval, s ha h[n] véges tartójú, akkor Lf [n] véges sok m¶velettel számolható,ezt nevezik 3 véges impulzus válasznak (FIR ). értékekt®l függ, ekkor h[n] = 0 L ha kauzális ha n < 0. Lf [p] sak az n ≤ p f [n] A sz¶r®t stabilnak nevezzük, ha korlátos bemenetre, korlátos kimenetet produkál, ami egyenérték¶ azzal, hogy P+∞ n=−∞ |h [n]| < +∞. 3 Finite Impulse Response 4 L sz¶r®nek a sajátvektorai diszkrét szinusz hullámok:eω [n] = eiωn , mivel teljesül,

hogy: Leω [n] = +∞ X eiw(n−p) h[p] = eiωn p=−∞ +∞ X h[p]e−iωp p=−∞ ahol a sajátérték a következ® Fourier sor, amit a sz¶r® transzfer függvényének nevezünk: ĥ(ω) := +∞ X h[p]e−iωp p=−∞ Riesz bázis. Az ortogonális bázisnál gyengébb feltétel a Riesz bázis feltéte- {en }n∈N lezése, amelynek a dení iója: legyen vektor sorozat egy H térben, ami lineárisan független, valamint lineáris kombiná iói s¶r¶ek és létezik A>0 és B >0 úgy, hogy úgy,hogy f= f ∈H +∞ X esetén található egy λ[n] Hilbert- H -ban, sorozat λ[n]en n=0 és X 1 1 2 2 2 kf k ≤ |λ[n]| ≤ kf k B A n Ekkor a Riesz reprezentá iós tétel szerint létezik hf, ẽn i, ẽn vektor sorozat, hogy λ[n] = ami szintén Riesz bázist alkot, s az eredeti bázis duálisának nevezik, valamint igaz rá, hogy: f= +∞ X n=0 hf, en i ẽn = +∞ X n=0 3. Változó felbontás sorozat Egy {Vj }j∈Z felbontás

sorozat alatt L2 (R) amire igaz, hogy monoton növeked® alterei hf, ẽn i en 4 egymásba ágyazott altereit értjük, L2 (R)-t: Vj−1 ⊂ Vj ⊂ . ⊂ L2 (R) azaz egy nomabb felbontás tartalmazza mindazt az informá iót, ami egy durvább közelítés el®állításához szükséges, 4 Multiresolution analysis 5 j azaz - ha PVj (f )-fel jelöljük Vj = {0}, f -nek lim j∞ [ Vj = L2 (R) j Vj -re való ortogonális vetületét - 5 f − PVj (f ) = 0 avagy egy függvény közelítései konvergálnak az eredeti függvényhez. f (t) ∈ Vj ⇐⇒ f (2t) ∈ Vj+1 f (t) ∈ V0 ⇐⇒ f (t − k) ∈ V0 k ∈ Z azaz Vj eltolás invariáns k 2j -vel való eltolásokra, ∃φ(t) : {φ(t − k)} Ekkor a többi Vj φ(t) V0 -nak -t skála függvénynek nevezzük. Ez a skála függvény generálja a térnek is egy-egy ortonormált bázisát, jelöljük ezt értelemszer¶en: Mivel ortonormális bázisa φj,k (t) = 2j/2 φ(2j t − k), {φj,k (t)}-vel,

ahol ami a feltételekb®l következik. V0 ⊂ V1 ezért minden V0 -beli függvény kifejezhet® a V1 bázisfüggvényei segítségével, spe iálisan a skála függvény is: φ(t) = X √ X 2 h[k]φ(2t − k) h[k]φ1,k (t) = Ezt a képletet dilatá iós a φ1,k (t) (3.1) k k 6 avagy nomítási 7 egyenletnek nevezzük. A h[k]együtthatókat ortonormalitásából számolhatjuk, skalár szorzat segítségével : √ Z h[k] = hφ1,k , φi = 2 ∞ −∞ A (3.1)-t integrálva t φ(t)φ(2t − k)dt szerint, kapjuk, hogy X 1 √ = h[k] 2 k 5 f ∈ V ortogonális vetülete f -nek, ha minimalizálja a kf − f k kifejezést j j j 6 dilation equation 7 renement equation 6 (3.2) φ(t − l)-vel megszorozzuk, és integráljuk t szerint, akkor: Z +∞ Z +∞ X X φ(t)φ(t − l)dt = 2 h[k]h[k ′ ]φ(2t − k ′ )φ(2t − 2l − k)dt valamint, ha (3.1)-t −∞ −∞ X = k k′ h[k]h[k + 2l] k újra felhasználva, hogy {φ(t − k)} ortogonális, X

h[k]2 = 1 kapjuk, hogy k és X h[k]h[k + 2l] = 0, l 6= 0 k 3.1 Skála függvény meghatározása dilatá iós együtthatókból Egy kompakt tartójú skála függvény kielégíti a következ® dilatá iós egyenletet: φ(t) = N N X X √ 2hk φ(2t − k) = ck φ(2t − k) k=0 ahol a tartó [0.N ] k=0 t = 0.N felírva kapjuk, a X X φ(i) = ck φ(2i − k) = c2t−j φ(j) Ezt i = 0.N j k lineáris egyenletrendszert, aminek egy egy saját érték¶ saját vektora adja meg a keresett φ(i) értékeket. Ebb®l az let segítségével tetsz®leges tn számolható {φ( 2 ) |n leszámítva teljesül is. ∈ Z }- t N +1 φ értékb®l, valamint a dilatá iós egyen- -re kiszámolhatjuk s feltehetjük, hogy φ φ(t)-t - {φ(tn) |n ∈ Z }esetén folytonos, ami a Haar esetet 3.2 Különbség tér8 Ha egy f (t) Vj -beli közelítését PVj f (t)-vel jelöljük, akkor az dj (t) = PVj+1 f (t) − PVj f (t)-vel jelölt különbség függvény, tartalmazza a

részleteket tásban. Azaz, felbonthatjuk a Vj+1 teret Vj+1 = Vj 8 detail spa e 7 M Wj 2−(j+1) felbon- alakban, ahol Vj -re. r®leges Wj -t a j szinten lev® felbontási térnek nevezzük, s ez persze me- A felbontást folytathatjuk tovább is, így kapjuk, hogy Vj = Vj−K K M Wj−k k=1 ahol a is: Wj alterek Wj ⊥ W j ′ ha továbbra is ortogonálisak j 6= j könnyen kaphatunk val jelöljük Így Wj L2 (R)-nek ′ . A Vj -kre Wj+1 egy Vj ′ -re, ha j ≥ j′, kikötött feltételek miatt, a bázisát átskálázással. s ha ortonormált bázisát, akkor adódik, hogy egy ortonormált bázisát kapjuk meg : s emiatt egymásra Wj egy bázisából {ψj,k (t)|k = −∞.∞}- ψj,k (t) = 2j/2 ψ(2j t−k). {ψj,k (t)|k = −∞.∞, j = 0.∞}, ahol minden bázis függvény egy ψ(t) függvény dilatált és eltolt képeként áll el®. Ezt a ψ -t alap wavelet függvénynek, vagy anya waveletnek 9 nevezzük. 4. Wavelet

függvény Mivel {ψ(t − k)} ⊆ W0 ⊂ V1 ezért ψ kifejezhet® V1 bázis függvényeinek segítségével a következ®képpen: ψ(t) = X √ X 2 g[k]φ(2t − k) g[k]φ1,k (t) = k ahol a gk (4.1) k együtthatók számolhatók zattal számolhatók: φ(2t − k) g[k] = hφ1,k , ψi = √ Z 2 ortonormalitása miatt skalárszor- ∞ −∞ ψ(t)φ(2t − k)dt (4.2) Így egy a skála függvényhez és dilatá iós együtthatók közötti összefüggéshez nagyon hasonló kap solatot kapunk a wavelet függvény és a wavelet együtthatók között. A két függvény és együttható sorozat szorosan összefügg a Vj tereken keresztül, ennek pontos felderítéséhez át kell térnünk az id®-tartományon végzett vizsgálódásról a frekven ia tartományra Fourier-transzformá ió segítségével. φ̂(ω) Z X√ = 2h[k] k ∞ −∞ φ(2t − k)e−iωt dt = Z ∞ 1 X ω ω = √ ( h[k]e−ik 2 ) φ(2t − k)e−i(2t−k) 2 d(2t) 2 k −∞ 1 ω ω =

√ ĥ( )φ̂( ) 2 2 2 (4.3) (4.4) (4.5) 9 mother wavelet 8 ahol ĥ(ω) = X h[k]e−ikω (4.6) k , s φ̂(ω) illetve ψ̂(ω) φ(t) és ψ(t) írhatjuk ilyen formába: Fourier transzformáltjai. Ekkor (41)-t szintén 1 ω ω ψ̂(ω) = √ ĝ( )φ̂( ) 2 2 2 (4.7) ahol szintén ĝ(ω) = X g[k]e−ikω k Ekkor az φ(t) ortogonalitása δk,0 = = φ(t − k)-ra így fogalmazható: ∞ Z ∞ 1 φ(t)φ(t − k)dt = φ̂(ω)φ̂(ω)eiωk dω = 2π −∞ −∞ Z 2π X ∞ 2 1 φ̂(ω + 2πl) eiωk dω 2π 0 Z l=−∞ jelöljük a bels® formulát kiemelve: Aφ (ω) = ∞ X φ̂(ω + 2πl) 2 l=−∞ ahol Aφ (ω) egy 2π ≥0 periódusú kifejezés lesz. Így az ortogonalitást úgy írhatjuk fel, hogy δk,0 = 1 2π Z 2π Aφ (ω)eiωk dω 0 azaz, ha Aφ (ω) = ∞ X φ̂(ω + 2πl) 2 =1 (4.8) l=−∞ 4.1 Skála függvény Riesz bázisból Ez alapján viszont egy Riesz bázisból is ortonormális rendszert

kaphatunk, ugyanis legyen {Vj }j∈Z nak, valamint legyen többszint¶ felbontás, φ(t) {θ(t − n)}n∈Z Riesz bázisa V0 - olyan függvény, melynek Fourier transzformáltjára teljesül, hogy φ̂(ω) =  P∞ k=−∞ θ̂(ω) θ̂ (ω + 2kπ) 9 2 1/2 jelöljük 1 φj,n (t) = √ φ 2 ekkor {φj,n (t)}n∈Z miatt ugyanis már 4.2 t−n 2j  Vj -nek j ∈ Z-re. Az ortogonális bázisa φ̂(ω)  le van normálva Aθ (ω)-val, el®bbi gondolatmenet így lesz Aφ (ω) = 1. Ortogonalitás dilatá iós együtthatókból Az (4.8)-t felírhatjuk (43) segítségével is, méghozzá: 1= ∞ X φ̂(ω + 2πl) 2 ∞ X = l=−∞ l=−∞ ∞ X 1 2 = mivel minden ω -ra ω + 2πl 1 ω + 2πl √ ĥ( )φ̂( ) 2 2 2 ĥ(ϑ + πl) 2 φ̂(ϑ + πl) 2 = 2 l=−∞ igaznak kell lennie, ezért áttérhetünk ϑ = ω/2-re. Ha ezt a kifejezést felírjuk páros és páratlan l -ekre külön, akkor kapjuk, hogy: 1 = ∞ 1 X ĥ(ϑ + 2lπ) 2

+ s mivel tudjuk, hogy 1= 1 ĥ(ϑ) 2 2 ∞ X 2 2 φ̂(ϑ + 2lπ) + l=−∞ ∞ X ĥ(ϑ + (2l + 1)π) ĥ(ω) 2π periódusú, ez tovább egyszer¶södik: 1 2 2 φ̂(ϑ + (2l + 1)π) 2 l=−∞ 2 φ̂(ϑ + 2lπ) + l=−∞ 1 ĥ(ϑ + π) 2 2 ∞ X φ̂((ϑ + π) + 2lπ) 2 l=−∞ ide behelyettesítve (4.8)-t kapjuk, hogy: 2 = ĥ(ϑ) 4.3 2 + ĥ(ϑ + π) 2 (4.9) Ortogonalitás wavelet együtthatókból Hasonlóan a wavelet függvényre is levezethet® ortogonalitási feltétel: ∞ X ψ̂(ω + 2πl) 2 =1 l=−∞ avagy: 2 2 = |ĝ(ϑ)| + |ĝ(ϑ + π)| 10 2 (4.10) Ezenkívül, ha még a wavelet függvény és a skála függvény ortogonalitását is fel akarjuk írni, akkor a következ®re juthatunk: 0 = Z ∞ φ(t)ψ(t − k)dt = −∞ = 1 2π Z = 1 2π Z ∞ φ̂(ω)ψ̂(ω)eiωk dω = −∞ +∞ 2π X φ̂(ω + 2πl)ψ̂(ω + 2πl)eiωk dω −0 l=−∞ ebb®l következik, hogy 0= +∞ X φ̂(ω + 2πl)ψ̂(ω

+ 2πl) l=−∞ Hasonlóan felhasználva a dilatá iós és wavelet függvény egyenlet együtthatóira vonatkozó képleteket, kapjuk, hogy : ĥ(ω)ĝ(ω) + ĥ(ω + π)ĝ(ω + π) = 0 (4.11) Ez az egyenlet kap solja össze a dilatá iós együtthatókat a wavelet függvény együtthatóival. 4.4 Dilatá iós és wavelet együtthatók közötti összefüggés Abban az esetben, ha mire teljesül, hogy ĝ(ω) = α(ω)ĥ(ω + π), 2 |α(ω)| = 1 hogy teljesül (4.11) Ilyen α-nak és ahol α egy α(ω) = −α(ω + π), választhatjuk az−e iω 2π periódusú függvény, akkor könnyen látható, függvényt, ami a számo- lást igen megkönnyíti. Mivel, ha beírjuk (46)-t a kifejezésbe: ĝ(ω) = −e−iω ĥ(ω + π) X = −e−iω h[k]eik(ω+π) k = X h[k](−1)1−k e−iω(1−k) k = X k = X h[1 − k](−1)k e−ikω g[n]e−inω n azaz, ebben az esetben: g[n] = (−1)n h[1 − n] 11 Tehát egy skála függvényhez tudunk

találni elég egyszer¶en wavelet együtthatókat, és abból waveletet tudunk számolni. 4.5 Wavelet függvény tulajdonságai A wavelet egy ψ ∈ L2 (R) függvény, melyre: Z +∞ ψ(t)dt = 0 −∞ valamint kψk2 = 1, s kompakt tartójú, mely tartalmazza t = 0-t. Ennek a függvénynek az eltoltjai és skálázottjai: 1 ψu,s (t) = √ ψ s  t−u s  - szintén 1 normájúak - lesznek az id® - frekven ia atomok. S a wavelet transzformáltja egy f függvénynek pedig W f (u, s) = hf, ψu,s i = ahol Z +∞ −∞ 1 f (t) √ ψ ⋆ s 1 ψ s (t) = √ ψ ⋆ s   −t s t−u s  dt = f ⋆ ψ s (u)  Az a feltételezés, hogy a ψ tartója kompakt, s egy 0 környezetére korlátozódik Rp 2 ( −p |ψ(t)| dt > 1 − ε), azzal a szemléletes tulajdonsággal jár, hogy W f (u, s)  u−p u+p  értékét f -nek az tartományon felvett értéke határozza meg. s , s 4.6 Gyors Ortogonális Wavelet Transzformá ió 10 Az FWT egy olyan

algoritmus, amivel kiszámolható egy véges felbontáson mintavételezett jel wavelet együtthatóit, iteratívan. Minden egy durvább PVj+1 f PVj f közelítéshez visszaad közelítést, és a wavelet együtthatókat, amelyeket PWj+1 f tartalmaz. Állítás (Mallat). és Vj -nek, Legyen {ψj,n }n∈Z és {φj,n }n∈Z ortonormális bázisa s az ezen alterekbe való vetítés együtthatóit jelöljük : 10 FWT - Fast Wavelet Transform aj [n] = hf, φj,n i 12 Wj -nek és dj [n] = hf, ψj,n i ekkor a felbontáshoz az együtthatókat megkaphatjuk így: +∞ X (4.12) n=−∞
h[n − 2p]aj [n] = aj ⋆ h̄ [2p] +∞ X g[n − 2p]aj [n] = (aj ⋆ ḡ) [2p] (4.13) aj+1 [p] = dj+1 [p] = n=−∞ valamint az aj+1 , dj+1 +∞ X aj [p] = n=−∞ = aj -t sorozatokból az számolhatjuk: h[p − 2n]aj+1 [n] + +∞ X n=−∞ ǎj+1 ⋆ h[p] + dˇj+1 ⋆ g[p] Az (4.12) belátáshoz a következ®k kellenek: Minden Vj ortogonális bázisában ebben a

formában: φj+1,p = +∞ X n=−∞ g[p − 2n]dj+1 [n] = φj+1,p ∈ Vj+1 ⊂ Vj felírható hφj+1,p , φj,n i φj,n (4.14) a skalárszorzatot külön felírva kapjuk, hogy hφj+1,p , φj,n i = +∞ Z −∞ 1 √ φ 2j+1  t 2j+1 −p  1 √ φ⋆ 2j   t − n dt = 2j s := 2tj − 2p Z +∞   s = φ φ (s − n + 2p) ds = 2 −∞   1 s √ φ = , φ (s − n + 2p) = h[n − 2p] 2 2 új változót bevezetve: visszaírva (4.14)-ba kapjuk: φj+1,p = +∞ X n=−∞ ezt f -fel h[n − 2p]φj,n skalár szorozva: aj+1 [p] = hf, φj+1,p i = = +∞ X n=−∞ * f, +∞ X n=−∞ h[n − 2p]φj,n h[n − 2p] hf, φj,n i = 13 +∞ X n=−∞ + = h[n − 2p]aj [n] Hasonló lépésekkel látható be a másik két egyenl®ség is. Így a kezünkben van egy olyan algoritmus, amely egy bemen® id®sorból, frekven ia szerint szétválasztja a jelet, egy magas frekven iáktól - zajtól mentes, és egy magas frekven iákat tartalmazó

együttható sorozatra. Ráadásul gyakorlati szempontokat tekintve számos el®nyös tulajdonsággal rendelkezik ez az eljárás: gyors - véges ltereket feltételezve, könnyen implementálható, s a konvolú iók számolása jól párhuzamosítható. 5. Biortogonális waveletek Nem minden esetben van szükség ortogonális bázisra, van amikor jobb, ha terünket egy enyhébb feltételeket megkövetel® bázissal bontjuk fel. Ortogonális esetben azt követeljük meg a bázis vektoroktól, hogy hei , ej i = δi,j teljesüljön. Biortogonális esetben, nem egyetlen - ortogonális - bázisunk van, hanem egy bázis: {ei }, és annak duálisa: {ẽi }, melyekre azt követeljük meg, hogy hei , ẽj i = δi,j . Ilyen duális bázist nyilván készíthetünk egy bázishoz. Valamint,ha egy bázis saját magának a duálisa, akkor az ortogonális is egyben Az ortogonális esetben az Wj -ben, bázist alkot VJ -ben, és {ψj,k (t)} pedig ennek megfelel®en szeretnénk deniálni

a duális nomodó felbontást, valamint a duális ψ̃ {φj,k (t)} {Ṽj } és {W̃j } altereket, valamint a duális skála φ̃ és wavelet függvényt. Méghozzá úgy, hogy D E φ̃j,k , φj,l = δk,l (5.1) és valamint Vj ⊥ W̃m és D E ψ̃j,k , ψm,l = δj,m, δk,l Ṽj ⊥ Wm (5.2) : D E ψ̃j,k , φm,l = 0 és ahol ψ̃j,k (t) = 2j/2 ψ̃(2j t − k) D és E φ̃j,k , ψ m,l = 0 φ̃j,k = 2j/2 φ̃(2j t − k). Dení ió szerint ezekre is fel lehet írni a dilatá iós (3.1) és wavelet (41) egyenleteket is, azaz: ψ̃(t) = X g̃[k]φ̃1,k (t) = k √ X 2 g̃[k]φ̃(2t − k) k 14 (5.3) és φ̃(t) = X h̃[k]φ̃1,k (t) = √ X 2 h̃[k]φ̃(2t − k) (5.4) k k Itt a következ®képpen számolhatjuk az együtthatókat: D E √ Z g̃[k] = φ1,k , ψ̃ = 2 valamint ∞ −∞ D E √ Z h̃[k] = φ1,k , φ̃ = 2 φ(2t − k)ψ̃(t)dt ∞ −∞ φ(2t − k)φ̃(t)dt Hasonlóan, amikor Fourier transzformá ióval a

frekven ia tartományra térünk át, kapjuk: 1 ˆ ω ˆ ω ˆ ψ̃(ω) = √ g̃( )φ̃( ) 2 2 2 és képleteket a duális skála és g̃-ból, ahogy ĝ δk,0 1 ˆ ω ˆ ω ˆ φ̃(ω) = √ h̃( )φ̃( ) 2 2 2 ˆ analóg függvényekre. Ahol g̃ (5.5) (5.6) módon van deniálva g -b®l. Ekkor (51)-t felírva: Z ∞ Z ∞ 1 ˆ = φ̃(t)φ(t − k)dt = φ̃(ω)φ̂(ω)eiωk dω = 2π −∞ −∞ Z 2π X ∞ 1 ˆ φ̃(ω + 2πl)φ̂(ω + 2πl)eiωk dω = 2π 0 is l=−∞ azaz: +∞ X ˆ + 2πl)φ̂(ω + 2πl) = 1 φ̃(ω l=−∞ hasonlóan: +∞ X ˆ ψ̃(ω + 2πl)ψ̂(ω + 2πl) = 1 l=−∞ valamint +∞ X ˆ ψ̃(ω + 2πl)φ̂(ω + 2πl) = 0 és l=−∞ +∞ X ˆ φ̃(ω + 2πl)ψ̂(ω + 2πl) = 0 l=−∞ Hasonlóan a (4.2) szakaszban végrehajtott átalakításokkal, kapjuk, hogy ˆ ĥ(ω) + h̃(ω ˆ + π)ĥ(ω + π) = 1 h̃(ω) ˆ ˆ + π)ĝ(ω + π) = 1 g̃(ω)ĝ(ω) + g̃(ω ˆ ĥ(ω) + g̃(ω ˆ + π)ĥ(ω + π) = 0 g̃(ω) ˆ ˆ +

π)ĝ(ω + π) = 0 h̃(ω)ĝ(ω) + h̃(ω 15 (5.7) 5.1 Együtthatók közötti összefüggés Biortogonális esetben is feltehetjük, hogy ˆ (ω + π) ĝ (ω) = −e−iω h̃ és g̃ˆ (ω) = n −e−iω ĥ (ω + π), így egyszer¶en számolható ltereket kapunk : g[n] = (−1) h̃ [1 − n] és n g̃[n] = (−1) h [1 − n]. Ortogonális esetben láttuk, hogy a waveleteket a lter együtthatókból le- hetett számolni, analóg módon zajlik itt is, azzal a különbséggel, hogy plusz megkötésekkel is élhetünk a lterünkre. A szimmetria érdekében kiköthetjük például, hogy legyen h[−n] (n ≥ 0) linom (ha cos (ω)-ra h[n] = h[−n], (ha a lter hossza páratlan), vagy h[n + 1] = ˆ a lter hossza páros). Ekkor ĥ(ω) (vagy h̃(ω)) valós po- nézve, ha páratlan, míg eiω/2 cos (ω/2)-szorosa egy cos (ω)-ra valós polinomnak, ha páros a lter. Továbbá, ha megköveteljük, hogy az els® N = 2l momentuma elt¶njön ψ -nek,

akkor a polinomnak kell tartalmaznia egy (1 + cos (ω))l = cos2l (ω/2) Azaz olyan biortogonális waveletet keresünk amelyre teljesül (5.7) valamint a következ® formába írhatóak:  ω N +k e−iω/2 cos q0 (cos (ω)) 2 ĥ (ω) = és  ω Ñ +k q̃0 (cos (ω)) e−iω/2 cos 2 ˆ h̃ (ω) = ahol N = 2l,Ñ = 2l̃ és k = 0,ha a lter páratlan, k=1 ha páros valamint q0 és q̃0 is polinomok. Ennek megoldása nagy vonalakban úgy zajlik, ahogy ortogonális esetben is történt. S megmutatható, hogy ilyen feltételeket kielégít® wavelet párokat találhatunk. Lásd [4℄ 5.2 Cohen-Daube hies-Feauveau biortogonális wavelet konstruk ió Legyen és P (eiw ) és P̃ (eiw ) szigorúan pozitív polinomok, úgy hogy: ω  2   ω   2 ĥ P eiω/2 + ĥ + π P ei(ω/2+π) = 2P (eiω ) 2 2 valamint        2 ˆ ω 2 ˆ ω h̃ P̃ eiω/2 + h̃ + π P̃ ei(ω/2+π) = 2P̃ (eiω ) 2 2 inf ω∈[−π/2,π/2] 16 ĥ (ω) > 0 és ˆ h̃ (ω)

> 0 inf ω∈[−π/2,π/2] akkor a ĥ(2−p ω) √ 2 p=1 (5.8) +∞ ˆ −p Y h̃(2 ω) ˆ √ φ̃(ω) = 2 p=1 (5.9) φ̂(ω) = és +∞ Y által deniált függvények biortogonális rendszert alkotnak : D E φ(t), φ̃(t − n) = δ[n] és a {ψj,n }(j,n)∈Z2 lamint 2 φ̂ ∈ L (R). {ψ̃j,n }(j,n)∈Z2 biortogonális Riesz és bázisa az L(R2 )-nek, va- A bizonyítás megtalálható itt:[1℄. 5.21 Biortogonális spline waveletek Egy ilyen megoldást fogunk röviden kiszámolni. Válasszuk ĥ (ω) = exp ahol k = 1 vagy 0 N N −1  cos lineáris kombiná iója  ω N 2 q0 = 1. Ekkor a skála függvény fokú spline függvény : φ̂ (ω) = exp ψ −ikω 2 párosságától függ®en. Azaz megkapjuk (5.8)-b®l egy Mivel   −ikω 2 φ (2t − n)  sin (ω/2) ω/2 N spline függvényeknek, ezért az is kom- pakt tartójú, hasonló fokú spline függvény. Felhasználva (57)-t kapjuk: (legyen M = (N + N˜)/2) ˆ (ω) = exp

h̃  −ikω 2  cos  ω Ñ M−1 X 2 k=0 M −1+k k ! sin  ω 2k 2 Az így kapott waveletet biortogonális spline waveletnek nevezik. 5.3 Tökéletes visszaállítás Ahogy az ortogonális esetben is történt, biortogonális waveletekkel is lehet diszkrét szignálokat felbontani együtthatók sorára, s azokból kés®bb újra el®állítani 17 az eredeti jelet. Ez ortogonális esetben azzal a problémával járt, hogy - a Haar lteren kívül - a quadratura tükör lterek (QMF) impulzus válasszal 11 nem rendelkeznek véges 12 . Az el®z® szakaszokban vizsgált biortogonális wavelet függvény párokat akarjuk két satornás sz¶r® rendszerekként 13 felhasználni, méghozzá úgy, hogy a transzformá iók - a sz¶rés és visszaállítás - után visszakapjuk az eredeti id®sort. A sz¶rés során a két satornás sz¶r® rendszer konvolválja az a0 szignált a h̄[n] = h[−n] low-pass lterrel, valamint a ḡ[n] = g[−n] high-pass

lterrel, aztán ritkítja 2-vel a kimenetet: a1 [n] = a0 ⋆ h̄[n] (5.10) d1 [n] = a0 ⋆ ḡ[n] (5.11) és Ezután a visszaállítás során az eredeti szignál úgy áll el®, hogy a nullákkal feltöltött a1 ,d1 jelsorozatot a duális high-pass illetve low-pass lterrel konvolváljuk: a˜0 [n] = ǎ1 ⋆ h̃[n] + dˇ1 ⋆ g̃[n] (5.12) 5.31 Vetterli tétele Egy sz¶r® rendszer akkor és sak akkor állítja vissza az eredeti szignált, ha ˆ ĥ⋆ (ω + π) h̃ (ω) + ĝ ⋆ (ω + π) g̃ˆ (ω) = 0 (5.13) ˆ ĥ⋆ (ω) h̃ (ω) + ĝ ⋆ (ω) g̃ˆ (ω) = 2 (5.14) és Bizonyítás Ha egy jelsorozat minden második elemét kihagyjuk (azaz y[n] = x[2n]), akkor a Fourier transzformáltját így számolhatjuk: ŷ (2ω) = +∞ X x[2n]e−i2nω = n=−∞ 1 (x̂ (ω) + x̂ (ω + π)) 2 A 0-ák beillesztését így írhatjuk fel egy jelsorozatba : x̌[n] = 11 quadrature mirror lter 12 nite impulse response 13 2- hannel lter bank  0 n = 2p + 1

x[n] 18 n = 2p (5.15) , ennek Fourier transzformáltja pedig: ŷ (ω) = +∞ X x[n]e−i2nω = x̂ (2ω) (5.16) n=−∞ A tétel bizonyításához el®ször mással kap solatba. Mivel a0 , a1 és d1 Fourier transzformáltját hozzuk egy- h és g valós, ezért ĥ (−ω) = ĥ⋆ (ω) és ĝ (−ω) = ĝ ⋆ (ω). Beírva (5.10) Fourier transzformáltjába (515)-t, kapjuk aˆ1 (2ω) =  1 aˆ0 (ω) ĥ⋆ (ω) + aˆ0 (ω + π) ĥ⋆ (ω + π) 2 hasonlóan (5.11) Fourier transzformáltjába: 1 dˆ1 (2ω) = (aˆ0 (ω) ĝ ⋆ (ω) + aˆ0 (ω + π) ĝ ⋆ (ω + π)) 2 Viszont (5.12) Fourier transzformáltjánál felhasználhatjuk (516)-t: ˆ0 (ω) = â1 (2ω) ˆh̃ (ω) + dˆ1 (2ω) g̃ˆ (ω) ã Innen, az egészet egyetlen képletbe s¶rítve kapjuk: ˆ0 (ω) = ã = Ahhoz, hogy az â0 (ω + π) a0 = a˜0  1 aˆ0 (ω) hˆ⋆ (ω) + aˆ0 (ω + π) hˆ⋆ (ω + π) ˆh̃ (ω) + 2
1 aˆ0 (ω) gˆ⋆ (ω) + aˆ0 (ω + π) gˆ⋆ (ω + π) g̃ˆ

(ω) 2  1 ˆ h̃ (ω) hˆ⋆ (ω) + g̃ˆ (ω) gˆ⋆ (ω) aˆ0 (ω) + 2  1 ˆ h̃ (ω) hˆ⋆ (ω + π) + g̃ˆ (ω) gˆ⋆ (ω + π) aˆ0 (ω + π) 2 teljesüljön, az â0 (ω) együtthatójának 1-nek kell lennie, s -nak meg el kell t¶nnie. S pont ez volt a tételben megfogalmazott feltétel. Mátrixos formában is írhatjuk a feltételt, ekkor : Ha a ĥ (ω) ĝ (ω) ĥ (ω + π) ĝ (ω + π) ! ∗ ˆ h˜⋆ (ω) gˆ˜⋆ (ω) ∆ (ω) = ĥ (ω) ĝ (ω + π) − ĥ (ω + π) ĝ (ω)-val sát, akkor a 2 × 2-es ! = 2 0 ! jelöljük a mátrix determinán- mátrixot invertálva : ˜⋆ (ω) hˆ ˜⋆ (ω) gˆ ! 2 = ∆ (ω) ĝ (ω + π) −ĥ (ω + π) ! (5.17) Azaz a rekonstruk iós lter akkor létezik, ha a determináns nem t¶nik el minden ω ∈ [−π, π]-re. 19 Állítás Tökéletes rekonstruk iós sz¶r®re teljesül, hogy ˆ ˆ ĥ⋆ (ω) h̃ (ω) + ĥ⋆ (ω + π) h̃ (ω + π) = 2 (5.18) s®t, amennyiben a sz¶r®k

végesek - véges impulzus válasszal rendelkeznek, (FIR 14 lterek) - akkor a determináns egyszer¶en számolható, s ebben az esetben létezik a∈R és l∈ Z, hogy ˆ ĝ (ω) = ae−i(2l+1)ω h̃⋆ (ω + π) és 1 g̃ˆ (ω) = e−i(2l+1)ω ĥ⋆ (ω + π) a Bizonyítás Ez úgy látható be, hogy (5.17)-t felírva: 2 ĝ (ω + π) ∆ (ω) (5.19) −2 g̃ˆ⋆ (ω) = ĥ (ω + π) ∆ (ω) (5.20) ˆ ⋆ (ω) = h̃ és így: ĝ (ω) g̃ˆ⋆ (ω) = − A ∆ (ω) dení iója miatt (5.18)-t ∆(ω + π) ˆ ⋆ h̃ (ω + π) ĥ (ω + π) ∆ (ω) ∆ (ω + π) = −∆ (ω), így (5.14)-re alkalmazva kapjuk Mivel egy véges impulzus válasszal rendelkez® sz¶r® Fourier transzformáltja dení ió szerint véges sorozata exp (±inω) alakú tagoknak. Így a termináns is egy ilyen véges sorozat, valamint (5.19) miatt −1 ∆ ∆ (ω) (ω) de- is az. S egy olyan véges sorozataexp (±inω) tagoknak, amelyeknek a re iproka is felírható

véges sok exp (±inω) ∆ (ω + π) = −∆ (ω), olyan l∈Z és a∈ R, taggal, az sak egyetlen tagból állhat. S mivel ezért ennek a kitev®ben lev® n páratlan. Azaz, létezik hogy ∆ (ω) = −2a exp (i (2l + 1) ω) ezt behelyettesítve (5.19) és (520)-be, kapjuk a bizonyítandó állítást 14 nite impulse response 20 Amennyiben a=1 l=0 és akkor (5.18)-t az id®tartományra átírva - azaz a sz¶r® együtthatóira megfogalmazva az egyenl®séget : 1−n g [n] = (−1) h̃ [1 − n] és 1−n g̃ [n] = (−1) Látható, hogyha megköveteljük a felbontási rekonstruk iós h̃, h h [1 − n] sz¶r® legyen ugyanaz mint a akkor (5.18)-b®l (410) lesz 6. Wavelet lifting Az el®z® részben használt sz¶r®ket tovább vizsgáljuk Laurent polinomok segítségével, s fel próbáljuk bontani egyszer¶bb transzformá iók sorozatára. Ehhez az eddigi állításokat át kell fogalmazni Laurent polinomokra. Egy adott h véges lterhez

rendeljük a következ® polinomot: h(z) = N X h[k]z −k M Ezen polinom foka deniáljuk |h| = N − M -nek. A valós együtthatós Laurent polinomok kommutatív gy¶r¶t alkotnak, viszont többnyire sak maradékosan lehet osztani, ráadásul nem is egyértelm¶en. Formálisan: ha van két Laurent polinom akkor mindig létezik egy olyan |b (z)| és |r (z)| < |b (z)| q (z) a(z) r (z) és és b(z) 6= 0, hogy polinom, amire úgy, hogy |b (z)| ≤ |a (z)|, |q (z)| = |a (z)| − a (z) = b(z)q(z) + r(z). Magát a Laurent gy¶r¶t akkor, és két   R z, z −1 -vel szokták jelölni. Egy Laurent polinom sak akkor invertálható, hogyha egyetlen tagból áll, azaz satornás sz¶r® rendszer itt  
M 2; R z, z −1 -val 2×2 (6.1) |h| = 0. Egy -es mátrix lesz a gy¶r¶ felett, amik az jelölt gy¶r¶t alkotják. Laurent polinomok esetén könnyen látható, hogy ahhoz, hogy a   h, g, h̃, g̃ egy tökéletesen visszaállító sz¶r® rendszer

polinomjai legyenek, a következ® egyenl®ségek teljesülése szükséges, (5.13) és (514) alapján:

h (z) h̃ z −1 + g (z) g̃ z −1 = 2

h (z) h̃ −z −1 + g (z) g̃ −z −1 = 0 21 Legyen az M (z) modulá iós mátrix a következ®: M (z) = Hasonló legyen a duális M̃ (z) " h (z) h (−z) g (z) g (−z) # modulá iós mátrix. Ekkor mátrixokkal az egyen- l®ség a következ®képpen alakul: M̃ z −1 azaz, mindkét mátrix része soportjának. 6.1 Egy h
t M (z) = 2I  
GL 2; R z, z −1 -nek, Polifázis reprezentá ió15 lternek a polifázis reprezentá iója alatt értsük a következ®t: hps (z) = X h[2k]z −k és hpt (z) = k azaz a az invertálható mátrixok hps h [2k + 1] z −k k h tartalmazza a X páros együtthatóit, míg a hpt írható

h (z) = hps z 2 + z −1 hpt z 2 valamint hps z 2 és
= h (z) + h (−z) 2
h (z) − h (−z) hpt z 2 = 2z −1 Legyen ezután a polifázis mátrix : P

(z) = hps (z) gps (z) hpt (z) gpt (z) ! így viszont teljesül, hogy P z 15 polyphase representation
2 t = 1/2M (z) 22 1 z 1 −z ! . a páratlanokat. Ekkor Hasonlóan deniáljuk a P̃ (z) duális polifázis mátrixot, ekkor a tökéletes vissza- állíthatóság feltétele, hogy P (z) P̃ z −1 Azaz P (z) hatjuk
t =I invertálható, s®t feltehetjük, hogy gps (z)-t és gpt (z)-t det P (z) = 1, mivel mindig oszt- a determinánssal. P (z) Tehát, egy FIR wavelet transzformá ió megtalálása egyenérték¶ egy 1 determinánsú mátrix megtalálásával. A legkézenfekv®bb, ha h(z) = h̃(z) = 1 és g(z) = g̃(z) = z −1 P (z) = I, ebb®l . Ezt a transzformá ió Lazy-wavelet transzformá iónak nevezik, amikor gyakorlatilag sak a jel páros és páratlan összetev®ire való szétválogatása történik meg. 6.2 Lifting Ha van egy x jelsorozat, akkor tipikusan az egymás utáni elemek er®sen korre- lálnak egymással, azaz

lehetséges létrehozni egy a páros sorszámú elemekb®l (jelöljük nokat (legyen ez xpt ). xps -nek) P prediktort, ami például sak próbálja megállapítani a páratla- Természetesen ez a prediktor nem biztos, hogy tökéletes, így fel kell jegyezni az eltérést: d = xpt − P(xps ). Visszaalakításkor persze a d eltérés és xps alapján megkaphatjuk a páratlanokat: xpt = P(xps ) + d Ha P jó prediktor, akkor d ritkán nem nulla, vagy legalábbis közel van 0-hoz. Például választhatjuk prediktorak a szomszédos értékek átlagolását, azaz P(xps )[2k + 1] = (x [2k] + x [2k + 2]) , 2 s az eltérés pedig: d[k] = x[2k + 1] − Így kaptunk egy (xps , d) jel (x [2k] + x [2k + 2]) . 2 párt, ami még azzal a hiányossággal rendelkezik, hogy a frekven ia komponensek nem válnak el egymástól a két sorozatba. A -ben ugyan a magas frekven ia található, de a xps sak az d x megrítkításával jött létre, s így a mintavételezés

hibája miatt oda magas frekven iákból származó 23 zajok is bekerülhetnek. Például a futó átlaga az eredeti U16 , x d-re xps -nek nem ugyanaz mint az mintának. Ezt a helyzetet javítandó egy második lifting lépésben, egy alkalmazott operátorral próbáljuk simítani xps -t: a = xps + U(d) . Ez a lépés is triviálisan visszafordítható, egy adott (a, d) párból xps megkapható: xps = a − U(d). Az el®z® példához visszatérve, ha a futó átlagokat akarjuk meg®rizni, akkor úgy kell U -t választani, hogy: (d[k − 1] + d[k]) . 4 a[k] = x[2k] + Ezt az általános konstruk ió, kiterjeszthetjük olyan esetre is, amikor a mintavételezés nem egyenl® id®közönként történik, ekkor látható, hogy egy jó prediktor βk x2k + (1 − βk )x2k+1 Deniáljuk egy alakú, ahol (h, g) βk a rá s egyenletlenségeit®l függ. sz¶r® párt kiegészít®nek fázis mátrix determinánsa 17 , ha a megfelel® P (z) poli- 1. Állítás

Legyen (h, g) kiegészít® sz¶r® pár, ekkor minden más, véges sak akkor alkot h-val s (z) sz¶r® akkor és kiegészít® sz¶r® párt, ha g ′ (z) = g (z) + h (z) s z 2 alakú, ahol g′ egy Laurent polinom.
Bizonyítás Ha felbontjuk h (z) s z 2
-t páros és páratlan tagokra, akkor a páros komponense hps (z) s (z) lesz, míg a páratlan hpt (z) s (z). A lifting alkalmazása után - amikor a P prediktornak az s (z) együtthatóiból származó súlyozást választjuk - az új polifázis mátrixnak azt kapjuk, hogy : ′ P (z) = P (z) 16 mint update 17 omplementary 24 1 s (z) 0 1 ! , s ennek az új polifázis mátrixnak is a determinánsa 1 lesz. A lifting módosítja a visszaállítás menetét is, ekkor az új duális polifázis mátrix a következ® lesz: 1 P˜′ (z) = P̃ (z) Ebb®l az új h̃ −s z −1 visszaállító sz¶r®re kapjuk, hogy: 0
1 ! .
h̃′ (z) = h̃ (z) − g̃ (z) s z −2 . Ezt az állítást

megfogalmazhatjuk a duális esetre is. Állítás Legyen (h, g) kiegészít® sz¶r® pár, ekkor minden más, véges sak akkor alkot g -vel t (z) sz¶r® akkor és kiegészít® sz¶r® párt, ha h′ (z) = h (z) + g (z) t z 2 alakú, ahol h′ egy Laurent polinom.
A bizonyítás ugyanaz mint az el®z® esetben is volt, a különbség, hogy a duális lifting a következ®képpen módosítja a polifázis mátrixunkat: 1 ′ P (z) = P (z) 6.3 0 t(z) 1 ! . Laurent polinom felbontás Az eukleidészi algoritmus használatával fogjuk egy polifázis mátrixot liftingek sorozatára bontani. Állítás Legyen a0 (z) és b0 (z) 6= 0 két Laurent polinom, úgy hogy Ismételjük a következ® lépéseket: |a0 (z)| ≥ |b0 (z)| . ai+1 (z) := bi (z) bi+1 (z) := ai (z) akkor mod bi (z) , an (z) lesz a0 (z) és b0 (z) legnagyobb közös osztója, a legkisebb n-re, amire bn (z) = 0 teljesül. 25 Mivel |bi+1 (z)| < |bi (z)|, ezért létezik véges id®

alatt befejez®dik. Legyen ai (z) /bi (z) m, hogy |bm (z)| = 0, qi+1 (z) egy olyan polinom, azaz algoritmus amire qi+1 (z) = (6.1 jelölését használva) ekkor az algoritmus egy lépése felírható az alábbi mátrix szorzással: ! ai+1 (z) bi+1 (z) 0 = ! 1 1 −qi (z) ai (z) bi (z) ! . Ezt iterálva kapjuk, hogy an (z) 0 Azaz a0 (z) b0 (z) így ! = ! 1 Y i=n = n Y 0 1 1 −qi (z) qi (z) 1 1 i=1 0 ! ! ! a0 (z) b0 (z) an (z) 0 ! . , an (z) osztja a(z)-t és b(z)-t is, s ha an (z) egy tagú, akkor a(z) és b(z) relatív prímek. 6.4 Faktorizá iós algoritmus Visszatérve a kiegészít® sz¶r® párokhoz megmutatjuk, hogy hogyan lehet felírni egy tetsz®leges h sz¶r®t lifting lépések sorozataként. Feltehetjük, hogy hps (z) és hpt (z) relatív prímek, hiszen bármely közös faktor osztaná det P (z)-t is, amir®l tudjuk, hogy 1. Így az eukleidészi algoritmust lefuttatva hps (z)-ra és hpt (z)-ra, a legnagyobb közös

osztó egy egytagú polinom lesz. Az osztás nem egyértelm¶sége miatt választhatjuk úgy ezt az egy tagot, hogy pont a konstans tag legyen. Így kapjuk, hogy hps (z) hpt (z) Ha = n Y qi (z) 1 1 i=1 0 ! K 0 ! . |hpt (z)| > |hps (z)| akkor az els® osztó, q1 (z) nulla, ezért az egyszer¶ség ked- véért feltehetjük, hogy g ! |h (z)| páros. Egy h sz¶r®höz megkaphatjuk a kiegészít®, ltert, amire ez kell, hogy teljesüljön: P (z) = hps (z) gps (z) hpt (z) gpt (z) ! = n Y qi (z) 1 1 i=1 0 ! K 0 0 1/K ! . Azt az egyszer¶ észrevételt felhasználva, hogy qi (z) 1 1 0 ! = 1 qi (z) 0 1 ! 0 1 1 0 26 ! = 0 1 1 0 ! 1 0 qi (z) 1 ! , írhatjuk a következ® formába képletünket:  P (z) =  Ahol a n/2 Y i=1 q2i−1 (z)-s felel meg. Míg a 1 q2i−1 (z) 0 1 tagok lifting, a ! 1 0 q2i (z) 1 q2i (z)-s !  K 0 0 1/K ! . tagok duál lifting transzformá iónak K -s tag a triviális,

egyetlen elemre korlátozott,K -val való szorzó, kiinduló sz¶r®nek felel meg, ezt a ltert, lazy lternek is nevezik. Összefoglalva, felírtuk a h sz¶r®höz tartozó P (z) polifázis mátrixot, majd ezt felbontottuk egy lazy lteren végrehajtott lifting és duál lifting átalakítások sorozatára. 6.41 Haar wavelet felbontása Erre a faktorizá ióra mutatunk példát Haar waveletb®l kiindulva. Ebben az esetben a következ® sz¶r®ink vannak: h (z) = 1 + 1z −1 1 1 g (z) = − + z −1 2 2 1 1 −1 h̃ (z) = + z 2 2 g̃ (z) = −1 + 1z −1 Azaz P (z) = 1 − 12 1 2 1 ! ! 1 0 = 1 1 1 0 − 21 1 ! Hasonlóan a visszaállítási sz¶r® rendszernél: −1 P̃ (1/z) = P (z) = 1 1 2 0 1 ! Ebb®l a lter transzformá iókra azt kapjuk, hogy: a′ [l] = x [2l] ′ x[2l + 1] d[l] = d′ [l] − a′ [l] 1 a′ [l] + d[l] 2 d [l] = a[l] = 27 1 0 −1 1 ! . . ennek az inverze pedig ez lesz: a′ [l] = d′ [l] = 1 a[l] − d[l] 2 d[l]

+ a′ [l] x [2l + 1] = d′ [l] x [2l] = a′ [l] 28 Hivatkozások [1℄ J.C Feauveau A Cohen, I Daube hies Biorthogonal bases of ompa tly supported wavelets. Commun on Pure and Appl Math, 45:485560, 1992 [2℄ C. K Chui An Introdu tion to Wavelets A ademi Press, San Diego, CA, 1992. [3℄ I. Daube hies Orthonormal bases of ompa tly supported wavelets. Com- mun. on Pure and Appl Math, 45:909996, 1988 [4℄ I. Daube hies Ten Le tures on Wavelets SIAM Philadelphia, 1992 [5℄ D.L Donoho Interpolating wavelet transforms 1992 [6℄ A. Haar Zur Theorie der orthogonalen Funktionensysteme Math Ann, 69:331371, 1910. [7℄ W. Sweldens I Daube hies Fa toring wavelet transforms into lifting steps 1997. [8℄ S.G Mallat Multiresolution approximations and wavelet orthonormal bases of L2 (R). [9℄ S.G Mallat Trans. Amer Math So , 315(1):6987, 1989 A Wavelet Tour of Signal Pro essing. A ademi Press, Orlando-San Diego, 2nd edition, 1999. [10℄ R.EBlahut Fast Algorithms for

Digital Signal Pro essing Addison-Wesley, Reading, MA, 1984. [11℄ W. Sweldens The lifting s heme: A ustom-design onstru tion of biort- hogonal wavelets. Appl Comput Harmon Anal, 3(2):186200, 1996 29