Harris角点检测的优化算法①

洪改艳, 芮廷先, 俞伟广, 何士产, 王天召(上海财经大学 浙江学院经济与信息管理系, 金华 000)(上海财经大学 信息管理与工程学院, 上海 00000)(解放军705部队, 金华 000)

Harris角点检测的优化算法①

洪改艳1, 芮廷先2, 俞伟广1, 何士产1, 王天召31(上海财经大学 浙江学院经济与信息管理系, 金华 321000)2(上海财经大学 信息管理与工程学院, 上海 200000)3(解放军73051部队, 金华 321000)

针对Harris角点检测算法中提取出较多的伪角点和计算量大的问题, 提出了一种基于Harris角点检测的改进算法. 为抑制Harris角点检测中的伪角点数目并且提高算法的效率, 首先加入预筛选得到候选角点, 在计算水平和垂直方向梯度时, 对于梯度较小的像素点进行预处理, 在进行非极大值抑制时采用自适应阈值, 提高算法自适应性, 最后利用USAN对角点进行进一步选择. 实验结果表明, 改进的Harris角点检测算法不仅提高了检测精度和效率, 而且对噪声具有一定的鲁棒性.

Harris角点; 角点预选; 自适应阈值; USAN

角点被普遍认为是二维图像亮度变化剧烈或者图像边缘曲线上曲率极大值的点[1]. 角点检测在图像匹配、光流计算、运动估计、形状分析、相机标定和3D重建、视觉的定位和测量等方面都有重要的应用.

目前, 角点检测技术可以分为两类: 第一类是基于图像边缘信息[2], 如基于边界曲率的角点检测, 基于边界链码的角点检测, 基于小波变换模极大的角点检测; 第二类是基于图像灰度信息[3], 如Moravec算法[4], Harris算法[3], SUSAN算法[1], MIC算法[5]等. 在第一类角点检测中, 角点对边缘线依赖比较大, 边缘线提取时如果发生中断, 则会对角点的提取结果造成很大的影响. 第二类角点检测主要缺点是定位精度比较差, 同时还有可能漏掉一些实际的角点, 产生一些伪角点, 对噪声比较敏感. 第二类角点检测中, 应用比较多的是Harris算法[6]和SUSAN算法, 但是存在计算量大和精度不高的问题.

本文在对Harris角点检测原理进行详细分析的基础上, 针对Harris角点检测算法在检测精度和效率这两个方面的不足, 提出了一种改进Harris算法. 改进的Harris算法在进行Harris算法之前, 首先对图像点进行预选, 选出合适的点作为候选点, 在Harris算法中对水平、垂直方向梯度进行了改进, 采用自适应阈值提取Harris角点, 最后利用USAN[1]进一步剔除伪角点. 通过实验对改进算法的精度和效率进行了验证.

1 Harris算法检测原理及步骤

1.1 Harris算法基本原理

Harris算法以Moravec算法为基础, Moravec算法的基本原理是: 取以目标像素点为中心的一个小窗口,并将窗口沿上下左右4个方向移动, 计算这4个方向上窗口内的灰度变化, 并以4个灰度变化值中的最小值作为该目标像素点的角点相应函数, 若该值大于设定阈值, 则为角点.

Harris算法则计算窗口沿任何方向移动后的灰度变化, 并用解析形式表达. 设以像素点≤为中心的小窗口在X方向上移动u, Y方向上移动v, Harris算法给出了灰度变化度量的解析表达式:

其中, det(M)表示矩阵M的行列式, trace(M)表示矩阵的迹, k一般取为0.04. 当目标像素点的CRF值大于给定的阈值时, 则该目标像素点为角点.

1.2 Harris算法步骤

根据Harris算法的基本原理, 可以将Harris算法步骤分为以下五个步骤:

Step1计算图像像素在X和Y方向上的梯度, 以及两者的乘积, 得到矩阵M;

Step2 对图像进行高斯滤波, 得到新的M;

Step3 计算原图像上对应每个像素点的CRF值;

Step4 选取局部极值点. 在Harris算法中, 特征点被认为是局部范围内的极大CRF值所对应的像点;

Step5 设定阈值, 选取角点.

2 优化的Harris算法

为了提高Harris算法检测角点的效率和精度, 改进Harris算法主要在以下四个方面:

(1) 在伪角点附近, 各点的灰度变化不太大, 甚至没有变化. 针对这种情况, 提出了邻近像素灰度相似度(Graylevel Similarity of Adjacent Pixels, GSAP)概念, GSAP是指以图像像素点为中心与其邻域8个点的像素灰度值进行比较;

