崔佳潔，崔希民，王 強，李 聰

中國礦業(yè)大學（北京）地球科學與測繪工程學院，北京 100083

1 引言

隨著現(xiàn)在科技的迅猛發(fā)展，特別是計算機技術、通信技術等的發(fā)展，在測繪領域出現(xiàn)了很多的技術創(chuàng)新。在科學和技術不斷發(fā)展下，人們對3D測量技術和三維數(shù)據(jù)迅速處理的需求也在增加[1]。在不同測量條件下（如對象，表面材料，測量范圍和環(huán)境）幾秒之內(nèi)得到的密集的3D點云[2-4]，它主要是由簡單的幾何元素（如平面、球面、氣缸，錐和環(huán)面）等組成的[5]。與三維測量技術的進展相比，三維數(shù)據(jù)處理在軟件工具方面幾乎停滯不前[6]。數(shù)據(jù)擬合各種方法的改進和應用以及如何得到合適的模型一直是一個比較熱門的研究領域。處理三維數(shù)據(jù)時，模型擬合的算法是從一個點云中估算模型參數(shù)的基礎，通常通過最小化一個預定義的最佳誤差的平方和來確定模型參數(shù)，即最小二乘法[7]。

本文在最小二乘原理的基礎上闡述了一種新的數(shù)據(jù)擬合方法——幾何正交距離擬合法。在各種誤差的測量中，首先關心的是在處理空間數(shù)據(jù)時擬合模型與給定的點之間最短的距離（也稱為幾何距離，正交距離）[8]。但是很長一段時間，在幾何距離誤差最小化分析和計算時遇到困難，阻礙開發(fā)適當?shù)臄M合算法。幾何正交距離擬合方法是基于通過給定點到符合其幾何特征相關點的坐標描述，此時從給定點到幾何特征擬合點之間的連線是最短的。理論上幾何正交距離擬合方法，充分應用正交的概念和最小二乘原理，克服了代數(shù)方法的缺點，從而期望得到更好的精度與執(zhí)行效率。一般代數(shù)擬合方法，是用含代數(shù)參數(shù)的隱式多項式方程來表示曲線或曲面，如果測量點不在擬合模型上，就存在擬合誤差，把它叫做代數(shù)距離，簡單直接的方法是確定使每個點的代數(shù)距離的平方和最小的代數(shù)參數(shù)。在代數(shù)擬合中（二維、三維或任意n維），通常認為其中n-1維的數(shù)據(jù)是精確的，而只有剩下的一維數(shù)據(jù)是有誤差的，而且代數(shù)擬合計算成本小，易于實現(xiàn)，這種前提導致了一般最小二乘代數(shù)擬合在測量領域的廣泛使用[9]。

2 幾何正交距離擬合方法

2.1 最小二乘擬合原理

設空間內(nèi)有一個直線工件（如圖1），為求取其變形量，對該工件上的點進行一系列觀測，得到n個點的坐標(xi，yi)，由于該工件存在變形，不考慮觀測誤差，每個觀測點的變形量即該點觀測值與設計值的直線距離。以vi表示各觀測點至設計值之間的距離改正數(shù)，可以采用多種方法來較合理地確定，測繪工作中常采用使每個觀測點到曲線距離的平方和為最小的方法[10]。

圖1 直線工件

觀測過程中每個點的中誤差都存在一定的差別，合理的方法是定義權：

σ0是與觀測值無關的常數(shù)項，稱為先驗單位權中誤差，mi為i點的中誤差，中誤差與權值成反比。

以每個觀測點到曲線距離的平方和為最小來確定曲線時，權值的大小決定了觀測點對曲線確定的貢獻大小，因此,條件可以改為：

寫成矩陣形式VTPV=min，由此確定出的曲線被認為是最合理的。

2.2 幾何正交距離擬合

2.2.1 直線正交距離擬合

直線上一已知點X0，r為3維空間內(nèi)平行于這條直線的單位向量，這條直線可表示為：

使測量點到直線的正交距離的平方和=達到最小，對其求導可得（平行軸理論[11]）：

定義：

可得慣性張量H[11]為：

正交距離平方和變?yōu)椋?/p>

對稱方陣H可通過奇異值分解[12]（SVD）為：

其中，WH=[diag(wH1，wH2， …，wHn)]， VH=(vH1，vH2，…，vHn)，VH=1， 奇 異 值wH1，wH2，…，wHn和 正 交 向 量vH1，vH2，…，vHn分別是質(zhì)心力矩和主慣性軸[13]。如果r平行于其中一個主軸vHj，由此可得：，此時直線可表示為：。

奇異值分解是提供空間一組標準的正交基，是一種求解最小平方差的方法[14]?？傊?，這條由m個觀測點通過正交距離擬合而成的直線，經(jīng)過這些點的中心，并且平行于其中一個有最小質(zhì)心主力矩的主慣性軸。

2.2.2 平面正交距離擬合

平面上點X0，n為3維空間內(nèi)垂直于這個平面的單位法向量，這個平面可表示為：

其中：

對稱方陣H可通過奇異值分解（SVD）為：

其中：

當選擇n平行于向量vMj時wMj最小，正交距離平面可表示為：

總之，這個由m個觀測點通過正交距離擬合而成的平面，經(jīng)過這些點的中心，并且垂直于其中一個有最小質(zhì)心主力矩的主慣性軸[15]。

2.2.3 圓和球正交距離擬合

一個圓或球的方程可以用圓心（球心）X0和半徑r來表示，如圖2所示。

