趙 傳，張保明，陳小衛(wèi)，郭海濤，盧 俊

1. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001； 2. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710054

趙傳，張保明，陳小衛(wèi)，等.一種利用點(diǎn)云鄰域信息的建筑物屋頂面高精度自動(dòng)提取方法[J].測(cè)繪學(xué)報(bào)，2017,46(9)：1123-1134.

10.11947/j.AGCS.2017.20160518.

ZHAO Chuan,ZHANG Baoming,CHEN Xiaowei,et al.Accurate and Automatic Building Roof Extraction Using Neighborhood Information of Point Clouds[J]. Acta Geodaetica et Cartographica Sinica,2017,46(9):1123-1134. DOI:10.11947/j.AGCS.2017.20160518.

一種利用點(diǎn)云鄰域信息的建筑物屋頂面高精度自動(dòng)提取方法

趙 傳1,2，張保明1，陳小衛(wèi)1,2，郭海濤1，盧 俊1

1. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001； 2. 地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710054

從LiDAR數(shù)據(jù)中高精度地提取建筑物屋頂面是構(gòu)建屋頂面拓?fù)潢P(guān)系、實(shí)現(xiàn)建筑物三維模型重建的關(guān)鍵。本文針對(duì)現(xiàn)有算法提取復(fù)雜建筑物屋頂面適應(yīng)性較差、精度較低等問題，提出了一種利用點(diǎn)云鄰域信息的建筑物屋頂面高精度自動(dòng)提取方法。通過主成分分析計(jì)算點(diǎn)云特征，構(gòu)建特征直方圖，選取可靠種子點(diǎn)；利用提出的局部點(diǎn)云法向量分布密度聚類算法聚類種子點(diǎn)，快速準(zhǔn)確地提取初始屋頂面片；構(gòu)建基于鄰域信息的投票模型，有效地解決屋頂面競(jìng)爭(zhēng)現(xiàn)象。試驗(yàn)結(jié)果表明，本文方法可自動(dòng)、高精度地提取屋頂面，對(duì)不同復(fù)雜程度的建筑物具有較好的適應(yīng)性，能為建筑物三維模型重建提供可靠的屋頂面信息。

建筑物屋頂面；LiDAR數(shù)據(jù)；鄰域信息；密度聚類；點(diǎn)云；建筑物三維重建

激光雷達(dá)測(cè)量(light detection and ranging,LiDAR)是近十幾年迅猛發(fā)展起來的一種新型、高效的空間數(shù)據(jù)獲取技術(shù)，在數(shù)字城市建設(shè)、植被檢測(cè)、災(zāi)害處理和城市規(guī)劃等領(lǐng)域都發(fā)揮著重要的作用[1]。建筑物作為城市中最基本、最主要的組成元素，其三維信息是重要的基礎(chǔ)地理信息[2]，基于機(jī)載激光雷達(dá)數(shù)據(jù)的建筑物三維模型重建已成為當(dāng)前的研究熱點(diǎn)[3]。屋頂面作為建筑物屋頂結(jié)構(gòu)的基本組成元素，快速、準(zhǔn)確地對(duì)其進(jìn)行提取是基于機(jī)載LiDAR數(shù)據(jù)重建建筑物三維模型的關(guān)鍵步驟[4]。由于機(jī)載LiDAR點(diǎn)云分布不連續(xù)、不規(guī)則，點(diǎn)云中存在噪聲，以及建筑物具有多層次空間復(fù)雜結(jié)構(gòu)等因素的影響，從建筑物L(fēng)iDAR點(diǎn)云中自動(dòng)、高精度地提取屋頂面仍然面臨較大的挑戰(zhàn)。

目前，學(xué)者們圍繞屋頂面提取進(jìn)行了大量研究，提出了很多方法，主要可分為模型擬合法、區(qū)域增長(zhǎng)法、聚類法、剖面分析法和能量最小化法[5-7]。模型擬合法利用局部范圍內(nèi)的點(diǎn)云擬合預(yù)定義模型的方程實(shí)現(xiàn)屋頂面的提取，較為經(jīng)典的模型擬合法有隨機(jī)采樣一致性(random sample consensus,RANSAC)算法和三維Hough變換，其中RANSAC具有較好的穩(wěn)健性，在有大量局外點(diǎn)時(shí)也能較好地估計(jì)出高精度的模型參數(shù)，但提取結(jié)果中容易出現(xiàn)偽平面，且在數(shù)據(jù)復(fù)雜的情況下，效率將顯著降低，文獻(xiàn)[5]提出了加權(quán)RANSAC，研究了多種權(quán)函數(shù)對(duì)提取結(jié)果的影響，較好地解決了提取結(jié)果中出現(xiàn)偽平面的問題，文獻(xiàn)[8]改進(jìn)了RANSAC的采樣策略，較大地提高了其效率；三維Hough變換[9-10]將特征檢測(cè)問題轉(zhuǎn)換到參數(shù)空間，通過采樣參數(shù)空間，并在參數(shù)空間進(jìn)行簡(jiǎn)單累加統(tǒng)計(jì)得到參數(shù)聚類中心，但采樣間隔大小對(duì)提取結(jié)果的精度有一定影響，通常采樣間隔越小，提取結(jié)果越精確，但同時(shí)會(huì)使算法效率顯著降低。區(qū)域增長(zhǎng)法[11-14]簡(jiǎn)單易行，效率較高，但對(duì)初始種子點(diǎn)的要求較高，增長(zhǎng)過程易受噪聲點(diǎn)的影響，且對(duì)于過渡平緩的屋頂面難以設(shè)置停止增長(zhǎng)條件，容易出現(xiàn)過增長(zhǎng)。聚類法根據(jù)點(diǎn)之間的距離或點(diǎn)云密度等相似性測(cè)度，利用如k-means[15]、MeanShift[16]等聚類算法聚類點(diǎn)云，可得到較為穩(wěn)定的提取結(jié)果，但由于受聚類參數(shù)、聚類策略等因素的影響，容易導(dǎo)致過提取和漏提取。剖面分析法將掃描線分析用于識(shí)別點(diǎn)云中的平面特征，其原理簡(jiǎn)單，具有分割結(jié)果好、速度快、效率高等優(yōu)點(diǎn)，可實(shí)現(xiàn)大區(qū)域點(diǎn)云數(shù)據(jù)中平面特征的提取，文獻(xiàn)[7]以規(guī)則格網(wǎng)組織方式索引點(diǎn)云，利用規(guī)則格網(wǎng)中高程最大點(diǎn)計(jì)算4個(gè)方向的掃描線，并由掃描線得到交叉線元，通過基于交叉線元和基于點(diǎn)的兩種增長(zhǎng)方式，實(shí)現(xiàn)了屋頂面快速準(zhǔn)確提取，但由于僅利用了4個(gè)方向的掃描線，難以適應(yīng)各種形狀屋頂面的提取(如長(zhǎng)條形屋頂面)，且該算法利用規(guī)則格網(wǎng)中高程最大點(diǎn)計(jì)算掃描線，因此格網(wǎng)大小的設(shè)置對(duì)提取結(jié)果會(huì)有一定的影響，此外，交叉線元長(zhǎng)度沒有明確的含義，較難設(shè)置。能量最小化法通過定義包含數(shù)據(jù)項(xiàng)、平滑項(xiàng)等的能量函數(shù)，利用最小生成樹、歸一化割、圖割等算法得到極小化解，從而將屋頂面提取問題轉(zhuǎn)換成全局最優(yōu)標(biāo)記問題，文獻(xiàn)[6]以區(qū)域增長(zhǎng)的結(jié)果作為初始輸入，利用α-expansion圖割算法求得能量函數(shù)的極小化解，提高了提取完整率和正確率，但其提取結(jié)果中的屋頂面數(shù)不可能多于初始輸入中的屋頂面數(shù)，因此無法通過后續(xù)優(yōu)化過程提取部分漏提取的屋頂面，且迭代求解能量函數(shù)的極小化解效率較低。

