基于压缩感知的手写汉字识别研究
2017-10-16张曼雪
张 军，张曼雪
(1.西安航空学院 士官学院，西安 710077；2.西安外国语大学 经济金融学院，西安 710128)
基于压缩感知的手写汉字识别研究
张 军1，张曼雪2
(1.西安航空学院 士官学院，西安 710077；2.西安外国语大学 经济金融学院，西安 710128)
基于压缩感知理论，提出一种手写汉字识别的算法。该算法首先对手写汉字图像进行随机采样得到其特征，然后对其进行稀疏表示，并最小化其l1范数得到样本的稀疏解，最后利用该稀疏解的系数判别测试样本的类别。
手写文字识别；压缩感知；稀疏表示；l1范数最小化数
0 引言
模式识别就是通过计算机用数学技术方法来研究模式的自动处理和判读，汉字识别是模式识别领域的一个重要分支。经过了几十年的发展，字符识别已经取得了很多显著的成果，如西文识别、用于邮政系统的识别系统等[1-2]。在汉字识别中，由于汉字类别多、结构复杂、相似字多、书写差异大[3]等原因，使手写汉字识别工作成为文字识别中的难点。虽然经过多年的研究，汉字识别已经有了许多成果，但是在实际应用中，提高汉字识别性能仍然是一个突出的问题。对于约束力较小的手写汉字识别，目前没有一种单一的实用方案能达到很高的识别精度与高准确度，当下研究人员正准备向更为实用、准确、错误率低的方向发展。一方面，尽量把新的知识运用到预判别及特点提取当中，如隐马尔可夫、神经网络、支持数学形态学、向量机等；另一方面，从多角度对手写汉字进行全面分析，亦是当前的研究热点。
近年来，在信息处理领域，稀疏线性计算问题即压缩感知理论(Compressive Sensing)引起了广大研究者的兴趣[4-5]。压缩感知理论在模式识别问题上也有应用，文献[6]利用稀疏理论有效地实现了人脸识别，但不是使用基础的超完备基，而是使用原始样本作为超完备基。因为假如每类样本素材足够多的话，原始样本可以线性组合为测试样本，这对于所有的样本资料来说，其表示方式必然是比较稀疏的，从而可以通过压缩感知的方法来实现采样。文献[7]同样利用这种方法，可以对手写数字进行有效的识别。本文基于上述思想，将压缩感知理论应用到更为困难的手写汉字识别领域。
1 压缩感知的基本理论
与传统的奈奎斯特采样定理不同，压缩感知理论认为，信号的采样速率并不仅仅取决于其带宽，与信号的内容也有很大的关系。只要信号在某个变换区域是稀疏的或者是可压缩的，那么就可以用一个独立的观测矩阵将变换所得信号投影到一个低维空间上，然后通过求解，进一步优化，从这些少量的投影中复现出原信号，可以证明这样的投影包含了重现信号的足够信息。
从上面压缩感知理论的基本描述可以看出，该理论有三个要点要解决：(1)稀疏的定义；(2)观测矩阵如何选取；(3)如何解决优化问题。
1.1 稀疏的基本慨念
从拉普拉斯变换、傅立叶变换、小波变换再到后来兴起的多参数几何分析，研究目的都是如何在不同的函数空间，为输入信号提供一种更加简洁、直接的分析方法，所有的变换都是在发掘原始信号的特征并稀疏表示，或者说都在提高非线性特性以便更好的逼近原始信号，进一步用函数空间的多重向量表示信号的稀疏程度。
稀疏的数学定义是：信号Y在正交基Ψ下的变换系数向量为Θ=ΨTY，假如对于0
(1)
则说明系数向量Θ在某种意义下是稀疏的。
稀疏的另外一种定义方法是：如果变换系数θi=〈x,ψi〉的支撑域{i：θi≠0}小于等于K，则可以说信号X是K2项稀疏。
压缩感知的基础和前提是找到最佳的稀疏域，所以这是研究的重要方向。
1.2 如何选择观测矩阵
Y=φΘ=ΦΨTX=ACSX
(2)
对于给定的Y，从式(2)中求出Θ是一个线性计算问题，但因为M<
1.3 解决信号重构问题
从少量的投影中以高概率重构出原信号，这就是信号重构的问题。在压缩感知理论中，由于观测数量M远小于信号长度N，因此不得不求解欠定方程组Y=ACSX。表面上看，欠定方程组求解似乎是无法完成，但是由于信号X是稀疏的或可压缩的，这个特性从根本上改变了信号重构问题，使得方程可解。
为更好地描述压缩感知理论的信号重构问题，首先定义向量X={X1,X2,…,Xn} 的p-范数为
(3)
当p=0时，得到0-范数，它实际上表示X中非零项的个数。于是，在信号X稀疏的前提下，求解方程组Y=ACSX的问题转化为确定最小0-范数问题
min‖ΨTX‖0s.t.ACSX=ΦΨTX=Y
(4)
但是0-范数问题是一个所谓的非确定性的问题，求解l1优化问题可以得到近似的解，从而使得该问题可解。
2 压缩感知在手写汉字识别中的应用[7]
手写汉字识别是确定当前输入的样本与训练样本之间的对应关系。我们假定系统的类别为K，每个类别对应的训练样本为N1，N2，…，Nk。对应于类别i，其特征矩阵Ai={vi1,vi2,…,viNi}，则对于属于i类的输入测试样本Y，有Y=k1·vi1+k2·vi2+…+kNi·viNi。所以在识别过程中，在类别未知的情况下，可以表述为Y=0·v11+…+0·vi-1,Ni-1+k1·vi1+k2·vi2+…+kNi·viN+0·vi+1,1+…+0·vK,Nk，ki,j∈R。
对于上面可以有如下的表达
Y=Ax
(5)
对于待分类样本Y，x为稀疏系数，x=(k11,k12,…,kK,Nk)T,A为观测矩阵，A=(A1,A2,…,AK)=(v11,v12,…,vK,Nk)。
为了用稀疏系数x来表达Y，需要解方程(5)。方程(5)中，A为M×N矩阵，其中N>>M，所以方程(5)是一个欠定方程组，有无穷组解。用最小l1范数来约束该问题，即
Y=Axs.t.x=argmin‖x‖1
(6)
在得到稀疏系数x后，用一个函数Ti(x)来计算用第i类恢复出来的Yi，Yi=ATi(x)，其中
Ti(x)={0,0,…,kil,ki2,…,kiNi0,…,0}
(7)
最后分类用最小残差来分类，即
minri(yi)=min‖y-AT(xi)‖
(8)
用压缩感知进行手写汉字识别的流程图如图1所示。
图1 算法流程图
3 实验及结果
为了验证算法的有效性，本文提出的方法在ETL9B手写汉字库上做了实验。ETL9B是由日本JAIST采集的，包含3036个类别，每个类别由200个人书写。图2是该数据库中的部分样本示意图。
图2 ETL9B样本示意
文章中的算法如下描述：首先对原始的文字图像进行采样，得到16×16 的图像，然后将其直接拉伸成一个多维的一维向量，再用实际样本组成观测矩阵A。识别过程中，用待识别样本在最小l1范数下计算稀疏系数x，利用公式(8)得到分类结果。
为了简化实验，所以只选了2965个汉字的200个类别用于实验，图2是测试样本的示意图，图3是稀疏系数示意图。实验结果是最近中心的识别率为97.2%，最近邻区域的识别率为98.9%，本文方法实验区域的识别率为99.1%。
可以看出，本文提出的方法可以有效的鉴别文字图像的类别信息，其中，最近中心(Nearest Mean)是用待分类样本与每个类别的中心点的欧式距离来判断样本的类别。
图3 稀疏系数示意图
4 结语
基于压缩感知理论的手写汉字识别，首先对手写汉字图像进行随机采样得到其特征；然后对其进行稀疏表示，并最小化其l1范数得到样本的稀疏解；最后利用该稀疏解的系数判别测试样本的类别。该方法的优势在于：一是利用对信号的随机采样替代了传统的特征提取方法，简化了算法的实现过程。二是用所有的训练样本组成训练字典，避免了复杂的训练过程。
在手写汉字数据库ETL9B上的实验结果表明了提出方法的有效性。在未来工作中，研究的重点将放在如何构建新的观测矩阵，以节省存储空间，提升计算效率。
[1] ARICA N,YARMAN-VURAL F T.An Overview of Character Recognition Focused on Off-line Handwriting[J].IEEE Transactions on Systems Man and Cybernetics Part C:Applications and Reviews,2011,31 (2):216-233.
[2] FUJISAWA H.Forty Years of Research in Character and Document Recognition-an Industrial Perspective[J].Pattern Recognition,2008,41(8):2435-2446.
[3] DAI R,LIU C,XIAO B.Chinese Character Recognition:History,Status and Prospects[J].Frontiers of Computer Science in China,2007,1(2):126-136.
[4] CAND E J,WAKIN M B.An Introduction to Compressive Sampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.
[5] ROMBERG J.Imaging via Compressive Sampling:Introduction to Compressive Sampling and Recovery via Convex Programming[J].IEEE Signal Processing Magazine,2008,25(2):14-20.
[6] 刘长红,杨扬,陈勇.基于压缩传感的手写字符识别方法[J].计算机应用,2009,29(8):2080-2082.
[7] 石光明，刘丹华，高大化，等. 压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1081.
[责任编辑、校对：东艳]
Abstract：A handwritten Chinese character recognition algorithm is presented on the basis of the compressive sensing theory.First of all,character images are sampled at random to form the feature vector,which is then expressed with sparse representation,and itsl1norm is minimized to obtain its sparse form.Finally,the coefficient of the sparse representation is adopted to judge the class of the samples.
Keywords：handwritten Chinese character recognition;compressive sensing;sparse representations;l1-minimization
HandwrittenCharacterRecognitionBasedonCompressiveSensing
ZHANGJun1,ZHANGMan-xue2
(1.School of Noncommissioned Officers,Xi′an Aeronautical University,Xi′an 710077,China; 2.School of Economics and Finance,Xi′an International Studies University,Xi′an 710128,China)
TP391.43
A
1008-9233(2017)05-0047-04
2017-05-11
陕西省教育厅专项科研计划项目(14JK1362)
张军(1968-)，男，陕西大荔人，副教授，主要从事工业电气自动化研究。
