ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants

Many estimation problems in robotics, computer vision, and learning require estimating unknown quantities in the face of outliers. Outliers are typically the result of incorrect data association or feature matching, and it is not uncommon to have problems where more than 90% of the measurements used for estimation are outliers. While current approaches for robust estimation (e.g., RANSAC or graduated non-convexity) are able to deal with moderate amounts of outliers, they fail to produce accurate estimates in the presence of many outliers. This paper develops an approach to prune outliers. First, we develop a theory of invariance that allows us to quickly check if a subset of measurements are mutually compatible without explicitly solving the corresponding estimation problem. Second, we develop a graph-theoretic framework, where measurements are modeled as vertices and mutual compatibility is captured by edges in a graph. We generalize existing results showing that the inliers form a clique in this compatibility graph and typically belong to the maximum clique. We also show that in practice the maximum k-core of the compatibility graph provides an approximation of the maximum clique, while being much faster to compute in large problems. The combination of these two contributions leads to ROBIN, our approach to Reject Outliers Based on INvariants, which allows us to quickly prune outliers in generic estimation problems. We demonstrate ROBIN in four geometric perception problems and show it boosts robustness of existing solvers (making them robust to more than 95% outliers), while running in milliseconds in large problems.