intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Nén dữ liệu Ảnh part 1

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

Thêm vào BST
Báo xấu
199
lượt xem 40
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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....

Chủ đề:

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

Lưu

Nội dung Text: Nén dữ liệu Ảnh part 1

  1. 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á 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: 227 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  2. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 1 Tû lÖ nÐn = x% r 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ù 228 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  3. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 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. 229 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  4. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh  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. 230 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  5. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 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. 231 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  6. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 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¸ 232 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  7. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 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 233 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  8. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh 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 234 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  9. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh "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 ... ... 235 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  10. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh ... ... 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. 236 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
  11. Ch­¬ng T¸m: nÐn d÷ liÖu ¶nh §Çu §Çu Thùc hiÖn vµo Ra 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. 237 NhËp m«n xö lý ¶nh sè - §HBK Hµ néi
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2