吳 旭， 盧凌雯， 梁棟棟， 汪曉楚

(1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241003；2.安徽師范大學(xué) 地理與旅游學(xué)院，安徽 蕪湖 241003；3.安徽師范大學(xué) 地理大數(shù)據(jù)研究中心，安徽 蕪湖 241003；4.蘇州市測(cè)繪院有限責(zé)任公司，江蘇 蘇州 221008)

在逆向工程、計(jì)算機(jī)視覺(jué)、CAD制圖、三維測(cè)量技術(shù)等眾多領(lǐng)域，點(diǎn)云數(shù)據(jù)處理技術(shù)從八十年代起就被廣泛應(yīng)用，且發(fā)展至今[1]。隨著計(jì)算機(jī)輔助設(shè)計(jì)與計(jì)算機(jī)圖形學(xué)的發(fā)展，越來(lái)越多的學(xué)者對(duì)點(diǎn)云數(shù)據(jù)的曲面重建技術(shù)產(chǎn)生了濃厚的興趣。從現(xiàn)有研究來(lái)看，曲面重構(gòu)大致可以分為顯式曲面重構(gòu)和隱式曲面重構(gòu)兩類方法[2]。顯式曲面重構(gòu)方法提出較早，需要先將點(diǎn)云參數(shù)化，然后再進(jìn)行曲面重構(gòu)。它一般不能用單個(gè)曲面來(lái)直接擬合點(diǎn)云，比如NURBS算法需要先將點(diǎn)云分割成不同區(qū)域，然后分別擬合各自的曲面，最后將擬合的各曲面進(jìn)行拼合得到完整曲面。隱式曲面重構(gòu)方法利用隱式函數(shù)得到逼近點(diǎn)云的等值曲面，相比顯式曲面重構(gòu)方法，隱式曲面重構(gòu)更適用于重構(gòu)復(fù)雜拓?fù)湫螤畹那?，且重?gòu)的曲面具有很好的封閉性和完整性。除此之外，劉含波[3]等對(duì)曲面重建方法有兩種分類方式：根據(jù)生成的表面是否經(jīng)過(guò)原始采樣點(diǎn)，分為基于插值的表面重建和基于逼近的表面重建；根據(jù)重建過(guò)程中所依賴的插值點(diǎn)的信息，分為基于全局準(zhǔn)則的整體重建和基于局部準(zhǔn)則的局部重建。宋大虎等[4]根據(jù)現(xiàn)有算法的特點(diǎn)，將曲面重建算法分為隱式曲面算法、參數(shù)曲面算法、基于學(xué)習(xí)的方式和Delaunay三角剖分算法。

本文從點(diǎn)云表面重建方式的角度，把曲面重建分成網(wǎng)格曲面、隱式曲面、參數(shù)曲面，其中貪婪投影三角化算法屬于網(wǎng)格曲面重建，移動(dòng)立方體算法以及泊松方程算法屬于隱式曲面重建，NURBS算法屬于參數(shù)曲面重建。

在實(shí)際工程中，采用多邊形模型如網(wǎng)格方法作為輸入輸出，無(wú)論在數(shù)據(jù)處理方面，還是在計(jì)算機(jī)顯示方面，都擁有一定的優(yōu)勢(shì)[5]。Delaunay三角網(wǎng)的逐點(diǎn)插入法與分治合并法兩大方法在19世紀(jì)70年代相繼被提出。20世紀(jì)80年代末，Chew提出了Delaunay Refinement算法[6]，在90年代初，Ruppert改進(jìn)了Delaunay Refinement算法，使該算法得到的三角形最小角大于20.7度[7]。之后，Rivara、Hitscfeld、Simpson等人進(jìn)一步擴(kuò)展和優(yōu)化，使得最小角的最小值達(dá)到30度[8]?；陔[式函數(shù)的曲面重構(gòu)方法可分為局部擬合方法和全局?jǐn)M合方法?；诰植繑M合的隱式函數(shù)重構(gòu)方法出現(xiàn)較早。最早的代表性方法山由Hoppe等[9]人提出，先擬合局部點(diǎn)云的平面，再估算點(diǎn)云的一致性法矢，然后構(gòu)建有向距離函數(shù)，最后提取其零等值面。其中代表性的是移動(dòng)最小二乘曲面(MLS)方法[10]。和局部擬合方法不同，全局隱式擬合方法利用數(shù)學(xué)函數(shù)同時(shí)擬合所有點(diǎn)云數(shù)據(jù)來(lái)重構(gòu)曲面，徑向基函數(shù)(RBF)[11]方法是代表性的算法之一。基于參數(shù)曲面的重建也是長(zhǎng)久以來(lái)點(diǎn)云重建的重要手段之一。參數(shù)曲面典型的算法有B-splines曲面、NURBS(非均勻有理B樣條曲面)[12]以及Bezier曲面。

