Informatika | Információelmélet » Nemoda Balázs - Fraktál alapú képtömörítések

NEMODA BALÁZS FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉSEK KKMF MŰSZAKI INFORMATIKA SZAK DIP MODUL BELSÔ KONZULENS DR. CSINK LÁSZLÓ 1997 5 TARTALOMJEGYZÉK 1. BEVEZETÉS 8 2. MATEMATIKAI MODELLEK ALKOTÁSA A VALÓS VILÁG KÉPEIRŐL 10 2.1 A VALÓS VILÁG KÉPEINEK LEÍRÁSA ÉS TULAJDONSÁGAIK 10 2.2 A VALÓS VILÁG KÉPEINEK MATEMATIKAI MODELLJEI12 3. MATEMATIKAI ALAPOK A FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉSEKHEZ I 17 3.1 TEREK, LEKÉPZÉSEK ÉS TRANSZFORMÁCIÓK 17 3.2 AFFIN TRANSZFORMÁCIÓK 18 3.21 Affin transzformációk R-en 18 3.22 Affin transzformációk az Euklideszi síkon 18 3.23 Affin transzformációk három dimenziós valós térben 21 3.3 A METRIKUS TEREK ÉS TRANSZFORMÁCIÓK TOPOLÓGIKUS TULAJDONSÁGAI 22 3.4 A KONTRAKCIÓS LEKÉPZÉS TÉTELE – KULCS A FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉSHEZ 24 4. FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS I: IFS FRAKTÁLOK 27 4.1 A KÉPEK TERE – A HAUSDORFF TÉR H 27 4.2 KONTRAKCIÓS LEKÉPZÉSEK A H TÉREN 28 4.3 ITERÁLT FÜGGVÉNY

RENDSZEREK 30 2 4.4 AZ R -EN AFFIN TRANSZFORMÁCIÓKBÓL KÉSZÜLT ITERÁLT FÜGGVÉNY RENDSZEREK 31 4.5 AZ IFS ATTRAKTOROK SZÁMÍTÁSÁRA SZOLGÁLÓ MÁSOLÓGÉP ALGORITMUS 32 4.6 A KOLLÁZS TÉTEL 34 4.7 FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS IFS FRAKTÁLOK FELHASZNÁLÁSÁVAL 35 4.8 SZÜRKEÁRNYALATÚ MÁSOLÓGÉP ALGORITMUS 38 5. FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS II: A FRAKTÁL TRANSZFORMÁCIÓ40 5.1 A FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS MÓDSZERÉNEK ÁLTALÁNOS LEÍRÁSA40 5.2 HELYI ITERÁLT FÜGGVÉNY RENDSZEREK 42 5.3 A KOLLÁZS TÉTEL HELYI IFS-EKRE 44 5.4 HELYI IFS-EK BINÁRIS ATTRAKTORAINAK SZÁMÍTÁSA A MENEKÜLÉSI IDŐ ALGORITMUS FELHASZNÁLÁSÁVAL . 46 5.5 A FEKETE-FEHÉR FRAKTÁL TRANSZFORMÁCIÓ 47 5.6 A SZÜRKEÁRNYALATÚ FRAKTÁL TRANSZFORMÁCIÓ 49 5.7 A FRAKTÁL TRANSZFORMÁCIÓ OPERÁTORHOZ RENDELHETŐ HELYI IFS 50 6. GYAKORLATI MEGVALÓSÍTÁS 51 6.1 EGYSZERŰ AUTOMATIKUS FRAKTÁL TRANSZFORMÁCIÓ 51 6.2 FRAKTÁL KÉPKÓDOLÓ RENDSZER TERVEZÉSÉNEK KÉRDÉSEI 53

6.21 A kép felbontásának képfüggő módjai 54 6.22 Az összehasonlítandó képrészletek távolságának mérése54 6.23 Felhasználható kontraktív transzformációk tere 54 6.3 AZ EGYES TÉNYEZŐK HATÁSA A TÖMÖRÍTÉSI FOLYAMATRA 55 7. SZAKIRODALOM 57 8. SZÓMAGYARÁZAT 59 5 Összefoglaló Jelen szakdolgozat egy újfajta – a jelenleg legelterjedtebb JPEG formátumhoz hasonló –, veszteséges képtárolási módszer a fraktál alapú képtömörítés bemutatását tűzte ki céljául. Barnsley és Hurd : Fractal Image Compression c. művére támaszkodva részletesen ismerteti a módszer alapjául szolgáló matematikai elméleteket, tételeket. Vázolja a módszer gyakorlati megvalósításának egy egyszerű módját kitérve az egyes részletek végeredményt befolyásoló hatásaira is. Végül a lemezmellékleten megtalálható kereskedelmi programot vizsgálva összehasonlító elemzését adja az itt tárgyalt módszer és a JPEG formátum által

elérhető eredményeknek. Abstract The subject of this thesis is to introduce a new method of storing images – similarly to the currently most well known format, the JPEG – in a lossy way, the method of fractal image compression. Relying upon Barnsley and Hurd’s : Fractal Image Compression it discusses the mathematical theories and theorems in details serving the basis of the method. It outlines a simply way of the practical implementation, mentioning the influence of parts to the result. Finally it gives a comparative analysis of results of the presented method and JPEG by examining the commercial programme, that can be found on the enclosed disk. 5 1. BEVEZETÉS Napjainkra a számítógépek felhasználásának egyre több olyan módja alakul ki, melyre első modelljeik megépítésekor még nem gondoltak. Ezek közül egyik legjelentősebb a képi információk megjelenítése, feldolgozása. A növekvő igényeket egyre nagyobb teljesítményű perifériák (monitorok,

nyomtatók, szkennerek) szolgálják ki. Az így létrejövő hatalmas mennyiségű adatot azonban még a szintén gyors ütemben fejlődő tároló rendszerek (lemezek, winchesterek, CD-k) sem lennének képesek eltárolni eredeti formában. Manapság, a multimédia és a hálózatok világában, az adatok tárolásán túl továbbításuk sebessége is fontos tényezővé vált. Mindkét területen nagy mennyiségű álló-, sőt egyre gyakrabban mozgóképi adatforgalmat kell lebonyolítani szoros idő és erőforrás korlátok között. Nyilvánvalóan szükségessé vált az adatok tömörítése ahhoz, hogy mindezen feltételeknek a lehető legjobban eleget tudjunk tenni. Kezdetekben a képek felbontása és ábrázolható színmélység kisebb volt, így a képeket modellező digitális adatmennyiség is. Tárolásukkor különböző aritmetikai, logikai módszerekre épülő, de veszteségmentes tömörítési eljárásokat alkalmaztak – a kitömörítés után kapott kép

bitre megegyezik az eredetivel. Azonban ezek sem feleltek meg minden igénynek, ezt a több tucat elterjedt képformátum bizonyítja. Ezen módszerek, fejlődésük ellenére általában csak kis tömörítési arányok elérésére voltak képesek, s így az egyre nagyobb felbontású, színmélységű perifériák által szolgáltatott növekvő mennyiségű adat feldolgozására egyre kevésbé voltak alkalmasak. Új módszerekre lett szükség. Az új módszerek legtöbbje veszteséges adattömörítést valósít meg. A tömörítendő képet valamilyen módszer szerint közelítik, csökkentik a digitális adatsorban előforduló jelek kombinációinak számát, így a hagyományos módszerekkel jobban tömöríthető adatsort állítanak elő. Az ily módon tömörített adatokból visszaállított kép azonban nyilván nem fog teljes mértékben megegyezni az eredetivel. Az egyik ilyen megoldást a manapság legelterjedtebb formátum, a JPEG kínálja. Az általa használt

diszkrét koszinusz transzformáció (DCT) tömörítési algoritmusa a kép színeinek frekvencia értékeinek vizsgálatára alapoz. A nagyon magas – az emberi szem által kevésbé érzékelhető – frekvencia értékeket szűri ki. Ilyen értékek leggyakrabban az alakzatok éleinél fordulnak elő, a kiszűrt pixeleket a környezetükben lévő alacsonyabb frekvenciájú pixel értékekkel helyettesíti. Így már nagyobb tömörítési arányok is elérhetőek, de ennek a módszernek is akadnak hátrányai : • a tömörítendő kép méretének növekedése a tömörített kép minőségének romlásával vagy a tömörített méret növekedésével jár, 5 • az így kapott kép felbontásfüggő, ha az eredetinél nagyobb felbontásban jelenítjük meg, a képen – a pixelek sokszorozásból származó – szögletesedés figyelhető meg. Szakdolgozatomban egy másik, jelenleg még kevésbé elterjedt, de sok sikerrel kecsegtető módszer ismertetésére

vállalkozom. A fraktál alapú képtömörítés a JPEGhez hasonlóan veszteséges tömörítést valósít meg, itt azonban nem a digitális adatok tömörítése a cél. A kép egyes elemeit elemi alakazatokkal, fraktálokkal közelítik, s csak az ezeket a képeket előállító függvények együtthatóit tárolják. Az adatvesztés ebben az esetben a közelítés pontatlanságából adódik. Azonban az alkalmazott módszernek köszönhetően az eredményül kapott kép felbontásfüggetlen lesz. A kódolási felbontástól függetlenül tetszőleges felbontásban megjelenítve is folytonos képet kapunk. A módszer megértéséhez szakdolgozatom első részében összefoglalom a fraktálok és a tömörítési módszer alapjául szolgáló matematikai alapokat, majd a következőkben az erre felépülő tömörítési módszert tekintem át. Ismertetem a módszer alapjául szolgáló elméleteket, majd az automatizáláshoz szükséges feltételeket. A dolgozat lezárásaként

gyakorlati alkalmazásának lehetőségeiről, annak megvalósítási módjáról és a konzekvenciákról szólok. A dolgozat 2–5. fejezeteinek felépítése és tartalma Barnsley és Hurd : Fractal Image Compression c. művének 2–4 és 6 fejezetein alapul, a szemléltető ábrák is onnan származnak. 5 2. MATEMATIKAI MODELLEK ALKOTÁSA 2.1 A VALÓS VILÁG KÉPEIRŐL A valós világ képeinek leírása és tulajdonságaik Fraktál alapú képtömörítési módszereket felhasználva nem csak digitális képeket tömöríthetünk, hanem a valós világ képeit is ábrázolhatjuk hasonlóan tömör formában. Fontos tehát tudnunk, mi is a valós világ egy képe? Megértésének egyik egyszerű módja, ha egy – a környező világról készült – jó minőségű, élesen fókuszált pillanatfelvételként képzeljük el, ha úgy tetszik analóg adatként értelmezve. Ezekre a dolgokra fogunk az elkövetkezendőkben matematikai modelleket alkotni. A valós világ

összes képeinek halmazát ℜ-el jelöljük. ℜ egy I eleme (egy kép) a következőkben felsorolt nyolc tulajdonsággal rendelkezik. Tulajdonság I. A valós világ bármely I ∈ ℜ képe tartóval és fizikai dimenziókkal rendelkezik, az alábbiaknak megfelelően. Egy kép tartója egy  ∈ R2 halmaz, ahol R2 egy Euklideszi síkot jelöl.  a következőképpen definiált :  = {(x, y) ∈ R2, a ≤ x ≤ b, c ≤ y ≤ d }, ahol a < b és c < d valós konstansok. Itt I fizikai dimenziói (b-a) és (d-c) egységűek, az egység alatt fizikai mértékegységeket (inch, méter) értve. Ekkor azt mondjuk, hogy  az I kép tartója. Az  ∈ R2 halmaz, fizikai dimenzióival – (b-a) egység és (d-c) egység – együtt adja meg a kép fizikai kiterjedését. A fizikai dimenziók megléte a méretek és mérések alapjainak felállításhoz szükséges, hogy kapcsolatot teremthessünk ℜ és a fizikai valóság között. A valós világbeli kép  tartójának

geometriája és topológiája van. A kép tartóját az Euklideszi síkból származtatjuk. Folytonosan deformálható és a végtelenségig nyújtható a topológia és a valós analízis törvényei szerint. Tulajdonság II. Legyen I ∈ ℜ Ekkor I kromatikus 1 jellemzőkkel bír Ezt a kép részhalmazaihoz rendelt fényfrekvenciák (színek) és intenzitások biztosítják. Ezek valós értékű függvényekkel vagy a kép tartóján végzett valós értékű Borel mértékekkel modellezhetők. I tartójának minden mérhető részhalmazához rendelhető számtani jellemzők olyan együttese, amely a halmaz és a halmazhoz rendelt fényintenzitások és frekvenciák különböző átlagait írják le. A valós világ képeihez kromatikus jellemzőket rendelő matematikai modellekről a 2.2 alfejezetben lesz majd szó Itt főként ℜ általános tulajdonságainak leírásával foglalkozunk. A felbontás függőség tulajdonság illusztrálására azonban néhány példát itt is

adunk. Digitális képek kezelésekor az egyik különösen fontos lépés, amikor a kép tartóját párhuzamos egyenesek rácsozatával téglalap alakú alhalmazok tömbjére, pixelekre bontjuk. Minden pixel – maga is ℜ egy eleme – saját kromatikus jellemzőkkel bír 5 Digitális képeknél ezeket kerekített valós számok véges halmazával modellezik, például a pixelhez rendelt fényintenzitás vörös, zöld és kék (RGB) tartományainak jellemzésére. A hozzárendelés módja szerint több módszer is létezik : a már említett RGB komponensek megadása, egyszerű fekete-fehér modell vagy a fény intenzitását jelző szürkeárnyalat. Tulajdonság III. Legyen I ∈ ℜ Ekkor I felbontás függő Ez azt jelenti, hogy I bármely tetszőlegesen nagy, de véges felbontás esetén is jellemezhető. Az egyes pixelek színét és intenzitását jelző numerikus értékek megadhatóak. Nincs logikai ellentmondás ugyanazon kép két különböző felbontásban

megadott alakja között. Azonban a matematikai modellezési folyamat egy finomabb szintjére kell eljutnunk ahhoz, hogy megtudjuk, milyen módon határozhatóak meg  numerikus jellemzőinek értékei különböző felbontási szinteken. Példák a 22 alfejezetben találhatók Tulajdonság IV. A valós világ képeinek összességét alkotó ℜ halmaz zárt a vágás művelet alatt. Legyen I ∈ ℜ Jelentse I , az I tartójából választott bármely, a tartó oldalaival párhuzamos oldalú, téglalap alakú területet, mely egy újabb kép. Ekkor I ∈ℜ . A vágás művelet alatti zártság tulajdonság a valós világ képeivel kapcsolatos azon alapvető gondolatot fejezi ki, hogy a valós világ egy képe, bármily kicsi is, információt hordoz és önmaga is egy kép. Ez a tulajdonság a következővel együtt a képek matematikailag gazdag elméletének kritikus szerkezeti részeit összegzi. Legyen I ∈ ℜ. Tekintsük I -nek I egy izotropikusan 2 kinyújtott vagy

