空間圓形物體的共形幾何代數擬合方法

焦衛東,龐艷麗

(中國民航大學天津市智能信號與圖像處理重點實驗室,天津 300300)

1 引言

城市地鐵施工中盾構技術[1]、隧道測量[2]、交通工具風洞實驗以及某些圓形工業器件[3]-[6]在安裝校驗過程中需要按照規定的精度標準進行規范合理的安裝,同時各個儀器設備在運轉過程中也需要進行規范的測量。所有測量都是對空間圓形物體進行處理,而施工過程可能會給圓形器件帶來不同程度的變形導致其各項參數與設計值不完全一致,且空間圓形或孔型物體的特征量無法直接進行測量,間接方法成為此類問題的首選,目前常用的方法為通過專門的測繪儀器如全站儀或三維激光掃描技術[7]采集空間圓形物體周圍點集,并對采集到的坐標點利用不同的檢測或擬合方法計算得到該空間圓形的特征量。

平面圓已經有了較成熟的檢測方法如Hough變換[8]等,而升維變換增加了空間圓擬合的難度。目前,歐氏空間常用的空間圓檢測方法主要有立體視覺方法、最小二乘擬合法[9]、改進的最小二乘擬合法。其中,文獻[10]中提到的立體視覺方法,首先利用Canny算子提取圓邊緣點[11],然后提取出投影橢圓中心,利用雙目視覺原理得到空間圓的幾何參數,由于透視投影變換時會導致空間圓中心的投影與投影橢圓的中心不一致,因此立體視覺方法在處理大型圓形物體時得到的空間圓心坐標精度不高。針對此問題,文獻[12]對此進行改進,利用相機光心與成像橢圓構建空間圓錐方程,進而得到圓錐正底面從而求解出空間圓的平行平面方程,然后利用實際半徑找到正確空間圓方程。該方法雖然提高了檢測精度,但前提是實際半徑已知,另外由于歐氏空間線性方程求解的過程繁瑣,算法效率比較低。而最小二乘擬合法多是基于空間球面數學模型和平面方程進行數據處理,文獻[13]中,首先將三維坐標轉換到平面內進行平面圓擬合,將結果映射回三維坐標系從而得到空間圓的幾何參數,該方法需要進行二維、三維坐標的轉換,原理復雜且直接將三維坐標映射到平面內進行平面圓擬合誤差較大。針對此問題很多學者提出了多種解決方法,主要分為兩類,第一類充分結合空間圓的幾何特性,即空間圓中任意兩條弦對應的中垂面與空間圓所處的平面相交且交點即為平面圓的圓心,然后結合最小二乘擬合法推導出圓心計算方程,進而得到圓半徑[14]。通過該方法計算得到的參數誤差比較小,但依然難以避免由于歐氏空間計算的坐標相關性、多維不統一性導致的計算結構復雜、動態計算困難等問題。第二類利用奇異值(Singular Value Decomposition,SVD)分解[15]和最小二乘法進行最佳圓擬合,首先使用SVD找到最適合均值中心點集的平面,然后將均值中心點投影到擬合平面上,利用最小二乘法計算圓參數,最后將圓心換為三維坐標。該方法通過SVD的方式,求解得到適合對三維點集擬合的平面,克服了維度變換所帶來的精確度不高的問題,但同時增加了算法復雜度。

上述方法在保證檢測精度的前提下無法兼顧算法效率問題,而幾何代數(Geometric Algebra,GA)[16][17]對幾何實體獨特的表示方法以及坐標不相關性的特點可以簡化計算復雜度,其基本算子如內積(inner product)、外積(outer product)、幾何積(geometric product),簡化了幾何實體在傳統歐氏空間復雜坐標的表達,另外用內積替代距離等復雜的歐氏空間變量,便于高維空間到低維空間的相互轉化[18][19]。2010年白志鵬、李茂寬等提出基于共形幾何代數(Conformal Geometric Algebra,CGA)的平面圓擬合方法[20],在CGA空間直接表示平面圓方程,進而通過內積算子判斷點與圓的關系確定最佳擬合圓。而空間圓不能在共形空間中直接表示,所以平面圓擬合的共形幾何方法不再適用于空間圓擬合問題。

