We just made FAST9 faster !

FAST9 is a keypoint detection algorithm proposed by Edward Rosten and Tom Drummond(Dept of Engineering, Cambridge University, UK). The primary purpose behind proposing this scheme was to make it computationally feasible to run on embedded processor.

FAST9 involves checking if a sequence of neighbouring points(in this case 9) are bigger or smaller than the central pixel by a particular threshold. This involves a lot of if else conditions which are computationally very expensive on an embedded processor. Instead Rosten and Drummond proposed that one doesnt have to really check for all the conditions to verify if a point is corner point or not. Instead you could make a few quick checks and then do an early exit, if it appears that the point under consideration is not a corner point. For arriving at the most optimal sequence of the quick checks, Rosten and Drummond proposed using machine learning.

Uncanny Vision was determined to make this keypoint  detection scheme even faster, by utilizing the ARM Neon instruction set. We used a different technique to optimize FAST9. The performance of our implementation is not image or threshold dependent, whereas this is not the case with the original implementation proposed by the authors.

The original implementation had 2 steps to it. First was to detect potential corner points, based on a threshold. Step 2 was to rate these detected points using a particular score. This scoring can be used to select the best points amongst the corner points detected. The original paper proposes a few possible scoring functions, while OpenCV implements one particular option from amongst these. Uncanny Vision chose a different scoring function(one amongst the options suggested in the paper), which suits our implementation.

Profile details for FAST9 are as follows on a Cortex A8(profiled in beagle board running Linux, clocked at 720 MHz) for  a 640×480 image


Threshold = 20 , Total Corners =8702
OpenCV
FAST9       : 21.5 ms
FAST score(OpenCV version)      : 11.7 ms
Total time = 21.5 + 11.7 = 33.2ms

UncannyCV
FAST9+FAST score(Uncanny version)     :18.4 ms

Threshold = 10, Total Corners =23388
OpenCV
FAST9        : 24.6 ms
FAST score(OpenCV version)      : 24.9 ms
Total time = 24.6 + 24.9 = 49.5ms

UncannyCV
FAST9+FAST score(Uncanny version)     :17.9 ms