基于相似度的手写汉字笔划鉴别方法实验研究

白晓东, 姜 杰, 邓红静, 李 艺

(南京师范大学 1a.计算机科学与技术学院; 1b.教育科学学院，江苏 南京 210023;2.江苏省信息安全保密技术工程研究中心，江苏 南京 210097)



基于相似度的手写汉字笔划鉴别方法实验研究

白晓东1a，2, 姜 杰1b, 邓红静1b, 李 艺1b

(南京师范大学 1a.计算机科学与技术学院; 1b.教育科学学院，江苏 南京 210023;2.江苏省信息安全保密技术工程研究中心，江苏 南京 210097)

针对手机和平板电脑上手写汉字主流的xml存储格式，提出了一种对识别用户手写汉字笔划的算法。算法首先从三种结构特征对手写汉字进行编码，然后计算用户字笔划、模板字笔划之间不同编码集合的相似度，最后组合多种相似度识别手写汉字的笔划，并通过三种应用实验验证方法的有效性。笔顺的判别一直是手写汉字识别的难点，文章中提出的方法笔顺的识别率高达95%以上。此算法在用户字的多笔、少笔判别、笔顺判别、整字的正确性以及美观性判别等方面都有着广泛的应用。

改进型Hausdorff距离; 方位编码; Voronoi图; 拓扑相似度

0 引 言

当前，以手机和平板电脑为代表的移动式智能电子产品已经成为人们生活中不可或缺的部分，与之相关的海量软件也伴随而来，在众多的软件中，汉字手写软件无疑是最具中国文化特色的产品，如今，汉字手写类软件已经广泛应用于各个领域[1]。然而，为此类软件提供支持的汉字手写研究多集中在汉字识别环节，随着人们对汉字手写平台需求的不断深入，可能要求计算机对手写汉字的正确性、美观性、书写风格等做出评价，甚至要求计算机对书写者性格、心理状态等做出准确的判断，这给汉字手写研究带来了新的挑战。

手写汉字识别后研究所涉及的判断与评价，其关键步骤是笔划正确性识别：即判断手写汉字的每个笔划是什么笔划，书写是否正确，同时判断它的书写顺序是什么。然而，汉字的种类多样、结构复杂，每个汉字都由若干个笔划组成；每个人书写汉字的笔顺和笔划也可能不一样，这就造成了书写后的汉字可能存在不同程度的“畸变”，这些都给手写汉字正确笔划的辨识带来了困难。

手写汉字识别后研究通常都是通过与模板字比对,完成对其细节的判断与评价。人们辨识手写汉字的某个笔划时一般会这样考虑：“在正确的方位上笔划的形状正确，同时它与其它笔划的关系也是正确的，那么，就是这个笔划”，由此可见，方位、形状和笔划间拓扑关系这三个手写汉字的结构特征是辨识正确笔划的关键因素。本文通过抽取汉字笔划上述三种特征的编码，计算手写汉字笔划与模板字笔划三种编码的相似度，最后通过总相似度来决定手写汉字笔划与模板字笔划的对应关系，从而判断出手写汉字的笔划是否书写正确，笔顺是否与标准字一致，而且可以发现是否有多笔、少笔的现象发生。与传统处理方法相比，这种方法不需要对原始数据进行平滑、规整等预处理，减少了中间环节，提高了识别效率。

1 判别前处理

联机手写汉字测试多采用CASIA的OLHWDB数据库，而目前移动设备主流的方法是将手写汉字的轨迹信息和时间信息存储在xml文件中，如图1所示，用户字和由专家书写的模板字均保存于xml文件中：手写汉字由笔划stroke构成，而stroke由point构成，每个point记录了笔尖(指尖)移动轨迹的x、y坐标和其时间戳，因此，移动手写设备中的汉字笔划被表述成了二维空间的点集信息。判别前需要对模板字和用户字进行空间配准，经典配准方法首先要计算匹配对象的最小覆盖区域，如最小凸闭包(MCC)、最小外接矩形(MBR)和最小外接圆(MBC)等[2-3]，然后经过仿射变换或RST变换使两个匹配空间重合[4-5]。由于用户字与模板字可能存在着较大差异，而且这种差异是个体的差异(例如用户字可能存在多方向倾斜)，而非系统性的，因此用上述方法进行空间配准并不科学。本文根据移动设备上手写汉字笔划的存储特点，简化了这一过程：首先以模板字点集中的xmin、xmax、ymin、ymax组成水平矩形作为待匹配空间，然后对用户字的所有笔划(点集)做RST变换，即

图1 移动设备上手写汉字的存储与比对

2 编码的抽取

2.1 笔划方位编码和形状编码的抽取

以AR的对角线交叉点为圆心，将半对角线4等分分别为半径，做4个同心圆，从圆心做射线8等分同心圆，则区域被分割为32份。同心圆从内向外编号，分别为1到4，从水平45°开始顺时针旋转，8个方向依次编号为1～8，如图2所示。

图2 用于方位编码和形状编码的坐标体系

笔划点集中的所有点都可以用c(i,j)来表示其方位，其中i表示此点所在的方向1～8，j表示此点距离中心点的远近，即相对位置1～4。笔划k的方位编码可以用c(i,j)的集合表示，即：

2.2 笔划的拓扑关系编码的抽取

笔划的拓扑关系是笔划间交、接、邻、离的关系，它是识别笔划时需要抽取的重要特征，可以通过常规的几何方法获取一个手写汉字多个笔划间的拓扑关系，但是过程非常繁琐，而且容易出现误判或漏判的情况，本文中采用一种基于Voronoi图的笔划拓扑关系判断算法[6-8]，方便快捷且不会出现漏判的情况。

(a)

(b)

(c)

(d)

算法 foundTopolpgy(V(P)):

输入 以汉字笔划端点和笔段端点为基元的AR区域Voronoi图。

输出 每个笔划与其它笔划的拓扑关系集。

(1) 初始化队列Q，将所有的笔划(笔划端点+笔段端点)放入;

(2) 初始化队列T，将所有的笔划(笔划端点+笔段端点)放入;

(3)a=0;

(4) while(Q不空){

(5) 从Q中取出笔划si;

(6) while(T不空且i!=j){

(7) 从T中取出笔划sj;顺序扫描si中的点;

(10) 从T中去除sj;break;

(13) 从T中去除sj;break;

(14)a++;

(15) };

(17) 从T中去除sj;break;

(18) if(T不空且剩余笔划数为t);

(20) 将所有的笔划放入T;从Q中去除si;a=0;

(21) }。

3 相似度计算

3.1 方位相似度和形状相似度的计算

方位相似度的计算要同时考虑方向和位置因素，而且二者同等重要，因此，可采用方向和位置的乘积关系表示方位。Hausdorff距离(HD)是衡量元素不相等点集相似性的经典方法，Dubuisson和Jain[9]提出了改进型Hausdorff距离(MHD)。MHD将单向Hausdorff距离定义为

算法 simpos(S,S')。

输入 模板字方位码集S和用户字方位码集S'。

输出 方位相似度矩阵U。

(1) 初始化队列Q，将S的所有笔划放入;

(2) 初始化队列T，将S'的所有的笔划放入;

(3) while(T不为空){

(4) 从T中取出s'i;

(5) while(Q不为空){;

(6) 从Q中取出sj;

(7) 计算s'i和sj的方向MHD：HMND(s'i,sj);

(8) 计算s'i和sj的相对位置MHD：RMND(s'i,sj);

(9)U(i,j)=1-HMND(s'i,sj)×RMND(s'i,sj)/Tpos

(10) }

(11) 将S的所有笔划放入Q;

(12) }

