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á 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, ch­a 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 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 tr­ng 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 =
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 %. 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 tr­ng c¬ b¶n cña ph­¬ng ph¸p nÐn. NhiÒu khi tû lÖ nÐn cao còng ch­a 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. 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ù 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 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 (Lempel-Ziv- 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Þ ë 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÷ 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× 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· 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 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. 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 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¸. 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). 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 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 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 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· 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¸ l­u tr÷ c¸c ¶nh Bitmap theo d¹ng PCX, BMP (®· nªu trong ch­¬ng 2). 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÷ 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: 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÷ 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: Ký tù TÇn suÊt Ký tù tÇn suÊt x¸c suÊt "1" 152 "0" 1532 0.2770 "2" 323 "6" 602 0.1088 "3" 412 "." 536 0.0969 "4" 226 " " 535 0.0967 "5" 385 "3" 112 0.0746 "6" 602 "5 " 385 0.0696 "7" 92 "2" 323 0.0585 "8" 112 "_" 315 0.0569 "9" 87 "4" 226 0.0409 "0" 1532 "+" 220 0.0396 "." 536 "1" 152 0.0275 "+" 220 "8" 112 0.0203 "_" 315 "7" 92 0.0167 " " 535 "9" 87 0.0158 B¶ng tÇn xuÊt B¶ng tÇn suÊt s¾p theo thø tù gi¶m dÇn L­u ý 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 tÖp nÐn tõng bit tõ ®Çu ®Õn cuèi ta cã thÓ duyÖt c©y m· cho cho ®Õn mét l¸, tøc lµ ký tù ®· ®­îc gi¶i nÐn. C©y m· Hufman t­¬ng øng Gèc 1 0 N12 N11 1 0 1 0 N10 "0" N9 N8 1 0 1 0 1 0 N7 N6 N5 "6" "." " " 1 0 1 0 1 0 N4 "3" N3 "5" "2" "_" 1 0 1 0 N2 "4" "+" N1 1 0 1 0 "1" "8" "7" "9" H×nh 8.2. C©y m· Huffman . B¶ng tõ m· g¸n cho c¸c ký tù bëi m· ho¸ Huffman "0" 10 "_" 0110 "6" 010 "4" 11110 "." 001 "+" 11011 " " 000 "1" 111111 "3" 1110 "8" 111110 "5" 1100 "7" 110101 "2" 0111 "9" 110100 8.2.3 Ph­¬ng ph¸p LZW Më ®Çu Kh¸i niÖm nÐn tõ ®iÓn ®­îc Jacob 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¶i 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 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 nÐn LZW ®­îc sö dông cho tÊt c¶ c¸c lo¹i file nhÞ ph©n. Nã th­êng ®­îc dïng ®Ó nÐn c¸c lo¹i v¨n b¶n, ¶nh ®en tr¾ng, ¶nh mµu, ¶nh ®a møc x¸m... 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è bit mµu cña ¶nh. 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 s¾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 v« h¹n vµ ®Ó ®¶m b¶o 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: 0  0    1  1    ...  ...    ...  ...    255  255    256  256  (Clear Code)   257  257  (End Of Information)   258  Chuçi    259  Chuçi    ...  ...    ...  ...    4095  Chuçi    + 256 tõ m· ®Çu tiªn theo thø tù tõ 0...255 chøa c¸c sè nguyªn tõ 0...255. §©y lµ m· cña 256 kÝ tù c¬ b¶n trong b¶ng m· ASCII. + Tõ m· thø 256 chøa mét m· ®Æc biÖt lµ "m· xo¸" (CC - Clear Code). Môc ®Ých viÖc dïng m· xo¸ nh»m kh¾c phôc t×nh tr¹ng 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· xo¸ ®Ó b¸o hiÖu kÕt thóc 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· xo¸ 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 mét ¶nh sÏ ®­îc m· ho¸ riªng. Ch­¬ng 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 c¸c 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 biÓu diÔn bëi 12 bit. VÝ dô minh ho¹ c¬ chÕ nÐn cña LZW Cho chuçi ®Çu vµo lµ "ABCBCABCABCD" (M· ASCII cña A lµ 65, B lµ 66, C lµ 67). Tõ ®iÓn ban ®Çu ®· gåm 256 kÝ tù c¬ b¶n. §Çu vµo  §Çu Ra  Thùc hiÖn   A (65)   A ®· cã trong tõ ®iÓn ( §äc tiÕp   B (66)  65  Thªm vµo tõ ®iÓn m· 258 ®¹i diÖn cho chuçi AB   C (67)  66  Thªm vµo tõ ®iÓn m· 259 ®¹i diÖn cho chuçi BC   B  67  Thªm vµo tõ ®iÓn m· 260 ®¹i diÖn cho chuçi CB   C   BC ®· cã trong tõ ®iÓn ( §äc tiÕp   A  259  Thªm vµo tõ ®iÓn m· 261 ®¹i diÖn cho chuçi BCA   B   AB ®· cã trong tõ ®iÓn ( §äc tiÕp   C  258  Thªm vµo tõ ®iÓn m· 262 ®¹i diÖn cho chuçi ABC   A  67  Thªm vµo tõ ®iÓn m· 263 ®¹i diÖn cho chuçi CA   B   AB ®· cã trong tõ ®iÓn ( §äc tiÕp   C   ABC ®· cã trong tõ ®iÓn ( §äc tiÕp   D  262  Thªm vµo tõ ®iÓn m· 263 ®¹i diÖn cho chuçi ABCD   Chuç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,63. ThuËt to¸n - Gi¸ trÞ cê INPUT = TRUE khi vÉn cßn d÷ liÖu ®Çu vµo vµ ng­îc l¹i. - Chøc n¨ng cña c¸c hµm: ( InitDictionary() : Hµm nµy cã chøc n¨ng khëi t¹o tõ ®iÓn. §Æt gi¸ trÞ cho 256 phÇn tö ®Çu tiªn. G¸n m· xo¸ (Clear Code) cho phÇn tö thø 256 vµ m· kÕt thóc th«ng tin (End Of Information) cho phÇn tö thø 257. Xo¸ gi¸ trÞ tÊt c¶ c¸c phÇn tö cßn l¹i. ( Hµm Output() : göi chuçi bit ra file. Chuçi bit nµy cã ®é dµi lµ 9,10,11 hoÆc 12 tuú thuéc vµo vÞ trÝ trong tõ ®iÓn cña tõ m· göi ra.C¸c chuçi bit nµy ®­îc nèi tiÕp vµo víi nhau. ( Hµm GetNextChar(): Tr¶ vÒ mét kÝ tù tõ chuçi kÝ tù ®Çu vµo. Hµm nµy cËp nhËt gi¸ trÞ cña cê INPUT x¸c ®Þnh xem cßn d÷ liÖu ®Çu vµo n÷a hay kh«ng. ( Hµm AddtoDictionary() sÏ ®­îc gäi khi cã mét mÉu míi xuÊt hiÖn. Hµm nµy sÏ cËp nhËt mÉu nµy vµo phÇn tö tiÕp theo trong tõ ®iÓn. NÕu tõ ®iÓn ®· ®Çy nã sÏ göi ra m· xo¸(Clear Code) vµ gäi ®Õn hµm InitDictionary() ®Ó khëi t¹o l¹i tõ ®iÓn. ( Hµm Code(): Tr¶ vÒ tõ m· øng víi mét chuçi. T­ t­ëng cña ®o¹n m· trªn cã thÓ hiÓu nh­ sau: NÕu cßn d÷ liÖu ®Çu vµo th× tiÕp tôc ®äc. Mét chuçi míi sÏ ®­îc t¹o ra tõ chuçi cò(chuçi nµy ban ®Çu trèng, chuçi nµy ph¶i lµ chuçi ®· tån t¹i trong tõ ®iÓn) vµ kÝ tù võa ®äc vµo. Sau ®ã kiÓm tra xem chuçi míi ®· cã trong tõ ®iÓn hay ch­a. Môc ®Ých cña c«ng viÖc nµy lµ hi väng t×m ®­îc chuçi cã sè kÝ tù lín nhÊt ®· tån t¹i trong tõ ®iÓn. NÕu tån t¹i ta l¹i tiÕp tôc ®äc mét kÝ tù tiÕp theo vµ lÆp l¹i c«ng viÖc. NÕu ch­a cã trong tõ ®iÓn, th× göi chuçi cò ra ngoµi vµ thªm chuçi míi vµo tõ ®iÓn. Cã thÓ xem l¹i phÇn vÝ dô ®Ó hiÓu râ h¬n. H×nh 8.3. S¬ ®å thuËt to¸n nÐn LZW Gi¶i nÐn d÷ liÖu nÐn b»ng LZW Gi¶i thuËt gi¶i nÐn gÇn nh­ ng­îc víi gi¶i thuËt nÐn . Víi gi¶i thuËt nÐn, mét tõ m· øng víi mét chuçi sÏ ®­îc ghi ra tÖp khi chuçi ghÐp bëi chuçi trªn víi kÝ tù võa ®äc ch­a cã mÆt trong tõ ®iÓn. Ng­êi ta còng cËp nhËt ngay vµo tõ ®iÓn tõ m· øng víi chuçi t¹o bëi chuçi cò víi kÝ tù võa ®äc. KÝ tù nµy ®ång thêi lµ kÝ tù ®Çu tiªn trong chuçi øng víi tõ m· sÏ ®­îc ghi ra tiÕp theo. §©y lµ ®iÓm mÊu chèt cho phÐp x©y dùng thuËt to¸n gi¶i nÐn. ThuËt to¸n ®­îc m« t¶ nh­ sau: while(GetNextCode() != EOI) do Begin if FIRST_CODE /* M· ®Çu tiªn cña mçi m¶nh ¶nh*/ Then Begin OutBuff(code); OldStr := code; End; If code = CC /* M· xo¸*/ Then Begin InitDictionary(); FIRST_CODE = TRUE; End; NewStr := DeCode(code); OutBuff(NewStr); OldString = OldStr + FirstChar(NewStr); AddtoDictionary(OldStr); OldString := NewStr; End; + Gi¸ trÞ cê FIRST_CODE = TRUE chØ m· võa ®äc lµ m· ®Çu tiªn cña mçi m¶nh ¶nh. M· ®Çu tiªn cã c¸ch xö lÝ h¬i kh¸c so víi c¸c m· tiÕp theo. + M· CC b¸o hiÖu hÕt mét m¶nh ¶nh. M· EOI b¸o hiÖu hÕt toµn bé th«ng tin ¶nh. +Chøc n¨ng cña c¸c hµm: ( GetNextCode() : Hµm nµy ®äc th«ng tin ®Çu vµo(d÷ liÖu nÐn) tr¶ vÒ m· t­¬ng øng. Chóng ta nhí l¹i r»ng, d÷ liÖu nÐn gåm chuçi c¸c tõ m· nèi tiÕp nhau. Ban ®Çu lµ 9 bit, sau ®ã t¨ng lªn 10 bit råi 11, 12 bit. NhiÖm vô cña hµm nµy kh«ng ph¶i ®¬n gi¶n. §Ó biÕt ®­îc t¹i thêi ®iÓm hiÖn thêi, tõ m· dµi bao nhiªu bit ta ph¶i lu«n theo dâi tõ ®iÓn vµ cËp nhËt ®é dµi tõ m· t¹i c¸c phÇn tö thø 512, 1024, 2048. ( OutBuff() Hµm nµy göi chuçi gi¸ trÞ ®· gi¶i m· ra vïng nhí ®Öm. ( DeCode() Hµm nµy tra cøu tõ ®iÓn vµ tr¶ vÒ chuçi kÝ tù t­¬ng øng víi tõ m·. ( FirstChar() LÊy kÝ tù ®Çu tiªn cña mét chuçi. KÝ tù võa x¸c ®Þnh nèi tiÕp vµo chuçi kÝ tù cò (®· gi¶i m· ë b­íc tr­íc) ta ®­îc chuçi kÝ tù cã mÆt trong tõ ®iÓn khi nÐn. Chuçi nµy sÏ ®­îc thªm vµo tõ ®iÓn gi¶i nÐn. ( Hµm Output() : göi chuçi bit ra file. Chuçi bit nµy cã ®é dµi lµ 9,10,11 hoÆc 12 tuú thuéc vµo vÞ trÝ trong tõ ®iÓn cña tõ m· göi ra.C¸c chuçi bit nµy ®­îc nèi tiÕp vµo víi nhau. Tr­êng hîp ngo¹i lÖ vµ c¸ch xö lý §èi víi gi¶i thuËt LZW tån t¹i mét tr­êng hîp ®­îc sinh ra nh­ng ch­¬ng tr×nh gi¶i nÐn cã thÓ kh«ng gi¶i m· ®­îc. Gi¶ sö c lµ mét kÝ tù, S lµ mét chuçi cã ®ä dµi lín h¬n 0. NÕu m· k cña tõ ®iÓn chøa gi¸ trÞ lµ cS. Chuçi ®Çu vµo lµ cScS. Khi ®äc ®Õn cSc ch­¬ng tr×nh sÏ t¹o m· k' chøa cSc. Ngay sau ®ã k' ®­îc dïng thay thÕ cho cSc. Trong ch­¬ng tr×nh gi¶i nÐn, k' sÏ xuÊt hiÖn tr­íc khi nã ®­îc ®Þnh nghÜa. RÊt may lµ tõ m· võa ®äc trong tr­êng hîp nµy bao giê còng cã néi dung trïng víi tæ hîp cña tõ m· cò víi kÝ tù ®Çu tiªn cña nã. §iÒu nµy gióp cho qu¸ tr×nh cµi ®Æt ch­¬ng tr×nh kh¾c phôc ®­îc tr­êng hîp ngo¹i lÖ mét c¸ch dÔ dµng. 8.2.4 Ph­¬ng ph¸p m· ho¸ khèi (Block Coding) Nguyªn t¾c Ph­¬ng ph¸p nµy lóc ®Çu ®­îc ph¸t triÓn cho ¶nh sè 2 møc x¸m, sau ®ã hoµn thiÖn thªm bëi c¸c ph­¬ng ph¸p thÝch nghi vµ më réng cho ¶nh sè ®a cÊp x¸m. Cho mét ¶nh sè I(x,y) kÝch th­íc M x N. Ng­êi ta chia nhá ¶nh sè thµnh c¸c khèi h×nh ch÷ nhËt kÝch th­íc k x l, (k,l) lµ rÊt nhá so víi M, N. Nh­ vËy ¶nh gèc coi nh­ gåm c¸c khèi con xÕp c¹nh nhau vµ cã N x M / (k x l) khèi con. Ta cã thÓ dïng ph­¬ng ph¸p m· ho¸ Huffman cho tõng khèi cña ¶nh gèc, nghÜa lµ g¸n cho mçi tõ khèi mét tõ m· nhÞ ph©n nh­ ë phÇn trªn. Mét khã kh¨n gÆp ph¶i khi dïng m· ho¸ tèi ­u Huffman ®ã lµ sè l­îng khèi qu¸ lín. Gi¶i ph¸p ë ®©y lµ dïng m· ho¸ gÇn tèi ­u, ®¬n gi¶n h¬n ®Ó thùc hiÖn m· ho¸. Ta gi¶ thiÕt c¸c khèi lµ ®éc lËp víi nhau vµ sè cÊu h×nh lµ 2kl. Gäi p(i,k,l) lµ s¸c xuÊt xuÊt hiÖn cÊu h×nh i, entropy t­¬ng øng lµ: H(k,l) = -
p(i,k,l)log2P(i,k,l) Gi¸ trÞ H(k,l) cã thÓ diÔn gi¶i lµ sè bit/ khèi. C¸c tõ m· g¸n cho c¸c khèi k x l ®­îc t¹o bëi c¸c ®iÓm tr¾ng (cÊu h×nh tréi) lµ "0". C¸c tõ m· g¸n cho c¸c khèi k x l kh¸c gåm kxl bit mµu ("1" cho ®en, "0" cho tr¾ng) ®i tiÕp sau 1 bit tiÒn tè "1". ViÖc m· ho¸ theo khèi còng ®­îc sö dông nhiÒu trong c¸c ph­¬ng ph¸p kh¸c nh­ ph­¬ng ph¸p dïng biÕn ®æi sÏ tr×nh bµy trong phÇn 8.3 ®Ó gi¶m bít kh«ng gian l­u tr÷. ThuËt to¸n Gi¶ sö p(0,k,l) x¸c suÊt cña khèi chØ t¹o bëi c¸c ®iÓm tr¾ng lµ ®· biÕt, t û sè nÐn cã thÓ tÝnh ®­îc dÔ dµng. X¸c suÊt nµy cã thÓ ®­îc thiÕt lËp bëi m« h×nh lý thuyÕt cho mét kiÓu khèi ®Æc biÖt. Do vËy, ta chia khèi lµm 2 lo¹i: Khèi 1 chiÒu vµ khèi 2 chiÒu. Khèi 1 chiÒu S¸c xuÊt p(0,k,l) tÝnh ®­îc nhê vµo m« h×nh cña qu¸ tr×nh markov bËc mét. Qu¸ tr×nh nµy ®­îc biÓu diÔn nhê ma trËn dÞch chuyÓn tr¹ng th¸i ( : ( = p(t/t) p(®/t) (8.1) p(t/®) p(®/®) víi : - p(t/t) lµ s¸c xuÊt cã ®iÒu kiÖn tr¾ng sang tr¾ng, - p(®/®) lµ s¸c xuÊt cã ®iÒu kiÖn ®en sang ®en. C¸c x¸c suÊt kh¸c cã ý nghÜa t­¬ng tù. Nh­ vËy: p(0,k,1) = p(t)p(t/t)k-1. (8.2) §iÒu nµy cã thÓ gi¶i thÝch nh­ sau: s¸c xuÊt xuÊt hiÖn mét khèi k x 1 chØ gåm c¸c ®iÓm tr¾ng b»ng s¸c xuÊt xuÊt hiÖn 1 ®iÓm tr¾ng tiÕp theo k-1 dÞch chuyÓn tr¾ng sang tr¾ng. Dùa vµo c¸c quan hÖ trªn, ta tÝnh ®­îc tû sè nÐn Cr. 1 Cr = (8.3) k[1-p(t))p(t/t)k-1]+1 Khèi 2 chiÒu S¸c xuÊt p(0,k,l) cña c¸c khèi toµn tr¾ng còng tÝnh ®­îc mét c¸ch t­¬ng tù nh­ trªn: p(0,k,l) = p(t)p(t/t)k-1 [p(t/t)p(t/X=t,Y=t)l-1]k-1 (8.4) Mèi quan hÖ nµy t­¬ng ®­¬ng: p(0,k,l) = p(t)p(t/t)k+l+2)p(t/X=t,Y=t)(l-1)(k-1) (8.5) vµ tû sè nÐn sÏ cho bëi c«ng thøc: 1 Cr = (8.6) [1-p(t))p(t/t)k+l-2]+1/kl Thùc tÕ, khi cµi ®Æt ng­êi ta hay chän khèi vu«ng vµ gi¸ trÞ thÝch hîp cña k tõ 4 ®Õn 5. 8.2.5 Ph­¬ng ph¸p thÝch nghi ThuËt ng÷ "thÝch nghi" th­êng dïng ®Ó chØ sù thÝch hîp cña c¸c tõ m· theo mét nghÜa nµo ®Êy. Nh­ trong ph­¬ng ph¸p RLC ë trªn, thay v× dïng chiÒu dµi tõ m· cè ®Þnh m bits, ng­êi ta dïng chiÒu dµi biÕn ®æi vµ trªn c¬ së ®ã cã ph­¬ng ph¸p RLC thÝch nghi. Trong ph­¬ng ph¸p m· ho¸ khèi, ng­êi ta dïng chiÒu dµi khèi cè ®Þnh gåm k x l ®iÓm ¶nh. Tuy nhiªn, víi ¶nh kh«ng thuÇn nhÊt, ph­¬ng ph¸p m· ho¸ nµy béc lé nhiÒu nh­îc ®iÓm. V× r»ng, víi ¶nh kh«ng thuÇn nhÊt, chÝnh sù kh«ng thuÇn nhÊt cña ¶nh quyÕt ®Þnh sù thÝch nghi víi ®iÒu kiÖn côc bé. Mét c¶i tiÕn cho vÊn ®Ò nµy lµ cè ®Þnh mét kÝch th­íc cña khèi, cßn kÝch th­íc kia coi nh­ lµ hµm cña mét t¸c ®éng trung b×nh theo hµng (víi l=1) hay theo mét nhãm hµng (l > 1). T¸c ®éng ®­îc quan t©m còng gièng nh­ c¸c ph­¬ng ph¸p trªn lµ sù dÞch chuyÓn c¸c ®iÓm tr¾ng sang ®en trªn hµng. Mét c¸ch lý thuyÕt , ng­êi ta còng tÝnh ®­îc gi¸ trÞ tèi ­u cña k (kotp): kotp =
l=1 vµ N lµ sè ®iÓm ¶nh trªn hµng (8.7) ( lT l > 1 Trªn c¬ së nµy, ng­êi ta ¸p dông m· ho¸ khèi tù ®éng thÝch nghi cho mét sè øng dông [6]: - M· ®äan hay khèi k x 1 tù ®éng thÝch nghi víi t¸c ®éng côc bé. - M· ®äan hay khèi k x 1 tù ®éng thÝch nghi 1 chiÒu. - M· khèi k x l tù ®éng thÝch nghi 2 chiÒu. 8.3 ph­¬ng ph¸p m· ho¸ dùa vµo biÕn ®æi thÕ hÖ thø nhÊt Tuy r»ng b¶n chÊt cña c¸c ph­¬ng ph¸p nÐn dùa vµo biÕn ®æi rÊt kh¸c víi c¸c ph­¬ng ph¸p ®· tr×nh bµy ë trªn, song theo ®Þnh nghÜa ph©n lo¹i nÐn, nã vÉn ®­îc xÕp vµo hä thø nhÊt. V× cã c¸c ®Æc thï riªng nªn chóng ta xÕp riªng trong phÇn nµy. 8.3.1 Nguyªn t¾c chung Nh­ trong 8.1.3, c¸c ph­¬ng ph¸p m· ho¸ dùa vµo biÕn ®æi lµm gi¶m l­îng th«ng tin d­ thõa kh«ng t¸c ®éng lªn miÒn kh«ng gian cña ¶nh sè mµ t¸c ®éng lªn miÒn biÕn ®æi. C¸c biÕn ®æi ®­îc dïng ë ®©y lµ c¸c biÕn ®æi tuyÕn tÝnh nh­: biÕn ®æi KL, biÕn ®æi Fourrier, biÕn ®æi Hadamard, Sin, Cosin, v,...,v. V× ¶nh sè th­êng cã kÝch th­íc rÊt lín, nªn trong cµi ®Æt ng­êi ta th­êng chia ¶nh thµnh c¸c khèi ch÷ nhËt nhá nh­ ®· nãi trong 8.2.3. Thùc tÕ, ng­êi ta dïng khèi vu«ng kÝch th­íc cì 16 x 16. Sau ®ã tiÕn hµnh biÕn ®æi tõng khèi mét c¸ch ®éc lËp. Chóng ta ®· biÕt (xem ch­¬ng Ba), d¹ng chung cña biÕn ®æi tuyÕn tÝnh 2 chiÒu lµ: X(m,n) =
a(m,n,k,l)x(k,l) (8.8) víi: - x(k,l) lµ tÝn hiÖu vµo - a(m,n,k,l) lµ c¸c hÖ sè cña biÕn ®æi - lµ phÇn tö cña ma trËn biÕn ®æi A. Ma trËn nµy gäi lµ nh©n cña biÕn ®æi. C¸ch x¸c ®Þnh c¸c hÖ sè nµy lµ phô thuéc vµo tõng lo¹i biÕn ®æi sö dông. §èi víi phÇn lín c¸c biÕn ®æi 2 chiÒu, nh©n cã tÝnh ®èi xøng vµ t¸ch ®­îc: A[m,n,k,l] = A'[m,k] A"[n,l] Nh­ ®· chØ ra trong 3.2.3, nÕu biÕn ®æi lµ KL th× c¸c hÖ sè ®ã chÝnh lµ c¸c phÇn tö cña vÐc t¬ riªng. 8.3.2 ThuËt to¸n m· ho¸ dïng biÕn ®æi 2 chiÒu C¸c ph­¬ng ph¸p m· ho¸ dïng biÕn ®æi 2 chiÒu th­êng gåm 4 b­íc sau: b1) Chia ¶nh thµnh khèi ¶nh ®­îc chia thµnh c¸c khèi nhá kÝch th­íc k x l vµ biÕn ®æi c¸c khèi ®ã mét c¸ch ®éc lËp ®Ó thu ®­îc c¸c khèi Vi, i=0,1,...,B víi B = N x M / (k x l). b2) X¸c ®Þnh ph©n phèi bit cho tõng khèi Th­êng c¸c hÖ sè hiÖp biÕn cña c¸c biÕn ®æi lµ kh¸c nhau. Mçi hÖ sè yªu cÇu l­îng ho¸ víi mét sè l­îng bit kh¸c nhau. b3) ThiÕt kÕ bé l­îng ho¸ Víi phÇn lín c¸c biÕn ®æi, c¸c hÖ sè v(0,0) lµ kh«ng ©m. C¸c hÖ sè cßn l¹i cã trung b×nh 0. §Ó tÝnh c¸c hÖ sè, ta cã thÓ dïng ph©n bè Gauss hay Laplace. C¸c hÖ sè ®­îc m· ho¸ bëi sè bit kh¸c nhau, th­êng tõ 1 ®Õn 8 bit. Do vËy cÇn thiÕt kÕ 8 bé l­îng ho¸. §Ó dÔ cµi ®Æt, tÝn hiÖu vµo v1(k,l) ®­îc chuÈn ho¸ ®Ó cã d¹ng: v1(k,l) = v1(k,l)/(k,l (k,l) ( (0,0) (8.9) Tr­íc khi thiÕt kÕ bé l­îng ho¸, ng­êi ta t×m c¸ch lo¹i bá mét sè hÖ sè kh«ng cÇn thiÕt. b4) M· ho¸ TÝn hiÖu ®Çu ra cña bé l­îng ho¸ sÏ ®­îc m· ho¸ trªn c¸c tõ bit ®Ó truyÒn ®i hay l­u tr÷ l¹i. Qu¸ tr×nh m· ho¸ dùa vµo biÕn ®æi cã thÓ ®­îc tãm t¾t trªn h×nh 8-3 d­íi ®©y. NÕu ta chän phÐp biÕn ®æi KL cho ph­¬ng ph¸p sÏ cã mét sè nh­îc ®iÓm: Khèi l­îng tÝnh to¸n sÏ rÊt lín v× ph¶i tÝnh ma trËn hiÖp biÕn, tiÕp sau lµ ph¶i gi¶i ph­¬ng tr×nh t×m trÞ riªng vµ vÐc t¬ riªng ®Ó x¸c ®Þnh c¸c hÖ sè. V× lý do nµy, trªn thùc tÕ ng­êi ta thÝch dïng c¸c biÕn ®æi kh¸c nh­ Hadamard, Haar, Sin vµ Cosin. Trong sè biÕn ®æi nµy, biÕn ®æi Cosin th­êng hay ®­îc dïng h¬n. q p U AUAT V L­îng ho¸ V M· ho¸ U A-1VA* V Gi¶i m· L­u Tr÷/TruyÒn q p H×nh 8.4. M· ho¸ vµ gi¶i m· bëi m· ho¸ biÕn ®æi 8.3.3 M· ho¸ dïng biÕn ®æi Cosin vµ chuÈn JPEG 8.3.3.1 PhÐp biÕn ®æi Cosin mét chiÒu PhÐp biÕn ®æi Cosin rêi r¹c (DCT) ®­îc Ahmed ®­a ra vµo n¨m 1974. KÓ tõ ®ã ®Õn nay nã ®­îc øng dông rÊt réng r·i trong nhiÒu ph­¬ng thøc m· ho¸ ¶nh kh¸c nhau nhê hiÖu suÊt gÇn nh­ tèi ­u cña nã ®èi víi c¸c ¶nh cã ®é t­¬ng quan cao gi÷a c¸c ®iÓm ¶nh l©n cËn. BiÕn ®æi Cosin rêi r¹c ®­îc sö dông trong chuÈn ¶nh nÐn JPEG vµ ®Þnh d¹ng phim MPEG. PhÐp biÕn ®æi Cosine mét chiÒu PhÐp biÕn ®æi Cosin rêi r¹c mét chiÒu ®­îc ®Þnh nghÜa bëi: Trong ®ã:
Khi d·y ®Çu vµo x(n) lµ thùc th× d·y c¸c hÖ sè X(k) còng lµ sè thùc. TÝnh to¸n trªn tr­êng sè thùc gi¶m ®i mét nöa thêi gian so víi biÕn ®æi Fourier. §Ó ®¹t ®­îc tèc ®é biÕn ®æi tho¶ m·n yªu cÇu cña c¸c øng dông thùc tÕ, ng­êi ta ®· c¶i tiÕn kÜ thuËt tÝnh to¸n vµ ®­a ra nhiÒu thuËt to¸n biÕn ®æi nhanh Cosine. Mét trong nh÷ng thuËt to¸n ®ã ®­îc giíi thiÖu d­íi ®©y. PhÐp biÕn ®æi Cosin nhanh PhÐp biÕn ®æi Cosin nhanh viÕt t¾t lµ FCT (Fast Cosine Transform), dùa vµo ý t­ëng ®­a bµi to¸n ban ®Çu vÓ tæ hîp cña c¸c bµi to¸n biÕn ®æi FCT trªn c¸c d·y con. ViÖc tiÕn hµnh biÕn ®æi trªn c¸c d·y con sÏ ®¬n gi¶n h¬n rÊt nhiÒu so víi d·y gèc. V× thÕ, ng­êi ta tiÕp tôc ph©n nhá d·y tÝn hiÖu ®Õn khi chØ cßn mét phÇn tö. Gi¶i thuËt biÕn ®æi Cosin nhanh kh«ng thùc hiÖn trùc tiÕp trªn d·y tÝn hiÖu ®Çu vµo x(n) mµ thùc hiÖn trªn d·y x'(n) lµ mét ho¸n vÞ cña x(n). Gi¶ thiÕt sè ®iÓm cÇn tÝnh FCT lµ luü thõa cña 2: N = 2M. D÷ liÖu vµo x(n) sÏ ®­îc s¾p xÕp l¹i nh­ sau:
víi

víi
Nh­ vËy nöa ®Çu d·y x'(n) lµ c¸c phÇn tö chØ sè ch½n cña x(n) xÕp theo chiÒu t¨ng dÇn cña chØ sè. Nöa sau cña x'(n) lµ c¸c phÇn tö chØ sè lÎ cña x(n) xÕp theo chiÒu gi¶m dÇn cña chØ sè. Thay vµo c«ng thøc (8.10) ta ®­îc: Rót gän biÓu thøc trªn ta ®­îc: Chia X(k) ra lµm hai hai d·y, mét d·y bao gåm c¸c chØ sè ch½n, cßn d·y kia bao gåm c¸c chØ sè lÎ. PhÇn chØ sè ch½n: Cã thÓ chuyÓn vÒ d¹ng: (8.11) PhÇn chØ sè lÎ Cã thÓ biÓu diÔn d­íi d¹ng: Ta cã:
Do vËy (8.12) trë thµnh: (8.13) §Æt :

Ta thu ®­îc: (8.14) Cã thÓ nhËn ra ngay c¸c c«ng thøc (8.14) (8.15) lµ phÐp biÕn ®æi Cosin N/2 ®iÓm cña g(n) vµ h(n). Nh­ vËy bµi to¸n biÕn ®æi Cosine cña d·y x'(n) ®· ®­îc ®­a vÒ hai bµi to¸n biÕn ®æi Cosine cña hai d·y con lµ g(n) vµ h(n) cã kÝch th­íc b»ng mét nöa x'(n). Hai d·y g(n) vµ h(n) tÝnh to¸n ®­îc mét c¸ch dÔ dµng. g(n) lµ tæng cña nöa ®Çu d·y x'(n) víi nöa sau cña nã. h(n) lµ hiÖu cña nöa ®Çu d·y x'(n) víi nöa sau cña nã sau ®ã ®em nh©n víi 2CNn. Ta lÆp l¹i qu¸ tr×nh chia ®«i ®èi víi c¸c d·y con, d·y con cña d·y con vµ cø tiÕp tôc chia nh­ thÕ. Gièng nh­ biÕn ®æi Fourier, mçi b­íc lÆp còng ®­îc coi lµ mét tÇng ph©n chia. Víi N = 2M th× sè tÇng ph©n chia lµ M. §Ó dÔ h×nh dung, ®Çu ra cña mçi tÇng ®­îc kÝ hiÖu lµ Xm(n) víi m lµ tÇng hiÖn thêi. Ta xem x'(n) lµ biÕn ®æi Cosin 0 tÇng cña x'(n):
XM(n) lµ biÕn ®æi Cosin tÇng M cña x(n), nã kh«ng ph¶i lµ X(k). Bëi v× cø sau mçi tÇng, kh«ng chØ thø tù c¸c phÇn tö trong X(k) bÞ x¸o trén mµ c¸c X(2k+1) cßn ®­îc céng víi X(2k-1). §Çu ra cña mét tÇng lµ ®Çu vµo cña tÇng tiÕp theo.
víi

víi
Tõ c«ng thøc tÝnh g(n) vµ h(n) ta cã: víi
Cø sau mçi tÇng, sè d·y con l¹i ®­îc nh©n ®«i. XÐt phÐp biÕn ®æi t¹i tÇng thø m , chóng ta ph¶i lÆp l¹i c«ng viÖc biÕn ®æi cho 2m-1 d·y con. Mçi d·y con ®ãng vai trß nh­ d·y x'(n) trong tÇng thø nhÊt. Sè phÇn tö trong mét d·y lµ:
.C«ng ®o¹n biÕn ®æi trªn mét d·y con gäi lµ mét khèi biÕn ®æi. Mçi d·y con sÏ tiÕp tôc ®­îc ph©n lµm hai d·y nhá h¬n. C«ng thøc tæng qu¸t t¹i mçi khèi lµ: Víi
, trong ®ã k = 0,1,...,2m-1 PhÇn x©y dùng c«ng thøc tæng qu¸t trong phÐp biÕn ®æi nhanh Fourier ®­îc tr×nh bµy kh¸ chi tiÕt ë trªn chóng ta cã thÓ xem l¹i phÇn nµy ®Ó hiÓu h¬n vÒ c«ng thøc tæng qu¸t cho mét khèi biÕn ®æi nhanh Cosin. ThuËt to¸n biÕn ®æi nhanh Cosin cã thÓ m« t¶ b»ng c¸c b­íc sau: B­íc 1: TÝnh d·y hÖ sè Cji. X¸c ®Þnh sè tÇng M = log2N. TÇng hiÖn thêi m=1. B­íc 2: NÕu m ( M thùc hiÖn b­íc 3. NÕu kh«ng kÕt thóc. (Ch­a hÕt c¸c tÇng) B­íc 3: Khèi hiÖn thêi k = 0. B­íc 4: NÕu k < 2m-1 Thùc hiÖn b­íc 5. NÕu kh«ng thùc hiÖn b­íc 6. (Ch­a hÕt c¸c khèi trong mét tÇng) B­íc 5: TÝnh to¸n Xm(i) trong khèi theo c«ng thøc tæng qu¸t (8.16), (8.17). T¨ng k lªn 1. Quay vÒ b­íc 4. (ChuyÓn ®Õn khèi tiÕp theo) B­íc 6: T¨ng m lªn 1. Quay vÒ b­íc 2 (ChuyÓn ®Õn tÇng tiÕp theo) Mét sè vÊn ®Ò l­u ý khi cµi ®Æt thuËt to¸n biÕn ®æi Cosin nhanh Kh¸c víi biÕn ®æi Fourier nhanh, trong biÕn ®æi Cosin, x(n) kh«ng ph¶i ®Çu vµo trùc tiÕp vµ X(k) kh«ng ph¶i lµ ®Çu ra trùc tiÕp. ë ®Çu vµo, x'(n) chØ lµ c¸ch s¾p xÕp l¹i x(n). Chóng ta biÕt r»ng t¹i mçi tÇng, ®èi víi mçi khèi:
Nªn ë ®Çu ra, sau khi tÝnh ®­îc XM(n) chóng ta ph¶i thùc hiÖn viÖc trõ truy håi tõ tÇng M vÒ tÇng 1 sau ®ã ho¸n vÞ l¹i theo thø tù ®¶o bit míi thu ®­îc hÖ sè biÕn ®æi X(k) cÇn tÝnh. Bµi to¸n s¾p xÕp l¹i theo thø tù ®¶o bit ®· ®Ò cËp trong phÇn biÕn ®æi Fourier. Bµi to¸n trõ truy håi cµi ®Æt kh¸ ®¬n gi¶n. D·y hÖ sè Cji ®­îc tÝnh tr­íc mét lÇn. Trong c¸c øng dông mµ sè ®iÓm tÝnh FCT kh«ng ®æi hoÆc chØ nhËn mét sè gi¸ trÞ cô thÓ, ng­êi ta th­êng tÝnh tr­íc Cji vµ ghi ra file. Khi thùc hiÖn biÕn ®æi th× ®äc tõ file ®Ó lÊy th«ng tin nµy. Trong øng dông cña chóng ta, ta tÝnh tr­¬c Cji vµ l­u vµo mét m¶ng. PhÐp biÕn ®æi sÏ truy cËp b¶ng nµy ®Ó lÊy hÖ sè cÇn thiÕt. PhÐp biÕn ®æi Cosin ng­îc PhÐp biÕn ®æi Cosin ng­îc ®­îc ®Þnh nghÜa b»ng c«ng thøc: (8.18) Víi
PhÐp biÕn ®æi Cosin ng­îc sÏ ®­îc thùc hiÖn theo chiÒu ng­îc l¹i víi quy tr×nh ®· iÕn hµnh trong phÐp biÕn ®æi nhanh. Tuy nhiªn, c«ng viÖc nµy kh«ng ®­îc thuËn lîi nh­ phÐp biÕn ®æi FFT ng­îc. Tõ X(k) chóng ta ph¶i kh«i phôc l¹i XM(n) b»ng c¸ch thùc hiÖn c¸c phÐp céng truy håi vµ phÐp ho¸n vÞ theo thø tù ®¶o bit. C«ng thøc tæng qu¸t cho mçi khèi biÕn ®æi ng­îc ®­îc x©y dùng dùa trªn c«ng thøc tæng qu¸t trong biÕn ®æi xu«i: Víi
, trong ®ã k = 0,1,...,2m-1 PhÐp biÕn ®æi ng­îc ph¶i cµi ®Æt riªng. Tuy vËy, t­ t­ëng chÝnh cña hai bµi to¸n xu«i vµ ng­îc vÒ c¬ b¶n gièng nhau. §Çu ra cña phÐp biÕn ®æi ng­îc sÏ lµ x'(n). Muèn thu ®­îc x(n) ta ph¶i ®¶o l¹i vÞ trÝ. 8.3.3.2 PhÐp biÕn ®æi Cosin rêi r¹c hai chiÒu PhÐp biÕn ®æi Cosin rêi r¹c hai chiÒu ®­îc ®Þnh nghÜa bëi: (8.21) Trong ®ã,
khi k1 = 0 vµ
khi k1 = 1,2,...,N1-1
khi k2 = 0 vµ
khi k2 = 1,2,...,N2-1 PhÐp biÕn ®æi ng­îc ®­îc ®Þnh nghÜa bëi c«ng thøc: (8.22)
nhËn c¸c gi¸ trÞ nh­ trong c«ng thøc biÕn ®æi xu«i. §Ó n©ng cao tèc ®é biÕn ®æi ng­êi ta ®· ph¸t triÓn c¸c gi¶i thuËt biÕn ®æi nhanh Cosin hai chiÒu. C¸ch lµm phæ biÕn nhÊt lµ tËn dông phÐp biÕn ®æi nhanh Cosin mét chiÒu. Ta biÕn ®æi c«ng thøc (2.21) vÒ d¹ng: §Æt: (8.23) C«ng thøc (8.23) trë thµnh: (8.25) C«ng thøc (8.24) lµ phÐp biÕn ®æi Cosin rêi r¹c mét chiÒu cña x(n1,n2), trong ®ã n2 lµ biÕn sè, cßn n1 ®ãng vai trß lµ tham sè thu ®­îc kÕt qu¶ trung gian X'(n1,k2). C«ng thøc (8.25) lµ phÐp biÕn ®æi Cosin rêi r¹c cña X'(n1,k2) víi n1 lµ biÕn sè cßn k2 lµ tham sè. §Õn ®©y t­ t­ëng cña thuËt to¸n ®· râ rµng. Khi biÕn ®æi nhanh Cosin hai chiÒu cña mét ma trËn ¶nh, ta sÏ tiÕn hµnh biÕn ®æi nhanh mét chiÒu trªn c¸c ®iÓm ¶nh theo hµng, sau ®ã ®em biÕn ®æi nhanh mét chiÒu theo cét cña kÕt qu¶ võa thu ®­îc. BiÕn ®æi nhanh Cosin ng­îc hai chiÒu còng ®­îc x©y dùng dùa trªn kÕt qu¶ phÐp biÕn ®æi nhanh Cosin ng­îc mét chiÒu. Tõ c«ng thøc (8.22) ta biÓu diÔn l¹i nh­ sau: (8.26) §Æt: (8.27) Khi ®ã c«ng thøc (8.26) sÏ trë thµnh: (8.28) C«ng thøc (8.27) lµ phÐp biÕn ®æi Cosin ng­îc rêi r¹c mét chiÒu cña X(k1,k2), trong ®ã k2 lµ biÕn sè, cßn k1 ®ãng vai trß lµ tham sè thu ®­îc kÕt qu¶ trung gian x'(k1,n2). C«ng thøc (8.28) lµ phÐp biÕn ®æi Cosin ng­îc rêi r¹c cña x'(k1,n2) víi k1 lµ biÕn sè cßn n2 lµ tham sè. Nh­ vËy, muèn kh«i phôc l¹i ¶nh ban ®Çu tõ ma trËn hÖ sè biÕn ®æi chóng ta sÏ biÕn ®æi nhanh Cosin ng­îc rêi r¹c mét chiÒu c¸c hÖ sè theo hµng, sau ®ã ®em biÕn ®æi nhanh Cosin rêi r¹c mét chiÒu theo cét c¸c kÕt qu¶ trung gian võa tÝnh ®­îc. 8.3.3.3 BiÕn ®æi Cosin vµ chuÈn nÐn JPEG JPEG lµ viÕt t¾t cña Joint Photographic Expert Group ( nhãm c¸c chuyªn gia ph¸t triÓn chuÈn ¶nh nµy). ChuÈn JPEG ®­îc c«ng nhËn lµ chuÈn ¶nh quèc tÕ n¨m 1990 phôc vô c¸c øng dông truyÒn ¶nh cho c¸c lÜnh vùc nh­ y häc, khoa häc kÜ thu©t, ¶nh nghÖ thuËt... ChuÈn JPEG ®­îc sö dông ®Ó m· ho¸ ¶nh ®a møc x¸m, ¶nh mµu. Nã kh«ng cho kÕt qu¶ æn ®Þnh l¾m víi ¶nh ®en tr¾ng. ChuÈn JPEG cung cÊp gi¶i thuËt cho c¶ hai lo¹i nÐn lµ nÐn kh«ng mÊt m¸t th«ng tin vµ nÐn mÊt m¸t th«ng tin. Trong phÇn d­íi ®©y, chóng t«i tr×nh bµy chi tiÕt vÒ mét trong c¸c d¹ng nÐn biÕn ®æi chÊp nhËn mÊt m¸t H×nh 8.5 BiÕn ®æi Cosin cña ¶nh (tr¸i) vµ biÕn ®æi ng­îc (¶nh gèc - ph¶i) th«ng tin dïng biÕn ®æi Cosin cña chuÈn JPEG: BiÕn ®æi Cosin tuÇn tù (Sequential DTC-Based). BiÕn ®æi Cosin tuÇn tù lµ kÜ thuËt ®¬n gi¶n nhÊt nh­ng ®­îc dïng phæ biÕn nhÊt vµ nã ®¸p øng ®­îc hÇu hÕt c¸c ®Æc tÝnh cÇn thiÕt cho phÇn lín c¸c øng dông. M· ho¸ JPEG bao gåm nhiÒu c«ng ®o¹n nh­ ®· nªu trong 8.3.3.1. S¬ ®å thuËt to¸n nÐn vµ gi¶i nÐn ®­îc m« t¶ nh­ d­íi ®©y. Qu¸ tr×nh gi¶i nÐn sÏ ®­îc lµm ng­îc l¹i, ng­êi ta gi¶i m· tõng phÇn ¶nh nÐn t­¬ng øng víi ph­¬ng ph¸p nÐn ®· sö dông trong phÇn nÐn nhê c¸c th«ng tin liªn quan ghi trong phÇn header cña file nÐn. KÕt qu¶ thu ®­îc lµ hÖ sè ®· l­îng tö. C¸c hÖ sè nµy ®­îc kh«i phôc vÒ gi¸ trÞ tr­íc khi l­îng tö ho¸ b»ng bé t­¬ng tù ho¸. TiÕp ®ã ®em biÕn ®æi Cosin ng­îc ta ®­îc ¶nh ban ®Çu víi ®é trung thùc nhÊt ®Þnh. B¶ng m· vµ b¶ng l­îng tö trong s¬ ®å gi¶i nÐn ®­îc dùng lªn nhê nh÷ng th«ng tin ghi trong phÇn cÊu tróc ®Çu tÖp (Header) cña tÖp ¶nh nÐn. Qu¸ tr×nh nÐn chÞu tr¸ch nhiÖm t¹o ra vµ ghi l¹i nh÷ng th«ng tin nµy. PhÇn tiÕp theo sÏ ph©n tÝch t¸c dông cña tõng khèi trong s¬ ®å. A. Ph©n khèi ChuÈn nÐn JPEG ph©n ¶nh ra c¸c khèi 8x8. C«ng ®o¹n biÕn ®æi nhanh Cosin hai chiÒu cho c¸c khèi 8x8 tá ra hiÖu qu¶ h¬n. BiÕn ®æi Cosin cho c¸c khèi cã cïng kÝch cì cã thÓ gi¶m ®­îc mét phÇn c¸c tÝnh to¸n chung nh­ viÖc tÝnh hÖ sè Cji . Khi n=8 chóng ta chØ cÇn tÝnh hÖ sè Cji cho 3 tÇng(8= 23), sè c¸c hÖ sè lµ: 4 + 2 + 1 = 7 NÕu víi mét ¶nh 1024 x 1024, phÐp biÕn ®æi nhanh Cosin mét chiÒu theo hµng ngang hoÆc hµng däc ta ph¶i qua 10 tÇng (1024 = 210). Sè c¸c hÖ sè Cji lµ : 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1021. Thêi gian tÝnh c¸c hÖ sè Cji víi toµn bé ¶nh 1024x1024 lín gÊp 150 lÇn so víi thêi gian tÝnh to¸n c¸c hÖ sè nµy cho c¸c khèi. BiÕn ®æi Cosin ®èi víi c¸c khèi cã kÝch th­íc nhá sÏ lµm t¨ng ®é chÝnh x¸c khi tÝnh to¸n víi sè dÊu phÈy tÜnh, gi¶m thiÓu sai sè do lµm trßn sinh ra. Do c¸c ®iÓm ¶nh hµng xãm cã ®é t­¬ng quan cao h¬n, do ®ã phÐp biÕn ®æi Cosin cho tõng khèi nhá sÏ tËp trung n¨ng l­îng h¬n vµo mét sè Ýt c¸c hÖ sè biÕn ®æi. ViÖc lo¹i bít mét sè hÖ sè n¨ng l­îng thÊp trong c¸c khèi chØ t¹o ra mÊt m¸t th«ng tin côc bé gióp n©ng cao chÊt l­îng ¶nh. ¶nh sÏ ®­îc chia lµm B khèi víi:
C¸c khèi ®­îc x¸c ®Þnh bëi bé sè (m,n) víi m = [0..MB-1] vµ n = [0..NB-1], ë ®©y m chØ thø tù cña khèi theo chiÒu réng, n chØ thø tù cña khèi theo chiÒu dµi. Ph©n khèi thùc chÊt lµ x¸c ®Þnh t­¬ng quan gi÷a to¹ ®é riªng trong khèi víi to¹ ®é thùc cña ®iÓm ¶nh trong ¶nh ban ®Çu. NÕu ¶nh ban ®Çu ký hiÖu Image[i,j] th× ma trËn biÓu diÔn khèi (m,n) lµ x[u,v]®­îc tÝnh:
B - BiÕn ®æi BiÕn ®æi lµ mét c«ng ®o¹n lín trong c¸c ph­¬ng ph¸p nÐn sö dông phÐp biÕn ®æi. NhiÖm vô cña c«ng ®o¹n biÕn ®æi lµ tËp trung n¨ng l­îng vµo mét sè Ýt c¸c hÖ sè biÕn ®æi. C«ng thøc biÕn ®æi cho mçi khèi lµ: (8.29) Trong ®ã

ThuËt to¸n biÕn ®æi nhanh Cosin hai chiÒu cho mçi khèi trong tr­êng hîp nµy sÏ bao gåm 16 phÐp biÕn ®æi nhanh Cosin mét chiÒu. §Çu tiªn, ng­êi ta biÕn ®æi nhanh Cosin mét chiÒu cho c¸c d·y ®iÓm ¶nh trªn mçi hµng. LÇn l­ît thùc hiÖn cho 8 hµng. Sau ®ã ®em biÕn ®æi nhanh Cosin mét chiÒu theo tõng cét cña ma trËn võa thu ®­îc sau 8 phÐp biÕn ®æi trªn. Còng lÇn l­ît thùc hiÖn cho 8 cét. Ma trËn cuèi cïng sÏ lµ ma trËn hÖ sè biÕn ®æi cña khèi t­¬ng øng. Gi¶i thuËt biÕn ®æi nhanh ®­îc m« t¶ nh­ h×nh sau: Trong s¬ ®å gi¶i nÐn ta ph¶i dïng phÐp biÕn ®æi Cosin ng­îc. C«ng thøc biÕn ®æi ng­îc cho khèi 8x8: (8.30) Trong ®ã

S¬ ®å biÕn ®æi ng­îc nhanh ®­îc biÓu diÔn nh­ sau: Cã thÓ dÔ dµng quan s¸t ®­îc ®é nh¹t rÊt nhanh cña ¶nh tõ gãc trªn bªn tr¸i xuèng gãc d­íi bªn ph¶i. N¨ng l­îng tËp trung nhÊt vµo ®iÓm (0,0) cña ma trËn hÖ sè biÕn ®æi. H×nh 8.6 BiÕn ®æi FFT xu«i(tr¸i) vµ ng­îc ph¶i C- L­îng tö ho¸ Khèi l­îng tö ho¸ trong s¬ ®å nÐn ®ãng vai trß quan träng vµ quyÕt ®Þnh tØ lÖ nÐn cña chuÈn nÐn JPEG. §Çu vµo cña khèi l­îng tö ho¸ lµ c¸c ma trËn hÖ sè biÕn ®æi Cosin cña c¸c khèi ®iÓm ¶nh. Nguyªn t¾c l­îng ho¸ ®· tr×nh bµy trong 2.2.2. §Ó gi¶m sè bé l­îng tö, ng­êi ta t×m c¸ch quy c¸c hÖ sè ë c¸c khèi vÒ cïng mét kho¶ng ph©n bè. ChuÈn nÐn JPEG chØ sö dông mét bé l­îng tö ho¸. Gi¶ sö r»ng c¸c hÖ sè ®Òu cã hµm tÝnh x¸c suÊt xuÊt hiÖn nh­ nhau. Chóng ta sÏ c¨n chØnh l¹i hÖ sè yj b»ng phÐp g¸n :
Víi (j lµ trung b×nh céng cña hÖ sè thø j. (j lµ ®é lÖch c¬ b¶n cña hÖ sè thø j. Nh­ vË,y chóng ta sÏ ®ång nhÊt ®­îc møc quyÕt ®Þnh vµ møc t¹o l¹i cho tÊt c¶ c¸c hÖ sè. Do ®ã, c¸c hÖ sè sÏ ®­îc biÓu diÔn b»ng cïng mét sè l­îng bit. Cã nhiÒu c¸ch tiÕp cËn ®Ó tÝnh ®­îc c¸c møc quyÕt ®Þnh vµ møc t¹o l¹i. Lloyd – Max ®­a ra gi¶i thuËt sau: B­íc 1: Chän gi¸ trÞ khëi t¹o: d0 = yL dN = yH r0 = d0 N lµ sè møc l­îng tö B­íc 2: Cho i biÕn thiªn tõ 1 ®Õn N-1 thùc hiÖn c¸c c«ng viÖc sau: a. TÝnh di theo c«ng thøc:
b. TÝnh ri theo c«ng thøc:
B­íc 3: TÝnh
B­íc 4: NÕu rN-1 ( r' ®iÒu chØnh l¹i r0 vµ lÆp l¹i tõ b­íc 2 ®Õn b­íc 4. Trong qu¸ tr×nh cµi ®Æt thñ tôc t¹o ra bé l­îng tö ho¸, Lloyd vµ Max ®· cã nhiÒu c¶i tiÕn ®Ó tÝnh to¸n dÔ dµng h¬n. X¸c ®Þnh di b»ng c«ng thøc trong b­íc 2a ®­îc tiÕn hµnh theo ph­¬ng ph¸p Newton-Raphson. Sau ®©y lµ c¸c b­íc m« t¶ toµn bé c«ng viÖc cña khèi l­îng tö ho¸ t¸c ®éng lªn c¸c hÖ sè biÕn ®æi Cosin: B­íc 1: TÝnh trung b×nh céng ( vµ ®é lÖch c¬ b¶n ( cho tõng hÖ sè ë mçi vÞ trÝ trong khèi:

Víi yj lµ hÖ sè thø j, n lµ sè khèi. B­íc 2: Lùa chän tØ lÖ sè hÖ sè gi÷ l¹i trong mét khèi. B­íc 3: Gi÷ l¹i c¸c hÖ sè cã ®é lÖch c¬ b¶n lín h¬n. B­íc 4: LËp ma trËn T sao cho: Tij = 1 nÕu hÖ sè (i,j) ®­îc gi÷ l¹i. B­íc 5: C¨n chØnh l¹i gi¸ trÞ cña c¸c hÖ sè xoay chiÒu ®­îc gi÷ l¹i ë c¸c khèi:
B­íc 6: TÝnh ph©n bè cña c¸c gi¸ trÞ xoay chiÒu ®· c¨n chØnh. B­íc 7: TÝnh ®é lÖch c¬ b¶n (s cña c¸c ph©n bè võa tÝnh. B­íc 8: L­îng tö ho¸ c¸c hÖ sè xoay chiÒu b»ng c¸ch sö dông bé l­îng tö Lloyd-Max sau khi ®· ®iÒu chØnh møc quyÕt ®Þnh vµ møc t¹o l¹i cña nã theo c¸ch sau:


Thµnh phÇn mét chiÒu sÏ kh«ng l­îng tö ho¸. §Õn ®©y, ta chuyÓn sang b­íc nÐn. D - NÐn §Çu vµo cña khèi nÐn gåm hai thµnh phÇn: thµnh phÇn c¸c hÖ sè mét chiÒu vµ thµnh phÇn c¸c hÖ sè xoay chiÒu. Thµnh phÇn c¸c hÖ sè mét chiÒu Ci(0,0) víi i = 0,1,..., 63 chøa phÇn lín n¨ng l­îng tÝn hiÖu h×nh ¶nh. Ng­êi ta kh«ng nÐn trùc tiÕp c¸c gi¸ trÞ Ci(0,0) mµ x¸c ®Þnh ®é lÖch cña Ci(0,0):
di cã gi¸ trÞ nhá h¬n nhiÒu so víi Ci nªn trong biÓu diÔn dÊu phÈy ®éng theo chuÈn IEEE754 th­êng chøa nhiÒu chuçi bit 0 nªn cã thÓ cho hiÖu suÊt nÐn cao h¬n. Gi¸ trÞ C0(0,0) vµ c¸c ®é lÖch di ®­îc ghi ra mét tÖp t¹m. TÖp nµy ®­îc nÐn b»ng ph­¬ng ph¸p nÐn Huffman. Thµnh phÇn c¸c hÖ sè xoay chiÒu Ci(m,n) víi 1 ( m ( 7 , 1 ( n ( 7 chøa c¸c th«ng tin chi tiÕt cña ¶nh. §Ó n©ng cao hiÖu qu¶ nÐn cho mçi bé hÖ sè trong mét khèi ng­êi ta xÕp l¹i chóng theo thø tù ZigZag. Cã thÓ h×nh dung h×nh ZigZag nh­ b¶ng trang bªn. T¸c dông cña s¾p xÕp l¹i theo thø tù ZigZag lµ t¹o ra nhiÒu lo¹t hÖ sè gièng nhau. Chóng ta biÕt r»ng n¨ng l­îng cña khèi hÖ sè gi¶m dÇn tõ gãc trªn bªn tr¸i xuèng gãc d­íi bªn ph¶i nªn viÖc s¾p xÕp l¹i c¸c hÖ sè theo thø tù ZigZag sÏ t¹o ®iÒu kiÖn cho c¸c hÖ sè xÊp xØ nhau(cïng møc l­îng tö) n»m trªn mét dßng. 0  2  3  9  10  20  21  35   1  4  8  11  19  22  34  36   5  7  12  18  23  33  37  48   6  13  17  24  32  38  47  49