GESAC: Robust graph enhanced sample consensus for point cloud registration

Pairwise point cloud registration (PCR) is a crucial problem in photogrammetry, which aims to find a rigid transformation that registers a pair of point clouds. Typically, PCR is performed in a coarse-to-fine manner. Coarse registration provides good initial transformations for fine registration, which determines whether the PCR can succeed. RANSAC-based correspondence registration is the most popular technique for coarse registration. However, the outlier rate of feature correspondences extracted from point clouds is generally very high. Current RANSAC-variants require a huge number of trials to achieve satisfactory results at high outlier rates. This paper proposes a fast and robust RANSAC-variant for PCR, called graph enhanced sample consensus (GESAC). GESAC improves classic RANSAC-family in both sampling and model fitting steps. In the sampling, GESAC generates a much larger subset instead of a minimal subset for model fitting. RANSAC-variants treat a subset as a good one only if the correspondences in the subset are all inliers. In contrast to RANSAC-variants, GESAC allows outliers in the subset and only requires three inliers in the case of point cloud coregistration. Hence, the probability to obtain good subsets of GESAC is much larger than the ones of classic RANSAC-variants. GESAC uses an equal-length constraint to filter degraded subsets and expresses a subset as a graph. Then, a max-pooling graph matching strategy is applied to remove potential outliers in the subset. In the model fitting, GESAC introduces a shape-annealing robust estimate instead of classic least-squares for rigid transformation estimation. Hence, even if the subset cleaned by graph matching still contains outliers, GESAC is able to recover a correct solution for PCR. Both simulated and real experiments demonstrate the power of GESAC, i.e., it can tolerate up to more than 99% outliers and is 4000 + times faster than RANSAC at outlier rates above 99% (Note that the running time of feature extraction is not included).