莫建文，龐建鏗，袁 華

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004)

基于VTK的三維點(diǎn)云曲面重建研究*

莫建文，龐建鏗，袁 華

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004)

針對(duì)三維點(diǎn)云數(shù)據(jù)重建效率低、不能實(shí)時(shí)交互等問(wèn)題，利用魯棒性強(qiáng)的 Power Crust算法和三維可視化類庫(kù)Visualization Toolkit(VTK)的良好并行機(jī)制與強(qiáng)大的圖像處理能力，實(shí)現(xiàn)了三維點(diǎn)云數(shù)據(jù)曲面快速重建。該算法使用Power Crust對(duì)三維點(diǎn)云進(jìn)行曲面重建，接著對(duì)得到的網(wǎng)格進(jìn)行線性調(diào)整、簡(jiǎn)化和平滑，最后引入VTK進(jìn)行渲染、繪制、顯示，并實(shí)時(shí)交互。實(shí)驗(yàn)結(jié)果表明，該算法可以加快散亂點(diǎn)云數(shù)據(jù)的重建速度，較好地保持了點(diǎn)云數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，提高了曲面重建的精確性和魯棒性，且交互性強(qiáng)，適合實(shí)時(shí)處理。

三維點(diǎn)云；Power Crust；VTK；曲面重建

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)連接起來(lái)，構(gòu)建成一個(gè)三角網(wǎng)格，但在網(wǎng)格對(duì)應(yīng)、拼接等問(wèn)題上沒(méi)有解決好。等值面提取[1]是取當(dāng)前點(diǎn)的 8個(gè)鄰近點(diǎn)形成一個(gè)虛擬的多維數(shù)據(jù)集，確定一個(gè)多邊形來(lái)代表等值面表面，但等值面涉及到復(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ì)以上問(wèn)題，本文提出了一種基于 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)化、平滑等處理，

通過(guò)局部形狀校正獲得三維模型，顯示并交互。實(shí)驗(yàn)結(jié)果表明，此算法運(yùn)行速度快，重建曲面較為準(zhǔn)確、光滑，圖像質(zhì)量高，適合實(shí)時(shí)處理。

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

VTK[5-7]是美國(guó) Kitware公司利用 C++語(yǔ)言開(kāi)發(fā)的一套集3D圖形學(xué)、圖像處理和可視化于一體的C++類庫(kù)。它是一個(gè)源碼開(kāi)發(fā)、可視化技術(shù)和圖像處理軟件系統(tǒng)，可在 C++、Tcl/Tk、Jave、Pyhon語(yǔ)言環(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ù)、過(guò)濾、映射與渲染，最后將所成圖像呈現(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è)貪婪的濾波過(guò)程來(lái)處理那些有噪聲的散亂數(shù)據(jù)，逆向重建了曲面的三角網(wǎng)格，并有理論上的支持。

2.1 Power Crust算法原理

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

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

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)過(guò)三角剖分的原始點(diǎn)云連接成三角網(wǎng)格模型，經(jīng)過(guò)Voronoi圖過(guò)濾器過(guò)濾后，刪除不符合要求的網(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)過(guò) 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ù)，通過(guò)調(diào)整點(diǎn)的位置來(lái)降低輪廓面的鋸齒效應(yīng)和分級(jí)效應(yīng)，改善圖形的質(zhì)量。

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

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

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

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

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

實(shí)驗(yàn)使用的數(shù)據(jù)來(lái)源于對(duì)現(xiàn)實(shí)動(dòng)物貓的三維掃描，通過(guò)激光掃描儀掃描到的數(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)過(guò)程

在Microsoft Visual C++平臺(tái)中，對(duì)三維點(diǎn)云進(jìn)行曲面重建和可視化，主要經(jīng)過(guò)下面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)過(guò)簡(jiǎn)化、平滑后的曲面網(wǎng)格，經(jīng)過(guò)平面法向量估計(jì)、數(shù)據(jù)映射，建立演員類等處理，在VTK流水線機(jī)制上進(jìn)行渲染、繪制。

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

圖1 三維曲面重建整體框圖

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

為了證明算法的有效性，選用兔子、貓、馬3組三維點(diǎn)云數(shù)據(jù)來(lái)進(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é)果。

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

圖2 三維點(diǎn)云原始點(diǎn)云圖

圖3 Power Crust曲面重建圖

圖4 本文算法曲面重建圖

表1 兩種方法對(duì)不同點(diǎn)云模型的曲面重建對(duì)照表

5 結(jié)語(yǔ)

本文分析了現(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ì)于沒(méi)有法向量的大量散亂點(diǎn)云數(shù)據(jù)，處理速度非常快，但效果不是很準(zhǔn)確。所以將經(jīng)過(guò)去噪、濾波后的點(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í)意義。相信在不久的將來(lái)，隨著計(jì)算機(jī)技術(shù)的發(fā)展以及圖像處理技術(shù)的深入研究，三維點(diǎn)云曲面重建將會(huì)擁有廣泛的應(yīng)用空間。

[1]LI J，HUANG S，LI G，et al.Reconstruction and visualiza-tion of 3D surface model from serial-sectioned contour points[C].Image and Signal Processing(CISP)，2010 3rd International 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].Computational Geometry，2001，19(2)：127-153.

[3]NI T，MA Z.A fast surface reconstruction algorithm for 3D unorganized 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 based on scattered point cloud data surface reconstruction[C]. Wireless Mobile and Computing(CCWMC 2011)，IET International Communication Conference on.IET，2011：97-101.

[5]WILLIAM J，SCHROEDER，LISA S，et al.The visualization toolkit 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 surface reconstruction from noisy point clouds[C].Image Processing(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.

3D surface reconstruction of point cloud based on VTK

Mo Jianwen，Pang Jiankeng，Yuan Hua
(School of Information and Communication，Guilin University of Electronic Technology，Guilin 541004，China)

3-D reconstruction of point cloud data has low efficiency and can not real-time interaction.In order to overcome above problems,this article uses Power Crust algorithm with strong robustness and 3-D visualization class library Visualization Toolkit(VTK)，which has good parallelism and powerful image processing ability，to realize the fast reconstruction of three-dimensional point cloud data.The algorithm uses Power Crust to pretreat the input point cloud data,and adjusts approximation error dynamically, simplifying and smoothing.Later,the VTK is used to realize rendering,drawing,display and real-time interaction.Experimental results show that this algorithm can speed up the reconstruction of scattered point cloud data,maintain the topology,improve the accuracy and robustness of surface reconstruction,and be able to interact in real time.

3D point cloud；Power Crust；VTK；surface reconstruction

TP391.41

A

0258-7998(2015)04-0156-03

10.16157/j.issn.0258-7998.2015.04.039

2014-12-31)

莫建文(1972-)，男，博士，副教授，主要研究方向：模式識(shí)別、智能信息處理、圖像處理。

龐建鏗(1989-)，男，碩士研究生，主要研究方向：圖像處理。

袁華(1975-)，通信作者，男，碩士，講師，主要研究方向：圖像處理、智能圖像處理，E-mail：yuanhua@guet.edu.cn。

廣西自然科學(xué)基金(2013GXNSFAA019331，2014GXNSFDA118035)；桂林電子科技大學(xué)研究生教育創(chuàng)新計(jì)劃資助項(xiàng)目（GDYCSZ201453）