Compresia Si Codarea Informatiei

I. Buciu - Compresia si Codarea Informaţiei

Ioan Buciuibuciu@uoradea.ro

http://webhost.uoradea.ro/ibuciu/

Departamentul de Electronică,Facultatea de Inginerie Electrică si Tehnologia Informaţiei

Universitatea Oradea, 410087, str. Universităţii 1,Romania

Compresia Compresia ssi Codarea i Codarea InformaInformaţţieiiei

Scopul cursului este de a familiariza studentul cu principiile si metodele de compresie şi codare a informaţiei şi, în particular, pentru imagini statice, secvenţe de imagini şi informaţie audio.

Noţiunile importante prezentate la curs vor fi dezbătute pe larg în cadrul lucrărilor de laborator asociate cursului.

Material de curs (bibliografie principală):

D. D. Salomon: Data Compression: The Complete Reference (Fourth Edition), Springer – Verlag, 2007.

Mohammed Ghanbari: Standard Codecs: Image compression to Advanced Video Coding, Institution of Electrical Engineers , 2003.

Scopul cursuluiScopul cursului

Bibliografie adiţională:

Cliff Wootton: A Practical Guide to Video and Audion Compression, Focal Press, 2005.

V. Bhaskaran and K. Konstantinides: Image and Video Compression Standards, 2nd Edition, Springer, 1997.

R. C. Gonzales, R. E. Woods, S. L. Eddins, Digital Image Processing using Matlab, Gatesmark Publishing, 2009.

Cerinţe pentru intrarea în examen:

Situaţia la laborator încheiată (se pot recupera doar 2 lucrări în perioada de recuperare !)

Scopul cursuluiScopul cursului

Introducere: noţiuni de bază in prelucrarea imaginilor, transformata Fourier, şi aplicaţii ale prelucrării semnalelor video.

Compresia fără pierderi: codarea Huffman, codarea aritmetica, codarea Lempel – Ziv.

Transformate: transformate unitare, transformata KLT, Transformata Cosinus Discreta (TCD), transformata undisoară.

Compresia cu pierderi a imaginilor statice: JPEG, JPEG 2000.

Fundamente de prelucrare a semnalului video.

Estimarea mişcării.

Compresia audio.

Cuprinsul cursuluiCuprinsul cursului

Prelucrarea semnalelor video este un domeniu folosit în:

Transmisiile TV digitale;

Studiourile TV digitale;

Videoconferinţe, videotelefonie;

Multimedia;

Transmisii video via Internet;

Librării digitale (căutare bazată pe conţinut);

Servicii de reţea noi pentru protecţia informaţiei (ex. watermarking, etc.);

Importanta domeniuluiImportanta domeniului

Necesitatea introducerii de noi canale TV într-o lăţime de banda limitată.

Necesitatea furnizării unei imagini şi sunet de calitate superioară.

Apariţia de noi servicii digitale odată cu dezvoltarea tehnologiilor aferente.

Constrângerile şi problemele prelucrării semnalelor video sunt:

Proiectarea camerelor video şi sistemelor de transmisie;

Transmiterea, înregistrarea şi depozitarea eficientă a semnalelor video;

Constrângeri legate de lungimea de bandă şi rata de bit;

Extragerea şi descrierea conţinutului informaţiei.

Importanta domeniuluiImportanta domeniului

Intr-un sistem de transmisie digital sursa de informaţie suferăurmătoarele etape:

sursa de informaţie codarea sursei codarea canalului modulaţia canal de transmisie demodulaţia decodarea canalului decodarea sursei recuperarea informaţiei

Cursul de faţă se referă doar la codarea şi decodarea sursei şi la recuperarea informaţiei (video sau imagini statice).

Codarea sursei se poate adapta la cazul particular a semnalelor video iar codarea sursei se poate adapta la proprietăţile canalului de transmisie.

Transmiterea digitala a informaTransmiterea digitala a informaţţieiiei

Prin exploatarea redundantei spaţiale, spectrale şi temporale a informaţiei (semnalelor video) se poate optimiza procesul de transmitere şi stocare a informaţiei.

Informaţia irelevantă pentru ochiul uman este eliminată (prin cuantizare) datorită proprietăţilor biologice ale ochiului uman (percepţia vizuală).

Criteriul calităţii cantitative pentru eliminarea redundaţei se referă la Eroarea Medie Patratica (EMP) şi la valoarea Raportului Semnal – Zgomot(RSZ).

Calitatea vizuala a unei imagini vizualizată de ochiul uman este subiectivă şi NU coincide întotdeauna cu calitatea cantitativă.

Este necesară determinarea unui criteriu pentru ambele calităţi.

Transmiterea digitala a informaTransmiterea digitala a informaţţieiiei

SCOPUL COMPRESIEI ?

1. Reducerea spaţiului de stocare pe

disc, hardware, etc.

2. Reducerea timpului de transmisie

pentru informaţia de dimensiune mare.

CUM SE OBTINE COMPRESIA ?

Raspuns: CODARE

Inainte de codare: MODELARE

Compresia Compresia -- GeneralitatiGeneralitati

Compresia Compresia -- GeneralitatiGeneralitatiMODELARE transformarea informaţiei originale prin extragerea

informaţiei redundante obţinerea modelului.

Informaţia obţinută (modelul) aproximează informaţia originală.

Cu cat modelul este mai apropiat de caracteristicile informaţiei originale (sursa) cu atat algoritmul de compresie este mai eficient.

Modelul este generat din statisticile empirice ale sursei.

SURSA EMITE SIMBOLURI APARTINAND UNUI ALFABET FINIT.

Alfabet mulţimea tuturor simbolurilor generate de sursă.

CODARE informaţiei i se atribuie cuvinte de cod.

TermenulTermenul dede compresiecompresie -- ExempleExempleUn exemplu simplu: un fişier de 100 K caractere

Spaţiu de stocare: (45*3 + 13*3 + 12*3 + 16*3 + 9*3 + 5*3)* 1000

= 300 Kbiti

Caracter a b c d e f

Frecventa(1000s)

45 13 12 16 9 5

Codare cu lungime fixa

000 001 010 011 100 101

TermenulTermenul dede compresiecompresie -- ExempleExempleSe poate comprima informaţia de mai sus ???

DA. SOLUTIE: Atribuirea caracterelor care apar mai frecvent cuvinte de cod mai scurte şi celor care apar mai putin frecvent cuvinte de cod mai lungi.

Spaţiu de stocare: (45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)* 1000

= 224 Kbiti Salvăm 25 % din spaţiu !

Caracter a b c d e f

Codare culungime fixa

000 001 010 011 100 101

Codare cu lungime variabila

0 101 100 111 1101 1100

Coduri unic decodabileCoduri unic decodabileAtribuirea cuvintelor de cod trebuie facută în aşa fel încat să nu existe

ambiguităţi la decodare (şirul să fie decodat in mod unic).

Coduri de lungime fixa: Cod_1

Coduri de lungime variabilă:

Cod_2 si Cod_3

Fie secvenţa de mesaj:

S = aacabad

Caracter Cod_1 Cod_2 Cod_3

a 00 0 0

b 01 10 1

c 10 110 00

d 11 111 01

Coduri unic decodabileCoduri unic decodabileFolosindu-se tabelul anterior, codarea lui S va fi:

MC Cod_1(S) = 00001000010011

MC Cod_2(S) = 001100100111

MC Cod_3(S) = 000001001

Codul_1 si codul_2 sunt unic decodabile decodarea conduce la secvenţa iniţială aacabad.

Codul_3 NU ESTE UNIC DECODABIL !

Decodare MC Cod_3(S) accbcb SAU acadab SAU aaaaabcb !!!

Codurile cu lungime fixă sunt întotdeauna unic decodabile.

Nu toate codurile de lungime variabilă sunt unic decodabile.

Coduri unic decodabileCoduri unic decodabilePentru ca un cod să fie unic decodabil nici un cuvant de cod NU

TREBUIE să fie prefix pentru un alt cuvant de cod din setul de cuvinte existente în cod.

Eliminarea ambiguităţii.

TermenulTermenul dede compresiecompresie -- ExempleExempleUn exemplu de semnal sinusoidal compus:

f(t) = cos(t) + 5*cos(2*t) + cos(3*t) + 2*cos(4*t)

Presupunem ca pe intervalul [0, 2*pi] fixam 1000 de puncte egal distantate (valorile t pe axa X) pentru reprezentarea functiei (valorile functiei pe axa Y).

Putem interpola complet aceste date prin folosirea unui model A:

t = linspace(0,2*pi, 1000)’:

b = cos(t) + 5*cos(2*t) + cos(3*t) + 2*cos(4*t)

A = [ones(size(t)), cos(t), cos(2*t), cos(3*t), cos(4*t)]

si rezolvarea ecuatiei Ax = b, pentru obtinerea coeficientilor x:

TermenulTermenul dede compresiecompresie -- ExempleExemplex = A \ b; x = [0 1 5 1 2];

Prin eliminarea coeficientilor

cu valoare < 2:

A = [cos(2*t), cos(4*t)]

x = [5.0040, 2.0040];

TermenulTermenul dede compresiecompresie -- ExempleExempleCompresie prin eliminarea (filtrarea)

unor frecvente.

EXEMPLU 1

t = linspace(0,2*pi, 2^8)’:

f = exp(-(cos(t).^2)).*(sin(2*t) + …

+ 2*cos(4*t) + 0.4*sin(t).*sin(50*t))

Aplicare transformata Fourier:

fy = fft(y);

Pastrarea coeficientilor care respecta

conditia 7 <= k <= 2^8.

TermenulTermenul dede compresiecompresie -- ExempleExemplefilterfy = [fy(1:6), zeros(1,2^8 – 12), fy(2^8 – 5: 2^8)];

Aplicare transformata Fourier inversa pentru reconstructia semnalului filtrat:

filtery = ifft(filterfy).

Sa consideram un proces aleator, mai exact o secvenţă de variabile aleatoare notata cu u(n).

Expectaţia unei variabile aleatoare X este definită de relaţia:

Proces staţionar: o secvenţă aleatoare u(n) se numeşte staţionară in sens strict (local) dacă densitatea comună a fiecărei secvenţe

parţiale este egală cu densitatea secvenţei deplasatepentru orice întreg m şi orice lungime k.

O secvenţă u(n) se numeşte staţionară în sens larg (global) dacă:

E[u(n) ] = μ = constant

E[u(n) * u(n)’ ] = r (n – n’) = r (n’) depinde doar de de n’.

[ ] dxxfxXE X )(∫∞

∞−=

{ }kllu ≤≤1),(

{ }klmlu ≤≤+ 1),(

Semnale aleatoareSemnale aleatoare

Presupunem că avem o sursă care generează un set discret de mesaje independente rk (numit alfabet) cu probabilităţile pk, k = 1, …, L. Informaţia asociată acestui alfabet este definită de relatia:

Ik = – log2 pk (biti)

Entropia unei surse este reprezentată de informaţia medie generată de sursa:

Entropia unei surse ne oferă limita inferioară a numărului de biţi necesari pentru codarea sursei.

)mesajbiti/(log1

kkk ppH

Fundamente de teoria informaFundamente de teoria informaţţieiiei

Fundamente de teoria informaFundamente de teoria informaţţieiieiExemplu: Fie alfabetul sursa A = {0, 1, 2, 3} care genereaza urmatoarea

informatie (mesaj): M = {0, 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3,3}. Probabilitatea de aparitie a simbolurilor este: p(0) = 1/20 = 0.05, p(1) = 2/20 = 0.1, p(2) = 4/20 = 0.2 si p(3) = 13/20 = 0.65. Entropia este:

H = - (p(0) * log2(p(0)) + p(1) * log2(p(1)) + p(2) * log2(p(2)) + p(3) * log2(p(3)) ) = - (0.05 * log2(0.05) + 0.1 * log2(0.1) + 0.2 * log2(0.2) + 0.65 * log2(0.65) ) = -1.42 biti/mesaj.

Daca presupunem ca intre fiecare 2 simboluri consecutive exista corelatie, corelatia (redundanta) se poate elimina prin extragerea fiecarui simbol din valoarea sa precedenta, obtinandu-se astfel o sursa de reziduri.

Fundamente de teoria informaFundamente de teoria informaţţieiieiAstfel M se transforma in Mr = {0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0,

1, 0, 0, 0}, iar alfabetul va fi A = {-1, 1, 0} . Probabilitatea de aparitie a simbolurilor va fi acum: p(-1) = 1/20 = 0.05, p(1) = 4/20 = 0.2, p(0) = 15/20 = 0.75. Entropia este:

H = = - (0.05 * log2(0.05) + 0.2 * log2(0.2) + 0.75 * log2(0.75) ) = -0.992 biti/mesaj < -1.42 .

Prin eliminarea redundantei mesajul poate fi reprezentat pe un numarmai mic de biti !

Entropia unei surse ne oferă limita inferioară pentru lungimea medie de cod Imedie a unui cod cu lungime variabilă asociat simbolului rk.

Redundanţa unui cod este dată de relaţia: R = Imedie – H.

Entropia unei surse este maximă în cazul unei distribuţii uniforme, adică: pk = 1/ L, k = 1, …, L.

Fundamente de teoria informaFundamente de teoria informaţţieiiei

Considerăm o sursa staţionară şi discretă de informaţie.

La codarea sursei fiecărui simbol i se asociază un cuvânt de cod.

Lungimea de cod este dată de lungimea numărului de biţi din cuvânt.

Lungimea medie de cod este reprezentată de rata de bit exprimată în biţi pe simbol.

Teorema lui Shannon pentru codarea sursei fără zgomot ne spune că, pentru o sursă discretă şi staţionară, rata de bit minimă necesară pentru codarea unui simbol, în medie, este egală cu entropia sursei.

In practică, imaginile şi secvenţele video sunt reprezentate de alfabete de lungime finită.

Teorema codTeorema codăării sursei fara zgomotrii sursei fara zgomot

Eficienţa (randamentul) unei codări este dată de relaţia:

Redundanţa unei surse poate fi exprimată in raport cu η :Daca η = 1, redundanţa R = 0.

In cazul canalelor de transmisie cu zgomot simbolurile recepţionate pot suferi erori datorate lipsei redundanţei din informaţiei.

Prin adăugarea redundanţei (codarea canalului) unele erori pot fi depistate sau chiar corectate.

medieIH

Teorema lui Shannon pentru codarea sursei fără zgomot ne spune că este posibilă transmiterea fără eroare a simbolurilor pe un canal cu zgomot dacărata de bit R este mai mică decât capacitatea C a canalului (R < C).

Canalul se presupune a fi fără memorie.

Capacitatea (Gaussiana) a canalului este dată de zgomot şi de puterea semnalului.

Capacitatea canalului limitează superior rata de bit.

Teorema codării fără zgomot limitează inferior rata de bit pentru codarea sursei şi a canalului fără zgomot.

Teorema codării canalului cu zgomot limitează superior rata de bit pentru o transmisie fără erori.

In cazul unei codări cu pierderi are loc o distorsiune a informaţiei.

Una din cauze este procesul de cuantizare a informaţiei.

Erorile pot sa apară chiar şi în cazul unui canal fără zgomot.

Si în acest caz se poate defini o limita inferioara a ratei de bit.

Codarea cu pierderi a informaCodarea cu pierderi a informaţţieiiei

Teorema codării sursei ne spune că, pentru o distorsiune dată D, există o funcţie numită Rata de Distorsionare R(D) exprimată prin minimul ratei de bit necesară transmiterii sursei cu o distorsiune mai mică decât D.

Pentru distorsiuni mai mici decât D, rata de bit satisface relaţia

Pentru un canal cu zgomot relaţia devine:

Relaţia de mai sus se referă la teorema transmiterii informatiei care ne spune că este posibilă transmiterea informaţiei distorsionate cu D pe un canal cu zgomot dacă capacitatea C a unui canalului cu zgomot este mai mare decât rata de distorsiune R(D).

)(DRR ≥

)(DRC ≥

Codarea cu pierderi a informaCodarea cu pierderi a informaţţieiiei

Majoritatea standardelor de codare video (standarde ISO & ITU) de la începutul anilor 90 au fost bazate pe acelaşi principiu generic (sau model) cunoscut sub numele CODEC DPCM / DCT (DPCM – Differential Pulse Code Modulation, DCT – Discrete Cosine Transform).

Paşii de bază ale codării video:

Fiecare cadru video este procesat în unităţi numite macroblocuri.

Fiecare cadru este comparat cu un cadru de referinţă prin determinarea celei mai bune “similarităţi” pentru fiecare macrobloc. Acest pas se numeşte determinarea vectorului de estimare a miscării.

ModelulModelul CODEC Video DPCM / DCTCODEC Video DPCM / DCT

Paşii de bază a codării video:

Formarea unui macrobloc rezidual prin extragerea macroblocului prezis din macroblocul real.

Macroblocul rezidual este transformat (tipic cu ajutorul Transformatei Cosinus Discreta – TCD) şi apoi cuantificat.

Coeficienţii cuantificaţi sunt reordonaţi şi codaţi cu un cod de lungime variabilă (run – level code).

La final, coeficienţii, vectorul de mişcare si locaţia asociatăpentru fiecare macrobloc sunt comprimaţi (codarea entropiei) pentru producerea fluxului (de biţi) final.

ModelulModelul CODEC Video DPCM / DCTCODEC Video DPCM / DCT

Elemente fundamentale de prelucrare a Elemente fundamentale de prelucrare a imaginiiimaginii

Prelucrarea imaginii digitale poate fi împarţită în 6 clase de bază:

1. Reprezentarea şi modelarea imaginii;

2. Imbunătăţirea imaginii;

3. Restaurarea imaginii;

4. Analiza imaginii;

5. Reconstrucţia imaginii;

6. Compresia imaginii.

Imagine Tablou bidimensional de pixeli

Reprezentarea imaginii caracterizează cantitatea de imagine reprezentatăde fiecare pixel (elementul de imagine).

Obiectivul principal al imbunătătirii imaginii este de a prelucra imaginea in asa fel încât imaginea finală sa fie mai “potrivită” pentru o aplicaţie specifică (este un proces orientat pe problema).

Restaurarea imaginii se referă la eliminarea sau minimizarea unei degradări din imagine.

Analiza imaginii se referă la măsurători cantitative pentru descrierea unei imagini.

Aplicaţii ale analizei imaginii: imagistică medicală, robotică, etc.

Majoritatea metodelor de prelucrare a imaginii, cum ar fi îmbunătăţirea imaginii sau filtrarea, folosesc informaţie locală de imagine. Aceste operaţii pot fi executate folosind o fereastră finită (mască) care se deplasează de-a lungul imaginii.

Informaţia globală de imagine este folosită în special pentru transformarea imaginii, cum ar fi, Transformata Cosinus Discreta (TCD).

Majoritatea metodelor de codare a imaginilor sunt de tip codare – bloc: imaginea originală se împarte în blocuri de lungime fixă (de regulă 8 x 8 pixeli) iar aceste operaţii se aplică tuturor acestor blocuri (local).

Transformata Fourier (TF) si Transformata Fourier inversă a unei funcţii f (x) sunt date de perechea:

{ } dxxf(x)f(x)F )2 j (-exp21)( πξπ

ξ ∫∞

∞−== F

[ ] ξπξξπ

ξ dxFFf(x) )2 (jexp)(21)( ∫

∞−== 1-F

TransformataTransformata Fourier (TF)Fourier (TF)

{ } dydxxy)f(xy)f(xF y))(2 j (-exp,21,),( 2121 ξξππ

ξξ +== ∫∫∞

∞−

∞−F

Transformata Fourier - 2D (TF - 2D) si Transformata Fourier inversă a sa sunt date de relaţiile:

[ ] 2212121 y))(2 (jexp,21,),( ξξξξπξξπ

ξξ ddx)F()F(yxf +== ∫∫∞

∞−

TransformataTransformata Fourier 2D (TF Fourier 2D (TF –– 2D)2D)

Cateva din proprietaţile transformatei TF - 2D :

Frecvente spaţiale. Dacă f(x, y) reprezintă luminanţa imaginii si x, y coordonatele spaţiale, atunci ξ1, ξ2 se numesc frecvenţe spaţiale ce reprezintă schimbările de luminanţă în raport cu distanţa spaţială.

Separabilitate. Prin definiţie transformata Fourier kernel este separabilă => O transformată Fourier 2D se poate obţine din transformări Fourier succesive 1D.

Teorema convoluţiei.

( ) ( )2121 ,ξξF,ξξHf(x,y)h(x,y)g(x,y) =⊗=

TransformataTransformata Fourier Fourier –– 2D (TF 2D (TF –– 2D)2D)

Imagini si transformateImagini si transformate FourierFourierO imagine (ca orice semnal) poate fi interpretată ca o sumă de

componente de diverse frecvenţe.

Frecvenţa spaţială se referă la modul în care se modifică valoarea unui pixel în raport cu valorile pixelilor vecini din aceeasi imagine.

O variaţie lentă a valorilor de la un capat al celuilalt al imaginii indicăimagine de frecvenţe spaţiale joase.

O variaţie bruscă a valorilor pentru pixelii adiacenti conduce la imagine de frecvenţe spatiale înalte.

Exemple de variaţie bruscă în imagine: contur, margine, muchie.

Imagini si transformateImagini si transformate FourierFourier

Imagine de frecvente spatiale joase Imagine de frecvente spatiale inalte

O imagine naturala este compusa atat din frecvenţe spaţiale înalte cat şi frecvenţe spaţiale joase.

Descompunerea imaginii în componente de frecvenţă Transformata Fourier bidimensională (TF – 2D) parte reala şi parte complexă.

TF – 2D: domeniul pixelilor domeniul frecvenţelor spaţiale.

Imagini si transformateImagini si transformate FourierFourierPartea reala a TF – 2D reprezintă amplitudinea frecvenţelor spaţiale

prezente în imagine.

Partea complexă a TF – 2D reprezintă faza frecvenţelor spaţiale din imagine.

Reprezentarea frecvenţelor spaţiale din imagine “diagrama stea”: frecvenţa cea mai joasă este reprezentată în centrul diagramei iar frecvenţele spaţiale cresc pe măsură ce ne indepărtăm de mijlocul diagramei.

TF – 2D pentru imaginea de frecvente spatiale joase

Stanga: imaginea originala; dreapta: diagrama stea. Se observa ca majoritatea componentelor din imagine sunt concentrate in partea din mijloc a

diagramei (partea luminoasa), indicand o imagine de frecvente spatiale predominante joase.

TF – 2D pentru imaginea de frecvente spatiale inalte

Stanga: imaginea originala; dreapta: diagrama stea. Se observa ca majoritatea componentelor din imagine sunt distribuite in spatiul frecventelor inalte.

Componenta continua (DC)

Componente de frecvente joase

Componente de frecvente inalte

a) b) c)

