2013/01/31

年賀はがき当たりチェックアプリとSVM(2)

はがき当たりチェックアプリプロジェクトも開始から1週間経ちました。
手作業で確認したほうが早いのですが、まぁ趣味の一部なのでその辺は気にしないことにしましょう。


OpenCVのサンプルコードに、digits.pyというSVMを使って手書き数字を認識するコードがあります。これのデータセットは、20x20ピクセルの画像を5000枚並べたものです。

はがきの番号は手書きとは違って明朝体風の印刷フォントなので、線の太さが一定ではありません。サンプルをそのまま使った場合の認識率はさほどよくありませんでした。

はがきの番号のフォント名がわかれば紙にたくさん印刷してデータセットを簡単に作れるのですが、ググってもフォント名はわかりませんでした。
机の中を漁ったところ、去年の年賀状があったのでその番号だけを切り取って板に貼りつけて、データセットをたくさん作れるようにしました。


あとはデジカメで撮影し、OpenCVで文字っぽいものを自動で切り出し、あとは0から9までの10個のフォルダに人力で仕分けしました。数字の分布が均一では無いため、全ての数字が500枚以上になるまでこの地味な作業が続きました。

そしてサンプルのデータセットと同じように20x20ピクセルに縮小したものを5000枚並べた画像を作りました。これでSVMをトレーニングすると、なかなかいい精度の識別器が出来上がりました。


識別機はできたものの、どうやって特徴量を決めているのかな〜とPythonのソースコードを見たところ、HoGという特徴量を使っているとのこと。
HoGは Histograms of Oriented Gradientsの略で、画像の特定セルの勾配をヒストグラムにするものだそうで。人や車など、大まかな形状を探すものに向いているようです。

参考元(中部大学):

Pythonのチュートリアルでは、20x20の画像を10x10の4つに分けて、 勾配を16に分けてヒストグラムを作っているようです。10x10セル一つで16次元なので、4つで64次元。Huモーメントだと7次元なので、こっちのほうがクラス分けには良さそうですね。
サポートベクターを求めるのにある程度時間がかかりますが、一度サポートベクターを求めてしまえば、あとはファイルに保存したものを読みこめばいいので、PCでSVMの学習をおこなって、Androidに学習ファイルだけを渡せば良さそうです。

次は6桁の数字を判定する部分を作って、今年来た年賀状が当たっているかをチェックしてみたいと思います。


ではまた。

2013/01/22

年賀はがき当たりチェックアプリとSVM


毎年書くのがメンドイ年賀状。
「去年もらったから今年書かなきゃ」的なチキンレースを
私含め全国民がやっているかのようです。

それはさておき、年賀状の下部には「お年玉くじ」がついています。
家の中にある今年の年賀状は約60枚(未使用含む)。宝くじは宝くじセンターにもってけば機械でバババッとチェックしてくれますが年賀状はそうはいきません。

Google Playで探してみたところ、「下2桁を入力して当たりの可能性があれば音がなる」アプリがいくつかありました。
このアプリを使ってもいいのですが、先週末OpenCV for Androidをインストールしたところ。OpenCVは画像処理ライブラリで、OCR機能もあります。

ということで練習がてら年賀状当たりチェックソフトを作ってみることにしました。

ターゲット:OpenCV for Androidが動作する背面カメラ付きデバイス
仕様:
  • VGAサイズの画像を使用する
  • ガイドを表示して一定の位置に年賀状の当たり番号をおいてもらう
  • OCR処理する(印刷モノなのでやりやすいはず)
  • 結果によって音を変える。
  • PCとAndroidで別のコードになるので、移植しやすい関数を選ぶ
開発の流れ
  1. 我が家にある年賀状を10枚ほどピックアップ。うち5枚をテスト用当たり番号とする
  2. デジカメでVGAサイズで撮影。番号を一定の位置に収める
  3. まずはPCでコードを書く。
  4. うまく動いたら本番の番号にきりかえる
  5. 家にある年賀状をチェック!!
  6. あたってても外れてても、うまく動いたらAndroidに移植する。

