RATSAC - Random tree sampling for maximum consensus estimation

Abstract

The maximum consensus problem lies at the core of several important computer vision applications as it is one of the most popular criteria for robust estimation. Although considerable efforts have been devoted to solving this problem, exact algorithms are still impractical for real-world data. Randomized hypothesize-and-test approaches such as RANSAC and its variants are therefore still the key players in the field. Revolving around the original RANSAC algorithm, different sampling schemes have been proposed. Despite achieving substantial improvements, these RANSAC variants are still insufficient for highly contaminated data. With the aim to improve the class of randomized techniques, this paper contributes a novel approach to solve the maximum consensus problem using Monte Carlo Tree Search. Based on the theory of the LP-type problems, we reformulate the maximum consensus as an instance of tree search, which advocates the use of Monte Carlo Tree Search to explore the tree. We empirically demonstrate that our method outperforms other state- of-the-art methods in common geometric estimation problems.