Programul de studii: Matematic a si Informatic a Aplicat a n Inginerie [618803]

UNIVERSITATEA POLITEHNICA DIN BUCURES TI
FACULTATEA DE S TIINT E APLICATE
Programul de studii: Matematic a  si Informatic a Aplicat a ^ n Inginerie
PROIECT DE DIPLOM A
COORDONATOR S TIINT IFIC, ABSOLVENT: [anonimizat].dr. Vladimir BALAN Albu Iuliana-Cristina
Bucure sti
2017

UNIVERSITATEA POLITEHNICA DIN BUCURES TI
FACULTATEA DE S TIINT E APLICATE
Programul de studii: Matematic a  si Informatic a Aplicat a ^ n Inginerie
Aprobat Decan,
Prof. Univ. Dr. Emil PETRESCU
PROIECT DE DIPLOM A
Specicul  si actualitatea compresiei JPEG
^ n imagistica digital a
COORDONATOR S TIINT IFIC, ABSOLVENT: [anonimizat].dr. Vladimir BALAN Albu Iuliana-Cristina
Bucure sti
2017

Cuprins
Introducere 4
1 Compresia imaginii 6
1.1 Reprezentarea  si caracterizarea imaginilor . . . . . . . . . . . . . . . . . . 6
1.1.1 Repartizarea imaginilor . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Caracterizarea matematic a a imaginilor digitale . . . . . . . . . . . 7
1.1.3 Operat ii asupra imaginilor . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Reprezentarea numeric a a imaginii . . . . . . . . . . . . . . . . . . . . . . 10
2 Fi siere JPEG 12
2.1 Stocarea imaginilor ^ n memorie . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Stocarea imaginilor ^ n  siere . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Prolul de culoare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Transformata cosinus discret a(DCT) 15
3.1 Transformata cromatic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Sub-e santionare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Descompunerea imaginii ^ n blocuri . . . . . . . . . . . . . . . . . . . . . . 18
4 Standardul JPEG 21
4.1 Codarea secvent ial a DCT cu pierderi . . . . . . . . . . . . . . . . . . . . . 21
4.2 Codarea expandat a DCT cu pierderi . . . . . . . . . . . . . . . . . . . . . 22
4.3 Codarea far a pierderi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.1 Codarea entropic a Human . . . . . . . . . . . . . . . . . . . . . . 23
4.3.2 Codarea RLC "Run Length Coding" . . . . . . . . . . . . . . . . . 25
4.4 Codarea ierarhic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5 Comparat ia dintre formatul JPEG  si formatul PNG 27
6 Concluzii 28
29
Index de abrevieri 30
3

Introducere
Compresia este necesar a pentru reprezentarea imaginilor ^ n format numeric, deoarece
consum a o cantitate mare de informat ie. Termenul de compresie se refer a la totalitatea
metodelor ce au ca scop reducerea cantit at ii de date necesare pentru reprezentarea unei
imagini. Compresia este folosit a ^ n general pentru stocarea sau transmiterea imaginilor.
Pentru a stoca o imagine avem nevoie de spat iu considerabil, iar pentru transmiterea
ei avem nevoie de un canal de transmisie de band a larg a. Cel mai frecvent imaginile se
codic a intr-o form a comprimat a, exist^ and ^ n momentul de fat a un num ar mare de tehnici
de compresie  si un num ar  si mai mere de formate: GIF, JPEG1,WIF, …
Compresia JPEG este numele dat unui algoritm dezvoltat de Joint Photographic Experts
Group, al c arui scop este de a minimiza dimensiunea  sierului fotograc. Scopul JPEG
a fost s a dezvolte o metod a de compresie a imaginilor cu ton continuu. ^In 1987 grupul
JPEG a desfa surat un proces de select ie bazat pe o apreciere direct a a calitat ii unei
imagini compresate  si a restr^ ans cele 12 metode propuse initial la 3[ ?,?].^In acest timp
au fost formate 3 grupuri de lucru pentru ^ mbun at at irea acestor metode iar ^ n ianuarie
1988, pe baza unui proces de select ie mult mai riguros, a fost dezv aluit a o nou a propunere
bazat a pe 8×8 DCT, care avea cea mai bun a calitate a imaginii.
JPEG este un sistem de compresie cu pierderi pentru imaginilie color si cu niveluri de
gri. Acesta funct ioneaz a pe 24 de bit i  si este proiectat astfel ^ nc^ at factorul de pierdere
sa poat a  reglat de c atre utilizator la dimensunea imaginii, calitatea imaginii,  si este
proiectat astfel ^ nc^ at pierderea are cel mai mic efect asupra percept iei umane.
O prezentare general a a procesului de compresie este prezentat ^ n gura 1.
Figura 1: Pa si ^ n compresia JPEG
La ^ nceputul compresiei JPEG sunt trei planuri de culoare, distribuite pe 8 bit i, ecare
reprezent^ and ro su, albastru  si verde (RBG). Acestea sunt culorile folosite de hardwere
pentru a genera imagini. Primul pas este de a transforma aceste planuri ^ n culori YIQ
sau YUV. Planul Y este folosit pentru a reprezenta luminozitatea imaginii, I reprezint a
interfaza  si Q este componenta de nuant  a (crominant a).
1JPEG-(Joint Photographic Experts Group) este o metod a de compresie a imaginilor fo-
tograce.Scopul formatului a fost de a reduce dimensiunea  sierelor ce cont in imagini grace de tip
fotograc, naturale  si cu un num ar mare de culori f ar a a afecta calitatea imaginii.
4

