AGAST Corner Detector: faster than FAST and even FAST-ER

千海之貝 2011-12-22

展開全文

AGAST Corner Detector: faster than FAST and even FAST-ER

Motivation

Corner response of the OAST9 mask.

Corners are preferred cues in Computer Vision due to their two dimensional constraint and fast algorithms to detect them. Recently, Edward Rosten et al. presented the corner detection approach FAST, which outperforms conventional algorithms not only regarding their performance but also their repeatability. This detector is based on the accelerated segment test (AST), which is a modification of the SUSAN corner detector, as described in the FAST-paper.

The accelerated segment test (AST) is a so called twenty question problem. Rosten computes the decision tree by learning the distribution of the corner configuration from a training set of a specific environment. This approach has some drawbacks:

If the camera is rotated, the pixel configuration of a corner may change significantly. Thus, the adaption to a scene results in a speed up of the corner detector only as long as the camera or the environment does not move (especially rotate). Any motion can lead to corner configurations which are rather slow to evaluate.
Some corner configurations may be missing in the training set which leads to false positive and false negative responses of the corner detector.
The decision tree has to be learned for every new environment from scratch.
ID3 is used to build the decision tree, which is a greedy algorithm and, therefore, the result can be quite suboptimal.
FAST builds a ternary decision tree for a binary target machine - a binary tree would be more efficient.

AGAST: Adaptive and Generic Accelerated Segment Test

In our approach, we propose a technique to compute a binary decision tree (corner detector) which is generic and does not have to be adapted to new environments. It is complete by definition (no false positive or false negative responses) and the only parameters are the memory access times to weight the various pixel comparisons. The tree is optimal for a certain probability of similar pixels in the AST mask.

By combining two trees, the corner detector adapts to the environment automatically and provides the most efficient decision tree for the image region with only one pixel delay (see figure on the right hand side). Hence, it results in a corner detector, which is faster and does not have to be trained while preserving the same corner response and repeatability as the (complete) FAST corner detector. We called this detector AGAST, which stands for Adaptive and Generic Accelerated Segment Test.

Please keep in mind, that the AST, which AGAST is based on, has been developed by Edward Rosten (et al.) and that in our approach only the way the decision trees for the AST are built and used has been significantly improved. AGAST uses also the same non-maximum suppression as FAST.

We also compare different pattern sizes for the AST and discuss the effect of noise and blur for various mask sizes. The figure on the right hand side shows the pattern for the 16 pixel mask (green), the 12 pixel masks (blue, square and diamond) and the 8 pixel mask (red).

For more details please refer to the paper in the publication section.