3D Registration with Maximal Cliques

In plain words

Lining up two 3D scans of the same object or room means finding the rotation and shift that make them match. Usually you first guess which points in one scan correspond to points in the other, and many of those guesses are wrong. Wrong guesses can ruin the alignment.

This method checks pairs of guessed matches against each other. Two matches are compatible when the distance between their points is about the same in both scans. Groups of matches that are all compatible with each other form consistent sets. The method keeps the complete sets (ones that cannot grow by adding another match), chooses one for each match, computes an alignment from each set, and keeps the best alignment. It needs no training data. It can also be added on top of learned matchers to make them more accurate.

TL;DR

MAC is a geometric-only, training-free method for 3D point cloud registration. It takes putative correspondences (from FPFH, FCGF or a learned descriptor) and returns one rigid transform. Its key step is searching maximal cliques in a second-order compatibility graph instead of a single maximum clique. The authors report the best or tied-best recall on 3DMatch, 3DLoMatch and KITTI against the baselines they list, and gains when plugged into deep methods. Several parameters differ between paper and code; see Paper vs code.

Problem

Feature matching produces correspondence sets with many outliers, especially under low overlap and noise §1. RANSAC-style sampling degrades as the outlier rate rises and needs many iterations §1. Branch-and-bound global methods are costly for large or highly contaminated sets §2.1. Earlier clique-based work searched for a single maximum clique, which is a tight constraint that uses only global consensus §3.3. Deep methods need training data and often generalise poorly across datasets §1.

Method

The method works on correspondences c = (p^s, p^t), where p^s and p^t are matched points in the source and target clouds §3.1. Each step below is described in the paper; the MAE score and post-refinement are not part of the paper's text (see Paper vs code).

Graph construction §3.2. Each correspondence is a node. The first-order graph (FOG) scores each pair by how well their point distances agree eq. 1. The score is a Gaussian of that mismatch with width d_cmp eq. 2. A pair becomes an edge if its score is above t_cmp; the edge weight is the score, and otherwise the weight is zero. The graph is undirected, so the weight matrix is symmetric §3.2.

The second-order graph (SOG), the paper's default, multiplies each FOG weight elementwise by the product of the FOG weight matrix with itself eq. 3. This keeps an edge only when the two nodes share compatible neighbours, which makes the graph sparser and stricter §3.2 app. A. The per-edge form is given in app. A, eq. 7.

Maximal cliques §3.3. A maximal clique is one that no node can be added to. Maximal cliques are enumerated with igraph's modified Bron-Kerbosch routine §3.3. The paper gives worst-case cost O(d(n-d)3^(d/3)), where d is the graph degeneracy, and notes that d is small for sparse correspondence graphs §3.3.

Node-guided selection §3.3. Each clique is weighted by the sum of its pairwise edge weights eq. 4. Each node keeps only the heaviest maximal clique that contains it, and duplicates are removed. The result has at most one clique per node §3.3.

Optional filters §3.3. Normal consistency keeps pairs whose normal angles agree: the absolute difference of the sines of the source and target angles must be below a threshold t_α eq. 5. The value of t_α is not stated. Clique ranking sorts the cliques by weight and keeps the top K §3.3. The paper reports that normal consistency slightly lowers results and that K = 100 already performs well tab. 5.

Hypothesis and selection §3.4. Each remaining clique gives a rigid transform by SVD. The default is instance-equal weighting (all correspondences weigh the same). A weighted variant is tested and performs slightly worse §3.4 §4.5. The paper's objective maximises a sum of per-correspondence scores over the transform eq. 6, and considers MAE, MSE and inlier count as evaluation metrics §3.4. The best hypothesis is used for the final registration §3.4.

Pipeline, in pseudocode:

# MAC registration  [§3]
# Input:  src (N, 3), tgt (N, 3): N putative correspondences; pr (scalar)
# Output: rigid transform (R, t) in SE(3)

def mac_register(src, tgt, pr, d_cmp, t_cmp, tau):
    # 1. First-order compatibility weights  [§3.2] [eq. 1] [eq. 2]
    fog = first_order_weights(src, tgt, d_cmp, t_cmp)     # (N, N)
    # 2. Second-order weights: elementwise fog * (fog @ fog)  [§3.2] [eq. 3]
    sog = fog * (fog @ fog)                               # (N, N)
    # 3. All maximal cliques with at least 3 nodes  [§3.3] [§4.1]
    cliques = maximal_cliques(sog, min_size=3)
    # 4. Clique weight = sum of pairwise edge weights  [§3.3] [eq. 4]
    weights = [clique_weight(c, sog) for c in cliques]
    # 5. Each node keeps its heaviest clique; duplicates removed  [§3.3]
    selected = node_guided_selection(cliques, weights, num_nodes=N)
    # 6. One instance-equal SVD fit per selected clique  [§3.4]
    hypotheses = [svd_fit(src[c], tgt[c]) for c in selected]
    # 7. Score each hypothesis with MAE (code, not paper text)  [§3.4]
    scores = [mae_score(h, src, tgt, tau) for h in hypotheses]
    # 8. Return the best-scoring hypothesis  [§3.4]
    return hypotheses[argmax(scores)]

