画像セグメンテーションにおけるウェーブレット係数の局所テクスチャ特徴を用いたGraph Cuts 福田恵太・滝口哲也・有木康雄 (神戸大学)

研究目的 画像の認識，識別，検索，編集など 様々な画像処理技術の前処理 画像処理における重要な問題の一つに一枚の画像から対象と なる領域を抽出するセグメンテーションの問題がある． 画像の認識，識別，検索，編集など 様々な画像処理技術の前処理

近年，セグメンテーション問題をエネルギー最小化問題で解く手法が多く提案されている． 研究背景 近年，セグメンテーション問題をエネルギー最小化問題で解く手法が多く提案されている． ⇒その中でGraph Cutsという手法を用いる． Y.Boykov, M.P.Jolly,“Interactive graph cuts for optimal boundary & region segmentation of object in N-D images”, IEEE International Conference on Computer Vision and Pattern Recognition その利点は… エネルギー最小化問題を大域的な解で求めることが可能 　Snakes, Level Set Methodでは境界線を元に局所解を求める 他のエネルギー最小法より性能がよい 　Belief Propagation, Message Passing法との比較実験 容易なラベル付けで，与え方に依存しにくい

Graph Cuts O B t-link Object terminal S T O B n-link 物体らしさを表す 近傍の画素関係を表す O B グラフの作成 入力画像 (3×4) 背景らしさを表す S T O B min cut カット Background terminal t-link セグメンテーション S→Tへの重み総和が最小となるカット セグメンテーション結果

従来法の問題点 (1) t - link > n - link 色分布が強くなり，突発的な誤検出 n - link > t - link エッジ情報が強くなり，局所的なエッジに弱い 平滑化処理の繰り返しによるグラフカット 　 局所的なエッジ情報に頑健なセグメンテーションが可能 T. Nagahashi, H.Fujiyoshi, and T.Kanade，“ Image Segmentation Using Iterated Graph Cuts Based on Multi-scale Smoothing， ”ACCV2007

従来法の問題点 (2) 提案手法 物体及び背景が類似した色を持つ画像 色分布からのセグメンテーションが困難 局所テクスチャ特徴量を色分布と共に t - linkで扱う 色分布に依存せずセグメンテーションが可能 提案手法 Haar Wavelet変換に基づく多重解像度解析により平滑化と局所テクスチャ特徴の定義を並列に行い，グラフカットによるセグメンテーションを繰り返し行う．

Graph Cuts Segmentation 提案手法 LL,LH,HL,HH画像取得 Graph Cuts Segmentation 事前確率 GMM(色+テクスチャ)の更新 k ← k-1 LL: 平滑化画像 LH,HL,HH:テクスチャ特徴 Haar Waveletによる多重解像度解析 (level k) seed 入力 出力 t-link n-link SeedとLevel kを与える． Level kまで多重解像度解析 平滑化画像をn-linkに使用 局所テクスチャ特徴を定義 5. 色＋テクスチャをGMMに適用 6. 一段階前の結果から事前確率 7. Graph Cutsの処理を行う 8. k=0まで，2.～7.を繰り返す

多重解像度解析 LH1 HL1 HH1 LL1 多重解像度解析 画像データを特定の周波数帯域を持ついくつかの小さいサイズの画像データに分割する方法. Level 1 Level 2 LL:平滑化画像 　HL:縦方向 LH:横方向 HH:斜め方向の変化量 Haar Wavelet 変換　（k=2の時） Level 0 Level 1 Level 2

Graph Cuts Segmentation LL,LH,HL,HH画像取得 Graph Cuts Segmentation 事前確率 GMM(色+テクスチャ)の更新 k ← k-1 LL: 平滑化画像 LH,HL,HH:テクスチャ特徴 Haar Waveletによる多重解像度解析 (level k) seed 入力 出力 t-link n-link SeedとLevel kを与える． Level kまで多重解像度解析 平滑化画像をn-linkに使用 局所テクスチャ特徴を定義 5. 色＋テクスチャをGMMに適用 6. 一段階前の結果から事前確率 7. Graph Cutsの処理を行う 8. k=0まで，2.～7.を繰り返す

