文章快速检索  
  高级检索
正射影像镶嵌线自动搜索的视差图算法
袁修孝1,2, 段梦梦1, 曹金山3    
1. 武汉大学遥感信息工程学院, 湖北 武汉 430079;
2. 地球空间信息技术协同创新中心, 湖北 武汉 430079;
3. 武汉大学资源与环境科学学院, 湖北 武汉 430079
摘要:提出了一种基于正射影像视差图的区域级镶嵌线搜索算法。首先利用半全局约束立体匹配算法(semi-global matching,SGM)分别计算立体像对的左右视差图,并通过自适应阈值化去除细小的噪声区域,再经数学形态学方法进一步削弱噪声影响和填补小的漏洞区域,得到了较为精细的房屋等非地面区域的分割结果,从而分离出地面与非地面区域;然后采用改进的贪婪蛇搜索算法进行镶嵌线搜索,以提高算法的稳健性。试验表明,本文算法能很好地避开房屋等明显突出地表的实体,得到不穿越非地面区域的最优路径。
关键词正射影像(DOM)     镶嵌线     视差图     贪婪蛇搜索算法    
A Seam Line Detection Algorithm for Orthophoto Mosaicking Based on Disparity Image
YUAN Xiuxiao1,2, DUAN Mengmeng1 , CAO Jinshan3     
1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China;
2. Collaborative Innovation Center of Geospatial Technology, Wuhan 430079, China;
3. School of Resources and Environmental Science, Wuhan University, Wuhan 430079, China
First author: YUAN Xiuxiao (1963-), male, PhD, Professor, PhD supervisor, majors in research and teaching of theory and method for high precision airborne and spaceborne photogrammetric positioning and geometric processing of high-resolution satellite remote sensing imagery. E-mail: yuanxx@whu.edu.cn
Foundation support: The National Basic Research Program of China(973 Program)(No.2012CB719902);The National Natural Science Foundation of China (No. 41371432);Major Projects of High-resolution Earth Observation System(No.50-H31D01-0508-13/15)
Corresponding author: Duan Mengmeng, E-mail: 540524486@qq.com
Abstract: This paper proposes a regional seam line detection algorithm based on the disparity image of the orthophoto. Firstly, the disparity images of the stereo pair are generated by using the SGM (semi-global matching)method, and the small noises are removed through the adaptive threshold. Then, the mathematical morphology method is used to further eliminate the noises and to fill the small holes on the disparity image in order to accurately separate out the non-ground area. Lastly, the seam line is detected using the improved greedy snake algorithm which with better robustness. The experimental result has shown that our method is effective and is able to acquire an optimized seam line that passed around the entities above the ground.
Key words: digital orthophoto map(DOM)     seam line     disparity image     greedy snake algorithm    

1 引 言

数字正射影像图(DOM)是由多张数字微分纠正影像镶嵌而成的,其中镶嵌线的生成是最关键的一步。一条好的镶嵌线应使镶嵌影像在镶嵌线两侧色彩过渡自然且没有几何错位,即避开影像的差异区域。实际生产中,特别是城区高分辨率航摄影像的镶嵌,大都是在商业软件自动生成镶嵌线的基础上进行人工编辑。因此,研究镶嵌线的自动生成方法对于提高DOM的质量与生产效率具有重要意义。

传统的镶嵌线生成方法大多是利用重叠区影像像元差异或局部纹理差异构建代价影像,然后在其上搜索差异最小的连通路径。文献[1]采用相关系数作为相似性测度,并引入了几何约束(如接近像主点或者观察方向与表面法向的夹角)。文献[2, 3]定义了包含色彩和纹理信息的相似性测度,并提出利用Twin Snake模型搜索镶嵌线,能保证镶嵌线的光滑性,但得到的曲线可能会丢失全局最小值而停留在局部或全局最大值处,该算法仅对林区影像效果较好。文献[4]将动态规划算法用于最优镶嵌线检索,搜索起点到终点间最优路径,但该方法得到的镶嵌线走向受到限制,并不一定是全局最短路径。文献[5]利用Dijkstra算法进行最短路径搜索,但算法复杂度高。文献[6]提出基于蚁群算法的镶嵌线自动选择方法,有效地避开了房屋、树木、水域等反差较大的区域,但算法对蚂蚁数目敏感,局部搜索能力较弱。文献[7]对最小化最大搜索算法进行改进,较好地避开了差值影像上明亮的区域。文献[8, 9]提出一种接缝线网络的自动生成及优化方法,提高了区域范围内多影像的镶嵌效率。文献[10]提出基于极值判断的镶嵌线搜索方法,明显优于最小灰度差值方法。

