仿Magic Touch中的手写识别算法

转自：http://www.ashan.org/archives/685 可以参考例子：http://edn.egret.com/cn/article/index/id/709

这个算法是我在传媒大学授课时候给学生们讲过的一种识别算法。由于它的原理非常简单，计算也并不复杂非常适合学习练手。与此同时，在终端手写识别算法中，我所讲解的算法在计算上也非常节约性能，但识别精度却不是很高。

由于是游戏中使用，其实我们不需要对复杂的汉字，或者文字字符进行识别，有的仅仅是非常简单的符号。下图中所示的符号，则是游戏中出现的一些常见符号。

我们可以将这些基本的符号总结为“|—V^ZC”等。这对于我们学习手写识别的算法试验也更加简单一些。我们来看一下具体的实现思路与方法（实例中的代码采用Egret编写）。

第一步：设置一个八方向坐标

第二步：将八个风向平均分为八个区域
仿Magic Touch中的手写识别算法 - 第3张 | u3d8技术分享

第三步：将八个区域进行编号

第四步：对应每个编号，计算出它的旋转角度范围

第五步：采集用户对于屏幕触摸时候的数据

代码如下：

//注册侦听

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();

}

第七步：将采样数据转换为方向序列

两个点练成一条线段肯定会有方向，也会有角度。在第四步中，我们已经计算出每个角度范围内所代表的方向编号。现在我们需要将这个方向编号序列计算出来

100

101

102

103

104

105

106

107

108

109

110

111

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%的时候，就认为用户书写正确。通过这种方式来调整游戏的难易度。

本文固定链接: http://www.u3d8.com/?p=601
转载请注明: 网虫虫在 u3d8.com 发表过

最后编辑：2016-10-11

作者：网虫虫

分享是一种快乐；分享是一种美德；分享是一种幸福！

站内专栏站点 QQ交谈

2024年11月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

您可能还会对这些文章感兴趣！