Consensus Set Maximization with Guaranteed Global Optimality for Robust Geometry Estimation

Abstract

Finding the largest consensus set is one of the key ideas used by the original RANSAC for removing outliers in robust-estimation. However, because of its random and non-deterministic nature, RANSAC does not fulfill the goal of consensus set maximization exactly and optimally. Based on global optimization, this paper presents a new algorithm that solves the problem exactly. We reformulate the problem as a mixed integer programming (MIP), and solve it via a tailored branch-and-bound method, where the bounds are computed from the MIP's convex under-estimators. By exploiting the special structure of linear robust-estimation, the new algorithm is also made efficient from a computational point of view.