人人都能看懂的复杂手势识别

在制作游戏的过程中,会遇到很多有趣的算法,今天我给大家分享一个识别复杂手势的算法
由于它的原理非常简单,计算也并不复杂非常适合学习练手。与此同时,在终端手写识别算法中,我所讲解的算法在计算上也非常节约性能,但识别精度却不是很高。 由于是游戏中使用,其实我们不需要对复杂的汉字,或者文字字符进行识别,有的仅仅是非常简单的符号。下图中所示的符号,则是游戏中出现的一些常见符号
(游戏名称 Magic Touch)

我们可以将这些基本的符号总结为 “V”, “|”, “^”, “-“, “Z”, “U”,”Ω” 等。这对于我们学习手写识别的算法试验也更加简单一些。我们来看一下具体的实现思路与方法

第一步:设置一个八方向坐标,将八个风向平均分为八个区域,八个区域进行编号,对应每个编号,计算出它的旋转角度范

第二部(开始敲代码了)我们肯定要先注册点击事件(点击事件的开始,移动,结束。 实例中的代码采用Egret编,语言是TS)

private init(e:egret.Event=null):void {

    this.stage.addEventListener(egret.TouchEvent.TOUCH_BEGIN, this.onTouchBegin, this);
    this.stage.addEventListener(egret.TouchEvent.TOUCH_MOVE, this.onTouchMove, this);
    this.stage.addEventListener(egret.TouchEvent.TOUCH_END, this.onTouchEnd, this);
}

private onTouchBegin(e:egret.TouchEvent):void {
    this.shape.graphics.clear();
    this.mouseDatas = [];
    var p:egret.Point = new egret.Point(e.stageX, e.stageY);
    this.mouseDatas.push(p);
    this.currentPoint = p;
}

private onTouchMove(e:egret.TouchEvent):void {
    var p:egret.Point = new egret.Point(e.stageX,e.stageY);
    this.mouseDatas.push(p);
    this.shape.graphics.lineStyle(5,0) ;
    this.shape.graphics.moveTo(this.currentPoint.x,this.currentPoint.y);
    this.shape.graphics.lineTo(p.x,p.y);
    this.shape.graphics.endFill();
    this.currentPoint = p;
}

    private onTouchEnd(e:egret.TouchEvent):void {
        var p:egret.Point = new egret.Point(e.stageX,e.stageY);
        this.mouseDatas.push(p);
        this.shape.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);
        }
    }
    let id = this.sweep(this.repDiff(this.dirsArr));
    if (this.sign[id]) {
        this.label.text = "当前所画图形为:"+this.sign[id];
    }
    else {
        this.label.text = "画的不标准判断没有图形";
    }
} 

根据所在象限与角度计算出方向编号。 方向编号,以第一象限0度为基础,按照顺时针方向,将圆等分为8份

private getDirByAngQuad(ang:number,quad:number):number {
    let n = 0;
    switch(quad) {
        case 1:
            if( ang<=22.5 && ang>= 0 ) {
                 n = 1;
            }
            else if( ang<= 67.5 && ang> 22.5 ) {
                n = 8;
            }
            else {
                n = 7;
            }
        break;
        case 2:
            if( ang<=22.5 && ang>=0 ) {
                n = 5;
            }
            else if( ang<= 67.5 && ang> 22.5 ) {
                n = 6;
            }
            else {
                n = 7;
            }
        break;
        case 3:
            if( ang<= -67.5 && ang>= -90 ) {
                n = 3;
            }
            else if( ang<=-22.5 && ang> -67.5 ) {
                n = 4;
            }
            else{
                n = 5;
            }
        break;
        case 4:
            if( ang<=-67.5 && ang>= -90 ) {
                n = 3;
            }
            else if( ang<=-22.5 && ang>-67.5) {
                n = 2;
            }
            else{
                n = 1;
            }
        break;
    }
    return n;
} 

计算两点关系所形成的象限 以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算法。 下面是我们预先定义的答案的数据。需要注意的是笔顺有正有反,两种都要考虑到
(此处使用的对比是 Levenshtein Distance 算法 附加上算法链接Levenshtein Distance 算法
V:”28″,”46″
| :”3″,”7″
^ :”82″,”64″
– :”5″,”1″
Z:”141″,”585″
U:”32187″, “34567”
Ω:”167812341″

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];
        }
    }
    switch (maxType) {
        case 0:
            if(max<=0.6) {
                maxType = -1;
            }
        break;
        case 1:
            if(max<=0.1) {
                maxType = -1;
            }
        break;
        case 2:
            if(max<=0.5) {
                maxType = -1;
            }
        break;
        case 3:
            if(max<=0.8) {
                maxType = -1;
            }
        break;
        case 4:
            if(max<=0.6) {
                maxType = -1;
            }
        break;
        case 5:
            if(max<=0.6) {
                maxType = -1;
            }
        break;
        case 6:
            if(max<=0.7) {
                maxType = -1;
            }
        break;
        case 7:
            if(max<=0.7) {
                maxType = -1;
            }
        break;
    }

    return maxType;
}

private Levenshtein_Distance(s,t):number {
    var n=s.length;
    var m=t.length;
    var d=[];
    var i;
    var j;
    var s_i;
    var t_j;
    var cost;
    if (n == 0) return m;
    if (m == 0) return n;
        for (i = 0; i <= n; i++) {
        d[i]=[];
        d[i][0] = i;
    } 
    for (j = 0; j <= m; j++) {
        d[0][j] = j;
    } 
    for (i = 1; i <= n; i++) {
        s_i = s.charAt (i - 1);
        for (j = 1; j <= m; j++) {
            t_j = t.charAt (j - 1);
            if (s_i == t_j) {
                cost = 0;
            }
            else{
                cost = 1;
            }
            d[i][j] = this.Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
        }
    }
    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);
}

private Minimum(a,b,c){
    return a < b ? ( a < c ? a : c) : ( b < c ? b : c);
}

总结:这是一个看起来复杂,实现起来起始很容易的算法,把图形问题,最后转化成字符串的相似度的一个对比,只要想象力够丰富,就能再画出更复杂的手势,但是只能是一笔画,希望对大家都能有所帮助,感谢观众大老爷都看完了。

发表评论