針對(duì)現(xiàn)有方法提取復(fù)雜建筑物屋頂面適應(yīng)性較差、精度較低等問題，本文提出一種利用點(diǎn)云鄰域信息的建筑物屋頂面高精度自動(dòng)提取方法。

1 算法描述

本文算法通過預(yù)處理選取可靠聚類種子點(diǎn)，利用局部點(diǎn)云法向量分布密度聚類(local normal vector distribution density-based spatial clustering of applications with noise,LNVD-DBSCAN)提取初始屋頂面片，并在此基礎(chǔ)上進(jìn)行面片細(xì)化處理，可較好地提取不同復(fù)雜程度建筑物的屋頂面，具體技術(shù)流程見圖1。

圖1 屋頂面提取流程Fig.1 Flowchart of roof extraction

1.1 預(yù)處理

建筑物屋頂一般由多個(gè)屋頂面構(gòu)成，在屋頂面相交處會(huì)形成如屋脊線等尖銳特征，尖銳特征附近的點(diǎn)云法向量通常難以準(zhǔn)確計(jì)算，尤其當(dāng)點(diǎn)云較為稀疏或噪聲較大時(shí)，計(jì)算的點(diǎn)云法向量可靠性更差[17]。為保證法向量分布密度聚類提取建筑物屋頂面的準(zhǔn)確性，首先對(duì)建筑物點(diǎn)云進(jìn)行預(yù)處理，得到可靠的聚類種子點(diǎn)。預(yù)處理過程包括以下兩個(gè)步驟：

(1)

式中，λ0、λ1、λ2為Cp的3個(gè)特征值，且滿足λ0≤λ1≤λ2；v0為λ0對(duì)應(yīng)的特征向量。

(2) 統(tǒng)計(jì)曲率直方圖，選取種子點(diǎn)，為后續(xù)處理提供可靠的初始數(shù)據(jù)。確定直方圖采樣間隔是構(gòu)建直方圖的首要步驟，由于點(diǎn)云分布不規(guī)則、建筑物屋頂面形狀復(fù)雜多樣等因素的影響，導(dǎo)致不同建筑物點(diǎn)云曲率的分布不同，設(shè)置固定的采樣間隔難以得到較為準(zhǔn)確的建筑物點(diǎn)云曲率分布，因此無法計(jì)算合適的曲率閾值。本文通過建筑物點(diǎn)數(shù)Nb設(shè)置統(tǒng)計(jì)區(qū)間個(gè)數(shù)，并根據(jù)建筑物點(diǎn)云曲率最大最小值動(dòng)態(tài)計(jì)算采樣間隔ΔK

(2)

式中，KS代表所有建筑物點(diǎn)云的曲率；κmin為最小間隔，一般取10-3～10-5。

確定采樣間隔后，通過累計(jì)直方圖計(jì)算曲率閾值，得到種子點(diǎn)集seed

seed={p|Kpτ)，τ=r·Nb}

(3)

式中，accu為累計(jì)直方圖的值；v(accu>τ)為accu大于τ時(shí)直方圖橫坐標(biāo)對(duì)應(yīng)的曲率值；r為非尖銳特征點(diǎn)數(shù)與屋頂面點(diǎn)云數(shù)的比值，一般取0.8～0.95。

圖2(a)—(c)分別為建筑物影像、對(duì)應(yīng)點(diǎn)云曲率分布和種子點(diǎn)選取結(jié)果，圖2(c)中黑色點(diǎn)代表選取的種子點(diǎn)。由圖2可知，算法較好地選取了可靠的聚類種子點(diǎn)。建筑物為典型的人工地物，屋頂面多為平面，屋頂面點(diǎn)云法向量整體上會(huì)指向多個(gè)方向，具有一定的相似性[19]。圖2(d)為圖2(a)所示建筑物的點(diǎn)云法向量空間分布(圖2中不同顏色代表不同的屋頂面點(diǎn))，由圖2可知，同一屋頂面點(diǎn)云法向量在法向量空間分布較為集中，因此可通過法向量分布密度聚類提取建筑物屋頂面。

