Maximal clique search

Overview

Given putative correspondences with many wrong pairs, build a graph whose nodes are correspondences and whose edges join pairs that agree with each other. A group of nodes that are all joined to each other is a clique, and a clique that cannot grow by one more node is maximal 2305.10854 §3.2 2305.10854 §3.3. Every variant shares this idea: a maximal clique is a set of matches that are consistent with each other, so it is a candidate set of inliers. Variants differ in how the graph is weighted, which cliques are kept, and how each candidate is turned into a transform and scored.

The compatibility test in the registration setting is a rigid-distance check. A pair of matches is compatible when the distance between their source points is close to the distance between their target points 2305.10854 eq. 1.

Variants

Maximal cliques with node-guided selection (MAC)

Build a first-order graph from pairwise distance agreement, then a second-order graph that keeps an edge only when the two nodes also share compatible neighbours 2305.10854 eq. 3. Enumerate all maximal cliques of at least three nodes, weight each by the sum of its edge weights 2305.10854 eq. 4, and keep for each node only its heaviest clique. Fit one rigid transform per kept clique by SVD with equal weights, and choose the best by a score; the paper names mean absolute error and inlier count as options 2305.10854 §3.4. Card: 3D Registration with Maximal Cliques.

The paper argues against the older approach of searching for a single maximum clique, because one clique uses only the global consensus [arxiv:2305.10854 §3.3]. Its own ablation supports that choice on 3DMatch with FPFH: maximal cliques reach 83.86% recall and the maximum-clique row reaches 74.06% 2305.10854 tab. 5.

When to use which

The paper does not compare MAC with every clique-based variant. Results come from its own benchmarks (3DMatch, 3DLoMatch, KITTI, U3M and ETH) and use its chosen baselines 2305.10854 §4.1 2305.10854 §4.2. Numbers from one benchmark should not be read as general speed or accuracy claims.

Implementation sketch

The common core, as the card describes it. Variants change the marked steps.

# Maximal-clique filtering then per-clique fit  [arxiv:2305.10854 §3]
# Input:  src (N, 3), tgt (N, 3): N putative correspondences
# Output: rigid transform (R, t) in SE(3)

def clique_register(src, tgt, d_cmp, t_cmp):
    # Pairwise compatibility from distance agreement  [eq. 1] [eq. 2]
    fog = compat_weights(src, tgt, d_cmp, t_cmp)      # (N, N)
    # Second-order weights, the MAC default  [eq. 3]
    sog = fog * (fog @ fog)                           # (N, N)
    # Every maximal clique with at least 3 nodes  [§3.3]
    cliques = maximal_cliques(sog, min_size=3)
    # Clique weight: sum of pairwise edge weights  [eq. 4]
    w = [clique_weight(c, sog) for c in cliques]
    # Keep the heaviest clique per node, drop duplicates  [§3.3]
    kept = node_guided_select(cliques, w, num_nodes=N)
    # One rigid fit per kept clique, equal weights  [§3.4]
    hyps = [svd_fit(src[c], tgt[c]) for c in kept]
    # Score each hypothesis; MAC uses MAE in the code  [§3.4]
    return best_by_score(hyps, src, tgt)

Variants change the compatibility kernel (in the paper, a Gaussian of the distance mismatch), the order of the graph, the clique filter and the score. The card's Paper vs code section lists the settings the authors' repository uses.

Contradictions

• Compatibility kernel. The paper gives a Gaussian of the distance mismatch 2305.10854 eq. 2. The authors' repository uses a linear kernel for its KITTI path and its Python demos, and the Gaussian for the 3DMatch and 3DLoMatch C++ path. The card lists the file references [card: 2305.10854, Paper vs code].
• Compatibility threshold. The paper sets t_cmp to 0.99, rising to 0.999 above 5000 matches 2305.10854 §4.1. The repository uses other values per dataset and descriptor, for example 0.995 for FPFH on 3DMatch and 0.9 for FPFH on KITTI [card: 2305.10854, Paper vs code].
• Timing. At 5000 matches the paper gives 3265.42 ms in one table and 3259.38 ms in another 2305.10854 tab. 8 2305.10854 tab. 12. The paper does not explain the gap.
• Refinement. The paper's text does not describe a post-refinement step. The repository runs one [card: 2305.10854, Paper vs code], so reported numbers may depend on code the paper does not describe.

Papers

• 3D Registration with Maximal Cliques: training-free point-cloud registration that enumerates maximal cliques of a second-order correspondence graph and keeps one clique per node by weight.