基于模板边缘的自适应Harris角点检测算法

李冰 吕进来 郝晓丽

摘  要： 针对传统Harris算法检测的角点出现聚簇、伪角点以及阈值人为设定的问题，提出一种基于模板边缘的自适应Harris算法。首先，利用局部区域的思想检测出图像中的潜在角点区域;然后，对潜在角点区域利用改进的自适应阈值Harris算法进行角点提取;最后，提出模板边缘的思想，构造一个新的圆形模板，通过评估中心点与模板边缘像素点邻域的灰度变化情况，对提取的角点进行提纯，过滤掉伪角点，得到最终检测结果。实验结果表明，该方法在计算效率上比Harris算法提高了32.8%，在实际应用中具有较高的精确度和鲁棒性。

关键词： 角点检测; 自适应Harris算法; 角点提取; 角点提纯; 伪角点过滤; 圆形模板构造

中图分类号： TN911.73?34                       文献标识码： A                         文章编号： 1004?373X（2019）11?0040?05

Abstract： Since the traditional Harris detection algorithm has the problems of corner point clustering， pseudo corner point and man?made threshold setting， an self?adaptive Harris algorithm based on template edge is proposed in this paper. The algorithm is to detect the potential corner area in the image by using the idea of local area， and then the improved adaptive threshold Harris algorithm is used to extract the corner point in the potential corner area. On the basis of template edge， a new circular template is constructed. The grayscale change of pixel points in the center and template edge area is evaluated to purify the extracted corner points， filter out the pseudo corner points， and obtain the final detection results. The experimental results show that the computational efficiency of the algorithm is improved by 32.8% than the traditional Harris algorithm， and the algorithm has higher accuracy and stronger robustness in practical applications.

Keywords： corner detection; adaptive Harris algorithm; corner point extraction; corner point purification; pseudo corner filtering; circular template construction

0  引  言

角點检测是图像处理的基础问题，尽管一个角点可能只包含0.5%个像素，但它却能代表这幅图像最重要的信息。角点具有计算量少、匹配简单、不受光照影响以及旋转、平移、缩放不变性的优点，因此，角点在三维场景重建、目标跟踪与识别等计算机视觉领域具有广泛的应用[1?3]。

目前，角点提取技术主要分为两类：基于图像边缘的角点检测算法和基于灰度变化的角点检测算法[4]。前者主要是通过分析图像边缘曲线的几何特性来检测角点。但该方法过于依赖图像边缘轮廓，难度较大，计算复杂，且一旦图像边缘存在模糊或发生局部变化，可能会导致角点提取失败[5]。

而基于灰度变化的角点检测算法是根据图像像素点的灰度变化情况，计算曲率和梯度来提取角点，其中最具典型的算法为Harris算法。文献[6]针对Harris算法尺度变化敏感的问题，提出将区域检测和利用多尺度结合非极大值抑制的改进Harris算法相结合的方法，该方法能有效增强算法的多尺度性，但运算量大，在低对比度图像中易产生虚假角点。文献[7]针对Harris算法阈值人为设定的问题，将图像进行分割，根据子图的对比度设置阈值，并结合NCC算法和RANSAC算法对角点进行提纯。该方法能有效增加图像匹配点对数。文献[8]针对Harris算法的检测性能依赖高斯窗窗长和阈值的不足，提出圆环模板，利用像素点评估中心像素邻域灰度的变化来滤除虚假角点。该方法具有较好的鲁棒性，但阈值设置低会出现大量伪角点，需要一一进行滤除，计算量大，耗时长。

在综合了前人研究工作各自优势和不足的基础上，本文提出一种基于模板边缘的自适应Harris角点检测算法。该算法首先利用局部区域的思想[9]，找出图像局部灰度变化明显的区域，建立潜在角点区域库，然后用改进的自适应阈值Harris检测算法对库中区域进行角点提取，形成角点集，最后提出了模板边缘的思想，对角点集进行提纯，过滤掉伪角点。该方法不仅运算量小，而且利用像素间的相关信息，提高了检测精度。实验分析验证了本文算法的良好性能。

1  Harris角点检测算法

Harris角点检测算法主要运用微分运算和自相关矩阵检测图像的角点[10]。定义图像[I]，在图像上任意像素点[（x，y）]处，模板[w（x，y）=exp（x2+y2）σ2] 形成的窗口在[x]方向和[y]方向分别移动[（u，v）]后产生的灰度变化[E（u，v）]为：

式中：[λ1]和[λ2]为矩阵[Q]的特征向量;[k]为经验常数，取值范围为[0.04～0.06]。在本文实验中，[k=0.04]。当图像中每一个像素点对应的[CRF]值在局部区域内为极大值并大于设定的阈值时，则该点即为需要提取的角点。

Harris算法能够有效提取图像的特征，具有计算量小、稳健性强的优点。但在实际应用中也发现了一些不足：

1） 阈值人为选择，可能会影响角点检测的数量。阈值大会造成大量角点信息的丢失，反之，则会提取出伪角点。

2） 提取角点不精准，会出现聚簇角点和伪角点。本文在继承Harris算法的基础上，对这两点不足进行改进。

2  基于模板边缘的自适应Harris算法

2.1  潜在角点区域检测

由于角点检测算法对每一个像素点会进行多次重复运算，而实际上一幅图像中只有10%～20%属于可能的角点区域。为了避免多重运算，先对图像进行潜在角点区域提取：通过运用[3×3]大小的两个相邻区域的灰度值之均值和的差值大小来比较，判别该区域是否有角点存在，具体判别公式如下：

式中：[（x0，y0）]与[（x1，y1）]表示模板的中心点;[P（x0，y0）=19x0，y0为中心I（x，y）]，[P（x1，y1）=19x1，y1为中心I（x，y）]分别表示一个模板的像素灰度值之均值和;[T1]为给定的阈值，为了避免人为设定阈值对实验结果的影响，采用可变阈值[T1=12min（P（x0，y0），P（x1，y1））]。

若两个区域的灰度变化之差[Δp]大于阈值[T1]，就认为该区域可能存在角点，设定为潜在角点区域;反之，则为平坦区域。

2.2  模板边缘思想

目前采用的模板通常是圆或矩阵，并对模板中心与模板下覆盖的所有像素点进行比较。但模板覆盖过多冗余的信息，导致计算量增加。本文提出的模板边缘思想是借鉴SUSAN算法思想[11]提出的，如图1所示。

图1  圆形模板边缘

令[M]表示模板，模板中的像素用[m∈M]表示，中心点的像素為[m0]，模板边缘的像素点分别用[m1，m2，…，m20]表示。在图像内移动模板，用[V]表示模板边缘像素灰度方差，则：

2.3  基于模板边缘的自适应Harris算法

本文先利用局部区域思想对图像潜在角点区域进行粗略的筛选，然后只需对潜在角点区域库使用改进的自适应阈值的Harris角点检测算法进行角点检测，而平坦区域直接跳过，在一定程度上提高了算法效率。

在利用Harris算法对潜在角点区域库进行角点提取时，为了避免漏检情况，采用的高斯窗口设置为[[9，3]]。阈值是根据每个潜在角点区域灰度值的变化来确定的，先对式（3）的CRF进行非极大值抑制，保留大于动态阈值[t]与式（4）中的可变阈值[T1]且为局部极大值的点，作为角点。公式如下：

式中：[t]动态变化，其变化范围主要依据潜在角点区域像素点的局部最大值来确定。

实验表明，本文[t]的最佳变化范围为0.009～0.02。这里与可变阈值[T1]进行比较，主要是为了将区域中特征变化不明确的角点筛选掉，减少计算量。提取初角点后，利用模板边缘的思想对其进行筛选，过滤掉伪角点和聚簇角点。方法如下：

