Tài liệu Bài báo cáo-xử lý ảnh-chương 8

Ch¬ng T¸m: nÐn d÷ liÖu ¶nh 8 n Ðn d÷ liÖu ¶nh image compression 8.1 Tæng quan vÒ nÐn d÷ liÖu ¶nh Ch¬ng nµy nh»m cung cÊp mét sè kh¸i niÖm (thuËt ng÷) nh: nÐn, tØ lÖ nÐn, c¸c ý tëng dÉn tíi c¸c ph¬ng ph¸p nÐn kh¸c nhau vµ c¸ch ph©n lo¹i, ®¸nh gi¸ c¸c ph¬ng ph¸p nÐn. 8.1.1 Mét sè kh¸i niÖm NÐn D÷ liÖu (Data Compression) NÐn d÷ liÖu lµ qu¸ tr×nh lµm gi¶m lîng th«ng tin "d thõa" trong d÷ liÖu gèc vµ do vËy, lîng th«ng tin thu ®îc sau nÐn thêng NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 227 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh nhá h¬n d÷ liÖu gèc rÊt nhiÒu. Víi d÷ liÖu ¶nh, kÕt qu¶ thêng lµ 10 : 1. Mét sè ph¬ng ph¸p cßn cho kÕt qu¶ cao h¬n. Theo kÕt qu¶ nghiªn cøu ®îc c«ng bè gÇn ®©y t¹i viÖn kü thuËt Georgie, kü thuËt nÐn fractal cho tØ sè nÐn lµ 30 trªn 1[6]. Ngoµi thuËt ng÷ "nÐn d÷ liÖu”, do b¶n chÊt cña kü thuËt nµy nã cßn cã mét sè tªn gäi kh¸c nh: gi¶m ®é d thõa, m· ho¸ ¶nh gèc. Tõ h¬n hai thËp kû nay, cã rÊt nhiÒu kü thuËt nÐn ®· ®îc c«ng bè trªn c¸c tµi liÖu vÒ nÐn vµ c¸c phÇn mÒm nÐn d÷ liÖu ®· xuÊt hiÖn ngµy cµng nhiÒu trªn th¬ng trêng. Tuy nhiªn, cha cã ph¬ng ph¸p nÐn nµo ®îc coi lµ ph¬ng ph¸p v¹n n¨ng (Universel) v× nã phô thuéc vµo nhiÒu yÕu tè vµ b¶n chÊt cña d÷ liÖu gèc. Trong ch¬ng nµy, chóng ta kh«ng thÓ hy väng xem xÐt tÊt c¶ c¸c ph¬ng ph¸p NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 228 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh nÐn. H¬n n÷a, c¸c kü thuËt nÐn d÷ liÖu chung ®· ®îc tr×nh bµy trong nhiÒu tµi liÖu chuyªn ngµnh. ë ®©y, chóng ta chØ ®Ò cËp c¸c ph¬ng ph¸p nÐn cã ®Æc thï riªng cho d÷ liÖu ¶nh. Tû lÖ nÐn (Compression rate) Tû lÖ nÐn lµ mét trong c¸c ®Æc trng quan träng nhÊt cña mäi ph¬ng ph¸p nÐn. Tuy nhiªn, vÒ c¸ch ®¸nh gi¸ vµ c¸c kÕt qu¶ c«ng bè trong c¸c tµi liÖu còng cÇn ®îc quan t©m xem xÐt . Nh×n chung, ngêi ta ®Þnh nghÜa tû lÖ nÐn nh sau: Tû lÖ nÐn = 1 r x% víi r lµ tû sè nÐn ®îc ®Þnh nghÜa: r = kÝch thíc d÷ liÖu gèc/ kÝch thíc d÷ liÖu thu ®îc sau nÐn. Nh vËy hiÖu suÊt cña nÐn lµ : (1 tû lÖ nÐn) x %. NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 229 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Trong c¸c tr×nh bµy sau, khi nãi ®Õn kÕt qu¶ nÐn, chóng ta dïng tû sè nÐn, thÝ dô nh 10 trªn 1 cã nghÜa lµ d÷ liÖu gèc lµ 10 phÇn sau khi nÐn chØ cã 1 phÇn. Tuy nhiªn, còng ph¶i thÊy r»ng nh÷ng sè ®o cña mét ph¬ng ph¸p nÐn chØ cã gi¸ trÞ víi chÝnh sù nÐn ®ã, v× r»ng hiÖu qu¶ cña nÐn cßn phô thuéc vµo kiÓu d÷ liÖu ®Þnh nÐn. Tû lÖ nÐn còng chØ lµ mét trong c¸c ®Æc trng c¬ b¶n cña ph¬ng ph¸p nÐn. NhiÒu khi tû lÖ nÐn cao còng cha thÓ nãi r»ng ph¬ng ph¸p ®ã lµ hiÖu qu¶ h¬n c¸c ph¬ng ph¸p kh¸c, v× cßn c¸c chi phÝ kh¸c nh thêi gian, kh«ng gian vµ thËm chÝ c¶ ®é phøc t¹p tÝnh to¸n n÷a. ThÝ dô nh nÐn phôc vô trong truyÒn d÷ liÖu: vÊn ®Ò ®Æt ra lµ hiÖu qu¶ nÐn cã t¬ng hîp víi ®êng truyÒn kh«ng. NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 230 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Còng cÇn ph©n biÖt nÐn d÷ liÖu víi nÐn b¨ng truyÒn. Môc ®Ých chÝnh cña nÐn lµ gi¶m lîng th«ng tin d thõa vµ dÉn tíi gi¶m kÝch thíc d÷ liÖu. Tuy vËy, ®«i khi qu¸ tr×nh nÐn còng lµm gi¶m b¨ng truyÒn tÝn hiÖu sè ho¸ thÊp h¬n so víi truyÒn tÝn hiÖu t¬ng tù. 8.1.2 C¸c lo¹i d thõa d÷ liÖu Nh trªn ®· nãi, nÐn nh»m môc ®Ých gi¶m kÝch thíc d÷ liÖu b»ng c¸ch lo¹i bá d thõa d÷ liÖu. ViÖc x¸c ®Þnh b¶n chÊt c¸c kiÓu d thõa d÷ liÖu rÊt cã Ých cho viÖc x©y dùng c¸c ph¬ng ph¸p nÐn d÷ liÖu kh¸c nhau. Nãi mét c¸ch kh¸c, c¸c ph¬ng ph¸p nÐn d÷ liÖu kh¸c nhau lµ do sö dông c¸c kiÓu d thõa d÷ liÖu kh¸c nhau. Ngêi ta coi cã 4 kiÓu d thõa chÝnh: • Sù ph©n bè ký tù NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 231 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Trong mét d·y ký tù, cã mét sè ký tù cã tÇn suÊt xuÊt hiÖn nhiÒu h¬n mét sè d·y kh¸c. Do vËy, ta cã thÓ m· ho¸ d÷ liÖu mét c¸ch c« ®äng h¬n. C¸c d·y ký tù cã tÇn xuÊt cao ®îc thay bëi mét tõ m· nhÞ ph©n víi sè bÝt nhá; ngîc l¹i c¸c d·y cã tÇn xuÊt thÊp sÏ ®îc m· ho¸ bëi tõ m· cã nhiÒu bÝt h¬n. §©y chÝnh lµ b¶n chÊt cña ph¬ng ph¸p m· ho¸ Huffman (xem môc 8.2.2). • Sù lÆp l¹i cña c¸c ký tù Trong mét sè t×nh huèng nh trong ¶nh, 1 ký hiÖu (bÝt "0" hay bÝt "1") ®îc lÆp ®i lÆp l¹i mét sè lÇn. Kü thuËt nÐn dïng trong trêng hîp nµy lµ thay d·y lÆp ®ã bëi d·y míi gåm 2 thµnh phÇn: sè lÇn lÆp vµ kÝ hiÖu dïng ®Ó m·. Ph¬ng ph¸p m· ho¸ kiÓu nµy cã tªn lµ m· ho¸ lo¹t dµi RLC (Run Length NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 232 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Coding). Ph¬ng ph¸p m· ho¸ RLC sÏ ®îc tr×nh bµy trong môc 8.2.1. • Nh÷ng mÉu sö dông tÇn suÊt Cã thÓ cã d·y ký hiÖu nµo ®ã xuÊt hiÖn víi tÇn suÊt t¬ng ®èi cao. Do vËy, cã thÓ m· ho¸ bëi Ýt bÝt h¬n. §©y lµ c¬ së cña ph¬ng ph¸p m· ho¸ kiÓu tõ ®iÓn do Lempel-Ziv ®a ra vµ cã c¶i tiÕn vµo n¨m 1977, 1978 vµ do ®ã cã tªn gäi lµ ph¬ng ph¸p nÐn LZ77, LZ78. N¨m 1984, Terry Welch ®· c¶i tiÕn hiÖu qu¶ h¬n vµ ®Æt tªn lµ LZW (LempelZiv- Welch). Ph¬ng ph¸p nÐn nµy sÏ ®îc tr×nh bµy trong 8.2.3. • §é d thõa vÞ trÝ Do sù phô thuéc lÉn nhau cña d÷ liÖu, ®«i khi biÕt ®îc ký hiÖu (gi¸ trÞ) xuÊt hiÖn t¹i mét vÞ trÝ, ®ång thêi cã thÓ ®o¸n tríc sù xuÊt hiÖn cña c¸c gi¸ trÞ NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 233 ë c¸c vÞ trÝ Ch¬ng T¸m: nÐn d÷ liÖu ¶nh kh¸c nhau mét c¸ch phï hîp. Ch¼ng h¹n, ¶nh biÓu diÔn trong mét líi hai chiÒu, mét sè ®iÓm ë hµng däc trong mét khèi d÷ lÖu l¹i xuÊt hiÖn trong cïng vÞ trÝ ë c¸c hµng kh¸c nhau. Do vËy, thay v× lu tr÷ d÷ liÖu, ta chØ cÇn lu tr÷ vÞ trÝ hµng vµ cét. Ph¬ng ph¸p nÐn dùa trªn sù d thõa nµy gäi lµ ph¬ng ph¸p m· ho¸ dù ®o¸n. C¸ch ®¸nh gi¸ ®é d thõa nh trªn hoµn toµn mang tÝnh trùc quan nh»m biÓu thÞ mét c¸i g× ®ã xuÊt hiÖn nhiÒu lÇn. §èi víi d÷ liÖu ¶nh, ngoµi ®Æc thï chung ®ã, nã cßn cã nh÷ng ®Æc thï riªng. ThÝ dô nh cã øng dông kh«ng cÇn toµn bé d÷ liÖu th« cña ¶nh mµ chØ cÇn c¸c th«ng tin ®Æc trng biÓu diÔn ¶nh nh biªn ¶nh hay vïng ®ång nhÊt. Do vËy, cã nh÷ng ph¬ng ph¸p nÐn riªng cho ¶nh dùa vµo biÕn ®æi ¶nh hay dùa vµo biÓu NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 234 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh diÔn ¶nh. C¸c ph¬ng ph¸p nµy sÏ lÇn lît tr×nh bµy trong môc 8.3 vµ 8.4. 8.1.3 Ph©n lo¹i c¸c ph¬ng ph¸p nÐn Cã nhiÒu c¸ch ph©n lo¹i c¸c ph¬ng ph¸p nÐn kh¸c nhau. C¸ch thø nhÊt dùa vµo nguyªn lý nÐn. C¸ch nµy ph©n c¸c ph¬ng ph¸p nÐn thµnh 2 hä lín: • NÐn chÝnh x¸c hay nÐn kh«ng mÊt th«ng tin: hä nµy bao gåm c¸c ph¬ng ph¸p nÐn mµ sau khi gi¶i nÐn ta thu ®îc chÝnh x¸c d÷ liÖu gèc. • NÐn cã mÊt m¸t th«ng tin: hä nµy bao gåm c¸c ph¬ng ph¸p mµ sau khi gi¶i nÐn ta kh«ng thu ®îc d÷ liÖu nh b¶n gèc. Trong nÐn ¶nh, ngêi ta gäi lµ c¸c ph¬ng ph¸p "t©m lý thÞ gi¸c". C¸c ph¬ng ph¸p nµy lîi dông tÝnh chÊt cña m¾t ngêi, chÊp nhËn mét sè vÆn xo¾n trong ¶nh khi kh«i phôc NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 235 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh l¹i. TÊt nhiªn, c¸c ph¬ng ph¸p nµy chØ cã hiÖu qu¶ khi mµ ®é vÆn xo¾n lµ chÊp nhËn ®îc b»ng m¾t thêng hay víi dung sai nµo ®ã. C¸ch ph©n lo¹i thø hai dùa vµo c¸ch thøc thùc hiÖn nÐn. Theo c¸ch nµy, ngêi ta còng ph©n thµnh hai hä: • Ph¬ng ph¸p kh«ng gian (Spatial Data Compression): c¸c ph¬ng ph¸p thuéc hä nµy thùc hiÖn nÐn b»ng c¸ch t¸c ®éng trùc tiÕp lªn viÖc lÊy mÉu cña ¶nh trong miÒn kh«ng gian. • Ph¬ng ph¸p sö dông biÕn ®æi (Transform Coding): Gåm c¸c ph¬ng ph¸p t¸c ®éng lªn sù biÕn ®æi cña ¶nh gèc mµ kh«ng t¸c ®éng trùc tiÕp nh hä trªn [6]. Cã mét c¸ch ph©n lo¹i kh¸c n÷a, c¸ch ph©n lo¹i thø ba, dùa vµo triÕt lý cña sù m· ho¸. NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 236 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh C¸ch nµy còng ph©n c¸c ph¬ng ph¸p nÐn thµnh 2 hä: • C¸c ph¬ng ph¸p nÐn thÕ hÖ thø nhÊt: Gåm c¸c ph¬ng ph¸p mµ møc ®é tÝnh to¸n lµ ®¬n gi¶n, thÝ dô nh viÖc lÊy mÉu, g¸n tõ m·, v,..., v. • C¸c ph¬ng ph¸p nÐn thÕ hÖ thø hai: Dùa vµo møc ®é b·o hoµ cña tû lÖ nÐn. Trong c¸c phÇn tr×nh bµy díi ®©y, ta sÏ theo c¸ch ph©n lo¹i nµy. Còng cßn ph¶i kÓ thªm mét c¸ch ph©n lo¹i thø tù do Anil.K.Jain nªu ra. Theo c¸ch cña Jain, c¸c ph¬ng ph¸p nÐn gåm 4 hä chÝnh: • Ph¬ng ph¸p ®iÓm. • Ph¬ng ph¸p dù ®o¸n. • Ph¬ng ph¸p dùa vµo biÕn ®æi. • C¸c ph¬ng ph¸p tæ hîp (Hybrid). NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 237 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Thùc ra c¸ch ph©n lo¹i nµy lµ chia nhá cña c¸ch ph©n lo¹i thø ba vµ dùa vµo c¬ chÕ thùc hiÖn nÐn. XÐt mét c¸ch kü lìng nã còng t¬ng ®¬ng c¸ch ph©n lo¹i thø ba. Nh×n chung, qu¸ tr×nh nÐn vµ gi¶i nÐn d÷ liÖu cã thÓ m« t¶ mét c¸ch tãm t¾t theo s¬ ®å h×nh 8.1 díi ®©y. Qu¸ tr×nh nÐn D÷ liÖu gèc D÷ liÖu nÐn Qu¸ tr×nh gi¶i nÐn NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 238 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh H×nh 8.1 S¬ ®å chøc n¨ng qu¸ tr×nh nÐn d÷ liÖu 8.2 C¸c ph¬ng ph¸p nÐn thÕ hÖ thø nhÊt Trong líp c¸c ph¬ng ph¸p nµy, ta lÇn lît xem xÐt c¸c ph¬ng ph¸p: - M· ho¸ lo¹t dµi RLC (Run Length Coding) - M· ho¸ Huffman - M· ho¸ LZW(Lempel Ziv-Wench) - M· ho¸ khèi (Block Coding). 8.2.1 Ph¬ng ph¸p m· ho¸ lo¹t dµi Ph¬ng ph¸p m· ho¸ lo¹t dµi lóc ®Çu ®îc ph¸t triÓn dµnh cho ¶nh sè 2 møc: møc ®en (1) vµ møc tr¾ng (0) nh c¸c v¨n b¶n trªn nÒn tr¾ng, trang in, c¸c bøc vÏ kü thuËt. Nguyªn t¾c cña ph¬ng ph¸p lµ ph¸t hiÖn mét lo¹t c¸c bÝt lÆp l¹i, thÝ dô nh mét NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 239 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh lo¹t c¸c bit 0 n»m gi÷a hai bit 1, hay ngîc l¹i, mét lo¹t bit 1 n»m gi÷a hai bit 0. Ph¬ng ph¸p nµy chØ cã hiÖu qu¶ khi chiÒu dµi d·y lÆp lín h¬n mét ngìng nµo ®ã. D·y c¸c bit lÆp gäi lµ lo¹t hay m¹ch (run). TiÕp theo, thay thÕ chuçi ®ã bëi mét chuçi míi gåm 2 th«ng tin: chiÒu dµi chuçi vµ bit lÆp (ký tù lÆp). Nh vËy, chuçi thay thÕ sÏ cã chiÒu dµi ng¾n h¬n chuçi cÇn thay. CÇn lu ý r»ng, ®èi víi ¶nh, chiÒu dµi cña chuçi lÆp cã thÓ lín h¬n 255. NÕu ta dïng 1 byte ®Ó m· ho¸ th× sÏ kh«ng ®ñ. Gi¶i ph¸p ®îc dïng lµ t¸ch chuçi ®ã thµnh 2 chuçi: mét chuçi cã chiÒu dµi 255, chuçi kia lµ sè bit cßn l¹i. Ph¬ng ph¸p RLC ®îc sö dông trong viÖc m· ho¸ lu tr÷ c¸c ¶nh Bitmap theo d¹ng PCX, BMP (®· nªu trong ch¬ng 2). NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 240 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Ph¬ng ph¸p RLC cã thÓ chia thµnh 2 ph¬ng ph¸p nhá: ph¬ng ph¸p dïng chiÒu dµi tõ m· cè ®Þnh vµ ph¬ng ph¸p thÝch nghi nh kiÓu m· Huffman. Gi¶ sö c¸c m¹ch gåm M bits. §Ó tiÖn tr×nh bµy, ®Æt M =2m-1. Nh vËy m¹ch cò ®îc thay bái m¹ch míi gåm m bits. Víi c¸ch thøc nµy, mäi m¹ch ®Òu ®îc m· ho¸ bëi tõ m· cã cïng ®é dµi. Ngêi ta còng tÝnh ®îc, víi M=15, p=0.9, ta sÏ cã m=4 vµ tû sè nÐn lµ 1,95. Víi chiÒu dµi cè ®Þnh, viÖc cµi ®Æt thuËt to¸n lµ ®¬n gi¶n. Tuy nhiªn, tû lÖ nÐn sÏ kh«ng tèt b»ng dïng chiÒu dµi biÕn ®æi hay gäi lµ m· RLC thÝch nghi. 8.2.2 Ph¬ng ph¸p m· ho¸ Huffman Nguyªn t¾c Ph¬ng ph¸p m· ho¸ Huffman lµ ph¬ng ph¸p dùa vµo m« h×nh thèng kª. Dùa vµo d÷ NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 241 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh liÖu gèc, ngêi ta tÝnh tÇn suÊt xuÊt hiÖn cña c¸c ký tù. ViÖc tÝnh tÇn xuÊt ®îc thùc hiÖn b»ng c¸ch duyÖt tuÇn tù tÖp gèc tõ ®Çu ®Õn cuèi. ViÖc xö lý ë ®©y tÝnh theo bit. Trong ph¬ng ph¸p nµy, ngíi ta g¸n cho c¸c ký tù cã tÇn suÊt cao mét tõ m· ng¾n, c¸c ký tù cã tÇn xuÊt thÊp tõ m· dµi. Nãi mét c¸ch kh¸c, c¸c ký tù cã tÇn xuÊt cµng cao ®îc g¸n m· cµng ng¾n vµ ngîc l¹i. Râ rµng víi c¸ch thøc nµy, ta ®· lµm gi¶m chiÒu dµi trung b×nh cña tõ m· ho¸ b»ng c¸ch dïng chiÒu dµi biÕn ®æi. Tuy nhiªn, trong mét sè t×nh huèng khi tÇn suÊt lµ rÊt thÊp, ta cã thÓ kh«ng ®îc lîi mét chót nµo, thËm chÝ cßn bÞ thiÖt mét Ýt bit. ThuËt to¸n ThuËt to¸n bao gåm 2 bíc chÝnh: NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 242 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh • Giai ®o¹n tÝnh tÇn suÊt cña c¸c ký tù trong d÷ liÖu gèc: DuyÖt tÖp gèc mét c¸ch tuÇn tù tõ ®Çu ®Õn cuèi ®Ó x©y dùng b¶ng m·. TiÕp sau ®ã lµ s¾p xÕp l¹i b¶ng m· theo thø tù tÇn suÊt gi¶m dÇn. • Giai ®o¹n thø hai: m· ho¸. DuyÖt b¶ng tÇn suÊt tõ cuèi lªn ®Çu ®Ó thùc hiÖn ghÐp 2 phÇn tö cã tÇn suÊt thÊp nhÊt thµnh mét phÇn tö duy nhÊt. PhÇn tö nµy cã tÇn xuÊt b»ng tæng 2 tÇn suÊt thµnh phÇn. TiÕn hµnh cËp nhËt l¹i b¶ng vµ ®¬ng nhiªn lo¹i bá 2 phÇn tö ®· xÐt. Qu¸ tr×nh ®îc lÆp l¹i cho ®Õn khi b¶ng chØ cã mét phÇn tö. Qu¸ tr×nh nµy gäi lµ qu¸ tr×nh t¹o c©y m· Huffman v× viÖc tËp hîp ®îc tiÕn hµnh nhê mét c©y nhÞ ph©n víi 2 nh¸nh. PhÇn tö cã tÇn suÊt thÊp ë bªn ph¶i, phÇn tö kia ë bªn tr¸i. Víi c¸ch t¹o c©y nµy, tÊt c¶ c¸c bit d÷ NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 243 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh liÖu/ ký tù lµ nót l¸; c¸c nót trong lµ c¸c nót tæng hîp. Sau khi c©y ®· t¹o xong, ngêi ta tiÕn hµnh g¸n m· cho c¸c nót l¸. ViÖc m· ho¸ rÊt ®¬n gi¶n: mçi lÇn xuèng bªn ph¶i ta thªm 1 bit "1" vµo tõ m·; mçi lÇn xuèng bªn tr¸i ta thªm 1 bit "0". TÊt nhiªn cã thÓ lµm ngîc l¹i, chØ cã gi¸ trÞ m· thay ®æi cßn tæng chiÒu dµi lµ kh«ng ®æi. Còng chÝnh do lý do nµy mµ c©y cã tªn gäi lµ c©y m· Huffman nh trªn ®· gäi. Qu¸ tr×nh gi¶i nÐn tiÕn hµnh theo chiÒu ngîc l¹i kh¸ ®¬n gi¶n. Ngêi ta còng ph¶i dùa vµo b¶ng m· t¹o ra trong giai ®o¹n nÐn (b¶ng nµy ®îc gi÷ l¹i trong cÊu tróca ®Çu cña tÖp nÐn cïng víi d÷ liÖu nÐn). ThÝ dô, víi mét tÖp d÷ liÖu mµ tÇn suÊt c¸c ký t cho bëi: NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 244 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh Ký tù TÇn suÊt tÇn suÊt x¸c suÊt "1" 152 1532 323 602 0.1088 "3" 412 536 0.0969 535 "5" 112 "6" 226 385 "." "" "3" 0.0746 602 "5 " 0.0696 "7" 92 323 0.0585 315 "6" 0.0967 385 "8" "0" 0.2770 "2" "4" Ký tù 112 0.0569 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 245 "2" "_" Ch¬ng T¸m: nÐn d÷ liÖu ¶nh "9" 226 "0" 87 "4" 0.0409 1532 220 0.0396 "." 536 152 0.0275 "+" 220 112 0.0203 "_" 315 92 0.0167 "" 535 87 0.0158 "+" "1" "8" "7" "9" B¶ng B¶ng tÇn xuÊt tÇn suÊt s¾p theo thø tù gi¶m dÇn Lu ý r»ng, trong ph¬ng ph¸p Huffman, m· cña ký tù lµ duy nhÊt vµ kh«ng m· nµo lµ phÇn b¾t ®Çu cña m· kh¸c. V× vËy, khi ®äc NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 246