Urm atorul pas ^ n algoritmul JPEG este ^ mpart irea ec arui plan de culoare ^ n blocuri de
8×8. Fiecare bloc este apoi codicat separat. Primul pas ^ n codarea unui bloc este de
a aplica transformata cosinus ^ n ambele dimensiuni[ ?,?]. Aceasta returneaz a un bloc
8×8 de termeni de frecvent  a pe 8 bit i. P^ an a ^ n prezent aceasta nu introduce nici o
pierdere. Dup a transformata cosinus, urm atorul pas este de a utiliza cuantizarea scalar a
uniform a. Aceast a cuantizare este controlabil a pe baza parametrilor  si este principala
surs a de pierderi de informat ie ^ n compresia JPEG.Factorii de scalare sunt specicat i
^ ntr-un tabel 8×8, ^ n care sunt reprezentate frecvent ele. JPEG dene ste tabele de cuan-
ticare pentru componentele Y, I si Q. Mai jos sunt prezentate tabelele pentru luminant  a
 si crominant  a.
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[5]
Tabelul 1. Coecient ii de cuantizare pentru luminant  a
17 18 24 47 99 99 99 99
18 21 26 66 99 99 99 99
24 26 56 99 99 99 99 99
47 66 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99[5]
Tabelul 2. Coecient ii de cuantizare pentru crominant  a
5

Capitol 1
Compresia imaginii
1.1 Reprezentarea  si caracterizarea imaginilor
1.1.1 Repartizarea imaginilor
O imagine digital a este o matrice bidimensional a de e santioane, ^ n care ecare e santion
poart a numele de pixel. Precizia cu care se lucreaz a este determinat a de num arul de nivele
de gri cu care se poate reprezenta intensitatea unui pixel  si poate  exprimat a ca num arul
de bit i/pixeli. ^In fnct ie de acest parametru, imaginile pot  clasicate ^ n:
imagini binare reprezentate printr-un bit/pixel;
grac a pentru calculator ,reprezentat a prin patru bit i/pixeli;
imagini atonale ("grayscale" – pe scara de gri) , reprezentate prin opt bit i/pixeli;
imagini color , reprezentate prin  saisprezece,dou zeci  si patru sau mai mult i bit i/pixeli
[5].
^In general, reprezentarea imaginilor este realizat a ^ n domeniul continuu. Pentru o
imagine monocrom a, reprezentarea este realizat a prin intermediul unei funct ii F(x;y;t ),
unde (x;y) apart ine domeniului spat ial  si teste variabila timp.
Senzat ia de culoare se obt ine prin amestecul culorilor primare ro su ( Red), verde
(Green)  si albastru ( Blue). Dac a luam ^ n considerare spat iul de reprezentare a culo-
rilor R,G,B (gura 1.1), dreapta pentru care R=G=B reprezint a tocmai scara de gri ^ ntre
alb  si negru.
Figura 1.1: Reprezentarea imaginilor color ^ n spat iul RGB
^In practi a, imaginile sunt reprezentate ^ n domeniul discret spat ial prin intermediul ma-
tricelor [1]. O imagine digital a monocrom a este o funct ie bidimensional a care specic a
6

intensitatea luminii ^ n ecare punct:
x= 1;:::;N y = 1;:::;M
f(x;y) =2
6664f(1;1)f(1;2)::: f (1;M)
f(2;1)f(2;2)::: f (2;M)
…………
f(N;1)f(N;2)::: f (N;M )3
7775:(1:1)
unde pentru ecare 1 xN;1yM;(x;y) sunt coordonatele spat iale ale punc-
tului ^ n imagine  si f(x;y)f0;1;


;L1g, undeLeste num arul de niveluri de gri.
O imagine digital a color feste un vector cu componente matrice, ecare component a in-
dic^ and gradul de luminozitate al car arui pixel( x;y)^ n banda de culoare corespunz atoare.
De exemplu, ^ n reprezentarea RGB:1
x= 1;


;N y = 1;


