ランダムウォーカーアルゴリズム

ランダムウォーカーアルゴリズムは、画像セグメンテーションのためのアルゴリズムです。アルゴリズムの最初の説明では、^{[ 1 ]}ユーザーが対話的に少数のピクセルに既知のラベル（シードと呼ばれる）を付けます。たとえば、「オブジェクト」と「背景」などです。ラベル付けされていないピクセルはそれぞれランダムウォーカーを放出するものと想定され、各ピクセルのランダムウォーカーが最初に各ラベルを持つシードに到達する確率が計算されます。つまり、ユーザーがそれぞれ異なるラベルを持つ K 個のシードを配置した場合、各ピクセルについて、そのピクセルから出るランダムウォーカーが最初に各シードに到達する確率を計算する必要があります。これらの確率は、連立一次方程式を解くことで解析的に決定できます。各ピクセルについてこれらの確率を計算した後、そのピクセルには、ランダムウォーカーを送信する可能性が最も高いラベルが割り当てられます。画像はグラフとしてモデル化され、各ピクセルはノードに対応し、ノードはエッジによって隣接するピクセルに接続され、エッジはピクセル間の類似性を反映するように重み付けされます。したがって、ランダムウォークは重み付きグラフ上で発生します（グラフ上のランダムウォークの紹介については、DoyleとSnellを参照してください^{[ 2 ]}）。

当初のアルゴリズムは画像セグメンテーションのための対話型手法として定式化されましたが、データ忠実度項（例えば、強度事前分布）が与えられると、完全自動アルゴリズムに拡張されました。^{[ 3 ]}また、他のアプリケーションにも拡張されています。

このアルゴリズムは、当初レオ・グラディによって会議論文として発表され^{[ 4 ]}、後に学術誌論文として発表された^{[ 1 ] 。}

アルゴリズムはランダムウォークの観点から説明されているが、各ノードがランダムウォーカーをシードに送信する確率は、グラフ・ラプラシアン行列を用いた疎行列かつ正定値の線形方程式系を解くことで解析的に計算できる。この行列は変数で表すことができる。${\displaystyle L}$このアルゴリズムは任意の数のラベル（オブジェクト）に適用できることが示されていますが、ここでは説明を簡潔にするために2つのラベルを例として説明します。

画像はグラフで表され、各ノードは${\displaystyle v_{i}}$ピクセルと各エッジに関連付けられています${\displaystyle e_{ij}}$隣接するピクセルを接続する${\displaystyle v_{i}}$そして${\displaystyle v_{j}}$エッジの重みはノードの類似性を符号化するために使用され、これは画像の強度、色、テクスチャ、またはその他の意味のある特徴の違いから導き出すことができます。たとえば、画像の強度を使用する場合${\displaystyle g_{i}}$ノードで${\displaystyle v_{i}}$エッジ重み付け関数を使用するのが一般的です

${\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}$

ノード、エッジ、重みを使用して、グラフのラプラシアン行列を構築できます。

ランダムウォーカーアルゴリズムはエネルギーを最適化する

${\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}}$

