大規模特定物体認識技術およびその最新研究事例

信学会の自分の記事、今は条件付きで公開できるらしいので、以前の解説記事を公開します。会誌なのでふわっとした感じになってますが…
内田祐介, 酒澤茂之, "大規模特定物体認識の最新動向," 信学会誌, Vol. 93, No. 3, pp. 207-213, 2013. Copyright (C) 2013 IEICE.
公開条件等の認識が間違っていたらご指摘ください！

もう少し新しい情報を追加した記事を画像ラボさんに寄稿させて頂いたのですが、こちらは公開できないのでそのうちアップデートして別の記事として公開したいですね。
内田祐介, 酒澤茂之 "大規模特定物体認識技術およびその最新研究事例," Vol. 24, No. 12, pp. 61-68, 2013.

Japan CV Dayで発表してきました

今更ですが一応。

Japan Computer Vision Day 2013
http://partake.in/events/5a96edbd-7a32-4a6d-81b8-bf5e7bbcbbf4

togetter
http://togetter.com/li/540498

Ustream
http://www.ustream.tv/channel/%E5%90%8D%E5%8F%A4%E5%B1%8Bcv-prml%E5%8B%89%E5%BC%B7%E4%BC%9A

発表資料

"K-means Hashing: an Affinity-Preserving Quantization Method for Learning Binary Compact Codes," CVPR'13. を概説しています。k-means（ベクトル量子化）の符号化効率の良さと、バイナリコードの高速な距離計算の良いとこ取りができる手法です。ハッシングをk-meansでやっているところが面白くてこの論文を選びましたが、既存手法のiterative quantization (ITQ) のも非常に面白いです。
ITQは、ハッシングを量子化とみなすことで、ハッシングのための射影行列の最適化に直交プロクラステス問題を適用することを可能としました。直交プロクラステス問題は下式で表現される最小化問題です。
R = \arg\min_{\Omega} || A \Omega - B ||_F^2 \; \mathrm{subject \; to} \; \Omega^T \Omega = I
http://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem
直感的には行列AとBをなるべく同じにするような回転行列Rを求める問題です。量子化問題の場合、AとBはそれぞれ、量子化対象のベクトルとそれに対応するコードブックのベクトルを並べた行列です。そしてこれらの行列の差分のフロベニウスノルム（量子化誤差）を最小化する回転行列RがSVDで簡単に求まるのです。
ハッシングではなく、直積量子化の符号化効率の改善に利用している手法も提案されており、ほとんど同じ手法が同時にCVPR'13に採録されています。読んでみるとどちらも同じく直交プロクラステス問題に落とし込んでいることが分かると思います。ITQ論文がなければこれらの手法が生まれるのはもう少し遅かったのではないでしょうか。
"Cartesian k-means," CVPR'13.

"Optimized Product Quantization for Approximate Nearest Neighbor Search," CVPR'13.

やっていることはITQとほぼ同じで、直積量子化時の量子化誤差を最小化する回転を求め、回転されたベクトルを再度直積量子化コードブックに割り当て、その割り当てから直積量子化コードブックを更新するということを繰り返しています。

ついでなのでハッシング系の論文リストもおいておきます。

  1. "Similarity search in high dimensions via hashing," VLDB'99. (LSH)
  2. "Spectral Hashing," NIPS'08. (SH)
  3. "Learning to Hash with Binary Reconstructive Embeddings," NIPS'09. (BRE)
  4. "Locality Sensitive Binary Codes from Shift-Invariant Kernels," NIPS'09. (SIKH)
  5. "Kernelized Locality-Sensitive Hashing for Scalable Image Search," ICCV'09. (KLSH)
  6. "Sequential Projection Learning for Hashing with Compact Codes," ICML'10. (USPLH)
  7. "Self-Taught Hashing for Fast Similarity Search," SIGIR'10.
  8. "CARD: Compact And Real-time Descriptors," ICCV'11.
  9. "Complementary Hashing for Approximate Nearest Neighbor Search," ICCV'11.
  10. "Coherency Sensitive Hashing," ICCV'11.
  11. "Hashing with Graphs," ICML'11. (AGH)
  12. "Minimal Loss Hashing for Compact Binary Codes," ICML'11.
  13. "Random Maximum Margin Hashing," CVPR'11.
  14. "Iterative Quantization: A Procrustean Approach to Learning Binary Codes," CVPR'11. (ITQ)
  15. "LDAHash: Improved Matching with Smaller Descriptors," PAMI'12. (LDAH)
  16. "Isotropic Hashing," NIPS'12.
  17. "Supervised Hashing with Kernels," CVPR'12.
  18. "Spherical Hashing," CVPR'12.
  19. "Multidimensional Spectral Hashing," ECCV'12.
  20. "Double-Bit Quantization for Hashing," AAAI'13.
  21. "Variable Bit Quantisation for LSH," ACL'13.
  22. "Hash Bit Selection: a Unified Solution for Selection Problems in Hashing," CVPR'13.
  23. "Compressed Hashing," CVPR'13.
  24. "Inductive Hashing on Manifolds," CVPR'13.
  25. "Learning Binary Codes for High-Dimensional Data Using Bilinear Projections," CVPR'13.
  26. "K-means Hashing: an Affinity-Preserving Quantization Method for Learning Binary Compact Codes," CVPR'13.

