  This paper presents a novel randomized algorithm for robust point cloud
registration without correspondences. Most existing registration approaches
require a set of putative correspondences obtained by extracting invariant
descriptors. However, such descriptors could become unreliable in noisy and
contaminated settings. In these settings, methods that directly handle input
point sets are preferable. Without correspondences, however, conventional
randomized techniques require a very large number of samples in order to reach
satisfactory solutions. In this paper, we propose a novel approach to address
this problem. In particular, our work enables the use of randomized methods for
point cloud registration without the need of putative correspondences. By
considering point cloud alignment as a special instance of graph matching and
employing an efficient semi-definite relaxation, we propose a novel sampling
mechanism, in which the size of the sampled subsets can be larger-than-minimal.
Our tight relaxation scheme enables fast rejection of the outliers in the
sampled sets, resulting in high-quality hypotheses. We conduct extensive
experiments to demonstrate that our approach outperforms other state-of-the-art
methods. Importantly, our proposed method serves as a generic framework which
can be extended to problems with known correspondences.
