Waveletek és ridgeletek azaz zördületek és ráncok

Waveletek és ridgeletek azaz zördületek és ráncok Pröhle Tamás 2009. június 4.

⊕ September 23, 2011

0. Bevezetés

PT//Zördületek és ráncok//MMIX

2

0.0 Mese a zördületekről és a ráncokról A waveletek és a ridgeletek, azaz a zördületek és a ráncok szerteágazó, kacskaringós matematika történeti múlttal rendelkeznek. Ráadásul érdekes magyar vonatkozásokkal, legnevezetesebben Haar Alfréd és Gábor Dénes révén. Mindkettőjük munkája általánosan elismerten csatlakozik ezekhez, a manapság oly intenzíven kutatott, gyakorlatban sokfele alkalmazott eszközökhöz, fogalmakhoz. Egy jel Fourier transzformáltjáról leolvasható, hogy a jelben a különböző periodicitású hatások mekkora intenzitással vannak jelen. De ez a Fourier transzformált nem mutatja a jel időbeli változását, időben lokális információ direkt módon nincs benne: a Fourier transzformált egy-egy ω pontbeli értéke az időtől függetlenül, csak az adott frekvencia intenzitását és a fázisát méri.

urier transzformációval felcserélhető. Így az eljárás kismértékü bonyolítása árán pótolható a Fourier transzformált időbeli lokalizációjának hiánya azáltal, hogy a Fourier transzfomáltat az időablak helyének függvényében vesszük. A módszer alkalmazhatósága korlátozott: zavaró a szélek hatása és az hogy a különböző frekvenciáju komponenseknek a fix szélességü ablakokba eltérő számu ciklusa esik.

A spektrum időbeli változásának egyfajta mutatója a Gábor-transzformált (STFT: Short Time Fourier Transformation) ami a jelnek egy időben ablakolt részére veszi a Fourier transzformáltat. Kihasználja, hogy egy fix szélességü — például Gauss formáju — időablak lényegében egy konvolució, ami a Fo-

Az időben és térben változó spektrum vizsgálatának feladatát a waveletek szerinti transzformáció oldja meg elegánsan. A waveletek ugyanis időben korlátos tartójúak és az összenyomott-eltolt változataik a függvények terében ugyanolyan sorfejtésre alkalmasak mint a Fourier esetén a sinus-cosinus rendszer.

Hosszú út vezetett a wavelet transzformálás módszereinek kifejlődéséig. Talán azért is, mert az elért eredményt — mint távoli célt — pontosan soha sekisem fogalmazta meg. Ez a kulcsa annak is, hogy e tárgyban se szeri - se száma a különböző minőségü könyvnek, cikknek, tananyagnak és népszerüsítő irománynak. És hát ezért lehetséges az is, hogy most van értelme e terebélyes téma egy részét újabb szempontok szerint összefoglalni.

egyben útmutatás is legyen a legujabb kutatási területek felé.

A legegyszerübb wavelet a Haar-wavelet. Az elvét többdimenzióban is sokfele, eredményesen alkalmazzák, bár a konvergenciája lassú, főleg a közelítő függvények folytonosságának hiánya miatt. A módszer bemutatása a bevezető irodalom agyoncsépelt, terjengős témája. Az alkalmazási elterjedtségnek az az oka, hogy a megvalósítása — a szükséges algoritmuTömör elméleti bevezető után az általánositásokra, a sok egyszerüsége miatt — informatikailag rendkívül többdimenziós módszerekre összpontosítunk. Külö- hatékony. Legismertebb alkalmazási példája a 4-fa nösen fontosak azok a részek, amik a wavelet típusu képtárolás. képfeldolgozási módszerek alapjai. A cél azoknak az eljárásoknak a tárgyalása, amik leginkább a digitális A legujabb wavelet irodalom jelentős részének az a képeken látható görbék és textúrák elemzésére al- fő gondolata, hogy bemutatja, hogy a Haar rendkalmasak. szer egyik vagy másik tulajdonsága hogyan öröklődik vagy javul egy-egy általánosítás által. Mi mégiscsak Csak egy vázlatot készítettünk. Az alapos leírás a lehető legrövidebben térünk ki a Haar rendszer meghaladja e rövid összefoglaló terjedelmét. A fő bemutatására. Mert az egyszerüsége miatt nagyon cél az volt, hogy a waveleteken alapuló eljárások rosszul tűzi ki az általánosítások útját ugyanakkor algoritmikus és matematikai konstrukcióinak minél az alapos bemutatása mégiscsak nagyon hosszukás rövidebb magyarázatát adjuk. Úgy, hogy a leírás lenne. 0.0 Előszó: mese a zördületekről

MMIX

3

0. Bevezetés


4

0.1 Tartalomjegyzék

Bevezetés Elmélet Konstrukció Többdimenzió Általánosítás Statisztika Alkalmazás Bibliográfia Mellekletek

0. I. II. III. IV. V. A. B. M.

2. 6. 69. 87. 98. 101. 108. 116. 127.

oldal oldal oldal oldal oldal oldal oldal oldal oldal

Az egyes részek alpontjai 0. Bevezetés 0.0 Előszó 0.1 Tartalomjegyzék I. Elmélet I.0 Előszó: a wavelet transzformált I.1 A waveletek értelmezése

.... I.2 Altérsorok 2 I.3 Klasszikus waveletek 4 I.4 Alapvető tételek I.5 Ortogonális MRA .... I.6 Biortogonális MRA 6 I.7 A PR feltétel 7 I.8 A lifting

12 18 34 43 49 58 62

II. Konstrukció II.0 Előszó II.1 Daubechies ortogonális wavelete II.2 Ortogonális Coiflet II.3 Ortogonális symmlet II.4 Biortogonális spline wavelet III. Többdimenzió III.0 Előszó III.1 Multiwaveletek III.2 Szeparábilis kétdimenziós wavelet III.3 Nem-szeparábilis kétdimenziós wavelet III.4 Többdimenziós wavelet konstrukciók IV. Általánosítás IV.0 Előszó IV.1 Ridgelet IV.2 Curvelet

0.1 Tartalomjegyzék

V. Statisztika V.0 Előszó V.1 Idősor wavelet spektrum V.2 Idősor zajszürés V.3 Képek wavelet felbontása V.4 Élek és textúrák detektálása

.... 69 70 78 80 81 A. Alkalmazás A.0 Előszó .... A.1 Idősor elemzés 87 A.2 Kép transzformálás 88 A.3 A JPEG szabványok 93 95 B. Bibliográfia 97 B.0 Bevezetés B.1 Könyvek B.2 Cikkek .... B.3 Programok 98 99 M. Mellékletek 100 M. A mellékletek listája

MMIX

.... 101 102 103 105 107 .... 108 109 110 111 .... 116 117 118 121 .... 127

5

I. Elmélet


6

I.0 Előszó: a wavelet transzformált

A wavelet fogalom értelmezése Altérsorok Klasszikus waveletek Alapvető tételek Ortogonális MRA Biortogonális MRA A PR feltétel A lifting

I.1 I.2 I.3 I.4 I.5 I.6 I.7 I.8

7. 12. 18. 34. 43. 49. 58. 62.

oldal oldal oldal oldal oldal oldal oldal oldal

Ebben a szakaszban a wavelet felbontás alapvető eszközeit mutatjuk be. Ezen belül annak a leírását (I.5) tekintjük a legfontosabbnak, hogy miért és hogyan számítható ki egy függvény egy zördület szerinti sorfejtése, továbbá azoknak az elveknek a bemutatását (I.7), amiknek alapján waveletek konstruálhatóak. A waveletek elméletének ebben a szakaszban érintett fogalmai tárgyalhatók tisztán matematikai és tisztán algoritmikus szempontból is. A matematikai tárgyalás nehézsége a számos felmerülő fogalom egzakt definiálásának szükségessége. De az algoritmikus út követése sem sokkal egyszerübb. Ráadásul e terület különös szépsége pont abban rejlik, hogy a matematika legvegyesebb területével áll szoros kapcsolatban. Ha pusztán csak az eljárások kisebb-nagyobb trükkjeire koncentrálnánk akkor fedve maradna számos izgalmas analitikai kérdés.

I.1 A waveletek értelmezése és alaptulajdonságai Definició Azokat a ψ függvényeket nevezzük waveleteknek, azaz zördületeknek amik L2 (R)-beliek és amikre ha a ˆ Fourier transzformáltat F(ψ)(ω) = ψ(ω) jelöli a Cψ =

Z

∞ −∞

2 ˆ |ψ(ω)| dω ω

