劉海兵,曲英杰,顏青松,鄧 非

武漢大學測繪學院,湖北 武漢 430079

城市場景的建筑物三維重建是當前計算機視覺、計算機圖形學和攝影測量領(lǐng)域的一個重要研究內(nèi)容,在城市規(guī)劃[1]、可視化[2]、仿真模擬[3]、導航[4]、娛樂[5]等領(lǐng)域被廣泛應(yīng)用。傳統(tǒng)的建筑物三維重建方法生成的網(wǎng)格模型準確詳細,細節(jié)豐富且能夠逼真地表示建筑物的幾何結(jié)構(gòu)特征,但稠密冗余的表示直接降低傳輸、處理以及渲染的性能,難以實時更新,不利于分析和應(yīng)用,而高保真度、低復雜度的建筑物單體結(jié)構(gòu)化模型具有更廣泛的應(yīng)用場景。

目前的建筑物單體結(jié)構(gòu)化重建方法主要從實景三維數(shù)據(jù)中提取建筑物的平面結(jié)構(gòu)、屋頂輪廓、立面輪廓、建筑物高度等幾何信息,進而恢復建筑物的幾何形狀和拓撲結(jié)構(gòu)。文獻[6]通過隨機采樣一致(random sample consensus,RANSAC)算法[7]從點云中提取平面基元,將點云的三維空間劃分為一組軸對齊盒子,通過對盒子進行篩選生成一個多邊形表面模型來近似描述建筑物,效率低且不穩(wěn)定。文獻[8]在使用RANSAC算法[7]提取平面基元的基礎(chǔ)上,通過平面基元的相交裁剪確定多邊形表面模型的候選面,在基于馬爾可夫隨機場(Markov random field,MRF)的能量方程優(yōu)化下剔除冗余面,生成一個緊湊簡潔的封閉多邊形表面模型。但由于平面相交生成了大量冗余面,只能處理復雜度較低的簡單建筑物數(shù)據(jù)。為此文獻[9]對平面基元進行自適應(yīng)的空間劃分,根據(jù)深度隱式場[10]計算其空間占有率,避免了冗余候選面的干擾。文獻[11—12]也采用規(guī)則約束和連通性分析的方法,最大程度減少了冗余候選面的數(shù)量。文獻[13]將室外場景的點云結(jié)構(gòu)化重建拓展到了室內(nèi),但點云缺失依舊是重建的難題。網(wǎng)格相比點云在噪聲和數(shù)據(jù)缺失方面都有很大的改善,文獻[14]在先驗知識和跨度約束下對網(wǎng)格以自適應(yīng)變分方法[15]檢測出地平面和立面輪廓,組合成一個完整且具有語義的多細節(jié)層次(level of details,LOD)模型[16]。對于大規(guī)模網(wǎng)格,文獻[17]利用一個結(jié)合高度和圖像特征的MRF圖割[18-19],檢測出屋頂輪廓和立面輪廓,進而生成LOD模型。在不考慮建筑物先驗知識的情況下,文獻[20]結(jié)合深度神經(jīng)網(wǎng)絡(luò)與網(wǎng)格幾何約束,從網(wǎng)格和RGB圖像、高度圖、法向圖中獲得建筑物的清晰輪廓,靈活地對復雜的建筑物進行重建。但受限于網(wǎng)格輪廓幾何特征的有限性,生成的LOD模型細節(jié)層次較低,而平面基元提取不僅可以獲取更多的幾何結(jié)構(gòu)特征,還能利用拓撲結(jié)構(gòu)。文獻[21]采用區(qū)域生長算法提取網(wǎng)格的平面基元,根據(jù)面積閾值篩選出面積較大的平面基元進行多邊形表面模型的構(gòu)建,忽略了面積較小的平面基元,導致拓撲關(guān)系不準確,影響了重建的精度。文獻[22]采用一環(huán)形鄰域三角面區(qū)域生長的方法,極大地提高了平面基元提取的準確性,但同時重建了一些錯誤的幾何結(jié)構(gòu),影響了多邊形表面模型的整體精度。

