Reprezentarea imaginii in format necomprimat

Reprezentarea imaginii in format necomprimat

O imagine se reprezinta ca o matrice de puncte (de obicei de forma patrata), fiecare punct fiind caracterizat de o culoare. De exemplu, pentru imaginea urmatoare:se poate evidentia acest lucru daca se mareste o sectiune a imaginii astfel incit matricea de puncte sa devina vizibilaPentru a reprezenta o astfel de imagine trebuie sa se utilizeze un mod de reprezentare numeric al culorii. Pentru aceasta se porneste de la observata ca orice culoare poate fi obtinuta prin amestecul in diferite proportii a trei culori de baza (culori primare). In practica se utilizeaza ROSU (R), VERDE (G) si ALBASTRU (B).

In tabelul urmator este prezentata modalitatea de obtinere a citorva culori:

Intensitatea luminoasa a unei culori primare poate fi reprezentata numeric sub forma unui intreg de 8 biti, valoarea 0 corespunzind intensitatii nule iar cea maxima (255) intensitatii maxime. In acest fel, o culoare va fi reprezentata numeric printr-un triplet de intregi pe 8 biti (R,G,B). De exemplu culoarea GALBEN va avea o reprezentare de forma (255 ).

In aceste conditii imaginea se reprezinta sub forma unei matrici IM(Nx,Ny) unde Nx numarul de puncte pe orizontala si Ny nuamrul de puncte pe verticala iar elementele matricii sint tripleti de intregi pe 8 biti de tip (R,G,B).

Principiul compresiei (metode de tip DCT)

Metoda prezentata sta la baza formatului JPEG si este o metoda din categoria celor cu pierdere de informatie. Aceasta inseamna ca prin procesul de compresie imaginea va fi alterata insa intr-un mod aproape insesizabil, pierderea de informatie se referindu-se la acele componente care nu sint foarte importante in descrierea imaginii.

Compresia imaginii presupune citeva etape de prelucrare si anume:

- Transformarea din reprezentarea (R,G,B) in reprezentarea (Y,U,V)

In procedurile de compresie a imaginii se prefera o reprezentare a culorii diferita de cea normala (R,G,B) si anume reprezentarea (Y,U,V). Si in acest caz, o culoare este descrisa de un triplet de intregi ale caror valori sint date de urmatoarele relatii:

Valorile componentelor Y, U si V sint cuprinse intre -128 si 127. Utilitatea acestei reprezentari echivalente se poate evidentia in exemplul urmator in care sint prezentate descompunerile in forma (R,G,B) respectiv (Y,U,V) ale unei imagini:

Analizind acest exemplu pot face citeva observatii importante si anume

• componenta Y corespunde unei imagini alb-negru;
• componentele U si V contin mult mai putine detalii si prezinta un contrast mult mai redus.

Absenta detaliilor si contrastul scazut al componentelor U si V permit subesantionarea acestora de tipul 2x2 puncte -> 1 punct fara ca sa se piarda prea multa informatie. Modul de realizare al subesantionarii este inlocuirea blocurilor de 2x2 puncte cu un singur punct care are intensitatea egala cu media celor 4. In aceste conditii imaginea va fi descrisa de:

Prin aceste operatii se realizeaza o prima compresie 2:1. Astfel reprezentarea (R,G,B) pentru imaginea din exemplu cu rezolutia de 320x240 puncte necesita 3 componente a cite 320x240=76800 elemente adica un total de 230400 elemente (octeti). Reprezentarea (Y,U',V') necesita 320x240=76800 elemente pentru Y si 160*120=19200 elemente pentru U' si V' adica un total de 115200 elemente (octeti).

- Descompunerea in blocuri

Procedura de compresie se aplica unor blocuri de imagine de 8x8 puncte. In acest scop, cele trei componente Y, U' si V' sint descompuse in blocuri de acesta dimensiune. Datorita rezolutiei reduse in urma subesantionarii rezulta ca la 4 (2x2) blocuri ale componentei Y corespund cite un singur bloc al componentelor U' respectiv V'.

