のんびり読書日記

日々の記録をつらつらと

bayonを使って画像からbag-of-keypointsを求める

Programming

クラスタリングツールbayonとOpenCVを使って、画像からbag-of-keypointsを特徴量として抽出する手順について書きたいと思います。bag-of-keypointsは自然言語処理でよく使用されるbag-of-words(文章を単語の集合で表現したもの)と同じようなもので、画像中の局所的な特徴量(keypoint)の集合で画像の特徴を表します。bag-of-wordsと同じ形式ですので言語処理と同じように、bag-of-keypointsデータを使ってクラスタリングツールに適用したり、転置インデックスに載せたりといったことが可能になります。

今回は画像からbag-of-keypointsを取り出し、そのデータを使ってbayonで画像集合をクラスタリングするところまでやってみます。ちなみに画像処理は完全に素人で、この記事もニワカ知識で書いているので、間違っている箇所やもっと効率のいい手法があるかもしれません。その際は記事にコメントいただければ幸いですm(_ _)m

bag-of-keypoint抽出手順の概要

  1. 各画像から局所特徴量を抽出する
  2. 局所特徴量をクラスタリングし、クラスタの中心をvisual words(代表的なパターン)とする
  3. 各局所特徴量に対し一番近いvisual wordを求め、画像全体の特徴量をvisual wordsのヒストグラム(bag-of-keypoints)で表現する

画像の局所特徴量はSIFTを使います。SIFTでは画像中の特徴的な点(keypoint)をいくつか抽出します。各keypointは128次元の特徴ベクトルとなり、抽出されるkeypointの数は画像によって異なります。このようにkeypointごとに特徴ベクトルを持つため、画像全体の特徴ベクトルを表すにはそのまま使用するのは困難です。

そこで局所特徴量をクラスタリングして各クラスタの中心ベクトルを特徴的なパターン(ここではVisual Wordsと呼ぶ)とし、各局所特徴量は最も近いVisual Wordで置きかえることで、画像全体の特徴をVisual Wordの頻度(ヒストグラム)で表現することができます。このVisual wordのヒストグラムをbag-of-keypointと呼びます。

SIFTやbag-of-keypointsについては、以下の資料が非常に分かりやすかったので、より詳しく知りたい方はそちらをご参照下さい。

必要なもの

OpenCVのバージョンが2.0以降の場合は、SIFT Feature Detectorをコンパイルする時は以下のページを参考にしてソースコードを修正しておいてください。

画像データはとりあえずcaltech101を使用しますが、別で用意できるのであれば何でも構いません。

1.局所特徴量を抽出してbayonの入力を作成

まずはSIFT Feature Detectorを使って各画像からSIFTを特定し、bayonに適用する入力ファイルを作成します。以下のように実行してください。"/path/sift/bin/siftfeat"はSIFT Feature Detectorをビルドした時に生成される実行プログラムのパスです。

% mkdir data
% find /path/caltech101 -name "*.jpg" | ./save_sift.pl /path/sift/bin/siftfeat data/siftmap.tsv > data/input.tsv

SIFTの各座標を1つのドキュメントとして出力します。このとき各座標に固有のIDを割り振るので、各画像中のSIFT特徴量がどのIDに採番されたかを data/siftmap.tsv に保存しておきます。

2. 局所特徴量をクラスタリングしてVisual Wordsを特定

次に上記のSIFT特徴量をクラスタリングします。得られたクラスタの中心ベクトルがVisual wordsになります。

ただし実行環境によっては、すべてのSIFT特徴量をクラスタリングするにはメモリが足りない場合があります。そこでランダムにいくつかの座標を抜き出して、その座標のみでクラスタリングを行うようにします。下記では入力ファイルからランダムに10分の1行選択してます。本来なら各カテゴリから均等に選択するようにした方がよさそうですが、今回は全体からランダムに抽出します。

% ./rand_line.pl data/input.tsv 10 > data/input_10.tsv

