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

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 5
1 Generalit at i 7
1.1 Reprezentarea  si caracterizarea imaginilor . . . . . . . . . . . . . . . . . . 7
1.1.1 Repartizarea imaginilor . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Caracterizarea matematic a a imaginilor digitale . . . . . . . . . . . 9
1.2 Operat ii morfologice asupra imaginilor . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Dilatarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Eroziunea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Deschidere  si ^ nchidere . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Reprezentarea numeric a a imaginii . . . . . . . . . . . . . . . . . . . . . . 15
2 Fi siere JPEG 18
2.1 Stocarea imaginilor ^ n memorie . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Stocarea imaginilor ^ n  siere . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Metode de compresie 22
3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Transformata cromatic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Compresia imaginilor f ara pierderi . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.1 Codarea Human . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Codarea RLC ("run length coding") . . . . . . . . . . . . . . . . . 27
3.4 Compresia cu pierderi a imaginilor statice . . . . . . . . . . . . . . . . . . 28
3.4.1 Codarea predictiv a . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Codarea pe blocuri de pixeli . . . . . . . . . . . . . . . . . . . . . . 29
3.5 Sistem de codare bazat pe transformata Cosinus Discret a . . . . . . . . . . 32
3.6 Compresia imaginilor binare . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6.1 Codarea RLC  si Human aplicata a imaginilor binare . . . . . . . . 36
3.6.2 Cuantizarea diferent ial a cu predict ie . . . . . . . . . . . . . . . . . 37
3.6.3 Codarea prin adresare relativ a . . . . . . . . . . . . . . . . . . . . . 38
4 Standardul de compresie JPEG 39
4.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Codarea bazat a pe transformata cosinus discret a . . . . . . . . . . . . . . . 40
4.3 Codorul si decodorul JPEG . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4 Prelucrarea imaginilor color . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.5 Algoritmul de codare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6 Modul de codare progresiv . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.7 Codarea ierarhic a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Comparat ia dintre formatul JPEG  si formatul PNG 47
3

6 Concluzii 48
49
Index de abrevieri 50
Bibliograe 50

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

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

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
[6].
^In general, reprezentarea imaginilor este realizat a ^ n domeniul continuu. Pentru o imag-
ine 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 culorilor 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 [2]. O imagine digital a monocrom a este o funct ie bidimensional a care specic a
7

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.
1RGB ro su, verde, albastru (Red, Green, Blue ^ n englez a)
8

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.
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)
9

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.
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[2].
Matricea liniarizat a pe linii este:
fl=NX
n=1wT
n
f
Mn:
Matricea inversa este:
f=NX
n=1wn
fl
MN
n:
10

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:
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.
^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.
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.
11

Figura 1.3: Ilustrarea procesului de dilatare
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".[6]
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.
12

