Semidefinite Relaxations for Robust Multiview Triangulation

• URL: http://arxiv.org/abs/2301.11431v4
• Date: Wed, 5 Apr 2023 07:11:11 GMT
• Title: Semidefinite Relaxations for Robust Multiview Triangulation
• Authors: Linus H\"arenstam-Nielsen, Niclas Zeller, Daniel Cremers
• Abstract summary: We extend existing relaxation approaches to non-robust multiview triangulation by incorporating a truncated least squares cost function. We demonstrate through extensive experiments that the proposed approaches allow us to compute provably optimal reconstructions even under significant noise and a large percentage of outliers.
• Score: 53.360555898338106
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an approach based on convex relaxations for certifiably optimal robust multiview triangulation. To this end, we extend existing relaxation approaches to non-robust multiview triangulation by incorporating a truncated least squares cost function. We propose two formulations, one based on epipolar constraints and one based on fractional reprojection constraints. The first is lower dimensional and remains tight under moderate noise and outlier levels, while the second is higher dimensional and therefore slower but remains tight even under extreme noise and outlier levels. We demonstrate through extensive experiments that the proposed approaches allow us to compute provably optimal reconstructions even under significant noise and a large percentage of outliers.

Related papers

• Suppression of noise in separation estimation of optical sources with spatial-mode demultiplexing [0.0]
  Superresolution brought by spatial mode demultiplexing deteriorates rapidly. We propose a formal procedure to suppress the destructive effect of the noise. This allows for a recovery of superresolution for a special class of noise generated by displacement operators.
  arXiv  Detail & Related papers  (2024-07-02T07:08:26Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  We revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits. We show that our algorithms succeed where conventional methods fail.
  arXiv  Detail & Related papers  (2020-10-08T17:59:05Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Robust Uncertainty-Aware Multiview Triangulation [20.02647320786556]
  We propose a robust and efficient method for multiview triangulation and uncertainty estimation. Our contribution is threefold: First, we propose an outlier rejection scheme using two-view RANSAC with the midpoint method. Second, we compare different local optimization methods for refining the initial solution and the inlier set. Third, we model the uncertainty of a triangulated point as a function of three factors: the number of cameras, the mean reprojection error and the maximum parallax angle.
  arXiv  Detail & Related papers  (2020-08-04T00:47:42Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers [32.1176248075545]
  We propose the first general and practical to design certifiable algorithms for perception in the presence of a large amount of outliers. Our dual certifiers leverage solution-of-any suboptimal optimality of any problem.
  arXiv  Detail & Related papers  (2020-06-11T19:46:42Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.