Tartalomjegyzék *

1. Bevezető *

2. Példák fraktál alakzatokra *

3. Fraktálok leírórendszere *

4. Fraktálok alkalmazása *

5. Fraktáltömörítési módszerek *

6. Egy fraktáltömörítő program megvalósítása *

7. Összefoglalás *

SUMMARY *

8. Irodalomjegyzék *

A szakdolgozat témáját a fraktálok illetve alkalmazási területeinek ismertetése képzi. A fraktálok világa egyre táguló, egyre több és több tudományág fedezi fel jelentőségét. Mivel meglehetősen új, érdekes és ismeretlen területtel állunk szemben, kihívásnak éreztem e témát feldolgozni.

A káosz és a fraktálok a matematika egyazon ágába tartoznak. Mindkettőt a nemlineáris rendszerek tanulmányozása közben fedezték fel. Az elnevezést Benoit B. Mandelbrot alkotta meg, aki elsőként foglalkozott fraktálgeometriával. Maga a szó a latin eredetű fractus kifejezésből származik, aminek jelentése: „törés”. A név arra utal, hogy törtdimenziójú alakzatokról van szó. Ez pedig azt jelenti, hogy le tud modellezni olyan alakzatokat, amelyek törtdimenzióval írhatóak körül. Jellemzőjük a nagyfokú önhasonlóság. Az alakzatok bármely részének nagyítása is hasonló alakzatokat eredményez, akármilyen mélységben is vizsgáljuk. A vizsgálatok szerint a káoszban megjelenő véletlenszerűnek tűnő geometriák a fraktálgeometria segítségével közelíthető. Könnyen modellezhető egy partszakasz, egy felhő, vagy akár egy fa növekedése. A modellezésen kívüli területeket a dolgozat 4. fejezetében ismertetem.

A második fejezetben bemutatok néhány fraktáltípust, amelyek a számítógépes demók kedvelőinek már ismerősek lehetnek. Ezt követően a fraktálok leírórendszereit veszem nagyító alá. Végül a lehetséges alkalmazások közül kiemelt fraktáltömörítéssel foglalkozok, amelyhez példaprogramot is készítettem.

Egyszerű módon készíthetünk fraktálokat Cantor sorozat kialakításával. A sorozat kialakításának első lépése egy zárt intervallum [0,1] három egyenlő részre osztása. Az így keletkezett három rész közül a középsőt elhagyjuk. A másik két intervallumot pedig újra felosztjuk, majd ezt a műveletet folytatjuk tovább. Grafikusan ábrázolva a Cantor halmazt a 2.1-es ábrán látható képet kapjuk. Ennek megrajzolására alkalmas egyszerű algoritmus forráskódja a következő:

A Cantor rekurzív függvény egy bináris fa bejárási módszerével vázolja fel az alakzatot. Egészen addig a szintig rajzol, amíg a téglalapok magasságuk miatt már nem jeleníthetőek meg.

Érdekes dolgot tapasztalhatunk, ha megvizsgáljuk annak a tartománynak a méretét, amelyet a kiemelt 1/3-ok méreteinek összesítésével érhetünk el, a végtelenségig végrehajtott műveletsor után.

Azaz az eltávolított intervallumok mérete pontosan megegyezik a kiindulási mérettel. A sorozat a fraktálok azon jellemzőjét hordozza magán, hogy nagyítás esetén egyre több részlet jelenik meg, a felbontás pedig finomodik.

A sokak által hópehelyként is ismert alakzat elkészítésének módja hasonlít a Cantor sor megrajzolásának módszeréhez. Az egyes szakaszok kivétele helyett azonban két újabbat helyezünk be, amelyek egy egyenlő oldalú háromszög oldalai lesznek. A megrajzolás lépéseit a 2.1-es ábrán láthatjuk.

A Sierpinski háromszög az egyik legérdekesebb és legkönnyebben megrajzolható alakzat. Készítésének első lépéseként egy háromszög mindhárom oldalának felezőpontját összekötjük. Az így keletkező négy háromszög közül a középsőt kell eltávolítani.

A Sierpinski háromszöghöz hasonló módszerrel rajzolható meg a Sierpinski szőnyeg. Ennek generálásához négyszögeket vagy köröket is használunk.

A Mandelbrot és a Julia halmazok a komplex síkon megjelenő objektumok. Ennek megfelelően leírásuk komplex számokkal végzett műveletek sorozataként adható meg. A végrehajtandó művelet:

A z egy olyan komplex szám, amely nulláról indul, és a halmazon belül - a műveletet rajta akárhányszor is elvégezve – nem éri el a végtelent. A C szám ugyancsak komplex mennyiség.

Vegyük sorba az összes C értéket a komplex számsík (-2 ; -1,25), (0,5 ; 1,25) téglalap által határolt területén, és mindegyik érték esetén addig végezzük a műveleteket, amíg az z értéke vagy a műveletek száma el nem ér egy adott számot! Ha a megadott számú műveleten belül nem érjük el a kijelölt z értéket, akkor a C pont a Mandelbrot halmazon belül van. Ha pedig ettől kevesebb iteráció elégséges, akkor ezen iterációk száma megadja a képpont színét. Az alábbi programrészlet segítségével rajzolhatunk ki egy Mandelbrot halmazt.