integrál véges. A definícióban a Cψ végességére azért van szükség, mert — mint majd látjuk — ezen feltétel mellett lehetséges, hogy egy függvény előállítható a saját wavelet transzformáltjából. Egy f (t) : R → R függvény ψ szerinti wavelet transz- A wavelet transzformált tehát egyenlő az f (t) függformáltjának az a ∈ R\0 és b ∈ R értékekre a vény és a ψa,b (t) normalizált zördületek skalárszorZ ∞ zatainak összességével: 1 t−b Wψ,a,b (f ) = p ) dt f (t)ψ( a |a| −∞ Wψ,a,b (f ) = hf (t), ψa,b (t)i. integrállal értelmezett konstansok együttesét nevez- A ψ (t) normalizált zördületek a ψ(t) waveletből a,b zük. Kicsit máshogy jelölve a wavelet transzformált: (zördületből) eltolásokkal, dilatációkkal és normalizációval jön létre: Wψ,a,b (f ) = Wf,ψ (a, b) t−b 1 azaz a wavelet transzformáció az egyváltozós f (t). ψa,b (t) = p ψ hez a kétváltozós Wf,ψ (a, b) függvényt rendeli. a |a| I.1. A waveletek értelmezése

MMIX

7

I. Elmélet


A wavelet transzformálás Parseval formulája: 1 1 1 hf (t), g(t)i = Wf,ψ (a, b), Wg,ψ (a, b) , Cψ a a azaz a wavelet transzformálás skalárszorzat tartó.

A képlet bizonyításához vegyük észre, hogy ha a ψ(t) zördület Fourier transzformáltja Z ∞ 1 b ψ(ω) = √ f (t)e−iωt dt = F(ψ(t))(ω), 2π −∞ akkor — a Fourier transzformált tulajdonságait felhasználva közvetlenül, de elemi integrál azonossági képletek alapján is — a normalizált zördületek Fourier transzformáltja: 1 t−b − 12 d b ψa,b (ω) = F |a| ψ( . ) (ω) = |a| 2 e−ibω ψ(aω) a

8

d = hfˆ(ω), ψ a,b (ω)i =

Z

∞ −∞

p ˆ fˆ(ω) |a|e−ibω ψ(aω) dω =

p ˆ = 2π|a|F fˆ(ω)ψ(aω) (−b). Wg,ψ (a, b) =

És ugyanígy:

p ˆ (−b). 2π|a|F gˆ(ω)ψ(aω)

Ezt a két átalakítást felhasználva, a zördületekre bizonyítandó Parseval formula jobb oldalán szereplő skalárszorzat: + * ˆ ˆ ˆ F f (ω)ψ(aω) (−b) F gˆ(ω)ψ(aω) (−b) p p . 2π , |a| |a|

Itt ismét felhasználva a Fourier-Parseval képletet: Z Z 1ˆ 2 ˆ = 2π g (ω)|ψ(aω)| dω da = f (ω)ˆ a

Z ˆ ψ(aω)|2 Ennek alapján a Wf,ψ (a, b) wavelet transzformált ek= 2π dωhfˆ(ω), gˆ(ω)i = Cψ hf (t), g(t)i, vivalens átalakítása a Fourier-Parseval formula fel|ω| használásával: ami bizonyitja az állítást. Wf,ψ (a, b) = hf (t), ψa,b (t)i =

A wavelet transzformálás invertálása

= hf ∗ (t), g(t)i

azaz az f ∗ és a g skalárszorzata tetszőleges g-re ugyanaz, mint az f és g skalárszorzata, tehát f = f ∗ .

Ha f ∈ L2 (R) akkor az Z ∞Z ∞ 1 1 f (t) = Wf,ψ (a, b)ψa,b (t) db da Cψ −∞ −∞ a2

egyenlőség majdnem mindenütt igaz, azaz a wavelet transzformáltból az eredeti függvény visszanyerhető.

A megadott invertálási képlet helyes. Jelölje a jobboldalt f ∗ (t). Ekkor a waveletekre érvényes Parseval formula szerint, azonos átalakításokkal, a Fubini tételt felhasználva, tetszőleges g függvényre: 1 1 1 Wf,ψ (a, b), Wg,ψ (a, b) = hf (t), g(t)i = Cψ a a Z Z 1 1 = Wf,ψ (a, b)Wg,ψ (a, b) db da = Cψ a2 Z Z Z 1 1 = Wf,ψ (a, b) g(t)ψa,b (t) dt db da = Cψ a2 Z Z Z 1 1 Wf,ψ (a, b)ψa,b (t) db da g(t) dt = = Cψ a2 I.1. A waveletek értelmezése

A Cψ végessége, ha ψ ∈ L1 a ψˆ folytonossága ˆ okán ha R ∞ csak akkor teljesülhet, ha ψ(0) = 0, azaz α ψ(t)dt = 0. De feltéve α > 0 -ra a (1+|t|) |ψ(t)| −∞ 1 ˆ L -beli voltát, β = min(α, 1)-re |ψ(ω)| < C|ω|β , amiből Cψ végessége következik. Tehát a wavelet transzformált lényegében akkor invertálható, ha Z ∞ ψ(t)dt = 0. −∞

Tehát lényegében minden wavelet függvény szükségszerüen 0 integrálu!

A wavelet transzformált további tulajdonságai A wavelet transzformálás líneáris:

MMIX

Wψ (αf + βg) = αWψ (f ) + βWψ (g) 9

I. Elmélet


10

Az időbeli eltolás hatása a wavelet transzformáltra: Tehát a wavelet transzformálás egy megfelelően választott ψ függvény segitségével az egyváltozós f függvényekhez egy olyan kétváltozós függvényt renWψ (f (t − c))(a, b) = Wψ (f (t))(a, b − c) del, ami olyan hogy: A dilatáció hatása a wavelet transzformáltra: - az értéke a két változó minden lehetséges értékére skalárszorzat, tehát a transzformált értéke értelmezhető mint hasonlóság mérték az f függvény és választott ψ dilatált-eltolt példánya közt; - a transzformált algebrai tulajdonságai hasonlítanak a Fourier transzformálthoz; Wψ (f (−t))(a, b) = Wψ (f (t))(a, −b) - a transzformáltból az eredeti függvény helyreállítA wavelet transzformált paramétereinek invertálása: ható. a b Wψ (f (t/c)) (a, b) = Wψ (f (t)) ( , ) c c Az időbeli tükrözés hatása a wavelet transzformáltra:

1 b Wψ (f )(a, b) = Wf (ψ)( , − ) a a A Wf,ψ (a, b) wavelet transzformált az a paramétertől A wavelet transzformált línearitása a felhasznált wa- mint frekvenciától és a b paramétertől mint időtől velet szerint: függ. Az a adja meg, hogy a felhasznált ψ waveletet az időtengely mentén milyen mértékben nyomtuk Wαψ+βφ (f )(a, b) = αWψ (f )(a, b) + βWφ (f )(a, b) össze. És a b paraméter adja meg, hogy az összenyoWψ(t−c) (f )(a, b) = Wψ (f )(a, b + ca) mott waveletet az időben hova illesztettük. Wψ(t/c) (f )(a, b) = Wψ (f )(ac, b)

Az invertálási tétel igaz volta szemléletesen is jól látható. Vegyünk egy korlátos tartóju zördületet és egy közelíteni szándékozott jelet. Nyomjuk össze a zördületet erősen az időtengely mentén. Vegyük az összenyomott wavelet olyan időben eltolt variánsait, ahol az eltolás mértékek az összenyomás mértékének megfelelő sűrüséggel vannak jelen. Azaz ha például az időben felehosszura nyomtuk össze a waveletet, akkor vegyünk azonos időtartam alatt kétszerannyi eltolási pontot. Ezután a zördület összenyomott, eltolt verzióinak líneáris kombinációjával közelítsük a megadott jelet. Nyilvánvaló, hogy megfelelő feltételek teljesülése mellett a közelítés tetszőlegesen jó lehet. Hiszen az időben összenyomott wavelet tartója tetszőlegesen rövid. Így az egyes eltolt verziók konstansszorosai lényegében lokálisan approximálják a jelet az eltolt tartónak megfelelő, tetszőlegesen rövid szakaszon.

I.1. A waveletek értelmezése

Mint majd látjuk, a wavelet konstrukciók során fontos szerepet töltenek be az úgynevezett skála waveletek. Ezek a függvények azt a függvényteret generálják amit egy adott mértéknél nagyobb hullámhosszú waveletek generálnak. Sokszor úgy fogjuk előállitani egy-egy jel approximációját, hogy a jelnek a skála wavelet szerinti közelítését vesszük egyre finomabb felbontás (egyre kisebb hullámhossz, azaz a skála wavelet egyre nagyobb összenyomása) mellett. És azt fogjuk feltételezni, hogy egyrészt a skála wavelet olyan, hogy az eltoltjai által generált tér egymásba ágyazottan bővülő ha a hullámhossz csökkenő. Másrészt pedig azt tesszük fel, hogy az ‘eredeti’ — ebben a szakaszban tárgyalt — wavelet a bővülő skála-wavelet terek differenciáit generálja. Ezért van az, hogy a skála waveleteket approximációs-waveleteknek, az ebben a részben tárgyalt ‘eredeti’ waveleteket pedig detail-, azaz részletwaveleteknek is nevezik.

MMIX

11

I. Elmélet


12

I.2 Altérsorok Az MRA angol rövidítés (Multiresolution Analysis), értelemszerü fordítása körülményes. Ráadásul az elnevezés nem utal a szóbanforgó altérsor két legfontosabb tulajdonságára. Sem arra, hogy az MRA olyan altérsor ahol az alterek az elemeik időbeli eltolására invariánsak. Sem arra, hogy az ilyen altérsor tagjai dilatációval is létrehozhatóak egymásból. Ezért van az, hogy az MRA rendszereket pontatlan fordítással változó finomságu altérsoroknak, rövidebben: finomodó altérsoroknak, esetleg még rövidebben, csak altérsoroknak nevezzük. Ez a fordítás a ’multiresolution’-nak feleltethető meg. Az elnevezés maradéka, az ’analysis’ az MRA-k szokványos alkalmazására utal. Ugyanis egy Hilbert-térből vett MRA segítségével a Hilbert-tér tetszőleges eleme analizálható. Méghozzá úgy, hogy megvizsgáljuk mekkorák az abszolutértékei azoknak a vetületeknek, amiket az adott elemből az adott MRA egyes tagjaira vetítve kapunk. Az L2 Hilbert-tér esetünkben az ℓ2 (Z) sorozatok és ha a V tagjai közt dilatácós megfeleltetés van: vagy az L2 (R) függvények tere. Az L2 altereinek (iii) f (t) ∈ Vj pontosan akkor ha f (2t) ∈ Vj+1 . V = · · · ⊂ Vj−1 ⊂ Vj ⊂ Vj+1 ⊂ · · ·

sorozata akkor MRA azaz finomodó altérsor, ha T S (i) j Vj = 0 és az j Vj sűrü L2 -ben .

Továbbá, ha a V tagjai időben eltolás invariánsak: (ii) ha f (t) ∈ V0 akkor f (t − k) ∈ V0 ∀k ∈ Z

A t ∈ Z-t illetve ∈ R-t időnek nevezzük. Az időbeli eltolás k ∈ Z egész számmal vett f (t − k) eltoltakat, a dilatációk egydimenzióban felére vett f (2t) zsugorítást jelentenek. Sorozatok esetén a zsugorítás a páratlan indexüek elhagyását jelenti. A zsugorítás inverze a ’hígitás’: ekkor nullákat írunk a tagok közé, a páratlan indexü helyekre!

Ha van olyan ϕ(t) függvény amire V0 a ϕ(t − k), jelöléseket: k ∈ Z függvények líneáris generátuma, azaz ha V0 = span{ϕ(t − k), k ∈ Z},

ϕj,0 (t) =

∞ X

hk ϕj+1,k (t) .

k=−∞

akkor azt mondjuk, hogy az MRA-t a ϕ skála függ- Ezekkel a jelölésekkel, m = 1, 2, ... esetén: Z ∞ Z ∞ vény generálja. m m −j 2 ϕj,k (t)dt = 2 ϕm (t)dt . −∞

−∞

A továbbiakban azt vizsgáljuk, hogy mikor jön létre egymásba ágyazott altérsor egy olyan tér dilatáltja- Ha tehát a (1) egyenletet integráljuk, adódik: ∞ iból, ami egy ϕ(t) függvény eltoltjainak generátuma. X √ hk = 2 . k=−∞ Az MRA definíciója szerint, ha van olyan ϕ(t) ∈ V0 aminek egészszámokkal vett eltoltjai a V0 -t generál- Ha a ϕ1,k (t), k ∈ Z ortogonális rendszer, akkor az ják, akkor a ϕ(2t) és az 12 -el vett eltoltjai a V1 -et (1) négyzetét integrálva adódik, hogy: generálják. Ha V0 ⊂ V1 , akkor van olyan hk , k ∈ Z, ∞ X amire h2k = 1. ∞ X √ k=−∞ (1) ϕ(t) = hk 2ϕ(2t − k). k=−∞ Ez utóbbi teljesülése érdekében emeltük ki az (1) √ egyenletben a 2-t: így normalizálva érvényes, hogy Bevezetve a ’a dilatált-eltolt skálafüggvények súlya ϕ-ben (hk )’. √ ϕ0,k (t) = ϕ(t − k) és ϕj+1,k (t) = 2ϕj,0 (2t − k) I.2 Altérsorok

MMIX

13

I. Elmélet


Probléma, hogy az előállítási egyenlet együtthatóinak a fentitől eltérő normalizálása is szokásos. Úgy normalizáltunk, hogy az együtthatók √ négyzetösszege 1, emiatt az együtthatók összege 2. Ez a célszerü, ha a főtéma a függvény közelítés.

14

Vj -re, de elöbb ezekre az esetekre szorítkozunk. Az ortogonális esetben a Wj egyértelmü: a Vj altér ortogonális kiegészítője Vj+1 -ben, és a . . . , W−1 , W0 , W1 , . . . alterek is ortogonálisak:

√ Az 1 összegü hk / 2 együtthatókat akkor szokás al··· V V V −1 0 1 * * * * ··· >⊕ >⊕ >⊕ >⊕ kalmazni, ha a fenti előállitási egyenletet mint líne··· ··· W−1 W0 W1 áris filtert tekintjük. Ebben az esetben √ a dilatációs egyenlet együtthatóiként a 2 összegü 2hk együtthatókat szokás használni, ck illetve 2ck jelölésekkel. Tegyük fel hogy van olyan ψ(t) függvény aminek az időbeli eltoltjai generálják W0 -t, azaz De mi csak az elöbb mutatott normalizálást alkalW0 = span{ψ(t − k), k ∈ Z}. mazzuk! Ebben a rövid összefoglalóban az átsúlyozásból, átjelölésből komoly haszon nem származna. Ha van ilyen ψ, akkor azt a felbontáshoz tartozó Legyen Wj minden j ∈ Z-re a Vj+1 egy olyan altere, wavelet függvénynek (zördületnek) nevezzük, és akár a ψ által generált MRA felbontásról is beszélhetünk. amire Wj ⊕ Vj = Vj+1 . Ekkor nyilván Vj =

j−1 X

Wk .

k=−∞

Általános esetben a Wj nem feltétlenül ortogonális

Megjegyzés. Ortogonális esetben a fenti ψ szükségszerüen lényegében egyértelmü. Ugyanis, ha ˜ − k), k ∈ Z} = span{ψ(t − k), k ∈ Z} span{ψ(t

akkor ψ˜ és ψ egymásnak egészértékkel vett eltoltjakonstansszorosa. Ugyanis a kifeszitett alterek egyenlősége miatt ˜ = P ak ψ(t − k) ψ(t) k valamely ak együtthatók mellett. De ekkor ˜ − ℓ) = P ak ψ(t − k + ℓ) ψ(t k

is fennáll. Felhasználva a ψ˜ rendszer ortogonalitását, a két egyenlet szorzatát integrálva kapjuk, hogy: P δ0,ℓ = k ak ak+ℓ

hanem úgy is nevezni mint hogy ’anya wavelet’ illetve hogy ’apa wavelet’ (mother-father wavelet). A névszimbolika messze mutató, van ahol az általánosítás az óegyiptomi Oziris-Ízis párig is eljut. Az alternatív elnevezések közül mi inkább csak a sokkal képszerübb approximáció-részlet (approximations-details) megkülönböztetést alkalmazzuk. Ugyanis általában úgy lesznek az MRA rendszerek meghatározva, hogy a ϕ skála függvények líneáris kombinációi az analizált függvények nagyobb léptékü, trendszerü, ’approximációs’ részét fogják megközelíteni, mig a ψ waveletekkel a trendre rakódó zajt a ’részleteket’ fogják modellezni. Ennek a szemléletnek megfelelően nevezzük a Vj altereket approximációs és a Wj altereket a részlet altereknek.

tetszőleges ℓ ∈ Z-re fennáll. De ha ez igaz, és az a-k közül az első nem-nulla indexe u az utolsóé pedig v, és ha u 6= v volna, akkor δu,v = au av 6= 0 lenne. Tehát az a-k közt csak egy nem-nulla van, amire ˜ = aψ(t − s) teljesül |a| = 1. Tehát valóban a ψ(t) Mivel W0 ⊂ V1 van olyan gk , k ∈ Z, amire egy megfelelő s egészszámra, és egy 1 abszolút ér∞ tékü a-ra. X √ ψ(t) = gk 2ϕ(2t − k) (2) k=−∞ Elterjedt a ψ és a ϕ függvényeket nem csak mint waveleteket és skála waveleteket megkülönböztetni, Mint látható, az MRA-k esetén két dilatációs egyenI.2 Altérsorok

MMIX

15

I. Elmélet


let lehetséges. Az utóbbit, a ψ waveletet előállító (2) dilatációs egyenletet szokás wavelet egyenletnek, míg a korábbi hasonlót — a (1) ϕ skála függvényt előállitót — skála egyenletnek. Csak az olyan esetekkel akarunk foglalkozni, ahol a . . . W−1 ⊕ W0 ⊕ W1 . . . tér komponensein vett vetületek alapján előállítható a vetített függvény. Ezért, az előző részben leírt fogalmak szerint kell, hogy a ψ egy wavelet legyen. Azaz, szintén az ott irtak szerint kell, hogy Z ∞ ψ(t)dt = 0 −∞

16

Az MRA terekkel kapcsolatban egy tetszőleges jel (függvény) esetén a következő fogalmak és műveletek alapvető szerepet játszanak: - az approximációs együtthatók, azaz az az aj,k , k P∈∞Z sorozat, amire az a Vj teret generáló ϕj,k (t)-k k=−∞ aj,k ϕj,k (t) lineáris kombinációja az analizált jel vetülete Vj -n - a részlet (detail) együtthatók, azaz az a dj,k , k Z sorozat, amire a Wj teret generáló ψj,k (t)-k P∈ ∞ k=−∞ dj,k ψj,k (t) lineáris kombinációja az analizált jel vetülete Wj -n - analízis azaz a jel felbontása approximációs és részlet komponensre: az aj,k és dj,k együtthatópárok meghatározása adott j értékekre - szintézis azaz az eredeti jel előállitása az approximációs és részlet együtthatókból és a dilatált-eltolt ϕ és ψ függvényekből.

legyen. Ebből pedig véve a (2) dilatációs előállítás két oldalának integrálját — felhasználva, hogy míg a baloldal integrálja nulla, addig a jobb oldalon szeA skála és wavelet egyenletek (hk ) illetve (gk ) együttreplők függvényeké nem az — adódik, hogy: hatói fontos szerepet játszanak a diszkrét wavelet ∞ X transzformálás (azaz a jelek analizise vagyis az appgk = 0. roximációk és a részletek kiszámítása) és a szintézis k=−∞

(azaz az eredeti jelnek az approximációkból és a függvényrendszerre együttesen az úgynevezett biorrészletekből való helyreállítása) során. togonalitást. Ilyen biortogonális rendszerek, már a következő rész példái közt is szerepelnek. Noha azt Ezért elöbb bemutatunk néhány olyan (ϕ, ψ) függ- pontosabban, hogy ez a tulajdonság miben áll, csak vényt, ami szerint egy-egy MRA felépíthető. Majd a későbbiekben definiáljuk. az 1.4 részben bemutatunk néhány olyan tételt, ami ezeknek a függvényeknek a megtalásához szükséges. A következő szakasznak az a célja, hogy megmuVégül pedig, az 1.5 és 1.6 részekben végigszámol- tassa: vannak olyan (ϕ, ψ) függvények amik az edjuk, hogy mi a kapcsolat a dilatációs együtthatók dig leírt talán egzotikus tűnő tulajdonsággal rendelés egy-egy jel analizise és a szintézise során végre- keznek. Talán elégséges volna csak a legegyszerübb hajtandó műveletek közt. Elöbb úgy, hogy a skála példára a Haar rendszerre hivatkozni. De ezt nem függvény eltolásainak ortogonalitását feltételezzük. találtuk kellően meggyőző erejünek annak megmuMajd úgy is hogy két olyan, különböző skála függ- tatására, hogy a mondott tulajdonságú függvények vényt veszünk amire az eltoltak közt nem tesszük tényleg léteznek, éppen a példa túlzott egyszerüsége fel az ortogonalitást: csak az eltoltakból álló két okán.

I.2 Altérsorok

MMIX

17

I. Elmélet


18

I.3 Klasszikus waveletek

Ebben a szakaszban arra mutatunk példákat, hogy léteznek az előző szakaszokban leírt tulajdonságu waveletek (zördületek). Szinte kötelező ujjgyakorlatként bemutatjuk a Haar rendszert és bemutatunk néhány olyan rendszert is, ami az eddig leirtaknál bonyolultabb. Megjegyzendő, hogy az itt szereplő wavelet bázisok általában olyanok, hogy a paramétereik explicit meghatározhatók, ez azonban a wavelet rendszerekre általában nem igaz. 1. Haar rendszer függvények mint skála függvények, és a Legyen ϕ(t) = 1 ha t ∈ [0, 1] és ϕ(t) = 0 egyébként. ψj,k (t) = 2j/2 ψ(2j t − k) Legyen ψ(t) = 1 ha t ∈ [0, .5] és ψ(t) = −1 ha függvények mint hozzátartozó waveletek, együttesen t ∈ [0, .5] és ψ(t) = 0 egyébként. MRA rendszert alkotnak. Azaz legyen ϕ és ψ az ábra szerinti: ϕ(t) 6 1

ψ(t) 6

b

r

r

0

1 2

b

r

b -

r

b

1

0

1

-1

b 1 2

b

1 r

Könnyen látható, hogy ezekre a függvényekre a ϕj,k (t) = 2j/2 ϕ(2j t − k)

Ha az elöbbi jelöléseket vesszük, akkor a rajzokon a ϕ0,0 (t) illetve a ψ0,0 (t) látható. A ϕ0,1 (t) illetve a ψ0,1 (t) azok a függvények lennének aminek grafja ezekhez viszonyítva 1-1 egységgel jobbra tolt. A ϕ1,0 (t) és a ψ1,0 (t) képét úgy kaphatjuk, hogy az előző két függvény képét az x tengely mentén felére √ zsugorítjuk, ugyanakkor az y tengely mentén 2szörösére nyujtjuk. Az 1, 1 indexü függvények pedig

e függvények 1/2-del jobbra tolt verziói. Azaz a 0, 0 indexü és a 0, 1 indexü függvények ugyanúgy helyezkednek el egymáshoz viszonyítva, mint az 1, 0 és az 1, 1 indexüek. Rajzban például a ϕ esetén: √ 2

b r 6 r

0

√ 2

6 b

-

b 1 2

1 ϕ1,0 (t)

r

A mondottakon felül persze az is igaz, hogy: - adott j-re a ϕj,k (t), k = ..., −1, 0.1, ... függvények ortogonálisak. Ezért fogjuk ezt a rendszert ortogonális wavelet rendszernek nevezni.

b -

r

0

1 2

1 ϕ1,1 (t)

Ahhoz hogy lássuk, hogy a Haar rendszer (ϕ, ψ) függvénypárja tényleg egy MRA-t alkot, legfontosabb a következő (esetünkben nyilvánvaló) dolgokat végiggondolni: - ahhoz hogy Vj ⊥Wj , látni kell hogy a ϕj,k (t), k = ..., −1, 0.1, ... függvények ortogonálisak a ψj,ℓ (t), ℓ = ..., −1, 0.1, ... függvényekre. - látni kell, hogy az elöbbi függvények által előállitott minden függvény olyan, hogy a ϕj+1,m (t), m = ..., −1, 0.1, ... függvények által is előállítható mint lineáris kombináció (Vj ⊕ Wj ⊆ Vj+1 ). I.3 Klasszikus waveletek

- továbbá azt, hogy minden a ϕj+1,m (t), m = ..., −1, 0.1, ... függvények által, mint lineáris kombináció előállitott függvény előállitható az első fül szerint megjelölt függvények lineáris kombinációjaként is. Vj ⊕ Wj ⊇ Vj+1 )

Érdemes hosszabban megemlékezni arról, hogy ezt a legrégebben megismert, kompakt tartójú (azaz olyan függvényekből álló aminek minden tagja véges szakaszon nem-nulla) függvényrendszert — ami a wavelet függvény-rendszerekre jellemző eltolásokkal, dilatációkkal és eltolásokkal is létrehozható, — a Budapesten született Haar Alfréd alkotta. Először abban a 1909-ben védett göttingai doktori disszertációjában írt róla aminek szövege 1910-ben a Mathematische Annalen-ben is megjelent. Sőt

MMIX

19

I. Elmélet


bizonyos források értelmezhetőek úgy is, hogy létezik ennek a dolgozatnak egy olyan különlenyomata, aminek a függelékében ő sajátmaga úgy ír az általa alkotott függvényrendszerről mint ‘időben lokális hullám’okról.

20

jai szerint haladó Fourier-féle sora egy zérus-mértékü ponthalmaz kivételével összetartó." Megjegyzendő, hogy Haar a függvényrendszerét χ rendszernek nevezte és számos további nevezetes tulajdonságát bebizonyította. Tanári pályájával kapcsolatban feljegyezendő, hogy viszonylag fiatalon, 48 évesen 1933-ban halt meg, de rövid munkássága az oktatás téren is igen gazdag eredményü. Itthon elöbb Kolozsvárott (az 1912-ben Budapestre kerülő Fejér Lipót helyén) majd a háború után átmenetileg Budapesten dolgozott, és végül 1920-tól, Riesz Frigyessel együtt, a szegedi matematika megalapítója lett.

Magamnak sajnos eddig ilyen kiadványra nem sikerült bukkannom. (Nem kizárt, hogy az elterjedt vélekedés félreértésen alapul.) Mindenesetre úgy tünik Haar célja a függvényrendszer konstruálásával nem a dilatációs-eltolásos wavelet konstrukció bemutatása, és nemis egy időlokalizált ortogonális függvényrendszer létrehozása volt, hanem az — mint ahogyan arról maga is 1914-ben, az általa alkotott, ám gyorsan, széleskörben alkalmazott matematikai Könnyen látható, hogy a Haar rendszer ϕ (t) és j,k eszköz kapcsán a Matematikai Természettudományi ψ (t) függvényeire a skála dilatáció: j,k Értesítőben ír — hogy: "Ez a függvényrendszer az 1 1 egyetlen az eddig ismertek közt, amely azzal a tuϕj,k (t) = √ ϕj+1,k (t) + √ ϕj+1,k+1 (t) 2 2 lajdonsággal bír, hogy e függvenyek szerint minden folytonos függvény a Fourier féle módon konvergens illetve a wavelet dilatáció: sorbafejthető; általában minden Lebesque-féle érte1 1 √ √ ϕ (t) − ϕj+1,k+1 (t). ψ (t) = j+1,k j,k lemben integrábilis függvény e függvénysorozat tag2 2

Azaz a megfelelő h és g együtthatók: h = (h0 , h1 ) =

1 1 √ ,√ 2 2

!

1 1 √ , −√ 2 2

!

illetve g = (g0 , g1 ) =

2. A Daubechies 4 wavelet

Ha ugyanis a ϕ a lehető legrövidebb intervallumon, a (0, 3)-on kívül nulla, akkor az (1) dilatációból: √ ϕ(1) ϕ(1) h1 h0 = 2 ϕ(2) ϕ(2) h3 h2 .

Azaz a (ϕ(1), ϕ(2))′ sajátvektora a jobboldalt szereplő mátrixnak. Ebből pedig (ϕ(1), ϕ(2))′ = ′ 2 · (h0 , h3 ) . Azaz a ϕ — az ’összes egész’, azaz a — 0, 1, 2, 3 pontokban rendre 0, h0 , h3 , 0.

Ebből, ismét az (1) egyenletet alkalmazva a ϕ már Ennek a waveletnek az az érdekessége, hogy a dikiszámítható az ’összes fél pontban’ is! Ugyanis latációs egyenletek együtthatói explicit formában is t = .5, 1.5, 2.5-re az egyenlet jobb oldalán a ϕ-nek megadhatóak: csak ’egész’ pontokban vett értékei szerepelnek... h = (h0 , h1 , h2 , h3 ) = √ √ √ 1+√ 3 3+√ 3 3−√ 3 , , , = 4 2 4 2 4 2 g = (h3 , −h2 , h1 , −h0 )

√ 1−√ 3 4 2

Az eljárás folytatható: a (1) egyenletet alkalmazva a ϕ értéke a .25, .75 ... pontokban kiszámítható a 0, .5, 1, 1.5, 2, 2.5, 3 fél-pontokbeli értéke alapján. Stb.

A dilatációs együtthatókkal a ϕ és a ψ pontos értéke is kiszámítható a mindenütt sűrü diadikus helyeken! A DB4-re a ϕ képe — a leírt eljárással 95 pontban kiszámolva és közben líneárisan interpolálva: I.3 Klasszikus waveletek

MMIX

21

I. Elmélet


22

Tehát az első ábrán látható, DB4 rendszerhez tartozó ϕ egy olyan skála függvény, ami időben a ±1, ±2, . . . 1.2 értékekkel eltolva, önmagára ortogonális (a szorzatintegrál nulla) és aminek az időben felére össze0.8 nyomott és azok időben ±.5, ±1, . . . értékkel eltolt 0.4 példányaiból a (1) szerint az eredeti ϕ függvény (h 0 , h1 , h2 , h3 ) szerinti líneáris kombinációkkal elő0.0 áll. -0.4 A második ábrán látható ψ pedig egy olyan wavelet 0 0.5 1 1.5 2 2.5 3 függvény, ami a (2) egyenlet szerint a dilatált-eltolt ϕ-k alapján a (g0 , g1 , g2 , g3 ) együtthatókkal hozható És a ψ DB4 zördület függvény a (2) egyenlet alapján: létre, és amire az ortogonalitás a különböző mértékben dilatált és eltolt verziók közt is fennáll. 1.6

1.6 1.2 0.8 0.4 0.0 -0.4 -0.8 -1.2 0

0.5

1

1.5

2

2.5

3

A DB4 wavelet azért érdekes, mert a legegyszerübb olyan, nem egészen triviális (ϕ, ψ) függvénypár amivel a következő feladatok megoldhatóak, tetszőleges f (x) végestartóju függvény esetén: - a ϕ szerint vehető az f (x) függvény approximációja. Ez az approximáció a ϕ-nek és a ϕ egészszámokkal eltolt példányainak egy líneáris kombinációja. A legjobban közelítő líneáris kombinációban az egyes

eltolások együtthatója az f (x) és az eltolt ϕ szorzatának integrálja. - a ψ szerint vehetők a f (x) részletei. Fontos, hogy valójában a ’részlet’ is a függvény egy közelítése, csak a ψ jellegzetességei miatt olyan, hogy benne a részletek, azaz a lokális változások dominálnak. Ennek megfelelően a ’részlet’ mint közelítés technikailag úgyanúgy jön létre, mint az approximáció. A ψ egészszámokkal eltolt példányainak azt a líneáris kombinációját vesszük ami az f (x) függvényt legjobban közelíti, és az optimális közelítés minden egyes együtthatója egyenlő — szintúgy mint az approximációk esetén — az f (x) és a megfelelő mértékben eltolt ψ szorzatának integráljával. Ha a fentiekben leírt approximáció és részletek összegét vesszük, akkor az az egészszámokban egyenlő az eredeti függvénnyel. Ha vesszük ϕ és a ψ időben duplájára nyújtott és 0, ±2, ±4, . . . értékekkel eltolt változatait, akkor azok alapján — a korábbiakhoz hasonló módon veI.3 Klasszikus waveletek

hető az f (x) függvény durvább approximációja és durvább részletei. A kapott durvább közelítésben a nem-nulla tagok száma feleannyi mint amennyi a finomabb közelítésekben volt. A durvább approximáció és a részletek összege egyenlő az elöbb kapott finomabb approximációval. Az eljárás folytatható. Ismét duplájára nyujtva a skála és zördület függvényt és azt még ritkábban — a 0, ±4, ±8, . . . értékekkel eltolva — a függvényhez illesztve kapjuk a mégdurvább approximációt és a mégdurvább részleteket. A ’mégdurvább approximáció’ és a ’mégdurvább részlet’ összege természtesen ismét a korábban ’durvább’nak mondott, most egy lépéssel finomabb approximációval egyenlő. Az eljárás során végül egy olyan egészen durva approximációt és részletet kapunk, amiben a többszörösen megnyujtott skála és részlet függvények közül mindössze egynek az együtthatója nem nulla. ([6])

MMIX

23

I. Elmélet


A kapott, egészen durva approximációból és a hozzá dig a különböző komponensekben jelennek meg! tartozó durva, valamint az előzőleg kapott egyre finomabb részletekből a vizsgált függvény visszanyerhető. Méghozzá az egészen durva approximáció X és a különböző finomságu részletek összegeként. A következő ábra egy klasszikus példa. A legfelső, az X görbe a megfigyelési sor: a hibával terhelt sin(1/x) mintavételezése, 1024 pontban.

A6

D6

A legalsó (D1) ennek a megfigyelési sornak sornak a legfinomabb részlet közelítése a ψ eltolt példányaival. Az ábrán az A1 nem látható. Egyenlő egyfelöl X −D1-el, másfelöl A6+D6+D5+D4+D3+D2-el. A D2,...,D6 a durvább részletek és A6 az S egy durva approximaciója. láthatóak. Érvényes, hogy A6 + D6 = A5, A5 + D5 = A4 stb. Sőt, hogy f (x) = A6 + D6 + D5 + D4 + D3 + D2 + D1. Érdemes megfigyelni, hogy az egyes frekvenciák az X-ben időben eltolódva, a wavelet felbontásban pe-

D5

D4

D3

D2

D1

24

Az egyre durvább approximációk és részletek nem A bemutatott rendszer érdekes melléktanulsága, csak a mondott szorzatintegrálokkal kaphatóak meg! hogy míg egy tetszőleges invertálható szűrő esetén a szűrőnek és az inverznek az együttes hossza biztosan Vegyük a közelítendő függvény legfinomabb approxi- végtelen, addig itt a jelet két véges szűrővel kétfele mációjaként a függvény egészszám értékü pontokban bontva, két olyan részt kaptunk amiből két szintén vett értékeit. (Ha ez a mintavételezés nem elég pon- véges szűrővel olyan jelpár előállíható elő, amiknek tos, akkor elöbb nyujtsuk meg a függvényt az időten- összege — eltolástól eltekintve — megegyezik az eregely mentén.) Vegyük lépésenként az approximációs deti jellel. sor konvolucóját a h illetve a g dilatációs együtthatókkal, és minden második tagot hagyjuk el a kapott konvoluciós sorokból! Az így kapott, hosszában fe- 3. LeGall féle 5/3 lére zsugorodott két sor az eggyel durvább approximáció és részlet együtthatósor! Ezt a waveletet röviden LeGall-félének nevezzük. A ↓h ↓h ↓h ↓h hozzátett 5/3 fölösleges utalás arra, hogy ehhez a · · · aj−1,k aj,k aj+1,k · · ·

wavelethez egy 5 és egy 3 hosszuságu szűrő tartozik.

↓g

↓g

↓g

↓g Előfordul, hogy ugyanezt a waveletet ’rendszertani’ ··· dj−1,k dj,k dj+1,k ··· néven biort(5, 3) waveletnek nevezik. Hiszen a bőVegyük észre, hogy a ritkítás miatt így ugyanúgy lé- vebb, a spline alapu biortogonális szűrők családjának pésenként a felére csökken az approximáció és részlet egy tagjáról van szó. Másutt ugyanennek a szűrőegyüthatók száma, mint amikor a skála és zördü- nek biort(2, 2) a neve. Azon az alapon, hogy a let függvényeket az időben duplájára nyujtottuk és hozzátartozó két szűrő másodfokú polinomok hibátlan approximációjára alkalmas. egyre ritkábban illesztettük. I.3 Klasszikus waveletek

MMIX

25

I. Elmélet


A wavelet családok tagjainak elnevezésére szokás egy harmadik elvet is alkalmazni: besorszámozzák a család tagjait. Ez azért térhet el a fenti két elv (szűrőfokszám, approximációs képesség) alapján kapott névtől, mert nem minden együttható- illetve approximációs-fokszám lehetséges.

26

De szokás ezeket a függvénypárokat közelítés (approximációs) illetve részlet (detail) függvényeknek is nevezni. A hullámmal jelölt függvények az analízis függvények, a hullám nélküliek a rekonstrukciós, általánosabb nevükön a szintézis függvények. Vagyis a biortogonális rendszer négy függvénye: ϕ˜ az analízisapproximációs, ϕ a szintézis-approximációs, ψ˜ az analízis-részlet és a ψ szintézis-részlet függvény.

E zürzavar miatt használjuk erre a waveletre a viszonylag általánosan használt és külön megjegyzések A biortogonális wavelet rendszerekhez tartozó függvények felhasználásának menete általában követnélkül is egyértelmüen azonosító LeGall nevet. kező. Elöbb az analízis függvények segítségével felA Haar waveletnek is sokféle neve van forgalomban. bontjuk az analizálandó függvényt, azaz kiszámítjuk Leginkább azért, mert az egyszerüsége okán sokféle az approximációs és a részlet együtthatókat. Utóbb wavelet-családnak a legegyszerübb eleme. Ez a ‘leg- pedig (ha kell) a szintézis függvények segítségével egyszerübbség’ a LeGall-ra is érvényes egy wavelet kiszámítjuk az analizált függvény — adott wavelet család esetén: a LeGall a legegyszerübb biortogoná- rendszer szerinti — approximációját és a részleteit. lis spline wavelet. Azaz a biortogonális rendszer annyiban különbözik A biortogonális wavelet rendszerekhez két függvény- az ortogonális rendszertől, hogy két különböző függ˜ és a (ϕ, ψ). Ebből a (ϕ, pár tartozik: a (ϕ, ˜ ψ) ˜ ϕ) a vénypárt alkalmaz az analízisre illetve a szintézisre. ˜ skála függvények és a (ψ, ψ) a wavelet függvények. Ortogonális szűrők esetén mint láttuk, akárcsak a

Fourier sorok esetén, az analízis és a rekonstrukciós függvénypár ugyanaz: ugyanazokat a függvényeket alkalmazzuk a közelítés együtthatóinak meghatározására mint amiknek a líneáris kombinációja a közelítés lesz.

˜ = h g˜ = h =

1 √ (−1, 2, 6, 2, −1) 4 2 1 √ (−1, 2, −1) 2 2 1 √ (1, 2, 1) 2 2 1 √ (−1, −2, 6, −2, −1) 4 2

g = Ugyanakkor a biortogonális rendszerekben az approximációs és részlet együtthatók az analízis során ugyanúgy keletkeznek mint az ortogonális rendszeAmi azt jelenti, hogy a LeGall analízis függvények a rek esetében. Venni kell az analizálandó függvény fenti együtthatókkal a és az analízis skála illetve zördület függvény szorzat ˜ −2 ϕ(2t ˜ 2 ϕ(2t ϕ(t) ˜ = h ˜ − 2) + ... + h ˜ + 2) integrálját. Úgy, hogy a beszorzás elött a megfelelő ˜ ψ(t) = g˜−1 ϕ(2t ˜ − 1) + g˜0 ϕ(2t) ˜ + g˜1 ϕ(2t ˜ + 1) skála illetve zördület függvényt egyrészt össze kell a szintézis függvények pedig a nyomni megfelelő mértékben, másrészt el kell tolni. ϕ(t) = h−1 ϕ(2t − 2) + h0 ϕ(2t) + h1 ϕ(2t + 2) ψ(t) = g−2 ϕ(2t − 2) + ... + g2 ϕ(2t + 2) ˜ és (ϕ, ψ) dilatációs egyenleteket A biortogonális rendszerhez tartozó (ϕ, ˜ ψ) elégítik ki. függvénypároknak ugyanúgy MRA rendszert kell alkotniuk, mint ahogyan azt az ortogonális rendszerek esetén láttuk. Ezért egy biortogonális rendszerhez Ezekből a szűrőkből az elvét tekintve most ugyankét pár dilatációs együtthatórendszer tartozik. úgy, mint ahogyan azt a DB4 wavelet esetén láttuk, ˜ analízis illetve a (ϕ, ψ) szinkiszámolhatóak a (ϕ, ˜ ψ) A LeGall 5/3 két dilatációs együtthatópárja: tézis függvények. Csakhogy! Ha vesszük a például a I.3 Klasszikus waveletek

MMIX

27

I. Elmélet


ϕ˜ egész helyeken felvett értékeire vonatkozó     ˜ ˜  h1 h0 ϕ(1) ˜ ϕ(1) ˜ √ ˜3 h ˜2 h ˜ 1   ϕ(2) .  = 2 h  ϕ(2) ˜ ˜ ˜4 h ˜3 ϕ(3) ˜ ϕ(3) ˜ h

28

zünk, amire fj+1 (t) = c1 f2j−1 + ... + ck f2j−k akkor az fj , j = 1, 2, ... függvénysor viszonylag általános feltételek mellett, például L2 -ben konvergál.

Ahhoz, hogy az algoritmus eredményét explicit felírhassuk, vegyük észre hogy a cascade algoritmus egyenletet, azt láthatjuk hogy a megfelelő 2x1-es az akárhányadik lépésben, a közelítés értékét egy blokk Toeplitz mátrixnak az 1 dupla multiplicitású tetszőleges pontban a tőle egészszám távolságra sajátértéke. levő pontokbeli értékekből számolja ki. Vagyis, ha vesszük azt az f¯ vektort ami Általában az MRA-knak megfelelő blokk Toeplitz mátrixok olyanok lennének, hogy az 1 mint maxif¯(t) = (f (t), f (t + 1), ..., f (t + k))′ mális sajátérték mellett további 1/2, 1/4, 1/8,... sajátértékei vannak a dilatációnak megfelelően. Itt azonban a legnagyobb sajátérték dupla. Emiatt akkor feltételezve, hogy az f tartója a [0, k + 1) egy ¯ ’nem tudjuk elkezdeni’ a korábban mutatott diadi- olyan f vektorfüggvényt kapunk, aminek a [0, 1)-beli értéke meghatározza az f -et. Ráadásul a cascade alkus dilatáció algoritmust. goritmus szerint: A cascade (magyarul kaszkád lenne...) algoritmus f¯j+1 (x) = Td1 Td2 ...Tdj f¯j+1 (.dj dj+1 ...), a korábban mutatott diadikus egy variációja. Azon alapul, ha egy (c1 , ..., ck ) dilatációs együtthatórendszer mellett egy tetszőleges, korlátos tartóju f = f0 ha a t pont diadikus (kettedestört) felirása t = függvényből kiindulva egy olyan függvénysort képe- .d1 d2 ...dj dj+1 ..., és a k × k méretü,

megfelelő T0 illetve T1 mátrixok:  c1 c3 c2 c1  T0 =  .. .

Ezt figyelembe véve, a LeGall wavelet rendszer analizis és szintézis, skála illetve wavelet függvényei 8 lépésben az alábbi ábrák szerintiek:

    

0 0 0 · · · ck ck−1   c2 c1  c4 c3 c2 c1   T1 =  ..   . 0 0 0 0 · · · ck

Esetünkben a  −1 6 T0 =  −1 0

6.0

4.0 2.0 0.0

4.0 2.0 0.0

-2.0 -4.0

-2.0 -4.0 0

két T mátrix: 

  2 −1   2 −1   T1 = 2 6 2 −1 0 −1 2 6  2 6 2 0 0 0 −1 0 −1 2

E mátrixok sajátaltereinek illetve a sajátértékeik vizsgálatával viszonylag könnyen belátható: akárhogyan is indítjuk a cascade algoritmust, divergálni fog minden diadikus pontban, ugyanakkor minden nemdiadikus racionális pontban véges és konvergens.


6.0

1

2

3

4

1.5

1.5

1.0

1.0

0.5

0.5

0.0

0.0

-0.5

-0.5 0

1

2

3

4

1

2

3

4

1

2

3

4

Ennek a waveletnek különös súlyt ad, hogy egy módosított változata a JPEG2000 képtárolási szabvány egy lehetséges eljárási módja. A JPEG2000 azért alkalmazza a LeGall 5/3 egy módosított változatát, mert ez a transzformáció ugyan elvileg veszteségmentes, azaz kielégiti a PR (perfect reconstruction) feltételt de a gyakorlatban a véges tárolási pontosság okán mégsem az.

MMIX

29

I. Elmélet


30

A PR feltétel pontosabban azt jelenti, hogy a jelből a kerekített kódvektorokból az eredeti transzformáaz analízis-szintézis lépésekkel visszakapható az ere- latlan szinkódok meghatározhatóak. deti jel az approximáció és a részletek összegeként. A pontos rekonstrukció a módosított LeGall esetén azáltal érhető el végespontosságú ábrázolás mellett is, hogy a transzformálást csak egészszámokból álló vektorokra alkalmazzuk. Ez képfeldolgozási környezetben — ahol a szűrőt leginkább alkalmazzák — elégséges is, ugyanis a képpontok színkódjai minden esetben egészszámok. A módosítás√első fontos lépése, hogy a szűrőket átszorozzuk a 2 tényezővel. Ezáltal minden transzformált érték kettedes tört lesz. Ahhoz, hogy egészből-egészbe képező transzformációt és inverz transzformációt kapjuk, lehetséges volna a szűrők további átszorzása 2-vel. Ez ugyan megoldás lenne, de a transzformált vektor nagyon redundás lenne.

Ezt a kerekítést a szűrők egy liftingjének (feloldásának) nevezett felbontásával lehet legegyszerübben meghatározni. A lényege abban áll, hogy egy speciális faktorizációval az 5 illetve 3 széles szűrést 2 széles szűrések sorozatával helyettesítjük. A LeGall rendszer elvi PR tulajdonságáról a gyakorlatban könnyen meggyőződhetünk: ha kiszámítjuk egy véletlen jel analízisének durvább szinthez tartozó approximációs és részlet együtthatóit, lényegében ˜ illetve a g˜ szűrő szerinti konvolúciót, akkor mint a h a kapott együtthatósorokat a h illetve a g szerint konvolválva és a két sort összeadva, visszakapjuk az eredeti jelsorozatot.

Szerencsére erre a redundanciára nincs szükség, mert van egy olyan egyszerü kerekítési szabály, ami mel- A veszteségmentesség viszont általában is könnyen lett a transzformált színkód értékek olyanok, hogy igazolható. Mint majd látni fogjuk, ehhez az szük-

séges, hogy az alábbi két egyenlőség teljesüljön.

jelet. Az, hogy a jobb oldalon 1 helyett 2 áll, a szűrők normalizálásának egyfajta eredménye.

˜ h(z)h(z) + g˜(z)g(z) = 2 ˜h(z)h(−z) + g˜(z)g(−z) = 0

Látható, hogy az eddigi elmondás szerint egy pél˜ és a g˜ szerinti Itt a függvények alatt a megfelelő szűrők z- dául n hosszú megfigyeléssorból a h transzformáltját kell érteni. Esetünkben tehát a konvolúcióval (konvolúció alatt minden esetben cirkuláris konvolúciót kell érteni) két n hosszú sorozanégy polinom: tot nyerünk. Ha ezt tekintenénk transzformáltnak, ˜ ˜ −2 z −2 + h ˜ −1 z −1 + h ˜0 + h ˜ 1z + h ˜ 2z2 h(z) = h a módszer igen redundáns lenne. Belátható viszont h(z) = h−1 z −1 + h0 + h1 z hogy a megfelelő rekonstrukció úgy is elérhető, hogy g˜(z) = g˜−1 z −1 + g˜0 + g˜1 z nem a teljes transzformált sorozatot vesszük figyeg(z) = g−2 z −2 + g−1 z −1 + g0 + g1 z + g2 z 2 lembe: hanem töröljük belőle a páratlan sorszámú Itt a konstansok tényleges értékét az előző táblázat tagokat! Ezután a rekonstrukciót úgy nyerjük, hogy szerint kell venni, és a feltételek teljesülése polinom- elöbb a ritkitott sor minden tagja közé beírunk egy nullát, majd ezután vesszük a rekonstrukciós szűrők szorzással ellenőrizhető. szerinti konvolúciót. Az első egyenlőség jelentése az amit korábban leir˜ majd az eredtunk: a megfigyelési sorra elöbb a h ményre a h szűrőt alkalmazva a kétszeres transzformálás eredményhez hozzáadva annak eredményét, hogy a megfigyelési sorra elöbb a g˜ utána pedig a g szűrőt alkalmazzuk, az összeg visszaadja az eredeti I.3 Klasszikus waveletek

Ahhoz, hogy a mondott ritkítás-bővités műveletsor ellenére is pontos rekonstrukciót nyerjünk, szükséges hogy a második egyenlet is teljesüljön. Ezt az egyenletet szokás alias-feltételnek nevezni. Ugyanis akkor amikor a transzformáltból minden második tagot

MMIX

31

I. Elmélet


elhagyunk, akkor ez a ritkítás annak felel meg, hogy az eredeti jelet ritkábban mintavételezzük: emiatt megkülönböztethetetlenné válnak bizonyos hullámhosszú komponensek a megfigyelésben azaz az eredmény bizonyos áltényezőket tartalmaz. A második feltétel azt biztosítja, hogy ritkítás során keletkezett ál (alias) tényezők kiesnek. Az hogy a második egyenlet megfelel a mondott ritkítás-bővítés műveletnek a legegyszerübben abból látható, hogy mondott művelet ugyanaz, mintha az első transzformációk után kapott sorokba minden páratlan helyre 0-t irnánk.

32

A wavelet, illetve a neki megfelelő 4 szűrő ugyanúgy készül mint minden spline wavelet, a következő észrevételek alapján: √ ˜ ˜ Ha tekintjük a H(ω) = 2cosN ( ω2 ) függvényt mint ˜ = (h ˜ .) egy h - minden spline kielégít egy dilatációs egyenletet - egy spline dilatációt analízis skála dilatációnak véve, a biortogonális szintézis skála dilatáció együtthatói egy líneáris egyenlet megoldása árán adódnak - az alternáló-reverz szűrő megfelelő választás az analízis és a szintézis zördületek dilatációs együtthatóira

Ezeknek a feltételeknek általánosan tetszőleges fokszám szerinti egyik megoldása szerint: 4. Daubechies (7,9) ˜ = (−.046, −.029, .296, .557, ...) h g˜ = (−.027, −.017, .078, .267, −.603, ...) A Db(7, 9) wavelet ugyanúgy egy biortogonális spline h = (.027, −.017, −.078, .267, −.603, ...) wavelet mint ahogyan az volt a LeGall wavelet is, g = (−.046, .029, .296, −.557, ...) csak a fokszáma magasabb. Fontos megjegyezni, hogy ez a wavelet a JPEG2000-ben alkalmazott A táblázatban az együtthatók erősen kerekítettek. CDF97-tel csak a szűrői méretében egyezik meg. Minden vektor csak a középső eleméig van leírva, a

˜ vektor 7 elemü és folytatás szimmetrikus. Tehát a h a következő eleme .296 stb. Mindig a 0 indexü elem van kétszer aláhúzva. A h és a g úgy is származ˜ illetve a g˜-t alternáló előjelekkel tatható, hogy a h-t vesszük. (A megfordításra a szimmetria miatt nincs szükség.)

feltételt a jobboldali nem igazán teljesíti. Ezzel is összefügg azaz erős asszimetria ami a Db(7, 9) szűrő approximációs rendjére érvényes: (6, 2)! További problémája, hogy bizonyos közepes frekvenciákat nagymértékben felerősít. E zavarok miatt fogjuk megkonstruálni a Coiflet-eket!

Ezekből az együtthatókból felrajzolhatóak a spekt- A függvényeknek az értékeit a — a DB4-től és a LeGall-tól eltérően — a cascade algoritmussal célrumok 7.1 7.1 szerü meghatározni. Mivel mint látható, a Db(7, 9) 5.7 5.7 dilatációs együtthatói csak közelítően állnak rendel4.2 4.2 kezésre. Emiatt az analízis-szintézis MRA skála és zördület függvényeinek meghatározásához értelmet2.8 2.8 len a diadikus algoritmust alkalmazni. Hiszen an1.4 1.4 nak ereje — más rendelkezésre álló algoritmusokhoz 0.0 0.0 0 pi/2 pi 0 pi/2 pi viszonyított relatív bonyolultsága mellett — abban A spektrumképen szépen látható, hogy mennyire áll, hogy a megfelelő függvények értékét a dilatációs rossz módszert sikerült előállitani. Igaz, hogy mind- együtthatók pontos ismeretében pontosan határozza kettő aluláteresztő, ám az ehhez tartozó felül-stop meg.


MMIX

33

I. Elmélet


34

I.4 Alapvető tételek Ebben az szakaszban MRA rendszerekben értelmezhető további fontos feltételeket és azok lehetséges következményeit vizsgáljuk, lényegében bizonyítások nélkül. Ezeknek a tételeknek az ismerete és értése alapvető a waveletek gyakorlati alkalmazás során. Ugyanis ezek alapján magyarázható meg, hogy egy-egy helyzetben konkrétan mit számolunk, illetve hogy egy-egy számolás erdménye mit jelent. Állitás Ha ϕ egy MRA-t generál, akkor minden t ∈ R-re ∞ X

k=−∞

ϕ(t − k) =

∞ X

ϕ(k) =

k=−∞

Z

∞

legyen. Az sj periódusa 1, és: sj (t) =

∞ ∞ X X

k=−∞ ℓ=−∞

ϕ(τ )dτ .

−∞

=

∞ X

cℓ

∞ X

cℓ ϕ(2−(j−1) (t − k) − ℓ) =

ϕ(2−(j−1) (t − k − 2j−1 ℓ)) =

ℓ=−∞ k=−∞ Bizonyítás j−1 Legyenek P a dilatációs együtthatók: . . . , c−1 , c0 , c1 , . . . mivel {k + 2 ℓ : k ∈ Z} = Z: amire ck = 2, és definiáljuk sj (t)-t, úgy hogy ∞ ∞ X X t ∈ R, j ∈ Z-re = cℓ ϕ(2−(j−1) (t − n)) =

sj (t) =

∞ X

k=−∞

ℓ=−∞

−j

ϕ(2 (t − k))

n=−∞

= 2sj−1 (t) = 2j s0 (t)

Vagyis:

= s0 (t) = sj−1 (t)/2j = lim sj−1 (t)/2j = j=∞

= lim

j=∞

X

2−j ϕ(2−j (t + ℓ))) =