In cazul formatului JPEG blocurile de imagine din cele trei componente sint prelucrate intretesut. Pentru o numerotare a blocurilor conform figurii urmatoare:

ordinea prelucrarii acestora va fi Y1,Y2,Y3,Y4,U1,V1, , Y5,Y6,Y7,Y8,U2,V2, 

Fiecare bloc este prelucrat (comprimat) utilizind aceeasi procedura care presupune urmatoarele operatii:

- Aplicarea trasformatei cosinus discrete

Transformata cosinus discreta aplicata unei matrici S de 8x8 elemente conduce la obtinerea unei matrici T cu aceleasi dimensiuni, valorile elementelor fiind date de relatia:

Efectul acestei transformari se poate evidentia pe urmatorul exemplu in care se considera un bloc extras din componenta Y:

Elementele blocului selectat (matricea S) au valorile:

In urma aplicarii transformatei cosinus discrete se obtine matricea T cu urmatoarele valori:

Se poate observa ca elementele acestei matrici au valorile mari concentrate in coltul din stinga-sus restul fiind valori mici aproape nule. Explicatia acestui fenomen este data de faptul ca transformata cosinus discreta realizeaza o descompunere 'in frecventa'. Astfel coeficientii din coltul din stinga-sus corespund frecventelor joase - variatii lente de intensitate intre pixeli iar pe masura ce se avanseaza catre coltul din dreapta-jos coeficientii corespund frecventelor inalte - variatii rapide de intensitate date de detaliile fine din imagine. In general intr-o imagine reala frecventele inalte au o pondere mai redusa decit cele joase ceea ce explica valorile obtinute in urma transformarii.

- Cuantizarea matricii transformate

Operatia de cuantizare este singura in care se pierde informatie. Prin cuantizare se intelege impartirea element cu element a matricii T cu o matrice de cuantizare Q cu retinerea doar a partii intregi rezultind o matrice C definita astfel:

Utilizind o matrice de cuantizare Q cu valorile:

se obtine o matrice C avind urmatoarele valori:

Se observa ca in urma cuantizarii in matricea C fenomenul de concentrare a valorilor mari in coltul din stinga-sus si predominata valorilor mici (chiar zero) in rest este mult mai accentuata.

Pierderea de informatie de datoreaza realizarii impartirii cu retinerea doar a partii intregi a rezultatelor. In acest fel valorile pierd din precizie (cele mici transformindu-se in zero). Efectul acestei pierderi insa nu este sesizabil deoarece dupa cum se observa pierderile cele mai mari sint concentrate la nivelul coeficientilor de inalta frecventa care au pondere redusa in imagine si care oricum corespunzind detaliilor fine sint mai putin observabile se catre ochiul uman.

Rolul operatiei de cuantizare este acela de a obtine cit mai multe valori nule sau mici acestea avind avantajul unei codificari eficiente realizata ulterior. Transformata cosinus discreta ofera posibilitatea de a realiza aceasta operatie astfel incit efectul pierderii de informatie sa fie cit mai redus.

- Codificarea elementelor din matrice

Elementele matricii C trebuiesc codificate. In algoritmul de compresie JPEG sint utilizate doua proceduri diferite. Prima procedura este utilizata pentru codificarea elementului TQ(0,0) (cel din coltul din stinga sus al matricii cuantizate) numit coeficient DC, a doua procedura utilizindu-se pentru codificarea celorlalti 63 de coeficienti numiti coeficienti AC.

Codificarea coeficientilor DC

Coeficientii DC sint codificati utilizind un predictor simplu. Astfel in loc de valoarea coeficientului se codifica diferenta intre aceasta si valoarea coeficientului DC corespunzatoare blocului de 8x8 puncte anterior din aceeasi categorie (Y, U sau V).

