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

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

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

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

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

1 擬合算法

1.1 整體算法流程

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

首先，DF算法對收集到的點(diǎn)云數(shù)據(jù)進(jìn)行預(yù)處理，初始化數(shù)據(jù)點(diǎn)，得到初始數(shù)據(jù)矩陣。

然后對初始數(shù)據(jù)矩陣進(jìn)行運(yùn)算，得到一個(gè)7×7的矩陣M，該矩陣是一個(gè)中間變量，用于計(jì)算擬合后表達(dá)式系數(shù)等相關(guān)參數(shù)。利用最小二乘法和拉格朗日乘數(shù)法算出球面一般式中的每項(xiàng)的系數(shù)，得到初步的參數(shù)。

最后計(jì)算出球面的最終參數(shù)和一些分析參數(shù)，將結(jié)果和LM算法以及自身對比分析。

1.2 拉格朗日乘數(shù)法

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

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

圖1 拉格朗日數(shù)乘法結(jié)構(gòu)示意圖

1.3 球面擬合計(jì)算

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

對于球面來說，由于不存在交叉項(xiàng)，可以默認(rèn)將f，g，h設(shè)置為零。由上面拉格朗日數(shù)乘法得到的結(jié)論，我們構(gòu)建球面表達(dá)式：

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

并且點(diǎn)云個(gè)數(shù)至少要大于7。

接下來我們就要構(gòu)建上一部分計(jì)算的矩陣M，首先構(gòu)建矩陣A：

對于任意一個(gè)點(diǎn)i，其中()是點(diǎn)云中的任意一個(gè)有效點(diǎn)的坐標(biāo)。

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

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

1.4 計(jì)算結(jié)果的參數(shù)分析

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

其中1λ是對半徑的誤差分析，R是求出來的計(jì)算值，R′是標(biāo)準(zhǔn)值。

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

我們還保存了計(jì)算過程中使用的時(shí)間，來衡量計(jì)算的速度。

2 結(jié)果分析

2.1 與LM算法的對比

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

2.1.1 算法時(shí)間

我們?nèi)〗?jīng)過預(yù)處理的模擬數(shù)據(jù)，并去掉背景空白的點(diǎn)作為初始有效點(diǎn)進(jìn)行分析，分析的球?qū)嶋H位置為圓心在（0,0,0）點(diǎn)，半徑為15。對LM算法和DF算法進(jìn)行分別計(jì)算（下面如無說明，情況相同）。取不同的有效點(diǎn)數(shù)29081，7272，1818，451，分別計(jì)算它們所用的時(shí)間，得到下面的時(shí)間對比圖：

圖2 DF和LM算法時(shí)間對比

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

2.1.2 算法精確度

在相同情況下，我們對衡量參數(shù)λ1，λ2和E都進(jìn)行了分析計(jì)算，得到的結(jié)果如下：

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

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

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

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

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

2.1.3 受噪聲影響程度

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

從受噪聲影響情況來看，DF更容易受噪聲影響，當(dāng)噪聲超過0.11之后DF的精確度會增加的非?？欤诔^0.5之后已經(jīng)失去了可信度和可比較價(jià)值，所以，我們可以承認(rèn)，DF算法對噪聲的敏感性很高，我們在運(yùn)行計(jì)算之前需要結(jié)合去噪聲等算法來提高精度，因?yàn)樵谠肼曒^低的情況下，DF算法的可用性很高。

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

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

2.2 對點(diǎn)云進(jìn)行分組計(jì)算對結(jié)果的影響

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

3 結(jié) 論

本文提出了一種球面擬合的方法實(shí)現(xiàn)基于點(diǎn)云的球面三維逆向建模，并在速度和精度上都取得了較為理想的結(jié)果。通過與LM算法的對比分析，得出了DF算法的優(yōu)越性，和對噪聲影響敏感這一個(gè)需要改善的問題的結(jié)論，還提出需要在之前結(jié)合去噪分析的建議來改善噪聲對結(jié)果的影響。本文也對分組和在數(shù)據(jù)量較少的前提下的數(shù)據(jù)位置對結(jié)果影響進(jìn)行了分析，為之后后續(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ì)的玻殼曲面擬合方法[J]. 計(jì)算機(jī)測量與控制, 2004,12(6): 569-571.

[4]楊恒亮, 屠大維, 趙其杰. 基于三坐標(biāo)測量機(jī)的大口徑球面擬合測量方法[J]. 工具技術(shù), 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]張之孔. 加權(quán)二次曲面高程擬合方法及精度分析[J].測繪科學(xué)與工程, 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.