TL;DR
This paper introduces CLIPPER+, a novel algorithm for robustly aligning 3D point clouds, even when faced with extremely high percentages of incorrect initial correspondences (over 99% outliers). CLIPPER+ achieves this by reformulating the problem as finding a maximum clique in a graph and introducing an efficient pruning strategy that significantly speeds up computation while maintaining state-of-the-art accuracy.
What Problem Does This Paper Address?
Accurately aligning 3D point clouds from sensors like LiDAR or depth cameras is crucial for many robotics and computer vision tasks, such as simultaneous localization and mapping (SLAM) and object recognition. A key challenge is "data association" – correctly matching points from one cloud to another. Initial matching methods, often based on local features, can produce a large number of incorrect associations (outliers). Traditional robust methods like RANSAC struggle with extremely high outlier ratios (e.g., >95%), either failing or becoming computationally infeasible. While formulating this as a maximum clique problem offers theoretical robustness, finding the maximum clique is NP-hard, necessitating efficient approximation algorithms.
Methods
CLIPPER+ combines two main algorithmic approaches:
- Degeneracy-Ordered Greedy Maximal Clique (Algorithm 1): This is a fast heuristic that greedily builds a clique by prioritizing vertices with higher "core numbers" (a measure of a vertex's connectivity after recursively removing low-degree vertices). It's quick but can be less accurate on dense graphs.
- Continuous-Relaxation Maximal Clique (Algorithm 2): This approach uses a continuous optimization technique to find a maximal clique. It relaxes the binary constraint of clique membership into a continuous domain, allowing gradient-based optimization. This method is more accurate but computationally more expensive.
CLIPPER+'s novelty lies in how it combines these:
- It first runs the fast greedy algorithm to find an initial maximal clique.
- It then uses the "core number" property: if a larger clique exists, its vertices must have core numbers at least as high as the size of the initial greedy clique. This allows CLIPPER+ to prune the graph, removing vertices that cannot possibly be part of a larger clique.
- The more accurate continuous-relaxation algorithm is then applied to this smaller, pruned graph. This significantly reduces computation time while leveraging the accuracy of the optimization approach.
- The best clique found by either the greedy or the optimized approach on the pruned graph is returned.
Datasets
The paper evaluates CLIPPER+ on:
- DIMACS benchmark graphs: Standard, often dense graphs used for testing maximum clique algorithms.
- Synthetic and real-world point cloud registration problems:
- Stanford Bunny dataset: A common benchmark for point cloud registration.
- 7-Scenes, Sun3D, and ETH datasets: Real-world indoor (RGB-D) and outdoor (LiDAR) point cloud sequences.
The authors also mention releasing their code and evaluation benchmarks.
Key Insights and Ideas
- Core Number as a Pruning Heuristic: The insight that vertices in a larger clique must have a minimum core number is crucial. This allows for significant graph reduction before applying computationally intensive algorithms, leading to substantial speedups.
- Combining Speed and Accuracy: CLIPPER+ elegantly bridges the gap between fast but potentially inaccurate greedy methods and slow but accurate optimization methods by using the former to prepare the problem for the latter.
- Extreme Outlier Robustness: The graph formulation naturally handles high outlier ratios. CLIPPER+'s efficiency makes this robust approach practical for real-world scenarios where outlier percentages can exceed 99%.
- Maximal vs. Maximum Clique: While finding the maximum clique is NP-hard, CLIPPER+ aims for the maximum but guarantees finding a maximal clique. The paper shows that in practice, it often finds the true maximum clique, especially in registration scenarios.
Key Results
- Accuracy: CLIPPER+ consistently outperforms state-of-the-art algorithms (Pelillo, Ding, Belachew, CLIPPER, Greedy, Optim) in maximum clique estimation accuracy across various benchmarks.
- Robustness: It successfully registers point clouds in scenarios with over 99% outlier associations, a feat where other methods struggle or fail.
- Runtime: While the greedy component is fast, CLIPPER+'s overall runtime is significantly better than the standalone optimization approach, especially as outlier percentages increase and graphs become sparser due to pruning. For example, on the brock200_2 DIMACS graph, it achieved a ~10x reduction in runtime compared to the optimization-only approach.
- Real-world Performance: On real-world registration datasets (7-Scenes, Sun3D, ETH), CLIPPER+ achieved the highest accuracy and was competitive in runtime, often outperforming the standalone optimization component by ~2x.
Limitations and Future Work
- NP-Hardness: While CLIPPER+ is efficient, finding the true maximum clique remains NP-hard. The algorithm finds a maximal clique, which is often the maximum in practice but not guaranteed.
- Future Work:
- Investigate alternative optimization methods (e.g., second-order or quasi-Newton methods).
- Extend the algorithm to handle weighted graphs.
- Explore extensions of core numbers to weighted settings.
- Integrate CLIPPER+ as an outlier rejection module in existing point cloud registration pipelines to improve their runtime and outlier rejection capabilities.
Summary updated