Compresie Imagini

7/31/2019 Compresie Imagini

1/69

1

CAPITOLUL 10

COMPRESIA DE IMAGINI

10. 1. Reprezentarea numeric a imaginilor

O imagine este o suprafa de obicei dreptunghiular caracterizat,la nivelul oricrui punct al ei, de o anumit culoare. Ideal, culoarea variaz continuu n oricare direcie. Din pcate, n sistemele numerice, nu se potutiliza mrimi care variaz continuu, ci doar forma discretizat a acestora.

Astfel, o imagine trebuie s fie discretizat nainte de a se pune problema reprezentrii numerice. Discretizarea const n mpr irea imaginiintr-un caroiaj asemntor unei table deah. Fiecare por iune de imaginedelimitat de acest caroiaj va fi considerat ca avnd o culoare uniform - omedie a culorii existente pe aceast seciune. Aceste seciuni mai suntdenumitei pixeli sau puncte, numrul acestora definind rezoluia imaginii.De exemplu, pentru o imagine oarecare care are o rezoluie de 640x480 pixeli, nseamn c pe suprafaa acesteia s-a definit un caroiaj care omparte pe orizontal n 640 de seciuni iar pe vertical, n 480.

Pasul urmtor l constituie gsirea unei reprezentri pentru culoare.Orice culoare poate fi descompus n trei culori primare (de exemplu rou-R, verde-Gi albastru-B), cu alte cuvinte orice imagine poate fi obinut prin suprapunerea aditiv a trei radiaii luminoase avnd aceste trei culoriiintensiti diferite. Deci, pentru a reprezenta numeric o culoare, estesuficient s se reprezinte intensitile luminoase ale celor trei culori primare.


2/69

2

Dac se aloc cte 8 bii pentru fiecare component, se pot coda 256 nivelede intensitate, astfel, absena culorii (intensitate zero) se codific prinvaloarea 00000000 n binar sau 00 n hexazecimal, iar intensitatea maxim, prin cea mai mare valoare ce poate fi reprezentat pe 8 bii, i anume,11111111 n binar sau FF n hexazecimal. Aceast reprezentare, ns, inemai mult de modalitile tehnice de captarei reproducere a imaginiii mai puin de mecanismul fiziologic de percepere a culorii. Prin diferiteexperimente s-a constatat c din punct de vedere al capacitii de perceperea detaliilor, ochiul este mai sensibil la intensitatea luminoas a culorii dect

la nuan. Din acest motiv prezint interes o alt modalitate de reprezentarea culorii care s in cont de aceast observaie, un exemplu fiindreprezentarea YUV utilizat n televiziunea n culori. n acest caz, n loculcelor trei componente primare R,G,B se utilizeaz alte trei mrimi derivatedin acestea,i anume:

0,3 0,59 0,110,7 0,59 0,110,3 0,59 0,89

Y R G B

U R Y T G B

V B Y R B

= + += = = = +

(10.1)

n cazul acestei reprezentri, componenta Y corespunde intensitiiluminoase percepute pentru respectiva culoare (coeficienii 0,30, 0,59i0,11 reprezint str lucirile relative la alb ale celor trei culori primare rou,verde i, respectiv, albastru). Aceast component mai este ntlnit i subnumele de luminan. Componentele Ui V sunt cele care definesc nuanaculorii, din acest motiv, sunt denumite componente de crominan. Acestease calculeaz ca diferena dintre componenta roie, respectiv albastr , i ceade luminan.

Avantajul reprezentrii YUV este acela c separ componenta de

luminan, pentru care ochiul este foarte sensibil la detalii, de componentelede nuan pentru care sensibilitatea este mai redus. Acest lucru face posibil reducerea informaiei asociate unei imagini prin utilizarea uneirezoluii mai reduse pentru componentele de crominan. n cazul


3/69

3

televiziunii n culori se realizeaz o "compresie" prin limitarea benzii defrecven alocate semnalelor de crominan (de exemplu n sistemul PALsemnalele Ui V au o band de 1,3MHz fa de semnalul Y care are o band de 6MHz).

10.2. Reprezentarea imaginii n format necompresat

O imagine se reprezint ca o matrice de puncte (de obicei de forma

ptrat), fiecare punct fiind caracterizat de o culoare. De exemplu, pentruimaginea din Fig. 10.1(a) se poate evidenia acest lucru dac se mrete oseciune a imaginii astfel nct matricea de puncte s devin vizibil, ca nFig. 10.1(b).

(a)

(b)Figura 10.1


4/69

4

Pentru a reprezenta o astfel de imagine trebuie s se utilizeze un mod dereprezentare numeric al culorii. Pentru aceasta se pornete de la observaiac orice culoare poate fi obinut prin amestecul n diferite propor ii a treiculori de baz (culori primare). n practic se utilizeaz ROU (R), VERDE(G) i ALBASTRU (B). Intensitatea luminoas a unei culori primare poatefi reprezentat numeric sub forma unui ntreg de 8 bii, valoarea 0corespunznd intensitii nule iar cea maxim (255) intensitii maxime. nacest fel, o culoare va fi reprezentat numeric printr-un triplet de ntregi pe8 bii (R,G,B). De exemplu culoarea GALBEN va avea o reprezentare de

forma (255,255,0). n aceste condiii imaginea se reprezint sub forma uneimatrice IM(Nx,Ny) unde Nx reprezint numrul de puncte pe orizontal i Ny este numrul de puncte pe vertical, iar elementele matricei sunt triplei dentregi pe 8 bii de tip (R,G,B).

10.3. Metode i abord ri ale compresiei imaginii

n continuare se reiau cteva metode folosite n compresie,

evideniind aplicabilitatea lor n compresia de imagini.

1. Cuantizarea scalar poate fi folosit pentru a compresa imagini,dar performanele ei sunt mediocre. De exemplu, o imagine cu 8 bii/pixel poate fi compresat prin cuantizare scalar eliminnd cei mainesemnificativi patru bii ai fiecrui pixel. Aceasta conduce la o rat decompresie de 0,5, care pe lng faptul c nu este semnificativ, determin nacelai timpi reducerea numrul de culori (sau nuane de gri) de la 256 ladoar 16. O astfel de reducere nu numai ca descrete pe ansamblu calitatea

imaginii reconstruite, dar poate chiar crea benzi de diferite culori, un efectobservabili deranjant care este ilustrat aici.


5/69

5

Exemplul 10.1.Se consider , de exemplu, un rnd de 12 pixeli de culori similare,

pornind de la 202 la 215. n notaie binar aceste valori sunt:11010111 11010110 11010101 11010011 11010010 1101000111001111 11001110 11001101 11001100 11001011 11001010.

Cuantizarea va produce urmtoarele 12 valori de 4 bii:1101 1101 1101 1101 1101 1101 1100 1100 1100 1100 1100 1100,

din care se vor reconstrui cei 12 pixeli, prin adugarea a 4 zerouri, fiecreivalori cuantizate:

11010000 11010000 11010000 11010000 11010000 1101000011000000 11000000 11000000 11000000 11000000 11000000.

Primiiase pixeli ai rndului acum au valoarea 110100002 = 208, n timp ceurmtorii ase pixeli sunt 110000002 = 192. Dac rnduri adiacente au pixeli similari, primelease coloane vor forma o band, clar diferit de banda format de urmtoarele ase coloane. Acest fenomen de formare a benzilor, sau de conturare, este foarte evident pentru ochi, deoarece acetiasunt sensibili la marginii rupturi ntr-o imagine.

2. Cuantizarea vectorial poate fi folosit cu mai mult succes pentrua compresa imagini.

3. Metodele statistice funcioneaz mai bine cnd simbolurile cetrebuie compresate au probabiliti diferite. O secven de intrare n caremesajele au aceeai probabilitate nu se va compresa eficient. n acest sens,ntr-o imagine alb-negru sau color n tonuri continue, diferitele culori saunuane de gri se dovedesc de multe ori a avea aproximativ aceleai probabiliti. De aceea metodele statistice nu sunt o alegere bun pentru

compresia unor astfel de imagini,i sunt necesare noi abordri. Imaginile cudiscontinuiti de culoare, n care pixeli adiaceni au culori foarte diferite, se


6/69

6

compreseaz mai bine cu metodele statistice, dar n acest caz nu este uoar predicia pixelilor.

4. Metodele de compresie bazate pe dic ionar tind, de asemenea, s nu aib succes n cazul imaginilor cu tonuri continue. O astfel de imagineconine de obicei pixeli adiaceni n culori similare, dar nu conine modelerepetitive. Chiar i o imagine care conine modele repetitive, cum suntliniile verticale, le poate pierde cnd este digitizat. O linie vertical nimaginea original poate deveni uor oblic atunci cnd imaginea este

digitizat. O linie vertical ideal este prezentat n Fig. 10.2a. n Fig.10.2.b linia este presupus a fi perfect digitizat n zece pixeli, aezaivertical. Totui, dac imaginea este plasat n digitizor uor oblic, procesulde digitizare poate fi imperfect,i pixelii rezultai pot ar ta ca n Fig. 10.2.c.

a) b) c)

Fig. 10.2. Digitizare perfect i imperfect.

O alt problem a compresiei imaginilor bazate pe dicionar esteaceea c astfel de metode scaneaz imaginea rnd cu rnd,i pot pierdeastfel corelaii verticale ntre pixeli. Un exemplu sunt cele dou imagini dinFigura 10.3 a, b. Salvnd ambele imagini n GIF89, un format de fiier grafic bazat pe dicionar, au rezultat fiiere de dimensiuni 1053, respectiv1527 octei.


7/69

7

(a) (b)

Figura 10.3. Compresia bazat pe dicionar a liniilor paralele

Metodele tradiionale sunt nesatisf ctoare pentru compresia deimagini, astfel nct au fost necesare abordri noi, care, dei diferite, se bazeaz pe eliminarea redundanei din imagine, folosind urmtorul principiu:

Principiul compresiei de imagine . Dac se selecteaz aleator un pixel dintr-o imagine, exist o probabilitate mare ca vecinii si s aib

aceeai culoare sau culori foarte apropiate.Compresia de imagine este, deci, bazat pe faptul c pixeliinvecinai sunt puternic corelai. Aceast corelare se numete i redundan spaial.

Exemplul 10.2.n continuare este prezentat un exemplu simplu care ilustreaz cum

poate fi eliminat redundana dintr-un ir de pixeli corelai. Urmtoareasecven de valori reprezint intensitile a 24 de pixeli adiaceni dintr-un

rnd al unei imagini n tonuri continue: 12, 17, 14, 19, 21, 26, 23, 29, 41,38, 31, 44, 46, 57, 53, 50, 60, 58, 55, 54, 52, 51, 56, 60.


8/69

8

