一种改进的亚像素角点提取算法

摘要：针对Harris角点检测过程中存在定位粗糙、检测精度不高以及检测效率慢等原因，该文在Harris算法的基础上，结合Harris算子和Forstner算子提出一种改进的亚像素角点提取算法。该算法采用一种逐层检测策略，首先利用Harris算法进行角点粗略定位，首先对角点做一个初始选择，利用图像领域灰度相似度得到大部分角点的粗定位值，大大降低了算法的运算量，然后通过计算自相关矩阵的两个特征值，利用特征值和阈值比较筛选得到全部角点的粗定位值，避免了CRF（corner reference function角点响应函数）的计算，最后利用Forstner算子对粗定位后的角点进行亚像素级精确定位。实验证明，该算法不仅保证Harris算法的灵活性和Forstner算子的亚像素级精度，而且速度快，并且抗噪声性能较强。

关键词：Harris；Forstner；CRF；亚像素 效率；精度

中图分类号： TU198+.3 文献标识码：A 文章编号：1009-3044（2014）19-4552-04

An Improved Subpixel Corner Extraction Algorithm

TANG Ya-ping， CHEN Su-ting

（Jiangsu Key Laboratory of Meteorological Observation and Information Processing， Nanjing University of Information Science &Technology， Nanjing 210044， China）

Abstract： In view of the rough positioning、inaccurate detecting and the slow efficiency in the Harris corner detection，According to this，an improved Harris algorithm is presented in this paper， on the basis of the combining with Harris algorithm and Forstner operator . The algorithm adopts a layered detection strategy， firstly using Harris algorithm for corner rough localization， considering the slow detecting， before calculating the CRF we made an initial choice to avoid large amount of multiplication， after geting the coarse position of angular point， we then calculate Forstner operator for accurate positioning. Experiments show that the algorithm not only guarantees the flexibility of Harris algorithm and the subpixel accuracy of Forstner operator ，but also improve the speed and have strong anti-noise performance. The algorithm overcomes the problem on the detection speed and precision in the Harris algorithm.

Key words： Harris； Forstner； CRF； subpixel； accuracy； detection efficiency

图像特征点的提取是计算机视觉领域中非常重要的一步，其中，图像角点是最常见的一类特征之一，它具有旋转不变性、不随光照变化等优点，因此角点特征被广泛应用于物体跟踪、三维建模、摄影测量自动化以及遥感图像匹配等领域。

本文通过分析Harris角点检测过程中的一些弊端，如在对角点进行选择定位的过程中采用了大量乘法运算，运算量大，大大降低了算法检测的效率，同时Harris算法只能检测到像素级水平的坐标，对于精度要求高，需要准确定位像素坐标的场合不能够满足精度要求，该文在Harris算法基础上提出了一种改进的亚像素角点检测算法，该算法通过Harris算法和Forstner算子相结合，首先用Harris算法进行粗定位，在定位过程中对角点做一个初始选择，避免了大量的乘法运算，得到角点的粗定位值后，最后利用Forstner算子对角点进行亚像素级的精确定位。

1 Harris角点检测的原理

1988年，Chris Harris和Mike Stephens提出了Harris角点检测算法，该算法突破了Moravec算子在角点检测领域的局限性，Harris算法通过微分算子来计算像素点在任意方向的灰度变化，并计算出目标像素点的CRF（角点响应函数值），当CRF小于某个很小的值时，则认为检测点在区域内部，即灰度基本上无变化的区域，当CRF大于给定的阈值时，认为此点就是是角点，CRF小于零时，认为此点属于边缘上某点。

2 改进的Harris亚像素角点检测算法

2.1 Harris算法角点初定位

该算法首先利用Harris算法进行角点初定位，并在原算法基础上加以改进，主要是在计算CRF之前对所有像素点做一个初步筛选，因为这一部分主要都是加法运算，不涉及乘法操作，因此效率较原算法大大提高。

这里我们提出图像区域像素相似度的概念，图像区域像素相似度是指检测窗口中心点的灰度值与其周围n 个邻域内所有其他像素点灰度值的相似度，用它们的灰度差来描述这种相似度，如果灰度差小于某个值，则认为该点与中心点相似，反之则与中心点不相似。

我们使用的是3*3的检测模板窗口，对于中心像素点Image （i，j）计算其周围8 个邻域内像素点的相似度。并且统计中心像素点和该范围内像素点灰度值差的绝对值（记为Δ），若该值小于我们设定的阈值，就认为目标像素点与该像素点相似。

[nlike（i，j）=sum（R（i+x，j+y）） ] （1）

[（-1≤x≤1，-1≤y≤1，x≠0，y≠0）]其中：[1≤Δ（i+x，j+y）≤t]

