はじめに
これまで、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$ の最小化に先立って以下のように計算しておく。
- ユーザがマウスで大まかに $M$ 個の領域を指定する。
- $M$ 個の領域 $\{s_{1},\cdots,s_{M}\}$ が得られる。各領域 $s_{m}$ は画素の集合である。
- 各領域 $s_{m}$ にEMアルゴリズムを適用し、確率分布 $p_{m}(v)$ を算出する。この際、画素のRGB値を使用する。
- $m \in \{1,\cdots,M\}$ を各画素 $v$ に割り振るラベルとみなす。
「あらかじめ与えられた確率分布に従って画素 $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つを指定している。
 |
|
|
|
| GraphCut | GMM |
|---|
次の結果は3つの領域に分割した場合である。先と同じく大まかに、空、岩、海の領域を指定する。
 |
 |
 |
 |
 |
 |
| GraphCut | GMM |
|---|
開発環境
- Mac OS X 10.8.3
- プロセッサ：3.06 GHz Intel Core 2 Duo
- メモリ：4GB
- Xcode4.6.1 with Apple LLVM 4.2（C++ Language Dialect → GNU++11, C++ Standard Library → libc++）
- boost-1.51.0（Apple LLVM 4.1でコンパイルしたもの。こちら）
- 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"で終了となる。
0 件のコメント:
コメントを投稿