臺灣博碩士論文加值系統

本研究主要的目的是要提出一種有效的線性編碼法，應用於二維圖形
的壓縮，並討論藉由多層平面影像於空間體積模型（Spatial Volumetric
Model）建構之研究。空間體積模型資料的表示法普遍被應用在電腦視覺
、電腦輔助設計與製造、機器人運動碰撞偵測模擬、圖形識別….等。空
間體積模型資料要求愈精密及完整，則所處理的資料量將愈龐大，對於資
料的計算、儲存、傳輸皆是沈重的負荷。 四元樹（Quadtree）及八元
樹（Octree）的階層式資料結構（Hierarchical data structure）表示
法，除了可達到資料的壓縮與加速運算的能力，同時我們也可以用這較少
的資料直接進行必要的運算。在傳統的四元樹或八元樹是透過指標來達成
的鏈結節點的目的，由於大量的指標耗損儲存空間，本論文採用一種新的
結構－線性四元樹（Linear Quadtree）及線性八元樹(Linear Octree)，
它是將階層式的資料結構儲存在線性陣列中（Linear array），不需要指
標來表示節點間的相關位置，其空間的儲存量皆較指標表示法還小，並且
可有效支援基本的幾何運算如布林運算、旋轉運算等。

This research introduces a efficient linear encoding appliced
for plan image,and presents the spatial volumetric model
construction according to multi-layer plane image. Spatial
volumetric model representation had been used in computer vision
、CAD/CAM、robot motion simulation、pattern recognition etc.
However, the more exact model representation we need, the more
data information will be handled. The more load for data store
and transfer can be expected. The use of hierarchical data
structure presentation of quadtree and octree can attain to the
compression of data and acceleration operation, and also can
imediacy boolean and geometric proceed operation.Tradtion
quadtree and octree tend to link nodes by pointers. Because of
loss store space by a great lot of pointers, this research uses
a new structure-linear quadtree and linaer octree. It stores
hierarchial data structure in linear array, and it doesn`t need
pointers to express relevant location. It need less than using
pointers and also can operate basic geometric operation, such as
boolean operation、rotation operation etc.