一種新的基于Grassmann流形度量的手寫體數(shù)字識別方法

王衛(wèi)華 王長杰 張偉

摘 要： 針對現(xiàn)有手寫數(shù)字識別難以處理幾何變換下的識別難題，提出一種新的基于Grassmann流形度量的手寫體數(shù)字識別方法。在分析不同幾何變換下的手寫數(shù)字字符所構(gòu)成的非線性流形空間結(jié)構(gòu)基礎(chǔ)上，定義了Grassmann流形及其距離度量，并通過計算待識別數(shù)字字符與訓(xùn)練字符集合構(gòu)成的Grassmann流形距離實現(xiàn)手寫數(shù)字字符的分類識別。通過在MNIST數(shù)據(jù)庫上的實驗，證明該算法具有較好的實時性和魯棒性，在對數(shù)字的識別率、穩(wěn)定性、計算效率上顯著優(yōu)于現(xiàn)有基于切距離的手寫數(shù)字識別算法，在識別率、穩(wěn)定性上較現(xiàn)有基于歐氏距離的算法有較大的提高。

關(guān)鍵詞： 手寫字符識別； Grassmann流形； 幾何變換； 最近鄰分類

中圖分類號： TN911.73?34； TP391 文獻標(biāo)識碼： 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 引 言

隨著數(shù)字圖像技術(shù)的快速進步，手寫數(shù)字識別技術(shù)（Handwritten Numeral Recognition）也被廣泛地應(yīng)用于財務(wù)、金融等許多領(lǐng)域，其有著重要的理論和應(yīng)用價值[1?3]。雖然識別技術(shù)在脫機手寫英文、漢字方面中已取得一些成績，但距實際應(yīng)用還存在一定的距離。一些電子數(shù)據(jù)信息主要由數(shù)字字符和特殊符號組成，如郵政編碼、銀行數(shù)據(jù)等，在識別效能上主要取決于輸入數(shù)據(jù)的類型。如果能研發(fā)出一個高效的手寫體數(shù)字識別系統(tǒng)將有助于提高人工處理信息的錄入效率，因此手寫體數(shù)字識別具有較高的實用價值。

根據(jù)手寫數(shù)字識別方法不同，目前常用的方法有：模板匹配法、統(tǒng)計決策法和模糊判別法[4]等。這些方法都有自身的優(yōu)點也有自身無法克服的缺陷，識別率和實時性已經(jīng)很難突破。識別率難以提高的原因在于不同的手寫數(shù)字之間的差異較大，存在著幾何、粗細等變化，并且在實際的應(yīng)用過程中，對數(shù)字的識別正確率比文字的識別正確率要求更加嚴(yán)格；實時性難以提高的原因在于目前數(shù)字識別系統(tǒng)面對的往往是大批量數(shù)據(jù)處理。因此，研究出一個高性能識別率的手寫體數(shù)字識別算法任務(wù)艱巨。

最新研究表明人類的視覺感知以流形方式存在，視覺記憶可能以穩(wěn)態(tài)的流形存儲[5]。切距離方法是流形方法的切平面近似，通過計算測試樣本圖像到流形切平面之間的歐氏距離進行圖像分類，切距離方法已在字符中取得了廣泛應(yīng)用，并取得了較好的結(jié)果[6?7]。切距離本質(zhì)上是一種可變形模板匹配，用變化空間在模板處的切平面對變化空間進行近似，具有對幾何變換保持不變的性質(zhì)。然而切距離只能線性近似非線性流形，僅對較小范圍的圖像變換具有度量不變性，仍然是一種線性方法，易陷入局部最優(yōu)。

流形學(xué)習(xí)是近年來興起的非線性降維方法[8?19]，2000年，Seung和Daniel從神經(jīng)心理學(xué)的角度探討了人類的感知方式，認為人的感知可能以流形方式存在[5]，初步給出了流形學(xué)習(xí)的生物學(xué)認知基礎(chǔ)。另外兩篇文章分別從算法實現(xiàn)的角度提出了兩種經(jīng)典的流形學(xué)習(xí)算法Isomap[17]和LLE[18]。隨后不斷有新的流形學(xué)習(xí)算法提出[19]。

Grassmann流形在信號處理和控制領(lǐng)域、最優(yōu)化算法[8]、不變子空間計算[9]中有著重要應(yīng)用，近年來開始逐步應(yīng)用于計算機視覺和模式識別領(lǐng)域[10?12]。其研究內(nèi)容包括通信信道中的最優(yōu)預(yù)測和編碼問題[13]、宇航飛機外形設(shè)計中的流形插值運算[14]以及運動分割問題中涉及到的流形聚類[15]等。最近，一些學(xué)者提出了基于Grassmann流形的人臉識別方法[16]，在不同光照和幾何變化下較傳統(tǒng)識別方法取得了顯著的實驗結(jié)果。

受Grassmann流形距離在人臉識別中的研究啟發(fā)，本文提出了一種新的基于Grassmann流形度量的手寫數(shù)字識別方法，實驗結(jié)果表明，所提出算法在識別精度、穩(wěn)定性、計算效率上顯著優(yōu)于現(xiàn)有基于切距離的手寫字符識別算法，識別精度、穩(wěn)定性較現(xiàn)有基于歐氏距離的算法有明顯提高。

1 Grassmann流形距離

針對切距離方法的不足，本文研究了Grassmann流形距離（GD），并將其應(yīng)用于手寫體字符識別中。Grassmann流形理論是本文手寫體字符識別的理論基礎(chǔ)，與此相關(guān)的微分幾何和黎曼流形的詳細內(nèi)容見文獻[8]。