összezsugorított alakját. Ekkor I ∈ℜ ; vagyis ℜ zárt az izotropikus nyújtás és zsugorítás művelete alatt. Ez a tulajdonság valójában azt fejezi ki, hogy egy képet meg lehet nyújtani izotropikusan. A tulajdonság azonban nem adja meg a nyújtás (zsugorítás) adott képre való alkalmazásának módját; nem írja le pontosan, hogyan kell egy nyújtott kép kromatikus jellemzőit meghatározni. Ez az ℜ-re alkalmazott matematikai modelltől függ. A valós világ képeinek nyújtására a 2.2 alfejezetben találunk példákat, itt csak rövid felsorolását adjuk a lehetséges módszereknek : • nagyító lencsével, • vetítőgépekkel, • ugyanazon tárgyat más-más távolságról nézve. Tulajdonság V. Legyen I ∈ ℜ. Jelentse I I -nek egy, a tartójának oldalaival párhuzamos tengelyre vetített tükörképét. Ekkor I ∈ℜ ; vagyis ℜ zárt a tükrözés alatt Tulajdonság VI. Legyen I ∈ ℜ. Legyen I I egy kivágott és elforgatott, téglalap

alakú területének képe. Ekkor I ∈ℜ ; vagyis ℜ zárt hasonló forgatási műveletek alatt. Egy kép izotropikus zsugorítása és nyújtása példa egy kép hasonlóságára. A hasonlóság, a forgatások és tükrözések példák az affin 3 Tulajdonság VII. 5 transzformációkra, melyekről a 3. fejezetben lesz bővebben szó Az V, VI és VII tulajdonságot összefoglalhatjuk együtt a következő tulajdonságban. Tulajdonság VIII. ℜ zárt a képekből kivágott paralelogramma alakú területekre alkalmazott, tetszőlegesen invertálható affin transzformációkra, melyek téglalap alakú képeket eredményeznek. Fontos, hogy megkülönböztessük a valós világ képeit a látható tértől. A látható világ olyan matematikai modell, melyben a valós világbeli tárgyak az emberi látórendszer által felfogott és feldolgozott formában, három dimenziós térben jelennek meg. A látható tér tulajdonságainak matematikai jellemzésére tett kísérletek

mindezidáig nem jártak eredménnyel A valós világ képeinek modellezésére alkotott formulákkal ezért csak a képek jellemzésének egyszerűbb problémájára fordítunk figyelmet Úgy kezeljük őket, ahogy elménkben képzeletünk segítségével megjelennek, nem pedig az emberi látórendszer által felfogott és feldolgozott tárgyakként. 2.2 A valós világ képeinek matematikai modelljei Ahhoz, hogy a valós világ képeit a gyakorlatban is kezelni tudjuk szükséges ℜ valamilyen matematikai modelljét megalkotnunk. A következőkben ezekre mutatunk példákat. Megértésükhöz a mértékelmélet és az integrálási módszerek egy részének ismerete szükséges. Célunk itt csak az, hogy bemutassunk néhány az ℜ jellemzésre alkotható modellt, nem pedig egy teljes lista készítése. Modell I. ℜ-t ℜi-vel modellezzük, amely csak a fekete és fehér színeket használja a valós világ képeinek jellemzésére. Ilyen kép lehet például egy fax, vagy

alkonyatkor egy fa alakja az ég hátterén. ℜi bármely I elemét  tartója és Borel mértékkel 4 jellemezhető A ⊂  részhalmazának χA :  {0,1} karakterisztikus függvénye jellemezi. Az -ra “rajzolt” A halmaz fekete képet eredményez fehér háttéren. Ha “0” a fehér, “1” a fekete értéket jelöli, akkor az χA (x) függvény a következőképp definiált 1 ha x ∈ A, 0 ha x ∉ A. χA ( x) =  χA adja a kép kromatikus jellemzőit. Ebben a modellben a valós világ bármely képét teljesen megadja  tartója az A ⊂  Borel részhalmazzal együtt; és fordítva, bármely {, A ⊂  : A R2 Borel részhalmaza} definiálja ℜi egy elemét. Szükséges, hogy az A halmaz, és ennélfogva az χA :  {0,1} függvény is, Borel mértékkel jellemezhető legyen, hogy a kép mérhető részhalmazaira az integrál számítást alkalmazni tudjuk. Másfelől ez lehetővé teszi számunkra, hogy következetes módon 5

definiáljuk a kép véges felbontású közelítését, ahogy azt ℜ felbontás függőség (III.) tulajdonsága előírja. Például definiálhatjuk I -nek olyan tetszőlegesen nagy, véges felbontású, digitális közelítési modelljét, ahol a P ⊂  pixelhez az ∫P χA ( x) dx ∫ P dx hányados értéke szerint 0-t rendelünk, ha kisebb 0.5-nél vagy 1-et, ha nagyobb egyenlő 0.5 Ez, a 21 ábrán láthatókhoz hasonlóan, A véges felbontású (digitális) A közelítését eredményezi. Az A = Pm × n (A) jelölést alkalmazva, a P pixeleket  vízszintesen m, függőlegesen n elemű tömbre osztásával kapjuk. Ekkor ez a modell, egy Pm × n : ℜi ℜi leképzés, amely a valós világ egy képét önmagába viszi át.  minden A Borel részhalmazára Pm×n (Pm × n (A)) = Pm × n (A). Ekkor a {Pm × n (A); m,n = 1,2 } véges felbontású modellek konzisztensek, mert ha elkészítjük A elegendően nagy felbontású Pm´×n´ (A) digitális közelítését, hol

m´ sokkal nagyobb m-nél és n´ sokkal nagyobb n-nél, és ugyanezt a közelítést elvégezzük Pm × n (A) -ra, tehát Pm´×n´ (Pm × n (A)), akkor az eredmény megközelítőleg azonos; ha m és n értékét rögzítjük, d (Pm´×n´ (A), Pm´×n´ (Pm × n (A))) 0, ahogy m´ és n´ együttesen a végtelen felé tart. 2.1 ábra A véges felbontású A közelítése az A-ra fektetett pixel tömb segítségével Itt d az ℜi térben két – azonos tartóval rendelkező – kép összehasonlítására alkalmas mértéket jelöl, mint 5 d (A,B) = ∫χA(x) – χB(x)dx. Bármely ℜi beli, a fentiekhez hasonlóan A Borel halmazhoz rendelt, I kép nyújtása (zsugorítása) egy új H ∈ ℜi képet eredményez I  ⊂ R2 tartóját egy nagyobb (kisebb)  ⊂ R2 területre leképezve, melynek fizikai dimenziói egy s > 0 konstans aránnyal nagyobbak (kisebbek) mint -éi. A koordináták origójául a tartó bal alsó sarkát χ χ választva H

kromatikus jellemzőit az ( x) = A ( x / s) függvény alapján számíthatjuk minden x = (x,y) ∈ -re. Modell II. Ebben az esetben ℜ-t ℜii-vel modellezzük. Egy ℜii beli kép kromatikus jellemzőit a valós számok egy I, például [0,255] ⊂ R, intervallumának segítségével a lehetséges szürke-árnyalatokat jellemezve az f :  I függvénnyel ábrázoljuk. Az f (x,y) függvény a kép (x,y) pontjának intenzitását vagy fényességét adja meg. Egy f -et integrálási és / vagy folytonossági feltételeinek megadásával tovább pontosíthatjuk a modellt. Az f függvény adja meg a kép kromatikus jellemzőit ℜii -ben bármely képet pontosan megad  tartója és az f :  I függvény együtt; és fordítva, bármely f:I függvény – néhány feltétellel, például f ∈ l1() – együtt definiálja ℜii egy elemét. I ∈ ℜii tetszőlegesen nagy, de véges felbontású közelítési modelljeit állíthatjuk elő, ha minden P ∈ 

pixelhez az f ( P) = ∫P f ( x) dx ∫ P dx értéket rendeljük. ℜii bármely I képének – kromatikus jellemzői a fentieknek alapján f által adottak – nyújtása (zsugorítása) I  ⊂ R2 tartóját egy nagyobb (kisebb)  ⊂ R2 területre leképezve a H ∈ ℜii új képet eredményezi, melynek fizikai dimenziói egy s > 0 konstans aránnyal nagyobbak (kisebbek) mint -éi. H kromatikus jellemzői a g (x,y) = f (x/s,y/s) függvény alapján adódnak minden (x,y) ∈  -re. ℜii -ben az azonos tartóval rendelkező I, H képek távolságát a választott l1(), l2() vagy l ∞ () térnek megfelelő távolság függvény segítségével mérhetjük. Például definiálhatjuk a d (I,H ) = ∫ | f (x) – g (x)| dx, ahol f :  I és g :  I a két kép kromatikus függvényei. Modell III. Ez esetben ℜ-t ℜiii-vel modellezzük ℜiii egy képét  valós értékű normalizált µ Borel mértékének segítségével jellemzzük.

Az A ⊂  részhalmaz által kibocsátott fény összege 5 ∫A dµ. Ebben a modellben a kép egyetlen pontjához rendelt fény intenzitás értékét általában nem lehet megadni. ℜiii -ben bármely képet pontosan megad  tartója és µ normalizált Borel mértéke; és fordítva az -n végzett bármely Borel mérés az ∫ dµ = 1, alakra normalizálva definiálja ℜiii egy elemét. I ∈ ℜiii tetszőlegesen nagy, de véges felbontású közelítési modelljeit állíthatjuk elő, ha minden P ∈  pixelhez az f (P) ∫P dµ értéket rendeljük. ℜiii bármely I képének – kromatikus jellemzői a fentieknek alapján µ által adottak – nyújtása (zsugorítása) I,  ⊂ R2 tartóját egy nagyobb (kisebb)  ⊂ R2 területre leképezve a H ∈ ℜiii új képet eredményezi, melynek fizikai dimenziói egy s > 0 konstans aránnyal nagyobbak (kisebbek) mint -éi. H kromatikus jellemzői a ν mérés alapján számíthatók, ahol ν (B) =

µ (s-1B) minden B ⊂  Borel részhalmazra, és itt s-1 az -t -be vivő hasonlósági leképzést jelenti R2-en. ℜiii -ben az azonos tartóval rendelkező I, H képek távolságát a következőképp megadott d távolság függvény segítségével mérhetjük d (I,H ) = ∫ |dµ (x) – dν (x)|, ahol µ és ν a két képhez rendelt mérések. Modell IV. Ez esetben ℜ-t ℜiv -vel modellezzük ℜiv egy képének kromatikus jellemzőit a valós számok egy I, például [0,255] ⊂ R, intervallumának segítségével a lehetséges inztenzitásokat jelölve, és három függvénnyel fr :  I, fg :  I, fb :  I, ahol fr (x,y), fg (x,y), fb (x,y) a kép  tartójának (x,y) pontjainak vörös, zöld és kék összetevőjének intenzitását jelöli. Szükséges megadnunk ezen függvények integrálhatósági feltételeit. ℜiv -ben az azonos tartóval rendelkező I, H képek távolságát a választott l1(), 2 l () vagy l ∞ () térnek

megfelelő távolság függvény segítségével mérhetjük. Például definiálhatjuk a d (I,H ) = ∫ fr (x) – gr (x)dx + ∫fg (x) – gg (x)dx + ∫fb (x) – gb (x)dx, ahol f és g a két kép kromatikus függvényei. 5 A modell struktúrája és tárgyalása a továbbiakban az ℜii-nél leírtakhoz hasonlóan folytatódik. Sok más modell lehetséges és használható ℜ jellemzésére. Például a IV modellben jellemezhetnénk a szürkeárnyalatok inteznitását vagy a más megjelenítési rendszerekben használt Y,U,V vagy H,I,Q színességi értékeket. Használhatnánk valódi 3 dimenziós térbeli felületeket, melyek a képeket a pozíciótól függően a színkomponensek fényességével jellemeznék. A felületeket egyetlen geometriai egységként kezelve modellezhetnénk a képeket; vagy használhatnánk Borel mérést a képen belüli foton fényesség eloszlás jellemzésére, a kép minden színkomponensére. Az ℜ

modellezésének alapjául szolgáló matemetikai elem minden esetben végtelen finoman definiált jellegzetesség – a kép minden egyes részéhez, bármily kicsi és pontosan megadott, az optikai karakterisztikáit leíró számok rendeltek. Ha már megalkottuk az ℜ “képeinek” matemetikai modelljét, a következő lépés az 1-esek és 0-ák füzérére való áttérés. Szükséges, hogy matematikai “képeinket”, egyik vagy másik speciális térben lévő méréseinket vagy függvényeinket, szisztematikus módon közelíteni tudjuk; hogy az 1-esek és 0-ák véges sorozatát folyamatos és folytonos módon tudjuk összekapcsolni a végtelen képekkel. Az elemek közelítési módjainak olyan csoportjait kívánjuk bemutatni, amelyek egyrészt a képek készítéséül szolgáló matematikai tér elemi egységeit közelítik ill. modellezik, másrészt véges sok paramétertől függenek. Saját közelítési módszerüknek rendelkeznie kell karakterisztikákkal,

úgymint, a növekvő részletességű közelítés konvergenciájának aránya és a közelítés számításának komplexitásának növekedési aránya, amik megfelelőek a választott képi mértéket (távolság) és képi függvény osztályt tekintetbe véve. Mégpedig, ezeknek a közelítéséknek olyan megfelelő tulajdonságokkal kell rendelkezniük az ℜ jellemzésére választott matematikai modell(ek) képeire vonatkozóan, amelyek az általunk megszokott valós világ képeinek osztályával, és a látórendszerünk ezen képek kezelésének módszereivel a legkényelmesebb módot biztosítja. A képek közelítésére két matematikai modell osztályt választunk: (a) az IFS fraktálokat és (b) az FT fraktálokat. Mindkét közelítési osztály eleget tesz az 1-esek és 0-ák véges láncához kapcsolódó felbontás független modellek alapvető követelményeinek. Mindkét közelítési osztály konzisztens az ℜ tulajdonságaival is Különösen fontos az a

tény, hogy minden osztály felbontás független képeket biztosít, és hogy ezen képek konstans információ mennyiséggel rendelkeznek – a kivágás és nagyítás (zoomolás) nem csökkenti információ tartalmukat. 5 3. MATEMATIKAI ALAPOK A FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉSEKHEZ I 3.1 Terek, leképzések és transzformációk Ebben a fejezetben a címhez hűen a fraktál alapú képtömörítések megértéséhez szükséges alapvető matematikát foglaljuk össze. Néhány definíció, tétel bizonyosan ismert lesz már más tanulmányokból, de a teljesség és az egyértelműség kedvéért nem térek el az [1]-ben alkalmazott tematikától. Néhány definíció megadásával kezdjük. Mindenütt, ahol teret említünk, egy szerkezettel bíró halmazt értünk alatta. Térre példák az R valós vonal, az R2 Euklideszi sík, az R3 három dimenziós tér, a [0,1] egység intervallum, a  ⊂ R2 egység négyzete és a ∑ kód tér 5. Egy térnek például

