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

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

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

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

中圖分類號(hào)： TN911.73?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ù)的快速進(jìn)步，手寫數(shù)字識(shí)別技術(shù)（Handwritten Numeral Recognition）也被廣泛地應(yīng)用于財(cái)務(wù)、金融等許多領(lǐng)域，其有著重要的理論和應(yīng)用價(jià)值[1?3]。雖然識(shí)別技術(shù)在脫機(jī)手寫英文、漢字方面中已取得一些成績，但距實(shí)際應(yīng)用還存在一定的距離。一些電子數(shù)據(jù)信息主要由數(shù)字字符和特殊符號(hào)組成，如郵政編碼、銀行數(shù)據(jù)等，在識(shí)別效能上主要取決于輸入數(shù)據(jù)的類型。如果能研發(fā)出一個(gè)高效的手寫體數(shù)字識(shí)別系統(tǒng)將有助于提高人工處理信息的錄入效率，因此手寫體數(shù)字識(shí)別具有較高的實(shí)用價(jià)值。

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

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

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

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

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

1 Grassmann流形距離

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

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

3 實(shí)驗(yàn)與分析

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

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

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

3.2 識(shí)別性能分析

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

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

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

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

4 結(jié) 論

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

參考文獻(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ù)字識(shí)別[J].計(jì)算機(jī)與數(shù)字工程，2015，43（2）：223?225.

[3] 王一木，潘赟，龍彥辰，等.基于自組織映射的手寫數(shù)字識(shí)別的并行實(shí)現(xiàn)[J].浙江大學(xué)學(xué)報(bào)（工學(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].自動(dòng)化學(xué)報(bào)，2012，38（8）：1308?1320.

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

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