基于多重几何特征和CNN的脱机手写算式识别①

付鹏斌,彭荆旋,杨惠荣,李建君

(北京工业大学 信息学部,北京 100124)

目前的脱机手写识别技术可以精确高效地识别数字、英文字母和汉字[1–6],却无法较好地处理具有复杂空间结构关系的手写数学算式.已有的一些识别算法[7,8]可以实现简易的数学算式的判别,但对于一些具有复杂空间组合及包含关系的手写算式,不能有效地识别.Aly 等[9]提出仅利用相邻字符之间的空间关系进行算式识别,但对于特殊字符,如小数点等,没有独立的识别方法,还需进一步考虑相邻字符的识别结果.Wang 等[10]提出了一种基于编码-解码器框架的新型多模态注意网络,用于手写数学算式识别,该方法在CROHME 2014和CROHME 2016 数据库上达到了54.05%和50.56%的识别准确率,尚不能满足应用需求.Dai 等[11]实现了一款基于少量训练集的脱机手写算式识别系统,实验结果显示,该系统的识别准确率为80%.胡龙灿等[12]基于Android 平台开发了一款手写数学算式识别系统,但并未实现对识别的数学算式进行智能计算的功能.

鉴于以上研究成果不能较好地识别具有复杂空间组合及包含关系的脱机手写数学算式,且不具备智能计算功能.本文提出了一种基于多重几何特征和CNN的手写算式识别的解决方案,可有效提高手写算式识别的准确率,并以此为基础设计了手写算式识别系统,解决了数学算式智能计算问题,实现了手写算式的自动评阅,可应用于中小学课堂.

1 相关工作

1.1 图像预处理

图像预处理效果的好坏直接影响到字符识别的准确率.本文采取的图像预处理步骤如图1所示.

图1 图像预处理

原始图像来源于手机或平板电脑等数字拍照设备,由于应用场景为各类中小学课堂,学生拍照会出现角度倾斜、光照不均等情况.预处理时,首先基于顶点提取算法[13]对原始图像进行倾斜校正,接着采用自适应的高斯阈值分割算法对倾斜校正图像进行二值化.为有效去除图像噪声,保证图像分割质量,本文采用高斯去噪算法对二值化图像进行降噪操作,并基于圆形膨胀算法连接图像中的断裂笔划,生成原始图像的黑白图.然后,依据字符切分算法[14]对黑白图进行切分,得到单个字符图像.最后对字符图像进行重心归一化和尺寸归一化[15],生成了28×28 像素的目标图像.

1.2 数据准备

本文在MNIST 数据集的0～9 十类数字字符的基础上,新增了“+,–,×,÷,<,>,=,(,),√”等10 类常用数学符号.收集了不同年龄段的学生和部分成人的手写体数据,并以此为基础,经平移、旋转、缩放、腐蚀、膨胀、加噪等数字图像处理算法,形成了每类数学符号图像约为9000 张,总计92 429 张的数学符号训练集.并将其和MNIST 数据集合并,生成了手写数学算式的字符训练库EQU-MNIST,该数据集包含20 类手写字符,合计162 429 条数据.

2 基于CNN的字符识别

2.1 字符识别

文中用于单个字符识别的卷积神经网络结构[16]如图2所示,网络模型包含两个卷积层、两个池化层和两个全连接层.

图2 CNN 模型

标准输入为一张28×28 像素的图像.第一层卷积层设定有32 个5×5 大小的卷积核,输出32 张28×28像素的特征图.然后设定第一个池化层的大小为2×2,经历一次池化操作,图像块大小从28×28 缩小到14×14,得到深度为32的特征图.将第二层卷积核设定为5×5,数量是64,再经过一个2×2的池化层可得到64张7×7 像素的特征图.最后是两个全连接层,第一个全连接层的神经元个数为1024,第二个全连接层的神经元个数为20.即文中的字符分类数,标签与字符的对应关系如表1所示.

表1 标签字符对应关系

2.2 实验测试及分析

为验证CNN 模型的泛化性能,实验统计了模型对数字和新增数学符号的识别准确率.训练集为EQUMNIST 字符训练库,测试集来自不同年龄段多名学生的手写体数据,包括每类字符1000 张,合计20 000 张的标准化字符图像.实验结果如图3所示.

观察图3柱状图的趋势可以发现,除“1”“7”“>”“)”4 类字符外,其他字符的识别准确率都稳定在98.5%以上,而最低的也达到97%以上,说明本文的CNN 模型对新的数据集也具有良好的适应能力.同时,97%以上的字符识别率也保证了本文分类模型的可应用性.

3 基于多重几何特征的手写算式识别

虽然CNN 分类算法在单个字符识别上已经达到97%以上的识别率,可直接进行整式的判别,却无法识别小数、分数、指数、根式等具有复杂二维空间结构的手写数学算式.为此,本文提出一种基于多重几何特征的脱机手写算式识别算法,算法流程如图4所示:首先,提取待识别手写算式的几何特征;然后,基于不同算式所属知识点的学段,结合多重几何特征定义结构解析规则,判定算式类别,实现识别模型,并重点针对小猿口算、作业帮(家长版)未实现的初中知识点中的复杂指数和根式识别进行优化;最后,采用分治算法实现由以上各种算式组合嵌套的复合手写算式(见图5)识别.

图4 手写算式识别算法流程图

图5 复合手写算式样例

3.1 多重几何特征提取

文中设定原始图像的左上角坐标为坐标原点,坐标轴为X 轴水平向右,Y 轴竖直向下.因此经图像预处理后的字符图像g(x,y)除有效像素值外,还包含一组四元组信息(xmin,ymin,xmax,ymax),即图6中字符最小外包矩形的左上角坐标,右下角坐标.基于以上信息,本文选取字符宽高比 (WHR),中心坐标(xcenter,ycenter),质心坐标(xmass,ymass)作为单个字符的几何特征,结构模型如图6所示.

图6 字符几何特征

字符几何特征的定义如下:

定义1.图像的质心,也称为图像的重心.将图像中每一点的像素值理解成此点处的质量.图像的质心反映了目标像素值的集中位置.假设图像g(x,y)的(p+q)阶矩为:

依据(p+q)阶 矩定义图像g(x,y)的质心坐标.

以上定义反映的是单个字符的几何特性,不能有效地表达相邻字符间的空间位置关系.为进一步实现算式符号的重组识别,本文基于单个字符的几何特征,选取高度比 (HR),宽度比(WR),质心偏移角度 (α),中心偏移量 (δ),水平重叠区间比(HOR),垂直重叠区间比(VOR),多字符中心坐标(Xcenter,Ycenter)作为判断算式类别的几何特征.文中设定目标字符序号为2,前一字符序号为1,后一字符序号为3.字符对的结构模型如图7所示,以前一字符的质心坐标为坐标原点,坐标轴为X 轴水平向右,Y 轴竖直向上.

字符对几何特征的定义如下:

定义2.如图7所示,依据字符对的质心坐标定义质心偏移角度.质心偏移角度反映了相邻字符间的相对位置关系.

图7 字符对几何模型

定义3.基于前一字符的高度值和字符对的中心坐标定义中心偏移量.中心偏移量反映了相邻字符在竖直方向上的紧邻度.

定义4.据字符的四元组信息定义水平重叠区间比,垂直重叠区间比.HOR,VOR分别反映了相邻字符在竖直方向和水平方向上的投影重合度.

其中,m ax(v1,···,vn)表示n个值中的最大者,min(v1,···,vn)表示n个值中的最小者,[m,n]表示端点为m,n的闭区间,len([m,n])表示区间长度,即len([m,n])=n−m.

定义5.于多个字符的二维坐标定义多字符中心坐标:

3.2 小数和分数识别