ℓ

Z

=

Z

ugyanis az utolsó elötti összeg vehető úgy mint egy Riemann integrál közelítő összeg.

=

Z

−∞

Z ∞ X

m=−∞

ϕ(τ )dτ

∞

2 e−i(k−ℓ)ω |ϕ(ω)| ˆ dω =

2π(m+1) −2πm

2π(m+1)

e −2πm

−i(k−ℓ)ω

2 e−i(k−ℓ)ω |ϕ(ω)| ˆ dω = ∞ X

m=−∞

|ϕ(ω ˆ + 2πm)|2 dω.

Ez pedig valóban csak úgy lehet δk,ℓ minden lehetséges k, ℓ-re, ha (3) teljesül.

Állitás Egy ϕ ∈ L2 (R)-re a ϕ(t − k), k ∈ Z pontosan akkor Ha a ϕ MRA-ra alkalmas, akkor létezik olyan hk , ortonormált rendszer, ha a Fourier transzformáltjára k ∈ Z amire ∞ X √ X 1 hk ϕ(2x − k) ϕ(ω) = 2 |ϕ(ω ˆ + k2π)|2 = , (3) 2π k=−∞ minden ω ∈ [−π, π] esetén. \ Bizonyitás. Mivel ϕ(t − k) = e−ikω ϕ(ω), ˆ a hϕ(t − k), ϕ(t − ℓ)i = hϕ(t), ˆ ϕ(t\ + k − ℓ)i = I.4 Alapvető tételek

Ha H(s) a h sorozat Fourier transzformáltja, akkor: ϕ(s) ˆ = H(s/2)ϕ(s/2) ˆ Felhasználva az előző tételt:

MMIX

35

I. Elmélet


Állitás A h együtthatókkal meghatározott skála dilatációhoz tartozó ϕ approximáviós függvény egészszámokkal vett eltoltjai pontosan akkor ortogonálisak, ha a h együtthatók Fourier együtthatóira

36

több olyan ekvivalans tulajdonságról van szó, ami a matematikai kalkulus számos területén előfordul. Nem bizonyítjuk. De a kapcsolatos fogalmakat röviden összefoglaljuk, és kimondjuk a tulajdonságok ekvivalenciáját.

|H(s)|2 + |H(s + π)|2 = 1.

Értelmezések ˜ és (ϕ, ψ) függvénypárok által Tekintsünk egy a (ϕ, ˜ ψ) Állitás meghatározott biortogonális rendszert, aminek dilaHa V = Vk altérsor ortogonális MRA a ϕ skála függ˜ illetve h. Legyen Pn az a vetítés tációs együtthatói h vény és a h szűrő szerint, akkor a ami a ϕ-re a ϕn,k függvények által kifeszített altérre ∞ vetít, ami azt jelenti, hogy √ X X h−k−1 ϕ(2t − k) ψ(t) = 2 P f = hf, ϕñ,k i ϕn,k . n k=−∞ függvényre a ψj,k (t) a Wj alterek ortonormált bázisa. Legyen Qn a kiegészítő altérre vett vetítés, azaz Qn f = Pn+1 f − Pn f , Bizonyítás. A képlettel adott ψ ortonormált, bázis és L2 (R)-beli. vagyis a Pn+1 f egy léptékkel finomabb és a Pn f vetület különbsége.

Strang-Fix feltételek Azt mondjuk, hogy a ϕ approximációs rendje p, ha A waveletek fontos tulajdonság csoportja az, amit ||f − Pn f || = O((1/2p )n ), Strang-Fix feltételnek szokás nevezni ([4],[5]). Itt

azaz, ha ϕ szerinti approximáció hibája a ϕ finomodó dilatációja mellett 1/2p léptékben csökken. A ||Qn f || = O((1/2p )n ) becslés is érvényes mert igaz a ||Qn f || ≤ ||f − Pn f || + ||f − Pn+1 f || ortogonális rendszerben.

érvényes, m = 1, ..., p − 1-re. Ezt a feltételt szokás momentum feltételnek is nevezni.

Egy szűrő trigonometrikus polinomja h(ω) = P h −ikω h e . Megkaphatjuk ezt úgyPis, hogy vesszük k k k a z-transzformáltat azaz h(z) = k hk z -t a z = −iω helyettesitéssel. Azt mondjuk, hogy a ϕ pontossága p, ha m = e 0, 1, ..., p − 1-re van olyan cm,k együtthatórendszer, Azt mondjuk, hogy a h(ω)-nek ω = π-ben p-ed rendü amire X m gyöke van, ha h(ω) = (1+exp(−iω))p h0 (ω) egy megx = cm,k ϕ(x − k), felelő h0 (ω)-val, de itt inkább a k p azaz a polinomok p − 1. rendig hiba nélkül appro1 + e−iω h(ω) = h0 (ω) ximálhatóak. Ennek a tulajdonságnak az az érde2 kessége, hogy bár az egész elmélet alapvetően a L2 térben mozog, olyan függvények előállithatóságáról felbontást alkalmazzuk, hogy a h(0) = h0 (0) teljesüljön. van benne szó, amik nem L2 -beliek. Azt mondjuk, hogy a hk dilatációs együtthatók ki- A trigonometrikus polinom, diszkrét Fourier transzformált és a z transzformált formálisan nagyon haelégítik az összegszabályt p-re, ha a sonló, de mégsem szinonímája egymásnak. JelölésX ben sokszor csak az argumentum különbözteti meg k m (−1) k hk = 0 őket. Sok esetben egyszerübb a z transzformált fok I.4 Alapvető tételek

MMIX

37

I. Elmélet


38

galmával dolgozni, ami tulajdonképpen egy Laurent séges olyat konstruálnunk, amelyik a tulajdonságok polinom. bármelyikével rendelkezik. Állitás A következő feltételek ekvivalensek: - a ϕ approximációs rendje p - a ϕ pontossága p - a h kielégíti az összegszabályt p-re - a h(ω)-nak ω = π-ben p-ed rendü nullája van - a ϕˆ deriváltjai p − 1-ed rendig 2π-ben nullák A fenti állítás szerint tehát egyszerre érvényes, az hogy a finomság növekedésével hányadrendben javul a közelített függvény approximációja, hogy hányadrendü polinom az amit a wavelet-rendszer hibátlanul közelit, hogy a dilatációs együtthatók és egészszámhatvány vektor hányadik hatványa merőleges, hogy a dilatációs együtthatók z transzformáltjának az (1 + z) tényező hányadik hatványa osztója, és hogy a h mint szűrő mennyire pontosan választja szét a jel kis- és nagyfrekvenciás részeit. Azaz, ha olyan waveletet akarunk konstruálni amelyik a felsorolt tulajdonságok valamelyikével rendelkezik, akkor elég-

A tételt leggyakrabban abban a formában alkalmazzuk, hogy olyan waveletet konstruálunk aminek a pontossága p, és ezt úgy érjük el, hogy olyant konstruálunk, ami az összegszabálynak eleget tesz. Ez azért kényelmes feltétel, mert az ismeretlen dilatációs együtthatókra líneáris egyenletrendszert ad.

Állitás X ℓ

c2ℓ =

X

c2ℓ+1 = 1.

ℓ

Bizonyítás Egy korábbi állitás szerint: Z X X ϕ(2t − k) = ϕ(τ )dτ = ϕ(t − k). k

k

Ez a mennyiség, a dilatáció szerint, különvéve a pá-

ros és páratlan c-ket: Két ekvivalens fogalom Egy (ak ) líneáris szűrő szimmetrikus, ha van olyan XX X c2ℓ ϕ(2t−2k−2ℓ)+ c2ℓ+1 ϕ(2t−2k−2ℓ−1) m amire am−j = am+j minden j ∈ Z-re. Antiszimk ℓ ℓ metrikus, ha ugyanígy am−j = −am+j . XX XX Egy líneáris szűrő lineáris fázisu, ha a szűrő fázisto= ( c2ℓ )ϕ(2t−2j)+ ( c2ℓ+1 )ϕ(2t−2j −1) lása a frekvencia függvényében líneáris. j

ℓ

P

j

ℓ

Ez utóbbiból a γ2j = ℓ c2ℓ és a γ2j+1 = jelölésekkel minden t-re: X X ϕ(2t − k) = γj ϕ(2t − j).

P

ℓ c2ℓ+1

Ez utóbbi a következő módon értendő. A szűrő, az időbeli eltolás-invarianciája nyomán nyilván olyan, hogy nem változtatja meg a bemenő jel ciklushosszát. Sőt egy tisztán szinuszos (vagy koszinuszos) bemenetre a kimenet is egy tiszta szinusz függvény. Csak esetleg a kimenet amplitúdója és fázisa tér el a bemenet amplitudójától-fázisától.

Mint láthattuk, egy zördület szerinti transzformáltat úgy számolhatunk ki a megadott jelből, hogy vesszük megfelelő ritkítások és bővítések mellett a jel egy líneáris szűrés szerinti transzformáltját. Emiatt a waveletek alkalmazásakor két szempontból is fontos a líneáris szűrő alábbi két tulajdonsága.

Azt a függvényt ami megadja, hogy az egyes input frekvenciák mellett mennyi a kimenet amplitudója illetve mekkora a szűrő fázistolása a frekvencia válasz abszolútérték függvényének illetve a szűrő fázistolás függvényének nevezzük. Az, hogy egy szűrő fázistolása líneáris, azt jelenti hogy a mondott fázistolás függvény líneáris. Ez utóbbit szokás úgy is kifejezni,

k

j

Amiből az előzőek szerint γj = 1 minden j-re.

I.4 Alapvető tételek

MMIX

39

I. Elmélet


hogy a csoport késleltetés — group delay, ami nem más a fázistolás fázis szerinti deriváltja — konstans.

ϕ(t) =

40 P

k ck ϕ(2t

− k)

dilatációs egyenlet megoldására 4 lehetséges megolA két tulajdonság — mármint a szimmetria és a dást vázolunk. líneáris fázisúság — (lényegében) ekvivalens. A környezettől függ, hogy melyikre hivatkozunk. A szim- 1) Iterációval metria képfeldolgozás esetén lehet fontos. Ha egy A ϕ megtalálásának legkézenfekvőbb módja, venni képet soronként vagy oszloponként mint jelsorozatot egy tetszőleges kiinduló ϕ0 függvényt és abból a P dolgozunk fel, akkor jobb ha olyan transzformációt ϕn+1 (t) = k ck ϕn (2t − k) alkalmazzunk ami irányfüggetlen. A konstans késleltetés azt jelenti, hogy a szűrő olyan, hogy a tisztán képlet alapján lépésenként n = 1, 2, 3... -ra újat szászinuszos jeleket frekvenciától függetlenül időben molni. Az eljárással kapcsolatban fontos tudni, hogy azonos mértékben tolja el. Vagyis egy líneáris fá- olyan függvénysort határoz meg ami a megoldáshoz zisu szűrőnek egy jelen vett alkalmazása felfogható nem feltétlen egyenletesen konvergál. Ugyanakkor úgy, mint egy puszta újrasúlyozása annak, hogy a az iterációból is szépen látszik, hogy a ϕ tartójára 0 jel a harmónikus komponenseinek milyen keveréke, supp(ϕ) ⊂ [−N, N ] ha tudjuk hogy ha c 6= 0 akkor k anélkül hogy megváltoztatnánk a jel harmónikus k ∈ [−N, N ]. komponenseinek fázisait. A dilatációs egyenlet megoldása Adott ck együtthatók mellett, ahol

P

k ck

=2a

2) A Fourier transzformált alapján Vegyük a dilatációs egyenlet két oldalának Fourier transzformáltját. Ha a ϕ(t) Fourier transzformáltja Φ(ω) és a ck sorozaté C(ω) akkor a dilatációs egyen-

leté: Φ(ω) = C(ω/2)Φ(ω/2). √ Figyelembe véve, hogy C(0) = 1 és Φ(0) = 1/ 2π, az előbbi egyenlet ismételt felhasználásával: ∞ 1 Y √ Φ(ω) = C(ω/2n ). 2π n=1

Tehát a ϕ(t) Fourier transzformáltja a c dilatációs együtthatók Fourier transzformáltja alapján közelitően meghatározható. A ϕ(t) Fourier transzformáltjából pedig, az inverz Fourier transzformálással származtatható a keresett ϕ(t) skála függvény. 3) Rekurzióval Ez az a módszer amivel a DB4 és a LeGall wavelet rendszerek skála és zördület függvényeit kiszámoltuk. Azon alapul, hogy az egészszámokra felírt dilatációs egyenletek együttesen egy ϕ = Cϕ I.4 Alapvető tételek

típusú, sajátvektor egyenletet alkotnak, figyelembe véve, hogy a c-k és a ϕ egészszámokon felvett értékei közt végessok nem-nulla van. Itt ϕ egy vektor aminek elemeit a ϕ egészszámokon felvett értékei alkotják, és C egy olyan mátrix aminek soraiban — fordított sorrendben, soronként két pozícióval jobbra tolva — a c dilatációs együtthatók szerepelnek. (Azaz egy blokk Töplitz mátrix 1 × 2 méretü blokkokból.) Ha a c-nek megfelelő karakterisztikus polinom p-ed rendü gyökkel rendelkezik a −1-ben, akkor a C-nek p speciális sajátértéke van, annak megfelelően hogy a c-t úgy határoztuk meg, hogy mint szűrő p-ed rendben simuljon a 0-hoz a nagyfrekvenciájú hullámoknak megfelelő frekvenciákra: 1, 1/2, 1/4..., 1/2p−1 . Ezek közül az 1-hez tartozó sajátvektor adja meg a ϕ-t amivel tehát a ϕ(t) rendelkezésre áll a t ∈ Z halmazon. Ez az adathalmaz kiinduló pontja lehet egy rekurziós eljárásnak, mert — mint az könnyen látható — a dilatációs egyenlet olyan, ha ismert a ϕ(t) a k/2n , k ∈ Z pontokon valamely n ∈ Z mellett, akkor megadja a ϕ(t) értéket a t = k/2n+1 pontokra. Azaz, felhasználva a dilatációs

