generalitati despre compresia imaginilor 3-5 pagini 2 Transformarea wavelet exemple de transformate si scris cate ceva la ele 7-10 pagini… [628995]

1

2

3

1 Introducere :
generalitati despre compresia imaginilor 3-5 pagini
2 Transformarea wavelet
exemple de transformate si scris cate ceva la ele 7-10 pagini
avantaje/dezavantaje a folosirii transformatei wavelet 2 -3 pagini
3 Detaliem 2 metode si le c omparam intre ele pentru a arata care este mai buna si pe asta ne bazam si
restul lucrarii de licenta
4 rezultate cu imagini
5 concluzii

4
Introducere
Ce este o imagine digitală ?
Imaginea digitală este o suprafată dreptunghiulară formată din puncte, aranjate î n m rânduri
și n coloane. Fiecă rui punct al unei imagini digitale i se atribuie o anumită culoare. Expresia m x
n poartă denumirea de rezoluț ia ima ginii, iar punctele sunt num ite pixeli. Termenul de “rezoluție”
mai este folosit ș i pentru a indica numă rul de pixeli pe unitatea de lungime a imaginii. De exemplu,
pentru o imagine care are o rezoluție de 1920 x 1080 pixeli, înseamnă ca pe suprafaț a acest eia s-a
definit un caroiaj care o împarte pe orizontală în 1920 de secțiuni iar pe verticală î n 1080.

Evidentiere pixeli

O culoare se poate descompune î n trei culori primare (rosu -R, verde -G si albastru -B), adică orice
imagine se poate obține prin supr apunerea aditivă a trei radiaț ii luminoase avand aceste trei
culori primare cu intensităț i diferite.Pentru a reprezenta numer ic o culoare, este nevoie doar
să se reprezinte intensităț ile luminoase ale celor trei culori primare.

Formate de imagini
Există o mulțime de forme și mărimi de imagini, atât pentru imaginile tradiționale,
analogice, cât și pentru cele digitale. Cele mai întâlnite formate sunt cele dreptunghiulare, din
cauza formelor ecranelor de cinema, TV, monitoarelor și altele.

5

Formate de imagi ne standard
Vizualizarea imaginilor digitale
Există foarte multe programe cu ajutorul cărora o imagine digitală care a fost stocată pe
computer sau un alt spațiu de stocare extern poate fi vizibilă și pentru om. Astfel, imaginle de tipul
GIF, JPEG și PNG p ot fi prezentate pe un display cu ajutorul unui browse r web, acestea fiind cele
mai răspâ ndite fo rmate de codificare (standard) î n Internet. Formatul SVG a început să fie și el
utilizat mai frecvent, fiind un format standard al organizaț iei W3C.

6
Transformata wavelet
1.1Generalități
Wavelet -ul este un tip de funcție folosit pentru a împărți un semnal sau o funcție î n
componente diferite de timp -frecvență . Ac estea sunt studiate la o rezoluț ie specifică scalei
wavelet -ului. Transformata wavelet se referă la reprezentarea unei funcț ii cu ajutorul wavelet –
urilor.
Wavelet -urile sunt copii scalate si translatate ale unei unde oscilant e de lungime finită,
cunoscută ș i sub denumirea de wavelet mamă . Transformata wavelet, spre deosebire de
transformata Fo urier, ofera pos ibilitatea de a reprezenta funcții ce au discontinuități sau vârfuri
ascuț ite.
Un alt avantaj este reprezentat de faptul că are capaci tatea de a deconstrui ș i reconstrui
semnale neperiodice sau nesta ționare. Transformă rile wavelet pot fi c lasificate în transformă ri
wave let continue (CWT) si transformă ri wavelet discrete (DWT).

1.2 Definitii
Wavelet -ul este o funct ie 𝜓 ∈
2 (
) ce indeplinește următoarele proprietăț i:
• are media nulă ∫ 𝜓(𝑡)𝑑𝑡=0+∞
−∞ ;
• este normat ă||𝜓||=1;
• este centrată în vecină tatea: t = 0.

Functia Wavelet Daubechies

7
O familie de timp -frecvență este obținută prin scalarea lui 𝜓 cu s ¸si translatare ei cu u :
𝜓𝑢,𝑠(𝑡)=1
√𝑠𝜓(𝑡−𝑢
𝑠)
Aceste prelucrări păstrează norma:
𝜓𝑢,𝑠(𝑡)=1

Prelucrarea imaginilor cu a jutorul transformă rii wavelet
Tran sformata wavelet a funcț iei f ∈
2 (
) la momentul u ¸si scala s este:
𝑊 𝑓(𝑢,𝑠)=∫ 𝑓(𝑡)1
√𝑠𝜓∗(𝑡−𝑢
𝑠)𝑑𝑡 +∞
−∞

Filtrarea liniară
Transfo rmata wavelet poate fi rescrisă sub forma unui produs de convoluț ie:
𝑊 𝑓(𝑢,𝑠)=∫ 𝑓(𝑡)1
√𝑠𝜓∗(𝑡−𝑢
𝑠)𝑑𝑡 +∞
−∞
𝜓𝑠̅̅̅ (t)= 1
√𝑠𝜓∗(−𝑡
𝑠)
Transformata Fourier a lui 𝜓𝑠̅̅̅ (t) este:
𝜓𝑠̅̅̅ ̂(𝜔)=√𝑠𝜓∗̂(𝑠𝜔)
Din moment ce 𝜓̂(0)=∫ 𝜓(𝑡) 𝑑𝑡=0+∞
−∞ , se observă că 𝜓̂ reprezintă funcț ia de tra nsfer a unui
filtru trece bandă. Astfel convoluția calculează transformat a wavelet cu filtre trece bandă
dilatate.