纵观以上各种镶嵌线搜索方法,本质上都是像素级的,差异表达基于单个像素,并不能将存在几何差异的地物作为单个对象进行差异表达,因此镶嵌线难免会穿越建筑物等区域。针对这一不足,文献[11]提出一种DSM辅助的城区大比例尺DOM镶嵌算法,通过智能算法对DSM的地面和非地面区域进行区分,在镶嵌线搜索时能避开房屋等明显地物。文献[12]利用机载LiDAR点云数据提取高出地面的障碍区,利用A*算法自动搜索避开障碍区的镶嵌线。文献[13, 14]提出基于区域跨度和基于区域变化率的代价影像对象级优化算法。文献[15]提出形态学图像镶嵌算法,被改进后用于大范围的影像镶嵌[16, 17],使得镶嵌线能够绕开高楼、水域等地面实体。这些方法虽然都是区域级的,但需要DSM或LiDAR点云等数据进行非地面区域提取或利用图像处理算法进行影像区域分割,其适用性严格受制于辅助数据的获取与图像分割的精度,这对数字微分纠正影像的镶嵌来说十分不利。

鉴于此,本文提出一种利用微分纠正影像视差图进行区域级镶嵌线搜索的算法,以改进影像的差异表达,获得全局最优的影像镶嵌线。通过该算法既可以解决传统差值影像算法对影像差异区域表达不足的问题,又无须任何辅助数据就能实现对非地面区域的精确分割,从而有针对性地绕开非地面区域,得到较好的镶嵌线。

2 基于视差图的镶嵌线搜索原理 2.1 基本思想

假设左右相机具有相同的姿态和焦距,左相机的摄影中心坐标为(0,0,0),右相机的位置为左相机沿X轴简单平移Tx距离,则右相机的摄影中心坐标为(Tx,0,0)。物点P(X,Y,Z)在左右影像上的成像几何如图 1所示,Tx为基线长度。

由共线方程可知,P点在左影像上的像点坐标为

由于将相机坐标向右平移Tx等价于将物方坐标向左平移Tx,因此为了求得右影像上P点在左影像坐标系下的像点坐标,笔者将右相机坐标和物方P点坐标均左移Tx,如图 1所示,右相机坐标系与左相机重合,且P点坐标变为P′(X-Tx,Y,Z),则P点在右影像上坐标为

图 1 立体成像几何透视图 Fig. 1 Geometric perspective of stereo imaging

P点在左右影像上的水平像点坐标之差即为左右视差

由式(3)可知,在摄影基线和焦距一定的情况下,像点的视差d与物距Z成反比,即离相机越近的物体视差越大,离相机越远的物体视差越小。同理,航空摄影时,房屋等地面物体越高,在相邻两张影像上形成的视差就越大,这一特点即为本文算法的关键。视差图与差值影像的最大区别在于具有区域连续性,能够准确表达高出地面的物体的区域信息,能更好地用于镶嵌线的搜索。

为此,本文算法的基本思想是首先利用计算机视觉中立体影像匹配的原理,通过逐像素计算视差,得到间接反映重叠区影像内地物高度信息的视差图,然后对视差图进行预处理后作为代价影像,最后在代价影像上利用贪婪蛇算法搜索出一条从起点到终点不穿越障碍物的最优路径作为最终的镶嵌线,算法流程如图 2所示。

图 2 算法流程 Fig. 2 The algorithm flow chart
2.2 基于SGM算法的视差图生成