圖2 圓的表示

圖中di可表示為di= ||Xi-Xo-r。

di的雅可比矩陣為：

球擬合的線性方程組為：

同理，最小距離點X'i的雅可比矩陣為：

球擬合線性方程組可以寫成：

正交距離算法以正交距離殘差平方和極小為原則，同時顧及了因變量和自變量的誤差，通過向量和矩陣計算確定擬合模型。直線、平面的正交距離擬合是一個線性問題，計算成本較小，易于實現(xiàn)。圓、球擬合為非線性問題，由圓和球方程得到每個點的雅克比（jacobi）矩陣。

3 標準幾何體數(shù)據(jù)擬合結果對比

用一般代數(shù)擬合程序和幾何正交距離擬合程序處理實驗數(shù)據(jù)。直線和平面擬合實驗中，在測量誤差很小的情況下，兩種算法結果相差不大，經(jīng)過大量實驗數(shù)據(jù)的處理發(fā)現(xiàn)，當直線或平面上有偏離直線較遠的點時，結果明顯不同。這里僅列出測量點偏離直線或平面較遠時的實驗結果（如表1）。

表1 標準幾何體數(shù)據(jù)擬合結果

由上面的結果可以看出直線或平面擬合在測量誤差很大的情況下，正交距離擬合結果明顯優(yōu)于代數(shù)擬合結果。而圓和球的擬合即使在測量誤差很小的情況下，正交距離擬合結果優(yōu)于代數(shù)擬合結果，說明了正交距離擬合在曲線的擬合中有優(yōu)勢。

4 分析與總結

本文提出了一種對于一般曲線和空間隨機點云的最佳擬合算法——幾何正交距離擬合法，這種算法通過最小化測量點與擬合面之間的距離來估計線和面的參數(shù)。傳統(tǒng)一般代數(shù)擬合方法忽略了自變量x的誤差，直接建立自變量x與因變量y之間的關系方程式y(tǒng)=f(x)，而實際工程的測量和數(shù)據(jù)的采集都是通過一定的工程手段或測量儀器得到，無論自變量還是因變量都可能存在誤差，所以本文提出改變衡量最佳擬合曲線的標準。幾何正交距離擬合法以殘差的平方和極小為準則進行擬合，同時顧及了因變量和自變量的誤差，從幾何意義理解，采用正交距離法擬合更加合理。

在直線平面、擬合中，自變量的誤差較小，用代數(shù)最小二乘法擬合，自變量誤差常常被略而不計，對擬合參數(shù)的影響較小。計算簡單實用，因而得到了廣泛應用。但是當測量點偏離直線或平面較遠時，幾何正交距離擬合精度明顯優(yōu)于一般代數(shù)擬合的精度。從圓和球的擬合結果可以明顯看出當曲線自變量誤差較小時，幾何正交距離擬合精度明顯優(yōu)于一般代數(shù)擬合的精度，因為曲線自變量誤差較大，忽略自變量的誤差就會影響參數(shù)的大小，此時就應顧及自變量的誤差，使幾何體的擬合效果從整體上達到最佳，因此提出采用幾何正交距離擬合法擬合曲線。

[1]厲東偉.工業(yè)測量系統(tǒng)在國內(nèi)外的發(fā)展現(xiàn)狀[J].科技信息，2011，22（8）：130-132.

[2]Heinz I，Mettenleiter M，Hartl F，et al.3D ladar for inspection of real world environments[C]//Proc 5th Conf Optical 3D Measurement Techniques，Vienna，2001：10-17.

[3]3D laserscannerhardwareand softwaresurvey-point of beginning[EB/OL].（2004-04-11）.http：//www.pobonline.com/FILES/HTML/PDF/0104l aser-survey.pdf.

[4]Ullrich A，Reichert R，Schwarz R，et al.Time-of-flight-based 3D imaging sensor with true-color channel for automated texturing[C]//Proc 5th ConfOptical3D Measurement Techniques，Vienna，2001：2-9.

[5]王解先，季凱敏.工業(yè)測量擬合[M].北京：測繪出版社，2008：36-78.

[6]Ahn S J.Last squares orthogonal distance fitting of curves and surfaces in spare[M].New York：Springer，2004：17-20.

[7]牛常勝，楊國為.基于幾何距離準則的新數(shù)據(jù)擬合方法[J].微計算機信息，2006（24）.

[8]丁克良，歐吉坤，趙春梅.正交最小二乘曲線擬合法[J].測繪科學，2007，32（3）：16-19.

[9]蔡強.工業(yè)測量擬合與設備幾何要素分析技術的研究[J].山東科技大學學報，2011（4）.

[10]陶本藻.論最小二乘擬合[J].武漢測繪學院學報，1980：27-34.

[11]Beer F P,Johnston E R.Vector mechanics for engineers：dynamics[M].[S.l.]：McGraw-Hill，2009.

[12]Golub G H，Reinsch C.Singular value decomposition and least squares solutions[J].Numerische Mathematik，1970：403-420.

[13]Press W H，F(xiàn)lannery B P，Teukolsky S A，et al.Numerical recipes in C：the art of scientific computing[M].Cambridge，UK：Cambridge University Press，1988.

[14]王振芳，李博峰，沈云中.基于奇異值分解的擬穩(wěn)平差法[J].測繪通報，2008（5）：30-32.

[15]Pearson K.On lines and planes of closest fit to systems of points in space[J].The Philosophical Magazine，1901，2（6）：559-572.