metrikája 6 biztosíthatja szerkezetét Definíció Egy (X, d) metrikus tér olyan X tér vagy halmaz, melyben a d : X × X R valós értékű függvény az X beli x és y pontpár közti távolságot méri. Tegyük fel, hogy d a következő tulajdonságokkal rendelkezik: (i) (ii) (iii) (iv) d(x,y) = d(y,x), ∀ x, y ∈ X. 0 < d(x,y) < ∞, ∀ x, y ∈ X, x ≠ y. d(x,x) = 0, ∀ x ∈ X. d(x,y) ≤ d(x,z) + d(z,y), ∀ x, y, z ∈ X. Ekkor d-t a tér mértékének nevezzük. Definíció Legyen X egy tér. Egy X-en végzett transzformáció, kép vagy leképzés egy f : X X függvény. Ha S ⊂ X , akkor f (S) = {f (x) : x ∈ S} Az f függvény kölcsönösen egyértelmű leképezés, ha az x, y ∈ X -re az f(x) = f(y) -ból következik, hogy x = y. Ráképzés, ha f (X) = X. Invertálhatónak nevezzük, ha kölcsönösen egyértelmű leképezés és ráképezés; ebben az esetben definiálhatjuk az f -1 : X X transzformációt, amely f inverze, melyre f -1 (y) = x,

ahol x ∈ X az az egyedüli pont, amelyre y = f(x). Definíció Legyen f : X X egy transzformáció a téren. Az f függvény előre iteráltjai olyan f °n : X X transzformációk, amelyek az f °0 (x) = x, f °1 (x) = f (x), f °(n+1) (x) = f ° f (n) (x) = f (f (n) (x)) n = 0,1,2, . alapján definiáltak Ha f invertálható, akkor hátra iteráltjai olyan f °(-m) : X X transzformációk, amelyek az f °(-1) (x) = f -1(x), f °(-m) (x) = (f °m )-1 (x) m = 0,1,2, . alapján definiáltak 5 3.2 Affin transzformációk 3.21 Affin transzformációk R-en Az R-en értelmezett affin transzformációk a következő formában megadott f : R R transzformációk f (x) = a· x + b, ∀ x ∈ R, ahol a és b valós konstansok. Adott I = [0,1] intervallum esetén f (I) egy új |a| hosszú intervallum. Az f transzformáció a-val átméretez Az intervallum bal, 0 végpontja b-vel elmozdul, és f (I) b-től jobbra ill. balra helyezkedik el a pozitív ill negatív értékétől

függően. Az R egészén végzett affin transzformáció művelete a következőképp írható le. Az egész egyenes kinyúlik az origótól mérve, |a| > 1 esetén vagy összehúzódik felé ha |a| < 1; és 180°-ban elfordul O körül, ha a < 0. Transzlálódik, eltolódik b értéknyivel Balra tolódik, ha b < 0 és jobbra, ha b > 0. Vegyük észre, ha f : [0,1] [0,1] és g : [0,1] [0,1] affin transzformációk a [0,1] ⊂ R intervallumon, akkor az f °g is az. 3.22 Affin transzformációk az Euklideszi síkon Definíció A w : R2 R2 w (x,y) = (ax + by + e, cx + dy + f), (4.1) formában megadott transzformációt, ahol a, b, c, d, e és f valós számok, (két dimenziós) affin transzformációnak nevezzük. Használjuk a következő, azonos jelölésmódot is :  a b   c d w (x) = w   x  e    +   y  f  = Ax + T. Itt,  a b   c d A=  egy 2 × 2-es valós mátrix és a T oszlop vektor 

e    f , amit nem különböztetünk meg az (e, f) ∈ R2 koordináta pártól. Az ilyen transzformációknak fontos geometriai és algebrai tulajdonságaik vannak. Az A mátrix mindig leírható az  a b   r 1 cosθ1 − r 2 sinθ 2    =   c d   r 1 sinθ1 r 2 cosθ 2  5 formában, ahol (r1, θ1) az (a,c) pont (r2, (θ2 + r1 = π 2 )) az (b,d) pont polár koordinátái. Azaz, a 2 + c2 , θ1 = tan-1 (c/a) ha a ≠ 0, θ1 = π 2 ha a = 0 és c ≥ 0, 3π 2 θ1 = ha a = 0 és c < 0; 2 2 r2 = b + d , θ2 = tan-1 (d/b) ha b ≠ 0, θ1 = θ1 = π 2 3π 2 ha b = 0 és d ≥ 0, ha b = 0 és d < 0. Az R2 -en végzett  x    y A  x    y lineáris transzformáció bármely egy csúcsával az origóban lévő háromszöget egy másik, csúcsával az origóban lévő háromszögre képez le, ha ad – bc ≠ 0, ahogy a 3.1 ábrán látható. 3.1 ábra Az R2 beli lineáris

transzformáció illusztrációja Az R2-en értelmezett általános formájú w(x) = Ax + T affin transzformáció az A lineáris transzformációból és az azt követő T vektorral megadott transzlációból áll. Mindig található egy affin transzformáció, amely az (x1,x2), (y1,y2) és (z1,z2) csúcsokkal rendelkező háromszöget egy másik ( x 1, x 2), ( y 1, y 2) és ( z 1, z 2) csúcsú háromszögbe viszi át. A szükséges a, b, c, d, e és f együtthatókat a következő lineáris egyenletrendszer megoldásával nyerhetjük : 5 x1a + x2b + e = x 1, y1a + y2b + e = y 1, z1 a + z2 b + e = z 1 , x1c + x2d + f = x 2, y1c + y2d + f = y 2, z1 c + z2 d + f = z 2 . A w (x,y) = (ax + by + e, cx + dy + f) affin transzformáció inverze a w-1 (x,y) = (d· x – b· y – d· e + b· f , –c· x + a· y + c· e – a· f) ÷ α, affin transzformáció, ha α = (a· d, b· c) ≠ 0. A w : R2 R2 -n értelmezett w (x,y) = (x,y) -ként definiált affin transzformációt

azonossági leképzésnek nevezzük. A w : R2 R2 -n értelmezett w (x,y) = (r1x, r2y) -ként definiált speciális formájú affin transzformációt dilatációnak nevezzük. A w (x,y) = (x,–y) és w (x,y) = (–x,y) két affin transzformáció a tükrözésre példák, az első az y tengelyre, a második az x tengelyre történt tükrözést jelenti. A w (x, y) = (x + f, y + g) speciális formájú affin transzformációkat, ahol az f és g valós konstansok, transzlációnak (eltolásnak) nevezzük. A w : R2 R2 -n értelmezett affin transzformációt hasonlóságnak nevezzük, ha az alábbi speciális formák egyikeként leírható,  x  r cosθ   = y r sinθ w   − r sinθ   x  e     +  r cosθ   y  f  ,  x  r cosθ   = y r sinθ w   r sinθ   x  e     +  − r cosθ   y  f  , valamely (e, f) ∈ R2 transzlációra, valamely r ≠ 0

valós számra és valamely 0 ≤ θ ≤ 2π szögre. θ a forgatási szög, r pedig az arányossági tényező vagy lépték Az alábbi speciális formájú lineáris transzformációkat forgatásnak nevezzük  x  cosθ   = y sinθ A   − sinθ   x    cosθ   y . Az alábbi módon leírható speciális formájú lineáris transzformációkat w (x,y) = (x + by, y) vagy w (x,y) = (x, cx + y), 5 ahol b és c valós konstansok, ferdeségnek vagy nyírási transzformációnak nevezzük. Mindkét esetben rögzítve marad az egyik koordináta, mintha egy pakli kártyát elnyírnánk. Ha a w1 : R2 R2 és w2 : R2 R2 is affin transzformáció, akkor a w1 ° w2 is az. Így ötvözhetjük az affin transzformációkat, hogy újakat alkossunk Ez elvezet minket ahhoz a kérdéshez, hogy melyek azok az elemi affin transzformációk, amelyekből bármely másik affin transzformáció előállítható. A legtöbb általános affin

transzformáció felépíthető az eltolás és a lineáris transzformáció ötvözésével. A legtöbb általános lineáris transzformáció előállítható a dilatáció, a forgatás és a ferdeség egyesítésével. Legyen S R2 egy területe, melyet egy poligon vagy más “szép” körvonal határol. Legyen a w : R2 R2 egy w (x) = Ax + T affin transzformáció, a (4.1)-hez hasonlóan Az A determinánsa, det (A), a det (A) = a· d – b· c képlet alapján adott. Ekkor bizonyítható, hogy (a w (S) területe) = |det (A)|· (S területe). Ha det (A) < 0, akkor az S “megfordul” a transzformációval. 3.23 Affin transzformációk három dimenziós valós térben A legtöbb általános w : R3 R3 affin transzformáció kifejezhető mátrix formában  x a b     y =  c d  z  r s w   t u  p  x  e       y +  f   z   q  , ahol a, b, c, d, e, f, p, q, r, s,

t, u valós konstansok és (x, y, z) ∈ R3 ; azaz w (x, y, z) = (a· x + b· y + t· z + e, c· x + d· y + u· z + f, r· x + s· y + p· z + q). Ezt a transzformációt a kézenfekvő w (x) = Ax + T jelöléssel is ábrázolhatjuk. Feltéve, hogy az A mátrix determinánsa nem nulla, a transzformáció invertálható. Ez a transzformáció egy tetraédert egy másik tetraéderbe képez le. Fordítva, két tetraéder felhasználásával megadhatunk egy affin transzformációt a három dimenziós térben. Számunkra a v : R3 R3 affin transzformációk közül a következő speciális formájú különleges jelentősséggel bír v (x, y, z) = (w(x,y), pz + q), ahol w : R2 R2 egy két dimenzióbeli affin transzformáció. Bármely a z tengellyel párhuzamos egyenes darabot egy z tengellyel párhuzamos egyenes darabba visz át. Bármely a z tengelyre merőleges síkban fekvő háromszöget egy a z tengelyre merőleges síkban fekvő háromszögbe viszi át. Az ilyen transzformációk

speciális szerepet játszanak a szürkeárnyalatú fraktál transzformációkra alapuló képtömörítésben (lásd 5.6 alfejezet). 5 3.3 A metrikus terek és transzformációk topológikus tulajdonságai Itt a metrikus terek bizonyos részhalmazainak, pontsorozatainak és a rajtuk értelmezett függvények számos topológikus tulajdonságainak leírásával foglalkozunk, melyekre a következőkben szükségünk lesz majd. Az ekvivalens metrikus terek fogalmának ismertetésével kezdjük. Az ekvivalens mértékkel rendelkező metrikus tereken végzett transzformációk részhalmazaik és sorozataik sok – a következőkben ismertetésre kerülő – topológikus tulajdonságát megőrzik. Definíció Az X tér d1 és d2 mértéke ekvivalens, ha létezik olyan 0 < c1 < c2 < ∞ konstans, melyre c1d1 (x,y) ≤ d2 (x,y) ≤ c2d2 (x,y), ∀ (x, y) ∈ X × X. Definíció Az (X1, d1) és (X2, d2) metrikus terek ekvivalensek, ha létezik egy olyan h : X1 X2 függvény,

melyre az X1 -en értelmezett d 1 mérték a következőképp definiált d 1 (x,y) = d2 ( h(x), h(y) ), ∀ x, y ∈ X1 ekvivalens d1 -el. Definíció Az (X,d) metrikus térből az (Y,e) metrikus térbe vivő f : X Y függvény folytonos, ha minden ε > 0 és x ∈ X -hez létezik olyan δ > 0 melyre igaz, hogy d(x,y) < δ ⇒ e( f(x), f(y) ) < ε. ∞ n =1 pontok sorozata egy f : Z+ X függvény, ahol Z+ a Definíció Az X térbeli {xn} pozitív egész számok halmazát jelöli, és f (n) = xn minden n ∈ Z+ -ra. A pozitív egészek ∞ i =1 {ni} sorozata egy sorrendtartó g : Z+ Z+ függvény, melyre g (i) = ni minden i ∈ Z+ -ra. Azt mondjuk, g : Z+ Z+ sorrendtartó, ha rendelkezik az “m < n ⇒ g(m) < g(n), ∞ i =1 ∀ m, n ∈ Z+.” tulajdonsággal Az {xni} részsorozat egy f °g : Z+ X formájú függvény, f és g a fentiekben leírtakkal egyezik, ahol xni az f (g(i)) pontot jelöli. ∞ n =1 Definíció Az (X,d) metrikus térbeli pontok egy

{xn} sorozatát Cauchy sorozatnak nevezzük, ha bármely ε > 0 számhoz létezik egy olyan N > 0 egész szám, melyre d(xn, xm) < ε minden n, m > N-re. ∞ n =1 Definíció Az (X,d) metrikus térbeli pontok egy {xn} sorozata az x ∈ X ponthoz konvergál, ha bármely ε > 0 számhoz létezik egy olyan N > 0 egész szám, melyre 5 d(xn, x) < ε minden n > N-re. Ilyen esetben a sorozatot konvergensnek nevezzük. Az x ∈ X pontot, amihez a sorozat konvergál, a sorozat határértékének nevezzük, és a következő jelölést alkalmazzuk : x = limn∞ xn. ∞ Tétel Ha az (X,d) metrikus térbeli pontok egy {xn} n =1 sorozata egy x ∈ X ponthoz ∞ konvergál, akkor az {xn} n =1 sorozat egy Cauchy sorozat. ∞ Definíció Egy (X, d) metrikus tér teljes, ha X minden {xn} rendelkezik egy x ∈ X határértékkel. Definíció n =1 Cauchy sorozata Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. Az x ∈ X pontot S ∞ határpontjának

nevezzük, ha létezik a pontoknak egy olyan {xn} melyre limn∞ xn = x. n =1 sorozata, xn ∈ S {x}, Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. Ekkor S S -vel jelölt lezárását a következőképp definiáljuk S = S ∪ { S határpontjai }. Definíció S zárt, ha tartalmazza összes határpontját; azaz, S = S . Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. S nyílt, ha minden x ∈ S-re létezik egy ε > 0 melyre B (x,ε) = { y ∈ X : d(x,y) ≤ ε } ⊂ S. Ez a definíció ekvivalens a következővel : S nyílt, ha nem zárt. Definíció S tökéletes, ha egyenlő határpontjainak halmazával. Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. S kompakt, ha S ∞ n =1 minden {xn} részsorozatot. végtelen sorozata tartalmaz egy S-en belüli határértékkel rendelkező Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. S rögzített, ha létezik egy a ∈ X pont és egy R > 0 szám,