Figura 1.5: Ilustrarea procesului de eroxiune
Figura 1.6: Exemplu de eroziune (obiect = negru / fundal = alb)
^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.
13

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 [2]. 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. ^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
Figura 1.7: Ilustrarea operat iei de deschidere
Figura 1.8: Ilustrarea operat iei de ^ nchidere
14

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.9(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.10(b) [2].
Figura 1.9: (a)
Figura 1.10: (b)
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 [6]. 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[2]. 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.
15

^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.10(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.11: 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
16

^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.
17

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) [4] 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 [6].
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.
18

Funct iile returneaz a matrici iar secvent a C, anterioar a, este echivalent a cu :
imagine=zeros(nr_linii,nr_coloane);
19

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 [7]. 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 JPEG 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
 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
20

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 [4].
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.
21

Capitol 3
Metode de compresie
3.1 Introducere
Metodele uzual folosite pentru reducerea cantit at ii de informat ie prezente ^ n imaginile
digitale se ^ maprt ^ n dou a categorii:
codarea predictiv a;
codarea prin transform ari;
Codarea predictiv a exploateaz a redundant a existent a ^ n imagine, ^ n schimb codarea prin
transform ari realizeaz a modicarea structurii de date a imaginii ^ n alt a matrice. O cat-
egorie aparte a algoritmilor de compresie sunt reprezentat i prin metodele zice de com-
presie: sube santionarea, cuantizarea brut a, repetarea cadelor. Aceste metode se bazeaz a
pe reducerea frecvent ei de e santionare, a num arului de nivele de cuantizare, num arului de
nivele de cuantizare  si a frecvent ei cadrelor, p^ an a la limitele distorion arii prin conturare,
a imaginii [ ?,?]. Distorsiunile introduse sunt, pentru acela si raport de compresie, mai
mari dec^ at cele introduse de metodele performante.
Compresia de date se bazeaz a pe diferit i algoritmi de calcul care pot  implementat i
at^ at software c^ at  si hardware. Exist a dou a tipuri de compresie:
cu pierderi;
f ar a pierderi
Tehnica de compresie f ar a pierderi permite refacerea perfect a a imaginii originale, ^ n
schimb metoda de compresie cu pierderi reface imaginea asem an ator cu originalul dar nu
identic. Cu ajutorul acestor metode se pot obt ine rate de compresie mult mai mari  si
din acest a cauz a, sunt folosite cu prec adere pentru compresia imaginilor ^ n detrimentul
tehnicilor f ar a pierderi.
22

3.2 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 [6]. ^In cazul reprezent arii YUV , componenta
Figura 3.1: Conversia ^ n formatul YUV din RGB
Ycorespunde 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.
Unul dintre sistemele de coordonate cel mai utilizat ^ n prelucrarea  si compresia imaginilor
este sistemul YCbCr. La fel ca  si ^ n cazul YUV componenta Yreprezint a luminant a ^ n
timp ce componentele CbrespectivCrreprezint a semnalele de crominant a. Pornind de la
componentele primare de culoare RGB putem scrie urm atoarele relat ii:
Y= 0.299R+0.587G+0.114B
Cb=0.564(BY)
Cr=0.713(RY)
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.
23

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 [7]. 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
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.
24

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 [6]. 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
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.
25

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:
26

3.3.2 Codarea RLC ("run length coding")
27

3.4 Compresia cu pierderi a imaginilor statice
3.4.1 Codarea predictiv a
O alt a metod de realizare a compresiei este acea a abord arii predictive. Ea se bazeaz a
pe faptul c a datele ce urmeaz a a  comprimate nu difer a de la o valoare la alta, deci pot
 predict ionate destul de bine din calorile anterioare.
E santioanele care sunt luate ^ n considerare ^ n cazul cod arii predictive pot  din dome-
niul spat ial e din domeniul frecvent  a. Unul dintre cei mai simpli algoritmi de codare
predictiv a este codarea DPCM1. DPCM se realizeaz a pe semnalele cu corelat ie ^ ntre
e santioane succesive conduce la rapoarte de compresie bune. Imaginile sunt exemple
de semnal care au corelat ia ment ionat a mai sus. ^In imagini, aceasta ^ nseamn a c a exist a
o corelat ie ^ ntre pixelii vecini.
bXi1;j1eXi1;j
bXi;j1bXi;j
^In tabelul de mai sus este prezentat un exemplu de predictor. bXi;jeste valoarea estimat a
a luiXi;j si va avea formula:
bXi;j=Pi;j+qi;j
Dac a imaginea este puternic corelat a atunci Pi;jva avea o valuare foarte apropiat a de cea
a luiXi;j, rezult^ and o eroare mai mic a, ei;j. Practic informat ia transmis a pe canal este
eroarea de prect ie cuantizat a [4]. ^In general, pentru cuantizare se folose ste un cuantizator
uniform. Practic o serie de valori de intrare corespunz^ and unei singure valori de ie sire.
DE aici apare practic efectul compresiei cu pierderi, proces care este ireversibil. ^In cazul
^ n care se folose ste un cuantizator optimal putem scrie:
qi;j=rotunjireei;j


unde
reprezint a pasul de cuantizare. Pentru o imagine pe opt bit i ia valori ^ ntre 0  si
255.
Deoarece variat ia erorii de predict ie ei;jeste mai mic a dec^ at variant a e santioanelor
de intrareXi;j, procesul de cuantizare a eroorii nu va introduce distorsiuni suplimentare.
O variant a mai mic a corespunde cu o valoare a entropiei mai mic a  si deci un raport de
compresie obt inut ^ n nal este mai mare. A sa cum am ment ionat c^ and am discutat despre
corelat ia spat ial a a imaginilor, func/c tia covariant  a scade mult dac a lu am ^ n considerare
o distant a mai mare de opt pixeli fat  a de pixelul original. ^In concluzie, pentru calculul
predictorului nu este ecient a dac a utiliz am vecin at at i de pixeli care s a aib a o ad^ ancime
mai mare de opt pixeli.
Dac aXi;jreprezint a o imagine cu opt bit i, atunci eroarea, ei;jvs lua valori ^ n intervalul
[255;255]. Valorile cuantizate ale lui ei;jadic aqi;jvor ocupa acela si domeniu, doar c a
necesit a o reprezentare pe mai put ini bit i. Dac a avem 16 nivele de cuantizare, aceasta
^ nseamn a c a putem reprezenta qi;jpe numai 4 bit i, deci am obt inut o comprimare a
informat iei init iale.
1DPCM-Dierential Pulse Code Modulation
28

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:
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 [4]. 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
^In Figura 3.3 sunt prezentate dou a exemple de aplicare a transfor arilor. ^In gura a este
prezentat a o imagine surs a, care va  supus a transform arii Fourier rezult^ and matricea
transform arii din gura b, respectiv unei transform ari Cosinus Discret a rezult^ and matricea
transform arii din gura c.
A sa dup a cum se poate observa ^ n Figura 3.3, prin utilizarea DFT2energia se con-
centreaz a c atre extremit at ile matricei de coecient i [14]. ^In cazul transformatei Cosinus
2DFT-Transformata Fourier Discret a
29

Figura 3.3: Matricile coecient ilor transform arii DFT  si DCT
Discret a se observ a c a energia este ^ nmagazinat a ^ n coltt ul din st^ anga sus  si cu c^ at ne
deplas am spre colt ul din drapta jos valorile coecient ilor sunt mai mici. Din acest punct
de vedere utilizare DCT este mult mai ecient a dec^ act DFT. De aceea una dintre cele
mai utilizate transfor ari ^ n algoritmul de compresia este transformata cosinus discret a.
Un algoritm practic de codare prin transform ari aplicat pentru imagini este prezentat
^ n Figura 3.4, iar etapele succesive de implementare sunt urm atoarele:
Figura 3.4: Codare prin transformare bidimensional a
Divizarea imaginii de intrare ui^ n blocuri rectangulare de dimensiuni pq si
transformarea ec arui bloc, obt in^ andu-se Vi,i= 0;:::Il,I=NM
pq.
Determinarea aloc arii bit ilor . Pentru alocarea num arului de bit i putem folosi unul
din algoritmii uzuali din cazul unidimensional.
Alocarea cuantizatorului se face t ian^ and cont de modelele de distribut ie ale diferit ilor
coecient i ai transform arii.
Codarea ie sirii cuantizatorului ^ n cuvinte de cod  si transmisia sau memorarea lor.
30

Codarea zonal a  si codarea cu prag
Examinarea matricii de alocarea a bit ilor pune ^ n evident a faptul c  a doar o mic a zon a
din imaginea transformat a se transmite. Dac a Nieste num arul e santioanelor transmise,
se dene ste o mic a masc a zonal, ca ind matricea: m(k;l) =
31

3.5 Sistem de codare bazat pe transformata Cosinus
Discret a
^In Figura 3.5 este prezentat a schema bloc a unui sistem de care folose ste transformata
cosinus discret a. Aceasta reprezint a arhitectura de baz a utilizat a ^ n toate standardele de
compresie a imaginilor. O prima etap a a cod arii este ^ mpart irea imaginii ^ n blocuri de
Figura 3.5: Sistem de codare bazat pe transformata cosinus
8×8 pixeli.
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
32

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)
^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.
^In continuare vom considera doua exemple de implementare a algoritmului de compre-
sie DCT. Pentru aceasta am folosit o imagine pe 8 bit i. Am ^ mpart it imaginea ^ n blocuri
de 8×8 pixeli  si am extras dou a astfel de blocuri, unul dintr-o zon a cu activitate mic a^ n
care dierent a dintre pixelii vecini este mic a  si un alt bloc dintr-o zon a cu activitate mare,
caz ^ n care dierent a dintre pixelii vecini este semnicativ mai mare.
Valorile pixelilor sunt prezentate ^ n matricea X:
161 155 157 152 151 151 149 149
163 162 160 156 155 153 153 152
163 165 162 157 156 157 153 155
168 164 162 160 160 157 156 157
166 164 161 163 162 157 157 158
164 165 161 161 162 161 159 162
163 159 160 162 161 161 159 162
165 162 162 168 162 160 163 163
33

