Compresia Fractala a imaginilor

Oprea Mihaita GabrielParaschiv Cristian

Grupa 341 A2

Geometria FractalaTrateaza modelarea matematica a obiectelor cu aspect

neregulat, fragmentat, fracturat. Urmareste sa identificeproprietati de asemanare dintre partile ce alcatuiesc un ansamblu ierarhizat si sa determine cantitativ aceastaautosimilaritate printr-un exponent fractal.

• Compresia imaginii este o tehnică utilizată pentru stocarea unei imagini vizuale care reduce volumul de informații digitalizate necesare stocării electronice a imaginii.

• Existenta unui numar foarte mare de formate ale fisierelor foto, implica existanta unui numar foarte mare de algoritmi de compresie

- BMP = BitMaP- JPEG = Joint Photographic Experts Group- PNG = Portable Network Graphic- TIFF = Tagged Image File Format- GIF = Graphics Interchange Format- etc

Compresia de imagini

Tipuri de compresie

Cu pierderi- presupune eliminarea unei parti

din informatia originala si înlocuirea ei cu informatie similara(dar nu identica) la decompresie

Fara pierderi- nu va lasa date în afara pachetului

de compresie (arhivei). Acest tip de compresie se aplică, de exemplu, textului, pentru că dacă ar fi altfel, aţi risca la decompresia unui text comprimat să găsiţi un alt text decât cel dinaintea efectuării operaţiei de comprimar

Metode de compresie

Desi exista un numar mare de formate grafice, practic sunt folosite doarcateva metode pentru codificarea datelor. Mai mult, exista doar catevametode conventionale pentru compresia datelor in vederea utilizarii unuispatiu cat mai mic la stocare. Algoritmul Huffman - Prin intermediul acestei tehnici, se urmareste ca de faptcaracterelor care apar mai des sa li se asigure un cod mai scurt iar celor cu frecventa de aparitie mai redusa sa li se asigure un cod de lungime mai mare. Aceste corespondente se inregistreaza intr-o tabela de conversie care va fi folosita la decodificare.

Compresia LZW - se incepe cu o tabela simpla, care asigneaza cate un cod fiecaruicaracter posibil (256 de intrari a cate 8 biti fiecare, de exemplu). In timpului desfasurariiprocesului, algoritmul construieste o tabela de coduri mai mare si mai eficienta adaugandcoduri noi pentru fiecare noua secventa de caractere.

Compresia aritmetica - foloseste coduri mai scurte pentru caracterele ce apar maifrecvent. Este o tehnica mult mai eficienta, care ca si LZW, comprima secventele de valori sinu valorile in sine. Ea se apropie foarte mult de limitele teoretice ale compresiei.

Compresia fractala

Implementata prima data de Arnaud Jacquin care avea la bazaalgoritmi bazati pe sisteme de functii iterate IFS si sisteme de functii iterate partitionate PIFS.

Compresia fractala

• Este o metoda lossy de codare• Metoda este independenta de rezolutie,

imaginile putând fi scalate la o rezolutie mai mare decât imaginea originala

• Metoda duce la un timp mare de compresie dar decompresia este rapida

• Permite rate de compresie foarte mari

Cum functioneaza?Compresie fractala cu PIFS functioneaza prin gasirearedundanta în imaginea de intrare forme de portiuni similare ale imaginii. La PIFS transformările nu se referă la întreaga imagine înfăţişată prin părţile ei, ci este vorba de transformarea părţilor mai mari în părţi mai mici. PIFS-urile stabilesc legaturi intre acele zone ale imaginii initiale care in aparenta sunt similare. Zonele mari ale imaginii sunt numite blocuri domeniu, iar zonele mici sunt denumite blocuri scop. Construirea unui PIFS se rezuma la imperecherea fiecarui bloc scop cu blocul domeniu cu care se aseamana cel mai mult prin aplicarea unor transformari ce urmeaza a fi determinate.

Cum functioneaza?

• Metoda pentru gasirea unui PIFS bun, pentru orice imagine data, presupune 5 etape principale:– partitionarea imaginii in blocuri scop.– formarea setului de blocuri domeniu– alegerea tipului de transformari ce vor fi luate in

consideratie– selectarea unei distante metrice intre blocuri– specificarea unei metode pentru fiecare din aceste

etape

Bloc scop

Bloc domeniu

Identificarea unui bloc scop cu un bloc domeniu, astfel,cel din urma va fi inlocuit cu blocul scop

Descrierea aplicatieiCodul este scris in Matlab si se refera atat la codarea imaginilor alb-negru, cat si la decodarea lor. Algoritmul folosit presupune folosirea de blocuri scop si de domeniu patrate. Pasii procesului de codare sunt detaliati in continuare:Pasul 1. Citirea unei imagini – si in proiect se solicita imagini patratePasul 2. Impartirea imaginii in blocuri scop nesuprapuse patrate si blocuri domeniu nesuprapuse, dublu marimii blocurilor scop.Pasul 3. redimensionarea blocurilor domeniu (la aceeasi dimensiune ca si blocurile scop) si gasirea a 8 posibile transformari pentru fiecare bloc.Pasul 4. compararea fiecarui bloc scop cu toate blocurile domeniu pentru a gasi cea mai buna potrivire intre acestea.Pasul 5. salvarea coeficientilor:

- Localizarea domeniului- Cea mai buna transformare- Contrastul sau factorul de scalare.- Offsetul

Pasul 6. Se repeta pasii anteriori pentru toate blocurile scop.

Descrierea aplicatiei

• Aplicatia este scrisa in Matlab.• Se apeleaza programul principal RIFSbat.m• Se incarca imaginea pentru comprimare• In urma procesarii ei rezulta 10 versiuni diferite

ale imaginii fiecare cu o calitate diferita in functiede marja de eroare permisa de utilizator.

• Pentru decodarea imaginii se apeleaza functiafdec.m care returneaza imaginea decomprimataprecum si statistici ale rularii algoritmului.

Concluzii• Imaginile cu fractali au timp de decompresie foarte mic, astfel incat

sistemele multimedia, „video-on-demad” si tele-browsing pot progresa datorita faptului ca in cadrul acestor sisteme imaginea este comprimata o singura data si decomprimata de foarte multe ori.

• Imaginile compresate cu fractali au o rata de compresie foarte buna, avand o dimensiune comparabila cu cele comprimate cu JPEG, de multe ori chiar mai mica.

• Pastreaza o calitate foarte buna a imaginii in conditiile scalarii la dimensiuni foarte mari.

• Acest tip de compresie de imagini poate fi aplicata in domeniul medical, acolo unde medicii doresc sa observe detaliile imaginii la diferite scari. De asemenea in domeniile militar si al sistemelor de securitate aceasta trasatura este deosebit de utila.

Va multumim pentru atentie!