1

2. TEHNICI DE COMPRESIE A DATELOR 2.2. Necesitatea compresiei Reducerea cerinelor de stocare; Crete securitatea datelor; Folosirea eficient a benzii canalului de comunicaie:

Canal de comunicaii Informaie

Telefonie banda=3,4kHz 8000 eantioane/s x 8 bii/eantion = 64kb/s

Voce de band larg banda=7kHz

16000 e./s x 14 bii/e. = 224kb/s

CD-audio banda=22kHz 44100 e/s x 16 bii/e. (stereo) = 1,41 Mb/s

Imagini 512x512 pixeli x 24 bii/pixel = 6,3 Mb/imagine Video 640x480 pixeli color x 24 bii/pixel x 30 imagini/s = 221Mb/s

Diferena ntre banda disponibil i banda cerut pentru informaia necomprimat poate fi acoperit prin compresie.

2

2.1. Performanele compresiei Rata sau gradul de compresie - Majoritatea specificaiilor: raportul ntre cantitatea datelor la intrare i la ieire. - Problema: compatibilitatea datelor de la intrare i ieire

De exemplu: intrare: 512 x 480 pixeli, 24 bii pe pixel = 737 280 bytes ieire: 15 000 bytes rata de compresie: 737 280 / 15 000 = 49:1

Dar dac ieirea este o imagine cu o rezoluie de 256 x 240 pixeli rezult o reducere de 4 ori a imaginii deci o rat compresie de

(737 280 / 4) / 15 000 = 12:1. - Trebuie specificat numrul de bii pe pixelul afiat pentru fluxul comprimat.

De exemplu: imaginea de ieire are rezoluia 256 x 240 pixeli i este obinut din fluxul de 15 000 bytes. Rezult (15 000 x 8) / (256 x 240) = 2 bii pe pixel.

3

Calitatea imaginii - Se poate realiza compresie cu pierderi sau fr pierderi. - Compresia cu pierderi folosete o codare mai eficient dect codarea fiecrei valori din fluxul de

date de intrare.

- Reducerea numrului de bii (cuantizarea) pentru compresia cu pierderi se face pe baza unor:

- evaluri subiective (cele mai importante):

Scor Calitate Modificarea imaginii 5 Foarte Bun Imperceptibil 4 Bun Abia perceptibil dar nesuprtoare 3 Acceptabil Perceptibil i puin suprtoare 2 Slab Suprtoare dar fr pierderea

semnificaiei 1 Proast Foarte suprtoare i cu pierderea

semnificaiei

4

- evaluri obiective (PSNR = Peak Signal to Noise Ratio)

( ) ( )2

225510log ( )

, ,PSNR dB

X i j Y i j=

PSNR Calitate > 40dB Foarte bun 30 40dB Bun < 30dB Slab

Viteza de compresie i de decompresie - Compresia i decompresia nu dureaz ntotdeauna la fel de mult

Exemplu:

- stocarea imaginilor compresia nu este critic, decompresia poate fi critic - Video-on-Demand decompresia este critic (cerine de timp real la redare). - TVoverIP compresia i decompresia sunt critice (cerine de timp real la transm. i redare)

- Realizarea de sisteme hardware specializate pe compresie i decompresie

5

2.3. Codarea surselor analogice

Sunetele i imaginile digitale provin din semnale continue n timp/spaiu i n amplitudine; EANTIONAREA Pentru o reprezentare discret n timp semnalele continue sunt eantionate cu o frecven de

eantionare;

n domeniul frecven spectrul semnalului eantionat este repetarea periodic a spectrului

semnalului continuu pe multiplii de frecvena de eantionare;

6

Pentru ca semnalul original s poat fi refcut trebuie ca frecvena de eantionare s fie de dou ori mai mare dect frecvena maxim a spectrului semnalului continuu;

CUANTIZAREA Eantioanele au ns valori reale. Pentru o reprezentare discret pe un numr de bii a

eantioanelor este necesar cuantizarea;

n funcie de numrul de bii ales putem reprezenta mai multe niveluri ale amplitudinii eantioanelor. (3 bii nseamn 8 niveluri, 4 bii - 16 niveluri etc.)

7

Cu ct numrul de bii scade cu att eroarea de cuantizare crete.

Eroare de cuantizare zero nseamn numr infinit de bii.

8

Rezult c trebuie acceptat o anumit distorsiune n reprezentarea digital a semnalelor. Aceasta depinde de rata de bit RC.