a) Imaginea originala b) Amplitudinea coeficientilor TF

c) Amplitudinea centrata a coeficientilor TF

d) Faza TF

TF TF –– 2D : 2D : ExempluExemplu

TF TF –– 2D :2D : ExempluExemplu

In imaginea (centrata) a spectrului, componenta cea mai mare ca valoarea - punctul cel mai luminos - (continuă - DC) este situată in centrul imaginii.

Componenta DC este înconjurată de coeficienţii corespunzători frecvenţelor joase.

Din imagine se observă că, majoritatea frecvenţelor din imagine sunt concentrate în banda de frecvenţe (zona mai deschisă).

Cu cat ne îndepărtăm de centru găsim componente de frecvenţe tot mai înalte (valori tot mai mici apropiate de zero).

Frecvenţele înalte sunt asociate detaliilor din imagine (cum ar fi muchiile, de exemplu).

a) c)b)

Reconstructia imaginii din spectrul de amplitudini si faza TF

a) Imaginea originala b) Reconstructia folosind doar amplitudinea TF

c) Reconstructia folosind doar faza TF

Reconstructia imaginii din spectrul de amplitudini si faza TF

a) Imaginea originala

b) Reconstructia folosind amplitudinea + faza TF (reconstructie totala)

Importanta amplitudinii si fazei Importanta amplitudinii si fazei TF2DTF2D

Imaginea A Imaginea B

Amplitudine A+

Faza B

Amplitudine B+

Faza A

Reconstructia imaginii Reconstructia imaginii din din componentele componentele FourierFourier

Imagineaoriginala

50 componente

200 componente

1000 componente

TF TF –– 2D 2D

a) Imagine originala b) Zgomot sinusiodal c) Imagine zgomotoasa

d) Spectrul TF pentru a) e) Spectrul TF pentru zgomot

f) Spectrul TF pentru c)

AplicatiiAplicatii 2D 2D ––TF:TF: Suprimarea zgomotuluiSuprimarea zgomotului

AplicatiiAplicatii 2D 2D ––TF:TF: Suprimarea zgomotuluiSuprimarea zgomotuluiPentru eliminarea celor doua spoturi luminoase

(asociate zgomotului) din spectrul TF se aplica un filtru opreste-banda sau trece-jos pentru eliminarea componentelor de frecventa înalta (in care se gasescsi componente de zgomot).

Fitru Gaussian trece

jos (sigma = 0.8)

Fitru Butterworth opreste banda

Pentru compresia imaginii se poate folosi TF 2D:

Se stabileşte un prag θ;

Componentele de valoare sub acest prag (de frecvenţă foarte înaltă) se setează la zero.

Ex: pentru c2DTF = 5, θ = 7 c2DTF 0

De ce compresie ?

în binar c2DTF = 5 este reprezentat de 101 (pe 3 biţi) !

în binar c2DTF = 0 este reprezentat de 0 (1 bit) !

AplicatiiAplicatii 2D 2D ––TF:TF: Compresia imaginiiCompresia imaginii

Imaginile digitale au un spectru de frecvenţă limitat.

Transformata Fourier a unei imagini eşantionate în mod arbitrar este o replica scalată şi periodică a transformatei Fourier a imaginii originale.

Daca frecvenţele de eşantionare x, y sunt mai mari decât dublul lăţimii de banda (frecventele Nyquist), adică ξxs > 2 ξx0 si ξys > 2 ξy0 atunci F(ξ1, ξ2) poate fi reconstituit cu un filtru trece jos ideal.

Daca frecvenţele de eşantionare sunt sub frecventele Nyquist, spectrul F(ξ1, ξ2) este distorsionat şi nu poate fi reconstituit.

Teorema esantionariiTeorema esantionarii in 2Din 2D

Filtrarea de tip trece jos ideala in domeniul frecvenţă este echivalentă cu procesul de convoluţie cu funcţia sinc in domeniul spaţial.

Pentru reconstrucţia completă a unei funcţii continue f(x,y) cu ajutorul eşantioanelor sale f(mΔx, nΔ y) este necesară o interpolare de ordin infinit.

In realitate este posibilă doar o interpolare de ordin finit.

Interpolarea si filtrarea trece jos sunt două etape necesare pentru reconstrucţia semnalului analogic (continuu).

In cazul interpolării 2D (bidimensionale) interpolarea se aplică mai întâi liniilor şi apoi coloanelor.

Reconstructia folosind eReconstructia folosind eşşantioaneantioane

Imaginile digitale sunt de obicei reprezentate prin matrici în care fiecare element al matricii corespunde unei valori (pe nivele de gri pentru imagine reprezentată pe nivele de gri) a pixelului corespunzător locaţiei spaţiale.

O matrice ortogonală este o matrice pentru care inversa sa este egală cu transpusa sa: sau .

O matrice se numeşte unitară dacă inversa sa este egală cu conjugata transpusei: sau

Liniile (coloanele) unei matrici unitare pătrate de dimensiune N x N sunt ortogonale şi formează un set complet de vectori de bază într-un spaţiu vectorial de dimensiune N.

T1 AA =− IAAAA == TT

T1 ∗− = AA IAAAA == ∗∗ TT

MatriciMatrici

O imagine digitala este reprezentata ca funcţie de două variabile independente (x, y, de exemplu): u(x, y), v[x, y], f[x, y].

Variabilele x, y au valori discrete şi sunt notate de obicei cu l, c (linii, coloane) sau m, n.

Aceste variabile se referă la spaţiul imaginii, adică locaţia elementului de imagine (pixel).

In cazul informaţiei video se introduce o noua variabilă, timpul; valoarea pixelului la fiecare locaţie variază în funcţie de această nouă variabila.

Valoarea pixelului se poate referi la luminanţă (strălucire) în cazul imaginilor pe nivele de gri sau culoare în cazul imaginilor color.

Reprezentarea matematica a imaginiiReprezentarea matematica a imaginii

Aproape fiecare culoare poate fi compusă din cele trei culori fundamentale:

rosu, verde si albastru.

Retina conţine 3 tipuri de fotoreceptori

Reprezentarea informaReprezentarea informaţţiei iei

Imaginea Imaginea alb alb -- negrunegruImagine alb – negru:

doar 2 culori pentru fiecare

din pixelii imaginii.

1 – negru.

0 – alb.

Indexarea informatiei Indexarea informatiei de de culoareculoarePentru o imagine reprezentată

pe 8 biţi, valoarea unui pixel nu

poate depăşi 256.

Imagine color 24 Imagine color 24 -- bitibitiImagine color 24 – biţi (true color): milioane de (nuanţe) culori simultan

8 biţi pentru fiecare canal R, G si B.

Sistemul vizual uman Sistemul vizual uman -- fotoreceptoriifotoreceptoriiSVU conţine 3 tipuri de fotoreceptori (conuri) responsabili cu vederea

color: S, M, si L.

Cainii au 2 tipuri, albinele 4.

S este sensibil la albastru

(445 nm).

M este sensibil la verde

sau galben (535 nm).

S este sensibil la rosu

(575 nm).

Răspunsul la stimuli (sensibilitatea) nu este uniform.

Reprezentarea informaReprezentarea informaţţiei videoiei videoSecvenţele video pot fi tratate ca o secvenţă de cadre (imagini statice),

unde fiecare astfel de imagine reprezintă o matrice de pixeli.

Semnalul video color este reprezentat de cele trei culori primare RBG (Red, Blue, Green), aşa numitul spaţiul de culoare RGB.

Componentele R, G, B sunt puternic corelate.

In general pentru o codare eficientă, spaţiul de culoare este convertit în sistemul de culori YUV.

Y se referă la luminanţă (strălucire), iar U si V sunt componentele de crominanţă (diferente de culoare – nuanţă).

Conversia RGB YUV:

Y = 0,3 R + 0,6 G + 0,1 B; U = B – Y; V = R – Y

Un alt sistem de coordonate pentru culoare este spaţiul YCrCb, unde componentele Cr si Cb sunt obţinute astfel:

Cr = (V / 1,6) +0,5

Cb = (U / 2) + 0,5

Componentele Cr si Cb prezinta o redundanţă crescută.

Componentele de crominantă sunt de obicei subesantionate cu 2 în fiecare directie.

Un bloc de imagine 2 x 2 va fi astfel reprezentat de 4 valori de luminanţă şi o singură valoare pentru Cr si Cb.

Valorile lui Cb si Cr sunt obţinute prin medierea valorilor Cb si Cr din blocul 2 x 2 pixeli.

Reprezentarea Reprezentarea imaginiiimaginii colorcolor

Y U (Cb) V (Cr)

DE RETINUT:

Sistemul YUV separă componenta de luminanţă pentru care ochiul este foarte sensibil la detalii, de componentele de nuanţă la care sensibilitatea este mai redusă !

Consecintă: la semnalul TV apare o compresie în cazul crominantei (nuanţei) prin limitarea benzii de frecvenţă pentru U şi V la 1,3 MHz faţă de 6 MHz disponibil pentru semnalul Y (la sistemul TV PAL).

Reprezentarea Reprezentarea imaginiiimaginii colorcolor pentru compresiepentru compresie

Formate Formate de imaginede imagineCCIR – 601 – este un standard ce se referă la informaţia video digitală.

Mai precis, CCIR – 601 stabileşte un format de imagine de o rezoluţie impusă (dedicat special studiourilor digitale de inregistrări):

Rezoluţia de luminantă: 720 x 485.

Rezoluţia de crominantă: 360 x 485.

Numar de cadre pe secundă (ncs): 60.

Pentru alte aplicaţii, această rezoluţie poate să difere, rezoluţie mică (în aplicaţii de tip videoconferinţe sau videotelefonie) sau rezolutie mai mare (în cazul televiziunii HDTV).

Formate Formate de imaginede imagineFormatul SIF (source input format) foloseşte jumătate din aceste valori

(scanare intreţesută).

Mai exact: standardul european: 360 x 288 x 25

Mai exact: standardul american: 360 x 240 x 30

Număr de cadre pe secundă (ncs): 50.

Formatul CIF (common intermediate format):

Rezoluţia de luminanţă: 352 x 240.

Rezoluţia de crominanţă: 176 x 120.

Număr de cadre pe secundă (ncs): 30.

Formate Formate de imaginede imagineFormatul QCIF (quarter common intermediate format):

Rezoluţia de luminanţă: 176 x 120.

Rezoluţia de crominanţă: 88 x 60.

Numar de cadre pe secundă (ncs): 30.

Formatul SubQCIF: cel mai mic format standard

Rezolutia de luminanţă: 128 x 96.

HDTV: rezoluţie dublă faţă de referinţă CCIR – 601.

Variante HDTV:

1080 x 720 (nu este standard)

1920 x 720 (formatul propus in Europa)

1920 x 1200 (experimental)

Secvenţele video implica un volum mare de date.

De exemplu, sa consideram un modem de 56 kpbs si fiecare cadru de imagine color conţine:

288 x 352 pixeli,

fiecare pixel din culorile primare (R, G, B) este reprezentat pe 8 biti,

O secvenţa video conţine 30 de cadre / secunda

In aceste condiţii rata de bit necesara este de 72990720 biţi pe secunda (bps), adica de 1289 de ori mai mare decat rata de bit disponibila (a modemului).

NoNoţţiuniiuni introductive deintroductive de compresiecompresie videovideo

De aici compresia imaginii este necesara !

Compresia imaginii poate avea loc datorita prezentei informatiei redundante din imagine, prin eliminarea redundantei are loc compresia.

O mica parte din informaţia redundanta este totuşi folosita pentru obţinerea unei rezilienţe la eroare (aparuta la erorile de codare a canalului).

Redundanta se poate imparti in redundanta statistica si redundanta psihovizuala.

Redundanta statistica include redundanta spaţiala, spectrala si temporala.

Redundanta psihovizuala se refera la proprietatile Sistemului Vizual Uman (SVU): informaţia este perceputa in mod diferit.

SVU are proprietati de senzitivitate diferite:

mascarea luminanţei (contrastul): senzitivitatea ochilor depinde de intensitatea altui stimul vizual.

mascare temporala: SVU nu este sensibil la detalii in cazul in care scena se schimba brusc.

mascarea texturii (dependenta de detalii):cu cat textura este mai puternica (variata) cu atât este mai mare pragul de discriminare (zgomotul aditiv este mai puţin supărător pentru texturile variate decât in zonele netede de imagine).

mascarea frecventei: ochiul este mai puţin sensibil la conţinutul unei imagini corespunzător frecventelor înalte.

SVU are proprietati de senzitivitate diferite:

SVU este mai sensibil la informaţia de luminanţa decât la informaţia de crominanta.

Calitatea imaginii si a informaţiei video sunt doi factori hotărâtori pentru alegerea metodei de codare / compresie.

Daca doua metode ce compresie conduc la aceeasi calitate vizuala a imaginii sau a informaţiei video reconstituite, se prefera metoda care comprima cel mai bine (reduce informaţia mai mult).

Invers, daca o informaţie este comprimata cu aceeaşi cantitate de către doua metode de compresie, se prefera metoda care conduce la cea mai buna calitate vizuala a imaginii.

Măsurarea calitatii imaginii este dificila: măsurare obiectiva – eroarea medie pătratica, raport semnal – zgomot; măsurare subiectiva – măsurata de factorul uman prin inspecţie vizuala.

MMăăsurareasurarea calitatii imaginiicalitatii imaginii

