基于遗传算法的汉字书写水平评估算法研究

陈 洁,王 强,杜 嵘

(江苏金盾检测技术股份有限公司,江苏 南京 210042)

0 引言

我国中小学生教育高度重视汉字书写,2022 年教育部印发义务教育语文课程新标准,依据该标准,在三至六年级语文课程学习中,每周应至少安排1 课时书法课,并且中小学生都需要掌握毛笔楷书[1]。 由于汉字的字形数量繁多、结构复杂、书写有规律、形体差异度高等特点,目前对中小学生汉字书写水平的评估主要依靠教师人工评估。 人工评估方式较大地增加了语文教师的工作量,在确保评估质量的前提下,批阅速度很难大幅提升。 因此,目前有较多的研究尝试采用计算机算法评估汉字书写水平,采用的方法主要集中在机器学习和人工智能领域,比较典型的有以下3 类。

第一类:将书写过程视为笔迹的移动过程,提取动态信息[2-3],通过与标准字的动态信息与笔画粗细分析和对比实现评估。 由于书写的动态信息获取需要使用电子设备,此类方法又称为联机评估。

第二类:基于机器学习的方法,如深度学习[4]、SVM 分类的方法[5],尝试通过特征学习,将被评估的字归类成优、良、中、差4 个级别实现评估。

第三类:通过书写字的骨架和轮廓实现评估[6],基于待评估字与标准字的骨架差异度实现分析,给出评估结果。

第二、三类方法由于不需要使用电子设备提取动态信息,又称为脱机评估。 从上述的各类方法可以看出,第一类联机评估方法需要使用专用电子采集设备,不便于在日常学习环境中应用推广,而第二类方法需要大量的训练数据集以及复杂的神经网络架构,存在训练难度大、周期长且难以提供书写问题分析等不足。

综合分析第一、二类方法的不足,本文讨论的算法采用的是第三类方法。 中小学生书写多为硬笔书写的正楷,笔画粗细与书写水平评估结果关联度不高,实现书写水平判断的关键在于字的骨架和轮廓。由于汉字结构的复杂性和书写过程的随机性,通过图像提取汉字的骨架和轮廓比较困难。 因此,本文所提的方法将待评估汉字的笔画交叉点作为书写水平的评估特征,通过分析待评估汉字的笔画交叉点与标准字笔画交叉点的偏移程度实现对书写水平的评估。本文方法的优点在于不需要大量的训练数据与复杂的训练过程就可以实现对书写水平的评估,而且可以根据评估字不同部位的交叉点偏移度分析出书写者的书写问题。

1 关键点配准与遗传算法

1.1 关键点配准

关键点配准是指找到两幅图片上的关键点序列的对应关系,即:存在P1、P2两张图片,其中(x1,x2,…, xn)∈P1,(y1, y2,…, yn)∈P2, 找到点集X与点集Y 的对应关系如式(1)所示:

其中:f()是点x 与点y 的配对评估函数,根据配对的应用目标不同有不同的评估函数。 关键点配准算法一般要求在完成点配对之后,各点对评估函数值的总和最小。

关键点配准算法的应用范围很广,指纹识别是其最为经典的应用[7],除此之外,还有医学图像配准、点云配准等[8-9]。 这些应用场景下将关键点配准算法视为矩阵的变换,因为类似指纹、点云的应用场景下,两张图片相对应的点在各自所在的点集中相对空间位置变化不是很大,可以视为点集矩阵的刚性变换,如:点集的平移与旋转来实现配准。 但是,在本文的应用目标下,由于书写的随意性,待评估字图片中提取的笔画交叉点与标准字的笔画交叉点之间很难采用刚性变换匹配。 因此,本文提出基于邻近点相对位置的笔画交叉点配对评估函数,采用搜索交叉点配对空间的方式实现配准。

1.2 遗传算法