First-order weights and the MAE score, as implemented in the code:

# First-order compatibility  [§3.2] [eq. 1] [eq. 2]
# d_cmp is 10 * pr by default  [§4.1]
def first_order_weights(src, tgt, d_cmp, t_cmp):
    # Pairwise distances inside each cloud  [§3.2]
    dist_src = pairwise_distance(src)                     # (N, N)
    dist_tgt = pairwise_distance(tgt)                     # (N, N)
    # Rigid-distance mismatch of each pair  [eq. 1]
    mismatch = abs(dist_src - dist_tgt)                   # (N, N)
    # Gaussian compatibility score  [eq. 2]
    score = exp(-mismatch**2 / (2 * d_cmp**2))            # (N, N)
    # Zero out weights at or below t_cmp, so only edges remain  [§3.2]
    score[score <= t_cmp] = 0
    # No self-loops  [code: Python_implement/example.py#L157]
    fill_diagonal(score, 0)
    return score

# MAE hypothesis score  [§3.4] [code: Linux/PCR.cpp#L395-L420]
# The paper names MAE but its text gives no formula.
def mae_score(trans, src, tgt, tau):
    # Residual distance of each correspondence after the transform
    residual = norm(apply(trans, src) - tgt, axis=1)   # (N,)
    # Count only residuals below tau; each adds (tau - d) / tau
    inlier = residual < tau
    return sum(((tau - residual) / tau)[inlier])

Hyperparameters

