《影像匹配中几种相似性测度的分析.pdf》由会员分享，可在线阅读，更多相关《影像匹配中几种相似性测度的分析.pdf（3页珍藏版）》请在三一文库上搜索。
1、求,如果多用户时就不能考虑道路冲突的问题。 参考文献 1 严蔚敏,吴伟民.数据结构M.北京:清华大学出版社,2002. 2 苏永云,晏克非,黄 翔,等.车辆导航系统动态最优路径搜索 方法的研究J .系统工程,2000 ,18(4) :3237 3Nordbeck S, Rystedt B. Computer Cartography Shortest Route Pro2 gramsM. Sweden:The Royal University of Lund ,1969. 4 陆 锋,崔伟宏,卢冬梅.交通网络限制搜索区域时间最短路 径算法J .中国图象图形学报,2002 ,10(4A) :849
2、853 5 严寒冰,刘迎春.基于GIS的城市道路网最短路径算法研讨 J .中国计算机学报,2002 , 32(2) :210215 收稿日期:2003204214. /修回日期:2003205217. 作者简介:王建宇,副教授,主要从事图形学、 虚拟现实、 计算机仿 真研究。 E2mail:wangjyu mail. MULTI2PROPERTIES OPTIMAL PATH ALGORITHM RESEARCH BASED ON THE DIGITAL MAP WANGJianyuXU ZhenhongZHOU Xianzhong (Automation Dept artment , Nan
3、jing University of Science and Technology , 200 Xiaolingwei , Nanjing 210094 , China) ABSTRACTThe paper is to design an optimal path algorithm which is based on the digital map in a GIS system. The algorithm makes use of several properties of transportation networks to set the weights of the paths a
4、nd perfects the rectangle restricted searching area algorithm to make it applied into the transportation networks in GIS. KEY WORDSdijkstra algorithm; digital map ; optimal path; GIS 文章编号:100723817(2003)0420011203中图分类号:P231 文献标识码:B 影像匹配中几种相似性测度的分析 山海涛1 郭建星1 ,2耿则勋1 (1 信息工程大学测绘学院,郑州市陇海中路66号, 450052 ;
5、2武汉大学遥感信息工程学院,武汉市珞喻路129号,430079) 摘 要 对基于灰度影像匹配中的几种相似性测度进行了研究,分析了每种测度的直观意义、 限制条件以及改进 措施,最后通过实验结果验证了上述结论。 关键词 影像匹配;相似性测度;匹配窗口 影像匹配是数字摄影测量的关键技术之一。影像匹配 方法大致可分为三类:第一类是基于影像灰度的影像匹配算 法;第二类是基于影像特征的影像匹配算法;第三类是基于 对影像的理解和解释的影像匹配算法。其中,基于灰度的影 像匹配算法以左、 右像片上含有相应影像的目标区和搜索区 中的像元的灰度作为影像匹配的基础,利用某种相似性度 量,如相关函数(矢量数积)、 协方
6、差函数(矢量投影)、 相关系 数(矢量夹角)、 差平方和(差矢量模)、 差绝对值和(差矢量分 量绝对和) 1等测度的极值 ,来判定左右影像中的相应像点。 1 基于灰度的数字影像匹配 设g( x , y)与g ( x , y)为立体像对左右影像,基于灰 度的匹配方法是,把一幅图像中某一像点为中心的灰度区域 作为模板,在另一幅图像中搜索具有相同(或相似)灰度值分 布的对应点区域,从而实现两幅图像的配准。 令两个随机变 量X与Y分别表示左右数字影像中的一个像元灰度窗口,窗 口X与Y表示如下形式: x11x12x1N x21x22x2N xN1xN2xNN y11y12y1N y21y22y2N yN
7、1yN2yNN X与Y的均值用下式计算: ?x = 1 N2 N i =1 N j =1 xij,?y = 1 N2 N i =1 N j =1 yij(1) 其方差分别为: 2 X= N i =1 N j =1 x2ij-?x2, 2 Y= N i =1 N j =1 y2ij-?y2(2) 将左影像中的某个窗口X中的元素排列一行构成一个N2维 的向量X= ( x1, x2, xN2 ) , 称为目标向量;而将右影像中 某个与X可能相似的窗口Y的元素拉伸形成的N2维的向量 Y= ( y1, y2, yN2)称为搜索向量。 2几种基于灰度的相似性测度 2.1相关函数测度 两个灰度影像窗口X与Y
8、的相关函数定义为: 11测绘信息与工程 Journal of Geomatics2003Aug. ; 28(4) 图2协方差函数测度 图1相关函数测度 R ( X , Y) = N i =1 N j =1 xijyij(3) 基于相关函数匹配的基本原理是给定目标窗口X ,在右灰度 影像上某一搜索范围D内,寻找与X的相关函数值达到极大 值的搜索窗口Ymax,并认为该窗口即为X的匹配窗口,从而 两窗口相应的中心像素即为同名点。 即匹配窗口满足 Ymax=max YDR ( X , Y) (4) 由相关函数的定义式(3)可以看出,两窗口的相关函数 R ( X , Y)实际上即为两窗口拉伸矢量 X 与
9、Y 的内积: ( X Y ) = N2 i =1 xiyi 因此式(4)相当于: Y max=max Y D ( X Y) 由内积的定义,得: Y max=max Y D ( X Y ) = max Y D | X| |Y|cos(5) 给定目标窗口X ,其拉伸向量X 的模| X|即为定值。 对任意 的搜索向量Y, | X| |Y|cos最大则相当于|Y|cos最 大,即向量Y 在向量X 上的直接投影最大。 式(5)等价于: Y max=max Y D |Y|cos(6) 式(6)的直观解释如图1。 由图1(a)可以看出,对于投影向量 的模长小于目标向量|X|的搜索向量Y 1, Y2来说,显然
10、, 直接投影| Y|cos愈大, Y 与X 愈相似;从图1(b)还可以 看出,对于投影大于目标向量X 的搜索向量 Y 1、Y2来说,容易看出,直接投影| Y|cos 愈小, Y 与X 愈相似,由此可得结论1。 结论1:对于相关函数测度,当匹配窗口 向量在目标窗口向量上的投影小于(或等于) 目标窗口向量的模长时,投影越大越相似;反 之,越小越相似。 用一些具体的影像窗口对上述分析进行 实验。 首先选定一目标窗口 X ( 或拉伸后的一 维向量X ) , 其次在搜索范围内又选定一些搜 索窗口 Y ( 相应地就得到一些拉伸的一维向量 Y)。 选取其中的若干个窗口,其|Y|小于 目标向量X 的模| X|
11、 ,称为第 类窗口;选 取若干个窗口,其|Y|大于目标向量X 的 模|X| ,称为第 类窗口。 用相关函数测度 得到不同搜索向量的相似性程度2,如图 1( c) 、 图 1(d) 。 由于相关系数测度仍然是目前众多匹配 算法中较好的一种,所以本文的研究均以相关 系数测度为准,即认为相关系数越大越相似。 如图 1(c) 、 图1(d ) , 其中横轴表示投影向量模 长,纵轴表示相关系数。 2.2协方差函数测度 协方差函数是中心化的相关函数。 两个灰 度影像窗口X与Y的协方差函数定义为: CX Y= N i =1 N j =1 ( x ij-?x) ( yij-? y) (7) 基于协方差函数匹配
12、的基本原理是给定目标窗口X ,在右灰 度影像上某一搜索范围D内,寻找与X的协方差函数值达到 极大值的搜索窗口Ymax,并认为该窗口即为X的匹配窗口, 而两窗口相应的中心像素即为同名点,即匹配窗口满足: Ymax=max YDCX Y 由协方差函数的定义式(7)可以看出,实际上: CX Y= ( X-?X ) ( Y -?Y) 式中, X, Y 分别是目标窗口和匹配窗口拉伸后形成的一维 向量,?X = ( ?x ,?x ,?x) ,?Y = ( ?y ,?y ,?y) ,?x、 ?y用式(1) 计算。 若记 ?X= ( X-?X ) , ?Y= ( Y-?Y ) , 则 CX Y=?X ?Y 因
13、此,协方差函数测度相当于中心化的相关函数测度。 仿照 相关函数测度的分析,可得结论2。 结论2:对于协方差函数测度,当匹配窗口向量在目标窗 口向量上的投影小于(或等于)目标窗口向量的模长时,投影 越大越相似;反之,越小越相似。 用了一些具体的影像窗口对上述分析进行了实验。 结果 见图23。 2.3相关系数测度 相关系数是标准化的协方差函数。 两随机变量X与Y的 相关系数( X , Y)定义为: ( X , Y) = CX Y / ( 2 X 2 Y) 1/2 式中, 2 X 、 2 Y和CX Y分别用式(2)和式(7)计算。 其基本原理 21测绘信息与工程 Journal of Geomati
14、cs2003Aug. ; 28(4) 是给定目标窗口X ,在右灰度影像上某一搜索范围D内,寻 找与X的相关系数达到极大值的搜索窗口Ymax,并认为该窗 口即为X的匹配窗口,从而两窗口相应的中心像素即为同名 点。 也就是说匹配窗口满足: Ymax=max YD ( X , Y) 由2.2节中的分析可得: ( X , Y) =(?X,?Y ) = ?X ?Y/ (|?X| |?Y| ) = (?X/ |?X | ) ( ?Y/ |?Y | ) 记E? X=? X/ |?X| , E? Y=? Y/ |?Y| , E? X、E?Y均为归一化 (Normalized)向量,则 (?X,?Y) = E?
15、 XE?Y=cos (8) 式中, a是矢量E? X与E?Y的夹角。 因此相关系数测度相当于 消除了模长因素影响的相关函数测度,只与中心化、 归一化 后的目标向量和搜索向量的夹角a有关。 如图3(二维情形的 示意图)所示。 图3相关系数测度 一般说来,两相量之间的相似性程度除了与两向量之间 的夹角有关外(夹角越小越相似 ) , 还与两个待比较向量的模 长有关(两向量的模长越接近越相似)。 从形式上看,式(8)似 乎只考虑了两个待比较向量之间的夹角,还应考虑待比较向 量的模长。 但由于上述分析,式(8)实际上是消除了模长因素 影响后的相似性测度,因而足以度量两向量的相似性。 在实 验中进行了大量
16、的实际计算,也证明了这一结论。 2.4差平方和测度与差绝对值和测度 两个灰度影像窗口 X ( 或拉伸的一维向量X)和 Y ( 或 拉伸的一维向量Y)的差平方和定义为: S2= N2 i =1 ( x i- yi) 2 基于差平方和测度匹配的基本原理是给定目标窗口X ,在右 灰度影像上某一搜索范围D内,寻找与X的差平方和达到极 小值的搜索窗口Ymin,并认为该窗口即为X的匹配窗口,而 两窗口相应的中心像素即为同名点。 即匹配窗口满足: Ymin=min YDS 2 两个灰度影像窗口 X ( 或拉伸的一维向量X)和 Y ( 或 拉伸的一维向量 Y) 的差绝对值和定义为: S = N2 i =1 |
17、 xi-yi| 基于差绝对值和测度匹配的基本原理是给定目标窗口X ,在 右灰度影像上某一搜索范围D内,寻找与X的差绝对值和达 到极小值的搜索窗口Ymin,并认为该窗口即为X的匹配窗口, 而两窗口相应的中心像素即为同名点。 即匹配窗口满足: Ymin=min YDS 对于该两种测度也进行了相应的分析,并得出一些有意义的 结论2。 限于篇幅这里不作详细介绍。 3结果与结论 采用的实验影像是惠州地区的航空影像,像元为18m, 影像为524像素 540像素,实验结果见表1。 表1匹配试验结果 相似性测度匹配点数匹配成功率改进后成功率 相关函数测度1 0000. 010. 05 协方差函数测度1 000
18、0. 360. 40 相关系数测度1 0000. 93 从表1的实验结果明显可以看出,文中提出的几种相似 性测度的改进策略是正确的。 通过对这几种相似性度量算子的深入分析,得出了有意 义的结论,对今后这方面的研究工作具有重要的参考价值。 但从目前影像匹配的研究现状和应用前景来看,还有很多地 方值得进一步去探索,只有在理论上取得重大突破,才能更 快地推动影像匹配技术不断向前发展。 参考文献 1 张祖勋,张剑清.数字摄影测量学 M.武汉:武汉测绘科技 大学出版社, 1996. 2 山海涛.影像匹配中几种基本相似性测度的研究D.武汉: 武汉大学, 2002 3Eva Part2Enander , A
19、nders Sjoberg. MATLAB 5手册 M.北 京:机械工业出版社, 2000. 收稿日期:2003204214. /修回日期:2003205219. 作者简介:山海涛,硕士研究生,主要从事摄影测量与遥感、 图像处 理研究。 E2mail:hb43haitao. 2002 ANALYSIS OF SEVERAL OPERATORS OF SIMILARITY IN IMAGE MATCHING SHAN Haitao1GUO Jianxing1 ,2GENG Zexun1 (1 Institute of Surveying and Mapping , Information Eng
20、ineering University , 66 Middle Longhai Road , Zhengzhou 450052 , China ; 2 School of Remote Sensing and Information Engineering , Wuhan University , 129 Luoyu Road , Wuhan 430079 , China) ABSTRACTSeveral arithmetic operators of similarity in image matching are discussed. Thispaper analyzes theoretical explanation , constraints as well as improved tactics of every arithmetic operator of similarity. KEY WORDSimage matching; operator of similarity; match window 31测绘信息与工程 Journal of Geomatics2003Aug. ; 28(4)