1 算法描述

1.1 基于貪婪算法的網(wǎng)格曲面重建

貪婪算法常用于將復(fù)雜問(wèn)題簡(jiǎn)單化，使問(wèn)題變得更容易解決[13]。貪婪算法的性能影響最大的因素是貪婪三大準(zhǔn)則[14]：最近貪婪準(zhǔn)則；近鄰貪婪準(zhǔn)則；定向貪婪準(zhǔn)則。

基于貪婪算法的網(wǎng)格曲面重建的核心思想：(1)獲得各點(diǎn)的連接關(guān)系。將已知點(diǎn)通過(guò)法線投影至相應(yīng)平面，再對(duì)投影得到的點(diǎn)作Delauany三角化處理，經(jīng)軟件處理得到各點(diǎn)關(guān)系矩陣。(2)生成完整的三角網(wǎng)格曲面。獲得各點(diǎn)連接關(guān)系后，通過(guò)基于Delauany的空間區(qū)域增長(zhǎng)算法，經(jīng)初始曲面不斷擴(kuò)張邊界，生成結(jié)果。(3)形成最后的曲面重建模型。最后按照投影點(diǎn)云的相互關(guān)系完成各原始三維點(diǎn)間的拓?fù)溥B接獲得結(jié)果。

1.2 基于移動(dòng)立方體隱式曲面重建算法

移動(dòng)立方體算法常用于醫(yī)學(xué)圖像可視化三維重建，處理的對(duì)象為離散的三維空間規(guī)則數(shù)據(jù)場(chǎng)，主要應(yīng)用于三維重建的可視化。由于該算法具有步進(jìn)式的特點(diǎn)，故被稱為移動(dòng)立方體(Marching Cubes)算法[15]。Lorensond等人于1987年提出的Marching Cubes算法是一種流行的從體數(shù)據(jù)中提取等值面的算法[16]，該算法對(duì)每個(gè)被處理的體素，以三角面片表示其內(nèi)部的等值面，它的算法核心思想如下。

(1)三維數(shù)據(jù)場(chǎng)中構(gòu)造體素。通過(guò)選取立方體中上下兩層切片圖像形成三維數(shù)據(jù)場(chǎng)。(2)判斷立方體與等值面交點(diǎn)。通過(guò)8個(gè)頂點(diǎn)函數(shù)值與相應(yīng)等值面閾值的比較，分析生成相應(yīng)的索引表。(3)獲得各頂點(diǎn)處的法向量。通過(guò)索引表計(jì)算出交點(diǎn)處的坐標(biāo)，從而獲得各處的法向量。(4)曲面重建。由所求三角面片各頂點(diǎn)處的坐標(biāo)和法向量繪制出等值面，最后實(shí)現(xiàn)模型的重構(gòu)。

1.3 基于泊松方程的隱式曲面重建算法

泊松方程是有著重要應(yīng)用地位的偏微分方程，應(yīng)用領(lǐng)域很廣，如高動(dòng)態(tài)范圍圖像的調(diào)和映射、圖像區(qū)域的無(wú)縫編輯、流體力學(xué)、網(wǎng)格編輯等，其中多重泊松方程已在高效GPU計(jì)算得到了很好的應(yīng)用[17]?；诓此煞匠痰那嬷貥?gòu)是一種隱式曲面重構(gòu)方法，與使用較多的有向距離場(chǎng)函數(shù)不同。其核心思想如下。

(1)泊松重構(gòu)采用的是指示函數(shù)，即在模型內(nèi)部為1，外部為0。重構(gòu)的是修正后的指示函數(shù)，其指示函數(shù)如公式(1)：

(1)

在此種定義下，可知χ的梯度在距邊界w/2內(nèi)等于有向距離場(chǎng)的梯度d除以w，而在其他地方則恒為0。而有向距離場(chǎng)在某一點(diǎn)的梯度則等于這點(diǎn)對(duì)應(yīng)的曲面最近點(diǎn)的法矢(向內(nèi))。如果通過(guò)曲面點(diǎn)云中的最近點(diǎn)來(lái)近似曲面最近點(diǎn)，則χ的梯度可以由已知定向法矢的曲面點(diǎn)云得到。

(2)在已知函數(shù)梯度的情況下重構(gòu)出函數(shù)。記已知的函數(shù)梯度為V，定義泛函如公式(2)：

