基于Harris-CPDA的角点检测算法

胡晓彤，朱博文，程 晨

(天津科技大学 人工智能学院，天津 300457)

0 引 言

在工业自动化检测中，特征点检测被广泛应用于目标检测[1]、目标定位[2]、图像配准、图像拼接中，该技术减少人为手动调整，同时能准确反应被检测物体图像的重要的特征信息。目前针对提取角点的方式不同可以分为两大类[3]。

基于图像灰度变化检测角点。Harris算法[4]是由Harris和Stephens提出，针对更早期的Moravec算法[5,6]的优秀改进型。而针对Harris需人为多次调整阈值的弊端，提出非极大抑制[7]方式处理。韩松奇等[8]提出针对Harris算法采用非极大抑制时采用双阈值的方式对不同阈值下的角点进行比对；苏婷等[9]提出通过二次非极大值抑制，在第一次取极大值点之后，在其基础上再次选取，相当于选取第二大灰度变化值保留稍大局部里的相应度最大的点；而张见双等[10]提出将原图像分割成无重叠子区域，针对每个单独子区域设定单独阈值，根据子图对比度大小从而自适应阈值。

另一类是基于类曲率角点检测方式。最初由Ronsenfeld和Johnston提出支持域的余弦相似度估计曲率[11]，并在之后提出RJ73算法[12]，用平均K-consine代替原有算法，并且提出曲线上的某一点不能被赋予正确的支撑域大小；此时Mokhtarian和Suomela提出基于曲率尺度空间(curvature scale space，CSS)的角点检测算法[13]，该算法是在局部上进行检测角点，再从上至下的高尺度逐渐向低尺度追踪角点的位置，在不同尺度下进行搜索；为了弥补尺度因子与阈值选取问题，Awrangjeb和Lu提出点到弦距离累加和技术(chord-to-point distance accumulation，CPDA)[14]。

从Zhang等于ECCV上提出在基于图像细粒度上的分类识别实验[15]，将整体图像根据细粒度分类算法，在不同区域进行微小的特征分析。由这一思想，本文提出结合改进的Harris-CPDA算法生成关键点区域，从而进行进一步分析。

1 Harris角点检测算法及其优化

1.1 Harris角点检测的原理

Harris角点检测的算法可以说是对Moravec算法已有的缺陷问题进行优化及改良。Moravec算子实际上是依托一个正方形窗口只计算了8个方向的相邻像素灰度，同时使用了窗口值，只要在窗口中，权重都设置为1，但其实应当在中心位置赋予更大的权重。后人进行了很多改进的算法，其中Harris算法选取了一个较为平滑的窗口计算了各个方向上的像素灰度变化。图1(a)为图像中某一区域，我们在该局部区域存在一个窗口；图1(b)为当前局部区域各个方向上移动灰度信息并未发生变化，判定为该窗口区域并无角点特征；图1(c)为该平滑窗口在某一特定的方向上移动灰度值发生变化，而其它方向上并无变化，那么窗口检测的可能为一条直线线段，其中也无角点的特征；图1(d)为当该窗口多个方向运动存在不同的灰度值的变化则判定为该平滑窗口区域可能存在角点特征。

图1 不同区域灰度变化的描述

Harris算法获得各个方向上的灰度变化值。通过一个自相关函数计算灰度有明显变化的像素点位置，构造一个与相关函数相关的矩阵,通过比较构造出的矩阵的特征值可以得到相应的角点位置信息。将窗口平移[u,v]产生的灰度变化为E[u,v]，即

(1)

其中，w(x,y)表示窗口函数，向量[u,v]表示在某个方向及在其方向上的位移。I(x+u,y+v)表示唯一强度(shifted intensity)。为确定其为角点，通过公式可知，E[u,v]表示图像上某个方向上的灰度边度，要取得最大值应保证位移强度取得最大值。由

I(x+u,y+v)=I(x,y)+Ixu+Iyv+o(u2,v2)

