基于自适应阈值的FAST特征点提取算法

丁尤蓉，王敬东，邱玉娇，俞海波

(南京航空航天大学自动化学院，江苏 南京 210016)

数字图像处理领域中，特征点是图像非常重要的一个局部特征，它集中了图像中很多的形状信息，反映的是二维图像上亮度变化剧烈的点或图像边缘曲线上曲率极大值的点［1］等。所以特征点提取在目标识别、图像匹配、图像重构方面等领域有着广泛的应用。

特征点提取的方法有很多种，如Plessey提取算子和SUSAN提取算子等。最近几年在这些经典的特征点基础之上，出现了大量新的算法，并且算法研究也很火热，如2004年Lowe［2］提出了尺度变换不变特征提取算子，2006年Bay等人提出了SURF［3］提取算子。本文对其中较新的FAST(Features from Accelerated Segment Test)特征点提取算法进行了深入研究与分析。FAST算法［4］是一种简单快速的特征点提取算法，在2008年至2010年期间由 Edward Rosten，Reid Porter和 Tom Drummond提出的一种新式特征点检测算法。FAST算子由于快速性被广泛应用于实时系统中，但也存在着一些缺陷。由于图像中存在阴影和照度不均匀等因素，导致图像各处的对比度不同时，FAST算法的稳定性不高，适应能力差，并且提取的结果会出现多个特征点块［4］。针对这些缺陷本文对算法进行了改进，采用了动态全局阈值和动态局部阈值的方法来增强算法的稳定性和适应能力，并采用非极大值抑制法达到抑制多个特征点块的目的。实验表明，改进后的FAST算法效果显著。

1 优化的FAST特征点提取算法

1.1 FAST特征点提取算法

FAST算法检测的特征点定义为在像素点的周围邻域内有足够多的像素点与该点处于不同的灰度区域［4-6］，即有足够多的像素点的灰度值大于或者小于该点的灰度值。如图1所示，任取一像素p点，以其为中心形成一个圆形区域(半径等于3的离散化的Bresenham圆)，则中心像素p点被16个像素点包围。在16个像素点形成的圆周上，如果存在n个互相邻近的像素点的图像灰度值都大于I(p)+t，或者都小于I(p)－t(其中I(p)为p点的图像灰度值，t为阈值)，则该圆的中心像素点p为候选特征点。

文献［4］中提出，当n取12时，通过以下算法可以迅速排除大量的非特征点。算法步骤如下。

1)首先计算中心像素p点与圆周上的像素1和像素9的图像灰度差值(ΔI1和ΔI9)，若ΔI1和ΔI9的绝对值都小于阈值t，则该像素点p为非特征点，否则像素点p为候选特征点，算法继续执行。

图1 特征点检测模板示意图

2)计算中心像素p点与圆周上的像素5和像素13的图像灰度差值(ΔI5和 ΔI13)，若ΔI1、ΔI9ΔI5和ΔI13其中至少三项差值都大于阈值t或者都小于 －t，则像素点p为候选特征点，算法继续执行，否则该像素点p为非特征点;

3)按照步骤1)和2)的判断标准继续执行，直到检测完圆周上16个像素点。

上述方法中，无需将圆周上的所有像素点都与中心像素点比较，即可迅速排除大量非特征点，降低算法的时耗。但是同时算法也存在缺点:1)对于不同条件下得到的图像，它们的对比度和噪声情况有差异，因此选取阈值应该不尽相同，若采用固定阈值会导致算法的鲁棒性差;2)算法计算时，由于真实特征点附近像素点的性能和真实特征点的性能相像，所以会把这些点当成特征点检测出来，从而产生了特征块，使得特征点的聚集率很高，降低了算法的应用性能。

1.2 动态全局阈值T1的确定

FAST算法中，阈值表示所能检测到的特征点的最小对比度，也是能抵抗的噪声的最大容限。阈值选取的好坏决定了提取角点的结果。阈值越大，检测到的角点越少，反之，就越多［7］。虽然采用固定阈值计算简单，但是不能满足不同图像的特征点抽取要求，所以本文首先采用了动态设置全局阈值T1的方法对原始灰度图像进行初步特征提取。

