グラフカットによる領域セグメンテーションに関する研究
画像認識講座

永橋 知行

1.はじめに画像処理における重要な問題の一つに一枚の画像から対象となる領域を抽出する画像セグメンテーションの問題がある．近年，画像セグメンテーション手法として，GraphCuts を用いた画像セグメンテーション [1] が注目されている．しかし，Graph Cuts による画像セグメンテーション
では，複雑なエッジ情報を含んだ画像に対しては正確な物体領域を抽出することが困難という問題点がある．本手法
では，ガウシアンフィルタの平滑化度合いを変化させた画像に対し，平滑化度合いが大きなものから Graph Cuts を行い，そのセグメンテーション結果からグラフの t-link に反映させ，次の平滑化度合いのセグメンテーションに利用する．これらを繰り返し処理することにより，大域的なセグメンテーションから段階的に局所的なセグメンテーションを行う．また，動画像に対してはバンド幅が異なるスーパーピクセルを用いて繰り返し処理することで，大域的なセグメンテーションから段階的に局所的なセグメンテーションを実現する．

2.平滑化処理の繰り返しによる Graph Cuts本手法では，平滑化度合いの異なる複数の画像を使用し，平滑化度合いの大きなものから Graph Cuts を繰り返し行うことにより，局所的なエッジ情報に頑健なセグメンテーション手法を提案する．
Graph Cuts 画像 P に対する各ピクセルを p ∈ P としたとき，ラベルを = {L1 , L2 , . . . , Lp , . . . , L|P | } とし，各 Lp には物体 (”obj”) か背景 (”bkg”) のラベルを持つ．
また，p の近傍ピクセルを q ∈ N とする．Graph Cuts では，エネルギー関数を式 (1) に定義する．

E()

=

λ · R() + B()(1)

R(L) と B(L) により定義したエネルギー関数 E( ) を最小とするようなラベル を Graph Cuts Algorithm を用いて計算することでセグメンテーションを行う．
Graph Cuts Algorithm では，画像から図 1 のようにグラフを作成し min-cut/max-flow algorithm を用いてグラフの分割を実現している．グラフ G は，画像の各ピクセルに対応したノードと source と sink と呼ばれるターミナルからなる．グラフの作成に各ピクセルをノードとしてグラフを構成する．各ノード間を接続するエッジを n-link と呼び，各ノードから source (S) と sink (T ) のターミナルを接続するエッジを t-link と呼ぶ．n-link と t-link のエッジ
コストには，以下の式に従い計算する．



図 1 : グラフの作成=− ln Pr(Ip |O)(2)

Rp (”bkg”)=− ln Pr(Ip |B)(3)

B{p,q}∝exp −K=

1 + maxp∈P(Ip − Iq )22σ 2

q:{p,q}∈N藤吉 弘亘

O は物体, B は背景を意味し, また，Ip はピクセル p の輝度値である．ユーザは一部のピクセルに対して O, B を入力する．このとき入力された O, B を seed と呼ぶ，作成したグラフに対して，min-cut/max-flow algorithm を用いることで，物体と背景にグラフを分割する．
提案手法の流れ 図 2 に，提案手法の流れを示す．はじめ

図 2 : 手法の流れに，入力画像に対してユーザが物体と背景の seed の入力を行う．次に，平滑化度合いを決定する σ の初期値を決定する．これは画像を 1/4 にダウンサンプリングした際の画像の長辺が 100pixel 以下になる画像を平滑化を開始する画像とし，そこから σ の初期値を決定する．決定した σ を用いてガウシアンフィルタにより平滑化画像を作成し，それを入力画像として Graph Cuts を行う．Graph Cuts により，物体領域と背景領域の色分布に対して GMM(GaussianMixture Model) の当てはめを行う．また，物体領域と背景領域に対して距離変換を行い各ピクセルごとに物体と背景の事前確率を更新する．GMM の尤度と距離変換による事前確率から各ピクセルごとに物体と背景の事後確率を計算したものをグラフの t-link に設定し，次の Graph Cuts
処理に利用する．この処理を σ < 1 でセグメンテーション結果に変化がないか，σ = 0 となるまで繰り返す．この条
件を満たさない場合は，σ = α · σ として更新を行い再度Graph Cut を行う．このときの 0 < α < 1 である．
これらの手順を以下に示す．
Step1. seed の入力
Step2. σ の初期値計算
Step3. 画像の平滑化
Step4. Graph Cuts
Step5. セグメンテーション結果から事後確率の計算
Step6. σ < 1 でセグメンテーション結果が変化しなくなるか，σ = 0 となったら終了それ以外ならば σ =α · σ(0 < α < 1) と更新し Step 3 へ繰り返し処理による Graph Cuts
σ が大きな平滑化画像から Graph Cuts を繰り返し行う．本手法では 1 回前の Graph Cuts の結果から色分布確率と空間確率を計算し，t-link に用いる．
Pr(O)Pr(Ip |O)
Pr(O|Ip ) =(6)Pr(Ip )
Pr(B)Pr(Ip |B)
Pr(B|Ip ) =(7)Pr(Ip )
分母の Pr(Ip ) は Pr(O) と Pr(B) の両方にあるため，これらの大小関係には影響がないので Pr(Ip ) = 1 とする．前回のセグメンテーション結果から色分布確率 Pr(Ip |O), Pr(Ip |B)
は，色空間に当てはめた GMM により計算し，空間的確率 Pr(O), Pr(B) はセグメンテーション結果を距離変換したものから計算する．

