Space-Partitioning RANSAC

Abstract

A new algorithm is proposed to accelerate the RANSAC model quality calculations. The method is based on partitioning the joint correspondence space, e.g., 2D-2D point correspondences, into a pair of regular grids. The grid cells are mapped by minimal sample models, estimated within RANSAC, to reject correspondences that are inconsistent with the model parameters early. The proposed technique is general. It works with arbitrary transformations even if a point is mapped to a point set, e.g., as a fundamental matrix maps to epipolar lines. The method is tested on thousands of image pairs from publicly available datasets on fundamental and essential matrix, homography and radially distorted homography estimation. On average, the proposed space partitioning algorithm reduces the RANSAC run-time by 41% with provably no deterioration in the accuracy. When combined with SPRT, the run-time drops to its 30%.It can be straightforwardly plugged into any state-of-the-art RANSAC framework.