武龍飛 盧會龍 劉金號 李玉飛

(中冀建勘集團有限公司, 河北 石家莊 050000)

0 引言

影像鑲嵌是不同時間或不同視角獲取的多幅影像通過自動計算鑲嵌線,將影像鑲嵌獲取覆蓋整個測區(qū)的影像技術(shù)[1]。影像鑲嵌能夠?qū)⒉煌暯?、不同時間拍攝的具有重疊區(qū)域的多景影像鑲嵌在一起,突破了影像拍攝時間、空間的局限性,廣泛應用于醫(yī)學影像處理、遙感影像處理、虛擬現(xiàn)實分析、計算機視覺等領(lǐng)域[2]。影像鑲嵌技術(shù)需要將具有重疊區(qū)域的影像轉(zhuǎn)換到相同坐標系下再進行鑲嵌。正射影像糾正能夠?qū)⒂跋褡鴺宿D(zhuǎn)換的指定坐標系下,能夠滿足鑲嵌處理的要求。但由于地勢起伏的影響,糾正后的正射影像中存在一定未消除投影誤差,導致鑲嵌結(jié)果存在幾何錯位現(xiàn)象。因此,為提高正射影像鑲嵌線質(zhì)量和效率同時保證自動獲取一條避免建筑物被分開成為一個熱點問題[3]。

影像鑲嵌技術(shù)由Milgram[4]首次提出,之后自動選取鑲嵌線一直是眾多學者研究的一個重要方向。Davis[5]在影像重疊區(qū)域內(nèi)采用迪杰斯特拉(Dijkstra)算法搜索差值影像的最優(yōu)鑲嵌線,但Dijkstra算法采用窮舉策略,計算量很大。王作勇等人[6]提出A*搜索算法的鑲嵌線自動提取方法,該方法利用建筑物輔助數(shù)據(jù)避免了鑲嵌線穿過建筑物。程多祥等人[7]采用蟻群算法選取最優(yōu)鑲嵌線,該算法依賴于螞蟻數(shù)目,局部搜索能力較弱。Kerschner[8]提出基于Voronoi圖的鑲嵌網(wǎng)絡生成與優(yōu)化的方法,利用數(shù)字表面模型(digital surface model,DSM)數(shù)據(jù)對鑲嵌網(wǎng)絡進行優(yōu)化調(diào)整,改方法能有效地避免網(wǎng)絡定點落在樹木、建筑物等存在高差的區(qū)域。袁修孝等人[9]通過半全局立體匹配算法獲取立體影像的視差圖,結(jié)合形態(tài)學濾波算法分離出非地面點與地面點,采用貪吃蛇搜索算法獲取鑲嵌線,該方法計算視差圖運算量比較大而且對影像輻射信息要求高。宮思偉等人[10]和陳松等人[11]分別利用DSM和激光雷達(Light Detection And Ranging,LiDAR)點云數(shù)據(jù)先進行非地面區(qū)域提取,再搜索鑲嵌線,其適用性受到輔助數(shù)據(jù)的獲取與精度的限制。

針對上述存在一定的問題,有必要研究一種滿足快速生產(chǎn)數(shù)字正射影像(digital orthophoto map，DOM)產(chǎn)品的鑲嵌線智能檢測方法。本文提出一種基于A*算法的數(shù)學形態(tài)學鑲嵌線檢測方法,根據(jù)重疊區(qū)域的差值影像搜索一條避開房屋等非地面區(qū)域的最短路徑。

1 基于A*算法的數(shù)學形態(tài)學鑲嵌線檢測方法

1.1 計算差值影像

計算鑲嵌線時,應盡量避免穿越高大地物如房屋、樹冠以及色調(diào)差異較大的區(qū)域,同時避免生成鑲嵌影像上存在地物接邊不一致以及色調(diào)存在差異等問題,確保生成影像的質(zhì)量滿足應用需求。本文利用影像的灰度差值表示重疊區(qū)域的影像差異,計算公式為

(1)

式中,g1(x,y)、g2(x,y)分別為兩幅待鑲嵌影像在重疊區(qū)域中像素(x,y)處灰度值。

對于彩色影像,本文取各波段差值的最大值表示影像差異,公式為

(2)

