Source-linked AI summary
A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints
Álvaro Parra, Tat-Jun Chin, Frank Neumann, Tobias Friedrich, Maximilian Katzmann
TL;DR
High outlier rates in 3D keypoint correspondences make robust registration costly, while matching with pairwise constraints searches directly for mutually consistent correspondences. The paper formulates that search as maximum clique and proposes a graph-colouring-based algorithm, reporting faster solutions on realistic inputs and presenting the approach as a practical alternative to robust estimation.
Problem
Real 3D point clouds can have outlier rates above 95%, making robust estimation costly; the general matching problem is NP-hard, and the vertex-cover method handles only small instances.
Source: §1 · pp. 1–2Method
The paper reformulates matching with pairwise constraints as maximum clique and uses tree search with graph-colouring-based bounding and pruning.
Source: §1 · p. 2, §3.1 · p. 3Results
The proposed algorithm is one order of magnitude faster than the vertex-cover method and typically globally solves realistic inputs in seconds to minutes.
Source: §1 · p. 2Takeaways & Limitations
The authors conclude that matching with pairwise constraints is practical for point-cloud registration and an excellent alternative to standard robust estimation.
Source: §6 · p. 8The matching problem is NP-hard in general, and the state-of-the-art computer-vision vertex-cover algorithm handles only small instances.
Source: §1 · p. 2
Abstract
from arXiv · showhide
A popular paradigm for 3D point cloud registration is by extracting 3D keypoint correspondences, then estimating the registration function from the correspondences using a robust algorithm. However, many existing 3D keypoint techniques tend to produce large proportions of erroneous correspondences or outliers, which significantly increases the cost of robust estimation. An alternative approach is to directly search for the subset of correspondences that are pairwise consistent, without optimising the registration function. This gives rise to the combinatorial problem of matching with pairwise constraints. In this paper, we propose a very efficient maximum clique algorithm to solve matching with pairwise constraints. Our technique combines tree searching with efficient bounding and pruning based on graph colouring. We demonstrate that, despite the theoretical intractability, many real problem instances can be solved exactly and quickly (seconds to minutes) with our algorithm, which makes our approach an excellent alternative to standard robust techniques for 3D registration.
1. Introduction
3D point-cloud registration commonly starts from keypoint correspondences, but high outlier rates make robust estimation costly. The paper instead seeks the largest pairwise-consistent correspondence subset and formulates this search as maximum clique, reporting faster practical solutions than the vertex-cover approach.
1. Introduction
- Outlier rates exceeding 95% are common in real point clouds, substantially increasing robust-estimation cost.The paper attributes reduced 3D keypoint accuracy relative to 2D counterparts to irregular sampling densities.Source: §1 · p. 1
- Rather than estimate the registration function directly from all correspondences, the method searches for the largest pairwise-consistent subset.Two correspondences are consistent when their distance measure is below a predetermined threshold ε, indicating agreement up to ε with the same rigid transformation.Source: §1 · p. 1
- The resulting problem is matching with pairwise constraints, and the registration function can be estimated afterward from the selected correspondences.The selected subset's size can also serve directly as a similarity score for the shapes.Source: §1 · pp. 1–2
- The proposed maximum-clique algorithm is one order of magnitude faster than the vertex-cover method and typically globally solves realistic inputs in seconds to minutes.The authors identify graph-colouring-based bounding and pruning as vital for practical-sized inputs.Source: §1 · p. 2
- The paper presents matching with pairwise constraints as an alternative to conventional robust fitting for keypoint-based 3D registration.The stated applications of point-cloud registration include object recognition, robotic navigation, and digital reconstruction.Source: §1 · pp. 1–2
2. Graph formulation
The graph formulation represents correspondences as vertices and pairwise consistency as adjacency, making a largest mutually consistent subset a maximum clique. Its complement formulation is minimum vertex cover in the inconsistency graph; the paper also relates these problems to mixed-integer programs and solver baselines.
2. Graph formulation
- A vertex's adjacency set contains its neighboring vertices, and the set's size is its degree.The graph is undirected, with vertices V and edges E.Source: §2 · p. 2
- A maximum clique in the consistency graph gives the largest subset of mutually consistent correspondences; equivalently, a minimum vertex cover in the inconsistency graph removes the fewest correspondences to leave no inconsistent pair.The consistency graph connects pairs with d(ci,cj) ≤ ε, while its complement connects pairs with d(ci,cj) > ε.Source: §2 · p. 2
2.1. MIP solutions
- Both maximum clique and minimum vertex cover can be expressed as mixed-integer programs.The formulations use binary decision variables.Source: §2.1 · pp. 2–3
- The MIP formulations can be solved with industry-grade solvers such as IBM CPLEX and Gurobi Optimiser, which the experiments use as baselines.The paper does not further discuss these mature implementations.Source: §2.1 · p. 3
- Enqvist et al.'s vertex-cover branch-and-bound method uses factor-2 approximation bounding, but the authors report it is generally slower than MIP.Their proposed maximum-clique algorithm is reported to significantly outperform generic MIP solvers.Source: §2.1 · p. 3
- The authors propose a novel maximum-clique (MC) algorithm and report that their experimentation suggests it can significantly outperform generic mixed-integer programming (MIP) solvers.Source: §2.1 · p. 3
3. Maximum clique algorithm
The section presents MCQ as a branch-and-bound basis for the paper’s later algorithm, explaining clique search and graph-colouring bounds. Its pruning uses candidate-set size and colour-based upper bounds to avoid branches that cannot improve the best clique.
3. Maximum clique algorithm
- MCQ serves as the proposed method’s baseline, but the authors report it does not perform well on realistic point-cloud-registration inputs.Source: §3 · p. 3
3.1. BnB
- MCQ explores cliques with a depth-first branch-and-bound search, recursively restricting candidates to vertices adjacent to each expanded vertex.The root candidate set contains all vertices, and the largest clique is recorded when a leaf is reached.Source: §3.1 · p. 3
- The basic bound prunes a branch when the current clique plus all remaining candidates cannot exceed the best clique; removing an expanded vertex is safe because its larger cliques were already explored.The bound compares |R| + |S| with |Rbest|.Source: §3.1 · pp. 3–4
3.2. Pruning with graph colouring
- Graph colouring bounds the largest clique obtainable from a candidate set; fewer colours give a tighter bound, and MCQ greedily colours and expands vertices from right to left.Finding the minimum colouring is NP-hard, so MCQ uses a greedy heuristic and orders vertices by colour.Source: §3.2 · p. 4
4. A faster maximum clique algorithm
The proposed PMC algorithm adds pruning that expands only a selected subset of candidates, alongside graph-colouring bounds. The authors report significant speed-ups from the added selection step, which costs quadratic time per search-tree node.
4. A faster maximum clique algorithm
- PMC expands only a subset C of each candidate set, and its pruning complements the existing graph-colouring technique.PMC is the name given to the resulting Practical Maximum Clique algorithm.Source: §4 · pp. 4–5
- The pruning skips an unexpanded vertex adjacent to an already explored vertex because any clique containing it would already have been reached through that explored vertex.The argument assumes the relevant larger cliques from the explored vertex have already been searched.Source: §4 · p. 5
- The sample search reaches its optimal solution in 7 illustrated steps with Algorithm 3, compared with 12 steps for Algorithm 1.The example uses the same vertex order in both searches.Source: §4 · p. 5, Figure 4 · p. 6
- The authors report significant speed-ups from selecting vertices to skip, with the selection solved in quadratic time once per search-tree node.They equate the selection problem with finding the highest-degree vertex in the subgraph induced by S.Source: §4 · p. 6
5. Results
Across point-cloud scans with very high outlier rates, PMC generally found optimal solutions quickly and outperformed the other tested methods on larger inputs. The experiments compare exact solvers and RANSAC across multiple objects and correspondence-set sizes.
5. Results
- Outlier rates reached 99% across the tested correspondence instances, which were built from eight object scans using N = 1000, 3000, or 5000 correspondences.The scans came from the Stanford 3D Scanning Repository and Mian’s dataset; keypoints used ISS3D and PFH.Source: §5 · pp. 6–7
- The evaluation reports solution size, solver runtime, and SVD-estimated registration errors, with a one-hour timeout for optimization methods.Table 1 presents results for matching with pairwise constraints and RANSAC; a dash denotes a forced timeout.Source: §5 · p. 7, Table 1 · p. 7
- MIP-MC failed to finish within one hour on half of generated instances and took several orders of magnitude longer than PMC when it did finish.MIP-MC generally ran faster than MIP-MVC, but remained impractical under the one-hour limit.Source: §5 · p. 7, Table 1 · p. 7
- PMC generally found the optimum in less than 10 seconds, while MCQ took more than 1000 seconds on two N = 5000 instances and did not converge on every instance.PMC was considerably faster than MCQ at N = 5000, though MCQ performed better at N = 1000.Source: §5 · pp. 7–8, Table 1 · p. 7
- Figure 5 shows input correspondences, the largest pairwise-consistent subset, and the alignment estimated from that subset using SVD for N = 3000.Qualitative results cover all tested objects.Source: Figure 5 · p. 8, §5 · p. 8
- RANSAC’s median runtime was up to one order of magnitude greater than PMC’s across instances with more than 90% outliers.The authors attribute this to RANSAC runtime growing exponentially with outlier ratio.Source: Table 1 · p. 7, §5 · p. 8
6. Conclusions
The conclusion presents matching with pairwise constraints as a practical point-cloud registration approach when formulated as maximum clique. The proposed algorithm combines graph colouring with an additional pruning step to solve maximum clique efficiently.
6. Conclusions
- The authors conclude that maximum-clique formulation makes matching with pairwise constraints practical for point-cloud registration and an alternative to standard robust estimation.Their algorithm combines graph colouring with an additional pruning step.Source: §6 · p. 8