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

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

TL;DR

The Fast Gravitational Approach (FGA) is a physics-inspired method that aligns 3D point clouds by simulating them as particle swarms interacting through gravity. By combining second-order ordinary differential equations (ODEs) with Barnes-Hut tree acceleration, FGA achieves state-of-the-art robustness to noise and partial overlaps while maintaining real-time speeds on large-scale LiDAR data.

What Problem Does This Paper Address?

Rigid Point Set Registration (RPSR) is the task of finding the optimal rotation and translation to align two 3D scans. It is a foundational problem in robotics (SLAM), autonomous driving, and 3D reconstruction.

Traditional methods like Iterative Closest Point (ICP) are fast but notoriously sensitive to initial misalignments, noise, and "partial overlaps" (where only parts of the objects are visible in both scans). On the other end of the spectrum, modern deep-learning-based methods often struggle to generalize to new environments they weren't trained on. Physics-based approaches offer a robust alternative by treating alignment as an energy minimization problem, but they have historically been too computationally expensive—scaling quadratically ($O(N^2)$) with the number of points—making them impractical for large datasets like LiDAR scans.

Methods

FGA reimagines the registration problem as a dynamic simulation of $N$-body motion.

  1. Gravitational Simulation: The "source" point set is treated as a swarm of particles moving in a force field induced by a static "target" point set. The goal is to minimize the Gravitational Potential Energy (GPE) between them.
  2. Second-Order ODEs: Unlike many methods that use simple first-order updates, FGA uses second-order ODEs to model particle velocity and displacement. This includes a "dissipative force" (damping) that prevents the particles from oscillating endlessly, allowing the system to settle into a stable, aligned state.
  3. Barnes-Hut Acceleration: To solve the $O(N^2)$ bottleneck, the authors adapt the Barnes-Hut (BH) tree algorithm. By hierarchically partitioning space, distant groups of points are treated as single massive particles, reducing the force calculation complexity to a quasilinear $O(N \log N)$.
  4. Smooth-Particle Masses (SPM): Not all points are created equal. FGA introduces a mass initialization scheme that combines Normalized Intrinsic Volume (NIV)—which weights points based on local density to handle uneven sampling—and Radial Basis Functions (RBF) to incorporate landmark cues if available.
The Barnes-Hut tree structure (A) and force approximation (B) allow FGA to scale efficiently to large point clouds.

Datasets

The authors evaluated FGA across a diverse range of benchmarks:

  • Synthetic Scans: Stanford Bunny (runtime and noise tests) and ModelNet40 (CAD shapes for comparison with deep learning).
  • Indoor Scenes: 3DMatch (low overlap, highly challenging) and Stanford Lounge/Freiburg (RGB-D SLAM data).
  • Outdoor LiDAR: KITTI and Ford Campus datasets, featuring large-scale, non-uniformly sampled point clouds from autonomous driving sensors.

Key Insights and Ideas

  • Correspondence-Free Alignment: Most algorithms spend significant time searching for "nearest neighbors" to establish matches. FGA is correspondence-free; it looks at the global interaction of all points, which makes it inherently more robust to outliers and noise.
  • Physics as a Regularizer: By modeling momentum and damping, the particles are less likely to get "stuck" in poor local minima compared to the purely geometric jumps made by ICP.
  • Handling Density Inhomogeneity: LiDAR sensors produce much denser point clouds near the sensor than far away. The NIV mass initialization effectively "normalizes" these densities, ensuring that the alignment isn't biased toward high-density regions.
  • Optimization Momentum: The authors show that the time integration step ($\Delta t$) in their ODEs acts similarly to momentum in deep learning optimizers, helping the system traverse the energy landscape efficiently.
The GPE function plot shows how different time steps ($\Delta t$) affect the optimization trajectory toward the global minimum.

Key Results

FGA demonstrates a rare combination of accuracy, speed, and robustness:

  • Speed: The GPU implementation is roughly 100x faster than the CPU version. It can align massive LiDAR frames (~220k points) in just 0.7 seconds, supporting real-time odometry.
  • Robustness: In head-to-head tests against deep learning models like PointNetLK and DCP, FGA showed significantly better generalization. While the neural models' errors spiked when noise levels increased from 1% to 5%, FGA remained stable.
  • State-of-the-Art Performance: 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.
A qualitative comparison shows FGA (top center) achieving the lowest error and high speed compared to a wide array of competitors.

Limitations and Future Work

While FGA is highly robust, it still converges to a locally optimal alignment. If the initial misorientation is extremely large (e.g., 180 degrees), it may still require a good initialization or global search. Additionally, the accuracy of the registration is somewhat dependent on the quality of the feature-based mass initialization (SPM).

The authors suggest that future work could involve extending FGA to estimate non-rigid motion fields, which would be useful for tracking deforming objects or dynamic scenes 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 n-body motion. Additional alignment cues 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 the quadratic complexity of all-to-all point interactions, we adapt a Barnes-Hut tree for accelerated force computation and achieve quasilinear complexity. We show that the new method class has characteristics not found in previous alignment methods such as efficient handling of partial overlaps, inhomogeneous 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 deep-learning-based and general-purpose techniques (which do not take training data) in resolving transformations for LiDAR data and gains state-of-the-art accuracy and speed when coping with different data.
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},
}

Loading related content...

Figure