新型BoVW
いよいよ、従来のBoVWに変わる新しい特徴表現方法を見ていきます。これらの新しい特徴は直接線形手法に適用できるように設計されており、線形SVMと合わせて用いられることが多いです。
前置き
一枚の画像からBoVW（或いは、それに類する枠組み）によって特徴ベクトルを得るまでは、非常に大雑把に分けると次の二つの過程に分かれます。
- 画像から多数（数千〜数万）の局所特徴を抽出
- 得られた大量の局所特徴の情報を利用し、最終的なアウトプットである一本の特徴ベクトルを生成
どちらも大事なプロセスですが、今回考えるのは2のほうです。つまり、局所特徴はなんらかの方法でとってあるとして、その後どうするかという部分です。1の方は今回は触れませんが、SIFT + dense sampling などが多いようです（参考: Bag of Visual Words - n_hidekeyの日記）。
プロセス2で重要なのは、画像中の局所特徴分布が持つ統計的情報をいかにしてうまく表現するか、という点につきます。ただし、単に情報を拾い集めるだけでなく、線形識別器でうまく扱えるように特徴ベクトル化しなければなりません。現在、大きく分けると二つの流派がありますが、基本的にはどちらもこの考え方で説明できると思います。
(A) Sparse coding & Max pooling
Visual wordsを用いた特徴ベクトルの作成の際、(1)スパースネスを導入し、一つの局所特徴を複数wordへ割り当てる (Sparse coding), (2)各visual wordについて、アサインされた局所特徴のスコアの最大値を利用（max pooling）という手順をとることで識別性能大きく向上することが分かっており、注目されています。これらは同時に使われることが多いですが、それぞれ違うプロセスを担う概念であることに注意が必要です。
このアプローチを最初に提案したのは、NEC LabsとUIUCの共同チーム(NEC-UIUC)で、2009年のPASCAL VOCで一気に有名になったようです。それ以前の一般物体認識は進歩が停滞しており、形状特徴・カラー特徴など複数の特徴量を用いmultiple kernel learningで学習する方法が一般的でした。しかしこの年のNEC-UIUCがとった手法では、特徴はグレイスケール画像からとったSIFTのみで、識別器も単純な線形SVMでした。にも関わらず大差で圧勝してしまい、世界中の研究者の度肝を抜いたのです。
< Sparse coding >
Sparse coding の有効性が最初に示されたのは以下の論文です。
Jianchao Yang, Kai Yu, Yihong Gong, Thomas Huang,
Linear Spatial Pyramid Matching using Sparse Coding for Image Classification, CVPR 2009.
この時点では、なぜsparse codingが有効なのか明らかではありませんでしたが、著者らの次の論文で理由付けがなされ、より直接的に定式化されました。
Jingjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas Huang, and Yihong Gong
Learning Locality-constrained Linear Coding for Image Classification, CVPR 2010.
スパースネスの導入により、局所特徴分布の局所的*1な構造を抽出しやすくなる点が本質らしいです。もともと、一つの局所特徴を複数のvisual wordに割り当てるアプローチはsoft assignmentとしてよく知られていましたが、ここが大きな違いになっています。
（ナイーブに複数割り当てを行うだけでは、遠く離れたvisual wordが用いられる可能性もあるため）
Sparse codingは精力的に研究されており、さまざまな拡張が提案されています。例えば次の論文では、Laplacian matrixを用いた正則化を追加し精度向上を行っています。
Shenghua Gao, Ivor Wai-Hung Tsang, Liang-Tien Chia, and Peilin Zhao,
Local Features Are Not Lonely; Laplacian Sparse Coding for Image Classification, CVPR 2010
なお、Sparse codingはもちろんvisual wordsの作成（クラスタリング）の際にも導入でき、上記の論文でも実際にそうしています。しかし、その後の報告で、visual wordsの作成で頑張ってもそれほど効果はないことが示されています。これも面白いところです。
Adam Coates, Andrew Ng,
The Importance of Encoding Versus Training with Sparse Coding and Vector Quantization, ICML 2011.
< Max pooling >
さて、もう一つのポイントであるmax poolingについても説明します。これは上でも述べたとおり、各visual wordについて割り当てられた局所特徴のスコアの最大値をとり特徴ベクトルとするものです。これに対して従来のBoVW（ヒストグラム）はスコアの平均値をとっていると解釈できるので、この文脈ではaverage poolingと呼ばれます。
Max poolingで得られる特徴ベクトルは識別性能が高いことも大きな魅力ですが、最も重要なのは線形カーネルと相性がいいことです。これは線形識別器を直接適用可能であることを意味しており、従来のBoVWとは質的に異なる点です。
次の論文では、さまざまなコーディング・プーリング方法の組み合わせを調査しています。実験結果を見れば、max poolingの効果は一目瞭然です。
Y-Lan Boureau, Francis Bach, Yann LeCun, and Jean Ponce,
Learning Mid-Level Features For Recognition, CVPR 2010.
なぜmax poolingがこれほど優れた結果を示すのか、理論的な分析もなされています。
Y-Lan Boureau, Jean Ponce, Yann LeCun,
A Theoretical Analysis of Feature Pooling in Visual Recognition, ICML 2010.
BoVWのような非常にスパースな特徴（ほとんど要素が0）の場合、max poolingがaverage poolingよりも高い分離性能を持つことが示唆されています。また、より多くの局所特徴をプーリングすることが必ずしもよりよい結果にはつながらないという、一見直感に反する主張もされています。
(B) 高次統計量の利用
従来のBoVWは、各visual wordに帰属する局所特徴の数を単純にカウントするものです。しかしながら、帰属する局所特徴のなす分布の形状についての情報は考慮されないため、全く形の違う分布でも数が同じなら同じ特徴値となってしまうことが分かります。これを防ぐためにはvisual wordの数を増やしより細かく量子化することも考えられますが、計算コストが大きく増大します。
別なアプローチとして、局所特徴のより高次な統計量をとっていくアプローチがあります。例えば、1次モーメント（平均）、2次モーメント（分散）などを特徴ベクトルに加えます。このような方法だと、それほどvisual wordの数を増やさなくても分布情報をとらえることができ、計算コストの面でも有利です。ただし、適当にモーメントを列挙すればいいわけではなく、最終的な特徴ベクトルの計量（内積）を考えて設計する必要があります。
ここではその具体的な手法をいくつか紹介します。
< VLAD >
H. Jégou, M. Douze, C. Schmid, and P. Pérez,
Aggregating local descriptors into a compact image representation, CVPR 2010.
このアプローチでは一番分かりやすい手法です。各visual wordに帰属する局所特徴について、そのvisual wordを原点にとった場合の平均値をとり、これを全て並べて特徴ベクトルとします。従って、visual wordの数をN、局所特徴の次元数をdとした場合、最終的な特徴ベクトルの次元数はN×dとなります。
< Super vector coding >
Xi Zhou, Kai Yu, Tong Zhang, and Thomas S. Huang
Image Classi cation using Super-Vector Coding of Local Image Descriptors, ECCV 2010
これもやっていることはかなり似ており、各visual wordに帰属する局所特徴ついて、カウント（従来のBoVW)と平均値を並べたものを特徴ベクトルにします。こちらの特徴次元数は(N+1)×dとなります。また、その内積が分布間のBhattacharyyaライクなカーネルと等価になることが示されています。
ただし、特徴ベクトルのカウント部分と平均値部分のバランスをとる重みパラメータを与える必要があります。
< Fisher vector >
現在一番勢いのある手法です。Xerox Research Center Europe の研究者が開発しました。
この手法では、局所特徴の平均に加え分散（共分散除く）も用います。従って、特徴ベクトルの次元数は2Ndになります。このように質の異なる統計量を用いると特徴ベクトルの設計が難しくなりますが、この手法では情報幾何の応用の一つであるFisher kernelと呼ばれる技術を用いています。詳しい説明は省きますが、ざっくり言うとFisher vectorは局所特徴分布の生成モデル*2からのずれを表現したものになっています。特徴ベクトルはフィッシャー情報行列の逆行列によって適切にスケーリングされるため、近似的ですが線形空間として扱うことができます。前述のVLADはFisher vectorを簡略化したものと解釈することもできます。
最初に登場したのは実は結構前で、2007年です。
Florent Perronnin and Christopher Dance,
Fisher Kernels on Visual Vocabularies for Image Categorization, CVPR 2007.
2010年に発表された続報でFisher vectorの改良（L2正規化など）が示され、大きく性能が向上しました。大規模な問題に適用できることも実証され、注目を集めました。
Florent Perronnin, Jorge Sánchez , and Thomas Mensink,
Improving the Fisher Kernel for Large-Scale Image Classification, ECCV 2010.
Florent Perronnin, Yan Liu, Jorge Sánchez, Herve Poirier,
Large-scale image retrieval with compressed Fisher vectors, CVPR 2010.
< VLAT >
David Picard and Philippe-Henri Gosselin,
Improving Image Similarity With Vectors of Locally Aggregated Tensors, ICIP 2011.
VLADを拡張したもので、平均・分散にとどまらずさらに高次のモーメントを列挙する一般的な定式化になっています。ただし、特徴ベクトルの次元数が爆発してしまうので、実用上は2次モーメントまでにとどめるようです（それでも、共分散まで考慮するので次元数はかなり大きくなります）。
特徴ベクトルの内積は、ガウシアンカーネルによるkernels on bagsを近似することが示されています。
なお、このように局所特徴量の高次モーメントを特徴ベクトルにするアプローチは、有名な高次局所自己相関特徴（HLAC特徴）と同じです。もちろん、最初にクラスタリングを行うなどの違いはありますが、本質的な差ではないと思います。現在の最先端の手法と同じ考え方が、1980年代に既に提案されていることは非常に興味深いですね。
その他
< 性能比較 >
「で、結局どれが一番いいの？」という感じですが、まだどの手法も発展中なので今のところよく分かりません。いろんな手法を第三者が追試・比較した論文として、次のものがあります。
Ken Chatfield, Victor Lempitsky, Andrea Vedaldi and Andrew Zisserman,
The devil is in the details: an evaluation of recent feature encoding methods, BMVC 2011.
結果としては、Fisher vectorが一番よかったようです。これを含め最近の研究を見ていると、Fisher vector系の手法が少し優勢な気がします。ただし、BoVWと比較すると特徴ベクトルが密になりやすいのがデメリットかも知れません。
< 大規模一般物体認識 >
今回取り上げた手法は、大規模な問題でこそ真価を発揮するものです。2010年からはじまった、ImageNet large scale visual recognition challenge (ILSVRC) というコンペティションがそのテストベッドになっています。
初回の2010年はNEC-UIUCチームが勝利しました。LCCとsuper vectorを用いています。
http://www.image-net.org/challenges/LSVRC/2010/
この時の手法は、2011年のCVPRで報告されています。
Yuanqing Lin, Fengjun Lv, Shenghuo Zhu, Ming Yang, Timothee Cour, Kai Yu, Liangliang Cao, and Thomas Huang,
Large-scale Image Classification: Fast Feature Extraction and SVM Training, CVPR 2010
ちなみに、2位はXeroxチームでした。
2011年のコンペティションではXeroxが雪辱を果たしました。（ただし、NEC-UIUCは参加していませんでしたが…）
http://www.image-net.org/challenges/LSVRC/2011/
内容を見る限り、以下の論文の手法を用いているようです。この論文では、product quantizationを用いた特徴圧縮手法も提案されています。
Jorge Sánchez and Florent Perronnin,
High-Dimensional Signature Compression for Large-Scale Image Classification, CVPR 2011
