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

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-CristinaBucure 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-CristinaBucure sti
2017

Cuprins
Introducere 4
1 Generalit at i 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.2 Operat ii morfologice asupra imaginilor . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Dilatarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Eroziunea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.3 Deschidere  si ^ nchidere . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Reprezentarea numeric a a imaginii . . . . . . . . . . . . . . . . . . . . . . 13
2 Fi siere JPEG 16
2.1 Stocarea imaginilor ^ n memorie . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Stocarea imaginilor ^ n  siere . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Metode de compresie 19
3.1 Transformata cromatic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Descompunerea imaginii ^ n blocuri . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Compresia imaginilor f ara pierderi . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1 Codarea Human . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.2 Codarea RLC ("run length coding") . . . . . . . . . . . . . . . . . 25
3.4 Compresia cu pierderi a imaginilor statice . . . . . . . . . . . . . . . . . . 25
3.4.1 Codarea predictiv a . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Codarea pe blocuri de pixeli . . . . . . . . . . . . . . . . . . . . . . 25
4 Standardul de compresie JPEG 27
4.1 Codarea bazat a pe transformata cosinus discret a . . . . . . . . . . . . . . . 27
4.2 Codorul si decodorul JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Codarea ierarhic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Comparat ia dintre formatul JPEG  si formatul PNG 29
6 Concluzii 30
31
Index de abrevieri 32
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 fotogra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.
5

Capitol 1
Generalit at i
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
punctului ^ 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 )
…………
f(N;1)f(N;2)


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


f(n;M )]:
vectorul linie ndinf.
8

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.2 Operat ii morfologice asupra imaginilor
1.2.1 Dilatarea
Dilatarea se face prin suprapunerea unui element structural, B, peste imaginea A,
 si mulatrea lui peste imagine, ^ ntr-o manier a similar a convolut iei.2Diferent a dintre
convolut ie  si dilatarea folosind elementul structural este felul ^ n care se aplic a operat ia,
convolut ia ind ca un operator liniar iar dilatarea ind denit a cel mai bine prin urm atoarea
secvent  a de pa si:
Dac a orginea elementului structural se suprapune cu un pixel "fundal" din imagine,
nu se efectueaz a nici o modicare  si se trece la urm atorul pixel.[ ?,?]
Dac a originea elementului structural coincide cu un pixel "obiect" din imagine,
atunci tot i pixelii acoperit i de elementul structural devin pixeli "obiect".
Notat ie:
AB.
Elementul structural poate avea orice form a. C^ ateva forme des ^ ntalnite sunt:
2Convolut ia este o modalitate de a combina dou a semnale pentru a forma un al treilea. Ea este singura
tehnic a important a ^ n procesarea digital a a semnalelor. Folosind strategia descompunerii ^ n impulsuri,
sistemele sunt descrise de un semnal numit r aspuns la impuls. Convolut ia este important a deoarece leag a
cele trei semnale e interes: semnalul de intrare, semnalul de ie sire  si raspunsul de impuls.
9

Figura 1.2: Forme tipice pentru elementele structurale (B)
^In gura 1.3 este prezentat un exemplu de dilatare. A se observa c a ^ n cazul operat iei
de dilatare, tot i pixelii "obiect" vor  p astrat i, marginile obiectelor vor  extinse iar micile
goluri vor  umplute.
Figura 1.3: Ilustrarea procesului de dilatare
^In imaginea 1.4 este prezentat un exemplu de dilatare, unde gura a reprezint a imag-
inea origininal a A  si ^ n gura b avem imaginea rezultat a ^ n urma operat iei AB.
10

Figura 1.4: Exemplu de dilatare (obiect = negru / fundal = alb)
1.2.2 Eroziunea
Operat ia de eroziune este similar a cu cea de dilatare, dar anumit i pixeli "obiect" vor
 transformat i ^ n pixeli "fundal", invers fat a de dilatare. Ca mai sus elementul structural
