ActionScript で graffiti認識 と ひらがな認識
ひらがなリッパー | Si+ (wonderfl.net) (wonderfl.net2)
wonderfl に小ネタ連投．
マウスジェスチャで文字(又は Graffiti)を書くと認識してその文字が切り取られて落ちていきます．
それだけです．
もともとは，マウスジェスチャで操る感じの音アプリを作ろうとしてたんですが，明らかにオーバスペックなマウスジェスチャエンジンが出来上がりつつあったので，そこだけ取り出して少し真面目に作りこんでみました．コンテンツ的インパクトはあんまり無いですが，技術的には結構面白かったので，ちょっとブログに書き出してみようと思います．
Palm graffiti 認識
Palm graffiti ってのは Palm OS に搭載されていた，手書き文字認識専用の記号郡です．グラフィティ (Palm) - Wikipediaに詳しくのってます．基本は英語の大文字を一筆書きにしたものですが，文字認識しやすいように改変されていて，一部書き方が特殊です．スタイラスPDAの創世記に一世を風靡した OS なんですが，日本だとZaurusがあったせいか，あんま有名じゃない気もします．Palm OS は 現在の iPhone とか Andoroid とかと比べると想像を絶するような低スペック環境で動いており，そんな環境においてほぼナチュラルなスピードで書いた手書き文字（というか記号）を認識する技術は，当時，度肝を抜かれた記憶があります（自分で持ってたわけじゃなくてスーパーマニアックな友人に借りていじらせてもらってただけですが）．
さて，そんな低スペック環境での手書き文字認識アルゴリズムですが，
- 始点位置
- 終点位置
- マウス動きベクトル履歴
の情報だけを用いて認識してたそうです．具体的なところまでは知りませんが，同じ情報量で認識してみました．手書きですから生情報には様々な揺らぎやノイズがのります．そこで，まずは情報（マウス座標の履歴）を抽象化して大雑把な情報のみ抽出します．具体的には，
- 始点/終点座標は，全体を3x3の9区画に区切って，どこから始まってどこで終わったかを記録．
- 動きベクトル履歴は，マウス座標の前フレームとの差分値を 8方向に区分して方向と距離を記録（実際には識別に距離は使用しません）．連続する同一方向ベクトルはまとめて１つにして，距離が一定値以下の場合は切り捨てる．
次に，各記号の典型的なベクトル履歴とのレーベンシュタイン距離をもとめます．レーベンシュタイン距離は2つの文字列の類似性を評価する代表的な指標のひとつで，様々な分野で使われてます(レーベンシュタイン距離 - Wikipedia)．
最後に，始点/終点位置が不一致の場合，レーベンシュタイン距離にペナルティを加算して，一番低い値の文字を候補とします．
やってることは非常にシンプルですが，これだけでもかなり良い認識率でした．Palm graffiti は，区別しづらい文字を意図的に別の書き方にすることで，各文字間のレーベンシュタイン距離が長くなるように良く設計されています．
ただ，これだけだとあんまり面白みが無いので，いくつか独自チューンを加えてます．
- 人間は縦横の線の方が斜めより正確にかけるので，8方向区分について縦と横は狭めに設定（縦長のマスにあわせて縦はさらに狭くなってます）．
- 始点/終点位置の区分も同様に，中央区画は狭めに設定．
- 始点/終点位置のペナルティ判定は最低限必要な場合のみ行う(G-Q, P-D, 0-6など)．
- レーベンシュタイン距離について，置換/挿入/削除する文字よって重み付け．具体的には "13"の間に"2"が入る方が "5" が入るより軽く計算される．
- 1 と 0 は I と O と区別するため少しジェスチャを修正．
これらのチューニングでどの程度の効果があったかはよく判りませんが，たとえば"A"などは顕著に認識率が上がりました（Aの斜め線は45度間隔の8方向区分だとちょうど微妙な角度だったため）．
ひらがな認識
先の Graffiti 認識を参考にひらがな認識をやってみました．Graffiti と違う点は，
- 一筆では無い
- ”ハネ”がある
- 癖によって動き方向が変わる部分がある
位で，そんなに差はありません．
ただ，一筆では無いというのは厄介で，いつ書き終わったのか認識できません．ひらがなリッパー(Hiragana ripper)では，便宜的に1秒間入力が無かったら判定を行ってます．また，一筆ではないため，始点/終点も複数存在しています．やろうと思えば，重要な始点/終点だけピックアップして，判定する方法が考えられますが，今回は面倒なので始点終点判定は完全に省略してしまいました（例えば"さ-せ"の区別は，この方法で精度が上げられると考えられる）．あと，早く書くと行書体のようにつながってしまう問題もあります．次のハネとも関係してる部分ですが，これはつながってる文字もテンプレとして入れてしまう方法が有効と思われます．ただ，今回の判定ルーチンでは1筆でも2筆でも同じ1連の文字列としてレーベンシュタイン距離を計算してしまうため，つながった文字については特に何の対応もしていません．
認識する上では ”ハネ”というのも結構厄介です．日本人の目であればハネが有ろうと無かろうと，同じ文字として認識できますが，マウスの動きベクトルとしては大きな差になります（特に今回の認識ルーチンでは，ハネのように方向が急激に変わる箇所の重みが高いためさらに影響が大きい）．今回は，面倒だったので判定上必要な場所を除いてはハネの概念はザックリ切り落としてますが，このせいでかなり精度を落としてしまってると思われます．対応としては，ハネが有る/無い場合で複数のテンプレを用意しておくとか，位置がジャンプする直前の急激な方向変化をハネと認識して削除するといった方法が考えられると思います．
癖によって動き方向が変わる部分があるというのは例えば，"ふ"の3画目の点とか"こ"の最初の横線の角度とかです．これも複数のテンプレを用意しておく方法が有効かなと思いますが，今回はどっちとも取れるような中庸なテンプレにしてしまってます．
このようにザックリとした認識ルーチンのため，精度もそれなりですが，その割には結構高い認識率だなと感じています．