Doar doi din cei 24 de pixeli sunt identici. Valoarea lor medie este 40,3.Scznd perechi de pixeli adiaceni rezult secvena: 12, 5, -3, 5, 2, 4, -3, 6,11, -3, -7, 13, 4, 11, -4, -3, 10, -2, -3, 1, -2, -1, 5, 4.Cele dou secvene sunt ilustrate n Figura 10.4.

Fig. 10.4: Valorilei diferenele celor 24 pixeli adiaceni.

Secvena de valori diferen are trei proprieti care ilustreaz potenialul ei de compresie:

1. Valorile secvenei diferen sunt mai mici dect valorile pixelilor originali. Media lor este de 2,58.

2. Exist valori ale secvenei diferenelor care se repet. Exist doar 15valori diferen distincte, deci, n principiu ele pot fi codate prin patru bii fiecare.

3. Valorile secvenei diferen sunt decorelate, adic valori diferen adiacente tind a fi diferite. Aceasta poate fi observat dac seefectueaz o nou scdere a lor, rezultnd secvena 12, -7, -8, 8, -3,2, -7, 9, 5, -14, -4, 20, -11, 7, -15, 1, 13, -12, -1, 4, -3, 1, 6, 1.Valorile acesteia sunt mai mari dect diferenele anterioare.

n general, metodele de compresie pentru imagini sunt proiectate pentru un tip particular de imaginei n continuare se prezint cteva dinaceste metode specifice. Imaginile particulare vizate sunt imagini cu dou nivele, imagini cu tonuri de grii imagini color.

Abordarea 1 . Aceasta este folosit pentru imagini cu dou nivele.Un pixel dintr-o astfel de imagine este reprezentat printr-un bit. Aplicnd


9/69

9

principiul compresiei de imagine asupra unei imagini cu dou nivele,nseamn c pixelii nvecinai ai unui pixel P tind a fi identici cu P . Astfel,are sens folosirea unei codri RLC (Run length coding) pentru a compresa oastfel de imagine. O metod de compresie pentru o astfel de imagine o poatescana n ordinea rastrului (rnd cu rnd), calculnd lungimileirurilor de pixeli albii negri. Aceste lungimi sunt codate prin coduri de lungimevariabil i sunt nscrise n secvena compresat. Un exemplu de astfel demetod este compresia facsimil.

Ar trebui accentuat faptul c aceasta este doar o abordare a

imaginilor cu dou nivele. n practic, detaliile metodelor particulare difer ,n funcie de aplicaie. De exemplu, o metod poate scana imaginea coloan cu coloan, sau n zig-zag, sau o poate scana regiune cu regiune.

Abordarea 2 se aplic, de asemenea, pentru imagini cu dou nivele.Principiul compresiei de imagine spune c vecinii unui pixel tind a fisimilari lui. Se poate extinde acest principiui concluziona c dac pixelulcurent are culoareac (unde c este ori alb, ori negru), atunci pixelii deaceeai culoare anteriorii urmtori tind s aib aceiai vecini imediai.

Aceast abordare urmrete n vecini apropiai ai pixelului curenti i

consider ca un numr de n bii. Acest numr se numete contextul pixelului. n principiu pot exista2n contexte, dar datorit redundaneiimaginii, distribuia lor este neuniform. Unele contexte ar trebui s fiefoarte frecvente, iar celelalte, rare. Codorul numr de cte ori a fost gsitdeja fiecare context pentru un pixel de culoareac, i asigneaz corespunztor probabiliti acestor contexte. Dac pixelul curent areculoareac i contextul su are probabilitatea p, codificatorul poate folosicoduri aritmetice adaptive pentru a codifica pixelul cu acea probabilitate.Aceast abordare este folosit de standardul JBIG (Joint Bi-level Processing

Group).


10/69

10

n continuare, se consider imagini n nuane de gri. Un pixel dintr-oastfel de imagine este reprezentat prinn bii i poate avea una din 2n valori.Aplicarea principiul compresiei de imagine asupra unei imagini n nuane degri implic faptul c vecinii imediai ai unui pixel P tind a fi similari cu P ,ns nu n mod necesar identici cu el. Astfel, nu mai poate fi folosit codarea RLE (run length encoding) pentru compresia unei astfel de imagini,ci sunt folosite urmtoarele dou abordri.

Abordarea 3 . Se separ imaginea n tonuri de gri nn imagini pedou nivele i apoi se compreseaz fiecare cu un cod RLE instantaneu.

Principiul compresiei de imagini, n acest caz, s-ar formula prin afirmaia c doi pixeli adiaceni care sunt similari n imaginea n tonuri de gri vor fiidentici n cele mai multe imagini cu dou nivele. Acest lucru ns nu esteadevrat, aa cum reiese din urmtorul exemplu.

Exemplul 10.3.Se consider o imagine n tonuri de gri cu 4n = (adic 4 bii/pixel

sau 16 nuane de gri). Imaginea poate fi separat n patru imagini bi-nivel.Dac doi pixeli adiaceni din imaginea original au valorile 0000i 0001,

atunci sunt similari. De asemenea, sunt identici n trei din cele patru imagini bi-nivel. Totui, doi pixeli adiaceni cu valori 0111 i 1000 sunt deasemenea similari n imaginea n tonuri de gri (valorile lor sunt 7, respectiv8), dar difer n toate cele patru imagini alb-negru.

Aceast problem apare deoarece reprezentarea binar a numerelor ntregi adiacente poate diferi prin mai muli bii. Codurile binare pentru 0i1 difer printr-un bit, cele pentru 1i 2 difer prin doi bii, i cele pentru 7i8 prin patru bii. Soluia este proiectarea unor coduri speciale, astfel nctcodurile oricror dou numere ntregi consecutivei i i+1 s difere numai

printr-un singur bit. Un exemplu de astfel de cod este codul Gray reflectat[Sal].


11/69

11

Abordarea 4 . Se folosete contextului unui pixel pentru a prezicevaloarea sa. Contextul unui pixel este dat de valorile ctorva dintre veciniisi. Se examineaz civa vecini ai unui pixel P , se calculeaz o medie A,a valorilor lor,i se prezice c P va avea valoarea A. Principiul compresieide imagini spune c predicia va fi corect n cele mai multe cazuri, aproapecorect n multe cazuri,i complet greit n puine cazuri. Valoarea prezis a pixelului P reprezint informaia redundant n P , astfel nct secalculeaz diferena : = P - A, i se asigneaz coduri instantanee delungime variabil pentru diferitele valori. Dac P poate lua valori de la 0

la m-1, atunci va avea valori n intervalul [-(m-1),+(m-1)],i numrulcuvintelor de cod necesare este 2m - 1.

Experimente cu un numr mare de imagini sugereaz c valorile lui tind s fie distribuite dup distribuia Laplace. O metod de compresie ar putea s foloseasc aceast distribuie pentru a asigna o probabilitatefiecrei valori a lui, i apoi s se foloseasc codarea aritmetic pentru acoda eficient valorile. Acesta este principiul metodei progresivemultinivel MLP [Sal].

Contextul unui pixel poate fi constituit din unul sau doi din vecinii

si imediai. Dac, ns, se consider mai muli pixeli vecini n obinereacontextului, se pot obine rezultate mai bune. Media A ntr-un astfel de cazar trebui ponderat cu vecinii apropiai, care au o pondere mai mare. Pentruca decodorul s poat decoda o imagine, ar trebui s poat calcula contextulfiecrui pixel. Acest lucru nseamn c n context ar trebui s fie incluidoar pixelii care au fost deja codai. Dac imaginea este scanat n ordinearastrului, contextul ar trebui s conin doar pixeli localizai deasupra pixelului curent sau pe acelai rnd cu el, la stnga.

Abordarea 5 . Se aplic o transformare valorilor pixelilor,i se

codeaz valorilor transformate. Se reamintete c pentru a realizacompresia, trebuie redus sau eliminat redundana. Redundana uneiimagini este cauzat de corelaia dintre pixeli, deci transformnd pixelii


12/69

12

ntr-o reprezentare n care acetia sunt decorelai, se elimin redundana. Deasemenea este posibil ca o transformare s fie apreciat n funcie deentropia imaginii. ntr-o imagine puternic corelat, pixelii tind a avea valoriechiprobabile, ceea ce duce la o entropie maxim. Dac pixelii transformaisunt decorelai, anumite valori de pixeli devin mai frecvente, avnd astfel probabiliti mari, n timp ce alte valori sunt rare, fapt ce conduce la oentropie mic. Cuantiznd valorile transformate, se poate produce ocompresie cu pierdere de informaie, eficient, a imaginii. Se dorete cavalorile transformate s fie independente, deoarece codarea valorilor

independente face mai simpl construirea unui model statistic.n cazul imaginilor n culori, un pixel este constituit din trei

componente de culoare, rou, verdei albastru. Majoritatea imaginilor color sunt ori n tonuri continue, ori n tonuri discrete.

Abordarea 6 . Principiul acestei abordri const n separarea uneiimagini color n tonuri continue n trei imagini n tonuri de grii compresiafiecreia din ele separat, folosind abordrile 2, 3i 4.

Pentru o imagine n tonuri continue, principiul compresiei deimagini implic faptul c pixelii adiaceni au culori similare, dac nu chiar

identice. Totui, culori similare nu nseamn valori similare ale pixelilor. Seconsider , de exemplu, valori pe 12 bii ale pixelilor, n care fiecarecomponent de culoare este exprimat n patru bii. Astfel, cei 12 bii1000|0100|0000 reprezint un pixel a crui culoare este o mixtur de optuniti de rou (aproape 50%, din valoarea maxim de 15 uniti), patruuniti de verde (circa 25%),i deloc albastru. Se consider doi pixeliadiaceni cu valorile 0011|0101|0011i 0010|0101|0011. Acetia au culorisimilare, din moment ce doar componentele lor roii difer printr-o unitate.Cu toate acestea, cnd se consider ca numere de 12 bii, cele dou numere

001101010011i 001001010011 sunt diferite, pentru c difer ntr-un bit cu pondere semnificativ.


13/69

13

O caracteristic important a acestei abordri este folosirea uneireprezentri tip luminan crominan, YUV, n loc de reprezentareacomun RGB. Avantajul acestei reprezentri este c ochiul este sensibil lamodificri mici ale luminanei, dar nui la ale crominanei. Aceasta permite pierderea unei cantiti considerabile de date n componentele decrominan, f r o pierdere vizibil de calitate.

Abordarea 7. O abordare diferit este necesar pentru imaginile ntonuri discrete. Se reamintete c o astfel de imagine conine regiuniuniforme care pot aprea de mai multe ori ntr-o imagine. Un exemplu l

constituie o pagin scris la calculator care const din texti icoane. Fiecarecaracter de texti fiecare icoan este o regiune,i fiecare regiune poateaprea de mai multe ori n imagine. O modalitate posibil de compresie aunei astfel de imagini este scanarea sa, identificarea regiunilor,i gsirearegiunilor care se repet. Dac o regiune B este identic cu o regiune A dejagsit, atunci B poate fi compresat prin nregistrarea unui pointer corespunztor lui A n secvena compresat. Metoda descompunerii n blocuri este un exemplu de implementare a acestei abordri.

