Tehnici de Compresie a Imaginilor

Capitolul 1.

Prezentarea problemei compresiei de imagini

1.1 Fundamente

1.1.1 Reprezentarea imaginii

1.1.2 Cuantificarea imaginii

1.1.3 Modelarea matematică a imaginii

1.1.4 Introducere în problema compresiei de date

Tipuri de redundanță

1.1.5.1 Redundanța în codificare

1.1.5.2 Redundanța spatială .

1.1.5.3 Redundanța psihovizuală

1.1.6 Criterii de fidelitate

1.2. Modelarea procesului de compresie de imagini

1.3. Elemente de teoria informației

1.3.1 Măsurarea informației

1.3.2 Canalul de informații

1.4. Teoreme fundamentale de codificare

1.4.1 Teorema de codificare fără erori

1.4.2 Teorema de codificare de canal

1.4.3 Teorema de codificare a sursei

1.4.4 A1.5 Compresia fără erori

Aplicații

1.5 Compresia fără erori

1.5.1 Codificarea în lungime variabilă

1.5.1.1 Codificarea Huffman

1.5.1.2 Alte coduri de lungime variabilă utilizate

1.5.2 Codificarea aritmetică

1.5.3 Codificarea în planuri de biți

1.5.4 Codificarea imaginilor binare

1.5.4.1 Codificarea regiunilor constante

1.5.4.2 Codificarea dinamică unidimensională

1.5.4.2 Codificarea dinamică bidimensională

1.5.5 Codificarea predictivă fără pierderi

1.6 Comprimarea cu pierderi

1.6.1 Codificarea predictivă cu pierderi

1.6.2 Codificarea transformatei

29 pagini

=== Capitolul 1 ===

Capitolul 1.

Prezentarea problemei compresiei de imagini

1.1 Fundamente

1.1.1 Reprezentarea imaginii

Termenul de imagine monocromă ( imagine simplă ) se referă la o funcție de intensitate a luminii, bidimensională, notată f(x,y), unde x și y reprezintă coordonatele spațiale, iar valoarea lui f în fiecare punct (x,y) este proporțională cu luminozitatea ( strălucirea) imaginii în punctul respectiv și se numește nivel de gri (l) al pixelului (x,y). Evident, există 2 valori Lmin și Lmax astfel încât Lmin l Lmax. Intervalul [Lmin, Lmax] se numește scară de gri. În aplicațiile practice acestui interval i se asociază un alt interval [0,L], unde l = 0 corespunde valorii de negru, iar l=L este considerat alb. Valorile intermediare sunt nuanțe de gri ce variază continuu de la negru la alb. Pentru a o adapta procesării computerizate, o funcție de imagine f(x,y) va fi adusă în format digital, atât la nivel spațial cât și în amplitudine. Să presupunem că o imagine continuă f(x,y) este aproximată de o selecție uniformă echidistantă reprezentată sub forma unei matrici NM:

Membrul drept al relației de mai sus reprezintă ceea ce poartă în mod obișnuit numele de imagine digitală. Fiecare element al matricei referă un element de imagine sau pixel.

Procesul de selecție poate fi privit ca o partiționare a planului x0y în mai multe secțiuni, coordonatele centrului fiecărei secțiuni fiind o pereche de elemente ale produsului cartezian ZZ. Așadar, f(x,y) este o imagine digitală dacă (x,y) sunt întregi din ZZ, iar f este o funcție ce asociază câte o valoare de nuanță fiecărei pereche de coordonate (x,y).

Functia de imagine digitala poate fi privita ca o aplicatie f:{0,…,M-1}x{0,…,N-1}{0,…,L-1}. Multimea {0,…,L-1} este multimea nivelurilor de gri, iar M si N reprezinta dimensiunile imaginii digitale.

1.1.2 Cuantificarea imaginii

În procesul de cuantificare, spațiul în care sunt plasate valorile selecției se împart în intervale, toate valorile situate într-un interval fiind reprezentate printr-un singur nivel de cuantificare. În general se utilizează intervale de lungimi egale. De exemplu, unui punct din intervalul [zk, zk+1) i se asociază nivelul de gri qk.

Deși nivelele de cuantificare se iau de regulă cu lungimi egale, câteodată aplicarea cuantificării neuniforme este mai eficientă, dacă există diferențe semnificative între frecvența

de apariție a diferitelor niveluri de gri. Aplicarea unei cuantificări mai fine în astfel de spații ameliorează (optimizează) calitatea imaginii.

În cele ce urmează, vom prezenta o metodă de determinare a nivelurilor optime de cuantificare [Max60]:

Fie nivelurile de cuantificare q1, q2,…, qL și funcția histogramă h(z), care definește numărul de pixeli caracterizați de nivelul de gri z. Se definește eroarea medie pătratică de cuantificare astfel:

Pentru optimizarea calității imaginii alegem (q1,…,qL) și (z1, …,zL,zL+1) astfel încât să minimizeze E. Considerăm următorul sistem de ecuații:

care conduce la:

Ne interesează, în vederea cuantificării optime, cum selectăm zk și qk astfel încât să respecte relațiile de mai sus. Se poate utiliza următorul algoritm iterativ: selectăm un oarecare q1, după care determinăm z2 din relația (1.1.5) și q2 din relația (1.1.4),….până la qL. Dacă zL+1 nu coincide cu valoarea maximă permisă, modificăm q1 și reluăm procesul de iterație.

Cuantificarea optimă

Pe baza celor afirmate anterior, cuantificarea optimă este data de( [Max60]):

Pe baza relațiilor de mai sus, utilizând o tehnică iterativă, se obține o mulțime de praguri de cuantificare x1, x2,…xN+1.

1.1.3 Modelarea matematică a imaginii

Modelul matematic considerat a fi cel mai eficient în problema compresiei de imagini este modelul câmpului Gauss-Markov. Considerăm o imagine plasată într-un câmp Gauss-Markov discret omogen bidimensional [DELP79a]:

unde

Cele două condiții menționate mai sus afirmă că u(j,k) este un câmp Gauss independent de medie 0, iar termenul din relația (1.1.6) se numește coeficient de regresie.

Un caz special al modelului de câmp Gauss-Markov se obține pentru a=b=1 și se numește câmp Gauss-Markov de ordinul întâi.

f(j,k) = 1 f(j-1, k)+2 f(j-1,k-1)+3 f(j,k-1)+u(j,k) (1.1.7)

Relația de mai sus marchează faptul că nivelul de gri al pixelului (j,k) este determinat de valorile pixelilor săi vecini (j-1,k), (j-1,k-1) și (j,k-1). Gradul de dependență a nivelurilor de gri este descris de coeficienții .

1.1.4 Introducere în problema compresiei de date

Noțiunea de compresie de date se referă la căutarea unei soluții pentru problema reducerii cantității de date utilizate în reprezentarea unui anume volum de informații ( ce caracterizează o imagine digitală, în cazul de față). Se impune așadar o distincție clară între noțiunile de dată și informație. Datele reprezintă mijlocul prin care sunt transmise informațiile ce urmează a fi prelucrate și interpretate în scopul integrării lor într-un context mai larg. Pentru a reprezenta același volum de informații putem folosi cantități diferite de date. Se întâmplă de multe ori ca aceste date să refere și o serie de informații irelevante sau deja cunoscute, situație definită ca fiind o redundanță în date.

Redundanța este un concept abstract, însă cuantificabil din punct de vedere matematic. Notând cu n1 si n2 numărul de unități de informație conținute respectiv în două mulțimi de date ce reprezintă aceeași informație, se definește redundanța relativă de date (notată RD) a primei mulțimi prin următoarea relație:

unde s-a notat prin CR rata de comprimare, definită de CR = n1 / n2.

Tipuri de redundanță

În procesul de compresie de imagini au putut fi identificate și exploatate 3 tipuri principale de redundanță în date: – redundanța în codificare

redundanța spațială ( între pixeli )

redundanța psihovizuală

Se obține o compresie a datelor atunci când una sau mai multe din aceste redundanțe sunt reduse sau eliminate.

1.1.5.1 Redundanța în codificare

Să considerăm variabilele discrete rk [0,1], k=0,1,…,L-1 reprezentând nuanțele de gri ale unei imagini. Presupunem că fiecare nuanță rk apare cu probabilitatea p(rk), determinată de relația:

p(rk) = nk / n ,

unde L = nr de nuanțe

nk = nr de apariții ale nuanței k în imagine

n = nr total de pixeli.

Dacă fiecare valoare a lui rk se reprezintă printr-o secvență de cod de l(rk) biți, atunci lungimea medie a secvenței de cod necesară pentru reprezentarea fiecărui pixel este:

(1.1.8)

Prin urmare, numărul total de biți necesari pentru a codifica o imagine MN este MNLavg.

În cazul în care nuanțele unei imagini sunt codificate într-un fel ce utilizează mai multe simboluri decât ar fi fost absolut necesar pentru a reprezenta fiecare nuanță ( altfel spus, dacă alegerea codului nu minimizează ecuația (1.1.8) ), spunem că imaginea conține redundanță în codificare. Acest tip de redundanță apare în principal atunci când codurile asociate setului de evenimente n-au fost selectate optim în funcție de probabilitatea sau frecvența de apariție a evenimentului. În multe aplicații, compresia de date se obține asociind cele mai scurte coduri nuanțelor celor mai frecvente dintr-o imagine. Această metodă este cunoscută sub denumirea de codificare de lungime variabilă.

1.1.5.2 Redundanța spatială .

Operația de codificare nu modifică nivelul de corelație dintre pixelii unei imagini, corelațiile fiind rezultat al relațiilor structurale sau geometrice existente între obiectele imaginii.

Există o formă de redundanță în date determinată direct de legăturile dintre pixeli. Întrucât valoarea fiecărui pixel particular poate fi dedusă relativ ușor pe baza valorilor vecinilor săi, informațiile deținute de pixelii individuali este relativ mică. Prin urmare cea mai mare parte din contribuția vizuală a fiecărui pixel în parte este redundanta.

Pentru a reduce aceste redundanțe se impune transformarea șirului bidimensional de pixeli ulilizat pentru vizualizare și interpretare într-un format mai eficient (în general nonvizual). De exemplu, pot fi utilizate diferențele dintre pixelii adiacenți. Acest tip de transformări poartă numele de mapări și se numesc reversibile în cazul în care elementele imaginii originale pot fi reconstruite din mulțimea de date rezultate în urma transformării.

1.1.5.3 Redundanța psihovizuală

Ochiul nu prezintă o sensibilitate egală pentru toate informațiile vizuale din cadru, motiv pentru care unele informații prezintă o importanță mai mare decat altele în procesarea de imagini. Informațiile nesemnificative din acest punct de vedere se numesc redundante psihovizual și pot fi eliminate fără a diminua calitatea percepției.

Acest tip de redundanță nu ar trebui să constituie o surpriză, întrucât percepția umană a informațiilor vizuale nu implică analiza cantitativă a fiecarui pixel și a luminozității sale. În general, un observator distinge clar regiunile marginale și pe cele de conținut (structurale), pentru a le combina apoi mental în grupuri (categorii) de recunoaștere. Creierul corelează aceste categorii cu informațiile dobândite anterior cu scopul de a completa procesul de interpretare a imaginii.

Întrucât eliminarea datelor redundante psihovizual conduce la o pierdere cantitativă de informații, procesul a fost numit cuantificare. Se poate observa că, spre deosebire de operațiile menționate anterior, cuantificarea este o operație ireversibilă.

1.1.6 Criterii de fidelitate

Performanța unui sistem de compresie cu pierderi de informație este asigurată de fidelitatea imaginii. Prin urmare este necesară găsirea unui mijloc de evaluare a naturii și a întinderii pierderilor de informații Ca bază pentru o astfel de apreciere se utilizează două categorii generale de criterii:

– criterii de fidelitate obiectivă

– criterii de fidelitate subiectivă

Avem de-a face cu un criteriu de fidelitate obiectivă atunci când nivelul pierderilor de informații poate fi exprimat printr-o funcție ce depinde de parametrii imaginii inițiale și ai celei ulterior comprimată. Un astfel de criteriu este eroarea medie pătratică dintre o imagine de intrare și una de ieșire. Notând:

f funcția imaginii de intrare

o estimare a funcției f obținută în urma comprimării și eventualei decomprimări a imaginii de intrare,

pentru orice x și y din domeniul funcției definim eroarea dintre f (x, y) și astfel:

(1.1.9)

Dacă dimensiunea imaginii inițiale este MN , eroarea totalã dintre cele două imagini va fi :

Se definește eroarea medie pătratică dintre cele două imagini ( erms ) astfel:

(1.1.3)

Un alt criteriu de fidelitate obiectivă este dat de rata medie pătratică de claritate a semnalului imaginii comprimate-decomprimate ( notată SNRrms ), definit astfel:

(1.1.4)

Deși criteriile de fidelitate obiectivă menționate sunt ușor de calculat, nu reflectă întotdeauna calitatea vizuală a unei imagini. Acest lucru se datorează particularităților vizuale ale ochiului uman. De aceea se impune considerarea unui criteriu de fidelitate subiectivă, obținut din media evaluărilor unui număr corespunzător de observatori. Evaluările se pot face utilizând o scară ierarhică de evaluare sau prin comparări succesive ale valorilor funcțiilor f și

1.2. Modelarea procesului de compresie de imagini

Un sistem de comprimare constă în două blocuri structural distincte : un codificator și un decodor. O imagine de intrare f este preluată de codificator și transformată într-un set de simboluri. Este transmisă apoi prin intermediul unui canal decodorului, care urmează să reconstruiască imaginea de ieșire .

În general, poate fi sau nu o replică exactă a lui f. Dacă este, sistemul se numește liber de erori sau cu conservare de informații. În caz contrar, în imaginea refăcută va fi prezent un anumit nivel de distorsie.

Atât codificatorul cât și decodorul se compun din două subblocuri relativ independente. Codificatorul este compus dintr-un codificator de sursă, ce înlătură redundanțele datelor de intrare și un codificator de canal, ce protejează claritatea semnalului transmis de codificatorul de sursă, în condițiile în care transmiterea se face cu pierderi. În mod analog, decodorul include un decodificator de canal, urmat de un decodificator de sursă.

f

Fig 1.1 : Reprezentarea unui sistem general de compresie a imaginii.

În situația în care informația este transmisă de la codificator la decodor fără erori, nu mai este necesară prezența componentei de canal a codificatorului/decodificatorului .

