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がない)で作業。
  • ついでに今日の出来事をまとめる(←イマココ)

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

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

ECCV'12とCVPR'12の特定物体認識関連の論文にひたすら1行説明(所感)を付けてみた

去年末のCVアドベントカレンダーでやろうと思って力尽きてたのを今更公開。BMVC'12はやらないかも。CVPapersに載っているタイトルから変わっている論文が結構あった。理解度と好みで分量が違います。

ECCV'12

  • Efficient Discriminative Projections for Compact Binary Descriptors
    • Haar-like特徴のようにスケール・場所の違うboxフィルタまたはガウスフィルタの応答の線形和+signでバイナリ特徴を作る際の重みを学習。
  • Comparative Evaluation of Binary Features
    • detectorとしてHarris, MSER, FAST, ORB, BRISK, SURF, SIFT、descriptorとしてBRIEF, ORB, BRISK, SIFT, SURFを組み合わせた際のパフォーマンス評価。
  • Descriptor Learning Using Convex Optimisation
    • descriptorの改善。DAISYのような特徴領域の配置と、特徴ベクトルの次元削減をregularized dual averagingで最適化。
  • Match Graph Construction for Large Image Databases
    • 画像集合から、同一ランドマーク等が共通に写っている画像間にリンクが貼られているようなグラフを効率的に作りたい。ラベル伝播のアイディアで、少数のリンクから徐々にリンクの検証→ラベル伝播を行うことで効率的にグラフを構築する。
  • MatchMiner: Efficient Spanning Structure Mining in Large Image Collections
    • 画像集合から、同一ランドマーク等が共通に写っている画像間にリンクが貼られているようなグラフを効率的に作りたい。関連フィードバックとクエリ拡張で画像検索結果を高精度化し、更に検索結果のランク情報を類似度のスコアとして利用することを提案。
  • Size Matters: Exhaustive Geometric Verification for Image Retrieval
    • Googleから。閾値以上のスコア(対応点数)を持つリファレンス全てに対して幾何検証を効率的に行う。メインは文書検索における転置インデックスベースのtop-k検索に利用されるDocument at a Time (DAAT)とTerm at a Time (TAAT)を画像検索へ応用した際の評価。DAATとTAATは 転置インデックスとTop k-query を参考に。DAATを実現する効率的なデータ構造counting min-tree (CMT)が新規性?
  • Negative evidences and co-occurences in image retrieval: the benefit of PCA and whitening
    • BoVWのベクトルを平均から引くことで特定のVWが同時に出現しないことを画像類似度に反映する。その後BoVWのベクトルに対しPCA+パワー正規化+L2正規化により特徴ベクトルを生成。更に複数のボキャブラリーを利用することも提案。
  • TreeCANN - k-d tree Coherence Approximate Nearest Neighbor algorithm
    • 2つの画像間の全てのパッチをマッチング。AryaのANNによる近傍探索後、結果を周囲のパッチにpropagate(正解パッチの周囲のパッチも同じ幾何関係にある可能性が高い)。
  • WaSH: Weighted alpha-Shapes for Local Feature Detection
    • Edgeベースのdetector?
  • A Convolutional Treelets Binary Feature Approach to Fast Keypoint Recognition
    • FERNと同様にランダム射影で変換したパッチ群(の特徴)を特徴点と紐付けるが、射影した際のパラメータとバイナリ特徴を1:1で保持しておく。Convolutional Treelets Binary Featureと呼ばれるニューラルネットの出力を二値化して生成される特徴を利用。色々自明な気がする。バイナリ特徴のsub-signatureがLSHのハッシュ関数として使えるって、それLSHそのものだし…
  • KAZE Features
    • SIFT detectorにおけるガウシアンフィルタの代わりにnonlinear diffusion filtering(バイラテラルフィルタ的な効果)を利用。コード有り。 kaze 風なのはAISTでのインターンの結果?!
  • Attribute Discovery via Predictable Discriminative Binary Codes
    • バイナリ特徴ベクトルを、多クラスをうまく分類し、マージンが大きくなるような超平面で特徴ベクトル空間部分割するように学習する。大域解は得られないのでblock coordinate descentで最適化。
  • Improving Image-Based Localization by Active Correspondence Search
    • 大量の3次元上の特徴点に対し、カメラ画像を入力としてカメラ位置を推定する問題。特徴ベクトル空間でのマッチングと、3D空間でのマッチングをうまく融合。

