張 軍，張曼雪

(1.西安航空學(xué)院 士官學(xué)院，西安 710077；2.西安外國(guó)語(yǔ)大學(xué) 經(jīng)濟(jì)金融學(xué)院，西安 710128)

基于壓縮感知的手寫漢字識(shí)別研究

張 軍1，張曼雪2

(1.西安航空學(xué)院 士官學(xué)院，西安 710077；2.西安外國(guó)語(yǔ)大學(xué) 經(jīng)濟(jì)金融學(xué)院，西安 710128)

基于壓縮感知理論，提出一種手寫漢字識(shí)別的算法。該算法首先對(duì)手寫漢字圖像進(jìn)行隨機(jī)采樣得到其特征，然后對(duì)其進(jìn)行稀疏表示，并最小化其l1范數(shù)得到樣本的稀疏解，最后利用該稀疏解的系數(shù)判別測(cè)試樣本的類別。

手寫文字識(shí)別；壓縮感知；稀疏表示；l1范數(shù)最小化數(shù)

0 引言

模式識(shí)別就是通過(guò)計(jì)算機(jī)用數(shù)學(xué)技術(shù)方法來(lái)研究模式的自動(dòng)處理和判讀，漢字識(shí)別是模式識(shí)別領(lǐng)域的一個(gè)重要分支。經(jīng)過(guò)了幾十年的發(fā)展，字符識(shí)別已經(jīng)取得了很多顯著的成果，如西文識(shí)別、用于郵政系統(tǒng)的識(shí)別系統(tǒng)等[1-2]。在漢字識(shí)別中，由于漢字類別多、結(jié)構(gòu)復(fù)雜、相似字多、書寫差異大[3]等原因，使手寫漢字識(shí)別工作成為文字識(shí)別中的難點(diǎn)。雖然經(jīng)過(guò)多年的研究，漢字識(shí)別已經(jīng)有了許多成果，但是在實(shí)際應(yīng)用中，提高漢字識(shí)別性能仍然是一個(gè)突出的問題。對(duì)于約束力較小的手寫漢字識(shí)別，目前沒有一種單一的實(shí)用方案能達(dá)到很高的識(shí)別精度與高準(zhǔn)確度，當(dāng)下研究人員正準(zhǔn)備向更為實(shí)用、準(zhǔn)確、錯(cuò)誤率低的方向發(fā)展。一方面，盡量把新的知識(shí)運(yùn)用到預(yù)判別及特點(diǎn)提取當(dāng)中，如隱馬爾可夫、神經(jīng)網(wǎng)絡(luò)、支持?jǐn)?shù)學(xué)形態(tài)學(xué)、向量機(jī)等；另一方面，從多角度對(duì)手寫漢字進(jìn)行全面分析，亦是當(dāng)前的研究熱點(diǎn)。

近年來(lái)，在信息處理領(lǐng)域，稀疏線性計(jì)算問題即壓縮感知理論(Compressive Sensing)引起了廣大研究者的興趣[4-5]。壓縮感知理論在模式識(shí)別問題上也有應(yīng)用，文獻(xiàn)[6]利用稀疏理論有效地實(shí)現(xiàn)了人臉識(shí)別，但不是使用基礎(chǔ)的超完備基，而是使用原始樣本作為超完備基。因?yàn)榧偃缑款悩颖舅夭淖銐蚨嗟脑挘紭颖究梢跃€性組合為測(cè)試樣本，這對(duì)于所有的樣本資料來(lái)說(shuō)，其表示方式必然是比較稀疏的，從而可以通過(guò)壓縮感知的方法來(lái)實(shí)現(xiàn)采樣。文獻(xiàn)[7]同樣利用這種方法，可以對(duì)手寫數(shù)字進(jìn)行有效的識(shí)別。本文基于上述思想，將壓縮感知理論應(yīng)用到更為困難的手寫漢字識(shí)別領(lǐng)域。

1 壓縮感知的基本理論

與傳統(tǒng)的奈奎斯特采樣定理不同，壓縮感知理論認(rèn)為，信號(hào)的采樣速率并不僅僅取決于其帶寬，與信號(hào)的內(nèi)容也有很大的關(guān)系。只要信號(hào)在某個(gè)變換區(qū)域是稀疏的或者是可壓縮的，那么就可以用一個(gè)獨(dú)立的觀測(cè)矩陣將變換所得信號(hào)投影到一個(gè)低維空間上，然后通過(guò)求解，進(jìn)一步優(yōu)化，從這些少量的投影中復(fù)現(xiàn)出原信號(hào)，可以證明這樣的投影包含了重現(xiàn)信號(hào)的足夠信息。

