0 引言

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

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

　　1 三維可視化類庫VTK

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

　　構(gòu)成VTK體系主要有2種對象模型：圖形模型對象和可視化模型對象。圖形模型的主要作用是用圖形描述幾何體構(gòu)成的場景；可視化模型的主要作用是把幾何數(shù)據(jù)轉(zhuǎn)換成圖形數(shù)據(jù)和負(fù)責(zé)構(gòu)建幾何體。VTK有著一套3D交互部件，采用流水線機制，支持并行處理，選擇適當(dāng)?shù)乃惴ú?gòu)建自己的可視化流程，讀取數(shù)據(jù)、過濾、映射與渲染，最后將所成圖像呈現(xiàn)在屏幕上，并能實現(xiàn)人機交互。

　　2 重建算法簡介

　　準(zhǔn)確性和效率性是三維點云曲面重建和可視化的兩個關(guān)鍵因素。準(zhǔn)確性要求保持拓?fù)浣Y(jié)構(gòu)和形狀良好；效率性要求在保持原始拓?fù)浣Y(jié)構(gòu)的前提下降低重建時間。Power Crust算法在考慮采樣的密度和表面細(xì)節(jié)基礎(chǔ)上，采用一個貪婪的濾波過程來處理那些有噪聲的散亂數(shù)據(jù)，逆向重建了曲面的三角網(wǎng)格，并有理論上的支持。

　　2.1 Power Crust算法原理

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

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

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

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

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

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

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

　　Power圖和其對偶的規(guī)則三角剖分是對應(yīng)于加權(quán)點的Voronoi圖和Delaunay三角剖分。

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

　　2.2 Power Crust算法實現(xiàn)

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

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

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

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

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

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

　　2.3 網(wǎng)格簡化、平滑

　　經(jīng)過Power Crust算法重建得到的曲面網(wǎng)格由很多多邊形數(shù)據(jù)(主要是三角片)構(gòu)成，通常包含噪聲或者光潔度太差，繪制圖形的質(zhì)量較差，且不能夠快速地繪制和處理，而交互的應(yīng)用程序?qū)τ诙噙呅螖?shù)據(jù)的快速繪制有更高的要求。為了減少渲染時間和提高重建效率，本文在重建網(wǎng)格的基礎(chǔ)上采用Decimation技術(shù)實現(xiàn)網(wǎng)格簡化；使用平滑網(wǎng)格技術(shù)，通過調(diào)整點的位置來降低輪廓面的鋸齒效應(yīng)和分級效應(yīng)，改善圖形的質(zhì)量。

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

　　cimatePro執(zhí)行速度相對較快，并且在削減過程中能夠修改拓?fù)浣Y(jié)構(gòu)，使用邊折疊處理消除頂點和三角形，其錯誤度量方法使用基于到平面或邊的距離方法，能夠?qū)崿F(xiàn)被要求的任意削減程度。在vtkDecimatePro中，有兩個重要的變量：TargetReduction是被要求減少的三角形的數(shù)量；PreserveTopology被設(shè)置為是否允許改變拓?fù)浣Y(jié)構(gòu)。

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

3 算法實現(xiàn)

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

　　3.1 點云數(shù)據(jù)集

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

　　3.2 實驗過程

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

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

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

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

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

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

4 實驗結(jié)果及分析

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

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

5 結(jié)語

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

參考文獻(xiàn)

　　[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的幾何體構(gòu)建技術(shù)[J].內(nèi)蒙古科技大學(xué)學(xué)報，2012，31(2)：167-170.

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

　　[8] 劉偉寧.基于VTK的海底聲納數(shù)據(jù)實時三維建模軟件設(shè)計[D].杭州：浙江大學(xué)，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] 李云.不規(guī)則形體點云的三維重建研究[D].烏魯木齊：新疆大學(xué), 2013：22-32.

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