一种新的基于Grassmann流形度量的手写体数字识别方法

王卫华 王长杰 张伟

摘 要： 针对现有手写数字识别难以处理几何变换下的识别难题，提出一种新的基于Grassmann流形度量的手写体数字识别方法。在分析不同几何变换下的手写数字字符所构成的非线性流形空间结构基础上，定义了Grassmann流形及其距离度量，并通过计算待识别数字字符与训练字符集合构成的Grassmann流形距离实现手写数字字符的分类识别。通过在MNIST数据库上的实验，证明该算法具有较好的实时性和鲁棒性，在对数字的识别率、稳定性、计算效率上显著优于现有基于切距离的手写数字识别算法，在识别率、稳定性上较现有基于欧氏距离的算法有较大的提高。

关键词： 手写字符识别； Grassmann流形； 几何变换； 最近邻分类

中图分类号： TN911.73?34； TP391 文献标识码： A 文章编号： 1004?373X（2016）09?0066?04

Abstract： Since it is hard for the existing recognition method to recognize and handle the handwritten numbers in geometric transform， a new handwritten numeral recognition method based on Grassmann manifold measurement is proposed. On the basis of the analysis of the nonlinear manifold space structures composed of handwritten numeral characters in different geometric transforms， the Grassmann manifold and its distance measurement are defined. The waited recognition numeral characters are calculated and Grassmann manifold distance composed of character set is trained to realize the classification and recognition of the handwritten numeral characters. The results of experiment with MNIST database show that the proposed algorithm has better real?time performance and robustness， and is superior to the available handwritten numeral recognition algorithm based on tangent distance in the aspects of numeral recognition rate， stability and computing efficiency， and the recognition rate and stability of the proposed algorithm are better than those of the algorithm based on Euclidean distance.

Keywords： handwritten character recognition； Grassmann manifold； geometric transform； nearest neighbor classification

0 引 言

随着数字图像技术的快速进步，手写数字识别技术（Handwritten Numeral Recognition）也被广泛地应用于财务、金融等许多领域，其有着重要的理论和应用价值[1?3]。虽然识别技术在脱机手写英文、汉字方面中已取得一些成绩，但距实际应用还存在一定的距离。一些电子数据信息主要由数字字符和特殊符号组成，如邮政编码、银行数据等，在识别效能上主要取决于输入数据的类型。如果能研发出一个高效的手写体数字识别系统将有助于提高人工处理信息的录入效率，因此手写体数字识别具有较高的实用价值。

根据手写数字识别方法不同，目前常用的方法有：模板匹配法、统计决策法和模糊判别法[4]等。这些方法都有自身的优点也有自身无法克服的缺陷，识别率和实时性已经很难突破。识别率难以提高的原因在于不同的手写数字之间的差异较大，存在着几何、粗细等变化，并且在实际的应用过程中，对数字的识别正确率比文字的识别正确率要求更加严格；实时性难以提高的原因在于目前数字识别系统面对的往往是大批量数据处理。因此，研究出一个高性能识别率的手写体数字识别算法任务艰巨。

最新研究表明人类的视觉感知以流形方式存在，视觉记忆可能以稳态的流形存储[5]。切距离方法是流形方法的切平面近似，通过计算测试样本图像到流形切平面之间的欧氏距离进行图像分类，切距离方法已在字符中取得了广泛应用，并取得了较好的结果[6?7]。切距离本质上是一种可变形模板匹配，用变化空间在模板处的切平面对变化空间进行近似，具有对几何变换保持不变的性质。然而切距离只能线性近似非线性流形，仅对较小范围的图像变换具有度量不变性，仍然是一种线性方法，易陷入局部最优。

流形学习是近年来兴起的非线性降维方法[8?19]，2000年，Seung和Daniel从神经心理学的角度探讨了人类的感知方式，认为人的感知可能以流形方式存在[5]，初步给出了流形学习的生物学认知基础。另外两篇文章分别从算法实现的角度提出了两种经典的流形学习算法Isomap[17]和LLE[18]。随后不断有新的流形学习算法提出[19]。

Grassmann流形在信号处理和控制领域、最优化算法[8]、不变子空间计算[9]中有着重要应用，近年来开始逐步应用于计算机视觉和模式识别领域[10?12]。其研究内容包括通信信道中的最优预测和编码问题[13]、宇航飞机外形设计中的流形插值运算[14]以及运动分割问题中涉及到的流形聚类[15]等。最近，一些学者提出了基于Grassmann流形的人脸识别方法[16]，在不同光照和几何变化下较传统识别方法取得了显著的实验结果。

受Grassmann流形距离在人脸识别中的研究启发，本文提出了一种新的基于Grassmann流形度量的手写数字识别方法，实验结果表明，所提出算法在识别精度、稳定性、计算效率上显著优于现有基于切距离的手写字符识别算法，识别精度、稳定性较现有基于欧氏距离的算法有明显提高。

1 Grassmann流形距离

针对切距离方法的不足，本文研究了Grassmann流形距离（GD），并将其应用于手写体字符识别中。Grassmann流形理论是本文手写体字符识别的理论基础，与此相关的微分几何和黎曼流形的详细内容见文献[8]。

如图1所示， 对于[k]幅分辨率为[n]的数字字符图像，每幅图像用列向量存储，[k]幅图像构成数据矩阵[X，]用列空间表示为[R（X），]若[R（X）]的秩为[k，]则[R（X）]为[n]维向量空间的[k]维子空间，记作Grassmann流形[Gk，n]。定义如下：

3 实验与分析

为了证实所提出算法的有效性和鲁棒性，将基于Grassmann流形距离（GD）的手写数字识别算法同基于欧氏距离（ED）和基于切距离（TD）的两种算法进行数据对比分析，所有对比的距离度量方法都直接用于最近邻分类器实现手写数字识别。算法用Matlab语言实现，在处理器为Pentium Dual?core 2.5 GHz、内存为2 GB的微机上完成。实验数据采用NEC研究中心的MNIST手写数字数据库（见图3），许多实验研究基于此库[20] ，里面包含了60 000个训练样本和10 000个测试样本，每个样本为分辨率为28×28像素的bmp图片。本文实验中切距离算法和Grassmann流形距离算法构建训练字符集的旋转参数范围[θ]=±20°，缩放参数范围在[α1]=1.1和[α2]=0.9之间，平移参数[β]=±5之间，[γ]=±5之间。每个参数在参数变化范围内均匀取值10个。

3.1 计算复杂度分析

若每幅图像的分辨率为[m×n，]对于欧氏距离算法，不需要离线计算，只要在每个待测试样本与标准字符之间计算欧氏距离即可。对于切距离算法，离线过程，对每个训练字符进行几何变换（有[k]个变换），并求解切向量需要[10mnk]次计算；在线过程计算测试字符的几何变换和切向量同样需要[10mnk]次计算，计算训练字符与测试字符之间的切距离需要[6k3+2mnk2+4mnk+2mn]次计算。对于本文提出的算法，离线计算训练字符的几何变换需要[10mnk+23k2mn]次计算，在线需要对测试字符进行正交化，计算测试字符与训练集合的Grassmann流形距离需要[4k3+23k2mn+12mnk+23mn]次计算。三种算法的计算复杂度如表1所示。

3.2 识别性能分析

为了准确的定量分析训练图像数量对三种算法识别率的效果，在MNIST数据库中随机选择不同数量的训练图像和测试图像分别进行了3个识别实验，如表2所示。

表2中，P_N和Q_N分别代表测试集合字符图像和训练集合字符的数量。每个算法都运行10次，统计10次的识别率和识别率的方差，表中的计算时间为测试每个样本的平均计算时间。

表2中的实验数据表明：当训练图像数量不同时，基于GD算法的识别率都要高于另外两种算法的识别率。相对ED和TD，GD将正确识别率分别平均提高了5.7%和15.8%。ED，TD和GD方法的正确识别率的平均标准差分别为2.65，1.78 和0.81。

通过对比实验结果可知，本文提出的基于Grassmann流形距离的方法比现有基于切距离（TD）的方法在计算效率、识别率和稳定性方面都有显著提高。虽然本文算法计算效率不如基于ED的算法，但基于ED的算法识别率和稳定性远远不如本文算法。对于计算效率这一问题会随着高速硬件平台的发展而得到解决。

4 结 论

本文提出了新的基于Grassmann流形距离的手写数字识别算法，由于充分考虑了几何变换下数字字符在非线性空间的分布特性，因此提出的算法在识别精度、稳定性、计算效率上显著优于现有基于切距离的手写字符识别算法，识别精度、稳定性较现有基于欧氏距离的算法有质的提高，对解决目前手写体字符识别中的几何变换瓶颈难题提供了新的思路。下一步的工作主要是在硬件平台上实时实现本文算法。

参考文献

[1] LIU C L， NAKASHIMA K， SAKO H， et al. Handwritten digit recognition： benchmarking of state?of?the?art techniques [J]. Pattern recognition， 2003， 36（10）： 2271?2285.

[2] 秦鑫，张昊.基于BP人工神经网络的手写体数字识别[J].计算机与数字工程，2015，43（2）：223?225.

[3] 王一木，潘赟，龙彦辰，等.基于自组织映射的手写数字识别的并行实现[J].浙江大学学报（工学版），2014，48（4）：742?747.

[4] LECUN Y， JACKEL L D， TOTTOU L， et al. Comparison of learning algorithms for handwritten digit recognition [C]// Proceedings of 1995 International Conference on Artificial Neural Networks. [S.l.： s.n.]， 1995： 53?60.

[5] SEUNG H S， LEE D D. The manifold ways of perception [J]. Science， 2000， 290（5500）： 2268?2269.

[6] SIMARD P Y， LECUN， Y A， DENKER J S， et al. Transformation invariance in pattern recognition?tangent distance and tangent propagation [J]. International journal of imaging systems and technology， 2000， 11（3）： 239?274.

[7] DANIEL K， WOLFGANG M， HERMANN N， et al. Adaptation in statistical pattern recognition using tangent vectors [J]. IEEE transactions on pattern analysis and machine intelligence， 2000， 26（2）： 269?274.

[8] EDELMAN A， ARIAS T A， SMITH S T. The geometry of algorithms with orthogonality constraints [J]. SIAM journal on matrix analysis and applications， 1999， 20（2）： 303?353.

[9] LIN D， YAN S， TANG X. Pursuing informative projection on Grassmann manifold [C]// Proceedings of 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York： IEEE， 2006： 1727?1734.

[10] 王力，吴成东，陈东岳，等.非线性流形上的线性结构聚类挖掘[J].自动化学报，2012，38（8）：1308?1320.

[11] 曾青松.基于支持向量域描述的图像集匹配[J].模式识别与人工智能，2014，27（8）：735?740.

[12] 符达伟，彭立，王利娇，等.在Grassmann流形上构造相干酉空时码[J].通信学报，2013，34（10）：100?105.

[13] ZHANG L， TSE D N C. Communication on the Grassmann manifold： a geometric approach to the noncoherent multiple?antenna channel [J]. IEEE transactions on information theory， 2002， 48（2）： 359?383.

[14] AMSALLEM D， FARHAT C. An interpolation method for adapting reduced?order models and application to aeroelasticity [J]. Journal of AIAA， 2008， 46（7）： 1803?1813.

[15] SUBBARAO R， MEER P. Nonlinear mean shift over Riemannian manifolds [J]. International journal of computer vision， 2009， 84（1）： 1?20.

[16] BEVERIDGE J R， DRAPER B A， CHANG J M， et al. Principal angles separate subject illumination spaces in YDB and CMU?PIE [J]. IEEE transactions on pattern analysis and machine intelligence， 2009， 31（2）： 351?363.

[17] TENENBAUM J， SILVA V， LANGFORD J. A global geometric framework for nonlinear dimensionality reduction. Science， 2000， 290 （5500）： 2319?2323.

[18] ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science， 2000， 290（5500）： 2323?2326.

[19] LIN T， ZHA H. Riemannian manifold learning [J]. IEEE tran?sactions on pattern analysis and machine intelligence， 2008， 30（5）： 796?809.

[20] CUN Y L， CORTES C. The MNIST database of handwritten digits [EB/OL]. [2011?02?17]. http：//yann.lecun.com/exdb/mnist/2011.