Abstract
Functional registration algorithms represent point clouds as functions, such as spatial occupancy fields, to avoid the unreliable correspondence estimation inherent in conventional least-squares registration. However, existing functional methods are often computationally prohibitive and lack support for unknown scale—a critical requirement for tasks like CAD model-based object localization. In this work, we propose FLS (Functional Least-Squares), a scale-invariant functional registration algorithm with linear time complexity. By approximating the $L_2$-distance between functions using orthonormal basis functions, we achieve $O(N)$ complexity. This formulation allows us to leverage Translation-Rotation-Invariant Measurements (TRIMs) to decouple and estimate scale independently. Evaluation on standard 3D benchmarks demonstrates that FLS is an order of magnitude faster than state-of-the-art functional methods while maintaining superior robustness to noise, varying densities, and partial overlaps compared to correspondence-based approaches.
Introduction
Point cloud registration—the process of determining the optimal rotation, translation, and scale to align two 3D datasets—is a cornerstone of robotics and computer vision. Traditional algorithms typically rely on finding point-to-point correspondences. However, these methods often fail when faced with high noise, varying point densities, or significant outliers, as matching individual points becomes mathematically unstable.
Functional registration offers a robust alternative by treating point clouds as continuous density fields. Despite their advantages, functional methods have historically suffered from $O(N^2)$ computational complexity and an inability to handle scale variations. FLS addresses these gaps, providing a fast, scale-invariant framework suitable for real-time applications.
Methodology
The Delta-Mixture Representation
FLS represents a point cloud as a sum of Dirac delta functions. To facilitate efficient optimization, these functions are projected onto a set of orthonormal basis functions (specifically, normalized Fourier bases). This projection transforms the registration problem from the spatial domain to a coefficient domain.
Linear Complexity ($O(N)$)
One of the primary innovations of FLS is the "averaging shortcut." The authors demonstrate that mapping an unordered set of points to a set of function coefficients is equivalent to averaging the basis functions over the point set. Because this requires only a single pass over the data, the algorithm achieves linear time complexity, making it significantly faster than previous functional registration frameworks like Continuous Sensor Registration (CSR).
Sobolev Norm Weighting
To improve convergence, FLS employs Sobolev norm weighting. By applying diminishing weights to high-frequency basis functions, the algorithm prioritizes the "global structure" of the shape during the initial phases of alignment. This hierarchical approach prevents the optimization from getting trapped in local minima caused by fine-grained noise or small-scale surface details.
Decoupled Scale Estimation
To handle unknown scales (e.g., matching a sensor scan to a CAD model of a different unit), FLS utilizes Translation-Rotation Invariant Measurements (TRIMs). By analyzing the distribution of internal distances within a point cloud, the algorithm can estimate the relative scale between two objects independently of their orientation or position. This decoupling simplifies the 7-degree-of-freedom optimization problem into more manageable steps.
Experimental Evaluation
Benchmarks and Performance
The algorithm was evaluated using the ModelNet40 dataset, focusing on categories with non-symmetric geometries to ensure rigorous testing. FLS demonstrated the ability to register 10,000 points in under one second on a single CPU, outperforming CSR by an order of magnitude.
Robustness to Noise and Partial Overlap
In scenarios involving partial overlaps and varying point densities, FLS—particularly a hybrid version termed FLS-ICP—achieved a recovery rate of 56%. In contrast, the popular correspondence-based algorithm TEASER failed to recover the alignment (0% recovery rate) under the same high-noise and unknown-scale conditions. FLS also successfully handled scale factors ranging from 2x to 5x, a capability previously absent in functional frameworks.
Real-World Application
The researchers further validated FLS using real-world RGB-D data from an Intel RealSense D435 camera. The algorithm successfully registered noisy, "messy" sensor data, proving its utility for practical robotics tasks where sensor measurements are rarely pristine.
Conclusion and Future Work
FLS represents a significant step forward in functional registration, combining the robustness of global function matching with the speed of linear-time optimization. While the algorithm is currently sensitive to initial orientation (potential for local minima if rotated 180 degrees), its efficiency and scale-invariance make it a powerful tool for 3D vision. Future research may explore using the FLS "delta-distance" metric as a loss function for deep learning pipelines, potentially merging classical geometric principles with modern neural architectures.
Summary updated