Transmisia datelor multimedia in retele de calculatoare JPEG

Transmisia datelor multimedia in retele de calculatoareJPEGConf. Dr. Ing. Costin-Anton Boiangiu

UNIVERSITY POLITEHNICA of BUCHARESTDEPARTMENT OF COMPUTER SCIENCECompresia prin utilizarea transformarilor Compresia prin codarea transformarii este o tehnica foarte populara pentru compresia imaginilor si a surselor videoScopul aplicarii unei transformari este de a decorela continutul imaginii din acelasi cadru sau din cadre alaturate, si de a coda coeficientii transformarii, in loc de pixelii originali ai imaginiiIn acelasi timp se doreste micsorarea dependentei statistice dintre coeficienti, astfel incat sa se reduca numarul de biti necesari pentru transmiterea coeficientilor ramasiTermenul de transformare a imaginii se foloseste pentru a descrie o clasa de matrici utilizate in reprezentarea imaginilor.Daca un semnal 1-D poate fi reprezentat printr-o serie ortogonala de functii de baza, la fel o imagine poate fi reprezentata in functie de o multime discreta de functii 2D, numite si functii de bazaCompresia prin utilizarea transformarilor Ideea de baza a metodelor de tip transformate este de a descompune o imagine intr-o suma ponderata a unor imagini de baza, asa cum se prezinta in figura de mai josCriteriile de optimalitate se refera la compactarea energiei (un set mic de imagini de baza sunt suficiente pentru reprerzentarea imaginii) si decorelare (coeficientii pentru imaginile de baza suntr decorelate)Tranformata Karhunen-Loeve (KLT) este optimala pentru a matrice de covarianta data a semnalului consideratTransformata cosinus discrete (DCT) este apropiata de KLT pentru imagini ce pot fi reprezentate ca procese Markov de ordinul intai (pixelii curenti depoind numai de pixelii anteriori).

Descompunerea unei imagini dupa un set de imagini de baza

Transformari de baza in compresia prin codarea transformarii

Compresia prin utilizarea transformarilor Primul bloc realizeaza reducerea gamei dinamice a semnalului (imagine) in vederea eliminarii informatiei redundante si realizeaza impartirea imaginii in sub-blocuri acceptabile pentru realizarea eficienta a operatiei urmatoare, o transformareTransformarea se aplica pentru obtinerea unei reprezentari ce se poate coda mai eficientBlocul de cuantizare exista numai in metodele de compresie cu pierdere de informatie, intruct prin cuantizare numarul de simboluri ce trebuie codat se reduceUltimul bloc, codarea entropica, presupune folosirea unor tehnici de codare tip Huffman sau codare aritmetica in vederea obtinerii unei eficiente aproape de entropiei sursei ce are ca simboluri coeficientii cuantizatiCompresia prin utilizarea transformarilor In general, imaginea de intrare este impartita (divizata) in blocuri disjuncte, de marime NxNTransformarea poate fi reprezentata ca o operatie matriciala utilizand o matrice de transformare A, in vederea obtinerii celor NxN coeficienti de transformare, folosind o transformare liniara, separabila si de norma unitara de tipul:

Transformarea este reversibila pentru ca blocul de pixeli original, poate fi reconstruit utilizand o transformare inversa unitara, unde inversa matricii A este identica cu matricea transpusa, deci A-1 =AT, astfel incat:

