一種用于建筑物立面邊界特征點(diǎn)提取的凸包三角網(wǎng)算法

熊 峰，李宗春，付永健，何 華

(信息工程大學(xué) 地理空間信息學(xué)院，鄭州 450001)

隨著智慧城市、建筑信息模型(building information modeling, BIM)、城市信息模型(city information modeling, CIM)等概念的提出和空間數(shù)據(jù)獲取技術(shù)的深度發(fā)展，準(zhǔn)確高效地重建城市三維模型,從而實(shí)現(xiàn)三維現(xiàn)實(shí)世界的準(zhǔn)確理解和精細(xì)表達(dá)逐漸成為當(dāng)下的發(fā)展趨勢(shì)和研究熱點(diǎn)[1-3]。建筑物作為城市場(chǎng)景中的主要構(gòu)成成分，建筑物幾何模型的重建研究得到了廣泛的關(guān)注和發(fā)展[4]。

地面激光掃描(terrestrial laser scanning, TLS)系統(tǒng)是建筑物模型重建中數(shù)據(jù)獲取的重要來源，能快速采集包含大量細(xì)節(jié)特征(如門窗等)的建筑物立面點(diǎn)云數(shù)據(jù)，從而對(duì)機(jī)載建筑點(diǎn)云進(jìn)行有效的補(bǔ)充和擴(kuò)展[4-5]。建筑物立面結(jié)構(gòu)線的自動(dòng)獲取不僅能簡(jiǎn)化建筑物的形狀結(jié)構(gòu)和復(fù)雜的拓?fù)潢P(guān)系，而且可用于建筑物立面重建等工作中。因此，有效挖掘并提取建筑物立面結(jié)構(gòu)線具有十分重要的意義。

按照文獻(xiàn)[6]的定義，建筑物結(jié)構(gòu)線可分為邊界線和折疊線，如圖1所示。結(jié)構(gòu)線提取的關(guān)鍵在于對(duì)屬于邊界線和折疊線上的特征點(diǎn)進(jìn)行判斷和定位，文中主要針對(duì)邊界特征點(diǎn)進(jìn)行探討和研究。目前，國(guó)內(nèi)外學(xué)者針對(duì)建筑物立面邊界特征點(diǎn)提取已展開了大量研究，現(xiàn)有的提取方法大致可歸納為三類：①基于圖像的方法[7-10]。通常是將三維點(diǎn)云轉(zhuǎn)換成二維圖像，然后應(yīng)用圖像處理的方法檢測(cè)邊界特征點(diǎn)。該方法雖可以充分利用圖像領(lǐng)域中成熟的邊界提取技術(shù)，但在轉(zhuǎn)換過程中易丟失三維信息，存在一定的精度損失。②基于平面的方法[11-14]。此類方法先將建筑物點(diǎn)云數(shù)據(jù)分割為不同的平面，再提取每個(gè)平面的邊界點(diǎn)，從而實(shí)現(xiàn)邊界特征點(diǎn)的提取。該方法在平面特征顯著的情況下提取結(jié)果較好，但其傾向于擬合成較大平面，容易丟失較多的細(xì)節(jié)。③基于點(diǎn)的方法[15-18]。一般是通過局部特征直接從原始建筑物點(diǎn)云數(shù)據(jù)中提取邊界特征點(diǎn)。該方法能充分挖掘特征點(diǎn)的幾何拓?fù)潢P(guān)系，但抗噪性差，提取結(jié)果十分依賴局部特征的選取。

圖1 建筑物立面結(jié)構(gòu)線示意圖

