基于kd曲率的自适应支撑邻域角点检测

兰国清，胡旭晓，王永力，吴跃成

(浙江理工大学 机械与自动控制学院，浙江 杭州 310018)

在整个计算机视觉和图像处理过程中，图像的特征提取与匹配是最基本的处理方法[1-3]，已经广泛应用于全景拼接、三维匹配、目标跟踪等场合[4-8].而角点是图像特征的重要部分，它既保留了图像的重要信息，又减少了大量的数据，在当前大数据时代，扮演着越来越重要的角色，并且角点在图像仿射变换和噪声环境中具有相对稳定和不变性.计算机视觉领域的许多学者对特征提取和匹配问题已经进行了深入研究.现有的角点检测算法一般被分为3类：第一类是利用角点附近灰度值变化剧烈这一特点提出的算法，即基于梯度的角点检测方法，其经典算法主要有Moravec算法[9]、Harris算法[10](1977年Moravec发现在角点附近图像的灰度值变化很大，利用此特点提出了一种角点检测方法；Harris则是对此算法进行改进，通过局部自相关矩阵来区分角点和非角点)；第二类是用已有模板与图像上小区域进行匹配的算法，即基于模板的角点检测方法(Smith和Brady利用圆形模板于1997年提出了SUSAN检测算法[11])；第三类是利用轮廓上曲率极大值点进行阈值处理的算法，即基于轮廓的角点检测方法.此类方法包括k-cosine方法[12]、CSS角点检测方法[13]、ANDD角点检测方法[14]、KD曲率角点检测方法[15]等.其中，基于曲率尺度空间(CSS)的角点检测器应用较多.该算法主要是提取好的边缘轮廓曲线，对曲线进行大尺度的高斯核平滑处理，并分析曲线的极大值点，找出候选角点，然后通过小尺度进行定位跟踪.2013年Shui P L等提出利用各向异性高斯方向导数(ANDD)对角点进行提取与分类[14].2016年Chen S T等提出KD曲率焦点检测算法，通过曲线融合填补提取高质量的曲线，经高斯平滑处理，确定固定的支撑邻域和阈值，然后根据kd曲率含义进行曲线的曲率估计，将局部曲率最大值大于阈值的点作为候选角点[15].该方法中支撑邻域是固定的，这就意味着数字化曲线上相邻的两像素之间距离是固定的，从而在评估各角点强度时能够保持标准一致，但是现实中相邻像素之间的距离并不是固定的，如在研究机器人自主定位与导航的过程中，每帧图片都会发生旋转并可能受到噪声干扰，每条曲线上的像素点都会发生变化，即固定像素点个数对应着不同的曲线段，因此该算法会丢失许多角点，同时抗噪和抗旋性能不佳.

本文在KD曲率角点检测算法的基础上，提出一种基于自适应支撑邻域的角点检测算法，通过自适应阈值提取候选角点，并进行非极大值抑制，选出角点集，以期提高算法的抗噪、抗旋性能.

1 离散kd曲率的提取

Borrelli V等提出的曲率计算方法是针对连续型曲线的[16]，而数字化图像上都是离散的像素点.因此，该方法需作修改才可能适用于图像的角点提取.

1.1 连续曲线的kd曲率计算

假设连续曲线为Γ，pi是曲线上的一个点.以pi为原点建立坐标系，则曲线上的点坐标pi(x,y)如图1所示.由泰勒展开式得：

(1)

式中：y″(0)=k；y‴(0)=v；o(x3)为x3的高阶无穷小.假设pi点的y′(0)=0,则有极坐标：x=ηcosθ和y=ηsinθ.

图1 连续曲线上的点坐标

由隐函数定理[17]得：

(2)

(3)

式中，kd(pi)为pi点曲率，即kd(pi)=k.

由式(3)可知，在同一支撑邻域内，曲率越大的点，其αi值越小.

1.2 离散曲线的kd曲率计算

由于图像上像素是离散的(图2)，因此需要修改式(3)，使其能用于图像的曲率计算.

注：ros为支撑邻域.图2 离散型曲线

设pi-1=(xi-1，yi-1)，pi=(xi，yi)，pi+1=(xi+1，yi+1)，则ηi-1=(xi-1-xi，yi-1-yi)，ηi+1=(xi+1-xi，yi+1-yi)，αi=arccos[(ηi-1ηi+1)/(ηi-1ηi+1)](这里,ηi-1和ηi+1分别为ηi-1和η+1对应的向量),得:

(4)

2 支撑邻域的选取

为了区别传统的支撑邻域[18]，本文提出自适应支撑邻域检测思想，即采用一条曲线上总体支撑邻域来计算该曲线上各离散点、曲率所需的支撑邻域.当图像发生仿射变换或者受到噪声干扰时，根据曲线变化确定新的支撑邻域.为找出一个可以描述曲线变化的参数，当图像变换后，此参数仍能反映这条曲线的曲率变化趋势，本文做了进一步研究.

假设轮廓曲线Γ是以弧长s为参数的函数：

Γ=(x(s),y(s))

(5)

用高斯核g(s,σ)对轮廓曲线进行卷积运算，有：

(6)

则：

Γ={X,Y}

(7)

(8)

通过大量实验发现，kd曲率和Kros值变化趋势大致相同.对一条轮廓曲线(图3)进行仿射变换，在支撑邻域为8的情况下，它的kd曲率、Kros值变化如图4所示.

图3 积木图及其一条轮廓曲线

由图4可看出，即使对图像做不同处理，Kros值与kd曲率变化趋势也基本相同.从数学角度不难证明，Kros值与kd曲率存在相关关系.因此，通过Kros值可确定支撑邻域的长度.因kd曲率局部最大值对应于候选角点，所以Kros值局部最大值也对应于候选角点.本文首先提取Kros局部最大值，并进行阈值处理，统计满足要求的Kros值个数，然后通过不断调整参数得出最终阈值Tthred，最后计算出支撑领域.其具体步骤如下：

注：sx、sy均为缩放尺度.图4 轮廓曲线的kd曲率与Kros值

(1) 选取初始阈值t0=0.030 9;

(2) 通过t0，选取Kros大于t0的局部最大值，并且将最大值个数记为N；

(4) 判断N是否大于n，若大于n，则t=t0+Δt，返回(2)；

(5) 若t>0.082 3，则退出循环，取最后t值为最终阈值，即Tthred=t；

(6) 轮廓曲线的支撑邻域为：

(9)

式中：round为取整函数；c为常量.

3 候选角点阈值的获取

由式(3)可知，kd曲率大小取决于α角，而α的大小取决于Lros.根据文献[15]，对于不同的α和Lros值，kd曲率也不同(表1).

表1 不同支撑邻域Lros和α角对应的kd曲率

(10)

(11)

从表1可知，Lros值一定时，α越大，则kd曲率越小.本文提出的Lros是自适应变化的，针对不同曲线，有不同的Lros值，但是同一条曲线的Lros值是固定的.如果一条曲线上出现几个α角点，为了筛选真角点，则可设置阈值为：

(12)

式中，kthred为阈值.

以上即为本文提供筛选不同角点强度的方法.

4 新的角点检测算法

以式(9)获取每条曲线的Lros值后，计算每条曲线的kd曲率，通过式(12)确定真角点的阈值，从而克服KD算法中Lros值固定不变时，提取真角点阈值固定不变的缺陷，在此基础上提出新的角点检测算法.

提取边缘曲线后进行高斯核平滑处理，能够降低曲线附带噪声以及曲线局部变化对检测结果的影响.本文通过一次高斯平滑，用kd曲率来估计平滑后曲线的曲率，以大于阈值的局部最大值对应候选角点，进行非极大值抑制，从而去除伪角点.

(1) 根据文献[19]，用Canny算子进行边缘检测.

(2) 对提取的边缘曲线进行填补、融合，以提高边缘曲线的质量.受强噪声干扰以及利用Canny算子提取曲线本身缺陷的影响，提取曲线可能较短，而高斯卷积对短的边缘曲线来说比较困难，因此需要去除短的曲线.当曲线长度m满足下式：

(13)

式中：w和h分别为输入图片的宽和高，ε是一个参数.那么，可认为应该去除曲线.依据该原则提取高质量的曲线，加快了后续算法的速度；同时，本文还应用了T角点融合技术[15].

(3) 根据高斯卷积的需要，将边缘曲线状态分为两种loop、line[20].若曲线的第一个像素和最后一个像素之间的距离小于6个像素则认为是loop型曲线，其他的则属于line型曲线.

(4) 由于噪声对曲率的计算有很大影响，因此可用高斯核对边缘曲线进行平滑处理，较长曲线用大的尺度，相对短的曲线用小的尺度[15].但是若尺度σ太大或者太小，则平滑处理中会丢失角点，对噪声抑制能力较差，而且，曲线高斯平滑会使角点定位产生一定的误差.因此，选择合适的σ既能减小定位误差，也能够去除曲线局部变化对计算的不必要影响.σ的选取采取以下规则：

(14)

σ=1时，曲线的平滑处理效果不佳，需要设置理想的阈值来去除错误角点.

在计算kd曲率之前，需要确定Lros值.文献[15]中直接以一个固定的Lros来计算kd曲率.这种方法很容易丢失角点个数，并且抗旋性能不太好.本文首先确定每条曲线的Lros值，然后通过式(4)计算出kd曲率，利用式(12)并设置不同α0值(如α0=155°)来确定阈值kthred，最后，曲线上α≤α0的局部最大值通过该阈值即可被筛选出来.但是筛选出的局部最大值角点可能是错误或者比较弱的角点.因此，对这些局部最大值进行非最大抑制处理，可消除一些伪角点.从图4(c)—(f)中可以看出，对于真角点，它的kd曲率较大，对于伪角点则kd曲率很小.通过阈值处理和非极大值抑制，可以快速得到真角点.