得到

记上式最后的结果为Δ，则我们可以推出

(2)

M为2*2的矩阵可由图像的导数求得

(3)

其中，窗口函数为

(4)

这里Ix和Iy为在x和y方向上的导数，即各自方向上的梯度，w(x,y)窗口函数为高斯函数。其本质是一个椭圆的函数。椭圆的曲率大小是由M的特征值λ1与λ2决定的，所以通过比对矩阵M的特征值λ1与λ2，当两个特征值都很小时，自相关函数值在各个方向上都很小，说明高斯窗口函数中的图像灰度较为平坦；当矩阵M的特征值一个大一个小时，自相关函数值在某一方向上大，在其它方向上小，则表示检测到边缘直线；当矩阵M的特征值都很大，自相关函数值在所有方向上都增加，表示检测到了角点。这同时也是对Moravec算子边缘响应过于敏感做出了改善。

而针对矩阵M的特征值λ1与λ2大小的度量通过定义角点的响应函数CRF去衡量[1]

R=Det(M)-KTrace2(M)

(5)

其中，Det(M)为矩阵M的行列式，K通常取经验值0.04～0.06，Trace(M)为矩阵M的迹，通过角点相应函数值与选取的阈值T进行比对得到角点。

为避免K值选取的随机性，采取角点相应函数式(5)计算从而选取角点，即

(6)

1.2 改进的Harris算法

当然Harris算法也存在一定的缺陷，一方面是需要人为通过给出多次阈值，计算出图像中局部极点值即为角点，而阈值过小或过大会造成丢失与伪角点的形成，需要通过多次效果比对，选定一个较为合适的阈值才能得到预期效果角点的检测。另一方面角点的分布往往在特征值较大的某些区域，降低阈值产生角点的聚簇的现象，对后面角点的进一步提取造成一定的影响。所以本文采用徐克虎提出的一种自适应非最大抑制的Harris角点检测算法[16]，实验结果表明与CPDA共同检测特征点效果较好。

这种自适应非最大抑制的角点检测，是先对局部最大值进行从大到小的排序，在这基础上针对每一个局部最大值设定一个抑制半径r，为保证准确性该抑制最大值的c= 0.9倍大于抑制半径内的所有值时被添加进待选角点中，当得到足够数量角点时停止。

当一个局部最大值R(x,y)i为角点时，应满足

c·R(x,y)i>R(x,y)j
st(x,y)j∈(x,y)i±r

(7)

其最小抑制半径为

(8)

2 CPDA角点检测算法及其优化

2.1 CPDA角点检测的原理

采用尺度曲率空间的CSS算法，低尺度上对边缘的计算，这样对图像中局部的噪声和变化变得很敏感，会造成一定程度上的误检。在较高尺度的高斯函数进行平滑处理，取局部极大值点作为角点候选点，虽对敏感性进行了一定的缓解，但这样会造成曲线细节的丢失，造成定位不精确的问题。

一方面通过CSS算法计算量大，另一方面容易造成误差。与计算耗时的Harris算法结合起来时耗更长，所以通过计算点到弦的距离来模拟曲度，确定角点的位置，提出采用基于点到弦距离累加和的CPDA算法，如图2所示。

图2 CPDA算法点到弦距离累加和原理

边缘曲线上存在n个像素点，由P1，P2，…，Pn。从弦CL在Pk-LPk的位置开始，计算Pk到弦CL的距离记为dk,k-L，然后弦CL向曲线方向移一个像素到Pk-L+1Ck+1记为CL+1，计算Pk到弦CL+1的距离为dk,k-L+1，依次移动到弦CL在位置PkPk+L结束，求得所有距离的和，即为点Pk到弦CL的距离累加和hL(k)，求得和公式为

(9)

