# ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants arXiv: https://arxiv.org/abs/2011.03659 ยท HTML: https://mlsanity.com/paper/2011.03659/ ## Key facts - Cited by 38 papers in the map (data through 14 Oct 2026). - First posted on arXiv 7 Nov 2020. ## Built on by (most cited first, 30 of 38) - [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021) - [Self-supervised Geometric Perception](https://mlsanity.com/paper/2103.03114/) (2021) - [Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global Optimization](https://mlsanity.com/paper/2109.03349/) (2021) - [A Single Correspondence Is Enough: Robust Global Registration to Avoid Degeneracy in Urban Environments](https://mlsanity.com/paper/2203.06612/) (2022) - [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021) - [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024) - [KISS-Matcher: Fast and Robust Point Cloud Registration Revisited](https://mlsanity.com/paper/2409.15615/) (2024) - [Optimal Pose and Shape Estimation for Category-level 3D Object Perception](https://mlsanity.com/paper/2104.08383/) (2021) - [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022) - [Global Multi-modal 2D/3D Registration via Local Descriptors Learning](https://mlsanity.com/paper/2205.03439/) (2022) - [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023) - [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021) - [Recognizing Rigid Patterns of Unlabeled Point Clouds by Complete and Continuous Isometry Invariants with no False Negatives and no False Positives](https://mlsanity.com/paper/2303.15385/) (2023) - [Multi-instance Point Cloud Registration by Efficient Correspondence Clustering](https://mlsanity.com/paper/2111.14582/) (2021) - [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022) - [Point Cloud Registration for LiDAR and Photogrammetric Data: a Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms](https://mlsanity.com/paper/2302.07184/) (2023) - [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024) - [RANSAC Back to SOTA: A Two-stage Consensus Filtering for Real-time 3D Registration](https://mlsanity.com/paper/2410.15682/) (2024) - [Robust Single Rotation Averaging Revisited](https://mlsanity.com/paper/2309.05388/) (2023) - [DANIEL: A Fast and Robust Consensus Maximization Method for Point Cloud Registration with High Outlier Ratios](https://mlsanity.com/paper/2110.05075/) (2021) - [CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration](https://mlsanity.com/paper/2402.15464/) (2024) - [IRON: Invariant-based Highly Robust Point Cloud Registration](https://mlsanity.com/paper/2103.04357/) (2021) - [Practical, Fast and Robust Point Cloud Registration for 3D Scene Stitching and Object Localization](https://mlsanity.com/paper/2111.04228/) (2021) - [GraffMatch: Global Matching of 3D Lines and Planes for Wide Baseline LiDAR Registration](https://mlsanity.com/paper/2212.12745/) (2022) - [CLIPPER: Robust Data Association without an Initial Guess](https://mlsanity.com/paper/2402.07284/) (2024) - [CLIP-Clique: Graph-based Correspondence Matching Augmented by Vision Language Models for Object-based Global Localization](https://mlsanity.com/paper/2410.03054/) (2024) - [Category-Level Object Shape and Pose Estimation in Less Than a Millisecond](https://mlsanity.com/paper/2509.18979/) (2025) - [Robust Self-Tuning Data Association for Geo-Referencing Using Lane Markings](https://mlsanity.com/paper/2207.14042/) (2022) - [PCR-99: A Practical Method for Point Cloud Registration with 99 Percent Outliers](https://mlsanity.com/paper/2402.16598/) (2024) - [Fast globally optimal Truncated Least Squares point cloud registration with fixed rotation axis](https://mlsanity.com/paper/2508.15613/) (2025) ## Abstract (arXiv) 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 common to have problems where more than 90% of the measurements used for estimation are outliers. While current approaches for robust estimation 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 estimation problem. Second, we develop a graph-theoretic framework, where measurements are modeled as vertices and mutual compatibility is captured by edges. We generalize existing results showing that the inliers form a clique in this 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 faster to compute in large problems. 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 while running in milliseconds in large problems.