Compresia Imaginilor Binare

Aceasta lucrare isi propune a fi o introducere in metodele de compresie a imaginilor binare. De aceea tratarea subiectului nu se pretinde a fi exhaustiva. Se urmareste familiarizarea studentilor cu diversele procedee de codare exacta dezvoltate pina in prezent. Vor fi luate in considerare trei metode de codare exacta a imaginilor binare: (a) White Block Skipping (WBS), (b) Run Length Coding (RLC) si (c) Block Coding (BC). Prima metoda, WBS, va fi analizata din punctul de vedere al factorului de compresie si al modelului de Lant Markov asociat. A doua metoda, RLC, va cuprinde analiza atit a Codarii Lungimii Sirurilor Independent de Culoare cit si Codarea Lungimii Sirurilor Functie de Culoare. Si in cazul RLC va fi dezvoltat modelul Lantului Markov asociat. Pentru a treia metoda va fi calculat factorul de compresie maxim, corespunzator unei codari absolut optimale, iar apoi va fi implementat codul Huffman asociat statisticii preluate dintr-o imagine si din mai multe imagini. Cele trei metode studiate vor fi apoi comparate din punctul de vedere al factorului de compresie. In final se vor face considerente asupra altor metode de codare a imaginilor binare si asupra standardelor existente.

1. Introducere

A comprima un mesaj inseamna a pastra numai acei parametri care sint esentiali pentru destinatar. Ceilalti parametri nu se transmit, respectiv nu se stocheaza.

Sistemele de compresie pot fi grupate in doua categorii:

- sisteme care utilizeaza procedee care conserva entropia sursei, dar reduc redundanta ( codare exacta).

- sisteme care utilizeaza procedee care reduc entropia sursei ( o parte din informatie se pierde).

In cele ce urmeaza va fi tratata doar codarea exacta, deci la receptor, prin decodare va putea fi reprodusa exact sursa initiala.

Conform primei teoreme a lui Shanon [1], printr-o codare corespunzatoare, sursa de entropie H poate fi transformata intr-o sursa de entropie maxima HMAX ( sau aproape de maximum), respectiv se efectueaza o operatie de reducere a redundantei. Simbolurile sursei de entropie maxima, respectiv de redundanta zero, sint codate in cuvinte de lungime medie minima si in consecinta eficienta transmisiunii este maxima, iar stocarea lor se poate face in memorii de capacitate mai mica decit in absenta codarii.

Imaginile binare sint semnale discrete, bidimensionale, cu suport finit care pot lua doar doua valori ( negru = "0" si alb = "1" ). Aceste imagini se intilnesc in practica sub forma de pagini tiparite, scrisori, documente, ziare, harti geografice, harti meteorologice, fise cu amprente etc. Ca urmare transmisia si stocarea unor astfel de imagini este intilnita astazi in diverse domenii de activitate incepind cu uzuala, de acum, transmisie prin fax si terminind cu bazele de date de amprente utilizate in criminalistica. Datorinta volumului mare de memorie pe care il necesita o imagine binara ( un format standard de scrisoare de 8.5 x 11 inch esantionat la 200 puncte/inch contine aprox. 3,7 Mbiti ) apar avatajoase diversele metode de compresie, care reduc timpul de transmisie, largimea de banda necesara transminiei si necesarul de capacitate de stocare.

Compresia exacta este posibila datorita redundantei existente in imaginile binare. Astfel se constata existenta unei corelatii bibimensionale puternice intre elementele (pixeli) alaturate ale imaginii.Unele imagini binare sint caracterizate de zone intinse de nivel "1" (alb). De aici apare ideea utilizata de WBS [2], adica "sarirea blocurilor de alb".

Tehnica RLC [2], [3] exploateaza eficient corelatia orizontala a elemetelor imaginii prin gruparea lor in siruri negre si siruri albe, rezultind deci "codarea lungimii sirurilor".

Metoda BC [3] exploateaza in plus si corelatia verticala a elementelor imaginii prin gruparea acestora in blocuri, de unde denumirea de "codarea pe bloc".

Factorul de compresie obtinut printr-un procedeu de codare care reduce redundanta sursei este definit astfel:

Q = NO / NC (1)

unde:

NO este numarul total de biti din imaginea originala

NC este numarul total de biti din aceasi imagine dupa codare.

Notind cu "b" rata de bit, adica numarul mediu de biti pe pixel dupa codare, atunci, factorul de compresie poate fi definit si in functie de rata de bit:

Q = 1 / b (2)

Relatiile (1) si (2) aplicate asupra aceleiasi imagini si aceluiasi procedeu de codare, conduc la acelasi rezultat numeric.

Limita superioara a factorului de compresie este:

QMAX = 1 / H (3)

unde H este entropia sursei de semnal, care poate fi evaluata apriori doar aproximativ, utilizind un model matematic al sursei.

In cele ce urmeaza imaginile vor fi presupuse de dimensiune n x n.