論文の概要: Accelerating Globally Optimal Consensus Maximization in Geometric Vision
- arxiv url: http://arxiv.org/abs/2304.05156v3
- Date: Thu, 18 Jan 2024 04:19:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-19 20:58:22.637158
- Title: Accelerating Globally Optimal Consensus Maximization in Geometric Vision
- Title（参考訳）: 幾何学的視覚における総合的最適コンセンサス最大化の促進
- Authors: Xinyue Zhang, Liangzu Peng, Wanting Xu, Laurent Kneip
- Abstract要約: 我々は n 次元問題に対して n-1 次元空間上の分岐を可能にする新しい一般手法を提案する。
残りの自由度は、各有界計算において大域的に最適に解ける。
4つの基本的な幾何学的コンピュータビジョン問題に適用する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: ブランチ・アンド・バウンドベースのコンセンサス最大化は、異常な幾何学的問題に対するグローバル最適解を検索する重要な能力のために際立っている。
しかし、そのような解の発見は科学的価値を損なうが、実際のシナリオにおけるその応用は、目の前の問題の次元の関数として指数関数的に増加する計算複雑性によってしばしば禁止される。
本研究では,n次元問題に対してn-1次元空間上の分岐を可能にする,新しい一般手法を提案する。
残余自由度は、効率的な間隔スタビング手法を適用して、各境界計算内でグローバルに解くことができる。
個々の境界導出は、ソート問題を解決する追加の必要により計算が困難であるが、実際の間隔の削減とより厳密な境界は、必要なイテレーションの総数を大幅に減少させる。
このアプローチの抽象的導入の他に,4つの基本的な幾何学的コンピュータビジョン問題(カメラの切除,相対カメラのポーズ推定,ポイントセットの登録,回転と焦点距離推定)に適用する。
網羅的なテストを通じて、2桁を超える場合の大幅なスピードアップを実証し、オンラインアプリケーションシナリオにおけるグローバルな最適コンセンサス最大化の実現可能性を高める。
関連論文リスト
- Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Global optimization using random embeddings [1.2891210250935143]
本稿では,リプシッツ連続目的量の大域的最適化のためのランダム部分空間アルゴリズムフレームワークを提案する。
X-REGOは、連続的または同時的に、高次元の原問題を低次元のサブプロブレムにランダムに投影する。
この変種が元の問題の有効次元と近似大域最小化の両方を効率的に見つけることを数値的に示す。
論文 参考訳（メタデータ） (2021-07-26T10:45:49Z) - Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。
我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。
本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
論文 参考訳（メタデータ） (2021-07-25T14:13:07Z) - Transient growth of accelerated first-order methods for strongly convex
optimization problems [1.6114012813668934]
本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。
二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。
強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。
論文 参考訳（メタデータ） (2021-03-14T20:01:14Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。
我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
論文 参考訳（メタデータ） (2020-05-04T10:48:04Z) - Multi-consensus Decentralized Accelerated Gradient Descent [31.76773130271547]
分散凸最適化問題は、大規模機械学習、センサーネットワーク、制御理論に幅広い応用がある。
本稿では,最適な計算複雑性とほぼ最適な通信複雑性を実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-02T11:10:32Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。
本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
論文 参考訳（メタデータ） (2019-12-27T13:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。