初ロサンゼルス！（嬉しくない

国際学会ICME発表のためサンノゼに行くことに。全ての不幸は、成田サンノゼ直通便が復活したにもかかわらず、値段的事情によりSQ→UAのロサンゼルスでのトランジットが発生したこと…

  • 成田発、ロス着のSQが、30分遅れでロスに到着。SQは評判以上にサービス良さげ。ご飯美味しい。A380広い。CAさん美人。
  • 入国審査後、預けた荷物を受け取り、トランジットの便に送る（不幸の始まり。ここで止めてくれ）。
  • チェックインカウンターたどり着くと、トランジットのロス発サンノゼ着のUA便にCANCELLEDの文字が。イミフ！
  • UAのスタッフに聞いたが把握してなかった。中国系のスタッフと同僚の中国人が喋ってると段々険悪な感じに。なんかこっちの言ったことの2倍くらい唾飛ばしながら文句言ってくる。
  • カウンターで、今日のサンノゼ便は他社（デルタに電話してたみたい）含めてない。サンノゼに直接行く便は明後日ならある。今日深夜12:30着のサンフランシスコ行きならある。サンフランシスコからサンノゼは近いぜ！荷物はサンノゼで受け取れ、と言われる（笑
  • まさに埒が明かないので、今日はロスに泊まって、明日サンフランシスコ経由でサンノゼに行くことに。安宿を手配される。荷物だけは今日受け取りたかったので、手配してもらう。
  • バゲージクレームを行き来しつつ3時間くらい待ったが、荷物が返ってこない。
  • 隣でポスター持って荷物待ってる人がいたので話してみると、同じくICMEで発表するタイからの研究者だった！しかもちょっと前にNIIの佐藤先生のところでインターンしてたらしい（偶然すぎる）。ちなみに彼は、明日の朝のサンノゼ便（デルタ）がアサインされ、ぼくらの宿の2倍くらいの値段の宿がアサインされていた。対応してもらう相手次第ということを痛感。
  • バゲージクレームのカウンターを3つくらい行き来したりした結果、さらに1時間後くらいに（同時に預けたのに！）同僚の荷物だけ見つかる。
  • 自分の荷物は探してもらってるが全然出てこないので、今日見つかれば、明日のサンフランシスコ便に乗るときに受け取る、見つからなければサンノゼのホテルに送ってもらうことにしてホテルに行く（ホテルは思ったより悪くなかった。フタッフ優しい）
  • やけ酒とステーキを摂取する。
  • うたた寝後、今日中にやらないといけないことがあったのでロビー（にしかタダWifiがない）で作業。
  • ついでに今日の出来事をまとめる（←イマココ）

まぁ話のネタができたからいいけどね！（震え声

Global SIFT

意外に画像全体からSIFT特徴ベクトルを抽出するようなコードがないので、OpenCVのコードをベースに書いた（だいぶ前）。OpenCVの関数でも特徴領域を画像全体にすれば同じ事はできるけど。
ついでにGISTデビューのテスト。

RootSIFTのススメ

以前、CVPR'12特定物体認識に関する論文を全部軽くレビューしました。
ECCV'12とCVPR'12の特定物体認識関連の論文にひたすら1行説明（所感）を付けてみた - yu4uの日記
正直これは！というものはなかった印象ですが、Three things everyone should know to improve object retrieval [1] の、"Three things" のうち最初の1つ (RootSIFT) は良いものだと思うので紹介してみます。

要旨

  • RootSIFT＝SIFTのベクトルをL1正規化した後、各次元のルートを取ったベクトル、距離計算はユークリッド距離で行う
  • 既存のSIFTを利用したシステムに上の処理を追加するだけで使え、それだけで認識精度が結構向上する
  • 特定物体認識でSIFT使ってるならRootSIFTを使うべき（多分一般物体認識でも？HOGにも有効？）

問題設定

