  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.
