基于壓縮感知的閱卷系統(tǒng)手寫漢字識(shí)別算法

鄭昊辰，姜 維

(1.中國人民大學(xué) 附屬中學(xué),北京100080;2.華北水利水電大學(xué) 軟件學(xué)院,河南 鄭州 450045)

閱卷系統(tǒng)是現(xiàn)代化教學(xué)過程中評估教學(xué)效果的重要工具，手寫漢字識(shí)別是閱卷系統(tǒng)的重要組成部分[1-3]。精準(zhǔn)、高效的手寫漢字識(shí)別算法能夠大幅提高閱卷系統(tǒng)的準(zhǔn)確度和便捷性。但是由于漢字識(shí)別存在類別多、結(jié)構(gòu)復(fù)雜、相似字多、書寫差異大[4-8]等問題，手寫漢字識(shí)別算法已成為制約閱卷系統(tǒng)發(fā)展的瓶頸。雖然經(jīng)過多年的研究，漢字識(shí)別已經(jīng)有了許多成果，但其在實(shí)際應(yīng)用中的性能仍需改善。對于無約束的手寫漢字識(shí)別，尚無簡單的方案能滿足高識(shí)別率和識(shí)別精度的要求[9]。近年來，研究人員主要從兩個(gè)方向?qū)h字識(shí)別方法進(jìn)行改善：(1)運(yùn)用神經(jīng)網(wǎng)絡(luò)、隱馬爾可夫、支持向量機(jī)(Support Vector Machine，SVM)、數(shù)學(xué)形態(tài)學(xué)等方法進(jìn)行預(yù)處理、特征提取和分類；(2)采用信息集成的方式從多角度對手寫字符進(jìn)行綜合分析[10]。

在信息處理領(lǐng)域，關(guān)于超完備基的稀疏線性表示計(jì)算問題，即壓縮傳感理論(Compressive Sensing，CS)是近年來的研究熱點(diǎn)之一[11-12]。壓縮感知理論也可應(yīng)用在模式識(shí)別問題上，文獻(xiàn)[13]將訓(xùn)練樣本作為超完備基，利用稀疏表示的判別性實(shí)現(xiàn)了人臉識(shí)別。若每類樣本足夠充分，則測試樣本可表示為同類樣本的線性組合，對于整個(gè)樣本集而言，其表示是非常稀疏的，使得分類問題可通過壓縮感知的方法來實(shí)現(xiàn)。文獻(xiàn)[14]同樣利用這種方法，對手寫數(shù)字進(jìn)行了有效的識(shí)別。本文基于上述思想，將壓縮感知理論應(yīng)用到更為困難的手寫漢字識(shí)別領(lǐng)域。

1 壓縮感知

壓縮感知理論最早被應(yīng)用在信號(hào)處理領(lǐng)域[15]。與傳統(tǒng)的奈奎斯特采樣定理不同，壓縮感知理論認(rèn)為信號(hào)的采樣速率并不僅僅局限于其帶寬，還與信號(hào)的內(nèi)容有很大關(guān)系。只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的，那么就可以用一個(gè)與變換基不相關(guān)的觀測矩陣將變換所得的高維信號(hào)投影到一個(gè)低維空間上。若通過求解一個(gè)優(yōu)化問題就可以從這些少量的投影中以高概率重構(gòu)出原信號(hào)，則證明該投影包含了重構(gòu)信號(hào)的足夠信息。

從上面壓縮感知理論的基本描述可以看出，該理論有三個(gè)要點(diǎn)要解決：(1)稀疏的概念；(2)觀測矩陣的選取；(3)如何求解該優(yōu)化問題。這三點(diǎn)也構(gòu)成了壓縮感知理論研究的主體框架。

1.1 稀疏的概念

從傅立葉變換到小波變換再到后來興起的多尺度幾何分析，科學(xué)家們的研究目的均是為了研究如何在不同的函數(shù)空間為信號(hào)提供一種更加簡潔、直接的分析方式，所有這些變換都旨在發(fā)掘信號(hào)的特征并稀疏表示它,或者說旨在提高信號(hào)的非線性函數(shù)逼近能力，進(jìn)一步研究用某空間的一組基表示信號(hào)的稀疏程度或分解系數(shù)的能量集中程度。

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

(1)

則說明系數(shù)向量Θ在某種意義下是稀疏的。稀疏的另一種定義為：若變換系數(shù)θi=〈x,Ψi〉的支撐域{i：θi≠0}的勢小于等于K，則信號(hào)X是K項(xiàng)稀疏。如何找到最佳的稀疏域，是壓縮感知的基礎(chǔ)和前提，也是重要的研究方向。

1.1 觀測矩陣的選取

y=φΘ=ΦΨTX=ACSX

(2)

