Accelerating Globally Optimal Consensus Maximization in Geometric Vision

• URL: http://arxiv.org/abs/2304.05156v3
• Date: Thu, 18 Jan 2024 04:19:09 GMT
• Title: Accelerating Globally Optimal Consensus Maximization in Geometric Vision
• Abstract summary: We present a novel, general technique that allows us to branch over an n-1 dimensional space for an n-dimensional problem. The remaining degree of freedom can be solved globally optimally within each bound calculation. We present applications to four fundamental geometric computer vision problems.
• Score: 28.72335941963025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Branch-and-bound-based consensus maximization stands out due to its important ability of retrieving the globally optimal solution to outlier-affected geometric problems. However, while the discovery of such solutions caries high scientific value, its application in practical scenarios is often prohibited by its computational complexity growing exponentially as a function of the dimensionality of the problem at hand. In this work, we convey a novel, general technique that allows us to branch over an n-1 dimensional space for an n-dimensional problem. The remaining degree of freedom can be solved globally optimally within each bound calculation by applying the efficient interval stabbing technique. While each individual bound derivation is harder to compute owing to the additional need for solving a sorting problem, the reduced number of intervals and tighter bounds in practice lead to a significant reduction in the overall number of required iterations. Besides an abstract introduction of the approach, we present applications to four fundamental geometric computer vision problems: camera resectioning, relative camera pose estimation, point set registration, and rotation and focal length estimation. Through our exhaustive tests, we demonstrate significant speed-up factors at times exceeding two orders of magnitude, thereby increasing the viability of globally optimal consensus maximizers in online application scenarios.

Related papers

• Efficient Minimal Solvers for Visual-Inertial Relative Pose Estimation in Multi-Camera Systems [11.678515238325817]
  Estimating the relative poses of multi-camera systems is a fundamental problem in computer vision.<n>We propose two efficient minimal solvers for estimating the relative poses of multi-camera systems using a novel parameterization.
  arXiv  Detail & Related papers  (2026-06-08T13:36:27Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• COMPOSE: Hypergraph Cover Optimization for Multi-view 3D Human Pose Estimation [58.47973015036709]
  3D pose estimation from sparse multi-views is a critical task for action recognition, sports analysis, and human-robot interaction.<n>We propose COMPOSE, a novel framework that formulates multi-view pose correspondence matching as a hypergraph problem.<n> COMPOSE achieves improvements of up to 23% in average precision over previous optimization-based methods and up to 11% over self-supervised end-to-end learned methods.
  arXiv  Detail & Related papers  (2026-01-14T18:50:17Z)
• Scalable h-adaptive probabilistic solver for time-independent and time-dependent systems [7.807210884802377]
  We develop an $h$-adaptive probabilistic solver that can scale to a large number of collocation points.<n>We demonstrate the efficacy of the proposed solver on benchmark PDEs, as well as a time-dependent parabolic PDE formulated in a space-time setting.
  arXiv  Detail & Related papers  (2025-08-13T08:54:18Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management [14.310970006771717]
  We show that LMvinvin based gradient local minima with a non-asymptotic convergence analysis. We show that LMvinvin algorithm is provably convergent global minima with a non-asymptotic convergence analysis.
  arXiv  Detail & Related papers  (2025-02-26T15:13:08Z)
• Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
  We propose a first-order proximal gradient algorithm to solve the perspective relaxation of the problem within a BnB framework. We show that our approach significantly accelerates dual bound computations and is highly effective in providing optimality certificates for large-scale problems.
  arXiv  Detail & Related papers  (2025-02-13T17:14:18Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  Book presents several efforts to tackle this challenge with important scientific implications. It provides alternative optimization schemes that scale well in terms of computational complexity. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
  arXiv  Detail & Related papers  (2022-08-23T18:56:05Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Global optimization using random embeddings [1.2891210250935143]
  We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem.
  arXiv  Detail & Related papers  (2021-07-26T10:45:49Z)
• Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
  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.
  arXiv  Detail & Related papers  (2021-07-25T14:13:07Z)
• Transient growth of accelerated first-order methods for strongly convex optimization problems [1.6114012813668934]
  In this paper, we examine the transient behavior of accelerated first-order optimization algorithms. For quadratic optimization problems, we employ tools from linear systems theory to show that transient growth arises from the presence of non-normal dynamics. For strongly convex smooth optimization problems, we utilize the theory of integral quadratic constraints to establish an upper bound on the magnitude of the transient response of Nesterov's accelerated method.
  arXiv  Detail & Related papers  (2021-03-14T20:01:14Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  We show that the problem of robust mean estimation in the presence of a constant adversarial fraction can be solved by gradient descent. Our work establishes an intriguing connection between the near non-lemma estimation and robust statistics.
  arXiv  Detail & Related papers  (2020-05-04T10:48:04Z)
• Multi-consensus Decentralized Accelerated Gradient Descent [31.76773130271547]
  Decentralized convex optimization problem has wide range of applications in large-scale machine learning, sensor networks, and control theory. We propose novel algorithms that achieve optimal computation complexity and near optimal communication complexity.
  arXiv  Detail & Related papers  (2020-05-02T11:10:32Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

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.