改進區域增長和RANSAC由粗到精的建筑物分割方法

劉 建 興

(江西省核工業地質調查院，330038，南昌)

0 引言

機載激光雷達(Airborne Light Detection And Ranging, LiDAR)已經成為構建智慧城市獲取三維地理空間數據不可或缺的工具之一，并且在建筑物提取[1]、城市變化檢測[2]、城市三維建模[3]等取得了廣泛的應用。建筑物作為構建智慧城市最主要、最基本、最重要的組成部分，建筑物三維建模儼然已經成為當前研究的一個熱點。建筑物是由多個屋頂面片構成的，如何快速、精確地對建筑物屋頂面分割是三維建模必要的步驟。

近幾十年來，許多的學者對屋頂面分割進行了很多深入的研究，他們的研究大致可以分為兩類：特征聚類法、模型驅動法。特征聚類法主要方法有區域增長算法及其變種[4]、K-means[5]、DBSCAN[6]等。如Sampath等[5]使用K-means從非地面點中分割建筑物，提取建筑物屋頂面片。周欽坤等[7]通過主成分分析計算點云可靠性指標，利用k-means算法利用法向量進行聚類提取建筑物屋頂面。Xu等[8]提出一種改進DBSCAN的平面分割算法，該方法使用自適應的閾值改進DBSCAN算法，然后使用法向量精細化分割平面。這類方法是首先計算點云的特征，如法向量、曲率、密度等特征，然后根據相似性進行分割數據。這類方法在特征計算準確的時候，能夠有著較好的分割結果，但是局限性也正是在這里，很多時候需要依賴點搜索鄰域值的設定，同時這類方法對噪聲非常敏感。

模型驅動法主要是隨機采樣一致性(Random Sample Consensus，RANSAC)和Hough變換(Hough Transform，HT)。如艾效夷等[9]使用3D Hough變換從機載LiDAR數據中提取平面特征。章大勇等[10]利用以3D Hough變換基礎，加入了參數空間的對偶性，提出了一種基于對偶空間分割的三維Hough 變換算法，進行點云平面地標的提取。李娜等[11]引入角度、距離約束使用RANSAC算法對建筑物立面進行提取。何明等[12]使用形態學濾波改進RANSAC算法從點云中提取平面。周嘉俊等[13]提出了使用高差閾值來改進RANSAC算法來進行建筑物平面的提取。這2種方法利用平面數學模型進行屋頂面片的提取，其對噪聲和異常值具有穩健性，可以同時得到優化后的屋頂面片模型參數，但是這類方法對分割參數的設置非常敏感，容易得到偽平面，且算法耗時長。

針對上述方法所存在的問題，本文基于5種不同復雜程度的建筑機載點云數據，提出了一種結合改進區域增長和RANSAC由粗到精的建筑物分割方法。該方法首先基于LRSCPK計算點云法向量，然后利用最小曲率區域增長算法進行屋頂面粗分割，最后利用RANSAC進行小平面的分割和屋頂面的優化。

1 方法

本文方法主要包括3個步驟，點云預處理、屋頂面粗分割、屋頂面精分割，具體的分割流程如圖1所示。LiDAR數據是采用有人機搭載Leica ALS60激光雷達掃描系統獲取的某城區點云數據，然后通過Leica CloudPro軟件進行點云解算與誤差檢校。

圖1 屋頂面分割流程

1.1 預處理

預處理的目的是將LiDAR數據中建筑物屋頂點云提取出來。目前國內外針對從機載LiDAR數據中提取建筑物的問題已經進行了大量的研究。本文采用文獻[1]提出的反向迭代數學形態學(RIMM)算法進行建筑物點云的提取，該算法相較于著名的點云數據處理軟件Terrasoild中傳統的建筑物點云提取算法更為方便，該方法不需要對LiDAR數據進行濾波處理，且參數設置更為簡單，該方法不需要設置窗口大小閾值，只需要設定一個高程差閾值，后續窗口大小閾值與高程差閾值在迭代過程中自動計算。進行建筑物提取之后，將建筑物劃分格網投影至二維圖像，存在點云數據的格網對應賦值為1，反之賦值為0，最后生成一張二值圖。之后再進行連通性分析，實現建筑物點云的單體化分割。

1.2 屋頂面粗分割

1.2.1 基于LRSCPK的法向量計算 法向量是描述屋頂面中一個重要的特征，在分割屋頂面中起著至關重要的作用。許多的算法中都需要計算點云的法向量，所以某種程度上來說法向量計算的好壞也會影響到數據處理的精度。目前，應用最廣泛的法向量計算方法主要是主成分分析法(principle component analysis，PCA)，但是該方法計算出來的法向量在面片交界處并不準確(如圖2)，所以在進行屋頂面分割的時候，在屋脊線附近數據不能準確劃分[14]。