而定义的弦长如果太小，跨度过小会使定位角点错误，产生误检；弦长定义过大，可能存在将多个曲线峰谷描述成一个角点。所以此时CPDA定义3种不同的弦长长度L,并通过每个点3个曲度归一化，相乘获得曲度乘积项。通过曲度乘积项获取局部最大值作为候选点，首先通过获取的局部最大值与自适应的曲度阈值进行比较去除伪角点。曲度乘积项公式为

(10)

2.2 改进的CPDA算法

2.2.1 自适应曲度阈值

曲度阈值通常不稳定，所以提出与自适应局部曲度阈值进行比较，初步筛选较弱的角点。

自适应局部曲度阈值公式为

(11)

如果局部最大曲率值的绝对值小于公式的阈值，则被舍弃。其中C表示系数，当C设置为1时，说明没有角点被舍弃，为一个标准三角形角点；当C设置为2时，得到的是呈凸型的角点，为一个大曲度的圆角点；当C设置为1到2之间时，表示获取为圆角点，介于平滑与标准三角形角点之间，多适用于各类图像检测。其中K用来表示局部曲率的平均值，L1与L2为局部大小。

2.2.2 动态角点区域

由CPDA中自适应局部曲度阈值公式可知，L1到L2区域为动态角点区域(region of support)[17]，其定义为从一图像中的邻域局部曲率极小值到下一个从候选点到两端严格减少的曲率。本文提出在Harris算法检测下自适应曲率阈值的基础上，动态区域性的CPDA检测。动态角点区域针对局部细节检测精度有较大的提升,在鲁棒性上有较大的提升空间[18]。非动态的弦长，不同跨度产生的角点结果，可能存在漏检与重复检测，如图3所示。

图3 动态角点区域

其中曲线上存在5个不同曲率的标记点，在不同曲率下检出的效果不相同。当ROS设定过小时，每个标记点都会被认作角点；而当动态角点区域设定过大时，所有标记可能会被遗漏。需要动态设定检索区域范围的值，当检测标记点2的时候，应当选取标记点1到标记点3之间的区域，检测标记点3的时候应当选取标记点2到标记点4之间的区域，而不选取标记点1到标记点5之间的区域，从而造成漏检。通过这种动态角点区域选定，可以有效找到角点位置

(12)

经分析当∠Ci在160度与200度之间会从候选点中排除。

通常在CSS算法中使用动态区域方法，本文将自适应曲度阈值与动态检索角点区域的方法引入CPDA算法中，减少人为设定阈值，在一定程度上减少噪声对图像角点检测效果的影响[19]，提高了CPDA角点检测算法精度。

3 基于改进算法的图像局部细粒度特征分析

由图4可以看出，在整体中不同粒度下包含了不同层次的图像信息，在不同的定位下提取不同粒度的特征信息最终合并生成多粒度特征。

通过细粒度图像分类思想可以看出无论是在人工标注图像关键区域的强监督学习下，还是通过注意力机制的弱监督学习下，都是通过定位分类进行细小特征差分化分析。所以提出通过本文提出算法实现粗定位实现感兴趣区域的描述，针对该区域形成8*8的图像邻域，在全局中通过区域中的局部特征进行特征点定位分析。这有利于多尺度图像及细微差距特征的图像分类与识别。

图4 不同粒度下的粗定位

4 算法及流程

主体是通过文献提及的自适应非最大抑制的Harris算法检测出可能存在的角点，包含大量伪角点及重复角点，基于这些候选角点通过改进的CPDA算法的曲率自适应比较变换计算进行再次筛选，最终得到准确的区域，在该区域内进行特征点的定位分析。

(1)通过角点响应函数计算每个像素的响应值，获得初次筛选下的局部最大值点，记录相应坐标及编号。

(2)针对所有局部最大值点进行由大到小的顺序进行排序，相同的值时依据初次筛选下记录的编号进行排序。

(3)根据设定的最小抑制半径r逐渐缩小半径，对已有排序后的局部最大值进行二次筛选，得到非最大抑制下的第二次筛选下的候选角点。