凸包(Convex Hull)[19]自提出以來被廣泛用于不同數(shù)據(jù)的邊界點(diǎn)提取。在建筑物邊界特征點(diǎn)提取方面，Sampath等[20]改進(jìn)了凸包算法，首先選擇點(diǎn)云數(shù)據(jù)的坐標(biāo)極值點(diǎn)為初始邊界點(diǎn)，然后依次求解各點(diǎn)鄰域內(nèi)與某一方向夾角最大或最小的點(diǎn)作為下一個(gè)邊界點(diǎn)，直至提取出機(jī)載點(diǎn)云中建筑物外邊界特征點(diǎn)，但無法提取出內(nèi)邊界特征點(diǎn)，且一次僅能處理單一建筑物點(diǎn)云數(shù)據(jù)；龐世燕等[12]在提取出建筑物立面點(diǎn)云中的平面特征的前提下，通過構(gòu)建三角網(wǎng)將三角形連接數(shù)較少的點(diǎn)作為候選邊界點(diǎn)來提高凸包算法提取邊界特征點(diǎn)的速度和穩(wěn)定性，但其仍不能直接提取立面內(nèi)邊界特征點(diǎn)。Tseng等[21]首先提取出機(jī)載建筑物點(diǎn)云，然后進(jìn)行分割處理，再利用文獻(xiàn)[20]中改進(jìn)的凸包算法提取出邊界特征點(diǎn)，但依舊無法處理建筑物點(diǎn)云內(nèi)部存在孔洞的情況。對(duì)此，文中針對(duì)現(xiàn)有算法較難提取出建筑物立面點(diǎn)云中的邊界特征點(diǎn)、提取效果差等問題，提出一種構(gòu)建凸包三角網(wǎng)的建筑物立面邊界特征點(diǎn)提取方法，首先對(duì)各點(diǎn)及其近鄰點(diǎn)進(jìn)行投影與坐標(biāo)轉(zhuǎn)換，然后利用凸包算法初步提取邊界特征點(diǎn)后，對(duì)剩余點(diǎn)的凸包建立三角網(wǎng)，統(tǒng)計(jì)近鄰點(diǎn)在各三角形中的占比率以及各三角形的頂角大小，以此來篩選出建筑物立面點(diǎn)云中其余邊界特征點(diǎn)。

1 本文方法

由于點(diǎn)云數(shù)據(jù)中各點(diǎn)之間不具備空間拓?fù)潢P(guān)系，對(duì)任一目標(biāo)點(diǎn)是否為邊界特征點(diǎn)的判定可以依據(jù)該目標(biāo)點(diǎn)的近鄰點(diǎn)幾何特性來判定[6]。文中通過分析邊界特征點(diǎn)與非邊界特征點(diǎn)之間的鄰域幾何拓?fù)洳顒e，借助凸包算法等理論提出一種新的邊界特征點(diǎn)提取方法，具體技術(shù)路線如圖2所示。

圖2 文中方法技術(shù)路線

1.1 近鄰點(diǎn)投影與坐標(biāo)轉(zhuǎn)換

(1)

(2)

(3)

經(jīng)過上述步驟，獲得了目標(biāo)點(diǎn)O0在擬合平面的近鄰?fù)队包c(diǎn)。隨后，選用基于羅德里格旋轉(zhuǎn)公式將三維平面旋轉(zhuǎn)至與xoy平面平行。主要步驟如下：

Step1：依據(jù)目標(biāo)點(diǎn)法向量n0與xoy平面法向量nz=(0,0,1)計(jì)算旋轉(zhuǎn)角φ及旋轉(zhuǎn)軸l。

(4)

Step2：基于旋轉(zhuǎn)角φ和旋轉(zhuǎn)軸l=(p,q,t)按照羅德里格公式求解旋轉(zhuǎn)矩陣R。

(5)

Step3：左乘旋轉(zhuǎn)矩陣得到平行于xoy面的近鄰?fù)队包c(diǎn)

(6)

近鄰點(diǎn)投影與坐標(biāo)轉(zhuǎn)換過程如圖3所示。

圖3 近鄰點(diǎn)投影與坐標(biāo)轉(zhuǎn)換示意圖

1.2 邊界特征點(diǎn)提取