;M f = (fR;fG;fB);unde
fR(x;y) =2
6664fR(1;1)fR(1;2)::: f R(1;M)
fR(2;1)fR(2;2)::: f R(2;M)
…………
fR(N;1)fR(N;2)::: f R(N;M )3
7775:
fG(x;y) =2
6664fG(1;1)fG(1;2)::: f G(1;M)
fG(2;1)fG(2;2)::: f G(2;M)
…………
fG(N;1)fG(N;2)::: f G(N;M )3
7775:(1:2)
fB(x;y) =2
6664fB(1;1)fB(1;2)::: f B(1;M)
fB(2;1)fB(2;2)::: f B(2;M)
…………
fB(N;1)fB(N;2)::: f B(N;M )3
7775:
1.1.2 Caracterizarea matematic a a imaginilor digitale
Tehnicile de procesare a imaginilor digitale implic a at^ at proces ari in cazul 2-D, situat ie
^ n care este utilizat a reprezentarea matriceal a conform relat iilor (1.1)  si (1.2), c^ at  si pro-
ces ari uni-dimensionale. Transformarea poate  efectuat a prin liniarizarea la nivel de
coloan a sau linie. ^In continuare fdesemneaz a reprezentarea matriceal a a unei imagini
monocrome.
Liniarizarea la nivel de coloan a
Pentrum= 1::M(coloan a)
a) Fievm= [0;0;:::;1;0;:::;0]T(1 pe pozit ia m) vectorul cu Melemente.
1RGB ro su, verde, albastru (Red, Green, Blue ^ n englez a)
7

f
vm=2
6664f(1:1)::: f (1;m)::: f (1;M)
f(2;1)::: f (2;m)::: f (2;M)
……
f(N;1)::: f (N;m )::: f (N;M )3
7775
2
66666666640
…
0
1
0
…
03
7777777775=2
6664f(1;m)
f(2;m)
…
f(N;m )3
7775:(1:1:1)
Vectorulf
vmreprezint a cea de a m-a coloan a din f.
b) FieNmmatricea cu NMlinii  siNcoloane.
Nm=2
6666666664ONN
…
ONN
IN
ONN
…
ONN3
7777777775matricea 1
…
matriceam1
matriceam
matriceam+ 1
…
matriceaM(1:1:2)
unde 0 NNeste o matrice de ordin Ncu toate elementele 0, iar INeste matricea
unitate de ordin N.
fcm=Nm
(f
vm) =2
6666666664ONN
(f
vm)
…
ONN
(f
vm)
INN
(f
vm)
ONN
(f
vm)
…
ONN
(f
vm)3
7777777775=2
6666666664ON1
…
ON1
f
vm
ON1
…
ON13
7777777775:(1:1:3)
undefcmeste vectorul cu MNelemente ^ n care doar cel de-al m-lea segment este
nenul  si egal cu coloana mdinf.
Transformarea invers a este :
f=PM
m=1NT
m
fc
vT
m
Liniarizarea la nivel de linie
Pentru n=1… N(linie)
a) FiewT
n=[0,0,…,0,1,0,…,0] (1 pe pozitia n) vectorul cu Nelemente.
wT
n
f= [0;0;:::;0;1;0;:::;0]
2
66666664f(1;1)f(1;2)


f(1;M)
f(2;1)f(2;2)


f(2;M)
…………
f(n;1)f(n;2)


f(n;M )
…………
(N;1)f(N;2)


f(N;M )3
77777775:
= [f(n;1)f(n;2)


f(n;M )]:
(1.1)
8

vectorul linie ndinf.
b) FieMnmatricea cu Mlinii  siNMcoloane.
Mn= [OMM


OMMIMMOMM


OMM]:
undeOMMeste o matrice p atratic a de ordin Mcu toate elementele 0, iar IMeste
matricea unitate de ordin M.
fln=wT
n
f
Mn=
wT
n
f
OMM::: wT
n
f
OMMwT
n
f
IMM::: wT
n
f
OMM
=
O1M::: O 1MwT
n
f
O1MO1M::: O 1M
:
undeflneste un vector cu NMelemente ^ n care doar elementul neste nenul  si egal
cu liniandinf[1].
Matricea liniarizat a pe linii este:
fl=NX
n=1wT
n
f
Mn:
Matricea inversa este:
f=NX
n=1wn
fl
MN
n:
1.1.3 Operat ii asupra imaginilor
9

