0 引言

　　隨著圖像處理技術(shù)和激光掃描技術(shù)的發(fā)展,，三維曲面重建技術(shù)作為一個(gè)重要研究?jī)?nèi)容廣泛應(yīng)用于逆向工程、模式識(shí)別,、影視等領(lǐng)域中,，并得到快速發(fā)展。三維曲面重建是采用三維點(diǎn)云數(shù)據(jù)快速,、準(zhǔn)確地構(gòu)建出復(fù)雜的曲面模型?，F(xiàn)有的重建算法主要分為兩類：容積重建和表面重建[1],。容積重建在密集計(jì)算上耗費(fèi)時(shí)間較長(zhǎng),，不能夠滿足實(shí)時(shí)處理的需要。表面重建處理速度比較快,，適合實(shí)時(shí)處理,，主要包括輪廓線連接、等值面提取和Delaunay三角化,。輪廓線連接是把相鄰的橫截面輪廓點(diǎn)連接起來,，構(gòu)建成一個(gè)三角網(wǎng)格，但在網(wǎng)格對(duì)應(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)確性降低,。

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

　　1 三維可視化類庫(kù)VTK

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

　　構(gòu)成VTK體系主要有2種對(duì)象模型：圖形模型對(duì)象和可視化模型對(duì)象,。圖形模型的主要作用是用圖形描述幾何體構(gòu)成的場(chǎng)景；可視化模型的主要作用是把幾何數(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 重建算法簡(jiǎn)介

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

　　Voronoi圖在解決點(diǎn)與其他幾何對(duì)象的距離關(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軌跡的總和,。對(duì)于點(diǎn)集P中的每個(gè)點(diǎn)都有一個(gè)對(duì)應(yīng)的Voronoi多邊形，所有的多邊形總和就稱為點(diǎn)集P的Voronoi圖,。

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

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

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

　　Power圖和其對(duì)偶的規(guī)則三角剖分是對(duì)應(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)勢(shì)是在細(xì)節(jié)區(qū)域,，輸出的離散表面具有致密的點(diǎn)；在其他區(qū)域,，輸出的離散表面只有稀疏的點(diǎn),。 具體步驟如下：

　　(1)對(duì)采樣點(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)格簡(jiǎn)化、平滑

　　經(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)格簡(jiǎn)化；使用平滑網(wǎng)格技術(shù),，通過調(diào)整點(diǎn)的位置來降低輪廓面的鋸齒效應(yīng)和分級(jí)效應(yīng),，改善圖形的質(zhì)量。

　　VTK支持4種Decimation對(duì)象：vtkDecimate,、vtkDecimatePro,、vtkQuadricClustering、vtkQuardricDecimation,。vtkDe-

　　cimatePro執(zhí)行速度相對(duì)較快,，并且在削減過程中能夠修改拓?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是可視化對(duì)象的集合,，這些可視化對(duì)象可以連接起來形成一個(gè)可視化管道。這個(gè)管道開始輸入數(shù)據(jù)源,，經(jīng)過一系列的濾波器過濾,，最后顯示出來[1]。

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

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

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

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

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

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

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

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

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

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

　　為了證明算法的有效性,，選用兔子,、貓、馬3組三維點(diǎn)云數(shù)據(jù)來進(jìn)行測(cè)試,。圖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é)了兩種方法對(duì)3組數(shù)據(jù)的重建結(jié)果,。

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

5 結(jié)語

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