Research map / Point clouds / Registration and matching
Scalable 3D Registration via Truncated Entry-wise Absolute Residuals
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.
Proposes TEAR, a branch-and-bound method for outlier-robust 3D registration using a truncated entry-wise absolute residual loss decomposed into 3D and 2D subproblems, scaling to 10^7 point pairs with 99.8% outliers.
Problem
Outlier-robust 3D point-pair registration is unscalable for existing methods (consistency graphs, deep learning, branch-and-bound), running out of 16GB memory around 30,000 point pairs or being too slow at large scale.
Approach
Replace the usual consensus-maximization or truncated least-squares loss with a truncated entry-wise l1 residual loss (TEAR), decompose the 6-DoF problem into a 3-DoF and a 2-DoF subproblem solved by branch-and-bound with novel tight bounds computable in O(N log N), followed by SVD on the surviving inliers.
Key results
- TEAR handles 10^7 point pairs with 99.8% random outliers on the Stanford models, where consistency-graph and deep learning methods run out of memory.
- On 3DMatch TEAR reaches 94.52% RR in 1.26 s versus MAC (C++) 94.57% RR in 6.89 s, and on ETH TEAR reaches 96.43% RR in 0.38 s.
- TEAR is up to 70 times faster than TR-DE on real data and about 100 times faster than TR-DE in synthetic experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TEAR-1 rather than CM-1 as the branch-and-bound objective (ablation) | Branch-and-bound registration · Synthetic data, 95% outliers | F1-score | Helped |
| Replace TEAR-1 with CM-1 (ablation) | Branch-and-bound registration · Synthetic data, 95% outliers | Running time: more than 5 times slower | Hurt |
| Replace TEAR-1 with CM-1 (ablation) | Branch-and-bound registration · Synthetic data, 95% outliers | F1-score | Hurt |
| Replace TEAR-1 with TLS-1 (ablation) | Branch-and-bound registration · Synthetic data, 99% outliers | Running time | Hurt |
| Replace TEAR-1 with TLS-1 (ablation) | Branch-and-bound registration · Synthetic data, 99% outliers | F1-score | No clear effect |
| Use TEAR for registration | 3DMatch registration · 3DMatch | F1 (%): 89.48 -> 89.65 | Helped |
| Use TEAR for registration | KITTI registration · KITTI | Running time (s): 0.36 -> 0.25 | Helped |
| Use TEAR for registration | ETH registration · ETH | F1 (%): 92.23 -> 93.14 | Helped |
| Use TEAR on the original point cloud rather than downsampling to 104 point pairs | Lucy registration · Lucy, 107 point pairs, 99.8% outliers | Rotation error | Helped |
Surprising findings
- Branch-and-bound, usually considered slow, can be competitive and scale nearly linearly for outlier-robust 3D registration.
- Downsampling point clouds before registration with other methods raises rotation errors substantially, since it discards inliers and can increase the outlier ratio.
Limitations
- Experiments with huge-scale point clouds use synthetic outliers on Stanford models rather than real correspondences.
- Branch-and-bound lower bounds for TLS-1 are only O(N^2), and TEAR's bounds are tailored to the decomposed problem rather than general formulations.
- Some baselines (e.g., MAC, PointDSC, VBReg) run out of memory on the real ETH data, so comparisons there are partial.
Experimental setup
Datasets: 3DMatch KITTI ETH Stanford 3D scanning dataset
Benchmarks: 3DMatch KITTI ETH Stanford 3D scanning dataset
Metrics: registration recall F1-score rotation error translation error time peak memory
Baselines: RANSAC TEASER++ SC2-PCR MAC PointDSC VBReg TR-DE GORE FGR
Builds on: TR-DE TEASER++ GORE RANSAC
Closest papers by meaning
- Deterministic Point Cloud Registration via Novel Transformation Decomposition (CVPR 2022 · similarity 0.88)
- Progressive Correspondence Regenerator for Robust 3D Registration (CVPR 2025 · similarity 0.88)
- A robust inlier identification algorithm for point cloud registration via $\mathbf{\ell_0}$-minimization (NeurIPS 2024 · similarity 0.87)
- Register Anything Model for Generalizable and Robust Point Cloud Registration (NeurIPS 2026 · similarity 0.87)
- Multi-scale Consistency for Robust 3D Registration via Hierarchical Sinkhorn Tree (NeurIPS 2024 · similarity 0.87)
- Occlusion-aware Non-Rigid Point Cloud Registration via Unsupervised Neural Deformation Correntropy (ICLR 2025 · similarity 0.86)
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.