JavaScriptで簡単手書き文字認識

筆者: 藤本誠二 <fujimoto@ceptord.net>
更新: 2017年10月9日(月)

charec は、おもちゃの手書き文字認識プログラムです。 全体が200行ほどのJavaScriptで実装されています。
以下にデモを用意しています。灰色の枠内に1から9までの数字を一つ書くと、その数字を認識して右に表示します:

この記事では、このプログラムがどのような仕組みで動いているかを解説します。

基本的な仕組み

1. 筆跡を座標データとして取得する

最初に、キャンバスに座標系を導入します。 隅の点を原点にとって、X軸とY軸を引き、 キャンバス上の任意の点を (15, 35) のような座標で表せるようにします。 こうすると、ユーザーが描く筆跡は「平面上を動く一連の座標」として表現できます。 

実際に「3」という数字を描いた時のデータを、以下に示します:

時刻 t0 に座標 (80, 226) から描画が始まり、 時間の推移とともに点が移動しているのが見て取れると思います。
(なお、図では省略されてますが、この筆跡は時刻 t110 に座標 (99, 41) に到達して終わっています)

2. 各座標成分の極値をとる

筆跡を座標データとして扱えるようになったので、早速、X軸とY軸に成分を分解して、 各時点tnにおける動きを見てみます。 前節の描画データを、実際に分解してグラフに表すと次のようになります:

グラフの横軸は時刻 [t0, t110] で、縦軸は各時刻に対応する X/Y の値です。

ここでは各グラフの大雑把な形に注目します。 まずX軸成分のグラフに着目すると次の事に気がつきます:

このことを高校数学の用語を使って言い換えるなら、 X軸成分のグラフはt25・t80で極大値 t50で極小値を取っている、と言えます。 同様に、Y軸成分のグラフを分析すると、t10で極大値、t95で極小値をとっていることが分かります。

これを時系列順に整理すると、次のようになります:

(t10) Yで極大値 → (t25) Xで極大値 → (t50) Xで極小値 → (t80) Xで極大値 → (t95) Yで極小値

3. 情報を文字列に符号化する

この節では、前節の観察結果を簡潔に記述できる記法を導入します。

まず、X軸で極大値をとることを大文字の X で表し、 極小値をとることを小文字の x で表すことにします。 Y軸についても同様に、極大値をとることを Y と表し、 極小値をとることを y と表現します。

その上で、さらに Xy といった連結表記も許すことにします。 これは「最初にX軸で極大値をとり、続いてY軸で極小値をとる」という順序を表現するものです。 当然、3文字以上の結合も可能です。 例えば YXy なら「最初にY軸で極大値、次にX軸で極大値、最後にY軸で極小値をとる」という具合です。

この知識を元に、前節の観察結果を再び整理すると、次のようになります:

Yで極大値 [Y] → Xで極大値 [X] → Xで極小値 [x] → Xで極大値 [X] → Yで極小値 [y]

従って、前節の観察は YXxXy という5文字で表現できる事になります。

4. 極値に着目する理由

ここまで読んで「どうして極値に焦点を当てているのだろう?」と疑問に思った方もいるかもしれません。 この疑問は突き詰めると、文字の形とは何であるのか、という根本的な問題に帰着します。

例えば「3」という数字を考えてみましょう。 この数字をぼんやりと眺めてみると、書き手によって見栄えの差こそあれど、 どの筆跡も大雑把な"かたち"は共通していることが分かります。 さらに、字の丸み(すなわち極値)に着目すると、 この特徴はどの筆跡でもおおむね共有されている事が見えてきます。

実際に、いくつかのフォントで「3」という文字を印字した結果を以下に示します。 どのフォントでも、表面的な字形は異なっているにもかかわらず、 同じ極値条件を共有している事が見て取れると思います:

さらに一歩進んで、不変条件「YXxXy という極値を持つ」を満たすように、 フリーハンドで字を書いたとしましょう。 こちらも、いくつかのパターンを書いてみると分かりますが、 この条件を満たそうとすれば、 おおむねアラビア数字の「3」のような形になることが分かります。

そうであれば、キャンバス上に YXxXy という条件を満たすかたちが現れれば、 数字の3が描かれたと解釈できるのではないか、 というのがこのプログラムの核心にある洞察です。

5. モデルと照合する

