今回は, 手書き文字認識の文字照合(マッチング)についてまとめてみた.

1. DPマッチングとは?
DPマッチングとは, 入力パターンと参照パターンのデータ系列がどれだけ類似しているかを数値化する(類似度を計算する)方法の一つである.
ここでは話を簡単にするために, 1次元の符号列からなる2つのパターンがどれだけ似ているかを考えてみる.
  p1 = { a, b, b, b, c, d }
　p2 = { a, a, b, c, c }
2つのパターンは, 各符号の伸縮や符号違いなどがあるが, これらのパターンがどれだけ類似しているのかを, DPマッチングを使って求めてみる.
パターンP1とP2の各符号を対応付ける経路は, 以下の図のように表される.

この中でもっともパターン間距離が小さくなる経路は, 以下の式で各格子の距離を計算することで求められる.



ここで, 符号が同じ場合はd(i,j)=0, 異なる場合はd(i,j)=1として計算すると, 以下のようになる.

このように, DPマッチングは2つのパターン間の距離(類似度)を動的計画法(Dynamic Programing)を用いて計算する手法である.

2. 文字照合
2.1 文字照合の考え方
文字照合は, 文字を表す特徴点の対応付けをDPマッチングを使って行うことで, 入力されたパターンがどの文字のパターンに類似しているかを判定する.

2.2　類似度(距離)計算
入力パターンと参照パターンの特徴点の座標値を対応付けて, パターン間の距離を求めるだけでも, 認識対象の文字数が少ない場合認識可能である.
しかし, 漢字や平仮名など数千文字を認識対象とする場合, 座標値だけでは誤認識が発生しやすくなる. そこで, 今回は座標値だけでなくストロークの移動方向やタブレットへのタッチ情報も用いて, 以下の式でパターン間距離を計算する.

[コード]
  public class DPmatch {
    private final static int INFINITY = 0xffffff;
    private final static int POINT_MAX = 64;
    private final static int WINDOW_WIDTH_MIN = 3;
    private final static int COORD_WEIGHT = 1;
    private final static int DIRECT_WEIGHT = 8;
    private final static int STATE_WEIGHT = 64;
    // タッチのON/OFFによるペナルティ
    private static int[][] weight = {{ 0, 1}, {4,  0}};
 
    int calcDistance(Pattern inp, Pattern dict, int thres) {
      int inpLen = inp.segments.length;
      int dictLen = dict.segments.length;
      int[] g = new int[POINT_MAX];
      int inpWin, dictWin;
      int start, end;
      int g_ij_1, minDist, d;
      int a0, a1, a2;
      int inpIdx, dictIdx;
      int i, j;
  
      if(inpLen >= POINT_MAX || dictLen >= POINT_MAX) {
        return INFINITY;
      }
      // 初期化
      for(i=0; i<=dictLen; i++) {
        g[i] = INFINITY;
      }
      // 窓幅決定
      if(inpLen > dictLen) {
        inpWin = Math.max(inpLen - dictLen, WINDOW_WIDTH_MIN);
        dictWin = WINDOW_WIDTH_MIN;
      }
      else {
        inpWin = WINDOW_WIDTH_MIN;
        dictWin = Math.max(dictLen - inpLen, WINDOW_WIDTH_MIN);
      }
      // 枝狩り閾値
      thres *= (inpLen + dictLen);
  
      g[0] = 0;
      g_ij_1 = INFINITY;
      for(i=1, inpIdx=0; i<=inpLen; i++, inpIdx++) {
        start = Math.max(i - inpWin, 1);
        end   = Math.min(i + dictWin, dictLen);
        g_ij_1 = INFINITY;
        minDist = INFINITY;
        j = start;
        for(dictIdx=start-1; j<=end; j++, dictIdx++) {
          d = distance(inp.points[inpIdx], inp.segments[inpIdx], dict.points[dictIdx], dict.segments[dictIdx]);
          a0 = g_ij_1 + d;
          a1 = g[j-1] + 2 * d;
          a2 = g[j] + d;
          g[j-1] = g_ij_1;
          g_ij_1 = Math.min(Math.min(a0, a1), a2);
          minDist = Math.min(minDist, g_ij_1);
        }
        g[j-1] = g_ij_1;
        //　閾値を超えた場合, 計算を中断
        if(minDist > thres) {
          return INFINITY;
        }   
      }
      // トータル距離を正規化
      return (g_ij_1 / (inpLen + dictLen));
    }
  
    // 特徴点間の距離d(i, j)を計算
    private int distance(Point inpPo, Segment inpSeg, Point dictPo, Segment dictSeg) {
      // 座標点間の距離
      int cdist = (int)Math.sqrt((inpPo.x - dictPo.x)^2 + (inpPo.y - dictPo.y)^2);
      // セグメントの方向差
      int hdist = inpSeg.calcDiffDirect(dictSeg);
      // タッチのON/OFF状態によるペナルティ
      int sdist = weight[inpSeg.state][dictSeg.state];
      // 重み付け距離
      return (COORD_WEIGHT * cdist + DIRECT_WEIGHT * hdist + STATE_WEIGHT * sdist);
   }
 }

3. 認識動作の確認
平仮名46文字(”あ"～"ん")を登録し, 認識動作を確認した.


類似した文字群"わ", "ね", "れ"も一応認識ができることを確認した.


続け時も認識できることを確認した.


4. 手書き入力IMEにするには?
実用的な手書き文字入力エンジンにするためには, さらに以下のような作業が必要と考える.
a) 辞書パターンの作成
　多数の手書きデータを収集し, 収集した文字を文字毎にクラスタリングし, 辞書パターンを作成する.
b) 文字照合の高速化
　数千文字の辞書パターンすべてとマッチングを行うと処理時間がかかるので, 辞書パターンの予備選択など高速化処理を実装する.
c) 詳細識別
　画数の少ない文字には類似した文字(例えば, "七"と"ヒ"など)が多数あるので, 類似した文字の相違点を調べる詳細識別処理を実装する.
d) IME化
　他のアプリに文字入力できるよう, ソフトウェアキーボードのようなIMEアプリとして実装する.

これまで, 手書き文字認識の基本的な考え方について数回にわたって紹介してきたが, 今回の文字照合で一応終わりとする.
また, 実用化に向けて上記a)～d)に取り組むことがあれば, また続編として紹介していこうと思う.