最短路徑原理正射影像鑲嵌線自動提取

最短路徑原理正射影像鑲嵌線自動提取

岳貴杰1，杜黎明2，項琳3，李健3，張剛3

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

摘要：正射影像鑲嵌過程中，鑲嵌線的選取是一個重要的步驟，其自動化程度是影響全自動鑲嵌的一個重要因素。本文提出一種基于圖論最短路徑原理的正射影像鑲嵌線自動提取方法。該算法將圖像上提取得到的底層視覺信息(Canny邊緣)作為鑲嵌過程中的障礙物信息，在邊緣圖像上根據像素點的鄰接關系構建帶權有向圖，利用初始鑲嵌線作為初始條件計算圖中有向邊的權值，將正射影像鑲嵌線的提取過程轉化為圖論中最短路徑問題。實驗表明，該算法可以較為準確提取鑲嵌線，對全自動鑲嵌具有重要應用價值。

關鍵詞：正射影像；鑲嵌線；帶權有向圖；最短路徑

doi:10.3969/j.issn.1000-3177.2015.01.006

中圖分類號：P237文獻標識碼：A

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

基金項目：國家科技支撐計劃課題(2012BAJ23B05)。

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

通訊作者：宮阿都(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引言

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

正射影像鑲嵌線自動提取的問題可歸結為兩個方面：正射影像中障礙物的識別(房屋、樹木等高出地面的物體)和最優路徑的提取。理論上來講，給定障礙物條件，應該得到滿足一定條件的全局最優解。本文提出一種基于最短路徑原理的鑲嵌線自動提取方法，首先計算重疊區域影像的Canny邊緣，并將Canny邊緣影像視為障礙物信息；然后將鑲嵌線的提取問題轉換為帶權有向圖中最短路徑求取問題。本文采用基于最小堆原理改進的Dijkstra最短路徑算法進行了鑲嵌線自動提取實驗。

2正射影像鑲嵌中障礙物識別

正射影像中，房屋、樹木等高出地面的地物在重疊區域存在投影差，其灰度值較亮，通常采用差值影像對此類地物進行標示[1-2，6-8]。如圖1為一重疊區域原始圖像，圖2為重疊區域影像差值圖像。在計算差值影像過程中，由于待鑲嵌影像存在光照、色調等差異，將影響差值圖像標示障礙物的質量。

在計算機視覺領域，人們對邊緣或輪廓提取進行了深入的研究，輪廓信息確定了物體的外圍位置。邊緣或輪廓對影像分割、物體識別和分類有著重要的作用[9]。一個物體的輪廓表達了該物體和其他物體的區別。本文將物體的外圍輪廓視為障礙物即鑲嵌線需要避開的區域，如圖3所示，圖3為圖1區域的Canny邊緣。

3鑲嵌線自動提取

本文利用邊緣圖像中的像素點構建帶權有向圖，將圖像上鑲嵌線的提取問題轉換為帶權有向圖中最短路徑提取問題。該處理中的主要問題為帶權有向圖的構建、有向圖中鄰接點間權值的確定及最短路徑的提取。

3.1圖像上帶權有向圖的構建

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

對于m×n大小的圖像，構建的有向圖中頂點數為m×n。由于圖像任一個像素點，其鄰域可以通過行列號確定，有向圖無需用鄰接表或鄰接矩陣表示，節省大量空間。

圖1　重疊區域原始圖像

圖2　重疊區域差值圖像

圖3　重疊區域Canny邊緣

圖4　4-鄰域方法有向圖的構建及鄰接矩陣表示

3.2有向圖中鄰接頂點間權值的確定

在鑲嵌處理中，鑲嵌線的位置應接近重疊區域中心線，不應偏離重疊區域中心線太遠[10]。本文以重疊區域幾何中心線(初始鑲嵌線)為限制條件，計算圖中頂點的權值。

(1)初始鑲嵌線的確定

對于重疊區域為矩形的像對，其重疊區域的幾何中心線(初始鑲嵌線)如圖5所示。

圖5　矩形重疊區域中軸線的計算

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

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

(2)點到初始鑲嵌線的距離的定義

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

圖6　點p到豎直(水平)中軸線的距離

(3)鄰接點間權值的計算

設有向圖中一個頂點為v(i,j)，其圖像像素坐標為(i,j)，則v點的所有鄰接點到v點的權值采用式(1)確定：

(1)

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

3.3基于最小堆改進的Dijkstra最優路徑算法提取鑲嵌線

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

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

設構建的有向圖的頂點數和邊數分別為E，V，基于Dijkstra算法進行最優路徑查找時，其算法復雜度O(V3)，采用最小堆改進后其算法復雜度O((E+V)*logV)，改進后算法執行步驟如下：

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))

算法執行結束后，利用Parent數組回溯得到最短路徑。

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

在最短路徑的求取過程中，除影像邊界外的像素都有四個鄰接點，可能導致提取的路徑存在彎曲、迂回等現象，如圖7(a)所示?？梢愿鶕嶋H搜索方向進行有向圖的優化。如圖7(a)中，若求取A到B的最佳鑲嵌線，可以省略左方向的搜索；反之，若求B到A的鑲嵌線，省略右方向的搜索，稱之為3-鄰域搜索。省略左方向搜索構建的有向圖如7(b)所示。

圖7　有向圖中邊的優化

4鑲嵌線自動提取實驗與分析

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

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

圖8　4-鄰域搜索和3-鄰域搜索情況下鑲嵌線提取結果

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

5結束語

本文提出基于圖論最短路徑原理的鑲嵌線自動提取算法，通過Canny邊緣提取算法將邊緣特征作為鑲嵌過程中的障礙物信息，基于邊緣二值圖像構建帶權有向圖，將鑲嵌線提取問題轉化為最短路徑問題。利用快速Dijkstra算法進行實驗，結果表明，該方法可以有效地避開圖像中的障礙物區域，具有較高應用價值，可以用于自動鑲嵌中鑲嵌線的自動提取。

參考文獻：

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

[2]潘俊，王密，李德仁.接縫線網絡的自動生成與優化方法[J].測繪學報，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]溫紅艷，周建中.基于灰色理論的遙感圖像最佳鑲嵌線檢測[J].計算機工程與應用，2009，45(15)：31-33.

[6]左志權，張祖勛，張劍清，等.DSM輔助下城區大比例尺正射影像鑲嵌線智能檢測[J].測繪學報，2011，40(1)：84-89.

[7]方亞玲，焦偉利.利用對稱動態輪廓模型自動檢測圖像最優鑲嵌線[J].科學技術與工程，2007，14(7)：3451-3456.

[8]袁修孝，鐘燦.一種改進的正射影像鑲嵌線最小化最大搜索算法[J].測繪學報，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圖的接縫線網絡生成方法[J].武漢大學學報(信息科學版)，2009，34(5)：518-522.

[11]HOROWITZ E，SAHNI S，ANDERSONFREED S.數據結構(用面向對象方法與C++語言描述)(第二版)[M].北京：清華大學出版社.2007.

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

E-mail：gad@bnu.edu.cn