Abordarea 8 . Se mparte imaginea n regiuni (care se suprapun sau

nu) i se compreseaz prin procesarea pr ilor una cte una. Se presupune c urmtoarea parte de imagine neprocesat este partea cu numrul n. Sencearc regsirea ei n pr ile 1 1n , care au fost deja procesate. Dac partea n poate fi exprimat, de exemplu, ca o combinaie a unor pr ianterioare scalatei rotite, atunci doar cele cteva numere care specific combinaia trebuie salvate,i partean poate fi ignorat. Dac partea n nu poate fi exprimat ca o combinaie de pr i deja procesate, aceasta este procesat i salvat n secvena compresat.

Aceast abordare este baza diferitelor metode fractale pentru

compresia de imagini. Se aplic principiul compresiei de imagine asupra pr ilor de imagine, n loc de pixelii individuali. Aplicat n acest fel, principiul afirm c imaginile ce urmeaz a fi compresate au un anumit


14/69

14

volum de auto-similaritate, adic pr i de imagine sunt identice sau similarecu ntreaga imagine sau cu alte pr i.

10.4. Transform ri folosite n compresia imaginilor

Conceptul matematic de transformare este important n multedomenii, printre carei cel al compresiei de imagini. O imagine poate ficompresat prin transformarea pixelilor si (care sunt corelai) ntr-o

reprezentare unde acetia sunt decorelai. Compresia este obinut dac valorile noi sunt mai mici, n medie, dect cele originale. Compresia cu pierdere de informaie poate fi obinut prin cuantizarea valorilor transformate. Decodorul primete valorile transformate din secvenacompresat i reconstruiete datele originale (exacte sau aproximate), prinaplicarea transformrii inverse. Transformrile discutate n aceast seciunesunt ortogonale.

Termenul de decorelare se refer la faptul c valorile transformatesunt independente unele de altele. Ca urmare, ele pot fi codate independent,

ceea ce face mai simpl construirea unui model statistic. O imagine poate ficompresat, dac reprezentarea sa are redundan. Redundana n imaginideriv din corelarea pixelilor. Dac se transform imaginea ntr-oreprezentare n care pixelii sunt decorelai, se elimin redundana iimaginea a devenit n totalitate compresat.Se consider cazul n care se scaneaz o imagine n ordinea rastruluii segrupeaz perechile de pixeli adiaceni. Deoarece pixelii sunt corelai, cei doi pixeli ai unei perechi, n mod normal, au valori similare. n continuare seconsider perechile de pixeli ca puncte n spaiul bi-dimensional,i se

reprezint grafic. Setie c toate punctele de forma ( x,x) sunt localizate pe prima bisectoare, y = x , aa c este de ateptat ca punctele considerate s fieconcentrate n jurul acesteia. Fig. 10.4a arat rezultatele reprezentrii


15/69

15

pixelilor unei imagini oarecare, n care un pixel are valori de la 0 la 255.Cele mai multe puncte sunt grupate n jurul acestei linii,i doar cteva puncte sunt localizate departe de ea. Acum se transform imaginea prinrotirea tuturor punctelor cu 45 n sensul acelor de ceasornic n juruloriginii, aa nct prima bisectoare coincide acum cu axa x, ca n Fig.10.4 b.

Fig. 10.4. Rotirea unui grup de puncte

Aceasta se face prin intermediul transformrii simple


16/69

16

0 0* *0 0

1 1cos45 sin 45 1( , ) ( , ) ( , ) ( , )1 1sin 45 cos45 2

y x y x y x y = = =

R (10.2)

unde matricea de rotaie R este ortonormal (adic produsul scalar al unuirnd cu el nsui este 1, produsul scalar al rndurilor diferite este 0,i la fel pentru coloane). Transformarea invers este

* * 1 * * * * 1 11( , ) ( , ) ( , ) ( , )1 12

T x y x y x y x y = = =

R R (10.3)

(Inversa unei matrici ortonormale este transpusa sa).

Este evident c majoritatea punctelor ajung s aib coordonatele y nule sau aproape nule, n timp ce coordonatele x nu se modific foarte mult.Distribuiile coordonatelor x i y (adic pixelii cu numr impar i par dintr-oimagine) nainte de rotaie nu difer cu mult, pe cnd, dup rotaie,distribuia coordonatelor x r mne aproape la fel, dar cea a coordonatelor y este concentrat n jurul lui zero.

Cum coordonatele punctelor sunt cunoscute naintei dup rotaie,este simplu s se msoare reducerea ce intervine n corelaia punctelor, princalculul funciei de corelaie i i

i

x y dintre puncte. n acest caz, compresiaf r pierderi a imaginii poate fi efectuat prin simpla folosire a pixelilor transformai n secvena compresat. Dac se accept compresie cu pierderede informaie, atunci toi pixelii pot fi cuantizai, obinndu-se numereimai mici. De asemenea, se pot separa toi pixelii cu numr impar (cei carecreeaz coordonatele x ale perechilor), urmai apoi de toi pixelii cu numr par. Aceste dou secvene sunt numitevectorii coeficien ilor transformrii.A doua secven const din numere micii poate avea, dup cuantizare,iruri de zerouri, care pot conduce la o compresiei mai bun.

Se poate ar ta c dispersia total a pixelilor nu se modific prinrotaie [Sal], din moment ce matricea de rotaie este ortonormal. Totui,deoarece dispersia noilor coordonate y este mic, cea mai mare parte din


17/69

17

dispersie este acum concentrat n coordonatele x. Dispersia este uneorinumit energia distribuiei pixelilor, astfel nct se poate afirma c rotaia aconcentrat (sau compactat) energia n coordonata x i a realizat compresia nacest fel.

Concentrarea energiei ntr-o coordonat prezint avantajul c face posibil cuantizarea acestei coordonate mai fin dect pentru celelaltecoordonate. Urmtorul exemplu ilustreaz eficiena acestei transformrifundamentale.

Exemplul 10.4.Se consider punctul (4,5), ale crui coordonate sunt apropiate.

Folosind ecuaia (10.2), punctul este transformat n(4,5) (9,1) / 2 (6, 36396; 0, 7071)= R . Energiile punctului itransformatului su sunt 2 2 2 24 5 41 (9 1 ) / 2+ = = + . Dac se neglijeaz coordonata mai mic, 4, a punctului, se ajunge la o eroare de24 / 41 0,39= .Dac, ns, se neglijeaz cel mai mic din cei doi coeficieni transformai(0,7071), eroarea rezultat este doar de 20,7071 /41 0,012= . Un alt mod de

a obine aceeai eroare este considerarea punctului reconstruit. Aplicnd punctului transformat12 (9,1) transformarea invers dat de relaia 10.3, se

ajunge la punctul original (4,5). Fcnd acelai lucru cu12 (9,0) rezult

punctul reconstruit aproximat (4,5, 4,5). Diferena de energie dintre punctuloriginali cel reconstruit este aceeai cantitate

2 2 2 2

2 2[(4 5 ) (4,5 4,5 )] 41 40,5 0,012

4 5 41+ + = =

+(10.4)

Aceast transformare simpl poate fi extins cu uurin la orice

numr de dimensiuni. n loc de a selecta perechi de pixeli adiaceni, se potselecta triplete. Fiecare triplet devine un punct n spaiul tri-dimensional,iaceste puncte formeaz o regiune concentrat n jurul liniei care formeaz


18/69

18

unghiuri de 45 cu cele trei axe de coordonate. Cnd aceast linie este rotit astfel nct s coincid cu axa x, coordonatele y i z ale punctelor transformate devin numere mici. Transformarea este f cut prinmultiplicarea fiecrui punct cu o matrice de rotaie de dimensiune 3 3,ortonormal. Punctele transformate sunt apoi separate n trei vectori decoeficieni, din care ultimii doi sunt alctuii din numere mici. Pentrucompresie maxim, fiecare vector de coeficieni trebuie cuantizat separat.

Aceast idee se poate extinde la mai mult de trei dimensiuni, cusingura diferen c nu se pot vizualiza spaii de dimensiuni mai mari de

trei. Unele metode de compresie, cum ar fi JPEG, mpart o imagine n blocuri de 8 8 pixeli fiecare,i rotesc fiecare bloc de dou ori. Aceast rotaie dubl produce un set de 64 de valori transformate, din care prima,numit coeficient DC sau de curent continuu, este mare,i celelalte 63,numite coeficienii AC sau de curent alternativ, sunt, de obicei, mici.Astfel, aceast transformare concentreaz energia n prima din cele 64 dedimensiuni.

10.4.1. Transform ri ortogonale

Transformrile de imagine folosite n practic trebuie s fie rapidei, de preferin, simplu de implementat. Aceasta sugereaz folosireatransformrilor liniare. ntr-o astfel de transformare, fiecare valoaretransformat ic este o sum ponderat a pixelilor jd , unde fiecare este

multiplicat cu un factor (sau coeficient de transformare)ijw . Astfel,

i j ij jc d w= , pentru i,j=1,2, ...,n. (10.4)

Pentru n=4, relaia precedent se scrie matriceal


19/69

19

11 12 13 141 1

21 22 23 242 2

31 32 33 343 3

41 42 43 444 4

w w w wc d w w w wc d

w w w wc d

w w w wc d

=

n generalC = W D (10.4)

Fiecare rnd al luiW este numitvector al bazei .Se dorete determinarea valorilor ponderilor ijw , astfel nct prima

valoare transformat 1c s fie mare,i restul valorilor 2 2, ,...c c s fie mici.Din relaia i j ij jc d w= se observ c ic va fi mare, cnd fiecare pondere

ijw consolideaz contribuia lui jd la ic . Aceasta are loc, de exemplu, cnd

vectorii ijw i jd au valorii semne similare. Invers, ic va fi mic, dac

toate ponderile ijw sunt micii jumtate din ele au semnul opus lui jd .

Astfel, cnd se obine un ic mare, nseamn c vectorul ijw al bazei este

similar cu vectorul de date jd . Un ic mic, pe de alt parte, nseamn c ijw

i jd au forme diferite. n concluzie, vectorii bazeiijw pot fi interpretai camijloace de a extrage caracteristici din vectorul de date.

n practic, ponderile ar trebui s fie independente de date. Altfel, ponderile ar trebui incluse n secvena compresat, pentru a fi folosite dedecodor. Aceast lucru, combinat cu faptul c datele sunt valorile pixelilor,care sunt nenegative, sugereaz o modalitate de a alege vectorii bazei.Primul vector, cel care produce1c , ar trebui s fie alctuit din valori pozitive, poate chiar identice. Aceasta va ntri valorile nenegative ale