A Mandelbrot halmaz szélén az egyes részeket egymás után kinagyítva visszatérő, egymáshoz hasonló részeket – spirálokat, csápokat - fedezhetünk fel.

A fraktálok manuális és automatizált megjelenítéséhez, vizsgálatához definálnuk kell egy módszert, amely egyértelmű utasításokat tartalmaz matematikai vagy grammatikai formában. Tudnunk kell, hogy általános módszer nincsen, nem használható bármelyik metódus bármelyik típusú fraktál megjelenítésére. Éppen ezért sokan ezek alapján csoportosítják a fraktálokat, az alábbi csoportokat képezve:

Az Aristrid Lindenmayer által 1968-ban kidolgozott módszer eredeti célja a növényi fejlődés tanulmányozása volt. Az L-System (Lecture Notes Biomathematics) ezért alkalmas biológiai modellek felállítására. Segítségével könnyen leírhatunk egy teknőcgrafika lépéseit. Szimbólumai a toll mozgásirányának, lépései hosszának információit hordozzák.

Legyen az elfordulások szögmértéke 20°, a kezdeti irány pedig 90°. Most pedig alkossuk meg a szabályt! Lépjünk a tollal előre párat, majd forduljunk jobbra, lépjünk ismét előre, majd térjünk vissza a fordulás előtti pozícióba. Ez után forduljunk balra, lépjünk előre, és újra térjünk vissza. Szimbolikus formában leírva ez a következőképpen néz ki:

A forma felhasználásával készült ábra egy Y-ra hasonlít. Ahhoz, hogy eredményül egy fára emlékeztető ábrát kapjunk, a forma összes F szimbólumát helyettesítsük magával a formával. Az így kapott képlet:

A műveletet sokszor egymás után elvégezve a 3.1 ábrán látható képet kapjuk. Fraktál fa megjelenítésén kívül az L-System kiválóan alkalmas Koch görbe és Cantor sorozat leírására.

Az IFS kifejezés az Iterated System Function szavak rövidítéséből származik. Sokkal több területen alkalmazható, mint az L-System. Használata a tömörítésben, modellezésben ugyanúgy elterjedt, mint a művészetekben. Lényege az, hogy egy alakzaton – halmazon – transzformációk sorát hajtjuk végre. Ez a művelet az un. affin transzformáció, amely egy lineáris transzformációból és egy transzlációból áll. Ezt az Euklideszi síkon a következő általános formában adhatjuk meg:

Az A 2x2-es mátrix a lineáris transzformációt, míg a T oszlopvektor a transzláció műveletét végzi. Az a, b, c, d, e és f konstansok különböző megválasztása különböző eredményekhez vezet, ám vannak olyan elemi affin transzformációk, amelyek segítségével bármilyen összetett transzformáció megvalósítható. Ezeket az 1. táblázatban foglaltam össze.

Az alakzatokra (illetve azok pontjaira) alkalmazott affin transzformáció, amennyiben a konstansokat megfelelően választjuk meg, kontrakcióval jár. A sorozatban végrehajtott transzformációk hatására pedig az alakzat pontjainak koordinátái a tér egyetlen pontja felé kezdenek konvergálni. Ez az affin transzformáció fix pontja, amely véges méretű felbontás esetén fizikailag létezik, látható. Másképpen az IFS attraktorának is nevezzük azt a halmazt vagy fix pontot, amelyhez a rendszer tart.

Az Iterált Függvény Rendszerek ilyen és ehhez hasonló kontrakciós leképzések felhasználásával állítják elő a képet. Ez alapján, ha az IFS-t definícióval akarjuk meghatározni, a következőket mondhatjuk:

Két alkalmazását mutatom be. Az első az előző fejezetben már megismert Cantor sorozat, amelyet két transzformáció segítségével írhatjuk le:

Itt w₁ és w₂ is kontrakciós leképzés. Az attraktor maga a Cantor halmazbeli elemek összessége. Ha az IFS-t egy harmadik () transzformációval is kibővítenénk, az attraktor már magában foglalná a tér összes elemét, azaz maga a tér lenne.

A másik, jól ismert alkalmazása az iterált függvény rendszereknek a Sierpinski háromszög. Ez az alábbi három affin transzformáció sorozataként állítható elő:

Kétféle módszer kínálkozik arra, hogy az IFS segítségével fraktálokat készíthessünk. Az egyik, a véletlen iterációs algoritmus. Ennek lényege, hogy a kép egy területén kijelölt pontot a képen belülre affin transzformációval képzett kisebb méretű kép megfelelő részére illesztjük. A megfelelőségen itt a transzformáció által meghatározott pontot értjük. Belső képből annyi létezik, amennyi leképzési szabályt alkalmazunk az alakzatra. A Sierpinski háromszög esetén például háromból épül fel. Ezek közül véletlenszerűen választunk ki egyet. A véletlenszerűség befolyásoló tényezője egy számérték, amely mindegyik transzformációra egyenként meg van adva. Ismét a Sierpinski háromszöget véve példaként, a valószínűség mindháromnál azonos, 1/3-val egyenlő. Az első pontbehelyezés után a következő transzformált képbe kell a pontot tenni, annak megfelelően, hogy az eredeti képben hol helyezkedik az első transzformáció során kirajzolt pont. Ezt a műveletet kell elvégeznünk újra és újra.

A másik módszert determisztikus metódusnak hívják. Ezt használva sokkal több memóriára és időre lesz szükségünk. Működésének mechanizmusa teljes képek másolásából áll. Ezt a módszert példán keresztül részletesebben is ismertetem.

Legyen a kiindulási képünk egy papagáj fekete-fehér nyomdai fotója és legyen három transzformációnk. Az előbbi a 3.3 (b) ábrán, az utóbbiból létrehozott három keret az (a)-n szerepel. Első feladatunk, hogy a három kis keretbe transzformáció segítségével behelyezzük a papagáj képét. Ez után, az így létrejött (c) képet mentsük el. Most (a) mindhárom keretébe rakjuk be az elmentett képet. Ezt a műveletet folytassuk, amíg két egymás után elkészült kép között már nem látunk különbséget. Ebből az tűnik ki, hogy véges számú iteráció elvégzése után a felbontástól függően a kép már nem változik. Ez a transzformáció fix képe, a három affin transzformáció attraktora, az azok által létrehozott fraktál (g és h ábra). Ha megvizsgálnánk még egy ábrát, mondjuk egy szekrény képét, azt látnánk, hogy az iterációk végrehajtása után teljesen ugyanahhoz a fraktálhoz jutunk. Tehát a fraktál független a kiindulási képtől.

Nem esett szó arról, hogy mi történik abban az esetben, ha a transzformációk által létrehozott keretek, képek fedik egymást. Ha egy bit színmélységgel dolgozunk, akkor a háttértől elütő szín a meghatározó. Amennyiben két vagy több keret közül akár egyik is ilyenre színezi, a többi már nem módosítja.

Mi azonban a feladat, ha nem egy bites a színmélység, ha több szürkeárnyalat van, netán színes a kép? Szürkeárnyalatok esetén a közös pont intenzitására minden azt érintő keret befolyásolólag hat. A véletlen iterációs módszernél említett véletlen érték tulajdonság itt is szerephez jut. Ez, mint egy szűrőtényező viselkedik. Mindegyik affin transzformáció csak ezen értékének arányában módosítja a közös pontot. Ugyanez az elv érvényes a színes képekre is, ahol akár az RGB akár a YUV összetevőket egyenként összegezhetjük.

Ma már bizonyított, hogy a természet kedveli a fraktálalakzatokat. Átszűrődési (perkolációs) fürtöknek nevezett fraktálokat ismertek fel például a szilárd szemcsézetű anyagokban átáramló folyadékok (így a talajban szivárgó víz vagy az őrölt babkávé szemcséi között átszűrődő feketekávé) mintázatában. A korom, a kolloidok és egyes polimerek szintén fraktáloknak tűnnek. Ugyancsak fraktálok jelennek meg légbuborékok olajban történő mozgásakor, bizonyos kristályok növekedésekor, vagy a villámcsapásokra emlékeztető elektromos kisülésekben. A felhők szabálytalan mintázata és a tengerpartok csipkézettsége is szinte bizonyosan fraktálnak tekinthető. A természeti fraktálok létezésére vonatkozó bizonyítékok gyarapodtával a kutatók vizsgálni kezdték a fraktálok kialakulásának kérdését. 1981-ben Thomas A Witten III (Exon Research and Engineering Company) közreműködésével a gödöllői FM műszaki intézet kidolgozott egy fraktálnövekedési folyamatot, és azt diffúzió által szabályozott felhalmozódásnak (diffusion-limited aggregation,vagy röviden DLA) nevezte el. A modell szerint egy bizonyos fajta rendezetlen és megfordíthatatlan növekedési folyamat egy különleges fraktáltípust eredményezhet. Az elmélet abból a szempontból is vonzó, hogy fogalmilag egyszerű és számítógéppel könnyen modellezhető.

A DLA-modell jelentősége abban áll, hogy rámutat a fraktálok és a növekedés közötti kapcsolatra. A természeti tárgyak sokféleképpen növekedhetnek. Egy ideális kristály például az egyensúlyi állapot közelében növekszik: sokféle elrendeződést "kipróbál", míg csak rá nem talál a legstabilabb szerkezetűre. Amikor egy növekvő kristályhoz egy újabb molekula kötődik, általában csak egy sor lehetőség végigvizsgálása után kapcsolódik az arra alkalmas helyre; az egyensúlyi kristály lassan és állandó átrendeződések közepette alakul ki. A legtöbb valódi növekedési folyamat azonban nem rendelkezik ennyi idővel. Az élet például, bármely formáját nézzük is, nem egyensúlyi folyamat. A fraktálok nagy részének növekedése ugyancsak az egyensúlytól távoli.

