基于密度噪聲應(yīng)用空間聚類算法的機載激光雷達建筑物點云提取與單體化

呂富強，唐詩華*，何廣煥，蒙金龍

(1.桂林理工大學(xué)測繪地理信息學(xué)院，桂林 541004; 2.廣西空間信息與測繪重點實驗室，桂林 541004)

隨著無人機航攝技術(shù)的發(fā)展，建筑物信息提取的方式越來越多。建筑物信息的提取為房地一體、城區(qū)改造以及智慧城市等各項建筑相關(guān)的測繪項目提供有效的幫助[1]。因此，對建筑物信息的提取具有十分重要的現(xiàn)實意義。而提取出的建筑物信息需要單體化后才能夠賦予相應(yīng)的屬性信息，滿足用戶的不同需求。對于如何快速提取建筑物信息并將其單體化，國內(nèi)外學(xué)者開展了大量研究。

目前，建筑物信息提取的類型與方法有多種，主要類型有基于影像與基于點云兩大類。提取的方法較多，如王春林等[2]引入活動輪廓的圖割算法構(gòu)建并解算輪廓能量函數(shù)來實驗建筑物輪廓信息的提取。程亮等[3]利用LiDAR、影像以及K-means 聚類方法，提取建筑物輪廓信息。李強等[4]對建筑物點云數(shù)據(jù)構(gòu)建特征規(guī)則集的方式進行建筑物點云的提取。這些方法都可以較好地提取出建筑物信息，但其目標(biāo)都是大面積的建筑物提取，沒有進行建筑物自動單體化的提取。建筑物提取后的單體化方法中，目前較為廣泛的單體化方法包括ID單體化、切割單體化、動態(tài)單體化和人工單體化4種方式。孫松梅等[5]先提取建筑物基底矢量面，再對建筑物體單體化。張紅華等[6]通過獲取垂直的圖像上的建筑物的頂部結(jié)構(gòu)，以及建筑物側(cè)面的紋理特征來使建筑物單體化。李濟坤等[7]過 Canny檢測算法獲取建筑物邊界，用DP-Modeler實現(xiàn)了建筑物單體化。吳為民[8]采用了自動 ID 單體化的方法來進行建筑物的單體化。

現(xiàn)提出一種基于密度噪聲應(yīng)用空間聚類(density-based spatial clustering of applications with noise，DBSCAN)算法的建筑物點云提取與單體化的方法，在進行建筑群提取的過程中，以航攝影像為輔助，使用DBSCAN算法對建筑物點云進行提取，并將其單體化。該方法適用于分布明顯的建筑片區(qū)，在大范圍建筑片區(qū)中也有一定的適用性。旨在提高建筑物點云自動化提取程度，提高提取效率與精度。

1 原理

1.1 DBSCAN算法原理

使用DBSCAN算法進行建筑物點云的聚類處理。DBSCAN算法是一種基于密度的空間數(shù)據(jù)聚類，可以發(fā)現(xiàn)某一密度條件下任意形狀的聚類[9-10]。

該算法首先會選取一個核心點，通過這個核心進行三維空間的生長，每個簇類都可以由該簇類的任何核心對象唯一確定。通過分析數(shù)據(jù)分布密度來生成簇類，核心點在一個空間范圍內(nèi)檢索周圍數(shù)據(jù)點，小于聚類閾值時，將范圍內(nèi)點的點歸為該集合當(dāng)中，當(dāng)密度大于某一給定的閾值，就把該集合稱為簇類，該簇類即為密度相連的點的最大集合，低密度的數(shù)據(jù)區(qū)一般認(rèn)為是噪聲。

在該算法中，三維鄰域空間的閾值參數(shù)有兩個，一個為空間上的鄰域半徑(eps)，該參數(shù)使用的是歐式距離。首先選取任意核心點，然后進行核心點的近鄰點遍歷，再進行核心點與任意臨近點之間的距離計算，判斷該距離值是否大于eps值，若該距離值大于eps值，則不屬于同一簇類點，并設(shè)置為噪聲點。若該距離值小于eps值，則將該點歸為同一簇類集合中，并再將該點設(shè)為核心點，進行相同的遍歷步驟直至無法遍歷到新的核心點，則該集合即為一個簇類，最后遍歷到的同一簇類中的點則為邊界點。另一個參數(shù)為鄰域半徑球體內(nèi)的最小點集數(shù)(minpts)，當(dāng)一個簇類中核心點數(shù)與邊界點的數(shù)量和小于minpts值時，無法達到最小點集的數(shù)量要求，則該簇類內(nèi)的點都將歸為噪聲點。若大于minpts值，則繼續(xù)聚類。該算法二維聚類的簡單過程如圖1所示。藍色的為核心點，綠色的為邊界點，黑色的為噪聲點，圓圈的半徑即為eps值的大小。圖中的藍色點與綠色點為同一簇類中的點，黑色點判定為噪聲點后另成一簇。

