賀亦峰,胡 榮,鄒進貴

(1. 武漢大學(xué)測繪學(xué)院，湖北 武漢 430079； 2. 文華學(xué)院，湖北 武漢 430074)

隨著“智慧城市”建設(shè)的普及，尤其是車載激光掃描技術(shù)的迅速發(fā)展與應(yīng)用[1-3]，三維激光掃描技術(shù)已成為空間數(shù)據(jù)獲取的一種重要技術(shù)手段[4]，但大場景的三維點云數(shù)據(jù)量大，人工處理數(shù)據(jù)效率低下[5]，如何快速高效地將大量的點云數(shù)據(jù)進行重建與識別成為關(guān)鍵問題。點云分割對于目標(biāo)識別和特征重建有著直接的影響，是實現(xiàn)點云重建與識別的基礎(chǔ)。

國內(nèi)外學(xué)者提出了多種點云分割方法。一些學(xué)者利用RANSAC方法對建筑物表面點云進行提取[6]，并利用Delaunay三角網(wǎng)提取邊界點云[7]，取得了較好的效果。還有一些學(xué)者對RANSAC點云分割方法進行改進，如文獻(xiàn)[8]利用自適應(yīng)性Hough變換對點云進行分割，能高效分割采集的點云。一些學(xué)者利用平面增長算法分割點云，如文獻(xiàn)[9]利用了數(shù)據(jù)的相似性，這種算法受到種子平面的限制。文獻(xiàn)[10]提出了一種多樣性的區(qū)域增長算法，利用一種不規(guī)則三角網(wǎng)描述平面的基本特征，通過比較相鄰三角形的關(guān)系式去融合三角形。文獻(xiàn)[11]根據(jù)平面增長算法提出了一種自動提取分割平面的算法，在這種方法中結(jié)果受參數(shù)影響較大。

點云分割如何在精度和速度間找到平衡是一個重要的問題。本文使用多種經(jīng)典分割方法進行點云分割并比較分割精度、效率及適用范圍，在此基礎(chǔ)上提出一種新的分割方法，在建筑物立面點云分割上取得較好的效果。

1 三維激光點云立面分割算法

點云分割是將屬于同一平面的點云分割出來。目前常見的點云分割方法有：基于歐氏聚類的點云分割算法、基于區(qū)域增長的點云分割算法、基于RANSAC的點云分割算法。在這幾種算法基礎(chǔ)上，本文提出一種結(jié)合RANSAC和歐氏聚類的點云分割算法，并在試驗過程中取得了較好的分割效果。

1.1 基于歐氏聚類的點云分割

歐氏聚類方法是以歐氏距離為參考依據(jù)進行聚類的一種方法[12]，它利用KD-tree對點云進行分割，歐氏空間中的一個3D平面：Ax+By+Cz+D=0。在點云集合中取點Pi(xi,yi,zi)，則Pi到該平面的距離可以表示為

(1)

1.2 基于區(qū)域增長的點云分割

區(qū)域增長算法將每一塊區(qū)域作為處理對象，主要參考區(qū)域內(nèi)和區(qū)域間的異同關(guān)系，能夠較好地區(qū)分出圖像中的區(qū)域邊界。區(qū)域增長算法的基本思想是將具有相似性質(zhì)的點云集中起來構(gòu)成區(qū)域，該方法需要先選擇一個種子點，然后依次將種子點云周圍的相似點合并到種子點云所屬的區(qū)域中[13]。

1.3 基于RANSAC算法的點云分割

隨機抽樣一致性(random sample consensus，RANSAC)于1981年由Fischler和Bolles最先提出[14]。它是一種穩(wěn)健的模型參數(shù)估計算法，可根據(jù)一組包含異常數(shù)據(jù)的樣本數(shù)據(jù)集計算出數(shù)據(jù)的數(shù)學(xué)模型參數(shù)，得到有效的樣本數(shù)據(jù)[15]。

當(dāng)點云中的誤差點數(shù)為Nn，不正常的點數(shù)為Ne時，n全部是不正常的點的情況為

(2)

為了在三維激光點云中選擇合適的點必須提高迭代的次數(shù)，當(dāng)最小的選取點數(shù)為n時，取得良好的抽樣子集的概率P應(yīng)滿足

P=1-(1-εk)n

(3)

式中，ε為沒有誤差的點在總的點云數(shù)中的比值；k為模型參數(shù)解算過程中所需要的最小的數(shù)據(jù)；P的取值范圍在0.9～0.99之間。因此可以得到

(4)

判斷迭代是否繼續(xù)進行的條件為：①在當(dāng)前迭代的點數(shù)多于最佳擬合平面的點數(shù)時，將最佳擬合平面的點替換為當(dāng)前點；②在當(dāng)前點數(shù)量與最佳擬合平面點數(shù)量相同且當(dāng)前點閾值較小時，將最佳擬合平面的點替換為當(dāng)前點。

1.4 RANSAC與歐氏聚類結(jié)合的點云分割