Rat de bit: numr de bii pe secund; Distorsiune: Eroarea ptratic medie: 2E{[ ( ) ( )] }D x t x t=

Teorema lui Shannon: Pentru un proces aleator Gausian alb cu lrgimea de band W rata de bit

depinde de raportul semnal-zgomot:

9

De exemplu: Semnal vocal cu banda 4W kHz= i 40SNR dB=

Codarea PCM (Pulse Code Modulation): Eantionarea semnalului => semnal n timp discret, Cuantizarea semnalului => semnal digital, Codarea cu numr variabil de bii => reprezentare mai eficient;

10

Distorsiunea n acest caz este: esantionare cuantizareD D D= + Distorsiunea de eantionare provine din faptul c dac semnalul analogic are banda mai mare de

/ 2Sf acesta este filtrat trece-jos (LP) pentru a putea fi eantionat:

Distorsiunea de cuantizare provine din faptul c pentru fiecare bit n plus eroarea de cuantizare se njumtete i distorsiunea se micoreaz de 4 ori: 22 BD .

De asemenea D este proporional cu energia semnalului: 2xD .

unde c este o constant;

Rata de bit este:

11

Scriind raportul semnal zgomot n decibeli:

Constanta c, deci i 2c , depinde de tipul de cuantizare. Pentru cuantizarea uniform 2 7c dB . De exemplu: Telefonia digital cu 8bii/eantion: 41SNR dB=

12

2.4. De ce pot fi comprimate semnalele? amplitudinea semnalului este statistic redundant

Exemplu:

- un semnal are amplitudinea n intervalul [0,7] - sunt necesari 3 bii pe eantion

13

Valoare

Probabilitatea de apariie

Codare PCM

Codare entropic

0 0,125 000 100 1 0 001 2 0,5 010 0 3 0 011 4 0,125 100 101 5 0,125 101 110 6 0 110 7 0,125 111 111

reprezentarea amplitudinii pe un numr infinit de bii este (perceptual) irelevant. - Valoarea eantioanelor este cuantizat n funcie de diferena minim perceput. amplitudinile semnalului sunt mutual dependente (corelate)

14

- Exemplu de semnal fr o corelaie ntre amplitudinile succesive este zgomotul alb gausian. - Putem exploata corelaia ntre eantioane prin:

- Predicia eantionului urmtor pe baza celui curent ( ) ( ) , 1,x i j x i j= - Calculnd diferena ntre valoarea eantionului i cea prezis ( ) ( ) ( ) ( ) ( ), , , , 1,x i j x i j x i j x i j x i j = =

Aceast diferen are (n medie) un interval mult mai mic de valori (varian mai mic). => Se poate cuantiza diferena pe un numr mai mic de bii.

2.5. Tipuri de codri Codarea include compresia, securizarea datelor i controlul erorii

Codarea entropic

Codarea Run-Length Fr

pierderi Codarea Huffman Codarea Aritmetic

15

Codarea sursei

Predicie DPCM

Cu pierderi

Iau n considerare coninutul

DM

Transformri FFT DCT

Codare pe niveluri

Poziia biilor Subeantionare

Codare pe subbenzi

Cuantizarea vectorial

Codare hibrid

JPEG MPEG H.261

Codarea entropic - Pentru un set de simboluri cu probabilitile de apariie cunoscute

1 2, , ..., Np p p - Informaia proprie simbolului i este:

log iI p= - Entropia sursei este suma informaiilor pentru toate simbolurile:

16

( )1 21

, , ..., logN

N i ii

E p p p p p=

=

- Compresia caut s realizeze reprezentarea mesajelor cu numrul de bii minim corespunztor coninutului de informaie. Limita minim a compresiei este entropia.

- Codurile cu redundan minim au lungimea medie minim pentru o anumit distribuie de

probabiliti. - Raportul de compresie este lungimea medie a simbolurilor mprit la lungimea medie a

cuvintelor de cod (n bii). Codarea Run-Length - Eliminarea caracterelor care se repet

- zerouri n fiiere de date numerice - spaii n fiiere text - zone de aceeai crominan sau luminan n imagini

- Codarea numrului de apariii: - este necesar un indicator (flag)

17

Exemplu: flag = !, datele comprimate conin caracterul ! - numr de apariii intrare: ABCCCCCCCCDEFGGGGG (18 caractere) ieire: ABC!8DEFG!5 (11 caractere)