Figura 3.6: Exemplu de codare DCT
^In funct ie de spat iul culorilor ^ n care este reprezentat a imaginea, pixelii unei componente
pot avea valori medii zero sau diferite de zero. Pentru a realiza o prelucrare uniform a pe
toate planurile de pizeli, cele mai multe metode de codare DCT introduc un bloc de pre-
procesare, prin care valoarea medie obt inut a s a e zero [ ?,?]. Valoarea care se scade sau
adun a este apoi adunat a sau sc azut a la decodor dup a ce se aplic a transformata invers a.
^In cazul nostru , dup a sc aderea cu 128 obt inem matricea.
33 27 29 24 23 23 21 21
35 34 32 27 28 25 25 24
35 37 34 32 32 29 28 27
40 36 34 32 29 28 32 28
38 35 33 33 33 34 28 30
36 37 33 35 33 28 34 32
35 31 32 33 33 34 31 34
37 34 34 40 32 35 33 35
iar dup a aplicarea transformatei 2D DCT vom avea matricea coecient ilor Y, calculat i
dup a formula:
xk=N1X
n=0xncos
N
n+1
2
k
251 19 6 0 2 3 -2 2
-21 1- 3 1 -4 -1 2 3
-8 -2 -4 2 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
0 1 0 -2 0 -1 -3 1
-2 -1 -1 -1 0 0 1 -1
Trebuie precizat c a deja^ n acest punct al algoritmului s-a realizat o rotunjire a coecient ilor
DCT deci se poate spune c a avem pierderi datorit a procesului de implementare software,
pierderi ireversibile. Trebuie s a mai observ am c a ^ n matricea coecient ilor Ycomparativ
cu matricea pixelilor originali X, amplitudinile coecient ilor iau valori mari pentru pozit ii
apropiate de y00.^In general, pentru blocuri de pixeli cu activitate redus a, energia se va
acumula ^ n coecient ii de ordin inferior, ca ^ n cazul de fat a [ ?,?].
34

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:
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
Putem observa ^ n matricea coecient ilor cuantizat i num arul de zerouri este mult mai
mare dec^ at ^ n maricea coecient ilor de baz a. Alegerea matricii de cuantizare depinde de
caracteristicile vizuale  si de raportul de compresie pe care dorim s a-l obt inem. Practic
^ n urma procesului de cuantizare au rezultat doar opt valori nenule, comparativ cu cele
din matricea original a. Asta ^ nseamn a o rat a de compresie de 10.66. Matricea optt inut a
poate  ecient reprezentat a folosind o combinat ie de RLC  si codare de tip Human.
35

