0 引言

　　隨著圖像處理技術和激光掃描技術的發展，三維曲面重建技術作為一個重要研究內容廣泛應用于逆向工程、模式識別、影視等領域中，并得到快速發展。三維曲面重建是采用三維點云數據快速、準確地構建出復雜的曲面模型。現有的重建算法主要分為兩類：容積重建和表面重建[1]。容積重建在密集計算上耗費時間較長，不能夠滿足實時處理的需要。表面重建處理速度比較快，適合實時處理，主要包括輪廓線連接、等值面提取和Delaunay三角化。輪廓線連接是把相鄰的橫截面輪廓點連接起來，構建成一個三角網格，但在網格對應、拼接等問題上沒有解決好。等值面提取[1]是取當前點的8個鄰近點形成一個虛擬的多維數據集，確定一個多邊形來代表等值面表面，但等值面涉及到復雜的法向一致性調整，相當耗時。Delaunay三角化(如Power Crust算法[2-4]、Crust算法)是構造一個四面體網格，網格片之間的輪廓點為頂點，重建的不足在于容易遺漏一些輪廓點，導致重建的準確性降低。

　　針對以上問題，本文提出了一種基于Power Crust的三維點云曲面重建算法，對三維點云數據進行濾波、去噪等預處理，調用Power Crust算法進行曲面重建，利用VTK的pipeline機制對曲面網格進行簡化、平滑等處理，通過局部形狀校正獲得三維模型，顯示并交互。實驗結果表明，此算法運行速度快，重建曲面較為準確、光滑，圖像質量高，適合實時處理。

　　1 三維可視化類庫VTK

　　VTK[5-7]是美國Kitware公司利用C++語言開發的一套集3D圖形學、圖像處理和可視化于一體的C++類庫。它是一個源碼開發、可視化技術和圖像處理軟件系統，可在C++、Tcl/Tk、Jave、Pyhon語言環境下使用[8]。它融合了計算機圖形學、圖像處理和可視化三大技術，在可視化和圖像處理方面有著絕對的優勢，成為世界上研究圖像可視化系統的熱門工具。

　　構成VTK體系主要有2種對象模型：圖形模型對象和可視化模型對象。圖形模型的主要作用是用圖形描述幾何體構成的場景；可視化模型的主要作用是把幾何數據轉換成圖形數據和負責構建幾何體。VTK有著一套3D交互部件，采用流水線機制，支持并行處理，選擇適當的算法并構建自己的可視化流程，讀取數據、過濾、映射與渲染，最后將所成圖像呈現在屏幕上，并能實現人機交互。

　　2 重建算法簡介

　　準確性和效率性是三維點云曲面重建和可視化的兩個關鍵因素。準確性要求保持拓撲結構和形狀良好；效率性要求在保持原始拓撲結構的前提下降低重建時間。Power Crust算法在考慮采樣的密度和表面細節基礎上，采用一個貪婪的濾波過程來處理那些有噪聲的散亂數據，逆向重建了曲面的三角網格，并有理論上的支持。

　　2.1 Power Crust算法原理

　　Power Crust 算法原理涉及的概念主要有：中心軸變換[9]、Voronoi 圖、Delaunay三角化和Power圖[10-11]。

　　中軸很好地表現了物體形狀的特征及連接特性，對基于Voronoi的曲面重建算法有重要的意義,不僅是因為要利用它來定義采樣密度,而且位于中軸上的點到表面采樣點的向量構成了對該點表面法向量的一個很好的估計和預測。其誤差與采樣密度相關，很多基于Voronoi的算法都要利用該點來過濾三角片。

　　Voronoi圖在解決點與其他幾何對象的距離關系上作用很大。假設在給定平面或空間中，有n個散亂點，點集為P={p1，p2，…，pn}，定義：

　　其中，H(pi，pj)表示點集中的其他點到pi的距離比到pj的距離更近的軌跡，是一個半平面或者一個半空間；d(p，pi)表示p到pi的歐氏距離；V(pi)為點集中的其他點pj到點pi軌跡的總和。對于點集P中的每個點都有一個對應的Voronoi多邊形，所有的多邊形總和就稱為點集P的Voronoi圖。

　　Delaunay三角化和Voronoi圖是對偶關系，具有最小角最大、空洞與局部重連等特性。Power圖是Voronoi圖的擴展，可視為生成元是Power圓的Voronoi圖，只是其距離已不是歐氏距離而是Power距離：