今のところ3の中間、数字をひとつずつに切り分ける部分までは出来ました。
次はOCR処理のところです。
この前買ったMastering OpenCV with Practical Computer Vision Projectsに、自動車のナンバープレートを認識するプロジェクトの作り方が載っていました。その中で、ナンバープレートを認識するのにSVMを使ったそうです。



SVMはサポートベクターマシンの略で、機械学習の手法の一つ。
中身はよく知らないので、 OpenCV tutorialsに載っているIntroduction to Support Vector Machinesを読んでみます。

原著:Fernando Iglesias García
原題:Introduction to Support Vector Machines

 (Google翻訳+毎度おなじみ適当翻訳でお送りします。画像は元ページのを拝借しています)

================================================

サポートベクターマシン入門

ゴール
このチュートリアルでは、あなたは以下のことを学びます。
  • OpenCVのCvSVM::trainを使ってクラス分類器を作る方法
  • CvSVM::predictを使ってそのパフォーマンスをテストする方法
SVMって何?
サポートベクターマシン(SVM)は分離超平面クラス分類器として定義されます。
言い換えると、ベル付き訓練データ(教師付き学習)を指定すると、アルゴリズムが最適な超平面を出力する分類器です。

最適な超平面とは何でしょうか?以下の簡単な問題を考えてみましょう。
直線を引くと2つのクラスに分類できる2次元の点群があります。





注:この例ではデカルト平面での直線と点を高次元空間の超平面とベクトルとして扱います。これは問題を単純化したもので、この想像しやすい例を使って、どう行われているかを理解することが重要です。しかし、同じ概念をこの例の2次元よりも高い次元でも適用することができます。

上記の画像には、複数の直線が2つのクラスに分けるために引かれています。このうち、どの直線が分類するものとして適しているのでしょうか?我々人間は直感的に直線の価値を決めるための基準を定義することができます。
 直線があまりにも点に近すぎたりするとノイズに弱くなるため、その直線は正しく一般化されたものと考えることはできません。したがって、我々の目標は、 すべての点から可能な限り遠くを通る直線を見つけることです。

すなわち、SVMアルゴリズムの動作は与えられたデータに対し、最小距離が最大となる超平面を探す事になります。


どうやって最適な超平面をもとめるか?
超平面を定義するために使用される表記法は以下のとおりとなります。

f(x) = \beta_{0} + \beta^{T} x,
βは重みベクターでβ0はバイアスとなります。

最適な超平面はβとβ0のスケーリングによって無限の方法で表すことができます。
慣習として、以下の超平面が使用されます。
 |\beta_{0} + \beta^{T} x| = 1

xは超平面に一番近いトレーニングセットのサンプル点です。一般的に、超平面に一番近いサンプルはサポートベクターと呼ばれ、この表現は標準的な超平面と呼ばれます。

さて、超平面とサポートベクターとの距離を表す式を以下に表します。
 
\mathrm{distance} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||}.

 具体的には、分子が1になるサポートベクターまでの距離は、

\mathrm{distance}_{\text{ support vectors}} = \frac{|\beta_{0} + \beta^{T} x|}{||\beta||} = \frac{1}{||\beta||}.

で、これを2倍したものをマージンMとして扱います。


M = \frac{2}{||\beta||}

最後に、このMを最大化することは、トレーニングセットのすべての点Xiを分類するための要件L(β)を最小化することと同じです。L(β)は正式には
\min_{\beta, \beta_{0}} L(\beta) = \frac{1}{2}||\beta||^{2} \text{ subject to } y_{i}(\beta^{T} x_{i} + \beta_{0}) \geq 1 \text{ } \forall i,
となります。

Yiはトレーニングセットのラベルを表します。
これは、重みベクトルを取得するためのラグランジュ乗数を用いて解くことができる、ラグランジュの最適化問題です。

 ========================中断==============================