圖1 二維聚類原理圖

eps與minpts值的選取都有一定的規(guī)則限制。當(dāng)eps值選取過大時，會導(dǎo)致鄰域空間過大，不同類別的點集被錯誤聚類到同一簇類。而eps值選取過小時，則會導(dǎo)致同一類別的點無法聚類到同一簇類中，導(dǎo)致最后簇類集數(shù)量龐大。minpts值選取也會有一定的影響，該值設(shè)定過小時，則會使部分噪聲點集合歸之非噪聲的簇類之中。而該值選取過大時，則可能導(dǎo)致點集合中點數(shù)量較少的簇類無法進行聚類，被過多歸至噪聲點。

解決eps值的取值問題，需要用到k-距離曲線圖，計算所有點與它第k遠的點之間的距離，將結(jié)果排序后得到k-距離曲線圖，k值通常設(shè)為4，選擇該圖中第一個谷值點位置，該位置對應(yīng)的k距離值設(shè)定為eps值較為合適[11]。

minpts值的選取通常需要設(shè)定為大于數(shù)據(jù)的維度值(dim)，minpts≥dim+1時較為合適，也可以根據(jù)需求，適當(dāng)加大。

1.2 建筑物點云提取原理

1.2.1 預(yù)處理

根據(jù)DBSCAN算法的特點，DBSCAN算法具有一定的去噪效果，不需要再進行點云的去噪。但該算法基于MATLAB平臺進行數(shù)據(jù)處理時運算量較大，處理速度相對較慢。因此，需要對部分非相關(guān)點云進行剔除。除建筑物及與其貼邊相關(guān)的點云外，都屬于非目標(biāo)點云。對該部分點云采用“布料”濾波(cloth simulation filter，CSF)算法進行濾波處理，剔除地面點云，留下非地面點點云。

CSF算法將獲取的機載雷達點云數(shù)據(jù)進行反轉(zhuǎn)，由于點云數(shù)據(jù)包含(x，y，z)3個坐標(biāo)值，反轉(zhuǎn)時只需保持x、y不變，將z變?yōu)橄喾磾?shù)，即將原始點云數(shù)據(jù)坐標(biāo)變?yōu)?x，y，-z)。通過設(shè)置參數(shù)，使生成的布粒子在下降過程中，先與地面點接觸，通過分析布節(jié)點與相應(yīng)機載雷達點云的相互作用，確定粒子下降時停留的位置，確定布最后的形狀，實現(xiàn)點云濾波，完成對機載雷達原始點云數(shù)據(jù)的非地面點提取[12]，從而有效剔除點地面點點云，減小數(shù)據(jù)量。

為了進一步減小數(shù)據(jù)量與冗余，需要將已剔除大部分非相關(guān)點云的數(shù)據(jù)進行點云的抽稀。按照空間距離抽稀的方法進行等距離的抽稀。該方法是根據(jù)設(shè)置空間距離閾值進行點云的抽稀，設(shè)定兩點之間的距離，將小于該距離的點進行去除。

1.2.2 提取與單體化原理

建筑物點云的提取是基于點云密度聚類方法。采用無人機機載雷達獲得的建筑物點云，其密度遠大于其他非建筑物點云。根據(jù)這一特性，采用密度聚類的方法可以較好地提取出建筑物點云數(shù)據(jù)。

通過DBSCAN算法，設(shè)定合適的eps值與minpts值，對預(yù)處理后的點云數(shù)據(jù)進行聚類。聚類后的建筑物點云數(shù)據(jù)，每一幢樓房都會生成不同的簇類。以不同的顏色來標(biāo)識每一個簇類，并賦予每一個簇類相應(yīng)的簇類ID值，通過每幢樓房對應(yīng)的ID值，可以提取出需要的單幢建筑物點云，即實現(xiàn)建筑物點云的單體化提取。其他地物也會根據(jù)其特點進行相應(yīng)的簇類，而無法聚類的點云數(shù)據(jù)則會被判定為噪聲。

