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に入力した結果、どちらのクラスに分類されたかで青、または緑となります。
ラベル付きモデルは点で表現されます。
サポートベクターは点の周りに灰色の円が表示されます。


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

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

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

ではまた。

0 件のコメント:

コメントを投稿