一种快速自适应的Harris角点检测方法研究

王慧勇

(1.上海交通大学电子信息与电气工程学院，上海 200240;2.上海电视广播集团，上海 200070)

角点是一种重要的图像特征点，其在各个方向梯度变化较大，或在边缘曲线上具有曲率极大值，包含了重要的图像特征信息。所以在物体识别、图像配准、全景拼接等方面具有十分重要的意义［1-3］。准确并快速地提取到角点，能有效地降低信息处理量，大幅提高处理效率。

目前角点检测方法通常基于图像灰度信息，这种方法主要通过测算点的曲率及梯度来检测角点。此类方法应用最广泛的是Harris算法［4］，通过计算像素点所在位置的梯度来检测角点。实验结果表明，Harris角点检测法具有良好的检测效果，但该算法对图像中的每个点都计算其响应值，然后在邻域中选择最优点，计算量大，难以满足实时性要求。而Edward Rosten and Tom Drummond提出的FAST角点检测法实时性好，但对边缘易产生伪响应。同时传统的检测算法处理不同图片，需要人为给出一个经验阈值才能得到较理想的角点。

本文结合Harris算法和FAST算法的优势，提出了一种快速自适应Harris角点检测算法。该方法能有效地自适应提取角点，并满足实时性要求。

1 Harris算法原理

Harris角点检测算法［5-8］是C.Harris和MJ.Stephens提出的，是Moravec算法的改进。Moravec算法将像素点周边的一个邻域作为一个图像块，并检测这个图像块经过少量偏移和原图像块的相关性。如图1所示，假设像素点(x，y)的灰度值为f(x，y)，则图像中每个像素点 (x，y)移动(a，b)后，灰度变化强度表示为

式中:(a，b)可以取(0，1)，(-1，1)，(-1，0)，(-1，-1)，(0，-1)，(1，-1)，(1，0)，(1，1)这 8 个基本方向。于是可以得到8个灰度变化强度值。将8个值中最小的值作为该像素点的角点像素变化值。求出每一个像素点的角点像素变化值，在局部图像块中，该值最大的点为角点。

可以发现，Moravec角点检测算法有几个很明显的缺陷:

图1 中心点沿(1，1)方向移动一格

1)由于窗口是方形，并且是二元的，因此响应函数会有噪声;

2)自相关强度值的计算，只有离散的8个45°方向。

Harris角点检测算法针对些缺陷做出以下改进:

1)用像素的变化梯度代替像素值相减，并引入高斯窗函数(见图2)代替二值窗口函数，对离中心点越近的像素赋于越大的权重，以减少噪声影响。

图2 高斯窗函数

2)Moravec算子只考虑了每隔45°方向的共计8个固定的方向。Harris算子用Taylor展开去近似任意方向，可以计算任意方向上的像素值变化。于是对于局部微小的移动量［u，v］，可以近似得到下面的表达

写成矩阵形式

式中:Ix为x方向的差分;Iy为y方向的差分;w(x，y)为高斯函数。

在完善了Moravec算法的缺陷后，Harris定义角点响应函数R=detM-k(traceM)2来确定像素点是否角点。其中detM= λ1× λ2，traceM= λ1+ λ2，k取(0.04～0.06)。

在图像中，像素点可分为3种类型:平坦区域的像素点，物体边缘的像素点，角点。它们分别有着不同的特性，如图3所示。

结合R=detM-k(traceM)2，可知:1)平坦区域，λ1，λ2都很小;2)边缘的点，λ1，λ2中一个值大，另外一个值小;3)角点:λ1，λ2都比较大(见图4)。

显而易见，Harris算法将遍历图像中的每一个像素点，求其角点响应函数R，R的值越大，对应的2个特征值λ1，λ2都应该很大，最后对整幅图像得到的R做一个非极大抑制。通过设置R的阈值，在w×w范围内寻找极大值点，对提取的角点个数进行限制。则在图像中，同时满足像素点R值大于阈值T和其R值在w×w邻城内是局部极大值这两个条件的点被视为是角点。

2 Harris角点检测算法的局限

Harris角点检测法具有良好的检测效果，但是依然存在以下不足:

1)Harris角点检测算法采用7×7的矩形高斯窗口，且对图像中的每个点都计算其角点响应R值，然后在邻域中选择最优点。一张w×h图像，共需进行w×h次角点响应R值计算和阈值比较。在处理大分辨率图像时，该算法检测时间将会大幅上升，难以满足实时性要求。

2)Harris算法虽然利用非极大值抑制，但角点提取的效果完全依赖于阈值的设定。当阈值过大的时候，两个像素点灰度值相差很大才能成为角点，从而丢失了很多应有的角点;而当阈值过小的时候，灰度值相差较小的两个区域点也可满足阈值条件，就产生了大量的伪角点。在处理不同图像时，需要人为改变阈值，Harris角点检测算法才能得到较理想的角点。

3 基于预筛选及自适应阈值的Harris角点检测算法

针对以上两个问题，本文引入预筛选以及自适应阈值的概念，具体流程图如图5所示。

图5 原Harris算法和改进的Harris算法流程图

3.1 预筛选

在处理图片时先提取一批初选角点，然后再对提取出的初选角点进行Harris角点检测。根据流程图，虽然在计算角点响应值前增加了预筛选的过程，但预筛选后，留下来的待处理像素点数目远远小于图像的所有像素点数目，如此将大幅缩短运算时间，提高角点检测的效率。