Măsurarea (evaluarea) subiectiva este foarte costisitoare: este nevoie de multe imagini si mai mulţi evaluatori umani pentru o decizie finala.

MMăăsurareasurarea calitatii imaginiicalitatii imaginii

Notam cu e(m,n) eroarea dintre intrarea x(m,n) a codorului si reconstrucţia y(m,n) obţinuta de decodor, pentru fiecare pixel al carei coordonate pe linii si coloane sunt m si n.

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

Eroarea Medie Patratica (EMP) se defineşte ca valoarea medie a erori pătratice:

Raportul Semnal – Zgomot (RSZ) este definit prin:

∑ ∑−

1linii

1coloane

2 ),(coloanelinii1 nmeEMPε

1linii

1coloane

10 *coloanelinii),(

log*10)(ε∗

= ∑ ∑−

MMăăsurareasurarea obiectivaobiectiva aa calitatii imaginiicalitatii imaginii

La codarea video se foloseste frecvent Raportul Semnal – Zgomot de Varf (RSZV):

In relatia de mai sus se presupune o reprezentare a imagini pe 8 biti valorea maxima este 255.

Cu cat raportul RSZ este mai mare cu atat calitatea imaginii este mai buna.

Nu intodeauna principiul de mai sus coincide cu parerea factorului uman.

Se prefera o combinatie intre judecata subiectiva (factorul uman) si masuratoarea obiectiva.

10255log*10)(ε

=dBRSZV

MMăăsurareasurarea obiectivaobiectiva aa calitatii imaginiicalitatii imaginii

Exista trei etape principale in codarea unei imagini sursa: transformarea, cuantizarea si atribuirea cuvintelor de cod.

Procesul de transformare se foloseşte pentru determinarea cantitatii de informaţie din imagine sau informaţie video care trebuie codata.

Datele astfel transformate conduc la o reducere a redundantei din imagine si, ca o consecinţa, la o codare mai eficienta.

Procesul de cuantizare discretizeaza coeficienţii de transformare rezultând o compresie cu perderi.

Cuantizarea care foloseşte intrare si ieşire scalara se numeşte cuantizare scalara, in timp ce, cunatizarea vectoriala are ca intrare si ieşire vectori.

NotiuniNotiuni dede codare si decodarecodare si decodare aa surseisursei

Exemple de codare cu lungime vaiabila: codarea entropiei (codare Huffman si coduri aritmetice) si codare de tip run – length (RLC).

Cuanitizarea este un proces reversibil.

NotiuniNotiuni dede codare si decodarecodare si decodare aa surseisursei

Etapa de cuantizare transforma o variabila continua u intr-o variabila discreta u* care poate lua valori dintr-o mulţime finita de numere {r1, r2, …, rL}.

Procesul de cuantizare este ireversibil: valoarea variabilei continue (de la intrarea cuantizorului) nu poate fi determinata in mod unic pe baza valorii variabilei sale discrete (de la ieşirea cuantizorului).

Cuantizorul este definit de 2 parametrii: nivelele de decizie {tk, k = 1, …, L+1} si nivelele de reconstructie {rk, k = 1, …, L}.

Daca u se afla in intervalul [tk, tk+1) va lua valoarea discreta rk.

A = tL+1 – t1 se numeşte gama dinamica a cuantizorului.

ProcesulProcesul de de cuantizarecuantizare

ProcesulProcesul de de cuantizarecuantizareUn exemplu de cuantizor cu prag constant (QPC) este prezentat in figura

de mai jos.

QPC este caracterizat de 2 parametrii: valoarea de prag th si pasul de cuantizare q.

ProcesulProcesul de de cuantizarecuantizareIn practica nu se transmit coeficientii cuantizati ci un index de cuantizare

definit de expresia:

unde F(u,v) sunt coeficientii (obtinuti dupa transformarea imaginii – ex. Transformata TCD), iar simbolul semnifica rotunjirea la cel mai apropiat intreg.

Motivul pentru care se transmite indexul in locul coeficientilor cuantizati este faptul ca indexul are o entropie mult mai mica.

La decodare, coeficientii sunt recuperati (reconstituiti) prin cuantizare inversa:

⎥⎦

⎥⎢⎣

qvuFvuIndex ),(),(

⎣ ⎦

qvuIndexvuF q ×⎭⎬⎫

⎩⎨⎧ ±=

21),(),(

ProcesulProcesul de de cuantizarecuantizareProblema cu cuantizorul liniar este faptul ca, pentru o rata de bit scazuta

nivele de cuantizare sunt limitate pasul de cuantizare este mare.

Apare (mai ales in zonele de luminanta scazuta) asa numitul zgomot granular.

Zgomotul este mai putin pronuntat la un pas de cuantizare si mai mare dar se pierde din rezolutie (in acele zone) apare asa numitul zgomot de contur.

Solutia cea mai simpla este de a reduce pasul de cuantizare.

Pas de cuantizare mic reduce nivele de reconstructie (la o rata de bit scazuta) tranzitiile bruste din imagine (muchiile) nu pot fi codate cu o precizie satisfacatoare zgomot de panta supraincarcata.

ProcesulProcesul de de cuantizarecuantizareSOLUTIA: Folosirea unui pas de cuantizare adaptiv.

Pas de cuantizare mic pentru zonele uniforme din imagine (tranzitii lente)

Pas de cuantizare mare pentru zonele care reprezinta muchii sau tranzitii bruste (texturi complexe).

Se poate ajunge pana la 1 bit / pixel timp de calcul ridicat !

Cuantizorul Lloyd – Max este un cuantizor optim din punct de vedere al principiului EMP (minimizează distorsiunea introdusa de cuantizor)

Cuantizorul Lloyd minimizează EMP pentru un număr de nivele de cuantizare date.

Nivele de tranziţie optime sunt situate la jumătatea distantei dintre nivele de reconstrucţie optime.

Nivele de reconstrucţie optime sa afla la in centrul de masa al densitatii de probabilitate dintre nivele de tranziţie.

Nivelele de reconstrucţie si de tranziţie pot fi determinate iterativ folosind, de exemplu, metoda Newton – Rapshon.

CuantizorulCuantizorul Lloyd Lloyd -- MaxMax

O cuantizare uniforma este caracterizata de următoarele expresii:

nivele de decizie:

nivele de reconstrucţie:

Erorile de cuantizare sunt uniform distribuite pe intervalul

EMP este data de relaţia:

Ltt 11L −

=Δ + Δ+= −1kk tt

+= kk tr

⎟⎠⎞

⎜⎝⎛ ΔΔ−

121 22

Δ= ∫

Δ−duuEMPε

Cuantizarea optima uniformaCuantizarea optima uniforma

Daca nivele de cuantizare sunt prea mici se poate observa un efect de “contur” in imagini.

In mod normal imaginile sunt cuantizate uniform cu 8 biţi / pixel.Efectul de “contur” este vizibil la 6 biţi / pixel.

La imaginile color spaţiul de culoare nu este uniform.

O cuantizare pe 4 biţi este, de multe ori, suficienta pentru imaginile color.

Cuantizarea optima uniformaCuantizarea optima uniforma

Cuantizarea vectoriala (CV) se refera la transformarea unui bloc de date de eşantioane intr-un numar de stari finite.

CV este superioara vectorizarii scalare.

CV se foloseşte de dependentele statistice dintre eşantioanele de date.

Primul pas este descompunerea unei imagini intr-un set de vectori.

Fie x = [x1, x2, …, xm] un vector de dimensiune m corespunzător unui bloc dintr-o imagine.

In CV spaţiul de dimensiune m constituit din 2m blocuri posibile este cuantizat in L regiuni Ri, i = 1, …, L, numite regiuni Voronoi.

Cuantizarea vectorialaCuantizarea vectoriala

Toti vectorii inclusi in regiunea Ri sunt reprezentaţi de un singur vector, ri, ri = [ri1, ri2, …, rim] numit vector de cod.

Mulţimea r = [r1, ri2, …, rL] se numeşte alfabetul codului.

Partitionarea spaţiului m in L regiuni Voronoi in aşa fel încât eroarea medie pătratica de cuantizare sa fie minima se refera la proiectarea alfabetului de cod.

Odată ce alfabetul este alcătuit, pentru transformarea unui mesaj intr-un vector cod, se cauta vectorul de cod din alfabet de valoare cea mai apropiata de vectorul rezultat din transformarea mesajului (informaţiei).

Eticheta de reconstrucţie este data de entropia codului.

La decodare se cauta eticheta corespunzătoare vectorului de reconstrucţie.

Daca se aloca 8 biţi / pixel, si lungimea L a alfabetului este o putere a lui 2, rata de compresie este (m x 8) / log2L.

Valori tipice: m = 4 x 4, L = 1024 rata de compresie = 12,8.

Alfabetul este proiectat (invatat) folosind un set de antrenare de imagini reprezentative.

Pentru măsurarea distorsiunilor se foloseşte de regula EMP.

De regula este nevoie de 100 de vectori de antrenare / cod si L < 5000.

Metoda celor k – medii:

Se initializeaza j = 0 si un alfabet initial cu valori r(0) = [r1, r2, …, rL].

Pentru fecare iteraţie j = 1, …Se definesc regiunile Ri folosind r(j) si un clasificator de distanta minima.

Daca stop. (D(j) este distorsiunea totala pentru r(j)).

Daca nu este îndeplinita condiţia de mai sus, se incrementează j, se actualizează r(j) calculând media celor Ri.

ε<−−

Alegerea valorilor iniţiale ale alfabetului este cruciala !

Algoritmul descris este unul de tip căutare completa.

Este necesara reducerea cantitatii de date (informaţie)

Datele pot conţine o cantitate mare de informaţii redundante (spaţiala, temporala, de codare, sau psihovizuala).

Pentru reducerea redundantei datele sunt modelate.

Comprimare Date fara informaţie redundanta.

Relaţia de baza:

Compresie = Modelare + Codare

Notiuni introductive de compresie a informaNotiuni introductive de compresie a informaţţiei iei

Clasificarea metodelor de compresie:

cu pierderi (informaţia iniţiala NU SE POATE recupera in totalitate)

fara pierderi (informaţia iniţiala SE POATE recupera in totalitate)

Metodele practice de compresie (pentru codarea imaginilor si video) sunt de regula cu pierderi.

Notiuni introductive de compresie a informaNotiuni introductive de compresie a informaţţiei iei

Principiile compresiei sunt imprumutate de teoria informatiei.

Simbolurile sunt modelate ca variabile aleatoare.

Comceptul de baza se refera la “masurarea incertitudinii” cunoscuta sub numele de entropie:

Codarea sursei Reducerea entropiei Reducerea numarului (mediu) de biti necesari reprezentarii informatiei (imaginii) COMPRESIE

∑ ∈−=

XxxPxPXH )(log)()( 2

EntropiaEntropia

Exemplu 1: Fie o variabila aleatoare X cu probabilitatile (simbolului) urmatoare: 0.15, 0.15, 0.2, 0.25 si 0.25. Entropia este data de:

H(X) = – (0.15 log 0.15 + 0.15 log 0.15 + 0.2 log 0.2 +

+ 0.25 log 0.25 + 0.25 log 0.25) =

= – 0.3 log 0.15 – 0.2 log 0.2 – 2*0.5 log 0.25

≈ 2.2855 biti.

EntropiaEntropia

Exemplu 2: Fie o variabila aleatoare X cu probabilitatile (simbolului) urmatoare: 0.5, 0.25, 0.125 si 0.125. Entropia este data de:

H(X) = – (0.5 log 0.5 + 0.25 log 0.25 +

+ 0.125 log 0.125 + 0.125 log 0.125) =

= – 0.5 log 0.5 – 0.25 (log 0.25 + log 0.125)

= 1.75 biti.

EntropiaEntropia

CoduriCoduriCod: O secventa de simboluri (cuvinte ale sursei) reprezentate printr-o

alta secventa numita cuvant de cod.

Codurile unic decodabile sunt acele coduri pentru care cuvintele sursei pot fi recuperate in mod unic dintr-o secventa de cod (reprezentare 1 – la –1 fara pierderi).

Exemplu de coduri unic decodabile: coduri – prefix. La acest cod nici un cuvant de cod nu este prefixul altui cuvant de cod.

CoduriCoduriExemplu 3: Fie urmatorul alfabet de simboluri sursa X = {a, b, c, d}. Fie

o functie f care converteste X in cuvintele de cod binare B = {1, 01, 000, 001}. Acest cod este unic decodabil (nici un cuvant de cod din B nu este prefixul altuia). Daca luam ca multimea cuvintelor de cod sa fie {0, 01, 10, 11} , atunci f nu este unic decodabila (0 este prefixul lui 01). De exemplu ac ≠ ba, dar f*(ac) = f(a)f(c) = 010 = f(b)f(a) = f*(ba). Un exemplu de cod unic decodabil dar care nu este de tip prefix este urmatorul B = {0, 01, 011, 0111}.

Coduri Coduri blocblocDefinitie : O codare de tip bloc de ordinul n este o functie care atribuie

fiecarui bloc de n caractere consecutive o secventa de biti de lungime variabila.

Exemplu 4: sa consideram pentru inceput ca avem la dispozitie o sursa cu un alfabet compus doar din 2 litere : X = {a, b}. In acest caz literele ‘a’si ‘b’ au o probabilitate egala de aparitie.

Codare bloc de ordinul 1 : In acest caz fiecare caracter este reprezentat pe singur bit.

Coduri Coduri blocblocCodare bloc de ordinul 1 : In acest caz fiecare caracter este reprezentat

pe un singur bit.

In cazul de mai sus avem nevoie de 24 de biti pentru reprezentarea celor 24 de caractere – o medie de 1 bit / caracter.

Bloc p(Bloc) Cuvant de cod

a 0,5 0b 0,5 1

R = 1 bit/caracter

Coduri Coduri blocblocCodare bloc de ordinul 2: In acest caz fiecare pereche de caractere este

reprezentata pe unul, doi sau trei biti.

In cazul de mai sus avem nevoie de 20 de biti pentru reprezentarea celor 24 de caractere – o medie de 0.83 biti / caracter.

Bloc p(Bloc) Cuvant de cod

aa 0,45 0bb 0,45 10ab 0.05 110ba 0.05 111

R = 0,825 biti/caracter

CoduriCoduri blocblocCodare bloc de ordinul 3: In acest caz fiecare triplet de caractere este

reprezentata pe unul pana la 6 biti (17 biti pentru 24 caractere = 0.71 biti / caracter).

Bloc p (Bloc) Cuvant de codaaa 0,405 0bbb 0,405 10aab 0.045 1100abb 0.045 1101bba 0.045 1110baa 0.045 11110aba 0.005 111110bab 0.005 111111

R = 0,68 biti/caracter

Lungimea coduluiLungimea coduluiUn cod unic decodabil f pentru o variabila aleatoare X are lungimea

egala cu:

unde l(x) este lungimea (numarul de simboluri de cod) codului asociat lui x

Exemplu 4: Fie C codul – prefix pentru exemplul 3 cu probabilitatile 0,5; 0.25; 0.125; si 0,125. Lungimea codului este L(C) = 0,5 * 1 + 0,25*2 + 0.125*3 + 0.125*3 = 1.75. Pentru celalalt cod unic decodabil avem: L(C)= 0,5 * 1 + 0,25*2 + 0.125*3 + 0.125*4 = 1.875.

∑==x

xlxPXlECL )()()}({)(

Coduri optimaleCoduri optimaleUn cod sursa este optim daca are lungimea L(C) cea mai mica.

Prima teorema a lui Shannon: Orice cod optim satisface relatia:

1)()()( +<≤ XHCLXH

CodareaCodarea de tip Huffmande tip HuffmanCodarea de tip Huffman este un algoritm des folosit pentru proiectarea

unui cod – prefix (cand se cunosc variabilele – probabilitatile).

Codarea de tip Huffman este folosita in standardele mai vechi de imagine si video (standardul JPEG pentru imagini, MPEG – 2 si H – 263 pentru video).

Cand este cunoscuta distributia de probabilitati a unei surse discrete, algoritmul de codare Huffman furnizeaza o procedura sistematica de proiectare pentru a obtine lungimea optima a cuvantului de cod.

Codul Codul HuffmanHuffmanProiectarea codurilor Huffman implica 2 pasi: generarea simbolurilor si atribuirea codurilor:

Generarea simbolurilor: se formeaza arborele de codare Huffman in felul urmator:

a. Aranjarea probabilitatii simbolurilor pi in ordine descrescatoare si stabilirea acestora ca fiind frunzele arborelui.

b. Repetarea urmatorilor pasi pana cand ramurile se restrang intr-un nod:

i. Cele doua noduri cu cele mai mici probabilitati converg si formeaza un nou nod cu probabilitatea egala cu suma probabilitatilor celor doua noduri.

ii. Se atribue „1” si „0” perechii de ramuri care converge intr-un nod.

Codul Codul HuffmanHuffmanAtribuirea codurilor; cuvantul de cod pentru fiecare simbol este o secventa binara de la radacina arborelui catre frunza in care probabilitatea simbolului este localizata.

Exemplu 5: Se considera o sursa discreta continand 5 simboluri {a, b, c, d, e}cu o probabilitate de distributie {0.4, 0.14, 0.2, 0.2, 0.06}. Procedura de codare Huffman si rezultatele acestei codari sunt ilustrate in urmatoarele figuri. Se observa ca in timpul procesului de convergenta poate apareaposibilitatea ca doua sau mai multe probabilitati sa fie egale. De exemplu, la pasul 2 in fig. (a), probabilitatea simbolurilor d si e este egala cu probabilitatea simbolurilor b si c. In caz de egalitate alegerea convergentei poate fi arbitrara, iar codurile rezultate pot fi diferite, avand aceeasi rata medie de bit si aceeasi rata de compresie dupa cum poate fi verificat utilizand exemplele de coduri din fig. (a) si (b).

CodulCodul HuffmanHuffman1) Generarea simbolurilor 2) Atribuirea codurilor

Simbol Cuvant de cod

d 1110

e 1111

CodulCodul HuffmanHuffmanExemplu 6: Cuvintele de cod Huffman pentru alfabetul {e, o, a, i, u} cu