文献[18]提出一种半全局约束立体匹配算法(semi-global matching,SGM),通过在待匹配像素点多个方向上作动态规划来近似图像二维全局优化,确定视差图。SGM算法以互信息MI12为基础,根据两幅影像的联合灰度分布来计算匹配代价。MI是信息论中的一个基本概念,用于描述两个系统间的统计相关性,将其作为一种相似性测度引入影像匹配中,可以很好地处理影像中存在的复杂辐射关系,对全局辐射差异具有较高的稳健性,通过左右影像的信息熵H及其联合信息熵H12来定义,即

式中,HI表示影像I的信息熵;H12表示两幅影像的联合信息熵;PI表示灰度的统计概率(通过灰度直方图计算);g表示二维高斯卷积核。

在构建能量函数时,SGM算法引入平滑约束以保证匹配结果的整体一致性,同时采用逐像素匹配,得到密集可靠的匹配结果。SGM可以很好地兼顾效率与匹配效果,广泛应用于城区三维建模。

图 3(a)图 3(b)是相邻的两幅数字微分纠正影像,图 3(c)为相应的差值影像。从图中可以明显看出,差值影像作为代价影像在宏观上能很好地反映建筑物的轮廓,但这些轮廓并不连续,且房屋顶部区域都是代价值较小的区域,很容易导致镶嵌线穿过这些区域。而视差图则反映的是建筑物顶部连续区域的高度信息,这一特点可以避免镶嵌线横穿建筑物,如图 3(d)所示。

图 3 差值影像和视差图的对比 Fig. 3 Comparison of the difference image and the disparity image
2.3 视差图的优化

就数字微分纠正影像而言,由于存在遮蔽现象,相邻影像上不可避免地存在一些差异区域,这会在左右影像的视差图中表现出来。因此,需要对视差图进行优化处理以保证最终的代价影像能完整地反映出重叠区域左右影像的所有差异。

首先分别计算左右影像的视差图,并线性变换至0~255范围内保存为灰度图像。再对视差图进行二值化,去除视差较小的区域,这些区域也认为是可以穿越的区域。目前常用的图像二值化方法有3种:全局固定阈值法、局部自适应阈值法和最大类间方差法(OTSU)。局部自适应阈值是根据像素邻域块的像素值分部来确定该位置的二值化阈值;OTSU是使用某一个阈值将灰度图像分成目标和背景两类,当两类的类内方差最小和类间方差最大时即为最优阈值,如图 4所示。自适应阈值的效果受窗口大小和噪声的影响很大,许多细小噪声被放大了,而OTSU算法则又过度消除了目标区域;全局固定经验阈值效果较好,且原理上更接近按照地物高度截取目标的初衷。

图 4 3种阈值化方法对比 Fig. 4 Comparison of the three threshold methods

然后对左右影像的视差图进行叠加,算法如式(5)

式中,DNij为最终视差图上的像素灰度值;DN1ijDN2ij分别表示左、右影像视差图上的像素灰度值。

左右影像视差图叠加后会存在一些噪声,本文先采用闭运算[19, 20](先膨胀再腐蚀)来消除纯粹由噪声引起的部分,然后用开运算[19, 20](先腐蚀再膨胀)来连接邻近的区域。图 3(d)所示的视差图经上述优化处理后如图 5所示,可以看出优化后的视差图很好地反映出了图 3(c)中所示的差分影像的差异区域。

图 5 优化后的视差图 Fig. 5 The optimized disparity image
2.4 镶嵌线搜索

镶嵌线搜寻应遵循两个原则:原则1,镶嵌线应尽可能地靠近影像重叠区域中心线;原则2,镶嵌线应尽量沿着地物边缘走。原则1要求镶嵌线两侧具有尽可能小的几何畸变,原则2要求镶嵌线不穿越地物,保证地物的完整性。视差图作为代价影像,白色区域代价值高,代表了不可穿越的障碍区域;黑色区域代价值低,代表可以穿越的区域。因此,镶嵌线的搜索就是在视差图上寻找一条从起点到终点的最短且不穿越障碍区域的路径。文献[11]提出一种基于贪婪蛇思想的镶嵌线检测算法,具体做法是给定一个起点,预设搜索步距,每一步都在圆形搜索范围内选择离终点最近且不穿越障碍物的目标点作为中间节点。通过有序记录中间节点的坐标值,最终得到从起点到终点的最优路径。由于在搜索过程中有时会存在无法穿越的障碍区域,导致搜索失败。针对这一问题,本文规定在搜索下一个节点时,如果圆形范围内无法找到离终点最近且不穿越障碍物的点,则选择当前点与终点的直线方向上间隔为一个步距的点作为下一个节点,强制穿越障碍物。

