0 研究背景及意义

随着互联网的发展, 如拍照搜题、自动阅卷和题库建设等智慧教育应用层出不穷.由于在这些智慧教育应用中数学公式大多以图片的形式存在, 致使计算机无法直接理解这些公式, 从而影响后续针对课程资源和学生学习行为的分析和挖掘.为了提供更好的在线教育服务, 开展公式识别的研究显然是非常必要的.

公式识别是光学符号识别(Optical Character Recognition, OCR)的任务之一, 它相对于通常的光学符号识别有着其自身的特点: ①有些符号相似度高, 难以区分, 如减号、分号、连接符等; ②公式具有嵌套结构, 如开方运算嵌套分式、分式嵌套分式等, 正确理解公式结构相对比较困难; ③公式中的字符间存在相依关系, 如运算间的优先级关系, 以及符号的配对使用等, 一个符号识别错误或者位置不对导致整个公式无法理解.因此, 公式识别相对比较困难.

针对公式识别, 国内外大量的学者在提高符号识别准确率和确定公式结构方面进行了研究.一般情况下, 数学公式识别问题分为符号识别和结构分析这两个方面.

(1) 符号识别又分为字符分割、特征提取和识别. ①最常用的两种字符分割方法是投影法^[1]和连通域方法^[2].投影法是将图像中的符号像素进行垂直或水平方向上的投影, 再根据投影间隔等信息判断字符边界; 连通域方法是指将同属一个连通域的像素点进行连接, 且将其判定为一个字符.这两种方法在具体应用时也有其不足之处:投影法不能区分投影方向上有重叠的符号; 连通域方法会将属于同一字符的多个连通域分开. ②特征提取方面, 通常将每个字符图像规格化后分成5$\times$5的网格^[3], 然后计算每一个网格中的黑色像素点个数并作为一个特征, 但由于数学公式符号大小不统一, 在提取特征之前需要对其进行缩放, 这一过程可能导致像素点的信息丢失, 从而导致识别准确率降低. ③识别即利用各种分类器按照图像特征对其分类.

(2) Álvaro在对公式结构进行分析时, 定义了基于二维语法及其关联解析算法的统计框架^[4], 但计算复杂度相当大, 虽然引入了限制使得算法可运行, 但仍然不适用于搜索空间较大的情况.

本文将公式识别问题分为3个步骤:字符分割、符号识别和公式重组.字符分割是指将单个的公式符号从图片中分割出来, 以便进行识别; 符号识别是指通过OCR技术^[5]对图片中的文本和符号进行识别; 公式重组即根据已识别字符的上下文或位置信息确定该公式的原始结构.这3个步骤相辅相成, 所以需要同步提高分割、识别和重组的准确性, 才能保证学公式识别工作的有效性.

本文综合运用投影和连通域方法对字符进行分割, 并在分割后引入启发式规则, 将属于多个连通域的一个字符合并, 如"i""="等; 在符号识别方面, 采用改进的子区域像素点计算方法获取特征, 将单个字符在每个子区域内的像素点个数占总像素点个数的比例以及字符原始的宽高比作为该字符的特征, 以减小因公式符号大小不统一而识别错误的可能性; 最后, 对识别出的公式符号根据其位置信息进行重组, 并提出了运用递归思想确定公式及其子公式骨干线的方法.本文的主要贡献如下.

(1) 综合运用投影和连通域方法, 并引入启发式规则改进连通域字符分割的方法, 实现了高精度的字符分割.

(2) 选取像素点个数占比作为特征, 可忽略公式符号大小对符号识别的影响.

(3) 通过构建支持向量机(Support Vector Machine, SVM)模型, 对公式符号进行了分类; 根据一系列评估分类器的标准验证了本文方法识别符号的准确性和有效性;

(4) 提供了一种利用递归思想重构公式的方法.

本文后续结构:第1节介绍公式识别问题的国内外研究现状和本文实验的整体框架; 第2节介绍公式识别算法的具体实现; 第3节通过一系列实验验证本文所提方法的性能; 第4节总结公式识别所做的工作并展望未来研究的方向.

1 国内外研究现状

