[2015] Image Classification and Retrieval are ONE

[yoheikikuta]

論文リンク

http://ml.cs.tsinghua.edu.cn/~lingxi/PDFs/Xie_ICMR15_ONE.pdf

公開日（yyyy/mm/dd）

2015/06/23

概要

画像の分類と検索は画像間の類似度を対象にしているという点で本質的に同じだという主張。 分類でも検索でも使える Online Nearest-neighbor Estimiation (ONE) というモデルを提案。 画像間の類似度を計算する際に計算負荷が軽くなるように PCA と product quantization を使用、分類でも検索でもそれまでのモデルと比較して良い結果。

[yoheikikuta]

最近こういう問題に興味があるのでちょっと読んでみる。 タイトルが結構センスあるなぁ。

[yoheikikuta]

CNNの登場で分類はよくできるようになって、検索も toy program から商用利用されてきているような状況の中、共通する本質的な部分を明らかにすることでそれらを統合するモデルを作ろうというモチベーション。

統合したいというモチベーションはこれだけ見るとよく分からんが、一つのモデルでどちらでも解けたら有用だし、何より同じ仕組みで解けるのが興味深いという話だろう。

[yoheikikuta]

手法としては画像中の object を複数検出して、その object の特徴量間の距離を算出して平均を取ることで画像間もしくは画像とカテゴリの類似度を算出するという話。

論文曰く、contributions は

• 分類と検索の統合
• state of the art の達成
• GPUによる並列化

とあるが、読んでみるに本質的には１つめのみが重要そう。

[yoheikikuta]

Nearest Neighbor を使うので、その際の特徴量を低次元化するために以下の２つが紹介されている。 D 次元特徴量使ってを N 個のデータ全てとの距離を計算する場合は $ O(DN) $ の計算量なので、ここでは D を小さくしようという話である。

• PCA
• Product Qunatization (直積量子化) あるベクトルを M 分割し、分割された各サブベクトルは k-bit 量子化することで、量子化されたサブベクトルの直積として元のベクトルを表現するという話。距離計算は各サブベクトルに対してコードブックを作り代表ベクトル間の距離を予め計算することで、それを引いてきさえすればよいというもの。

[yoheikikuta]

上の話はあくまで計算効率化のための話なのでこの論文の本質ではない。 本質的には以下がポイント

• データセットとしては（画像、ラベル）を持っているものとする
• 一つの画像 I_n に対して K_n 個のオブジェクトを得る（これは selective search のような unsupervised な手法で獲得したり、手動で与えたり、のパターンがある）
• 各オブジェクトに対して CNN で特徴量（この論文では 4096 dim）を抽出
• query 画像の各オブジェクトに対して、あるカテゴリに属する全画像の全オブジェクトの特徴量の中で最も近いものを持ってくる。query画像の全オブジェクトの結果を平均して類似度を算出

文字だと少し分かりにくいが、式は以下のようになる。

[yoheikikuta]

計算コストは、object の数を K 個、データ数を N 個、PCA で D 次元に圧縮、直積量子化で M 個サブベクトルに分割、各サブベクトルでのコードブックを T とすると、

$ O(K^2 NM + KDT) $

となる。オリジナルでは $ O(4096 K^2 N) $ なので、これでかなり削減できているという寸法である。

[yoheikikuta]

ちなみに論文では object に対して上位は回転をさせたものを加えたりして表現力を向上させていたりするが、そこまで本質的な improve がないので割愛する。

[yoheikikuta]

分類：

検索：

[yoheikikuta]

扱うオブジェクトの数を変えた場合の性能の変化：

[yoheikikuta]

処理速度は Titan GPU を使って、SUN-397 (13万枚の画像) に対して 0.1 sec 程度とのこと。ただしデータ数に対して線形なので、数百万枚とかになると厳しい。そこを近似的にして探す方法はあるので然るべく適用すればいいとは思うが。