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.

People

Elmar Mair, M.Sc. (Robotics and Embedded Systems, MVP group - institute member)
Prof. Dr. Gregory D. Hager (Johns Hopkins University (JHU), Department of Computer Science, CIRL lab)
Prof. Dr.-Ing. Darius Burschka (Robotics and Embedded Systems, MVP group - institute member)
Dr.-Ing. Michael Suppa (German Aerospace Center (DLR), Institute of Robotics and Mechatronics)
Prof. Dr.-Ing. Gerd Hirzinger (German Aerospace Center (DLR), Institute of Robotics and Mechatronics)

Publication

[1]	Elmar Mair, Gregory D. Hager, Darius Burschka, Michael Suppa, and Gerhard Hirzinger. Adaptive and generic corner detection based on the accelerated segment test. In Proceedings of the European Conference on Computer Vision (ECCV'10), September 2010. [ DOI \| .bib \| .pdf ]

Code

The downloadable package includes the machine generated code for AGAST5 (8 pixel mask), AGAST7s/d (12 pixel square and diamond mask), OAST9 (16 pixel mask) together with an example of usage (example code and example image). OAST stands for optimal accelerated segment test. Due to the computational limitations, we could not compute the binary decision tree for the 16 pixel mask and the ternary decision tree does not allow any balancing. Thus only the optimal decision tree for this mask has been computed.
Our non-maximum suppression uses the same principle as the one implemented in the FAST package, but it is not sparse and about 40% faster than the FAST implementation.

Copyright (C) 2010 Elmar Mair
The program you can download here is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

You can download the code from AGAST @ SourceForge.
A thread-safe C++ implementation can be found at AGAST++ @ SourceForge (released under BSD v3).

If you are publishing a project using this software, please refrence following publication:

 @inproceedings{mair2010_agast,
   title       =    "Adaptive and Generic Corner Detection Based on the Accelerated Segment Test",
   author      =    "Elmar Mair and Gregory D. Hager and Darius Burschka and Michael Suppa and Gerhard Hirzinger",
   year        =    "2010",
   month       =    "September",
   booktitle   =    "European Conference on Computer Vision (ECCV'10)",
   url         =    "http://www6.in.tum.de/Main/ResearchAgast"
}

AGAST Corner Detector