数学公式识别是OCR的一个子问题. OCR是图片中目标识别的一个子领域, 它旨在实现图片中局部图像到文本的一种映射, 与人脸识别、对象识别等任务相似. OCR技术最初仅能识别印刷体的数字、英文字母等, 并且要求字体等格式统一; 但经过多年不断的发展, OCR技术已经可以识别手写数字、质量较差的文档以及大字符集等.目前, OCR技术已广泛应用于车牌识别、金融相关业务中的银行卡号识别以及文档中的文字识别等.但现有的OCR应用在解决公式识别问题时, 仍存在以下问题: ①公式的嵌套结构可能非常复杂, 对于含有上标、下标、根号、分式的公式很难准确识别; ②公式符号较多, 且存在相似符号, 给公式识别提出了新的挑战; ③公式中符号间可能存在不同类别的相依关系, 比如优先级关系、配对关系等.

为解决这一问题, 国内外学者在公式识别的各阶段都进行了大量研究, 也取得了较好的成果.以下从字符分割、符号识别和公式重组这3个方面对目前研究工作进行概述.

1.1 字符分割

字符分割是将每个公式符号从公式图片中分割出来, 以便逐个识别公式中的字符, 主要有3种分割方法, 分别是基于连通域方法、像素投影方法、语法驱动方法. Maclean提出了一种使用关系语法和模糊集解析二维输入的方法^[6], 利用语法驱动字符的分割. Awal等人也是利用语法驱动支持识别工作, 在公式语法的约束下, 将表达式的识别转化为表达式分割、符号识别和二维结构识别的同步优化问题^[7]. Álvaro采用连通域方法对字符进行分割^[8], 但该方法不能很好地处理有粘连或者存在多个连通域的字符, 且因为该方法采用SCFG (Stochastic Context-Free Grammers)和CYK(Cocke-Younger-Kasami)方法对公式的结构从左至右地进行分析, 所以识别不出左上标和左下标. Chowdhury运用像素投影方法将二值化后的图像像素进行垂直和水平投影, 再设定邻域波峰的阈值, 将字符与其邻域字符分隔开^[9], 但该投影方法不能区分水平方向或垂直方向上有重叠的像素点, 如根号和被开方数不能有效分割.

1.2 符号识别

符号识别是根据每个公式符号的特征对其进行分类. Álvaro等人使用欧氏距离计算有标签的字符与待识别字符的距离^[8], 选取与当前字符距离最小的$k$个点, 最终确定该字符的分类.但该分类方法计算量较大, 若已分类字符有$n$个, 待识别字符有$m$个, 则共需要计算$(n\times m)$次, 时间复杂度为$O(m\times n)$. Toselli采用隐马尔科夫模型(Hidden Marcov Model, HMM)进行符号识别^[10], 但HMM要求符号有固定的先后顺序, 故不能准确识别左上标和左下标的关系.

1.3 公式重组

公式重组是将识别出的符号根据其位置进行重组, 确定原公式的结构. Aly等人提出将相邻符号之间的空间关系进行自动分类^[11], 他们认为公式符号之间的空间关系可以根据其相邻符号的位置等信息确定.关于混合公式的重组, 靳简明等人定义了11种基本的公式类型^[12], 提出使用分解树将原始公式分解为一系列能表示为基本公式类型的子公式, 并以此对子公式进行识别, 之后再根据嵌套关系将子公式重组成原公式.

2 公式识别方法详解

本文提出的公式识别方法的整体架构如图 1所示, 该框架将数学公式识别分为字符分割、符号识别和公式重组等3个步骤.

2.1 字符分割

进行符号识别的前提是将图像中的公式分割成单个符号.本文结合投影和连通域的方法对符号进行分割.因为投影方法适用于分割区域无重叠的情况, 而对于每行中的符号分割效果不佳, 如分式、根式都不能有效分割.所以使用投影法对多行公式进行行定位, 确定每一行公式的上、下边界.在每一行的公式中, 采用基于八连通域的方法分割每一个符号, 即自左向右扫描图片, 找到一个未被访问过的黑色像素点, 判断其上、下、左、右、左上、左下、右上、右下这8个位置上是否存在黑色像素点, 若存在, 则连接到同一个连通域; 并且引入启发式规则, 合并"i""j""="等被分成多个部分的符号. 图 2所示即为一行中公式符号的分割结果, 其中每一个符号用矩形框框出.

2.2 符号识别

符号识别工作包括特征提取、多分类模型构建以及分类器识别.下面具体介绍它们的实现方法.