3.6 Compresia imaginilor binare
3.6.1 Codarea RLC  si Human aplicat a imaginilor binare
36

3.6.2 Cuantizarea diferent ial a cu predict ie
37

3.6.3 Codarea prin adresare relativ a
38

Capitol 4
Standardul de compresie JPEG
4.1 Introducere
Dezvoltarea aplicat iilor din domeniul IT au f acut necesar a implementarea unui stan-
dard pentru compresia imaginilor. Scopul implement arii JPEG a fost de a dezvolta un
standard de compresie a imaginilor care s a ^ ndeplineasc a o serie de cerint e:
s a e u sor de implementat ^ n aplicat ii;
s a permit a utilizatorului s a aleag a gradul de compresie ;
s a lucreze independent de tipul imaginii;
s a nu implice un grad de complexitate foarte mare din punct de vedere al calculelor;
s a permit a at^ at codarea secvent ial a c^ at  si cea progresiv a;
Dup a o serie de evalu ari preliminare, ^ n 1998 s-a luat decizia utiliz arii compresiei
cu DCT ca metod a de baz a utilizat a ^ n JPEG. ^Intre 1988-1990 s-au realizat o serie de
teste, simul ari  si ajust ari ale algoritmului. ^In 1991, JPEG devine o propunere de standart
internat ional, urm^ and ca un an mai t^ arziu acesta s a devin a standard internat ional. JPEG
include dou a metode de compresie:
metoda de compresie cu pierderi bazat a pe transformata Cosinus Discret a;
metoda de compresie predictiv a f ar a pierderi;
39

4.2 Codarea bazat a pe transformata cosinus discret a
40

4.3 Codorul si decodorul JPEG
Codorul JPEG
^In Figura 4.1 este prezentat a schema bloc a unui codor JPEG bazat pe trasformata DCT
pentru o imagine cu nivele de gri cu un singur plan de culoare. ^In cazul imaginilor color,
algoritmul se repet a pentru ecare component a. Prima etap a din algoritmul de compresie,
Figura 4.1: Schema codorului JPEG
putem observa c a este ^ mp art irea imaginii ^ n blocuri de 8×8 pixeli. Dac a rezolut ia spat ial a
a imaginii nu este multiplu de opt, atunci pixelii de pe ultimul r^ and sau ultima coloan a
sunt duplicat i, astfel ^ nc^ at, s a se obt in a blocul 8×8 pixeli.
Fiecare bloc este transformat ^ n domeniul frecvent  a prin aplicarea transformatei 2D
DCT. Standardul nu specic a un anumit algoritm pentru implementarea DCT. Coecient ii
DCT sunt apoi cuantizat i  si codat i entropic.
Codarea entropic a se face ^ n dou a etape. Prima este reprezentat a de o codare predic-
tiv a a coecient ilor DCT din ecare bloc 8×8, respectiv o codare RLC pentru coecient i
AC, iar cea de-a doua etap a este e un codor Human e un codor aritmetic. Codarea
arimetic a duce la obt inereaunui raport de compresie mai ecient dec^ at cel obt inut de
codorul Human, cu toate aceste ^ n practic a este mai put in folosit [ ?,?].
Pentru a putea  acceptat ca  si standard internat ional, JPEG a dezvoltat  si un  sier
care cont ine imaginea  si parametrii de codare ^ n  sirul de bit i codat. Acestea permit im-
plementarea JPEG pe diferite platforme, iar decompresia poate  realizat a f ar a probleme.
Decodorul JPEG
Dup a extragerea tabelelor de cuantizare  si codarea din  sirul de bit i codat, datele trim-
ise sunt trimise blocului decodor entropic. Coecient ii DCT sunt apoi decuantizat i si
translatat i ^ n domeniul spat ial folosind transformata invers a determinat i prin formul a
(3.2). Acestora li se adun a 128  si se obt ine blocul reconsruit. Calitatea acestei imagini
depinde de num arul de coecient i p astra cti la codare. Dac a se vor p astra tot i coecient ii
nenuli, atunci imaginea reconstruit a va  foarte asem an atoare cu originalul.
41

4.4 Prelucrarea imaginilor color
42

4.5 Algoritmul de codare
Ultimul bloc de prelucrare din schema codorului JPEG este compresia entropic a.
Codorul entropic folosit ^ n JPEG nu reprezint a nu reprezint a algoritmul clasic de co-
dare Human sau aritmetic a, ci folose ste unul care combin a o variant a a acestor tipuri
de codare cu o codare DPCM, respectiv RLC. Dac a folosim codarea Human ca algoritm
de baz a atunci se pot folosi p^ ana la opt tabele de codare, ^ ns avem dou a resctrct ii de care
trebuie s a t inem cont:
niciun cuv^ ant de cod nu trebuie s a dep a seasc a 16 bit i;
niciun cuv^ ant de cod nu poate avea tot i cei 16 bit i egali cu 1.
Codarea Human a coecient ilor DC
Av^ and ^ n vedere c a exist a o puternic a leg atur a ^ ntre coecient ii DC din blocurile
adiacente, standardul JPEG folose ste un algoritm de codare diferent ial a pentru ace sti
coecient i. Diferent a [ DCilDCi] poate s a ia valori ^ n intervalul [-2047, 2047]. Acest
domeniu este ^ mpart it ^ n 12 categorii, unde categoria " i" include toate valorile diferent  a
care pot  reprezentate pe ibit i. Astfel ecare valoare diferent  a ca  descris a de perechea
(dim, amp), unde dim reprezint a num arul de bit i necesari pentru a reprezenta ampli-
tudinea, iar amp, reprezint a valoarea efectiv a a diferent ei.
Codarea Human a coecient ilor AC
Pentru o rezolut ie de 8 bit i coecien ctii AC pot lua valori ^ ntre [-1023, 1023], ceea ce
implic a o ^ mp art ire ^ n 10 categorii de amplitudine. Fiecare coecient va  descris de o
pereche de valori ( dim, amp ). Dup a cuantizare, cei mai mult i coecient i vor avea valoarea
0, a sa cum am v azut ^ n capitolul precedent, astfel c a doar coecient ii nenuli vor  codat i
[14].
Scanarea zig-zag se face ^ n scopul ordon arii dup a spectrul de frecven ta. Deoarece
componentele de frecven ta ^ nalt a au valori aproximativ nule , ^ n urma scan arii zig-zag
rezult a  siruri nule, av^ and posibilitatea realiz arii unei cod ari RLC.
^In Figura avem traiectoria de parcurgere zig-zag, a coecient ilor AC, a sa cum este
specicat a ^ n standardul JPEG.
Figura 4.2: Algoritmul de ordonare zig-zag
Codorul RLC, furnizeaz a valoarea urm atorului coecient nenul  si num arul de coecient i
AC nenuli care-l preced. Astfel, ecare coecient AC nenul poate  descris de un cuv^ ant
de cod de form ( dim, amp ) [?,?]. Perechea dimeste codat a Human iar valoarea amp
este ad augat a la acest cod ^ n mod asemn ator algoritmului folosit pentru coecient ii DC.
43