对于圆形模板边缘[M]，将模板中的每个像素点[mk]与中心点的像素[m0]进行灰度比较，若大于[V]，设为1;反之设为0。具体公式为：

模板在图像上进行移动，当移动到平坦区域，模板上为1的点为0个;当移动到边缘，如图2情况1所示，模板上为1的点为11个;当移动到角点，如图2情况2所示，模板上为1的点小于11个。构造最终的角点响应函数为：

式中[N=k=120N（mk）] 。若[C]为1，则判断模板中心点[m0]为最终角点;反之，则舍去。

2.4  算法流程

本文从提取角点的精确度和计算效率的角度出发，提出基于模板边缘的自适应Harris角点检测算法，算法步骤如下：

Step1：输入图像，进行灰度处理。

Step2：提取潜在角点区域：通过运用[3×3]大小的两个相邻区域的灰度值之均值和的差值大小来比较，最终根据式（4）判断该区域是否有角点存在，若存在，命名为潜在角点区域，形成潜在角点区域库。

图2  模板边缘检测示例图

Step3：对潜在角点区域库利用改进的自适应Harris算法进行角点提取，形成角点集：

1） 利用模板[w（x，y）]生成高斯窗口[9，3]，在图像上移动产生灰度变化[E（u，v）]。

2） 根据式（2）对[E（u，v）]进行变化，并得到矩阵[Q]。计算矩阵的特征向量[λ1]和[λ2]。

3） 根据式（3）的角点响应函数[CRF]进行角点判别，[k]取常值0.04。

4） 根据式（6）对[CRF]进行非极大值抑制，保留大于动态阈值[t]、可变阈值[T1]且为局部极大值的点，作为初角点。

Step4：初角点提纯。具体操作如下：

1） 利用模板[M]在图像上移动，当中心点的像素[m0]移至Step3提取的初角点时，根据式（5）计算中心点与模板边缘像素灰度方差[V]。

2） 根据式（7）对方差[V]进行判别，更新[N（mk）]。

3） 根据式（8）的角点响应函数[C]判断模板中心点[m0]是否符合条件。若满足，则此初角点为最优角点，保留此初角点;若不满足，则将此初角点舍去。

判断完一个初角点之后，继续移动模板[M]至下一个初角点继续进行Step4，直到所有的初角点全部判别完毕，结束本算法。

本文算法的流程图如图3所示。

3  实验结果与分析

为了充分验证本文算法的有效性及优越性，首先选取了[256×256]的两幅边缘像素灰度变化明显的图像进行验证，并将实验结果与Harris算法、SUSAN算法、文献[8]的实验结果进行对比。图4为各算法检测结果。

图3  本文算法流程图

图4  各算法角点检测结果对比

通过观察图4可以看出，Harris算法和SUSAN算法提取的角点数目较多，但存在很多伪角点和聚簇角点。文献[8]的实验结果明显解决了伪角点和聚簇角点的不足，但漏检角点相对较多，且计算时间比本文算法长。本文算法表现出较好的检测性能，且时间上优于其他三种算法。

为了进一步验证本文算法的优越性，又采用2幅[280×280]的实际场景图像进行仿真实验。分别为摄影师图像和一个俯视图图像，这2幅图像中既有灰度变化较大的部分，也有曲率变化不太明显的角点和低对比度的角点。各算法检测结果如图5所示。可以看出，在实际场景中，Harris算法和SUSAN算法提取出的角点存在大量的虚假角点和聚簇角点;文献[8]算法检测结果表现较好;本文算法检测的角点数量虽然较少，但是准确率高，极少存在虚假角点，且提取出的角点在整幅图像中特征属性明显，具有实用价值。

为了能定量分析这四种算法提取角点的优劣性和时间效率，表1给出了4幅图像进行角点检测所用时间，结合实验结果和表中数据可以看出，本文算法提取的角点精度相较于其他三种算法高，且所用时间短，计算效率比Harris算法提高了32.8%，比文献[8]提高了34.2%。

