基于維度特征的RANSAC建筑物點(diǎn)云分割算法

劉 闖,花向紅,田 茂,袁 達(dá)

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

?

基于維度特征的RANSAC建筑物點(diǎn)云分割算法

劉 闖1,2,花向紅1,2,田 茂1,2,袁 達(dá)1,2

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

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

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

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

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

1 基于維度特征的RANSAC點(diǎn)云分割算法

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

1.1 建筑物表面形狀的分類

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

(1)

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

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

(2)

(3)

1.2 建筑物表面形狀分割

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

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

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

(4)

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

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

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

(5)

2 實(shí)驗(yàn)與分析

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

圖1 改進(jìn)的RANSAC點(diǎn)云分割算法流程

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

2.1 表面形狀分類分析

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

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

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

圖2 掃描的建筑物點(diǎn)云

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

2.2 表面形狀分割分析

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

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

圖3 RANSAC分割結(jié)果

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

3 結(jié) 論

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

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

[2] 胡偉,盧小平,李珵,等.基于改進(jìn)RANSAC算法的屋頂激光點(diǎn)云面片分割方法[J].測(cè)繪通報(bào)，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ìn)行激光點(diǎn)云分類方法研究[J].測(cè)繪通報(bào)，2014(7):23-26．

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

[責(zé)任編輯：張德福]

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建筑物點(diǎn)云分割算法[J].測(cè)繪工程，2017，26(1)：64-68.

10.19349/j.cnki.issn1006-7949.2017.01.014

2015-07-10

長(zhǎng)江科學(xué)院開放研究基金資助項(xiàng)目(CKWV2014217/KY)

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

P207

A

1006-7949(2017)01-0064-05