グラフカットを使った画像の切り抜き(パート1)

この手の画像切り抜きは Photoshop を使えば簡単かもしれませんが、 ここでは Python を使って切り抜きをしてみます。 オライリー本の「実践コンピュータビジョン」を参考にしているので 詳細はそちらをご覧ください。

対象となる画像

この画像のパンを切り抜いてみます。

実際の処理は パート2 を参照いただくとして パート1では、グラフカットの基本について確認します。

事前準備 最小カット

画像中の対象オブジェクトを切り抜くためにグラフ理論を使う。 右のような 点a を出発点（ソース）として 点f が終着点（シンク）となるグラフがあるときに、最大フロー/最小カット問題を計算する。 そうすると、ここにある点a - f を２つのグループに分けることができる。 これがグラフ理論による最大フロー/最小カットでできること・・・らしい。（よくわかってない。）

画像中のパンを切り抜きたいのに、いきなりグラフ理論の最小カットの計算とか言われてもあれだが、 これとそれとの関係を雑に説明すると・・・ この点a - f を画像中のピクセルに対応させ、それらを２つのグループにわけることができれば…つまり 画像中のパンに属するピクセルと背景に属するピクセルとをわけることができ、 結果として切り抜く境界線を特定できるというわけです。

エッジ部分には重みを設定するため、 もし…

• パンに属するピクセル同士のエッジは大きい重み
• 背景に属するピクセル同士のエッジも大きい重み
• パンと背景ピクセルをつなぐエッジは小さい重み

をそれぞれに設定することができれば、パンと背景のピクセルを意図通りに切り分けることができることになる。

実際には点a -f を各画像ピクセルに割り当てるのではなく 点b,c,d,e を割り当てる。

図中の緑色の数字はそれぞれのエッジにおける重み（ウェイト）。

このグラフでは、最小カットは 点a - b と 点e - f の部分でカットするのが最小になるのは一目瞭然だが、 Pythonで計算して確認する。

Python による最小カットの計算

pygraph を使うと最大フロー/最小カットの計算ができるらしい。 必要なら、以下のようにして pygraph をインストールして・・・ (Ubuntu 17.04 の場合)

sudo apt-get install python-pygraph

以下のコードを実行する。

from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flow

gr = digraph()

gr.add_nodes(['a','b','c','d','e','f'])
gr.add_edge(('a','b'), wt=1)
gr.add_edge(('b','c'), wt=4)
gr.add_edge(('c','f'), wt=3)
gr.add_edge(('a','d'), wt=5)
gr.add_edge(('d','e'), wt=3)
gr.add_edge(('e','f'), wt=2)

flows,cuts = maximum_flow(gr,'a','f')
#print flows
print cuts

結果は

{'a': 0, 'c': 1, 'b': 1, 'e': 0, 'd': 0, 'f': 1}

この結果の読み方は、それぞれの点a - f が 0 か 1 に割り当てられている。 つまり…

• 点a,d,e が 0
• 点c,b,f が 1

になっているので、 a,d,e と c,b,f のグループにわけられたことになる。

パート2へ続く。