este deplasat peste imagine, dar se va folosi urm atoarea secvent a de pa si:
Dac a originea elementului structural se suprapune peste un pixel "fundal" din imag-
ine atunci nu se efectueaz a nicio modicare  si se trece la urm atorul pixel.
Dac a originea elemtului structural se suprapune peste un pixel "obiect" din imagine
 si exist acel put in un pixel "obiect" al elementului structural care se suprapune peste
un pixel "fundal" din imagine, atunci pixelul curent din imagine va  transformat
^ n "fundal".[5]
Notat ie:
A B
^In gura 1.5 au r amas doar pixelii "obiect" care coincid cu originea elemtului structural
dac a acesta s-a suprapus ^ n ^ ntregime peste pixelii "obiect" ai unui obiect existent. Pentru
c a elemtul structural are trei pixeli l at ime, partea din dreapta a obiectului a fost complet
erodat a, dar partea din st^ anga  si-a ment inut c^ at iva dintre pixeli, pentru c a init ial avea
trei pixeli l at ime.
^In imaginea 1.5 este prezentat un exemplu de dilatare, unde gura a reprezint a imag-
inea origininal a A  si ^ n gura b avem imaginea rezultat a ^ n urma operat iei A B.
11

Figura 1.5: Ilustrarea procesului de eroxiune
Figura 1.6: Exemplu de eroziune (obiect = negru / fundal = alb)
1.2.3 Deschidere  si ^ nchidere
Cele dou a operat ii de baz a, dilatarea  si eroziunea pot  combinate ^ n secvent e de
operat ii complexe. ele mai utile operat ii de ltrare morfologic a sunt deschiderea  si
^ nchiderea [1]. Deschiderea const a ^ ntr-o eroziune urmat a de o dilatare  si poate  folosit a
pentru eliminarea pixelilor din regiunile care sunt prea mici pentru a cont ine elementul
structural. ^In acest caz, elementul structural este adesea numit sond a, pentru ca acesta
caut a obiecte prea mici  si le ltreaz a. ^In gura 1.7, avem un exemplu pentru deschidere.
Notat ie:
AB= (A B)B
^Inchiderea const a ^ ntr-o dilatare urmat a de o eroziune,  si poate  folosit a pentru
umplerea de goluri  si mici discontinuit at i. ^In gura 1.8 se poate vedea ca operat ia de
^ nchidere are ca efect umplerea golurilor  si a discontinuit at ilor. Compar^ and imaginile
din partea st^ anga  si partea dreapt a a gurii 1.9, putem observa c a ordinea operat iilor de
dilatare  si eroziune este important a. ^Inchiderea  si deschiderea au rezultate diferite, chiar
dac a ambele constau dintr-o operat ie de eroziune  si una de dilatare.
Notat ie:
AB= (AB) B
12

Figura 1.7: Ilustrarea operat iei de deschidere
Figura 1.8: Ilustrarea operat iei de ^ nchidere
1.3 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].
Pentru a reprezenta o astfel de imagine trebuie s a 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-
13

Figura 1.9: (a)
Figura 1.10: (b)
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.
^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:
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
14

