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

本科毕业设计(论文)二O一O年月日目录摘要[28]根本思想是：一个三角形的内角不但对于平移和旋转具有不变性，而且对于三角形的缩放也具有不变性(如图4.1)。三角形(a)旋转得出(b)，但是内角并没有发生改变，而缩放(a)变成(c)，和的大小依旧没有发生变化。(a)(b)(c)图4.1三角形的旋转和缩放不变性假设两点集，，其中，之间的最大匹配点子集，，且，点匹配的任务就是找出这些匹配点集。对点那么可组成对相似的三角形，且以某个点为顶点的三角形有个。基于此原理，将相似两三角形对应点的置信度加一。这样，在严格的情况下，真实匹配的点对之间的置信度会大于或等于，但由于出格点的存在，进行同向相似三角形检实际算法过程中将置信度大于某一阈值的两点作为最终匹配点。算法过程具体描述如下：1．三角形的建立及表示定义4.1：从待匹配的两幅图像中提取的角点集和中任意三点，依次连接这三点组成的三角形就称之为三角形。定义4.2：从两幅图像中任意选择两个三角形，它们组成一个三角形对。定义4.3：如果一个三角形对中的两个三角形的三个顶点对应匹配，那么称它们为一个匹配三角形对。三角形具有旋转、平移、伸缩变化不变性的特点，每一个三角形包含两个独立的不变的形状参数，参数的表示方法有很多种，常选择使用三角形边的比率来表示：参数1是三角形中间长度的边与最长边的比，参数2是三角形最短边长与最长边的比，a，b与c是三角形的三条边，且。通过定义可知,并且，同时。图4.2三角空间的三角形特征由空间中的三个点构成的三角形就可以转换成空间中用一个点来表示。由上面的定义可知，三角形映射到三角空间中是被限制在一个三角形区域中(如图4.2所示)，但是对于相似三角形，无论它如何平移、旋转或缩放，它总是投影在空间的同一点。两个图像中的三角形在三角空间中的对应点之间的距离在范围内，就认为它们相互匹配，即为一个三角形匹配对。2．三角形匹配穷举方法就是用A组中的每一个三角形去和B组中的每一个三角形进行比拟，而每一次的比拟都涉及到笛卡尔距离的计算。然而对三角空间中的B组坐标分别按照进行排序，再使用折半查找法能够迅速地在组B中找到开始点，只有那些落在范围之内的点需要进行比拟，能够防止大量的比拟。确定匹配点。指派两组点模式之间候选点的匹配是基于这样的思想：当存在很多个点时，将会在包含对应点的三角形之间出现过剩的匹配。换句话说，A组的一个点作为很多匹配的三角形的一局部，而这些三角形在B组有着对应点。为了计算A组的点i和B组的点j具有共同的三角形的数目，定义的权值二维表，并初始化为零。每一组匹配上的三角形，对于构成三角形的每个点，其在权值矩阵中的元素的权值被加1。通过加权后，权值矩阵中数值大的元素对应着匹配点。权值矩阵由两组点对组成。很明显点对的权值越高，点对为真正的配对的可能性越大。一种方法是给权值应用一个阈值，通过控制这个阈值的大小来控制随机误匹配点的数目及真正点匹配对的数目。估计这些数目是很难的，需要依靠许多参数来完成，比方参与匹配的点的个数，数组中数据排序程度等。3.减少误匹配点扩展三角空间可以减少误匹配。可能的扩展是包括一个与三角形尺寸有关的标准化参数，如三角形面积、周长。标准化可能是一组中所有三角形关于这个属性的平均值。标准化使得参数比例稳定，相似三角形具有相似的参数值。这个思想在于运用这些参数可以限制一些匹配，比方比拟大的三角形仅仅和比拟大的三角形匹配。这个方法很具有直觉性，是人类视觉识别相似三角形的局部技能。4.匹配流程1)由两幅图像所有特征点任意组合成的三角形集合，分别记为A、B；2)构建权值矩阵M。假设A、B分别有m和n个点，表示匹配相似三角形对中出现的次数，通过设定阈值确定三角形匹配对；3)减少误匹配。4)经过上面层层筛选，进而得到最终的匹配点。三角形相似方法局限性假设两特征点集的数量都为，每个点集将构成个三角形，方法需要对每对三角形进行相似性判定，时间复杂度。而且判定方法还需牵涉到较为复杂的除法和比拟操作。且未利用其他信息对一些伪匹配三角形进行剔除，造成相似三角形对数过多，容易造成误匹配。再者当模板点集中的一个点与目标点集中多个点匹配这种情况出现时，特征点的对应关系就找不出来了。4.2改良的相似三角形匹配方法实现根据以上对于传统三角形特征点匹配算法的原理及局限性分析，针对传统三角形匹配算法时间复杂度高，使用单模板匹配的局限性，通过引入基线及基线三角形组的概念，由复数相乘的几何意义，将图像特征点转移到复数向量空间中求解，不仅使算法的效率得到提高，同时也增强了算法的可靠性。下面进行改良相似三角形匹配方法的具体研究与实现。定义4.4：选取图像点集中任意两个特征点、，那么定义向量为图像中的一条基线。定义4.5：在选取图像中的一条基线后，以与以点集中其余特征点为顶点组成对应于的三角形组，那么称该三角形组为基线的三角形组。算法步骤：首先提取图像特征点，在图像中选取特征值较高且分布均匀的特征点构成特征点集，并根据图像特征点间的欧氏距离及描述符信息条件选择满足要求的基线，构造基线三角形组形成相应基线的三角形集合；然后从模幅员像的基线三角形集合中选取三角形子模版，对实物图像中的特征点进行相似三角形检索，当找到基线所对应三角形的顶点几何位置时，在判断它是否为特征点根底上，进一步结合该特征点位置的描述符信息剔除伪匹配三角形，在实物图像中准确定位出模幅员像。算法流程图如图4.3所示。图4.3匹配算法流程三角形选取方案研究1.改良选取三角形思路根据传统的基于相似三角形匹配方法，模板图像中个特征点，任意可组成个三角形，然后逐个使用每个三角形在实物图像中寻找相似三角形，是一种被动检索方式，显然这种方法基数非常大，所需要比拟的三角形个数很多，时间复杂度也就相应的增加。本章改良传统三角形的的被动搜索为主动搜索，即在实物图中找到对应于模板图像中的基线后运用复数空间理论，构造条基线，在实物图中主动找到以该基线为准的三角形组，然后判断该三角形组与模板图像的三角形组是否相似，从而很大程度上减少了检索三角形的数量，使算法时间复杂度由降为。2.奇异三角形的去除奇异三角形是指存在夹角近似于或的三角形(如图4.4)。奇异三角形，由于这些三角形面积狭小及边和边之间的关系不明显而不利于模幅员像的定位，所以不被选为子模版三角形。三角空间有一个特点，如果两点靠得很近，也就是说有两个点的坐标距离相当小，将在三角空间的某个角出现大量的点。这些三角形很难进行相似判定。另一方面，给定三角空间一个固定的容错量，那么这些靠的很近的点对，将大量地被筛选为相似匹配(或非相似匹配)。于是，通过限制三角形的形成来减少误匹配的可能及处理三角形的配对。图4.4奇异三角形相似三角形检索方法改良由于同向相似三角形检索首先需要对三角形进行相似性判断，然后进行同向性判断。设实物图像中提取出个特征点，传统的同向相似三角形检索需要对个点组成的个三角形进行同向相似性判断，三角形相似性判断方法目前已经相当成熟。下面给出两三角形同向的判断条件及证明。定理4.1：的顶点坐标为，，，对应顶点坐标分别为，，，那么与顶点同方向排列的充分必要条件是(4.1)证明：将点、、和点、、看作空间直角坐标系下的点，可得，，，，，。那么点、、与点、、同向排列的充要条件是向量和的向量积与向量和的向量积同向。(4.2)(4.3)其中：,,分别是三个坐标轴上的单位向量。易知同向的充要条件就是满足式(4.1)。证毕。如图4.5两三角形相似却不同向，不能由旋转得到。图4.5不同向的两相似三角形很显然传统的同向相似三角形检索时间复杂度为，且过程涉及到大量的除法和比拟运算。本文将采用一种主动的相似三角形检索方法，时间复杂度仅为。且根据复数相乘的几何意义，将图像特征点转移到复数向量空间中求解，大大提高了算法效率。定理4.2给定边与的边对应，那么将存在唯一的点使与同向相似。证明：假设对应边长分别为，，。边的长度为，根据三角形相似原理可知：边的长度与边的长度可由下式求出：(4.4)分别以点、为圆心，、为半径做圆、。由三角形三边之间的关系及式(4.4)可得：(4.5)由式(4.5)知两圆必交于不同的两点，且两点关于边对称。这样就得到两个与相似的三角形，这两个三角形反向相似，其中有且仅有一个三角形与同向相似，且对应的交点即为要求的点，证毕。根据定理4.2，同向相似三角形检索只需对条对应边求出对应点，然后判断点是否为特征点即可。对点是否为特征点的判断，只需在保存实物图像特征点的二维布尔值数组中检查点对应的值是否为真即可，算法复杂度为。然而，用定理4.2中证明的方法去求解点，那么需要求解二元二次方程组以及进行同向性判断，计算过程比拟复杂，下面将采用另一种方法求解点。在复数向量空间中，模板如图4.6(a)，由向量与向量唯一确定。给定向量如图4.6(b)，假设其与向量对应，那么算法只要找出点，使向量与向量所确定的与模板为同向相似三角形即可。根据定理4.2可知，点存在且唯一。根据三角形相似判定定理：两边对应成比例且夹角相等，那么两三角形相似。假设中向量到向量的角度为，与的比值为，可知只需中向量到向量的角度为，与的比值为，那么与同向相似。根据复数与向量一一对应关系及复数相乘的几何意义，向量对应的复数可由向量对应的复数乘以复数计算出来，由此点坐标被确定。称复数为旋转因子，可由向量对应的复数与向量对应的复数相除得到。图4.6同向相似三角形多模板改良方法分析相似三角形的特征点匹配方法利用了三角形的平移、旋转、缩放不变性，传统的判定方法目前已经比拟成熟，所以在对于旋转和缩放这类图像匹配的应用方面，具有较为突出的优越性。方法通过选取模板图像中三角形子模板对实物图像特征点进行同向相似三角形检索，来实现模板图像的粗匹配，可以在很大程度上减少传统图像匹配方法的搜索空间。但当模板三角形特征点中含有出格点时，那么检索出的匹配三角形集合中就不会含有同名匹配三角形，从而得不到准确的匹配位置。所以用单个三角形模板进行匹配是不可靠的，在本文提出的改良方法中将考虑用多个三角形模板进行匹配，具体是通过使用基线的三角形组形成多模板，使改良方法可靠性得到改善，并且利用特征点的描述符信息，更合理的选择基线，并可以剔除局部伪匹配三角形。在复数空间下得到对应特征点组成向量的三角形组的根底上，通过判断实物图中对应于模幅员像中的基线的三角形组的顶点为特征点的数量是否到达一定阈值，假设满足阈值要求，那么可以认为在实物图中找到一个模幅员像，同理遍历模幅员像中的所有基线，进行相似三角形检索，找到实物图中所有的模幅员像。在复数向量空间中，从特征点集中结合特征点的描述符信息，根据与模板图像对应特征向量的属性相似度，从实物图中选择基线，以其余所有的特征点与构成三角形组，具体方法以构造为例说明如下(如图4.7)：由模幅员对应的复数与对应的复数相除得到旋转因子，运用旋转因子找出点，使与所确定的三角形与模板为同向相似三角形。在得到以为基线构造的顶点的几何坐标位置后，判断点是否为实物图像中特征点，假设为特征点，进一步结合点特征向量信息，判断该特征点与模板图像中对应位置点的描述符信息是否相似，假设这两点特征向量相似度高，那么认为找到一个匹配三角形，同理构造以为基线组成的所有三角形，假设三角形组顶点满足要求的点到达一定阈值，那么认为在实物图像的该位置找到模板图像，提高了检索方法针对性和有效性。AA(a)模板图像三角形(b)实物图像中三角形图4.7相似三角形本章改良算法是在现有相似三角形匹配算法的根底上，通过选取模板图像中特征点组成基线的相应三角形组后，对实物图像相应特征点组成的基线进行对应的相似三角形检索来实现模板图像的定位，从而很大程度上减少了传统模板匹配方法的搜索空间，提高了搜索的效率。并且通过构造基线三角形组的思想，使匹配模板由单个模板变为多个模板，提高了搜索策略的可靠性。同时结合了H/S算法提取出图像中的特征点具有的描述符信息，更合理的选择实物图中的向量作为基线，减少搜索三角形的数量，提高了算法的效率，在复数空间下得到对应基线的三角形的几何位置时，不仅判断该点的位置是否为特征点，并利用该特征点与对应模板图中的相似三角形的顶点的特征向量的相似性，剔除局部伪匹配三角形，使算法的准确性得到进一步提高。改良的相似三角形匹配方法步骤如下：1)模板图像特征点构造点集，以点集组成个不同的向量作为基线，选择未处理的基线，将模板三角形转到复数向量空间中，通过向量和向量，计算出旋转因子；2)实物图像特征点构造点集，以点集组成个不同的向量，结合H/S算法提取得到特征点的描述符信息，选取与模板图像基线描述符信息相似的向量作为基线，如果个向量都处理完，那么转步骤5。否那么从中选取一个未处理的向量，与模板中向量对应，根据旋转因子，计算出向量，确定点的坐标；3)判断实物图像中周边很小的范围内是否有一个特征点。如果是，那么进一步判断该位置特征点的描述符信息与模板图中对应相似三角形顶点的描述符信息相似度，假设相似度满足要求那么输出为模板的一同向相似三角形，并设置特征点数量记录匹配到的同向相似三角形的数目；4)判断与模板图中对应基线的三角形组的顶点数量关系，假设值到达一定的阈值，那么输出在模板图像中匹配到一个模板图像，并用矩形框将其标识出；转步骤2，继续判断实物图中特征点集合中的其它基线；5)算法结束。4.3实验结果与分析实验实现改良的相似三角形特征点匹配算法，验证其在图像存在旋转、缩放、噪声以及复杂背景下物体识别的准确性及算法效率。实验中提取出角点用十字划线标识，并用矩形框标识出实物图像中识别出的模板图。实验使用VC++6.0平台，首先利用H/S特征点提取算法提取出图像中特征点，得到待匹配的两幅图像对应特征点集。1.模板图像旋转、缩放时匹配图4.8为实物图中存在模板图旋转、缩放时匹配结果，4.8(a)为模板图，4.8(b)为实物图，在(b)中存在与(a)相同、旋转、尺度变化、旋转缩放共存的模板图，用矩形标识出实物图中存在的模板图，实验结果说明该算法对于图像存在旋转、缩放情况下的有效性。(a)模板图(b)实物图图4.8模板图像存在旋转、缩放时匹配结果图2.存在噪声图像匹配图4.9为图像存在噪声情况下的图像匹配结果。4.9(a)为在模板图，4.9(b)为将实物图增加噪声后得到的匹配结果，实验结果说明在实物图受噪声干扰情况下，该算法仍能准确找到发生旋转、缩放情况的模板图像，同时也验证了改良H/S算法提取角点特征点的有效性。(a)模板图(b)添加噪声图图4.9图像存在噪声时匹配结果图3.背景较复杂时图像匹配使用GoogleEarth上截得的摇感图像图像匹配，图4.10中模板图像为实物图像一局部，4.10(a)模板图像经过90度旋转，并存在一定尺度放大，结果显示该方法准确的在实物图中找到相应模板图像，表达该算法在复杂背景下识别目标物体的实用性。(a)模板图(b)实物图图4.10复杂背景下列图像匹配(a)模板图(b)实物图图4.11模板图像旋转、缩放图像匹配4.4本章小结本章在H/S算法提取图像中稳定特征点的根底上，分析传统相似三角形匹配算法局限性，引入基线理论并结合特征点描述符信息，改良了三角形的构造方法。改良算法继承了传统相似三角形匹配算法抗旋转和缩放的优点，将传统被动同向相似三角形检索方法变为在复数空间下选择基线后主动构造相似三角形，同时在选择基线及进行相似三角形的判断时利用了特征点的描述符信息，提高了算法效率，剔除了大局部伪匹配三角形，并利用基线向量得到的对应三角形组获得多个模板在实物图中匹配，提高了三角形匹配算法可靠性和稳定性。第五章工作总结与展望5.1工作总结本文对图像特征点提取与匹配方法进行研究，在分析当前两种常用特征点提取算法根底上，结合Harris算法和SIFT算法的优点，提出一种新的H/S特征点提取算法，该改良算法具有效率高、得到的特征点具有良好的抗尺度和抗噪声性能，并在使用H/S特征点提取算法得到图像中的特征点后，针对传统相似三角形匹配算法局限性进行改良，改良算法提高了算法的效率和可靠性。所有实验基于VC++平台进行。本文所做的工作主要有以下几点：1)实现了Harris特征点提取算法和局部不变量SIFT特征点提取及最近邻匹配方法。首先对Harris算法的原理进行分析并实验实现，结果说明Harris算法检测效率高，针对图像存在旋转情况下有很高的点重复率，是一种比拟有效的点特征提取算法，但它在尺度和噪声发生变化情况下表现的鲁棒性差；针对Harris算法的缺乏，对局部不变特征点提取SIFT算法进行研究，实验说明该算法提取出的特征点对图像的旋转、缩放及光照、噪声变化时表现出较强的鲁棒性，但该算法速度较慢，并且要求图像满足足够多的纹理。2)提出了一种新的H/S图像特征点提取算法。在对Harris特征点提取算法和SIFT特征点提取算法分析的根底上，针对传统的Harris特征点检测算法检测效率高的优点，将SIFT特征点提取算法中的多尺度理论和特征点描述符引入传统的Harris算法，即结合SIFT算法的尺度不变性和抗噪声强的优点，使该改良算法抗尺度变化和抗噪性得到很大改善。3)提出了一种基于相似三角形的图像特征点匹配方法。首先使用本文提出的H/S图像特征点提取算法得到模板图像和实物图像中特征点，然后分析传统相似三角形特征点匹配算法的原理，传统相似三角形利用特征点构成的三角形形成新特征空间，将特征点匹配转化为三角形的匹配。基于三角形几何性质进行匹配的过程中，充分利用三角形的边长信息和内角的不变性，寻找模板图像和实物图像中基线相似三角形组的匹配，改良的相似三角形特征点匹配算法继承了传统相似三角形匹配算法抗旋转和缩放的优点，改变了传统同向相似三角形检索方法，采用了将被动搜索相似三角形变为在复数空间下选择基线后主动构造相似三角形的检索策略，同时在选择基线及进行相似三角形的判断时利用了特征点的描述符信息，剔除了大局部伪匹配三角形，提高了算法的效率。并且利用特征点组成基线向量得到对应三角形组形成多个模板图像进行匹配，提高了改良三角形特征点匹配算法的可靠性和稳定性。5.2工作展望在本文研究工作的根底上，后续将会对下述几个相关问题作进一步的深入研究。1)本文在提出改良传统相似三角形特征点匹配算法时主要依据三角形顶点之间的几何信息及描述符信息，而特征点组成的三角形内部同样也包含着丰富的特征信息(例如三角形内部的平均灰度值等)，因此通过利用特征点组成的三角形内部所具有的其他信息使相似三角形的检索更具有针对性，成为下一步研究方向。2)本文提出的改良传统三角形针对图像发生仿射变化时的适应性效果有待提高，由于在图像发生仿射变化时，三角形的内角不变性及边长比例不变性将不再适用，由于基于描述符的特征点匹配算法在图像发生仿射变化时匹配性能较好，进一步的研究工作可以借鉴基于描述符的特征点匹配算法思想，使本文提出的改良三角形匹配算法对于仿射变化的有效性得到改善。致谢在此首先感谢我的指导老师沙莎教授的亲切关心和悉心指导，老师的鼓励和引导是我不断努力、不断进取的动力。感谢罗三定教授，在实验室的进行毕业设计的这段日子，让我收获很多，成长很多，看到两位老师对待学术的严谨治学的态度，待人处事的方式都深深地影响了我。感谢常卢峰师兄的耐心帮助，每次在进行实验的过程中遇到困难，师兄都认真帮我分析，让我能够找到解决的方法。感谢赵跃师兄在论文写作过程当中对我的细心指导，感谢实验室里的每位师兄师姐的关心与照顾，在实验室的这段时光，是我成长最快也是我最开心的的日子，因为实验室的每一位成员都让我体会到实验室像个温暖的大家庭，每个人都是它的一分子，大家一起工作、一起学习、一起运动，我非常珍惜这段美丽的时光。感谢中南大学的各位任课老师，在这四年里，你们给予我了很多很多，让我不仅收获了专业知识上的提升，更重要的是培养了做人做事的方式与态度。感谢我的大学同学们，四年里我们共同努力、共同进步，感谢你们所给予我的关心与帮助，让我的大学生活如此丰富多姿。感谢我的父母，感谢你们给予我的爱与鼓励，让我能够用积极的角度看问题，即使在困难面前，也会一直努力，不断进步！再次感谢所有帮助过我的人们！谢谢你们！参考文献王红梅，张科，李言俊.图像匹配研究进展[J].计算机工程与应用,2004，19(4)：42~45.RanadeS，Rosenfeld.Apointpatternmatchingbyrelaxation[J].PatternRecognition，1980，12(4)：269~275.Kovács-VajnaZM.Afingerprintverificationsystembasedontriangularmatchinganddynamictimewarping[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2000，22(11)：1266~1276.DavidGLowe.Distinctiveimagefeaturesfromscale-invariantkeypoints.InternationalJournalofComputerVision，2004，60(2)：91~110.MatthewBrownandDavidGLowe.Automaticpanoramicimagestitchingusinginvariantfeatures[J].InternationalJournalofComputerVision，2007，74(1)：59~73.IrynaGordonandDavidGLowe.Scenemodelling，recognitionandtrackingwithinvariantimagefeatures[C].InternationalSymposiumonMixedandAugmentedReality(ISMAR)，2004.110~119.StephenSe，DavidGLoweandJamesJLittle.Vision-basedgloballocalizationandmappingformobilerobots[J].IEEETransactionsonRobotics，2005，21(3)：364~375.章权兵，罗斌，韦穗等.基于仿射变换模型的图象特征点集配准方法研究[J].中国图象图形学报，2003，8(10)：417~422.杨莉，张弘，李玉山.一种自适应RSUSAN角点提取算法[J].计算机科学，2004，31(5)：198~200.王建琦，邓雁萍，李介谷.一种改良的角点提取方法[J].上海交通大学学报，2000，34(7)：913~916.李华，刘文予，朱耀庭等.基于形态学的快速拐点提取统一模型[J].中国图象图形学报，2002，7(6)：543~547.张坤华，王敬儒，张启衡.多特征复合的角点提取方法[J].中国图象图形学报，2002，7(4)：319~324.DorkoG.，SchmidC.SelectionofScaleInvariantNeighborhoodsforObjectClassRecognition[C].In:ProceedingsInternationalConferenceonComputerVision，2003.634~640.DavidGLowe.Objectrecognitionfromlocalscale-Invariantfeatures[C].In:ProceedingoftheInternationalConferenceonComputerVision(ICCV’1999),1999.20~27.DavidGLowe.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision，2004，60(2)：91~110.HerbertBay，TinneTuytelaars，LucVanGool.SURF：Speededuprobustfeatures[C].In:ProceedingsoftheninthEuropeanConferenceonComputerVision，2006.