結(jié)合超體素與區(qū)域增長(zhǎng)的LiDAR點(diǎn)云屋頂面分割

李明星，任高升，吉文來(lái)

(1.江蘇省鹽城技師學(xué)院，江蘇 鹽城 224000；2.南京工業(yè)大學(xué)，江蘇 南京 211816 )

0 引 言

機(jī)載激光雷達(dá)(airborne light detection and ranging，LiDAR)是一種對(duì)地探測(cè)新技術(shù)，能夠快速、精確地獲取地物位置信息和高度信息，為構(gòu)建三維數(shù)字城市特別是建筑物重建提供了新的手段[1-2]。屋頂面作為建筑物屋頂結(jié)構(gòu)的基本組成元素，對(duì)其快速準(zhǔn)確提取是基于機(jī)載LiDAR點(diǎn)云建筑物三維模型重建的關(guān)鍵步驟[3]。

由于機(jī)載LiDAR點(diǎn)云分布不規(guī)則且建筑物空間結(jié)構(gòu)復(fù)雜，從建筑物L(fēng)iDAR點(diǎn)云中高精度分割屋頂面仍面臨較大挑戰(zhàn)。相關(guān)學(xué)者對(duì)此進(jìn)行了研究，主要分為聚類(lèi)法、3D-Hough變換、隨機(jī)抽樣一致性(random sampling consensus，RANSAC)法和區(qū)域增長(zhǎng)法等。聚類(lèi)法[4]根據(jù)點(diǎn)云間距和點(diǎn)云密度等相似性測(cè)度進(jìn)行聚類(lèi)，提取結(jié)果較為穩(wěn)定，但易受聚類(lèi)參數(shù)和聚類(lèi)策略的影響，導(dǎo)致過(guò)提取或漏提取；3D-Hough[5]通過(guò)在參數(shù)空間內(nèi)進(jìn)行簡(jiǎn)單累加統(tǒng)計(jì)得到參數(shù)聚類(lèi)中心，但采樣大小會(huì)影響特征提取精度，且離散化會(huì)增加計(jì)算量；RANSAC算法[6]通過(guò)迭代方式從一組數(shù)據(jù)樣本中估算數(shù)學(xué)模型參數(shù)，具有較好的穩(wěn)健性，但提取結(jié)果易出現(xiàn)偽平面，當(dāng)數(shù)據(jù)復(fù)雜時(shí)，算法效率較低。區(qū)域增長(zhǎng)法[7-8]簡(jiǎn)單易行，但參數(shù)難以設(shè)置且過(guò)度依賴(lài)局部特征的計(jì)算精度，增長(zhǎng)過(guò)程易受噪聲影響。

基于上述研究，提出一種結(jié)合超體素和區(qū)域增長(zhǎng)的建筑物屋頂面點(diǎn)云分割方法。利用超體聚類(lèi)算法將點(diǎn)云過(guò)分割為超體素，基于超體素的光滑性和表面幾何特征進(jìn)行區(qū)域增長(zhǎng)，實(shí)現(xiàn)屋頂面點(diǎn)云提取。結(jié)合某地區(qū)建筑物L(fēng)iDAR點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該方法的有效性。

1 超體素生成

超體素是由若干體素構(gòu)成的集合，超體聚類(lèi)算法將點(diǎn)云過(guò)分割為若干超體素并研究超體素之間的關(guān)系[9]。利用八叉樹(shù)組織初始點(diǎn)云，結(jié)合相鄰體素間歐氏距離和法向量信息得到特征距離并構(gòu)建體素鄰接圖，基于流約束的聚類(lèi)算法將體素劃分至距離最近的種子體素構(gòu)成超體素。

1.1 距離度量

Cpi·γi=λi·γi(i=0,1,2)

(1)

(2)

式中，λi為Cpi的特征值。設(shè)λ0<λ1<λ2，則鄰域點(diǎn)集最小特征值λ0對(duì)應(yīng)的特征向量γ0即為體素vi的法向量ni，Kpi為點(diǎn)pi的曲率。設(shè)點(diǎn)云的視點(diǎn)為vp，體素vi的中心點(diǎn)為Si，則對(duì)各點(diǎn)的法向量方向進(jìn)行一致性定向[11]：

ni·(vp-Si)>0

(3)

結(jié)合點(diǎn)云數(shù)據(jù)的法向量信息和空間距離度量體素間的相似性，依據(jù)法向量角度差異、曲率特征和歐式距離計(jì)算種子體素及其鄰接體素間的特征距離：

(4)