1.2 Reprezentarea numeric a a imaginii
O imagine se reprezint a ca o matrice de puncte, ecare punct ind caracterizat de o cu-
loare. De exemplu pentru imaginea din gura 1.2(a) se poate evident ia acest lucru dac a se
m are ste o sect iune a imaginii astfet^ nc^ at matricea de puncte s a devin a vizibil a, ca^ n gura
1.3(b) [1].
Figura 1.2: (a)
Figura 1.3: (b)
Pentru a reprezenta o astfel de imagine trebuie sa utiliz am un mod de reprezentare
numeric al culorii. Pornim de la observat ia c a orice culoare se obt ine prin amestecul ^ n
diferite proport ii a trei culori de baz a, ro su, verde  si albastru. Intensitatea luminoas a a
unei culori poate  reprezentat a numeric sub forma unui intreg de opt bit i, valoarea 0
corespunz^ and intensitat ii nule iar cea maxim a ind reprezentat a de 255 [5]. La modul
ideal, nu se pot utiliza m arimi care variaz a continuu ^ n oricare direct ie. ^In sistemele
numerice, nu se pot utiliza m arimi care variaz a continuu ci doar ^ n forma discretizat a a
acestora. Discretizarea este operat ia prin cae se reprezint a o m arime cu variat ie continuu
sub forma unui ansamblu nit de e santioane[1]. De exemplu, temperatura mediului am-
biant variaz a ^ n mod continuu pe durata zilei, totu si se poate reprezenta evolut ia acesteia
prin intermediul valorilor m asurate la un interval de un minut. Se poate observa c a pentru
o captur a c^ at mai precis a, aceasta trebuie m asurat a la un interval c^ at mai scurt posibil.
^In caz contrar se pot pierde anumite variat ii care au ap arut ^ ntre dou a m asur atori.
10

^In concluzie, o imagine trebuie s a e discretizat a^ nainte de a pune problema reprezent arii
numerice. Discretizarea const a ^ n ^ mpart irea imaginii ^ ntru-un coroiaj asem an ator unei
table de  sah. Fiecare set iune sect iune de imagine delimitat a de acest coroiaj va  consid-
erat a ca av^ and o culoare uniform a, o medie a culorii existente pe aceasta set iune. Aceste
sect iuni mai sunt denumite  si pixeli  si num arul acestora denind rezolut ia imaginii. Astfel
se poate arma c a o imagine oarecare are o rezolut ie de 640×480 pixeli ceea ce ^ nseamn a
c a pe suprafat a acesteia s-a denit un coroiaj cae o ^ mparte pe orizontal a ^ n 640 de set iuni
iar pe vertical a ^ n 480. Operat ia de discretizare a unei imagini esre pus a ^ n evident a ^ n
imaginea imaginea de la gura 1.3(b), care a fost m arit a ^ n mod special pentru a se putea
observa coroiajul. Pasul urm ator ^ l constituie g asirea unei reprezent ari pentru culoare.
Orice culoare poate  descompus a ^ n culorile primare, cele ment inute mai sus, cu alte cu-
vinte orice imagine poate  obt inut a prin suprapunerea aditiv a a trei radiat ii luminuase
av^ and aceste trei culori  si intensit at i diferite. ^In gura urm atoare se prezint a obt inerea
c^ atorva culori prin acest mecanism:
Figura 1.4: Proul de culoare
Pentru a reprezenta numeric o culoare este sucient s a reprezent am intensit at ile lumi-
noase ale celor trei culori primare. Dac a aloc am c^ ate opt bit i pentru ecare component a
se pot codica 256 nivele de intensitate, astfel, absent a culorii se codic a prin valoarea
00000000 binar iar intensitatea maxim a prin cea mai mare valoare reprezentat a pe opt
bit i  si anume 11111111 binar.
Aceast a reprezentare t ine mai mult de modalit at ile tehnice de captare  si reproducere
a imaginii  si mai putin de mecanismul ziologic de percepere a culorii. Prin diferite
experimente s-a constatat din punct de vedere al capacit at ii de percepere a delatiilor,
ochiul este mai sensibil la intensitatea luminoas a a culorii de^ at la nuan ta. Din acest
motiv este interesant a o alt a modalitate de reprezentare a culorii care s a t in a cont de
aceast a observat ie, un exemplu ind reprezentarea YUV. ^In acest caz, ^ n locul celor trei
componente primare RBG se utilizeaz a alte trei m arimi derivate din acestea  si anume :
Y = 0.30R+0.5G+0.11B
U = R-Y=0.70R-0.59G-0.11B
V = B-Y=-0.30R-0.59+0.89B
11

^In cazul acestei reprezent ari, componenta Y corespunde intensit at ii luminoase perce-
pute pentru respectiva culoare. Aceast a component a mai poart a numele  si sub numele de
luminant  a
12