图5  实际场景图像角点检测结果对比

表1  4幅图像的角点检测所用时间结果比较

4  結  语

针对传统Harris角点检测算法出现聚簇、伪角点以及阈值人为设定的问题，本文提出了模板边缘的思想。运用局部区域的思想检测出潜在角点区域，利用自适应阈值的Harris算法对潜在角点区域库进行角点提取，最后用模板边缘的思想对提取的角点进行提纯，过滤伪角点和聚簇角点。仿真结果表明本文算法鲁棒性好，结果精确，且计算效率比Harris算法提高了32.8%。未来研究工作将重点对提取的角点进行特征点匹配，以此来增强本文算法的实用性。

参考文献

[1] MANORANJITHAM R， DEEPA P. Novel interest point detector using bilateral?Harris corner method [C]// 2017 International Conference on Advanced Computing and Communication Systems. Coimbatore： IEEE， 2017： 1?4.

[2] YAO G， CUI J， DENG K， et al. Robust Harris corner matching based on the quasi homography transform and self?adaptive window for wide?baseline stereo images [J]. IEEE transactions on geoscience & remote sensing， 2017， 56（1）： 559?574.

[3] 洪改艳，芮廷先，俞伟广，等.Harris角点检测的优化算法[J].计算机系统应用，2017，26（4）：169?172.

HONG Gaiyan， RUI Tingxian， YU Weiguang， et al. Improved algorithm based on Harris corner detection [J]. Computer systems and applications ， 2017， 26（4）： 169?172.

[4] ZHANG W C， SHUI P L. Contour?based corner detection via angle difference of principal directions of anisotropic Gaussian directional Derivatives [J]. Pattern recognition， 2015， 48： 2785?2797.

[5] 赵亚利，章为川，李云红.图像边缘轮廓自适应阈值的角点检测算法[J].中国图象图形学报，2016，21（11）：1502?1514.

ZHAO Yali， ZHANG Weichuan， LI Yunhong. Novel contour?based corner detection with adaptive threshold [J]. Journal of image and graphics， 2016， 21（11）： 1502?1514.

[6] 吴鹏，徐洪玲，李雯雯.基于区域检测的多尺度Harris角点检测算法[J].哈尔滨工程大学学报，2016，37（7）：969?973.

WU Peng， XU Hongling， LI Wenwen. Multi?scale Harris corner detection algorithm based on region detection [J]. Journal of Harbin Engineering University， 2016， 37（7）： 969?973.

[7] 张见双，张红民，罗永涛.一种改进的Harris角点检测的图像配准方法[J].激光与红外，2017，47（2）：230?233.

ZHANG Jianshuang， ZHANG Hongmin， LUO Yongtao. Image registration method based on improved Harris corner detection algorithm [J]. Lasers & infrared， 2017， 47（2）： 230?233.

[8] 邓淇元，曲长文，江源.基于圆环模板的改进Harris角点检测算法[J].系统工程与电子技术，2016，38（4）：949?954.

DENG Qiyuan， QU Changwen， JIANG Yuan， Improved corner detection algorithm based on circle mask via Harris [J]. Systems engineering and electronics， 2016， 38（4）： 949?954.

[9] 梁艳.角点检测理论及算法研究[D].武汉：华中科技大学，2010.

LIANG Yan， Research on primary corner detection algorithm [D]. Wuhan： Huazhong University of Science and Technology， 2010.

[10] JUN Yan， YAN Piao. Research on the Harris algorithm of feature extraction for moving targets in the video [J]. Applied mechanics and materials， 2015， 741： 378?381.

[11] GAO Chao， ZHU Hongjun， GUO Yongcai. Analysis and improvement of SUSAN algorithm [J]. Signal processing， 2012， 92（10）： 2552?2559.