遥かへのスピードランナー

シリコンバレーでAndroidアプリの開発してます。コンピュータービジョン・3D・アルゴリズム界隈にもたまに出現します。

トップ > CV

AKAZE特徴量の紹介と他特徴量との比較

CV 画像認識

1月6日追記：作者のPablo氏とメールのやり取りをする中で、当初掲載していたスピードのベンチマークはコンパイラの最適化オプションが指定されていなかったことに気づきましたので、最適化オプションを指定して再度計測し、結果を差し替えました。

2012年のComputer Vision Advent Calendarで、さかな前線 » ECCV2012で発表されたKAZE局所特徴量を試してみた という記事を見て以来、ずっと気になっていた、KAZE特徴量を自分でも使ってみようと色々試していたところ、KAZE特徴量を高速化したAKAZE特徴量が公開されていることに気づきました。

AKAZE Features

僕の用途は、Android上のカメラプレビューからの特定物体認識なのですが、SIFTやSURFは特許問題があるし、KAZE特徴量はとにかく遅くて困っていた*1ので、これは渡りに船です。さっそく試してみたので、AKAZEの簡単な紹介と、他特徴量との比較ベンチマークを公開したいと思います。

AKAZE特徴量とは

作者のページによると、AKAZEのもととなっているKAZEのアイデアは、SIFTやSURFで使われているGaussian filterによるスケールスペースは、Gaussian filterが等方的であるため、オブジェクトのエッジもぼやかしてしまい、局所的な特徴をうまくとれないことがある。それを解決するために、非線形で非等方的なスケールスペースを使いましょう、というもの*2。

さらにAKAZEでは、Feature Descriptorとして、Modified-Local Difference Binary (M-LDB)という独自のDescriptorを使用し、さらにピラミッド構造の計算を高速化するための独自の工夫を組み入れることで、ロバスト性の向上と高速化を図った、ということです。

 

AKAZEのOpenCVへの組み込み

AKAZEのソースコードは、githubに公開されています。

AKAZE - https://github.com/pablofdezalc/akaze

素の状態でもわりと使いやすいのですが、OpenCV feature2dのcommon interfaceに対応しているとさらに使いやすいと思ったので、それに対応したバージョンを以下で公開しています*3。

AKAZE - cv::Feature2D API wrapper: https://github.com/thorikawa/akaze-opencv

詳しい使い方は、main.cppを見てください。以下のような使い方ができます。

Mat img = imread(...);
std::vector<KeyPoint> keypoints;
Mat descriptors;
Ptr<FeatureDetector> detector = FeatureDetector::create("AKAZE");
detector->detect(img, keypoints);
Ptr<DescriptorExtractor> extractor = DescriptorExtractor::create("AKAZE");
extractor->compute(img, keypoints, descriptors);

比較ベンチマーク

実際どれだけの性能なのか、他の特徴量との比較ベンチマークをとってみました。ベンチマークツールとしては、thorikawa/OpenCV-Features-Comparison · GitHub
を利用しており*4、Lenaさん画像を回転させたりスケール変化させたりしながら、特徴点対応の正確さを計算しています。なお、パラメータは全てデフォルトですので、チューニング次第で結果は異なります。（当たり前ですが）

スケール変化耐性

f:id:thorikawa:20140105204614p:plain
[f:id:thorikawa:20140105195310p:original]

回転耐性

f:id:thorikawa:20140105195306p:plain

輝度変化耐性

f:id:thorikawa:20140105195302p:plain

Blur耐性

f:id:thorikawa:20140105195254p:plain

スピード

注意：当初掲載していたスピードのベンチマークは、コンパイラの最適化オプションを指定せず計測したものでしたので、最適化オプション付きで再度計測し、結果を差し替えました。

Algorithm Average time per Frame (ms) Average time per KeyPoint (ms)
AKAZE 30.4636 0.208972
KAZE 108.736 0.553694
ORB 5.78174 0.015048
SIFT 44.0598 0.161384
SURF 20.917 0.0444678

スピードに関して１点注意事項があります。AKAZE/KAZEのコードはOpenMPでの並列化に対応しているのですが、このベンチマークではOpenMPを利用していません*5。Pablo氏からの指摘によれば、AKAZEのロジックは並列化に向いているため、OpenMPの利用により大幅なスピードアップが見込めるとのことです。OpenCVのSIFTとSURFのコードを見たところ、SIFTのコードは並列化していませんが、SURFのコードは並列化しています。上記ベンチマークのSURFの速さは、それも起因していると思われます。

参考：最適化オプション指定前の計測結果

Algorithm Average time per Frame (ms) Average time per KeyPoint (ms)
AKAZE 117.458 0.797077
KAZE 741.112 3.75878
ORB 5.77404 0.0151431
SIFT 41.0728 0.147772
SURF 18.4614 0.0391613

結論

画像変化のロバスト性については、スケール・回転・輝度・Blur全てにおいて、AKAZEが最も良い数値を示していることが分かります。実際使ってみた感じでも、かなり正確にトラッキングしている感じがします。

スピードに関しては、SIFTやSURFに比べてもかなり遅いです。スピードに関しても、SIFTやSURFに比べて同程度、もしくはそれ以上です。作者のPablo氏によると現在も改良を続けているとのことで、今後も期待できます。

このブログによると、SIFTやSURFよりもライセンス的に使いやすいオープンソースな特徴量を目指して作られたということで、画像認識で商用化を狙っている人たちには朗報ではないでしょうか。

Pablo氏は、もしAKAZE/KAZEを利用する場合は自分に教えてほしい、と言っています。実績づくりや、今度の改善に貢献するためにも、興味のある方はgithubに記載されているアドレスに連絡をとってあげてください。

