Point cloud registration—the process of aligning multiple 3D scans into a single coordinate framework—is foundational to robotics, medical imaging, and 3D reconstruction. Historically, this task has been dominated by the Iterative Closest Point (ICP) algorithm. While intuitive, ICP suffers from a fundamental computational bottleneck: it relies on an explicit nearest-neighbor search to establish point correspondences at every iteration. For two point clouds of size $N$, this introduces a quadratic complexity ($O(N^2)$) or requires expensive spatial data structures (like $k$-d trees) that fail to scale efficiently for high-resolution sensors or real-time applications. Furthermore, ICP is highly sensitive to initialization and easily trapped by outliers.
To overcome these limitations, recent research has shifted toward eliminating explicit correspondence loops, leveraging continuous functional representations, and adopting stochastic or filtering-based optimization paradigms.
Bypassing Explicit Correspondence Searches
The most direct way to eliminate the $O(N^2)$ nearest-neighbor bottleneck is to avoid explicit point-to-point matching entirely. Instead of asking "which point in cloud A matches which point in cloud B?", modern architectures map raw geometric data directly into a low-dimensional, permutation-invariant space where alignment can be computed globally.
In DeepCLR: Correspondence-Less Architecture for Deep End-to-End Point Cloud Registration, the authors utilize differentiable layers to directly estimate transformation parameters via flow embeddings. By bypassing nearest-neighbor lookups entirely, this architecture achieves inference speeds up to 28 times faster than traditional correspondence-based deep networks, making it viable for high-frequency LiDAR systems.
Similarly, Aoki in PointNetLK: Robust & Efficient Point Cloud Registration Using PointNet unrolls the classical Lucas & Kanade optimization algorithm into a recurrent network. By treating a PointNet architecture as a learnable imaging function, the framework achieves linear computational complexity ($O(N)$) relative to the number of points. This shift from local discrete matching to global feature tracking ensures that the optimization signal remains smooth and robust to initial misalignments. Bauer et al. extend this intuition in ReAgent: Point Cloud Registration Using Imitation and Reinforcement Learning by utilizing global feature embeddings within a reinforcement learning framework, maintaining high real-time inference speeds regardless of point cloud density.
Continuous and Probabilistic Representations
Another powerful strategy redefines what a point cloud is. Instead of treating a scan as a discrete set of coordinates, researchers represent the data as a continuous function or density field. When point clouds are projected onto a shared functional basis, alignment transforms from a combinatorial matching problem into a continuous optimization problem.
Sun et al. demonstrate this in Scale-Invariant Fast Functional Registration through Functional Least-Squares (FLS). By projecting point clouds onto a set of basis functions, they achieve alignment in linear time ($O(N)$). Because the representation is continuous, it inherently smooths out sensor noise and handles partial overlaps gracefully without requiring explicit outlier filtering.
A parallel approach involves mapping unstructured points to a fixed-length distance representation. In Efficient Learning on Point Clouds with Basis Point Sets, Prokudin et al. calculate distances from the point cloud to a predefined set of reference points (Basis Point Sets). This converts variable-sized, unorganized data into a fixed-length vector, allowing lightweight neural networks to execute single-pass mesh registration in under one millisecond. Furthermore, Lawin in Registration Loss Learning for Deep Probabilistic Point Set Registration combines deep feature extraction with probabilistic Gaussian Mixture Models (GMMs). This framework optimizes a registration loss directly, bypassing heavy 3D convolutions and achieving linear complexity while maintaining high precision.
Stochastic and Filtering-Based Optimization
When discrete correspondences or full-batch optimizations are unavoidable, the computational burden can be mitigated by changing how the optimization updates are calculated. Traditional methods process the entire point cloud before applying a single transformation update. Modern approaches borrow techniques from state estimation and deep learning optimization to update poses incrementally.
In Speeding Up Iterative Closest Point Using Stochastic Gradient Descent, Maken et al. replace batch optimization with Stochastic Gradient Descent (SGD). Instead of evaluating the entire dataset to compute a gradient, the algorithm computes correspondences on small, random mini-batches. This allows the system to reach a stable alignment in roughly a single pass through the data, drastically reducing the redundant computations typical of standard ICP.
Alternatively, registration can be framed as a non-linear state estimation problem. Moghari et al. leverage this perspective in Global Registration of Multiple Point Sets: Feasibility and Applications in Multi-fragment Fracture Fixation and A Novel Incremental Technique for Ultrasound to CT Bone Surface Registration Using Unscented Kalman Filtering. By utilizing an Unscented Kalman Filter (UKF), the algorithm processes point data incrementally. This filtering mechanism allows the system to converge using only a subset of available data points, significantly lowering the root-mean-square error and providing robust resistance to poor initial alignments and sensor noise.
Global Proxies and Transformation Spaces
Stitching multiple scans together (multiview registration) typically compounds the computational bottleneck, as exhaustive pairwise matching scales quadratically with the number of scans ($O(M^2)$ for $M$ scans). To maintain efficiency, recent frameworks decouple the scans from each other by anchoring them to a global proxy or optimizing directly within the space of transformations.
Birdal et al. address this in CAD Priors for Accurate and Flexible Instance Reconstruction by registering individual point cloud scans to a common geometric proxy (such as a rough CAD model). This establishes a unified coordinate system with linear complexity ($O(M)$) relative to the number of scans, completely bypassing the need for pairwise alignment and ensuring global consistency even in the presence of dynamic background clutter.
When a geometric prior is unavailable, global consistency can be achieved by diffusing relative transformations across a scan graph. In Multiview registration via graph diffusion of dual quaternions, the authors perform global alignment entirely within the space of transformations using dual quaternions and graph-based diffusion. By shifting the optimization from heavy point-level operations to compact transformation matrices, they reduce processing times by two to three orders of magnitude, enabling near-instantaneous refinement of complex 3D models.
Key Foundational Work
Global Registration of Multiple Point Sets: Feasibility and Applications in Multi-fragment Fracture Fixation (2007) — contributed 1 concept elements to this direction.
A Novel Incremental Technique for Ultrasound to CT Bone Surface Registration Using Unscented Kalman Filtering (2005) — contributed 1 concept elements to this direction.