為了解決當前方法存在的問題,本文提出了一種建筑物單體結(jié)構(gòu)化重建的變尺度網(wǎng)格基元提取方法。本文工作有以下貢獻:①提出了一種多尺度區(qū)域生長算法進行網(wǎng)格平面基元的提取,完整準確地提取出不同尺度大小的幾何結(jié)構(gòu)所對應(yīng)的平面基元。②提出了一種平面基元拓撲優(yōu)化算法,面積優(yōu)先級策略有效提升了共面平面基元的合并效率。

1 單體結(jié)構(gòu)化重建算法

本文基于文獻[21]提出的Polygonization方法,進行了多尺度區(qū)域生長提取網(wǎng)格平面基元、平面基元拓撲優(yōu)化兩個方面的改進,提出了一種有效且穩(wěn)定的建筑物單體結(jié)構(gòu)化重建的變尺度網(wǎng)格基元提取方法,重建出了更簡潔緊湊的、結(jié)構(gòu)化的多邊形表面模型。本文的算法包括平面基元檢測和多邊形表面模型生成兩個步驟,如圖1所示。Polygonization方法[21]采用單一尺度的平面基元提取方法,提取的平面基元不夠完整和準確。為解決這一問題,本文提出多尺度區(qū)域生長算法和平面基元拓撲優(yōu)化方法來提升平面基元提取的完整性和準確性。

1.1 多尺度區(qū)域生長算法

平面基元的提取需要計算每個網(wǎng)格頂點的k-ring鄰域平面度[23],如圖2所示,k-ring鄰域描述了一個網(wǎng)格頂點的局部幾何信息,因此可以通過一個網(wǎng)格頂點的k-ring鄰域平面度描述其在k-ring鄰域范圍內(nèi)平面的擬合質(zhì)量[24]。計算出每一個網(wǎng)格頂點的平面度,三角面的平面度是其頂點平面度的平均值,將平面度最大的三角面作為區(qū)域生長的初始種子面。

圖2 k-ring鄰域圖

多尺度區(qū)域生長算法流程如圖3所示,首先通過檢索初始種子面k-ring鄰域三角面包含的網(wǎng)格頂點,擬合出初始參考平面,通過添加滿足距離分割閾值和角度分割閾值的k-ring鄰域三角面形成新的種子面,逐步向外擴張,重復整個過程直到將整個網(wǎng)格提取為若干平面基元,并標識不同的顏色進行可視化表示。

圖3 多尺度區(qū)域生長算法流程

由于初始網(wǎng)格表面的平坦性不足,存在大量的噪聲和幾何缺陷,因此需要適宜的距離分割閾值和角度分割閾值保證區(qū)域生長的準確性。

距離分割閾值是多尺度區(qū)域生長算法準確提取網(wǎng)格平面基元的關(guān)鍵,通過衡量種子面的k-ring鄰域三角面到參考平面的投影距離進行平面基元的提取。如果投影距離大于距離分割閾值,判定該三角面不屬于當前平面基元。通常情況下,網(wǎng)格的平均邊長是距離分割閾值一個很好的參考數(shù)值,但對于所有建筑物網(wǎng)格模型而言,并非總能取得最優(yōu)的平面基元提取結(jié)果。因此根據(jù)網(wǎng)格三角面的尺度規(guī)模大小,按照式(1)構(gòu)建距離分割閾值,以平均邊長作為基本參考數(shù)值,通過調(diào)整系數(shù)控制距離分割閾值的大小

(1)

式中,ei是三角面的邊長;n是三角面邊的數(shù)量;a是調(diào)整系數(shù),本文通常情況下a設(shè)定為1。

角度分割閾值通過衡量種子面的k-ring鄰域三角面與參考平面的法向夾角進行平面基元的提取,如果夾角大于角度分割閾值,判定該三角面不屬于當前平面基元。一個適宜的角度分割閾值在多尺度區(qū)域生長過程中既能保證降低網(wǎng)格表面噪聲對平面基元提取的影響,又能準確地識別出平面基元的邊界,角度分割閾值按照式(2)進行構(gòu)建

例2 “平面外一條直線與此平面內(nèi)的一條直線平行，則該直線與此平面平行”是一個復合命題，其正確的命題網(wǎng)絡(luò)表征如圖1所示.

