用于图像匹配的改进Harris特征点检测算法

扈立超，史再峰，庞 科，刘江明，曹清洁，2

（1.天津大学电子信息工程学院，天津 300072；2.天津师范大学数学科学学院，天津 300387）

用于图像匹配的改进Harris特征点检测算法

扈立超1，史再峰1，庞 科1，刘江明1，曹清洁1，2

（1.天津大学电子信息工程学院，天津 300072；2.天津师范大学数学科学学院，天津 300387）

原始Harris特征点检测算法采用高斯滤波进行平滑处理，增强了其鲁棒性，但是也提高了该算法的复杂度，导致其不能应用到许多图像匹配系统中，还存在对T型和斜T型特征点定位不准确的问题。为此，提出一种新的特征点检测算法。使用加速分割测试特征的特征点检测原理排除大量的非特征点，利用邻域像素比较法消除部分强干扰点，采用改进的高效非极大值抑制算法获得结果特征点。实验结果表明，该算法具有较好的匹配精度和较快的检测速度，检测时间仅为原始Harris算法的13.9%，适用于实时图像匹配系统。

机器视觉；图像匹配；特征点检测；Harris算法；非极大值抑制

DO I：10.3969/j.issn.1000-3428.2015.10.040

1 概述

图像匹配是机器视觉与模式识别领域中的一个重要问题，其目的是为2幅不同图像中的相似目标物建立对应关系，它是众多视觉任务中的关键技术，包括图像识别、图像配准、三维重建和目标跟踪等［1］。随着一些较好特征提取算子的出现，基于特征点检测的配准算法应用更加广泛，对于位置变化、灰度变化以及图像变形等具有较好的鲁棒性，且计算量小、速度较快，是目前研究最多和应用最广的匹配算法［2］。 其中，基于灰度的特征点检测算法［3-5］直接对图像中像素点的灰度值进行处理，避免了基于轮廓的特征点检测算法［6-8］在提取轮廓时存在的误差，因此，在实际研究中得到了更多关注。

基于灰度的特征点检测算法通过使用图像的一阶或二阶导数来进行特征点提取。文献［3］计算各像素点在4个主要方向上的相邻像素灰度差的平方和，选取最小值作为特征点响应函数，在一定范围内具有最大特征点响应函数的像素点为特征点。在文献［3］特征点检测算法的基础上，文献［4］提出了著名的

Harris特征点检测算法，其广泛应用于许多计算机视觉任务。它通过引入高斯滤波函数来提高算法的稳定性和鲁棒性，但也正因如此该算法的复杂度被提高。由于在计算特征点响应函数时，该算法使用了差分方向导数计算方式，其与理想方向导数间存在误差从而在非极大值抑制阶段排除了真正特征点。

针对上述Harris特征点检测算法面临的2个主要问题，本文使用加速分割测试特征（Features from Accelerated Segment Test，FAST）的特征点检测［5］原理排除大量的非特征点，采用邻域像素比较法［9］排除强干扰点，使用改进的高效非极大值抑制算法进一步降低算法复杂度。

2 Harris特征点检测算法

2.1 Harris特征点检测算法原理

Harris特征点检测算法是以文献［3］算法为基础提出的，是一种基于信号的点特征提取算子。其原理是将待处理的图像窗口向任意方向做微小的移动，则灰度变化量可定义为：

其中，E（u，ν）为图像窗口内的灰度变化量；I（χ，y）为图像灰度函数，［I（χ+u，y+ν）-I（χ，y）］为图像灰度的梯度值；w（χ，y）为窗口函数，通常为高斯函数。

将式（1）在点（χ，y）处进行泰勒级数展开，并略去无穷小项为：

其中，矩阵M是2×2的实对称矩阵，通常称为自相关矩阵，可表示为：

其中，Iχ和Iy分别表示图像在水平和垂直方向上的梯度。某一点的图像灰度自相关函数的极值曲率可由自相关矩阵的特征值近似表示，如果自相关矩阵的2个特征值都很大，说明该点的图像灰度自相关函数的2个正交方向上的极值曲率比较大，此处为一个特征点。

在实际应用算法中，自相关矩阵的特征值分解可由计算如下的特征点响应函数替代：

其中，det（M）=A×B-C2为矩阵M的行列式；trace（M）=A+B为矩阵M的迹；k是一个经验值，取值范围在0.04～0.06之间。当R为局部最大值并且大于一个给定阈值时的位置就是特征点。

2.2 Harris特征点检测算法分析