Aceasta valoare (diferenta) este codificata utilizind urmatoarea procedura: mai intii se clasifica valoarea acestei diferenta intr-o clasa de valori. Modul de clasificare este prezentat in tabelul urmator:

Codul unei valori se obtine prin concatenarea unui cod pentru clasa din care face parte si un cod corespunzator valorii acesteia. Codul clasei (conform cu recomandarea T.81) este indicat in tabela DCL[] - pentru diferentele provenind din componenta Y respectiv DCC[] - pentru diferentele provenind din componentele U si V. Aceste tabele sint prezentate in fisierul JPEG.C care contine scheletul programului. Structura tabelelor cu codurile claselor este:

typedef structcoduri;

unde nb este numarul de biti din care este format codul iar cod[] este codul propriu zis reprezentat din sirul de nb biti 0 sau 1. In tabele sint utilizate codurile ASCII ale lui '0' si '1', in fisierul JPEG insa trebuie scrisi biti 0 sau 1.
De exemplu pentru un cod de clasa 5 (SSSS=0101) citind in tabela elementul DCL[5] se gaseste codul de 5 biti 11110.

Dupa acest cod de clasa trebuie adaugata valoarea coeficientului. Acesta consta din cei mai putini semnificativi nb biti din valoarea diferentei in cazul valorilor pozitive sau din valoarea diferentei minus 1 daca aceasta este negativa.

De exemplu, daca valoarea diferentei care trebuie codificata este 21 si apartine componentei Y (deci se va utiliza tabela DCL[]) avem un cod de clasa 5 pentru care codul este 11110. Valoarea este pozitiva, deci la acest cod trebuie adaugati cei mai putini semnificativi 5 biti ai acesteia. Valoarea 21 se reprezinta in binar 10101 (adica pe 5 biti cit indica clasa), deci codul complet va fi 1111010101.

Alt exemplu, valoarea care trebuie codificata este -21. In acest caz clasa este aceeasi diferenta fiind valoarea negativa a coeficientului. Acesta este reprezentat in complement fata de 2 (pe 16 biti de exemplu) avind reprezentarea 1111111111101011. Cei 5 biti care se adauga la codul clasei vor fi cei mai putin semnificativi 5 biti ai acestei valori din care se scade 1 adica 01010. Codul complet va fi in acest caz 1111001010.

Codificarea coeficientilor AC

Ordinea in care este parcursa matricea in vederea codificarii coeficientilor de tip AC se alege in asa fel incit sa se profite cit mai bine de distributia valorilor ceficientilor. Se urmareste gruparea valorilor nule in siruri cit mai lungi deoarece acest fapt permite o codificare cit mai eficienta (compresie maxima).

Deoarece valorile diferite de zero sint concentrate intr-un colt al matricii o parcurgere normala de tipul linie cu linie nu este eficienta. De aceea se prefera o parcurgere in zig-zag, ordinea de extragere a elementelor din matrice fiind prezentata in figura urmatoare:

Pentru matricea C din exemplul de mai sus coeficientii extrasi in acesta ordine se prezinta astfel:

-50, 57, -35, 32, 33, 2, -2, 6, -6, 5, 0, 2, 0, -4, 2, -1, 0, -2, -7, 1, 0, 0, 0, -3, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Se observa modul in care se grupeaza valorile nule catre sfirsitul sirului. De acest fapt se va tine cont in urmatoarea etapa in care se realizeaza codificarea acestor elemente.

Fiecare coeficient este un numar intreg care poate varia intre -1023 si +1023 (valorile sint obtinute analizind cazul cel mai defavorabil si modul in care lucreaza transformata cosinus discreta).

