Tehnici Fractale - Compresia Datelor

Fractalul.Definitie.Caracteristici

Un fractal este o figură geometrică fragmentată sau frântă care poate fi divizată în părți, astfel încât fiecare dintre acestea să fie (cel puțin aproximativ) o copie miniaturală a întregului. Termenul a fost introdus de Benoît Mandelbrot în 1975 și este derivat din latinescul fractus, însemnând "spart" sau "fracturat".

Fractalul, ca obiect geometric, are în general următoarele caracteristici:

- Are o structură fină la scări arbitrar de mici.

- Este prea neregulat pentru a fi descris în limbaj geometric euclidian tradițional.

- Este autosimilar (măcar aproximativ sau stochastic).

- Are dimensiunea Hausdorff mai mare decât dimensiunea topologică (deși această cerință nu este îndeplinită de curbele Hilbert).

- Are o definiție simplă și recursivă.

Deoarece par identici la orice nivel de magnificare, fractalii sunt de obicei considerați ca fiind infinit complecși Printre obiectele naturale care aproximează fractalii până la un anumit nivel se numără norii, lanțurile montane, arcele de fulger, liniile de coastă și fulgii de zăpadă.

Istoric

Naşterea geometriei fractale i se datorează matematicianului suedez de origine franceză Benoit Mandelbrot odată cu publicarea, în 1977, a lucrării de referinţă Geometria fractală a naturii (Geometria fractală a naturii). În acesată carte, Mandelbrot subliniază că geometria clasică nu poate reprezenta geometria norilor, a munţilor, etc , în măsura în care o poate face geomatria fractală, cu liniile ei de coastă infinit dataliabile:

“Norii nu sunt sfere, munţii nu sunt conuri, liniile de coastă nu sunt cercuri iar scoarţa copacilor nu este netedă, nici fulgerul nu cade în linie dreaptă.” – Benoit Mandelbrot, Geometria fractală a naturii, 1977

Această observaţie va deschide noi orizonturi pentru matematicieni. Totodată, programatorii vor exploata tînăra ramură a matematicii pentru a genera lumi artificiale extrem de realiste.

În 1981, John Hutchinson pune bazele teoriei sistemelor de funcţii iterate (IFS-Iterated Function System), în lucrarea Fractali şi autosimilaritate (Fractals and selfsimilarity), însă de abia în 1988, cercetătorul american Michael Barnsley reuşeşte să formalizeze aceată teorie, demonstrînd celebra teoremă a colajului, în lucrarea Fractali pretutindeni (Fractals everyware).

Teorema colajului stabileşte în ce condiţii un sistem de funcţii iterate poate genera un fractal, fapt cunoscut sub denumirea de „problema directă” a fractalilor. Totodată, teorema colajului îl face pe Barnsly să ridice problema duală, „problema inversă”: fiind dată o imagine, putem determina un sistem de funcţii iterate care să o genereze?

Arnaud Jacquin. Jacquin imaginează o schemă modificată de prelucrare a imaginilor: Sistemele de funcţii iterate partiţionate (PIFS – Partitioned Iterated System Function), care vor face posibilă automatizarea completă a procesului de compresie. Algoritmul utilizat nu era deloc sofisticat, ere extrem de lent, dar complet automatizat şi dărîma visul cercetătorilor în domeniul compresiei: o rată de 10000:1, fără pierderi semnificative de informaţie.

Astăzi, toate încercările de a realiza un program de compresie fractală au la baza tehnica lui Jacquin, cu diverse îmbunătăţiri. Totuşi, singurul sistem comercializat de acest gen este produs de către Iterated System Incorporated. El se numeşte Images Incorporated şi rulează pe platformă Windows.