图像特征之FAST角点检测

桃扇骨 2022-06-03 06:22 272阅读 0赞

原文站点：[https://senitco.github.io/2017/06/30/image-feature-fast/][https_senitco.github.io_2017_06_30_image-feature-fast]

前面已经介绍多种图像特征点(角点、斑点、极值点)的检测算法，包括Harris、LoG、HoG以及SIFT、SURF等，这些方法大多涉及图像局部邻域的梯度计算和统计，相比较而言，FAST(Features From Accelerated Segment Test)在进行角点检测时，计算速度更快，实时性更好。

### FAST角点定义 ###

FAST角点定义为：若某像素点与周围邻域足够多的像素点处于不同区域，则该像素可能为角点。考虑灰度图像，即若某像素点的灰度值比周围邻域足够多的像素点的灰度值大或小，则该点可能为角点。

### 算法步骤 ###

*  对于图像中一个像素点p，其灰度值为Ip
 *  以该像素点为中心考虑一个半径为3的离散化的Bresenham圆，圆边界上有16个像素(如下图所示)
 *  设定一个合适的阈值t，如果圆上有n个连续像素点的灰度值小于Ip−t或者大于Ip\+t，那么这个点即可判断为角点(n的值可取12或9)  
      
    ![circle.jpg][]

一种快速排除大部分非角点像素的方法就是检查周围1、5、9、13四个位置的像素，如果位置1和9与中心像素P点的灰度差小于给定阈值，则P点不可能是角点，直接排除；否则进一步判断位置5和13与中心像素的灰度差，如果四个像素中至少有3个像素与P点的灰度差超过阈值，则考察邻域圆上16个像素点与中心点的灰度差，如果有至少9个超过给定阈值则认为是角点。

### 角点分类器 ###

*  选取需要检测的场景的多张图像进行FAST角点检测，选取合适的阈值n(n<12)，提取多个特征点作为训练数据
 *  对于特征点邻域圆上的16个像素x∈\{ 1,2,...,16\}，按下式将其划分为3类  
    
    
    Sp→x=⎧⎩⎨⎪⎪d,Ip→x≤Ip−ts,Ip−t≤Ip→x≤Ip\+tb,Ip\+t≤Ip→x
 *  对每个特征点定义一个bool变量Kp，如果p是一个角点，则Kp为真，否则为假
 *  对提取的特征点集进行训练，使用ID3算法建立一颗决策树，通过第x个像素点进行决策树的划分，对集合P，得到熵值为  
    
    
    H(P)=(c\+c^)log2(c\+c^)−c(log2c)−c^(log2c^)
    
      
    其中c为角点的数目，c^为非角点的数目。由此得到的信息增益为  
    
    
    ΔH=H(P)−H(Pd)−H(Ps)−H(Pb)
    
      
    选择信息增益最大位置进行划分，得到决策树
 *  使用决策树对类似场景进行特征点的检测与分类

### 非极大值抑制 ###

对于邻近位置存在多个特征点的情况，需要进一步做非极大值抑制(Non-Maximal Suppression)。给每个已经检测到的角点一个量化的值V，然后比较相邻角点的V值，保留局部邻域内V值最大的点。V值可定义为  
\- 特征点与邻域16个像素点灰度绝对差值的和  
\- V=max(Σx∈Sbright|Ip→x−Ip|−t,Σx∈Sdark|Ip→x−Ip|−t)  
式中，Sbright是16个邻域像素点中灰度值大于Ip\+t的像素点的集合，而Sdark表示的是那些灰度值小于Ip−t的像素点。

### 算法特点 ###

*  FAST算法比其他角点检测算法要快
 *  受图像噪声以及设定阈值影响较大
 *  当设置n<12时，不能用快速方法过滤非角点
 *  FAST不产生多尺度特征，不具备旋转不变性，而且检测到的角点不是最优

### reference ###

*  [Paper: Machine learning for high-speed corner detection][Paper_ Machine learning for high-speed corner detection]
 *  [Paper: Faster and better: a machine learning approach to corner detection][Paper_ Faster and better_ a machine learning approach to corner detection]
 *  [http://www.cnblogs.com/ronny/p/4078710.html][http_www.cnblogs.com_ronny_p_4078710.html]
 *  [http://blog.csdn.net/hujingshuang/article/details/46898007][http_blog.csdn.net_hujingshuang_article_details_46898007]
 *  [http://blog.csdn.net/lql0716/article/details/65662648][http_blog.csdn.net_lql0716_article_details_65662648]
 *  [https://liu-wenwu.github.io/2016/10/08/fast-corners/][https_liu-wenwu.github.io_2016_10_08_fast-corners]
 *  [http://blog.csdn.net/skeeee/article/details/9405531][http_blog.csdn.net_skeeee_article_details_9405531]

[https_senitco.github.io_2017_06_30_image-feature-fast]: https://senitco.github.io/2017/06/30/image-feature-fast/
[circle.jpg]: https://ooo.0o0.ooo/2017/07/10/596386112222c.jpg
[Paper_ Machine learning for high-speed corner detection]: https://www.edwardrosten.com/work/rosten_2006_machine.pdf
[Paper_ Faster and better_ a machine learning approach to corner detection]: https://pdfs.semanticscholar.org/a963/288ffecda4fd2bc475efe7cfb59ab094e7c1.pdf
[http_www.cnblogs.com_ronny_p_4078710.html]: http://www.cnblogs.com/ronny/p/4078710.html
[http_blog.csdn.net_hujingshuang_article_details_46898007]: http://blog.csdn.net/hujingshuang/article/details/46898007
[http_blog.csdn.net_lql0716_article_details_65662648]: http://blog.csdn.net/lql0716/article/details/65662648
[https_liu-wenwu.github.io_2016_10_08_fast-corners]: https://liu-wenwu.github.io/2016/10/08/fast-corners/
[http_blog.csdn.net_skeeee_article_details_9405531]: http://blog.csdn.net/skeeee/article/details/9405531