基于三維重建技術的三角剖分*

谷利國，侯振杰

（內蒙古農業大學 計算機與信息工程學院,內蒙古 呼和浩特010018）

在計算機視覺中,三維重建是指由多幅二維圖像恢復物體三維可見表面幾何形狀的方法（物體的空間位置信息）。三維重建直接模擬人類雙眼處理景物的方式，具有簡單、可靠、靈活、使用范圍廣等特點，可以進行非接觸、自動、在線檢測等。

從某種角度上說，三維重建的最終目的是可視，就是把被重建的物體真實地顯示出來。由三維重建算法得到的是一組三維點集，并不能求得整個物體表面的細節，因此需要對這些散亂的三維點進行三角剖分，用許多小三角形組成的表面來近似物體表面，這樣就相當于給散亂的三維點集搭起一個立體的網狀骨架模型。經過三角剖分之后，所有三角形的平面片在空間撐出了物體的三維模型。這時只需要將物體的紋理從圖像中取出，并映射至三維模型上就可以提供物體的真實三維模型。

三角剖分是虛擬現實、計算機視覺等領域的一個研究熱點。目前針對三角化的研究主要有：BOLL和VEMURI[1]、BRINKLEY和 SCHMITT等采用參數表示法，將三維數據映射到二維參數域上,在二維進行曲面重構,然后將結果映射回三維空間；BOWYER和 WATSON[2]采用Delaunay三角剖分法,將二維的Delaunay三角剖分推廣到三維進行網絡重構。BERNARIDINI的 BPA算法[3]通過種子三角形不斷向周圍擴展，從而構成最終的三角形網格等。

目前,對于平面區域的散亂點集三角剖分已經取得了一定的成果，但很多算法推廣至三維空間仍存在一些問題，在算法的時間效率上也有待進一步提高，因此對于三維空間散亂點集的三角剖分有待進一步的發展。

本文提出了一種利用增量法與分治法相結合的算法，直接對空間散亂點進行三角剖分，降低算法的時間復雜度，并通過編程證明了該算法的可行性。

1 三角剖分算法的基礎理論

三角剖分中以Delaunay三角剖分最具有代表性，它是優化的三角剖分。Delaunay三角剖分的概念是1934年由俄國數學家Delaunay提出的。

三角剖分所具備的優異特性主要有以下幾個方面：

(1)最接近：以最臨近的三點形成三角形，且各線段(三角形的邊)皆不相交；

(2)唯一性：不論從區域何處開始構建，最終都將得到一致的結果；

(3)最優性：任意兩個相鄰三角形形成的凸四邊形的對角線如果可以互換的話，那么兩個三角形6個內角中最小的角度不會變大；

(4)最規則：如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay三角網的排列得到的數值最大；

(5)區域性：新增、刪除、移動某一個頂點時只會影響臨近的三角形；

(6)具有凸多邊形的外殼：三角網最外層的邊界形成一個凸多邊形的外殼。

關于Delaunay三角剖分主要有三類:增量算法(逐點插入法)、分治法(分割歸并算法)和三角網生長算法。三角網生長法在20世紀80年代中期以后就很少用到,較常見的是分治算法和逐點插入法。

增量算法的思想：先構造一個包含所有點集的大三角形，然后逐點在三角形內插入點，插入的過程不斷用Delaunay三角優化準則去檢查和調整，直到所有點插入完整，算法結束。

逐點插入法有不同的實現方法，區別在于初始多邊形的不同和初始三角剖分的方法不同。較有代表性的是Lawson算法[4]以及 Lee和 Schacher算法[5]。

分治算法的思想：所謂的分治法，其實就是分而治之。首先把要處理的點集分成幾個相等的子點集，按Delaunay三角優化準則對各子點集進行三角剖分，然后把各個子集的相鄰三角形邊界進行合并，最后對合并時在子集邊界處新生成的三角形進行優化。