Képzeljük el, hogy egy részecske fürt a következőképpen növekszik: ha időről időre egy-egy részecske hozzáér a növekvő képződményekhez, egyszerűen odatapad, anélkül, hogy más helyekkel próbálkozna. Az ilyen folyamatot nevezzük halmozódásnak. A halmozódás a nem-egyensúlyi folyamatok szélsőséges esete, mivel egyáltalán nem megy végbe átrendeződés. Tegyük fel, hogy a részecskék véletlenszerű bolyongással jutnak el a fürt közelébe: az egymást követő lépések nagysága és iránya véletlenszerű. A részecskéknek ezt a véletlenszerű bolyongással történő felhalmozódását nevezik DLA-nak, amelynek tárgyalása túlmutat a szakdolgozat keretein.

Guastello S.J. 1995-ben kiadott művében, a Chaos, catastrophe and human affairs: Applications of nonlinear dynamics to work, organizations, and social evolution (Káosz, katasztrófa és emberi ügyek: A nemlineáris dinamika alkalmazásai a munkában, szervezetekben és szociális fejlődésben) számtalan modellt állít fel élő rendszerek struktúráinak vizsgálata céljából, azzal a nem titkolt céllal, hogy jövőjükre vonatkozóan is jóslásokba bocsátkozhasson. Az egyik gyakorlati témájában a káosz attraktorainak szerepét például a munkanélküliségi mutató változásában is bizonyítani próbálta.

A közgazdaságtanban megállapított egy minimális munkanélküliségi érték, amely rövidtávon az infláció (és ebből kifolyólag a banki kamatok) által szabályozható, illetve viszont. Ezen érték szerint a munkanélküliség stabilis értéke 6,7% körül mozog. Statisztikai adatokat felhasználva Guastello nemlineáris rendszere a 6,6% felé konvergált. Ellenőrzésképpen a transzformációkat visszafelé is elvégezve visszakapta a statisztika első számadatát, a kiinduló feltételt. Sikerült hát olyan modellt felállítania, amely alkalmas egy statisztikailag hosszútávon stabilizálódó gazdasági mutató számítására.

Érdekes különbséget képezni emberek ösztönös, érzelmi és megfontolt, mérlegelt válaszai között, amikor egy szociális helyzetet változtató “furcsa attraktor” hurkába kerülnek. Természetesen az emberekre inkább az előbbi jellemző, a változások által hozott kényelmetlenségre dühvel, a rizikóra félelemmel reagálnak, megpróbálván ellenállni. A legtöbb ember érzelmekkel reagálva nem képes (vagy nem is akarja) látni a kreatív lehetőségeit vagy hosszútávú előnyeit annak a fraktál fejlődésnek amely ifjúkorában nem hoz mást csak kényelmetlenségeket. Az önszervező szociális rendszerek mindig megadják magukat az érzelmileg vonzó stabilitásnak, ami egy vulkán kupakja, és ami jól működik a katasztrófa pillanatáig.

Ezért egy jól működő rendszer nyitott a kritikákra, és ha nem is próbálja irányítás alá vonni a Divergencia által előidézett változásokat, azokat megérti és gyorsítja. A Complexity International magazin által felhozott példák között szerepelt az Európai Unió mintájára létrehozandó orosz, belorúz, kazakhsztán és kirgisztán szövetség, amely az orosz elnök tanácsára Bulgáriával is kibővülhetett volna, ám a bulgár lakosság tiltakozásával találkozott. A változás elutasítása miatt tombol jelenleg is a Balkánon háború.

A művész, aki saját magát “fraktalista”-nak hívja, meglepően sokat örököl a művészet történetéből. Számtalan művész alkalmazta ugyanis a technikát, még ha nem is ismerte definicióját, matematikai hátterét. Olyan neveket érdemes itt megemlíteni, mint például Vincent Van Gogh, aki energia sűrű örvényeibe burkolta tárgyait, vagy akár Escher rekurzív geometriái. Az építészetben kiemelkedő alkotásnak számítanak a Párizsi Operaház részletes barokk díszítései, vagy a gótikus katedrálisok ismétlődő ívei.

Vegyük a véletlenül képződő önhasonlító fraktálokat (mint amilyenek a fák és a hegyek) és a számítógép által generált nemlineáris fraktálokat (például a Mandelbrot halmazt), ahol a minták különböző méretekben ismétlődnek. Ha a Mandelbrot halmaz azon spirális, érdekes formáit tekintjük, amelyek a halmaz végtelen partvonala körül örvénylenek, hamarosan kiszámíthatónak tartjuk őket. Természetesen ez a kiszámíthatóság inkább pszichológiai okokra vezethető vissza. Egy idő után e tájak szemlélése unalmassá válik.

Ha a Mandelbrot halmazt egy igazi műalkotással hasonlítjuk össze, mint amilyen Picasso képe, vagy akár Shakespeare műve, rájöhetünk, hogy az utóbbiak legyenek akármelyik periódus, stílus vagy kultúra munkái, megőrzik vitalitásukat szemünkben, akárhányszor is találkozunk velük. A nagyszerű költemény, festmény mindig új élményt nyújt. Mona Lisa mosolya például örök talány marad.

Természetesen a fraktálművészet nem csak festészetből, építészetből és szobrászatból áll, a fraktálok hatást gyakorolnak a zenére is. A fraktálzene teória az úgynevezett “rózsaszín zajon” alapul. Tapasztalatok szerint ez sokkal kellemesebb a fülnek, mint a fehér vagy barna zajok, amelyek közül az első túl véletlenszerű a második pedig túlzottan merev. Mandelbrot tanulmánya alapján az idegrendszer perifériájának zaja fehér típusú, de az agy belső felé haladva rózsaszínűvé válik.

