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


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

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

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

ではまた。

22 件のコメント:

  1. Очень потрясающиеда еще удивительно точные интернет гадания для уточнении загадывания нашего дня грядущего - это непременно то, что вы увидите на страницах нашего сайта. Гадание таро на август 2019 оказывается наиболее быстрым и простым инструментом для получения необходимых информаций из эмпирического поля планеты Земля.

    返信削除
  2. Кафельная плитка Gayafores отлично подходит к любому интерьеру. Наилучший выбор настенного покрытия может приукрасить всякую коридор или ванную комнату. Декоративная плитка разделяется на два вида - для полов и уложенная на стены. Различается покрытие по величине, плотности и толщине. Отдельно стоящим лотом идет плитка из керамического гранита.

    返信削除
  3. Интерактивный сервис по поиску самых выгодных цен на железнодорожные перемещения предлагает всем пользователям купить жд билеты Москва Прага по максимально приемлемой стоимости без спекулянтов. На сайте 1poezd.ru представлен легкий и понятный каждому покупателю поиск железнодорожных билетов. Максимально актуальные направления, интерактивное резервирование, минимальные цены, благоприятные составы и купе.

    返信削除
  4. Обналичивайте деньги любым выгодным способом. Пересылать наличку из виртуального Casino X столь же легко, как совершать закупку в интернет магазине. По этому адресу https://japancasino-x.com/%e3%82%ab%e3%82%b8%e3%83%8ex%e3%83%95%e3%83%aa%e3%83%bc%e3%82%b9%e3%83%94%e3%83%b3/ достоверно разъяснены все возможные примеры получения денежных средств с вашего индивидуального счета на площадке. Игроку предоставляется возможность перевести игровой остаток на дебетовую карту или виртуальный счет, а сама транзакция проходит не больше минуты.

    返信削除
  5. Различные виды гадания обозначаются как астральные науки. Любой тип ворожения неповторим и необходим для различных задач. Гадание на ночь на суженого и четкость предзнаменований прямо зависит от умения гадающего. Каждый рассчитывает узнать собственную судьбу и представляет определенные варианты ворожбы максимально эффективными.

    返信削除
  6. Большое обилие развлечений на ПК выпускается каждый месяц. Самым легким вариантом получить востребованную игру является скачать игры про дрифт взломанная версия. Разбираться в жанрах компьютерных игрушек не так легко по причине нереального их обилия. Устанавливая игры с интернета вы получаете особый уровень противостояния атакам. Мошенники могут использовать непосредственность пользователей и распределять вирусный код. Скачка торрента оказывается легкой процедурой, доступной даже для неопытных посетителей.

    返信削除
  7. Thank you for the helpful text. I recommend visiting my site https://youtube-to-mp3-converter.com/. With it, you can easily download any music from Youtube to your phone.

    返信削除
  8. Большое обилие игр делается каждый день. Наиболее народным способом взять ожидаемую игрушку считается https://games9.ru/load/stehls/. Быть знатоком в стилях популярных игр не так просто по причине нереального их количества. Перекачав игрушки с треккера вы получаете больший уровень надежности. Злоумышленники могут использовать глупость пользователей и прикладывать вирусный код. Загрузка Torrent является простой процедурой, терпимой как минимум для молодых пользователей.

    返信削除
  9. Именно в этом месте юзеры сумеют узнать ХИТ-парад лучших любимых треков этого времени. Музыка 2020 русская популярное бесплатно – кто угодно отыщет на портале mp3smak.ru классную музыку. Конкретная пора года характеризуется собственными песнями, какие тянет переписать на свой девайс. Наконец-то нет нужды формировать личный список музыкальных хитов по крошкам из интернета. Неповторимая музыкальная коллекция содержит синглы наиболее слушаемых музыкантов в мире. Сумма треков для скачивания бесконечно.

    返信削除
  10. Только по интерактивным площадкам, например порочная TSBGDCK секс - вы сможете изображать своего сексуального любовника кем хотите. Девушку можно просто одеть в какой-либо экстравагантный туалет. Применение всяких забавных приспособлений лишь повысит результат интернет порева. Особо грубые настроения запросто осуществлять даже с каким-то компаньоном. Вы просто можете избавиться от комплексов. Парни могут опробовать немного новое, а красавицы с радостью проявят свои округлости.

    返信削除
  11. Гадание да-нет онлайн правдивое - попытка просмотреть приближающиеся события всегда зачаровывал людей. Всякий рассчитывает узнать собственное будущее и представляет определенные способы ворожбы наиболее достоверными. Предсказание будущего дает увидеть, что человека ожидает в предстоящем времени.

    返信削除
  12. Керамику плитка vitra arkitekt изготовляют в целом из натуральных исходников. Кафель возможно класть в залах заведений общепита, в школах и детских садиках. Экологически безвредный материал, совершенно безопасен для проживающих.

    返信削除
  13. Гадание на таро как будут развиваться ваши отношения это способ предсказать приближающиеся явления всегда заманивал род человеческий. Каждый мыслит предугадать свое грядущее и воспринимает определенные варианты ворожбы гораздо больше результативными. Хиромантия дает просмотреть, что человека подстерегает в ближайшем времени.

    返信削除
  14. Идеальное отображение нынешних видеопроекторов превзойдет ваши предположения. Делайте разумное решение – проекторы jvc в компании Projector 24 будет классным вариантом. Нынешние модификации видеопроекторов имеют беспроводную способность передачи информации.

    返信削除
  15. Гадание на измену верен ли мне мой мужчина позволяет угадать, что человека подстерегает в предстоящее время. Вариант увидеть приближающиеся действия непрерывно зачаровывал род человеческий. Всякий желает просмотреть свое грядущее и видит определенные способы ворожбы наиболее результативными.

    返信削除
  16. Три в ряд – более чем популярный игровой аппарат среди интерактивных игрушек Kazino X. Яркое меню и отличный поиск – это надежный вариант подобрать интересную интерактивную игру. Всего лишь на нашей платформе казино х отзывы реальных людей вы можете окунуться в удивительные путешествия.

    返信削除
  17. Развитие сегодняшних технологий дает возможность интерактивным порталам существенно оптимизировать предлагаемые сервисы. Казино х официальный сайт вход – воспользуйтесь преимуществом стабильной игры и выигрывайте серьезные суммы. Игральные автоматы обрели огромную популярность во всем мире.

    返信削除
  18. Люди спорят в логическом мышлении, формируют профессиональные коллективы и берут награды в турнирах. Использовав mrbit казино вы попадете в увлекательный мир Сетевых игр. Киберспорт – это новый вариант эволюции высокопрофессиональных соревнований. Игрушки нового поколения с реальными призами.

    返信削除
  19. Только на странице онлайн-казино FrankCasino вы увидите реально актуальные и замечательные игровые процессы. Frank casino отзывы – оптимальный результат, что даст возможность усилить ваш счет. Здесь есть возможность играться и зарабатывать реальные суммы!

    返信削除
  20. Узнать личную удачу реально лишь с помощью joy casino официальный. Крупнейшее онлайн-казино Oycasino – это лучший метод получить большие денежные средства. Насыщенный образ площадки приятен взору, а гигантское число игрушек предоставляет право проверить личную удачу.

    返信削除
  21. Существуют и разновидности мусорных емкостей из пластика. Могут быть оформлены отгрузки контейнеров для сбора мусора в отдельности. Тем не менее, на основном портале производителя СнабТоп.ру покупатели смогут в свою очередь купить здесь https://snabtop.ru/category/plastikovye-kontejnery/.

    返信削除
  22. Керамическая крошка, как исходный компонент, не подвергается горению. При возникновении горения pamesa mayfair navi не производит губительных веществ. Хорошая твердость гарантирует износостойкость материала на длительный срок.

    返信削除