書籍紹介: Visual Object Recognition

Visual Object Recognition (Synthesis Lectures on Artificial Intelligence and Machine Learning)

Visual Object Recognition (Synthesis Lectures on Artificial Intelligence and Machine Learning)

  • 作者: Kristen Grauman,Bastian Leibe
  • 出版社/メーカー: Morgan & Claypool Publishers
  • 発売日: 2011/02/28
  • メディア: ペーパーバック
  • 購入: 12人 クリック: 182回
  • この商品を含むブログを見る
最近読んだ本の紹介をしたいと思います。
名前の通り画像認識に関するチュートリアル本で、出版されたのは2011年2月28日です。
著者がKristen GraumanとBastian Leibeの二人なので、これはと思い衝動買いしてしまいましたが、期待通りいい内容でした。

前半と後半で特定物体認識と一般物体認識の話に大きく分かれており、それぞれ基礎から比較的最近の手法まで非常に分かりやすく、コンパクトにまとめてあります。これから画像認識を本格的に学ぼうとする人にとっては持っておいて絶対に損はない本だと思います。また、専門の人にとっても、知識を整理したり、抜けを補完したりする上で有用だと思います。私も、constellation model以降のpart-based手法の流れは知らなかったものも多く、大変勉強になりました。

欲を言えば、最新の手法に関しては少しカバーが甘いのが物足りなかったところです。例えば、bag-of-visual-wordsに関しては古くからある一般的なものしか記述がありません。また、物体検出に関しても、DPMまでの代表的な手法のみ扱っているようです。まあ、ページ数的に仕方ないとは思いますが・・・。

いずれにせよ、教科書としてはいい本で、多分修士の学生さんくらいに一番向いている気がします。それほど分量は多くない(厚さ12mmくらい)ので多分くじけず読み進めることができます(笑)。輪講などでとりあげてもいいかも知れませんね。

参考までに、以下に目次だけ引用します。

1 Introduction
 1.1 Overview
 1.2 Challenges
 1.3 The State of the Art

2 Overview:Recognition of Specific Objects
 2.1 Global Image Representations
 2.2 Local Feature Representations

3 Local Features:Detection and Description
 3.1 Introduction
 3.2 Detection of Interest Points and Regions
 3.3 Local Descriptors
 3.4 Concluding Remarks

4 Matching Local Features
 4.1 Efficient Similarity Search
 4.2 Indexing Features with Visual Vocabularies
 4.3 Concluding Remarks

5 Geometric Verification of Matched Features
 5.1 Estimating Geometric Models
 5.2 Dealing with Outliers

6 Example Systems:Specific-Object Recognition
 6.1 Image Matching
 6.2 Object Recognition
 6.3 Large-Scale Image Retrieval
 6.4 Mobile Visual Search
 6.5 Image Auto-Annotation
 6.6 Concluding Remarks

7 Overview:Recognition of Generic Object Categories

8 Representations for Object Categories
 8.1 Window-based Object Representations
 8.2 Part-based Object Representations
 8.3 Mixed Representations
 8.4 Concluding Remarks

9 Generic Object Detection:Finding and Scoring Candidates
 9.1 Detection via Classification
 9.2 Detection with Part-based Models

10 Learning Generic Object Category Models
 10.1 Data Annotation
 10.2 Learning Window-based Models
 10.3 Learning Part-based Models

11 Example Systems:Generic Object Recognition
 11.1 The Viola-Jones Face Detector
 11.2 The HOG Person Detector
 11.3 Bag-of-Words Image Classification
 11.4 The Implicit Shape Model
 11.5 Deformable Part-based Models

12 Other Considerations and Current Challenges
 12.1 Benchmarks and Datasets
 12.2 Context-based Recognition
 12.3 Multi-Viewpoint and Multi-Aspect Recognition
 12.4 Role of Video
 12.5 Integrated Segmentation and Recognition
 12.6 Supervision Considerations in Object Category Learning
 12.7 Language, Text, and Images