では次にクラスタリングを行います。bayonを使って以下のように実行してください。

% bayon -l 1.5 -c data/centroid.tsv --clvector-size 128 data/input_10.tsv > /dev/null

クラスタの中心ベクトル(これが visual words になります)を data/centroid.tsv に保存しておきます。その際デフォルトでは50次元までしかベクトルの要素を保存しないので、中心ベクトルのサイズをSIFTと同じ128次元に指定しておく必要があります。またクラスタリング結果そのものは特に使わないので、/dev/nullに流し込んで廃棄します。

各SIFT特徴量に最も近いvisual wordを特定しbag-of-keypointsを作成

次に各SIFT特徴量に対し、一番類似しているvisual wordを特定します。これはbayonの-Cオプションでさくっとできます。一番近いものだけ分かればいいので、--classify-size=1 を指定して類似するベクトルの出力を1つだけにしておきます。結構時間がかかるので気長に待ちます。

% bayon -C data/centroid.tsv --classify-size 1 data/input.tsv > data/classify.tsv

最後に各画像の特徴量をvisual wordsのヒストグラム(bag-of-keypoints)で表現します。

% ./assign_vwords.pl data/siftmap.tsv data/classify.tsv > data/bok.tsv

得られたbag-of-keypointsは以下のようになります。

% cat data/bok.tsv
/path/caltech101/101_ObjectCategories/accordion/image_0001.jpg 20  1   39  1   59  1   77  1   79  1   120 6   122 1   144 2   167 1   200 1
...

先頭が画像ファイル名で、それ以降は "visualword_id1 \t count1 \t visualword_id2 \t count2 ..." となります。visualword_id部分が例えば「りんご」「大根」のような単語に変えてみれば、これはbag-of-wordsとまったく同じ表現であることが分かります。

ここでちょっと思ったのですが、bag-of-keypointsは別に一番似ているものの頻度じゃなくて、似ているもの上位5個ぐらいの類似度(0〜1)を合わせたベクトルでもいいんじゃないかな...？まあとりあえず今回は文献のやり方に従います。

画像集合をクラスタリング

作成したbag-of-keypointsを使って、画像集合をbayonでクラスタリングしてみます。caltechは総数が9143個ですが、とりあえず500個のクラスタに分割します。またbayonを実行する際、--idfオプションをつけて特徴ベクトルに補正をかけることにします。

% bayon -n 500 --idf data/bok.tsv > data/cluster.tsv

少しクラスタリング結果を眺めてみた印象だと、人の顔はよく解析できているけど、ボロボロのクラスタが結構な割合であるので、もう少し改善が必要な感じでした。bayonの精度がいまいちなのか、bag-of-keypointsの結果がいまいちなのかをちゃんと検証できてないのがダメなのですが、まあとりあえずある程度は使えるかなと。

なかなかうまくできたクラスタをいくつか載せておきます。


まとめ

bayonを使って画像からbag-of-keypointsを抽出しました。また抽出結果を使用してbayonで画像集合をクラスタリングし、ある程度の精度が得られていることを確認しました。bag-of-wordsと同じ形式ですので、他にも既存の検索エンジンや分類器に入れたりといったこともできると思います。ゆくゆくは類似画像検索が作れればいいなーと妄想してます。

また今回は局所特徴量にSIFTを使用したのですが、SIFTは特許が取られているので商用で使う場合はちょっと厳しそうです。そこでSIFTと同じような局所特徴量としてSURFというアルゴリズムがあるようですので、現在これを使ってbag-of-keypointsを求めるよう実装中です。SURFはOpenCVにも入っているので比較的簡単に使えます。

あと今回はコマンドラインから一つ一つ呼び出すようにしてましたが、実際に使うときは面倒なので、もう少しまとめた形で実装し直して公開したいですね。

追記：SURFも特許がとられてたいたため、商用利用は許可がいるようです。

結局のところ商用で局所特徴量は何を使うのがいいんですかね？知識が足りなさ過ぎる…。