1. Uvod

Prošlo je već 20 godina otkada su fraktana tehnika predstavljena u računalnoj grafici. Te ideje zasnovane su na matematičkoj teoriji nazvanoj IFS (Itreated Function Systems) koju je predstavio i razvio australski matematičar John Hutchinson 1981 godine. Ubrzo zatim Michael Barnsley, proširuje teoriju IFS uvođenjem Collage teorema koji govori koje uvijete treba zadovoljiti IFS ukoliko se njome žele generirati slike. To dakako otvara intrigantne mogućnosti. Ako je fraktalna matematika dobra za generiranje slika prirodnih oblika (drveća, oblaka, listova, planina,…), da li je njome moguće komprimirenje slika? Polazeći od neke date slike koristeći IFS tako da se generira orginalna slika(manje ili više točno), poznati je problem inverzije (problem kodiranja slike ) .1988 taj problem rješava tada vodeći student Barnsley-a , Arnaud Jacquin uvodeći modificiranu verziju IFS tz.Partitionet Itreated Function Systems (PFIS).Ideja Jacquina je vrlo jednostavna. Sliku koju želimo kodirati ne smijemo promatrati kao kolaž kopija cijele slike, već kao kolaž kopija manjih dijelova slike. Npr. zamislimo sliku planine i oblake nad njome, dio oblaka ne izgleda slično cijelom krajoliku kojeg čini planina , oblaci i nebo, već tu sličnost vjerojatno moramo pronaći nekom drugom oblaku ili u nekom drugom dijelu slike. Dakle cijela zamisao leži na traženju sebi-slični dijelova na slici …

Zamislimo da imamo poseban fotokopirni stroj koji ulaznu sliku kopira tako da je dvostruko umanji i umnoži tri puta , kao što je to prikazano na slici 2.1

prema image-u iz slike 2.2.c tz. Sierpinski trokut. Ta konačna slika naziva se atrractor za taj fotokopirni stroj. Također se može primijetiti da ta konačna slika – attractor nije promijenjena procesom ,jer otkad je formirana od tri reducirane kopije od sebe same, ona ima taj detalj u svakom stupnju – to je fraktal. Fotokopirna mašina proizvodi slike sebi-slične nazvane fraktali.Općenito kažemo da je neki skup F fraktal ako ima slijedeća svojstva:

• Ako F ima detalje u svakom stupnju
• F je (točno, aproksimativno, ili statistički ) sebi-sličan
• «Fraktalna dimenzija» od F je veća od njegove topološke dimenzije
• Ako postoji jednostavan algoritam koji opisuje F

Vratimo se fotokopirnoj mašini uz primjedbu,sve dok krajni rezultat fotokopirne mašine koja radi u povratnoj vezi određen na način kako se transformira ulazna slika u kopiju, potrebno je samo opisati te transformacije da bismo dobili odgovarajući attractor. Različite transformacije vode do različitih attractora , sa tehničkim ograničenjem da transformacije moraju biti kontraktivne – a to je, da dane transformacije pridružene bilo kojim dvjema točkama u ulaznoj slici moraju dovesti bliže te točke na kopiji. Osim tog tehničkog ograničenja,možemo odabrati transformacije bilo kojeg oblika. U praksi, odabirom transformacija oblika

dovoljno je da izgeneriramo veliki i zanimljivi set attractora. Takve transformacije zovemo afine transformacije ravnine, i svaka može rastezati, skalitati, kositi(naheriti), rotirati i translatirati ulaznu sliku (image)

Svaka afina transforacija w_i je definirana sa šest parametara, a_i , b_i , c_i , d_i , e_i i f_i koja ne zahtijeva puno memorije za pohranu . Paprat može biti pohranjena sa 4 transformacija * 6 parametara za transformaciju * 32 bita za parametar = 768 bitova, dok pohranjivanje paprati kao kolekcije piksela, zahtijeva mogo više memorije( najmanje 65,536 bitiva za rezoluciju prikazanom slikom 2.3 ). Kompresijski omjer (ratio) iznosi 65,536/768= 85. 33

Ali kako pronaći potrebne parametre za bilo koju danu sliku i na taj način je kompresirali? (već ranije spomenuti problem inverzije). Barnsley-jev san je bio ponaći algoritam za računanje tih parametara. Međutim, slike koje nalazimo u prirodi uglavno su vrlo neprikladne za generiranje koristeći afine transformacije, a tome je tako jer slike iz prirode nisu upravo sebi-slične(self-similar ) tj. nisu fraktalne strukture. Tako Barnsley-jev san se nije ostvario. Međutim, postoje trikovi kojima je moguće riješiti problem inverzije. Pitanje je samo koliko su oni dobri u kodiranju slika. No prije svega treba objasniti Iterated Function Systems zato što je Fraktalna Kompresija slika igrađena na njoj.

Ponašanje fotokopirne mašine možemo opisati pomoću matamatičkog modela Iterated Function systems (IFS). Iterirani sistem funkcija sastoji se od kolekcije kontraktivnih afinih transformacija. Ta kolekcija transformacija definira mapu W

Mapa W nije pridružena ravnini, već je pridružena skupovima – a to su zbirevi točka u ravnini. Za neki ulazni skup (ili sliku) f, možemo izračunati w_i za svaki i (to odgovara stvaranju reduciranih kopija od ulazne slike f ), uzmemo uniju tih skupova(to odgovara načinu na koji se sklope reducirane kopije) i dobijemo novi skup W(f)(izlazna kopija ). Nazovimo podskupove ravnine imgesima(imiđima). Hutchinson je dokazao vrlo važno svojstvo IFS-a: ako je w_i kontraktivna u ravnini, tada je W kontraktivna na prostoru(zatvorenih i ograničenih) podskupova ravnine. Hutchinson-nov teorem na govori, da ako imamo kotrahirajuću mapu na prostoru image-a , tada postoji poseban image tz . attractor označen sa x_W , sa slijedećim svojstvima:

1. Ako dovedemo attractor na ulaz fotokopirne mašine , izlaz će biti jednak ulazu; image je fiksan, i attractor x_W je fiksna točka od W.

W(x_W)= x_W = w₁ (x_W ) U w₂(x_W ) U , . . . U w_n(x_W ) 3.1

2. Za neki ulazni image f₀ , možemo pokrenuti fotokopirnu mašinu jedanput da dobijemo prvu kopiju f₁ = W(f₀), dvaputa da dobijemo drugu kopiju f₂ = W(f₁) = W(W(f₀)) =W^o2(f₀), i tako dalje . Sa superskriptom _"o" označavamo da se radi o iteracijama : W^o2(f₀) označava kopiju nastalu drugom iteracijom. Attractor x_W koji je nastao iteriranjem mape W kada n teži prema beskonačnosti, je ustvari limit skupa W^on(f₀)

x_W = f_oo = lim_{n-> oo} W^on(f₀)

koji ne ovisi o izboru f₀

3. x_W je jedinstven. Ako pronađemo bilo koji skup f i transformacijsku mapu W da vrijedi W(f) = f , tada je f attractor od W; f = x_W . To znaći da će samo jedan i isključivo jedan skup zadovoljavati jednakost danu pod 3.1.