A fraktálokat alkalmazzák a kép és hangfeldolgozás területén is. Egyrészt felismerésre kiválóan alkalmas, hiszen a felismerendő hang vagy kép fraktálokra való felbontás után egy matematikai képletben leírható, így képletek paramétereinek összehasonlítására redukálódik le a feladat. Használható az elmélet tömörítésre is, hiszen a képletek paraméterei valószínűleg kevesebb helyet foglalnak el, mint maguk a nyers adatok. Természetesen mindegyik alkalmazásnak komoly matematikai háttere van. Algoritmusok ugyan léteznek de sok közülük egyenlőre nem automatizálható.

A szakdolgozat kiemelten foglalkozik a témán belül az állóképek tömörítésével. A legjobb fraktál alapú képtömörítő programok azonos hűség mellett kisebb méretet érnek el, mint a jelenleg legjobb tömörítési arányúnak tekintett JPEG. Hatalmas a különbség nagy hatásfokú (kis hűségű) tömörítés esetén, amikor a fraktál file a JPEG file akár tized része is lehet.

Távlati lehetőségek kiaknázhatatlan tárházát képzik a fraktálok. Ezek közül csak néhány példát említenék:

• A hullámtörők és a partvédő művek fraktális szerkezetű hullámcsapdák alkalmazásával védhetők. A stúdiókban felépített úgynevezett süketszobák, valamint a jó hang- és hőszigetelő közegek - a kőzetgyapot, a vatta stb. - szintén fraktálszerkezetűek.

• Az elektronikában alkalmazott kondenzátorok, a kémiai elemek, az akkumulátorok, a szűrők és a hőcserélők hatásos felülete fraktális struktúrák kialakításával növelhető.
• Az idegsejtek fraktális felépítéséből, összekapcsolódási szerkezetéből talán egy új, nagy biztonságú információátvitel egy lehetséges topológiája következik.

Elsõ lépésben a tömörítendő képet, felületét teljes mértékben lefedõ, adott méretű négyzetekre, úgynevezett domain blokkokra kell felbontani. A domain blokkok ideális mérete függ a teljes kép méretétől, illetve attól, hogy milyen minőségben és mekkora számításra szánt idővel szeretnénk reprodukálni. Az ajánlások szerint használhatunk 4x4, 8x8, 16x16 vagy akár 32x32-es blokkokat is. A kis méretű domain blokkok használatának előnyei közé tartozik, hogy geometriailag könnyen elemezhetőek, osztályozhatóak, gyorsan hasonlíthatóak és pontosabb tömörítést tesznek lehetővé. A 8x8 és nagyobb domain blokkokat az egyenletes képi területek redundanciájának jobb kihasználása és nagyobb tömörítési arány jellemzi.

A következő lépés a kép domain blokkoknál nagyobb területű, range blokkokra való felosztása. A range blokk mérete általában kétszerese domain blokkénak. A range blokkokat ezek után negyedére zsugorítjuk, amivel eléri a domain blokk méretét. A kicsinyített domain blokkokról másolatokat készítünk, és rajtuk olyan különböző transzformációkat végzünk, mint a forgatás, tükrözés és az árnyalatok, fényességi értékek megváltoztatása.

Ezután minden domain blokkhoz meghatározzuk a hozzá legjobban hasonlító zsugorított range blokkot. A kiválasztott blokk koordinátáit és a rajta alkalmazott transzformáció típusát, együtthatóit mentjük el a tömörített állományba. Az állományban megjelenő adatok összessége pedig az IFS kódja.

Felmerül a kérdés, hogy hogyan hasonlítjuk össze a blokkokat. Ennek egyik módszere az RMS (Root Mean Square) számítás. A két blokk pontjai különbségének négyzeteit összegezzük, és ebből vonunk gyököt. Minél kisebb az érték annál jobban hasonlítanak egymásra. Ennek képlete az alábbi:

A képletben szereplő B a domain blokk mérete, u és v a két kép pontjainak fényesség értéke, illetve színes képek esetén valamelyik összetevő intenzitása.

Barnsley alapvető algoritmusa még nem osztotta fel a képet range blokkokra, helyette az egész képből képzet fraktálokkal (mint a 3. fejezetben bemutatott papagáj) hasonlította össze a kép részleteit. Nem szigorú domain blokk felosztásra kell gondolnunk, inkább szabad szemmel is látható hasonlóságokra. Barnsley átfedésekkel is dolgozó IFS-t használt. Ezek miatt a folyamatot nem lehetett automatizált algoritmussal megoldani.

Arnaud Jacquin Barnsley tanítványaként rájött arra, hogy egy képnek nem az egész képből felépülő fraktálokból kell állnia. Vizsgálatai rámutattak arra, hogy jobb eredmény érhető el, ha a kép több darabját használjuk fel. Tőle származik tehát a fent ismertetett módszer elméleti alapja. Az alapvető algoritmus, amely minden domain blokkot minden range blokkal összehasonlít az alábbi módon épül fel:

1. A “potenciális válaszok” halmazának kiválasztása adott problémára.
2. Az alkalmas “megfelelés” mértékének tisztázása ezen halmazon.
3. Genetikus operátorok (pl: párosítás és mutációs) definálása.

1. Genetikus operátorok
2. A felvetődött probléma vázlatos leírása
3. A megfelelést vizsgáló függvény
4. Inicializálás

A populáció összes egyedét megvizsgáljuk, és az azok közül legalkalmasabbakat választjuk ki reprodukálásra. Az új elemeket úgy kapjuk, hogy a kiválasztott egyedekre alkalmazzuk az operátorokat. Két egyed szükséges a párosítás operátorhoz, amely a kettő különbségéből képez új elemet. A mutációs operátor viszont egy elem bizonyos részeinek, jellemzőinek módosítására alkalmazható.

A maradék – reprodukálásra alkalmatlan – egyedet pedig kicseréljük az újakkal. Ezzel újabb generációt hoztunk létre, amely ha nem alkalmas a feladat kijelölt közelítési szintű megoldására, új reprodukálásra szorul, azaz az algoritmust tovább kell folytatnunk.

Maga az algoritmus tehát a potenciális válaszok populációjának generációit fogja iterálni, minden szintnél kiválasztva az alkalmas egyedeket és felhasználva őket új egyedek létrehozására a genetikus operátorok segítségével. A problémát itt az alkalmas egyed kiválasztása jelenti. A biológiai természetes szelekcióhoz hű szimuláció mindig a “legfittebb” egyedet produkálja újra, amelynek felismeréséhez valamiféle mértékre van szükségünk. A mérés elvégzésére szolgáló függvényben felhasználhatnánk a Hutchinson metrikát (Barnsley 1988-as publikációja), de ez több ok miatt sem igazán alkalmas automatizált, számítógépes feldolgozáshoz. E helyett inkább apró részletekre bontjuk a generáció elemeit, és a négyzet alakú részletekben szereplő pontok számát hasonlítjuk össze, majd ezeket a különbség értékeket összegezzük. A populációban ideális fittséggel rendelkező egyed fittségi mérőszáma magasabb, az egyhez közelít. Az általános kiválasztási szabály pedig:

A tömörített állományban eltárolt adatokból a képet többszöri iterációval nyerhetjük vissza. Először két - a kép méretének megfelelő - memóriatömböt kell lefoglalnunk. Az egyik a domain, a másik pedig a range blokkok tárolásához szükséges. Ezeket először felosztjuk a megfelelő méretű területekre, majd a range blokk memória területére egy tetszőleges képet helyezünk.

A tömörítést itt is a kép felosztásával kezdődjük, ám nem feltétlenül azonos, egymás mellett helyet foglaló részleteket veszünk. Okosabb módon kell a képet áttekintenünk, és akár egymást is lefedő domain blokkokat képeznünk. Megtehetjük azt is, hogy akár az egész képet tekintjük részletnek, és a későbbiekben bontjuk további darabokra.

A fraktálokat egy listába foglaljuk, majd ezek közül választjuk ki azt, amelyik a legjobban hasonlít az adott képrészletre. Ezután addig változtatjuk a fraktál paramétereit, amíg el nem érjük a megfelelően hasonló képet. A kimeneti állományba csak a fraktál típusa és annak paraméterei kerülnek.

A szoftver Windows 95 operációs rendszert, vagy Win32 környezetet igényel. A választott programnyelv a Borland C++ 4.5, melyben az ObjectWindows támogatás és a Win32-es környezet megfelelő lehetőségeket biztosít egy ehhez hasonló alkalmazás elkészítéséhez. A program 8 bit mélységű szürkeárnyalatú TGA formátumú képek nagy hatásfokú be- és kitömörítésére alkalmas. Szabályozható a kitömörítés minőségi tényezője.

A program projektként tölthető be az IDE-be. A projekt központi állománya a compfrac.cpp amely a főablak menürendszerét kezeli. A be- és kitömörítést segítő közös rutinok a fractal.h állományban helyezkednek el, míg a comp.h és a decomp.h állományok csak a nevükből is következő egy-egy funkciót tartalmazzák.

Az állományok kiválasztása után hívjuk meg a compress függvényt. A függvényben először beállítjuk a zsugorított range és domain blokkok méreteit. Ezek jelenleg kötötten 4x4-esek, de az összehasonlító és átlagoló rutinok átírásával könnyen megvalósítható egy nagyobb blokkméret is. Mind a domain, mind a range blokkok, sőt a kép leírását is egy-egy struktúra hordozza (pictureblock). Ennek eleme az előbb beállított x és y méret, a pixelekben kifejezett hossz és egy mutató ami az első képpontra mutat abban a bufferben amit dinamikusan foglalunk – a következő lépésben.

A be- és kimeneti állományok megnyitása után beolvassuk a TGA fejlécet, és a kép adatait. Ez után a kép leátlagolása történik, minden egyes range blokkot felére redukálunk, egyszerű átlagszámítással. Gyakorlati megfontolások alapján a kép intenzitását is módosítjuk, minden pont fényességét ¾-ére csökkentjük.