う〜ん???

マージンを最大化するところまではまぁなんとなくわかりましたが、ラグランジュ乗数とやらはさっぱり。SVMの日本語解説ページを探したところ、以下のページがありました。

Support Vector Machine って,なに?

先にこっちを読んでおけばよかったかな。。
これを読んでもラグランジュ乗数はさっぱりわかりませんでしたが。



========================再開==============================

ソースコード
 省略。元URLを参照ください。

解説
1.トレーニングデータのセットアップ
 この練習問題のトレーニングデータは、”2つの異なるクラスのいずれかに属している”というラベルのついた二次元の点集合によて形成され、片方のクラスに1点、もう片方に3点という形で構成されています。
float labels[4] = {1.0, -1.0, -1.0, -1.0};
float trainingData[4][2] = {{501, 10}, {255, 10}, {501, 255}, {10, 501}};
CvSVM::train は、floatのMatオブジェクトを必要とするので、上記の配列からMatオブジェクトを生成します。
Mat trainingDataMat(3, 2, CV_32FC1, trainingData);
Mat labelsMat      (3, 1, CV_32FC1, labels);
2.SVMのパラメータのセットアップ
 このチュートリアルは一番単純なケース、つまりトレーニングセットが2つに線形分離可能な場合を扱っています。しかし、SVMは様々な種類の問題(例えば非線形に分離可能なデータ、サンプルの次元を上げるためのカーネル関数を用いたものなど)に使用することができます。そのため、SVMを訓練する前に、いくつかのパラメータを定義する必要があります。これらのパラメータは、CvSVMParamsオブジェクトに格納されます。

CvSVMParams params;
params.svm_type    = CvSVM::C_SVC;
params.kernel_type = CvSVM::LINEAR;
params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);
svm_type:SVMの種類。 Nクラス分類器を使用するため、C_SVCを選びました。
kernel_type:SVMのカーネルタイプ。我々は、トレーニングデータがどう扱われるかについてを考えていなかったため、カーネルタイプについては触れて来ませんでした。ここで簡単にカーネル関数の背後にある主要な考え方の説明をしましょう。これは、訓練データを線形分離可能セットに分類するためのマッピングです。このマッピングは、カーネル関数を使用してデータの次元数を効率的に増やすことで構成されています。我々はマッピングが行われないよう、CvSVM::LINEARを指定しました。
term_crit:終了条件。SVMはトレーニングを繰り返し、制約された二次最適化問題を解く方法で実装されています。アルゴリズムで最適な超平面が計算されていない場合でも、ステップ数の少ないうちに計算を終了することができます。ここでは、最大の反復数と許容誤差の最大を指定します。このパラメータはcvTermCriteriaで定義されます。

3.SVMの訓練
CvSVM::trainを使用して、SVMを訓練します。
CvSVM SVM;
SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);
4. SVMによって分類された領域
CvSVM::predictは入力したサンプルデータがSVMによってどう分類されるかを確認するために使用します。このチュートリアルでは領域ごとに異なる色とし、SVMによって分類されたデータを着色します。言い換えれば、画像のデカルト平面の点はピクセルと解釈されます。それぞれの点はSVMによって予測されたクラスの色に着色され、ラベルが1のクラスを青、ラベルが−1のクラスを緑としています。

Vec3b green(0,255,0), blue (255,0,0);

for (int i = 0; i < image.rows; ++i)
    for (int j = 0; j < image.cols; ++j)
    {
    Mat sampleMat = (Mat_(1,2) << i,j);
    float response = SVM.predict(sampleMat);

    if (response == 1)
       image.at(j, i)  = green;
    else
    if (response == -1)
       image.at(j, i)  = blue;
    }