(2)

其中Ω指整個(gè)計(jì)算域，泛函表示整個(gè)計(jì)算域上未知函數(shù)的梯度場(chǎng)與已知向量場(chǎng)的總誤差。令泛函最小，得到經(jīng)典的泊松方程如下公式(3)：

Δf=Δ*ν(注：邊界條件為f|?Ω=0)

(3)

(3)在離散的情況，使用離散正弦變換代替上面的連續(xù)變換，即可得到離散的解，而離散正弦變換可由快速傅立葉得到。最終隱式函數(shù)解用Marching-Cube方法轉(zhuǎn)為三角網(wǎng)格。

1.4 基于NURBS技術(shù)的曲面重建算法

1975年，有理B樣條曲線和曲面被美國(guó)Syracuse大學(xué)的Verspril研究出來(lái)。20世紀(jì)80年代后期，Pieg和Tiller經(jīng)過(guò)研究將有理B樣條延伸為非均勻有理B樣條(Nonuniform Rational B-Spline，NURBS)曲線和曲面。如今NURBS已成為自由曲線和曲面表征的應(yīng)用較為廣泛的技術(shù)，國(guó)際標(biāo)準(zhǔn)化協(xié)會(huì)(ISO)已將NURBS的方式作為定義工業(yè)產(chǎn)品幾何形狀的唯一數(shù)學(xué)方法[18]。NURBS曲面的表達(dá)[19]如公式(4)：

(4)

公式4表示k*l次NURBS曲面，其中：di,j(i=0，…，n;j=0，…m)是呈拓?fù)渚仃囮嚵械目刂泣c(diǎn)，進(jìn)而構(gòu)成一個(gè)完整的擁有控制點(diǎn)的網(wǎng)格；Wi,j是與控制點(diǎn)相聯(lián)系的加權(quán)因子；Bi,k(u)為u方向的k階基函數(shù)，Bj,l(v)為v方向的l階基函數(shù)，它們分別由u向和v向的節(jié)點(diǎn)矢量決定。利用NURBS進(jìn)行曲面重建時(shí)，其核心思想如下[20]：

(1)針對(duì)各切片上的數(shù)據(jù)，通過(guò)計(jì)算，將它們換算成帶權(quán)的型值點(diǎn)；

(2)根據(jù)B樣條曲線的邊界條件及反算公式獲得控制點(diǎn)，再把求得的控制點(diǎn)作為v向的型值點(diǎn)，最后沿v向依據(jù)B樣條曲線的邊界條件及反算公式進(jìn)行反算獲得di,j，從而形成整個(gè)控制網(wǎng)格。

2 算法實(shí)驗(yàn)及分析

2.1 曲面重建前預(yù)處理

在測(cè)量的過(guò)程中，由于儀器本身固有的一些誤差以及所測(cè)對(duì)象所處環(huán)境產(chǎn)生的誤差，不可避免地對(duì)測(cè)得的點(diǎn)云數(shù)據(jù)重建后的曲面產(chǎn)生影響。這些不規(guī)則數(shù)據(jù)難以用統(tǒng)計(jì)分析的方法去除，需要進(jìn)行平滑處理和漏洞修復(fù)。在通常不能進(jìn)行額外掃描的情況下，可以通過(guò)對(duì)數(shù)據(jù)重采樣來(lái)解決這一問(wèn)題[21]。根據(jù)相關(guān)研究[22]，移動(dòng)最小二乘法能通過(guò)給定的離散點(diǎn)來(lái)近似估計(jì)其中的未知點(diǎn)，然后連接這些離散點(diǎn)來(lái)獲取整個(gè)曲面。它不僅保證了原始樣本不變，而且用相對(duì)少量的空洞邊緣的樣本就能填補(bǔ)空洞。因此，本文在點(diǎn)云數(shù)據(jù)曲面重建前，利用移動(dòng)最小二乘法數(shù)據(jù)作為平滑處理及漏洞修復(fù)技術(shù)進(jìn)行預(yù)處理，進(jìn)一步增強(qiáng)曲面重建的效果。

2.2 四種不同算法的實(shí)驗(yàn)結(jié)果比較與分析

