基于區域生長算法的復雜建筑物屋頂點云分割

朱軍桃，王 雷，趙 傳，鄭旭東

(1.桂林理工大學測繪地理信息學院，桂林 541006；2.廣西空間信息與測繪重點實驗室,桂林 541006；3.信息工程大學地理空間信息學院，鄭州 450001)

0 引言

隨著機載激光雷達(light detection and ranging,LiDAR)測量技術的不斷突破，其應用前景廣為人們關注。利用高密度的LiDAR數據構建3D城市模型相比于影像匹配更加容易，而對城市中的建筑物進行模型重建無疑需要對復雜的建筑物屋頂進行精細化分割。由于復雜建筑物的屋頂存在較多大小不一的面片，其點云分布散亂且存在噪聲等問題，使現有算法在精確分割建筑物屋頂面時仍面臨著嚴峻挑戰。

對建筑物屋頂點云進行分割方法主要包括3類：①基于模型匹配的算法，由于實際中建筑物往往包含多個頂面，隨機采樣一致性算法(random sample consensus,RANSAC)[1-3]以迭代的方式從含有大量局外點中獲得最優的模型參數從而受到廣泛關注，但局外點所占比例往往需要以很高迭代次數才能獲得最優模型參數，導致時間成本巨大，不利于對復雜建筑物的屋頂面點云分割；②基于特征聚類的算法[4-5]，此類方法通過采樣點鄰域計算出采樣點微分幾何屬性，幾何屬性的估算受采樣點鄰域大小以及測量誤差影響，同時其閾值敏感性高，若設置不當就會造成建筑物屋頂面分割效果不理想甚至分割失敗；③基于區域生長算法[6-8]的算法，區域生長算法可簡單描述為從某種子點開始，以種子點與鄰域內點具有某種一致關系劃分點集，其中以法向量及曲率劃分方式居多，同特征聚類方法一樣，由于單個激光點不存在矢量屬性，往往以種子點鄰域內激光點采用擬合或計算特征值等方式近似表達種子點的法向量或曲率信息等，而鄰域的選取與測量誤差會直接影響所表征點的矢量信息，種子點的生長過程中鄰近點的搜索方式同樣可能影響生長結果，此類問題導致了區域生長算法在分割建筑物屋頂點云時易產生錯誤分割，且各屋頂面交界處采樣點難以準確分割。

針對上述區域生長算法中存在激光點矢量信息需要通過鄰域估算，生長過程中鄰域點選取不當的問題，本文提出一種以三角面為基元的基于區域生長算法的復雜建筑物屋頂點云分割算法。通過構建Delaunay三角網的方式，將屋頂面點云劃分至不規則三角網內,以區域生長算法劃分各三角面，避免了各激光點逐點進行矢量估算和鄰域點選取問題；然后合并各過度劃分的面片集合及孤立點，完成對建筑物屋頂面點云的精確分割。

1 研究方法

1.1 面片劃分

對于沒有任何拓撲信息的點云[9]，Delaunay三角網以最鄰近三點形成三角形，各三角形邊互不相交的獨有優勢，無疑成為建立各激光點間關系的良好方式。本文通過構建Delaunay三角網，計算各三角面片單位法向量，并剔除邊長過長與法向量異常的三角形。通過建筑物同一面片上各三角面法向量基本相同的特征，以任意三角面作為起始種子面，其單位法向量作為判斷條件，種子面的共邊三角面作為鄰近面，計算與此三角面共邊三角面單位法向量的夾角，設置角度閾值α作為生長條件，若夾角小于α，則2個三角面屬于同一面片集合；若大于α，則停止此方向生長。采用此方式可避免逐點估算法向量與判斷鄰近關系。區域生長流程如圖1所示。

圖1 三角面為基元的區域生長流程Fig.1 Flow chart for region growing based on triangles

最終同屬相同屋頂面片內的三角面會被劃分到同一面片集合中。但測量誤差、點云散亂性分布等問題會造成諸多法向量異常的三角面。圖2為一人字形屋頂，同一面片集合中出現了異常三角面，且在2個屋頂面交界處數量明顯增加。為解決此類過度劃分問題，需要對面片集合進行合并。

(a)人字形屋頂點云 (b)三角面集合

