Evolutionary Multitasking With Solution Space Cutting for Point Cloud Registration

Yue Wu, Peiran Gong, Maoguo Gong, Hangqi Ding, Zedong Tang, Yibo Liu, Wenping Ma, Qiguang Miao

TL;DR

This paper introduces EMTR-SSC, a novel evolutionary multi-task registration algorithm that tackles the common problem of falling into local optima in point cloud registration. By "cutting" the solution space into simpler and more complex tasks and enabling knowledge transfer between them, EMTR-SSC significantly improves the success rate of accurate registration.

What Problem Does This Paper Address?

Point cloud registration (PCR) is crucial for aligning 3D scans of objects or environments. While evolutionary algorithms (EAs) offer robustness to initial poses and flexible objective functions, they often struggle with local optima, leading to registration failures. Existing EAs rarely focus on the "success ratio" – the probability of avoiding these local optima – which is critical for practical applications. This paper aims to improve both the success ratio and the precision of evolutionary PCR methods.

Methods

The core of the proposed method, EMTR-SSC, is an Evolutionary Multi-Task Optimization (EMTO) framework. It defines two tasks:

  • Task α: Searches the full rigid transformation space (rotation and translation) using a robust M-estimator Chamfer Distance fitness function, designed to handle partial overlaps. This task aims for high accuracy but is prone to local optima.
  • Task β: Operates on a "cut" solution space, specifically by using Translation Invariant Measurements (TIMs) which effectively removes the translation component. This simplified search space makes it easier to find the global optimum.

Knowledge transfer occurs from Task β to Task α. A key innovation is the Knowledge Complement strategy, which uses Task β's rotation solution to estimate and complement the missing translation parameters for Task α, preventing negative transfer.

To reduce computational cost, a Sparse-to-Dense strategy is employed. In the early stages of evolution, sparser point clouds are used for faster evaluation, and denser point clouds are used in later stages for higher precision. A novel metric for computational cost, based on the number of nearest neighbor search (NNS) calls, is also introduced.

Datasets

The experiments were conducted on a variety of datasets:

  • Object-scale datasets: Armadillo, Bunny, Stanford Dragon, Happy, Chef, Chicken, U3M (Parasaurolophus, T-rex), Bimba, FGR (Chinese Dragon, Dancing Children), ModelNet40.
  • Scene-scale dataset: RESSO.

These datasets vary in point cloud size, overlap rate, and noise levels, providing a comprehensive evaluation.

Key Insights and Ideas

  • Solution Space Cutting for EMTO: The idea of dividing the search space into simpler (Task β) and more complex (Task α) tasks is a novel way to configure EMTO for PCR. The simpler task acts as a guide to help the more complex one escape local optima.
  • Knowledge Complement is Crucial: Simply transferring Task β's solution to Task α isn't enough. The proposed "Knowledge Complement" strategy, which intelligently estimates missing translation parameters, is vital for effective knowledge transfer and improving precision.
  • Sparse-to-Dense for Efficiency: The observation that sparse point clouds are sufficient for early-stage registration and dense clouds are needed later is a practical insight that significantly reduces computational burden without sacrificing accuracy.
  • Success Ratio Matters: The paper emphasizes the importance of the success ratio, a metric often overlooked, as a key indicator of an algorithm's practicality and robustness.

Key Results

  • Superior Success Ratio: EMTR-SSC achieved a significantly higher success ratio (up to 90% on many datasets) compared to 8 other evolutionary algorithms, including state-of-the-art EMTO methods. It showed an average success ratio improvement of 54.7% over the best single-task competitor and substantial improvements over other EMTO approaches.
  • High Precision: The method demonstrated competitive or superior registration precision (both rotation and translation error) compared to traditional, evolving, and deep learning approaches across various datasets.
  • Computational Efficiency: The sparse-to-dense strategy reduced computational cost by nearly 50% while maintaining high accuracy.
  • Robustness: The M-estimator in the fitness function made EMTR-SSC robust to outliers and partial overlaps, outperforming methods that struggled with these challenges.

Limitations and Future Work

  • Parameter Tuning: The paper acknowledges that parameters like the random mating probability (rmp) and the sparse-to-dense switch parameter (δ) need to be determined experimentally.
  • Adaptive Parameters: The authors suggest future work to investigate how to make these parameters adaptive rather than constant, which would improve the algorithm's generalizability to different datasets.

Summary updated

Abstract

Point cloud registration (PCR) is a popular research topic in computer vision. Recently, the registration method in an evolutionary way has received continuous attention because of its robustness to the initial pose and flexibility in objective function design. However, most evolving registration methods cannot tackle the local optimum well and they have rarely investigated the success ratio, which implies the probability of not falling into local optima and is closely related to the practicality of the algorithm. Evolutionary multi-task optimization (EMTO) is a widely used paradigm, which can boost exploration capability through knowledge transfer among related tasks. Inspired by this concept, this study proposes a novel evolving registration algorithm via EMTO, where the multi-task configuration is based on the idea of solution space cutting. Concretely, one task searching in cut space assists another task with complex function landscape in escaping from local optima and enhancing successful registration ratio. To reduce unnecessary computational cost, a sparse-to-dense strategy is proposed. In addition, a novel fitness function robust to various overlap rates as well as a problem-specific metric of computational cost is introduced. Compared with 8 evolving approaches, 4 traditional approaches and 3 deep learning approaches on the object-scale and scene-scale registration datasets, experimental results demonstrate that the proposed method has superior performances in terms of precision and tackling local optima.
BibTeX
@article{wu2023evolutionary,
  author = {Yue Wu and Peiran Gong and Maoguo Gong and Hangqi Ding and Zedong Tang and Yibo Liu and Wenping Ma and Qiguang Miao},
  title = {{Evolutionary Multitasking With Solution Space Cutting for Point Cloud Registration}},
  journal = {IEEE Transactions on Emerging Topics in Computational Intelligence},
  year = {2023},
  doi = {10.1109/tetci.2023.3290009},
}
Figure