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.
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.
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