n – linkの更新 n - link ：近傍との輝度値を比較し，注目画素と近傍 とのエッジの重みを決定する LL：平滑化画像 (n-link) 低解像画像から徐々に解像度を上げることで，大域的から局所的なセグメンテーションを可能とする． 輝度値が類似しているほど高い値を持つ． Level 1 Level 0 p q

Graph Cuts Segmentation LL,LH,HL,HH画像取得 Graph Cuts Segmentation 事前確率 GMM(色+テクスチャ)の更新 k ← k-1 LL: 平滑化画像 LH,HL,HH:テクスチャ特徴 Haar Waveletによる多重解像度解析 (level k) seed 入力 出力 t-link n-link SeedとLevel kを与える． Level kまで多重解像度解析 平滑化画像をn-linkに使用 局所テクスチャ特徴を定義 5. 色＋テクスチャをGMMに適用 6. 一段階前の結果から事前確率 7. Graph Cutsの処理を行う 8. k=0まで，2.～7.を繰り返す

テクスチャの変化量が大きい領域ほど値が大きい 局所テクスチャ特徴量 HL,LH,HH：局所テクスチャ特徴を定義 注目画素ｐ周辺 (３×３) のウェーブレット係数の絶対値平均 とする 元画像 LH (Level 1) HH (Level 1) HL (Level 1) テクスチャの変化量が大きい領域ほど値が大きい

Graph Cuts Segmentation LL,LH,HL,HH画像取得 Graph Cuts Segmentation 事前確率 GMM(色+テクスチャ)の更新 k ← k-1 LL: 平滑化画像 LH,HL,HH:テクスチャ特徴 Haar Waveletによる多重解像度解析 (level k) seed 入力 出力 t-link n-link SeedとLevel kを与える． Level kまで多重解像度解析 平滑化画像をn-linkに使用 局所テクスチャ特徴を定義 5. 色＋テクスチャをGMMに適用 6. 一段階前の結果から事前確率 7. Graph Cutsの処理を行う 8. k=0まで，2.～7.を繰り返す

t - linkの更新 (1) ：色+テクスチャ特徴量 物体らしいほど　　高い値をもつ 物体と背景の事後確率から，t-linkの重みを計算する S:”obj” T:”bkg” O B ：色+テクスチャ特徴量 背景らしいほど　　高い値をもつ

t - linkの更新 (2) 事前確率 （空間情報） 事後確率 O B 距離変換 T {p,T}間のt-linkへ使用 色 (RGB) テクスチャ特徴　をＧＭＭ T O B 距離変換 一つ前の物体領域 {p,T}間のt-linkへ使用 事前確率　（空間情報） 物体と背景の境界を0.5とし，境界からの距離を用いて，事前確率を定義する．

t - linkの更新 (3) 事前確率 （空間情報） 事後確率 S p 距離変換 {p,S}間のt-linkへ使用 色 (RGB) テクスチャ特徴　をＧＭＭ 距離変換 一つ前の背景領域 {p,S}間のt-linkへ使用 事前確率　（空間情報） 背景も同様に{p,S}間の全てのエッジに重みを与える．

Graph Cuts Segmentation LL,LH,HL,HH画像取得 Graph Cuts Segmentation 事前確率 GMM(色+テクスチャ)の更新 k ← k-1 LL: 平滑化画像 LH,HL,HH:テクスチャ特徴 Haar Waveletによる多重解像度解析 (level k) seed 入力 出力 t-link n-link SeedとLevel kを与える． Level kまで多重解像度解析 平滑化画像をn-linkに使用 局所テクスチャ特徴を定義 5. 色＋テクスチャをGMMに適用 6. 一段階前の結果から事前確率 7. Graph Cutsの処理を行う 8. k=0まで，2.～7.を繰り返す

Graph Cuts Segmentation エッジに対する重み S T O B 以上のように全エッジに対して重みを与え， ※ min-cut / max-flowアルゴリズムにより，グラフのカットを行い，セグメンテーション画像を得る Yuri Boykov and Vladimir Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision”

実験条件 評価方法として， 従来手法(1) Graph Cuts 従来手法(2) 平滑化処理のみのGraph Cuts Berkley Image database(50枚)を使用 (HS画像あり) 多重解像度解析はLevel 3まで実行 以下の式から誤検出率err(%)を算出 物体を背景と誤検出 背景を物体と誤検出

実験結果（1） Err(%) 4.05 2.42 1.57 従来手法でも十分精度が出ている画像も含まれているため，精度差が大きくでていない． 従来手法(1) 従来手法(2) 提案手法 Err(%) 4.05 2.42 1.57 従来手法でも十分精度が出ている画像も含まれているため，精度差が大きくでていない． 従来手法でも誤検出率を約４％まで抑えている． 比較的誤検出率が高かった画像について

実験結果（2） 平滑化と事前確率による効果 元画像+seed 従来手法(1) 従来手法(2) 提案手法 17.86% 4.42% 1.93% 9.96% 0.87% 0.57%

実験結果（3） テクスチャ特徴量による効果 元画像+seed 従来手法(1) 従来手法(2) 提案手法 10.56% 7.45% 1.86% 11.26% 10.54% 4.77% 11.84% 16.64% 1.99%

実験結果（4） テクスチャ変化の度合いが異なる画像に対する効果 元画像+seed 従来手法(1) 従来手法(2) 提案手法

考察 突発的なノイズの除去：従来手法(2), 提案手法 事前確率 一つ前の処理結果から大まかな形情報を取得 平滑化処理 　突発的なノイズの除去：従来手法(2), 提案手法 　事前確率 　一つ前の処理結果から大まかな形情報を取得 　平滑化処理 　局所的なエッジを乗り越えることが可能 　色分布で区別が困難な画像：提案手法 　テクスチャ変化の大きい画像 　自然物画像などには効果が大きい． 　テクスチャ変化の小さい画像 　人工物画像などにはあまり効果がない．

まとめ 多重解像度解析により平滑化と局所テクスチャ特徴を用いた繰り返しによるGraph Cutsを提案した． 　テクスチャ特徴と色特徴どちらが有効か画像ごとに違うためその差を考える．

ご静聴ありがとうございました．

Graph Cuts エネルギー関数を最小とするようなラベル f を求める手法． (エネルギー最小化問題) 活用例 領域に対するペナルティ 近傍に対するペナルティ 活用例 Image Segmentation Stereo Image Restoration Multi camera reconstruction などで注目されている ピクセルをノードとしたグラフを作成し，そのグラフの最小カットを 求めることで，物体と背景のセグメンテーションを行う．

処理時間について 画像サイズ：650×400 従来(1) 従来(2) 提案 10.92秒 62.96秒 87.22秒 画像サイズ：480×320 従来(1) 従来(2) 提案 8.04秒 36.77秒 55.43秒 Pentium® 4 CPU 3.20GHz

20 Min-cut 20 20 100 80 30 S T 60 20 10 S 20 20 T 残余ネットワーク(1) 10 10 10 50 50 40 20 20 Min cut 60 20 グラフの最小カットを求める S T 20 50 20 残余ネットワーク(2) 10 10 S 20 T 10 20 20 10 10 50 40 20 S 30 20 10 40 T 30 最大フロー(60) 10 10 20 最大フローと最小カットの値は等しい！ 残余ネットワーク(3)

ＳからTへのコストが最も小さくなるようにカットする Min-cutの概念 Ｓ つながりが強いほどカットは通らない． Ｔ ＳからTへのコストが最も小さくなるようにカットする