Efficient Large Scale Generalized Voting for Geometric Vision Problems
Abstract
Outlier rejection and equivalently inlier set optimization
is a key ingredient in numerous applications in computer vision such as filtering point-matches in camera pose estimation or plane and normal estimation in point clouds. Several
approaches exist, yet at large scale we face a combinatorial
explosion of possible solutions and state-of-the-art methods
like RANSAC, Hough transform or Branch&Bound require
a minimum inlier ratio or prior knowledge to remain practical. In fact, for problems such as camera posing in very
large scenes these approaches become useless as they have
exponential runtime growth if these conditions aren’t met.
To approach the problem we present a efficient and general algorithm for outlier rejection based on “intersecting”
k-dimensional surfaces in Rd
. We provide a recipe for casting a variety of geometric problems as finding a point in
Rd which maximizes the number of nearby surfaces (and
thus inliers). The resulting algorithm has linear worst-case
complexity with a better runtime dependency in the approximation factor than competing algorithms while not requiring domain specific bounds. This is achieved by introducing a space decomposition scheme that bounds the number of computations by successively rounding and grouping
samples. Our recipe (and open-source code) enables anybody to derive such fast approaches to new problems across
a wide range of domains. We demonstrate the versatility
of the approach on several camera posing problems with a
high number of matches at low inlier ratio achieving stateof-the-art results at significantly lower processing times.
is a key ingredient in numerous applications in computer vision such as filtering point-matches in camera pose estimation or plane and normal estimation in point clouds. Several
approaches exist, yet at large scale we face a combinatorial
explosion of possible solutions and state-of-the-art methods
like RANSAC, Hough transform or Branch&Bound require
a minimum inlier ratio or prior knowledge to remain practical. In fact, for problems such as camera posing in very
large scenes these approaches become useless as they have
exponential runtime growth if these conditions aren’t met.
To approach the problem we present a efficient and general algorithm for outlier rejection based on “intersecting”
k-dimensional surfaces in Rd
. We provide a recipe for casting a variety of geometric problems as finding a point in
Rd which maximizes the number of nearby surfaces (and
thus inliers). The resulting algorithm has linear worst-case
complexity with a better runtime dependency in the approximation factor than competing algorithms while not requiring domain specific bounds. This is achieved by introducing a space decomposition scheme that bounds the number of computations by successively rounding and grouping
samples. Our recipe (and open-source code) enables anybody to derive such fast approaches to new problems across
a wide range of domains. We demonstrate the versatility
of the approach on several camera posing problems with a
high number of matches at low inlier ratio achieving stateof-the-art results at significantly lower processing times.
Research Areas