Harris特征点检测是当前比较广泛使用的一种基于图像灰度的特征点提取算法，其主要优点在于：（1）其计算用到的是图像的灰度梯度值，所以，对光照是不敏感的。只是由于阈值的选择会影响特征点检测的数量。（2）其使用的是特征点附近的区域灰度二阶矩矩阵，而二阶矩矩阵可表示成一个椭圆。当椭圆转动时，特征值并不发生变化，所以，其对旋转是不敏感的。（3）其对图像中的每一个像素点都计算特征点响应函数，然后在邻域范围内寻找最优值，所以，其提取的特征点均匀且合理。

但是Harris特征点检测算法也存在着一些缺点，主要表现在：（1）引入高斯滤波函数进行平滑操作，虽然增强了算法的鲁棒性，但是由于高斯卷积计算量大，使得算法的复杂度被提高。并且该算法对整个图像的每个像素点都进行特征点响应函数计算和非极大值抑制操作，使得其检测效率非常低。（2）其特征点定位有偏差，特别是对 T型和斜 T型特征点定位不准确。文献［9］对5种类型的特征点进行了实验，检测结果表明Harris特征点检测算法对T型特征点在水平方向有一个像素的偏差，对斜T型特征点在水平和垂直方向均有一个像素的偏差。

3 改进的Harris特征点检测算法

3.1 检测效率改进

一幅图像中的特征点数量往往占不到全部像素点的1%，如果对全部像素点均进行检测，必然会造成效率的降低。针对该问题，本文首先利用FAST特征点检测算法原理来排除大量的非特征点。FAST算法以一个半径为3的Bresenham圆作为测试模板，圆上一共有16个点，中心点为待测像素点，如图1所示。

图1 FAST算法圆形模板示意图

如果此圆上至少有12个连续点的灰度值大于或者小于中心点的灰度值加上或者减去一个阈值，

那么此中心点被认为是一个特征点。

因为12个连续点必然包括像素点1，5，9和13中的3个，所以本文首先检测像素点1和像素点9。如果它们的灰度值均与中心点的灰度值相似，那么此中心点不是特征点，将其排除，否则继续检测像素点5和13。如果这4个像素点中至少有3个点的灰度值大于或者小于中心点的灰度值加上或者减去一个阈值，那么将此中心点记为候选特征点，供算法后续处理。但是，如果在这4个像素点中仅有2个相邻点的灰度值，远大于或者远小于中心点的灰度值，那么此中心点仍然可能是一个特征点，也将其记为候选特征点。通过此步骤能够排除大量的非特征点，所以，检测效率被剧烈提升。

3.2 匹配精度改进

对于提高算法的匹配精度，本文采用文献［9］算法，并在此基础上做一些改进，以便更适合本文算法。对于目标像素点，考虑其8邻域范围内的像素点，计算该范围内的像素点与目标像素点的灰度差值的绝对值，如果该值小于等于预设的阈值，则认为该像素点与目标像素点相似［9］。最后统计8邻域范围内相似点的个数，并根据相似点个数对目标像素点进行分类。文献［9］的目标像素点是一幅图像中的所有像素点，而本文的目标像素点只针对候选特征点。设8邻域内相似点个数为n，则目标像素点的分类情况如下：

（1）n=8，表示邻域内像素点均与目标像素点相似，所以，该点为一平坦区域内的点，因此，该点要被排除掉。

（2）n=7，可能的特征点为与目标像素点不相似的那个像素点，所以，该点要被排除掉。

（3）2≤n≤6，这种情况无法确定目标像素点性质，将此点进行保留。文献［9］对n=5的情况做了进一步的讨论，其考虑到了目标像素点左右两侧像素点的n值，而本文不再对其进行分析，因为本文为了提升检测效率，只计算候选特征点的相似点个数，所以目标像素点左右两侧像素点的n值可能并没有被计算。

（4）n=1，这种情况下的目标像素点可能为特征点，也可能为离散的噪声点，此时，需要考察24邻域内与目标像素点相似的个数，如果相似点个数仍然较小或者比例不变，那么可以认为该点为噪声点，将其排除。

（5）n=0，表示目标像素点邻域内没有与之相似的像素点，所以，该点为孤立像素点或者噪声点，将其排除。

通过此步骤能够排除强干扰点，从而实现对T型和斜T型特征点的准确定位，并且本文提出的算法仍然具有Harris特征点检测算法对其他类型特征点定位准确的优点。

3.3 改进的高效非极大值抑制

