研究生: |
陳慶全 Ching-Chuan Chen |
---|---|
論文名稱: |
碎形樹在可縮放式向量繪圖壓縮技術之探討 Study of SVG Compression on Fractal Tree Rendering |
指導教授: |
葉耀明
Yeh, Yao-Ming |
學位類別: |
碩士 Master |
系所名稱: |
資訊教育研究所 Graduate Institute of Information and Computer Education |
論文出版年: | 2005 |
畢業學年度: | 93 |
語文別: | 中文 |
論文頁數: | 100 |
中文關鍵詞: | 碎形、、 、樹 、壓縮 |
英文關鍵詞: | XML, SVG, L-system, Fractal, Tree, Compression |
論文種類: | 學術論文 |
相關次數: | 點閱:306 下載:1 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
許多電腦圖形系統在繪製有規律特性的自然影像時,例如樹木、雲朵、山脈、海洋等,採用Lindenmayer系統(簡稱為L-system)的理論,其使用單純、含有圖形意義的符號及具規律性質的規則,來衍生出逼真且複雜的碎形圖形。
本研究以L-system為描述碎形樹的基礎語言,先探討如何以SVG(Scalable Vector Graphics)在2D及3D碎形樹的呈現。一般圖形語言在呈現碎形樹時,隨著L-system語言中遞迴數增長,所需繪製的樹枝圖形物件呈指數成長,本研究探討如何有效降低龐大的圖形物件數,並提出幾種壓縮策略,來分析各種策略對哪幾類碎形樹的適用性,以及壓縮效果於檔案容量及記憶體使用量的分析。
本研究發展的壓縮演算法,依照不同類型的碎形樹,可透過此壓縮演算法,達到壓縮物件數量為原始物件數的70%至20%,讓使用者可以觀看更複雜的碎形樹之時,同時減低系統記憶體的使用量及降低網際網路頻寬之使用,並結合SVG相較於點陣圖的諸多優點,讓碎形樹於網際網路呈現或教學上,更為迅速便利。
L-system is usually used in a computer graphic system to draw the natural landscape with regular patterns, like plants, cloud, mountain, sea images. L-system consists of regular rules and simple syntax with graphic meaning to generate realistic and complicate pictures.
This research is based on L-system to describe the Fractal Tree. First, we develop a rendering scheme to draw Fractal Trees in two dimensional plane and three dimensional space by SVG(Scalable Vector Graphics). In general, as the repetition count rises in the L-system grammar, the branch count of a Fractal Tree raises exponentially. As a result, geometric objects within the Fractal Tree also grow exponentially. Therefore, we propose several graphics object compression methods to decrease the number of geometric objects. Our methods include SVG source code optimization schemes (i.e., Line Merge, Segment Merge, Code Merge) and data compressing scheme using GZIP technology.
The effective compression ration of our prototype system is among 20% to 70%. This research has effectively compressed the SVG objects of the Fractal Tree, which enables users to view more complex Fractal Tree image with less storage and network bandwidth.
[1] 葉耀明、林芃君,”以可縮放式向量圖形語言呈現碎形圖形Fractal Rendering Using SVG”,國立臺灣師範大學資訊教育系,2003
[2]Mandelbrot B. B. , "How long is the coast of Britain? Statistical Self-Similarity and Fractional Dimension.". Sceience 155 , Page636-638, 1967
[3] 碎形幾何與碎形理論, “碎形Fractal”
<< http://alumni.nctu.edu.tw/~sinner/complex/fractals/index.html>>
[4] Yao-Ming Yeh, Kuan-Sheng Lee. A XML-based Plant Modeling Language. Cvgip2001
[5] P. Prusinkiewicz and A. Lindenmayer. Rewriting D0L-system. The Algorithmic Beauty of Plants, Pages 3-6, Springer-Verlag, New York, 1990.
[6] Peter Linz. A Hierarchy of formal Languages and Automata. An Introduction to Formal Language and Automata, Pages 287-310, D. C. Health and Company, 1990.
[7] Prusinkiewicz, P., James, M., and Mech, R.. Synthetic Topiary, SIGGRAPH 94 Conference Proceedings, Annual Conference Series. ACM SIGGRAPH, Addison Wesley, August 1994.
[8] R. Mech and P. Prusinkiewicz, “Visual models of plants interacting with their environment”. Proceedings of SIGGRAPH’96, Pages 397-410, 1996.
[9] H. Abelson and A. A. diSessa. Turtle geometry. M.I.T. Press, Cambridge,, 1982.
[10] XML 台灣資訊網, “SVG簡介”.
<<http://www.xml.org.tw/Function/Fglossary1.asp?key=SVG>>
[11] W3C Candidate Recommendation, " Scalable Vector Graphics (SVG) 1.1 Specification" HTTP DOC, January 2003.
<<http://www.w3.org/TR/2003/REC-SVG11-20030114/index.html>>
[12] Micah Laaker. "Sams Teach Yourself SVG in 24 Hours", Page 8-13, Sams, 2002.
[13] The gzip home page, "Introduction".
<<http://www.gzip.org>>
[14]Batik SVG Toolkit, "Batik Overview".
<<http://xml.apache.org/batik/index.html>>
[15] Hung-Wen Chen,“L-system plant geometry generator”, HTTP DOC, January 1995.
<<http://www.tc.cornell.edu/Visualization/contrib/cs490-94to95/hwchen/>>
[16] Radomir Mech and Przemyslaw Prusinkiewicz,“Visual models of plants interacting with their environment”, In Proceedings of SIGGRAPH’96, Pages 397-410, 1996.
[17] Michael T. Wong, Douglas E. Zongker, and David H. Salesin,“Computer-Generated Floral Ornament”, In Proceedings of SIGGRAPH’98, Pages 423-434, 1998
[18] John Kacher,“Interaction of multiple L-systems”, HTTP DOC, Presented at NCUR 98 in Salisbury, Maryland, 1998. <<http://www.owlnet.rice.edu/~jkacher/lsys98.html?>>
[19] 葉耀明、簡嘉齡,” 語言式圖形表示法之研究Research on Language-Based Graphic Representations”,國立臺灣師範大學資訊教育系,1999