(2) 由于角点的局部区域灰度变化比较大, 可以忽略梯度较小的点, 不作检测运算, 只对梯度幅值比较大的像素点进行计算;

(3) Harris角点检测算法的缺点在于提取角点的时候所用的阈值是固定的, 所以角点提取的效果完全依赖于阈值的设定. 采用自适应阈值, 提高提取角点的自适应能力;

(4) 通过改进算法提取出的角点, 可能会在真正的角点附近小的邻域内出现伪角点. 为了剔除这些伪角点, 采用USAN去除这些伪角点, 进一步提高角点提取的精度.

2.1 GSAP处理得到候选点

设中心点像素的灰度值与周围一像素点灰度值差的绝对值为Δ, 设阈值为t, 如果tΔ≤, 则认为中心点与该点周围一点相似, 同理判断中心点与周围其它点是否相似. 统计中心点与周围8个点中相似点的个数, 记为（）,C i j:

根据以上讨论可知, 0≤C（ i, j）≤8, 下面对C（ i, j）进行讨论分析, 如果能够找出一个实例判定该点可能为角点, 那么该点就作为候选点进行角点检测.

(1) C（ i, j）=0, 表示中心点周围没有与之相似的像素点, 所以该像素点为孤立像素点或者是噪声点,不能作为候选点;

(2) C（ i, j）=7, 可表示为图1的两种情况, 其它情况都可以通过这两幅图像变换得到. (a)可能的角点应该是目标像素点的正上方的那个像素点, (b)可能的角点应该是目标像素点左上方的那个像素点, 所以这种情况下, 中心像素点不应该作为候选点;

(3) C（ i, j）=8, 表示中心点邻域的8个点都是与之相似的点, 不能作为候选点;

(4) 1≤C（ i, j）≤6, 这是情况比较复杂, 如图1(c)(d)(e)(f)(g)(h)所示, 此时中心像素点应该作为候选点进行角点检测.

图1 1≤C（ i, j）≤7的几种情况

综上所述, 当1≤C（ i, j）≤6时, 将中心像素点作为角点的候选点.

2.2 角点检测预处理

由于角点的局部区域图像灰度变化比较大, 可以忽略水平和垂直方向上梯度比较小的点, 不进行角点检测的运算, 只对梯度幅值比较大的像素点进行Harris计算, 这些像素点反映了图像角点的主要信息.在角点检测运算中, 对于点（x, y）, 计算其在水平方向的梯度Ix和垂直方向的梯度Iy, 利用如下公式进行判断, 只有满足条件的点才可以做后面的检测算法,否则就忽略该点.

其中, M和N为图像的高和宽, 这样就避免了在整个图像的每个像素点上计算Harris算子, 减少了计算量,同时也可以保证得到大部分的角点.

2.3 自适应阈值

在对一幅图像进行角点提取的时候, 使用的阈值是固定的, 可能会取得好的效果. 但是对其它图像未必使用, 考虑到算法的通用性, 提高检测精度, 有必要对阈值的自适应能力提出要求, 需要算法本身有能力计算出合适的阈值. 阈值是在提取角点时才会使用,因此考虑由角点响应函数值CRF来确定.

求取每个预处理后的角点的响应函数值CRF, 找出最大的CRF值, 随后定义阈值T为最大CRF值的p倍决定的, 即:

其中, C为总的预处理后的候选点总数目. 则:

从统计的观点出发,, 选取一系列图像包括各种场景进行实验,, 不断调整设定的p值, 比较结果, 发现p取经验值[0.005, 0.015] 时, 基本上所有角点都可以被检验出来, 而且产生的伪角点较少.

2.4 利用USAN去除伪角点

通过改进算法提取出的角点, 可能会在真正的角点附近小的邻域内出现伪角点. 为了剔除这些伪角点,采用USAN去除这些伪角点, 进一步提高角点提取的精度.

通过T=p· CRFmax提取出来的角点为corner( i, j), 利用圆形模板对corner( i, j)进行过滤.如果以角点（i, j）为模板核的USAN面积大于模板面积的一半, 则认为（i, j）是伪角点, 从而将点（i, j）从corner( i, j)中剔除. 过滤完所有的corner( i, j)后, 余下的点就是最终得到的角点. 文中采用的模板为7x7的圆形模板, 如图2所示.

