RANSAC for (Quasi-)Degenerate data (QDEGSAC)

Published 10 July 2006

Jan‐Michael Frahm, Marc Pollefeys

DOI10.1109/cvpr.2006.235

Citations121

TL;DR

This paper proposes a framework that estimates the correct relation with the same robustness as RANSAC even for (quasi-)degenerate data and can be applied for the estimation of any relation on any data and is not limited to a special type of relation as previous approaches.

Abstract

The computation of relations from a number of potential matches is a major task in computer vision. Often RANSAC is employed for the robust computation of relations such as the fundamental matrix. For (quasi-)degenerate data however, it often fails to compute the correct relation. The computed relation is always consistent with the data but RANSAC does not verify that it is unique. The paper proposes a framework that estimates the correct relation with the same robustness as RANSAC even for (quasi-)degenerate data. The approach is based on a hierarchical RANSAC over the number of constraints provided by the data. In contrast to all previously presented algorithms for (quasi-)degenerate data our technique does not require problem specific tests or models to deal with degenerate configurations. Accordingly it can be applied for the estimation of any relation on any data and is not limited to a special type of relation as previous approaches. The results are equivalent to the results achieved by state of the art approaches that employ knowledge about degeneracies.

Keywords

Computer Science

International Journal of Computer VisionDistinctive Image Features from Scale-Invariant Keypoints

55,266 Citations2004David Lowe

This paper presents a method for extracting distinctive invariant features from images that can be used to perform reliable matching between different views of an object or scene and can robustly identify objects among clutter and occlusion while achieving near real-time performance.

Communications of the ACMRandom sample consensus

25,463 Citations1981Martin A. Fischler, Robert C. Bolles

New results are derived on the minimum number of landmarks needed to obtain a solution, and algorithms are presented for computing these minimum-landmark solutions in closed form that provide the basis for an automatic system that can solve the Location Determination Problem under difficult viewing.

View PDF

Cambridge University Press eBooksMultiple View Geometry in Computer Vision

20,788 Citations2004Richard Hartley, Andrew Zisserman

Two-View Geometry Estimation Unaffected by a Dominant Plane

216 Citations2005Ondřej Chum, Tomáš Werner +1 more

A RANSAC-based algorithm for robust estimation of ep bipolar geometry from point correspondences in the possible presence of a dominant scene plane is presented, exploiting a theorem that if five or more of seven correspondences are related by a homography then there is an epipolar geometry consistent with the seven-tuple as well as with all correspondences related by the homography.

View PDF

Robust computation and parametrization of multiple view relations

171 Citations2002Philip H. S. Torr, Andrew Zisserman

A new method is presented for robustly estimating multiple view relations from image point correspondences and its use is illustrated for the estimation of fundamental matrices, image to image homographies and quadratic transformations.

An assessment of information criteria for motion model selection

111 Citations2002Philip H. S. Torr

Several model selection methods are compared with a particular emphasis on providing a method that will workfully automatically on real imagery and which will fit to the data without affecting structure, matching or segmentation.

IEEE Transactions on Pattern Analysis and Machine IntelligenceN-dimensional tensor voting and application to epipolar geometry estimation

58 Citations2001Chi–Keung Tang, Gérard Medioni +1 more

The methodology is novel and unconventional, since, unlike most other methods optimizing certain scalar, objective functions, the approach does not involve initialization or any iterative search in the parameter space, and is free of the problem of local optima or poor convergence.