A Fourier-analízis alkalmazásai a jel- és képfeldolgozásban
Diplomamunka Írta: Szabó Eszter Alkalmazott matematikus szak
Témavezető: Tóth Árpád, egyetemi docens Analízis Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar
Eötvös Loránd Tudományegyetem Természettudományi Kar 2010
Tartalomjegyzék 1. Előszó
1
2. Matematikai háttér
4
3. Függvényterek
12
3.1. Definíciók . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1.1. A "korlátos" (L∞ -beli) szakaszonként folytonos függvények . . . . . 12 3.1.2. Az "integrálható" (L1 -beli) szakaszonként folytonos függvények . . . 13 3.1.3. A "négyzetesen integrálható" (L2 -beli) szakaszonként folytonos függvények . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.4. A l2 tér . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.5. A differenciálható C n függvények . . . . . . . . . . . . . . . . . . . . 15 3.2. Függvénysorozatok konvergencája . . . . . . . . . . . . . . . . . . . . . . . . 16 4. Fourier-sorok
17
4.1. Bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2. Valós és komplex Fourier-sor . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3. Konvergencia tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3.1. Pontonkénti konvergencia . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3.2. Egyenletes konvergencia . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.3. L2 -beli konvergencia . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5. Egy dimenziós alkalmazás
34
5.1. A trigonometrikus rendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2. A Haar-rendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.3. Három tesztfüggvény trigonometrikus Fourier-sorfejtése . . . . . . . . . . . . 36 5.3.1. Az [1/2,1] karakterisztikus függvénye . . . . . . . . . . . . . . . . . . 36 5.3.2. Az [1/3,1] karakterisztikus függvénye . . . . . . . . . . . . . . . . . . 37
II
5.3.3. A p(x) = x4 − 2x3 + x2 polinom . . . . . . . . . . . . . . . . . . . . 40 5.4. Három tesztfüggvény Haar-rendszer szerinti sorfejtése . . . . . . . . . . . . . 41 5.4.1. Az [1/2,1] karakterisztikus függvénye . . . . . . . . . . . . . . . . . . 41 5.4.2. Az [1/3,1] karakterisztikus függvénye . . . . . . . . . . . . . . . . . . 42 5.4.3. A p(x) = x4 − 2x3 + x2 polinom . . . . . . . . . . . . . . . . . . . . 44 5.5. A trigonometrikus és a Haar-rendszer összehasonlítása . . . . . . . . . . . . 46 6. Két dimenziós alkalmazás
47
6.1. Digitális képek reprezentációja . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2. Szűrés a képtartományban . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.3. Szűrés a frekvenciatartományban . . . . . . . . . . . . . . . . . . . . . . . . 51 6.4. Alkalmazás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Köszönetnyilvánítás
60
Függelék
61
Irodalomjegyzék
63
III
1. fejezet
Előszó Matematikailag a jel egy- vagy többváltozós függvényként írható le, amely információt hordoz valamilyen jelenségről. A XVIII. században és a XIX. század elején több olyan fizikai probléma merült fel, ami az új matematikai elméletek kialakulását, ezzel párhuzamosan a régiek további bővítését segítették elő. A Fourier-analízis a nevét Joseph Fourier (1768-1830) francia matematikus után kapta. A jelanalízis során a jelet leíró számsorozatot vagy függvényt, leképezzük másik számsorozatra vagy függvényre, ennek segítségével a jelnek sok tulajdonságát felismerhetővé teszi. Fourier 1807-ben mutatta be cikkét a hővezetés differenciálegyenletéről. Elmélete, mely szerint tetszőleges folytonos, periodikus függvény előállítható szinusz függvények összegeként, sok fejtörést okozott a kortárs és későbbi matematikus társaknak. Évtizedekig akadtak elméleti problémák, nyitott kérdések, amelyből a gyakorlati alkalmazások során új módszerek, technikák születtek. A jel- ill. képfeldolgozásnak számos gyakorlati felhasználása létezik, például a honvédelemben (radar, hangradar, helymeghatározás); az űrkutatásban (felvételek minőségének javítása, adattömörítés); orvostudományban (elektrokardiogram, képdiagnózis). Az első és a második fejezet tartalmazza a szakdolgozat megértéséhez szükséges matematikai alapokat, amely több egyetemi tantárgy ismeretanyagából ragad ki kisebb részeket. Kimerítően tárgyaljuk a függvénysorok konvergenciafajtáit: a pontonkénti, L2 -beli és egyenletes konvergenciát. Ez fog alapjául szolgálni egy periodikus f függvény közelítő módon, trigonometrikus függvények végtelen összegeként történő előállítására, melyet Fouriersorfejtésnek nevezünk (folytonos esetben Fourier-transzformált). f (x) ∼ a0 +
∞ X
cos(kx) + bk sin(kx)
k=1
Jelölje SN (x) az N. részletösszeget.
1
A függvények előbbi egzakt formája feleslegesnek tűnhet, de látni fogjuk a harmadik fejezetben, hogy az összegzésben szereplő együtthatók (Fourier-együtthatók) ismerete minden információt hordozni fog az eredeti függvényről. Ezen az egyszerű ötleten alapul az adattömörítés folyamata is. Egy útja, hogy a jelet (legyen az egy- vagy többdimenziós) tömörítsünk az, hogy Fourier-sorba fejtjük és a kis abszolutértékű együtthatókat elhagyjuk, ezáltal véges sok együtthatóval rekonstruálható a függvény. Felmerülhet a kérdés, hogy minden függvényt elő tudunk-e állítani részletösszegek sorozatának határértékeként? Bizonyításokkal kimondjuk azon tételeket, amik elégséges feltételt adnak egy függvény sorral való reprezentálására. Nevezetesen látni fogjuk, hogy egy periodikus, folytonos jelet azon x pontjaiban, ahol létezik a deriváltja, ott az SN (x) sorozat pontonkénti konvergenciával közelíti meg az f -t. Ha a függvényről kevesebbet teszünk fel, pl. elhagyjuk a deriválhatóságot, akkor a jelet az előbbi módon nem állíthatjuk elő. 1900-ban Fejér Lipót magyar matematikus a Fourier-sorok elméletében jelentős felfedezést tett közé. Megalkotta az SN (x) sorozat számtani közepeként a Fejér-közepeket, N
σN (x) =
1 X Sk (x) N +1 k=0
amelyek tetszőleges folytonos, periodikus függvényt egyenletes konvergenciával közelítenek meg. A σN (x) Fejér-féle közelítő összeg előállítható oly módon is, hogy a Fourier-sor N. részletösszegében a Fourier-együtthatókat valamilyen súlyozással vesszük. Ezt szűrésnek hívjuk. A Fejér-tétel szerint a szűrt jel jobban közelíti az eredeti függvényt mint a közönséges Fourier-sor. A negyedik fejezetben három tesztfüggvényt választottunk (két karakterisztikus ill. egy polinomfüggvényt), hogy az előző fejezet tételeit példákkal tegyük szemléletesebbé. Egy jel sorfejtése nemcsak szögfüggvényekkel állítható elő, hanem más ortonormált rendszerrel pl. a Haar-bázisfüggvények segítségével. A fejezet végén összehasonlítjuk a két rendszer előnyeit ill. hátrányait. Az ötödik fejezetben az egydimenziós jelek analóg módjára célunk a képfeldolgozás rövid ismertetése. A kétdimenziós esetben a jelfüggvényünk egy olyan képet határoz meg, ahol a kép mérete megegyezik a függvény értelmezési tartományának koordinátáival és az (x, y) koordinátapárban a kép világosságértékei adják meg a függvény értékkészletét. Ezen intenzitások transzformációval történő közvetlen megváltoztatása történik az ún. képtartományban. A képfeldolgozásnak számos felhasználási területe létezik, néhányat említve csupán: alakzatfelismerés, zajszűrés, képtömörítés, hangtömörítés, képjavítás, melyek közül a zajszűréssel foglalkozunk részletesen. Szűrők (maszkok) használatával lokálisak tudunk képeken műveleteket végrehajtani, ezáltal a kisebb részletek változtatásával pontosabb 2
eredményt érhetünk el. A szűrők működési elve, hogy a nemkívánt frekvenciákat csillapítják (zajok) és a hasznos frekvenciákat kis mértékű változtatással, vagy anélkül, átengedik.Az egydimenziós esethez hasonlóan itt számos előnye lesz a Fourier-transzformált használatának, elsősorban az, hogy a számítások műveletigénye lényegesen kisebb lesz nagy méretű szűrők alkalmazása során. A képi illusztrációkat a széles alkalmazhatósági spektrummal rendelkező MATLAB szoftver segítségével készítettem el.
3
2. fejezet
Matematikai háttér Az első fejezetben kimondunk néhány definíciót, állítást, ill. tételt, amelyek tisztán az elméleti hátteret biztosítják a Fourier-transzformált bevezetéséhez. 2.0.1. Definíció. Egy (G, +) kommutatív csoport normált, ha ∃ k.k : G → R+ függvény, ami teljesíti a norma tulajdonságait G-n. Ezen a csoporton bevezethető egy metrika ρ(x, y)=kx − yk, és ez eltolás-invariáns, azaz tetszőleges x, y ∈ G elemekre teljesül, hogy
ρ(x + z, y + z) = ρ(x, y)
(x, y, z) ∈ G
(2.1)
2.0.2. Definíció. Egy (G, ρ) metrikus teret lokálisan kompaktnak nevezünk, ha a (G, +) normált csoport zárt gömbjei kompaktak: {x ∈ G : kxk ≤ r, r > 0} Ha a (G,ρ) metrikus tér kompakt, akkor a G normált csoport szintén kompakt. Nézzünk néhány példát kommutatív normált csoportra, ami fontos lesz a Fourier-transzformáció meghatározása során: 1. (R, +), a norma kxk := |x| 2. (Z, +), a norma kxk := |x| ˙ a norma kxk := min{x, 1 − x}. Az M megegyezik az R/Z faktorcsoporttal, 3. (M, +), amely izomorf a [0,1) félig zárt intervallum modulo 1 vett összeadás csoportjával.
4
˙ A csoport nullelemét jelöljük 0-val, és egy x ∈ M elem inverze legyen 1 − x. A + csoportműveletet értelmezzük a következőképpen: x+y ,ha x + y < 1 ˙ = x+y x+y-1 ,ha x + y ≥ 1
(2.2)
˙ a norma kxk := {min x, 1 − x}. 4. (Mm , +),
k A Mm := { m : k = 0, 1, . . . m − 1 (∀m ∈ N)}, ami az M egy diszkrét m-edrendű
ciklikus részcsoportja. 5. (T, ·), a norma kzk := |1 − z|. A T := {z ∈ C : |z| = 1} jelöli az egységhosszú komplex számok testét, melyben a nullelemet jelöljük 1-gyel, egy z ∈ T elem inverze legyen a komplex konjugáltja. 2.0.3. Definíció. A komplex trigonometrikus függvény legyen a következőképpen definiált leképezés: ǫ(t) := e2πit
(t ∈ R)
(2.3)
2.0.4. Tétel (Euler-formula). Tetszőleges valós t változó esetén eit = cos t + i sin t ahol az i =
√
−1.
Az előbbi tétel egyszerűen kapható az ex Taylor-sorfejtéséből az x = it helyen. 2.0.5. Lemma. Legyen t ∈ R ei(t+2π) = eit eit = 1
eit = e−it cos(nt) =
eint +e−int 2
és sin(nt) =
eint −e−int 2i
Az értelmezési tartomány M halmazra való leszűkítésével az M és T csoportok között izomorfizmust kapunk. Két valós értelmezési-tartománybeli elem összegét komplex számok szorzatába viszi át: ǫ(x + y) = ǫ(x)ǫ(y)
5
(2.4)
2.0.6. Tétel. A következő függvényhalmaz 1 inπt/a √ e , n = . . . , −1, 0, 1, . . . 2a teljes ortonormált rendszert alkot az L2 [−a, a] térben. Ha f (t) = Z a 1 f (t)e−inπt/a dt αn = 2a −a
P∞
inπt/a , −∞ αn e
akkor
2.0.7. Definíció. Egy γ : G → T leképezést a csoport karakterének nevezünk, ha folytonos, és érvényes rá a következő formula: γ(x + y) = γ(x)γ(y).
(2.5)
Ha egy leképezés kielégíti az előbb említett függvényegyenletet a csoportelmélet homomorfizmusnak nevezi. Mivel a komplex trigonometrikus rendszer folytonos és teljesíti a (2.5)-t, ˆ jelöli. A G ˆ ˙ csoport karaktere. G csoport karaktereinek a halmazát G ezért az ǫ az (M, +) a függvényszorzás műveletére nézve csoportot alkot, hiszen bármely két karakter szorzata ˆ ·) karakter, az egységelem γ0 ≡ 1, és egy karakter inverze a konjugáltja. Az így nyert (G, csoportot nevezzük a (G,+) csoport duálisának. Lássunk pár példát a fent említett normált csoportok karaktereinek a halmazára: ˆ := {ǫt (x) := ǫ(tx) = e2πixt , t ∈ R} ∼ 1. (R, +), R = (R, +) ˆ := {ǫt (x) := t ∈ M} ∼ ˙ 2. (Z, +), Z = (M, +) ˆ := {ǫn (x) : n ∈ Z} ∼ ˙ 3. (M, +), M = (Z, +) ˆ m := {ǫn (x) : n ∈ 0, 1, . . . , m − 1} ∼ ˙ 4. (Mm , +), M = (Zm , +) A karakterek természetesen n dimenzióra is kiterjeszthetők a csoportok direkt szorzatának műveletével. A magasabb dimenziójú csoport karaktereit úgy kapjuk, hogy az egyes normált csoportok karaktereinek Kronecker-szorzatát vesszük: γ(x) = (γ1 × γ2 × . . . × γn )(x) := γ1 (x1 )γ2 (x2 ) . . . γn (xn ), (x = (x1 , x2 , . . . xn ) ∈ G) Ebből nyerhetőek a korábbi kommutatív normált csoportokra adott példák n dimenziós ˙ Bármelyik duális csoportjának karakterei a trigonomegfelelői (Rn , +), (Zn , +), (Mn , +). metrikus rendszert tekintve a következőképpen kaphatók meg: ˆ n) (t ∈ Gn , x ∈ G
ǫx (t) := e2πihx,ti 6
(2.6)
amelyben a hx, ti a szokásos Rn skaláris szorzatot jelöli. A Fourier-transzformált értelmezéséhez még szükségünk van néhány mértékelméletbeli fogalomra. Legyen a továbbiakban (G,+) normált Abel-csoport és ρ indukált metrika, amellyel a G metrikus teret alkot. 2.0.8. Definíció. Legyen a B={(G, ρ) metrikus tér nyílt részhalmazai által generált σ-algebra}, ennek részhalmazait Borel-halmazoknak nevezzük. P (X) := {H ⊂ X} jelölje az X halmaz hatványhalmazát. A ⊂ P (X), ∅ ∈ A, m : A → R halmazfüggvény. 2.0.9. Definíció. Az m : A → R halmazfüggvény σ-additív, ha m(∅) = 0 és ha
A1 , A2 , . . . ∈ A páronként diszjunktak, melyekre teljesül ∪∞ i=1 Ai ∈ A, akkor m(∪∞ i=1 Ai )
=
∞ X
m(Ai ).
i=1
2.0.10. Definíció. Az m : A → R halmazfüggvény mérték, ha nemnegatív és σ-additív. 2.0.11. Állítás. ∀H ∈ B esetén x + H := {x + y : y ∈ H} ∈ B, tehát a B halmaz eltolás-invariáns. 2.0.12. Definíció. m: B → R mérték eltolás-invariáns, ha ∀x ∈ G, ∀H ∈ B: m(x + H) = m(H). 2.0.13. Tétel (Haar). Minden lokálisan kompakt topologikus csoporton létezik nemtriviális eltolás-invariáns Borel-mérték. Ennek neve Haar-mérték. Ez konstans szorzó erejéig egyértelmű. 2.0.14. Definíció. A ∈ P (X) halmazgyűrű, ha eleme az üres halmaz és B, C ∈ A esetén B ∪ C ∈ A és B\C ∈ A. 2.0.15. Tétel (Mértékkiterjesztési tétel). Legyen A ⊂ P (X) gyűrű és m : A → [0, ∞] mérték. Ekkor m kiterjeszthető mértékként az A által generált σ-algebrára. Az előző fontos mértékelméleti tétel bizonyítása maga a kiterjesztés konstrukciója. A továbbiakban a Borel-mérték helyett, ennek teljessé tételével kapott hasonlóan m-mel jelölt Haar-mértéket fogjuk használni. 2.0.16. Definíció. Lpm (G)
= {f : G → C m-mérhető, melyre kf kp :=
7
Z
G
|f |p dm
1
p
< ∞; 1 ≤ p ≤ ∞} (2.7)
A 3. fejezetben részletesen tárgyaljuk a függvénytérnek a p=∞, 1, 2 speciális eseteit. 2.0.17. Definíció. Egy (en ) ⊂ H Hilbert térbeli sorozat ortonormált rendszert (ONR) alkot, ha hei , ej iH
1 = δij = 0
,ha i = j ,ha i 6= j
(Kronecker − delta)
(2.8)
2.0.18. Definíció. Egy (en ) ⊂ H Hilbert térbeli sorozat teljes rendszert alkot, ha ∀x ∈ H : x = ~0 ⇔ x⊥en ∀n ∈ N+
(2.9)
2.0.19. Tétel. Legyen (G, +) kompakt csoport és m Haar-mérték. Ekkor a G karakterei ortonormált rendszert alkotnak az L2m téren Z γ1 (x)γ2 (x)dm = δγ1 γ2 G
(γ1 γ2 ∈ G)
(2.10)
Bizonyítás. Jelöljük c-vel az előbbi egyenletet. Ha γ1 6= γ2 , akkor ∃y : γ1 (y) 6= γ2 (y). Z Z c= γ1 (x + y)γ2 (x + y)dm = γ1 (x)γ1 (y)γ2 (x)γ2 (y)dm G
G
mivel a Haar-mérték eltolás-invariáns, ezért igaz = γ1 (y)γ2 (y). A karakterek egységhosszú komplex számok, és a feltételünk szerint γ1 (y) 6= γ2 (y), ezért a szorzat értéke csak akkor lehet nulla, ha c = 0, ami akkor teljesül, ha γ1 (x) 6= γ2 (x), azaz a karakterek ortonormált rendszert alkotnak. 2.0.20. Definíció. Egy f ∈ L1m függvény Fourier-transzformáltján a következő képlettel
ˆ →C megadott leképezést értjük, fˆ : G Z fˆ(γ) := f (t)γ(t)dm(t) G
ˆ (γ ∈ G)
(2.11)
Az elméleti háttér után az (2.11) egyenletnek a speciális eseteivel foglalkozunk, amikor ˙ a G = R, Z, M, Mm . A formális számolást jelentősen megkönnyíti, hogy a (R, +) és (M, +) ˙ esetén pedig csoportok Haar-mértéke megegyezik a Lebesgue-mértékével, a (Z, +), (Mm , +) a Lebesgue-mérték diszkrét megfelelője adódik mértékként. 2.0.21. Definíció. Fourier-transzformáltak. ˆ = R. (i) G := R, G Egy f ∈ L1 (R) trigonometrikus Fourier-transzformáltja (TFT) Z fˆ(x) = f (t)e−2πixt dt (x ∈ R) R
8
(2.12)
ˆ = Z. (ii) G := M, G Egy f ∈ L1 (M) trigonometrikus Fourier-együtthatója (TFE) Z
fˆ(n) =
f (t)e−2πint dt M
(n ∈ Z)
(2.13)
(x ∈ M)
(2.14)
ˆ = M. (iii) G := Z, G Egy f ∈ l1 (Z) trigonometrikus Fourier-sora (TFS) X
fˆ(x) =
f (n)e−2πixt
n∈Z
ˆ = Zm . (iv) G := Mm , G Egy f : Mm → C diszkrét Fourier-transzformáltja (DFT) X
fˆ(n) =
f (t)e−2πint
t∈Mm
(n ∈ Zm )
(2.15)
A Fourier-transzformáció segítségével az f időtartományából átléphetünk a frekvenciatartományba, azaz azon térbe melynek elemei az f függvény Fourier-transzformáltja ill. Fourieregyütthatói, attól függően, hogy folytonos vagy diszkrét volt-e a vizsgált jel. Fontos kérdés, hogyan nyerhetjük vissza az "eredeti" jelünket? Erre a kérdésre adnak választ a függvény értelmezési tartományától függő inverziós formula különböző alakjai. 2.0.22. Definíció. Inverziós formulák. (i) G := R csoportra vonatkozó inverziós formula f (x) =
Z
ˆ 2πixt dt f (t)e
(f, fˆ ∈ L1 (R))
(2.16)
(f ∈ L1 (M), fˆ ∈ l1 (Z))
(2.17)
R
(ii) G := M csoportra vonatkozó inverziós formula f (x) =
X
fˆ(n)e2πinx
n∈Z
(iii) G := Z csoportra vonatkozó inverziós formula f (n) =
Z
fˆ(x)e2πinx dx M
(f ∈ l1 (Z))
(2.18)
(f ∈ l1 (Mm ))
(2.19)
(iv) G := Mm csoportra vonatkozó inverziós formula f (x) =
1 X ˆ f (n)e−2πinx m n∈Zm
9
A továbbiakban ezekből csak azt a két esetet használjuk, amikor a jelet trigonometrikus Fourier-együtthatóinak segítségével állítjuk elő, ill. a diszkrét Fourier-sorfejtést használtam a 5-6. fejezetben a numerikus számítások során az egy és két dimenziós példák képi illusztrálására. A Fourier-transzformált magasabb dimenziójú megfelelője analóg módon adódik az előbbiekből:
fˆ(x) :=
Z
ˆ G
f (t)ǫx (t)dt
ahol ǫx (t) = e−2πihx,ti ǫx (t) = ǫx1 (t1 ) · · · ǫxn (tn ) ˆ n , t = (t1 , . . . , tn ) ∈ Gn ). (x = (x1 , . . . , xn ) ∈ G A kiterjesztés örökli az egydimenziós transzformált jó tulajdonságait. Jelölje az F az egydimenziós f jel Fourier-transzformáltját. 2.0.23. Tétel. Legyen f és g deriválható függvény. 1. A Fourier-transzformált és az inverze lineáris operátor. Tehát tetszőleges c konstans esetén F[f + g] = F[f ] + F(g) és F[cf ] = cF[f ]. F −1 [f + g] = F −1 [f ] + F −1 (g) és F −1 [cf ] = cF −1 [f ]. 2. Az n. derivált Fourier-transzformáltja: F[f (n) ](x) = (ix)n F[f ](x). 3. Az n. derivált inverz Fourier-transzformáltja: F −1 [f (x) ](t) = (−it)n F −1 [f ](x). 4. A Fourier-transzformált eltoltja: F[f (t − a)](x) = e−ixa F[f ](x). 5. A Fourier-transzformált dilatáltja: 1 x F[f (bt)](x) = F[f ]( ). b b 10
Két függvény között értelmezzünk egy új műveletet, a konvolúciót, amely használata nem vezet ki az L1 térből (ellentétben a függvények pontonkénti szorzásával, amire nézve az L1 nem zárt). 2.0.24. Definíció. Tegyük fel, hogy f és g integrálható függvények. Az f és g függvények közötti konvolúció műveletet jelöle ∗, ami a következőképpen számítandó: (f ∗ g)(x) =
Z
∞ −∞
f (x − t)g(t)dt =
Z
∞ −∞
f (t)g(x − t)dt.
2.0.25. Tétel. Legyenek f és g integrálható függvények. Ekkor F[f ∗ g] = F[f ]F[g]. A képfeldolgozásban az előző tétel nagyon fontos szerepet fog játszani, ez lesz az előnye a frekvenciatartománybeli szűrésnek a képtartománybeli szűréssel szemben. Nagy méretű szűrőmaszkok esetében a frekvenciatérbeli elemek szorzásával sokkal gyorsabban érhetjük el a kívánt változtatást a képünkön, mint az eredeti tartományban a konvolúció műveletével. Szűrésre az utolsó fejezetben fogunk példát látni.
11
3. fejezet
Függvényterek 3.1.
Definíciók
A jelfeldolgozásban az Lp térnek p = ∞, 1, 2 esetei kapnak főbb szerepet. Ezért vizsgáljuk meg az ezeket leíró függvényeket és néhány tulajdonságukat. 3.1.1. Definíció. Azt mondjuk, hogy egy f : I → R függvény szakaszonként folytonos, ha véges sok pont kivételével folytonos és a kivételes pontokban f -nek ugráshelyei vannak [11], azaz a véges sok kivételes xj pontban léteznek az f (xj +0), f (xj+1 −0) (j = 1, . . . , n−1) véges egyoldali határértékek.
3.1.1.
A "korlátos" (L∞ -beli) szakaszonként folytonos függvények
3.1.2. Definíció. Egy I intervallumon értelmezett szakaszonként folytonos f (x) függvényt korlátosnak nevezünk (≡ L∞ (I)-belinek), ha ∃M > 0 : |f (x)| ≤ M
∀x ∈ I
Az f (x) ∈ L∞ normája kf k∞ := sup{|f (x)| : x ∈ I}
(3.1)
Példák: Ha I zárt, korlátos intervallum, akkor az I-n folytonos f (x) függvény L∞ (I)-beli. Megjegyzés: fontos, hogy zárt legyen az intervallum, mert az f (x) = 1/x az I = (0, 1]-on tekintve nem korlátos függvény. Egy szakaszonként folytonos függvény minden véges intervallumon korlátos. A p(x) polinomfüggvények nem korlátosak a számegyenesen, de korlátosak R minden véges részintervallumán. 12
A sin x, cos x ∈ L∞ (R), így a komplex eix is korlátos, és
ksinxk∞ = kcosxk∞ = eix ∞ = 1.
3.1.2.
Az "integrálható" (L1 -beli) szakaszonként folytonos függvények
3.1.3. Definíció. Egy I intervallumon értelmezett szakaszonként folytonos f (x) függvényt integrálhatónak nevezünk (≡ L1 (I)-belinek), ha Z |f (x)| dx < ∞ I
Az f (x) ∈ L1 normája kf (x)k1 =
Z
I
|f | dx
(3.2)
Példák: Ha f (x) ∈ L∞ korlátos az I véges intervallumon, akkor f (x) integrálható függvény I-n. Korlátos, zárt intervallumon folytonos függvény L1 -beli. Korlátos, zárt intervallumon szakaszonként folytonos függvény L1 -beli. Egy korlátos függvény nem szükségszerűen integrálható. Tekintve a 0 ≤ α ≤ 1 kitevőt, az f (x) = x−α ∈ L∞ [1, ∞), de ∈ / L1 ([1, ∞)).
3.1.3.
A "négyzetesen integrálható" (L2 -beli) szakaszonként folytonos függvények
3.1.4. Definíció. Egy I intervallumon értelmezett szakaszonként folytonos f (x) függvényt integrálhatónak nevezünk (≡ L2 (I)-belinek), ha Z |f (x)|2 dx < ∞ I
kf k2 :=
Z
I
|f (x)|2 dx
1/2
(3.3)
Példák: Véges intervallumon korlátos függvény négyzetesen integrálható. Ez természetesen tartalmazza a zárt intervallumon folytonos ill. szakaszonként folytonos függvényeket. Tetszőleges nem feltétlenül korlátos I intervallumon azok a függvények, amelyek korlátosak és integrálhatóak, azok négyzetesen is integrálhatóak az I-n. 13
Legyen 0 < α < 1/2, f (x) = x−α , ekkor f (x) ∈ L2 [−1, 1]. Ez mutatja, hogy egy négyzetesen integrálható függvény nem szükségképpen korlátos. Legyen α ≥ 1/2, ekkor f (x) ∈ / L2 [−1, 1].
Legyen 0 ≤ α ≤ 1/2, f (x) = x−α , ekkor f (x) ∈ / L2 [1, ∞). Legyen α > 1/2, ekkor f (x) ∈ L2 [1, ∞).
Megjegyzés: a Cauchy-Schwarz egyenlőtlenség kapcsolatot teremt a L1 és L2 függvények között. 3.1.5. Tétel. Legyen I egy véges (azaz korlátos) intervallum. Ha f (x) ∈ L2 (I), akkor f (x) ∈ L1 (I).
A tétel megfordítása nem érvényes az intervallum korlátosságától függetlenül, például f (x) = x−1/2 ∈ L1 (0, 1), de nem négyzetesen integrálható a (0, 1) intervallumon. Ez a végtelen dimenziós vektortér a gyakorlatban hasznos lesz jelek analizálására. Egy jel, mint ahogy a bevezetésben említettük egy f (t) függvénnyel írható le, ami t időpontbeli értékeit adja meg a jelnek, másképpen fogalmazva az intenzitását adott helyen. Itt a t változó [a, b] intervallumból kerül ki, ez reprezentálja a jel időtartamát (előfordulhat, hogy a = −∞, b = ∞). A vizsgálandó jelet a gyakorlatban diszkretizáljuk, azaz az [a, b] intervallumnak veszik egy N pontból álló felosztását. Vegyük azt az egyszerű esetet, amikor az a = 0 és b = 1, tehát [0, 1] intervallum osztópontjai ekkor tj := j/N
1 ≤ j ≤ N . Ha a
függvény folytonos, akkor a [tj , tj+1 ) intervallumon elég jól megközelíti az f (tj )-t. Ezért az f függvényt a következő vektorral approximáljuk: fN = (f (t1 ), f (t2 ), . . . , f (tN )) ∈ Rn Az eredeti függvény lehető legjobb közelítését akkor kapjuk, ha az N elég nagy, másképpen egyre finomodó felosztássorozatot veszünk. Hasonlóképpen járunk el, amikor f és g négyzetesen integrálható jelek szorzatát akarjuk megkapni. Vesszük az f , g diszkretizáltjait, fN -t és gN -t, majd ezek n dimenziós vektorainak skaláris szorzatát képezzük: hfN , gN iRn =
N X
f (tj )g(tj ) =
j=1
N X
f (j/N )g(j/N ).
(3.4)
j=1
Az előző megközelítéssel az gond, hogy ha az N túl nagy, akkor a jobb oldali sor nem biztos, hogy véges. Ennek kiküszöbölésére 1/N -nel elosztjuk mindkét oldalt: N N X 1 1 X 1 hfN , gN iRn = f (j/N )g(j/N ) = f (j/N )g(j/N ) ∆t, ahol ∆t = N N N j=1
j=1
14
(3.5)
Ha N → ∞, akkor a diszkretizált függvények jól közelítik az eredeti függvényeinket, ez ad ötletet az L2 -beli elemek skaláris szorzatának értelmezéséhez, hogy az összegzés felfogható integrálként. 3.1.6. Definíció. Legyen f, g ∈ L2 [a, b]. A skaláris szorzat: Z b hf, giL2 = f (t)g(t)dt
(3.6)
a
Az L2 Hilbert-tér (3.6) a skaláris szorzatra nézve.
3.1.4.
A l2 tér
Nagyon sok alkalmazás esetén a jel már diszkrét. Például egy CD-ről származó jel reprezentálható diszkrét pontok halmazával, amik az intenzitást határozzák meg valamilyen idő-intervallumban. A függvény ebben az esetben egy sorozat, X = . . . , x−1 , x0 , x1 , . . ., ahol a megfelelő xj a j. [tj , tj+1 ] intervallumba eső értéke a jelnek. Elméletileg mindkét irányba végtelen hosszú sorozat is elképzelhető. A valóságban azonban rendszerint egy bizonyos pont után "megáll", lecseng a jel, ami matematikailag úgy interpretálható, hogy ∃N ∀ |j| > N esetén az xj = 0. 3.1.7. Definíció. Az l2 tér az X = . . . , x−1 , x0 , x1 , . . . ∈ C sorozatokból áll, ahol P∞ 2 2 n=−∞ |xn | < ∞. Az X, Y ∈ l elemek skaláris szorzata hX, Y il2 :=
∞ X
xn y n .
(3.7)
n=−∞
Az l2 Hilbert-tér a (3.7)-re nézve. Megszámlálható teljes ortonormált rendszert véve az L2 -ből kölcsönösen egyértelmű hozzárendelés létesíthető a l2 tér elemei között, amely a Riesz-Fischer tétel alapján lineáris izomorfia, és izometrikus: ˆ = hx, en i, n ∈ N ∈ l2 L2 ∋ x → x
3.1.5.
A differenciálható C n függvények
3.1.8. Definíció. Legyen n ∈ N. Azt mondjuk, hogy egy f (x) függvény eleme a C n (I)
térnek, ha n-szer folytonosan differenciálható az I-n. A C 0 (I) az I-n folytonos függvényeket jelöli. Az f (x) függvény C ∞ osztályba tartozik, ha eleme a C n (I)-nek ∀n ∈ N. Példák: A p(x) polinomfüggvények mind C ∞ (R)-beliek.
A "sapka" függvény f (x) = (1 − |x|)χ[−1,1] (x) folytonos, de nem deriválható az R-n, mivel az x = −1, 0, 1 helyeken nem létezik a deriváltja. 15
3.2.
Függvénysorozatok konvergencája
3.2.1. Definíció. Egy fn függvénysorozat pontonként konvergál az f függvényhez az [a, b] intervallumon, ha ∀t ∈ [a, b] ∀ǫ > 0 : ∃N ∀n ≥ N esetén |fn (t) − f (t)| < ǫ. 3.2.2. Definíció. Egy fn (t) függvénysorozat egyenetesen konvergál (L∞ -ben) az f (t) függvényhez az [a, b] intervallumon, ha ∀ǫ > 0 : ∃N ∀n ≥ N esetén |fn (t) − f (t)| < ǫ, ∀t-re. Lényeges különbség a két konvergencia-típus között, hogy az egyenletes konvergencia N száma csak az ǫ-tól függ ún. univerzális küszöb, míg a pontonkénti konvergencia esetén az N függ a t helytől és az ǫ számtól is. 3.2.3. Definíció. Azt mondjuk, hogy az fn függvénysorozat L2 ([a, b])-ben konvergál az f függvényhez, ha limn→∞ kfn − f kL2 =0 . Másképpen ∀ǫ > 0 ∃N ∈ Z: ∀n ≥ N esetén kf − fn kL2 < ǫ. Mi a kapcsolat a három konvergencia-típus között? Az egyenletes konvergencia nem engedi meg, hogy a az fn sorozat bármely helyen is nagy mértékben eltérjen a közelítendő f függvénytől, míg a pontonkénti konvergencia definíciójában ezt nem zárja ki. Ebből következik, hogy ha az fn függvénysorozat egyenletesen konvergens, akkor pontonként is konvergens. A visszafele irány nem teljesül, példaként említve az fn (t) = tn , n = 1, 2, 3 . . . sorozatot. Ez a 0 ≤ t < 1 esetén pontonként tart a nullához, ha az n egyre nő. Azonban a t = 1 helyhez közelítve egyre lassabb a konvergencia, nincs univerzális küszöbszám. 3.2.4. Tétel. Ha az fn függvénysorozat egyenletesen konvergál egy f függvényhez n → ∞ esetén egy a ≤ t ≤ b korlátos intervallumon, akkor fn tart az f -hez az L2 [a, b]-beli konvergencia értelemben is. Így általában egy pontonként konvergens sor nem biztos, hogy konvergál L2 normában. De a Lebesgue-féle dominált konvergencia tételben szerepel, hogy ha az fn pontonként tart az f -hez és egyenletesen korlátos, azaz |fn | ≤ K, K ≥ 0, akkor ezzel a plusz feltétellel
teljesül az L2 -beli konvergencia is.
16
4. fejezet
Fourier-sorok 4.1.
Bevezetés
A −π ≤ x ≤ π intervallumban az f (x) függvény sorfejtését fogjuk előállítani. A trigonometrikus sorfejtés a következő formulával kapható meg: a0 +
X
ak cos (kx) + bk sin (kx)
(4.1)
k
Első kérdés mely felmerülhet bennünk, hogy az egyenletben szereplő sor konvergens vagy divergens. Ebben a fejezetben elégséges feltételt adunk arra, hogy mikor lesz véges a sorfejtés, ill. mikor állítja elő az eredeti függvényt a (4.1) sor. 4.1.1. Tétel. Ha f (x) = a0 +
P∞
k=1 ak
cos (kx) + bk sin (kx), akkor az a0 , ak , bk -t az f (x)
függvény Fourier-együtthatóinak nevezzük, és a következőképpen számoljuk ki:
Z π 1 a0 = f (x)dx 2π −π Z π 1 an = f (x) cos(nx)dx π −π Z 1 π bn = f (x) sin(nx)dx. π −π
(4.2) (4.3) (4.4)
Az így kapott együtthatók persze csak akkor számolhatóak ki ezekkel az integrálokkal, ha a jelet a trigonometrikus rendszer szerint fejtettük sorba a −π ≤ x ≤ π intervallumon. Felmerülhet a kérdés, hogyan nyerjük más origóra szimmetrikus intervallumokra az együtthatókat, ill. ha antiszimmetrikus, miben módosulnak a képletek.
17
4.1.2. Lemma. Tegyük fel, hogy G(x) tetszőleges 2π szerint periodikus függvény. Ekkor tetszőleges valós c számra teljesül, hogy Z π+c Z G(x)dx = −π+c
π
G(x)dx.
(4.5)
−π
A lemmát használva az G(x) = f (x) cos x és G(x) = f (x) sin x esetére adódik, hogy az (4.1.1) tétel állítása érvényben marad minden 2π hosszúságú intervallumra. Ebből az a sejtésünk, hogy a formulában csak az intervallum hossza változtatja az együtthatók értékét. nπx Legyen −a ≤ x ≤ a. A cos x és a sin x tulajdonságaiból a cos nπx a és sin a függvények
periódusa 2a. A [−π, π] intervallumról a [−a, a] intervallumra az t = xπ/a, dt = πdx/a helyettesítéses integrállal a (4.1.2) formula megfelelő változata nyerhető Z π Z a 1 πx 1 G(t)dt = G( )dx. 2π −π 2a −a a Így a sejtésünket alátámasztó tétel a következő: 4.1.3. Tétel. Ha f (x) = a0 +
P∞
k=1 ak
cos (kπx/a) + bk sin (kπx/a) −a ≤ x ≤ a, ekkor
az f (x) függvény Fourier-együtthatói: Z a 1 f (x)dx 2a −a Z 1 a an = f (x) cos(nπx/a)dx a −a Z a 1 bn = f (x) sin(nπx/a)dx. a −a a0 =
(4.6) (4.7) (4.8)
Az eddigi számolások során nem használtuk ki a szöggfüggvényeink azon tulajdonságát, hogy a sin x páratlan, a cos x páros függvény. Az együtthatók integrállal való számítása során egyszerűsödnek a formulák, mert az integrál előjeles területként számítandó, ezért 4.1.4. Lemma. Ha F páros függvény, akkor Z
a
F (x)dx = 2
−a
Z
a
F (x)dx. 0
Ha F páratlan függvény, akkor Z
a
F (x)dx = 0.
−a
Következésképpen egy f függvény Fourier-sorát csak sin x és cos x függvény építi fel, attól függően, hogy az f páros vagy páratlan. 18
4.1.5. Tétel. Ha az f (x) függvény páros, akkor a Fourier-sora a [−a, a] intervallumon csak cos x P függvényből áll. Tehát f (x) = a0 + ∞ k=1 ak cos(kπx/a), ahol Z a 1 a0 = f (x)dx, (4.9) a 0 Z 2 a ak = f (x) cos(kπx/a)dx. (4.10) a 0 Ha az f (x) függvény páratlan, akkor a Fourier-sora a [−a, a] intervallumon csak sin x P függvényből áll. Tehát f (x) = ∞ k=1 bk sin(kπx/a), ahol Z 2 a bk = f (x) sin(kπx/a)dx. a 0 Legtöbbször a függvények nem szimmetrikus intervallumon értelmezettek, ezért vizsgáljuk meg a [0, a] intervallum esetét. Különítsük el a fentebb említettek szerint a függvényt paritása szerint: Az f (x) páros kiterjesztése a [−a, a] intervallumra. Legyen f(x) ha 0 ≤ x ≤ a fe (x) = f(-x) ha −a ≤ x < 0
Az fe (x) páros függvény a [−a, a] intervallumon, alkalmazható rá (4.1.5), ezért fe x = f (x)[0, a]-n, és az integrálformula csak az f (x)-t tartalmazza majd, ami kizárólag cos x függvényből fog felépülni: f (x) = a0 +
∞ X k=1
ak cos(kπx/a) 0 ≤ x ≤ a
ahol Z 1 a f (x)dx, a 0 Z 2 a ak = f (x) cos(kπx/a)dx. a 0 a0 =
(4.11) (4.12)
Az f (x) páratlan kiterjesztése a [−a, a] intervallumra. Legyen f(x) ,ha 0 ≤ x ≤ a fo (x) = -f(-x) ,ha −a ≤ x < 0
Az fo (x) páratlan függvény a [−a, a] intervallumon, az előzőekhez hasonlóan fo x = f (x) [0, a]-n, és az integrálformula csak az f (x)-t tartalmazza, ami kizárólag sin x függvényből fog felépülni: f (x) =
∞ X
bk sin(kπx/a)
k=1
19
0≤x≤a
ahol 2 bk = a
4.2.
Z
a
f (x) sin(kπx/a)dx. 0
Valós és komplex Fourier-sor
4.2.1. Definíció. Az f (x) függvény komplex Fourier-sora a −π ≤ x ≤ π intervallumon ∞ X
f (x) =
αn einx
n=−∞
ahol αn az ún. komplex Fourier-együttható Z 1 π αn = f (x)e−inx dx. 2π −π Röviden vizsgáljuk meg mi a kapcsolat a valós és a komplex Fourier-sorok között. Mutassuk meg, hogy a kettő egymásból származtatható. Egyszerűsítésképpen vegyük a x időváltozót a −π ≤ x ≤ π intervallumból, és a komplex sort válasszuk szét pozitív és negatív részekre: f (x) =
−1 X
inx
αn e
+ α0 +
n=−∞
ahol αn =
1 2π
∞ X
αn einx ,
(4.13)
n=1
Z
π
f (x)e−inx dx.
−π
Ha az f valós értékű volt, akkor az αn = αn , mert Z π Z 1 1 π inx α−n = f (x)e dx = f (x)e−inx dx = αn . 2π −π 2π −π Ezt felhasználva a (4.1) a következő alakot ölti, amelyben csak pozitív tagokra összegzük: f (x) = α0 +
∞ X
n=1
∞ ∞ X X αn einx + αn einx = α0 + 2Re αn einx . n=1
(4.14)
n=1
Így a komplex αn és a valós an , bn Fourier együtthatók közötti kapcsolat adódik a (4.1.1) tételből Z π 1 f (x)dx = a0 2π −π Z π Z π 1 1 1 −inx αn = f (x)e dx = cos nx − i sin nxdx = (an − ibn ) 2π −π 2π −π 2 1 α−n = (an + ibn ). 2 α0 =
Felhasználva az (4.14)-t megkapjuk a f függvény valós trigonometrikus Fourier-sorát ∞ ∞ X X f (x) = α0 + 2Re αn einx = α0 + Re (an − ibn )(cos nx + i sin nx) n=1
= a0 +
∞ X
n=1
an cos(nx) + bn sin(nx)
n=1
20
Természetesen hasonlóan megkapható a valós függvénysorokból a komplex függvénysorok származtatása. A továbbiakban egyaránt használni fogom egy függvény valós, ill. komplex sorral történő előállítását.
4.3.
Konvergencia tételek
Ebben az alfejezetben elégséges feltételt adunk arra, hogy egy f (x) függvény F (x) Fourier-sora a [−π, π] intervallumon mikor állítja elő a függvényt. Legyen F (x) = a0 +
∞ X
an cos nx + bn sin nx = a0 + lim
N →∞
n=1
N X
an cos nx + bn sin nx
n=1
ahol a0 , an , bn jelöli az f Fourier-együtthatóit. Egy függvénysort akkor neveznek pontonként, egyenletesen, L2 -ben konvergensnek, ha a sor részletösszegeinek sorozata pontonként, egyenletesen ill. L2 -ben konvergens. Megmutatjuk, hogy ha egy f (x) függvény folytonos és periodikus, akkor az f (x) differenciálhatóságától függően fogja az F (x) formális Fourier-sora előállítani a függvényt. Egy fontos tétel az ak , bk Fourier-együtthatókról. 4.3.1. Tétel (Riemann-Lebesgue Lemma). Tegyük fel, hogy az f (x) szakaszonként folytonos függvény az a ≤ x ≤ b intervallumon. Ekkor lim
Z
b
k→∞ a
f (x) cos(kx)dx = lim
Z
k→∞ a
b
f (x) sin(kx)dx = 0
Fontos következtetése a Riemann-Lebesgue lemmának az, hogy egy pozitív egész küszöbszámtól kezdve végtelen sok együttható lesz nagyon közel a nullához, tulajdonképpen ezen alapszik az adattömörítés folyamata is.
4.3.1.
Pontonkénti konvergencia
4.3.2. Tétel. Tegyük fel, hogy f (x) 2π szerint periodikus, folytonos függvény. Ekkor minden x pontban, ahol létezik az f ′ (x), az f (x) = F (x), azaz az F (x) pontonként konvergál az f (x) függvényhez. Bizonyítás. Jelölje SN a részletösszegek sorozatát:
SN (x) = a0 +
N X
ak cos(kx) + bk sin(kx)
k=1
ahol az a0 , ak , bk az f (x) függvény Fourier együtthatói. Bizonyítandó, hogy SN (x) → f (x), ha N → ∞. Először SN (x)-t írjuk át másik alakba. 21
1. A Fourier-együtthatók helyettesítése. Használva az együtthatók kiszámítására vonatkozó (4.1.1) tételt adódik, hogy SN (x) =
1 2π
Z
π
f (t)dt
−π
Z Z π N 1 X π + f (t) cos(kt) cos(kx)dt + f (t) sin(kt) sin(kx)dt π −π −π k=1 Z π N h X i 1 = f (t) 1 + 2 cos(kt) cos(kx) + sin(kt) sin(kx) dt. 2π −π k=1
Felhasználva a cos(x − y) = cos(x) cos(y) + sin(x) sin(y) addíciós összefüggést, 1 SN (x) = 2π
Z
π −π
N X f (t) 1 + 2 cos(k(t − x)) dt.
(4.15)
k=1
A jobb oldal összeg kiszámításához tekintsük a következő lemmát. 2. A Dirichlet-mag kiszámítása. 4.3.3. Lemma. Tetszőleges u ∈ [−π, π] intervallumból teljesül sin((N +1/2)u) sin(u/2) 1 + 2 cos(u) + 2 cos(2u) + . . . + 2 cos(N u) = 2N + 1
,ha u 6= 0 ,ha u = 0
Bizonyítás. A komplex exponenciálisra vonatkozó Euler-formulából felhasználva cos(nu) = Re{(eiu )n } összefüggést 1 1 2 +cos(u)+cos(2u)+. . .+cos(N u) = 2 − +1+cos(u)+cos(2u)+. . .+cos(N u) 2 2 = −1 + 2
N X k=1
N nX o cos ku = −1 + 2Re (eiu )k .
(4.16)
k=0
A jobb oldalon álló szumma egy geometriai összeg,
PN
k=0 z
k,
ahol a z = eiu . A
geometriai sor összegképletére vonatkozó ismereteinkből következik, hogy n 1 − ei(N +1)u o 1 + 2 cos(u) + 2 cos(2u) + . . . + 2 cos(N u) = −1 + 2Re 1 − eiu
(4.17)
ha eiu 6= 1.
A jobb oldalon álló tört számlálóját és nevezőjét e−iu/2 -l osztva egyaránt, a következő összefüggést kapjuk n 1 − ei(N +1)u o n e−iu/2 − ei(N +1/2)u o sin(u/2) + sin((N + 1/2)u) Re = Re = . 1 − eiu 2 sin(u/2) e−iu/2 − eiu/2 22
Ebből pedig a következő végeredmény adódik: sin(u/2) + sin((N + 1/2)u) sin(u/2) sin((N + 1/2)u) . = sin(u/2)
1 + 2 cos(u) + 2 cos(2u) + . . . + 2 cos(N u) = −1 +
3. A Fourier-sor N. részletösszegének kiszámítása. Felhasználva a lemmát az u = t − x helyettesítéssel az (4.15) egyenletbe: N 1 X f (t) + cos(k(t − x)) dt 2 −π k=1 Z π sin((N + 1/2)(t − x)) 1 f (t) dt = 2π −π sin((t − x)/2) Z π 1 = f (t)DN (t − x)dt 2π −π
SN (x) =
1 π
Z
π
Az egyszerűsítés végett legyen sin((N + 1/2)u) sin(u/2)
DN (u) =
(4.18)
az ún. Dirichlet-mag. A korábbi integrálformulában az u = t − x változócserét alkalmazva 1 SN (x) = 2π
Z
π−x
1 f (u + x)DN (u)du = 2π −π−x
Z
π
f (u + x)DN (u)du.
(4.19)
−π
Mivel az f és DN függvények periódusa 2π, a (4.1.2) lemma alkalmazásával kapjuk az utolsó egyenlőséget. 4. A Dirichlet-mag integrálja. 4.3.4. Lemma. 1 2π
Z
π
DN (u)du = 1 −π
Bizonyítás. Használva a (4.3.3) állítását DN (u) =
sin((N + 1/2)u) = 1 + 2 cos(u) + 2 cos(2u) + . . . + 2 cos(N u)). sin(u/2)
Integrálva az egyenletet 1 2π
Z
π
−π
DN (u)du =
1 2π
Z
Z π 2 du + cos(u) + cos(2u) + . . . + cos(N u)du . 2π −π −π | {z } | {z } π
=2π
=0
23
5. Utolsó lépés. Vegyünk az SN (x) (4.19)-beli előállítását, és megmutatjuk, hogy SN (x) =
1 2π
Z
π −π
Használva a (4.3.4) lemmát felírható f (x) = 1 2π
Z
π
−π
(4.20)
f (u + x)DN (u)du → f (x). 1 2π
Rπ
−π
f (x)DN (u)du-ként és
f (u + x) − f (x) DN (u)du → 0, ahol N → ∞.
A (4.18) segítségével a fenti határérték továbbírható: 1 2π
Z
π
f (u + x) − f (x) sin(u/2)
−π
(4.21)
sin((N + 1/2)u)du → 0.
Ahhoz, hogy alkalmazhassuk a Riemann-Lebesgue lemmát, szükséges feltétel, hogy az integrálandó függvény folytonos legyen ill. az argumentumban az u egész számmal legyen megszorozva. Ezért használjuk fel a sin(α + β) = sin(N u) cos(u/2) + cos(N u) sin(u/2) addíciós képletet. 1 2π
Z
π
−π
h f (u + x) − f (x)
1 + 2π
Z
π
−π
i cos(u/2) sin(N u)du
(4.22)
sin(u/2) h i f (u + x) − f (x) cos(N u)du.
(4.23)
A (4.23)-ban a [f (u + x) − f (x)] folytonos, tehát alkalmazható a Riemann-Lebesgue lemma. A (4.22) egyenletben a cos(u/2) folytonos függvénnyel való szorzás nem változtat a tört határértékén, ezért elég a törtet vizsgálni. g(u) :=
f (u + x) − f (x) sin(u/2)
A g(u) az u változó függvényeként folytonos a [−π, π] intervallumon az u = 0 kivételével.A tételünk feltevése szerint ∃f ′ (x) = limu→0
f (u+x)−f (x) . u
Ha a g füg-
gvénynek a 0 helyen megszüntethető szakadása van, ha a következőképpen definiáljuk: lim g(u) = lim
u→0
u→0
f (u + x) − f (x) f (u + x) − f (x) u/2 = lim ·2 u→0 sin(u/2) u sin(u/2) =1 | {z } = f ′ (x) · 1 · 2 = 2f ′ (x).
Ezzel az értékeadással az g(u) folytonos függvény, alkalmazható rá a Riemann-Lebesgue lemma, ezért állításunkat bizonyítottuk. Megjegyzés: lényeges, hogy a deriváltak létezzenek, kevés a konvergenciához feltenni azt, hogy a függvény folytonos és periodikus.
24
4.3.5. Tétel (DuBois-Reymond). Létezik f (x) folytonos, 2π szerint periodikus függvény, melynek a Fourier-sora divergál az x = 0 helyen. Másképpen: limN →∞ SN (0) nem létezik. 4.3.6. Definíció. Az f (x) függvény jobb- és baloldali határértéke legyen a következőképpen definiálva. A baloldali határérték: f (x − 0) = lim f (x − h) h→0+
A jobboldali határérték f (x + 0) = lim f (x + h) h→0+
Az f (x) függvény balról differenciálható, ha létezik a f ′ (x − 0) = lim
h→0−
f (x + h) − f (x) h
határérték. Az f (x) függvény jobbról differenciálható, ha létezik a f ′ (x + 0) = lim
h→0+
f (x + h) − f (x) h
határérték. Az előállításról szóló (4.3.2) tétel megköveteli a függvény folytonosságát és periodikusságát, ami sok esetben nem teljesül. Ekkor mi a teendő? A periodikusság problémája könnyen áthidalható, mert tetszőleges függvénynek vehető periodikus kiterjesztése a számegyenesen. Viszont a folytonosság nem korrigálható ilyen módon. A következő tétel állítása megmutatja, hogy a szakadási helyeken mennyire közelíti jól a nem folytonos függvényt a Fouriersora. 4.3.7. Tétel. Legyen f (x) szakaszonként folytonos, periodikus függvény. Legyen az x egy ugráshely. Tegyük fel, hogy léteznek a pontban az egyoldali deriváltak. Ekkor az f Fourier sora konvergál az x helyen a következő számtani középhez: f (x + 0) + f (x − 0) 2
Bizonyítás. Hasonlóképpen történik az (4.3.2) tételhez, azonban a 4. pontban a Fourier-magra vonatkozó integrált bontsuk két egyenlő részre: 25
4’
Z
1 2π
π 0
1 DN (u)du = 2π
Z
0
DN (u)du =
−π
1 2
Ez azért tehető meg, mert DN (u) páros függvény, ezért szimmetrikus félintervallumokra vett területe egyenlő. 5’ Ebben azt kell bebizonyítanunk, hogy 1 2π
Z
π
−π
f (u + x)DN (u)du →
f (x + 0) + f (x − 0) , ahol N → ∞ 2
(4.24)
Az előző egyenletet is bontsuk két részre 1 2π
Z
1 2π
Z
π 0
f (u + x)DN (u)du →
f (x + 0) 2
f (u + x)DN (u)du →
f (x − 0) 2
0 −π
Az 4. pontot felhasználva, a határérték átrendezéséből nyerjük 1 2π
Z
1 2π
Z
π
0 0
−π
f (u + x) − f (x + 0) DN (u)du → 0
(4.25)
(4.26)
f (u + x) − f (x − 0) DN (u)du → 0.
Felhasználva a (4.18) PN -re vonatkozó összefüggést 1 2π
Z
π
0
f (x + u) − f (x + 0) sin(u/2)
sin((N + 1/2)u)du → 0.
A tétel feltevése szerint a bal- és jobboldali deriváltak léteznek az x-ben. Ezért hasonlóan eljárva, az
f (x+u)−f (x+0) sin(u/2)
jobbról folytonos, a
f (x+u)−f (x−0) sin(u/2)
balról folytonos és
ebből kapjuk a jobb- és baloldali kiterjesztést, melyre a Riemann-Lebesgue lemmát alkalmazva nyerjük a tételünk állítását.
4.3.2.
Egyenletes konvergencia
Azt mondjuk, hogy az f (x) Fourier sora egyenletesen konvergál az f (x) függvényhez, ha a részletösszegek sorozatára teljesül, hogy SN (x) = a0 +
N X k=1
ak cos(kx) + bk sin(kx) → f (x) egyenletesen, ha N → ∞
ahol a0 , ak , bk a Fourier együtthatók. 4.3.8. Következmény. Egy folytonosan differenciálható, 2π periódusú f (x) függvényhez a Fourier sora egyenletesen konvergál a [−π, π] intervallumon.
26
Vegyünk a (4.3.7) tétel szerint egy szakaszonként folytonosan deriválható, 2π szerint periodikus függvényt, a g(x)-t. Legyen a g(x) egyik szakadási helye az xk , és itt az ugrás mértéke a. Ekkor képezve a g(xk ) − a(χ[xk ,1] ) különbséget, folytonosan differenciálható függvényt kapunk. A tétel 2π periódusú függvényekről szól, de a π, ahogy korábban is láttuk, helyettesíthető tetszőleges a számmal. Fontos megjegyezni az egyenletes konvergencia azon tulajdonságát, hogy megőrzi a folytonosságot. A következő lemma egy elégséges feltételt ad egyenletes és abszolút konvergenciára. 4.3.9. Lemma. Tegyük fel, hogy teljesül f (x) = a0 +
∞ X
ak cos(kx) + bk sin(kx)
k=1
a
∞ X k=1
|ak | + |bk | < ∞
feltétellel. Ekkor a Fourier-sora egyenletesen és abszolút konvergál az f (x) függvényhez. 1905-ben egy fiatal magyar matematikus, Fejér Lipót, bebizonyított egy a folytonos függvények konvergenciájára vonatkozó tételt. Az ő ötlete azon alapult, hogy ne a részletösszegek sorozatát vegyük alapul, hanem azok számtani közepét, és ezzel próbáljuk előállítani a keresett jelet. A "Fejér-közepek" legyenek: N
σN (x) :=
1 X Sk (x), N +1
(4.27)
k=0
ahol SN jelöli az N. részletösszeget: N X
SN (x) =
αk einx
k=−N
és αk a k. komplex Fourier együttható. 4.3.10. Lemma (Fejér-mag). (i) Ha f : [−π, π] → C folytonos függvény, akkor a Fejér-közepek felírhatók az ún. Fejérmag integrálásával: 1 σN (t) = 2π
Z
ahol a Fejér-mag:
π −π
KN (t − x)f (x)dx N
KN (x) :=
1 X Dk (x) N +1 k=0
ill. a Dirichlet-mag általános alakja: Dk (x) =
k X
m=−k
27
eimx .
(4.28)
(ii) További számolásból kapható:
KN (t) =
1 N +1
sin((N +1)t/2) sin(t/2)
2
N +1
(iii) A Fejér-mag intergálja 1: 1 2π
Z
ha t 6= 0 ha t = 0
π
KN (x)dx = 1.
−π
(iv) A Fejér-mag nemnegatív: KN (t) ≥ 0
tetszőleges t esetén
(v) Tetszőleges η > 0-re: KN (t) → 0 egyenletesen
∀t − re : η ≤ |t| ≤ π és N → ∞
Bizonyítás: (i) Az N. részletösszegnek a pontonkénti konvergencia bizonyításából felhasználva a Dirichlet-maggal történő előllítását: 1 SN (x) = 2π
Z
π
−π
f (x − t)DN (t)dt
kapható: Z π N N i 1 X 1 Xh 1 Sk (x) = f (x − t)Dk (t)dt σN (x) = N +1 N +1 2π −π k=0 k=0 Z π N h 1 X i 1 = f (x − t) Dk (t) dt 2π −π N +1 k=0 Z π 1 = f (x − t)KN (t)dt 2π −π Ezzel megkaptuk a részletösszegek Fejér-maggal való kiszámítását. (ii) Ismét használjuk a Dirichlet-magra ismertetett képletet: DN (x) =
N X
eikx = 1 + 2
k=−N
N X k=1
28
cos(kx) =
sin[(N + 1/2)x] . sin(x/2)
Helyettesítsük be a Fejér-mag (4.3.10) formulájába a fentebbit: (N + 1)KN (x) =
N X
Dk (x) =
k=0
= = = = =
1 Im sin(x/2)
N X sin[(N + 1/2)x] sin(x/2)
k=0 N hX
ei(k+1/2)x
k=0
i
h 1 ei(N +1)x − 1 i Im eix/2 sin(x/2) eix − 1 h ei(N +1)x − 1 i 1 Im ix/2 sin(x/2) e − e−ix/2 1 − cos[(N + 1)x] 2 sin2 (x/2) sin2 [(N + 1)x/2] . sin2 [x/2]
(iii) Most azt kell bebizonyítani, hogy a Fejér-mag integrálja 1. Helyettesítsük be a Dirichlet és a Fejér-mag közötti összefüggésbe a Dirichlet-mag exponenciális függvénnyel történő megadását: N k 1 X X imx KN (x) = e . N +1 k=0 m=−k
Integráljuk, majd cseréljük fel az integrálás és az összegzés sorrendjét (megtehető, mert véges sok tag van): Z π Z π h N k 1 1 1 X X imx i KN (x)dx = e dx 2π −π 2π −π N + 1 k=0 m=−k
= Mivel
k X
k=0 m=−k
h 1 Z π i eimx dx . 2π −π
0 ,ha m 6= 0 1 eimx dx = 1 ,ha m = 0 2π −π Z
ezért
1 N +1
N X
1 2π
Z
π
N
π
1 X KN (x)dx = 1 = 1. N +1 −π k=0
(iv) A négyzetes előállításból adódóan trivilitás. (v) Rögzítsünk le egy η > 0-t. Tetszőleges η ≤ |t| ≤ π a Fejér-magban szereplő törtre felső becslés adható, mivel a maximuma
1 -nek sin2 (x/2)
η-ban vétetik fel
1 1 ≤ . 2 sin x/2 sin η/2 2
Ezért igaz a következő állítás 0 ≤ KN (x) ≤
1 1 2 N + 1 sin η/2 29
η ≤ |x| ≤ π
15
10
5
0 −4
−3
−2
−1
4.1. ábra. A
0
1 sin2 (x/2)
1
2
3
4
függvény grafikonja
mely bizonyítja az egyenletes konvergenciát a 0-hoz, ha N → ∞. A Fejér-mag ezen tulajdonságaiból adható felső becslés arra, hogy a Fejér-közepek mennyire közelítik jól az f függvényt. 4.3.11. Tétel. Ha f : [−π, π] → C folytonos, akkor σN (t) → f (t)
∀t ∈ [−π, π] ha
N → ∞. Bizonyítás. Legyen 0 < η < π és Z 1 |σN (t) − f (t)| ≤ 2π
π −π
KN (t − x)f (x)dx − f (t)
mivel a Fejér-mag integrálja 1, ezért Z π Z π 1 1 = KN (x)f (t − x)dx − f (t)KN (x)dx . 2π −π 2π −π Kiemelés után:
Z 1 = 2π
π −π
(KN (x) f (t − x) − f (t) dx
figyelembe véve, hogy a Fejér-mag nemnegatív értékű ill. az intergál abszolútértékére ismert felsőbecslésből, adódik 1 ≤ 2π
Z
π −π
KN (x) |f (t − x) − f (t)|dx
30
η értékétől függően bontsuk ketté az integrált Z 1 = KN (x) |f (t − x)dx − f (t)| dx 2π |x|≤η Z 1 KN (x) |f (t − x) − f (t)| dx + 2π |x|>η Z 1 ≤ sup|x|≤η |f (t − x) − f (t)| KN (x)dx 2π |x|≤η Z 1 |f (t − x) − f (t)| dx + sup|x|≥η KN (x) 2π |x|>η
A 1 2π
Z
|x|≤η
KN (x)dx ≤
1 2π
Z
π
−π
KN (x)dx = 1 és kf kL1 ≤ c kf k∞
becsléseket használva juthatunk el a kívánt állításhoz: ≤ sup|x|≤η |f (t − x) − f (t)| + 2 kf k∞ sup|x|≥η KN (x). Ezzel megkaptuk, hogy a Fejér-közepek pontonként konvergálnak az f (t) függvényhez. A (4.3.11) tételből további meggondolással megkapható a folytonos függvényekre legerősebb, egyenletes konvergenciáról szóló tétel: 4.3.12. Tétel. Ha f : [−π, π] → C folytonos, akkor kσN (x) − f (x)k∞ → 0
haN → ∞
Bizonyítás. Az integrál tulajdonságából: Z π 1 |f (x − t) − f (x)| KN (t)dt. |σN (x) − f (x)| ≤ 2π −π Mivel folytonos függvény kompakt halmazon egyenletesen folytonos, ezért adott ǫ > 0 ∃δ > 0, hogy ha |x − y| ≤ δ akkor |f (x) − f (y)| ≤ ǫ. Bontsuk ketté az előbbi integrált δ szerint: 1 Z kσN (x) − f (x)k = |f (x − t) − f (x)| KN (t)dt 2π |t|≤δ Z + |f (x − t) − f (x)| KN (t)dt . δ≤t≤π
Mivel az f egyenletesen folytonos, ezért Z Z π 1 1 ǫ ǫKN (t)dt ≤ KN (t)dt = ǫ. 2π |t|≤δ 2π −π Legyen M := sup−π≤t≤π |f (t)|. A második integrálra a következő becslés teljesül: Z Z 1 M 2M KN (t)dt = KN (t)dt. 2π δ≤|t|≤π π δ≤|t|≤π 31
A (4.3.10) lemma utolsó állításának következménye: Z ∀ fix η > 0 esetén, lim
N →∞ η≤|t|≤π
Ezért ∃N ∈ N, ∀n ≥ N :
R
η≤|t|≤π
KN (t)dt = 0.
KN (t)dt < ǫ. Következésképpen
∀n ≥ N : kσN (x) − f (x)k ≤ ǫ + ǫ = 2ǫ.
4.3.3.
L2 -beli konvergencia
Az előző fejezetben megnéztük, hogyan tart a függvényhez az ő Fourier sora a függvény folytonosságától függően. De mit tudunk abban az esetben mondani, amikor nincs egyenletes, ill. pontonként konvergencia? Mivel van náluk "gyengébb" konvergencia típus, ezért sejtésünk az lehet, hogy talán L2 -beli értelemben jól approximálhatjuk a jelet. Funkionálanalízisbeli ismeretek alapján az L2 végtelen dimenziós tér bázisát alkotja az 1, sin x és a cos x függvények: VN := {1, cos(kx), sin(kx), k = 1, . . . , N }. Ezért a tér egy tetszőleges eleme előállítható a báziselemek lináris kombinációjaként c0 +
N X
ck cos(kx) + dk sin(kx)
k=1
ahol ck , dk komplex számok. Tegyük fel, hogy f ∈ L2 [−π, π]. Vegyük VN azon elemeit: fN (x) = a0 +
N X
ak cos(kx) + bk sin(kx)
k=1
ahol ak , bk a Fourier-együtthatók a (4.1.1) tétel alapján. Az a kérdésünk, hogy melyik L2 - beli elemmel közelíthetjük legjobban az f (x) függvényt? Tulajdonképpen az ak , bk együtthatók felfoghatóak úgy is, mint a cos(kx), sin(kx) által kifeszített alterekre vett ortogonális projekciója az f (x) függvénynek, tehát fN a legjobban közelítő függvény az L2 -beli értelemben. 4.3.13. Lemma. Legyen f ∈ V = L2 [−π, π]. Legyen VN = {1, cos(kx), sin(kx), 1 ≤ k ≤ N } által kifeszített lineáris tér. Legyen fN (x) = a0 +
N X
ak cos(kx) + bk sin(kx)
k=1
ahol ak , bk az f Fourier-együtthatói. Ekkor fN a VN térbőé az f -t legjobban megközelítő függvény az L2 -normában kf − fN kL2 = ming∈VN kf − gkL2 32
4.3.14. Tétel. Tegyük fel, hogy f ∈ L2 ([−π, π]). Legyen fN (x) = a0 +
N X
ak cos(kx) + bk sin(kx)
k=1
ahol ak , bk az f Fourier együtthatói. Ekkor fN konvergál f -hez L2 ([−π, π])-ben, azaz kfN − f k2L →, haN → ∞ Ez teljesül a komplex trigonometrikus Fourier sorokra is. 4.3.15. Tétel. Tételezzük fel, hogy f ∈ L2 ([−π, π]) a következő komplex Fourier-együtthatókkal 1 αn = 2π
Z
π
−π
f (x)e−inx dx n ∈ Z.
Ekkor a részletösszegek sorozata fN (x) =
N X
k=−N
konvergál az f -hez L2 ([−π, π])-ben, ha N → ∞.
33
αk eikx
5. fejezet
Egy dimenziós alkalmazás 5.1.
A trigonometrikus rendszer
A Fourier-sorok számítása során leggyakrabban a trigonometrikus rendszer (eit ) segítségével számítjuk ki a Fourier-együtthatókat. A rendszer legfontosabb tulajdonságait az első fejezetben taglaltuk.
5.2.
A Haar-rendszer
Ebben a fejezetben mutatunk a [0, 1] intervallumon egy ortogonális rendszert, amit Haar-rendszernek hívnak. A Haar-bázis a legegyszerűbb és a legelső ortonormált wavelet bázis. A számegyenes diadikus intervallumainak nevezzük a [0, 1) állandó felezéséből kapott intervallumokat, tehát Im,k := [2−m k, 2−m (k + 1)], ahol m ∈ Z+ és 0 ≤ k < 2m . Néhány tulajdonságuk: Minden Im,k a [0, 1) részintervalluma. Hosszuk |Im,k | = 2−m . Tetszőleges természetes n számnak egyértelműen megfeleltethető egy (m, k) számpár, m ∈ Z+ , és 0 ≤ k < 2m a következőképpen: n = 2m + k. m
Minden m számra az {Im,k }2k=0−1 halmaz a [0, 1) intervallum partíciója, azaz diszjunktak és együttesen lefedik a [0, 1)-t.
34
5.2.1. Definíció. A [0, 1] intervallum Haar-rendszere legyen a következőképpen meghatározva: n ∈ N, n := 2m + k, ahol m ∈ N, 0 ≤ k < 2m . h0 := 1. 2m/2 ,ha 2km ≤ x < k+1/2 2m k+1/2 hn (x) = −2m/2 ,ha 2m ≤ x < k+1 2m 0 ,különben
A természetes számok és a diadikus intervallumok között bijekció létesíthető, ezért minden Im,k diadikus intervallumhoz egy hn Haar-függvény tartozik és fordítva (n = 2m + k). Az első nyolc Haar-függvényről grafikon található a függelékben. Fourier-sorok generálása A 3. fejezet végén levő állításaink szerint az L2 térben az f (x)-t legjobban approximáló függvénysorozat a VN altérből való. Általánosítható-e megállapítás trigonometrikus rendszer helyett más ortonormált bázis által vett generált altérre? 5.2.2. Definíció. Legyen f (x) ∈ L2 (I) függvény és {gn (x)} az I intervallumon értelmezett ortonormált rendszer. Az f (x) generált Fourier-együtthatói legyenek a {gn (x)} rendszerre nézve a következők: c(n) =
Z
I
f (x)gn (x)dx = hf, gn iL2 .
Ekkor az f (x) generált Fourier-sora a {gn (x)} rendszerre nézve: f (x) ∼
X
n∈N
hf, gn i gn (x).
(5.1)
A következő tétel arra adja meg a választ, hogy mikor állítja elő a függvényt az előbbi sorösszeg. 5.2.3. Tétel. Legyen f (x) ∈ L2 (I), {gn (x)} teljes ortonormált rendszer L2 (I)-ben. Ekkor a (5.1) L2 -ben konvergens és
f (x) =
X
n∈N
hf, gn i gn (x).
A továbbiakban fontos szerepet fog betölteni az alkalmazások során, hogy a trigonometrikus és a Haar-rendszer teljes a [0, 1] intervallumon. A következő szakaszokban a 3. fejezetben tárgyalt konvergenciatételekre mutatunk függvényeket, amiket közelítünk trigonometrikus ill. Haar-rendszerrel is egyaránt. A [0, 1) intervallumot tekintettem a karakterisztikus és a polinomfüggvényem értelmezési tartományaként.
35
5.3. 5.3.1.
Három tesztfüggvény trigonometrikus Fourier-sorfejtése Az [1/2,1] karakterisztikus függvénye
Első "tesztfüggvényként" vettem az
1
2, 1
intervallum karakterisztikus függvényét, azaz
1 ,ha 1 ≤ x ≤ 1 2 χ[1/2,1] (x) = 0 ,ha 0 ≤ x < 1 2
A Fourier-együtthatók: Z 1 Z α0 = χ[1/2,1] (x)dx = 0
αn =
Z
1dx =
1/2
1 0
1
χ[1/2,1] (x)e−2πinx dx =
Z
1
1 2 e−2πinx dx =
1/2
1
h e−2πinx i1 −2πin
1/2
(−1)k − 1 2πin
=
0.5
0.45
0.4
0.35
0.3
0.5
0.25
0.2
0.15
0.1
0.05
0
0.5
0 −8 −7 −6 −5 −4 −3 −2 −1
1
0
1
2
3
4
5
6
7
8
5.1. ábra. Az [1/2,1] karakterisztikus függvénye és 17 darab Fourier-együtthatója
A komplex Fourier-együttható csak abban az esetben vesz fel nem nulla értéket, ha páratlan indexeket tekintjük
0 αn = −1
πin
,ha n = 2k ,ha n = 2k + 1
36
A trigonometrikus Fourier-sorfejtés a következő alakban írható:
χ[1/2,1] (x) =
∞ X 1 −1 + e2πi(2k+1)x 2 πi(2k + 1) k=−∞
= =
=
−1 ∞ X X 1 −1 −1 + e2πi(2k+1)x + e2πi(2k+1)x 2 πi(2k + 1) πi(2k + 1) 1
1 + 2
k=−∞ ∞ X
1 + 2
∞ X
k=1
k=1
−1 (e2πi(2k+1)x − e−2πi(2k+1)x ) {z } πi(2k + 1) | 2i sin(2π(2k+1)x)
−2 x π(2k + 1)
n=4
n=16
1.5
1.5
1
1
0.5
0.5
0
0
−0.5
0
0.5
−0.5
1
0
n=32 1.5
1
1
0.5
0.5
0
0
0
0.5
1
n=100
1.5
−0.5
0.5
−0.5
1
0
0.5
1
5.2. ábra. Az [1/2,1] karakterisztikus függvényének n. trigonometrikus részletösszege
5.3.2.
Az [1/3,1] karakterisztikus függvénye
Második "tesztfüggvényem" szintén a karakterisztikus függvény, ami az
1 ,ha 1 ≤ x ≤ 1 3 χ[1/3,1] (x) = 0 ,ha 0 ≤ x < 1 3
37
1 3
helyen ugrik.
A Fourier-együtthatók:
Z
1
α0 =
1
αn =
Z
χ[1/3,1] (x)dx =
0
0
=
Z
1 1/3
−2πinx
χ[1/3,1] (x)e
1 3
1dx = dx =
Z
1
e−2πinx dx =
1/3
h e−2πinx i1
− cos(2/3πnx) + i sin(2/3πnx) −2πin
−2πin
1/3
Az indexek hárommal való osztási maradékától függően más és más lesz az együttható 1
0.7
0.6
0.5
0.4 0.5 0.3
0.2
0.1
0
0.3333
0.6667
0 −8 −7 −6 −5 −4 −3 −2 −1
1
0
1
2
3
4
5
6
7
8
5.3. ábra. Az [1/3,1] karakterisztikus függvénye és 17 darab Fourier-együtthatója értéke:
αn =
0
,ha n = 3k √
3+ 3 −4πin √ 3− 3 −4πin
,ha n = 3k + 1 ,ha n = 3k + 2
38
A Fourier-sorfejtés:
χ[1/3,1] (x) =
∞ X 1 αn e2πinx + 3 n=−∞
√ √ ∞ X 1 3− 3 3+ 3 2πi(3k+1) 2πi(3k+2) = + 2Re + e e 3 −4πi(3k + 1) −4πi(3k + 2) k=1 √ √ ∞ 1 X 3+ 3 3− 3 = + sin(2π(3k + 1)x) + sin(2π(3k + 2)x) 3 −2π(3k + 1) −2π(3k + 2) k=1
n=4
n=16
1.5
1.5
1
1
0.5
0.5
0
0
−0.5
0
0.3333
0.6667
−0.5
1
0
0.3333
n=32 1.5
1
1
0.5
0,5
0
0
0
0.3333
1
0.6667
1
n=100
1.5
−0.5
0.6667
0.6667
−0,5
1
0
0.3333
5.4. ábra. Az [1/3,1] karakterisztikus függvényének n. trigonometrikus részletösszege A képeken látható, hogy mindkét karakterisztikus függvény esetében az ugráspontokhoz egyre közelebb érve oszcilláció lép fel. Ez a jelenség az ún. Gibbs-effektus. Ennek egy érdekes tulajdonsága, hogy a kiugrás mértéke minden esetben ugyanakkora, az össszeadandók számától függetlenül! Hiába veszünk egyre több tagot, az oszcilláció nem tűnik el, csak egyre kisebb lesz a rezgés intervalluma.
39
5.3.3.
A p(x) = x4 − 2x3 + x2 polinom
Fejtsük Fourier-sorba a következő "szép, sima" negyedfokú, egy főegyütthatós polinomfüggvényt.
p(x) = x4 − 2x3 + x2 Ez a széleken ill. deriváltjai a végpontokban mind 0-t vesznek fel, p(0) = p(1) = p′ (0) = p′ (1) = 0 A trigonometrikus rendszer szerinti Fourier-együtthatók: Z
1
x4 x3 i1 1 + = 5 4 3 0 30 0 Z 1 −3 αn = (x4 − 2x3 + x2 )e−2πinx dx = 4 4 2π n 0 α0 =
x4 − 2x3 + x2 dx =
h x5
0.07
0.035
0.06
0.03
0.05
0.025
0.04
0.02
0.03
0.015
0.02
0.01
0.01
0.005
0
0
0.5
−2
0 −8 −7 −6 −5 −4 −3 −2 −1
1
0
1
2
3
4
5
6
7
8
5.5. ábra. A p(x) = x4 − 2x3 + x2 polinom és 17 darab Fourier-együtthatója A sorfejtés:
∞
X −3 1 p(x) = + e2πinx . 30 −∞ 2π 4 n4
40
n=1
n=4
0.07
0.07
0.035
0.035
0
0
0.5
0
1
0
0.5
1
5.6. ábra. A p(x) = x4 − 2x3 + x2 polinom n. trigonometrikus részletösszege
5.4. 5.4.1.
Három tesztfüggvény Haar-rendszer szerinti sorfejtése Az [1/2,1] karakterisztikus függvénye
Az integrálás határait jelentősen leszűkítik az egyes Haar-függvények tartói:
Z
1
α0 =
1
α1 =
Z
1
α2 =
Z
0
0
0
χ[1/2,1] (x)h0 (x)dx =
Z
χ[1/2,1] (x)h1 (x)dx =
Z
χ[1/2,1] (x)h2 (x)dx =
Z
1
1/2 1 1/2 1
1dx =
1 2
−1dx =
−1 2
0dx = 0
1/2
n ≥ 2 esetén minden Haar-együttható 0 lesz, mert ha a diadikus intervallum beleesik az 1 2 , 1 -be, a Haar-függvény az adott diadikus intervallum felére nézve középpontosan szimmetrikus, így az előjeles területek kiejtik egymást.
χ[1/2,1] (x) =
∞ X 0
1 −1 αn hn (x) = 1 + (−1) = 1 2 2
41
1
0.7
0.6
0.5
0.4 0.5 0.3
0.2
0.1
0
0.5
0
1
0
2
4
6
8
10
12
14
16
5.7. ábra. Az [1/2,1] karakterisztikus függvénye és 17 db Haar együtthatója n=0
n=1
2
1.4
1.2 1.5 1 1
0.8
0.6
0.5
0.4 0 0.2
−0.5
0
0.5
0
1
0
0.5
1
5.8. ábra. Az [1/2,1] karakterisztikus függvényének n. Haar-részletösszege
5.4.2.
Az [1/3,1] karakterisztikus függvénye
Az [ 13 , 1] függvény esetén, már kevesebb együttható lesz nulla, az intervallumra nézett aszimetrikusságból adódóan:
42
Z
1
α0 =
1
α1 =
Z
1
α2 =
Z
1
α4 =
Z Z
1
0
0
Z
1
χ[1/3,1] (x)h0 (x)dx =
1
χ[1/3,1] (x)h1 (x)dx =
Z
2 3
1dx =
1/3
h1 (x)dx =
1/3 1/2
χ[1/3,1] (x)h2 (x)dx =
Z
χ[1/3,1] (x)h4 (x)dx =
Z
χ[1/3,1] (x)h5 (x)dx =
Z
Z
1/2
1dx + 1/3
√
Z
1 1/2
−1dx =
2 3
√ − 2 − 2dx = 6 0 1/3 Z 1 Z 1 Z 1 α3 = χ[1/3,1] (x)h3 (x)dx = h3 (x)dx = h3 (x)dx = 0 0
0
α5 =
0
1/3 1
1/2
h4 (x)dx = 0
1/3 3/8
2dx +
1/3
Z
1/2
3/8
−2dx =
−1 6
Az előzőekkel ellentében szép formula csak bonyolultabb számolással lenne adható, amit 1
0.7
0.6
0.5
0.4 0.5 0.3
0.2
0.1
0
0.3333
0.6667
0
1
0
2
4
6
8
10
12
14
16
5.9. ábra. A [1/3,1] karakterisztikus függvénye és 17 darab Haar-együtthatója most mellőzünk: χ[1/3,1] (x) =
∞
2 X + αn hn (x) 3 k=1
43
n=4
n=8
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0.3333
0.6667
0
1
0
0.3333
n=16 1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
1
0.6667
1
n=32
1
0
0.6667
0.3333
0.6667
0
1
0
0.3333
5.10. ábra. Az [1/3,1] karakterisztikus függvényének n. Haar-részletösszege
5.4.3.
A p(x) = x4 − 2x3 + x2 polinom
A polinom Haar-együtthatói: 1
α0 =
Z
1
αn =
Z Z
(k+1/2)/2m
=
3
Z
1
0
x4 − 2x3 + x2 dx =
h x5 5
−
2x4 x3 i1 1 + = 4 3 0 30
(x4 − 2x3 + x2 )hn (x)dx
= 2m/2
4
3
2
m/2
(x − 2x + x )2
k/2m
=
2
(x − 2x + x )h0 (x)dx =
0
0
4
h x5 5
−
2x4 4
+
x3 i(k+1/2)/2m 3
k/2m
dx −
Z
− 2m/2
(k+1)/2m
(x4 − 2x3 + x2 )2m/2 dx
(k+1/2)/2m h x5 2x4
5
−
4
+
x3 i(k+1)/2m 3 (k+1/2)/2m
−k5 + 2(k + 1/2)5 − (k + 1)5 5 29m/2 2(k4 − 2(k + 1/2)4 + (k + 1)4 ) + 4 27m/2 −k3 + 2(k + 1/2)3 − (k + 1)3 + 3 25m/2
44
0.07
0.035
0.06
0.03
0.05
0.025
0.04
0.02
0.03
0.015
0.02
0.01
0.01
0.005
0
0
0.5
0
1
0
2
4
6
8
10
12
14
16
5.11. ábra. A p(x) = x4 − 2x3 + x2 polinom és 17 darab Haar-együtthatója A polinom Haar-rendszer szerinti sorfejtése:
∞
X 1 + αn hn (x) p(x) = 30 k=1
n=4
n=8
0.06
0.06
0.04
0.04
0.02
0.02
0
0
0.5
0
1
0
n=16 0.08
0.06
0.06
0.04
0.04
0.02
0.02
0
0.5
1
n=32
0.08
0
0.5
0
1
0
0.5
5.12. ábra. A p(x) = x4 − 2x3 + x2 polinom n. Haar részletösszege
45
1
5.5.
A trigonometrikus és a Haar-rendszer összehasonlítása
Miként a Haar-bázis függvényeinek tartója a [0, 1] kicsi részintervallumaira koncentrálódik, ezért ha az m szám nagy, akkor az intervallum hossza nagyon kicsi. Ebből kifolyólag a Haar-rendszer időben jól lokalizál. Jelentős különbség továbbá, hogy Haar-bázis függvényei lépcsős függvények, ezzel szemben a Fourier-bázis függvények végtelen sokszor differenciálhatók a [0, 1]-n. Az említett jellemzők, és látványos képek alapján a Haar-rendszer roppant hatékonyan fog reprezentálni olyan függvényeket amelyek folytonosak, és diszkrét ponthalmaz kivételével differenciálhatóak (fűrészfogfüggvény) vagy a nem folytonos függvényeket, melyeknek véges sok ugrása van (karakterisztikus függvény), ellenben a sima függvényekkel, amiket sokkal lassabban közelít jól, ezek esetén pedig a Fourier-bázis approximál jobban. n=16
n=32
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
−0.2
0
0.3333
0.6667
−0.2
1
0
0.3333
0.6667
1
5.13. ábra. Az [1/3,1] intervallum karakterisztikus függvényének egyaránt 33 darab együtthatót tartalmazó Fourier- ill. Haar-sorfejtése
46
6. fejezet
Két dimenziós alkalmazás A technika, és a számítógépek nagy léptékű fejlődésével párhuzamosan kezdett kialakulni a képek számítógépes megjelenítésére való igény. Gondolhatunk akár az orvostudományban a páciensekről készített diagnózis felállításában óriási segítséget jelentő röntgenképek elterjedésére, amivel precízebb diagnózist tudnak adni. A digitális képfeldolgozás fogalmán azt a folyamatot értjük, mely során a világból érkező vizuális információt számítógéppel feldolgozhatóvá, alakíthatóvá (kicsinyítés, nagyítás, színek változtatása, szűrés stb.) tesszük. Tehát a kép tulajdonképpen nem más mint vizuális információk összessége, ahol a lényeges információt, amit objektumnak nevezzünk, szeretnénk szétválasztani a felesleges részektől. Ezen objektumokat képpontok (pixelek) csoportjai alkotják, mert önmagában egy-egy képpont nem hordoz lényeges információt.
6.1.
Digitális képek reprezentációja
A kép tulajdonképpen nem más, mint egy két dimenziós f (x, y) függvény, ahol a függvény értéke a képpont "intenzitását" (világosságértékeit) adja meg az (x, y) koordinátapárban. Egy kép digitalizálásához fontos alapkövetelmény, hogy a koordináták digitalizáltak legyenek, ezáltal válik felhasználhatóvá a számítógép számára. Ezért azt a képet hívjuk digitalizált képnek, ahol minden koordináta és a képet meghatározó függvényértékek diszkrét és véges mennyiségek. A különböző képpontokhoz rendelt értéket többféle módon lehet megadni, ez függ a kép színétől (fekete-fehér, színes), annak tárolási módjától, ill. milyen módon akarjuk a képet feldolgozni. A szürkeárnyalatú képek esetén leginkább a 8 bites kódolás (értékek [0, 255] között) az elterjedt, mert ez kellően részletes, bár a szem ennél többet is meg tud különböztetni. A legsötétebb (fekete) színt a 0 képpontérték jelöli, míg a nála nagyobb számok az egyre világosabbakat. A 255 a fehér színt reprezentálja. Még
47
gyakran használják a [0, 1] intervallumra koncentrált lebegőpontos számábrázolást. Ezen képek reprezentálása egy M × N méretű, valós értékű mátrixszal történik, a koordináta konvenció legyen a mátrixok indexelésének megfelelően a következőképpen: az origót tekintsük az (1,1) párban (f (0, 0) = f(1, 1)), és a kép egy pixelének színét, színmélységét a mátrix egy eleme fogja meghatározni. Így MATLAB-beli megjelenítés mátrixa:
f(1, 1)
f(1, 2)
...
f(1, N )
f(2, 1) f(2, 2) . . . f(2, N ) f= .. .. .. . . . f(M, 1) f(M, 2) . . . f(M, N )
A képjavítást (image enhancement) igénylő problémák során a képet könnyebben feldolgozható formába alakítjuk, amelyben nem feltétlenül az a cél, hogy az eredeti kép (a valóság mintavételezettje) minél "szebb", hozzá leginkább hasonlító mását nyerjük ki, hanem esetlegesen a számunkra értékes objektumok, élek, határok, jellegzetességek fokozásával, hangsúlyozásával elérjük az elképzeléseinknek megfelelő végeredményt. A képjavítási eljárások két csoportba sorolhatóak be aszerint, hogy az eredeti képsíkon (világosságértékekkel) vagy a frekvenciatartományban (Fourier-transzformáltak által alkotott térben) dolgozunk.
6.2.
Szűrés a képtartományban
Először foglalkozzunk a képtartományban a világosságkódok közvetlen használatával történő számítások vizsgálatával. A következő kifejezéssel szemléltethető a folyamat: g(x, y) = T (f (x, y))
(6.1)
ahol f (x, y) az eredeti képet, g(x, y) a kapott képet jelöli. A képletben szereplő T pedig az f -n értelmezett operátor, amely az (x, y) páron illetve a "szomszédjain" hat. A legegyszerűbb megközelítés egy (x, y) pont szomszédjainak meghatározására, ha kijelölünk egy négyzetet vagy téglalapot (ami pixeltől pixelig tart) az (x, y) középpont körül. Általában a mátrix sorainak és oszlopainak a számát páratlan számúra választják, hogy a mátrix középső eleme a kiszemelt képpontra illeszthető legyen, és erre szimmetrikus téglalapot (a pont környezetét) használunk. A (6.1) azon speciális esetére mutatunk példát, amikor a kiszemelt pont szomszédai 1 × 1-s négyzetbe foglalhatók, azaz maga a pont önmaga környezete. Ebben az esetben a g függvény értéke az (x, y)-ban csak az 48
f (x, y) értékétől (intenzitásától) függ és ekkor a T operátort intenzitás-transzformációnak nevezik. A MATLAB IPT toolboxban legegyszerűbb intenzitás függvényként megtalálható az imadjust függvény, aminek a szintaktikája: g=imadjust(f,[low_in high_in],[low_out high_out],gamma) A leképezés az f függvény értékeit változtaja a fent jelzett határok között, a γ nagyságától függően átskálázza az intenzitásokat.
Ha γ < 1, a leképezés eredménye a magasabb (világosabb) kimeneti értékekre súlyozódik. γ = 1, a leképezés lineáris. γ > 1, a leképezés eredménye a alacsonyabb (sötétebb) kimeneti értékekre súlyozódik. A képen látható, hogy ez egyfajta exponenciális transzformáció, ahol a γ érték meghatározása leggyakrabban tapasztalati úton történik, bár létezik rá numerikus számítás, ami meglehetősen bonyolult. A korábbi egyszerűbb példából kiindulva, nagyobb környezetet és T leképezést véve definiálható a szűrés folyamata: 1. Az (x, y) középpont kiválasztása. 2. Az operátor "ráeresztése" az (x, y) pontra. 49
3. A leképezés értékének beillesztése az eredménykép megfelelő pontjába. 4. Az eljárás megismétlése az eredeti kép minden egyes pontjára. A szűrés folyamata során valamely információk hatásai csökkenthetőek, kiemelhetőek, megszüntethetőek. A digitalizált képek gyakran "zajosak", azaz számunkra nem kívánatos, zavaró információt tartalmaznak. A zaj adódhat a rossz mintavételből, vagy akár a kedvezőtlen képelőállítási körülményekből (pl.: ködben, sötétben való fényképezés, kamera lencséjének piszkossága). Ezen zajok csökkentésére irányul a zajszűrés mechanizmusa, ami történhet az eredeti képtérben és a frekvenciatartományban is. A szűrő (filter, mask) felfogható egy M × N méretű mátrixként, ahol a méret egyben jelzi a kiválasztott középpontra szimmetrikus szomszédok számát, ezeket fogjuk figyelembe venni a számítások során. A szűrés tulajdonképpen súlyozott összegként kapható (a súly a képpontot fedő mátrix-együttható). Ez (2M + 1) × (2N + 1) méretű mátrix esetén: g(x, y) =
M N X X
f (x + i, y + j)tij
i=−M j=−N
képlettel határozható meg, ahol T = tij a konvolúciós mátrixelem, f (x, y) az eredeti kép. Ha a T szűrőoperátor lineáris, akkor a folyamatot lineáris szűrésnek hívjuk. Tehát az eljárás során egy pixel értékét helyettesítjük a szűrőmátrixnak (képpont környezetétől függ!) és a képpont konvolúciójából kapott számmal. (Még szokták használni a korreláció műveletét is, amikor a szűrőmátrix elforgatottját alkalmazzák.) A konvolúció során a szűrőmátrixot a képre illesztjük, majd a mátrix középpontja által fedett pixel értékét helyettesítjük az egymást fedő elemek szorzatának összegével. Ezután eggyel további képpontra lépünk és iteráljuk az előző lépést. Már korábban is láttunk példát szűrésre mégpedig az egydimenziós esetben, amikor az f (x) függvény N. részletösszegét, N. Fejérközepét a Dirichlet ill. Fejér-maggal konvolváltuk meg: 1 SN (x) = 2π
Z
π
1 σN (x) = 2π
Z
π
DN (u)f (u + x)du
−π
ahol DN a Dirichlet-mag, KN (u)f (u + x)du
−π
ahol KN a Fejér-mag. Ekkor a Fejér-mag bizonyult jobb szűrőmaszknak, hiszen a tesztfüggvényt határétékben a σN (x) egyenletes konvergencia pontossággal közelítette meg. Felmerülhet a kérdés, hogy a szűrőmaszk illesztése során mi történik a kép szélein elhelyezkedő pontokkal, hisz lesznek 50
"lelógó" sorok, amik nem fedik a kép szélein levő elemeket. Ennek a problémának a megoldására több lehetőség közül választhatunk: Csak az érvényes területtel számolunk, azaz az eredeti képhez képest kisebb képet kapunk ("körbenyírjuk"). Kiegészítjük megfelelő számú nullával a transzformálandó képet. Ennek hátránya, hogy nullák kerülnek a súlyozott összegbe a széleken, és így a világos képszél sötétedik. A kép széleit tükrözzük oly módon, hogy a megnövelt kép érvényes területe megegyezzen az eredeti kép méretével. A képfokozó-javító eljárásokat a javítandó hiba típusa szerint osztályokba lehet sorolni: élkiemelő (ott keres éleket, ahol a világos és sötét területek érintkeznek), zajelnyomó (zajszűrés, simítás, mikoris a zavaró hatásokat csökkentik, eltüntetik a képről), kontrasztfokozó (fokozás, csökkentés). A konvolúciós mátrixban levő elemek határozzák meg, hogy a konvolúció során zajszűrés vagy élkiemelő folyamat megy-e végbe. A MATLAB által kínált leggyakrabban használt lineáris szűrők: average, disk, gaussian, laplacian, log, sobel, melyekről részletes leírás a Helpben található.
6.3.
Szűrés a frekvenciatartományban
Ebben a szakaszban a frekvenciatartományban a két dimenziós diszkrét Fourier-transzformált segítségével szűrjük ki a zajokat a "javítandó" képről. A lineáris szűrökkel együtt használjuk a DFT-t, ami számos megoldási lehetőséget fog nyújtani a szűrési folyamatokra akár olyan területeken is, mint a képminőség fokozása, helyreállítása, adatainak tömörítése. 6.3.1. Definíció. Legyen f (x, y) egy M × N méretű képet meghatározó függvény, ahol x = 0, 1, 2, . . . , M − 1 és y = 0, 1, 2, . . . , N − 1. Az f függvény kétdimenziós diszkrét Fourier transzformáltján (DFT) értjük a következő F (u, v) (diszkrét Fourier együtthatók) függvényt F (u, v) =
M −1 N −1 X X
f (x, y)e−i2π(ux/M +vy/N )
x=0 y=0
ahol u = 0, 1, 2, . . . , M − 1 és v = 0, 1, 2, . . . , N − 1. 51
(6.2)
A frekvenciatartomány nem más mint az F (u, v) értékei, ahol az u-t és v-t frekvencia változóknak nevezzük. Ezen téglalap alakú tartományon kívül a függvényt mindkét koordináta irányában periodikusnak feltételezzük, annak ellenére, hogy szemléletesen csak egy M × N méretű periódussal végzünk számításokat. 6.3.2. Tétel. Az f függvény inverz diszkrét Fourier transzformáltja: M −1 N −1 1 X X f (x, y) = F (u, v)ei2π(ux/M +vy/N ) M N u=0 v=0
(6.3)
ahol x = 0, 1, 2, . . . , M −1 és y = 0, 1, 2, . . . , N −1 és F (u, v) a diszkrét Fourier együtthatók. Bizonyítás. Bontsuk szét az exponenciális függvény hatványkitevőjét: f (x, y) =
M −1 N −1 i 1 Xh1 X F (u, v)ei2πvy/N ei2πux/M . M N u=0
v=0
Ez megegyezik két egymásutáni egy dimenziós transzformáció elvégzésével, mégpedig úgy, hogy először az oszlopokra alkalmazzuk az 1D diszkrét inverz Fourier-transzformációt és a visszatranszformált oszlopokból álló kép sorait transzformáljuk ismét az 1D diszkrét inverz Fourier-transzformálttal. A fenti formulákat használva a Fourier-transzformált számolási igénye meglehetősen nagy lehet. Ennek megoldására dolgozták ki a gyors Fourier-transzformációt (FFT), amiben az együtthatókat rekurzív módon számítjuk, ennek köszönhetően sokkal gyorsabb algoritmust szolgáltat. A mátrixok indexeléséhez alkalmazkodva az origót az előző szakaszhoz hasonlóan eggyel eltoljuk f (0, 0) = f(1,1) és F (0, 0) = F(1,1), ahol f, F a matematikai mennyiségek, f,F pedig a MATLAB-beli megjelenítésük. Ha az f (x, y) valós, akkor a Fourier-transzformáltja komlex értékű függvény, ezért a transzformáció Fourier-spektruma (F (u, v) nagysága) így kapható: |F (u, v)| =
p
Re2 (u, v) + Im2 (u, v)
A komplex szám szöge pedig: Φ(u, v) = tan−1
h Im(u, v) i Re(u, v)
Néhány tulajdonsága a diszkrét Fourier-együtthatóknak: 1. Ha az f (x, y) valós, akkor az ő Fourier-transzformáltja konjugáltan szimmetrikus az origóra: F (u, v) = F ∗ (−u, −v) 52
2. Az előző következménye, hogy a Fourier-spektrum is szimmetrikus az origóra: |F (u, v)| = |F (−u, −v)| 3. A DFT végtelenül periodikus az u és v irányában M és N periódussal: F (u, v) = F (u + M, v) = F (u, v + N ) = F (u + M, v + N ) 4. Az inverz DFT is örökli a tulajdonságot: f (x, y) = f (x + M, y) = f (x, y + N ) = f (x + M, y + N ) Az alkalmazások során szokás a DFT-t (M/2, N/2)-vel eltolni, azért hogy a transzformáció a (M/2, N/2) pontra legyen középpontosan szimmetrikus, azaz a legnagyobb abszolút értékű elemek (ezeknek legnagyobb a frekvenciája) kerüljenek a kép középpontjába. Ha átléptünk a frekvencia tartományba, akkor a Fourier-együtthatók jellemzik ebben a térben az eredeti függvényt. A képet manipuláló eljárások azon alapulnak, hogy a transzformált függvény egyetlen elemének módosítása az inverz transzformáció elvégzése után kihat a kép egészére. A zajok a világosságkódoknál abból adódtak, ha azok nagysága hirtelen, ugrásszerűen változott, ezért ezek csökkentésére, megszüntetésére úgy nyílik lehetőség a frekvencia tartományban, ha a jelentős eltérést okozó rövidebb hullámhosszú (magasabb frekvenciájú) ek2π(ux/M +vy/N ) bázisfüggvények együtthatóit valamilyen mértékben megváltoztatjuk. Az f függvény visszanyerése folytán például a 0-ra cserélt F (u, v) együtthatókhoz tartozó bázisfüggvények eltűnnek. Ezzel szemben, ha az alacsony frekvenciájú (nagy objektumokat) együtthatókat tartjuk meg és a magas frekvenciájú, rövidebb hullámhosszhoz tartozóakat hagyjuk el, akkor pl. egy éles képen az objektumok sarkait erősíthetjük meg. Ezért az előbbit alul- az utóbbit pedig felüláteresztő szűrőeljárásnak nevezik.Az együtthatók ilyen változtatásával elérhetjük, hogy az általunk célul kitűzött képet elnyerhessük. Hogy az inverz DFT sorfejtésben mik az új együtthatók, arra a konvolúciós tétel adja a választ: 6.3.3. Tétel (Konvolúciós tétel). Legyen az eredeti képtartományban f (x, y) a képet leíró függvény és h(x, y) tetszőlegesen válaszott lineáris szűrő. Ekkor f (x, y) ∗ h(x, y) ⇔ H(u, v)F (u, v) ahol ∗ szimbólum a konvolúció műveletet jelöli, F (x, y) az f , H(x, y) pedig a h függvény diszkrét Fourier-transzformáltja.
53
A tétel sugallja, hogy a frekvenciatartománybeli szűrés úgy történik, hogy előállítjuk a képnek és valamely adott vagy generált lineáris szűrőnek a Fourier-transzformáltját, amiket összeszorzunk, majd a kapott mátrixszal képezzük a bázisfüggvények sorfejtését. A módosított Fourier-együtthatók: G(u, v) = H(u, v)F (u, v) A javított kép előállítása: f (x, y) =
M −1 N −1 1 X X G(u, v)ek2π(ux/M +vy/N ) MN u=0 v=0
Műveletvégrehajtás szempontjából soknak tűnhet a három Fourier-transzformált (szűrő-, kép-, majd invertálás) kiszámítása, de ez csak a látszat. A képtérben való konvolválás esetén a maszkméret függvényében négyzetesen nő a műveletigény. Viszont az FFT használatával a frekvenciatérben két mátrix összeszorzása, majd visszatranszformálása nagyságrendekkel kevesebb művelettel számítható ki.
6.4.
Alkalmazás
Ahhoz, hogy szemléltessük a képtartománybeli szűrést, kiválasztottuk a következő sejtekkel teli színes képet.
6.1. ábra. Egy sejtekkel teli színes kép
54
A sejtmagot ún. kolloid rendszer (nagy súrlódású, felületi feszültségű és rugalmasságú) sejtplazma, ill. egy féligáteresztő hártya, a külső membrán vagy sejthártya építi fel. Célunk ebben az alfejezetben az, hogy a fentebbi képet a képfeldolgozási módszerek közül a zajszűrés használatával leválasszuk a sejtmag körüli részeket, melyek számunkra feleslegesek és minél jobban láthatóvá tegyük a sejtmagokat, melyeket vegyész kutatók később meg tudnak számolni. Először is a képet szürkeárnyalatúvá transzformáltam, hiszen a színek az ábrában a sejtmagok leszámlálásában nem játszik szerepet, könnyebb feldolgozást tesz lehetővé a monokróm megjelenítés. A képtartományban a lineáris szűrők közül a átlagoló (average), körformában "átlagoló" (disk) ill. a Gauss aluláteresztő maszkot használtam. Average szûrõ n=5
Disk szûrõ r=2
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0 1
0 1 0.5
1
0.5
0.5
0
1 0.5
0
0 −0.5 −1
F
y
0 −0.5
−0.5 −1
−0.5 −1
F
Fx
y
−1
Fx
6.2. ábra. Az 5 × 5-s méretű average és disk szűrő A két szűrőmátrix:
1 1 1 1 1
1 1 1 1 A = 25 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0
2
5
2
0
2 10 10 10 2 1 D = 126 5 10 10 10 5 2 10 10 10 2 0 2 5 2 0
ahol A jelöli az average, D jelöli az 5 × 5 méretű mátrixegyütthatókat. A zajcsökkentő operátorok tulajdonsága, hogy az elemeinek az összege 1, különben a kép világossága eltolódna. Az average szűrő alkalmazásakor átlagos intenzitást számolunk, ezáltal mindegyik pontot ugyanolyan súllyal vesszük figyelembe. Nagy méretű mátrix esetén 55
6.3. ábra. Képtartományban szűrés 3 × 3-s méretű average ill. disk szűrővel előfordulhat, hogy a p pixel az eredetitől nagyon eltérő értéket vehet fel, mégha az nem is volt zaj. Az átlagolás hátránya, hogy elmossa az éleket és nem veszi figyelembe, hogy a kiválasztott p pontra illesztett n×n-s környezet elemei milyen távol vannak a p képponttól. Ezért ennél jobb megoldást nyújt a disk lineáris szűrő, mert ott a kijelölt pixel szomszédai a p-től távolodva egyre kisebb mértékben (kisebb súllyal) változtatják meg a p értékét. A diskkel hasonló tulajdonsággal rendelkezik a Gauss-szűrő is, ahol a súlyozás a pixeltől egyre messzebb exponenciálisan csökken. 0.4
1
0.8
G(u,v)
0.6 0.2
0.4
0.2
0 1 0.5
1 0.5
0 0 −0.5 0 −4
−2
0
2
4
Gv
−0.5 −1
−1
G
u
6.4. ábra. A Gauss (normális) eloszlásfüggvény egy és kétdimenzióban
56
Az 5 × 5-s méretű Gauss-szűrő mátrixa:
1
4
7
4
1
4 16 26 16 4 1 G= 7 26 41 26 7 273 4 16 26 16 4 1 4 7 4 1 A normális eloszlás eloszlásfüggvénye 0 várható érték esetén egy és két dimenzióban:
x2 1 e− 2σ2 2πσ 1 − u2 +v2 2 G(u, v) = e 2σ 2πσ 2
G(u) = √
ahol σ jelöli a szórást.
6.5. ábra. Képtartományban szűrés 5 × 5-s méretű Gauss szűrővel szigma=1 ill. szigma=25 szórással Ennek előnye, hogy figyelembe veszi a szomszédok közelségét lágyítva ezzel a képet, viszont homályosító hatása is van, azaz az élek is simulnak. Az intenzitásegyenletlenségek kiküszöbölésére a legegyszerűbb leképezés a gamma transzformáció volt, ami bizonyos határokon belül átskálázza a világosságértékeket (6.6 ábra). Ezzel jutottunk eddig a legközelebb a célunkhoz, hogy a sejtmagok minél jobban elkülönüljenek, bár sok szemcse maradt 57
6.6. ábra. Az eredeti kép és az imadjust(f,[0 0.4],[0 1],40) a képen. Ezért kevés csak a szűrés vagy a gamma operátor használata. Lássuk mi adódik abból, amikor használjuk az average vagy disk szűrőt, majd a már transzformált képeket, ami kevesebb zajt tartalmaz, transzformáljuk tovább. A különbség szemmel látható.
6.7. ábra. Képtartományban szűrés 3x3-s méretű average ill. disk szűrővel és imadjust(f,[0 0.4],[0 1],40)
58
Az ötletet tovább fokozva nyertem a legjobb képet a probléma megoldására. Először alkalmaztam a disk szűrőt, amivel koncentráltabbá tettem a sejtmagokat, majd átlagoló szűrővel csökkentettem a zajokat, és végül a gamma leképezéssel kihangsúlyoztam az eredetileg is sötét színű sejtmagokat.
6.8.
ábra.
Képtartományban
szűrés
imadjust(f,[0 0.4],[0 1],40)
59
disk,
majd
average
szűrővel
és
Köszönetnyilvánítás Szeretném megköszönni konzulensemnek, Tóth Árpádnak, a diploma írása során tett értékes észrevételeit, ösztönzését, biztatását, amivel mindig új lendületet adott a felmerülő kérdések átgondolására és megoldására. Szeretném megköszönni szüleimnek az egyetemi évek alatt nyújtott támogatásukat. És nem utolsó sorban köszönettel tartozom bátyámnak, aki mindig mellettem állt és önzetlenül bátorított.
60
Függelék Az Lp , lp terek 6.4.1. Definíció. Legyen Ω ⊂ Rn Lebesgue-értelemben mérhető halmaz, Ω 6= ∅, és 1 ≤ p < ∞ ill. p = ∞. Tekintsük azokat az L-mérhető Ω → C függvényeket, melyekre a, ha 1 ≤ p < ∞ :
R
Ω
|f |p dλ < ∞
b, ha p = ∞ : ess supΩ |f | := inf {supΩ\N |f | : N ⊂ Ω Lebesgue-nullmértékű} < ∞ Az Lp (Ω) a fenti függvényekből áll, ha azonosítjuk a Lebesgue majdnem mindenütt egyenlő függvényeket egymással. Pontosabban, ekvivalencia-relációval fogalmazva: f ∼ g, ha f = g m.m., és az Lp (Ω) tér a fenti függvényhalmaz ekvivalencia-osztályaiból áll.
6.4.2. Definíció. Az Lp (Ω)-n értelmezett indukált normák legyenek a következők R 1 kf kLp := ( Ω |f |p dλ) p
a, 1 ≤ p < ∞ : b, p = ∞ :
kf kL∞ := ess supΩ |f |
6.4.3. Definíció. Ha s > r és Ω ⊂ Rn korlátos, akkor 1. a terek fordítottan tartalmazzák egymást, azaz Ls (Ω) ⊂ Lr (Ω), 2. az Ls -norma "‘erősebb"’, azaz ∃c > 0 : ∀f ∈ Ls (Ω) kf kLr ≤ c kf kLs . 6.4.4. Definíció. A lp tér elemei konvergens, ill. korlátos sorozatok, azaz a, ha 1 ≤ p < ∞:
lp := {x : N → C sorozatok, melyre kxklp := (
∞ X
n=1
b, ha p = ∞:
1
|xn |p ) p
l∞ := {x : N → C korlátos sorozatok} kxkl∞ := supn |xn |
61
P∞
p n=1 , |xn |
< ∞}
n=1
n=2
1
2
0
0
−1 0
1/2 n=3
−2 0
1
2
2
0
0
−2 0
−2 0
1/4
2/4 n=5
3/4
1
2
2
0
0
−2 0
−2 0
1/8 2/8 3/8 4/8 5/8 6/8 7/8 1 n=7
2
5
0
0
−2 0
1/4
2/4 n=4
3/4
1
1/8 2/8 3/8 4/8 5/8 6/8 7/8 1 n=6
1/8 2/8 3/8 4/8 5/8 6/8 7/8 1 n=8
−5 0 1/162/16 4/16 6/16 8/16 10/16 12/16 14/16 1
1/8 2/8 3/8 4/8 5/8 6/8 7/8 1
6.9. ábra. Haar-függvények 62
Irodalomjegyzék [1] Stoyan Gisbert: Matlab 4. és 5. verzió, Typotex kiadó 1998. [2] Albert Bogges-Francis J. Narcowich: A First Course in Wavelets with Fourier Analysis, Prentice Hall 2001. [3] David F. Walnut: An Introduction to wavelet Analysis, Birkhäuser Boston 2001. [4] Wikipédia, http://hu.wikipedia.org/wiki/A Fourier-sorok története [5] Nagy László: A Fourier-analízis elmélete és gyakorlata, PHD tézis 2007. [6] Rafael C. Gonzalez-Richard E. Woods-Steven L. Eddings: Digital Image Processing using MATLAB, Prentice Hall 2004. [7] T. W. Körner: A First Look at Fourier Analysis, Jegyzet 2003. [8] Kovács György: A képfeldolgozás matematikája, Debreceni Egyetem gyakorlati jegyzet 2009. [9] Székely Gergely: Digitális Képfeldolgozás, Pécs Szakdolgozat 2000. [10] Schipp Ferenc: Fourier-analízis, ELTE egyetemi jegyzet 2006. [11] Laczkovich Miklós-T. Sós Vera: Analízis I.
63