pixelilor. Fiecare din ceilali vectori ar trebui s aib jumtate din elemente pozitive, cealalt jumtate, negative. Cnd sunt multiplicai cu valorilenenegative ale datelor, astfel de vectori tind s produc o valoare mic. O


20/69

20

alegere bun a vectorilor bazei ar fi dac acetia ar fi foarte diferii unul dealtul,i astfel pot extrage mai multe caracteristici. Aceasta duce la ideea cavectorii bazei s fie ortogonali. Dac matricea de transformareW esteortogonal, transformarea n sine se numete ortogonal. O alt observaiecare ajut la selectarea vectorilor bazei este c acetia ar trebui s aib frecvene din ce n ce mai mari, extr gnd astfel caracteristici de frecven mai nalt din date pe parcursul calculului valorilor transformate.

Aceste consideraii sunt satisf cute de matricea ortogonal:1 1 1 1

1 1 1 1W1 1 1 11 1 1 1

=

(10.5)

Primul vector al bazei (rndul de sus al luiW ) const numai dinvalori 1, deci frecvena sa este zero. Fiecare din vectorii urmtori are doi de+1 i doi de -1, deci produc valori transformate mici,i frecvenele lor (msurate ca numrul de schimbri de semn de-a lungul vectorului bazei)devin mai nalte. Aceast matrice este similar cu transformarea Walsh-Hadamard [ref].

Exemplul 10.5.Se transform vectorul de date (4, 6, 5, 2) cu ajutorul matricei 10.5

i se obine

=

15

317

2564

111111111111

1111

Rezultatele sunt ncurajatoare, din moment ce1c este mare (n

comparaie cu datele originale)i dou din valorile r mase ic sunt mici.


21/69

21

Totui, energia datelor originale este 2 2 2 24 6 5 2 81+ + + = , n timp ceenergia valorilor transformate este 2 2 2 217 3 ( 5) 1 324+ + + = , de patru orimai mult. Este posibil a se conserva energia, prin multiplicarea matricei detransformareW prin factorul de scalare 1/2. Noul produs (4,6,5,2)T W genereaz acum valorile transformate (17/2, 3/2, -5/2, 1/2). Energia esteconservat, dar este concentrat n prima component, care conine

28,5 /81 89%= din energia total, n comparaie cu datele originale, n care prima component coninea 24 /81 20%= din energie.

Un alt avantaj al luiW este c efectueaz i transformarea invers.Produsul (17 / 2, 3/ 2, -5 / 2, 1/ 2)T W reconstruiete datele originale (4, 6,5, 2).

Pentru a aprecia eficiena transformrii, se cuantizeaz vectorultransformat (8,5; 1,5; -2,5; 0,5) n ntregii (9, 1, -3, 0)i se efectueaz transformarea invers, obinndu-se vectorul (3,5; 6,5; 5,5; 2,5). Un altexperiment este de a renuna complet la cele dou elemente mai mici alevectoruluii de a face transformarea invers pentru vectorul (8,5; 0; -2,5;0). Aceasta produce datele reconstruite (3; 5,5; 5,5; 3), nc foarte apropiatede valorile originale. n concluziei aceast transformare simpl este util n compresie.

10.4.2. Transform ri bi-dimensionale

Exemplul 10.6.Avnd datele bi-dimensionale sub forma de matrice 44

=

9542674563869674

D


22/69

22

(n care prima coloan este identic cu exemplul anterior), se poate aplicatransformare uni-dimensional anterioar . Rezultatul este:

1 1 1 11 1 1 111 1 1 121 1 1 1

= =

C' WD

8,5 11,5 10,5 151,5 3,5 1,5 02,5 0,5 0,5 3

0,5 0,5 2,5 0

=

D

Fiecare coloan din C este transformarea unei coloane dinD. Se observ primul element al fiecrei coloane a luiC este dominant. De asemenea,toate coloanele au aceeai energie. Se poate considera c C este primaetap dintr-un proces n doi pai care produce transformarea bi-dimensional a matriceiD. Pasul doi ar trebui s transforme fiecare linie alui C , i aceasta se face prin nmulirea lui C cu transpusaW T. Pentruacest caz particular W este simetric, deci se ajunge la T TC=C'W =WCWsau

8,5 11,5 10,5 15 1 1 1 11,5 3,5 1,5 0 1 1 1 112,5 0,5 0,5 3 1 1 1 12

0,5 0,5 2,5 0 1 1 1 122,75 2,75 0,75 3,751,75 3,25 0,25 1,750,25 3,25 0,25 2,251,25 1,25 0,75 1,75

= =

=

C

Elementul din stnga sus este dominant, coninnd 89% din energiatotal de 579 din matricea de dateD original. Transformarea n doi pai, bi-dimensional, a redus corelarea att n dimensiunea vertical ct i n cea

orizontal.n continuarea se vor prezenta pe scurt cteva transformri uzuale.


23/69

23

10.4.3. Transformarea Karhunen-Love (KLT)

Transformarea Karhunen-Love (KLT) are cea mai bun eficien din punct de vedere al compactrii energiei (sau, altfel spus, decorelare a pixelilor), dar are mai mult o valoare teoretic dect una practic.

Se consider o imagine care se mparte nk blocuri de cten pixelifiecare, unden este de obicei 64, dar poate aveai alte valori,i k depindede mrimea imaginii. Se consider blocurile de vectorib (i) , undei=1, 2, ...,k . Pe baza acestora se calculeaz vectorul medie ( )( ) /ii k = b b . Sedefinete un nou set de vectori( ) ( )i i= v b b , care vor avea media zero.Matricea transformrii KLT are dimensiuneann i se noteaz cu A.Rezultatul transformrii vectoruluiv(i) este vectorul ponderew(i)=Av (i).Valoarea medie a luiw(i) este de asemenea zero. Se construiete o matriceV ale crei coloane sunt vectoriiv(i) i o alt matrice ale crei coloane suntvectorii ponderew(i).

V=(v(1),v(2),.....,v(k)), W =(w(1),w(2),....,w(k)) (10.6)MatriceleV i W au fiecaren liniii k coloane. Din definiia luiw(i)

rezult c W=AV .Cei n vectori de coeficieni c(j) din transformarea Karhunen-Love

sunt dai de relaia:( ) (1) (2) ( )( , ,..., ), 1,2,..., j k j j jw w w j n= =c (10.7)

Astfel, vectorulc(j) este format din elementele j ale tuturor vectorilor ponderew(i) cu i=1,2,...,k (c(j) este coordonata j a vectorilor w(i)).

Se examineaz elementele matricei produs (WW T) (aceasta este omatrice de dimensiuninn ). Un element oarecare, din liniaa i coloanab,al acestei matrice este o sum de produse:

( ) ( ) ( ) ( ) ( ) ( )

1 1( )

k k T i i a b a b

ab a b i ii i

w w c c= =

= = = W W c c , pentru , [1, ]a b n (10.8)


24/69

24

Deoarece valoarea medie a fiecrui vector w(i) este zero, un element(WW T) jj, de pe diagonala principal a matricei produs, este variana saudispersia elementului j (sau a coordonatei j) a vectoruluiw(i).

Elementele din afara diagonalei sunt covarianele vectorilor w(i),adic un element ( )T abWW este covariana coordonatelor a i b ale

vectorilor w(i), care este egal cu produsul scalar ( ) ( )a bc c . Un deziderat major al transformrilor aplicate imaginii este de a decorela coordonatelevectorilor. Din teoria probabilitilor se tie c dou coordonate sunt

decorelate, dac covariana lor este zero. Un alt deziderat este acela decompactare a energiei, care, de fapt este n strns legtur cu primul.Avnd n vedere aceste lucruri, se urmrete gsirea unei matrice detransformareA, astfel nct produsul (WW T) s fie o matrice diagonal.

Din definiia matriceiW se obine:WW T=(AV )(AV )T=A(VV T)AT (10.9)

Matricea VV T este simetric, i elementele ei sunt covarianelecoordonatelor vectorilor v(i):

( ) ( )

1

( )k

T i iab a b

i

v v=

= VV , pentru , [1, ]a b n (10.10)Deoarece matricea ( )T VV este simetric, vectorii si proprii suntortogonali. Se normalizeaz aceti vectori, pentru a fi ortonormalii se alegca linii ale matriceiA. Rezultatul obinut este:

1

2

3

0 0 00 0 0

( ) 0 0 0

0 0 0

T T T

n

A A

= =

WW VV

(10.11)

Aceast alegere a matriceiA conduce la o matrice T WW diagonal, alecrei elemente de pe diagonala principal sunt valorile proprii ale matricei


25/69

25

T VV . MatriceaA este matricea transformrii Karhunen Loeve, liniilesale fiind vectorii bazei KLTi energiile (varianele) vectorilor transformaisunt valorile proprii 1 2, ,..., n ai matricei ( )T VV . Vectorii bazeitransformrii KL nu sunt fici, ei sunt dependeni de date, fiind calculai pe baza pixelilor imaginii originale. Din acest motiv, ei trebuie s inclui nsecvena de date compresate, fapt ce scade eficiena acestei transformate.

Exemplul 10.7.Se urmrete obinerea transformatei Karhunen Loeve de ordinul 2

pentru o secven de intrare arbitrar . Matricea de autocorelaie a unui proces sionar este

( ) ( )0 1(1) (0)

xx xx

xx xx

R R

R R

=

R (10.12)

unde ( ) xx R n , n=0,1 sunt valorile funciei de autocorelaie.Rezolvnd ecuaia 0|| = R I , se obin cele dou valori proprii

1 2(0) (1), (0) (1) xx xx xx xx R R R R = + = . Vectorii proprii corespunztori sunt

= 1V =

2V (10.13)

unde , sunt constante arbitrare. Dac se impune condiia deortonormalitate, care presupune ca amplitudinea vectorului s fie unu, seobine

21==

i matricea K este:

=

1111

21

K (10.14)


26/69


27/69


28/69

28

Rndurilei coloanele de blocuri din aceast figur corespund unor valoriale lui ui respectiv, v, de la 0 la 3. Numrul de schimbri de semn pe parcursul unui rnd sau al unei coloane a unei matrice se numete secven ierea rndului sau coloanei.

Matricele corespunztoare transformatei DWHT pot fi obinuterecursiv i ca rearanjri ale matricelor discrete Hadamard care sunt de oimportan particular n teoria codrii [ref]. O matrice Hadamard dedimensiune N are proprietatea c THH =NI unde I este matricea unitate.Matricele Hadamard ale cror dimensiuni sunt puteri ale lui doi pot ficonstruite astfel:

=

N N

N N N H H

H H H 2 (10.18)

cu [ ]11 = H . Astfel se obin

=

=

1111

11

112 H H

H H H (10.19)

==

111111111111

1111

22

224 H H

H H H (10.20)

=

=

11111111111111111111111111111111

111111111111111111111111

11111111

44

448 H H

H H H (10.21)


29/69

29