遗传算法(Genetic Algorithm,GA)是一种优化求解的算法,1995 年由John holland 博士提出[10],与粒子群算法、蚁群算法等都属于拟生类的优化算法,其基本思路是模拟生物进化过程中基因的演化,在目标求解空间中找到优解。 遗传算法的核心组成包括:

(1)编码策略。

编码策略即提出一种编码方案,将问题的求解空间映射成基因序列。 基因序列一般是一个二进制序列,每个序列对应一个求解空间中的解。

(2)适应度函数。

适应度函数即评估函数,评估某一个编码序列对于目标问题求解的优劣度,优劣度会影响到下一步遗传操作。 适应度函数需要满足单值、连续、非负等要求。

(3)遗传操作。

当前已有的编码序列集合中,通过对遗传操作生成下一代基因编码序列。 主要有:变异操作按一定概率修改编码序列中的位。 交叉操作按一定概率交换两个序列的不同编码部位;选择操作按适应度函数找到最优的N 个序列,直接放入下一代序列集合。

本文需要实现的是待评估书写字与标准字的关键点配准,而使用二进制编码序列可以很方便地表达点配准方案,如:编码序列中的1 位表示点配准的对应点。 因此本文的求解目标可以很方便地转换成遗传算法的编码方式,采用遗传算法实现关键点配准的求解。 此外,本文采用遗传算法实现笔画交叉点配对方案的搜索,寻找关键点配准优解方案,还有两个原因:一是单字配准的计算量仍然可观,据统计,汉字平均笔画有11.2 画,交叉点平均10 个左右,按全局搜索则关键点配对的方案平均超过百次,每次都需要执行评估相关的浮点计算,因此单字配准的计算量仍较大;二是遗传算法比较适应于分布式计算架构,按本文前述需要实现对中小学生的日常书写字评估,而正常一所中小学生每周的书写作业产生的待评估书写数量很大。 遗传算法本质上是可以并行分布式的,所以基于分布式计算框架实现的遗传算法适应于本文应用场景的需要。 因此,本文在进行了关键点配准的相关研究之后,选用遗传算法实现对笔画交叉点的配准求解空间搜索。

2 基于遗传算法的笔画交叉点配准算法

2.1 笔画交叉点向量的构建

通常汉字书写的脱机评价算法在评价之前,需要对用户书写的汉字图片进行相关的平滑、去噪与二值化处理,再对汉字图片进行细化、去毛刺等算法处理,获得待评价汉字的笔画交叉点。 由于本文关注的是关键点配准问题,此类的预处理并不是本文算法解决问题的主要范围。 为此,本文采用人工标注的方式实现对标准字与待评估字笔画交叉点的提取。 人工标注笔画交叉点的标准字与待评估字如图1—2 所示。

图1 标注交叉点的标准书写字

如图1 和图2 所示,本文通过直接在写字书的图片上标注出交叉点,以获取各交叉点的二维坐标位置。 虽然图1 和图2 经过拍照书写字来采集电子图片,并缩放到同样大小的尺寸,但由于拍照远近、书写位置与大小的变化,直接使用笔画交叉点的二维坐标作为评估算法的点向量显然无法实现有效评估。

图2 标注交叉点的待评估书写字

结合汉字从上向下、从左向右的书写习惯以及交叉点配准主要依赖于周边相邻的点,本文采用相邻位置构建交叉点向量。 对于相邻的点,本文给定的判断算法如下。

算法1:关键点X 的相邻点集构建算法。

(1)假设存在一点X,其二维坐标为(x1,x2),设X 的相邻点集合E 为空;

(2)构建候选点集C,将图中所有关键点排序放入C,C 中各点的排序是以各点与X 的欧氏距离从小到大排列;

(3)构建边集合L,边集合为相邻点集合E 中各点按顺序依次连接形成的封闭多边形的边;

(4)以X 为起点,从候选点集中取出Y 作为终点,构建线段XY;

(5)判断线段XY 与边集合L 中的边是否相交;