基于歐氏聚類的點云分割得到的分割主要是由點到分割面的閾值d0作為判斷依據(jù)的，當(dāng)閾值較大時會呈現(xiàn)一大片點云為一個分割面，而當(dāng)減小分割閾值后，雖可以將明顯的分割面分離開來，但又極易將同一層面的點云分成多類點云。與基于歐氏聚類的點云分割算法相比，基于RANSAC的點云分割效果可控因素較多，通過設(shè)置合適的閾值可以較好地分割建筑物立面點云，但該算法也存在部分誤分割現(xiàn)象，且不能將每塊窗戶分割開來。

因此，本文提出一種結(jié)合RANSAC與歐氏聚類的點云分割算法。首先使用RANSAC算法對點云進行粗分割，得到大面積的點云立面，即墻面和窗沿，而對于剩下的點云數(shù)據(jù)，利用歐氏聚類算法進行分類，設(shè)置較大的歐氏距離閾值，可以較好分割出窗戶元素。該算法的流程如圖1所示。

圖1 結(jié)合RANSAC與歐氏聚類的點云分割流程

2 試驗與分析

掃描建筑物立面得到原始的三維激光點云數(shù)據(jù)(如圖2所示)，為了提高后期分割的效率，需要提前對原始數(shù)據(jù)作預(yù)處理。首先剔除干擾點云，原始點云數(shù)據(jù)總量為658 023，經(jīng)過點云剔除后剩余點云數(shù)量為251 109(如圖3所示)。數(shù)據(jù)剔除以后點云整體效果更整齊，更便于分割處理。隨后對經(jīng)過剔除以后的點云數(shù)據(jù)濾波去噪，去噪后點云數(shù)量為71 343(如圖4所示)。

圖2 原始點云數(shù)據(jù)

圖3 點云剔除后點云數(shù)據(jù)

圖4 濾波去噪后點云數(shù)據(jù)

點云數(shù)據(jù)預(yù)處理后采用基于歐氏聚類的點云分割、基于區(qū)域增長的點云分割、基于RANSAC的點云分割、結(jié)合RANSAC和歐氏聚類的點云分割4種算法對預(yù)處理后的點云數(shù)據(jù)進行分割，通過C++編程實現(xiàn)點云分割。其中，基于歐氏聚類的算法在點到聚類面的距離的閾值選擇上很難取到一個能直接將窗戶、墻面、窗沿等區(qū)分開的值。而RANSAC算法進行點云分割可以通過類似于深度值的參數(shù)較好地分割窗戶、墻面、窗沿，但無法將窗戶之間分割開來，且存在大量點云未被處理。由此提出一種新的點云分割算法，首先用RANSAC算法粗分割點云，再用歐氏聚類方法分割獨立的窗戶元素。

對上述幾種點云分割算法進行多次試驗，試驗平臺為Windows10 64位系統(tǒng)，主要硬件配置為Intel core i7-4720HQ，12 GB內(nèi)存。設(shè)置不同閾值，統(tǒng)計各種算法的精度和運行耗時。

2.1 基于歐氏聚類的點云分割算法

基于歐氏聚類的點云分割結(jié)果主要由點到聚類面的距離閾值決定，設(shè)置該距離閾值分別為7、8、9、10 cm，每一個距離測試兩次(分別讓最小點云數(shù)量為50和100)，統(tǒng)計試驗用時、未分割個數(shù)和過分割個數(shù)，如圖5—圖7所示。

圖5 歐氏聚類點云分割運行耗時統(tǒng)計

圖6 歐氏聚類點云分割未分割個數(shù)統(tǒng)計

圖7 歐氏聚類點云分割過分割個數(shù)統(tǒng)計

當(dāng)閾值增大時，程序運行時間緩慢增加。精度方面，未分割數(shù)量會顯著增加，過分割個數(shù)隨著閾值增加而較少，這是由聚類數(shù)量減少導(dǎo)致。由分析結(jié)果可以看出，很難控制歐氏距離的閾值得到理想的分割結(jié)果，該分割方法只有當(dāng)待測物為分離較遠(yuǎn)的幾個獨立物體才適合使用。距離閾值為7和10 cm時的分割結(jié)果分別如圖8、圖9所示。

圖8 歐氏聚類(閾值7 cm)

圖9 歐氏聚類(閾值10 cm)

2.2 基于區(qū)域增長的點云分割

本試驗設(shè)置平面包含的最小點數(shù)為50，設(shè)置法向量估計中最鄰近點數(shù)為50、40、30、20、10，設(shè)置參考鄰域點數(shù)為5、10、15、20、30，設(shè)置法線夾角閾值為3°、5°、7°、10°、15°。默認(rèn)參數(shù)為：法線估計最鄰近點30，參考鄰域點15，法線夾角閾值7°。該算法若不將點云先進行濾波處理，區(qū)域增長算法處理噪聲很慢，運行時間會達(dá)到30 min以上，故在分割前進行濾波處理去除噪聲。統(tǒng)計不同參數(shù)下的運行耗時、未分割個數(shù)和過分割個數(shù)見表1。

表1 基于區(qū)域增長的點云分割不同參數(shù)下用時及精度分析

由表1可知，閾值越大耗時越短，而閾值若設(shè)置過大會導(dǎo)致分割不完全。參數(shù)閾值下的錯誤分割數(shù)量呈現(xiàn)拋物線趨勢，這是由于在閾值很小時很多點云數(shù)據(jù)被識別成噪聲，未分割較多，過分割很少(如圖10所示)。而當(dāng)閾值過大時，分割數(shù)少，未分割數(shù)也會增加，過分割少(如圖11所示)。在閾值取到適中時分割效果最好，此時噪聲數(shù)量較少，未分割較少，過分割不多，如圖12所示。

圖10 分割結(jié)果(閾值過小時)

圖11 分割結(jié)果(閾值過大時)

圖12 分割結(jié)果(閾值適中時)

可以看出，基于區(qū)域增長的點云分割算法適用于小曲率變化曲面，尤其適合對連續(xù)階梯平面進行點云分割，如利用SLAM算法生成的建筑走廊等。

2.3 基于RANSAC算法的點云分割

基于RANSAC的點云分割效果由點到平面的距離的閾值和聚類面最小點云數(shù)量決定。本試驗將距離閾值設(shè)為5、7、10、12、15 cm，將迭代條件中剩余點云數(shù)量設(shè)為100個點和全部點云的20%兩種。比較分析分割效果并統(tǒng)計，如圖13、圖14所示。

圖13 基于RANSAC算法的點云分割運行耗時統(tǒng)計

圖14 基于RANSAC算法的點云分割錯誤分割個數(shù)統(tǒng)計

剩余點云數(shù)量閾值越大，距離閾值越大，運行時間越短。精度方面，在閾值不超過12 cm時，大部分點云可以被識別(如圖15所示)，而當(dāng)閾值達(dá)到15 cm和0.2倍點云，會導(dǎo)致大量窗戶內(nèi)部元素未被處理而產(chǎn)生空白，如圖16所示。

圖15 RANSAC_12 cm_100points

圖16 RANSAC_15 cm_0.2*cloud

基于RANSAC的點云分割算法可以較好地提取出建筑物立面點云，但該方法并不能將每塊窗戶分割開來，也存在一些誤分割。

2.4 結(jié)合RANSAC和歐氏聚類的點云分割

本文提出一種結(jié)合RANSAC和歐氏聚類的點云分割方法，首先用RANSAC對點云進行粗分割，再使用歐氏聚類的方法細(xì)分割。本次試驗分別將RANSAC算法深度值閾值設(shè)為5、7、10、12、15 cm，平面最小點云數(shù)量為總數(shù)量的0.3、0.35、0.4、0.45、0.5，點到平面歐氏距離閾值為5、7、10、12、15、18、20、25 cm。記錄統(tǒng)計運行耗時和錯誤分割數(shù)，默認(rèn)參數(shù)為10 cm、0.4倍點云、10 cm，見表2。

表2 結(jié)合RANSAC和歐氏聚類的點云分割在不同參數(shù)下的用時及精度分析

參數(shù)設(shè)置運行耗時/s錯誤分割數(shù)/個RANSAC中深度距離閾值/cm511827130131011501211421510718RANSAC中最小平面點數(shù)占總點云的比例0.3120230.3511600.411500.4510710.51071歐氏聚類中歐氏距離閾值/cm5110357109351010916121123151122181150201180251220

由表2可得，閾值變化對運算用時并不明顯，整體運行耗時短，與RANSAC算法分割速度接近。從精度來看，該方法可以零錯誤地分割出立面點云。當(dāng)利用RANSAC算法進行粗分割時設(shè)置深度閾值10～12 cm，最小平面點數(shù)大于0.35倍點云，可以較好地提取出墻面及窗沿，再利用歐氏聚類點云分割取較大歐氏距離閾值分割出窗戶，得到較好的分割效果，分割結(jié)果如圖17所示。

圖17 結(jié)合RANSAC與歐氏聚類的點云分割(深度10 cm，最小平面點0.4倍點云，歐氏距離25 cm)

3 結(jié) 語

本文對多種點云分割方法進行研究，對不同方法分割出的點云結(jié)果進行精度評定，根據(jù)不同的分割結(jié)果得出不同分割方法的適用條件。從運算耗時角度來看，歐氏聚類算法最快，區(qū)域增長算法耗時最長。從適用性角度分析，歐氏聚類的點云分割算法適用于分割分離的物體，區(qū)域增長方法分割點云適合小曲率變化曲面的分割，RANSAC算法適合不同層面的點云數(shù)據(jù)分層。在此基礎(chǔ)上，本文提出了一種結(jié)合RANSAC和歐氏聚類的點云分割算法，運算耗時較快，相比幾種傳統(tǒng)點云分割算法，可以較好地分割出建筑物立面點云。