Matricea H a transformrii DWHT poate fi obinut din matriceaHadamard prin multiplicarea acesteia cu un factor de normalizare, astfelnct THH =I , i prin reordonarea liniilor n ordine descresctoare a

frecvenei. Normalizarea implic multiplicarea matricei cu N

1 .

Reordonnd 8 H , se obine

1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 111 1 1 1 1 1 1 181 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 1

H

=

(10.22)

Deoarece matricea f r factorii de scalare const din 1, operaia detransformare const doar n adunare i scdere. Din acest motivtransformata este util n situaii n care minimizarea ctigului de calculeste foarte important.

10.4.5. Transformarea Haar

Transformarea Haar [ref] este bazat pe funcia Haar hk (x), care estedefinit pentru x [0,1] i pentru k=0, 1, ..., N-1, unde N=2n.

Orice ntregk poate fi exprimat sub form de sum astfel k=2p+q-1,

unde 0 p n-1, q=0 sau 1 pentru p=0,i 1 q 2 p

pentru p 0. Deexemplu, pentru N=4=22, se obine 0=20+0-1, 1=20+1-1, 2=21+1-1, i3=21+2-1.


30/69

30

Funcia de baz a transformatei Haar este definit astfel:10,1)()( 000 == x pentru

N xh xh

(10.23)i

/ 2

/ 2

1 ( 1) / 22 ,2 2

1 ( 1) / 2( ) ( ) 2 ,2 2

0, n rest

p p p

def p

k pq p p

q q x

q qh x h x x

N

. (10.28)

Se ncepe cu un set de opt valori de datet p (pixeli, eantioane de sunet, saualte date) i se obine un set de opt coeficieni DCT, f G . Decodorul primete coeficienii DCT n seturi de opt,i aplic transformarea invers DCT (IDCT) pentru a reconstrui valorile de date originale (tot n grupuri decte opt). IDCT se calculeaz cu relaia

7

0

1 (2 1)cos2 16t j j j

t j p C G

=

+ = , pentru t=0, 1,...., 7 (10.29)

Exemplul 10. 7.Urmtorul experiment ilustreaz eficiena DCT. Se ncepe cu setul

de opt datep=(12, 10, 8, 10, 12, 10, 8, 11), se aplic acestora DCT uni-dimensional i se obin cei opt coeficieni: 28,6375; 0,571202; 0,46194;1,757; 3,18198; -1,72956; 0,191342; -0,308709.

Acetia pot fi folosii pentru a reconstrui cu precizie datele originale(cu excepia unor mici erori cauzate de precizia limitat a mainilor). Scopuleste, ns, de a compresa datelei mai mult, astfel nct se recurge lacuantizarea coeficienilor obinui.

Mai nti acetia se cuantizeaz la 28,6; 0,6; 0,5; 1,8; 3,2; -1,8; 0,2;-0,3; i apoi se aplic IDCT, obinndu-se coeficienii 12,0254; 10,0233;7,96054; 9,93097; 12,0164; 9,99321; 7,94354; 10,9989.


34/69

34

Se cuantizeaz apoi coeficienii i mai mult, la 28; 1; 1; 2; 3; -2; 0;0, i se aplic IDCT, obinndu-se valorile 12,1883; 10,2315; 7,74931;9,20863; 11,7876; 9,54549; 7,82865; 10,6557.

n sfr it, se cuantizeaz coeficienii la 28; 0; 0; 2; 3; -2; 0; 0,i prinaplicarea IDCT se obine secvena 11,236; 9,62443; 7,66286; 9,57302;12,3471; 10,0146; 8,05304; 10,6842; unde cea mai mare diferen dintre ovaloare original (12) i o valoare reconstruit (11,236) este 0,764 (sau6,4% din 12).

DCT bi-dimensional Din experien se tie c pixelii unei imagini sunt corelai pe dou

dimensiuni, nu doar pe una (un pixel este corelat cu vecinii si de la stngai de la dreapta, deasuprai dedesubt). De aceea metodele de compresie aimaginii folosesc DCT bi-dimensional, dat de relaia

1 1

0 0

1 (2 1) (2 1)cos cos2 22

n n

ij i j xy x y

y j x iG C C p

n nn

= =

+ + = , (10.30)

pentru 0 i, j n-1. Imaginea este mpr it n blocuri denn pixeli xy p

(de obicei se folosete n=8), i ecuaia (10.30) este folosit pentru a obineun bloc de 88 coeficieni DCT, ijG , pentru fiecare bloc de pixeli. Dac compresia este cu pierdere de informaie, coeficienii sunt cuantizai.Decodorul reconstruiete un bloc de valori de date (aproximate sau precise) prin calculul IDCT.

1 1

0 0

1 (2 1) (2 1)cos cos2 22

n n

xy i j iji j

y j x i p C C G

n nn

= =

+ + = (10.31)

unde1

, 0, pentru 0,1,..., 721, 0,

f f C f f

== =>


35/69

35

DCT bi-dimensional poate fi interpretat n dou moduri diferite, ca orotaie (de fapt, dou rotaii separate),i ca baz a unui spaiu vectorialn-dimensional. n prima interpretare se consider un bloc denn pixeli. Mainti se consider fiecare rnd al acestui bloc ca un punct

,0 ,1 , 1( ; ;...; ) x x x n p p p n spaiul n-dimensional, i se rotete punctul cuajutorul transformrii date de suma din interior

1

,0

(2 1)1 cos2

n

x j j xy y

y jG C p

n

=

+ = (10.32)

a ecuaiei (10.30). Aceasta transformare are ca rezultat un bloc G1 x,j de nn coeficieni, unde primul element al fiecrui rnd este dominanti restulelementelor sunt mici. Suma exterioar a ecuaiei (10.30) este

1

,0

1 (2 1)1 cos22

n

ij i x j x

x iG C G

nn

=

+ = (10.33)

Aici, coloanele lui G1 x,j sunt considerate puncte n spaiul n-dimensional,isunt rotite. Rezultatul este un coeficient mare n colul stnga-sus al bloculuii n2 - 1 coeficieni mici n rest. Aceast interpretare consider DCT bi-dimensional ca dou rotaii separate, fiecare nn dimensiuni. Este interesant

de observat c dou rotaii n n dimensiuni sunt mai rapide dect una nn2

dimensiuni, deoarece n al doilea caz este necesar o matrice de rotaie dedimensiunen2n2.

A dou interpretare (presupunndn = 8) folosete ecuaia (10.30) pentru a crea 64 blocuri de 88 valori fiecare. Cele 64 de blocuri sunt apoifolosite ca baz a unui spaiu de vectori 64-dimensionali (sunt imagini de baz). Imaginile de baz folosite n DCT bi-dimensional sunt date nFig.10.7. Orice bloc B de 88 pixeli poate fi exprimat ca o combinaieliniar a imaginilor de baz, i cele 64 de ponderi ale acestei combinaii

liniare sunt coeficienii DCT ai blocului B.


36/69

36

Fig. 10.7. Imaginile de baz pentru transformata discret cosinus bi-dimensinal

Exemplul 10.8.n continuare, se prezint rezultatele aplicrii transformatei DCT bi-

dimensionale la a dou blocuri de 88 valori. Primul bloc, cu valorile dinTabelul 10.2, are valori ntregi puternic corelate n intervalul [8,12]i celde-al doilea, valori aleatoare n acelai interval. Primul bloc conduce la uncoeficient DC mare, urmat de coeficieni AC mici (incluznd 20 de zerouri).

Coeficienii celui de-al doilea bloc, prezentai n Tabelul 10.3, includ doar un zero.


37/69

37

Tabelul 10.2. DCT bi-dimensional a unui bloc de valori corelate

12 10 8 10 12 10 8 11 81 0 0 0 0 0 0 011 12 10 8 10 12 10 8 0 1,57 0,61 1,19 0,38 -1,81 0,20 -0,328 11 12 10 8 10 12 10 0 -0,61 0,71 0,35 0 0,07 0 0,02

10 8 11 12 10 8 10 12 0 1,90 -0,35 4,76 0,77 -3,39 0,25 -0,5412 10 8 11 12 10 8 10 0 -0,38 0 -0,77 8,00 0,51 0 0,0710 12 10 8 11 12 10 8 0 -1,81 -0,07 -3,39 -0,51 1,57 0,56 0,258 10 12 10 8 11 12 10 0 -0,20 0 -0,25 0 -0,56 -0,71 0,29

10 8 10 12 10 8 11 12 0 -0,32 -0,02 -0,54 -0,07 0,25 -0,29 -0,90

Tabelul 10.3. DCT bi-dimensional a unui bloc de valori aleatoare

8 10 9 11 11 9 9 12 79,12 0,98 0,64 -1,51 -0,62 -0,86 1,22 0,3211 8 12 8 11 10 11 10 0,15 -1,64 -0,09 1,23 0,10 3,29 1,08 -2,979 11 9 10 12 9 9 8 -1,26 -0,29 -3,27 1,69 -0,51 1,13 1,52 1,339 12 10 8 8 9 8 9 -1,27 -0,25 -0,67 -0,15 1,63 -1,94 0,47 -1,3012 8 9 9 12 10 8 11 -2,12 -0,67 -0,07 -0,79 0,13 -1,40 0,16 -0,15

8 11 10 12 9 12 12 10 -2,68 1,08 -1,99 -1,93 -1,77 -0,35 0 -0,8010 10 12 10 12 10 10 12 1,20 2,10 -0,98 0,87 -1,55 -0,59 -0,98 2,7612 9 11 11 9 8 8 12 -2,24 0,55 0,29 0,75 -2,40 -2,40 0,06 1,14

Compresia unei imagini cu DCT presupune parcurgerea urmtorilor pai:

Se mparte imaginea nk blocuri Bi , i=1,2,,k , de nn (obinuit,88) pixeli fiecare.

Se aplic DCT bi-dimensional fiecrui bloc Bi. Aceastatransformare exprim blocul ca o combinaie liniar a celor 64 deimagini de baz din Fig. 10.7. Rezultatul este un bloc, numit vector

( )iW de 64 de ponderi ( )i jw , unde j=0, 1, ...,.63.


38/69


39/69


40/69

40

opt coeficieni (0; 256,3; 0; 90; 0; 60,1; 0; 51). Folosind aceti coeficieni,IDST poate reconstrui valorile originale, dar este uor de observat c nacest caz coeficienii AC nu se comport ca cei ai DCT. Acetia nu devindin ce n ce mai micii nu exist iruri de zerouri ntre ei.

Aplicnd DST asupra urmtoarelor opt valori puternic corelate: 11;22; 33; 44; 55; 66; 77; 88, rezult un set de coeficieni i mai puinconvenabili (0; 126,9; -57,5; 44,5; -31,1; 29,8; -23,8; 25,2), neexistndabsolut deloc compactare de energie.

Aceste argumentei exemple, mpreun cu faptul c DCT produce

coeficieni puternic decorelai, justific folosirea DCT n defavoarea DST ncompresia de date.

10.5. Compresia JPEG (Joint Photographers ExpertsGroup)

Domeniul compresiei (codrii) de imagini este legat de minimizareanumrului de bii necesari pentru a reface o imagine, cu aplicaii n specialn transmisiai stocarea imaginilor. Aplicaiile din domeniul transmisiilor de imagini se ntlnesc n televiziunea radiodifuzat, comunicaiile spaiale,radar i sonar, reele de telecomunicaii, transmisii fax, teleconferine etc.Compresia imaginilor este esenial din punct de vedere al memor rii(stocrii) imaginilor n aplicaii de imagistic medical, n tehnica videodigital, pentru realizarea documentelor multimedia etc. Noile tehnologii decompresie a imaginilor ofer o soluie posibil pentru integrarea aplicaiilor de imaginii video digitale. Ratele de compresie au ajuns n prezent pn la1:100, depinznd de calitatea imaginii ref cute. Tehnica de compresie nueste suficient pentru a putea rezolva problemele care apar n aplicaiilemultimedia. Pentru a putea realiza portabilitatea aplicaiilor de imaginiisecvene video digitale pe mai multe sisteme, este necesar implementarea


41/69


42/69

42

reduse, f r o afectare deranjant a percepiei vizuale a imaginii. Evident c acest lucru este determinat de gradul de compresie acceptat.

JPEG este o metod sofisticat de compresie cu pierdere pentruimagini color sau alb-negru (cu scar de gri). Un avantaj al JPEG este faptulc folosete muli parametri, permind astfel utilizatorului s reglezecantitatea de date pierdutei, de asemenea, rata de compresie. Momentanreprezint cel mai bun standard existent n materie de compresie aimaginilor statice. Standardul este implementat att n format software ctihardware pentru a satisface necesitile de prelucrare n timp real a

aplicaiilor multimedia. Creat iniial pentru compresia imaginilor statice,standardul a fost extinsi pentru secvenele video. Standardul realizat pentru secvene video se numete M-JPEG (Motion JPEG). Practic n cazulsecvenelor video digitale fiecare cadru este considerat ca o imagine fix icompresat cu standardul JPEG. Metoda nu este cea mai eficient din punctul de vedere al mrimii ratei de compresie, dar ofer o alternativ pentru compresia video digital. Adesea, ochiul uman nu distinge nici odegradare a imaginii chiar la o rat de compresie de 10:1 sau 20:1.

Exist patru moduri principale de operare specificate de standardul

JPEG :- modul de baz, n care fiecare component a imaginii este codat

printr-o singur scanare stnga-dreapta, respectiv sus-jos;- codarea expandat DCT cu pierderi, n care se realizeaz o codare

progresiv a spectrelor imaginii de intrare;- codarea f r pierderi, n care imaginea este codat astfel nct se

garanteaz reproducerea exact la decodare;- codarea ierarhic, n care imaginea este codat la rezoluii multiple.n continuare, se va prezenta detaliat numai primul dintre acestea,

celelalte numai principial.


43/69

43

10.5.1. Modul de baz (baseline)Schema bloc a algoritmului de codare JPEG este dat n Fig. 10.8.

Fig. 10.8 Algoritmul de codare JPEG

Principiul compresiei prin metode de tip DCTCompresia cu pierderi presupune cteva etape de prelucrare,i anume:

Transformarea din reprezentarea (R,G,B) n reprezentarea(Y,U,V)

n procedurile de compresie a imaginii se prefer o reprezentare aculorii diferit de cea normal (R,G,B),i anume, reprezentarea (Y,U,V),obinut cu relaiile 10.1. Valorile componentelor Y, Ui V sunt cuprinsentre -128 i 127. Utilitatea acestei reprezentri echivalente se poateevidenia n Fig. 10.9, n care sunt prezentate descompunerile n forma(R,G,B) respectiv (Y,U,V) ale imaginii din Fig. 10.1a.


44/69

44

Componenta R Componenta G

Componenta B Componenta Y

Componenta U Componenta V

Fig. 10.9. Componentele R, G, B, Y, U, V ale imaginii 10.1.a

Analiznd acest exemplu, se pot face cteva observaii importanteianume:- componenta Y corespunde unei imagini alb-negru;- componentele Ui V conin mult mai puine detaliii prezint un contrastmult mai redus.


45/69

45

Datorit absenei detaliilor i contrastului sczut al componentelor Ui V, acestora li se aplic o subeantionare cu factorul 2 pe ambele direcii,vertical i orizontal, inndu-se cont de faptul c percepia ochiului estemai mic la semnalele de crominan, fa de cele de luminan. Modul derealizare a subeantionrii const n nlocuirea blocurilor de 2x2 puncte cuun singur punct care are intensitatea egal cu media celor 4. n acestecondiii imaginea va fi descris de componentele Ui V, din Fig. 10.10.

Componenta U' (subesantionat) Componenta V' (subesantionat)

Fig. 10.10 Componentele subeantionate Ui V

Prin aceste operaii se realizeaz o prim compresie, cu factorul 2:1.Astfel, reprezentarea (R,G,B) pentru imaginea din exemplu cu rezoluia de320x240 puncte necesit 3 componente a cte 320x240=76800 elemente,adic un total de 230400 elemente (octei). Reprezentarea (Y,U',V') necesit 320x240=76800 elemente pentru Yi 160*120=19200 elemente pentru U'i V' adic un total de 115200 elemente (octei).

Descompunerea n blocuriProcedura de compresie se aplic unor blocuri de imagine de 8x8

puncte. Dac nici una din dimensiunile imaginii nu este multiplu de 8,codorul copie ultima coloan sau linie pn cnd lungimea final este


46/69


47/69

47

n blocuri de 8x8 pixeli, aa cum se poate observai n Fig.10.8. Fiecrui bloc astfel obinut i se aplic transformata cosinus discret bi-dimensional,folosind ecuaiile:

DCT:7 7

0 0

1 (2 1) (2 1)cos cos4 16 16ij i j xy x y

y j x iG C C p

= =

+ + = (10.35)

IDCT:7 7

0 0

1 (2 1) (2 1)cos cos4 16 16 xy i j iji j

y j x i p C C G

= =

+ + = (10.36)

unde

1 , dac 021, n rest

i j

i j

C C i j

C C

= = = =

= =(10.37)

Pentru a ilustra cum lucreaz algoritmul, se va folosi un bloc dedimensiune 88 din componenta de luminan a imaginii Lena, aa cum este prezentat n Tabelul 10.4.

Tabelul 10.4. un bloc de dimensiune 88 al imaginii Lena

124 125 122 120 122 119 117 118121 121 120 119 119 120 120 118126 124 123 122 121 121 120 120124 124 125 125 126 125 124 124127 127 128 129 130 128 127 125143 142 143 142 140 139 139 139150 148 152 152 152 152 150 151156 159 158 155 158 158 157 156

Considernd blocul de 88 pixeli din Tabelul 10.4, se scade 128 dinfiecare elementi aplicnd DCT, se obin coeficienii DCT prezentai nTabelul 10.5.


48/69


49/69

49

cuantizarea matricei transformate

Operaia de cuantizare este singura n care se pierde informaie.Algoritmul JPEG utilizeaz coeficieni de cuantizare pentru a cuantizadiferiii coeficieni de intrare. Mrimea pasului de cuantizare este organizat ntr-un tabel, numit tabel de cuantizare. Un exemplu de tabel de cuantizaredin recomandrile JPEG este prezentat n Tabelul 10.6. Fiecare valoarecuantizat este reprezentat de o etichet. Prin cuantizare se ntelegempr irea element cu element a matriciiG cu o matrice de cuantizareQ, cu

reinerea doar a pr ii ntregi, rezultnd o matriceI .

Tabelul 10.6. Coeficienii de cuantizare pentru luminanta (a) si pentrucrominanta (b)

(a)

16 11 10 16 24 40 51 6112 12 14 19 26 58 60 5514 13 16 24 40 57 69 5614 17 22 29 51 87 80 62

18 22 37 56 68 109 103 7724 35 55 64 81 104 113 9249 64 78 87 103 121 120 101

72 92 95 98 112 100 103 99

(b)17 18 24 47 99 99 99 9918 21 26 66 99 99 99 9924 26 56 99 99 99 99 9947 66 99 99 99 99 99 99

99 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 99


50/69

50

99 99 99 99 99 99 99 99

Eticheta corespunztoare valorii cuantizate a coeficienilor ijG aitransformatei este

, 0,5ij

i j t ij

G I

Q

= +

(10.36)

undet ijQ este elementul (i,j) din tabelul de cuantizarei este cel mai

mare ntreg mai mic dect x. Se consider coeficientul 00G din Tabelul10.5, care este 39, 88. Din tabelul 10.6a,t Q00 este 16, deci,

0039,88 0,5 2,9925 2

16 I

= + = = (10.37)

Valoarea reconstruit este obinut din etichet, prin multiplicareaacesteia cu intrarea corespunztoare n tabelul de cuantizare. Deci, valoarea

reconstruit a 00 va fi 00 00t Q adic 2*16=32. Eroarea de cuantizare n

acest caz este 39, 88-32=7, 88. Similar, din Tabelele 10.5i 10.6, 01G este

6, 56i t Q01 este 11, deci

016,56 0,5 1,096 111

I = + = =

(10.38)

Valoarea reconstruit este 11 i eroarea de cuantizare este 11-6,56 = 4,44.Continund n acest mod, se obin eantioanele din Tabelul 10.7.

Tabelul 10.7. Coeficientii cuantizai obinui folosind tabelul de cuantizareal coeficienilor

2 1 0 0 0 0 0 0


51/69

51

-9 0 0 0 0 0 0 03 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0

Se observ c, n urma cuantizrii, n matricea coeficienilor cuantizai, fenomenul de concentrare a valorilor mari n colul din stngasus, i predominaa valorilor mici (chiar zero) n rest, este mult maiaccentuat.

Pierderea de informaie se datoreaz realizrii mpr irii cu reinereadoar a par ii ntregi a rezultatelor. n acest fel valorile pierd din precizie(cele mici transformndu-se n zero). Efectul acestei pierderi, ns, nu estesesizabil deoarece, dup cum se observ, pierderile cele mai mari suntconcentrate la nivelul coeficienilor de nalt frecven, care au pondere

redus n imagine i care, corespunznd detaliilor fine, sunt mai puinobservabile de ctre ochiul uman.Rolul operaiei de cuantizare este acela de a obine ct mai multe

valori nule sau mici, acestea avnd avantajul unei codri eficiente realizat ulterior. Transformata cosinus discret ofer posibilitatea de a realizaaceast operaie astfel nct efectul pierderii de informaie s fie ct mairedus.Din Tabelul 10.7 care conine eantioanele cuantizate se poate observa c mrimea pasului crete pe msura ndeprtrii de coeficientul DC.

Deoarece eroarea de cuantizare este o funcie cresctoare de mrimea pasului, coeficienii de nalt frecven vor fi afectai de o eroare decuantizare mai mare dect cei de joas frecven. Decizia asupra mrimii


52/69

52

relative a pasului de cuantizare se bazeaz pe modul de percepere a erorilor de sistemul vizual uman. Diferii coeficieni ai transformrii au importan perceptual diferit. Erorile de cuantizare din coeficieni DCi AC de joas frecven sunt mai uor de detectat dect erorile de cuantizare pentrucoeficienii AC de nalt frecven. De aceea se folosete un pas mai mare pentru coeficienii mai puin importani perceptual.

Deoarece cuantizoarele au nivelul 0 ca nivel de reconstrucie, procesul de cuantizare funcioneaz, de asemenea,i ca operaie de codarede prag. Toi coeficienii cu amplitudinea mai mic dect jumtate din

mrimea pasului vor fi zero. Deoarece mrimea pasului la sfr itul scanariin zig-zag este mare, probabilitatea gsirii unei secvene lungi de zerocrete. Acest efect poate reprezenta o modalitate de modificare a ratei. Prinmrirea pasului, se poate reduce numrul de valori diferite de zero necesare pentru a fi transmise, ceea ce nseamn o reducere a numrului de biinecesari.

codarea elementelor din matricea coeficien ilor cuantiza iCoeficienii cuantizai sunt scanai zig-zag, n scopul obinerii unei

secvene unidimensionale, ce va fi aplicat codorului entropic. Aa cum s-amai precizat, primul coeficient se numete coeficient de curent continuu,DC, i reprezint media intensitii blocului. Ceilali 63 de coeficieni senumesc coeficieni AC (coeficieni de curent alternativ). Scanarea n zig-zagse face n ideea ordonrii dup spectrul de frecven. Deoarececomponentele de frecven nalt au valori aproximativ nule, n urmascanrii zig-zag rezult un ir de zerouri la sfr itul secvenei, dnd posibilitatea realizrii unei codri eficiente RLC (Run Length Coding)iHuffman.

n algoritmul de compresie JPEG sunt utilizate dou proceduri decodare diferite. Prima procedur este utilizat pentru codificareaelementului I00, care este coeficientul DC, a doua procedur utilizndu-se


53/69

53

pentru codificarea celorlali 63 de coeficieni AC. Coeficientul DC estecodat diferenial fa de coeficientul DC din blocul anterior, folosindalgoritmul DPCM (Differential Pulse Code Modulation). Coeficienii ACsunt codai RLC. Coeficienii DC i AC astfel codai vor fi codai apoientropic utiliznd codarea Huffman.

Codarea coeficien ilor DCDin Fig. 10.7 se observ c matricea de baz corespunztoare

coeficienilor DC este o matrice constant, astfel nct coeficientul DC este

media (sau un pultiplu al acesteia) pixelilor din blocul de dimensiune 88.Valoarea medie a pixelilor din orice bloc 88 nu va diferi substanial devaloarea medie din blocul 88 vecin; de aceea valorile coeficienilor DCvor fi relativ apropiate, motiv pentru care este eficient a coda diferena ntreacestai valoarea coeficientului DC corespunztoare blocului de 8x8 puncteanterior din aceeai categorie (Y, U sau V), dect etichetele n sine.

n funcie de numrul de bii folosii la codarea valorii pixelului,numrul de valori pe care le pot lua etichetelei, deci, diferenele dintrecoeficieni, poate deveni destul de mare. Un cod Huffman pentru un alfabet

aa mare ar fi greu de implementat. Recomandarea JPEG rezolv aceast problem prin partiionarea valorilor pe care le pot lua diferenele, n clase.Mrimea acestor clase crete n puteri ale lui doi. Astfel, clasa zero are unsingur membru, clasa unu are doi membri, clasa doi are patru membrii aamai departe. Numrul clasei este codat Huffman. Claselei cuvintele de codHuffman corespunztoare acestora sunt prezentate n Tabelul 10.8. Fiecarelinie a Tabelul 10.8 conine numere mai marii mai multe dect ale liniei precedentei, neconinnd numerele din linia precedent. Linia i coninentregi din domeniul [-(2i-1),+ (2i-1)], din care lipsete intervalul din mijloc

[-(2i-1-1),+ (2i-1-1)]. n codarea coeficienilor DC se transmite codulcorespunztor claseii (liniei din tabel) n care se ncadreaz numrul, urmat


54/69

54

de i bii care reprezint numrul coloanei din Tabelul 10.8 n care se afl numrul ce trebuie codat.

Numrul coloanei, C, este reprezentarea pei bii a valorii diferenei,n cazul valorilor pozitive sau de cei mai puin semnificativii bii aireprezentrii valorii diferenei minus 1, n complement fa de 2, dac aceasta este negativ.

n cazul valorilor din Tabelul 10.7, considernd c blocul nu este primul, eticheta corespunztoare coeficientului DC este codat diferenial,adic se codeaz diferena dintre valoarea cuantizat a etichetei din acest

bloci valoarea cuantizat a esantionului din blocul anterior. Dac blocul de procesat este primul, se transmite n clar valoarea coeficientului DC.

De exemplu, dac valoarea diferenei care trebuie codificat este 21i apar ine componentei Y, se transmite nti codul pentru clasa 5, care este111110. Valoarea este pozitiv i se gsete n a 21-a coloan a liniei 5(numrarea coloanelor ncepe cu 0), deci la acest cod trebuie adugat reprezentarea pe 5 bii a numrului 21 care este 10101, codul complet fiind11111010101.

Dac, ns, valoarea care trebuie codat este -21, clasa este aceeai,

diferena fiind valoarea negativ a coeficientului. Aceast valoare se gseten coloana a 10-a a clasei 5. Aadar, fie se transmite reprezentarea pe 5 biia numrului coloanei, 10, care este 01010, fie se transmit ultimii 5 bii aireprezentrii n complement fa de 2 a numrului (-21), din care se scade 1,adic (-22)2C= 101010, ai crui ultimi 5 bii sunt identici cu ai numrului 10.Codul complet va fi n acest caz 11111001010.

n cazul coeficientului DC din Tabelul 10.7, dac se presupune c eticheta corespunztoare din blocul anterior a fost -1, atunci diferena va fi3. Din Tabelul 10.9 se observ c aceast valoare apar ine clasei 2. Deci,

se va transmite codul Huffman pentru clasa 2, 110, urmat de o secven dedoi bii, 11, pentru a indica numrul coloanei n care se afl numrul 3 sauvaloarea din aceast clas care a fost codat, adic, se va transmite 11011.


55/69

55

Tabelul 10.9. Codarea diferenelor etichetelor DC

Clasa Codul Huffmancorespunz torclasei

0 0 0

1 -1 1 10

2 -3 -2 2 3 110

3 -7 . -4 4 . 7 1110

4 -15 . -8 8 . 15 11110

5 -31 . -16 16 . 31 1111106 -63 . -32 32 . 63 1111110

7 -127 . -64 64 . 127 11111110

8 -255 . -128 128 . 255 111111110

9 -511 . -256 256 . 511 1111111110

10 -1023 . -512 512 . 1023 11111111110

11 -2047 . -1024 1024 . 2047 111111111110

12 -4095 . -2048 2048 . 4095 1111111111110

13 -8191 . -4096 4096 . 8191 11111111111110

14 -16383 . -8192 8192 . 16383 111111111111110

15 -32767 . -16384 16384 . 32768 111111111111111

16 32768

Numrul cuvintelor de cod Huffman este egal cu logaritmul n baza doi alnumrului de valori posibile pe care le pot lua diferenele dintre etichete.Dac diferenele pot lua 4096 de valori posibile, lungimea codului Huffman

este 4096log2 =12, numr folosit de obicei n codare.


56/69

56

Codarea coeficien ilor ACOrdinea n care este parcurs matricea n vederea codificrii

coeficienilor de tip AC se alege n aa fel nct s se profite ct mai bine dedistribuia valorilor coeficienilor. Se urmrete gruparea valorilor nule niruri ct mai lungi, deoarece acest fapt permite o codare mai eficient (compresie maxim).

Deoarece valorile diferite de zero sunt concentrate ntr-un col almatricei, o parcurgere de tipul linie cu linie nu este eficient. De aceea se prefer o parcurgere n zig-zag, ordinea de extragere a elementelor din

matrice fiind prezentat n Fig. 10.12.

Figura 10.12. Parcurgerea n zig zag a matricei coeficienilor cuantizai

Pentru matricea coeficienilor din Tabelul 10.7 , coeficienii extrain aceast ordine sunt: 1, -9, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0. Se observ modul n care se grupeaz valorile nule ctre sfr itul irului. De acest fapt se vaine cont nurmtoarea etap, n care se realizeaz codarea acestor elemente. Fiecare

coeficient este un numr ntreg care poate varia, potrivit standardului JPEG,ntre -1023 i +1023 (valorile sunt obinute analiznd cazul cel maidefavorabili modul n care lucreaz transformata cosinus discret).


57/69


58/69

58

Z/i Cuv. de cod Z/i Cuv. de cod Z/i Cuv. de cod

0/0(EOB) 1010 F/0(ZRL) 111111110010/1 00 1/1 1100 F/1 11111111111101010/2 01 1/2 11011 F/2 11111111111101100/3 100 1/3 1111001 F/3 11111111111101110/4 1011 1/4 111110110 F/4 11111111111110000/5 11010 1/5 11111110110 F/5 1111111111111001

innd cont de aceste observaii, pentru coeficienii din Tabelul10.7, rezult urmtorul set de coduri care trebuie generate:

(0,1)(0,-9)(0,-3)(0,0,...0) = EOBDe exemplu, se dorete codificarea simbolului (0,1) dinirul de mai

sus. Prima valoare, 1, apar ine categoriei 1. Deoarece nu sunt zerouri care

s precead aceast valoare, se transmite codul Huffman corespunztor lui0/1, care, din Tabelul 10.10, este 00. Se concateneaz cu acest cod unsingur bit de 1 pentru a indica faptul c valoarea transmis este 1. Cuvntulde cod pentru perechea (0,1) este deci 001. Analog, -9 este alaseleaelement din clasa 4. De aceea se transmiteirul binar 1011, care este codulHuffman pentru 0/4, urmat de 0110, pentru a ar ta c -9 este cel de-alaselea element din clas. Urmtoarea valoare este 3, care apar ine clasei 2,deci se transmite codul Huffman 01, corespunztor lui 0/2, urmat de 11.Toate esantioanele dup acest punct sunt zero, astfel nct se transmite

codul Huffman EOB, care n acest caz este 1010.


59/69

59

Pentru exemplul considerat, datele sunt 11011 001 10110110 01111010, adic se folosete un numr de 24 de bii pentru reprezentarea blocului de dimensiune 8x8, adic o medie de 3/8 bii/pixel.

Se precizeaz c tabele prezentate pentru cuantizareai codareacoeficienilor DCi AC nu sunt singurele recomandate de standardul JPEG,acesta limitnd ns la 4, tabelele de coduri Huffman pentru codareacoeficienilor AC pentru luminan i crominan. Modul JPEG de baz folosete numai dou asemenea tabele.

Lanul de decodare JPEG este parcurs n ordine invers codrii.Astfel, imaginea compresat JPEG este supus n primul pas unui decodor entropic. Dup decodarea entropic, se aplic decuantizarea, folosindaceiai coeficieni care au fost folosii i la cuantizare, prezentai n Tabelele10.6 a,b. n urma decuantizrii se obin coeficienii transformatei cosinusdiscrete din Tabelul 10.11. Aceti coeficieni sunt trimii blocului detransformare cosinus discret invers, IDCT, care aplic transformarea dat de relaia 10.36. Acestora li se adun 128 i se obine blocul reconstruit prezentat n Tabelul 10.12. Calitatea acestei imagini depinde de numrul de

coeficieni pstrai la codare. Dac se vor pstra toi coeficienii nenuli,atunci imaginea reconstruit va fi foarte asemntoare cu originalul.

Tabelul 10.11. Valorile coeficienilor dup decuantizare

32 11 0 0 0 0 0 0-108 0 0 0 0 0 0 042 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0


60/69

60

0 0 0 0 0 0 0 0

Tabelul 10.12. Blocul reconstruit

123 122 122 121 120 120 119 119121 121 121 120 119 118 118 118121 121 120 119 119 118 117 117124 124 123 122 122 121 120 120130 130 129 129 128 128 128 127

141 141 140 140 139 138 138 137152 152 151 151 150 149 149 148159 159 158 157 157 156 155 155

Dei reducerea este substanial, de la 8 bii pe pixel la 3/8 bii pe pixel, reproducerea este remarcabil de apropiat de original.

Dac se dorete o reproducere cu acuratee mai mare, se poate faceacest lucru cu preul creterii ratei, micornd mrimea pasului decuantizare din tabelul de cuantizare. Acest lucru va determina o cretere anumrului de bii transmii. Similar, se poate scdea rata, prin creterea pasului de cuantizare, cu preul creterii distorsiunilor.

10.5.2. Modul de codare cu pierderi expandatExist trei diferene principale ntre modul de baz i cel expandat,

i anume:- Modul expandat poate folosi 8-12 bii;- Modul expandat poate folosi cai codare entropic att codarea

Huffman, cti codarea aritmetic;- Modul expandat poate folosi att codarea progresiv ct i cea

secvenial.


61/69

61

n multe dintre aplicaiile de compresie a imaginilor aparedezavantajul c, datorit rezoluiilor mari la care sunt reprezentateimaginile, timpul de codare, de transmisiei, respectiv, de decompresie estede ordinul minutelor. n astfel de aplicaii se poate aplica un algoritm decompresie progresiv, care iniial produce o imagine brut, dup care, prinscanri succesive, se mbuntete calitatea imaginii.

Dac se presupune c valoarea unui pixel este apropiat de cea avecinului su, se poate folosi valoarea pixelului nvecinat pentru a predictavaloarea pixelului de codat. Ideea este aceea de a ndeprta orice redundan

care poate exista. Diferena dintre valoarea actual i cea prezis este codat i transmis. Aceast diferen se numete eroare de predic ie sau reziduu .Receptorul folosete acelai pixel nvecinat pentru a face predicia pentruacel pixeli acelai algoritm de predicie cai emitorul. Din moment ce sefolosete acelai pixeli acelai algoritm pentru a face predicia, receptorular trebui s genereze aceeai valoare de predicie ca i emitorul. Aceast valoare, cnd este adugat la eroarea de predicie dat de emitor, ar trebuis conduc exact la pixelul original recuperat. Dac algoritmul folosit pentru predicie const n alegerea unei combinaii liniare a pixelilor

nvecinai, atunci aceast abordare se numete predic ie liniar . Pentru ca,att emitorul cti receptorul s foloseasc acelai pixel pentru generarea prediciei, trebuie s se impun o ordine a pixelilor. n general, se presupunec pixelii unei imagini sunt generai linie cu linie, de la stnga la dreapta,ide sus n jos. Acest procedeu se numete ordine de scanare de tip rastru.

De exemplu, se consider c " imaginea" din Fig. 10.13a esteimaginea original. Dac se folosete vecinul stng al fiecrui pixel ca predicie a acelui pixel, eroarea de predicie poate fi reprezentat ca oimagine rezidual, dup cum se arat n Fig. 10.13b.


62/69

62

4 8 4 8 1 1 1 11 2 4 6 5 1 1 18 4 5 5 5 5 5 52 4 8 5 7 9 5 52 4 6 7 7 7 9 92 2 2 3 4 9 7 33 3 6 6 6 6 7 77 7 7 7 6 7 7 7

(a) (b)Fig. 10.13. (a) Imaginea original i (b) eroarea ei de predicie

Se observ numrul mare de zerouri din imaginea rezidual. ntr-oimagine n care exist cu precdere acest tip de redundan sau structur ,adic pixeli vecini au valori apropiate una de alta, aceast abordare va ducela o imagine rezidual care const n principal din zerourii numere mici.Imaginea rezidual poate fi codificat n general cu mult mai puini biidect imaginea original. n acest exemplu se folosete vecinul din stnga pentru predicie. Dar se poate folosi, de asemenea, vecinul de sus sau ocombinaie avantajoas a lor. Schemele de predicie pentru pixelul curentcare se bazeaz pe vecini aflai pe direcii diferite sunt cunoscute subdenumirea de scheme de predicie bi-dimensionale. n ciuda simplitii lor,tehnicile de predicie liniar sunt eficiente, iar performanele lor suntsurprinztor de apropiate de performanele obinute cu ajutorul altor tehnicimai sofisticate.

Modul de compresie progresiv JPEG, se obine prin realizarea unuiset de subimaginii fiecare subimagine va fi codat cu un set specific decoeficieni DCT. n consecin, codorul DCT va trebui s aib un buffer ncare datele (coeficienii DCT ai subimaginilor) s fie memorate nainte decodarea entropic. n Fig. 10. 14 este prezentat modul de formare aimaginilor codate progresiv JPEG.

4 4 -4 4 -7 0 0 01 1 2 2 -1 -4 0 08 -4 1 0 0 0 0 02 2 4 -3 2 2 -4 02 2 2 1 0 0 2 02 0 0 1 1 5 -2 -43 0 3 0 0 0 1 07 0 0 0 -1 1 0 0


63/69

63

Compresia progresiv JPEG poate fi obinut folosind trei tipuri dealgoritmi:

- un algoritm progresiv de selecie spectral;- un algoritm progresiv de aproximri succesive;- un algoritm progresiv combinat.

a) b) c)Fig. 10.14. Compresia progresiv JPEG

Algoritmul progresiv de selec ie spectral grupeaz coeficieniiDCT n cteva benzi de frecven. De obicei, nti sunt transmiicoeficienii de joas frecven, dup care urmeaz coeficienii de nalt frecven. n Fig. 10.15 este prezentat un exemplu n care coeficienii DCTsunt mpr ii n patru benzi de frecven. n banda 1 se gsesc numaicoeficienii de curent continuu (DC), banda 2 cuprinde primii coeficieniAC, AC1, AC2, banda 3 conine coeficienii AC3, AC4, AC5, AC6, iar banda 4, coeficienii AC7,... , AC63.


64/69


65/69


66/69

66

10.5.3. Compresia secven ial JPEG f r pierderiStandardul JPEG permitei folosirea unui algoritm de compresie

f r pierderi, respectiv un algoritm de compresie predictiv n locultransformrii DCT. n Fig. 10.19 este prezentat schema bloc a unui codor JPEG f r pierderi. Blocurile de cuantizare neuniform din schema standardde compresie JPEG sunt nlocuite n cazul de fa cu un bloc de codare predictiv.

Fig. 10.19. Schema generalizat o codorului JPEG f r pierderi

Blocul predictor lucreaz astfel: se calculeaz o predicie aeantionului X' pe baza eantioanelor precedente A, Bi C, figurate ]n Fig.10.20, dup care se calculeaz diferena dintre eantionul original Xi cel prezis: DX=X-X'.

