Fast Gravitational Approach for Rigid Point Set Registration with Ordinary Differential Equations

Sk Aziz Ali, Kerem Kahraman, Christian Theobalt, Didier Stricker, Vladislav Golyanik

Abstract

This article introduces a new physics-based method for rigid point set alignment called Fast Gravitational Approach (FGA). In FGA, the source and target point sets are interpreted as rigid particle swarms with masses interacting in a globally multiply-linked manner while moving in a simulated gravitational force field. The optimal alignment is obtained by explicit modeling of forces acting on the particles as well as their velocities and displacements with second-order ordinary differential equations of motion. Additional alignment cues can be integrated through particle masses. We propose a smooth-particle mass function for point mass initialization, which improves robustness to noise and structural discontinuities. To avoid prohibitive quadratic complexity, we adapt a Barnes-Hut tree for accelerated force computation, achieving quasilinear computational complexity. Experiments show that FGA performs on par with or outperforms competing non-deep-learning-based techniques in resolving transformations for LiDAR data and gains state-of-the-art accuracy and speed when coping with different types of data disturbances.

Introduction

Rigid Point Set Registration (RPSR) is the foundational task of finding the optimal rotation and translation to align two 3D scans, critical for robotics, autonomous driving, and SLAM. Traditional methods like Iterative Closest Point (ICP) are efficient but sensitive to initial misalignments and noise. Conversely, modern deep-learning methods often struggle to generalize across unseen environments. Physics-based approaches offer a robust alternative by treating alignment as an energy minimization problem, but they have historically been computationally expensive, scaling quadratically ($O(N^2)$) with the number of points. FGA addresses these limitations by combining robust physics-based simulation with efficient computational structures.

Methodology

FGA reimagines registration as a dynamic simulation of $N$-body motion governed by gravitational interaction.

Gravitational Simulation and ODEs

The "source" point set is treated as a swarm of particles moving in a force field induced by a static "target" point set. The objective is to minimize the Gravitational Potential Energy (GPE) between them. Unlike first-order methods, FGA utilizes second-order ordinary differential equations (ODEs) to model particle velocity and displacement. This includes a dissipative damping force that prevents oscillation, allowing the system to settle into a stable, aligned state.

Barnes-Hut Acceleration

To overcome the $O(N^2)$ bottleneck of all-to-all point interactions, FGA adapts the Barnes-Hut (BH) tree algorithm. By hierarchically partitioning space, distant groups of points are approximated as single massive particles. This reduces the force calculation complexity to a quasilinear $O(N \log N)$, making it practical for large-scale LiDAR datasets.

The Barnes-Hut tree structure (A) and force approximation (B) enable FGA to scale efficiently to large point clouds.

Smooth-Particle Masses (SPM)

FGA introduces a mass initialization scheme called Smooth-Particle Masses. It utilizes Normalized Intrinsic Volume (NIV) to weight points based on local density, effectively handling the inhomogeneous sampling common in LiDAR sensors. This ensures the alignment is not biased toward high-density regions near the sensor.

Experiments and Results

The authors evaluated FGA on diverse benchmarks, including synthetic Stanford Bunny scans, ModelNet40 CAD shapes, and real-world indoor (3DMatch) and outdoor LiDAR (KITTI, Ford Campus) datasets.

Performance and Robustness

FGA demonstrates a significant leap in both speed and robustness:

  • Speed: The GPU implementation is approximately 100x faster than the CPU version, aligning massive LiDAR frames (~220k points) in just 0.7 seconds.
  • Robustness: FGA is correspondence-free, looking at global interactions rather than nearest-neighbor matches. This makes it inherently more robust to outliers and noise compared to ICP. In tests against deep learning models like PointNetLK and DCP, FGA showed superior generalization as noise levels increased.
  • Accuracy: On the challenging 3DMatch dataset, FGA outperformed all compared general-purpose techniques in both accuracy and runtime, often by factors of 2.5x to 4x.
Qualitative comparison showing FGA achieving the lowest error and high speed compared to a wide array of competitors.

Conclusion

FGA provides a powerful, physics-inspired framework for rigid registration that bridges the gap between robust energy-based methods and real-time performance requirements. By leveraging second-order ODEs and Barnes-Hut acceleration, it achieves state-of-the-art results on large-scale data without requiring scene-specific training. Future work may extend this framework to non-rigid motion fields for tracking deforming objects in real-time.

Summary updated

Abstract

This article introduces a new physics-based method for rigid point set alignment called Fast Gravitational Approach (FGA). In FGA, the source and target point sets are interpreted as rigid particle swarms with masses interacting in a globally multiply-linked manner while moving in a simulated gravitational force field. The optimal alignment is obtained by explicit modeling of forces acting on the particles as well as their velocities and displacements with second-order ordinary differential equations of motion. Additional alignment cues (point-based or geometric features, and other boundary conditions) can be integrated into FGA through particle masses. We propose a smooth-particle mass function for point mass initialization, which improves robustness to noise and structural discontinuities. To avoid prohibitive quadratic complexity of all-to-all point interactions, we adapt a Barnes-Hut tree for accelerated force computation and achieve quasilinear computational complexity. We show that the new method class has characteristics not found in previous alignment methods such as efficient handling of partial overlaps, inhomogeneous point sampling densities, and coping with large point clouds with reduced runtime compared to the state of the art. Experiments show that our method performs on par with or outperforms all compared competing non-deep-learning-based and general-purpose techniques (which do not assume the availability of training data and a scene prior) in resolving transformations for LiDAR data and gains state-of-the-art accuracy and speed when coping with different types of data disturbances.
BibTeX
@inproceedings{ali2021fast,
  author = {Sk Aziz Ali and Kerem Kahraman and Christian Theobalt and Didier Stricker and Vladislav Golyanik},
  title = {{Fast Gravitational Approach for Rigid Point Set Registration with Ordinary Differential Equations}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=l5UNGXGci1J},
}
Figure