 án tt nghip i hc c lc
 Th Hnh – D04VT1 i
C LC
MC LC i
THUT NG VIT TT iii
DANH MC HÌNH V v
LI GII THIU vi
CHNG 1: TNG QUAN V NÉN NH VÀ CHUN NÉN NH JPEG 7
1.1. Gii thiu tng quan v nén nh 7
1.1.1 Phân loi k thut nén 8
1.1.2 Mt s k thut mã hóa 9
1.2 Chun nén JPEG 12
1.2.1 Gii thiu 12
1.2.2 Bin i cosin ri c DCT 14
1.2.3 Lng t hóa 19
1.2.4 Quét zig-zag 21
1.2.5 Mã hóa  dài thay i VLC 23
1.2.6 Quá trình gii nén 25
1.2.7 Mã hóa và gii mã JPEG tun t 28
1.2.8 Nén JPEG y tin 29
1.3. Kt lun 30
CHNG 2: BIN I WAVELET 31
2.1 Bin i Wavelet 31
2.1.1 Bin i wavelet ri rc 33
2.1.2 Khái nim phân tích a phân gii 34
2.1.3 S dng b lc và thut toán hình chóp 36
2.2 M rng i vi các tín hiu 2-D. 39
2.3 Trin khai Lifting cho bin i wavelet ri rc 41
2.3.1 Lifting 43
2.3.2 S ph thuc d liu cho tính toán Lifting 47
2.4. Kt lun 49

DWT Decrete Wavelet Transform Bin i wavelet ri rc
EBCOT Embedded Block Coding with
optimized Truncation
Thut toán mã hóa cho BPC
EPH End of Packet Header Kt thúc tiêu  gói
FDCT Forward Decrete Cosin Transform Bin i cosin ri rc thun
FIR Finite Impulse Response áp ng xung hn ch
ICT I Colour Transform Nhóm các nh
IDCT High Definition Television Truyn hình  phân gii cao
ISO/IEC International Standards
Organisation/International
Electrotechnical Commission
T chc chun quc ty ban k
thutin quc t
IWT Interger Wavelet Transform Bin i Wavelet nguyên
JPEG Joint Photographic Experts Group Nhóm chuyên môn vnh
 án tt nghip i hc Thut ng vit tt
 Th Hnh – D04VT1 iv
JPWL JPEG Wireless JPEG cho không dây
LSB Least Significant Bit Bit có  quan trng thp nht
MJPEG Motion JPEG Mt chun trong h JPEG
MPEG Motion Picture Experts Group Nhóm chuyên môn v phim nh
MSB Most Significant Bit Bit có  quan trng cao nht
MSE Mean - Squared Error Sai s bình phng trung bình
PSNR Peak Signal to Noise Ratio T l tín hiu nh trên nhiu
QMF Quardrature mirror filters B lc gng cu phng
RGB Red, Green and Blue Các màu c bn
RCT Reversible Colour Transform Bin i màu thun nghch
RLC Run Length Coding Mã hóa  dài chy
RVLC Reversible Variable Length Code Mã hóa  dài thayi nghch

Hình 1.14 S  khi h thng gii mã JPEG 25
Hình 1.15 Khôi phc các m nh trong khi 8x8 27
Hình 1.16 Sai s ca các m nh c khôi phc so vi giá tr ban u 27
Hình 1.17 S khi mã hóa và gii mã JPEG 28
Hình 1.18 Quá trình gii mã JPEG ly tin và tun t 29
Hình 2.1 Hàm wavelet m (t) 32
Hình 2.2 Phân tích và tái to tín hiu wavelet a phân gii 3 mc s dng cu trúc b
lc hình chóp. 38
Hình 2.3 Tính toán hàng-ct ca DWT 2-D. 40
Hình 2.4 M rng DWT cho các tín hiu 2-D 40
Hình 2.5 nh xe p ban u và sau các mc phân tích; 41
Hình 2.6 Phân tích và tái to tín hiu trong DWT 43
Hình 2.7 DWT thun và ngc da trên Lifting 45
Hình 2.8 S quan h d liu vi các h s lifting. 48
Hình 3.1 Kin trúc ca b mã hóa JPEG-2000 50
Hình 3.2 Ví d minh ha kh nng ca công ngh JPEG2000 53
Hình 3.3 Minh ha các kiu nén 55
Hình 3.4 S khi ca thut toán b mã hóa JPEG2000 và lung d liu 59
Hình 3.5 Lng t hóa dead-zone 63
Hình 3.6 Mã hóa theo vùng 64
Hình 3.7 Mt n ROI 65
Hình 3.8 MAXSHIF 66
Hình 3.9 Ví d cu trúc d liu cây tag 70
Hình 3.10 Cu trúc cây Quad 71
Hình 3.11 Lung bit c to ra sau mã hóa 71
Hình 3.12 nh dng lung bit 72
 án tt nghip i hc Li gii thiu
 Th Hnh – D04VT1 vi
