Fractal_rom

8/7/2019 Fractal_rom

1/22

Compresia fractal a imaginilor

1

COMPRESIA FRACTAL A IMAGINILOR

1. IntroducereCompresia fractal a imaginilor ("Fractal Image Compression" - FIC) este o metod relativ nou, descrispe scurt de urmtoarele caracteristici:

1. Este o metod de compresie cu pierderi ("lossy")2. Este o metod promitoare, superioar (pentru rapoarte de compresie mari) standardului JPEG.3. Fractalii implicai n FIC sunt Sisteme de Funcii Iterate (IFS).4. Este o form de cuantizare vectorial care folosete un dicionar virtual ("virtual codebook").5. mbuntirea rezoluiei este o caracteristic important, dar totui NU poate ajuta la obinerea unor

rapoarte de compresie exagerate.6. Comprimarea este lent iar decomprimarea este rapid.7. Metoda este patentat.

Naterea geometriei fractale este legat de numele matematicianului Benoit B. Mandelbrot, care apublicat n 1977 lucrarea "The Fractal Geometry of Nature", titlu de referin n domeniu. Lucrarea aenunat o teorie important: geometria tradiional, bazat pe linii drepte i suprafee netede, nu seaseamn geometriei naturii (copacilor, norilor, munilor), spre deosebire de geometria fractalilor, cumuchiile lor curbe i detalii "ad infinitum".

Aceast teorie a deschis numeroase posibiliti. Cercettorii din domeniul calculatoarelor au avut ladispoziie un sistem matematic capabil s genereze peisaje artificiale dar care totui arat natural, iarmatematicienii - un ntreg univers de entiti geometrice de studiat. Evident, matematicienii au nceput scaute existena unor similitudini n cadrul acestei diversiti. John Hutchinson a demonstrat n 1981 caceste similitudini exist, i anume n cadrul Teoriei Funciilor Iterate ("Iterated Function Theory").

Ulterior, Michael Barnsley a publicat renumita carte "Fractals Everywhere", n care prezint teoria"Iterated Function Systems" (IFS) i unde formuleaz "Collage Theorem". Aceasta enun proprietile pecare un IFS trebuie s le aib pentru a putea fi folosit la reprezentarea unei imagini.

A aprut astfel urmtoarea problem: dac, pe de o parte, teoria fractalilor este util pentru generarea unorimagini cu aspect "natural", nu cumva poate fi folosit i n sens invers, la comprimarea imaginilor ?(avnd n vedere i faptul c anumii fractali din spatiul complex, foarte spectaculoi, se genereaz pebaza unor ecuaii foarte simple). Pornind de la o imagine dat, obinerea unui IFS care o poate genera(identic sau ct mai similar) a fost denumit "the inverse problem". Aceast problem rmneanerezolvat.

Michael Barnsley afirm n 1988 c a rezolvat problema folosind "Collage Theorem". El a patentatmetoda i a raportat rezultate spectaculoase (rapoarte de compresie 10.000:1), dar numai pe imagini careerau construite manual. Deoarece algoritmul lui Barnsley este foarte lent i necesit asisten din parteaunui operator uman, patentul lui Barnsley este cunoscut sub denumirea ironic de "Graduate StudentAlgorithm":

acquire a graduate student give the student a picture and a room with a workstation lock the door wait until the student has reverse engineered the picture open the door


2/22


2

Rezultatele obinute de unul dintre doctoranzii lui Barnsley au permis depirea limitrilor drastice ale"graduate student algorithm". Arnaud Jacquin renun la determinarea IFS pentru ntreaga imagine,propunnd o variant modificat a IFS numit "Partitioned Iterated Function Systems" (PIFS), deasemenea patentat, i realizeaz o implementare soft a algoritmului. Algoritmul nu era nici sofisticat,nici rapid, ns era complet automat. Preul pltit este renunarea la rapoartele de compresie spectaculoaseanunate de Barnsley: pentru imagini color cu 24 bpp, rata de compresie obinut varia ntre 8:1 i 50:1 ncondiiile unei caliti acceptabile.

Fractalii din cadrul FIC nu fac parte dintre cei din planul complex (cum sunt setul Mandelbrot sau seturileJulia), ci din categoria IFS. Matematicianul Heinz-Otto Peitgen compar IFS cu o "Multiple ReductionCopying Machine" (MRCM), care reprezint un copiator cu urmtoarele proprieti:

1. Exist mai multe sisteme de lentile, care creeaz copii multiple (posibil) parial suprapuse.2. Fiecare sistem de lentile reduce mrimea originalului.3. Copiatorul opereaz n bucl, rezultatul unui pas fiind intrare pentru urmtorul. Ca imagine iniial se

poate alege orice.

Prima caracteristic definete IFS ca fiind un sistem. Datorit celei de a doua, funciile unui IFS suntcontractive. Cea de-a treia face IFS un sistem iterativ.

Aadar, un IFS este un set de transformri contractive care mapeaz o anumit zon rectangular nregiuni mai mici ale ei. Pentru aceasta, aproape ntotdeauna se folosesc transformri afine, caretranslateaz, scaleazi rotesc punctele planului.

Caracteristica important a IFS este c evaluarea iterativ a setului de transformri (funcionarea MRCM)conduce spre o imagine unic, numit atractorul IFS-ului. Conform "Collage Theorem", atractorul estecomplet independent de imaginea iniial.

Pentru o imagine care trebuie codificat, gsirea IFS-ului optim este cunoscut sub numele de "inverseproblem". Dup cum s-a artat anterior, aceast problem nu a fost rezolvat. Pentru a putea face fadiversitii imaginilor reale (naturale) se folosesc PIFS. n PIFS, transformrile nu mapeaz ntreagaimagine n poriuni, ci mapeaz poriuni mai mari din imagine n poriuni mai mici, datorit variaiilorcalitative ale imaginii (ex. alternana nori cer - nori). PIFS stabilete o legtur ntre poriuni dinimaginea iniial care au un aspect similar. Conform notaiei introduse de Jacquin, regiunile mari suntnumite "domain" (D) iar cele mici "range" (R) - transformrile opernd de la un "domain" la un "range".Vom folosi n cele ce urmeaz notaiile de domeniu pentru domain i cea de codomeniu pentrurange. Am preferat aceast soluie pentru avantajul de a indica faptul c transformata fractal din cadrulPIFS se aplic unui domeniu i rezult un codomeniu. n mod riguros ar trebui folosit de fiecare dattermenul de bloc domeniu respectiv bloc codomeniu dar, din motive de simplificare a expunerii nu vomrepeta uneori i bloc, presupunnd c acest lucru este subneles. E necesar ca fiecare pixel din imagineaoriginal s aparin cel puin unui codomeniu. Dispunerea codomeniilor n cadrul imaginii constituiepartiionarea imaginii.

Deoarece acest sistem de mapri este contractiv, prin iteraii el va converge rapid spre atractorul su.Construirea PIFS const tocmai n gsirea perechilor codomeniu-domeniu i a transformrilor afine cerealizeaz maprile optime.

Prin urmare, o codificare fractal a unei imagini const n:

1. Partiionarea imaginii (forma i poziia codomeniilor)2. Descrierea transformrilor afine (cte una pentru fiecare codomeniu)

Esena procesului de compresie este gsirea perechilor codomeniu-domeniu pentru care eroarea de colaj

("collage error") - de reprezentare a unui codomeniu printr-o versiune transformat a domeniului - esteminim. Procesul de cutare este din acest motiv foarte lent. Dei teoria nu impune nici o restricie asupra


3/22


3

formei blocurilor, n practic se consider doar forme ptrate, dreptunghiulare sau triunghiulare doarpentru a face problema abordabil.

n general gsirea unui PIFS bun pentru o imagine dat cuprinde urmtoarele etape:

1. Partiionarea imaginii n codomenii.2. Alegerea setului de domenii.3. Alegerea tipului de transformri ce vor fi folosite.4. Selectarea unei metrici (distane) pentru blocuri (o msur a erorii).5. Specificarea unei metode de determinare optim a perechilor codomeniu-domeniu.

Optimizarea fiecreia dintre aceste etape este important i prezint n continuare interes deosebit ncadrul FIC. Cu toate acestea, se poate afirma c principala problem a FIC rmne creterea vitezei decodificare.

O imagine obinut prin achiziie prezint o rezoluie determinat de performanele dispozitivului.Mrirea imaginii prin soft ("zoom") nu ofer detalii suplimentare peste un anumit nivel, ci doar replicvaloarea pixelilor. Cu o imagine fractal lucrurile se comport diferit: deoarece transformrile afine suntcontractive d.p.d.v. spaial, la fiecare iteraie sunt create detalii suplimentare (are loc o cretere arezoluiei). Sunt create astfel detalii cu autoasemnare la orice nivel de rezoluie, pn la nivel

infinitezimal. Acest fapt confer imaginilor fractale independen de rezoluie. Din aceast cauz, laorice "zoom" ntr-o imagine fractal, aceasta va arta cum "este de ateptat", fr efectul de bloc produsde replicarea pixelilor. Trebuie atras ns atenia c, n cazul imaginilor fractale, detaliile nu au fostreinute ci au fost generate (evaluarea raportului de compresie pe baza unei imagini mrite constituie oposibil confuzie). n fapt, FIC reprezint o modalitate avansatde interpolare.

Comparaia FIC cu cuantizarea vectorial (CV) indic: CV: blocurile codomeniu i domeniu au aceeai mrime; IFS: blocurile domeniu sunt ntotdeauna mai

mari. CV: blocurile domeniu sunt copiate fr modificri; IFS: fiecare bloc domeniu sufer o transformare

afin. CV: dicionarul este stocat separat de imagine; IFS: dicionarul nu este dat n mod explicit, ci cuprinde

poriuni din atractor pe msur ce acesta este generat n timpul iteraiilor (motiv pentru care e numitdictionar virtual ("virtual codebook"). El nu exist separat de transformrile afine ce definesc un IFS.

CV: dicionarul este comun pentru mai multe imagini; IFS: "dicionarul virtual" este specific pentrufiecare imagine.

Exist o variant a CV numit "Mean-Removed Gain-Shape Vector Quantization", care permite iscalarea i deplasarea luminanei, variant care apropie i mai mult cele dou domenii.

n procesarea de imagini se depun mari eforturi pentru a evalua (cuantifica) ct mai precis eroareaprezent ntr-o imagine comprimati apoi pentru a minimiza aceast msur (discutabil) a erorii. Celemai des folosite criterii de evaluare a erorii sunt raportul semnal-zgomot SNR sau PSNR (n special),eroarea medie ptratici eroarea medie absolut.

Testele efectuate pentru a compara (d.p.d.v. al RSZ) JPEG i FIC arat c JPEG este mai bun pentru ratemai mici de compresie, iar FIC este mai bun pentru rate mai mari de compresie, limita fiind de obicei njurul ratei de 40:1. Susintorii JPEG afirm c aceast valoare favorizeaz JPEG, ntruct peste aceastlimit imaginile sunt sever afectate de distorsiuni, ceea ce le face de cele mai multe ori inutilizabilepractic. Adepii FIC, pe de alt parte, susin c SNR nu e un parametru de eroare potrivit i cdistorsiunile au un aspect mult mai "natural" dect aspectul "rectangular" al JPEG, att la rate de bit micict i mari (observaie n principiu corect dar neacceptat unanim). Ceea ce lipsete este un parametru deeroare uor de calculat i care s reflecte fidel impresia subiectiv asupra subiecilor umani. Pn lagsirea acestui parametru, ochiul uman este cel mai bun arbitru.


4/22


4

2. Puin matematic

Ct de mare este un fractal? Cnd doi fractali sunt similari unul altuia ntr-un oarecare sens ? Exist maimulte numere, asociate cu fractali, care pot fi folosite pentru a-i compara. Ele sunt de obicei denumitedimensiuni fractale i reprezint ncercri de a cuantifica impresia subiectiv pe care o avem n legaturcu ct de dens ocup fractalul spaiul su metric. Dimensiunea fractal reprezint o msur obiectivpentru a compara fractalii. Prezentm n continuare cteva fundamente matematice n ceea ce privetedimensiunea fractal, conform crii de referin a lui Barnsley "Fractals everywhere".

Fie (X,d) un spaiu metric complet i fie A H(X) un subset compact nevid al lui X. Fie > 0. NotmB(x,) sfera nchis de razi avnd centrul n punctul xX. Definim N(A,) ca fiind numrul minim desfere nchise de raz necesare s acopere A.

N(A,) = cel mai mic ntreg pozitiv M astfel c A B xnnM

=

( , )1U

pentru un set de puncte {xn : n = 1,2,...,M} X.

Ideea intuitiv aflat n spatele noiunii de dimensiune fractal este c un set A are dimensiunea fractal Ddac

N(A, ) CD

1 pentru o valoare pozitiv C

Riguros, avem urmtoarea definiie:

Definiie Fie AH(X) unde (X,d) este un spaiu metric. Pentru fiecare > 0 fie N(A,) cel mai mic numrde sfere nchise de raznecesare a acoperi A. Dac

DN A

=

0 1lim

ln( ( , ) )

ln( / )

exist, atunci D este numitdimensiunea fractal a lui A.

Vom folosim n continuare notaia D = D(A) i spunem "A are dimensiunea fractal D". Se poate arta

uor c dimensiunea fractal a unui punct este 0 i a unui segment este 1.

Procesul de determinare a dimensiunii fractale este simplificat de urmtoarea teorem n care senlocuiete variabila real cu o variabil discretn.

"The Box Counting Theorem" Fie AH(Rm) i metrica euclidian. Se acoper Rm cu cutii nchiseptrate de latur (1/p

n) ca n Figura 1. Fie Nn(A) numrul de asemenea cutii care intersecteaz

atractorul. Dac

DN A

pn

n

n=

limln( ( ) )

ln( )

existatunci A are dimensiunea fractalD.

n Figura 1 s-a reprezentat cazul spaiului bidimensional (m=2) pentrup=3 i n=2. Folosind aceast teorem rezult uor c dimensiuneafractal a unei regiuni ptratice este 2.

Un exemplu tipic de fractal este "mulimea lui Cantor" (C): pornind de laintervalul [0,1] se elimin "treimile din mijloc". Aplicnd teoremaanterioar pentru p=3, m=1 i avnd Nn(C) = 2

n.

1

10

Figura 1 Acoperire cu cutii nchise


5/22


5

D

N C

pn

n

nn

n=

=

= lim lim

ln( ( ) )

ln( )

ln( )

ln( )

ln

ln

2 2

3

n

3

Un alt exemplu pe care se poate aplica uor teorema anterioar este "triunghiul lui Sierpinski" (S) obinutprin nlocuirea unui triunghi cu trei replici ale sale reduse la jumtate, reprezentarea sa fiind dat nFigura 2a. n Figura 2b este reprezentat mprirea n cutii nchise de latur (1/2)n corespunznd cazuluim=2 i p=2 din Teorem n momentul n = 6. Rezult c avem nevoie de un numr de 3n asemenea cutiirezultnd

DN S

pn

n

nn

n=

=

=

lim limln( ( ) )

ln( )

ln( )

ln( )

ln

ln

3

2

3

2

n

Dimensiune fractal pentru atractorii IFS

O teorem spectaculoas care permite determinarea rapid a dimensiunii unui fractal este urmtoarea,care se poate aplica fractalilor obinui ca i atractori ai IFS.

Teorem Fie {Rm;w1,w2,...,wN} un IFS hiperbolic i fie A atractorul su. Fie wn o asemnare avndfactorul de scalare sn pentru fiecare n{1,2,3,...,N}. DacIFS este complet nesuprapus sau doar alturatatunci atractorul are dimensiunea fractalD(A), care este datde soluia unica ecuaiei

snn

N D A

= =

1

1( )

, D(A)[0,m]

DacIFS este suprapus, atunci D A D( ) unde D este soluia ecuaiei

snn

N D

= =1 1, D [0,)Aceast teorem ne permite determinarea rapid a dimensiunii fractale ca n exemplele urmtoare:

privind "mulimea lui Cantor" (C) ca i atractorul unui IFS hiperbolic

[ , ]; ( ) ; ( )011

3

1

3

2

31 2 w x x w x x= = +

obinem avnd s1 = 1/3 i s2 = 1/3

a b

Figura 2 Triunghiul lui Sierpinski


6/22


6

1

3

1

31

+

=

D C D C ( ) ( )

3ln

2ln)(32 = CDD(C)=

regsind evident valoarea determinat anterior.

privind "triunghiul lui Sierpinski" (S) ca i atractorulunui IFS hiperbolic avem trei transformri cu factoriide scalare s1 =s2=s3= 1/2.

1

2

1

2

1

21

+

+

=

D S D S D S( ) ( ) ( )

=3 = 2D(S) D S( )ln

ln

3

2

regsind evident valoarea determinat anterior

privind clasica "curb Koch" (K) ca i atractorul unuiIFS hiperbolic avem patru transformri cu factorii de

scalare s1 = s2 = s3 = s4 = 1/3.

1

3

1

3

1

3

1

31

+

+

+

=

D K D K D K D K ( ) ( ) ( ) ( )

=4 = 3D(K) D K( )ln

ln

4

3

Se constat c dimensiunea fractal a seturilor

considerate ca i exemple este fracionar (nu este un

numr ntreg). Aceasta valoare fracionar este cea care a

stat la baza introducerii termenului de fractal pentru

aceste seturi (figuri).Figura 3 Curba lui Koch


7/22


7

3. Comparaie cu alte metode

Compresia de imagini bazat pe DCT i standardizat n JPEG este o tehnic de succes pentru rapoarte decompresie de pn la aproximativ 40:1. Peste aceast limit, aspectul de bloc devine pregnant iarcalitatea imaginii scade devenind inutilizabil n practic. Eliminarea componentelor de frecven ridicatdetermin distorsiuni mari n cadrul imaginii, efectele fiind vizibile mai ales pe muchiile obiectelor din

imagine, aspect cunoscut sub numele de fenomenul Gibb.

Un alt dezavantaj al compresiei JPEG const n dependena de rezoluie a imaginii comprimate. n cazuln care este necesar afiarea imaginii la o rezoluie superioar celei originale este necesar duplicareapixelilor, efectul de bloc devenind suprtor.

Diferite puncte de vedere asupra compresiei fractale a imaginilor

Pe msura creterii interesului pentru compresia fractal a imaginilor, cercettorii au apropiat acestdomeniu de diferite alte domenii. Cele mai importante puncte de vedere propuse pentru abordareacompresiei fractale a imaginilor au la baz asemnarea cu:

SISTEMELE CU FUNCII ITERATE(IFS) - Asemenea sisteme sunt de fapt operatori n spaiul metrici au fost introduse n matematic de o lucrare a lui Hutchinson n 1981 care a aratat c au, ca i atractori,subseturi fractale. Barnsley a intuit pentru prima dat folosirea IFS n compresia imaginilor prindescrierea imaginilor ca atractori. Arnaud Jacquin propune n 1989 o metod care renun la privireantregii imagini ca i un fractal i pune bazele PIFS ("Partitioned IFS"), moment care a constituit de faptnceputul unei noi direcii de cercetare foarte promitoare n domeniul compresiei de imagini.

CUANTIZAREA VECTORIAL - Compresia fractal a imaginilor este foarte apropiat de un cazparticular de cuantizare vectorial, numit mean-removed shape-gain vector quantization MRSG-VQ. nMRSG-VQ un bloc este aproximat prin suma unei componente continue (constante) i o versiune scalata unui reprezentant din dicionar. Specificul compresiei fractale const n aceea c dicionarul nu esteprezent explicit la decodare, ci doar implicit prin transformarea fractal. Din acest motiv dicionarul maieste numit i dicionar virtual ("virtual codebook").

Nici unul din aceste puncte de vedere nu este general (complet), toate mpreun contribuind la nelegereamai profund a acestei tehnici i la dezvoltarea acesteia prin includerea de idei existente deja i care i-audovedit cu prisosin utilitatea n acele domenii.

Alegerea modelului codor-decodor al FIC se face pe baza punctului de vedere al Sistemelor de FunciiIterate (IFS), n timp ce pentru determinarea parametrilor codorului se adopt n principal punctul devedere al cuantizrii vectoriale.

4. Problema Invers a Sistemelor de Funcii Iterate

Fie (M,d) un spaiu metric al imaginilor digitale, unde d este o metric - o msur a distorsiunii, i fie orig

o imagine care se dorete a se coda. Problema invers a teoriei funciilor iterate este construcia uneitransformri de contracie a imaginii, definit din spaiul (M,d) n el nsui, pentru care orig s fie punctfix. Notm F setul transformrilor permise: un subset specific, definit a priori, al spaiului tuturorcontraciilor n (M,d).

Cerinele asupra transformrii sunt urmtoarele: s < 1 astfel nct ,M d((),()) sd(,) (1)

i d (orig,(orig) ) s fie ct mai apropiat de zero (2)

Scalarul s este numit contractivitatea transformrii . n aceste condiii, i considernd c are o


8/22


8

complexitate mai mic dect imaginea original, poate fi privit ca i o codificare (cu pierderi) aimaginii orig .

Prin aplicarea repetat a inegalitii triunghiului n (M,d) i folosind contractivitatea lui se poate arta cpentru orice imagine 0i orice ntreg pozitiv n avem:

ds

d s dorign

orig orig n

orig( , ( ) ) ( , ( ) ) ( , ) 0 01

1

+ (3)

Din precedentele dou relaii i considernd s < 1, observm c, dup un numr iniial de iteraii, termeniioricrei secvene iterate de forma

{ n = n( 0 ) }n0 (4)

unde 0 este o imagine iniial oarecare, se grupeaz n jurul imaginii originale (rezultat cunoscut nliteratur ca i "Collage Theorem"). n spaiul imaginilor discrete cuantizate, secvena converge spre oimagine stabil care, datorit modului de construcie, se spune c este fractal.

n raport cu cele prezentate anterior, considerm utile urmtoarele observaii:1. Apropierea lui n( 0 ) de orig este condiionat de distana d(orig,(orig)).2. Convergena secvenei n depinde n mod esenial de restricia ca s s fie mai mic dect 1.3. Transformarea constant = orig care are contractivitatea 0 i satisface n mod evident (1) i (2) nu

este n F deoarece suntem interesai doar de transformri care pot fi descrise pe un numr de bii maimic dect imaginea iniial - o cerin esenial pentru compresie.

Numim o asemenea transformare din F care satisface (1) i (2) un cod fractalpentru origi spunem corig este aproximativ auto-transformabil n raport cu . Aceast terminologie are la baz faptul cimaginile obinute prin aceast procedur sunt rezultatul aplicrii iterative a unei transformri asupra uneiimagini iniiale, procedur care este tipic generrii de seturi fractale deterministe.

n Figura 4 se prezint schema general a unui sistem de codare-decodare fractal.

Observaia c redundana din cadrul imaginilor poate fi modelat prin autoasemnarea la nivel de blocurine ndreapt atenia spre o clas de transformri avnd forma general:

M, () =0 L e n a

Figura 15 Convergena procesului iterativ de decodificare

IteraiaAtractor Imagine

iniial 1 2 3 4 5 6 7 8 9 10

Lena Negru 11.32 16.18 20.67 24.97 30.28 31.25 31.33 31.33 31.32 31.32

Lena Peppers 16.02 20.74 25.17 29.02 31.15 31.31 31.32 31.32 31.32 31.32

Peppers Negru 11.92 16.80 21.28 25.34 30.04 31.46 31.60 31.61 31.61 31.61

Peppers Lena 15.70 20.62 24.77 28.90 31.32 31.58 31.60 31.61 31.61 31.61Tabelul 1 Convergena procesului iterativ de decodificare (PSNR dB)


17/22


17

Imaginea iniial (negru) Iteraia 1 (PSNR 11.32 dB)

Iteraia 2 (PSNR 16.18 dB) Iteraia 3 (PSNR 20.67 dB)


Figura 16 Primele 5 iteraii ale secvenei de decodificare Negru Lena

(Iteraia 10 este prezentat n Figura 12)


18/22


18

Imaginea iniial (Peppers) Iteraia 1 (PSNR 16.02 dB)



Figura 17 Primele 5 iteraii ale secvenei de decodificare Peppers Lena


19/22


19

16, 8, 4. Se ncearc codificarea folosind blocuri de dimensiune maxim. Dac acest lucru nu se poateface n limitele unui criteriu de eroare impus, blocul se divide n 4 fii i se ncearc codificareaindependent a fiecrui fiu. Acest procedeu de divizare poate continua pn n momentul atingeriidimensiunii minime a blocului, cnd codificarea se face pe baza acestei dimensiuni indiferent dendeplinirea criteriului de eroare. Un exemplu de divizare este dat n Figura 18. Blocul (a), care nurespect criteriul de eroare, este divizat (b) n patru fii (c). Aceia dintre ei care nu respect criteriul de

eroare sunt la rndul lor divizai (d). Cei care respect criteriul de eroare (blocul haurat) sunt folosii ca icodomeniu n cadrul PIFS.

O descriere algoritmic este dat n continuare:

Algoritm "quadtree":

1. Se alege o valoare a erorii medii ptratice ca i criteriu limit de eroare. Se aleg limitele pentrudimensiunea blocului. Se partiioneaz imaginea folosind dimensiunea maxim a blocului.

2. Se iniializeaz o stivi se introduc n ea blocurile de dimensiune maxim.3. Ct timp stiva nu este vid se execut urmtorii pai:

Se extrage din stiv un bloc codomeniu R i se caut domeniul D pe baza cruia R poate fiaproximat optim R sD+o1. Se determin eroarea E(R,D).

Dac criteriul de eroare este satisfcut sau dac dimensiunea blocului este cea minim, se scriu nfluxul de date comprimat valorile s, o, izometria i poziia lui D. Altfel, se divide blocul n cele 4 blocuri fiu i se introduc aceste blocuri n stiv.

Dei algoritmul a fost descris n termenii implementrii unei stive, n practic de cele mai multe ori seconsider o implementare recursiv n care stiva algoritmului este nlocuit de stiva sistemului utilizatde compilator pentru apelul (recursiv) de funcii.

Algoritmul de determinare a domeniului optim prin cutare i transformrile considerate n mapareadomeniu-codomeniu sunt aceleai ca i la algoritmul neadaptiv. Decodificarea se face de asemenea prinaplicarea iterativ a transformrilor pe o imagine iniial.

Un avantaj al acestui algoritm este acela c, prin alegerea de diferite valori pentru criteriul de eroare, se

pot obine diferite rapoarte de compresie i caliti ale imaginii putnd astfel trasa, prin puncte,caracteristica rat-distorsiune a metodei (prezentat n Tabelul 2 i n Figura 19). Un dezavantaj al acesteimetode const n faptul c nu se pot prescrie calitatea imaginii refcute i rata de bit (raportul decompresie) dorite n mod direct.

Prezentm n Figura 20 imaginile obinute prin considerarea pentru criteriul de eroare a valorilor 8 i 20care au dus la obinerea unor rapoarte de compresie de 39.59 respectiv 93.48 n condiiile unui PSNR de30.10 dB respectiv 25.88 dB. Ca i n cazul algoritmului neadaptiv, pentru vizualizarea erorii imaginea afost scalat astfel nct erorii maxime s i corespund nivelul maxim de negru.

dcba

Figura 18 Un exemplu de aplicare a partiionrii quadro


20/22


20

Se constat partiionarea diferit din cadrul imaginii: n zonele uniforme codorul a ales blocuri dedimensiune mai mare, iar n cele cu detalii blocuri de dimensiune mai mic (minim). n cazul unuicriteriu de eroare mai restrictiv (primul caz n Figura 20) partiionarea a fost mai fin, eroarea obinutmai mic, dar preul pltit a fost mai mare (n sensul numrului de bii necesari codificrii transformriituturor blocurilori implicit al raportului de compresie obinut). Raportul de compresie poate fi crescutsuplimentar prin aplicarea unei codri entropice.

9. Compresia fractal a secvenelor video

Aplicarea tehnicilor fractale n domeniul video este de dat mai recent, tehnicile fractale dezvoltndu-sen contextul imaginilor alb-negru (n nivele de gri) statice. n principal, abordrile fractale ale compresieivideo au la baz urmtoarele:

Codare cadru cu cadru bazat pe tehnici fractale. Se folosesc uneori informaii de micare pentru arestrnge (accelera) cutarea. Tehnica este o extensie simplist a metodelor dedicate imaginilor statice(Figura 21).

24

25

26

27

28

29

30

31

0 20 40 60 80 100 120 140

Raport Compresie

PSNR(d

B)

Lena

Peppers

Figura 19 Caracteristica Rat-Distorsiune

Lena Peppers

Tolerana Timp(sec)

RaportCompresie

PSNR(dB)

Timp(sec)

RaportCompresie

PSNR(dB)

2 304 20.50 30.87 292 20.23 30.86

4 220 27.21 30.78 246 23.94 30.80

6 181 33.07 30.51 191 30.84 30.58

8 159 39.59 30.10 156 37.58 30.24

10 128 46.76 29.46 136 43.37 29.75

12 112 53.52 28.85 123 48.78 29.27

14 100 59.83 27.28 108 54.84 28.74

16 88 69.88 27.28 96 63.04 27.90

18 77 79.65 26.77 85 70.86 27.03

20 66 93.48 25.88 76 80.19 26.39

22 58 108.23 25.27 63 95.56 25.48

24 47 134.08 24.43 53 115.68 24.59

Tabelul 2 Performanele metodei "quadtree" n funcie de criteriul de eroare


21/22


21

Rap.Compr. = 93.48 PSNR=25.88 dB Rap.Compr. =39.59 PSNR=30.10 dB

Partiionarea imaginii

Criteriul de toleran = 20 Eroarea de refacere (scalat) Criteriul de toleran = 8

Figura 20 Rezultatele obinute folosind codorul adaptiv bazat pe partiionare quadro


22/22


Codare de volum ("cube coding scheme"). Esena acestor metode const n extinderea sistemelorPIFS de la 2D la 3D prin considerarea timpului (numrului de cadru) ca i a treia dimensiune ideterminarea unei mapri contractive (pe toate cele trei dimensiuni). Secvena de codat se mparte nsecvene de cadre denumite G.O.P. ("Group of Picture") care se codeaz mpreun. n loc s sempart fiecare cadru n codomenii ptratice, se mparte "volumul" unui asemenea G.O.P. n cuburicodomeniu (mai general n paralelipipede, de cele mai multe ori dreptunghice) nesuprapuse care secodific ca i PIFS. Transformrile PIFS considerate mapeaz fiecare asemenea volum domeniu ntr-un volum codomeniu dup cum se indic n Figura 22.

M+PM+k1M

cadru

Figura 21 Codare cadru cu cadru

M+PM+k2M+k1M

cadru

Figura 22 Codare de volum

Fractal_rom

Documents

Transcript of Fractal_rom