# ARCS: Accurate Rotation and Correspondence Search

arXiv: https://arxiv.org/abs/2203.14493 · HTML: https://mlsanity.com/paper/2203.14493/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 104 references that are in the map.
- First posted on arXiv 28 Mar 2022.

## Builds on (most cited first, 30 of 36)

- [PREDATOR: Registration of 3D Point Clouds with Low Overlap](https://mlsanity.com/paper/2011.13005/) (2020)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [Deep Global Registration](https://mlsanity.com/paper/2004.11540/) (2020)
- [The Perfect Match: 3D Point Cloud Matching with Smoothed Densities](https://mlsanity.com/paper/1811.06879/) (2018)
- [MAGSAC++, a fast, reliable and accurate robust estimator](https://mlsanity.com/paper/1912.05909/) (2019)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [MAGSAC: marginalizing sample consensus](https://mlsanity.com/paper/1803.07469/) (2018)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [A comprehensive survey on point cloud registration](https://mlsanity.com/paper/2103.02690/) (2021)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020)
- [An Overview of Robust Subspace Recovery](https://mlsanity.com/paper/1803.01013/) (2018)
- [A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers](https://mlsanity.com/paper/1905.12536/) (2019)
- [CLIPPER: A Graph-Theoretic Framework for Robust Data Association](https://mlsanity.com/paper/2011.10202/) (2020)
- [Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications](https://mlsanity.com/paper/2007.15109/) (2020)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [Beyond Gr"obner Bases: Basis Selection for Minimal Solvers](https://mlsanity.com/paper/1803.04360/) (2018)
- [ReAgent: Point Cloud Registration using Imitation and Reinforcement Learning](https://mlsanity.com/paper/2103.15231/) (2021)
- [GOGMA: Globally-Optimal Gaussian Mixture Alignment](https://mlsanity.com/paper/1603.00150/) (2016)
- [A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints](https://mlsanity.com/paper/1902.01534/) (2019)
- [Dual Principal Component Pursuit](https://mlsanity.com/paper/1510.04390/) (2015)
- [One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers](https://mlsanity.com/paper/2006.06769/) (2020)
- [VSAC: Efficient and Accurate Estimator for H and F](https://mlsanity.com/paper/2106.10240/) (2021)
- [Practical optimal registration of terrestrial LiDAR scan pairs](https://mlsanity.com/paper/1811.09962/) (2018)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)
- [Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage](https://mlsanity.com/paper/1302.6256/) (2013)
- [PHASER: a Robust and Correspondence-free Global Pointcloud Registration](https://mlsanity.com/paper/2102.02767/) (2021)
- [A note on Probably Certifiably Correct algorithms](https://mlsanity.com/paper/1509.00824/) (2015)

## Built on by (most cited first, 15 of 15)

- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [Accelerating Globally Optimal Consensus Maximization in Geometric Vision](https://mlsanity.com/paper/2304.05156/) (2023)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [G3Reg: Pyramid Graph-based Global Registration using Gaussian Ellipsoid Model](https://mlsanity.com/paper/2308.11573/) (2023)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [Efficient and Deterministic Search Strategy Based on Residual Projections for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/2305.11716/) (2023)
- [Transformation Decoupling Strategy based on Screw Theory for Deterministic Point Cloud Registration with Gravity Prior](https://mlsanity.com/paper/2311.01432/) (2023)
- [Spatiotemporal Multi-Camera Calibration using Freely Moving People](https://mlsanity.com/paper/2502.12546/) (2025)
- [Towards Understanding The Semidefinite Relaxations of Truncated Least-Squares in Robust Rotation Search](https://mlsanity.com/paper/2207.08350/) (2022)
- [fCOP: Focal Length Estimation from Category-level Object Priors](https://mlsanity.com/paper/2409.19641/) (2024)
- [Correspondence-Free Fast and Robust Spherical Point Pattern Registration](https://mlsanity.com/paper/2508.02339/) (2025)
- [Accelerating Outlier-robust Rotation Estimation by Stereographic Projection](https://mlsanity.com/paper/2502.06337/) (2025)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [ViGG: Robust RGB-D Point Cloud Registration using Visual-Geometric Mutual Guidance](https://mlsanity.com/paper/2511.22908/) (2025)
- [Global Truncated Loss Minimization for Robust and Threshold-Resilient Geometric Estimation](https://mlsanity.com/paper/2603.14796/) (2026)

## Abstract (arXiv)

This paper is about the old Wahba problem in its more general form, which we call "simultaneous rotation and correspondence search". In this generalization we need to find a rotation that best aligns two partially overlapping 3D point sets, of sizes m and n respectively with m≥ n. We first propose a solver, textttARCS, that i) assumes noiseless point sets in general position, ii) requires only 2 inliers, iii) uses O(mlog m) time and O(m) space, and iv) can successfully solve the problem even with, e.g., m,n≈ 106 in about 0.1 seconds. We next robustify textttARCS to noise, for which we approximately solve consensus maximization problems using ideas from robust subspace learning and interval stabbing. Thirdly, we refine the approximately found consensus set by a Riemannian subgradient descent approach over the space of unit quaternions, which we show converges globally to an varepsilon-stationary point in O(varepsilon-4) iterations, or locally to the ground-truth at a linear rate in the absence of noise. We combine these algorithms into textttARCS+, to simultaneously search for rotations and correspondences. Experiments show that textttARCS+ achieves state-of-the-art performance on large-scale datasets with more than 106 points with a 104 time-speedup over alternative methods. urlhttps://github.com/liangzu/ARCS