I GII THIU
Nhng nm tr li ây, nén nh ã tr thành công ngh ch yu cho các ng

Mc ích ca chng này là gii thiu chung v nén nh, bao gm khái nim,
phân loi các k thut c bn ca nén nh, mt s phng pháp trong mã hóa nh: mã
hóa doán, mã hóa da trên phép bin i, mã hóa bng con. Chng 1 cng trình
bày v mt h thng nén nh theo chun JPEG.
1.1. Gii thiu tng quan v nén nh
S phân tích các tín hiu video cho thy có s liên quan cht ch gia các khung
nh liên tip và c trong bn thân nhng phn tnh. V mt lý thuyt, vic gim s
ng quan ca nhng tín hiu này có th dn ti vic nén bng tn mà không nh
ng áng k ti  phân gii hình nh. Hn na, có th tn dng  nhy ca h
thng th giác ca con ngi i vi s mt mát mt s thông tin có th gim c
nhiu s tng quan hn. Do ó, các công ngh nén có tn tht có thc s dng
 làm gim s lng bit biu din trong khi vn gic mt cht lng hình nh
chp nhn c.
Nh vy, nhng tín hiu mang thông tin có thc nén, tc là chuyn sang mt
s biu din hoc mt dng mà yêu cu ít bit hn tín hiu ban u (không nén). Mt
thit b hoc chng trình dùng  nén mt tín hiu là mt encoder và thit b hay
chng trình  gii nén tín hiu là mt decoder. Mt b enCOder/DECoder c gi
là mt CODEC.
Hình 1.1 B mã hóa ngun, b mã hóa kênh, kênh
Hình 1.1 th hin mt ví dn hình v mt CODEC là mt phn ca h thng
truyn thông. Thông tin ban u (cha nén) c mã hoá (nén): ó là quá trình mã hoá
ngun. Tín hiu ã mã hoá ngun sau ó c tip tc mã hoá  thêm kh nng
chng li (mã hoá kênh) và  u tiên  truyn dn qua mt kênh. Ti u thu, mt
b gii mã kênh s tách và (hoc) sa nhng li trong quá trình truyn dn và mt b
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 8
gii mã ngun s gii nén tín hiu. Tín hiu ã c gii nén có th ging ht nh tín
hiu ban u (nén không tn tht) hoc nó cng có th b méo hoc suy bin theo mt
vài cách nào ó (nén có tn tht).
1.1.1 Phân loi k thut nén

n (nguyên lý này c s dng trong mã hoá Huffman). Vic nén c to ra bi
vic làm gim s tha tnh trong file vn bn. Loi CODEC c s dng cho mc
ích này c bit n là CODEC entropy. Mô hình ngun s khai thác các c tính
ca d liu hình nh và biu din nó di mt dng có th nén bi mt b mã hoá
entropy. Hình 1.2 th hin mt thit k c bn ca mt CODEC hình nh hoc video
bao gm mt mô hình ngun và mt b mã hoá/gii mã entropy.
Hình 1.2 CODEC hình nh hoc video
1.1.2 Mt s k thut mã hóa
a) Mã hóa doán:
i vi mã hoá doán (predictive coding) các giá tr mang thông tin ã c gi
hay ang sn có sc s dng  doán các giá tr khác, và ch mã hoá s sai lch
gia chúng. Phng pháp này n gin và rt phù hp vi vic khai thác các c tính
cc b ca bc nh. K thut DPCM chính là mt ví dn hình ca phng pháp
này. u. Trong phng pháp mã hoá d oán, sai lch nh gc và nh doán vn
có ý ngha (còn s dng  bc tip theo) sau khi lng t hoá, chính u này làm
cho phng pháp mã hoá doán có nhiu d liu c truyn i hn so vi phng
pháp mã hoá bin i.
b) Mã hóa da trên phép bin i:
Mã hoá da trên phép bin i (transform based coding) thc hin nh sau: trc
tiên thc hin phép bin i vi nh  chuyn s biu din nh t min không gian
sang mt min biu din khác. Các phép bin i thng dùng là: DCT - bin
i Cosine ri rc, DWT - bin i Wavelet ri rc tip ó thc hin mã hoá i vi
các h s bin i. Phng pháp này có hiu sut nén cao hn rt nhiu so vi phng
pháp nén doán bi vì chính các phép bin i (s dng các thuc tính nén nng
ng ca mình) ã gói gn toàn b nng lng bc nh ch bng mt s ít các h s,
s ln các h s còn li ít có ý ngha loi b sau khi lng t hoá và nh vy
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 10
ng d liu phi truyn nh i rt nhiMt phép bin i là mt hàm toán hc
c s dng  bin i mt tp các giá tr này thành mt tp giá tr khác và to ra