2.2.1 特征提取

符号识别是根据每个符号的特征向量推断该符号所属的分类.为提高符号识别的泛化能力, 需要提取具有代表性且全面的特征.传统的特征提取方法是以子区域内像素点个数作为特征, 需要对公式图像进行缩放处理, 而不适当的缩放可能会影响图像的原始像素特征.本文对该特征提取方法进行了改进, 即将含有单个符号的图像按行列均分成5$\times $5的小区域, 计算子区域内黑色像素数占总的黑色像素数的百分比并将其作为特征, 这样就忽略了符号大小对识别结果的影响.考虑到将分号、减号、连接符等根据黑色像素个数占比作为特征进行分类效果不佳, 所以加入原始图像的宽高比, 形成含有26个特征值的特征向量.

2.2.2 多分类模型构建

进行多分类的常用分类器有决策树、神经网络、$k$NN($k$-Nearest Neighbor)、SVM等, 结合本文实验样本量较小、需要很强的泛化能力的特点, 本文选择SVM来实现识别任务.

SVM构造多分类器的方法有多分类SVM、一对多法(One-Versus-Rest SVMs, OVR SVMs)、一对一法(One-Versus-One SVM, OVO SVMs).本文采用OVO SVMs方法进行构造, 即在任意两类样本之间设计一个SVM, 当对一个未知样本进行分类时, 最终得票最多的类别即为该未知样本的类别.因此, 该问题的本质仍然是对样本进行二分类. SVM线性分类器的目标是在$n$维数据空间中找到一个分类超平面, 该超平面的方程可表示为

$ \begin{equation} \theta ^{\rm T}x+b=0, \end{equation} $

(1)

则计算未知样本落在超平面的某侧即可判断该未知样本的类别.

为减小分类错误的风险, 需要最小化SVM的代价函数, 即

$ \begin{equation} \mathop {\min }\limits_\theta C\sum\limits_{i=1}^m {\left[ {y^{(i)}\cos {\rm t}_1 (\theta ^{\rm T}x^{(i)})+(1-y^{(i)})\cos {\rm t}_0 (\theta ^{\rm T}x^{(i)})} \right]} +\frac{1}{2}\sum\limits_{i=1}^n {\theta _j^2 }, \end{equation} $

(2)

其中, $C$用于控制误分类训练样本惩罚程度, $\cos t_1 (\theta ^{\rm T}x^{(i)})$表示将样本分类为1 (正例)的代价, $\cos t_0 (\theta ^{\rm T}x^{(i)})$表示将样本分类为0 (负例)的代价.由式(2)得到取得最小代价的权重向量$\theta $, 则可根据式(1)中的计算方法得到未知样本所属类别.

2.2.3 分类器识别符号

本文采集了包括0$\sim $9、a$\sim $z、A$\sim $Z、+、$-$、=、/、*、$>$、$<$、根号、积分号、括号、分号等在内的102种公式符号, 对每个未知分类的符号提取其特征, 然后利用已构建的SVM多分类模型, 再根据特征向量计算得到该符号的所属分类.

2.3 结构分析及公式输出

在识别出单个字符后, 根据每个字符的位置信息, 确定该公式的骨干线, 其中在骨干线上的符号被视为关键符号, 而其他不在骨干线上的符号则利用递归方法在其所在区域确定子骨干线, 直至子区域内只包含单个符号.对于未在骨干线上的单个字符, 根据其前后骨干线上的字符确定其位置. 图 3中每一条贯穿公式符号的水平线即为公式的骨干线.

本文主要根据符号的位置信息确定公式结构, 具体步骤如下.

(1) 输入公式中各个符号的位置、大小信息.

(2) 遍历公式中的符号, 计算出一个完整公式的纵坐标中心位置, 即骨干线, 将在骨干线上的符号定义为关键符号.

(3) 对骨干线上符号进行分析, 分别针对几种特殊情况讨论, 如分式、根式、积分等, 对于分式, 以LaTeX格式先输出$\backslash $frac{}{}, 再分别对分子分母进行处理; 对于积分, 先输出$\backslash $int_{}^{}, 再分别对上标下标进行处理.

(4) 对于不在骨干线上且能够形成含有不少于一个符号的子公式, 循环(2)、(3)步骤, 直至子公式中仅有一个符号, 再根据该符号在骨干线之上或之下确定上下标关系.