SIFTの距離計算には、基本的にユークリッド(L2)距離が使われている。ところで、ヒストグラム特徴には、L2距離を用いるよりも、L1距離、カイ二乗距離、EMDやヘリンガーカーネル等を用いたほうが良いと言われている。SIFTも勾配方向のヒストグラムであることを考慮すると、L2距離以外の距離を利用することで画像検索や画像認識で精度向上が期待できる。

解法

通常のSIFTの代わりに、RootSIFT（＝SIFTのベクトルをL1正規化した後、各次元のルートを取ったベクトル）を利用する。今、\mathbf{x} および \mathbf{y} をL1正規化されたSIFTベクトル、\sqrt{\mathbf{x}} および \sqrt{\mathbf{y}} をそれらの各次元のルートを取ったRootSIFTベクトルとする。RootSIFT間のL2距離を計算してみると、
||\sqrt{\mathbf{x}} - \sqrt{\mathbf{y}}||_2^2 = ||\mathbf{x}||_1^1 + ||\mathbf{y}||_1^1 - 2 \sqrt{\mathbf{x}}^{\mathrm{T}} \sqrt{\mathbf{y}} = 2 - 2 \sqrt{\mathbf{x}}^{\mathrm{T}} \sqrt{\mathbf{y}}
となる。ここで、\sqrt{\mathbf{x}}^{\mathrm{T}} \sqrt{\mathbf{y}} = \textstyle\sum_i \sqrt{x_i y_i} = K(\mathbf{x}, \mathbf{y}) はヘリンガーカーネルの定義そのものであるので、RootSIFTに対してユークリッド距離を用いて（非）類似度を判定することは、元の（L1正規化された）SIFTベクトルに対してヘリンガーカーネルを利用していることに等しい。ポイントは、RootSIFTにしてしまえば、その後は通常のSIFTと同じようにL2距離を前提とできるので、従来のシステムを全く変更することなく導入できる点にある。
実験では、既存手法を含めた様々な手法の特徴ベクトルをSIFTからRootSIFTに変更するだけで、数%の精度向上（元々サチってるので、数%でも結構凄い）が確認できている。

感想

非常にシンプルな手法ですが、理論的な裏付けがあり、処理がモジュール化されてるのが好きです。特に、通常のSIFT抽出のプログラムをいじるまでもなく、後処理を追加するだけでこれまでのパイプライン処理をそのまま利用できるのが大きいと思います（厳密にはSIFT特徴ベクトルを抽出する際に、大きな値を持ったビンをカットオフしている処理があり、その処理をOFFにすべきかとか気になることはありますが）。
自分でもチューニングした比較的サチってるシステムで試してみましたが、有意に精度が改善されましたので、SIFTやGLOHといったヒストグラム特徴を使ってる方は、取り敢えず試してみて損はないと思います。ちなみに画像検索でもほぼ同様のこと（SIFT特徴のpower正規化）が提案されています[2]。

なお、SIFT等に対してL2距離以外を使おうという考え自体は非常に一般的で、下記のチュートリアルが良くまとまっています。
http://www.cs.huji.ac.il/~ofirpele/DFML_ECCV2010_tutorial/
カーネル表現を陽に特徴ベクトルにマッピングする手法はICCV'09あたり（CV初心者だったのであまり覚えていない）でブームだった気がしますが、その辺りで似たようなのはやられてないのかな？という気はします。

余談

ヒストグラム特徴へのヘリンガーカーネル適用の妥当性は、情報幾何的な観点からも納得性があります。つまり、L1正規化されたSIFTベクトル（ヒストグラム）\mathbf{x} および \mathbf{y} を多項分布のパラメータとみなすと、その多項分布間の測地線距離 (geodesic distance) は閉形式で書けて、
2 \arccos \textstyle\sum_i \sqrt{x_i y_i}
となり[3,4]、類似度尺度としてはヘリンガーカーネルと等価になります。
上記までの考え方は、同じく多項分布のパラメータとみなせるBoVWに対しても有効と思われます。

[1] R. Arandjelovic and A. Zisserman, "Three things everyone should know to improve object retrieval," in Proc. of CVPR, 2012.
[2] M. Jain, et al., "Hamming Embedding Similarity-based Image Classification," in Proc. of ICMR, 2012.
[3] C. Atkinson, et al., "Rao's Distance Measure," in Sankhya, 1981.
[4] 山田, "情報幾何学的手法を用いたテクスチャ画像の分類について," 信学論D, 2001.

みんな大好きなSIFTの特許を訳してみた

