查詢結果分析
來源資料
頁籤選單縮合
題 名 | 廣先走訪之線性四元樹暨其空間幾何運算元=A Linear Quadtree with Breadth-First Traversal and Related Geometric Operators |
---|---|
作 者 | 張克章; 鄭來龍; | 書刊名 | 技術學刊 |
卷 期 | 11:1 1996.03[民85.03] |
頁 次 | 頁129-138 |
分類號 | 312.13 |
關鍵詞 | 完整四元樹; 廣先搜尋; 終端節點; 節點串列; 色彩串列; Complete quadtree; Breadth-first traversal; Terminal node; Node list; Color list; |
語 文 | 中文(Chinese) |
中文摘要 | 本文提出一種新的線性四元樹編碼方法,運用在網格影像圖形資料節省儲存空間的問題上,可將編碼時間維持在與圖形解析度成線性關係之條件內,並使儲存空間資料所需要的記憶體空間降低,達到改進以往研究的成果。此外,本文所提編碼之結果,亦可直接進行各種空間資料的運算,以獲得空間資料快速運算的效果。本文所提編碼方法係建立於完整四元樹階層關係的基本觀念,並採行廣先搜尋走訪、摩頓序列及利用節點串列與色彩串列兩種資料結構推導而成。其中,節點串列使每一個表示四元樹分支狀況之內部節點,維持使用一個位元表示;終端節點所表示之空間資料則記錄在色彩串列之中;同時,可隨空間資料種額之增加而改變其表示之位元數,而不需重新建立四元樹,因此對於在壓縮碼上亦可直接進行增加多元資料或執行疊圖等運算。且因本編碼法的結構特性,同樣地適於推廣至多維空間資料上之處理。為驗証與測試本文所提之方法,本文以兩張空間圖形資料進行實證比較,實證結果顯示本文所提方法之可行性與優點。 |
英文摘要 | A new coding scheme for linear quadtrees with several geographical operations are proposed in this paper. There are two objectives in this paper. The first objective is to find a coding scheme with which the requirement of large storage for recording spatial data in GIS or image processing can be improved from the past researches. The second objective is to verify the feasibility of the proposed coding scheme for spatial data processing. The proposed linear quadtree coding scheme is developed on the basis of the hierarchical structure of a complete quadtree. Techniques of breadthfirst traversal, Morton sequence with two data structures of node list and color list are used to develop the proposed coding scheme. The node list maintains the outputs of quadtree decompositions, and uses only one bit to record data; All terminal nodes, representing different spatial data, in the quadtree are recorded in the color list. The application of the color list has an advantage that the number of bits required to represent various number of objects are extendible, so that the requirement of the construction of new quadtrees is no longer necessary. The feasibility of the proposed linear quadtree coding scheme is verified by two raster images of spatial data. Results of experimental tests reveal that the proposed scheme has the least storage requirement among various coding schemes. Several geometric operations are also implemented to demonstrate the applicability of the proposed coding scheme for geographical data processing. Due to the characteristic of the proposed coding scheme, the problem of multicolor quadtrees is also solvable by the method proposed in this paper. |
本系統中英文摘要資訊取自各篇刊載內容。