式中，DC為體素間的曲率變化值，Cmax為體素鄰域范圍內(nèi)的最大曲率值，DS為體素間歐氏距離，Dθ為互為鄰接關(guān)系的體素間法向量的點(diǎn)積，λC、λS、λθ分別為DC、DS、Dθ的權(quán)重。由于兩種不同空間的距離尺度不一，對(duì)DC、DS和Dθ進(jìn)行歸一化處理得到鄰接體素間的特征距離，以其作為體素鄰接圖中邊的權(quán)重構(gòu)建三維點(diǎn)云26鄰接圖[12]。

1.2 超體素聚類(lèi)

利用流約束的聚類(lèi)算法分割體素?cái)?shù)據(jù)，算法具體過(guò)程為：

(1)初始化k個(gè)種子體素集合SSi={SS1,SS2…SSk}。

(2)搜索種子體素鄰域內(nèi)的體素vi與種子體素SSi之間的特征距離，若在閾值范圍內(nèi)，則將vi劃分至Ci中。

(3)更新聚類(lèi)集合Ci的中心體素：

(5)

(4)重復(fù)上述步驟，直至聚類(lèi)集合的中心體素SS不再變化，聚類(lèi)集合Ci即為超體素。

算法流程如圖1所示。

圖1 超體素生成算法流程圖

2 結(jié)合超體素的區(qū)域增長(zhǎng)算法

通過(guò)分析超體素結(jié)構(gòu)特征和區(qū)域增長(zhǎng)算法[12]的特性，提出一種基于超體素和區(qū)域增長(zhǎng)的屋頂面點(diǎn)云分割方法。通過(guò)擬合平面殘差值選擇種子超體素，歸一化法線和點(diǎn)特征直方圖(Point Feature Histogram，PFH)度量鄰接超體素間的相似性，基于區(qū)域增長(zhǎng)算法聚類(lèi)超體素提取屋頂面片點(diǎn)云。

2.1 相似性特征度量

超體素內(nèi)包含大量的體素，對(duì)一個(gè)或幾個(gè)體素計(jì)算得到的屬性特征無(wú)法代表整個(gè)超體素，因此，引入PFH估計(jì)超體素的表面幾何特征并利用法線方向變化確保分割結(jié)果的光滑性。在128維空間下，利用法線方向和PFH建立超體素的特征向量：

F=[x,y,z,PFH1…125]

(6)

式中，x,y,z為超體素法向量的坐標(biāo)，PFH1…125為125維空間的PFH向量。結(jié)合超體素光滑性和幾何特征約束，歸一化法線和PFH向量得到歸一化距離S，將其作為種子超體素與鄰接超體素之間的相似性度量。

(7)

式中，σN為法向量的權(quán)重，σPFH為超體素PFH的權(quán)重，σN+σPFH=1，SN和SPFH分別對(duì)應(yīng)超體素法向量和PFH特征向量夾角的余弦值。

2.2 基于超體素的區(qū)域增長(zhǎng)

基于超體素的區(qū)域增長(zhǎng)算法需要選取種子超體素進(jìn)行初始化。僅利用超體素質(zhì)心點(diǎn)曲率信息無(wú)法準(zhǔn)確度量整個(gè)超體素的結(jié)構(gòu)特征，因此，結(jié)合超體素結(jié)構(gòu)特征，改進(jìn)區(qū)域增長(zhǎng)算法的種子選取策略。

基于最小二乘法對(duì)每個(gè)超體素進(jìn)行平面擬合，計(jì)算對(duì)應(yīng)的殘差值并利用殘差值判斷超體素表面的近似曲率，確定初始種子超體素。選擇殘差值最小的超體素作為當(dāng)前區(qū)域初始種子，以初始種子超體素為中心進(jìn)行區(qū)域增長(zhǎng)。設(shè)定固定閾值rth篩選鄰域內(nèi)的候選種子超體素繼續(xù)增長(zhǎng)，保證了分割算法可以較好地處理邊界區(qū)域。

綜上所述，結(jié)合超體素的區(qū)域增長(zhǎng)算法具體流程如圖2所示：

圖2 基于超體素的區(qū)域增長(zhǎng)算法流程圖

(1)構(gòu)建KD-Tree空間索引，利用最小二乘法對(duì)每個(gè)超體素進(jìn)行平面擬合并計(jì)算相應(yīng)的殘差值，根據(jù)殘差值對(duì)所有超體素進(jìn)行排序，選擇殘差值最小的超體素作為初始種子超體素。

(2)若當(dāng)前種子超體素集合U非空，選擇初始種子超體素對(duì)當(dāng)前區(qū)域開(kāi)始增長(zhǎng)，設(shè)定固定的殘差閾值rth篩選當(dāng)前種子鄰域內(nèi)的候選種子集合。

(3)搜索初始種子超體素的r半徑鄰域，根據(jù)歸一化距離S度量鄰接超體素之間的相似性，將閾值Sth范圍內(nèi)的鄰接超體素添加到當(dāng)前分割區(qū)域。

(4)對(duì)初始種子鄰域超體素判斷結(jié)束后，從U中移除該種子超體素，選擇鄰域內(nèi)的候選種子超體素繼續(xù)對(duì)當(dāng)前區(qū)域進(jìn)行增長(zhǎng)，若U為空，則停止當(dāng)前區(qū)域的增長(zhǎng)。

(5)選取新的初始種子超體素，重復(fù)上述步驟直至遍歷所有的超體素?cái)?shù)據(jù)。

3 實(shí)驗(yàn)分析

為了驗(yàn)證算法對(duì)屋頂面的提取效果及適應(yīng)性，從ISPRS提供的City Site機(jī)載LiDAR數(shù)據(jù)集中(圖3)選取一塊包含11棟建筑物的LiDAR 點(diǎn)云進(jìn)行測(cè)試。實(shí)驗(yàn)點(diǎn)云單個(gè)建筑物面積相對(duì)較大且包含的屋頂面?zhèn)€數(shù)較多，建筑物屋頂面的大小、形狀差異較大。

圖3 實(shí)驗(yàn)區(qū)點(diǎn)云數(shù)據(jù)

采用相關(guān)文獻(xiàn)[13]定義的建筑物屋頂面提取質(zhì)量評(píng)價(jià)體系，其中屋頂面的提取率為：

(8)

式中，S為實(shí)驗(yàn)選取的建筑物屋頂面，S*為算法分割獲得的建筑物屋頂面。計(jì)算算法提取率時(shí),將面積大于5 m2的屋頂面為主屋頂面，其余為次屋頂面[13]。算法需要設(shè)置4個(gè)參數(shù)，分別為體素半徑Rv，相鄰超體素間距離Rs，區(qū)域增長(zhǎng)鄰域搜索半徑r和法向量差異閾值，Rv、Rs和r的設(shè)置均與點(diǎn)云密度ρ有關(guān)：

(9)

式中，n為點(diǎn)云中離散點(diǎn)的數(shù)量。屋頂面點(diǎn)云分割實(shí)驗(yàn)結(jié)果如表1所示。

表1 屋頂面分割統(tǒng)計(jì)結(jié)果

由表1可知，利用傳統(tǒng)區(qū)域增長(zhǎng)算法得到的主屋頂面、次屋頂面和所有屋頂面的提取率僅為80%、41.2%和76.2%。采用區(qū)域增長(zhǎng)法進(jìn)行屋頂面分割，較大面積的屋頂面分割效果較好，但在邊緣處及屋頂面相交處，由于局部特征計(jì)算的不穩(wěn)定性且難以找到合適的增長(zhǎng)閾值，出現(xiàn)了鄰近屋頂面被合并或者同一屋頂面被分割的現(xiàn)象；基于超體素的區(qū)域增長(zhǎng)算法，得到的屋頂面提取率較高，主屋頂面、次屋頂面和所有屋頂面的提取率分別為93.3%、52.9%和87.7%。次屋頂面仍存在漏檢的情況，主要原因是，次屋頂面與相鄰面積較大的屋面近似平行且高差較小，算法易將屋頂面邊緣點(diǎn)優(yōu)先分配給相鄰面積更大的屋頂面。與傳統(tǒng)區(qū)域增長(zhǎng)算法相比，本文方法屋頂面提取率較高，分割的屋頂面更加完整，在屋頂面拓?fù)潢P(guān)系復(fù)雜的情況下仍能取得較好的分割效果。

4 結(jié) 語(yǔ)

針對(duì)傳統(tǒng)區(qū)域增長(zhǎng)算法的不足，提出一種基于超體素的區(qū)域增長(zhǎng)屋頂面點(diǎn)云分割方法。將點(diǎn)云分割為超體素，結(jié)合超體素的光滑性和幾何特征約束進(jìn)行區(qū)域增長(zhǎng)，提取屋頂面片點(diǎn)云。實(shí)驗(yàn)結(jié)果表明，該方法的屋頂面提取率高且適應(yīng)性好，對(duì)復(fù)雜建筑物屋頂面仍有較好的分割效果，為建筑物精細(xì)建模提供了基礎(chǔ)。但本文算法參數(shù)較多且需要根據(jù)點(diǎn)云密度進(jìn)行設(shè)置，如何對(duì)不同類(lèi)型點(diǎn)云數(shù)據(jù)自適應(yīng)設(shè)置參數(shù)將是下一步的研究?jī)?nèi)容。