二維凸包是幾何計(jì)算中普遍采用的一種結(jié)構(gòu)計(jì)算辦法，若平面上存在有限個(gè)點(diǎn)的點(diǎn)集S，其凸包是包含S的最小凸多邊形[22]。在1.1節(jié)中，已將各點(diǎn)的近鄰點(diǎn)轉(zhuǎn)換為平面點(diǎn)集，在此基礎(chǔ)上，用凸包思想分析各點(diǎn)的鄰域幾何拓?fù)潢P(guān)系，可以發(fā)現(xiàn)：在理想情況下，邊界特征點(diǎn)呈連續(xù)的直線分布，以近鄰點(diǎn)數(shù)k=12為例，繪制的邊界特征點(diǎn)及內(nèi)點(diǎn)(非邊界特征點(diǎn))的凸包如圖4所示，利用邊界特征點(diǎn)的近鄰點(diǎn)所求得的凸包點(diǎn)集包含該邊界特征點(diǎn)，而內(nèi)點(diǎn)的凸包點(diǎn)集不會(huì)包含該內(nèi)點(diǎn)。在實(shí)際的數(shù)據(jù)采集過程中，獲取的點(diǎn)云數(shù)據(jù)不均勻，其邊界特征點(diǎn)往往是紊亂的，潛在邊界特征點(diǎn)及內(nèi)點(diǎn)(非潛在邊界特征點(diǎn))的凸包如圖5所示，利用潛在邊界特征點(diǎn)的近鄰點(diǎn)所求得的凸包點(diǎn)集難以包含該潛在邊界特征點(diǎn)，且內(nèi)點(diǎn)的凸包點(diǎn)集仍不會(huì)包含該內(nèi)點(diǎn)。

圖4 理想情況下的凸包求解示意圖

圖5 一般情況下的凸包求解示意圖

但潛在邊界特征點(diǎn)靠近附近邊界特征點(diǎn)，其近鄰點(diǎn)分布仍具有偏向一側(cè)的特性，且與附近邊界特征點(diǎn)的連線間存在一個(gè)較大的夾角。如圖6所示，潛在邊界特征點(diǎn)O與附近邊界特征點(diǎn)A和特征點(diǎn)B連線間的夾角，比內(nèi)點(diǎn)O′與附近邊界特征點(diǎn)C和特征點(diǎn)D連線之間的夾角大一些。

因此，為盡可能提取出能描述邊界特性的潛在邊界特征點(diǎn)，文中以目標(biāo)點(diǎn)為中心，構(gòu)建凸包三角網(wǎng)(在圖5的基礎(chǔ)上構(gòu)建的凸包三角網(wǎng)如圖6所示)，通過定義三角網(wǎng)中近鄰點(diǎn)在各三角形中的占比率δm(m為三角形編號(hào))和以目標(biāo)點(diǎn)為頂點(diǎn)的三角形的頂角值φm來描述潛在邊界特征點(diǎn)的特性，即潛在邊界特征點(diǎn)越靠近附近邊界特征點(diǎn)，其近鄰點(diǎn)在三角形中的δm越低，且φm越大。

(7)

式中:k為目標(biāo)點(diǎn)的近鄰點(diǎn)數(shù)量；tm為近鄰點(diǎn)在編號(hào)為m的三角形中的數(shù)量。

綜上所述，文中提取邊界特征點(diǎn)的主要步驟如下：

Step1：求解各點(diǎn)的近鄰點(diǎn)集并進(jìn)行投影和坐標(biāo)轉(zhuǎn)換，基于凸包算法[23]求解各點(diǎn)的近鄰點(diǎn)經(jīng)投影及坐標(biāo)轉(zhuǎn)換后的凸包點(diǎn)集。若目標(biāo)點(diǎn)屬于該點(diǎn)集，則該點(diǎn)為邊界特征點(diǎn)，否則構(gòu)建凸包三角網(wǎng)進(jìn)一步予以判斷。