(4)应用Canny边缘检测算子得到图像边缘，填充曲线边缘缝隙，检测出T型角点，加入第二次筛选的候选点中。

(5)将二次筛选的候选点与T型角点通过曲度乘积公式计算曲率与自适应曲度阈值进行比较去除圆角点，得到第三次筛选结果。

(6)将第三次筛选得到得候选角点通过动态区域比对进行角度阈值比较，删除错误角点。同时对欧式距离小于25像素的近邻T型角点进行删除操作，符合则并入正确角点集合中，得到最终的特征区域。

(7)经过该算法图像已经得到特征点的粗定位，将粗定位候选区域作为网络的输入端，在当前像素区域进行局部的特征学习，经过多粒度的网络得到融合特征。

5 实验结果及性能评价

相关算法实验采用Windows XP系统，处理器为Intel(R) Core(TM) i5，2.60 GHz,可用内存为3.26 GB。本文算法基于改进的Harris-CPDA算法主要与典型Harris算法、非极大抑制下的Harris算法、CPDA算法进行实验结果与性能评价。经典的Harris算法与CPDA算法在不同的阈值区间下检测效果各不相同，所以通过设置3种不同的阈值区间[0，20]、[20，50]、[50，80]与本文算法进行实验比对。实验图片方面，图片工件选择单个工件，单个工件不同种类与多种类工件混合进行对照实验。

5.1 检测性能评估

角点检测的评估，本文首先依据Mokhtarian提出的角点数一致性(consistence of corner numbers，CCN) 的概念[20]

CCN=100%×1.1-|Nt-NO|

(13)

其中，CCN数值越大，表明角点检测效果越好。基于式(13)基础上，提出3种不同点的检测效果，正确检测、误检测、漏检测。其中Nt为变换后检测角点数目，Nc为原始图像检测角点数目。而人为选取特征点并不具有客观性，所以Awrangjeb等提在CCN基础上提出平均重复率(ave-rage repeatability)与定位误差(localization error)[21]

(14)

(15)

其中，Nm为图形变换前后都存在的特征点，(xoi,yoi)和(xti,yti)为变换图像与原图像相应角点的坐标位置，相差3个像素以内为匹配的特征点。

5.2 多阈值实验分析

这里以图5中3幅实验图片为例，选取单一不同种，与多种模型混合情况实验。

图5 算法测试实验用图

这里依据CCN式(13)及准确率式(14)与定位误差式(15)提出，在准确角点范围内，合格率是指在检出角点中有效角点所占实际角点的比例，漏检率是指未检测出来角点的比例，误检率是指多余的干扰点与重复点的比例。

通过实验分析，由其不同阈值下的数据如表1所示可以直观发现，Harris算法在阈值为[0.2,0.5]区间内效果最佳，中间阈值强度在合格率方面介于其它两种阈值中间，漏检率与误检率也处在中间，相对其它两种阈值强度较为均衡。所以确定Harris算法在该区间与本文算法进行比对。同样CPDA算法在canny算法边缘检测中选取阈值范围在[0.2,0.5]取得较好的结果，其数据见表2。

5.3 传统算法对比结果

通过图6(a)、图6、(d)、图6 (g)可以看出，Harris算法检测出来点的数量很多，但相应存在很多误检与漏检的特征点；而图6(b)、图6(e)、图6(h)CPDA算法在曲率确定上带有模糊性，大曲率与小曲率是否划定为特征点为漏检的主要原因；本文算法完善了Harris与CPDA算法的缺陷，在特征点检测上有良好效果。

表1 Harris算法多阈值分析/%

表2 CPDA算法多阈值分析/%

而从局部图7来看，图7(b)、图7(c)相应的Harris算法检测伪角点仍旧过多，其基于灰度在灰度变化区域敏感，容易认定为角点；图7(d)、图7(e)基于曲率的CPDA算法在工件内部的特征点检测并不敏锐；图7(f)为提出的算法,其检测特征点准确，同时在工件内部检测表现良好。

