qrst

國家圖書館索書號: 312.93 037M 82-1 系統編號: 81CYCU0392002 
　　　　　研究生: 郭宏春 Kuo, Horng Chuen 
 (以研究生姓名查詢國家圖書館索書號 ，未查獲者表國圖尚未典藏) 
 (以研究生姓名查詢國科會科資中心微片資料庫) 
 (連結至全國圖書聯合目錄)　 (連結至政大圖書館館藏目錄) 
　　　　論文名稱: 由邊視投影重建物體之演算法 
　　　　論文名稱: Reconstruction Algorithms by Using Edge View Projections 
　　　　指導教授: 鍾斌賢 Jong, Bin Shyan 
　　　　學位類別: 碩士 
　　　　校院名稱: 中原大學 
　　　　系所名稱: 資訊工程研究所 
　　　　　　學號: 8077002 
　　　　　學年度: 81 
　　　　　語文別: 中文 
　　　　論文頁數: 88 
　　　　　關鍵字: 線性八元樹;邊視投影;掃掠;機 Linear Octree;Edge View  
 動邊界;可見面的決定 Projection;Sweep;Active  
  Border;Visible Surface  
  Determination 
[摘要] 
三度空間物體之表示結構及處理在計算機圖學、圖形識別、醫學影像以及 
機器人學領域中是非常重要的。階層樹狀結構中之四元樹和八元樹提供簡 
潔資料結構及快速之資料讀取功能，是一個有效率的儲存物體方法。線性 
四元樹及線性八元樹儲存排序串列之物體碼，則為一種缺乏指標之階層樹 
狀結構。在本論文中，我們將介紹一個新的演算法從邊視投影來重建三度 
空間線性八元樹。除此之外，我們也提出一個三度空間線性八元樹顯像之 
改善演算法。一般而言，體積交集方法之基本原則是沿著觀看方向掃掠輪 
廓所得之體積來交集重建物體，如何找尋有效率的方法來建構物體之大約 
外形體積則是最主要的工作。根據邊視投影及機動邊界特性，我們走訪邊 
視投影之線性四元樹得到基本節點，而且使用一個雜湊表來儲存這些基本 
節點。然後我們走訪目標樹，並且利用雜湊表檢查節點的投影是否覆蓋某 
一輪廓的黑色節點來決定顏色。以如此方法，我們找出從邊視投影建構線 
性八元樹的線性時間演算法。線性八元樹之顯像與從投影重建八元樹是一 
相反問題。基本上而言，如何決定黑色節點的可見面、走訪節點的數目， 
投影描繪時間，將是決定顯像效率的主要因素。我們發展一新的演算法於 
線性八元樹上，根據所給定觀看方向的FTB 順序走訪線性八元樹，利用機 
動邊界使得我們能夠快速解決可見面的問題。同時我們也說明此演算法為 
一線性時間。 
The representation and manipulation of three dimensional 
objects are important topic in the fields of computer graphics, 
pattern recognition, medical imaging and robotics. Hierarchical 
data structures such as quadtree and octree are efficient ways 
to store the spatial information because they provide a compact 
data structure and allow rapid data access to occupancy 
informa- tion. The linear quadtree and linear octree are 
hierarchical pointerless representation which store object 
elements as sorted codes. In this thesis, we propose a new 
method to reconstruct the linear octree from its edge view 
projections. An improved algorithm for displaying linear octree 
is also presented. In generally, volume intersection is the 
underlying paradigm wherein the objects are reconstructed by 
intersecting the vol- umes generated by sweeping the silhouette 
along the respective view direction. On the basis of the 
property of edge view pro- jction and active border, we 
traverse the silhouette represented by linear quadtree to 
obtain base nodes and a hash table is de- vised to store these 
base nodes. Then we perform a tree traversal from target tree 
and determine if the projections of its nodes overlap any black 
nodes of the silhouette stored in the hash table, and colors 
they are appropriate. In such a way, we find a linear time 
algorithm for constructing linear octree from its edge view 
projections. Projecting octrees to display three dimensional 
objects is the converse problem of construction octrees from 
projection images. Basically, it determines the efficiency of 
displaying linear octree that how to find visible faces of 
black octant, number of nodes traversed and time spent to scan 
conversion. We propose an efficient algorithm based on 
traversing linear octrees in a front-to-back order determined 
by a given direc- tion, and the visible faces are decided by 
using active border. We also show that the algorithm is a 
linear time algorithm. 

 
[機讀格式] 輸出 ISO2709 機讀編目格式