Figura 1.11: Proul de culoare
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
^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. Componentele U  si V sunt cele care denesc nuant a culorii, din acest motiv
sunt denumite componente de crominan ta. Se observ a c a se calculeaz a ca diferen ta dintre
componenta ro sie respectiv albastr a  si cea de luminant  a.
15

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.
16

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
Fotograa digital a utilizeaz a numeroase formate de  siere, ecare dintre ele adaptate
unei anumite utiliz ari: captur a, prelucrare, arhivare. Cele mai utilizate tipuri de  siere
de imagine sunt: JPEG, TIFF, GIF, PNG, DNG, etc.
Spre deosebire de imaginile vectoriale, imaginile fotograce fac parte din categoria
celor matriceale. Acest gen de imagine este alc atuit din pixeli. Pixelii pot  asemuit i cu
pl acile de faiant a de pe un perete, ei sunt dispu si ^ n r^ anduri suprapuse pentru a acoperi
formatul imaginii. La a sarea pe ecran sau la imprimare, mai mut i pixeli sunt a sat i pe
unitatea de lungime. Pentru a avea impresia de detalii bine denite.
Pentru imaginile alb-negru, deoarece ochiul uman nu poate distinge mai mult de 200
de nuant e de gri, s-a considerat c a 256 este cel mai apropiat num ar care satisface aceast a
situat ie, de aceea, imaginile alb-negru sunt codicate cu 8 bit i pentru ecare pixel.
JPEG este un algoritm de compresie, propus de Joint Photograe Expert Group  si care
a fost destinat comprim arii imaginilor alb-negru sau color, luate din realitate. Algoritmul
de compresie se bazeaz a pe sensibilitatea crescut a a ociului uman la variat iile mici de
luminant  a  si sensibilitatea mai redus a la variat iile mici de culoare [6]. Algoritmul acord a
mai mult a atent ie pentru modic arile ne de luminant  a  si o pondere mai mic a pentru
culoare, ^ ntruc^ at imaginea comprimat a este destinat a observ arii de c atre oameni.
Compresia JPEF se face cu pierderi de informat ie, adic a o parte din informat iile
det inute de imaginea init ial a sunt ^ nl aturate denitiv. Dac a avem nevoie de o metod a
f ar a pierdere de informat ie, putem alege metoda TIFF, dar ^ n aceast a situat ie,  sierul va
 mult mai mare.
O proprietate foarte util a a algoritmului jpeg este capacitatea de a avea un grad
variabil de comprimare, ales de utilizator. Aceasta ^ nseamn a c a dac a dorim obt inerea
unui  sier de imagine mai mic, se poate alege o rat a mare de comprimare, iar pentru a
ment ine calitatea la o cot a ridicat a, se alege un grad redus de comprimare. La prima
comprimare a imaginilor, chiar  si pentru un grad mediu, pierderea ^ n calitate este minor a.
Toate aparatele fotograce digitale, pentru a realiza economie de spat iu pe cartela de
memorie, prezint a posibiliatea de a comprima imaginea desc arcat a de pe CCD ^ n imagine
comprimat a JPEG^ n diverse rapoarte, f ar a o degradare semnicativ a. Dac a  sierul JPEG
este deschis, prelucrat, salvat, apoi din nou deschis, prelucrat si salvat, de mai multe ori,
se vor observa pierderile de calitate.
Formatul GIF este mai vechi dec^ at JPEG, este superior ^ n privint a calit at ii imaginii,
a ratei de comprimare sau a ambelor, dar are un pachet cu o palet a redus a de culori,
deoarece, prin convent ie, GIF are maximum 256 de culori. Imaginile optime pentru
comprimare prin metoda GIF sunt cele cu linii  si cu suprafet e uniform colorate, cum
sunt cele desenate cu programe de grac a. Cu c^ at imaginea cont ine mai multe nuant e,
cu atat JPEG se descurc a mai bine, GIF comprim a bine imaginile netede, cum ar
chenarele fotograilor sau conturul literelor aplicare peste o imagine, pe care JPEG le
red a mai difuz, datorit a rotunjirilor inerente ^ n calculele matematice pe care le efectueaz a
algoritmul de compresie.
^In incercarea de a corecta decient ele  sierelor de tip GIF, a ap arut formatul PNG  si
care prezint a codicare pe 8 bit i sau pe 24 de bit i inclusiv gestionarea transparent ei pe 256
nivele. Formatul PNG este recunocut de practic toate programele moderne de prelucrare
17

 si navigare pe internet. Formatul PNG-24 suport a  si imagini cu tonuri continue, dar
