基于維度特征的RANSAC建筑物點云分割算法

劉 闖,花向紅,田 茂,袁 達

(1.武漢大學 測繪學院，湖北 武漢 430079；2.武漢大學 災害監(jiān)測與防治中心，湖北 武漢 430079)

?

基于維度特征的RANSAC建筑物點云分割算法

劉 闖1,2,花向紅1,2,田 茂1,2,袁 達1,2

(1.武漢大學 測繪學院，湖北 武漢 430079；2.武漢大學 災害監(jiān)測與防治中心，湖北 武漢 430079)

提出一種以建筑物表面形狀特征為分割依據(jù)的改進RANSAC點云分割算法。該算法以主成分分析算法為基礎計算維度特征和熵函數(shù)，并以熵函數(shù)最小準則確定最優(yōu)鄰域，繼而進行表面形狀分類，運用法向量夾角作為約束條件對分類結(jié)果進行優(yōu)化。將分類結(jié)果作為隨機抽樣一致性(RANSAC)點云分割算法的模型選擇依據(jù)，進行建筑物表面分割，采用法向量和距離等約束條件對分割結(jié)果進行優(yōu)化，從而分割出具有不同形狀的特征表面。實驗表明：文中提出的改進的RANSAC點云分割算法是可行的，能有效保留表面特征。

維度特征；熵函數(shù)；點云數(shù)據(jù)；建筑物表面形狀；改進的RANSAC算法

隨著研究的不斷深入，點云分割的算法理論已得到不斷豐富和完善。在眾多的算法中，隨機抽樣一致性算法(RANSAC)作為一種有效的穩(wěn)健估計算法[1]，在建筑物表面分割方面有天然優(yōu)勢。李娜等[1]將點云的r半徑密度引入RANSAC點云分割的判定準則中，并結(jié)合角度和距離等約束條件進行算法改進。胡偉等[2]將種子點的選取和點到距離的標準差等引入到屋頂面片點云的RANSAC分割中。Awwad等[3]提出以點云法向量與RANSAC分割平面的夾角剔除分割假平面的方法，提高分割質(zhì)量。Martinez J等[4]提出通過對掃描數(shù)據(jù)定向改進RANSAC點云分割算法。但當涉及形狀較為復雜的表面時，RANSAC一次僅能使用一個模型，而使用常規(guī)的一種模型分割，會造成分割的錯誤或不足，導致表面特征的丟失，為后續(xù)的曲面重建及建模工作帶來不便；若使用兩種或多種模型分別對點云分割，會導致部分點云分割錯誤或位于不同模型中。

Demantke等[5]提出通過計算維度特征，確定最優(yōu)鄰域和鄰域的形狀的方法。Yang等[6]成功地將維度特征與點云的其他特征相結(jié)合，使用支持向量機(SVM)方法實現(xiàn)不同物體的分類與提取。Pauly M等[7]提出通過自適應步長的PCA算法與輪廓模型相結(jié)合，從點云表面模型中提取線形特征的方法。Belton D等[8]提出用局部鄰域構(gòu)建協(xié)方差矩陣進行點云數(shù)據(jù)分類和特征提取的改進算法，并應用于分割之中。借鑒上述思想，為克服在表面形狀較為復雜的建筑物分割中存在的分割不足或錯誤現(xiàn)象，本文提出一種以維度特征為基礎，進行多類模型分割的RANSAC分割改進算法。

1 基于維度特征的RANSAC點云分割算法

為保證形狀較為復雜的建筑物表面分割的正確性和特征的完整性，本文將以維度特征為基礎的形狀判斷準則引入到RANSAC點云分割算法中，并針對形狀判定準則存在的缺陷，提出以法向量夾角對其判定結(jié)果進行修正的方法。對分類后的形狀選擇不同分割模型分別進行RANSAC分割，并以法向量和距離為約束條件進行分割優(yōu)化，有效保證分割的正確性和特征的完整性。

1.1 建筑物表面形狀的分類

依據(jù)主成分分析(PCA)算法構(gòu)建點pi的局部協(xié)方差矩陣C。由于C為對稱正定矩陣，必存在特征值分解，即

(1)

分類時，首先，確定鄰域搜索半徑的下限r(nóng)min和上限r(nóng)max及變化步長rΔ，并設定初始搜索半徑r為rmin，并以此令r=r+rΔ，根據(jù)搜索半徑，對局部鄰域內(nèi)的點云運用PCA算法分別計算相應的維度特征和熵函數(shù)值，熵函數(shù)計算見式(2)，直至r>rmax。然后，比較并選出最小熵函數(shù)值，并將其對應的半徑的覆蓋區(qū)域作為最優(yōu)鄰域[3]，利用最優(yōu)鄰域?qū)木S度值區(qū)分不同形狀。

