# Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 19 Jan 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions](https://mlsanity.com/paper/1603.08182/) (2016)
- [Deep Closest Point: Learning Representations for Point Cloud Registration](https://mlsanity.com/paper/1905.03304/) (2019)
- [A Metric Learning Reality Check](https://mlsanity.com/paper/2003.08505/) (2020)
- [TEASER: Fast and Certifiable Point Cloud Registration](https://mlsanity.com/paper/2001.07715/) (2020)
- [PointNetLK: Robust & Efficient Point Cloud Registration using PointNet](https://mlsanity.com/paper/1903.05711/) (2019)
- [Deep Global Registration](https://mlsanity.com/paper/2004.11540/) (2020)
- [D3Feat: Joint Learning of Dense Detection and Description of 3D Local Features](https://mlsanity.com/paper/2003.03164/) (2020)
- [The Perfect Match: 3D Point Cloud Matching with Smoothed Densities](https://mlsanity.com/paper/1811.06879/) (2018)
- [Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration](https://mlsanity.com/paper/1605.03344/) (2016)
- [PRNet: Self-Supervised Learning for Partial-to-Partial Registration](https://mlsanity.com/paper/1910.12240/) (2019)
- [Feature-metric Registration: A Fast Semi-supervised Approach for Robust Point Cloud Registration without Correspondences](https://mlsanity.com/paper/2005.01014/) (2020)
- [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)
- [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)
- [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)
- [Submodularization for Quadratic Pseudo-Boolean Optimization](https://mlsanity.com/paper/1311.1856/) (2013)

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

- [DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming](https://mlsanity.com/paper/2603.25442/) (2026)
- [Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching](https://mlsanity.com/paper/2405.08589/) (2024)

## Abstract (arXiv)

In many applications, we need algorithms which can align partially overlapping point sets and are invariant to the corresponding transformations. In this work, a method possessing such properties is realized by minimizing the objective of the robust point matching (RPM) algorithm. We first show that the RPM objective is a cubic polynomial. We then utilize the convex envelopes of trilinear and bilinear monomials to derive its lower bound function. The resulting lower bound problem has the merit that it can be efficiently solved via linear assignment and low dimensional convex quadratic programming. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently. Experimental results demonstrated better robustness of the proposed method against non-rigid deformation, positional noise and outliers in case that outliers are not mixed with inliers when compared with the state-of-the-art approaches. They also showed that it has competitive efficiency and scales well with problem size.