将重叠区中线上的第一个点作为起始点S(x,y),最后一个点作为终点T(x,y)。中间节点分别为F1F2,…,Fk(k∈N),搜索步距为Δt,搜索方向间隔为Δθ,Dist(x,y)表示两个点之间的欧氏距离。改进后的搜索算法步骤如下。

(1) 更新当前节点FzS(x,y)。

(2) 计算当前节点与终点T(x,y)之间的单位方向向量ST,以S(x,y)为圆心,按间隔Δθ依次旋转向量ST·Δt,并依次记录下该向量的终点FZ1,FZ2,…,FZk(kN)作为候选点。

(3) 以min(Dist(FZ1,T(x,y)),…,Dist(FZk,T(x,y)))准则,选择像素值为0且距离终点T(x,y)最近的候选点作为新的节点,若找不到像素为0且距离终点最近的点,则将FZT·Δt的终点作为新节点。将Fz更新为新节点。

(4) 重复步骤(2)-(3),直到Dist(Fk,T(x,y))<Δt或到达影像最后一行像素,更新当前节点为T(x,y),则算法结束。

3 试验及其结果分析 3.1 试验设计

为了验证本文算法的有效性,选取某地区一对数字微分纠正影像进行镶嵌试验。微分纠正影像已经根据地理坐标信息进行了重叠区域的裁剪,地理范围完全一致。影像地物类型包含有房屋、道路和湖泊等,影像大小为1820像素×4140像素,空间分辨率为0.2m。采用Visual Studio 2010开发环境,在配备Intel 奔腾双核E5300、2.6GHz CPU和4GB内存的台式计算机上进行了试验。

3.2 镶嵌质量分析

差分影像上理想的镶嵌线应沿着灰度值小的区域前进,参考基于差分影像的方法,给出定量评价镶嵌线质量的两个指标:①差分影像上镶嵌线像素灰度平均值f1最小;②差分影像上镶嵌线灰度值较大(灰度值大于某一阈值)的像素个数f2最少,能较好地反映镶嵌线上像素灰度的分布。f1f2可表示为

式中,L(SL)表示镶嵌线SL上的像素数;num表示集合中的像元数;Gt为设定的灰度阈值。

利用本文算法对上述影像进行镶嵌试验,并将搜索到的镶嵌线分别用红线显示在左右原始影像上(以便更直观的进行比较),试验结果如图 6所示。

图 6(a)图 6(b)可以看到,本文算法搜索到的镶嵌线整体走势是沿着重叠区影像中心线的,符合2.4节中的原则1。整体上看,镶嵌线很好地避开了地面建筑物。在影像顶部镶嵌线穿越了少量建筑物,是因为该处房屋本身高度较低,视差值太小,在二值化过程中被消除了,而且在差值影像上该部分影像本身色彩差异也不明显,因此认为是可以容许的。图 6(c)图 6(d)分别是图 6(a)图 6(b)中白色方框区域的局部放大显示,可以看出镶嵌线是沿着建筑物等地物边缘行进的,符合2.4节中的原则2。镶嵌线反映在差分影像上如图 6(e)所示。

图 6 镶嵌线搜索结果 Fig. 6 The result of the seam line detection

为了与其他算法进行比较,这里分别采用蚁群算法和Photoshop对同一立体像对进行了镶嵌试验,结果如图 7所示。

图 7 3种算法效果对比图 Fig. 7 Comparison of the three methods