Ef=-α1Dln(α1D)-α2Dln(α2D)-α3Dln(α3D).

(2)

(3)

1.2 建筑物表面形狀分割

考慮到RANSAC算法是不加區(qū)分的對待所有數(shù)據(jù)，噪聲點云會對分割造成一定的影響。為獲得正確的建筑物表面模型，在建筑物表面形狀分類的基礎上，按照下列步驟進行分割：

1)按照RANSAC算法要求，需要在一定的置信概率下，獲得求解模型參數(shù)的最小迭代次數(shù)M，滿足關系式[1,9]

P=1-(1-(1-ε)m)M.

(4)

式中:P為能取得較好模型的概率，一般為0.9～0.99;ε為數(shù)據(jù)錯誤率;m為計算模型參數(shù)需要的最小點數(shù)。

2)從確定的建筑物表面形狀中,隨機選取m個點云數(shù)據(jù)，計算建筑物表面模型參數(shù)。按照歐氏距離判定準則進行局內(nèi)點和局外點的判定，即通過計算點云至模型表面的幾何距離d,若d在閾值δ范圍內(nèi)則是局內(nèi)點，反之是局外點。按照RANSAC算法,直到構(gòu)建M個模型為止。從M個模型中選取點云數(shù)最多的模型，當模型上點大于一定閾值時，利用這些點云數(shù)據(jù)，采用整體最小二乘方法求得模型參數(shù)，將此模型作為最優(yōu)模型，并將此模型上的點從點云數(shù)據(jù)中剔除；否則跳出分割過程，將點云歸為離散點。

3)對剩余的點，按照步驟2)進行建筑物表面形狀提取，獲取所有符合條件的模型。

(5)

2 實驗與分析

為了考察本文提出的改進的RANSAC點云分割算法的可行性和效果，采用C++和OPENGL實現(xiàn)該算法，其算法流程如圖1所示。

圖1 改進的RANSAC點云分割算法流程

采用RIGEL_VZ_400地面三維激光掃描儀，對兩種不同風格的建筑物進行掃描，設置采樣間隔為0.03 m，其掃描的建筑物點云數(shù)據(jù)如圖2所示。

2.1 表面形狀分類分析

確定最優(yōu)鄰域是形狀正確分類的前提。受PCA算法所需點云數(shù)的影響,根據(jù)相關統(tǒng)計，鄰域范圍內(nèi)點云應在10個以上[3]，為此，本文設定rmin為0.08 m；考慮到建筑物A上部的圓體的體積大小，為盡量避免將曲面分為平面，設置rmax為3 m；在綜合考慮分類的正確率和計算時間后，并將其平分為16份。按照1.1節(jié)方法分別計算相應半徑的維度特征和熵函數(shù)，并比較熵函數(shù)大小選出最優(yōu)鄰域，并按式(1)進行形狀分類，分類結(jié)果見圖2。

由圖2中分類后的點云可以看出，在選定最優(yōu)鄰域進行形狀分類時，結(jié)果基本正確。此外，在界面的交界處點云被錯誤的分為三維曲面，且當結(jié)構(gòu)凹凸較明顯時，會將凹凸相交處的邊界線分為三維曲面，如建筑物A中平面部分中的窗體邊緣及凸出部分的邊緣被判斷成三維曲面。為此，本文通過計算表面上一點p及相鄰點的法向量夾角Δθ，對比夾角與閾值的大小，對形狀分類結(jié)果進一步處理。針對本文數(shù)據(jù)，設置夾角閾值為0.2°。處理前后的對比見表1。

由表1可以看出，建筑物A平面分類的準確率為74.9%，曲面分類準確率為80.2%；建筑物B分類的正確率可達到90.8%。采用以法向量夾角為約束條件對分類結(jié)果進行處理后，建筑物A平面分類準確率提高14.9%，曲面分類準確率提高8.1%；建筑物B分類準確率提高3.1%。

圖2 掃描的建筑物點云

建筑物類別點云總數(shù)/個原始數(shù)據(jù)類別數(shù)量/個分類形狀原始分類優(yōu)化后分類數(shù)量/個正確率/%數(shù)量/個正確率/%建筑物A88128平面曲面803477781平面曲面線形平面曲面線形60229182971821147062426974.9---80.2-721526374182174568676989.8---88.3-建筑物B90182平面90182平面曲面線形818595680264390.8--846952844264393.9--

2.2 表面形狀分割分析

在進行RANSAC點云分割時，為有效區(qū)分不同的形狀模型，保證表面特征的完整性，本文根據(jù)采集數(shù)據(jù)結(jié)構(gòu)凹凸的具體情況，設置距離閾值δ為0.2 m；此外，為減少離群點對分割的影響，在迭代計算模型時，將終止條件設定為最優(yōu)模型的局內(nèi)點數(shù)不少于總數(shù)的1/5。分割結(jié)果如圖3所示。