　　已知d維空間的點集S，p∈S的權為wp(-∞<wp<+∞)，有：

　　其中，?仔p(x)稱為x到p的Power距離。

　　Power圖和其對偶的規則三角剖分是對應于加權點的Voronoi圖和Delaunay三角剖分。

　　可以證明,從極點到表面采樣點的向量是該采樣點表面法向量的一個很好的近似。這個結論將為中軸的計算和基于Voronoi的曲面重建算法提供強有力的理論支持。

　　2.2 Power Crust算法實現

　　Power Crust算法先計算出采樣點的中心軸，找出Voronoi頂點從而創建Voronoi圖，然后進行Delaunay三角化，把經過三角剖分的原始點云連接成三角網格模型，經過Voronoi圖過濾器過濾后，刪除不符合要求的網格，最后得到所需要的網格。此算法可以生成一個不漏水的、密封的三維網格，同時還得到原始表面中軸的估計量，能進行含有噪聲、有尖角、非封閉的點云數據的曲面重建。Power Crust算法的優勢是在細節區域，輸出的離散表面具有致密的點；在其他區域，輸出的離散表面只有稀疏的點。 具體步驟如下：

　　(1)對采樣點集S進行Delaunay 三角化，找到 Voronoi頂點，邊界框上的頂點被認為是Power圖上的采樣點。

　　(2)確定哪些Voronoi頂點為極點。

　　(3)生成極點球集合Bp，計算出Power圖。

　　(4)標記出每個極點是里面的或是外面的。

　　(5)給出三角化作為輸出，并返回結果。

　　2.3 網格簡化、平滑

　　經過Power Crust算法重建得到的曲面網格由很多多邊形數據(主要是三角片)構成，通常包含噪聲或者光潔度太差，繪制圖形的質量較差，且不能夠快速地繪制和處理，而交互的應用程序對于多邊形數據的快速繪制有更高的要求。為了減少渲染時間和提高重建效率，本文在重建網格的基礎上采用Decimation技術實現網格簡化；使用平滑網格技術，通過調整點的位置來降低輪廓面的鋸齒效應和分級效應，改善圖形的質量。

　　VTK支持4種Decimation對象：vtkDecimate、vtkDecimatePro、vtkQuadricClustering、vtkQuardricDecimation。vtkDe-

　　cimatePro執行速度相對較快，并且在削減過程中能夠修改拓撲結構，使用邊折疊處理消除頂點和三角形，其錯誤度量方法使用基于到平面或邊的距離方法，能夠實現被要求的任意削減程度。在vtkDecimatePro中，有兩個重要的變量：TargetReduction是被要求減少的三角形的數量；PreserveTopology被設置為是否允許改變拓撲結構。

　　VTK提供兩種平滑過濾器：vtkSmoothPolyDataFilter、vtkWindowedSincPolyDataFilter。vtkSmoothPolyDataFilter的平滑效果好、平滑速度較快。在vtkSmoothPolyDataFilter過濾器中，重要的變量是SetNumberOfIterations，即設置平滑迭代次數。

3 算法實現

　　VTK是可視化對象的集合，這些可視化對象可以連接起來形成一個可視化管道。這個管道開始輸入數據源，經過一系列的濾波器過濾，最后顯示出來[1]。

　　3.1 點云數據集

　　實驗使用的數據來源于對現實動物貓的三維掃描，通過激光掃描儀掃描到的數據以三維坐標的形式存儲在Txt文本中。Txt文本存儲的點云數據是一個多行3列的矩陣，每行記錄數據點的x、y、z 3個坐標值，保證數據的正確性；在保證完整性的基礎上進行數據精簡，提高運算速率。

　　3.2 實驗過程

　　在Microsoft Visual C++平臺中，對三維點云進行曲面重建和可視化，主要經過下面5個步驟：

　　(1)點云預處理。對三維點云數據進行去噪與濾波處理，由vtkPolyData和vtkPoint等VTK函數讀入VTK的pipeline流水線中。

　　(2)調用Power Crust算法對點云進行曲面重建。對VTK流水線機制讀入的點云數據，調用Power Crust算法進行頂點聚類、Delaunay三角化特性檢測、三角化，得到初步的曲面網格。

　　(3)簡化、平滑曲面網格。對重建后得到的網格，調用vtkDecimatePro、vtkSmoothPolyDataFilter等VTK函數進行簡化和平滑處理，減少網格數量，縮短渲染時間和提高運算效率。

