SVM在小字符集手写体汉字识别中的应用研究
摘 要: 本文将支持向量机(SVM)引入到小字符集脱机手写体汉字识别中。文章首先介绍了SVM的基本原理和主要算法，然后在实验中采用了LibSVM训练软件，针对银行票据手写汉字的小字符集进行了仿真，同时与欧氏距离分类方法进行了比较。实验结果表明此方法的汉字识别率较高,在小字符集手写体识别中具有较强的实用性。
关键词： 支持向量机(SVM)；LibSVM；脱机手写体汉字识别
Small-set Off-line Handwritten Chinese Characters Recognition
Based on Support Vector Machine
Zhu Hui, Yang Yang, Xie Bin, Feng Jun
(Information
Eng.
School
, Univ.
of Science
and Technology Beijing
100083)
Abstract: This paper presents the application of SVM in small-set off-line handwritten Chinese characters recognition. The paper begins with basic introduction of SVM theories and algorithms. Then software LibSVM is pro
-posed for handwritten Chinese characters training of bank forms. The results are also compared with Euclidean Distance classifier, which indicates that the SVM strategy can improve recognition rate and therefore has more practicability.
Key words: Support Vector Machines (SVM); LibSVM; Off-line Handwritten Chinese Character Recognition
近年来，脱机手写体汉字识别这一模式识别领域中最棘手的问题，取得了大量的研究成果。但是,非特定人手写汉字识别仍然被认为是文字识别领域最困难的问题之一,其原因可以归结为:汉字规模大；相似汉字较多,且有些相似字差别极其细微；存在大量的不规则书写变形。由于后两个因素的存在,导致相似字在特征空间中的距离变小,使得普通距离分类器的推广能力变弱。因此,如何补偿手写汉字的书写变形,提高分类器的泛化和推广能力,就成为汉字识别研究的关键问题之一。
支持向量机（Support Vector Machines）简称SVM,是AT&T Bell实验室的V. Vapnik等人根据统计学习理论提出的一种新的机器学习方法,它已初步表现出很多优于已有方法的分类性能，在解决小样本学习、非线性以及高维模式识别等问题中表现出许多特有的优势。其基本思想可概括为:首先通过非线性变换将输入空间变换到一个高维空间,然后在这个新空间中求取最优线性分类面,而这种非线性变换是通过定义适当的内积函数实现的。根据结构风险最小化准则,在使训练样本分类误差极小化的前提下,尽量提高分类器的泛化推广能力。从实施的角度看,训练支持向量机等价于解一个线性约束的二次规划问题,使得分隔特征空间中两类模式点的两个超平面之间距离最大,而且它能保证得到的解为全局最优点,使得基于支持向量机的手写汉字分类器能够吸收手写的变形,从而具有较好的泛化和推广能力[1]。
1. 支持向量机(SVM）
1.1 单类问题
由于支持向量机（SVM）具有良好的泛化特性，因此可以用来进行向量估计，以包含大多数的相关图像，并使用规则剔除野值[2]。单类问题的命名缘自于在训练集和测试集中只使用正定样本。它的思想就是将数据规划到特征空间中，用最小半径的超球面包围最多的训练数据，特点是数据样本非常密集。主要应用于工程诊断的状态监测和医学诊断中判断是否正常等。具体算法详见文献[3]。
1.2 两类问题
SVM方法是从线性可分情况下的最优分类面提出的。首先考虑一个二维两类模式分类问题，设模式样本为
支持向量机就是要解决下列优化问题：
（1）
约束条件：
函数 把 规划到高维（或是无限维）空间中，SVM就是要解决在高维空间中寻找具有最大分隔空间的线性分离超平面的问题。其中 ， 是错分样本的惩罚因子， 是内积函数（又称核函数）[4][5]。
2. 针对汉字识别的多类问题
2.1 多类问题
汉字识别属于多类问题，识别方法较多，但就特征而言，主要可以分为两类：统计方法和结构方法。此外还有目前较流行神经网络方法。本文的小样本字符集的识别问题中，采用的则是SVM中的多类识别方法。目前多类SVM的方法主要有one-against-all, one-against-one, DAGSVM等[6]。
One Against All，有时也称为One Versus Rest。如果数据有 类，需要训练 个分类器。第 个分类器取第 类数据为正例，其余数据为负例。给定 个训练数据 ，第 类的约束条件为 ， 支持向量机解决下列问题：
,
（2）
函数 把训练数据 规划到一个高维的线性空间， 是惩罚因子。
最小化 实际上等价于最大化 ，即两组数据的最大间隔。当数据线性不可分时，惩罚因子 可以减少训练误差的数值。SVM的基本问题就是要在正则项 和训练误差之间寻找均衡值。
(2)式的问题解决后，还需要考虑下列 个决策函数
最后归为有最大决策值的类。
（3）
在实际问题中解决的是跟（2）式有相同变量值的对偶问题。这样， 个 变量的二次规划问题得以解决。
One Versus One，也称One Against One，在本文的分类识别中用的是这种方法。算法思想如下：如果有 类数据，选取第 类数据和第 类数据构造一个分类器，其中 （一般设 为正例， 为负例），这样需要训练 个分类器。对于第 和第 类数据，需要解决下列的两分类问题：
（4）
用投票法解决上述问题，若 判断 属于第 类，第 类的票数加1；反之，第 类票数加1。 最后归为拥有最多票数的类。这种投票法称为“Max Wins”法。但如果两类具有同样的票数，该方法就不太适用了，这时可以选择索引值较小的类。
在实际问题中，通常解（4）式的对偶问题，因为它的变量个数和两类的数据个数相同。若平均每类有 个数据点，可以解决 个二次规划问题，其中每个有大约 个变量。
2.2 核函数的选择
常用的核函数有以下四种：
线性函数：
多项式函数：
径向基函数（RBF）:
Sigmoid函数：
其中 是核参数。
本文将RBF函数作为核函数的首选，原因主要有以下几点：
首先，RBF函数可以将样本非线性地规划到更高维的空间中，从而解决类标签和属性间非线性的关系问题，这是线性核函数无法解决的。进一步而言，线性核函数是RBF核函数的特例（可从线性函数的惩罚因子 和RBF核函数的 性能的相关性得到）。另外，Sigmoid核函数取某些特定参数时性能和RBF相同。
其次，超参数的数目影响模型选择的复杂性。多项式核函数数目比RBF核函数多，因此其模型选择更为复杂。
最后，RBF函数的数值限制条件少。由于 被限制在0和1之间，而多项式核函数的值可能会趋于不定值 或零值 且幂值更高；Sigmoid核函数在取某些参数值时则可能无效。
3. 实验方法和结果分析
3.1 样本选择
本文选用的试验数据为银行票据手写体输入,分别为大写汉字包括零、壹、贰、叁、肆、伍、陆、柒、捌、玖、拾、亿、佰、仟、万、圆、元、角、分、整、正、共21个。这21种汉字先经过模型匹配、二值化、细化、去噪等预处理。特征提取方法采用基于点密度的弹性网格方向特征作为支持向量机的输入样本。汉字图像经二值化和归一化后,根据汉字图像的黑象素点的密度分布划分一定大小的弹性网格。然后,汉字图像经过细化,根据8邻域象素点分布情况,把每个黑象素点分解到横、竖、撇、捺四种方向子模式。最后,根据四种方向子模式的每个弹性网格中的笔划象素点的分布情况计算网格方向特征。对于8×8的网格,则特征维数降为256。
3.2 仿真及结果
SVM算法采用的是训练软件LibSVM [5], 在多类识别中采用one-versus-one方法。LibSVM是由Chih-Chung Chang 和 Chih-Jen Lin开发的一个SVM工具，广泛用于SVM、回归、和分类估计，并且支持多类分类；它的基本算法结合了Platt 提出 的SMO和Joachims提出的SVMLight算法思想。
（1） 实验步骤如下：
a. 将数据转换成SVM软件要求的格式
b. 对数据按比率缩放（归一化）
c. 先用RBF核函数
d. 使用交叉确认法找到最佳的参数
e. 用 和 训练整个训练集
f. 试验
（2）绝对特征
在SVM中，要求用一个实数向量代表一个数据实例，所以要把绝对特征转换成数值。用 个数代表 个类的特征，其中的某一个类用1表示，其他类用0表示。例如，一个3类特征{红，绿，蓝}可写成（0，0，1），（0，1，0），（1，0，0）。
（3）缩放
对于训练数据和测试数据使用同样的缩放比率，都按比率缩至[-1, +1] 或 [0, 1]范围内。
（4）模型选择
先决定选择哪一个核函数进行尝试，然后可定出 和其他核参数。建议将RBF 核函数作为首选。
（5）交叉确认
交叉确认的基本思想为：把已有样本集分为两个子集，用其中一组（训练集）来训练分类器，另一组（检验集）用于检验（即估计训练好的分类器的泛化错误），然后根据检验结果来评估分类器的性能，并调整分类器的相关参数，之后再进行同上的训练与调整过程。当泛化错误达到理想值时，则得到的分类器为目标分类器 [4][8]。
3.3 结果分析
实验系统中,待识别的汉字有21种,每种汉字收集了100个不同的书写样本,共有样本数目为2100。其中1890(21×90)个样本集进行训练,其余210(21×10)个样本集用于输入测试。部分训练样本如图1所示。
图1 部分训练样本
图2 银行票据样本(1)
图2为某银行票据样本原图，被用作测试样本。首先用图像匹配的方法进行预处理，去除页面原有的印刷体部分，得到的结果如图3所示。
图3 处理后的结果
图4 银行票据样本(2)
图4是另一个测试样本，首先要经过图像预处理以去除图中的横线。对图3、图4预处理完后的图像进行识别，都得到了正确的识别结果。表1列出了将SVM方法和欧氏距离分类方法比较得到的结果，可以看出，在小样本情况下，SVM方法较之欧氏距离法有较高的识别率。
表1 SVM实验结果和欧氏距离分类方法比较
分类方法
识别率(%)
误识率(%)
SVM
90.6
1.1
欧式距离
80.2
2.6
4. 结论
本文分类讨论了SVM在单类、两类和多类问题中的应用，并把针对多类问题的SVM分类器引入到小字符集脱机手写体汉字识别中。实验中使用LibSVM训练软件进行了仿真，并和欧氏距离分类方法进行了比较。其结果表明，SVM方法的引入可以较大程度的提高识别率，是一条可行且高效的途径。此外，根据不同的应用环境，再采取多分类器集成的方式和相应的前、后处理方法，可得到更满意的效果。
参考文献：
[1] 高学,金连文,尹俊勋,黄建成.一种基于支持向量机的手写汉字识别方法[J]. 电子学报, May 2002, 30(5)
[2] B. Scholkopf, J. C. Platt, J. T. Shawe, A. J. Smola, R. C.Williamson,
“Estimation the support of a high-dimensional Distribution”, Technical Report MSR-TR-99-87, Microsoft Research
[3] Yunqiang Chen, Xiang Zhou, and Thomas S. Huang,“one-class SVM for learning in image retrieval”,In Proc. IEEE Int'l Conf. on Image Processing 2001, Thessaloniki, Greece
[4] 边肇祺,张学工等.模式识别[M].清华大学出版社,2001.5
[5] Chih-Chung Chang and Chih-Jen Lin, LIBSVM : a library for support vector machines, 2001
[6] C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines , IEEE Transactions on Neural Networks, 13(2002), 415-425.
[7] Richard O. Duda, Peter E. Hart and David G. Stork， "Pattern Classification ( 2nd ed. )", Wiley Interscience, 2000.
