最短路徑原理正射影像鑲嵌線(xiàn)自動(dòng)提取

岳貴杰1，杜黎明2，項(xiàng)琳3，李健3，張剛3

(1.首都師范大學(xué) 資源環(huán)境與旅游學(xué)院，北京 100048；2.河南城建學(xué)院測(cè)繪工程學(xué)院，河南 平頂山 467036；3.中國(guó)測(cè)繪科學(xué)研究院，北京 100039)

摘要：正射影像鑲嵌過(guò)程中，鑲嵌線(xiàn)的選取是一個(gè)重要的步驟，其自動(dòng)化程度是影響全自動(dòng)鑲嵌的一個(gè)重要因素。本文提出一種基于圖論最短路徑原理的正射影像鑲嵌線(xiàn)自動(dòng)提取方法。該算法將圖像上提取得到的底層視覺(jué)信息(Canny邊緣)作為鑲嵌過(guò)程中的障礙物信息，在邊緣圖像上根據(jù)像素點(diǎn)的鄰接關(guān)系構(gòu)建帶權(quán)有向圖，利用初始鑲嵌線(xiàn)作為初始條件計(jì)算圖中有向邊的權(quán)值，將正射影像鑲嵌線(xiàn)的提取過(guò)程轉(zhuǎn)化為圖論中最短路徑問(wèn)題。實(shí)驗(yàn)表明，該算法可以較為準(zhǔn)確提取鑲嵌線(xiàn)，對(duì)全自動(dòng)鑲嵌具有重要應(yīng)用價(jià)值。

關(guān)鍵詞：正射影像；鑲嵌線(xiàn)；帶權(quán)有向圖；最短路徑

doi:10.3969/j.issn.1000-3177.2015.01.006

中圖分類(lèi)號(hào)：P237文獻(xiàn)標(biāo)識(shí)碼：A

收稿日期：2013-11-19修訂日期：2014-01-09

基金項(xiàng)目：國(guó)家科技支撐計(jì)劃課題(2012BAJ23B05)。

作者簡(jiǎn)介：張栩然(1987～)，男，博士研究生，主要從事遙感和地理信息系統(tǒng)應(yīng)用研究。

通訊作者：宮阿都(1976～)，男，副教授，主要從事紅外遙感研究。

Automatic Seamline Extraction for Orthophoto Mosaicking

Based on Shortest Path Method

YUE Gui-jie1，DU Li-ming2，XIANG Lin3，LI Jian3，ZHANG Gang3

(1.CollegeofResourcesandEnvironment，CapitalNormalUniversity，Beijing100048；

2.HenanUniversityofUrbanConstruction，SchoolofSurveyingEngineering，Pingdingshan467036；

3.ChineseAcademyofSurveyingandMapping，Beijing100039)

Abstract：Seamlines extractions are important step during DOM mosaicking，which is an important factor for automatic processing.An automatic seamline extraction algorithm for orthophoto mosaicking based on shortest path method is introduced.The algorithm regards low-level vision information (Canny edge) as obstacles information during mosaicking processing，constructs weighted directed graph using Canny edge image according pixels’ neighbors，calculates weight for directed edge in graph by initial seamline，and converts seamline extraction for orthophoto mosaicking to shortest path problem.Result shows that the algorithm can extract seamline precisely，and is useful for automatic DOM mosaicking processing.

Key words：digital orthophoto map；seamline；weighted directed graph；shortest path

1引言

在正射影像的鑲嵌過(guò)程中，一個(gè)重要的步驟是進(jìn)行鑲嵌線(xiàn)的選取。鑲嵌線(xiàn)應(yīng)盡可能地避免穿過(guò)房屋、樹(shù)木等高出地面的區(qū)域[1-2]，其提取方法是影響自動(dòng)化鑲嵌一個(gè)重要因素。國(guó)內(nèi)傳統(tǒng)數(shù)字?jǐn)z影測(cè)量軟件如JX4、Virtuzo等通常采用手工的方法繪制鑲嵌線(xiàn)，工作強(qiáng)度大、效率低。新一代基于網(wǎng)格的數(shù)字?jǐn)z影測(cè)量系統(tǒng)如DPGRID Mapping采用基于蟻群算法的鑲嵌線(xiàn)自動(dòng)提取算法[1]，該算法將重疊區(qū)域差值影像上灰度值大于閾值的點(diǎn)作為可能的障礙物區(qū)域，在搜索過(guò)程中采用蟻群算法基于輪盤(pán)賭原理進(jìn)行局部尋優(yōu)提取鑲嵌線(xiàn)，其實(shí)現(xiàn)過(guò)程中存在閾值、搜索次數(shù)及算法收斂性難以確定等問(wèn)題。Jaechoon Chon等提出一種基于Dijkstra算法的鑲嵌線(xiàn)自動(dòng)提取算法[3]，該算法中權(quán)值確定復(fù)雜。除此以外，還有基于Twin Snake的算法[4]、基于灰色理論的方法[5]等。

