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

Tartalomjegyzék

1. Kezdetek 3 1.1. Rövid Időtartamú Fourier Analízis (STFT) . . . . . . . . . . . . 3

2. Definíciók 4

3. Változó felbontás sorozat 5 3.1. Skála függvény meghatározása dilatáció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 . . . . . . . . . . . . . . . . . . . . 9 4.2. Ortogonalitás dilatációs együtthatókból . . . . . . . . . . . . . . 10 4.3. Ortogonalitás wavelet együtthatókból . . . . . . . . . . . . . . . 10 4.4. Dilatáció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áció . . . . . . . . . . . . 12

5. Biortogonális waveletek 14 5.1. Együtthatók közötti összefüggés . . . . . . . . . . . . . . . . . . . 16 5.2. Cohen-Daubechies-Feauveau biortogonális wavelet konstrukció . . 16

5.2.1. Biortogonális spline waveletek . . . . . . . . . . . . . . . . 17 5.3. Tökéletes visszaállítás . . . . . . . . . . . . . . . . . . . . . . . . 17

5.3.1. Vetterli tétele . . . . . . . . . . . . . . . . . . . . . . . . . 18

6. Wavelet lifting 21 6.1. Polifázis reprezentáció . . . . . . . . . . . . . . . . . . . . . . . . 22 6.2. Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.3. Laurent polinom felbontás . . . . . . . . . . . . . . . . . . . . . . 25 6.4. Faktorizációs algoritmus . . . . . . . . . . . . . . . . . . . . . . . 26

6.4.1. Haar wavelet felbontása . . . . . . . . . . . . . . . . . . . 27

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ációnak azon tulajdonsága, hogy a transzformáció eredménye egy egy változós függvény, ami az intenzitást mutatja a frekvencia függvényében. Azaz, elvész az idő információ, 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 stacioná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-stacionárius, átmeneti jellemzőket is, a szignál sodródhat, trendek figyelhető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 frekvencia kapcsolatá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ációt, hogy az mindig csak egy rövid szakaszát analizálja. Formálisan vett egy w (t) kompakt, sima függvényt^{2}, s vizsgálta az alábbi kifejezést:

X(τ, ω) = ∫_{−∞}^{∞} 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 frekvencia 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 frekvenciára. Egy szélesebb ablak pontosabb információt szolgáltat a jelben megbújó frekvenciákról, viszont az idő felbontása kevésbé pontos. Míg egy szűkebb ablakkal kisebb frekvencia 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áció, ahol a fix ablak méret - felbontás helyett a frekvenciától függő felbontást lehet alkalmazni. Azaz magas frekvenciák esetén jobb idő-érzékenységet, míg alacsonyabb frekvenciájú változások esetén kevésbé pontos időbeli lokalizációt kaphatunk.

1Short-Time Fourier Transformation

2ilyen „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))

2. Definíciók

A továbbiakban a következő jelöléseket használjuk a konzisztencia kedvéért: a[n]-nel jelöljük a sorozatokat, n∈ ℤ, míg a(n)-nel, ha n ∈ ℝ. Egy f függvény Fourier transzformáltját f̂-vel, egy a[n] sorozat megfordítottját ā[n] = a[−n]- nel, valamint legyen

x̌[n] = \begin{cases}0 & n = 2p + 1 \\ x[n] & n = 2p \end{cases}

L egy idő invariáns lineáris operátor, ha egy p-vel eltolt, f_{p}[n] = f[n − p] mintára, a kimenet is eltoltja lesz:

Lf_{p}[n] = Lf[n − p]

Impulzus válasz - minden f[n] szignál felírható eltolt Dirac függvények összegeként:

f[n] = ∑_{p=−∞}^{+∞} f[p]δ[n − p]

Legyen h[n] := Lδ[n] a diszkrét impulzus válasz, az L linearitása és idő invarianciája miatt:

Lf[n] = ∑_{p=−∞}^{+∞} f[p]h[n − p] = f ⋆ h[n]

Azaz, egy diszkrét idő invariáns operátor felírható diszkrét konvolúcióval, s ha h[n] véges tartójú, akkor Lf[n] véges sok művelettel számolható,ezt nevezik véges impulzus válasznak (FIR^{3}). L kauzális ha Lf[p] csak az n ≤ p f[n] értékektől függ, ekkor h[n] = 0 ha n < 0. A szűrőt stabilnak nevezzük, ha korlátos bemenetre, korlátos kimenetet produkál, ami egyenértékű azzal, hogy ∑_{n=−∞}^{+∞} |h [n]| < +∞.

3Finite Impulse Response

L szűrőnek a sajátvektorai diszkrét szinusz hullámok:e_{ω}[n] = e^{iωn}, mivel teljesül, hogy:

Le_{ω}[n] = ∑_{p=−∞}^{+∞} e^{iw(n−p)}h[p] = e^{iωn} ∑_{p=−∞}^{+∞} h[p]e^{−iωp}

ahol a sajátérték a következő Fourier sor, amit a szűrő transzfer függvényének nevezünk:

ĥ(ω) := ∑_{p=−∞}^{+∞} h[p]e^{−iωp}

Riesz bázis. Az ortogonális bázisnál gyengébb feltétel a Riesz bázis feltételezése, amelynek a definíciója: legyen {e_{n}}_{n∈ℕ} vektor sorozat egy H Hilberttérben, ami lineárisan független, valamint lineáris kombinációi sűrűek H-ban, és létezik A > 0 és B > 0 úgy, hogy f ∈ H esetén található egy λ[n] sorozat úgy,hogy

f = ∑_{n=0}^{+∞} λ[n]e_{n}

és

\frac{1}{B} ∥f∥^{2} ≤ ∑_{n} |λ[n]|^{2} ≤ \frac{1}{A} ∥f∥^{2}

Ekkor a Riesz reprezentációs tétel szerint létezik ẽ_{n} vektor sorozat, hogy λ[n] = ⟨f, ẽ_{n}⟩, ami szintén Riesz bázist alkot, s az eredeti bázis duálisának nevezik, valamint igaz rá, hogy:

f = ∑_{n=0}^{+∞} ⟨f, e_{n}⟩ ẽ_{n} = ∑_{n=0}^{+∞} ⟨f, ẽ_{n}⟩ e_{n}

3. Változó felbontás sorozat ^{4}

Egy {V_{j}}_{j∈ℤ} felbontás sorozat alatt L^{2}(ℝ) egymásba ágyazott altereit értjük, amire igaz, hogy monoton növekedő alterei L^{2}(ℝ)-t:

V_{j−1} ⊂ V_{j} ⊂ … ⊂ L^{2}(ℝ)

azaz egy finomabb felbontás tartalmazza mindazt az információt, ami egy durvább közelítés előállításához szükséges,

4Multiresolution analysis

⋂_{j} V_{j} = \{0\}, \overline{⋃_{j} V_{j}} = L^{2}(ℝ)

azaz - ha P_{V_{j}}(f)-fel jelöljük f -nek V_{j}-re való ortogonális vetületét - ^{5}

lim_{j→∞} ∥f − P_{V_{j}} (f)∥ = 0