5.サポートベクター
我々にはサポートベクトルの情報を取得するための2つの方法があります。CvSVM::get_support_vector_countはサポートベクターの合計数を、CvSVM::get_support_vectorはインデックスを指定してそれぞれのサポートベクターを取得することができます。今回は、このサポートベクターを強調するためにこれらのメソッドを使用しています。

int c     = SVM.get_support_vector_count();

for (int i = 0; i < c; ++i)
{
 const float* v = SVM.get_support_vector(i);// get and then highlight with grayscale
  circle(   image,  Point( (int) v[0], (int) v[1]),   6,  Scalar(128, 128, 128), thickness, lineType);
}

結果

画像のすべてのピクセルが入力値です。
SVMに入力した結果、どちらのクラスに分類されたかで青、または緑となります。
ラベル付きモデルは点で表現されます。
サポートベクターは点の周りに灰色の円が表示されます。


============ここまで============

ふむふむふむ。
なんとなく使い方が分かって来ました。

もう一回ナンバープレートを認識する章をきちんと読んで、サンプルコードを拝借しながら実装してみたいと思います。

ではまた。

2013/01/18

OpenCV2.4.3 for Androidをダウンロードしてみた

2ヶ月ぶりの更新です。
いろいろあってこっちの研究は手をつけていませんでした。

久々にOpenCV関連で情報が更新されてないかな~とググってみると、
AndroidのアプリとしてOpenCV Managerがあるではありませんか。
早速ダウンロードしてきてドキュメントを読んでみましょう。

(OpenCV2.4.3-AndroidのOpenCVManagerのドキュメントを都合のよいように翻訳してます。正確性は全くもって保証されません。画像はドキュメントから拝借しています。 )


******************************************************************
Android OpenCV Manager
1.1 Introduction

OpenCV Managerは、エンドユーザのデバイス上でOpenCVのライブラリがサービスとして利用できるようにするためのものです 。アプリケーション間でのOpenCVの動的ライブラリの共有を許可します。このマネージャは、以下のような利点を提供します。
  • メモリの消費量が減ります(ディスク&物理メモリ?)。すべてのアプリケーションが同一のバイナリを使用するため、それぞれのアプリケーションにライブラリを含めなくてよくなるからです。
  • すべてのプラットフォームに対して、最適化することができます。(注:CPUの種類、サポートしているSIMDの機能別にOpenCV Managerがビルドされています)
  • 信頼されたOpenCVライブラリのソースが利用できます。これらはすべてGooglePlayマーケットからダウンロードすることができます。
  • 時折アップデートとバグフィックスが行われます。 

利用モデル
OpenCVのモデル図
  1. OpenCVライブラリに依存しているアプリケーションがGoogle Playからインストールされます。
  2. 初回起動時に、OpenCV Managerのインストールを促します。
  3. ユーザがOpenCVManagerをGoogle Playからダウンロードしてインストールします。
  4. Managerが起動すると、ユーザの所持しているデバイスに適したOpenCVライブラリのインストールを促します。
  5. ライブラリのインストールが完了すると、アプリケーションが起動します。
OpenCV Managerのアーキテクチャ



1.2 マネージャのワークフロー
どうやって適切なバージョンのOpenCVManagerを選ぶか?
バージョン1.7から、様々なバージョンのOpenCVManagerがビルドされてきました。どのパッケージも特定のハードウェアプラットフォーム用に対応するOpenCVバイナリを含んでいます。
大抵のOpenCV ManagerはOpenCVのビルトインバージョンを使用します。ARMv7AプロセッサでNEONをサポートしている場合は、それ用の別パッケージが利用されます。新しいパッケージ選択方式では、大抵のユーザは簡単に、またGoogle playマーケットから自動的にOpenCVをインストールすることができます。

Google playマーケットが利用できない場合(エミュレータや開発ボードなど)は、adb toolを使用して手動でインストールすることができます。
adb install OpenCV-2.4.3-android-sdk/apk/OpenCV(略)..apk
以下のテーブルを参照し、あなたのデバイスに最適なバージョンのマネージャをインストールしてください。
(テーブル略。 Nexus7の場合はOpenCV_2.4.3.2_Manager_2.4_armv7a-neon.apkを使いましょう)