Capitol 2
Fi siere JPEG
2.1 Stocarea imaginilor ^ n memorie
Principalul limbaj de programare utilizat pentru aplicat ii cu calcule intensiv e r am^ ane
limbajul C(C++). Stocarea imaginilor se va face, evident, prin intermediul unor variabile
ce implementeaz a structuri de date bidimensionale. Ceea ce este deosebit, este modul de
declarare a acestora: declararea static a nu este convenabil a din cauza dimensiunilor ^ n
general mari ale imaginilor,  si deci este necesar a o declarare dinamic a. Particularitatea
este dat a de memorarea separat a a ec arei linii (sau coloane) a matricii ^ ntr-un vector
alocat dinamic,  si gruparea adreselor de ^ nceput a acestora ^ ntr-un vector de pointeri, la
care se va ret ine adresa de ^ nceput (deci un alt pointer) [3] Dac a consider am un tip generic
de date pentru componentele matricii (caracter sau ^ ntreg ori real), atunci o secvent  a C
de declarare a unei imagini poate :
tip ** imagine;
unsigned int contor;
imagine=(tip**) malloc(nr_linii*sizeof(tip*));
for (contor=0;contor<nr_linii;contor++)
imagine[contor]=(tip*) malloc(nr_coloane*sizeof(tip));
Se remarc a folosirea constantelor nrlinii sinrcoloane  si a tipului generic tippentru
valoarea pixelilor. Linia a 3-a aloc a spat iul pentru un masiv de de pointeri la date de
tip pointer; spat iul de memorie necesar (argumentul funct iei malloc ) este dat de num arul
de pointeri pe liniile imaginii ce ^ nmult e ste dimensiunea unui astfel de pointer ( sezeof(tip
*)). Valoarea imagine[contor] este adresa de ^ nceput a spat iului de memorie la care ^ ncep
valorile pixelilor de pe linia contor ; acet ia sunt stocat i ^ ntrun vector declarat de mal-
loc(nr coloane*sizeof(tip)) . Trebuie remarcat a convesia de tip(cast) obligatori ce ^ nsot e ste
ecare alocare de memorie. De asemenea se observ a c a secvent a anterioara nu face nici
un fel de vericare a succesului operat iei de alocare de memorie (vericarea faptului c a
valoarea returnat a de funct ia malloc nu este NULL ).^In mod implicit, tot i pixelii sunt
int ializat i cu 0 [5].
Spre deosebire de limbajul C, limbajul MatLab1aduce mari simplic ari. Exist a un
singur tip de date, reprezentate pe 8 octet i. Orice variabil a MatLab este creat a ^ n momen-
tul folosirii sale ^ n mombrul st^ ang al unei expresii; orice variabil a este o matrice (scalarul
este o matrice de o linie  si o coloan a).
1MatLab-Matrix Laboratory este un mediu interactiv de programare pentru calculele  stiint ice  si din
inginerie. Funct iile de baz a ale programului sunt extinse de numeroase pachete de funct ii specializate
pentru diferite domenii de aplicare.
13

Funct iile returneaz a matrici iar secvent a C, anterioar a, este echivalent a cu :
imagine=zeros(nr_linii,nr_coloane);
2.2 Stocarea imaginilor ^ n  siere
Un  sier este o entitate logic a de organizare a informat iei ^ nscrise pe mediile magnetice
de stocare  si se compune dintr-un  sir de octet i. Pentru stocarea imaginii este necesar ca
ace sti octet i s a cont in a informat ia pixelilor precum  si informat ia despre tipul imaginii:
dimensiunile acesteia, dac a este sau nuat a, dac a are sau nu o tabel a de culoare ata sat a,
dac a este sau nu comprimat a  si dup a ce metod a. Anumite structuri de  siere au fost
impuse de-a lungul timpului de rme produc atoare de software sau de organisme de stan-
dardizare, c apat^ and denumirea de formate de imagini. Formatele de imagini s-au f acut
cunoscute mai ales dup a extensia standard a  sierelor ce cont in imaginile stocate dup a
formatul respectiv: TIFF (Tagged Image File Format), GIF (Graphics Interchange For-
mat), PNG ( Portable Network Graphics), JPEG (Joint Photographic Experts Group),
etc.
14

2.3 Prolul de culoare
15

Capitol 3
Transformata cosinus discret a(DCT)
3.1 Transformata cromatic a
^Intr-o imagine color, JPEG comprim a ecare component a de culoare separat. De si
este posibil a comprimarea componentelor de ro su, verde, albastru intr-un mod ecient,
totu si comprimarea JPEG lucreaz a mai ecient c^ and informat iile de culoare sunt aplicate
sub form a de luminant  a (st alucire)  si crominant  a. Acest lucru este mult mai folositor,
deoarece ochiul este mai put in sensibil la schimb arile de culoare dec^ at la schimb arile de
luminozitate.
^Intr-o imagine de tip RGB, toate cele trei canale cont in informat ii despre luminozitate  si
ca urmare necesit a o codare cu aceea si rat a [5].
Figura 3.1: Conversia ^ n formatul YUV din RGB
^In cazul reprezent arii YUV, componenta Y corespunde intensit at ii luminoase, aceast a
component a mai este intalnit a  si sub numele de luminant  a. Componentele U  si V sunt cele
care denesc nuant a culorii, din acest motiv sunt denumite componente de crominant  a.
2
4Y
U
V3
5=2
40.299 0.587 0.114
-0.148 -0.289 0.437
0.615 -0.515 -0.1003
5
2
4R
G
B3
5:
Pentru a reface informat iile init iale vom avea nevoie de valorile tripletului RGB. Pentru
acest lucru vom folosi urm atoarele formule:
2
4R
G
B3
5=2
41 0 1.140
1 -0.395 -0.581
1 2.032 03
5
2
4Y
U
V3
5:
16

