Xử lý ảnh_Chương 4 Mã hóa ảnh

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Ò l­u tr÷. VÝ dô gi¶m l­u 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 l­u tr÷ ¶nh cña ch­¬ng tr×nh vò trô hay l­u tr÷ ¶nh lÞch sö (kh«ng thÓ cã l¹i ®­îc) ph¶i l­u 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, nh­ng 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, nh­ng 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 l­u tr÷, kh«ng cã kªnh th«ng tin . ë ®©y chuçi bit ë ®Çu ra bé m· ho¸ ¶nh ®­îc l­u tr÷ vµo m«i tr­êng l­u 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 tr­ng 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, nh­ng 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) L­u ý 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.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ú nh­ng 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