13 Conclusions

Fine-grained visual categorization

一般物体認識は技術的興味の対象としては魅力的ですが、結局のところ何の役に立つのでしょうか?一般物体認識は、人間にとっていわば「常識」にあたるような基本概念の獲得を目指すものですが、常識であるがゆえに意外と使いどころがないのが実情かもしれません。例えば、街でふとみかけたかっこいいバイクについて知りたくなり、google gogglesのようなアプリで認識・検索したとします。この時、単に「バイク」と言われてもそんなの分かっとるわという話で何の意味もありません。この場合、そのバイクのメーカーや型などが知りたいはずです。
このように実用上価値を見出しやすいのは、物体の基本概念よりはもっとspecificな情報の認識であると思われますが、一般物体認識の研究分野においては主に前者のみが扱われてきました。後者はFine-grained visual categorization (FGVC) と呼ばれ、近年注目される分野になってきています。

FGVCについて、まだあまり明確な定義はないような気がしますが、CVPR'11で開催された初のワークショップのHPには以下のように説明されています。

The First Workshop on Fine-Grained Visual Categorization
http://www.fgvc.org/

"Fine categorization lies in the continuum between basic level categorization (frog vs piano) and identification of individuals (face recognition, biometrics). The visual distinctions between similar categories are often quite subtle and therefore difficult to address with today’s general-purpose object recognition machinery. It is likely that radical re-thinking of some of the matching and learning algorithms and models that are currently used for visual recognition will be needed to approach fine categorization."

要するに、従来の一般物体認識と特定物体認識の中間的なものということのようです。自分の持ってるイメージだと、一般物体認識は幅優先、FGVCは深さ優先でカテゴリを押さえていく感じでしょうか。今のところ、技術的には従来の一般物体認識の手法がほぼそのまま試されている感じですが、今後この領域ならではの面白さが出てくるか注目です。


以下の論文では、ImageNetの大規模なデータを用い、さまざまなポリシーでカテゴリを設定して識別実験を行っています。同じカテゴリ数であっても、概念的に近いクラスを集めた場合は識別精度がかなり落ちることが示されており、FGVCの難しさが伺えます。

Jia Deng, Alexander C. Berg, Kai Li, and Li Fei-Fei, "What Does Classifying More Than 10,000 Image Categories Tell Us?", ECCV 2010.

なお、この論文で使われたFungus134(キノコ*1)、 Vehicle262(車)などのデータセットは、その後のFGVCの研究でもよく用いられています。

他にも、いくつかデータセットが出ています。
一番有名なのは、Caltech-Birdデータセットでしょうか。200種類の鳥の識別をします。バードウォッチングで使えると楽しそうですね。

Welinder P., Branson S., Mita T., Wah C., Schroff F., Belongie S., Perona, P. “Caltech-UCSD Birds 200”. California Institute of Technology. CNS-TR-2010-001. 2010.
http://www.vision.caltech.edu/visipedia/CUB-200.html

Stanford dogデータセットでは、120種類の犬種の識別をします*2

Aditya Khosla, Nityananda Jayadevaprakash, Bangpeng Yao and Li Fei-Fei. "Novel dataset for Fine-Grained Image Categorization", First Workshop on Fine-Grained Visual Categorization (FGVC), IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
http://vision.stanford.edu/aditya86/ImageNetDogs/

少し古いですが、Oxford Flowerデータセットも有名です。102種類の花の識別をします。このデータセットがでた時点では、あまりFGVCの概念が殊更強調されることはなかったような気がします。

Nilsback, M-E. and Zisserman, A. "Automated flower classification over a large number of classes",
Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing (2008)
http://www.robots.ox.ac.uk/~vgg/data/flowers/

なお、写真でとった植物を識別したい、というモチベーションはけっこう昔からあったようで、葉っぱの認識などが研究されています。以下のワークショップが有名です。