全局阈值T1的选取应能随着图像全局灰度分布的变化而合理地变化，适应不同图像的特征点提取要求。文中具体采用了KSW熵方法来获得图像的全局最佳阈值T1。KSW熵方法是由Kapur等人提出，通过研究图像灰度直方图的熵，利用条件概率描述图像中目标与背景的灰度分布，并据此定义目标与背景的熵[8]。

KSW熵方法主要分为两个步骤。首先以图像的灰度直方图作为灰度值的概率分布密度函数的一个近似估计，然后利用此密度函数结合熵的原理构造了目标函数，从而实现阈值的选取。此方法是以灰度直方图即以各灰度值出现的频率来近似估计灰度值的概率分布，包含了图像的全局灰度信息，这样使得阈值可以随着图像灰度分布不同而合理地变化，使得最终特征点提取算法的适应性增强，满足不同图像的特征点抽取要求。KSW熵方法结合熵的原理，图像的熵表示图像平均信息量，熵值越大，表明此时获得的信息量越大。由于特征点为灰度变化剧烈的点，包含了大量的信息，因此通过图像熵可以获得可靠的最佳阈值。

设阈值t将灰度范围为［0，L－1］的图像划分为两类 S1和 S2，S1和 S2分别为［0，t］和［t+1，L － 1］的像素频率分布。则 S1={p0，p1，p2，…，pt}，S2={pt+1，pt+2，pt+3，…，pL－1}，其中 pi为各灰度级出现的频率。令 Pt=，则 S1和S2的熵S1和S2分别为:

则图像的熵S为S1和S2之和，即S=S1+S2。根据上述描述和推论，在灰度差梯度图的灰度级范围内遍历计算每一个t，计算两部分的熵，最后得出熵之和最大的对应的那个灰度级记为Tmax，熵之和最小的那个灰度级记为Tmin。则最佳全局阈值T1为

其中，k为比例系数，由于特征点阈值与图像的对比度相关，因此通过KSW熵方法确定图像灰度级差，即最佳全局阈值T1。设图像上某个像素点(x0，y0)，只有当该象素点的Bresenham圆周上存在n(n=12)个像素点的灰度值都大于 I(x0，y0)+T1，或者都小于I(x0，y0)－ T1(其中 I(x0，y0)为图像上坐标为(x0，y0)点的图像灰度值，T1为全局阈值)，该像素点(x0，y0)为候选特征点，否则该点就不是特征点。

1.3 动态局部阈值T2的确定

采用KSW熵方法确定的全局阈值虽然能随着图像全局灰度分布的变化而合理地变化，满足不同的图像对阈值的要求，但是它和图像的全局灰度分布相关不能适应图像局部的灰度变化。当图像中由于存在阴影，照度不均匀，突发噪声和背景灰度变化等因素，导致图像各处的对比度不同，如果只用一个动态的全局阈值对整幅图像进行特征提取，则不能兼顾图像各处的情况而使提取效果受到影响，提取的结果会产生错误的特征点。所以必须对利用动态全局阈值得到的候选特征点进一步判断筛选，本文采用了设置动态局部阈值T2的方法对候选特征点进行进一步筛选。

本文分析了图像灰度值的对比度，提出图像不同区域L下局部阈值T2的自适应取值方法，设图像上(x0，y0)点为候选特征点，以(x0，y0)为中心取方形区域的边长为L，定义动态局部阈值T2为

式中，Iimax和Iimin(i=1，2，…，n)分别代表方形区域L中最大的n个灰度值和最小的n个灰度值，Iiaver为方形区域L的灰度平均值。令Δ=，则Δ为对比度，由于FAST算法的本质就是对相邻像素对比度的衡量，因此本文的局部阈值采取与图像局部的对比度相关(成比例关系)。经实验，比例系数k，一般取2～4。这样候选特征点通过局部阈值进一步筛选，使特征点提取更稳定。只有当候选特征点(x0，y0)的Bresenham圆周上存在n个(n=12)像素点的灰度值都大于I(x0，y0)+T2，或者都小于I(x0，y0)－T2(其中I(x0，y0)为图像上坐标为候选特征点(x0，y0)的图像灰度值，T2为局部阈值)，则保留该候选特征点(x0，y0)，否则舍弃该候选特征点。这样有利于筛选掉一些虚假特征点，使特征点提取更稳定。