Fig. 10.20. Poziionarea eantioanelor pe baza crora se calculeaz predicia

Aceast diferen este codat entropic cu ajutorul unui codor Huffman. n Fig. 10.21 sunt prezentai paii parcur i n algoritmul decodare.


67/69

67

Fig. 10.21. Schema de codare cu pierderi JPEG

n Tabelul 10.13 sunt date cteva formule folosite n predicie.

Tabelul 10.13. Predictori folosii pentru compresia cu pierderi

Index formula de predicie0 f r predictor 1 X=A2 X=B

3 X=C4 X=A+B-C5 X=A+(B-C)/26 X=B+(A-C)/27 X=(A+B)/2

10.5.4. Compresia JPEG ierarhic Compresia ierarhic JPEG permite o reprezentare progresiv a

imaginii decodate, ntr-un mod similar cu algoritmul progresiv, dar, n plusfa de acesta, permite imagini codate cu rezoluii multiple. Se creeaz astfel, un set de imagini compresate, ncepnd cu imagini de rezoluie mic


68/69

68

i continund cu imagini a cror rezoluie crete ctre rezoluia imaginiioriginale. Acest proces se numete subeantionare sau codare piramidal. nFig. 10.22 este figurat un astfel de algoritm.

Fig. 10.22. Codare ierarhic JPEG

