# Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 48 references that are in the map.
- First posted on arXiv 14 May 2024.

## Builds on (most cited first, 16 of 16)

- [3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions](https://mlsanity.com/paper/1603.08182/) (2016)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [D3Feat: Joint Learning of Dense Detection and Description of 3D Local Features](https://mlsanity.com/paper/2003.03164/) (2020)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection](https://mlsanity.com/paper/1909.08605/) (2019)
- [Guaranteed Outlier Removal for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/1711.10209/) (2017)
- [FilterReg: Robust and Efficient Probabilistic Point-Set Registration using Gaussian Filter and Twist Parameterization](https://mlsanity.com/paper/1811.10136/) (2018)
- [GOGMA: Globally-Optimal Gaussian Mixture Alignment](https://mlsanity.com/paper/1603.00150/) (2016)
- [Scalable 3D Registration via Truncated Entry-wise Absolute Residuals](https://mlsanity.com/paper/2404.00915/) (2024)
- [An Adaptive Data Representation for Robust Point-Set Registration and Merging](https://mlsanity.com/paper/1511.04240/) (2015)
- [Density Adaptive Point Set Registration](https://mlsanity.com/paper/1804.01495/) (2018)
- [TriVoC: Efficient Voting-based Consensus Maximization for Robust Point Cloud Registration with Extreme Outlier Ratios](https://mlsanity.com/paper/2111.00657/) (2021)
- [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)
- [Efficient Global Point Cloud Alignment using Bayesian Nonparametric Mixtures](https://mlsanity.com/paper/1603.04868/) (2016)
- [A Concave Optimization Algorithm for Matching Partially Overlapping Point Sets](https://mlsanity.com/paper/1701.00951/) (2017)
- [Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets](https://mlsanity.com/paper/2101.07458/) (2021)

## Abstract (arXiv)

Numerous applications require algorithms that can align partially overlapping point sets while maintaining invariance to geometric transformations (e.g., similarity, affine, rigid). This paper introduces a novel global optimization method for this task by minimizing the objective function of the Robust Point Matching (RPM) algorithm. We first reveal that the original RPM objective is a cubic polynomial. Through a concise variable substitution, we transform this objective into a quadratic function. By leveraging the convex envelope of bilinear monomials, we derive a tight lower bound for this quadratic function. This lower bound problem conveniently and efficiently decomposes into two parts: a standard linear assignment problem (solvable in polynomial time) and a low-dimensional convex quadratic program. Furthermore, we devise a specialized Branch-and-Bound (BnB) algorithm that branches exclusively on the transformation parameters, which significantly accelerates convergence by confining the search space. Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to non-rigid deformations, positional noise, and outliers, particularly in scenarios where outliers are distinct from inliers.