8
1.3 Transformata Wavelet Reală
Fie 𝜓 un wavelet real . Pentru c ă media sa est e nulă , integrala wavelet
𝑊 𝑓(𝑢,𝑠)=∫ 𝑓(𝑡)1
√𝑠𝜓∗(𝑡−𝑢
𝑠)𝑑𝑡 +∞
−∞măsoară variaț ia lui 𝑓 în vecină tatea lui 𝑢, a cărei mărime
este proporțională cu 𝑠.
Transformare a reală wavelet este completă ș i conservă energia semnalului, atâta t imp câ t wavelet –
ul satisface o con diție slabă de admisibilitate specificată de teorema Calderon -Grossmann –
Morlet:
Teoremă : Fie 𝜓 ∈
2 (
) o funcț ie reală astfel încâ t:
𝐶𝜓=∫|𝜓̂(𝜔)|
𝜔+∞
0𝑑𝜔<+∞
Atunci orice 𝑓 ∈
2 (
) satisface:
Prelucrarea imaginilor cu ajutorul transformă rii wavelet
𝑓(𝑡)=1
𝐶𝜓̂∫ ∫ 𝑊𝑓(𝑢,𝑠)1
√𝑠𝜓(𝑡−𝑢
𝑠)𝑑𝑢𝑑𝑠
𝑠2+∞
−∞+∞
0 ¸si
∫ |𝑓(𝑡)|2𝑑𝑡=+∞
−∞1
𝐶𝜓̂∫ ∫ |𝑊𝑓 (𝑢,𝑠)|2𝑑𝑢𝑑𝑠
𝑠2+∞
−∞+∞
0 ¸

Ipoteza teore mei se numește condiț ia de admisibilita te wavelet. Pentru a garanta că aceasta
integrală este finită trebuie să ne asigurăm că 𝜓̂ (0) = 0, ceea ce explică condiția impusă la
început ș i anume ca toate wavelet -urile să aibă media nulă. Condiț ia est e aproap e
sufici entă. Dacă 𝜓̂ (0) = 0 ¸si 𝜓̂(𝑤) este continuă ș i derivabilă atunci condiț ia de
admisibilitate este satisfăcută .
Funcț ia de scalare.

9
Când 𝑊𝑓(𝑢,𝑠) este cunoscută doar pentru 𝑠<𝑠0, apare necesitatea unei informaț ii suplim entare,
pentru recuperarea lui 𝑓, corespunză toare lui 𝑊𝑓(𝑢,𝑠) pentru 𝑠>𝑠0. Aceasta informație este
obținută introducând o funcț ie de scalare 𝜑 reprezentâ nd o agregare a wavele t-urilor cu scala mai
mare decâ t 1.
Modulul transformatei Fourier a funcției de sca lare 𝜑 este:
|𝜑̂(𝜔)|2=∫|𝜓̂(𝑠𝑤)|2𝑑𝑠
𝑠+∞
1
Faza complexă a lui 𝜑̂(𝜔) poate fi aleasă arbitrar. Se poa te verifica faptul că ||𝜑||=1¸si se poate
evidenția din condiț ia de admis ibilitatea faptul că :
lim
𝜔→0|𝜑(𝜔)|2=𝐶𝜓
Astfel funcția de scală poate fi interpretată ca ră spunsul la impuls a unui filtru trece -jos.
𝜑𝑠(𝑡)=1
√𝑠𝜑̅(𝑡
𝑠);𝜑𝑠̅̅̅(𝑡)=𝜑𝑠∗(−𝑡)
Deci aproximarea pentru frecvenț e joase a lui f la scala s este:
𝐿𝑓(𝑢,𝑠)=𝑓×𝜑𝑠̅̅̅(𝑢)
Prelucrarea im aginilor cu ajutorul transformă rii wavelet 10 2.1.2
1.4 Transformata Wavelet Discretă (DWT)
Fie 𝑓̇(𝑡) un semnal continuu uniform eșantionat î n intervale de 𝑁−1ın [0, 1]. Transformata wavelet
a acestui semnal p oate fi calculată doar p entru scale 𝑁−1<𝑠<1. Pentru procesarea discretizată
este mai ușor de normalizat eșantioanele la o distanță de 1 și astfel se consideră semnalul dilatat
𝑓(𝑡)=𝑓(𝑁−1𝑡). Dacă se efectuează schimbarea de variabilă î n cadru l transformatei wavelet se
obține:
𝑊𝑓(𝑢,𝑠)=𝑁−12⁄𝑊𝑓(𝑁𝑢,𝑁𝑠)

10
Se notează 𝑓[𝑛]=𝑓(𝑛) semnalul discret de mă rime N . Transformata wavelet discretă asociată
semnalului se calculează la 𝑠=𝑎𝑗,cu 𝑎=𝑎1𝑣⁄ ce ofera 𝑣 scale int ermediare pentru fiecare octavă
[2𝑗,2𝑗+1].
Fie ψ (t) un wavelet cu suport î n intervalul [−𝑁2⁄;𝑁2⁄]
Pentru 2≤𝑎𝑗≥𝑁𝐾−1, un wavelet discret scalat cu a j este definit astfel:
𝜑𝑗[𝑛]=1
√𝑎𝑗𝜑(𝑛
𝑎𝑗).
Acest wavelet discret are 𝐾𝑎𝑗 valori nenule în –𝑁2⁄,𝑁2⁄. Scala 𝑎𝑗 trebuie să fie mai
mare decâ t 2, altfel intervalul de eș antionare ar putea fi mai mare decâ t suportul wavelet -ului.
O transformare wavele t calculată până la scala 𝑎𝐽 nu este o reprezentare completă a
semnalului. Astfe l este necesară adăugarea frecvenț elor 𝐿𝑓[𝑛,𝑎𝐽] joase corespunz ătoare scalelor
mai mari de 𝑎𝐽 . Un filtru de scalare discret și periodic este obținut prin eș antio narea funcț iei de
scalare 𝜑(𝑡) definită anterior.
𝜑𝐽[𝑛]=1
√𝑎𝐽𝜑(𝑛
𝑎𝐽) 𝑝𝑒𝑛𝑡𝑟𝑢 𝑛∈ [−22⁄,𝑁2⁄]

