Transmisia datelor multimedia in retele de calculatoare

Compresia Wavelet

Conf. Dr. Ing. Costin-Anton Boiangiu<Costin.Boiangiu@CS.PUB.RO>

UNIVERSITY POLITEHNICA of BUCHARESTDEPARTMENT OF COMPUTER SCIENCE

IntroducereCompresia imaginilor bazata pe transformari Wavelet

urmareste eliminarea:

Redundanţei spaţiale: În aproape toate imaginile naturale valorile pixelilor apropiaţi sunt identice sau uşor diferite

Redundanţei spectrale: În imaginile compuse din mai mult de o bandă spectrală valorile spectrale ale aceluiaşi pixel sunt deseori corelate

Redundanţei temporale: Cadrele adiacente într-o secvenţă video suferă mici modificări

2

Transformarea WaveletUna dintre metodele cele mai uzuale de efectua analiza a

unui semnal este descompunerea sa într-o sumă ponderată de funcţii numite funcţii bază ("basis functions"):

unde:c(i) sunt coeficienţi/ponderi ("weights“)b(i) sunt funcţii bază

3

Transformarea WaveletDin moment ce funcţiile bază sunt cunoscute problema se

reduce calculul coeficienţilor c(i)Pentru a simplifica abordarea vom presupune că toate

funcţiile b(i) sunt variante scalate şi translatate ale aceleiaşi funcţii b cunoscută sub numele de wavelet mamă ("mother wavelet")

Scalarea este realizată prin multiplicarea cu un factor de scală, în general ales ca fiind 2De aceea este aleasă forma de scalare în cascadă b(2u)

unde u este un număr întreg

4

Transformarea WaveletDeoarece b are un suport finit este necesară translaţia în

axa timpului pentru a acoperi întregul semnalTranslaţia este realizată prin shiftarea tuturor

componentelor lui b adică b(2u * x - k),unde k este un

număr întregDe fapt se realizează o translaţie cu 2-u

* k deoarece se poate scrie că:

5

Transformarea WaveletCumulând rezultatele rezultă o descompunere a lui f de

forma:

unde

Multiplicarea cu 2u/2 este necesară pentru a păstra bazele ortonormate

6

Compresia imaginilor staticePasii compresiei:

aplicarea unei transformări wavelet pentru a extrage caracteristicile de frecvenţă ale imaginii

cuantizarea datelor rezultatecodificarea valorilor rezultate din cuantizare

7

Implementarea Wavelet

8

Implementarea WaveletTransformarea directă wavelet ("Forward Wavelet Transform") poate

fi implementată eficient în O(n) prin utilizarea unei perechi de QMF ("Quadrature Mirror Filters“)

Fiecare QMF constă dintr-o dualitate de filtre care împart banda de frecvenţe a semnalului în două : H - filtru LPF("LowPass Filter") G - filtru HPF("HighPass Filter")

Răspunsurile digitale ale lui H şi G sunt "în oglindă" ("mirrored"):

Răspunsurile în impuls ale transformărilor directă şi inversă ale QMF-ului notate (Ĥ,Ĝ) respectiv (H, G) sunt date de relaţiile :

9

Exemplu – W6Wavelet-ul “mama”

10

Exemplu – W6Răspunsurile în impuls pentru H şi G; graficul reprezintă

magnitudinea semnalului în funcţie de frecvenţa normalizată

11

Implementarea WaveletUn semnal unidimensional poate fi filtrat prin convoluţia

coeficienţilor filtrului c(k) cu valorile semnalului:

unde M este numărul de coeficienţi ("taps") ai filtruluiTransformarea wavelet unidimensională directă a

semnalului s este realizată prin: convoluţia lui s atât cu Ĥ cât şi cu Ĝ aplicare "downsampling" cu 2

12

Implementarea WaveletRelaţia dintre coeficienţii filtrului Ĥ, Ĝ şi începutul semnalului s este:

De notat că filtrul Ĝ se extinde înaintea semnalului ca timp iar dacă semnalul este finit Ĥ se extinde dincolo de sfârşitul semnalului O situatie similară apare la calculul transformărilor inverse pentru filtrele H şi G

Într-o implementare reală utilizatorul va trebui să aleagă cu ce anume va completa semnalul; o practică bună este de a înlânţui semnalul după capete:

… s(n - 1) s(n) s0 s1 s2 … s(n - 1) s(n) s0 s1 …

creând în acest mod o extensie periodică a lui s

13

ExempluTransformarea 2D wavelet asupra unei imagini realizată prin aplicarea unei

succesiuni de transformări 1D separate

14

ExempluTransformarea 2D wavelet inversă asupra unei imagini; ee

deduce uşor aplicarea paşilor inverşi din transformarea directă

15

CuantizareaTransformarea wavelet directă decorelează valorile pixelilor

în imaginea initială şi concentrează informaţia imaginii într-un număr relativ mic de coeficienti

În general asupra coeficienţilor obtinuţi din transformarea wavelet se aplică o funcţie prag ("threshold") ce are rolul de a îmbunătăţi performanţele de compresie fără a distorsiona semnificativ imaginea

Codificarea coeficienţilor rezultaţi se face ulterior cu un algoritm de compresie fără pierderi preferăndu-se Huffman adaptiv cu fereastra glisantă de dimensiune 64K după aplicarea în prealabil a unei codificări RLE

16

CuantizareaHistograma valorilor pixelilor pentru

o imagine 8 BPP („Bits per pixel”) ("Lenna" 512x512) respectiv histograma coeficienţilor wavelet aceliaşi imagini după ce transformarea a fost aplicată

17

Rezultate experimentaleDouă tipuri de codificări:

FLC – Codificare de lungime fixă ("Fixed Length Coding") VLC – Codificare de lungime variabilă ("Variable Length

Coding") Codificări wavelet:

18

Rezultate experimentale

Se poate observa că performanţele codificării cu lungime variabilă sunt mai bune ca cele ale codificării cu lungime statică

19

Rezultate experimentale

20

Compresia videoCompresia video pe bază de transformări wavelet este

realizată prin aplicarea aceleiaşi tehnici din compresia imaginilor statice dar asupra diferenţelor (imaginii diferenţă) dintre două cadre succesive

Decompresia se realizează prin aplicarea transformării inverse wavelet şi însumarea cu imaginea iniţială

Nu există în momentul de faţă nici un format standard referitor la codificarea succesiunilor de imagini pe bază de wavelet-uri

21

Exemplu - compresie

22

Exemplu - decompresie

23