グラフカット(画像処理)

画像処理におけるグラフカットの話が、次のスライドにわかりやすくまとめてあった。

■ 第14回 画像センシングシンポジウム グラフカットの理論と応用(石川博)
http://www.f.waseda.jp/hfs/SSIITutorial.pdf

理解した範囲の要点をまとめてみる(画像は上記PDFより)


・画像のセグメンテーション(領域抽出)などに用いられる。例:CT画像から臓器の領域だけを綺麗に切り抜きたい

・画像中の各ピクセルを、領域の「中」と「外」の2値に分ける問題。単純にある閾値で分けると、領域が飛び飛びになる(ノイズが乗る)

・エネルギー最小化問題で領域分けする。なるべく元の画像(単純に閾値で分けたもの)に近い、かつ、なるべく隣接する画素は同じ領域に含まれる。という条件。

・画像をグラフで表す。隣接する画素同士を連結したグラフ構造(1つの画素は周囲8つの画素と連結される)。

・「領域分け=グラフ構造の切断」と考える。切断後も、グラフ構造によって繋がっている画素は同じ領域に含まれる。

・では、どこでグラフを切断するか?

・それぞれの枝に「重み(コスト)」を設定する(画素の値が近いものは「重い」)。なるべくコストが最小となるように切断を行う。

・コストが最小となるような切断は「最大流」の考え方で求まる。「辺の重みをパイプの太さと考えて、異なる領域に属することが明らかな2点間に水を流した時に、最大流で飽和する辺」が切断する辺。

・この切断片は多項式時間で求まる

ディジタル画像処理の基礎と応用―基本概念から顔画像認識まで (ディジタル信号処理シリーズ)

ディジタル画像処理の基礎と応用―基本概念から顔画像認識まで (ディジタル信号処理シリーズ)

詳解 OpenCV ―コンピュータビジョンライブラリを使った画像処理・認識

詳解 OpenCV ―コンピュータビジョンライブラリを使った画像処理・認識