Prelucrarea și Analiza Imaginilor

Compresia imaginilor se refera la reducerea volumului de date (numarului de biti) cu

care este reprezentata imaginea, printr-o transformare reversibila - imaginea trebuie sa

poata sa fie recuperata integral (sau cu diferente foarte mici, controlabile) din versiunea

sa comprimata.

METODE DE COMPRESIE A IMAGINILOR

Termenul de compresie a imaginilor (uneori numit si codare a imaginilor) se refera la o clasa larga de tehnici si metode al caror scop este reprezentarea unui imagini date cu un numar cât mai mic de biti (mai mic decât numarul de biti al reprezentarii initiale). Necesitatea reducerii cantitatii de informatie necesara reprezentarii este evidenta daca consideram cazul memorarii imaginilor radiografice (4000 x 2500 pixeli, cu 4096 nivele de gri, deci 14,3 MB) sau al transmisiei de televizune alb-negru (625 x 625 pixeli cu 256 nivele de gri, de 50 de ori pe secunda, deci un flux de 18.6 MB secunda) [9]. Procesul de recompunere a imaginii initiale din reprezentarea restrânsa se numeste decompresie sau decodare; este evident ca prin decodare trebuie sa se obtina o imagine cât mai apropiat a de imaginea orginala. Exista doua categorii fundamentale de tehnici de compresie (codare) codarea fara pierderi (in care imaginea decodata este identica cu imaginea ini-tiala) si codarea cu pierderi, in care se admit mici diferente fata de original. Calitatea unui procedeu de compresie (pentru o imagine data) se masoara prin factorul de calitate (raportul semnal zgomot (3.4) dintre imaginea originala f si imaginea decodata g) si factorul (raportul) de compresie. Factorul de compresie C este raportul dintre cantitatea de informatie necesara reprezentarii imaginii initiale si cantitatea de informatie necesara reprezentarii imaginii codate; evident compresia are loc daca factorul de compresie este supraunitar (C 1). Uneori, factorului de compresie i se asociaza (sau este inlocuit de) rata de compresie cantitatea de informatie necesara reprezentarii comprimate a fiecarui pixel al imaginii; rata de compresie se masoara in biti per pixel (bpp).

O alta clasificare posibila a tehnicilor de compresie se poate face dupa tipul imaginii careia i se aplica vom face astfel distinctia intre compresia imaginilor binare si compresia imaginilor cu nivele de gri. Se impune totusi o observatie metodele de codare ce se vor prezenta in cadrul tehnicilor speifice imaginilor binare pot fi folosite pentru compresia oricarei succesiuni de valori binare, indiferent de semnificatia acestora (ceea ce inseamna ca ar putea fi folosite si pentru compresia imaginilor cu nivele de gri) si sunt metode de compresie fara pierderi.

Compresia imaginilor binare

Putem considera ca singura categorie de imagini binare de interes sunt imaginile in albnegru (sau monocrome); valorile punctelor acestora sunt fie 0 (reprezentând fundalul de culoare alba), fie 1 (reprezentând punctele de interes, de culoare neagra)1. Celedoua clase de metode de codare pe care le avem in vedere sunt codarea entropica (metoda de codare Huffman) si metodele de codare on-line (pe flux de biti); deosebirea dintre aceste metode (la un nivel al implementarii) este ca pentru codarea entropica este necesara parcurgerea si stocarea intermediara a intregii imagini.

Codarea entropica (Huffman)

Codarea entropica (Huffman) este metoda optimala de codare a unei surse de informatie. Codarea sursei de informatie S ale carei mesaje sunt {s1, s2, ..., sN}, de probabilitati {p(s1), p(s2), ..., p(sN)} prin alfabetul X cu D simboluri inseamna a asocia fiecarui mesaj si al sursei primare de informatie un sir de simboluri din alfabetul codului. Lungimea medie a cuvintelor de cod este data de raportul dintre entropia sursei primare si entropia alfabetului codului

l =

H(S)

H(X)

(7.1)

Se doreste obtinerea unei lungimi medii minime a cuvintelor de cod, si deci, echivalent, marirea entropiei alfabetului codului; la limita, lungimea media minima posibila de obtinut este

lmin =

H(S)

logD

(7.2)

Procedeul practic prin care se realizeaza alocarea simbolurilor din alfabetul codului astfel incât entropia acestuia sa fie maximizata (metoda Huffman) se bazeaza pe reducerea iterativa a numarului de simboluri ale sursei de codat si construirea unei surse restrânse. La fiecare etapa cele D simboluri cele mai putin probabile ale sursei de informatie sunt reunite intr-un nou simbol; procedeul de restrângere continua pâna când se obtine o sursa redusa cu exact D simboluri. Apoi, pentru fiecare reunire de simboluri, fiecare mesaj individual va primi codul cuvântului reunit ca prefix, urmat de câte un simbol din

alfabetul codului. Vom considera urmatorul exemplu. O sursa S genereaza 6 simboluri, de probabilitati descrise de vectorul P = [0.3; 0.25; 0.2; 0.1; 0.1; 0.05]. Sursa este codata optimal, simbol cu simbol, cu cuvinte de cod generate cu 1Deci conventia de reprezentare prin culori este modificata fata de conventia generala utilizata 0 nu mai este negru, ci alb.

Codarea optimala a unei surse se realizeaza conform algoritmului Huffman. Se stie ca numarul de simboluri ale sursei ce se codeaza trebuie sa indeplineasca o anume relatie ??N-D D-1 ? N??; in acest caz, N = 6, D = 3 si deci

N - D

D - 1

=

6 - 3

3 - 1

=

3

2

? N

Completarea se face adaugând sursei simboluri de probabilitate nula; in acest caz, cu un singur astfel de simbol adaugat obtinem N = 7 si

N - D

D - 1

=

7 - 3

3 - 1

=

4

2 ? N

Entropia sursei extinse S este data de

H(S) = -

7 ??i=1

p(si) log p(si) = - (0.3 log 0.3 + 0.25 log 0.25 + 0.2 log 0.2 + 2 ˇ 0.1 log 0.1) -

-0.05 log 0.05 - 0 log 0 = 2.366 bitsimbol

Atunci, conform (7.2), lungimea medie minima a unui cuvânt de cod este