ImageCLEF 2011 plant identification task
http://www.imageclef.org/2012/plant

FGVCに特化した技術の開発はまだこれからという感じですが、次の論文などは個人的に好きです。

Branson S., Wah C., Babenko B., Schroff F., Welinder P., Perona P., Belongie S., “Visual Recognition with Humans in the Loop”, European Conference on Computer Vision (ECCV), Heraklion, Crete, Sept., 2010.

前述のCaltech-birdデータセットを用い鳥の種類の識別をします。単に画像だけから識別するのではなく、ユーザに対話的に質問を投げヒントをもらい識別性能を向上させます。このような枠組みは従来の一般物体認識では正当化させづらかったと思われますが、ユーザ自身にも分からない情報を得るために使うのであれば有用そうです*3。Attributeに関する教師ラベルもとれて一石二鳥かもしれません。

*1:キノコの種類の識別ができたら本当にできたらすごいですね。実際に使うのはこわいですが。。

*2:なお、今年のImageNet large scale visual recognition challengeでも、100種類の犬の識別タスクが加わるようです。http://www.image-net.org/challenges/LSVRC/2012/index

*3:ただし、自然言語処理人工知能の技術が支配的になり、画像処理がいらなくなる可能性はありそうですが・・・

Sift on GPU

SiftGPUを動かしてみたのでメモ

環境:CentOS6.0(64bit), GeForce9600GT

CUDAインストール

ここから、nvidiaドライバとCUDAのツールキットをダウンロードする。
http://developer.nvidia.com/cuda-toolkit-41

NVIDIA-Linux-x86_64-285.05.33.run
cudatoolkit_4.1.28_linux_64_rhel5.x.run
gpucomputingsdk_4.1.28_linux.run

まずドライバを入れる。このままインストールすると、Nouveau kernel driverが邪魔と怒られるのでdisableする必要がある。
/boot/grub/grub.confの、起動するOSのkernelの行の末尾にrdblacklist=nouveauと追記すれば良い。
こんな感じ。

kernel /vmlinuz-2.6.32-71.29.1.el6.x86_64 ro root=/dev/mapper/vg_quad00-lv_root rd_LVM_LV=vg_quad00/lv_root rd_LVM_LV=vg_quad/lv_swap rd_LVM_LV=vg_quad00/lv_swap rd_NO_LUKS rd_NO_MD rd_NO_DM LANG=ja_JP.UTF-8 KEYBOARDTYPE=pc KEYTABLE=jp106 crashkernel=128M rhgb quiet rdblacklist=nouveau

再起動して、GUIをおとす。

$ init 3

NVIDIAのドライバをインストール。

$ bash NVIDIA-Linux-x86_64-285.05.33.run 
$ init 5

CUDAのツールキットもインストール

$ bash cudatoolkit_4.1.28_linux_64_rhel5.x.run
$ bash gpucomputingsdk_4.1.28_linux.run

LD_LIBRARY_PATHは通しておいた方がよい。

$ export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/cuda/lib64

Sift GPU

ここのコードをありがたく使わせていただきます。
http://cs.unc.edu/~ccwu/siftgpu/

展開して普通にmakeすれば基本的に大丈夫だが、いろいろライブラリがいるので必要に応じてインストール。
自分の環境だと、devil、glewをソースからコンパイルして入れた。OpenGLあたりも入ってなければ多分必要。
http://openil.sourceforge.net/
http://glew.sourceforge.net/

無事コンパイルできたらサンプルを動かしてみる。

$ cd SiftGPU/bin
$ ./SimpleSIFT
[GPU VENDOR]:	NVIDIA Corporation 474MB
TEXTURE:	8192

[SiftGPU Language]:	GLSL
Image size :	800x600
Image loaded :	../data/800-1.jpg
#Features:	3359
#Features MO:	3927
[RUN SIFT]:	0.575