Codificatorul de sursă realizează reducerea sau eliminarea redundanțelor de codificare, spațiale sau psihovizuale ale unei imagini de intrare. Aplicațiile specifice și cererile de fidelitate asociate determină alegerea celei mai bune metode de codificare pentru fiecare situație dată. Orice procedeu de codificare conține în principal trei operații independente, fiecare dintre ele realizând reducerea uneia din cele trei tipuri de redundanță descrise anterior.

f Canal (a)

Canal (b)

Fig.1.2: Schema unui codificator de sursa (a) si a unui decodificator de sursa (b).

Într-o primă fază a procesului de codificare, mapper-ul conferă datelor de intrare un nou format (în general nonvizual), în scopul de a reduce redundanțele spațiale ale imaginii de intrare. Această operație este în general reversibilă și poate sau nu să reducă direct cantitatea de date utilizate pentru a reprezenta imaginea.

A doua fază, realizată prin intermediul unui cuantificator, reduce precizia rezultatului oferit de mapper, în funcție de câteva criterii prestabilite de fidelitate. Acest stadiu elimină redundanțele psihovizuale ale imaginii inițiale. Operația este ireversibilă, putând fi omisă dacă se dorește o compresie fără erori.

În cea de-a treia și ultima fază a procesului de codificare, codificatorul de simboluri creează un cod de lungime fixă sau variabilă pentru a reprezenta rezultatul operației anterioare. Cel mai adesea se utilizează codul de lungime variabilă. El asociază cel mai scurt cuvânt de cod valorii cu cea mai frecventă apariție, reducând în felul acesta redundanțele de codificare. Această operație este reversibilă. După încheierea pasului de codificare în simboluri, considerăm că imaginea a fost procesată pentru a îndepărta cele trei tipuri de redundanță.

Nu este obligatoriu ca toate cele trei faze să fie prezente în structura unui sistem de comprimare. Să ne amintim, de exemplu, că sistemele fără pierderi de informații omit faza a doua. Pe de alta parte, există tehnici de comprimare care conțin blocuri combinate, ce realizează simultan mai multe operații.

Decodificatorul de sursă conține doar două componente: un decodificator de simboluri și un mapper invers. Aceste blocuri realizează, în ordine inversă, operațiile codificatorului de simboluri și mapper-ului.

Codificatorul / decodificatorul de canal. Aceste două componente au un rol important atunci când canalul de comunicare este predispus la erori. Ele sunt introduse pentru a elimina impactul erorilor de transmitere prin adăugarea unei forme controlate de redundanță în datele codificatorului de sursă.

1.3. Elemente de teoria informației

Întrucât comprimarea urmărește reducerea volumului de date utilizat în reprezentarea unei imagini, apare în mod firesc întrebarea: există o cantitate minimă de date suficientă pentru a descrie complet o imagine fără pierderi de informație? Teoria informației asigură cadrul matematic pentru a răspunde unor astfel de întrebări.

1.3.1 Măsurarea informației

Premiza fundamentală în teoria informației este că procesul de generare a informațiilor poate fi modelat probabilistic, putând fi măsurat într-o manieră intuitivă. În acord cu această supoziție, un eveniment aleator E a cărui probabilitate de apariție este P(E) va conține

l(E) = log ( 1/ P(E) ) = – log P(E) (1.3.1)

unități de informație. l(E) se numește informația internă a evenimentului E.

Baza logaritmului din relația (1.3.1) determină unitățile de măsură a informației. Dacă se folosește baza r, spunem că măsurarea se face în unități r-are. Dacă alegem baza 2, unitatea de informație se numește bit.

Dacă P(E) = ½ atunci l (E) = – log2 ½ = 1 bit.

1.3.2 Canalul de informații

Un canal de informații este mediul fizic prin intermediul căruia se realizează transferul de informații de la sursă la utilizator. Figura de mai jos reprezintă un model matematic simplu al unui sistem informațional:

Perechea (A, z) Q = {qkj} Perechea (B, v)

A = {ai } B = {bk }

z = [ P(a1), P(a2),…, P(aj)] T v = [ P(b1), P(b2),…, P(bk)] T

Fig 1.3 Reprezentarea unui sistem informațional

Parametrul de interes este capacitatea sistemului, definită ca fiind eficiența transmiterii informației. Presupunem că sursa generează o secvență de simboluri dintr-o mulțime finită sau numărabilă de caractere posibile. Mulțimea de simboluri A = {a1, a2,…,aJ} definește alfabetul sursei. Notând cu P(ai) probabilitatea ca sursa să transmită simbolul ai , rezultă în mod evident .

Observație: Perechea (A,z), unde z = [ P(a1), P(a2),…, P(aj)] T descrie complet sursa de informații.

Conform relației (1.3.1), informația internă generată de transmiterea unui singur simbol de către sursă este l(ai) = – log P(ai). Dacă se generează k simboluri, legea numerelor mari demonstrează că, pentru valori mari ale lui k, simbolul ai va apărea în medie de k P(ai) ori. Prin urmare, informația internă medie obținută din k ieșiri este:

Informația medie furnizată de o singură ieșire a sursei va fi:

(1.3.2)

și se numește incertitudinea sau entropia sursei. Cu cât valoarea ei crește, cu atât există mai multă incertitudine și sursa furnizează mai multe informații. Dacă simbolurile sursei sunt echiprobabile, entropia se maximizează și sursa asigură cea mai bună informație medie pe simbol.

Vom defini în continuare funcția de transfer a canalului de informații. Informația transferată ieșirii canalului este o valoare aleatoare discretă ce ia valori într-o mulțime finită sau numărabilă de simboluri B = {b1, b2,…,bk}, ce poartă numele de alfabetul canalului. Probabilitatea ca simbolul bk să apară în informațiile furnizate utilizatorului este P(bk). Perechea finită (B,v), unde v = [ P(b1), P(b2),…, P(bk)] T descrie complet ieșirea canalului, deci și informația recepționată de utilizator.

Relația dintre probabilitatea unei anumite ieșiri de canal și distribuția de probabilitate a sursei z este descrisă prin expresia:

(1.3.3)

unde P(bk / ai) este probabilitatea condiționată de recepționare a simbolului bk atunci când a fost generat de către sursă simbolul ai. Dacă probabilitățile condiționate referite de relația (1.3.3) se scriu în formă matriceala, astfel încât:

(1.3.4)

atunci distribuția de probabilitate a întregului alfabet de ieșire se poate calcula din

v = Qz (1.3.5)

Matricea Q poartă numele de matrice de canal.

Pentru a determina capacitatea unui canal de informații prin intermediul matricei Q, va trebui calculată în primul rând entropia sursei de informații în ipoteza că receptorul de informații observă o ieșire particulară bk. Relația (1.3.3) definește o distribuție a simbolurilor emise de sursă pentru fiecare ieșire observată bk, deci fiecare bk este caracterizat de o funcție de entropie condițională. Această funcție, notată H(z / bk), se scrie în felul următor:

(1.3.6)

unde P( ai / bk) este probabilitatea ca simbolul ai să fi fost transmis de sursă în condițiile în care a fost recepționat simbolul bk. Valoarea medie a acestei expresii este:

(1.3.7)

Din relațiile (1.3.6) și (1.3.7), după o eventuală rearanjare a termenilor, rezultă:

(1.3.8)

unde P(ai , bk) este probabilitatea ca ai să fie transmis și bk recepționat.

Termenul H(z/v) poartă numele de ambiguitatea lui z în raport cu v și reprezintă informația medie furnizată de un simbol-sursă, în condițiile observării simbolului de ieșire rezultat în urma generării sale. Definim informația mutuală dintre z și v, notată prin I(z,v) astfel:

I(z,v) = H(z) – H(z/v) (1.3.9)

Pe baza relațiilor (1.3.2) și (1.3.8), cum P(aj) = P(aj, b1) + P(aj, b2) +…+ P(aj, bk) rezultă:

(1.3.10)

care, după câteva transformări, se poate scrie:

(1.3.11)

Se observă că valoarea minimă pe care o poate lua I(z,v) este 0 și se obține atunci când simbolurile de intrare, respectiv de ieșire sunt statistic independente (adică atunci când P(aj, bk) = P(aj) P(bk) ). Capacitatea canalului descris de matricea Q se definește prin

(1.3.12)

și reprezintă coeficientul maxim de fiabilitate cu care este transmisă informația prin canal.

1.4. Teoreme fundamentale de codificare

Cele mai multe noțiuni introduse se bazează pe modelul prezentat in sectiunea 1.3.2 , compus dintr-o sursă de informații, un canal și un utilizator. În această secțiune vom adăuga modelului un sistem de comunicare și vom analiza trei teoreme de bază referitoare la codificarea informației. Așa cum arată figura 1.4, sistemul de comunicare se află situat între sursa de informații și utilizator și se compune dintr-un codificator și un decodificator.

Fig. 1.4 Reprezentarea unui sistem de comunicare

Shannon a formulat trei teoreme fundamentale de codificare, care corespund la trei situații care pot descrie sistemul de comunicare.

1.4.1 Teorema de codificare fără erori

Atunci când canalul de informații și sistemul de comunicație sunt fără erori, principala funcție a sistemului de comunicație este de a reprezenta sursa cât mai compact posibil. În aceste condiții, teorema de codificare fără erori, cunoscută și sub numele de prima teoremă a lui Shannon, definește lungimea medie minimă a unui cuvânt de cod pe simbol-sursă ce poate fi obținută.

O sursă de informații definită de ansamblul finit (A, z), având simboluri sursă statistic independente, se numește sursă de memorie zero. Dacă se consideră ieșirea sa ca fiind un n-tuplu de simboluri din alfabetul sursă (n>1),aceasta se va numi variabilă bloc aleatoare. Ea poate lua oricare din cele Jn valori posibile, notate i, din mulțimea de secvențe A = {1, 2,…, Jn },unde fiecare i se compune din n simboluri ale lui A. Probabilitatea lui , notată P(i ) este:

(1.4.1)

Notând z= { P(1), P(2), …, P(jn)}, entropia sursei este:

(1.4.2)

Aplicând relația (1.4.1) rezultă H(z) =n H(z) (1.4.3). Sursa (A,z) se numește n-extensie a sursei inițiale.

Întrucât informația internă a secvenței de ieșire i este log(1/P(i)), i se va codifica cu un cuvânt de cod de lungime l(i) astfel încât:

(1.4.4)

Intuiția ne sugerează reprezentarea secvenței de ieșire i printr-un cuvânt de cod a cărui lungime să fie cel mai mic întreg mai mare decât informația internă a lui i.( se poate construi un singur cod valid cu această constrângere). Prin înmulțire cu P(i) și sumare după i, obținem:

, de unde rezultă apoi

H(z) Lavg < H(z)+1 (1.4.5), unde Lavg este lungimea medie a cuvântului de cod corespunzător n-extensiei unei surse nonextinse. Prin urmare, rezultă:

(1.4.6)

Prin împărțire la n obținem: H(z) Lavg /n < H(z)+ (1.4.7), iar apoi, prin trecere la limită: (1.4.8).

Ecuația (1.4.8) reprezintă prima teoremă a lui Shannon pentru o sursă de memorie zero. Ea afirmă ca putem obține valori ale Lavg /n oricât de apropiate de H(z) codificând extensiile de ordin cât mai mare ale sursei. Deși obținut în urma presupunerii independenței statistice a simbolurilor-sursă, rezultatul poate fi extins și pentru cazuri mai generale.

Pe baza rezultatului oferit de prima teoremă a lui Shannon definim eficiența a unei strategii de codificare:

(1.4.9)

1.4.2 Teorema de codificare de canal

În cazul în care canalul sistemului de compresie este predispus la erori, interesul constă în minimizarea erorilor de comunicare, astfel încât sistemul să asigure un transfer cât mai bun de informații. Apare în mod firesc întrebarea: cât de mici pot fi făcute erorile în comunicație?

Exemplu: Un canal simetric binar (pentru care p(0)=p(1)=1/2) are probabilitatea de eroare pe = 0.01 (adică 99% din simbolurile-sursă se transmit corect prin canal). O metodă simplă pentru creșterea siguranței în comunicație este repetarea fiecărui simbol binar intr-un mesaj de câteva ori. Să presupunem, de exemplu, că în loc să transmitem un 0 și un 1, transmitem mesajele codificate 000 și 111. Probabilitatea de a nu interveni erori în timpul transmisiei unui mesaj de 3 simboluri este (1- pe)3 sau pe3, iar probabilitățile de transmitere a unei singure erori, a două, respectiv trei erori sunt 3pe pe2, 3pe2 pe, respectiv pe3. Întrucât probabilitatea de transmisie eronată a unui singur simbol este mai mică decât 50%, mesajele recepționate pot fi decodificate pe baza valorilor majoritare obținute în urma recepționării celor trei simboluri. Atunci, probabilitatea de decodificare incorectă a unui cuvânt de cod compus din 3 simboluri este pe3+3 pe2 pe. Când nu intervine nici o eroare, sau doar una singură,valoarea obținută majoritar decodează corect mesajul. Pentru pe=0.01, probabilitatea de intervenție a unei erori de comunicare este redusă la 0.0003.

Extinzând schema de codificare repetitivă descrisă mai sus, putem micșora oricât de mult erorile globale de comunicare. În cazul general, realizăm acest lucru prin codificarea n-extensiei sursei utilizând secvențe de cod k-are de lungime r, unde krJn. Ideea principală este de a selecta numai din cele kr secvențe de cod posibile ca fiind valide și de a stabili apoi o regulă de decizie care optimizează probabilitatea unei decodificări corecte. În exemplul precedent, repetarea fiecărui simbol-sursă de trei ori este echivalent cu codificarea în bloc a sursei binare nonextinse utilizând 2 secvențe de ieșire de 23=8 cuvinte de cod binare posibile, cele două cuvinte de cod valide fiind 000 și 111. Dacă decodorul primește un cuvânt de cod nonvalid, valoarea majoritară determină evaluarea ieșirii.

Rata de generare a informației (măsurată în unități de informație pe simbol) pentru o sursă de informații de memorie zero este egală cu entropia sa, H(z). n-extensia unei surse generează informații cu o rată de H(z)/n unități de informație pe simbol. Dacă informația e codificată, ca în exemplul precedent, rata maximă a informației codificate este (log)/r și se obține atunci când cele cuvinte de cod valide utilizate pentru codificarea sursei sunt echiprobabile. Prin urmare, un cod de dimensiune și lungime a blocului r va avea rata

R = log (/ r).

Teorema a doua a lui Shannon afirmă că R<C, unde C este capacitatea canalului de memorie zero caracterizat de matricea Q, există rZ și un cod de blocuri de lungime r și rată R astfel încât probabilitatea unei erori de decodare în bloc <,>0. Cu alte cuvinte, probabilitatea de eroare poate fi făcută oricât de mică atâta timp cât rata mesajului codificat este mai mică decât capacitatea canalului.

