Research map / Point clouds / Registration and matching
FastMAC: Stochastic Spectral Sampling of Correspondence Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Applies graph signal processing with a high-pass Laplacian filter on the generalized degree signal to stochastically sample correspondences, accelerating maximal-clique (MAC) 3D point cloud registration to real-time with little accuracy loss.
Problem
Maximal-clique-based 3D point cloud registration (MAC) is slow because maximal clique search on the correspondence graph scales exponentially with the number of correspondences, and deterministic graph sampling via SVD is too expensive.
Approach
Treat the generalized degree of each correspondence as a graph signal, apply a Laplacian high-pass filter, and sample correspondences with probability proportional to the filtered response magnitude; this stochastic approximation of optimal spectral sampling runs in time linear in sample count and is inserted before MAC.
Key results
- FastMAC@5 accelerates MAC by about 80x on KITTI (FCGF) while keeping registration recall near MAC (97.84% vs 97.66% at 50% ratio in Table 2).
- FastMAC@20 runs in real time (about 35 ms per registration on KITTI per Figure 1) with RR of 98.02% on KITTI FPFH.
- Stochastic sampling takes a stable ~15 ms as sample count grows, whereas deterministic greedy SVD-based sampling took about two days for 2500 samples in the authors' experiment.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on KITTI with FCGF · KITTI, FCGF | RR (%): 97.25 -> 97.48 | Helped |
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on KITTI with FCGF · KITTI, FCGF | Time(s): 0.570 -> 0.028 | Helped |
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on 3DMatch with FCGF · 3DMatch, FCGF | RR (%): 93.72 -> 92.30 | Hurt |
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on 3DMatch with FCGF · 3DMatch, FCGF | Time(s): 0.914 -> 0.038 | Helped |
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on 3DLoMatch with FCGF · 3DLoMatch, FCGF | RR (%): 59.85 -> 55.25 | Hurt |
| Sample correspondences at 20% ratio with FastMAC instead of using MAC without sampling | MAC on 3DLoMatch with FCGF · 3DLoMatch, FCGF | Time(s): 1.181 -> 0.051 | Helped |
| Replace high-pass graph filtering with all-pass filtering (ablation) | FastMAC on KITTI with FCGF, 1% sampling · KITTI, FCGF | RR (%): 71.89 -> 28.11 | Hurt |
| Replace high-pass graph filtering with low-pass filtering (ablation) | FastMAC on KITTI with FCGF, 1% sampling · KITTI, FCGF | RR (%): 71.89 -> 13.33 | Hurt |
| Replace high-pass graph filtering with all-pass filtering (ablation) | FastMAC on KITTI with FCGF, 5% sampling · KITTI, FCGF | RR (%): 96.04 -> 93.33 | Hurt |
| Replace high-pass graph filtering with low-pass filtering (ablation) | FastMAC on KITTI with FCGF, 5% sampling · KITTI, FCGF | RR (%): 96.04 -> 90.09 | Hurt |
| Replace high-pass graph filtering with all-pass filtering (ablation) | FastMAC on KITTI with FCGF, 10% sampling · KITTI, FCGF | RR (%): 96.94 -> 96.94 | No clear effect |
| Replace high-pass graph filtering with low-pass filtering (ablation) | FastMAC on KITTI with FCGF, 10% sampling · KITTI, FCGF | RR (%): 96.94 -> 94.96 | Hurt |
Surprising findings
- Random sampling and farthest point sampling degrade sharply, and FPS performs even worse than random sampling, attributed to using 6D Euclidean distance on correspondences.
- Combining the xyz signal with the generalized degree signal degrades performance, which the authors attribute to contamination of the degree signal.
Limitations
- Graph construction becomes the bottleneck as the sample ratio decreases.
- Performance drops at very low sampling ratios (e.g., 1%), especially on low-overlap 3DLoMatch.
Experimental setup
Datasets: KITTI 3DMatch 3DLoMatch
Benchmarks: KITTI 3DMatch 3DLoMatch
Metrics: registration recall (RR) rotation error (RE) translation error (TE) runtime (ms)
Baselines: MAC FGR TEASER++ RANSAC-4M CG-SAC SC2-PCR DGR PointDSC GC-RANSAC 3DRegNet random sampling farthest point sampling
Builds on: MAC graph signal processing sampling theory FCGF FPFH
Closest papers by meaning
- Multi-scale Consistency for Robust 3D Registration via Hierarchical Sinkhorn Tree (NeurIPS 2024 · similarity 0.86)
- PointMC: Multi-instance Point Cloud Registration based on Maximal Cliques (ICML 2024 · similarity 0.85)
- Scalable 3D Registration via Truncated Entry-wise Absolute Residuals (CVPR 2024 · similarity 0.85)
- GraphI2P: Image-to-Point Cloud Registration with Exploring Pattern of Correspondence via Graph Learning (CVPR 2025 · similarity 0.84)
- Multiway Point Cloud Mosaicking with Diffusion and Global Optimization (CVPR 2024 · similarity 0.84)
- A robust inlier identification algorithm for point cloud registration via $\mathbf{\ell_0}$-minimization (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.