　　(4)渲染、繪制點云曲面。經過簡化、平滑后的曲面網格，經過平面法向量估計、數據映射，建立演員類等處理，在VTK流水線機制上進行渲染、繪制。

　　(5)顯示、交互。對得到的點云曲面圖，在VTK中進行顯示，并實現交互操作。整個三維點云曲面重建的框圖如圖1所示。

4 實驗結果及分析

　　為了證明算法的有效性，選用兔子、貓、馬3組三維點云數據來進行測試。圖2(a)、(b)、(c)分別是兔子、貓、馬三維點云顯示圖，圖3(a)、(b)、(c)分別是兔子、貓、馬三維點云數據調用Power Crust算法得到的重建效果圖，圖4(a)、(b)、(c)分別是兔子、貓、馬三維點云調用本文算法得到的重建效果圖。表1總結了兩種方法對3組數據的重建結果。

　　通過以上幾種點云數據重建曲面可以看出，使用Power Crust算法曲面重建效果比較粗糙，并帶有很多突出和凹陷面;采用本文算法后的點云數據重建效果圖表面平滑光順，效果逼真，繪制速度快、效果好，能夠很好地反映三維點云的立體效果，并能保留物體原有的一些細節，對比結果很明顯。因此說明，把基于Voronoi 圖和Delaunay三角化的Power Crust算法和VTK可視化類庫結合起來是一個提高曲面重建效率的有效方法。

5 結語

　　本文分析了現有的曲面重建技術，在效率較高的基于Voronoi圖和Delaunay三角剖分的Power Crust算法基礎上，結合具有強大圖形處理能力的可視化類庫VTK，實現了三維點云曲面重建，并達到實時交互性能。Power Crust算法具有流程簡單、重建結果精確等優點，對于沒有法向量的大量散亂點云數據，處理速度非常快，但效果不是很準確。所以將經過去噪、濾波后的點云數據集，調用Power Crust算法進行曲面重建，輸入具有強大圖像處理能力的VTK進行簡化、平滑處理，最終得到的重建結果比較逼真，魯棒性強。這一方法有效提高了重建和可視化的效率，可以很方便地應用在各個需要獲取物體近似表面模型的領域，具有很大的現實意義。相信在不久的將來，隨著計算機技術的發展以及圖像處理技術的深入研究，三維點云曲面重建將會擁有廣泛的應用空間。

參考文獻

　　[1] LI J，HUANG S，LI G，et al.Reconstruction and visualiza-tion of 3D surface model from serial-sectioned contourpoints[C].Image and Signal Processing(CISP)，2010 3rdInternational Congress on.IEEE，2010，5：2396-2400.

    [2] AMENTA N，CHOI S，KOLLURI R K.The power crust，unions of balls，and the medial axis transform[J].Computa-tional Geometry，2001，19(2)：127-153.

　　[3] NI T，MA Z.A fast surface reconstruction algorithm for 3Dunorganized points[C].2010 2nd International Conference on

　　Computer Engineering and Technology，2010，7：15-18.

　　[4] LI H，MA X，LI J，et al.Research on model correction basedon scattered point cloud data surface reconstruction[C].Wireless Mobile and Computing(CCWMC 2011)，IET Inter-national Communication Conference on.IET，2011：97-101.

　　[5] WILLIAM J，SCHROEDER，LISA S，et al.The visualizationtoolkit user′s guide：updated for version 4.0[M].Kitware，

　　1998.

　　[6] 呂曉琪，李許峰，賈東征.基于可視化工具VTK的幾何體構建技術[J].內蒙古科技大學學報，2012，31(2)：167-170.

　　[7] 肖何，何明耘，白忠建，等.基于VTK的電磁場三維可視化研究及實現[J].計算機應用，2008，27(11)：2773-2775.

　　[8] 劉偉寧.基于VTK的海底聲納數據實時三維建模軟件設計[D].杭州：浙江大學，2010.

　　[9] AGANJ E，KERIVEN R，PONS J P.Photo-consistent sur-face reconstruction from noisy point clouds[C].Image Pro-cessing(ICIP)，2009 16th IEEE International Conference on，

　　IEEE，2009：505-508.

　　[10] 李云.不規則形體點云的三維重建研究[D].烏魯木齊：新疆大學, 2013：22-32.

　　[11] 李海生.Delaunay三角剖分理論及可視化應用研究[M].哈爾濱：哈爾濱工業大學出版社，2010：12-22.