1.2 LNVD-DBSCAN聚類

聚類是一個(gè)無監(jiān)督的分類過程，常見的聚類方法主要可以分為劃分式聚類方法、層次聚類方法、基于密度和網(wǎng)格的聚類方法和其他聚類方法[20]。k-means作為一種經(jīng)典的劃分式聚類方法，應(yīng)用較為廣泛，但該方法需預(yù)先設(shè)定聚類個(gè)數(shù)或聚類中心，且只考慮單個(gè)聚類中心之間的距離[21]，適用于類球形簇的聚類。層次聚類方法通過反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合得到聚類結(jié)果，聚類個(gè)數(shù)難以確定且效率較低，適合小型數(shù)據(jù)集的聚類。DBSCAN(density-based spatial clustering of applications with noise)作為一種經(jīng)典的基于密度的聚類方法[22]，利用數(shù)據(jù)密度作為劃分?jǐn)?shù)據(jù)的準(zhǔn)則，適用于聚類任意形狀的數(shù)據(jù)，但僅使用單一距離度量數(shù)據(jù)間的相似性，難以顧及數(shù)據(jù)的多維特征[21]，且方法對(duì)參數(shù)的設(shè)置比較敏感。目前已有學(xué)者利用DBSCAN從LiDAR數(shù)據(jù)中提取路燈[23]、建筑物[24]等地物點(diǎn)云，得到了較好的結(jié)果。

通過分析建筑物屋頂面點(diǎn)云法向量分布的特點(diǎn)和DBSCAN算法的聚類特性，本文提出一種點(diǎn)云局部法向量分布密度聚類(LNVD-DBSCAN)方法，將屋頂面點(diǎn)云在空間域和法向量特征域的特點(diǎn)融入DBSCAN，使用兩個(gè)距離度量屋頂面點(diǎn)云之間的相似性，并結(jié)合建筑物同一屋頂面點(diǎn)云法向量夾角較小的特點(diǎn)，以解決DBSCAN算法參數(shù)難以設(shè)置的缺點(diǎn)。

LNVD-DBSCAN算法主要包括鄰域擴(kuò)充和面片驗(yàn)證兩個(gè)步驟，下面對(duì)其主要原理進(jìn)行介紹。

1.2.1 鄰域擴(kuò)充

定義建筑物點(diǎn)p的ε鄰域εp為

(4)

式中，q代表點(diǎn)p的ε鄰域點(diǎn)；np、nq分別代表點(diǎn)p、q的單位法向量；θ為法向量夾角閾值，取值一般不大于10°。

鄰域擴(kuò)充流程如圖3所示，將所有建筑物點(diǎn)的處理狀態(tài)置為未標(biāo)記，算法依次處理種子點(diǎn)集中的未標(biāo)記點(diǎn)，如果未標(biāo)記點(diǎn)p的ε鄰域點(diǎn)數(shù)|εp|大于形成屋頂面的最少點(diǎn)數(shù)m(m根據(jù)點(diǎn)云密度自適應(yīng)設(shè)置)，則判斷為提取到屋頂面片M，將該點(diǎn)及其ε鄰域點(diǎn)標(biāo)記為屋頂面片M的點(diǎn)，并順序處理M中的所有點(diǎn)。如果種子點(diǎn)集中滿足條件的未標(biāo)記點(diǎn)都已處理，則結(jié)束鄰域擴(kuò)充，得到多個(gè)初始屋頂面片。

1.2.2 面片驗(yàn)證

建筑物可能包含多個(gè)平行屋頂面，雖然鄰域擴(kuò)充時(shí)加入了點(diǎn)云空間距離約束，但對(duì)于距離較小的平行屋頂面，如圖4(a)所示，屋頂面片A、B交界處點(diǎn)的k鄰域點(diǎn)可能分布在A、B兩個(gè)屋頂面片，導(dǎo)致算法在鄰域擴(kuò)充時(shí)將兩個(gè)屋頂面片合并提取(如圖4(b)中紅色點(diǎn)云所代表的屋頂面片)，因此在鄰域擴(kuò)充后，需要判斷提取的初始屋頂面片是否正確。

圖2 點(diǎn)云特征分布及種子點(diǎn)選取結(jié)果Fig.2 Point cloud feature distribution and seeds selection result

圖3 鄰域擴(kuò)充流程Fig.3 Illustration of neighborhood extension

由于相鄰平行屋頂面的距離和法向量夾角較小，通過聚類或區(qū)域增長(zhǎng)難以分離，因此采用隨機(jī)抽樣的方法構(gòu)建虛擬屋頂面驗(yàn)證初始屋頂面片的正確性。面片驗(yàn)證流程如圖5所示，將初始屋頂面片M作為初始數(shù)據(jù)，通過隨機(jī)選點(diǎn)構(gòu)建虛擬屋頂面片N，如果存在相鄰平行屋頂面(即M與N法向量夾角大于θ)，則分離，并輸出N，同時(shí)更新M的數(shù)據(jù)(即將屬于N的點(diǎn)從M中去除)。相鄰平行屋頂面數(shù)通常較少，因此只需設(shè)置較小的迭代次數(shù)t(根據(jù)單個(gè)建筑物相鄰平行屋頂面數(shù)設(shè)置，取值一般不大于50)即能分離所有相鄰平行屋頂面，圖4(c)為面片驗(yàn)證結(jié)果，由圖可知，算法較好地分離了相鄰平行屋頂面。

圖4 鄰域擴(kuò)充及面片驗(yàn)證結(jié)果Fig.4 Neighborhood extension and roof surface validation results

圖5 面片驗(yàn)證流程Fig.5 Illustration of roof surface validation

1.3 面片細(xì)化處理

1.3.1 面片合并

