ベクトル量子化

はてブのコメントを見たのと、僕もbag of keypoints関係の論文を見たときに一瞬で分かったつもりになってそれを信じ続けていたけど不安になったのでググったところ別に間違ってもいなさそうだったので、ここでたまに書いてるベクトル量子化とは何かという話とそれをなぜ使っているのかという話を。（僕なりに）
僕がベクトル量子化と言ったときには、単純には
入力ベクトル→クラスラベル(スカラ)
への変換を指している。あらかじめ、K個のクラス(グループ)を定義しておいて、入力ベクトルがどのクラスに属するか推定を行って、属するクラスの番号に変換してしまう。これによって、どんな入力ベクトルも(int)1〜Kのスカラ値に変換できる、というかかなり大雑把だけどそういうことにしてしまう。
具体的な例としては、
まず入力ベクトルとして想定されるデータを適当に集めてそれをk-meansでクラスタリングする。データはK個のクラスに分類されて、各クラスの重心となるK個のベクトル(代表ベクトル)が求まるので、それをコードブック(変換用のテーブル)とする。量子化では、入力されたベクトルと各代表ベクトルとの距離を計算して一番近い(似ている)代表ベクトルのクラスラベル(コードブックの添え字)を返す。
など。

何がうれしいの？

僕が最近やっているアニメ顔類似検索ではSURFというアルゴリズムから得られる特徴点を使って画像同士の類似度を計算していて、それにはベクトルの集合同士の類似度を求める必要がある。
具体的な例を出すと、まず画像からSURFの特徴点(キーポイント)を検出すると
http://www.udp.jp/g/1vA.pnghttp://www.udp.jp/g/T_.png
こんな感じになって(このキャプチャは昔のやつなのであくまでイメージで)、この黒い丸の中心が特徴点の座標で丸の大きさがスケール(大きさ,範囲)を表している。また各特徴点(の記述子)は中心から丸の範囲の画素の並びによって64次元の実数ベクトルで表現されているので、画像はベクトルの集合で表現されていることになる。
これを使って画像同士がどの程度似ているかを計算しようとすると、単純には特徴点同士の非類似度(似てない度)をコストと置いてコストの合計が最小となるような点の組み合わせを割当問題として解いたときの合計コストを画像の非類似度とすればいいーとか思うわけだけど、それだと計算量が大きいとか検出されている点の数が全然違うやんけいった問題があるので、思い切って次のようにしてしまう。

  • 特徴点の位置関係やスケールは無視して単純な集合としてしまう [ bag of keypoints (袋の中に特徴点を詰めたイメージ)]
  • 各特徴点を表す64次元のベクトルをベクトル量子化して(int)1〜Kのスカラ値にしてしまう [visual-words (K種類の単語に置き換える)]

こうすると、

int クラスのヒストグラム[K] = { 0 };
vector 特徴点;
foreach 特徴点 (画像に含まれる特徴点たち) {
   int クラスラベル = ベクトル量子化(特徴点);
   ++クラスのヒストグラム[クラスラベル];
}

と、K個のビンがあるヒストグラムによって画像に含まれる特徴点の集合が表せるようになる。意味としては、画像にどのクラスに属する特徴点がどれだけずつ含まれているのか？といった情報になる。
KビンのヒストグラムはK次元のベクトルなので、画像をひとつのベクトルで表現できるようになって、よくある類似度や機械学習のアルゴリズムで扱えるようになる。

(おわり)