初步提取建筑物點云后，可以根據(jù)三維空間上的歐氏距離值去除噪聲。提取數(shù)據(jù)后，數(shù)據(jù)中含有其他地物簇類和建筑物相關(guān)點云的簇類。建筑物相關(guān)點云的簇類中，部分非建筑物點云與建筑物點云聚類在同一簇內(nèi)的，這些點云可能為道路點云、停車場點云和樹木點云等非目標(biāo)點云。由于這些點云與建筑物貼邊或相近，使得這部分點云與建筑物點云錯誤的聚類在一起。根據(jù)建筑物點云的墻面的密度特點，將粗略提取出來的建筑物點云進行二維聚類，可以得到明顯的邊界線，但仍然保留三維信息，將邊界線外的點云進行去除，留下邊界內(nèi)的點云數(shù)據(jù)，完成點云的分割任務(wù)。

點云分割時可能存在少數(shù)非目標(biāo)點云數(shù)據(jù)被遺漏，或存在樓房挑出部分下方的地面點數(shù)據(jù)未完全剔除，所以需要進行進一步的優(yōu)化處理，結(jié)合正射影像，通過三維的視角對數(shù)據(jù)進行檢查，主要是對建筑挑出或遮蓋部分的數(shù)據(jù)進行剔除，剔除該部分?jǐn)?shù)據(jù)后，再進行一次三維的DBSCAN算法聚類，即可得到優(yōu)化的建筑物點云數(shù)據(jù)，并賦予每一幢建筑不同的顏色與簇類ID，實現(xiàn)單體化。

1.3 精度評價方法

從建筑物點云的提取數(shù)量誤差、正確率和單體化提取出的建筑物平面邊線長度的精度誤差3個方面進行精度評定。將本文方法提取的建筑物點云與TerraScan軟件所提取出的點云數(shù)量與正確率進行比較，以人工提取的建筑物點云作為參考。再將單體化提取的建筑物輪廓邊線長度與實測數(shù)據(jù)進行比較，根據(jù)兩者誤差進行精度評定。

2 實驗與分析

將DBSCAN算法與正射影像組合使用，提取出目標(biāo)區(qū)域建筑的點云。首先使用CloudCompare軟件的布料濾波算法，對原始點云數(shù)據(jù)進行預(yù)處理。其次，使用DBSCAN算法對預(yù)處理點云進行去噪與建筑物點云的三維聚類，將建筑物點云進行初步提取。再對初步提取的建筑物點云進行二維聚類，根據(jù)建筑物點云的密度特點，將點云與正射影像相結(jié)合，進行建筑物與其他地物的點云分割，最后再進行一次三維的密度聚類，優(yōu)化出最終的建筑物點云，具體流程如圖2所示。

圖2 處理流程圖

2.1 數(shù)據(jù)預(yù)處理

實驗數(shù)據(jù)采用的是桂林理工大學(xué)博士生公寓的點云數(shù)據(jù)，使用CloudCompare軟件進行預(yù)處理。采用CSF算法進行地面點的剔除，采用空間抽稀法進行點云的抽稀，空間中兩點的距離為1 m，預(yù)處理后的點云數(shù)據(jù)如圖3所示?？梢钥闯?，數(shù)據(jù)中存在大量非建筑物點云，在后續(xù)處理中，需要進行去除。

圖3 預(yù)處理后的點云圖

2.2 建筑物點云初步提取

基于MATLAB平臺，對預(yù)處理后的數(shù)據(jù)進行初步提取。將eps值按照k距離圖肘部值進行選取，如圖4所示。

圖4 k距離曲線圖

根據(jù)k-距離曲線圖可得，eps值選取為1.3～1.4 m最佳。將minpts值設(shè)定為4，eps值選取為1.3、1.35和1.4 m 3個值，進行數(shù)據(jù)測試后可得到各個eps值的聚類結(jié)果，將3個聚類結(jié)果進行對比，如圖5所示。

圖5 初步聚類

在圖5中，除建筑物點云簇類與噪聲點外，均歸至其他地物簇類。從運行結(jié)果圖與簇類數(shù)量比較得出，當(dāng)eps=1.3 m時，噪聲點數(shù)量較多，簇類數(shù)量為107個，數(shù)量較多，聚類效果欠佳；當(dāng)eps=1.35 m時，噪聲點數(shù)量正常，簇類數(shù)量為86個簇類，僅有少部分非建筑物點云歸至建筑物點云；當(dāng)eps=1.4 m，噪聲點較少，但其聚類過度，簇類數(shù)量為77個，使許多非建筑物點云數(shù)據(jù)與建筑物點云歸為同一簇。將該結(jié)果的噪聲點去除，導(dǎo)出簇類結(jié)果。

2.3 點云邊緣分割

