ランダムウォーカーアルゴリズム
画像セグメンテーションアルゴリズム

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

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

このアルゴリズムは当初レオ・グレイディによって会議論文[4]として発表され、その後ジャーナル論文として発表されました。[1]

数学

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

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

わ 私 j ＝ 経験 ⁡ （ − β （ グラム 私 − グラム j ） 2 ） 。 {\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}

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

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

質問 （ × ） ＝ × T L × ＝ ∑ e 私 j わ 私 j （ × 私 − × j ） 2 {\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}}

ここで、 はグラフの各ノードに関連付けられた実数値変数を表し、については 、についてはによって最適化が制約されます。ここで、と はそれぞれフォアグラウンドシードとバックグラウンドシードの集合を表します。をシードされたノードの集合（すなわち）とし、をシードされていないノードの集合（すなわち はすべてのノードの集合）とすると、エネルギー最小化問題の最適解は次の式で与えられます。 × 私 {\displaystyle x_{i}} × 私 ＝ 1 {\displaystyle x_{i}=1} v 私 ∈ F {\displaystyle v_{i}\in F} × 私 ＝ 0 {\displaystyle x_{i}=0} v 私 ∈ B {\displaystyle v_{i}\in B} F {\displaystyle F} B {\displaystyle B} S {\displaystyle S} S ＝ F ∪ B {\displaystyle S=F\cup B} S ¯ {\displaystyle {\overline {S}}} S ∪ S ¯ ＝ V {\displaystyle S\cup {\overline {S}}=V} V {\displaystyle V}

L S ¯ 、 S ¯ × S ¯ ＝ − L S ¯ 、 S × S 、 {\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}

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

尤度（単項）項をアルゴリズムに組み込むには、[3]でエネルギーを最適化することが 示されています。

質問 （ × ） ＝ × T L × + γ （ （ 1 − × ） T F （ 1 − × ） + × T B × ） ＝ ∑ e 私 j わ 私 j （ × 私 − × j ） 2 + γ （ ∑ v 私 f 私 （ 1 − × 私 ） 2 + ∑ v 私 b 私 × 私 2 ） 、 {\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),}

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

（ L S ¯ 、 S ¯ + γ F S ¯ 、 S ¯ + γ B S ¯ 、 S ¯ ） × S ¯ ＝ − L S ¯ 、 S × S − γ F S ¯ 、 S ¯ 。 {\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}}}.}

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

たとえば、尤度/単項項を使用してオブジェクトのカラー モデルを組み込む場合、 はノードの色がオブジェクトに属するという信頼性を表します (つまり、 の値が大きいほど、オブジェクト ラベルに属する信頼性が高いことを示します)。また、はノードの色が背景に属するという信頼性を表します。 f 私 {\displaystyle f_{i}} v 私 {\displaystyle v_{i}} f 私 {\displaystyle f_{i}} v 私 {\displaystyle v_{i}} b 私 {\displaystyle b_{i}} v 私 {\displaystyle v_{i}}

アルゴリズムの解釈

ランダムウォーカーアルゴリズムは当初、ランダムウォーカーをピクセルにドロップした際に、オブジェクト（前景）シードと背景シードのどちらに最初に到達するかという確率に基づいて、ピクセルをオブジェクト／背景として分類するアルゴリズムとして考案されました。しかし、このアルゴリズムには、他にもいくつかの解釈があり、[1]で紹介されています。

回路理論の解釈

電気回路理論とグラフ上のランダムウォークの間には、よく知られた関連性があります。[5] そのため、ランダムウォーカーアルゴリズムは、電気回路の観点から2つの異なる解釈が可能です。どちらの場合も、グラフは各辺が受動的な線形抵抗器に置き換えられた電気回路とみなされます。辺に関連付けられた抵抗 はに等しく設定されます（つまり、辺の重み は電気伝導率に等しくなります）。 r 私 j {\displaystyle r_{ij}} e 私 j {\displaystyle e_{ij}} r 私 j ＝ 1 わ 私 j {\displaystyle r_{ij}={\frac {1}{w_{ij}}}}

