GraphCutによる領域分割

in English

はじめに

　これまで、K-means ClusteringとGaussian Mixture Model(GMM)を利用した領域分割について考えてきた^1,2,3 。今回はGMMとGraphCutアルゴリズムを組み合わせて領域分割を行う。

定式化

　画像上に存在する画素の位置座標の集合を $V$、各画素 $v \in V$ に割り振るラベルを $m$ 、隣接画素の集合を $C$、画素 $v$ にラベル $m$ を割り振る確率を $p_{m}(v)$ 、与えられた画像のエッジ画像を $e(v)$ と書くことにする。 このとき、GraphCutアルゴリズムで最小化すべきエネルギー関数を次式で定義した。 $$\begin{equation} E(X)=\lambda\;\sum\limits_{v\;\in\; V}\left\{1-p_{m}(v)\right\}+\kappa\;\sum\limits_{(u,v)\;\in\; C}\left(1-\delta_{m,n}\right)\;\left\{\;1-\;\left|e(u)\right|\;\right\} \label{energy} \end{equation}$$ ここで、$\lambda,\kappa$ は正の定数、$\delta_{i,j}$ はクロネッカーのデルタ、$X$ は各画素へのラベルの割り振りかたの全てを表現する変数である。これは「配置」と呼ばれる。GraphCutアルゴリズムを使い、$E$ を最小にするような配置 $X$ を見つけることが目的である。

　式($\ref{energy}$)の右辺第1項はデータ項と呼ばれる。$p_{m}(v)$ は $E$ の最小化に先立って以下のように計算しておく。

1. ユーザがマウスで大まかに $M$ 個の領域を指定する。
2. $M$ 個の領域 $\{s_{1},\cdots,s_{M}\}$ が得られる。各領域 $s_{m}$ は画素の集合である。
3. 各領域 $s_{m}$ にEMアルゴリズムを適用し、確率分布 $p_{m}(v)$ を算出する。この際、画素のRGB値を使用する。
4. $m \in \{1,\cdots,M\}$ を各画素 $v$ に割り振るラベルとみなす。

OpenCVを使って計算される $p_{m}(v)$ は1を越えるので、各画素 $v$ に対して計算される全確率分布 $\{p_{1}(v),\cdots,p_{M}(v)\}$ をその最大値で割り、最大値を1にしておく。全画素に対しこの作業を行う。 式($\ref{energy}$)の第1項の物理的意味は以下の通りである。
「あらかじめ与えられた確率分布に従って画素 $v$ にラベル $m$ を割り振る。最も確度の高いラベルを割り振ったとき、エネルギー $E$ への寄与は最小になる」

　第2項は平滑化項と呼ばれる。今回の計算ではエッジ画像を使用した。この量についても、グレー画像にSobelフィルタを適用し、あらかじめ計算しておく。x軸方向、y軸方向の2つのエッジ画像 $e_{x}(u),e_{y}(u)$ を用意し、 $u=(x,y),v=(x+1,y)$ のときは $e_{x}(u)$ を、$u=(x,y),v=(x,y+1)$ のときは $e_{y}(u)$ を選択する。 絶対値が1以下となるように最大値で規格化しておく。平滑化項の物理的意味は以下の通りである。
「隣接画素 $(u,v)$ に割り振るラベル $(m,n)$ の値が同じとき、平滑化項は $E$ に寄与しない。それらが異なる場合、$E$ を増大させる。エッジの値が大きい画素近傍では $E$ への寄与は小さいが、エッジの値が小さい画素近傍での寄与は大きくなる」

　ここまでの議論を踏まえると、$E$ の第1項を最小するには確率の大きいラベルを各画素に割り振れば良い。一方、第2項を最小にするには、エッジの大きい画素近傍でラベル値を変え、エッジの小さい画素近傍ではラベル値を同じにすれば良い。これらのトレードオフにより $E$ を最小にする配置$X$が決まる。

結果

　最初に大まかなに領域を指定する。ここでは背景と鳥の2つを指定している。

実行すると以下のようになる。左が今回の結果、右は前回実装したGMMによる領域分割の結果である。

GraphCut	GMM

GMMの結果に見られる細かいノイズが、GraphCutの方ではほとんど消滅していることが分る。これが平滑化項の効果である。

　次の結果は3つの領域に分割した場合である。先と同じく大まかに、空、岩、海の領域を指定する。

実行すると以下のようになる。

GraphCut	GMM

ここでもGMMに見られるノイズがGraphCutではほとんど見られない。これら2つの計算では$\lambda=\kappa(=100)$とした。

開発環境

1. Mac OS X 10.8.3
2. プロセッサ：3.06 GHz Intel Core 2 Duo
3. メモリ：4GB
4. Xcode4.6.1 with Apple LLVM 4.2（C++ Language Dialect → GNU++11, C++ Standard Library → libc++）
5. boost-1.51.0（Apple LLVM 4.1でコンパイルしたもの。こちら）
6. opencv-2.4.3（Apple LLVM 4.2でコンパイルしたもの。こちら）

ソース

ソースは ここからダウンロードできる。上記の開発環境で動作確認した。

ライブラリ

GraphCutアルゴリズムのライブラリとしてGCO Version3を利用した。

実行方法

実行ファイ名は、ImageSegmentationWithGraphCutである。引数なしで実行すると以下を出力する。 オプション--ratioに対しては、$r=\kappa/\lambda$の値を指定する。すなわち、$\kappa=r\lambda$となる。$\lambda$の値は100に固定してある。それ以外の引数の意味はここと同じである。

以下を実行すると、--inputで指定した画像が開く。 マウスによる領域の指定方法はここと同じであるが、指定できる領域の数は0から5までの6つである。"e"を押して実行、"c"で領域の全削除、"q"で終了となる。

参考文献

1. "GrabCut" — Interactive Foreground Extraction using Iterated Graph Cuts
2. Bust out your own graphcut based image segmentation with OpenCV