FAST,全称Features From Accelerated Segment Test,是一种快速的角点检测算法,本文记录相关内容。
特征点提取到底是提取的是什么?
怎么比较两个特征点是否是同一个?
那么怎么比较周围信息?
FAST (Features from Accelerated Segment Test)是一个特征点提取算法的缩写。
在此之前已经有多种图像特征点(角点、斑点、极值点)的检测算法,包括Harris、LoG、HoG以及SIFT、SURF等被提出,这些方法大多涉及图像局部邻域的梯度计算和统计,相比较而言,FAST(Features From Accelerated Segment Test)在进行角点检测时,计算速度更快,实时性更好。
FAST角点定义为:若某像素点与周围邻域足够多的像素点处于不同区域,则该像素可能为角点。考虑灰度图像,即若某像素点的灰度值比周围邻域足够多的像素点的灰度值大或小,则该点可能为角点。
这是一个点提取算法。它原理非常简单,遍历所有的像素点,判断当前像素点是不是特征点的唯一标准就是在以当前像素点为圆心以3像素为半径画个圆(圆上有16个点),统计这16个点的像素值与圆心像素值相差比较大的点的个数。超过9个差异度很大的点那就认为圆心那个像素点是一个特征点。
为了获得更快的效果,还采用了而外的加速办法。首先对候选点的周围每个 90 度的点:1,9,5,13 进行测试(先测试 1 和 19, 如果它们符合阈值要求再测试 5 和 13)。如果 p 是角点,那么这四个点中至少有 3 个要符合阈值要求。如果不是的话肯定不是角点,就放弃。对通过这步测试的点再继续进行测试(是否有 12 的点符合阈值要求)。这个检测器的效率很高,但是它有如下几条缺点:
前 3 个问题可以通过机器学习的方法解决,最后一个问题可以使用非最大值抑制的方法解决。
选取需要检测的场景的多张图像进行FAST角点检测,选取合适的阈值n(n<12),提取多个特征点作为训练数据
对于特征点邻域圆上的16个像素 x \in {1,2,…,16 },按下式将其划分为3类
$$ S_{p\rightarrow x} = \begin{cases} d, I_{p\rightarrow x} \leq I_p-t \\ s, I_p-t \leq I_{p\rightarrow x} \leq I_p+t \\ b, I_p+t \leq I_{p\rightarrow x} \end{cases} $$
对每个特征点定义一个bool变量 K_p,如果 𝑝 是一个角点,则 K_p 为真,否则为假
,得到熵值为
其中 为非角点的数目。由此得到的信息增益为
选择信息增益最大位置进行划分,得到决策树
使用决策树对类似场景进行特征点的检测与分类
对于邻近位置存在多个特征点的情况,需要进一步做非极大值抑制(Non-Maximal Suppression)。
具体来说就是:给每个已经检测到的角点一个量化的值 𝑉,然后比较相邻角点的𝑉值,保留局部邻域内𝑉值最大的点。𝑉值可定义为
它被称为OpenCV中的任何其他特征检测器。如果需要,你可以指定阈值,是否应用非最大抑制,要使用的邻域等。
对于邻域,定义了三个标志,cv.FAST_FEATURE_DETECTOR_TYPE_5_8,cv.FAST_FEATURE_DETECTOR_TYPE_7_12和cv.FAST_FEATURE_DETECTOR_TYPE_9_16。下面是一个关于如何检测和绘制FAST特征点的简单代码。