Xử lý ảnh - chương 8

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].
Nội dung trích xuất từ tài liệu:
Xử lý ảnh - chương 8 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh 8 nÐn d÷ liÖu ¶nh image compression8.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ÖmNÐ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ècvµ 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íid÷ 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ËtnÐ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¸ctµ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ªnth¬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. Trongch¬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¬nn÷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ªnNhËp m«n xö lý ¶nh sè - §HBK Hµ néi 227 Ch¬ng T¸m: nÐn d÷ liÖu ¶nhngµ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¸pnÐ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òngcÇn ®îc quan t©m xem xÐt . Nh×n chung, ngêi ta ®Þnh nghÜa tû lÖ nÐn nh sau: 1 Tû lÖ nÐn = x% rví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ã 1phÇ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ÐnchØ 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µokiÓ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¶ncñ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Ònkh«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Ýnhcñ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íitruyÒ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¹ibá 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 choviÖ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 -NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 228 Ch¬ng T¸m: nÐn d÷ liÖu ¶nh¬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étsè 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Êtcñ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) ® îclÆ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¸pm· 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. DovË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äilµ ph¬ng ph¸p nÐn LZ77, LZ78. N¨m 1984, Terry Welch ®· c¶i tiÕn hiÖu qu¶ h¬nvµ ®Æt tªn lµ LZW (Lempel-Ziv- Welch). Ph ¬ng ph¸p nÐn nµy sÏ ®îc tr×nh bµytrong 8.2.3.• §é d thõa ...