プリパラのアイテム画像をBoVWで分類する
私はプリパラのことがとても好きだしプリパラのことを考えている時だけ”生きている”という感じがします。 皆さんもきっとそうだろうと思います。
しかしパソ君にとってはどうでしょうか？ パソ君は我々の生活になくてはならないものですが、パソ君はプリパラのことを”理解”しているでしょうか？ このパソ君の無機質な表情からはとてもそうは思えません。
パソ君にはプリパラを理解してもらう必要があります。 これはプリパラが現実を侵食するために絶対に必要なことです。
なんと幸いなことにプリパラの公式サイトにはプリパラのアイテム画像がしかもメタ情報付きでアップロードされています。
パソ君を調教するのにこいつを使わない手はないでしょう。
ということでパソ君にプリパラのアイテム画像を｛アゲアゲアイテム、ヘアアクセ、トップス、ボトムズ、ワンピース、シューズ｝の6種類に分類させることで、パソ君のプリパラに対する理解を深めてもらいました。 （識別率の絶対値よりも、プリパラの画像を認識する際の傾向を調査するのが本当にやりたいことだったりします。また、後で述べますが重大な実験上の誤りを見逃しています。）
今回採用したのはBag of visual words (BoVW)という方法です。
画像は生のRGBであれば各ピクセルに対し8*3=24bitの情報があり、画像全体の情報はそれのピクセル数倍になります。 冗長な情報が多く含まれているので生の画素値をそのまま使うのは最悪のアプローチで（あると普通は思いま）す。（CNNはそこを上手くやってしまうわけですが、それは置いておいて）
そこで画像を認識する際によく使われ（ていた）るのが局所特徴量というやつです。 局所特徴量の抽出はまずdetectorで特徴点を検出し、次に各特徴点に対してdescriptorで特徴ベクトルを算出するという2つのステップからなります。 局所特徴量はある画像に対して、特徴点と特徴ベクトルのペアの集合として定義されます。
ここで第一に問題になるのが、画像によって抽出される特徴点の数が違うということです。 画像ごとに局所特徴量の次元数が変わるので、ここままではよく使われている機械学習の手法をそのまま使うことができません。
第二の問題は、異なる画像に似たような特徴ベクトルが多く含まれている場合があるということです。 例えば、他の画像と全く違う局所特徴量が1つ抽出されたとしても、他の画像とよく似ている局所特徴量が10個抽出されたのでは、画像をパソ君に区別させるのは難しいです。
（私の理解では）以上2つの問題を解決したのが、BoVWというやつです。
まず、学習データから局所特徴量を抽出します。 そして、特徴ベクトルに対しクラスタリングを行いK個のクラスタに分類します。 最後に各画像の各特徴ベクトルに対し、クラスタ重心との最近傍探索による投票を行い、K次元のヒストグラムを作成します。 このK次元のヒストグラムを画像の特徴量とするのです。
第一の問題は全ての画像が同じK次元の特徴量を持つので解決しますし、第二の問題も多くの画像に含まれる似た特徴ベクトルは同じクラスタに潰れるので解決します。
解説はググれば色々でてきます。
ノウハウに関しては以下の記事が大変参考になりました。
何をしたのか
BoVWでプリパラのアイテム画像を｛アゲアゲアイテム、ヘアアクセ、トップス、ボトムス、ワンピース、シューズ｝の6種類に分類した。 局所特徴量の種類とクラスタ数を変えて識別率を比較した。 データは公式サイトにあるラベル付き画像データを使った。
この実験で明らかにしたかったこと
- どれくらい性能でるのか？
- どの局所特徴量が性能が良いのか？
- クラスタリングの次元数を上げるとどれくらい性能は上がるのか？
実験環境
ソフト：Windows、Python 3.4.1、OpenCV 3.0RC（特徴抽出からヒストグラム作成まで）、scikit-learn（SVMによる識別）
データ：2015/07/25時点にプリパラ公式サイトにアップロードされていたアイテム画像（ アゲアゲアイテム：127、 ヘアアクセ：247、 トップス：328、 ボトムス：288、 ワンピース：296、 シューズ：473、 合計：1759 ）
画像サイズ：｛256×256｝（元サイズは｛512×512｝）
局所特徴量：｛KAZE, AKAZE, ORB, BRISK｝
クラスタリングの次元数（K）：｛128, 256, 512, 1024, 2048, 4096, 8192｝
識別器：SVM（RBFカーネル、C=1、Γ=8、1対1分類器による6クラス識別）
評価方法：5 fold cross validationを行う。5つのfoldの識別率の平均値で評価する。
表1：実験に使った局所特徴量
| 特徴量名 | dense sampling方法 | 種類 | 距離尺度 | OpenCVのコンストラクタ(特徴量名_create())のパラメータ | 引用 |
|---|---|---|---|---|---|
| KAZE | 特徴点検出の閾値を0にする | 実数 | ユークリッド距離 | threshold=0.0 | KAZE Features. Pablo F. Alcantarilla, Adrien Bartoli and Andrew J. Davison. In European Conference on Computer Vision (ECCV), Fiorenze, Italy, October 2012. |
| AKAZE | 特徴点検出の閾値を0にする | バイナリ | ハミング距離 | threshold=0.0 | Fast Explicit Diffusion for Accelerated Features in Nonlinear Scale Spaces. Pablo F. Alcantarilla, Jesús Nuevo and Adrien Bartoli. In British Machine Vision Conference (BMVC), Bristol, UK, September 2013. |
| BRISK | 特徴点検出を使わず、背景以外から4点置きにサンプリング | バイナリ | ハミング距離 | thresh=0.0 | Stefan Leutenegger, Margarita Chli and Roland Siegwart: BRISK: Binary Robust Invariant Scalable Keypoints. ICCV 2011: 2548-2555. |
| ORB | 特徴点検出を使わず、背景以外から4点置きにサンプリング | バイナリ | ハミング距離 | edgeThreshold=11, patchSize=11 | Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary R. Bradski: ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571. |
上記記事のように、detectorによる特徴点検出を使わず密に等間隔にサンプリングした点に対して特徴ベクトルの算出を行うdense samplingを行いたかったのですが、KAZEとAKAZEではそれができませんでした。（OpenCVのドキュメントにもできないとはっきり書いてありました） そこでKAZEとAKAZEについては特徴点検出の閾値を0にし可能な限り多く特徴点を算出することでdense samplingを代用しました。 こんな感じです。（特徴ベクトルを算出した点を黄緑で示しています）
図1：AKAZEで検出された特徴点の例
ORBとBRISKについてはdetectorを使わず背景を除く4ピクセル置きに特徴ベクトルを算出しました。dense samplingを行ってくれる関数がOpenCV3.0からなくなってしまっていたので、この処理は自分で実装しました。本来はスケールも変えたほうがいいはずですが、自分で書くのは大変だったのでやめました。（C++のオレオレ実装はネットで見つけましたが今回はPythonなので使えませんでした。） こんな感じです。（特徴ベクトルを算出した点を黄緑で示しています）
図2：密にとった特徴点の例
特徴点が多い＝特徴ベクトルが多いほど、特徴ベクトルのクラスタリングの信頼度が高まるはずです。（こんな表現をしたら確率統計マンに殺害されそうだけど上手い言い方がわからない） より正しくクラスタリングの重心が求まれば、より高い識別率が期待できるでしょう。 画像をみてわかるように今回使っている特徴点の数はORBやBRISKのほうが遥かに多いです。 仮にKAZEやAKAZEのdescriptorの性能が良かったとしても、特徴ベクトルの数が全く違うのでORBやBRISKのほうが性能が良いではないかと予想できます。
実験結果
予想通り、BRISKとORBのほうがKAZEとAKAZEより識別率が良いという結果になりました。 BRISK＞ORB＞AKAZE＞KAZEという順序になりました。
表2：識別率とクラスタ数の関係
| クラスタ数 | KAZE | AKAZE | BRISK | ORB |
|---|---|---|---|---|
| 128 | 0.701 | 0.739 | 0.842 | 0.814 |
| 256 | 0.720 | 0.753 | 0.865 | 0.843 |
| 512 | 0.766 | 0.793 | 0.901 | 0.868 |
| 1024 | 0.822 | 0.839 | 0.914 | 0.883 |
| 2048 | 0.835 | 0.850 | 0.925 | 0.898 |
| 4096 | 0.866 | 0.860 | 0.937 | 0.906 |
| 8192 | 0.861 | 0.876 | 0.936 | 0.916 |
図3：識別率とクラスタ数の関係
考察
この実験から言えるのはdescriptorの性能はKAZEよりAKAZEのほうが良く、またORBよりBRISKのほうが良いということです。 特徴点の取り方が全然違うので識別率の絶対値が高いからといって一概にORBやBRISKのほうがKAZEやAKAZEより良いとはいえません。
手を動かす前はAKAZEが一番新しいのでAKAZEが一番性能がいいのではないかと思っていましたが、そうはなりませんでした。
KAZEとAKAZEの特徴は特徴点検出にあると私は考えています。 SHIFTやSURF等（今回は比較していませんが）のdetectorはDoG（Difference of Gaussian）ですが、これはエッジまでもぼかしてしまい微細な特徴点が検出できないという問題がありました。 ORBとBRISKのdetectorはFASTベースで、これは速いのですが誤検出が多い印象があります。 一方、KAZEとAKAZEではエッジを選択的に残すnon-linear diffusionを使い、微細な特徴点も比較的正確に検出することができます。（のようなことが論文に書いてあります、たぶん）
今回はdetectorを活用しきれなかったのでAKAZEの性能が伸びなかったのではないかと考えています。
不正行為
この実験では最悪なズルをしていて、特徴抽出を行う際の学習データにテストデータが含まれています。 全データから抽出した全特徴ベクトルに対してK-meansをかけ重心を求め、その重心とマッチングを行うことで全データのヒストグラムを作成しています。 （認識時はcross validationをしています。あるfold以外のヒストグラムを使って識別器を学習し、そのfoldでテストしています）
正しくは各foldに対し、それ以外のfoldに含まれる特徴ベクトルに対してクラスタリングを行いクラスタ重心を求め、そのクラスタ重心に対してヒストグラムを作成すべきです。 本当は、学習時にはテスト時に入ってくるデータの特徴ベクトルなんて知らないはずですから。
全部終わる頃になって、これはダメダメダッメーズルズルズッル－だよと気づきましたが、ただでさえクラスタリングにめっちゃ時間がかかったし、foldごとにクラスタリングするとなると約fold数倍の時間がかかるはずなのでめんどくさくなってやめました。 これは本当はやってはいけないことですが、これは実験レポートでも論文でもないし、なんとなく傾向がわかったのでまあよしとしましょう。
何が言いたいかというと、識別率の絶対値にあまり意味はありません。識別率は全体的に本来の値より高くなっていると思われます。
この実験で明らかになったこと
- どれくらい性能でるのか？→90%くらい。しかしズルしてるので本当はもっと低いはず。
- どの局所特徴量が性能が良いのか？→今回比較した中ではBRISKが一番よかった。descriptorの性能もあるが密に特徴ベクトルを算出したことの影響も大きいはず。
- クラスタリングの次元数を上げるとどれくらい性能は上がるのか？→次元数2倍で識別率は数%上がる
結論
パソ君の調教にある程度成功した。パソ君がプリパラの素晴らしさを理解し始めたのは大変良いことだ。
その他
Kを大きくするとクラスタリングはめちゃくちゃ時間がかかりました。K=8192でcore i7のコアを全部使って半日くらいかかったと思います。
また、ユークリッド距離しかサポートしていないK-meansライブラリを使ってバイナリ特徴量をクラスタリングする際はちょっと注意しないといけないのですが、それについては気が向いたら書きます。
余談ですが、プリパラ公式サイトのHTMLはニンゲンの手のぬくもりが感じられるHTMLで、本来”トップス”が入るべきところに”ラブリー”が入っていたりして全自動でスクレイピングできませんでした。 どうも世界を支配するプリパラの”システム”が作っているのではないようです。
