利用圖割算法進行城市密集點云表面模型重建

馬東嶺，王曉坤，李廣云

(1. 信息工程大學地理空間信息學院，河南 鄭州 450001； 2. 山東建筑大學測繪地理信息學院，山東 濟南 250101)

智慧城市的建立需要城市真三維模型作為數據基礎[1]。現行建立城市三維模型的方法主要有手工建模、三維激光掃描儀建模、利用多視影像建模。手工建模是指利用類似于3ds Max等建模軟件[2]以及最初的測量數據進行建模[3]。通常，手工建模具有模型美觀、單體化好等優(yōu)勢，但建模速度慢、周期性長[4]，且有輕重區(qū)分，將不重要的模型建成白模型。因此，該種建模方式并不能夠兼顧效率和質量，只能用于城市重要建筑的精細建模。為了提高建模效率，利用三維掃描技術進行三維重建已應用于多個領域[5]，如古建筑三維重建、邊坡監(jiān)測等。由于利用三維激光掃描技術進行三維重建需要像全站儀一樣設站，因此該種建模方式對于大場景、大區(qū)域的復雜城市進行三維重建的效率依舊不能滿足要求。近幾年由于無人機(UAV)技術[6]的迅猛發(fā)展，無人機傾斜攝影以其高效便捷、成本低廉的優(yōu)勢成為城市區(qū)域攝影測量的主要手段。在這種情況下，基于傾斜影像的城市三維重建成為研究熱點。而如何利用傾斜影像獲得的密集點云來構建密集點云表面模型是基于傾斜影像進行三維重建的核心問題之一。

針對密集點云表面模型重建，國內外已有大量學者進行了相關研究。其中，文獻[7]提出了一種基于體素的重建方法——Marching Cubes算法，該算法是在每一個體素中抽取相應的等值面的算法；文獻[8]提出了一種基于物體中軸線轉換來擬合表達物體表面的Power Crust的重建算法；文獻[9]在IMLS方法[10]基礎上提出了基于擬合代數球面的移動最小二乘表面重建算法——APSS算法；文獻[11]提出了一種基于隱式曲面方程的重建方法——Poisson算法，該算法是通過隱式曲面方程的重建來解決表面重建問題；文獻[12]在研究二維構網生長算法及現有空間三維構網方法的基礎上，提出了利用空間三角形的法向量實現三維構網；文獻[13]提出了一種無需對離散點集所對應的自由曲面進行分片投影的生長算法；文獻[14]利用球面投影實現激光掃描點云數據的三維構網方法。針對城市建模特點，有學者專門研究符合城市特點的建模方法。針對城市模型存在直角拐角多、拐點不容易捕捉的問題，文獻[15]提出了符合城市模型的區(qū)域生長算法；針對城市區(qū)域的地形特征，文獻[16]提出了顧及地形的城市三維可視化方法。雖然以上方法能夠完成對城市區(qū)域的三維重建，但是仍存在城市區(qū)域建模效率偏低、建模效果不理想等問題，因此尋找一種更為理想的表面模型重建方法迫在眉睫。本文以城市區(qū)域為例，利用無人機獲取傾斜影像，并對傾斜影像進行預處理得到目標區(qū)域的三維密集點云，在此基礎上利用圖割算法對點云進行表面模型重建。本文提出的方法在城市區(qū)域密集點云表面模型重建中具有建模效果好、建模效率高的優(yōu)勢。

1 圖割理論