由于點(diǎn)云分布不規(guī)則、法向量計(jì)算存在偏差等因素的影響，部分屋頂面通過LNVD-DBSCAN聚類后可能形成多個(gè)面片，如圖6(a)中建筑物點(diǎn)云的聚類結(jié)果為圖6(b)。為得到完整的建筑物屋頂面，需合并屬于同一屋頂面的初始屋頂面片。

圖6 屋頂面片合并Fig.6 Roof surface mergence

初始屋頂面片只包含非尖銳特征區(qū)域的屋頂面點(diǎn)，在合并前需標(biāo)記其余未標(biāo)記點(diǎn)，即以初始屋頂面片平面外接矩形為基礎(chǔ)，向四周擴(kuò)展一定距離db形成緩沖區(qū)(根據(jù)屋頂面實(shí)際大小，db的取值范圍為2～8 m)；計(jì)算未標(biāo)記點(diǎn)到各初始屋頂面片的距離，如果距離中的最小值小于δ0(由于噪聲等因素影響，取值稍大，δ0一般不大于0.3 m)，且未標(biāo)記點(diǎn)在最小值對(duì)應(yīng)的面片緩沖區(qū)內(nèi)，則將未標(biāo)記點(diǎn)標(biāo)記為該初始屋頂面片點(diǎn)。

將未標(biāo)記點(diǎn)標(biāo)記后，根據(jù)以下3個(gè)原則合并初始屋頂面片：①兩屋頂面片相鄰，即兩屋頂面片之間的最小平面距離dh小于dhmin(dhmin取值范圍為0～1.5 m)；②兩屋頂面片夾角小于θ，面片夾角通過面片法向量計(jì)算；③兩屋頂面片的垂距dv小于δ0。面片合并原則用式(5)表示

(5)

式中各符號(hào)的含義如圖6(c)面片合并示意圖所示，其中p1、p2分別為屋頂面片A、B的任一點(diǎn)，平面A1、B1分別過屋頂面片A、B的質(zhì)心p3、p4，且法向量滿足式(6)

(6)

圖6(d)為圖6(b)聚類結(jié)果的面片合并結(jié)果。由圖6可知，算法較好地合并了屬于同一屋頂面的初始屋頂面片，得到了完整的屋頂面。

1.3.2 屋頂面競(jìng)爭(zhēng)處理

屋頂面競(jìng)爭(zhēng)現(xiàn)象是指一些屋頂面點(diǎn)在數(shù)學(xué)意義上可同時(shí)歸屬為多個(gè)屋頂面，在多個(gè)屋頂面相交區(qū)域更為常見[14]。在圖7中，點(diǎn)p1、p2分別屬于屋頂面A、C，但由于點(diǎn)p1、p2到屋頂面B的距離小于到屋頂面A、C的距離，因此在未標(biāo)記點(diǎn)分類時(shí)點(diǎn)p1、p2被錯(cuò)誤加入屋頂面B中，導(dǎo)致屋頂面邊界不清晰。此外，在未標(biāo)記點(diǎn)分類時(shí)，由于沒有考慮建筑物屋頂面點(diǎn)云空間分布的連續(xù)性和規(guī)律性，導(dǎo)致部分點(diǎn)可能存在明顯的錯(cuò)分現(xiàn)象，如圖7中的點(diǎn)p3。本文通過構(gòu)建鄰域投票模型解決上述問題。

建筑物點(diǎn)云中的任一點(diǎn)是否屬于屋頂面M主要由兩個(gè)因素決定：該點(diǎn)鄰域點(diǎn)涉及的不同屋頂面點(diǎn)數(shù)和到屋頂面M的距離，且兩個(gè)因素相互獨(dú)立。令點(diǎn)p的k鄰域點(diǎn)所涉及的屋頂面集合為Y，Y={Y1,Y2,…,Ym}，m代表k鄰域點(diǎn)涉及的屋頂面數(shù)，通過分析可知，點(diǎn)p屬于屋頂面Yi的權(quán)值w(Yi)滿足

w(Yi)=w1(ni)·w2(di)i=1,2,…,m

(7)

式中，ni、di分別代表點(diǎn)p的k鄰域中屬于屋頂面Yi的點(diǎn)數(shù)和到屋頂面Yi的距離；w1(ni)、w2(di)分別代表點(diǎn)p通過ni、di計(jì)算的權(quán)值。

圖7 屋頂面競(jìng)爭(zhēng)示意圖Fig.7 Illustration of roof competition

權(quán)函數(shù)對(duì)確定點(diǎn)云所屬屋頂面至關(guān)重要。通常，點(diǎn)p的k鄰域點(diǎn)屬于屋頂面Yi的點(diǎn)數(shù)ni越多，則點(diǎn)p為屋頂面Yi點(diǎn)的概率越大，即w1(ni)越大，且w1(ni)應(yīng)隨ni減小迅速減??；點(diǎn)p與屋頂面Yi的距離di越小，則點(diǎn)p屬于屋頂面Yi的概率越大，即w2(di)越大，且w2(di)應(yīng)隨di增大迅速減小，當(dāng)距離大于一定閾值時(shí)w2(di)接近于0，w1(ni)、w2(di)的曲線圖應(yīng)為圖8(a)、(b)所示，因此本文采用高斯函數(shù)進(jìn)行描述。

設(shè)ni、di服從方差為σni、σdi，均值為μni、μdi的高斯分布，通過分析及高斯分布3σ原則可得

(8)

圖8 權(quán)函數(shù)分布示意圖Fig.8 Illustration of weighted function distribution

(9)

2 試驗(yàn)與分析

2.1 數(shù)據(jù)與試驗(yàn)方法

