Nén dữ liệu Ảnh part 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....
Nội dung trích xuất từ tài liệu:
Nén dữ liệu Ảnh part 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 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 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 ...