Mivel a betömörítési idő nagyon hosszú, egy nem modális ablakot nyitunk, amelybe folyamatosan kiírt százalékértékek tájékoztatást adnak a tömörítés állapotáról. A számítások végzése alatt az ablakobjektumok egyetlen eseménymetódusa sem érhető el, ezért a rendszer “nem felel” státuszt jelezhet. Ezen ok miatt is szükség van egy hasonló megoldásra, ami tájékoztatást ad arról, hogy a program nem “fagyott le”.

Az aktuális domain blokkot bemásoljuk egy erre a célra elkőkészített bufferbe, majd kiszámoljuk pontjainak egyszerű intenzitás átlagértékét. A belső ciklus ugyanezt teszi egyenként az összes zsugorított range blokkal. A range blokk intenzitásának mértékét kivonjuk az aktuális domain blokk átlagából, és az eredményt arra használjuk fel, hogy módosítsuk a range blokk intenzitását. Ezek után elkezdjük elvégezni a kijelölt transzformációkat. A programban a range blokkot nyolcféle műveletnek vetjük alá (flip). A műveletet leíró szám három alsó bitje fontos, ezek képviselnek egy-egy transzformációt, úgy mint x, y irányú tengelyre valamint az átlókra való tükrözést.

Minden egyes transzformáció után megvizsgáljuk, hogy mennyire tér el az átalakított range blokk a domain blokktól. A differenciát vizsgáló (difference) függvény a pontok különbségének négyzetösszegét képzi, és ezzel tér vissza. Amennyiben ez kisebb, mint az előző minimum - illetve az első összehasonlítás előtt beállított kellően nagy szám -, a range blokk x, z koordinátáit, fényességi eltolását és a rajta végrehajtott transzformáció kódját eltároljuk. A belső ciklus végén a legjobban hasonlító blokk adatait tárolják a változók, amelyeket a könnyű kezelhetőség végett struktúrába foglalunk (affinmap). Ezt a struktúrát mentjük le a kimeneti állományba.

A külső ciklus leforgása után a tömörítés végéhez értünk, a file a kép helyreállításához szükséges összes információt tartalmazza. A tömörített állomány mérete csak a betömörítendő kép dimenzióitól függ. Minden affin transzformációs blokk 7 bájtot foglal, a kép méretei 4 bájton írhatóak le. Ez alapján a következő képlet körülbelül megadja a file méretét:

Azért kell körülbeliségről beszélnünk, mert az átlapolódások miatt egy teljes sorral vagy oszloppal nőhet a hossz. Ha a fenti képlettel számolunk, akkor egy tömörítetlen képpel szemben 50 %-os arány érhető el. Azonban ha megvizsgáljuk a kimeneti állományunkat, jól láthatjuk, hogy azon például egy huffman tömörítést elvégezve még jobb, akár nagyságrendekkel is eltérő eredményt érhetünk el.

A kitömörítést a decompress függvény végzi, amely az állományok megnyitása után beolvassa a kép méreteit tartalmazó első két adatot. Ezt követően a kimeneti állományba helyezi a TGA fejlécet. A tömörített file teljes méretéből meghatározzuk az affintérkép struktúrák számát:

A range illetve domain blokkok száma természetesen ugyanennyi lesz. A transzformációs térképstruktúrák (affinemap) számára egybefüggő memóriaterületet foglalunk le, amelyre az affinelist fog mutatni. Az adatok beolvasása után a bemeneti file már le is zárható.

Most értünk a ciklusokhoz. A külső ciklus az iterációk megfelelő számát biztosítja. Ez a szám a felhasználó által definált. Az első művelet, amelyet elvégzünk, az a kép leátlagolása, amivel egyben az elméleti range blokk buffer területére másoljuk a képet. A mapptr mutató itt kapja meg alapértékként az első affintérkép struktúra címét.

A belső ciklus sorban végighalad a teljes kép összes domain blokkján, mindegyikhez megkresve a térkép által hozzárendelt zsugorított range blokkot. A zsugorított range blokkot a leátlagolt képterületről vesszük ki. Először az intenzitását toljuk el a megfelelő mértékben, majd végrehajtjuk rajta a kívánt transzformációt. Az ezek után létrejött blokkot másoljuk a teljes kép területére. A mapptr mutatót megnöveljük, ami típusa miatt a következő affintérkép struktúrára fog mutatni.

A ciklusok befejeztével, a teljes kép területen rendelkezésre álló – feltehetően – az eredeti képtől nem sokban különböző blokkot a kimeneti állományba mentjük. A kitömörítési idő lényegesen – nagyságrendekkel - rövidebb, mint a betömörítésre szánt. Nem sokkal marad el egy JPEG állomány kitömörítési idejétől, tehát olyan helyeken is fel lehet használni, ahol az időtényező meglehetősen fontos.

Mivel a program TGA formátumot képes konvertálni, erről is szükséges egy rövid ismertető. A tga.h header állományban definált struktúraelemek a következő leíró adatoknak felelnek meg.

A fenti adatokból felismerés szempontjából DEPTH a legfontosabb, mert ennek 3-as értéke jelenti azt, hogy szürkeárnyalatú képpel állunk szemben. A program természetesen a WIDTH és a HEIGHT mezőket is használja.