Compresia prin utilizarea transformarilor Transformarea insasi nu face nici o compresieScopul transformarii este de a decorela semnalul de intrare ceea ce duce la re-distributia energiei semnalului peste un numar mic de coeficienti, coeficientii transformariiIntrucat energia semnalului se conserva rezulta ca u are loc pierdere de energie si de informatieIn acest fel multi coeficienti pot fi neglijati dupa cuantizare si inaintea codariiIn plus, prin considerarea si includerea unui model al aparatului vizual, in speta a functiei de sensibilitate la constrast, in procesul de cuantizare a coeficientilor rezulta de asemenea o marire a eficientei compresieiCompresia prin utilizarea transformarilor O transformare se numeste uni-dimensionala (1D) daca este aplicata intr-o singura directie (dimensiune) a unei imagini, adica pe linie sau pe coloanaO trasnformare bi-dimensionala (2D) este aplicata unui bloc 2D de pixeliO transformare este separabila daca nucleul transformarii poate fi descompus in doua nuclee 1D pentru operatiile efectuate pe verticala si pe orizontalaAstfel o transformare separabila aplicata unui bloc de NxN pixeli poate fi efectuata in doi pasiMai intai se aplica o transformare 1D in N puncte pe orizontala, deci pe fiecare linie a blocului, si apoi o alta trasformare 1D pe coloanele bloculuiPrin transformata 1D in N puncte se intelege o transformare 1D efectuata pe N pixeliCompresia prin utilizarea transformarilor In alegerea tipului de transformare se are in vedere gradul de decorelare a imaginii, functiile de baza dupa acre se face descompunerea, numarul de operatii necesar pentru realizarea transformarii, rapiditatea implementarilorCele mai folosite transformari sunt: Transformata Fourier Discreta (DFT)Trasformata Karhunen-Loeve (KLT)Transformata cosinus discreta (DCT)Trasformata Walsh-Hadamard (WHT)Transformata cosinus discreta (DCT)Cea mai folosita transformare este DCT aplicata unor blocuri de marime mica, 8x8 pixeliExplicatia consta in puterea de decorelare si in existenta unor algoritmi pentru implementari de timp realDCT este apropiata de transformata Fourier discreta si trebuie retinut ca coeficientii acesteia (DCT) pot fi interpretati in domeniul frecventaCoeficienti DCT mici arata/corespund unor frecvente spatiale mici in blocurile de imagine considerateCoeficienti DCT mari corespund frecventelor mariTransformata cosinus discreta (DCT)Pentru aplicarea transformarii, se esantioneaza o imagine la intervale regulate, se analizeaza componentele spectrale prezente in esantionae, se inlatura acele frecvente care nu afecteaza imaginea din punctual de vedere al ochiului umanAceasta metoda este baza pentru standardele JPEG, MPEG, (CCCIT)H.261 si H.263A fost dezvoltata de Ahmed, Natarajan, and Rao [1974] S-a folosit prima oara in compresia imaginilor de Chen and Pratt [1984]

Transformata cosinus discreta (DCT)Pentru o matrice s de dimensiune nxn, DCT 2D se calculeaza simplu: DCT 1D se aplica pentru fiecare linie a lui s apoi fiecarei coloane a rezultatuluiRelatiile de calcul sunt:

Transformata cosinus discreta (DCT)In notatie matriciala:

Refacerea informatiei originale inseamna:

Transformata cosinus discreta (DCT)Ca si in cazul uni-dimensional, fiecare element S(u,v) al transformarii este produsul intern intre intrare si functia baza, unde in acest caz functiile de baza sunt matrici de dimensiune nxn

Fiecare matrice de baza este produsul a doi vectori de baza

Fiecare matrice de baza poate fi considerata ca o imagine

Matricele de baza ai transformatei cosinus bidimensionale, n=8

Transformata cosinus discreta (DCT)Fiecare matrice de baza este caracterizata de o frecventa spatiala, orizontala si verticalaMatricile din figura sunt aranjate de la stanga la dreapta si de sus in jos in ordinea crescatoare a frecventelorFiecare pixel din imaginea DCT descrie ponderea fiecarei matrici de baza in semnalul (imagine) de la intrarePixelii sunt aranjati, in ordinea crescatoare a frecventelor de la stanga la dreapta si de sus in josCel mai stralucitor pixel din coltul din dreapta sus este cunoscut ca termenul de current continuu, sau componenta medie, cu frecventa {0,0}El este media pixelilor de la intarre, si este tipic cel mai mare coefficient in DCT al imaginilor naturaleModelarea statistica a coeficientilor DCTCoeficientii DCT urmaresc o functie densitate de probabilitate de tip gaussiana generalizata cu medie de forma:

unde

Functia

este o functie de scalare astfel incat si p este un parametru de forma

Modelarea statistica a coeficientilor DCTFunctia gamma este definita prin:

In raport cu u si v, care sunt indicii coeficietilor DCT din cadrul unui bloc, marimile de mai sus sunt constante pentru un coeficient, si controleaza forma si variantaDaca parametrul de forma, p, este 1 atunci distribuita gaussiana generalizata devine distributie LaplaceDaca parametrul de forma are valoarea 2 se obtine distributia gaussiana.

