基于图像尺度变化的一种特征点匹配算法

曾召华，王奕婷，赵 谦，赵 肃，冯 瑞，毛昕蓉

（1.西安科技大学通信学院，陕西西安 710054;2.西安市政设施管理局，陕西西安 710003;3.中国水电顾问集团西北勘测设计研究院，陕西西安 710065）

基于图像尺度变化的一种特征点匹配算法

曾召华1，王奕婷1，赵 谦1，赵 肃2，冯 瑞3，毛昕蓉1

（1.西安科技大学通信学院，陕西西安 710054;2.西安市政设施管理局，陕西西安 710003;3.中国水电顾问集团西北勘测设计研究院，陕西西安 710065）

通过对灰度相关法特征点匹配算法的理论研究和实验分析，提出了一种能够克服图像尺度变化的特征点匹配算法。该算法主要根据图像特征点间欧氏距离的关系，结合传统的特征点灰度相关法和特征点的梯度相关法进行精确匹配。实验证明，该算法容易理解，易于实现，匹配结果较精确，误匹配点较少。

欧氏距离;相关法;特征点梯度;尺度变化

1 特征点匹配

特征点匹配［1］是计算机视觉中的关键技术，在运动估计、图像识别等领域有着重要的应用。特征点是图像局部灰度值发生剧变的点，包含丰富的图像信息，特征点匹配就是对图像上提取的特征点在另一图像上找到该特征点的精确位置。基于上述因素，本文提出了在Harris特征点提取［2］的结果上再进行匹配算法验证的思路。而传统的基于图像灰度的相关匹配算法［3－5］主要是逐像素地把一个以一定大小的实时图像窗口的灰度矩阵与参考图像对应位置的窗口灰度阵列按某种相似性度量方法进行搜索比较，寻找出相关性最大的点。但经典相关匹配算法的运算量大，对尺度变化后的图像进行特征点匹配精确度较差，在一定程度上影响了它的实用性。因此探索易理解、易实现的能够克服尺度变化的图像特征点匹配算法是必要的。本文提出的匹配算法，主要利用两幅图像特征点间欧氏距离［6］的关系来确定匹配点集，极大地减少了灰度相关计算的次数，也排除了一部分的误匹配点，并使用特征点的梯度相关法进行精确匹配，结果达到了较好的精确效果。

2 基于灰度的相关匹配算法［7－8］

在检测出特征点之后，利用角点矩形领域窗口内像素的灰度信息，通过互相关函数来判断是否匹配。两幅图像不同特征点的相似程度采用互相关函数来评价，互相关关系定义为

式中:是图像Ik上点（u，v）的邻域灰度平均值;σ（Ik）是图像Ik中（2n+1）×（2m+1）邻域内点的标准偏差。R值越大，说明两个特征点越相似。

对于图像I1上的特征点m1和图像I2上的特征点m2，图像坐标分别为（u1，v1）和（u2，v2），给定以m1为中心的相关性窗口（2n+1）×（2m+1），在I2相应于m1的位置选定（2du+1）×（2dv+1）的搜索窗口，通过上述的互相关公式计算所有在搜索窗口内的特征点m2与m1的相关系数，最后为计算出来的相关系数设定阈值k来判断，在计算结果大于设定的阈值时，认为两点是相互匹配的点。

虽然，这种相关法匹配容易理解并实现，但是，它在理论上假定了两幅图像没有光照的变化，同时没有太大的平移和旋转，无法精确做到发生尺度变化后的图像匹配。这样必然限定了该算法的应用范围，同时固定的阈值导致了整个系统的误判性增高，大的阈值使得很多匹配点被漏检，小的阈值导致更多的一对多的误匹配点出现。

3 相关算法理论

3.1 欧氏距离

在二维图像当中的欧氏距离主要是指两点之间的距离，本文采用欧氏距离主要是来计算一幅图像中两个特征点的距离，计算公式为

式中:（x1，y1）和（x2，y2）是一幅图像特征点集中的点;d是在该图像上的两点之间的欧氏距离。考虑到图像特征点之间最为直接的关系就是距离的关系，因此，无论需要匹配的两幅图像有无尺度变化，它们在特征点之间距离关系上是不会变的。本文采用欧氏距离来约束特征点集的匹配，主要思想是在第一幅图像上如果离特征点A最近的距离就是特征点B，那么在对应需要匹配的另一幅图像上肯定有与A匹配的点A1，如果特征点A与特征点A1是正确的匹配点，那么在A1对应的图像上必然能找到距离A1最近的点，该点有可能就是B所匹配的点。

3.2 梯度算法

图像的梯度在图像的边缘检测，图像滤波等方面的应用已十分成熟，本文主要是把梯度作为图像特征点匹配的一个新的衡量标准，主要考虑如果两幅图像上的某个点是匹配的，那么它们各自的梯度值应该是相关的。

在计算图像梯度时，主要是把图像看成二维离散函数，图像的梯度其实就是二维离散函数的求导，即

式中:G（i，j）就是梯度值;dx和dy分别是二维图像的两个方向的导数值;I是图像像素的值;（i，j）为像素的坐标。不过，图像梯度一般也可以用中值差分来计算，即

本文主要利用匹配特征点的梯度相关性来实现特征点的匹配。首先，分别计算两幅图像特征点的梯度，然后对需要匹配的特征点集进行梯度相关性的计算，梯度相关性计算主要利用相关法的计算公式，只是把灰度值的相关性比对变成梯度值的相关性比对，见式（8）。最后，计算出相关系数R，R越大，则相关性越大。

其中，各部分的计算方法同灰度相关法计算方法类似，在这里不再赘述。

3.3 本文提出的改进的特征点匹配算法

1）对于获得的两幅图像的特征点集，首先需要对每组点集进行去除相同坐标点的初始化处理。然后，选择初始的第一组精准的匹配点，该初始的匹配点组可以在基于一幅图像的一个特征点的基础上，通过手动地自助选择另一幅图像上对应点，主要操作是通过主动观察的方法，选定相对应需要匹配的特征点在这幅图像上大概的匹配位置，获得一些对应的匹配点集。

2）开始对步骤1）产生的一对多的点集进行细化，首先用灰度相关法计算每两个点之间的灰度相关系数，该相关系数小于阈值k时，认为原计算的那个点是误匹配点，从而去除部分误匹配点，然后对剩余点用梯度相关法来精确匹配点，主要是通过计算两点之间的梯度相关系数，如果该系数大于阈值l，则认定该点为对应的匹配点。这样，最终获得初始的、精确的、一对一的匹配点。

3）在获得初始的一组精确的匹配点组后，在第一幅图像上用欧氏距离来计算离第一个匹配成功的特征点最近的点，该点被确定为需要匹配的第二个点。针对这个需要匹配的点，在第二幅图像上同样寻找离第一个匹配成功的特征点最近的点，因为需要考虑图像发生尺度变化后可能引起的图像畸变，因此，在这幅图像上把该最近的距离的n倍作为阈值g，计算第一个点到其他点的欧氏距离，把在这个阈值g范围内的点认为是第一幅图像上第二个点可能匹配的点。然后按照步骤2）一对多地匹配点的方法来精确匹配点。

4）剩余的两幅图像上的特征点集，按照步骤3）的方法处理，直到特征点全部匹配完成。实现的算法流程图如图1所示。

图1 改进的匹配算法的基本流程图

4 实验结果及分析

本文采用了MATLAB2011版本工具对新算法和经典的灰度相关匹配算法进行仿真实验。两幅图中需要对300个特征点对进行匹配，但为了在图像中能清楚看到匹配结果，避免过多的线被遮挡，所以在图中选用部分点来显示。图2与图3是在旋转尺度变化下，按照传统的灰度相关法所进行的特征点匹配结果图和改进算法所进行的特征点匹配结果图。图4与图5是在旋转和缩放同时变化下传统的灰度相关法所进行的特征点匹配结果图和改进算法所进行的特征点匹配结果图。表1为两种算法的比较。

图2 传统的灰度相关法匹配算法的结果（旋转）

图3 改进的匹配算法的结果图（旋转）

图4 传统的灰度相关法匹配算法的结果（旋转+缩放）

图5 改进的匹配算法的结果图（旋转+缩放）

表1 两种算法在时间和匹配结果上的对比

结合图2～图5和表1明显可看出，灰度相关法在对尺度变化的图像中匹配特征点应用上基本失效，同时，从本文改进算法的实验结果可知，仍存在极少数的误匹配点，但是与传统算法的匹配结果相比，获得了比较理想的结果，不过也同样增大了运算的时间复杂度。

5 结语

本文在传统的灰度相关法匹配特征点的思想上，提出了可以克服图像尺度变化的特征点匹配的算法，该算法在实现和理解上都比较简单，结果也比较理想。但同时为获得更简单、实用以及具有更好鲁棒性的特征点匹配算法，本文算法还需进行深入研究。

:

［1］陈君，戚飞虎.一种新的基于特征点的立体匹配算法［J］.中国图象图形学报，2005，10（11）:1411－1414.

［2］涂春萍，柴亚辉，李广丽，等.一种基于Harris角点特征精确匹配的图像拼接方［J］.实验室研究与探索，2011，30（10）:41－43.

［3］陈淑荞.数字图像特征点提取及匹配的研究［D］.西安:西安科技大学，2009.

［4］张汗灵，郝重阳.基于特征的自动图像配准算法［J］.电视技术，2003，27（9）:40－43.

［5］薛菲，张荣国，张建国，等.基于NCC与SSDA的快速特征点匹配融合算法［J］.计算机与数字工程，2010，38（10）:19－21.

［6］魏志强，黄磊，纪筱鹏.基于点特征的序列图像匹配方法研究［J］.中国图象图形学报，2009，14（3）:525－530.

［7］尹丹，满家居，王梓豪.一种改进的点特征图像匹配算法［J］.计算机与现代化，2008（3）:71－76.

［8］宋晓闯.基于灰度和几何特征的图像匹配算法研究［D］.天津:河北工业大学，2008.

赵 谦（1977— ），副教授，主要从事智能化图像处理及虚拟化现实应用相关研究。

Feature Points Matching Algorithm Based on Image Scale Variations

ZENG Zhaohua1，WANG Yiting1，ZHAO Qian1，ZHAO Su2，FENG Rui3，MAO Xinrong1

（1.School of Communication and Information Engineering，Xi’an University of Science and Technology，Xi’an 710054，China;2.Xi’an Municipal Facilities Administration Bureau，Xi’an 710003，China;3.HYDRO China Xibei Engineering Corporation，Xi’an 710065，China）

A feature point matching algorithm which can overcome the image scale change is proposed by theoretical research and experimental analysis of feature points matching algorithm of gray correlation method.It is mainly based on the relationship of Euclidean distance of image feature points combined with the traditional gray correlation method of feature points and the gradient correlation method of feature points to precise matching.Experiments prove that it is easy to understand，easy to implement，have more accurate matching results and less false matching points.

euclidean distance;correlation method;gradient feature points;scale change

TN911.73;TP751

A

【本文献信息】曾召华，王奕婷，赵谦，等.基于图像尺度变化的一种特征点匹配算法［J］.电视技术，2014，38（3）.

陕西省科技研究发展计划工业攻关项目（2013K07－35）;西安市科技计划项目（CXY1343（4）;CX1258⑤;CX1258⑥）;陕西省教育厅科研计划项目（12JK0508;12JK0535）;西安市碑林区应用技术研发项目（GX1209;GX1311;GX1310）

曾召华（1972— ），副教授，主要从事3G移动通信关键技术研究;

王奕婷（1987— ），女，硕士生，主要研究方向为图像的三维重建;

责任编辑:时 雯

2013－03－19