最初の解釈では、背景シードに関連付けられた各ノードは直接接地され、オブジェクト/フォアグラウンドシードに関連付けられた各ノードは接地された単位直流理想電圧源に接続されます（つまり、各ノードに単位電位を確立します）。この回路構成によって各ノードに確立される定常電気回路の電位は、ランダムウォーカーの確率と正確に等しくなります。具体的には、ノードにおける電位は、ノードにドロップされたランダムウォーカーが背景ノードに到達する前にオブジェクト/フォアグラウンドノードに到達する確率に等しくなります。 v 私 ∈ B {\displaystyle v_{i}\in B} v 私 ∈ F {\displaystyle v_{i}\in F} v 私 ∈ F {\displaystyle v_{i}\in F} × 私 {\displaystyle x_{i}} v 私 {\displaystyle v_{i}} v 私 {\displaystyle v_{i}}

2つ目の解釈では、ランダムウォーカー確率を0.5で閾値化することでノードをオブジェクトまたは背景としてラベル付けすることは、ノードとオブジェクトまたは背景シード間の相対的な有効コンダクタンスに基づいてノードをオブジェクトまたは背景としてラベル付けすることと同等です。具体的には、ノードがオブジェクトシードに対して背景シードよりも高い有効コンダクタンス（有効抵抗）を持つ場合、ノードはオブジェクトとしてラベル付けされます。ノードがオブジェクトシードに対して背景シードよりも高い有効コンダクタンス（有効抵抗）を持つ場合、ノードは背景としてラベル付けされます。

拡張機能

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

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

アプリケーション

画像のセグメンテーション以外にも、ランダム ウォーカー アルゴリズムまたはその拡張は、コンピューター ビジョンやグラフィックスのさまざまな問題にも適用されています。

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

