賀亦峰,胡 榮,鄒進(jìn)貴

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

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

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

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

1 三維激光點(diǎn)云立面分割算法

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

1.1 基于歐氏聚類的點(diǎn)云分割

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

(1)

1.2 基于區(qū)域增長(zhǎng)的點(diǎn)云分割

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

1.3 基于RANSAC算法的點(diǎn)云分割

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

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

(2)

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

P=1-(1-εk)n

(3)

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

(4)

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

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

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

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

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

2 試驗(yàn)與分析

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

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

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

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

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

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

2.1 基于歐氏聚類的點(diǎn)云分割算法

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

圖5 歐氏聚類點(diǎn)云分割運(yùn)行耗時(shí)統(tǒng)計(jì)

圖6 歐氏聚類點(diǎn)云分割未分割個(gè)數(shù)統(tǒng)計(jì)

圖7 歐氏聚類點(diǎn)云分割過分割個(gè)數(shù)統(tǒng)計(jì)

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

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

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

2.2 基于區(qū)域增長(zhǎng)的點(diǎn)云分割

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

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

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

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

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

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

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

2.3 基于RANSAC算法的點(diǎn)云分割

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

圖13 基于RANSAC算法的點(diǎn)云分割運(yùn)行耗時(shí)統(tǒng)計(jì)

圖14 基于RANSAC算法的點(diǎn)云分割錯(cuò)誤分割個(gè)數(shù)統(tǒng)計(jì)

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

圖15 RANSAC_12 cm_100points

圖16 RANSAC_15 cm_0.2*cloud

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

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

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

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

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

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

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

3 結(jié) 語

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