3 实验评估 3.1 实验设置 3.1.1 数据集

实验使用的数据集为InftyCDB-1^[13]印刷体公式数据集, 该数据集包含30篇科技文献中含有的数学公式图片.本实验从该数据集中随机选择了28 764条样本, 按照训练集和测试集7:3的比例划分.

3.1.2 参数设置

实验使用的SVM模型默认参数如表 1所示.

3.1.3 比较方法

为了验证实验性能, 将该实验使用的SVM分类器与决策树^[14]、MLP (Multi-Layer Perceptron)神经网络^[15]分类器进行对比.利用决策树解决多分类问题时, 虽然易于理解和解释, 但存在过拟合问题, 且对于各类样本数量不一致的情况, 信息增益的结果偏向于具有更多数值的特征. MLP神经网络也是解决多分类问题的一个很好的方法, 但由于其网络的隐藏层神经元个数选取较难, 且容易得到局部最优解, 导致学习不充分.而SVM分类器方法能够将样本空间映射到一个高维乃至无穷维的特征空间中, 将问题转换为线性可分的, 这种方法对于本文实验的小样本训练集非常适用, 具有很好的泛化能力.后面的实验结果将给出验证.

3.1.4 度量指标

选择识别率、查准率、查全率和$F$1分数($F$1-score)作为度量标准来衡量方法的精度:识别率是指识别正确的符号个数占总符号数的比例; 查准率是指每一类识别正确的符号个数占识别为该类的符号总数的比例; 查全率是指每一类识别正确的符号个数占系统中该类总量的比例; $F$1-score是用来衡量查全率和查准率的指标.多分类问题中的查准率、查全率和$F$1-score都是通过构建混淆矩阵计算得出的.

3.2 实验结果

本文做了两组对比实验.第一组实验对比了使用原特征和改进特征时, 利用SVM分类器识别公式符号的效果, 实验结果如表 2所示.第二组实验对比决策树、MLP神经网络和OVO SVMs这3种分类器对同一数据集的符号识别效果, 实验结果如表 3所示.

从表 2可以看出, 改进的特征选择方法有效地提高了公式符号的效果.因为改进后, 选择每个子区域内黑色像素个数占总像素数的比例作为特征, 可以忽略符号大小对识别率的影响, 从而增强该方法的泛化能力, 得到较高的识别率、查准率、查全率和$F$1-score.

从表 3可以看出, 在相同的数据集上利用不同的分类器进行分类, OVO SVMs表现最佳.因为SVM分类器适用于小样本的分类问题, 本实验仅包含102个分类, SVM将样本空间映射到高维空间较为简单, 且因SVM具有泛化能力强的特点, 所以在本实验中表现最佳.而决策树算法在对那些各类别样本数量不一致的数据进行分类时, 会将样本数少的一类误分为样本数多的一类. MLP神经网络虽然可以达到较高的识别率, 但因其参数复杂, 不易于调整, 因此在该符号识别的小型网络中表现不是最佳.

4 总结

本文实现了一种基于SVM分类的数学公式识别方法, 在符号分割、特征提取方面做出了改进, 并使用泛化能力强的SVM方法对符号进行识别.首先利用投影和连通域方法分别对公式图片进行行分割和列分割, 对于被分成多个连通域的符号进行合并, 确保精确分割每个符号.再通过选择黑色像素点数占比和宽高比作为特征, 来忽略公式大小对识别率的影响, 提高识别公式的泛化能力.最后选择适合对小样本进行处理且泛化能力强的SVM分类器, 结果证明达到较高的识别率.同时, 提出了一种基于递归的公式结构分析方法, 不断将公式分解为子公式, 再根据公式符号位置确定各个子公式的骨干线, 通过骨干线确定其他上下标符号.本文方法能够有效地提高识别公式符号的准确性, 且支持多层嵌套公式的分析.

本文的识别方法对公式符号的识别率高达98.0%, 但在公式结构分析方面仍可进一步优化.一些情况下, 公式符号的表示含义以及结构与上下文符号有关, 因此, 如何将符号位置信息和上下文符号信息相结合, 做到在确定公式符号结构的基础上, 根据上下文符号判断该符号是否识别正确, 并对识别错误的符号进行修正, 将成为今后优化公式识别工作的研究重心.