Nén dữ liệu ảnh

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, 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. 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 trng 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 =

1

r

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 trng c¬ b¶n cña

ph¬ng ph¸p nÐn. NhiÒu khi tû lÖ nÐn cao còng cha 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.

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 227

Ch¬ng T¸m: nÐn d÷ liÖu ¶nh

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× lu tr÷ d÷ liÖu, ta chØ cÇn lu 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 trng 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

NhËp m«n xö lý ¶nh sè - §HBK Hµ néi 228