改进的算法思想是利用像素点的相似度来提取初选角点。像素点的相似度将指检测窗口中心点灰度值与其周围n邻域内其他像素点灰度值的相似程度，这种相似程度是用两者灰度值之差来描述。如果邻域内点的灰度值与中心点Point(i，j)的灰度值之差的绝对值在一个阈值t范围内，则认为这个点与中心点是相似的。同时，计数器Counter开始计数。在中心点Point(i，j)点的n邻域点全部被遍历一边之后，根据计数器Counter的大小，就可以判断这个中心点是否是初选角点。

改进的算法将使用FAST角点检测算法来考量像素点的相似度。FAST角点检测算法是Edward Rosten和Tom Drummond在2006年提出的一种简单快速的角点探测算法。该算法将角点定义为在角点的周围邻域内有足够多的像素点的灰度值大于该点的灰度值或者小于该点的灰度值。

图6中p点附近半径为3的圆环上有16个点，若其中有连续的12个点的灰度值与p点的灰度值差别超过某一阈值，则可以认为p点为角点。通过预筛选的过程，可以得到初选角点。然后再对这些初选角点进行Harris运算去除伪角点，避免了对整幅图像进行扫描，提高了角点检测的效率。

图6 FAST初选角点判定法

3.2 自适应阈值

对于某一幅特定的图片采用某个阈值会得到比较好的角点检测效果，但将这个特定的阈值应用到其他图片上未必是最佳阈值。这就要求算法本身有能力计算出适合不同图片的阈值。

考虑到阈值是在提取角点时才会使用，本文通过记录角点响应函数值R，得出R的最大值Rmax，不同图像的Rmax也不同。本文通过统计大量图片，其中图片来源为创意素材库网(http://sc.52design.com/)，涵括人物、动物、风景、建筑等，基本能代表现实中的各种图片。通过记录素材库中每张图片Rmax，可以得到Rmax统计分布如图7所示。

图7 Rmax取值分布图

分析得出:Rmax=p×108，其中p＞0，定义阈值T=k×Rmax，选取素材库中图片进行实验。发现当0＜p＜1时，灰度值变化不大，k取经验值0.04;当1＜p＜5时，灰度值变化一般，k取经验值0.02;当p＞5时，灰度值变化较大，k取经验值0.01。如此，基本可以检测出所有角点，并且伪角点比较少。可以得到

式中:p=Rmax/108。

4 实验结果及性能分析

选取若干分辨率不同的图像进行MATLAB仿真实验，如图8所示。

图8 不同分辨率的测试图片

1)将利用FAST算法预筛选与原始Harris算法相比较，结果如表1所示。

表1 采用预筛选算法与原Harris算法效率对比

由表1可以发现:对于所采集的图像，预筛选后，后续需要遍历的像素点只占原算法像素点的10%左右，遍历时间一般都能降低一半。从表中可以看出改进算法在处理大分辨率图像时，优势更加明显。大大缩短了角点检测时间，有利于在实时处理中的应用。

2)为了对比采用自适应阈值算法与原算法的实际效果。选取两张不同的图片，阈值T分别为2×106和5×106，实际角点检测情况如图9和图10所示。

图9 阈值T=2×106处理不同图片效果差异

从图9和图10可以发现:同一个阈值在处理不同图片时，检测效果差异很大。对于示例中左边图像，灰度变化差异小，需要选择相对小的阈值。示例中右边图像则相反。如果实践中发现检测效果不佳，则需要人为设置阈值，效率低下。采用自适应阈值算法后，其阈值T是图像角点响应函数最大值的一个比值。这对于任意图像都设定了阈值比较基准，可以得到较好的检测效果。

图10 阈值T=5×106处理不同图片效果差异

实际效果如图11所示。

图11 采用自适应阈值算法角点检测效果

通过实验可以发现:基于Harris的快速自适应角点检测算法相比基于Harris角点检测算法能得到更多的正确角点，同时抑制了伪角点的数目。避免了阈值选取不当导致的角点检测不准确，且减少了大量校调阈值的工作。

5 结论

文中对Harris角点检测算法进行了分析，并在此基础上改进了算法。通过使用FAST算法对图像进行预筛选，提高算法的运行效率，并采用了自适应阈值使算法能根据图像具体情况自动给出合理的阈值。对比改进的算法与原始算法，新算法避免了阈值的选择，有效地克服了阈值选择不当造成的角点冗余或丢失，并大幅缩短运算时间。

［1］SZELISKI R.Image alignment and stitching［EB/OL］.［2013-01-20］.http://research.microsoft.com/apps/pubs/default.aspxid=75695.

［2］SZELISKI R，KANG S B.Direct methods for visual scene reconstruction［C］//Proc.IEEE Workshop on Presentation of Visual Scenes.［S.l.］:IEEE Press，1995:25-33.

［3］CANNY J.A computational approach to edge detection［C］//Proc.IEEE Trans.PAMI，1996，8(6):679-697.

［4］陈白帆.基于尺度空间理论的Harris角点检测［J］.中南大学学报:自然科学版，2005，36(5):751-754.

［5］朱建尚.基于GPU的实时亚像素Harris角点检测［J］.计算机工程，2010，36(12):213-215.

［6］蔡耀仪，林海军.基于Harris角点检测的嵌入式稳像系统设计［J］.电视技术，2012，36(13):12-16.

［7］倪乐真，李玉山，刘洋，等.一种基于角点配对的稳像算法［J］.电视技术，2009，33(S2):71-74.

［8］王玉珠，杨丹，张小洪.基于B样条的改进型Harris角点检测算法［J］.计算机应用研究，2012，36(9):73-75.