Download - 2 compresie
-
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.