仿Magic Touch中的手写识别算法
这个算法是我在传媒大学授课时候给学生们讲过的一种识别算法。由于它的原理非常简单，计算也并不复杂非常适合学习练手。与此同时，在终端手写识别算法中，我所讲解的算法在计算上也非常节约性能，但识别精度却不是很高。
由于是游戏中使用，其实我们不需要对复杂的汉字，或者文字字符进行识别，有的仅仅是非常简单的符号。下图中所示的符号，则是游戏中出现的一些常见符号。
我们可以将这些基本的符号总结为“|—V^ZC”等。这对于我们学习手写识别的算法试验也更加简单一些。我们来看一下具体的实现思路与方法（实例中的代码采用Egret编写）。
第一步：设置一个八方向坐标
第二步：将八个风向平均分为八个区域
第三步：将八个区域进行编号
第四步：对应每个编号，计算出它的旋转角度范围
第五步：采集用户对于屏幕触摸时候的数据
代码如下：
//注册侦听
egret.MainContext.instance.stage.addEventListener(egret.TouchEvent.TOUCH_BEGIN,this.mouseDown,this);
egret.MainContext.instance.stage.addEventListener(egret.TouchEvent.TOUCH_END,this.mouseUp,this);
egret.MainContext.instance.stage.addEventListener(egret.TouchEvent.TOUCH_MOVE,this.mouseMove,this);
//响应函数
private mouseDown(evt:egret.TouchEvent)
{
this._layer.graphics.clear();
this._mouseDatas = [];
var p:egret.Point = new egret.Point(evt.stageX,evt.stageY);
this._mouseDatas.push(p);
this._currentPoint = p;
}
private mouseMove(evt:egret.TouchEvent)
{
var p:egret.Point = new egret.Point(evt.stageX,evt.stageY);
this._mouseDatas.push(p);
this._layer.graphics.lineStyle(5,0) ;
this._layer.graphics.moveTo(this._currentPoint.x,this._currentPoint.y);
this._layer.graphics.lineTo(p.x,p.y);
this._layer.graphics.endFill();
this._currentPoint = p;
}
private mouseUp(evt:egret.TouchEvent)
{
var p:egret.Point = new egret.Point(evt.stageX,evt.stageY);
this._mouseDatas.push(p);
this._layer.graphics.clear();
this.motion();
}
第六步：数据降噪操作
我们看到，不同的手机屏幕响应和游戏FPS都会影响到我们采样的数据。现在我们拥有了很多坐标点信息，这些坐标点都是用户手指划过的地方。我们需要对一些较为密集的点进行降噪操作。具体的数值需要进行反复试验。我这里将两个采样数据点的间距设置为大于30px。
private motion()
{
var _arr:egret.Point[] = [];
var currentIndex:number = 0;
var len:number = this._mouseDatas.length;
_arr.push(this._mouseDatas[currentIndex]);
for(var i:number=0; i<len; i++)
{
if( egret.Point.distance(this._mouseDatas[currentIndex], this._mouseDatas[i])>30 )
{
currentIndex = i;
_arr.push(this._mouseDatas[currentIndex]);
}
}
this._mouseDatas = _arr;
this.parseDirection();
}
第七步：将采样数据转换为方向序列
两个点练成一条线段肯定会有方向，也会有角度。在第四步中，我们已经计算出每个角度范围内所代表的方向编号。现在我们需要将这个方向编号序列计算出来
private parseDirection()
{
this._dirsArr = [];
var len:number = this._mouseDatas.length;
for(var i:number=0; i<len; i++)
{
if( this._mouseDatas[i+1])
{
var p1:egret.Point = this._mouseDatas[i];
var p2:egret.Point = this._mouseDatas[i+1];
var a:number = p1.y - p2.y;
var b:number = egret.Point.distance(p1,p2);
var rad:number = Math.asin( a/b );
var ang:number = rad * 57.2957800; // rad * 180/Math.PI 直接求常量，优化
var quad:number = this.quadrant(p1,p2);
var dir:number = this.getDirByAngQuad(ang, quad);
this._dirsArr.push(dir);
}
}
}
/*
根据所在象限与角度计算出方向编号。
方向编号，以第一象限0度为基础，按照顺时针方向，将圆等分为8份。
*/
private getDirByAngQuad(ang:number,quad:number):number
{
switch(quad)
{
case 1:
if( ang<=22.5 && ang>= 0 )
{
return 1;
}
else if( ang<= 67.5 && ang> 22.5 )
{
return 8;
}
else
{
return 7;
}
break;
case 2:
if( ang<=22.5 && ang>=0 )
{
return 5;
}
else if( ang<= 67.5 && ang> 22.5 )
{
return 6;
}
else
{
return 7;
}
break;
case 3:
if( ang<= -67.5 && ang>= -90 )
{
return 3;
}
else if( ang<=-22.5 && ang> -67.5 )
{
return 4;
}
else{
return 5;
}
break;
case 4:
if( ang<=-67.5 && ang>= -90 )
{
return 3;
}
else if( ang<=-22.5 && ang>-67.5)
{
return 2;
}
else{
return 1;
}
break;
}
}
/*
计算两点关系所形成的象限
以P1 作为坐标原点，P2为设定点，判断P2相对于P1时所在象限
*/
private quadrant(p1:egret.Point,p2:egret.Point):number
{
if(p2.x>=p1.x)
{
if( p2.y <= p1.y )
{
return 1;
}
else
{
return 4;
}
}
else
{
if( p2.y <= p1.y )
{
return 2;
}
else
{
return 3;
}
第八步：方向数据去重操作
我们在第七步生成了方向序列，但是这个数据中可能会出现这样的现象。例如：2，3，1，4，5，3，3，3，3。
不难发现，最后是4个3相连。对于我们后续的步骤来说，用户所绘制的线路方向，每两个相邻的方向都应不同。所以这里我们需要做去重操作。代码如下：
/*
对比去重
*/
private repDiff(data:number[]):string
{
var str:string = "";
var len:number = data.length;
var currentType:number = 0;
for(var i:number=0; i<len; i++)
{
if( currentType != data[i])
{
currentType = data[i];
str += data[i];
}
}
return str;
}
第九步：识别对比
第八步中我们得到了一个字符串，事实上字符串内容也就是我们所解析出来的方向数据。这一步我们要和已经定义好的数据进行对比。最终会得出一个相似率。如果相似率超过一定百分比，我们就认为用户书写是正确的。
对于两个字符串比较相似度，我们直接使用Levenshtein Distance算法。
下面是我们预先定义的答案的数据。需要注意的是笔顺有正有反，两种都要考虑到。
V："28","46"
| ："3","7"
^ ："82","64"
- ："5","1"
Z："141","585"
对比代码如下：
private sweep( str:string ):number
{
var maxType:number = -1;
var max:number = -1;
var len:number = this._symbol.length;
for(var i:number=0; i<len; i++)
{
var val:number = this.Levenshtein_Distance_Percent(this._symbol[i], str);
if(val>max)
{
max = val;
maxType = this._symbolG[i];
}
}
if(max<0.4)
{
maxType = -1;
}
return maxType;
}
private Levenshtein_Distance(s,t)
{
var n=s.length;// length of s
var m=t.length;// length of t
var d=[];// matrix
var i;// iterates through s
var j;// iterates through t
var s_i;// ith character of s
var t_j;// jth character of t
var cost;// cost
// Step 1
if (n == 0) return m;
if (m == 0) return n;
// Step 2
for (i = 0; i <= n; i++) {
d[i]=[];
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt (i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt (j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}else{
cost = 1;
}
// Step 6
d[i][j] = this.Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
// Step 7
return d[n][m];
}
private Levenshtein_Distance_Percent(s,t):number{
var l=s.length>t.length?s.length:t.length;
var d=this.Levenshtein_Distance(s,t);
return (1-d/l);//.toFixed(4);
}
private Minimum(a,b,c){
return a<b?(a<c?a:c):(b<c?b:c);
}
我将对比数据设置为40%，当相似率大于40%的时候，就认为用户书写正确。通过这种方式来调整游戏的难易度。
