Curs04_saccdmm_codare_transformari.pdf

SACCDMM - Curs 05Sisteme de codare bazate pe transformari

Topicul cursului

• Transformări de imagini• Transformări ortogonale• Transformări 2D• DCT, IDCT

Curs - SACCDMM - an I Master TM, Semestrul I2

Transformări de imagini• Compresia imaginilor prin transformări:

• transformarea intensităților pixelilor - care sunt valori corelate - într-oreprezentare în care acestea sunt decorelate

• Decorelare• valorile după transformare sunt independente una de alta• media noilor valori este mai mica decât a valorilor iniţiale

• Compresia• o imagine poate fi comprimată dacă prezintă redundanţă

• Intensitățile pixelilor sunt corelate• Compresia cu pierderi

• se realizează prin transformare urmată de cuantizare

• Transformările tratate• Ortogonale (DCT)• Sub-banda (Wavelet)


Algoritmul de codare prin transformări• u [Nx1]• transformarea A – matrice NxN• v – vector complex (componente necorelate)• cuantizare independenta a componentelor• v’ – vectorul de iesire cuantizat• transformarea B – matrice NxN• u’ – vectorul de iesire


u =

u(1) u(2) : : u(N)

v(1) v(2) : : v(N)

v'(1) v'(2) : : v'(N)

u'(1) u'(2) : : u'(N)

Transform. liniară A

Transform. liniară B = u' v =

Transformări de imagini – exemplu [Salomon, 2007]

• scanare imagine• extragere perechi de intensități

adiacente (x, y)• o pereche va fi un punct in

reprezentarea grafica x vs. y (vezi fig. a)• în general, valorile x, y, sunt aproximativ

egale pentru pixelii adiacenţi• y=x → punctul e pe axa de 45º• y≈x → punctul e in jurul axei de 45º

• aplicarea unei transformări• rotire cu 45º (vezi fig. b)

• y devine aproape 0,• x nu se schimbă mult


Transformări de imagini – exemplificare


Scanare imagine – extragere perechi de intensități vecine (x, y):

x y x y … x y

…

…

…

… … … … … … …

…

…

Distribuţiile pe x, y sunt aproximativ asemănătoare înainte de transformare

Distribuţiile pe x, y sunt DIFERITE după transformare –y aproximativ 0, scalare pe 101; x nu se modifică substanţial

Transformări de imagini• Verificarea reducerii redundanței după aplicarea transformatei

• calcul inter-corelație a valorilor• pentru punctele (xi,yi): ∑i xiyi

• Energia – compactare si conserva• Compresie:

• se transmit valorile obținute după transformare = coeficienții transformării• se pot transmite sub forma a doi vectori X, Y → rezultă şiruri lungi de zero

• X – vectorul transformării intensităților de pe pozițiile impare• Y – vectorul transformării intensităților de pe pozițiile pare

• după transformare - se pot adăuga alte metode de compresie• dacă se acceptă compresie cu pierderi – transformarea este urmata de

cuantizare => valori mai mici• Concentrarea energie într-o componenta

• Face posibila cuantizarea mai fină a vectorului X si mai puternica a lui Y


Transformări ortogonale• “Proprietăţile” transformărilor de imagini

• Reducerea redundanţei imaginii – prin reducerea valorii pixelilor• Identificarea părţilor mai puţin importante din imagine prin izolarea

diferitelor frecvenţe (benzi de frecvenţă) din imagine

Frecvenţa orizontală


Transformări ortogonale• Frecvenţa

• Joase – caracteristicile importante din imagine• Înalte – detalii mai puţin importante

Original FTJ FTS


Transformări ortogonale• Izolarea frecvenţelor

• Se pot aplica grade de cuantizare diferită pentru diversele benzi defrecvenţă

• Transformările implementate practic• Rapide• Uşor de implementat• În general se folosesc transformările liniare


Transformări ortogonale• Transformări liniare:

• Forma matricială: C=W·D• Unde:

• wij (fiecare rând-vector de bază) se calculează în funcţie de tipultransformatei şi trebuie să:• reducă redundanţa• izoleze frecvenţele