表 1统计了3种算法得到的镶嵌线在差分影像上的平均灰度、最大灰度以及“大灰度”像素个数。从效率上看,蚁群算法、Photoshop和本文算法分别消耗CPU时31.6s、32.3s和55.7s,本文算法为了得到高精度的视差图花费的时间稍多于前两种算法。从质量上看:①蚁群算法在一定程度上是沿着地物边缘行进的,但穿越了多处房屋;②Photoshop得到的镶嵌线虽然较好地绕开了建筑物,但镶嵌线偏离影像重叠区域中心线太远,影响了镶嵌效果;③本文算法搜索到的镶嵌线既保持在影像重叠区域中线附近,又很好地避开了房屋,效果较好。从定量指标上看,本文算法得到的镶嵌线在差分影像上的最大灰度和“大灰度”像素个数两项指标都要优于另外两种算法,平均灰度介于它们之间,这表明本文算法的镶嵌结果最为理想。

表 1 差分影像上镶嵌线像素统计 Tab. 1 Pixel statistics of seam line on differential image
路径长度
/像素
像素数 /个运行时间
/s
最大灰度平均灰度
灰度>50灰度>100灰度>150灰度>200
蚁群算法41401434125031.61969.47
Photoshop42861585032.31812.97
本文算法51343490055.71485.02
4 结束语

针对传统基于差值影像的像素级镶嵌线搜索算法的不足,本文提出了基于立体像对视差图的区域级镶嵌线搜索算法,在对视差图进行优化处理后,利用改进的贪婪蛇搜索算法搜索出最优路径。试验表明,本文算法能搜素出避开房屋等地表实体的高质量的镶嵌线,实现了数字微分纠正影像的拼接。综合考虑算法效率与镶嵌质量,本文算法在可容忍的时间开销内镶嵌线搜索结果是明显优于蚁群算法和Photoshop的。但在影像下部,镶嵌线穿越了水域,出现了不规则绕行现象,下一步将针对这一问题进行研究和改进。

参考文献
[1] SCHICKLER W, THORPE A. Operational Procedure for Automatic True Orthophoto Generation[J]. ISPRS Commission IV Symposium on GIS——Between Vision and Application, 1998, IAPRS, 32(4): 527-532.
[2] KERSCHNER M. Twin Snakes for Determining Seam Lines in Orthoimage Mosaicking[J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(4): 454-461.
[3] KERSCHNER M. Seamline Detection in Colour Orthoimage Mosaicking by Use of Twin Snakes[J]. ISPRS Journal of Photogrammetry & Remote Sensing, 2001, 56(1): 53-64.
[4] EFROS A A, Freeman W T. Image Quilting for Texture Synthesis and Transfer[C]//Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques.New York: ACMSIGGRAPH, 2001: 341-346.
[5] DAVIS J. Mosaic of Scenes with Moving Objects[C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Santa Barbara, CA: IEEE, 1998: 354-360.
[6] ZHANG Jianqing, SUN Mingwei, ZHANG Zuxun. Automated Seamline Detection for Orthophoto Mosaicking Based on Ant Colony Algorithm[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6): 675-678. (张剑清, 孙明伟, 张祖勋. 基于蚁群算法的正射影像镶嵌线自动选择[J]. 武汉大学学报: 信息科学版, 2009, 34(6): 675-678.)
[7] YUAN Xiuxiao,ZHONG Can.An Improvement of Minimizing Local Maximum Algorithm on Searching Seam Line for Orthoimage Mosaicking[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2): 199-204. (袁修孝, 钟灿. 一种改进的正射影像镶嵌线最小化最大搜索算法[J]. 测绘学报, 2012, 41(2): 199-204.)
[8] PAN Jun, WANG Mi, LI Deren. Generation of Seamline Network Using Area Voronoi Diagram with Overlap[J]. Geomatics and Information Science of Wuhan University, 2009, 34(5): 518-521. (潘俊, 王密, 李德仁. 基于顾及重叠的面Voronoi图的接缝线网络的生成方法[J]. 武汉大学学报: 信息科学版, 2009, 34(5): 518-521.)
[9] PAN Jun, WANG Mi, LI Deren. Approach for Automatic Generation and Optimization of Seamline Network[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3): 289-294. (潘俊, 王密, 李德仁. 接缝线网络的自动生成及优化方法[J]. 测绘学报, 2010, 39(3): 289-294.)
[10] OU Xiaoping. Research on Technologies of Automatic Remote Sensing Image Mosaic[D]. Zhengzhou: Information Engineering University, 2013. (欧小平. 遥感影像自动化镶嵌关键技术研究[D]. 郑州: 信息工程大学, 2013.)
[11] ZUO Zhiquan, ZHANG Zuxun, ZHANG Jianqing, et al. Seamlines Intelligent Detection in Large-scale Urban Orthoimage Mosaicking[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(1): 84-89. (左志权, 张祖勋, 张剑清,等. DSM辅助下城区大比例尺正射影像镶嵌线智能检测[J]. 测绘学报, 2011, 40(1): 84-89.)
[12] SUN Jie, MA Hongchao, TANG Xuan. Optimization of LiDAR System Ortho-image Mosaic Seam-line[J]. Geomatics and Information Science of Wuhan University, 2011, 36(3): 325-328. (孙杰, 马洪超, 汤璇. 机载LiDAR正射影像镶嵌线智能优化研究[J]. 武汉大学学报: 信息科学版, 2011, 36(3): 325-328.)
[13] ZHOU Qinghua, PAN Jun, LI Deren. Overview of Automatic Generation of Mosaicking Seamlines for Remote Sensing Images[J]. Remote Sensing for Land and Resources, 2013, 25(2): 1-7. (周清华, 潘俊, 李德仁. 遥感图像镶嵌接缝线自动生成方法综述[J]. 国土资源遥感, 2013, 25(2): 1-7.)
[14] ZHOU Qinghua. Research on Seamline Optimization for Aerial Images[D]. Wuhan: Wuhan University, 2013. (周清华. 航空影像接缝线优化方法研究[D]. 武汉: 武汉大学, 2013.)
[15] SOILLE P. Morphological Image Compositing[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(5): 673-683.
[16] BIELSKI C, GRAZZINI J, SOILLE P. Automated Morphological Image Composition for Mosaicing Large Image Data Sets[C]//IEEE International Geoscience and Remote Sensing Symposium. Barcelona: IEEE, 2007: 4068-4071.
[17] BIELSKI C, SOILLE P. Order Independent Image Compositing[C]//ROLI F,VITULANOS ed. Image Analysis and Processing.Berlin: Springer, 2005, 3617: 1076-1083.
[18] HIRSCHMULLER H. Accurate and Efficient Stereo Processing by Semi-global Matching and Mutual Information[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Diego: IEEE, 2005: 807-814.
[19] SUI Lichun, ZHANG Yibin, LIU Yan, et al. Filtering of Airborn LiDAR Point Cloud Data Based on the Adaptive Mathematical Morphology[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 390-396. (隋立春, 张熠斌, 柳艳,等. 基于改进的数学形态学算法的LiDAR点云数据滤波[J]. 测绘学报, 2010, 39(4): 390-396.)
[20] GENG Shuai. Image Denoising Based on Mathematical Morphology[D]. Ji'nan: Shandong Normal University, 2012. (耿帅. 基于数学形态学的图像去噪[D]. 济南: 山东师范大学, 2012.)
http://dx.doi.org/10.11947/j.AGCS.2015.20140421
中国科学技术协会主管、中国测绘地理信息学会主办。
0

文章信息

袁修孝, 段梦梦, 曹金山
YUAN Xiuxiao, DUAN Mengmeng, CAO Jinshan
正射影像镶嵌线自动搜索的视差图算法
A Seam Line Detection Algorithm for Orthophoto Mosaicking Based on Disparity Image
测绘学报,2015,44(8):877-883
Acta Geodaeticaet Cartographica Sinica, 2015, 44(8): 877-883.
http://dx.doi.org/10.11947/j.AGCS.2015.20140421

文章历史

收稿日期:2014-08-08
修回日期:2014-12-23

相关文章

工作空间