最短路径原理正射影像镶嵌线自动提取

最短路径原理正射影像镶嵌线自动提取

岳贵杰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)所示。可以根据实际搜索方向进行有向图的优化。如图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