melyekre d(a,x) < R, ∀ x ∈ S-re. Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. S teljesen rögzített, ha minden ε > 0 -hoz létezik pontoknak olyan véges {y1, y2, , yn } ⊂ S halmaza, hogy bármely x ∈ S-re d(x,yi) < ε valamely yi ∈ {y1, y2, , yn } esetén. 5 Tétel Legyen (X,d) egy teljes metrikus tér. Legyen S ⊂ X Ekkor S akkor és csak akkor kompakt, ha zárt és teljesen rögzített. Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. Az x ∈ X S egy körvonali pontja, ha bármely ε > 0 esetén B (x,ε) tartalmaz egy pontot X S-ből és egy pontot S-ből is. Definíció jelöljük. S összes körvonali pontjának halmazát S körvonalának nevezzük, és ∂S -el Definíció Legyen S ⊂ X az (X,d) metrikus tér egy részhalmaza. Az x ∈ S pontot S egy belső pontjának nevezzük, ha létezik olyan ε > 0 szám, melyre B (x,ε) ⊂ S. Definíció S belső pontjainak halmazát S belsejének nevezzük,

S0-val jelöljük. Definíció Az (X,d) metrikus tér összefüggő, ha csak két olyan részhalmaza létezik, melyek egyszerre nyíltak és zártak, és ezek X és ∅. Egy S ⊂ X részhalmaz csak akkor összefüggő, ha az (S,d) metrikus tér is összefüggő. Definíció S szétválasztott, ha nem összefüggő. Definíció S teljesen szétválasztott feltéve, hogy S egyedüli nem üres részhalmazai egyetlen pontot tartalmazó részhalmazok. 3.4 A kontrakciós 7 leképzés tétele – kulcs a fraktál alapú képtömörítéshez Definíció Legyen f : X X egy transzformáció a téren. Azon xf ∈ X pont, melyre f (xf) = xf , a transzformáció fix pontjának hívjuk. A 3.2 ábra egy affin transzformáció fix pontját ábrázolja 5 3.2 ábra Ez az ábra egy affin transzformáció (xf ,yf ) = w (xf ,yf ) fix pontját ábrázolja A kód téren értelmezett T : ∑ ∑ transzformáció a következőképp definiált T(σ1σ2σ3σ4σ5) = σ2σ3σ4σ5σ6 és eltolás

operátornak nevezzük. A T°n transzformáció, bármely n ∈{0, 1, 2, 3, }-re a következők szerint viselkedik T°n (σ1σ2σ3σ4σ5) = σn+1σn+2σn+3σn+4σn+5 Ha a kód tér a {0,1} szimbólumokból épül fel, akkor a T°3 fix pontjai 000000000000000000000000000000000000000000000000000 111111111111111111111111111111111111111111111111111 011011011011011011011011011011011011011011011011011 100100100100100100100100100100100100100100100100100 001001001001001001001001001001001001001001001001001 Definíció Az f : X X (X,d) metrikus téren értelmezett transzformáció kontraktív vagy kontrakciós leképezés, ha létezik olyan 0 ≤ s < 1 melyre d (f (x), f (y)) ≤ s· d (x,y) ∀ x, y ∈ X. Bármely ilyen s számot az f kontrakciós tényezőjének hívunk. Tétel (A kontrakciós leképezés tétele) Legyen f : X X egy az (X,d) teljes metrikus téren értelmezett kontrakciós leképezés. Ekkor f pontosan egy xf ∈ X fix ponttal 5 rendelkezik, sőt bármely x ∈ X

pontra az {f°n (x) : n = 0, 1, 2, } sorozat az xf ponthoz konvergál; azaz lim n ∞ f°n (x) = xf minden x ∈ X -re. Bizonyítás Legyen x ∈ X. Legyen 0 ≤ s < 1 az f kontrakciós tényezője Ekkor d (f°n (x), f°m (x)) ≤ sm∧ n d (x,f°|n–m| (x)) minden m, n = 0, 1, 2, -re, ahol az x ∈ X kötött. Az m∧n jelölést az m, n számpár minimumára alkalmazzuk. Nevezetesen, k = 0, 1, 2, -ra d(x, f°k (x)) ≤ d( x, f (x) ) + d( f (x), f°2 (x) ) + + d( f°(k – 1) (x), f°k (x) ), ≤ ( 1 + s + s2 + sk – 1) d(x, f (x)), ≤ (1– s)-1 d(x, f (x)), így a (4.2) egyenlőtlenségbe helyettesítve a következőt kapjuk d (f°n (x), f°m (x)) ≤ sm∧ n · (1– s)-1· d(x, f (x)), ∞ n=0 amiből egyből következik, hogy az { (x)} egy Cauchy sorozat. Mivel X teljes, ez a Cauchy sorozat is rendelkezik egy xf ∈ X határértékkel, így f°n lim n ∞ f°n (x) = xf. Most azt kell megmutatnunk, hogy xf az f fix pontja. Mivel f kontraktív, folytonos is,

ennélfogva lim lim f (xf) = f ( n∞ f°n (x)) = n∞ f°n+1 (x) = xf. Legvégül, lehet egynél több fix pont is? Tegyük fel van. Legyen xf és yf f két fix pontja. Ekkor xf = f (xf), yf = f (yf), és d( xf, yf ) = d( f (xf), f (yf) ) ≤ sd( xf, yf ), amiből (1– s) d( xf, yf ) ≤ 0, amiből következik, hogy d( xf, yf ) = 0, tehát xf = yf . Ezzel teljessé vált bizonyításunk. 5 (4.2) 4. FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS I: IFS FRAKTÁLOK 4.1 A képek tere – a Hausdorff tér H A következőkben leírjuk H teret, ahol kényelmesen tanulmányozhatjuk a metrikus terek olyan fontos részhalmazait, mint például az (, Euklideszi). Figyelmünket csak a teljes metrikus tereknek szenteljük, mivel csak ezek tanulmányozására lesz szükség fraktális képtömörítési eljárások vizsgálatakor. Általában az (X,d) R2, Euklideszi mértékkel mért tér esetét vizsgáljuk; de az általános elméletek felállítása is hasznos lehet. Nevezetesen, ha rajzok,

képek, vagy az R2 más “fehér alapon fekete” részhalmazait szeretnénk vizsgálni, alkalmas a (H(R2),h(Euklideszi)) metrikus teret használnunk. Definíció Legyen (X,d) egy teljes metrikus tér. Ekkor H(X) a tér azon pontjait jelöli, melyek X, az üres halmazon kívüli, kompakt részhalmazai. Definíció Legyen (X,d) egy teljes metrikus tér, x ∈ X, és B ∈ H(X). d(x,B) = min {d(x,y) : y ∈ B}. d(x,B) az x pont B halmaztól mért távolsága. Definíció Legyen (X,d) egy teljes metrikus tér. Legyen A és B H(X) részei d(A,B) = max { d(x,B) : x ∈ A}. d(A,B) az A ∈ H(X) és a B ∈ H(X) halmazok távolságát jelenti. Segédtétel Legyen (X,d) egy teljes metrikus tér. Ha A, B és C H(X) elemei, akkor d(A ∪ B,C) = d(A,C) ∨ d(B,C), ahol x ∨ y az x, y maximumát jelenti. Definíció Legyen (X,d) egy teljes metrikus tér. Ekkor H(X)-ben lévő A és B halmazok pontjai közti Hausdorff távolságot a következőképp definiáljuk h(A,B) = d(A,B) ∨ d(B,A). Ezt

a H halmaz Hausdorff mértékének is nevezzük. 5 Segédtétel Legyen (X,d) egy teljes metrikus tér. Ekkor H(X) A, B, C, D elemeire h(A ∪ B,C ∪ D) ≤ h(A,C) ∨ d(B,D). Segédtétel Legyen (X,d) egy teljes metrikus tér. Legyen A, B H(X) eleme Legyen > 0. Ekkor ε h(A,B) ≤ ε ⇔ A ⊂ B + ε és B ⊂ A + ε, ahol A + ε = { x ∈ X : d(x,A) ≤ ε }. Az előző eredmények, melyek a [2]-ben részletesebben tárgyaltak, hasznosak a következő központi tétel bizonyításakor. Ezen a tétel segítségével jelenthetjük ki az IFS fraktálok létezését. Tétel Legyen (X,d) egy teljes metrikus tér. Ekkor H(X,h) egy teljes metrikus tér Sőt, ha {An ∈ H(X) : n = 1, 2, }} egy Cauchy sorozat, akkor A= lim n ∞ An ∈ H(X) a következőképp jellemezhető A = { x ∈ X : ∃ x-hez konvergáló {xn ∈ An}Cauchy sorozat}. Bizonyítás Lásd [2] és az ottani referenciák. Legyen (X,d) egy teljes metrikus tér és jelölje (H(X), h(d)) a hozzárendelt

Hausdorff teret, a korábban leírt h(d) Hausdorff mértékkel. A h(d) jelölést annak jelzésére használjuk, hogy a h alapjául szolgáló mérték d. 4.2 Kontrakciós leképzések a H téren Segédtétel Legyen w : X X egy kontrakciós leképezés az (X,d) metrikus téren. Ekkor w folytonos. Bizonyítás Legyen adott ε > 0. Legyen w kontrakciós tényezője egy s > 0 Ekkor d( w(x), w(y) ) ≤ sd(x,y) < ε d(x,y) < δ mindig igaz, ha δ = ε / s. 5 Segédtétel Legyen w : X X egy folytonos leképezés az (X,d) metrikus téren. Ekkor w H(X)-et önmagába képzi le. Bizonyítás Legyen S X egy nem üres kompakt részhalmaza. Ekkor nyilvánvaló, hogy w(S) = {w(x) : x ∈ S } is nem üres. w(S) kompaktságát kell bizonyítanunk Legyen {yn = w(xn)} S pontjainak egy végtelen sorozata. Ekkor {xn} is S pontjainak egy végtelen sorozata. Mivel S kompakt, létezik egy olyan {x N n} részsorozat, amely az x ∈ S ponthoz konvergál; de ekkor a w folytonosságból

adódik, hogy {yN n = f (x N n)} az {yn} részsorozata és y ∈ w(S)-hoz konvergál. Ez teljessé teszi bizonyításunkat A következő segédtétel pedig megmutatja, hogyan készíthetünk egy (H(X), h) kontrakciós leképezést egy (X,d)-n értelmezett kontrakciós leképezésből. Segédtétel Legyen w : X X egy folytonos leképezés az (X,d) metrikus téren s kontrakciós tényezővel. Ekkor w : H(X) H(X) az alábbiak szerint definiált w(B) = {w(x) : x ∈ B}, ∀ B ∈ H(X) egy (H(X), h(d))-n értelmezett kontrakciós leképezés, s kontrakciós tényezővel. Bizonyítás Az 1. segédtételből következik, hogy w : X X folytonos Ennélfogva a 2 segédtétel szerint w H(X)-et önmagába képzi le. Legyen B, C ∈ H(X) Ekkor d(w(B),w(C)) = max{min{d(w(x),w(y)) : y ∈ C} : x ∈B} ≤ max{min{s· d(x,y) : y ∈ C } : x ∈B } ≤ s· d(B,C). Hasonlóképpen d(w(C),w(B)) ≤ s· d(C,B). Ennélfogva, h(w(B),w(C)) = d(w(B),w(C)) ∨ d(w(C),w(B)) ≤ s· d(B,C) ∨ d(C,B) ≤ s·

d(B,C). Ez teljessé teszi bizonyításunkat. A következő segédtétel biztosítja a (H(X), h)-n értelmezett kontrakciós leképezések egyesítésével új kontrakciós leképezés létrehozásának alapvető módszerét. Ez a módszer eltér az eredeti egyesítés értelmezéstől. Segédtétel Legyen (X,d) egy teljes metrikus tér. Legyenek a {wn : n = 1, 2, , N} kontrakciós leképezések a (H(X), h) téren. Jelölje sn a wn leképezés kontrakciós tényezőjét minden n-re. W : H(X) H(X)-et az alábbiak szerint definiáljuk W(B) = w1(B) ∪ w2(B) ∪ ∪ wN(B) N U = n =1 wn(B), minden B ∈ H(X)-re. 5 Ekkor W egy s = max {sn : n = 1, 2, , N} kontrakciós tényezővel rendelkező kontrakciós leképezés. Bizonyítás Lásd [1]. 4.3 Iterált függvény rendszerek Definíció Egy (hiperbolikus) iterált függvény rendszer egy (X,d) teljes metrikus tér és megfelelő sn kontrakciós tényezőjű wn : X X kontrakciós leképezések véges halmazából áll, n = 1,

2, , N. Az IFS betűszó az Iterated Function System-ből származik. Az ilyen IFS-ekre {X; wn, n = 1, 2, , N} jelölést alkalmazunk, kontrakciós tényezője s = max{sn : n = 1, 2, , N }. A definícióban azért van zárójelben a hiperbolikus szó, mert a gyakorlatban is gyakran elhagyják. Sőt, néha az IFS terminológia alatt csak egy metrikus téren értelmezett leképezések véges halmazát értik, a leképzésekre adott minden különös feltétel nélkül. A következő tétel összegzi a hiperbolikus IFS-ekkel kapcsolatos főbb tényeket. Tétel (Az IFS tétel) Legyen {X; wn, n = 1, 2, , N} egy s kontrakciós tényezővel rendelkező hiperbolikus iterált függvény rendszer. Ekkor az alábbiak szerint definiált W : H(X) H(X) transzformáció N U W(B) = n =1 wn(B), minden B ∈ H(X)-re egy a (H(X), h(d)) téren értelmezett, s kontrakciós tényezővel rendelkező kontrakciós leképezés; azaz h(W(B),W(C)) ≤ s· h(B, C). minden B, C ∈ H(X)–re. Rendelkezik egy

egyedi A ∈ H(X) fix ponttal, amelyre N U A = W(A) = n =1 wn(A), teljesül, és A = lim n ∞ W°n (B) minden B ∈ H(X)–re. Bizonyítás lásd [2]. Definíció Az IFS tétel által definiált A ∈ H(X) fix pontot az IFS attraktorának hívjuk. 5 Az IFS-ek egy példája a kód téren alapul. Legyen (∑,d) a {0,1,2} szimbólumokból felépített kód tér a következő mértékkel ∞ d(x,y) = ∑ n =1 xn − yn 4n . Definiáljuk a w1 : ∑ ∑ -et w1(x) = 0x1x2x3-ként és w2(x) = 2x1x2x3-ként . Ekkor w1 és w2 is kontrakciós leképezés. Az {∑; w1, w2} IFS attraktora az ∑ klasszikus C Cantor halmazhoz hasonló szerkezetű részhalmaza. Ha az IFS-t kibővítjük egy harmadik w3(x) = 1x1x2x3 transzformációval, akkor az attraktor az egész ∑ térré válik. 4.4 Az R2 -en affin transzformációkból készült iterált függvény rendszerek Tekintsük az {R2; w1,w2,w3} IFS-t, ahol wi affin transzformációk R2-en:  x 0.5 0   x 0 

y =  0 0.5  y + 0     , w1     x 0.5 0   x 100  y =  0 0.5  y +  0     , w2     x 0.5 0   x 30  y =  0 0.5  y + 30     . w3    A fenti IFS attraktora a (0,0), (200,0) és (60,60) csúcsokkal rendelkező Sierpinski háromszög, amint az 4.1 ábrán látható 4.1 ábra (0,0), (200,0) és (60,60) csúcsokkal rendelkező Sierpinski háromszög 5 Az affin transzformációkból származó IFS-eket mátrixokkal jellemezni nem gazdaságos. Inkább a következő formát használjuk  x  a i  y =  c wi    i bi   x  ei  + di   y  fi  = Aix + ti. Ekkor az {R2; w1,w2,w3} IFS az 4.1 táblázatban látható módon fejezhető ki w 1 2 3 a 0.5 0.5 0.5 b 0 0 0 c 0 0 0 d e 0.5 0 0.5 100 0.5 30 f p 0 0.33 0 0.33 30 0.34 4.1

táblázat egy Sierpinski háromszög IFS kódja Az 4.1 táblázatban látható, hogy minden wi i = 1, 2, 3 értéksorhoz egy további pi érték rendelt. Ezek a számok valószínűségekként értelmezendők Az {X; wn, n = 1, 2, , N} IFS általános esetében N ilyen {pi : i = 1, 2, , N } szám lenne, melyekre teljesülnek az alábbiak, p1 + p2 + p3 + + pN = 1 és pi > 0 minden i = 1, 2, , N-re. Ezek a számok az IFS attraktorainak mérés elméletéhez kapcsolódnak, és az IFS attraktorának képnek a véletlen iterációs algoritmus 8 segítségével történő számításakor játszanak szerepet, amelyekről bővebben [5]-ben olvashatunk. De nincs szerepük a fekete-fehér képekre alkalmazott másológép algoritmusban. A véletlen iterációs algoritmussal kapcsolatban értékeik a következő módon határozhatók meg detAi pi ≈ ∑ N i =í Ai = a i bi − ci di ∑ iN=1 a ibi − ci di i = 1, 2, , N-re. Ha, valamely i-re det Ai = 0, akkor pi-hez egy kis

pozitív érték, például 0.001, adható meg. Egyéb esetekben tapasztalat alapján dönthetünk Az 41 táblázat adataira mint IFS kód hivatkozunk. Egy IFS attraktora a véletlen iterációs algoritmus [2] segítségével számítható ki. 4.5 Az IFS attraktorok számítására szolgáló másológép algoritmus Az 4.3 alfejezetben bemutatott IFS tételből származó eredmények alapján a következő módszer ajánlkozik egy IFS attraktorának meghatározására. Válasszunk egy A0 ⊂ R2 kompakt halmazt. Ekkor An = W°n (A) értékét a következők szerint határozhatjuk meg 5 N An+1 = U j =1 wj(An) n = 1, 2, -re; azaz, készíthetünk egy {An : n = 0, 1, 2, 3, } ⊂ H(R2) sorozatot. Az IFS tétel értelmében az {An} sorozat az IFS Hausdorff térbeli attraktorához konvergál. Ez biztosítja egy IFS attraktorának folytonos közelítési eljárását. Az eljárás gyakorlatba átültetésének egyik módja, amikor wn hasonlóak, a másológép algoritmus

alkalmazása a következők szerint. Az 42 (a) ábra egy téglalap alakú papírlapot mutat 3 téglalappal, mindegyik kis téglalap az őket tartalmazó lap kerületének 0.4096 arányú kicsinyítése Nyolc azonos másolatot készítettünk erről a lapról; forrás lapokként hivatkozunk rájuk. Következőként egy szövegről három másolatot készítünk, szintén 0.4096 arányban kicsinyítve, és az egyik forrás lapra ragasztjuk, mindegyik kis téglalapban a lekicsinyített szöveggel, ahogy az 4.2 (b) ábrán látszik. Az eredmény lapról újabb három azonos arányban kicsinyített másolat készül és a második forrás lap téglalapjaiba illesztjük őket, az 4.2 (c) ábrához hasonlóan A folytonosan ismételt eljárás az 4.2 (b)–(i) ábrákon látható képek sorozatát eredményezi A kép egyre kevésbé változik – azaz a folyamat képek konvergens sorozatát látszik eredményezni, az elméletbeli ígéretünkhöz híven. A végső kép alapvetően nem

változik, ha megismételjük a folyamatot – a transzformáció fix képét, az attraktorát mutatja. Ez a forrás lapon alkalmazott három affin transzformáció által létrehozott fraktál. 5 4.2 ábra (a)–(i) Egy fraktál előállítása a másológép algoritmust egy szövegoldalra alkalmazva A másológép algoritmust néhány szempont szerint fogalmilag általánosítjuk. Először, úgy képzeljük, mintha az összes transzformációt egyszerre alkalmaznánk a másológépben : azaz egyetlen iterációs lépésben nem kell mindig a számos másolat elkészítésének és összeszerkesztésének fáradtságos munkáját elvégezni. Másodszor, a másológép által tetszőleges transzformációt, pontosabban tetszőleges affin transzformációt, elvégeztethetőnek tételezünk fel. Harmadszor, az 48 alfejezetben leírtaknak megfelelően, a másolót szürkeárnyalatú képek kezelésére is alkalmasnak tartjuk a fekete-fehér képek mellett. 4.6 A kollázs 9 tétel A

következő tétel jelenti az adott halmazhoz közeli attraktorú IFS tervezésének magját. Ez a különböző fraktál alapú képtömörítő rendszerek által használt ugyanazon alapvető elv variációinak prototípusa. Az általános elvet később, a 51 alfejezetben tárgyaljuk 5 Tétel (A kollázs tétel) Legyen (X,d) egy teljes metrikus tér. Legyen adott T ∈ H(X) és ε ≥ 0. Válasszunk egy olyan 0 ≤ s < 1 kontrakciós tényezőjű {X; w1,w2, ,wN} IFS-t, amelyre  N   T, U wn (T )  ≤ ε, h  n =1 ahol h(d) a Hausdorff mérték. Ekkor h (T,A) ≤ ε / (1–s), ahol A az IFS attraktora. Ekvivalens módon  N   T, U wn (T )  minden T ∈ H(X)-re. h (T,A) ≤ (1–s)-1 h  n =1 Bizonyítás Lásd [2] 4.7 Fraktál alapú képtömörítés IFS fraktálok felhasználásával A kollázs tétel elmondja, hogy egy adott halmazhoz hasonlító vagy ahhoz közeli attraktorú IFS-t megtalálásához előbb a transzformációk – egy

olyan alkalmas téren értelmezett kontrakciós transzformációk, melyben a kérdéses halmaz megtalálható – egy olyan halmazát kell megkeresni, hogy a vizsgált halmaz transzformált képeinek uniója vagy kollázsa az adott halmazhoz közeli vagy hasonló legyen. A két kép hasonlóságának mértékét a Hausdorff távolság segítségével vizsgáljuk. A fraktál alapú képtömörítés központi célja, hogy a valós világ képeinek jellemzésére olyan felbontásfüggetlen modelleket találjunk, melyek egyesek és nullák véges (és lehetőleg rövid) sorozatával adhatók meg. Ha a valós világbeli képünk olyan elemi formájú fekete-fehér alakzat, mint a 2.2 (i) alfejezetben leírtak, akkor fraktál alapú képtömörítést valósíthatunk meg az IFS tömörítési algoritmust alkalmazva, amely egy a kollázs tételre alapuló interaktív kép modellezési módszer. Az IFS tömörítési algoritmus a T, -ben fekvő, cél képpel kezdődik. T lehet egy

digitalizált kép (például egy fehér levél egy fekete háttéren) vagy egy poligonizált közelítés (egy poligonizált levél körvonal) is. T -t egy grafikus számítógép monitoron ábrázoljuk. A  x a 1 b1   x  e1   y =  c d   y +  f  1    1  = A1x + t1. w1(x) = w1    1 affin transzformációt az a1 = d1 = 0.25, b1 = c1 = 025 együtthatókkal inicializálva mutatjuk be. A w1(T) képet a monitoron egy a T színtől eltérő színnel jelenítjük meg A w1(T) kép az eredeti T negyed méretű másolata, a (0,0) ponthoz közelebbi középponttal. Ezután a felhasználó úgy változtatja meg az együtthatókat egy egér vagy más interakciós technika segítségével, hogy a w1(T) kép változatos módon eltolva, elforgatva és elnyírva 5 jelenjen meg a képernyőn. A felhasználó célja a w1(T) képet úgy alakítani, hogy a T kép egy részét lefedje. Fontos, hogy a w1(T) kép dimenziói kisebbek

legyenek a T dimenzióinál, hogy w1 zsugorítás (kontrakció) voltát biztosítsuk. Ha a w1(T) már megfelelően pozícionált, rögzítjük együtthatóival együtt, és egy új w2 affin transzformációt és w2(T) másolatot mutatunk be. w2 képét interaktív módon úgy alakítjuk, hogy a w2(T) a T kép w1(T) által le nem fedett pixeleket (egy pixel alapú megjelenítési módszert feltételezve) fedje le. A w1(T) és w2(T) átfedése engedélyezett, de általában a lehető legkisebb kell legyen. Ily módon a felhasználó kontraktív affin transzformációk egy {w1,w2,w3, ,wN} halmazát definiálja, mely a következő tulajdonsággal rendelkezik: az eredeti T cél kép és a N T=U n =1 wn(T) halmaz látszólag közeli, amíg N a lehető legkisebb. A T és T közelségének matematikai mutatója a h(T, T ) Hausdorff távolságuk. A “látszólag közeliségen” a “h(T, T ) kicsit” értjük. Az így meghatározott {w1,w2,w3, ,wN} transzformációk együtthatóinak

értékeit eltároljuk. A kollázs tétel biztosít minket arról, hogy ennek az IFS-nek az A attraktora is látszólag közel lesz T-hez. Sőt, ha T = T , akkor A = T A nem csak közelíti a T képet, hanem egy felbontás független modellt is biztosít számára, közben csak egyesek és nullák véges sorozatát használva. Az IFS tömörítési algoritmust az 4.3 ábra illusztrálja, amely a cél T poligonális levelet ábrázolja a bal felső és alsó képen. T-t mindkét esetben nagyjából lefedi négy saját magára alkalmazott affin transzformáció. A feladatot gyengén oldotta meg az alsó kép és jól a felső A hozzájuk tartozó attraktorok a jobb oldalon láthatók: a felső közelebb van a célhoz, mert jobb a kollázs. 5 4.3 ábra Egy poligonális levél jó és rossz kollázsainak és a megfelelő attraktorok képe Közelítő kollázs Valódi páfrány Fraktál 4.4 ábra A fekete fodorka eredeti és a kollázs tétel segítségével előállított képe A

fekete fodorka nevű páfrány képét előállító IFS kollázsa, amely az 4.4 ábrán látható, négy a következő formában leírt affin leképzésből áll  x  r cosθ   = wi  y  r sin θ − s sin θ   x  h    +  s cosθ   y  k (i = 1, 2, 3, 4). Hasonló transzformációk IFS kódja az 4.2 táblázatban adott Leképzés 1 2 3 4 Eltolások Forgatások Léptékek h k r s θ φ 0.0 00 0 0 0.0 016 0.0 16 -25 -25 085 085 0.0 16 49 49 0.3 034 0.0 044 120 -50 03 037 4.2 táblázat A fekete fodorka IFS kódja, arány és szögértékekkel megadva A kollázs tétel alapján szintén tudjuk, ha a kontrakciós tényezőt állandó értéken tartva a wn transzformációban csak kis változtatásokat teszünk, akkor a wn(T) képen, így az attraktoron is, csak kis változások történnek – azaz ha minden wn transzformáció, egy a H(X) teret önmagába képző transzformációnak tekintve, egyenletesen és

folytonosan függ wn paramétereitől fix kontraktivitás esetén, akkor a hozzátartozó IFS attraktora is folytonosan függ a paraméterektől. Más szavakkal, a paraméterek kis változására kis 5 változással jár az attraktornál is, így biztosítja, hogy a rendszer hiperbolikus maradjon. Ezek szerint folytonosan ellenőrizhetjük az IFS attraktorát a transzformációk paramétereinek változtatásával. Pontosan ezt tesszük kép tömörítési alkalmazások során is 4.5 ábra Az IFS attraktorok folyamatos paraméterfüggőségének illusztrációja Az IFS attraktorának a beágyazott paraméterektől való függését szemlélteti az 4.5 ábra, amely egy fraktál páfrány a hozzá tartozó IFS kódok változtatása okozta egyenletes változását mutatja. Összetettebb képek is felépíthetők sok részlet felhasználásával, ekkor minden részlet egy-egy IFS. Ráadásul sok más bonyolultabb módszer is létezik a fraktál alapú képtömörítés elérésére,

mind az affin transzformációk és a folytonos függőség alapvető témájára épít. Például az IFS algoritmus működik kondenzációs IFS 10-ek esetében is Sőt mitöbb, maga a kondenzációs halmaz is lehet egy IFS attraktor, így sokkal összetettebb hierarchikus modellek is felépíthetőek a valós világ képei számára. Ha az IFS-t felépítő affin transzformációk együtthatóit egyetlen bájton ábrázolnánk, akkor egy négy transzformációból álló IFS tárolásához csak 24 bájtnyi adat szükséges. Ezután az együtthatók tárolására valamely veszteségmentes adat tömörítési módszert kell alkalmazni. Ezzel a következő fejezetben foglalkozunk Meglepő és izgalmas eredményre juthatunk, amikor felfedezzük, hogy az IFS elméletet az IFS kódokra alkalmazva optimális módon valósíthatjuk meg a kívánt veszteségmentes adattömörítést. 4.8 Szürkeárnyalatú másológép algoritmus Szürkeárnyalatú képekre – a fekete-fehér esetnél

leírtakhoz hasonlóan – képezhetünk IFS-eket és megalkothatjuk a hozzájuk tartozó kollázs tételt, lásd [1] 4.10 alfejezet A különbség mindössze annyi, hogy itt három dimenziós térben értelmezzük az IFS-t felépítő transzformációkat, a harmadik dimenzió a szürkeségi árnyalat. Az ilyen IFS-ek attraktorainak kiszámítására szolgál a szürkeárnyalatú másológép algoritmus. Képzeletbeli másológépünk ekkor a másolandó kép zárt területein nem csak tetszőleges affin transzformációk végrehajtására képes, hanem egy szűrőrendszer 5 segítségével a másolandó területek intenzitását is meg tudja változtatni. A szűrők “áteresztő képességét” az adott transzformációhoz tartozó pi , i = 1, 2, , N, értékkel jellemezzük, amelyeket valószínűségekként is értelmezhetünk, ahogy azt már a 4.4 alfejezetben is jeleztük. Ugyanis a kontrakció feltétele miatt 0 ≤ pi < 1, de mivel a kép összterületének