o probabilitate de distributie {0.42, 0.30, 0.12, 0.09, 0.07} sunt urmatoarele:

1) Generarea simbolurilor 2) Atribuirea codurilor

Simbol Cuvant de cod

i 0100

u 0101

CodareaCodarea aritmeticaaritmeticaDezavantajele codului Huffman: lungimea alfabetului creste, nu este

adaptabil (ca lungime), etc.

O solutie: Codul Aritmetic.

Idea de baza este folosirea probabilitatilor (simbolurilor) ca si cuvinte de cod.

Codarea sursei in cuvinte de cod se face secvential folosindu-se functia de repartitie cumulativa:

Codurile aritmetice adaptice sunt folosite in standardele actuale de compresie a imaginii (JPEG2000) si video MPEG – 4 si H.264.

kx kxpiF

Codarea aritmeticaCodarea aritmeticaCodarea aritmetica se imparte in 2 etape:

Generarea unei etichete pentru o secvenţă dată de mesaje;

Etichetei i se atribue un cod binar.

Generarea unei etichete:

Se începe cu intervalul [0,1].

Funcţia de repartiţie a variabilei aleatoare asociate sursei este folosită la împărţirea intervalului de lungime 1 în subintervale de forma [Fx(xi-1), Fx(xi)], proporţionale cu valorile funcţiei de repartiţie.

Apariţia primului mesaj din secvenţă restricţionează intervalul care conţine eticheta la unul din subintervale.

Codarea aritmeticaCodarea aritmeticaGenerarea unei etichete:

Se presupune că primul mesaj este sk şi x(sk)=xk; atunci intervalul care conţine valoarea etichetei va fi subintervalul [Fx(xi-1), Fx(xi)].

Acesta este partiţionat în subintervale proporţionale cu valorile funcţiei de repartiţie, la fel ca intervalul original.

Fiecare mesaj care urmează impune ca eticheta să fie restricţionată la un subinterval care este partiţionat în continuare în aceleaşi proporţii.

În general, pentru o secvenţă x = x1x2, …, xn, se poate arăta călimita superioară şi cea inferioară a intervalului etichetei pot fi calculate recursiv, cu relaţiile:

unde prin l(n) şi u(n) s-au notat limitele inferioară, respectiv, superioară a intervalului ce conţine eticheta corespunzătoare succesiunii de n mesaje.

În relaţiile de mai sus se va considera l(0) = 0 şi u(0) =1 deoarece înainte de a furniza mesajele intervalul iniţial se consideră [0,1].

( ) )1()1()1()1( −−+= −−−nx

nnnn xFlull

( ) )()1()1()1(nx

nnnn xFlulu −−− −+=

În final eticheta sa ia fie la mijlocul intervalului final

fie limita inferioara a intervalului

DE RETINUT: Pentru codarea unui mesaj folosind un cod aritmetic este necesara cunoasterea alfabetului, probabilitatile de aparitie a simbolurilor si a mesajului de codat.

)()( nn

xluxT +

)()( nx lxT =

Codarea aritmeticaCodarea aritmeticaExemplu 6: Fie sursa cu alfabetul S = {s1,s2,s3}, cu p(s1) = 0.8, p(s2) =

0.02, p(s3) = 0.18. Se defineşte variabila aleatoare x(si) = i şi se doreşte a coda secvenţa 1321.

Din modelul de probabilitate se obţine Fx(k) = 0, Fx(1) = 0.8, Fx(2) = 0.82, Fx(3) = 1, pentru k > 3.

Se iniţializează cu u(0) = 1, l(0) = 0.

Primul element al secvenţei este 1:

l(1) = 0 + (1 – 0)*0 = 0

u(1) = 0 + (1 – 0)*0.8 = 0.8

adică eticheta este conţinută în intervalul [0, 0.8).

Codarea aritmeticaCodarea aritmeticaUrmătorul element este 3:

l(2) = 0 + (0.8 – 0)*Fx(2) = 0.656

u(2) = 0 + (0.8 – 0)* Fx(3) = 0.8

intervalul care conţine eticheta pentru secvenţa 13 este [ 0.656; 0.8).

În continuare urmează 2:

l(3) = 0.656 + (0.8 – 0.656)*Fx(1) = 0.7712

u(3) = 0.656 + (0.8 – 0.656)* Fx(2) = 0.77408

Intervalul urmator este [0.7712; 0.77408).

Codarea aritmeticaCodarea aritmeticaUrmează 1 şi limitele intervalului devin :

l(4) = 0.7712 + (0.77408 – 0.7712)*Fx(0) = 0.7712

u(4) = 0.7712 + (0.77408 – 0.7712)* Fx(1) = 0.773504

Eticheta este:7712.0)1321( =xT

Decodarea aritmeticaDecodarea aritmeticaIntervalul care conţine eticheta este o submulţime a fiecărui interval

obţinut la codare.

Se urmăreşte a se decoda elementele din secvenţă astfel încât valoarea etichetei să fie cuprinsă între limitele l(k) şi u(k) pentru fiecare k.

DE RETINUT: Pentru decodarea unui mesaj codat in cod aritmetic (asacum se prezinta la intrarea unui decodor) este necesara doar cunoasterealungimii mesajului, alfabetului, probabilitatilor de aparitie a simbolurilor in alfabet si a etichetei.

Decodarea aritmeticaDecodarea aritmeticaExemplu 7: Fie eticheta . Sa se decodeze mesajul

x1x2x3x4 codat cu un cod aritmetic avand eticheta de mai sus si alfababetul S = {s1,s2,s3}, cu p(s1) = 0.8, p(s2) = 0.02, p(s3) = 0.18.

Rezolvare:

Fx(k) = 0, Fx(1) = 0.8, Fx(2) = 0.82, Fx(3) = 1.

Se începe cu l(0) = 0 şi u(0) = 1.

După decodarea primului element din secvenţă , x1, limitele devin

l(1) = 0 + (1 – 0)* Fx (x1 – 1) = Fx (x1 – 1)

u(1) = 0 + (1 – 0)*Fx(x1) = Fx (x1)

Este necesară aflarea valorii lui x1 pentru care valoarea etichetei 0.7712cade în intervalul obţinut.

07712)( 4321 =xxxxTx

Decodarea aritmeticaDecodarea aritmeticax1 = 1, rezultă intervalul [0; 0,8),

x1 = 2, rezultă intervalul [0,8; 0,82),

x1 = 3, rezultă intervalul [0,82; 1).

Cum eticheta este conţinută în primul interval, se decide x1 = 1.

Se continua (NOUL INTERVAL ESTE CEL ASOCIAT LUI x1 = 1 !):

l(2) = 0 + (0,8 - 0)* Fx (x2 – 1) = 0.8*Fx (x2-1)

u(2) = 0 + (0,8 - 0)*Fx(x2) = 0.8*Fx (x2)

x2 = 1, rezultă intervalul [0; 0,64),

x2 = 3, rezultă intervalul [0,656; 0,8).

Decodarea aritmeticaDecodarea aritmeticaEticheta este conţinută în ultimul interval, aşa că se decide x2 = 3.

Se continua (NOUL INTERVAL ESTE CEL ASOCIAT LUI x2 = 3 !):

l(3) = 0,656 + (0,8 – 0,656)* Fx (x3 – 1) = Fx (x3 – 1)

u(3) = 0,656 + (0,8 – 0,656)*Fx(x3) = Fx (x3)

x3 = 3, rezultă intervalul … ?

Eticheta este conţinută în al doilea interval, aşa că se decide x3 = 2.

Decodarea aritmeticaDecodarea aritmeticaSe continua (NOUL INTERVAL ESTE CEL ASOCIAT LUI x3 = 2 !):

l(4) = 0,7712 + (0.77408 – 0,7712 )* Fx (x4 – 1) = Fx (x4 – 1)

u(4) = 0,7712 + (0.77408 – 0,7712 )*Fx(x4) = Fx (x4)

x4 = 1, rezultă intervalul [0.7712; 0.773504 ),

x4 = 2, rezultă intervalul [0.773504; 0.7735616),

x4 = 3, rezultă intervalul … ?

Eticheta este conţinută în primul interval, aşa că se decide x4 = 1.

In final se obtine x1x2x3x4 = 1321.

Codul Lempel Codul Lempel –– ZivZivCodul Lempel – Ziv si variantele sale sunt metode care combina

modelarea cu codarea. Aceste coduri sunt alcatuite din 2 etape: atribuirea de probabilitati (formarea unui dictionar) urmata de o codare aritmetica cod aritmetic adaptiv.

Cele doua variante de baza LZ77 (cu fereastra glisanta) si LZ78.

O varianta des intilnita este codul Lempel – Ziv – Welch (LZW) folosit in aplicatii ca: formatul de imagine fara pierderi Graphical Interchange Format (GIF), Portable Document Format (PDF - Adobe Acrobat), PostScript (PS).

Codul Lempel Codul Lempel –– ZivZivIdea de baza: folosirea sirurilor curente pentru predictia sirurilor viitoare.

Crearea unui dictionar cu ajutorul sirurilor curente disponibile si atribuirea uni index de dictionar pentru cel mai lung sir care se potriveste cu datele curente. Urmatorul simbol (care nu se potriveste) este folosit pentru expandarea dictionarului.

Codul Lempel Codul Lempel –– ZivZivExemplu:

Codarea diferentialaCodarea diferentialaIdea de baza: in loc sa se codeze direct sursa semnalului, se codeaza

diferenta dintre semnalul curent si predictia sa (semnalul ce urmeaza).

Aceasta abordare se numeste codare predictiva sau diferentiala.

Codarea diferentiala se bazeaza pe corelatia spatiala sau temporala dintrepixeli.

Valorile diferenta au de regula o gama dinamica mica.

Cand aceste valori se cuantizeaza metoda se numeste Modulatia Diferentiala a Implusurilor in Cod (MDIC).

Un caz special este Modulatia Delta.

Procesul de codare implica operatia de transformare, cuantizare si atribuire a codului.

Codarea diferentialaCodarea diferentialaDesi MDIC este simpla, nu ofera o compresie eficienta.

Imaginea digitala este reprezentata printr-o matrice (tablou 2D) in care pixelii invecinati sunt puternic corelati (prezenta redundantei spatiale).

Diferenta dintre valorile corespunzatoare nivelurilor de gri are o varianta mai mica decat imaginea originala pentru acelasi numar de biti / esantion eroarea de cuantizae va fi mai mica.

La codarea MDIC de tip pixel – cu – pixel (nu codare bloc), valoarea pixelului precedent este folosit ca predictor, semnalul diferenta avand expresia:

1iiiii zzzzd −−=−= ˆ

Codarea diferentialaCodarea diferentialaVersiunea cuantizata a diferentei este data de expresia:

unde cu eq s-a notat eoarea de cuantizare.

La decodare, valoarea pixelului reconstituit este data de expresia:

Aparitia erorii numerice de acumulare !

Pentru evitarea acestei erori predictia la codare trebuie sa fie identica cu cea de la decodare.

Din acest motiv, la codare se folosesc valorile reconstituite a esantioanelor codate anterior in loc de valorile reale.

qiii eddQd +== )(ˆ

ri dzz ˆ

1 += −

Codarea diferentialaCodarea diferentialaLa codare, semnalul diferenta ia valoarea:

adica valoarea anterioara reconstituita este folosita ca predictor

La codare se simuleaza decodarea in bucla de predictie pentru evitarea erorilor de acumulare.

De regula se foloseste cuantizorul Lloyd – Max.

Predictorul este proiectat pentru cazul unor erori de cuantizare zero, iar cuantizorul este astfel proiectat sa minimizeze eroarea de cuantizare.

Dupa operatia de cuantizare se aplica un algoritm de codare fara pierdericum ar fi codarea Huffman sau aritmetica.

riii zzd 1−−=

riz 1− iz

Predictie liniaraPredictie liniaraIntr-un sistem MDIC, versiunea prognozata a unui esantion poate fi

descrisa ca o functie avand ca argumente esantioanele anterioare reconstituite:

In cazul unei predictii liniare avem functia respectiva se poate exprima:

unde aj sunt coefficientii de predictie.

( )rni

rii zzfz −−= ,...,ˆ 1

rjiji zaz

Predictia liniaraPredictia liniaraSemnalul, diferenta este dat de iar valoarea cuantizata a

lui este .Versiunea reconstituita:

Eroarea de predictie este

In general coeficientii de predictie sunt selectati in asa fel incat valoarea erorii medie patratica este minimizata.

Distorsiuni tipice la codarea intracadru (in interiorul cadrului):

Zgomot granular: zgomot aleator in zonele uniforme ale imaginii.

Discontinuitati de muchie.

iii zzd ˆ−=id

iiri dzz ˆˆ +=

iii zze ˆ−=

Codarea diferentiala intercadruCodarea diferentiala intercadruCodarea secventelor de imagini (video) se numeste codarea intercadru.

Cadrele succesive contin, in mare parte, informatie redundanta.

In codarea 3D – MDIC se exploateaza ambele tipuri de redundanta: spatiala si temporala.

Se foloseste scanarea intretesuta si doar liniile pare sau impare ale cadrului prezent sunt achizitionate simultan.

Daca se proceseaza liniile pare, liniile impare al cadrului curent sunt de asemenea disponibile (vecinii de sus ai liniei pare) si vecinii scanati deja, in asa fel incat este possibila predictia.

Mai mult, liniile pare si impare ale cadrului precedent sunt dispoibile.

Codarea predictiva Codarea predictiva cu cu compensare compensare a a miscariimiscariiPentru o rata de cadru suficient de mare, modificarile care apar de la

cadru la cadru pot fi atribuite deplasarii (miscarii) obiectelor pe durata secventei video (de – a lungul cadrelor).

Daca ar fi posibila analiza miscarii obiectelor din cadrele succesive am putea estima pozitia lor in cadrele urmatoare prin predictia pozitiei lor din cadrele anterioare.

In acest caz s-ar cuantiza si coda doar diferenta dintre cadrul real si cel estimat.

Aceasta abordare se numeste Codare Predictiva cu Estimare a Miscarii, metoda adoptata la majoritatea standardelor de codare video.

Coordonatele vectorului Coordonatele vectorului de de miscaremiscareEroarea medie patratica

Eroarea medie absoluta

Codarea transformateiCodarea transformateiIn cazul codarii transformatei, pentru obtinerea compresiei se tine cont

de corelatia intracadru (intre pixeli).

Codarea transformatei este o tehnica fundamentala in compresia imaginilor statice.

Este folosita si in compresia video pentru informatiei intracadru si a erorii de predictie in codarea predictiva cu compensare a miscarii.

Codarea transformatei este folosita in standarde ca: JPEG, JPEG2000, MPEG 1 – 4, si ITU H.261, H.263, H.264.

In codarea transformatei se urmareste reducerea corelatiei dintre pixeli reducerea redundantei spatiale.

Pixelii ce contin informatie redundanta sunt eliminati.

Principiile compresiei Principiile compresiei videovideoCodarea intercadru predictiva sta la baza codecurilor video actuale si

este folosita la H.261, H.263, MPEG – 1, 2 si 4.

Cele trei principii fundamentale de reducere a redundantei:– Reducerea redundantei spatiale dintre pixelii imaginii (eliminarea

sau transformarea pixelilor similari) aplicarea transformatelor.– Reducerea redundantei temporale pentru eliminarea

similaritatilor dintre cadrele succesive codarea diferentelor dintre cadre.

– Codarea entropiei pentru reducerea redundantei dintre simbolurile de informatie tehnici de codare cu lungime variabila (Huffman, coduri aritmetice, etc).

– PLUS: Redundanta psihovizuala Redundanta spectrala !

Sistemul Vizual Uman si Perceptia vizualaSistemul Vizual Uman si Perceptia vizualaSistemul vizual uman (SVU) este EXTRAORDINAR de perfect in

recunoasterea faciala la o rezolutie extrem de scazuta.

De ce ? Rezolutie scazuta imagine de frecventa joasa.

Detaliile nu sunt importante si sunt eliminate (corespunzatoare frecventelor inalte) !!!

Informatia (energia) relevanta (dpdv vizual) este concentrata in spectrul frecventelor joase !

Sistemul Vizual Uman si Perceptia vizualaSistemul Vizual Uman si Perceptia vizuala

Rezolutia: 32 x 25 pixeli ! Rezolutia: 638 x 495 ~ factor de rezolutie = 20 x

1. Imaginile de tip RGB convertite in spatiu de culoare reprezentat mai eficient (eliminarea redundantei) + predictia distorsiunilor de culoare.

2. Descompunerea imaginilor in componente de frecvente spatiale orientate (asemanator modelului de filtrare de tip undisoara Gabor – o descompunere eficienta).

3. Masurarea contrastului local prin transformari neliniare aproximare prin folosirea amplitudinilor coeficientilor undisoara.

4. Senzitivitatea SVU scade cu cresterea frecventelor spatiale => necesitatea compensarii Functiei de Senzitivitate a Contrastului (FSC).

5. Efectul de mascare prezice ce cantitate de zgomot de cuantizare (ce apare in momentul compresiei- codarii) poate fi “ascuns” (mascat de) in semnalul original fara afectarea vizibila a calitatii imaginii.

Efectul de mascare mascarea unei zone din imagine de catre alta zona apropriata in spatiu si cu caracteristici spaiale si de frecventa similare contrast mult mai puternic pentru a 2-a zona fata de prima.

6. Combinarea tuturor informatiilor (descompuse in componente defrecvente spatiale diferite si prelucrate de pasii de mai sus) pentru generarea tabloului intreg aproximarea datelor (imaginii) originale cu varianta comprimata, la nivelul SVU.

Sistemul Vizual Uman si Perceptia vizualaSistemul Vizual Uman si Perceptia vizualaExemplu de descompunere pentru imaginea “Becalli”

Sistemul Vizual Uman si Perceptia vizualaSistemul Vizual Uman si Perceptia vizualaExemplu de mascare a contrastului

Redundanta psihovizuala Redundanta psihovizuala –– Perceptia vizualaPerceptia vizualaRedundanta spectrala se manifesta la nivelele inferioare ale sistemului

vizual uman (primele trei nivele ale retinei).

Peceptia vizuala se manifesta la nivelele superioare ale sistemului vizual uman cerebel.

Perceptia vizuala este extrem de complexa.

Redundanta psihovizuala Redundanta psihovizuala –– Perceptia vizualaPerceptia vizualaLGN – Lateral Geniculate Nucleus – 6 nivele - perceptia informatiei de

luminanta (celule ganglionare specializate).

Cortexul vizual – V1 … AIT.

V1 (cortexul vizual primar) – 6 nivele sunt stimulate - transmit implusuri catre nivelele superioare atunci cand sunt stimulate de catre:

muchii orientate;

diverse frecvente spatiale;

diverse frecvente temporale;

locatii spatiale particulare;

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUObiecte ireale (imposibile):

Triunghiul lui Oscar Reutersward

Interpretarea 3D – mentala

a modelului !

Creierul uman percepe stimulul

vizual pe componente locale si apoi

le imbina pentru alcatuirea intregului

Triunghiul ca intreg – IMPOSIBIL DE REALIZAT ! - PARADOX

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzii ambigue:

Ambiguitate de perceptie

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzii de distorsiune:

Efectul este cauzat

de celulele neuronale

sensibile la orientare.

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzii de distorsiune:

Spirala lui Fraser:

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzie de camuflaj:

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUInhibitie laterala contrast simultan:

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUContrast simultan :

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzie de miscare:

Iluzii opticeIluzii optice -- ImperfectiunileImperfectiunile SVUSVUIluzie de adancime:

Perceptia vizualaPerceptia vizualaSensibilitatea ochiului uman la REZOLUTIE este functie de distanta !

Corelarea datelorCorelarea datelorFie doi vectori (variabile) a = (1, 2, 3, 4, 3, 2, 1) si b = (3, 5, 7, 9, 7, 5, 3).

Spunem despre cei doi vectori ca sunt puternic corelati pozitiv, deoarece ai > ai-1 implica bi > bi-1 si ai < ai-1 implica bi < bi-1 (daca se cunoasteevolutia lui a putem prezice evolutia lui b) coeficientul de corelatie R ~ +1.

Corelare pozitiva cei doi vectori se modifica in acelasi sens.

Daca b = (9, 7, 5, 3, 5, 7, 9) ai > ai-1 implica bi < bi-1 si ai < ai-1 implicabi > bi-1 cei doi vectori sunt puternic corelati negativ coeficientul de corelatie R ~ –1 .

Daca evolutia ai > ai-1 sau ai < ai-1 nu se spune nimic despre bi si bi-1 cei doi vetori nu sunt corelati coeficient de corelatie R ~ = 0.

Corelarea datelorCorelarea datelor

a) R ~ +1 b) R ~ – 1 c) R ~ 0R = Cab / Ca*Cb, unde Cab este maricea de covarianta a celor doi

