A robust inlier identification algorithm for point cloud registration via 𝓁0-minimization

Yinuo Jiang, Xiuchuan Tang, Cheng Cheng, Ye YuanNeurIPS 2024

TL;DR

This paper introduces a novel algorithm for robustly identifying correct correspondences (inliers) in point cloud registration, even with a high percentage of incorrect ones (outliers). By reformulating the problem as an $l_0$-minimization task and employing a clever two-stage decoupling strategy, their method achieves state-of-the-art accuracy and robustness across various challenging datasets.

What Problem Does This Paper Address?

Point cloud registration is a fundamental task in 3D computer vision and robotics, crucial for applications like 3D reconstruction, SLAM, and autonomous driving. The goal is to align two point clouds by estimating a rigid transformation (rotation and translation). A common pipeline involves extracting features, matching them to establish correspondences, and then estimating the transformation. However, feature matching is imperfect, leading to a significant number of incorrect correspondences (outliers). These outliers can severely degrade the accuracy of the estimated transformation. Existing methods struggle to effectively handle high outlier ratios and noise, especially in complex or textureless scenes.

Methods

The core of this paper is a new inlier identification algorithm based on $l_0$-minimization. Instead of directly minimizing the squared error (which is sensitive to outliers), they aim to minimize the number of non-zero errors (the $l_0$ norm). This is applied to local sets of correspondences derived from a compatibility graph.

The key innovation is a two-stage decoupling strategy:

  1. Decoupling Rotation and Translation: The 6-DOF rigid transformation is first split into independent 3-DOF rotation and 3-DOF translation problems. This is achieved by working with relative point positions, where translation cancels out for rotation estimation, and vice-versa for translation.
  2. Decoupling Inlier Identification from Estimation: For each of the decoupled rotation and translation problems, they further decouple the inlier identification from the estimation itself. This is done using null-space matrices and a Bayesian approach. Essentially, they isolate the part of the error that is independent of the transformation being estimated, allowing them to identify inliers based on this transformed error.

This approach allows them to solve for fitting errors and then identify correspondences with the smallest errors as inliers. Hypotheses generated from local sets are then combined to select the best overall transformation.

Datasets

The paper evaluates its method on several standard benchmarks:

  • Synthetic dataset: Stanford Bunny point cloud, augmented with noise and outliers.
  • Outdoor scenes: KITTI dataset [13], using sequences 8-10.
  • Indoor scenes: 3DMatch [44] and 3DLoMatch [17] datasets.

Key Insights and Ideas

  • $l_0$-minimization for Robustness: Framing inlier identification as an $l_0$-minimization problem is a powerful way to directly target the goal of fitting as many inliers as possible, inherently downplaying the influence of outliers compared to $l_2$-based methods.
  • Two-Stage Decoupling is Crucial: The paper demonstrates that breaking down the complex 6-DOF registration problem into smaller, manageable rotation and translation sub-problems, and then further decoupling inlier identification from estimation, is key to achieving both robustness and efficiency.
  • Bayesian Approach Enhances Inlier Identification: The use of a Bayesian framework within the decoupled estimation process helps to refine inlier identification, especially in the presence of noise.
  • Local Sets for Scalability and Robustness: By formulating the problem on local sets of correspondences, the method can handle a large number of initial correspondences more efficiently and robustly.

Key Results

  • State-of-the-Art Accuracy: The proposed method achieves the highest registration recall (RR) and competitive rotation error (RE) and translation error (TE) across KITTI, 3DMatch, and 3DLoMatch datasets, outperforming both traditional and learning-based methods. For example, on KITTI with FPFH, it achieves 99.56% RR, 0.34° RE, and 7.85cm TE.
  • Exceptional Robustness to Outliers: The method demonstrates remarkable resilience to high outlier ratios, performing well even at 99% outliers on the synthetic Bunny dataset, significantly outperforming competitors like FGR and RANSAC.
  • Robustness to Noise: It also shows strong performance under increasing Gaussian noise levels, maintaining low errors where other methods falter.
  • Efficiency: While not the absolute fastest, the method is competitive in terms of efficiency, especially when considering its high accuracy. The explicit solutions derived from the convex relaxation contribute to this.

Limitations and Future Work

  • Feature Ambiguity: The paper acknowledges that failure cases can occur in scenes with repeated patterns or textureless structures due to feature matching ambiguity. These are noted as challenging problems.
  • Future Work: Potential solutions suggested include improving feature extraction or employing point cloud completion techniques. The authors also plan to explore applications in multimodal medical image registration and enhance robustness for featureless data.
  • Scalability: While efficient, further improvements through parallel computing and C++ implementation are suggested, particularly for the two-stage decoupling components.

Summary updated

BibTeX
@inproceedings{jiang2024robust,
  author = {Yinuo Jiang and Xiuchuan Tang and Cheng Cheng and Ye Yuan},
  title = {{A robust inlier identification algorithm for point cloud registration via 𝓁0-minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
}
Figure