Dup procesul de subeantionare, fiecare imagine de joas rezoluie sescaleaz la imaginea cu rezoluie imediat superioar prin metoda invers,numit supraeantionare, fiind folosit ca predictor pentru urmtoarea etap.Algoritmul de compresie ierarhic const din urmtorii pai:

- filtrarea i subeantionarea imaginii originale cu factorul dorit(multiplu al lui 2), de-a lungul fiecrei dimensiuni (vertical,orizontal);

- codarea imaginii de rezoluie mic folosind tehnicile de codareDCT secvenial, DCT progresiv sau codarea f r pierderi;

- decodarea imaginii de rezoluie redus, interpolarea isupraeantionarea cu un factor de 2, pe direcia orizontal i/sauvertical, folosind un filtru de interpolare identic cu cel de ladecodor;


69/69

69

- folosirea imaginii supraeantionate ca predictor al imaginiioriginale, i codarea diferenelor dintre cele dou imagini,folosind una din tehnicile amintite;

- se repet algoritmul pn cnd se codeaz imaginea la rezoluiainiial.

Codarea ierarhic necesit o zon de memorie destul de mare pentrua putea implementa algoritmul, dar avantajele sunt acelea c imagineacodat este imediat disponibil la diferite rezoluii.

Compresie Imagini

Documents

Transcript of Compresie Imagini