因此,本文在以上大量研究的基礎之上,綜合各自方法的優缺點,提出一種基于CGA的空間圓擬合方法。該方法在基于CGA平面圓擬合的基礎上,把空間圓擬合問題的實體對象轉換為球,利用CGA空間對球的中獨特表示形式,把平面圓擬合轉換為基于CGA的球擬合問題。進一步對求解得到的兩個最佳擬合超球面,在CGA空間利用Meet算子計算兩個超球面的交,結果即為最佳擬合空間圓。

2 共形幾何代數

2.1 基本定義

CGA有三個基本算子,分別是內積、外積和幾何積

(1)

其中,a、b為向量,θ是它們之間的夾角,i表示運算空間。內積既適用于相同維度的幾何對象,也可作用于不同維度的幾何對象,實質上是一種降維運算,可用于求解距離和角度等標量。外積適用于任意維度的空間,通過外積可進行空間維度的擴展與幾何形體的構建,實質上是一種升維運算。幾何積將外積和內積結合起來,實現矢量和標量的混合維度運算,成為幾何代數的核心運算,簡化算法結構,提高傳統代數計算的通用性。

共形幾何代數相對歐氏空間又增加兩個維度,空間變換從3維擴展到5維,其正交矢量基為:e1,e2,e3,e+,e-,滿足

(2)

引入Rn空間無窮遠點和原點

(3)

則5維共形空間的基變為:e1,e2,e3,e∞,e0。

幾何實體在CGA空間可以用內積和外積兩種不同的形式[21][22],表1是基本幾何實體的CGA表示以及在歐氏空間中對應的表達。

表1 共形幾何代數中實體的表示

2.2 基本運算

2.2.1CGA空間Meet運算

Meet運算符以統一的方式確定兩個對象之間的相交關系。blade是CGA的基本元素,給定任意兩個bladeA和B,如果滿足

(4)

則Meet運算表達式為

M=A∩B=(B·IAB)·A=Β*·A

(5)

其中,IAB表示包括A、B的最小子空間的偽標量。判斷不同對象之間的包含關系需要采用不同的相交判斷算法,通過不同幾何實體之間的Meet計算結果,可以生成所需的對象。本文主要討論相交球體之間的Meet運算結果,如表2所示。

2.2.2CGA空間距離計算

CGA空間中點、圓、球可以用矢量形式表示,這些對象的內積產生標量,可以用作距離的度量。CGA空間矢量(幾何實體)可以表示為

S=s1e1+s2e2+s3e3+s4e0+s5e∞s+s4e0+s5e∞

(6)

矢量P和S的內積表示為

P·S=(p+p4e∞+p5e0)·

(s+s4e∞+s5e0)=p·s-p4s5-p5s4

(7)

當P、S表示為兩個點時,由表1

(8)

因此,由式(7),這兩點內積為

(9)

當P表示點,S表示球時,由表1

(10)

根據式(7)得,點與球之間的內積為

(11)

此時,點與球內積的2倍等價于球半徑平方減去點到球心距離的平方,內積仍然與實體間的距離有關。

另外,CGA空間中不同實體之間的內積形式各不相同,但其意義均與距離有關。

3 基于CGA的空間圓擬合

3.1 擬合模型

在歐氏空間中,求解一組點 的最優擬合球(圓),可通過求解

(12)

3.創新服務方式，推行風險提示。待條件成熟后，以“互聯網+稅務”和大數據應用為依托，在納稅人通過互聯網正式進行年度納稅申報前，利用稅務登記信息、納稅申報信息、財務會計信息、備案資料信息、第三方涉稅信息等內在規律和聯系，對稅款計算的邏輯性、申報數據的合理性、稅收與財務指標關聯性等提供風險提示服務，幫助納稅人正確理解稅收政策，減少納稅風險。