图2 7x7圆形模板及利用USAN的角点判别

3 实验结果及分析

为了验证本文改进算法的有效性, 利用经典的“积木”图片进行仿真验证. 实验数据: 256x256像素大小的图片, 在PC(Intel(R) Core(TM) i3CPU2.93GHz, 1.80G内存)机上利用Matlab进行实验. 高斯窗口为7x7, t取20, 非极大值抑制窗口为3x3, 圆形模板为7x7, 比例系数p取0.008. 实验结果如图3所示.

图3 实验结果

表1 实验数据结果比较

通过实验, 原始的Harris检测算法在检测时产生较多的伪角点, 并且程序运行的时间比较长. 而改进后的Harris检测算法因为对图像点进行了预选择和预处理, 大大降低了程序运行的时间, 从0.765s减少为0.297s, 将近原始算法的30%; 保证检测出正确的角点的同时, 检测时产生的伪角点数目也大大降低, 从16个降低到了5个, 不足原始算法的30%.

为了验证改进的Harris检测算法对噪声的鲁棒性,对图像增加了椒盐噪声, 椒盐噪声通常由图像传感器、传输信道、解码处理、图像切割等产生的黑白相间的亮暗点噪声, 实验中椒盐噪声的参数d=0.01, 实验结果如图4所示.

图4 加入椒盐噪声(d=0.01)后的实验结果

通过实验结果可以看出, Harris算法对噪声比较敏感, 但是改进后的Harris算法相对于原始Harris算法具有一定的鲁棒性.

4 结语

针对Harris角点检测算法的一些缺点, 包括在角点提取中会出现伪角点, 并且在非极大值抑制时设置固定阈值的问题, 提出了基于Harris角点检测算法的改进算法. 在不影响Harris角点检测算法计算简便和稳定的前提下, 首先利用GSAP对图像进行处理得到候选点, 在计算水平和垂直梯度时对候选点进行预处理, 在非极大值抑制时采用自适应阈值, 提高了算法的自适应性, 最后为了进一步剔除伪角点采用USAN对提取的角点进行处理. 实验结果表明, 优化后的Harris角点检测算法不仅仅减少了提取的伪角点数量和缩短了运算时间, 而且对噪声具有一定的鲁棒性.

1 Smith SM, Brady JM. SUSAN—A new approach to low-level image processing. International Journal of Computer Vision, 1997, 23(1): 45–78.

2 Quddus A, Fahmy MM. An improved waveletbased corner detection technique. Proc. of the IEEE International Conference on Acoustics, Speech and Signal Processing. Phoenix, USA. IEEE. 1999. 3213–3216.

3 Harris C, Stephens MJ. A combined corner and edge detector. Proc. of the 4th Alvey Vision Conference. Manchester, England. IEEE. 1988. 147–151.

4 Moravec H. Towards automatic visual obstacle avoidance. Proc. of the 5th International Joint Conference on Artificial Intelligence. Cambridge, MA, USA. William Kaufmann. 1977. 584.

5 Trajkovic M, Hedley M．Fast corner detection． Image and Vision Computing, 1998, 16(2): 75–87．

6 Schmid C, Mohr R, Bauckhage C. Evaluation of Interesting Point Detectors. International Journal of Computer Vision, 2000, 37(2): 151–172.

Improved Algorithm Based on Harris Corner Detection

HONG Gai-Yan1, RUI Ting-Xian2, YU Wei-Guang1, HE Shi-Chan1, WANG Tian-Zhao31(Department of Economics and Information Management, Shanghai University of Finance and Economics Zhejiang College, Jinhua 321000, China)2(School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200000, China)3(No.73051 of PLA, Jinhua 321000, China)

According to the problems of extracting more false corners and large computation problems in harris corner detection, this paper proposes an improved algorithm based on harris corner detection. In order to reduce the number of false corners and improve the algorithm efficiency, a pre-selection strategy is embedded to pick out potential corners before the normal routine. When calculate the horizontal and vertical gradients, the pixels with smaller horizontal and vertical gradients are pre-processed. In order to improve the auto-adaptive of algorithm, an auto-adaptive threshold is adopted, finally using USAN to make further selection. The result shows that the improved algorithm not only can improve the precision and efficiency of corner detection, but also is robust to noise to some extent.

Harris corner; corner pre-selection; auto-adaptive threshold; USAN

2016-07-18;收到修改稿时间:2016-08-08

10.15888/j.cnki.csa.005718