正射影像鑲嵌線(xiàn)自動(dòng)提取的問(wèn)題可歸結(jié)為兩個(gè)方面：正射影像中障礙物的識(shí)別(房屋、樹(shù)木等高出地面的物體)和最優(yōu)路徑的提取。理論上來(lái)講，給定障礙物條件，應(yīng)該得到滿(mǎn)足一定條件的全局最優(yōu)解。本文提出一種基于最短路徑原理的鑲嵌線(xiàn)自動(dòng)提取方法，首先計(jì)算重疊區(qū)域影像的Canny邊緣，并將Canny邊緣影像視為障礙物信息；然后將鑲嵌線(xiàn)的提取問(wèn)題轉(zhuǎn)換為帶權(quán)有向圖中最短路徑求取問(wèn)題。本文采用基于最小堆原理改進(jìn)的Dijkstra最短路徑算法進(jìn)行了鑲嵌線(xiàn)自動(dòng)提取實(shí)驗(yàn)。

2正射影像鑲嵌中障礙物識(shí)別

正射影像中，房屋、樹(shù)木等高出地面的地物在重疊區(qū)域存在投影差，其灰度值較亮，通常采用差值影像對(duì)此類(lèi)地物進(jìn)行標(biāo)示[1-2，6-8]。如圖1為一重疊區(qū)域原始圖像，圖2為重疊區(qū)域影像差值圖像。在計(jì)算差值影像過(guò)程中，由于待鑲嵌影像存在光照、色調(diào)等差異，將影響差值圖像標(biāo)示障礙物的質(zhì)量。

在計(jì)算機(jī)視覺(jué)領(lǐng)域，人們對(duì)邊緣或輪廓提取進(jìn)行了深入的研究，輪廓信息確定了物體的外圍位置。邊緣或輪廓對(duì)影像分割、物體識(shí)別和分類(lèi)有著重要的作用[9]。一個(gè)物體的輪廓表達(dá)了該物體和其他物體的區(qū)別。本文將物體的外圍輪廓視為障礙物即鑲嵌線(xiàn)需要避開(kāi)的區(qū)域，如圖3所示，圖3為圖1區(qū)域的Canny邊緣。

3鑲嵌線(xiàn)自動(dòng)提取

本文利用邊緣圖像中的像素點(diǎn)構(gòu)建帶權(quán)有向圖，將圖像上鑲嵌線(xiàn)的提取問(wèn)題轉(zhuǎn)換為帶權(quán)有向圖中最短路徑提取問(wèn)題。該處理中的主要問(wèn)題為帶權(quán)有向圖的構(gòu)建、有向圖中鄰接點(diǎn)間權(quán)值的確定及最短路徑的提取。

3.1圖像上帶權(quán)有向圖的構(gòu)建

在有向圖的構(gòu)建過(guò)程中，若采用基于4-鄰域搜索原則(即圖像中每一個(gè)像素點(diǎn)最多存在四個(gè)鄰接點(diǎn)，如圖4中p4的鄰接點(diǎn)為p1、p3、p5、p7)，由此確定圖中頂點(diǎn)間鄰接關(guān)系。構(gòu)建的有向圖及其鄰接矩陣如圖4(a)及圖4(b)所示，圖4(b)中字母表示鄰接點(diǎn)之間的權(quán)值。

對(duì)于m×n大小的圖像，構(gòu)建的有向圖中頂點(diǎn)數(shù)為m×n。由于圖像任一個(gè)像素點(diǎn)，其鄰域可以通過(guò)行列號(hào)確定，有向圖無(wú)需用鄰接表或鄰接矩陣表示，節(jié)省大量空間。

圖1　重疊區(qū)域原始圖像

圖2　重疊區(qū)域差值圖像

圖3　重疊區(qū)域Canny邊緣

圖4　4-鄰域方法有向圖的構(gòu)建及鄰接矩陣表示

3.2有向圖中鄰接頂點(diǎn)間權(quán)值的確定