avagy egy függvény közelítései konvergálnak az eredeti függvényhez.

f(t) ∈ V_{j} ⟺ f(2t) ∈ V_{j+1}
f(t) ∈ V_{0} ⟺ f(t − k) ∈ V_{0} k ∈ ℤ

azaz V_{j} eltolás invariáns \frac{k}{2^{j}} -vel való eltolásokra,

∃ϕ(t) : {ϕ(t − k)} ortonormális bázisa V_{0}-nak

Ekkor a ϕ(t) -t skála függvénynek nevezzük. Ez a skála függvény generálja a többi V_{j} térnek is egy-egy ortonormált bázisát, jelöljük ezt {ϕ_{j,k}(t)}-vel, ahol értelemszerűen: ϕ_{j,k}(t) = 2^{j/2}ϕ(2^{j}t − k), ami a feltételekből következik.

Mivel V_{0} ⊂ V_{1}ezért minden V_{0}-beli függvény kifejezhető a V_{1} bázisfüggvényei segítségével, speciálisan a skála függvény is:

ϕ(t) = ∑_{k} h[k]ϕ_{1,k}(t) = \sqrt{2} ∑_{k} h[k]ϕ(2t − k)  (3.1)

Ezt a képletet dilatációs^{6} avagy finomítási^{7} egyenletnek nevezzük. A h[k]együtthatókat a ϕ_{1,k}(t) ortonormalitásából számolhatjuk, skalár szorzat segítségével :

h[k] = ⟨ϕ_{1,k}, ϕ⟩ = \sqrt{2} ∫_{−∞}^{∞} ϕ(t)ϕ(2t − k)dt  (3.2)

A (3.1)-t integrálva t szerint, kapjuk, hogy

\frac{1}{\sqrt{2}} = ∑_{k} h[k]

5f_{j} ∈ V_{j} ortogonális vetülete f -nek, ha minimalizálja a ∥f_{j} − f∥ kifejezést

6dilation equation

7refinement equation

valamint, ha (3.1)-t ϕ(t − l)-vel megszorozzuk, és integráljuk t szerint, akkor:

∫_{−∞}^{+∞} ϕ(t)ϕ(t − l)dt = 2 ∫_{−∞}^{+∞} ∑_{k} ∑_{k′} h[k]h[k′]ϕ(2t − k′)ϕ(2t − 2l − k)dt
= ∑_{k} h[k]h[k + 2l]

újra felhasználva, hogy {ϕ(t − k)} ortogonális, kapjuk, hogy

∑_{k} h[k]^{2} = 1

és

∑_{k} h[k]h[k + 2l] = 0, l ≠ 0

3.1. Skála függvény meghatározása dilatációs együtthatókból

Egy kompakt tartójú skála függvény kielégíti a következő dilatációs egyenletet:

ϕ(t) = ∑_{k=0}^{N} \sqrt{2}h_{k}ϕ(2t − k) = ∑_{k=0}^{N} c_{k}ϕ(2t − k)

ahol a tartó [0..N]. Ezt t = 0..N felírva kapjuk, a

ϕ(i) = ∑_{k} c_{k}ϕ(2i − k) = ∑_{j} c_{2t−j}ϕ(j) i = 0..N

lineáris egyenletrendszert, aminek egy egy saját értékű saját vektora adja meg a keresett ϕ(i) értékeket. Ebből az N + 1 ϕ értékből, valamint a dilatációs egyenlet segítségével tetszőleges t -re kiszámolhatjuk ϕ(t)-t - {ϕ(tn) |n ∈ ℤ}esetén számolható \{ϕ(\frac{tn}{2}) |n ∈ ℤ\}- s feltehetjük, hogy ϕ folytonos, ami a Haar esetet leszámítva teljesül is.

3.2. Különbség tér^{8}

Ha egy f(t) V_{j}-beli közelítését P_{V_{j}}f(t)-vel jelöljük, akkor az d_{j}(t) = P_{V_{j+1}}f(t)− P_{V_{j}}f(t)-vel jelölt különbség függvény, tartalmazza a részleteket 2^{−(j+1)} felbontásban. Azaz, felbonthatjuk a V_{j+1} teret

V_{j+1} = V_{j} ⨁ W_{j}

8detail space

alakban, ahol W_{j}-t a j szinten levő felbontási térnek nevezzük, s ez persze merőleges V_{j}-re. A felbontást folytathatjuk tovább is, így kapjuk, hogy

V_{j} = V_{j−K} ⨁_{k=1}^{K} W_{j−k}

ahol a W_{j}alterek továbbra is ortogonálisak V_{j′}-re, ha j ≥ j′, s emiatt egymásra is: W_{j} ⊥ W_{j′}ha j ≠ j′. A V_{j}-kre kikötött feltételek miatt, a W_{j} egy bázisából könnyen kaphatunk W_{j+1}egy bázisát átskálázással. s ha {ψ_{j,k}(t)|k = −∞...∞}- val jelöljük W_{j} ortonormált bázisát, akkor adódik, hogy ψ_{j,k}(t) = 2^{j/2}ψ(2^{j}t−k). Így L^{2}(ℝ)-nek egy ortonormált bázisát kapjuk meg : {ψ_{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)} ⊆ W_{0} ⊂ V_{1}

ezért ψ kifejezhető V_{1} bázis függvényeinek segítségével a következőképpen:

ψ(t) = ∑_{k} g[k]ϕ_{1,k}(t) = \sqrt{2} ∑_{k} g[k]ϕ(2t − k)  (4.1)

ahol a g_{k} együtthatók számolhatók ϕ(2t − k) ortonormalitása miatt skalárszorzattal számolhatók:

g[k] = ⟨ϕ_{1,k}, ψ⟩ = \sqrt{2} ∫_{−∞}^{∞} ψ(t)ϕ(2t − k)dt  (4.2)

Így egy a skála függvényhez és dilatációs együtthatók közötti összefüggéshez nagyon hasonló kapcsolatot 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 V_{j} 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 frekvencia tartományra Fourier-transzformáció segítségével.

ϕ̂(ω) = ∑_{k} \sqrt{2}h[k] ∫_{−∞}^{∞} ϕ(2t − k)e^{−iωt}dt =  (4.3)
= \frac{1}{\sqrt{2}}(∑_{k} h[k]e^{−ik \frac{ω}{2}} ) ∫_{−∞}^{∞} ϕ(2t − k)e^{−i(2t−k) \frac{ω}{2}} d(2t) (4.4)
= \frac{1}{\sqrt{2}}ĥ(\frac{ω}{2} )ϕ̂(\frac{ω}{2} )  (4.5)

9mother wavelet

ahol

ĥ(ω) = ∑_{k} h[k]e^{−ikω}  (4.6)

, s ϕ̂(ω) illetve ψ̂(ω) ϕ(t) és ψ(t) Fourier transzformáltjai. Ekkor (4.1)-t szintén írhatjuk ilyen formába:

ψ̂(ω) = \frac{1}{\sqrt{2}}ĝ(\frac{ω}{2} )ϕ̂(\frac{ω}{2} )  (4.7)