1.4.3 Teorema de codificare a sursei

Presupunem că ne aflăm în situația în care canalul este fără erori, însa se dorește o comprimare mult mai bună a datelor furnizate de sursă, cu sacrificarea unei zone din conținutul informațional (se acceptă un nivel maxim acceptabil de distorsie D). Ne propunem să determinăm cea mai mică rată supusă criteriilor de fidelitate menționate, la care pot fi transmise utilizatorului informațiile despre sursă. Această problemă se adresează în special unui capitol din teoria informației numit teoria ratei de distorsie.

Considerăm sursa de informații și ieșirile decodorului definite de perechile finite (A,z) , respectiv (B,v), în condițiile în care canalul este fără erori iar matricea de canal Q care realizează legatura dintre z și v reprezintă complet un proces de codificare-decodare. Întrucât procesul este determinist, Q descrie un canal artificial de memorie zero care modelează efectul compresiei și decompresiei de informații. De fiecare dată când sursa transmite simbolul aj, acesta se reprezintă printr-un simbol de cod, ce urmează a fi decodat, rezultând simbolul de ieșire bk cu probabilitatea qkj.

În ce privește problema codificării sursei astfel încât distorsia medie să fie mai mică decât D, aceasta necesită formularea unei reguli care să asocieze o valoare de distorsie cantitativă fiecărei aproximări posibile a ieșirii sursei. Pentru cazul simplu al unei surse nonextinse, putem folosi o funcție de cost nenegativă p(aj,bk), numită măsură de distorsie, pentru a defini penalizarea asociată reproducerii ieșirii sursei aj cu ieșirea decodorului bk. Ieșirea sursei este aleatoare, astfel încât distorsia este definită tot printr-o variabilă aleatoare, a cărei valoare medie, notată d(Q) este:

(1.4.10)

O procedură particulară de codificare-decodare este D-admisibilă dacă și numai dacă distorsia medie asociată lui Q este mai mică sau egală cu D.

Notăm QD = { qkj / d(Q) D }. (*)

Întrucât fiecare proces de codare-decodare este definit prin matricea artificială de canal Q, informația medie obținută prin observarea unei singure ieșiri a decodificatorului poate fi calculată din ecuația (1.3.11). Astfel, putem defini funcția ratei de distorsie:

(1.4.11), și observăm că minimul se atinge în Q. Dacă D=0, rezultă B(D) H(z).

Ecuația (1.4.11) definește rata minimă la care orice informație referitoare la sursă poate fi transmisă utilizatorului în condițiile restricției că distorsia medie să fie mai mică sau egală cu D. Pentru a calcula această rată minimizăm pur și simplu I(z,v) (vezi ec 1.3.11) printr-o alegere corespunzătoare a lui Q, supusă următoarelor constrângeri:

qkj 0 (1.4.12), (1.4.13), d(Q) = D (1.4.14)

Exemplu de măsură de distorsie (fiecare eroare de codificare-decodificare e considerată ca fiind o unitate de distorsie):

