論文の概要: Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision
- arxiv url: http://arxiv.org/abs/2202.00418v1
- Date: Tue, 1 Feb 2022 14:06:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-02 17:48:27.518376
- Title: Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision
- Title（参考訳）: コンピュータビジョンのためのシリアルおよび並列マイカット/マックスフローアルゴリズムのレビュー
- Authors: Patrick M. Jensen, Niels Jeppesen, Anders B. Dahl and Vedrana A. Dahl
- Abstract要約: Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
- 参考スコア（独自算出の注目度）: 6.574107319036238
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Minimum cut / maximum flow (min-cut/max-flow) algorithms are used to solve a
variety of problems in computer vision and thus significant effort has been put
into developing fast min-cut/max-flow algorithms. This makes it difficult to
choose an optimal algorithm for a given problem - especially for parallel
algorithms, which have not been thoroughly compared. In this paper, we review
the state-of-the-art min-cut/max-flow algorithms for unstructured graphs in
computer vision. We evaluate run time performance and memory use of various
implementations of both serial and parallel algorithms on a set of graph cut
problems. Our results show that the Hochbaum pseudoflow algorithm is the
fastest serial algorithm closely followed by the Excesses Incremental Breadth
First Search algorithm, while the Boykov-Kolmogorov algorithm is the most
memory efficient. The best parallel algorithm is the adaptive bottom-up merging
approach by Liu and Sun. Additionally, we show significant variations in
performance between different implementations the same algorithms highlighting
the importance of low-level implementation details. Finally, we note that
existing parallel min-cut/max-flow algorithms can significantly outperform
serial algorithms on large problems but suffers from added overhead on small to
medium problems. Implementations of all algorithms are available at
https://github.com/patmjen/maxflow_algorithms
- Abstract（参考訳）: 最小カット/最大フロー (min-cut/max-flow) アルゴリズムはコンピュータビジョンの様々な問題を解決するために用いられ、高速のmin-cut/max-flowアルゴリズムの開発に多大な努力が払われている。
これにより、与えられた問題、特に完全比較されていない並列アルゴリズムに対して最適なアルゴリズムを選択することが困難になる。
本稿では,コンピュータビジョンにおける非構造化グラフに対する最先端のmin-cut/max-flowアルゴリズムについて述べる。
本稿では,一連のグラフカット問題に対する逐次アルゴリズムと並列アルゴリズムの様々な実装の実行時間性能とメモリ使用について評価する。
以上の結果から,Hochbaum擬似フローアルゴリズムは最も高速なシリアルアルゴリズムであり,Excesses Incremental Breadth First Searchアルゴリズムがそれに近づき,Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高いことがわかった。
最良の並列アルゴリズムは、LiuとSunによる適応的なボトムアップマージアプローチである。
さらに,異なる実装間の性能が,低レベルの実装の重要さを強調した同じアルゴリズムで大きく変化することを示す。
最後に、既存の並列マイトカット/マックスフローアルゴリズムは、大問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
すべてのアルゴリズムの実装はhttps://github.com/patmjen/maxflow_algorithmsで利用可能である。
関連論文リスト
- GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions [2.9998889086656586]
分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。
我々の研究は、大規模データセットにおける部分モジュラー最適化問題を解く必要性によって動機付けられている。
論文 参考訳（メタデータ） (2024-03-15T14:19:09Z) - Efficient and Accurate Optimal Transport with Mirror Descent and
Conjugate Gradients [15.128885770407132]
本研究では, エントロピー的最適輸送, ミラー降下, 共役勾配の文献から, 最適輸送のための新しいアルゴリズムを設計する。
我々のスケーラブルでGPU並列化可能なアルゴリズムは、ワッサースタイン距離を極端精度で計算することができ、数値安定性の問題なく相対誤差レート10～8ドルに達することができる。
論文 参考訳（メタデータ） (2023-07-17T14:09:43Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。