Bag of Visual Words

Bag of visual words (BoVW)は、一般物体認識において現在最も広く普及している画像特徴表現で、画像中の多数の局所特徴をベクトル量子化しヒストグラムにしたものです。最近はOpenCVなどのツールの普及により使いやすくなってきましたが、実際に使ってみようとすると細かい部分でつまづくことも多いのではないでしょうか。最新の研究では認識精度が飛躍的に向上していますが、局所特徴抽出などの細かいノウハウの蓄積による部分もかなり大きいと思います。
（そのような部分は学術的な新規性は低いため、論文ではさらりと書いてあることが多いのですが）

以下、自分が把握しているノウハウをまとめてみたいと思います。ただし、私自身の経験や主観に基づくものであり、絶対的なものではないことにご注意ください。
また、BoVWについて基本的な知識があることを前提としています。

画像サイズ

まず、そもそも画像はどれくらいの大きさ（解像度）がいるのか、経験がないと迷うところだと思います。
これに関しては扱うタスクの性質次第としか言いようがないですが、一般的にはそれほど大きな解像度は必要ありません。
例えば、現在一般物体認識のベンチマークとして用いられているデータセットでは、一辺200〜300ピクセル程度の大きさに揃えれば十分です。
画像の細かい構造を見たい場合はもう少し大きくてもいですが、それでもVGA程度の大きさがあれば問題ないと思います。

局所特徴量

局所特徴としてはSIFTが定番ですが、他にもSURF、HOG、LBPなどさまざまなものが使われています。BoVWにすることが前提の場合、輝度勾配ベースの局所特徴であればそれほど性能差はないのではないかと思います。SURFは計算も比較的速く、使いやすいのでよく利用しています。
これに限らず、color descriptor、self similarity descriptorなどいろいろな選択肢があります。

  • Koen E. A. van de Sande, Theo Gevers and Cees G. M. Snoek, Evaluating Color Descriptors for Object and Scene Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 32 (9), pages 1582-1596, 2010.
  • Eli Shechtman and Michal Irani, Matching Local Self-Similarities across Images and Videos, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2007)

局所特徴のサンプリング方法

BoVWにする場合、ここが非常に重要な部分です。最も大事なのは、dense samplingと呼ばれる方法で特徴抽出を行うことです。
もともとSIFTなどでは、difference of Gaussianなどのフィルタにより視覚的顕著性のある特徴点を抽出し、オリエンテーションとスケールを正規化した局所特徴を記述します。しかし、この方法でとられた局所特徴をBoVWにすると性能がかなり悪いことが経験的に知られています。これは、視覚的に顕著な点が必ずしも識別に有効であるとは限らないためであると考えられます。また、一枚の画像から得られる局所特徴数が少なくなる傾向にあるため、統計的な安定性の観点からも問題となります。

  • Eric Nowak, Frédéric Jurie, and Bill Triggs, Sampling Strategies for Bag-of-Features Image Classification, ECCV 2006.
  • Li Fei-Fei, Pietro Perona, A Bayesian Hierarchical Model for Learning Natural Scene Categories, CVPR 2005.

Dense samplingでは、固定のグリッドで特徴抽出を行う点を定め、全ての点でオリエンテーション、スケールを固定した局所特徴をとります。やること自体は非常にシンプルですが、大事なポイントが2つあります。

  1. グリッドの幅（隣り合う特徴点同士の距離）はできるだけ狭いほうがよいです。極端に言えば、全てのピクセルで特徴をとってもよいです。最低でも10ピクセル間隔、できれば5ピクセル、3ピクセル間隔くらいで抽出するといい性能が出ます。もちろん、サンプリングを密にするほど計算コストは大きく増えるので、現実的なところで設定する必要はあります。
  2. 局所特徴記述子のスケール（抽出窓の大きさ）は、一般的には、20〜30ピクセル程度にすることが多いようです。さらに、同じ点から異なる複数のスケールで特徴をとると性能が向上することが知られています。例えば、16ピクセル、24ピクセル、32ピクセル、などのスケールの特徴を同時にとります。このように、スケール方向の軸についても密にサンプリングを行うことで、画像中の物体の大きさの変化に頑健になります。また、画像あたりの局所特徴数を水増しする効果もあると思います。以下の最新の研究では、なんと8スケールからとっています。

Josip Krapac, Jakob Verbeek, Frédéric Jurie, Modeling Spatial Layout with Fisher Vectors for Image Categorization, International Conference on Computer Vision, 2011

Visual wordの作成（クラスタリング）

