Báo cáo nghiên cứu khoa học: Nén ảnh fractal

Tuyển tập những báo cáo nghiên cứu khoa học hay nhất của trường đại học vinh tác giả: 10. Phạm Quang Trình, Trần Hữu Tâm, Nén ảnh fractal ...Công nghệ (hay công nghệ học hoặc kỹ thuật học) có nhiều hơn một định nghĩa. Nhìn chung có thể hiểu công nghệ là tập hợp các phương pháp, quy trình, kỹ năng, bí quyết, công cụ, phương tiện dùng để biến đổi các nguồn lực thành sản phẩm. Như vậy công nghệ là việc phát triển và ứng dụng của các dụng cụ, máy móc, nguyên liệu và quy trình để...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: "Nén ảnh fractal " §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 nÐn ¶nh fractal Ph¹m Quang Tr×nh (a), TrÇn H÷u T©m (b) Tãm t¾t. Bµi b¸o nµy t×m hiÓu øng dông cña h×nh häc Fractal trong viÖc nÐn ¶nh. KÕt qu¶ cña bµi b¸o lµ c¶i tiÕn ph−¬ng ph¸p ph©n h×nh tø ph©n vµ cµi ®Æt ch−¬ng tr×nh nÐn ¶nh Fractal b»ng ph−¬ng ph¸p nµy. 1. §Æt vÊn ®Ò ViÖc øng dông h×nh häc Fractal vµo thùc tÕ ®· ®¹t ®−îc nhiÒu kÕt qu¶ tèt trong c¸c ngµnh khoa häc tù nhiªn vµ x· héi. Trong khoa häc m¸y tÝnh, h×nh häc Fractal gióp cho viÖc thiÕt kÕ h×nh ¶nh ®Ñp trªn m¸y tÝnh mét c¸ch ®¬n gi¶n vµ trùc quan. Trong xö lý ¶nh, h×nh häc Fractal gióp cho viÖc nÐn ¶nh trªn m¸y tÝnh th«ng qua hÖ hµm lÆp IFS, PIFS... mét c¸ch hiÖu qu¶. Trong nh÷ng n¨m gÇn ®©y, viÖc nghiªn cøu ph¸t triÓn ch−¬ng tr×nh nÐn ¶nh Fractal ®ang gÆp nhiÒu khã kh¨n, c¸c kÕt qu¶ ®¹t ®−îc cßn h¹n chÕ nh−: ch−¬ng tr×nh míi chØ nÐn víi c¸c lo¹i ¶nh x¸m, tØ lÖ nÐn ch−a cao vµ thêi gian nÐn vÉn cßn l©u. Trong bµi viÕt nµy chóng t«i chØ ra h¹n chÕ cña mét sè ph−¬ng ph¸p nÐn ¶nh Fractal vµ kh¾c phôc nh÷ng h¹n chÕ ®ã. Trªn c¬ së lý thuyÕt cña h×nh häc Fractal vµ c¸c ph−¬ng ph¸p nÐn ¶nh Fractal chóng t«i ®· cµi ®Æt ®−îc mét ch−¬ng tr×nh nÐn ¶nh tèt h¬n nh÷ng ch−¬ng tr×nh ®· cã ë chç nã cã thÓ nÐn ®−îc ¶nh mµu vµ nÐn ®−îc nhiÒu kiÓu ¶nh kh¸c nhau: BITMAP, JPG, WMF, ICON... 2. nÐn ¶nh Fractal 2.1. Kh¸i niÖm vÒ nÐn ¶nh Fractal Gi¶ sö ta cã mét m¸y photo ®Æc biÖt, m¸y nµy t¹o ra 3 ¶nh thu nhá trªn cïng mét b¶n copy mµ mçi ¶nh cã kÝch th−íc gi¶m ®i mét nöa so víi kÝch th−íc ban ®Çu. H×nh 1. Mét m¸y photo t¹o ra 3 b¶n sao thu nhá cña ¶nh ban ®Çu NhËn bµi ngµy 20/9/2006. Söa ch÷a xong 08/01/2007. 73 §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 H×nh 1 minh ho¹ mét phÐp lÆp theo c¸ch xö lý cña m¸y copy ®èi víi mét ¶nh. Ta thÊy r»ng, nÕu qua nhiÒu lÇn lÆp tÊt c¶ c¸c b¶n photo cña c¸c ¶nh cïng héi tô vÒ mét ¶nh. ¶nh cuèi cïng thu ®−îc mang tÝnh chÊt tù t−¬ng tù ë hÇu hÕt c¸c chi tiÕt, ®ã chÝnh lµ mét tÝnh chÊt cña Fractal. Bøc ¶nh thu ®−îc nµy chÝnh lµ tËp hót cña m¸y photo (xem [5]). M¸y photo cã thÓ nhËn bÊt kú mét ¶nh nµo ®−a vµo ®Ó råi cho ra b¶n copy cã kÝch th−íc gi¶m nh−ng sè b¶n t¨ng lªn. V× vËy, nÕu qu¸ tr×nh nµy thùc hiÖn theo mét chu tr×nh lÆp, sè b¶n copy sÏ t¨ng lªn nh−ng kÝch cì gi¶m dÇn. C¸c phÐp biÕn ®æi kh¸c nhau qua qu¸ tr×nh lÆp sÏ dÉn ®Õn c¸c tËp hót kh¸c nhau. C¸c phÐp biÕn ®æi ë ®©y lµ c¸c ¸nh x¹ co. Th«ng th−êng, nÕu nh− c¸c ®iÓm ¶nh trªn b¶n copy më réng dÇn ra th× tËp hót cã thÓ cã kÝch cì v« h¹n. §Ó lo¹i trõ ®iÒu nµy th× c¸c phÐp biÕn ®æi ph¶i cã giíi h¹n bëi mét vµi d¹ng nµo ®ã. Trong thùc tÕ ng−êi ta chän c¸c ¸nh x¹ cã d¹ng e i   x  a bi   x  wi   =  i f  d i  y +  y  ci    i ®Ó sinh ra tËp c¸c ¸nh x¹ co. H×nh 2. Ba b¶n copy ®−îc t¹o ra qua m¸y photo ë h×nh 2.1 C¸c phÐp biÕn ®æi nh− vËy gäi lµ phÐp biÕn ®æi affine trªn mÆt ph¼ng nh− phÐp quay, tÞnh tiÕn, phÐp chia nhá theo tû lÖ vµ thay ®æi ¶nh ®−a vµo,.. 74 §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 Mét ®Æc ®iÓm cña tÊt c¶ c¸c tËp hót lµ th«ng th−êng chóng ®−îc h×nh thµnh theo c¸ch nµy, vÞ trÝ cña mét phÇn ¶nh trong ¶nh ban ®Çu lµ c¸c b¶n ®−îc copy trªn toµn bé ¶nh. Bøc ¶nh ®−îc h×nh thµnh tõ phÐp biÕn ®æi (gi¶m kÝch cì) copy chÝnh nã, v× thÕ cho nªn nã cã chi tiÕt ë mäi tû lÖ, c¸c ¶nh ®ã ®−îc gäi lµ c¸c ¶nh Fractal. Ph−¬ng ph¸p t¹o ¶nh Fractal thùc hiÖn bëi John Hutchinson vµ M. Barnsley ®· ®Ò xuÊt viÖc l−u tr÷ ¶nh nh− mét tËp hîp c¸c ¸nh x¹ ®Ó cã thÓ øng dông trong viÖc nÐn ¶nh. 2.2. ThuËt to¸n nÐn ¶nh Fractal 2.2.1. ThuËt to¸n nÐn ¶nh Fractal tæng qu¸t ThuËt to¸n nµy do Micheal Barnsley ®Ò xuÊt. Theo Barnsley th× ta chia ¶nh f ®· cho thµnh c¸c h×nh vu«ng rêi nhau kÝch th−íc B×B ®iÓm ¶nh gäi lµ c¸c khèi range vµ ký hiÖu lµ Ri. Sau ®ã ta chia ¶nh thµnh mét tËp c¸c khèi cã kÝch th−íc 2B×2B ®iÓm ¶nh gäi lµ c¸c khèi domain vµ ký hiÖu lµ Dj, c¸c khèi Dj kh«ng nhÊt thiÕt ph¶i rêi nhau. B©y giê, víi mçi khèi Ri ta ph¶i t×m mét khèi Dj vµ mét ¸nh x¹ co wi sao cho Dj qua ¸nh x¹ co wi võa t×m ®−îc sÏ xÊp xØ Ri, (xem [5]). 2.2.2. ThuËt to¸n gi¶i m· ¶nh Fractal tæng qu¸t ViÖc gi¶i nÐn bao gåm viÖc lÆp l¹i ¸nh x¹ co W tõ mét ¶nh bÊt kú nµo ®ã cho ®Õn khi ®−îc ®iÓm bÊt ®éng (¶nh ®−îc t¹o ra tõ W) xÊp xØ ¶nh gèc, (xem [5]). 2.2.3. ThuËt to¸n nÐn ¶nh QD (Quadtree Decomposition) B−íc 1. Ph©n chia M thµnh c¸c khèi ®Ých Ri lµ c¸c khèi vu«ng cã kÝch th−íc B×B ®iÓm ¶nh (kÝch th−íc lín nhÊt), vµ chia M thµnh c¸c khèi nguån Dj lµ c¸c khèi vu«ng cã kÝch th−íc 2B × 2B ®iÓm ¶nh. B−íc 2. §Æt S = {Ri}, i = 1, 2, ..., (n/2B); B−íc 3. While khi S ≠ ∅ do (i) LÊy Ri ra khái S; (ii) For j = 1 to 8 do Begin R’i = §Cj (Ri); //PhÐp ®¼ng cù thø j ®èi víi Ri. For each Dk ⊂ M do T×m si, oi sao cho d(si×Dk + oi, R’i) ≤ ε; End; If t×m ®−îc then ghi th«ng tin vÒ Dk, Ri, §Cj, si, oi Else If Ri ®· ®¹t ®−îc kÝch th−íc tèi thiÓu then §¸nh dÊu Ri lµ khèi háng vµ l−u th«ng tin tèi thiÓu cho Ri Else chia Ri thµnh 4 khèi « vu«ng con vµ thªm vµo S. 75 §¹i häc Vinh T¹p chÝ khoa häc, t ...