どこ${\displaystyle x_{i}}$はグラフ内の各ノードに関連付けられた実数値変数を表し、最適化は によって制約されます。${\displaystyle x_{i}=1}$のために${\displaystyle v_{i}\in F}$そして${\displaystyle x_{i}=0}$のために${\displaystyle v_{i}\in B}$、 どこ${\displaystyle F}$そして${\displaystyle B}$はそれぞれ前景シードと背景シードの集合を表します。${\displaystyle S}$シードされたノードのセットを表します (つまり、${\displaystyle S=F\cup B}$） そして${\displaystyle {\overline {S}}}$シードされていないノードのセットを表します (つまり、${\displaystyle S\cup {\overline {S}}=V}$どこ${\displaystyle V}$はすべてのノードの集合である）場合、エネルギー最小化問題の最適解は、次の解によって与えられる。

${\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}$

添え字はグラフのラプラシアン行列の部分を示すために使用されます${\displaystyle L}$それぞれのセットによってインデックス付けされます。

アルゴリズムに尤度（単項）項を組み込むために、^{[ 3 ]}ではエネルギーを最適化できることが示された。

${\displaystyle Q(x)=x^{T}Lx+\gamma \left((1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}+\gamma \left(\sum _{v_{i}}f_{i}(1-x_{i})^{2}+\sum _{v_{i}}b_{i}x_{i}^{2}\right),}$

正の対角行列の場合${\displaystyle F}$そして${\displaystyle B}$このエネルギーを最適化すると、線形方程式系が得られます。

${\displaystyle \left(L_{{\overline {S}},{\overline {S}}}+\gamma F_{{\overline {S}},{\overline {S}}}+\gamma B_{{\overline {S}},{\overline {S}}}\right)x_{\overline {S}}=-L_{{\overline {S}},S}x_{S}-\gamma F_{{\overline {S}},{\overline {S}}}.}$

シードされたノードのセット、${\displaystyle S}$この場合は空になることがあります（つまり、${\displaystyle {\overline {S}}=V}$しかし、正の対角行列が存在することで、この線形システムには一意の解が存在する。

例えば、尤度/単項式を使用してオブジェクトのカラーモデルを組み込む場合、${\displaystyle f_{i}}$ノードの色が信頼度を表す${\displaystyle v_{i}}$オブジェクトに属する（つまり、より大きな値${\displaystyle f_{i}}$より強い信頼を示している${\displaystyle v_{i}}$オブジェクトラベルに属していた）${\displaystyle b_{i}}$ノードの色が信頼度を表す${\displaystyle v_{i}}$背景に属する。

ランダムウォーカーアルゴリズムは、ピクセルにドロップされたランダムウォーカーが最初にオブジェクト（前景）シードまたは背景シードに到達する確率に基づいて、ピクセルをオブジェクト/背景としてラベル付けすることから始まりました。しかし、この同じアルゴリズムの他のいくつかの解釈が^{[ 1 ]に登場しています。}

上記で説明した従来のランダムウォーカーアルゴリズムは、いくつかの方法で拡張されています。

• 再起動を伴うランダムウォーク^{[ 6 ]}
• アルファマッティング^{[ 7 ]}
• 閾値選択^{[ 8 ]}
• ソフト入力^{[ 9 ]}
• 事前にセグメント化された画像上で実行します^{[ 10 ]}
• スケール空間ランダムウォーク^{[ 11 ]}
• オフライン事前計算を使用した高速ランダムウォーカー^{[ 12 ] [ 13 ]}
• 柔軟な互換性関数を可能にする一般化ランダムウォーク^{[ 14 ]}
• グラフカット、ランダムウォーカー、最短経路を統合するパワーウォーターシェッド^{[ 15 ]}
• ランダムウォーカー流域^{[ 16 ]}
• 多変量ガウス条件付き確率場^{[ 17 ]}

画像分割以外にも、ランダムウォーカーアルゴリズムまたはその拡張版は、コンピュータビジョンやグラフィックスにおけるいくつかの問題にも応用されている。

• 画像の色付け^{[ 18 ]}
• インタラクティブなロトスコープ^{[ 19 ]}
• 医用画像セグメンテーション^{[ 20 ] [ 21 ] [ 22 ]}
• 複数のセグメンテーションを統合する^{[ 23 ]}
• メッシュ分割^{[ 24 ] [ 25 ]}
• メッシュノイズ除去^{[ 26 ]}
• セグメンテーション編集^{[ 27 ]}
• 影の除去^{[ 28 ]}
• ステレオマッチング（すなわち、一次元画像レジストレーション）^{[ 29 ]}
• 画像融合^{[ 14 ] [ 17 ]}

• オリジナルのランダムウォーカーアルゴリズムを実装したMATLABコード
• 事前計算を用いたランダムウォーカーアルゴリズムを実装したMATLABコード
• オリジナルのランダムウォーカーアルゴリズムのPython実装。 2012年10月14日にWayback Machineにアーカイブ済み。画像処理ツールボックスscikit-image内。