ここも経験がないと迷うところだと思います。直感的には、多数の局所特徴をクラスタリングするのは大変な作業に思えますが、文献を見てもあまり丁寧に記述されていない場合が多いです。(k-meansで1000個のvisual wordを作成しました、以上。のような感じ）
実は最近の研究では、クラスタリングの過程そのものはあまり重要ではなく、むしろそのあとのコーディング（ヒストグラム作成に相当する部分）が性能を決定する上でクリティカルであることが示されています。

  • Eric Nowak, Frédéric Jurie, and Bill Triggs, Sampling Strategies for Bag-of-Features Image Classification, ECCV 2006.
  • Adam Coates, Andrew Ng, The Importance of Encoding Versus Training with Sparse Coding and Vector Quantization, ICML 2011.

これは経験的にも知られており、多くの場合クラスタリングはかなり適当にやられています*1。
クラスタリングに用いるサンプルは、多くの場合数十万点から百万点程度で十分です。一枚の画像から数千点程度の局所特徴を抽出することを考えるとかなり少なく感じますね。クラスタリング手法はk-means法が定番ですが、これも真面目に収束を待つと大変なので、適当な回数反復計算を行って打ち切ればよいと思います。

ただし、visual word（セントロイド）の数は十分大きくとる必要があります。基本的に、大きければ大きいほど性能は上がります。一般的には、数千から数万くらいの数にとる場合が多いです。

ヒストグラム作成（コーディング）

ここまでくれば、あとはやることはシンプルです。画像中の各局所特徴について一番近いvisual wordを求め、投票してヒストグラムを作るだけです。基本は全てのvisual wordについての線形探索になりますが、visual wordの数が大きいと大変なので近似最近傍法などを入れてもよいでしょう。これについてはあまり詳しくないので省きます。

適切なカーネルの利用

無事にBoVWがとれれば後は適当な識別器に放り込むだけですが、線形識別器、あるいは線形カーネルはそのまま利用すると極端に性能が落ちます。ここでは、ヒストグラムインタセクションカーネル、カイ二乗カーネルなどを使うべきです。（本当にものすごく性能が変わります）
ただし、カーネル法を使うとサンプル数に対するスケーラビリティが落ちるため、大規模なデータからの学習が困難になります。そのような場合はexplicit embeddingと呼ばれるアプローチで、元のBoVWを高次元の空間に移すと認識性能を損なわずに線形識別器を適用することができます。この点については、以下のPFIさんの解説が素晴らしいです。

線形識別器でカーネルトリックを使う方法
http://research.preferred.jp/2011/09/kernel-trick/

なお、どうしても元のBoVWに線形識別器を適用したい場合、単純に各要素の平方根をとるだけでもBhattacharyyaカーネルと等価になるため、多少ましになるのでお薦めです。

  • Subhransu Maji, Alexander C. Berg, Max-Margin Additive Models for Detection, ICCV 2009.
  • Andrea Vedaldi, Andrew Zisserman, Efficient Additive Kernels via Explicit Feature Maps, CVPR 2010.

認識性能と計算コストのトレードオフ

Dense samplingで抽出する特徴を密にしたり、visual wordの数を増やせば当然計算量は増えます。いかに性能を落とさず計算コストを下げるかについては、以下の文献が参考になると思います。

J.R.R. Uijlings, A.W.M. Smeulders and R.J.H. Scha, Real-time Visual Concept Classification, IEEE Transactions on Multimedia, 99, 2010.

この論文では、さまざまな局所特徴記述子や次元圧縮手法、近似最近傍手法について調査がされています。また、例えばSIFTは通常4x4の小グリッドからヒストグラムを抽出しますが、これを2x2にしても性能がほとんど変わらないというような細かい実装についても報告がされています。

その他のテクニック

認識性能を上げるための工夫として、まず元になる学習サンプルを水増しする手が考えられます。単純に、左右を反転させた画像を加えるだけでも性能がかなり向上することが知られています。

K. Chatfield, V. Lempitsky, A. Vedaldi, A. Zisserman, The devil is in the details: an evaluation of recent feature encoding methods, British Machine Vision Conference, 2011

これが許されるかはタスクの性質によりますが、場合によってはさらに人工的に変形を加えた画像を加えることも可能であるとおもいます。
（ただし、データセットに対する認識スコアを競うベンチマーキングでこれを行うと反則扱いされてしまうかも知れないので注意が必要です）

また、同じ局所特徴記述子であっても、通常のBoVWに加えエッジ画像から生成した別のBoVWを併用することで性能向上が行えることが報告されています。

Jianxin Wu, James M. Rehg, Beyond the Euclidean distance: Creating effective visual codebooks using the histogram intersection kernel, ICCV 2009.

もともとSIFTやSURFなどの局所特徴は輝度勾配ベースなので、エッジ画像からとってもあまり意味的な違いはない気がするのですが、少なくとも実験的には有効なようです。

*1:上記の文献では、ランダムに選んだvisual wordでもそれほど性能が低下しないことが示されています