(画像処理での)グラフカットとは

• 画像処理にグラフ理論での最大流/最小カットを適用したもの。
• エネルギーを定義して、それを最小化をする「エネルギー最小化問題」。(ここで、最小カットが有用)。

• 作るグラフは、画素を頂点としてその画素の隣接画素と辺をつないだものに、頂点s,tを加え、「sからすべての画素」と「すべての画素からt」への辺を加えたもの、がよく使われてるっぽい。

• グラフの作り方は上記以外にもありえる。(関連として、Normalized Cutsとかは、画素を頂点とした完全グラフっぽいし)
• 離れたピクセルやピクセル以外を頂点(サイト)とすることもある。

• 使われている(研究されている)用途
  • 画像復元(ノイズ除去とか)
  • ステレオ(カメラ2つ以上でのなんか)
  • セグメンテーション
  • 動画像解析
  • テクスチャ合成
  • フォトモンタージュ、など

エネルギーの表現

• g:データ項。その画素(サイト)とつけるラベル(新しくつけた画素)のみに依存する。
• h:平滑化項。隣接するサイト間でXに与えられるラベルがどのような関係にあるべきか。
• X:ラベルをつけられた配置(新しい画像)。

• Xの組み合わせはすごく多い。(64x64の白黒画像で2^(64*64)通りの画像がありえる)
• NP困難(無茶振り)
• gとhをいろいろ変えることでいろいろ応用するぽい(ノイズ除去やセグメンテーションとかに)

• エネルギーを最小化する方法は、
  • グラフカット(GC)
  • 信念伝播法(Belief Propagation(BP), ニューラルとかのBack Propagationとは違う！)
  • ツリー重み再配分メッセージ伝達法(TRW)
  • など

• GCでは、エネルギーの形に制限があるが、大域最小値を比較的高速に求められる。
• グラフカットへ適用するため、頂点u,vを切断するときのコストc(u,v)に上記g,hを適用し、切断する。
• 最小のコストとなる切断の仕方は、最大流/最小カットのお話。

ノイズ除去

• 参考にしながら実際にやってみた図。
• 使わせてもらったプログラム(http://vision.csd.uwo.ca/code/)

• (ぶっちゃけgraphcutsなら自分で実装してもよかった)

• ステレオ視の方は、OpenCVに実装されてるみたい。FindStereoCorrespondenceGC。

参考にした(ちゃんと読むべき)ページ、論文

• Boykov先生(http://www.csd.uwo.ca/~yuri/)
• 石川先生(http://hwm7.gyao.ne.jp/hihfs/indexJ.html)
• 最大フロー最小カット(http://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E6%B5%81%E6%9C%80%E5%B0%8F%E3%82%AB%E3%83%83%E3%83%88%E5%AE%9A%E7%90%86)
• フォードファルカーソンアルゴリズム(http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%95%E3%82%A1%E3%83%AB%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)

最大流/最小カットのアルゴリズム

wikipedia(http://en.wikipedia.org/wiki/Maximum_flow_problem)に載ってた解法アルゴリズムは、

• 線形計画法
• フォード・ファルカーソンのアルゴリズム(O(E maxflow))
  • エドモンド・カープアルゴリズム(O(V E^2))
• ディニッツ法(O(V^2 E))
• など