為了驗(yàn)證本文算法的提取精度及適應(yīng)性，利用Vaihingen地區(qū)[26]和科羅拉多博爾德分校[27]的機(jī)載LiDAR數(shù)據(jù)集(分別記為數(shù)據(jù)集1和數(shù)據(jù)集2)中的部分建筑物點(diǎn)云數(shù)據(jù)，在Visual Studio 2012 C++和Intel(R) CoreTMi7-4810MQ處理器、8 GB運(yùn)行內(nèi)存的軟硬件環(huán)境下進(jìn)行兩組試驗(yàn)，分別記為試驗(yàn)1和試驗(yàn)2。由于本文研究重點(diǎn)是從建筑物點(diǎn)云中提取屋頂面，因此地面、墻面及植被等非建筑物地物點(diǎn)云已被剔除，本文所用數(shù)據(jù)集的基本信息如表1所示。

表1 數(shù)據(jù)集信息

試驗(yàn)與RANSAC[28]、M-采樣一致性估計(jì)算法(M-estimators sample consensus,MSAC)[29]及結(jié)合主成分分析的區(qū)域增長(zhǎng)(region growth+principal component analysis,RG_PCA)[11]算法進(jìn)行對(duì)比，由于RANSAC和MSAC無法分離位于同一平面的屋頂面，因此本文將兩種方法的提取結(jié)果經(jīng)歐氏空間聚類(聚類距離設(shè)置為2 m)后與本文方法對(duì)比。根據(jù)前文列出的各閾值的范圍，試驗(yàn)中本文算法閾值設(shè)置的情況如下：r=0.9，κmin=10-4，θ=4°，δ0=0.25 m，t=30，db=5 m，dhmin=1 m。

試驗(yàn)中建筑物標(biāo)準(zhǔn)屋頂面為結(jié)合影像人工提取，由于算法提取的屋頂面與標(biāo)準(zhǔn)屋頂面的關(guān)系可能為一對(duì)一、一對(duì)多或多對(duì)多，因此本文采用文獻(xiàn)[25]的處理和評(píng)價(jià)方法，即通過計(jì)算提取的屋頂面與標(biāo)準(zhǔn)屋頂面的重疊率，根據(jù)最大重疊率確定提取的屋頂面與標(biāo)準(zhǔn)屋頂面的對(duì)應(yīng)關(guān)系，按下式計(jì)算完整率comp、正確率corr和提取質(zhì)量quality

(10)

式中，‖TP‖為正確提取的屋頂面點(diǎn)數(shù)；‖F(xiàn)N‖為漏提取的屋頂面點(diǎn)數(shù)；‖F(xiàn)P‖為誤提取的屋頂面點(diǎn)數(shù)。

2.2 試驗(yàn)結(jié)果及比較

2.2.1 試驗(yàn)1: 單棟建筑物數(shù)據(jù)

選取10棟屋頂面拓?fù)潢P(guān)系復(fù)雜的建筑物點(diǎn)云作為試驗(yàn)1數(shù)據(jù)，分別記為建筑物1—10(其中建筑物1—5選自數(shù)據(jù)集1，建筑物6—10選自數(shù)據(jù)集2)。不同算法屋頂面提取結(jié)果如圖9所示，其中綠色代表未提取的屋頂面點(diǎn)和屋頂附屬物點(diǎn)，其他顏色分別代表提取的不同屋頂面。

對(duì)比圖9中不同算法的提取結(jié)果可知，本文算法提取結(jié)果較好。對(duì)于過渡平緩的相鄰屋頂面，如建筑物1和2影像中的藍(lán)色矩形區(qū)域，RANSAC、MSAC及RG_PCA提取效果較差；對(duì)于曲率變化較小的曲面屋頂面，如建筑物2、4和9影像中的綠色矩形區(qū)域，RANSAC、MSAC提取結(jié)果較差，RG_PCA和本文算法能得到較好的提取結(jié)果；對(duì)于相鄰屋頂面夾角適中的建筑物，如建筑物3，點(diǎn)云的法向量和曲率都能通過PCA較為準(zhǔn)確地計(jì)算，4種算法均能得到較好的提取結(jié)果，但對(duì)于夾角較大的建筑物，如建筑物5，屋脊線附近點(diǎn)云法向量計(jì)算不準(zhǔn)確且局部點(diǎn)云曲率變化較大，導(dǎo)致RG_PCA提取效果較差；本文算法漏提取了建筑物4和5中的部分屋頂面(如建筑物4、5影像紅色矩形區(qū)域)，主要原因是該部分屋頂面點(diǎn)數(shù)較少且位于多個(gè)屋頂面相交處，計(jì)算的點(diǎn)云曲率較大，因此選取的種子點(diǎn)不包含該屋頂面點(diǎn)云；對(duì)于存在多個(gè)重復(fù)結(jié)構(gòu)的建筑物，如建筑物8，RANSAC提取結(jié)果中屋頂面競(jìng)爭(zhēng)現(xiàn)象較為明顯，導(dǎo)致提取結(jié)果效果較差，MSAC的提取效

果在一定程度上有所提高，但存在過提取現(xiàn)象；對(duì)于屋頂面?zhèn)€數(shù)多、屋頂面大小形狀差異大且拓?fù)潢P(guān)系極為復(fù)雜的建筑物，如建筑物6、9和10(屋頂面?zhèn)€數(shù)均大于30個(gè))，RANSAC、MSAC及RG_PCA均出現(xiàn)了不同程度的誤提取，提取結(jié)果比較雜亂，難以用于構(gòu)建屋頂面拓?fù)潢P(guān)系。本文方法主要為提取平面屋頂面，能較好地提取上述各建筑物的平面屋頂面，但對(duì)于曲率變化較大的曲面屋頂面，算法會(huì)將此類屋頂面提取為多個(gè)屋頂面片，如建筑物影像6和影像7紅色矩形區(qū)域，提取效果較差。

2.2.2 試驗(yàn)2: 區(qū)域建筑物數(shù)據(jù)

選取6個(gè)區(qū)域建筑物點(diǎn)云作為試驗(yàn)2數(shù)據(jù)，分別記為area1—area6(其中area1—area3選自數(shù)據(jù)集1，area4—area6選自數(shù)據(jù)集2)，所選區(qū)域影像如圖10(a)—(f)所示。由于篇幅限制，僅給出本文算法提取結(jié)果，如圖10(g)—(l)所示。