Step2：在Step1的基礎(chǔ)上，計(jì)算各三角形中近鄰點(diǎn)占比率δm，并統(tǒng)計(jì)各三角形的頂角值φm。

Step3：若各三角網(wǎng)的δm均大于占比率閾值δ0(見圖6)，則認(rèn)為該點(diǎn)的近鄰點(diǎn)均勻分布在該目標(biāo)點(diǎn)附近，直接判定該點(diǎn)為內(nèi)點(diǎn)(如圖6(b)所示內(nèi)點(diǎn)凸包三角網(wǎng)，設(shè)置較小的δ0時(shí)各三角形中近鄰點(diǎn)占比率)；對(duì)小于占比率閾值δ0的三角形統(tǒng)計(jì)得到最大頂角值φp(如圖6(a)所示潛在邊界特征點(diǎn)的凸包三角網(wǎng)，當(dāng)存在①號(hào)和②號(hào)等多個(gè)三角形占比率均小于閾值δ0，采用最大頂角值進(jìn)行下一步篩選)，如果φp大于等于角度閾值φ0，則認(rèn)為該點(diǎn)為邊界特征點(diǎn)，否則為非邊界特征點(diǎn)。

圖6 一般情況下的凸包三角網(wǎng)構(gòu)建示意圖

2 試驗(yàn)與分析

2.1 試驗(yàn)平臺(tái)與數(shù)據(jù)

試驗(yàn)均在Intel(R) Core(TM)i7-8700 CPU @ 3.20GHz RAM 8GB的計(jì)算機(jī)上展開。選取一組模型采樣點(diǎn)云數(shù)據(jù)及四組實(shí)測(cè)點(diǎn)云數(shù)據(jù)以驗(yàn)證方法的有效性，其中，Data1、Data2、Data4數(shù)據(jù)是使用Riegl VZ-400地面激光掃描儀在某學(xué)校校園采集得到的局部建筑物立面點(diǎn)云數(shù)據(jù)；Data3數(shù)據(jù)是參考文獻(xiàn)[24]中的方法通過構(gòu)建建筑物立面BIM模型生成的點(diǎn)云數(shù)據(jù)，數(shù)據(jù)分布情況較為理想；Data5數(shù)據(jù)是從開源數(shù)據(jù)集Robotic 3D Scan Repsitory-12中選取的某一建筑物立面數(shù)據(jù)，該立面存在較多不規(guī)則局部凸起，數(shù)據(jù)分布情況較為復(fù)雜。5組試驗(yàn)數(shù)據(jù)相關(guān)信息如表1所示。

表1 試驗(yàn)數(shù)據(jù)相關(guān)信息

2.2 評(píng)價(jià)指標(biāo)

為定量評(píng)價(jià)文中方法的性能，采用簡(jiǎn)化率(simplification rate, SR)以及精度P、召回率R和F1得分4個(gè)指標(biāo)對(duì)建筑物立面邊界特征點(diǎn)提取結(jié)果進(jìn)行評(píng)價(jià)，具體計(jì)算方法見式(8)。

(8)

式中:NB為文中方法提取的建筑物立面邊界特征點(diǎn)數(shù)量；N0為文中建筑物立面點(diǎn)云總數(shù)；TP為文中方法正確提取的建筑物立面邊界特征點(diǎn)數(shù)量；FP為文中方法錯(cuò)誤提取的建筑物立面邊界特征點(diǎn)數(shù)量；FN為文中方法未提取出的建筑物立面邊界特征點(diǎn)數(shù)量。

2.3 參數(shù)設(shè)置