fényessége nem változhat meg, a p1 + p2 + + pN = 1 egyenlőségnek is teljesülnie kell. Ezek után másológépünk a forrás képet a fentiekben leírtak szerint kicsinyíti, az egymást átfedő eredmény területeken a fényességi értékeket összegezve, ott világosabb lesz az eredmény. A fekete-fehér másológép működéséhez hasonlóan a másolás eredménye itt is független lesz a kiinduló képtől, s a módszer ugyanúgy alkalmazható kondenzációs IFS-ek esetében is. 5 5. FRAKTÁL ALAPÚ KÉPTÖMÖRÍTÉS II: A FRAKTÁL TRANSZFORMÁCIÓ 5.1 A fraktál alapú képtömörítés módszerének általános leírása Az eddig tárgyalt fraktál alapú képtömörítési módszerek mind ugyanazon három alapvető összetevőből épülnek fel 1. Egy Y modell az ℜ térbeli valós világ képeinek modellezésére, a 2 fejezetben leírtaknak megfelelően. Y minden “pontja ” egy valós világbeli képet jelent,  tartóval, kromatikus jellemzőkkel, és

így tovább. Y példái halmazok, függvények és mérések tereiből állnak. 2. Egy d mérték az Y téren, amelyre az (Y,d) egy teljes metrikus tér 3. Egy az (Y,d) téren értelmezett kontraktív O operátor Azaz olyan O operátor, amelyhez létezik egy 0 ≤ s < 1 valós szám, és d(O(φ),O(ψ)) ≤ s· d(φ, ψ) minden φ,ψ ∈ Y-ra. Az O operátor az alatta fekvő  térre és kromatikus jellemzőkre ható elemi kontraktív transzformációk véges halmazából épül fel. O egy példája W, a Hutchinson operátor W= U wi , amely bináris képek esetén használatos, ha Y a 2. fejezetben leírt ℜi tér, és d az 4 fejezetben tárgyalt Hausdorff távolság. Az operátor a tömören kifejezhető wi függvényekből épül fel. A gyakorlatban ezek egy vagy más formában leírt kontraktív affin transzformációk; és mint ilyenek együtthatóik véges halmazaival leírhatók, teljes halmazuk pedig az O operátor “kódját” jelenti. Ebben a fejezetben az O

operátort helyi iterált függvény rendszerek segítségével írjuk le. Az 1, 2 és 3 összetevőből származtatható tételeket és feltételeket a következőképp összegezhetjük: (1) Tétel (Az attraktorok létezése) Mivel O kontraktív és az Y metrikus tér teljes létezik egy olyan egyedi φ ∈ Y kép, melyre O(φ) = φ. (2) Feltétel (Az attraktorok fraktál jellemzője) Megelőlegezzük φ felbontás független jellemzőjét az O-t alkotó függvények kontraktivitása miatt: az egész állandó kép ugyanaz mint a rá alkalmazott kontrakciók összege vagy uniója, azaz saját maga (részei) zsugorított másolataiból készül. A kontraktivitás módjától függően a fókusz lehet térbeli, intenzitásbeli vagy a mérték elmélet 5 alapján értelmezett kontraktivitás, és feltételezzük, hogy φ attraktora örökli a kapcsolódó fraktál jellemzőket. (3) Tétel (Az attraktorok számítására) φ kiszámításához felhasználhatjuk azt a tényt, hogy

ha ψ ∈ Y akkor O-t ismételten alkalmazva ψ-re az a φ attraktorhoz konvergál; azaz lim n ∞ O°n = φ. Sőt, ha létezik egy olyan C valós konstans, melyre d(φ1,φ2) < C minden φ1, φ2 ∈ Y -ra, akkor a d(O°n(ψ), φ) ≤ snC becsült hibaértékkel élhetünk. A fenti egyenlőség azt mondja, hogy állandó képek állíthatók elő a másológép vagy a szürkeárnyalatú másológép algoritmushoz hasonló algoritmusok segítségével. A becsült hiba pedig lehetőséget biztosít, hogy meghatározhassuk a kívánt pontosság eléréséhez szükséges iterációk számát. (4) Tétel (Általános közelítési kollázs tétel) A ψ ∈ Y és az O φ attraktora közti távolság a következő becslés alapján rögzített d ( ψ , O( ψ )) (1 - s) d(φ, ψ) ≤ . A fenti tételek bizonyításai a [2]-ben találhatók meg. Az O(ψ) halmazt egy kollázsnak nevezzük, míg a d(ψ,O(ψ)) távolságot a kollázs hibának. A tétel szerint egy ψ-hez közeli attraktorú

O operátor megtalálásához csak azt a problémát kell megoldanunk, hogy olyan O-t találjunk, amelyet ψ-re alkalmazva nem nagyon változtatja meg ψ-t. Például, ha a szürkeárnyalatú algoritmust úgy alakítjuk át, hogy a kimenete “úgy nézzen ki” mint a bemenete, akkor a hozzá kapcsolódó állandó kép is “úgy fog kinézni” mint a bemenet. Így, ha az 1, 2 és 3 összetevő rendelkezésünkre áll, bármikor képesek vagyunk valamilyen formájú fraktál alapú képtömörítő rendszert előállítani. Például az 4 fejezetben bemutattuk, hogy globálisan definiált transzformációk gyűjteményeinek egyesítésből különböző módon állíthatunk elő O operátorokat úgy, hogy a fent leírt szerkezet alkalmazható legyen. Mindegyik eset egy interaktívan vezérelhető fraktál kép modellezésre alkalmas fraktál alapú képtömörítési rendszert eredményezett; ezen rendszerek attraktorai halmazokként és a valós világ képeinek különböző

modelljeihez kapcsolódó mérésekként definiálhatók. A fraktál transzformációs elméletben az 1, 2 és 3 alapvető összetevők helyi transzformációk gyűjteményei által biztosítottak. Ezek különböző módokon összegyűjtve alkotják az O operátort és egy kapcsolódó felbontás független képek, fraktál attraktorok, előállítására alkalmas rendszert. Mindegyik változat az automatikus fraktál alapú képtömörítés különböző módjaihoz vezet; a transzformációk helyi jellege 5 teszi lehetővé az transzformációk kiválasztásának inkább automatikus mint interaktív módját. 5.2 Helyi iterált függvény rendszerek A fraktál transzformációs elmélet bemutatása céljából és hogy megmutassuk, hogy a fraktálok által definiált helyi transzformációk alkalmazása hogyan vezet automatikus képtömörítési módszerekhez, megnézzük mi történik ha az IFS elméletet bináris képek esetében helyi transzformációk felhasználásával

alkalmazzuk. A bináris képek automatikus fraktál alapú tömörítésének egy egyszerű vázlatát ismertetjük. Definíció Legyen (X,d) egy kompakt metrikus tér. Legyen R X egy nem üres részhalmaza. Legyen w : R X és legyen s egy 0 ≤ s < 1 valós szám Ha d(w(x),w(y)) ≤ s· d(x,y) minden x,y-ra R-ben, akkor w-t egy helyi kontrakciós leképezésnek nevezzük (X,d)-n. Az s szám a w kontraktivitási tényezője. Definíció Legyen (X,d) egy kompakt metrikus tér és legyen wi : Ri X egy helyi kontrakciós leképezés (X,d)-n wi kontrakciós tényezővel i = 1, 2, , N-re, hol N egy pozitív egész. Ekkor {wi : Ri X : i = 1, 2, , N }-t helyi iterált függvény rendszernek (helyi IFS) nevezzük. Az s = max {si : i = 1, 2, , N } a helyi IFS kontrakciós tényezője. A helyi IFS-eket felhasználhatjuk kontraktív leképezések definiálására kép tereken. Itt a következő típusokra nézünk példákat Jelölje S X összes részhalmazainak halmazát. Ekkor

definiálhatunk egy Whelyi : S S operátort a következőknek megfelelően N Whelyi (B) : wi U í =1 ( Ri ∩ B), minden B ∈ S-re. Megfelelő kikötésekkel úgy is tekinthetjük a Whelyi -t, mint egy operátor a H(X) Hausdorff téren, amely X nem üres kompakt részhalmazait tartalmazza; ekkor, nagyon lazán fogalmazva, azt találjuk, hogy Whelyi kontraktív H(X) egyes kompakt részhalmazain s kontrakciós tényezővel a Hausdorff mértékre tekintettel. Azaz, nagyon durván előálltak a fraktál tömörítési rendszerek előző alfejezetben leírt összetevői, ha Whelyi -t választjuk az Y = H(X) téren alkalmazott O operátornak. Azt mondjuk, hogy az X egy nem üres A részhalmaza az attraktora vagy állandó képe a helyi IFS-nek, ha 5 Whelyi (A) = A. Egy helyi IFS-nek lehet, hogy nincs attraktora, de lehet hogy több alapvetően különbözővel rendelkezik. Ha A és B attraktorok, akkor A ∪ B is az, amely szerint ha létezik attraktor, akkor létezik egy

legnagyobb is, nevezetesen amely tartalmazza az összes többit. Ezt a Whelyi összes attraktorának uniójával állíthatjuk elő Általánosságban erre gondolunk, ha a Whelyi attraktoráról beszélünk. Jelöljön {wi : Ri X : i = 1, 2, , N } egy helyi IFS-t, ahol feltételezzük, hogy az Ri halmazok kompaktak. Ekkor X kompakt részhalmazainak egy {An : n = 0, 1, 2, } sorozatát definiálhatjuk a következőképp A0 = X, N An = wi U í =1 ( Ri ∩ An-1) minden n = 1, 2, 3, Nyilvánvalóan ellenőriznünk kell, hogy A0 ⊃ A1 ⊃ A2 ⊃ A3 ⊃ Azaz {An : n = 0, 1, 2, } kompakt halmazok csökkenő sorozata. 5 5.1 ábra A w1 : R1  és w2 : R2  helyi kontraktív affin transzformációkból felépülő helyi IFS rendszer attraktorához konvergáló halmazok csökkenő sorozata. Nevezetesen létezik egy olyan A ⊂ X kompakt halmaz, amire lim n ∞ An = A és N A= wi U í =1 ( Ri ∩ A ) = Whelyi (A). Ekkor, ha nem üres, A a helyi IFS attraktora –

valójában a maximális attraktora. A ürességének lehetőségét kizárhatjuk, ha találunk egy olyan B nem üres kompakt részhalmazt, melyre Whelyi (B) ⊃ B. Ez például akkor lehetséges, ha wi(Ri) ⊂ Ri valamely i-re. A fenti magyarázat egy példája látható a 51 ábrán 5.3 A kollázs tétel helyi IFS-ekre Az általánosan tiszta kontrakciós operátorok csekély száma ellenére megfelelő körültekintéssel a helyi IFS-eket úgy tekinthetjük, mint az általános IFS-eket. Mi történik, ha alkalmazzuk a kapcsolódó kollázs tételt? 5 5.2 ábra Az Ri ⊂  terület és wi (Ri) képe egy helyi IFS-ben Legyen adott egy fekete-fehér cél kép, jelöljük G ⊂ -vel. Hogy elkészíthessük G fraktál modelljét -et kis négyzetekre osztjuk, a G-t metszőket Di -vel jelöljük i = 1, 2, , N ahogy a 5.2 ábrán látható Ekkor minden i = 1, 2, , N -hez keresünk egy wi : Ri  helyi affin transzformációt s kontrakciós tényezővel, amelyre wi (Ri) =

Di és wi (Ri ∩ G) ≅ Di ∩ G. Itt a közel egyenlőség feltétele lehet, hogy a wi (Ri ∩ G) és Di ∩ G közti Hausdorff távolság kicsi legyen, azaz h(wi (Ri ∩ G), Di ∩ G) < ε minden i = 1, 2, , N-re. Más mértékek is használhatóak. Szimmetria Mátrix  1 0   0  0 1 1 2 3 4 5 6 Leírás azonosság  −1 0    0 1 tükrözés az y tengelyre 1 0     0 −1  −1 0     0 −1  0 1    1 0  0 1    −1 0 tükrözés az x tengelyre 180°-os forgatás tükrözés az y = x egyenesre 90°-os forgatás  0 −1   1 0  270°-os forgatás 5  0 −1    −1 0  7 tükrözés az y = -x egyenesre 5.1 táblázat A négyszög affin szimmetriái A forgatások az óramutató járásával ellentétes irányúak D1 = w1R1 D2 = w2R2 D3 = w3R3 D4 = w4R4 Leképezés 1 2 3 4 R1 = R2 = R3 = R4 Dx 0 4 8 12 Dy 0 4 8 12 Rx 0 0 0 0

Ry 0 0 0 0 Az eredeti kép és attraktor Szimmetria 0 0 2 0 5.3 ábra Egyszerű célkép és a hozzárendelt helyi IFS Az attraktort, a Di és Ri blokkok helyzetét és a helyi IFS kódot is szemléltetve. Gyakorlati alkalmazáskor az alábbi formájú transzformációk közül válasszunk w(z) = 0.5 A z + t ahol A :   egy a 5.1 táblázatból választott affin szimmetria Ekkor az Ri blokk kétszer akkora méretű mint Di, ahogy a 5.2 ábrán látható Ha minden Di blokk azonos méretű i = 1, 2, , N-re, akkor a helyi IFS teljesen megadható minden i esetén az aktuális Di és Ri bal alsó sarkainak (Dx, Dy) és (Rx, Ry) koordinátáival, valamint a 5.1 táblázat egyik A affin szimmetriáját kijelölő egész számmal. Az eredményt a helyi IFS kódnak hívjuk és a 53 ábrán látható módon fejezhető ki. 5 5.4 Helyi IFS-ek bináris attraktorainak számítása a menekülési idő algoritmus felhasználásával Bináris képek esetén a helyi IFS-ek A

attraktorának kiszámítására létezik egy egyszerű a [2]-ben leírt menekülési idő algoritmus (escape time algorithm). Legyen D = ∪di és deifináljuk f : D -t a következőképp f(x) = wi -1(x) x ∈ Di i = 1, 2, 3, N esetén. Figyeljük meg, hogy f (Di) = Ri. Ezért használjuk az Ri jelölést wi értelmezési tartomá– nyára és Di-t érték készletére. Az f : D ⊂   egyenes vonalú affin transzformáció olyan rendszert biztosít számunkra, amely taszító halmaza a helyi IFS attraktora. A Di területeket domain blokkoknak míg az Ri területeket range blokkoknak nevezzük. A helyi IFS A attraktora a következőképp kiszámított An közelítések csökkenő sorozata : (0) Inicializáljuk egy számlálót nullával és adjuk meg az iterációk maximális n értékét. (1) Adjuk a bemenetre x ∈ -et. (2) x eleme D-nek? Ha igen, helyettesítsük x-et f (x)-el. Ha nem, legyen a kimenet “x ∉ A” és lépjünk ki. (3) Növeljük a