由圖10可知，在建筑物屋頂面面積大小、形狀變化較大，拓?fù)潢P(guān)系復(fù)雜程度不同的情況下，本文算法均能得到較好的提取結(jié)果。為更好地對(duì)比不同算法的提取結(jié)果，圖11給出了Area 1和Area 5中部分建筑物不同算法的提取結(jié)果。

對(duì)比圖11中A、B區(qū)域不同算法的提取結(jié)果可知，RG_PCA和本文算法均出現(xiàn)漏提取部分屋頂面現(xiàn)象，主要原因是漏提取的屋頂面點(diǎn)云法向量計(jì)算不準(zhǔn)確且點(diǎn)云曲率較大，RANSAC和MSAC雖提取到B區(qū)域左側(cè)屋頂面部分點(diǎn)，但難以提供可靠的屋頂面信息；RANSAC和MSAC較好地提取了C區(qū)域的建筑物屋頂面，但存在部分屋頂面過提取現(xiàn)象，由于該區(qū)域屋頂面較多且形成了較多的尖銳特征，導(dǎo)致點(diǎn)云曲率變化較大，因此RG_PCA漏提取了部分屋頂面和較多點(diǎn)云；D區(qū)域建筑物屋頂包含較多附屬物(如煙囪等)，屋頂面點(diǎn)云較為稀疏，相比其他3種算法，本文算法的提取結(jié)果較好；對(duì)于E、F區(qū)域的建筑物，RANSAC、MSAC和RG_PCA均存在明顯的誤提取，且RANSAC和MSAC存在明顯的屋頂面競(jìng)爭(zhēng)現(xiàn)象，而本文算法提取結(jié)果較好。

2.3 定量評(píng)價(jià)及分析

為定量評(píng)價(jià)本文算法的提取性能，統(tǒng)計(jì)了兩組試驗(yàn)的屋頂面提取精度及時(shí)間。屋頂面提取精度均按照式(10)計(jì)算，統(tǒng)計(jì)結(jié)果如表2所示。

圖9 試驗(yàn)1屋頂面提取結(jié)果Fig.9 Roof extraction results of the first experiment

圖10 試驗(yàn)2建筑物影像及屋頂面提取結(jié)果Fig.10 Building image and roof extraction results of the second experiment

圖11 試驗(yàn)2屋頂面提取結(jié)果對(duì)比Fig.11 Roof extraction results comparison of the second experiment

由表2可知，RANSAC、MSAC、RG_PCA和本文方法屋頂面提取正確率相差不大，但本文方法相對(duì)于其他幾種算法的完整率和提取質(zhì)量有較大提高，即本文方法漏提取和誤提取的屋頂面點(diǎn)相對(duì)較少。此外，對(duì)于屋頂結(jié)構(gòu)相對(duì)簡(jiǎn)單的建筑物，如試驗(yàn)1中建筑物3和試驗(yàn)2中的area 2和area 3，4種算法都能比較準(zhǔn)確地提取，但對(duì)于屋頂結(jié)構(gòu)復(fù)雜的建筑物，本文方法提取精度有顯著提高，該結(jié)果亦驗(yàn)證了2.2節(jié)的定性分析，同時(shí)也說明本文方法對(duì)不同復(fù)雜程度的建筑物屋頂面提取的適應(yīng)性及準(zhǔn)確性。

圖12為不同算法屋頂面提取時(shí)間統(tǒng)計(jì)結(jié)果。由圖12可知，整體上RANSAC和MSAC兩種方法算法效率相近，且提取復(fù)雜建筑物屋頂面所需時(shí)間明顯高于本文方法，RG_PCA算法效率較高，然而由2.2節(jié)和表2可知，相較于其他3種算法，RG_PCA的屋頂面提取效果和精度較差，這也進(jìn)一步說明本文方法提取復(fù)雜建筑物屋頂面的有效性。

圖12 屋頂面提取時(shí)間統(tǒng)計(jì)結(jié)果Fig.12 Roof extraction time statistics results

通過試驗(yàn)結(jié)果對(duì)比和定量評(píng)價(jià)可知，對(duì)于屋頂結(jié)構(gòu)簡(jiǎn)單的建筑物，本文方法稍優(yōu)于其他3種算法，但對(duì)于屋頂結(jié)構(gòu)復(fù)雜的建筑物，本文方法能顯著降低誤提取和漏提取屋頂面點(diǎn)云數(shù)，主要原因有：①較好地綜合利用了屋頂面點(diǎn)云的空間域和法向量特征域的特點(diǎn)，即對(duì)于法向量計(jì)算可靠的點(diǎn)云，利用LNVD-DBSCAN聚類得到較準(zhǔn)確的初始屋頂面片，對(duì)于其他點(diǎn)云，通過計(jì)算點(diǎn)到面片距離進(jìn)行處理；②采用了由粗到細(xì)的處理方式，即先提取屋頂面部分點(diǎn)云(初始屋頂面片)，然后通過面片細(xì)化處理得到建筑物所有完整屋頂面；③通過構(gòu)建鄰域投票模型，較好地解決了屋頂面競(jìng)爭(zhēng)現(xiàn)象，保證了提取屋頂面的連續(xù)性。

