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

§å ¸n tèt nghiÖp 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 Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 1 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh Môc lôc Më ®Çu ............................................................................................................................ 3 CH-¬ng I: Giíi thiÖu tæng quan vÒ nÐn ¶nh ........................................... 4 I.1.Giíi thiÖu vÒ ¶nh sè vµ xö lý ¶nh sè....................................................................... 4 I.1.1.¶nh sè ................................................................................................................ 4 I.1.2.Xö lý ¶nh sè....................................................................................................... 5 I.2.Môc ®Ých vµ sù cÇn thiÕt cña nÐn ¶nh .................................................................. 6 I.3.C¸c kh¸i niÖm c¬ b¶n .............................................................................................. 7 Ch-¬ng II: C¸c ph-¬ng ph¸p nÐn ¶nh ......................................................... 9 II.1.C¸ch ph©n lo¹i c¸c ph-¬ng ph¸p nÐn ¶nh ........................................................... 9 II.1.1.C¸ch ph©n lo¹i dùa vµo nguyªn lý nÐn ......................................................... 9 II.1.2.C¸ch ph©n lo¹i dùa vµo c¸ch thøc thùc hiÖn nÐn......................................... 9 II.1.3.C¸ch ph©n lo¹i dùa vµo lý thuyÕt m· ho¸ .................................................. 10 II.1.4.Qu¸ tr×nh nÐn vµ gi¶i nÐn ............................................................................ 10 II.2.Ph-¬ng ph¸p m· ho¸ ®é dµi lo¹t RLE............................................................... 11 II.2.1.Nguyªn t¾c .................................................................................................... 11 II.2.2.ThuËt to¸n ..................................................................................................... 13 II.2.3.Mét sè thñ tôc ch-¬ng tr×nh ....................................................................... 14 II.3.Ph-¬ng ph¸p m· ho¸ Huffman .......................................................................... 19 II.3.1. Nguyªn t¾c .................................................................................................... 19 II.3.2. ThuËt to¸n .................................................................................................... 19 II.3.3.Mét sè thñ tôc ch-¬ng tr×nh ....................................................................... 24 II.4.Ph-¬ng ph¸p m· ho¸ LZW................................................................................. 27 II.4.1.Nguyªn t¾c ..................................................................................................... 27 II.4.2. ThuËt to¸n .................................................................................................... 31 II.4.3.Mét sè thñ tôc ch-¬ng tr×nh ....................................................................... 34 II.5.Ph-¬ng ph¸p m· ho¸ JPEG ................................................................................ 38 II.5.1.Nguyªn t¾c ..................................................................................................... 38 II.5.2.ThuËt to¸n ..................................................................................................... 38 II.5.3.Mét sè thñ tôc ch-¬ng tr×nh ....................................................................... 48 II.6.Ph-¬ng ph¸p m· ho¸ JPEG2000........................................................................ 54 II.6.1. Lịch sử ra đời và phát triển chuẩn JPEG2000 .......................................... 54 II.6.2.Các tính năng của JPEG2000 ...................................................................... 54 II.6.3.Các bước thực hiện nén ảnh theo chuẩn JPEG2000 ................................. 55 II.6.3.1.Xử lý trước biến đổi............................................................................... 55 II.6.3.2. Biến đổi liên thành phần ..................................................................... 55 II.6.3.3. Biến đổi riêng thành phần (biến đổi Wavelet) .................................... 56 II.6.3.4. Lượng tử hoá - Giải lượng tử hoá ...................................................... 57 II.6.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá...................................... 58 II.6.3.6. Phương pháp mã hoá SPIHT ............................................................... 59 II.6.3.7. Phương pháp mã hoá EZW .................................................................. 60 II.6.4.So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác .... 62 Ch-¬ng III: Cµi ®Æt ch-¬ng tr×nh vµ thö nghiÖm ............................ 66 KÕt luËn...................................................................................................................... 69 Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 2 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 3 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 4 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶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÷. C¸c giai ®o¹n chÝnh trong xö lý ¶nh cã thÓ ®-îc m« t¶ trong h×nh sau: L-u tr÷ CAMERA Thu nhËn ¶nh Sè ho¸ Ph©n tÝch ¶nh NhËn d¹ng dd¹ng¹ng SENSOR L-u tr÷ Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 HÖ quyÕt ®Þnh Trang : 5 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 6 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p 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. NhvË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. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 7 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh “ 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). Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 8 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 9 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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 D÷ liÖu gèc D÷ liÖu nÐn Qu¸ tr×nh gi¶i nÐn H×nh 2.1 : Qu¸ tr×nh nÐn vµ gi¶i nÐn Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 10 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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) Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 11 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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 Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 12 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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) Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 13 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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; Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 14 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh } 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) || Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 15 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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; } Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 16 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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; Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 17 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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; } Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 18 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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±. Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 19 §å ¸n tèt nghiÖp T×m hiÓu mét sè ph-¬ng ph¸p nÐn ¶nh 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 1532 1 152 2 323 3 412 4 226 5 385 6 602 7 92 8 112 9 87 B¶ng tÇn suÊt s¾p xÕp gi¶m dÇn KÝ tù X¸c suÊt (%) 0 0.3906 6 0.1535 3 0.1051 5 0.0982 2 0.0824 4 0.0577 1 0.0388 8 0.0286 7 0.0235 9 0.0222 Sinh viªn thùc hiÖn : T¹ Minh Th¾ng CT 702 Trang : 20