留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于图论的遥感影像误匹配点自动探测方法

袁修孝 袁巍 陈时雨

袁修孝, 袁巍, 陈时雨. 基于图论的遥感影像误匹配点自动探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
引用本文: 袁修孝, 袁巍, 陈时雨. 基于图论的遥感影像误匹配点自动探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
YUAN Xiuxiao, YUAN Wei, CHEN Shiyu. An Automatic Detection Method of Mismatching Points in Remote Sensing Images Based on Graph Theory[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
Citation: YUAN Xiuxiao, YUAN Wei, CHEN Shiyu. An Automatic Detection Method of Mismatching Points in Remote Sensing Images Based on Graph Theory[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154

基于图论的遥感影像误匹配点自动探测方法

doi: 10.13203/j.whugis20180154
基金项目: 

国家自然科学基金 41771479

国家高分专项(民用部分) 50-H31D01-0508-13/15

国家973计划 2012CB719902

详细信息
    作者简介:

    袁修孝, 博士, 教授, 博士生导师, 湖北名师, 珞珈杰出学者, 主要从事航空航天摄影测量高精度定位理论与方法、高分辨率卫星遥感影像几何处理等的研究和教学工作。代表成果:GPS/IMU辅助空中三角测量等。yuanxx@whu.edu.cn

    通讯作者: 袁巍, 博士生。milaoyw@whu.edu.cn
  • 中图分类号: P237

An Automatic Detection Method of Mismatching Points in Remote Sensing Images Based on Graph Theory

Funds: 

The National Natural Science Foundation of China 41771479

the National High Resolution Earth Observation System (the Civil Part) 50-H31D01-0508-13/15

the Major State Basic Research Development Program(973 Program) of China 2012CB719902

More Information
    Author Bio:

    YUAN Xiuxiao, PhD, professor. He is concentrated on the research and education in remote sensing (RS), global navigation satellite system (GNSS) and their integration. He has made unique and original contribution to the areas of theories and methods for high precision photogrammetric positioning, GNSS/IMU-supported aerotriangulation, geometric processing of high-resolution satellite imagery, and so on. He published 12 monographs and more than 130 papers. E-mail:yuanxx@whu.edu.cn

    Corresponding author: YUAN Wei, PhD candidate. E-mail: milaoyw@whu.edu.cn
  • 摘要: 提出一种基于图论的卫星遥感影像误匹配点自动剔除方法。首先以稀疏匹配点为节点分别构建左右影像的完全图;然后利用每个节点所对应三角形的相似度之和为属性值构建导出图;最后通过搜索导出图中属性值最小的节点定位误匹配点。在剔除单个误匹配点的基础上,采用重新构建完全图-导出图-定位误匹配点的循环搜索策略,达到自动探测并剔除多个误匹配点的目的。实验表明,该方法无需建立匹配点间的映射模型,仅利用三角形的相似关系就可以定位误匹配点,与广泛使用的随机抽样一致性粗差探测方法相比,对误匹配点具有更高的识别率和更低的误判率。
  • 图  1  基于图论的误匹配点探测流程图

    Figure  1.  Flowchart of Mismatch Point Detection Based on Graph Theory

    图  2  影像匹配点构成的完全图

    Figure  2.  Complete Graph Made up of Image Matching Points

    图  3  包含误匹配点的完全图

    Figure  3.  Complete Graph Containing Mismatched Points

    图  4  匹配完全图及其导出图

    Figure  4.  Complete Graph and Its Derived Diagram Made up of Image Matching Points

    图  5  人工量测的像片连接点

    Figure  5.  Image Joint Points of Artificial Measurement

    图  6  f值随误匹配率的变化曲线

    Figure  6.  Change Curve of the f Value with the Mismatch Rate

    图  7  影像匹配精度的对比图

    Figure  7.  Contrast Diagram of Image Matching Precision

    表  1  实验影像的主要技术参数

    Table  1.   Technical Parameters of Selected Experimental Images

    实验组号 遥感卫星 影像区域 影像大小/像素 地面采样间隔/m
    1 高分一号 高山区 18 192×18 000 2.02.1
    资源三号 24 530×24 575
    2 高分二号 城区 9 376×9 136 1.02.1
    资源三号 24 530×24 575
    3 资源三号(前视) 城区 24 525×24 419 2.13.5
    资源三号(下视) 16 292×16 348
    下载: 导出CSV

    表  2  自动剔除误匹配点后保留的同名点数

    Table  2.   Number of Homonyms Reserved After Automatic Elimination of Mismatched Points

    实验组号 RANSAC方法 本文方法
    1 10 076 11 942
    2 6 498 6 530
    3 21 598 22 239
    下载: 导出CSV

    表  3  影像匹配点的离散度

    Table  3.   Discreteness of Image Matching Points

    实验组号 不剔除误匹配点 RANSAC方法 本文方法
    1 5.12×10-5 1.91×10-4 9.74×10-5
    2 8.90×10-5 1.12×10-4 1.10×10-4
    3 3.20×10-5 5.50×10-4 4.60×10-5
    下载: 导出CSV
  • [1] 李德仁, 袁修孝.误差处理与可靠性理论[M].武汉:武汉大学出版社, 2012

    Li Deren, Yuan Xiuxiao. Error Processing and Relia-bility Theory[M]. Wuhan:Wuhan University Press, 2012
    [2] Baarda W. A Testing Procedure for Use in Geodetic Networks[OL]. http://www.ncgeo.nl/downloads/09Baarda.pdf, 1968
    [3] Wilcox R R. Introduction to Robust Estimation and Hypothesis Testing[M]. Pittsburgh:Academic Press, 2011
    [4] 李德仁.利用选择权迭代法进行粗差定位[J].武汉测绘学院学报, 1984, 9(1):46-68 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK000003186032

    Li Deren. Gross Error Location by Means of the Iteration Method with Variable Weights[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1984, 9(1):46-68 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK000003186032
    [5] Kubik K. An Error Theory for the Danish Method[C]. The Symposium of ISP Commission Ⅲ, Helsinki, Finland, 1982
    [6] Huber P J. Robust Statistics[M]//Marques T A, Buckland S T, Borchers D L, et al. International Encyclopedia of Statistical Science. Berlin, Heidelberg: Springer, 2011
    [7] Fischler M A, Bolles R C. Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J]. Communications of the ACM, 1981, 24(6):381-395 doi:  10.1145/358669.358692
    [8] İmre E, Adrian H. Order Statistics of RANSAC and Their Practical Application[J]. International Journal of Computer Vision, 2015, 111(3):276-297 doi:  10.1007/s11263-014-0745-1
    [9] Chum O, Jiri M. Matching with PROSAC-Progressive Sample Consensus[C]. The IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CA, USA, 2005
    [10] 张正鹏, 江万寿, 张靖.车载立方体全景影像匹配点的粗差检测方法[J].武汉大学学报·信息科学版, 2014, 39(10):1208-1213 http://ch.whu.edu.cn/CN/abstract/abstract3097.shtml

    Zhang Zhengpeng, Jiang Wanshou, Zhang Jing. A Gross Error Detection Method of Vehicle-Borne Cubic Panoramic Image Sequence[J]. Geomatics and Information Science of Wuhan University, 2014, 39(10):1208-1213 http://ch.whu.edu.cn/CN/abstract/abstract3097.shtml
    [11] 张永军, 王博, 黄旭, 等.影像匹配粗差的局部矢量面元剔除方法[J].测绘学报, 2014, 43(7):717-723 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201407010.htm

    Zhang Yongjun, Wang Bo, Huang Xu, et al.Local Vector Surface Elimination Method for Gross Error of Image Matching[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(7):717-723 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201407010.htm
    [12] 张永军, 王博, 段延松.一种针对大倾角影像匹配粗差剔除的算法[J].武汉大学学报·信息科学版, 2013, 38(37):1135-1138 http://ch.whu.edu.cn/CN/abstract/abstract2787.shtml

    Zhang Yongjun, Wang Bo, Duan Yansong.An Algorithm of Gross Error Elimination for Large Dip Image Matching[J]. Geomatics and Information Science of Wuhan University, 2013, 38(37):1135-1138 http://ch.whu.edu.cn/CN/abstract/abstract2787.shtml
    [13] 徐秋辉, 佘江峰, 宋晓群, 等.利用Harris-Laplace和SIFT描述子进行低空遥感影像匹配[J].武汉大学学报·信息科学版, 2012, 37(12):1443-1447 http://ch.whu.edu.cn/CN/abstract/abstract413.shtml

    Xu Qiuhui, She Jiangfeng, Song Xiaoqun, et al. Matching Low Altitude Remote Sensing Image with Harris-Laplace and SIFT Descriptor[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12):1443-1447 http://ch.whu.edu.cn/CN/abstract/abstract413.shtml
    [14] 徐秋辉, 佘江峰, 宋晓群, 等.利用改进的DCCD和SIFT描述符的影像匹配方法[J].武汉大学学报·信息科学版, 2015, 40(12):1613-1617, 1645 http://ch.whu.edu.cn/CN/abstract/abstract3389.shtml

    Xu Qiuhui, She Jiangfeng, Song Xiaoqun, et al. An Image Matching Method Based on Improved DCCD and SIFT Descriptor[J]. Geomatics and Information Science of Wuhan University, 2015, 40(12):1613-1617, 1645 http://ch.whu.edu.cn/CN/abstract/abstract3389.shtml
    [15] 王之卓.摄影测量原理[M].武汉:武汉大学出版社, 2007

    Wang Zhizhuo. The Principle of Photogrammetry[M]. Wuhan:Wuhan University Press, 2007
    [16] Saleem S, Sablatnig R. A Robust SIFT Descriptor for Multispectral Images[J]. IEEE Signal Processing Letters, 2014, 21(4):400-403 doi:  10.1109/LSP.2014.2304073
    [17] 袁修孝, 李然.带匹配支持度的多源遥感影像SIFT匹配方法[J].武汉大学学报·信息科学版, 2012, 37(12):1438-1442 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201212014

    Yuan Xiuxiao, Li Ran. A SIFT Image Matching Method with Match-Support Measure for Multi-source Remotely Sensed Images[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12):1438-1442 http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201212014
    [18] West D B. Introduction to Graph Theory[M]. New Jersey: Prentice Hall, 2001
    [19] Duchenne O, Bach F, Kweon I S, et al. A Tensor-Based Algorithm for High-Order Graph Matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(12):2383-2395 doi:  10.1109/TPAMI.2011.110
    [20] Chen S Y, Yuan X X, Yuan W, et al. Poor Textu-ral Image Matching Based on Graph Theory[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2016, 41(B3):741-747
    [21] Yuan X X, Chen S Y, Yuan W, et al. Poor Textu-ral Image Tie Point Matching via Graph Theory[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2017, 129(7):21-31
    [22] Ye Y, Shan J. A Local Descriptor Based Registration Method for Multispectral Remote Sensing Images with Non-linear Intensity Differences[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 90:83-95 doi:  10.1016/j.isprsjprs.2014.01.009
    [23] Zhu Q, Wu B, Xu Z X. Seed Point Selection Me-thod for Triangle Constrained Image Matching Propagation[J]. IEEE Geoscience and Remote Sensing Letters, 2006, 3(2):207-211 doi:  10.1109/LGRS.2005.861735
  • [1] 姚永祥, 张永军, 万一, 刘欣怡, 郭浩宇.  顾及各向异性加权力矩与绝对相位方向的异源影像匹配 . 武汉大学学报 ● 信息科学版, 2021, 46(11): 1727-1736. doi: 10.13203/j.whugis20200702
    [2] 李欣, 杨宇辉, 杨博, 尹峰.  利用方向相位特征进行多源遥感影像匹配 . 武汉大学学报 ● 信息科学版, 2020, 45(4): 488-494. doi: 10.13203/j.whugis20180445
    [3] 詹总谦, 李一挥, 王陈东, 郑莉.  顾及局部相对几何变形改正的影像匹配和空三逐步精化方法 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1620-1627. doi: 10.13203/j.whugis20170342
    [4] 叶沅鑫, 慎利, 陈敏, 王继成.  局部相位特征描述的多源遥感影像自动匹配 . 武汉大学学报 ● 信息科学版, 2017, 42(9): 1278-1284. doi: 10.13203/j.whugis20150576
    [5] 王奋飞, 任鑫, 刘建军, 施俊, 李春来.  嫦娥二号影像密集匹配及DEM制作方法 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 918-923. doi: 10.13203/j.whugis20150147
    [6] 徐亚明, 石娟, 安动动, 马旭东.  利用影像分割和匹配特征进行无人机影像变化检测 . 武汉大学学报 ● 信息科学版, 2016, 41(10): 1286-1291. doi: 10.13203/j.whugis20140873
    [7] 徐秋辉, 佘江峰, 宋晓群, 肖鹏峰.  利用改进的DCCD和SIFT描述符的影像匹配方法 . 武汉大学学报 ● 信息科学版, 2015, 40(12): 1613-1617,1645. doi: 10.13203/j.whugis20130753
    [8] 张春森, 吕佩育, 郭丙轩.  基于控制点约束影像的密集匹配及其在考古发掘中的应用 . 武汉大学学报 ● 信息科学版, 2015, 40(12): 1575-1581. doi: 10.13203/j.whugis20130510
    [9] 张永军, 熊金鑫, 余磊, 凌霄.  严密定位模型辅助的国产卫星影像匹配 . 武汉大学学报 ● 信息科学版, 2014, 39(8): 897-900. doi: 10.13203/j.whugis201200178
    [10] 张谦, 贾永红, 胡忠文.  多源遥感影像配准中的SIFT特征匹配改进 . 武汉大学学报 ● 信息科学版, 2013, 38(4): 455-459.
    [11] 张永军, 王博, 段延松.  一种针对大倾角影像匹配粗差剔除的算法 . 武汉大学学报 ● 信息科学版, 2013, 38(10): 1135-1138.
    [12] 闫利, 陈林.  一种改进的SURF及其在遥感影像匹配中的应用 . 武汉大学学报 ● 信息科学版, 2013, 38(7): 770-773.
    [13] 叶沅鑫, 单杰, 熊金鑫, 董来根.  一种结合SIFT和边缘信息的多源遥感影像匹配方法 . 武汉大学学报 ● 信息科学版, 2013, 38(10): 1148-1151.
    [14] 袁修孝, 李然.  带匹配支持度的多源遥感影像SIFT匹配方法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1438-1442.
    [15] 袁修孝, 刘欣.  基于有理函数模型的高分辨率卫星遥感影像匹配 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 671-674.
    [16] 宋妍, 田玉刚, 贾小霞.  基于Zernike矩的多时相遥感影像匹配方法研究 . 武汉大学学报 ● 信息科学版, 2009, 34(10): 1226-1230.
    [17] 江万寿, 郑顺义, 张祖勋, 张剑清.  航空影像特征匹配研究 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 510-513.
    [18] 张祖勋, 张剑清, 张力.  一种利用影像匹配的城区三维景观图生成途径 . 武汉大学学报 ● 信息科学版, 1999, 24(4): 283-289.
    [19] 曾湧, 廖明生, 张剑清, 沈未名.  保持匹配一致性的遥感影像压缩编码 . 武汉大学学报 ● 信息科学版, 1997, 22(3): 245-247,251.
    [20] 李德仁, 王树根.  数字影像匹配质量的一种自动诊断方法 . 武汉大学学报 ● 信息科学版, 1995, 20(1): 1-6.
  • 加载中
图(7) / 表(3)
计量
  • 文章访问数:  1016
  • HTML全文浏览量:  88
  • PDF下载量:  278
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-05-08
  • 刊出日期:  2018-12-05

基于图论的遥感影像误匹配点自动探测方法

doi: 10.13203/j.whugis20180154
    基金项目:

    国家自然科学基金 41771479

    国家高分专项(民用部分) 50-H31D01-0508-13/15

    国家973计划 2012CB719902

    作者简介:

    袁修孝, 博士, 教授, 博士生导师, 湖北名师, 珞珈杰出学者, 主要从事航空航天摄影测量高精度定位理论与方法、高分辨率卫星遥感影像几何处理等的研究和教学工作。代表成果:GPS/IMU辅助空中三角测量等。yuanxx@whu.edu.cn

    通讯作者: 袁巍, 博士生。milaoyw@whu.edu.cn
  • 中图分类号: P237

摘要: 提出一种基于图论的卫星遥感影像误匹配点自动剔除方法。首先以稀疏匹配点为节点分别构建左右影像的完全图;然后利用每个节点所对应三角形的相似度之和为属性值构建导出图;最后通过搜索导出图中属性值最小的节点定位误匹配点。在剔除单个误匹配点的基础上,采用重新构建完全图-导出图-定位误匹配点的循环搜索策略,达到自动探测并剔除多个误匹配点的目的。实验表明,该方法无需建立匹配点间的映射模型,仅利用三角形的相似关系就可以定位误匹配点,与广泛使用的随机抽样一致性粗差探测方法相比,对误匹配点具有更高的识别率和更低的误判率。

English Abstract

袁修孝, 袁巍, 陈时雨. 基于图论的遥感影像误匹配点自动探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
引用本文: 袁修孝, 袁巍, 陈时雨. 基于图论的遥感影像误匹配点自动探测方法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
YUAN Xiuxiao, YUAN Wei, CHEN Shiyu. An Automatic Detection Method of Mismatching Points in Remote Sensing Images Based on Graph Theory[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
Citation: YUAN Xiuxiao, YUAN Wei, CHEN Shiyu. An Automatic Detection Method of Mismatching Points in Remote Sensing Images Based on Graph Theory[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 1854-1860. doi: 10.13203/j.whugis20180154
  • 在卫星遥感影像匹配中,误匹配难以避免,且误匹配率有时会相当高,故误匹配点探测已成为影像匹配的一个必不可少的环节。模拟摄影测量系统采用人工量测方式选取像片连接点,由于数据量小,粗差率低,仅依据简单的“3倍单位权中误差”原则就能定位绝大部分的误判点[1-2]。进入数字摄影测量时代以后,利用影像匹配方法自动提取像片连接点时,得到的匹配点数量巨大,误匹配率颇高,粗差量级很大,人工挑错方法不再适用。为此,人们常用稳健估计方法来自动剔除误匹配点[3]。稳健估计方法一是从最小二乘平差着手,在迭代计算过程中通过不断调整观测值的权值来定位粗差,称之为选权迭代法[4-6]。该方法对中小粗差比较有效,但对大粗差或者高误匹配率的情况,效果并不十分理想[3];二是采用随机抽样一致性(random sample consensus, RANSAC)[7-9]方法,将其与特定的遥感影像处理模型相结合,设计出多种误匹配点探测方法。如张正鹏等[10]充分利用全景影像的对极几何性质,提出了一种多约束条件的RANSAC方法,通过计算匹配点的光流场来剔除误匹配点;张永军等[11]通过引入矢量描述子,假设误差服从正态分布,提出了一种基于局部矢量面元的误匹配点探测方法,也可以通过将像方匹配点拟合成一个曲面来剔除误匹配点[12];徐秋辉等[13-14]利用单应变换和RANSAC算法剔除无人机影像中的误匹配点。

    无论是选权迭代法,还是RANSAC方法,误匹配点检测都需要建立一个全局数学模型[15],一般说来并非易事。尽管一些算法可以利用局部影像的几何特征来检测误匹配点,但是它们无一例外地都假设匹配误差是服从正态分布的,对误匹配率较高的遥感影像匹配而言,这一假设常常难以成立。因此,设计一种不依赖于全局数学模型的局部最优误匹配点探测方法显得十分必要。基于图论的思想,本文提出一种无需建立匹配点间的具体变换模型而仅依靠三角形的相似性就可以检测误匹配点的方法。通过与RANSAC方法的对比实验发现,该方法对误匹配点的探测具有更高的识别率和更低的误判率。

    • 尽管卫星遥感影像立体像对左右影像间存在一定的由地形起伏以及人工建筑物引起的几何变形,但这种高度变化相对于卫星的飞行高度是一个小量,因此这种形变始终保持在一定的范围内,使得影像的几何特征在局部范围内保持不变[16-17]。若将稀疏匹配点构成完全图[18],则在没有匹配误差的情况下,由左右影像中的匹配点分别构成的完全图应该是相似的;若匹配点中存在误匹配点,则以其为节点的匹配三角形间的相似度将变得非常低。如果将当前节点的属性值标识为其他节点的支持率之和,则每个节点应具有相近的属性值。但当完全图中包含有误匹配点时,其属性值一定会低于同名像点的属性值。因此,基于完全图的这一特性就可以设计一种基于图论的误匹配点探测方法,图 1示意了其探测过程。

      图  1  基于图论的误匹配点探测流程图

      Figure 1.  Flowchart of Mismatch Point Detection Based on Graph Theory

    • 以左右影像上的稀疏匹配点为节点,分别构建完全图(即图中每个节点与其他节点都有一条连接边)。误匹配点检测的目的就是利用影像的几何不变特征分辨出误匹配点与正确匹配点。在完全图中有大量的三角形,而在影像的局部范围内,匹配三角形的仿射变换关系是一个几何不变量,这些三角形将成为误匹配点检测的基础。图 2表示由立体像对左右影像上的5对同名像点所形成的完全图。

      图  2  影像匹配点构成的完全图

      Figure 2.  Complete Graph Made up of Image Matching Points

      图 2可以看出,完全图由5个节点组成,共包含10个三角形,而每个顶点涉及到6个三角形,共顶点的6个三角形聚成一个类,形成对该顶点的支持度。在影像的局部范围内,由于影像的几何结构相对稳定,就每个节点而言,其支持度大致相等。

      若存在误匹配点,则由其构成节点的匹配支持度将远小于其他节点的匹配支持度。图 3所示的一对完全图中,一共包含两对误匹配点(6, 6′)和(7, 7′)。以其中任一节点为顶点,一共可形成C62=15对匹配三角形。这些匹配三角形可以分为3类:①不包含误匹配点,设此类匹配三角形的平均相似度为s0;②仅包含1个误匹配点,设此类匹配三角形的平均相似度为s1;③包含有2个误匹配点,设此类匹配三角形的平均相似度为s2。很明显,绝大多数情况下,s0>s1s0>s2

      图  3  包含误匹配点的完全图

      Figure 3.  Complete Graph Containing Mismatched Points

      若某个顶点为正确匹配点,则其匹配支持度为:

      $$ {c_0} = 6{s_0} + 8{s_1} + {s_2} $$ (1)

      若某个顶点为误匹配点,则其支持度为:

      $$ {c_1} = 10{s_1} + 5{s_2} $$ (2)

      将上述两种情况下得到的匹配支持度求差得:

      $$ {c_0} - {c_1} = 6{s_0} - 2{s_1} + 4{s_2} $$ (3)

      由于s0>s1s0>s2,因此c0-c1>0,即不包含误匹配点的节点的匹配支持度远大于包含有误匹配点的节点的匹配支持度。从图 3可以看出,尽管误匹配点会对正确匹配点形成错误的匹配支持度,但总体而言,正确匹配点的匹配支持度要远大于误匹配点的匹配支持度。

    • 构建完全图后可以求出完全图的节点匹配支持度,则可反映出误匹配点的分布情况。因此,在每个完全图中,可依据匹配支持度来定义局部敏感度指标,从而达到探测和剔除误匹配点的目的。若将匹配点构成的两个完全图导出为一个带有属性的完全图(称之为导出图),则每个节点的属性可以用包含该顶点的三角形的支持度作为测度,既可以用三角形描述符的相似度之和来表示,也可以用三角形的3个内角的余弦值来表示。本文将两个三角形的相似度表示为[19]

      $$ s\left( i \right) = {\rm{exp}}( - \frac{1}{{{\varepsilon ^2}}}{(\parallel {\mathit{\boldsymbol{d}}_{\Delta ijk}} - {\mathit{\boldsymbol{d}}_{\Delta i\prime j\prime k\prime }}{\parallel _2})^2} $$ (4)

      式中,$s\left( i \right) $为$\Delta ijk $与$ \Delta i\prime j\prime k\prime $的相似度;ε为高斯核函数的带宽;d为三角形的形状描述向量;‖·‖2表示向量的长度。

      对一个包含m个节点的完全图而言,包含节点i的三角形一共有Cm-12个,这些三角形就形成了一个聚类:

      $$ \begin{array}{l} P = \{ (\Delta ijk;\Delta i\prime j\prime k\prime ), (\Delta imn;\Delta i\prime m\prime n\prime ), \\ (\Delta ipq;\Delta i\prime p\prime q\prime ), \ldots \} \end{array} $$ (5)

      聚类P中的每一个元素表示一对匹配三角形,用pt表示。聚类P可以表示为:

      $$ P = \left\{ {1 \le t \le m, {\rm{ }}t \in 整实数|{p_t}} \right\} $$ (6)

      聚类P对节点i的支持度即节点i的属性值,可表示为:

      $$ a\left( i \right) = \frac{1}{m}\sum\limits_{t = 1}^m {} s({p_t}) $$ (7)

      事实上,式(7)表示了包含节点i的三角形与其匹配三角形之间的平均相似度。例如,在图 4中,节点1的聚类为{(△123;△1′2′3′), (△134;△1′3′4′), (△135;△1′3′5′), (△136;△1′3′6′), (△145;△1′4′5′), (△146;△1′4′6′)},节点1的属性值可以按照式(7)计算。以此类推可以计算其他5个节点的属性,形成一个如图 4所示的两个完全图的导出图。

      图  4  匹配完全图及其导出图

      Figure 4.  Complete Graph and Its Derived Diagram Made up of Image Matching Points

      图 4可以看出,导出图与两个完全图具有相同数量的顶点和边,不同的是导出图是一个顶点带有匹配支持度属性的完全图。

    • 由于导出图中节点的属性标识了聚类对该节点的支持度,因此节点的属性在一定程度上反映了该节点为误匹配点的概率。然而,影像匹配中往往会包含多个误匹配点,致使节点的属性值不能真正反映其是否为误匹配点。为此,本文提出一种迭代的导出图生成算法。其基本思想是:首先利用所有的匹配点对构建两个完全图及其导出图,然后搜索图中属性值最小的节点。若其属性值小于给定阈值,且图中节点的属性值变化量大于阈值,则删除该节点,重新生成完全图及其导出图;若其属性值大于给定阈值,则停止迭代。此时的完全图即为没有误匹配点的完全图,从而完成对误匹配点的探测。该算法的伪代码如下。

      算法1:基于图论的误匹配点检测算法

      Input:匹配点对

      Output:同名像点

      1  begin

      2  do

      3  for i=1…m do

      4  ${a_i} = \frac{1}{m}\sum\limits_{t = 1}^m {} s({p_t}) $

      5  end

      6 对{a1, a2am}进行降序排列

      7  删除最小的属性值an对应的节点n

      8  $ a_n^{(p + 1)} \leftarrow a_n^{(p)}$

      pp+1

      10  while $ \left( {{\rm{abs}}\left( {a_n^{(p)} - a_n^{(p + 1)}} \right) > 0.01\parallel a_n^{(p + 1)} < a} \right)$

      11  end

      算法1中的a为常数,可以由影像中的正确匹配点组成的完全图按照式(7)计算得到。但就影像密集匹配而言,直接使用算法1的效率太低。因此可以对影像进行分块,对每个影像块的匹配点采用算法1进行误匹配点探测,一方面可以加速完全图的生成,另一方面可以减小影像形变的影响。

    • 为了验证本文方法的有效性和适用性,分别对模拟数据和真实数据进行了实验验证。在模拟数据中,人工量测了同名像点并随机添加了一定数量的误匹配点,以误匹配点识别率和误判率两项指标来评价算法的有效性。真实数据系采用基于图论的匹配算法[20-21]所得到的同名像点,分别统计误匹配点剔除后所保留的同名像点数以及匹配精度,以评价算法的效果。

    • 模拟实验是首先在400像素×400像素的局部卫星遥感影像对上人工均匀地量测30对同名像点(图 5),然后加入一组均匀分布的随机点对(经人工辨识,随机生成的点对均为误匹配点,将误匹配率控制在10%~90%),并与经典的RANSAC粗差检测方法进行对比实验。在RANSAC算法中,使用单应变换矩阵作为几何不变量,并将反投影误差阈值设定为3个像素。

      图  5  人工量测的像片连接点

      Figure 5.  Image Joint Points of Artificial Measurement

      为了评价误匹配点检测的效果,本文使用误匹配点识别率r和误匹配点误判率f两个评价指标:

      $$ r = \frac{{{d_f}}}{f} \times 100\% , f = \frac{{{d_t}}}{t} \times 100\% $$ (8)

      式中,df为探测到的误匹配点中真实误匹配点的数量;f为在匹配点集中人为加入的误匹配点的数量(本实验为0~27个);dt为探测到的误匹配点中实际为正确匹配点的数量;t为匹配点集中所有正确匹配点的数量(本实验为30);r表示误匹配点检测算法的正面作用,r值越大说明误匹配点检测效果越好;f表示误匹配点检测算法的负面作用,f值越小越好。

      实验发现,本文方法和RANSAC方法得到的r值均为1.0,这说明两种方法都能检测出所有的误匹配点。图 6绘制了两种方法所得到的f值随误匹配率的变化曲线。

      图  6  f值随误匹配率的变化曲线

      Figure 6.  Change Curve of the f Value with the Mismatch Rate

      图 6可以清楚地看到,本文方法与RANSAC方法的误检率存在明显的差异。当误匹配率不超过60%时,RANSAC方法的f值基本保持在0.4左右;当误匹配率超过60%时,RANSAC的误检率明显上升;当误匹配率为90%时,RANSAC方法将所有的正确匹配点都识别为误匹配点。

      进一步分析图 6不难发现,本文算法的f值要远低于RANSAC算法,且不随误匹配率的变化而改变,具有很好的稳定性。究其原因在于,RANSAC方法采用了随机抽样策略,通过抽样点来拟合变换模型,使用非抽样点来验证模型。随着误匹配点数量的增加,在有限次数的采样中,抽到正确匹配点的概率变小。即使抽到正确的匹配点,由于非抽样点中包含有大量的误匹配点,也难以形成足够数量的一致集,甚至是形成了错误的一致集,从而陷入局部最优。此外,由于影像形变的存在,单应变换无法准确描述同名像点之间的几何映射关系。相比较而言,本文方法的聚类方式避免了局部最优,通过迭代生成导向图而回避了对几何不变量的求解,因此不会受到影像几何变形的影响。

    • 表 1列出了用于3组实验的高分辨率卫星遥感影像的主要参数,利用基于图论的匹配方法自动提取了同名像点,通过本文方法与RANSAC方法对其进行了误匹配点检测比较实验。3组实验检查点数均为36个。为了评价误匹配点剔除的效果,本文采用匹配点精度RMSE(root mean square error) [22]和匹配点分布D两个评价指标[23]

      $$ \left\{ \begin{array}{l} {\rm{RMSE}} = \sqrt {\sum\limits_{i = 1}^n {\left( {{x_i} - x{\prime _i}} \right)/n} } \\ D = \frac{1}{{m - 1}}\sqrt {\sum\limits_{i = 1}^m {{{\left( {\frac{{{A_i}}}{{\bar A}} - 1} \right)}^2}} } \times \sqrt {\sum\limits_{i = 1}^m {{{\left( {{S_i} - 1} \right)}^2}} } \end{array} \right. $$ (9)

      表 1  实验影像的主要技术参数

      Table 1.  Technical Parameters of Selected Experimental Images

      实验组号 遥感卫星 影像区域 影像大小/像素 地面采样间隔/m
      1 高分一号 高山区 18 192×18 000 2.02.1
      资源三号 24 530×24 575
      2 高分二号 城区 9 376×9 136 1.02.1
      资源三号 24 530×24 575
      3 资源三号(前视) 城区 24 525×24 419 2.13.5
      资源三号(下视) 16 292×16 348

      式中,n为检查点数;xi为检查点的像平面坐标;xi为根据单应变换模型计算得到的像平面坐标;m为匹配点构成的不规则三角网中三角形的总数;Ai为三角网中第i个三角形的面积;A为三角网中所有三角形的平均面积;Si为第i个三角形中的最大内角。

      图 7示意了匹配点的精度。从图 7可以看出,自动剔除误匹配点后,影像匹配精度有了明显的提高。仔细比较本文方法与RANSAC方法不难发现,在实验1与实验3中,本文方法优于RANSAC方法,而在实验2中两种方法效果相当。究其原因,第二组影像为城区,地形比较平坦。当地形为一个平面时,影像间的几何关系可以使用单应变换模型来描述,因此RANSAC方法能剔除绝大多数的误匹配点,从而使得影像匹配点具有较高的精度。本文方法与RANSAC方法的精度一致,充分说明了本文方法的有效性。第三组影像虽然也是覆盖城区,但由于相机的视角不同,使用单应变换模型描述影像间的几何关系存在较大误差。而本文方法将这种模型误差限制在一个面积较小的匹配三角形内,比整体的单应变换模型引起的误差要小得多,使剔除误匹配点的效果要好得多。同样的结果还出现在实验1中,由于第一组影像覆盖的是高山区,地形起伏造成了较大的投影差,使得单应变换的模型误差较大。

      图  7  影像匹配精度的对比图

      Figure 7.  Contrast Diagram of Image Matching Precision

      不仅如此,经过误匹配点探测后,在3组实验中,本文方法保留的匹配点的数量均多于RANSAC方法处理后的匹配点的数量(详见表 2)。这再一次证明了模拟实验中的结论——本文方法的误判率较低,能尽量多地保留正确的匹配点,具有较高的稳定性。

      表 2  自动剔除误匹配点后保留的同名点数

      Table 2.  Number of Homonyms Reserved After Automatic Elimination of Mismatched Points

      实验组号 RANSAC方法 本文方法
      1 10 076 11 942
      2 6 498 6 530
      3 21 598 22 239

      匹配点离散度见表 3。由表 3可以看出,由于误匹配点探测会剔除一部分点,无论是本文方法还是RANSAC方法,在剔除误匹配点后,匹配点的离散度均有不同程度的升高,这说明匹配点的分布质量都有所下降,但本文方法对匹配点的分布状况影响较小。正是因为本文方法较RANSAC算法能保留更多的正确匹配点,且对匹配点的分布影响更小,因此经本文方法处理后的匹配点具有更高的定位精度和可靠性。

      表 3  影像匹配点的离散度

      Table 3.  Discreteness of Image Matching Points

      实验组号 不剔除误匹配点 RANSAC方法 本文方法
      1 5.12×10-5 1.91×10-4 9.74×10-5
      2 8.90×10-5 1.12×10-4 1.10×10-4
      3 3.20×10-5 5.50×10-4 4.60×10-5
    • 本文采用基于图论的误匹配点探测方法,将稀疏匹配点构建成完全图,并利用完全图构建的导出图进行迭代搜索,可自动剔除影像匹配中的误匹配点。实验表明,本文方法在模拟数据中的误匹配点识别率为100%,误检率仅为3.5%;在实际数据的实验中,本文方法对匹配精度的改善是较为明显的。相对于广泛使用的RANSAC方法,经本文方法处理后的影像匹配点具有更高的精度和更好的点位分布。然而,当匹配点较多时,尤其是在影像密集匹配中,构建完全图是相当耗时的,在迭代导出图时,由于需要重构完全图,也需要耗费大量的CPU时间,因此本文算法在计算效率上还有待提高,影像分块、GPU并行计算将是本文进一步研究的方向。

参考文献 (23)

目录

    /

    返回文章
    返回