新的角点检测算法流程如图5所示.

图5 新的角点检测算法流程

5 仿真实验与性能分析

5.1 实验步骤

任何非平移仿射变换都可以分解为旋转、均匀缩放和非均匀变换.本文算法与KD角点提取算法、ANDD角点提取算法、CPDA角点提取算法[21]、Harris角点提取算法、ATCD角点提取算法[22]进行了实验比较.实验中使用10幅图像处理经常使用的积木图、实验室图、房子图等图像.对这10幅图像进行高斯噪声实验和仿射变换[23]，具体步骤如下：

(1) 对原图进行旋转变换，在[-90°,90°]范围内进行旋转，旋转间隔为10°；

(2) 对图像进行非一致尺度变换，sx=1，sy的值在[0.5，2.0]之间变化，间隔为0.1；

(3) 对图像进行一致尺度变换，即sx=sy，并且它们的值在[0.5，2.0]之间变化，间隔为0.1；

(4) 对图像添加高斯白噪声.

5.2 实验评估方法

为了确定算法的鲁棒性，需要对实验进行评估，本文采用文献[24]的方法进行评估，计算重复率和定位误差.测试图像和原始图像之间的角点重复率为：

Rav=Nr/2×(1/N0+1/Nt)

(15)

式中：N0为原始图像中检测到的角点数；Nt为图像变换后检测到的角点数，Nr为原始图像变换前后检测到的角点重复数.

Rav反映了仿射变换下或者高斯白噪声下的角点检测算法的稳定性.平均重复率越高，角点检测算法鲁棒性越好.

定位误差为：

(16)

5.3 参数的选择

表2所示为每阶段实验得到的参数.

5.4 实验结果

采用本文算法进行角点提取的实验结果如图6所示.通过5种算法(即：Harris、He&Yang[25]、ANDD、ATCD、本文算法)，在有噪声和无噪声的情况下测试积木图和实验室图像角点错误率和损失率的实验结果如图7所示.角点错误率和损失率分别指错误角点与丢失角点占总角点的百分比.

表2 实验参数表

图6 实验室图像角点提取结果

从图7可以看出，在无噪声的情况下，He&Yang算法错误率最高，本文算法错误率最低；在损失率方面，Harris算法最高(其主要原因是此算法需要利用图像的灰度信息)，而本文算法中等.在有噪声的情况下，Harris算法错误率很高，对噪声比较敏感，而本文算法错误率最低.综合来说，本文算法最优.

几种算法实验室图和积木图有无添加高斯白噪声的情况下定位误差如图8所示.从图8可以看出，Harris算法在有无噪声干扰下定位误差都很大，添加噪声情况下，本文算法相比于其他算法的定位误差最小，算法性能良好.

几种算法的平均重复率如图9所示.从图9可以看出，各种算法的平均重复率都很好，在图9(a)中，随着尺度慢慢变大，其平均重复率先增大后减小，同时也可以看出本文的算法有着更好的重复性能；图9(b)表明了在非一致尺度因子中，本文算法的平均重复率比较高，而且相对稳定；在图9(c)中，在顺时针旋转时，随着角度的增加，平均重复率减小，当旋转角度超过40°时，平均重复率开始增加，逆时针变化情况与顺时针大致相同，而在这几种算法中，Harris算法上下波动比较大，但是总体上看要好于CPDA算法、He&Yang算法，而KD算法与本文算法处于同一水平，都优于其他算法.

图7 错误率和损失率折线图 图8 几种算法的定位误差

图9 几种算法的平均重复率

5.5 性能分析

从实验结果可知，许多算法的平均重复率相对稳定，这意味着用现有许多角点检测算法检测到的角点还是很稳定的，但是对于一些比较复杂的曲线，可能会检测到伪角点或者丢失角点，而本文提出的算法能够在很大程度上降低错误率和损失率且能够提高重复率.本文提出自适应支撑邻域，并确定一个良好的全局kd阈值，使算法具有良好的抗噪和抗旋转性能，且有较高的平均重复率.

6 结束语

本文提出了自适应支撑邻域的角点检测方法，使用kd曲率对轮廓曲线进行曲率估计，计算简单、快捷，能够加快算法速度.通过大量实验，检测图像仿射变换下算法的检测能力，如计算定位误差、平均重复率以及错误率和损失率.实验表明，本文算法具有良好的性能，能够与现阶段一些优秀角点检测算法媲美.本文提出的自适应支撑邻域技术，结合kd曲率以及融合曲线技术，采用自适应阈值提取角点，避免了许多伪角点.但本文自适应支撑邻域还缺少严格的数学证明，只是经验公式.因此，在下一步研究中，将着重从数学角度进行分析，最终提高算法的鲁棒性，使算法进一步优化.