Globally optimal registration of noisy point clouds

Rangaprasad Arun Srivatsan, Tejas Zodage, Howie ChosetarXiv 2019 · OpenReview

Abstract

Registration of 3D point clouds is a fundamental task in several applications of robotics and computer vision. While registration methods such as iterative closest point (ICP) and its variants are popular, they are typically only locally optimal. Recent work on globally optimal registration often performs poorly in the presence of noise. This paper introduces a mixed-integer programming (MIP) approach for globally optimal registration that explicitly considers measurement uncertainty. By combining a robust global formulation with fast local methods in a multi-step pipeline, the proposed method achieves superior accuracy across various levels of noise, outliers, and partial geometric overlap.

Introduction

Point cloud registration (PCR) is a critical component in localization, mapping, and object recognition. The objective is to determine the optimal rotation and translation to align two sets of 3D points. While the Iterative Closest Point (ICP) algorithm is the industry standard due to its speed, it is prone to converging to local minima if the initial alignment is poor.

Existing globally optimal methods, such as Go-ICP, attempt to solve this by searching the entire transformation space. However, these methods often rely on Euclidean distance metrics that assume clean data. In real-world scenarios, sensors like LiDAR and RGB-D cameras introduce significant noise and outliers. This paper addresses these challenges by incorporating uncertainty directly into the optimization process.

Methodology: The PCR-MIP-Mah Formulation

The core contribution is PCR-MIP-Mah, a registration framework that utilizes Mahalanobis distance instead of standard Euclidean distance. This allows the system to weight point correspondences based on the expected noise characteristics of the sensor and the geometric model.

To ensure the problem remains computationally tractable for standard solvers like Gurobi, the authors employ several technical strategies:

  • Linearization: The Mahalanobis distance is reformulated using an $l_1$ norm to maintain linear constraints.
  • Convex Relaxations: Because rotation matrices are inherently non-convex, the authors use piecewise-convex relaxations and McCormick constraints to "convexify" the search space, enabling the solver to find the true global minimum.

The Multi-Step Pipeline

To mitigate the computational cost of Mixed-Integer Programming, the authors propose a three-stage pipeline that balances global search with local efficiency:

  1. Approximate Pose Estimation (APE): A rapid, coarse alignment performed on a small subset of points.
  2. Refinement for Noise (RN): The primary PCR-MIP-Mah algorithm is executed, but search is restricted to a "correspondence band" of likely candidates identified in the APE step.
  3. Local Dense Refinement (LDR): A final high-precision polish using all available points and a local optimizer (IMLP).
The multi-step optimization pipeline transitions from coarse approximate pose estimation (APE) to a restricted global search (RN) and finally to local dense refinement (LDR).

Key Insights and Uncertainty Modeling

A pivotal insight of this work is that modeling anisotropic noise—where uncertainty varies by direction—significantly improves robustness. By treating the error landscape as a complex surface with multiple valleys, the Mahalanobis-based global approach can navigate toward the ground truth where Euclidean methods might fail.

Error landscape comparison: The Mahalanobis formulation (PCR-MIP-Mah) successfully identifies the global minimum (ground truth) in a noisy landscape, whereas Euclidean and local methods often stall in local minima.

Experimental Evaluation

The method was rigorously tested across synthetic and real-world datasets:

  • Synthetic Models: The Stanford Bunny (noise testing), the Dragon (outlier testing), and the "David" head (partial overlap testing).
  • Real-World RGB-D: Indoor lounge scans focusing on pure geometric registration.
  • Real-World LiDAR: Urban environment scans from the Oakland dataset using Velodyne sensors.

Results and Discussion

Experimental results demonstrate that PCR-MIP-Mah outperforms state-of-the-art methods in challenging conditions:

  • Noise Robustness: At high noise levels ($\sigma = 4 \times 10^{-2}$), PCR-MIP-Mah maintained a rotation error of 2.33°, while local methods like IMLP failed completely (errors > 50°).
  • Outlier Handling: The system remained stable with up to 40% outliers, achieving a Target Registration Error (TRE) of $3 \times 10^{-3}$.
  • Real-World Performance: On the Oakland LiDAR dataset, the method achieved a rotation error of 0.38° and a translation error of 0.7cm, proving its viability for automotive-grade sensor data.

Conclusion

This work presents a robust, globally optimal framework for 3D point cloud registration. By integrating Mahalanobis distance into a mixed-integer programming formulation and utilizing a multi-step pipeline, the authors bridge the gap between global search and practical sensor noise. While the computational cost of MIP solvers remains a hurdle for real-time applications, this approach provides a new benchmark for accuracy in noisy environments. Future work will explore relaxing the isotropic noise assumption for sensor points and extending the formulation to non-rigid, deformable objects.

Summary updated

Abstract

Registration of 3D point clouds is a fundamental task in several applications of robotics and computer vision. While registration methods such as iterative closest point and variants are very popular, they are only locally optimal. There has been some recent work on globally optimal registration, but they perform poorly in the presence of noise in the measurements. In this work we develop a mixed integer programming-based approach for globally optimal registration that explicitly considers uncertainty in its optimization, and hence produces more accurate estimates. Furthermore, from a practical implementation perspective we develop a multi-step optimization that combines fast local methods with our accurate global formulation. Through extensive simulation and real world experiments we demonstrate improved performance over state-of-the-art methods for various level of noise and outliers in the data as well as for partial geometric overlap.
BibTeX
@misc{srivatsan2019globally,
  author = {Rangaprasad Arun Srivatsan and Tejas Zodage and Howie Choset},
  title = {{Globally optimal registration of noisy point clouds}},
  year = {2019},
  eprint = {1908.08162},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.08162},
}
Figure