基于點云的球面三維逆向建模

李勝男， 林 曉, ， 陳 言， 馬利莊

( 1. 上海交通大學電子信息與電氣工程學院，上海 200240；2. 洛陽師范學院信息技術學院，河南 洛陽 471000）

逆向建模指的是通過對工程中掃描得到的點云數據經過擬合計算，得到三維空間模型的一種方法。對球面點云的擬合[1]來說，尤其是對只有不完整球面的掃描數據點云來說，本算法在工程上有廣泛的應用價值，不僅在零件檢測、建筑物結構恢復等方面應用廣泛，在氣象學和考古學等領域也逐漸嶄露頭角，顯示出其不可替代的作用。本算法利用激光掃描獲得的點云來擬合球面和圓柱面，恢復被遮擋物的原貌；對于不全的圖形，將其整體圖形展示出來，為后續(xù)工作打下基礎。

現(xiàn)階段，球面和圓柱面等二次曲面的擬合主要是利用非線性最小二乘法[2-4]中的LM[5]算法進行迭代計算。然而，LM算法收斂次數會受到初始值設定的影響，從而影響計算速度，并有可能由于收斂次數過多而在漫長的計算之后失敗，得到不準確的結果。2005年，Tahir Rabbani Shah[6]提供了一種通過對二次曲面的一般式全部九個參數直接擬合計算的方法，為二次曲面擬合開辟了一條新路。2008年Wenjuan Sun[7]提出對小角度的一段表面進行球面擬合的方法，2011年張之孔[8]提出加權二次曲面高程擬合方法及精度分析，這些都在一定程度上推動了球面擬合算法的發(fā)展。

本文提出的直接擬合方法(DF)結合以上算法，并提出改進，能夠更快速準確的直接擬合出球面的幾何參數。通過對球面添加不同程度高斯白噪聲，算法給出了其對噪聲的適應性分析。算法通過將點云切割分層整合計算和整體代入兩種方法進行實現(xiàn)，并對比相應結果，分析得到相應結論。算法還對點云數量和點云分布位置等情況進行討論，從而分析出影響算法結果的幾個方面。

1 擬合算法

1.1 整體算法流程

本文提出的算法（以下簡稱DF算法）主要是通過3個過程得到最終的結果

首先，DF算法對收集到的點云數據進行預處理，初始化數據點，得到初始數據矩陣。

然后對初始數據矩陣進行運算，得到一個7×7的矩陣M，該矩陣是一個中間變量，用于計算擬合后表達式系數等相關參數。利用最小二乘法和拉格朗日乘數法算出球面一般式中的每項的系數，得到初步的參數。

最后計算出球面的最終參數和一些分析參數，將結果和LM算法以及自身對比分析。

1.2 拉格朗日乘數法

拉格朗日乘數法[9]是一種常見的求函數極值的方法，對于具有約束條件的函數來說，可以通過引入λ量進行求解，本文實現(xiàn)的球面擬合是以這個方法為基礎的。

對于一個平面來說，我們可以設置平面法向量為n =(nx,ny,nz)，并且進行單位化，設|n| =1，將原點到這個平面的距離，我們設置為ρ，那么，對于任意一個點云中的點p =(px,py,pz)，我們可以計算它的到平面的正交距離，表示為n·p-ρ。為了優(yōu)化點云中的點到這個平面的距離之和（最小二乘法得到擬合最佳結果），采用拉格朗日乘數法[9]：

圖1 拉格朗日數乘法結構示意圖

1.3 球面擬合計算

二次曲面都可以用一般形式表示出來：

對于球面來說，由于不存在交叉項，可以默認將f，g，h設置為零。由上面拉格朗日數乘法得到的結論，我們構建球面表達式：

對于球面來說，a,b,c應該是相等的。但是對于計算結果來說，他們在允許的條件下大致相等。對于我們的算法來說，我們只需要6個維度的未知量即可，所以我們追加了一個限制條件，系數的平方和等于1即

并且點云個數至少要大于7。

接下來我們就要構建上一部分計算的矩陣M，首先構建矩陣A：

對于任意一個點i，其中()是點云中的任意一個有效點的坐標。

M矩陣是一個7×7的矩陣，對于Tahir Rabbani Shah提出的算法進行了改進，提高了速度將近四倍。利用上一章闡述的拉格朗日乘數法，我們要得到的結果系數向量：

向量n是矩陣最小的特征值所對應的特征向量，通過求出向量n，從而得到一般式的系數，也就得到了利用最小二乘法計算的最短距離時對應的結果。利用這種方法，問題的主要部分得到解決。之后我們只需要對球的表達式進行配方等基本操作，就可以得到半徑和圓心等幾何參量。

1.4 計算結果的參數分析

對于球面來說，不僅僅需要計算球面的圓心和半徑，我們還提供了4個參量對計算結果進行分析，他們分別是：

其中1λ是對半徑的誤差分析，R是求出來的計算值，R′是標準值。

E是點云中所有點距離球面的幾何距離的平均值，是對球面誤差的整體分析。

我們還保存了計算過程中使用的時間，來衡量計算的速度。

2 結果分析

2.1 與LM算法的對比

LM算法是非線性最小二乘法中被廣泛應用的一種算法，它通過給出初始值和表達式形式，利用相應的迭代方法，進行收斂計算，從而得到球面的幾何參數。下面我們就DF和LM算法進行對比分析。

2.1.1 算法時間

我們取經過預處理的模擬數據，并去掉背景空白的點作為初始有效點進行分析，分析的球實際位置為圓心在（0,0,0）點，半徑為15。對LM算法和DF算法進行分別計算（下面如無說明，情況相同）。取不同的有效點數29081，7272，1818，451，分別計算它們所用的時間，得到下面的時間對比圖：

圖2 DF和LM算法時間對比

由圖中可以看出，DF算法時間明顯小于LM算法，而且在隨著點數增加的同時，增長率明顯小于LM算法，在速度上明顯優(yōu)于LM。而且DF算法只與有效點數有關，而LM算法還與迭代次數和迭代初始值相關。

2.1.2 算法精確度

在相同情況下，我們對衡量參數λ1，λ2和E都進行了分析計算，得到的結果如下：

圖3 DF和LM算法半徑誤差值λ1對比

圖4 DF和LM算法圓心誤差值λ2對比

圖5 DF和LM算法幾何距離誤差對比

對于3種誤差的分析，我們無一例外的發(fā)現(xiàn)，DF算法的精確度明顯高于LM算法，而且，LM的算法精確度不只是受到點數的影響，在1818點的時候還出現(xiàn)了跳變。而DF算法則不會有這種問題。

而且，DF算法對有效點數的要求不高，在這四種情況下，我們可以看到，誤差基本不受有效點數的影響，而點數對于速度的影響是唯一的制約條件，我們可以在保持精確度不受影響的條件下，通過降低點數的條件下來提高速度，這是一個DF算法相對于LM算法的另一個優(yōu)點。不過降低點數不能極端地影響點云中點的分布，否則會對結構造成一定程度，甚至是很大的影響，后面會進行分析。

2.1.3 受噪聲影響程度

由于在實際工程中，掃描會帶來一定程度的高斯白噪聲，所以，在相同點數29081的條件下，我們分別對兩個算法添加了高斯白噪聲，等級依次為0, 0.1, 0.2 和 0.5，并分別進行了比較，得到圖6所示。

從受噪聲影響情況來看，DF更容易受噪聲影響，當噪聲超過0.11之后DF的精確度會增加的非?？?，在超過0.5之后已經失去了可信度和可比較價值，所以，我們可以承認，DF算法對噪聲的敏感性很高，我們在運行計算之前需要結合去噪聲等算法來提高精度，因為在噪聲較低的情況下，DF算法的可用性很高。

圖6 DF和LM算法受噪聲影響對比

而噪聲影響對于球面函數擬合的影響是否重要，這要看工程上的具體要求。一般來說，采集到的點云都帶有噪聲，但是強度并不是很大，在誤差允許的范圍之內。影響擬合精度的原因很大程度上來說，是數據點只采集到球面的一部分而不是全部，或者由于遮擋等關系，造成點云數據的不全面，所以DF算法對于噪聲的影響還是在可接受范圍內的，而噪聲在0.1左右的時候，DF算法并未受到明顯的影響。

2.2 對點云進行分組計算對結果的影響

由于精度對數據點的個數并沒有特別大的影響，所以，我們嘗試通過先分組計算，最后整合各組數據來得到結果。但是，得到的結果并不理想，而且，對于數據量較少（10～100之間）的情況下，數據點的位置分布也對擬合的結果影響較大。

3 結 論

本文提出了一種球面擬合的方法實現(xiàn)基于點云的球面三維逆向建模，并在速度和精度上都取得了較為理想的結果。通過與LM算法的對比分析，得出了DF算法的優(yōu)越性，和對噪聲影響敏感這一個需要改善的問題的結論，還提出需要在之前結合去噪分析的建議來改善噪聲對結果的影響。本文也對分組和在數據量較少的前提下的數據位置對結果影響進行了分析，為之后后續(xù)工作的研究提供了方向。

[1]Cavalier T M, Lehtihet E A, Del Castillo E, et al. An adaptive sphere-fitting method for sequential tolerance control [J]. International Journal of Production Research, 2002, 40(12): 2757-2767.

[2]Levenberg K. A method for the solution of certain non-linear problems in least squares [J]. Quarterly of Applied Mathematics, 1944, 2(2): 164-168.

[3]宋敏清,丁國清, 顏國正. 一種基于最小二乘估計的玻殼曲面擬合方法[J]. 計算機測量與控制, 2004,12(6): 569-571.

[4]楊恒亮, 屠大維, 趙其杰. 基于三坐標測量機的大口徑球面擬合測量方法[J]. 工具技術, 2007, 41(12):78-81.

[5]Ananth R. The levenberg-marquardt algorithm [R]. 8th June, 2004.

[6]Rabbani T S. Automatic reconstruction of industrial installations using point clouds and images [D]. Delft University of Technology, 2006.

[7]Sun Wenjuan, Hill M, McBride J W. An investigation of the robustness of the nonlinear least-squares sphere fitting method to small segment angle surfaces [J].Precision Engineering, 2008, 32(1): 55-62

[8]張之孔. 加權二次曲面高程擬合方法及精度分析[J].測繪科學與工程, 2011, 31(2): 26-28.

[9]Vapnyarskii I B. Lagrange multipliers [M]. Hazewinkel,Michiel. Encyclopedia of Mathematics. Berlin:Springer. ISBN 978-1-55608-010-4.