ahol szintén

ĝ(ω) = ∑_{k} g[k]e^{−ikω}

Ekkor az ϕ(t) ortogonalitása ϕ(t − k)-ra így fogalmazható:

δ_{k,0} = ∫_{−∞}^{∞} ϕ(t)\overline{ϕ(t − k)}dt = \frac{1}{2π} ∫_{−∞}^{∞} ϕ̂(ω)\overline{ϕ̂(ω)}e^{iωk}dω =
= \frac{1}{2π} ∫_{0}^{2π} ∑_{l=−∞}^{∞} |ϕ̂(ω + 2πl)|^{2} e^{iωk}dω

jelöljük a belső formulát kiemelve:

A_{ϕ}(ω) = ∑_{l=−∞}^{∞} |ϕ̂(ω + 2πl)|^{2} ≥ 0

ahol A_{ϕ}(ω) egy 2π periódusú kifejezés lesz. Így az ortogonalitást úgy írhatjuk fel, hogy

δ_{k,0} = \frac{1}{2π} ∫_{0}^{2π} A_{ϕ}(ω)e^{iωk}dω

azaz, ha

A_{ϕ}(ω) = ∑_{l=−∞}^{∞} |ϕ̂(ω + 2πl)|^{2} = 1  (4.8)

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 {V_{j}}_{j∈ℤ} többszintű felbontás, {θ(t − n)}_{n∈ℤ} Riesz bázisa V_{0}- nak, valamint legyen ϕ(t) olyan függvény, melynek Fourier transzformáltjára teljesül, hogy

ϕ̂(ω) = \frac{θ̂(ω)}{(∑_{k=−∞}^{∞} |θ̂(ω + 2kπ)|^{2})^{1/2}}

jelöljük

ϕ_{j,n}(t) = \frac{1}{\sqrt{2}}ϕ (\frac{t − n}{2^{j}})

ekkor {ϕ_{j,n}(t)}_{n∈ℤ} ortogonális bázisa V_{j}-nek j ∈ ℤ-re. Az előbbi gondolatmenet miatt ugyanis már ϕ̂(ω) le van normálva A_{θ}(ω)-val, így lesz A_{ϕ}(ω) = 1.

4.2. Ortogonalitás dilatációs együtthatókból

Az (4.8)-t felírhatjuk (4.3) segítségével is, méghozzá:

1 = ∑_{l=−∞}^{∞} |ϕ̂(ω + 2πl)|^{2} = ∑_{l=−∞}^{∞} |\frac{1}{\sqrt{2}}ĥ(\frac{ω + 2πl}{2} )ϕ̂(\frac{ω + 2πl}{2} )|^{2} =
= \frac{1}{2} ∑_{l=−∞}^{∞} |ĥ(ϑ + πl)|^{2} |ϕ̂(ϑ + πl)|^{2}

mivel minden ω-ra 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 = \frac{1}{2} ∑_{l=−∞}^{∞} |ĥ(ϑ + 2lπ)|^{2} |ϕ̂(ϑ + 2lπ)|^{2} +

+\frac{1}{2} ∑_{l=−∞}^{∞} |ĥ(ϑ + (2l + 1)π)|^{2} |ϕ̂(ϑ + (2l + 1)π)|^{2}

s mivel tudjuk, hogy ĥ(ω) 2π periódusú, ez tovább egyszerűsödik:

1 = \frac{1}{2} |ĥ(ϑ)|^{2} ∑_{l=−∞}^{∞} |ϕ̂(ϑ + 2lπ)|^{2} + \frac{1}{2} |ĥ(ϑ + π)|^{2} ∑_{l=−∞}^{∞} |ϕ̂((ϑ + π) + 2lπ)|^{2}

ide behelyettesítve (4.8)-t kapjuk, hogy:

2 = |ĥ(ϑ)|^{2} + |ĥ(ϑ + π)|^{2}  (4.9)

4.3. Ortogonalitás wavelet együtthatókból

Hasonlóan a wavelet függvényre is levezethető ortogonalitási feltétel:

∑_{l=−∞}^{∞} |ψ̂(ω + 2πl)|^{2} = 1

avagy:

2 = |ĝ(ϑ)|^{2} + |ĝ(ϑ + π)|^{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 = ∫_{−∞}^{∞} ϕ(t)\overline{ψ(t − k)}dt =
= \frac{1}{2π} ∫_{−∞}^{∞} ϕ̂(ω)\overline{ψ̂(ω)}e^{iωk}dω =
= \frac{1}{2π} ∫_{−0}^{2π} ∑_{l=−∞}^{+∞} ϕ̂(ω + 2πl)\overline{ψ̂(ω + 2πl)}e^{iωk}dω

ebből következik, hogy

0 = ∑_{l=−∞}^{+∞} ϕ̂(ω + 2πl)\overline{ψ̂(ω + 2πl)}

Hasonlóan felhasználva a dilatációs és wavelet függvény egyenlet együtthatóira vonatkozó képleteket, kapjuk, hogy :

ĥ(ω)\overline{ĝ(ω)} + ĥ(ω + π)\overline{ĝ(ω + π)} = 0  (4.11)

Ez az egyenlet kapcsolja össze a dilatációs együtthatókat a wavelet függvény együtthatóival.

4.4. Dilatációs és wavelet együtthatók közötti összefüggés

Abban az esetben, ha ĝ(ω) = α(ω)\overline{ĥ(ω + π)}, ahol α egy 2π periódusú függvény, mire teljesül, hogy |α(ω)|^{2} = 1 és α(ω) = −α(ω + π), akkor könnyen látható, hogy teljesül (4.11). Ilyen α-nak választhatjuk az−e^{iω} függvényt, ami a számolást igen megkönnyíti. Mivel, ha beírjuk (4.6)-t a kifejezésbe:

ĝ(ω) = −e^{−iω}\overline{ĥ(ω + π)}
= −e^{−iω} ∑_{k} h[k]e^{ik(ω+π)}
= ∑_{k} h[k](−1)^{1−k}e^{−iω(1−k)}
= ∑_{k} h[1 − k](−1)^{k}e^{−ikω}
= ∑_{n} g[n]e^{−inω}

azaz, ebben az esetben:

g[n] = (−1)^{n}h[1 − n]

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 ψ ∈ L^{2} (ℝ) függvény, melyre:

∫_{−∞}^{+∞} ψ(t)dt = 0

valamint ∥ψ∥_{2} = 1, s kompakt tartójú, mely tartalmazza t = 0-t. Ennek a függvénynek az eltoltjai és skálázottjai:

ψ_{u,s}(t) = \frac{1}{\sqrt{s}}ψ (\frac{t − u}{s})

- szintén 1 normájúak - lesznek az idő - frekvencia atomok. S a wavelet transzformáltja egy f függvénynek pedig

W f(u, s) = ⟨f, ψ_{u,s}⟩ = ∫_{−∞}^{+∞} f(t)\frac{1}{\sqrt{s}}ψ^{⋆} (\frac{t − u}{s}) dt = f ⋆ \overline{ψ}_{s} (u)

ahol

\overline{ψ}_{s}(t) = \frac{1}{\sqrt{s}}ψ^{⋆} (\frac{−t}{s})

Az a feltételezés, hogy a ψ tartója kompakt, s egy 0 környezetére korlátozódik ( ∫_{−p}^{p} |ψ(t)|^{2} dt > 1 − ε), azzal a szemléletes tulajdonsággal jár, hogy W f(u, s) értékét f -nek az[\frac{u−p}{s}, \frac{u+p}{s}] tartományon felvett értéke határozza meg.

4.6. Gyors Ortogonális Wavelet Transzformáció ^{10}

Az FWT egy olyan algoritmus, amivel kiszámolható egy véges felbontáson mintavételezett jel wavelet együtthatóit, iteratívan. Minden P_{V_{j}}f közelítéshez visszaad egy durvább P_{V_{j+1}}f közelítést, és a wavelet együtthatókat, amelyeket P_{W_{j+1}}f tartalmaz.

Állítás (Mallat). Legyen {ψ_{j,n}}_{n∈ℤ} és {ϕ_{j,n}}_{n∈ℤ} ortonormális bázisa W_{j}-nek és V_{j}-nek, s az ezen alterekbe való vetítés együtthatóit jelöljük :

a_{j}[n] = ⟨f, ϕ_{j,n}⟩

10FWT - Fast Wavelet Transform

és

d_{j}[n] = ⟨f, ψ_{j,n}⟩

ekkor a felbontáshoz az együtthatókat megkaphatjuk így:

a_{j+1}[p] = ∑_{n=−∞}^{+∞} h[n − 2p]a_{j}[n] = (a_{j} ⋆ h̄) [2p]  (4.12)

d_{j+1}[p] = ∑_{n=−∞}^{+∞} g[n − 2p]a_{j}[n] = (a_{j} ⋆ ḡ) [2p]  (4.13)

valamint az a_{j+1}, d_{j+1} sorozatokból az a_{j}-t számolhatjuk:

a_{j}[p] = ∑_{n=−∞}^{+∞} h[p − 2n]a_{j+1}[n] + ∑_{n=−∞}^{+∞} g[p − 2n]d_{j+1}[n] =
= ǎ_{j+1} ⋆ h[p] + ď_{j+1} ⋆ g[p]

Az (4.12) belátáshoz a következők kellenek: Minden ϕ_{j+1,p} ∈ V_{j+1} ⊂ V_{j} felírható V_{j} ortogonális bázisában ebben a formában:

ϕ_{j+1,p} = ∑_{n=−∞}^{+∞} ⟨ϕ_{j+1,p}, ϕ_{j,n}⟩ ϕ_{j,n}  (4.14)

a skalárszorzatot külön felírva kapjuk, hogy

⟨ϕ_{j+1,p}, ϕ_{j,n}⟩ = ∫_{−∞}^{+∞} \frac{1}{\sqrt{2^{j+1}}} ϕ (\frac{t}{2^{j+1}} − p) \frac{1}{\sqrt{2^{j}}} ϕ^{⋆} (\frac{t}{2^{j}} − n) dt =

új változót bevezetve: s := \frac{t}{2^{j}} − 2p

= ∫_{−∞}^{+∞} ϕ (\frac{s}{2}) ϕ (s − n + 2p) ds =
= ⟨\frac{1}{\sqrt{2}}ϕ (\frac{s}{2}) , ϕ (s − n + 2p)⟩ = h[n − 2p]

visszaírva (4.14)-ba kapjuk:

ϕ_{j+1,p} = ∑_{n=−∞}^{+∞} h[n − 2p]ϕ_{j,n}

ezt f-fel skalár szorozva:

a_{j+1}[p] = ⟨f, ϕ_{j+1,p}⟩ = ⟨f, ∑_{n=−∞}^{+∞} h[n − 2p]ϕ_{j,n}⟩ =
= ∑_{n=−∞}^{+∞} h[n − 2p] ⟨f, ϕ_{j,n}⟩ = ∑_{n=−∞}^{+∞} h[n − 2p]a_{j}[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, frekvencia szerint szétválasztja a jelet, egy magas frekvenciáktól - „zajtól” - mentes, és egy magas frekvenciá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 filtereket feltételezve, könnyen implementálható, s a konvolúció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 ⟨e_{i}, e_{j}⟩ = δ_{i,j} teljesüljön. Biortogonális esetben, nem egyetlen - ortogonális - bázisunk van, hanem egy bázis: {e_{i}}, és annak duálisa: {ẽ_{i}}, melyekre azt követeljük meg, hogy ⟨e_{i}, ẽ_{j}⟩ = δ_{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 {ϕ_{j,k}(t)} bázist alkot V_{J}-ben, és {ψ_{j,k}(t)} pedig W_{j}-ben, ennek megfelelően szeretnénk definiálni a duális finomodó felbontást, valamint a duális {Ṽ_{j}} és {W̃_{j}} altereket, valamint a duális skála ϕ̃ és wavelet ψ̃ függvényt. Méghozzá úgy, hogy

⟨ϕ̃_{j,k}, ϕ_{j,l}⟩ = δ_{k,l}  (5.1)

és

⟨ψ̃_{j,k}, ψ_{m,l}⟩ = δ_{j,m,}δ_{k,l}  (5.2)

valamint V_{j} ⊥ W̃_{m} és Ṽ_{j} ⊥ W_{m} :

⟨ψ̃_{j,k}, ϕ_{m,l}⟩ = 0

és

⟨ϕ̃_{j,k}, ψ_{m,l}⟩ = 0

ahol ψ̃_{j,k}(t) = 2^{j/2}ψ̃(2^{j}t − k) és ϕ̃_{j,k} = 2^{j/2}ϕ̃(2^{j}t − k). Definíció szerint ezekre is fel lehet írni a dilatációs (3.1) és wavelet (4.1) egyenleteket is, azaz:

ψ̃(t) = ∑_{k} g̃[k]ϕ̃_{1,k}(t) = \sqrt{2} ∑_{k} g̃[k]ϕ̃(2t − k)  (5.3)

és

ϕ̃(t) = ∑_{k} h̃[k]ϕ̃_{1,k}(t) = \sqrt{2} ∑_{k} h̃[k]ϕ̃(2t − k)  (5.4)

Itt a következőképpen számolhatjuk az együtthatókat:

g̃[k] = ⟨ϕ_{1,k}, ψ̃⟩ = \sqrt{2} ∫_{−∞}^{∞} \overline{ϕ(2t − k)}ψ̃(t)dt

valamint

h̃[k] = ⟨ϕ_{1,k}, ϕ̃⟩ = \sqrt{2} ∫_{−∞}^{∞} \overline{ϕ(2t − k)}ϕ̃(t)dt

Hasonlóan, amikor Fourier transzformációval a frekvencia tartományra térünk át, kapjuk:

ˆψ̃(ω) = \frac{1}{\sqrt{2}} ˆg̃(\frac{ω}{2} ) ˆϕ̃(\frac{ω}{2} )  (5.5)

és

ˆϕ̃(ω) = \frac{1}{\sqrt{2}} ˆh̃(\frac{ω}{2} ) ˆϕ̃(\frac{ω}{2} )  (5.6)

képleteket a duális skála és függvényekre. Ahol ˆ g̃ analóg módon van definiálva g̃-ból, ahogy ĝ is g-ből. Ekkor (5.1)-t felírva:

δ_{k,0} = ∫_{−∞}^{∞} ϕ̃(t)\overline{ϕ(t − k)}dt = \frac{1}{2π} ∫_{−∞}^{∞} ˆ ϕ̃(ω)\overline{ϕ̂(ω)}e^{iωk}dω =
= \frac{1}{2π} ∫_{0}^{2π} ∑_{l=−∞}^{∞} ˆ ϕ̃(ω + 2πl)\overline{ϕ̂(ω + 2πl)}e^{iωk}dω

azaz:

∑_{l=−∞}^{+∞} ˆ ϕ̃(ω + 2πl)\overline{ϕ̂(ω + 2πl)} = 1

hasonlóan:

∑_{l=−∞}^{+∞} ˆ ψ̃(ω + 2πl)\overline{ψ̂(ω + 2πl)} = 1

valamint

∑_{l=−∞}^{+∞} ˆ ψ̃(ω + 2πl)\overline{ϕ̂(ω + 2πl)} = 0 és ∑_{l=−∞}^{+∞} ˆ ϕ̃(ω + 2πl)\overline{ψ̂(ω + 2πl)} = 0

Hasonlóan a (4.2) szakaszban végrehajtott átalakításokkal, kapjuk, hogy

ˆh̃(ω)\overline{ĥ(ω)} + ˆ h̃(ω + π)\overline{ĥ(ω + π)} = 1  (5.7)
ˆg̃(ω)\overline{ĝ(ω)} + ˆ g̃(ω + π)\overline{ĝ(ω + π)} = 1
ˆg̃(ω)\overline{ĥ(ω)} + ˆ g̃(ω + π)\overline{ĥ(ω + π)} = 0
ˆh̃(ω)\overline{ĝ(ω)} + ˆ h̃(ω + π)\overline{ĝ(ω + π)} = 0

5.1. Együtthatók közötti összefüggés

Biortogonális esetben is feltehetjük, hogy ĝ (ω) = −e^{−iω}ˆh̃ (ω + π) és ˆ g̃ (ω) = −e^{−iω}ĥ (ω + π), így egyszerűen számolható filtereket kapunk : g[n] = (−1)^{n} h̃ [1 − n] és g̃[n] = (−1)^{n} h [1 − n].

Ortogonális esetben láttuk, hogy a waveleteket a filter együtthatókból lehetett számolni, analóg módon zajlik itt is, azzal a különbséggel, hogy plusz megkötésekkel is élhetünk a filterünkre. A szimmetria érdekében kiköthetjük például, hogy legyen h[n] = h[−n], (ha a filter hossza páratlan), vagy h[n + 1] = h[−n] (n ≥ 0) (ha a filter hossza páros). Ekkor ĥ(ω) (vagy ˆ h̃(ω)) valós polinom cos (ω)-ra nézve, ha páratlan, míg e^{iω/2} cos (ω/2)-szorosa egy cos (ω)-ra valós polinomnak, ha páros a filter. 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} = cos^{2l} (ω/2)

Azaz olyan biortogonális waveletet keresünk amelyre teljesül (5.7) valamint a következő formába írhatóak:

ĥ (ω) = e^{−iω/2} (cos \frac{ω}{2} )^{N+k} q_{0} (cos (ω))

és

ˆh̃ (ω) = e^{−iω/2} (cos \frac{ω}{2} )^{Ñ+k} q̃_{0} (cos (ω))

ahol N = 2l,Ñ = 2l̃ és k = 0,ha a filter páratlan, k = 1 ha páros valamint q_{0}é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-Daubechies-Feauveau biortogonális wavelet konstrukció

Legyen P (e^{iw}) és P̃(e^{iw}) szigorúan pozitív polinomok, úgy hogy:

|ĥ (\frac{ω}{2} )|^{2} P (e^{iω/2}) + |ĥ (\frac{ω}{2} + π)| P (e^{i(ω/2+π)})^{2} = 2P (e^{iω})

és

|ˆh̃ (\frac{ω}{2} )|^{2} P̃ (e^{iω/2}) + |ˆh̃ (\frac{ω}{2} + π)| P̃ (e^{i(ω/2+π)})^{2} = 2P̃(e^{iω})

valamint

inf_{ω∈[−π/2,π/2]} |ĥ (ω)| > 0

és

inf_{ω∈[−π/2,π/2]} |ˆh̃ (ω)| > 0

akkor a

ϕ̂(ω) = ∏_{p=1}^{+∞} \frac{ĥ(2^{−p}ω)}{\sqrt{2}}  (5.8)

és

ˆϕ̃(ω) = ∏_{p=1}^{+∞} \frac{ˆh̃(2^{−p}ω)}{\sqrt{2}}  (5.9)

által definiált függvények biortogonális rendszert alkotnak :

⟨ϕ(t), ϕ̃(t − n)⟩ = δ[n]

és a {ψ_{j,n}}_{(j,n)∈ℤ^{⊭}} és {ψ̃_{j,n}}_{(j,n)∈ℤ^{⊭}}biortogonális Riesz bázisa az L(ℝ^{2})-nek, valamint ϕ̂ ∈ L^{2} (ℝ). A bizonyítás megtalálható itt:[1].

5.2.1. Biortogonális spline waveletek

Egy ilyen megoldást fogunk röviden kiszámolni. Válasszuk

ĥ (ω) = exp (\frac{−ikω}{2} ) cos (\frac{ω}{2} )^{N}

ahol k = 1 vagy 0 N párosságától függően. Azaz q_{0} = 1. Ekkor a skála függvény megkapjuk (5.8)-ből egy N − 1 fokú spline függvény :

ϕ̂ (ω) = exp (\frac{−ikω}{2} ) (\frac{sin (ω/2)}{ω/2})^{N}

Mivel ψ lineáris kombinációja ϕ (2t − n) spline függvényeknek, ezért az is kompakt tartójú, hasonló fokú spline függvény. Felhasználva (5.7)-t kapjuk: (legyen M = (N + Ñ)/2)

ˆh̃ (ω) = exp (\frac{−ikω}{2} ) cos (\frac{ω}{2} )Ñ ∑_{k=0}^{M−1} ( \begin{matrix}M − 1 + k \\ k \end{matrix} ) sin (\frac{ω}{2} )^{2k}

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 az eredeti jelet. Ez ortogonális esetben azzal a problémával járt, hogy - a Haar filteren kívül - a quadratura tükör filterek (QMF) ^{11} nem rendelkeznek véges impulzus válasszal ^{12}.

Az előző szakaszokban vizsgált biortogonális wavelet függvény párokat akarjuk két csatornás szűrő rendszerekként ^{13} felhasználni, méghozzá úgy, hogy a transzformáció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 csatornás szűrő rendszer konvolválja az a_{0} szignált a h̄[n] = h[−n] low-pass filterrel, valamint a ḡ[n] = g[−n] high-pass filterrel, aztán ritkítja 2-vel a kimenetet:

a_{1}[n] = a_{0} ⋆ h̄[n]  (5.10)

és

d_{1}[n] = a_{0} ⋆ ḡ[n]  (5.11)

Ezután a visszaállítás során az eredeti szignál úgy áll elő, hogy a nullákkal feltöltött a_{1},d_{1} jelsorozatot a duális high-pass illetve low-pass filterrel konvolváljuk:

ã_{0}[n] = ǎ_{1} ⋆ h̃[n] + ď_{1} ⋆ g̃[n]  (5.12)

5.3.1. Vetterli tétele

Egy szűrő rendszer akkor és csak akkor állítja vissza az eredeti szignált, ha

ĥ^{⋆} (ω + π) ˆ h̃ (ω) + ĝ^{⋆} (ω + π) ˆ g̃ (ω) = 0  (5.13)

és

ĥ^{⋆} (ω) ˆ h̃ (ω) + ĝ^{⋆} (ω) ˆ g̃ (ω) = 2  (5.14)

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ω) = ∑_{n=−∞}^{+∞} x[2n]e^{−i2nω} = \frac{1}{2} (x̂ (ω) + x̂ (ω + π))  (5.15)

A 0-ák beillesztését így írhatjuk fel egy jelsorozatba :

x̌[n] = \begin{cases}0 & n = 2p + 1 \\ x[n] & n = 2p \end{cases}

11quadrature mirror filter

12finite impulse response

132-channel filter bank

, ennek Fourier transzformáltja pedig:

ŷ(ω) = ∑_{n=−∞}^{+∞} x[n]e^{−i2nω} = x̂ (2ω)  (5.16)

A tétel bizonyításához először a_{0} , a_{1}és d_{1} Fourier transzformáltját hozzuk egymással kapcsolatba. Mivel h és g valós, ezért ĥ (−ω) = ĥ^{⋆} (ω) és ĝ (−ω) = ĝ^{⋆} (ω). Beírva (5.10) Fourier transzformáltjába (5.15)-t, kapjuk

â_{1} (2ω) = \frac{1}{2} (â_{0} (ω) ĥ^{⋆} (ω) + â_{0} (ω + π) ĥ^{⋆} (ω + π))

hasonlóan (5.11) Fourier transzformáltjába:

d̂_{1} (2ω) = \frac{1}{2} (â_{0} (ω) ĝ^{⋆} (ω) + â_{0} (ω + π) ĝ^{⋆} (ω + π))

Viszont (5.12) Fourier transzformáltjánál felhasználhatjuk (5.16)-t:

ˆã_{0} (ω) = â_{1} (2ω) ˆ h̃ (ω) + d̂_{1} (2ω) ˆ g̃ (ω)

Innen, az egészet egyetlen képletbe sűrítve kapjuk:

ˆã_{0} (ω) = \frac{1}{2} (â_{0} (ω) ĥ^{⋆} (ω) + â_{0} (ω + π) ĥ^{⋆} (ω + π)) ˆ h̃ (ω) +

\frac{1}{2} (â_{0} (ω) ĝ^{⋆} (ω) + â_{0} (ω + π) ĝ^{⋆} (ω + π)) ˆ g̃ (ω)

= \frac{1}{2} (ˆh̃ (ω) ĥ^{⋆} (ω) + ˆ g̃ (ω) ĝ^{⋆} (ω)) â_{0} (ω) +
\frac{1}{2} (ˆh̃ (ω) ĥ^{⋆} (ω + π) + ˆ g̃ (ω) ĝ^{⋆} (ω + π)) â_{0} (ω + π)

Ahhoz, hogy a_{0} = ã_{0} teljesüljön, az â_{0} (ω) együtthatójának 1-nek kell lennie, s az â_{0} (ω + π) -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 :

( \begin{matrix}ĥ (ω) & ĝ (ω) \\ ĥ (ω + π) & ĝ (ω + π) \end{matrix} ) ∗ ( \begin{matrix}ˆh̃^{⋆} (ω) \\ ˆg̃^{⋆} (ω) \end{matrix} ) = ( \begin{matrix}2 \\ 0 \end{matrix} )

Ha a Δ (ω) = ĥ (ω) ĝ (ω + π) − ĥ (ω + π) ĝ (ω)-val jelöljük a mátrix determinánsát, akkor a 2 × 2-es mátrixot invertálva :

( \begin{matrix}ˆh̃^{⋆} (ω) \\ ˆg̃^{⋆} (ω) \end{matrix} ) = \frac{2}{Δ (ω)} ( \begin{matrix}ĝ & (ω + π) \\ −ĥ (ω + π) \end{matrix} )  (5.17)

Azaz a rekonstrukciós filter akkor létezik, ha a determináns nem tűnik el minden ω ∈ [−π, π]-re.

Állítás

Tökéletes rekonstrukció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} filterek) - akkor a determináns egyszerűen számolható, s ebben az esetben létezik a ∈ ℝ és l∈ ℤ, hogy