というわけで、得られた極値の情報から文字を推定するステップに話を進めましょう。

前節の議論を応用して、アラビア数字について、対応する極値条件を洗い出します。 数字の形にいくつかの書き方がある場合は、そのパターンごとに極値条件を抽出します。 以下に抽出サンプルを示します:

こうして極値条件と数字を対応させた辞書が出来上がったなら、 あとはユーザーが描いた筆跡を逐次解析して、 その極値条件にマッチする数字を返却すれば良いわけです。

以上が、このプログラムの手書き文字認識の基本的な仕組みになります。

筆跡のノイズを処理する

人間の筆跡はそんなにスムーズでなく、 一本の直線を書くにしても、実際にはデコボコしてます。 このため、単純に筆跡の極値をとってしまうと、 デコボコのせいでノイズが発生します。 この一見、些細に見えるブレが、現実には文字識別の精度に大きく関わってきます。

この章では、どのようにノイズを処理しているのかを解説します。

1. 線の凹凸を均す

まずはデコボコをならして、できるだけ線をなめらかにする方針でノイズを取り去ります。 この処理を一般に「スムージング」と呼びます。

スムージングについて、よく使われるテクニックは「移動平均」です。 これは特に難しい処理ではなく、 平均をとる枠のサイズ n を最初に決めておいて、 時系列を追って枠を一つずつずらしながら平均をとっていくという手法です。

以下の図は、実際の筆跡データに対して、移動平均 (n=5) を適用した結果を示したものです:

2. 小さな変動を無視する

移動平均をとっても取り除けないデコボコもあります。

このプログラムの範疇では、文字の大きな"かたち"にのみ関心があるので、 大局に影響しない変動は無視することができます。 具体的に「何が些細な変動にあたるのか」は文脈に依存する問題ですが、 少なくとも手書きの数字に関しては、 数ピクセルの変動で生じた極値が、描かれた文字の意味を変えることは余り無さそうです。

charecの実装では閾値を設けて、10px以下の変動は無視するようになっています。

3. 最も近い候補を選出する

こうしてノイズを処理しても、 抽出された極値条件が手持ちの辞書にマッチしない場合があります。 次の単純化した例で考えてみましょう。

辞書には三つのモデルが登録されていますが、 抽出された条件 YxXyx はそのどれにもマッチしていません。 従って、モデル辞書から完全マッチを拾うだけのロジックだと、 ここでお手上げになってしまいます。

しかし、筆跡データから見て取れるように、 この文字の形は数字の「8」に極めて近いものです。 実際に、抽出された極値条件をとってみても、 登録されている「8」の筆跡モデルとは、たった一ヶ所の違いしかありません (末尾の X が欠けているだけです)。 そこで、何とかこのあたりの事情を取り込んで、それらしい候補を選出できないでしょうか。 これを実現するには、何らかの方式で、極値条件どうしの「類似度」を上手く定義する必要がありそうです。

実は、そのような類似度を計る方法は既に(いくつも)存在しています。 そのうちの代表例が「レーベンシュタイン距離」という尺度です。 ここでは詳細な解説は省きますが、 これは任意の二つの文字列の近似度を測定する、非常に汎用的な手法です。 この手法を実際に今回のケースにあてはめた結果を、以下に示します:

数字 辞書モデル (A) 抽出条件 (B) A/Bの距離
8 YxXyxX YxXyx 1
9 YxyXy YxXyx 2
9 YxyX YxXyx 2

したがって、この尺度をロジックに組み込むことで、 最も距離が小さい「8」を自然に選出できることになります。

手法の限界

最後に、本記事で解説した識別手法の限界について一通り記述します。

まず本手法で解説した方法では、大雑把な文字の形しか判定できません。 X軸とY軸の極値から分かるのはその程度だからです。 より多くの素性をモデルに取り込むことも考えられますが、 どこまで筋良く識別モデルを拡張できるかは、よくわかっていません。

筆順への依存の問題もあります。 実際に、上のデモで意図的に書き順を変えてみると、 精度はがくんと落ちます。 文字の書き方は文化圏によって変わるので、 このことは現実にも問題になります。

参考文献

Schimke, S., Vielhauer, C. and Dittmann, J. "Using adapted levenshtein distance for on-line signature authentication." In Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference on (Vol. 2, pp. 931-934). IEEE.


Top