基于點云數據的曲面重建算法比較研究

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

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

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

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

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

1 算法描述

1.1 基于貪婪算法的網格曲面重建

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

基于貪婪算法的網格曲面重建的核心思想：(1)獲得各點的連接關系。將已知點通過法線投影至相應平面，再對投影得到的點作Delauany三角化處理，經軟件處理得到各點關系矩陣。(2)生成完整的三角網格曲面。獲得各點連接關系后，通過基于Delauany的空間區域增長算法，經初始曲面不斷擴張邊界，生成結果。(3)形成最后的曲面重建模型。最后按照投影點云的相互關系完成各原始三維點間的拓撲連接獲得結果。

1.2 基于移動立方體隱式曲面重建算法

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

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

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

泊松方程是有著重要應用地位的偏微分方程，應用領域很廣，如高動態范圍圖像的調和映射、圖像區域的無縫編輯、流體力學、網格編輯等，其中多重泊松方程已在高效GPU計算得到了很好的應用[17]。基于泊松方程的曲面重構是一種隱式曲面重構方法，與使用較多的有向距離場函數不同。其核心思想如下。

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

(1)

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

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

(2)

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

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

(3)

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

1.4 基于NURBS技術的曲面重建算法

1975年，有理B樣條曲線和曲面被美國Syracuse大學的Verspril研究出來。20世紀80年代后期，Pieg和Tiller經過研究將有理B樣條延伸為非均勻有理B樣條(Nonuniform Rational B-Spline，NURBS)曲線和曲面。如今NURBS已成為自由曲線和曲面表征的應用較為廣泛的技術，國際標準化協會(ISO)已將NURBS的方式作為定義工業產品幾何形狀的唯一數學方法[18]。NURBS曲面的表達[19]如公式(4)：

(4)

公式4表示k*l次NURBS曲面，其中：di,j(i=0，…，n;j=0，…m)是呈拓撲矩陣陣列的控制點，進而構成一個完整的擁有控制點的網格；Wi,j是與控制點相聯系的加權因子；Bi,k(u)為u方向的k階基函數，Bj,l(v)為v方向的l階基函數，它們分別由u向和v向的節點矢量決定。利用NURBS進行曲面重建時，其核心思想如下[20]：

(1)針對各切片上的數據，通過計算，將它們換算成帶權的型值點；

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

2 算法實驗及分析

2.1 曲面重建前預處理

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

2.2 四種不同算法的實驗結果比較與分析

在逆向工程中，精度體現著逆向生成的模型和現實世界實物之間差距的程度，曲面擬合精度則體現了擬合得到的曲面模型和實物之間的偏差，通常通過實物上的原始點到模型表面的偏差距離來表示[23-26]。曲面擬合精度對曲面重建過程的誤差控制、重建方法優劣的衡量有著重要的指導意義[18]。重建算法的評價體系國內外還沒有很好的標準。本文主要利用兔子點云數據、建筑物點云數據進行實驗，通過從算法本身的時間復雜度、空間復雜度以及重建后的曲面擬合精度等三個方面進行各算法間的比較分析，從而得出研究結果。

本文的所有算法實驗都是基于PCL點云庫完成的，算法所用的計算機編程語言為C++，計算機的具體配置為Core i3處理器、4G內存以及windows7操作系統。圖1為兔子點云數據及建筑物點云重建的實驗結果，表1、表2為實驗結果分析的數據。

圖1 重建結果比較

(圖中從左到右對應的組圖分別為原始數據點云、貪婪三角化重建結果、移動立方體重建結果、泊松方程重建結果、NURBS重建結果)

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

表1 四種算法的時間復雜度及空間復雜度

表2 四種算法重建后精度評價

注：其中Max表示點云與3D曲面模型的最大距離；Mean表示點云與3D曲面模型的平均距離；中誤差即所建模型與點云的標準偏差)

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

3 結束語

本文針對兩種不同類型的數據，從點云曲面重建三種方式中，比較了四種不同算法的優劣程度。為了進行點云重建各種算法的比較，提出了通過算法的時間復雜度與空間復雜度以及重建后的精度評價來衡量各算法的優劣。其中重建后的精度評價用點云與3D曲面模型的最大距離、點云與3D曲面模型的平均距離以及所建模型與點云的標準偏差即中誤差來表示。實驗結果表明，參數曲面重建方式較好，網格曲面重建及隱式曲面重建其次。本研究可以為曲面重建方式的選擇提供一定的參考。