Image size :	640x480
Image loaded :	../data/640-1.jpg
#Features:	2377
#Features MO:	2784
[RUN SIFT]:	0.125

[SiftMatchGPU]: GLSL

2276 sift matches were found;

速い!そのうちCPUと速度比較とかしてみたいと思います。

Does Content Matter?

今日は、最近読んでいろいろ考えさせられた論文について紹介したいと思います。

Web-Scale Multimedia Analysis: Does Content Matter?
IEEE MultiMedia. 18(2): 12–15 (2011)
(pdf) http://www.slaney.org/malcolm/yahoo/VisionAndViews/Spring2011-DoesContentMatter.pdf
(HP) http://labs.yahoo.com/node/650

内容としては、マルチメディアのコンテンツ解析分野において、これまでの考え方に疑問を投げかけるものです。
この分野では、画像・動画像・音楽などの検索や推薦をコンテンツドリブンに行いたがる人が多く、定型的に用いられるロジックとしては、

  1. 現在実用化されているシステムは、周囲のテキストなどなんらかのメタ情報を利用するものが大半である。
  2. しかし、これらのメタ情報はコンテンツの中身そのものと直接関連しているわけではないので、必ずしも望ましい結果が得られない。
  3. 従って、コンテンツの信号そのものから特徴抽出(FFTなど)を行い、これを利用することが必要である。

というところだと思います。しかしこの論文では、多くのタスクでコンテンツ自体の特徴よりもメタ情報の方がはるかに有効であったという結果を示しており、安易に上記の考え方をとり続けることに警鐘を鳴らしています。

内容紹介

この論文の著者であるMalcolm SlaneyさんはYahoo! Researchの研究者で、マルチメディア分野では大御所の一人です。
音楽や画像を中心に、長い間前述のようなコンテンツ解析とその応用へ取り組んできた方だけに、非常に重みを感じます。
以下に極簡単に内容をまとめますが、是非とも原文を読むことをお勧めします。とても歯切れのよい文章で、示唆に富んでいます。

< 音楽検索 >

著者が過去に行った実験で、音楽の類似度を測定する二つのアプローチについて比較を行っています*1

  1. 各曲の音声波形から得られる特徴量を利用する。(ジャンル識別などでよく用いられるものだそうです。)
  2. 各曲について5段階でユーザが評価したスコアを、ユーザ数分並べて素性ベクトルとする。

あるデータセットを用いたブラインドテストの結果、後者が圧倒的によい結果となりました。

< 動画像推薦 >

Netflixは2009年に、映画推薦のコンペティションを開催しました。賞金総額100万ドルの大規模なもので、多くの研究者の関心を集めました。
動画像特徴量を用いる試みも多く行われましたが、優勝したシステムでは結局そのようなコンテンツ自体の特徴は一切用いられませんでした。ユーザの評価スコア、映画の公開時期など多数のメタ情報をブースティングで組みあわせています。

このコンペティションの参加者の多くはコンテンツ解析にも精通した研究者であったにも関わらず、このような結果になったことの意義が強調されています。プロジェクトのページでは以下のようにコメントされています。
「アカデミアの世界で行われるベンチマーキングの多くは、単一の情報源(例えば画像のみ)に基づき、単純な指標で評価するものになっています。これはこれで、問題に対する一つの解へ集中するためにはよい枠組みであるといえます。しかしながら、現実の世界ではより優れた方法が求められています。最も優れた方法が、我々が期待するものとは限らないのです。」

< 画像アノテーション >