在逆向工程中，精度體現(xiàn)著逆向生成的模型和現(xiàn)實(shí)世界實(shí)物之間差距的程度，曲面擬合精度則體現(xiàn)了擬合得到的曲面模型和實(shí)物之間的偏差，通常通過(guò)實(shí)物上的原始點(diǎn)到模型表面的偏差距離來(lái)表示[23-26]。曲面擬合精度對(duì)曲面重建過(guò)程的誤差控制、重建方法優(yōu)劣的衡量有著重要的指導(dǎo)意義[18]。重建算法的評(píng)價(jià)體系國(guó)內(nèi)外還沒(méi)有很好的標(biāo)準(zhǔn)。本文主要利用兔子點(diǎn)云數(shù)據(jù)、建筑物點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，通過(guò)從算法本身的時(shí)間復(fù)雜度、空間復(fù)雜度以及重建后的曲面擬合精度等三個(gè)方面進(jìn)行各算法間的比較分析，從而得出研究結(jié)果。

本文的所有算法實(shí)驗(yàn)都是基于PCL點(diǎn)云庫(kù)完成的，算法所用的計(jì)算機(jī)編程語(yǔ)言為C++，計(jì)算機(jī)的具體配置為Core i3處理器、4G內(nèi)存以及windows7操作系統(tǒng)。圖1為兔子點(diǎn)云數(shù)據(jù)及建筑物點(diǎn)云重建的實(shí)驗(yàn)結(jié)果，表1、表2為實(shí)驗(yàn)結(jié)果分析的數(shù)據(jù)。

圖1 重建結(jié)果比較

(圖中從左到右對(duì)應(yīng)的組圖分別為原始數(shù)據(jù)點(diǎn)云、貪婪三角化重建結(jié)果、移動(dòng)立方體重建結(jié)果、泊松方程重建結(jié)果、NURBS重建結(jié)果)

從圖1可以看出，基于NURBS點(diǎn)云重建與基于貪婪投影三角化點(diǎn)云重建的曲面失真度小，效果較好，基于移動(dòng)立方體的點(diǎn)云重建與基于泊松方程點(diǎn)云重建的效果次之。從表1四種算法的時(shí)間復(fù)雜度及空間復(fù)雜度可以看出，基于貪婪投影與基于NURBS所用的時(shí)間復(fù)雜度及空間復(fù)雜度較小，基于移動(dòng)立方體與基于泊松方程的時(shí)間復(fù)雜度及空間復(fù)雜度較大。從表2四種算法重建后精度評(píng)價(jià)可以看出，兩種不同類型的數(shù)據(jù)，四種算法針對(duì)兔子點(diǎn)云重建的誤差較小，對(duì)建筑物點(diǎn)云重建的誤差較大。從兔子點(diǎn)云數(shù)據(jù)重建中可以看出，基于貪婪投影與基于NURBS重建后的誤差較小，基于移動(dòng)立方體與基于泊松方程重建后的誤差較大。從建筑物點(diǎn)云數(shù)據(jù)重建中可以看出，基于NURBS重建的誤差最小，基于移動(dòng)立方體與基于泊松方程重建的誤差其次，基于貪婪投影的誤差最大。

表1 四種算法的時(shí)間復(fù)雜度及空間復(fù)雜度

表2 四種算法重建后精度評(píng)價(jià)

注：其中Max表示點(diǎn)云與3D曲面模型的最大距離；Mean表示點(diǎn)云與3D曲面模型的平均距離；中誤差即所建模型與點(diǎn)云的標(biāo)準(zhǔn)偏差)

綜上所述，針對(duì)本文涉及的兩種類型點(diǎn)云數(shù)據(jù)中，三種重建方式，基于NURBS參數(shù)曲面重建的方式最佳，基于貪婪投影三角化網(wǎng)格曲面重建的方式其次，基于移動(dòng)立方體與基于泊松方程隱式曲面重建方式的時(shí)間復(fù)雜度與空間復(fù)雜度較大，且重建后的點(diǎn)云模型誤差也較大。

3 結(jié)束語(yǔ)

本文針對(duì)兩種不同類型的數(shù)據(jù)，從點(diǎn)云曲面重建三種方式中，比較了四種不同算法的優(yōu)劣程度。為了進(jìn)行點(diǎn)云重建各種算法的比較，提出了通過(guò)算法的時(shí)間復(fù)雜度與空間復(fù)雜度以及重建后的精度評(píng)價(jià)來(lái)衡量各算法的優(yōu)劣。其中重建后的精度評(píng)價(jià)用點(diǎn)云與3D曲面模型的最大距離、點(diǎn)云與3D曲面模型的平均距離以及所建模型與點(diǎn)云的標(biāo)準(zhǔn)偏差即中誤差來(lái)表示。實(shí)驗(yàn)結(jié)果表明，參數(shù)曲面重建方式較好，網(wǎng)格曲面重建及隱式曲面重建其次。本研究可以為曲面重建方式的選擇提供一定的參考。