在鑲嵌處理中，鑲嵌線(xiàn)的位置應(yīng)接近重疊區(qū)域中心線(xiàn)，不應(yīng)偏離重疊區(qū)域中心線(xiàn)太遠(yuǎn)[10]。本文以重疊區(qū)域幾何中心線(xiàn)(初始鑲嵌線(xiàn))為限制條件，計(jì)算圖中頂點(diǎn)的權(quán)值。

(1)初始鑲嵌線(xiàn)的確定

對(duì)于重疊區(qū)域?yàn)榫匦蔚南駥?duì)，其重疊區(qū)域的幾何中心線(xiàn)(初始鑲嵌線(xiàn))如圖5所示。

圖5　矩形重疊區(qū)域中軸線(xiàn)的計(jì)算

設(shè)兩幅重疊影像初始鑲嵌線(xiàn)為多段線(xiàn)l(i)，i=0，1，…，n，多段線(xiàn)上每一點(diǎn)x，y坐標(biāo)分別為xi，yi：

若(|x0-xi-1|>|x0-yi-1|)則初始鑲嵌線(xiàn)為水平中軸線(xiàn)，反之為豎直鑲嵌線(xiàn)。

(2)點(diǎn)到初始鑲嵌線(xiàn)的距離的定義

設(shè)p1，p2圖像上的像素點(diǎn)，則p1，p2到豎直(水平)中軸線(xiàn)的水平(豎直)距離定義為點(diǎn)到初始鑲嵌線(xiàn)的距離。如圖6中d1、d2分別表示點(diǎn)到豎直、水平中軸線(xiàn)的距離。

圖6　點(diǎn)p到豎直(水平)中軸線(xiàn)的距離

(3)鄰接點(diǎn)間權(quán)值的計(jì)算

設(shè)有向圖中一個(gè)頂點(diǎn)為v(i,j)，其圖像像素坐標(biāo)為(i,j)，則v點(diǎn)的所有鄰接點(diǎn)到v點(diǎn)的權(quán)值采用式(1)確定：

(1)

其中g(shù)(i,j)表示邊緣圖像(i,j)像素點(diǎn)處的灰度值(邊緣圖像上灰度值0表示背景，255表示前景)，d(i,j)表示像素點(diǎn)到初始鑲嵌線(xiàn)的距離，w_max為權(quán)值的最大值。

3.3基于最小堆改進(jìn)的Dijkstra最優(yōu)路徑算法提取鑲嵌線(xiàn)

最短路徑(Shortest Path)是指：從圖的某一個(gè)頂點(diǎn)出發(fā)，找出一條通往另一頂點(diǎn)的最短路徑[11]。本文采用基于最小堆改進(jìn)的Dijkstra最短路徑算法進(jìn)行最短路徑計(jì)算。

(1)基于最小堆改進(jìn)的Dijkstra最短路徑算法求取鑲嵌線(xiàn)的步驟。

設(shè)構(gòu)建的有向圖的頂點(diǎn)數(shù)和邊數(shù)分別為E，V，基于Dijkstra算法進(jìn)行最優(yōu)路徑查找時(shí)，其算法復(fù)雜度O(V3)，采用最小堆改進(jìn)后其算法復(fù)雜度O((E+V)*logV)，改進(jìn)后算法執(zhí)行步驟如下：

H=CreateMinimumHeap ()

InsertNode (H，node，0，0)

Forifrom 1 ton-1

InsertNode (H，node，i，w_max)

Forkfrom 1 ton

(i，d)=GetMinimumNode (H)

D[i]=d

For all edgesij：

Ifd+Weight (i，j)

Parent[k]=j

DecreaseKey (H，node，j，d+Weight (i，j))

算法執(zhí)行結(jié)束后，利用Parent數(shù)組回溯得到最短路徑。

(2)減少搜索次數(shù)的方法

在最短路徑的求取過(guò)程中，除影像邊界外的像素都有四個(gè)鄰接點(diǎn)，可能導(dǎo)致提取的路徑存在彎曲、迂回等現(xiàn)象，如圖7(a)所示?？梢愿鶕?jù)實(shí)際搜索方向進(jìn)行有向圖的優(yōu)化。如圖7(a)中，若求取A到B的最佳鑲嵌線(xiàn)，可以省略左方向的搜索；反之，若求B到A的鑲嵌線(xiàn)，省略右方向的搜索，稱(chēng)之為3-鄰域搜索。省略左方向搜索構(gòu)建的有向圖如7(b)所示。

圖7　有向圖中邊的優(yōu)化

4鑲嵌線(xiàn)自動(dòng)提取實(shí)驗(yàn)與分析

