联机手写识别在手机游戏中的应用研究

唐胜凯 孙彩虹

摘要：联机手写识别在手机游戏中的应用已有相关产品，其中一个成功案例是将手写笔迹转换为方向码序列进行模式匹配，取相似度最高的模式作为识别结果。但是这种算法的健壮性差，对不规范的手写笔迹识别率低，而且算法的效率可进一步优化。针对这些缺陷，通过优化手写笔迹方向模型和编辑距离算法，提出了一种基于方向组的联机手写识别算法。通过对比实验证明，改进后的算法有效提高了联机手写识别系统的健壮性和识别率，而且算法的运行效率更高。

关键词：联机手写识别；手机游戏；健壮性；方向码；方向码序列

中图分类号：TP391 文献标识码：A

文章编号：1009-3044（2019）13-0201-04

Applied Research of Online Handwriting Recognition in Mobile Game

TANG Sheng-kai，SUN Cai-hong

（School of information， Renmin University of China， Beijing 100872，China）

Abstract： Online handwriting recognition has been applied in mobile games， a successful case is to convert the handwriting into a direction code sequence for pattern matching. The highest mode is used as the recognition result. However， the robustness of this algorithm is poor， the handwriting recognition rate is low， and the performance of the algorithm can be further optimized. To make up for these defects， an online handwriting recognition algorithm based on direction group is proposed by optimizing handwriting direction model and editing distance algorithm. The comparison experiments show that the improved algorithm effectively improves the robustness and recognition rate of the online handwriting recognition system， and the performance of the algorithm is higher.

Key words：online handwriting recognition； mobile game； robustness； direction code； direction code sequence

1 引言

联机手写识别开始于1960年[2]，是模式识别的一个重要研究方向[3]。联机手写识别技术不仅在理论上有重要的研究意义，而且在实际中也有很重要的应用价值[4]。随着半导体和计算机技术的发展以及模式识别领域理论和方法研究的不断深入和完善，到20世纪80年代后期，联机手写识别技术的研究已经朝着实用的方向努力，特别是英文，已经开始研究完全无限制的整句识别技术[4]。

手机游戏中的很多符号都是根据游戏风格而设计的特殊符号，不能通过键盘输入，只能通过手写输入。联机手写识别在手机游戏中的应用，国外已有Maigc Touch 等相关产品，但是国内这方面的研究很少。其中一个成功案例[7]所采用的方法是把手写笔迹细进行8方向编码[5，6]得到方向码序列[4]，通过计算其与字典中的方向码序列的相似度，取相似度最高的符号作为识别结果。但是这种算法的健壮性差，时间复杂度和内存占用都比较高。因此，对这种联机手写识别算法进行了一系列改进和优化，提出了一种基于方向组的联机手写识别算法，使得改进后的算法具有更高的健壮性和识别率，算法复杂度更低，显著提升了联机手写识别系统的性能，可有效改善用户的实时交互体验。

2 联机手写识别算法原理

联机手写识别原理如图1所示，当用户在触摸屏上进行手写时，系统以一定的频率记录笔迹信息，即一系列的坐标点，这些坐标点是离散的，并且相邻两点的连线是计算机所能分辨的最小线段，用8个方向码分别标记每个线段所属的方向，每个手写笔迹都可以产生出一个方向码序列[4]，通过计算其与字典中的方向码序列的相似度，取相似度最高的作为识别结果。

2.1 方向码

方向码是表示手写笔迹方向的數字或字母。把手写笔迹转换为方向码序列的过程是，从头至尾遍历手写笔迹的一系列坐标点，每次取相邻的两个坐标点，前面的点P1（x1， y1）称为起点，后面的点P2（x2， y2）称为终点，以起点P1为圆心，把触摸屏划分为八个圆心角相等的扇形，按顺序依次编号为1， 2， 3， 4， 5， 6， 7， 8，终点P2落在哪个扇形，两点连线的方向码就是对应扇形的编号，如图3所示。图3中的角度是P1与P2的连线与触摸屏水平线的夹角，可以看出每个方向的摆动范围是45度。

先根据相邻坐标点的相对位置，确定终点落在哪个象限，再根据两点连线与水平线的夹角确定方向码[7]，需要注意的是，触摸屏坐标系的原点在左上角，而且Y轴方向是指向下的，具体算法如下：

算法1：确定手写笔迹坐标点所在象限

以 P1 为原点，判断 P2 所在象限 Q：

如果 x2 >= x1，则 P2 在第一、四象限：

如果 y2 <= y1 ，则 P2 在第一象限 Q = 1

否则P2 在第四象限Q = 4

否则 P2 在第二、三象限：

如果 y2 <= y1 ，则 P2 在第二象限 Q = 2

否则P2 在第三象限 Q = 3

算法2：将手写笔迹坐标点转换为方向码

计算P1 与P2 的连线与水平线的夹角 θ

根据P2所在象限 Q 和 θ 判定P1 与P2 连线的方向码 C

2.2 方向码序列

预处理是联机手写识别的重要一环，分为两步：第一步是对原始点坐标的滤波；第二步是对由这些点的坐标所计算出来的方向码的滤波[5]。

由于手写的随意性，得到的一系列手写笔迹坐标点不能直接用于方向码转换，需要先进行滤波，去除冗余和噪声点，来消除因不同的手写习惯对系统造成的影响。

对手写笔迹坐标点进行编码得到的方向码序列中可能有相邻的重复方向码，例如：2，3，3，3，1，1。在进行模式匹配前，还需要去除方向码序列中相邻的重复方向码，减少后续模式匹配的计算量。

在定义方向码序列字典时，要考虑用户的不同手写习惯，比如有人喜欢正写，有人喜欢反写，即使同一个人每次下笔的方向也可能不同。用方向码序列表示一个符号，可以很方便地支持不同的写法，表1给出了几种符号的方向码序列定义实例：

2.3 方向码序列相似度计算

决定联机手写识别系统性能的关键因素是模式匹配算法，其优劣直接影响着最终的识别率高低。距离匹配是一种常用的模式匹配方法[9]，具体来说就是用采样得到的手写笔迹方向码序列 test 与字典中的方向码序列pattern[i]（i=1，2，…，n，n为字典容量）进行逐一匹配，计算test与pattern[i] 之间的距离 D（test， pattern[i]），再换算为相似度 similarity，取相似度最大的模式所对应的符号作为识别结果。相似度计算公式如下：

similarity = 1 – D（test， pattern[i]） / L

其中 L 表示方向码序列的最大长度。

文献[7]采用莱文斯坦距离度量方向码序列之间的差异。莱文斯坦距离（Levenshtein Distance），又称编辑距离，是由俄罗斯科学家弗拉基米尔·莱文斯坦（Vladimir Levenshtein）于1965年在文献[11]中提出的算法，是一种常用的字符串编辑距离度量方法，在多个领域得到了广泛应用。莱文斯坦距离[10]是指两个字符串之间，由一个字符串转换为另一个字符串所需的最少编辑操作次数，允许的编辑操作包括三种：将一个字符替换成另一个字符，插入一个字符，删除一个字符。

算法3：莱文斯坦距离算法

m = test的长度

n = pattern 的长度

cost 整数，用于记录编辑距离

D 矩阵，用于记录中间计算的莱文斯坦距离

如果m == 0，则返回n并退出。

如果n == 0，则返回m并退出。

初始化莱文斯坦距离 D 矩阵的第一行和第一列：

for （i = 0； i < m； i++） D[i][0] = i；

for （j = 0； j < n； j++） D[0][j] = j；

for （i = 0； i < m； i++）

遍历 test中的每个方向码 test[i]

for （j = 0； j < n； j++）

遍历 pattern中的每个方向码 pattern[j]

如果 test[i] == pattern[j] 则编辑距离 cost = 0

否则编辑距离 cost = 1

插入一个字符的代价 c1 = D[i-1][j]+1

删除一个字符的代价 c2 = D[i][j-1]+1

替换一个字符的代价c3 = D[i-1][j-1] + cost

D[i][j] = min（c1， c2， c3） 三种代价中取最小的

返回最终的莱文斯坦距离 d[n][m]

3 改进联机手写识别算法

这种基于方向码的方案能有效利用手写笔迹的特征，能很好地满足手写输入的实时性要求。通过多组实验发现，这种算法对于规范的手写笔迹识别率较高。但是对于不规范的手写笔迹，这种算法的识别率就很低了。用户的自然输入往往比较随意，强制所有用户进行规范输入是不现实的。所以联机手写识别系统要达到比较理想的应用水平，必须对核心算法进行改进，增强其健壮性也就是抗干扰能力，这是联机手写识别技术的难点。

在计算方向码序列的莱文斯坦距离时，算法的时间复杂度和空间复杂度都是 O（m*n），通过对算法的分析和測试，发现算法的时间效率和空间效率都可以进一步优化。

3.1 健壮性优化

通过对以上算法的测试和分析，可以发现用8个方向表示手写笔迹太粗略，尤其是对弧线较多的符号，算法的健壮性较差。针对这些缺陷，下文提出了一种基于方向码组的联机手写识别算法，用方向码组来定义符号的方向码序列模式。计算莱文斯坦距离时，根据方向码在方向码组中的位置，来确定编辑距离大小，从而使得计算结果更符合手写笔迹的实际情况，有效提高了联机手写识别系统的健壮性和识别率。

3.1.1 方向码细化

文献[1]把笔迹方向特征从4个方向延伸到8个方向，识别率得到很大程度的提高。这里把笔迹方向特征从8个方向细化为16个方向，方向码依次为：0，1，…9，a，…，f 共 16 个字符，如图4所示：

细化后的单个方向摆动范围从 45o 缩小到了 22.5o，但是下面定义的方向码组可以让摆动范围扩大到67.5 o，可有效处理不规范的手写笔迹。

3.1.2 带权重的方向码组

每个方向码组由一个主方向和2～4个辅方向组成，共3～5个方向码，例如：'9a8'，其中‘9是主方向码，排在第一位，‘a和‘8是辅方向码，排在后面，辅方向码的顺序可以颠倒，也就是说‘9a8和‘98a是同一个方向码组。

对方向码组中的权重分配如下：主方向的权重是1.0，辅方向的权重都是0.8。例如，如果手写笔迹的方向码是9，则其与方向码组‘9a8的相似度是1.0，如果手写笔迹的方向码是8或a，则其与方向码组‘9a8的相似度是0.8。

3.1.3 方向码序列模式优化

在定义手写笔迹的方向码序列字典时，采用方向码组作为一个基本单位，表2给出了几种符号的方向码组序列定义实例：

3.2 方向码序列相似度算法优化

单纯的字符串可以通过替换、插入、删除等三种基本操作转换为另一个字符串，莱文斯坦距离所要计算的是字符串编辑距离中的最小距离，所以在计算过程中，遇到对应位置字符不同时，不能只考虑字符替换而一直进行编辑距离的累加，还要考虑插入字符和删除字符的情况，取编辑距离最小的操作。

但是，手写笔迹的每一段都是首尾衔接的，不能随意删除方向码或插入方向码，所以在计算莱文斯坦距离时，遇到对应位置方向码不同时，只处理当前方向码即可，不用考虑插入方向码和删除方向码的情况，这样得到的计算结果更符合实际情况。

因此，从方向码序列的这个特点入手，对莱文斯坦距离的计算过程进行优化，不再进行嵌套循环，而是一遍通过。具体来说，就是先遍历手写笔迹的方向码序列，遍历结束后，如果系统定义的方向码序列模式还没到最后，则继续检查其余的方向码组，直到最后。改进后的算法，时间复杂度降为 O（max（m， n））。

由于新算法不需要记录中间计算结果，可以对原算法的数据结构进行优化，去掉二维数组，改用一个数值变量保存计算结果即可。改进后的算法，空间复杂度降为 O（1）。

经测试，新算法的计算结果比原算法更符合实际，健壮性显著提高，而且时间复杂度和空间复杂度都减少了很多。

设m为手写笔迹方向码序列 test 的长度，n为系统定义的方向码序列模式 pattern 的长度，那么优化之后的莱文斯坦距离算法如下：

算法4：优化之后的莱文斯坦距离算法

方向组长度 groupLength = 3

如果m == 0，则返回n并退出。

如果n == 0，则返回m并退出。

初始化莱文斯坦距离 cost = 0

start = 0 用于pattern子串起始索引

for （i = 0； i < m； i++） 遍历 test 中的每个方向码

方向码组 group = pattern 的子串 （start， start + groupLength）

如果 test[i] 不在 group 中：

如果 pattern 还有下一组，且 i > 0：

则切换到 pattern 下一组 start = start + groupLength

i = i -1 再次检查 test 当前方向码

否则 pattern 到尾部或 test[0] 不在方向码组中：

开头不对或结尾不对，直接扣分 cost + 1

否则 test[i] 在 group 中：

如果 test[i] 是 group 的第一个元素，则不扣分

否则 test[i] 是辅方向，要分情况处理：

如果 pattern 还有下一组，则 cost + 0.2

否则 pattern 到最后了，对 test 多余的辅方向不再扣分

若 pattern 還没到最后，则取下一组，直到最后

如果 test 最后一个方向码在 group 中，则不扣分。

否则直接扣分 cost = cost + 1

3.3 根据手机游戏的特点进一步优化算法

与汉字识别不同的是，手机游戏符号识别不用匹配字典中所有的符号，只匹配显示中的符号即可，这样可以进一步降低算法的复杂度，而且可以解决相似度高的符号问题。设计字典时，如果两个符号相似度很高，则归并到一个组，在抽取符号时，如果某个组的符号在显示中，则取其他组中的符号，使得显示中的符号彼此相似度很低。

4 实验测试和结果分析

4.1 实验设计

开发环境是Windows 7操作系统白鹭引擎5.2.6，实现了一个手机游戏，用于比较新算法和原算法的健壮性和识别率，实验环境是安卓手机，如图5所示：

游戏开始后会从屏幕下方冒出气球，气球上有待匹配的符号，用户在触摸屏上手写符号，如果匹配成功，则气球消失得分+1，否则气球飞走生命-1，直到生命为0或达到样本容量上限游戏结束。

4.2 实验结果分析

采用对比实验分别测试原算法和新算法，分析二者的差异，进而得出实验结论。实验要收集的数据包括手写笔迹的规范性、识别率等，把20种符号从简单到复杂分成5组分别进行实验，每组实验随机抽取100个样本，每个样本只手写一次（正向书写或反向书写，反向书写也可以很规范，所以不再单独做反向书写实验），相似度阈值取0.6，即相似度大于60%才认为匹配成功，得到的实验数据如表3和表4所示：

从表3和表4可以看出，新算法对规范度高的手写笔迹具有更高的识别率，对规范度低的笔迹识别率也在93%以上。

4.3 实验结论

通过对比实验与分析，可以证明新算法的健壮性和识别率都得到了显著提高，克服了原算法健壮性差、识别率低、内存占用高、时间复杂度高的缺陷，使联机手写识别系统的性能得到有效提升，更符合智能手机应用的运行要求。

5 总结与展望

基于方向组和改进编辑距离的联机手写识别算法，细化了手写笔迹方向模型，定义了带权重的方向码组，优化了方向码序列相似度计算过程。通过多组实验证明，这种新算法健壮性强、识别率高，而且时间复杂度和内存占用更低。

l 对于没有明显的开头和结尾的符号不能很好地定义，例如：☆，∞，O等，从任意一点开始手写都行，需要支持所有方向开头的方向码序列，考虑正反方向和不规范写法，则需要定义的方向码序列太多。

l 没有利用笔段的长度信息。

联机手写识别不仅具有广阔的应用前景，而且还有重要的理论价值[8]。研究手写识别可以帮助认识高难度模式识别的一般规律，发展新的模式识别理论。由于手写识别问题的复杂性和多重性，其在许多学科的研究中具有很高的理论探索价值和启发创造作用；激发了大量新思想和新方法，促进了相关学科的深入发展。在信息技术日新月异的21世纪，越来越智能、越来越人性化的信息设备正逐步走入人们的日常生活，联机手写识别技术一定会得到进一步的发展和普及。

参考文献：

[1] Z.L. Bai， Q. Huo， A Study on the Use of 8-Directional Features for Online Handwritten Chinese Character Recognition [C]， in Proc. IEEE ICDAR ，2005（1）：262-266.

[2] 白真龙，霍强. 在联机手写中文识别中一种针对8方向特征提取的改进算法[C]. 中文信息处理前沿进展——中国中文信息学会二十五周年学术会议，2006：484-492.

[3] 邹明福，钮兴昱. 联机手写英文识别[J].计算机研究与发展，2006.43（1）：138-144.

[4] 樊庆林. 基于笔画的联机手写汉字识别系统的研究与实现[D].安徽大学，2007.

[5] 刘光泽. 联机手写汉字识别的设计与实现[D].中国民航大学，2011.

[6] 索南尖措，关白，李雷，等.藏文联机手写识别的研究與实现[J].计算机时代，2017（7） ：10-12.

[7] A闪. 仿Magic Touch中的手写识别算法[EB/OL]. https：//ashan.org/archives/685. 2016-02-05.

[8] 罗巧玲. 联机手写汉字识别关键技术研究[D].华中科技大学，2009.

[9] 吕新桥. 联机手写汉字识别技术研究[D].华中科技大学，2009.

[10] 陈正铭，霍英.编辑距离算法在中文文本相似度计算中的优化与实现[J].韶关学院学报，2015（12）.

[11] Levenshtein V I. Binary Codes Capable of Correcting Spurious Insertions and Deletions of Ones[J]. Problems of Information Transmission， 1965， 1（1）： 8-17.

【通联编辑：唐一东】