1.4 非极大值抑制法

经过全局阈值T1和局部阈值T2的筛选，得到了候选特征点，但是这时的特征点在图像的一些区域会出现聚集现象，形成边缘点和多个特征点块。所谓特征点块是由于真实特征点附近像素点的性能和真实特征点的性能相像，所以会把这些点当成特征点检测出来，从而产生了特征块。实际上特征点应当是具有较大灰度变化的区域中心，在一个小区域内不可能全是特征点，所以必须对候选特征点进一步判断筛选。

本文采用非极大值抑制法进行进一步筛选，对于每个候选特征点p，都存在着固定的临界阈值εt，即当判断阈值t为临界阈值εt时，该候选特征点p周围的像素点满足判定标准的像素点的个数N刚好为12。简言之，该临界阈值εt使候选特征点p处于特征点和非特征点的分界上。经分析可知，对于任一候选特征点p，其临界阈值εt越大，该候选点的强度越大，是特征点的可能性也越大。本文通过计算每个候选特征点的临界阈值εt，利用εt参与局部非极大值抑制。具体步骤如下。

1)通过迭代和线性插值求出候选特征点pi的临界阈值εti，此时候选特征向量包含三种信息(x，y方向坐标和临界阈值 εti)，即 pi(xi，yi，εi);

2)分别比较 pi(xi，yi，εi)与其局部候选特征点p1(xi－1，yi，ε1)，p2(xi+1，yi，ε2)，p3(xi，yi－1，ε3)和 p4(xi，yi+1，ε4)的临界阈值，若 εi＞ε1，ε2，ε3，ε4，则剔除局部候选特征点 p1、p2、p3和 p4。

2 实验结果及分析

2.1 不同特征点提取算法性能对比

针对本文叙述，实验选取了同一场景不同对比度的图像进行实验。如图2所示，图(a)为实验原图，图(b)在图(a)的基础上加强了整个图像的亮度，图(c)在图(a)的基础上改变了图像局部的亮度。图3为其对应的灰度直方图，直方图上不同区间上用不同的灰度信息表示被统计图像中对应灰度的分布情况。从灰度直方图中可以看出图(b)在图(a)的基础上减少了图像对比度，图(c)在图(a)的基础上改变了图像的整个对比度。本文分别对SIFT算法、优化前的FAST算法和优化后的FAST算法的特征点提取效果进行对比。

图2 实验图片

图3 灰度直方图

三种算法的提取效果如图4所示，算法提取到的特征点图中用十字标出。SIFT算法速度较慢，并且在图(b)和图(c)明显存在特征点提取错误的现象，如:屋顶、烟囱和天空部分。特别是天空部分，图中已用框标志出明显的错误提取。FAST算法提取速度虽然很快，但很容易形成特征点聚集的现象。如图4(2)中的图(b)和图(c)的烟囱、屋檐、屋角部分明显的出现错误的特征点聚集现象，已用框标志出来。优化后的FAST算法有效地抑制了错误的特征点聚集现象(如烟囱、屋檐、屋角部分)，而且在原本特征点分布密集的部分也能实现较多的特征点提取(如房檐部分)，当同一场景图像的全局对比度或者局部对比度变化时，优化后的FAST算法的适应性较强，稳定性较高。

图4 不同算法的测试效果

定义两个指标重复度r和聚集度c，实验中取同一幅图像以及其变化后图像，假设在原图像上提取的特征点总数记为N1，在变化后图图像上提取到的特征点总数记为N2，在变化后图像上得到的所有特征点中与在原图像上提取的特征点相重合的个数记为Nr，则重复度，即重复度越大，算子的稳定性越高;聚集度就是衡量边缘点或者特征块被误检为特征点的一个指标，同时也反应了特征点在图像中的分散程度。设N为图像中抽取出的特征点数，Nc为特征点周围聚集超过3个的特征点总数，则聚集率100%。实验数据如表1所示。

表1 特征点算法性能对比

通过表1和图4可以直观地看出优化后的FAST算法重复度高、聚集度低。从表1的算法耗时数据可以看出，FAST算法提取速度非常快，由于本文针对FAST算法的一些缺点进行优化，因此增加了算法的一些复杂度和耗时量，但是相比于SIFT算法，优化后FAST算法的特征提取算法还是很快，满足实时系统的需求。

2.2 FAST算法优化前后实验结果分析

为了进一步验证本文优化后的FAST算法对不同光照和对比度情况下具有一定的适应能力，实验选取了两组图像序列进行实验，一组图像序列为在实验原图的基础上逐渐递增和递减(步长为5%)图像的亮度，该组图像序列中的一些实验图像效果如图5和图6所示，图5为原FAST算法提取效果，图6为优化后的FAST算法提取效果;另一组图像序列为在实验原图的基础上逐渐递增和递减(步长为5%)图像的对比度，该组图像序列中的一些实验图像效果如图7和图8所示，图7为原FAST算法提取效果，图8为优化后的FAST算法提取效果，从以上效果图中可以直观地看出改进后的算法的稳定性高，避免了大量特征点聚集的现象。

图5 亮度逐渐变化的FAST算法提取效果

图6 亮度逐渐变化的优化后FAST算法提取效果

为了更方便地对优化前后的FAST算法性能分析，本文根据前面定义的重复度r和聚集度c两个指标，对实验的两组序列图像进行重复度和聚集度计算，并且描绘出曲线，如图9和图10所示。其中，图9为亮度逐渐变化序列图像中FAST算法优化前后的重复度和聚集度曲线。其中，横坐标为在实验原图的基础上的亮度变化率，纵坐标分别为重复度和聚集度。图10为对比度逐渐变化序列图像中FAST算法优化前后的重复度和聚集度曲线，其中横坐标为在实验原图的基础上的对比度的变化率，纵坐标分别为重复度和聚集度。通过图9和图10的曲线，可以发现优化后的FAST算法聚集度小于FAST算法，很好地克服了FAST算法聚集度高即存在大量特征点块的缺点。同时，当同一场景的图像的亮度和对比度逐渐变化时，优化后的FAST算法的重复度大于FAST算法。可见，相比于FAST算法，优化后的FAST算法稳定性好，对不同光照和对比度情况下有一定的适应性。

图7 对比度逐渐变化的FAST算法提取效果

图8 对比度逐渐变化的优化后FAST算法提取效果

图9 亮度变化序列图像中算法的性能指标对比

从以上的实验分析可以发现，相比于FAST算法，优化后的FAST算法稳定性较好，不易产生特征点块并且对不同光照和对比度情况下有一定的适应性，同时相比于其他算法，算法的提取速度仍然较快，适应实时系统的需求，算法的综合性能得到了很大的改善。

3 结束语

本文采用动态全局阈值、动态局部阈值和非极大值抑制方法，改进了FAST特征提取算法，实验证明优化后的算法性能得到了提高，效果良好，尤其适用于对系统实时性和稳定性要求较高的场合。当场景的光照和亮度发生变化时，使用该算法，仍能实现稳定可靠特征提取，为后续特征点应用处理工作，打下坚实的基础。

图10 对比度变化序列图像中算法的性能指标对比

［1］赵文彬，张艳宁.角点检测技术综述［J］.计算机应用，2006(10):17-19.

［2］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，2(60):91-110.

［3］Bay H，Tuytelaars.T，Gool L.Surf:Speeded up robust features［C］.European Conference on Computer Vision，2006，3951:404-417.

［4］Rosten E，Drummond T.Faster and better:a machine learning approach to corner detection ［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2010，32(2):105-119.

［5］LEPETIT V，FUA P.Keypoint recognition using randomized trees［J］.IEEE Trans on PAMI，2006，28(9):1465-1479.

［6］ROSTEN E，Drummond T.Fusing points and lines for high performance tracking［C］.IEEE International Conferenceon Computer Vision，2005(2):1508-1515.

［7］刘波，仲思东.一种基于自适应阈值的SUSAN角点提取算法［J］.红外技术，2006，28(6):331-333.

［8］孙文昌，宋建社，杨檬，等.基于熵和独特性的角点提取算法［J］.计算机应用，2009(29):225-227.