számlálót; ha a számláló = n, a kimenet “x ∈ A” és kilépünk. (4) Ugorjunk az (1)-re. 5.5 A fekete-fehér fraktál transzformáció A következőkben a bináris képek automatikus fraktál alapú tömörítési rendszerének fő lépéseit ismertetjük. A módszer részletes leírása a [8]-ben található 0. Legyen a bemenet az  ⊂ R2 egy részhalmaza, a G bináris kép 1. Fedjük le G-t a 54 ábrán látható módon Di domain blokkokal A {Di : i = 1, 2, , n} domain blokkok teljes halmazának le kell fednie G-t. A domain blokkok nem fedhetik át egymást; van néhány megfontolás a domain blokkok éleire vonatkozólag, de ezeket figyelmen kívül hagyjuk az egyszerűség kedvéért. Minden domain blokk négyzet alakú. 2. Válasszuk ki a lehetséges R ⊂  range blokkok egy csoportját úgy, hogy R ∩ G ≠ ∅. Ezek a domain blokkok oldalainál kétszer hosszabb oldalú négyzetek Minden lehetséges range blokk bal alsó sarkának (Rx, Ry) koordinátái

egy véges L halmazon belül kell esnie. Hasonlóan definiáljuk a helyi kontraktív affin 5 transzformációk egy T gyűjteményét, az R range blokkot a Di domain blokkba vivő leképezést. Azaz i = 1, 2, , n-re Ti = {w(Di, Rx, Ry, j) : (Rx, Ry) ∈ L; j = 0, 1, 2, , 7 }, ahol w(Di, Rx, Ry, j) az R értelmezési tartományú, Di értékkészeltű kontraktív affin transzformáció a következő formájú 0.5 A(j) z + t és A(j) az 5.1 táblázatbeli j-edik szimmetria 3. A következők szerint folytassuk le a fraktál transzformációs eljárást Minden i-re válasszuk ki azt a wi ∈ Ti -t, amely minimalizálja a h(wi (Ri ∩ G), Di ∩ G) Hausdorff távolságot. Azaz minden domain blokkhoz válasszuk ki azt a hozzá tartozó range blokkot és szimmetriát, amire a kép range blokkon belüli részének transzformáltja leginkább hasonlít a kép domain blokkon belüli területére. A fentieket az 5.5 és 56 ábrák illusztrálják A Whelyi (G) = ∪wi (Ri ∩ G) halmazt a G

kép a helyi IFS-hez tartozó kollázsának, míg a h(wi (Ri ∩ G), Di ∩ G) értéket a kapcsolódó kollázs hibának nevezzük. 4. Rögzítsük a tömörített adatokat helyi IFS kód formában 53 ábrán látható módon 5. Alkalmazzunk egy veszetségmentes adattömörítési algoritmust a helyi IFS kódra, hogy előállítsuk a tömörített helyi IFS kódot. A kép kitömörítésére a másológép vagy a menekülési idő algoritmust alkalmazhatjuk. A gyakorlatban ezek a lépések digitális képeken digitális formában valósulnak meg. Ez tartalmazza a számítógépes grafikáknál megszokott hagyományos kvantálási és diszkretizációs eljárásokat. 5.5 ábra Megfelelő x, y koordináták halmazának kiválasztása a G képhez. 5.4 ábra Egy a G halmazzal megadott bináris kép négyzet alakú Di domain blokkokkal lefedve. 5 Leképezés 1 2 3 4 5 6 7 8 9 Dx 0 1 2 3 2 3 2 3 3 Dy 2.5 2.5 2 2 3 3 1 1 0 Rx 0 0 2 2 2 2 2 2 2 Ry 2 2 2 2 2 2 0 0 0 Szimmetria 0 0

0 0 0 0 0 0 0 5.6 ábra Minden Di domain blokkhoz egy a h(wi (Ri ∩ G), Di ∩ G) Hausdorff távolságot minimalizáló wi affin transzformációt és Ri range blokkot határozunk meg. A helyi IFS kódot a táblázat foglalja össze. 5.6 A szürkeárnyalatú fraktál transzformáció A következőkben megalkotjuk a szürkeárnyalatú képek automatikus fraktál alapú tömörítésére alkalmas helyi IFS szerkezetet. A valós világbeli képek ℜ terének modellezésére a φ :  I valós értékű függvényekből felépülő Y teret választjuk. Itt az I = [a,b] ⊂ R a képen belül előforduló lehetséges szürkeségi értékek valós intervallumát jelenti, mint például [0,255]. Ez a modell megegyezik a 2 fejezetben ismertett ℜii-vel Az Y teret teljes metrikus térré alakítjuk a φ1, φ 2 ∈ Y függvények közti távolságot az alábbiak szerint definiálva d(φ1,φ2) = sup{φ1|(x,y) – φ2(x,y)| : (x,y) ∈ }. Itt |z| a z valós szám abszolút értékét

jelöli, a sup pedig a szuprémumot. 5 Jelölje D  egy véges Di ⊂ , i = 1, 2, , M, halmazok véges gyűjteményéből álló felbontását; azaz M = U i =1 Di, ahol Di ∩ Dj = ∅ ha i ≠ j-re. Legyen minden i-re fi: Di , ahol fi (Di) = Ri, és legyen vi : R R egy 0 ≤ s < 1 kontrakciós tényezővel rendelkező kontrakciós transzformáció. Azaz |vi (z1) – vi (z2)| < s· | z1 – z2 | minden z1, z2 ∈ R-re, i = 1, 2, , M. Ekkor definiáljuk F : Y Y -t az alábbiak szerint F(ψ)(x,y) = vi (ψ(fi (x,y))) ha x,y ∈ Di. Ekkor F kontrakciós tényezője s. F-et a fraktál transzformációs operátornak nevezzük Tétel (A fraktál transzformáció konvergenciájáról) Legyen az (Y,d) teljes metrikus tér és az F : Y Y operátor a fentiek szerint definiált. Ekkor az F kontrakciós leképezés Y-on; vagyis minden φ1,φ2 ∈ L∞()-re d(F(φ1),F(φ2)) ≤ s· d(φ1,φ2), ahol F kontrakciós tényezője s. Az 5.1 fejezetben leírtaknak

megfelelően előállt a fraktál alapú képtömörítő rendszerhez szükséges az 1, 2 és 3 összetevőkkel rendelkező O operátor, az F. Nevezetesen, létezik egy egyedi φ ∈ Y függvény, amelyre F(φ) = φ. A φ függvényt a fraktál transzformáció attraktorának nevezzük. φ kiszámításához felhasználhatjuk azt a tényt, hogy az F-et egy ψ ∈ Y-re ismételten alkalmazva ψ egységesen az φ attraktorhoz konvergál; azaz lim n ∞ F°n (ψ) = φ; sőt rendelkezésünkre áll az alábbi becsült hibaérték |F°n(ψ)(x,y)| ≤ sn |b – a| minden (x,y) ∈ -re, ahol I = [a,b]. Az ψ ∈ Y és a fraktál transzformációs operátor attraktorának távolsága az alábbi közelítés szerint kötött d ( ψ , F ( ψ )) (1 - s) d(φ, ψ) ≤ . 5 Ez az F fraktál transzformációs oprátorra alkalmazott kollázs tétel. 5.7 A fraktál transzformáció operátorhoz rendelhető helyi IFS Az F fraktál transzformációs operátor tulajdonképpen a helyi IFS-ek

Whelyi operátornak három dimenzióban értelmezett változata. Ennek szemléltetésére tegyük fel, hogy az fi (x,y) függvények invertálhatók értelmezési tartományaikon. Ekkor a fenti szerkezete a következőképp kapcsolódik a helyi IFS-ekhez {wi : Ri X : i = 1, 2, , N}, ahol X =  × [a,b], Ri = Ri × [a,b], és wi : Ri X az alábbiak szerint definiált wi(x,y,z) = (wi(x,y) vi (z)) minden (x,y,z) ∈ Ri, wi(x,y) = fi -1(x,y), i = 1, 2, , N-re. X-hez hozzárendeljük a d Euklideszi mértéket, így (X,d) egy kompakt metrikus tér. Ha mindegyik wi függvény kontraktív (ami nem feltétel az előző tételben!) s kontrakciós tényezővel, akkor a helyi IFS is kontraktív azonos kontrakciós tényezővel. Legyen Y = H(X) és definiáljuk a Whelyi : Y Y az alábbiak szerint Whelyi = U wi (Ri ∪ B). Egyszerű belátni, hogy a Whelyi azokat a halmazokat, melyek projekciója az xy síkban az egész , önmagukba képzi le, és valóban Whelyi ({x, y, ψ(x,y) : (x,y)

∈ }) = {x, y, F(ψ)(x,y) : (x,y) ∈ }. Azaz Whelyi az ψ ∈ Y-t ábráját F(ψ) ábrájába képzi le. Ez azt jelenti, hogy F φ fenti fix pontja Whelyi attraktora; vagyis Whelyi (A) = A, ahol A = {x, y, ψ(x,y) : (x,y) ∈ }. 5 6. GYAKORLATI MEGVALÓSÍTÁS 6.1 Egyszerű automatikus fraktál transzformáció A szakdolgozatom írásának kezdetén rendelkezésre álló ismereteim szerint az előző fejezetekben ismertetett elméletek gyakorlati megvalósítására csak a 4.7 alfejezetben leírt, a felhasználó erős közreműködését igénylő, módjára látszott lehetőség. A későbbi olvasmányok [1],[4],[8] és a szakirodalomban megjelölt szoftver megismerése azonban ismét azt bizonyította, hogy a fejlődés rohamléptekkel halad e téren is. Ezért ebben a fejezetben az elmélet után a gyakorlati megvalósítás lehetőségét ismertetem röviden az [1],[4],[8]-ban leírtak alapján. Még egy rövid megjegyezés : az [1]-ben és a többi

áttekintett irodalomban eltért a range és domain blokkok értelmezése, a szakdolgozatban az [1]-ben alkalmazott értelmezéshez maradtam hű. 6.1 ábra Automatikus fraktál alapú képtömörítő folyamatábrája 5 6.2 ábra Fraktál tömörítéssel tárolt képek visszaállításának automatikus módszere Először lássuk tehát a módszert automatikusan megvalósító számítógépeken is implementálható tömörítő rendszer felépítését. A rendszer folyamatábrája a 61 ábrán látható. Itt és most csak a tömörítő rendszer működését vázolom fel, az egyes tényezőknek tömörítésre gyakorolt hatását a következő alfejezetben ismertetem. 5 Első lépésben a kódolandó képet diszjunkt de uniójukban az egész kép felületét lefedő, definiált oldalhosszú négyzetekre, a domain blokkokra bontjuk fel. A második lépés a lehetséges, a domain blokkoknál mindig nagyobb területű, range blokkok meghatározása. Legegyszerűbb esetben a

domain és range blokkok mérete kötött, például 8×8 és 16×16 pixel méretűek rendre. Az így meghatározott range blokkokra elvégezett kontrakciós leképezésekkel, az előbbi példát folytatva a range blokkokat negyedére (8×8 pixel) zsugorítva a fényességi értékeket 3/4 csökkentve és az 5.1 táblázatban összefoglalt 8 szimmetriákat alkalmazva, előállítjuk az ún. zsugorított range blokkokat. Ezután, egy ún blokk komparátor segítségével, minden domain blokkhoz meghatározzuk a hozzá legközelebb álló zsugorított range blokkot, majd az eredményül kapott blokk koordináta illetve a rá alkalmazott transzformáció együttható jellemzőit eltárolva állítjuk elő az egész kép IFS kódját. Legvégül az így kapott adatsorra még valamilyen hagyományos tömörítési eljárást alkalmazva kaphatjuk meg a végleges tömörített képadatot. Az így előállt adatokból az eredeti kép visszaállításának módját a 6.2 ábrán láthatjuk. A

kép visszaállításához két az eredeti kép megjelenítéséhez szükséges nagyságú memória buffert foglalunk le, a domain illetve a range blokkok számára, majd ezeket a fileból kiolvasott adatok alapján felosztjuk megfelelő méretű területekre és a range blokk buffer területére egy tetszőleges kezdő képet töltünk. Az egyes buffereken belül a területeket címző pointerek inicializálása után minden domain blokk bufferbeli területre a hozzátartozó range blokkon végrehajtott megfelelő kontrakciós affin transzformáció végrehajtásával nyert képrészletet írjuk. Miután minden domain blokkot feltöltöttünk az egész domain blokk buffer tartalmát átmásoljuk a range blokk bufferbe, majd újra kezdjük a folyamatot. Az algoritmus kilépési feltételét két módon adhatjuk meg : a végrehajtandó iterációk számával vagy egy küszöb értékkel, melyet egy teljes iterációs ciklus után a range és domain blokk bufferek tartalmának

különbségével hasonlítunk össze. Utóbbi esetben az iteráció akkor ér véget, ha a két memóriaterület tartalmának különbsége kisebb lesz az előre megállapított küszöbértéknél, ez az ún. konvergencia módszer. 6.2 Fraktál képkódoló rendszer tervezésének kérdései Az előbbiekben láthattuk, hogyan működik egy egyszerű fraktál alapú képtömörítési rendszer, ebben a fejezetben részletesen kitérek a rendszer működését befolyásoló egyes tényezők megvalósításának lehetőségire a [6]-ra támaszkodva. A különböző fraktál alapú tömörítő rendszereknél lényegi letérés a betömörítés folyamatában található, a kitömörítés minden helyen a korábbiakban tárgyalt másológép algoritmusok vagy a menekülési idő algoritmus felhasználásával történt. A betömörítésnél három fontos az eredményre nagy befolyást gyakorló tényezőt kell megvizsgálnunk. A képet milyen képfüggő módon bontjuk fel domain ill

range blokkokra, két képrészlet összehasonlítására milyen módszert alkalmazunk és a zsugorított range blokkok előállítására milyen kontraktív transzformációkat használhatunk fel. Lássuk tehát ezeket részleteikben 5 6.21 A kép felbontásának képfüggő módjai Itt két kérdést kell megválaszolnunk, mekkora domain blokk méretet használunk, és változhat-e a domain blokk mérete. A range blokkok mérete minden áttekintett rendszerben a domain blokk méretének kétszerese volt. Az első kérdést az alábbi szempontokat figyelembe véve válaszolhatjuk meg. Kis domain blokkok (4×4 pixel és kisebb) • • • • könnyen elemezhetőek és osztályozhatóak geometriailag a blokkok közti hasonlóság megállapítása gyors könnyen valósítható meg pontos tömörítés az így előállt tömörítő rendszer robosztus, mely teljesítménye különböző képek esetén is állandó Nagy domain blokkok (5×5 pixel és nagyobb) • az egyenletes