In cazul codificarii 'normale' fiecare din acesti coeficienti poate fi reprezentat pe 11 biti (1 bit de semn + 10 biti valoare). Acest mod de codificare practic duce la o reprezentare pe mai multi biti decit in cazul imaginii necomprimate (se folosesc 11 biti pentru un coeficient in loc de 8 biti pentru un pixel). Din acest motiv, in cazul algoritmului de compresie JPEG se procedeaza la o alta modalitate de codificare.

In acest caz se asociaza un cod combinatiei dintre numarul de valori nule (daca exista) care preced un element diferit de zero si valoarea acestuia din urma. Prectic se codifica perechi (Numar_zerouri,Valoare) in locul fiecarui coeficient in parte. In realitate din considerente de reducere a numarului de combinatii posibile numarul de zerouri se limiteaza la 16. In cazul in care exista mai mult de 16 elemente nule se emit coduri speciale (ZRL) care semnifica 16 zerori care nu sint urmate de un element diferit de zero. De exemplu 18 zeroruri urmate de un element cu valoarea -21 se vor codifica printr-un ZRL urmat de codul corespunzator perechii (2,-21).

Deasemenea in cazul in care dintr-un anumit punct al sirului pina la sfirsitul acestuia nu mai exista nici un element diferit de zero se emite un alt cod special (EOB) in locul tuturor valorilor nule ramase.

Tinind cont de aceste observatii, pentru exemplul de mai sus rezulta urmatorul set de coduri care trebuiesc generate:

• EOB

Si in acest caz se clasifica simbolurile. De data aceasta clasa unui simbol este formata din combinarea a doua elemente. Primul element este clasa valorii coeficientului diferit de zero (SSSS) obtinuta similar ca in cazul coeficientilor DC adica:

Al doilea element este dat de numarul de zerouri - valoare intre 0 si 15 care pate fi reprezentata pe 4 biti (RRRR).

Codul corespunzator acestei clase combinate este dat in tabelele ACL[] - pentru elementele provenind din componenta Y respectiv ACC[] pentru elementele provenind dincomponentele U si V.

Pozitia codului in tabela pentru un simbol dat se calculeaza cu relatia INDEX=16xRRRR+SSSS. Se observa rezervarea codurilor cu RRRR=0 si SSSS=0 pentru simbolul special EOB si al celui cu RRRR=15 si SSSS=0 pentru simbolul special ZRL.

De exemplu, se doreste codificarea simbolului (1,-4) din sirul de mai sus. Pentru acesta se determina SSSS ca fiind 3 si RRRR ca fiind 1. Indexul in tabela este 16x1+3=19. Deoarece valoarea apartine componentei Y se va utiliza tabela ACL[] deci codul clasei este reprezentat pe 7 biti adica 1111001.

La fel ca in cazul coeficientilor DC, acest cod al clasei trebuie sa fie urmat de valoarea coeficientului diferit de zero (utilizind aceeasi procedura). Pentru exemplul analizat valoarea acestuia este -4 (1111111111111100 in complement fata de 2), valoarea minus 1 este 1111111111111011, deci se vor adauga cei mai putin semnificativi 3 biti adica 011. Codul complet al simbolului (1,-4) este 1111001011.

Informatii suplimentare

Pentru informatii suplimentare se poate consulta recomandarea T.81 a CCITT care descrie amanuntit standardul de compresie si reprezentare a imaginilor in format JPEG.

Deoarece standardul este deosebit de vast, recomand pentru inceput a se citi paginile 13-15, 24-30 si 87-91 in care este descris modul de lucru in cazul stndard (format secvential, cu pierderi, codificare Huffman), mod de lucru descris si in materialul de mai sus. Detalii referitoare la formatul propriu-zis pot fi gasite la paginile 31-45.

Structura programului

Pentru a usura realizarea programului de compresie cerut in cadrul proiectului am realizat un schelet al acestuia JPEG.C. In acest fisier sint scrise procedurile de citire a imaginii din fisierul de tip bitmap (.BMP), de deschidere respectiv scriere antet fisier JPEG cit si proceduri de uz general.

