特徴点選択とペア化によるNaive-Bayes Nearest-Neighbor手法の改良
電気通信大学情報理工学専攻
秋山 瑞樹
柳井 啓司

背景
• BoF(Bag of Features)クマ• 量子化を行う• SVMやBoostingなどの機械学習により量子化誤差を補う• 近年は、量子化誤差を減らす手法も提案されている• 特徴点マッチング• 量子化を行わない• 特定物体認識でのみ使われてきた• カテゴリー分布の広がりに対応できないため

Naive-Bayes Nearest-Neighbor(NBNN)[Oren Boiman et al. 2008]
特徴点マッチングでありながら、カテゴリー認識が可能

目的• 特徴点マッチングベース手法の認識精度向上を目指す• NBNNの改良を行う

1. SaliencyMapによる特徴の重み付け
2. mi-SVMによる特徴の重み付け
3. 特徴のペア化

関連研究：NBNN• Naive-Bayes Nearest-Neighbor(NBNN) [Oren Boiman et al. 2008]
𝑐128次元[0.54,0.43, …, 0.32] :𝑑1[0.11,0.06, …, 0.70] :𝑑2⋮[0.38,0.17, …, 0.01] :𝑑𝑛−1[0.62,0.87, …, 0.41] :𝑑𝑛
局所特徴(SIFT)

 局所特徴をそのまま使う𝑛

𝐶 = 𝑎𝑟𝑔 min𝑐𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 )𝑖=12𝑑11⋮𝑐1𝑑𝑚𝑎𝑥⋮𝑑1 − 𝑁𝑁1 (𝑑1 ) 2 +𝑑2 − 𝑁𝑁1 (𝑑2 ) 2 +⋯ = 𝐷𝑖𝑠𝑡𝐶1𝑐

𝑑1𝑡
𝐷𝑖𝑠𝑡𝐶𝑡⋮𝑐𝑡
𝑑𝑚𝑎𝑥

データベースmin 𝐷𝑖𝑠𝑡𝐶𝑐となるC が認識結果

Aeroplane, car , bike…

𝐶 ∶ テスト画像の推定されたクラス
𝑛 ∶ テスト画像の特徴数
𝑑𝑖 ∶ テスト画像の特徴量
𝑁𝑁𝑐 (𝑑𝑖 ): クラス𝑐に属する𝑑𝑖 の最近傍特徴量

関連研究：NBNN
 ノンパラメトリックな“Image to Class”の認識Image to Image(NN法)Image to Class(NBNN)
Image to Class距離15.3
Aeroplane

最短距離のクラス
5.3

テスト画像

認識結果

car
7.3

最短距離の画像

motorbike

データベース
局所特徴の集合car関連研究• Towards Optimal Naïve Bayes Nearest Neighbor [Regis Behmo
et al. CVPR 2010]• NBNNにパラメータを導入し、各クラス毎の異なる分布を正規化する距離計算を行えるようなパラメータを学習する。
𝑛𝐶 = 𝑎𝑟𝑔 min 𝛼 𝑐𝑐

𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 ) 2 + 𝛽𝑐
𝑖=1

関連研究
• Image-To-Class Distance Metric Learning for ImageClassification. [Zhengxiang Wang et al. CVPR 2010]• NBNNの距離計算をマハラノビス距離で行うことで精度向上
𝑛𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 ) 𝑇 𝑀𝑐 𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 )𝐶 = 𝑎𝑟𝑔 min𝑐

𝑖=1

• Multi-label learning by image-to-class distance for scene

classication and image annotation.[Zhengxiang Wang et al. ACM 2010]• データベース特徴にマージン最大化によって重みをつける
𝑛𝐶 = 𝑎𝑟𝑔 min𝑐

𝑊𝑁𝑁𝑐 (𝑑𝑖) ・𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 )
𝑖=12

関連研究
• The nbnn kernel.[T.Tuytelaars et al. ICCV 2011]• NBNNをカーネル化することで、SVMを用いる学習ベース手法と組み合わせることを可能にした。
• 本手法の位置付け
パラメータ 距離空間 重み付け カーネル化 ペア化の変化
学習
Boiman (CVPR2008)

×××××

Behmo (ICCV2010)○××××Wang(ECCV2010)○○×××Wang(ACM2010)○×○××

