論文の概要: CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration
- arxiv url: http://arxiv.org/abs/2402.15464v1
- Date: Fri, 23 Feb 2024 17:50:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 13:53:31.064313
- Title: CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration
- Title（参考訳）: CLIPPER+:ロバストなグローバル登録のための高速最大斜めアルゴリズム
- Authors: Kaveh Fathian, Tyler Summers
- Abstract要約: 未重み付きグラフの最大傾きを求めるアルゴリズムであるCLIPPER+を提案する。
標準グラフベンチマークにおけるCLIPPER+の性能と,合成および実世界のクラウド登録問題を評価する。
- 参考スコア（独自算出の注目度）: 3.448338949969246
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present CLIPPER+, an algorithm for finding maximal cliques in unweighted
graphs for outlier-robust global registration. The registration problem can be
formulated as a graph and solved by finding its maximum clique. This
formulation leads to extreme robustness to outliers; however, finding the
maximum clique is an NP-hard problem, and therefore approximation is required
in practice for large-size problems. The performance of an approximation
algorithm is evaluated by its computational complexity (the lower the runtime,
the better) and solution accuracy (how close the solution is to the maximum
clique). Accordingly, the main contribution of CLIPPER+ is outperforming the
state-of-the-art in accuracy while maintaining a relatively low runtime.
CLIPPER+ builds on prior work (CLIPPER [1] and PMC [2]) and prunes the graph by
removing vertices that have a small core number and cannot be a part of the
maximum clique. This will result in a smaller graph, on which the maximum
clique can be estimated considerably faster. We evaluate the performance of
CLIPPER+ on standard graph benchmarks, as well as synthetic and real-world
point cloud registration problems. These evaluations demonstrate that CLIPPER+
has the highest accuracy and can register point clouds in scenarios where over
$99\%$ of associations are outliers. Our code and evaluation benchmarks are
released at https://github.com/ariarobotics/clipperp.
- Abstract（参考訳）: 未重み付きグラフの最大傾きを求めるアルゴリズムであるCLIPPER+を提案する。
登録問題はグラフとして定式化でき、最大のクランクを見つけることで解くことができる。
この定式化は外れ値に対する極端なロバスト性をもたらすが、最大クランクを求めることはnpハードな問題であり、それゆえ大規模問題には実際に近似が必要となる。
近似アルゴリズムの性能は、その計算複雑性(ランタイムが低いほど良い)と解の精度(解が最大傾きにどの程度近いか)によって評価される。
したがって、CLIPPER+の主なコントリビューションは、比較的低いランタイムを維持しながら、最先端の正確性を上回っている。
CLIPPER+ は以前の作業 (CLIPPER [1] と PMC [2]) に基づいて構築され、小さなコア番号を持ち最大傾きの一部にはならない頂点を削除してグラフをプルークする。
これによりより小さなグラフが得られ、最大傾きをかなり速く推定することができる。
標準グラフベンチマークにおけるCLIPPER+の性能と,合成および実世界のクラウド登録問題を評価する。
これらの評価は、CLIPPER+の精度が最も高く、99セント以上の関連が外れたシナリオでポイントクラウドを登録できることを示している。
コードと評価ベンチマークはhttps://github.com/ariarobotics/clipperp.comで公開されています。
関連論文リスト
- A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
未分岐グラフの$k$-defective cliqueは、$G$は、最大で$k$の欠損エッジを持つほぼ完全なグラフを誘導する。
与えられたグラフから最大の$k$$-defective Cliqueを求める最大$k$-defective Clique問題は、社会的および生物学的ネットワーク分析のような多くのアプリケーションにおいて重要である。
論文 参考訳（メタデータ） (2024-07-23T15:40:35Z) - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - FastMAC: Stochastic Spectral Sampling of Correspondence Graph [55.75524096647733]
本稿では,対応グラフの領域にグラフ信号処理を導入する最初の研究について述べる。
我々は、対応グラフ上の一般化次数信号を利用し、高周波成分を保存するサンプリング戦略を追求する。
アプリケーションとして,FastMACと呼ばれる,リアルタイムな高速な3D登録アルゴリズムを構築した。
論文 参考訳（メタデータ） (2024-03-13T17:59:56Z) - CLIPPER: Robust Data Association without an Initial Guess [38.56736000339334]
初期推定を必要としないデータアソシエーションのためのグラフ理論の定式化について検討する。
既存のグラフ理論アプローチは、未重み付きグラフを最適化し、重み付きエッジに符号化された重要な一貫性情報を破棄し、NPハード問題を正確に解こうとする。
この問題に対して2つの緩和法を導入する: 凸半有限緩和法は経験的に厳密であることが判明し、CLIPPERと呼ばれる高速な1次アルゴリズムはミリ秒でほぼ最適解に到達する。
論文 参考訳（メタデータ） (2024-02-11T19:16:01Z) - 3D Registration with Maximal Cliques [49.41310839477418]
最大傾斜角(MAC)を用いた3次元登録法を提案する。
重要な洞察は、以前の最大斜めの制約を緩めることである。
U3M, 3DMatch, 3DLoMatch, KITTIの実験によりMACは登録精度を効果的に向上することを示した。
論文 参考訳（メタデータ） (2023-05-18T10:15:44Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。
提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。
我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
論文 参考訳（メタデータ） (2023-02-01T14:02:06Z) - CLIP Itself is a Strong Fine-tuner: Achieving 85.7% and 88.0% Top-1
Accuracy with ViT-B and ViT-L on ImageNet [139.56863124214905]
CLIPの微調整性能はかなり過小評価されている。
具体的には、CLIP ViT-Base/16とCLIP ViT-Large/14は、ImageNet-1KデータセットのTop-1精度を85.7%、88.0%微調整することができる。
論文 参考訳（メタデータ） (2022-12-12T18:59:59Z) - Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
大きなグラフで高密度なサブグラフをリストすることは、コミュニティ検出のような様々なネットワーク分析アプリケーションにおいて重要なタスクである。
本稿では、最大$k$-プレックスと最大$k$-プレックスを所定の大きさで列挙する研究線を継続する。
私たちの最初のコントリビューションはアルゴリズムListPlexで、すべての最大$k$-plexesを$O*(gammaD)$ time for each constant $k$, where $gamma$ is a value to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that far less。
論文 参考訳（メタデータ） (2022-02-17T16:25:56Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。