Chương 4: Mã hóa ảnh

Chia sẻ: Lê Sĩ Năm | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

226
lượt xem 97
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu chính của mã hóa ảnh là làm sao trình bày ảnh với số bit 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 4: Mã hóa ảnh

ch¬ng 4: m· ho¸ ¶nh 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. 167
ch¬ng 4: m· ho¸ ¶nh ¶nh gèc Bé m· ho¸ Bé m· ho¸ ¶nh kªnh Kªnh truyÒn ¶nh phôc håi Bé gi¶i m· Bé gi¶i m· ¶nh kªnh H×nh 4.1. M«i trêng ®iÓn h×nh vÒ m· ho¸ ¶nh. 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«n g 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). ¶nh gèc BiÕn ®æi Lîng tö hãa G¸n tõ m· Chuçi bit 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 168
ch¬ng 4: m· ho¸ ¶nh 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¸. fˆ  Q f   r ; d i 1  f  d i (4.1) i Q=thuËt to¸n lîng tö ho¸. 169
ch¬ng 4: m· ho¸ ¶nh 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 : fˆ  Q f   f  e (4.2) Q Trong ®ã e Q lµ sai sè lîng tö tÝnh theo : e  fˆ  f (4.3) Q Sai sè lîng tö ho¸ e Q 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 d f , fˆ lµ mét ®é ®o kho¶ng c¸ch gi÷a f vµ fˆ . Nh÷ng vÝ   p dô kh¸c cña d f , fˆ bao gåm fˆ  f vµ fˆ  f p . 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 d f , fˆ ch¼ng h¹n nh ®é mÐo trung b×nh D :    D  E d f , fˆ     d f , fˆ p 0   f df f 0 0 (4.4) f   0 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. d d  1i  L (4.5a) i i 1 di  d i 1 r  1 i  L (4.5b) i 2  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ö e Q 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 e Q 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ö e Q trong bé lîng tö ho¸ ®Òu trë thµnh kh«ng t¬ng quan b»ng c¸ch dïng kü 170
ch¬ng 4: m· ho¸ ¶nh 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. f Bé lîng tö ho¸ ®Òu ˆf ˆf 7 r4 8 5 r3 8 3 r2 8 1 f r1 8 0d0 1d4 1 d1 1 d2 3 d3 4 2 4 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¸c h 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 d 0 vµ d1 th× møc lîng tö r 1 Ýt dîc sö dông. S¾p xÕp c¸c møc lîng tö r 1, 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 : 171
ch¬ng 4: m· ho¸ ¶nh    Q  D  E d fˆ  f  E e 2   E  fˆ  f    2     2 (4.6)   p f  fˆ  f 0  df 0 f 0  f   0 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 :  f 0 ri  f 0 2 df 0 d L i D   p (4.7) f i 1 f  d 0 i 1 §Ó t×m cùc tiÓu D : D 0 1k L r k D 0 1  k  L 1 (4.8) d k d   0 d  L Tõ (4.7) vµ (4.8) :  f 0 df 0 d k  f p 0 f f d k 1 r  0 , 1 k  L (4.9a) k  f 0 df 0 d k  p f f d o k 1 r r k 1 d k , 1  k  L 1 (4.9b) 2 d   (4.9c) 0 d (4.9d) L  172
ch¬ng 4: m· ho¸ ¶nh 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 d k-1  f  dk . Nh÷ng ph¬ng tr×nh cßn l¹i nãi lªn r»ng mø c quyÕt ®Þnh d k (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. eQ  ˆf  f 1/8 f 1/4 1/2 3/4 1 1/8 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. 173
ch¬ng 4: m· ho¸ ¶nh 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 2 f  0 2  pf(f0)= e víi  = 1 2 §Òu Gauss Laplace Bit ri di ri di ri di 1 -0.5000 -1.0000 -0.7979 - -0.7071 - 0.5000 0.0000 0.7979 0.0000 0.7071 0.0000 1.0000   2 -0.7500 -1.0000 -1.5104 - -1.8304 - -0.2500 -0.5000 -0.4528 -0.9816 -0.4198 -1.1269 0.2500 0.0000 0.4528 0.0000 0.4198 0.0000 0.7500 0.5000 1.5104 0.9816 1.8340 1.1269 1.0000   3 0.8750 -1.0000 -2.1519 - -3.0867 - -0.6250 -0.7500 -1.3439 -1.7479 -1.6725 -2.3796 -0.3750 -0.5000 -0.7560 -1.0500 -0.8330 -1.2527 -0.1250 -0.2500 -0.2451 -0.5005 -0.2334 -0.5332 0.1250 0.0000 0.2451 0.0000 0.2334 0.0000 0.3750 0.2500 0.7560 0.5005 0.8330 0.5332 0.6250 0.5000 1.3439 1.0500 1.6725 1.2527 0.8750 0.7500 2.1519 1.7479 3.0867 2.3769 1.0000 4 -0.9375 -1.0000   -0.8125 -0.8750 -2.7326 - -4.4311 - -0.6875 -0.7500 -2.0690 -2.4008 -3.0169 3.7240 -0.5625 -0.6250 -1.6180 -1.8435 -2.1773 -2.5971 -0.4375 -0.5000 -1.2562 -1.4371 -1.5778 -1.8776 -0.3125 -0.3750 -0.9423 -1.0993 -1.1110 -1.3444 -0.1875 -0.2500 -0.6568 -0.7995 -0.7287 -0.9198 -0.0625 -0.1250 -0.3880 -0.5224 -0.4048 -0.5667 0.0625 0.0000 -0.1284 -0.2582 -0.1240 -0.2664 0.1875 0.1250 0.1284 0.0000 0.1240 0.0000 0.3125 0.2500 0.3880 0.2582 0.4048 0.2644 0.4375 0.3750 0.6568 0.5224 0.7287 0.5667 0.5625 0.5000 0.9423 0.7995 1.1110 0.9198 0.6875 0.6250 1.2562 1.0993 1.5778 1.3444 0.8125 0.7500 1.6180 1.4371 2.1773 1.8776 0.9375 0.8750 2.0690 1.8435 3.0169 2.5971 1.0000 2.7326 2.4008 4.4311 3.7240   174
ch¬ng 4: m· ho¸ ¶nh Bé f lîng tö ho¸ ˆf kh«ng ®Òu ˆf 1.5104 0.4528 f -0.9816 0.9816 -0.4528 -1.5104 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. 0 -10 Lîng tö ho¸ ®Òu 10 log10 D -20 Lîng tö ho¸ -30 Lloyd_Max -40 2 4 8 16 32 64 128 L (1bit) (2bit) (3bit) (4bit) (5bit) (6bit) (7bit) 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. 175
ch¬ng 4: m· ho¸ ¶nh 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 p g(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. g gˆ f Phi tuyÕn Bé lîng tö Phi tuyÕn -1 fˆ ho¸ ®Òu 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 p g(g0) ®ång ®Òu lµ : 1 f  g  C f    p x dx 2 (4.10) f x   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’ : D'  E gˆ  g 2  (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 f i víi 1 i  N vµ mçi v« híng ®îc lîng tö ho¸ ra L i møc. NÕu L i ®î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µ : 176
ch¬ng 4: m· ho¸ ¶nh B L2 i (4.12a) B i = log2Li (4.12b) Tæng sè bit B cÇn thiÕt ®Ó m· ho¸ N v« híng lµ : N B   Bi (4.13) i 1 Tõ (4.12) vµ (4.13) ®îc tæng sè møc lîng tö L : N L   Li  2 B (4.14) i 1 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  E  fˆ  N  f i  ®èi víi B i (1 i  N) trong ®ã fˆi lµ kÕt qu¶ lîng tö ho¸ fi. NÕu c¸c v« 2 i 1 i  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µ: B 1  i2 Bi   log 2 1/ N 1 i  N (4.15) N 2  N 2   j   j 1  Trong ®ã i2 lµ ph¬ng sai cña v« híng fi . Tõ (4.15) suy ra : i Li = 2 B  2 B / N i 1/ N 1 i  N (4.16)  N    j     j 1  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Õ. 177
ch¬ng 4: m· ho¸ ¶nh 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.fCi (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 . f2 f1 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. 178
ch¬ng 4: m· ho¸ ¶nh 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 d f , fˆ lµ ®é ®o sù chªnh lÖch gi÷a f vµ fˆ .Mét vÝ dô   cña d f , fˆ lµ eQTeQ trong ®ã t¹p ©m lîng tö e Q ®Þnh nghÜa theo : eQ  fˆ  f  VQ  f   f (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 :    D  E d f , fˆ (4.19)   NÕu d f , fˆ lµ eQTeQ th× tõ (4.18) vµ (4.19) suy ra :    D  E eQT eQ  E  fˆ  f    fˆ  f  T    fˆ  f p   f 0 df 0 T    .. fˆ  f 0 0 f (4.20)  L    ... ri  f 0  ri  f 0 df 0 T i 1 f 0 Ci §é 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 e QTeQ 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Ýnh t¬ng quan). XÐt 2 nguån ngÉu nhiªn f1 vµ f2 cã hµm mËt ®é x¸c suÊt ®ång thêi p f 1 f2 f 1 '  , f 2' nh trªn h×nh 4.9a. Hµm mËt ®é x¸c suÊt ®ång thêi cã biªn ®é ®ång ®Òu vµ b»ng 1/2a 2 trong vïng g¹ch chÐo, b»ng kh«ng ë ngoµi vïng g¹ch chÐo. Hai hµm mËt ®é x¸c suÊt biªn p f  f1'  vµ 1   còng ®îc vÏ trªn h×nh. V× E[ f1,f2]  E[f1] E[f2] nªn f1 vµ f2 lµ t¬ng quan hay p f2 f 2 ' phô thuéc tuyÕn tÝnh. Gi¶ thiÕt ta lîng tö ho¸ riªng rÏ f1 vµ f2 , dïng lîng tö ho¸ v« híng vµ tiªu chuÈn MMSE. 179
ch¬ng 4: m· ho¸ ¶nh ' f 2' f 2 a a   p f 2 f 2' a f1' 1 -a 2a -a -a   p f1 f 1' 1 2a f1' -a a (a) f 2' f 2' a a f1' f1' -a a -a a -a -a -a -a (b) (c) H×nh 4.9. Minh ho¹ viÖc lî ng tö ho¸ vect¬ khai th¸c sù phô thuéc tuyÕn tÝnh cña c¸c v« híng trong vect¬ : (a) Hµm mËt ®é x¸c suÊt p f 1 f2 f 1 ' , f 2'  (b) C¸c møc lîng tö ho¸ (c¸c chÊm trªn h×nh) khi lîng tö ho¸v« híng. (c) C¸c møc lîng tö ho¸ (c¸c chÊm trªn h×nh) khi lîng tö ho¸vect¬. V× mçi v« híng f 1 vµ f2 ®Òu cã hµm mËt ®é x¸c suÊt ®Òu nªn bé lîng tö ho¸ v« híng tèi u lµ lîng tö ho¸ ®Òu. NÕu ta cho mçi v« híng cã 2 møc lîng tö th× c¸c møc lîng tö cña mçi v« hí ng lµ a/2 vµ -a/2 . Bèn (2x2) møc lîng tö hîp thµnh 4 180
ch¬ng 4: m· ho¸ ¶nh chÊm trªn h×nh 4.9b. Râ rµng lµ 2 trong sè 4 møc lîng tö lµ l·ng phÝ. Víi phÐp lîng tö ho¸ vect¬ ta chØ cã thÓ dïng 2 møc lîng tö nh trªn h×nh 4.9c. VÝ dô nµy cho thÊy r»ng lîng tö ho¸ vect¬ cho phÐp gi¶m sè møc lîng tö mµ kh«ng ph¶i hi sinh MSE. Ta cã thÓ lo¹i bá sù phô thuéc tuyÕn tÝnh gi÷a f 1 vµ f2 b»ng c¸ch ®em quay hµm mËt ®é x¸c suÊt ®i 45 0 theo chiÒu kim ®ång hå, kÕt qu¶ cña phÐp biÕn ®æi to¹ ®é tuyÕn tÝnh kh¶ nghÞch nµy ®îc biÓu diÔn trª n h×nh 4.10. Trong hÖ to¹ ®é míi g 1 vµ g2 kh«ng t¬ng quan, v× E[g 1,g2] = E[g 1] E[g2]. Trong hÖ to¹ ®é míi nµy cã thÓ ®Æt hai møc lîng tö vµo c¸c chÊm ë trªn h×nh b»ng c¸ch lîng tö ho¸ v« híng hai ®¹i lîng v« híng, vµ khi ®ã u thÕ cña lîng tö ho¸ve ct¬ kh«ng cßn n÷a. g 2’ a 2 g 1’  2a  2a a - 2 H×nh 4.10. KÕt qu¶ lo¹i trõ sù phô thuéc tuyÕn tÝnh gi÷a hai v« híng f 1 vµ f2 ë h×nh 4.9 khi thùc hiÖn phÐp biÕn ®æi tuyÕn tÝnh f 1 vµ f2. Lo¹i bá sù phô thuéc tuyÕn tÝnh lµm mÊt u thÕ cña phÐp lîng tö ho¸ vect¬. Nh vËy lµ phï hîp víi quan ®iÓm cho r»ng lîng tö ho¸ vect¬ cã thÓ khai th¸c sù phô thuéc tuyÕn tÝnh gi÷a c¸c v« híng trong vect¬. PhÐp lîng tö ho¸ vect¬ còng cã thÓ khai th¸c sù phô thuéc phi tuyÕn. Ta ®a ra mét vÝ dô minh ho¹. XÐt 2 biÕn ngÉu nhiªn f 1 vµ f2 vµ hµm mËt ®é x¸c suÊt ®ång thêi p f 1 f2 f 1 '  , f 2' ®îc biÓu diÔn trªn h×nh 4.11a. Hµm mËt x¸c suÊt vÉn lµ ®Òu víi biªn ®é b»ng 1/(8a 2) trong vïng g¹ch chÐo vµ b»ng kh«ng ngoµi vïng ®ã. Hµm mËt ®é x¸c suÊt biªn p f  f1'  vµ 1   còng ®îc vÏ trªn h×nh 4.11a. Tõ hµm mËt ®é x¸c suÊt ®ång thêi E[f 1,f2] = E[f1] p f2 f 2 ' E[f2] vµ do ®ã f 1 vµ f2 ®éc lËp tuyÕn tÝnh. Tuy vËy p  f , f   p  f  p  f  nªn f1 vµ f1 f 2 1 ' 2 ' f1 1 ' f2 2 ' f2 phô thuéc thèng kª. 181
ch¬ng 4: m· ho¸ ¶nh Khi mµ c¸c biÕn ngÉu nhiªn ®éc lËp tuyÕn tÝnh nhng phô thuéc thèng kª ta b¶o chóng phô thuéc phi tuyÕn. ' f 2' f 2 a 2a   p f 2 f 2' a -a a f1' 1 -2a -a 2a 4a -a -2a   p f1 f 1' 1 4a f1' -2a 2a (a) f 2' f 2' 2a 2a a a a f1' a f1' -2a -a 2a -2a -a 2a -a -a -2a -2a (b) (c) H×nh 4.11. Minh ho¹ viÖc lîng tö ho¸ vect¬ khai th¸c sù phô thuéc tuyÕn tÝnh gi÷a c¸c v« híng trong vect¬ : a) Hµm mËt ®é x¸c suÊt p f 1 f2 f 1 '  , f 2' . b) C¸c møc lîng tö (c¸c chÊm) khi lîng tö ho¸ v« híng . c) C¸c møc lîng tö (c¸c chÊm) khi lîng tö ho¸ vect¬. 182
ch¬ng 4: m· ho¸ ¶nh NÕu ta lîng tö ho¸ f 1 vµ f2 riªng rÏ, dïng tiªu chuÈn MSE vµ cho mçi v« híng 2 møc lîng tö, th× c¸c møc lîng tö tèi u cho mçi v« híng lµ -a vµ a. C¸c møc lîng tö tæng hîp trong trêng hîp ®ã lµ 4 chÊm trong h×nh 4.11b. §é mÐo trung b×nh D = E[eQTeQ] trong vÝ dô nµy lµ 5a 2/12. VÝ dô nµy cho thÊy r»ng dïng lîng tö ho¸ vect¬ cã thÓ lµm gi¶m MSE mµ kh«ng cÇn t¨ng sè møc lîng tö. Ta cã thÓ lo¹i bá phô thuéc phi tuyÕn gi÷a f 1 vµ f2 trong vÝ dô nµy b»ng mét thuËt to¸n phi tuyÕn kh¶ nghÞch. KÕt qu¶ cña mét thuËt to¸n nh vËy ®îc biÓu diÔn trªn h×nh 4.12. g 2' 2a -a g1' a -2a H×nh 4.12. KÕt qu¶ cña viÖc lo¹i bá sù phô thuéc tuyÕn tÝnh gi÷a hai v« híng f 1 vµ f2 ë h×nh 4.11. V× p g g g1' , g 2'   p g g1'  p g g 2'  nªn g1 vµ g2 ®éc lËp thèng kª. Trong nh÷ng 1 2 1 2 trêng hîp nµy cã thÓ ®Æt hai møc lîng tö vµo c¸c chÊm trªn h×nh b»ng c¸ch lîng tö ho¸ v« híng hai ®¹i lîng v« híng, vµ u thÕ cña lîng tö ho¸ vect¬ kh«ng cßn n÷a. Qua vÝ dô nµy thÊy r»ng lo¹i bá phô thuéc phi tuyÕn lµm gi¶m u thÕ cña lîng tö ho¸ vect¬. Nh vËy phï hîp víi quan niÖm cho r»ng lîng tö ho¸ vect¬ cã thÓ khai th¸c sù phô thuéc phi tuyÕn gi÷a c¸c v« híng trong vect¬. PhÐp biÕn ®æi tuyÕn tÝnh bao giê còng cã thÓ lo¹i bá sù phô thuéc tuyÕn tÝnh. VÒ sù phô thuéc phi tuyÕn ®«i khi ta còng lo¹i bá ®îc b»ng mét thuËt to¸n phi tuyÕn kh¶ nghÞch. NÕu ta lo¹i bá phô thuéc tuyÕn tÝnh hay phi tuyÕn b»ng mét thuËt to¸n phi tuyÕn kh¶ nghÞch tríc khi lîng tö ho¸ th× u thÕ cña lîng tö ho¸ vect¬ vÒ kh¶ n¨ng khai th¸c phô thuéc tuyÕn tÝnh hay phi tuyÕn sÏ kh«ng cßn n÷a. Nh vËy lµ ph¶i hÕt søc chó ý ®Õn quan hÖ chÆt chÏ gi÷a giai ®o ¹n biÕn ®æi vµ giai ®o¹n lîng tö ho¸ trong m· ho¸ ¶nh. NÕu nh giai ®o¹n biÕn ®æi lµm mÊt phô thuéc tuyÕn tÝnh hay phi tuyÕn gi÷a c¸c v« híng cÇn m· ho¸ th× ®Õn giai ®o¹n lîng tö ho¸ møc ®é c¶i thiÖn cña lîng tö ho¸ 183
ch¬ng 4: m· ho¸ ¶nh vect¬ so víi lîng tö ho¸ v« híng s Ï gi¶m sót,lµm cho lîng tö ho¸ vect¬ trë lªn kÐm hÊp dÉn. §iÒu ®ã nãi lªn mét phÇn t¹i sao trong bé m· ho¸ d¹ng sãng sù c¶i thiÖn do lîng tö ho¸ vect¬ ®em l¹i râ nÐt h¬n trong bé m· ho¸ phÐp biÕn ®æi. C¸c v« híng dïng trong bé m· ho¸ d¹ng sãng, ch¼ng h¹ n c¸c cêng ®é ¶nh, cã tÝnh t¬ng quan cao h¬n c¸c v« híng trong bé m· ho¸ phÐp biÕn ®æi, ch¼ng h¹n c¸c hÖ sè phÐp biÕn ®æi DCT. §iÒu nµy sÏ ®îc ph©n tÝch ë c¸c tiÕt 3 vµ 4. Ngoµi viÖc khai th¸c sù phô thuéc thèng kª lîng tö ho¸ vect¬ cßn cã thÓ khai th¸c sù t¨ng thø nguyªn, nghÜa lµ t¨ng sè v« híng trong vect¬. §Ó minh ho¹ ta xÐt 2 biÕn ngÉu nhiªn f 1vµ f2 cã hµm mËt ®é x¸c suÊt ®ång thêi ®Òu trong mét miÒn h×nh vu«ng cã diÖn tÝch A. Râ rµng lµ f 1 vµ f2 ®éc lËp thèng kª. Gi¶ sö sè møc lîng tö L rÊt lín vµ do ®ã kÝch thíc tÕ bµo nhá h¬n h×nh vu«ng trong ®ã hµm mËt ®é x¸c suÊt kh¸c 0. Tríc hÕt ta xÐt phÐp lîng tö ho¸ v« híng f 1 vµ f2. V× hµm mËt ®é x¸c suÊt cña f 1 vµ f2 lµ ®Òu nªn theo tiªu chuÈn MMSE, lîng tö ho¸ ®Òu lµ tèi u. ViÖc lîng tö ho¸ ®Òu f1 vµ f2 riªng rÏ ®a tíi nh÷ng møc lîng tö vµ tÕ bµo vÏ ë h×nh 4.13a. Trong trêng hîp lîng tö ho¸ v« híng tÕ bµo cã d¹ng h×nh vu«ng cã c¹nh a. NÕu ®em lîng tö ho¸ vect¬ f1 vµ f2 th× c¸c møc lîng tö vµ tÕ bµo nh trªn h×nh 4.13b – TÕ bµo cã d¹ng lôc gi¸c. Th«ng qua tÝnh to¸n cã thÓ chøng minh r»ng MSE trong trêng hîp lîng tö ho¸ vect¬ thÊp h¬n trêng hîp lîng tö ho¸ v« híng 4% nÕu møc lîng tö nh nhau. Còng cã thÓ chøng minh lµ sè møc lîng tö mµ lîng tö ho¸ vect¬ yªu cÇu bÐ h¬n sè møc cña lîng tö ho¸ v« híng 2% khi MSE nh nhau. Sù c¶i thiÖn nµy thêng nhá h¬n nhiÒu so víi møc c¶i thiÖn b»ng lîng tö ho¸ vect¬ khi khai th¸c sù phô thuéc thèng kª. Tuy vËy sù c¶i thiÖn sÏ nÐt h¬n nhiÒu khi thø nguyªn (nghÜa lµ sè v« híng trong vect¬) t¨ng lªn. Lu ý r»ng sù c¶i thiÖn thªm nµy vÉn ®¹t ®îc ngay c¶ khi c¸c v« híng trong khèi ®éc lËp thèng kª víi nhau. Sù c¶i thiÖn mµ lîng tö ho¸ vect¬ ®em l¹i trong mét sè trêng hîp cho phÐp m· ho¸ 1 v« híng díi 1 bit. NÕu ta m· ho¸ riªng rÏ tõng v« híng vµ cho mçi v« híng tèi thiÓu 2 møc lîng tö (nÕu dïng 1 møc lîng tö th× coi nh kh«ng m· ho¸) th× tû lÖ bit tèi thiÓu cã thÓ lµ 1 bit mçi v« híng. NÕu dïng lîng tö ho¸ vect¬, cã thÓ cho mçi v« híng 2 hoÆc trªn 2 møc lîng tö nÕu xÐt riªng rÏ, nhng nÕu n h×n tæng hîp l¹i th× tèc ®é bit sÏ thÊp h¬n mét bit mçi v« híng. §Ó minh ho¹ ®iÒu nµy ta trë l¹i vÝ dô h×nh 4.9. Khi lîng tö ho¸ v« híng (h×nh 4.9b) cho mçi v« híng 2 møc lîng tö th× tæng l¹i cÇn ®Õn 4 møc cho 2 v« híng, vµ tû lÖ bit lµ 1 bit cho mçi v« híng. Khi lîng tö ho¸ vect¬ (h×nh 4.10c) ta cho mçi v« 184
ch¬ng 4: m· ho¸ ¶nh híng 2 møc lîng tö khi xÐt tõng v« híng riªng rÏ vµ còng chØ cã 2 møc lîng tö cho c¶ hai v« híng. Trong trêng hîp nµy tû lÖ bit lµ 1 2 bit cho mçi v« híng. NÕu ta ®Þnh m· ho¸ cêng ®é pixel vµ mçi cêng ®é pixel tèi thiÓu ph¶i ®îc biÓu diÔn b»ng 2 møc lîng tö th× ph¬ng ph¸p lîng tö ho¸ vect¬ lµ c¸ch tiÕp cËn ®Ó cho tû lÖ bit thÊp h¬n 1 bit/pixel. ¦u thÕ cña lîng tö ho¸ vect¬ so víi lîng tö ho¸ v« híng còng ph¶i tr¶ gi¸ : gi¸ thµnh vÒ tÝnh to¸n vµ lu tr÷ khi lîng tö ho¸ vect¬ ®¾t h¬n nhiÒu so víi lîng tö ho¸ v« híng . PhÇn lín yªu cÇu tÝnh to¸n vµ lu tr÷ lµ ®Ó thiÕt kÕ vµ lu tr÷ s¸ch m· vµ ®Ó tra s¸ch m· ®Ó nhËn ra møc lîng tö ph¶I g¸n cho mét vect¬. H×nh 4.13. Minh ho¹ kh¶ n¨ng khai th¸c sù t¨ng thø nguyªn cña phÐp lîng tö. Trong trêng hîp nµy bªn lîng tö ho¸ vect¬ Ýt h¬n bªn lîng tö ho¸ v« híng 4%. a) Lîng tö ho¸ v« híng f 1 vµ f2 . b) Lîng tö ho¸ vect¬ f 1 vµ f2 185
ch¬ng 4: m· ho¸ ¶nh 1.3. ThiÕt kÕ s¸ch m· vµ algorit K -means. Khi lîng tö ho¸ vect¬ cÇn x¸c ®Þnh c¸c møc lîng tö ri vµ c¸c tÕ bµo C i . B¶ng liÖt kª c¸c møc lîng tö gäi lµ s¸ch m· lîng tö hay gäi t¾t lµ s¸ch m·. NÕu trong s¸ch cã L møc kîng tö th× ta gäi nã lµ s¸ch m· L møc. S¸ch m· ë ®Çu m¸y ph¸t dïng ®Ó lîng tö ho¸ mét nguån vect¬ thµnh 1 trong L møc lîng tö , cßn ë ®Çu m¸y thu dïng ®Ó x¸c ®Þnh møc lîng tö theo tõ m· nhËn ®îc. Theo sù tho¶ thuËn tríc cña bªn ph¸t vµ bªn thu, hai bªn dïng s¸ch m· nh nhau. ThiÕt kÕ s¸ch m· cho lîng tö ho¸ vect¬ lµ mét bµI to¸n khã. Kh«ng gièng trêng hîp lîng tö ho¸ v« híng, c¸c møc lîng tö bªn lîng tö ho¸ vect¬ lµ nh÷ng vect¬, cßn bê c¸c tÕ bµo còng kh«ng cßn lµ ®iÓm n÷a. Sù khã kh¨n vÒ thiÕt kÕ s¸ch m· lµ mét lý do ®Ó nh÷ng n¨m 70 vÒ tríc lîng tö ho¸ vect¬ kh«ng ®îc xÐt ®Õn khi m· ho¸ ¶nh vµ tiÕng nãi. C¸ch x¸c ®Þnh ri vµ CI tèi u phô thuéc tiªu chuÈn sai sè ®îc sö dông. Tiªu chuÈn MSE thêng dïng cã thÓ biÓu diÔn nh ®é mÐo trung b×nh D  E[d ( f , fˆ )] víi d ( f , fˆ )  ( fˆ  f ) T ( fˆ  f ) . ThiÕt kÕ tèi u s¸ch m· lµ bµi to¸n phi tuyÕn cao ®é. Muèn gi¶i bµi to¸n ®ã nªn khai th¸c 2 ®iÒu kiÖn cÇn cho lêi gi¶i bµi to¸n sau ®©y : §iÒu kiÖn 1 . §Ó 1 vect¬ f cã thÓ lîng tö ho¸ vÒ 1 trong nh÷ng møc lîng tö, bé lîng tö ho¸ tèi u ph¶i chän møc lîng tö ri cã mÐo nhá nhÊt gi÷a f vµ ri : VQ(f ) = ri nÕu vµ chØ nÕu d(f,ri)  d(f,rj) , i  j 1 j  L (4.21) §iÒu kiÖn 2 . Mçi møc lîng tö ri ph¶i tèi thiÓu ho¸ ®îc mÐo trung b×nh D trong Ci : Tèi thiÓu ho¸ E[d(f,ri) | f  Ci ] ®èi víi ri . (4.22) Møc ri tho¶ m·n (4.22) gäi lµ t©m quay cña C i. NÕu (4.21) kh«ng tho¶ m·n, th× cã thÓ lµm gi¶m mÐo trung b×nh D b»ng c¸ch ¸p ®Æt (4.21). NÕu (4.22) kh«ng tho¶ m·n, cã thÓ lµm gi¶m D b»ng c¸ch ¸p ®Æt (4.22). Hai ®iÒu kiÖn trªn lµ ®iÒu kiÖn cÇn cho lêi gi¶i tèi u. §iÒu kiÖn 1 ®Þnh ra 1 quy t¾c ®Ó lîng tö ho¸ f mµ kh«ng sö dông C i mét c¸ch   têng minh. Nãi c¸ch kh¸c ®é mÐo d f , fˆ cïng víi tÊt c¶ møc lîng tö ri , víi 1  i  186