Avantajul reprezent arii YUV este acela c a separ a componenta de luminant a, pentru
care ochiul este foarte sensibil, la detalii de componentele de nuant a pentru care sensi-
bilitatea este mai redus a. Acest lucru face posibil a reducerea informat iei asociate unei
imagini prin utilizarea unei rezolut ii mai reduse pentru componentele de crominant a.
17

3.2 Sub-e santionare
18

3.3 Descompunerea imaginii ^ n blocuri
Aceast a metod a este inspirat a din procedura de copresie JPEG  si face parte din cate-
goria celor cu pierderi de informat ie. Procedura de compresie este dat a pentru codicarea
unei imagini monocrome de dimensiune 8×8 pixeli. Dac a dimensiunea imaginii nu este
multiplu de 8, atunci codorul copiaz a ultima coloan a sau linie p^ an a c^ and lungimea nal a
este un multiplu de 8. Aceste linii sau coloane puse suplimentar sunt ^ ndep artate ^ n tim-
pul procesului de decodare[ ?,?].
Cele trei componente RGB sau YUV sunt descompuse ^ n blocuri de dimensiune 8×8.
Un bloc de 8×8 pixeli poate  considerat o matrice de 8×8 elemente, ecare element
ind un num ar^ ntreg, reprezentat pe un num ar oarecare de bit i  si care codic a intensitatea
componentei, corespunz atoare acelui bloc. ^In cazul ^ n care se utilizeaz a reprezentarea
RGB, valorile elementelor sunt ^ ntodeauna pozitive iar daca se utilizeaz a reprezentarea
YUV, elementele corespunz atoare blocurilor Y sunt pozitive iar celelalte dou a componente
pot lua  si valori negative. ^In general, pentru compresie, imaginile sunt convertite ^ n
reprezentarea YUV. Dac a analiz am formulele de calcul care descriu aceas a conversie, se
poate preziza domeniul de variat ie al celor trei componente pentru o reprezentare RGB
pe opt bit i.
Y = 0.30R+0.5G+0.11B
U = R-Y=0.70R-0.59G-0.11B
V = B-Y=-0.30R-0.59+0.89B
Componentele R,G  si B ind codicate pe opt bit i pot lua valori ^ n domeniul 0..255.
Componenta Y, la r andul ei va avea valori ^ ntre 0..255 deoarece 0.30+0.59+0.11=1. Com-
ponentele U  si V, pot varia ^ ntre 179:::179 respectiv ^ ntre 227:::227. Se observ a o neu-
niformitate ^ n aceste domenii de valori care poate ridica probleme ^ n esrimarea preciziei  si
cerint elor de reprezentare a informat iei pe parcursul procesului de compresie. Din acest
motiv se propune un alt set de relat ii pentru conversia din RGB ^ n YUV :
Y = 0.30R+0.59G+0.11B+128
U = 0.50R-0.42G-0.08B
V = -0.17R-0.33G+0.50B
^In cazul acestor relat ii seobt ine pentru toate cele trei componente Y, U  si V acela si
domeniu de variat ie , -128…128.
Prima operat ie ce se realizeaz a ^ n scopul compresiei este transformarea imaginii din
matricea bloc intr-o form a echivalent a. ^In acest scop se utilizeaz a transformata cosinus
discret a, care porne ste de la matricea imagine S, genereaz a o matrice transformat a T
dup a urm atoarea formul a de calcul [ ?,?]:
T(i;j) =1
4CiCj"7X
x=07X
y=0Sy;x
cos(2x+ 1)j
16cos(2y+ 1)i
16#
:
Trecerea invers a de la matricea transformat a la matricea init ial a se poate realiza prin
transformata invers a descris a de relat ia:
S(i;j) =1
4"7X
x=07X
y=0CyCxTy;x
cos(2x+ 1)x
16cos(2y+ 1)y
16#
:
19

^In ambele relat ii avem:Ci;Cj=1p
2, dac au=v= 0;
Ci;Cj= 1; ^ n rest:
Elemntele matricii transformate reprezint a ponderile cu care se ^ nsumeaz a un num ar
de 64 de marici " sablon" constante pentru a se obt ine matricea imagine. Aceste matrici
 sablon pot  imaginate ca ni ste imagini de tip "tabl a de  sah", elementului ( i;j) din T