由于正射影像是根據(jù)數(shù)字高程模型(digital elevation model，DEM)糾正得到,高出地面的地物在正射影像上存在投影誤差,灰度差值會較大。因此差值影像可以較好地反映高大地物和色調(diào)差異較大的區(qū)域,使搜索到的鑲嵌線更好地滿足無縫鑲嵌的要求。

1.2 優(yōu)化差值影像

由于遙感影像地物復雜性,導致差值影像上存在地物邊界不清或地物邊界不連續(xù)現(xiàn)象。在實際應用中通常在差值影像上檢測鑲嵌線,會存在鑲嵌線穿過建筑物造成建筑物接邊存在誤差或建筑物表達不完整現(xiàn)象,難以獲取理想的檢測結(jié)果。本文對重疊區(qū)域的差值影像采用數(shù)學形態(tài)學方法進行改進處理,確保優(yōu)化后的差值影像即能正確的表示影像差異又能夠保證生成地物的完整性。

數(shù)學形態(tài)學的膨脹和腐蝕兩個基本運算,主要用于影像上特征尺寸的增大和減少。對重疊區(qū)域的差值影像采用正方形結(jié)構(gòu)元素處理時,膨脹和腐蝕運算定義如下：

對于重疊區(qū)域的差值影像ΔD的膨脹運算為取局部窗口內(nèi)的差值影像最大值,具體公式為

(3)

式中,(xp,yp)為差值影像上以點(x,y)中心5×5窗口內(nèi)任一點。

腐蝕運算為取局部窗口內(nèi)的差值影像最大值,具體公式為

(4)

通過膨脹運算對重疊區(qū)域差值影像處理能夠?qū)⑴R近斷開的地物進行連接,填充整個地物內(nèi)部的細小孔洞,確保鑲嵌影像上地物的完整性,避免鑲嵌線穿過存在高差的建筑物導致接邊處存在誤差。

1.3 基于A*算法的檢測方法

1.3.1 A*算法原理

A*算法是一種靜態(tài)路網(wǎng)中求最短路徑的啟發(fā)式搜索算法[12],其效果相當于找到最佳路徑的Dijkstra算法,在簡單情況下,其速度相當于廣度優(yōu)先遍歷(breath first search，BFS)算法,因此改算法具有Dijkstra算法的準確性,也具有BFS算法的效率,Dijkstra算法以初始點為目標節(jié)點進行貪婪搜索會產(chǎn)生大量的盲目搜索,而BFS算法是以目標點為結(jié)點進行貪婪搜索在遇到障礙物時不能及早躲避,而A*算法是將兩者結(jié)合以初始點和目的地之和最短進行搜索,選擇最優(yōu)路徑,減少搜索范圍、提高搜索效率。

A*算法的估價函數(shù)f(n)表示為

(5)

式中,f(n)表示為起點過節(jié)點n到目標點的估價函數(shù);g(n)表示起始點到節(jié)點n的實際代價;h(n)是從節(jié)點n到目標點的估計代價。

對A*算法中h(n)的可納性準則滿足搜索到最小點估值,即要求

(6)

1.3.2 鑲嵌線檢測

鑲嵌線檢測可以簡化為在重疊區(qū)域從起始點到目標點搜索一條影像差異最小、最短路徑優(yōu)化問題。陳松[11]等選取鑲嵌線時結(jié)合DSM數(shù)據(jù)避免障礙區(qū)域,采用歐式距離計算g(n)和h(n)值,公式為

(7)

(8)

式中，(xsta,ysta)為起點的像點坐標；(xgo,ygo)為目標點的像點坐標；(xn,yn)為過起始點與目標點路徑上任意中間節(jié)點n的坐標；D為影像格網(wǎng)分辨率。

通過式(5)、式(7)、式(8)組成A*算法鑲嵌線檢測估價函數(shù),僅能沿水平與垂直方向進行移動,算法運行效率較低且難以滿足影像無縫鑲嵌的需求。為提高搜索效率,對四鄰域搜索方向進行改進,添加對角線方向搜索采用八鄰域方法確定鄰接頂點。原有的式(7)、式(8)難以精確表示估價函數(shù)值。針對八鄰域搜索特點,本文對g(n)與h(n)的計算方法進行重新定義為