如圖1所示， 對于[k]幅分辨率為[n]的數(shù)字字符圖像，每幅圖像用列向量存儲，[k]幅圖像構(gòu)成數(shù)據(jù)矩陣[X，]用列空間表示為[R（X），]若[R（X）]的秩為[k，]則[R（X）]為[n]維向量空間的[k]維子空間，記作Grassmann流形[Gk，n]。定義如下：

3 實驗與分析

為了證實所提出算法的有效性和魯棒性，將基于Grassmann流形距離（GD）的手寫數(shù)字識別算法同基于歐氏距離（ED）和基于切距離（TD）的兩種算法進行數(shù)據(jù)對比分析，所有對比的距離度量方法都直接用于最近鄰分類器實現(xiàn)手寫數(shù)字識別。算法用Matlab語言實現(xiàn)，在處理器為Pentium Dual?core 2.5 GHz、內(nèi)存為2 GB的微機上完成。實驗數(shù)據(jù)采用NEC研究中心的MNIST手寫數(shù)字?jǐn)?shù)據(jù)庫（見圖3），許多實驗研究基于此庫[20] ，里面包含了60 000個訓(xùn)練樣本和10 000個測試樣本，每個樣本為分辨率為28×28像素的bmp圖片。本文實驗中切距離算法和Grassmann流形距離算法構(gòu)建訓(xùn)練字符集的旋轉(zhuǎn)參數(shù)范圍[θ]=±20°，縮放參數(shù)范圍在[α1]=1.1和[α2]=0.9之間，平移參數(shù)[β]=±5之間，[γ]=±5之間。每個參數(shù)在參數(shù)變化范圍內(nèi)均勻取值10個。

3.1 計算復(fù)雜度分析

若每幅圖像的分辨率為[m×n，]對于歐氏距離算法，不需要離線計算，只要在每個待測試樣本與標(biāo)準(zhǔn)字符之間計算歐氏距離即可。對于切距離算法，離線過程，對每個訓(xùn)練字符進行幾何變換（有[k]個變換），并求解切向量需要[10mnk]次計算；在線過程計算測試字符的幾何變換和切向量同樣需要[10mnk]次計算，計算訓(xùn)練字符與測試字符之間的切距離需要[6k3+2mnk2+4mnk+2mn]次計算。對于本文提出的算法，離線計算訓(xùn)練字符的幾何變換需要[10mnk+23k2mn]次計算，在線需要對測試字符進行正交化，計算測試字符與訓(xùn)練集合的Grassmann流形距離需要[4k3+23k2mn+12mnk+23mn]次計算。三種算法的計算復(fù)雜度如表1所示。

3.2 識別性能分析

為了準(zhǔn)確的定量分析訓(xùn)練圖像數(shù)量對三種算法識別率的效果，在MNIST數(shù)據(jù)庫中隨機選擇不同數(shù)量的訓(xùn)練圖像和測試圖像分別進行了3個識別實驗，如表2所示。

表2中，P_N和Q_N分別代表測試集合字符圖像和訓(xùn)練集合字符的數(shù)量。每個算法都運行10次，統(tǒng)計10次的識別率和識別率的方差，表中的計算時間為測試每個樣本的平均計算時間。

表2中的實驗數(shù)據(jù)表明：當(dāng)訓(xùn)練圖像數(shù)量不同時，基于GD算法的識別率都要高于另外兩種算法的識別率。相對ED和TD，GD將正確識別率分別平均提高了5.7%和15.8%。ED，TD和GD方法的正確識別率的平均標(biāo)準(zhǔn)差分別為2.65，1.78 和0.81。

通過對比實驗結(jié)果可知，本文提出的基于Grassmann流形距離的方法比現(xiàn)有基于切距離（TD）的方法在計算效率、識別率和穩(wěn)定性方面都有顯著提高。雖然本文算法計算效率不如基于ED的算法，但基于ED的算法識別率和穩(wěn)定性遠遠不如本文算法。對于計算效率這一問題會隨著高速硬件平臺的發(fā)展而得到解決。

4 結(jié) 論

本文提出了新的基于Grassmann流形距離的手寫數(shù)字識別算法，由于充分考慮了幾何變換下數(shù)字字符在非線性空間的分布特性，因此提出的算法在識別精度、穩(wěn)定性、計算效率上顯著優(yōu)于現(xiàn)有基于切距離的手寫字符識別算法，識別精度、穩(wěn)定性較現(xiàn)有基于歐氏距離的算法有質(zhì)的提高，對解決目前手寫體字符識別中的幾何變換瓶頸難題提供了新的思路。下一步的工作主要是在硬件平臺上實時實現(xiàn)本文算法。

參考文獻

[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īng)網(wǎng)絡(luò)的手寫體數(shù)字識別[J].計算機與數(shù)字工程，2015，43（2）：223?225.

[3] 王一木，潘赟，龍彥辰，等.基于自組織映射的手寫數(shù)字識別的并行實現(xiàn)[J].浙江大學(xué)學(xué)報（工學(xué)版），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] 王力，吳成東，陳東岳，等.非線性流形上的線性結(jié)構(gòu)聚類挖掘[J].自動化學(xué)報，2012，38（8）：1308?1320.

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

[12] 符達偉，彭立，王利嬌，等.在Grassmann流形上構(gòu)造相干酉空時碼[J].通信學(xué)報，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.