intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST
Báo xấu
164
lượt xem 39
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 để...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Nén ảnh fractal "

  1. §¹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
  2. §¹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
  3. §¹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
  4. §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 ë ®©y §Cj(Ri) ®−îc hiÓu lµ phÐp ®¼ng cù thø j trªn khèi Ri, d lµ mét mªtric nµo ®ã trong 3 mªtric sau g ( x, y ) , ∀f, g ∈ F sup(f, g) = sup f ( x, y ) ( x , y )∈M ∑ ( f ( x, y) − g ( x, y)) 2 , ∀f, g ∈ F dms(f, g) = ( x , y )∈M 1n ∑ ( f ( xi , y i ) − g ( xi , y i )) 2 , ∀f, g ∈ F, drms(f, g) = n i =1 trong ®ã n lµ sè ®iÓm ¶nh cña f vµ g. Khi ®ã c¸c kh«ng gian (F, dsup), (F, dms), (F, drms) lµ c¸c kh«ng gian mªtric ®Çy ®ñ (xem [5]). ViÖc gi¶i m· bao gåm viÖc lÆp l¹i ¸nh x¹ co W tõ mét ¶nh nµo ®ã. Sù ph©n chia tø ph©n ®−îc sö dông ®Ó x¸c ®Þnh tÊt c¶ c¸c khèi Range trªn ¶nh. Víi mçi khèi range Ri, khèi domain Dj t−¬ng øng ¸nh x¹ lªn nã ®−îc co l¹i b»ng c¸ch lÊy trung b×nh céng cña tõng khèi. C¸c gi¸ trÞ mµu cña c¸c pixel trªn Dj sau khi ®−îc co l¹i sÏ ®−îc nh©n víi si råi céng víi oi vµ ®−îc ®Æt vµo trong range ®· ®−îc x¸c ®Þnh theo th«ng tin cña phÐp ®¼ng cù. C«ng viÖc nµy sÏ ®−îc lÆp l¹i cho ®Õn khi ®iÓm bÊt ®éng cña ¸nh x¹ W xÊp xØ víi ¶nh gèc. Nh− vËy ta nhËn thÊy cã thÓ l−u tr÷ Range thay cho viÖc ph¶i l−u tr÷ c¶ Range vµ Domain. §iÒu nµy cã thÓ h¹n chÕ ®−îc sè l−îng ¸nh x¹ co ph¶i thö, t¨ng tèc ®é cña gi¶i thuËt nÐn ¶nh Fractal, viÖc gi¶i nÐn chÝnh lµ viÖc ghÐp c¸c vïng ®ång mµu theo mét trËt tù ®Ó cã ®−îc ¶nh gèc. 3. C i ®Æt ch−¬ng tr×nh nÐn ¶nh 3.1 M« h×nh ¶nh M« h×nh cña ¶nh lµ hµm cã d¹ng f: M → R × G × B, trong ®ã M ⊂ »2 lµ gi¸ cña ¶nh, víi c¸c ¶nh sè cã ®é ph©n gi¶i h÷u h¹n th× M lµ mét l−íi rêi r¹c m×n ®iÓm ¶nh vµ M ⊂ »2. R, G, B lµ thµnh phÇn ®é mµu cña c¸c ®iÓm, R, G, B ∈ [0; 255]. 3.2. ý t−ëng nÐn Dùa vµo ph−¬ng ph¸p ph©n h×nh tø ph©n ®· ®−îc ®Ò cËp ®Õn, ta xÐt mét ¶nh vu«ng kÝch th−íc 2k 2k (k nguyªn vµ kh«ng ©m). VÝ dô ¶nh cã kÝch th−íc 256 × 256 (2k 2k). 76
  5. §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 H×nh 3.1 H×nh 3.2 H×nh 3.3 §Çu tiªn ta xÐt xem ¶nh cã ph¶i lµ mét vïng ®ång mµu hay kh«ng. NÕu ph¶i th× l−u to¹ ®é ®Ønh tr¸i trªn, kÝch th−íc vµ mµu cña c¶ ¶nh ®ã vµo file, ng−îc l¹i th× chia ¶nh thµnh 4 ¶nh con, mçi ¶nh ®Òu lµ h×nh vu«ng cã kÝch th−íc 128 ×128 (2k-1 2k1), tiÕp tôc xÐt nh− trªn ®èi víi tõng ¶nh. Qu¸ tr×nh ®−îc lÆp l¹i cho ®Õn khi ta thu ®−îc c¸c h×nh vu«ng ®ång mµu hay kÝch th−íc cña chóng bÐ h¬n vïng cùc tiÓu cho tr−íc. 3.3. ý t−ëng gi¶i nÐn Dùa trªn c¸ch l−u tr÷ c¸c vïng ®ång mµu mµ ta ®−a ra c¸ch gi¶i nÐn. Nãi chung viÖc gi¶i nÐn chÝnh lµ viÖc ghÐp c¸c vïng ®ång mµu (lµ c¸c ¶nh con cã ®−îc tõ c¸ch ph©n chia ¶nh gèc) theo mét trËt tù ®Ó cã ®−îc ¶nh gèc. H×nh 4. Lùa chän vïng cùc tiÓu ®èi víi ¶nh JPG 77
  6. §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 3.4. Ch−¬ng tr×nh + Giao diÖn ch−¬ng tr×nh H×nh 5. Giao diÖn ch−¬ng tr×nh + Thñ tôc ph©n h×nh: Procedure phanhinh(Image); + Thñ tôc ®äc file ¶nh: Procedure DocAnhClick (Sender: TObject); + Thñ tôc l−u file ¶nh: Procedure LuufileClick (Sender: Tobject); + Hµm lÊy mµu trung b×nh: Funtion LayMauTB (Vung: Tvung): MauRGB; + Thñ tôc Lùa chän vïng ¶nh: Funtion Xacdinhvung (Vung: Tvung;tlkv:byte): boolean; + Thñ tôc Gi¶i nÐn ¶nh: Procedure Giainen (path: String;var: TBitmap); + Thñ tôc chän nÐn hay gi¶i nÐn: Procedure TuychonClick (Sender: TObject); + §äc, l−u vïng ¶nh t¹m thêi Funtion Spop (top,stack); Procedure Spush (top,Stack,Image); Qua kÕt qu¶ nghiªn cøu vµ cµi ®Æt thuËt to¸n trªn chóng t«i cã mét sè kÕt luËn sau: ViÖc chän kÝch th−íc c¸c Range (vïng cùc tiÓu) ¶nh h−ëng ®Õn chÊt l−îng vµ tØ lÖ nÐn. KÝch th−íc Range lín th× tØ lÖ nÐn cao nh−ng chÊt l−îng ¶nh nÐn thÊp. §èi víi nh÷ng ¶nh cã nhiÒu vïng ®ång mµu cho kÕt qu¶ nÐn rÊt tèt, ng−îc l¹i cho hiÖu qu¶ nÐn ch−a cao ®èi víi nh÷ng ¶nh cã ®é dÞch chuyÓn mµu phøc t¹p. 78
  7. §¹i häc Vinh T¹p chÝ khoa häc, tËp XXXVI, sè 3A-2007 4. KÕt luËn Dùa trªn c¬ së cña ph©n h×nh tø ph©n vµ c¸ch l−u tr÷ Range, Domain trong c¸c ph−¬ng ph¸p nÐn ¶nh cña Fractal, chóng t«i ®· cµi ®Æt ®−îc ch−¬ng tr×nh nÐn ¶nh Fractal víi mét sè −u ®iÓm sau - Thêi gian nÐn nhanh - TØ lÖ nÐn kh¸ cao - NÐn nhiÒu kiÓu file ¶nh kh¸c nhau nh− : BMP, ICON, WMF, JPG... - NÐn ¶nh mµu. Trong thêi gian tíi, chóng t«i sÏ tiÕp tôc t×m hiÓu, cµi ®Æt ch−¬ng tr×nh nÐn ¶nh fractal theo c¸c ph−¬ng ph¸p kh¸c. T i liÖu tham kh¶o [1] K. J. Falconer, Fractal Geometry: mathematical foundtions and applications, John Wiley & Sons, Inc, 1990. [2] Y. Fisher, Fractal Image Compression Theory and Application, Springer - Verlag, 1995. [3] Hannes Hartenstein, Matthias Ruhl, Dietmar Saupe, Region-Based Fractal Image Compression, IEEE Transactions on Image Processing, March, 1999. [4] Lª H÷u §¹t, C¸c kÜ x¶o lËp tr×nh víi Visual Basic vµ lËp tr×nh Borland Delphi, Nhµ xuÊt b¶n Gi¸o dôc, 2000. [5] Ng« Quèc T¹o, C¬ së h×nh häc Fractal vµ ch−¬ng tr×nh thö nghiÖm Fractal, Trung t©m KHTN & CNQG-TT98-04, Hµ Néi, 1998. [6] http://www.femtosoft.biz/fractals. Summary Fractal image compressions This article studied the application of Fractal geometric theory to image compressions. Its results used to improve the quadtree-division method and install the program of Fractal image compressions utilizing the mentioned method. (a) Häc viÖn Qu¶n lý gi¸o dôc, Bé Gi¸o dôc v § o t¹o (b) Häc viªn cao häc CNTT, Tr−êng ®¹i häc s− ph¹m H Néi. 79
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.01: Bộ Luận Văn Thạc Sĩ Quản Trị Kinh Doanh MBA
165 tài liệu
2069 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2