quan tng không bao git c do nhng b lc này ch xp x vi các b lc lý
ng. Hình 1.3 di ây là s tng quát gii thích k thut mã hoá bng con.
Các b lc s dng trong mã hoá bng con là các b lc gng t phng – QMF
(quardrature mirror filters), do vy chúng ta ch cn thit k các b lc thông thp
có áp ng H còn áp ng ca các b lc thông cao ch là s dch pha 180
0
so vi b
lc thông thp. S chính xác ca b lc ph thuc vào s các h s ca b lc.
Mt trong các phng pháp mã hoá bng con ó là áp dng s phân ly cây bát
phân  phân ly d liu nh thành các bng tn khác nhau. Ý tng ca
phng pháp này là: trc tiên lc và lc bnh  phân ly nh thành các bng con
tn s cao và thp, sau ó tip tc phân ly nhng ch áp dng cho ng con tn s thp
 to thành các bng con tn s cao và thp  tip tc lc b. K thut này rt ph
bin và cng c áp dng trong các b mã s dng bin i Wavelet. u ra ca các
ng con sau khi ã gin lc sc lng t hoá và mã hoá c lp. Mi bng con
s s dng b lng t hoá riêng và mi b lng t hoá này có tc  ly mu riêng
(bít/mu).
N vy rõ ràng mã hoá ng con không t c s nén, mà nó ch thc hin
vic gii ng quan d nh gc và tp trung ng ng ca nh vào mt s
ng con. Nén ch t c là do s c b nh
(decimation)
và do s lng t
hoá
(quantization)
.
Trong các h thng mã hoá bng con hai chiu thc t, ngi ta chia min tn s -
không gian hai chiu ca nh gc thành các bng khác nhau  bt k mc nào.
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 12
Hình 1.4 Minh ho quá trình phân ly bng con cây bát phân

nó cho nh nén cht lng tt nht i tc  bit thp và gii thut chuyn i nhanh và
d dàng thc hin bng phn cng. Trc khi a vào chuyn i DCT, nh gc phi
c x lý  nén di tn tín hiu hiu màu và chia nh thành các block. Vic nén ph
tín hiu hiu màu làm gim   tha tâm sinh lý.  thut này da vào c trng h
thng th giác a con ngi. Mt ngi kém nhy vi s thay i tín hiu màu hn s
thay i tín hiu chói. Vì vy, ta không cn thit truyn i thông tin a tín hiu màu
vi tn s nh truyn thông tin tín hiu chói.
 l ly mu thông ng là 4:2:2 và 4:1:1. nh ng 4:2:2 ngha là c 4 mu tín
hiu chói thì có 2 mu cho mi loi tín hiu hiu màu. Nói cách khác, c 2 mu tín
hiu chói có 1 mu tín hiu hiu màu. nh ng 4:1:1 ngha là c 4 mu tín hiu chói
thì có 1 mu cho mi loi tín hiu hiu màu. Gi s tín hiu hiu màu ch c ly
mu theo chiu c và mi mu có 8 bit, s bit trung bình trên mt pixel theo  l ly
mu 4:2:2 là 8×4/2, hay 16 bit/pixel. Theo  l 4:1:1 là 8×6/4, 12bit/pixel.  thut
ly mu tín hiu hiu màu c áp ng  hai chiu ngang và dc.  nhiên, iu này
làm gim hn na lng thông tin v tín hiu hiu màu.
Trc khi thc hin bin i DCT, nh c chia thành các khi ln riêng bit
không chng nhau (MB-Marco Block). Mi MB bao gm 4 block các tín hiu chói (Y)
và 2,4 hoc 8 block các mu tín hiu hiu màu (Cr,Cb). S các block a tín hiu hiu
màu ph thuc vào tiêu chun ly mu a tín hiu video: 4:2:2, 4:1:1 hay 4:2:0 v.v.
Tt  các block có cùng kích thc và mi block là mt ma trn im nh 8×8
pixel c ly t mt nh màn hình theo chiu t trái sang phi, t trên xung di.
Kích thc block là 8×8c chn bi hai lý do sau:
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 14
a) Th nht, qua vic nghiên cu cho thy hàm tng quan suy gim rt nhanh khi
khong cách gia các pixel vt quá 8.
b) Th hai, là s tin li cho vic tính toán và thit k phn cng. Nói chung, 
phc p v tính toán  ng nu kích thc block tng.
Hình 1.6  mã hóa và gii mã theo JPEG
1.2.2 Bin i cosin ri c DCT