In continuare este descrisa structura acestui fisier sursa:

• functia main - citeste de la consola numele fisierului BMP cit si calitatea dorita a compresiei (0, 1 sau 2). Apeleaza apoi cu acesti parametrii comprima(nume_fisiser,calitate);
• functia comprima(nume_fisier,calitate) - deschide fisierul BMP, citeste din antetul acestuia dimensiunile imaginii, creaza fisierul JPEG scriind antetul acestuia apoi extrage din fisierul BMP benzi de imagine orizontale cu inaltimea de 16 pixeli care sint apoi trimise spre compresie functiei comprima_banda(banda_imagine,dim_x,fisier_jpeg,calitate);
• comprima_banda(banda_imagine,dim_x,fisier_jpeg,calitate) - extrage blocurile de imagine de 8x8 pixeli din banda de imagine realizind conversia de reprezentare a culorii din RGB in YUV cit si subesantionarea componentelor U si V. Pentru fiecare bloc extras apeleaza functia comprima_bloc(fisier_jpeg,tip_bloc,calitate) care va realiza compresia propriu zisa a acestor blocuri de imagine;
• comprima_bloc(fisier_jpeg,tip_bloc,calitate) - aceasta este functia care trebuie scrisa in cadrul proiectului. Aici trebuie implementate transformata cosinus discreta aplicata blocului, cuantizarea elementelor si codificarea acestora conform cu algoritmul prezentat mai sus. Matricea S (blocul de imagine) este intr-o matrice

float s[8][8];

completata de catre functia de compresie banda. Parametrii functiei sint: fisier_jpeg - handler pentru fisierul JPEG creat, tip_bloc - tipul componentei din care provine blocul (0=Y, 1=U, 2=V), calitate - calitatea impusa compresiei (0=ridicata, 1=normala, 2=scazuta). Acesti parametrii vor fi utilizati pentru selectarea tabelelor utilizate in compresie.

Procedurile de uz general sint:

• scrie_bit(fisier,bit) - realizeaza scrierea unui bit cu valoarea indicata de parametrul bit in fisierul indicat de fisier. Parametrul bit este reprezentat in ASCII, deci va fi '0' pentru 0 respectiv '1' pentru 1.
• amp(x) - este o functie care determina clasa SSSS pentru o valoare x data.

Tabele utilizate:

• tabela de ordonare in zig-zag - este o matrice de intregi zz[8][8]. Elementul zz[i][j] reprezinta pozitia in sirul ordonat a elementului [i][j];
• tabele de cuantizare - sint 6 tabele predefinite 3 pentru cuantizarea matricilor provenind din componenta Y (DQT_L0, DQT_L1 si DQT_L2) respectiv 3 pentru cele provenind din componentele U sau V (DQT_C0, DQT_C1 si DQT_C2). Cifra de la sfirsitul denumirii tabelelor corespunde calitatii compresiei care se obtine utilizind tabela respectiva. Tabelele de cuantizare au elementele ordonate conform cu ordinea care se obtine in urma citirii in zig-zag a elementelor matricii care trebuie cuantizata. Primele 3 elemente corespund marker-ului utilizat in antetul JPEG si vor fi ignorate. Astfel, elementul t[1][2] care este al 7-lea in sirul ordonat va fi cuantizat cu elementul 7+3=10 din tabela de cuantizare;
• tabele de codificare clase - sint in numar de 4 si anume 2 pentru clasele coeficientilor DC (DCL - pentru Y, DCC - pentru U si V) si 2 pentru clasele coeficientilor AC (ACL - pentru Y, ACC - pentru U si V). Formatul acestor tabele a fost descris in prezentarea de mai sus.

Toate celelalte tabele sau proceduri din sursa nu prezinta interes pentru dezvoltarea proiectului ele fiind necesare pentru scrierea antetului JPEG in conformitate cu standardul.