依據(jù)本文提出的基于圖論最短路徑原理的鑲嵌線(xiàn)自動(dòng)提取算法，選取影像進(jìn)行鑲嵌線(xiàn)的提取實(shí)驗(yàn)。如圖8中，(a)、(c)和(e)表示3-鄰域提取的結(jié)果，(b)、(d)和(f)表示4-鄰域的提取結(jié)果，Canny邊緣提取時(shí)采用的High threshold和Low threshold參數(shù)分別為0.6和0.3。運(yùn)行時(shí)間如表1所示。

從圖8(a)～圖8(f)可以看出，文中所述方法可以很大程度上躲避房屋等障礙物。采用4-鄰域方法的得到的鑲嵌線(xiàn)存在較多的彎曲、迂回部位，不利于后期的均光勻色處理，而采用3-鄰域的處理方法可以得到相對(duì)規(guī)整的鑲嵌線(xiàn)，方便后期處理。

圖8　4-鄰域搜索和3-鄰域搜索情況下鑲嵌線(xiàn)提取結(jié)果

鑲嵌線(xiàn)提取實(shí)驗(yàn)圖8(a)圖8(b)圖8(c)圖8(d)圖8(e)圖8(f)圖像尺寸681×334530×354692×329Canny邊緣提取時(shí)間78ms62ms79msDijkstra運(yùn)行時(shí)間797ms781ms641ms578ms781ms719ms

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

本文提出基于圖論最短路徑原理的鑲嵌線(xiàn)自動(dòng)提取算法，通過(guò)Canny邊緣提取算法將邊緣特征作為鑲嵌過(guò)程中的障礙物信息，基于邊緣二值圖像構(gòu)建帶權(quán)有向圖，將鑲嵌線(xiàn)提取問(wèn)題轉(zhuǎn)化為最短路徑問(wèn)題。利用快速Dijkstra算法進(jìn)行實(shí)驗(yàn)，結(jié)果表明，該方法可以有效地避開(kāi)圖像中的障礙物區(qū)域，具有較高應(yīng)用價(jià)值，可以用于自動(dòng)鑲嵌中鑲嵌線(xiàn)的自動(dòng)提取。

參考文獻(xiàn)：

[1]張劍清，孫明偉，張祖勛.基于蟻群算法的正射影像鑲嵌線(xiàn)自動(dòng)選擇[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009，34(6)：675-678.

[2]潘俊，王密，李德仁.接縫線(xiàn)網(wǎng)絡(luò)的自動(dòng)生成與優(yōu)化方法[J].測(cè)繪學(xué)報(bào)，2010，39(3)：289-294.

[3]JAECHOON C，HYONGSUK K，CHUN S L.Seam-line determination for image mosaicking：A technique minimizing the maximum local mismatch and the global cost[J].ISPRS Journal of Photogrammetry and Remote Sensing，2010，65(1)：86-92.

[4]KERCHNER M.Seamline detection in colour orthoimage mosaicking by use of twin snakes[J].ISPRS Journal of Photogrammetry & Remote Sensing，2001，(56)：53-64.

[5]溫紅艷，周建中.基于灰色理論的遙感圖像最佳鑲嵌線(xiàn)檢測(cè)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(15)：31-33.

[6]左志權(quán)，張祖勛，張劍清，等.DSM輔助下城區(qū)大比例尺正射影像鑲嵌線(xiàn)智能檢測(cè)[J].測(cè)繪學(xué)報(bào)，2011，40(1)：84-89.

[7]方亞玲，焦偉利.利用對(duì)稱(chēng)動(dòng)態(tài)輪廓模型自動(dòng)檢測(cè)圖像最優(yōu)鑲嵌線(xiàn)[J].科學(xué)技術(shù)與工程，2007，14(7)：3451-3456.

[8]袁修孝，鐘燦.一種改進(jìn)的正射影像鑲嵌線(xiàn)最小化最大搜索算法[J].測(cè)繪學(xué)報(bào)，2012，41(2)：199-204.

[9]CATANZARO B，SU B Y，SUNDARAM N，et al.Efficient，high-quality image contour detection[C].2009 IEEE 12th International Conference on Computer Vision，2009，2381-2388.

[10]潘俊，王密，李德仁.基于顧及重疊的面Voronoi圖的接縫線(xiàn)網(wǎng)絡(luò)生成方法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009，34(5)：518-522.

[11]HOROWITZ E，SAHNI S，ANDERSONFREED S.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述)(第二版)[M].北京：清華大學(xué)出版社.2007.

E-mail：zhangxuran@mail.bnu.edu.cn

E-mail：gad@bnu.edu.cn