非极大值抑制能够在一定范围内寻找到一个最大值，同时，把其他值排除掉。在特征点检测算法中，如果一个像素点的特征点响应函数为局部最大值并且大于一个给定阈值，那么此点被认为是一个特征点。Harris特征点检测算法计算每一个像素点的特征点响应函数，并以每一个像素点为中心执行非极大值抑制，这必然会造成检测效率的降低。因为一旦一个局部最大值被搜索到，那么在一定范围内必然不会出现另一个最大值，这意味着不需要在这个范围内继续以其他像素点为中心来执行非极大值抑制。

文献［10］提出了高效非极大值抑制算法，从而很好地解决了低效率的问题，如图2所示，非极大值抑制窗口为（2n+1）×（2n+1）。首先，它将图像划分为多个（n+1）×（n+1）的块。其次，在每一个块中寻找最大值，如图2中的黑点表示每个块中的最大值。最后，对于每一个块中的最大值，其完整邻域被测试，如图2中像素点a的虚线窗口。

图2 高效的非极大值抑制算法

虽然高效非极大值抑制算法能很好地解决原始算法的低效率问题，但是要将其运用到特征点检测领域必然会呈现出一个缺陷。因为该算法将图像中的所有区域均进行划分，并在每块区域上执行非极大值抑制，而有些区域为平坦区域，特征点是不可能出现在这些平坦区域中，所以该算法不可避免地提高了复杂度。所以，本文在应用该算法之前做了一些改进，以降低其复杂度。

通过3.1节，已经排除掉大量的非特征点，同时得到候选特征点队列。首先，以一个候选特征点为中心，形成一个（n+1）×（n+1）的区域。其次，在该区域中寻找具有最大响应函数的候选特征点，同时将其他候选特征点从队列中删除。再次，对该候选特征点做完整邻域的测试。最后，按照以上3步遍历所有剩余的候选特征点。据此，高效非极大值抑制算法应用到特征点检测领域所遇到的问题便被有效地解决。

4 实验结果与分析

为了更好地客观评价本文算法，本文引入特征点检测常用的2个关键评价指标：特征点数量一致性（CCN）和精确度（ACU）。文献［11］提出定义如式（5）所示的CCN准则和定义如式（6）所示的ACU准则：

其中，No是原始图像中被检测到的特征点数量；Nt是变换图像中被检测到的特征点数量。特征点检测算法的稳定性越强，其CCN值越高。

其中，No是原始图像中被检测到的特征点数量；Na是被检测到的特征点中所包含的真正特征点的数量；Ng是真正特征点的数量。特征点检测算法的定位准确性越强，其ACU值越高。

为了评估本文算法，进行了大量实验，并与原始Harris特征点检测算法［4］和FAST-9特征点检测算法［5］进行了比较。测试图像及其全部特征点位置如图3所示，图中每一个点表示一个特征点。此测试图像一共有38个特征点。

图3 测试图像及其特征点

实验结果如表1所示。其中，分别包括每一种算法所检测到的真正特征点数量、所漏报的特征点数量、所误报的特征点数量、ACU结果和每一种算法的运行时间。由结果可知，本文算法拥有最好的精确度和最快的检测速度，检测时间仅为原始Harris算法的13.9%，适用于实时图像匹配系统。

表1 3种特征点检测算法的检测结果

为了评估特征点检测算法的重复性，本文对图像施加了缩放变换。算法的重复性越高，在缩放变换下其检测到的特征点数量越不会发生变化，说明该算法的稳定性越好。通过使用双三次插值算法来实现图像的缩放变换，缩放倍数区间为［1.0，2.0］。本文对原始图像在［1.0，2.0］的区间内以0.2的间隔分别施以缩放变换，使用这3种特征点检测算法提取缩放图像中的特征点，根据式（5）分别计算每个缩放图像的CCN值，并对所有的CCN求出平均值。在［1.0，2.0］缩放倍数区间内提取的特征点数量及其平均CCN值如表2所示。从平均CCN的结果可知，本文算法的重复性最高，在图像发生缩放变换下，仍能很好地进行匹配。

表2 3种算法在缩放倍数区间内的实验结果

本文分别使用这3种算法提取2幅待匹配图像的特征点，然后利用归一化互相关算法［12］进行2幅图像特征点的匹配，匹配对数占所提取的特征点比重越大，说明该算法检测出的特征点越准确，匹配精度越好。匹配结果如图4所示，相同的数字表示相匹配的特征点。

图4 特征点匹配结果

实验结果如表3所示。其中，分别包括每一种算法所检测到的图4左图特征点数量、右图特征点数量、2幅图像相匹配的特征点对数量和匹配率。由结果可知，本文算法拥有最好的匹配精度，优于另外2种算法。

表3 3种特征点检测算法的匹配结果

5 结束语