当[Δ（i+x，j+y）>t]时[R（i+x，j+y）=0]。

从定义中可以看出：[0≤nlike≤8]。现在讨论 [nlike（i，j）]值的含义 。

1） nlike （i ， j） = 8，表示 8 个邻域范围内都是和它相似的像素点排除此类点作为角点可能性

2） nlike （i ， j） = 0，表示 8 个邻域范围内都是和它不相似的像素点，也可以排除。

3） nlike （i ， j） = 7，分为以下两种情况，图 2（a） 中，角点可能位于中心像素点正上方的那个像素点，图2（b） 中，角点可能位于中心像素点右上方的那个像素点，这种情况也应该排除。

（a） （b）

图2

4） nlike （i，j） =1，也有两种情况。由上可知中心像素点也应该排除作为角点可能性。

5） 2 ≤ nlike（i，j） ≤ 6，暂时无法判定，作为我们的角点候选点集。

对上述不能通过图像领域像素相似度进行定位的角点，我们通过原Harris算法计算这些角点的自相关矩阵的特征值，如果两个特征值都很小，则说明这个区域是一个平坦区域；如果两个特征值一大一小，则是一条直线；如果两个值都很大，则这个点就是角点。或者通过计算CRF来进行判断。

[R=C（x，y）=det（M）-ktr2（M）] （2）

其中C只与自相关矩阵的特征值M有关，若C大数值整数，则为角点，若C为大数值负数，则为边缘上的点，若C为小数值整数，则为平坦区域中的点。在算法当中，我们对CRF进行阈值处理，判断CRF>threshold，并提取局部最大值点就是我们所需要的角点。

2.2 角点的亚像素级精确定位

考虑到Harris算法角点检测过程中存在定位不精确的问题，而Forstner算子本身就拥有较高的定位精度但是却受灰度对比度变化的影响较大，该文通过将Harris算法与Forstner算子结合起来，利用Forstner算子的定位功能对经过Harris算法粗定位后的角点进行亚像素级坐标的精确定位。

2.2.1 最佳窗口的确定

以每一个候选角点为中心，取一个3*3的窗口N进行计算窗口兴趣值q和w，若兴趣值大于给定阈值，并且为局部最大值，则将该窗口作为我们的最佳窗口。其中阈值由上一步Harris算法粗定位过程中根据图像灰度确定的阈值T所决定。

1）首先计算每个粗定位角点（c，r）的Robert’s梯度：

[gc=?g?c=gi+1，j+1-gi，jgr=?g?r=gi，j+1-gi+1，j] （3）

图3 Robert’s梯度

2） 计算3*3窗口中的灰度协方差矩阵Q

[Q=N-1=gc2gcgrgrgcgr2-1] （4）

其中：

[∑gc2=i=c-kc+k-1i=r-kr+k-1（gi+1，j+1-gi，j）2∑gr2=i=c-kc+k-1i=r-kr+k-1（gi，j+1-gi+1，j）2gcgr=i=c-kc+k-1i=r-kr+k-1（gi+1，j+1-gi，j）（gi，j+1-gi+1，j）K=INT（1/2）] （5）

3） 计算兴趣值q和w

在计算兴趣值之前我们首先对各个模板窗口做一个初始选择，在以某个角点粗定位值为中心的窗口内，分别在x、y方向上计算Sobel梯度算子大小，当它们大于给定阈值时，才对所在窗口计算兴趣值q和w。

[Gx=-10+1-20+2-10+1*W and Gx=+1+2+1000-1-2-1*W] （6）

Gx及Gy分别代表经横向及纵向边缘检测的图像，W表示被选窗口，窗口内每个像素的横向及纵向梯度近似值为[G=Gx2+Gy2]，当G>T时，对其计算兴趣值。

接下来对粗角点为中心的每个模板大小窗口计算兴趣值q和w，考虑到矩阵的迹作为分母，当矩阵的迹等于0时，无法判断结果，因此在计算矩阵迹时，加上一个常数C，避免了矩阵迹为0时无结果的情况。

[q=4Det（N）tr2（N）+Cw=1tr（Q）=Det（N）tr（N）+C] （7）

其中[Det（N）]代表矩阵N的行列式，[tr（N）]为矩阵的迹。

2.2.2 粗定位角点的精确定位

对Harris算法初步定位出来的角点进行精确定位，首先我们假设最佳窗口内任意粗定位角点（c，r）的边缘直线L的方程为：

[ρ=rcosθ+csinθ] （8）

上式中，[ρ]为原点到直线L的垂直距离；[θ]为梯度角，[tanθ=gc/gr.gc，gr]为该点的Robert梯度。假设角点坐标为[（c0，r0）]，同时设v为点[（c，r）]到直线L的距离，在[（c，r）]处我们给出误差方程：