• di = sunt valori pozitive şi corelate (intensități)• ci = suma ponderată a tuturor intensităților di (care sunt transformate)

• primul ci va avea o valoare mai mare wij având doar valori pozitive• ceilalți coeficienți ci vor avea valori mai mici dacă wij vor fi pozitivi și

negativiCurs - SACCDMM - an I Master TM, Semestrul I11

Transformări ortogonale• Pentru a putea izola diferitele frecvenţe

• vectorii de bază trebuie să fie ortogonali adică matricea W esteortogonală (Ortogonală ↔ inversa ei = cu transpusa)

• Exemplu de W: număr egal de 1, -1• Primul rând wij va fi numai de 1• Rândul 2 va avea o singură schimbare de semn• Rândul 3 va avea 2 schimbări de semn ş.a.m.d.

• Transformarea Walsh-Hadamard:

• Pentru conservarea energiei• Se multiplică W cu un factor de scală ½

111111111111

1111

W


Transformări ortogonale – conservarea energie•

2222 ,,, energia - dcbadcba


111111111111

1111

W

Transformări ortogonale• Doar prin transformare NU obținem compresie!!! Este necesară cuantizarea pentru a avea compresie

• Fie rotunjirea la valori întregi• Rezultatul transformarii inverse va fi diferita de original

• Fie trunchierea (|ci|<2 atunci zero)• Rezultatul transformarii inverse va fi diferita de original

• Chiar dacă sunt diferite, matricile sunt foarte apropiate deoriginal => compresie cu pierderi

• Pentru a obţine un raport de compresie ridicat – algoritmisuccesivi, transformări complexe

TC 0319'

TC 05.205.8'

TCWD 5.25.55.65.3'2'

TCWD 35.55.53'2'


TD 2564 TDWC 5.05.24.15.82

Se aplică 1D pe linii

Mai avem corelaţie între elementele de pe linii se aplică 1D pe coloane, W- simetrică deci

C este decorelată și elementul din stânga sus – este dominant Primele rânduri şi primele coloane (colţul stânga sus) conţin elemente importante Compresie – dacă se aplică cuantizare Se pot elimina în special elementele din dreapta-jos – elementele de înaltă

frecvenţă

Transformări bidimensionale

8888667757564765

D


320212205044

23282626

8888667757564765

111111111111

1111

' DWC

13371315

55313551103

111111111111

1111

320212205044

23282626

' TWCCWDWWDWWCC TT '

Transformări bidimensionale• Transformata Walsh-Hadamard

• Rapidă şi uşor de implementat• Slabe performanţe în compactarea energiei

• Transformata Haar• Simplă şi rapidă (cea mai simplă dintre transformatele Wavelet)

• Transformata Karhunen-Loeve• Cea mai bună variantă teoretică – compactarea energiei• Coeficienţii nu sunt ficşi – depind de datele de la intrare; calcule

complicate; coeficienţii trebuie incluşi în şirul codat (necesari ladecodare)

• Transformata Cosinus Discretă• Aproape la fel de eficientă ca şi KLT• Foloseşte vectori de bază ficşi


DCT – Discrete Cosine Transform

1,...,2,1,00 dacă ,1

0 dacă ,2

1,

212cos2 1

0

nff

fCn

ftpCn

G f

n

ttff

• Pt intrările – pixeli, eşantioane audio, etc.,• Gf ieşirile sunt coeficienţii transformatei DCT• G0 coeficientul DC, restul sunt coeficienții AC• Intrările valori întregi, ieşirile valori reale pozitive şi negative• Calcule greoaie – timpi de calcul mari – necesitatea alegerii DCT

rapide


IDCT:

1

0 212cos2 n

jjjt n

jtGCn

p

• concentrează energia într-un număr mic de coeficienţi• cei mai mulţi coeficienţi sunt zero sau foarte apropiaţi de zero• în aplicaţiile practice datele sunt împărţite în seturi de n valori

• n mic seturi multe de coeficienţi – puţini zero• n mare datele nu sunt corelate nu se pot obţine coeficienţi zero• în general n=8

Exemplu DCT şi IDCT … cuantizarea!• Imagine: 12108101210811• Coeficienţii DCT:

• Dacă se păstrează toţi coeficienţii se poate reface IDCT rezultândimaginea (setul de date) iniţială

• Cuantizare1• IDCT …

• Cuantizare2• IDCT …

• Cuantizare3 …doar 4 coeficienti• IDCT…


DCT-2D• Pe rânduri• Apoi pe coloane• Transformarea pe blocuri de pixeli


Exemple cu privire la proprietatea de compactare a energiei pentru imagini standard


Sistem de codare cu DCT

Imagine originalăBlocuri de 8x8

Transformata DCT 8x8 DCT

Cuantizarea coeficienţilor DCT

Codare entropică

Informaţie comprimată


Codarea pe blocuri de pixeli• algoritmi de codare spaţială pe blocuri

• gruparea pixelilor în blocuri• metode clasice de compresie spaţială• compresie mai bună decât varianta clasică

• algoritmi de codare prin transformări• gruparea pixelilor pe blocuri• transformarea într-un alt domeniu (frecvenţă)• DFT, DCT, DST, Hadamard


Alocarea bitilor• dispersia coeficienţilor nu este uniformă• cuantizare cu număr diferit de biţi• numărul biţilor de cuantizare este nk întreg


8 7 6 5 3 3 2 2 2 1 1 1 1 1 0 0 7 6 5 4 3 3 2 2 1 1 1 1 1 0 0 0 6 5 4 3 3 2 2 2 1 1 1 1 1 0 0 0 5 4 3 3 3 2 2 2 1 1 1 1 1 0 0 0 3 3 3 3 2 2 2 1 1 1 1 1 0 0 0 0 3 3 2 2 2 2 2 1 1 1 1 1 0 0 0 0 2 2 2 2 2 2 1 1 1 1 1 0 0 0 0 0 2 2 2 2 1 1 1 1 1 1 1 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

alocarea bitilor pentru DCT pe fereastra de 16x16 pixeli pentru o rata medie de 1bit/pixel

Codarea prin transformare bidimensionala• divizarea imaginii de intrare

• MxN -> rezulta NM/pq blocuri de dimensiune pxq• se reduce capacitatea de calcul• se reduce numărul de operatii necesare pentru calculul transformatei

(inclusiv prin implementarea algoritmilor rapizi de calcul)


q p

p q

uj

u'j

ApUiATq Cuantizare Codare Transm./

memorare

Decodare A*TVjA*qp

r - rata compresiei (biti/pixel)

r

2,5

2,0

1,5

1,0

0,5 2x2 4x4 8x8 16x16 32x32 64x64 128x128

Dimensiunea blocurilor

Codarea prin transformare bidimensională• alocarea bitilor• alegerea cuantizorului (coef. CC, CA)• codarea ieşirii cuantizorului• reproducerea coeficienţilor (canal fără zgomot)


Codarea zonală şi codarea cu prag• doar o mica zonă din imaginea transformată se transmite

(alocarea biţilor)• codarea zonala

• masca zonala

• codarea cu prag• pragul

• masca cu prag

• ordonarea “zig-zag”


Exemple DCT-2D corelat-aleator• corelate


Exemple DCT-2D corelat-aleator• aleator


Exemple DCT-2D nivele de gri-binare


Cum să folosim DCT• P vectorul de intrare• Să considerăm n=3 se poate scrie ecuaţia DCT

• Putem ignora


Cum să folosim DCT• Matricea ortogonală dar nenormată

• DCT normată…


Obţinerea matricei DCT• Se selectează n unghiuri

• Se calculează vectorii vk

• Se normalizează fiecare vector şi se creează matricea DCT• n=8


Obţinerea matricei DCT


Din nou exemple de DCT-2D


Codarea DCT


Codarea DCT

161 155 157 152 151 151 149 149 163 162 160 155 156 153 153 152 163 165 162 157 157 153 156 155 168 164 162 160 157 156 160 156 166 164 161 163 157 157 162 158 164 165 161 161 161 156 162 160 163 159 160 161 162 161 159 162 165 162 162 168 163 161 160 163

33 27 29 24 23 23 21 21 35 34 32 27 28 25 25 24 35 37 34 29 29 25 28 27 40 36 34 32 29 28 32 28 38 36 33 35 29 29 34 30 36 37 33 33 33 28 34 32 35 31 32 33 34 33 31 34 37 34 34 40 35 33 32 35

-128

251 19 6 0 2 3 -2 2

-21 10 3 1 -4 -1 2 3

-8 -2 -4 1 3 -2 5 -1

-6 -1 1 1 0 1 0 1

0 1 0 1 1 5 1 -2

-4 -1 1 1 0 0 3 1

0 1 0 -2 0 -1 -2 1

-2 -1 -1 -1 0 0 1 -1

16 11 10 16 24 40 51 61 12 12 14 19 26 58 60 55 14 13 16 24 40 57 69 56 14 17 22 29 51 87 80 62 18 22 37 56 68 109 103 77 24 35 55 64 81 104 113 92 49 64 78 87 103 121 120 101 72 92 95 98 112 100 103 99

initiala

Coef. DCT Matrice de cuantizare Coef. DCT cuantizati

16 2 1 0 0 0 0 0 -2 1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Codarea DCT

256 22 10 0 0 0 0 0 -24 12 0 0 0 0 0 0 -14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

162 160 157 153 151 149 149 148 163 162 158 155 153 151 151 151 166 164 161 158 156 155 155 155 167 166 163 161 159 158 158 159 168 167 164 162 161 161 161 162 167 166 164 162 161 161 162 163 166 164 163 161 161 161 162 163 164 163 162 160 160 161 162 163

IDCT; +128

1 5 0 1 0 -2 0 -1 0 0 -2 0 -3 -2 -2 -1 3 -1 -1 1 -1 2 -1 0 -1 2 1 1 2 2 -2 3 2 3 3 -1 4 4 -1 4 3 1 3 1 0 5 0 3 3 5 3 0 -1 0 3 1

10 1 1 2

0 0

25520log1 ˆ( , ) ( , )

N M

x y

eroareaX x y X x y

MN

40.67 dB


Codarea DCT

172 77 102 193 159 65 103 188 135 64 133 195 119 59 132 184 99 65 157 183 89 64 152 168 82 74 169 164 60 73 168 143 64 92 179 139 51 95 172 119 46 119 178 104 50 121 170 87 42 137 171 72 59 139 156 69 70 162 150 55 70 154 139 55

163 70 115 204 140 60 108 187 134 63 125 197 120 65 129 187 99 66 146 185 87 71 151 173 74 82 168 165 56 78 163 143 54 101 177 136 42 97 169 115 41 119 169 102 46 124 168 93 47 143 160 74 59 145 155 68 61 164 157 58 68 154 138 46


Algoritmi de calcul rapid al DCT• 1D DCT pe 8 puncte – 64 înmulţiri; 56 adunări• Algoritmul I – simetric


Algoritmi de calcul rapid al DCT• Algoritmul I – simetric

• 22 înmulţiri şi 28 (6+6+16) adunări


Algoritmi de calcul rapid al DCT• Algoritmul II – CHEN• Pasul 1

• Pasul 2

X(0) a0

X(1) a1

X(2) a2

X(3) a3

X(4) a4

X(5) a5

X(6) a6

X(7) a7

b0

b1

b2

b3

b4

b5

b6

b7

I II z0

z1

z2

z3

z4

z5

z6

z7

III

c4

c4

5.0 Y(0)

5.0 Y(4)

0.5 Y(2)

0.5 Y(6)

0.5 Y(1)

0.5 Y(5)

0.5 Y(3)

0.5 Y(7)

IV

c2

c2

s2 s2

c1

c1

s1 s1

c5

c5

s5 s5

Unde avem următoarele notaţii: m

n

m+n

m-n

m

n

m n mn


Algoritmi de calcul rapid al DCT• Algoritmul II – CHEN … rezultă 16 înmulţiri şi 26 adunări• Pasul 3

• Pasul 4


Comparaţie

• DCT 2D 8x8 pixeli clasic avem 1024 înmulţiri şi 896adunări


Problema


Curs04_saccdmm_codare_transformari.pdf

Documents

Transcript of Curs04_saccdmm_codare_transformari.pdf