(13)

(14)

對此代價函數求解,使得代價函數最小的解即是所求的最佳擬合球。

對求得的最小非負特征解S1,S2,即分別對應最佳擬合超球和第二最佳擬合超球。從而擬合的圓為:

circle=M(S1,S2)=S1∩S2

(15)

經過計算兩個最小特征解的求交,即可得到空間擬合圓方程及參數,無需進行迭代求解,因此可降低歐氏空間直接求解式(12)的計算復雜度。

3.2 算法步驟

基于CGA的空間圓擬合算法,無需通過迭代逼近的方法求其最優解,可以由式(14)及式(15)得到其解析解,理論上可以得到空間圓準確的擬合結果。其主要步驟為(流程圖如圖1所示):

1)獲取實驗數據點集{pi},并將其映射到CGA空間的數據點集{Pi};

2)利用式(13)、(14)對數據點集{Pi}求兩個最小非負特征解分別對應最優擬合超球S1和第二最優擬合超球S2,從而實現CGA空間球擬合過程;

3)利用式(15),通過CGA空間Meet算子(交運算)得到目標空間圓,輸出空間圓方程及相關參數;

4)利用步驟3)得到的空間圓方程及參數進行可視化表示。

4 實驗分析

實驗環境為Intelcorei7、2.90GHz處理器、8GB內存、Windows10 64bit計算機、python3.8平臺。實驗中的內積、外積、幾何積、Meet算子由Gaigen系統的Clifford模塊提供。實驗分兩組進行,第一組實驗對自造三維數據集利用本文算法進行空間圓擬合,第二組實驗分別對兩組利用全站儀測得的某圓形鋼結構參數進行空間圓擬合,并對算法的有效性進行了評估。

4.1 擬合模型

本組實驗針對離散分布的三維數據點集,將本文算法(簡記為CGA方法)與文獻[14]中最小二乘方法(Leastsquares,Leastsq)、以及文獻[15]中基于SVD的最小二乘方法(簡記為SVD)進行比較。

隨機生成繞圓心為(3,3,4),半徑2.5的空間圓分布的100個離散數據點,實驗數據點的分布如圖2所示。在圖2(a)表示實驗數據點中幾乎不存在噪聲點即理想情況下,對其添加一定噪聲的實驗數據點如圖2(b)所示。噪聲點占比0.01的實驗擬合結果如圖3所示,CGA空間圓擬合算法通過最佳擬合超球與第二最佳擬合超球的Meet運算得到空間圓,其中圖3(a)表示CGA擬合圓的球面表示,其中兩個超球面的相交圓即為最佳擬合空間圓,在圖3(b)中對其進行了單獨表示。同樣噪聲點占比0.1的實驗擬合結果如圖4所示,圖4(a)表示CGA擬合圓的球面表示,其中兩個超球面的相交圓即為最佳擬合空間圓,在圖4(b)中對其進行了單獨表示。

圖3 噪聲比占比0.01情況下CGA擬合結果

圖4 噪聲比占比0.1情況下CGA擬合結果

通過圖3(a)、圖4(a)可以看出,由于CGA空間對幾何實體獨特的表示方法,對空間圓擬合問題提出了新思路,即通過內積、外積算子將歐氏空間代價函數求解問題轉換到CGA空間表示,避免了歐氏空間算法由于迭代次數多導致計算復雜度高、效率低的問題。無論是無噪聲還是有噪聲情況,CGA擬合的精度都非常高。

為進一步驗證本文算法的有效性,從算法運行效率上與歐氏空間中的兩種擬合方法:文獻[14]中最小二乘法、文獻[15]中基于SVD方法進行對比分析,結果如表3所示。

表3 檢測結果及運行時間