dimensiunile  sierelor sunt mai mari ca cele JPEG.
Tagged Image File Format (TIFF) este un format de  siere de imagine, creat de
compania Aldus  si a devenit rapid suportat de toate programele de prelucrare  si vizionare
a imaginilor digitale. Calitatea imaginii digitale^ n format TIFF esre foarte bun a. Fi sierele
TIFF pot suferi prelucr ari repetate, f ar a afecta calitatea, deoarece informat ia este stocat a
f ar a comprimare  si f ar a pierderi. Dezavantajul major ar formatului este dimensiunea
foarte mare [3].
Formatul TIFF este recomandat ca  sier de salvare ^ ntre etapele de prelucrare ale
imaginilor pe calculator, deoarece permite salv ari repetate, f ar a degradarea calit at ii imag-
inii. Poate  folosit pentru stocarea sau arhivarea imaginilor, de si dimensiunile mari ale
 sierelor ^ l fac cam nepractic.
Fi sierele de imagine RAW sunt  siere brute, ce cont in datele primare, a sa cum sunt
ele furnizate de captator, f ar a nici o modicare. ^In header-ul  sierului RAW exist a ^ ns a
informat ii referitoare la toate set arile camerei ^ n momentul fotograerii  si care pot
utilizare ca punct de plecare pentru prelucrare. Dimensiunile sunt mari, dar ceva mai
mici dec^ at  sierul TIFF, iar calitatea imaginii este maxim a.
Formatul RAW are dou a dezavantaje majore: implic a obigatoriu o prelucrare, pentru
a putea  imprimat  si ecare produc ator de camer a foto digitale are un format specic
de  sier  si care de regul a nu poate  prelucrat cu programul unei rme concurente.
Adobe Camera RAW ^ ncearc a s a t in a pasul cu ultimele formate de  siere RAW
ap arute, dar un nou tip de  sier implic a o actualizare a programului.
Formatul de  sier DNG (Digital NeGative) a fost creat recent de Adobe ^ n intent ia
de a pune la dispozit ie fotogralor un format universal de  sier RAW. Formatul DNG a
fost adoptat at^ at de unii produc atori de camere foto digitale, c^ at  si de unii produc atori
de software. Fi sierele de tip DNG prezint a acelea si avantaje  si dezavantaje ca cele de tip
RAW. Compania Adobe ne asigur a c a va furniza permanent suport pentru acest tip de
 siere.
18

Capitol 3
Metode de compresie
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.
19

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.
20

3.2 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, se obt 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#
:
(3.1)
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#
:
(3.2)
21

^In ambele relat ii avem:Ci;Cj=1p
2;dac a u=v=0,
Ci;Cj= 1; ^ n rest:
Elementele 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 corespund 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:
22

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
3.3 Compresia imaginilor f ara pierderi
Compresia f ar a pierderi face referire la metode de compresie pentru care setul original
de date necomprimate poate  ref acut exact din  sirul comprimat. Necesitatea folosirii
compresiei f ar a pierderi const a ^ n accea c a multe aplicat ii nu permit introducerea erorilor
^ n semnalul original. Exist a o serie de algoritmi de compresie f ar a pierderi care se folosesc
cu succes ^ n domeniul imagisticii. Pentru ^ nceput prezent am care sunt aspectele generale
legate de compresia f ar a pierderi.
S a consider am o surs a Sde simboluri aleatoare s1;s2;:::;s n.Spoate  o imagine
digital a, iar sireprezint a una din cele Nvalori posibile pe care le poate lua un pixel din
imagine [6]. Dac a pireprezint a probabilitatea de aparit ie a simbolului siatunci putem
deni informat ia ca ind:
I(si) = log1
pi=logpi
Dac a baza logaritmului ar  2, atunci informat ia se m asoar a ^ n bit i, iar dac a baza este
10, atunci informat ia se m asoar a ^ n digit i, dar ^ n general m asur am informat ia ^ n bit i pe
simbol. Conform teoremei lui Shannon, entropia unei surse Seste denit a ca ind:
H(S) =X
ipilog1
pi
Conform teoriei informat ionale, dac a simbolurile sisunt distincte, atunci num arul
mediu de bit i necesari pentru a coda simbolurule respective este dat de entropia sursei [ ?,
?].^In practic a, entropia unei surse nu se cunoa ste, ea se poate estima cel mult depinz^ and
de modelul de probabilitate ales.
Avem urm atoarea secvent a de simboluri: 4 5 8 6 7 8 9 4 8,  si presupunem c a avem o
surs a care genereaz a 6 simboluri: s1=4,s2=5,s3=4,s4=7,s5=8,s6=9.^In cazul ^ n
care folosim un model de probabilitate ^ n care toate simbolurile au acea si probabilitate
de aparit ie pi=1
6, atunci entropia sursei este:
H(S) = 6
1
6log26 = 2:585
.
Dac a folosim acest model de probabilitate, nu vom putea g asi o schem a de codare care
s a codeze simbolurile cu mai put in de 2.585 bit i pe e santion. ^In cazul ^ n care se alege un
model de probabilitate ^ n care pi=3
10,p2=3
10 sip3=p4=p5=p6=1
10, entropia
obt inut a ^ n acest caz este 2.371.
Schema bloc a unui codor f ar a pierderi este prezentat a ^ n Figura 3.2. Folosind un set
de simboluri de intrare se genereaz a un model de probabilitate care va  folosit de blocul
de alocare a cuvintelor de cod. O astfel de combinare ^ ntre blocul de alocare a cuvintelor
23