CVPR'12

  • Supervised Hashing with Kernels (CVPR'12)
    • Hashing with graphsの人。主にクラス分類を目的とし、同じクラス間のハミング距離を小さく、異なるクラス間のハミング距離を大きくするようなハッシュ関数を学習。バイナリ特徴間のハミング距離を、バイナリ特徴間の内積で等価表現することで目的関数をシンプルに。
  • Progressive Graph Matching: Making a Move of Graphs via Probabilistic Voting (CVPR'12)
    • graph matchingとgraph progressionを繰り返し行うことで高精度なグラフマッチングを行う(?)
  • Computing Nearest-Neighbor Fields via Propagation-Assisted KD-Trees
    • PatchMatchの拡張。2枚の画像間のピクセルレベルでの対応を求める際に、右の画像の各ピクセルの特徴ベクトルがkd-treesに格納されているとする。あるピクセル間で対応が取れた際に、従来は対応の取れた右の画素同士も類似しているという仮定のもとそれらが対応が取れるか検証していた。提案手法では右の画素と同じleafに登録されている(空間的に近いとは限らない)特徴ベクトル全てを追加の検証対象とすることで打ち切りを高速化する。
  • QsRank: Query-sensitive Hash Code Ranking for Effcient e-neighbor Search (CVPR'12)
    • PCA+signのハッシュ関数による特徴量ベクトルのバイナリ化。range searchをターゲットとし、クエリ特徴はバイナリ化せずにハッシュ関数の超平面までの距離を利用する。特に、クエリからハッシュを定義する超平面までの距離がε以上あれば、そのハッシュにより定義されるビットが異なるリファレンス特徴までの距離は絶対にε以上となることを利用する。【関連】"Asymmetric Hamming Embedding," ACMMM'11.
  • Three things everyone should know to improve object retrieval (CVPR'12)
    • (1)RootSIFT: SIFTの特徴ベクトルをL1正規化後、各次元をルート。こうしてできた特徴ベクトルの二乗距離を利用すると、L1正規化後の特徴ベクトルに対しヒストグラム間の類似度を測るのにより適切なヘリンガーカーネルを適用しているのに等しい。変換後の特徴ベクトルは既存のパイプラインにそのまま入力できることが大きな利点。(2)クエリ拡張時に、検索結果の上位をpositive、下位をnegativeとして線形SVMを学習し、識別面からの符号付き距離を利用してリランキングを行う。(3)データベース画像について、同一オブジェクトが写っている画像の特徴を追加する既存手法に対し、画像全体の特徴を追加するのではなく、同一オブジェクトが写っている矩形領域のみの特徴を追加することでprecisionの低下を防ぐ。
  • D-Nets: Beyond Patch-Based Image Descriptors (CVPR'12)
    • 特徴点間のエッジを記述してマッチング。コード有り。 D-Nets
  • Spherical Hashing (CVPR'12)
    • ハッシュベースの近似最近傍探索手法。pivotの点との距離が閾値以下であれば1、閾値より大きければ0となるハッシュと、点の座標と閾値を最適化する手法を提案。
  • Mobile Product Search with Bag of Hash Bits and Boundary Reranking (CVPR'12)
    • PCA+signのバイナリ特徴をハッシュとして利用&複数ハッシュテーブル&multi-probe(#普通すぎてnoveltyが分からない)+物体のboundaryの検証でreranking.
  • Object retrieval and localization with spatially-constrained similarity measure and k-NN re-ranking (CVPR'12)
    • weak geometric consistency系。マッチングの投票をリファレンス毎の離散化された(x,y)座標へ行う(検索対象オブジェクトの中心座標へのハフ変換)。また、full geometric verification後の検索結果の上位N件を更にクエリとして検索を行い、その結果ランキングリスト群を利用してrerankingを行う(クエリ拡張の一種)。
  • Scalable $k$-NN graph construction for visual descriptors (CVPR'12)
    • データベース中の各高次元ベクトルについてk近傍を求めておくk近傍グラフの正確かつ効率的な構築法。データをランダムかつ階層的に分割し、分割された領域内でknnを求め、複数のそれらの結果を統合する。
  • Real-time Image-based 6-DOF Localization in Large-Scale Environments (CVPR'12)
    • Harris detector + BRIEF descriptorで高速なトラッキング。globalな位置推定のための2D-to-3Dマッチングでは、オフラインで複数スケールの特徴量を抽出し、オンラインではスケール不変でないdetectorを利用することで高速化。
  • A Fast Nearest Neighbor Search Algorithm by Nonlinear Embedding (CVPR'12)
    • 次元圧縮と距離のlower boundによる打ち切りの高精度化を利用した(近似)再近傍探索。
  • 3D Visual Phrases for Landmark Recognition (CVPR'12)
    • 2D空間で行われているweak geometric verification系のvisual phraseを3Dの点群へ応用。
  • Inverted Multi-Index (CVPR'12)
    • visual wordのコードブックを直積量子化で作りましたとしか読めないが…同じコードブック数で比較するとい言っている箇所が幾つかあるが、各部分ベクトルのコードブックと分割していない全体のコードブックサイズを同じにしているのはどうかと思う。コードブックサイズを大きくしてmultiple-assignment (priority search) を行ったほうが精度は高くなるのは当たり前なわけで。フェアに比較すると結局は(特徴ベクトルより上の階層の)visual wordの最近傍探索の精度の話になって、それって全探索と直積量子化を利用した近似探索の差ですよねって結論に。
  • Fast Computation of min-Hash signatures for Image Collectionss (CVPR'12)
    • 複数の画像 (document) を同時に処理することによりmin-Hashの生成を高速化。手法はともかく、公開データセットを利用しているのに一般的なMAPで精度を出さないあたり、やっぱりmin-Hashではあんまり精度でないんだと邪推。
  • FREAK: Fast Retina Keypoint (CVPR'12)
    • BRISKのdetector (AGAST) と、DAISY記述子のようなマルチスケールの円パッチの組の平均輝度の大小関係からバイナリ特徴を抽出。どのパッチの組を利用するかはORBで利用されているアルゴリズムを利用。DAISY→A Fast Local Descriptor for Dense Matching
  • Image Matching using Local Symmetry Features (CVPR'12)
    • 線対称、点対称っぽさを複数スケールでスコア付け、極値をsymmetry featuresとして検出、マッチング。
  • Randomized Visual Phrases for Object Search (CVPR'12)
    • 画像をランダムグリッドに分割し、各グリッド内のVW集合をvisual phraseとする。効率が悪そうな気がするけど検索ロジックがよく分からない…
  • Iterative Nearest Neighbors for Classification and Dimensionality Reduction (CVPR'12)
    • 対象となる特徴ベクトルqに関して、qの最近傍NN(q)との残差を利用して q = q + λ(q - NN(q)) と再帰的に再構築。最終的にはスパースコーディングを行ったような基底群と重みベクトルが得られる。
  • Fast Search in Hamming Space with Multi-Index Hashing (CVPR'12)
    • バイナリベクトルのハミング空間での厳密なkNNまたはレンジサーチ手法。bビットのベクトルをm個の部分ベクトルに分割し、各部分ベクトルに対応するハッシュ(転置インデックス)を作成(m個のハッシュ)。ポイントは、ベクトルpから最大rビット異なるベクトルを検索しようとしたとき、検索されるべきベクトルはfloor(r/m)ビット以下の違いしかない部分ベクトルが存在する(鳩ノ巣原理)。例えば、128ビットのベクトルを4分割するとして、最大7ビットの違いのあるベクトルを検索する場合には、各部分ベクトルに対応するハッシュについて、クエリと1ビットまで違うハッシュ値のリストと距離計算を行う。64ビットのベクトル1B個 (8BG) をインデックス化すると86BGになるという記述で読むのを辞めそうになったが…そもそもSIFTやGISTのベクトルをバイナリ化したもの(既に近似されている)を対象としている以上、厳密なkNNにどこまで意味があるかという意味ではLSHでも良いかなと。