圖割算法是一種基于圖論的能量優(yōu)化算法[17]，該方法將目標構成一幅網格圖的形式，并建立相應的能量方程，運用求最大流最小割的方式獲取網格圖的最優(yōu)化分割來獲取最優(yōu)化結果。利用圖割方法解決問題需將待分割的目標群體作為圖割算法網格圖的頂點[18]，并將待分割的目標群體的相關關系作為圖割算法網格圖的邊。由于圖割問題存在目標和背景兩種關系，因此除了待分割的目標群體外，還有代表目標的匯節(jié)點和代表背景的源節(jié)點。利用圖中邊集合的一個子集作為割集合，其代價就是邊子集中所有元素的權值的和。割集合即指將該集合中所有邊打斷會導致圖割網格圖的分開。如果一個割集合的元素所有權值之和最小，那么這個集合就稱為最小割，也即圖割的結果。根據福特-富克森定理，網路的最大流max-flow等于最小割min-cut。因此max-flow/min-cut算法就可以用來獲得s-t圖的最小割。

2 密集點云表面模型重建方法

本文將密集點云表面模型重建問題轉換為利用圖割方法選取最優(yōu)四面體問題。由于利用圖割方法解決問題需要建立相應的圖結構，因此本文將密集點云構成的四面體作為圖的節(jié)點，四面體之間的相鄰三角面作為圖的邊。除此之外，還需要給定相應的節(jié)點權值和邊的權值，其中節(jié)點的權值為表面可見性Evis(S)，邊的權值為光澤一致性Ephoto(S)和表面平滑度Earea(S)。建立能量函數方程

E(S)=Evis(S)+λphotoEphoto(S)+λareaEarea(S)

(1)

式中，λphoto和λarea為相應的正權重。通過求解圖的最小割來保證上述方程達到的最小值，進而選出最佳的表面四面體和對應的表面三角形。

2.1 表面可見性Evis(S)

在構建小四面體時，每個頂點需要保留一些可見性信息。若該點是通過多次合并獲取的，則該點至少保留兩個原始點的可視性信息。這個信息決定了節(jié)點可視性，如果某個四面體的頂點屬于最終表面，那么應該在它所來自的視圖中是可見的。這種情況說明，當一個頂點到攝像機中心的射線與一個標記為內側的四面體相交時，它們就會發(fā)生沖突。因此，用Evis(S)表示當一條光線從攝像機中心的射線穿過在表面的四面體時，穿入穿出時就會發(fā)生能量變化。但是，這樣的能量項不適合圖割算法，因為它需要圖中兩個以上節(jié)點之間的復雜交互。相反，射線從內部射到相機中心，經過若干個三角面片，穿出可視面片時，能量發(fā)生變化，相機中心發(fā)出的光線與小四面體上的三角面的交點到該三角面相對的頂點的距離的函數作為四面體權值。表面可見性為

(2)

式中，v為光線與重建三角面的交點；D(v)為交點到該三角面相對頂點距離的函數。

2.2 光澤一致性Ephoto(S)

光澤一致性項Ephoto(S)是指給定表面S與所看到的不同輸入圖像的匹配程度[19]。因此，表面光澤一致性項為

(3)

式中，ρ(T)是指每個三角形的可視信息量的多少，由3個頂點共有的可視信息給定；A(T)為根據三角形面積給定的權值。

2.3 表面平滑度Earea(S)

通過減少單個三角形表面面積來改善表面平滑性。因此，表面平滑度能量為

(4)

在表面S上的三角形T，A(T)為根據三角形面積給定的權值，并通過A(T)給圖中每一條邊賦值。

3 試驗與結果分析

試驗數據采用城市地區(qū)的無人機傾斜影像數據。計算機硬件環(huán)境為Intel Core i3 CPU 2.4 GHz、軟件環(huán)境為SGM和GodWork。首先，通過GodWork軟件對無人機傾斜影像數據進行空三解算；然后，利用SGM算法對空三解算后的影像進行多視密集匹配，生成試驗需要的三維密集點云；最后，利用本文提出的圖割算法來構建密集點云表面模型。流程如圖1所示。

3.1 空三解算及生成點云

將無人機傾斜影像加載到GodWork軟件中，通過軟件計算影像的空三結果，并將糾正后的影像及影像的空三結果導入SGM軟件中。通過SGM灰度匹配的方法將空三測量產生的稀疏點云生成為三維密集點云。

3.2 給密集點云添加結構

