Space-Partitioning RANSAC
This incremental improvement addresses efficiency for computer vision tasks like geometric model estimation, benefiting researchers and practitioners using RANSAC frameworks.
The paper tackles the problem of accelerating RANSAC model quality calculations by proposing a space-partitioning algorithm that reduces run-time by 41% on average without accuracy loss, as tested on fundamental and essential matrix, homography, and radially distorted homography estimation.
A new algorithm is proposed to accelerate 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, it reduces the RANSAC run-time by 41% with provably no deterioration in the accuracy. It can be straightforwardly plugged into state-of-the-art RANSAC frameworks, e.g. VSAC.