本文提出一种改进的Harris特征点检测算法。通过使用FAST特征点检测原理排除大量的非特征点，对高效非极大值抑制算法进行改进，降低原始算法的复杂度，通过使用邻域像素比较法排除一些强干扰点，实现对 T型和斜 T型特征点的准确定位。实验结果表明，该算法的特征点定位精度和缩放不变性要优于其他算法，并且拥有较快的检测速度和最高的特征点匹配率。今后考虑将Harris特征点检测精度由像素级提高到亚像素级，从而进一步完善算法的检测性能。

［1］ 吴振国，杨红乔.一种具有仿射不变性的图像匹配算法［J］.计算机工程，2013，39（8）：215-218.

［2］ 曾 峦，王元钦，谭久彬.改进的SIFT特征提取和匹配算法［J］.光学 精密工程，2011，19（6）：1391-1397.

［3］ Moravec H P.Towards Automatic Visual Obstacle Avoidance［C］//Proceedings of the 5th International Joint Conference on Artificial Intelligence.Cambridge，USA：M IT Press，1977：584-590.

［4］ Harris C，Stephens M.A Combined Corner and Edge Detector［C］//Proceedings of the 4th Alvey Vision Conference.Manchester，UK：［s.n.］，1988：147-151.

［5］ Rosten E，Porter R，Drummond T.Faster and Better：A Machine Learning Approach to Corner Detection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（1）：105-119.

［6］ Mokhtarian F，Suomela R.Robust Image Corner Detection Through Curvature Scale Space［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20（12）：1376-1381.

［7］ He Xiaochen.Corner Detector Based on Global and Local Curvature Properties［J］.Optical Engineering，2008，47（5）.

［8］ Awrangjeb M，Lu Guojun.Robust Image Corner Detection Based on the Chord-to-point Distance Accumulation Technique［J］.IEEE Transactions on Multimedia，2008，10（6）：1059-1072.

［9］ 王 崴，唐一平.一种改进的Harris特征点提取算法［J］.光学 精密工程，2008，16（10）：1995-2001.

［10］ Neubeck A，Gool L V.Efficient Non-maxim um Suppression［C］//Proceedings of the 18th International Conference on Pattern Recognition.Washington D.C.，USA：IEEE Press，2006：850-855.

［11］ Mokhtarian F，Mohanna F.Performance Evaluation of Corner Detectors Using Consistency and Accuracy Measures［J］.Computer Vision and Image Understanding，2006，102（1）：81-94.

［12］ Tsai Duming，Lin Chienta.Fast Normalized Cross Correlation for Defect Detection［J］.Pattern Recognition Letters，2003，24（15）：2625-2631.

编辑 刘冰

Improved Harris Feature Point Detection Algorithm for Image Matching

HU Lichao1，SHI Zaifeng1，PANG Ke1，LIU Jiangming1，CAO Qingjie1，2
（1.School of Electronic and Information Engineering，Tianjin University，Tianjin 300072，China；2.School of Mathematical Sciences，Tianjin Normal University，Tianjin 300387，China）

By using Gaussian filtering for smooth processing，the original Harris feature point detection algorithm enhances its robustness.But it also increases the complexity of the algorithm which can not be applied to many image matching systems.Its positioning accuracy of T-type and diagonal T-type feature points is low.In order to solve the above problems，a new feature point detection algorithm is proposed.Amounts of non-feature points are excluded by using the principle of Features from Accelerated Segment Test（FAST）feature point detection.Some strong interference points are ruled out by using neighborhood pixels comparison method.The resulting feature points are obtained by using the improved efficient non-maximum suppression algorithm.Experimental results demonstrate that the improved algorithm has better matching accuracy and higher detection speed，its detection time is only approximately 13.9%that of the original Harris algorithm and it is quite suitable for real-time image matching system s.

machine vision；image matching；feature point detection；Harris algorithm；non-maximum suppression

扈立超，史再峰，庞 科，等.用于图像匹配的改进 Harris特征点检测算法［J］.计算机工程，2015，41（10）：216-220.

英文引用格式：Hu Lichao，Shi Zaifeng，Pang Ke，et al.Improved Harris Feature Point Detection Algorithm for Image Matching［J］.Computer Engineering，2015，41（10）：216-220.

1000-3428（2015）10-0216-05

A

TP391

国家“863”计划基金资助项目（2012AA012705）；国家国际科技合作专项基金资助项目（2012DFB10170）。

扈立超（1988-），男，硕士研究生，主研方向：数字图像处理；史再峰，讲师；庞 科，博士研究生；刘江明，硕士研究生；曹清洁，博士研究生。

2014-11-03

2014-11-27E-mail：hulichao@tju.edu.cn