Rp (”obj”)

指導教授·1(4)dist(p, q)

B{p,q}(5)

3.スーパーピクセルを用いた繰り返しによる GraphCuts

動画像に対して本手法を適応した場合，各ピクセルをノードとするため，大量のノードが必要となる．また，時間軸方向に対しての平滑化をどのようにするかが問題となる．そこで，異なるバンド幅で作成されたスーパーピクセ
ルを使用し，バンド幅が大きなものから Graph Cuts を繰図 3 : セグメンテーション結果り返し処理することにより高精度なセグメンテーション手法を実現する．
スーパーピクセルの作成 空間と時間軸方向を考慮したMean Shift クラスタリングを用いて，スーパーピクセルを作成する．空間，時間，色情報を持った入力ベクトルを
xi = {xsi , xti , xri }，フィルタ結果を zi ，各ピクセルのラベ
ルを Li とする．また，{yj }j=1,2,... を以下のように定義
する．
 n yj −xi 2xg  h 
i=1 iyj+1g(x)=  yj −xi 2ghi=1(8)n= s 2   t 2   r 2 x Cx x (9)  k pk2
  k  hs ht hrhshthr

ここで，h2s , ht , hpr はそれぞれ空間，時間，色のバンド幅で，C は正規化定数である．k(x) はカーネル関数である．
Mean Shift クラスタリングは以下の手順で行われる．

1. Mean Shift により，zi = yi,c として特徴空間の情報を格納
2. 特徴空間において，zi をクラスタ {Cp }p=1,...,m にクラスタリング
3. Li = {p|zi ∈ Cp }4. 各領域において，M pixel 以下の領域を削除
バンド幅を変化させる場合，現在の各スーパーピクセルごとに Mean Shift クラスタリングを行い，スーパーピクセルを細分化させる．図 4 に，Mean Shift クラスタリングにより作成されたスーパーピクセルを示す．

を作成する手法 (従来法)，Mean Shift のバンド幅を変化させながら繰り返しグラフカットを行う手法 (提案手法) の比較を行う．
実験結果 表 1 に誤検出，図 3 にセグメンテーション結果を示す．表 1 より，従来法と比較したとき，提案手法は
表 1 : 誤検出率 [%]
従来法

提案手法

over segmentation

1.90

1.18

under segmentation

5.47

1.96

total

7.36

3.13

セグメンテーション精度を約 1.59% 向上させることができた．

5.おわりに本稿では，ガウシアンフィルタの平滑化度合いを変化させた画像に対し，平滑化度合いが大きなものから GraphCuts を繰り返し行う手法を提案した．また，動画像に対しては，Mean Shift のバンド幅を変化させることで，同様の効果を得ることができた．評価実験より，大域的なセグメンテーションから局所的なセグメンテーションと変化させることにより，従来法と比較し 1.59% 向上させることができた．

参考文献[1] Y. Boykov, M-P. Jolly, “Interactive Graph Cuts forOptimal Boundary & Region Segmentation of Objects in N-D Images” , ICCV, vol. I, pp. 105-112,
2001

研究業績
[1] 永橋知行, 藤吉弘亘, 金出武雄. “平滑化処理の繰り返しによるグラフカットを用いた画像セグメンテーション”, 情報処理学会論文誌コンピュータビジョンとイメージメディア, Vol 22,2008(掲載予定)

図 4 : スーパーピクセルの作成例[2] T. Nagahashi, H. Fujiyoshi, and T. Kanade. “ObjectType Classification Using Structure-based Feature Representation”, MVA2007, pp. 142-145, May, 2007.

実験概要 本手法の有効性を示すために評価実験を行う．
動画像に対して，初期フレームのみに seed の入力を行う．
10 フレーム目のセグメンテーション結果により評価する．
比較対象として，スーパーピクセルをノードとしてグラフ[3] T. Nagahashi, H. Fujiyoshi, and T. Kanade. “Image Segmentation Using Iterated Graph Cuts Based on Multiscale Smoothing”, ACCV2007, Part II, LNCS 4844, pp.
806-816.
(他 研究会技術報告 2 件, 学会口頭発表 3 件)

4.評価実験