基于區(qū)域生長算法的復(fù)雜建筑物屋頂點云分割

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

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

0 引言

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

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

針對上述區(qū)域生長算法中存在激光點矢量信息需要通過鄰域估算，生長過程中鄰域點選取不當(dāng)?shù)膯栴}，本文提出一種以三角面為基元的基于區(qū)域生長算法的復(fù)雜建筑物屋頂點云分割算法。通過構(gòu)建Delaunay三角網(wǎng)的方式，將屋頂面點云劃分至不規(guī)則三角網(wǎng)內(nèi),以區(qū)域生長算法劃分各三角面，避免了各激光點逐點進(jìn)行矢量估算和鄰域點選取問題；然后合并各過度劃分的面片集合及孤立點，完成對建筑物屋頂面點云的精確分割。

1 研究方法

1.1 面片劃分

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

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

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

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

圖2 三角面區(qū)域生長結(jié)果

Fig.2Resultofregiongrowingoftriangles

1.2 面片合并

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

Ax+By+Cz+D=0，

(1)

式中A,B,C,D為系數(shù)。

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

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

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

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

(2)

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

3)面片合并。統(tǒng)計各面片集合激光點數(shù)量，由大到小排列，并認(rèn)為激光點數(shù)量最多的集合為標(biāo)準(zhǔn)平面。計算標(biāo)準(zhǔn)面至各Alpha Shape邊緣距離，若平面在Alpha Shape邊緣內(nèi)，距離為0；若距離小于閾值Б，則計算平面夾角，即

(3)

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

ρr=Kρ，

(4)

(5)

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

2 實驗

2.1 實驗數(shù)據(jù)與參數(shù)

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

2.2 算法對比

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

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

本文方法分割結(jié)果 RANSAC分割結(jié)果 區(qū)域生長分割結(jié)果

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

本文方法分割結(jié)果 RANSAC分割結(jié)果 區(qū)域生長分割結(jié)果

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

Fig.3-1Comparisonbetweendifferentalgorithmsonsegmentationofbuildings

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

本文方法分割結(jié)果 RANSAC分割結(jié)果 區(qū)域生長分割結(jié)果

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

本文方法分割結(jié)果 RANSAC分割結(jié)果 區(qū)域生長分割結(jié)果

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

Fig.3-2Comparisonbetweendifferentalgorithmsonsegmentationofbuildings

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

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

C=TP/(TP+FN)，

(6)

A=TP/(TP+FP)，

(7)

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

(8)

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

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

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

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

3 結(jié)論

本文提出了一種以三角面為基元的基于區(qū)域生長算法的復(fù)雜建筑物屋頂點云分割算法，以構(gòu)建Delaunay三角網(wǎng)方式構(gòu)建建筑物點云之間關(guān)系，并以各三角面片單位法向量作為判別條件，依據(jù)共邊三角面單位法向量的相似性對建筑物屋頂點云進(jìn)行分割。

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

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

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

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