Summary

The undefined website provides an in-depth explanation of the FAST (Features from Accelerated Segment Test) corner detection algorithm, its machine learning enhancements, and its application in computer vision tasks, particularly emphasizing its efficiency for real-time processing in applications like SLAM.

Abstract

The FAST algorithm is introduced as a computationally efficient method for corner detection in images, which is crucial for real-time applications such as SLAM (Simultaneous Localization and Mapping) in mobile robots. Developed by Edward Rosten and Tom Drummond, FAST outperforms other feature detectors in speed while maintaining robust performance. The algorithm operates by testing a circular set of pixels around a candidate point to determine if it qualifies as a corner based on a defined intensity threshold. A machine learning approach is incorporated to optimize the detection process by creating a decision tree that minimizes the number of pixel comparisons required. This approach significantly reduces computational time and resources. The article also addresses limitations of the FAST algorithm, such as its performance on computer-generated images with crisp edges and proposes solutions like Gaussian blurring. Non-maximal suppression is employed to refine the detection of interest points. The article concludes with a practical implementation example using OpenCV and provides references and further reading resources for those interested in exploring the topic more deeply.

Opinions

The author suggests that traditional feature detectors are not suitable for real-time applications due to their slower processing speeds.
FAST is presented as particularly advantageous for real-time video processing due to its high-speed performance.
The use of machine learning techniques is advocated to further enhance the speed and efficiency of the FAST algorithm.
The author acknowledges limitations in the FAST algorithm's ability to detect corners on certain types of images, such as those with edges perfectly aligned with the x and y axes.
The author provides a practical example of FAST implementation using OpenCV, implying that it is a viable method for developers to adopt in their computer vision projects.
The article implies that the FAST algorithm, with its machine learning enhancements, represents a significant advancement in the field of feature detection.

Introduction to FAST (Features from Accelerated Segment Test)

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 has limited computational resources.

As a solution to this, Features from accelerated segment test (FAST) is a corner detection method, which could be used to extract feature points and later used to track and map objects in many computer vision tasks. The FAST corner detector was originally developed by Edward Rosten and Tom Drummond and was published in 2006. The most promising advantage of the FAST corner detector is its computational efficiency. Moreover, when machine learning techniques are applied, superior performance in terms of computation time and resources can be realized. The FAST corner detector is very suitable for real-time video processing application because of this high-speed performance.

This is part of a 7-series Feature Detection and Matching. Other articles included

Feature Detection using FAST

The algorithm is explained below:

12 point segment test corner detection in an image patch. The highlighted squares are the pixels used in the corner detection. The pixel at p is the center of a candidate corner. The arc is indicated by the dashed line passes through 12 contiguous pixels which are brighter than p by more than the threshold.

Select a pixel p in the image which is to be identified as an interest point or not. Let its intensity be Ip.
Select appropriate threshold value t.
Consider a circle of 16 pixels around the pixel under test. (This is a Bresenham circle of radius 3.)
Now the pixel p is a corner if there exists a set of n contiguous pixels in the circle (of 16 pixels) which are all brighter than Ip + t, or all darker than Ip - t. (The authors have used n= 12 in the first version of the algorithm)
To make the algorithm fast, first compare the intensity of pixels 1, 5, 9 and 13 of the circle with Ip. As evident from the figure above, at least three of these four pixels should satisfy the threshold criterion so that the interest point will exist.
If at least three of the four-pixel values — I1, I5, I9, I13 are not above or below Ip + t, then p is not an interest point (corner). In this case reject the pixel p as a possible interest point. Else if at least three of the pixels are above or below Ip + t, then check for all 16 pixels and check if 12 contiguous pixels fall in the criterion.
Repeat the procedure for all the pixels in the image.

There are a few limitations to the algorithm. First, for n<12, the algorithm does not work very well in all cases because when n<12 the number of interest points detected are very high. Second, the order in which the 16 pixels are queried determines the speed of the algorithm. A machine learning approach has been added to the algorithm to deal with these issues.

Machine Learning Approach

Select a set of images for training (preferably from the target application domain)
Run FAST algorithm in every image to find feature points.
For every feature point, store the 16 pixels around it as a vector. Do it for all the images to get feature vector p.
Each pixel (say x) in these 16 pixels can have one of the following three states:

Sp->x is the state, Ip->x is the intensity of the pixel x. and t is a threshold.

Depending on these states, the feature vector P is subdivided into 3 subsets Pd, Ps, Pb.
Define a variable Kp which is true if p is an interest point and false if p is not an interest point.
Use the ID3 algorithm (decision tree classifier) to query each subset using the variable Kp for the knowledge about the true class.
The ID3 algorithm works on the principle of entropy minimization. Query the 16 pixels in such a way that the true class is found (interest point or not) with the minimum number of queries. Or in other words, select the pixel x, which has the most information about the pixel p. The entropy for the set P can be mathematically represented as:

This is recursively applied to all the subsets until its entropy is zero.
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.

Compute a score function, V for all the detected feature points. V is the sum of absolute difference between p and 16 surrounding pixels values.
Consider two adjacent keypoints and compute their V values.
Discard the one with lower V value.

Limitations of the FAST Algorithm

Other corner detection methods work very differently from the FAST method and a surprising result is that FAST does not detect corners on computer-generated images that are perfectly aligned to the x-axes and y-axes. Since the detected corner must have a ring of darker or lighter pixel values around the center that includes both edges of the corner, crisp images do not work well.

This because the FAST algorithm requires a ring of contrasting pixels more than three-quarters around the center of corner. In the computer-generated image, both edges of a box at a corner are in the ring of the pixel used, so the test for a corner fails. A workaround to this problem is to add blur (by applying a Gaussian filter) to the image so that the corners are less precise but can be detected.

Implementation

I was able to implement FAST using OpenCV. Here’s how I did it:

Github link for the code: https://github.com/deepanshut041/feature-detection/tree/master/fast

References

Viswanathan, Deepak. “Features from Accelerated Segment Test ( FAST ).” (2011).
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.
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.
https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_feature2d/py_fast/py_fast.html
https://in.udacity.com/course/computer-vision-nanodegree--nd891