[機械学習] bayon+LSHIKITを使って画像クラスタリング

bayonを使って画像からbag-of-keypointsを求める - のんびり読書日記の記事を読んで、クラスタリングを行う際の入力データを作るために文献[1]にある方法が利用できると思って実験してみた。

局所特徴量を持ったデータの取扱い

画像データの分類などを行う際にSIFTのような画像中の特徴点(keypoint)を抽出するということがよく行われる。
例えばSIFTを用いる場合は各keypointは128次元のベクトルとなり、画像ごとにいくつかのkeypointが抽出される。ここで抽出されるkeypointの数は画像ごとに異なる。このため、画像間の類似性を比較するのは困難である。

これに対するアプローチとしては一つは画像中の特徴点同士の全対比較を行う、もしくはマッチングをとるという方法が挙げられるがこれは計算量が非常に大きい。
別の方法としてヒストグラムを利用するという方法がある。これは各特徴点を量子化して画像全体を一つの特徴ベクトルに落とすというものである。この特徴ベクトルは量子化した特徴点の頻度のヒストグラムとして表現される。これを行う一つの方法としては[2]で紹介されているVisual Wordの方法がある。

もう一つの方法としては[1]で提案されているLSHを用いたヒストグラムの構成法がある。

LSHを用いたヒストグラムの構成

簡単に[1]の手法を紹介する。LSHが何かについては[3]などを確認してもらうとして、ここでは特徴点をBビットにハッシングする関数があり、似た特徴点は高い確率で同じハッシュ値をとるような関数hが構成できているという元で議論を進める。

画像中の各特徴点に対してLSHを用いてハッシングする、これによって得られるハッシュ関数の値は[0,2^B)の範囲を取る。各値の頻度(ヒストグラム)を計算することによって2^B次元の特徴ベクトルが生成される。これらのヒストグラムを独立にN個生成して連結することによってN * 2^B次元の特徴ベクトルとして1枚の画像を表現する。また、画像にkey-pointが少ないときにヒストグラムに使われない値が多く出てきてしまうのでヒストグラムの作成時に独立なM個のハッシュ関数を適用してその値の頻度を足すという操作(Folding)を加える。

これらの操作を行うことにより、特徴点の集合を特徴点の個数によらない一つのN * 2^B次元の特徴ベクトルとして表現でき、あとは通常のベクトルデータを扱うツールを適用することができる。

実装

[1]の作者が公開しているLSHKITというツールがあり、それに上で述べたヒストグラムを用いた構成法も載っているので実装してみた。プログラムの動きとしては標準入力から画像ファイルのパスを受けとると、そのパスに関するヒストグラムをbayonで用いることのできる形式にして標準出力に出力するというものになってます。[2]の記事と比較するとVisual Wordをbayonでクラスタリングを行い特定して、bag-of-keypointsに出力という部分がなくなって、入力画像から直接ヒストグラムを生成してることが分かる。
利点としては入力の画像のみでヒストグラムを作れるので[2]で述べられているようなVisual Wordの特定にメモリが足りなくなるということがないことが挙げられる。

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

#include <unistd.h>
#include <highgui.h>

#include <lshkit.h>

extern "C"{
#include "sift.h"
#include "imgfeatures.h"
#include "utils.h"
}

using namespace std;
using namespace lshkit;

typedef Repeat<ThresholdingLsh> MyLSH;
typedef Histogram<MyLSH> MyHistogram;

int main(){
  string filePath;
  while(getline(cin , filePath)){
    // load image
    IplImage * img = cvLoadImage(filePath.c_str(), 1);
    if(!img){
      cerr << "unable to load image from " << filePath;
      continue;
    }
    // extract SIFT Features
    struct feature * features;
    int numberOfKeypoints = sift_features( img , &features);
    vector < vector<float> > sift_fs_vector( numberOfKeypoints);
    for(int i = 0 ; i < numberOfKeypoints ; ++i){
      int d = features[i].d;
      vector<float> fs_v(d);
      for(int j = 0 ; j < d ; ++j){
        fs_v[j] = features[i].descr[j];
      }
      sift_fs_vector[i] = fs_v;
    }
    free(features);
    cvReleaseImage(&img);

    // create Histogram
    MyLSH::Parameter param;
    param.repeat = 8; // repeat 8 times, produce 8 bits.
    param.dim = 128;
    param.min = 0.0;
    param.max = 255.0; // Parameters are set for SIFT features.
    DefaultRng rng;
    unsigned N = 10, M = 10;
    MyHistogram hist;
    hist.reset(M, N, param, rng);
    float * output = new float[hist.dim()];
    hist.zero(output);
    for(int i = 0 ; i < sift_fs_vector.size() ; ++i){
      hist.add(output , &sift_fs_vector[i][0]);
    }
    cout << filePath;
    for(int i = 0 ; i < hist.dim() ; ++i){
      if(output[i]){
        cout << "\t" << i << "\t" << output[i];
      }
    }
    cout << endl;
    delete[] output;
  }
  return 0;
}

クラスタリング

最後にbayonを用いてクラスタリングを実行してみた。コマンドは[2]と同様に

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

とした。

得られたクラスタのいくつかを示す。1番めと2番めはそれなりのまとまりを見せているが、3番目はわりとごちゃっとしていてクラスタリングがちゃんとできているとはいえない。



LSHを使ってヒストグラムを構成する部分は結構パラメータがいくつもあるためその部分に関するチューニングとbayon以外のクラスタリング手法を試すことが考えられ、興味深い。また、論文ではSIFTではなくPCA SIFTというものを用いているのでそれを使うことが考えられる。
あとはSVMなどを利用した判別などクラスタリング以外の問題を解くのも面白いかもしれない。

参考文献