vectori a si b iar Ca si Cb sunt variantele celor doi vectori

Corelarea datelor Corelarea datelor –– corelare intracadru corelare intracadru ((spatialaspatiala))

Corelarea datelorCorelarea datelor –– corelare corelare intracadruintracadru((spatialaspatiala))

Corelarea coloanelor (sau liniilor) dintr-o imagine

Linia R(1) R(2) R(3) R(4) R(5) R(6) R(7) R(8)

62 0.93 0.85 0.78 0.73 0.67 0.61 0.54 0.45

63 0.92 0.83 0.77 0.72 0.65 0.59 0.52 0.43

64 0.93 0.86 0.82 0.75 0.67 0.61 0.54 0.45

65 0.92 0.85 0.81 0.75 0.67 0.61 0.54 0.46

66 0.91 0.83 0.78 0.71 0.64 0.59 0.51 0.42

med 0.92 0.84 0.79 0.73 0.66 0.60 0.53 0.44

Corelarea datelor Corelarea datelor –– corelare corelare intercadruintercadru((temporalatemporala))

Corelarea temporala dintre doua cadre

Informatia mutuala masoara cantitatea de informatie redundanta(corelatia):

∑∑ ⎟⎟⎠

⎞⎜⎜⎝

yx ypxpyxpyxpYXI

)()(),(log),();(

Informatia mutuala: 1&2 = 2.04, 1&3 = 1.91, 1&4 = 1.63, 2&3 = 1.93, 2&4 = 1.56, 3&4 = 1.43

Corelarea datelorCorelarea datelor –– corelare corelare intercadruintercadru((temporalatemporala))

Informatia mutuala: 0.06 !

Decorelarea datelorDecorelarea datelorDecorelare REDUCEREA REDUNDANTEI (spatiale sau

temporale)! COMPRESIE !

Decorelare prin aplicarea transformatelor.

Transformarea datelor este posibila deoarece energia unui semnal(pentru imagini naturale) este concentrata in majoritate in regiunea frecventelor joase (un numar mic de coeficienti de transformare sunt necesari pentru reprezentarea apxoximativa a semnalului).

Coeficientii de transformare pot fi ulterior cuantizati codare cupierderi (valorile originale ale semnalului nu mai pot fi reconstituite)!

Decorelare prin transformarea datelor rotirea datelor, “albire”, vectori singulari, etc.

Decorelarea datelorDecorelarea datelorExemplu de transformare - rotire.

Fiecare pixel pe x1 si x2 sunt puternic corelati (pe o directie de 450).

Daca se rotesc axele cu 450, aparitia comuna a pixelilor de-a lungul axei y1 au odistributie uniforma, dar, de-a lungul axei y2 majoritatea sunt concentrati in jurul valorii zero Consecinta: in medie y1 si y2 pot fi reprezentati la o rata de biti maimica decat pixeli de pe x1 si x2 compresie !

Decorelarea datelorDecorelarea datelorTransformarea spatiului (x1, x2) in (y1, y2) prin rotirea cu 450 se realizeaza cu

ajutorul matricei de rotatie:

y1 se numeste valoarea medie (sau componenta continua), iar y2 componenta reziduala.

Energia din domeniul pixel este egala cu energia din domeniul transformatei (matrice de transformare este ortonormata (Teorema lui Parseval).

Decorelarea datelorDecorelarea datelorExemplu de transformare – rotirea unei imagini.

Ditributia pixelilor pe X inainte de rotatie

Ditributia pixelilor pe Y inainte de rotatie

Ditributia pixelilor pe X dupa rotatie

Ditributia pixelilor pe Y dupa rotatie

Imagine

Transformata Transformata de de ““albirealbire””Pasi: 1. Determinarea vectorilor singulari ai matricei de covarianta Cx:

2. Aplicarea transformatei:

z = Λ-1/2QTx

Matricea Λ-1/2 este inversa matricei diagonale Λ1/2 ale carei elemente sunt egale cu radacina patrata a valorilor proprii. Matricea de covarianta transformata:

Cz = [Λ-1/2QT]Cx[Λ-1/2QT]T = I

ne spune ca efectul transformatei este rotirea sistemului de coordonate si scalarea matricei de covarianta la matricea identitate.

A = Q ΛQT

Transformata Transformata de de ““albirealbire””Exemplu de transformare – decorelarea pixelilor dintr-o secventa de imagini prin

metoda de “albire” – reducerea redundantei temporale.

Sus: Datele originale. Jos: Datele decorelate. Coeficentul de corelatie dintre imagini este:

Inainte de “albire”: 1&2 = 0.97, 1&3 = 0.94, 1&4 = 0.90, 2&3 = 0.97, 2&4 = 0.90, 3&4 = 0.92

Dupa “albire”: 1&2 = – 0.14, 1&3 = – 0.05, 1&4 = – 0.44, 2&3 = 0.01, 2&4 = – 0.42, 3&4 = – 0.56

Codarea transformateiCodarea transformateiLa receptie datele codate sunt decodate si imaginile sunt reconstituite.

Alocarea bitului: in domeniul transformatei se aplica operatii cum ar fi trunchiere, cuantizare si atribuirea cuvintelor de cod.

Transformate folosite: Transformata Discreta Karhunen – Loeve(TDKL), Transformata Cosinus Discreta (TCD) si Transformata Undisoara(TU).

Elemente fundamentale Elemente fundamentale de de transformaretransformareOperatia de transformare este un procedeu (functie) care transforma

semnalul initial x(t) obtinandu-se o noua reprezentare a semnalului y(t).

Transformata se numeste liniara daca semnalul rezultant se obtine prin combinatii liniare a semnalului initial:

y = Tx

unde T reprezinta matricea de transformare.

In cazul imaginilor, fiecare imagine poate fi reprezentata cu ajutorul imaginilor de baza obtinute prin transformare.

Pentru o imagine de dimensiune N x N exista N2 imagini de baza.

La majoritatea standardelor de compresie (JPEG, MPEG – 1, MPEG –2), N = 8 64 imagini de baza.

Elemente fundamentale Elemente fundamentale de de transformaretransformareLa receptie se aplica operatia inversa transformarii.

Daca transformata este ortogonala, adica T*TT = I, unde I este matricea unitate, transformata inversa se simplifica: T-1 = TT.

In acest caz, daca nu exista cuantizare, imaginea poate fi reconstituita fara eroare.

Ideea de baza a unei transformate: concentrarea energiei semnalului in cat mai putin coeficienti de transformare.

Compresia se poate obtine prin setarea la valoarea zero ai acelor coeficienti (de valoare mica) care nu depasesc un prag prestabilit.

Transformata Transformata FourierFourierTransformata Fourier conduce la determinarea spectrului unui semnal.

Transformata Fourier reprezinta un semnal printr-o suma de semnale (componente) sinusiodale.

Componentele sinusoidale si cosinusoidale sunt functii de baza ortogonale. Reprezentarea este unica si fiecare coeficient Fourier reprezinta contributia unei componente sinusiodale la o anumita frecventa.

Semnalele periodice sunt reprezentate foarte eficient cu ajutorul transformatei Fourier.

Daca semnalul prezinta zone de tranzitie, transformata Fourier nu mai este eficienta.

Transformata Transformata FourierFourierIn acest caz se poate folosi o fereastra (masca) pe “suprafata” careia sa

poate aplica transformata Fourier.

Transformata Fourier nu contine informatii despre translatarea in timp sau spatiu a unui semnal.

Se poate folosi transformata Fourier scurta (de tip “short – time”).

Valori si vectori singulariValori si vectori singulariλ se numeste valoare singulara a matricei A daca indeplineste relatia:

det (A – λI) = 0

si fiecare solutie λ are un vector singular corespunzator x:

Ax – λx

Suma valorilor singulare ale lui A este egala cu suma elementelor sale de pe diagonala.

Produsul valorilor singulare ale lui A este egala cu determinantul sau.

Valori si vectori singulariValori si vectori singulariSa presupunem ca matrica A de dimensiune n x n are n vectori singulari

independenti. Daca acesti vectori sunt ordonati in coloanele matricei S, atunci avem relatia:

S-1AS = Λ si A = S Λ S-1

unde Λ este o matrice diagonala cu elementele formate din λ.

O matrice A simetrica si cu elemente reale poate si descompusa in

A = Q ΛQT

unde Q contine vectori singulari ortogonali si Λ valorile singulare corespunzatoare.

Transformata Karhunen Transformata Karhunen -- LoeveLoeveTransformata Karhunen – Loeve (TKL) este o transformata optima

d.p.d.v. al erorii medie patratice.

TKL concentreaza cea mai mare parte a energiei unui semnal de lungime n in l ≤ n coeficienti de transformare.

Eroarea medie patratica de reconstructie este data de suma variantei componentelor eliminate (nu se iau in considerare erorile de cuantizare sautransmisie).

TKL este o transformata ortogonala ce decoreleaza componentele unui semnal: y = Tx si x = TTy

unde vectorii de pe liniile lui T sunt vectorii proprii ai matricei de covarianta a semnalului x.

Transformata Karhunen Transformata Karhunen -- LoeveLoeveMatricea de corelatie a unui semnal transformat este o matrice diagonala.

KLT se bazeaza pe descompunerea in vectori proprii ai matricei de covarianta.

Desi transformata este optima, KLT este rareori folosita in practica datorita timpului de calcul mare (complexitate de calcul) necesar descompunerii in vectori proprii

Mai mult, KLT deoinde si de natura datelor.

In practica se folosesc alte transfomari sub-optimale (dar cu rezultate apropiate de cele obtinute de KLT) cum ar fi transformata Haar, Transformata Cosinus Discreta.

ReducereaReducerea dimensionalitatii dimensionalitatii -- ACPACPReducerea dimensionalitatii datelor – o metoda statistica este descrisa de

analiza conmponentelor principale (ACP).

ACP transforma datele in asa fel incat un vector de observatie de dimensiune d este inlocuit de k combinatii liniare a variabilelor datelor initiale. (k < d !)

Definitie: Fie x un vector de dimensiune d si variabile aleatoare cu media μ si matricea de covarianta (dispersie) Σ . Fie U = (u1, u2, …, ud) o matrice ortogonala in asa fel incat are loc relatia:

UT Σ U = Λ = diag(λ1,λ2, … λd)

unde sunt valorile singulare asociate lui Σ, iar

este componenta pricipala j.dλλλ ≥≥≥ L21

( ) ( )μxuμxUv −=−= Tj

ReducereaReducerea dimensionalitatiidimensionalitatii -- ACPACPComponentele principale standardizate:

Vectorii singulari uj sunt de lungime unitara.

Componentele yj sunt decorelate si var (yj) = λj

Proprietati: Varianta cea mai mare a semnalului este continuta in primul vector principal.

jj yz 2/1−= λ

Transformata Cosinus DiscretaTransformata Cosinus DiscretaTransformata Cosinus Discreta (TCD) este larg utilizata in codarea audio

si video.

Spre deosebire de ACP, TCD este independenta de natura datelor.

TCD bidimensionala directa definita pentru un bloc de dimensiune N x Neste reprezentata de relatia:

Valorea pixelului in pozitia (i,j) este sij iar Suv reprezinta coeficientul de transformare.

⎥⎦⎤

⎢⎣⎡ +

⎥⎦⎤

⎢⎣⎡ +

= ∑∑−

ivuuv 2

v)12(cos2

u)12(cos21 1

Transformata Cosinus DiscretaTransformata Cosinus DiscretaTransformata inversa este data de relatia:

In cazul standard N = 8, i, j iau valori {0, …, 7}, iar TCD este data de:

TCD sta la baza standardului de compresie JPEG.

⎥⎦⎤

⎢⎣⎡ +

⎥⎦⎤

⎢⎣⎡ +

= ∑∑−

v)12(cos2

u)12(cos21 1

⎪⎩

⎪⎨⎧ ==

altfel

vudacaCC vu

⎥⎦⎤

⎢⎣⎡ +

⎥⎦⎤

⎢⎣⎡ +

= ∑∑== 16

v)12(cos16

u)12(cos41 7

ππ jisCCSj

Transformata Cosinus DiscretaTransformata Cosinus DiscretaImaginile de baza

ale TCD pentru un

bloc de dimensiune

8 x 8.

Frecventa crescatoare

Componenta continuua

Standardul JPEG – un standard de compresie a imaginii propus de ITU (International Telecommunication Union) si ISO (International Organization for Standardization).

JPEG = Joint Photographic Experts Group.

Caracteristici:

permite utilizatorului (aplicatiei) sa faca un compromis intre calitatea imaginii si rata de compresie dorita.

standardul este independent de tipul imaginii (nu exista constrangeri de imagini color, rezolutie, continut, etc).

complexitate de calcul relativ mica.

permite o scanare secventiala sau multipla (progresiva).

StandardulStandardul JPEGJPEG

Standardul Standardul JPEGJPEGStandardul JPEG foloseste TCD.

JPEG a devenit standard international in 1992.

JPEG include 2 tipuri de compresie de baza: compresie cu pierderi TCD si o metoda predictiva pentru compresia fara pierderi.

Cele patru moduri de operare sunt: secvential bazat pe TCD, progresiv bazat pe TCD, fara pierderi si hierarhic.

In cazul compresiei fara pierderi codarea predictiva este urmata de o codare cu cod Huffman sau cod aritmetic.

Standardul Standardul JPEGJPEG

Imagine necomprimata

01101101 …AC

Scanare zig-zag

Diferenta

Tabel cod entropieTabel Q

CuantizareTCD

Blocuri 8 x 8

- 128 Tabel cod entropie

Date comprimate (biti)

01101101 …DLV

Tabel cod entropie

Scanare zig-zag

DiferentaDecuantizare

Tabel Q

Imagine comprimata

Date comprimate (biti)

Sus: Schema bloc pentru compresia JPEG, Jos: Schema bloc pentru decompresia JPEG

Codarea canalului

Decodarea canalului

Codarea sursei

Decodarea sursei

Standardul Standardul JPEGJPEGPasii prezentati in continuare pentru codarea bazata pe compresia TCD

sunt corespunzatori imaginile pe nivele de gri.

Pentru imaginile color acesti pasi se repeta pentru fiecare componenta de culoare.

Pasii unei compresii bazate pe TCD sunt:

1. Pentru o imagine ale carei pixeli iau valori intre 0 si 255, din fiecare astfel de valoare se substrage 128. (In acest caz numarul de biti pentru reprezentare este B = 8, iar nivele de gri sunt 2B = 28 = 256).

Standardul Standardul JPEGJPEG2. Imaginea este impartita in blocuri (nesuprapuse) de dimensiune 8 x 8.

101 90 74 55 54 62 61 29

95 80 61 46 54 70 72 44

99 79 58 48 62 78 78 53

104 84 64 56 73 90 88 100

117 101 79 65 78 94 92 97

140 125 94 68 73 85 82 99

145 139 136 114 82 69 76 92

155 145 143 139 126 107 94 87

Standardul Standardul JPEGJPEGObservatie: Daca dimensiunea imaginii nu este o putere a lui 8, atunci

ultimele linii si coloane sunt multiplicate pentru a se obtine dimensiuneacorespunzatoare.

Observatie: Fiecare bloc este reprezentat inainte de compresie pe 64 de biti (28), iar dupa compresie, sa zicem, pe 0 pana la 20 de biti.

3. Fiecare bloc este transformat in domeniul frecventa prin aplicarea TCD bidimensionale. Vor rezulta 64 de coeficienti TCD si un spectru de frecventa de dimensiune 8 x 8.

Fiecare valoare din acest spectru reprezinta amplitudinea unei as anumite functii de baza.

Standardul Standardul JPEGJPEGAceste functii de baza sunt descrise de relatia:

Frecventele joase sunt situate in partea de sus – stanga a spectrului iar frecventele inalte in partea din dreapta – jos. Componenta continua (frecventa zero) b00 este situata in coltul din partea sus – stanga.

⎥⎦⎤

⎢⎣⎡ +

⎥⎦⎤

⎢⎣⎡ +

v)12(cos16

u)12(cosb ππ jiuv

Standardul Standardul JPEGJPEGFunctiile TCD de baza sunt ilustrate in figura de mai jos:

Standardul Standardul JPEGJPEGTCD calculeaza spectru unei imagini prin corelarea fiecarui bloc de

dimensiune 8 x 8 cu fiecare din aceste functii de baza.

Mai exact, valoarea spectrului se calculeaza prin multiplicarea functiilor de baza corespunzatoare cu valorile blocului si apoi prin insumarea produselor.

4. Coeficientii sunt cuantizati folosindu-se o matrice de cuantizare.

In proiectarea matricei de cuantizare se tine cont de compromisul dintre rata de compresie si fidelitatea (calitatea imaginii).

Proiectarea matricei de cuantizare tine cont de sensibilitatea ochiului uman in perceptia calitatii imaginii.

Standardul Standardul JPEGJPEGOchiul uman este mult mai sensibil la frecventele joase decat la cele

inalte !!!

Nivelul de calitate cuprins intre 1 si 100 in functie de matricea de cuantizare.

1 corespunde celei mai scazute calitati dar unei compresii maxime.

100 calitate maxima, compresie minima.

Standardul Standardul JPEGJPEGMatricea de cuantizare standard JPEG corespunzatoare unui compromis

optim intre calitate si compresie este definita de:

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

9910310011298959272101120121103877864499211310481645535247710310968563722186280875129221714566957402416131455605826191412126151402416101116

Standardul Standardul JPEGJPEGQ10 – nivel de calitate 10 (compresie mare)

Q90 – nivel de calitate 90 (compresie scazuta)

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

2552552552552552552552552552552552552552552552452552552552552552551751202552552552552551851109025525525525514511085702552552552001208065702552552551309570605525525520012080506080

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

2020202220191814212424211716131018231216131175152122141174412161710643311141185333111212543221210853223

StandardulStandardul JPEGJPEGCuantizarea se obtine prin divizarea fiecarui element al matricei

transformate (coeficientii TCD) cu elementul corespunzator din matricea de cuantizare si apoi rotunjirea la cel mai mare intreg:

unde Du,v sunt coeficientii TCD.

⎟⎟⎠

⎞⎜⎜⎝

vu,, Q

DrotunjirevuC

StandardulStandardul JPEGJPEG5. Primul element al matricei C (valoarea coeficientului DC) este codata prin

modul diferenta iar celelalte 63 de valori (coeficientii AC) sunt cititi in modul zig –zag si apoi codati:

DE CE ZIG – ZAG ? Pentru ca, coeficientii corespunzator frecventelor cele mai importante (componenta continua si cele joase) vor apare primele in aceasta secventa pe cand cele de frecventa joasa (cuantizate ca valoare la zero !) apar in coada sirului eficienta maxima a codarii (Huffman).

Standardul Standardul JPEGJPEG6. Codarea cu cod de lungime variabila (CLV) – codarea entropica se

realizeaza in 2 etape:

1. Convertirea coeficientilor TCD cuantizati intr-un set intermediar de simboluri.

2. Fiecarui simbol i se asociaza coduri de lungime variabila.

Un simbol este structurat pe doua parti: simbolul_1 (CLV) si simbolul_2 (reprezentare binara a pentru amplitudinea partii a doua).

Standardul Standardul JPEGJPEGPentru reconstructia (decodare) imaginii pasii sunt urmatorii:

1. Se decodeaza fluxul de biti (decodor Huffman sau aritmetic)

2. Fiecare element a lui C multiplicat cu elementul corespunzator almatricii initiale de cuantizare, obtinandu-se R:

3. Se aplica transformata inversa TCD pentru matricea R, rotunjita la cel mai apropiat intreg:

4. Valoarea 128 se aduna la rezultatul final, obtinandu-se imaginea comprimata in format JPEG.

vu,vu,vu, CxQR =

)(rotunjire TRTN T=

Standardul Standardul JPEGJPEGExemplu

Sectiune imagine color Componenta de luminanta

Componenta Cr Componenta CrImaginea color intreaga

Standardul Standardul JPEGJPEGExemplu Componenta de luminanta

Valorile pixelilor

Standardul Standardul JPEGJPEGExemplu

Se scade 128

StandardulStandardul JPEGJPEGExemplu

⎟⎟⎠

⎞⎜⎜⎝

vu,, Q

DrotunjirevuC

Coeficientii TCDCoeficientii TCD

cuantizati

Dupa cuantizare exista doar 31 coeficientii de luminanta diferiti de zero dintr-un total de 256 (16 x 16 – dimensiunea imaginii) o compresie de ~= 88 % !

Reprezentarea 3D a coeficientilor TCD de luminanta inainte de cuantizare si dupa cuantizare (Unghi de vizualizare: azimuth = -40, elevatie = 30). Se observa lipsa multor coeficienti dupa cuantizare (mai

exact, valoarea lor se reduce la 0)

StandardulStandardul JPEGJPEG

Reprezentarea 3D a coeficientilor de luminanta TCD inainte de cuantizare si dupa cuantizare (Unghi de vizualizare: azimuth = -74, elevatie = 0). Se observa lipsa multor coeficienti dupa cuantizare (mai exact, valoarea lor se reduce la 0)

DC DC DC DC DC DC DC DC

Standardul Standardul JPEGJPEGInainte de aplicarea TCD pentru cele 3 componente, componentele de

crominanta se reduc la jumatate. In cazul nostru imaginea are dimensiunea16 x 16 2 componente de crominanta de dimensiune 8 x 8.

In final avem 4 blocuri de luminanta (8 + 8 + 8 +8) si 2 de crominanta (Cb si Cr) 6 blocuri concatenate 8 x (8 x 6) = 8 x 48 elemente:

Y11, Y12, Y21, Y22, Cb11, Cr11, Y13, Y14, Y23, Y24, Cb12, Cr12,Y31, Y32, Y41, Y42, C21, Cr21, Y33, Y34, Y43, Y44, Cb22, Cr22.

Y11 Y12 Y13 Y14

Y21 Y22 Y23 Y24

Y31 Y32 Y33 Y34

Y41 Y42 Y43 Y44

Cb11 Cb12

Cb21 Cb22

Cr11 Cr12

Cr21 Cr22

Standardul Standardul JPEGJPEGEOB

Coeficientii DC: – 11, – 8, – 7, – 9, – 2, si 4 Vectorul DC diferenta: (– 11, 3, 1, – 2, 7, 6)

Coeficientii AC pentru bloc 1 (scanare zig – zag): (1, 6, 0, 0, 1, 0, –1, 0, 1, 2, EOB) – 11 coeficienti

Coeficientii AC pentru bloc 2 (scanare zig – zag): (– 4, 4, 1, –1, 1, 0, 0, 0, 1, 0, 1, EOB) – 12 coeficienti

Coeficientii AC pentru bloc 3 (scanare zig – zag): (2, –3, 0, 0, 1, 0, 0, 1, –3, 0, 0, 1, EOB) – 13 coeficienti

Coeficientii AC pentru bloc 4 (scanare zig – zag): (–4, –7, 2, 1, 4, 0, 1, 0, – 1, 0, – 1, EOB) – 12 coeficienti

Coeficientii AC pentru bloc 5 (scanare zig – zag): EOB – 1 coeficient.

Coeficientii AC pentru bloc 6 (scanare zig – zag): EOB – 1 coeficient.

Coeficientii DC: – 15, – 12, – 11 si –13 Vectorul DC diferenta: (– 15, 3, 1, – 2)

Coeficientii AC pentru bloc 1 (scanare zig – zag): (1, 6, 0, 0, 1, 0, –1, 0, 1, 2, EOB) – 11 coeficienti

Coeficientii AC pentru bloc 1 (scanare zig – zag): (– 4, 4, 1, –1, 1, 0, 0, 0, 2, 0, 1, EOB) – 12 coeficienti

Coeficientii AC pentru bloc 1 (scanare zig – zag): (2, –3, 0, 0, 1, 0, 0, 1, –3, 0, 0, 1, EOB) – 13 coeficienti

Coeficientii AC pentru bloc 1 (scanare zig – zag): (–4, –7, 2, 1, 4, 0, 1, 0, – 1, 0, – 1, EOB) – 12 coeficienti

Standardul Standardul JPEGJPEGCodarea coeficientilor (diferenta) DC de luminanta:

Fiecare coeficient este format din:

[simbol_1 simbol_2]

– 15: simbol_1 categoria: 4 cod: 101

simbol_2 15 in binar 1111

– 15 (complement fata de 1) 0000

Codul complet pentru –15 este:

1010000

3: simbol_1 categoria: 2 cod: 011

Codul complet pentru 3 este:

Tabelul Huffman pentru coeficientii DC corespunzator componentei de luminanta

Standardul Standardul JPEGJPEGCodarea coeficientilor (diferenta) DC de luminanta:1: simbol_1 categoria: 1 cod: 010

Codul complet pentru 1 este:

– 2: simbol_1 categoria: 2 cod: 011

– 2 (complement fata de 1) 01

Codul complet pentru –15 este:

Codul pentru coeficientii DC este 1010000 01111 0101 01101 – 21 de biti

Tabelul Huffman pentru coeficientii DC corespunzator componentei de luminanta

Standardul Standardul JPEGJPEGCodarea coeficientilor AC de luminanta:

Fiecare coeficient este format din:

[simbol_1 simbol_2]

Simbol_1 este dat de [Run, Categorie] codul in binar corespunzator tabelului Huffman pentru coeficientii AC de luminanta.

Run este numarul de zerouri din fata coeficientului in cauza

Categorie – numarul de biti necesari expresiei in binar a coeficientului.

Simbol_2 este coeficientul exprimat in binar.

Coeficientii AC pentru bloc 1 (scanare zig – zag): (1, 6, 0, 0, 1, 0, –1, 0, 1, 2, EOB)

EOB se refera la ultimul bit zero dupa care toti ceilalti (pana la 63) sunt zero.

Coeficientii AC sunt reprezentati astfel: {(0, 1), (0, 6), (2, 1), (1, -1), (1, 1), (0, 2), (0, 0)}.

Tabelul Huffman pentru coeficientii AC corespunzator componentei de luminanta

Standardul Standardul JPEGJPEGCodarea coeficientilor AC de luminanta:Coeficientii AC pentru bloc 1 (scanare zig – zag): (1, 6, 0, 0, 1, 0, –1, 0, 1, 2, EOB)

1: simbol_1 run = 0, categorie = 1, cod 00

Cod complet 001

Cod complet 100110

1: simbol_1 run = 2 (doua zerouri inainte), categorie = 1, cod 11100

Cod complet 111001

Standardul Standardul JPEGJPEGCoeficientii AC pentru bloc 1 (scanare zig – zag): (1, 6, 0, 0, 1, 0, –1, 0, 1, 2, EOB)

– 1: simbol_1 run = 1 (un zero inainte), categorie = 1, cod 1100

simbol_2 1 in binar 1, – 1 complement 0

Cod complet 11000

1: simbol_1 run = 1 (doua zerouri inainte), categorie = 1, cod 1100

Cod complet 11001

Cod complet 0110

EOB: se codeaza 1010

Coeficientii AC pentru blocul 1 sunt codati cu sirul de biti: 001100110111001110001100101101010 – 33 de biti

Standardul Standardul JPEGJPEGCoeficientii AC pentru blocul 2 sunt codati cu sirul de biti:

10001110010000100000111111011110110011010 – 41 de biti

Coeficientii AC vor fi astfel codati cu sirul (152 de biti):

00110011011100111000110010110101010001110010000100000111111011110110011010011001001110011110010100111001101010001110000001100011001001100111000110001010.

Numarul total de biti pentru stocarea imaginii (sau transmiterea ei) este 21 + 152 = 172 biti.

Standardul Standardul JPEGJPEGCalitatea compresiei - biti/pixeli (bpp) – numarul total de biti din imaginea comprimata

(inclusiv pentru cele doua componente de crominanta) impartit la numarul total de pixeli.

In cazul nostru (DOAR PENTRU LUMINANTA) 172 / 256 = 0.67 bpp (imaginea este de dimensiune 16 x 16 = 256).

La decompresie, pasii se repeta in sens invers (decodare Tabel Huffman pentru coeficientii AC si DC, TCD inversa + decuantizare, se adauga valoarea 128, etc).

Standardul Standardul JPEG JPEG -- RezultateRezultate

Imaginea originala (necomprimata) si valorile pixelilor asociati

Imaginea comprimata si valorile pixelilor asociati

Standardul Standardul JPEG JPEG -- RezultateRezultate

Q = 90, RC = 10:1, Dim = 47 Kb, 1.72 bpp

Q = 50, RC = 24:1, Dim = 38 Kb, 0.74 bpp

Q = 25, RC = 34:1, Dim = 34 Kb, 0.52 bpp

Q = 10, RC = 57:1, Dim = 26 Kb, 0.31 bpp

Q = 1, RC = 124:1, Dim = 1.52 Kb, 0.17 bpp

BMP, Dim = 192 Kb (256 x 256)

Standardul Standardul JPEG JPEG –– RezultateRezultate

Q = 50, fara bit de eroare, 6693 biti pentru DC, 59289 biti pentru AC

Q = 50, 2 biti de eroare, pentru DC

Q = 50, 2 biti de eroare, pentru AC

Imaginea eroare Imaginea eroare Imaginea eroare

Standardul Standardul JPEG JPEG –– RezultateRezultate

Imaginea eroare

Q = 70, cu bit de eroare (un bit lipsa)

Q = 70, cu bit de eroare (un bit in plus)

Imaginea eroare Imaginea eroare

Q = 70, fara bit de eroare, 6687 biti pentru DC, 79911 biti pentru AC

StandardulStandardul JPEG JPEG ––!!Inainte de transmisie coeficientii din figura d) sufera o reprezentare

intermediara.

Primul numar (coeficientul DC) este codat diferential: daca coeficientul DC al blocului precedent este 12 diferenta este +3 o reprezentare intermediara: de tip 2 (3), unde 2 este dimensiunea iar 3 este amplitudinea.

Dimensiunea se refera la numarul de biti necesar pentru codarea valorii aplitudinii.

Urmeaza codarea coeficientului cuantizat AC:

Simbol 1: (Runlength, Dimensiune)

Simbol 2: Amplitudine

Runlength se refera la numarul valori zero consecutive ai coeficientilor AC din scanarea in zig – zag de dinaintea coeficientului in cauza.

MetodaMetoda de de compresie fara pierdericompresie fara pierderiIn acest caz se foloseste o codare spatiala (spre deosebire de TCD unde

avem de-a face cu o codare in frecventa).

Fiecare pixel este codat folosindu-se o codare predictiva, unde valoarea prezisa se obtine din una dintre cele anterioare.

Erorile de predictie sunt codate fir cu un cod Huffman fie cu un cod aritmetic.

Metoda Metoda de de codare hierarhicacodare hierarhicaIn acest caz se foloseste o reprezentare progresiva.

Este potrivita pentru codarea multirezolutie.

Imaginea este descompusa pe mai multe nivele de rezolutie (subesantionata) asa numite nivele piramidale, rezultand o secventa de cadre.

Metoda Metoda de de codare hierarhicacodare hierarhicaCu exceptia primului cadru, procesul de codare predictiva este aplicat

diferentelor dintre cadrul care trebuie codat si si cadrul de referinta (cadrul anterior, de regula).

Primul cadru (care reprezinta cea mai mica rezolutie) este codat in mod nediferential.

Cadrele se pot coda fie folosind o metoda secventiala de tip TCD, codare progresiva sau codare fara pierderi de tip Huffman sau cu cod aritmetic.

Prelucrarea imaginilor Prelucrarea imaginilor colorcolorPrezentarea si descrierea standardului JPEG a fost facuta pentru imagini

pe nivele de gri.

JPEG se poate folosi si pentru imagini color (de tip “24 biti”) prinaplicarea sa pentru fiecare componenta de culoare.

Spatiul RBG este, in general, transformat in alte coordonate ale spatiului de culoare, cu ar fi spatiul YUV sau YCbCr (unde exista o corelatie mica intre componente).

Cea mai importanta informatie spatiala este continuta in componenta de luminanta Y.

Componentele de crominanta sunt subesantionate, dimensiunea fiind redusa la jumatate.

Formatul Formatul GIF (Graphics Interchange Format)GIF (Graphics Interchange Format)Este un format de compresie fara pierderi nestandardizat oficial.

A fost primul format pentru imagini color (1987).

Formatul GIF accepta doar imagini color de nuante reduse (256 culori –8 biti).

Formatul GIF se bazeaza, in principal, pe o varianta a algoritmului de codare Lempel – Ziv – Welch (LZW).

Formatul Formatul PNG (Portable Networks Graphics)PNG (Portable Networks Graphics)Formatul PNG este un format de compresie fara pierderi (1996),

proiectat pentru imbunatatirea compresiei formatului GIF si pentru aplicatii web.

La ora actuala reprezinta un standard oficial ISO / IEC.

PNG suporta trei tipuri de imagini (nivele de gri, culori, si culori paleta redusa).

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaCodarea in sub-benzi de frecventa este predecesorul codarii bazate pe

transformata undisoara.

Principiul codarii in sub-benzi de frecventa a fost introdusa in 1976 –folosita de atunci la compresia vorbirii (audi) si imaginii.

Principiul de baza este descompunerea spectrului semnalului in benzi de frecventa, codarea lor separata, urmata de transmiterea lor.

Succesul codarii in sub-benzi se datoreaza:

1. Dupa cum se stie din materialul prezentat anterior, imaginile naturale au tendinta de a genera un spectru de frecventa neuniform, in care cea mai mare parte a energiei sale este concentrata in partea inferioara a spectrului (zona frecventelor joase).

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventa2. Mai mult, perceptia umana este mai putin sensibila la extremitatile

spectrului de frecventa (frecvente prea joase sau prea inalte, indiferent de informatie – audio sau video).

3. Imaginile sunt codate ca un singur bloc (imaginea intreaga odata) si nu este impartita pe blocuri ca si in cazul unei codari de tip TCD nu apar acele artefacte de imagine.

Codarea in sub-benzi este asemanatoare ca principiu cu transformataFourier (analiza in domeniul frecventa) dar bancile sale de filtre au proprietati de decorelare mai bune a informatiei.

Functiile de baza Fourier sunt foarte exacte in frecventa dar sunt imprecise in spatiu.

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaCu alte cuvinte, energia semnalului corespunzator functiilor de baza de

tip Fourier nu sunt concentrate pe o singura frecventa (localizate in spatiu) ci este distribuita pe toata gama de frecventa (pe tot spatiul).

Daca pixelii din imagine ar fi INTOTDEAUNA puternic corelati nu ar fi nici o problema.

In realitate, in imagine exista zone in care pixelii sunt slab corelati (de exemplu in zonele de tranzitie sau discontinuitati – muchiile).

Spre deosebire de functiile de baza de tip Fourier, functiile de tip sub-banda nu numai ca au o delimitare clara in frecventa dar sunt si compacte pe intreg spatiul (bine localizate in spatiu).

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaImpartirea in sub-benzi se realizeaza prin trecerea imaginii printr-un set

(banci) de filtre de analiza de tip trece-banda.

Filtrele sunt impartite in benzi de octave (impartire similara cu cea care are loc in sistemul vizual uman).

Octava – este intervalul dintre 2 frecvente pentru care exista raportul 2:1 (frecventa superioara este exact dublul frecventei inferioare).

Exemplu: daca o nota muzicala are frecventa de 400 Hz, nota urmatoare la distanta de o octava este de 800 Hz, iar nota muzicala precedenta la distanta de o octava este cea corespunzatoare frecventei de 200 Hz.

16 KHz este la 2 octave de 4 KHz (4*2 = 8, 8*2 = 16)

4 KHz este la 3 octave de 500 Hz (500*2 = 1000, 1000*2 = 2000, 2000*2 = 4000).

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaDeoarece latimea de banda pentru fiecare versiune filtrata a imaginii este

mai mica decat banda intreaga, aceste sub-benzi pot fi sub-esantionate la o rata mai scazuta imagini de dimensiune redusa.

Subimaginile sunt cuantizate, codata si apoi transmise.

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaImaginile sunt receptionate la destinatie, aduse la dimensiunea originala

prin aplicarea unor filtre de sinteza (inversa filtrelor de sinteza), rezultatele sunt interpolate si adunate astfel incat sa compuna imaginea originala.

In absenta erorilor de cuantizare, imaginea reconstituita ar trebui sa fie o copie PERFECTA a imaginii originale (cazul ideal).

Acest lucru ar fi insa posibil doar daca raspunsul in frecventa a filtrelor de sinteza sunt distincte pe tot spectrul, adica, cu alte cuvinte, nu exista suprapunere intre benzile de frecventa ceea ce ar necesita o regiune de tranzitie a filtrelor foarte abrupta (practic pe verticala) lucru imposibilde realizat in practica.

Ca si consecinta apar distorsiuni de suprapunere.

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaPentru eliminarea distorsiunilor de suprapunere intre filtrul de analiza si

cel de sinteza trebuie stabilita o anumita relatie in asa fel incat regiunile de tranzitie sa se elimine reciproc.

H0(z) si H1(z) reprezinta functia de transfer a transformatei z a filtrului de analiza de tip trece-jos si trece-sus.

La codare are loc o subesantionare cu factorul 2 (eliminarea esantioanelor pare de exemplu).

Filtru de analiza dual (pe 2 benzi) Codor / decodor de tip sub-banda (pe 2 benzi)

Codarea Codarea in subin sub--benzi benzi de de frecventafrecventaSubesantionarea este echivalenta cu cu comprimarea sursei de imagine

cu factorul 2 (dublarea componentelor de frecventa) dublarea latimii pentru fiecare componenta din spectru.

Generarea sub-benzii de tip trece-jos si reconstructia semnalului

Generarea sub-benzii de tip trece-sus si reconstructia semnalului

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaLa decodare se aplica operata inversa: supraesantionarea.

Supraesantionarea se obtine prin inserarea unor esantioane egale ca valoare cu zero (0) printre esantioanele de intrare expansiune spatiala a secventei de intrare in decodor.

In domeniul de frecventa toate componentele vor fi comprimate.

Problema imposibilitatea proiectarii unui filtru ideal cu frecventa de taiere verticala !

Spectrul A ilustreaza semnalul original esantionat si trecut printr-un filtru trece-jos o parte din energie ramane sub valoarea Fs / 4, frecventa de taiere ideala pentru acest filtru.

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaExpandarea spectrului (B) subesantionare.

Comprimarea spectrului (C) prin supraesantionare.

In final, se vor genera componente auxiliare de frecvente localizate la multiplii impari de Fs / 2 in spectrul de frecventa.

Consecinta: Aparitia suprapunerii la reconstructia sub-benzii originale (spectrul D).

In cazul filtrului de tip trece-sus apare aceeasi problema.

Imaginea finala de iesire este generata prin adunarea subbenzilor de tip trece-jos si trece-sus interferenta prin suprapunere.

Solutie: faza celor 2 componente de frecventa sa difere prin π.

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaAnaliza de face cu ajutorul transformatei in planul Z.

Pentru analiza corespunzatoare filtrului de tip trece-jos, dupa aplicarea filtrului de sinteza, reconstructia sub-benzii exprimata in planul Z poate fi scrisa sub forma:

unde Y0(z) si Y1(z) sunt intrarile filtrelor de sinteza dupa supraesantionare.

Cu presupunerea ca nu exista erori de cuantizare sau transmisie, esantioanele reconstituite vor avea expresia:

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaH0(-z) * H(-z) si H1(-z) * H(-z) sunt componentele de suprapunere

generate de procesul de subesantionare corespunzatoare benzilor de frecventa joasa, respectiv inalta.

Inlocuind relatiile de ai sus in relatia anterioara obtinem:

Primul termen corespunde semnalului util reconstituit iar al doilea termen corespunde componentelor de suprapunere.

Prin definirea filtrelor de sinteza prin relatiile

componentele de suprapunere pot fi elimiate.

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaSemnalul reconstituit este astfel descris de:

Definind P(z) = H0(z)*H1(-z), avem:

Reconstructia semnalului este acum perfecta dar semnalul este intarziat cu m esantioane:

Functia de transfer (intrare/iesire) in planul Z este data acum de relatia:

In domeniul pixelilor secventa {y(n)} de imagine reconstituta este o copie perfecta a imaginii de intrare dar deplasata cu m pixeli, {y(n)} = x(n –m)}. P(z) se numeste filtru de produs iar m este intarzierea introdusa desetul de filtre. Filtrul de produs trebuie sa aiba un numar impar decoeficienti.