corespunz^ andu-i o tabl a cu ilinii  sijcoloane. Se poate arma c a elementele matricii
transformate cu indici mici coresound detaliilor mai grosiere din imagine iar cele cu indici
mai mari delatiilor mai ne. Din acest motiv, dac a analiz am matricea T obt inute prin
transformarea diferitelor blocuri dintr-o imagine, vom observa c a ^ n colt ul din st^ anga-
sus al matricilor avem valori mari  si cu c^ at cobor^ am spre colt ul din dreapta-jos valorile
elementelor ^ ncep s a scad a mult, chiar spre zero. O precizare ^ n leg atur a cu transformata
cosinus discret a este accea c a pentru o matrice S cu elemente ^ n intervalul -128…128 se
pot obt ine ^ n matricea T valori cuprinse ^ ntre -1023…1023.
Transformarea imaginii este o operat ie care teoretic nu degradeaz a imaginea. Se ob-
serv a c a exist a o transformat a invers a exact a, singura posibilitate de degradare a imaginii
ind erorile de calcul. Pentru compresie, ^ nsa este necesar s a se piard a ceva informat ie.
Acest lucru se poate realiza printr-o reducere a precizei de reprezentare a elementelor
matricii transformate. O modalitate de reducee a preciziei este aceea de a ^ mpart i acel
num ar cu o anumit a valoare  si de a ret ine doar partea ^ ntreag a din rezultat. Refacerea
valorii init iale se realizeaz a foarte simplu ^ nmult ind num arul obt inut cu valoarea cu care
s-a realizat ^ mpart irea. Aceast a operat ie se nume ste cuantizare. Problema este cu c^ at
s a se ^ mpart a elementele matricii transformate astfel ^ ncat la refacerea imaginii efectul
acestei aproxim ari  sa e mai put in vizibil a.
Pentru a rezolva aceast a problem a, pornim de la observat ia c a detaliile ne au o
important  a redus a ^ n aprecierea calit at ii unei imagini, iar aceste detalii sunt caracterizate
de elementele din matricea transformat a situate c atre colt ul din dreapta-jos. Astfel se
poate deni o matrice de cuantizare care s a cont in a ^ n ecare pozit ie valoarea prin care
se va realiza ^ mpart irea elementului corespunz ator din matricea transformat a. Aceasta
matrice poate  aleas a astfel ^ ncat s a e simetric a  si elementele sale s a creasc a pe m asur ce
se coboar a din colt ul din st^ anga-sus c atre cel din dreapta-jos. Un exemplu de matrice
este dat ^ n continuare.
4 4 5 5 6 6 7 7
4 5 5 6 6 7 7 8
5 5 6 6 7 8 9 10
5 6 6 7 8 9 10 11
6 6 7 8 10 12 14 16
6 7 8 9 12 13 16 19
7 7 9 10 14 16 20 24
7 8 10 11 16 19 24 29
Prin operat ia de cuantizare se obt ine o matrice ^ n care descre sterea valorii elementelor
este mult mai pronunt at a, multe elemente devenind zero. Un exemplu de matrice obt inut a
prin cuantizare este cel prezentat mai jos:
20

236 -105 -24 -11 0 0 0 0
-13 -17 0 0 0 0 0 0
11 0 0 0 0 0 0 0
0 0 0 -3 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
21

Capitol 4
Standardul JPEG
4.1 Codarea secvent ial a DCT cu pierderi
22

4.2 Codarea expandat a DCT cu pierderi
23

4.3 Codarea far a pierderi
4.3.1 Codarea entropic a Human
^In general, comprimarea datelor const a ^ n a lua un
ux de simboluri si a le transforma
^ n coduri. Dac a compresia este ecient a,
uxul rezultat de coduri este mai mic dec^ at
simbolurile int iale. Decizia de a emite un anumit cod pentru un anumit simbol sau un
set de simboluri se bazeaz a pe un model. Modelul este pur  si simplu o colect ie de date
 si reguli folosite pentru a procesa simbolurile de intrare  si de a determina codul de ie sire.