分治法也有不同的實現方法,其不同之處在于使用不同的子集劃分方法、子集中三角剖分方法或者各子集邊界的合并方法，比較經典的算法是Lee和Schacher算法[5]、Dwyer 算法[6]。

2 改進的三角剖分算法

2.1 復雜度及優缺點分析

增量算法簡單直觀，占用內存小，魯棒性好，容易實現，但時間復雜度差,最壞情況為O(n2)。當處理的散亂點數量增長時，處理的時間也指數地增長，故降低其時間復雜度顯得相當重要。

分治算法時間復雜度方面較好，其最壞情況為O(lgn)，但由于遞歸執行，需要較大的內存空間，對于大規模的散亂點的處理要求大量的內存空間。

兩種算法各有自己的優點和缺點，增量算法時間效率差，節省內存空間;而分治法時間效率好，但需要大量內存。

改進的算法思想是把分治算法與增量法結相結合，以分治算法為主體,增量法為輔：當遞歸分割數據點集的過程進行到子點集中的數據量小于一個預定值——分割閾值時終止,然后用增量法在子集中生成子三角網。這一新的算法稱為合成算法。

2.2 算法的改進

2.2.1 分治法中的改進

分治法中采用一對八式的八叉樹數據模型來完成分割與合并。

首先利用八叉樹模型對空間離散點進行分割，然后對八叉樹葉子節點進行Delaunay三角化，最后依據Delaunay法則將各局部三角網自下而上逐級合并，進而生成最終的整個點集三角網模型,這樣將兩種三角化適當結合，提高了算法的效率。

其中，在合并的過程中盡量減少了查找正確擴展點的范圍，從而節約了時間，提高了算法的執行效率。

具體作法：將各節點生成三角網凸殼的擴展邊（邊界）找出，用鏈表分別存儲，兩兩合并三角網時所需用到的邊和點就可直接取自這兩條鏈表中的數據，而無需在該區域中所有點中逐一比較尋找了，從而避免了很多無用功。

用八叉樹來表示三維形體，既可以看成是四叉樹方法在三維空間的推廣，也可以認為是用三維體素陣列表示形體方法的一種改進,如圖1所示。

八叉樹有三種不同的存儲結構，分別是規則方式、線性方式以及一對八方式。相應的八叉樹也分別稱為規則八叉樹、線性八叉樹以及一對八式八叉樹。不同的存儲結構的空間利用率及運算操作的方便性是不同的。分析表明，一對八式八叉樹優點更多一些。

(1)規則八叉樹

規則八叉樹缺陷較多，最大的問題是指針占用了大量的空間。假定每個指針要用2 B表示，而節點的描述用1 B,則存放指針要占總存儲量的94%。因此，這種方法雖然十分自然，容易掌握，但在存儲空間的使用率方面不是很理想。

(2)線性八叉樹

線性八叉樹不僅節省存儲空間，對某些運算也較為方便,但是為此付出的代價是喪失了一定的靈活性。

(3)一對八式的八叉樹

一個非葉節點有8個子節點，為了確定起見，將它們分別標記為 0、1、2、3、4、5、6、7。綜上所述，如果一個記錄與一個節點相對應，那么在這個記錄中描述的是這個結點的8個子節點的特性值。而指針給出的則是該8個子節點所對應記錄的存放處，而且還隱含地假定了這些子結點記錄存放的次序。也就是說，即使某個記錄是不必要的(例如該節點已是葉節點)，則相應的存儲位置也必須空閑在那里，以保證不會錯誤地存取到其他同輩節點的記錄。這樣當然會有一定的浪費，除非它是完全的八叉樹，即所有的葉節點均在同一層次出現，而在該層次之上的所有層中的節點均為非葉節點。

綜上優缺分析后，文中選擇了一對八式的八叉樹數據模型。

2.2.2 Delaunay增量算法的改進

Delaunay增量算法的思想是逐點插入,每次插入一個散亂點，經處理形成若干新的四面體;但隨著插入點的增加，所生成的四面體便成倍地增長，而計算量也大大增加。