Codarea cu numr variabil de bii pe simbol - Se obine o rat mai mare de compresie - Caracterele care apar mai frecvent se codeaz cu mai puini bii - Caracterele care apar mai puin frecvent se codeaz cu mai muli bii Codarea Huffman 1. Se ordoneaz simbolurile n ordinea descresctoare a probabilitii. 2. Se grupeaz ultimele dou simboluri i se adun probabilitatea lor formnd un nou simbol. 3. Se reordoneaz noul set n ordinea descresctoare a probabilitii 4. Se repet paii 2 i 3 pn rmn dou probabiliti 5. Se aloc bitul 0 uneia din probabiliti i bitul 1 celeilalte. 6. Se merge n sens invers adugnd cte un bit la fiecare grup de 2 simboluri. 7. Se formeaz cuvintele de cod

18

si Ps(si) Cuvntul

de cod 0 0,005 1001111 1 0,05 100110 2 0,14 101 3 0,20 11 4 0,51 0 5 0,08 1000

19

6 0,04 10010 7 0,005 1001110

- Codarea iniial ar necesita 3 bii pe simbol.

Entropia H(S) = 2.024 bii/simbol Lungimea medie L = 2.204 bii/simbol

- Permite decodarea instantanee a fluxurilor de date Mesajul codat: 101 11 1000 100110 Mesajul decodat: 2 3 5 1

Codarea Aritmetic - Se consider intervalul [min, max) care iniial este [0,1) . Lungimea intervalului este:

max min 1 = . - Intervalul este mprit la numrul de simboluri, fiecare avnd aceeai probabilitate. - Presupunem c simbolurile sursei au fost numerotate de la 1 la n i prob. simbolului i este ip . - Simbolul k este codat cu un numr ntre [min, max) astfel:

20

1. Se calculeaz probabilitile dinamic.

2. 1

1inf

k

kp

= ; 1

supk

kp= 3. min maxr =

4. max' min supr= + min' min infr= +

- Codarea irului bcca se face cu orice valoare n intervalul [.6334,.6390) Codarea Diferenial PCM (DPCM) i codarea predictiv (LPC) - Valorile viitoare ale semnalului pot fi aproximate (prezise) din comportamentul (eantioanele)

anterioare datorit corelaiei ntre eantioanele semnalului. - Codarea DPCM se bazeaz pe faptul c orice poate fi prezis din semnal la codare poate fi

reconstruit la decodare. - Etapele codrii DPCM:

_

_

_

_

a

b

c

0

1/3

2/3

1

_

_

_

b

c

a

_

_

_

_

a

b

c

_

_

_

a

b

c

1/3

1/3

1/3

1/4

2/4

1/4

1/5

2/5

2/5

1/6

2/6

3/6

.3333

.4167

.5834

.6667

.5834

.6001

.6334

.6667

.6334

.6390

.6501

.6667

21

1. Prezicerea valorii curente ( )x n din valorile anterioare ( 1)x n , ( 2)x n , ... 2. Calculul diferenei (eroarea de predicie) ntre valoarea curent i valoarea prezis: ( ) ( ) ( )x n x n x n = 3. Codarea erorii prediciei (cuantizarea + codarea VLC = cu numr variabil de bii) se poate face cu un numr mai mic de bii.

Predictor Memorie

Q VLC( )x n ( )x n ( )qx n

( )x n( )x n

00010100101

- Decodorul trebuie s reproduc aceeai valoare prezis ( )x n din valorile anterior decodate

( )1x n , ( )2x n ...

22

Predictor Memorie

QVLD( )v n ( )x n

( )x n

00010100101

- Pentru predicie se poate folosi:

- PCM: ( ) 0x n = - Simpla diferen: ( ) ( 1)x n x n= - Media ponderat a ultimelor dou eantioane: 1 2( ) ( 1) ( 2)x n h x n h x n= + - Predictor liniar general:

1

( ) ( )N

kk

x n h x n k=

=

- Eroarea de reconstrucie/codare:

23

*

*

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( )

r n x n x n x n x n x n

x n x n q n

= = + = = =

- Rezult c eroarea global de reconstrucie n DPCM este egal cu eroarea de cuantizare a

diferenei ( )x n . - Raportul semnal-zgomot va fi determinat de performanele cuantizorului relativ la variana

semnalului ( )x n . Codarea cu transformate

24

- O transformat convertete un set de date ntr-o reprezentare alternativ care este mai convenabil pentru codare

- Transformatele sunt reversibile Exemplu: - un bloc de 2 x 2 pixeli:

A B Transformata: X0 = A X1 = B A X2 = C A X3 = D A

Transformata invers: A = X0 B = X1 + X0 C = X2 + X0 D = X3 + X0

C D

- A, B, C i D au fiecare 8 bii - X0 este codat pe 8 bii (pixelul de baz) - X1, X2 i X3 necesit numai 4 bii - 8 + (3 x 4) = 20 => 5bii/pixel

Transformata Cosinus Discret (DCT)

25

- Conversie imagine frecven. - Importana informaiei de frecven:

- variaii lente de intensitate n imagine sunt cel mai bine percepute de ochi. - variaiile lente corespund frecvenelor joase. - tranziiile brute (pixelii de zgomot) corespund frecvenelor nalte i nu sunt percepute de ochi.

- Pentru un bloc din imagine de 8 x 8 pixeli, DCT este dat de: ( ) ( )7 7

0 0

2 1 2 1cos cos

16 16mn m n yxx y

x m y nC k k I

= =

+ +=

unde

1 , pentru , 02 2,

1 , n rest2

m n

m nk k

==

- Coeficientul 00C se numete coeficient DC i reprezint frecvena spaial 0 sau media valorilor

pixelilor din bloc.

26

- Ceilali coeficieni se numesc coeficieni AC i reprezint frecvenele spaiale orizontale i verticale din bloc.

- Se poate da i o reprezentare matricial:

TY = C XC

unde X este un bloc de NxN pixeli din imagine, Y conine NxN coeficieni DCT, iar C este o matrice NxN cu elementele:

( )2 1cos2mn n

m nC k

N+= ,

1 , pentru 02 2

1 , n rest2

n

nk

==

- DCT nu realizeaz compresia datelor Transformata Cosinus Discret Invers (IDCT)

27

( ) ( )7 70 0

2 1 2 1cos cos

16 16xy u v vuu v

x u y vI k k C

= =

+ +=

unde

1 , pentru , 02 2,

1 , n rest2

u v

u vk k

==

- Teoretic transformarea DCT IDCT este fr pierderi Codarea n subbenzi

28

- S presupunem c un semnal are cea mai mare parte a energiei concentrate n domeniul frecvenelor joase.

- Se efectueaz o eantionare cu 10kHz, 8 bii pe eantion. Rata de transmisie necesar este de 80kbii/s.

- O transmisie mai eficient se poate realiza diviznd domeniul de frecven n dou subbenzi:

FTJ FTJ

FTS FTS

- Prin decimare se pstreaz numrul de eantioane constant, repartizate pe subbenzi. - Pentru primul semnal CODEC1 va aloca tot 8 bii. - Deoarece energia coninut n al doilea semnal este mai mic CODEC2 poate aloca numai 4 bii. - Rezult n total 5 x 8 + 5 x 4 = 60kbii/s, deci o reducere cu 3/4. - n cazul 2D se pot folosi filtre separabile rezultnd patru descompuneri JJ, JS, SJ, SS.

29

Reprezentare polifazic

- Dac matricea ( )zE este matricea de la transformata DCT i ( )zR este matricea de la

transformata IDCT atunci codarea pe subbenzi devine codarea cu Transformata Cosinus Discret. - Codarea n subbenzi poate fi privit ca o codare prin transformate cu blocuri suprapuse. Deci

poate exploata corelaia ntre pixeli pe domenii mai largi.

30

- Efecte ale codrilor - prin transformate: se observ blocurile pe care s-a aplicat transformata. - n subbenzi: apariia unor inele i o accentuare a contururilor.

Alocarea optim a biilor - Se poate aloca diferit numrul de bii pe eantion pentru fiecare subband n funcie de

caracteristicile semnalului n acea subband - Considerm c semnalul kx din fiecare subband k se cuantizeaz pe kb bii. Eroarea de

cuantizare este:

22 22 kk k

bq xc =

unde 1/12c = . - Eroarea total de cuantizare este:

2 2

1

1k

M

q qkM

=

= - Rata total de bit este:

1

1 Mk

kb b

M ==

31

- Se arat c 1/

2 2 2

1

2k

MMb

q xk

c =

. Egalitate avem pentru 2 2kq q k = - Rezult alocarea optim a biilor:

2

2

1 log2

kxk

q

cb

=

- Ctigul este 2

11/

2

1

1

1k

k

M

xk

MM

xk

MG

=

=

=

.

Avem ctig unitar dac 2

kx sunt egale.