*1:平均的な画像サイズで、特徴点検出〜マッチングまで10秒以上かかる

*2:どのように非線形なスケールスペースを構築するのか、というところまでは理解しきれていません

*3:作者のPablo氏もOpenCVに対応させると言っていますが、まだ対応されていないようです

*4:Ievgen氏が公開されている https://github.com/BloodAxe/OpenCV-Features-Comparison のfork

*5:OpenMPに対応していない、Androidでの利用をメインに考えているため

AndroidとOpenCVで試す特定物体認識

android CV

6月2日に開催されたDevLOVEさんと弊社の共同開催勉強会で、「Android×ComputerVision」というお題で発表してきました。
要はOpenCVをAndroidアプリに組み込んで特定物体認識を試そう、というもの。

資料は以下です。

20110602_MTI×DevLOVE発表資料「Android×ComputerVision」

ソースはgithubで公開してます。
https://github.com/thorikawa/AndroidObjectRecognition/

概要

資料にも記載していますが、カメラのプレビュー画像からSURFの特徴点を検出して、LSHで再近傍検索→特定物体認識というのを毎フレーム行っています。
「物体」はCDのジャケット画像を5枚の内から認識して、それぞれの画像にあった音を鳴らす、というデモを行い、うまく認識することができました。

構成・ビルド方法

チェックアウト後のソースは

  1. OpenCVをAndroidから利用しやすくするためのOpenCVプロジェクト(android-jni以下)
  2. アプリのプロジェクト(apps/ObjectRecognition以下)
  3. 検出対象の画像から特徴点を検出しておくユーティリティ(dump_keypoints.cpp)

の3つから構成されています。
上記1番はAndroidライブラリプロジェクトとなっており、2番から参照されているため、Eclipseでビルドする場合は、両プロジェクトをimportしておく必要があります。
また、検出対象となる物体の特徴ベクトルはapps/ObjectRecognition/assets/keypoints以下にテキストファイルが配置されています。追加したい場合は、dump_keypointsでダンプした結果をここに追加し、2番のJavaソースで読み込んでいる箇所を修正してみてください。

チェックアウト後のソースには、ビルド後のバイナリも含まれていますが、自分でビルドしたい場合、
apps/ObjectRecognition
に移動してantコマンドを実行することでAndroidアプリをビルドすることができます。

$ cd ${checkoutdir}/apps/ObjectRecognition
$ ant debug

改変方法

ソースを自分でいじりたい場合、アプリ側のJavaソースだけならチェックアウト後のソースをそのまま変更することができます。
c++部分のソースをいじりたい場合は、AndroidをターゲットにしてOpenCVをビルドできる環境が必要です。
まだ環境を構築していない人は、
http://opencv.willowgarage.com/wiki/Android
を参考に環境構築してみてください。

課題と考察

SURFの特徴点検出がとにかく遅いです。濃淡の差が細かく激しい画像だと、1回の検出処理に約3sec程かかります。
OpenCVは、他にもデフォルトでSTARやFASTなどの特徴点検出アルゴリズムを搭載しており、これらの方がSURFよりも速いのですが、精度のチューニングが間に合わなかったため、SURFで実装しています。
実用化に向けては、速度と精度のバランスを取ったチューニングを行う必要があります。（←そりゃそうだ）

また、今回は毎回LSHに突っ込む特徴ベクトルを毎回読み込んでいるため、

  • 特徴ベクトルのデータが膨大
  • 特徴ベクトルの読み込みに時間がかかる

という問題があります。
原理的には計算されたハッシュ値だけをデータとして持たせておけば再近傍の計算はできるはずなので、その部分も課題となります。

CV最先端ガイド勉強会でSVMについて発表してきました

CV 画像認識

本日開催された第９回「コンピュータビジョン最先端ガイド」勉強会＠関東でSVMの章を発表してきました。
SVMはPRML読書会でも発表しているので、資料は半分くらい流用です。悪しからず。

コンピュータービジョン最先端ガイド2 3.4ベクトルデータに対するカーネル法（SVM)

SVMをちゃんと勉強しようと思うと、双対定理から二次計画問題、カーネル法などかなり幅広い知識が必要で、2回目の発表でも、自分自身勉強不足を痛感させられます。今回は特に、ラグランジュ未定定数法と双対定理については、内容を諳んじれるように頭に叩き込むようにしました。未だに参考書がないと内容が出てこないので。またlibsvmなどのライブラリを自分でも使い始めたので、パラメータとSVMの汎化性能については身を持って知ることができた点は良かったと思っています。

勉強会では、特にカーネルの選び方について、参加者の間でも熱い議論が交わされました。僕は資料に「ガウスカーネルだけで問題ないでしょ？」的なことを書いていたんですが、僕の前の発表でその説は叩きのめされ、僕も考えを改めることになりました。

たとえば、第3章6節には、畳み込みカーネルという（実数ベクトル以外の）構造化データに対するカーネルの例が上げられています。このような例を見たのは初めてで、なるほどガウスカーネル以外のカーネルも重要なのだなあと実感することができました。

また、実数ベクトルではガウスカーネルが使われることが多いと思うのですが、多項式カーネルの方が綺麗に線形分離できるケースもあるだろうという意見もありました。まあそういうケースもあるかもしれない、とは思うのですが、いまいち実例が思いつきません。例えば、スイスロールを例に上げると、ちょうどスイスロール上の境界線で線形分離できるようなカーネルを見つける、みたいなイメージでしょうか。このあたりも今後実践経験で学んでいければよいな、と思います。