Đồ án Tìm hiểu một số phương pháp nén ảnh

Lêi c¶m ¬n ! Em xin bµy tá lßng biÕt ¬n s©u s¾c nhÊt tíi PGS. TS. Ng« Quèc T¹o, thÇy ®· tËn t×nh h­íng dÉn vµ gióp ®ì em rÊt nhiÒu trong qu¸ tr×nh thùc tËp vµ t×m hiÓu nghiªn cøu ®Ò tµi ®­îc giao ®Ó em cã thÓ hoµn thµnh tèt b¸o c¸o tèt nghiÖp cña m×nh. Em xin ch©n thµnh c¶m ¬n sù d¹y b¶o cña c¸c thÇy gi¸o, c« gi¸o Khoa C«ng NghÖ Th«ng Tin - Tr­êng §¹i häc D©n LËp H¶i Phßng ®· trang bÞ cho em nh÷ng kiÕn thøc c¬ b¶n ®Ó em cã thÓ hoµn thµnh b¸o c¸o tèt nghiÖp vÒ ®Ò tµi ®­îc giao. Trong qu¸ tr×nh nghiªn cøu ®Ò tµi mÆc dï ®· ®­îc c¸c thÇy c« gi¸o h­íng dÉn tËn t×nh nh­ng do nhiÒu nguyªn nh©n chñ quan vµ kh¸ch quan nªn ®Ò tµi kh«ng tr¸nh khái sai sãt .Em rÊt mong ®­îc c¸c thÇy c« gi¸o chØ dÉn ,®ãng gãp nh÷ng ý kiÕn quý b¸u gióp em hoµn thiÖn h¬n b¸o c¸o tèt nghiÖp , ph¸t triÓn vµ më réng ®Ò tµi ®ùoc giao . Em xin ch©n thµnh c¸m ¬n ! H¶i Phßng, ngµy th¸ng n¨m 2007 Sinh viªn T¹ Minh Th¾ng Môc lôc Më ®Çu Ngµy nay, cïng víi sù ph¸t triÓn kh«ng ngõng cña khoa häc vµ c«ng nghÖ th× m¸y tÝnh ®ãng vai trß ngµy cµng quan träng vµ kh«ng thÓ thiÕu trong cuéc sèng x· héi loµi ng­êi. ViÖc trao ®æi th«ng tin cña con ng­êi trong tÊt c¶ c¸c ngµnh, c¸c lÜnh vùc cña ®êi sèng ngµy cµng trë nªn cÇn thiÕt cïng víi sù ra ®êi vµ ph¸t triÓn cña m¹ng Internet. Xö lý ¶nh lµ mét ngµnh khoa häc cßn t­¬ng ®èi míi mÎ so víi nhiÒu ngµnh khoa häc kh¸c nh­ng nã ®ang ®­îc tËp trung nghiªn cøu vµ ph¸t triÓn v× nh÷ng øng dông thùc tiÔn cña nã trong nhiÒu ngµnh , lÜnh vùc kh¸c nhau. Trong ®ã “NÐn ¶nh” lµ mét phÇn cña xö lý ¶nh cã øng dông to lín trong truyÒn th«ng vµ trong l­u tr÷, ®· cã rÊt nhiÒu ph­¬ng ph¸p nÐn ¶nh ®­îc ra ®êi vµ kh«ng ngõng ®­îc c¶i tiÕn ®Ó ngµy cµng hoµn thiÖn ®em l¹i hiÖu qu¶ nÐn cao vµ cho chÊt l­îng ¶nh tèt nhÊt. Trong ®å ¸n tèt nghiÖp “T×M hiÓu mét sè ph­¬ng ph¸p nÐn ¶nh” ®­îc sù h­íng dÉn cña PGS .TS . Ng« Quèc T¹o em ®· ®i s©u nghiªn cøu mét sè ph­¬ng ph¸p nÐn ¶nh phæ biÕn nh­ : m· lo¹t dµi RLE, HUFFMAN, LZW, JPEG vµ ph­¬ng ph¸p nÐn ¶nh JPEG2000 dùa trªn biÕn ®æi Wavelet víi nh÷ng ®Æc tÝnh v­ît tréi so víi c¸c chuÈn nÐn tr­íc ®ã ®em l¹i hiÖu qu¶ nÐn cao , cho ¶nh nÐn chÊt l­îng tèt vµ nhiÒu nh÷ng ­u ®iÓm kh¸c mµ c¸c chuÈn nÐn tr­íc ®ã kh«ng thÓ cã. Néi dung ®å ¸n tèt nghiÖp bao gåm c¸c phÇn chÝnh nh­ : ch­¬ng mét giíi thiÖu tæng quan vÒ xö lý ¶nh, môc ®Ých ch­¬ng nµy lµ giíi thiÖu mét sè kh¸i niÖm cÇn biÕt vÒ ¶nh sè vµ xö lý ¶nh sè. Ch­¬ng hai sÏ giíi thiÖu mét sè ph­¬ng ph¸p nÐn ¶nh vµ c¸ch ph©n lo¹i c¸c ph­¬ng ph¸p nÐn ¶nh. Ch­¬ng ba sÏ giíi thiÖu vÒ ch­¬ng tr×nh thö nghiÖm vµ kÕt qu¶ ®¹t ®ù¬c cña ch­¬ng tr×nh. Cuèi cïng sÏ lµ phÇn kÕt luËn ®¸nh gi¸ kÕt qu¶ nghiªn cøu thu ®­îc vµ h­íng ph¸t triÓn cña ®Ò tµi. CH­¬ng I: Giíi thiÖu tæng quan vÒ nÐn ¶nh I.1.Giíi thiÖu vÒ ¶nh sè vµ xö lý ¶nh sè: I.1.1.¶nh sè: ¶nh cã thÓ biÓu diÔn d­íi d¹ng tÝn hiÖu t­¬ng tù hoÆc tÝn hiÖu sè. Trong biÓu diÔn sè cña c¸c ¶nh ®a møc x¸m, mét ¶nh ®­îc biÓu diÔn d­íi d¹ng mét ma trËn hai chiÒu. Mçi phÇn tö cña ma trËn biÓu diÔn cho møc x¸m hay c­êng ®é cña ¶nh t¹i vÞ trÝ ®ã. Mçi phÇn tö trong ma trËn ®­îc gäi lµ mét phÇn tö ¶nh, th«ng th­êng kÝ hiÖu lµ PEL (Picture Element) hoÆc lµ ®iÓm ¶nh (Pixel). - Víi ¶nh ®a cÊp x¸m: NÕu dïng 8 bit (1 byte) ®Ó biÓu diÔn møc x¸m, th× sè c¸c møc x¸m cã thÓ biÓu diÔn ®­îc lµ 28 hay 256. Mçi møc x¸m ®­îc biÓu diÔn d­íi d¹ng lµ mét sè nguyªn n»m trong kho¶ng tõ 0 ®Õn 255, víi møc 0 biÓu diÔn cho møc c­êng ®é ®en nhÊt vµ 255 biÓu diÔn cho møc c­êng ®é s¸ng nhÊt. - Víi ¶nh mµu: C¸ch biÓu diÔn còng t­¬ng tù nh­ víi ¶nh ®en tr¾ng, chØ kh¸c lµ c¸c sè t¹i mçi phÇn tö cña ma trËn biÓu diÔn cho ba mµu riªng rÏ gåm: ®á (red), lôc (green) vµ lam (blue). §Ó biÓu diÔn cho mét ®iÓm ¶nh mµu cÇn 24 bit, 24 bit nµy ®­îc chia thµnh ba kho¶ng 8 bit. Mçi kho¶ng nµy biÓu diÔn cho c­êng ®é s¸ng cña mét trong c¸c mµu chÝnh. Pixel or PEL §é s¸ng trung b×nh trong mçi h×nh ch÷ nhËt = gi¸ trÞ mét ®iÓm ¶nh. H×nh 1.1 BiÓu diÔn cña mét møc x¸m cña ¶nh sè. I.1.2.Xö lý ¶nh sè: Xö lý ¶nh lµ mét khoa häc mÆc dï cßn t­¬ng ®èi míi so víi nhiÒu ngµnh khoa häc kh¸c ,nhÊt lµ trªn quy m« c«ng nghiÖp. Xö lý ¶nh sè cã rÊt nhiÒu øng dông nh­ lµm næi c¸c ¶nh trong y häc, kh«i phôc l¹i ¶nh do t¸c ®éng cña khÝ quyÓn trong thiªn v¨n häc, t¨ng c­êng ®é ph©n gi¶i cña ¶nh truyÒn h×nh mµ kh«ng cÇn thay ®æi cÊu tróc bªn trong cña hÖ thèng chuyÓn t¶i, nÐn ¶nh trong khi truyÒn ®i xa hoÆc l­u tr÷. CAMERA SENSOR Thu nhËn ¶nh Sè ho¸ Ph©n tÝch ¶nh HÖ quyÕt ®Þnh NhËn d¹ng dd¹ng¹ng L­u tr÷ L­u tr÷ C¸c giai ®o¹n chÝnh trong xö lý ¶nh cã thÓ ®­îc m« t¶ trong h×nh sau: I.2.Môc ®Ých vµ sù cÇn thiÕt cña “ nÐn ¶nh ”: NÐn ¶nh lµ mét kü thuËt m· ho¸ c¸c ¶nh sè ho¸ nh»m gi¶m sè l­îng c¸c bit d÷ liÖu cÇn thiÕt ®Ó biÓu diÔn ¶nh. Môc ®Ých lµ gi¶m ®i nh÷ng chi phÝ trong viÖc l­u tr÷ ¶nh vµ chi phÝ thêi gian ®Ó truyÒn ¶nh ®i xa trong truyÒn th«ng nh­ng vÉn ®¶m b¶o ®­îc chÊt l­îng cña ¶nh. NÐn ¶nh thùc hiÖn ®­îc lµ do mét thùc tÕ: th«ng tin trong bøc ¶nh kh«ng ph¶i lµ ngÉu nhiªn mµ cã trËt tù , tæ chøc.V× thÕ nÕu bãc t¸ch ®­îc tÝnh trËt tù, cÊu tróc ®ã th× sÏ biÕt phÇn th«ng tin nµo quan träng nhÊt trong bøc ¶nh ®Ó biÓu diÔn vµ truyÒn ®i víi sè l­îng Ýt bit h¬n so víi ¶nh gèc mµ vÉn ®¶m b¶o tÝnh ®Çy ®ñ cña th«ng tin.ë bªn nhËn qu¸ tr×nh gi¶i m· sÏ tæ chøc, s¾p xÕp l¹i ®­îc bøc ¶nh xÊp xØ gÇn chÝnh x¸c so víi ¶nh gèc nh­ng vÉn tháa m·n chÊt l­îng yªu cÇu. D­íi ®©y lµ vÝ dô vÒ l­u tr÷ ¶nh sè vµ truyÒn ®i xa víi ®­êng truyÒn 9600 baud (9600 bps) ®Ó thÊy râ sù cÇn thiÕt cña viÖc nÐn ¶nh: • ¶nh ®a cÊp x¸m hay ¶nh 256 mµu cã kÝch th­íc 800 x 600, 8 bit/®iÓm ¶nh, cÇn 3.840.000 bit l­u tr÷ vµ mÊt 6.67 phót ®Ó truyÒn. • ¶nh mµu RGB (24 bit/®iÓm ¶nh ) cïng ®é ph©n gi¶i nh­ vËy cÇn h¬n 10 triÖu bit ®Ó l­u tr÷ vµ 20 phót ®Ó truyÒn. • Mét phim ©m b¶n cã kÝch th­íc 24 ´ 36 mm (35 mm) chia b»ng c¸c kho¶ng c¸ch nhau 12 µm, vµo kho¶ng 3000 ´ 2000 ®iÓm, 8 bit / pixel, yªu cÇu 48 triÖu bit cho l­u gi÷ ¶nh vµ 83 phót ®Ó truyÒn. Qua vÝ dô trªn ta thÊy nhiÒu vÊn ®Ò trong viÖc l­u tr÷ vµ truyÒn t¶i ¶nh sè ho¸. NÐn ¶nh cã nhiÒu øng dông trong thùc tÕ nh­ : truyÒn c¸c v¨n b¶n ®å ho¹ qua ®­êng ®iÖn tho¹i (Fax), nÐn ¶nh trong y tÕ vµ truyÒn h×nh c¸p….ChÝnh sù øng dông trong nhiÒu lÜnh vùc cña nÐn ¶nh cïng víi sù tiÕn bé trong lÜnh vùc vi ®iÖn tö dÉn ®Õn sù ra ®êi c¸c chuÈn nÐn ¶nh. NÐn ¶nh ®¹t ®­îc b»ng c¸ch lo¹i bá c¸c phÇn d­ thõa trong ¶nh ®· ®­îc sè ho¸. D­ thõa cã thÓ lµ d­ thõa th«ng tin vÒ kh«ng gian, d­ thõa vÒ cÊp x¸m hay d­ thõa vÒ thêi gian: • D­ thõa th«ng tin vÒ kh«ng gian : trong mét bøc ¶nh lu«n tån t¹i sù t­¬ng quan gi÷a c¸c ®iÓm ¶nh c¹nh nhau. • D­ thõa th«ng tin vÒ cÊp x¸m :lµ d­ thõa dùa vµo sù t­¬ng quan gi÷a c¸c mµu s¾c c¹nh nhau. • D­ thõa th«ng tin vÒ thêi gian : Trong mét chuçi ¶nh video, tån t¹i sù t­¬ng quan gi÷a c¸c ®iÓm ¶nh cña c¸c frame kh¸c nhau . I.3.C¸c kh¸i niÖm c¬ b¶n: • Pixel (picture element) : phÇn tö ¶nh ¶nh trong thùc tÕ lµ mét ¶nh liªn tôc vÒ kh«ng gian vµ vÒ gi¸ trÞ ®é s¸ng. §Ó cã thÓ xö lý ¶nh b»ng m¸y tÝnh cÇn thiÕt ph¶i tiÕn hµnh sè ho¸ ¶nh. Nh­ vËy mét ¶nh lµ mét tËp hîp c¸c pixel. Mçi pixel lµ gåm mét cÆp to¹ ®é x, y vµ mµu. CÆp to¹ ®é x,y t¹o nªn ®é ph©n gi¶i (resolution). Mµn h×nh m¸y tÝnh cã nhiÒu lo¹i víi ®é ph©n gi¶i kh¸c nhau: 320 x 200, 640x350, 800x600, 1024x768,… • Møc x¸m (Graylevel) Møc x¸m lµ kÕt qu¶ sù m· ho¸ t­¬ng øng cña mçi c­êng ®é s¸ng cña mçi ®iÓm ¶nh víi mét gi¸ trÞ sè – kÕt qu¶ cña qu¸ tr×nh l­îng ho¸ . • D÷ liÖu Trong mét bµi to¸n, d÷ liÖu bao gåm mét tËp c¸c phÇn tö c¬ së mµ ta gäi lµ d÷ liÖu nguyªn tö. Nã cã thÓ lµ mét ch÷ sè, mét ký tù, ... nh­ng còng cã thÓ lµ mét con sè, mét tõ, ... ®iÒu ®ã phô thuéc vµo tõng bµi to¸n. • NÐn d÷ liÖu NÐn d÷ liÖu lµ qu¶ tr×nh gi¶m dung l­îng th«ng tin “d­ thõa” trong d÷ liÖu gèc vµ lµm cho l­îng th«ng tin thu ®­îc sau nÐn th­êng nhá h¬n d÷ liÖu gèc rÊt nhiÒu. Do vËy, tiÕt kiÖm ®­îc bé nhí vµ gi¶m thêi gian trao ®æi d÷ liÖu trªn m¹ng th«ng tin mµ l¹i cho phÐp chóng ta kh«i phôc l¹i d÷ liÖu ban ®Çu. • Tû lÖ nÐn Tû lÖ nÐn lµ mét trong c¸c ®Æc tr­ng quan träng cña mäi ph­¬ng ph¸p nÐn. Tû lÖ nÐn ®­îc ®Þnh nghÜa nh­ sau: Tû lÖ nÐn = 1/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 nÐn. Nh­ vËy hiÖu suÊt nÐn = (1- tû lÖ nÐn)*100%. §èi v¬i ¶nh tÜnh, kÝch th­íc chÝnh lµ sè bit biÓu diÔn toµn bé bøc ¶nh. §èi víi ¶nh video, kÝch th­íc chÝnh lµ sè bit ®Ó biÓu diÔn mét khung h×nh video (video frame). Ch­¬ng II: C¸c ph­¬ng ph¸p nÐn ¶nh II.1.C¸ch ph©n lo¹i c¸c ph­¬ng ph¸p nÐn ¶nh: II.1.1.C¸ch ph©n lo¹i dùa vµo nguyªn lý nÐn: NÐn b¶o toµn th«ng tin (losses compression): bao gåm c¸c ph­¬ng ph¸p nÐn mµ sau khi gi¶i nÐn sÏ thu ®ù¬c chÝnh x¸c d÷ liÖu gèc.Tuy nhiªn nÐn b¶o toµn th«ng tin chØ ®¹t hiÖu qu¶ nhá so víi ph­¬ng ph¸p nÐn kh«ng b¶o toµn th«ng tin. NÐn kh«ng b¶o toµn th«ng tin (lossy compression): bao gåm c¸c ph­¬ng ph¸p nÐn sau khi gi¶i nÐn sÏ kh«ng thu ®­îc d÷ liÖu nh­ b¶n gèc. C¸c ph­¬ng ph¸p nµy ®­îc gäi lµ “t©m lý thÞ gi¸c” ®ã lµ 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.Ph­¬ng ph¸p nµy lu«n ®em l¹i hiÖu qu¶ cao do lo¹i bá ®i nh÷ng th«ng tin d­ thõa kh«ng cÇn thiÕt. II.1.2.C¸ch ph©n lo¹i dùa vµo c¸ch thøc thùc hiÖn nÐn: Ph­¬ng ph¸p kh«ng gian (Spatial Data Compression ): c¸c ph­¬ng ph¸p 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 chø kh«ng t¸c ®éng trùc tiÕp. II.1.3.C¸ch ph©n lo¹i dùa vµo lý thuyÕt m· ho¸: C¸c ph­¬ng ph¸p nÐn thÕ hÖ thø nhÊt: gåm c¸c ph­¬ng ph¸p cã møc ®é tÝnh to¸n ®¬n gi¶n nh­ lÊy mÉu , g¸n tõ m·,…. C¸c ph­¬ng ph¸p nÐn thÕ hÖ thø hai: gåm c¸c ph­¬ng ph¸p dùa vµo møc ®é b·o hoµ cña tû lÖ nÐn b»ng c¸ch sö dông c¸c phÐp to¸n tæ hîp ®Çu ra mét c¸ch hîp lý hoÆc sö dông biÓu diÔn ¶nh nh­ : ph­¬ng ph¸p kim tù th¸p Laplace, ph­¬ng ph¸p dùa vµo vïng gia t¨ng, ph­¬ng ph¸p t¸ch hîp. II.1.4.Qu¸ tr×nh nÐn vµ gi¶i nÐn : Gåm 2 c«ng ®o¹n : NÐn : d÷ liÖu gèc qua bé m· ho¸ d÷ liÖu , bé m· ho¸ nµy thùc hiÖn nÐn d÷ liÖu ®Õn mét møc thÝch hîp cho viÖc l­u tr÷ vµ truyÒn dÉn th«ng tin. Qu¸ tr×nh nµy sÏ thùc hiÖn viÖc lo¹i bá hay c¾t bít nh÷ng d­ thõa cña ¶nh ®Ó thu ®­îc th«ng tin cÇn thiÕt nh­ng vÉn ®¶m b¶o ®­îc chÊt l­îng ¶nh. Gi¶i nÐn : d÷ liÖu nÐn ®i qua bé gi¶i m· d÷ liÖu, bé gi¶i m· sÏ thùc hiÖn gi¶i nÐn ®Ó thu ®­îc d÷ liÖu gèc ban ®Çu.ViÖc gi¶i nÐn nµy th­êng ph¶i dùa vµo c¸c th«ng tin ®i kÐm theo d÷ liÖu nÐn ,tuú thuéc vµo kiÓu nÐn hay ph­¬ng ph¸p nÐn mµ d÷ liÖu gi¶i nÐn ®­îc cã hoµn toµn gièng víi d÷ liÖu gèc ban ®Çu hay kh«ng. Tãm l¹i 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¬ ®å d­íi ®©y: Qu¸ tr×nh nÐn Qu¸ tr×nh gi¶i nÐn D÷ liÖu gèc D÷ liÖu nÐn H×nh 2.1 : Qu¸ tr×nh nÐn vµ gi¶i nÐn II.2.Ph­¬ng ph¸p m· ho¸ ®é dµi lo¹t RLE: M· ho¸ theo ®é dµi lo¹t RLE (Run Length Encoding) lµ mét ph­¬ng ph¸p nÐn ¶nh dùa trªn sù c¾t bít c¸c d­ thõa vÒ kh«ng gian (mét vµi h×nh ¶nh cã vïng mµu lín kh«ng ®æi ®Æc biÖt ®èi víi ¶nh nhÞ ph©n). Lo¹t ®­îc ®Þnh nghÜa lµ d·y c¸c phÇn tö ®iÓm ¶nh (pixel) liªn tiÕp cã cïng chung mét gi¸ trÞ. II.2.1.Nguyªn t¾c : Nguyªn t¾c cña ph­¬ng ph¸p nµy lµ ph¸t hiÖn mét lo¹t c¸c ®iÓm ¶nh lÆp l¹i liªn tiÕp, vÝ dô :110000000000000011 .Ta thÊy ®iÓm ¶nh cã gi¸ trÞ 0 xuÊt hiÖn nhiÒu lÇn liªn tiÕp thay v× ph¶i l­u tr÷ toµn bé c¸c ®iÓm ¶nh cã gi¸ trÞ 0 ta chØ cÇn l­u tr÷ chóng b»ng c¸ch sö dông c¸c cÆp (®é dµi lo¹t, gi¸ trÞ). VÝ dô: Cho mét chuçi nguån d : d =5 5 5 5 5 5 5 5 5 5 19 19 19 19 19 0 0 0 0 0 0 0 23 23 23 23 23 23 23 23 Ta sÏ cã chuçi míi : (10 5) (5 19) (7 0) (8 23) Tû sè nÐn = 20/ 8 = 2.5 §èi víi ¶nh ®en tr¾ng chØ sö dông 1 bit ®Ó biÓu diÔn 1 ®iÓm ¶nh th× ph­¬ng ph¸p nµy tá ra rÊt hiÖu qu¶, ta thÊy ®iÒu ®ã qua vÝ dô sau : Cho mét chuçi nguån d: 000000000000000111111111100000000001111111111000000000000000 Ta cã chuçi míi : (15, 10, 10, 10, 15) Tû sè nÐn = 60 bit / (5*4 bit) = 3 ( chØ sö dông 4 bit ®Ó thÓ hiÖn ®é dµi lo¹t vµ kh«ng thÓ hiÖn gi¸ trÞ lo¹t v× ¶nh ®en tr¾ng chØ cã 2 gi¸ trÞ bit lµ 0 hoÆc lµ 1) Chó ý: • §èi víi ¶nh chiÒu dµi cña mét d·y lÆp cã thÓ lín h¬n 255, nÕu ta dïng 1 byte ®Ó l­u tr÷ chiÒu dµi 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 lµ 255, chuçi kia cã chiÒu dµi cßn l¹i. • Ph­¬ng ph¸p nÐn RLE chØ ®¹t hiÖu qu¶ khi chuçi lÆp lín h¬n 1 ng­ìng nhÊt ®Þnh nµo ®ã hay nãi c¸c kh¸c trong ¶nh cÇn nÐn ph¶i cã nhiÒu ®iÓm ¶nh kÒ nhau cã cïng gi¸ trÞ mµu.Do ®ã ph­¬ng ph¸p nµy kh«ng ®em l¹i cho ta kÕt qu¶ mét c¸ch æn ®Þnh v× nã phô thuéc hoµn toµn vµo ¶nh nÐn chØ thÝch hîp cho nh÷ng ¶nh ®en tr¾ng hay ¶nh ®a cÊp x¸m. VÝ dô: Ta cã mét chuçi nguån: d=5 7 9 11 13 18 28 38 48 58 30 35 40 45 Chuçi kÕt qu¶ sau khi m· ho¸ : 1 5 1 7 1 9 1 11 1 3 1 18 1 28 1 38 1 48 1 58 1 30 1 35 1 40 1 45 Tû sè nÐn = 14 / 28 = 0.2 Nh­ vËy chuçi sau khi m· ho¸ ®· lín h¬n nhiÒu chuçi nguån ban ®Çu. Do ®ã cÇn ph­¬ng ph¸p c¶i tiÕn ®Ó xö lý nh÷ng tr­êng hîp nh­ trªn tr¸nh lµm më réng chuçi d÷ liÖu nguån nghÜa lµ chØ m· ho¸ ®é dµi lo¹t d÷ liÖu lÆp l¹i. Ng­êi ta ®· ®­a ra c¸ch ®ã lµ thªm kÝ tù tiÒn tè vµo tr­íc ®é dµi lo¹t, viÖc gi¶i m· ®­îc thùc hiÖn nÕu gÆp kÝ tù tiÒn tè víi ®é dµi lo¹t vµ gi¸ trÞ ®iÓm ¶nh theo sau. VÝ dô: Ta cã chuçi nguån : d = 5 8 4 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10 10 10 Gi¶ sö kÝ tù tiÒn tè lµ “+” ta cã : 5 8 4 +7 8 + 9 10 Tû sè nÐn = 19 / 9 = 2.1 Tuy nhiªn trong mét sè tr­êng hîp c¸c ®iÓm ¶nh cã ®é t­¬ng quan víi nhau vÓ gi¸ trÞ møc x¸m nh­ trong vÝ dô d­íi ®©y ta cã thÓ tiÕn hµnh xö lý nh­ sau. VÝ dô: Ta cã mét chuçi nguån: d = 5 7 9 11 13 18 28 38 48 58 55 60 65 70 75 80 85 90 95 100 Ta cã dùa vµo ®é t­¬ng quan nµy ®Ó cã ®­îc hiÖu qu¶ nÐn cao , b»ng viÖc ¸p dông e(i) = d(i) –d(i-1) sÏ thu ®­îc : 5 2 2 2 2 5 10 10 10 10 -3 5 5 5 5 5 5 5 5 5 ¸p dông ph­¬ng ph¸p nÐn lo¹t dµi ta dÔ dµng thu ®­îc : (5 1)( 2 4)(5 1)(10 5)(-3 1)(5 9) II.2.2.ThuËt to¸n: ThuËt to¸n nh­ sau : • TiÕn hµnh duyÖt trªn tõng hµng cho ®Õn khi kÕt thóc vïng d÷ liÖu ¶nh, trong qu¸ tr×nh duyÖt tiÕn hµnh kiÓm tra ®Ó t×m ra nh÷ng lo¹t cã cïng gi¸ trÞ ®ång thêi chó ý nh÷ng kÝ hiÖu xuèng dßng (hay kÕt thóc dßng) ,kÕt thóc ¶nh Bitmap, … • Khi gÆp lo¹t cã ®é dµi > 3 th× nh¶y ®Õn chÕ ®é nÐn ng­îc l¹i nh¶y ®Õn chÕ ®é kh«ng nÐn tuy nhiªn nÕu lo¹t > 255 th× sÏ t¸ch ra chØ m· < 255 sau ®ã m· tiÕp phÇn cßn l¹i. Ngoµi ra cßn c¸c chÕ ®é kh¸c nh­ : b¾t ®Çu , kÕt thóc 1 dßng. • KÕt thóc khi gÆp kÝ hiÖu kÕt thóc bitmap ( end – o f- bitmap) II.2.3.Mét sè thñ tôc ch­¬ng tr×nh : • Ch­¬ng tr×nh nÐn theo ph­¬ng ph¸p RLE : void CRLE::CompressInRLE8(BYTE*pSrcBits,CByteArray& pRLEBits, int& RLE_size) { int line; int src_index = 0, dst_index = 0, counter, i; for ( line = 0; line < m_dib.dsBmih.biHeight; line++) { state_start: if ( EndOfLine(src_index)) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index++; goto end_of_line; } if(pSrcBits[src_index]==pSrcBits[src_index+1]) goto tate_compress; if ( EndOfLine(src_index+1)) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; goto end_of_line; } if (pSrcBits[src_index+1] == pSrcBits[src_index+2]) { pRLEBits[dst_index++] = 1; pRLEBits[dst_index++] = pSrcBits[src_index++]; goto state_compress; } else goto state_no_compress; state_compress: for ( counter = 1; counter <= 254; counter++) { if ( pSrcBits[src_index+counter] != pSrcBits[src_index] ) break; if ( EndOfLine(src_index+counter) ) { pRLEBits[dst_index++] = counter+1; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index += counter +1; goto end_of_line; } } pRLEBits[dst_index++] = counter; pRLEBits[dst_index++] = pSrcBits[src_index]; src_index += counter; goto state_start; state_no_compress: for (counter = 2; counter <= 254; counter++) { if ( EndOfLine(src_index+counter) ) { pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter + 1; for (i = counter + 1; i > 0; i--) pRLEBits[dst_index++]=pSrcBits[src_index++]; if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++]; goto end_of_line; } if(EndOfLine(src_index+counter+1) || pSrcBits[src_index+counter] != pSrcBits[src_index+counter+1] ) continue; if(EndOfLine(src_index+counter+2) || SrcBits[src_index+counter+1] != pSrcBits[src_index+counter+2] ) continue; else { if ( counter > 2) counter--; pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter+1; for (i = counter+1; i > 0; i--) pRLEBits[dst_index++] = pSrcBits[src_index++]; if ( 0 != ((counter+1) % 2) ) pRLEBits[dst_index++]; goto state_compress; } } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = counter; for (i = counter; i > 0; i--) pRLEBits[dst_index++] = pSrcBits[src_index++]; if ( 0 != ((counter) % 2) ) pRLEBits[dst_index++]; goto state_start; end_of_line: if ( 0 != (src_index % 4 )) { int pad = 4 - (src_index%4); src_index += pad; } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = 0; } pRLEBits[dst_index++] = 0; pRLEBits[dst_index++] = 1; RLE_size = dst_index; } • Ch­¬ng tr×nh gi¶i nÐn ph­¬ng ph¸p RLE : BOOL CRLE::DecRLE8(ifstream &fil, BYTE *pDest) { DWORD x, y, paddedwidth; paddedwidth =BMPWIDTHBYTES(pInfo->biWidth*pInfo-> biBitCount); BYTE FirstByte, SecondByte; WORD data; x = y = 0; while (!fil.eof()) { if (!fil.read((char*)&data, 2)) return FALSE; FirstByte = LOBYTE(data); SecondByte = HIBYTE(data); if (FirstByte == 0) { switch (SecondByte) { case 0: x = 0; y++; break; case 1: return TRUE; case 2: if (!fil.read((char*)&data, 2)) return FALSE; x += LOBYTE(data); y += HIBYTE(data); break; default: char ch; for (BYTE i = 0; i < SecondByte; i++) { if (!fil.get(ch)) return FALSE; pDest[paddedwidth * y + x++] = (BYTE)ch; } if ((SecondByte % 2) == 1) if (!fil.get(ch)) return FALSE; } } else { for (BYTE i = 0; i < FirstByte; i++) pDest[paddedwidth * y + x++] = SecondByte; } } return FALSE; } II.3.Ph­¬ng ph¸p m· ho¸ Huffman: II.3.1. 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ª. Ng­êi ta tÝnh tÇn suÊt xuÊt hiÖn cña c¸c ký tù b»ng c¸ch duyÖt tuÇn tù tõ ®Çu tÖp gèc ®Õn cuèi tÖp. ViÖc xö lý ë ®©y tÝnh theo bit. Trong ph­¬ng ph¸p nµy c¸c ký tù cã tÇn suÊt cao mét tõ m· ng¾n, c¸c ký tù cã tÇn suÊt thÊp mét tõ m· dµi. Nh­ vËy 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 còng cã tr­êng hîp bÞ thiÖt 1 Ýt bit khi tÇn suÊt lµ rÊt thÊp. II.3.2. ThuËt to¸n: • ThuËt to¸n m· ho¸ Huffman gåm 2 b­íc chÝnh: • B­íc mét: TÝnh tÇn suÊt cña c¸c ký tù trong d÷ liÖu gèc b»ng c¸ch 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· vµ tÝnh to¸n tÇn suÊt. TiÕp theo sau lµ s¾p xÕp l¹i b¶ng m· theo thø tù tÇn suÊt gi¶m dÇn. • B­íc hai: DuyÖt b¶ng tÊn suÊt tõ cuèi lªn ®Çu ®Ó thùc hiÖn ghÐp hai phÇn tö cã tÇn suÊt thÊp thµnh mét phÇn tö duy nhÊt cã tÇn suÊt b»ng tæng hai tÇn suÊt thµnh phÇn. CËp nhËt phÇn tö nµy vµo vÞ trÝ phï hîp trong b¶ng vµ lo¹i bá hai phÇn tö ®· xÐt. Thùc hiÖn cho ®Õn khi b¶ng chØ cã mét phÇn tö. §©y lµ qu¸ tr×nh t¹o c©y nhÞ ph©n Huffman ,phÇn tö cã tÇn suÊt thÊp ë bªn ph¶i, phÇn tö kia ë bªn tr¸i. 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¸ thùc hiÖn theo quy ®Þnh : mçi lÇn xuèng bªn ph¶i ta thªm mét bit ‘1’ vµo tõ m·, mçi lÇn xuèng bªn tr¸i ta thªm mét bit ‘0’ vµo tõ m·. Qu¸ tr×nh gi¶i nÐn còng kh¸ ®¬n gi¶n ®­îc tiÕn hµnh theo chiÒu ng­îc l¹i. 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 l­u tr÷ trong cÊu tróc ®Çu cña tÖp nÐn cïng víi d÷ liÖu nÐn). VÝ dô: Mét tÖp bÊt kú cã tÇn suÊt xuÊt hiÖn cña c¸c kÝ tù sè nh­ b¶ng sau. Ký tù TÇn suÊt 0 1 2 3 4 5 6 7 8 9 1532 152 323 412 226 385 602 92 112 87 B¶ng tÇn suÊt s¾p xÕp gi¶m dÇn KÝ tù X¸c suÊt (%) 0 6 3 5 2 4 1 8 7 9 0.3906 0.1535 0.1051 0.0982 0.0824 0.0577 0.0388 0.0286 0.0235 0.0222 0.3905 0.6100 0.3905 0 6 5 2 4 1 8 7 9 3 0.3905 0.1535 0.1051 0.0982 0.0824 0.0577 0.0457 0.0388 0.0286 0.3905 0.1535 0.1051 0.0982 0.0824 0.0674 0.0577 0.0457 0.3906 0.1051 0.1034 0.0982 0.0824 0.0674 0.3905 0.1535 0.1498 0.1051 0.1034 0.0982 0.3905 0.2016 0.1535 0.1498 0.1051 0.3905 0.2549 0.2016 0.1535 0.3905 0.3551 0.2549 0.0286 0.0388 0.1535 0.0235 0.0222 0.0577 0.0824 0.0982 0.1051 0.1535 M« t¶ : Ta tiÕn hµnh hîp nhÊt hay céng 2 tÇn suÊt nhá nhÊt ë cuèi b¶ng ®Ó thu ®­îc gi¸ trÞ tÇn suÊt míi sau ®ã ®­a gi¸ trÞ nµy trë l¹i b¶ng tÇn suÊt ban ®Çu ®· bá ®i 2 tÇn suÊt thµnh phÇn t¹o thµnh nã. Sau khi ®­a gi¸ trÞ míi vµo b¶ng ta ph¶i tiÕn hµnh s¾p xÕp l¹i toµn bé b¶ng , lóc nµy sè l­îng tÇn suÊt chØ cßn lµ n-1 nÕu ban ®Çu sè l­îng tÇn suÊt lµ n. TiÕp tôc thùc hiÖn lÇn l­ît theo thø tù nh­ trªn cho ®Õn khi nµo sè l­îng tÇn suÊt chØ cßn l¹i duy nhÊt 1 gi¸ trÞ. ViÖc t¹o c©y nhÞ ph©n cã thÓ ®­îc thùc hiÖn theo mét thuËt to¸n sau: 1. TÊt c¶ nh÷ng ký tù ban ®Çu ®­îc xem nh­ lµ nh÷ng ký tù giao ®iÓm tù do. 2. Hai nót tù do víi tÇn sè xuÊt hiÖn thÊp nhÊt ®­îc ph©n c«ng tíi mét nót gèc víi gi¸ trÞ b»ng víi tæng cña hai nót con tù do. 3. Hai nót con ®­îc chuyÓn khái danh s¸ch nót tù do. ChuyÓn nót gèc míi t¹o thµnh c«ng vµo danh s¸ch. 4. B­íc hai sang b­íc ba ®­îc lÆp cho ®Õn khi chØ cã 1 nót tù do vÒ phÝa tr¸i. Nót tù do nµy lµ gèc cña c©y. Qu¸ tr×nh x©y dùng c©y nhÞ ph©n Huffman ®­îc thÓ hiÖn chi tiÕt nh­ trong h×nh sau : B0 0 6 3 5 2 4 1 8 7 9 B1 0 6 3 5 2 4 1 8 B2 0 6 3 5 2 4 B3 0 6 3 5 2 B4 0 6 3 5 B5 0 6 3 B6 0 6 B7 0 B8 0 7 9 1 8 7 9 4 1 8 2 7 9 4 5 1 8 2 3 7 9 4 5 6 7 9 4 5 6 1 2 3 8 H×nh 2.3 : Qu¸ tr×nh t¹o c©y nhÞ ph©n Ta cã c©y m· Huffman t­¬ng øng nh­ sau : 0 1 3 7 9 4 5 6 1 8 2 0 B¶ng tõ m· g¸n cho c¸c kÝ tù sè nh­ sau: KÝ tù M· 0 6 3 5 2 4 1 8 7 9 1 001 011 0001 0100 00000 01010 01011 000010 000011 Nh­ vËy víi vÝ dô sau ®©y ta cã thÓ tiÕn hµnh m· ho¸ nh­ sau: Chuçi nguån : 00000000006666693333 à kÝch th­íc = 20*8=160 bit Sö dông m· Huffman theo b¶ng trªn àkÝch th­íc =10*1+5*3+1*6+4*3= 43 bit V× gÝa trÞ trÞ 0 xuÊt hiÖn 10 lÇn nh­ng chØ dïng 1 bit ®Ó thÓ hiÖn, gi¸ trÞ 6 xuÊt hiÖn 5 lÇn dïng 3 bit ®Ó thÓ hiÖn ,gi¸ trÞ 9 dïng 6 bit vµ gi¸ trÞ 3 xuÊt hiÖn 4 lÇn dïng 3 bit ®Ó thÓ hiÖn. Tû sè nÐn = 160 / 43 = 3.7 Trong ph­¬ng ph¸p m· 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· tr­íc.V× vËy khi ®äc theo tõng bit tõ ®Çu ®Õn cuèi tÖp nÐn ta cã thÓ duyÖt c©y m· cho ®Õn mét l¸, tøc lµ ký tù ®· ®­îc gi¶i m·. ViÖc gi¶i m· ch¾c ch¾n ph¶i sö dông c©y nhÞ ph©n gièng nh­ trong m· ho¸. §Ó ®äc, gi¶i m· ®­îc yªu cÇu ph¶i sö dông theo ®óng tiªu chuÈn nhÊt ®Þnh . II.3.3.Mét sè thñ tôc ch­¬ng tr×nh : • Ch­¬ng tr×nh nÐn ph­¬ng ph¸p HUFFMAN : bool CompressHuffman(BYTE*pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen) { CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); int nNodeCount = GetHuffmanTree(nodes); int nNodeSize = sizeof(DWORD)+sizeof(BYTE); nDesLen = nSrcLen+nNodeCount*nNodeSize; pDes = (BYTE*)malloc(nDesLen); BYTE *pDesPtr = pDes; memset(pDesPtr, 0, nDesLen); *(DWORD*)pDesPtr = nSrcLen; pDesPtr += sizeof(DWORD); *pDesPtr = nNodeCount-1; pDesPtr += sizeof(BYTE); for(nCount = 0; nCount < nNodeCount; nCount++) { memcpy(pDesPtr, &nodes[nCount], nNodeSize); pDesPtr += nNodeSize; } qsort(nodes, 256, sizeof(CHuffmanNode), asciiCompare); int nDesIndex = 0; for(nCount = 0; nCount < nSrcLen; nCount++) { *(DWORD*)(pDesPtr+(nDesIndex>>3))|=nodes[pSrc[nCount]].dwCode<< (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; } nDesLen = (pDesPtr-pDes)+(nDesIndex+7)/8; pDes = (BYTE*)realloc(pDes, nDesLen); return true; } • Ch­¬ng tr×nh gi¶i nÐn ph­¬ng ph¸p HUFFMAN : bool DecompressHuffman(BYTE*pSrc,int nSrcLen,BYTE*&pDes, int &nDesLen) { nDesLen = *(DWORD*)pSrc; pDes = (BYTE*)malloc(nDesLen+1); int nNodeCount = *(pSrc+sizeof(DWORD))+1; CHuffmanNode nodes[511], *pNode; int nNodeSize = sizeof(DWORD)+sizeof(BYTE), nSrcIndex = nNodeSize; for(int nCount = 0; nCount < nNodeCount; nCount++) { memcpy(&nodes[nCount], pSrc+nSrcIndex, nNodeSize); nSrcIndex += nNodeSize; } GetHuffmanTree(nodes, false); CHuffmanNode *pRoot = &nodes[0]; while(pRoot->pParent) pRoot = pRoot->pParent; int nDesIndex = 0; DWORD nCode; nSrcIndex <<= 3; while(nDesIndex < nDesLen) { nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; } return true; } II.4.Ph­¬ng ph¸p m· ho¸ LZW: Kh¸i niÖm nÐn tõ ®iÓn ®­îc Jocob Lempe vµ Abraham Ziv ®­a ra lÇn ®Çu tiªn 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 Welch ®· c¶i tiÕn gi¶i thuËt LZ thµnh gi¶i thuËt míi hiÖu qu¶ h¬n vµ ®­îc ®Æt tªn lµ LZW ( Lempe – Ziv - Welch). Ph­¬ng ph¸p nµy 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, nã hay h¬n c¸c ph­¬ng ph¸p tr­íc ®ã ë kü thuËt tæ chøc tõ ®iÓn cho phÐp n©ng cao tû lÖ nÐn. Gi¶i thuËt LZW ®­îc dïng cho tÊt c¶ c¸c lo¹i file nhÞ ph©n, th­êng ®­îc dïng ®Ó nÐn c¸c lo¹i d÷ liÖu nh­ : v¨n b¶n, ¶nh ®en tr¾ng, ¶nh mµu, ¶nh ®a cÊp s¸m… vµ lµ chuÈn nÐn cho c¸c d¹ng ¶nh GIF vµ TIFF. Sè bit / pixel kh«ng ¶nh h­ëng ®Õn hiÖu qu¶ cña LZW. II.4.1.Nguyªn t¾c: 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 tõ vùng). 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 song song víi qu¸ tr×nh ®äc d÷ liÖu. Sù xuÊt hiÖn cña 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 ®· ®ùoc ®äc qua. ThuËt to¸n liªn tôc tra cøu vµ sau mçi lÇn ®äc mét ký tù ë d÷ liÖu ®Çu vµo th× tiÕn hµnh cËp nhËt l¹i tõ ®iÓn. Do giíi h¹n cña bé nhí vµ ®Ó ®¶m b¶o tèc ®é t×m kiÕm nhanh, tõ ®iÓn chØ giíi h¹n 4096 phÇn tö dïng ®Ó l­u tr÷ gi¸ trÞ cña c¸c tõ m·. Nh­ vËy ®é dµi lín nhÊt cña tõ m· lµ 12 bit (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). Khi sè mÉu lÆp lín h¬n 4096 th× ng­êi ta sÏ coi ¶nh gåm nhiÒu m¶nh ¶nh vµ tõ ®iÓn sÏ gåm nhiÒu tõ ®iÓn con. Khi hÕt mét m¶nh ¶nh sÏ göi 1 m· xo¸ ( CC ) ®Ó b¸o hiÖu kÕt thóc m¶nh ¶nh cò vµ b¾t ®Çu m¶nh ¶nh míi ®ång thêi sÏ khëi t¹o l¹i tõ ®iÓn. • Tõ m· thø 257 chøa m· kÕt thóc th«ng tin (EOI - End Of Information). Th«ng th­êng mét file ¶nh GIF cã thÓ chøa nhiÒu m¶nh ¶nh, mçi m¶nh ¶nh nµy 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ô : Cho chuçi ®Çu vµo “HELLOHELLOHELL” Tõ ®iÒn ban ®Çu ®· gåm 256 kÝ tù c¬ b¶n. KÝch th­íc ®Çu vµo : 14 x 8 = 112 bit §Çu vµo §Çu ra Thùc hiÖn H(72) H ®· cã trong tõ ®iÓn à ®äc tiÕp E(69) 72 Thªm vµo tõ ®iÓn m· 258 ®¹i diÖn cho chuçi HE L(76) 69 Thªm vµo tõ ®iÓn m· 259 ®¹i diÖn cho chuçi EL L 76 Thªm vµo tõ ®iÓn m· 260 ®¹i diÖn cho chuçi LL O(79) 76 Thªm vµo tõ ®iÓn m· 261 ®¹i diÖn cho chuçi LO H 79 Thªm vµo tõ ®iÓn m· 262 ®¹i diÖn cho chuçi OH E HE ®· cã trong tõ ®iÓn à ®äc tiÕp L 258 Thªm vµo tõ ®iÓn m· 263 ®¹i diÖn cho chuçi HEL L LL ®· cã trong tõ ®iÓn à ®äc tiÕp O 260 Thªm vµo tõ ®iÓn m· 264 ®¹i diÖn cho chuçi LLO H OH ®· cã trong tõ ®iÓn à ®äc tiÕp E 262 Thªm vµo tõ ®iÓn m· 265 ®¹i diÖn cho chuçi OHE L EL ®· cã trong tõ ®iÓn à ®äc tiÕp L 259 Thªm vµo tõ ®iÓn m· 266 ®¹i diÖn cho chuçi ELL 76 Input = FALSE EOI Chuçi ®Çu ra lµ : 72 69 76 76 79 258 260 262 259 76 KÝch th­íc ®Çu ra : 6 x 8 + 4 x 9 = 84 bit Tû sè nÐn : 112 / 84 = 1.3 Qu¸ tr×nh gi¶i nÐn thùc hiÖn nh­ sau: Code OutBuff() AddToDictionary() CodeWord String 72 H 69 E 258 HE 76 L 259 EL 76 L 260 LL 79 O 261 LO 258 HE 262 OHE 260 LL 263 HEL 262 OH 264 LLO 259 EL 265 OHE 76 L 266 ELL EOI Chuçi thu ®­îc sau gi¶i nÐn :”HELLOHELLOHELL” II.4.2. ThuËt to¸n: • ThuËt to¸n nÐn b»ng LZW: InitDictionary() Output(Clear_Code) OldStr = NULL WHILE ( Input ) { NewChar = GetNextChar() NewStr = OldStr + NewChar IF ( InDictionary(NewStr) ) OldsSr = NewStr ELSE { Output(Code(OldStr)) AddToDictionary(NewStr) OldStr = NewChar } } Output(Code(OldStr)) Output(EOI) • 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: • Hµm InitDictionary() : Khëi t¹o tõ ®iÓn. §Æt gi¸ trÞ cho 256 phÇn tö ®Çu tiªn. G¸n m· xo¸ CC cho phÇn tö thø 256 vµ m· kÕt thóc th«ng tin EOI cho phÇn tö thø 257. Xo¸ gi¸ trÞ tÊt c¶ c¸c phÇn tö cßn l¹i. • Hµm InDictionary (NewStr) : KiÓm tra chuçi NewStr ®· cã trong tõ ®iÓn ch­a . • Hµm OutPut() : Göi chuçi bit ra file.Tuú thuéc vµo vÞ trÝ cña tõ m· trong tõ ®iÓn mµ chuçi bit cã ®é dµi lµ 9,10,11 hoÆc 12. • 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ê Input x¸c ®Þnh xem cßn d÷ liÖu ®Çu vµo n÷a hay kh«ng. • Hµm AddToDictionary() : Hµm lµm chøc n¨ng cËp nhËt mÉu míi 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¸ CC 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 1 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 rç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 trong tõ ®iÓn. NÕu tån t¹i th× 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. • Gi¶i nÐn d÷ liÖu 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. ThuËt to¸n ®­îc m« t¶ nh­ sau: WHILE (GetNextCode() != EOI) { IF (First_Code) /*M· ®Çu tiªn cña mçi m¶nh ¶nh*/ { OutBuff(DeCode(code)) OldStr = DeCode(code) } ELSE { IF (code == CC) /*M· xo¸*/ { InitDictionary() First_Code = TRUE } NewStr = DeCode(code) OutBuff(NewStr) OldStr = OldStr + FirstChar(NewStr) AddToDictionary(OldStr) OldStr = NewStr } } • Gi¸ trÞ cê First_Code = TRUE chØ m· võa ®äc lµ m· ®Çu tiªn cña mçi m¶nh ¶nh. Chøc n¨ng cña c¸c hµm: • 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. • 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. • Hµm OutBuff() : Hµm nµy göi chuçi ®· gi¶i m· ra vïng nhí ®Öm. • Hµm InitDictionary(): Khëi t¹o tõ ®iÓn. §Æt gi¸ trÞ cho 256 phÇn tö ®Çu tiªn. G¸n m· xo¸ CC cho phÇn tö thø 256 vµ m· kÕt thóc th«ng tin EOI cho phÇn tö thø 257. Xo¸ gi¸ trÞ tÊt c¶ c¸c phÇn tö cßn l¹i. • Hµm DeCode() : Hµm nµy tra cøu tõ ®iÓn vµ tr¶ vÒ chuçi ký tù t­¬ng øng víi m·. • Hµ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 AddToDictionary() : Hµm lµm chøc n¨ng cËp nhËt mÉu míi 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¸ CC vµ gäi ®Õn hµm InitDictionary() ®Ó khëi t¹o l¹i tõ ®iÓn.. II.4.3.Mét sè thñ tôc ch­¬ng tr×nh : • Ch­¬ng tr×nh nÐn ph­¬ng ph¸p LZW : BOOL CLZW::Compress(CFile &source, CFile &destination) { long prefix = 0; long result = 0; BYTE readByte = 0; unsigned long filetotal = 0; CString logString; DWORD resAdd = 256; Init(); filetotal = source.GetLength(); if (m_tudien == NULL) { CreateDictionary(); } source.Read(&prefix, 1); while (source.GetPosition() < filetotal) { source.Read(&readByte, 1); result = m_tudien->GetEntry(prefix, readByte); if (result == -1) { resAdd = m_tudien->AddEntry(prefix, readByte); CalculateBitSize(resAdd); logString.Format("Adding combination of %d and %d to dictionary to entry %d.",prefix, readByte, resAdd); Log(logString); CompressData(destination, prefix); prefix = readByte; result = -1; } else { prefix = result; readByte = 0; } } CompressData(destination, prefix); CloseCompressedFile(destination); ClearDictionary(); return TRUE; } • Ch­¬ng tr×nh gi¶i nÐn ph­¬ng ph¸p LZW : BOOL CLZW::Decompress(CFile &source, CFile &destination) { DWORD prefix = 0, data = 0; CString logString; CByteArray decodeString; BYTE writeData = 0, character = 0; int counter = 0; Init(); if (m_tudien == NULL) { CreateDictionary(); } prefix = DecompressData(source); character = (BYTE)prefix; destination.Write(&prefix, 1); while ((data = DecompressData(source)) != m_MaxCode[m_MaxBits]) { if (!m_tudien->IsCodeExist(data)) { decodeString.Add((BYTE)character); m_tudien->GetBytesFromCode(&decodeString, prefix); } else { m_tudien->GetBytesFromCode(&decodeString, data); character = decodeString.GetAt(decodeString.GetSize() - 1); } counter = decodeString.GetSize(); while (counter > 0) { writeData = (BYTE)decodeString.GetAt(--counter); destination.Write(&writeData, 1); logString.Format("Adding character code %d with know visualisation of: %s", writeData, convertASCIIToText(writeData)); Log(logString); } decodeString.RemoveAll(); m_tudien->AddEntry(prefix, (BYTE)character); CalculateBitSize(m_tudien->GetMaxCode()+1); prefix = data; } return TRUE; } II.5.Ph­¬ng ph¸p m· ho¸ JPEG: II.5.1.Nguyªn t¾c: JPEG lµ viÕt t¾t cña Joint Photographic Expert Group ( nhãm c¸c chuyªn gia ®å ho¹ ph¸t triÓn chuÈn nµy ). ChuÈn nµy ®­îc ph¸t triÓn tõ gi÷a thËp niªn 80 bëi sù hîp t¸c cña tæ chøc ISO vµ ITU vµ ®Õn 1992 ®­îc c«ng nhËn lµ chuÈn ¶nh quèc tÕ ,phôc vô c¸c øng dông vÒ ¶nh cho c¸c lÜnh vùc nh­ m¹ng, 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. JPEG kh«ng cho kÕt qu¶ æn ®Þnh l¾m víi ¶nh ®en tr¾ng, nã cung cÊp c¶ 2 chÕ ®é nÐn : nÐn mÊt m¸t th«ng tin vµ nÐn kh«ng tæn thÊt. Do ®é phøc t¹p vµ hiÖu suÊt nÐn cña JPEG kh«ng mÊt m¸t th«ng tin mµ nã kh«ng ®­îc sö dông phæ biÕn .D­íi ®©y chØ 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 th«ng tin dïng biÕn ®æi Cosin tuÇn tù ( Sequential DTC- Based) cña chuÈn JPEG. II.5.2.ThuËt to¸n: M· ho¸ JPEG bao gåm nhiÒu c«ng ®o¹n, s¬ ®å thuËt to¸n nÐn vµ gi¶i nÐn ®­îc m« t¶ nh­ d­íi ®©y Ph©n khèi ¶nh gèc 8x8 8x8 8x8 DCT L­îng tö ho¸ M· ho¸ ¶nh nÐn B¶ng l­îng tö B¶ng m· Khèi 8x8 8 x 8 H×nh 2.5.1 : Qu¸ tr×nh nÐn ¶nh theo chuÈn JPEG Qu¸ tr×nh gi¶i nÐn sÏ ®­îc thùc hiÖn ng­îc l¹i, ng­êi ta dùa vµo c¸c th«ng tin liªn quan ghi trong phÇn Header cña file nÐn ®Ó gi¶i m· tõng phÇn ¶nh nÐn øng víi ph­¬ng ph¸p nÐn. KÕt qu¶ thu ®­îc lµ hÖ sè ®· l­îng tö. C¨n cø vµo b¶ng l­îng tö sÏ kh«i phôc l¹i gi¸ trÞ tr­íc khi l­îng tö ho¸ cña c¸c hÖ sè nµy. Cuèi cïng lµ biÕn ®æi Cosin ng­îc ®Ó thu l¹i ®­îc ¶nh nh­ ban ®Çu . ¶nh nÐn ¶nh gi¶i nÐn T­¬ng tù ho¸ Gi¶i m· DCT ng­îc B¶ng l­îng tö B¶ng m· H×nh 2.5.2 : Qu¸ tr×nh gi¶i nÐn ¶nh JPEG Chia ¶nh thµnh khèi ChuÈn nÐn JPEG ph©n ¶nh ra c¸c khèi 8x8. BiÕn ®æi nhanh Cosin 2 chiÒu cho c¸c khèi 8x8 sÏ ®¹t hiÖu qu¶ h¬n, viÖc 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è Cij . Khi n = 8 chóng ta chØ cÇn tÝnh hÖ sè Cij cho 3 tÇng (8 = 23), sè c¸c hÖ sè lµ: 4 + 2 + 1 = 7 NÕu víi mét ¶nh 512x512, phÕp biÕn ®æi nhanh Cosin mét chiÒu theo hµng ngang hoÆc hµng däc ta ph¶i cÇn qua 9 tÇng (512 = 29). Sè c¸c hÖ sè Cij lµ: 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 +1 =509. Nh­ vËy thêi gian tÝnh c¸c hÖ sè Cij cho ¶nh 512x512 lín gÊp 72 lÇn so víi thêi gian tÝnh to¸n c¸c hÖ sè nµy cho tõng khèi 8x8 , nÕu kÝch th­íc ¶nh lín h¬n th× chi phÝ thêi gian sÏ cßn t¨ng gÊp nhiÒu lÇn ®ång thêi cßn gióp viÖc tÝnh to¸n trong khi biÕn ®æi Cosin chÝnh x¸c h¬n. ¶nh sÏ 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]. Trong ®ã : m : thø tù cña khèi theo chiÒu réng. n : 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 t¹o ®é 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: x[u,v] = Image[mk + u, nl + v] B. BiÕn ®æi §©y lµ c«ng ®o¹n quan träng cña 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 nµy 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µ: Trong ®ã: Khi k1 = 0 Khi (0<k1<8) Khi k2 = 0 Khi (0<k2<8) ThuËt to¸n biÕn ®æi nhanh Cosin hai chiÒu cho mçi khèi sÏ bao gåm 16 phÐp biÕn ®æi nhanh Cosin mét chiÒu. TiÕn hµnh biÕn ®æi nhanh Cosin mét chiÒu cho c¸c d·y ®iÓm ¶nh trªn 8 hµng. TiÕp ®ã tiÕn hµnh biÕn ®æi nhanh Cosin mét chiÒu trªn 8 cét cña ma trËn võa thu ®­îc sau 8 phÐp biÕn ®æi trªn.KÕt qu¶ sÏ lµ ma trËn hÖ sè biÕn ®æi cña khèi t­¬ng øng. -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X’(0) X’(1) X’(2) X’(3) X’(4) X’(5) X’(6) X’(7) ®¶o bÝt Gi¶i thuËt biÕn ®æi nhanh ®­îc m« t¶ nh­ h×nh sau: H×nh 2.5.3: M« t¶ gi¶i thuËt biÕn ®æi nhanh 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: Khi k1 = 0 Khi (0<k1<8) Khi k2 = 0 Khi (0<k2<8) Trong ®ã: C«ng thøc tÝnh x’(k1,n2) lµ phÐp biÕn ®æi Cosin ng­îc rêi r¹c mét chiÒu cña X(k1,k2). Nh­ vËy muèn kh«i phôc l¹i ¶nh ban ®Çu tõ 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. S¬ ®å biÕn ®æi Cosin ng­îc nhanh ®­îc biÓu diÔn nh­ sau: 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 -1 -1 -1 -1 -1 -1 -1 -1 0.5 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X’(0) X’(1) X’(2) X’(3) X’(4) X’(5) X’(6) X’(7) ®¶o bÝt 0.5 0.5 0.5 H×nh 2.5.4 : S¬ ®å biÕn ®æi Cosin ng­îc 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. Nh­ ta ®· biÕt ¶nh ®­îc chia lµm nhiÒu khèi, øng mçi khèi lµ c¸c hÖ sè x¸c ®Þnh. Tr­íc khi thùc hiÖn b­íc l­îng tö ho¸ ta cã thÓ lo¹i bá vµi hÖ sè. Ngoµi hÖ sè (0,0) (®­îc coi lµ thµnh phÇn DC) biÓu diÔn møc s¸ng trung b×nh cña mét khèi ta cã thÓ lo¹i mét sè hÖ sè kh¸c trong khèi mang th«ng tin chi tiÕt vÒ ¶nh. Ta cã thÓ b¾t ®Çu lo¹i bá tõ hÖ sè cã ®é lÖch chuÈn thÊp nhÊt. ViÖc nªn gi÷ l¹i bao nhiªu hÖ sè cßn tuú thuéc vµo viÖc ta muèn tû lÖ nÐn cao hay thÊp vµ nh÷ng yªu cÇu vÒ chÊt l­îng cña ¶nh nÐn . §Ó 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. Ta sÏ c¨n chØnh l¹i hÖ sè yj b»ng phÐp g¸n: Víi: mj lµ trung b×nh céng cña hÖ sè thø j sj 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 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: TÝnh ri-1 theo c«ng thøc: TÝnh ri theo c«ng thøc: ri = 2di – ri-1 TÝnh di 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. 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 m vµ ®é lÖch c¬ b¶n s 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Ö hÖ sè gi÷ l¹i trong mçi 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 khu vùc T Tn = 1 nÕu hÖ sè (i,j) ®­îc gi÷ l¹i Tn = 0 ng­îc 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 ss 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: di Ü di x ss ri Ü ri x ss dN = - d0 Thµnh phÇn mét chiÒu sÏ kh«ng l­îng tö ho¸ (phÇn tö (0,0) cña khèi 8x8 ®­îc coi lµ thµnh phÇn mét chiÒu, 63 phÇn tö cßn l¹i ®­îc coi lµ c¸c thµnh phÇn xoay chiÒu). §Õ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è xoay chiÒu vµ thµnh phÇn c¸c hÖ sè mét 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 = Ci+1(0,0) - Ci(0,0) di cã gi¸ trÞ nhá h¬n hiÒu so víi Ci nªn trong biÓu diÔn dÊu phÈy ®éng cã nhÒu chuçi bÝt 0 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 thêi. 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 chóng l¹i theo thø tù Zig-Zag. ViÖc s¾p xÕp nµy gióp t¹o ra nhiÒu lo¹t hÖ sè gièng nhau do 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.D­¬i ®©y lµ mét minh ho¹ vÒ khèi Zig-Zag : 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 14 16 25 31 39 46 50 57 15 26 30 40 45 51 56 58 27 29 41 44 52 55 59 62 28 42 43 53 54 60 61 63 H×nh 2.5.5 : Minh ho¹ khèi Zig-Zag Mçi khèi Zig-Zag nµy ®­îc m· ho¸ theo ph­¬ng ph¸p RLE. Cuèi mçi khèi ®Çu ra cña RLE, ta ®Æt dÊu kÕt thóc khèi EOB (End Of Block). Sau ®ã c¸c khèi ®­îc dån l¹i vµ l¹i m· ho¸ mét lÇn b»ng ph­¬ng ph¸p m· Huffman. Nhê cã dÊu kÕt thóc khèi nªn cã thÓ ph©n biÖt hai khèi c¹nh nhau khi gi¶i m· Huffman. Hai b¶ng m· Huffman cho hai thµnh phÇn hÖ sè tÊt nhiªn sÏ kh¸c nhau. §Ó cã thÓ gi¶i nÐn ®­îc, chóng ta ph¶i ghi l¹i c¸c th«ng tin nh­: kÝch th­íc ¶nh, kÝch th­íc khèi, ma trËn T, ®é lÖch tiªu chuÈn, c¸c møc t¹o l¹i, hai b¶ng m· Huffman, kÝch th­íc khèi nÐn mét chiÒu, kÝch th­íc khèi nÐn xoay chiÒu … vµ ghi nèi tiÕp vµo hai tÖp nÐn cña hai thµnh phÇn hÖ sè. Cµi ®Æt gi¶i thuËt cho nÐn JPEG thùc sù phøc t¹p. chóng ta ph¶i l¾m ®­îc c¸c kiÕn thøc vÒ nÐn RLE, Huffman, biÕn ®æi Cosin, x©y dùng bé l­îng tö ho¸ Lloyd – Max … Tuy nÐn vµ gi¶i nÐn JPEG h¬i chËm nh­ng bï l¹i cho kÝch th­íc tÖp nÐn nhá. II.5.3.Mét sè thñ tôc ch­¬ng tr×nh : • Ch­¬ng tr×nh nÐn ph­¬ng ph¸p JPEG: bool CJPEG::write_JPEG_file(const char * filename, int quality) // JPEG compression { struct jpeg_compress_struct cinfo; struct jpeg_error_mgr jerr; FILE * outfile; unsigned char ** buffer; int row_stride; outfile = fopen(filename, "wb"); if (outfile == NULL) return false; cinfo.err = jpeg_std_error(&jerr); jpeg_create_compress(&cinfo); jpeg_stdio_dest(&cinfo, outfile); cinfo.image_width = m_width; cinfo.image_height = m_height; cinfo.input_components = m_mode; switch (m_mode) { case MODE_RGB: cinfo.in_color_space = JCS_RGB; break; case MODE_GRAYSCALE: cinfo.in_color_space = JCS_GRAYSCALE; break; } jpeg_set_defaults(&cinfo); jpeg_set_quality(&cinfo, quality, TRUE); jpeg_start_compress(&cinfo, TRUE); row_stride = m_width * cinfo.input_components; buffer = new unsigned char * [cinfo.image_height]; buffer[0] = new unsigned char[cinfo.image_height * row_stride]; for (int k = 0; k < (int)(cinfo.image_height); k++) { buffer[k] = buffer[0] + row_stride*k; } int i, j; switch (m_mode) { case MODE_RGB: for (j = 0; j < m_height; j++) { for (i = 0; i < m_width*3; i += 3) { buffer[j][i] = image[j][i/3].red; buffer[j][i+1] = image[j][i/3].green; buffer[j][i+2] = image[j][i/3].blue; } } break; case MODE_GRAYSCALE: for (j = 0; j < m_height; j++) { for (i = 0; i < m_width; i++) { buffer[j][i] = gImage[j][i]; } } break; } while (cinfo.next_scanline < cinfo.image_height) { (void) jpeg_write_scanlines(&cinfo, &buffer[cinfo.next_scanline], 1); } jpeg_finish_compress(&cinfo); fclose(outfile); delete [] buffer[0]; delete [] buffer; jpeg_destroy_compress(&cinfo); return true; } • Ch­¬ng tr×nh gi¶i nÐn ph­¬ng ph¸p JPEG: int CJPEG::write_BMP_file(const char * outfile) // Writes a bitmap (.bmp) file (JPEG decompression) { FILE * fp; size_t result; int rowEndBytes = (4-(m_width*3)%4)%4; BITMAPFILEHEADER bmFileHdr; bmFileHdr.bfType = 0x4d42; bmFileHdr.bfSize = 58 + (m_width*3 + rowEndBytes) * m_height; bmFileHdr.bfReserved1 = 0; bmFileHdr.bfReserved2 = 0; bmFileHdr.bfOffBits = 58; BITMAPINFOHEADER bmInfo; bmInfo.biSize = 40; bmInfo.biWidth = m_width; bmInfo.biHeight = m_height; bmInfo.biPlanes = 1; bmInfo.biBitCount = 24; bmInfo.biCompression = BI_RGB; bmInfo.biSizeImage = (m_width*3 + rowEndBytes) * m_height; bmInfo.biXPelsPerMeter = 0; bmInfo.biYPelsPerMeter = 0; bmInfo.biClrUsed = 0; bmInfo.biClrImportant = 0; fp = fopen(outfile, "wb"); if (fp == NULL) return WRITE_BMP_FILENOTFOUND_ERR; result = fwrite((char *)&bmFileHdr, sizeof(BITMAPFILEHEADER), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((char *)&bmInfo, sizeof(BITMAPINFO), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } RGBpixel pixel; BYTE pJunk = 0; for (int j = m_height - 1; j >= 0; j--) { for (int i = 0; i < m_width; i++) { this->getPixel(j, i, pixel); result = fwrite((BYTE *)&pixel.blue, sizeof(BYTE), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((BYTE *)&pixel.green, sizeof(BYTE), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } result = fwrite((BYTE *)&pixel.red, sizeof(BYTE), 1, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } } if (rowEndBytes != 0) result = fwrite((BYTE *)&pJunk, sizeof(BYTE), rowEndBytes, fp); if (result == 0) { fclose(fp); return WRITE_BMP_WRITE_ERR; } } fclose(fp); return WRITE_BMP_SUCCESS; } II.6.Ph­¬ng ph¸p m· ho¸ JPEG2000: II.6.1. Lịch sử ra đời và phát triển chuẩn JPEG2000: Như chúng ta đã biết, sự ra đời của JPEG mang lại nhiều lợi ích to lớn về nhiều mặt. JPEG có thể giảm nhỏ kích thước ảnh, giảm thời gian truyền và làm giảm chi phí xử lý ảnh trong khi chất lượng ảnh là khá tốt. Tuy nhiên cho đến nay người ta mới chỉ ứng dụng dạng thức nén có tổn thất thông tin của JPEG vì mã hoá không tổn thất của JPEG là khá phức tạp. Để việc nén ảnh có hiệu quả hơn, Ủy ban JPEG đã đưa ra một chuẩn nén ảnh mới là JPEG2000. JPEG2000 sử dụng biến đổi Wavelet và các phương pháp mã hoá đặc biệt để có được ảnh nén ưu việt hơn hẳn JPEG. JPEG2000 hiện vẫn đang tiếp tục được phát triển, nhưng phần I đã được tổ chức ISO chấp nhận là chuẩn nén ảnh quốc tế áp dụng cho ảnh tĩnh. Chuẩn nén ảnh JPEG2000 mà xương sống là biến đổi Wavelet với tính năng vượt trội so với JPEG chắc chắn sẽ được sử dụng trong các server nội dung để chuyển đổi định dạng ảnh trong mạng di động. II.6.2.Các tính năng của JPEG2000: JPEG2000 có nhiều chức năng đặc biệt hơn mọi chuẩn nén ảnh tĩnh khác như JPEG hay GIF. Dưới đây là các chức năng ưu việt của JPEG2000 so với các chuẩn nén ảnh tĩnh khác - Cho chất lượng ảnh tốt nhất khi áp dụng nén ảnh tĩnh có tổn thất. - Sử dụng được với truyền dẫn và hiển thị luỹ tiến về chất lượng, độ phân giải, các thành phần màu và có tính định vị không gian. - Sử dụng cùng một cơ chế nén ảnh cho cả hai dạng thức nén. - Truy nhập và giải nén tại mọi thời điểm trong khi nhận dữ liệu. - Giải nén từng vùng trong ảnh mà không cần giải nén toàn bộ ảnh. - Có khả năng mã hoá ảnh với tỷ lệ nén theo từng vùng khác nhau. - Nén một lần nhưng có thể giải nén với nhiều cấp chất lượng tuỳ theo yêu cầu của người sử dụng. Hiện tại, ISO và uỷ ban JPEG đã đưa ra khuyến nghị thay thế JPEG bằng JPEG2000. II.6.3.Các bước thực hiện nén ảnh theo chuẩn JPEG2000: Xö lý tr­íc biÕn ®æi BiÕn ®æi thuËn liªn thµnh phÇn BiÕn ®æi thuËn riªng thµnh phÇn L­îng tö ho¸ M· ho¸ Gi¶i m· ho¸ Gi¶i l­îng tö ho¸ BiÕn ®æi ng­îc riªng thµnh phÇn BiÕn ®æi ng­îc liªn thµnh phÇn Xö lý sau biÕn ®æi ¶nh gèc ¶nh kh«i phôc ¶nh sau m· ho¸ ¶nh m· ho¸ H×nh 2.6.1:C¸c b­íc nÐn vµ gi¶i nÐn JPEG2000 II.6.3.1.Xử lý trước biến đổi: Do sử dụng biến đổi Wavelet, JPEG2000 cần có dữ liệu ảnh đầu vào ở dạng đối xứng qua 0. Xử lý trước biến đổi chính là giai đoạn đảm bảo dữ liệu đưa vào nén ảnh có dạng trên. Ở phía giải mã, giai đoạn xử lý sau biến đổi sẽ trả lại giá trị gốc ban đầu cho dữ liệu ảnh. II.6.3.2. Biến đổi liên thành phần : Giai đoạn này sẽ loại bỏ tính tương quan giữa các thành phần của ảnh. JPEG2000 sử dụng hai loại biến đổi liên thành phần là biến đổi màu thuận nghịch (Reversible Color Transform - RCT) và biến đổi màu không thuận nghịch (Irreversible Color Transform - ICT) trong đó biến đổi thuận nghịch làm việc với các giá trị nguyên, còn biến đổi không thuận nghịch làm việc với các giá trị thực. ICT và RCT chuyển dữ liệu ảnh từ không gian màu RGB sang YCrCb. RCT được áp dụng trong cả hai dạng thức nén có tổn thất và không tổn thất, còn ICT chỉ áp dụng cho nén có tổn thất. Việc áp dụng các biến đổi này trước khi nén ảnh không nằm ngoài mục đích làm tăng hiệu quả nén. Các thành phần Cr, Cb có ảnh hưởng rất ít tới sự cảm nhận hình ảnh của mắt trong khi thành phần độ chói Y có ảnh hưởng rất lớn tới ảnh. Chúng ta có thể thấy rõ hơn điều này trên hình vẽ sau: H×nh 2.6.2 II.6.3.3. Biến đổi riêng thành phần (biến đổi Wavelet) : Biến đổi riêng thành phần được áp dụng trong JPEG2000 chính là biến đổi Wavelet. Để đảm bảo tính toàn vẹn thông tin cũng phải áp dụng các phép biến đổi thuận nghịch hoặc không thuận nghịch. Do phép biến đổi Wavelet không phải là một phép biến đổi trực giao như biến đổi DCT mà là một phép biến đổi băng con nên các thành phần sẽ được phân chia thành các băng tần số khác nhau và mỗi băng sẽ được mã hóa riêng rẽ. JPEG2000 áp dụng biến đổi Wavelet nguyên thuận nghịch 5/3 (IWT) và biến đổi thực không thuận nghịch Daubechies 9/7. Việc tính toán biến đổi trong JPEG2000 này sẽ được thực hiện theo phương pháp Lifting. Sơ đồ của phương pháp Lifting 1D áp dụng trong JPEG2000 trên hình 2.6.3.Việc tính toán biến đổi Wavelet 2D suy ra từ biến đổi Wavelet 1D theo các phương pháp phân giải ảnh tuỳ chọn. Trong JPEG2000 có 3 phương pháp phân giải ảnh nhưng phương pháp được sử dụng nhiều nhất chính là phương pháp kim tự tháp. H×nh 2.6.3 Do biến đổi Wavelet 5/3 là biến đổi thuận nghịch nên có thể áp dụng cho nén ảnh theo cả hai phương pháp, có tổn thất và không tổn thất trong khi biến đổi 9/7 chỉ áp dụng cho nén ảnh theo phương pháp có tổn thất thông tin. II.6.3.4. Lượng tử hoá - Giải lượng tử hoá : Các hệ số của phép biến đổi sẽ được tiến hành lượng tử hoá. Quá trình lượng tử hoá cho phép đạt tỷ lệ nén cao hơn bằng cách thể hiện các giá trị biến đổi với độ chính xác tương ứng cần thiết với mức chi tiết của ảnh cần nén. Các hệ số biến đổi sẽ được lượng tử hoá theo phép lượng tử hoá vô hướng. Các hàm lượng tử hoá khác nhau sẽ được áp dụng cho các băng con khác nhau và được thực theo biểu thức: V(x,y) = với Δ là bước lượng tử, U(x,y) là giá trị băng con đầu vào; V(x,y) là giá trị sau lượng tử hoá. Trong dạng biến đổi nguyên, đặt bước lượng tử bằng 1.Với dạng biến đổi thực thì bước lượng tử sẽ được chọn tương ứng cho từng băng con riêng rẽ. Bước lượng tử của mỗi băng do đó phải có ở trong dòng bít truyền đi để phía thu có thể giải lượng tử cho ảnh. Công thức giải lượng tử hoá là: U(x,y) = r là một tham số xác định dấu và làm tròn, các giá trị ( U x,y);V(x,y) tương ứng là các giá trị khôi phục và giá trị lượng tử hoá nhận được. JPEG2000 không cho trước r tuy nhiên thường chọn r =1/ 2 . II.6.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá: JPEG2000 theo khuyến nghị của uỷ ban JPEG quốc tế có thể sử dụng nhiều phương pháp mã hoá khác nhau cũng như nhiều cách biến đổi Wavelet khác nhau để có thể thu được chất lượng ảnh tương ứng với ứng dụng cần xử lý. Điều này giúp cho JPEG2000 mềm dẻo hơn nhiều so với JPEG. Việc áp dụng các phương pháp mã hoá khác nhau cũng được mở rộng sang lĩnh vực nén ảnh động bằng biến đổi Wavelet. Trong thực tế các phương pháp mã hoá ảnh được áp dụng khi nén ảnh bằng biến đổi Wavelet cũng như JPEG2000 thì có hai phương pháp được coi là cơ sở và được áp dụng nhiều nhất: phương pháp SPIHT và phương pháp EZW. Hiện nay JPEG2000 vẫn được áp dụng mã hoá bằng hai phương pháp này và một phương pháp phát triển từ hai phương pháp này là phương pháp mã hoá mặt phẳng bít. Vì thế ở đây chúng ta sẽ xem xét hai phương pháp này. Việc kết hợp dòng dữ liệu sau mã hoá của JPEG2000 thực chất là để thực hiện các tính năng đặc biệt của JPEG2000 như tính năng ROI v.v... II.6.3.6. Phương pháp mã hoá SPIHT: Có thể thấy rằng dù áp dụng biến đổi Wavelet nào hay cùng với nó là một phép phân giải ảnh nào thì trong các băng con có số thứ tự thấp cũng là những thành phần tần số cao (mang thông tin chi tiết của ảnh) trong khi những băng con có số thứ tự cao hơn thì sẽ chứa những thành phần tần số thấp (mang thông tin chính về ảnh). Điều đó nghĩa là các hệ số chi tiết sẽ giảm dần từ băng con mức thấp (HH1 chẳng hạn) (ứng với thành phần tần số cao) xuống băng con mức cao (ứng với thành phần tần số thấp) và có tính tương tự về không gian giữa các băng con, ví dụ như một đường biên của hình vẽ trong ảnh sẽ tồn tại ở cùng một vị trí trên các băng con đó (tương ứng với mức độ phân giải của băng con ấy). Điều này đã dẫn tới sự ra đời của phương pháp SPIHT (Set partitioning in hierarchical trees - phương pháp mã hoá phân cấp theo phân vùng). Phương pháp SPIHT được thiết kế tối ưu cho truyền dẫn luỹ tiến. Điều này có nghĩa là tại mọi thời điểm trong quá trình giải nén ảnh theo phương pháp mã hoá này thì chất lượng ảnh hiển thị tại thời điểm ấy là tốt nhất có thể đạt được với một số lượng bít đưa vào giải mã tính cho tới thời điểm ấy. Ngoài ra, phương pháp này sử dụng kỹ thuật embedded coding; điều đó có nghĩa là một ảnh sau nén với kích cỡ (lưu trữ) lớn (tỷ lệ nén thấp) sẽ chứa chính dữ liệu sau nén của ảnh có kích cỡ (lưu trữ) nhỏ (tỷ lệ nén cao). Bộ mã hoá chỉ cần nén một lần nhưng có thể giải nén ra nhiều mức chất lượng khác nhau. Giả sử gọi các pixel trong một ảnh p cần mã hoá là pi, j. Áp dụng một phép biến đổi Wavelet T nào đó cho các pixel trong ảnh để tạo ra các hệ số của phép biến đổi Wavelet là ci, j. Các hệ số này tạo ra một ảnh biến đổi là C. Phép biến đổi này được viết dưới dạng toán tử như sau: C=T(p). Trong phương pháp truyền dẫn luỹ tiến với ảnh thì bộ mã hoá sẽ bắt đầu quá trình khôi phục (giải nén) ảnh bằng cách đặt các giá trị của ảnh khôi phục từ các hệ số biến đổi là . Sử dụng các giá trị giải mã của các hệ số biến đổi để tạo ra một ảnh khôi phục (vẫn chưa áp dụng biến đổi ngược Wavelet) là và sau đó áp dụng biến đổi ngược Wavelet để tạo ra ảnh cuối cùng là . Chúng ta có thể viết dưới dạng toán tử như sau:=T−1 (). Nguyên tắc quan trọng của phương pháp truyền dẫn ảnh theo kiểu luỹ tiến chính là phương pháp này luôn truyền đi các giá trị mang thông tin quan trọng hơn của ảnh đi trước. Sở dĩ làm như vậy là do các thông tin đó chính là các thông tin sẽ làm giảm thiểu nhiều nhất độ méo dạng của ảnh (sự sai khác giữa ảnh gốc và ảnh khôi phục). Đây chính là lý do tại sao phương pháp SPIHT luôn truyền đi các hệ số lớn trước và cũng là một nguyên tắc quan trọng của phương pháp này. Một nguyên tắc nữa là các bít có trọng số lớn bao giờ cũng mang thông tin quan trọng nhất trong dữ liệu nhị phân. Phương pháp SPIHT sử dụng cả hai nguyên tắc này; nó sắp xếp các hệ số biến đổi và truyền đi các bít có trọng số lớn nhất. Quá trình giải mã có thể dừng lại ở bất kỳ một bước nào ứng với giá trị ảnh cần mã hoá yêu cầu. Đây chính là cách mà phương pháp mã hoá SPIHT làm tổn thất thông tin. II.6.3.7. Phương pháp mã hoá EZW: Phương pháp mã hoá EZW (Embedded Zerotree Wavelet Encoder) cũng dựa trên cơ sở phép mã hoá luỹ tiến (progressive coding) giống như phương pháp mã hoá SPIHT. Phương pháp này chủ yếu dựa trên khái niệm về cây zero (zerotree). Về cơ bản, thuật toán này dựa trên hai nguyên tắc như đã trình bày ở phần phương pháp mã hoá SPIHT. Sau đây chúng ta sẽ xem xét các khái niệm cơ bản của thuật toán: Cây tứ phân: Sau khi áp dụng biến đổi Wavelet ứng với các mức phân giải khác nhau chúng ta có thể biểu diễn các hệ số biến đổi dưới dạng một cây. Ta thấy rằng với cây biểu diễn này cứ mỗi nút cha thì có 4 nút con. Sở dĩ có được điều này là do quá trình biến đổi Wavelet ở các tỷ lệ khác nhau. Ta gọi đây là các cây tứ phân (quadtree). H×nh 2.6.4: C©y tø ph©n Cây zero (zerotree): Cây zero là một cây tứ phân, trong đó tất cả các nút của nó đều nhỏ hơn nút gốc. Một cây như vậy khi mã hoá sẽ được mã hoá bằng một đối tượng duy nhất và khi giải mã thì chúng ta cho tất cả các giá trị bằng không. Ngoài ra để có thể mã hoá được các hệ số Wavelet trong trường hợp này, giá trị của nút gốc phải nhỏ hơn giá trị ngưỡng đang được xem xét ứng với hệ số Wavelet đó Sau khi có đủ các khái niệm cần thiết về cây tứ phân và cây zero, chúng ta có thể trình bày nguyên lý hoạt động của thuật toán. Thuật toán sẽ mã hoá các hệ số theo thứ tự giảm dần. Chúng ta sẽ dùng một giá trị gọi là ngưỡng (threshold) và sử dụng ngưỡng này để tiến hành mã hoá các hệ số biến đổi. Các hệ số được mã hoá theo thứ tự từ vùng tần số thấp đến vùng tần số cao. Và chỉ những hệ số có giá trị tuyệt đối lớn hơn hoặc bằng ngưỡng thì mới được mã hoá. Tiếp theo giảm ngưỡng và tiếp tục làm như vậy cho tới khi ngưỡng đạt tới một giá trị nhỏ hơn giá trị của hệ số nhỏ nhất. Cách giảm giá trị ngưỡng ở đây thực hiện tương đối đặc biệt, giá trị của ngưỡng giảm xuống một nửa so với trước đó. Bộ giải mã phải biết các mức ngưỡng này thì mới có thể giải mã ảnh thành công. Nhưng khi ta đi từ nút cha đến nút con trong cây tứ phân thì nó vẫn có 3 nút con. Vậy ta phải đi theo nhánh có nút con nào trước. Hay nói một cách đầy đủ hơn ta di chuyển từ hệ số này đến hệ số khác theo thứ tự như thế nào. Có nhiều cách di chuyển khác nhau, tuy nhiên hai cách di chuyển trên hình trên được sử dụng nhiều nhất. H×nh 2.6.5 Việc sắp xếp này còn phải được quy ước thống nhất giữa quá trình mã hoá và quá trình giải mã để việc giải mã ảnh được thành công. Trên đây chỉ là nguyên lý cơ bản của phương pháp mã hoá EZW. Hiện nay phương pháp mã hoá này được áp dụng ngày càng nhiều nén ảnh động. Phương pháp này cho tỉ lệ nén và độ tin cậy giải mã cao. Ngoài ra phương pháp EZW rất dễ triển khai trên máy tính bởi phương pháp này không yêu cầu việc lập trình quá phức tạp. II.6.4.So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác: Một tính năng quan trọng và là ưu điểm rõ nét nhất của JPEG2000so với JPEG cũng như các chuẩn nén ảnh khác như MPEG 4 VTC hay JPEG - LS v. v.... là JPEG2000 đưa ra cả hai kỹ thuật nén có tổn thất và không tổn thất theo cùng một cơ chế mã hoá nghĩa là JPEG2000 thực hiện tất cả các dạng thức của JPEG chỉ bằng một cơ chế mã hoá duy nhất. Nếu xét về sự tồn tại của hai kỹ thuật này thì JPEG cũng có khả năng nén ảnh có tổn thất và không tổn thất thông tin. Tuy nhiên với JPEG thì cơ chế mã hoá với hai dạng này là khác nhau và rất khó để sử dụng cả hai dạng này cùng lúc cho cùng một ứng dụng. Do đó, có thể thấy rằng JPEG có tính mềm dẻo hơn bất kỳ chuẩn nén ảnh tĩnh nào trước đây. Hơn thế, chúng ta đã thấy rằng tất cả các phương pháp thiết kế cho chuẩn JPEG2000 đều ưu việt và có nhiều tính năng hơn so với JPEG; ngoài ra những thống kê về thực tế cho thấy với cùng một tỷ lệ nén và một loại ảnh thì ảnh được nén bởi JPEG2000 hầu như luôn có chất lượng tốt hơn so với JPEG. Chúng ta xem xét hai ảnh trên hình 2.6.6 để thấy rõ điều này, ảnh bên trái được nén theo JPEG còn ảnh bên phải được nén theo JPEG2000. JPEG JPEG 2000 JPEG JPEG 2000 H×nh 2.6.6 (a ,b) Tính năng ưu việt thứ hai của JPEG2000 so với JPEG chính là trong dạng thức nén có tổn thất thông tin, JPEG2000 có thể đưa ra tỷ lệ nén cao hơn nhiều so với JPEG. Các phần mềm nén ảnh JPEG hiện tại (kể cả Photoshop) cũng chỉ thiết kế để có thể nén được tới tỷ lệ 40:1nhưng với JPEG2000 thì tỷ lệ nén có thể lên tới 200:1. Theo công thức tính PSNR trong đơn vị dB, chúng ta có: (b là số bít dùng biểu diễn một pixel trên ảnh gốc) PSNR(dB) = Trong đó MSE( Mean square error ) là sai số bình phương trung bình , PSNR (peak to signal to noise ratio) là tỉ số tín hiệu trên nhiễu đỉnh.MSE thường được gọi là phương sai lượng tử - (quantization error variance) .MSE giữa ảnh gốc và ảnh khôi phục được tính như sau : Trong đó tổng lấy theo j, k tính cho tổng tất cả các điểm ảnh trong ảnh và N là số điểm ảnh trong ảnh. RMSE là căn bậc 2 của MSE . Với hai ảnh ở hình 2.6.6, sự so sánh về tham số PSNR cho trên bảng bên dưới. Để có thể so sánh dễ dàng hơn, ta xét ảnh được nén với các tỷ lệ khác nhau (đo lường bởi hệ số bít/pixel hay bpp). Tất cả các số liệu trên bảng đều cho thấy JPEG2000 nén ảnh tốt hơn là JPEG; hơn thế hệ số PSNR mà chúng ta xét trong bảng được đo trong hệ đơn vị logarit. Bit per pixel 0.125 0.50 2.00 Ảnh 1 theo JPEG 24.42 31.17 35.15 Ảnh 1 theo JPEG2000 28.12 32.95 37.35 Ảnh 2 theo JPEG 22.6 28.92 35.99 Ảnh 2 theo JPEG2000 24.85 31.13 38.80 Tính năng ưu việt thứ 3 của JPEG2000 so với JPEG là chuẩn nén ảnh này có thể hiển thị được các ảnh với độ phân giải và kích thước khác nhau từ cùng một ảnh nén. Với JPEG thì điều này là không thể thực hiện được. Sở dĩ có điều này là do JPEG2000 sử dụng kỹ thuật phân giải ảnh và mã hoá đính kèm mà chúng ta đã nói tới ở phần mã hoá ảnh theo JPEG2000. Tính năng này là một lợi thế đặc biệt quan trọng của JPEG2000, trong khi JPEG cũng như các chuẩn nén ảnh tĩnh trước đây phải nén nhiều lần để thu được chất lượng với từng lần nén khác nhau thì với JPEG2000 ta chỉ cần nén một lần còn chất lượng ảnh thì sẽ được quyết định tuỳ theo người sử dụng trong quá trình giải nén ảnh theo JPEG2000.Một tính năng ưu việt nữa của JPEG2000 là tính năng mã hoá ảnh quan trọng theo vùng (ROI - Region of Interest) mà chúng ta đã đề cập trong phần mã hoá ảnh theo JPEG2000. Hình 2.6.7 : Minh hoạ tính năng ROI JPEG2000 còn có một khả năng đặc biệt ưu việt hơn so với JPEG, đó chính là khả năng vượt trội trong khôi phục lỗi. Đó là khi một ảnh được truyền trên mạng viễn thông thì thông tin có thể bị nhiễu; với các chuẩn nén ảnh như JPEG thì nhiễu này sẽ được thu vào và hiển thị, tuy nhiên với JPEG2000, do đặc trưng của phép mã hoá có thể chống lỗi, JPEG2000 có thể giảm thiểu các lỗi này tới mức hầu như không có. Ch­¬ng III: Cµi ®Æt ch­¬ng tr×nh vµ thö nghiÖm Tõ nh÷ng c¬ së lý thuyÕt tr×nh bµy ë trªn em ®· tiÕn hµnh cµi ®Æt ch­¬ng tr×nh cho mét sè ph­¬ng ph¸p nÐn ¶nh : RLE, HUFFMAN, LZW, JPEG trªn ng«n ng÷ lËp tr×nh Visual C++ 6.0. Ch­¬ng tr×nh ch¹y t­¬ng ®èi æn ®Þnh nh­ng chØ hç trî ®Þnh d¹ng ¶nh Bitmap. C¸c ph­¬ng ph¸p RLE, HUFFMAN, LZW ch­¬ng tr×nh chØ ch¹y tèt trªn ¶nh Bitmap 256 mµu cßn ®èi víi JPEG th× hiÖn thêi míi hç trî cho ¶nh Bitmap 24 bit mµu. C¸c file ¶nh ®­îc nÐn theo c¸c ph­¬ng ph¸p kh¸c nhau sÏ ®­îc l­u víi c¸c ®Þnh d¹ng ®uçi kh¸c nhau HUFFMAN (*.huff) , LZW (*.lzw) , JPEG (*.jpg) riªng RLE vÉn gi÷ nguyªn ®u«i *.bmp. Ngoµi c¸c th­ viÖn vµ c¸c hµm ®­îc hç trî s½n trong Visual C++ 6.0 ch­¬ng tr×nh cßn sö dông thªm mét sè th­ viÖn riªng. C¸c thuËt to¸n ®Òu cã ­u nh­îc ®iÓm kh¸c nhau vµ ®em l¹i kÕt qu¶ ch­¬ng tr×nh kh¸c nhau. Tèc ®é nÐn vµ hiÖu qu¶ nÐn cña c¸c ph­¬ng ph¸p rÊt kh¸c nhau do ®é phøc t¹p gi¶i thuËt vµ chÊt l­îng ¶nh kÕt qu¶ yªu cÇu lµ kh¸c nhau. Ph­¬ng ph¸p RLE, HUFFMAN cho kÕt qu¶ nhanh chãng vµ chÊt l­îng ¶nh kh«ng thay ®æi nh­ng hiÖu suÊt nÐn th­êng kh«ng cao ®èi víi ¶nh Bitmap 256 mµu cßn ph­¬ng ph¸p LZW do trong thuËt to¸n ph¶i x©y dùng tõ ®iÓn nªn tèc ®é nÐn t­¬ng ®èi chËm nh­ng kÕt qu¶ nÐn rÊt cao.Cuèi cïng ph­¬ng ph¸p JPEG th× chÊt l­îng ¶nh nÐn vµ hiÖu qu¶ nÐn tû lÖ nghÞch víi nhau, chÊt l­îng ¶nh nÐn tèt th× kÝch th­íc file gi¶m Ýt vµ ng­îc l¹i . Giao diÖn chÝnh ch­¬ng tr×nh : Ph­¬ng ph¸p nÐn ¶nh RLE Xem ¶nh Ph­¬ng ph¸p nÐn ¶nh HUFFMAN Ph­¬ng ph¸p nÐn ¶nh LZW Ph­¬ng ph¸p nÐn ¶nh JPEG §­êng dÉn file ®Ých §­êng dÉn file nguån KÝch th­íc file ®Ých KÝch th­íc file nguån C¸c b­íc thùc hiÖn ch­¬ng tr×nh : Chän môc ®Ých thùc hiÖn nÐn (Compression) hoÆc gi¶i nÐn (Decompression ) trong ph­¬ng ph¸p nÐn muèn sö dông. Click vµo nót “Duongdan” thø nhÊt ®Ó më file muèn thùc thi ,nÕu muèn xem ¶nh chän (nÕu lµ ¶nh Bitmap) th× click nót >> ®Ó xem ¶nh cßn kÝch th­íc file hiÓn thÞ bªn d­íi. Click vµo nót “Duongdan” thø hai ®Ó chØ ®­êng dÉn ®Õn file muèn l­u l¹i kÕt qu¶. Click nót “Thuchien” xong ch­¬ng tr×nh sÏ th«ng b¸o b»ng hép héi tho¹i MessageBox cßn riªng víi JPEG ta cßn ph¶i chän chÊt l­îng ¶nh nÐn th× míi thùc hiÖn nÐn. ChÊt l­îng cµng cao th× ¶nh sÏ Ýt bÞ thay ®æi nh­ng hiÖu suÊt nÐn thÊp vµ ng­îc l¹i. Th«ng b¸o hoµn tÊt nÐn hoÆc gi¶i nÐn KÕt luËn KÕt qu¶ ®¹t ®­îc vµ øng dông cña ®å ¸n §å ¸n ®· tr×nh bµy c¸c kh¸i niÖm quan träng cÇn thiÕt cña kü thuËt nÐn ¶nh nãi chung vµ c¸c nguyªn t¾c , c¬ së lý thuyÕt ,thuËt to¸n cña mét sè ph­¬ng ph¸p nÐn ¶nh phæ biÕn nh­ : m· lo¹t dµi RLE, HUFFMAN, LZW, JPEG, JPEG2000.Trong ®ã tr×nh bµy ph­¬ng ph¸p nÐn ¸nh JPEG2000 sö dông biÕn ®æi Wavelet ®Ó nÐn ¶nh, ®©y lµ ph­¬ng ph¸p nÐn ¶nh ®ang ®­îc quan t©m ph¸t triÓn v× c¸c tÝnh n¨ng næi bËt so víi c¸c ph­¬ng ph¸p kh¸c. Ph­¬ng ph¸p nµy kh«ng chØ cho hiÖu suÊt nÐn cao, chÊt l­îng ¶nh b¶o ®¶m so víi c¸c ph­¬ng ph¸p nÐn RLE, HUFFMAN, LZW, JPEG mµ cßn c¸c tÝnh n¨ng riªng biÖt do s­ dông biÕn ®æi Wavelet ®Ó nÐn ¶nh nh­ : nÐn ¶nh theo vïng (ROI) , trong mét ¶nh c¸c vïng hoÆc c¸c ®èi t­îng cã thÓ cã tû lÖ nÐn kh¸c nhau ,nÐn ¶nh mét lÇn nh­ng cã thÓ gi¶i nÐn ¶nh víi chÊt l­îng ¶nh vµ kÝch th­íc ¶nh kh¸c nhau tuú theo yªu cÇu ng­êi sö dông ....C¸c ph­¬ng ph¸p nÐn tr×nh bµy ë trong ®å ¸n lµ nh÷ng ph­¬ng ph¸p ®ang ®­îc sö dông kh¸ réng r·i trong nhiÒu lÜnh vùc ®Æc biÖt trong truyÒn th«ng cho ¶nh trªn m¹ng ®¶m b¶o tèc ®é, thêi gian vµ chÊt l­îng d÷ liÖu truyÒn. H­íng ph¸t triÓn nghiªn cøu Mét sè h­íng nghiªn cøu trong t­¬ng lai : §å ¸n míi ®Ò cËp ®Õn c¸c ph­¬ng ph¸p nÐn ¶nh tÜnh mµ ch­a øng dông chóng cho ©m thanh, video, ®Æc biÖt lµ biÕn ®æi Wavelet cña chuÈn JPEG2000 do ®ã viÖc ®i s©u nghiªn cøu t×m hiÓu c¸c hä cña Wavelet lµ rÊt cÇn thiÕt. Nghiªn cøu thªm vÒ c¸c gi¶i thuËt SPIHT, EZW vµ c¸c øng dông cña chóng. C¸c ph­¬ng ph¸p nÐn ®­îc tr×nh bµy trong ®å ¸n ®· ra ®êi tõ nhiÒu n¨m tr­íc do ®ã cÇn nghiªn cøu nh÷ng c¶i tiÕn ®èi víi mçi phu¬ng ph¸p ®Ó n©ng cao hiÖu qu¶ nÐn. C¸c tµi liÖu tham kh¶o: 1. PGS.NguyÔn Thanh Thuû, Ths.L­¬ng M¹nh B¸, NhËp m«n xö lý ¶nh sè 2. Vâ §øc Kh¸nh (2003),Gi¸o tr×nh xö lý ¶nh , Nxb Thèng kª, Hµ Néi 3. D.Huffman , A method for the contruction of minimum – redundancy codes, Proc IRE 40, 1098-1101 (1952) 4. NguyÔn Kim S¸ch (1997), Xö lý ¶nh vµ video sè , Nxb Khoa häc vµ Kü thuËt , Hµ Néi . 5. Michael David Adams - Faouzi Kossentini - Touraji Ebrahimi - “JPEG2000 : The Next Generation Still Image Compression Standard” (2000) 6. Website: 7. Website: