Introducing the FAST algorithm
Created and recorded by Yiming Cai, November 2021
Music: Twilight Area (https://www.lmms.io/lsp/?action=show&...) by Alf42red (https://www.lmms.io/lsp/?action=brows...) License: Creative Commons
Recap from feature detection video
Introduction to FAST
Visualization steps of FAST
Sample Matlab function: FAST
Summary
In the video for feature matching, I used a Matlab built-in function called Harris corner detection. In the last video, I introduced the Harris corner detection algorithm. This time, I want to talk about another feature detection algorithm called FAST, Features from Accelerated Segment Test algorithm.
The full name of the FAST algorithm is Feature from Accelerated Segment Test. Just like its name, one of its biggest advantages is fast. Also, by using the fast algorithm, the result of feature matching is controllable by changing the threshold.
Let's begin with the basic idea of the FAST algorithm. Take P0 as the pixel we are looking at, the algorithm will go through pixels around P0, and detect their differences. By detecting the difference between pixels, FAST will make its decision about whether this pixel is a feature point or not.
Now the question is how does the algorithm tell the difference? The most common way is measuring the difference of grayscale between pixels. Suppose the grayscale value of P0 is 20, and let’s set the threshold equal to 10. The red box means pixel has grayscale values that are bigger than 30, the yellow box is smaller than 10, gray box is between 10 and 30.
We only consider pixels that are 3 pixels away from p0. The reason we do this is to reduce the weak features and reduce the calculation for an image.
Now, one important thing is, the FAST algorithm will only consider a pixel as a possible feature point when there are more than n pixels that have grayscale bigger than p0+threshold, or more than n pixels smaller than p0-threshold. The continuous is the key of this algorithm.
Let's look at some examples. In our case, we consider the n equal to 9. Meaning, we want to find at least 9 continuous pixels that exceed the threshold.
In this picture, there are more than 9 continuous red pixels. So we consider this as a feature point.
In this picture, there are more than 9 continuous yellow pixels. So we consider this as a feature point.
However, in this picture, you will notice that even though all pixels around p0 exceed the threshold, but we do not consider this as a feature point.
The reason why it's not considered as a feature point is discontinuous. Other than just finding pixels that exceed the threshold, we expect the continuous. Such as at least 9 continuous pixels bigger than p0+threshold, or 9 continuous pixels smaller than p0-threshold. But not 9 continuous pixels bigger or smaller than the boundaries.
Based on its way of making decisions, the FAST algorithm is not very mathematics like other feature detecting algorithms such as Harris, it's more subjectively.
So we just talked about how to search feature points. And now, we can start considering getting rid of weak features.
To get rid of weak points in FAST, the easiest way is to increase the value of the threshold. Let's look at an example.
So the original threshold is 10, and the grayscale value is marked in this picture. This pixel is now considered a feature point.
How about we increase the threshold?
Let‘s set the threshold as 13, you will notice that the continuity does not exist anymore. Then, we don't consider this point as a feature point anymore.
(switch to code)
In Matlab, calculating matrix is easier than double for loop.
(go through the code)
In this video, we talked about what FAST algorithm is and how does it work. I also showed you a way to build FAST algorithm in Matlab without using for loops. Hope this video is helpful.