Modelarea statistica a coeficientilor DCTFunctia densitate de probabilitate gaussiana generalizata, cu diferite valori ale parametrului de forma

Exemplu - Litera A (8x8 pixel) si coeficientii DCTSe considera problema compresiei unei imagini, ce reprezinta litera A

Exemplu - Litera A refacuta pentru numar diferit de coeficienti

Selectarea numarului de coeficienti se bazeaza pe faptul ca cele mai mari valori se gasesc in jurul frecventelor joase (cel putin pentru imagini naturale)Compresia unei imagini prin DCT - raportul de compresie este 4

Compresia unei imagini prin DCTIn primul caz s-au retinut 101 coeficienti si in al doilea caz s-au retinut 3677 coeficientiRaportul de compresie este:

unde: nc este numarul de coloanenl este numarul de liniin_bit_per_pixel este numarul de biti pentru reprezentarea intensitatii unui pixeln_coef este numarul de coeficienti considerati in transformaren_bit_per_coef este numarul de simboluri binare pentru reprezentarea unui coeficient Exemplu: pentru imagini cu nivele de gri: n_bit_per_pixel = 8 si n_bit_per_coef = 32

Standardului JPEGIn standardul de compresie JPEG (Joint Photographic Experts Group)), fiecare coefficient DCT este normalizat (ponderat) cu valori ale unei matrici de normalizare, care este fixa pentru toate blocurileObiectivul ponderarii este evidentierea importantei coeficeintilor in raport cu importanta perceptuala a fiecarui coeficientDupa normalizare coeficientii sunt rotunjiti la cel mai aproape intregPentru varianta de baza a standardului JPEG se pot folosi 4 matrici de normalizare, in raport cu luminanta si componentele de crominanta ale imaginiiFiecare componenta a ariei de normalizare Q(u,v) este un intreg reprezentat pe 8 biti care in efect determina marimea pasului de cuantizareJPEG lucreaza cu 24 de biti pentru culoare, (16.7 milioane de culori), indiferent de numarul de culori din imagineStandardului JPEGIn general, frecventele spatiale de ordin mare sunt mai putin vizibile ochiului uman in comparatie cu frecventele joaseAstfel, intervalele de cuantizare sunt alese mai mari pentru frecvente mariUrmatoarea matrice de cuantizare este folosita intens pentru imaginile monco-crome si pentru componenta de luminanta a imaginiii colorEa se folosteste in compresia JPEG si este determinata din masurarea pragului de vizibilitate al coeficientului DCTAlte aplicatii pot folosi alte valori ale matrii de ponderareStandardului JPEGVizualizand matricea de luminanta, QL, si matricea de crominanta, QC, pe o scara a nivelelor de gri se vede dependenta factorilor de cuantizare de frecventa, prin cresterea intensitatii incepand din coltul stanga sus inspre coltul dreapta jos (0 = negru si 121 = alb)

Standardului JPEG

Standardului JPEG

Standardului JPEGLa efectuarea compresiei, se transforma matricea in blocuri si se cuantizeaza fiecare blocLa de-compresie se inmulteste fiecare bloc cu matricea de cuantizare si se obtine imaginea reconstruitaCuantizarea inseamna rotunjira la cel mai apropiat intreg

Standardului JPEGPrin normalizare si cuantizare se obtin multe valori de 0 pentru coeficientii DCT Inainte de codare entropica, coeficientii DCT sunt reformatati in format 1D prin scanare in zig-zag dupa urmatoarea configuratie (sau tabel de citire), in vederea gruparii celulelor care sunt corelate si a indepartarii acestei redundante prin codare entropicaAceasta arie este determinata de proprietatile sistemului olfactiv uman, care este mai putin sensibil la frecvente inalte, si permite folosirea corelatiilor celulelor invecinateS =

Standardului JPEGFiecare componenta din aria de normalizare este un intreg pe 8 biti si este transferata receptorului ca parte a informatiei de antetSe pot specifica pana la 4 arii de normalizare, de exemplu arii diferite pentru componentele de luminanta si crominanta ale unei imagini color Fiecare componenta de culoare este codata independentDe exemplu, o imagine reprezentata in spatiul YIQ este codata ca trei imagini separateSchema bloc a codorului JPEG

Schema bloc a decodorului JPEG

ObservatiiInainte de afectuarea transformarii blocului imagine are loc o deplasare a valorii pixelilor in jos cu jumatate din gama dinamica folosita la reprezentareDe exemplu, daca se foloseste gama [0 255] atunci se va scadea valoarea 128, inainte de aplicarea transformariiPentru decuantizare, de foloseste regula punctului de mijloc la refacerea coeficientilor DCT, deci la mijlocul intervalului de cuantizareAcest tip de reconstructie ar fi optimal daca si numai daca functia densitate de probabilitate a coeficientilor DCT ar fi uniformaIn realitate es este neuniforma, astfel incat pentru a minimiza valoarea patratica medie se alege ca valoare estimata coordonata centroidului intervalui de cuantizareDeterminarea pozitiei centroidului portiunii hasurate

ObservatiiIn contextul detectiei prezentei unei informatii ascunse intereseaza posibilitatile de determinare a modificarii functiei densiatte de probabilitateCoeficientii DCT au fdp de tip Laplace, ceea ce corespunde valorii 1 a parametrului de forma in expresia functiei gaussiene generalizateSe considera expresia

unde x reprezinta valorile coeficientilor DCT

ObservatiiDaca repreznta valorile cuantizate si Q este pasul de cuantizare atunci valoarea reconstituita va fi in intervalul:

Valoarea optima a esantionului refacut, peste intervalul anterior, este:unde offsetul se determina din statistica imaginii originala sau a imaginii refacute

ExempluSa se faca compresia imaginii s prin metoda codarii transformarii cu pierdere de informatie:

ExempluMatricea transformarii cosinus discrete este:

Transformata cosinus discreta aplicata imaginii s este:

ExempluSe alege matricea de cuantizare de forma:

Tranformata cuantizata:

ExempluNeglijand coeficientii mai mici de 1, 2.5 si 5 din maximumul coeficientilor AC se obtin transformatele ponderate reduse:

ExempluIn vederea codarii coeficientii se parcurg in zigzag coeficientii transformarii, dupa traiectoria:

T = [S(1,1), S(1,2), S(2,1), S(3,1), S(2,2), S(1,3), S(1,4), S(2,3), S(3,2), S(4,1), S(4,2), S(3,3), S(2,4), S(3,4), S(4,3), S(4,4)]

ExempluPentru prima matrice, Scr1, se obtine:T1= [ 32, 0, -9, -4, 0 ,7, 0, -3, 0, 0, 0, -2, 0, 0, 0, 0, EOB]

Primul coeficient este codat diferential, cu referire la valoarea coeficientului din blocul anteriorCeilalti definesc simbolurile de codare de forma [run,level]:T1= {(1,-9),(0,-4), (1 ,7), (1, -3), (3, -2), (3, 0), EOB}ExempluSimbolurile astfel obtinute se codeaza dupa un tabel de codare Huffman definit a priori, de obiceiPentru cazul de fata se va considera ca RLC binara plecand de la o reprezentare pe 8 biti a numerelor intregi cu semnPentru bitul de semn, se considera 0 pentru numere pozitivePentru caracterul EOB (End Of Block) se considera valoarea -127, foarte putin probabila sa apara in ultima pozitieRezulta fluxul binar:T1bin= {0100.000, 0000.0000, 1001.0001, 1000.1001, 0000.0000, 0000.1111, 0000.0000,1000.0011, 0000.0000, 0000.0000, 0000.0000, 1000.0010, 0000.0000, 0000.0000, 000.0000, 1111.1111}ExempluPrin codare RLC se obtine:T1Comprimat= {0, 1, 0*13, 1, 0*2, 1, 0*3, 1*2, 0*3, ,0*2, 1, 0*12, 1*5, 0*5, 1*2, 0*24, 1 ,0*5, 1, 0*25, 1*8}Impunand un numar maxim de 128 de repetari (maxim 7 biti) pentru cele doua simboluri (0 si 1) , rezulta numarul de biti necesar pentru aceasta reprezentare: n = 1+1+8+1+8+1+8+8+8+8+1+8+8+8+8+8+1+8+1+8+8 = 119Raportul de compresie este:

ExempluIn cazul refacerii imaginilor, dupa deponderare si transformare inversa:

Reconstructia imaginilor din trunchierea transformarilor

ExempluCompresia imaginii cameraman cu algoritmul JPEG si blocuri de marime 8x8S-au considerat mai multe variante in care numarul de coeficienti considerati ai transformarii sunt 4, 9 si 16Raportul de compresie este:

unde nl este numarul de liniinc este numarul de coloanenp este numarul de pixelinb_per_pixel este numarul de biti pentru un pixeln_blocuri este numarul de blocuri in care se descompune imaginea (blocuri de dimensiune 8x8)n_coef este numarul de coeficienti ai transformarii ce sunt memorati,n_bit_per_coef este numarul de biti pentru reprezentarea unui coeficient

ExempluEste interesant de observat ca aceste valori ale raportului de compresie s-au obtinut fara a se considera si codarea entropica la care este supusa imaginea dupa normalizare si scanare in zig-zagNumarul de variabil de coeficienti se obtine prin modificarea matricii de ponderare

Codarea coeficientilor in JPEGJPEG a emis mai multe standarde:JPEG cu pierdere de informatie, bazata pe DCTJPEG-LS fara pierdere de informatie, bazata pe codare predictiva si codare entropicaJPEG2000, cu sau fara pierdere de informatie, bazata pe transfomata undinelor (wavelet transform)Versiunea de baza a JPEG presupune efectuarea urmatoarelor calcule:impartirea in blocuri de 8x8 pixelipentru fiecare bloc executa:calculeaza DCTcuantizeaza perceptualcodifica cu lungime variabila dupa schema RLC + HuffmanCodarea coeficientilor in JPEGCuantizarea coeficientilor se poate face si uniform si inlaturarea coeficientilor celor mai mici dupa diverse criterii:Cuantizarea neuniforma este superioara intrucat tine seama de perceptia vizualaCoeficientii cu semnificatie de componenta medie (DC coefficients) sunt codati prin codare predictiva, folosind valorile din blocul anterior si codarea erorii prin codare HuffmanCoeficientii cu semnificatie de componente alternative (AC coefficients) sunt codati astfel:Scaneaza matricea coef DCT in zig-zagDefineste simboluri compuse de forma {run, level}, unde run reprezinta numarul de zerouri de dinaintea unei valori non-zero si level este valoarea coef iceintului consideratCodarea coeficientilor in JPEGPentru codarea Huffman a simbolurilor compuse se poate folosi o tabela Huffman implicita sau una construita prin tehnicile cunoscuteIn locul codarii Huffman se poate folosi si codarea artimetica pentru a obtine o cresterea a raportului de compresieExemplu (DC)Fie coeficientul DC curent cu valoarea 2Fie valoarea in blocul anteriori 4Eroarea de predictie este -2Eroarea de predictie se codeaza in doua parti:codul categoriei careia ii apartine eroare, in cazul de fata 2, cu cuvantul de cod 100codul pozitiei in cadrul categoriei; -2 este in pozitia 1 in cadrul categoriei 2, si are codul 01

Codul final este 100+01=10001Exemplu (AC)Fie primul simbol (0,5)Valoarea 5 este reprezentata in doua partiPrima valoare este data de categoria careia ii apartine valoare 5In cazul de fata 3 cu codul 100A doua valoare, este data de pozitia in cadrul categorieiIn cazul de fata 5 este in pozitia 5 in categoria 3 si are codul 101

Codul final este 100+101Tabelele de codare pentru coeficientii DC -DCT sub JPEG standard

Tabelele de codare pentru coeficientii ACDC -DCT sub JPEG standard

Referinte(Sikora, 1997)Thomas Sikora, MPEG Digital Video-Coding Standards, IEEE Signal Processing Magazine, pp.82100, 1997(Watson, 1994)Watson, Andrew B., Image Compression Using the Discrete Cosine Transform, Mathematica Journal, 4(1), 1994, p. 81-88(JPEG, 2000)http://www.jpeg.org/(Bojkovic, 1997)Zoran S. Bojkovic, Corneliu I. Toma, Vasile Gui, Radu Vasiu, Advanced Topics in Digital Image Compression, Editura Politehnica , 1997