*グラフカット とは 　画像などの複数の要素を持つデータに，要素間の整合性を考えた最適なラベルを設定するアルゴリズムの１つです．グラフカットは，画像上で類似する領域をラベリングする処理や非連続な信号を取り除くノイズ除去などに良く利用されます．グラフカットの効果を示す簡単な例として，ノイズ除去の結果を図１に示します． [img:ynt1] {{small:図１ ノイズを含む入力画像とグラフカットを使って最適値を計算した出力画像}} 　グラフカットでは，式(1)に示すように２つの項（データ項と平滑化項）の和を最小化するように入力データの各要素の値{$ L $}を推定します． {$$E(L) = \sum_{p \in P}D_p(L_p) + \sum_{(p,q) \in N}V_{p,q}(L_p, L_q) \tag{1}$$} 　ここで，データ項の{$D$}は元々の要素の値と整合するときに小さくなる関数です．平滑化項の{$V$}は隣り合う要素が同じ値のときに小さくなる関数です． 　例えば画像のように多くの要素を持つデータでは，すべての{$L$}の組み合わせから{$E$}を求めて最適値を探す方法は計算量の観点から現実的ではありません．この問題に対しグラフカットでは，グラフの最大流量を求める問題に置き換えて効率的に最適値を計算します．その中で[1]は，計算効率の観点から現在広く利用されている方法の１つです． {{small:[1]Y.Boykov and V.Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision", IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI), 2004}} {{small:[link:http://www.csd.uwo.ca/~yuri/Papers/pami04.pdf] }} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/graphcut ノイズを含むLennaの2値画像からノイズ除去を行います．