由圖3(a)可知，當采用一種模型(以平面模型為例)進行分割時，會導致上部的球體(僅取球面上位于斜平面上的點)和側(cè)面屋檐(數(shù)據(jù)丟失)等特征信息的錯誤或丟失。采用本文方法可有效避免上述問題，如圖3(b)所示。

圖3 RANSAC分割結(jié)果

為了解決過度分割現(xiàn)象，如存在窗體和墻體不在同一平面等現(xiàn)象，本文采用平面法向量夾角閾值0.1°和平面間距0.25 m進行分割面的優(yōu)化，其結(jié)果如圖3(c)所示。由圖3(c)可知，本文方法有效保留表面的特征，避免運行RANSAC僅能使用一種模型的缺陷。

3 結(jié) 論

本文通過引入維度特征進行形狀的判斷和分類，并通過法向量夾角進行優(yōu)化，保證分類的正確性，后續(xù)進行RANSAC分割，既能有效避免采用不同模型分別對所有點云數(shù)據(jù)進行處理造成的點云分割錯誤或重復，又能保證分割的正確性與完整性。實驗證明，通過本文的方法，能夠有效克服僅使用一種模型的RANSAC分割造成的分割錯誤或不足，有效保留表面特征，為下一步的曲面重建和建模做好準備。

[1] 李娜,馬一薇,楊洋,等.利用RANSAC算法對建筑物立面進行點云分割[J].測繪科學,2011，36(5):144-145.

[2] 胡偉,盧小平,李珵,等.基于改進RANSAC算法的屋頂激光點云面片分割方法[J].測繪通報，2012(11):31-34.

[3] AWWAD T M,ZHU Qing,DU Zhiqiang,et al.An improved segmentation approach for planar surfaces from unstructured 3D point clouds[J].The photogrammetric record,2010,25(129): 5-23.

[4] MARTINEZ J,SORIA-MEDINA A,ARIAS P,et al.Automatic processing of Terrestrial Laser Scanning data of building facades[J].Automation in construction,2012,22: 298-305.

[5] DEMANTKE J,MALLET C,DAVID N,et al.Dimensionality based scale selection in 3D lidar point clouds[J].ISPRS Workshop on Laser Scanning 2011: 29-31.

[6] YANG Bisheng,DONG Zhen.A shape-based segmentation method for mobile laser scanning point clouds[J].ISPRS Journal of Photogrammetry and Remote Sensing,2013,81:19-30.

[7] PAULY M,KEISER R,GROSS M.Multi-scale feature extraction on point-sampled surfaces[J].Computer graphics forum,2003,22(3):281-289.

[8] BELTON D,LICHTI D.Classification and segmentation of terrestrial laser scanner point clouds using local variance information[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Science,2006,36(5):44-49.

[9] 張蕊,李廣云,李明磊,等.利用PCA-BP算法進行激光點云分類方法研究[J].測繪通報，2014(7):23-26．

[10] 李孟迪,蔣勝平,王紅平,等.基于隨機抽樣一致性算法的穩(wěn)健點云平面擬合方法[J].測繪科學,2015,40(1):102-106.

[責任編輯：張德福]

An improved RANSAC algorithm based on dimension feature in 3D point cloud of buildings

LIU Chuang1,2,HUA Xianghong1,2,TIAN Mao1,2,YUAN Da1,2

(1.School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China;2.Hazard Monitoring and Prevention Research Center,Wuhan University,Wuhan 430079,China)

An improved RANSAC algorithm for complex surface shape feature in buildings is proposed in this paper.The dimension characteristics and the entropy functions are calculated,and the optimal neighborhood is determined by the criterion of the minimum value of entropy function,and the surface shape is classified.The precision of the classification result is improved by the angle of the normal vectors.Models are selected in random sampling (RANSAC) algorithm based on the classification results,then the surfaces of building are segmented.The more precise surfaces are segmented by the normal vector and distance constraints.Experiment shows that the improved RANSAC algorithm is feasible,and the surface characteristics can be effectively kept.

dimension characteristic; entropy function; point cloud data; surface shape of buildings; improved RANSAC algorithm

引用著錄：劉闖,花向紅,田茂，等.基于維度特征的RANSAC建筑物點云分割算法[J].測繪工程，2017，26(1)：64-68.

10.19349/j.cnki.issn1006-7949.2017.01.014

2015-07-10

長江科學院開放研究基金資助項目(CKWV2014217/KY)

劉闖(1991-)，男，碩士研究生.

P207

A

1006-7949(2017)01-0064-05