利用文中方法從試驗(yàn)數(shù)據(jù)中提取建筑物立面邊界特征點(diǎn)，涉及的參數(shù)主要有近鄰點(diǎn)數(shù)量k、三角網(wǎng)中近鄰點(diǎn)的占比率閾值δ0、角度閾值φ0。近鄰點(diǎn)數(shù)量k是用來定義每個(gè)目標(biāo)點(diǎn)的近鄰點(diǎn)個(gè)數(shù)的參數(shù)；占比率閾值δ0是用來判斷是否為邊界特征點(diǎn)的重要指標(biāo)，用于描述目標(biāo)點(diǎn)的近鄰點(diǎn)集的分布情況，即潛在邊界點(diǎn)越靠近附近邊界特征點(diǎn)，該三角網(wǎng)中的近鄰點(diǎn)越少，對(duì)應(yīng)的占比率越低，因此，閾值一般選擇較小值；角度閾值φ0是在滿足占比率閾值δ0的前提下進(jìn)一步篩選的參數(shù)，角度越大，說明越靠近附近邊界特征點(diǎn)，即可能是潛在邊界特征點(diǎn)。表2為文中5組試驗(yàn)對(duì)應(yīng)的參數(shù)設(shè)置，其中，Data1、Data2數(shù)據(jù)較為理想，對(duì)應(yīng)的參數(shù)設(shè)置是在已知真值的前提下依據(jù)評(píng)價(jià)指標(biāo)獲得的，其他數(shù)據(jù)的參數(shù)設(shè)置均為目測(cè)較好的試驗(yàn)結(jié)果對(duì)應(yīng)的參數(shù)。

2.4 定量試驗(yàn)

為驗(yàn)證和評(píng)價(jià)文中方法的性能，利用Data1和Data2實(shí)測(cè)點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)。兩組點(diǎn)云數(shù)據(jù)分布較為規(guī)則，以人工提取最外側(cè)的邊界特征點(diǎn)作為真值。引入文獻(xiàn)[20]中改進(jìn)的凸包算法、文獻(xiàn)[17]中基于點(diǎn)的邊界特征點(diǎn)提取方法與文中方法進(jìn)行對(duì)比分析，文獻(xiàn)[20]中通過改進(jìn)凸包算法，逐點(diǎn)判斷當(dāng)前點(diǎn)與近鄰點(diǎn)的連線和某一固定方向之間的夾角來尋找邊界特征點(diǎn)，文獻(xiàn)[17]中針對(duì)邊界特征點(diǎn)提出了一種簡(jiǎn)單有效的檢測(cè)方法，即通過計(jì)算每個(gè)點(diǎn)的近鄰點(diǎn)集的重心點(diǎn)到當(dāng)前點(diǎn)的距離來判定是否為邊界特征點(diǎn)。表3統(tǒng)計(jì)了文獻(xiàn)[20]、文獻(xiàn)[17]方法和文中方法對(duì)兩組點(diǎn)云數(shù)據(jù)的邊界特征點(diǎn)提取前后的點(diǎn)云數(shù)量、簡(jiǎn)化率SR、精度P、召回率R和F1得分，提取效果如圖7和圖8所示。

表2 文中方法試驗(yàn)參數(shù)設(shè)置

表3 兩種點(diǎn)云數(shù)據(jù)定量評(píng)價(jià)結(jié)果

圖7 Data1提取結(jié)果

圖8 Data2提取結(jié)果

綜合分析表3和圖7～8，可以發(fā)現(xiàn)：

1) Data1、Data2分別為曲面和平面類型點(diǎn)云數(shù)據(jù)，3種方法均能提取出兩種立面形狀的邊界特征點(diǎn)，但文獻(xiàn)[20]方法無法提取出立面內(nèi)邊界特征點(diǎn)(如圖8(c)橢圓圈所示)，另外，由于拐角處邊界特征點(diǎn)(如圖8(d)圓圈中的拐角處)的重心點(diǎn)與特征點(diǎn)之間的距離相較于其他特征點(diǎn)小一些，文獻(xiàn)[17]方法難以很好地提取出拐角處邊界特征點(diǎn)。

