論文の概要: Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix
- arxiv url: http://arxiv.org/abs/2301.06443v2
- Date: Fri, 1 Sep 2023 12:38:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 17:08:45.946034
- Title: Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix
- Title（参考訳）: スパース結果に基づくコンピュータビジョンにおける最小解法とその作用行列との関係
- Authors: Snehal Bhayani, Janne Heikkil\"a, Zuzana Kukelova
- Abstract要約: いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
- 参考スコア（独自算出の注目度）: 17.31412310131552
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many computer vision applications require robust and efficient estimation of
camera geometry from a minimal number of input data measurements, i.e., solving
minimal problems in a RANSAC framework. Minimal problems are usually formulated
as complex systems of sparse polynomials. The systems usually are
overdetermined and consist of polynomials with algebraically constrained
coefficients. Most state-of-the-art efficient polynomial solvers are based on
the action matrix method that has been automated and highly optimized in recent
years. On the other hand, the alternative theory of sparse resultants and
Newton polytopes has been less successful for generating efficient solvers,
primarily because the polytopes do not respect the constraints on the
coefficients. Therefore, in this paper, we propose a simple iterative scheme to
test various subsets of the Newton polytopes and search for the most efficient
solver. Moreover, we propose to use an extra polynomial with a special form to
further improve the solver efficiency via a Schur complement computation. We
show that for some camera geometry problems our extra polynomial-based method
leads to smaller and more stable solvers than the state-of-the-art Grobner
basis-based solvers. The proposed method can be fully automated and
incorporated into existing tools for automatic generation of efficient
polynomial solvers. It provides a competitive alternative to popular Grobner
basis-based methods for minimal problems in computer vision. We also study the
conditions under which the minimal solvers generated by the state-of-the-art
action matrix-based methods and the proposed extra polynomial resultant-based
method, are equivalent. Specifically we consider a step-by-step comparison
between the approaches based on the action matrix and the sparse resultant,
followed by a set of substitutions, which would lead to equivalent minimal
solvers.
- Abstract（参考訳）: 多くのコンピュータビジョンアプリケーションは、RANSACフレームワークで最小限の問題を解くために、最小限の入力データ測定からカメラ幾何学を堅牢かつ効率的に推定する必要がある。
最小問題は通常スパース多項式の複素系として定式化される。
システムは通常過剰決定され、代数的に制限された係数を持つ多項式からなる。
最先端の多項式解法の多くは、近年自動化され高度に最適化されたアクション行列法に基づいている。
一方、スパース結果とニュートンポリトープの代替理論は、効率の良い解法の生成には成功せず、主にポリトープは係数の制約を尊重していない。
そこで本稿では,ニュートンポリトープの様々な部分集合をテストし,最も効率的な解法を探索するための簡易反復スキームを提案する。
さらに,schur補数計算による解法効率をさらに向上させるために,特別な形式を持つ補数多項式を用いることを提案する。
いくつかのカメラ幾何問題において、この多項式ベースの余分な解法がグロブナー基底解法よりも小さくより安定な解法をもたらすことを示した。
提案手法は,効率的な多項式解法を自動生成する既存のツールに完全自動で組み込むことができる。
コンピュータビジョンにおける最小限の問題に対して、一般的なgrobnerベース方式の代替手段を提供する。
また,最先端動作行列法と提案する余剰多項式結果行列法で生成する最小解法が等価である条件についても検討した。
具体的には、作用行列に基づくアプローチとスパース結果とのステップ・バイ・ステップの比較を考察し、続いて一連の置換を行い、同値な最小解法を導出する。
関連論文リスト
- Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。
ローラン方程式系に対する自動解法生成器を提案する。
論文 参考訳（メタデータ） (2023-07-01T12:12:52Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Polynomial Preconditioning for Gradient Methods [9.13755431537592]
対称性によって生成される新しいプレコンディショナー群を提案する。
条件番号の証明可能な改善を施した一階最適化手法を提供する。
グラディエントおよびファストグラディエントメソッドにプレコンディショニングを組み込む方法を示し、それに対応するグローバルな複雑性を確立する。
論文 参考訳（メタデータ） (2023-01-30T18:55:38Z) - Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
本書は、この課題に重要な科学的意味を持って取り組むためのいくつかの取り組みを提示している。
これは計算複雑性の観点からうまくスケールする代替の最適化スキームを提供する。
制約のない問題や制約のない問題に対して、緩和の疎開的階層を提示する。
論文 参考訳（メタデータ） (2022-08-23T18:56:05Z) - Weighted Low Rank Matrix Approximation and Acceleration [0.5177947445379687]
低ランク行列近似は機械学習における中心的な概念の1つである。
低ランク行列補完(LRMC)は、いくつかの観測が欠落しているときにLRMA問題を解く。
重み付き問題を解くアルゴリズムと2つの加速手法を提案する。
論文 参考訳（メタデータ） (2021-09-22T22:03:48Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文 参考訳（メタデータ） (2020-08-05T17:52:10Z) - Computing stable resultant-based minimal solvers by hiding a variable [20.402488757146692]
コンピュータビジョンアプリケーションは、最小数の入力データ測定からカメラ幾何学を頑健に推定する必要がある。
本稿では,1つの変数を隠蔽することにより,方程式のスパース系を解くための興味深い代替スパース法について検討する。
研究結果から,提案手法は現状のGr"オブザーバベースの解法よりも安定な解法に導かれることが示された。
論文 参考訳（メタデータ） (2020-07-17T07:40:10Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。