Efficient Large Scale Inlier Voting for Geometric Vision Problems
- URL: http://arxiv.org/abs/2107.11810v2
- Date: Tue, 27 Jul 2021 10:15:03 GMT
- Title: Efficient Large Scale Inlier Voting for Geometric Vision Problems
- Authors: Dror Aiger, Simon Lynen, Jan Hosang, Bernhard Zeisl
- Abstract summary: Outlier rejection and equivalently inlier set optimization is a key ingredient in numerous applications in computer vision.
We present an efficient and general algorithm for outlier rejection based on "intersecting" $k$-dimensional surfaces in $Rd$.
We demonstrate the versatility of the approach on several camera posing problems with a high number of matches at low inlier ratio.
- Score: 3.1231364554255636
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 $R^d$. We provide a recipe for casting a variety of
geometric problems as finding a point in $R^d$ 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 state-of-the-art results at significantly lower
processing times.
Related papers
- Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
We propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method.
Our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
arXiv Detail & Related papers (2023-12-14T09:53:54Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
We compare 8 popular numerical black-box optimization algorithms on the $L_infty$ star discrepancy problem.
We show that all used solvers perform very badly on a large majority of the instances.
We suspect that state-of-the-art numerical black-box optimization techniques fail to capture the global structure of the problem.
arXiv Detail & Related papers (2023-06-29T14:57:56Z) - Fast and Robust Non-Rigid Registration Using Accelerated
Majorization-Minimization [35.66014845211251]
Non-rigid registration, which deforms a source shape in a non-rigid way to align with a target shape, is a classical problem in computer vision.
Existing methods typically adopt the $ell_p$ type robust norm to measure the alignment error and regularize the smoothness of deformation.
We propose a formulation for robust non-rigid registration based on a globally smooth robust norm for alignment and regularization.
arXiv Detail & Related papers (2022-06-07T16:00:33Z) - Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies.
We present a number of applications where the use of multiple geometric models improves accuracy.
These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
arXiv Detail & Related papers (2021-03-25T14:35:07Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm.
We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound.
We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
arXiv Detail & Related papers (2021-01-19T04:24:23Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and
Applications [25.222024234900445]
This paper introduces two unifying formulations for outlier-robust estimation, Generalized Maximum Consensus (G-MC) and Generalized Truncated Least Squares (G-TLS)
Our first contribution is a proof that outlier-robust estimation is inapproximable: in the worst case, it is impossible to (even approximately) find the set of outliers.
We propose the first minimally tuned algorithms for outlier rejection, that dynamically decide how to separate inliers from outliers.
arXiv Detail & Related papers (2020-07-29T21:06:13Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
Local features provide region-to-region rather than point-to-point correspondences.
We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline.
Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
arXiv Detail & Related papers (2020-07-20T12:07:48Z) - Computing stable resultant-based minimal solvers by hiding a variable [20.402488757146692]
Computer vision applications require robust estimation of camera geometry from a minimal number of input data measurements.
In this paper, we study an interesting alternative sparse-based method for solving sparse systems of equations by hiding one variable.
We show that for the studied problems, our resultant based approach leads to more stable solvers than the state-of-the-art Gr"obner bases-based solvers.
arXiv Detail & Related papers (2020-07-17T07:40:10Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
We propose a formulation for robust non-rigid registration based on a globally smooth robust estimator for data fitting and regularization.
We apply the majorization-minimization algorithm to the problem, which reduces each iteration to solving a simple least-squares problem with L-BFGS.
arXiv Detail & Related papers (2020-04-09T01:45:05Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.