簡易檢索 / 詳目顯示

回結果列表
研究生： 陳慶全
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
論文種類： 學術論文
相關次數： 點閱：305  下載：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.

    附表目錄 iii 附圖目錄 vi 第一章 緒論 1 第一節 研究背景 1 第二節 研究目的 3 第三節 論文架構 3 第二章 碎形樹與SVG 4 第一節 碎形理論 4 2.1.1 碎形的特性 5 2.1.2 典型碎形 6 第二節 林登梅爾系統 8 2.2.1. 林登梅爾系統的基本概念 8 2.2.2. L-System的一般型態 9 2.2.3. D0L-system的定義及視覺化 12 第三節 可縮放式向量圖形語言 14 2.3.1. 概念與呈現 15 2.3.2. 基本物件 19 2.3.3. SVG的優點 21 2.3.4. SVG與Flash比較 23 第四節 GZIP檔案壓縮格式 26 第三章 碎形樹向量呈現方法 27 第一節 二維碎形樹以SVG呈現探討 27 第二節 三維碎形樹以SVG呈現探討 35 第三節 碎形樹擬真化探討 40 3.3.1. 隨機生長 40 3.3.2. 樹枝粗細變化及樹葉 42 3.3.3. 植物向光性 43 3.3.4. 生長法則 46 第四章 碎形樹之向量壓縮演算法 49 第一節 線段合併（Line Merge） 49 第二節 區段合併（Segment Merge） 59 第三節 原始碼合併（Code Merge） 62 第四節 檔案壓縮技術採用GZIP 64 第五章 壓縮效果分析 65 第一節 SVG物件數分析 65 5.1.1.二維碎形樹 65 5.1.2.三維碎形樹 72 第三節 記憶體使用量分析 83 第四節 隨機碎形樹分析 86 第六章 結論 88 第一節 結論 88 第二節 未來發展方向 90 參考文獻 91 附錄 93 附表目錄 【表2-1】Flash與SVG在一致性及延伸性的比較 24 【表2-2】Flash與SVG在plug-in方面的比較 25 【表3-1】海龜式繪圖法符號表 28 【表3-2】L-system的基本樹型之規則、結果字串與圖形 28 【表3-3】L-system基本樹型與SVG原始碼對照表 29 【表3-4】二維碎形樹繪製演算法 34 【表3-5】3D空間座標軸旋轉符號表 36 【表3-6】三維碎形樹繪製演算法 39 【表4-1】Line Merge Algorithm 57 【表4-2】Segment Merge Algorithm 61 【表4-3】Code Merge Algorithm 63 【表5-1】F[+F][-F]F Line Merge 分析 66 【表5-2】F[+F][-F]F Segment Merge 分析 67 【表5-3】F[+F][-F]F Code Merge 分析 67 【表5-4】F[+X]F[-X]+X Line Merge 分析 68 【表5-5】F[+X]F[-X]+X Segment Merge 分析 69 【表5-6】F[+X]F[-X]+X Code Merge 分析 69 【表5-7】FF[+++F-F][+F+F+F] Line Merge 分析 70 【表5-8】FF[+++F-F][+F+F+F] Segment Merge 分析 71 【表5-9】FF[+++F-F][+F+F+F] Code Merge 分析 71 【表5-10】二維碎形樹與壓縮方法效能對應表 72 【表5-11】F[+&F][+^F][-&F][-^F]F Line Merge 分析 74 【表5-12】F[+&F][+^F][-&F][-^F]F Segment Merge 分析 74 【表5-13】F[+&F][+^F][-&F][-^F]F Code Merge 分析 75 【表5-14】FF[^^^F+F][&&&F+F][+F+F+F] Line Merge 分析 76 【表5-15】FF[^^^F+F][&&&F+F][+F+F+F] Segment Merge 分析 76 【表5-16】FF[^^^F+F][&&&F+F][+F+F+F] Code Merge 分析 77 【表5-17】三維碎形樹與壓縮方法效能對應表 77 【表5-18】F[+F][-F]F Line Merge 檔案容量分析 78 【表5-19】F[+F][-F]F Segment Merge 檔案容量分析 79 【表5-20】F[+F][-F]F Code Merge 檔案容量分析 79 【表5-21】F[+X]F[-X]+X Line Merge 檔案容量分析 80 【表5-22】F[+X]F[-X]+X Segment Merge 檔案容量分析 80 【表5-23】F[+X]F[-X]+X Code Merge 檔案容量分析 81 【表5-24】FF[+++F-F][+F+F+F] Line Merge 檔案容量分析 81 【表5-25】FF[+++F-F][+F+F+F] Segment Merge 檔案容量分析 82 【表5-26】FF[+++F-F][+F+F+F] Code Merge 檔案容量分析 82 【表5-27】基本樹型F[+F][-F]F記憶體使用量分析 84 【表5-28】灌木樹型F[+X]F[-X]+X記憶體使用量分析 84 【表5-29】柳樹FF[+++F-F][+F+F+F] 記憶體使用量分析 85 【表5-30】基本樹型隨機生長Line Merge壓縮比率 86 【表5-31】基本樹型隨機生長Segment Merge壓縮比率 87 【表6-1】壓縮方法適用範圍表 89 【表6-2】碎形樹擬真化與壓縮方法適用性對應表 89 【附表-1】FF+[+F-F-F]-[-F+F+F]Line Merge分析 94 【附表-2】FF+[+F-F-F]-[-F+F+F] Segment Merge分析 94 【附表-3】FF+[+F-F-F]-[-F+F+F] Code Merge分析 94 【附表-4】F[+F]F[-F]F Line Merge分析 96 【附表-5】F[+F]F[-F]F Segment Merge分析 96 【附表-6】F[+F]F[-F]F Code Merge分析 96 【附表-7】F[+F]F[-F][F]Line Merge分析 98 【附表-8】F[+F]F[-F][F]Segment Merge分析 98 【附表-9】F[+F]F[-F][F] Code Merge分析 98 【附表-10】F[+X][-X]FX Line Merge分析 100 【附表-11】F[+X][-X]FX Segment Merge分析 100 【附表-12】F[+X][-X]FX Code Merge分析 100 【附表-13】F-[[X]+X]+F[+FX]-X Line Merge分析 102 【附表-14】F-[[X]+X]+F[+FX]-X Segment Merge分析 102 【附表-15】F-[[X]+X]+F[+FX]-X Code Merge分析 102 附圖目錄 【圖2-1】Koch Snowflake圖形 6 【圖2-2】Sierpinski gasket圖形 7 【圖2-3】L-system範例 9 【圖2-4】遞迴一到三次的基本樹型 13 【圖2-5】SVG的基本形狀 20 【圖2-6】SVG的文字範例 21 【圖3-1】二維碎形樹轉換SVG格式流程 31 【圖3-2】二維碎形樹繪製初始狀態 32 【圖3-3】二維碎形樹可能分枝情況 33 【圖3-4】3D空間方位圖 36 【圖3-5】三維碎形樹轉換SVG格式流程 37 【圖3-6】二維基本樹型隨機生長呈現 41 【圖3-7】三維基本樹型隨機生長呈現 41 【圖3-8】分枝生長粗細變化與結果字串關係示意圖 42 【圖3-9】二維碎形樹樹枝粗細及樹葉繪製呈現 43 【圖3-10】三維碎形樹樹枝粗細繪製呈現 43 【圖3-11】樹木向光性生長示意圖 44 【圖3-12】基本樹型日照左右不均生長結果 45 【圖3-13】灌木樹日照左右不均生長結果 45 【圖3-14】分枝模型示意圖 46 【圖3-15】基本樹型依生長空間競爭圖 47 【圖4-1】FF[-F] 圖形 50 【圖4-2】FF[+&F]圖形 51 【圖4-3】F[+F][-F]F圖形 51 【圖4-4】F[+&F][+^F]F圖形 52 【圖4-5】F[+F]F[-F]F[+F]F圖形 53 【圖4-6】F[+&F]F[+^F]F圖形 54 【圖4-7】F[+F]FF[+F][-F]F[+F]F圖形 55 【圖4-8】F[+&F]FF[+&F] [+^F]F圖形 56 【圖4-9】F[---F][-F-F-F] 圖形 59 【圖4-10】F[--&F][--^F][-F-F-F] 圖形 61 【圖4-11】GZIP實作概念圖 64 【圖5-1】基本樹型F[+F][-F]F呈現圖 66 【圖5-2】灌木樹F[+X]F[-X]+X呈現圖 68 【圖5-3】柳樹FF[+++F-F][+F+F+F]呈現圖 70 【圖5-4】三維基本樹型F[+&F][+^F][-&F][-^F]F呈現圖 73 【圖5-5】三維柳樹FF[^^^F+F][&&&F+F][+F+F+F]呈現圖 75 【圖5-6】Batik SVG Browser 83 【附圖-1】FF+[+F-F-F]-[-F+F+F]呈現圖 93 【附圖-2】F[+F]F[-F]F呈現圖 95 【附圖-3】F[+F]F[-F][F]呈現圖 97 【附圖-4】F[+X][-X]FX呈現圖 99 【附圖-5】F-[[X]+X]+F[+FX]-X呈現圖 101

    [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

    QR CODE