如何縮短算法中各個環節的計算時間成為提高整個算法效率的關鍵。這些關鍵問題涉及散亂點的加入方式、搜索方法等。

本文在搜索四面的外接圓時使用了指南針算法，提高了算法的搜索效率。

2.3 可行性分析

(1)采用八叉樹分割，并用遞歸的思想，當數據量大的時候，調用的程序運行效率比較低。在本程序的實現中，將遞歸調用轉化為迭代，從而提高算法效率[7,8]。

(2)文中在增量算法中嵌入了指南針算法搜尋四面體外接球體，以加快算法的搜尋速度。

(3)在合并的過程中盡量縮小查找正確擴展點的范圍,提高了算法的執行效率。

3 實驗

本文的實驗環境：CPU為Pentium(R)Dual-Core 2.5GHz，內存1 GB，顯卡為集成顯卡，操作系統為 Window XP，仿真平臺為Matlab 7.0。

(1)選取通過三維掃描儀得到的點云圖，分別利用Matlab中的Delaunay（）函數剖分和改進的三角剖分算法對點云圖進行剖分，在點數變化時，對兩種算法所剖分出四面的數量和所用時間進行比較,結果如表1所示。

(2)選取通過三維掃描儀得到的一條圍巾的點云圖，分別利用 Matlab中 Delaunay()函數、Delaunayn()剖分和改進的三角剖分算法對點云圖進行剖分。通過三維掃描儀掃描圍巾得到點云,如圖2所示，使用原算法和改進算法對圍巾點云圖進行三角剖分，結果如圖3和圖4所示。

對圖3和圖4中的1號與2號區域放大,比較效果分別如圖 5、圖 6、圖 7、圖 8所示。

使用兩種算法對圍巾點云剖分在剖分出四面的數量和所用時間方面進行比較,結果如表2所示。

表1 對三維掃描儀得到的三維點進行三角剖分

通過對不同數量的空間散亂點的三角剖分，利用Matlab內置的Delauany()函數與改進的三角剖分算法對空間散亂點集進行三角剖分，對剖分出四面體的數量和所用時間進行比較，改進的算法在剖分出的四面體數量和時間效率上有明顯的優勢。而且由以上圖的比較可以看出，對于重建出的模型效果，改進后的算法明顯優于前者。

表2 算法效率分析

本文算法通過使用分治法和增量法的合成算法，在分治法中使用八叉樹數據模型，使遞歸問題轉化為迭代問題，提高了算法的執行效率；在增量法中嵌入指南針算法，提高了搜索效率。使用合成算法在空間的三角剖分方面有很大的優勢。此外分析了算法中的不足之處，并提出有待進一步研究的問題，為后續的展望工作打下基礎。

[1]BOLLE R M,VEMURI B C.On three-dimensional surface reconstruction methods.IEEE Trans.Pat.Anal.Mach.Intell,1985,7(4):431-441.

[2]WATSON D F.Computing the N-dimensional delaunay tessellation with application to voronoi polytopes.The Computer Journal,1981,24(2):167-172.

[3]BERARIDINI F,MITTLEMAN J,SILVA C,et al.The ball-pivoting algorithm for surface reconstruction.IEEE Trans.Virsualization Comput.Graphics,1999(4):43-72.

[4]LAWSON G L.Generation of a triangular grid with application to contour plotting[C].In:Teehnical Memorandum.Institute of Technology,Jet Pollution Laboratory,California,1972:294-299.

[5]LEE D T,SCHACHER B J.Two algorithms for eonstrueting a delaunay triangulation[J].International Journal of Computer and Information Seienees,1980(9):219-242.

[6]DWYER R A.A faster divide-and-conquer algorithm fore constructing Delaunay triangulations[J].Algorithmica,1987(2):137-151.

[7]朱站立，劉天時.數據結構（第二版）[M].西安：西安交通大學出版社，1999.

[8]PIEGL L A,RICHARD A M.Algorithm and data structure for triangulating multiply connected polyonal domains[J].Computers&Graphics,1993,14(16);23-35.