(6)如果相交,则Y 不是X 点的相邻点,丢弃该点;如果不相交,则将Y 放置到相邻点集E 中,同时从候选点集中删除Y。

显然,依据上述算法通常一点最多有3 个相邻点。 根据最终本文算法的配准评估,可以预定相邻集合的最少点数,来增加配准点的相邻点个数。 基于上述相邻点的构建算法,本文给出的点向量定义如下:

假设存在一点X,其相邻点集合E,且相邻点集合E 的长度为N,则X 的点向量空间维度为N,其中第i 维是X 与相邻点集合E 中第i 点构建的距离与角度对< γ,θ>:

如上所述,则本文构建的长度N 的关键点向量为:(<γ1,θ1>,<γ2,θ2>,…,<γn,θn>)。 在构建完成之后,再进一步对点向量各维度欧氏距离进行规一化,如式(3)所示,最终得到本文的关键点向量。

2.2 编码与关键点配准评估函数

编码是遗传算法的基础,由于汉字书写的随意性,经常会有待评估书写字的笔画交叉点数与标准字的笔画交叉点数不一致,因此,本文的编码方案选择二者中最大交叉点数作为编码的长度,具体的编码方式如下:

若标准字的笔画交叉点数为N,待评估书写字的笔画交叉点数为M,且有N>M,则本文算法的编码长度为N。 若某个编码的第i 位为1,且其为该编码的第j 个1 位,则其代表待评估书写字的第j 个关键点应与N 的第i 个关键点配准。

若M>N,反之亦然。 关键点配准评估函数也是本文遗传算法的适应度函数,实现对已有编码表达的关键点配准方案的评估。 设有关键点向量对,首先给出针对该关键点向量的配准评估函数如式(4):

由于各关键点的相邻点个数并不一定相同,因此在评估函数中,定义n 为关键点向量i 与关键点向量j这二者相邻点个数的最小值。 G(i,j)值为二关键点配准之后,前n 个相邻点的二二对应围成的几何三角形面积的平均值。 从上文所述的关键点向量定义可知,关键点向量的维度是按对应相邻点与关键点的距离远近,从小到大排序。 因此G(i,j)函数体现出离关键点越近的相邻点对配准评估的值影响越大。 此外,显然,G(i,j)值越小,两个关键点的配准效果越好。

基于上式(4),本文提出关键点配准评估函数如下式(5):

从式(5)可以看出,设有标准字的笔画交叉点向量数N,待评估书写字的笔画交叉点向量数M,且N

除了上述的编码与评估函数之外,由于本文关键点配准对编码的长度和编码中1 的位数有要求。 因此,需要对遗传算法的变异、交叉操作时,做一定的修改,以保证生成的新编码中1 的位数与需要配准的关键点个数相同。

4 实验与总结

基于上述本文关键点向量的构建与评估函数,本文实现了遗传算法的改造,并完成了小样本数据的配准实现。 本文按汉字的结构分成上下、左右、包围以及独体4 种类型,每种类型一共选择了20 个汉字,选择了20 个小学生,每个汉字书写4 次,然后采集形成图片集,如图3 所示。

图3 待评估汉字样本

同时,本文也开发了一个小型的JS 前端页面,用于采集待评估汉字的笔画交叉点,构建交叉点数据集,对于书写字算法与标准字的最终配准结果判断,本文采用人工目测的方式,依据配准点所在字的大体位置,将配准最终结果分成4 类,准确、较准、一般、差。 基于数据集,实现并验证了本文算法。 在默认的相邻点判断算法情况下,也即1 个关键点最多有3 个相邻点,配准结果准确率为78.74%,而默认相邻点为4 个的情况下,配准结果准确率为88.61%。

由本文的实验结果可以看出,本文的算法具有较高的实用性,与其他同类联机评估或者使用深度学习的方法相比,本文算法不需要大量的数据集,也不需要复杂的训练过程。 本文算法基于遗传算法,能适应大规模评估的需要,因而也具有一定的应用推广优势。