本文方法本質(zhì)上屬于聚類法，與其他聚類法不同的是，本文方法依據(jù)點(diǎn)云聚類后能否得到可靠結(jié)果將其分為兩部分進(jìn)行處理，較好地解決了聚類法存在的過提取和漏提取問題。文獻(xiàn)[6]作為一種能量最小化法，可同時(shí)得到所有屋頂面提取結(jié)果，但對(duì)于初始輸入中漏提取的屋頂面，無法通過后續(xù)優(yōu)化過程提?。槐疚乃惴ㄍㄟ^聚類建筑物點(diǎn)也能同時(shí)得到所有屋頂面提取結(jié)果，且對(duì)于漏提取的屋頂面，可通過面片驗(yàn)證等步驟進(jìn)行提取。文獻(xiàn)[7]作為一種剖面分析法，具有較高的屋頂面提取效率和提取準(zhǔn)確率，但難以適應(yīng)各種形狀屋頂面的提取(如長(zhǎng)條形屋頂面)，且算法涉及的部分參數(shù)(如格網(wǎng)大小和交叉線元的長(zhǎng)度)沒有明確的含義，如何設(shè)置這些參數(shù)得到最優(yōu)結(jié)果需要進(jìn)一步的探討；本文方法利用點(diǎn)云特征提取初始屋頂面片，適用于任意形狀屋頂面的提取，算法雖涉及多個(gè)參數(shù)，但各參數(shù)都有明確的含義，因此易于設(shè)置。

3 結(jié) 論

針對(duì)復(fù)雜建筑物屋頂面提取問題，本文提出了一種利用點(diǎn)云鄰域信息的建筑物屋頂面高精度自動(dòng)提取方法。試驗(yàn)結(jié)果表明，本文方法提取結(jié)果精度高，對(duì)復(fù)雜程度不同的建筑物屋頂面都能較好地提取；算法提取自動(dòng)化程度較高，適應(yīng)性較好。需要說明的是，本文方法雖涉及較多的參數(shù)，但都具有較好的適應(yīng)性，文中針對(duì)不同數(shù)據(jù)集的多個(gè)區(qū)域建筑物屋頂面提取都設(shè)置相同的取值，均能得到較好的提取結(jié)果，因此參數(shù)較多并不影響本文方法的自動(dòng)化程度和屋頂面提取精度。本文方法依賴于點(diǎn)云法向量，雖然通過選取種子點(diǎn)能得到法向量計(jì)算較為準(zhǔn)確的點(diǎn)云，但法向量的計(jì)算精度對(duì)提取結(jié)果仍然有一定的影響，因此在后續(xù)工作中需對(duì)點(diǎn)云法向量的計(jì)算進(jìn)行更多的討論，以進(jìn)一步提高屋頂面提取精度。

[1] 李怡靜, 胡翔云, 張劍清, 等. 影像與LiDAR數(shù)據(jù)信息融合復(fù)雜場(chǎng)景下的道路自動(dòng)提取[J]. 測(cè)繪學(xué)報(bào), 2012, 41(6): 870-876.

