CliReg: Clique-based robust Point Cloud Registration

We propose a branch-and-bound algorithm for robust rigid registration of two point clouds in the presence of a large number of outlier correspondences. For this purpose, we consider a maximum consensus formulation of the registration problem and reformulate it as a (large) maximal clique search in a correspondence graph, where a clique represents a complete rigid transformation. Specifically, we use a maximum clique algorithm to enumerate large maximal cliques and a fitness procedure that evaluates each clique by solving a least-squares optimization problem. The main advantages of our approach are i) it is possible to exploit the cutting-edge optimization techniques employed by current exact maximum clique algorithms, such as partial maximum satisfiablity-based bounds, branching by partitioning or the use of bitstrings, etc.; ii) the correspondence graphs are expected to be sparse in real problems (confirmed empirically in our tests), and, consequently, the maximum clique problem is expected to be easy; iii) it is possible to have a good control of suboptimality with a k-nearest neighbour analysis that determines the size of the correspondence graph as a function of k. The new algorithm is called CliReg and has been implemented in C++. To evaluate CliReg, we have carried out extensive tests on a dataset of 540 instances generated from scan-matching models in the public Standford 3D Scanning repository. The results show that CliReg clearly dominates the state-of-the-art (e.g., RANSAC, FGR, and TEASER++) in terms of robustness, with a running time comparable to TEASER++ and RANSAC. In addition, we have implemented a fast variant called CliRegMutual that performs similarly to the fastest heuristic FGR.