CodareaCodarea in subin sub--benzi benzi de de frecventafrecventaUn exemplu de astfel de filtru este dat de relatia:

Prin factorizarea (descompunerea in factori) relatiei de mai sus, se obtin urmatoarele 3 solutii pentru perechile de filtre de analiza si sinteza:

Folosirea ecuatiilor de mai sus (indiferent care) ne conduce la rezultatul

P(z) – P(-z) = 2z – 3, adica o intarziere de 3 esantioane.

Transformata undisoaraTransformata undisoaraTransformata undisoara a fost propusa in locul transformatei Fourier

pentru avantajele pe care le ofera asupra ultimei.

Functiile de baza se numesc undisoare.

Undisoarele au un suport compact (se pot anula doar pe anumite intervale mici) spre deosebire de transformata Fourier care are o durata infinita (descrisa de functia sinus sau cosinus).

Undisoarele sunt localizate atat in timp cat si in frecventa.

Cand se doreste o informatie precisa la frecventa joasa se foloseste un interval scurt.

Cand se doreste o informatie precisa la frecventa inalta se foloseste un interval lung.

Transformata undisoaraTransformata undisoaraUndisoarele sunt folosite pentru analiza localizata a semnalelor cat si in

cazul zonelor de singularitate a semnalului.

Transformata undisoara reprezinta un semnal ca o combinatie liniara a versiunilor deplasate si scalate a undisoarei initiale (numita si undisoara de baza - undisoara mama).