Tuytelaars(ICCV2011)

×××○

×

提案手法

○×○

×○

提案手法概要
テスト画像

学習画像

画像特徴量の抽出
データベース化

特徴のペア化mi-SVM

特徴の重み付け

SIFT

SaliencyMap

クラス認識

提案手法詳細• 画像特徴量の抽出• SIFT特徴量.

128 次元特徴ベクトルで表現し、回転・スケール・変化・照明変化に対して耐性のある特徴である

提案手法詳細• 特徴の重み付け
SaliencyMapによる重み付け.
画像の顕著性を考慮することで、物体から得られた特徴に対する重要度を上げる。各ピクセルごとに評価値が得られる
1.

Saliency Map
1. ガウシアンピラミッドによる9スケール画像
2. 輝度、色相、方向成分の抽出

3. 各成分ごとにスケール間差分の計算

輝度成分

色相成分

スケール画像方向成分

4. 各成分の統合
Saliency Map

Saliency Map
SaliencyMap 評価値[0.04, 0.83, …, 0.03, 0.01][0.11, 0.96, …, 0.15, 0.10]⋮[0.18, 0.37, …, 0.22, 0.24][0.22, 0.17, …, 0.31, 0.41]

データベース特徴
SIFT特徴量

SaliencyMap重み[0.54,0.43, …, 0.32][0.11,0.16, …, 0.12]⋮[0.38,0.17, …, 0.01][0.62,0.87, …, 0.41]

0.23
0.67
0.89
0.78

対応した座標の局所特徴に対する重みとする

提案手法詳細• 特徴の重み付け
mi-SVMによる重み付け.
MIL(Multiple Instance Learning)手法の一種で、あるクラスのデータベースだけに現れる画像特徴と、他のクラスにも現れる画像特徴を識別することができる。
2.

評価値

データベース[0.54,0.43, …, 0.32][0.11,0.06, …, 0.70]⋮[0.38,0.17, …, 0.01][0.62,0.87, …, 0.41]

MIL[ 1.5 ][-1.2 ]⋮
[ 0.5 ][-0.2 ]

mi-SVM
Positive Bag(ex. 車クラス)

Positive Bagの更新

Negative Bag(ex. 車クラス以外)

SVM
２つのBagから学習

ポジティブ画像にだけ現れる重要な特徴に重み付けmi-SVM
Positive データセット(ex. 車クラス)[0.54,0.43, …, 0.32][0.11,0.06, …, 0.70]⋮[0.38,0.17, …, 0.01][0.62,0.87, …, 0.41]

Negative データセット(ex. 車クラス以外)[0.04,0.35, …, 0.54][0.11,0.37, …, 0.53]⋮[0.10,0.85, …, 0.29][0.21,0.43, …, 0.94]

mi-SVM

Positive データセット
mi-SVM重み(ex. 車クラス)[0.54,0.43, …, 0.32] 0.98
[0.11,0.06, …, 0.70] -1.56⋮[0.38,0.17, …, 0.01] 1.78
[0.62,0.87, …, 0.41] -0.67

提案手法詳細• 特徴のペア化[𝑥1 , 𝑦1 , 𝑥2 , 𝑦2 , 𝑓1 , 𝑓2 ]• 隣接特徴5個までをペアにする。
• 同じスケール内で隣接特徴を選択する• 特徴数を増やすことができる

評価実験
1. Caltech101クラスから10クラスを選択して実験• 各クラス学習画像15枚、テスト画像15枚• 3 fold - crossvalidationで評価• 8 ピクセルグリッド、5スケールによりSIFT特徴を抽出• クラスあたりの特徴数 30,000(ペア化なし)、150,000(ペア化あり)barrelbass

car sidecougar bodygareldheadphonejoshua tree

laptopsaxphonewatch評価実験
2. 独自に作成した25クラスデータセット• Webから収集した画像で構築されているので、データセットにノイズ画像が含まれる。
• 各クラス学習画像1050枚、テスト画像50枚• DoG(difference of gaussian) によりSIFT特徴を抽出• クラスあたりの特徴数 600,000• 評価方法正しく分類されたテスト画像数
分類率 =テスト画像総数

