1、 攻读硕士学位研究生学位（毕业）论文 面向点云采集的多视图像匹配技术研究 类 型 农业推广硕士 领 域、方 向 农业信息化 研 究 生 指 导 教 师 完 成 时 间 中国 陕西 杨凌 面向点云采集的多视图像匹配技术研究 摘 要 针对尺度不变特征转换 SIFT（ Scale-invariant feature transform）算法误匹配率高且运行效率低的问题，提出一种改进的双向 SIFT 特征匹配算法。本研究以基于 SIFT算法的图像匹配技术为研究对象，在详细分析了其原理、实现过程、主要优势及不足后，针对其缺陷进行改进，主要内容如下： （ 1）在去除误匹配方面，首先采用双向匹配消除部分误匹
2、配，从根本上减少匹配点的数量，然后结合视差梯度约束和 RANSAC 算法进行特征点对的提纯。本研究在传统的 SIFT算法的基础上，对 SIFT特征向量进行正反两次匹配，从而提高匹配的精确度，这对于利用匹配点对实现空间姿态和位置的自动标定尤为重要。为了从 根本上增加匹配点对的数目，又保证匹配的准确性，本研究同时提出了利用交集和并集去除误匹配的方法，取并集作为出匹配点对，利用准确度较高的交集估计基础矩阵，然后利用基础矩阵去除并集中的误匹配。 （ 2）在提高运行速度方面，本研究首先在初匹配中采用 K 邻近算法，其次对视差梯度约束进行改进，减少迭代次数来降低耗时。传统的视差梯度约束算法大概可以消除约
3、20%的误匹配，每次迭代只能去掉 一 个误匹配点对，当迭代次数过多的时候，严重影响程序的运行速度。本研究算法采用改进的视差梯度约束算法，将第 三 步中 “去掉最大视差梯度和对应的点对 ”改为 “去掉所有视差梯度和大于最小视差梯度和 3 倍对应的点对 ”。改进后，每次迭代可去除多个误匹配点对，减少迭代次数，算法的耗时也减少。 关键词 ： SIFT算法；视差梯度约束； RANSAC 提纯；特征点；误匹配 RESARCH OF ACQUISITION ON MULTI-VIEW IMAGE OF POINT CLOUDS ABSTRACT An improved bidirectional SIFT
4、 feature matching algorithm is proposed for the high mismatching rate and low operation efficiency of SIFT algorithm. Based on Image-Matching-Technology with SIFT algorithm as the research object, we analyzed the principle, implementation process, and the main advantages and disadvantages in detail,
5、 and also improved the defect. Finally, the main results are as follows: （ 1） To remove the mismatching, there are two steps to follow. First, SIFT bidirectional matching algorithm is taken to eliminate part of the mismatch. Second, disparity gradient constraint and RANSAC algorithm are used to puri
6、fy the matching points. On the basis of traditional SIFT algorithm in this paper, we processed two matching in positive and negative for SIFT feature vector. It will improve the accuracy of the matching, and is important to realize automatic calibration of space posture and position using matching p
7、oints. In order to increase the number of matching points fundamentally and ensure the accuracy of matching, this paper also puts forward the method of using intersection and sets for mismatching removing, and selects sets as the matching points. And the fundamental matrix was estimated based on the
8、 intersection with high accuracy, then using fundamental matrix for mismatching removing in the sets. （ 2） To improve the speed of process, it is not only K nearest method was taken at the beginning of matching, but disparity gradient constraint is also improved, in order to reduce the iterations to
9、 lower the consuming time. Traditional disparity gradient constraint algorithm can eliminate about 20% of the match probably, and each of the iterations can only remove a match point by mistake, what is more, when the number of iterations are too much, the running speed of the program can be serious
10、ly influenced. In this paper, the improved disparity gradient constraint algorithm was adopted, in which the third step of “remove the biggest disparity gradient and the corresponding point on“ was changed into “get rid of all of the disparity gradient and 3 times greater than the minimum disparity
11、gradient and the corresponding point on“. After that each of the iterations can remove more than one false match point, and the number of iterations is reduced, the time of the algorithm is reduced too. KEYWORDS： SIFT; Disparity Gradient; RANSAC algorithm; Feature Point; Mismatching 目 录 第一章 绪 论 .1 1
12、.1 研究目的与意义 .1 1.2 国内外研究现状 .2 1.3 研究的主要内容 .4 1.4 论文的组织结构 .6 第二章 立体匹配原理及方法 .7 2.1 立体匹配 .7 2.1.1 立体匹配原理 .7 2.1.2 立体匹配方法 .8 2.1.3 相似性度量 . 10 2.2 极线约束算法 . 10 2.2.1 数据筛选的约束条件 . 10 2.2.2 极线约束 . 11 2.3 视差梯度算法 . 11 2.4 SIFT匹配算法 . 12 2.4.1 SIFT算法相关术语 . 12 2.4.2 SIFT算法的特性 . 13 2.5 本章小结 . 17 第三章 具体算法设计 . 18 3.1
13、 初匹配点的获取 . 18 3.2 剔除误匹配 . 19 3.3 特征点 提纯 . 22 3.3.1 视差梯度约束 . 22 3.3.2 RANSAC 去除误匹配 . 24 3.4 算法步骤 . 27 3.5 改进后的理论分析 . 28 3.6 本章小结 . 29 第四章 实验结果分析 . 30 4.1 实验结果 . 30 4.1.1 亮度变换和尺度变化的匹配 . 30 4.1.2 旋转变换的匹配 . 32 4.2 数据分析 . 34 4.2.1 改进算法数据分析 . 34 4.2.2 SIFT算法数据对比 . 36 4.3 实验结论 . 38 4.4 本章小结 . 38 第五章 总结与展望
14、. 39 5.1 总结 . 39 5.2 展望 . 39 参考文献 . 40 致 谢 . 43 作者简介 . 44 第一章 绪 论 1 第一章 绪 论 1.1 研究目的与意义 自 20世纪 70年代以来，科学家将视点逐步转移到了视觉计算理论上，新兴的立体视觉技术取得了广泛的关注。立体视觉作为一门复杂的交叉学科，它与认知心理学和视觉神经系统科学都有较为密切的联系。立体视觉问题需要从根本上彻底解决，但科学家们首要面临的问题就是理论和实验两方面的挑战、自然场景的变换和认知行为的复杂度，同时视觉行为意义上的定量理论还需要大量实验进行推 导和证明，因此立体视觉匹配技术的发展还存在着许多未知的理论和方法，
15、具有巨大的发展空间。简单的说，视觉理论是一门具有复杂性且涉及面很广泛但发展尚未成熟的学科。立体视觉技术发展到现如今，在科学研究和实际应用两个层面上遇到的技术解决方案都是针对具体科研课题和应用瓶颈提出的。例如对三维场景的快速恢复技术，基本上只局限于图像中景物的可视部分进行的，对于物体被隐藏起来的部分，基本无法进行解析处理。利用景物的局部信息恢复景物真实的、完整的表面信息确实很有难度，同时具有相当的挑战性。在立体视觉匹配技术的长期研究过程中，发现 了几个较为普遍存在的问题，对于一些非完全漫反射的物体表面、纹理信息缺乏的图像相关区域、物体边缘信息不明确或边缘深度不连续和遮挡等相关现象，匹配算法难以取
16、得准确率较高的匹配结果，匹配算法的性能也受到了一定程度的影响和干扰，甚至直接导致误差的出现。 立体匹配是双目体视技术中最重要，最复杂也是最困难的一步。当二维图像特征点提取后，关键任务是匹配，也就是寻求左 (右 )图像中的每个特征点在右 (左 )图像中的对应点。由于将空间三维场景投影为平面二维图像时，同一景物在不同视点下的图像中存在着明显差异，并且场景中的噪声干扰、光 照条件、景物的物理特性与几何形状、摄像机特性等诸多变化因素都将被综合到单一的图像灰度值中，因此仅由灰度值来定性以上这些因素和特征是十分困难的。为了求解对应点和减少错误匹配，人们建立了诸如唯一性约束、连续性约束、外极线约束、一致性约
17、束等许多约束，然而随着约束条件的增加，匹配难度相应增大，匹配的选择性空间相应缩小。 随着计算机视觉技术日新月异的发展，图像匹配技术被广泛地应用于社会科学等各个领域，例如三维重建、立体视觉、遥感图像分析等。同时，在当今高速发展的社会中，图像匹配技术也具有广泛的应用前景，其中包括疾病的 诊断、地形地貌的勘测、目标跟踪技术、指纹识别、文字识别及相关场景的分析等。目前，各国都是在努力进行研究和发展图像匹配技术，其主要原因是通过该项技术可以促进国家军事力量的发展，例如战斗机中导航系统的定位功能就是基于图像匹配技术的基础之上进行研发定制的。该技术同时也受到了各国科学家的偏爱，大力发展并将此应用于实际中，对
18、于国民军事力量是质的飞跃。 21世纪，技术才是发展的唯一动力，立体匹配技术又是各国军事发展的核心动力，由此可以看出图像匹配技术的重要性。图像处理主要是对图像信息进行加工进一面向点云采集的多视图像匹配技术研究 2 步处理，以满足人们的视觉、 心理和实际应用上的要求。图像匹配是其中最为重要也是最为困难的一步。图像处理技术主要包括图像分析、图像识别、图像特征描述、图像增强、图像复原、图像分割等一系列图像处理的具体功能，这些应用图像处理技术的功能都为新兴的机器视觉系统的应用提供了全方面、不同的辅助手段 （ D Scharstein and R Szeliski 2002） 。图像匹配一般是针对两幅图像
19、，以获得它们的共同元素，主要处理不同时间段、不同参数的传感器或者不同视角下 获得的同一场景的两幅图像或者多幅图像进行特征点提取与匹配的过程 （ 何东健等 2003） 。其实质就是给定一幅图像中的一个点，寻找另外一幅图像中的对应点，这两个图像点为空间同一个点分别在两幅图像上的投影。立体视觉就是由拍摄的不同角度，从而获得两幅或者多幅有重叠区域的图像，根据立体匹配技术来获取物体的三维几何信息，而立体匹配技术的实质就是通过事先给定一幅图像中的一点，然后通过三维投影等原理寻找另外一 幅图像中的对应点，这两个图像点均为空中同一点在两幅图像上的投影 （ J.E.W. Mayhew and J.P. Fris
20、ky 1981;张辉等 2009） 。目前，许多基于双目立体技术的测量方法通常是先进行 前期的立体匹配，然后再在匹配生成的视差图上使用三角法或其他方法进行三维数据提取，便于后期分析处理。 从图像自动提取三维信息的过程中，图像匹配是一个重要的环节。但是，立体图像匹配方法在图像纹理信息重叠、遮挡等区域存在着较高的不可靠性。空间中的一点具有三维信息，而通过摄像机拍摄的图像 只具有简单的二维图像信息，不同视角下获得的图像具有较大的差异性 （ C.F. Olson and L.H. Matthies 1998; D. Geiger and J.A. Vlontzos 1993） 。有很多因素使得场景中的
21、点在图像 上成为不稳定的点，如拍摄的角度、光照的影响、噪声的干扰等一些因素。因此，要准确的对二维图像进行无误差匹配非常的困难。也正是如此，立体匹配技术的研究在近些年中得到了重视。 1.2 国内外研究现状 作为计算机视觉领域的重要阵地，立体匹配技术近年来逐渐形成 了一股研究热潮。在国内外的同类近期研究中，主要是改进的匹配策略 （ Zhang W et al. 2007） 、迭代松弛算法 （ Yoon K J et al. 2006） 、边缘检测算法 （ 胡少军等 2007） 、自适应迭代松弛的立体点对匹配算法 （ 张辉等 2009） 、分级 立体 匹配算法 （ 李刚等 2009） 、采用最小二乘
22、法进行点对匹配算法 （ 张辉等 2009） 、 SURF算法的改进 （ 宋延爽和耿楠 2012） 。 1997年是 Schmid和 Mohr对图像匹配技术研究的开创性时刻，他们将不变的局部特征匹配进一步扩展到解决一般性的图像识别等相关问题，即通过使用一个点的特征与现有的大型点库图像数据库进行匹配对比。同时他们还对 Harris角探测器进行了改良，通过Harris角探测器来获取兴趣点，但实验过程中他们始终都是在使用同一个图像局部区域的旋转不变的描述子来代替相关窗口。这些特征可以在两幅图像 或者多幅图像之间进行任意方向、任意角度变化时进行匹配处理。此外，他们还通过多次试验，证明多特征匹第一章 绪
23、论 3 配具有可实时性，通过识别一致的匹配特征聚类，可以在遮挡和混杂的情况下顺利完成一般的识别工作。 Basri等人在 1998年通过多次试验证明了一种新算法，通过提取局部区域边界或边缘的信息，进行物体识别，对于后来识别功能的发展奠定了道路。后期人们多次尝试吸纳其他一些特征或有用属性，例如颜色信息、运动信息、图形背景识别或背景色彩、区域形状描述子和立体图景提示等。 在 2000年， Schiele和 Crowley提出自己的新想 法，充分利用多维直方图来进行概括总结，得到图像区域内的测量值的具体分布情况，最终通过该方法获取得到的这种特征算子对于纹理明显的或较为复杂的目标尤为有效。 Carnei
24、ro和 Jepson在 2002年提出了一种较为新的思想，他们提出了一种基于相位的局部特征的特征描述子，他们主要针对改善光照对图像特征点提取与匹配的影响，它们主要是通过用相位来表示而不是采用局部空间频率的量级。 2003年， Fitzgibbon（ 2003） 通过多次试验，引入了一种高性能的鲁棒因子，通过Levenberg-Marquardt算法来优化 对应的代价函数，取得了一定的成效。该算法虽然从根本上改善收敛的窄带，但是算法本身对初始值的过渡依赖使得算法具有一定的局限性，噪声、聚类和外点的影像等外界条件都可能会导致该高性能因子失效。 Yoon K J等人在 2006年提出了将迭代松弛算法
25、应用匹配方法中，主要用于基于区域的匹配方法中，通过利用各种大小不同权重值的窗口进行特征点搜索，该算法提高了准确率，但却增加了运算的工作量，从而使得算法整体的效率并不是很高。 2007年，胡少军（ 2007）提出边缘检测法提取小麦叶片边缘数据，根据小麦叶片生长曲线将边缘数据映 射到三维空间。实验结果表明，该方法可以获得较为准确的边缘点的原始数据。 2008年， Thomas（ 2008） 提出了一种新的匹配算法，通过对非刚体变换图像模型进行分析处理，从而使之达到像素集匹配。在图像的四维图空间中连续的进行迭代，从而优化目标函数。其中利用这一思想的代表算法就是 ICP算法 （ Sun CM 2002
26、） ，首先假定给出一组初始值， ICP算法主要采用的是欧式距离，将之作为匹配度量的函数，通过匹配度量函数计算变换系数矩阵，最终将得到的系数值带入初始的目标函数，进行连续多次的迭代优化，直至达到目标要求或最 大迭代次数为止。但该算法也存在不足，容易造成局部最优，即具备最大或最小值的存在，同时该算法需要有个前提 条件就是具有一个良好的匹配初始值，但初始值的获取又成了新的问题 （ WONG S Set and CHAN K L 2010） 。 2009年，张辉等人提出了新的匹配算法 采用自适应迭代松弛的方法进行立体点对的匹配。该算法采用的是两步法，即为构造和优化。在该算法中，涉及到了视差梯度算法，这
27、是该算法的核心之处。算法的具体思想如下：首先利用视差梯度约束来构造匹配支持度函数；然后通过松弛方法优化该函数来完成立体点对的 匹配。由于利用了动态更新松弛匹配过程参数的方法，因此有效地降低了误匹配率和误剔除率。在此基础上还面向点云采集的多视图像匹配技术研究 4 提出了对松弛过程结束后的匹配结果，再次使用视差梯度约束来进行进一步检验的策略，该策略能够以一定幅度的误剔除率提升为代价， 大幅度降低了误匹配率，从而可满足许多要求严格限制误匹配率的应用 （ MacLean WJ 2006） 。算法中并没有涉及到匹配检验，得到的匹配对中可能存在一对多的情况。 同期，张辉等人 还提出了采用最小二乘法进行点对
28、匹配的算法，利用带权值的匹配窗口 （ 李伟等 2007） ，同时提出了用生长法进行初始匹配，可 以大幅度地减少算法迭代次数，从根本上提高匹配速度。缺点是采用固定的权值进行窗口匹配，并没有大幅度减少误匹配率。 李刚 （ 2010） 提出首先提取双目图像对的边缘特征点 , 然后对特征点的梯度不变性与奇异值特征不变性进行分析 , 建立基于不变量特征的二级匹配算法 , 求解基础矩阵。通过基础矩阵，可以系统地完成三级立体匹配。算法简单而且具有实用性，对目标识别、目标 跟踪以及三维表面的恢复与重建具有重要的意义，但总体精度有待提高 （ 蒋明等 2000） ，同时算法具有一定的局限性，只针对边缘的特征点，这
29、就要求边缘图像的清晰度和准确 性。 宋延爽 （ 2012） 利用计算性能优越的 SURF算法对所选取的关键帧进行特征点提取，使用基于哈希映射的特征点匹配算法加快特征点的匹配，并结合 RANSAC算法剔除误匹配点对。该算法的鲁棒性较好，可以实现快速匹配，保证实时性。 在国内外众多算法研究中，几乎都没有从根本上提高特征点匹配的准确性。后期将以一定幅度的剔除率为代价，大幅度降低误匹配率，以满足许多严格要求限制误匹配率的应用。 1.3 研究的主要内容 图像匹配技术的主要任务就是通过提取相对较为稳定的特征，随后进行特征点的描述。这里提到的稳定一词的可以理解 为是在各种复杂变化的因素下，局部特征仍旧具有较
30、强的稳定性。各种复杂的因素有许多，例如对于外界光源变化、对于图像的整体尺度变化、拍摄角度的变化及外界环境的变化，同时还有噪声的影响、物体之间的遮挡以及物体之间的相对运动等。要求得到的局部特征可以处 理以上这些情况，并不受到过多的影响，从而保证了后期匹配的准确率 （ Sun CM 2002; 吴庆双等 2011） 。若局部特征并不受这些影响因素的影响，则将这些变量称之为不变量。例如旋转不变量，要求选取的局部特征必须能够适应视觉角度的变化。 局部特征采纳的具体依据是该特征可以 从根本上增强匹配的准确率，同时对鲁棒性有较为明显的提高。通过计算可以得到它们的计算成本，若计算成本远小于其他特征的计算成本
31、，则该局部特征定义为可以采纳的局部特征。因此，此后的许多应用系统可能都是由很多特征类型组合而成。 通过图像 的局部特征可以构造特征描述符，相对较为明显的特征有角点、边缘等 （ D.Chetverikow et al. 2005; W.J. Rockledge 1997） 。为了便于后期的特征点匹配处理，将局部特征的描述符进行重组第一章 绪 论 5 和变换，最终得到能够满足要求的特征向量，根据描述符的特性可以推出特征向 量同样具有一定的稳定性，但特征向量将更便于后期的计算。总而言之，特征向量的形成促使将图像中的匹配问题转为特征点的匹配，再转为空间特征向量的聚类问题。 图像匹配技术的核心主要是指通
32、过相关的匹配算法进行特征点的匹配，范围主要在两幅或两幅以上的图像之间，该过程叫做识别同名点的过程，通常将已知的目标图像或原始图像称为模板图像，即为匹配模板；同时在待搜索图像中，搜索到的可能与模板 图像具有相对应特征的子图称为目标图像，即为该模板的待匹配的图像 （ 张桂林和徐捷1997） 。图像匹配是指同一场景的物体在不同时间或者不同角度拍摄 的两幅或两幅以上的图像之间寻找相互对应关系，图像匹配技术属于计算机视觉领域的一个小分支。对于二维图像匹配问题是这样定义的，两幅或两幅以上的图像在空间和灰度上的映射。通过转化，得到固定尺寸的二维矩阵 1F 和 2F ，用 1F 和 2F 分别代表两幅图像，用
33、 1( , )F X Y和 2( , )F X Y 分别代表其对应位置 ( , )XY 上的具体灰度值，则两幅图像之间的映射可具体表示为： 2 ( , ) ( 1 ( ( , ) ) )F X Y G F H X Y （ 1-1） 其中，公式 1-1中 H 具体表示为一个抽象的二维空间坐标变换，即 ( , ) ( , )X Y H X Y ，函数 G 表示为一维灰度变换。 因为拍摄图像的时间不同造成光照的影响、拍摄的角度的影响、传感器本身的缺陷及噪声等因素的影响， 从根本上造成图像中存在失真性和几何差异性，甚至几何上的畸变情况 （ S.A. Lloyd 1987; 仲启媛等 2002） 。前期
34、对图像进行简 单的预处理时也会导致误差的增大。在交错的情况下，如何从根本上大幅度提高匹配算法的精度、匹配的准确性、匹配运行速度及相关速率和适应性成为研究过程中主要关注的热点。 本研究提出了一种基于 SIFT特征的图像特征点提取与匹配算法。通过传统 SIFT算法的思想进行特征的提取，利用相似性原理进行欧式距离的计算。接着得到初始的匹配对，不断地对比例阀值进行调整，得到了匹配点对，使用改进后的 RANSAC算法进行下一步的特征点提纯匹配，进一步确保提高准确率。 利用 SIFT算法在三维重建方面的优势，并为了降低算法的错配率，以准确实现 空间位置和姿态的自动标定，其过程主要包括图 1-1中的四个部分。算法分别通过 SIFT双向匹配中匹配阈值的选择、视差梯度约束，以及RANSAC算法逐步降低算法错配率；同时为了提高算法
