コンピュータビジョン特論

コンピュータビジョン特論
Bag-of-Keypoints
永橋知行
2007 年 8 月 07 日
1
はじめに
近年において一般物体認識で注目されている手法として，Bag-of-Keypoints [1] がある．Bagof-Keypoints では画像を局所特徴量の集合とみなすことで，各特徴量の位置情報を使用せずに
識別を行う．そのため，背景が異なる画像に対しても識別することが可能となる．
本稿では，Bags-of-Keypoints の手法の説明とそれらを応用した手法の紹介をする．
2
歴史的背景
Bag-of-Keypoints の考え方は，文書分類などに用いられる Bag-of-Word に基づいている．Bagof-Word は文書分類などの分野では古典的な手法として知られている．この手法では，文書を単
語の集合とみなし，単語の頻度によりその文章の特徴を表現する．これらの特徴を学習させるこ
とにより，テキストの分類を行う．Bag-of-Keypoints では文書の単語を局所特徴量 (keypoint,
visual work, visual term) とすることで，文書分類手法を画像に応用した手法である．
3
Bag-of-Keypoints
図 1 に，Bag-of-Keypints の流れを示す．Bag-of-Keypoints の手法としてさまざまな手法が提
案されている．
3.1
特徴量抽出の流れ
Bag-of-Keypoints の特徴量抽出の流れを以下に示す．
• 局所特徴量の抽出
• 局所特徴量のベクトル量子化
1
FLAB Work Document Aug 7, 2007
2
図 1: Bag-of-Keypoints の流れ
• クラスタの頻度を計算
はじめに，画像中から局所特徴量として SIFT 特徴量の抽出を行う．次に抽出した SIFT 特徴
量をベクトル量子化する．このとき，ベクトル量子化に用いるコードブックは学習データから
作成する．最後に，ベクトル量子化された SIFT 特徴量から各クラスタの頻度（ベクトル量子
化ヒストグラム）を作成する．
3.1.1
局所特徴量の抽出
局所特徴量の抽出には SIFT を用いる．このとき，SIFT 特徴量の記述範囲を決定する必要があ
る．この SIFT 特徴量の記述範囲の決定法として，主に 2 つの種類に分けられる．
• Interest point detector
画像中から特徴点とスケールを検出し，その範囲から SIFT 特徴量を記述する．Quelhas
ら [3] は，SIFT [2] と同様に DoG 極値を利用して特徴点の検出を行っている．Csurka ら
[1] は，Aﬃne Invariant keypoint [4] を利用し，得られた領域をアフィン変換により正規
化して SIFT 特徴量の抽出を行っている（図 2）.
FLAB Work Document Aug 7, 2007
3
図 2: Aﬃne Invariant keypoint を用いた SIFT 特徴量の抽出：(a)Aﬃne Invariant keypoint (b)
正規化された領域 (c) 8 方向の輝度勾配強度 (文献 [1] より)
• Regular grid この方法では，画像を等間隔に分割をし，スケールをランダムに決定して
SIFT 特徴量を記述している．Fei-Fei ら [5] はグリッドに分割して SIFT 特徴量を記述す
ることにより風景画像など 13 クラスに対しての画像分類をしている．自然風景シーンで
はエッジやコーナーといった特徴点の抽出が困難であるため，グリッドに分割すること
で，DoG 極値を用いるよりも高精度に分類できていることが述べられている．
表 1: 各手法での識別結果 [%] (文献 [5] より)
Descriptor
Grid Random DoG
11x11 pixel
128-dim SIFT
3.2
64.0
65.2
47.5
60.7
N/A
52.5
識別器
Bag-of-Keypoints では，ベクトル量子化ヒストグラムを識別器の入力とする．このとき用いら
れる識別器として，
• SVM
• Naive Bayes
• pLSA
• LDA
などが使われている．特に，pLSA と LDA は文書分類である Bag-of-Word で用いられている
手法である．以下に，各手法の概要を述べる．
3.2.1
Naive Bayes
Naive Bayes では，各特徴量間の相関はないと仮定し，各特徴量ごとにカテゴリである確率を
計算することにより全体のカテゴリの確率を計算する手法である．画像から得られる局所特徴
量を w = {w1 , w2 , . . . , wn }, カテゴリを c とするとき，Naive Bays では以下の式によりカテゴ
FLAB Work Document Aug 7, 2007
4
リ c∗ を決定する．
c∗ = arg max p(c|w) ∝ p(c)p(w|c) = p(c)
c
3.2.2
p(wn |c)
(1)
n
pLSA (Probabilistic Latent Semantic Analysis)
pLSA (Probabilistic Latent Semantic Analysis) [6] とは，文書と単語など，離散 2 変数の計数
データの生成モデルである．文書を d ∈ D = {d1 , . . . , dN }, 語を w ∈ W = {w1 , . . . , wM }, 潜
在変数の話題を z ∈ Z = {z1 , . . . , zK } としたとき，文書と単語の生成モデルを以下の式で定義
する．
p(d, w) = p(d)
p(w|z)p(z|d)
(2)
z∈Z
これは，文書と語について対象に定義することができる．
p(d, w) =
p(z)p(d|z)p(z|w)
(3)
z∈Z
LDA はこの pLSA を改良した生成モデルである．
Sivic ら [7] は，この pLSA にスケールと位置情報を加えて識別精度を向上させる Translation
and Scale invariant pLSA (TSI-pLSA) を提案している．
3.3
そのほかの応用例
Agarwal ら [8] は，画像中の visual word のヒストグラムを局所領域で作成し上位階層の特徴
量を計算し，これを繰り返すことで階層的な特徴量の記述を行う Hyperfeature を提案してい
る．また，Grauman ら [9] は Pyramid Match Kernels という２つの bag 同士の部分マッチン
グに基づいて類似度を計算するカーネル関数を提案している．
4
おわりに
Bags-of-Keypoints の手法の説明とそれらを応用した手法の紹介を行った．
参考文献
[1] G. Csurka, C.R. Dance, L. Fan, and C. Bray, “Visual categorization with bags of keypoints.”，
, Profc. of ECCV Workshop on Statistical Learning in Computer Vision, pp. 1-22, 2004.
[2] D. G. Lowe, “Distinctive image features from scale-invariant keypoints”, International
Journal of Computer Vision, 60(2), pp. 91-110, 2004.
FLAB Work Document Aug 7, 2007
5
[3] P. Quelhas, F. Monay, J-M. Odobez, D. Gatica-Perez, T. Tuytelaars, and L. Van-Gool,
“Modeling Scenes with Local Descriptors and Latent Aspects”, In Proceedings ICCV,
2005.
[4] K. Mikolajczyk, and C. Schmid. “An Aﬃne Invariant Interest Point Detector”, ECCV,
pp. 128-142, 2001.
[5] L. Fei-Fei, and P. Perona, “A Bayesian Hierarchical Model for Learning Natural Scene
Categories”, Proc. IEEE CVPR, vol. 2, pp. 524 - 531, 2005.
[6] T. Hofmann “Unsupervised Learning by Probabilistic Latent Semantic Analysis”, Machine Learning, vol. 43, pp. 177-196, 2001.
[7] J. Sivic, and A. Zisserman, “Video Google: A Text Retrieval Approach to Object Matching in Videos”, Proc. of ICCV. vol. 2, pp. 1470-1477, 2003.
[8] A. Agarwal, and B. Triggs, “Hyperfeatures – Multilevel Local Coding for Visual Recognition”, Proc, 9th ECCV, vol. 1, pp 30-43, 2006.
[9] K. Grauman, and T. Darrell, “Pyramid Match Kernels: Discriminative Classiﬁcatin with
Sets of Image Feature”, Proc. of ECCV Workshop on Statistical Leaning in Computer
Vision, pp. 1458-1465, 2005.

Download Report