MMIX

41

I. Elmélet


P egyenletet a keresett skálafüggvény értékei tetszőleϕ(2j t − k) = i ci ϕ(2j+1 t − (2k + i)) = ges finomságu diadikus pontokon kiszámolható. P = ℓ cℓ−2k ϕ(2j+1 t − ℓ). Mint láthatjuk, ez az eljárás a skála függvényt úgy származtatja a dilatációs egyenletéből, hogy egy rekurziós számolásnak egy blokk Töplitz mátrix sa- Így játvektora a kiinduló pontja. A módszer hátránya, P P f (t) = ℓ k sj,k cℓ−2k ϕ(2j − ℓ). hogy a dilatációs együtthatók általában csak közelítően ismertek emiatt az eredmény pontossága is tehát korlátozott ([3]). P sj+1,ℓ = k cℓ−2k sj,k . 4) Az un. ’cascade’ algoritmussal Ez a legismertebb módszer skála függvények meghatározására. Ha f ∈ Vj ⊂ Vj+1 akkor P P f (t) = k sj,k ϕ(2j − k) = k sj+1,k ϕ(2j+1 − k).

Ugyanakkor

42

Ha tehát az iteráció az s0 , k = δk értékekből indul, akkor f (t) = ϕ(t) és mert a ϕ(2j t − k) tartója j → ∞ mellett egyre szűkebb, a ϕ(k/2j ) közelítően sjk . Azaz a mutatott speciális konvolúció ismételt alkalmazásával — a cascade algoritmussal — a ϕ értékei tényleg meghatározhatóak.

I.5 Ortogonális MRA Legyen V = · · · ⊂ Vj ⊂ Vj+1 ⊂ · · · az ℓ2 (Z) egy finomodó altér sorozata. Legyen a W = (. . . Wj , Wj+1 , . . .) egy olyan altérsor ahol Wj ortogonális Vj -re és Wj ⊂ Vj+1 . Azaz legyen W az olyan ortogonális kiegészítő alterekből álló sorozat amikre Wj ⊕ Vj ⊆ Vj+1 , ahol a tartalmazáson túl az egyenlőség nem feltétlenül teljesül. Feltételezzük, hogy a V0 illetve a W0 altereket a ϕ(t) illetve a ψ(t) függvények egészértékekkel eltolt, ortogonális példányai generálják. Továbbá azt, hogy a Vj illetve a Wj alterek függvényei a Vj+1 illetve a Wj+1 alterek függvényeiből (és fordítva) dilatációval létrehozhatóak. A mondott konstrukció esetén, Vj = spanϕj,k és a Wj = spanψj,k ahol ϕj,k = és ψj,k = tahát a ϕ illetve a ψ egészszámokkal eltolt és megfelelő mértékben dilatált példánya. Vagyis egy tetszőleges f (t) függvény Vj illetve a Wj -beli közelítése nyilván felírható, két megfelelően választott P P — általában (aj,k )-val illetve (dj,k )-val jelölt — együttható sorozat segítségével: fj (t) = k aj,k ϕj,k és k dj,k ψj,k . Megmutatjuk, hogy egy tetszőleges f (t) függvény Vj+1 -beli fj+1 (t)közelítése — azaz a közelítését meghatározó (aj+1,k ) együtthatósor — alapján hogyan számítható ki a függvény Vj illetve Wj -beli közelítése, azaz a közelítéseknek megfelelő (aj,k ) illetve (dj,k ) sorozatok. És fordítva, hogyan adható meg a (aj,k ) és a (dj,k ) sorozatok alapján az az (a∗j+1,k ) együtthatósor, ami az (aj,k ) és (dj,k ) sorozatokhoz tartozó Vj ⊕ Wj -beli közelítést úgy adja meg, mint egy Vj+1 -beli elemet? A vázolt konstrukció fontos tulajdonsága a V hierarchikussága és a W ortogonalitása. Például emiatt elégséges a Vj ⊕ Wj -beli közelítéshez a Vj+1 -beli közelítést venni és azt vetíteni külön-külön a Vj és a Wj alterekre, ha a Wj ⊕ Vj = Vj+1 teljesül. Az R-n értelmezett függvények esetén a közelítés első lépése, I.5 Ortogonális MRA

MMIX

43

I. Elmélet


44

hogy a függvény Z-beli pontokban vett értékeit vesszük, azaz hogy a függvényt diszkretizáljuk. Emiatt a továbbiakban feltételezhető, hogy a közelítendő függvény valójában egy diszkrét sorozat. Itt eddig és a továbbiakban is minden úgy értendő, hogy j ∈ Z tetszőleges! Legyenek a skála-függvény dilatációs együtthatói h: az f (t) legjobb Vj ⊕ Wj -beli közelítése. De kérdezhető az az a∗j+1,k együttható sorozat is, ami ezt a P ϕj,k (t) = k hk ϕj+1,k (t) közelítést mint Vj+1 -beli függvényt előállítja!

és a ψ zördület dilatációs együtthatói g: ψj,k (t) =

P

k

gk ϕj+1,k (t).

A számolások rövidítéséhez megmutatjuk, hogy és hogy

hϕj+1,k , ϕj,m i = hk−2m

Legyenek az f (t) függvény (sorozat) Vj+1 -beli fj+1 (t) hϕj+1,k , ψj,m i = gk−2m . közelítésének együtthatói aj+1,k , k ∈ Z: Ugyanis, az s = 2j − m jelölés mellett: √ P hϕ , ϕ i = 2−1 hϕ(2j+1 t − k), ϕ(2j t − m)i = j+1,k j,m fj+1 (t) = k aj+1,k ϕj+1,k (t). √ = 2−1 hϕ(2s + 2m − k), ϕ(s)i P Kiszámítjuk az f (t) legjobb Vj illetve Wj -beli kö= hϕ(2s + 2m − k), n hn ϕ(2s − n)i . zelítésének, azaz a megfelelő ’approximáció’-nak és ’részlet’-nek az aj,k illetve a dj,k együtthatóit. Ezekre És hasonlóan: √ az együtthatókra lesz: hϕj+1,k , ψj,m i = 2−1 hϕ(2j+1 t − k), ψ(2j t − m)i = √ P P ∗ 2−1 hϕ(2s + 2m − k), ψ(s)i = fj (t) = k aj,k ϕj,k (t) + k dj,k ψj,k (t)

P

elhagyjuk a nyert sorozatok páratlan sorszámú tagjait. Vagyis úgy, hogy ha a dilatációs együtthatókkal Ezekből a fenti képletek a ϕj,k (t) és a ψj,k (t) függvé- konvolvált eredményt sűritjük (down sampling). nyek ortonormalitását felhasználva adódnak. = hϕ(2s + 2m − k),

n

gn ϕ(2s − n)i .

Hasonló módon kiszámolhatjuk azt is, hogy mik azok Vegyük észre, hogy a fj+1 közelítésből, figyelembe a a∗ j+1,k együtthatók, amik a kapott véve a Vj és Wj merőlegességét, és a ϕ illetve a ψ P P eltolások melletti ortogonalitását: m aj,m ϕj,m + m dj,m ψj,m P aj,m = hfj+1 , ϕj,m i = k aj+1,k hϕj+1,k , ϕj,m i Vj ⊕ Wj -beli közelítéshez, mint Vj+1 -beli függvényhez tartoznak? Ehhez, figyelembevéve a függvények P dj,m = hfj+1 , ψj,m i = k dj+1,k hϕj+1,k , ψj,m i. ortogonalitását, a Itt felhasználva az előző számolásokat: P aj,m = k aj+1,k hk−2m dj,m =

P

k

aj+1,k gk−2m .

h

P

m

aj,m ϕj,m +

P

m

dj,m ψj,m , ϕj+1,k i

szorzatokat kell meghatározni k ∈ Z-re. A kifejezés azonos átalakítással: P

aj,m hϕj,m , ϕj+1,k i +

P

m dj,m hψj,m , ϕj+1,k i. Azaz a durvább, Vj altérben az approximáció és a Wj altérben a részlet együtthatói úgy határozhatóak Itt ismét felhasználva a korábban nyert képleteket: meg, hogy vesszük a finomabb Vj+1 altérbeli együttP P hatók konvolucióját a h illetve g együtthatókkal és a∗j+1,k = m aj,m hk−2m + m dj,m gk−2m .

I.5 Ortogonális MRA

MMIX

m

45

I. Elmélet


46

- h−k Azaz a finomabb térbeli approximációs együtthatók aj,m - ↑ 2 a durvább térbeli approximációs és részlet együttha?- a∗ j+1,m tók alapján úgy nyerhetők, hogy elöbb felhígitjuk a 6 - g−k dj,m - ↑ 2 durvább közelítés szerinti együtthatókat (up sampling, minden másodiknak nullákat írunk az együtthatók közé) majd a hígitott sorozatokat konvolváljuk Itt a téglalapalakú doboz a beírt szűrő szerinti filth-val illetve g-vel, és a két eredménysort összeadjuk. rációt, azaz eltolás invariáns líneáris transzformációt jelent. A szintézis esetén a felhasznált szűrők Vagyis beláttuk, hogy az a séma ami szerint az anaa h−k és a g−k , ami a reverz szűrőknek felel meg, lizis, azaz a durvább szint szerinti approximáció és hiszen mint láthattuk az a∗ előállításában az összegrészlet együtthatóinak kiszámolása elvégezhető: ben a h illetve a g futó-indexe negatív. A négyzet formájú dobozok a sűritést és a hígitást jelentik. - ↓ 2 - aj,m h Megjegyzendő, hogy ez utóbbi transzformációk nem eltolás invariáns transzformációk. Ráadásul míg aj+1,m ↓ 2 · ↑ 2 = I, addig ugyanez a ↑ 2 · ↓ 2-re nyilván g - ↓ 2 - dj,m nem érvényes. Vegyük észre, hogy ez utóbbi (azaz, hogy a ↑ 2 inverz jobbról, de balról nem) azáltal A szintézis számolási sémája. Azaz az, ahogy meg- lehetséges, hogy a transzformációkat a végtelen sohatározhatóak azok az együtthatók, amik adott app- rozatokon vizsgáljuk! roximáció és részlet együtthatóknak megfelelő közelítéshez finomabb szinten tartozó approximáció További az ortogonális MRA rendszerekhez tartozó filterekre érvényes nevezetes egyenlőségeket vezetheegyütthatói kiszámolhatóak.

P tünk le. Ehhez vegyük a dilatációs egyenletek eltolt hϕ(t), ψ(t − n)i = 0 = k hk gk−2n . változatait. Ezeket az egyenleteket nevezzük a dilatációs együttA skála függvényre érvényes: hatókra vonatkozó ortogonalitási feltételeknek. X √ ϕ(t − n) = hm 2ϕ(2(t − n) − m) m Ha g szűrőként valamely N-re, a X √ = hm 2ϕ(2t − (m + 2n)) gk = (−1)k hN −k m

=

X k

√ hk−2n 2ϕ(2t − k).

A zördületre hasonlóan levezethető, hogy igaz a: √ P ψ(t − n) = k gk−2n 2ϕ(2t − k).

szűrőt — a h reverz-alternáló párját — vesszük, akkor az utóbbi két ortogonalitási feltétel, feltételezve az első érvényességét nyilván igaz. És igazak a korábban mutatott tulajdonságokat felhasználva az alábbiak is:

A két dilatáció együtthatósorra ezekből az azonosságokból — ha a ψ és ϕ ortogonális — minden n ∈ Z-re következnek az alábbi egyenlőségek: P hϕ(t), ϕ(t − n)i = δ(n) = k hk hk−2n P hψ(t), ψ(t − n)i = δ(n) = k gk gk−2n és a kettőre együttesen:

I.5 Ortogonális MRA

MMIX

P

hk =

k

P

P

P

k

√

k

h2k = 1

k

h2k =

g2k =

P

2

P

P

k

P

k

k

k

gk = 0

gk2 = 1

h2k+1 =

√1 2

g2k+1 = ± √12 . 47

I. Elmélet


48

Megjegyzendő hogy a fenti g — a h reverz-alternáló gyan határozzák meg a ϕ és ψ függvényeket. párja — a g-re csak egy lehetséges választás. Hiszen a g nem egyértelmü. De mint láttuk az alternatív Ugyanakkor a dilatációs együtthatókra az ortogoválasztások közt más valós együtthatóju nincs. nalitási feltételek alapján eddig felírt egyenletekben több paraméter szerepel, mint ahány egyenlet van. Ezzel megmutattuk, hogy a dilatációs együtthatók Emiatt a fenti egyenleteknek több megoldása van. hogyan határozzák meg a jel approximációjának és Ezt kihasználva a következő, II. részben fogunk többa részleteinek kiszámolási módját. És a 3. pontban féle, további korlátozó feltételek bevezetése mellett, — a példáknál — azt is láttuk, hogy a dilatációs többféle ortogonális wavelet családot definiálni! együtthatók (legalábbis a reguláris esetekben) ho-

I.6 Biortogonális MRA

Definíció Egy (uk , vk ), k ∈ Z bázispárt biortogonális bázisnak nevezünk, ha hui , vj i = δi,j , i, j ∈ Z. Véges vektortér esetén, nyilvánvaló hogy a biortogonális bázispár bármelyike meghatározza a másikat. Ugyanis minden j ∈ Z-re, például a vj — szükségszerüen eleme annak az 1 dimenziós altérnek ami merőleges arra az altérre amit az uk , k ∈ Z, k 6= j vektorok feszítenek ki. A vj hosszát pedig, szintén minden j ∈ Z-re meghatározza a huj , vj i = 1 feltétel. És a vj -t valóban egyértelmüen határozza meg a hossza és egy 1 dimenziós altér, aminek eleme.

biortogonális bázispár fogalma, ha megvizsgáljuk hogyan jöhet létre ilyen bázispár az R2 -ben és az R3 -ban. Ha az R2 -ben felveszünk két tetszőleges vektort, amit u1 illetve v1 -nek tekintünk, akkor nyilvánvaló, hogy v2 , u2 ezekhez képest olyan mintha a (u1 , v1 )-et derékszöggel elforgattuk és megcseréltük volna:

A fenti megállapítás egyben azt is jelenti, hogy ha veszünk egy tetszőleges uk , k ∈ Z bázist, akkor van pontosan egy olyan vk , k ∈ Z bázis, amire a (uk , vk ), k ∈ Z ortonormált bázispárt alkot.

v 2

1 v 1 u2 BMB H j H

u1

Legegyszerübb úgy megérteni, hogy mit jelent a I.6. Biortogonális MRA

MMIX

49

I. Elmélet

PT//Zördületek és ráncok//MMIX P Ha R3 -ban az egyik bázisnak egy tetszőleges tripod az y = ∞ j=−∞ αj vj vektorra x = y. három (u1 , u2 , u3 ) vektorát vesszük, akkor a biortogonális párját (v1 , v2 , v3 )-at legegyszerübben úgy Könnyen látható, hogy ∀k ∈ Z esetén hozhatjuk létre, hogy vesszük azt a három vektort, hx, uk i = hy, uk i, ami az u tripod csúcsából indul, és merőleges az u tripod lapjaira. Ebből a konstrukcióból nyilvánvalóan látszik, ha az u derékszögü volt, akkor a v ugyanis ∞

X vektorai megegyeznek az u vektoraival! Ha viszont hy, uk i = α j v j , uk = az u tripod nem volt ortogonális, akkor a két bázis j=−∞ — szemben az R2 -beli esettel — már pl forgatással ∞ ∞ X X nem vihető át egymásba: különböznek a szögeik. = αj hvj , uk = αj δj,k = αk .

50

j=−∞ j=−∞ Állítás: rekonstrukció Ha (u, v) egy biortogonális bázis pár, és egy tetsző- Ebből pedig következik hogy a mondott egyenlőség leges x vektorra, ∀k ∈ Z esetén αk = hx, uk i, akkor fennáll, hiszen az uk , k ∈ Z bázis.

Vegyük az előző jelölések mellett az n = 2 esetet. Vagyis azt amikor a síkban két vektor pár van (u1 , u2 ) és (v1 , v2 ) amikre hu1 , v1 i = hu2 , v2 i = 1 és u1 ⊥v2 valamint u2 ⊥v1 ! Ebben az esetben azt kell igazolni, hogy egy tetszőleges x vektorra x = hx, u1 iv1 + hx, u2 iv2 . Megmutatjuk, hogy az állitás a kétdimenziós esetben milyen érdekes geometriai feladattá egyszerüsödik. Az előzőnél bonyolultabb, de teljesen elemi, szemléletes bizonyítás következik.

Legyen az origo az O pont. Legyenek az O-ból induló az u1 , u2 illetve v1 , v2 valamint a tetszőleges x vektorok végpontjai U1 , U2 , V1 , V2 és X. Jelölje az X vetületét az OU1 egyenesen T és a V1 vetületét ugyanezen az egyenesen R. Legyen az XT egyenes metszete az OV1 -el M . V2

b

X

1b *b U2 b b M MBB B bH B H O HH j H Hb HH U1 HH b H H T HH HH b

R

I.6. Biortogonális MRA

V1

−→

−→

−→

Látható, hogy OX=OM + M X, és hogy valamely −→

−→

−→

−→

a és b valós számokra OM = a· OV1 , M X= b· OV2 . Tehát ha belátjuk, hogy például a = hx, u1 i akkor az állitást igazoljuk. Márpedig ez utóbbi igaz, hiszen ha α = U1 OV1 ∠ és β = U1 OX∠, akkor |OT | = |x| cos(β) és |OR| = |v1 | cos(α). Ha ezeket az egyenlőségeket megszorozzuk |u1 |-el akkor egyrészt az hx, u1 i-t másrészt a hv1 , u1 i = 1-et kapjuk. Ugyanakkor az XT egyenes párhuzamos a V1 R-el, tehát az ROV1 △ és a T OM △ hasonlósága alapján: OM : OV1 = OT : OR = hx, u1 i : 1, ami bizonyítandó volt. Ilyen egyszerü esetben az is nyilvánvalóan látszik, hogyha az (u1 , u2 ), (v1 , v2 ) vektorpárok nem síkbeliek, hanem (3 dimenziós) térbeliek, akkor könnyen lehetséges, hogy a ’rekonstrukció’ nem az eredeti vektort állítja elő. Hiszen lehetséges, hogy az (u1 , u2 ) illetve (v1 , v2 ) vektorpárok ne ugyanazt a síkot feszítsék ki!

MMIX

51

I. Elmélet


52

Az ortogonális bázisok alkalmazása a tetszőleges bázisokkal szemben azért célszerü, mert amikor egy vektort az adott bázis szerint fel akartunk bontani, akkor a bázis egy-egy elemének együtthatóját meg tudtuk határozni csak a bázis megfelelő eleme alapján. Ugyanakkor ortogonális bázis esetén a vektor analízise (az együtthatók megállapítása) és szintézise (a felbontott vektor előállítása) ugyanazon bázis szerint történik. Mint láttuk a biortogonális bázispárok lehetőséget adnak arra, hogy úgy állítsunk elő egy tetszőleges vektort, hogy az ’analízis’t az egyik a bázis szerint, míg a ’szintézis’t pedig a másik bázis szerint végezzük. A biortogonális MRA definíciója A ϕ˜ és a ϕ függvénypár biortogonális, ha hϕ(t ˜ − j), ϕ(t − ℓ)i = δj,ℓ minden j, ℓ ∈ Z-re .

P ˜ j hj hj−2k = δk .

Ugyanis a dilatációs egyenlet szerint √ P ϕ(t − k) = 2 ℓ hℓ ϕ(2(t − k) − ℓ),

tehát A ϕ˜ és a ϕ függvények finomodóak, ha létezik olyan δk = hϕ(t), ˜ ϕ(t − k)i = ˜ és h együttható sorozat, amire teljesülnek a h P P √ P ˜ j hℓ hϕ(2t = 2 j ℓh ˜ − j), ϕ(2t − (2k + ℓ))i. ˜ j ϕ(2t ϕ(t) ˜ = 2 jh ˜ − j) √ P ϕ(t) = 2 ℓ hℓ ϕ(2t − ℓ) Ebből pedig — felhasználva hogy a ϕ(2t ˜ − j), j ∈ Z és a ϕ(2t − ℓ), ℓ ∈ Z rendszerek is biortogonálisak dilatációs egyenletek. — az állítás adódik. Sőt az összeget máshogyan paEgy finomodó biortogonális függvénypár dilatációs raméterezve az is látható, hogy együtthatóira — hasonlóan az ortogonális esethez — P ˜ belátható, hogy minden k ∈ Z-re ℓ hℓ−2k hℓ = δk .

e és V a biortogonális finomodó ϕ˜ illetve ϕ Legyen V által generált MRA. És legyen P˜j illetve Pj az a vetítés ami az L2 függvényeket V˜j -re illetve Vj -re vetíti, merőlegesen. Ekkor egy tetszőleges f függvényre a biortogonalitás miatt egyrészt: P P˜j f = ℓ hf, ϕj,ℓ (x)iϕ˜j,ℓ (x)

egészszámmal vett eltolásának.

fj ortogonális Vj -re és fordítva: Belátjuk, hogy a W Wj ortogonális Vej -re. Elég csak az utóbbit belátni, mert az állítás és a megfordítása szimmetria okán ekvivalens. Legyen tehát g ∈ Wj tetszőleges függvény. Ekkor g = Qj g = Pj+1 g − Pj g, de mivel Wj ⊂ Vj+1 , a Pj+1 gP= g is igaz: Pj g = 0. Figyelembe véve a másrészt Pj g = ℓ hg, ϕ˜j,ℓ (x)iϕj,ℓ (x) előállítást, a hg, ϕ˜j,ℓ i = 0 P Pj f = ℓ hf, ϕ˜j,ℓ (x)iϕj,ℓ (x). adódik minden ℓ-re. Vagyis érvényes, hogy a g ortogonális V˜j -re, amiből a bizonyítandó következik. ej illetve Qj azt a transzformációt, ami a Jelölje Q Ennek alapján látható hogy az is igaz, hogy függvényekhez az altérsorozatokon vett vetületek diffj ⊥Wℓ ha j 6= ℓ, minden j, ℓ ∈ Z-re W ferenciáit rendeli hozzá: ej f = P˜j+1 f − P˜j f Q

fj és Wℓ alterek ortogonáazaz a különböző indexü W lisak egymásra.

Qj f = Pj+1 f − Pj f . fj illetve Wj a Q ej illetve a Qj képterét. A Jelölje W fj és Wj terek dilatációkkal létrehozhatóak egymásW ból is, és invariánsak az olyan eltolásokra, amik a f0 és a W0 egy-egy dilatációk szerint megfelelnek a W I.6. Biortogonális MRA

Ha a ϕ˜ és a ϕ biortogonális finomodó függvényekre a megfelelő kaszkád algoritmusok konvergálnak, akkor léteznek a ψe és a ψ kiegészítő waveletek, és ezek közvetlenül is kiszámíthatóak a ϕ e és a ϕ skála függvényekből: létezik olyan g˜ és g együttható sorozat,

MMIX

53

I. Elmélet


hogy ˜ ψ(x) = illetve ψ(x) =

√ P 2 j g˜j ϕ(2x ˜ − j) √ P 2 ℓ gℓ ϕ(2x − ℓ).

54

