0 引言

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

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

　　1 三維可視化類庫VTK

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

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

　　2 重建算法簡介

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

　　2.1 Power Crust算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

　　(3)生成極點(diǎn)球集合Bp，計(jì)算出Power圖。

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

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

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

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

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

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

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

3 算法實(shí)現(xiàn)

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

　　3.1 點(diǎn)云數(shù)據(jù)集

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

　　3.2 實(shí)驗(yàn)過程

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

5 結(jié)語

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

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

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

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