ĝ (ω) = ae^{−i(2l+1)ω}ˆh̃^{⋆} (ω + π)

és

ˆg̃ (ω) = \frac{1}{a}e^{−i(2l+1)ω}ĥ^{⋆} (ω + π)

Bizonyítás

Ez úgy látható be, hogy (5.17)-t felírva:

ˆh̃^{⋆} (ω) = \frac{2}{Δ (ω)}ĝ (ω + π)  (5.19)

és

ˆg̃^{⋆} (ω) = \frac{−2}{Δ (ω)}ĥ (ω + π)  (5.20)

így:

ĝ (ω) ˆ g̃^{⋆} (ω) = −\frac{Δ(ω + π)}{Δ (ω)} ˆh̃^{⋆} (ω + π) ĥ (ω + π)

A Δ (ω) definíciója miatt Δ (ω + π) = −Δ (ω), így (5.14)-re alkalmazva kapjuk (5.18)-t.

Mivel egy véges impulzus válasszal rendelkező szűrő Fourier transzformáltja definíció szerint véges sorozata exp (±inω) alakú tagoknak. Így a Δ (ω) determináns is egy ilyen véges sorozat, valamint (5.19) miatt Δ^{−1} (ω) is az. S egy olyan véges sorozataexp (±inω) tagoknak, amelyeknek a reciproka is felírható véges sok exp (±inω) taggal, az csak egyetlen tagból állhat. S mivel Δ (ω + π) = −Δ (ω), ezért ennek a kitevőben levő n páratlan. Azaz, létezik olyan l ∈ ℤ és a∈ ℝ, hogy