e ψ) függvénypár is biortogonáis teljesül, azaz a (ψ, lis, tehát a wavelet dilatációs együtthatókra ugyanúgy mint ahogyan a skála dilatáció együtthatóira, teljesülnek a P P ˜j gj−2k = ℓ g˜ℓ−2k gℓ = δk jg egyenlőségek.

Ezekre a g˜ és g együtthatókra, az elöbb bizonyított Vagyis a biortogonális ϕ˜ és ϕ finomodó skála függortogonalitások miatt, vények szerinti MRA pár felépíthető a következő P P ˜ módon, a kaszkád algoritmus konvergciája esetén. ˜j−2k = ℓ hℓ−2k gℓ = δk . j hj g

ugyanúgy bizonyíthatóan mint az előző, hasonló Venni kell a függvénypárhoz tartozó ψ˜ és ψ biortoösszegek esetén. Ráadásul egy megfelelő választás gonális waveletek alapján a a g˜-ra és a g-re fj = span ψej,k és Wj = span ψj,k W ˜ k illetve a gk = (−1)k hk , a g˜k = (−1)k h fj és a Wj biortogonális minaltereket, amik közül a W f azaz a skála dilatáció együtthatóinak fordított sor- den j ∈ Z-re, és amik közül minden j 6= ℓ-re a Wj és rendben való alkalmazása, alternáló előjelekkel. Eb- a Wℓ ortogonális. Ekkor ből viszont nyilvánvaló, hogy a

e − j), ψ(t − ℓ)i = δj,ℓ hψ(t

Vej =

j−1 M

k=−∞

fk és Vj = W

j−1 M

k=−∞

Wk ,

Se S Vj és a Vej altér sűrü L2 -ben. A két középső sorban van f−1 , W−1 ), (W f0 , W0 ), (W f1 , W1 ) . . . . . . (W A konstrukció a következő módon szemléltethető a biortogonális részlet altérpárokból álló ortogonális altérpár sorozat. ··· Ve Ve Ve ··· * −1 * 0 * 1 * Megmutatjuk hogy biortogonális MRA esetén, ho>⊕ >⊕ >⊕ >⊕ f f f gyan lehet kiszámolni egy Vj+1 -beli fj+1 függvény ··· ··· W−1 W0 W1 approximáció együtthatóinak ismeretében a dur vább Vj térbeli approximáció és a durvább Wj tér··· W−1 W0 W1 ··· >⊕ >⊕ >⊕ >⊕ beli részlet együtthatóit. Illetve azt, hogy hogyan H H H H j j j j ··· H ··· V−1 H V0 H V1 H számolhatók ki azok a finomabb Vj+1 térbeli approxi∗ mációs együtthatók, amik ahhoz a fj+1 függvényhez Az ábra két felső sorában vannak az analízishez, a tartoznak, amire adottak azok az együtthatók, amik két alsó sorában pedig a szintézishez használt altér- a durvább Vj térbeli approximációhoz illetve a dursorok. Az első és az utolsó sor az approximációs vább Wj térekbeli részletekhez tartoznak. alterek, a két középső a részletek sorozata. A felső sor az analízis MRA Legyen P f = e e e e j+1 ℓ aj+1,ℓ ϕj+1,ℓ . V = · · · V−1 ⊂ V0 ⊂ V1 · · · A függvény durvább, Vj -beli approximációjának az utolsó sor pedig a szintézis MRA együtthatói: és az is igaz, hogy a

V = · · · V−1 ⊂ V0 ⊂ V1 · · · . I.6. Biortogonális MRA

aj,k = hfj+1 , ϕ˜j,k i. MMIX

55

I. Elmélet


Felhasználva, hogy ϕ˜j,k

P ˜ = mh ˜j+1,m m−2k ϕ

azonos átalakítással: P P ˜ m−2k hϕj+1,ℓ , ϕ˜j+1,m i. aj,k = ℓ m aj+1,ℓ h

Ebből a ϕj+1,ℓ és ϕ˜j+1,m biortogonalitása alapján: P ˜ ℓ−2k . aj,k = ℓ aj+1,ℓ h

Hasonlóan a durvább, Wj -beli részletek együtthatói: dj,k

= hfj+1 (t), ψ˜j,k i.

Felhasználva, hogy P ψ˜j,k = m g˜m−2k ϕ˜j+1,m

azonos átalakítással: P P dj,k = ℓ m aj+1,ℓ g˜m−2k hϕj+1,ℓ , ϕ˜j+1,m i.

56

Ismét a ϕ˜j+1,ℓ és ϕj+1,m biortogonalitásából: P dj,k = ℓ aj+1,ℓ g˜ℓ−2k .

∗ Vegyük most a finomabb Vj+1 térbeli fj+1 függvényt, a Vj ⊕ Wj térbeli előállítása alapján: P P ∗ fj+1 = ℓ aj,ℓ ϕj,ℓ + ℓ dj,ℓ ψj,ℓ .

A Vj+1 térbeli approximáció együtthatói ∗ a∗j+1,k = hfj+1 , ϕ˜j+1,k i.

Használjuk fel, hogy P P ϕj,ℓ = m hm−2ℓ ϕj+1,m és ψj,ℓ = m gm−2ℓ ϕj+1,m

innen, a ϕ˜j+1,k és ϕj+1,m biortogonalitásából: P P a∗j+1,k = ℓ aj,ℓ hk−2ℓ + ℓ dj,ℓ gk−2ℓ .

Vagyis azt láthatjuk, hogy a durvább térbeli approximáció és részlet együtthatói úgy származtathatóak ˜ illetve a g˜ analízis szűrőkkel konvolváljuk, majd a a finomabb térbeli együtthatókból, hogy azokat a h kapott sornak minden második elemét vesszük. A durvább térbeli approximációs és részlet együtthatókból

úgy kaphatjuk a finomabb térbeli approximáció együtthatóit, hogy elöbb a durvább térbeli együtthatókat felhígitjuk, minden második helyre nullákat írva, majd a kapott sorokat a h illetve a g szintézis szűrőkkel konvolváljuk, és a kapott konvoluciós sorokat összeadjuk. Azaz egy megfigyelési soron az analízis és szintézis a következő folyamatábra szerinti: -

˜ h

aj+1,m -

I.6. Biortogonális MRA

g˜

-↓ 2

- aj,m

-↓ 2

- dj,m

MMIX

-↑ 2

-

-↑ 2

-

h−k g−k

?- a∗ j+1,m 6

57

I. Elmélet


58

I.7 A PR feltétel

A PR (perfect reconstruction) azaz a pontos rekonstrukció feltétel azt jelenti, hogy a közelitett függvény előállítható a skála és a wavelet függvény szerinti közelítések összegeként. Előzőleg láttuk, hogy ha egy (ϕ, ψ) függénypár MRA rendszert alkot, akkor a hozzátartozó g és h dilatációs együtthatók alapján hogyan számolható egy függvény legjobb közelítő sorozata az adott MRA szerint. Pontosabban megmutattuk azt, hogy egy közelitett függvény esetén mi a kapcsolat az MRA szomszédos tagjain vett vetületeinek együtthatói közt: - egy adott finomságú approximációból hogyan számolható a durvább approximáció és részlet (a vetület együtthatók a durvább approximációs és detail térre) - egy adott finomságú approximációból és részletből hogyan számolható közelítés a finomabb approximációra (a finomabb approximációs térre vett vetület

együtthatói hogyan közelíthatőek a durvább approximáció és részlet együtthatók ismeretében) Az összefüggéseket részletesen végigszámoltuk abban az esetben amikor (ϕ, ψ) ortogonális rendszer és ˜ függvényekkel együtt biortogoakkor is, ha a (ϕ, ˜ ψ) nális rendszer. Most megmutatjuk, hogyan foglalható össze az a feltétel, hogy a mondott két transzformáció, a dekompozíció és a rekonstrukció egymás inverzei legyenek. Azaz, hogy a pontos rekonstrukció teljesüljön. A PR feltétel legkényelmesebben a mondott transzformációk modulációs mátrixával irható le.

P Egy c sorozat c(ω) = j cj e−ijω Fourier transzfor- Ennek megfelelően egy (an ) approximációs sorozat máltját, a c sorozat symbolumának is szokás nevezni dekompozíciós wavelet transzformáltjának két kom˜ g˜) dilatációs együtthatópár szerint: ponense a (h, ebben a témakörben. A symbolumokkal megfogalmazva annak a transzformációnak a symboluma, mely szerint elöbb vesszük a megfigyelési sor konvolúcióját egy c szűrővel, majd minden páratlan sorszámú tagot törölve sűritjük, a következő: ↓ c(ω) =

1 ˜ ˜ an−1 (2ω) = √ h(ω)a n (ω) + h(ω + π)an (ω + π) 2

1 dn−1 (2ω) = √ g˜(ω)an (ω) + g˜(ω + π)an (ω + π) 2 A rekonstrukció pedig:

1 (c(ω/2) + c(ω/2 + π)) 2

1 √ an (ω) = h(ω)an−1 (2ω) + g(ω)dn−1 (2ω) 2

vagy máshogy: 1 ↓ c(2ω) = (c(ω) + c(ω + π)) . 2

Ha figyelembe vesszük, hogy a fentiek esetén a 1 √ an (ω) = h(ω)an−1 (2ω) + g(ω)dn−1 (2ω) 2

Az inverz: a ritkítás, azaz minden jel közé egy nulla beirása és a konvolució c-vel, az elöbbi módon irva a is igaz, akkor a dekompoziciós és rekonstrukciós lépés a következő mátrix egyenletek formájába is irható. következő: A dekompozíció: ↑ c(ω) = c(2ω) ˜ ˜ + π) 1 an−1 (2ω) s (ω) h(ω) h(ω n √ = 2 dn−1 (2ω) sn (ω + π) g˜(ω) g˜(ω + π) I.7 A PR feltétel

MMIX

59

I. Elmélet


60

˜ h(ω) g ˜ (ω) A rekonstrukció: −1 ∗ ˜ (ω) = M (ω) = M ˜ + π) g˜(ω + π) h(ω s (ω) n √1 = 2 sn (ω + π) Ha ∆(ω) = det M (ω) = h(ω)g(ω +π)−h(ω +π)g(ω) akkor a szokásos mátrix invertálási képlettel: an−1 (2ω) h(ω) g(ω) = dn−1 (2ω) h(ω + π) g(ω + π) g(ω + π) −h(ω + π) 1 −1 M (ω) = ∆(ω) Jelölje az itt szereplő mátrixokat −g(ω) h(ω) h(ω) h(ω + π) M (ω) = Ez azonban, összevetve az M −1 (ω) korábbi képletég(ω) g(ω + π) vel, ha az M (ω) és az az M ∗ (ω) elemei polinomok, és csak úgy lehetséges, hogy a ∆(ω)-nak csak egy tagja ˜ ˜ nem-nulla. Ráadásul mert ∆(ω) = ∆(ω + π) ez a ˜ (ω) = h(ω) h(ω + π) . M polinom: g˜(ω) g˜(ω + π) ∆(ω) = αei(2n+1)ω Ezeket a mátrixokat nevezzük a wavelet transzformáció modulaciós mátrixainak. alakú valamely egész n-re és |α| = 1 mellett. A modulációs mátrixokal a PR azaz a perfekt rekonstrukció feltétele egy biortogonális wavelet esetén: ˜ (ω) = M (ω)M ˜ ∗ (ω) = I M (ω)∗ M Ebből:

Vagyis teljesülnie kell a g˜j = −1/α∗ (−1)j h∗2n+1−j és ˜∗ a gj = α∗ (−1)j h 2n+1−j összefüggésnek. Tehát ha a ˜ és h szűrők lényegében egyérPR teljesül, akkor a h telmüen meghatározzák a g˜ és g szűrőket.

Ennek az észrevételnek megfelelően, elégséges ha a A levezetés fontos ’mellékterméke’ a wavelet dilatábiortogonalitás mátrixos alakjából következő négy cio g illetve g˜ együtthatóira a következő állitás feltétel közül csak egy, például ha a Állitás ˜ ˜ + π) = 1 ˜ illetve h skála dilatációk esetén csak az alh(ω)h(ω) + h(ω + π)h(ω Valós h ternáló reverz g˜ illetve g wavelet dilatációk adhatnak feltételt teljesül. PR feltételnek elegettevő ortogonális illetve biortogonális wavelet rendszert.

I.7 A PR feltétel

MMIX

61

I. Elmélet


62

I.8 A lifting azaz a wavelet transzformáció felbontása

A lifting tipikus matematikai módszer. Azt szokták liftingnek nevezni, amikor egy műveletet az eredetivel ekvivalens, több lépésből álló műveletsorral helyettesítenek. Waveletek lifting felbontásának ötlete először W. Sweldens (1996,[2]) munkájában jelent meg. A wavelet transzformáció lifting felbontását eleinte az hajtotta, hogy a transzformációnak ez az útja algoritmikus megvalósítás szempontjából előnyösebb. Azóta kiderült, hogy arra is alkalmazható, hogy előállitsuk a wavelet transzformációs algoritmusok un egész (vagy adott pontosságu) változatát. Utóbbi időkben legtöbbször arra használják fel, hogy új többdimenziós nemszeparábilis waveleteket konstruáljanak. Elöbb csak azt mutatjuk meg, hogy mit jelent a akkor a klasszikus Haar transzformáció és az inverze lifting a Haar wavelet esetén és azt, hogy hogyan a következő két műveletet jelenti: lehet a lifting segítségével a klasszikus Haar transz√ ! √ 2 2 o + e e a formációt kevéssé redundáns egész transzformációvá √2 7→ √22 = 2 o d o− 2 e változtatni. De utóbb azt is bemutatjuk hogy a wa2 velet transzformáció esetén hogyan értelmezhető a √ ! √ 2 2 a − d e a lifting általánosabban. 2 2 √ √ = 7→ 2 2 o d a+ d 2

2

Ha (e, o) két egymásutáni jele egy jelsorozatnak ahol Abból véve a jelölést, hogy ‘even’ = e és ‘odd’ = o, az e a páros és az o pedig a páratlan sorszámú elem, valamint hogy az a = ‘approximation’, és a d = ‘de-

tail’. Minthogy ez utóbbiak a skála illetve a részlet mint a Haar-wavelet transzformált konstansszorosa: vektornak az elemei. értelmezhető a következő módon is: - Az a a skála érték, az approximáció, a közelítés: ′ A Haar transzformáció során, ha az (e, o) egészszá- két egymásutáni megfigyelés átlaga. mok, az (a, d)′ szükségszerüen irracionális. Ám ha a - A d a részlet, a detail, a változás: két egymásutáni √ wavelet transzformáltat 2-vel√megszorozzuk és az megfigyelés különbsége. inverz wavelet transzformáltat 2-vel elosztjuk, ak- És értékelhetjük úgy, hogy erre a két célra külön inkor olyan transzformációpárt nyerünk ami egymás formáció híján: ‘aligha tudnánk jobb tippet kapni’. inverze, és ha (e, o)′ egészszámok, akkor (a, d)′ is az: Ugyanakkor ez a wavelet transzformáció előállitható 1 1 a − d e a o+e e két transzformáció egymásutánjaként is: 2 = 7→ 21 = 7→ 1 o a + d d o−e o 2 2 a = e + 12 d e e a 7→ 7→ = d = o − e o d d De ekkor a lehetséges értékek száma a a és a d esetén kb kétszerannyi mint amennyi az o és az e esetén és az inverze, hasonló módon: volt. Ha viszont a transzformáció következő változa e e e = a − 12 d a tát vesszük: . = 7→ 7→ o o=d+e d d o+e e a − 12 d a e 2 7→ 7→ = = Így minden lépésben csak egy-egy komponenst móo d o−e a + 21 d o dosítottunk, és a módosítás is csak annyi, hogy az az értékkészlet szétszóródása legalább az első (az egyik koordinátát a korábbi kettő lineáris kombináaluláteresztő) komponens vonatkozásában már nem ciójával helyettesítjük. áll fenn. A transzformált pedig bár úgy jött létre, I.8 Lifting

MMIX

63

I. Elmélet


64

Ennek megfelelően a Haar wavelet transzformáció a re módosítjuk. következő lépésekben végezhető el: - kettébontjuk a v0 , ..., v2n−1 megfigyelési folyamatot, Hasonló módon a LeGall 5/3 transzformáció lifting a páros és a páratlan helyeken álló álló o0 , ..., on−1 felbontása. páros és e0 , ..., en−1 páratlan részsorozatokra. - a páratlan sorozatból kivonjuk a páros sorozatot 1 1 dj = oj − (ej + ej+1 ) aj = oj + (dj−1 + dj ) (dj = ej − oj , j = 0, ..., n − 1) 2 4 - a páros sorozathoz hozzáadjuk az elöbb nyert sorozat felét (aj = ej + dj /2, j = 0, ..., n − 1) 1 1 ej = aj − (dj−1 + dj ) oj = dj + (ej + ej+1 ) 4 2 A wavelet transzformáció ilyen felbontását nevezzük Ha pedig egész-transzformációt akarunk, akkor mert itt kétszer is kell egészrészt képezni, valamivel boliftingelésnek. nyolultabb kerekítési módszer a célravezető: Ha azt akarjuk, hogy a művelet egész számokat egész 1 1 1 számokba vigyen, akkor az aj kiszámításakor vegyük dj = oj − 2 (ej +ej+1 ) ; aj = oj + 4 (dj−1 +dj )+ 2 a dj /2 alsó egészrészét: azaz legyen aj = ej + ⌊dj /2⌋. Az így adódo transzformációsornak nyilván az lesz az 1 1 1 inverze, ha az ej számítási módját a ej = aj −⌊dj /2⌋- ej = aj − 4 (dj−1 +dj )+ 2 ; oj = dj + 2 (ej +ej+1 ) A liftingből az az általános algoritmikus haszon származik, hogy a wavelet transzformálás ‘helyben’ és néhány, a transzformált sor hosszától független számú lépésben elvégezhető. Nincs szükség külön tárhelyre. Az egyes frissitési lépések mindig az előző lépésben előállt adatokat használják fel.

A műveleteket rajzban a következő módon szokás bemutatni: lazy wavelet even x

- split

dual lifting ?

predict ?

primal lifting 6

a

- ···

update 6

6

update

- ···

6

?

predict ?

?

merge

-x

6

odd d A fenti, lifting séma szerinti számolást a Haar és a különbség, hogy most (lusta módon) nem törődtünk LeGall esetén is a waveletek ismert szűrőiből vezet- azzal, hogy elkülönítsük a megfigyelések frekvencia szerinti fázisait: külön az alacsony és a magas frektük le. venciáju részt. Ám az egyes lépéseket a következő módon is lehet értelmezni. Az első lépésben kettévágjuk a megfigyelési sort a páros és páratlan sorszámu megfigyelésekre. Az így nyert, két fele-hosszu megfigyelési sort az eredeti megfigyelések lazy azaz lusta wavelet transzformáltjának szokás nevezni. Azon az alapon, hogy ebből a két komponensből ugyanúgy visszanyerhető az eredeti megfigyelési sor, mint a ‘nemlusta’ wavelet transzformációk esetén. ‘Csak’ az a I.8 Lifting

A következő lépések a lustaságból származó hibákat korrigálják. Megkeressük, hogy a skála komponensnek szánt ‘even’ azaz páros rész szegítségével, hogyan javítható a részlet komponensnek szánt ‘odd’ azaz páratlan rész: ‘predict’. Majd e becsléssel javított hiba segítségével karbantartjuk a skála értéket: ‘update’. Elöbb a ‘részletek’et javitjuk, majd az ‘approximáció’t.

MMIX

65

I. Elmélet


Az inverz transzformálás esetén az a és d komponensből, ugyanezeket a lépéseket forditott sorrendben megtéve, előálltjuk az eredeti megfigyeléssor páros és páratlan komponensét, és ezek egyszerü összefésüléssel az eredeti, teljes megfigyeléssort: ‘merge’. Wavelet transzformált lifting felbontása

66

Legyen egy x számsor z-transzformáltja P tetszőleges −k z(x) = . Ekkor a z 2 helyen az xe számk xk z sor z-transzformáltja xe (z 2 ) = 12 (x(z) + x(−z)) és az xo z-transzformátja, szintén a z 2 helyen xo (z 2 ) = z2 (x(z) + x(−z)). És az is nyilvánvaló, hogy x(z) = xe (z 2 ) + z −1 xo (z 2 ).

A szakasz első részében megmutattuk, hogy a Haar Ezekkel a jelölésekkel az x konvoluciója egy wavortogonális és a LeGall biortogonális wavelet transz- elet transzformáció (h, g) filterpárja szerint, polinom formálás hogyan bontható fel a fentiekben vázolt mátrixos reprezentációban: értelmezésü lifting lépésekre. Most megmutatjuk, lp(z) h(z) x(z) = hogy ugyanez egy tetszőleges PR wavelet esetén hp(z) g(z) pontosabban mit jelent. Jelentse egy tetszőleges x számsor esetén az xe , vagyis az e index azt, hogy a számsor páros indexü helyeken szereplő tagjaiból képzett számsort vettük. Hasonló módon az o index (tehát xo ) pedig azt, hogy az adott sor páratlan indexüekből álló részsorát vettük. Legyen az ugyanígy értelmezett részsor például egy h szűrő esetén a he illetve a ho .

Itt a hp illetve lp a megfigyeléseknek a transzformációk szerint leválasztott alacsony illetve magas frekvenciás részét jelenti. Mivel a tényleges wavelet transzformált, (a, d)T ennek a két komponensnek a ritkításával keletkező hpe és lpe :

a(z 2 ) d(z 2 )

=

lpe (z 2 ) hpe (z 2 )

=

1 (lp(z) 2 1 (hp(z) 2

+ lp(−z)) + hp(−z))

Tehát a wavelet transzformált polinomok feletti mát- A duális lifting polifázis mátrixa és annak inverze: rixok szorzásával: 2 1 −s(z) 1 0 a(z ) x(−z) h(−z) h(z) = 21 . 0 1 s(z) 1 d(z 2 ) x(z) g(−z) g(z)

Ez azonban kevesbé hatékony. Hiszen elöbb kiszáa primal lifting polifázis mátrixa és annak inverze: mítjuk az ‘egész’ konvoluciót, majd a felét ‘kidob juk’. Viszont nyilván érvényes, hogy : 1 t(z) 1 0 0 1 −t(z) 1 a(z) = lpe (z) = he (z)xe (z) + z −1 ho (z)xo (z) d(z) = hpe (z) = ge (z)xe (z) + z −1 go (z)xo (z) Ebből pedig: xe (z) he (z) ho (z) a(z) . = z −1 xo (z) ge (z) go (z) d(z) Jelölje a

egy-egy a transzformációnak megfelelő s(z) illetve t(z) Laurent polinommal. Nevezetesen például a LeGall wavelet polifazis mátrixának lifting felbontása:

1 he (z) ho (z) P (z) = 1 0 1 0 1 4 t + 41 z ge (z) go (z) P (z) = − 12 z −1 − 12 1 0 1 0 − 21 mátrixot. Ezt a mátrixot szokás a transzformáció polifázis mátrixának nevezni. A lusta wavelet A transzformáció ezen felbontásából, az előzőek transzformált polifázis mátrixa nyilván az identitás: alapján nyilvánvalóan adódnak az invertálás lépé sei. Sőt a transzformáció egész változata is. 1 0 P (z) = 0 1

I.8 Lifting

MMIX

67

I. Elmélet Felbontás lifting lépésekre


68

zik az eredetileg végrehajtandótól. Ráadásul:

ho (z) = s(z)he (z) + h′o (z) Az általános lifting felbontás tehát a wavelet traszformáció polifázis mátrixának a go (z) = s(z)ge (z) + go′ (z) Y 1 0 1 sk (z) K1 0 Vagyis a megmaradó transzformáció rész a ho (z) P (z) = tk (z) 1 0 1 0 K2 illetve go (z) Euklideszi típusu osztási maradéka az k he (z) illetve ge (z) szerint. Tehát a h′o (z) illetve szorzat alakban való felirását jelenti. Az, hogy tet- g ′ (z) Laurent polinom rangja kisebb mint amennyi o szőleges polifázis mátrix felirható ebben a formában a h (z) illetve g (z) polinomoké volt. (A rang itt ano o könnyen következik abból a megfigyelésből, hogy ho- nak az index intervallumnak az elemszáma minusz gyan változtatja meg például egy primál lifting lépés egy, amibe a polinom nem-nulla együtthatói esnek.) leválasztása a végrehajtandó transzformáció polifá- Maga az osztás nyilván nem egyértelmü. zis mátrixát: A duális lifting lépés hasonló. Az, hogy a felbontás 1 s(z) he (z) h′o (z) he (z) ho (z) = ′ véges lépésben végetér a PR feltétel miatt érvényes. 0 1 ge (z) go (z) ge (z) go (z) Ugyanis a PR feltétel a polifázis mátrixokkal megfoazaz a leválasztott lépés után még végrehajtandó galmazva azt jelenti, hogy: P (s)Pe(z −1 )′ = I emiatt transzformáció csak a második oszlopában különbö- a determinánsa általában 0-ad rendü polinom.

II.0 Wavelet konstrukciók: előszó Ortogonális Daubechies wavelet Ortogonális Coiflet Ortogonális symmlet Biortogonális spline wavelet

II.1 II.2 II.3 II.4

70. 78. 80. 81.

oldal oldal oldal oldal

Az előző, elméleti részben megismerkedtünk a waveletek fogalmával és azok alapvető tulajdonságaival. Általános összefüggéseket mutattunk be a waveletek lehetséges paraméterei közt és bemutattunk néhány egyszerü waveletet is annak érdekében, hogy jobban elképzelhető legyen a működési módja ennek a kifejezetten elméleti elgondolásokból levezetett ám mégis gyakorlati módszernek. E rész hat szakasza a két legfontosabb wavelet osztálynak és a három legklasszikusabb szerkesztési elveknek felel meg. A két wavelet osztály: az ortogonális és a biortogonális. A három szerkesztési elv: ortogonalitás, szeparáció és szimmetria.

II.0 Wavelet konstrukciók: előszó

MMIX

69

II. Konstrukciók


70

II.1 Daubechies ortogonális wavelet családja Azt, a korlátos tartójú ortogonális wavelet családot mutatjuk be, ami néhány — ma, történetileg alkalminak mondható — kisérlet után az első olyan volt, ami a széleskörü gyakorlati alkalmazhatóság szempontjából is kielégítő tulajdonságokkal rendelkezik. Ezt a wavelet családot Ingrid Daubechies szerkesztette felkérésre, 1983-ban az alábbi elvek alapján. Egy ortogonális wavelet rendszert közvetlenül a két dilatációs együtthatósora határozza meg: az általában h-val jelölt skála dilatáció és a g-vel jelölt részlet (vagy wavelet) dilatáció. Tehát ahhoz, hogy egy ilyen rendszert egyértelmüen megadjunk a (h, g) együttható sorozat párt kell megadnunk. Ugyanakkor azt is láttuk, hogy a h ismeretében a g egyértelmü, ha valós-együtthatós rendszert akarunk konstruálni. Ezért a továbbiakban csak azt vizsgáljuk: melyek azok a feltételek, amik a h-t meghatározhatják.

Ez a két feltétel a következőket jelenti: - Megköveteljük a talált h skála dilatációs együtthatókkal kapcsolatban, hogy a hozzájuk tartozó ϕ függvény időbeli eltoltjai ortogonális rendszert alkossanak.

- Megköveteljük, hogy a megfigyelési sornak a ϕ(t − k), k ∈ Z függvények (azaz a ϕ és annak az egészszámokkal vett eltoltjai) összes lehetséges lineáris kombinációja közül vett legjobb approximációja olyan legyen, hogy tartalmazza a megfigyelési I. Daubechies, mint a családot meghatározó tulaj- sor alacsony frekvenciás komponenseit, de ne tartaldonságot az ortogonalitást és a megfelelő szűrő alul- mazza a magas frekvenciás komponenseket. áteresztő tulajdonságát választotta.

A két feltétel matematikai nyelven a következő: - a ϕ(t), ϕ(t − 1), ϕ(t − 2), ... függvények alkossanak ortonormált rendszert; - ha a h szűrő Fourier transzformáltja H(ω), akkor H(0) 6= 0 és H(π) = 0 legyen.

A H-ra tett két kikötés — ahhoz, hogy a h alul áteresztő, felül stoppos legyen: minimális. Azzal szokás kiegészíteni, hogy a π-ben ne csak a H(ω), hanem annak deriváltjai is nullák legyenek. Ugyanis ennek teljesülése a remények szerint azt eredményezi, hogy a H(ω) nem csak a π-ben nulla, hanem Az eltolt ϕ(t) függvények ortogonalitása a skála dila- lényegében annak a környezetében is. tációs tulajdonsággal együtt, a következőket jelenti. Nézzük hogy mit jelent a h-ra nézve az, hogy H(π) = Mivel a skála-dilatáció szerint: 0 és hogy a H (d) (π) = 0, d = 1, 2.... Azaz, hogy a h P ϕ(t) = hj ϕ(2t − j) Fourier transzformáltja és annakP néhány deriváltja a π-ben nulla! Deriválva H(ω) = j hj eijω -t és beheFelhasználva, hogy ortogonális függvények dilatáltja lyettesítve a π-t, m = 0, 1, 2, ...-ra nyerjük hogy: ortogonális, tehát hogy a ϕ(2t), ϕ(2t−1), ϕ(2t−2), ... X függvények ortogonálisak: (−1)k hj j m = 0 P j hϕ(t), ϕ(t − k)i = j hj hj+2k = δk . Azaz, hogy: Azaz, hogy: h0 − h1 + h2 − h3 + ... = 0 −h1 + 2h2 − 3h3 + 4h4 − ... = 0 h20 + h21 + h22 + h23 + ... = 1 −h1 + 22 h2 − 32 h3 + 42 h4 − ... = 0 h0 h2 + h1 h3 + h2 h4 + ... = 0 −h1 + 23 h2 − 33 h3 + 43 h4 − ... = 0 h0 h4 + h1 h5 + h2 h6 + ... = 0 ... ... II.1 Daubechies ortogonális waveletei

MMIX

71

II. Konstrukciók


72

Tehát az ortogonalitási feltételek egy nemlineáris A normalizálás feltétele: egyenletrendszert jelentenek, míg az approximációs h20 + h21 + ... + h2L = 1 kiegészitő feltételek egy lineárisat. Az

L−1 2

= m darab ortogonalitási feltétel: Ha olyan ϕ-t akarunk konstruálni ami véges tartóju, akkor olyan h szűrőt kell konstruálni aminek végesh0 h2 + h1 h3 + ... + hL−3 hL−1 + hL−2 hL = 0 .. sok tagja nem nulla. Könnyen látható, hogy ebből . az ortogonalitási feltételek miatt az is következik, h0 h2k + h1 h2k+1 + ... + hL−2k hL = 0 hogy nem lehet olyan a h nem-nulla együtthatóinak .. . helyeit fedő legrövidebb intervallum, hogy abban páh0 hL−1 + h1 hL = 0 ratlan számu hely van. Ugyanis, ha ilyet akarnánk konstruálni akkor az ortogonalitási feltételek közül Az m + 1 darab kiegészítő, approximációs feltétel: az utolsóban, a páros hellyel való eltolások miatt, csak 1 szorzat volna: a nem-nullának megengedett h0 −h1 + h2 − h3 + ... −hL =0 együtthatók közül az első és az utolsó szorzata. Eb−h1 + 2h2 − 3h3 + ... −LhL = 0 .. ből pedig szükségszerüen következne, hogy az első és . az utolsó közül egyik mégis nulla. −h1 + 2m h2 − 3m h3 + ... −Lm hL = 0 Vagyis, csak olyan ortogonális wavelet rendszer lé- Ezzel 1 + L−1 + L+1 = L + 1 = M darab, azaz 2 2 tezhet, amiben a h nemnulla tagjainak száma: L + ugyanannyi egyenletet határoztunk meg, mintahány 1 = M = 2, 4, 6, ...! Tehát a megoldandó egyenlet- ismeretlen a keresett szűrőben van. rendszerek tetszőleges (páros) M esetén:

Ezek az egyenletek sajnos csak néhány kisebb M érték mellett oldhatóak meg explicit módon.

h20 + h21 = 1 h0 − h1 = 0

Ennek az egyenletrendszernek a megoldása a Haar Állitás A H(−1) = 0 approximációs és az L−1 db ortogona- wavelet. Az adott wavelet-családon belüli neve: DB2. 2 litási feltétel mellett, a két normalizációs feltétel: √ P P A fentiek szerinti egyenletrendszer M = 4-re: a k h2k = 1 és a k hk = 2 ekvivalens.

Állitás A fenti L + 1 darab egyenletnek 2(L+2)/4 valós megoldása van, és ebből egyetlen olyan, amire a h karakterisztikus polinom minden — nem −1-el egyenlő — gyöke az egységkörön kívüli.

h20 + h21 + h22 + h23 h0 h2 + h1 h3 h0 − h1 + h2 − h3 −h1 + 2h2 − 3h3 + 4h4

= = = =

1 0 0 0

Speciális esetekben az egyenletnek általában azt az, Ennek az egyenletrendszernek a megoldása a korábelőző állítás szerinti egyetlen megoldását vesszük, ban, I.3 rész 2. példájaként részletesen leírt DB4. amire a gyökök egysékörön kívüliek. Ugyanis az az Ujabb példaként vegyük az M = 6 esetét. egyetlen, amire a nyert szűrők stabilisak. Ha M = 6, az ortogonalitási egyenletek száma 3: Néhány speciális eset a korábbiak szerint már ismert. Legyen M = 2, ekkor az egyenletrendszer:

II.1 Daubechies ortogonális waveletei

MMIX

h20 + h21 + h22 + h23 + h24 + h25 = 1 h0 h2 + h1 h3 + h2 h4 + h3 h5 = 0 h0 h4 + h1 h5 = 0 73

II. Konstrukciók


És az approximáxiós feltételek száma is 3: h0 − h1 + h2 − h3 + h4 − h5 = 0 0h0 − 1h1 + 2h2 − 3h3 + 4h4 − 5h5 = 0 0h0 − 1h1 + 4h2 − 9h3 + 16h4 − 25h5 = 0

74

Legyen az y első 8 jele a = (a0 , a1 , . . . , a7 ), az approximáció. A második 8 pedig a d = (d0 , d1 , . . . , d7 ), a részletek. Fel fogjuk irni részletesen a A x=y D

Ennek az egyetlenrendszernek is explicit felirható a egyenletet! Itt az A a transzformált approximációs stabilis megoldása: p √ √ √ 2 résznek, D pedig a transzformált detail részének feh0 = 32 1 + 10 + 5 + 2 10 p √ lel meg. Az A azt a 8 × 16-os mátrixot jelöli, ami √ √ h1 = 322 5 + 10 + 3 5 + 2 10 a h-ból származik és az x-ből az y első 8 elemét p √ √ √ 2 adja. És D hasonlóan a g-ból adódik és az y utolsó h2 = 32 10 − 2 10 + 2 5 + 2 10 8 elemét adja. Ugyanakkor az g a korábbiak szerint p √ √ √ h3 = 322 10 − 2 10 − 2 5 + 2 10 (g0 , g1 , g2 , g3 , g4 , g5 ) = (h5 , −h4 , h3 , −h2 , h1 , −h0 ). p √ √ √ h4 = 322 5 + 10 − 3 5 + 2 10 Ahhoz, hogy a pontos rekonstrukció megvalósuljon p √ √ √ a h5 = 322 1 + 10 − 5 + 2 10 A T T A |D = D Érdemes kipróbálni, hogy az így nyert transzformá T ció tényleg PR. Azaz olyan, hogy a transzformáltból I8 0 A A AT D = = = I16 tényleg visszanyerhető az eredeti jel. DT A DT D 0 I8

egyenlőségnek kell teljesülnie. Legyen az eredeti jel a 16 hosszu x és a transzformált Behelyettesítés mellett láthatjuk: az állitás igaz! a szintén 16 hosszu y.

                           

h5 0 0 0 0 0 h1 h3 g5 0 0 0 0 0 g1 g3

h4 0 0 0 0 0 h0 h2 g4 0 0 0 0 0 g0 g2

h3 h5 0 0 0 0 0 h1 g3 g5 0 0 0 0 0 g1

h2 h4 0 0 0 0 0 h0 g2 g4 0 0 0 0 0 g0

h1 h3 h5 0 0 0 0 0 g1 g3 g5 0 0 0 0 0

h0 h2 h4 0 0 0 0 0 g0 g2 g4 0 0 0 0 0

0 h1 h3 h5 0 0 0 0 0 g1 g3 g5 0 0 0 0

0 h0 h2 h4 0 0 0 0 0 g0 g2 g4 0 0 0 0

0 0 h1 h3 h5 0 0 0 0 0 g1 g3 g5 0 0 0

0 0 h0 h2 h4 0 0 0 0 0 g0 g2 g4 0 0 0

A feltételek általános megoldása Vegyük a skála dilatációs egyenlet együtthatóinak P m0 (ω) = √12 n hn e−inω

0 0 0 h1 h3 h5 0 0 0 0 0 g1 g3 g5 0 0

0 0 0 0 h1 h3 h5 0 0 0 0 0 g1 g3 g5 0

0 0 0 0 h0 h2 h4 0 0 0 0 0 g0 g2 g4 0

0 0 0 0 0 h1 h3 h5 0 0 0 0 0 g1 g3 g5

0 0 0 0 0 h0 h2 h4 0 0 0 0 0 g0 g2 g4

                           

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15





                          =                          

a0 a1 a2 a3 a4 a5 a6 a7 d0 d1 d2 d3 d4 d5 d6 d7

                           

polinom. Ha feltesszük, hogy a megfelelő skála függvény egészértékü eltoltjai ortonormált rendszert alkotnak, akkor

transzformáltját, ami valójában egy trigonometrikus

II.1 Daubechies ortogonális waveletei

0 0 0 h0 h2 h4 0 0 0 0 0 g0 g2 g4 0 0

MMIX

|m0 (ω)|2 + |m0 (ω + π)|2 = 1. 75

II. Konstrukciók


76

Ha azt akarjuk, hogy a h aluláteresztő szűrő legyen Megjegyzés 1 ≤ N mértékben, akkor kell, hogy az m0 (ω)-nak A Bezout tétel viszonylag egyszerüen bizonyítható N -szeres gyöke legyen a π. Vagyis, hogy — akár konstruktíven is — a legnagyobb közös osztó képzésére alkalmas Euklideszi algoritmussal. Ez a N 1 + e−iω tétel szerint, egy m0 (ω) = L(ω) 2 A(y)C(y) + B(y)D(y) = 1 alaku legyen, ahol a L(ω) is egy trigonometrikus po- alakú egyenletnek, ha az A(y) egy adott n-ed fokú linom. és a B(y) egy adott m-ed fokú relatív prím polinom, Ha M0 (ω) = |m0 (ω)|2 , akkor egyetlen olyan megoldása van, ahol C(y) legfeljebb m − 1-ed fokú és D(y) egy legfeljebb n − 1-ed fokú M0 (ω) = (cos2 (ω/2))N L(ω) polinom. ahol az L(ω) = |L(ω)|2 a cos(ω) polinomja, és a M0 (ω) + M0 (ω + π) = 1

Ha az idézett Bezout tételt az A(y) = (1 − y)N és a B(y) = y N polinomokra alkalmazzuk akkor azt kapjuk, hogy a

egyenlet is teljesül. Ebből pedig, a sin2 (ω/2) = (1 − cos(ω))/2 és további helyettesités mellett az

(1 − y)N P (y) + y N Q(y) = 1

(1 − y)N P (y) + y N P (1 − y) = 1 ekvivalens egyenletet nyerjük.

egyenletnek egyetlen olyan megoldása van, ahol a P (y) és a Q(y) legfeljebb N − 1-ed fokú. Ha ebben az egyenletben az y helyébe 1 − y-t írunk, akkor a y N P (1 − y) + (1 − y)N Q(1 − y) = 1

egyenletet kapjuk. Vagyis azt, hogy a korábbi egyenletnek P -re és Q-ra a Q(1 − y) és a P (1 − y) is legfeljebb N − 1 fokszámu polinom megoldása. Ugyanakkor ez — az egyértelmüség miatt — csak úgy lehet, ha P (y) ≡ Q(1 − y) és Q(y) ≡ P (1 − y)!

valósegyütthatós szimmetrikus polinomnak — minden z gyökére a z, az 1/z és a 1/z is megoldás. Tehát a gyöktényezős felbontás alapján található olyan h(z) amire h(z)h(1/z) = p(z). Sőt a h(z) egyértelmüen megválasztható úgy, hogy minden gyöke az egységkörön kívül legyen.

Ugyanakkor az egyenlet explicit megoldható, hiszen A tárgyalt waveltekre DB2, DB4, ... stb hivakozása az utóbbi azonosság felhasználásával: viszonylag általános, úgy értelmezve hogy a szám a P (y) = (1 − y)−N (1 − y N P (1 − y)) = nemnulla dilatációs együtthatók száma. De a szám PN −1 N +k−1 k N y + O(y ). = k=0 k néha értendő, hogy a wavelet approximációs rendItt a jobb oldalra a megfelelő Taylor sort irtuk, ami- jével egyenlő: és ez sorszámozásként is értelmezhető. ből — ismét felhasználva a legfeljebb N rangu megoldás egyértelmüségét — a megoldásra a A DBn waveletek együtthatóiról sokfele található összfoglaló táblázat. A legegyszerübb programokban N −1 X N +k−1 k is található olyan eszköz, aminek segítségével a ϕ, ψ y P (y) = k függvények kirajzolhatóak. Megjegyezendő, hogy e k=0 függvények simasága és az általuk vetett hullámok explicit képlet adódik. Az így nyert P (y)-ból az száma a fokszám növekedtével nő, az aszimmetria y = 1 − cos(ω)/2 = (−e−iω + 2 + eiω )/4 pedig csökken. De a DB2-et kivéve egyik sem az. Ez, és z = e−iω helyettesitéssel egy Laurent polinomot ha egy DBn a szűrőt vizuálius céllal képfeldolgozásra nyerünk, ami z N -el való szorzás után egy p(z) szim- alkalmazzuk, kellemetlen eltolódásokat okozhat. metrikus polinomot ad. A p(z) polinomnak — mint II.1 Daubechies ortogonális waveletei

MMIX

77

II. Konstrukciók


78

II.2 Ortogonális Coiflet Az ortogonális coifleteket I. Daubechies konstruált először, 1993-ban. Ez a wavelet rendszer olyan, hogy a hozzá tartozó ϕ approximációs és ψ részlet függvényeknek egyaránt, meghatározott pontossságu közelítési tulajdonsága van. Szemben a korábban definiált ortogonális Daubechies waveletekkel, amik esetén csak a ψ részlet függvények birnak előirt közelítési tulajdonsággal. Az új wavelet rendszer arról a Ronald Coifman matematikusról kapta a nevét, aki először felvetette az ilyen tulajdonságú waveletek szükségességét. Az eredeti ötlet az volt, hogy olyan wavelet rendszert approximációs rész jó közelítéssel egyenlő a közelíkonstruáljanak, amiben a skála és a zördület résznek tett jelel. azonos számú eltünő momentuma van. Azaz olyat, R amire a skála függvény ϕ(t)dt = 1 és a wavelet Az eltünő momentumok miatt egyrészt a h(ω) = R függvény ψ(t)dt = 0 alap tulajdonsága mellett p = ((1 + e−iω )/2) h0 (ω) = e−ipω/2 cosp (ω/2)h0 (ω), R k t ϕ(t)dt = 0, k = 1, 2, ..., p − 1 másrészt a h(ω) − 1 = és

p

R

tk ψ(t)dt = 0, k = 1, 2, ..., p − 1.

= ((1 − e−iω )/2) h1 (ω) = ip e−ipω/2 sinp (ω/2)h1 (ω)

Ezekből, ha p = 2n az y = sin2 (ω/2) helyettesitéssel, és az q1 (y) = e−inω h0 (ω) és q2 (y) = e−inω h1 (ω) Az ilyen tulajdonságu wavelet előnye ugyanis abban jelölésekkel nyerjük a áll, hogy a felbontott f (t) jelre a diadikus pontok(1 − y)n q1 (y) + (−1)n y n q2 (1 − y) = 1 ban: |aj,k − s−j/2 f (2−j k)| = O((1/2p+1 )j ), azaz az

Bezout P tipusu egyenletet, aminek a megoldása: A vázolt módszerrel adódó egyik legrövidebb, 6 n−1 n+j−1 j j y + y r(y). Ezt visszahelyet- hosszúságú filter együtthatói: q1 (y) = j=0 j testve adódik a h0 — szemben a Daubechies wavelet √ esetével — külön faktorizáció nélkül. Vagyis az orh−2 = 161√2 1 − 7 √ togonalitás az r-en múlik. Amit úgy biztosíthatunk, 1√ 7 5 + h = −1 16 2 hogy a megfelelő helyettesítés mellett az r-re mint √ h0 = 162√2 7 + 7 szabad paraméterre megoldjuk a √ h1 = 162√2 7 − 7 |h(ω)|2 + |h(ω + π)|2 = 1 √ 1√ 7 1 − h = 2 egyenletet, ami — mint láttuk — az ortogonalitás 16 2 √ 1√ ekvivalens feltétele. h3 = 16 2 −3 + 7

II.2 ortogonális Coiflet

MMIX

79

II. Konstrukciók


80

II.3 Ortogonális symmlet Ez a fajta wavelet, bizonyos értelemben egy zsákutca. Azelött konstruálta I. Daubechies, hogy észrevették volna, hogy a képfeldolgozásban oly fontos szimmetria (a h szűrő szimmetriája) milyen könnyen garantálható az ortogonalitás feladása ám a biortogonalitás megőrzése mellett. (1992,[7]) A megértéséhez annak látása szükséges, hogy a szűrő szimmetriája ekvivalens a fázisának a linearitásával. Ám mint az könnyen bizonyítható, olyan ortogonális wavelet aminek fázisa (a szűrője Fourier transzformáltjának fázisáról van szó) lineáris volna nem létezik a Haar waveletet kivéve. Emiatt a mondott szimmetricitási feltételt csak közelitően lehet kielégíteni. Így a konstrukciós feltételek a következőre módosulnak: olyan adott rendü ortogonális szűrőt keresünk aminek a fázisa minimális.

értékre szimmetrikus: h(ω) = (1 + e−iω )/2 Ha viszont átirjuk ezt a Fourier transzformáltat: a h(ω) =

e−iω/2 |h(ω)| ha 0 ≤ ω ≤ π −e−iω/2 |h(ω)| ha π ≤ ω ≤ 2π

formába. Akkor látható hogy ennek a fázisa is lineáris, csak szakaszonként: és a szakadás π-ben van, ahol a h(ω) nulla. Az is könnyen látható, hogy a A h a mérnöki gyakorlatban lineáris, ha a Fourier félszámok körül szimmetrikus filterek Fourier transztranszformáltja h(ω) = e−iℓω |h(ω)| egy ℓ ∈ Z egész- formáltja mind ilyen tulajdonságú. számra. Ez ekvivalens azzal, hogy aj = a2ℓ−j ∀j. Ha az olyan filtereket keressük, amiknek a a fenti Ám, ha ehhez a definícióhoz ragaszkodnánk, akkor általánositott értelemben közelitőleg szakaszonként a Haar filter sem lenne szimmetrikus, hiszen az az 21 lineáris a spektruma, akkor nyerjük a symmleteket.

II.4 Biortogonális spline wavelet Az itt bemutatt konstrukció I. Daubechies (ref) eredeti konstrukciójának felel meg. Azt, hogy milyenek a biortogonális waveletek már az I.3 rész (pp 18-) 3. és 4. példáin — a LeGall és a D79 wavelettel — bemutatattuk. Mindkét példa az spline biortogonális wavelet család tagja. A spline mint kiindulás azért jó, mert egy olyan feltételezés ami mellett a biortogonalitási és PR feltétel általánosan, viszonylag könnyen megoldható. Most azt mutatjuk meg, hogyan konstruálódik ennek a családnak egy tetszőleges fokszámu tagja. Természetesen vannak nem spline típusú biortogonális waveletek is. Elöbb megmutatjuk, hogy minden spline kielégit egy dilatációs egyenletet. Majd megmutatjuk, hogy a cos függvény hatványait hogyan értelmezhetjük mint dilatációs együtthatókhoz tartozó symbólumokat. Ezután megadjuk azokat a biortogonalitási és aluláteresztési tulajdonságokat amiknek kombinációja alapján I.Daubechies megkonstruálta a spline alapu biortogonális waveleteket. Majd felírjuk a mondott feltételek általános megoldásait és megmutatjuk, hogy a mondott megoldások megfelelőek. Végül pedig példát mutatunk arra, hogyan lehet egy spline alapu biortogonális wavelet esetén a rendszerII.4 Biortogonális spline wavelet

hez tartozó szűrőket közvetlenül meghatározni. A spline fogalma a waveletek esetén a lehető legszűkebb értelmezés szerint veendő: az k-ad rendü spline a független ξ1 , ξ2 + ...ξk , U[− 12 , 21 ] eloszlású változók ηk = ξ0 + ξ1 + ... + ξk összegének az sk (x) sűrüségfüggvénye. Könnyen látható, hogy k = 1-re az ηk eloszlása a [−1, 1]-en kívül nulla értékü ’háromszög’ függvény: x ∈ [−1, 0]-ra 1 + x és x ∈ [0, 1]-re 1 − x.

MMIX

81

II. Konstrukciók


82

k = 2-re három másodfokú szakaszból áll: x ∈ ahogyan azt az alábbi ábra is mutatja: [−1.5, −.5]-re 21 (x + 1.5)2 , x ∈ [−.5, .5]-re x2 + .75 és 1.0 1.0 0.8 0.8 x ∈ [.5, 1.5]-re 12 (x − 1.5)2 . k = 3-ra négy harmadfokú szakaszból áll, stb. A kapcsolódó polinom darabok érdekessége, hogy a kapcsolódási pontokon a spline eggyel kevesebb deriváltja folytonos is, mint ahányad rendü polinomok összeragasztásából az adott spline áll. Mint látható, esetünkben a spline a fokszáma által teljes egészében meghatározott. Kötött, hogy a spline az egyes szakaszokon hányadfokú, és hogy mely polinomokból áll. Általánosabb spline esetén nem megkötöttek sem a polinomok, sem a fokszám sem pedig a szakaszok. De az sem, hogy a csomópontokon a derivált hányadrendben folytonos.

0.6

0.6

0.4

0.4

0.2

0.2

0.0

0.0

0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0

0.4 0.3 0.3 0.3 0.2 0.2 0.1 0.1 0.0 -4

-3

-2

-1

0

1

2

3

4

-4

-3

-2

-1

0

1

2

3

4

A bal felső az un. box függvény, esetünkben a 0. spline. A jobb felső az 1. spline, ezt szokták háromszög függvénynek nevezni: két független U[− 21 , 12 ] eloszlású összegének a sűrüség függvénye. A bal alsó a 2. spline, azaz három független összegének sűrüség függvénye, három parabolából áll. A jobb alsó egyszerre két sürüségfüggvényt mutat. A standard p Ha nem ηk hanem ηk 12/k sűrüségfüggvényét vizs- normálisat és az előzőt úgy normálva, hogy a szórása gálnánk az k függvényében, és azt összehasonlíta- szintén 1 legyen. Megfigyelhető, hogy mennyire kicsi nánk a standard normális sűrüségfüggvényével, ak- a különbség e két sűrüségfüggvény közt... kor szépen látható volna az összeg konvergenciája,

Most persze nem erre a centrális határeloszlási tu- függvények hatványainak sorfejtéseként. lajdonságra van szükség, hanem arra, hogy minden spline kielégit egy dilatációs egyenletet. Könnyen látható, hogy ha k páros, és k/2 √ X √ k 2 Vegyük észre, hogy a k = 0-ra az sk (x) spline az k ˜ H(ω) = 2cos (ω/2) = eiℓω 2n k/2 − ℓ (1, 1) együtthatókkal érvényes ℓ=−k/2

akkor

s0 (x) = 1 · s0 (2x + 1) + 1 · s0 (2x) dilatációs egyenletet elégiti ki. k = 1-re a ( 12 , 1, 12 ) együtthatókkal a

√

√ 2 cosk (0) = 2 és √ ˜ H(π) = 2 cosk (π/2) = 0. ˜ H(0) =

1 1 k k · s1 (2x + 1) + 1 · s1 (2x + 1) + · s1 (2x − 1) Tehát ℓ = − 2 , ..., −1, 0, 1, ..., 2 -re a k + 1 tagu 2 2 √ ˜ ℓ = k2 k h k/2−ℓ 2 egyenletet. Sőt általában, ha k páros akkor páratlan hosszú szűrő szimmetrikus, aluláteresztő. P k −k k+1 s (2x + sk (x) = k+1 2 − ℓ + 1) n ℓ=0 ℓ 2

s1 (x) =

ha pedig k páratlan, akkor P −k k+1 sn (2x + sk (x) = k+1 ℓ=0 2 ℓ

k+1 2

Hasonló módon, ha k páratlan, és √ ˜ H(ω) = 2eiω/2 cosk (ω/2) =

− ℓ + 1).

(k+1)/2

Megmutatjuk, hogyan származtatható a spline függvények együtthatóinak Fourier transzformáltja a cos II.4 Biortogonális spline wavelet

MMIX

=

X

ℓ=−(k−1)/2

√ k 2 eiℓω 2n k/2 + ℓ 83

II. Konstrukciók


akkor ˜ H(0) =

√

√

2 cosk (0) = 2 és √ ˜ H(π) = 2 cosk (π/2) = 0.

Tehát ℓ = − k−1 , ..., −1, 0, ..., k+1 -re a k + 1 tagu 2 2 √ ˜ ℓ = k2 k h k/2+ℓ 2

páros hosszú szűrő szimmetrikus, aluláteresztő. A fenti két szűrő átindexelve, ℓ = 0, 1, ..., k-ra √ ˜ ℓ−k/2 = 2 k . h 2k ℓ

84

Ezek aX feltételek pedig ekvivalensek a ˜ ℓ hℓ = 1 h Xℓ ˜ ℓ hℓ+2j = 0 h ℓ

˜ szűrőnek az elöbb feltételek teljesülésével. Ha itt h bemutatott spline szűrőket vesszük, akkor az egyen˜ és a h hosszától függ. letek lineárisak és a számuk a h Ugyanakkor ezekből a feltételekből következik, hogy ˜ illetve annak adott k + 1 = N ˜ hossza meladott h, lett nem lehet a h hossza tetszőleges. Sőt az is korlátozott, hogy milyen paritású lehet a h kezdő és végindexe.

˜ Ha feltételezzük a h szűrő szimmetriáját (h-ra ez, ˜ ha h egy spline szűrő, akkor érvényes) és ha N jelöli ˜ és N paritásának meg kell Láttuk, hogy ahhoz hogy a pontos rekonstrukció és a a h hosszát, akkor az N biortogonalitás teljesüljön, elég olyan H(ω)-t találni, egyeznie. Továbbá páratlan hosszuságú filterpárok esetén a két filter kezdő indexének különböző pariamire tásunak kell lennie. Páros hosszúságu filterpároknak ˜ ˜ mindig páros indexen kell végződnie. H(ω)H(ω) + H(ω + π)H(ω + π) = 2. általános formába irható.

Könnyen látható, hogy a fenti egyenletek önmagukban nem elégségesek a h együtthatóinak a meghatározására. Ezért kiegészítjük az ismeretlen h-ra vonatkozó aluláteresztési (pontosabban felül stoppos) feltételekkel. Azaz megkövetelünk H-ra néhány további derivált π-beli 0 voltát, akkor azaz azt hogy a H ′ (π) = 0, H ′′ (π) = 0, ... egyenlőségek teljesüljenek. A mondott feltételek (szinte egyetlen) haszna, hogy olyan egyenletrendszereket ad, ami lineáris és amire a megoldás általánosan felirható. Ugyanis mint azt a I.3 fejezet (pp18-) 4. példájában láttuk, az így keletkező waveletnek igen előnytelen tulajdonsága a ˜ és a h nagyon eltérő approximációs tulajdonsága h (lásd a spektrum ábrát is!).

egyenleteknek, azaz a pontos rekonstrukció a biortogonáltás és approximációs feltételeknek eleget tesznek a következő Fourier transzformálttal rendelkező szűrők. Páros N -re: ℓ+ℓ˜ X ω √ ℓ + ℓ˜ − 1 + j N ω 2cos sin2j = H(ω) 2 j=0 2 j

Páratlan N -re: ℓ+ℓ˜ ω √ iω/2 N ω X ℓ + ℓ˜ + j sin2j = H(ω) 2e cos 2 j=0 2 j

A mondott állitás helyességéről meggyőződhetük hosszadalmas, ámde nyilvánvaló számolással. Ellenőrizni kell a fenti PR egyenlőség teljesülését, és azt hogy a megfelelő deriváltak a megfelelő helyen tényleg nullák.

Számoljuk végig a bior(4, 8) esetet! ˜ normalizálás mellett a 3. spline: Legyen a h Állitás √ ˜ az elöbbiek szerinti spline szűrő, akkor a fenti ˜ −1 , h ˜ 0, h ˜ 1, h ˜ 2 ) = 2 (1, 3, 3, 1). Ha h (h 8 II.4 Biortogonális spline wavelet

MMIX

85

II. Konstrukciók


86

Mivel ez szűrő páros hosszuságu, a hozzátartozó h- Az így nyert négy egyenlet már elégséges a h megnak is annak kell lennie és páros indexen kell vég- határozásához, ha figyelembe vesszük azt is, hogy ződnie. Jelöljék a keresett szűrő elemeit: a h szimmetrikus, azaz hogy h0 = h1 , h−1 = h2 , h−2 = h3 , h−3 = h4 . Ez utóbbit is figyelembe véve (h−3 , h−2 , h−1 , h0 , h1 , h2 , h3 , h4 ) . a négy egyenlet: A normalizálási feltétel: ˜ 1 h 1 + 2h ˜ 2 h2 2h =1 ˜h−1 h−1 + h ˜ 0 h0 + h ˜ 1 h1 + h ˜ 2 h2 = 1 . ˜h2 h4 + h ˜ 1 h3 + h ˜ 1 h2 + h ˜ 2 h1 = 0 ˜ 1 h4 + h ˜ 2 h3 h =0 A két ortogonalitási feltétel: −h1 + 3h2 − 5h3 + 7h4 =0 ˜ −1 h1 + h ˜ 0 h2 + h ˜ 1 h3 + h ˜ 2 h4 = 0 h Ennek megoldása: ˜ −1 h3 + h ˜ 0 h4 = 0 . h Ez eddig összesen három feltétel. Vegyük ehhez (h−3 , h−2 , h−1 , h0 , h1 , h2 , h3 , h√4 ) = = 642 (3, 9, 7, 45, 45, 7, 9, 3) hozzá hogy H ′ (π) = 0, azaz azt hogy a H eggyel magasabb rendben felül-stoppos legyen: Az így nyert bior(4, 8) approximációs rendje (2, 4) −3iω −2iω −iω −3ih−3 e − 2ih−2 e − ih−1 e + azaz úgyanúgy asszimetrikus, mint azt a bior(7, 9) +ih1 eiω + 2ih2 e2iω + 3h3 e3iω + 4ih4 e4iω = 0 . esetén láttuk.

III.0 Többdimenziós wavelet fajták: előszó Multiwaveletek Szeparábilis kétdimenziós wavelet Nem-szeparábilis kétdimenziós wavelet Többdimenziós wavelet családok

III.1 III.2 III.3 III.4

88. 93. 95. 97.


Az eddig vett waveletek számos tulajdonsága azon múlott, hogy R → R függvények, és hogy a dilatációs egyenletükben egy 2-es szorzó található. Így például az is, hogy a megfelelő MRA-ban a bővülő alterek differencia alterei egydimenziósak: a ϕ skála függvényből egyértelmüen meghatározható, általában ψ-vel jelölt, (részlet) waveletnek nevezett függvény eltoltjaival generálható. Az 1. pontban megmutatjuk, hogy hogyan változik a helyzet ha a dilatációs faktor 2 helyett egy m egész. Egy szürke árnyalatos 2D kép feldolgozható egydimenziós waveletekkel két lépésben úgy, hogy elöbb a kép sorait transzformáljuk majd pedig az így összeálló két, félszéles approximációs és részlet kép oszlopait. (2.pont) A módszer egy szorzattá alakítható (szeparábilis) kétdimenziós szűrőpár szerinti transzformációnak felel meg, egy többcsatornás wavelet. A wavelet fontos jellemzője a lokalitás. A szeparábilis szűrő ’nem használja ki’ az általa érintett terület adta szabadságot. Ezért tanulmányozzuk az olyan szűrőket, amik nem feltétlen szeparábilisak. (3. pont) Nem szeparabilis szűrő esetén a dilatáció (rafináció) transzformációjára általában csak az a megkötés, hogy a Z2 négyzetrácsot sajátmagába képezze, és hogy az attraktora a síkot kicserepezze. (4. pont) III.0 Többdimenziós wavelet fajták: előszó

MMIX

87

III. Többdimenzió


88

III.1 Multiwaveletek Ebben a pontban azt vizsgáljuk, mi történik hogyha a skálafüggvény ϕ(t) =

√

m

k1 X

k=k0

hk ϕ(m · t − k)

dilatációs egyenletében m = 2 helyett egy tetszőleges, m ≥ 2 egészszámot alkalmazunk. Néhány érvényes tétel felsorolásával megmutatjuk hogy azon kívül, hogy a differencia altér dimenziója 1 = 2 − 1 helyett m − 1 lesz, lényegében semmi sem változik! A tárgyalás során a vizsgálatot az R → R függvényekről kiterjesztjük az R → Rr leképezésekre. Ennek megfelelően a vizsgált skála függvények általában ϕ(t) = (ϕ1 (t), ..., ϕr (t))′ formájuak, azaz r multiplicitásuak lesznek, és a hk dilatációs (rafinációs) együtthatók pedig r × r méretü mátrixok.

és, hasonló módon egy (ϕ, ˜ ϕ) függvénypárt biortogonálisnak nevezünk ha érvényes, hogy Z

ϕ(t ˜ − j), ϕ(t − ℓ) = ϕ(t ˜ − j)ϕ′ (t − ℓ)dt = δj,ℓ I,

ahol az I most egy r×r identitás. A rafinációs egyenlet együtthatóinak symbóluma egy trigonometrikus Egy ϕ(t) skálafüggvényt ortogonálisnak nevezünk, mátrix polinom: ha minden k egészre érvényes, hogy k1 Z 1 X

hk e−jkω . H(ω) = √ ϕ(t), ϕ(t − k) = ϕ(t)ϕ′ (t − k)dt = δk I, m k=k0

egyenlet jelenti, a biortogonalitást pedig a: Az ortogonalitás a rafinációs mátrixokkal kifejezve, minden ℓ egészszámra a X hk h′k−mℓ = δℓ I

m−1 X

˜ + 2πn )H ′ (ω + 2πn ) = I. H(ω m m n=0

√ Példa egy ilyen függvényre a ϕ(t) = (1 3(2t − 1))′ egyenletek teljesülését jelenti, a biortogonalitást pe- úgy véve, hogy a [0, 1]-n kívüli t értékekre ϕ(t) = dig a: X (0, 0)′ legyen. Könnyen látható, hogy ez a függvény ˜ k h′ h = δ I ℓ k−mℓ kielégíti a dilatációs egyenletet r = 2-re a k

k

egyenletek.

1 h0 = √ 2 2

2 √

0 − 3 1

1 h1 = √ 2 2

√2 0 3 1

Mint látható, ezek az egyenletek — m = 2-re — teljes egészében megegyeznek a korábban bemutatott, együtthatókkal, m = 2-re, k0 = 0, k1 = 1 mellett. egydimenziós esetre vonatkozó (bi)ortogonalitási feltételekkel. A DGHM waveletet, azaz a Donovan-GeronimoHardin-Massopust féle waveletet tekintik a legegyAz ortogonalitást a symbólumokkal, szintén az m = szerübb, nem nyilvánvaló r = 2 multiplicitásu or2 esethez hasonló módon, tetszőleges m ≥ 2 -re a togonális wavelet példának. Ennek a ϕ függvénye explicit nem adható meg. Ortogonálitása például az m−1 X 2πn 2 együtthatói alapján látható be. |H(ω + )| = I m n=0 III.1 Multiwaveletek

MMIX

89

III. Többdimenzió


A DGHM wavelet rafinációs egyenletének nem-nulla együtthatói a (h0 , h1 , h2 , h3 ), ezek rendre: √ 1 1 12 0 12 16 2 √ √ √ √ 20 2 − 2 −6 20 2 9 2 20 1 1 0 0 0 0 √ √ √ √ . 20 2 9 2 −6 20 2 − 2 0

90

akkor a ϕ(n) (t) konvergál a megoldáshoz. Láttuk, hogy m = 2 esetén a skálafüggvény tartóját a a nem-nulla együtthatók száma meghatározza. Tetszőleges m-re csak valamivel kevesebb igaz: supp ϕ ⊂ [k0 /m − 1, k1 /m − 1].

Ugyanakkor tetszőleges rafinációs egyenlet megolA ϕ(t) stabil, ha van olyan véges 0 < α < β konsdásának ϕ(t) ˆ Fourier transzformáltja felirható az tans, amikre tetszőleges ck mellett: együtthatók H(ω) symbólumával a X X X ! ∞ α ||ck ||2 < || ck ϕ(t − k)|| < β ||ck ||2 . Y −k ϕ(t) ˆ = H(m ω) ϕ(0) ˆ k k k k=1

aszimptotikus kifejezés formájában, szintúgy mint az egydimenziós esetben. És a cascade algoritmus is működik: egy ϕ(0) (t) kezdőfüggvénnyel, ha ϕ

(n)

(t) =

√

m

k1 X

k=k0

hk ϕ(n−1) (m · t − k)

A kompakt tartóju ϕ(t) linearisan független, ha X k

ck ϕ(t − k) = 0

csak ha ck = 0, minden k-ra.

E fogalmak alapján megadhatóak az alapvető regularitási feltételek, amik az olyan ϕ(t) skálafüggvényekre érvényesek, amik L2 -beliek, stabil és lineárisan független eltolásokkal: - az együtthatók H(ω) mátrixa 0-ban olyan, hogy a legnagyobb sajátértéke egyszeres és az értéke 1 - van olyan y együttható vektor, amire egy nem-nulla c előáll a X c= y ′ ϕ(x − k) k

formában; - és ugyanez az y olyan, hogy: y ′ δk = y ′ H( és

2πk ) m

ugyanazt az alteret, ha vannak olyan Ak együtthatók, és amiknek symbóluma paraunitér, és amikre X ϕ2 (t) = Ak ϕ1 (t − k). k

MRA-nak nevezzük az L2 egy olyan altérsorozatát ami kétirányban végtelen, egymásba ágyazott azaz S V = · · · T⊂ Vj ⊂ Vj+1 ⊂ · · · , és amire: Vj sűrü L2 -ben; Vj = 0; f (t) ∈ Vj ⇔ f (t + k/mj ) ∈ Vj ; f (t) ∈ Vj ⇔ f (mt) ∈ Vj+1 ; és amihez létezik olyan ϕ(t) amire a ϕ(t − k), k ∈ Z függvények a V0 stabil bázisa.

Belátható, hogy a fenti esetben a V differencia altereit — azaz a · · · , W−1 , W0 , W1 , · · · -t — generálja Hmℓ+k y egy olyan ψ (s) , s = 1, ..., m − 1 függvényrendszer, ℓ ami által generált altér merőleges a megfelelő V alterekre, és amik a ϕ függvényből a Egy A(ω) trigonometrikus mátrix polinom para√ X (s) unitér, ha A(ω)A′ (ω) = I. Két ϕ1 (t), ϕ2 (t) orthogoψ (s) (t) = m gk ϕ(mt − k) nális kompakt tartóju skálafüggvény akkor fesziti ki k ′

X

III.1 Multiwaveletek

1 = √ y′. m

MMIX

91

III. Többdimenzió


92

módon az előbbi értelmezés szerint egyértelmüen nulla voltát jeltentette. Ugyanez a többdimenziós meghatározott együtthatókkal kifejezetők. esetben lényegesen bonyolultabb! Most a p-ed rendü összegfeltétel, ugyanarra az y-ra A multiwaveletekre vonatkozó Strang-Fix tétel sze- ami a regularitási feltételnél szerepelt, s = 0, ..., m − rint a p-ed rendü approximáció, a p-ed rendü pon- 1 mellett a: n tosság, a p-ed rendü összegszabály és a symbólum X 2πs n ′ (1 − δp )ys = mt (−i)n−t yt′ Dn−t H( ) megfelelő rendü deriváltjának nulla volta ekvivalens t m t=0 feltételek. A kapcsolatos fogalmak csak részben nyilvánvaló általánosításai az egydimenziós wavelekre egyenlőség eljesülése n = 0, ..., p − 1-re. vonatkozó fogalmaknak. Az approximációs fok és a pontosság az egydimenÉrdekes különbség, hogy a multiwaveletek diszkrét ziós analógia szerint definiálható. Ha Pj az MRA j. és folytonos momentumok — bár egy-egy értelmü tagjára, a Vj -re való vetítést jelöli akkor, azt mondkapcsolat áll fenn köztük — most formájukban is juk, hogy az approximációs fok p, ha eltérők. A k. diszkrét momentum egy mátrix: ||f (x) − Pj f (x)|| = O((1/mp )j ). 1 X n √ ℓ hℓ A pontosság pedig akkor p, ha van olyan cjk amire m ℓ X j x = cjk ϕ(x − k), A folytonos k. momentum egy vektor: Z k xk ϕ(t)dt azaz, ha az xj hatványfüggvény j = 0, 1, ..., p − 1-re előállítható mint a skálafüggvény eltoltjainak lineáris Az összegszabály az egydimenziós esetben lényegékombinációja. ben egy alternáló előjelekkel számolt momentum

III.2 Szeparábilis kétdimenziós wavelet A többdimenziós szürkeárnyalatos kép tekinthető mint egy R2 → R függvény. Az R2 → R függvények terében is értelmezhetők átlatános értelemben vett waveletek azon feltételek analógjai alapján, amiket az egydimenziós esetben láttunk.

- az oszloponként nyert transzformáltakat egymás mellé irva egy olyan képet kapunk, amiben 4 darab félszéles és félmagas kép látható! - a bal felső az ami az approximásiós sorok approximációs oszlopai – a jobb alsó pedig az ami a részlet Ha azonban meg akarjuk takaritani a konstrukcióval sorok részlet oszlopai járó bonyodalmakat, akkor vehető az alábbi általános algoritmus: - vegyük a kép vizszintes sorainak mint megfigyelés- Az így nyert transzformációra a következők igazak: soroknak a wavelet transzformáltját - ugyanezt az eredményt nyerjük, ha elöbb az oszlo- az egy-egy sorra nyert approximációs és részlet kö- pokat, utóbb pedig a sorokat transzformáljuk. zelítéseket irjuk egymás után, és az egyes sorok így - az eredmény megfelel annak, ha az eredeti képet vett transzformáltjait irjuk egymás alá azoknak a szűrőknek a direkt szorzatával konvol- így két képrészt kapunk: az előzőhöz viszonyítva váljuk, amikkel a megfelelő approximációt illetve félszéles approximációs és félszéles részlet képet részletet nyerhetjük. - a két félszéles kép minden oszlopának, mint meg- - az eredmény tulajdonképpen egy multiwavelet figyeléssornak vegyük a wavelet transzformáltját, és m = 4 dilatációs faktorral: az approximáció a bal irjuk az approximációs és részlet közelítést egymás felső sarok, és a négy részlet a jobb-felső, bal-alsó és alá a jobb-alsó! III.2 Szeparábilis kétdimenziós wavelet

MMIX

93

III. Többdimenzió


94

konstruálható divergenciamentes wavelet. A vázolt úton könnyen nyerünk olyan waveleteket, amikkel a képek feldolgozhatóak. E módszer szá- Ez utóbbi állitás a klasszikus formájában Lemariémos előnye és hátránya közül kiemelendő: gyorsan Rieusset-től származik (1994): számolható; a szorzat-forma miatt nem használja ki a lokalitás összes lehetőségét; ezen a módon nem A mondott negatív állitás azért érdekes, mert

III.3 Nem-szeparábilis kétdimenziós wavelet Ebben a pontban egy igen-egyszerü konstrukcióval, a lifting technikát felhasználva mutatunk példát arra, hogy hogyan alkotható nem-szeparábilis kétdimenziós wavelet. Egy konkrét wavelet konstrukciót mutatunk be. A módszer red-black és quincunx néven is ismert.

A quinqunx a régi római öt unciás neve. A súlyát egy olyan veretrész is jelezte, amin öt pont ugyanúgy helyezkedik el mint az ötös a mostanában használaA red-black elnevezés azt mutatja, hogy a sík cse- tos dominón, vagy a kockán. repezése e wavelet esetén a sakktáblának felel meg. Ugyanis e wavelet dilatációs mértéke m = 2, és a két A red-black//quinqunx wavelet transzformáció komponens esetén a ritkítás olyan mintha a rácssze- ugyanis a következő, lifting módszerrel meghatárüen elhelyezkedő közelítési pontokat egy sakktáb- rozva: lának megfelelően módon kiszineznénk és azután az = legyen az első lépés egy lazy, azaz lusta wavelet egyik komponens esetén csak a vörös, a másik esetén transzformáció: tekintsük a kép approximációjának meg csak a fekete pontokat tartanánk meg. azokat a pontokat, amik a sakktábla szerint vörösek, és részleteknek pedig azokat, amik feketék. A quinqunx elnevezés azt irja le, hogy a konsruk- = a predict fázisban az eddig nyert approximáció ció lifting pedikciós és korrekciós lépéseiben hogyan alapján javítjuk a becslésünket arra nézve, hogy viszonyulnak egymáshoz az aktuális rácson a módo- mennyi lehet a függvény detail (részlet) közelitése, méghozzá úgy hogy ehhez a pont rács szerinti négy sítot és a módosító értékek helyei. III.3 Nem-szeparábilis kétdimenziós wavelet

MMIX

95

III. Többdimenzió


szomszéd pontbeli approximáció értéket használjuk fel. = az upgrade fázisban, az approximáció komponens módosításával helyreállitjuk a két komponens ortogonalitását, méghozzá a pont 4 közvetlen szomszédja beli — a predict fázisban már módosult — detail értékeket felhasználva. A predikt és az upgrade függvények a következők A predikt: 1 dj,ℓ = dj,ℓ − (aj−1,ℓ + aj+1,ℓ + aj,ℓ−1 + aj,ℓ+1 ) 4 Az upgrade: 1 aj,ℓ = aj,ℓ + (dj−1,ℓ + dj+1,ℓ + dj,ℓ−1 + dj,ℓ+1 ) 8 A red-black módszer érdekessége, hogyha egy képre a megfelelő felbontást ismételten alkalmazzuk, akkor az egymásutáni felbontásokban kezelt pontok —

96

mármint azok a pontok amikhez az egyes lépésekben figyelembe vett közelítési pontok tartoznak — olyan négyzetrácsokat alkotnak, amik az egyes lépésekben egymázhoz viszonyítva 45o -kal elforgatottak. Amikor a második lépésben, a kapott approximációhoz egy durvább approximációt akarunk illeszteni, leválasztva az egy lépéssel durvább részleteket, akkor a két komponens pontjai már ujra egy olyan rácsszerkezetben lesznek, ami az eredeti rácsszerkezettel párhuzamos! Így a köztes lépés approximációs és részlet waveletének rácsa 45o -kal elforgatott. A red-black wavelet esetén olymódon csökken a pontok száma negyedére, hogy közben két részlet wavelet közelités keletkezik. Ha ugyanezt egy szeparábilis wavelettel tettük volna, akkor a keletkező részletek száma 3 lett volna!

III.4 Többdimenziós wavelet konstrukciók Az előző pontokban példát láttunk arra hogy egy wavelet esetén, megváltoztatva a dilatációs arányt (a tetszőleges) és megváltoztatva az R2 kicserepezését, hogyan nyerhetünk képfeldolgozásra alkalmas többdimenziós waveleteket. Most megmutatjuk, hogy igen általános, az A rafinácós mátrixra és a tér kicserepezésére tett feltételek mellett, a létrejövő wavelet rendszerek matamatikai értelemben ugyanúgy kezelhetőek, mint az első részben tárgyalt egydimenziós-dilatációs waveletek. +–

III.4 Többdimenziós wavelet konstrukciók

MMIX

97

IV. Általánosítások


98

IV.0 Általánosítások: előszó Ridgelet IV.1 99. oldal Curvelet IV.2 100. oldal Az első részben láttuk (és ez spekulatív módon is nyilvánvaló), hogy a függvények igen széles osztálya alkalmas arra, hogy a dilatált eltolt verzióinak lineáris kombinációja lényegében tetszőleges függvényt előállitson. A kérdés valójában csak a hatékonyság. Az, hogy tudjuk-e a közelitett függvényben rejlő információt viszonylag kevés változóba sűriteni. Pontosabban, tudunk-e olyan információ sűritést előállitani ami a tipikus képek esetén a feldolgozás szempontjából fontos információkat a lényegtelenektől elkülönítve reprezentálja. Az információ sürítés egyfajta mértéke volt, hogy a kép L2 normája hogyan oszlott el a transzformációval nyert együtthatók közt. Egyáltalán, hogy egyenlő volt-e a két norma. Ennek egyfajta mértéke a frame tulajdonság, pontosabban az, hogy egy bázis vékony-e. Azaz hogy a bázis legjobban csökkenő és a legjobban növekvő normáju eleme esetén a növekedés és a csökkenés mértéke egymáshoz viszonyítva nem túl nagy. Ortogonális waveletek esetén ez az arány 1. Ez biztosítja, hogy nem jön létre túl sok, lényeges információt hordozó együttható. Ugyanakkor a lényeg abszolút értelemben vett sűritésének igénye mellett, fontos szempont a keresett részletek kiemelésének szükségessége. És az utóbbi teszi indokolttá egy-egy olyan frame alkalmazását is, ami bár redundáns, mégis nagyon jó, mert azt a részletet emelik ki, amit keresünk.

IV.1 Ridgelet A ridgelet elvileg és technikailag is a legegyszerübb, legkézenfekvőbb modellezése annak, hogy a digitális képek jelentős részén az információ nagyjából egyenes vonalakból áll. Illetve annak, hogy a képeken az információt jelentő különböző texturákat nagyjából egyenes vonalak választják el egymástól. Értelmezés Ridgeletnek (szószerint: hátság, tetőgerinc, taréj, én a képszerü egyértelmübbség okán ráncnak nevezem) az olyan kétváltozós függvényeket nevezzük, amik valójában csak az egyik változójuktól függnek, és e

IV.1 Ridgelet

változójuk szerint waveletelek. Azaz wavelet skála függvény az a ϕ(x, y) amire ϕ(x, 0) egy egydimenziós wavelet skála függvény, és amire tetszőleges y, mellett ϕ(x, y) = ϕ(x, 0).

MMIX

99

IV. Általánosítások


100

IV.2 Curvelet A ridgeleteknél láttuk, a képek olyan kétváltozós függvények szerinti sorfejtését, amik dilatáltjai, elforgatottjai és eltoltjai egy olyan függvénynek, ami az egyik változója mentén konstans, a másik változója mentén pedig egy (egydimenziós) wavelet. A képek ridgelet felbontása szerencsés matematikai konstrukciók nyomán technikailag rendkívül hatékony. Azáltal, hogy egy-egy ridzsben De mint képmodell kiegészitések nélkül csak speciális szinterek és texturák esetén kielégítő, hiszen a képeken megjelenő vonalak sok esetben erősen görbülnek, és az egyenes voltuk erősen lokális. A curvelet olyan speciális wavelet, ami szemben a ridgeletekkel nem konstans az egyik irányban, hanem minden irányban korlátos tartóju. ++–

V.0 A wavelet statisztikai alkalmazása: előszó Idősorok wavelet spektruma Idősorok zajszűrése Képek wavelet felbontása Élek és textúrák detektálása

V.1 V.2 V.3 V.4

102. 103. 105. 107.


V.0 A wavelet statisztikai alkalmazása: előszó

MMIX

101

V. Statisztika V.1 Idősor wavelet spektrum


102

V.2 Idősor zajszürés A küszöbölésnek két módszere ismert: a kemény és a lágy. Mindkét módszer első lépése egy megfelelő küszöbérték meghatározása. Ha rendelkezésre áll a megfelelő s küszöb meghatározása után megváltoztatjuk az összes wavelet együtthatót annak megfelelően, hogy a kemény vagy lágy küszöbölést választottuk.

Lényeges különbség az egyszerübb kemény-módszer rovására, hogy a lágy módszer együttható transzformáló függvénye folytonos. Ha a kemény módszert alkalmazzuk, akkor a függvény előállításában ténylegesen alkalmazott skála és wavelet függvények együtthatói közt nem lesz olyan, aminek az együtthatója küszöb alatti. Azaz nem lesznek ’kis súlyu’ komponensek.

A kemény módszer szerint minden olyan együtthatót nullának veszünk, aminek az értéke abszolutértékben küszöb alatti.

Kemény

Lágy 6

6 b

A lágy módszer szerint minden olyan együtthatót nullának veszünk, aminek az értéke abszolutértékben küszöb alatti és azoknak az együtthatóknak az abszolutértékéből, amiknek az abszolutértéke a küszöb felett van, kivonjuk a küszöbértéket. V.2 Idősor zajszürés

MMIX

r

r -

r

r -

-s 0

s

-s 0

s

b

103

V. Statisztika


A küszöbérték meghatározására négy fontosabb - az előző kettő bizonyos keveréke módszer említendő: - minimax elven meghatározott - a James-Stein féle zsugoritásos - a fix, megfigyelés hossz függő

104

V.3 Képek wavelet felbontása Képek wavelet transzformálása esetén, legszokásosabb egy szeparábilis wavelet alkalmazása. Amennyiben szeparábilis wavelettet alkalmazunk, lehetséges egy kép transzformáltját úgy előállitani, hogy elöbb például a sorokat bontjuk fel approximációs és részlet komponensre, így egy ’fél széles’ approximációs és részlet képet nyerve. Utóbb pedig külön-külön transzformálva a két képet a képek oszlopainak vesszük a wavelet felbontását. Négy — A, H, V és D, — negyed méretü képet nyerve, a képek elnevezése során azt véve figyelembe, hogy milyen irányú felbontáskor tartozott az approximációs részhez: - az A approximáció, ami az approximáció a sorfelbontáskor nyert approximációból A H - a H horizontális rész, ami a részlet a sorfelbontáskor nyert approximációból - a V vertikális rész, ami az approximáció a sorfelbontáskor nyert részletekből V D - a D részletek, ami a részlet a sorfelbontáskor nyert részletekből Többszintü felbontás esetén, a már felbontott képet dolgozzuk fel, úgy mintha az eredeti kép a bal-felső negyedbeli approximáció lenne. A felbontást mindaddig folytatható, míg a keletkező approximáció elég nagy ahhoz, hogy — figyelembe véve a széle hatásokat — mint az eredeti kép approximációja értelmezhető legyen. Megjegyzendő, hogy a sor-oszlop felbontás sorrendje anélkül felcserélhető, hogy az eredményképek változnának hiszen a kép egy wavelet szerinti felbontása — a lényegét tekintve — egy speciális líneáris szűrés.

V.3 Képek wavelet felbontása

MMIX

105

V. Statisztika


Kép transzformáció Haar módszerrel

106

a V eleme:

Vi,j = (ai,j + bi,j − ci,j − di,j )/4, Alacsony műveletigénye, könnyü programozhatósága miatt lassú konvergenciája ellenére gyakran alkala D elemei: mazzák a Haar wavelet kétdimenziós szorzatát képek transzformálására. Di,j = (ai,j − bi,j − ci,j + di,j )/4. A kétdimenziós Haar transzformált esetében a két Az inverz transzformáláskor a 2x2-es elemek közül irányu transzformáció szorzataként kapott transz- az i. sor j. bal felső sarka (ez volt ai,j ): formáció a következő módon irható le: (Ai,j + Hi,j + Vi,j + Di,j )/4. - bontsuk az eredeti képet 2x2-es négyzetekre! Mit látható ez a transzformáció visszaadja a bal felső - legyenek az i. sor j. négyzetének elemei: sarkok értékét. Hasonlóan a jobb-felső sarok: ai,j bi,j ci,j di,j - a transzformált mátrix előző jelölések szerinti A részének i. sor j. eleme: Ai,j = (ai,j + bi,j + ci,j + di,j )/4,

a H megfelelő eleme:

Hi,j = (ai,j − bi,j + ci,j − di,j )/4,

(Ai,j − Hi,j + Vi,j − Di,j )/4. A bal alsó sarok: (Ai,j + Hi,j − Vi,j − Di,j )/4. És a jobb alsó sarok: (Ai,j − Hi,j − Vi,j + Di,j )/4.

V.4 Élek és textúrák detektálása

V.4 Élek és textúrák detektálása

MMIX

107

A. Alkalmazás


108

A.0 A waveletek alkalmazásai: előszó Idősor elemzés A.1 Képtranszformálás A.2 A JPEG és a JPEG2000 szabványok A.3

109. oldal 110. oldal 111. oldal

Ebben a részben három, a waveletek alkalmazási szempontjából fontos területét mutatjuk be. Az idősor elemzést, ahol a wavelet sorfejtés alapvetően zajszűrési és változás detektálási célokat szolgálhat. Megmutatjuk, hogy a képelemzések esetén egy-egy speciális wavelet transzformáció olyan képet eredményezhet, amiben a keresett struktúrák kiemelődnek. A harmadik téma a JPEG2000 szabvány ami egy olyan speciális terület, ahol a wavelet mint felhasznált eszköz, akár a mindennapi életünkben is megjelenhet.

A.1 Idősor elemzés

A.1 Idősor elemzés

MMIX

109

A. Alkalmazás A.2 Kép transzformálás


110

A.3 A JPEG és a JPEG2000 szabványok A 80-as években alakult ’Joint Photographic Experts Group’ nevü csoport munkájának eredménye a JPEG néven ismert az 1992-ben közzétett ISO 10918 digitális képtárolási szabvány. A szabvány olyan sikeres, hogy mostanság is ebben a formátumban tárolják a digitális képek jelentős hányadát. Pedig közismert, hogy ez a tárolási mód nem adja vissza változatlanul az eltárolt képeket! Ráadásul ugyanennek a szakértői csoportnak időközben létrejött egy ujabb, olyan ajánlata is ami hatékonyabb és rugalmasabb és aminek van olyan változata, ami szükség esetén információvesztés nélküli. Ez a módszer JPEG2000 néven vált ismertté, mert 2000-ben publikálták. A hivatalos neve ISO 15444. A továbbiakban ennek a két — a JPEG és a JPEG2000 — szabványnak a rövid leírása következik. A JPEG szabvány elöbb a kép Fourier transzformáltját veszi majd a transzformált egy szokványos módszerrel tömörített változatát tárolja. JPEG2000ben — ugyanilyen rövidséggel — csak az az ujdonság, hogy a Fourier transzformáció helyett wavelet transzformáció is alkalmazható.

- A LeGall 5/3 algoritmust kerekítéssel olyanná tették, hogy a véges ábrzolási pontosság mellett a hibamentesség nem okoz redundanciát. - A Cohen-Daubechies-Feauveau féle 9/7 algoritmus a (7, 9)-es biortogonális spline filter totális áttervezésével adódott. Itt az volt a probléma, hogy a ’klasszikus’ 9/7 esetében az analízis és a szintézis skála függvény közelítő képessége jelentősen eltér A JPEG2000-ben két wavelet módszer lehetséges. (6, 2). Ezzel szemben az új CDF97 két skálafüggvéMindkettő a klasszikus biortogonális spline filter nyének közelítő képessége kiegyenlített: (4, 4). család egy-egy tagjának egy-egy variánsa. A.3 A JPEG és a JPEG2000

MMIX

111

A. Alkalmazás


A JPEG szabvány esetén az vezet a kép romlásához, hogy a képet hatékonyan akarjuk tárolni. Emiatt nem a kép pontjainak egy vagy több dimenziós egészszám vektorokból álló szinkódjait tároljuk, hanem a szinkódmátrixok Fourier transzformáltját, azaz bizonyos sin-cos függvény együtthatókat. Ez azért probléma, mert technikailag nincs lehetőség arra, hogy ezeket az együtthatókat minden esetben teljes pontossággal eltároljuk. És elvileg is kizárt, hogy amikor a képpontok szinét újra kiszámoljuk a tárolt együtthatókból, akkor a megfelelő sin-cos függvények értékeit teljes pontossággal megadjuk. Azaz ha a JPEG algoritmusát alkalmazzuk, akkor feltétlen kerekíteni kell. A kerekítés szükségességét elvileg a wavelet transzformáció sem törli el. Ha egy wavelet alapalgoritmust kerekítéssel egészítünk ki, akkor egy olyan transzformációpár is veszteségessé válhat ami eredetileg nem az. Ha viszont egy racionális együtthatós wavelet transzformáció lifting lépéseit kerekítjük, ak-

112

kor már invertálható egész variánst nyerünk. Igaz, hogy közben a kerekítés miatt veszítünk az ortogonalitásból illetve a biortogonalitásból és ez rontja a közelítések hatásfokát. A JPEG2000 a LeGall53 alkalmazása mellett azért veszteségmentes, mert a szabvány az alapeljárás egy olyan kerekítéssel kiegészített változatát alkalmazza, ami mellett az veszteségmentes (az analízis: azaz az approximációs és részlet együthatók kiszámítása, és a szintézis: az együtthatókból az eredeti megfigyelt érékek kiszámítása a skála és wavelet függvények segítségével, egymás inverze) marad, miközben olyanná válik, hogy egész számokat egészekbe képez. Ráadásul úgy, hogy az eljárás konstansai is egészszámok. Ha a JPEG2000-en belül a CDF97 transzformációt alkalmazzuk, akkor a JPEG2000 tárolási eljárás is veszteséges, és ennek a módszernek nincs is ’egész’ változata. Mégis van értelme ezt az algoritmust venni, ha helytakarékos jóminőségü tárolást aka-

runk. Kevésbé teszi szellemképessé a tárolt képet mint a sin-cos rendszer. Adott hibahatár mellett a tárolt kép kisebb. Ugyanis az élekkel tagolt – helyileg sima képekhez a wavelet-sor lokálisan és globálisan is gyorsabban konvergál mint a Fourier.

lehet. Egy valós kép egy-egy pontjának szinkódja az utóbbi rendszer szerint általában egyenletesebb eloszlásu a lehetséges kódok terében. Ez javíthat a tárolás elött alkalmazott tömörítő algoritmus hatékonyságán. Az általános tömörítő algoritmusok ugyanis olyanok, hogy nagyobb a hatásfokuk, ha a A CDF97 azért tárhatékonyabb a LeGall-nál mert tömörítendő egyenletesebb eloszlásu. megtartva a waveletekre jellemző lokalitást, a függvényei simábbak. Ugyanakkor a nagyobb simaság a A JPEG és a JPEG2000 a tömörítés elött nem ilyen lokalitás romlását jelenti és a szűrők nagyobb szé- egyszerü szinkód konverziót alkalmaz, hanem wavlessége bizonyos lassulást okoz. Ám a tapasztalatok elet sorbafejti a képet. Így a transzformáció után és az elemzések azt mutatják, hogy a gyorsaság és nem szinkódokat, hanem a sorfejtések együtthatóit pontosság ellentmondó igényei közt a CDF97 jó komp- kell kezelni. Ez azért hasznos, mert a sorfejtés esetromisszum. leges csonkítása — a kis súlyu tagok elhagyása — Az egyszerübb képtárolási módszerek a kép pontjainak szinkódjaiból képzett állományt tárolják tömörítve. Ezeknél az eljárásoknál is szokásos, a tömörítés elött egy transzformációt venni: áttérnek az RGB tárolásról az YCbCr rendszerre. Ez egy egy-egyértelmü megfeleltetés két lehetséges szinkódrendszer közt. Az áttérés ennek ellenére hasznos A.3 A JPEG és a JPEG2000

könnyen szabályozható mértékü közelítést és tárigény csökkentést jelent. Ugyanakkor remélhető az is, hogy a sorfejtés megmaradó együtthatói a lehetséges együtthatók terében egyenletesebben oszlanak el mint az eredeti szinkódok. Továbbá a sorfejtéses transzformáció azért is jobb mint az egyszerü szinkód transzformáció, mert topológikus. A képet nem pontonként kódolja újra hanem egészében, a szom-

MMIX

113

A. Alkalmazás


szédosságot is figyelembe véve.

˜ H(z) =

2−5

64 −6+ρ 5ρ

114 z 2 (1 + z −1 )4

+ 2) (z 2 + z −2 − (8 − ρ)(z + z −1 ) + 128 5ρ −3 A LeGall53 kerekítéssel való kiegészítése 2 z 2 (1 + z −1 )4 (−z − z −1 + ρ) H(z) = ρ−2 Ezt kifejtve a szűrők együtthatói (közelítően): A módszer részletes leirása az I.8 (62-) pontban ta˜ = (−...., .6029, .2669, −.0782, −.0169, .0267) h lálható h = (−...., 1.1151, −.5913, −.0575, .0913) A CDF97 rendszer approximációs (balra) és részlet A CDF97 konstrukciója (jobbra) függvényei úgy, hogy a felső sorban az analizis függvények és az alsóban pedig a szintézis függA CDF97 szűrőt úgy nyerjük, hogy a (9, 7) szűrő- vények láthatóak. 2.0 2.0 hosszuság mellett figyelembe vesszük a biortogonali1.5 1.5 1.0 1.0 tás ’természetes’ feltétele mellett azt is, hogy a két 0.5 0.5 appoximációs szűrő — az analízis és szintézis során 0.0 0.0 -0.5 -0.5 használt — kiegyensúlyozottabban legyen alul át – -1.0 -1.0 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 felül stoppos tulajdonságu. 2.0 2.0 1.5 1.5 Legyen ρ a 128 − 116x + 40x2 − 5x3 = 0 egyenlet 1.0 1.0 egyetlen valós gyöke, azaz 0.5 0.5 8 2 + 3 3

r 3

q q √ √ 7 3 3 ( 10 + 3 15 + 10 − 3 15). 25

Ekkor a két szűrő Fourier transzformáltja:

0.0 -0.5 -1.0

0.0 -0.5 -1.0 0 1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

A Fourier transzformáltakon megfigyelhetjük, hogy a skála függvények analizis és szintézis szűrője az ω = π érték mellett jól simulnak a 0 értékhez.

sq 2

sq 2

1

1

.5

.5

felül-stop’ feltételpárt mint a klasszikus 7/9-es biortogonális pár (lásd I.3 pp18- ). De ez nem is véletlen, hiszen úgy konstruáltuk, hogy mindkét waveletének a pontossága 4 legyen: azaz hogy a hiba nélkül közelített polinomok fokszáma legalább 3. legyen.

A Strang-Fix feltétel szerint azt is jeleti, hogy a módszer approximációs rendje (4, 4), szemben a D79-el Azaz, hogy valóban jobban teljesíti a ’alul-át és amire ez a fokszám 2 illetve 6 volt. 0

0

0

pi/2

pi

A.3 A JPEG és a JPEG2000

0

pi/2

pi

MMIX

115

B. Bibliográfia


B.0 Bibliográfia: előszó Könyvek B.1 Cikkek B.2 Programok B.3

117. oldal 118. oldal 121. oldal

Sokféle sok hiba vagyes terminológia ellentmondó jelölésrendszer.

116

B.1 Könyvek [..] G. Strang, T. Nguyen: Wavelets and Filter banks, (1996) Wellesley Cambridge Press. [..] A. Bultheel: Wavelets with applications in signal and image processing, (2006) Katholieke Universiteit Leuven.

B.1 Könyvek

MMIX

117

B. Bibliográfia B.2 Cikkek


118

Bibliography [1] T.Lin, Sh.Xu, Q.Shi, P.Hao: An algebraic construction of orthonormal M-band wavelets with perfect reconstruction, Appl. Math. and Comp. (2006) pp717-730. [2] W.Sweldens: The lifting scheme, a 5 minite tour Z. Angew. Math. Mech. (1996), Suppl pp42-44. [3] G.Strang: Eigenvalues of ↓ H and convergence of the cascade algorithm, (1996), IEEE Trans SP ppA Fourier analaysis of the finite element variational method, Construct. Aspects of Funct. Anal. (1971) pp796-830. [4] G.Strang, G.Fix: A Fourier analaysis of the finite element variational method, Construct. Aspects of Funct. Anal. (1971) pp796-830. [5] F.Chaplais: The Strang and Fix Conditions, Manuscript 1999. 119

B. Bibliográfia


120

[6] S.G.Mallat: A theory for multiresolution signal decomposition: the wavelet representation, IEEE Tr. on PMI (1989) pp674-693. [7] I. Daubechies: Ten Lectures on Wavelets, (1992) Society for Industrial and Applied Mathematics.

BIBLIOGRAPHY

BIBLIOGRAPHY

B.3 Programok Ugylátszik, hogy egy-egy ujabb eljárás megtalálásakor kevéssé érdemes az eljárást már létező, bővíthető programokhoz illeszteni. Emiatt több esetben egy-egy eljárást, csak egy teljesen önálló program formájában tudjuk elérni. Mentheti a helyzetet, hogy egyfelől nehéz, egy működő rendszer logikáját kiismerni, és ez mindenképpen egyfajta bizonytalansági korlátot visz egy uj eljárás esetleges implementációjába. Másfelől bizony egy-egy ujabb eljárás néha olyannyira műveletigényes, hogy speciális, az adott eljáráshoz illeszkedő adatstruktúra híján gyakorlatilag használhatatlanul lassú. Két programcsomag wavelet rutinjait mutatom be. A jogdijakkal védett MATLAB-ét és a GNU licenc szerint szerkesztett R programét. A két programról, a http protokol szerint elérhető www.r-project.org www.mathworks.com lapokon lehetséges. A programok felhasználásával kapcsolatos feltételekről tájékozódni a www.R-project.org/licenses/ www.mathworks.com/license.txt lapokon. Minden Tisztelt Olvasó figyelmét ezúton is felhívom a jogkövető magatartásra! B.3 Programok

MMIX

121

B. Bibliográfia


122

[..] R Development Core Team (2009). R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN 3-900051-07-0, URL http://www.R-project.org. A két program logikai rendszere hasonló. Első közelítésben mindkettő egy interpreter típusú nyelv, amihez fejlett grafikus script szerkesztő tartozik. A mag része egy olyan fogalom rendszer illetve program ami az alapvető algebrai műveletek végrehajtására is alkalmas. Viszonylag könnyen programozható benne jószerivel tetszőleges matematikailag pontosan leírt algoritmus. Könnyü bennük nem túl összetett ábrák készítése. Ugyanakkor mindkettő könnyen és szabadon kiegészíthető.

badon felhasználhatók is. De ha ’szabad’ toolboxot használunk, akkor is szükség van az alaprendszer jogtisztaságára. olyanok, amik Az R-hez is számtalan kiegészítés tartozik. Ezeket több-kevesebb következetességgel ’packages’-nek nevezik. Ezek minősége, terjedelme, megbízhatósága erősen változik, viszont a felhasználásuk általában szabad. Forrásnyelvük általában hozzáférhető, szükség esetén fejleszthető.

A MATLAB-ban akár magunk is irhatunk olyan 2009 kora őszén, a wavelet témával összefüggő ’toolbox’-okat, amik a rendszer részeivé válnak. Szá- következő MATLAB eszközöket (toolbox): mos ilyen toolbox létezik. Ezeket a toolboxokat wavelet általában külön jogdij terheli, de vannak köztük sza- és R csomagokat (package)

BIBLIOGRAPHY wavelets wavethresh wmtsa waveslim

BIBLIOGRAPHY találtam. A következőkben ezeket az eszközöket tekintem át. Különös tekintettel arra, hogy ...

Az R program és kiegészítései Package: wavelets Version: 0.2-3 Date: 2007-08-01 Title: A package of funtions for computing wavelet filters, wavelet transforms and multiresolution analyses Author: Eric Aldrich <[email protected]> Maintainer: Eric Aldrich <[email protected]> Depends: R (>= 2.0.0), methods Description: This package contains functions for computing and plotting discrete wavelet transforms (DWT) and maximal overlap discrete wavelet transforms (MODWT), as well as their inverses. Additionally, it contains functionality for computing and plotting wavelet transform filters that are used in the above decompositions as well as multiresolution analyses. LazyLoad: yes License: GPL version 2 or newer B.3 Programok

MMIX

123

B. Bibliográfia


124

URL: http://www.atmos.washington.edu/~ealdrich/wavelets/ Packaged: Wed Aug 1 11:40:50 2007; eric Built: R 2.7.1; i386-pc-mingw32; 2008-06-15 21:05:17; windows Package: wavethresh Version: 2.2-9 Note: ----- Version also in wvrelease() in ./R/release.R Date: 2006-08-07 Author: G.Nason of R-port: A.Kovac (1997) and M.Maechler (1999) Maintainer: Martin Maechler <[email protected]> Title: Software to perform wavelet statistics and transforms. Description: Software to perform 1-d and 2-d wavelet statistics and transforms Depends: R (>= 2.1) License: GPL version 2 or later Packaged: Mon Aug 7 11:41:59 2006; maechler Built: R 2.7.1; i386-pc-mingw32; 2008-06-15 21:06:05; windows Package: wmtsa Type: Package Title: Insightful Wavelet Methods for Time Series Analysis Version: 1.0-4 Date: 2007-09-21 Author: W.Constantine (Insightful Corp.) D.Percival (Appl.Phys.Lab. Univ. of Washington)

BIBLIOGRAPHY

BIBLIOGRAPHY

Maintainer: William Constantine <[email protected]> Depends: R (>= 2.5.1), splus2R (>= 1.0-2), ifultools (>= 1.0-3), graphics, stats, MASS DependsSplus: ifultools (>= 1.0-2) Description: Software to book Wavelet Methods for Time Series Analysis, Donald B. Percival and Andrew T. Walden, Cambridge University Press, 2000. License: GPL-2 ZipData: no Packaged: Tue Feb 19 17:39:58 2008; wconstan Built: R 2.9.0; ; 2009-04-17 12:13:02 UTC; windows Package: waveslim Version: 1.6.1 Date: 2007-10-9 Title: Basic wavelet routines for one-, two- and three-dimensional signal processing Author: Brandon Whitcher Maintainer: Brandon Whitcher Depends: R (>= 2.0), stats, graphics, grDevices ZipData: no LazyLoad: yes LazyData: yes Description: Basic wavelet routines for time series (1D), image (2D) and array (3D) analysis. The code provided here is based on wavelet methodology developed in Percival and Walden (2000); Gencay, Selcuk and Whitcher (2001); the B.3 Programok

MMIX

125

B. Bibliográfia


126

dual-tree complex wavelet transform (CWT) from Kingsbury (1999, 2001) as implemented by Selesnick; and Hilbert wavelet pairs (Selesnick 2001, 2002). All figures in chapters 4-7 of GSW (2001) are reproducible using this package and R code available at the book website(s) below. License: GPL (>= 2) URL: http://www.image.ucar.edu/~whitcher/ http://www.image.ucar.edu/~whitcher/book/ Packaged: Tue Oct 9 11:55:13 2007; bjw34032 Built: R 2.9.0; i386-pc-mingw32; 2009-04-17 11:42:03 UTC; windows

BIBLIOGRAPHY

BIBLIOGRAPHY

M. A mellékletek listája A melléklet egy előadás és 3 gyakorlat anyagát tartalmazza, a következők szerint. Előadás Bevezetés a waveletek elméletébe és idősoros, képfeldolgozási alkalmazásába 1. Gyakorlat A wavelet és skála függvények bemutatása 2. Gyakorlat A wavelet spektrum alkalmazasa idősor feldolgozásban 3. Gyakorlat A wavelet spektrum alkalmazasa kép feldolgozásban

M. Mellékletek listája

MMIX

127

Waveletek és ridgeletek azaz zördületek és ráncok

Recommend Documents