今回は, 手書き文字認識の特徴抽出についてまとめてみた.
1．文字認識手法と特徴量
手書き文字認識を行う場合, あらかじめ考慮しておかなければならない問題がある.
それは, 続け字と筆順の問題である.
続け字は, 文字内のどのストロークを続けるか組み合わせが多数にのぼり, 予め参照パターンを準備するのはかなり困難である.
しかし, 筆順はある程度誤りのパターンが決まっており, 主な筆順誤りを参照パターンとして登録することで対応が可能である.
そこで, 今回は楷書にも続け字にも対応可能なアルゴリズムとするため, ストロークをつないで一筆書きパターンを作成し, DPマッチングという手法を使って参照パターンとの照合を行うことにする.
そこで, 以下の特徴量を持つ入力パターンを作成する.
1) ストロークを一定の間隔で近似した特徴点の座標値
2) 特徴点間(セグメント)の方向
3) ストロークのON/OFF情報
2. 特徴抽出
上記1)～3)の特徴量を抽出し, 入力パターンを作成する.
2.1 文字の正規化
特徴量の一つとして座標値を用いるため, 筆記した文字の大きさによる照合誤差を少なくするため, 入力された文字を128x128dotに拡大する.
a) 文字の外接枠を求める.
b) 文字タイプ(ドット, 横長, 縦長, 通常)をチェックする.
ドット: 文字幅 < 入力枠の幅/4, 文字高さ < 入力枠の高さ/4
横長 : 文字幅 > 文字高さ * 4
縦長 : 文字高さ > 文字幅 * 4
通常 : 上記以外
c) 文字タイプに応じて以下の大きさに座標変換する.
ドット: 32dot x 32dot
横長 : 128dot x 32dot
縦長 : 32dot x 128dot
通常 : 128dot x 128dot
[コード]
// 文字の外接枠計算
private void extractBoundingBox(ArrayList<Stroke> strokes) {
int count = strokes.size();
Rect bx = null;
for(int i=0; i<count; i++) {
Stroke strk = strokes.get(i);
if(bx == null) {
bx = new Rect(strk.boundingBox);
}
else {
if(bx.left > strk.boundingBox.left) {
bx.left = strk.boundingBox.left;
}
if(bx.right < strk.boundingBox.right) {
bx.right = strk.boundingBox.right;
}
if(bx.top < strk.boundingBox.top) {
bx.top = strk.boundingBox.top;
}
if(bx.bottom > strk.boundingBox.bottom) {
bx.bottom = strk.boundingBox.bottom;
}
}
}
boundingBox = bx;
}
// 文字タイプをチェック(ドット：0, 横長:1, 縦長:2, 通常:3)
private int checkCharType() {
int width = boundingBox.right - boundingBox.left + 1;
int height = boundingBox.top - boundingBox.bottom + 1;
if(width < BOX_SIZE/DOT_RATIO && height < BOX_SIZE/DOT_RATIO) {
return TYPE_DOT;
}
if(width > height * HV_RATIO) {
return TYPE_LONGX;
}
else if(height > width * HV_RATIO) {
return TYPE_LONGY;
}
else {
return TYPE_NORMAL;
}
}
// 入力パターンを正規化
private void normalizeChar(ArrayList<Stroke> strokes) {
int count = 0;
for(int i=0; i<numStrks; i++) {
count +=strokes.get(i).points.length;
}
Point[] pts = new Point[count];
int width = boundingBox.right - boundingBox.left + 1;
int height = boundingBox.top - boundingBox.bottom + 1;
int normWidth = NORMALIZE_SIZE;
int normHeight = NORMALIZE_SIZE;
int type = checkCharType();
switch(type) {
case TYPE_DOT:
normWidth /= HV_RATIO;
normHeight /= HV_RATIO;
break;
case TYPE_LONGX:
normHeight /= HV_RATIO;
break;
case TYPE_LONGY:
normWidth /= HV_RATIO;
break;
}
int xscale = normWidth * SCALE / width;
int yscale = normHeight * SCALE / height;
Log.v("norm", "xscale=" + xscale + ", yscale=" + yscale);
int idx = 0;
for(int i=0; i<numStrks; i++) {
Stroke strk = strokes.get(i);
for(int j=0; j<strk.points.length; j++) {
Point po = new Point(strk.points[j]);
if(Stroke.isStrokeEnd(po) == false) {
po.x = (po.x - boundingBox.left) * xscale / SCALE;
po.y = (po.y - boundingBox.bottom) * yscale / SCALE;
}
pts[idx++] = po;
Log.v("norm", "x=" + po.x + ", y=" + po.y);
}
}
points = pts;
}
2.2 変化点抽出
ストロークの座標点間の角度を求め, 座標点の前後のセグメントの角度差が大きい(10度以上)座標点を変化点として抽出する.
セグメントの長さが短い場合, 前後のセグメントに統合する.
[コード]
// 折れ線近似を行う
private void approximateByStraightLine() {
Point[] pts = points;
int count = pts.length;
Point p0 = Stroke.setStrokeEnd();
int idx = 0;
int curr = 0;
for(int i=0; i<count; i++) {
if(Stroke.isStrokeEnd(p0) == true) {
pts[idx].x = pts[i].x; // 始点を保存
pts[idx++].y = pts[i].y;
p0 = pts[i];
curr = i;
i++;
}
else if(Stroke.isStrokeEnd(pts[i]) == true) {
pts[idx].x = pts[i-1].x; // 終点を保存
pts[idx++].y = pts[i-1].y;
pts[idx].x = pts[i].x; // PenUpを保存
pts[idx++].y = pts[i].y;
p0 = pts[i];
curr = 1;
}
else {
int maxDiff = 0;
int maxIdx = 0;
for(int j=curr+1; j<i; j++) {
Segment seg02 = new Segment(p0, pts[j]);
Segment seg21 = new Segment(pts[j], pts[i]);
int diff = seg02.calcDiffDirect(seg21);
if(diff >= maxDiff) {
maxDiff = diff;
maxIdx = j;
}
}
if(maxDiff > UNIFY_ANGLE) { // 変化点
p0 = pts[maxIdx];
Log.v("sample", "idx=" + maxIdx + "x=" + p0.x + ", y=" + p0.y + "dir=" + maxDiff);
pts[idx].x = p0.x;
pts[idx++].y = p0.y;
curr = maxIdx;
i = curr + 1;
}
}
}
points = reallocPoint(pts, idx);
}
// 短いセグメントを統合する
private void unifyShortSegment() {
Point[] pts = points;
Segment[] segs = new Segment[pts.length];
// セグメント情報, ストロークのON/OFFを抽出する.
int idx = 0;
int count = pts.length;
for(int i=1; i<count; i++) {
if(!Stroke.isStrokeEnd(pts[i])) {
segs[idx] = new Segment(pts[idx], pts[i], Segment.PEN_DOWN);
pts[idx+1] = pts[i];
idx++;
}
else { // ストローク終点
if(++i<count) {
segs[idx] = new Segment(pts[idx], pts[i], Segment.PEN_UP);
pts[idx+1]= pts[i];
idx++;
}
}
}
// 短いセグメントを前後のセグメントに統合
count = idx;
idx = 0;
for(int i=0; i<count; i++) {
int diff1 = 180;
int diff2 = 180;
if(segs[i].length < MIN_SEGLEN && segs[i].isPenDown()) {
if(i > 0 && segs[i-1] != null && segs[i-1].isPenDown()) {
diff1 = segs[i-1].calcDiffDirect(segs[i]);
}
if(segs[i+1] != null && segs[i+1].isPenDown()) {
diff2 = segs[i].calcDiffDirect(segs[i+1]);
}
if(diff1 <= diff2) {
if(idx > 0 && i > 0 && (i+1) < count) {
segs[idx-1].direct = Segment.calcDirect(pts[i-1], pts[i+1]);
segs[idx-1].length = Segment.calcLength(pts[i-1], pts[i+1]);
}
}
else {
if((i+2) < count) {
segs[i+1].direct = Segment.calcDirect(pts[i], pts[i+2]);
segs[i+1].length = Segment.calcLength(pts[i], pts[i+2]);
pts[i+1] = pts[i];
}
}
}
else {
segs[idx] = segs[i];
pts[idx++] = pts[i];
}
}
// 最後の座標点をコピー
pts[idx] = pts[count];
// 配列ｻｲｽﾞを変更
points = reallocPoint(pts, idx+1);
segments = reallocSegment(segs, idx);
}
2.3 入力パターンの作成
ストロークを構成するセグメントとストローク間の移動部分を一定(今回は16dot)の間隔で近似する.
[コード]
// 一定ピッチで近似する
private void approximateByConstantPitch() {
int bufSize = FEATURE_SIZE;
Point[] patPts = new Point[bufSize];
Segment[] patSegs = new Segment[bufSize];
Point[] pts = points;
Segment[] segs = segments;
int count = pts.length;
int idx = 0;
int base = 0;
patPts[idx++] = new Point(pts[base]); // セグメントの始点をセット
for(int i=0; i<count-1; i++) {
int segnum = segs[i].length / SEG_PITCH;
if((segs[i].length%SEG_PITCH) >= MIN_SEGLEN)
segnum++;
if(segnum == 0)
segnum = 1;
int seglen = segs[i].length / segnum;
if(segnum > 1) {
int sumLen = seglen;
for(int j=0; j<segnum-1; j++) {
int dx = ((pts[i+1].x - pts[i].x)*sumLen)/segs[i].length;
int dy = ((pts[i+1].y - pts[i].y)*sumLen)/segs[i].length;
patPts[idx] = new Point((dx+patPts[base].x), (dy+patPts[base].y));
patSegs[idx-1] = new Segment(patPts[idx-1], patPts[idx], segs[i].state);
if(++idx >= bufSize) {
bufSize += FEATURE_SIZE;
patPts = reallocPoint(patPts, bufSize);
patSegs = reallocSegment(patSegs, bufSize);
}
sumLen += seglen;
}
}
// セグメントの終点
patPts[idx] = new Point(pts[i+1]); // セグメントの始点をセット
patSegs[idx-1] = new Segment(patPts[idx-1], patPts[idx], segs[i].state);
base = idx;
if(++idx >= bufSize) {
bufSize += FEATURE_SIZE;
patPts = reallocPoint(patPts, bufSize);
patSegs = reallocSegment(patSegs, bufSize);
}
}
points = reallocPoint(patPts, idx);
segments = reallocSegment(patSegs, idx-1);
}
[動作例]
入力パターンの例を示す. 
青丸が特徴点, 青線が筆記したストローク, 緑線がストローク間の移動を表している.
次は, 入力パターンと参照パターンとのマッチング(照合)について考えてみる.
幼児向けひらがな練習アプリを作っているのですが、文字認識機能を追加したくて、参考にさせていただいています。
なんとかうまくできたっぽい(?)ので、続いてDPmatch頑張ります！