式中，hd(n)表示節(jié)點n沿對角線方向到目標點的距離；hs(n)表示除對角線行走后還需走直線距離；w(n-1,n)表示節(jié)點n與節(jié)點n-1兩節(jié)點間距離權(quán)重為

(11)

式中，T為灰度閾值。

為了減少搜索區(qū)域,本文將影像差值小于閾值T的區(qū)域內(nèi)搜索鑲嵌線,減少搜索區(qū)域的存儲空間,提高算法運算效率。A*算法在搜索過程中通過建立OPEN表記錄所有被考慮尋找最優(yōu)路徑節(jié)點,CLOSE表記錄被舍棄的路徑。在優(yōu)化重疊區(qū)域的差值影像上如圖1,設A為鑲嵌線的起點,B為目標點,綠色格子表示自由區(qū)域,灰色格子為建筑物,采用A*算法搜索從A到B最優(yōu)鑲嵌線的步驟如下：

(1)設定初始灰度閾值T,對于無人機影像,一般閾值T取30即可;

(2)將起始點A存入OPEN表,由于查找OPEN表中只有A一個節(jié)點,故將A從OPEN表中移出,存入CLOSE表。然后將節(jié)點A相鄰節(jié)點加入OPEN表內(nèi)

(3)檢查與當前節(jié)點相鄰且不在CLOSE表中的節(jié)點,計算該點與相鄰節(jié)點g(n)、h(n)、f(n)值,g(n)為當前節(jié)點n到起始點A的值,h(n)表示為當前節(jié)點n通過可通區(qū)域到目標點的值,f(n)為二者的和。

(4)選取OPEN表中f(n)值最小的節(jié)點,移除OPEN表同時設置為父節(jié)點并加入CLOSE表內(nèi)。若父節(jié)點的相鄰節(jié)點為障礙物時,不操作。否則查看是否在OPEN表內(nèi),如果不在OPEN表內(nèi),將該子節(jié)點加入OPEN表內(nèi)。若子節(jié)點在OPEN表內(nèi),則計算g(n)值并與原開啟列表的g(n)值比較大小。若當前路徑的g(n)值大于原開啟列表g(n)值,則按照原始列表關(guān)系,h(n)值不變。最后,將OPEN表中f(n)值最小的點設置為父節(jié)點,直到檢測到目標點B則完成鑲嵌線的檢測;

(5)由目標點B反向追溯父節(jié)點到A,生成最優(yōu)的鑲嵌線路徑(橙色格子)。

1.4 金字塔分層策略

由于遙感影像數(shù)據(jù)量較大,若直接在重疊區(qū)域的差值影像上進行A*算法搜索,計算量和所需內(nèi)存依然較大,本文結(jié)合影像匹配過程中金字塔匹配策略思路,采用金字塔策略進行由粗到細的鑲嵌線檢索[13]。影像金字塔是遙感影像多分辨率分析處理中常用重要結(jié)構(gòu),通過將原始影像逐步降低分辨率獲取多次度的遙感影像數(shù)據(jù)集,從上到下影像分辨率逐漸變高影像細節(jié)也逐漸清晰,如圖1所示。

圖1 金字塔結(jié)構(gòu)

金字塔分層搜索策略是一種由粗到精的搜索策略,首先,根據(jù)需要在分辨率較低的影像上進行初始搜索;然后,將搜索到的鑲嵌線同比例變換到上以分辨率影像上;最后,在鑲嵌線相鄰區(qū)域以當前節(jié)點為父節(jié)點在一定區(qū)域內(nèi)進行搜索細化,以獲取更加精準的鑲嵌線。初始搜索圖層的選擇是根據(jù)原始影像(第零層影像)大小來確定的,對于航空影像,一般可采用1∶3的分層策略,即在第三層影像進行初始搜索。采用金字塔分層策略搜索鑲嵌線,既可以避免影像較大情況下,中間數(shù)據(jù)過多造成內(nèi)存不足的現(xiàn)象,又可以提高搜索效率,滿足快速鑲嵌的要求。

2 實驗與分析

為了驗證本文算法的有效性,在Windows10 64位操作系統(tǒng)、i5-8400QM CPU、8 GB內(nèi)存的臺式機下,采用VS 2010環(huán)境下采用C++語言完成文中提出鑲嵌線檢測算法實驗。實驗影像為某城市地區(qū)一對數(shù)字正射影像,影像大小為5 548×3 863,重疊區(qū)域大小為5 352×2 269。