|n1·n2|

(2)

式中,n1和n2分別是參考平面和三角面經(jīng)過歸一化后的法向量;θ是角度閾值,由于建筑物網(wǎng)格模型表面并不平坦,因此本文角度分割閾值通常情況下設(shè)定為30°。

第一次區(qū)域生長采用的距離分割閾值難以提取尺度較小的平面基元。為此,本文首先設(shè)定適宜的面積閾值將尺度較大的平面基元篩選出來,對尺度較小的幾何結(jié)構(gòu)所對應(yīng)的平面基元進行第二次區(qū)域生長。第二次區(qū)域生長的距離分割閾值由剩余的三角面邊長重新計算,而角度分割閾值不變。

面積閾值的確定采用最大類間方差法(OSTU)[25]圖像灰度分割算法的原理,將平面基元的面積值分成一大一小兩類,保證類間方差最大化,有效地對平面基元進行篩選。首先將平面基元按照面積值從大到小進行排序,令{S1,S2,S3,…,SN}表示排序后N個平面基元的面積值,假設(shè)選擇一個閾值Sk(SN

σ2=P1(m1-m)2+P2(m2-m)2

(3)

即m1和m2兩個均值隔得越遠,σ2越大,兩個部分的差異性越大,越能有效地將平面基元按照面積值分成兩部分。

如圖4所示,多尺度區(qū)域生長算法采用不同大小的距離分割閾值分兩次從網(wǎng)格中提取平面基元,有效解決了單一尺度區(qū)域生長算法提取網(wǎng)格平面基元不準確、不規(guī)則的問題,更完整準確地從網(wǎng)格不同尺度大小的幾何結(jié)構(gòu)中提取出對應(yīng)的平面基元。

圖4 多尺度區(qū)域生長效果

1.2 平面基元拓撲優(yōu)化

平面基元拓撲優(yōu)化包括兩個內(nèi)容:合并共面的平面基元及恢復平面基元的鄰接關(guān)系。Polygoniza-tion方法[21]窮舉所有的平面進行合并,計算復雜度高。而本文采用面積優(yōu)先級策略(圖5),減少平面基元的遍歷次數(shù),提高合并的效率。具體如下:①首先計算平面基元的面積,按照面積從大到小進行優(yōu)先級排序;②選擇面積最大的平面基元作為初始平面基元,按照優(yōu)先級逐一去遍歷其他平面基元,計算兩個平面基元之間的投影距離和法向夾角,將滿足距離閾值(參照式(1))和角度閾值(設(shè)為10°)的平面基元與初始平面基元進行合并;③未滿足合并條件的平面基元重新篩選出優(yōu)先級最高的作為初始平面基元,繼續(xù)按照優(yōu)先級執(zhí)行合并;直到完成所有共面平面基元的合并。

平面基元之間的鄰接關(guān)系需要依靠三角面來確定,具體過程如圖6所示。只要兩個平面基元之間存在至少一個公共的網(wǎng)格頂點,就認為它們是相鄰的?；謴推矫婊g的鄰接關(guān)系,保證拓撲完整準確,這對后續(xù)確定建筑物的輪廓至關(guān)重要。

圖6 恢復平面基元的鄰接關(guān)系

1.3 多邊形表面模型生成

如圖7所示,根據(jù)平面基元之間的鄰接關(guān)系,本文構(gòu)建一個結(jié)構(gòu)圖來存儲平面基元。結(jié)構(gòu)圖中的每一個頂點對應(yīng)于一個平面基元,而如果兩個頂點對應(yīng)的平面基元相鄰,則用一條邊進行相連。為了更加準確有效地生成候選面,將結(jié)構(gòu)圖中的平面基元擬合成平面,通過平面的相交裁剪確定建筑物的輪廓,進而生成候選面。最終通過MRF的能量方程優(yōu)化從候選面中篩選出一組最優(yōu)的平面生成水密流形的多邊形表面模型。

圖7 多邊形表面模型生成

2 試驗結(jié)果與分析

為了驗證本文建筑物單體結(jié)構(gòu)化重建的變尺度網(wǎng)格基元提取方法的有效性,在Windows10操作系統(tǒng)下,采用計算機硬件配置如下:3.20 GHz Intel Core i7-8700 CPU、64 GB RAM,使用C++實現(xiàn)了本文的方法,并對一組城市場景的建筑物網(wǎng)格模型進行了試驗。

2.1 試驗結(jié)果

試驗結(jié)果如圖8所示,第一列輸入的原始網(wǎng)格是通過文獻[26]的方法創(chuàng)建的單個非封閉建筑物網(wǎng)格,網(wǎng)格的復雜程度從網(wǎng)格a—網(wǎng)格f逐漸遞增,噪聲也隨之遞增。第二列是采用二次度量誤差(quadic error metrics,QEM)[27]網(wǎng)格簡化算法進行簡化的效果,第三列是采用Polygonization方法[21]生成的多邊形表面模型,第四列是本文方法生成的多邊形表面模型。

圖8 試驗結(jié)果

QEM算法對于噪聲較少且比較簡單的網(wǎng)格a和網(wǎng)格b,簡化效果還比較規(guī)則準確;但面對復雜且噪聲較多的網(wǎng)格c—f,簡化后的網(wǎng)格表面凹凸不平,輪廓邊界很不規(guī)則,甚至出現(xiàn)了變形。采用Polygonization方法能夠較為規(guī)則準確地重建出尺度較大的建筑物主體結(jié)構(gòu),但對于尺度較小且復雜的幾何結(jié)構(gòu),極易重建錯誤甚至無法重建。而本文方法有效地改善了這一情況,從網(wǎng)格a—f,不僅規(guī)則準確地重建出了尺度較大的建筑物主體結(jié)構(gòu),尺度較小且復雜的幾何結(jié)構(gòu)也能夠重建出來,具備了更豐富的結(jié)構(gòu)特征。

計算Hausdorff距離[28]評估多邊形表面模型與原始網(wǎng)格的近似程度即模型精確度,如表1所示。表1中藍色表示多邊形表面模型與原始網(wǎng)格之間誤差較小,紅色則表示誤差較大?？梢园l(fā)現(xiàn),相比Polygonization方法[21],本文重建出的多邊形表面模型與原始網(wǎng)格之間存在較小的誤差,RMSE值更小,具備更高的精確度,較為準確地恢復了建筑物的幾何結(jié)構(gòu),且具備較強的噪聲抗干擾能力。

表1 模型精確度

圖9通過比較每一階段的時間成本進行重建效率的對比。由于多尺度區(qū)域生長算法提取到數(shù)量更多的平面基元,因此時間成本略高;但通過本文的平面基元拓撲優(yōu)化,更多的平面基元卻耗費了更短的時間,更高效地完成了平面基元的拓撲優(yōu)化,效率提升明顯;由于生成的平面較多,在模型生成階段耗費了較多的時間進行篩選,但總時長相比Polygonization方法仍有明顯的優(yōu)勢。

圖9 模型的重建效率比較

多邊形表面模型的三角面數(shù)量如表2所示,本文方法最大程度地實現(xiàn)了數(shù)據(jù)量的壓縮,相比網(wǎng)格而言,更加輕量化,簡化率低于0.5%,仍能夠準確規(guī)則地描述建筑物的幾何結(jié)構(gòu)。雖然三角面數(shù)量比Polygonization方法略高一點,這是由于本文方法生成的模型保留了尺度較小的幾何結(jié)構(gòu),細節(jié)方面更加豐富。

表2 模型的三角面數(shù)量

2.2 多尺度區(qū)域生長的影響

2.2.1k-ring鄰域選擇

本文對k-ring鄰域在平面基元提取過程中的影響進行了定性分析(表3)。如表3所示,1-ring和2-ring鄰域由于包含數(shù)量較少的網(wǎng)格頂點,局部平面擬合過程缺乏強有力的約束條件,對噪聲過于敏感,因此平面基元的邊界不能清晰完整地檢測出來,導致平面基元提取錯誤,RMSE值較大,降低了多邊形表面模型的重建精度。相對來說3-ring和4-ring鄰域的局部平面擬合質(zhì)量較高,能夠準確地檢測出平面基元的邊界,可靠地引導多尺度區(qū)域生長算法進行平面基元的提取,RMSE值較小,重建的多邊形表面模型更加精確;但4-ring鄰域相比3-ring鄰域效果上并沒有很大的提升,效率上卻降低了很多,因此本文試驗均采用3-ring鄰域。

表3 k-ring鄰域的影響

2.2.2 多尺度區(qū)域生長的影響

為了突出體現(xiàn)多尺度區(qū)域生長算法的有效性,本文進行了多尺度與單一尺度區(qū)域生長算法的對比試驗(圖10)。通過圖10可以發(fā)現(xiàn)單一尺度區(qū)域生長算法由于將噪聲和幾何缺陷也提取到平面基元中,導致提取的平面基元并不準確規(guī)則,建筑物尺度較小的幾何結(jié)構(gòu)損失嚴重,直接降低了多邊形表面模型的重建精度,甚至會導致重建失敗。相比之下,多尺度區(qū)域生長算法降低了噪聲和幾何缺陷的影響,能夠準確完整地提取出女兒墻、煙囪、多層屋頂、配電箱等尺度較小的幾何結(jié)構(gòu)所對應(yīng)的平面基元,平面基元的邊界處也更加準確規(guī)則,損失了較少的幾何結(jié)構(gòu)特征,能夠更穩(wěn)健地對建筑物網(wǎng)格模型進行平面基元的提取。

圖10 多尺度區(qū)域生長的影響

2.3 平面基元拓撲優(yōu)化的影響

平面基元拓撲優(yōu)化過程中,本文通過面積優(yōu)先級策略合并共面的平面基元,減少平面基元的遍歷次數(shù),有效提高了合并效率。為了更直觀地突出面積優(yōu)先級策略的效率提升,本文進行了的對比試驗。由于合并效率和平面基元的數(shù)量有關(guān),因此試驗采用的網(wǎng)格具備不同數(shù)量的平面基元,試驗結(jié)果如圖11所示。通過圖11可以發(fā)現(xiàn),面積優(yōu)先級策略相比窮舉方法,計算復雜度低,合并效率明顯提升,在本文試驗所用的網(wǎng)格上提高了5～10倍。

圖11 合并共面平面基元的效率對比

2.4 限制因素

本文方法依賴平面基元提取的準確性和完整性。如圖12所示,由于網(wǎng)格的分辨率有限,一些幾何結(jié)構(gòu)只由幾個三角面組成,在幾何結(jié)構(gòu)極其復雜或過于平滑的區(qū)域,平面基元的提取并不準確;而且網(wǎng)格表面曲率逐漸變化的弧形結(jié)構(gòu)也很難準確地用平面去近似表示,因此就會丟失幾何結(jié)構(gòu)特征,影響重建的精度。在平面基元拓撲優(yōu)化方面,本文采用的面積優(yōu)先級策略雖然提高了效率,但并沒有采用多線程等高性能計算技術(shù),如果網(wǎng)格的幾何結(jié)構(gòu)過于復雜,效率并不突出。

圖12 不準確的平面基元

3 結(jié) 論

本文提出了一種建筑物單體結(jié)構(gòu)化重建的變尺度網(wǎng)格基元提取方法,生成的多邊形表面模型在精確度和細節(jié)層次方面有了一定程度上的提升。多尺度區(qū)域生長算法有效解決了單一尺度區(qū)域生長算法提取平面基元不準確、邊界不規(guī)則的問題,能夠完整準確地從網(wǎng)格不同尺度的幾何結(jié)構(gòu)中提取出平面基元,降低了結(jié)構(gòu)特征的損失,增強了噪聲的抗干擾能力;并通過平面基元拓撲優(yōu)化進一步改善平面基元的質(zhì)量,其中面積優(yōu)先級策略有效地提高了共面平面基元5～10倍的合并效率。但本文的方法仍有一些亟待改進之處,后續(xù)工作會進一步優(yōu)化現(xiàn)有的算法,實現(xiàn)高效率高精度的建筑物單體結(jié)構(gòu)化重建。