ANTSAC: Combining RANSAC with Ant Colony Algorithms for Robust Estimation

ANTSAC is a new variant of the well-kwown RANdom SAmple Consensus (RANSAC) algorithm for robust estimation of model parameters. The idea of our method is based on the pheromone memory used in ant colony algorithms. ANTSAC is computationally efficient and convincingly easy to implement. It significantly outperforms RANSAC achieving higher inlier rates in less time. ANTSAC is entirely generic, such that no further domain knowledge is required, as it is for many other RANSAC extensions. Nevertheless, it is competitive to state-of-the-art methods, e.g., PROSAC or LO-RANSAC, even in domain specific scenarios.

Pheromone based sampling

The core of ANTSAC is a pheromone memory, which gains information from the process of iteratively sampling model instances, while the sampling itself becomes more and more intelligent over time. This is achieved as follows.


  • First, for instantiating the model, samples are picked according to a probability distribution computed based on the pheromone levels of all samples.

  • Second, after each hypothesis evaluation, all samples are rewarded based on their distance to the current model by accordingly increasing their particular pheromone levels.

  • Third, the pheromones ''evaporate'' over time, such that pheromones of poorly rewarded samples vanish.

Hence, the process of repeatedly selecting and updating pheromones of the samples turns ANTSAC into a meta-heuristic search strategy that enables the real inlier candidates to emerge.


The above image sequence shows the pheromone levels of 10,000 samples containing a noisy ellipse over time. ANTSAC enabled the real inlier candidates to emerge.

Experimental results

ANTSAC clearly outperforms classical RANSAC. For fundamental matrix estimation ANTSAC produces up to 160% more inliers than RANSAC. To gain the same number of inliers ANTSAC needs only a fractional part of iterations compared to RANSAC. On average ANTSAC often finds optimal model instances within 50 iterations that RANSAC does not find even after more than 10,000 iterations. The improvement of ANTSAC grows with the difficulty of the problem. ANTSAC needs less runtime to produce a similar number of inlier as, e.g., PROSAC, LO-RANSAC or USAC-1.0. As a sampling strategy, ANTSAC (without prior knowledge) is predominantly better than PROSAC sampling (with prior knowledge).



Publications

[1] Sebastian Otte, Ulrich Schwanecke, and Andreas Zell. ANTSAC: A Generic RANSAC Variant Using Principles of Ant Colony Algorithms. In 2014 22nd International Conference on Pattern Recognition (ICPR), pages 3558-3563, August 2014. [ DOI ]

Contact

Sebastian Otte, Tel.: (07071) 29 - 78979, sebastian.otte at uni-tuebingen.de