LI Yijing, HU Xiangyun, ZHANG Jianying, et al. Automatic Road Extraction in Complex Scenes Based on Information Fusion from LiDAR Data and Remote Sensing Imagery[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 870-876.

[2] 徐文學(xué), 楊必勝, 魏征, 等. 多標(biāo)記點(diǎn)過程的LiDAR點(diǎn)云數(shù)據(jù)建筑物和樹冠提取[J]. 測(cè)繪學(xué)報(bào), 2013, 42(1): 51-58.

XU Wenxue, YANG Bisheng, WEI Zheng, et al. Building and Tree Crown Extraction from LiDAR Point Cloud Data Based on Multi-marked Point Process[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1): 51-58.

[3] 龔健雅, 崔婷婷, 單杰, 等. 利用車載移動(dòng)測(cè)量數(shù)據(jù)的建筑物立面建模方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2015, 40(9): 1137-1143.

GONG Jianya, CUI Tingting, SHAN Jie, et al. A Survey on Facade Modeling Using LiDAR Point Clouds and Image Sequences Collected by Mobile Mapping Systems[J]. Geomatics and Information Science of Wuhan University, 2015, 40(9): 1137-1143.

[4] 黃先鋒, SOHN G, 王瀟, 等. 基于帶權(quán)點(diǎn)法向量的LiDAR數(shù)據(jù)屋頂檢測(cè)方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2009, 34(1): 24-27.

HUANG Xianfeng, SOHN G, WANG Xiao, et al. Roof Detection Using LiDAR Data Based on Points’ Normal with Weight[J]. Geomatics and Information Science of Wuhan University, 2009, 34(1): 24-27.

[5] XU Bo, JIANG Wanshou, SHAN Jie, et al. Investigation on the Weighted RANSAC Approaches for Building Roof Plane Segmentation from LiDAR Point Clouds[J]. Remote Sensing, 2016, 8(1): 5.

[6] YAN Jixing, SHAN Jie, JIANG Wanshou. A Global Optimization Approach to Roof Segmentation from Airborne LiDAR Point Clouds[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014(94): 183-193.

[7] WU Teng, HU Xiangyun, YE Lizhi. Fast and Accurate Plane Segmentation of Airborne LiDAR Point Cloud Using Cross-line Elements[J]. Remote Sensing, 2016, 8(5): 383.

[8] SCHNABEL R, WAHL R, KLEIN R. Efficient RANSAC for Point-cloud Shape Detection[J]. Computer Graphics Forum, 2007, 26(2): 214-226.

[9] TARSHA-KURDI F, LANDES T, GRUSSENMEYER P. Hough-transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from LiDAR Data[C]∥International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. Strasbourg: ISPRS, 2007: 407-412.

[10] VOSSELMAN G, DIJKMAN S. 3D Building Model Reconstruction from Point Clouds and Ground Plans[C]∥International Archives of Photogrammetry and Remote Sensing. Annapolis, MD, USA: ISPRS, 2001: 37-43.

[11] RABBANI T, VAN DEN HEUVEL F A, VOSSELMAN G. Segmentation of Point Clouds Using Smoothness Constraint[C]∥International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences. Delft: ISPRS, 2006: 248-253.

[12] 龐世燕, 劉亞文, 左志奇, 等. 結(jié)合區(qū)域增長(zhǎng)法和TIN邊緣分割的建筑物立面幾何特征提取[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2015, 40(1): 102-106.

PANG Shiyan, LIU Yawen, ZUO Zhiqi, et al. Combination of Region Growing and TIN Edge Segmentation for Extraction of Geometric Features on Building Facades[J]. Geomatics and Information Science of Wuhan University, 2015, 40(1): 102-106.

[13] VOSSELMAN G. Automated Planimetric Quality Control in High Accuracy Airborne Laser Scanning Surveys[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2012(74): 90-100.

[14] 高廣, 馬洪超, 張良. 利用合成算法從LiDAR數(shù)據(jù)提取屋頂面[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2014, 39(10): 1225-1230.

GAO Guang, MA Hongchao, ZHANG Liang. Automatic Extraction of Building Roofs from LiDAR Data Using a Hybridized Method[J]. Geomatics and Information Science of Wuhan University, 2014, 39(10): 1225-1230.

[15] SAMPATH A, SHAN Jie. Segmentation and Reconstruction of Polyhedral Building Roofs from Aerial LiDAR Point Clouds[J]. IEEE Transactions on Geoscience and Remote Sensing, 2010, 48(3): 1554-1567.

[16] FERRAZ A, BRETAR F, JACQUEMOUD S, et al. 3D Segmentation of Forest Structure Using a Mean-shift Based Algorithm[C]∥Proceedings of the 17th IEEE International Conference on Image Processing. Hong Kong, China: IEEE, 2010: 1413-1416.

[17] LIU Xiuping, ZHANG Jie, CAO Junjie, et al. Quality Point Cloud Normal Estimation by Guided Least Squares Representation[J]. Computers & Graphics, 2015(51): 106-116.

[18] PAULY M. Point Primitives for Interactive Modeling and Processing of 3D Geometry[D]. Zurich: ETH Zurich, 2003.

[19] 胡偉. 機(jī)載LiDAR數(shù)據(jù)三維建筑物模型重建方法研究[D]. 焦作: 河南理工大學(xué), 2012.

HU Wei. Research on 3D Building Reconstruction from Airborne LiDAR Data[D]. Jiaozuo: Henan Polytechnic University, 2012.

[20] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008, 19(1): 48-61.

SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering Algorithms Research[J]. Journal of Software, 2008, 19(1): 48-61.

[21] BIRANT D, KUT A. ST-DBSCAN: An Algorithm for Clustering Spatial-temporal Data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221.

[22] BORDOGNA G, IENCO D. Fuzzy Core DBSCAN Clustering Algorithm[C]∥LAURENT A, STRAUSS O, BOUCHON-MEUNIER B, et al. Information Processing and Management of Uncertainty in Knowledge-based Systems. Cham: Springer International Publishing, 2014: 100-109.

[23] YAN W Y, MORSY S, SHAKER A, et al. Automatic Extraction of Highway Light Poles and Towers from Mobile LiDAR Data[J]. Optics & Laser Technology, 2016, 77: 162-168.

[24] 呂峰. 利用航空影像和LiDAR點(diǎn)云進(jìn)行建筑物重建的方法研究[D]. 成都: 西南交通大學(xué), 2013.

Lü Feng. Building Reconstruction Methods Study Based on Aerial Image and LiDAR Point Cloud[D]. Chengdu: Southwest Jiaotong University, 2013.

[25] AWRANGJEB M, FRASER C S. An Automatic and Threshold-free Performance Evaluation System for Building Extraction Techniques from Airborne LiDAR Data[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 2014, 7(10): 4184-4198.

[26] ISPRS. ISPRS Test Project on Urban Classification and 3D Building Reconstruction[DB/OL]. (2016-08-13)[2016-09-28]. http:∥www2.isprs.org/commissions/comm3/wg4/detection-and-reconstruction.html.

[27] OpenTopography. NCALM Project. PI: Shane Grigsby, University of Colorado, Boulder[DB/OL]. (2016-09-10)[2016-12-10]. https:∥doi.org/10.5069/G9ZC80SR.

[28] FISCHLER M A, BOLLES, R C. Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6): 381-395.

[29] TORR P H S, ZISSERMAN A. MLESAC: A New Robust Estimator with Application to Estimating Image Geometry[J]. Computer Vision and Image Understanding, 2000, 78(1): 138-156.

Accurate and Automatic Building Roof Extraction Using Neighborhood Information of Point Clouds

ZHAO Chuan1,2,ZHANG Baoming1,CHEN Xiaowei1,2,GUO Haitao1,LU Jun1

1. Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China; 2. State Key Laboratory of Geo-information Engineering, Xi’an 710054, China

High accuracy building roof extraction from LiDAR data is the key to build topological relationship of building roofs and reconstruct buildings. Aiming at the poor adaptation and low extraction precision of existing roof extraction methods for complex building, an accurate and automatic building roof extraction method using neighborhood information of point clouds is proposed. Point clouds features are calculated by principle component analysis, and reliable seed points are selected after feature histogram construction. Initial roof surfaces are extracted quickly and precisely by the proposed local normal vector distribution density-based spatial clustering of applications with noise (LNVD-DBSCAN). Roof competition problem is solved effectively by the poll model based on neighborhood information. Experimental results show that the proposed method can extract building roofs automatically and precisely, and has preferable adaptation to buildings with different complexity, which is able to provide reliable roof information for building reconstruction.

building roofs; LiDAR data; neighborhood information; density-based clustering; point cloud; 3D building reconstruction

The National Natural Science Foundation of China (No. 41601507); The Open Research Foundation of State Key Laboratory of Geo-information Engineering (No. SKLGIE2015-M-3-3)

ZHAO Chuan(1991—),male, PhD candidate, majors in point cloud data processing and building 3D model reconstruction based on point cloud.

P237

A

1001-1595(2017)09-1123-12

國(guó)家自然科學(xué)基金(41601507);地理信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開放基金(SKLGIE2015-M-3-3)

(責(zé)任編輯：張艷玲)

2016-10-25

修回日期： 2017-08-09

趙傳(1991—)，男，博士生，研究方向?yàn)辄c(diǎn)云數(shù)據(jù)處理、基于點(diǎn)云數(shù)據(jù)的建筑物三維模型重建。

E-mail： zc_mail163@163.com