de cod  si modelul probabilit at ii poart a generic numele de codare entropic a. Ideea de baz a
^ n codarea entropic a este folosirea cuvintelor de cod c^ at mai scurte pentru simbolurile cu
probabilitate mare  si respectiv folosirea cuvintelor de cod mai lungi pentru simbolurile
cu probabilitatea de aparit ie mai mic. Modelul de probabilitate poate  obt inut e din
analiza simbolurilor de intrare c^ at  si prin folosirea unui set de date predenit.
Figura 3.2: Schema bloc a codorului f ar a pierdei
3.3.1 Codarea 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,
uxulrezultat de coduri este mai mic dec^ at sim-
bolurile 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 ^ n 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
24

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'.
{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.
^In cazul imaginilor metoda are ca rezultat un cod de lungime variabil a corespunz ator
ec arui bloc, blocurile cu probabilit at e mare ind reprezentat de coduri de lungime mic a
sau mare. Pentru o m arime dat a a blocului, codarea Human este cea mai ecient a. Dac a
valorilor cuantizat i nu sunt uniform distribuite, entropia lor va  mai mic a B bit i/pixeli
 si este posibil a folosirea unui cod care necesit a mai put in de B bit i/pixeli. ^In urma
implement arii algoritmului se obt ine un tabel de codare Human pentru un set dat de
probabilit at i. Codarea  si decodarea se face foarte simplu, cunosca^ and valorile din tabel.
Dat a ind lungimea variabil a a cuvintelor de cod, este necesar a utilizarea unui registru,
^ n cazul foarte uzual ^ n care informat ia este transmis a printr-un canal cu rat a constant a
de transmisie. M arimea tabelului de cod este de L= 2MB, undeMreprezin a numarul de
bit i din bloc, iar cel mai lung cuv^ ant de cod poate avea cel mult Lpixeli.
O versiune mai ecient a a codului Human este codul Human trunchiat: Ll< L
ales corespunz ator, primele Llsimboluri sunt codate Human, iar simbolurile r amase se
codeaz a cu un cod prex, urmat de un cod de lungime x a. O alt a variant a const a ^ n
folosirea codului Human modicat, la care num arul ^ ntreg ise reprezint a ca:
i=qL1+j;0qInt(L1)
L1
;0jLl:
3.3.2 Codarea RLC ("run length coding")
3.4 Compresia cu pierderi a imaginilor statice
3.4.1 Codarea predictiv a
3.4.2 Codarea pe blocuri de pixeli
Multe dintre metodele de compresie a imaginilor au o implementare pentru a opera
pe blocurile de pixeli. Aceast a categorie de algoritmi se ^ mparte la r^ andul ei ^ n:
25

algoritmi de codare spat ial a pe blocuri
algoritmi de codare prin transform ari
^In cazul algoritmului de codare spat ial a pe blocuri, pixelii sunt grupat i ^ n blocuri, iar
blocurile sunt apoi comprimate prin metode clasice de compresie spat ial a. Un exemplu
de compresie spat ial a este cuantizarea vectorial a. Coantizare vectorial a este o modalitate
de a reduce rezolut ia cu care este reprezentat un set de date. Esent a metodei const a ^ n
reprezentarea unor grupuri de valori din setul original de date ca valori singulare ^ n noul
set, reduc^ andu-se astfel cantitatea tatal a de informat ie. Cuantizarea este o tehnic a de
compresie cu pierdere de informat ie.
Din punct de vedere al rezultatelor compresiei, ace sti algoritmi conduc la obt inerea
unui raport de compresie mai ridicat dec^ at ^ n cazul algoritmului de compresie spat ial a,
dac a se ia ^ n seam a un acela si grad al distorsiunii.
Spre deosebire de prima categorie, algoritmi de codare prin transf arm ari, ^ mpart imag-
inea ^ n blocuri de pixeli, dup a care ecare din aceste blocuri este transformat ^ ntr-un alt
domeniu, cum ar  de exemplu domeniul frecvent a.
Se consider a dou a matrici de transformare de dimensiune NxN:
Tc=ftc(u;i)g;u;i = 0;1;:::;N1
Tr=ftr(v;j)g;v;j = 0;1;:::;N1
pe care le numim funct ii de baz a. Dac a not am cu X, imaginea bidimensional a, putem
exprima procesul liniar de transformare ca ind:
Y=TcXTrt
undeTrteste matricea transpus a a lui Tr. Dac a transformata Teste simetric a atunci
Tc=Tr=T, iarY=TXTt. Ideea transform arii imaginii init iale X^ nYeste de a obt ine
o reprezentare compact a a datelor de imagine. Metodele de compresie prin transform ari
exploateaz a aceast a reprezentare compact a a informat iei  si elimin a acele date din Ycare
nu sunt importante [3]. Unele dintre cele mai cunoscute funct ii de baz a utilizate ^ n
compresia imaginilor pentru transform ari sunt:
transformata Fourier Discret a
transformata Cosinus Discret a
transformata Cosinus Discret a
transformata Hadamard
transformata Karhunen-Loeve
Figura 3.3: Codare prin transformare bidimensional a
Un algoritm practic de codare prin transform ari aplicat pentru imagini este prezentat ^ n
Figura 3.3, iar etapele succesive de implementare sunt urm atoarele.
26

Capitol 4
Standardul de compresie JPEG
4.1 Codarea bazat a pe transformata cosinus discret a
27

4.2 Codorul si decodorul JPEG
4.3 Codarea ierarhic a
28

Capitol 5
Comparat ia dintre formatul JPEG  si formatul PNG
29

Capitol 6
Concluzii
30

Index
a comprima, 17
bit i, 21
bloc, 5, 21
codare entropic a, 24
compresia f ar a pierderi, 23
compresie, 4
crominant a , 19
cuantizare, 22
culoare, 17
digit i, 23
dilatare, 10, 11
e santion, 23
element structural, 11
entropie, 23
eroziune, 12

ux, 24
imagine, 22
imagine , 13
luminant  a, 5, 15
pixel, 16, 17
ponderile, 22
transformare, 22
31

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 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] J. Ziv and A. Lempel, A Universal Algorithm For Sequential Data Compression ,
IEEE Transactions on Informations Theeory Vol.23, nr.3, Mai 1977, p.337-343.
[13] J. Ziv and A. Lempel, Compression of Individual Sequences Via Variable-Rate Cod-
ing, IEEE Transactions on Informations Theeory vol.24, nr.5, Sept. 1978, p.530-536.
[14] Zoran S. Bojkovic, Corneliu I. Toma, Vasile Gui, Radu Vasiu, Advanced Topics in
Digital Image Compression , Editura Politehnica, 1997.
32