圖2 三角面區域生長結果

Fig.2Resultofregiongrowingoftriangles

1.2 面片合并

依據以三角面為基元的方式，可以部分解決屋頂交界處法向量分布散亂問題。2個屋頂面相交處三角面的3個激光點分別屬于不同平面，由于激光點以相鄰共邊三角形為種子面的鄰近面，孤立的三角面各邊被不同面片集合所剖分，即將異常三角面上各點劃分至不同面片集合，但仍存在未被劃分的點與過度分割的面片集合。考慮到測量誤差及生長角度閾值α所造成的影響，為更精確獲得各面片平面方程，即

Ax+By+Cz+D=0，

(1)

式中A,B,C,D為系數。

采用RANSAC算法計算各面片集合的平面方程。因已經過初步劃分的點云極少含有局外點，即少量的迭代次數就能得到最優平面方程，減少時間成本。

在不考慮房屋附屬的情況下，認為激光點數量越少的集合越有可能為過度分割的平面，其中具有較大誤差點可能性越高,因此本文采取以下策略解決過度分割問題：

1)邊界獲取。采用Alpha Shape算法獲得各集合非凸邊緣，具體方法見文獻[10]。

2)孤立點合并。將構成平面最少激光點數小于3的點集作為孤立點處理，計算孤立點P到各Alpha Shape邊緣距離，若P在Alpha Shape邊緣內，距離為0；若P至最近Alpha Shape邊緣距離小于閾值Б，則計算點到平面距離L，即

(2)

設定閾值δ，若L≤δ，則將P合并至此面片集合，并更新此集合Alpha Shape邊緣；若L>δ，則將P作為噪聲點剔除。

3)面片合并。統計各面片集合激光點數量，由大到小排列，并認為激光點數量最多的集合為標準平面。計算標準面至各Alpha Shape邊緣距離，若平面在Alpha Shape邊緣內，距離為0；若距離小于閾值Б，則計算平面夾角，即

(3)

對于平面夾角閾值，若設置太大，則容易造成某些夾角小的面片過度合并；若設置太小，則容易造成過度剖分的面片難以融合。因此本文依據點集數量對閾值進行改進，計算公式為

ρr=Kρ，

(4)

(5)

式中：Nb為標準面片激光點數量；Nn為鄰近面片激光點數量；ρ為平面夾角閾值初值；ρr為最終平面夾角閾值。式(5)依據各集合激光點數量，若數量與標準面片越接近則越可能為真實屋頂面，減小閾值有利于避免過度合并；相反，增大閾值有利于合并因激光點數量少而使噪聲被放大的面片；但為了避免夾角閾值過小，設置K≥0.2。

2 實驗

2.1 實驗數據與參數

本文實驗數據來自國際攝影測量與遙感學會(International Society for Photogrammetry and Remote Sensing,ISPRS)提供的德國Vaihingen地區的機載LiDAR點云，點云平均密度約4個/m2，并使用由Yang等[11]分類的建筑物點云數據，使用CloudCompare軟件剔除分類錯誤的激光點。依據文獻[4]，法向量角度閾值α選取范圍一般為5°～10°，本文選取5°；孤立點與平面到各Alpha Shape邊界距離閾值Б應大于點云平均距離，本文選取2倍點云平均距離，為1 m；為保證孤立點與面片正確合并，孤立點到各平面距離閾值δ選取應小于點云平均距離，本文取1/2點云平均距離，設置為0.25 m；2個平面夾角閾值ρ應大于α，本文取10°。

2.2 算法對比

通過對比RANSAC算法與區域生長算法分割的建筑物點云，定量評價本文方法對建筑點云的分割效果。

(a)建筑物1影像 (b)建筑物1 (c)建筑物1 (d)建筑物1

本文方法分割結果 RANSAC分割結果 區域生長分割結果

(e)建筑物2影像 (f)建筑物2 (g)建筑物2 (h)建筑物2

本文方法分割結果 RANSAC分割結果 區域生長分割結果

圖3-1 不同算法對建筑物分割效果對比

Fig.3-1Comparisonbetweendifferentalgorithmsonsegmentationofbuildings

(i)建筑物3影像 (j)建筑物3 (k)建筑物3 (l)建筑物3

