一种多模型超图用于手写汉字识别算法

魏炳辉 谢晖慧 邓小鸿

(江西理工大学应用科学学院 江西 赣州 341000)

0 引 言

随着社会经济的快速发展，商业银行每天需要处理、保存的票据数量在迅速增长。票据的处理程序包括人工录入、核验及存档等繁琐的过程，这给银行工作人员带来了沉重的负担。面对银行票据如此严格又繁琐的处理程序，人工处理的方式工作效率低下，不但满足不了日益增长的处理需求，而且容易出现人为错误，给银行带来不必要的经济损失。为了解决上述问题，提高银行业的自动化技术水平，票据自动处理技术的设计很快成为相关领域研究的重要课题。其中手写汉字识别是最重要的一个难关。票据上的手写汉字因其存在形式复杂多样，致其识别率不高，难以达到商用化标准。因而票据手写汉字识别技术的研究成果对商业银行系统的运作有很大的实用和参考价值，同时取得的研究成果也将对图像处理、模式识别、人工智能等多个学科的发展起到一定的推动作用，具有重要的实用价值和理论意义。

国外对手写字符识别的研究比较早，目前已有许多实用化的产品[1-2]，一个完整的手写字符识别系统的研究内容主要涉及字符分割、特征提取、字符识别，目前字符分割算法已达到商用化程度，以后研究的重点在于特征提取与字符识别。国内外在字符串分割与识别等处理技术方面都取得了重大进展[3-4]。对于字符目标提取，目前的大多数方法是通过对字符对象的亮度或笔画特征建模来提取字符目标。典型的方法有Ye等[5]采用一种综合亮度特征和局部几何特征的字符笔画双边缘模型，用于复杂背景中字符对象的提取，该笔画模型融合笔画宽度约束与笔画亮度信息，能有效地解决背景突变带来的问题。季婧婧等[6]利用二次分割的方法滤除票据上的彩色印章以提高文本内容的识别率。但这些成果都只在于数字与字母等结构相对简单的字符识别研究，而手写汉字方面识别正确率仍然不高。

造成这种情况的原因，是我国手写汉字结构复杂，形体丰富多样导致手写汉字识别率达不到商用化标准。近年来研究较多的是手写汉字块的特征提取算法研究。根据不同的规则及分类，识别方法大体可分为三类：模板匹配法、统计模式识别方法以及结构模式识别方法。这些方法主要是基于人工神经网络、支持向量机、隐马尔可夫模型和最近邻匹配等方法的推广或几种方法的集成[7-8]。根据系统的实际需要，采用多种信息源、多种特征提取以及多识别器结合等多项预处理技术[9-10]，来提高识别系统的性能。文献[10]利用深度学习的方法识别手写汉字正确识别率已经达到96.13%，是目前公布的最好结果。然而该研究所用的手写汉字都是相对规范的、笔画比较清楚的，另外深度学习模型需要大量的训练样本，训练时间较长，但在现实中难以满足这些条件。不同的人手写汉字存在很多复杂的情况，如字符粘连、连笔现象、位置高低不一、大小不一等，提取单个的手写汉字，再进行识别的效果受前述影响较大，难以达到商用化标准。在银行票据手写汉字识别需求中，存在训练样本少和实时性要求高的特点。

本文利用多模型超图学习理论，对比较固定的文本块学习其归属标志。其出发点有两个：一是超图学习方法适合小样本学习，在训练样本较少的情况下可以获得较好的分类性能；二是票据上有些文本块的内容比较固定，利用超图学习识别速度较快。超图学习模型在公开的一些标准数据集上已经体现出一定的优势，而在手写汉字识别上还鲜有报道。

1 算法设计

基于超图的学习模型是一种非常重要的直推式半监督学习方法，在已有的直推式半监督学习算法中，超图学习方法能获得较好的性能[11-12]。超图学习目标是找到样本间的高层相关性，在超图构建时，超边的权值需要依据一定的法则来确定。为了挖掘手写汉字间的多重相关性，在普通超图的模型中融入稀疏表示与成对约束理论，以及该结合模型的最优解论证方法。下面先介绍构建普通超图，再以手写文本块特征向量的解稀疏表示系数建立稀疏超图与标记样本的成对约束模型，最后融合这几个模型求解最优解。

1.1 构建普通超图

构建普通超图时，超边选取有多种方法，对于给定样本，一种办法是距离其最近的若干样本所组成的集合为一条超边；第二种办法是指定一个阈值，与该样本的距离值小于设定阈值的样本集合为超边。本文选取前者构建超图学习模型。

设定图G=(X,E)，所有样本x构成样本集X，和所有的超边e集合构成边集E，每一条超边包含了若干个样本，边的权重是该边中所有样本间的距离平均值。设定矩阵Dv、De和W对角线元素分别表示相应样本所在的边数、超边中样本的个数和超边的权值，设定邻接阵H，矩阵元素表示两样本间的连接关系。根据文献[12]，得到目标函数如下：

(1)

1.2 构建稀疏超图

(2)

式中：w=[w1,w2,…,wd]T。x和w表示同一个数据点,前一个是基于空间域，另一个是基于Σ域。我们的目标是求解出基于Σ的稀疏系数,即w包含尽量少的非零元素。根据文献[14-15],这个稀疏解可以通过以下目标函数式求解得到：

(3)

假定数据集是采样于一个包含k个独立子空间的统一空间里，相当于这个数据集包含k类，该目标函数可以获得块稀疏解，每一块中的非零元素对应一个子空间(关于块稀疏求解方法请参阅文献[14])。相近的样本稀疏表示也相近，可以被同子空间中相近的点线性表示，稀疏系数对应着样本间的相关性或权值。

