Graph-Cut RANSAC: Local optimization on spatially coherent structures

A new local optimization (LO) technique, called Graph-Cut RANSAC, is proposed for RANSAC-like robust geometric model estimation. To select potential inliers, the proposed LO step applies the graph-cut algorithm, minimizing a labeling energy functional whenever a new so-far-the-best model is found. The energy originates from both the point-to-model residuals and the spatial coherence of the points. The proposed LO step is conceptually simple, easy to implement, globally optimal and efficient. Graph-Cut RANSAC is combined with the bells and whistles of USAC. It has been tested on a number of publicly available datasets on a range of problems - homography, fundamental and essential matrix estimation. It is more geometrically accurate than state-of-the-art methods and runs faster or with similar speed to less accurate alternatives.