4.6 Modul de codare progresiv
Exist a dou a diferent e ^ ntre modul de baz a  si modul progresiv:
modul progresiv poate folosi ^ ntre 8 si 12 bit i pentru reprezentarea planurilor de
culoare;
modul progresiv poate folosi at^ at codarea Human c^ at  si docarea entropic a;
^In multe aplicat ii de compresie a imaginilor apare dezavantajul c a, datorit a rezolut iilor
mari la care sunt reprezentate imaginile, timpul de codare, de transmisie  si respectiv de
decompresie este de ordinul minutelor. ^In astfel de aplicat ii se poate aplica un algoritm de
compresie progresiv, care init ial produce o imagine brut a, dup a care prin scan ari succesive
se ^ mbun at at e ste calitatea imaginii.
Modul de compresie progresiv JPEG, se obt ine prin realizarea unui set de subimmagini,
ecare subimagine ind codat a cu un set specic de coecient i DCT. Codorul DCT va
trebui s a aib a un amortizor ^ n care datele s a e memorate ^ nainte de codarea entropic a.
^In Figura 4.3 este prezentat modul de compresie progresiv JPEG,
Figura 4.3: Exemplu de compresie progresiv a
Codarea progresiv a se obt ine folosind trei tipuri de algoritmi:
algoritm progresiv de select ie spectral a;
algoritm progresiv de aproxim ari progresive;
algoritm progresiv combinat;
Algoritmul progresiv de select ie spectral a
Acest algoritm grupeaz a coecient ii transformatei cosinus distret a ^ n benzi de frecvent a.
Coecient ii de joas a frecvent a sunt transmi si ^ ntai, dup a care urmeaz a coecient ii cu
frecvent a ^ nalt a. ^In Figura 4.4 este prezentat un exemplu ^ n care coecient ii DCT sunt
^ mp art it i ^ n patru benzi. ^In banda 1 sunt coecient ii de curent continuu, banda 2 cuprinde
primii coecient i de curent alternativ, AC1, AC2, banda 3 cont ine cot ine coecient ii AC3,
AC4, AC5, AC6, iar banda 4 coecient ii de la AC7 p^ an a la AC63.
Algoritmul progresiv cu aproxim ari succesive
Acest algoritm se bazeaz a pe transmisia init ial a, cu precizie sc azut a, a tuturor coecient ilor
transformatei cosinus discret a, dup a care se transmite restul informat iei, pentru obt inerea
unei imagini de calitate superioar a [ ?,?].^In Figura 4.5 este prezentat un exemplu ^ n care
coecient ii DCT sunt ^ mpart it i ^ n trei benzi de aproxim ari succesive. Pe banda 1 ^ ntalnim
tot i coecient ii DCT ^ mpart it i la 4, banda 2 cuprinde coecient ii ^ mpart it i la 2  si pe banda
3 avem coecient ii DCT la precizia normal a.
Algoritmul progresiv combinat
Acest algoritm reprezint a o combinat ie a primilor doi algoritmi. ^In Figura 4.6 este prezen-
tat planul coecient ilor DCT ai unei imagini, dup a ce aplic am algoritmul combinat. Dup a
cum putem observa s-au format opt secvent e de coecient i, care vor  transmi si ^ n ordinea
numerot arii lor  si anumel DC1 apoi AC1 si a sa mai departe.
44

