F - 中部大学

中部大学工学部情報工学科
卒業論文
ワイルドカードを用いた Random Ferns による
ノイズに頑健な特徴表現
竹ノ内 信寛
2012 年 3 月
指導教授 藤吉弘亘
A Graduation Thesis of College of Engineering, Chubu University
A Noise-Robust Feature Representation by Random Ferns Using
Wild-Card
Nobuhiro Takenouchi
はじめに
画像中から特定の物体を認識する技術 (特定物体認識) は，Intelligent Transport Sys-
tem(ITS:高度道路交通システム) で代表的な標識認識や，Augmented Reality(AR:拡張現
実) を用いたアプリケーションなど多岐に渡る分野で実用化されている．近年の特定物体
認識は，D.Lowe が提案した画像の回転，スケール変化，照明変化に頑健な SIFT(Scale
Invariant Feature Transform)[5] によるキーポイントマッチング手法が多く利用されてい
る．
SIFT は画像変化に対する頑健性は優れているものの，計算コストが非常に高く，リア
ルタイム処理が必要なアプリケーションには不向きである．この問題に対し，T.Bay らは，
SIFT をベースとしたキーポイントマッチングを高速化した SURF(Speeded Up Robust
Features)[7] を提案している．SURF は，Hessian 行列を用いてキーポイントを高速に算出
するために，ガウシアンの 2 次微分を box filters で近似している．box filters は，Integral
Image を使用することで高速な処理を可能としている．これにより，SURF は SIFT と同
程度の精度で高速化を実現している．
SIFT や SURF のようなアプローチとは別に，Randomized Trees(RTs) を利用した識別
器によるキーポイントマッチング手法 [2] がある．RTs によるキーポイントマッチングは，
あらかじめテンプレート画像からアフィン変化に頑健なキーポイントを検出し，決定木を
利用してテンプレート画像の学習を行う．RTs を利用することで，マッチングの際に入力
画像の特徴量を記述する必要がなく，決定木の分岐のみを観測することで高速なマッチン
グが実現できる．さらにアフィン変化に頑健なキーポイントを用いているため，SIFT で
は認識が困難なアフィン変化の強い画像に対しても頑健にマッチングが可能である．
2010 年には RTs を改良した Random Ferns を用いたキーポイントマッチング手法 [1] が
提案されている．Random Ferns は，決定木の分岐関数を同じ階層で統一することで，末
端ノードまでの分岐を “0” と “1” のバイナリで表現している．これにより，高精度かつ高
速なキーポイント分類を実現している．
ii
RTs や Random Ferns のように，決定木を用いたキーポイントマッチング手法は，画
像中の局所領域内の輝度を用いて特徴を表現している．そのため，画像ノイズや遮蔽によ
り輝度値が変化すると認識が困難となる場合がある．例えば，車載カメラから取得した映
像を処理するようなシステムの場合，雨や太陽光の影響で画像中に画像ノイズが発生す
る．特定物体認識を用いた AR のアプリケーションにおいても，対象物体のテクスチャの
欠損等の画像ノイズが発生してしまう．そこで，本研究ではこれらの画像ノイズに対して
頑健にキーポイント分類を行うことを実現するため，Random Ferns から得られるバイナ
リコードに対して “0” と “1” を許容するワイルドカードを導入する．これにより，キーポ
イントの分類時に画像ノイズの影響で入力画像の輝度値が変化してしまった場合におい
て，誤ったバイナリをワイルドカードを用いてマスキングすることで，ノイズに対して頑
健なキーポイント分類を実現する．
iii
目次
第 1 章 画像局所特徴量による対応点マッチング
1.1
1.2
1.3
SIFT：Scale Invariant Feature Transform . . . . . . . . . . . . . . . . . . .
1
1.1.1
スケールとキーポイント検出 . . . . . . . . . . . . . . . . . . . . .
2
1.1.2
キーポイントのローカライズ . . . . . . . . . . . . . . . . . . . . .
8
1.1.3
オリエンテーションの算出 . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.4
特徴量の記述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
SURF: Speeded Up Robust Features . . . . . . . . . . . . . . . . . . . . . 15
1.2.1
検出段階 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.2
記述段階 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Randomized Trees を用いたキーポイントの分類 . . . . . . . . . . . . . . . 23
1.3.1
キーポイント検出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3.2
決定木の構築 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3.3
キーポイントの分類 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
第 2 章 ワイルドカードを用いた Random Ferns によるキーポイントの分類
2.1
1
29
Random Ferns を用いたキーポイントの分類 . . . . . . . . . . . . . . . . . 29
2.1.1
決定木の構築 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2
キーポイントの分類 . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2
提案手法の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3
分岐関数の選択 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4
提案手法によるキーポイントの分類 . . . . . . . . . . . . . . . . . . . . . . 36
2.4.1
ワイルドカードにより許容される複数の頻度の統合 . . . . . . . . . 36
2.4.2
マスキングするバイナリの選択 . . . . . . . . . . . . . . . . . . . . 37
iv
第 3 章 評価実験
38
3.1
データベース . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2
実験概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3
実験結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
おわりに
44
謝 辞
46
参考文献
47
v
図目次
1.1
LoG オペレータ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
DoG 処理の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
6
1.4
σ の連続性を保持した効率的な平滑化処理 . . . . . . . . . . . . . . . . . .
√
s = 2(k = 2) のときの DoG 処理例 . . . . . . . . . . . . . . . . . . . . . .
1.5
極値検出の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.6
スケールと DoG 出力の関係 . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.7
キーポイント候補点の絞り込み . . . . . . . . . . . . . . . . . . . . . . . .
9
1.8
ヒストグラム作成の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9
2 方向のオリエンテーションを持つキーポイント . . . . . . . . . . . . . . . 13
7
1.10 特徴量を記述する領域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.11 ブロックごとの特徴量記述 . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.12 手法の流れ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.13 曲面 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.14 box filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.15 領域の輝度和 ([12]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.16 スケールスペース . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.17 極値探索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.18 キーポイント検出結果 [7] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.19 特徴量記述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.20 キーポイントの検出アプローチ . . . . . . . . . . . . . . . . . . . . . . . . 24
1.21 LoG の近似 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.22 テンプレート画像のアフィン変換 . . . . . . . . . . . . . . . . . . . . . . . 25
1.23 画像変化に頑健なキーポイント . . . . . . . . . . . . . . . . . . . . . . . . 26
1.24 決定木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
vi
1.25 学習データ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.26 キーポイントの分類 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1
Random Ferns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2
オイラー角によるパッチ画像の回転 . . . . . . . . . . . . . . . . . . . . . . 31
2.3
学習サンプルの例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4
Random Ferns によるキーポイント分類 . . . . . . . . . . . . . . . . . . . . 32
2.5
“∗” を用いた Random Ferns によるキーポイント分類 . . . . . . . . . . . . 33
2.6
選択された分岐関数
2.7
“∗” による複数のバイナリコードの許容 . . . . . . . . . . . . . . . . . . . . 36
3.1
テンプレート画像 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2
キーポイントマッチングの正解率 [%](実験 1) . . . . . . . . . . . . . . . . . 40
3.3
キーポイントマッチングの正解率 [%](実験 2) . . . . . . . . . . . . . . . . . 41
3.4
キーポイントマッチング結果
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . . . . . . . . . . . . 43
vii
表目次
3.1
実験パラメータ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2
キーポイントマッチングの正解率 [%](実験 1) . . . . . . . . . . . . . . . . . 40
3.3
キーポイントマッチングの正解率 [%](実験 2) . . . . . . . . . . . . . . . . . 41
viii
第1章
画像局所特徴量による対応点マッ
チング
従来の特定物体認識は，画像の回転，スケール変化，照明変化などによる見えの変化に
対応するため，画像の局所領域から得られる特徴量を用いたキーポイントマッチングによ
る手法が多く提案されている．本章では，SIFT をはじめとする従来のキーポイントマッ
チング手法について述べる．
1.1
SIFT：Scale Invariant Feature Transform
SIFT はグレースケール画像から，キーポイントの検出と，特徴量の抽出を行う手法で
ある．画像間の対応点を求めるために必要な局所特徴量を抽出するには，対象となる画
像からキーポイントを検出する必要がある．Harris らは，1988 年にキーポイントとして
コーナーを検出する手法 (Harris Corner Detector)[8] を提案した．Lindeberg はスケール
スペースを用いることで画像の構造を解析し，blob の検出と自動スケール選択を行う手
法 [9] を提案した (1994 年)．また，Schmid らは Harris corner detector によって検出され
たキーポイントに対し，その点の画素値や微分値から算出した値を特徴量とし，画像の
回転に頑健な局所特徴量を記述した [10](1997 年)．これにより，回転変化が生じても画像
間のマッチングや認識を行うことが可能となった．しかし，Schmid らの手法に用いられ
ている Harris corner detector は，画像のスケール変化に敏感であるため拡大・縮小等の
異なるスケールの画像間ではマッチングが困難となる．Lowe は Schmid らの局所領域の
1
1.1. SIFT：Scale Invariant Feature Transform
特徴量記述という考えを拡張し，スケールスペースを用いることで，画像のスケール変
化や回転に不変な特徴量を記述する Scale-Invariant Feature Transform(SIFT) を提案した
[3][4][5](1999 年)．SIFT は，回転・スケール変化等に不変な特徴量を記述できるため，イ
メージモザイク等の画像のマッチングや物体認識に用いられている．SIFT の処理は，キー
ポイントの検出 (detection) と特徴量の記述 (description) の 2 段階からなり，各処理は以
下の流れとなる．

 1. スケールとキーポイント検出
detection
 2. キーポイントのローカライズ

 3. オリエンテーションの算出
description
 4. 特徴量の記述
1. スケールとキーポイント検出では，DoG 処理によりスケールとキーポイントを検出し，
2. キーポイントのローカライズでは，1. で検出されたキーポイントから特徴的でない点を
削除し，その後サブピクセル推定を行う．3. オリエンテーションの算出では，回転に不変
な特徴を得るためにキーポイントのオリエンテーションを求める．4. 特徴量の記述では，
3. で求めたオリエンテーションに基づいてキーポイントの特徴量を記述する．1.1.1 では，
スケールとキーポイント検出について述べる．1.1.2 では，キーポイントのローカライズ
について述べる．1.1.3 では，オリエンテーションの算出について述べる．1.1.4 では，特
徴量の記述について述べる．
1.1.1
スケールとキーポイント検出
第 1 段階のキーポイント検出では，DoG 処理を用いてスケールスペースにおける極値
探索をすることで，キーポイントの位置とスケールを決定する．
■ LoG によるスケール探索
キーポイントのスケール探索には，ガウス関数が有効であることが Koenderink[11] や
Lindeberg[9] により報告されている．Lindeberg は，ガウシアンカーネルを用いたスケール
スペースとして Scale-normalized Laplacian-of-Gaussian(以下 LoG) を提案している．LoG
は，画像にスケール σ を変化させながら式 (1.1) で表される LoG オペレータ (図 1.1) を適
用し，その極大位置をキーポイントのスケールと決定する．
2
1.1. SIFT：Scale Invariant Feature Transform
図 1.1: LoG オペレータ
( 2
)
x2 + y 2 − 2σ 2
x + y2
LoG = f (σ) = −
exp −
2πσ 6
2σ 2
(1.1)
σ はガウシアンフィルタのスケール，x と y は注目画素からの距離である．LoG は計算コス
トが高いという問題があり，Lowe[3] によってより効率的な極値検出法として Difference-
of-Gaussian(DoG) を用いる手法が提案されている．DoG と LoG の関係は次式の拡散方程
式から導かれる．
∂G
= σ∇2 G
∂σ
(1.2)
G はガウス関数であり，右辺はガウス関数の 2 次微分 (LoG) である．式 (1.2) は次式のよ
うに表すことができる．
∂G
G(x, y, kσ) − G(x, y, σ)
≈
∂σ
kσ − σ
(1.3)
式 (1.2) と式 (1.3) から次式が成り立つ．
∂G
G(x, y, kσ) − G(x, y, σ)
≈
∂σ
kσ − σ
(1.4)
(k − 1)σ 2 ∇2 G ≈ G(x, y, kσ) − G(x, y, σ)
(1.5)
σ∇2 G =
したがって次式が得られる．
ここで，σ 2 ∇2 G は LoG であるので，式 (1.5) は DoG が LoG の近似であることを表して
いる．LoG と DoG から得られる結果がほぼ同じであるため，SIFT では計算効率の良い
DoG を用いる．
3
1.1. SIFT：Scale Invariant Feature Transform
■ Difference-of-Gaussian 処理
キーポイント候補点は，スケールの異なるガウス関数 G(x, y, σ) と入力画像 I(u, v) を畳
み込んだ平滑化画像 L(u, v, σ) の差分 (DoG 画像) から求める．それぞれ以下の式により
求める．
L(u, v, σ) = G(x, y, σ) ∗ I(u, v)
( 2
)
1
x + y2
G(x, y, σ) =
exp −
2πσ 2
2σ 2
(1.6)
(1.7)
DoG の結果の画像を D(u, v, σ) とすると，DoG 画像は次式で求まる．
D(u, v, σ) = (G(x, y, kσ) − G(x, y, σ)) ∗ I(u, v)
= L(u, v, kσ) − L(u, v, σ)
(1.8)
この処理を σ0 から k 倍ずつ大きくした 異なるスケール間で行い，図 1.2 に示すような複
数の DoG 画像を求める．σ が一定の割合で増加し続けると，ガウシアンフィルタのウィ
図 1.2: DoG 処理の流れ
ンドウサイズが大きくなり，処理できない端領域の拡大と計算コストの増加という問題が
発生する．この問題に対し，SIFT では画像のダウンサンプリングにより σ の変化の連続
性を保持した平滑化処理を実現している．
4
1.1. SIFT：Scale Invariant Feature Transform
■ σ の連続性を保持した平滑化処理
σ の連続性を保持した効率的な平滑化処理を図 1.3 に示す．はじめに，入力画像を初期
値である σ0 で平滑化し，平滑化画像 L1 (σ0 ) を得る．次に σ0 を k 倍した値 kσ0 で平滑化
を行い L1 (kσ0 ) を得る．同様の処理により，σ の異なる複数の平滑化画像を得る．ここま
での処理 1 セットを 1 オクターブとする．次に，複数生成された平滑化画像の中から 2σ0
で平滑化された画像 L1 (2σ0 ) を 1/2 のサイズにダウンサンプリングする．1 オクターブに
おける処理回数については増加率 k の設定とともに後述する．1/2 のサイズにダウンサン
プリングされた画像 L2 (σ0 ) と，2σ0 で平滑化を行った画像 L1 (2σ0 ) には以下のような関係
が成り立つ．
L1 (2σ0 ) ≈ L2 (σ0 )
(1.9)
この関係を利用することで，σ の最大値を制限することができるため，ガウシアンフィル
タのウィンドウサイズによる計算量の増加を防ぐことができる．
■ 増加率 k
σ の増加率 k は，1 オクターブにおけるスケールスペースの分割数により決定する．ス
ケールスペースの分割数を s とした場合，1 オクターブでは，スケールスペースは σ0 か
ら 2σ0 まで増加するため，σ の増加率 k は k = 21/s となる．図 1.4 に示す DoG 処理の例で
√
は，s = 2(分割数 2) であるため，k = 21/2 = 2 となる．極値探索には DoG 画像を 3 枚 1
組で処理する必要があるため，s 枚の極値検出の対象となる画像を得るためには s + 2 枚
の DoG 画像が必要となる．さらに，s + 2 枚の DoG 画像を得るためには s + 3 枚の平滑
化画像が必要になる．したがって，1 オクターブにおける平滑化の回数は s + 3 回となる．
ここで求まる極値検出対象画像は次章で行う極値検出に用いるものである．文献 [5] では，
実験により分割数 s = 3，初期値 σ0 = 1.6 のとき，最適なキーポイントを得ることができ
ると報告されている．
1 枚の入力画像に対するオクターブ数は，入力画像のサイズに依存する．入力画像は，
処理が進むにつれて 1/2 のサイズにダウンサンプリングされる．ダウンサンプリングを続
けた結果，画像の一辺のサイズがある値以下になったとき処理を終了する．この値は任意
で決定する．この値が大きければ，少ないオクターブ数になり，小さければ多いオクター
ブ数になる．例えば 640×480 ピクセルの画像に対して，ダウンサンプリング後の最小の
5
1.1. SIFT：Scale Invariant Feature Transform
図 1.3: σ の連続性を保持した効率的な平滑化処理
サイズを 10 とした場合，6 回目のダウンサンプリングで一辺が 7 ピクセルとなり処理が
終了するため，オクターブ数は 5 となる．
■ DoG 画像からの極値検出
DoG は異なるスケールによる平滑化画像の差分のため，DoG の値が大きくなる σ では，
スケールの変化領域にエッジ等の情報量を多く含んでいるといえる．そこで，DoG 画像
から極値を検出し，キーポイントとスケールを決定する．極値の検出は，図 1.5 のように
DoG 画像 3 枚一組で行う．DoG 画像 (図 1.5 中の点線で囲まれた画像) の注目画素 (図 1.5
中の黒色領域) と，その周りの 26 近傍 (図 1.5 中の灰色領域) を比較し，極値であった場
6
1.1. SIFT：Scale Invariant Feature Transform
図 1.4: s = 2(k =
√
2) のときの DoG 処理例
合，その画素をキーポイント候補点として検出する．このような極値検出は，σ の値の小
さい DoG 画像から行う．一度極値が検出された画素は，より大きなスケールで極値が検
出されてもキーポイント候補点としない．この処理をスケールの異なる DoG 画像の全画
素に対して行う．次に，スケールスペースの極値の性質について述べる．画像中のある座
図 1.5: 極値検出の流れ
7
1.1. SIFT：Scale Invariant Feature Transform
標におけるスケール変化と DoG 出力値の推移を図 1.6 に示す．実線の円で示すスケール
サイズのとき，右に示すグラフから DoG 出力が最大値 (極大値) となることがわかる．図
1.6(a) の原画像を 2 倍に拡大した (b) においても，実線で示すスケールにて DoG の値が
最大となる．このとき，図 1.6(a) の DoG の極値を σ1 ，図 1.6(b) を σ2 とすると，σ2 = 2σ1
の関係が成り立つ．このように，画像サイズが 2 倍になると，DoG の極値探索により検
出されたキーポイントのスケール σ も比例して 2 倍となる．SIFT は，特徴を最も含むス
ケール σ を自動的に決定するため，空間的に同範囲の領域から特徴量を記述することで，
拡大・縮小に不変な特徴量となる．
図 1.6: スケールと DoG 出力の関係
1.1.2
キーポイントのローカライズ
1.1.1 により検出されたキーポイント候補点の中には，DoG 出力値が小さい点 (low contrast) やエッジ上の点が含まれており，これらの点はノイズや開口問題に影響を受け易い
という問題がある．そこで，キーポイント候補点の中から， 主曲率とコントラストによ
り安定したキーポイントに絞り込む．さらに，キーポイントのサブピクセル推定により位
置とスケールを算出する．
8
1.1. SIFT：Scale Invariant Feature Transform
図 1.7: キーポイント候補点の絞り込み
■ 主曲率によるキーポイントの絞り込み
エッジ上に存在するキーポイント候補点の削除方法について述べる．キーポイント候補
点における 2 次元ヘッセ行列 H を次式により計算し，主曲率を求める．

H=

Dxx Dxy

(1.10)
Dxy Dyy
行列内の導関数は，キーポイント候補位置での DoG 出力値の 2 次微分から得られる．こ
こで，ヘッセ行列から求められる第 1 固有値を α，第 2 固有値を β(α > β) とする．この
ときヘッセ行列の対角成分の和 Tr(H) と行列式 Det(H) は次のように計算できる．
Tr(H) = Dxx + Dyy = α + β
Det(H) = Dxx Dyy − (Dxy )2 = αβ
(1.11)
(1.12)
さらに，γ を第 1 固有値と第 2 固有値の比率とし，α = γβ とすると次式のようになる．
(α + β)2
(γβ + β)2
(γ + 1)2
Tr(H)2
=
=
=
Det(H)
αβ
γβ 2
γ
(1.13)
この値は固有値そのものではなく，固有値 α，
β の比率で決まる．したがって，固有値を求
めずにエッジ上の点であるか判別することが可能となる．この値を次式に示すようにしき
い値処理することで，不要なキーポイント候補点を削除する．
Tr(H)2
(γth + 1)2
<
Det(H)
γth
(1.14)
9
1.1. SIFT：Scale Invariant Feature Transform
式 (1.14) を満足するような点をキーポイント候補とする．しきい値は γth により決定する．
この処理は，Harris のコーナー検出に良く似たもので，固有値の比率がしきい値より大き
い点，つまりエッジ上に存在する点が削除される．文献 [5] では γth = 10 を採用しており，
しきい値は 12.1 となる．
図 1.7(a) は検出された全キーポイント候補点を表している．図中の円の中心がキーポ
イント位置，円の半径がキーポイントの持つスケールである．図 1.7(b) では，主曲率に
よりドア等のエッジ上の点が削除されていることがわかる．
■ キーポイントのサブピクセル位置推定
3 変数 (x, y, σ) の 2 次関数をフィッティングすることで，キーポイント候補点のサブピ
クセル位置とスケールを算出する．ある点 x = (x, y, σ)T での DoG 関数 D(x) をテイラー
展開すると次式のようになる．
∂D T
1 ∂2D
D(x) = D +
x + xT
x
∂x
2 ∂x2
(1.15)
式 (1.15) について x に関する偏導関数を求め，0 とすると次式が得られる．
∂D ∂ 2 D
+
x̂ = 0
∂x
∂x2
(1.16)
このとき x̂ はキーポイント候補点 (極値) のサブピクセル位置を表している．この式を変
形し次式を得る．
∂2D
∂D
x̂ = −
2
∂x
∂x
この式は次のように表される．





∂2D
∂x2
∂2D
∂xy
∂2D
∂xσ
∂2D
∂2D
∂2D
∂xy
∂y 2
∂yσ
∂2D
∂2D
∂2D
∂xσ
∂yσ
∂σ 2

(1.17)


x

 

 
 y  = −

 
σ

∂D
∂x
∂D
∂y
∂D
∂σ




(1.18)
式 (1.18) をキーポイント候補点のサブピクセル位置 x̂ を得るために変形する．




 x 

 
 y  = −

 
σ
∂2D
∂x2
∂2D
∂xy
∂2D
∂xσ
∂2D
∂xy
∂2D
∂y 2
∂2D
∂yσ
∂2D
∂2D
∂2D
∂xσ
∂yσ
∂σ 2
−1 









∂D
∂x
∂D
∂y
∂D
∂σ




(1.19)
10
1.1. SIFT：Scale Invariant Feature Transform
得られた式 (1.19) を解くことにより，キーポイント候補点のサブピクセル位置 x̂ = (x, y, σ)
を得る．
■ コントラストによるキーポイントの絞り込み
サブピクセル位置での DoG 出力を算出し，コントラストによるキーポイントの絞り込
みを行う．式 (1.19) は次のように表される．
x̂ = −
∂ 2D
∂x2
−1
∂D
∂x
(1.20)
式 (1.20) を式 (1.15) に代入すると次式が得られる．
D(x̂) = D +
1 ∂D T
x̂
2 ∂x
(1.21)
D は DoG 関数であり，x̂ はサブピクセル位置を表しているため，式 (1.21) はサブピクセ
ル位置での DoG 出力値となる．この DoG の値からキーポイント削除の判別を行う．文献
[5] では，しきい値として 0.03 を用いている．サブピクセル位置での DoG 出力の絶対値が
しきい値より小さい場合 (つまり，コントラストが低い場合) ノイズに影響されやすいた
め削除する．図 1.7(c) にコントラストにより絞り込まれたキーポイントを示す．
1.1.3
オリエンテーションの算出
検出したキーポイントに対して，第 2 段階の処理である特徴量の記述を行う．まず，検
出された各キーポイントのオリエンテーションを求める．オリエンテーションはキーポイ
ントにおける方向を表し，特徴量記述の際にオリエンテーションにより向きの正規化を
行うことで，回転に不変となる．キーポイントのオリエンテーションを求めるには，まず
キーポイントが検出された平滑化画像 L(u, v) の勾配強度 m(u, v) と勾配方向 θ(u, v) を以
下の式により求める．
√
fu (u, v)2 + fv (u, v)2
fv (u, v)
θ(u, v) = tan−1
fu (u, v)
m(u, v) =
(1.22)
(1.23)
11
1.1. SIFT：Scale Invariant Feature Transform

 f (u, v) = L(u + 1, v) − L(u − 1, v)
u
 fv (u, v) = L(u, v + 1) − L(u, v − 1)
(1.24)
局所領域における勾配強度 m(x, y) と勾配方向θ(x, y) から図 1.8 に示すような重み付方向
ヒストグラム h を以下の式により作成する．
hθ′ =
∑∑
x
w(x, y) · δ [θ′ , θ(x, y)]
(1.25)
y
w(x, y) = G(x, y, σ) · m(x, y)
(1.26)
ここで，hθ は，全方向を 36 方向に量子化したヒストグラムである．w(x, y) はある局所領
域の画素 (x, y) での重みであり，キーポイントが持つスケールサイズのガウス窓 G(x, y, σ)
と勾配強度 m(x, y) から求める．δ は Kronecker のデルタ関数で，勾配方向 θ(x, y) が量子
化した方向 θ′ に含まれるとき 1 を返す．また，このときのガウス窓にはキーポイントが持
つスケールを用いる．ガウス窓による重み付けにより，キーポイントに近い特徴量がより
強く反映される．この 36 方向のヒストグラムの最大値から 80% 以上となるピークをキー
ポイントのオリエンテーションとして割り当てる．
図 1.8 の例ではキーポイントに割り当てられるオリエンテーションは 1 方向のみである
が，図 1.9 のようにコーナーのようなキーポイントでは 2 方向となり，2 つのオリエンテー
ションを持つ．このように，1 つのキーポイントに対して複数のオリエンテーションが割
り当てられる場合がある．
1.1.4
特徴量の記述
検出したオリエンテーションを基に，SIFT descriptor により 128 次元の特徴量を記述
する．まず，図 1.10 に示すようにキーポイントのオリエンテーション方向に回転する．特
徴量の記述には，キーポイント周辺領域の持つ勾配情報を用いる．使用する勾配情報は，
キーポイントを中心とし，そのキーポイントが持つスケールを半径とした円領域内から求
める (図 1.10 中のガウス窓内の領域)．周辺領域を一辺を 4 ブロックの計 16 ブロックに分
割し，図 1.10 に示すようにブロックごとに 8 方向 (45 度ずつ) の勾配方向ヒストグラムを
作成する．この勾配方向ヒストグラムは，キーポイントのオリエンテーションを算出した
ときに作成したヒストグラムと同様の手法で求める．
12
1.1. SIFT：Scale Invariant Feature Transform
図 1.8: ヒストグラム作成の流れ
図 1.9: 2 方向のオリエンテーションを持つキーポイント
図 1.11 の例では 4×4 = 16 ブロックに各 8 方向のヒストグラムを作成するため，4×4×8 =
128 次元の特徴ベクトルとしてキーポイントの特徴を記述する．このように，キーポイン
トが持つオリエンテーション方向に座標軸をあわせた領域で特徴を記述するため，回転に
不変な特徴量となる．また，128 次元の各特徴ベクトルの長さはベクトルの総和で正規化
13
1.1. SIFT：Scale Invariant Feature Transform
図 1.10: 特徴量を記述する領域
する．これにより，キーポイントは照明変化に対して影響の少ない特徴量となる．
図 1.11: ブロックごとの特徴量記述
14
1.2. SURF: Speeded Up Robust Features
1.2
SURF: Speeded Up Robust Features
SIFT は，画像の回転やスケール変化等に不変であるため，それら要素に適している．
しかし，処理コストが高いことが問題となっており，SIFT を用いるアプリケーションで
はリアルタイム処理が難しい課題となっている．SIFT を高速化したアルゴリズムである
Grabner らが提案する FastApproximatedSIFT[6] は検出段階で Integral Image を活用し
DoG 処理→ DoM 処理に変更，記述段階では Integral Histogram を用いている．しかし，
DoM 処理において DoG を近似していないため，画像ノイズによわく，スケール変化の頑
健性も SIFT に比べ劣る．そこで，検出段階を SIFT と近似して高速化をはかった Herbert
Bay らが提案する Speeded Up Robust Features(SURF)[7] を以下に説明する．
1.2.1
検出段階
図 1.12: 手法の流れ
SIFT は DoG 画像を作成することでキーポイントを検出しているが，SURF は Hessian
行列を算出することでキーポイントを検出している．Hessian 行列を高速に算出するため
に，Integral Image を用いる．これは，Hessian 行列の算出に box filters を用いる box filters
はある領域の画素の合計を求める処理が含まれるため，Integral Image を使うと高速に処
理できるからである．キーポイント算出までの処理の流れを図 1.12 に示す．
15
1.2. SURF: Speeded Up Robust Features
■ キーポイントとは
ハリスや SIFT のキーポイントは基本的には輝度変化の大きなエッジ上が選ばれる．エッ
ジ上が好まれる理由は，テスクチャのない所よりもテスクチャが多いところの方が，そ
の場所を示す情報が多いためである．エッジは，x 方向とｙ方向の片方に輝度差が大きい
場所や xy 方向の両方の輝度差が大きい場所をいい，輝度差には正負があるため大きく 3
種類に分けられる．(全部で６種類）図 1.13 に x と y 方向の輝度差について示す．xy 方向
の両方の輝度差が大きく同一方向の時は図 1.13(左) のようにドーム型の曲面になる．図
1.13(中) は，xy 方向の両方の輝度差が大きいが，x 方向とｙ方向の輝度差の向きが異なっ
ている場合，図 1.13(右) は，x 方向とｙ方向の片方に輝度差が大きい場合を示している．
エッジを見つける場合は，輝度差が図 1.13 のどのタイプになるのかを調べることにより
検出できる．図 1.13 の分類は Hessian 行列を求めガウス曲率を求めることにより判別す
ることができる．
図 1.13: 曲面
■ Hessian 行列


H=
Lxx Lxy

(1.27)
Lxy Lyy
Hessian 行列は，表面の曲率に関する情報を示しており，Hessian 行列を求めることによ
り，ガウス曲率を求めることができる．Lxx (x, y, σ) は x 軸の 2 次微分結果であり，σは
ガウス関数の標準偏差である．
16
1.2. SURF: Speeded Up Robust Features
Hessian 行列からガウス曲率を求めるには次式の det(H) を算出する．
det(H) = Lxx Lyy − (Lxy )2
(1.28)
det(H) が正の値を持つ時は，x 方向と y 方向の輝度差が同一方向に大きいことになる．
det(H) が負の値を持つ時は x 方向と y 方向の輝度差が大きいが向きが異なる場合である．
det(H) が 0 のときは，x 方向とｙ方向の片方に輝度差が大きい場合を示している．det(H)
を調べることにより図 1.13 に示すようにエッジの種類を判別が可能となる．SURF は各ス
ケールの画像に対して det(H) を求めて極値探索によりキーポイントを検出する．Hessian
行列算出において，Lyy や Lxy を微分により求めると，各画素の値を参照して求める必
要があるため，計算コストが高い．そこで，SURF では，Integral Image と box filters を
用いることで高速に計算している．box filters により算出された Lyy , Lxx , Lxy をそれぞれ
Dyy , Dxx , Dxy とすると，det(H) は次式より算出される．
det(Happrox) = Dxx Dyy − (0.9Dxy )2
(1.29)
0.9 倍してあるのは，近似のために生じる誤差を修正するためである．0.9 倍は実験的に求
めたパラメータである．SURF でキーポイントとするのは図 1.13(左) のみである．他の種
類はキーポイントとして検出しない．
■ box filters
σ=1.2 の Lxy ，Lyy の box filters を図 1.14 に示す．フィルタサイズ 9 × 9 の box filters は
σ=1.2 のガウシアンと同等となる．Lxy ，Lyy は，図 1.14(左）になり box filters で近似し
た Dxy , Dyy は図 1.14（右）になる．box filters で近似することにより各画素ごとの演算が
不要である領域の合計値を算出する処理に変わるため，Integral Image を用いた算出が可
能となり高速化できる．
キーポイント検出にはまず，9 x 9, 15 x 15, 21 x 21, 27 x 27 のフィルタサイズを用い
る．それぞれ，1.2, 2.0, 2.8, 3.6 のスケールに対応している．
17
1.2. SURF: Speeded Up Robust Features
図 1.14: box filters
■ Integral Image
Integral Image(積分画像) は，2001 年に Viola と Jones により提案された手法である．矩
形領域が重なり合う場合，積分画像は高速に矩形領域の輝度値の和を算出することができ
る．画像 I(x, y) から求められる積分画像 ii(x, y) は次式より算出できる．
ii(x, y) = ii(x − 1, y) + s(x, y)
(1.30)
s(x, y) = s(x, y − 1) + I(x, y)
(1.31)
ここで，s は y 軸方向の累積画像，s(x, −1) = ii(−1, y) = 0 とする．一度，積分画像を
算出することにより，図 1.15 の領域 D の輝度値の合計を式 (1.32) より高速に算出するこ
とができる．
D = (ii(x, y) + ii(x + W, y + H)) − (ii(x + W, y) + ii(x, y + H))
(1.32)
積分画像を用いない場合，矩形領域内の画素数だけ加算が必要である．しかし，積分画
像を用いた場合，ラスタスキャンを 2 回行い，矩形領域の数の度に 3 回の加減算を行うだ
けでよい．
18
1.2. SURF: Speeded Up Robust Features
図 1.15: 領域の輝度和 ([12])
■ スケールスペース
SIFT では，画像サイズを変えることで，スケールスペースを求めている．しかし，画
像のスケーリングは処理コストが大きい．SURF では，box filters と Integral Image を用
いてガウス曲率を求めているため，box filters のフィルタサイズを大きくしても処理コス
トが増加しない．そのため，SIFT のスケールスペースより高速に求めることができる．
図 1.16: スケールスペース
19
1.2. SURF: Speeded Up Robust Features
■ 極値探索
キーポイント検出の極値探索は SIFT と同様に行われる．異なるスケールのフィルタリ
ング結果を 3 枚 1 組で 26 近傍探索を行う．26 近傍で極値ならキーポイントとして検出す
る．検出結果を図 1.18 に示す．
図 1.17: 極値探索
図 1.18: キーポイント検出結果 [7]
20
1.2. SURF: Speeded Up Robust Features
1.2.2
記述段階
回転の不変性を得るためのオリエンテーションと特徴量記述方法を下記に示す．
■ オリエンテーション
キーポイントを中心とした半径 6s（s：スケール) の範囲から Haar-Wauelet（4s) を用い
て勾配方向を求める．そのとき，SIFT と同様に勾配強度を算出し，勾配強度が最も大き
い方向をオリエンテーションとしている．SIFT では 10 度ごともとめているが，SURF で
は 60 度ごとである．U-SURF はこの工程をスキップしている．そのため，回転変化に不
変ではない．
■ 特徴量記述
キーポイントを中心とした 20s × 20s（s：スケール) の正方形領域を 4 × 4 のサブ領域に分
割し Haar-Wauelet（2s × 2s) を算出することにより，勾配ベクトルを求める．勾配ベクトル
∑
∑
∑
∑
の x 方向，ｙ方向をそれぞれ dx , dy とする．dx , dy より 4 次元ベクトル ( dx , dy , |dx |, |dy |)
を求める．x 方向の勾配が大きく，その絶対値も大きいときは正の勾配方向となり，逆に
負の勾配方向のときは，x 方向の勾配が小さく，その絶対値は大きくなる．このように，
方向とその絶対値の情報により強度変化の極性の情報が得られる．16 のサブ領域から 4
次元ベクトルを求めて 64 個の特徴量を算出することができる．より精度を求めるために
128 次元の特徴量も用意されている．これは，同様の方法により 4 × 4 のサブ領域に分割
∑
∑
∑
∑
する．64 次元では 4 次元ベクトル ( dx , dy , |dx |, |dy |) を求めているが，128 次元
∑
∑
では， dx , |dx | を求める時に dy < 0 と dy ≥ 0 にの場合に分けて dy < 0 の時の合計と
∑
∑
dy ≥ 0 の時の合計を求めている．同様に， dy , |dy | を求めている．これは，強度変化
(向き，強さ）の情報が詳細になるため精度の向上が期待できる．また，比較用として 36
次元の特徴量も用意された．これは，64 次元の特徴量算出のときに 4 × 4 のサブ領域に
分割するのを 3 × 3 のサブ領域に変更する．これにより 9 × 4 の 36 次元の特徴量を記述
する．
21
1.2. SURF: Speeded Up Robust Features
図 1.19: 特徴量記述
22
1.3. Randomized Trees を用いたキーポイントの分類
1.3
Randomized Trees を用いたキーポイントの分類
SIFT をベースとしたアプローチでは，回転やスケール変化に頑健であるがアフィン変
化に対応できず，高精度でリアルタイム処理は困難である．そこで，アフィン変化に頑健
でリアルタイムでマッチングが可能な手法を以下に述べる．Lepetit 等が提案する手法 [2]
は，Randomized Trees を用いたクラス分類手法をキーポイントの分類に応用した手法で
ある．リアルタイムにキーポイントを検出しキーポイントの分類を行うことを実現して
いる．キーポイントの分類は，テンプレート画像の N 個のキーポイント K = k1 ...kn を
抽出し，入力画像から抽出されたキーポイントのパッチ画像 p(kinput ) と，テンプレート
画像のキーポイント ki のどれと一致するか決定することである．そのため，決定木から
p(kinput ) に一致するクラスラベル Y (p) ∈ C = 1, 2, ..., N を見つける．
以下に，高速なキーポイント検出手法 [13]，キーポイントの分類に用いる決定木の構築，
決定木を用いたマッチングの手法を述べる．
1.3.1
キーポイント検出
リアルタイムに対応点をマッチングするためには，高速なキーポイント検出が必要であ
る．キーポイント検出は，LoG の応答値からキーポイントの候補を決定し，LoG により
スケールを探索しオリエンテーションを算出する．
最初に，キーポイントの候補を探索する．図 1.20 に示すように，テンプレート画像を
ラスタ操作した注目画素 m についての LoG の応答を算出し，近傍で最大となる m をキー
ポイントの候補とする．高速に LoG を算出するために計算コストを削減したものに近似
する．LoG の近似は以下の式に示す．
LoG(m) ≈ Σα∈[0;π] Iσ (m − dRα ) − Iσ (m) + Iσ (m + dRα )
(1.33)
図 1.21 に近似された LoG を示す．Iσ は平滑化後の画像である．dRα は dRα = (R cos α; R sin α)
であり，R が半径を示す．R を大きくしていき応答値が最大になったときの R をスケール
値とする．
次に，オリエンテーションを求める．オリエンテーションは以下の式から算出される．
αm = arg max |Iσ (m) − Iσ (m + dRα )|.
(1.34)
α∈[0;2π]
23
1.3. Randomized Trees を用いたキーポイントの分類
図 1.20: キーポイントの検出アプローチ
図 1.21: LoG の近似
注目画素 Iσ (m) と円上の Iσ (m + dRα ) の輝度差が最も大きい時の α がオリエンテーショ
ンとなる．
最後に，すべてのキーポイントにおいて，以下の条件を満たすキーポイントを不安定な
キーポイントとして除去する．
If|Iσ (m) − Iσ (m + dRα )| ≤ +τ and
if|Iσ (m) − Iσ (m − dRα )| ≤ +τ then m is not a keypoint
(1.35)
Iσ (m) とスケール上のピクセル Iσ (m + dRα ) と Iσ (m − dRα ) の画素の輝度差が閾値 τ よ
り大きい場合はキーポイントとして検出する．以上のキーポイント検出手法は，スケール
探索の処理結果からオリエンテーションとキーポイント検出が可能であるため高速に処理
が可能である．
24
1.3. Randomized Trees を用いたキーポイントの分類
1.3.2
決定木の構築
決定木の構築は，学習画像の作成，決定木の構築からなる．
■ 学習データ
アフィン変化に頑健なキーポイントを選択するために，ランダムなパラメータである
アフィン変換行列 Γ を作成し，複数個の Γ を用いて図 1.22 に示す学習データを構築する．
この学習データのすべての画像からキーポイントを検出してアフィン変化に頑健なキーポ
イントを選択する．
図 1.22: テンプレート画像のアフィン変換
・アフィン変化に頑健なキーポイントの選択
図 1.22 の学習データからキーポイントを検出し，同一位置のキーポイントの検出数をカ
ウントする．元となるキーポイントを検出するために，アフィン変換前のテンプレート画
像からキーポイントを検出する．学習データ全てからキーポイントを検出し，変換に用い
たアフィン変換行列 Γ の逆行列 Γ−1 を用いてキーポイントをテンプレート上の座標に変
換する．座標を変換することで，テンプレート上の対応するキーポイントがわかるため，
同一位置のキーポイントを数えて，異なるアフィン変換に対して多く検出されたキーポイ
ントを抽出することができる．こうすることで，アフィン変化に頑健なキーポイントを選
択できる． 実験では，200 個以上のアフィン変換に対して同一位置のキーポイントを保
持している．図 1.23 は，ブックカバーと人形上で選択されたキーポイントを示す．
25
1.3. Randomized Trees を用いたキーポイントの分類
図 1.23: 画像変化に頑健なキーポイント
■ Randomized Trees
決定木の例を図 1.24 に示す．決定木 T = (T1 , …, TL ) は分岐点（ノード）とノードの末
端（リーフノード）から構成される．ノードには子ノードに分岐するための条件（特徴
量）が記述されている．ノードとその分岐条件（特徴量）は事前に作成され，ノードの階
層の数は事前に決められている．リーフノードには，テンプレートの各キーポイントがど
れくらいたどり着いたのかを示す確率分布 pη(l,P) (Y (P) = c) が格納されている．η(l, P)
は，入力パッチ画像 P のたどり着いた木 Tl のリーフノードであり，ｃ はテンプレートの
キーポイントの種類を示す．リーフノードの確率分布を構築するために図 1.25 に示すよ
うに，キーポイントを中心とした 32 × 32 のパッチ画像を作成する．横方向にはアフィン
変換パラメータは異なるが同一位置のキーポイントのパッチ画像を示している．このパッ
チ画像はキーポイントのスケールにより正規化されている．決定木を構築するために図
1.25 をランダムにサブセットに分ける．サブセット 1 つにつき決定木が構築される．実験
ではサブセットの数を 32 個としている．サブセット内の画像すべてを決定木に入れリー
フノードの確率分布を構築していく．
・特徴量
ノードの特徴量は，キーポイントを中心としたパッチ画像内の 2 点のピクセル m1 と m2
の輝度差を特徴量とする．
C2 (m1, m2) =


go to left child
if Iσ (P, m1) < Iσ (P, m2)

go to right child otherwise
(1.36)
Iσ (P, m) は，画像ノイズの影響を抑える平滑化 (Gaussian) の後のパッチ画像 P の注目画
素 m の輝度値である．パッチ画像サイズは 32 × 32 である．この特徴は 2 点の輝度レベ
26
1.3. Randomized Trees を用いたキーポイントの分類
図 1.24: 決定木
図 1.25: 学習データ
ルの差を見ているので，影等の影響は受けるが，照明変化に頑健な傾向にある．
1.3.3
キーポイントの分類
決定木を用いて入力画像のキーポイントとマッチングを行う．流れを図 1.26 に示す．入
力画像からキーポイントを検出し，各キーポイントから 32 × 32 のパッチ画像を作成する．
キーポイントのパッチ画像を決定木に入れることでリーフノードの確率分布に基づいて
テンプレート画像のキーポイントに分類する．分類は，図 1.26 に示すように，入力した
パッチ画像 P がたどり着いた木 T = (T1 , …, TL ) のリーフノードの確率分布の平均 Pc (P)
27
1.3. Randomized Trees を用いたキーポイントの分類
図 1.26: キーポイントの分類
を以下の式より求め，最も平均の高いキーポイント ｃ に分類される．
1∑
pη(l,P) (Y (P) = c)
Ŷ (P) = arg max pc (P) = arg max
c
c
L l=1
L
(1.37)
上記の分類では必ずどこかのキーポイントに分類されるため，その分類が正しいかを判断
するために下記の式により閾値処理する．s は信頼度であり，Tc は閾値である．
P (Y (P) = c|Ŷ (P) = c, pc (P) > Tc ) > s
(1.38)
信頼度 s は 60 ％と 90 ％の間をとる．Pc (P) が Tc より低いキーポイントはテスクチャの少な
い背景上で検知されたキーポイントの可能性が高い．あるいはキーポイントの分類を誤っ
た可能性が高くなり，そのようなキーポイントは削除する必要がある．これは，RANSAC
により削除する事が可能である．Randomized Trees の欠点はメモリを大量に消費するこ
とである．メモリの使用容量は，木の深さや木の数につれて，指数関数的に増加する．し
たがって，木の深さや木の数は，木の情報を格納するメモリーと認識率の間のトレードオ
フとなる．
28
第2章
2.1
ワイルドカードを用いた
Random Ferns によるキーポイ
ントの分類
Random Ferns を用いたキーポイントの分類
1.3 で述べたように，決定木を用いたキーポイントマッチング手法は，従来の SIFT を用
いた手法と比較して，高速かつアフィン変化に頑健なマッチングが可能である．しかし，
Randomized Trees によるキーポイントマッチングは，サンプルに対するノードの分岐が
親ノードの分岐に依存する．そのため，階層の浅いところから順に処理をしていく必要
があり，計算効率が悪いという問題がある．一方，Ozuysal らが提案する Random Ferns
を用いたキーポイントマッチング手法 [1] は，図 2.1 に示すように，決定木の各ノードに
おける分岐関数を階層ごとに統一し，ノードを独立させることで，サンプルの特徴を “0”
と “1” のバイナリで表現して高速な処理を可能としている．以下に，Random Ferns を用
いたキーポイントマッチング手法について説明する．
2.1.1
決定木の構築
Random Ferns における決定木の構築は，Randomized Trees を用いたキーポイントマッ
チング手法と同様で，学習サンプルの生成と決定木の学習からなる．
29
2.1. Random Ferns を用いたキーポイントの分類
Randomized Tree
Random Fern
F1
F1
F2
F4
F3
F5
F6
F1
F2
F7
F3
F2
F3
F3
F2
F3
F3
図 2.1: Random Ferns
■ 学習サンプルの生成
Randomized Trees の学習サンプルは，アフィンパラメータ Γ をランダムに決定し，テ
ンプレート画像をアフィン変換することで作成している．しかし，ランダムでパラメー
タを決定すると，テンプレート画像の見えに偏りが起きることがある．文献 [1] では，こ
の問題を解決するためにテンプレート画像のキーポイントから抽出したパッチ画像をオ
イラー角を用いて回転する．このとき，xyz 軸の回転角度を等間隔に網羅的に変更するこ
とで，サンプルの見えの偏りが無くなり，且つ従来の方法では表現できない 3 次元上の回
転を表現することができる．式 2.1 に，2 次元座標のオイラー角の回転行列を示す．各回
転パラメータは図 2.2 に示す関係にあり，それぞれの範囲は ϕ ∈ [0◦ , 90◦ ]，θ ∈ [0◦ , 90◦ ]，
ψ ∈ [0◦ , 360◦ ] である．作成した学習サンプルの例を図 2.3 に示す．
[ ′] [
][
][
][ ]
x
cos(ψ) − sin(ψ) cos(θ) 0 cos(ϕ) − sin(ϕ) x
=
y′
sin(ψ) cos(ψ)
0
1 sin(ϕ) cos(ϕ)
y
(2.1)
生成したパッチ画像をキーポイントごとに同一のクラス ci (i = 1, 2, . . . , I) とし，学習
サンプルとする．
■ 決定木の学習
生成した学習サンプルを用いて決定木 F =(F1 , F2 , . . . , Fk , . . . , FK ) を学習する．K は決
定木の数を示す．各ノードは，学習サンプル内のランダムに選択した 2 点のピクセル m1
30
2.1. Random Ferns を用いたキーポイントの分類
z
ψ
θ
φ
x
y
図 2.2: オイラー角によるパッチ画像の回転
図 2.3: 学習サンプルの例
と m2 の輝度値の大小関係により，式 (2.2) を用いて “0” か “1” のバイナリを出力する．サ
ンプルの特徴を末端ノードまでのバイナリコードで表現し，各クラスの出力パターン b の
頻度を表すヒストグラム H k,ci = {hk,ci (1), . . . , hk,ci (M )}(M は出力パターン数) を決定木
ごとに保持するしておく．分類時にはこのヒストグラム H を用いて特徴の近いキーポイ
ントクラスに分類する．
f=


0 if m1 < m2

1 otherwise
(2.2)
31
2.1. Random Ferns を用いたキーポイントの分類
2.1.2
キーポイントの分類
構築した決定木を用いて入力画像のキーポイント分類を行う．流れを図 2.4 に示す．入
力画像のキーポイントから抽出したパッチ画像を決定木に入力し，各決定木から得られる
出力バイナリコードの頻度を式 (2.3) を用いてキーポイントを分類する．
入力画像
F1
F2
０
１
０
１
０
１
１
０
７
５
０
０１２３４５６７
...
.
.
.
０１２３４５６７
.
.
.
.
.
.
０１２３４５６７
０１２３４５６７
{
=
1: ＜
0 : otherwise
max
...
=
０１２３４５６７
...
頻度
cI
...
０１２３４５６７
頻度
.
.
.
１
...
０１２３４５６７
c2
FK
頻度
c1
パッチ画像
０１２３４５６７
=
c1 c2
...
cI
０１２３４５６７
図 2.4: Random Ferns によるキーポイント分類
cˆi = argmax
ci
K
∏
hk,ci
(2.3)
k=1
32
2.2. 提案手法の流れ
提案手法の流れ
2.2
Random Ferns は，入力画像のキーポイントから抽出したパッチ画像を入力し，決定木
ごとに出力されるバイナリコードを用いてキーポイントの分類を行う．しかし，このよう
なバイナリコードを用いた特徴表現は，ノイズ等の影響でパッチ画像の輝度値が変化し，
取得されるバイナリコードにビット反転が発生した場合に認識精度が低下する問題があ
る．そこで，本研究では入力画像から得られるバイナリコードにワイルドカード (“∗”) を
導入し，ビット反転を起こしたノードをマスキングしてその影響を抑制することで，ノイ
ズに頑健なキーポイントの分類を行う．図 2.5 に提案手法によるキーポイント分類 “∗” の
流れを示す．ワイルドカードを用いた Random Ferns によるキーポイント分類は，まず，
学習により構築した Random Ferns に未知入力画像から抽出したパッチ画像を入力する．
次に，パッチ画像から得られたバイナリコードに対して各ノードに “∗” を適用した場合の
頻度を算出する．算出した頻度を用いてクラスごとに最適なマスキングパターンの結果を
選択し，各決定木の出力とする．最後に，Random Ferns と同様に各決定木の出力を総乗
することで，頻度が最も高くなるキーポイントクラスに分類する．
F1
Random Ferns の頻度分布
FK
０
１
０
１
１
０
...
００１
ク
ラ
F2
１
...
０
...
average
ス
頻度
F1
０１２３４５６７
出力パターン
パッチ画像
入力画像
＊ パターン
００１
max
００＊
０
０
＊
０
＊
１
＊
０
１
max
ラ
０
０
１
００＊
...
ク
＊０１
＊ による頻度の統合
1: ＜
0 : otherwise
１
ス
０＊１
{
クラス ci
クラス ci
=
クラス ci
クラス ci
図 2.5: “∗” を用いた Random Ferns によるキーポイント分類
33
2.3. 分岐関数の選択
2.3
分岐関数の選択
提案手法は，Random Ferns の出力バイナリコードに対して “∗” を導入することで，入
力画像に含まれる画像ノイズの影響を抑制する．Random Ferns の各ノードにおける分岐
関数は 2.1 に述べたように，パッチ画像中からランダムに選択した 2 点のピクセルの輝度
値の大小関係を用いる．そのため，分岐関数で選択された 2 点のピクセルがパッチ画像内
の 1 つのノイズに含まれないように設計すべきである．そこで，提案手法では分岐関数に
おいて選択される 2 点のピクセルが一定以上のユークリッド距離だけ離れるような制約を
設ける．図 2.6 に従来法と提案手法それぞれの選択方法で選択された分岐関数を示す．こ
こで，1 点目に選択されたピクセルを赤，2 点目に選択されたピクセルを黄色で示す．
図 2.6 より，従来の選択方法は完全にランダムに設定しているため，2 点が近い位置に
選択される場合もある．一方，提案手法における分岐関数は 2 点が離れた位置に選択され
ていることがわかる．これにより，提案手法は選択された 2 点のピクセルが 1 つの画像ノ
イズに含まれることを防いでいる．
34
2.3. 分岐関数の選択
(a) 従来の選択方法
(b) 提案手法の選択方法
図 2.6: 選択された分岐関数
35
2.4. 提案手法によるキーポイントの分類
2.4
提案手法によるキーポイントの分類
提案手法は，未知入力画像のパッチ画像を各決定木 k に入力して得られたバイナリコー
ド b において，ビット反転が発生したバイナリに対して “∗” を導入する．しかし，出力さ
れるバイナリコードの情報からは，どのノードでビット反転が発生したかはわからない．
そこで，提案手法では，各ノードに対して網羅的に “∗” を導入して頻度を算出すること
で，マスキングするバイナリを選定する．これにより選択された最適なマスキングパター
ンを用いてバイナリコードをマスキングし，マスキングされたバイナリコードにおける頻
度を各決定木，各クラスで算出することでキーポイントの分類を行う．
2.4.1
ワイルドカードにより許容される複数の頻度の統合
取得したバイナリコード b の各バイナリに対して “∗” を適用したパターン b∗ を考え
る．例えば，ある決定木から得られたバイナリコードが (1010)2 の場合，“∗” パターンは
b∗ = (1010)2 , (101∗)2 , (10 ∗ 0)2 , (1 ∗ 10)2 , (∗010)2 となる．このとき，“∗” の導入により許
容される各クラス ci の複数の頻度 hk,ci は，図 2.7 に示すように式 (2.4) を用いて平均によ
り pk に統合する．
＊ を適用したバイナリ
b*
１０１０
取得したバイナリ
b
１０１０
１０１＊
１０＊０
１＊１０
＊０１０
平均
１０１０
１０１１
平均
１０１０
１０００
平均
１０１０
１１１０
平均
１０１０
００１０
図 2.7: “∗” による複数のバイナリコードの許容
36
2.4. 提案手法によるキーポイントの分類
∗
pk (ci , b ) =
1
2f (b∗ )
∑
(11...1)2
hk,ci (b∗ ) δ[ b∗ , n ]
(2.4)
n=(00...0)2
ここで，f (b∗ ) は b∗ に含まれる “∗” の数を出力する関数を示している．また δ[·] はクロネッ
カーのデルタ関数を表しており，2 つの要素が一致する場合は 1，それ以外は 0 を出力する
関数である．したがって式 (2.4) は，(00 . . . 0)2 から (11 . . . 1)2 までの全てのバイナリコー
ドと，b∗ が一致するときの頻度を総和し，それを頻度の数で除算することで平均による
頻度の統合を行っている．これにより，各バイナリに “∗” を適用したパターン b∗ のそれ
ぞれの頻度を算出できる．
2.4.2
マスキングするバイナリの選択
最終的にマスキングを行うバイナリは，前節で求めた b∗ の頻度 pk を用いて選択する．
元々出力されたバイナリにおける頻度，各ノードに対して “∗” を適用した場合の頻度をそ
れぞれ算出し，式 (2.5) に示すように，全ての “∗”b∗ の内，クラス ci ごとに頻度 pk の値が
最大となるようなマスキング位置を選択する．
p′k (ci ) = max
pk (ci , b∗ )
∗
b
(2.5)
この処理を全ての決定木で行い，各決定木におけるバイナリのマスキングを考慮したクラ
スごとの頻度を算出する．そして式 (2.6) により各決定木の頻度 p′k を総乗し，算出された
値が最大となるキーポイントクラス ci に入力画像パッチを分類する．
cˆi = argmax
ci
K
∏
p′k (ci )
(2.6)
k=1
37
第3章
評価実験
提案手法の有効性を示すため，2 種類の評価実験を行う．本章では，評価実験の詳細に
ついて述べる．
3.1
データベース
Random Ferns を構築するための学習サンプルには，テンプレート画像のキーポイン
トから抽出したパッチ画像をアフィン変換した画像を用いる．図 3.1 に示すテンプレート画
像から作成した学習サンプルを用いて，オイラー角を ϕ ∈ [0◦ , 90◦ ] は 5◦ 刻み，θ ∈ [0◦ , 90◦ ]
は 5◦ 刻み，ψ ∈ [0◦ , 360◦ ] は 30◦ 刻みで変化させてアフィン変換を行い，一つのキーポイ
ントクラスにつき約 15,000 枚の学習サンプルを生成する．生成した全ての学習サンプル
をデータベースとして使用し，決定木を学習する．
図 3.1: テンプレート画像
38
3.2. 実験概要
3.2
実験概要
評価実験は，従来法の Random Ferns と，提案手法の “∗” を導入した Random Ferns に
よる認識精度の比較を行う．評価には，キーポイントマッチングの正解率を用いる．入力
画像にはテンプレート画像を一定のアフィンパラメータにより変換した画像を使用する．
テンプレート画像と入力画像とでキーポイントマッチングを行い，実際に検出・マッチン
グされたキーポイントの座標と，テンプレート画像のキーポイントの座標をアフィンパラ
メータにより変換した座標値との正誤判定を行う．入力画像から検出するキーポイント数
に対する正解数により従来法と提案手法の認識精度を比較する．また，提案手法の画像ノ
イズに対する有効性を確認するため，入力画像に一定の割合の画像ノイズを付加して実験
を行う．複数の入力画像によるキーポイントマッチングの結果より，(1) 画像ノイズの割
合による認識精度の比較，(2) 決定木の深さによる認識精度の比較を行う．各実験に使用
するパラメータは表 3.1 に示す．提案手法は，導入する “∗” の数を最大 1 ∼ 2 の 2 つを実
験に使用する．
表 3.1: 実験パラメータ
実験
キーポイントクラス数 I
決定木の数 K
決定木の深さ
画像ノイズの割合 [% ]
(1)
100
80
20
0 ∼ 50
(2)
100
80
4 ∼ 20
40
39
3.3. 実験結果
3.3
実験結果
評価実験 (1) の結果を図 3.2，表 3.2 に示す．図 3.2，表 3.2 より，従来法は入力画像に
含まれる画像ノイズの割合に比例して認識精度が低下する．しかし，提案手法は画像ノイ
ズの割合が高い場合においても従来法と比較して高い認識精度を維持できている．また，
決定木に導入する “∗” の数を増加すると，ノイズが含まれない入力画像に対しては従来法
よりも認識精度が低下する．しかし，“∗” の数が多いほど，高い割合のノイズを含む入力
画像に対して高い認識精度で分類が行える．以上のことから，提案手法は画像ノイズの影
響によるビット反転を抑制し，頑健にキーポイント分類を行えることがわかる．
50
正解率 [%]
40
30
20
10
0
従来法
提案手法＊1個
提案手法＊2個
0
10
20
30
ノイズの割合 [%]
40
50
図 3.2: キーポイントマッチングの正解率 [%](実験 1)
表 3.2: キーポイントマッチングの正解率 [%](実験 1)
ノイズ割合 [%]
従来法
0
10
20
30
40
48.6 47.2 42.6 30.3 15.4
50
8.5
提案手法 “∗”1 個
48.6 48.3 47.2 44.4 35.3 21.5
提案手法 “∗”2 個
47.5 47.2 46.8 45.5 41.5 31.9
40
3.3. 実験結果
評価実験 (2) の結果を図 3.3，表 3.3 に示す．図 3.3，表 3.3 より，提案手法は決定木の
深さが 6 以下の場合に従来法と比較して認識精度が低下する．しかし，決定木の深さが小
さすぎるため十分な学習ができておらず，従来法においても高い認識精度が得られていな
い．一方，従来法において最も高い認識精度の場合 (深さ 16) を比較すると，提案手法は
従来法と比較して高精度な認識を実現している．したがって，十分な深さの決定木を構築
することで，提案手法は従来法よりもノイズに頑健なキーポイント分類が可能なことがわ
かる．また，導入する “∗” の数は，決定木の深さに対して 1 割以下となるように設計する
ことで十分な効果が得られることを実験により確認した．
50
40
従来法
提案手法＊1個
提案手法＊2個
正解率 [%]
30
20
10
0
4
8
12
決定木の深さ
16
20
図 3.3: キーポイントマッチングの正解率 [%](実験 2)
表 3.3: キーポイントマッチングの正解率 [%](実験 2)
決定木の深さ
従来法
4
6
8
10
12
14
16
18
20
9.9 10.7 10.7 12.5 16.9 21.0 22.1 19.5 15.4
提案手法 “∗”1 個
6.2
9.3
17.5 25.0 32.2 36.2 37.0 37.4 35.3
提案手法 “∗”2 個
1.7
1.6
3.5
7.3
16.2 29.3 36.6 40.4 41.5
41
3.3. 実験結果
評価実験におけるキーポイント分類によるマッチング結果を図 3.4 に示す．図 3.4 より，
ノイズが含まれない画像に対しては従来法 · 提案手法ともに高精度なマッチングができて
いる．20% のノイズを付加した画像の場合，従来法 · 従来手法とも高精度にマッチングが
できているが，従来法はマッチングされるキーポイントの数が大きく減少し，画像ノイズ
によりキーポイントの分類に影響が出ていることがわかる．40% のノイズを付加した画
像の場合，従来法はマッチング率が大きく低下して誤った結果を表示している．しかし，
提案手法はこのようにノイズの割合が高い場合においても 90% 以上のマッチング率を維
持できている．これは，提案手法は，画像ノイズの影響で発生したビット反転に対してワ
イルドカードを導入することで，認識精度の低下を抑制してノイズに頑健なキーポイント
分類を実現できたといえる．
42
3.3. 実験結果
マッチング率 98%（47/48）
マッチング率 95%（42/44）
マッチング率 93%（28/30）
マッチング率 95%（36/38）
マッチング率 14%（2/14）
マッチング率 95%（21/22）
従来法
提案手法
図 3.4: キーポイントマッチング結果
43
おわりに
本論文では，ワイルドカードを用いた Random Ferns によるノイズに頑健な特徴表現法
を提案した．各章について以下にまとめる．
第 1 章では，画像局所特徴量を用いた従来のキーポイントマッチング手法について述べ
た．決定木によりキーポイントを学習する手法では，識別時に特徴量記述を必要とせず，
入力画像から抽出したパッチ画像を決定木に入力することで高速な処理が可能である．
第 2 章では，Random Ferns によるキーポイント分類とその問題点，提案手法のアイディ
アについて述べた．Random Ferns は，決定木における分岐ノードを階層ごとに統一する
ことで，キーポイントの特徴を “1” と “0” のバイナリで表現する．しかし，このようなバ
イナリを用いた特徴表現は，入力画像に画像ノイズが含まれていた場合，ビット反転が発
生し認識精度が低下する問題があった．そこで，本研究では Random Ferns から出力され
るバイナリコードに対して “1” と “0” を許容するワイルドカードを導入することで，ノイ
ズに頑健な特徴表現を行った．提案手法は，識別時に出力されたバイナリコードにワイル
ドカードを導入することで，ノイズの影響でビット反転したノードをマスキングすること
を目的とした．しかし，出力されたバイナリコードの情報だけでは，どのノードでビット
反転が発生したかはわからない．そのため，提案手法では各ノードに対して網羅的にワイ
ルドカードを適用してクラスごとの発生確率を算出する．これにより，ワイルドカードで
マスキングするノードの位置を自動的に選定し，パッチごとに異なるビット反転の位置を
考慮できる．
第 3 章では，提案手法の有効性を確認するために，ノイズを付加した画像に対してキー
ポイント分類による評価実験を行った．実験の結果，従来法である Random Ferns は入力
画像に含まれるノイズの割合が高くなるにつれて認識精度が大きく低下した．一方，提案
手法はノイズの割合が高い場合においても認識精度の低下を抑制し，画像ノイズに対して
頑健なキーポイントの分類を実現した．また，決定木の深さを変更した実験では，提案手
法は十分な深さの決定木を構築することで高い有効性を示すことを確認した．
44
今後は，遮蔽等の一般環境下で発生するノイズに対する提案手法の有効性を調査する予
定である．
45
謝 辞
本研究を行うにあたり，終始懇切なるご指導を頂きました中部大学工学部 藤吉弘亘教授
に謹んで感謝します．次に本研究を進めるにあたり，有意義な御助言，御指導頂いた中部
大学大学院工学研究科情報工学専攻 山内悠嗣氏，後藤雄飛氏に心から厚く御礼申し上げ
ます．最後に，本研究において，アドバイスや相談等に協力していただいた藤吉研究室の
皆様に感謝致します．
46
参考文献
[1] M. Ozuysal, M. Calonder, V. Lepetit, P. Fua, “Fast Keypoint Recognition using
Random Ferns” IEEE Transactions on Pattern Analysis and Machine Intelligence,
Vol. 32, Nr. 3, pp. 448 - 461, 2010.
[2] V. Lepetit and P. Fua, “Keypoint Recognition Using Randomized Trees”, Transactions on Pattern Analysis and Machine Intelligence, 28, 9, pp. 1465 - 1479, 2006.
[3] D. G. Lowe, “Object Recognition from Local Scale-Invariant Features”, International
Conference on Computer Vision, Corfu, Greece, pp. 1150 - 1157, 1999.
[4] D. G. Lowe, “Local Feature View Clustering for 3D Object Recognition”, IEEE
Conference on Computer Vision and Pattern Recognition, pp. 682 - 688, 2001.
[5] D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, Int. Journal of Computer Vision, 60, pp. 91 - 110, 2004.
[6] B. H. Grabner Michael, Grabner Helmut, “Fast Approximated SIFT”, Proc. of
ACCV, pp. 918 - 927, 2006.
[7] T. T. H. Bay and L. V. Gool, “SURF: Speeded-Up Robust Features”, In ECCV, pp.
404 - 417, 2006.
[8] C. Harris and M. Stephens, “A Combined Corner and Edge Detector”, Proc. of
Fourth Alvey Vision Conference, pp. 147 - 151, 1988.
[9] T. Lindeberg, “Scale-Space Theory: A Basic Tool for Analysing Structures at Different Scales”, Proc. of Journal of Applied Statistics, 21(2), pp. 224 - 270, 1994.
47
[10] C. Schmid amd P. Mohr, “Local Grayvalue Invariants for Image Retrieval”, Proc. of
IEEE Trans. Pattern Analysis and Machine Intelligence, 19, pp. 530 - 534, 1997.
[11] J. J. Koenderink, “The Structure of Images”, Proc. of Biological Cybernetics, 50,
pp. 363 - 370, 1984.
[12] P. L. H. Wang and T. Zhang, “Histgram Features-Based Fisher Linear Discriminant
for Face Detection”, Proc. of Asian Conference on Computer Vision, pp. 521 - 530,
2006.
[13] V. Lepetit and P. Fua, “Towards Recognizing Feature Points Using Classification
Trees”, Technical Report IC/2004/74, EPFL, 2004.
48
ワイルドカードを用いた Random Ferns によるノイズに頑健な特徴表現
竹ノ内 信寛
(中部大学工学部情報工学科)
2012 年 3 月