参考文献

  1. ^ abc Grady, L.：「画像セグメンテーションのためのランダムウォーク」PAMI、2006
  2. ^ P. Doyle, JL Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984
  3. ^ ab Leo Grady：「事前モデルを使用したマルチラベルランダムウォーカー画像セグメンテーション」、Proc. of CVPR、Vol. 1、pp. 763–770、2005年。
  4. ^ Leo Grady、Gareth Funka-Lea：「グラフ理論的電位に基づく医療アプリケーション向けのマルチラベル画像セグメンテーション」、第8回ECCVワークショップ「医療画像分析へのコンピュータビジョンアプローチと生物医学画像分析における数学的手法」の議事録、pp. 230–245、2004年。
  5. ^ PG Doyle, JL Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984
  6. ^ TH Kim、KM Lee、SU Lee: ランダムウォークとリスタートを用いた生成画像セグメンテーション、ECCV 2008論文集、pp. 264–275
  7. ^ J. Wang、M. Agrawala、MF Cohen：「ソフトシザーズ：リアルタイムで高品質なマットを作成するためのインタラクティブツール」Wayback Machineに2021年6月27日にアーカイブ、SIGGRAPH 2007の論文集
  8. ^ S. Rysavy、A. Flores、R. Enciso、K. Okada: ランダムウォークセグメンテーションの洗練のための分類基準、ICPR 2008年大会論文集
  9. ^ W. Yang、J. Cai、J. Zheng、J. Luo：「統合された組み合わせユーザー入力によるユーザーフレンドリーなインタラクティブ画像セグメンテーション」、IEEE Trans. on Image Proc.、2010
  10. ^ C. Chefd'hotel, A. Sebbane: マルチラベル画像セグメンテーションのための流域隣接グラフ上のランダムウォークとフロントプロパゲーション、ICV 2007年論文集
  11. ^ R. Rzeszutek、T. El-Maraghi、D. Androutsos: スケールスペースランダムウォークを用いた画像セグメンテーション、第16回国際デジタル信号処理会議論文集、pp. 458–461、2009年
  12. ^ L. Grady, AK Sinop, "Fastapproximate Random Walker Segmentation using eigenvector precomputation". IEEE Con​​f. CVPR, pp. 1–8, 2008
  13. ^ S. Andrews, G. Hamarneh, A. Saad. 事前計算を用いた事前確率を用いた高速ランダムウォーカーによるインタラクティブな医用画像セグメンテーション, Proc. of MICCAI 2010
  14. ^ ab R. Shen、I. Cheng、J. Shi、A. Basu：「多重露出画像の融合のための一般化ランダムウォーク」、IEEE Trans. on Image Processing、2011 年。
  15. ^ Camille Couprie、Leo Grady、Laurent Najman、Hugues Talbot、「Power Watersheds：統合グラフベース最適化フレームワーク」、IEEE Transactions on Pattern Analysis and Machine Intelligence、Vol. 33、No. 7、pp. 1384-1399、2011年7月
  16. ^ S. Ram, JJ Rodriguez: Random Walker Watersheds: A New Image Segmentation Approach、IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)、pp. 1473-1477、バンクーバー、カナダ、2013年5月
  17. ^ ab R. Shen、I. Cheng、A. Basu：「階層的多変量ガウスCRFにおけるQoEベースのマルチ露出融合」、IEEE Trans. on Image Processing、2013年。
  18. ^ X. Liu、J. Liu、Z. Feng：ランダムウォークによるセグメンテーションを用いたカラー化、画像とパターンのコンピュータ分析、pp. 468–475、2009
  19. ^ R. Rzeszutek、T. El-Maraghi、D. Androutsos: スケールスペースランダムウォークによるインタラクティブなロトスコープ、2009 IEEE 国際マルチメディア・エキスポ会議論文集
  20. ^ SP Dakua、JS Sahambi：「ランダムウォークアプローチを用いた心臓MR画像からの左心室輪郭抽出」、Int. Journal of Recent Trends in Engineering、Vol 1、No. 3、2009年5月
  21. ^ F. Maier、A. Wimmer、G. Soza、JN Kaftan、D. Fritz、R. Dillmann: ランダム ウォーカー アルゴリズムを使用した自動肝臓セグメンテーション[デッドリンク]、Bildverarbeitung für die Medizin 2008
  22. ^ P. Wighton、M. Sadeghi、TK Lee、MS Atkins：教師あり設定における皮膚病変の完全自動ランダムウォーカーセグメンテーション、MICCAI 2009年大会
  23. ^ P. Wattuya、K. Rothaus、JS Prassni、X. Jiang：ランダムウォーカーに基づく複数セグメンテーションの結合アプローチ、ICPR 2008年大会論文集
  24. ^ Y.-K. Lai, S.-M. Hu, RR Martin, PL Rosin: ランダムウォークを用いた高速メッシュセグメンテーション、2008 ACM固体および物理モデリングシンポジウム論文集
  25. ^ J. Zhang、J. Zheng、J. Cai：「制約付きランダムウォークを使用したインタラクティブなメッシュカット」、IEEE Trans. on Visualization and Computer Graphics、2010 年。
  26. ^ X. Sun, PL Rosin, RR Martin, FC Langbein: 特徴保存メッシュノイズ除去のためのランダムウォーク、Computer Aided Geometric Design、第25巻、第7号、2008年10月、pp. 437–456
  27. ^ L. Grady, G. Funka-Lea：「事前セグメント化された画像/ボリュームのデータ駆動型編集に対するエネルギー最小化アプローチ」、MICCAI紀要、第2巻、2006年、888～895頁
  28. ^ G. Li、L. Qingsheng、Q. Xiaoxu：ランダムウォークとエッジ特徴に基づく移動車両の影の除去、IITA 2008論文集
  29. ^ R. Shen, I. Cheng, X. Li, A. Basu: ランダムウォークを用いたステレオマッチング Archived 2021-06-27 at the Wayback Machine , Proc. of ICPR 2008
  • オリジナルのランダムウォーカーアルゴリズムを実装したMATLABコード
  • 事前計算を伴うランダムウォーカーアルゴリズムを実装する Matlab コード
  • オリジナルのランダムウォーカーアルゴリズムのPython実装 Archived 2012-10-14 at the Wayback Machine in the image processing toolbox scikit-image
「https://en.wikipedia.org/w/index.php?title=ランダムウォーカーアルゴリズム&oldid=1310973463」より取得