2)3種方法均具有較高的簡(jiǎn)化率，能使原始點(diǎn)云數(shù)據(jù)得到很好簡(jiǎn)化。結(jié)合F1得分指標(biāo)來看，文中方法在簡(jiǎn)化數(shù)據(jù)的同時(shí)，能較好地保留邊界特征信息，達(dá)到更好的提取效果。需要說明的是，文獻(xiàn)[20]方法在Data2中的簡(jiǎn)化率較高的原因在于該方法漏提取了內(nèi)邊界特征點(diǎn)；

3)文中方法在精度、召回率和F1得分3個(gè)指標(biāo)的綜合表現(xiàn)上優(yōu)于文獻(xiàn)[20]和文獻(xiàn)[17]方法，提取結(jié)果與人工提取的邊界特征點(diǎn)達(dá)到了很高的吻合度，可以提取出較為顯著的邊界特征點(diǎn)。但文中方法需要逐點(diǎn)判斷，無法與文獻(xiàn)[17]方法一樣實(shí)現(xiàn)批量處理，因此較耗時(shí)。

2.5 對(duì)比試驗(yàn)

為進(jìn)一步展示建筑物立面邊界特征點(diǎn)提取效果，分別采用文獻(xiàn)[20]、文獻(xiàn)[17]方法以及文中方法對(duì)Data3、Data4、Data5進(jìn)行邊界特征點(diǎn)提取，提取結(jié)果如圖9～11所示。

圖9 Data3提取結(jié)果對(duì)比

圖10 Data4提取結(jié)果對(duì)比

圖11 Data5提取結(jié)果對(duì)比

由圖9～11的提取結(jié)果可知，文獻(xiàn)[20]方法僅能提取出建筑立面的外邊界特征點(diǎn)，而文中方法與文獻(xiàn)[17]方法均能對(duì)建筑立面內(nèi)外邊界特征點(diǎn)進(jìn)行有效提取，可以較直觀地反映出建筑物立面的形狀結(jié)構(gòu)，其中，Data3、Data4的邊界特征點(diǎn)提取效果相當(dāng)，但對(duì)于Data5，文獻(xiàn)[17]方法漏提取或誤提取現(xiàn)象較為嚴(yán)重，如圖11(c)所示，提取的邊界特征點(diǎn)明顯存在邊界缺失或局部誤提取的現(xiàn)象，而文中方法提取結(jié)果較為完整，提取出的邊界特征點(diǎn)較為準(zhǔn)確。分析其原因主要是，文獻(xiàn)[17]基于距離指標(biāo)的判斷方法更適用于點(diǎn)云規(guī)則分布的平面邊界特征點(diǎn)的檢測(cè)，對(duì)于點(diǎn)云密度差異明顯的建筑物立面難以設(shè)置合適的距離閾值，因此容易出現(xiàn)邊界缺失或局部誤提取的現(xiàn)象；而文中方法對(duì)近鄰點(diǎn)進(jìn)行了坐標(biāo)投影和轉(zhuǎn)換操作且采用占比率和角度指標(biāo)，受局部凸起和點(diǎn)云密度不一的影響更小一些。

3 結(jié)束語

文中針對(duì)建筑物立面重建的現(xiàn)實(shí)需求，以地面LiDAR點(diǎn)云數(shù)據(jù)為研究對(duì)象，基于傳統(tǒng)的凸包算法，提出了一種用于建筑物立面邊界特征點(diǎn)提取的凸包三角網(wǎng)方法。選取模型采樣點(diǎn)云數(shù)據(jù)及不同類型、不同密度的實(shí)測(cè)建筑立面點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn)，結(jié)果表明，文中方法能有效提取出建筑立面邊界特征點(diǎn)，較好地保留了特征信息，并且不易受立面類型不同和點(diǎn)云密度變化的影響，具有較強(qiáng)的適應(yīng)性，可為建筑物結(jié)構(gòu)線的提取以及建筑物立面建模提供前期保障。但所提方法需要逐點(diǎn)判斷、較為耗時(shí)，下一步將繼續(xù)優(yōu)化方法，降低時(shí)間成本。