RootSIFTのススメ - yu4uの日記

以前、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.