基于决策导向非循环图支持向量机的脱机手写体汉字识别

吴仕莲 杨杰 赵冬琴

摘要：目前脱机手写体汉字识别在小字符集方面取到了比较好的效果，但在大字符集方面仍存在着识别速度慢、准确率低等问题。不同于传统的二叉树方法，本文将决策导向非循环图用于汉字识别，并加以改进。仿真实验表明，该算法能对大字符集的手写体汉字进行识别，有效减小了误差，具有较高的识别率。

关键词：支持向量机 多分类 脱机手写体汉字 决策导向非循环图

中图分类号：TP391.4 文献标识码：A 文章编号：1007-9416（2016）07-0041-02

Abstract：Currently，off-line handwritten Chinese characters recognition in the small category character recognition has obtained good effect. However，recognition in large character set still has the weakness of low efficiency and low accuracy.This paper presented an improved SVM-based algorithm of Decision Direct Acyclic Graph（ DDAG）. Simulation results demonstrate that the algorithm can recognize large character set of handwritten Chinese character and has high recognition performance.

Key Words：SVM；multi-classification；Handwritten Chinese Characters；DDAG

字符识别技术已经发展了几十年，对英文来说，识别技术已经足够成熟了[1]。而中文却存在汉字字符集字量过大的问题，使得多分类问题愈加困难，对汉字的识别研究也集中于小字符集方面。传统的识别技术如神经网络、决策树等识别方法也存在识别速度慢、识别率不高等问题[2]。而SVM在识别手写体汉字上具有识别率高、识别速度快的优点[3]。针对SVM中常用的多分类方法存在的识别速度慢、误差大的问题，文章提出一种将决策导向非循环图用于汉字识别并加以改进的算法，并成功应用于大字符集的汉字识别方面。

1 支持向量机

1.1 SVM分类器

支持向量机（ Support Vector Machine，SVM）这一概念是Vapnik等人在20世纪90年代中期首次提出的。它在泛化能力和有限个训练样本的学习精度间取得了很好的平衡，由此获得了较好的推广能力。支持向量机 灵活地根植于凸优化理论，因此具有良好的最优化性。同时，SVM建立于结构风险最小化准则上，从而使得支持向量机分类器具有较好的推广能力 ，已得到了广泛的应用。SVM起初对线性可分情况进行分析，而对于汉字识别的非线性分类问题，用核函数将特征向量从低维空间映射到高维空间，使低维空间的非线性分类问题转换为高维空间的线性分类问题，在高维空间采用线性分类算法对汉字的非线性特征进行分析。在二分类问题中，给定样本

，，则svm的判决函数就是下式

（1）

其中是（2）式约束问题的最优解

（2）

（3）

（4）

其中为拉格朗日乘子，C为惩罚因子，b是分类阈值，b的计算公式如下

（5）

K为核函数，定义了一个从低维空间到高维空间的映射，是一种计算映射到高维空间之后内积的一种简便方法。主要有

（1）线性内核：

（2）径向基内核（RBF）：

（3）多项式内核：

（4）sigmoid核：

本文采用的应用最广的RBF核函数，在手写体识别领域也取得了较好的效果。SVM的计算机实现则采用smo的改进算法。

1.2 多分类问题

SVM本来是针对二分类问题提出来的，而汉字识别却是多分类问题，所以要构造多类分类器，目前主要是通过多个二分类器组合实现多类分类的功能。常见方法有one-against-one、one-against-rest两种。

（1）一对其他法（one-against-rest）：即在训练时依次把某个类别的样本归为一类，其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个二分类器。分类时比较的值，将最大值对应类别赋给待分类样本。

（2）一对一法（one-against-one）：在任意两类样本之间设计一个二分类器，即k个类别的样本就需要设计k（k-1）/2个二分类器。当对一个待识别样本进行分类时，用所有的二分类器对样本进行“投票”，该待分类样本的类别就是最后得票最多的类别。一对一分类方法简单有效，并且训练时间较短，适合大字符集的汉字识别这样的大规模数据。因此本文选择一对一法训练二分类器。

2 决策导向非循环图

2.1 决策导向非循环图基本原理

决策导向非循环图DDAG（Decision Direct Acyclic Graph），对于n类分类问题，DDAG采用一对一（one against one）的方法训练分类器，即得到n（n-1）/2个二分类器。为了解决k类分类问题，首先需要训练k（k-1）/2个分类器，然后DDAG识别需经过下列步骤

（1）生成类别系列，，并且定义i与j，初始化分别指向序列的开头与结尾

（2）对于待识别样本x，用二类分类器进行分类，其中表示由和类训练样本训练而成的二分类器。

（3）如果类，则令；如果，则令。再回到②，直到，此时i指向的类别即为待分类样本x的类别。

结果如图1所示。

可以看出，DDAG采用了1-v-1的多类SVM基本结构[8]。对于一个N类问题的分类过程，DDAG为了对某待测样本进行分类，只需要构造n-1个决策点，相对其他方法而言速度更快，并且准确度更高，不存在误分、拒分。