將初步提取的點云數(shù)據(jù)進行二維聚類，去除非相關(guān)點。在該步驟中，建筑物點云降維后數(shù)據(jù)密集程度會遠高于其他非建筑地物，將eps參數(shù)設(shè)置為約等于抽稀間距，可以更好地將非建筑物點云與建筑物點云進行分割，在該步驟中根據(jù)k距離曲線，eps值設(shè)定為1.05 m。導(dǎo)出范圍線簇類與范圍線內(nèi)的簇類，剩余簇類全部剔除。通過該步驟可以去除掉大量非建筑物點云，二維聚類部分結(jié)果如圖6所示。

將二維聚類的結(jié)果與已制作完成的文檔對象模型(document object model,DOM)進行融合處理與分析。正射影像據(jù)有很強的直觀性，將兩者進行疊加分析，檢查范圍線與正射影像重合情況，并結(jié)合二維聚類結(jié)果，去除與范圍線簇類錯誤聚類的非建筑物點云。則范圍線內(nèi)的即基本為建筑物點云，處理結(jié)果如圖7所示。

2.4 優(yōu)化處理

將分割后的點云數(shù)據(jù)再次使用DBSCAN算法進行三維聚類與單體化處理，對聚類結(jié)果進行優(yōu)化，除去極少數(shù)點云分割時未處理完全的非建筑點云數(shù)據(jù)。采用與初步提取相同的參數(shù)，eps值設(shè)定為1.35 m，則可得到最后的建筑物點云。每一幢建筑物的點云簇類都有特定的簇類ID，根據(jù)需求，按照相應(yīng)的簇類ID導(dǎo)出，即可實現(xiàn)建筑物點云單體化，整體優(yōu)化結(jié)果如圖8所示。根據(jù)1#樓房的簇類號，提取出其單體化點云數(shù)據(jù)，處理前后的效果如圖9所示。

圖8 優(yōu)化處理結(jié)果

圖9 單體化成果

3 精度評價

將提取結(jié)果與TerraSolid軟件提取的建筑物點云數(shù)據(jù)結(jié)果進行數(shù)量與正確率的比較，提取1#建筑物單體數(shù)據(jù)的各邊長值與實際測量得到的邊長值進行比較進行定量的分析。TerraScan提取出的建筑物點云如圖10所示。

圖10 TerraSolid提取結(jié)果

從TerraSolid所提取出的結(jié)果看，該軟件提取出的建筑物點云底部點云缺失較多，但其建筑物上半部分的提取效果較好。

以人工提取出的建筑物點云作為參考，進行兩種提取方法的對比分析。人工提取出的建筑物點云數(shù)量共12 598個。兩種提取方法的獲取點云數(shù)量與正確率如表1所示。

由表1可知，Terrascan軟件建筑物點云提取的正確率為56.52%，而采用本文方法提取的正確率為97.36%。由此可得，本文方法總體分類精度高于采用Terrascan 分類方法。

表1 數(shù)量正確率比較

將1#建筑物點云單體化提取出的建筑物輪廓邊界與實際測量得到的數(shù)值進行比較，如表2所示。

表2 邊長比較

由表2可知，通過本文方法提取，每幢建筑物邊長值最大誤差為0.17 m，平均絕對誤差為0.055 m，中誤差為0.077 m。說明本文方法對建筑群的點云提取與建筑物點云單體化提取結(jié)果均能滿足相關(guān)規(guī)范要求。

4 結(jié)論

針對機載激光雷達建筑物點云提取過程中自動化提取困難，以及提取后的建筑物點云單體化過程煩瑣等問題，利用DBSCAN算法進行提取與單體化，結(jié)論如下。

(1)使用DBSCAN算法與正射影像的組合使用，可以有效地對建筑物點云與其他地物點云進行分割。

(2)利用本文方法，提取出的點云正確率可以達到97.36%，建筑物平面邊界長度精度可以達到厘米級。

(3)利用本文方法對建筑物點云進行提取與單體化，使建筑物點云數(shù)據(jù)的提取處理效率提高，使提取與單體化過程更加快速與簡便，并得到符合規(guī)范的數(shù)據(jù)成果。

由于該提取方法中點云的聚類與點云的分割與實際無人機采集數(shù)據(jù)的精度有關(guān)，且點云數(shù)據(jù)量較大，數(shù)據(jù)處理需要一定的設(shè)備要求。因此，提高提取精度則必須要提高無人機的數(shù)據(jù)采集精度或采用更好數(shù)據(jù)處理設(shè)備。另外，該算法是基于密度的聚類方法，無人機所采集的點云數(shù)據(jù)在建筑物密集程度較大的區(qū)域，每幢建筑相鄰墻面的點云數(shù)據(jù)密度大小不夠，在該部分單體化提取效果可能會相比于墻面間距稍大的建筑群的點云數(shù)據(jù)提取效果稍差。在后續(xù)的研究中，將對此進行下一步的改進。