画像アノテーションとは画像へいくつかのキーワードを付与するタスクであり、比較的単純なパターン認識の問題です。多くの人が、画像自体の信号(ピクセル)が一番重要な情報を持つと考えてきましたが、果たしてどうでしょうか。
Yahoo! Researchの研究者がFlickrの関係者に、アダルト写真のフィルタリングのために最新のコンピュータビジョン技術が必要か聞いてみたことがあるそうです。しかし彼らは即座にこれを否定し、ネットワークグラフを利用する方が有効だろうと答えました。Flickrの場合、どの写真も誰によって撮影されアップロードされたかが分かり、その撮影者の友人の写真にはどのようなラベルがついているか、などの周辺のコンテキストを得ることができます。これらの情報の方が画像そのものよりも強力であろうということです。

この考え方を一般化し、調査した結果が発表されています*2。この実験では、ウェブから画像を収集し、ハイパーリンクからグラフを作っています。その結果、最も有効であったのは、画像自体の特徴量でも画像周辺のテキストでもなく、グラフ上の近傍画像の持つラベルでした。要するに、同じサイトや似たようなサイトにある画像は似たようなものが多いという、ある意味当たり前の結果なのかも知れません*3

< 結論 >(訳、一部のみ)

「コンテンツ解析分野の研究者として、私はコンテンツ自体を無視すべきなどというつもりはありません。しかしながら、問題を解くにはさまざまな方法があります。マルチメディアコンテンツを取り巻く豊富なメタ情報を見過ごすべきではないでしょう。
我々への"宿題"になっている課題では、画像のピクセルしか考慮しないかも知れません。しかし現実の世界はそれほど単純ではありません。全てのコンテンツはなんらかの文脈を持っており、その情報を無視することは科学的ではないし、成功へのチャンスを遠のかせるでしょう。」

感想

まず率直な感想としては、よくこんな論文書いたなあと(笑)。コンテンツ解析が大好きな人にとっては苦々しい論文かもしれません。ただ、このような事実は事実として受け入れなければなりません。著者自身もコンテンツ解析の専門家であるだけに、かなり苦悩されたのだろうと思います。分野のリーダーとして正しい方向へ議論を導こうとする強い意志を感じました。

冒頭で述べたようなコンテンツ解析の論法は、おそらく15年前にはある程度説得力があったのでしょう。ただ、現在ではSNSなどの急激な進歩により、コンテンツに対して人間が直接的に与えたメタ情報がいくらでもとれるようになって来ています。最終的に評価するのが人間である以上、こうした情報を用いる方がよい結果になるのは当然といえば当然なのかもしれません。

今までは、画像・動画像などを中心としたコンテンツ解析は見た目が分かりやすく、何となくすごいものが出来そうな印象を与えるものであったため研究対象にしやすかった面がありますが、これからはその最終的な目的がシビアに問われるようになりそうです。

*1:M. Slaney and W. White, Similarity Based on Rating Data, Proc. Int'l Soc. Music-Information Retrieval, 2007.

*2:D.K. Mahajan and M. Slaney, Image Classification Using the Web Graph, Proc. Int'l Conf. Multimedia, ACM Press, 2010, pp. 991-994.

*3:ただし、この実験ではアダルトコンテンツの識別という最もwebグラフの効果が出そうなタスクを扱っているので、一般的な画像認識でも同じ結果になるかは議論が必要であると思います。

新型BoVW

いよいよ、従来のBoVWに変わる新しい特徴表現方法を見ていきます。これらの新しい特徴は直接線形手法に適用できるように設計されており、線形SVMと合わせて用いられることが多いです。

前置き

一枚の画像からBoVW(或いは、それに類する枠組み)によって特徴ベクトルを得るまでは、非常に大雑把に分けると次の二つの過程に分かれます。

  1. 画像から多数(数千〜数万)の局所特徴を抽出
  2. 得られた大量の局所特徴の情報を利用し、最終的なアウトプットである一本の特徴ベクトルを生成

どちらも大事なプロセスですが、今回考えるのは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

*1:"局所"がかぶってややこしいですが、こちらは特徴空間上の局所構造を指しています。

*2:この場合混合正規分布。構成する正規分布が一つ一つがvisual wordに相当するものと解釈できます。

従来型BoVWの変換