小数点通常位于小数运算中相邻两个字符的偏下位置,因此本文基于字符高度,中心坐标,相邻字符识别结果等特征,设定小数运算的判定规则如下:

如果目标字符与相邻两个字符满足上述判定规则,则说明字符间属于小数关系,文中设定小数点的字符标记为20,进一步得到小数识别算法流程如图8所示.

图8 小数识别算法流程图

分数是由分子、分号和分母组合的具有上中下位置关系的数学算式.本文选取宽高比,中心偏移量,水平重叠区间比,多字符中心坐标作为分数运算的几何特征识别指标.在识别分数时均转换为等价的除法运算,同时,添加一组圆括号保证分数运算转换为除法运算时的优先级.具体识别算法流程如图9所示.

图9中的分数识别算法只能识别真分数,假分数等常见分数,为使识别算法能够完全实现中小学数>学课堂中的分数判别,本文进一步处理类似于等带分数.基于分数识别算法,设计带分数的识别算法如算法1.

算法1.分数识别算法.输入:原始识别列表oriList输出:带分数识别结果串resultStr Step 1.逆序遍历原始识别列表oriList,记录带分数的整数系数在列表中的终止索引endIndex,起始索引startIndex.Step 2.基于索引从原始列表oriList 中提取带分数的整数系数列表,并依据表1标签字符对应关系转换成整数字符串integerStr.Step 3.基于终止索引endIndex 从原始列表oriList 中提取带分数的真分数字符串fractionStr.Step 4.将带分数的整数系数字符串与真分数字符串相加,生成结果字符串resultStr=“(”+integerStr+“+”+fractionStr+“)”.

图9 分数识别算法流程图

3.3 指数和根式识别优化

指数运算属于典型的上下结构的数学算式,指数一定位于底数的右上角位置,因此本文基于字符高度,高度比,质心偏移角度多重几何特征,设定指数运算的判定规则:

如果相邻两个字符满足上述判定规则,则说明字符间属于指数关系,进一步得到指数识别算法的伪代码如下:

其中,函数isexponential 基于判定规则实现相邻字符指数关系的判别,函数list2str 依据表1将标记列表转换成识别字符串.

为实现对根式识别模型的优化,首先需要完成对特殊符号根号的判别,而根号(√)与表1中的字符对勾(√)在形态上十分相似,如果仅依据CNN 模型进行识别,可能会导致最终分类结果的错误,进而对根式的判别带来干扰.因此,本文提取根号的拐点特征和半包围结构特征,实现根号识别算法见算法2.

算法2.根号识别算法.输入:字符图像image输出:识别结果result(True or False)Step 1.基于角点提取算法获取字符的拐点信息,并对其进行编号(如图10(a)所示),如果拐点个数小于4,则result=False;否则,执行Step2.Step 2.依据根号的①②③拐点信息定义半包围结构的有效区域(如图10(b)所示).HORVOR Step 3.基于,判断半包围结构的有效区域内是否存在其他字符,如果不存在,则result=False;否则result=True.

基于算法2,本文依据“减法”思想完成根式的识别:首先从字符图像集中移除根号,再进行根指数和根底数的识别,最后完成根式字符串的构建,具体算法实现如下:

算法3.根式识别算法.输入:字符图像集images输出:根式识别结果串radicalStr

Step 1.遍历字符图像集images,基于算法2 判断是否存在根号,如果存在,则执行Step2;否则,返回根式识别结果串radicalStr.Step 2.基于根号的②③拐点信息提取根指数图像,识别分类并转换为根指数字符串indexStr.Step 3.基于根式转指数的运算规则,若indexStr为空,则indexStr=“1/2”;否则,indexStr=“1/”+indexStr.HORVOR Step 4.依据根号的半包围结构的有效区域,结合,,提取根底数图像,识别分类并转换为根底数字符串baseStr.Step 5.构建根式识别字符串radicalStr=“pow(”+baseStr+“,”+indexStr+“)”.

图10 根号的结构特征

根式识别算法如算法4.