MPEGでは特定物体認識用の特徴量 (CDVS) の標準化を行なっていて、そのメーリングリストを久々に見たらSIFTの特許回避に関する話があった。
Compact Descriptors for Visual Search | MPEG
「SIFTはDoGを使ってるので、LoGベースなら大丈夫なんじゃない？LoGなんてめっちゃ昔から使われてるし！」→「SIFTの特許は（スケールスペースでの）極値を検出する処理が取られてて、そこに抵触する可能性があるのでは？」といったやり取りがあって、そういえばSIFTの特許を真面目に読んだこと無いなぁと思って訳してみた。確かに、極値を検出する処理が請求項1になっているよう。
請求項1〜4が検出器の話、請求項1、5〜9が記述子の話。請求項10以降は装置とコンピュータに言い換えただけの請求項なので省略。

  • 請求項1
    多数のピクセルによって定義される、画像中のスケール不変特徴を特定する方法であって、
    前記画像から生成された多数の差分画像中のピクセル強度の極値の場所を（以下のように）特定し、
    （問題としている（差分）画像中の各ピクセル強度と、前記ピクセルに関係するある範囲中にあるピクセル強度とを比較することで局所極大もしくは局所極小となるピクセルを特定し、
    前記局所極大もしくは局所極小のピクセル強度と、問題としている画像の直前の画像のピクセル強度を比較することで極大もしくは極小となる可能性のあるピクセルを特定し、
    前記極大もしくは極小となる可能性のあるピクセル強度と、問題としている画像の直後の画像のピクセル強度を比較することで実際の極大もしくは極小となるピクセルを特定する）
    更に前記画像から生成された多数の差分画像中のピクセルの極値に対応するピクセル領域の各部分領域について多数の部分記述子を生成する方法。
  • 請求項2
    請求項1に記載の方法であって、前記差分画像を生成することを特徴とする方法。
  • 請求項3
    請求項2に記載の方法であって、差分画像を生成する際に、初期画像を平滑化することで平滑化画像を生成し、前記初期画像から前記平滑化画像を減算することによって差分画像を生成することを特徴とする方法。
  • 請求項4
    請求項3に記載の方法であって、差分画像を生成する際に請求項3に記載の通り連続的に平滑化と減算を行い、その際、連続平滑化処理で利用される初期画像は、直前の平滑化処理で生成された平滑化画像であることを特徴とする方法。
  • 請求項5
    請求項1に記載の方法であって、差分画像中の各ピクセルについて勾配ベクトルを生成することを特徴とする方法。
  • 請求項6
    請求項5に記載の方法であって、各差分画像における実際の極大もしくは極小となるピクセルそれぞれに角度ベクトルを紐付けることを特徴とする方法。
  • 請求項7
    請求項6に記載の方法であって、多数の部分領域記述子を生成する際に、前記各対応部分領域中のピクセルの勾配ベクトルに基づいて部分領域記述子を生成することを特徴とする方法。
  • 請求項8
    請求項7に記載の方法であって、前記部分領域記述子を生成する際に、前記部分領域において予め定められた角度範囲内の角度を持つピクセル数を測定することを特徴とする方法。
  • 請求項9
    請求項8に記載の方法であって、多数の部分領域記述子を生成する際に、多数の角度範囲と前記記述子とを関連付け、各部分領域毎に、各角度範囲の角度をを持つピクセル数を測定することを特徴とする方法。

原文↓
US6711293B1 - Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image - Google Patents

  1. A method of identifying scale invariant features in an image defined by a plurality of pixels, the method comprising:
    locating pixel amplitude extrema in a plurality of difference images produced from said image by:
    comparing the amplitude of each pixel in an image under consideration with the amplitudes of pixels in an area about said each pixel in said image under consideration to identify local maximal and minimal amplitude pixels;
    comparing the amplitudes of said local maximal and minimal amplitude pixels with the amplitudes of pixels in a predecessor image to the image under consideration to identify possible maximal and minimal amplitude pixels and
    comparing the amplitudes of said possible maximal and minimal amplitude pixels with the amplitudes of pixels in a successor image to the image under consideration to identify actual maximal and minimal amplitude pixels; and
    producing a plurality of component subregion descriptors for each subregion of a pixel region about said pixel amplitude extrema in said plurality of difference images produced from said image.
  2. The method claimed in claim 1 further comprising producing said difference images.
  3. The method claimed in claim 2 wherein producing a difference image comprises blurring an initial image to produce a blurred image and subtracting said blurred image from said initial image to produce a difference image.
  4. The method claimed in claim 3 wherein producing said difference images comprises successively blurring and subtracting as recited in claim 3 where said initial image used in a successive blurring function includes a blurred image produced in a predecessor blurring function.
  5. The method claimed in claim 1 further comprising producing a pixel gradient vector for each pixel in each difference image.
  6. The method claimed in claim 5 further comprising associating vector orientations with respective actual maximal and minimal amplitude pixels associated with each difference image.
  7. The method claimed in claim 6 wherein producing a plurality of component subregion descriptors comprises producing subregion descriptors for each respective subregion in response to pixel gradient vectors of pixels within said each respective subregion.
  8. The method claimed in claim 7 wherein producing each of said subregion descriptors comprises determining the number of pixel vectors at orientations within a predefined range of orientations in said subregion.
  9. The method claimed in claim 7 wherein producing a plurality of subregion descriptors comprises associating with each of said descriptors a plurality of orientation ranges and determining the number of pixel vectors at orientations within respective orientation ranges, for each subregion.

