首页
登录 | 注册

特征点检测FAST算法

1.FAST基本算法

用一句话来讲FASTN算法的原理就是:若一个像素周围有一定数量的像素与该点像素值不同,则认为其为角点。步骤如下:

1)在图像中任选一点p, 假定其像素(亮度)值为 Ip
2)以r为半径画圆,覆盖p点周围的M个像素,如下图所示: r=3, M=16
3)设定阈值t,如果这周围的16个像素中有连续的N个像素的像素值减去 Ipt 或者有连续的N个像素都大于 Ip+t, 如果t=0,那么就可以理解为:有连续N个像素大于或小于Ip的灰度值。那么这个点就被判断为角点。

特征点检测FAST算法

由于在检测特征点时是需要对图像中所有的像素点进行检测,然而图像中的绝大多数点都不是特征点,如果对每个像素点都进行上述的检测过程,那显然会浪费许多时间,因此论文中采用了一种进行非特征点判别的方法。如上图中,对于每个点都检测第1、5、9、13号像素点,如果这4个点中至少有3个满足都比Ip+t

Ip+t

大或者都比Ipt

Ip−t

小,则继续对该点进行16个邻域像素点都检测的方法,否则则判定该点是非特征点(也不可能是角点,如果是一个角点,那么上述四个像素点中至少有3个应该和点相同),直接剔除即可。                                                                                                                                                                                                                                                                                                                           这种做法在大幅减少了判断特征点的运算量,提升了算法的运行速度。但是还是存在一些问题,如下:
(1)当我们使用的n<12

n<12

时就不能通过上面说明的方法对非角点进行快速过滤;
(2)这样检测出来的特征点不是最优的,因为这种检测方法暗含了对特征周围的像素分布的假定;
(3)忽略了上述的前4个检测的结果分析;
(4)检测得到的特征点容易挤在一起。

 

2.非极大值抑制

针对算法(4)的缺点:很可能大部分检测出来的点彼此之间相邻,我们要去除一部分这样的点。为了解决这一问题,可以采用非最大值抑制的算法:假设P,Q两个点相邻,分别计算两个点与其周围的16个像素点之间的差分和为V,去除V值较小的点,即把非最大的角点抑制掉。


3.基于机器学习的特征点检测算法

针对(1)(2)(3)的缺点:作者使用机器学习的特征点检测方法,这种检测方法解决了上面的前3个问题

具体算法如下:

  1. 首先选取你进行角点提取的应用场景下很多张的测试图片。
  2. 运行FAST角点检测算法来获取测试图片集上的所有角点特征。
  3. 对于每个角点,我们把它邻域圆上的16个点存储下来保存在一个vector内,处理所有步骤2中得到的角点,并把它们存储在PP中。
  4. 对于图像上的点pp,它周围邻域圆上位置为x,x{116}x,x∈{1…16}的点表示为pxp→x,可以用下面的判断公式将该点pxp→x分为3类:
    Spx=d,s,b,IpxIptIptIpx<Ip+tIp+tIpx(darker)(similar)(brighter)Sp→x={d,Ip→x≤Ip–t(darker)s,Ip−t≤Ip→x<Ip+t(similar)b,Ip+t≤Ip→x(brighter)
  5. PP为训练图像集中所有像素点的集合,我们任意16个位置中的一个位置xx,可以把集合PP分为三个部分Pd,PsPd,PsPbPb,其中PdPd的定义如下,PsPsPbPb的定义与其类似
    Pb={pP:Spx=b}Pb={p∈P:Sp→x=b}
    换句话说,对于任意给定的位置xx,它都可以把所有图像中的点分为三类,第一类PdPd包括了所有位置xx处的像素在阈值tt下暗于中心像素,第二类PsPs包括了所有位置xx处的像素在阈值tt下近似于中心像素,PbPb包括了所有位置xx处的像素在阈值tt下亮于中心像素。
  6. 定义一个新的布尔变量KpKp,如果pp是一个角点,那些KpKp为值,否则为假。
  7. 使用ID3算法(决策树分类器)来查询每一个子集。
  8. 递归计算所有的子集直到KpKp的熵为0;
  9. 被创建的决策树就用于于其他图片的FAST检测。

那么问题来了,什么样角度的角点都能检测到吗?如下图:有三种角点,分别是45°角,90°角和135°角。

特征点检测FAST算法

那么FASTN算法哪个角点都能检测到么?答案是肯定的。但是这取决于连续像素N的设置。我们仍然假如半径r=3,那么在该圆上有16个像素:如下图:

特征点检测FAST算法

因为该算法检测角点的条件是:连续N个像素大于或小于中心灰度值减去阈值t,所以这个N从某种程度上就决定了能检测到的角度。比如下图:以黑线为基准的话,设置N=10的话,能检测到小于135°的角(黑红夹角),设置N=12的话,能检测到小于90°的角(黑蓝夹角),设置N=14的话,则能检测到小于45°的角(黑绿夹角)。

特征点检测FAST算法

4.FAST算法总结

1)在速度上要比其他算法速度快很多
2)受图像噪声以及设定的阈值影响很大
3)FASTN不产生多尺度特征而且FASTN特征点没有方向信息,这样就会失去旋转不变性。


参考:https://blog.csdn.net/x454045816/article/details/52373063

        https://www.cnblogs.com/ronny/p/4078710.html



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号