1.5 Transformata Haar
Informatiile care sunt in forma transformatei wavelet in situatii practice, cum ar fi sunet si imagini
digitalizate, sunt discrete, formate din numere individuale. Acesta este motivul pe ntru care
transformata wavelet discreta si nu transformata wavelet continua este folosita in practica.
Transformata Haar este un tip de transformata wavelet discreta, aceasta foloseste o functie de scala
φ(t) si un wavelet 𝜓(𝑡) ambele ilustrate in Figura 1.1, pentru a reprezenta un numar mare
de functii 𝑓(𝑡) si are formula
𝑓(𝑡)=∑ 𝑐𝑘𝜑(𝑡−𝑘)∞
𝑘=−∞+∑ ∑𝑑𝑗,𝑘 𝜓(2𝑗𝑡−𝑘)∞
𝑗=0∞
𝑘=−∞
Unde 𝑐𝑘 si 𝑑𝑗,𝑘 sunt coeficientii care trebuie calculati.

11
Funcția de scal ă de bază φ (t) este impulsul unității
𝜑(𝑡)={1, 0≤𝑡<1
0, 𝑖𝑛 𝑟𝑒𝑠𝑡

Figura 1.1
Funcț ia 𝜑(𝑡−𝑘) este o copie a 𝜑(𝑡), mutând 𝑘 unităț i spre dreapta. Similar, 𝜑(2𝑡−𝑘)
este o copie a fun cției 𝜑(𝑡−𝑘) scalată la jumătate din lăț imea 𝜑(𝑡−𝑘).
Copiile mutate sunt folosite pentru a aproxima 𝑓(𝑡) la diferiț i timpi 𝑡. Copiile scalate sunt
folosite pentru a aproxima 𝑓(𝑡) la rezoluții mai înalte. Î n Figura 1.2 ne este prezentată funcț ia
𝜑(2𝑗𝑡−𝑘) pentru 𝑗=0,1,2 𝑠𝑖 3 si 𝑘=0,1,….,7
Wav elet-ul de bază Haar este descris in funcț ia:
𝜓(𝑡)={ 1, 0≤𝑡<0.5
−1, 0.5≤𝑡<1

Figura 1.2

12
Din această formulă putem observa că wavlet -ul general Haar 𝜓(2𝑗𝑡−𝑘) este o copie a 𝜓(𝑡)
mutată 𝑘 unitati spre dreapta ș i o scală cu o lăț ime de 1/2𝑗
În fugura 1.3 sunt prezentate cele patru valori ale wavelet -ului Haar 𝜓(2𝑗𝑡−𝑘) 𝑘=0,1,2, si 3.

Figura 1.3
Ambele 𝜑(2𝑗𝑡−𝑘) si 𝜓(2𝑗𝑡−𝑘) sunt nonzero în intervalul de lăț ime 1/2𝑗. Acest int erval este
suportul lor. Fiindcă intervalul tinde să fie scurt, putem spune că aceste funcț ii au un suport
compact.

Figura 1.4 Imagine originală

13

Figura 1.5 Imagine descompusă pe 1 scală de rezoluț ie

Figura 1.6 imagine descompusă pe 2 scale de rezoluț ie

14
1.6 Dezavantaje ale transformării wavelet
Oscilaț iile
Ținând cont de fap tul ca wavelet -urile sunt funcții cu filtre trece -bandă, coeficienț ii wavelet
și în special coeficienții funcț iei prelucrate cu ajutorul transformatei wavele t tind să oscileze
pozitiv și ne gativ în jurul singularităților. Aceasta reprezintă o problemă care complică
considerabil procesarea cu ajutorul wavelet -urilor, ceea ce face ca extracția singularităților și, î n
particular, modelarea semnalului să devină o provocare.
Invarianța translaț iilor
Trebuie precizat că o translație (oricât de mică ) a semnalului poate perturba considerabil
tiparul de oscilație al coeficienților wavelet în jurul singularităț ilor. De asemenea, trebuie să se țină
cont de faptul că variația la translație complică ș i procesarea domeniului wavelet.
Astfel, algoritmii trebuie să fie proiectați pentru a putea face fată unei game largi de
posibile tipare pentru coeficienți i wavelet cauzate de sin gularităț ile translatate.
Aliasing
Din distanțarea largă a eșantioanelor coe ficienț ilor wavelet și din faptul că acești coeficienți
wavelet sunt calculați prin operații recurente de subeșantionare discretă combinate cu filtr e trece
sus și trece jos neideale, rezultă un alias substanț ial.
DWT -ul invers anulează desigur alias -ul, dar numai în cazul în care coeficienții wavelet și
de scalare nu sunt schimbați. Orice coeficienț i wavelet (threshold, filtrare si cuantifi care) răstoarnă
balanț a dintre transformata directă ș i transformata inversă, acestea ducând la artefacte în
reconstrui rea semnalului.
Lipsa orientă rii
În timp ce sinusoidele Fourier din dimensiunile mai mari corespund undelor înalte
orientate, produsul tensor standard pentru construirea wavelet -urilor produce un efect de
checkboard care este direcționat simultan în mai multe direcț ii. Aceast a proprietate de lipsa a
selecției orientării complică modelarea ș i procesarea t răsăturilor imaginil or geometrice precum
muchiile și graniț ele.

15
2.1 Transformarea cosinus discreta
Transformarea cosinus a fost introdusa de Ahmed (N. Ah med, T. Natarajan and K. R. Rao,
“On Image Processing and a Discrete Cosine Transform,” IEEE Trans. Computers, C -23, 1,
January 1974, 90 –93) si are largi aplicatii in codificarea si compresia imaginilor (standardul JPEG
pentru poze si MPEG pentru video).
Teoria Fourier specifica faptul ca orice semnal periodic poate fi reprezentat ca o suma
infinita de unde sinusoidale simle cu frecvente si amplitudini variabile. Se va considera semnalul
corespunzator unei linii de pixeli dintr -o imagine, deci un semnal un idimensional, pentru care :

𝑓(𝑥)=∑𝑎𝑛 cos (𝑛𝜔𝑥)∞
𝑛=0
f(x) este o functie periodica pe domeniul spatial, unde ω=2πf, f fiind frecventa
fundamentala a undei. Pe masura ce n varieaza, sunt considerate componentele de frecventa, an
este amplitudi nea componentei a n-a de frecventa.
Transformările cosinus și sinus discrete, (DCT, DST) aparțin familiei transformărilor
trigonometrice cu aplicații în compresia/decompresia datelor. Dintre acestea, DCT este de departe
mai folosită în practică, datorită p roprietății de compactare a energiei.

2.2 DCT unidimensională
În practică se folosește DCT bi -dimensională, dar pentru ușurința înțelegerii se consideră
mai întâi DCT uni -dimensională.
Se consideră formele de undă 𝑤(𝑓)=cos (𝑓𝜃), pentru 0<𝜃<𝜋, cu f recvențele
𝑓=0,1,…,7 , și 𝜃=𝜋
16,3𝜋
16,5𝜋
16,7𝜋
16,9𝜋
16,11𝜋
16,13𝜋
16,15𝜋
16
Fiecare formă de undă 𝑤(𝑓)este eșantionată în opt puncte, pentru a forma un vector al
bazei 𝒗𝑓.

16
Cei opt vectori rezulta ți 𝒗𝑓 ,𝑓=0,1,…,7 (un total de 64 de numere) sunt prezent ați în Tabelul
2.1. Aceștia reprezintă baza pentru DCT uni -dimensională.
Se observă similaritatea dintre acest tabel și matricea ordogona lă W .

Tabelul 2.1

Acești opt vectori 𝒗𝑖 sunt ortonormali (datorită alegerii particulare a celor opt puncte de
eșantionare) și pot fi organizați într -o matrice de transformare 8×8. Pentru că această matrice este
ortonormală, ea este o matrice de rotație, deci, DCT uni -dimensională poate fi interpre tă ca o
rotație în opt dimensiuni.
O altă interpretare a DCT uni -dimensională este aceea că se pot considera cei opt vectori
ortonormali 𝒗𝑖 ca bază a unui spațiu vectorial, și orice alt vector p poate fi exprimat în acest spațiu
ca o combinație lini ară a acestor vi.
De exemplu, se aleg ca date de test 8 numere corelate, p=(0,6; 0,5; 0,4; 0,5; 0,6; 0,5; 0,4;
0,55). Se exprimăm vectorul p ca o combinație liniară a celor opt vectori ai bazei, 𝒑=∑𝑤𝑖 𝒗𝑖.

17
Rezolvând acest sistem de opt ecua ții se obțin cele opt ponderi:

Ponderea 𝑤0 nu este cu mult diferită de elementele vectorului p, dar celelalte șapte ponderi
sunt mult mai mici. Acest fapt indică modul în care DCT (sau orice altă transformare ortogonal ă)
produce compresie.
Cele 8 ponderi vor reprezenta pur și simplu elementele compresate ale vectorului p.
Cuantizând cele opt ponderi, se poate crește considerabil compresia, în timp ce se pierde doar o
cantitate mică de date.
Figura 2.1 ilustrează grafic această combinație liniară . Fiecare din cei opt vectori 𝒗𝑖 este
prezentat ca un rând de opt dreptunghiuri mici, gri, unde o valoare de +1 este colorată în alb, și -1
în negru. Fiecare din ce le opt elemente ale vectorului p este exprimat ca suma ponder ată a unei
scări de gri cu opt nivele.

Figura 2.1

18
2.3 DCT bi -dimensională
Din experiență se știe că pixelii unei imagini sunt corelați pe două dimensiuni, nu doar pe
una (un pixel este corelat cu vecinii săi de la stânga și de la dreapta, deasupra și dedes ubt). De
aceea metodele de compresie a imaginii folosesc DCT bi -dimensională, dată de relația
(2.1)

pentru 0 ≤ i, j ≤ n -1. Imaginea este împărțită în blocuri de n×n pixeli x ,y,p (de obicei se folosește
n=8), și ecuația (2.1 ) este folosită pentru a obține un bloc de 8×8 coeficienți DCT, 𝐺𝑖𝑗, pentru
fiecare bloc de pixeli.
Dacă compresia este cu pierdere de informație, coeficienții sunt cuantizați. Decodorul
reconstruiește un bloc de valori de date (aproximate sau precise) prin calculul IDCT.

unde
𝐶𝑓={1
√2, 𝑓=0,
1, 𝑓>0, 𝑝𝑒𝑛𝑡𝑟𝑢 𝑓=0,1,…,7
DCT bi -dimensională poate fi interpretată în două moduri diferite, ca o rotație (de fapt, două rotații
separate), și c a bază a unui spațiu vectorial 𝑛-dimension al. În prima interpre tare se consideră un
bloc de 𝒏×𝒏 pixeli. Mai întâi se consideră fiecare rând al acestui bloc ca un
punct (𝑝𝑥,0;𝑝𝑥,1;….;𝑝𝑥,𝑛−1) în spaț iul 𝑛-dimensional, și se rotește punctul cu ajutorul
transformării date de suma din interior

19

a ecuației (2.1 ). Aceasta transformare are ca rezultat un bloc 𝐺1𝑥𝑗 de 𝒏×𝒏 coeficienți, unde
primul element al fiecărui rând este dominant și restul elementelor sunt mici. S uma exterioară a
ecuației (2.1 ) este

Aici, coloanele lui 𝐺1𝑥𝑗 sunt considerate puncte în spațiul n -dimensional, și sunt rotite.
Rezultatul este un coeficient mare în colțul stânga -sus al blocului și n 𝑛2−1 coeficienți mici în
rest. Această interpretare consideră DCT bidimensional ca două rotații separate, fiecare în
𝒏 dimensiuni.
Este interesant de observat că două rotații în 𝑛 dimensiuni sunt mai rapide decât una în 𝒏𝟐
dimensiuni, deoarece în al doilea caz este necesară o matrice de rotație de dimensiune 𝒏𝟐×𝒏𝟐
A două interpretare (presupunând 𝑛 = 8) folosește ecuația ( 2.1) pentru a crea 64 blocuri de
8×8 valori fiecare. Cele 64 de blocuri sunt apoi folosite ca bază a unui spațiu de vectori 64 –
dimensionali (sunt imagini de bază).
Imaginile de bază folosite în DCT bi -dimensională sunt date în Fig. 2.2 . Orice bloc 𝐵 de
8×8 pixeli poate fi exprimat ca o combinație liniară a imaginilor de bază, și cele 64 de ponderi ale
acestei combinații liniare sunt coeficienții DCT ai bloculu i 𝐵.

20

Figura 2.2. Imaginile de bază pentru transformata discretă cosinus bi -dimensională
În con tinuare, se prezintă rezultatele aplicării transformatei DCT bidimensionale la a două
blocuri de 8×8 valori. Primul bl oc, cu valorile din Tabelul 2,2 , are valori întregi puternic corelate
în intervalul [8,12] și cel de -al doilea, valori aleatoare în acela și interval. Primul bloc conduce la
un coeficient DC mare, urmat de coeficienți AC mici (incluzând 20 de zerouri).
Coeficienții celui de -al doile a bloc, pre zentați în Tabelul 2 .3, includ doar un zero.

Tabel 2.2 DCT bi -dimensională a unui bloc de valor i corelate

21

Tabel 2 .3
Compresia unei imagini cu DCT presupune parcurgerea următorilor pași:
 Se împarte imaginea în k blocuri Bi , i=1,2,…,k, de 𝑛×𝑛 (obișnuit, 8×8) pixeli fiecare.
 Se aplică DCT bi -dimensională fiecărui bloc Bi. Aceasta transformare exprimă blocul ca
o combinație liniară a celor 64 de imagini de bază din Fig. 2.2. Rezultatul este un bloc,
numit vector W( )i de 64 de ponderi ( )i wj , unde j=0, 1, …,.63.
 Cei k vectori 𝑾(𝑖) (i=1, 2,…., k) sunt împărțiți în 64 de vectori de coe ficienți 𝑪(𝑖), unde
cele k elemente ale vectorului 𝑪(𝑗) sunt(𝑤𝑗(1),𝑤𝑗(2),…,𝑤𝑗(𝑘)). Primul vector de coeficienți
𝑪(0) este format din cei k coeficienți DC.
 Fiecare vector de coeficienți 𝑪(𝑗) este cuantizat separat pent ru a produce un vector
cuantizat 𝑸(𝑗) , care reprezintă datele compresate. Decodorul citește cei 64 de vectori de
coeficienți cuantizați 𝑸(𝑗), îi folosește pentru a construi k vectori de ponderi 𝑾(𝑖) , și aplică
IDCT fiecărui vector de ponde ri, pentru a reconstrui cei 64 de pixeli ai blocului 𝐵𝑖.

22
Pentru o i magine de test este furnizat ă reprezentarea grafică a transformă rii cosinus:

Figura 2.3 Imagine originala

Figura 2.4 Imagine descompus ă

23
Originea se regăsește în colțul stâ nga sus. Energia imaginii tinde să se concentreze spre frecventele
spațiale mai mici.
Transformarea cosinus a unei imagini nxn se poate calcul a prin reflectarea imaginii după
granițele sale pentru a obț ine un tablou 2nx2n , calcularea transformării Fourier si preluarea parților
reale ale transformă rii Fourier.

Transformarea sinus discreta
Tran sformarea sinus a fost introdusă de Jain (A. K. Jain, “A Fast Karhunen –Loeve
Transform for Finite Discrete Images,” Proc. National Electronics Conference, Chicago, October
1974, 323 –328) ca un su bstitut algoritmic rapid pentru transformarea Karhunen -Loeve a unui
proces Markov. Pe ntru o singura dimensiune, funcț ia de baza este:
1)1 )(1(sin12),(
Nu x
NxuA

pentru u,x = 0, 1, 2, … , N -1
Transformarea sinus bidimensională este data de relaț ia









 1)1 )(1(sin1)1 )(1(sin],[12],[1
01
0 Nv y
Nu xyxfNvuFN
xN
y 

Transformarea sinus inversă este identică ca formă :









 1)1 )(1(sin1)1 )(1(sin],[12],[1
01
0 Nv y
Nu xvuFNyxfN
uN
v 

24
Pentru o imagine de test este furnizata re prezentarea grafica a transformă rii sinus:

Figura 2.5 Imagine originala

Figura 2.6 Imagine descompus ă

25
De asemenea transf ormarea sinus poate fi calculată din transformarea Fourier sau dir ect
utilizând ecuațiile de definiț ie.
Pentru a justifica folosirea mult mai frecventă a DCT în defavoarea DST, în continuare se
prezintă diferențele dintre funcțiile sinus și cosinus și de ce aceste diferențe duc la o transformare
sinus discretă ineficientă. Funcția sinus este o funcție impară, iar funcția cosinus, pară.
Deși singura diferență dintre cele două funcții este faza (adică funcția cosinus este o
versiune defazată a sinusului), această diferență este su ficientă pentru a le inversa paritatea.
Pentru a înțelege diferența dintre DCT și DST se examinează cazul uni -dimensional. DCT
uni-dimensională, dată de ecuația (10.27), folosește funcția cos((2t+1)fπ/16) pentru f=0, 1…. 7.
Pentru primul termen, unde f =0, această funcție devine cos(0), care este 1. Acest termen
este coeficientul DC, care produce media celor opt valori de date supuse transformării.
DST este bazată în mod similar pe funcția sin((2t+1)fπ/16), având ca rezultat un prim
termen nul (din mom ent ce sin(0)=0), care nu contribuie cu nimic la transformare, deci DST nu
are un coeficient DC.
Dezavantajul acestui lucru poate fi observat când se consideră exemplul a opt valori de
date identice ce trebuie transformate. Astfel de valori sunt, desigur, perfect corelate. Când sunt
reprezentate grafic ele devin o linie orizontală.
Aplicând DCT acestor valori, se produce doar un coeficient DC; toți coeficienții AC fiind
nuli. DCT compactează toată energia datelor într -un unic coeficient DC, a cărui valoar e este
identică cu a datelor. IDCT poate reconstrui exact cele opt valori (cu excepția unor modificări
minore date de precizia limitată de calcul).
Aplicarea DST asupra acelorași opt valori, pe de altă parte, conduce la șapte coeficienți
AC a căror sumă e ste o formă de undă care trece prin cele opt puncte corespunzătoare datelor, dar
oscilează între aceste puncte.

26

Acest comportament, are trei dezavantaje, în principal:
1. Energia datelor originale nu este compactată;
2. Cei șapte coeficienți nu sunt decorelați (pe când datele sunt perfect corelate);
3. Cuantizând cei șapte coeficienți se poate ajunge la o puternică scădere a calității reconstrucției
realizate de DST inversă.

3 Metode și abordă ri ale compresiei imaginii
Există mai multe metode folosit e pentru a comprima o imagine.
1 Cuantizarea scalară este folosită pentru a compresa imagini, dar dezavantajul ei este
reprezentată de faptul că performanțele ei sunt mediocre. De exemplu, o imagine cu 8 biți/pixel
poate fi compresată prin cuantizare scala ră eliminând cei mai nesimnificativi patru biți ai ficărui
pixel. Acest lucru duce la o rată de compresie de 0,5 fiind aproape neexistentă, dar în același timp
și reducerea numărului de culori de la 256 la 16.
2 Cunatizarea vectorială are un succes mult m ai bun pentru a compresa imagini.
3 Metodele statice au o eficiență bună când simbolurile care trebuie compresate au
probabilități diferite. O secvență de intrare în care mesajele au aceeași probabilitate nu se va
compresa eficient.

27

3.1Compresia SPIH T
Transformata Haar este una simplă, iar o compresie mai bună poate fi obținută cu ajutorul
unui alt filtru wavelet. S -a observat faptul că diferite filtre wavelet produc diferite rezultate,
depinzând de tipul imaginii, dar nu este limpede ce fel de filtru trebuie folosit pentru o imagine
dată.
Indiferent de particularitațile filtrului utilizat, imaginea este descompusă în subbande,
astfel subbandele inferioare corespuns frecvențelor mari ale imaginii ( ele sunt highpass level) iar
subbandele superioare co respund frecvențelor mici ale imaginii (lowpass level), iar marea parte a
energiei imaginii este concentrată, acest lucru ne este exemplificat in figura 3.1 .

Figura 3.1

28
SPIHT a fost creat pentru transmisia progresivă optimă, cât și pentru compresie. Un a din
cele mai importate caracteristici ale SPIHT (poate chiar una unică) este aceea că în orice clipă pe
durata decodării unei imagini, calitatea imaginii obținute este cea mai bună calitate care se poate
obține pentru numărul de biți impuși de decodor în acel moment.

O altă caracteristică importantă a SPIHT este faptul că folosește o codare incorporată.
Această caracteristică este definită astfel : dacă un encoder produce două fișiere, unul mai mare de
mărimea M și unul mai mic de mărimea m, atunci fișier ul mai mic este identic cu primii m biți al
fișierului mare.
Următorul exemplu ilustrează în mod adecvat sensul acestei definiții. Daca trei persoane
asteaptă să le trimit o imagine compresată,dar ei au nevoie ca imaginea compresată să fie la calitați
diferite.
Prima persoană are nevoie de o imagine care are dimensiunea de 10Kb, a doua persoană
de o imagine cu dimensiunea de 20 Kb iar a treia persoană de o imagine care are dimensiunea de
50 Kb.Cele mai multe metode de compresie a imaginilor cu pierderi ar trebui să compreseze
aceeași imagine de trei ori, la calitați diferite, pentru a genera trei fișiere de dimensiuni dorite.
SPIHT, pe de altă parte, creează un singur fișier, și apoi trei bucăți de lungimi 10 Kb, 20 Kb, si
50Kb, toate pornind de la începutu l fișierului, putând fi transmise la cele trei persoane, satisfăcând
astfel toate nevoile.
3.2 Compresia EZW
Metoda SPIHT este un fel extensie a metodei EZW, aceasta metoda avand numele
embedded coding using zerotrees of wavelet coefficients. Metoda EZW, imple mentata in practica,
incepe prin efectuarea 9-tap filtru cu oglinda simetrica cu cuadratura (QMF). B ucla principală este
apoi repetată pentru valorile pragului care sunt reduse la jumătate la sfârșitul fiecare iterație .
Pragul este utilizat pentru a calcu la o hartă de semnificații semnificativă și nesemnificativ ă
a coeficienților wavelet. Arbori i zero sunt folosiți pentru a rep rezenta harta semnificației într -un
mod eficient.

29

Figura 3.2 Arborii zero

30
4 Implementare a aplicației
4.1 Algoritmul
Codul fol osit a fost in programul MATLAB, am folosit acest program deoarece este us or
de implementat . Prima imagine de test folosită (Mask) se poate găsi în librăria MATLAB, iar a
doua (Lena) a fost descărcată.

X=imread(‘ nume imagine’)
image(X)
axis square
colormap(pink(255))
title(Ima: mask')
Inseram imaginea care va urma sa fie comprimata, putem alege sa introducem manual
calea directa sau daca am importat calea, putem doar introduce numele imaginii. Numarul de linii
si numarul de coloane a imaginii trebuie sa fie o putere a lui 2.
meth = ‘numele metodei’ ;
option = 'c'; # numele compresiei folosite
[CR,BPP] = wcompress(option,X,' numele imaginii ',meth,'BPP',0.5)
O masurare a rezultatului o reprezinta calitatea ratei de compresie (CR) si numarul de biti
pe pixel ( Bit-Per-Pixel BPP).
Valoarea procentuala CR ne indica faptul ca imaginea comprimata este stocata folosind
CR% din dimensiunea de stocare initiala, pe cand BPP reprezinta numarul de biti folositi pentru
stocarea unui pixel din imagine. Pentru o imagine alb -negru, valoarea initiala a BPP -ului este 8,
pe cand pentru o imagine color valoarea initiala a BPP -ului este de 24, deoarece 8 biti sunt folositi
pentru codarea fiecarei culori primare.

31
Scopul metodelor de compresie este de a gasi cel mai bun compromis in tre o valoare cat
mai mica a ratei de compresie si un rezultat perceptiv bun.

meth = ‘numele metodei’ ;
wname = 'haar'; % numele Wavelet -ului
nbloop = 6; % numarul de bucle
[CR,BPP] = wcompress('c',X,'mask.wtc',meth,'maxloop', nbloop, …
'wname','haar');
Xc = wcompress('u', nume imagine ');
colormap(pink(255))
subplot(1,2,1); image(X);
axis square;
title('Original Image')
subplot(1,2,2); image(Xc);
axis square;
title(‘Imagine comp rimata – 6 bucle )
xlabel({['Compression Ratio : ' num2str(CR,'%1.2f %%')], …
['BPP: ' num2str(BPP,'%3.2f')]})
# Acum ilustrăm utilizarea metodelor progresive de compresie, începând cu algoritmul EZW
folosind wavelet -ul Haar. Parametrul cheie este numărul de bucle; creșterea duce la o mai bun ă
recuperare, dar un raport de compresie mai rău.
[CR,BPP] = wcompress('c',X,'mask',meth,'maxloop',9,'wname','haar');
Xc = wcompress('u','mask');

32
figure
colormap(pink(255))
subplot(1,2,1); image(Xc);
axis square;
title('Imagine comprimata – 9 bucle')
xlabe l({['Compression Ratio: ' num2str(CR,'%1.2f %%')],…
['BPP: ' num2str(BPP,'%3.2f')]})
[CR,BPP] = wcompress('c',X,'mask',meth,'maxloop',12,'wname','haar');
Xc = wcompress('u','mask');
colormap(pink(255))
subplot(1,2,2); image(Xc);
axis square;
title('Imagine comprimata – 12 bucle')
xlabel({['Compression Ratio: ' num2str(CR,'%1.2f %%')],
['BPP: ' num2str(BPP,'%3.2f')]}
[CR,BPP] = wcompress('c', X,'mask','ezw','maxloop',11,
'wname','haar');
Xc = wcompress('u','mask') ;
figure;
colormap(pink(255))
subplot(1,2,1); image(Xc);
axis square;
title('Imagine comprimata – 11 bucle')

33
xlabel({['Compression Ratio : ' num2str(CR,'%1.2f %%')],
['BPP: ' num2str(BPP,'%3.2f')]})

[CR,BPP] = wcompress('c', X,'mask','ezw','maxlo op',12,
'wname','haar');
Xc = wcompress('u','mask');
subplot(1,2,2); image(Xc);
axis square;
title('Imagine comprimata – 12 bucle')
xlabel({['Compression Ratio : ' num2str(CR,'%1.2f %%')],
['BPP: ' num2str(BPP,'%3.2f')]})

[CR,BPP] = wcompress('c',X,'mask','spiht',' maxloop',12,
'wname','bior4.4');
Xc = wcompress('u','mask');
figure;
colormap(pink(255))
subplot(1,2,1); image(X);
axis square;
title('Imagine originala')
subplot(1,2,2); image(Xc);
axis squar e;
title('Imagine comprimata SPIHT – 12 bucle')

34
xlabel({['Compression Ratio : ' num2str(CR,'%1.2f %%')],
['BPP: ' num2str(BPP,'%3.2f')]})
[CR,BPP] = wcompress('c',X,'mask','ezw','maxloop',11,
'wname','bior4.4');
Xc = wcomp ress('u','mask');
figure;
colormap(pink(255))
subplot(1,2,1); image(Xc);
axis square;
title('Imagine comprimata – 11 bucle bior4.4')
xlabel({['Compression Ratio: ' num2str(CR,'%1.2f %%')], …
['BPP: ' num2str(BPP,'%3.2f')]})
[CR,BPP] = wcompress ('c',X,'mask','ezw','maxloop',12, …
'wname','bior4.4');
Xc = wcompress('u','mask');
subplot(1,2,2); image(Xc);
axis square;
title('Imagine comprimata – 12 bucle bior4.4')
xlabel({['Compression Ratio: ' num2str(CR,'%1.2f %%')], …
['BPP: ' num2st r(BPP,'%3.2f')]})
[CR,BPP] = wcompress('c',X,'mask','spiht','maxloop',11, …
'wname','bior4.4');
Xc = wcompress('u','mask');

35
figure;
colormap(pink(255))
subplot(1,2,1); image(Xc);
axis square;
title('Imagine comprimata SPIHT – 11 bucle bior4.4')
xlabel({['Compression Ratio: ' num2str(CR,'%1.2f %%')], …
['BPP: ' num2str(BPP,'%3.2f')]})

[CR,BPP] = wcompress('c',X,'mask','spiht','maxloop',12, …
'wname','bior4.4');
Xc = wcompress ('u','mask');
subplot(1,2,2); image(Xc);
axis square;
title('Imagine comprimata SPIHT – 12 bucle bior4.4')
xlabel({['Compression Ratio: ' num2str(CR,'%1.2f %%')], …
['BPP: ' num2str(BPP,'%3.2f')]})

36
4.2Rezultate
Se poate observa o rata de compresie foarte buna, dar din pacate ca si rezultat avem o
imagine decomprimata foarte grosiera.

Figura 4.1 Imagine originală

37

4.2 Imagine compresata 6 bucle

Se va mă ri numarul de bucle la 9, 11, respectiv 12, pentru a putea vedea daca putem obtine
o calitate mai buna a imaginii la o rata de compresie cat mai buna si u n numar de BPP cat mai
mic.

38

Figura 4.3 Imagine compresată -9 bucle

Figura 4.4 Imagine compresată -11 bucle

39

Figura 4.5 Imagine compresată -12 bucle

Figura 4.6 Imagine originală

40

Dupa 12 bucle putem spune ca am obtinut reultate foarte bune cu ajutorul transformarii Haar.
Diferentele sunt in schimb destul de mari intre 11 bucle si 12 bucle.

Tabel ul 4.1
In continuare vom folosi wa velet -ul bior 4.4 la un numar de bucle de 11 ,respectiv 12 bucle, acesta
fiind mult mai eficient in compresia imaginilor. Wavelet Metoda de
compresie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Haar EZW 6 bucle 0.23 0.02 1576 16.16
Haar EZW 9 bucle 1.96 0.16 190.6 25.33
Haar EZW 11 bucle 6.88 0.55 28.35 33.61
Haar EZW 12 bucle 11.56 0.92 10.87 37.77

41

Figura 4.7 Imagine compresată -11 bucle bior4.4

Figura 4.8 Imagine compresată -12 bucle bior4.4

42

Wavelet Metoda de
compresie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Bior4.4 EZW 11 4.43 0.35 23.51 34.42
Bior4.4 EZW 12 7.83 0.63 8.42 38.88
Tabel ul 4.2
Se observa fap tul ca nu doar rata de compresie a scazut , cat si numarul de biti -per-pixel.
Folosind o metoda de compresie mult mai recenta ,SPIHT, valoarea BPP se poate imbunatati si
mai mult.

Figura 4. 9 Imagine compresată SPIHT -11 bucle bior4.4

43

Figura 4. 10 Imagine compresată SPIHT -12 bucle bior4.4

Wavelet Metoda de
compr esie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Bior4.4 SPIHT 11 1.57 0.12 79.8 29.11
Bior4.4 SPIHT 12 2.86 0.23 33.66 32.86
Tabel ul 4.3

44
Folosind acelasi cod putem compare rezultatele si la o imagine color .

Figura 4. 11 Imagine originală si imagine compresată 6 bucle
La fel ca in cazul imaginilor alb -negru dupa 6 bucle re zultatul este nesatisfacator.

Figura 4. 12 Imagine compresata 9 bucle si imagine compresată 12 bucle

45

Figura 4. 13 Imagine compresata 11 bucle si imagine compresată 12 bucle

Figura 4. 14 Imagine compresata 11 bucle bior 4.4 si imagine compresată 12 bucle bior 4.4

46

Figura 4. 15 Imagine compresata SPIHT 11 și imagine compresată SPIHT 12 bucle

Figura 4. 16 Imagine originală și imagine compresată SPIHT 12 bucle

47
Tabel ul 4.4
Tabel ul 4.5
Tabel ul 4.6

Wavelet Metoda de
compresie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Haar EZW 6 bucle 0.10 0.02 1248 17.17
Haar EZW 9 bucle 1.44 0.35 283.9 23.6
Haar EZW 11 bucle 8.42 2.02 55.91 30.36
Haar EZW 12 bucle 16.93 4.6 21.19 34.87
Wavelet Metoda de
compresie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Bior4.4 EZW 11 6.64 1.59 51.5 31.01
Bior4.4 EZW 12 13.49 3.24 18.64 35.43
Wavelet Metoda de
compre sie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Bior4.4 SPIHT 11 4.52 1.09 68.36 29.78
Bior4.4 SPIHT 12 8.88 2.13 27.91 33.67

48
Din Tabelele 4.1, 4.2, și 4.3 exemplificând cele mai bune valori, obtinem tabelul 4 .7

Wavelet Metoda de
compresie Numar de
bucle Rata de
compresie
(%) Biti-per-
Pixel MSE
(%) PSNR
(db)
Haar EZW 12 11.56 0.92 10.87 37.77
Bior4.4 EZW 12 7.83 0.63 8.42 38.88
Bior4.4 SPIHT 12 2.86 0.23 33.66 32.86
Tabel ul 4.7

Concluzii
În această lucrare se urmărește implementarea mai multor tehnici wa velet de compresi e a
imaginilor, zerotree încorporat pe bază de wavelet (EZW – wavelet -based embedded zeroree) și
partiționarea mulț imilor în arbori ierarhici (SPIHT) , folosind transformata Haar respectiv
transformata Bior. Pentru implementarea acestor tehnici am folosit M ATLAB R2018b.

49
Cu ajutorul acestor implementări am putut mă sura eficacitatea metodelor menț ionate.
Dintre algoritmii JPEG, compresia imaginilor bazată pe metoda wavelet furnizează rezultate
semnificativ mai bune, ea fiind o metodă cu adevărat eficientă pe ntru compresia imaginilor.
Cu ajutorul acestor algoritmi, am identificat o serie de param etri pentru măsurarea
performanț elor, precum PSNR, CR, BPP și MSE.
Prin calcularea acestor param etri putem compara metodele menț ionate.

Cu ajutorul transfomatei Ha ar si a metodei de compresie EZW