Bài giảng Đồ họa và xử lí ảnh - Chương 6: Nén ảnh - Nguyễn Đình Cường

· hãa RLC sÏ ®­îc tr×nh bµy trong môc sau.7Nén ảnhNHỮNG MẪU SỬ DỤNG TẦN SUẤTCã thÓ cã d·y kÝ tù nµo ®ã xuÊt hiÖn víi tÇn suÊt t­¬ng ®èi cao. Do vËy, cã thÓ m· hãa bëi Ýt h¬n. §©y lµ c¬ së cña ph­¬ng ph¸p m· hãa kiÓu tõ ®iÓn do Lempel-Ziv ®­a ra vµ c¶i tiÕn vµo n¨m 1977 vµ 1978 vµ do ®ã cã tªn gäi lµ ph­¬ng ph¸p nÐn LZ 77, LZ 78. N¨m 1984, Terry Welch ®· c¶i tiÕn hiÖu qu¶ h¬n vµ ®Æt tªn lµ LZW (Lempel-Ziv Welch). Ph­¬ng ph¸p nÐn nµy sÏ ®­îc tr×nh bµy trong môc sau.8Nén ảnhĐỘ 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Þ ë c¸c vÞ trÝ 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÷ liÖu l¹i xuÊt hiÖn trong cïng mét vÞ trÝ ë c¸c hµng kh¸c nhau. Do vËy, thay v× l­u tr÷ d÷ liÖu, ta chØ cÇn l­u 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· hãa 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 tr­ng 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 diÔn ¶nh. 9Nén ảnhPHÂ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 hai hä lín: NÐn chÝnh x¸c hay nÐn kh«ng mÊt th«ng tin: 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: 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 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 ®ã.10Nén ảnhPHÂN LOẠI CÁC PHƯƠNG PHÁP NÉNC¸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 Compresion): C¸c ph­¬ng ph¸p thuéc hä nµy thùc hiÖn nÐn b»ng c¸c 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].11Nén ảnhPHÂN LOẠI CÁC PHƯƠNG PHÁP NÉNCã mét c¸ch ph©n lo¹i kh¸c n÷a, c¸ch ph©n lo¹i thø 3, dùa vµo triÕt lý cña sù m· hãa, ph©n c¸c ph­¬ng ph¸p nÐn thµnh hai 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·,C¸c ph­¬ng ph¸p nÐn thÕ hÖ thø hai: Dùa vµo møc ®é b·o hßa cña tû lÖ nÐn. 12Nén ảnhCÁC PHƯƠNG PHÁP NÉN THẾ HỆ THỨ IM· hãa lo¹t dµi RLC (Run Length Coding).M· hãa HuffmanM· hãa LZW (Lempel-Ziv Welch)M· hãa khèi (Block Coding).13Nén ảnhPHƯƠNG PHÁP Mà HOÁ LOẠT DÀIPh­¬ng ph¸p m· hãa lo¹t dµi lóc ®Çu ®­îc ph¸t triÓn dµnh cho ¶nh sè hai 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 bit lÆp l¹i, thÝ dô nh­ mét 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÷ 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 hai 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 l­u ý 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· hãa th× sÏ kh«ng ®ñ. Gi¶i ph¸p ®­îc dïng lµ t¸ch chuçi ®ã thµnh hai 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· hãa l­u tr÷ c¸c ¶nh Bitmap theo d¹ng PCX, BMP14Nén ảnhPHƯƠNG PHÁP Mà HOÁ LOẠT DÀIPh­¬ng ph¸p RLC cã thÓ chia thµnh hai 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 theo kiÓu 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 bit. Víi c¸ch thøc nµy, mäi m¹ch ®Òu ®­îc m· hãa 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 cßn gäi lµ m· RLC thÝch nghi.15Nén ảnhPHƯƠNG PHÁP Mà HOÁ HUFFMANa. 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÷ 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 suÊ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 suÊt thÊp tõ m· dµi. Nãi mét c¸ch kh¸c c¸c ksi tù cã tÇn suÊ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· hâa 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.16Nén ảnhPHƯƠNG PHÁP Mà HOÁ HUFFMANb. ThuËt to¸n	ThuËt to¸n gåm hai b­íc chÝ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· hãa. DuyÖt b¶ng tÇn suÊt tõ cuèi lªn ®Çu ®Ó thùc hiÖn ghÐp hai 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 suÊt b»ng tæng hai 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á hai phÇn tö ®· xÐt. Qu¸ tr×nh ®­îc lÆp l¹i cho ®Õn khi b¶ng chØ cßn 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 hai 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÷ 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· hãa rÊt ®¬n gi¶n: mçi lÇn xuèng bªn ph¶i ta thªm mét bit “1” vµo tõ m·; mçi lÇn xuèng bªn tr¸i ta thªm mét 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­ ®· 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óc ®Ç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:17Nén ảnhVÍ DỤ NÉN HUFFMAN18Nén ảnhVÍ DỤ NÉN HUFFMAN19Nén ảnhPHƯƠNG PHÁP LZWMë ®Çu	Kh¸i niÖm nÐn tõ ®iÓn ®­îc Jaco Lempel vµ Abraham Ziv ®­a ra lÇn ®Çu tiªn vµo n¨m 1977, sau ®ã ph¸t triÓn thµnh mét hä gi¶ thuËt nÐn tõ ®iÓn LZ. N¨m 1984 Terry Welch ®· c¶i tiÕn gi¶i thuËt LZ thµnh mét gi¶i thuËt míi cã hiÖu qu¶ h¬n vµ ®Æt tªn lµ LZW. Ph­¬ng ph¸p nÐn tõ ®iÓn dùa trªn viÖc x©y dùng tõ ®iÓn l­u c¸c chuçi kÝ tù cã tÇn suÊt lÆp l¹i cao vµ thay thÕ b»ng tõ m· t­¬ng øng mçi khi gÆp l¹i chóng. Gi¶i thuËt LZW hay h¬n c¸c gi¶i thuËt tr­íc nã ë kü thuËt tæ chøc tõ ®iÓn, cho phÐp n©ng cao tû lÖ nÐn.Gi¶i thuËt LZW ®­îc sö dông cho t¸t c¶ c¸c lo¹i file nhÞ ph©n vµ th­êng ®­îc dïng ®Ó nÐn c¹c lo¹i v¨n b¶n, ¶nh ®en tr¾ng, ¶nh mµu, ¶nh da møc s¸ng  vµ lµ chuÈn nÐn cho c¸c d¹ng ¶nh GIF vµ TIFF . Møc ®é hiÖu qu¶ cña LZW kh«ng phô thuéc vµo sè bÝt mµu cña ¶nh.20Nén ảnhPHƯƠNG PHÁP LZWb. Ph­¬ng ph¸p	Gi¶i thuËt nÐn LZW x©y dùng mét tõ ®iÓn l­u c¸c mÉu cã tÇn suÊt xuÊt hiÖn cao trong ¶nh. Tõ ®iÓn lµ tËp hîp nh÷ng cÆp tõ vùng vµ nghÜa cña nã. Trong ®ã ,tõ vùng sÏ lµ c¸c tõ m· ®­îc x¾p xÕp theo thø tù nhÊt ®Þnh. NghÜa lµ mét chuçi con trong d÷ liÖu ¶nh. Tõ ®iÓn ®­îc x©y dùng ®ång thêi víi qu¸ tr×nh ®äc d÷ liÖu. Sù cã mÆt cña mét chuçi con trong tõ ®iÓn kh¼ng ®Þnh r­µng chuçi ®ã ®· tõng xuÊt hiÖn trong phÇn d÷ liÖu ®· ®äc. ThuËt to¸n liªn tôc “tra cøu” vµ cËp nhËt tõ ®iÓn sau mçi lÇn ®äc mét kÝ tù ë d÷ liÖu ®Çu vµo.Do kÝch th­íc bé nhí kh«ng ph¶i lµ v« h¹n vµ ®Ó b¶o ®¶m tèc ®é t×m kiÕm, tõ ®iÓn chØ giíi h¹n 4096 ë phÇn tö dïng ®Ó l­u lín nhÊt lµ 4096 gi¸ trÞ cña c¸c tõ m·. nh­ vËy ®é dµi lín nhÊt cña tõ m· lµ 12 bits( 4096=212). CÊu tróc tõ ®iÓn nh­ sau:21Nén ảnhPHƯƠNG PHÁP LZW256 tõ m· ®Çu tiªn theo thø tù tõ 0  255 chøa c¸c sè nguyªn tõ 0255. ®©y lµ m· cña 256 kÝ tù c¬ b¶n trong b¶ng m· ASCII.Tõ m· 256 chøa mét m· ®Æc biÖt lµ “xãa m·” (cc-clear code). Môc ®Ých viÖc dïng m· xãa nh»m kh¾c phôc t×nh tr¹nh sè mÉu l¹p trong ¶nh lín h¬n 4096. Khi ®ã mét ¶nh ®­îc quan niÖm lµ nhiÒu m¶nh ¶nh, vµ tõ ®iÓn lµ mét bé tõ ®iÓn gåm nhiÒu t­ ®iÓn con. Cø hÕt mét m¶nh ¶nh ng­êi ta l¹i göi mét m· xãa ®Î b¸o hiÖu kÕt thóc mét m¶nh ¶nh cò, b¾t ®Çu m¶nh ¶nh míi ®ång thêi khëi t¹o l¹i tõ ®iÓn cho m¶nh ¶nh míi. M· xãa cã gi¸ trÞ lµ 256.Tõ m· thø 257 chøa m· kÕt thóc th«ng tin (EOI-End Of Information). M· nµy cã gi¸ trÞ lµ 257. Nh­ chóng ta ®· biÕt, mét file ¶nh GIF cã thÓ chøa nhiÒu ¶nh. Mçi ¶nh sÏ ®­îc m· hãa riªng. Ch­¬ng tr×nh tr×nh gi¶i m· sÏ lÆp ®i lÆp l¹i thao t¸c gi¶i m· tõng ¶nh cho ®Õn khi gÆp m· kÕt thóc th«ng tin th× dõng l¹i. C¸c tõ m· cßn l¹i (tõ 258 ®Õn 4095) chøa mÉu th­êng lÆp l¹i trong ¶nh. 512 phÇn tö ®Çu tiªn cña tõ ®iÓn biÓu diÔn b»ng 9 bit. C¸c tõ m· tõ 512 ®Õn 1023 biÓu diÔn bëi 10 bit, tõ 1024 ®Õn 2047 biÓu diÔn bëi 11 bit vµ tõ 2048 ®Õn 4095 ®­îc biÓu diÔn bëi 12 bit. 22Nén ảnhVÍ DỤ: NÉN LZWCho chuçi ®Çu vµo lµ”ABCBCABCABCD” (m· ASCII cña A lµ 65, B lµ 66, C lµ 67 23Nén ảnhVÍ DỤ: NÉN LZWChuçi ®Çu ra sÏ lµ : 	65-66-67-259-258-67-262§Çu vµo cã kÝch th­íc : 	12 x 8 = 96 bits§Çu ra cã kÝch th­íc lµ: 	4x8 + 3x9 = 59 bits TØ lÖ nÐn lµ : 	96:59=1,6324Nén ảnh