(a)PCA法向量計算

(b)LRSCPK法向量計算圖2 法向量估算對比示意圖

針對這個問題，本文采用一種具有先驗知識的低秩子空間聚類框架的法向量估算方法(low-rank subspace clustering framework with prior-knowledge, LRSCPK)[15]，該方法在將主成分分析法估算的法向量作為先驗知識進行領域聚類，然后利用引導矩陣(式(1))的低秩子空間聚類將各向異性鄰域分割成幾個各向同性鄰域，并為當前點識別一致的子鄰域。最后將擬合一致子鄰域的平面的法線作為當前點在尖銳特征附近的法線。

min‖Z‖*+β‖PΩ(Z)‖1+γ‖E‖2,1

(1)

式中：‖·‖*表示奇異值之和，‖·‖2,1表示范數之和，Z是向量矩陣，Ω是引導矩陣(guiding matrix)，E是融合約束條件，β和γ是2個參數，文獻[15]中設置為1。

1.2.2 最小曲率區域增長法 在估算出點云穩健的法向量之后，本文采用PCL庫中區域增長算法(Region Growing，RG)進行建筑物屋頂面的分割。該算法主要思路是對點云按照曲率值進行排序，將最小曲率值作為種子點開始增長，直到沒有標記的點為止。詳細步驟如下。

1)輸入單棟建筑物點云數據及其法向量n和曲率c，設置曲率閾值cth、法向量夾角閾值θth、搜索鄰域點數目k，根據曲率從小到大進行排序生成隊列VP，將最小曲率值作為初始種子點，初始標記為0。

2)對于每個種子點，若該點標記不為-1，則初始化一個種子點隊列SC,利用Kd-tree找到它的相鄰點{BC}，依次遍歷{BC}，逐一計算相鄰點與種子點的曲率閾值cth和法向量夾角閾值θth，將符合條件的點添加到隊列SC中且進行標記。

3)遍歷種子點隊列SC，重復步驟2)直至隊列SC為空。

4)再次從隊列VP中查找種子點，重復步驟2)、3)直到遍歷完隊列VP。

1.3 屋頂面精分割

1.3.1 RANSAC分割小面片 在進行區域增長之后，大面積的屋頂面片基本會分割出來，但是還存在一部分小面積的屋頂面片不能分割出來，同時一些變化角度小的屋頂面片區域增長算法也不能識別。針對這兩點問題，采用RANSAC算法對上一步分割后的結果進行優化。具體步驟如下。

1)上一節方法分割后數據可以分為兩類：分割出的數據集{Ri}和分割后留下的數據Q，遍歷數據集{Ri}，利用RANSAC進行屋頂面片分割，確定分割出的數據為單個平面數據；反之，則將其分割成多個面片，將提取的面片數據添加到面片集{Pi}中。

2)遍歷的面片集{Pi}，利用點到平面的距離從數據Q中將符合條件的點添加至該集合。

3)利用RANSAC算法從分割后的數據屋頂面片分割，將小面積的屋頂面片分割出來，將其加入面片集{Pi}，直到平面分割完成，輸出面片集{Pi}。

1.3.2 屋頂面優化 通過前面的步驟中基本能夠將數據中屋頂面片全部分割出來，但是可能分割出來的數量會比真實的屋頂面片數量多，還需要進行屋頂面合并工作。由于上一步已經獲取到每個平面的參數方程，可以通過平面的法向量和距離來進行合并屋頂面。具體步驟如下。

1)遍歷面片集{Pi}，依次計算Pi與集合中其他面片的法向量夾角，如果存在Pj與Pi法向量夾角小于閾值，則進入步驟2。

2)計算面片Pj與Pi之間的距離，如果距離小于閾值，則同時標記面片Pj與Pi，將這2個面片合并成一個面片添加至面片集{Pi}out，。反之則標記面片Pi，將添加到面片集{Pi}out。

3)繼續遍歷面片集{Pi}，直至所有面片標記完成，輸出{Pi}out將其作為最終分割結果。

2 實驗結果與分析

2.1 數據與評價標準

為了驗證本文方法的有效性與適用性，本次實驗數據選取T字型建筑物、人型建筑、復雜建筑等具有代表性的建筑物(數據詳細描述見表1)。本文實驗的硬件環境：Intel(R)CoreTMi7-11800H處理器、16G內存，軟件環境：Visual Studio2015 C++和PCL1.8.1(Point Cloud Libary)。同時將本文算法分割結果與RANSAC[16]、區域增長[17]進行對比分析。本文以舒敏等[14]人的研究成果，不斷調整算法參數進行試驗，最終確定參數如下：搜索鄰近點數目為20，區域增長法向量夾角閾值θth為0.03°，曲率閾值cth為0.1，屋面優化中點到面的距離為0.1 m。

