Technische Universität München Robotics and Embedded Systems
 

AGAST Corner Detector

 

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

Motivation

oast9_16.png
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:

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.

tree_adaptive.png

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.

pattern.jpgpattern2.jpg

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

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"
}

Related Links

FAST, Features from Accelerated Segment Test - the first AST based corner detector developed by Edward Rosten (et al.). This page provides publications and source code.

Locations of visitors to this page