從上面壓縮感知理論的基本描述可以看出，該理論有三個(gè)要點(diǎn)要解決：(1)稀疏的定義；(2)觀測(cè)矩陣如何選??；(3)如何解決優(yōu)化問題。

1.1 稀疏的基本慨念

從拉普拉斯變換、傅立葉變換、小波變換再到后來(lái)興起的多參數(shù)幾何分析，研究目的都是如何在不同的函數(shù)空間，為輸入信號(hào)提供一種更加簡(jiǎn)潔、直接的分析方法，所有的變換都是在發(fā)掘原始信號(hào)的特征并稀疏表示，或者說(shuō)都在提高非線性特性以便更好的逼近原始信號(hào)，進(jìn)一步用函數(shù)空間的多重向量表示信號(hào)的稀疏程度。

稀疏的數(shù)學(xué)定義是：信號(hào)Y在正交基Ψ下的變換系數(shù)向量為Θ=ΨTY，假如對(duì)于00，這些系數(shù)能夠滿足

(1)

則說(shuō)明系數(shù)向量Θ在某種意義下是稀疏的。

稀疏的另外一種定義方法是：如果變換系數(shù)θi=〈x,ψi〉的支撐域{i：θi≠0}小于等于K，則可以說(shuō)信號(hào)X是K2項(xiàng)稀疏。

壓縮感知的基礎(chǔ)和前提是找到最佳的稀疏域，所以這是研究的重要方向。

1.2 如何選擇觀測(cè)矩陣

Y=φΘ=ΦΨTX=ACSX

(2)

對(duì)于給定的Y，從式(2)中求出Θ是一個(gè)線性計(jì)算問題，但因?yàn)镸<>M)，則該問題有望求出確定解。此時(shí)，要設(shè)法明確Θ中的K個(gè)非零系數(shù)θi的合適位置。由于觀測(cè)向量Y是這些非零系數(shù)θi對(duì)應(yīng)Φ的K個(gè)列向量的線性組合，從而可以形成一個(gè)M×K的線性方程組來(lái)求解這些非零項(xiàng)的具體值。

1.3 解決信號(hào)重構(gòu)問題

從少量的投影中以高概率重構(gòu)出原信號(hào)，這就是信號(hào)重構(gòu)的問題。在壓縮感知理論中，由于觀測(cè)數(shù)量M遠(yuǎn)小于信號(hào)長(zhǎng)度N，因此不得不求解欠定方程組Y=ACSX。表面上看，欠定方程組求解似乎是無(wú)法完成，但是由于信號(hào)X是稀疏的或可壓縮的，這個(gè)特性從根本上改變了信號(hào)重構(gòu)問題，使得方程可解。

為更好地描述壓縮感知理論的信號(hào)重構(gòu)問題，首先定義向量X={X1,X2,…,Xn} 的p-范數(shù)為

(3)

當(dāng)p=0時(shí)，得到0-范數(shù)，它實(shí)際上表示X中非零項(xiàng)的個(gè)數(shù)。于是，在信號(hào)X稀疏的前提下，求解方程組Y=ACSX的問題轉(zhuǎn)化為確定最小0-范數(shù)問題

min‖ΨTX‖0s.t.ACSX=ΦΨTX=Y

(4)

但是0-范數(shù)問題是一個(gè)所謂的非確定性的問題，求解l1優(yōu)化問題可以得到近似的解，從而使得該問題可解。

2 壓縮感知在手寫漢字識(shí)別中的應(yīng)用[7]

手寫漢字識(shí)別是確定當(dāng)前輸入的樣本與訓(xùn)練樣本之間的對(duì)應(yīng)關(guān)系。我們假定系統(tǒng)的類別為K，每個(gè)類別對(duì)應(yīng)的訓(xùn)練樣本為N1，N2，…，Nk。對(duì)應(yīng)于類別i，其特征矩陣Ai={vi1,vi2,…,viNi}，則對(duì)于屬于i類的輸入測(cè)試樣本Y，有Y=k1·vi1+k2·vi2+…+kNi·viNi。所以在識(shí)別過(guò)程中，在類別未知的情況下，可以表述為Y=0·v11+…+0·vi-1,Ni-1+k1·vi1+k2·vi2+…+kNi·viN+0·vi+1,1+…+0·vK,Nk，ki,j∈R。

對(duì)于上面可以有如下的表達(dá)

Y=Ax

