CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration

Kaveh Fathian, Tyler H. Summers

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:

  1. It first runs the fast greedy algorithm to find an initial maximal clique.
  2. 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.
  3. 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.
  4. 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

Abstract

We present CLIPPER+, an algorithm for finding maximal cliques in unweighted graphs for outlier-robust global registration. The registration problem can be formulated as a graph and solved by finding its maximum clique. This formulation leads to extreme robustness to outliers; however, finding the maximum clique is an NP-hard problem, and therefore approximation is required in practice for large-size problems. The performance of an approximation algorithm is evaluated by its computational complexity (the lower the runtime, the better) and solution accuracy (how close the solution is to the maximum clique). Accordingly, the main contribution of CLIPPER+ is outperforming the state-of-the-art in accuracy while maintaining a relatively low runtime. CLIPPER+ builds on prior work (CLIPPER Lusk et al. (2021) and PMC Rossi et al. (2015)) and prunes the graph by removing vertices that have a small core number and cannot be a part of the maximum clique. This will result in a smaller graph, on which the maximum clique can be estimated considerably faster. We evaluate the performance of CLIPPER+ on standard graph benchmarks, as well as synthetic and real-world point cloud registration problems. These evaluations demonstrate that CLIPPER+ has the highest accuracy and can register point clouds in scenarios where over 99% of associations are outliers. Our code and evaluation benchmarks will be released at https://github.com/ariarobotics/clipperp.
BibTeX
@article{fathian2024clipper,
  author = {Kaveh Fathian and Tyler H. Summers},
  title = {{CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2024},
  url = {https://openreview.net/forum?id=PS3jKe3EEY},
}
Figure