武龍飛 盧會(huì)龍 劉金號(hào) 李玉飛

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

0 引言

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

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

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

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

1.1 計(jì)算差值影像

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

(1)

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

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

(2)

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

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

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

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

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

(3)

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

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

(4)

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

1.3 基于A*算法的檢測(cè)方法

1.3.1 A*算法原理

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

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

(5)

式中,f(n)表示為起點(diǎn)過(guò)節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估價(jià)函數(shù);g(n)表示起始點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià);h(n)是從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價(jià)。

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

(6)

1.3.2 鑲嵌線檢測(cè)

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

(7)

(8)

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

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

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

(11)

式中，T為灰度閾值。

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

(1)設(shè)定初始灰度閾值T,對(duì)于無(wú)人機(jī)影像,一般閾值T取30即可;

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

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

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

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

1.4 金字塔分層策略

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

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

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

2 實(shí)驗(yàn)與分析

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

2.1 重疊區(qū)域差異對(duì)比試驗(yàn)

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

(a)上影像

(b)下影像圖2 試驗(yàn)影像

(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ù)而且車輛形狀表示不準(zhǔn)確,導(dǎo)致檢測(cè)到的鑲嵌線穿過(guò)了2個(gè)建筑物和2輛汽車,產(chǎn)生了幾何錯(cuò)位現(xiàn)象,如圖5(a)所示。優(yōu)化后的圖3(b)中地物表示準(zhǔn)確,搜索到的鑲嵌線能夠很好地避開(kāi)建筑物區(qū)域和車輛,如圖5(b)所示,保證了鑲嵌影像的質(zhì)量,說(shuō)明本文對(duì)差值影像的優(yōu)化是有效的。

2.2 鄰域結(jié)構(gòu)對(duì)比試驗(yàn)

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

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

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

2.3 與OrthoVista對(duì)比試驗(yàn)

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

圖6 對(duì)比實(shí)驗(yàn)

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

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

3 結(jié)束語(yǔ)

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