CVPR'13の特定物体認識関連の論文リスト

怖いお兄さんにプレッシャーを受けたので、差し当たり CVPR 2013 papers on the web - Papers からあとで読むリストだけ作った。全論文だと、"Dictionary Learning"がタイトルにあるのが9件もあったけどなんだろ。sparse coding系の辞書学習だと思うんだけど目新しいわけでもないしたまたま？

  • Understanding Indoor Scenes using 3D Geometric Phrases
  • Diffusion Processes for Retrieval Revisited
  • Fast, Accurate Detection of 100,000 Object Classes on a Single Machine
  • Cartesian k-means
  • Learning Structured Hough Voting for Joint Object Detection and Occlusion Reasoning
  • Transfer Sparse Coding for Robust Image Representation
  • Boosting Binary Keypoint Descriptors
  • Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
  • Deformable Graph Matching
  • Graph-Based Discriminative Learning for Location Recognition
  • Constraints as Features
  • Cross-view Image Geolocalization
  • K-means Hashing: an Affinity-Preserving Quantization Method for Learning Binary Compact Codes
  • Supervised Kernel Descriptors for Visual Recognition
  • Fast Convolutional Sparse Coding
  • Hash Bit Selection: a Unified Solution for Selection Problems in Hashing
  • Compressed Hashing
  • All about VLAD
  • Online Robust Dictionary Learning
  • Discriminative Subspace Clustering
  • A Bayesian Approach to Multimodal Visual Dictionary Learning
  • Correspondence-Less Non-Rigid Registration of Triangular Surface Meshes
  • Alternating Decision Forests
  • Learning Class-to-Image Distance with Object Matchings
  • Online Object Tracking: A Benchmark
  • Robust Feature Matching with Alternate Hough and Inverted Hough Transforms
  • Inductive Hashing on Manifolds
  • Learning Compact Binary Codes for Visual Tracking
  • Learning Binary Codes for High-dimensional Data using Bilinear Projections
  • Optimized Product Quantization for Approximate Nearest Neighbor Search
  • The Generalized Laplacian Distance and its Applications for Visual Matching
  • Accurate Localization of 3D Objects from RGB-D Data using Segmentation Hypotheses
  • Efficient Maximum Appearance Search for Large-Scale Object Detection
  • Sparse Output Coding for Large-scale Visual Recognition
  • Towards Contactless, Low-Cost and Accurate 3D Fingerprint Identification
  • What Makes a Patch Distinct?
  • Dense Non-Rigid Point-Matching Using Random Projections
  • Visual Tracking via Locality Sensitive Histograms
  • Improving the Visual Comprehension of Point Sets
  • Fast multiple-part based object detection using KD-Ferns
  • Optimizing 1-Nearest Prototype Classifiers
  • Query Adaptive Similarity for Large Scale Object Retrieval
  • FAsT-Match: Fast Affine Template Matching
  • Lp-norm IDF for Large Scale Image Search
  • Dense Segmentation-aware Descriptors
  • CLAM: Coupled Localization and Mapping with Efficient Outlier Handling
  • SLAM++: Simultaneous Localisation and Mapping at the Level of Objects
  • Visual Place Recognition with Repetitive Structures
  • Keypoints from Symmetries by Wave Propagation
  • A Fast Approximate AIB Algorithm for Distributional Word Clustering
  • Learning SURF Cascade for Fast and Accurate Object Detection
  • Efficient 2D-to-3D Correspondence Filtering for Scalable 3D Object Recognition
  • Discriminative Color Descriptors
  • Binary Code Ranking with Weighted Hamming Distance
  • Leveraging Structure from Motion to Learn Discriminative Codebooks for Scalable Landmark Classification
  • Sparse Quantization for Patch Description
  • Learning and calibrating per-location classifiers for visual place recognition