Feature Point

FAST Keypoint

Resources

• Original Paper: http://www.edwardrosten.com/work/rosten_2005_tracking.pdf
  • Available locally: file:///Users/stevengong/My%20Drive/Books/FAST%20rosten_2005_tracking.pdf
• Good High Level Article: https://medium.com/data-breach/introduction-to-fast-features-from-accelerated-segment-test-4ed33dde6d65

The FAST algorithm

We basically apply this on a circular ring of pixels, to detect a feature.

“A test is performed for a feature at a pixel $p$ by examining a circle of 16 pixels (a Bresenham circle of radius 3) surrounding $p$. A feature is detected at $p$ if the intensities of at least 12 contiguous pixels are all above or all below the intensity of $p$ by some threshold $t$“.

• For ORB Features, they use FAST-9, so a circle of radius 9

So more generally, 3/4 of the surrounding pixel space should be above or below the threshold of the center pixel.

Small optimization step

The authors recommend considering 4 points first (1, 5, 9, 13 in the image). At least 3 of them should all be above or below the intensity of $p$ by threshold $t$.

Using Machine Learning

Notice that the order in which the 16 pixels is queried determines the runtime of the algorithm. This is where we can make use of ML to find the optimal order.

This was recommended in the Medium article, I don’t think I found it in the original paper.

Limitations

There are 2 limitations:

1. Not orientation aware
   • The keypoint does not include orientation information
2. Not scale aware
   • A keypoint that is too far / too close would not get detected

These limitations are addressed in ORB.