说明：Tdirection=max{HMND(s'1,s1),HMND(s'1,s2),…,HMND(s'm,sn)};

Tlocation=max{RMND(s'1,s1),RMND(s'1,s2),…,RMND(s'm,sn)};

方位相似度矩阵表示为

U=

V=

3.2 拓扑关系相似度的计算

拓扑关系相似度的计算要考虑交、接、邻、离之间的远近关系[10-11]：交与接最相似，与邻的关系次之，与交最不相似的是离；接与交、邻的关系最相似，与离的关系最不相似；邻与接、离的关系最相似，与交的关系最不相似；离与邻最相似，与接的关系次之，与交的关系最不相似[12-13]。为了体现交、接、邻、离之间的远近关系，定义笔划sk的拓扑数量值：

ftopology(sk)=sk(intersect)×23+sk(phase)×22+sk(adjacent)×21+sk(depart)

识别笔划，交的关系最为重要，接次之，然后才是邻、离[14-15]，上述定义体现了这个因素。同时，将交、接、邻、离映射成数值使用户字和模板字在拓扑关系上具有了可比性。这样定义用户字笔划s'i和模板字笔划sj的拓扑相似度

拓扑关系相似度矩阵为

W=

3.3 总相似度

总相似度是通过计算3种特征相似度的加权平均得到的，设置不同特征的权值可以使总相似度更加体现手写字的特点。由于用户在书写时随意性较大，笔画变形可能较严重，因此考虑给形状相似度较小的权重。上文中的U、V、W矩阵都是无量纲的矩阵，通过矩阵的加权平均就可以获得总相似度矩阵：

其中，ω1=ω2=0.4，ω3=0.2。矩阵S是用户字笔划识别的依据。通过S，可以对用户的书写做如下判断：

(2) 是否存在错误的笔划：若S的行向量Pi的每一个分量ak，k=1,2,…,n均小于T，则笔划i是错误的笔划。T是相似度阈值。

(4) 特殊情况的处理，用户字笔划i1和笔划i2匹配到相同的模板字笔划j：① 如果Pi1和Pi2都还有大于T的分量，则选ai1和ai2的较大者与笔划j匹配；② 如果Pi1和Pi2中的某一个只存在一个大于T的分量，另一个还有大于T的分量，则选择前者与j匹配；③ 如果Pi1和Pi2都只存在一个大于T的分量，则选择ai1和ai2中较大者与笔划j匹配，另一个被视为错误的笔划。

4 实验与分析

实验选择三星GT-N8010作为手写设备，屏幕大小10.1″，屏幕像素密度149PPI，4核CPU，主频1.4 GHz，内存2 GB，Android4.0操作系统。书写工具为三星自带1 024级灵敏度S-Pen手写笔，实验程序模仿软笔书法效果。软件的界面风格如图4所示。测试字和测试对象的选择强调对整体的覆盖，以方便观察算法的有效性。共选用550个汉字作为实验用字，事先由书法专家制作完成。这550个汉字中，根据汉字的特点分别选取了独体字100个(I)、左右结构的汉字100个(II)、上下结构的汉字100个(III)、左中右结构的汉字加上中下结构的汉字100个(IV)、内外结构的汉字加半包围结构的汉字100个(V)、复杂结构的汉字50个(VI)，为了验证算法的效果，在这些汉字中，还特别标注了字形相似的汉字，例如“末”和“未”，“人”和“入”等，字形相似的汉字共52组，121个汉字(X)，每组2-4个汉字不等，为了做到无情境带入，测试时X组的汉字不依组别，随机呈现。括号中是每个组别的编号，550个测试汉字涵盖了所有汉字结构类型和繁简程度。分别选择小学生36人(P)、初中生45人(H)、普通成人20人(A)和文案工作者5人(I)作为书写测试对象，他们分别代表汉字初学者、汉字学习者、汉字使用者和汉字书写熟练者，可以覆盖汉字书写几乎所有的人群，括号中是他们的类别。被试的书写实验安排如表1所示。

第2组实验考虑到小学生是初学写字，容易出现多笔、少笔、笔划、笔顺等错误，而成年人已经形成了固定的书写习惯，也容易有上述错误，让他们写结构复杂的汉字错误出现的频率较高。第4组实验的考虑相同。实验共收集22 596个样本，其中有效样本19 372个，实验的分析过程在Eclipse KEPLER平台J2EE版本上编写java程序处理19 372个xml文件。

分别定义判断多笔、少笔的查准率和召回率为：

分别定义判断错误笔划的查准率和召回率为：

定义笔顺的识别率为：

表2是实验结果列表。

表2 手写汉字笔划识别的实验数据统计

从统计数据可以看出，多笔、少笔的识别基本没有错误，错误笔划的识别率也较高，笔顺的识别率虽然也在95%以上，但是还有待于提高。

5 结 语

本文从手写汉字的三种结构特征出发，对手写汉字进行编码，然后计算用户字笔划、模板字笔划之间不同编码集合的相似度，最后组合多种相似度识别手写汉字的笔划，并通过三种应用的实验验证方法的有效性。笔顺的判别一直是手写汉字识别的难点，实验证明，本文提出的方法对笔顺的识别率高达95%以上。

在此基础上，可以进一步研究如何评价手写汉字的正确性和美观性，还可以研究书写者的写字风格和心理状态，可以想见，这些研究在汉字书法教育、心理学等领域有着广泛的应用前景。

[1] 陈 邹.用户自适应联机手写汉字识别方法[D].深圳:哈尔滨工业大学深圳研究生院,2010.

[2] Shahabi C,Safar M.Efficient retrival and spatial querying of 2D objects[C]∥Proceedings of the IEEE International Conference on Multimedia Computing and Systems(ICMCS),1999,2:611-617.

[3] Safar M，Shahabi C.2D topological and direction relations in the world of minimum bounding circles[C]∥1999 International Database Engineering and Applications Symposium,1999:239-247.

[4] Latecki L J,La k'mper R.Application of planarshape comparison to object retrieval in image databases[J].Pattern Recognition,2002,35(1):15-29.

[5] Bengtsson A, Eklundh. Shape Representation by Multiscale Contour Approximation[J]. EEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(1):85-93.

[6] 周培德.计算几何——算法分析与设计[M].北京：清华大学出版社,2000.

[7] CHEN Jun, LI Cheng-ming, LI Zhi-lin,et al. A Voronoi-based 9-intersectionModel forSpatial Relations[J]. International Journal of Geographical Information Science,2001, 15(3): 201-220.

[8] LI Zhi-lin,ZHAO Ren-liang,CHENJun.A Voronoi-based Spatial Algebra forSpatial Relations[J]. Progress inNatural Science, 2002, 12(7): 528-536.

[9] Dubuisson M P，JAIN A K.A modified Hausdorff distance for object matching[C]∥Proceedings of the 12th IAPR International Conference on Pattern Recognition,1994:566-568.

[10] Eliseo Clementini, Paolino Di Felice, Peter van Oosterom. A small set of formal topological relationships suitable for end-user interaction [C]∥Advances in Spatial Databases Lecture Notes in Computer Science,1993,692:277-295.

[11] Clementini E,Difelice P D. A comparison of methods for representing topological relationships [J]. Information Science,1995,3(3):149-178.

[12] 林金坤.拓扑学基础[M].北京:科学出版社,2004:48-55.

[13] 邓 敏.矢量数据拓扑关系扩展模型的理论与方法[D].武汉:武汉大学,2003.

[14] 郭庆胜,杜晓初,刘 浩.空间拓扑关系定量描述与抽象方法研究[J].测绘学报,2005,34(2):123-128.

[15] 邓 敏,冯学智,陈晓勇.面目标间拓扑关系形式化描述的层次模型[J].测绘学报,2005,34(2):142-147.

Experiment Research on the for the Stroke of Handwritten Chinese Characters Identification Method Based on Similarity

BAIXiao-dong1a，2,JIANGJie1b,DENGHong-jing1b,LIYi1b

(1a. School of Computer Science and Technology, 1b. Education Technology Department of Education Science School, Nanjing Normal University, Nanjing 210097, China; 2. Jiangsu Engineering Research Center of Information Security Technoly, Nanjing 210097, China)

For the handwritten Chinese mainstream storage format of mobile phones and tablet PC, this paper proposes a handwritten Chinese character strokes recognition algorithms, Firstly the three structural features of handwritten Chinese characters are encoded, and then calculate the word stroke among users, templates word strokes similarity different set of encoding, and finally a combination of a variety of similarity recognize handwritten Chinese character strokes and three applications through experimental verification of the validity of the method. Stroke discrimination has been the difficulty of handwritten Chinese character recognition, and the recognition rate of the proposed method stroke up to 95%. The algorithm in user word multi pen and pen less discrimination, stroke identification, the whole character of the correctness and aesthetic judgment, etc. have a wide range of applications.

improved hausdorff distance; orientation coding; Voronoi diagram; topological similarity

2015-05-20

江苏省高校哲学社会科学基金项目(2011SJB8800287)；江苏省教育科学“十二五”规划项目 (D/2011/01/055)

白晓东(1969-)，男，河北唐山人，硕士，讲师，主要研究领域为计算几何、图形学、图像处理等。

Tel.：13851580972; E-mail: baixiaodong@njnu.edu.cn

HP 311

A

1006-7167(2015)12-0132-05