表1 代表性建筑物相關信息

為了定量地評價屋頂分割結果，本文采用文獻[18]的方法與人工分割結果對比，計算分割后的屋頂面的完整性(Comp)、正確性(Corr)和質量(Quality)來評估分割點結果：

(2)

其中：TP(True Positive)是指分割結果中發現的真實平面數值，FN(False Negative)是指分割結果中發現的錯誤平面數值，FP(False Positive)是指分割結果中未發現的平面數值。

2.2 結果分析與評價

本文了利用3種不同方法對5棟具有代表性的建筑物點云數據進行了分割，其結果如圖3所示。圖3中原始數據按高程進行著色，其中白色實線為建筑物屋脊線(參考分割線)。

圖3 分割結果對比

在屋頂面片法向量夾角較小的建筑物上，如B1對應的分割結果，可以發現區域增長算法可能會存在2個屋頂面無法區分的情況；本文算法與 RANSAC算法卻能夠較好地分割。在常見的T型建筑物中，3種算法都能夠比較好地對建筑物進行分割，但是在細節方面，本文的算法分割效果更好，B2中紅色方框部分，由于數據法向量之間的角度偏差較小，區域增長算法和RANSAC算法將其分割為同一屋頂面數據。在規則對稱的數據上，如B3對應的分割結果，可以發現區域增長算法和RANSAC算法能夠很好地將面積較大的屋頂面分割出來，但是在較小的屋頂面卻不能較好地完成分割，本文算法卻能夠較好地將這部分小面積的屋頂面分割出來，但是對于較小的煙囪，這部分數據量較少，也不能進行分割。在人型建筑物較多且屋頂面片法向量夾角較小的建筑物上，如B4對應分割結果，區域增長算法與本文算法分割效果都較好，但是RANSAC算法會存在分割錯誤的情況。對于屋頂面多且大小不一的復雜建筑物，如B5對應的分割結果，區域增長算法能夠較好地分割出面積較大的屋頂面，對于面積較小的屋頂面則會失敗，但是本算法卻能夠很好地將這一部分分割出來。

總的來說，與區域增長算法相比，在夾角較小的屋頂面上，區域增長算法可能會分割失敗，將其識別為同一個平面，如B1和B5所示，由于本算法能夠精確計算每個點多法向量，能夠精確地分割屋頂面，也能夠為每個屋頂面分割得到更多的點。針對小范圍的屋頂面數據，還利用RANSAC對區域增長后數據進行了優化，也能夠精確到將這部分分割出來。與RANSAC算法相比，RANSAC可能會存在屋頂面競爭的問題，如B3分割后效果所示，由于該算法需要隨機采樣確定起始平面，這樣先分割的屋頂面會將其他屋頂面的數據分割到該平面中，造成局部錯誤分割，而本方法是先進行區域增長，再利用RANSAC算法對區域增長后的數據進行優化，由于分割后數據一般只存在1個或者2個屋頂面，這時候就能減少許多屋頂面競爭的問題。

為了定量評估不同方法的屋面風格性能，以屋頂面為單元統計了分割的完整性(Comp)、正確性(Corr)和質量(Quality)，如表2所示。

表2 精度對比

由表2可知，從整體上來看，本文方法分割相較于區域增長算法和RANSAC算法有著較好的分割效果，完整性、正確性、質量的平均值分別為：100%、94.6%、94.6%。反觀區域增長和RANSAC算法在完整性、正確性、質量的平均值數值均不高，分別為：84.9%/84%、70.2%/63.6%、65.2%/60.2%。從細節上來看，本文算法在B1、B3、B4數據上能夠達到100%的完整性、正確性、質量，對于B2、B5中存在著點云數目較小的人型煙囪，完整性還是100%，但是正確性和質量分別為77.8%和95.2%，這是數據本身缺陷造成的。區域增長和RANSAC算法在單個數據集上并未有很好的表現。

3 結束語

本文提出了一種結合改進區域增長和RANSAC由粗到精的建筑物分割方法。該方法首先基于LRSCPK計算點云法向量，然后利用最小曲率區域增長算法進行屋頂面粗分割，最后利用RANSAC進行小平面的分割和屋頂面的優化。試驗表明，所提出的方法能夠有效地分割不同程度的復雜建筑物，且在小面積的屋頂面有著較好的分割效果。本文的方法未能考慮到精分割中RANSAC分割小面片中相鄰面片可能會存在面片競爭的情況，這也是下一步研究需要優化改進的地方。同時由于機載LiDAR對建筑物側面信息的獲取能力有限，本文方法未應用于建筑側面點云數據分割，下一步可考慮通過多源點云數據進行融合，獲取空地一體化建筑點云進行建筑物分割。