本文方法是在三維點云中添加一些結構，同時高效地聚合頂點中的相近頂點，這是通過逐步構建三維點集的Delaunay三角剖分來完成的。三角測量的每個頂點不僅存儲其位置，而且還保存其起源的關鍵點列表。每次從原始三維點云中選擇一個候選點，就可以找到它在三角測量中最近的鄰居點，計算兩個三維點之間的投影誤差。這可能會出現兩種不同的情況：如果重投影誤差在某個閾值以上，則將該候選點視為不同的點并插入到Delaunay三角剖分中；相反，如果誤差小于閾值，則在Delaunay三角剖分中不插入該候選點，而是更新最近的頂點。過程如圖2所示。

3.3 對密集點云進行表面模型重建

利用本文提出的方法對密集點云構成的小四面體的三角面進行選取，通過求解圖割問題最小割的方式，獲取哪些面屬于密集點云表面模型，并將這些面重建為密集點云表面模型。

通過上述方法重建的模型表面如圖3所示。

由試驗結果可以看出，該算法獲取的三維密集點云表面模型保持了建筑物的棱角，并且將建筑物的屋頂裝飾提取了出來，極大地還原了真實建筑的幾何結構信息。對于有樹木遮擋的地方，通過本文方法重建的模型能夠較好地表達出建筑和樹木。為進一步驗證本文方法的有效性，將本文方法與MVE表面重建方法進行了對比，如圖4所示。

經過對比可以看出，MVE重建方法在環(huán)境復雜的區(qū)域重建效果不好，沒有有效的區(qū)分出墻面和其他的噪音點。而本文方法可以在環(huán)境復雜的情況下，完整地表達城市區(qū)域建筑物的三維表面，清晰地重現建筑物的細節(jié)特征。對于點云分布散亂的情況，該算法識別模型表面能力強，可以有效地標識出墻面和散亂點云。本文方法通過更加合理的選取規(guī)則，盡可能避開了大三角形的選取，構建的密集點云表面模型更加符合現實狀況。試驗結果統(tǒng)計數據對比見表1。

表1 研究區(qū)域試驗結果對比

通過對比試驗結果統(tǒng)計數據，本文方法生成的三維點云表面模型比MVE重建方法生成的三維點云表面模型的節(jié)點和面更多，說明本文方法選取的三角面更小，細節(jié)表達更詳細。相比于MVE重建方法的用時，本文方法用時更短，體現了本文算法建模效率高的特點。

通過試驗發(fā)現，本文提出的城市密集點云表面模型重建方法的模型重建效果更理想，能夠正確重建出建筑物、路面、樹木等地形地物。通過該算法重建出的模型建筑細節(jié)豐富，建筑物、植被分界清晰，證明該方法建模效率高、可行性高、重建效果好。同時，由于該算法相比于其他方法的運行時間短，因此解決了城市密集點云表面模型重建中存在的建模效率低的難題，大大提高了無人機傾斜影像在城市三維模型重建中的實用性和使用價值。

4 結 語

本文根據城市密集點云的數據特性，提出了一種基于圖割理論的城市密集點云表面模型重建方法。通過對無人機傾斜影像進行數據預處理獲取目標的密集點云，然后對預處理生成的密集點云插入連接邊生成四面體，并將四面體及相鄰三角面構成圖割問題，通過求解這個圖割問題獲取密集點云的最優(yōu)表面模型。利用該方法對一個比較復雜的場景點云數據進行試驗，完整地重建了該地區(qū)的密集點云表面模型。試驗結果表明，該方法重建效果好、重建速度快，重建出的建筑物幾何特征結構清晰。對比于其他方法，該方法在點云雜亂的地區(qū)也可以完成點云模型表面重建。由于傾斜影像存在較大的透視變形、分辨率差異以及密集點云存在噪聲和遮擋等問題，如何進一步在密集點云表面模型重建中去除這些錯誤將是下一步研究的重點。