對于給定的Y從式(2) 中求出Θ是一個(gè)線性規(guī)劃問題，但由于M?N，即方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這是一個(gè)欠定問題，一般來講無確定解。然而，如果Θ具有K項(xiàng)稀疏性(K?M)，則該問題有望求出確定解。此時(shí)，只要設(shè)法確定出Θ中的K個(gè)非零系數(shù)θi的合適位置，由于觀測向量Y是這些非零系數(shù)θi對應(yīng)Φ的K個(gè)列向量的線性組合，從而可以形成一個(gè)M×K的線性方程組來求解這些非零項(xiàng)的具體值。

1.2 信號(hào)重構(gòu)

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

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

(3)

當(dāng)p=0時(shí)得到0-范數(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è)NP-hard的問題，但求解l1優(yōu)化問題可以得到近似的解，從而使得該問題可解。

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

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

對于上述問題可以有如下表達(dá)

Y=Ax

(5)

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

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

Y=Ax
s.t.x=arg min ||x||1

(6)

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

Ti(x)={0,0,…,ki1,ki2,…,kiNi,0,…,0}

(7)

最后分類用最小殘差來分類，即

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

(8)

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

圖1 算法流程圖

3 實(shí) 驗(yàn)

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

圖2 ETL9B樣本示意

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

為簡化實(shí)驗(yàn)，本文選取2 965個(gè)漢字的200個(gè)類別用于實(shí)驗(yàn)，圖3是測試樣本的稀疏系數(shù)。表1為本文算法在該數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，可以看出，提出的方法可以有效鑒別文字圖像的類別信息。

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

最近中心最近鄰本文方法識(shí)別率97.2%98.9%99.1%

其中，最近中心(Nearest Mean，NM)是用待分類樣本與每個(gè)類別中心點(diǎn)的歐式距離來判斷樣本的類別。最近鄰(Nearest Neighbor，NN)是用待分類樣本與每個(gè)類別的中心點(diǎn)的歐式距離來判斷樣本的類別。

4 結(jié)束語

本文提出的方法用對信號(hào)的隨機(jī)采樣替代了傳統(tǒng)的特征提取方法，簡化了算法的實(shí)現(xiàn)過程；另外，新方法用所有的訓(xùn)練樣本組成訓(xùn)練字典，避免了復(fù)雜的訓(xùn)練過程。在手寫漢字?jǐn)?shù)據(jù)庫ETL9B上的實(shí)驗(yàn)結(jié)果表明提出方法的有效性。未來工作的研究重點(diǎn)將放在如何構(gòu)建新的構(gòu)建觀測矩陣，以節(jié)省存儲(chǔ)空間提升計(jì)算效率。

[1] 田香玲,席志紅.壓縮感知觀測矩陣的優(yōu)化算法[J].電子科技,2015,28(8):102-111.

[2] 任越美,張艷寧,李映.壓縮感知及其圖像處理應(yīng)用研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào),2014,40(8):1563-1575.

[3] Lu W, Liu Y Z,Wang D S.Efficient feedback scheme based on compressed sensing in MIMO wireless net works[J].Computers and Electrical Engineering,2013,39(6):1587-1600.

[4] 阮濤,那彥,王澍.基于壓縮感知的遙感圖像融合方法[J].電子科技,2012,25(4):43-46.

[5] 杜卓明,耿國華,賀毅岳.一種基于壓縮感知的二維幾何信號(hào)壓縮方法[J].自動(dòng)化學(xué)報(bào),2012, 38(11): 1841-1846.

[6] Liang S, Wang Y, Liu Y. Face Recognition Algorithm Based on Compressive Sensing and SRC[C].Guangzhou:Second International Conference on Instrumentation, Measurement, Computer, Communication and Control,IEEE Computer Society, 2012.

[7] 何楚,劉明,馮倩,等.基于多尺度壓縮感知金字塔的極化干涉SAR圖像分類[J].自動(dòng)化學(xué)報(bào), 2011, 37(7):820-827.

[8] Arica Nafiz,YarmanVural,Fatos T. An overview of character recognition focused on off-line handwriting[J].IEEE Transactions on Systems, Man and Cybernetics,2001,31(2):216-233.

[9] Fujisawa H.Forty years of research in character and document recognition-an industrial perspective[M].Amsterdam:Elsevier Science Inc.,2008.

[10] 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.

[11] Cand E J,Wakin M B. "People Hearing Without Listening:" an introduction to compressive sampling[J].IEEE Signal Processing Magazine, 2008,25(2):21-30.

[12] Romberg J.Imaging via compressive sampling [J]. IEEE Signal Processing Magazine, 2008, 25(2):14-20.

[13] Yang A Y, Wright J, Ma Y, et al. Feature selection in face recognition: a sparse representation perspective[J].IEEE Signal Processing Magazine, 2007,24(7):97-109.

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

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

[16] Saito T, Yamada H, Yamamoto K. On the data base ETL9 of handprinted characters in JIS Chinese characters and its analysis[J].IEICE Transactions,1985, 68(4):757-764.