X k C k xm
NN
π
−
=
+
=
∑
(1.1)
Hàm bin i DCT ngc (mt chiu):
( )
1
0
2 (2 1)
()()cos
2
N
k
mk
xm XkCk
NN
π
−
=
+
=
∑
(1.2)
trong ó: X(k) là chui kt qu.
x(m) là giá tr a mu m.

7
0
7
0
ππ vkuj
kjf
jk
++
∑∑
==
(1.3)
trong ó:
f(j,k)- các mu gc trong khi 8×8 pixel.
F(u,v)-các h s ca khi DCT 8×8.
( ) ( )
1/2 ,0
,
1 ,0
uv
Cu Cv
uv

=

=

≠


 án tt nghip i hc Chng 1 Tng quan v nén nh…

00
( 2 1) ( 2 1)
, ( , )cos cos
4 16 16
uv
CuCv
ju kv
f jk Fuv
ππ
==
++
=
∑∑
(1.5)
Nh vy, bin i DCT ging nh bin i Fourier và các h s F(u,v) ng ging
nhau v ý ngha. Nó biu din ph tn tín hiu c biu din bng các mu f(j,k). n
thân phép bin i DCT không nén c s liu, t 64 mu ta nhn c 64 h s.
Tuy nhiên, phép bin i DCT thay i phân b giá tr các h s so vi phân b các
giá tr mu. Phép bin i DCT cho ta giá tr DC tc F(0,0) thng ln nht và các h
s trc tip k nó ng vi tn s thp có giá tr nh hn, các h s còn i ng vi tn
s cao có giá tr rt nh.
Hình  1.7 là mt ví d minh ha quá trình DCT hai chiu a mt khi 8×8
im nh (chói) c trích ra t mt nh thc. Nu dùng quá trình DCT cho các tín
hiu s thành phn Y, C
R
,C
B
thì các tín hiu C
B
,C

các giá tr pixels en (giá tr=0) và trng (giá tr=255) xen . Sau khi gim vi –128
thu c các giá tr pixels trong di ng +127 và –128. ây là khi nh có s bin
i ln nht v giá tr biên  các im nh và các h s DCT kt qu xác nh nhn
xét này. Mc dù có nhiu h s tn s bng 0, giá tr ca các h s có tn s cao óng
vai trò quan trng trong vic tái o i hình nh khi bin i DCT ngc.
Tóm i, DCT làm gim  ng quan không gian a thông tin trong block. iu
ó cho phép biu din thích hp  min DCT do các h s DCT có xu hng có phn
 tha ít hn. iu này có ngha là DCT gói mt phn ln nng lng tín hiu vào
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 19
các thành phn bin i có tn s ng i thp  u tr hoc truyn dn, o 0 và
các giá tr rt thp i vi thành phn tn s cao.
Hình 1.9 Khai trin DCT cho khi nh có  chói dng bàn c.
Nh c tính ca h thng nhìn a mt ngi, các h s DCT có th c mã hóa
phù hp, ch các h s DCT quan trng nht mi c mã hóa và truyn i. DCT
thun kt hp vi DCT nghch  không cho tn tht nu  dài t mã ca h s là 13
n 14 bit cho tín hiu video u vào c s hóa bng các mu dài 8 bit. Nu h s
c lng t hóa bng 11 bit (hoc ngn hn), thì nén bng DCT  có tn hao.
1.2.3 Lng t hóa
Bc tip theo a quá trình nén trong nh là lng t hóa các h s F(u,v) sao
cho làm gim c s lng bit cn thit. Các h s ng ng vi tn s thp có các
giá tr ln hn, và nh vy nó cha phn nng lng chính a tín hiu, do ó phi
lng t hóa vi  chính xác cao. Riêng h s mt chiu òi i  chính xác cao
nht, bi  nó biu th giá tr  chói trung bình a tng khi phn tnh. Bt 
mt sai sót nào trong quá trình lng t h s mt chiu u có kh ng nhn bit d
dàng bi nó làm thay i mc  chói trung bình a khi. Ngc i, vi các h s
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 20
ng ng vi tn s cao và có các giá tr nh, thì có th biu din i bng tp giá tr
nh n hn các giá tr cho phép.


