图像特征点提取及匹配算法研究论文VIP

本 科 毕 业 设 计 (论 文 )题 目 名 称 ： 学 院 ： 专 业 年 级 ： 学 生 姓 名 ： 班 级 学 号 ： 指 导 教 师 ： 二 O 一 O 年 月 日 I目 录摘 要 .IIIABSTRACT.IV第一章 绪论 .11.1 研究背景 .11.2 研究现状综述 .21.2.1 特征点提取研究现状 .21.2.2 特征点匹配研究现状 .41.3 研究内容 .51.4 论文组织结构 .6第二章 图像特征点提取算法研究 .82.1 Harris 特征点提取算法 .82.1.1 Harris 特征点检测原理 .82.1.2 Harris 特征点检测步骤 .92.1.3 实验分析 .92.2 SIFT 特征点提取算法 .122.2.1 SIFT 特征点提取算法原理及步骤 .122.2.2 实验分析 .162.3 本章小结 .19第三章 改进的 H/S 特征点提取算法 .203.1 H/S 算法分析 .203.1.1 H/S 算法提出的可行性分析 .203.1.2 H/S 算法结合方案研究 .213.2 H/S 算法实现 .223.2.1 多尺度特征点检测 .223.2.2 特征点描述 .233.3 实验分析 .253.3.1 算法评价标准 .253.3.2 分情况特征点提取结果分析 .253.4 本章小结 .27第四章 基于 H/S 的特征点匹配方法 .294.1 相似三角形方法局限性分析 .294.1.1 三角形匹配原理 .29II4.1.2 三角形相似方法局限性 .314.2 改进的相似三角形匹配方法实现 .314.2.1 三角形选取方案研究 .324.2.2 相似三角形检索方法改进 .334.2.3 多模板改进方法分析 .354.3 实验结果与分析 .364.4 本章小结 .39第五章 工作总结与展望 .405.1 工作总结 .405.2 工作展望 .41致 谢 .42参考文献 .43III摘 要图像匹配是图像处理领域的基础课题，在图像拼接、全景视图、对象识别等计算机视觉方面有广泛应用。图像匹配分为基于灰度的方法和基于特征的方法，前者简单易行，但算法时间复杂度高，难以处理图像存在旋转和尺度变化等情况，后者在适应性和速度方面有很大优势，但图像特征的提取以及如何建立特征之间的对应关系一直是这类方法的研究难题。本文提出了一种新的特征点检测算法，并根据三角形相似原理，提出一种改进特征点匹配方法。本文首先对两种特征点提取算法(Harris 算法和 SIFT 算法)进行分析比较，Harris 角点检测算法效率高，但对尺度变化和抗噪性的鲁棒性差，SIFT 算法对尺度变化及抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高，本文结合两种算法的优点，提出了一种新的 H/S 特征点提取算法，该算法特征点检测效率高，并且尺度不变性及抗噪性得到很大改善。在采用新的 H/S 特征点提取算法得到图像中特征点后，对特征点匹配方法进行研究。传统的三角形相似匹配方法虽然实现简单，鲁棒性好，但时间复杂度高，针对此局限性，本文提出了一种改进三角形匹配方法，将传统方法被动搜索相似三角形变为在复数空间下选择基线后主动构造相似三角形，并利用特征点组成基线向量对应三角形组得到多个模板在实物图中匹配，提高了改进算法的实时性和稳定性。关键词 特征点，H/S 算法，机器视觉，相似三角形检索IVABSTRACTImage matching is a basic problem in the field of image processing, it has wide applications in computer vision, such as image stitching, panoramic view, object recognition and so on. It includes gray-based method and feature-based method. The former method is simple, but the time complexity of this algorithm is high, especially its difficult to deal with the situations of image rotation and scaling. The latter method is much more easily overcoming the difficulties which encountered by the former method, but how to create the corresponding relationships between the images features is always a difficult problem. A new feature point extracting method is proposed in this thesis, and a new matching method which is based on similar triangles is proposed.The thesis firstly analyses and compares two kinds of extracting feature points algorithms( Harris algorithm and SIFT algorithm ), Harris algorithm has high efficiency and poor anti-scaling and anti-noise performance, SIFT algorithm has good robustness about anti-scaling and anti-noise, but the time complexity of this algorithm is high, and it has a great demand on image texture. The thesis combines the advantages of these two algorithms, a new H/S algorithm which is used to extract feature points is proposed, this algorithm has well efficiency, meanwhile, the anti-scaling and anti-noise performance is greatly improved. While the feature points of images are obtained by using the new H/S algorithm, the matching methods are studied. Traditional similar triangles matching method is simple and has good robustness, but the time complexity of this algorithm is high, because of this limitations, the thesis proposes a improved matching method which is based on similar triangles, making the traditional passively searching similar triangles to select the baseline to actively construct similar triangles. The algorithm uses multi-templates to match in the image, the real time ability and stability of the algorithm is improved.KEY WORDS feature points, H/S algorithm, computer vision, similar triangles retrieval图像特征点提取及匹配算法研究 第一章 绪论1第一章 绪论1.1 研究背景图像特征点提取和匹配是图像处理研究领域中的基础课题，也是机器视觉的关键技术之一，广泛应用于虚拟现实、视频压缩、图像复原、图像数据库检索等技术中，具有广泛的应用前景及社会经济价值。因此，特征点的提取和匹配越来越得到研究人员的关注。图像匹配可以认为是在不同时间或相同时间、从不同视角或相同视角对同一场景拍摄的两幅或者多幅图像进行的空间域上的匹配过程。它通过建立两幅图像之间的对应关系，确定相应的几何变换参数，对两幅图像中的同一目标进行匹配。近几年在许多领域中，都对图像配准进行了大量的研究，比较有代表的有：模式识别、自动导航、遥感领域、医学诊断、计算机视觉等。经过国内外研究者多年的努力，人们提出了多种图像匹配方法。这些方法大致可分为基于灰度值的方法和基于特征的方法两大类 1。基于灰度的匹配就是逐像素地把一个以一定大小的实时图像窗口的灰度矩阵与实际图像的所有可能的窗口灰度矩阵按某种相似性度量方法进行搜索比较的匹配方法。为了克服基于灰度匹配方法缺点，提出了基于特征的匹配方法。特征匹配方法首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像之间特征的匹配对应关系，常用的特征基元有点特征、边缘特征和曲线轮廓及区域特征等。由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在基于特征的匹配中有更加广泛的应用。如何建立图像兴趣点之间的对应关系一直是这类方法的研究热点。目前已有许多有关此类问题的如 Sanjay Ranade 等提出的松弛算法 2、Zsolt Mikls 等提出的三角形匹配算法 3等。特征点匹配方法首先依赖于好的特征提取方法，特征点提取方法是从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数或数据量的压缩。特征提取方法一般包含两个阶段：一是对图像进行分割，提取目标区域或其边界，抽取目标的基本特征，如灰度、纹理、形状描述。二是找出或构造目标作某种运动或无论目标作何种运动都不变化的目标图像特性的特征不变量。当提取特征点数目过多时就会存在大量的干扰信息(如：伪匹配点)，这将影响匹配的正确率和速度，当提取特征点过少时，将不利于精确匹配。同时特征点匹配方法需要保证在两幅图像点集中存有大量有效点，而当图像特征点较多时，算法复杂度较大。本文基于以上热点问题展开研究，首先对两种特征点提取算法(Harris 算法和图像特征点提取及匹配算法研究 第一章 绪论2SIFT 算法)进行原理分析及实验比较，得出 Harris 角点检测算法效率高，但对尺度变化和噪声干扰鲁棒性差，以及 SIFT 算法对尺度变化及抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高等结论，提出一种在多尺度下提取图像稳定特征点的 H/S(Harris/SIFT)算法，并在此基础上采用复数空间中相似三角形多模版匹配算法进行特征点间匹配，通过理论分析及实验证明该方法在时间复杂度方面的改进和在图像存在旋转、缩放情况时匹配的准确性和有效性。1.2 研究现状综述1.2.1 特征点提取研究现状在实际问题中图像可能受到噪声、背景的干扰，也可能发生平移、尺度、视角、光照等变化，如何选择合理的特征和描述算子，使得这些特征不仅具有良好的表征性能，而且在上述因素变化下保持相对不变(即不变性)，直接决定了基于特征点的图像匹配效果。以计算机视觉的不变理论为基础，对图像特征的不变性研究是目前图像处理的重要环节，吸引了众多研究工作者的兴趣。图像特征的不变性研究目前已取得了大量的研究成果。这些研究主要集中于以下几方面：1) 不变特征的选取，如图像的点、线、轮廓，像素点的强度、曲率、矩、特征向量等。2) 不变性获取的途径，如通过特征变换、小波理论、神经网络、编码技术、特征描述子的构造等。3) 不变特征的描述，如 SIFT 描述子、PCA-SIFT 描述子、不变矩描述子、傅里叶描述子、微分不变描述子、颜色描述子、链码描述子等。近年来，不变特征已引起国内外研究者和研究机构的广泛关注。在相关领域中，具有代表性的研究机构是加拿大 British Columbia 大学智能计算实验室，该实验室开展了局部仿射不变特征提取方面的工作，其研究成果已应用于目标识别 4、全景图拼接 5、虚拟现实 6、机器人自主导航 7等领域。芬兰的 Oulu 大学机器视觉小组于 2004 年开始进行几何不变性方面的研究，提出了一种具有完全仿射不变性的特征提取方法，并用于目标识别与配准。Oxford 大学的机器人研究小组开展视觉不变性方面的研究，他们的主要成果是提出了一种仿射协变(Covariant)区域的检测方法，用于提取图像局部区域的仿射不变特征 8。由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在基于特征的匹配中应用最广。目前在特征点提取方面，基于角点、局部不变特征点提取研究得到广泛关注。1. 角点检测方法一直以来角点没有明确的数学定义，人们普遍认为角点是二维图像亮度变化剧烈的点或图像边缘曲线上曲率极大值的点。这些点在保留图像图形重要特征的同时，图像特征点提取及匹配算法研究 第一章 绪论3可以有效地减少信息的数据量，使其信息的含量很高，有效地提高了计算的速度，有利于图像的可靠匹配，使得实时处理成为可能。其在三维场景重建、运动估计、目标跟踪、目标识别、图像配准与匹配等计算机视觉领域起着非常重要的作用。目前角点的检测主要分为两大类：基于图像边缘的角点提取算法和直接基于图像灰度的角点检测。基于边缘提取的角点检测算法的基本思想是：角点是一种边缘上的点，它是一种特殊的边界点，即两条以上边界的交点。这类算法的基础就在于先检测出图像的边缘，然后再在此基础之上检测出边缘突然变换的点，就作为检测角点的结果。主要缺点是对边缘提取算法依赖性大，如果提取的边缘发生错误，或是边缘线发生中断(在实际中经常会遇到这种情况)，则对角点的提取结果将造成较大影响。直接基于图像灰度的角点检测，依据角点是局部内灰度和梯度变换剧烈的极大点，所以这类算法所应用的手段主要是通过计算曲率及梯度来达到检测角点的目的。由于它不需要进行边缘提取工作，所以在实际中得到了广泛的应用。目前国内研究角点提取算法重点主要在已有算法的改进，如杨莉等基于SUSAN 算法提出的 RSUSAN (Redefined SUSAN)角点提取算法 9，使用了更为有效和简便的计算 USAN 区域的方法，提高了计算速度；王建琦等人提出一种改进的角点提取方法 10，该方法是基于 MIC 算法的改进，该算法采用了在方形窗边界上的线性插值，在插值的基础上计算出边缘角，通过它来对角点候选点做进一步的筛选；李华等人提出了一种新的基于形态骨架的快速拐点提取方法 11，该方法基于物体条件骨架原理，采用改进的非对称开运算算子，并利用内外骨架分别实现对物体凸点和凹点的提取，以保证拐点提取的完整性；张坤华等人提出一种利用图像灰度特征和边界轮廓点特征相复合的角点提取方法 12，克服了单一特征提取角点所带来的弊病，提高了角点提取的精度。2. 局部不变特征点提取方法局部不变特征点提取方法主要利用目标局部区域的信息来构造特征量，由于这些一定数目的局部区域可能离散地出现在目标的不同位置，当对每个区域独立地提取特征时，即使目标位于复杂环境中或有部分遮挡，通过局部特征提取仍可得到目标的部分信息，从而实现复杂背景中目标的识别与确认。由于不用对目标进行分割或提取轮廓等预处理，不需要得到目标的全部信息，因此与全局的方法相比，其适用面更广。局部不变特征提取方法的研究已成为了一个非常活跃的研究方向 13，出现了大批研究成果，其中部分成果已达到了实用阶段。局部不变特征提取需要解决两个问题：一是特征区域定位，即在哪里提取特征；二是区域内信息描述，即用什么特征量来描述区域内的信息。下面将分析和比较不同方法如何解决这两个问题。Lowe 利用尺度空间性质，提出了一种尺度不变关键点(Keypoint)检测方法 1415，以同时在尺度域和空间域取得极值的点作为关键点，并以关键点作为特征区域的中图像特征点提取及匹配算法研究 第一章 绪论4心，同时，关键点所在的尺度还用以确定特征区域的大小。这种方法较好地同时解决了特征区域定位和大小选择的问题。在每个特征区域内，Lowe 以梯度方向的直方图为基础构造了一种称为 SIFT（Scale Invariant Feature Transform）的局部不变特征提取性能的衡量标准。SURF 是由 Herbert Bay 等 2006 年提出的另一种有效的特征提取方法 16，与SIFT 一样不仅可以检测出图像的兴趣点即特征，同时提供了一种创建具有不变描述器的方法。这样描述器独立地用于识别所找到的兴趣点，同时能在尺度变化、旋转、光照及视角变化及出现噪声情况下进行很好地匹配。这种不变性对于诸如需要稳定和重复性特点以用来支持目标的识别的移动机器人这样的应用程序是相当重要的。通过研究 SURF 在处理模糊和旋转的图像时表现出很强的优点，而在视角变化和光照变化上略差一些。当相比于 SIFT，SURF 的速度要更快，但是在图像出现视角和光照变化上匹配的效果没有 SIFT 好。近年来还出现了许多局部不变特征提取方法，如基于视觉显著性的局部不变特征提取 17和基于微分几何测地线概念的方法 18，后者甚至对非仿射变换造成的几何形变具有很好的不变性。1.2.2 特征点匹配研究现状特征点匹配就是将不同图像上由同一场景点投影而成的特征点对找出来。由匹配线索不同，现有的匹配算法基本可以分为两大类：1) 基于窗口的匹配(Area-Based Matching,ABM)，窗口是由待匹配点附近的像素灰度值组成的二维矩阵，其中最常用的是用交叉相关性来匹配，这是目前大多数匹配算法的基础。Rosenholm不使用固定大小的窗口，而是用连接窗(connected window)在全局范围内进行匹配)，该方法对于处理重复纹理具有较好的效果。2) 基于特征的匹配(Feature-Based Matching，FBM)，在匹配前先要抽取边或区域等特征。这些特征是图像内容更抽象的描述，在不同的光照下具有更多的不变性。但是特征匹配往往有很高的计算代价。除此之外，各种匹配方法所采用的优化算法也不尽相同，有的使用全局优化算法，如动态规划法、穷举法、凸规划法和松弛法等；还有的使用一些非全局最优算法，如贪婪算法，模拟退火算法和随机搜索算法等。以上的大多数方法都隐含地引入了一些约束，如动态规划法就需要顺序不变约束。当这些约束不满足时，相应的方法就无法使用。Maciel等使用线性规划的方法来解决匹配中产生的歧义问题，这种方法可以得到某种意义上的全局最优解，并且由于线性规划法已经很成熟。因此可以保证算法有较高的效率，但是线性规划法需要消耗大量的内存并且要预先估计正确的匹配数。如何建立特征点之间的对应关系是基于特征点匹配方法的核心研究课题，虽然特征点匹配技术起步较晚，但是应用的迫切和前景的广泛使它引起了广大学者们的图像特征点提取及匹配算法研究 第一章 绪论5极大关注，在近十几年里得到了长足的发展，并出现大量的匹配方法。不同的图像变换模型又具有不同的匹配方法，如在一些应用领域中，根据已有的先验知识可以直接计算出缩放比例，如在地球资源卫星图像的配准中，可以直接利用给定图像的比例信息，而只需要考虑在一些区域被遮挡的情况下存在的平移与旋转。这时相当于提供了一个不变量，即一幅图像中任意两个特征点的距离与另一幅图像对应的特征点之间的距离相等。这样使匹配算法能够简化为只考虑有平移、旋转的情况下求解点集之间的对应关系，但在很多实际应用中，由于存在图像噪声及视场变