以下、アプリケーションの呼び出しフローなので省略。

1.3 Java OpenCV Loader
class OpenCVLoader
OpenCVライブラリの共通初期化方法を提供するヘルパークラスです。

boolean initDebug()
static boolean initDebug()
OpenCVライブラリを読み込み、初期化します。 大雑把に言うと、system.loadLibrary("opencv_java")といった感じです。
戻り値:boolean
trueが返ると、初期化に成功したことになります。
注: このメソッドは、製品コードでは推奨されません。開発時にのみ使用するようにしてください。アプリケーションを公開する場合は、非同期の初期化方法を使用してください。

boolean initAsync()
static boolean initAsync( 引数略)
OpenCVライブラリをOpenCVマネージャを使用して初期化します。
パラメータ
 Version:OpenCVライブラリのバージョン
 AppContext:サービスに接続するためのアプリケーションコンテキスト。
 Callback:LoaderCallbackInterfaceを実装するオブジェクト。接続のハンドリングを行います。
戻り値:boolean
trueが返ると、初期化に成功したことになります。

OpenCVバージョン定数
OPENCV_VERSION_2_4_2  バージョン2.4.2
OPENCV_VERSION_2_4_3 バージョン2.4.3

1.4 Base Loader Callback インターフェースの実装
class BaseLoaderCallback
LoaderCallbackInterfaceの基本実装です。
 以下省略

1.5  Loader Callbackインターフェース
class LoaderCallbackInterface
非同期によるOpenCVの初期化のためのコールバックインターフェースです。
void onManagerConnected(int status)
OpenCVライブラリの初期化処理が終わったあとに呼び出されるメソッドです。
パラメータ:status  初期化ステータスコード(初期化ステータスコードを参照)

void onPackageInstall(InstallCalbackinterface Callback)
パッケージのインストールが必要なときに呼ばれるコールバック

初期化ステータスコード
SUCCESS:初期化が完了しました
MARKET_ERROR:Google playアプリケーションが呼び出せませんでした
INSTALL_CANCELLED:OpenCVライブラリのインストールがキャンセルされました
INCOMPATIBLE_MANAGER_VERSION:OpenCVManagerのバージョンがこのアプリと互換性がありません。マネージャの更新が必要です
INIT_FAILED:初期化に失敗しました
1.6インストールコールバックインターフェース
 class InstallCallbackInterface
パッケージのインストールやアップデート用のインターフェース。

String getPackageName()
パッケージ名を返します。 "OpenCV Manager Service"や"OpenCV library"など。

void install() パッケージのインストール時
void cancel() インストールキャンセル時
void wait_install() パッケージのインストール中

Java API
 http://docs.opencv.org/java/ を参照してね!!


******************************************************************

ふーむふむ。
Android NDKを使ってネイティブコードを使わなくても、JavaだけでOpenCVを使った
アプリケーションが作れるようですね。

いくつかサンプルプロジェクトも含まれているので、それを参考になにか作ってみますかね。


あと、「Mastering OpenCV with Practical Computer Vision Projects」という本が去年の12月末に発売されたとのこと。

本の内容は、

    Cartoonifier and Skin Changer for Android.
    Marker-based Augmented Reality on iPhone or iPad.
    Marker-less Augmented Reality.
    Exploring Structure from Motion using OpenCV.
    Number Plate Recognition using SVM and Neural Networks.
    Non-rigid Face Tracking.
    3D Head Pose Estimation using AAM and POSIT.
    Face Recognition using Eigenfaces or Fisherfaces.
    Developing Fluid Wall using the Microsoft Kinect.






となっています。
Kindle Storeで18ドルだったのでポチっておきました。
円安になる前に買っておけばよかったかな。。
今日の夜はこれを読みながら寝ようと思います。
ではまた。