Abstract
This work describes Barnes-Hut Rigid Gravitational Approach (BH-RGA) - a new rigid point set registration method relying on principles of particle dynamics. Interpreting the inputs as two interacting particle swarms, we directly minimise the gravitational potential energy of the system using non-linear least squares. Compared to solutions obtained by solving systems of second-order ordinary differential equations, our approach is more robust and less dependent on the parameter choice. We accelerate otherwise exhaustive particle interactions with a Barnes-Hut tree and efficiently handle massive point sets in quasilinear time while preserving the globally multiply-linked character of interactions. Among the advantages of BH-RGA is the possibility to define boundary conditions or additional alignment cues through varying point masses. Systematic experiments demonstrate that BH-RGA surpasses performances of baseline methods in terms of the convergence basin and accuracy when handling incomplete, noisy and perturbed data. The proposed approach also positively compares to the competing method for the alignment with prior matches.
Introduction
Point set registration—the task of finding the optimal rotation and translation to align two sets of 3D points—is a fundamental challenge in computer vision and robotics. Traditional approaches are typically divided into local policies, like Iterative Closest Point (ICP), which are fast but prone to local minima, and multiply-linked policies, which are robust but computationally expensive ($O(N^2)$).
BH-RGA bridges this gap by treating point sets as interacting particle swarms. By reformulating the gravitational potential energy (GPE) minimization into a stable optimization problem and utilizing astrophysical acceleration techniques, the method achieves global robustness with quasilinear scaling.
Methods
The BH-RGA framework introduces two primary innovations to achieve high-performance registration:
Altering Physical Laws for Optimization
In standard physics, gravitational potential energy follows a $1/r$ relationship, which is singular at $r=0$ and often requires unstable differential equation solvers. BH-RGA applies a negative elementwise reciprocal transform, making the potential energy proportional to the squared distance between points. This "inverse world" preserves global interaction properties while transforming the problem into a Non-Linear Least Squares (NLLS) optimization, allowing the use of efficient solvers like Levenberg-Marquardt.
Barnes-Hut Acceleration
To resolve the quadratic bottleneck of all-to-all interactions, the method borrows the Barnes-Hut tree from astrophysics. Instead of calculating individual pulls from every point, the algorithm aggregates distant clusters into single centers of mass. This reduces complexity to $O(M \log N)$, enabling the alignment of hundreds of thousands of points. The tree also acts as a multi-resolution representation, allowing the solver to address coarse global structures before refining local details.
Mass as a Feature
Because the system is physics-based, point "mass" can be used to incorporate additional cues:
- Prior Matches: Points with known correspondences can be assigned high mass to anchor the alignment.
- Visual Features: Color or intensity can be mapped to mass values to attract similar points.
- Density Correction: Volumetric Mass Normalization (VMN) ensures that dense clusters do not unfairly dominate the global alignment.
Key Results
BH-RGA was evaluated against synthetic benchmarks (Stanford Bunny) and real-world datasets (KITTI lidar, SINTEL sequences).
- Robustness: In scenarios with 100% uniform noise, BH-RGA maintained a 100% success rate, significantly outperforming ICP and Coherent Point Drift (CPD).
- Scalability: The algorithm aligned 446,000 points in approximately 11 seconds, a task that would take hours for traditional gravitational methods.
- Accuracy: On KITTI lidar data, the method successfully registered frames with high outlier ratios (~20%) without requiring prior pose estimates or subsampling.
As shown in the figure above, the parameter $\gamma$ controls the trade-off between speed and accuracy. Higher $\gamma$ values allow for more granular interactions, refining the alignment at the cost of increased computation.
Conclusion
BH-RGA demonstrates that intentionally altering physical laws can lead to more efficient and stable optimization in computer vision. By combining global gravitational interactions with quasilinear tree-based acceleration, it provides a robust solution for massive point set registration. Future work will explore non-rigid registration and hardware-specific optimizations for further speed gains.
Summary updated