Figura 4.4: Algoritmul progresiv cu select ie spectral a
Figura 4.5: Algoritmul progresiv cu aproxim ari succesive
4.7 Codarea ierarhic a
Codarea ierarhic a este reprezentat a de codare piramidal a a unei imagini la diferite
rezolut ii, ecare diferind ca rezolut ie de codarea adiacent a printr-un factor din oricare
dou a domensiuni, orizontal a sau vertical a, sau chiar ambele. Fiecare plan al imaginii
este codat cu o secvent  a de cadre. Primul cadru este reprezentat de obicei de o versiune
de rezolut ie joas a a imaginii originale. Cadrele care urmeaz a sunt cadre reprezentate de
diferent a^ ntre planurile imaginii surs a sube santionate  si planurile de referint  a reconstruite.
Cadrele pot  codate folosind codarea JPEG cu pierderi, e cadarea f ar a pierderi. Codarea
ierarhic a este folositoare atunci c^ and avem nevoie de imagini la rezolut ii multiple [2].
^In Figura 4.6 este prezentat un exemplu de codare ierarhic a.
Figura 4.6: Algoritmul progresiv combinat
45

Figura 4.7: Exemplu de codare ierarhic a
Din imaginea original a Xse genereaz a dou a versiuni sube santionate:
X2, ^ n care imaginea este sube santionat a cu 2 pe ambele direct ii H siV;
X4, ^ n care imaginea este sube santionat a cu 4 pe ambele direct ii;
Algoritmul de compresie ierarhic a const a ^ n urm atorii pa si:
sube santinarea imaginii originale cu factorul dorit, de-a lungul ec arei dimensiuni,
vertical sau orizontal;
codarea imaginii de rezolut ie joas a folosind tehnicile de codare DCT secvent ial a,
progresiv a sau codarea f ar a ierderi;
decodarea imaginii de rezolut ie mic a, interpolarea  si suprae santionarea cu un factor
de doi, pe direct ia vertical a sau orizontal a, folosind un ltru de interpolare identic
cu cel al decodorului;
folosirea imaginii suprae santionat a ca predictor al imaginii originale  si codarea
diferent elor dintre dou a imagini;
se repet a algoritmul p^ an a c^ and algoritmul se codeaz a la rezolut ia init ial a.
Trebuie s a subliniem faptul c a procesul de sube santionare, poate  precedat de o
operat ie de ltrare pentru a reduce efectele de tip alias.
Imaginea codat a este alc atuit a din trei cadre: S1,S2,S3. CadrulS1reprezint a imaginea
X4comprimat a. Folosind doar codorul S1decodorul poate extrage o imagine X0
l, de
rezolut ie mic a. Cadrul S2reprezint a imaginea diferent  a dintre X2 si o estimare a lui X0
2,
dup a suprae santionarea lui X4cu 2. Folosind S1 siS2, decodorul poate extrage o imagine
de rezolut ie medie X0
m.^In mod similar S3este imaginea diferent a ^ ntre imaginea original a
X si o estimare a lui X, bazat a pe X2 siX4. Dac a se folose ste o metod a de compresie
f ar a pierderi atunci X=X0.
Pentru codarea ierarhic a trebuie sa aloc am o zon a de memorie destul de mare pentru
a implementa algoritmul, dar avem avantajul c a imaginea codat a este imediat disponibil a
la diferite rezolut ii.
46

Capitol 5
Comparat ia dintre formatul JPEG  si formatul PNG
47

Capitol 6
Concluzii
48

Index
a comprima, 20
algoritm, 46
bit i, 32
bloc, 6, 32, 33
codare entropic a, 24
codare predictiv a, 41
coecient i, 34
compresia f ar a pierderi, 24
compresie, 5
compresie ierarhic a, 46
conversie, 33
crominant a , 23
cuantizare, 35
culoare, 20
decodare, 26, 46
digit i, 24
dilatare, 11, 13
e santion, 24
element structural, 12
entropie, 24
eroare de predict ie cuantizat a, 28
eroziune, 13
ltru, 46

ux, 25
frecvent a, 44
imagine, 35
imagine , 15
luminant  a, 6, 17
matrice, 35
pixel, 18, 20
ponderile, 33
redundant  a, 22
rezolut ie, 29, 41, 46
sube santionare, 22, 46
transformare, 35
49

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