képi területek redundanciájának jobb kihasználást eredményezi • nagyobb tömörítési arány érhető el A második kérdésre a jelenlegi rendszerek mindegyike a változtatható blokk méretet adja válaszul. Kötött blokkméret esetében csak a képek egy szűk halmaza tömöríthető hatásosan. A kérdés ma már inkább az, hány és milyen méretű blokk méret szintet különböztessünk meg. Jacquin munkájában kétszintű, 8×8 és 4×4-es, blokkok használatát javasolja, azonban az irodalomban egyre többet hallani a quadtree partícionálást megvalósító rendszerekről is. A [11]-ben bemutatott rendszer például öt szintet különböztet meg, 64×64, 32×32, 16×16, 8×8 és 4×4 pixel felbontásúakat. 6.22 Az összehasonlítandó képrészletek távolságának mérése Az áttekintett irodalomban javarészt az egyszerű RMS (Root Mean Square) közép módszerét alkalmazzák, amely az alábbi képlet alapján számítja a távolságot ∑ dL2 (µ,ν) =

( 1≤i , j ≤ B (µ i,j – ν i,j )2 )1/2 ahol µ és ν, a két összehasonlítandó képrészletet, B×B méretű és µi,j képrészletek i,j-ik pixelét jelölik. ill. νi,j a 6.23 Felhasználható kontraktív transzformációk tere A felhasználható kontraktív transzformációkat két részre bontva vizsgálhatjuk, egyik részük a zsugorított range blokk területi leképzést adja, mint az 5.1 táblázatban látható szimmetriák (geometria rész), másik részük az így kapott területek szürkeségi értékét csökkenti (tömeg rész). 5 Ezen kívül érdemes a range megkülönböztetni : árny blokk (shade) : él blokk (edge) : távközi blokk (midrange) : blokkokat a területeik képe alapján az alábbi módon egyenletes terület, jelentős változás nélkül éles intenzitás váltás tapasztalható a területen egyenletes változás, pontos él nélkül A range blokkok halmaza tehát a fenti három fajta uniójából áll. Ezek közül a tényleges

tömörítéskor csak az él és távközi blokkokat szokták használni, mert az árny blokkok minden geometriai transzformációra önmagukat eredményezik, tömeg részt változtató transzformációkkal pedig egyetlen árny blokkból előállítható az összes többi. A felhasználható transzformációk megalkotásakor két további szempontot kell szem előtt tartanunk. A transzformációk leírását a lehető legegyszerűbb formában kell tartanunk, hogy minél jobb tömörítést érhessünk el – a lehető legkevesebb bittel kell leírni az együtthatókat –, másfelől a transzformációk kontraktivitását elemi transzformációk kontraktivitásával is előállíthatjuk. Ezek után lássuk, az egyes range blokk típusok estén milyen alakú tömeg transzformációk alkalmazandók. árny blokk : távközi blokk : csak a színértékek eltolásának megadása szükséges a kontraszt skála átméretezése αi (µ) mellett egy fényerősség eltolást használnak ∆gi

Ti (µ) = αi (µ) + ∆gi él blokk : a sötét, világos és átmeneti részek meghatározása után a távközi blokknál alkalmazottakon kívül egy izometrikus nyújtást / zsugorítást lni is alkalmaznak az egyes részekre Ti (µ) = lni (αi (µ) + ∆gi ) 6.3 Az egyes tényezők hatása a tömörítési folyamatra A tömörítési folyamatot hatásosságát többféle szempont szerint vizsgálhatjuk. Ilyen szempontok a gyorsaság, elért tömörítési nagyság, a tömörített és visszaalakított kép hűsége az eredetihez. Fraktál alapú képtömörítési rendszereknél a fentiekben tárgyalt tényezők az alábbi befolyással bírnak: • A közelítésre alkalmazott domain és range blokkok mérete : ezek nagy értékek esetén a képet kevesebb területtel tudjuk lefedni, azaz a tömörített adatsor rövidebb, a tömörítéshez szükséges idő kevesebb lesz, de a terület nagysága miatt az eredeti képhez való hűség csökken. Kisebb értékeik

nyilvánvalóan ellenkező előjellel hatnak a vizsgált szempontokra. Változtatható blokk méret esetén több bit szükséges az egyes blokkok lekódolásához, de ez a nagyobb blokk méretekből adódó tömörített adatsor csökkenés mellett elhanyagolható. • Két kép összehasonlításának módszere : valószínűleg ez sem lényegtelen elem, de nem találkoztam olyan forrással, amelyben kitértek volna befolyásoló hatására. 5 • Az alkalmazható kontraktív affin transzformációk száma : nagy értékük esetén sokkal több zsugorított range blokk közül választhatjuk ki a legmegfelelőbbet, így nyilván nagyobb képi hűséget érhetünk el, de ez a tömörítési idő és esetenként az eredmény file méretének növekedésével járhat. A fenti tényezők hatása azonban a kép tartalmától is függ. Egy egyszerű geometria alakzatokat ábrázoló kép tárolása például kevesebb helyet vesz igénybe, mert az őket leíró függvények is

egyszerűbbek és könnyebben meghatározhatók, mint például egy fenyves erdő látképe. A szakirodalomban említett Fractal Imager nevű Windows alapú program az egyetlen általam ismert a fraktál alapú képtömörítést kommersz módon megvalósító rendszer. A többi program általában csak a probléma egyes részeire koncentrálva, szürkeárnyalatú képeken működik. Használatakor a következőket tapasztaltam : • Tömörítés ideje az egyéb módszerekkel (JPEG, GIF, stb) összevetve nagyon lassú, de a várt időket így is jóval meghaladó. Átlagos tömörítés (85) mellett 640×480-as felbontású 256 színű kép tömörítése nem vett 1 percnél több időt igénybe. Nagyobb felbontás – 800×600 – és maximális pontosságú tömörítés mellett azonban 7 perc volt szükséges a JPEG néhány másodpercével szemben. • Tömörítési aránya a hűség csökkentésével a JPEG által elérhetőhöz hasonlóan alakult, sőt nagyon alacsony hűség

mellett jobb méretet és képet eredményezett, mint a hasonló hűségű JPEG. Magasabb értékek (85-100) esetén lényegi eltérést a vizsgált képeken nem tudtam észrevenni, az eredmény file mérete azonban radikálisan megnőtt. • A képi hűség, még alacsony minőségű tömörítés esetén is, meghaladta a JPEG által elérhetőket, sőt néhol még az eredeti képet is valósághűbben ábrázolta. A visszaalakított képeknél minden esetben az eredeti kép színeinél halványabb, fakóbb színeket eredményezett, ami a kontrakciónak köszönhető. A képek részleteinek kinagyításakor azonban eddig máshol nem tapasztalt módon az élek, vonalak megőrzik folytonosságukat, és nem töredeznek szét pixelekké. Fontosnak tartom megjegyezni a JPEG-gel való összehasonlításkor, hogy alacsony képi hűség mellett a JPEG-nél tapasztalható erős blokkosodással szemben a FIF formátumú képeknél inkább az egyes területek “elkenődése” tapasztalható,

mintha egy festményre esett vízcsepp miatt folytak volna össze az egyes területek. A fentiek mellett említésre érdemes, hogy a program fekete-fehér illetve 16 színű képeken alkalmazva az eddig ismeretes módszereknél rosszabb eredményt ért el, ami valószínűleg a kihasználható redundancia alacsonyabb értékének köszönhető. Összefoglalva tehát nagyfelbontású színes vagy szürkeárnyalatú képek tárolására a jelenleg általam ismert legjobb módszer, betömörítésének időigényessége ellenére is. Minden más szempontból a legjobb eredményt adja, így nem csoda, hogy az Internetes alkalmazásokban a JPEG és GIF formátum mellett lassan a FIF is szabvánnyá válik. 5 7. SZAKIRODALOM Felhasznált irodalom Könyvek : [1] Barnsley, M. F and Hurd, L P (1993) Fractal Image Compression AK Peters, Ltd. [2] Barnsley, M. F (1988) Fractals Everywhere Academic Press, Boston [3] Kovács, J., Takács, G és Takács, M (1986) Analízis Nemzeti

Tankönyvkiadó, Budapest Folyóirat cikkek : [4] Anson, L. F (1993) Fractal Image Compression Byte, 18k 11sz 195-202 p [5] Barnsley, M. F and Sloan, A D (1988) A Better Way to Compress Images Byte, 1988. January 215-223 p [6] Jacquin, A. E (1993) Fractal image coding: a review Proceedings IEEE, 81.k 10sz 1451-1466 p [7] Jürgens, H., Peitgen, H O és Saupe, D (1990) A fraktálok nyelve Tudomány, 1990. október 38-45 p Egyéb : [8] U.S Patent #5,065,447 számú szabadalom, hozzáférhető a Magyar Szabadalmi Hivatal Szabadalmi Információs Központjának Szabadalmi Tárában További ajánlott irodalom [9] Ammeter, H. and Hazeghi, K (1993) Progress in fractal image data compression. Bull Schweiz Elektrotechn Vereins, 84k 7sz 11-16 p [10] Bedford, T., Dekking, F M, Breewer, M, Keane, M S and van Schooneveld, D. (1994) Fractal image coding of monochrome images Signal Processing : Image Communications, 6.k 5sz 405-419 p [11] Lu, G. and Yew, T L (1994) Image compression using

quadtree partitioned IFS-s. Electronics Letters, 30k 1sz 23-24 p [12] Jackson, D. J and Mahmod, W (1996) Parallel pipelined fractal image compression using quadtree recomposition. Computer journal, 39k 1sz 1-13 p [13] McGregor, D. R and Fryer, R J (1996) Faster Fractal Compression Dr Dobb’s Journal, 21.k 1sz 34-40 p [14] Rinaldo, R. and Calvagno, G (1995) Image coding by block prediction of multiresolution subimages. IEEE Transactions on Image Processing, 4k 7sz 909-920 p 5 [15] Zhang, L., Zhang, B and Chen, G (1996) Generating and coding of fractal graphs by neural networks and mathematical morphology methods. IEEE Transactions on Neural Networks, 7.k 2sz 400-407 p [16] Zhao, Y. and Yuan, B (1996) A hybrid image compression scheme combining block based fractal coding and DCT. Signal Processing : Image Communications, 8.k 2sz 73-78 p [17] Zhao, Y. and Yuan, B (1994) Image compression using fractals and discrete cosine transform. Electronics Letters, 30k 6sz 474-475 p A témával

kapcsolatban további információk szerezhetők be az alábbi Internet címeken: [1] http://www.iteratedcom Michael F Barnsley Iterated Systems Inc nevű cégének honlapja. A szakdolgozatban ismertett tömörítési módszereket magas színvonalon megvalósító Fractal Imager és Fractal Viewer Windows alapú programok shareware változatait és sok további információt találhatunk itt. [2] http://inls3.ucsdedu/y/Fractals Yuval Fisher honlapja, a szerzőre szintén sokat hivatkoznak különböző a témával foglalkozó forrásokban. Sok információt és a témával kapcsolatos további linkeket találhatunk itt. [3] http://links.uwaterlooca A kanadai Waterloo egyetemen folyó a Natural Sciences and Engineering Research Council of Canada (NSERC) által támogatott Waterloo Fractal Compression Project kutatásainak eredményeit tartalmazó lapok. [4] http://spanky.triumfca/www/fractint Fractint Homepage Az azonos nevű program legutolsó verziói illetve kiegészítései

találhatók itt, sok kiegészítéssel. A program segítségével sokfajta mesterséges fraktál és IFS rajzoltatható. Az Internet böngésző programoknál ajánlott a fractal image compression kulcsszóra kerestetni. 5 8. SZÓMAGYARÁZAT 1 kromatikus : színes (9. oldal) izotrópikus : minden irányban azonos mértékben végrehajtott (változtatás) (10. oldal) 3 affin transzformáció : hasonlósági transzformáció (bővebben lásd a 3.2 alfejezetben) (10. oldal) 4 “Borel halmaz : A számegyenes ~ának nevezünk minden olyan számhalmazt, amely előállítható véges vagy megszámlálhatóan sok diszjunkt intervallum egyesítéseként; speciálisan intervallumnak tekintjük az egyetlen valós számot tartalmazó halmazokat is. A ~okból álló Ω halmazrendszer ún σ-gyűrűt alkot: megszámlálhatóan sok Ω-beli halmaz egyesítése és két Ω-beli halmaz különbsége is Ω-hoz tartozik. Minden ~hoz hozzárendelhetünk egy ún. Borel-mértéket : ha H ∈ Ω

és H = ∪Ij (ahol Ij véges vagy megszámlálhatóan sok diszjunkt intervallum), akkor H Borel-mértéke ∑µIj-vel egyenlő, ahol µIj az Ij intervallum hossza. ~nak gyakran csak olyan Ω-beli halmazokat neveznek, amelyek Borel-mértéke véges (vagyis amennyiben ∑µIj végtelen sor, akkor az konvergens numerikus sor).” 2 Matematikai kislexikon. (1972) Műszaki Könyvkiadó, Budapest 43 o Borel halmazok alatt képek esetén azonos kromatikus jellemzőjű pixelek halmazát, azaz homogén területeket értünk. (11. oldal) 5 Kód tér : Egy kód teret a kódszavaiban előforduló elemek halmazának megadásával definiálhatunk, például a {0,1} egy bináris kód teret jelent. Ekkor a kódteret felépítő lehetséges kódszavak : 00000, 11111., 10101, 11011110101001, (16. oldal) 6 metric : metrika, mérték (16. oldal) 7 contraction : zsugorítás, kontrakció (23. oldal) 8 random iteration algorithm : véletlen iterációs algoritmus (31. oldal) 9 collage theorem :

kollázs tétel (33. oldal) 10 kondenzációs IFS : A hagyományos IFS-hez hasonló alakzat, de a hozzátartozó transzformáció rendszer kiegészül egy w0 ún. kondenzációs transzformációval, amely minden B ∈ H(X) halmazt ugyanazon w0(B) = C kondenzációs halmazba képez le. Magyarul a kondenzációs transzformáció egy 0 kontrakciós tényezővel rendelkező kontrakciós leképezés, amelynek egyedüli fix pontja a kondenzációs halmaz. Kondenzációs IFS-ekre a hagyományos IFS-ekhez hasonlóan megalkotható az IFS és a kollázs tétel is, lásd [1] 4.4 és 48 alfejezetei (37. oldal) 5