本文方法分割結果 RANSAC分割結果 區域生長分割結果

(m)建筑物4影像 (n)建筑物4 (o)建筑物4 (p)建筑物4

本文方法分割結果 RANSAC分割結果 區域生長分割結果

圖3-2 不同算法對建筑物分割效果對比

Fig.3-2Comparisonbetweendifferentalgorithmsonsegmentationofbuildings

由圖3可以看出，RANSAC算法分割建筑物點云，僅追求數學上的一致性，導致平面過度分割，如圖3(c)中框選區域；以區域生長算法分割建筑點云，在處理屋脊時處效果欠佳；而以本文方法所獲得結果均避免了上述問題。但本文方法在圖3(b)中框選處，將本應處于同一平面上的點簇劃分成2個平面；由圖3(c)和(d)可知，RANSAC算法同樣發生此問題，而區域生長算法在此處將大量屋頂面過度融合。在對建筑物2的劃分中，圖3(f)中各屋檐處存在狹窄平面，最終被劃分為主屋頂面的一部分。由此發現，本文處理狹長區域時，由于三角面法向量敏感性，容易導致三角面的關聯被異常面截斷甚至難以構成三角面，導致狹長的點簇被劃分為孤立點而被劃分到其他屋頂面上。圖3(k)框選處，存在較多誤差較大的激光點，RANSAC算法在此處分割出錯誤平面；圖3(l)中此處錯分現象更為嚴重；而圖3(j)采用本文方法未受到誤差較大的激光點干擾，正確分割了此平面，說明本文方法較RNASAC算法與區域生長算法的抗噪能力更強。

為更加準確地評價本文方法精度，采取文獻[12]的評價準則分別對本文方法、RANSAC算法與區域生長算法的分割完整率C、正確率A及分割質量Q進行評估。計算公式分別為

C=TP/(TP+FN)，

(6)

A=TP/(TP+FP)，

(7)

Q=TP/(TP+FN+FP)，

(8)

式中：TP為正確分割激光點數量；FN為漏提激光點數量；FP為錯誤分割激光點數量。

表1和表2分別為各算法的精度對比和建筑物屋頂面分割數量對比。由表1可知，采用本文方法對建筑物1，3，4的分割完整率、正確率及提取質量均在不同程度上優于RANSAC算法及區域生長算法分割方法，其中對建筑物的分割完整率明顯高于后者，由此發現采取本文分割方法有較好的抗噪能力。但建筑物2中所表現的數據，采取本文方法分割效果較差于RANSAC算法，原因是其所含狹長屋頂面較多，最終導致過多的錯誤分割。由表2可見，對建筑物4的3種方法分割結果相差無幾，隨著建筑物頂面數量增加，本文分割方法逐漸優于RNASAC算法與區域生長算法，但本文方法建筑物2所分割效果相對較差。

表1 算法精度對比Tab.1 Comparison between accuracies of algorithms (%)

表2 建筑物屋頂面分割數量對比Tab.2 Comparison between quantity of roofs of building in segmentation

3 結論

本文提出了一種以三角面為基元的基于區域生長算法的復雜建筑物屋頂點云分割算法，以構建Delaunay三角網方式構建建筑物點云之間關系，并以各三角面片單位法向量作為判別條件，依據共邊三角面單位法向量的相似性對建筑物屋頂點云進行分割。

1)本文方法避免了對各激光點進行法向量估算，且無需建立激光點間的鄰近關系，一定程度上簡化了傳統區域生長算法步驟。

2)雖然本文在屋頂面交界處同區域生長算法一樣出現了法向量異常的三角面，但以三角面為基元的分割方式使法向量異常三角面被其鄰近面片所剖分，部分地解決了屋頂交界處采樣點異常問題。

3)對于仍然存在的一部分孤立點與過度分割的面片，通過RANSAC算法，快速獲取各平面方程系數，結合Alpha Shape算法判斷孤立點及各平面鄰近關系，精確合并了孤立點與過度分割面片。比較于RANSAC算法與傳統的區域生長算法，本文方法所獲取結果在分割精度與屋頂面分割數量上均更為理想。

4)本文方法不足之處在于，以三角面為基元的分割方式對于狹長的建筑物屋頂面分割效果不理想。該問題將在今后學習研究中完善解決。