基于A*算法的遙感影像鑲嵌線檢測

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

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

0 引言

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

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

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

1 基于A*算法的數學形態學鑲嵌線檢測方法

1.1 計算差值影像

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

(1)

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

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

(2)

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

1.2 優化差值影像

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

數學形態學的膨脹和腐蝕兩個基本運算,主要用于影像上特征尺寸的增大和減少。對重疊區域的差值影像采用正方形結構元素處理時,膨脹和腐蝕運算定義如下：

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

(3)

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

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

(4)

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

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

1.3.1 A*算法原理

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

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

(5)

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

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

(6)

1.3.2 鑲嵌線檢測

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

(7)

(8)

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

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

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

(11)

式中，T為灰度閾值。

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

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

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

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

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

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

1.4 金字塔分層策略

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

圖1 金字塔結構

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

2 實驗與分析

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

2.1 重疊區域差異對比試驗

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

(a)上影像

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

(a)優化前

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

(a)優化前

(b)優化后圖4 鑲嵌結果比較

(a)優化前

(b)優化后圖5 局部鑲嵌結果比較

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

2.2 鄰域結構對比試驗

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

表1 鑲嵌線效率與節點數量統計

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

2.3 與OrthoVista對比試驗

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

圖6 對比實驗

表2 鑲嵌線效率與質量統計

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

3 結束語

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