# FastMAC: Stochastic Spectral Sampling of Correspondence Graph

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 77 references that are in the map.
- First posted on arXiv 13 Mar 2024.

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

- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions](https://mlsanity.com/paper/1603.08182/) (2016)
- [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)
- [Geometric Transformer for Fast and Robust Point Cloud Registration](https://mlsanity.com/paper/2202.06688/) (2022)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [CoFiNet: Reliable Coarse-to-fine Correspondences for Robust Point Cloud Registration](https://mlsanity.com/paper/2110.14076/) (2021)
- [SpinNet: Learning a General Surface Descriptor for 3D Point Cloud Registration](https://mlsanity.com/paper/2011.12149/) (2020)
- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [Graph-Cut RANSAC](https://mlsanity.com/paper/1706.00984/) (2017)
- [RAFT-3D: Scene Flow using Rigid-Motion Embeddings](https://mlsanity.com/paper/2012.00726/) (2020)
- [3DRegNet: A Deep Neural Network for 3D Point Registration](https://mlsanity.com/paper/1904.01701/) (2019)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [3D Registration with Maximal Cliques](https://mlsanity.com/paper/2305.10854/) (2023)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration](https://mlsanity.com/paper/2203.14453/) (2022)
- [ROBIN: a Graph-Theoretic Approach to Reject Outliers in Robust Estimation using Invariants](https://mlsanity.com/paper/2011.03659/) (2020)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [LODE: Locally Conditioned Eikonal Implicit Scene Completion from Sparse LiDAR](https://mlsanity.com/paper/2302.14052/) (2023)
- [CLIPPER: A Graph-Theoretic Framework for Robust Data Association](https://mlsanity.com/paper/2011.10202/) (2020)
- [PQ-Transformer: Jointly Parsing 3D Objects and Layouts from Point Clouds](https://mlsanity.com/paper/2109.05566/) (2021)
- [Fast Resampling of 3D Point Clouds via Graphs](https://mlsanity.com/paper/1702.06397/) (2017)
- [Robust Fitting in Computer Vision: Easy or Hard?](https://mlsanity.com/paper/1802.06464/) (2018)
- [VIBUS: Data-efficient 3D Scene Parsing with VIewpoint Bottleneck and Uncertainty-Spectrum Modeling](https://mlsanity.com/paper/2210.11472/) (2022)
- [A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints](https://mlsanity.com/paper/1902.01534/) (2019)
- [3D Implicit Transporter for Temporally Consistent Keypoint Discovery](https://mlsanity.com/paper/2309.05098/) (2023)
- [From Semi-supervised to Omni-supervised Room Layout Estimation Using Point Clouds](https://mlsanity.com/paper/2301.13865/) (2023)
- [RANSIC: Fast and Highly Robust Estimation for Rotation Search and Point Cloud Registration using Invariant Compatibility](https://mlsanity.com/paper/2104.09133/) (2021)

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

- [TurboReg: TurboClique for Robust and Efficient Point Cloud Registration](https://mlsanity.com/paper/2507.01439/) (2025)
- [BUFFER-X: Towards Zero-Shot Point Cloud Registration in Diverse Scenes](https://mlsanity.com/paper/2503.07940/) (2025)
- [Progressive Correspondence Regenerator for Robust 3D Registration](https://mlsanity.com/paper/2502.02163/) (2025)
- [RARE: Refine Any Registration of Pairwise Point Clouds via Zero-Shot Learning](https://mlsanity.com/paper/2507.19950/) (2025)
- [A Consistency-Aware Spot-Guided Transformer for Versatile and Hierarchical Point Cloud Registration](https://mlsanity.com/paper/2410.10295/) (2024)
- [ACEvo: Adversarial Co-Evolution of Problem Distributions and Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2506.02594/) (2025)
- [3D Registration in 30 Years: A Survey](https://mlsanity.com/paper/2412.13735/) (2024)
- [Dual-frame Fluid Motion Estimation with Test-time Optimization and Zero-divergence Loss](https://mlsanity.com/paper/2410.11934/) (2024)
- [Mining and Transferring Feature-Geometry Coherence for Unsupervised Point Cloud Registration](https://mlsanity.com/paper/2411.01870/) (2024)
- [Online Navigation Refinement: Achieving Lane-Level Guidance by Associating Standard-Definition and Online Perception Maps](https://mlsanity.com/paper/2507.07487/) (2025)
- [Toward Zero-Shot Point Cloud Registration Across Diverse Scales, Scenes, and Sensor Setups](https://mlsanity.com/paper/2601.02759/) (2026)
- [DualReg: Dual-Space Filtering and Reinforcement for Rigid Registration](https://mlsanity.com/paper/2508.17034/) (2025)
- [R3PM-Net: Real-time, Robust, Real-world Point Matching Network](https://mlsanity.com/paper/2604.05060/) (2026)
- [Angle-I2P: Angle-Consistent-Aware Hierarchical Attention for Cross-Modality Outlier Rejection](https://mlsanity.com/paper/2605.04541/) (2026)
- [Ex-Sim(3)-Reg: 2D-3D Correspondence Pruning via Extended Sim(3) Registration](https://mlsanity.com/paper/2608.28096/) (2026)
- [Unsupervised Point Cloud Registration via Training-Time Semantic Guidance](https://mlsanity.com/paper/2609.15228/) (2026)

## Abstract (arXiv)

3D correspondence, i.e., a pair of 3D points, is a fundamental concept in computer vision. A set of 3D correspondences, when equipped with compatibility edges, forms a correspondence graph. This graph is a critical component in several state-of-the-art 3D point cloud registration approaches, e.g., the one based on maximal cliques (MAC). However, its properties have not been well understood. So we present the first study that introduces graph signal processing into the domain of correspondence graph. We exploit the generalized degree signal on correspondence graph and pursue sampling strategies that preserve high-frequency components of this signal. To address time-consuming singular value decomposition in deterministic sampling, we resort to a stochastic approximate sampling strategy. As such, the core of our method is the stochastic spectral sampling of correspondence graph. As an application, we build a complete 3D registration algorithm termed as FastMAC, that reaches real-time speed while leading to little to none performance drop. Through extensive experiments, we validate that FastMAC works for both indoor and outdoor benchmarks. For example, FastMAC can accelerate MAC by 80 times while maintaining high registration success rate on KITTI. Codes are publicly available at https://github.com/Forrest-110/FastMAC.