Programul folose ste modelul pentru a deni cu exactitate probabilitat ile ec arui simbol,
pentru a produce un cod corespunz ator acestor probabilit at i.
Modelarea  si codicarea sunt dou a lucruri disticte. Oamenii folosesc frecvent termenul de
codicare pentru a se referi la ^ ntregul proces de compresie a datelor ^ n loc de o singur a
component a a acestui proces.
^In anul 1952, D.A. Human a publicat o metod a ecient a a schemelor de codare.
Aceast a metod a reprezint a un algoritm de compresie a datelor f ar a pierderi [5]. Ideea
acestui algoritm este de a atribui coduri de lungime variabil a pentru caracterele de in-
trare, lungimea codurilor atribuite se bazeaz a pe frecvent ele de caractere corespunz atoare.
Caracterul cel mai frecvent devine cel mai mic cod  si caracterul cel mai put in frecvent
devine cel mai mare cod. Princiupiul este de a utiliza un num ar mai mic de bit i pentru a
codica datele in coduri binare ^ n funct ie de frecvent a aparit iei lor.
^In cazul codic arii Human, ie sirea real a a codicatorului este determinat a de un set de
probabilit at i. La utilizarea acestui tip de codare, simbolul care are o probabilitate foarte
mare de aparit ii, genereaz a un cod cu un num ar mic de bit i, iar un simbol cu o probabil-
itate mic a genereaz a un cod cu un num ar mare de bit i.
Algoritmul Human constituie un algoritm optimal, ^ n sensul c a nici un alt algoritm nu
asigur a o mai mic a lungime medie a cuvintelor.
^In cazul alfabetului statitic de ordin 0, arborele Human este construit ^ n mod identic,
at^ at ^ n faza de compresie, c^ at  si ^ n cea de decompresie, pe baza setului de contoare
asociate simbolurile din alfabet. Alfabetul  si contoarele trebuie transmise al aturi de setul
comprimat de date, pentru ca decriptarea s a e exact a.
O prim a idee de a construi arborele binar ^ n manier a adaptiv a este urm a toarea:
odat a cu ecare simbol citit/decriptat se construie ste complet arborele. Aceast a manier a
de construct ie este, ^ ns a, extrem de ecient a, deoarece efortul de construct ie de la pasul
anterior se pierde integral.
Pa sii algoritmului Human static sunt urm atorii:
Ordonarea mesajelor sursei ^ n ordine descresc atoare a probabilit at ilor.
Formarea din ultimele dou a mesaje a unui mesaj restr^ ans r1=SN1S
SNav^ and
p(r1) =p(SN1) +p(SN).
Includerea mesajelor r1^ n mult imea celorlalte mesaje, ^ n ordine descresc atoare a
probabilit at ilor , alc atuind  sirul ordonat R1.
Repetarea algoritmului de rest^ angere p^ ana c^ and ultimul  sir ordonat Rkcont ine doar
dou a mesaje.
Cuvintele de cod corespunz atoare ec arui mesaj se obt in ^ n felul urm ator:
{simboluluirk1i se aloc a '0', iar lui rk'1'.
24

{la ecare diviziune ^ n dou a se aloc a simbolurile '0'  si '1' p^ an a c^ and se ajunge
la mult imi formate dintr-un singur mesaj.
Exemplu:
S a se codeze prin algoritmul Human binar sursa caracterizat a de urm atoarea distribut ie:
S:s1s2s3s4s5s6
0:15 0:05 0:3 0:15 0:25 0:10
25

4.3.2 Codarea RLC "Run Length Coding"
26

4.4 Codarea ierarhic a
27

Capitol 5
Comparat ia dintre formatul JPEG  si formatul PNG
28

Capitol 6
Concluzii
29

Index
compresie, 4
imagine, 8
30

Bibliograe
[1] Castleman K. R., Digital Image Processing , Prentice Hall, USA, 1996.
[2] Chris Solomon,Toby Breckon, Fundamentals digital image processing ,Editura Wiley-
Blackwell, 2011.
[3] Guy E. Blelloch, Introduction to Data Compression , January 31, 2013, pag 44-50.
[4] Jain, A.K., Fundamentals of Digital Image Processing ,Prentice Hall, Englewood Clis
NJ, 1989.
[5] R. Gonzalez and R. Woods, Digital image processing , Addison-Wesley, Reading (MA),
1992.
[6] Thomas Sikora, MPEG Digital Video-Coding Standards ,IEEE Signal Processing Mag-
azine,1997, pag.82-100.
[7] Wahl, F. M., Digital Image Signal Processing, Artech House , Boston, 1987.
[8] Watson, Andrew B., Mathematica Journal , 4(1), 1994, pag. 81-88.
[9] Wilhelm BuJain, A. Krger, Mark J. Burge, Principles of Digital Image Processing ,
Springer-Verlag London Limited, 2009, pag.16-20.
[10] Yun Q.Shi, Huifang Sun, Image and Video Compression for Multimedia Engineering ,
2000, pag. 157-167.
[11] Zamperoni, P., Image Enhancement, Advances in Imaging and Electron Physics , vol.
92, pp. 1-77, Academic Press, 1995.
[12] Zoran S. Bojkovic, Corneliu I. Toma, Vasile Gui, Radu Vasiu, Advanced Topics in
Digital Image Compression , Editura Politehnica, 1997.
31