由表3結果得到,在可靠性方面,三種算法與理論值相差不大。而基于CGA的方法相比其它兩種方法具有明顯的優勢:數學模型簡單,便于計算,可直接得到空間圓參數,計算過程無需進行復雜的迭代求解,從而提高運算效率。

為進一步考慮噪聲對算法準確度的影響,選擇服從高斯分布的實驗點數據進行擬合。噪聲點分布在整個平面上而不是在圓附近,按照噪聲偏移數據點的情況分為兩組實驗,如圖5(a)、(b)所示。基于CGA方法的數據點擬合結果如圖6、圖7,結果可以看出:當噪聲點越來越偏移數據點時,擬合結果與真實值略有偏差,在誤差允許的范圍內,可忽略不計。

圖5 實驗數據點分布

圖6 噪聲1情況下CGA擬合結果

圖7 噪聲2情況下CGA擬合結果

由于空間圓擬合算法在歐氏空間是基于空間球體數學模型和平面方程聯合得到結果,在計算過程中需要求解大量參數,從而導致運行效率低。而在CGA空間避免了線性計算過程,在簡化計算復雜度的同時,處理問題更具幾何直觀意義。表4中給出了對圖6、圖7實驗數據點三種方法的擬合結果及運行時間。由表4可知,在兩種復雜噪聲情況下,CGA方法的準確度最高、其次是基于最小二乘的方法、最后是基于SVD的方法。其中噪聲2情況的半徑誤差依次是:4.2088、11.6786、12.1007(×10-3),因此基于CGA方法不僅對含有復雜噪聲點數據具有較高的擬合精度,且運行效率最高,運行時間縮短了接近4～5倍。

表4 檢測結果及運行時間

4.2 工程仿真驗證

為了驗證本文方法在實際應用中的實用性,以文獻[4]、[5]中的某圓形鋼結構的實測參數為例進行驗證。采用最小二乘方法、基于SVD方法以及基于CGA方法分別對數據進行擬合計算,數據點三維坐標如表5、6所示。

表5 實例1三維坐標

表6 實例2三維坐標

圖8(a)、9(a)分別給出實例1、實例2的CGA擬合結果,具體實測點及擬合圓形如圖8(b)、9(b)。實例1中圓形鋼結構設計半徑為12.2m,利用CGA方法測得擬合圓半徑與設計半徑誤差為3.932mm。另外兩種歐氏空間方法得到的擬合圓半徑誤差均為3.391mm,但是其運行效率低于CGA方法。實例2中圓形物體設計半徑為5m,CGA方法測得擬合圓半徑誤差為3.315mm,最小二乘法為3.293mm,SVD方法為3.296mm。因此,基于CGA方法的空間圓擬合算法滿足工程測量的需要,且由于獨有的空間特性,運行效率高于歐氏空間。實驗結果如表7所示。

圖9 CGA擬合結果-實例2

表7 檢測結果及運行時間

5 總結

本文在CGA平面圓擬合基礎之上,將最小二乘擬合球算法引入到CGA空間,得到CGA空間擬合球算法的新表達,并結合CGA空間特殊的Meet算子,提出了基于共形幾何代數的空間圓擬合算法。與文獻[14]中基于空間圓特性的最小二乘方法、文獻[15]中基于SVD的最小二乘方法相比,本文算法:

1)共形空間對幾何實體的處理更加直觀,避免了歐氏空間大量求解方程帶來的算法冗余問題,算法有效性得到明顯提升。

2)將歐氏空間最小二乘擬合球方法映射到CGA空間得到新表達,避免了求解復雜線性方程對算法效率的影響。

3)利用CGA空間Meet算子獨特的幾何意義計算兩個最佳擬合超球,得到最佳擬合空間圓。避免了歐氏空間三維、二維坐標之間的相互轉換,算法結構簡單,計算效率高。

4)實驗表明,本文算法針對數據點較多、噪聲分布復雜情況下,算法的檢測精度更高,同時運行效率高,工程實用性較強。