从实验结果数据与实验结果图来看，可以看出Harris算法在检测方面，倾向于大而全，在角点检测数量上较多，非常全面，细节上也会采用较多角点去表示，因为数量较多所以存在较少的漏检角点，但同时带来的是一个特征用多个重复角点表述；典型的CPDA算法针对边界检测效果相对于Harris算法较好，但其多受限于边界的阈值效果，对于工件的内部细节特征找的不够详细，同时也受限于检测步长，跨度大小不能适应性调整也是局限了多尺度下的角点检测，在圆角点的区分还是相对模糊。

通过表3与表4分析可以看出本文算法在保证检测角点正确数量的同时，针对Harris系算法在CCN计算下合格率上有7%的提升，漏检率提升30%，误检率方面也有50%以上的提升，在CCN计算上的准确率上更有40%的提高，定位误差减少了0.3个像素；针对CPDA算法来看有小幅提升，着重在特征点的漏检率方面有了40%以上的提升，误检率上30%的提升并降低了特点的定位误差。而通过表5可以看出比Harris系算法时间提升0.8 s，比CPDA算法花费时间小幅降低。在改善相应的缺陷同时，在时效上比Harris系算法与CPDA算法有了较大的提升。

图6 整体检测效果展示

图7 局部检测效果展示

表3 角点CCN检测数据对比/%

表4 角点检测重复率与定位误差数据对比

表5 算法运行时间(以图6为例)

5.4 多粒度下的实验对比结果

为方便观察，选取图5(a)中的轴类零件及相应自标定数据集，经过校正之后原图像通过本文提出的改进Harris-CPDA算法生成一个特征点的粗定位，针对不同的关注度得到不同细粒度下的特征信息，相比于强监督学习，减少人为标注同时提高准确度。本文选取与Part-based R-CNNs进行对比性实验，针对这种强监督学习可以分为两部分定位与识别，其在大规模数据集中有良好的表现，而在工业上数据集较少，两者选取自标定数据集进行测试。

从图8(a)、图8(c)可以看出Part-based R-CNNs算法存在框选错误，光线及角度的改变对其判定产生一定的干扰，致使误差；相比与本文提出的算法图8(b)、图8(d)与深度学习有很好的结合性，对于不同场景下的检测，有较强的鲁棒性。

图8 本文算法与Part-based R-CNNs效果对比

定位上来说Part-based R-CNNs的Selective Search会在一张图片生成较多的候选区域，会产生大量的无关区域,增加了运行时间，同时定位的准确程度是建立在多候选区域之上，与本文提出算法相比并不理想,通过表6与表7可以看出，相比于有Bounding box的基础上,定位的准确性上提升了16%左右。针对于分类在准确性上也有近5%的提升。为了展示分类效果选取环类工件，展示定位效果以轴类零件展示，如图8，针对环型工件区分内外环分类定位，对于轴类工件以特征区域及整体进行分类定位。

表6 与Part-based R-CNNs定位数据对比

表7 与Part-based R-CNNs分类数据对比

6 结束语

本文首先介绍了基于两种不同方法角点检测算法的基本构成及现状，针对Harris算法采用文献提及的非最大抑制的方法进行处理，一定程度上减少阈值强度对其影响，此时检测角点重复点数量较多，存在一定的误检点。同时针对CPDA算法提出自适应曲率阈值的方法，去除圆角点，而针对相对单一化的步长，不能检测多尺度下的角点，采用动态角点区域的方式不断迭代排除伪角点。

而通过本文提出的基于灰度与基于曲率的两种角点检测结合提出改进的Harris-CPDA算法。实验结果表明在保证较多的正确角点检测的前提下，减少了单一位置重复的特征描述，相比于Harris算法与CPDA算法在检测精度方面有了较大的提升。而通过传统方法针对图像进行粗定位，与图像的细粒度的结合，使图像在多尺度与监督学习方向上的微小特征的定位有了进一步的提升，这种融合提升了特征的表达能力。