După ce am realizat calculul B(D) (pentru orice sursă de memorie zero și măsură de distorsie singulară (adică pentru care distorsia asociată unui bloc de simboluri este suma distorsiilor fiecărui simbol din bloc), teorema de codificare a sursei afirmă că , r și un cod de lungime r și R<R(D)+ astfel încât distorsia medie pe simbol d(Q)D+. O consecință practică a acestei teoreme și a celei anterioare este că ieșirea sursei poate fi reconstituită de decodificator cu o probabilitate de eroare oricât de mică, asigurând canalului o capacitate C>B(D)+. Acest rezultat este cunoscut sub numele de teorema de transmitere a informației.

1.4.4 Aplicații

Teoria informației asigură instrumentele necesare reprezentării și manipulării directe și cantitative a informației. Vom analiza aplicațiile acestora în domeniul specific al compresiei de imagini și vom încerca să dezvoltăm pentru început un model statistic de generare a imaginii.

Exemplu: Considerăm că se cere estimarea conținutului de informație (sau entropia) imaginii simple de 8 biți:

21 21 21 95 169 243 243 243

21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

21 21 21 95 169 243 243 243

O metodă de abordare relativ simplă este de a considera un model particular de sursă și de a calcula entropia imaginii pe baza acestuia. De exemplu putem presupune că imaginea a fost produsă de o sursă imaginară de niveluri de gri pe 8 biți care emite secvențial pixeli statistic independenți în funcție de o lege predefinită de probabilitate. În acest caz, simbolurile-sursă sunt nivelurile de gri iar alfabetul sursei este compus din 256 simboluri posibile. Dacă probabilitățile simbolurilor au o formă standard (de exemplu, gaussiană), conținutul mediu de informație sau entropia fiecarui pixel al imaginii se poate calcula cu ajutorul relației (1.3.2). În cazul unei distribuții uniforme, de exemplu, simbolurile-sursă sunt echiprobabile, iar entropia sursei este de 8 biți/pixel. Prin urmare, entropia totală a imaginii-eșantion de 48 precedentă este de 256 biți.

O metodă alternativă de estimare a conținutului de informație presupune construirea unui model al sursei pe baza frecvenței relative de apariție a nuanțelor de gri în imaginea considerată. O imagine observată poate fi interpretată, cu alte cuvinte, ca o demonstrație a comportamentului sursei de niveluri de gri care a generat-o. În aceste condiții, este de preferat folosirea histogramei nivelurilor de gri:

O estimare de ordinul întâi a entropiei sursei se poate calcula pe baza relației (1.3.2) și are, în acest exemplu, o valoare de 1.81 biți/pixel (de unde rezultă o entropie totală de 58 biți).

Se pot obține estimări mai bune examinând frecvența relativă a blocurilor de pixeli din imaginea eșantion, unde prin bloc înțelegem un grup de pixeli adiacenți. Această estimare aproximează cu atât mai bine entropia sursei cu cât crește lungimea blocului. Vom calcula prin urmare frecvența relativă a perechilor de pixeli (adică a doua extensie a sursei):

Rezultatul estimării entropiei este de 2.5/2 = 1.25 biți/pixel. Această estimare se obține prin calcularea frecvenței relative a blocurilor de 2 pixeli și se numește estimare de ordinul doi. Estimările corespunzătoare de ordin superior vor oferi aproximări din ce în ce mai bune ale entropiei sursei.

Estimarea de ordinul întâi a entropiei este limita inferioară a compresiei ce poate fi obținută prin utilizarea exclusivă a unui cod de lungime variabilă. Prin urmare, diferențele dintre estimările de ordin superior și cea de ordinul întâi indică prezența sau absența redundanțelor spațiale. Dacă pixelii sunt statistic independenți (adică dacă nu există redundanță spațială), estimările de ordin superior sunt echivalente cu estimarea de ordinul întâi, iar codul de lungime variabilă oferă o compresie maximă.

Estimarea de ordinul întâi a entropiei unei imagini nu reprezintă în mod necesar rata minimă de cod a acesteia, datorită faptului că pixelii unei imagini în general nu sunt statistic independenți. Procesul de minimizare a entropiei unei imagini se numește codificarea sursei și combină, în cazul fără erori, cele două operații, de mapare și codificare de simboluri. Dacă se tolerează pierderi de informație, include și operația de cuantificare.

Tot cu ajutorul instrumentelor teoriei informației putem aborda problema un pic mai complicată a compresiei de imagini cu pierderi. În acest caz, rezultatul principal este teorema de codificare a sursei. Pentru aplicarea corectă a acestui rezultat este necesară stabilirea unui model corespunzător de sursă și a unei măsuri de distorsie și calcularea funcției ratei de distorsie obținută B(D). Primul pas al acestui proces a fost deja analizat. Al doilea pas constă în adoptarea unui criteriu de fidelitate obiectivă, iar pasul final implică găsirea unei matrici Q care minimizează ecuația (1.3.11), și supusă constrângerilor date de relațiile (*) și (1.4.14).

1.5 Compresia fără erori

În cele mai multe aplicații în care este necesară reducerea cantității de date, se acceptă numai compresia fără erori. Ne vom opri de aceea, asupra principalelor strategii folosite în mod curent.

Tehnicile de compresie fără erori se împart în două categorii relativ independente: 1.stabilirea unei reprezentări alternative a imaginii, care să reducă redundanțele spațiale.

2.codificarea acestei reprezentări în vederea eliminării redundanțelor de codificare.

Acești pași corespund operațiilor de mapare și codificare de simboluri discutate anterior.

1.5.1 Codificarea în lungime variabilă

Cea mai simplă metodă de realizare a compresiei fără erori constă în reducerea doar a redundanței de codificare. Așa cum am menționat deja, acest lucru se obține codificând nivelurile de gri astfel încât să minimizeze relația (1.1.8). Pentru aceasta este necesară construcția unui cod de lungime variabilă care să asocieze cele mai scurte cuvinte de cod posibile nuanțelor de gri cu cea mai mare probabilitate de apariție. Prezentăm în continuare câteva metode de construcție a unui astfel de cod.

1.5.1.1 Codificarea Huffman

Codificarea Huffman este cea mai cunoscută tehnică de îndepărtare a redundanțelor de codificare și obține cel mai mic număr de simboluri de cod pe simbol- sursă.

Primul pas în procedura de codificare Huffman este de a crea o serie de reduceri ale sursei prin ordonarea probabilităților simbolurilor considerate și combinarea simbolurilor cu probabilitățile cele mai mici într-un singur simbol ce le va înlocui în următoarea reducere a sursei. Procesul continuă până la obținerea unei surse reduse de 2 simboluri.

Fig.1.5 Reducerea sursei in procesul de codificare Huffman binara

Fig.1.6 Procedura de codificare Huffman

Al doilea pas în procedura de codificare Huffman constă în codificarea fiecărei surse reduse, începând cu sursa cea mai mică. Codul binar de lungime minimă pentru o sursă de 2 simboluri este, evident, format din simbolurile 0 și 1. Întrucât simbolul cu probabilitatea 0.6 al ultimei surse reduse (codificat cu 0) a fost generat prin combinarea a două simboluri din sursa redusă situată la stânga sa, prima literă de cod a celor două simboluri va fi 0, după care se adaugă arbitrar 0 sau 1, pentru a le distinge. Această operație se repetă pentru fiecare sursă redusă, până când se ajunge la sursa originală și se obține codul final.

După construirea codului (care este unic determinat), orice șir de simboluri codificate Huffman se poate decodifica prin analizarea simbolurilor individuale de la stânga la dreapta. De exemplu, pentru codul binar din figura 5.2, din parcurgerea de la stanga la dreapta a șirului codificat 010100111100 rezultă că primul cuvânt valid de cod este 01010, care este codul simbolului a3. Următorul este 011, care codifică simbolul a1, etc. În final se obține mesajul complet decodificat: a3a1a2a2a6.

1.5.1.2 Alte coduri de lungime variabilă utilizate

Când procesul de codificare implică un număr foarte mare de simboluri, construcția codului binar Huffman devine foarte dificilă. În cazul în care avem de codificat J simboluri-sursă, sunt necesare J-2 reduceri de sursă și J-2 asocieri de coduri. Astfel, construcția codului optim Huffman pentru o imagine de 256 de nuanțe de gri necesită 254 reduceri de sursă și 254 asignări de cod. Din punct de vedere al complexității computationale a acestei sarcini, câteodată este necesară sacrificarea eficienței codificării în favoarea simplității construcției codului.

Tabelul de mai jos ilustrează 4 coduri de lungime variabilă. Se observă că lungimea medie a codului Huffman este mai mică decât în cazul celorlalte coduri, codul binar natural având lungimea cea mai mare. În plus, coeficientul de 4.05 biți/simbol obținut prin metoda Huffman se apropie mult de valoarea limită a entropiei sursei, care este 4biți/simbol.

Deși nici unul dintre codurile prezentate nu atinge eficiența codului Hufman, toate sunt ușor de construit. Ca și în cazul metodei Huffman, se asociază cuvintele cele mai scurte celor mai frecvente simboluri-sursă.

Coloana 5 ilustrează codul Huffman trunchiat, generat prin codificarea Huffman doar a celor mai probabile simboluri ale sursei, pentru câteva valori întregi pozitive <J. Un cod prefix urmat de un cod de lungime fixă corespunzător este utilizat pentru a reprezenta toate celelalte simboluri-sursă. În tabelul e mai sus = 12, iar codul-prefix a fost generat ca al 13-lea cuvânt de cod. Adică, un simbol-prefix a cărui probabilitate este suma probabilităților simbolurilor a13 – a21 a fost inclus ca un al 13-lea simbol în timpul codificării Huffman a celor mai probabile 12 simboluri-sursă. Cele 9 simboluri rămase vor fi apoi codificate utilizând prefixul de cod (care aici este 10) și o valoare binară de 4 biți egală cu indicele simbolului minus 13.

Coloana a șasea a tabelului ilustrează un alt cod de lungime variabilă cunoscut sub numele de B-cod. Fiecare cuvânt de cod se compune din biți de continuare, notați cu C, si biți de informație, reprezentați prin numere binare. B-codul din tabel se numește B2-cod întrucât se utilizează 2 biți de informație la un bit de continuare. Secvența de B2-cod corespunzătoare șirului a11a2a7 este 001 010 101 000 010 sau 101 110 001 100 110, în funcție de cum am ales primul bit de continuare (0 sau 1).

Celelalte două coduri din tabel au fost numite coduri cu deplasare (shift-coduri). Un shift-cod se generează astfel:

Se aranjează simbolurile-sursă în ordinea descrescătoare a probabilităților

Se împarte numărul total de simboluri în blocuri de lungimi egale

Se codifică elementele individuale din interiorul tuturor blocurilor în mod identic

Se adaugă simbolurile speciale de deplasare înainte sau înapoi pentru identificarea fiecarui bloc.

Pentru a genera codul binar de 3 biți din coloana 7, sursa de 21 de simboluri a fost în primul rând ordonată în funcție de probabilitățile de apariție și împărțită în 3 blocuri de câte 7 simboluri. Simbolurile individuale ale blocului superior – considerat ca fiind bloc de referință – sunt apoi codificate în cod binar de la 000 la 110. Cel de-al 8-lea cuvânt de cod binar (111) nu este inclus în blocul de referință, însă este utilizat în controlul deplasărilor ce identifică blocurile rămase. Simbolurile celorlalte 2 blocuri se codifică apoi prin combinarea unuia sau a două simboluri de deplasare cu codurile binare utilizate pentru codificarea blocului de referință.

Codul Huffman cu deplasare (coloana 8) a fost generat într-un mod similar. Principala diferență constă în asocierea unei probabilități simbolului de deplasare, după ce s-a aplicat în prealabil codificarea Huffman a blocului de referință. În mod natural, asocierea se realizează sumând probabilitățile tuturor simbolurilor-sursă situate în afara blocului de referință, adică utilizând același principiu pe care l-am folosit în definirea simbolului-prefix în codul Huffman trunchiat. În acest caz, suma este 0.39. Simbolul de deplasare este deci cel mai probabil simbol și i se asociază unul din cele mai scurte cuvinte de cod (00).

1.5.2 Codificarea aritmetică

Spre deosebire de codurile de lungime variabilă descrise anterior, codificarea aritmetică nu generează coduri-bloc (nu există o corespondență unitară între simb-sursă și cuvintele de cod). În schimb, unei întregi secvențe de simboluri (mesaj) i se asociază un singur cuvânt de cod aritmetic, ce definește un interval de numere între 0 și 1. Cu cât crește numărul de simboluri din mesaj, cu atât intervalul utilizat pentru reprezentarea sa devine mai mic și numărul de unități de informație (biți, de ex) necesari reprezentării intervalului crește.

Fiecare simbol al mesajului reduce lungimea intervalului în funcție de probabilitatea sa de apariție. Întrucât această tehnică nu necesită, ca în cazul metodei Huffman, ca fiecare simbol-sursă să se traducă într-un număr integral de simboluri de cod, ea atinge teoretic limita stabilită de teorema de codificare fără erori.

Să considerăm, de exemplu, că se dorește codificarea aritmetică a secvenței a1a2a3a4, provenită de la o sursă de 4 simboluri. La începutul procesului de codificare, mesajului i se asociază întregul interval [0,1). Acest interval se împarte în 4 regiuni în funcție de probabilitățile fiecărui simbol-sursă. Simbolului a1, de exemplu, i se asociază intervalul [0, 0.2), etc. Considerând primul simbol codificat, intervalul mesajului se va restrânge la [0, 0.2). Acest nou interval se împarte din nou în funcție de probabilitățile simbolurilor-sursă originale, procedeul continuând apoi cu următorul simbol al mesajului. În acest fel, simbolul a2 restrânge subintervalul la [0.04, 0.08), a3 la [0.056, 0.072) și așa mai departe. Ultimul simbol al mesajului, privit ca indicator al sfârșitului de mesaj, restrânge intervalul la [0.06752, 0.0688). Orice număr din acest interval, de exemplu 0.068, poate fi folosit pentru a reprezenta mesajul.

În exemplul anterior, se folosesc 3 unități zecimale pentru a reprezenta un mesaj de 5 simboluri, deci 0.6 unit zecimale/simbol, valoare care se apropie favorabil de entropia sursei, care este 0.58 unit zecimale/simbol. Rezultatul codificării aritmetice se apropie de limita stabilită de teorema de codificare fără erori proporțional cu lungimea secvenței ce urmează a fi codificată. Practic, există doi factori ce determină această diferență:

– adăugarea indicatorului de sfârșit de mesaj, necesar pentru a separa mesajele între ele.

– utilizarea unei precizii aritmetice finite

1.5.3 Codificarea în planuri de biți

Următoarea metodă de codificare urmărește reducerea redundanțelor spațiale și are la bază ideea de descompunere a unei imagini pe mai multe niveluri într-o serie de imagini binare, ce urmează apoi a fi comprimate prin una din metodele cunoscute.

Descompunerea în planuri de biți (planuri elementare)

Nuanțele de gri ale unei imagini de m biți se pot reprezenta sub forma:

am-12m-1+ am-22m-2+…+ a121+ a020 (1.5.1)

Pornind de la această idee, o metodă simplă de descompunere a imaginii într-o colecție de imagini binare constă în separarea celor m coeficienți în m planuri elementare de 1 bit. Planul elementar de ordinul i (i=0,m-1) se generează pe baza celor ai biți ai fiecărui pixel. În general, fiecare plan elementar se construiește asociind fiecărui pixel din imaginea originală coeficientul polinomial corespunzător. Dezavantajul acestei abordări este că modificări mici ale nuanțelor pot avea un impact semnificativ asupra complexității planurilor elementare. Dacă un pixel de intensitate 127 (0111111) este adiacent unui pixel de intensitate 128 (1000000), fiecare plan elementar va conține o tranziție corespunzătoare de la 0 la 1 sau invers.

O abordare alternativă de descompunere (care reduce efectul variațiilor de nuanță) este de a reprezenta mai întâi imaginea într-un cod Gray de m biți. Codul Gray de m biți gm-1… g2g1g0 corespunzător formei polinomiale (1.5.1) se calculează astfel:

gi = ai ai+1 , 0im-2

gm-1 = am-1 , unde reprezintă “sau exclusiv”.

Caracteristica principală este diferența de o singură poziție de bit între cuvintele de cod succesive. Astfel, când 127 și 128 sunt adiacente, de exemplu, doar al 7-lea plan elementar va conține o tranziție de la 0 la 1, întrucât codul Gray corespunzător celor doi pixeli adiacenți 127 și 128 va fi 11000000, respectiv 01000000.

1.5.4 Codificarea imaginilor binare

1.5.4.1 Codificarea regiunilor constante

O metodă simplă de a comprima o imagine binară sau un plan elementar este de a utiliza cuvinte de cod speciale pentru a identifica suprafețe întinse formate numai din 1 sau 0. Într-o astfel de abordare, numită codificarea regiunilor constante, imaginea este împărțită în blocuri de dimensiune mn pixeli, clasificate ca fiind fie albe, fie negre sau de intensitate mixtă. Categoria cu cea mai frecventă apariție este cea căreia i se asociază cuvântul de cod de 1 bit 0, iar celorlalte două categorii li se asociază cuvinte de cod de 2 biți 10 și 11. Compresia se realizează întrucât cei mn biți utilizați în mod normal pentru reprezentarea fiecărei suprafețe constante se înlocuiesc cu cuvinte de cod de 1 sau 2 biți. Evident, codul asociat categoriei de intensitate mixtă este utilizat ca un prefix urmat de modelul blocului de mn biți.

Când e necesară comprimarea documentelor cu textură predominant albă, o metodă simplă este de a codifica suprafețele albe (informațiile de fundal) cu 0 și toate celelalte blocuri (inclusiv cele exclusiv negre), care marchează obiectele imaginii, cu 1 urmat de codificarea blocului. Această metodă, numită de omisiune a blocurilor albe (WBS), are avantajul de a anticipa tendințele structurale ale imaginii ce urmează a fi comprimată. Cum prezența câtorva regiuni exclusiv negre este de așteptat, acestea se grupează cu regiunile mixte, permițând utilizarea unui cuvânt de cod de 1 bit pentru blocurile albe, cu probabilitate mare de apariție.

Există două abordări ale acestei metode: una unidimensională și una bidimensională.

Metoda de codificare WBS unidimensională împarte liniile imaginii în segmente de N pixeli. Pentru codificarea segmentelor compuse din pixeli albi se utilizează cuvântul de cod de 1 bit “0”, în timp ce segmentele ce conțin cel putin un pixel negru se codifică printr-un cuvânt de cod de N+1 biți, primul bit fiind 1 iar ceilalți N biți fiind preluați din datele originale. De exemplu, pentru 00001011 și N=4, codul WBS unidimensional este 011011.

În urma aplicării acestei metode de codificare se obține o rată de 1-pw + (1/N) biți/pixel, unde pw este probabilitatea de apariție a unui segment alb.

În codificarea WBS bidimensională, în locul segmentelor se codifică blocuri de dimensiune MM. Similar, se va utiliza cuvântul de cod “0” pentru marcarea unui bloc în întregime alb, și un cuvânt de cod de M2+1 biți pentru reprezentarea blocurilor ce conțin cel puțin un pixel negru.

O metodă WBS adaptativă, mai eficientă, a fost propusă de DeCoulon și Johnsen. Se pornește inițial de la un bloc de dimensiune MM, cu M=16, de exemplu. Dacă blocul este în întregime alb, i se asociază cuvântul de cod “0”. În caz contrar, se utilizează prefixul 1 și se împarte blocul în subblocuri de dimensiune 88. Procedeul continuă pentru fiecare din aceste subblocuri, până la obținerea de subblocuri de dimensiune 22.

1.5.4.2 Codificarea dinamică unidimensională

O alternativă de codificare a suprafețelor constante este de a reprezenta fiecare linie a unei imagini binare (sau plan binar) printr-o secvență de lungimi care să descrie traiectoriile succesive ale pixelilor negri și albi. Această metodă reprezintă, alături de extinderea sa în planul bidimensional, abordarea standard în domeniul codificării în facsimil (FAX). Ideea centrală este de a codifica fiecare grup continuu de 0 sau 1 întâlnit pe parcursul scanării de la stânga la dreapta a unei linii, prin lungimea corespunzătoare și de a stabili o convenție pentru determinarea valorii de deplasare. Acest lucru se poate realiza specificând valoarea primei deplasări pentru fiecare linie sau presupunând că fiecare linie începe cu o deplasare albă, a cărei lungime poate fi 0.

De exemplu, codul dinamic 24,2,68,2,33 reprezintă o linie binară de 128 de pixeli, care începe cu 24 de pixeli albi, urmați de 2 pixeli negri, 68 albi, 2 negri și din nou 33 albi.

Fie {1,2,…,N} mulțimea de valori pe care le pot lua tranzițiile de la alb la negru, unde N este lungimea liniei. Acestei mulțimi i se asociază un set de probabilități {p1,p2,…,pN}, pe baza cărora se construiește un cod de lungime variabilă.

De exemplu, dacă considerăm simbolul aj ce reprezintă un drum negru de lungime j, putem estima probabilitatea ca simbolul aj să fie emis de o sursă imaginară de drumuri negre împărțind numărul de linii negre de lungime j din întreaga imagine la numărul total de linii negre.

O estimare a entropiei acestei surse de linii negre, notată H0, rezultă din substituția acestor probabilități în relația (1.3.2). Analog pentru entropia liniilor albe, notată H1.Aproximarea entropiei imaginii este:

HRL = (H0+ H1)/( L0+ L1) (1.5.2)

unde L0 este valoarea medie a lungimii liniilor negre, iar L1 valoarea medie a lungimilor liniilor albe.

1.5.4.2 Codificarea dinamică bidimensională

Codificarea analizată anterior poate fi ușor extinsă într-o varietate de proceduri de codificare în planul bidimensional. Una din cele mai cunoscute metode este codificarea în adrese relative (RAC), care se bazează pe principiul punerii în evidență a tranzițiilor binare care încep și care termină fiecare drum negru sau alb.

Notând: ec = distanța de la tranziția curentă c la ultima tranziție efectuată liniei curente e, cc = distanța de la c la prima tranziție similară trecută (în aceeași direcție), notată c, din linia precedentă.

Dacă ec cc, rezultă d = ec, și se utilizează pentru reprezentarea liniei curente. Dacă cc<ec, atunci d = cc, unde d este distanța codificată RAC.

RAC necesită stabilirea unei convenții pentru determinarea valorilor drumurilor. În plus, tranzițiile imaginare de la începutul și sfârșitul fiecărei linii, ca și eventuala linie de început (una albă, de exemplu) trebuie considerate astfel încât marginile imaginii să poată fi controlate corespunzător. În final, întrucât distribuțiile de probabilitate ale distanțelor RAC ale celor mai multe imagini nu sunt uniforme în practică, pasul final al procedurii RAC este de a codifica distanța RAC selectată utilizând un cod corespunzător de lungime variabilă.

Așa cum se poate observa din figura 5.3.1, se poate utiliza un cod similar codului B2. Celor mai mici distanțe li se asociază cele mai mici cuvinte de cod, iar toate celelalte se codifică utilizând un prefix pentru a indica cea mai mică distanță RAC, un al doilea prefix care asociază d unui interval specific de distanțe și reprezentarea binară (notată XXX…X în figură) a lui d minus distanța de bază a intervalului. Dacă ec = 8, cc = 4 ca în figură, cuvântul de cod RAC corespunzător este 110001

Fig 1.7 O ilustrare a codificării în adrese relative

1.5.5 Codificarea predictivă fără pierderi

Această metodă se bazează pe eliminarea redundanțelor spațiale ale pixelilor apropiați prin extragerea și codificarea doar a informației nou-introdusă de fiecare pixel. Această “nouă informație” a fiecărui pixel se definește ca diferența dintre valoarea reală și cea estimată a fiecarui pixel.

Predictorul estimează nivelul de gri al pixelului curent din nivelurile de gri ale unui număr stabilit de pixeli vecini precedenți. Estimarea rezultată este apoi comparată cu valoarea reală pentru a obține eroarea de estimare. Combinația dintre predictor și comparator constituie dispozitivul de mapare (“mapper-ul”). Acest dispozitiv tranformă datele imaginii originale în date de eroare, mai puțin corelate și care necesită mai puțini biți la codificare.

În procesul invers, datele sunt inițial decodificate apoi adăugate datelor estimate în vederea reconstituirii imaginii originale. Predictorul este identic celui utilizat la transmitere.

Figura de mai jos evidențiază principalele componente ale unui sistem de codificare predictivă fără pierderi. Acesta constă într-un codificator și un decodificator, fiecare conținând un estimator (predictor) identic. Pe măsură ce codificatorul primește succesiv fiecare pixel al imaginii de intrare, predictorul generează valoarea sa estimată pe baza unui anume număr de intrări anterioare. Ieșirea predictorului este apoi rotunjită la cel mai mic întreg, notat .

Definim eroarea de predicție: ,care se reprezintă printr-un cod de lungime variabilă pentru a genera următorul element al șirului de date comprimate. Decodificatorul reconstruiește en din cuvintele de cod recepționate și realizează operația inversă: .

Imaginea Imagine (a)

de intrare comprimată

Imagine Imagine (b)

comprimată decomprimată

Fig 1.8 Modelul codificării predictive fără pierderi: (a) codificator; (b) decodificator.

În cele mai multe cazuri, estimarea funcției imagine se realizează pe baza combinației liniare a m pixeli anteriori:

(1.5.3)

unde m = ordinul predictorului liniar

i = coeficientul de estimare.

În codificarea predictivă unidimensională, relația de mai sus se scrie:

(1.5.4)

Se observă că predicția liniară unidimensională este o funcție determinată de pixelii anteriori situați doar în linia curentă. În codificarea predictivă bidimensională, predicția este determinată de pixelii anteriori obținuți prin scanarea de la stânga la dreapta și de sus în jos a imaginii. În cazul tridimensional se adaugă și pixelii cadrelor precedente. Relația (1.5.3) nu poate fi evaluată pentru primii m pixeli ai fiecărei linii, de aceea este necesară codificarea acestora prin alt mijloc (codificare Huffman, de exemplu), acest lucru fiind valabil și pentru cazurile cu mai multe dimensiuni.

Coeficientul de comprimare obținut în urma codificării predictive fără pierderi este direct proporțional cu reducerea entropiei rezultată în urma introducerii imaginii în sfera erorii de predicție. Întrucât prin predicție și diferențiere se înlătură o mare cantitate de redundanță spațială, funcția de densitate de probabilitate a erorii de predicție tinde spre 0 și se caracterizează printr-o variație relativ mică (în comparație cu distribuția inițială a nivelurilor de gri).

1.6 Comprimarea cu pierderi

Spre deosebire de metodele subliniate anterior, comprimarea cu pierderi se bazează pe compromiterea fidelității imaginii reconstituite în favoarea unei comprimări mai bune. Dacă distorsiunea rezultată (care poate fi sau nu aparentă vizual) poate fi tolerată, creșterea ratei de comprimare prezintă o foarte mare importanță.

1.6.1 Codificarea predictivă cu pierderi

Modelul unei astfel de codificări, prezentat în figura 6.1, conține, pe lângă componentele prezentate anterior, specifice codificării predictive fără pierderi, un cuantificator, plasat între codificatorul de simboluri și punctul de apariție a erorii de predicție. El primește la intrare rotunjirea codificatorului și transferă eroarea de predicție într-un interval limitat de ieșiri, notat , care stabilește gradul de comprimare și distorsie asociat codificării predictive cu pierderi.

Pentru a adapta sistemul introducerii pasului de cuantificare, codificatorul este modificat astfel încat predicțiile generate de codificator și decodificator să fie echivalente. Acest lucru se realizează prin introducerea predictorului codificatorului într-un circuit de feed-back, a cărui intrare, notată , este generată în funcție de anticipările anterioare și erorile cuantificate corespunzătoare.

Rezultă (1.6.1), unde a fost definit anterior.

Configurația de ciclu închis previne infiltrarea erorilor la ieșirea decodificatorului. Observăm din fig.6.1 că relația (1.6.1) este valabilă și pentru ieșirea decodificatorului.

Imagine Imagine (a)

de intrare comprimată

Imagine Imagine (b)

comprimată reconstituită

Fig.1.9 Un model de codificare predictivă cu pierderi: (a) codificator; (b) decodificator.

Delta modularea (DM) este o formă simplă de codificare predictivă, în care predictorul și cuantificatorul se definesc astfel:

și

unde <1 este un coeficient de predicție , iar este o constantă pozitivă. Se obține o rată de codificare de 1 bit/pixel. În regiunea de transfer rapid, unde este prea mic pentru a reprezenta schimbări semnificative de intrare, apare o distorsiune numită efect de curbură, în timp ce atunci când este prea mare pentru a reprezenta tranformări mici ale intrărilor, apare efectul granular. Aceste două tipuri de distorsiune sunt comune tuturor formelor de codificare predictivă cu pierderi. Gradul de distorsiune depinde de o mulțime complexă de interacțiuni existente între cuantificare și metodele de predicție aplicate.

Predictori optimi

Predictorii optimi utilizați în cele mai multe aplicații de codificare predictivă minimizează eroarea pătratică de predicție a codificatorului:

în condițiile în care

În aceste condiții, problema construcției predictorilor optimi se reduce la selectarea celor m coeficienți de predicție care minimizează expresia:

Derivând în funcție de fiecare coeficient și rezolvând sistemul de ecuații rezultat sub presupunerea că fn are media 0 și varianța 2 rezultă = R-1r (1.6.2), unde R-1 este inversa matricei de autocorelare:

(1.6.3)

iar r și sunt vectorii cu m elemente:

și (1.6.4)

Varianța erorii de predicție rezultată în urma utilizării acestor coeficienți optimali este:

(1.6.5)

Deși mecanismul de evaluare a expresiei (1.6.2) este relativ simplu, calculul autocorelațiilor necesare obținerii matricilor R și r este dificil în practică, de aceea predicțiile locale nu se folosesc aproape niciodată. În cele mai multe cazuri, se calculează o mulțime de coeficienți globali pe baza unui model simplu de imagine după care se înlocuiesc corelațiile corespunzătoare în relațiile (1.6.3) și (1.6.4). De exemplu, pentru o sursă Markov bidimensională a cărei funcție de autocorelare este: E{f(x,y)f(x-i,y-i)}= 2prph iar predictorii generalizați de ordinul 4:

f(x,y) = 1f(x, y-1) + 2f(x-1, y-1) +3f(x-1, y) +4f(x-1, y+1)

Coeficienții optimali rezultați (Jain[1991]) sunt: 1 = ph, 2 = – prph, 3 = pr, 4 = 0, unde ph și pr sunt coeficienții de corelație orizontali, respectiv verticali ai imaginii considerate.

În final, introducem condiția . Această restricție permite ieșirii predictorului situarea într-un interval acceptabil de niveluri de gri și reducerea impactului unei transmisii neclare, receptată sub forma unor linii orizontale în imaginea reconstituită. Acest lucru este important, întrucât o singură eroare se poate propaga în toate ieșirile ce vor urma, decodificatorul devenind instabil. Restricția impusă restrânge infiltrarea erorii doar asupra unui număr mic de ieșiri.

1.6.2 Codificarea transformatei

Metodele de codificare predictivă analizate anterior se aplică direct pixelilor unei imagini, de aceea au fost numite metode de domeniu spațial. În codificarea transformatei, o transformată liniară, reversibilă ( cum ar fi cea Fourrier) este utilizată pentru reprezentarea imaginii printr-un set de coeficienți ai transformatei, care sunt apoi cuantificați și codificați.

Figura 6.2.1 reprezintă schema unui sistem de codificare a transformatei. Decodificatorul implementează secvența inversă de pași (cu excepția operației de cuantificare) ai codificatorului, care realizează patru operații relativ simple: descompunerea în subimagini, transformarea, cuantificarea și codificarea. O imagine de intrare NN se subdivide inițial în subimagini (blocuri) de dimensiune nn, care la aplicarea transformatei, genereaza (N/n)2 matrici de transformare nxn. Scopul procesului de transformare este de a decorela pixelii fiecărei subimagini sau de a stoca cât mai multă informație posibilă într-un număr cât mai mic de coeficienți de transformare. Pasul de cuantificare elimină apoi selectiv sau cuantifică mai brut coeficienții care dețin cea mai puțină informație. Acești coeficienți au cel mai redus impact asupra calității imaginii reconstituite. Pentru fiecare bloc, se construiește o matrice de alocare de biți cu scopul de a indica numărul de biți asociați pixelilor din blocul respectiv. În funcție de această matrice de alocare a biților, receptorul poate separa datele codificate și va introduce zero-uri în spațiul pixelilor înlăturați. Ultimul pas constă în codificarea (printr-un cod de lungime variabilă) a coeficienților cuantificați.

Reconstituirea imaginii se obține prin aplicarea transformatei inverse asupra blocurilor și combinând apoi aceste blocuri.

Imagine Imagine

de intrare comprimată

(NN) (a)

Imagine Imagine

comprimată reconstituită (b)

Fig. 1.10 Sistem de codificare a transformatei: (a) codificator; (b) decodificator.

Transformata cosinusului

Cel mai des se aplică transformata cosinusului, întrucât, cu excepția transformatei Karhunen-Loeve, care se dovedește a fi optimă, însă care nu se poate transcrie într-un algoritm eficient, se apropie cel mai mult de optim, în condițiile considerării criteriului erorii medii pătratice și a modelului Gauss – Markov.

Transformata bidimensională a cosinusului, directă și inversă, se definește în felul următor:

unde /2 u,v = 0

c(u), c(v) = 1 u,v = 1,2,…,N-1

0 altfel

În cadrul metodei de codificare a transformatei cu ajutorul transformatei cosinusului, imaginea de intrare se subdivide inițial în subimagini (blocuri) de dimensiune 16×16 sau 8×8 în general.

=== Capitolul 2 ===

Capitolul 2.

Algoritmi de compresie a imaginilor

Practic, codificarea imaginilor în vederea compresiei se adresează reducerii cantității de date necesare în reprezentarea și memorarea unei imagini digitale. Toate metodele de compresie se bazează pe exploatarea redundanțelor informaționale prezente în majoritatea datelor care reprezintă imagini. Redundanța poate fi descrisă în mai multe moduri, fiecare din acestea conducând la o clasă particulară de algoritmi de compresie.

Redundanța statistică (de codificare) este direct legată de distribuția de probabilitate și va fi tratată cu ajutorul elementelor furnizate de teoria informației în capitolul 3. Metodele de compresie fără pierderi ( codificarea Huffman, dinamică, etc) se bazează pe îndepărtarea acestui tip de redundanță.

Un alt mod, care vizează în mod special eliminarea redundanțelor spațiale existente în cadrul informației furnizate de pixelii unei imagini constă în utilizarea predictibilității în vecinătăți locale. Modelele de predicție locală se bazează pe corelarea spațială existentă și încearcă decorelarea pixelilor în vecinătăți locale. Cele mai multe tehnici predictive realizează o compresie cu pierderi.

O altă metodă de compresie se obține cu ajutorul tranformatei de imagine și se bazează pe faptul că o serie de transformate ortogonale (DCT, KLT, WHT) pot concentra informația esențială a unei imagini într-un șir de coeficienți.

2.1 Codificarea Huffman

2.1.1 Descrierea algoritmului

Presupunem că se dă o imagine de NM pixeli, codificată în sistem PCM (pulse code modulation) cu B biți/pixel. Transmisia PCM necesită NMB biți pentru întreaga imagine digitală. În acest caz, fiecare din cele 2B niveluri de intensitate (nuanțe) ale imaginii se transmit utilizând B biți. Numărul mediu de biți/pixel poate fi redus prin aplicarea unui cod de lungime variabilă. Un astfel de cod este și codul Huffman, descris pe scurt in capitolul 1.

În codul Huffman, nici un cuvânt de cod nu este prefixul altui cuvânt de cod, aspect care asigură codului Huffman proprietatea de unic decodabilitate. Codul rezultat se reprezintă sub formă de arbore. Presupunem că imaginea are 8 niveluri de intensitate. Numărul de biți necesar în codificarea PCM este B = 3. Presupunem cunoscută distribuția de probabilitate p = (p(0), …, p(2B -1)} și se vor ordona nuanțele imaginii (niv. de intensitate) în ordinea descrescătoare a probabilității p(i). Nuanțele constituie nodurile arborelui Huffman, care se construiește în B-1 pasi. La fiecare pas, cele două noduri ale arborelui care au probabilitate minimă se combină formând un nod intermediar. Probabilitatea asociată nodului nou obținut va fi suma probabilităților nuanțelor corespunzătoare celor două ramuri. Procedura se repetă până se epuizează toate nivelurile de intensitate și se obține un nod rădăcină de probabilitate 1. Arborele obținut este apoi reordonat în vederea eliminării intersecțiilor ramurilor (fig 2.1). Secvențele de cod se construiesc traversând arborele de la rădăcină la celelalte noduri. La fiecare nivel se asignează 0 ramurii superioare și 1 celei inferioare. Procedeul se repetă până în momentul în care s-au traversat toate nodurile arborelui. Fiecare nod corespunde unei singure nuanțe. Secvența de cod asociată unei nuanțe constă în succesiunea de 0 și 1 rezultată în urma traversării arborelui de la rădăcină la nodul corespunzător.

0.12 0 i=0 C=000

0.27

0.57 0

0 0.15 1 i=3 C=001

1.0 1 0.30 i=2 C=01

0.26 0 i=1 C=10

1 0.43

0.1 0 i=4 C=110

0.17 1 0.03 0 i=5 C=1110

0.07 0.02 0

1 1 i=6 C=11110

0.04 0.02 1 i=7 C=11111

Fig 2.1 Construcția și rearanjarea arborelui Huffman

2.1.2 Implementare în C

Programul care construiește codul Huffman va fi prezentat în continuare, însă se impun în prealabil unele precizări asupra instrumentelor utilizate. Procedura huftree() utilizează vectorul de probabilitate a nuanțelor pentru a crea un arbore de codificare ale cărui noduri sunt de forma:

typedef struct symbol far*SPOINTER;

struct symbol { float prob;

SPOINTER comp[2]; };

Nodurile arborelui sunt cuprinse într-un vector numit leaf și pointat de *lpnr. Fiecare element al acestui vector conține probabilitatea nuanței corespunzătoare. La fiecare pas, se utilizează procedura find2min() pentru a găsi 2 noduri ale arborelui cu probabilitate minimă. Aceste noduri se combină într-un nod nou prin intermediul procedurii merge(). La sfârșitul construcției arborelui, procedura întoarce rădăcina arborelui. Ulterior, arborele obținut este accesat prin utilizarea subrutinei treeaccess(), în scopul de a produce secvența de cod corespunzătoare fiecărui nod al arborelui. Întreaga tabelă de secvențe de cod este returnată de șirul code.

int huftree (pdf, rpnr, lpnr, NUMOFSYMBOLS)

vector pdf;

SPOINTER *rpnr;

struct symbol far**lpnr;

int NUMOFSYMBOLS;

/* Subrutina pentru construcția arborelui Huffman:

pdf: vectorul probabilităților nivelurilor de gri

rpnr: pointer la rădăcina arborelui de decodificare

lpnr: pointer la șirul nodurilor arborelui de decodificare

NUMOFSYMBOLS: numărul de simboluri ale imaginii */

{int i, j;

SPOINTER *nodes;

int min[2];

/* Se pregătește construcția arborelui de decodificare Huffman */

/* ‘leaf’ este un șir de elemente de tip symbol care corespunde nodurilor arborelui Huffman.

‘nodes’ este un șir de elemente de tip SPOINTER. Unul dintre ele va pointa rădăcina arborelui Huffman după construcția acestuia. Restul vor fi nule. */

if ((*lpnr = (struct symbol far*)

_fmalloc(NUMOFSYMBOLS*sizeof(struct symbol))) = = NULL)

return(-10);

if ((nodes = = (SPOINTER*)

malloc(NUMOFSYMBOLS*sizeof(SPOINTER))) = = NULL)

return(-10);

/* Se initializează ‘leaf’. Elementele șirului ‘nodes’ vor pointa elementele șirului ‘leaf’ */

i = initialize(nodes, lprn, pdf, NUMOFSYMBOLS);

if (i) return (i);

/* Construcția arborelui de decodificare Huffman */

for(i = NUMOFSYMBOLS – 1; i > 0; i – – )

{ if (find2min (nodes, min, NUMOFSYMBOLS) return(-310);

if ((nodes [(min[0] > min[1] ? min[1] : min[0])]

= merge(nodes, min)) = = NULL) return(-10);

nodes [(min[0] > min[1] ? min[0] : min[1])] = NULL;

}

/*Verifică câte elemente ale șirului ‘nodes’ sunt NULL. Dacă există cel puțin un element care nu este NULL sau dacă toate elementele lui ‘nodes’ sunt NULL, întoarce eroare de decodificare */

*rpnr = NULL;

for(i = 0; i < NUMOFSYMBOLS; i + +)

if (nodes[i]!=NULL)

{ if (*rpnr = = NULL) *rpnr = nodes[i];

else return(-310);}

if (*rpnr = = NULL) return(-310);

return(0);

}

int initialize (nodes, lpnr, pdf, NUMOFSYMBOLS)

SPOINTER *nodes;

struct symbol far**lpnr;

vector pdf;

int NUMOFSYMBOLS;

/*Procedura de inițializare a elementelor ‘leaf’ și ‘nodes’: vector de elemente de tip SPOINTER. Unul dintre ele va indica rădăcina arborelui Huffman după construcția arborelui.

lpnr: pointer către vectorul elementelor de tip symbol care corespund nodurilor arborelui Huffman.

pdf: scara de nuanțe pdf

NUMOFSYMBOLS: numărul de simboluri ale imaginii */

{

int i;

/* daca valorile pdf sunt 0.0 aduna o constanta mica */

for ( i=0; i < NUMOFSYMBOLS; i++)

{

if(pdf[i] = = 0.0) (*lpnr)[i].prob = 0.000001;

else (*lpnr)[i].prob = pdf[i];

(*lpnr)[i].comp[0] = NULL; (*lpnr)[i].comp[1] = NULL;

}

for (i = 0; i < NUMOFSYMBOLS; i++) nodes[i]=& (*lpnr)[i] ;

return(0);

}

int find2min(nodes, min, NUMOFSYMBOLS)

SPOINTER *nodes;

int min[2];

int NUMOFSYMBOLS;

/* Procedura care identifică cele două elemente pointate de ‘nodes’ care au probabilitate minimă.

nodes: vector de elemente de tip SPOINTER.

min: tabela rezultat care conține elementele ce pointează poziția acelor două elemente ale ‘nodes’ cu probabilitatea minimă.

NUMOFSYMBOLS: numărul de simboluri ale imaginii */

{

int i;

i = NUMOFSYMBOLS-1;

while(nodes[i] = = NULL && i >= 0) i – -;

if (i<0) return (-310);

min[0]=i;

for (i = NUMOFSYMBOLS-1; i >= 0; i- -)

if(nodes[i]!=NULL)

if(nodes[i] >prob < nodes[min[0]] >prob) min[0] = i;

i = NUMOFSYMBOLS-1;

while((nodes[i] = = NULL && i>=0) i = = min[0]) i- -;

if (i<0) return (-310);

min[1]=i;

for (i =NUMOFSYMBOLS-1; i >= 0; i- -)

if(nodes[i]!=NULL && i!=min[0])

if(nodes[i] >prob < nodes[min[1]] >prob) min[1]=i;

return(0);

}

SPOINTER merge(nodes, min)

SPOINTER *nodes;

int min[2];

/* Procedura de fuzionare a două elemente ale ‘nodes’.

nodes: șir de elemente de tip SPOINTER.

min: tabela rezultat ce conține elementele care pointează poziția a două elemente ale ‘nodes’ cu probabilitate minimă.*/

{

SPOINTER p;

if (((p=(SPOINTER) _fmalloc(sizeof(struct symbol))) = = NULL)

return(NULL);

p >prob = nodes[min[0]] >prob + nodes[min[1]] >prob;

p >comp[0] = min[0] > min[1] ? nodes[min[1]] : nodes[min[0]];

p >comp[1] = min[0]>min[1] ? nodes[min[0]] : nodes[min[1]];

return(p);

}

int treeacces(root, stackpointer, stack, leaf, code)

SPOINTER root;

int *stackpointer;

char *stack;

struct symbol far*leaf;

unsigned char far* far * code;

/* Procedura de traversare în preordine a arborelui Huffman

root: rădăcina arborelui (variabila de intrare)

stackpointer: numărul de biți din stivă

stack: stiva de biți

leaf: șirul de noduri ale arborelui

code: tabel de șiruri ce conțin cuvinte de cod (var de ieșire)*/

{

int i, j;

if (root = = NULL) return(-1);

/* Dacă se atinge un nod, se reține cuvântul conținut în stiva în tabela de cod*/

if(root >comp[0] = = NULL)

{

i = (int)(root-leaf);

if((code[i] = (unsigned char far*)

_fmalloc((*stackpointer +1)*sizeof(char))) = = NULL) return(-1);

for(j = 0; j <=*stackpointer; j++) code[i][j] = stack[j];

}

/*în caz contrar accesează cei doi fii ai nodului curent*/

else

{

stack[*stackpointer] = 48;

(*stackpointer)++;

stack[*stackpointer] = 0;

i = treeacces(root->comp[0], stackpointer, stack, leaf, code);

if(i) return(i);/

stack[(*stackpointer)-1] = 49;

i = treeacces(root comp[1], stackpointer, stack, leaf, code);

if(i) return(i);

(*stackpointer)- -;

stack[*stackpoiter] = 0;

}

return(0);

}

2.2 Compresia LZW

2.2.1 Descriere generală

Metoda LZW, propusă de Lempel-Ziv și Welch este una dintre cele mai populare scheme de compresie și poate fi utilizată pentru compresia oricărui fișier binar de date. Este o metodă de compresie fără pierderi, rapidă și poate fi aplicată pentru imagini de orice lungime de biți.

Compresia LZW se bazează pe construcția unei tabele de cod care asociază șirurilor de biți întâlnite frecvent secvențe de cod la ieșire. Imaginea digitală este privită ca un șir binar unidimensional, la fel și imaginea codificată. Algoritmul obține șirul de ieșire și actualizează tabela de cod simultan. Astfel, registrul de cod se poate adapta trăsăturilor particulare ale imaginii ce urmează a fi comprimată. Tabela de cod poate cuprinde cel mult 4096 ( = 212) secvențe, și fiecare secvență de cod are o lungime de maxim 12 biți. Primele 256 cuvinte de cod [0,…,255] conțin numerele 0…255 și corespund șirului de caractere standard. Cuvântul de cod #256 conține un cod special, “clear code”, al cărui rol va fi descris ulterior. Cuvântul de cod #257 conține codul de sfârșit de informație (EOI) și se utilizează pentru a specifica sfârșitul unui fișier imagine. Cuvintele de cod de la #258 la #4095 codifică șiruri binare cu apariție frecventă în imagine. Primele 512 elemente ale tabelei se reprezintă prin 9 biți fiecare. Secvențele de cod de la #512 la #1023 se reprezintă prin 10 biți, de la #1024 la #2047 prin 11 biți, iar de la #2048 la #4095 prin 12 biți. Partea tabelei de la #258 la #4095 se construiește pe parcurs.

Procedura de compresie LZW:

STRING = caracterul de intrare

WHILE (există caractere de intrare) DO

CHARACTER = următorul caracter de intrare

IF STRING+CHARACTER este în tabela de cod THEN

STRING = STRING + CHARACTER

ELSE

produce codul pentru STRING

adaugă STRING + CHARACTER în tabela de cod

STRING = CHARACTER

ENDOFIF

ENDOFWHILE

se afișează codul pentru STRING

Procedura de decompresie:

Algoritmul de decompresie urmărește reconstituirea șirului de intrare pe baza codului obținut în urma aplicării algoritmului de compresie. Eficiența algoritmului LZW este datorată în mare măsură faptului că nu este necesară traversarea tabelei de cod pentru a obține codul de decompresie. Tabela se poate construi exact ca în procesul de compresie, pe baza șirului de intrare.

WHILE (există caractere de intrare) DO

citește NEW_CODE

IF (NEW_CODE nu este în tabelă) THEN

STRING = traducerea lui OLD_CODE

STRING = STRING + CHARACTER

ELSE

STRING = traducerea corespunzătoare lui NEW_CODE

ENDOFIF

reține STRING

CHARACTER = primul caracter din STRING

Adaugă OLD_CODE + CHARACTER tabelei

OLD_CODE = NEW_CODE

ENDOFWHILE

2.2.2 Implementare în C

Algoritmul de codificare este relativ simplu. El utilizează în principal 3 elemente: tabela de cod T, șirul prefix P și sirul curent S. Caracterele care se citesc la intrare se rețin în variabila C. Prezentăm în continuare algoritmul de compresie LZW:

#define TRUE 1

#define FALSE 0

typedef struct llink far*LPOINTER;

struct llink {

int n;

LPOINTER next;

};

Procedura lzw(.) realizează codificarea imaginii de intrare im prin algoritmul descris și obține fișierul de ieșire fw. Se impune să precizăm semnificația variabilelor folosite în cadrul procedurii: Ns reprezintă numărul de simboluri imagine (de regulă 256), Nc numărul de secvențe de cod (de regulă 4096), N și M numărul de linii, respectiv de coloane. c este poziția lui (P+C) în tabela de cod T, unde P reprezintă prefixul curent, iar C caracterul nou introdus (pixelul curent); oldc = poziția lui P în tabela de cod, Plength: lungimea prefixului curent P, Tlength: șirul lungimilor secvențelor de cod, codesize: numărul curent de biți pe pixel transmis la ieșire (variază de la 9 la 12), tablepointer este un pointer către ultima locație a tabelei de cod, iar llinks reprezintă un șir de pointeri către toate secvențele de cod care au același prefix.

int lzw(im,fw,Ns,Nc,N,M)

image im;

FILE *fw;

int Ns, Nc, N, M;

{

int i, j, h, tablepointer, c, oldc, maxcode, codesize, ENDOUT,

Plength, far* T, far *Tlength;

unsigned int RemainingBits, BitsRead, item;

LPOINTER *llinks;

unsigned char C;

/* maxcode: 2^(codesize) */

/* Se aloca memorie pentru tabela de cod */

if((T=(int far*)_fmalloc(Nc*sizeof(int))) = = NULL)

return(-10);

if((Tlength = (int far*)_fmalloc(Nc*sizeof(int))) = = NULL)

return(-10);

if((llinks = (LPOINTER *) malloc(Nc*sizeof(LPOINTER))) = = NULL)

return(-10);

/* Initializare */

tablepointer = INT_MAX;

oldc = INT_MAX;

RemainingBits = 16; BitsRead = 0;

item = 0;

ENDOUT=FALSE;

init_lzw (Ns, Nc, &tablepointer, T, Tlength, &Plength, &maxcode, &codesize, llinks);

/* Se transmite codul special “clear” la iesire */

send2output (fw, (unsigned int) Ns, codesize, &RemainingBits, &BitsRead, ENDOUT,

&item);

/* Ciclul principal al algoritmului LZW */

for(i=0; i<N; i++)

for(j=0; j<M; j++)

{C=im[i][j];

/* Verifica daca (P+C) este in T */

if((c=inT( T, Tlength, C, oldc, llinks))>=0)

{ /* Daca este, P=P+C. Incrementeaza Plength */

Plength++;

}

else

{ /* Daca nu, scrie oldc in fisierul de iesire, adauga P+C in T si modifica P=C */

send2output(fw, (unsigned int) oldc, codesize, &RemainingBits, &BitsRead,

ENDOUT, &item);

h=AddToTable(T, oldc, (int)C, Tlength, Plength, &tablepointer, &codesize,

&maxcode, Nc, llinks);

if(h = = -10) return(-10);

/* Verifica daca tabela de cod a fost stearsa */

if(h = = -340)

{ send2output (fw, (unsigned int)Ns, codesize, &RemainingBits, &BitsRead,

ENDOUT, &item);

init_lzw (Ns, Nc, &tablepointer, T, Tlength, &Plength, &maxcode,

&codesize, llinks);

}

c = (int)C;

Plenth = 1;

}

oldc=c;

}

/* Se transmite pozitia prefixului curent la iesire */

send2output(fw, (unsigned int) oldc, codesize, &RemainingBits, &BitsRead,

ENDOUT, &item);

/* Se transmite codul EOI iesirii */

send2output(fw, (unsigned int)(Ns+1), codesize, &RemainingBits, &BitsRead,

ENDOUT, &item);

/* Dupa completarea codului, se transmite ceea ce a ramas in ‘item’ la iesire */

ENDOUT = TRUE;

send2output(fw, 0, codesize, &RemainingBits, &BitsRead, ENDOUT, &item);

return(0);

}

Procedura de inițializare a tabelei de cod și a prefixului curent:

int init_lzw(Ns, Nc, tablepointer, T, Tlength, Plength, maxcode, codesize, llinks)

int Ns, Nc, *tablepointer, far* T, far* Tlength, *Plength, *maxcode, *codesize;

LPOINTER *llinks;

/*

maxcode: codul maxim care poate fi reprezentat cu ‘codesize’ biti

codesize: lungimea curenta (in biti) a codului citit

{

int i,j;

LPOINTER p;

/* Daca procedura este la primul apel introduce primele Ns+2 elemente ale tabelei */

if(*tablepointer = = INT_MAX)

for(i=0; i<Ns+1; i++)

{T[i] = i; Tlength[i] = 1;}

else

/* Daca procedura este apelata pentru reinitializare, se elibereaza toate elementele dupa cele Ns+2 */

for(i=0; i<Nc; i++)

for(;llinks[i]!=NULL;)

{ p = llinks[i] >next; _free(llinks[i]); llinks[i] = p;}

for(i=0; i<Nc; i++) llinks[i] = NULL;

*Plength = 0; *tablepointer = Ns+1;

*maxcode = Ns << 1; j = 0; i = *maxcode – 1;

while(i) { i = i >> 1; j + +; }

*codesize = j;

return(0);

}

Procedura inT() verifică dacă tabela de cod include combinația prefix+simbol (P+C):

int inT (T, Tlength, Plength, symbol, old, llinks)

int far* T, far* Tlength, old, Plength;

unsigned char symbol;

LPOINTER *llinks;

/* symbol: simbolul de intrare (C)

old: pozitia prefixului cuirent (P) in tabela de cod */

{ int i;

LPOINTER p;

if(old = = INT_MAX) return ((int)symbol);

/* Realizeaza cautarea descendentilor sirului care corespunde prefixului curent (T[old]) */

if(llinks[old]!=NULL)

{ for(p=llinks[old]; p!=NULL; p = p >next)

{ i = p > n;

if(Tlength[i] = = Plength+1)

if(T[i] = = (int) symbol) return(i);

}

}

return(-310);

}

Procedura AddToTable() adaugă T(pos)+c tabelei de cod la poziția indicată de tablepointer, unde pos reprezintă poziția șirului ce urmează a fi scris în T, iar c este codul ASCII al caracterului ce urmează a fi adăugat în T(pos).

int AddToTable (T, pos, c, Tlength, Plength, tablepointer, codesize, maxcode, Nc, llinks)

int far* T, pos, c, far* Tlength, Plength, *tablepointer, *codesize, *maxcode, Nc;

LPOINTER *llinks;

{ LPOINTER p;

(*tablepointer)++;

if (*tablepointer= =*maxcode) { (*maxcode)<<=1; (*codesize)++;}

T [*tablepointer]=c;

Tlength[*tablepointer]=Plength+1;

/*actualizarea legaturilor*/

if (llinks[pos]!=NULL)

{

for (p=llinks[pos]; p->next!=NULL; p=p->next);

if ((p->next=(LPOINTER)

_fmalloc(sizeof(struct llink)))= =NULL) return(-10);

p=p->next;

}

else

{

if ((llinks[pos]=(LPOINTER)

_fmalloc(sizeof(struct llink)))= =NULL) return(-10);

p=llinks[pos];

}

p->n=*tablepointer;

p->next=NULL;

if (*tablepointer= =Nc-1) return(-340);

return(0);

}

Procedura init_lzw() inițializează tabela de cod creînd primele 258 de intrări. Simbolul-prefix este nul. Procedura send2output() transmite informația codificată fișierului rezultat. Codul “clear” indică începutul unei noi imagini. După ce se efectuează aceste actualizări, algoritmul se derulează într-o manieră iterativă. La fiecare pas, se citește un bit de imagine și se creează șirul curent prin concatenarea șirului prefix cu noul bit de imagine (S = P+C). Dacă șirul curent este găsit în tabela de cod, prefixul se actualizează: P = S și procedura se repetă în scopul de a găsi cel mai lung șir din tabela de cod care este “similar” cu șirul curent. Dacă șirul curent nu se găsește în tabela de cod, rezultă că doar prefixul poate fi găsit în tabelă. Deci cuvântul de cod al prefixului se transmite șirului de ieșire (imaginea codificată). Se adaugă apoi șirul curent tabelei de cod și prefixul se reinițializează la valoarea pixelului nou introdus (P=C). Când se întâlnește caracterul de sfârșit de imagine, se transmite ieșirii codul de sfârșit de informație (EOI). Fiecare element al lui T poate avea un număr de “descendenți”, adică secvențe de cod cu același prefix obținute prin concatenarea unei secvențe de cod deja existente T[i] cu un caracter (de ex. o valoare de pixel). Astfel, tabela de cod T se organizează în formă arborescentă pentru a facilita căutarea. Această structură poate avea mai multe rădăcini. Căutarea șirului curent în tabela de cod T se realizează prin intermediul procedurii inT() și a șirului llinks. Fiecare element llinks[i] al acestui șir corespunde șirului T[i] din tabela de cod și conține o listă a pozițiilor descendenților lui T[i] în T (adică o listă a tuturor secvențelor de cod cu același prefix). Structura rezultată este exploatată în cadrul procedurii inT() în scopul măririi vitezei de căutare. Această structură permite memorarea doar a ultimului caracter a secvenței de cod corespunzătoare în T[i]. Întreaga secvență de cod asociată lui T[i] se obține urmând în llinks calea care conduce la T[i]. Procedura AddToTable() introduce elementele noi în tabela T și reactualizează descendenții elementelor lui T în șirul llinks. Se observă că tabela de cod se construiește progresiv și se poate adapta caracteristicilor imaginii. Dacă imaginea este fragmentată, fiecare fragment are propria sa tabelă de cod. Dacă dimensiunea tabelei de cod este 4096, se transimte codul Clear și se reinițializează tabela.

Decompresia LZW urmează exact procedeul invers. Nu este necesară transmiterea sau memorarea tabelei de cod, întrucât aceasta se va reconstitui progresiv pe parcursul decompresiei. Algoritmul începe cu procedura de inițializare. Se determină dimensiunea inițială de cod și se inițializează tabela de cod, introducând pentru început primele 258 de intrări.O procedură GetNextCode() citește următorul cuvânt de cod al imaginii codificate. Procedura începe prin a citi cuvinte de cod de 9 biți. Pe măsură ce tabela de cod se construiește progresiv, numărul de biți crește cu o unitate la dimensiunile 511, 1023 și 2047 ale tabelei. Dacă se întâlnește un cod Clear, tabela se reinițializează. Dacă șirul T[code] care corespunde noului cuvânt de cod code este găsit în tabelă, șirul corespunzător este transmis ieșirii, tabela de cod urmând a fi reactualizată prin adăugarea unei intrări formată din șirul T[old] corespunzător cuvântului de cod anterior, old, și primul caracter din T[code]. Dacă șirul care corespunde noului cuvânt de cod nu se află în tabelă, șirul de ieșire se obține prin concatenarea T[old] cu primul caracter al T[code] și va fi adăugat în tabela de cod. O procedură output_string() utilizează tabela T pentru a decodifica pixelii imaginii și a-i trimite în pozițiile corespunzătoare în buffer-ul imaginii de ieșire. Procedura se repetă până se întâlnește codul EOI. La decodificare nu este necesară o structură arborescentă pentru tabela de cod, ci o matrice de bytes.

2.3 Codificarea predictivă

2.3.1 Descrierea algoritmului

O modalitate alternativă de manipulare a redundanțelor informaționale constă în utilizarea predictibilității în vecinătăți locale. Fie f(n,m) nuanța asociată pixelului (n,m) și f(n+i, m+j), (i,j)A nuanțele corespunzătoare pixelilor vecinătății locale descrisă de mulțimea A. Datorită corelației spațiale relativ puternice care există între pixelii unei imagini, f(n,m) poate fi prezisă pe baza nuanțelor corespunzătore pixelilor vecini. Se definește astfel o regulă de predicție L, care este în general o funcție liniară a nuanțelor (intensităților) pixelilor corespunzători ferestrei A:

f(n,m) = L(f(n-i, m-j), (i,j)A, (i,j) (0,0) )

Presupunem că A are o formă care corespunde unui predictor cauzal. Dacă o astfel de fereastră scaneaza(parcurge) planul imaginii de la stânga la dreapta și de sus în jos, acoperă doar pixelii imaginii unei zone deja scanată. Astfel, putem realiza o predicție f(m,n) pe baza valorilor deja reconstituite ale pixelilor fr(n-i, m-j) deja traversați:

f(n,m) = L(fr(n-i, m-j), (i,j)A )

Se poate elabora o tehnică predictivă recursivă pe baza considerațiilor anterioare. Presupunem că am găsit o regulă optimă de predicție L. La fiecare pas, în locul intensității (nuanței) f(n,m) se va codifica eroarea de predicție, definită astfel:

e(n,m) = f(n,m) – f(n,m)

Dacă eq(n,m) reprezintă valoarea cuantificată și codificată a erorii e(n,m), f(n,m) se va putea reconstitui astfel:

fr(n,m) = L(fr(n-i, m-j), (i,j)A ) + eq(n,m)

Dacă predicția f(n,m) este bună, eroarea e(n,m) variază într-un interval relativ mic și se poate codifica cu ajutorul unei secvențe de cod relativ scurte. Prin urmare se obține o rată de compresie destul de bună. Transmiterea coeficienților de predicție și a erorii codificate este necesară în reconstituirea valorii f(n,m) pe baza relației de mai sus. Această schemă de codificare, numită DPCM (differential pulse code modulation) este ilustrată în figura 2.2 și este de regulă o metodă de compresie cu pierderi, datorită introducerii unui cuantificator în procesul de codificare. Se poate însa dezvolta și o schemă de compresie predictivă fără pierderi. Imaginea digitală este deja cuantificată într-un număr de niveluri de intensitate ( de regulă 0…255). Predictorul poate fi forțat să producă numere întregi la ieșire. În acest caz, semnalul de eroare e(n,m) poate fi codificat utilizând, de exemplu, metoda Huffman, fără a aplica vreun alt fel de cuantificare.

f(n,m) eq(n,m) eq(n,m) f(n,m)

+

– + f(n,m)

+

Fig 2.2 Ilustrare DPCM.

Performanța algoritmului depinde în mare măsură de regula (funcția) de predicție utilizată și de alegerea coeficienților săi. Cea mai simplă cale de abordare este de a aplica metoda DPCM la nivel unidimensional fiecărei linii a imaginii. Presupunem că linia de imagine f(n,m) notată f(m) pentru simplitate se poate exprima în felul următor (ca un proces staționar AR):

O alegere naturală a schemei de predicție este dată de regula:

Coeficienții funcției de predicție alcătuiesc vectorul a = [a(1),…,a(p)]T. Fereastra de predicție A conține pixelii reconstituiți {fr(m-1),…,fr(m-p)}. Eroarea cuantificată se transmite receptorului. Linia imaginii se reconstituie pe baza relației:

Coeficienții funcției de predicție sunt dați de soluția sistemului:

unde R(k) este funcția de autocorelație a f(m).

Această cale de abordare se poate extinde la nivel bidimensional. Se va obține următoarea schemă de predicție:

Coeficienții funcției de predicție pot fi aleși optim prin minimizarea erorii medii pătratice:

Minimizarea ne conduce la o mulțime de ecuații de forma:

,

unde R(k,l) reprezinta funcția de autocorelație a imaginii f(n,m). Soluția sistemului de mai sus dă coeficienții optimi ai modelului, a(i,j), (i,j)A. Odată determinați acești coeficienți, se poate obține și cuantifica eroarea imaginii: . Imaginea originală se poate reconstitui de către receptor pe baza relației:

2.3.2 Calculul coeficienților funcției de predicție.

Implementare în C.

Vom prezenta în continuare un algoritm de calcul al coeficienților funcției de predicție pentru modelul specificat mai sus și o fereastră de predicție de tip semiplan bidimensional asimetric (de forma celui ilustrat in fig.2.3), de dimensiune (LL+LR+1)K+LL+1 pixeli.

Coeficienții funcției de predicție a(i,j) se memorează într-un vector A de dimensiune (LL+LR+1)K+LL+1 astfel: A = [a(0,0),…,a(0,LL),a(1,-LR),…, a(1,LL),…,a(K,-LR),…,a(K,LL)]T.

K=2

LL=3 LR=1

Fig 2.3: Fereastra de predicție de tip semiplan bidimensional asimetric.

int arcoefficients(ima, N, M, K, LL, LR, A, Pu)

image ima;

int N, M, K, LL, LR;

float A[];

float *Pu;

{

/* Procedura pentru calculul coeficientilor AR bidimensionali

ima: imaginea de intrare

N,M: dimensiunea imaginii (coordonatele de final)

K, LL, LR: dimensiunea zonei suport a modelului AR

A: coeficienti AR ( variabile de iesire)

Pu: varianta procesului

int k, l, i, j;

int c, c1, c2;

float *AA;

float *BB;

float far * far* RR;

float corsample ( );

/* RR: matricea de corelatie

AA:vecorul coeficientilor */

RR=matf2((K+1)*(LL+LR+1), (K+1)*(LL+LR+1);

AA=(float *)malloc(((K+1)(LL+LR+1))*sizeof(float));

BB=(float *)malloc(((K+1)(LL+LR+1))*sizeof(float));

/* Calculul elementelor matricei de corelatie RR */

j=-1;

for(k=0; k<=k; k++)

for(1=0; 1<=LL+RR; 1++)

{j++; RR[0]=corsample(ima, ima, N, M, k, l);}

for(k=0; k<=K; k++)

{ j=k*(LL+LR+1);

for(l=1; 1>=LL+LR; 1++)

RR[l] [j]=corsample(ima, ima, N, M, k, -1);

for(I=1; I<=LL+LR; i++)

{ j=-1;

for(k=0; k<=K; k++)

{ j++;

for(l=1; l<=LL+LR; 1++)

{ j++; RR[i] [j]=RR[I-1] [j-1] ; }

}

}

c=(LL+LR+1);

for(c1=1; c1<=K; c1++)

for(c2=c1; c2<=K; c2++)

for(i=0; I<c; i ++)

for(j=0; j<c; j++)

RR[c1*c+i] [c2*c+j]=RR[(c1-1)*c+i] [c2-1)*c+j];

c=(K+1)*(LL+LR+1);

for(i=1; i<c; i++)

for(j=0; j<I; j++)

RR[i] [j]=RR[j] [i]

for(i=LR+1; i<c; i++)

BB[i]=-RR[i] [LR];

/* Se rezolva sistemul RR*AA=BB */

arsolve(RR, BB, AA, LR+1, c) ;

AA[LR]=1.0;

for(i=LR; i<c; i++) A[i-LR]=AA[i];

*Pu=0.0;

for(i=LR; I<c; i++)

Pu += RR[LR] [i]*AA[i];

mfreef2(RR, (K+1)*(LL+LR+1)); free(AA); free(BB);

return(0);

}

arsolve(sa, sb, ss, s1, sn)

float far* far* sa;

float *sb;

float *ss;

int s1, sn;

{ int k, k1, k2, reg;

float p;

for(k=s1; k1<sn-1; k++)

{ reg=k;

for(k1=k+1; k1<sn; k1++)

if(fabs((double)sa[k1] [k])>fabs((double)sa[reg[ [k] ))

reg=k1;

if( reg !=k )

{ for(k2=k; k2<sn; k2++)

{ p=sa[k] [k2]; sa[k] [k2]=sa[reg] [k2];

sa[reg] [k2]=p;

}

p=sb[k]; sb[k]=sb[reg]; sb[reg]=p;

for(k1=k+1; k1<sn; k1++)

{ for(k2=k+1; k2<sn; k2++)

sa[k1] [k2]=sa[k1] [k2]-sa[k] [k2]*sa[k1] [k] / sa[k] [k];

sb[k1]=sb[k1]-sa[k1] [k] / sa[k] [k] *sb[k];

}

for(k1=k+1; k1<sn; k1++) sa[k1] [k]=0.0;

}

ss[sn-1]=sb[sn-1] / sa[sn-1] [sn-1];

for(k=0; k<sn-1-s1; k++)

{ k1=sn-2-k;

p=sb[k1];

for(k2=sn-1-k; k2<sn; k2++) p=p-sas[k1] [k2]*ss[k2];

ss[k1]=p / sa[k1] [k1];

}

}

float corsample(im1, im2, N, M, k, l)

image im1;

image im2;

int N, M;

int k, l;

{

int y, z;

float sum;

sum=0.0;

for(y=(k<0) ? –k : 0 ; (k<0 && y<N) || (k>0= && y+k<N) ; y++)

for(x=(1<0) ? –1 : 0 ; (1<0 && x<M) || (1<=0 && x+1<M ; x++)

sum +=(unsigned int)im1[y+k] [x+1]*(unsigned int)im2[y] [x];

sum / =(float)N*(float)M;

return (sum);

}

Algoritmul prezentat utilizează procedura corsample() pentru calculul funcției de autocorelație R(k,l) a imaginii care trebuie modelată. Ecuațiile corespunzătoare se scriu în forma matriceala RA=B, sistem rezolvat de procedura arsolve() care calculează coeficienții modelului.

De multe ori este suficientă utilizarea ferestrelor mici de predicție:

.Coeficienții modelului ai, i =1,4 și varianța 2=E[2(n,m)] se obțin rezolvând sistemul:

2=R(0,0) – a1R(1,0) – a2R(0,1) – a3R(1,1) – a4R(1,-1).

Coeficienții de autocorelație R(i,j) se pot estima pe baza relației:

Codificarea predictivă DPCM este o tehnică simplă de compresie a imaginii și poate fi implementată relativ ușor. Se obțin rate de compresie moderate și are dezavantajul de a fi sensibilă la propagarea erorilor de transmisie prin canal.

2.4 Codificarea transformatei

2.4.1 Descriere generală

O altă metodă de codificare a imaginilor digitale constă în utilizarea transformatelor de imagine în scopul de a concentra conținutul informațional al imaginii într-un număr redus de coeficienți ai transformatei. Dacă se obține o condensare a informației, un număr mare de coeficienți ai transformatei pot fi eliminați, restul urmând a fi codificați prin intermediul unui cod de lungime variabilă. Rezultă astfel o rată de compresie destul de mare. La decodificarea imaginii se utilizează transformata inversă. Schema de codificare a transformatei este ilustrată in figura 2.4. Considerăm matricea f reprezentând o imagine (sau un bloc de imagine) de dimensiune NM. Imaginea transformată F este dată de: F = Af , unde A este matricea de transformare. Transformarea inversă se definește astfel: f = A-1F. O transformată este unitară dacă satisface proprietatea: AA*T=ATA*=I. O transformată unitară satisface proprietatea de conservare a informației:

(2.4.1)

O imagine f(x,y) de dimensiune nn se poate exprima în funcție de transformata sa bidimensională A(u,v) astfel:

(2.4.2) (1) , unde x,y=0,1,…,n-1

(1) [Gonzales,Woods – “Digital Image Processing”,pag 377]

Relația de mai sus se poate scrie:

(2.4.3),

unde F este matricea de dimensiune nn ce conține pixelii lui f(x,y), iar .

Prin urmare F se poate scrie ca o combinație liniară de n2 matrici de dimensiune nn (Huv), care constituie baza de imagini elementare ale transformatei.

În practică, de cele mai multe ori conținutul esențial de informație (energia semnalului) este inegal distribuit în coeficienții transformatei. Coeficientul DC și o serie de alți coeficienți “de frecvență joasă” F(k), 1 k K <<L tind să concentreze cea mai mare parte din conținutul informațional al imaginii. Astfel, mulți coeficienți de transformare (de exemplu F(k), k>K) pot fi eliminați fără a rezulta pierderi semnificative de informație.

Se definește funcția mască (șablon) a coeficienților transformatei:

Se obține astfel o aproximare a lui F din expresia:

(2.4.4)

Observație: m a fost introdus pentru a elimina imaginile de bază care influențează cel mai puțin expresia (2.4.3).

Eroarea medie pătratică dintre (sub)imaginea F și aproximarea sa este:

unde s-a notat prin norma matricei , iar este varianța coeficientului în punctul de transformare (u,v).

Coeficienților rămasș li se va aloca un număr variabil de biți nk, 1 k K, astfel încât numărul mediu de biți pe pixel să fie egal cu un număr B predefinit. Odată realizată alocarea de biți, urmează a se efectua cuantificarea coeficienților F(k), 1 k K. Se pot construi K cuantificatori diferiți, care urmează a fi aplicați coeficienților de transformare, rezultând imaginea (sau blocul de imagine) codificat/ă. Procesul de decodificare este foarte simplu: Transformata inversă A-1 se aplică vectorului coeficienților obținându-se astfel o estimare a imaginii originale f.

2.4.2 Selecția transformatei

În procesul de construire a unui algoritm eficient de codificare a transformatei intervin câteva probleme. Prima se referă la alegerea transformatei ce urmează a fi aplicată. Există mai multe alternative: transformata Fourier discretă (DFT), transformata Walsh-Hadamard (WHT), transformata cosinusului discretă (DCT), transformata Karhunen-Loeve (KLT) etc. Rezultatele experimentale au demonstrat superioritatea abilității de comprimare a DCT față de cea a DFT sau WHT, transformarea optimă în acest sens fiind KLT, care minimizează eroarea medie pătratică pentru orice imagine de intrare și pentru orice număr de coeficienți reținuți. ([Kramer,Mathews[1956]]). Întrucât KLT conține dependență în date, obținerea bazei de imagini elementare KLT este o sarcină oarecum dificilă, motiv pentru care KLT este arareori utilizată în practică. De aceea, cele mai multe sisteme de codificare ( inclusiv standardul JPEG de compresie al CCITT) se bazează pe DCT, care asigură un compromis rezonabil între capacitatea de comprimare și complexitatea computațională. DCT are și avantajul de a evita vizualizarea granițelor dintre subimagini, comparativ cu alte transformate sinusoidale, cum ar fi DFT. Întrucât DFT conține puncte de discontinuitate, când coeficienții sunt trunchiați și cuantificați, apare așa numitul efect de grilaj, datorită faptului că pixelii ce delimitează marginile subimaginilor sunt caracterizați de valorile medii ale discontinuităților apărute în punctele de graniță. DCT reduce acest efect, întrucât nu conține discontinuități în punctele de delimitare.

2.4.3 Selecția dimensiunii subimaginilor

Un alt factor semnificativ care determină erorile de codificare a transformatei și complexitatea computațională este dimensiunea subimaginilor. Nu se recomandă aplicarea unei singure transformate întregii imagini datorită variațiilor statistice ce intervin în diferite regiuni ale imaginii. Imaginea se împarte într-un număr de blocuri ce urmează a fi codificate independent. În cele mai multe aplicații, imaginile se subdivid astfel încât să reducă corelația (redundanța) dintre subimaginile adiacente la un nivel acceptabil și astfel încât n să fie o putere întreagă a lui 2, unde n este dimensiunea unei subimagini. În general, atât nivelul de compresie, cât și complexitatea computațională cresc direct proporțional cu dimensiunea subimaginii. Dimensiunea tipică de bloc este 88 sau 1616.

2.4.4 Alocarea de biți

O altă problemă se referă la determinarea unui mod eficient de alocare de biți. Fie nk, k=1,…,L numărul de biți alocat fiecărui coeficient F(k), k=1,…,L. Dacă nk =0 rezultă că F(k) a fost eliminat. Numărul mediu de biți/pixel va fi:

(2.4.5)

Distorsia medie datorată cuantificării coeficienților este dată de relația:

(2.4.6)

unde Q[.] reprezintă cuantificatorul, iar este varianța coeficientului F(k). Funcția de distorsie a cuantificatorului q(nk) este o funcție descrescătoare pentru care q(0)=1 și q()=0. Scopul procedurii de alocare de biți este minimizarea erorii medii pătratice (2.4.6) sub constrângerea (2.4.5). O alegere rezonabilă a numărului de biți este dată de relația:

(2.4.4)

Pentru a obține lungimi întregi de biți, relația (2.4.4) se rotunjește.

După ce s-a obținut alocarea de biți, se construiesc cuantificatorii optimi pentru fiecare coeficient de transformare. Este necesară determinarea densității de probabilitate a coeficienților. Pentru modelarea densității de probabilitate a coeficienților DC se utilizează o distribuție Rayleigh. Pentru restul coeficienților se utilizează distribuții Gauss sau Laplace. În practică, pentru coeficienții DC se aplică o cuantificare uniformă și se utilizează o lungime maximă de biți (de regulă n1=8). Toți ceilalți coeficienți F(k) se împart prin varianțele corespunzătoare în scopul de a obține coeficienți de varianță unitară. Se construiește câte un cuantificator pentru fiecare lungime de biți n, 1nn1. Dacă lungimea maximă de biți este 8, sunt necesari 7 cuantificatori, care urmează a fi aplicați coeficienților corespunzători. Coeficienții cuantificați se codifică apoi prin metoda Huffman.

Decodificarea este foarte simplă. Inițial se realizează o decodificare Huffman. Coeficienții de transformare sunt dați de:

Blocul de imagine se obține prin aplicarea transformatei inverse:.

…

Fig. 2.4: Codificarea/decodificarea transformatei.

2.5 Codificarea secvențelor de imagini

O gamă largă de imagini ce urmează a fi comprimate și procesate se găsesc sub formă de secvențe (de exemplu, imaginile TV). Acestea sunt caracterizate de prezența, alături de cele două coordonate spațiale de bază, a unei a treia coordonate, ce determină caracterul de secvență și care cel mai adesea este timpul sau spectrul.

2.5.1Codificarea imaginilor TV prin compensarea mișcării

Datorită necesității transmiterii în timp real a imaginilor TV, se preferă metoda predictivă. Codificarea imaginilor TV prin compensarea mișcării reprezintă o abordare adaptativă, bazată pe următoarele strategii:

Fiecare cadru se împarte în două părți: una statică, ce reprezintă fundalul (care se menține constant de la o secvență la alta), iar cealaltă dinamică (ceea ce variază).

Se transmit informațiile referitoare la regiunile de animație, și anume:

adresele pixelilor din zona de animație

informații de actualizare a nivelurilor de gri asociate pixelilor din zona de animație.

Se utilizează un frame buffer pentru reglarea ratei de codificare în funcție de rata constantă a canalului (întrucât informațiile referitoare la zonele de animație sunt dependente de timp, rata de codificare variază în timp).

Estimarea recursivă a deplasării

Algoritmul, propus de Netraveli și Robbins, în urma unor iterații efectuate pixel cu pixel (pasul de iterație se poate realiza și asupra unui bloc mic de pixeli), se reia estimarea de deplasare a fiecărui pixel din zona de animație, aplicând următoarea formulă de actualizare:

Ďi = Ďi-1 + Ui

unde Ďi este estimarea deplasării la iterația i, iar Ui este actualizarea lui Ďi-1 la Ďi . Fie x reprezentarea coordonatei spațiale, iar f(x,t-) și f(x,t) nivelurile de gri ale două cadre succesive în locația x la momentul t. Se definește diferența deplasării în cadru(DFD) astfel:

DFD(x, Ďi-1) = f(x,t) – f(x – Ďi-1,t – )

În cazul în care estimarea de deplasare Ďi poate fi scrisă sub formă fracționară, evaluarea formulei precedente va utiliza interpolarea în spațiul discret bidimensional. Presupunem că predicția asociată pixelului din poziția xa este caracterizată de deplasarea Ďi-1 și nivelul de gri f(xa – Ďi-1,t -), iar eroarea de predicție este DFD(xa ,Ďi-1); la următorul pas de iterație, eroarea de estimare va fi DFD(xa ,Ďi) și DFD(xa ,Ďi)DFD(xa ,Ďi-1).

Vom avea: Ďi = Ďi-1 – (/2)D[DFD(xa ,Ďi-1)]2

= Ďi-1 – DFD(xa ,Ďi-1) D DFD(xa ,Ďi-1) , unde este o constantă pozitivă mică și D este gradientul relativ la deplasarea D. Rezultă:

D [DFD(xa ,Ďi-1)] = f(xa – Ďi-1, t -), prin urmare:

Ďi = Ďi-1 – DFD(xa ,Ďi-1) f(xa – Ďi-1, t -).

Pe baza acestui algoritm recursiv, a fost construit sistemul de codificare a imaginilor TV prin compensarea mișcărilor a cărui diagramă este prezentată simplificat în imaginea (2.5). Inițial se calculează predicția de compensare a mișcării cu ajutorul estimatorului de deplasare. Pe baza diferenței dintre cadre, segmentorul controlează estimatorul de deplasare și predictorul de compensare a mișcării prin intermediul comutatoarelor A, respectiv B, asigurându-le (restrângându-le) activitatea doar asupra zonelor de animație. Transmiterea erorii de predicție este controlată de asemenea de segmentor prin intermediul comutatorului C. Clasificarea zonelor de animație se realizează pe baza următoarelor formule:

1.FDIF(x)>T2

sau

2.FDIF(x)>T1

și FDIF>T1 în punctele a, b, c sau d și FDIF>T1 în punctele A, B, C sau D,

unde FDIF este o abreviere pentru diferența de cadru, iar T1 și T2 reprezintă 2 praguri, T2T1. Valorile tipice pentru T1 si T2 pentru cazul caracterizat de 256 niveluri de gri sunt 1, respectiv 3.

În cadrul zonelor de animație, există o regiune compensabilă, în care predicția de compensare a mișcării este suficient de fidelă astfel încât nu mai este necesară transmiterea unor informații de actualizare, și o regiune necompensabilă, pentru care se transmite eroarea de predicție. Clasificarea se realizează pe baza următoarelor reguli:

1.Un pixel din zona de animație se consideră a fi necompensabil dacă amplitudinea erorii de predicție este mai mare decat 3 din 255.

2.Pixelii compensabili cu deplasări mai mici sau egale cu 3 se consideră de asemenea ca fiind pixeli necompensabili.

+ C

Predictia de compensare

a miscarii

Fig 2.5: Diagrama unui codificator de compensare a mișcării

2.6 Codificarea imaginilor color

O imagine color se reprezintă prin sinteza unor imagini independente ce conțin variații de nuanțe de roșu (R), verde (G), respectiv albastru (B). Dacă imaginile RGB se codifică separat, erorile de codificare și de transmitere vor afecta calitatea vizuală a imaginii color reconstituite. În urma analizei modelului uman de percepție a culorilor, Frei și Baxter au propus un model bazat pe o transformare neliniară, ce constă în principal din trei operații. Primele două operații se definesc matematic în felul următor:

A treia operație este reprezentată prin 3 filte de frecvență (fig.2.6). Rezultatele practice au demonstrat că distorsia obținută este relativ mică conform criteriilor subiective de fidelitate.

h2 h1

h3

1.0 10

Fig.2.6: Funcțiile filtru de frecvență ale modelului de percepție color