In this chapter,
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).
in the image which is to be identified as an interest point or not. Let its intensity be
.
.
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.
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:
First 3 points are addressed with a machine learning approach. Last one is addressed using non-maximal suppression.
.
) in these 16 pixels can have one of the following three states:
is subdivided into 3 subsets,
,
,
.
, which is true if
is a corner and false otherwise.
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
.
Detecting multiple interest points in adjacent locations is another problem. It is solved by using Non-maximum Suppression.
for all the detected feature points.
is the sum of absolute difference between
and 16 surrounding pixels values.
values.
value.
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.
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: