thesis.dvi

2007

年度修士論文

グラフカットによる

領域セグメンテーションに関する研究

指導教授

藤吉 弘亘

中部大学大学院

工学研究科

情報工学専攻

博士前期課程

修士論文題目

グラフカットによる

領域セグメンテーションに関する研究

情報工学専攻 氏名 永橋知行 論文要旨

近年，高精度な画像セグメンテーションの手法として，

Graph

Cuts

が提案されている．しかし，

Graph Cuts

による画像セグ

メンテーションでも，物体と背景のエッジ以外に複雑なエッジ

を含む画像に対しては正確なセグメンテーションを行うのは

困難である．このような問題に対して，本論文では，平滑化度

合いを変化させ，繰り返し処理による

Graph Cuts

を用いた高

精度な画像セグメンテーション法を提案する．ガウシアンフィ

ルタの平滑化度合いを変化させた画像に対し，平滑化度合い

が大きなものから

Graph Cuts

を行い，そのセグメンテーショ

ン結果をグラフの

t-link

に反映させ，次の平滑化度合いのセグ

メンテーションに利用する．これらを繰り返し処理することに

より，大域的なセグメンテーションから段階的に局所的なセグ

メンテーションを行うことができるため，画像に複雑なエッジ

が存在する場合でも頑健なセグメンテーションが可能となる．

評価実験より，提案手法は従来の

Interactive Graph Cuts

と比

較し，

4.7%

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

た．また，動画像セグメンテーションに対しては，ノードの数

が増加するという問題がある．そこで，バンド幅を変化させな

がら，

Mean Shift Segmentation

を用いてスーパーピクセルを作

成することで，大域的なセグメンテーションから局所的なセグ

メンテーションを行う手法を実現する．

目 次

第 1 章 まえがき 1 第 2 章 グラフカットによる画像セグメンテーション 3 2.1 グラフカットとエネルギー最小化問題 . . . . 3 2.1.1 ラベリング問題 . . . . 3 2.2 グラフカットアルゴリズム . . . . 5 2.2.1 領域のセグメンテーション . . . . 7 2.2.2 従来法：グラフカットを用いた画像セグメンテーション . . . . 8 2.2.3 従来法の問題点 . . . . 9 第 3 章 平滑化処理の繰り返しによるグラフカット 11 3.1 提案手法の流れ . . . 11 3.2 平滑化画像の作成 . . . 13 3.3 繰り返し処理によるグラフカット . . . 14 3.3.1 色分布確率の更新 . . . 14 3.3.2 空間的確率の更新 . . . 15 3.4 繰り返し処理とその効果 . . . 15 3.5 セグメンテーション評価実験 . . . 16 3.5.1 実験概要 . . . 16 3.5.2 実験結果 . . . 17 3.5.3 考察 . . . 18 3.6 まとめ . . . 20 第 4 章 動画像に対するグラフカットによるセグメンテーション 21 4.1 従来法 . . . 21 4.2 スーパーピクセルを用いた繰り返し処理によるグラフカット . . . 21 4.2.1 スーパーピクセルの作成 . . . 21 4.3 評価実験 . . . 23 4.4 まとめ . . . 24

第 5 章 領域分割に基づく SIFT 特徴を用いた物体識別 25 5.1 Bag of Keypoints . . . 25 5.1.1 歴史的背景 . . . 25 5.1.2 Bag of Keypoints による物体識別 . . . 25 5.1.3 特徴量抽出の流れ . . . 26 5.1.4 識別器 . . . 27 5.2 構造に基づく特徴量抽出 . . . 29 5.2.1 混合正規分布を用いた領域分割 . . . 29 5.2.2 特徴量抽出 . . . 31 5.2.3 ベクトル量子化ヒストグラム . . . 32 5.3 グラフマッチングによる物体識別 . . . 33 5.3.1 グラフによる特徴量の記述 . . . 33 5.3.2 グラフマッチング . . . 34 5.4 物体識別評価実験 . . . 35 5.4.1 屋外環境データにおける評価実験 . . . 35 5.4.2 一般物体認識における評価実験 . . . 36 5.5 まとめ . . . 37 第 6 章 むすび 41 謝  辞 43 参考文献 45 研究業績一覧 49 付 録 A Mean Shift 51 A.1 核密度推定 (Kernel Density Estimation) . . . 51

A.2 密度勾配推定 (Density Gradient Estimation) . . . 52

付 録 B Scale-Invariant Feature Transform 55 B.1 スケールとキーポイント検出 . . . 55 B.1.1 LoG によるスケール探索 . . . 55 B.1.2 Difference-of-Gaussian 処理 . . . 57 B.1.3 σ の連続性を保持した平滑化処理 . . . 57 B.1.4 増加率 k . . . 59 B.1.5 DoG 画像からの極値検出 . . . 60 B.2 キーポイントのローカライズ . . . 60 B.2.1 主曲率によるキーポイントの絞り込み . . . 61 ii

B.2.2 キーポイントのサブピクセル位置推定 . . . 62 B.2.3 コントラストによるキーポイントの絞り込み . . . 63 B.3 オリエンテーションの算出 . . . 64 B.4 特徴量の記述 . . . 64 B.5 画像変化に対する SIFT 特徴量 . . . 66 付 録 C 発表原稿 69

図 目 次

2.1 ラベリング問題 . . . . 4 2.2 ネットワーク . . . . 5 2.3 グラフ例 . . . . 6 2.4 s-t cut . . . . 6 2.5 Lazy Snapping によるセグメンテーション例 (文献 [1] より) . . . . 8 2.6 Grabcut によるセグメンテーション例 (文献 [2] より) . . . . 9 2.7 複雑なエッジを含む画像でのグラフカットによるセグメンテーション . . . 9 3.1 手法の流れ . . . 11 3.2 繰り返し処理によるセグメンテーション例 . . . 12 3.3 ダウンサンプリングを用いた平滑化 . . . 13 3.4 空間的確率と色分布確率の更新の流れ . . . 14 3.5 各平滑化画像に対する n-link と t-link の変化とセグメンテーション結果例 . 17 3.6 セグメンテーション例と誤検出率 . . . 19 3.7 λ の変化によるセグメンテーション結果の違い . . . 20 4.1 従来法によるグラフカットによる動画像セグメンテーション . . . 22 4.2 手法の流れ . . . 23 4.3 スーパーピクセルの作成例 . . . 23 4.4 セグメンテーション結果 . . . 24 5.1 Bag of Keypoints の流れ . . . 26

5.2 Affine Invariant keypoint を用いた SIFT 特徴量の抽出：(a)Affine Invariant keypoint (b) 正規化された領域 (c) 8 方向の輝度勾配強度  (文献 [3] より) . 27 5.3 検出領域に対しての混合正規分布の当てはめ例 . . . 29 5.4 GMM によるセグメンテーション例 . . . 30 5.5 Mean-Shift セグメンテーションとの違い . . . 31 5.6 重み付き方向ヒストグラム . . . 32 5.7 SIFT 特徴量の記述 . . . 32 5.8 特徴量抽出 . . . 33

5.9 物体識別の流れ . . . 33 5.10 グラフによる記述 . . . 34 5.11 実験データ例 . . . 35 5.12 人と二輪車の特徴量の違い . . . 38 5.13 正解データ例 . . . 39 5.14 実験データ例 . . . 39 5.15 実験結果 . . . 40 5.16 回転画像に対する領域分割結果 . . . 40 A.1 式 (A.13) の関係 . . . 53

A.2 Mean Shift による最頻値探索 (文献 [4] より) . . . 54

B.1 LoG オペレータ . . . 56 B.2 DoG 処理の流れ . . . 57 B.3 σ の連続性を保持した効率的な平滑化処理 . . . 58 B.4 s = 2 のときの DoG 処理例 . . . 59 B.5 極値検出の流れ . . . 60 B.6 スケールと DoG 出力の関係 . . . 61 B.7 キーポイント候補点の絞り込み . . . 62 B.8 ヒストグラム作成の流れ . . . 65 B.9 2 方向のオリエンテーションを持つキーポイント . . . 66 B.10 特徴量を記述する領域 . . . 66 B.11 ブロックごとの特徴量記述 . . . 67 B.12 画像変化に対する SIFT 特徴量 . . . 68 vi

表 目 次

2.1 エッジに与える重み . . . . 7 3.1 誤検出率 [%] . . . 18 3.2 誤検出率 [%] . . . 18 3.3 各手法の処理時間 [s]（繰り返し回数） . . . 20 4.1 誤検出率 [%] . . . 23 5.1 各手法での識別結果 [%] (文献 [5] より) . . . 27 5.2 識別結果 [%] . . . 36 5.3 識別結果 (α = 0.1) . . . 36

第

1

章

まえがき

画像処理における重要な問題の一つに一枚の画像から対象となる領域を抽出する画像 セグメンテーションの問題がある．画像セグメンテーションは，一般物体認識，合成画像 の生成などの前処理として利用されるため重要な問題である． 近年，画像セグメンテーション問題をエネルギー最小化問題として解く手法が提案され ている．このような手法として，Snake などの動的輪郭モデル [6] や Level Sets[7], Graph Cuts [1, 2, 8, 9, 10, 11] などが挙げられる．Snake や Level Sets は境界線に対してのエネ ルギー関数を作成し，エネルギー関数が小さくなるように境界線を変化させる手法であ る．そのため，これらの手法では局所解しか求めることができないというデメリットがあ る．一方，Graph Cuts では各領域からエネルギー関数を定義し，それらの大域解を求め ることが可能である．

Graph Cuts を用いたセグメンテーション手法として， Boykov らにより Inreractive Graph Cuts [9, 10] が提案されている．Interactive Graph Cuts では，ユーザが与えた正 解ラベルと画像からグラフを作成し，minimum cut/maximum flow algorithm を用いるこ とで，エネルギー関数の最小化を行う．この Interactive Graph Cuts を基にした手法とし て，高速化のためにスーパーピクセルをノードとしてグラフへ拡張した Lazy Snapping[1] やセグメンテーション精度を向上させるために繰り返し処理により前景と背景の色分布を セグメンテーション結果から再学習し，繰り返しセグメンテーションをする Grab Cut[2] などが提案されている．これらの Graph Cuts による画像セグメンテーションでは，複雑 なエッジ情報を含んだ画像に対しては正確な物体領域を抽出することが困難という問題点 がある．これは，ピクセル間の輝度値から計算される n-link の影響により，局所的なエッ ジを乗り越えることができないためである． そこで，本論文では複数の平滑化画像を用いて繰り返し処理によるグラフカットセグ メンテーション法を提案する．本手法では，ガウシアンフィルタの平滑化度合いを変化さ せた画像に対し，平滑化度合いが大きなものから Graph Cuts を行い，そのセグメンテー ション結果をグラフの t-link に反映させ，次の平滑化度合いのセグメンテーションに利用 する．これらを繰り返し処理することにより，大域的なセグメンテーションから段階的に 局所的なセグメンテーションを行う．また，動画像に対しては，スーパーピクセルのバン ド幅を変化させることで，大域的なセグメンテーションから段階的に局所的なセグメン テーションを実現する．評価実験により，本手法が静止画と動画像のセグメンテーション

に対して有効であることを述べる．

各章の構成

本論文は 7 つの章から構成される．1 章は本研究の背景と，提案手法の概要を述べ，2 章 はグラフカットによる画像セグメンテーション手法について述べる．3 章では平滑化とセ グメンテーションを繰り返し処理する方法とその効果について述べる．4 章では，本手法 を動画像セグメンテーションへ適応させた手法について述べる．5 章では，セグメンテー ションの応用例として，領域分割に基づく物体識別手法について述べる．最後の 6 章で本 論文のまとめとする．また，領域分割手法として用いる Mean Shift，物体識別に用いる 特徴量として利用する SIFT について付録に載せる． 2

第

2

章

グラフカットによる画像セグメンテー

ション

2.1

グラフカットとエネルギー最小化問題

コンピュータビジョンの問題として，エネルギーを最小化する問題がある．例えば，画 像をピクセル単位で輝度，視差，領域分割などでラベリングをする問題が挙げられる．実 画像に対してラベリングを行う場合，画像のノイズなどの影響により不明確な部分が存 在する可能性があり，最適なラベリングを行うことは困難である．そこでエネルギー最小 化問題に対して，Boykov らは minimum cut/maximum flow algorithms を利用してエネ ルギーを最小化する方法 [8] を提案している．彼らの手法では，問題設定に合うようにグ ラフを作成し，そのグラフの minimun cut を求めることにより，エネルギー関数の最小 化を行う．この minimum cut は max flow algorithm を用いることにより，効率的に計算 することが可能である．近年，minimum cut/maximum flow algorithms に基づいた手法 が提案されており，image restoration [12, 13, 14, 15], stereo and motion [16, 17, 18, 19], image segmentation [9, 20, 21], multi-camera reconstruction [22] などさまざまな分野に応 用されている．本章では，ラベリング問題，グラフカットアルゴリズムについて述べ，そ して，グラフカットアルゴリズムを用いた領域のセグメンテーション，グラフカットステ レオについて述べる．

2.1.1

ラベリング問題

ラベリング問題とは，画像 P の各ピクセル p に対して，ラベル Lpをつけていく問題で ある．このラベリングを何に対して行うかは，求める問題により異なる．例えば，ステレ オでは depth に対してラベリングをし，セグメンテーションでは各物体に対してラベリン グする．図 2.1 では，輝度値に対してラベリングを行った結果である．このようなラベリ ング問題に対する，解法の１つとしてエネルギー関数 E(L) を以下のように定義し，これ を最小化する方法がある． E(L) =
p∈P Dp(Lp) +
(p,q)∈N V_(p,q)(Lp, Lq) (2.1)

図 2.1: ラベリング問題 ここで，N は近傍領域のピクセル，Dp(Lp) は観測データに対してのペナルティー関数， V_(p,q)(Lp, Lq) は近傍ピクセルとの相互関係を表した関数である． ■ エネルギー最小化モデル エネルギー関数 E は，同一のもののラベリングや境界が不連続なものなど，どのよう な問題に対して行うかにより決定される．このエネルギー関数のモデルとして， Potts Interaction Energy Model と Liner Interaction Energy Model の 2 つが提案されている．

■ Potts Interaction Energy Model

Potts Interaction Energy Model では，エネルギー関数を以下のように定義している．

E(I) =
p∈P ||Ip− Ip◦|| +
(p,q)∈N K_(p,q)· T (Ip
= Iq) (2.2) ここで，I = {Ip|p ∈ P } は正解データの集合で，ここでは，ラベルの事を指す．I◦ = {I◦ p|p ∈ P } はノイズが混入している観測データである．この項では，入力されたデータと の差が小さくなるようなラベルが付けられるようにしたものである．また，K(p, q) は近 傍ピクセルとのラベルの不連続性を表したペナルティー関数，T (Ip, Iq) は Ipと Iqを比較 する指標関数であり，Ipと Iqが異なる場合は 1, それ以外は 0 を返す．この K(p, q) は，p と q が似ている場合は大きくなる関数であるが，同じラベルが付いている場合は T (Ip, Iq) が 0 となる為反映されない．そのためこの項では，近傍で異なるラベルがつけられてお り，かつ似ていないほど小さくなるといえる．この Potts Energy は 2 値のラベリングで は max flow を用いることにより最適解を得ることが可能であるが，多値のラベリングで は NP hard 問題となるため，最適解を得られない可能性がある． 4

■ Liner Interaction Energy Model

次に，Liner Interaction Energy Model は以下のように定義される.

E(I) =
p∈P ||Ip− Ip◦|| +
(p,q)∈N A_(p,q)· |Ip− Iq| (2.3)

このモデルと Potts Model では A_(p,q)と K_(p,q)の項が異なる．A_(p,q)は近傍ピクセルである

p と q の重要性を表す関数である．このエネルギー関数は，Potts Energy よりも多くのラ

ベルを扱う際に有効である．

2.2

グラフカットアルゴリズム

定義したエネルギー関数 E に基づきグラフを作成し，min-cut/max-flow algorithm より 最適解を求める．このようにして最適解を求める手法はコンピュータビジョンでは Graph Cuts Algorithm と呼ばれている．もともとの min-cut/max-flow algorithm は以下のよう なネットワークに対して，どの程度の量を最大流すことができるかを求める手法である． この章では，min-cut/max-flow algorithm について述べる． 図 2.2: ネットワーク ■ グラフ 重み付き有向グラフを G = (E, V ) と定義する．このとき，V はノード (node)，E は エッジ (edge) である．このグラフをコンピュータビジョンの問題で使用する場合はピクセ ルやボクセルなどがノードとなる．またピクセルやボクセル以外のノードとして，ソース (source)s ∈ V とシンク (sink)t ∈ V と呼ばれる特殊なターミナル（ラベル）を追加する． エッジはノード間の関係を表現しており，周辺のピクセルやボクセルとの関係を表したも のを n-link，各ピクセルやボクセルと s，t との関係を表したものを t-link と呼ぶ．n-link

のコストは，周辺ピクセルとの連続性を表現したペナルティ関数により決定され，t-link のコストは各ピクセルがそのラベルである確率を表したペナルティ関数により決定され る．n-link と t-link は，式 (2.1) の Vp,qと Dpに相当する．作成されるグラフをネットワー クグラフと呼ぶ（図 2.3(a)）． 図 2.3: グラフ例 ■ 最小カットと最大フロー ネットワークグラフを s∈ S と t ∈ T = V − S となる 2 つのグラフへの分割を考える． 分割する際に切断されるエッジを s-t カットと呼ぶ．その切断されるカットのうち S から T へ接続されているエッジのコストの総和を s-t カットの容量という．この s-t カットの容 量が最小となる s-t カット（最小カット）を求めたい．この最小カットは，最大フロー最 小カットの定理を用いることによって，ネットワークグラフの最大フローから求めること が可能である． 図 2.4: s-t cut

最大フローを求める手法の代表的なものとして，Ford-Fulkerson Method[23] と Push-Relabel Method[24] がある．Ford-Fulkerson Method はフローの増分路が存在しないとき，

そのフローは最大であるという考えに基づいている．はじめに，フローを 0 として s から t への増分路を探索し，フローを増加させる．この作業を増分路がなくなるまで繰り返す ことにより，最大フローを求める．Push-Relabel Method では，s から近傍のノードへ可 能な限りフローを流し，それをすべてのノードに対して繰り返すことにより最大フローを 求める．

2.2.1

領域のセグメンテーション

グラフカットアルゴリズムを用いて領域のセグメンテーションを行う．作成するグラフ は，Potts Interaction Energy Model に従い以下のように定義する．

E(L) = λ· R(L) + B(L) (2.4) R(L) =
p∈P Rp(Lp) (2.5) B(L) =
{p,q}inN B_{p,q}· δ(Lp, Lq) (2.6) δ(Lp, Lq) =  1 if Lp
= Lq 0 otherwise (2.7) ここで，R(L) は領域情報，B(L) は境界情報，λ は R(L) のパラメータ係数である．この エネルギー関数 E(L) に基づき，グラフのエッジのコストを計算する（表 2.1）． 表 2.1: エッジに与える重み

edge weight(cost) for

{p, q} B_{p, q} {p, q} ∈ N λ· Rp(”bkg”) p∈ P, p ∈/O ∪ B {p, S} K p∈ O 0 p∈ B λ· Rp(”obj”) p∈ P, p ∈/O ∪ B {p, T } 0 p∈ O K p∈ B ここで，

Rp(“obj”) = − ln Pr(Ip|O) (2.8)

B_{p,q} ∝ exp  −(Ip− Iq)2 2σ2  · 1 dist(p, q) (2.10) K = 1 + max p∈P
q:{p,q}∈N B_{p,q} (2.11) となる．O は物体, B は背景を意味し, また，Ip はピクセル p の輝度値である．ユーザ は一部のピクセルに対してO, B を入力する．このとき入力された O, B を seed と呼ぶ．

Pr(Ip|O), Pr(Ip|B) は seed 以外のピクセルの t-link に設定する物体と背景の尤度である．

dist(p, q) はピクセル p, q

のユークリッド距離を用いる．作成したグラフに対して，min-cut/max-flow algorithm を用いることで，物体と背景にグラフを分割する．このような処 理により，インタラクティブな画像セグメンテーションを実現する．

2.2.2

従来法：グラフカットを用いた画像セグメンテーション

グラフカットを用いた画像セグメンテーション法として，Li らは Lazy Snapping [1] を 提案している．Lazy Snapping では，スーパーピクセルを用いて処理速度の向上と使い やすいユーザインタフェースを用いることでインタラクティブ性を高めている（図 2.5）． また，Rother らにより提案された GrabCut [2] を提案している．GrabCut は，対象を矩

図 2.5: Lazy Snapping によるセグメンテーション例 (文献 [1] より)

形領域で指定し，そこから，物体と背景の色分布を GMM にモデル化し，Graph Cuts に よりセグメンテーションを行う．得られたセグメンテーション結果から，色分布を再学習 することで，高精度なセグメンテーションを実現している（図 2.6）．

図 2.6: Grabcut によるセグメンテーション例 (文献 [2] より)

2.2.3

従来法の問題点

従来法である Interactive Graph Cuts[9], [20] では，seed が与えられていない t-link の エッジコストには，seed の色分布から得られる尤度を利用して計算するか 0 とする．尤 度の計算を行う場合，n-link に比べ t-link が大きくなると，色分布による影響が強くなり， 突発的な誤検出が多くなる場合がある．そのため，このような誤検出を抑制するためには，

λ によって n-link の影響を強くする必要がある．n-link の影響が強いと，画像中のエッジ

情報に対しての依存性が強くなる．そのため，図 2.7 に示すように Interactive Graph Cuts では画像に複雑なエッジが存在する場合，局所的なエッジを乗り越えてセグメンテーショ ンすることが困難となる．

第

3

章

平滑化処理の繰り返しによるグラフカット

本研究では平滑化度合いの異なる複数の画像を使用し，平滑化度合いの大きなものから Graph Cuts を繰り返し行うことにより，局所的なエッジ情報に頑健なセグメンテーショ ン手法を提案する．

3.1

提案手法の流れ

図 3.1 に，提案手法の流れを示す．はじめに，入力画像に対してユーザが物体と背景の 図 3.1: 手法の流れ seed の入力を行う．次に，平滑化度合いを決定する σ の初期値を決定する．これは画像サ イズを半分にダウンサンプリングした際の画像の長辺が一定値 l 以下になる画像を平滑化 を開始する画像とし，そこから σ の初期値を決定する．決定した σ を用いてガウシアン フィルタにより平滑化画像を作成し，それを入力画像として Graph Cuts を行う．Graph Cuts により，物体領域と背景領域の色分布に対して GMM(Gaussian Mixture Model) の 当てはめを行う．また，物体領域と背景領域に対して距離変換を行い各ピクセルごとに物 体と背景の事前確率を更新する．GMM の尤度と距離変換による事前確率から各ピクセル ごとに物体と背景の事後確率を計算したものをグラフの t-link に設定し，次の Graph Cuts 処理に利用する．この処理を σ < 1 でセグメンテーション結果に変化がないか，σ = 0 と

Cut を行う．このときの 0 < α < 1 である． これらの手順を以下に示す．

Step1. seed の入力 Step2. σ の初期値計算 Step3. 画像の平滑化 Step4. Graph Cuts

Step5. セグメンテーション結果から事後確率の計算 Step6. σ < 1 でセグメンテーション結果が変化しなくなるか，σ = 0 となったら終了，そ れ以外ならば σ = α· σ(0 < α < 1) と更新し Step 3 へ このような繰り返し処理により，大域的なセグメンテーションから段階的に局所的なセ グメンテーションを実現している様子を図 3.2 に示す．以下に平滑化画像の作成方法と繰 り返し処理の詳細について述べる． 図 3.2: 繰り返し処理によるセグメンテーション例 12

3.2

平滑化画像の作成

  ガウシアンフィルタを用いて，平滑化画像を作成する．画像を I，ガウス分布を G(σ) としたとき，平滑化画像 L(σ) は以下の式で計算される． L(σ) = G(σ)∗ I (3.1) 大きい σ の場合にはフィルタのウィンドウサイズを大きくする必要がある．ウィンドウサ イズが大きくなると，画像の端といった信頼性が低い領域の増加，処理時間の増加という 問題点が挙げられる．そこで本手法では，画像のダウンサンプリングにより σ の変化の連 続性を保持した平滑化画像を作成する． はじめに，入力画像 I₁に対して σ を 1 から 2 へ増加させて平滑化画像 L₁(σ) を作成す る．次に，画像 I のサイズを半分にダウンサンプリングしたものを I₂とする．この画像 I₂に対して，σ = 1 として平滑化画像 L₂(σ) を作成する．L₁(σ) と L₂(σ) には以下の式が 成り立つ． L₁(2σ) =.. L2(σ) (3.2) この関係を利用することにより，ダウンサンプリングを行ったものに対して，σ を 1 から 2 の間で変化させることで，ウィンドウサイズを変化させることなく元の画像サイズに対 して σ を連続的に大きくすることができる．これをダウンサンプリング後の画像サイズ がある程度小さくなるまで繰り返すことにより，通常のガウシアンフィルタでは不可能な サイズの σ に対しても連続的に平滑化画像を作成することが可能となる．図 3.3 にその流 れを示す． 図 3.3: ダウンサンプリングを用いた平滑化

3.3

繰り返し処理によるグラフカット

σ が大きな平滑化画像から Graph Cuts を繰り返し行う．従来の Graph Cuts では，t-link

は式 (2.8), (2.9) の尤度を用いて計算する．これを本手法では 1 回前の Graph Cuts の結果 から事後確率を以下の式により計算し，t-link に用いる． R_p(“obj”) = − ln Pr(O|Ip) (3.3) R_p(“bkg”) = − ln Pr(B|Ip) (3.4) このとき，Pr(O|Ip) と Pr(B|Ip) はベイズの定理から式 (3.5), (3.6) により計算する． Pr(O|Ip) = Pr(O)Pr(Ip|O) Pr(Ip) (3.5) Pr(B|Ip) = Pr(B)Pr(Ip|B) Pr(Ip) (3.6) 分母の Pr(Ip) は Pr(O) と Pr(B) の両方にあるため，これらの大小関係には影響がないの

で無視することができる．尤度 Pr(Ip|O), Pr(Ip|B) は従来法と同様に色分布確率を用いる．

事前確率 Pr(O), Pr(B) には，１つ前のセグメンテーション結果から空間的確率を計算す る．空間的確率を用いることで，１つ前のセグメンテーション結果に基づいて，次のセグ メンテーションの注目位置を変化させる．この色分布確率と空間的確率を繰り返し処理の 中で更新し，t-link に反映させることで，大域的なセグメンテーションから局所的なセグ メンテーションを行う．図 3.4 に，色分布確率と空間的確率の更新の流れを示す． 図 3.4: 空間的確率と色分布確率の更新の流れ

3.3.1

色分布確率の更新

色分布確率 Pr(Ip|O), Pr(Ip|B) の計算には，GMM (Gaussian Mixture Model) [25] を用

いて色分布を表現する．当てはめる色分布は RGB の 3 次元となるため，以下の式を用

いる． Pr(Ip|·) = K
i=1 αipi(Ip|µi, Σi) (3.7) p(Ip|µ, Σ) = 1 (2π)3/2|Σ|1/2 · exp  1 2(Ip− µ) T Σ−1(Ip − µ)  (3.8) GMM を物体と背景の各領域の色分布に対して EM アルゴリズム [26] を用いて当てはめ る．これにより，ヒストグラムでは離散的であった値に対して，GMM を用いることによ り連続的に取り扱うことができる．当てはめた GMM のパラメータから式 (3.7) を用いる

ことにより，Ipの色分布確率 Pr(Ip|O) と Pr(Ip|B) を求める．

3.3.2

空間的確率の更新

1 つ前の Graph Cuts のセグメンテーション結果の空間情報を用いて，空間的確率 Pr(O), Pr(B)

の更新を行う．物体と背景の境界付近では，次のセグメンテーション時にはどちらになる か不明なため，同程度に物体と背景が生起すると考えられる．一方，境界から離れてい る位置では，次のセグメンテーション時に物体と背景が入れ変わる可能性は低い．この ような確率分布を作成するために，物体領域と背景領域に対して距離変換を行う．このと き，境界からの距離 d を 0.5 から 1 に正規化する．正規化した物体の距離 dobjと背景の距 離 dbkg を用いて空間的確率を以下の式で更新する． Pr(O) =  dobj if dobj ≥ dbkg 1− dbkg if dobj < dbkg (3.9) Pr(B) = 1 − Pr(O) (3.10)

3.4

繰り返し処理とその効果

GMM により得られた色分布確率 Pr(Ip|O), Pr(Ip|B) と距離変換により得られた空間的

確率 Pr(O), Pr(B) を用いて，式 (3.3) により物体の事後確率 Pr(O|Ip)，式 (3.4) により背 景の事後確率 Pr(B|Ip) を計算する． 物体の事後確率 Pr(O|Ip) から式 (3.3) により{p, T } 間の t-link のコストを，背景の事後 確率 Pr(B|Ip) から式 (3.4) により{p, S} 間の t-link のコストをそれぞれ計算し，これを 3.2 に示したように次の平滑化画像を用いた Graph Cuts 処理に利用する．これにより，１つ 前のセグメンテーション結果を次のグラフカットへ伝播させることができる．

図 3.5 に，繰り返し処理によるセグメンテーション結果を示す．図 3.5(b) は，従来法で ある Interactive Graph Cuts[9] によりセグメンテーションをした例である．図 3.5(c) は， n-link の大きさの分布を表したものである．σ = 0 は入力画像に対しての n-link の分布で あり，背景に強い細かなエッジが存在することがわかる．そのため，背景領域が物体と誤 検出されている．提案手法では，図 3.5(c) より，平滑化処理により n-link を変化させるこ とで，大域的な情報から局所的な情報へ変化しているのがわかる．一方，t-link では，空

間的確率 Pr(O), Pr(B) と色分布確率 Pr(Ip|O), Pr(Ip|B) により計算される．空間的確率に

より，1 つ前のセグメンテーション結果から次のセグメンテーションでどの位置を注目を するかを表現している．図 3.5(d) より，次のセグメンテーションの注目領域が変化してい るのがわかる．また，図 3.5(e) は，物体と背景の色分布確率を表現している．この空間的 確率 Pr(O), Pr(B) と色分布確率 Pr(Ip|O), Pr(Ip|B) を t-link に用いることで，1 つ前のセ

グメンテーション結果を次のセグメンテーションへ反映させる．これを平滑化度合いを大 きな値から小さくしながら繰り返し処理することにより，大域的なセグメンテーションか ら段階的に局所的なセグメンテーションを実現することが可能となる．

3.5

セグメンテーション評価実験

3.5.1

実験概要

本手法の有効性を示すために評価実験を行う．実験に使用する評価用画像データベースに は，GrabCut1 にて提供されている 50 枚の人・風景・動物等の画像を用いる．これらの画像に

対し，同じ seed を与えて提案手法と従来法である Interactive Graph Cuts [9] と GrabCut[2] との比較を行う．評価方法として，物体領域のマスクデータを正解データとし，それに 対しての誤検出率により評価する．物体の正解ラベルをO = {O₁, O₂, . . . , Op, . . . , O|P |},

背景の正解ラベルをB = {B₁, B₂, . . . , Bp, . . . , B|P |}，得られたセグメンテーション結果

をL = {L1, L2, . . . , Lp, . . . , L_{|P |}} とする．このとき，物体領域を背景と誤検出したものを

over segmentation，背景領域を物体と誤検出したものを under segmentation として各誤 検出率を以下の式で求める． over seg. =  p∈Pδ(Lp − Bp) |P | (3.11) under seg. =  p∈Pδ(Lp − Op) |P | (3.12)

Graph Cuts のパラメータ λ は，Interactive Graph Cuts では λ = 0.005 として seed が与 えられた位置のみ t-link を計算する．Grabcut と提案手法では，λ = 0.02 として実験を

1_{http://research.microsoft.com/vision/cambridge/}

i3l/segmentation/GrabCut.htm

図 3.5: 各平滑化画像に対する n-link と t-link の変化とセグメンテーション結果例 行う．

3.5.2

実験結果

表 3.1 に，評価用データベース 50 枚の画像に対するセグメンテーション結果を示す．表 3.1 より，提案手法は従来法に比べ 2.14% セグメンテーションの精度を向上させることが できた．また実験に用いた画像の中で，従来法で誤検出率が 2% 以下のものを成功画像， 2% 以上を失敗画像とした際の実験結果を表 3.2 に示す．表 3.2 より，提案手法は従来法で 成功する画像に対しては同程度のセグメンテーション精度である．一方，失敗画像に対し ては 4.79% セグメンテーション精度を向上させることができている．これは，提案手法 では，平滑化を行うことにより周波数成分が低い大域的なセグメンテーションから始める ことにより大まかなセグメンテーションをする．また，距離変換を考慮した t-link を用い ることにより，次のセグメンテーションでの注目位置を考慮するため，大域的な情報を保

表 3.1: 誤検出率 [%] 従来法 Interactive GrabCut[2] 提案手法 Graph Cuts[9] over seg. 1.86 3.33 1.12 under seg. 1.89 1.59 0.49 total 3.75 4.93 1.61 表 3.2: 誤検出率 [%] 従来法 Interactive GrabCut[2] 提案手法 Graph Cuts[9] 成功画像 over seg. 0.29 3.54 0.81 (26 枚) under seg. 0.43 1.03 0.22 total 0.72 4.58 1.03 失敗画像 over seg. 3.56 3.10 1.45 (24 枚) under seg. 3.47 2.21 0.79 total 7.04 5.31 2.25 持することができる．そして，徐々に平滑化度合いを低くしていくことで，大域的な情報 を保持しつつ，より細かいセグメンテーションを行うことが可能となる．そのため，提案 手法は従来法で失敗した画像に対しても高精度にセグメンテーションを行うことができた と考えられる．図 3.6 に各手法の画像セグメンテーション例とエラー率 (err) を示す．こ のエラー率は式 (3.11) の over segmentation と式 (3.12) の under segmentation を足した値 である．

3.5.3

考察

■ λ の変化による影響

式 (2.1) の t-link と n-link の強さを制御するパラメータ λ は，Interactive Graph Cuts で は経験的に決定している．Interactive Graph Cuts [9] と提案手法にて λ を 100 から 0 まで変 化させた結果を図 3.7 に示す．図 3.7 の λ = 0.005 のように n-link が強い場合，Interactive Graph Cuts と提案手法ともに大まかな物体領域の抽出はできているが，細部に誤検出が ある．一方，λ の値を大きくして t-link の影響を強くした場合，Interactive Graph Cuts で

図 3.6: セグメンテーション例と誤検出率 は誤検出領域が多いが，提案手法では安定して物体領域を抽出できていることがわかる． これは，従来法では t-link に色情報のみが使われているため，物体領域の色に似ている色 の背景領域が誤検出される．提案手法では繰り返し処理における 1 つ前の Graph Cuts の 結果から，大まかな物体領域と背景領域の形を捉えた t-link が得られるため，λ を大きく した場合でも突発的な誤検出を抑制することができる．このことから，提案手法は λ を変 化させても，安定したセグメンテーション結果を得ることができる． ■ 処理時間について 従来法と提案手法の処理時間の計測を行う．処理時間計測には画像サイズを 150x113, 300x225, 600x450 の 3 種類を用いる．使用した PC は Intel(R) Xeon 2.66GHz × 8，メモ リ 4.0GB である．表 3.3 に各手法での処理時間と繰り返し回数を示す．表 3.3 より，提案 手法は繰り返し処理が入るため，処理時間が大幅に増加する．解決策として，繰り返し回 数の軽減や Lazy Snapping [1] のようにスーパーピクセルからグラフを作成することによ るグラフカットの高速化が考えられる．

図 3.7: λ の変化によるセグメンテーション結果の違い 表 3.3: 各手法の処理時間 [s]（繰り返し回数） Interactive GrabCut[2] 提案手法 Graph Cuts[9] 150x113 0.38 2.91 (4 回) 9.81 (8 回) 300x225 0.94 8.15 (3 回) 37.59 (10 回) 600x450 3.57 98.04 (12 回) 154.70 (12 回)

3.6

まとめ

平滑化の繰り返し処理による，大域的なセグメンテーションから段階的に局所的なセグ メンテーションを行う手法を提案した．従来法では，複雑なエッジを含む画像に対しても 安定してセグメンテーションを行えることを確認した．評価実験より，提案手法は従来法 と比較し 2.14% セグメンテーション精度を向上することができた．従来法で成功した画 像は同程度のセグメンテーション精度で，失敗した画像に対しては 4.79% セグメンテー ション精度を改善することができた．また，グラフカットのパラメータ λ に対して，安定 したセグメンテーションが可能であることを実験により確認した． 20

第

4

章

動画像に対するグラフカットによるセグメ

ンテーション

4.1

従来法

Interactive Graph Cuts [9] での動画像セグメンテーションでは，各ピクセルをノード として，グリッド上に n-link を作成する．t-link は，画像と同様にすべてのピクセルに対 して作成する．図 4.1 に動画像に対応したグラフを示す．このように動画像に対してグラ フを作成した場合，各ピクセルをノードとするため，大量のノードが必要となる．そのた め，長時間のシーケンスには対応することができない，計算コストの増加などの問題が生 じる．また，時間軸方向に対しての平滑化をどのようにするかが問題となる．

4.2

スーパーピクセルを用いた繰り返し処理によるグラフカ

ット

従来法の問題点を解決するため，本手法では，異なるバンド幅で作成されたスーパーピ クセルを使用し，バンド幅が大きなものから Graph Cuts を繰り返し行うことにより高精 度なセグメンテーション手法を実現する．

4.2.1

スーパーピクセルの作成

空間と時間軸方向を考慮した Mean Shift Segmentation [4] を用いて，スーパーピクセ

ルを作成する．空間，時間，色情報を持った入力ベクトルを xi ={xsi, xti, xri}，フィルタ 結果を zi，各ピクセルのラベルを Liとする．また，{yj}j=1,2,... を以下のように定義する． yj+1 = n i=1xig _x−x i h  2 n i=1g _x−x i h  2 (4.1) g(x) = C h2_shth p r k   x s hs  2 k   x t ht  2 k   x r hr  2 (4.2)

図 4.1: 従来法によるグラフカットによる動画像セグメンテーション

ここで，hs, ht, hrはそれぞれ空間，時間，色のバンド幅で，C は正規化定数である．k(x)

はカーネル関数である．Mean Shift Segmentation は以下の手順で行われる．

1. Ｍ ean Shift により，zi = yi,cとして特徴空間の情報を格納

2. 特徴空間において，zi をクラスタ {Cp}p=1,...,m にクラスタリング

3. Li ={p|zi ∈ Cp}

4. 空間領域において，M pixel 以下の領域を削除

この Mean Shift Segmentation のバンド幅 hs を大きいものから処理することにより，

大域的なセグメンテーションから段階的に局所的なセグメンテーションを行う．図 4.3 に， 各バンド幅におけるスーパーピクセルの例を示す．

図 4.2: 手法の流れ 図 4.3: スーパーピクセルの作成例

4.3

評価実験

本手法の有効性を示すために評価実験を行う．動画像に対して，初期フレームのみに seed の入力を行う．10 フレーム目のセグメンテーション結果により評価する．比較対象 として，スーパーピクセルをノードとしてグラフを作成する手法 (従来法)，Mean Shift のバンド幅を変化させながら繰り返しグラフカットを行う手法 (提案手法) の比較を行う． 表 4.1 に誤検出，図 4.4 にセグメンテーション結果を示す． 表 4.1 より，従来法と比較し 表 4.1: 誤検出率 [%] 従来法 提案手法 over segmentation 1.90 1.18 under segmentation 5.47 1.96 total 7.36 3.13 たとき，提案手法はセグメンテーション精度を約 4.23% 向上させることができている．し かし，画像セグメンテーションと比較し誤検出率が高い．この原因として，Mean Shift Segmentation の精度が低いためだと考えられる．これらの問題は今後の課題としたい．

図 4.4: セグメンテーション結果

4.4

まとめ

動画像のセグメンテーションでは，各ピクセルをノードとしてグラフを作成した場合， ノード数が増加するため長時間のシーケンスに対応できない，計算コストが増加するな どの問題がある．そこで，本手法ではバンド幅を変化させたスーパーピクセルを繰り返し 処理することで，大域的なセグメンテーションから局所的なセグメンテーションを行う． 評価実験により，スーパーピクセルを用いたのみの場合と比較し，バンド幅を変化させて 繰り返し処理をすることにより，約 4.23% セグメンテーション精度を向上させることが できた．しかし，画像セグメンテーションと比較した場合，Mean Shift Segmentation の 精度が低いため，誤検出率が高い．これらの問題は今後の課題としたい．

第

5

章

領域分割に基づく

SIFT

_{特徴を用いた物体}

識別

平滑化処理の繰り返しによるグラフカットにより，高精度なセグメンテーション結果を 得ることができた．このセグメンテーション結果を用いて，物体識別を行う．

本手法では，SIFT(Scale Invariant Feature Transform) 特徴量に基づくベクトル量子化 ヒストグラムを領域分割した各領域ごとに抽出し，それらの関係をグラフを用いて表現す る．領域分割には，混合正規分布モデルを用いて検出領域を各構造の主領域ごとに分割す る手法を用いる．

5.1

Bag of Keypoints

近年において一般物体認識で注目されている手法として，Bag of Keypoints [3] がある． Bag of Keypoints では画像を局所特徴量の集合とみなすことで，各特徴量の位置情報を使 用せずに識別を行う．そのため，背景が異なる画像に対しても識別することが可能となる．

5.1.1

歴史的背景

Bag of Keypoints の考え方は，文書分類などに用いられる Bag of Word に基づいてい る．Bag of Word は文書分類などの分野では古典的な手法として知られている．この手法 では，文書を単語の集合とみなし，単語の頻度によりその文章の特徴を表現する．これら の特徴を学習させることにより，テキストの分類を行う．Bag of Keypoints では 文書の 単語を局所特徴量 (keypoint, visual work, visual term) とすることで，文書分類手法を画 像に応用した手法である．

5.1.2

Bag of Keypoints

による物体識別

図 5.1 に，Bag of Keypoints の流れを示す．Bag of Keypoints の手法としてさまざまな 手法が提案されている．

図 5.1: Bag of Keypoints の流れ

5.1.3

特徴量抽出の流れ

Bag of Keypoints の特徴量抽出の流れを以下に示す． • 局所特徴量の抽出 • 局所特徴量のベクトル量子化 • クラスタの頻度を計算 はじめに，画像中から局所特徴量として SIFT 特徴量の抽出を行う．次に抽出した SIFT 特徴量をベクトル量子化する．このとき，ベクトル量子化に用いるコードブックは学習 データから作成する．最後に，ベクトル量子化された SIFT 特徴量から各クラスタの頻度 （ベクトル量子化ヒストグラム）を作成する． 26

■ 局所特徴量の抽出

局所特徴量の抽出には SIFT を用いる．このとき，SIFT 特徴量の記述範囲を決定する 必要がある．この SIFT 特徴量の記述範囲の決定法は，主に 2 つの種類に分けられる．

• Interest point detector

画像中から特徴点とスケールを検出し，その範囲から SIFT 特徴量を記述する．Quel-has ら [27] は，SIFT [28] と同様に DoG 極値を利用して特徴点の検出を行っている． Csurka ら [3] は，Affine Invariant keypoint [29] を利用し，得られた領域をアフィン 変換により正規化して SIFT 特徴量の抽出を行っている（図 5.2）.

図 5.2: Affine Invariant keypoint を用いた SIFT 特徴量の抽出：(a)Affine Invariant keypoint (b) 正規化された領域 (c) 8 方向の輝度勾配強度  (文献 [3] より) • Regular grid この方法では，画像を等間隔に分割をし，スケールをランダムに決定して SIFT 特 徴量を記述している．Fei-Fei ら [5] はグリッドに分割して SIFT 特徴量を記述する ことにより風景画像など 13 クラスに対しての画像分類をしている．自然風景シー ンではエッジやコーナーといった特徴点の抽出が困難であるため，グリッドに分割 することで，DoG 極値を用いるよりも高精度に分類できていることが述べられて いる． 表 5.1: 各手法での識別結果 [%] (文献 [5] より)

Descriptor Grid Random DoG

11x11 pixel 64.0 47.5 N/A

128-dim SIFT 65.2 60.7 52.5

5.1.4

識別器

Bag of Keypoints では，ベクトル量子化ヒストグラムを識別器の入力とする．このと き用いられる識別器として，

• SVM

• Naive Bayes • pLSA • LDA

などが使われている．特に，pLSA と LDA は文書分類である Bag-of-Word で用いられて いる手法である．以下に，各手法の概要を述べる． ■ Naive Bayes Naive Bayes では，各特徴量間の相関はないと仮定し，各特徴量ごとにカテゴリである 確率を計算することにより全体のカテゴリの確率を計算する手法である．画像から得られ る局所特徴量をw = {w₁, w₂, . . . , wn}, カテゴリを c とするとき，Naive Bayes では以下 の式によりカテゴリ c∗を決定する． c∗ = arg max c p(c|w) ∝ p(c)p(w|c) = p(c)  n p(wn|c) (5.1) ■ pLSA

pLSA (Probabilistic Latent Semantic Analysis) [30] とは，文書と単語など，離散 2 変

数の計数データの生成モデルである．文書を d ∈ D = {d₁, . . . , dN}, 語を w ∈ W = {w1, . . . , wM}, 潜在変数の話題を z ∈ Z = {z1, . . . , zK} としたとき，文書と単語の生成モ デルを以下の式で定義する． p(d, w) = p(d)
z∈Z p(w|z)p(z|d) (5.2) これは，文書と語について対称に定義することができる． p(d, w) =
z∈Z p(z)p(d|z)p(z|w) (5.3) LDA はこの pLSA を改良した生成モデルである．

Sivic ら [31] は，この pLSA にスケールと位置情報を加えて識別精度を向上させる Trans-lation and Scale invariant pLSA (TSI-pLSA) を提案している．

図 5.3: 検出領域に対しての混合正規分布の当てはめ例

5.2

構造に基づく特徴量抽出

本章では，移動体識別における特徴量の抽出法について述べる．グラフカットにより検 出された物体領域に対して混合正規分布を当てはめ，検出領域を分割する．分割後の各 領域に対して SIFT 特徴量を抽出し，ベクトル量子化ヒストグラムを用いて特徴を表現す る．以下に，各処理の詳細を示す．

5.2.1

混合正規分布を用いた領域分割

物体の内部パターンを記述するために，検出領域に対して混合正規分布を当てはめる [32, 33] 物体領域の座標 (u, v) と輝度 I をxi = {ui, vi, Ii}T，混合正規分布パラメータを Φ = {αj,φj = (µj, Σj)}cj=1としたとき，x に対して，式 (5.4) の確定的アニーリング

EM(DAEM:Deterministic Annealing EM) アルゴリズム [34] を用いて混合正規分布パラ

メータ ΦM Lを推定する． ΦM L = arg max Φ c
j=1 (αj · pj(x|µj, Σj))β p(x|µ_j, Σj) = 1  (2π)3|Σj| · exp −1 2(x − µj) T_Σ−1 j (x − µj)  (5.4) pj(x|µj, Σj) は，平均µj，共分散行列 Σjであり，φj ={µj, Σj} の各正規分布である．β は DAEM アルゴリズムの温度パラメータである．この β を変化させることにより，EM アルゴリズムの問題点であった初期値への依存性を軽減することができる．また，αjは 混合比で，αj > 0， c j=1αj = 1 を満たす．図 5.3 に，4 つの正規分布を当てはめ後，ΦM L で表される 3 次元の混合正規分布を 2 次元画像平面 (u, v) 上に投影した例を示す．各正規 分布は，物体の内部パターンとなる主領域（クラスタ）を表しており，これを物体構造の 記述に利用する．

図 5.4: GMM によるセグメンテーション例 推定されたパラメータ ΦM Lから，各ピクセルx がどの正規分布 φiに属しているかを 次式により求め，領域分割を行う． Ci = arg max i pi(x|φi) (5.5) 図 5.4(c) は，異なるクラスに対するセグメンテーション結果である．一般に領域分割手法 として用いられている Mean-Shift によるクラスタリング手法 [4] は，図 5.5 に示すように， 同一色で繋がる自動車の側面と背面を同じクラスタに，側面のガラスとボディは別のクラ スタに分けられる．また，提案手法では混合正規分布を用いるため，適した分布数を設定 することで，微細なテクスチャの変化に影響されず，側面のガラスや車体を同一クラスタ に分けられるため，物体構造に基づいた領域分割が可能である．これは，xi ={ui, vi, Ii}T の 3 次元空間でクラスタリングを行うため，側面と背面といった構造ごとへの分割が可能 になると考えられる． 30

図 5.5: Mean-Shift セグメンテーションとの違い

5.2.2

特徴量抽出

領域分割後の各ピクセルに対して，SIFT descriptor [28] に基づく特徴量を抽出する．以 下に，各処理の流れを示す． ■ SIFT Descriptor SIFT descriptor は，あるピクセルの代表輝度勾配方向を決定し，その方向を基準とし た輝度勾配ヒストグラムを作成し，多次元ベクトルで特徴を記述する．はじめに，注目画 素の代表輝度勾配方向を決定する．画像 L(x, y) の輝度勾配方向 θ(x, y) と大きさ m(x, y) は以下の式により求められる． m(x, y) =  fx(x, y)2+ fy(x, y)2 (5.6) θ(x, y) = tan−1  fy(x, y) fx(x, y)  (5.7) このとき， fx(x, y) = L(x + 1, y)− L(x − 1, y) (5.8) fy(x, y) = L(x, y + 1)− L(x, y − 1) (5.9) である．輝度勾配の大きさ m を方向 θ を用いて，各方向のヒストグラムを次式より作成 する． w(x, y) = G(x, y, σ)· m(x, y) (5.10) hθ =
x
y w(x, y)· δ[θ, θ(x, y)] (5.11) G(x, y, σ) はガウス分布である．また，θ は全方向を 36 分割したものを使用する．このヒ ストグラムの最大値の方向をその位置での代表輝度勾配方向とする（図 5.6）．

図 5.6: 重み付き方向ヒストグラム 図 5.7: SIFT 特徴量の記述 この代表輝度勾配方向を基準とした周囲の輝度勾配ヒストグラムを作成する．正規分布 から得られる領域を 4x4 の領域に分割し，それぞれの位置で 8 方向の輝度勾配ヒストグラ ムを作成する．4x4 の領域にそれぞれ 8 方向ヒストグラムを作成するため，128 次元ベク トルの特徴量を持つことになる（図 5.7）．この 128 次元の SIFT 特徴量を各ピクセルごと に抽出する．

5.2.3

ベクトル量子化ヒストグラム

各領域ごとにベクトル量子化ヒストグラムを作成する．はじめに，ベクトル量子化に用 いるコードブックを作成する．コードブックは，参照データから抽出したすべての SIFT 特徴量を用いる．それらの SIFT 特徴量を LBG アルゴリズムを用いてクラスタリングを し，コードブックを作成する．次に，各領域を構成するピクセルの SIFT 特徴量をコード ブックに従い符号化する．各符号を各領域ごとにヒストグラムを作成し，その面積で正規 化を行う．この正規化したベクトル量子化ヒストグラムを図 5.8 に示すように分割した領 域の特徴量として利用する． 32

図 5.8: 特徴量抽出

5.3

グラフマッチングによる物体識別

ベクトル量子化ヒストグラムをその領域の特徴量とし，それらをグラフによって記述 し，グラフマッチングにより物体識別を行う．このとき，物体領域全体から得られる大域 的特徴量と，物体領域を混合正規分布によりセグメンテーションし各領域から得られる局 所的特徴量のそれぞれのマッチングコストを計算する．この大域的特徴量と局所的特徴量 を統合させ，k-NN 法を用いて識別を行う．提案する物体識別の流れを図 5.9 に示す． 図 5.9: 物体識別の流れ

5.3.1

グラフによる特徴量の記述

各領域毎に得られたベクトル量子化ヒストグラムをグラフにより表現する．グラフは頂 点（ノード）と，頂点を結ぶ辺（エッジ）によって構成される．分割された各領域をノー ドとし，ベクトル量子化ヒストグラムをノード特徴量として記述する．エッジには，各領 域を構成する正規分布の中心のユークリッド距離をエッジ特徴量として記述し，各ノード の位置関係を表現する．図 5.10 にグラフを記述した例を示す．

図 5.10: グラフによる記述

5.3.2

グラフマッチング

作成したグラフ間のコストをグラフマッチングにより計算する．ノードの集合をN = {n1, . . . ,n4}T，エッジの集合E = {e1, . . . ,e6}Tとする．参照グラフT = {N1, . . . ,N4,e1, . . . ,e6}T}T と，入力グラフX 間のマッチングコストを以下の式より求める． cost(T , X) = 4
i=1 ||nt i − n x i|| + 6
j=1 ||et j − e x j|| (5.12) このとき，T と X のノードの対応は未知であるため，T と X のノードの全ての組み合 わせについてコストを計算し，最小値をT と X のマッチングコストとする． Cost(T , X) = min i {cost(T , Xi)} (5.13) 分割した各領域から得られる特徴量のコスト Costlと領域全体から求める大域的特徴量の コスト Costgを統合率 α を用いてマッチングコストを計算する．

Cost = α· Costl+ (1− α) · Costg (5.14)

(0≤ α ≤ 1)

この入力パターンと参照パターンとのコストから，kNN 法を用いて識別クラスを判定する．

5.4

物体識別評価実験

5.4.1

屋外環境データにおける評価実験

■ 実験データ 構造情報に基づく特徴量の評価実験を行う．識別クラスとして，人 (SH)，人複数 (HG)， 二輪車 (BK)，自動車 (VH) の 4 クラスを対象とする．評価用データとして，3 年間分の映 像データから 30 分からなる映像シーンを選び，計 23 時間の映像データベースを作成し， その中から各識別クラス 200 パターン，計 800 パターンを用いた．作成するコードブッ クのサイズは 32，当てはめる正規分布数は 4 とする．図 5.11 に実験に使用した画像例を 示す． 図 5.11: 実験データ例 ■ 実験結果 統合率 α を変化させたときの識別結果を表 5.2 に示す． 大域的特徴量と構造に基づく 特徴量を統合することで，3.2% 識別率を向上させることができた．表 5.3 に，α = 0.1 で の識別結果をコンフュージョンマトリクスに示す．構造情報を加えることで大域情報のみ (α = 0) を使用した際に人を二輪車と誤識別したパターンを減少させることができた．図 5.12 に人と二輪車の領域全体と各領域ごとに得られたベクトル量子化ヒストグラムを示 す．人と二輪車の大域的特徴量は非常に似ていることがわかる．従って，大域的に捉えた 特徴の記述では，誤識別が起こる可能性が高い．一方，構造に基づく特徴量は，図 5.12 の (a)(b) と (e)(f) のように上半身の特徴量は似ているが，(c)(d) と (g)(h) のように下半身部 分の特徴量が異なっていることがわかる．そのため，部分的に物体の見え方が似ている人 と二輪車の誤識別を抑制することができたと考えられる．図 5.13 に，構造に基づく特徴 量を加えたことで正解した例を示す．

表 5.2: 識別結果 [%] α   0.0 0.1 0.3 0.5 0.7 0.9 1.0 SH 75.6 80.8 77.5 74.7 71.4 70.9 71.8 HG 80.4 87.1 85.7 85.7 85.7 85.2 85.2 Class BK 86.3 87.7 86.3 87.2 86.3 85.3 85.8 VH 97.3 96.8 95.9 95.9 96.4 96.4 96.4 合計 85.0 88.2 86.4 85.9 85.0 84.5 84.9 表 5.3: 識別結果 (α = 0.1) out SH HG BK VH correct rate[%] SH 172 24 16 1 172 80.8 HG 9 182 16 2 182 87.1 in BK 15 10 185 1 185 87.7 VH 7 0 0 212 212 96.8 合計 751 88.2

5.4.2

一般物体認識における評価実験

■ 実験データ Caltech database 1 を用いた識別実験を行う．図 5.14 に，実験に用いるデータ例を示 す．この実験では，以下に示す 3 つの手法の比較を行う．

bok1 [3] Bag of keypoints． 対象画像中から SIFT 特徴量を抽出し，ベクトル量子化ヒ

ストグラムによりその物体の特徴を記述する手法．背景の変化に頑健で，物体の構 造情報を必要としない． bok2 [35] 対象領域をグリッドに分割し，それぞれの領域からベクトル量子化ヒストグ ラムを作成． proposed method GMM を用いて領域分割し，それぞれの領域からベクトル量子化ヒ ストグラムを作成． 1_{http://www.vision.caltech.edu/Image Datasets/Caltech256/} 36

■ 実験結果 図 5.15 に，各手法での実験結果を示す．図 5.15 より，提案手法は，bok1 よりも約 17.6% 精度を向上させることができた．しかし，bok2 と比較した場合では，提案手法は約 5.6% 識別率が低い．一方，入力画像を 45 度回転させて入力した場合，提案手法，bok1 では 識別率に変化はないが，bok2 では回転した画像をグリッドに分割するため識別率が低下 する．図 5.16 に，回転画像に対する，GMM を用いた領域分割結果を示す．図 5.16 より， GMM を用いた領域分割は，回転した画像でも領域分割結果が変化しない．そのため，本 手法は，回転に対して不変な特徴量を抽出することが可能となる．しかし，bok2 では，画 像が回転することにより，構造情報が変化する．そのため，bok2 では正しく認識するこ とができない．

5.5

まとめ

画像セグメンテーションの応用例として，領域分割に基づく物体識別手法を提案した． 本手法は，得られた物体領域を混合正規分布を用いて領域分割し，各領域から SIFT 特徴 量に基づくベクトル量子化ヒストグラムを抽出する．このベクトル量子化ヒストグラムを 各領域の特徴量とし，それらをグラフにより表現する．これらをグラフマッチングにより マッチングコストを計算する．屋外環境データを用いた評価実験より，領域全体から得ら れる大域的な特徴量と，各領域から得られる局所的な特徴量を用いることにより，大域的 な特徴量のみの場合より 3.2% 識別性能を向上させることができた．特に，人と二輪車の ように局所的な情報のみが異なる場合，大域的な特徴量ではそれらの情報が埋もれてしま うが，局所的な情報を入れることにより識別率を向上させることができる．また，一般物 体認識において，従来法である Bag of keypoints と比較し，約 17.6% 識別性能を向上さ せることができた．

図 5.12: 人と二輪車の特徴量の違い

図 5.13: 正解データ例

図 5.15: 実験結果

図 5.16: 回転画像に対する領域分割結果

第

6

章

むすび

本論文では，画像セグメンテーション手法として，平滑化の繰り返し処理によるグラフ カットを用いた画像セグメンテーション手法について述べ，セグメンテーション結果の応 用例として，領域分割に基づく物体識別手法について述べた．各章ごとのまとめは以下の 通りである． 3 章では，平滑化の繰り返し処理による，大域的なセグメンテーションから段階的に局 所的なセグメンテーションを行う手法を提案した．提案手法では，複雑なエッジを含む 画像に対しても安定してセグメンテーションを行えることを確認した．評価実験より，約 4.79% セグメンテーション精度を向上することができた．また，グラフカットのパラメー タ λ に対して，安定したセグメンテーションが可能であることを実験により確認した．

4 章では，動画像に対して，スーパーピクセルを Mean Shift Segmentation により作成 し，そのときのバンド幅を変化させることで，大域的なセグメンテーションから段階的に 局所的なセグメンテーションを行う手法を提案した．評価実験により，スーパーピクセル を用いたのみの場合と比較し，バンド幅を変化させて繰り返し処理をすることにより，約 4.23% セグメンテーション精度を向上させることができた． 5 章では，画像セグメンテーションの応用例として，領域分割に基づく物体識別手法を 提案した．屋外環境データを用いた評価実験より，領域全体から得られる大域的な特徴量 と，各領域から得られる局所的な特徴量を用いることにより，大域的な特徴量のみの場合 より 3.2% 識別性能を向上させることができた．特に，人と二輪車のように局所的な情報 のみが異なる場合，大域的な特徴量ではそれらの情報が埋もれてしまうが，局所的な情報 を入れることに識別率を向上させることができる．また，一般物体認識において，従来法 である Bag of keypoints より，約 17.6% 識別性能を向上させることができた． 今後の課題として，動画像セグメンテーションでのスーパーピクセル作成時の Mean Shift Segmentation の精度向上が挙げられる．また，画像セグメンテーション時の途中経 過から物体の構造情報を記述し，そこから物体認識を行う手法の検討を行う予定である．

謝 辞

本研究を行うにあたり，指導教授として終始懇切なご指導を頂きました中部大学 藤吉 弘亘准教授に謹んで深謝します． また，終始懇切なご指導を頂きました同学 岩堀祐之教授，平田豊教授に謹んで深謝し ます． また，本研究を進めるにあたり，カーネギーメロン大学 金出武雄教授と株式会社 日立 製作所 数井誠人氏に心から厚く御礼申し上げます． 最後に，本研究で用いたプログラムの開発や研究の相談など協力して頂いた藤吉研究室 の皆様に感謝致します．