評価実験(10クラス分類)• ベースライン• NBNN[Boiman 2008]
𝑛𝐶 = 𝑎𝑟𝑔 min𝑐𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 )𝑖=12+ 𝛼 𝑙𝑑𝑖 − 𝑙𝑁𝑁𝑐(𝑑𝑖)2𝑙𝑥 ∶ xの座標(x,y)• α を変化させて一番精度がよかった値をベースラインとする• 平均分類率 0.673• 提案手法に対しても、αを変化させて実験を行った。

実験結果(10クラス分類)• Saliency Mapによる重み付けの結果
𝑛exp(−𝑤𝑆𝑎𝑙𝑖𝑒𝑛𝑐𝑦𝑀𝑎𝑝 /𝛽) 𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 ) 2𝐶 = 𝑎𝑟𝑔 min
𝑐𝑖=1• 各クロスバリデーションでβの値を変化させて実験を行った平均の分類率
0.695

平均分類率 0.689

0.690.685
0.680.675
0.670.665

ベースライン

SaliencyMap

実験結果(10クラス分類)• mi-SVMによる重み付けの結果
𝑛exp(−𝑤𝑚𝑖−𝑆𝑉𝑀 /𝛾) 𝑑𝑖 − 𝑁𝑁𝑐 (𝑑𝑖 ) 2

𝐶 = 𝑎𝑟𝑔 min
𝑐𝑖=1• 各クロスバリデーションでγの値を変化させて実験を行った平均の分類率
0.695

平均分類率 0.691

0.690.685

0.680.675
0.670.665
0.66

ベースライン

mi-SVM

実験結果(10クラス分類)• 2つの重み付けを組み合わせた結果
平均分類率 0.695

0.70.695
0.690.685

0.680.675
0.670.665
0.66

ベースライン

SaliencyMap

mi-SVMSaliencyMap+mi-SVM

実験結果• 特徴量ペア化の結果
0.705

ペア化のみ 0.696

0.7

ペアなし

0.695

ペアあり

0.690.685
0.68
0.675

ペアあり+SaliencyMap

ベースライン 0.673

ペアあり+mi-SVM

0.67
0.665
0.66

ペアあり
+SaliencyMap+mi-SVM

実験結果(25クラス分類)• ベースライン• BoF(codebook size = 1000)+サポートベクターマシン(線形カーネル)• BoF(codebook size = 1000)+サポートベクターマシン(χ^2カーネル)• NBNN[Boiman 2008]• 全てにおいて座標情報(α)は利用しない• またクラスあたりの特徴数が多いので、ペア化は利用しない

実験結果(25クラス分類)
0.6

0.5

0.4

NBNN
0.477
BoF+SVM(χ^2)
0.362

NBNN+SaliencyMap+mi-SVM
0.482
BoF+SVM(線形カーネル)
BoF+SVM(χ^2カーネル)

0.3

0.2

NBNN

BoF+SVM(線形)0.171

NBNN+SaliencyMap

NBNN+mi-SVM

0.1
NBNN+SaliencyMap+mi-SVM

0まとめ• NBNN手法の改良• SaliencyMap、mi-SVMによる重み付け• 特徴のペア化• 評価実験

10クラス分類

NBNN

提案手法

分類率

0.673

0.695

25クラス分類

SVM(χ^2)

NBNN

提案手法

分類率

0.362

0.477

0.482

• データセット• 関連研究ではノイズが無い綺麗なデータセットでしか、実験をしていないが、NBNN手法はノイズが有る信頼性の低いデータセットに対して、BoFベース手法を上回る精度が期待できることが分かった。

今後の課題• mi-SVMについて• 学習時間の関係から学習特徴数を減らした。
• ポジティブ5000, ネガティブ30000しか利用していない。

• より大規模かつ高速な重み付けが可能になるMIL手法を検討する必要がある。
• 有効な利用方法• 信頼性の低いデータセットを利用するシーン• Web動画、Web画像の自動ランキングなど

ご清聴ありがとうございましたCaltech101における比較結果

Caltech101

Caltech 5クラス

Boiman(CVPR2008)

65%

Boiman (CVPR2008)73.1%

Wang(ECCV2010)48%

Wang(ECCV2010)

89.8%

Tuytelaars(ICCV2011)

62.7%

BoW + χ2-SVM(Wang(ECCV2010))

89.1%