根据求解后的稀疏表示，构建稀疏超图，样本相应的稀疏表示参数如果是非零值，表示两样本间相关，该参数表示相关性的紧密程度，邻接关系阵A为：

(4)

式中：|(wi)j|表示wi的第j个元素的绝对值。设定Ls=I-Dv-(1/2)AWDe-1ATDv-(1/2)为基于稀疏表示的拉普拉斯矩阵，稀疏超图的正则表达式为:

minfLsfT

(5)

1.3 样本成对约束

近年来，成对约束[16-17]在半监督学习领域引起了广泛关注。成对约束包含两个约束：必须连接约束和不能连接约束。利用训练样本的标记信息，必须连接约束表示，标记信息相同的样本或者说同类样本通过学习后，其类别信念必须相近；而不能连接约束规定不同类的样本通过学习后，其类别信念相距越远越好。这里结合这两个约束进超图学习模型中以增强学习能力。

设定fi为xi的学习之后类别信念,C+表示与xi同类的样本集，C-表示与xi不同类的样本集,必须连接约束可以表示为:

(6)

和不能连接约束表示为：

(7)

结合这两个约束为成对约束，表示为：

minfLpfT

(8)

1.4 融合稀疏表示与成对约束理论的超图学习

在普通超图中融入稀疏表示与成对约束理论成为一种新的结合学习算法，本文称之为多模型超图学习模型(CSP)，目标函数为：

(9)

(10)

式中：r>1。为解决这个目标函数，我们利用一种迭代求解的方法[18]，先初始化β=[1/3,1/3,1/3],固定β利用拉葛日乘法更新f：

(11)

然后固定f，最小化表达式(11)，可以计算出β为：

(12)

这个学习模型通过两到三次迭代后收敛。表1给出了算法流程。

表1 算法流程

2 实 验

本文收集68个志愿者同时写64遍“华为技术有限公司”和“网络基础”的文本块图像，图1为四个志愿者手写汉字图像。本文利用8重交叉验证方法，即在每一次实验中，把所有标记数据与非标记数据分别分成8等份，选取其中1份作为训练样本集，剩下的7份为测试样本集。然后重复8次，每一个样本都有机会成为训练样本，取均值作为性能评估。

图1 手写汉字示例

实验首先对每个文本块进行特征分析[19-20]。志愿者在写文字时没有限定写法，对字体、字号、粗细、字间距、高低等不作要求，完全按照其真实的写法。结构特征包含质心特征、笔画特征、笔画特征点、几何特征。质心特征(2D)是文本笔画分布的体现，将二值图像转化成点阵形式，再依据质心计算公式求出水平质心与垂直质心。笔画特征(4D)由横、竖、撇、捺四种基本笔画构成，对单字分别提取这四种基本笔画，统计出各自的数量。笔画特征点(4D)主要有端点、折点、歧点与交点，端点是笔画的起点或终点，折点是笔画方向出现显著变化的点，歧点是三叉点，交点是四叉点。按序对二值图像进行扫描，统计出各笔画特征点的个数。几何特征(1D)是计算包含文本块的最小矩形的长宽比值。统计特征包含方向特征、网格特征、Gabor特征等。方向特征(1D)是文本块的方向角度。网格特征(30D)是把包含文本块的最小矩形平均分成若干行若干列，每个单元格中文字像素点的个数统计，本文实验时分成3行10列共30个单元格。Gabor特征(30D)是在网格基础上计算Gabor变换后的对应能量表示。最后组合这些多种特征为文本块的72维的特征向量。

为检测所提出的算法，我们在实验中对比以下几种方法：k-近邻分类器(KNN)确定某点中最近邻的k个点中，相同标记最多的标记指定给此点，简单易实现，本文把KNN当作基本的方法用来比较；半监督区分性分析(SDA)算法[21]通过求解一个关于训练数据区分结构的映射，利用训练数据，包含未标记数据，构建一个目标函数，这个目标函数加入了由局部几何流形的离散估计得出的拉普拉斯图，这样能保持数据内部的流形结构；自适应超图学习算法(AHL)[22]选取多个领域作为超边集，然后迭代学习每边的权值，以此来更新样本的类别信念c；本文提出的结合稀疏表示和成对约束理论成为一种新的超图学习框架(CSP)。

图2所示为两类手写汉字的四个分类算法的正确率及误差，可以看出本文提出的算法CSP在正确识别率上表现最好，与AHL比较接近。但在误差方面，CSP表现较之于AHL的波动较大，说明CSP受噪声影响较大。而SDA算法表现较为稳定，在两类数据集上的正确识别率相差较小，每次实验间的误差更小。KNN只考虑样本特征间的距离相似性而表现一般，并且受噪声影响最大。综合这四类算法表现都不高，主要是志愿者在连续写字时，会随着心情的变化而有所改变。刚开始时写的字比较规范，到后面是越来越潦草，多笔画少笔画都有可能出现。如图3所示两位志愿者写的“网络基础”，是错判率最高的两类样本。可以看出，字形与笔画都有变化，出现连笔现象较多，致使作出错误的判断。

图2 两类手写汉字块的四个分类算法识别率

图3 错判率较高的两位志愿者手写汉字示例

3 结 语

本文为提高手写汉字的识别率，考虑样本间更多层的关系，融合稀疏表示与成对约束理论成为一个新的超图学习模型。通过加入稀疏表示，更好地表现同类样本间的相关性。通过增加成对约束，对有标记样本的类别属性进行更有力的约束，加强同类样本间未标记样本的样本类别属性传递。在两类手写汉字数据集上的实验表明，本文提出的新超图学习模型有一定效果，但在现实中由于手写体易受外在因素与手写者的主观因素的影响，总体识别率还较低，需要进一步的研究提高。