Δ (ω) = −2a exp (i (2l + 1) ω)

ezt behelyettesítve (5.19) és (5.20)-be, kapjuk a bizonyítandó állítást.

14finite impulse response

Amennyiben a = 1 és l = 0 akkor (5.18)-t az időtartományra átírva - azaz a szűrő együtthatóira megfogalmazva az egyenlőséget :

g [n] = (−1)^{1−n} h̃ [1 − n] és g̃ [n] = (−1)^{1−n} h [1 − n]

Látható, hogyha megköveteljük a felbontási h szűrő legyen ugyanaz mint a rekonstrukciós h̃, akkor (5.18)-ből (4.10) 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ációk sorozatára. Ehhez az eddigi állításokat át kell fogalmazni Laurent polinomokra.

Egy adott h véges filterhez rendeljük a következő polinomot:

h(z) = ∑_{M}^{N} h[k]z^{−k}

Ezen polinom foka definiáljuk |h| = N − M-nek.

A valós együtthatós Laurent polinomok kommutatív gyűrűt alkotnak, viszont többnyire csak maradékosan lehet osztani, ráadásul nem is egyértelműen. Formálisan: ha van két Laurent polinom a(z) és b(z) ≠ 0, hogy |b (z)| ≤ |a (z)|, akkor mindig létezik egy olyan q (z) és r (z) polinom, amire |q (z)| = |a (z)| − |b (z)| és |r (z)| < |b (z)| úgy, hogy