+
),(
2
),(
),(
vuQ
vuQ
vuF
(1.6)
Các giá tr Fq(u,v) s c mã hóa trong các công n tip theo.
Cn phi xác nh là trong quá trình lng t hóa có trng s có xy ra mt thông
tin, gây tn hao. ây là bc tn hao duy nht trong thut toán nén. Mc  tn hao
ph thuc vào giá tr các h s trên ng lng t. Sau khi nhân các h s lng t hóa
Fq(u,v) vi Q(u,v) và bin i ngc DCT  không nhn c block s cp các mu
f(j,k). Tuy nhiên, trong trng hp nh t nhiên và la chn các giá tr Q(u,v) thích
hp, s khác nhau  nhn mc mà mt ngi không phân bit c gia nh gc
và nh biu din.
Hình 1.10 Các ng lng t cho tín hiu chói và màu theo chun JPEG
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 21
Các thành phn DC và tn s thp là các thông s nhy m nht a khi pixel
gc. H s DC  c lng t vi  chính xác 12 bit nhm tránh các nhiu xut
hin gia các khi im nh. Ngc i, các h s tn s cao có th lng t hóa thô
vi  chính xác 2 bit-do kh ng m nhn a mt ngi gim  tn s cao. Theo
ó, h s chia trong ng lng t hóa là nh i vi các h s có tn s thp và ng
t t i vi các h s có tn s cao hn.
Trong hình  1.10, giá tr khi xác nh cho phép các giá tr tín hiu chói và tín
hiu màu c lng t khác nhau. Nhiu lng t i vi tín hiu màu khó nhìn thy
n i vi tín hiu chói, cho nên có th thc hin lng t hóa thô tín hiu màu.

 thut RLC c dùng  mã hóa có hiu qu các h s DCT ã lng t hóa
n là dùng trc tip cho s liu nh. Sau quá trình quét zig-zag  trên, RLC  c
thc thi. Mt h s khác 0 sau giá tr DC c mã hóa bng 1 t mã bao gm 2 thông
s: s lng 0 chy trc 1 h s riêng khác 0 và mc a nó sau khi lng t hóa.
 án tt nghip i hc Chng 1 Tng quan v nén nh…
 Th Hnh – D04VT1 23
RLC thc cht là vic thay th các h s có giá tr 0 bng s lng các ch s 0 xut
hin.
Hình  1.12 là mt ví d v mã hóa entropy. Trong ví d này, chui mt chiu
các h s DCT sau khi quét zig-zag vi các giá tr ging nhau c gom i vi nhau
bng mã RLC. Lúc này, chui mt chiu có các n chui dài có cùng giá tr là các
symbol có dng:< chiu dài chui 0, giá tr>.
 ây, giá tr 10 không có giá tr 0 nào trc ó c biu din bng <0,10>; giá
tr –2 có hai giá tr 0ng trc c biu din bng <2,-2>v.v Riêng mt du c
bit là End of Block (EOB) c dùng  cho bit tt  các h s tip theo trong khi
bng 0. Trong ví d này, ta có mt chui 49 t mã vi giá tr 0. Nh vy ch xét riêng
49 t mã giá tr 0c nén xung ch còn 3 t mã. iu này chng  hiu sut nén rt
cao a mã hóa RLC. Nén bng mã RLC là quá trình nén không tn hao.
1.2.5 Mã hóa  dài thay i VLC
Các t mã RLC tip c c mã hóa bng cách t các t mã ngn cho các mc
có xác sut xut hin cao và các t mã dài cho các mc có xác sut xut hin thp.
Bng 1.1 minh ha các phân nhóm các h s AC.
ng 1.2 là mt ví d v bng mã Huffman tng ng cho các nhóm. T mã ngn
báo hiu kt thúc khi (EOB) cho bit tt  các h s còn i trong khi mang giá tr
0. Trong ví d khi h s DCT, h s DCT (40) c mã hóa DPCM bng cách dùng
giá tr DC (25) a khi DCT trc. Mã hóa DPCM m rng thang biu din tín hiu
Y t ( -1024 n 1016) n (-2048 n 2032).
ng 1.1 Phm vi giá tr các h s trong các nhóm (category).
Giá tr chênh lch h s DC c mã hóa VLC nh mt ng tìm kim (lookup
table). u ra a nó là mt s nh phân Huffman da trên giá tr chênh lch các h s