algorithm - 開始点のないグラフ検索アルゴリズム

Question

シーンのエッジ マップがあり、空と地形を最もよく分離するエッジを抽出したいと考えています。これは、グラフ トラバーサルの問題として適切に組み立てられているようです。ただし、A* などの一般的な検索アルゴリズムは、開始点と終了点 (それぞれ最初と最後の列以外) の使用に依存しています。これらのパラメータを必要としないグラフ検索のアルゴリズムはありますか? また、滑らかさなど、抽出されたエッジのいくつかのグローバル機能を最大化したいと思います。注: 速度は重要な問題です。これはリアルタイムで行う必要があります。

Answer 1

コンピュータ ビジョンの研究者は、最小限のカットでこの種の問題に取り組んできました。ウィキペディアには、コンピューター ビジョンのグラフ カットに関する記事全体があります。この関係を最初に確立した Greig、Porteous、および Seheult によって提案されたアルゴリズムをここにスケッチします。

ピクセルの色から、そのピクセルが空と地形である可能性をログに記録する関数があるとします。ソース頂点、シンク頂点、各ピクセルの頂点を持つグラフを準備します。そのピクセルが空である対数尤度に等しい容量でソースを各ピクセルに接続します。各ピクセルを、そのピクセルが地形である対数尤度に等しい容量でシンクに接続します。隣接するピクセルの各ペアについて、異なる分類を持つ対数尤度に等しい容量でそれらを接続します。最小カットを計算します。カットのソース側のすべての頂点は空として分類され、カットのシンク側のすべての頂点は地形として分類されます。

あるいは、地形が画像の下部にあり、空が上部にあることがわかっている場合は、代わりにソースを上部の各ピクセルに接続し、下部のピクセルをシンクに接続します。容量は無限です。次に、色に基づいてピクセルを分類するための対数尤度を省略し、隣接するピクセルの色の類似性によってエッジの容量を変化させることができます。