Nén Ảnh part 1

Chia sẻ: Asg Ahsva | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

107
lượt xem 22
download

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

Chỉ dẫn Nén ảnh là một kỹ thuật mã hoá hiệu suất cao ảnh số nhằm làm giảm số bit cần cho biểu diễn ảnh. Chức năng của kỹ thuật này là giảm độ lớn dữ liệu phải lưu trữ cùng với thời gian truyền trong khi vẫn giữ nguyên chất lượng của ảnh. Để đánh giá sự cần thiết của nén ảnh, chúng ta xem xét về yêu cầu bộ nhớ và thời gian truyền khi dùng một modem 9600 baud (bit/s) cho các ảnh sau đây: ■ Một ảnh 512  512 điểm, 8 bit cho một...

Chủ đề:

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

Lưu

Nội dung Text: Nén Ảnh part 1

Ch¬ng 13 NÐn d÷ liÖu ¶nh 13.1 ChØ dÉn NÐn ¶nh lµ mét kü thuËt m· ho¸ hiÖu suÊt cao ¶nh sè nh»m lµm gi¶m sè bit cÇn cho biÓu diÔn ¶nh. Chøc n¨ng cña kü thuËt nµy lµ gi¶m ®é lín d÷ liÖu ph¶i lu tr÷ cïng víi thêi gian truyÒn trong khi vÉn gi÷ nguyªn chÊt lîng cña ¶nh. §Ó ®¸nh gi¸ sù cÇn thiÕt cña nÐn ¶nh, chóng ta xem xÐt vÒ yªu cÇu bé nhí vµ thêi gian truyÒn khi dïng mét modem 9600 baud (bit/s) cho c¸c ¶nh sau ®©y: ■ Mét ¶nh 512  512 ®iÓm, 8 bit cho mét ®iÓm, ¶nh møc x¸m yªu cÇu 2,097,152 bit cho lu gi÷ vµ mÊt 3.64 phót ®Ó truyÒn. ■ Mét ¶nh mµu RGB cã cïng c¸c bíc xö lý nh trêng hîp trªn yªu cÇu xÊp xØ 6 triÖu bÝt cho lu tr÷ vµ mÊt gÇn 11 phót ®Ó truyÒn. ■ Mét phim ©m b¶n cã kÝch thíc 24  36 mm (35 mm) chia b»ng c¸c kho¶ng c¸ch nhau 12 µm, vµo kho¶ng 3000  2000 ®iÓm, 8 bit cho mét ®iÓm, yªu cÇu 48 triÖu bit cho lu gi÷ ¶nh vµ 83 phót ®Ó truyÒn. Mét phim ©m b¶n mµu sÏ yªu cÇu mét sè lín gÊp ba lÇn cho lu gi÷ vµ truyÒn. Râ rµng, viÖc truyÒn vµ lu gi÷ c¸c ¶nh sÏ cã nhiÒu vÊn ®Ò. Cã rÊt nhiÒu vÝ dô kh¸c mµ sÏ dÔ dµng lµm s¸ng tá vai trß cña nÐn ¶nh, vµ rÊt cã nhiÒu nghiªn cøu tËp trung vµo lÜnh vùc nµy. Fax, mét tµi liÖu ®å ho¹ ®îc truyÒn qua ®êng d©y ®iÖn tho¹i, nÐn d÷ liÖu ¶nh y häc, truyÒn h×nh lµ mét vµi trong sè nhiÒu øng dông tiÒm tµng cña nÐn ¶nh. Sù ph¸t triÓn cña kü thuËt vi ®iÖn tö vµ sù ph¸t triÓn cña rÊt nhiÒu øng dông th¬ng m¹i dÉn d¾t sù ph¸t triÓn cho c¸c tiªu chuÈn vµ phÇn cøng cña bé nÐn ¶nh theo thêi gian thùc. NÐn ¶nh lµ ®¹t ®îc b©õng c¸ch lo¹i bá c¸c phÇn thõa trong ¶nh. C¸c phÇn thõa nµy cã thÓ ë trong miÒn kh«ng gian, miÒn phæ, hoÆc lµ phÇn thõa trong thêi gian. ■ PhÇn thõa kh«ng gian lµ kÕt qu¶ do mèi quan hÖ t¬ng quan gi÷a c¸c ®iÓm gÇn nhau. 309
■ PhÇn thõa phæ lµ kÕt qu¶ do mèi t¬ng quan gi÷a c¸c mÆt ph¼ng mµu kh¸c nhau. ■ PhÇn thõa thêi gian lµ kÕt qu¶ mèi t¬ng quan cña c¸c khung kh¸c nhau mét d·y c¸c ¶nh nh trong truyÒn h×nh . Trong ch¬ng nµy t«i sÏ tr×nh bµy víi c¸c b¹n mét sè thuËt to¸n nÐn ¶nh cã kÕt qu¶ tèt ®îc thõa nhËn réng r·i. Chóng ta sÏ ph¸t triÓn thuËt to¸n thµnh m· ch¬ng tr×nh C, sau ®ã kiÓm tra kÕt qu¶ cña c¸c kü thuËt nµy qua c¸c vÝ dô ch¹y thö. B¹n sÏ cã nhiÒu kinh nghiÖm b»ng c¸ch tù ch¹y c¸c ch¬ng tr×nh nµy. 13.2 M· thèng kª Nh÷ng ¶nh mµ chóng ta thu nhËn ®îc m· ho¸ vµ lu gi÷ díi d¹ng "m· tù nhiªn". Mét møc x¸m cña gi¸ trÞ ®îc m· ho¸ b»ng 8 bit nhÞ ph©n b»ng nhau. VÝ dô mét møc x¸m gi¸ trÞ 6 ®îc m· ho¸ lµ 0000 0110. Mét sù s¾p xÕp m· ho¸ lu©n phiªn nhau ®îc dïng trong m· møc x¸m. Lo¹i m· nµy cã ®Æc tÝnh lµ bÊt kú hai tõ m· liÒn nhau nµo còng chØ kh¸c nhau mét vÞ trÝ. B¶ng 13.1 tr×nh bµy hai kiÓu m· kh¸c nhau cho mét tÝn hiÖu mÉu cã gi¸ trÞ vµo kho¶ng tõ 0 ®Õn 7. Mét kiÓu cho ta thÊy r»ng tÝn hiÖu kh«ng nhÊt thiÕt ph¶i cã gi¸ trÞ thùc sù tõ 0 ®Õn 7, nhng ph¶i cã 8 møc riªng biÖt. B¶ng 13.1 C¸c m· kho¶ng c¸ch b»ng nhau Vµo M· tù M· møc nhiªn x¸m 0 000 111 1 001 110 2 010 100 3 011 101 4 100 001 5 101 000 6 110 010 7 111 011 Nh÷ng lo¹i m· nµy thêng gäi lµ m· kho¶ng c¸ch b»ng nhau. M· kho¶ng c¸ch b»ng nhau kh«ng ®îc dïng trong trong thèng kª d÷ liÖu. Sù thõa nhËn nµy ®îc t¹o ra khi ta coi r»ng tÊt c¶ c¸c møc x¸m (hoÆc gi¸ trÞ tÝn hiÖu chãi) cã cïng sè lÇn xuÊt hiÖn trong ¶nh. NÕu ®iÒu nµy kh«ng ®óng, d¹ng m· nµy kh«ng ph¶i tèt nhÊt. NÕu chóng ta ph¸t triÓn mét m· 310
mµ mét sè Ýt bÝt h¬n ®îc kÝ hiÖu cho c¸c tõ m· biÓu diÔn c¸c møc x¸m cã kh¶ n¨ng xuÊt hiÖn cao h¬n, th× trung b×nh ®é dµi tõ m· sÏ nhá nhÊt vµ lo¹i m· mµ chóng ta võa ph¸t triÓn lµ c¬ b¶n cho m· phÇn thõa tèi thiÓu. TÊt c¶ c¸c lo¹i m· nµy ®îc biÕt víi tªn m· cã ®é dµi thay ®æi hoÆc ®«i khi gäi lµ m· entropy. C©u hái ®Æt ra cho chóng ta lóc nµy lµ : ■ ChiÒu dµi tõ m· trung b×nh tèi thiÓu mµ cã thÓ dïng gi¶i m· ®Ó söa l¹i m· chÝnh x¸c lµ g×? ■ Lµm c¸ch nµo chóng ta t¹o ra m· nµy? C©u tr¶ lêi cho c©u hái ®Çu tiªn cã thÓ t×m thÊy trong lý thuyÕt th«ng tin. NÕu ta cho r»ng mét møc x¸m g cña x¸c suÊt p(g) ®îc cho b»ng tõ m· dµi L(g) bit. ChiÒu dµi tõ m· trung b×nh, trong mét ¶nh møc x¸m 8 bit, ®îc cho bëi 255 L   p ( g ) L( g ) bit/ pixel (13.1) 0 Mét thõa nhËn hîp lý n÷a cã thÓ suy ra lµ sù kiÖn cã sè lÇn xuÊt hiÖn Ýt, th× sÏ cung cÊp nhiÒu th«ng tin h¬n sù kiÖn sè lÇn xuÊt hiÖn nhiÒu h¬n. Sù thõa nhËn nµy dÉn chóng ta ®Õn mèi quan hÖ 1 (13.2) L( g )  log 2 p ( g ) C¬ sè 2 dïng khi L(g) ®îc cho díi d¹ng ®¬n vÞ nhÞ ph©n hoÆc bit. ChiÒu dµi tõ nhá nhÊt mµ cã thÓ ®îc dïng cho bëi 255 Lmin    p ( g ) log 2 p ( g ) bÝt/pixel (13.3) g 0 BiÓu thøc nµy gäi lµ entropy cña tÝn hiÖu. Entropy th× kh«ng bao giê ©m v× p(g) n»m trong kho¶ng [0,1]. §¹o hµm cña biÓu thøc entropy cã thÓ t×m thÊy trong c¸c s¸ch nãi vÒ tin häc hoÆc th«ng tin. Chó ý r»ng cho mét ¶nh 256 møc x¸m mµ tÊt c¶ c¸c møc cã kh¶ n¨ng xuÊt hiÖn b»ng nhau khi dïng biÓu thøc (13.3) chóng ta cã: 255 1 1 Lmin   bit/pixel log 2 ( )8 256 256 0 §iÒu nµy cã nghÜa lµ mét m· cã ®é dµi b»ng nhau cã thÓ dïng trªn mét ¶nh mµ cã hµm ph©n bè cêng ®é s¸ng ®ång ®Òu. C©u tr¶ lêi cho c©u hái thø hai ®Ò cËp ®Õn m· cã phÇn thõa nhá nhÊt (m· tèi u) ®îc Huffman t×m ra. Lo¹i m· nµy gäi lµ m· Huffman vµ ®îc ¸p dông réng r·i trong c¸c kü thuËt m· ho¸ b»ng phÇn cøng còng 311
nh b»ng phÇn mÒm trong c¸c øng dông th¬ng m¹i. B©y giê chóng ta sÏ xem xÐt s¬ ®å m· ho¸ Huffman. ThuËt to¸n m· ho¸ Huffman tu©n theo c¸c giíi h¹n sau: 1. Kh«ng cã hai th«ng b¸o nµo cã sù s¾p xÕp cña tõ m· gièng nhau. 2. Tõ m· cña th«ng b¸o ®îc m· hãa theo c¸ch mµ kh«ng cÇn mét sù chØ dÉn nµo thªm ®Ó chØ ra ®©u lµ n¬i b¾t ®Çu vµ ®©u lµ n¬i kÕt thóc cña tõ m·. H¹n chÕ thø hai chØ ra r»ng kh«ng cã th«ng b¸o nµo ®îc m· ho¸ theo c¸ch mµ khi tõ m· xuÊt hiÖn, bit nèi bit, nh lµ mét phÇn cña tõ m· lín h¬n. VÝ dô, 01, 102, vµ 202 lµ c¸c tõ m· hîp lÖ. Mét d·y cña c¸c tõ m· xuÊt hiÖn cã d¹ng 1111022020101111102 cã thÓ t¸ch ra thµnh 111-102- 202-01-01-111-102. TÊt c¶ c¸c vÊn ®Ò mµ chóng ta cÇn quan t©m khi gi¶i m· lµ bé m· gèc. NÕu nh mét bé m· bao gåm 11, 111, 102, 02 th× khi mét th«ng b¸o b¾t ®Çu vãi 11, ta sÏ kh«ng biÕt liÖu ®©y lµ th«ng b¸o 11 hay ®©y lµ phÇn b¾t ®Çu cña th«ng b¸o 111. NÕu mét th«ng b¸o 11102 xuÊt hiÖn th× ta sÏ kh«ng biÕt liÖu ®©y lµ 111-02 hoÆc lµ 11-102 ®îc truyÒn ®i. M· Huffman ®îc m· ho¸ theo hai h¹n chÕ trªn ®©y vµ gäi lµ m· cã ®é d thõa tèi thiÓu hay gäi lµ m· tèi u. Ph¬ng ph¸p m· ho¸ nµy theo hai bíc: bíc thu gän vµ bíc më réng. §Ó xem xÐt ph¬ng ph¸p m· ho¸ nµy ta coi r»ng c¸c th«ng b¸o ®Ó x©y dùng tõ m· ®îc s¾p xÕp theo thø tù x¸c suÊt xuÊt hiÖn gi¶m dÇn. p(0)  p(1)  p(2)  ...  p(N - 1) ë ®©y N lµ sè cña c¸c th«ng b¸o. Nh t«i ®· chØ ra ban ®Çu, cho bé m· ho¸ tèi u th× ®é dµi cña tõ m· ®îc x¾p xÕp theo thø tù L(0)  L(1)  L(2)  ...  L(N - 1) C¸c bíc díi ®©y tr×nh bµy gi¶i thuËt m· ho¸ Huffman. Gi¶i thuËt nµy, còng nh phÇn lín c¸c gi¶i thuËt kh¸c trong cuèn s¸ch nµy, ®îc ph¸t triÓn bëi chÝnh t¸c gi¶. 13.2.1 Gi¶i thuËt thu gän C¸c bíc cña gi¶i thuËt thu gän ®îc tr×nh bµy tèt nhÊt theo c¸c bíc sau ®©y: §Æt M = N vµ coi ®©y lµ mét m¶ng tuyÕn tÝnh cã kÝch thíc N - 2. Cho i = 0 ®Õn N - 3 lÆp l¹i c¸c bíc sau: { Céng p(M) vµ p(M - 1). Thay p(M - 1) b»ng kÕt qu¶ thu ®îc. X¸c ®Þnh vÞ trÝ, loc, trong M - 1 vÞ trÝ ®Çu tiªn cña m¶ng p trong ®ã p(M - 1) > p(loc). 312
§Æt temp = p(M - 1). ChuyÓn c¸c gi¸ trÞ tõ p(loc) ®Õn p(M - 2) xuèng mét vÞ trÝ. §Æt gi¸ trÞ trung gian vµo loc. Lu gi¸ trÞ trung gian trong m¶ng tuyÕn tÝnh v theo v(N - 2 - i) = loc Gi¶m M ®i mét gi¸ trÞ. } §Ó hiÓu gi¶i thuËt thu gän ta xem xÐt vÝ dô sau. Gi¶ sö r»ng kh¶ n¨ng xuÊt hiÖn cña c¸c th«ng tin lµ: p = {0.25, 0.25, 0.125, 0.125, 0.0625, 0.0625, 0.0625, 0.0625} Gi¶i thuËt thu gän ®îc tr×nh bµy ë trªn, cho trêng hîp nµy, trong h×nh 13.1, tõ ®ã chóng ta cã thÓ viÕt:  2 1  v   4  3 6  5   1 0.25 0.25 0.25 0.25 0.25 0.5 0.5 0.25 2 0.25 0.25 0.25 0.25 0.25 0.5 0.25 3 0.125 0.125 0.125 0.25 0.25 0.125 4 0.25 0.125 0.125 0.125 0.125 5 0.125 0.125 0.0625 0.0625 6 0.125 0.0625 0.0625 7 0.0625 8 0.0625 H×nh 13.1 Gi¶i thuËt thu gän. M¶ng tuyÕn tÝnh v ®îc dïng ®Ó x©y dùng m· ho¸ Huffman theo bíc më réng ®îc tr×nh bµy ë díi ®©y. 13.3.2 Bíc më réng Bíc gi¶i thuËt nµy cã thÓ tr×nh bµy theo c¸c bíc sau: 313
1) G¸n c¸c gi¸ trÞ ban ®Çu cho mét m¶ng H theo: 0  H (1)      H (2 )  1  0  H (3)     H  0  .  .  .     .  .  0 H ( N )    Chó ý lµ phÇn tö thø hai b»ng 1 cßn c¸c phÇn tö kh¸c b»ng 0. VÐc t¬ tuyÕn tÝnh v = [v[1] v[2] v[3] ... v[N - 2]]T ®îc tÝnh trong bíc thu gän. Chó ý lµ vÞ trÝ cña c¸c phÇn tö ®îc cho b»ng 1,2,3 ... 2) §Æt M = 2 vµ i = 1. 3) Lu phÇn tö ë vÞ trÝ v[i] trong m¶ng H vµo mét biÕn trung gian temp. temp = H[v(i)] 4) DÞch chuyÓn c¸c phÇn tö c¸c phÇn tö ë vÞ trÝ díi H[v(i)] mét vÞ trÝ lªn phÝa trªn. ChÌn gi¸ trÞ 0 vµo vÞ trÝ cuèi cïng. 5) Sao chÐp temp tíi vÞ trÝ thø M trong H. 6) DÞch tr¸i H(M) mét bÝt. 10 0 1 0 1 0 1 0 1 0 1 0 21 10 1 1 1 1 1 1 1 1 1 1 3 11 0 0 0 0 0 1 0 0 1 0 0 1 0 4 0 1 01 0 0 1 1 0 1 1 0 1 1 5 01 1 0 0 0 0 0 0 0 0 1 0 6 0 0 1 00 1 0 0 0 1 1 7 00 1 1 0 0 0 0 8 0 0 0 1 H×nh 13.2 Gi¶i thuËt më réng. 7) H[M + 1] = H[M] + 1. 8) T¨ng M vµ i lªn mét. 9) NÕu i  (N - 2) quay l¹i bíc thø ba. 314
NÕu kh«ng th× ®· hoµn thµnh, vµ m· n»m trong b¶ng H. C¸c bíc trªn gi¶i thÝch qua h×nh 13.2 dïng vÝ dô h×nh 13.1. C¸c bíc trªn ®îc lËp ra bëi Huffman. Lu vµ Chen ®· nhËn ra r»ng thuËt to¸n cña Huffman kh«ng ph¶i lóc nµo còng t¹o ra mét m· cã ®é dµi ®¬n diÖu t¨ng dÇn qua vÝ dô cña hä díi ®©y: Xem xÐt kh¶ n¨ng xuÊt hiÖn th«ng tin díi ®©y: 0.5 0.1  0.1 P  0.1 0.1  0.1 Theo gi¶i thuËt thu gän ë trªn chóng ta cã 2 2 v  3  2 vµ t¹o bé m· 0  101    1000 H  1001 110    111  Bé m· trªn kh«ng tho¶ m·n ®iÒu kiÖn vÒ chiÒu dµi cña tõ m· ®¬n ®iÖu t¨ng dÇn; tuy nhiªn, bé m· nµy cã thÓ sö dông nÕu nã tho¶ m·n ®iÒu kiÖn cã kh¶ n¨ng gi¶i m· ®îc. Lçi nµy cã thÓ söa ®îc b»ng mét thay ®æi nhá theo Lu vµ Chen trong bíc thø ba tõ p(M - 1)  p(loc) p(M - 1) > p(loc) thµnh Theo ph¬ng ph¸p nµy cho ta kÕt qu¶ 315
1  2 v  2  2 vµ t¹o ra mét bé m· 1  001    010  H  011  0000   0001 Chó ý lµ thuËt to¸n Lu vµ Chen t¹o ra bé m· th× hoµn thiÖn h¬n thuËt to¸n m« t¶ ë trªn. Ch¬ng tr×nh díi ®©y t¹o ra bé m· dïng c¸c bíc thu gän vµ më réng ë trªn. Ch¬ng tr×nh nµy sö dông thuËt to¸n Lu vµ Chen m« t¶ ë trªn. Ch¬ng tr×nh còng tÝnh trung b×nh ®é dµi tõ. Ch¬ng tr×nh kh«ng dïng trªn ¶nh, mµ chØ minh ho¹ c¸c bíc thùc hiÖn viÖc sinh m· Huffman. Chó ý ®iÒu kiÖn dïng trong bíc 3 cña qu¸ tr×nh thu nhá ®îc thay b»ng ®iÒu kiÖn cña Lu vµ Chen. Ch¬ng tr×nh 13.1 Ch¬ng tr×nh vÝ dô sinh m· Huffman. /*Program 13.1 "HUFFMAN.C". Example program for generating the Huffman code.*/ /* Example program to demonstrate the algorithm for the generation procedure of the Huffman code. */ #include #include /*float p[]={0.2, 0.18, 0.1, 0.1, 0.1, 0.06, 0.06, 0.04, 0.04, 0.04, 0.04, 0.03, 0.01}; int N=13;*/ float p[]={0.5,0.1,0.1,0.1,0.1,0.1}; int N=6; void main() 316
{ int i,M,j,loc; unsigned char v[11],L[13],code[13]; unsigned char ctemp,Ltemp; float temp,sum,pt[13]; for(j=0;j
code[1]=1; M=1; for(i=0; i
§é dµi tõ trung b×nh ®îc tÝnh bëi c«ng thøc (13.1). Chó ý r»ng ch¬ng tr×nh còng tÝnh ®é dµi c¸c bit cña mçi m· vµ ®é dµi tõ trung b×nh. §é dµi sÏ m· cÇn thiÕt cho viÖc m· ho¸ vµ gi¶i m· c¸c tÝn hiÖu. Bµi t©p 13.1 1. Ch¹y ch¬ng tr×nh 13.1 dïng vÝ dô cho trong tµi liÖu cña Huffman: p = {0.2, 0.18, 0.1, 0.1, 0.1, 0.06, 0.06, 0.04, 0.04, 0.04, 0.04, 0.03, 0.01} 2. §æi gi¶ thiÕt: if (p[M - 1]  p[j] thµnh if (p[M - 1] > p[j]) trong ch¬ng tr×nh. Ch¹y ch¬ng tr×nh vµ so s¸nh víi bé m· cho bëi Lu vµ Chen. 3. Dïng vÝ dô cho bëi Lu vµ Chen, chó ý sù kh¸c nhau trong chiÒu dµi tõ m· vãi hai ®iÒu kiÖn kh¸c nhau. NhiÖm vô tiÕp theo cña chóng ta thËt râ rµng. Chóng ta cÇn viÕt mét ch¬ng tr×nh C ®Ó m· ho¸ vµ gi¶i m· ¶nh sè dïng lîc ®å m· Huffman. Ch¬ng tr×nh sÏ bao gåm: tÝnh to¸n kh¶ n¨ng x¶y ra cña mçi møc x¸m vµ x¾p xÕp l¹i theo thø tù gi¶m dÇn cña kh¶ n¨ng cã thÓ. TÊt nhiªn, ch¬ng tr×nh còng bao gåm mét vector ®Ó lu gi÷ c¸c th«ng tin cÇn thiÕt vÒ c¸c møc x¸m theo kh¶ n¨ng cña c¸c sù kiÖn, vÝ dô, mét b¶ng tra cøu. Ch¬ng tr×nh còng sÏ lo¹i trõ c¸c sù kiÖn kh«ng cã kh¶ n¨ng x¶y ra. Khi c¸c bíc ë trªn ®îc thùc hiÖn, m· Huffman ®îc sinh ra theo gi¶i thuËt ®îc m« t¶ trªn. Trong viÖc m· ho¸ ¶nh sè b¹n cÇn nhí r»ng ch¬ng tr×nh sÏ cÇn nhiÒu byte trªn ®Üa. Khi viÕt mét thñ tôc gi¶i m· ta cÇn chó ý ®Õn giíi h¹n nµy. 13.2.3 M· ho¸ ¶nh sè Tríc khi m· ho¸ ta cÇn t¹o ra hai b¶ng tra cøu: 1. Mét b¶ng tra cøu (LUT) chøa quan hÖ c¸c gi¸ trÞ møc x¸m trªn ¶nh vãi bé m· ho¸ Huffman. B¶ng LUT nµy cã thÓ ph¸t triÓn dïng quan hÖ: table_code[gray[i]] = code[i] ë ®©y code[i] lµ m· Huffman. 2. Mét b¶ng tra cøu x¸c lËp quan hÖ gi÷a c¸c møc x¸m trªn ¶nh vãi chiÒu dµi tõ m· Huffman. LUT cã thÓ t¹o ra theo mèi quan hÖ sau: 319
table_length [ gray[i]] = L[i] M· ho¸ theo c¸c bíc sau: a. Më mét file ®Ó chøa ¶nh ®· ®îc m· ho¸. b. §Æt Len = 0 vµ aux = 0. aux lµ mét thanh ghi bèn byte ®Ó truyÒn m·. Len chøa sè c¸c bÝt cßn l¹i trong aux. c. §äc gi¸ trÞ ®iÓm ¶nh. d. X¸c ®Þnh m· Huffman cña nã, code[i], vµ ®é dµi cña tõ m· L[i], dïng hai b¶ng LUT ®Ó t¹o ra gi¸ trÞ ban ®Çu. e. DÞch aux sang tr¸i L[i] bit. f. Thùc hiÖn phÐp logic OR code[i] víi aux. g. Len = Len + L[i]. h. NÕu Len  8 th× chuyÓn 8 bit cuèi ®Õn file ®Çu ra vµ gi¶m Len ®i 8. i. NÕu cha hÕt file th× chuyÓn ®Õn bíc c. k. ChuyÓn c¸c bÝt cßn l¹i trong thanh ghi aux ra file ®Çu ra. §Ó gi¶i m· ®îc ¶nh chóng ta cÇn ph¶i t¹o thªm phÇn header cña file. Header cña file bao gåm c¶ chiÒu dµi thùc sù cña file tÝnh theo bit. Chó ý lµ chiÒu dµi thùc sù cã thÓ lín h¬n hoÆc b»ng chiÒu dµi thùc sù cña file. §iÒu nµy bëi v× chóng ta chØ cã thÓ chøa díi d¹ng ®¬n vÞ byte, cßn file ¶nh ®· m· ho¸ ph¶i cã chiÒu dµi kh«ng chia hÕt cho 8. PhÇn nµy chøa ®ñ th«ng tin ®Ó thiÕt lËp c¸c b¶ng LUT, dïng cho viÖc gi¶i m· ¶nh. Nã bao gåm c¸c møc x¸m trªn ¶nh, d¹ng m· Huffman vµ chiÒu dµi t¬ng ®¬ng cña chóng. Chó ý r»ng c¸c tõ m· ®îc s¾p xÕp theo thø tù gi¶m dÇn theo x¸c suÊt xuÊt hiÖn cña chóng. Ch¬ng tr×nh C sau ®©y sÏ tr×nh bµy c¸c bíc trªn. Ch¬ng tr×nh 13.2 "HUCODING" . M· ho¸ Huffman ¶nh sè. /*Program 13.2 "HUCODING.C". Huffman coding of digital images.*/ /* This program is for coding a binary file using Huffman codes. */ #include #include #include #include #include #include 320