馬東嶺,王曉坤,李廣云
(1. 信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州 450001; 2. 山東建筑大學(xué)測(cè)繪地理信息學(xué)院,山東 濟(jì)南 250101)
智慧城市的建立需要城市真三維模型作為數(shù)據(jù)基礎(chǔ)[1]。現(xiàn)行建立城市三維模型的方法主要有手工建模、三維激光掃描儀建模、利用多視影像建模。手工建模是指利用類似于3ds Max等建模軟件[2]以及最初的測(cè)量數(shù)據(jù)進(jìn)行建模[3]。通常,手工建模具有模型美觀、單體化好等優(yōu)勢(shì),但建模速度慢、周期性長(zhǎng)[4],且有輕重區(qū)分,將不重要的模型建成白模型。因此,該種建模方式并不能夠兼顧效率和質(zhì)量,只能用于城市重要建筑的精細(xì)建模。為了提高建模效率,利用三維掃描技術(shù)進(jìn)行三維重建已應(yīng)用于多個(gè)領(lǐng)域[5],如古建筑三維重建、邊坡監(jiān)測(cè)等。由于利用三維激光掃描技術(shù)進(jìn)行三維重建需要像全站儀一樣設(shè)站,因此該種建模方式對(duì)于大場(chǎng)景、大區(qū)域的復(fù)雜城市進(jìn)行三維重建的效率依舊不能滿足要求。近幾年由于無(wú)人機(jī)(UAV)技術(shù)[6]的迅猛發(fā)展,無(wú)人機(jī)傾斜攝影以其高效便捷、成本低廉的優(yōu)勢(shì)成為城市區(qū)域攝影測(cè)量的主要手段。在這種情況下,基于傾斜影像的城市三維重建成為研究熱點(diǎn)。而如何利用傾斜影像獲得的密集點(diǎn)云來(lái)構(gòu)建密集點(diǎn)云表面模型是基于傾斜影像進(jìn)行三維重建的核心問(wèn)題之一。
針對(duì)密集點(diǎn)云表面模型重建,國(guó)內(nèi)外已有大量學(xué)者進(jìn)行了相關(guān)研究。其中,文獻(xiàn)[7]提出了一種基于體素的重建方法——Marching Cubes算法,該算法是在每一個(gè)體素中抽取相應(yīng)的等值面的算法;文獻(xiàn)[8]提出了一種基于物體中軸線轉(zhuǎn)換來(lái)擬合表達(dá)物體表面的Power Crust的重建算法;文獻(xiàn)[9]在IMLS方法[10]基礎(chǔ)上提出了基于擬合代數(shù)球面的移動(dòng)最小二乘表面重建算法——APSS算法;文獻(xiàn)[11]提出了一種基于隱式曲面方程的重建方法——Poisson算法,該算法是通過(guò)隱式曲面方程的重建來(lái)解決表面重建問(wèn)題;文獻(xiàn)[12]在研究二維構(gòu)網(wǎng)生長(zhǎng)算法及現(xiàn)有空間三維構(gòu)網(wǎng)方法的基礎(chǔ)上,提出了利用空間三角形的法向量實(shí)現(xiàn)三維構(gòu)網(wǎng);文獻(xiàn)[13]提出了一種無(wú)需對(duì)離散點(diǎn)集所對(duì)應(yīng)的自由曲面進(jìn)行分片投影的生長(zhǎng)算法;文獻(xiàn)[14]利用球面投影實(shí)現(xiàn)激光掃描點(diǎn)云數(shù)據(jù)的三維構(gòu)網(wǎng)方法。針對(duì)城市建模特點(diǎn),有學(xué)者專門研究符合城市特點(diǎn)的建模方法。針對(duì)城市模型存在直角拐角多、拐點(diǎn)不容易捕捉的問(wèn)題,文獻(xiàn)[15]提出了符合城市模型的區(qū)域生長(zhǎng)算法;針對(duì)城市區(qū)域的地形特征,文獻(xiàn)[16]提出了顧及地形的城市三維可視化方法。雖然以上方法能夠完成對(duì)城市區(qū)域的三維重建,但是仍存在城市區(qū)域建模效率偏低、建模效果不理想等問(wèn)題,因此尋找一種更為理想的表面模型重建方法迫在眉睫。本文以城市區(qū)域?yàn)槔脽o(wú)人機(jī)獲取傾斜影像,并對(duì)傾斜影像進(jìn)行預(yù)處理得到目標(biāo)區(qū)域的三維密集點(diǎn)云,在此基礎(chǔ)上利用圖割算法對(duì)點(diǎn)云進(jìn)行表面模型重建。本文提出的方法在城市區(qū)域密集點(diǎn)云表面模型重建中具有建模效果好、建模效率高的優(yōu)勢(shì)。
圖割算法是一種基于圖論的能量?jī)?yōu)化算法[17],該方法將目標(biāo)構(gòu)成一幅網(wǎng)格圖的形式,并建立相應(yīng)的能量方程,運(yùn)用求最大流最小割的方式獲取網(wǎng)格圖的最優(yōu)化分割來(lái)獲取最優(yōu)化結(jié)果。利用圖割方法解決問(wèn)題需將待分割的目標(biāo)群體作為圖割算法網(wǎng)格圖的頂點(diǎn)[18],并將待分割的目標(biāo)群體的相關(guān)關(guān)系作為圖割算法網(wǎng)格圖的邊。由于圖割問(wèn)題存在目標(biāo)和背景兩種關(guān)系,因此除了待分割的目標(biāo)群體外,還有代表目標(biāo)的匯節(jié)點(diǎn)和代表背景的源節(jié)點(diǎn)。利用圖中邊集合的一個(gè)子集作為割集合,其代價(jià)就是邊子集中所有元素的權(quán)值的和。割集合即指將該集合中所有邊打斷會(huì)導(dǎo)致圖割網(wǎng)格圖的分開(kāi)。如果一個(gè)割集合的元素所有權(quán)值之和最小,那么這個(gè)集合就稱為最小割,也即圖割的結(jié)果。根據(jù)福特-富克森定理,網(wǎng)路的最大流max-flow等于最小割min-cut。因此max-flow/min-cut算法就可以用來(lái)獲得s-t圖的最小割。
本文將密集點(diǎn)云表面模型重建問(wèn)題轉(zhuǎn)換為利用圖割方法選取最優(yōu)四面體問(wèn)題。由于利用圖割方法解決問(wèn)題需要建立相應(yīng)的圖結(jié)構(gòu),因此本文將密集點(diǎn)云構(gòu)成的四面體作為圖的節(jié)點(diǎn),四面體之間的相鄰三角面作為圖的邊。除此之外,還需要給定相應(yīng)的節(jié)點(diǎn)權(quán)值和邊的權(quán)值,其中節(jié)點(diǎn)的權(quán)值為表面可見(jiàn)性Evis(S),邊的權(quán)值為光澤一致性Ephoto(S)和表面平滑度Earea(S)。建立能量函數(shù)方程
E(S)=Evis(S)+λphotoEphoto(S)+λareaEarea(S)
(1)
式中,λphoto和λarea為相應(yīng)的正權(quán)重。通過(guò)求解圖的最小割來(lái)保證上述方程達(dá)到的最小值,進(jìn)而選出最佳的表面四面體和對(duì)應(yīng)的表面三角形。
在構(gòu)建小四面體時(shí),每個(gè)頂點(diǎn)需要保留一些可見(jiàn)性信息。若該點(diǎn)是通過(guò)多次合并獲取的,則該點(diǎn)至少保留兩個(gè)原始點(diǎn)的可視性信息。這個(gè)信息決定了節(jié)點(diǎn)可視性,如果某個(gè)四面體的頂點(diǎn)屬于最終表面,那么應(yīng)該在它所來(lái)自的視圖中是可見(jiàn)的。這種情況說(shuō)明,當(dāng)一個(gè)頂點(diǎn)到攝像機(jī)中心的射線與一個(gè)標(biāo)記為內(nèi)側(cè)的四面體相交時(shí),它們就會(huì)發(fā)生沖突。因此,用Evis(S)表示當(dāng)一條光線從攝像機(jī)中心的射線穿過(guò)在表面的四面體時(shí),穿入穿出時(shí)就會(huì)發(fā)生能量變化。但是,這樣的能量項(xiàng)不適合圖割算法,因?yàn)樗枰獔D中兩個(gè)以上節(jié)點(diǎn)之間的復(fù)雜交互。相反,射線從內(nèi)部射到相機(jī)中心,經(jīng)過(guò)若干個(gè)三角面片,穿出可視面片時(shí),能量發(fā)生變化,相機(jī)中心發(fā)出的光線與小四面體上的三角面的交點(diǎn)到該三角面相對(duì)的頂點(diǎn)的距離的函數(shù)作為四面體權(quán)值。表面可見(jiàn)性為
(2)
式中,v為光線與重建三角面的交點(diǎn);D(v)為交點(diǎn)到該三角面相對(duì)頂點(diǎn)距離的函數(shù)。
光澤一致性項(xiàng)Ephoto(S)是指給定表面S與所看到的不同輸入圖像的匹配程度[19]。因此,表面光澤一致性項(xiàng)為
(3)
式中,ρ(T)是指每個(gè)三角形的可視信息量的多少,由3個(gè)頂點(diǎn)共有的可視信息給定;A(T)為根據(jù)三角形面積給定的權(quán)值。
通過(guò)減少單個(gè)三角形表面面積來(lái)改善表面平滑性。因此,表面平滑度能量為
(4)
在表面S上的三角形T,A(T)為根據(jù)三角形面積給定的權(quán)值,并通過(guò)A(T)給圖中每一條邊賦值。
試驗(yàn)數(shù)據(jù)采用城市地區(qū)的無(wú)人機(jī)傾斜影像數(shù)據(jù)。計(jì)算機(jī)硬件環(huán)境為Intel Core i3 CPU 2.4 GHz、軟件環(huán)境為SGM和GodWork。首先,通過(guò)GodWork軟件對(duì)無(wú)人機(jī)傾斜影像數(shù)據(jù)進(jìn)行空三解算;然后,利用SGM算法對(duì)空三解算后的影像進(jìn)行多視密集匹配,生成試驗(yàn)需要的三維密集點(diǎn)云;最后,利用本文提出的圖割算法來(lái)構(gòu)建密集點(diǎn)云表面模型。流程如圖1所示。
將無(wú)人機(jī)傾斜影像加載到GodWork軟件中,通過(guò)軟件計(jì)算影像的空三結(jié)果,并將糾正后的影像及影像的空三結(jié)果導(dǎo)入SGM軟件中。通過(guò)SGM灰度匹配的方法將空三測(cè)量產(chǎn)生的稀疏點(diǎn)云生成為三維密集點(diǎn)云。
本文方法是在三維點(diǎn)云中添加一些結(jié)構(gòu),同時(shí)高效地聚合頂點(diǎn)中的相近頂點(diǎn),這是通過(guò)逐步構(gòu)建三維點(diǎn)集的Delaunay三角剖分來(lái)完成的。三角測(cè)量的每個(gè)頂點(diǎn)不僅存儲(chǔ)其位置,而且還保存其起源的關(guān)鍵點(diǎn)列表。每次從原始三維點(diǎn)云中選擇一個(gè)候選點(diǎn),就可以找到它在三角測(cè)量中最近的鄰居點(diǎn),計(jì)算兩個(gè)三維點(diǎn)之間的投影誤差。這可能會(huì)出現(xiàn)兩種不同的情況:如果重投影誤差在某個(gè)閾值以上,則將該候選點(diǎn)視為不同的點(diǎn)并插入到Delaunay三角剖分中;相反,如果誤差小于閾值,則在Delaunay三角剖分中不插入該候選點(diǎn),而是更新最近的頂點(diǎn)。過(guò)程如圖2所示。
利用本文提出的方法對(duì)密集點(diǎn)云構(gòu)成的小四面體的三角面進(jìn)行選取,通過(guò)求解圖割問(wèn)題最小割的方式,獲取哪些面屬于密集點(diǎn)云表面模型,并將這些面重建為密集點(diǎn)云表面模型。
通過(guò)上述方法重建的模型表面如圖3所示。
由試驗(yàn)結(jié)果可以看出,該算法獲取的三維密集點(diǎn)云表面模型保持了建筑物的棱角,并且將建筑物的屋頂裝飾提取了出來(lái),極大地還原了真實(shí)建筑的幾何結(jié)構(gòu)信息。對(duì)于有樹(shù)木遮擋的地方,通過(guò)本文方法重建的模型能夠較好地表達(dá)出建筑和樹(shù)木。為進(jìn)一步驗(yàn)證本文方法的有效性,將本文方法與MVE表面重建方法進(jìn)行了對(duì)比,如圖4所示。
經(jīng)過(guò)對(duì)比可以看出,MVE重建方法在環(huán)境復(fù)雜的區(qū)域重建效果不好,沒(méi)有有效的區(qū)分出墻面和其他的噪音點(diǎn)。而本文方法可以在環(huán)境復(fù)雜的情況下,完整地表達(dá)城市區(qū)域建筑物的三維表面,清晰地重現(xiàn)建筑物的細(xì)節(jié)特征。對(duì)于點(diǎn)云分布散亂的情況,該算法識(shí)別模型表面能力強(qiáng),可以有效地標(biāo)識(shí)出墻面和散亂點(diǎn)云。本文方法通過(guò)更加合理的選取規(guī)則,盡可能避開(kāi)了大三角形的選取,構(gòu)建的密集點(diǎn)云表面模型更加符合現(xiàn)實(shí)狀況。試驗(yàn)結(jié)果統(tǒng)計(jì)數(shù)據(jù)對(duì)比見(jiàn)表1。
表1 研究區(qū)域試驗(yàn)結(jié)果對(duì)比
通過(guò)對(duì)比試驗(yàn)結(jié)果統(tǒng)計(jì)數(shù)據(jù),本文方法生成的三維點(diǎn)云表面模型比MVE重建方法生成的三維點(diǎn)云表面模型的節(jié)點(diǎn)和面更多,說(shuō)明本文方法選取的三角面更小,細(xì)節(jié)表達(dá)更詳細(xì)。相比于MVE重建方法的用時(shí),本文方法用時(shí)更短,體現(xiàn)了本文算法建模效率高的特點(diǎn)。
通過(guò)試驗(yàn)發(fā)現(xiàn),本文提出的城市密集點(diǎn)云表面模型重建方法的模型重建效果更理想,能夠正確重建出建筑物、路面、樹(shù)木等地形地物。通過(guò)該算法重建出的模型建筑細(xì)節(jié)豐富,建筑物、植被分界清晰,證明該方法建模效率高、可行性高、重建效果好。同時(shí),由于該算法相比于其他方法的運(yùn)行時(shí)間短,因此解決了城市密集點(diǎn)云表面模型重建中存在的建模效率低的難題,大大提高了無(wú)人機(jī)傾斜影像在城市三維模型重建中的實(shí)用性和使用價(jià)值。
本文根據(jù)城市密集點(diǎn)云的數(shù)據(jù)特性,提出了一種基于圖割理論的城市密集點(diǎn)云表面模型重建方法。通過(guò)對(duì)無(wú)人機(jī)傾斜影像進(jìn)行數(shù)據(jù)預(yù)處理獲取目標(biāo)的密集點(diǎn)云,然后對(duì)預(yù)處理生成的密集點(diǎn)云插入連接邊生成四面體,并將四面體及相鄰三角面構(gòu)成圖割問(wèn)題,通過(guò)求解這個(gè)圖割問(wèn)題獲取密集點(diǎn)云的最優(yōu)表面模型。利用該方法對(duì)一個(gè)比較復(fù)雜的場(chǎng)景點(diǎn)云數(shù)據(jù)進(jìn)行試驗(yàn),完整地重建了該地區(qū)的密集點(diǎn)云表面模型。試驗(yàn)結(jié)果表明,該方法重建效果好、重建速度快,重建出的建筑物幾何特征結(jié)構(gòu)清晰。對(duì)比于其他方法,該方法在點(diǎn)云雜亂的地區(qū)也可以完成點(diǎn)云模型表面重建。由于傾斜影像存在較大的透視變形、分辨率差異以及密集點(diǎn)云存在噪聲和遮擋等問(wèn)題,如何進(jìn)一步在密集點(diǎn)云表面模型重建中去除這些錯(cuò)誤將是下一步研究的重點(diǎn)。