FAST Algorithm for Corner Detection

Goal

In this chapter,

  • We will understand the basics of FAST algorithm
  • We will find corners using OpenCV functionalities for FAST algorithm.

Theory

We saw several feature detectors and many of them are really good. But when looking from a real-time application point of view, they are not fast enough. One best example would be SLAM (Simultaneous Localization and Mapping) mobile robot which have limited computational resources.

As a solution to this, FAST (Features from Accelerated Segment Test) algorithm was proposed by Edward Rosten and Tom Drummond in their paper “Machine learning for high-speed corner detection” in 2006 (Later revised it in 2010). A basic summary of the algorithm is presented below. Refer original paper for more details (All the images are taken from original paper).

Feature Detection using FAST

  1. Select a pixel 

 in the image which is to be identified as an interest point or not. Let its intensity be 

.

  1. Select appropriate threshold value 

.

  1. Consider a circle of 16 pixels around the pixel under test. (See the image below)
  1. Now the pixel 

 is a corner if there exists a set of 

 contiguous pixels in the circle (of 16 pixels) which are all brighter than 

, or all darker than 

. (Shown as white dash lines in the above image). 

 was chosen to be 12.

  1. A high-speed test was proposed to exclude a large number of non-corners. This test examines only the four pixels at 1, 9, 5 and 13 (First 1 and 9 are tested if they are too brighter or darker. If so, then checks 5 and 13). If 

 is a corner, then at least three of these must all be brighter than 

 or darker than 

. If neither of these is the case, then 

 cannot be a corner. The full segment test criterion can then be applied to the passed candidates by examining all pixels in the circle. This detector in itself exhibits high performance, but there are several weaknesses:

  • It does not reject as many candidates for n < 12.
  • The choice of pixels is not optimal because its efficiency depends on ordering of the questions and distribution of corner appearances.
  • Results of high-speed tests are thrown away.
  • Multiple features are detected adjacent to one another.

First 3 points are addressed with a machine learning approach. Last one is addressed using non-maximal suppression.

Machine Learning a Corner Detector

  1. Select a set of images for training (preferably from the target application domain)
  2. Run FAST algorithm in every images to find feature points.
  3. For every feature point, store the 16 pixels around it as a vector. Do it for all the images to get feature vector 

.

  1. Each pixel (say 

) in these 16 pixels can have one of the following three states:

  1. Depending on these states, the feature vector 

 is subdivided into 3 subsets, 

.

  1. Define a new boolean variable, 

, which is true if 

 is a corner and false otherwise.

  1. Use the ID3 algorithm (decision tree classifier) to query each subset using the variable 

 for the knowledge about the true class. It selects the 

 which yields the most information about whether the candidate pixel is a corner, measured by the entropy of 

.

  1. This is recursively applied to all the subsets until its entropy is zero.
  2. The decision tree so created is used for fast detection in other images.

Non-maximal Suppression

Detecting multiple interest points in adjacent locations is another problem. It is solved by using Non-maximum Suppression.

  1. Compute a score function, 

 for all the detected feature points. 

 is the sum of absolute difference between 

 and 16 surrounding pixels values.

  1. Consider two adjacent keypoints and compute their 

 values.

  1. Discard the one with lower 

 value.

Summary

It is several times faster than other existing corner detectors.

But it is not robust to high levels of noise. It is dependant on a threshold.

FAST Feature Detector in OpenCV

It is called as any other feature detector in OpenCV. If you want, you can specify the threshold, whether non-maximum suppression to be applied or not, the neighborhood to be used etc.

For the neighborhood, three flags are defined, cv2.FAST_FEATURE_DETECTOR_TYPE_5_8,cv2.FAST_FEATURE_DETECTOR_TYPE_7_12 and cv2.FAST_FEATURE_DETECTOR_TYPE_9_16. Below is a simple code on how to detect and draw the FAST feature points.

import numpy as np
import cv2
from matplotlib import pyplot as plt

img = cv2.imread('simple.jpg',0)

# Initiate FAST object with default values
fast = cv2.FastFeatureDetector()

# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv2.drawKeypoints(img, kp, color=(255,0,0))

# Print all default params
print "Threshold: ", fast.getInt('threshold')
print "nonmaxSuppression: ", fast.getBool('nonmaxSuppression')
print "neighborhood: ", fast.getInt('type')
print "Total Keypoints with nonmaxSuppression: ", len(kp)

cv2.imwrite('fast_true.png',img2)

# Disable nonmaxSuppression
fast.setBool('nonmaxSuppression',0)
kp = fast.detect(img,None)

print "Total Keypoints without nonmaxSuppression: ", len(kp)

img3 = cv2.drawKeypoints(img, kp, color=(255,0,0))

cv2.imwrite('fast_false.png',img3)

See the results. First image shows FAST with nonmaxSuppression and second one without nonmaxSuppression:

Additional Resources

  1. Edward Rosten and Tom Drummond, “Machine learning for high speed corner detection” in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
  2. Edward Rosten, Reid Porter, and Tom Drummond, “Faster and better: a machine learning approach to corner detection” in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

mxnet框架样本,使用C++接口

哇塞,好久么有跟进mxnet啦,python改版了好多好多啊,突然发现C++用起来才是最爽的. 贴一个mxnet中的C++Example中的mlp网络和实现,感...

1K50
来自专栏锦小年的博客

复杂网络(1)--图论的基本理论

1 图论的基本概念 1.1 图(graph)及其分类 (1) 图的定义:图是由点集V={vi}以及V中元素无序对的集合E={ek}所构成的二元组,记为G=(...

286100
来自专栏wym

Codeforces Round #483 (Div. 2) B. Minesweeper

One day Alex decided to remember childhood when computers were not too powerful ...

12420
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(上)

因为这一章的内容基本上都是涉及向量的,先来一个2D向量类:Vector2D.as (再次强烈建议不熟悉向量运算的童鞋,先回去恶补一下高等数学-07章空间解释几何...

22360
来自专栏数据结构与算法

2017.9.17校内noip模拟赛解题报告

预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

42170
来自专栏wym

hdu 1025 Constructing Roads In JGShining's Kingdom

JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which...

14930
来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

281100
来自专栏chenjx85的技术专栏

leetcode-458-Poor Pigs

18940
来自专栏CreateAMind

(Keras)基于DDPG用300行Python代码玩转TORCS(开放赛车模拟器)-教程及代码

视频地址 http://weibo.com/3164120327/EcF8g6jdw

42630
来自专栏图形学与OpenGL

CG实验4 三维几何变换

13610

扫码关注云+社区

领取腾讯云代金券