Explicit feature map

これに関してはどちらかというと識別器の工夫で、BoVWという表現そのものは何も変わりないのですがけっこう大事だと思うので。

冒頭で述べたようにBoVWには非線形カーネルの利用が必要でした。もともとカーネルはunknownな高次元空間における内積を観測空間で行うためのツールでしたが、これを用いるとサンプル数に対するスケーラビリティは著しく落ちます(O(n^2)〜O(n^3))。だったら、その高次元空間への写像(feature map)を明示的に書き下してしまって直接線形識別器(O(n))を使えばいいじゃないかというのがモチベーションです。もちろん、一般的にはそのような高次元空間が書けるとは限りませんが、BoVWのようなヒストグラム特徴でよく用いられるカーネルについては比較的簡単に設計できることが分かっています。

おそらく、最初に有名になったのは次の論文です。この論文では、ヒストグラムインタセクションカーネルのfeature mapが示されています。

Subhransu Maji, Alexander C. Berg, Max-Margin Additive Classifiers for Detection, ICCV 2009.

このアプローチはすぐに、さまざまなadditive kernelへ拡張されています。Additive kernelとは、ヒストグラムのビンごとに定義される非線形カーネルの線形和で書けるカーネルのことで、さっきのインタセクションカーネルカイ二乗カーネルなどが代表例です。

A. Vedaldi and A. Zisserman, Efficient additive kernels via explicit feature maps, CVPR 2010.

Florent Perronnin, Jorge Sánchez and Yan Liu, Large-Scale Image Categorization with Explicit Data Embedding, CVPR 2010.

一般的なRBFカーネルについては同様の方法がもっと前から提案されています。フーリエ変換を利用して代表点をサンプリングするようです。

A. Rahimi and B. Recht, Random features for large-scale kernel machines, NIPS 2007.

これをgeneralized RBFカーネルに応用したものも提案されています。

Sreekanth Vempati, Andrea Vedaldi, Andrew Zisserman, C. V. Jawahar,
Generalized RBF feature maps for Efficient Detection, BMVC 2010.

一般的に、カイ二乗距離等を用いたGRBFが精度面では最も優れているので、これが一つの完成形であると言えるでしょう。

Feature mapの考え方は非線形識別問題における一般的なもので、BoVWという表現そのものを変えるものではありません。次節で見ていきますが、最近はBoVW自体の意味を見直す動きが広がり新しい特徴表現が登場してきたこともあり、feature mapは現在ではあまり見なくなった気がします。が、逆に言えば今までに抽出したBoVW*1があればそれはそのまま利用できます。
前述のMaji & Bergの手法をBoVWに適用し、10,000クラスの大規模な識別実験を行った例が報告されています。

Jia Deng, Alexander C. Berg, Kai Li, and Li Fei-Fei,
What Does Classifying More Than 10,000 Image Categories Tell Us? ECCV 2010.

*1:もちろん、他の特徴ベクトルでも利用できるでしょう。

次世代BoVWまとめ

以前のエントリでも述べましたが、bag of visual words(BoVW)は一般物体認識における標準的な画像特徴表現であり、非常によく用いられます。ですが、BoVWはこの3年ほどで急速に進歩しており、よく見られる「k-meansでクラスタリングヒストグラム作成 → 非線形SVM」という定石は既に時代遅れのものとなりつつあります。

今日は、BoVWに関連する最近のトレンドをいくつか見てみたいと思います。実は、これは一般物体認識の大規模化と深い関わりがあります。古典的なBoVWでは非線形カーネルの利用が必要でしたが、最近の手法は線形識別器を直接適用できるように考えて設計されています。ここがうまくいけばあとは、いかにして大規模な線形識別器を学習するか、という機械学習データマイニング等でよく議論される問題まで落ちてきます。これにより、一般物体認識もかなり大きな規模のデータで学習・認識を行うことが徐々に可能になってきています。