2.2 基于改进DDAG的支持向量机

传统支持向量机采用一对一或者一对其它方法设计多分类器时，会存在误分、拒分区域。而层次结构固有的弊端就是自上而下的误差累积，DDAG也不能避免。从图1中可以看出误差从根节点向下逐渐累积，并且越靠近根节点的分类性能对整个分类模型的影响越大。因此在生成DDAG的过程中，应该让更容易分离的两类更早分离出来。而传统DDAG随机生成类别序列，并没有刻意早分离容易分离的两类。为了减少累积误差，提高识别率，应将容易分离的两类分别放置在类别序列的两端，即在汉字识别过程中，应该将形近字训练成的二分类器放在叶子节点处，字形差别大的汉字训练成的二分类器放在上层节点。令p，q分别表示第p类和第q类汉字，在DDAG的第①步产生类别系列时，设，，对于形近字，应尽可能使i=j+1；对于字形差别比较大的汉字，则应尽可能使i+j=k+1。这样在识别过程中，从根节点到叶子节点的过程中，都是先分类差别大的2类，大大减少了上层节点的累积误差。

但在具体的计算机实现中，形近字的划分却很困难。采用聚类的方法无疑会很大程度上增加计算量，并且也不能很好的区分汉字的字形差异程度。而汉字的UTF-8编码是按照拼音排列的，即音近字的编码是相邻的。一般而言，很多形近字也是音近的，所以很大程度上可以用UTF-8编码来代表汉字的字形，即认为编码相邻的汉字是形近字，编码差别越大，字形差别越大。这样在生成类别序列时，只需要按照编码逐个填入对应的汉字类别即可。对于n个汉字的分类，具体算法流程如下：

Step1：采用一对一的方法来训练分类器，得到n（n-1）/2个二分类器；

Step2：根据UTF-8编码从前往后依次给汉字标注为第1类，第2类...第i类...第n类；

Step3：生成类别系列时，令；

Step4：对于待识别样本x，用二类分类器进行分类，其中表示由和类训练样本训练而成的二分类器；

Step5：如果类，则令；如果，则令。再回到②，直到；

Step6：根据查找对应的UTF-8编码，并根据编码确定并输出对应的汉字。

3 仿真实验及分析

在识别之前对获取文字图像进行预处理，具体流程如下：

3.1 二值化处理

即先将24位真彩色图像转化为8位灰度图像，然后使用otsu方法进行最佳全局阈值处理得到二值图像。

3.2 图像分割及特征提取

在分割之前之前获得的二值图像采用中值滤波方法做平滑去噪，然后使用投影方法分割出每个字符。有如下几种常用的特征： （1）灰度或颜色的统计特征；（2）纹理与边缘特征；（3）图像的代数特征；（4）图像变换系数特征。而本文采用一种较为便捷的特征提取方法，将文本图像归一化为32*16大小的图像；然后将图像网格化，划分成3*3网格，分别统计每个网格中黑色像素点的个数，这组成特征向量的前9维，然后统计两条横分割线和两条纵分割线上黑色像素点的个数，组成整个13维的特征向量。

实验根据UTF-8编码选取常用的3729个汉字，每个汉字取40个训练样本，10个测试样本，核函数选择径向基函数，惩罚因子C为1.2，松弛变量为0.001，识别结果如表1所示。

从表1可以看出，DDAG在大字符集手写体汉字的识别中具有较高的识别率，同时改进后的DDAG也减少了累积误差，提高了识别率。仿真实验表明，该算法能对大字符集的手写体汉字进行识别，很大程度上减少了累积误差，具有较高的识别率。

参考文献

[1]In-Jung Kim and Xiaohui. Handwritten Hangul recognition using deep convolutional neural networks.Springer Berlin Heidelberg，2015.

[2]李琼，陈利，王维虎，基于 SVM 的手写体数字快速识别方法研究[J].计算机技术与发展，2014，（02）.

[3]张芳，汪成军.基于支持向量机的手写体汉字的识别[J].计算机与数字工程，2006，（01）.

[4]朱程辉，项思俊.手写体汉字识别的二叉树 SVM算法研究[J].智能、算法、系统工程，2009，（09）.

[5]Keerithi SS，Shevade SK，Bhattacharyya C， et al. Improvements to Platt' s SMO Algorithm for SVM Classifier Design[ J] .Neural Computation， 2001，13（ 3）： 637～ 649.

[6]秦朗.基于二叉树多层分类SVM的脱机手写体汉字识别方法研究[D].合肥：合肥工业大学，2010.

[7]刘勇，全廷伟.基于 DAG-SVMS 的 SVM 多类分类方法[J].统计与决策，2007，248（20）：14-148.

[8]李昆仑.一种基于有向无环图的多类SVM分类器[J].模式识别与人工智能，2003，（02）.

[9]汪政，邵良杉.多类支持向量机分类算法—DDAG[J].研究开发，2010，（07）.

[10]翟俊海，赵文秀，王熙照.图像特征提取研究[J].河北大学学报，2009，（01）.