[ρ+ν=r0cosθ+c0sinθw（r，c）=Δg2=gr2+gc2] （9）

对上式进行法化，可得下式：

[gr2grgcgrgcgc2.r0c0=gr2rgrgccgrgcrgc2c] （10）

求解上述方程，我们就可以得到角点的亚像素级坐标[（c0，r0）]。

3 实验结果及分析

通过Matlab实现上面改进后的算法，并与Harris原算法提取后的角点进行比较，通过对多幅图像的角点提取实验证明，该算法对角点目标的提取、定位抗噪性能好，运算量小且实现速度快。

3.1 改进算法对角点检测的时间运行效率实验及分析

表1为改进前原 Harris 算法和改进后的Harris 算法对6 幅给定图像进行角点提取时，在核心算法部分（通过计算CRF确认角点）所消耗的平均时间的比较。

表1 原算法与改进算法在核心算法部分平均消耗时间的比较（单位：秒）

[图像名＼&lena.jpg＼&stuff.jpg＼&fruits.jpg＼&baboon.jpg＼& fish.jpg＼&cat.jpg＼&改进前 ＼&6.566712＼&6.556286＼&6.755664＼&6.681580＼&6.601732＼&6.569117＼&改进后＼&1.170748＼&1.141037＼&1.598029＼&2.172551＼&2.195614＼&1.130464＼&]

3.2 改进算法与原算法在图像角点定位精度方面的比较

通过对南京信息工程大学的遥感图像利用原算法和改进算法分别进行角点检测，进行对比。

（a）原算法 （b）改进算法

图4

表2 原算法和改进算法在遥感图像上提取的角点坐标比较（单位：pixel）

[＼& Harris算法角点像素级坐标＼& 改进算法亚像素级坐标＼&1＼&（88，110）＼&（88.1135，110.3272）＼&2＼&（71，107）＼&（71.8135，107.1112）＼&3＼&（197，65）＼&（197.7462，65.9697）＼&4＼&（328，321）＼&（328.7394，321.8376）＼&5＼&（318，235）＼&（318.9163，235.6999）＼&6＼&（212，303）＼&（212.0830，303.1214）＼&7＼&（63，96）＼&（63.3472，96.5439）＼&8＼&（316，343）＼&（316.7932，343.5493）＼&9＼&（329，333）＼&（329.3616，333.7831）＼&10＼&（190，313）＼&（190.1755，313.9654）＼&]

4 结论

本文通过改进Harris角点检测算法，并通过实验验证了改进算法在角点检测方面的优越性，分别就提取时间和提取的准确度与原算法进行了比较。改进算法解决了Harris算法定位不精确，运算量大等情况，还解决了Foestner算子受阈值选择以及图像对比度和灰度的影响，通过实验验证，改进算法的运算时间约为原算法的17.83%，并且角点的亚像素定位误差可达到0.1265个像素，可以有效的应用于后期的计算机视觉和三维重建当中。

参考文献：

[1] 周龙萍.基于改进的Harris算法检测角点[J].计算机技术与发展，2013，23（2）：11-14.

[2] 房超，王小鹏，牛云鹏，王超.基于改进Harris算法的角点检测[J].计算机与数字工程，2011，39（5）：142-144.

[3] 郭海霞，解凯.基于USAN的改进的角点检测算法[J].计算机工程， 2007，22（33）：232-234. （下转第4571页）

（上接第4555页）

[4] 张海燕，李元媛，储晨昀.基于图像分块的多尺度 Harris 角点检测方法[J].计算机应用，2011，31（ 2） ：356-357.

[5] 王崴，唐一平，任娟莉.一种改进的Harris 角点提取算法[J].光学精密工程，2008，16（10）：1995-2001.

[6] Ville O， Janne H. Image registration using blur-invariant phase correlation [J].IEEE Signal Processing Letters，2007， 14（7）： 449-452.

[7] Chen Aihua，Zhu Ming，Wang Yanhua，Xue Chen.Image feature points match algorithm based on orientation angles[J].Journal of Optoelectronics-Laser，2009，20（4）.

[8] Bastanlar Y，Yardimci，Y.Corner validation based on extracted comer properties[J].Computer vision and image understanding，2008，112（3）.

[9] Song wei，Hou Jianjun.A novel zero-bit watermarking algorithm based on Logistic chaotic system and singUlar value decomposition[J]Acta Physica Sinca，2009，58（7）.

[10] Zhao Wanjin，Gong Shengrong，Liu Chunping，Shen Xiangjun.A Daptive Harris Corner Detection Algorithm[J]. Computer Engineering，2008，34 （10）：212-215.