Transformata undisoara sta la baza standardului de compresie JPEG 2000.

Daca factorul de scala si pozitie (pentru deplasare) se aleg ca puteri ale lui 2, atunci transformata dse numeste Transformata Undisoara Discreta (TUD), iar descompunerea se numeste diadica.

Transformata undisoaraTransformata undisoaraTransformata undişoară descompune o imagine în componente de

imagini detaliate + imagine brută.

Să considerăm că avem o secvenţă de eşantioane

[8 4 1 3]

Prin medierea valorilor (elementelor) două cate două, obţinem secvenţa:

care defineşte o reprezentare mai brută a secvenţei originale.

Dacă se doreşte păstrarea informaţiei pierdute prin mediere, primul coeficient va fi 2 iar al doilea coeficient va fi –1, deoarece:

6 + 2 = 8, 6 – 2 = 4, 2 + (– 1) = 1, 2 – (– 1) = 3

Transformata undisoaraTransformata undisoaraContinuand procesul de descompunere vom obtine

[8 4 1 3]

[6 2] [2 –1]

[4] [2]

iar transformarea finală va avea forma:

[4 2 2 –1]

In descompunerea de mai sus nu s-a pierdut informaţie.

Detaliile şi medierile (reprezentările brute) vor apare pe diverse nivele de scală.

Semnalul original poate fi reconstituit la nivelul de detaliu dorit printr-un procedeu recursiv cu ajutorul coeficienţilor de detaliu.

Transformata undisoaraTransformata undisoaraDin punct de vedere al compresiei, se observă cum coeficienţii de detaliu

au o valoarea foarte mică.

Prin introducerea unui prag în aşa fel incat coeficienţii mai mici decat acest prag sa fie egalaţi cu zero, se obţine o compresie semnificativă.

Transformata undişoară poate deveni unitară prin scalarea elementelor sale cu o constantă, de ex. in cazul transformatei undişoara Haar de dimensiune 2 x 2:

Exemple de undişoare: Haar, pălărie mexicană, Daubechies.

⎥⎦

⎤⎢⎣

⎡−1111

Transformata undisoaraTransformata undisoaraAnaliza undişoarelor poate fi efectuată cu ajutorul băncilor de filtre.

Exista filtre de analiză, sinteză, de subeşantionare si supraeşantionare.

Băncile de filtre pot fi proiectate în asa fel incat să se obţină o reconstrucţie perfectă a semnalului original şi evitandu-se efectul de suprapunere (prin folosirea filtrelor undişoare biortogonale).

Transformata undisoaraTransformata undisoaraCalitatea compresiei se măsoară in general in biţi / pixeli (bpp) şi

exprimă numărul de biţi necesar reprezentării imaginii comprimate (inclusiv pentru componentele de crominanţă în cazul imaginilor culori) impărţit la numărul de pixeli ai componentei de luminanţă.

0.25 – 0.5 bpp: calitate moderată – calitate acceptabilă suficientă doar pentru unele aplicatii.

0.5 – 0.75 bpp: calitate acceptabilă – calitate foarte bună suficientăpentru unele aplicatii.

0.75 – 1.5 bpp: calitate excelentă – suficientă pentru majoritatea aplicaţiilor.

1.5 – 2 bpp: imaginea comprimată nu se distinge de imaginea originală.

Descompunerea multirezolutie Descompunerea multirezolutie a a imaginiiimaginii cu cu aplicatie aplicatie in in compresia datelorcompresia datelor

Descompunerea multirezoluţie a datelor transformate undişoareanaliza semnalelor simultan în timp şi frecvenţă.

Undişoarele sunt funcţii matematice folosite pentru descompunerea unui semnal în componente de frecvenţă şi studierea fiecărei componente în parte.

Transformatele undişoare filtrează (descompune) datele în componente de rezoluţie joasă (aproximarea datelor – frecvenţe joase) şi componente de detaliu (frecvenţe inalte).

Descompunerea multirezolutieDescompunerea multirezolutie a a imaginii imaginii cu cu aplicatie aplicatie in in compresia datelorcompresia datelor

Descompunerea multirezolutie Descompunerea multirezolutie a a imaginii imaginii cu cu aplicatie aplicatie in in compresia datelorcompresia datelor

Cea mai simplă transformata undişoară mediere si scădere.

Considerăm un semnal unidimensional.

Exemplu:

Descompunerea multirezolutie Descompunerea multirezolutie a a imaginiiimaginii cu cu aplicatieaplicatie in in compresia datelorcompresia datelor

Calculul transformatei undişoare implicăfolosirea recursivă acoeficientilor de mediere şi diferenţă set de filtre

Descompunerea multirezolutieDescompunerea multirezolutie a a imaginii imaginii cu cu aplicatieaplicatie in in compresia datelorcompresia datelor

Sub–eşantionare (rezoluţie joasă + detalii) şi Supra–eşantionare(reconstrucţie din frecvenţă joasă + detalii).

Sub–eşantionare set (bănci) de filtre de analiză.

Supra–eşantionare set (bănci) de filtre de sinteză.

Exemplu 1: Sub–eşantionare si Supra–eşantionare.

Descompunere

Reconstrucţie

Exemplu 2: Arbore logaritmic (arbore multirezoluţie):

Ieşire: 4.5, -2, -1, -1, -.5, -.5, -.5, -.5

Exemplu 3 - Transformata Haar unidimensionala:

Se da vectorul de intrare {1, 2, 3, 4, 5, 6, 7, 8} (rezolutie 8)

Pasul 1 (rezolutie 4):

Frecvente joase de iesire L1 = {1.5, 3.5, 5.5, 7.5} – medie

Frecvente inalte de iesire H1 = {-0.5, -0.5, -0.5, -0.5} – detalii

Pasul 2 (rezolutie 2) - Repetarea pasului 1 pentru banda de frecvente joase (L1):

L2 = {2.5, 6.5} – medie

H2 = {-1, -1} – coeficienti de detaliu

Pasul 3 (rezolutie 1) Repetarea pasului 1 pentru banda de frecvente joase (L2):

L3 = {4.5} – medie

H3 = {-2} – coeficienti de detaliu

Exemplu 3 (continuare):

Se transmite doar vectorul descompus {4.5, -2, -1, -1, -0.5, -0.5, -0.5, -0.5}. In procesul de descompunere nu se pierde nici nu se castiga informatie. Vectorul original se poate reconstitui din vectorul descompus prin adaugarea si scaderea coeficientilor de detaliu la valoarea corespunzatoare celei mai mici rezolutii. Vectorul descompus are tot atatea valori (8) ca si vectorul original dar, cu exceptie primei valori, toate celelalte valori sunt mai mici. In principiu, VALORI MAI MICI NUMAR DE BITI REDUS (TRANSFORMARE ZECIMAL – BINAR, HUFFMAN, ETC) COMPRESIE !

Există 2 reprezentări:

1. Descompunere standard

2. Descompunere piramidală

Descompunere piramidală undişoară – fiecare descompunere este compusă din 3 pasi:

Calcularea unei imagini la rezoluţie joasă (aproximări a imaginii de bază) filtarea imagini şi sub-eşantionare (mediere)rezultatului cu factorul 2.

Supra – eşantionarea rezultatului de mai sus cu factorul 2.

Calcularea diferenţei dintre imaginea obţinută la pasul 2 şi cea obţinută la pasul 1.

După descompunere se obţin 4 sub - imagini: (aproximată imaginii şi 3 sub - imagini diferenţă).

Descompunere piramidală undişoară:

Exemplu: imagine 8 x 8 pixeli

La reconstrucţia imaginii se porneşte de la sub – imaginea de rezoluţie scazută la care se adaugă (gradual) sub – imaginile diferenţă (detalii) în funcţie de rezoluţia dorită.

Pentru compresie, în locul imaginii originale se poate folosi sub –imaginea de rezoluţie scazută.

Pentru fiecare nivel de descompunere, imaginea este reprezentată de 3 sub – imagini diferenţă care pot fi comprimate, codate şi transmise mult mai eficient decat imaginea originală.

Standardul Standardul JPEG JPEG –– 20002000

Imagine originala

Compresie fara pierderi

5.2 bpp

1.89 bpp

1.84 bpp

Rezolutie joasa

Sub-bandaCompresie cu pierderi

O singura componenta

Standardul Standardul JPEG JPEG –– 20002000Standardul JPEG – 2000 este ultima variantă de compresie dezvoltată de

Joint Photographic Experts Group.

Este un standard acceptat de ISO şi recomandat de ITU – T.

Are la bază descompunerea multirezoluţie a undişoarelor.

Transformate undişoare folosite: de tip intreg “5 – 3” (compresie reversibilă aproape fără pierderi) şi Daubechies “9 – tap” sau “7 – tap”, undişoara discretă Mallat.

Principalul avantaj al JPEG – 2000 in raport cu JPEG este rata de compresie mai bună pentru aceeaşi calitate a imaginii (< 0.25 bps).

StandardulStandardul JPEG JPEG –– 20002000Carateristici:

JPEG – 2000 permite extragerea de rezolutii diferite a imaginii sau componente dintr-un flux de biti, alocarea unei regiuni de interes (ROI) in imagine si rata de compresie diferita (fata de restul imaginii) asociate acestei ROI;

se pot comprima imaginii de dimensiune mare (64 k x 64k);

transmitere in medii zgomotoase;

codare si decodare in timp real;

impartirea (optional) imaginii in blocuri nesuprapuse (tipic 64 x 64);

pentru fiecare sub – banda se poate folosi o cuantizare scalara independenta;

Standardul Standardul JPEG JPEG –– 20002000Carateristici:

transmisie progresivă a calitatii sau rezolutiei imaginii;

oferă atat compresie cu pierderi cat si fără pierderi;

access spaţial aleator in fluxul de biti;

optiunea de zoom;

oferă opţiunea de prelucrare a imaginii in domeniul transformatei (rotire, decupare, etc);

rata de bit este fixă;

optiunea de protecţie a imaginii (drepturi de copyright, watermarking, criptare, etc);

biţii cei mai semnificativi se transmit primii.

Standardul Standardul JPEG JPEG –– 20002000Standardul JPEG 2000 foloseşte în mare parte toate elementele şi pasii

de compresie folosiţi la JPEG de baza (decorelarea pixelilor prin transformare, cuantizarea, codarea entropiei, etc) plus etape adiţionale specifice standardului JPEG 2000 (preprocesare şi postprocesare).

Preprocesare Codare de baza PostprocesareIntrare Iesire

Standardul Standardul JPEG JPEG –– 20002000Preprocesare – 3 paşi de preprocesare.

I. “Tiling” – impărţirea imaginii in blocuri nesuprapuse (disjuncte).

Dimensiunea blocului – un pixel întreaga imagine.

Un astfel de bloc este o unitate de bază pentru operaţia de codare: toţi pasii de codare sunt efectuaţi pe această unitate.

Fiecare astfel de bloc poate fi comprimat şi codat independent de celelalte blocuri.

Dezavantaj: nu se exploatează corelaţia dintre pixelii de la marginea blocurilor adiacente odată cu reducerea dimensiunii blocului se reduce şi caştigul în compresie a codorului.

Standardul Standardul JPEG JPEG –– 20002000II. Deplasarea valorii coeficientului DC – pentru fiecare componentă

RGB valoarea coeficientului DC se deplasează cu 2B – 1, cu B biţi pentru fiecare componentă de culoare.

III. Transformata de culoare.

Componentele de culoare conţin informaţie redundantă (sunt puternic corelate) necesară decorelarea:

Transformare de culoare ireversibilă (cu pierderi):

Standardul Standardul JPEG JPEG –– 20002000

III. Transformata de culoare.

Transformare de culoare reversibilă (fără pierderi) :

In acest caz decorelarea nu este atat de puternică (in comparaţiecu prima transformare) dar informaţia de culoare se poate recupera.

Standardul Standardul JPEG JPEG –– 20002000Codarea de baza -

Transformata

de culoare

Flux de biti

Goffset DC

offset DC

Standardul Standardul JPEG JPEG –– 20002000????????????????????????????????????????????????????????

Standardul Standardul JPEG JPEG –– 20002000Codare diferenţiată in funcţie de regiunea de interes

Regiune de interes (ROI) (4.5 bpp)(0.05 bpp)

Standardul Standardul JPEG JPEG –– 20002000Codare pentru rezoluţii diferite

Standardul Standardul JPEG JPEG –– 20002000Reconstrucţia imaginii iniţiale in funcţie de rezoluţia dorită.

Standardul Standardul JPEG JPEG –– 20002000Exemple

JPEG la 0.125 bpp JPEG2000 la 0.125 bpp

JPEG la 0.25 bpp JPEG2000 la 0.25 bpp

StandardulStandardul JPEG JPEG –– 20002000Exemple

Imaginea originala

2.5 bpp cu 4 nivele TUD

Imaginea originala

Regiune de interes (ROI) comprimata la 5.85 bpp

Imaginea diferenta

CompresiaCompresia Audio Audio –– Modelul PsihoacusticModelul PsihoacusticUrechea umană este capabilă să perceapă (audă) semnale audio cu

frecvenţele cuprinse in spectrul (bandă) de frecvenţă [20 Hz – 20 KHz].

Nu toate frecvenţele sunt percepute in acelasi mod (cele situate la extremităţile spectrului de frecvenţă sunt percepute cu dificultate).

Dupa ani de cercetare a modului in care urechea umană percepe sunetele s-a ajuns la concluzia că spectrul de frecvenţă poate fi impărtit in subbenzi critice neuniforme, neliniare şi dependente de nivelul sunetului scară de analiză Bark sau curbele Fletcher.

Compresia Compresia Audio Audio –– Modelul PsihoacusticModelul Psihoacustic

Barks = 13*arctan(0.00076*Hz) + 3.5*arctan((f / 7500)^2)

Compresia Compresia Audio Audio –– Modelul PsihoacusticModelul PsihoacusticPentru punerea in evidenţă a relaţiei dintre frecvenţă şi percepţia

sunetului procedura este următoarea:

se generează un ton de un nivel audibil foarte mic.

se creste uşor amplitudinea tonului pană la pragul audibil si se notează acel prag.

experimentul se repetă pentru mai multe frecvenţe si mai multi subiecţi.

Compresia Compresia Audio Audio –– Modelul PsihoacusticModelul PsihoacusticUn semnal audio este un semnal complex compus din mai multe

frecvenţe.

Principiu: Dacă un semnal audio are componente de frecvenţe aflate subpragul audibil, acele frecvenţe se pot elimina deoarece ele oricum nu sunt auzite de o persoana cu un sistem auditiv normal.

Sistemul auditiv uman (SAU) este incapabil să diferenţieze un semnal de frecvenţă 1.000 Hz de unul de 1.001 Hz (sau 997 Hz).

Daca semnalul de 1000 Hz este mai puternic decat cel de 997 Hz, acesta din urmă va fi “mascat” de primul, şi nu este perceput MASCARE AUDITIVA.

Compresia Compresia Audio Audio –– Modelul PsihoacusticModelul PsihoacusticProprietatea de mascare a sistemului auditiv uman

Mascarea auditivă este o caracteristică de percepţie a sistemului de auditiv uman şi se referă la “acoperirea” unui sunet de intensitate (nivel) slab de către un sunet mai puternic in intensitate şi aflat in vecinătatea temporală sau spectrală a sunetului mai slab.

Dacă două sunete se suprapun pe axa timpului (sunt recepţionate de aparatul auditiv uman in acelaşi moment de timp), iar unul din ele este mascat de un altul, spunem că avem mascare in frecvenţă (sau simultană).

Chiar şi zgomotul, dacă este foate puternic, poate masca un semnal audio.

CompresiaCompresia Audio Audio –– Modelul PsihoacusticModelul PsihoacusticMascarea auditivă este foarte importantă pentru domeniul de codare

audio perceptuală in stabilirea unui prag de mascare sub care frecvenţelese pot elimina (frecvenţe care sunt dificil de perceput de către urechea umană şi care sunt oricum mascate de frecvenţele vecine) conduce la un număr de biţi mai mic compresie.

Modele de mascare simultană şi temporală sunt cunoscute sub numele de modele psihoacustice.

Exemplu de alocare de biti in functie de nivelul perceptibil al sunetului

Compresia Compresia Audio Audio –– fara pierderifara pierderiCompresie cu pierderi.

Compresie fără pierderi.

Compresia fara pierderi

Tehnici de codare a formei de undă (axa temporala) – aproximareasemnalului original continuu prin ESANTIONARE si CUANTIZARE semnal digital (eşantionat)!

Ex: Tehnica de Modulatie a Impulsului in Cod (MIC) folosit in tehnologia Compact Disc Digital Audio (CD audio) – considerat format comprimat ! – nu este adevărat in totalitate - standard pentru Hi-Fi.

Semnal audio CD – eşantionat la 44.1 KHz – 16 biti / eşantion rată de 705 kbps

Compresia Compresia Audio Audio –– fara pierderifara pierderi

Procesul de inregistrare audio analogic

Procesul de cuantizare reprezentat schematic – esantioane de semnal

Compresia Compresia Audio Audio –– fara pierderifara pierderiPercepţia si calitatea semnalului audio este puternic afectată de raportul

semnal-zgomot (RSZ).

Ideal, la digitizarea unui semnal audio, RSZ ar trebui sa ramană constant pentru orice nivel de cuantizare.

Acest lucru este posibil prin folosirea unei scari logaritmice de compresie (compresie – expandare).

Metode standard de compresie: legea – miu, legea – A.

Alte tehnici de compresie fără pierderi: modulaţia implusurilor in cod adaptivă (MICA) şi modulatia implusurilor in cod diferenţială (MICD).

Codarea Huffman sau LZW (oferă o rată de compresie mică !)

Compresia Compresia Audio Audio –– cu cu pierderipierderiPrincipiu: reducerea redundanţei perceptuale (sunetele abia perceptibilesunt codate cu o precizie mică, sau chiar deloc).

Spre deosebire de compresia audio fără pierderi, in cazul compresieiaudio cu pierderi se lucrează pe scara frecvenţelor codare sub-bandă.

Pentru trecerea din domenil timp in frecvenţa se folosesc transformate.

Cea mai cunoscuta este Transformata Cosinus Discreta Modificata (TCDM) - spectrul este impărţit in blocuri (ferestre) consecutive in care prima jumătate a unui bloc este suprapusă peste a doua jumătate a blocului anterior.

Spectrul de frecvenţe este impărţit, se stabileste un prag de mascare, sub care frecvenţele pot fi eliminate fără afectarea semnificativă(perceptibilă !) a calităţii sunetului.

Compresia Compresia Audio Audio –– standarde standarde MPEGMPEGMP1 (MPEG audio layer – 1): Cel mai simplu codec. Principiu: identificarea componentelor de ton locale prin determinarea maximelor (varfurilor) locale din spectrul de frecvenţe audio.

Incepe in 1998 şi finalizată in 1992.

Este format din 3 moduri de operare numite niveluri (layers), de la cel mai simplu layer – 1 la cel mai complex layer – 3 care oferă cea mai bună calitate a sunetului la o rată de bit scazută (~ 128 kbps pentru un canal stereo).

Compresia Compresia Audio Audio –– standarde standarde MPEGMPEGMP2 (MPEG audio layer – 2): Informaţia dintr-o fereastră este prezisăcu ajutorul celor 2 ferestre precedente prin interpolare liniară.

Caracteristici:

suport pentru formatul de canal 5.1 (sunet cinema).

codare la o rata de bit mai scazută permite frecvenţe de eşantionare de 16 KHz, 22.05 KHz, si 24 KHz.

nu ofera o codare diferită de MPEG – 1.

Compresia Compresia Audio Audio –– standarde standarde MPEGMPEGMP3 (MPEG audio layer – 3): mascare in domeniul timp + model psihoacustic + TCDM + alocare dinamică a biţilor + codare Huffman.

MPEG – 4 audio oferă o rată de bit de la 2 kbps pană la codare de calitate inaltă 64 kbps/canal.

Indiferent de variantă, toate MP-urile descompun semnalul in 32 de sub-benzi egale.

Compresia Compresia Audio Audio –– standarde standarde MPEGMPEGDezavantaje:

Dimensiunea egală a benzilor nu corespunde cu benzile critice de mascare a zgomotului eroarea de cuantizare poate fi semnificativă.

Reconstrucţia semnalelor prin aplicarea filtrării inverse nu este perfectă erori de reconstrucţie chiar in absenţa erorilor de cuantizare.

Filtrele (32) adiacente se suprapun un singur ton poate afecta 2 filtre (bănci de filtre).

Soluţia: apariţia unui nou format de compresie audio: AAC (advanced audio coding) MPEG 4 audio, cu extensia: .mp4 audio.

Principiul compresiei Principiul compresiei mp3mp3Filtrarea digitala (eliminarea unor frecvenţe) este o tehnică foarte eficientă in unele cazuri (telefonie digitală), dar este o metoda destul de brutală.

Există metode mai elegante de a reduce spaţiul de stocare a unui semnal audio menţinand in acelasi timp si calitatea originală !

Idea: Stocarea coeficienţilor mai putin importanţi (adică corespunzători frecvenţelor mai putin importante d.p.d.v. a sistemului psihoacustic) folosind un numar de biţi mai mic cuantizare diferită.

Coeficienţii “mai putin importanti” (nesemnificativi) sunt acei coeficienţi care au o amplitudine mică in spectrul de frecvenţă (TCD de exemplu).

Principiul compresiei Principiul compresiei mp3mp3ACEST PRINCIPIU STA LA BAZA COMPRESIEI MP3 !!!

Coeficienţii corespunzători benzii verzi sunt reprezentaţi (cuantizaţi) pe un număr mai mic de biţi (precizie redusă) decat ceilalti coeficienţi.

Principiul compresiei Principiul compresiei mp3mp3Stabilirea valorii pragului sub care se face o cuantizare diferitădetermină compromisul dintre calitate şi rata de compresie.

De exemplu, dacă 90 % dintre coeficienti apartin benzii verzi (precizie scazută), iar aceşti coeficienţi sunt reprezentaţi pe 8 biţi, iar cei rămaşi (10%) sunt reprezentaţi pe 16 biţi, avem nevoie de un spaţiu de stocarecu 45 % mai mic decat in cazul in care toţi coeficienţii ar fi fost reprezentaţi prin 16 biţi !

De retinut: Nu este eliminată nicio frecvenţă din spaţiul de frecvenţe original, amplitudinele corespunzătoare acestor frecvenţe sunt doar aproximate cu o precizie mai mare sau mai mică in raport cu amplitudinele din spectrul iniţial.

CompresiaCompresia Audio Audio –– MPEGMPEG--1 Layer1 Layer--3 (mp3)3 (mp3)

Schema bloc pentru codorul audio MPEG – 1 Layer 3 (mp3)

Compresia Compresia Audio Audio –– MPEGMPEG--1 Layer1 Layer--3 (mp3)3 (mp3)Bucla de control a ratei de cuantizare neuniformă – dacă numărul de biţi rezultaţi din codarea Huffman depăşeşte numărul de biţi disponibil pentru codarea unui bloc, se face o corecţie a pasului de cuantizare pas de cuantizare mai mare valori cuantizate mai mici un număr mai mic de biţi necesari.

Bucla de control a distorsiunii – folosită pentru modelarea zgomotului de cuantizare sub pragul de mascare folosirea unor factori de scalare.

Factor de scală inţtial = 1 pentru fiecare bandă.

Daca zgomotul de cuantizare > pragul de mascare (determinat de modelul psihoacustic) factorul de scală este reajustat pas de cuantizare mai mic contradicţie mai sus reajustarea ratei de cuantizare neuniformă.

Compresia Compresia Audio Audio –– MPEGMPEG--2 AAC (mp4)2 AAC (mp4)

Schema bloc pentru codorul audio MPEG – 1 Layer 3 (mp3)

Compresia Compresia Audio Audio –– MPEGMPEG--2 AAC (mp4)2 AAC (mp4)Numărul liniilor de frecvenţă este 1024 (faţă de 576 cat este la MPEG –1 Layer – 3).

Cuplare pentru codarea intensităţii in mijlocul benzii + la extreme.

Mod imbunătăţit de comutare bloc – 5.3 ms la o frecvenţă de eşantionare de 48 KHz.

M/S – bloc mono / stereo.

SZ – bloc de suprimare (modelare) a zgomotului – folosit pentru imbunătăţirea calităţii sunetului codat la rate de bit reduse.

Pentru aceeaşi calitate a sunetului, mp4 (AAC) oferă o rata de bit (compresie) de pană la 30 % mai mică decat formatul de compresie mp3.

Formatul Formatul Header Header –– MPEGMPEG--1 + MPEG1 + MPEG--22Fiecare fişier audio digital şi codat în formatul audio MPEG – 1/2 conţine informaţii suplimentare (extra) în asa numitul header care este transmis odată la fiecare 24 ms (pentru o frecvenţă de esantionare de 48 KHz). Header - ul conţine:

cod de sincronizare (pentru codor si decodor);

rata de bit;

frecvenţa de esantionare necesară pentru comutarea decodorului pe frecvenţa corectă: 32, 44.1, sau 48 KHz în cazul MPEG – 1.

nivelul (1,2, sau 3) şi informaţii despre tipul MPEG (1 sau 2);

modul de codare: mono, dual mono, stereo, dual stereo;

protecţie copyright - 2 biti (!) incluşi în Serial Copy Management Scheme.

Compresia vorbiriiCompresia vorbiriiAnaliza vorbirii este un caz particular din domeniul analizei semnalului audio.

Spectrul de frecvenţă este limitat la < 4 KHz.

2 tipuri de codare: pe axa timpului (forma de undă) şi analiză prin sinteză de vocodere.

Codare pe axa timpului nu oferă o compresie cu o rată de bit scazută(e nesatisfăcătoare), utilă doar pentru semnale audio pe bandă largă.

Vocoderele utilizează o codare parametrică exploatează zona perceptuală rate de bit mult mai scăzute viteză considerabilă.

Tehnici: codarea predictivă liniară (CPL), predicţia liniară rezidualăexcitată (PLRE), etc.

Compresia Si Codarea Informatiei

Documents

Transcript of Compresia Si Codarea Informatiei

PIPP-TIC tehnologia informatiei

Modul I Tehnologia Informatiei

managementul securitatii informatiei

Transmisia datelor multimedia in retele de calculatoare Compresia imaginilor . Generalitati

Carte Manag Informatiei

Securitatea Informatiei Cristian-Andreiv1

Noile Tehnologi Ale Informatiei

Achzitia informatiei

Capitole de Transmiterea si codarea informaţieiac.upg-ploiesti.ro/gpanaitescu/tci_capitole.pdf · Capitole de Transmiterea si codarea informaţiei Coduri protectoare la erori ...

Natura informatiei

Securitatea Informatiei

665378applicationCalculatoare Si Tehnologia Informatiei

Analiza informatiei

5 - Compresia fara pierdere de calitate - III.pptx

Utilizarea informatiei

bazele tehnologiei informatiei

CAPITOLUL 10 COMPRESIA DE IMAGINItelecom.etc.tuiasi.ro/pns/cc/curs_cc/cap10_compresie...1 CAPITOLUL 10 COMPRESIA DE IMAGINI 10. 1. Reprezentarea numerică a imaginilor O imagine este

Gesteunea Informatiei

Tehnologia informatiei

Teoria transmisiunii informatiei