碎形樹在可縮放式向量繪圖壓縮技術之探討

Study of SVG Compression on Fractal Tree Rendering

陳慶全(Ching-Chuan Chen)

指導教授 ： 葉耀明

國立臺灣師範大學/教育學院/資訊教育學系/碩士(2004年)

摘要

許多電腦圖形系統在繪製有規律特性的自然影像時，例如樹木、雲朵、山脈、海洋等，採用Lindenmayer系統（簡稱為L-system）的理論，其使用單純、含有圖形意義的符號及具規律性質的規則，來衍生出逼真且複雜的碎形圖形。
本研究以L-system為描述碎形樹的基礎語言，先探討如何以SVG（Scalable Vector Graphics）在2D及3D碎形樹的呈現。一般圖形語言在呈現碎形樹時，隨著L-system語言中遞迴數增長，所需繪製的樹枝圖形物件呈指數成長，本研究探討如何有效降低龐大的圖形物件數，並提出幾種壓縮策略，來分析各種策略對哪幾類碎形樹的適用性，以及壓縮效果於檔案容量及記憶體使用量的分析。
本研究發展的壓縮演算法，依照不同類型的碎形樹，可透過此壓縮演算法，達到壓縮物件數量為原始物件數的70％至20％，讓使用者可以觀看更複雜的碎形樹之時，同時減低系統記憶體的使用量及降低網際網路頻寬之使用，並結合SVG相較於點陣圖的諸多優點，讓碎形樹於網際網路呈現或教學上，更為迅速便利。

關鍵字

碎形、、 ； 樹 ； 壓縮 ； HASH(0x8e65e80) ； HASH(0x8e65ef8) ； HASH(0x8e65f70)

並列摘要

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.

並列關鍵字

XML ； SVG ； L-system ； Fractal ； Tree ； Compression

參考文獻

[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

[8] R. Mech and P. Prusinkiewicz, “Visual models of plants interacting with their environment”. Proceedings of SIGGRAPH’96, Pages 397-410, 1996.

[11] W3C Candidate Recommendation, " Scalable Vector Graphics (SVG) 1.1 Specification" HTTP DOC, January 2003.

[12] Micah Laaker. "Sams Teach Yourself SVG in 24 Hours", Page 8-13, Sams, 2002.