(5)

對(duì)于待分類樣本Y，x為稀疏系數(shù)，x=(k11,k12,…,kK,Nk)T,A為觀測(cè)矩陣，A=(A1,A2,…,AK)=(v11,v12,…,vK,Nk)。

為了用稀疏系數(shù)x來(lái)表達(dá)Y，需要解方程(5)。方程(5)中，A為M×N矩陣，其中N>>M，所以方程(5)是一個(gè)欠定方程組，有無(wú)窮組解。用最小l1范數(shù)來(lái)約束該問題，即

Y=Axs.t.x=argmin‖x‖1

(6)

在得到稀疏系數(shù)x后，用一個(gè)函數(shù)Ti(x)來(lái)計(jì)算用第i類恢復(fù)出來(lái)的Yi，Yi=ATi(x)，其中

Ti(x)={0,0,…,kil,ki2,…,kiNi0,…,0}

(7)

最后分類用最小殘差來(lái)分類，即

minri(yi)=min‖y-AT(xi)‖

(8)

用壓縮感知進(jìn)行手寫漢字識(shí)別的流程圖如圖1所示。

圖1 算法流程圖

3 實(shí)驗(yàn)及結(jié)果

為了驗(yàn)證算法的有效性，本文提出的方法在ETL9B手寫漢字庫(kù)上做了實(shí)驗(yàn)。ETL9B是由日本JAIST采集的，包含3036個(gè)類別，每個(gè)類別由200個(gè)人書寫。圖2是該數(shù)據(jù)庫(kù)中的部分樣本示意圖。

圖2 ETL9B樣本示意

文章中的算法如下描述：首先對(duì)原始的文字圖像進(jìn)行采樣，得到16×16 的圖像，然后將其直接拉伸成一個(gè)多維的一維向量，再用實(shí)際樣本組成觀測(cè)矩陣A。識(shí)別過(guò)程中，用待識(shí)別樣本在最小l1范數(shù)下計(jì)算稀疏系數(shù)x，利用公式(8)得到分類結(jié)果。

為了簡(jiǎn)化實(shí)驗(yàn)，所以只選了2965個(gè)漢字的200個(gè)類別用于實(shí)驗(yàn)，圖2是測(cè)試樣本的示意圖，圖3是稀疏系數(shù)示意圖。實(shí)驗(yàn)結(jié)果是最近中心的識(shí)別率為97.2%，最近鄰區(qū)域的識(shí)別率為98.9%，本文方法實(shí)驗(yàn)區(qū)域的識(shí)別率為99.1%。

可以看出，本文提出的方法可以有效的鑒別文字圖像的類別信息，其中，最近中心(Nearest Mean)是用待分類樣本與每個(gè)類別的中心點(diǎn)的歐式距離來(lái)判斷樣本的類別。

圖3 稀疏系數(shù)示意圖

4 結(jié)語(yǔ)

基于壓縮感知理論的手寫漢字識(shí)別，首先對(duì)手寫漢字圖像進(jìn)行隨機(jī)采樣得到其特征；然后對(duì)其進(jìn)行稀疏表示，并最小化其l1范數(shù)得到樣本的稀疏解；最后利用該稀疏解的系數(shù)判別測(cè)試樣本的類別。該方法的優(yōu)勢(shì)在于：一是利用對(duì)信號(hào)的隨機(jī)采樣替代了傳統(tǒng)的特征提取方法，簡(jiǎn)化了算法的實(shí)現(xiàn)過(guò)程。二是用所有的訓(xùn)練樣本組成訓(xùn)練字典，避免了復(fù)雜的訓(xùn)練過(guò)程。

在手寫漢字?jǐn)?shù)據(jù)庫(kù)ETL9B上的實(shí)驗(yàn)結(jié)果表明了提出方法的有效性。在未來(lái)工作中，研究的重點(diǎn)將放在如何構(gòu)建新的觀測(cè)矩陣，以節(jié)省存儲(chǔ)空間，提升計(jì)算效率。

[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] 劉長(zhǎng)紅,楊揚(yáng),陳勇.基于壓縮傳感的手寫字符識(shí)別方法[J].計(jì)算機(jī)應(yīng)用,2009,29(8):2080-2082.

[7] 石光明，劉丹華，高大化，等. 壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),2009,37(5):1070-1081.

[責(zé)任編輯、校對(duì)：東艷]

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

陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目(14JK1362)

張軍(1968-)，男，陜西大荔人，副教授，主要從事工業(yè)電氣自動(dòng)化研究。