• Ismert fileformátumok közötti konvertálás lehetővé tétele. Azaz a program be tudjon olvasni GIF, JPEG, BMP stb. állományokat is.
• Beállíthaó domain blokk méretek. Az alapbeállításként szolgáló 4x4-es blokkméret nagy képek esetén feleslegesen lassítja a feldolgozást. Érdemes lenne megvalósítani 8x8, 16x16 sőt 32x32-es blokkméretet is. Ezek közül a program automatikusan is tudna választani, ha a felhasználó így kívánja.
• Szines képek feldolgozásának lehetősége. Három intenzitásjellemző használata mellett lehetővé válna akár true color képek tömörítése is.
• Kettős tömörítés használata. A CIF file ebben az esetben nem az affintérkép struktúrákat tartalmazná, hanem annak sűrítményét. A file szerkezetét tekintve a legalkalmasabb erre a célra egy Huffman algoritmus.

A szoftver telepítésében az InstallShield Express van segítségünkre. A telepítő könyvtárból a SETUP.EXE-t kell elindítani, ami a telepítési folyamatot automatikusan vezérli. A feltelepített program ezután a startmenüből, vagy a compfrac.exe állománnyal indítható.

A képernyőn indítás után egy ablak jelenik meg, amelynek file menüje egyértelmű utasításokat tartalmaz. A compress menüpontot választva tömöríthetjük össze a 8 bit szürkeárnyalatú képet. Először az ezt tartalmazó állományt kell kiválasztanunk az előugró dialógus segítségével, majd a létrehozni kívánt file megnevezése jön. Ennek ajánlott .CIF kiterjesztésűnek lennie, amit a program fel is ajánl. A két file kiválasztása után kezdődik a tömörítés folyamata. Ennek százalékos állapotáról folyamatos információt szolgáltat egy megjelenő státuszablak. Előfordulhat, hogy a program nem válaszol a tömörítés ideje alatt, de amíg a státuszablakban változást látunk, a szoftver megfelelően működik.

A kitömörítés hasonló módon zajlik, amelyet a file menü decompress pontjának választásával indíthatunk. Először a tömörített CIF állományt majd a kitömörítés célpontját képző új file nevét kell meghatároznunk. A kitömörítés folyamatáról nem kapunk információt, mivel az meglehetősen rövid, azonban a művelet végén az eredményről értesít minket a program.

Az options menüpont választásával előugró dialógusablakban állíthatjuk be a kitömörítéskor elvégzendő iterációk számát. Minél magasabb ez az érték, annál szebb, az eredetihez hű képet kapunk. Az iterációk száma függ a kép méretétől is, nagyobb képhez érdemesebb nagyobb értéket választani. Az alapbeállítás 16, ami közelítőleg 200x200-as felbontás igényeinek általában megfelel.

A programot az exit menüpont választásával hagyhatjuk el. A help menü about pontjában pedig információt kaphatunk a szoftverről.

A szakdolgozatom témája a fraktálok és alkalmazásaik voltak. A munka elején ismertettem a tipikus és gyakran előforduló fraktálok matematikai alapjait. Ez után bemutattam két rendszert, amelyek a fraktálok leírására alkalmasak. A következő fejezetben ismertettem néhány alkalmazási területen betöltött szerepüket, úgy mint művészetek, kép- és hangfeldolgozás, szociológia és gazdaság. Ezt a képek tömörítésénél alkalmazott fraktáltechnológia leírása követte az 5. fejezetben. Ezeket a szabályokat alkalmazva készítettem egy, a fraktáltömörítést szemléltető programot, amely 256 szürkeárnyalatú képek tömrítésére alkalmas.

1. Benoit Mandelbrot
   The Fractal Geometry of Nature
   WH Freeman & Co., New York, 1983
1. Michael F. Barnsley
   Fractals Everywhere
   Academic Press
   1993, 1988
2. Michael F. Barnsley and Lyman P. Hurd
   Fractal fracimage/Image Compression
   AK Peters Limited
   1993
3. Yuval Fisher
   Fractal fracimage/Image Compression: Theory and Applycation
   Springer Verlag, New York
   1995
4. D.Saupe, J. Hart
   Fractal Models for fracimage/Image Synthesis, Encoding and Analisys
   SIGGRAPH’96, Course Notes XX, New Orleans
   1996.
5. Guastello S. J.
   Chaos, catastrophe and human affairs: Applications of nonlinear dynamics to work, organizations, and social evolution
   1996.
6. Nemoda Balázs
   Fraktál alapú képtömörítések
   Kandó Kálmán Műszaki Fősikola (szakdolgozat)
   1997.
7. Márkus Zoltán
   A fraktálok világa
   Kandó Kálmán Műszaki Fősikola (szakdolgozat)
   1996.

• http://glug.cs.uml.edu/~mgaona/Proposal/node4.html
• http://astsun.astro.virginia.edu/~eww6n/math/CantorDust.html
• http://www.csu.edu.au/ci/contents.html
• http://library.advanced.org/12740/cgi-bin/login.cgi
• http://www.rasip.fer.hr/research/compress/algorithms/adv/fraccomp