一种通过分析方向码的简易手写识别方法
一种通过分析方向码的简易手写识别方法
李国镇
摘要：本文介绍一种在线手写识别方法，属于智能草稿纸的一个分课题。通过实时采集用户输入，并对采集到的数据进行快速，准确的预处理，采用决策树方法，得到对应的方向码序列。用此方向码与设备内预存的每一个数据计算，采用经过改造的Levenshtein Distance算法求得LD值，计算得到的最小值就为用户输入的内容。
手写识别是计算机智能的接受用户手写输入的一种能力。这种对计算机的输入可能是写在一张纸上的，要通过扫描仪输入计算机的“离线”情况。另一种是，通过触控笔的移动“在线”获得用户输入的情况。以下讨论的输入为第二种输入情况。
在线手写识别能够实时的自动处理由传感器输入到计算机的信息，包括X(t)，Y(t)，抬笔，落笔等。这种数据被称之为数字墨水，并且可以动态的表示用户输入的笔迹。
下面从用户落笔开始对手写识别过程进行分析。
当用户落笔后，我们的程序截获penDown事件，从系统提供的参数可以得知触控笔落笔处的坐标（x , y）。首先要判断此点是否在程序允许输入的范围之内，若不是，则抛弃此事件，若是，则处理此事件。
有两种情况要产生penDown事件，第一种为用户输入新的字符的开始，第二种为用户还未完成此字符，而是要输入此字符的下一个笔划。要分别对两种情况的penDown事件进行处理，把坐标值存入相应的存储空间。
下一个事件就为penMove事件。也要同上一个事件一样分两种情况，把对应的坐标存入对应的存储空间。此处还要注意一点，若输入的内容过多，就要返回错误。因为用户可能为了测试程序的健壮性，随意的在屏幕上连续输入，不抬笔。如果没有考虑到这种情况，很可能产生溢出，导致系统崩溃。
再下一个事件自然为penUp事件。这个事件要特别注意，要判断这个事件的产生代表了什么意义，可能是这个字符输入完了，也可能是这个字符没有输入完，而是要输入另一个字符。要处理这一点就要费一点功夫。我采取得办法是，当产生下一个penDown事件时计算两个事件之间的间隔，据本人体验，23个时钟周期比较合适。当时间大于此数证明要输入下一笔，当时间小于这个数则说明这个字符还没有输入完全。下一步就要对存取的这个笔迹进行处理了。
此时采集到的笔迹有很多无关因素，这些无关因素可能来自用户输入时，由于屏幕太滑而产生的抖动，使得锯齿过多。或者在开始和结束处产生的干扰笔迹。因此就要对这些情况进行处理。
产生的轨迹假设为（1，2）（3，4）（5，6）（7，8）
则array中存储array = {8,1,2,3,4,5,6,7,8};
平滑处理：
for(i = 4
i <= (array[0]/2-3)
i++)
{
array[2*i] = (array[2*(i-3)] + array[2*(i-2)] + array[2*(i-1)] + array[2*i] +array[2*(i+1)] + array[2*(i+2)] + array[2*(i+3)])/7;
array[2*i-1] = (array[2*(i-3)-1] + array[2*(i-2)-1] + array[2*(i-1)-1] + array[2*i-1] +array[2*(i+1)-1] + array[2*(i+2)-1] + array[2*(i+3)-1])/7;
}
冗余处理：
for(i = 2
i <= array[0]/2 &&
i<=NUMMAX
i++)
{
d = sqrt(( (array[2*i] - array[2*(i-1)])*(array[2*i] - array[2*(i-1)]) ) + ( (array[2*i-1] - array[2*(i-1)-1])*(array[2*i-1] - array[2*(i-1)-1]) ));
if(d < 8)
{
array[2*i] = array[2*i-1] = 0
//del vertex
}
}
然后去除标记为删除的点
if(array == 0)
{
for(j=i;j<array[0] &&
array[j] == 0 &&
j<=NUMMAX;j++)
;
array = array[j] + array;
array[j] = array - array[j];
array = array - array[j];
}
if(j >= array[0])
array[0] = i-1;
经过这些预处理，得到的笔迹将能真实的反应用户的输入情况。
下一步就为获取方向码。
我们规定二维平面上有8个方向，分别规定为1，2，3，4，5，6，7，8
在根据以下公式计算以下两个偏移值：
dx = array[2*i-1] - array[2*i-3];
dy = array[2*i] - array[2*i-2];
求得：
d = sqrt(dx*dx + dy*dy);
再建立一个满三叉树如下，通过类似于决策树的方法来得到方向码。
从第0层到第1层选择时，计算dx/d 若
if(dx / d >= 0.37) //left child
if(dx / d > -0.37 &&
dx/d < 0.37) //middle child
if(dx / d <= -0.37) //right child
从第1层到第2层选择时，计算dy/d若
if(dy / d >= 0.37) //left child
if(dy / d > -0.37 &&
dx/d < 0.37) //middle child
if(dy / d <= -0.37) //right child
0．37为MIT经过试验总结出来的比较能够有区分度的值。
这样用户输入的字符的方向码就得到了。
下一步就是要进行匹配计算，看这个方向码与存储的那个字符相似度最大。
本文采用了1965年由Vladimir Levenshtein发明的Levenshtein distance算法，并通过此算法地原理加以改进，使之适应我们的需要。
原理：
要想得到两个字符串的相似度（距离），也就是要计算一个字符串转换为另一个要比较的字符串时，所要经历的变化此数。
这里把461123 转变成 5611637，看看他的相似度是多少。
461123 → 561123 （把 4 替换成 5）
561123 → 561163 （把2 替换成 6）
561163 → 5611637 （在最后增加 7）
可以看出，从4661123转变成5611637至少需要3步。那么我们怎么让计算机也这样计算呢？
首先创建一个D[m][n]这里就是D[6][7]矩阵，来存放每次比较得到的距离。
从两个字符串的左边开始比较,记录已经比较过的子串相似度，然后进一步得到下一个字符位置时的相似度。
D[x][y]代表第一个字符串的0—x位，转变到第二个字符串的0---y位所经历的插入，删除，替换的总数。
D[x-1][y], D[x][y-1], D[x-1][y-1] 表示经过若干步的计算已经使字符串相等。
计算D[x][y]的值的过程：
如果这两位的字符相等，则取min(D[x-1][y], D[x][y-1], D[x-1][y-1])。说明此步不需要再进行改动。
如果这两位的字符不相等，则取min(D[x-1][y], D[x][y-1], D[x-1][y-1]) + 1。因为不相等所以就要进行插入，删除，替换中的一个替换工作。
例如当算到矩阵D[3,3]位置时,也就是当比较到461和561时,要从已经比较过的3对子串46-561, 461-56和46-56之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。所以最终答案就是最又下脚的值。
代码如下：
static Int8 levenshtein_distance(UInt8 s[] ,UInt8 x[])
{
UInt8 t,i=1,j,n,m,cost,distance;
UInt8 d[BKMAX + 1][BKMAX + 1];
n = s[0];
m = x[0];
if(n!=0 &&
m!=0 &&
n<=BKMAX &&
m<=BKMAX)
{
m++;
n++;
for(t=0;t<n &&
i<=NUMMAX;t++)
d[t][0] = t;
for(t=0;t<m &&
i<=NUMMAX;t++)
d[0][t] = t;
for(i=1;i<n &&
i<=NUMMAX;i++)
for(j=1;j<m &&
i<=NUMMAX;j++)
{
if( s==x[j] )
cost=0;
else
cost=1
// 1：此处可以进行改进
d[j] = minimum( d[i-1][j]+1, d[j-1]+1, d[i-1][j-1] + cost );
}
distance = d[n-1][m-1];
return distance;
}
else
return MAXD
}
把用户输入的数据经过处理得到的方向码序列，并与以存储在计算机内部的方向码逐个进行比较，放入一个数组中。再从这个数组中查找最小值。得到的最小值的角标就是所输入的数字。
这样数字手写识别的工作就完成了。
转贴请注明出处。
若有错误尽情指出，不胜感激。