a (z) = b(z)q(z) + r(z).  (6.1)

Magát a Laurent gyűrűt R [z, z^{−1}]-vel szokták jelölni. Egy Laurent polinom akkor, és csak akkor invertálható, hogyha egyetlen tagból áll, azaz |h| = 0. Egy két csatornás szűrő rendszer itt 2 × 2 -es mátrix lesz a gyűrű felett, amik az M (2; R [z, z^{−1}])-val 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 (5.14) alapján:

h (z) h̃ (z^{−1}) + g (z) g̃ (z^{−1}) = 2
h (z) h̃ (−z^{−1}) + g (z) g̃ (−z^{−1}) = 0

Legyen az M (z) modulációs mátrix a következő:

M (z) = [ \begin{matrix}h (z) & h (−z) \\ g (z) & g (−z) \end{matrix} ]

Hasonló legyen a duális M̃ (z) modulációs mátrix. Ekkor mátrixokkal az egyenlőség a következőképpen alakul:

M̃ (z^{−1})^{t} M (z) = 2I

azaz, mindkét mátrix része GL (2; R [z, z^{−1}])-nek, az invertálható mátrixok csoportjának.

6.1. Polifázis reprezentáció^{15}

Egy h filternek a polifázis reprezentációja alatt értsük a következőt:

h_{ps} (z) = ∑_{k} h[2k]z^{−k} és h_{pt} (z) = ∑_{k} h [2k + 1] z^{−k}

azaz a h_{ps} tartalmazza a h páros együtthatóit, míg a h_{pt} a páratlanokat. Ekkor írható

h (z) = h_{ps} (z^{2}) + z^{−1}h_{pt} (z^{2})

valamint

h_{ps} (z^{2}) = \frac{h (z) + h (−z)}{2}

és

h_{pt} (z^{2}) = \frac{h (z) − h (−z)}{2z^{−1}}

Legyen ezután a polifázis mátrix :

P (z) = ( \begin{matrix}h_{ps} (z) & g_{ps} (z) \\ h_{pt} (z) & g_{pt} (z) \end{matrix} )

így viszont teljesül, hogy

P (z^{2})^{t} = 1/2M (z) ( \begin{matrix}1 & z \\ 1 & −z \end{matrix} ) .

15polyphase representation

Hasonlóan definiá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})^{t} = I

Azaz P (z) invertálható, sőt feltehetjük, hogy det P (z) = 1, mivel mindig oszthatjuk g_{ps}(z)-t és g_{pt}(z)-t a determinánssal.

Tehát, egy FIR wavelet transzformáció megtalálása egyenértékű egy P (z) 1 determinánsú mátrix megtalálásával. A legkézenfekvőbb, ha P (z) = I, ebből h(z) = h̃(z) = 1 és g(z) = g̃(z) = z^{−1}. Ezt a transzformáció Lazy-wavelet transzformációnak nevezik, amikor gyakorlatilag csak 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 korrelálnak egymással, azaz lehetséges létrehozni egy ℙ prediktort, ami például csak a páros sorszámú elemekből (jelöljük x_{ps}-nek) próbálja megállapítani a páratlanokat (legyen ez x_{pt}). Természetesen ez a prediktor nem biztos, hogy tökéletes, így fel kell jegyezni az eltérést:

d = x_{pt} − ℙ(x_{ps}).

Visszaalakításkor persze a d eltérés és x_{ps} alapján megkaphatjuk a páratlanokat:

x_{pt} = ℙ(x_{ps}) + d

Ha ℙ 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

ℙ(x_{ps})[2k + 1] = \frac{(x [2k] + x [2k + 2])}{2},

s az eltérés pedig:

d[k] = x[2k + 1] − \frac{(x [2k] + x [2k + 2])}{2}.

Így kaptunk egy (x_{ps}, d) jel párt, ami még azzal a hiányossággal rendelkezik, hogy a frekvencia komponensek nem válnak el egymástól a két sorozatba. A d -ben ugyan a magas frekvencia található, de a x_{ps} csak az x megrítkításával jött létre, s így a mintavételezés hibája miatt oda magas frekvenciákból származó „zajok” is bekerülhetnek. Például a futó átlaga az x_{ps}-nek nem ugyanaz mint az eredeti x mintának. Ezt a helyzetet javítandó egy második lifting lépésben, egy 𝕌^{16}, d-re alkalmazott operátorral próbáljuk simítani x_{ps}-t:

a = x_{ps} + 𝕌(d)

. Ez a lépés is triviálisan visszafordítható, egy adott (a, d) párból x_{ps}megkapható:

x_{ps} = a − 𝕌(d).

Az előző példához visszatérve, ha a futó átlagokat akarjuk megőrizni, akkor úgy kell U-t választani, hogy:

a[k] = x[2k] + \frac{(d[k − 1] + d[k])}{4}.

Ezt az általános konstrukció, 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}x_{2k} + (1 − β_{k})x_{2k+1} alakú, ahol β_{k} a rács egyenletlenségeitől függ.

Definiáljuk egy (h, g) szűrő párt kiegészítőnek ^{17}, ha a megfelelő P (z) polifázis mátrix determinánsa 1.

Állítás

Legyen (h, g) kiegészítő szűrő pár, ekkor minden más, véges g′ szűrő akkor és csak akkor alkot h-val kiegészítő szűrő párt, ha

g′ (z) = g (z) + h (z) s (z^{2})

alakú, ahol s (z) 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 h_{ps} (z) s (z) lesz, míg a páratlan h_{pt} (z) s (z). A lifting alkalmazása után - amikor a ℙ 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) ( \begin{matrix}1 & s (z) \\ 0 & 1 \end{matrix} ) ,

16mint update

17complementary

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:

P̃′ (z) = P̃ (z) ( \begin{matrix}1 & 0 \\ −s (z^{−1}) & 1 \end{matrix} ) .

Ebből az új h̃ visszaállító szűrőre kapjuk, hogy:

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 h′ szűrő akkor és csak akkor alkot g-vel kiegészítő szűrő párt, ha

h′ (z) = h (z) + g (z) t (z^{2})

alakú, ahol t (z) 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:

P′ (z) = P (z) ( \begin{matrix}1 & 0 \\ t(z) & 1 \end{matrix} ) .

6.3. 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 a_{0} (z) és b_{0} (z) ≠ 0 két Laurent polinom, úgy hogy |a_{0} (z)| ≥ |b_{0} (z)| . Ismételjük a következő lépéseket:

a_{i+1} (z) := b_{i} (z)

b_{i+1} (z) := a_{i} (z) mod b_{i} (z) ,

akkor a_{n} (z) lesz a_{0} (z) és b_{0} (z) legnagyobb közös osztója, a legkisebb n-re, amire b_{n} (z) = 0 teljesül.

Mivel |b_{i+1} (z)| < |b_{i} (z)|, ezért létezik m, hogy |b_{m} (z)| = 0, azaz algoritmus véges idő alatt befejeződik. Legyen q_{i+1} (z) egy olyan polinom, amire q_{i+1} (z) = a_{i} (z) /b_{i} (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:

( \begin{matrix}a_{i+1} (z) \\ b_{i+1} (z) \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & −q_{i} (z) \end{matrix} ) ( \begin{matrix}a_{i} (z) \\ b_{i} (z) \end{matrix} ) .

Ezt iterálva kapjuk, hogy

( \begin{matrix}a_{n} (z) \\ 0 \end{matrix} ) = ∏_{i=n}^{1} ( \begin{matrix}0 & 1 \\ 1 & −q_{i} (z) \end{matrix} ) ( \begin{matrix}a_{0} (z) \\ b_{0} (z) \end{matrix} ) .

Azaz

( \begin{matrix}a_{0} (z) \\ b_{0} (z) \end{matrix} ) = ∏_{i=1}^{n} ( \begin{matrix}q_{i} (z) & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}a_{n} (z) \\ 0 \end{matrix} ) ,

így a_{n} (z) osztja a(z)-t és b(z)-t is, s ha a_{n} (z) egy tagú, akkor a(z) és b(z) relatív prímek.

6.4. Faktorizáció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 h_{ps} (z) és h_{pt} (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 h_{ps} (z)-ra és h_{pt} (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

( \begin{matrix}h_{ps} (z) \\ h_{pt} (z) \end{matrix} ) = ∏_{i=1}^{n} ( \begin{matrix}q_{i} (z) & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}K \\ 0 \end{matrix} ) .

Ha |h_{pt} (z)| > |h_{ps} (z)| akkor az első osztó, q_{1}(z) nulla, ezért az egyszerűség kedvéért feltehetjük, hogy |h (z)| páros. Egy h szűrőhöz megkaphatjuk a kiegészítő, g filtert, amire ez kell, hogy teljesüljön:

P (z) = ( \begin{matrix}h_{ps} (z) & g_{ps} (z) \\ h_{pt} (z) & g_{pt} (z) \end{matrix} ) = ∏_{i=1}^{n} ( \begin{matrix}q_{i} (z) & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}K & 0 \\ 0 & 1/K \end{matrix} ) .

Azt az egyszerű észrevételt felhasználva, hogy

( \begin{matrix}q_{i} (z) & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}1 & q_{i} (z) \\ 0 & 1 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}1 & 0 \\ q_{i} (z) & 1 \end{matrix} ) ,

írhatjuk a következő formába képletünket:

P (z) = (∏_{i=1}^{n/2} ( \begin{matrix}1 & q_{2i−1} (z) \\ 0 & 1 \end{matrix} ) ( \begin{matrix}1 & 0 \\ q_{2i} (z) & 1 \end{matrix} )) ( \begin{matrix}K & 0 \\ 0 & 1/K \end{matrix} ) .

Ahol a q_{2i−1} (z)-s tagok lifting, a q_{2i} (z)-s tagok duál lifting transzformációnak felel meg. Míg a K-s tag a triviális, egyetlen elemre korlátozott,K-val való szorzó, kiinduló szűrőnek felel meg, ezt a filtert, lazy filternek is nevezik. Összefoglalva, felírtuk a h szűrőhöz tartozó P (z) polifázis mátrixot, majd ezt felbontottuk egy lazy filteren végrehajtott lifting és duál lifting átalakítások sorozatára.

6.4.1. Haar wavelet felbontása

Erre a faktorizációra mutatunk példát Haar waveletből kiindulva. Ebben az esetben a következő szűrőink vannak:

h (z) = 1 + 1z^{−1}

g (z) = −\frac{1}{2} + \frac{1}{2}z^{−1}

h̃ (z) = \frac{1}{2} + \frac{1}{2}z^{−1}

g̃ (z) = −1 + 1z^{−1}

Azaz

P (z) = ( \begin{matrix}1 & −\frac{1}{2} \\ 1 & \frac{1}{2} \end{matrix} ) = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}1 & −\frac{1}{2} \\ 0 & 1 \end{matrix} ) .

Hasonlóan a visszaállítási szűrő rendszernél:

P̃ (1/z) = P (z)^{−1} = ( \begin{matrix}1 & \frac{1}{2} \\ 0 & 1 \end{matrix} ) ( \begin{matrix}1 & 0 \\ −1 & 1 \end{matrix} ) .

Ebből a filter transzformációkra azt kapjuk, hogy:

a′ [l] = x [2l]
d′ [l] = x[2l + 1]
d[l] = d′[l] − a′[l]
a[l] = a′[l] + \frac{1}{2}d[l]

ennek az inverze pedig ez lesz:

a′[l] = a[l] − \frac{1}{2}d[l]
d′[l] = d[l] + a′[l]
x [2l + 1] = d′[l]
x [2l] = a′ [l]

Hivatkozások

[1] J.C. Feauveau A. Cohen, I. Daubechies. Biorthogonal bases of compactly supported wavelets. Commun. on Pure and Appl. Math., 45:485–560, 1992.

[2] C. K. Chui. An Introduction to Wavelets. Academic Press, San Diego, CA, 1992.

[3] I. Daubechies. Orthonormal bases of compactly supported wavelets. Commun. on Pure and Appl. Math., 45:909–996, 1988.

[4] I. Daubechies. Ten Lectures on Wavelets. SIAM Philadelphia, 1992.

[5] D.L. Donoho. Interpolating wavelet transforms. 1992.

[6] A. Haar. Zur Theorie der orthogonalen Funktionensysteme. Math. Ann., 69:331–371, 1910.

[7] W. Sweldens I. Daubechies. Factoring wavelet transforms into lifting steps. 1997.

[8] S.G. Mallat. Multiresolution approximations and wavelet orthonormal bases of L^{2} (R). Trans. Amer. Math. Soc., 315(1):69–87, 1989.

[9] S.G. Mallat. A Wavelet Tour of Signal Processing. Academic Press, Orlando-San Diego, 2nd edition, 1999.

[10] R.E.Blahut. Fast Algorithms for Digital Signal Processing. Addison-Wesley, Reading, MA, 1984.

[11] W. Sweldens. The lifting scheme: A custom-design construction of biorthogonal wavelets. Appl. Comput. Harmon. Anal., 3(2):186–200, 1996.