読者です 読者をやめる 読者になる 読者になる

MNISTをSURFを使ったbag of keypointsで

とにかく早く動かす欲で半分くらい想像でやってしまったので、誤りがあれば指摘などなど。

SURFとは!

SURFは回転とスケールに不変な特徴点検出アルゴリズムで、keypoints(点の位置とスケール)とdescriptor(正規化された勾配のヒストグラム)を得ることができる。
このdescriptorsを画像の局所的な(画像パッチの)特徴ベクトルと考えると、画像に含まれるSURF Descriptorの集合を(十分大きければ)画像のidentificationとすることができる。

大まかな内容

  • MNISTの学習データからSURF Descriptorを抽出する
  • ベクトル量子化のためのコードブックを作成する
    • 抽出したSURF Descriptorをk個にクラスタリングする
    • 各クラスの重心をコードベクトルとし、クラスをvisual-wordという単語の単位にする
  • 画像をグローバルな単語の集合と考えると、文章分類で使うような単語の頻度に基づいた特徴ベクトルで表すことができるので、これを分類する。

具体的に行ったこと

まず、MNISTの学習データ6万件からOpenCVのSURF実装を使って140万個(1画像平均23.3個)のSURF Descriptorを抽出した。SURFの特徴点は画像が小さすぎると抽出できないようだったので、元画像(28x28)の左右上下に18pxのパディングを入れた64x64の画像を作ってそれを128x128に拡大した画像から抽出するようにした。
このSURF Descriptorを128次元(拡張ありだとそうなる)のベクトルとして、k-means++で2048クラスに分類し、各クラスの重心をコードベクトルとするコードブックを作成した。
次に各データのSURF Descriptorをコードベクトルに対する最近傍探索でコードブックの添え字に変換し、それを単語IDとして、単語IDの頻度を軸とした2048次元の特徴ベクトルとした。これを学習データセットとテストデータセットに対して行った。
あとは、普通の分類問題と同じように教師あり学習で分類器を学習し、テストを行った。分類器は、前回も使った多層パーセプトロン(中間層素子64)を使った。

結果


89.38%

感想

この方法は点の位置関係を使っていないので、そんなにいい結果は出ないと思っていたけど思っていたよりはよかった。回転不変な局所特徴の集合だと6と9は同じじゃね?とか思っていたけど、手書き文字だとそうでもないらしい。
テスト画像が回転・位置ズレ・スケールの変更などされていた場合でも同じ結果になるはずなので、長所はある。しかし、MNISTにそんな評価基準はないので、まあ適切ではないよねと思った。
実装面では、k-meansの収束条件がデータ数に対して厳しいのか、そんなものなのか、全然終わらなかったので、50ステップで打ち切るようにした。128次元を140万件というと多い気がするけど、OpenMPとSSEを駆使したオレオレ実装のk-means++だと1ステップ60秒程度だったので、まだ余裕あることが確認できた。
前にやっていたShape Contextでも特徴点とその周辺の勾配ヒストグラムを使っていて、これは回転不変性がなかったので、これをSURFにしたらいいんじゃねーと思った。ただ、Shape Contextは点の割り当て問題を解くのがめちゃくちゃ遅いので試したくなかった。
クラスがもっと増える状況だと多層パーセプトロンのような学習器は使えないので、点ごとに近傍のデータを集めながらラベルをランキングして決定するような方法にしないといけないので、そこでLSHやFLANNの出番かーと思った。
おわり。

今後は

LDAとか使って画像の分類を試したいですね。そしてAnimeFaceと合体させてキャラクタ画像自動フォルダ分類ツールとか作って(略) #_金くれ

実験コード

未公開オレオレライブラリを使っているので動かないし、コメントアウト位置を変えながらコンパイルすることで機能を変えたりしているひどいものですが、上の説明の補足程度に。
MNIST: bag of keypoints