3.4 复合算式识别

数学算式具有二维空间结构,在水平分布的基础上,分数、指数、根式还具有其内嵌结构,这种特征使得复合算式识别过程适合用数据结构中的树来表示.如图11所示,本文采用分治算法实现复合数学算式的识别,具体识别过程如图11所示.

图11 复合算式识别

图11描述了手写复合算式的识别过程:首先,基于分治算法,结合已实现的手写算式识别算法(见图4)将复合算式逐层分解,直至所有的简单算式(如小数,分数,指数以及根式)和单个字符都位于树的最底层,作为树的叶子节点.然后,基于运算规则将这些简单算式和字符向上合并,直到生成树的根结点为止,即手写复合算式被识别出来.以树的第二层第一个节点(从左往右)为例,依据手写算式识别算法将该算式判定为分数;接着提取分子笔划部分,并将这部分笔划序列按照字符切分、手写算式识别的处理方式递归进行,直到所有节点均不可再拆分为止,然后逐层将子节点的识别结果串组合生成父节点的识别序列,最终得到分子的识别结果串,同理,得到分母的识别结果串;再将分子,分号,分母三者的识别结果串组合作为一个新的识别序列添加到根节点的子识别序列中.

4 实验测试与分析

4.1 实验环境及数据

基于以上研究,设计并实现基于多重几何特征和CNN的脱机手写算式识别系统.系统环境参数信息如表2所示.

表2 系统环境参数信息

实验测试数据来自不同年龄段32 名学生(小学生10 名,初中生10 名,大学生12 名)的76 幅手写体数学算式图像,合计2660 个手写算式,算式类别及数量分布如表3所示.

表3 算式类别及数量

4.2 实验结果及分析

为验证识别算法的有效性,本文采用算式识别准确率作为评价标准,数学定义如下:

其中,p表示算式识别准确率,TN表示正确识别算式的个数,FN表示错误识别算式的个数.

本文设定图像分辨率、光照、噪声等图像特征参数作为影响实验结果的自变量.采用控制变量法验证不同特征参数对算式识别率的影响,参数取值及对应的实验结果如表4所示.

表4 参数取值及对应的实验结果

图12 图像分辨率对算式识别率的影响

图13 光照对算式识别率的影响

图14 噪声对算式识别率的影响

观察图12～图14中折线图的走势,每组实验的折线图并未完全重合,说明图像分辨率、光照、噪声等图像特征参数对实验结果有一定的影响,但仍在合理范围内.同时,本文系统在九组实验中的算式识别准确率基本稳定在80% 以上,算式平均识别率也维持在88.15%～90.43%之间,验证了该系统在不同条件下均具有较好的稳定性,可靠性和实用性.

为验证手写算式识别算法对复杂指数和根式识别的优化效果,进一步评价系统的性能,将本文系统与目前市场上主流的小猿口算、作业帮(家长版)进行对比实验,比较不同系统的算式识别准确率,测试集采用本文的实验测试数据.系统识别效果截图见图15,实验结果如表5所示.

由图15可知,本文的手写算式识别算法实现了对初中知识点中复杂指数和根式识别的优化.同时,分析表5可知,本文系统的算式识别率最高,相比其他系统的优势十分明显,进一步验证了本文系统的实用性.

图15 3 个系统识别效果截图

表5 不同系统算式识别率对比

5 结论与展望

脱机手写算式识别一直是智慧教育领域研究的热点与难点,本文重点针对中小学数学课堂中的手写算式,提出了一种基于多重几何特征和CNN的脱机手写算式识别的解决方案,有效地提高了手写算式识别的准确率,并以此为基础设计实现了脱机手写算式识别系统,解决了数学算式智能计算的问题,实现了手写算式的自动评阅,将应用于陕西省数所中小学的课堂教学中.依托该系统可以高效便捷地完成学生作业的批阅,减轻教师负担,减少重复劳动和主观误判,显著提高课堂效率,具有很强的实际意义.