2.1 重疊區(qū)域差異對比試驗

為了驗證差值影像優(yōu)化的有效性,分別以優(yōu)化前和優(yōu)化后的差值影像計算代價矩陣檢測鑲嵌線,如圖2所示。圖3(a)為兩影像直接作差生成的差值影像的二值化結(jié)果,閾值T=30,圖3(b)為圖3(a)進行數(shù)學形態(tài)學膨脹處理后的結(jié)果,膨脹模板為5×5的正方形結(jié)構(gòu)元素。圖4(a)、圖4(b)分別是以圖3(a)、圖3(b)為差值影像進行鑲嵌線檢測后的鑲嵌結(jié)果。圖5(a)、圖5(b)分別是圖4(a)、圖4(b)的局部放大圖。

(a)上影像

(b)下影像圖2 試驗影像

(a)優(yōu)化前

(b)優(yōu)化后圖3 差值影像比較

(a)優(yōu)化前

(b)優(yōu)化后圖4 鑲嵌結(jié)果比較

(a)優(yōu)化前

(b)優(yōu)化后圖5 局部鑲嵌結(jié)果比較

圖3(a)中建筑物的邊界不連續(xù)而且車輛形狀表示不準確,導致檢測到的鑲嵌線穿過了2個建筑物和2輛汽車,產(chǎn)生了幾何錯位現(xiàn)象,如圖5(a)所示。優(yōu)化后的圖3(b)中地物表示準確,搜索到的鑲嵌線能夠很好地避開建筑物區(qū)域和車輛,如圖5(b)所示,保證了鑲嵌影像的質(zhì)量,說明本文對差值影像的優(yōu)化是有效的。

2.2 鄰域結(jié)構(gòu)對比試驗

為了分析本文提出算法的效率和質(zhì)量,分別利用基于四鄰域和八鄰域的A*算法在數(shù)據(jù)一上檢測鑲嵌線,并統(tǒng)計消耗時間和鑲嵌線節(jié)點數(shù)目,如表1所示。

表1 鑲嵌線效率與節(jié)點數(shù)量統(tǒng)計

由表1可知,金字塔分層搜索策略使四鄰域搜索和八鄰域的搜索效率均提高了30倍左右。同時,本文提出的基于八鄰域的A*搜索算法速度比四鄰域搜索算法快,而且在不采用金字塔分層策略搜索時,即搜索影像越大時,速度優(yōu)勢越明顯。由于本文方法可以沿對角線進行搜索,搜索到的鑲嵌線更短,鑲嵌節(jié)點更少,可以減小后續(xù)鑲嵌縫消除處理的計算量?？梢钥闯?本文提出的八鄰域搜索算法的效率和質(zhì)量均優(yōu)于四鄰域搜索算法。

2.3 與OrthoVista對比試驗

為了分析本文方法的有效性,分別利用本文方法和商業(yè)軟件OrthoVista對正射影像進行鑲嵌,如圖6所示。白色線為本文方法檢測的鑲嵌線,青色線為OrthoVista檢測的鑲嵌線。表2為兩種方法搜索鑲嵌線的效率與質(zhì)量統(tǒng)計數(shù)據(jù)。

圖6 對比實驗

表2 鑲嵌線效率與質(zhì)量統(tǒng)計

由表2可知,本文方法和OrthoVista軟件的效率相當,對數(shù)據(jù)進行處理時,OrthoVista檢測的鑲嵌線穿過了3個建筑物,而本文方法檢測的鑲嵌線繞過了建筑物,主要落在道路和草地上。相比之下,本文方法檢測的鑲嵌線具有更高的質(zhì)量。

3 結(jié)束語

本文提出一種基于A*算法的數(shù)學形態(tài)學鑲嵌線檢測方法,通過對差值影像進行數(shù)學形態(tài)學膨脹處理,能使鑲嵌線更好地避開房屋、樹冠等高出地面的地物,同時利用八鄰域和金字塔分層搜索策略,提高了鑲嵌線自動選取的效率。該方法能夠較快地檢測出一條較高質(zhì)量的最短鑲嵌線,鑲嵌線比較簡潔,能夠減少后續(xù)鑲嵌縫消除處理的計算量。