Xử lý ảnh_Chương 4 Mã hóa ảnh
Mục tiêu chính của mã hóa ảnh là làm sao trình bầy ảnh với số bít càng nhỏ càng tốt trong khi vẫn giữ được mức chất lượng và độ dễ hiẻu ở mức chất lượng vừa đủ với một ứng dụng đã cho.
Bạn đang xem trước 20 trang tài liệu Xử lý ảnh_Chương 4 Mã hóa ảnh, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ch¬ng 4: m· ho¸ ¶nh
167
Ch¬ng 4
M· HO¸ ¶NH
Më ®Çu.
Môc tiªu chÝnh cña m· ho¸ ¶nh lµ lµm sao tr×ng bÇy ¶nh víi sè bÝt cµng nhá cµng
tèt trong khi vÉn gi÷ ®îc møc chÊt lîng vµ ®é dÔ hiÓu ë møc chÊt lîng võa ®ñ víi
mét øng dông ®· cho. Cã hai lÜnh vùc øng dông:
Mét lµ gi¶m bÒ réng b¨ng tÇn cÇn thiÕt cho hÖ truyÒn ¶nh. VÝ dô truyÒn h×nh sè,
héi nghÞ video, fax –øng dông thø hai lµ gi¶m bít yªu cÇu vÒ lu tr÷. VÝ dô gi¶m lu tr÷
sè liÖu ¶nh trong c¸c ch¬ng tr×nh vò trô vµ sè liÖu video trong m¸y ghi h×nh sè. Tuú
theo tÝnh chÊt cña øng dông, møc ®é chÊt lîng ¶nh vµ ®é dÔ hiÓu cã thÓ biÕn ®æi trong
mét ph¹m vi réng. Trong lu tr÷ ¶nh cña ch¬ng tr×nh vò trô hay lu tr÷ ¶nh lÞch sö
(kh«ng thÓ cã l¹i ®îc) ph¶i lu tr÷ l¹i toµn bé t liÖu sè cña nguyªn b¶n ®Ó sö dông vÒ
sau.
Nh÷ng kü thuËt kh«ng lµm mÊt tÝ th«ng tin nµo vµ cho phÐp phôc håi chÝnh x¸c t
liÖu sè ban ®Çu, gäi lµ kü thuËt cã tÝnh b¶o tån th«ng tin. Trong truyÒn h×nh sè th× bé m·
ho¸ kh«ng cÇn ph¶i lµ lo¹i b¶o tån th«ng tin nh vËy. ë ®©y chÊt lîng cao lµ quan
träng, nhng cã thÓ bá qua mét sè th«ng tin tõ t liÖu gèc, trong ph¹m vi mµ tÝn hiÖu
gi¶i m· ra vµ hiÖn lªn mµn h×nh vÉn võa m¾t ngêi xem. Trong øng dông vÒ ®iÒu khiÓn
con tµu tõ xa, ®é dÔ hiÓu cña ¶nh lµ quan träng nhÊt, nhng cã thÓ hi sinh mét phÇn chÊt
lîng. Cµng gi¶m yªu cÇu vÒ chÊt lîng vµ ®é dÔ hiÓu, th× tèc ®é bit cµng h¹.
M· ho¸ ¶nh liªn quan ®Õn c¶i thiÖn ¶nh vµ phôc chÕ ¶nh. nÕu ta cã thÓ c¶i thiÖn
c¶m quan thÞ gi¸c cña ¶nh ®îc lËp l¹i hay nÕu ta cã thÓ gi¶m sù xuèng cÊp do algorit
m· ho¸ h×nh g©y ra (vÝ dô nh t¹p ©m lîng tö ho¸ ) th× ta cã thÓ gi¶m bít sè lîng bit
cÇn thiÕt ®Ó biÓu diÔn mét ¶nh ë møc ®é chÊt lîng vµ ®é dÔ hiÓu ®· cho, hay cã thÓ gi÷
nguyªn sè bit mµ c¶i thiÖn chÊt lîng vµ ®é dÔ hiÓu .
M«i trêng ®iÓn h×nh vÒ m· ho¸ ¶nh nh trªn h×nh 4.1. ¶nh digital ®îc m·
ho¸ ¶nh m· ho¸. Bé m· ho¸ nµy gäi lµ bé m· ho¸ nguån. §Çu ra bé m· ho¸ nµy lµ mét
chuçi bit gäi lµ ¶nh gèc.
ch¬ng 4: m· ho¸ ¶nh
168
Bé m· ho¸ kªnh biÕn chuçi bit nµy ra mét d¹ng thÝch hîp cho viÖc truyÒn qua
mét kªnh th«ng tin, th«ng qua mét d¹ng ®iÒu chÕ nµo ®ã. TÝn hiÖu ®· ®iÒu chÕ ®îc
truyÒn qua kªnh th«ng tin. Kªnh th«ng tin sÏ ®a vµo mét Ýt nhiÔu vµ trong bé m· ho¸
kªnh ph¶i tr÷ liÖu mét biÖn ph¸p söa lçi ®Ó kh¾c phôc t¹p ©m kªnh nµy. ë ®Çu thu, tÝn
hiÖu nhËn ®îc qua gi¶i ®iÒu chÕ vµ hoµn nguyªn thµnh chuçi bit nhê bé gi¶i m· kªnh.
Bé gi¶i m· ¶nh ®em chuçi bÝt hoµn nguyªn thµnh ¶nh cho hiÖn lªn mµn h×nh vµ in ra.
Kh¸c víi m«i trêng truyÒn tin ë h×nh 4.1, trong nh÷ng øng dông m· ho¸ ¶nh ®Ó gi¶m
lu tr÷, kh«ng cã kªnh th«ng tin . ë ®©y chuçi bit ë ®Çu ra bé m· ho¸ ¶nh ®îc lu tr÷
vµo m«i trêng lu tr÷ chê sau lÊy ra dïng.
Bé m· ho¸ ¶nh ë h×nh 4.1 cã ba phÇn tö c¬ b¶n (H×nh 4.2).
H×nh 4.2. Ba thµnh phÇn chÝnh trong m· ho¸ ¶nh.
PhÇn tö ®Çu tiªn vµ quan träng nhÊt lµm biÕn ® æi ¶nh vµo mét kh«ng gian (miÒn)
thÝch hîp nhÊt cho viÖc lîng tö ho¸ vµ g¸n tõ m·. VÒ thùc chÊt phÇn tö nµy quyÕt ®Þnh
xem c¸i g× ph¶i ®em m· ho¸. Algorit m· ho¸ ¶nh chia lµm ba lo¹i chÝnh, tuú theo ®Æc
trng nµo cña ¶nh ®îc m· ho¸. Lo¹i thø nhÊt gäi lµ bé m· ho¸ d¹ng sãng, cêng ®é ¶nh
Bé m· ho¸
¶nh
Bé m· ho¸
kªnh
Bé gi¶i m·
¶nh
Bé gi¶i m·
kªnh
Kªnh truyÒn
¶nh phôc
håi
¶nh gèc
H×nh 4.1. M«i trêng ®iÓn h×nh vÒ m· ho¸ ¶nh.
¶nh gèc BiÕn ®æi Lîng tö hãa G¸n tõ m· Chuçi bit
ch¬ng 4: m· ho¸ ¶nh
169
hay mét biÕn thiªn cña cêng ®é ¶nh, vÝ dô cêng ®é cña hai pixel kÒ nhau, ®îc m·
ho¸. Lo¹i thø hai, gäi lµ bé m· ho¸ hÖ sè biÕn ®æi (hay hµm biÕn ®æi) , ¶nh ®îc biÕn
®æi sang kh«ng gian kh¸c, ch¼ng h¹n biÕn ®æi Fourier hoÆc biÕn ®æi Cosin, nh vËy lµ
sang mét miÒn (domain) kh¸c víi miÒn cêng ®é, vµ c¸c hÖ sè biÕn ®æi ®îc m· ho¸.
Lo¹i thø ba gäi lµ bé m· ho¸ m« h×nh (model) tÝn hiÖu, ngêi ta m« h×nh ho¸ ¶nh hoÆc
mét m¶nh nµo ®ã cña ¶nh vµ c¸c th«ng sè cña m« h×nh ®îc m· ho¸. Sau ®ã ¶nh ®îc
tæng hîp tõ c¸c th«ng sè m« h×nh ®· m· ho¸. PhÇn tö thø hai lµ ®Ó lîng tö ho¸. §Ó biÓu
diÔn mét ¶nh víi mét sè bÝt h÷u h¹n, th× cêng ®é ¶nh, hÖ sè biÕn ®æi hay th«ng sè m«
h×nh ph¶i ®îc lîng tö ho¸. ViÖc lîng tö ho¸ bao gåm vi Öc g¸n møc lîng tö vµ c¸c
biªn quyÕt ®Þnh. PhÇn tö thø ba ®Ó g¸n tõ m· tøc lµ chuçi bÝt biÓu diÔn c¸c møc lîng tö.
Mçi phÇn tö ®Òu nh»m ®Ó khai th¸c sù d thõa trong ¶nh gèc vµ nh÷ng giíi h¹n
cña thiÕt bÞ hiÖn h×nh còng nh cña hÖ thÞ gi¸c con ngêi .
V× vËy ba phÇn tö liªn quan chÆt chÏ víi nhau. Ch¼ng h¹n nÕu phÇn tö biÕn ®æi
trong bé m· ho¸ lµm cho c¸c sè liÖu gi¶m sù t¬ng quan ®ñ møc th× u thÕ cña lîng tö
hãa vect¬ so víi lîng tö ho¸ v« híng gi¶m ®i. NÕu c¸c møc lîng tö trong bé lîng
tö ho¸ ®îc chän sao cho mçi møc ®îc sö dông víi x¸c suÊt nh nhau th× u thÕ cña tõ
m· cã ®é dµi biÕn ®æi so víi tõ m· cã ®é dµi cè ®Þnh gi¶m ®i.
1. Lîng tö ho¸.
1.1. Lîng tö ho¸ v« híng.
Gäi f lµ mét lîng v« híng liªn tôc, cã thÓ ®¹i biÓu cêng ®é mét pixel hoÆc
mét hÖ sè biÕn ®æi hay mét th«ng sè cña m« h×nh ¶nh. §Ó biÓu diÔn f b»ng mét sè lîng
bit h÷u h¹n, ta chØ dïng mét sè lîng h÷u h¹n møc lîng tö. Gi¶ sö cã L møc ®îc dïng
®Ó biÔu f. Qu¸ tr×nh g¸n mét gi¸ trÞ f cho mét trong L møc g äi lµ lîng tö ho¸ biªn ®é
hay gäi t¾t lµ lîng tö ho¸. NÕu mçi ®¹i lîng v« híng ®îc lîng tö ho¸ mét c¸ch ®éc
lËp th× qu¸ tr×nh gäi lµ lîng tö ho¸ v« híng. NÕu hai hoÆc trªn hai ®¹i lîng v« híng
kÕt hîp cïng lîng tö ho¸ th× qu¸ tr×nh gäi lµ lîng tö ho¸ vect¬ hay lîng tö ho¸ khèi.
Gäi fˆ lµ f ®· ®îc lîng tö ho¸.
irfQf ˆ ; ii dfd 1 (4.1)
Q=thuËt to¸n lîng tö ho¸.
ch¬ng 4: m· ho¸ ¶nh
170
ri = víi 1 i L lµ L møc lîng tö.
di = víi 0 i L lµ L møc quyÕt ®Þnh hay L bê quyÕt ®Þnh.
Theo (4.1) th× nÕu f r¬i vµo gi÷a d i-1 vµ di th× nã ®îc ¸nh x¹ vµo møc lîng tö r i .
NÕu ta ®· x¸c ®Þnh c¸c møc quyÕt ®Þnh vµ møc lîng tö th× qu¸ tr×nh lîng tö
ho¸ f lµ mét qu¸ tr×nh x¸c ®Þnh. Còng cã thÓ biÓu diÔn :
Q
effQf ˆ (4.2)
Trong ®ã eQ lµ sai sè lîng tö tÝnh theo :
ffe
Q
ˆ (4.3)
Sai sè lîng tö ho¸ eQ cßn gäi lµ t¹p ©m lîng tö . §¹i lîng e Q2 coi nh trêng
hîp ®Æc biÖt cña ®é ®o ®é mÐo ffd ˆ, lµ mét ®é ®o kho¶ng c¸ch gi÷a f vµ fˆ . Nh÷ng vÝ
dô kh¸c cña ffd ˆ, bao gåm ˆ ff vµ pp ff ˆ .
C¸c møc lîng tö vµ møc quyÕt ®Þnh thêng ®îc x¸c ®Þnh b»ng c¸ch tèi thiÓu
ho¸ mét tiªu chuÈn sai sè nµo ®ã dùa trªn ffd ˆ, ch¼ng h¹n nh ®é mÐo trung b×nh D :
00
0
0
ˆ
,
ˆ
, dffp
f
ffdffdED f
(4.4)
Ph¬ng ph¸p lîng tö ho¸ ch©n ph¬ng nhÊt lµ lîng tö ho¸ ®Òu trong ®ã c¸c
møc lîng tö (vµ møc quyÕt ®Þnh) c¸ch ®Òu nhau.
Li1
1
ii dd (4.5a)
Li1
2
1 i
i
dd
r
i (4.5b)
lµ kÝch thíc bíc nh¶y b»ng kho¶ng c ¸ch gi÷a hai møc lîng tö kÒ nhau hay hai møc
quyÕt ®Þnh kÒ nhau. VÝ dô vÒ lîng tö ho¸ ®Òu víi L=4 vµ f gi¶ thiÕt gåm gi÷a 0 vµ 1
®îc tr×nh bµy ë h×nh 4.3. T¹p ©m lîng tö e Q thêng phô thuéc tÝn hiÖu. Ch¼ng h¹n t¹p
©m lîng tö eQ cña bé lîng tö ho¸ ®Òu (trong h×nh 4.3) ®îc biÓu diÔn ë h×nh 4.4. Tõ
h×nh nµy thÊy r»ng eQ lµ hµm cña f vµ do ®ã nã phô thuéc tÝn hiÖu. Cã thÓ lµm cho t¹p
©m lîng tö eQ trong bé lîng tö ho¸ ®Òu trë thµnh kh«ng t¬ng quan b»ng c¸ch dïng kü
ch¬ng 4: m· ho¸ ¶nh
171
thuËt gi¶ t¹p ©m cña Robert . Nh sÏ thÊy trong tiÕt 3 phÐp gi¶i t¬ng quan cña nhiÔu
lîng tö ho¸ sÏ h÷u dông trong viÖc c¶i thiÖn chÊt lîng hÖ m· ho¸ ¶nh. Nã lµm thay ®æi
®Æc tÝnh cña sù xuèng cÊp ¶nh m· ho¸. Ngoµi ra cã thÓ lµm gi¶m t¹p ©m lîng tö ®· gi¶i
t¬ng quan b»ng c¸ch dïng algori t phôc håi ¶nh nh ch¬ng 3.
H×nh 4.3 : VÝ dô vÒ bé lîng tö ho¸ ®Òu. Sè møc lîng tö lµ 4, f n»m gi÷a 0 vµ 1, fˆ lµ f
®· lîng tö ho¸. C¸c møc lîng tö vµ bê quyÕt ®Þnh ®îc ký hiÖu lµ r i vµ di.
Tuy lîng tö ho¸ ®Òu lµ c¸ch tiÕp cËn tù nhiªn nhÊt, nhng nã kh«ng ph¶i lµ tèi
u. Gi¶ sö f tËp trung ë mét vïng nµo ®ã nhiÒu h¬n ë c¸c vïng kh¸c. Nh vËy g¸n nhiÒu
møc lîng tö cho vïng ®ã nhiÒu h¬n c¸c vïng kh¸c lµ hîp lý. Ta xem l¹i vÝ dô ë h×nh
4.3. NÕu f Ýt khi r¬i vµo gi÷a d0 vµ d1 th× møc lîng tö r1 Ýt dîc sö dông. S¾p xÕp c¸c
møc lîng tö r1, r2, r3, vµ r4 sao cho chóng ®Òu n»m gi÷a d 1 vµ d4 sÏ cã ý nghÜa h¬n.
Lîng tö ho¸ mµ c¸c møc lîng tö vµ møc quyÕt ®Þnh kh«ng c¸ch ®Òu gäi lµ lîng tö
ho¸ kh«ng ®Òu. ViÖc x¸c ®Þnh tèi u ri vµ di phô thuéc vµo tiªu chuÈn sai sè®îc sö
dông. Tiªu chuÈn thêng dïng nhÊt lµ sai sè qu©n ph¬ng tèi thiÓu MMSE*_ gi¶ thiÕt f
lµ mét biÕn ngÉu nhiªn cã hµm mËt ®é x¸c suÊt lµ p f(f0). Dïng tiªu chuÈn MMSE ta x¸c
®Þnh rk vµ dk b»ng c¸ch tèi thiÓu ho¸ ®é mÐo trung b×nh D, víi :
48
7
r
28
3
r
38
5
r
18
1
r
Bé lîng tö ho¸ ®Òuf fˆ
fˆ
f
00d 14
1
d 22
1
d 34
3
d 41 d
ch¬ng 4: m· ho¸ ¶nh
172
0
2
00
22
ˆ
0
ˆˆ
dffp
ffEeEffdED
ff
f
f
Q
(4.6)
Lu ý r»ng fˆ lµ mét trong L møc lîng tö tÝnh theo (4.1), ta cã thÓ ®em (4.6)
viÕt ra :
0
2
0
1
0
10
dffrfpD
i
L
i
d
df
f
i
i
(4.7)
§Ó t×m cùc tiÓu D :
L
k
d
d
LD
r
D
0
k
1k10
d
Lk10
(4.8)
Tõ (4.7) vµ (4.8) :
Lk
dffp
dffpf
r
k
k
k
k
d
d
o
f
f
d
df
f
k
1,
1
1
00
000
0 (4.9a)
11,
2
1 Lkrrd kk (4.9b)
0d (4.9c)
Ld (4.9d)
ch¬ng 4: m· ho¸ ¶nh
173
Ph¬ng tr×nh ®Çu trong (4.9) nãi lªn r»ng møc lîng tö r k lµ t©m quay (centroid)
cña pf(f0) trong kho¶ng dk-1 f dk .
Nh÷ng ph¬ng tr×nh cßn l¹i nãi lªn r»ng mø c quyÕt ®Þnh dk (trõ d0 vµ dL) lµ ®iÓm
chÝnh gi÷a hai møc lîng tö r k vµ rk+1 . Ph¬ng tr×nh (4.9) lµ bé ph¬ng tr×nh cÇn cho lêi
gi¶i tèi u. Víi mét sè hµm mËt ®é x¸c suÊt, trong ®ã cã c¸c mËt ®é : ®Òu, Gauss, vµ
Laplace, th× (4.9) còng lµ bé ph¬ng tr×nh ®ñ.
Gi¶i (4.9) lµ mét bµi to¸n phi tuyÕn. Bµi to¸n phi tuyÕn ®· ®îc gi¶i cho mét sè
hµm mËt ®é x¸c suÊt. C¸c lêi gi¶i khi p f(f0) lµ : ®Òu, Gauss, Laplace, nh trªn b¶ng 1.
Bé lîng tö ho¸ dùa trªn tiªu chuÈn MMSE ®îc gäi lµ bé lîng tö ho¸
Lloyd_Max.
Theo b¶ng 1, bé lîng tö ho¸ ®Òu lµ bé lîng tö ho¸ MMSE tèi u khi p f(f0) lµ
hµm mËt ®é x¸c suÊt ®Òu.
Víi nh÷ng mËt ®é x¸c suÊt kh¸c, lêi gi¶i tèi u lµ mét bé lîng tö ho¸ kh«ng
®Òu. H×nh 4.5 biÓu diÔn c¸c møc lîng tö vµ møc quyÕt ®Þnh tèi u øng víi hµm mËt ®é
x¸c suÊt Gauss cã ph¬ng sai lµ 1 vµ L=4.
CÇn ®¸nh gi¸ møc ®é c¶i thiÖn mµ bé lîng tö ho¸ MMSE tèi u ®em l¹i so víi
bé lîng tö ho¸ ®Òu. Ch¼ng h¹n xÐt mét hµm ®é x¸c suÊt Gauss cã gi¸ trÞ trung b×nh lµ 0
vµ ph¬ng sai lµ 1.
H×nh 4.4 : Minh ho¹ vÒ sù phô thuéc cña t¹p ©m lîng tö vµo tÝn hiÖu.
H×nh 4.6 biÓu diÔn mÐo trung b×nh D theo hµm cña sè møc lîng tö, ®êng liÒn
nÐt øng víi bé lîng tö ho¸ MMSE tèi u, ®êng vÏ chÊm øng víi bé lîng tö ho¸ ®Òu,
trong ®ã c¸c møc lîng tö r i ®îc chän ®èi xøng ®èi víi gèc to¹ ®é, c¸c møc quyÕt ®Þnh
cùc tiÓu vµ cùc ®¹i gi¶ thiÕt lµ - vµ , bíc lîng tö ®îc chän ®Ó ®é mÐo trung b×nh
D lµ cùc tiÓu.
ffˆeQ
1/8
1/8
f
13/41/21/4
ch¬ng 4: m· ho¸ ¶nh
174
B¶ng 4.1 . VÞ trÝ cña c¸c møc lîng tö vµ quyÕt ®Þnh ®èi víi bé lîng tö ho¸
Lloyd_Max. Víi hµm mËt ®é x¸ c suÊt ®Òu, gi¶ thiÕt p f(f0) ®Òu gi÷a –1 vµ 1. Víi hµm mËt
®é x¸c suÊt Gauss gi¶ thiÕt trung vÞ b»ng 0 vµ ph¬ng sai b»ng 1. Víi hµm mËt ®é x¸c
suÊt Laplace
pf(f0)=
0
2
2
2
f
e
víi = 1
§Òu Gauss Laplace
Bit ri d i ri d i ri d i
1
2
3
4
-0.5000 -1.0000
0.5000 0.0000
1.0000
-0.7500 -1.0000
-0.2500 -0.5000
0.2500 0.0000
0.7500 0.5000
1.0000
0.8750 -1.0000
-0.6250 -0.7500
-0.3750 -0.5000
-0.1250 -0.2500
0.1250 0.0000
0.3750 0.2500
0.6250 0.5000
0.8750 0.7500
1.0000
-0.9375 -1.0000
-0.8125 -0.8750
-0.6875 -0.7500
-0.5625 -0.6250
-0.4375 -0.5000
-0.3125 -0.3750
-0.1875 -0.2500
-0.0625 -0.1250
0.0625 0.0000
0.1875 0.1250
0.3125 0.2500
0.4375 0.3750
0.5625 0.5000
0.6875 0.6250
0.8125 0.7500
0.9375 0.8750
1.0000
-0.7979 -
0.7979 0.0000
-1.5104 -
-0.4528 -0.9816
0.4528 0.0000
1.5104 0.9816
-2.1519 -
-1.3439 -1.7479
-0.7560 -1.0500
-0.2451 -0.5005
0.2451 0.0000
0.7560 0.5005
1.3439 1.0500
2.1519 1.7479
-2.7326 -
-2.0690 -2.4008
-1.6180 -1.8435
-1.2562 -1.4371
-0.9423 -1.0993
-0.6568 -0.7995
-0.3880 -0.5224
-0.1284 -0.2582
0.1284 0.0000
0.3880 0.2582
0.6568 0.5224
0.9423 0.7995
1.2562 1.0993
1.6180 1.4371
2.0690 1.8435
2.7326 2.4008
-0.7071 -
0.7071 0.0000
-1.8304 -
-0.4198 -1.1269
0.4198 0.0000
1.8340 1.1269
-3.0867 -
-1.6725 -2.3796
-0.8330 -1.2527
-0.2334 -0.5332
0.2334 0.0000
0.8330 0.5332
1.6725 1.2527
3.0867 2.3769
-4.4311 -
-3.0169 3.7240
-2.1773 -2.5971
-1.5778 -1.8776
-1.1110 -1.3444
-0.7287 -0.9198
-0.4048 -0.5667
-0.1240 -0.2664
0.1240 0.0000
0.4048 0.2644
0.7287 0.5667
1.1110 0.9198
1.5778 1.3444
2.1773 1.8776
3.0169 2.5971
4.4311 3.7240
ch¬ng 4: m· ho¸ ¶nh
175
H×nh 4.5. VÝ dô vÒ bé lîng tö ho¸ Lloyd_Max. Sè møc lîng tö lµ 4, hµm mËt
®é x¸c suÊt lµ Gauss víi trung vÞ b»ng 0 vµ ph¬ng sai b»ng 1.
H×nh 4.6. So s¸nh ®é mÐo trung b×nh D =E[( fˆ -f)2] theo hµm cña sè møc lîng tö L
trong 2 trêng hîp :
§êng liÒn nÐt : bé lîng tö ho¸ Lloyd_Max (khi hµm mËt ®é x¸c suÊt lµ
Gauss, trung vÞ b»ng 0 vµ ph¬ng sai b»ng 1).
§êng vÏ chÊm : bé lîng tö ho¸ ®Òu. Trôc tung tÝnh theo 10 log 10D.
Bé
lîng tö ho¸
kh«ng ®Òu
1.5104
0.9816-0.9816
0.4528
-0.4528
-1.5104
f
f fˆ
fˆ
10
lo
g 10
D
Lîng tö
ho¸ ®Òu
Lîng tö ho¸
Lloyd_Max
2 4 8 16 32 64 128 L
(1bit) (2bit) (3bit) (4bit) (5bit) (6bit) (7bit)
0
-10
-20
-30
-40
ch¬ng 4: m· ho¸ ¶nh
176
Trªn h×nh 4.6 nÕu dïng tõ m· cã ®é dµi ®Òu ®Ó biÓu diÔn c¸c møc lîng tö t h× sù
tiÕt kiÖm bit lµ 0 ~ 1/2 bit khi L trong kho¶ng 2 (1 bit) vµ 128 (7 bit). Trong vÝ dô nµy
gi¶ thiÕt hµm mËt ®é x¸c suÊt p f(f0) lµ Gauss. Cã thÓ tiÕn hµnh ph©n tÝch t¬ng tù víi c¸c
hµm mËt ®é x¸c suÊt kh¸c, hµm mËt ®é x¸c suÊt cµng kh¸c xa hµm ph©n b è ®Òu th× u
thÕ cña lîng tö ho¸ kh«ng ®Òu so víi lîng tö ho¸ ®Òu cµng lín. Quan niÖm : “ bé lîng
tö ho¸ ®Òu lµ tèi u khi hµm mËt ®é x¸c suÊt ph©n bè ®Òu ” l¹i gîi ý cho ta mét c¸ch tiÕp
cËn kh¸c. §ã lµ, ta cã thÓ ¸nh x¹ f vµo g b»ng mét phÐp phi tuyÕn s ao cho pg(g0) lµ ®Òu,
ta ®em lîng tö ho¸ g b»ng mét bé lîng tö ho¸ ®Òu, sau ®ã l¹i thùc hiÖn phÐp ¸nh x¹
ngîc. Ph¬ng ph¸p nµy ®îc minh ho¹ trªn h×nh 4.7.
H×nh 4.7. Lîng tö ho¸ kh«ng ®Òu b»ng phÐp nÐn -d·n.
PhÐp phi tuyÕn nµy ®îc gäi lµ phÐp nÐn -d·n (companding). Theo lý thuyÕt x¸c
suÊt, mét lùa chän cña phÐp phi tuyÕn (hay phÐp nÐn -d·n) C[] ®Ó t¹o ra ®îc pg(g0)
®ång ®Òu lµ :
2
1
dxxpfCg
f
x
f (4.10)
pg(g0) nhËn ®îc ®ång ®Òu trong kho¶ng –1/2 g 1/2 .
Tuy (1.10) dÔ gi¶i h¬n hÖ ph¬ng tr×nh phi tuyÕn (1.9), hÖ ë h×nh 1.7 l¹i tèi thiÓu
ho¸ D’ :
2ˆ' ggED (4.11)
mµ mÐo D’ ë (4.11) kh«ng gièng D ë (4.6).
Trong tiÕt nµy ta ®· xÐt viÖc lîng tö ho¸ mét ®¹i lîng v« híng f. Trong m·
ho¸ ¶nh, ph¶i lîng tö ho¸ nhiÒu ®¹i lîng v« híng. Mét c¸ch tiÕp cËn lµ lîng tö ho¸
tõng c¸i ®éc lËp _ C¸ch nµy gäi lµ lîng tö ho¸ v« híng mét nguån vect¬. Gi¶ sö cã N
v« híng fi víi 1 i N vµ mçi v« híng ®îc lîng tö ho¸ ra L i møc. NÕu Li ®îc biÓu
diÔn b»ng mét luü thõa cña 2 vµ nÕu mçi møc lîng tö ®îc m· ho¸ víi mét sè bit nh
nhau (nghÜa lµ víi tõ m· cã ®é dµi ®Òu) th× quan hÖ gi÷a L i víi mét sè bit cÇn thiÕt B i lµ :
Phi tuyÕn Bé lîng tö
ho¸ ®Òu
Phi tuyÕn-1gˆgf fˆ
ch¬ng 4: m· ho¸ ¶nh
177
iBL 2 (4.12a)
B i = log2Li (4.12b)
Tæng sè bit B cÇn thiÕt ®Ó m· ho¸ N v« híng lµ :
N
i
iBB
1
(4.13)
Tõ (4.12) vµ (4.13) ®îc tæng sè møc lîng tö L :
B
N
i
iLL 2
1
(4.14)
XÐt (4.13) vµ (4.14) nhËn thÊy tæng sè bit B lµ tæng c¸c B i cßn tæng sè møc lîng
tö L lµ tÝch c¸c L i. NÕu cã mét sè bit cè ®Þnh B ®Ó m· ho¸ N v« híng b»ng phÐp lîng
tö ho¸ v« híng nguån vect¬ th× ph¶i ph©n phèi B cho N v« híng. ChiÕn lîc tèi u ®Ó
ph©n bæ bit phô thuéc tiªu chuÈn sai sè vµ hµm mËt ®é x¸c suÊt cña c¸c v« híng. ChiÕn
lîc tèi u thêng dïng lµ cho v« híng cã ph¬ng sai lín nhiÒu bit, v« híng cã
ph¬ng sai bÐ Ýt bit. VÝ dô : gi¶ sö cÇn tèi thiÓu ho¸ sai sè qu©n ph¬ng
N
i
ii ffE
1
2ˆ ®èi víi Bi (1 i N) trong ®ã ifˆ lµ kÕt qu¶ lîng tö ho¸ fi. NÕu c¸c v«
híng cã hµm mËt ®é x¸c suÊt gièng nhau chØ cã ph¬ng sai kh¸c nhau ta sÏ dïng mét
ph¬ng ph¸p lîng tö ho¸ nh nhau, ch¼ng h¹n dïng bé lîng tö ho¸ Lloyd_Max cho
tõng v« híng. Khi ®ã lêi gi¶i gÇn ®óng vÒ ph©n bæ bit lµ:
Ni
N
BB N
N
j
j
i
i
1log
2
1
/1
1
2
2
2
(4.15)
Trong ®ã i2 lµ ph¬ng sai cña v« híng fi . Tõ (4.15) suy ra :
Li = N
N
j
j
iNBBi
/1
1
/22
1 i N (4.16)
Theo (4.16) sè møc lîng tö cho fi tØ lÖ víi i , lµ ®é lÖch chuÈn cña fi . Tuy (4.15)
lµ mét lêi gi¶i gÇn ®óng víi mét sè gi¶ thiÕt nhÊt ®Þnh, nã vÉn lµ c¨n cø tham kh¶o trong
nh÷ng bµi to¸n ph©n bæ bit. B i trong (4.15) cã thÓ ©m vµ nãi chung kh«ng ph¶i lµ sè
nguyªn. Khi lîng tö ho¸ v« híng B i ph¶i lµ mét sè nguyªn kh«ng ©m. §ã lµ ®iÒu kiÖn
rµng buéc khi gi¶i c¸c bµi to¸n ph©n bæ bit trong thùc tÕ.
ch¬ng 4: m· ho¸ ¶nh
178
1.2 . Lîng tö ho¸ vect¬.
Trong tiÕt trªn, th¶o luËn vÒ lîng tö ho¸ v« híng mét v« híng vµ mét nguån
vect¬. Mét c¸ch tiÕp cËn kh¸c ®Ó m· ho¸ nguån vect¬ lµ ®em chia c¸c v« híng thµnh
nh÷ng khèi, xem mçi khèi nh mét ®¬n vÞ sau ®ã lîng tö ®ång thêi nh÷ng v« híng
nµy trong ®¬n vÞ ®ã. Nh vËy gäi lµ lîng tö ho¸ vect¬ hay lîng tö ho¸ khèi .
Gäi f = [f1, f2,..., fN]T lµ mét vect¬ M chiÒu gåm N v« híng fi cã gi¸ trÞ thùc, biªn
®é liªn tôc . Trong phÐp lîng tö ho¸ vect¬ f ®îc ¸nh x¹ vµo mét vect¬ M chiÒu kh¸c r
= [r1, r2,..., rN]T. Kh¸c víi f mµ c¸c phÇn tö cã biªn ®é liªn tôc, vect¬ r ®îc chän tõ L
møc lîng tö. Gäi fˆ lµ f ®· ®îc lîng tö ho¸, ta biÓu diÔn nã b»ng :
fˆ =VQ(f)=ri.fCi (4.17)
VQ lµ to¸n tö lîng tö ho¸ vect¬ ri víi 1 i N chØ L møc lîng tö vµ C i ®îc gäi lµ tÕ
bµo thø i . NÕu f n»m trong tÕ bµo C i , th× f ®îc ¸nh x¹ vµo ri. H×nh 4.8 cho mét vÝ dô
lîng tö ho¸ vect¬ khi N =2 vµ L = 9 . C¸c chÊm trªn h×nh lµ nh÷ng møc lîng tö, vµ
c¸c ®êng liÒn nÐt lµ ®êng biªn tÕ bµo .
Trong lîng tö ho¸ vect¬ tÕ bµo cã thÓ cã h×nh d¹ng, kÝch thíc bÊt kú. §ã lµ
®iÒu kh¸c biÖt víi lîng tö ho¸ v« híng, mµ tÕ bµo (miÒn g i÷a 2 møc quyÕt dÞnh kÒ
nhau) cã thÓ cã kÝch thíc bÊt kú nhng h×nh d¹ng cè ®Þnh .
H×nh 4.8 . VÝ dô lîng tö ho¸ vect¬. Sè v« híng trong mçi vect¬ lµ 2, sè
møc lîng tö lµ 9.
f1
f2
ch¬ng 4: m· ho¸ ¶nh
179
PhÐp lîng tö ho¸ vect¬ khai th¸c sù mÒm dÎo nµy. Còng nh trong trêng hîp
v« híng, ta ®Þnh nghÜa ®é mÐo ffd ˆ, lµ ®é ®o sù chªnh lÖch gi÷a f vµ fˆ .Mét vÝ dô
cña ffd ˆ, lµ eQTeQ trong ®ã t¹p ©m lîng tö eQ ®Þnh nghÜa theo :
ffVQffeQ ˆ (4.18)
C¸c møc lîng tö rI vµ bê c¸c tÕ bµo C I x¸c ®Þnh b»ng c¸ch lÊy cùc tiÓu 1 tiªu
chuÈn sai sè nµo ®ã, ch¼ng h¹n ®é mÐo trung b×nh D :
ffdED ˆ, (4.19)
NÕu ffd ˆ, lµ eQTeQ th× tõ (4.18) vµ (4.19) suy ra :
...
ˆˆ
..
ˆˆ
1 f
000
0000
0
L
i C
i
T
i
f
T
T
Q
T
Q
i
dffrfr
dffpffff
ffffEeeED
(4.20)
§é mÐo trung b×nh ë (4.20) lµ sai sè qu©n ph¬ng MSE vµ lµ d¹ng tæng qu¸t cña (4.7) .
¦u ®iÓm cña eQTeQ so víi lîng tö ho¸ v« híng mét nguån vect¬ lµ c¶i thiÖn
chÊt lîng. Lîng tö ho¸ vect¬ cho phÐp gi¶m thÊp ®é mÐo trung b×nh D khi gi÷ sè møc
lîng tö kh«ng ®æi, hay cho gi¶m sè møc lîng tö khi gi÷ ®é mÐo trung b×nh D kh«ng
®æi. Lîng tö ho¸ vect¬ c¶i thiÖn chÊt lîng so víi lîng tö ho¸ v« híng b»ng nhiÒu
c¸ch. C¸ch cã ý nghÜa nhÊt lµ khai th¸c mèi quan hÖ thèng kª gi÷a c¸c v« híng trong
cïng khèi.
§Ó minh ho¹viÖc lîng tö ho¸ vect¬ cã thÓ khai th¸c mèi quan hÖ thèng kª ta h·y
xÐt 2 vÝ dô. Trong vÝ dô thø nhÊt ta khai th¸c mèi quan hÖ tuyÕn tÝnh (tÝn