Post-refinement is in the code only. The Python script repeats the loop below until the inlier count stops rising. It fits a weighted SVD on the current inliers, with weights 1 / (1 + (d / tau)^2) and tau = 0.1 [code: Python_implement/example_with_fpfh_fcgf.py#L93-L109]:

# Post-refinement, Python variant
# [code: Python_implement/example_with_fpfh_fcgf.py#L93-L109]
def refine(trans, src, tgt, tau, iters=20):
    previous_count = 0
    for _ in range(iters):
        # Residuals of all correspondences under the current transform
        residual = norm(apply(trans, src) - tgt, axis=1)
        inlier = residual < tau
        # Stop when the inlier count no longer rises
        if count(inlier) <= previous_count:
            break
        previous_count = count(inlier)
        # Weighted SVD on the current inliers
        weights = 1 / (1 + (residual[inlier] / tau)**2)
        trans = weighted_svd_fit(src[inlier], tgt[inlier], weights)
    return trans

Results

All numbers are author-reported. Recall (RR) is the percentage of pairs that meet the success criteria; RE is in degrees and TE in centimetres. Baselines are the authors' choices. Results use FPFH or FCGF correspondences, unless stated.

The 5000-match column of tab. 3 is the source of the headline 95.7% / 78.9%. The main 3DMatch tables do not state a sample count.

Paper vs code

The code is the authors' repository, linked from the paper's footnote §1. Commit b0d19635c4c9d69399397495d02422eda94248c2, MIT licence. The repository has C++ (Linux, Windows) and a Python demo. The C++ path is the one that contains the benchmark-specific settings (dataset branches, descriptor branches), and the Python demo is a simpler subset.

• Graph kernel. The paper gives one Gaussian kernel eq. 2. The C++ default for 3DMatch and 3DLoMatch uses that Gaussian PCR.cpp. The C++ KITTI path uses a linear kernel 1 - d^2 / tau^2 with tau = 0.6 PCR.cpp. The Python demos use the linear kernel with tau = 0.1 m, not 10 pr example.py. The C++ predator and low-inlier paths also use the linear kernel PCR.cpp.
• Compatibility threshold. The paper says t_cmp = 0.99, rising to 0.999 above 5000 matches §4.1. The code uses 0.999 for FCGF and 0.995 for FPFH on 3DMatch, whatever the count PCR.cpp. KITTI uses 0.999 for FCGF and 0.9 for FPFH PCR.cpp. The 0.99 default is in the paper; the code also has 0.85 for SpinNet and D3Feat PCR.cpp.
• MAE inlier threshold. The paper never gives tau for MAE (see the table above). The code uses 0.1 m for 3DMatch and 3DLoMatch, 0.6 m for KITTI and 5 x resolution for U3M registration.cpp.
• Refinement. The paper's text does not describe any refinement. The C++ code runs up to 20 iterations of MAE-based refinement on the chosen hypothesis registration.cpp, and the function stops when the score stops rising PCR.cpp. The Python demo's refinement stops when the inlier count stops rising [code: Python_implement/example_with_fpfh_fcgf.py#L93-L109].
• Clique size. The paper uses a minimum of 3 §4.1. The code call uses 3, but its comment says 4 for 3DMatch registration.cpp.
• Top-K and normal consistency. The paper lists both as techniques §3.3. The default C++ path has top-K disabled (unbounded) and the normal-consistency block commented out registration.cpp, registration.cpp.
• Normal estimation. The paper says 20 nearest neighbours §4.1. The active C++ FPFH normals use a radius search desc_dec.cpp; the 20-neighbour setting is in a commented-out block desc_dec.cpp.
• Objective score. The paper's objective uses a per-correspondence score s(c_i) eq. 6, which the compiled text does not define. The code's score is MAE summed over all correspondences PCR.cpp.
• Node-guided selection. The Python demos drop cliques whose weight is zero example.py. The paper does not say this.
• Translation error. The Python demos report TE as the translation norm times 100, i.e. centimetres for metre-scale clouds example.py.
• Matching rule. The Python demos form correspondences by one-way nearest neighbour in feature space example_with_fpfh_fcgf.py. The paper says only that correspondences are formed by matching descriptors §3.1.
• Resolution. The code computes pr as the mean of the source and target mesh resolutions registration.cpp. The paper leaves pr to an external reference §4.1.

Pitfalls

• Three kernel forms in the repository. Gaussian (paper, C++ default), linear with tau = 0.1 m (Python, C++ predator path), and linear with tau = 0.6 m (C++ KITTI). Pick the one you mean and say so when comparing numbers.
• The Python demo can return the identity. In the FPFH/FCGF script, if len(group) == 1: continue example_with_fpfh_fcgf.py skips every hypothesis when all surviving cliques have three nodes, so the output is the identity transform. The basic demo has the same check at example.py and lacks the empty-group guard that the FPFH/FCGF script adds example_with_fpfh_fcgf.py.
• The demo picks the refined result with ground truth. The FPFH/FCGF script keeps the refined transform only if its RE and TE are both lower than the unrefined ones example_with_fpfh_fcgf.py. That uses the ground truth, so it cannot run on unseen data. Use the score instead.
• Maximal cliques can be expensive. The worst case is exponential in the degeneracy §3.3. At 5000 correspondences the search takes 48.37% of total time, and total time is 3265.42 ms tab. 8. Memory at 5000 is 150.86 MB tab. 13. The paper reports MAC as far cheaper in memory than PointDSC and TEASER++ at the same size tab. 13.
• Two timing tables disagree. At 5000 correspondences, tab. 8 gives 3265.42 ms and tab. 12 gives 3259.38 ms. The paper does not explain the gap.
• Evaluation is the bottleneck. With a perfect judge, MAC-1 reaches 98.46% / 91.24% recall tab. 7, so hypothesis scoring, not clique generation, limits results §4.5. The paper says so in its limitation §5.
• Weighted SVD is ambiguous. The paper says the weights are "the primary eigenvalues" of W_SOG §3.4. The code uses instance-equal weighting by default. The paper finds weighting slightly worse §4.5.
• Degenerate inputs. Cliques of zero weight are dropped in the demos example.py but the paper does not say so. If enumeration finds no clique, the C++ code prints "NO CLIQUES!" registration.cpp; the paper does not describe this case.
• Baseline labelling on ETH. The text says the 24.2% and 18.51% gains are over RANSAC-50K app. B. The table lists only the FPFH, FCGF and SpinNet base rows tab. 11; the RANSAC row is not in the table.
• Threshold choice changes the graph. The code uses 0.85 for SpinNet and D3Feat PCR.cpp, far below the paper's 0.99 default. The paper's timing tables cover only the Predator correspondences tab. 8, so runtime for other descriptors at these thresholds is not reported.

Lineage

• Builds on: second-order compatibility from SC2-PCR (Chen et al., 2022) §3.2; RANSAC-style hypothesis evaluation metrics from Yang et al. (2021) §3.4; igraph's maximal-clique routine (Eppstein et al., 2010) §3.3.
• Compared against: RANSAC variants, SAC-COT, GC-RANSAC, TEASER++, CG-SAC, SC2-PCR, SM, FGR, GO-ICP §2 §4.2 §4.3; deep methods 3DRegNet, DGR, DHVR, PointDSC, CoFiNet, Predator, GeoTransformer §4.3 tab. 3.
• Superseded by: not known from this wiki. The repository README links a 2024 TPAMI version of the same work and a follow-up named MAC++ (3DV 2025). Neither is covered by this card.