基于多重幾何特征和CNN的脫機(jī)手寫算式識別①

付鵬斌,彭荊旋,楊惠榮,李建君

(北京工業(yè)大學(xué) 信息學(xué)部,北京 100124)

目前的脫機(jī)手寫識別技術(shù)可以精確高效地識別數(shù)字、英文字母和漢字[1–6],卻無法較好地處理具有復(fù)雜空間結(jié)構(gòu)關(guān)系的手寫數(shù)學(xué)算式.已有的一些識別算法[7,8]可以實(shí)現(xiàn)簡易的數(shù)學(xué)算式的判別,但對于一些具有復(fù)雜空間組合及包含關(guān)系的手寫算式,不能有效地識別.Aly 等[9]提出僅利用相鄰字符之間的空間關(guān)系進(jìn)行算式識別,但對于特殊字符,如小數(shù)點(diǎn)等,沒有獨(dú)立的識別方法,還需進(jìn)一步考慮相鄰字符的識別結(jié)果.Wang 等[10]提出了一種基于編碼-解碼器框架的新型多模態(tài)注意網(wǎng)絡(luò),用于手寫數(shù)學(xué)算式識別,該方法在CROHME 2014和CROHME 2016 數(shù)據(jù)庫上達(dá)到了54.05%和50.56%的識別準(zhǔn)確率,尚不能滿足應(yīng)用需求.Dai 等[11]實(shí)現(xiàn)了一款基于少量訓(xùn)練集的脫機(jī)手寫算式識別系統(tǒng),實(shí)驗(yàn)結(jié)果顯示,該系統(tǒng)的識別準(zhǔn)確率為80%.胡龍燦等[12]基于Android 平臺開發(fā)了一款手寫數(shù)學(xué)算式識別系統(tǒng),但并未實(shí)現(xiàn)對識別的數(shù)學(xué)算式進(jìn)行智能計(jì)算的功能.

鑒于以上研究成果不能較好地識別具有復(fù)雜空間組合及包含關(guān)系的脫機(jī)手寫數(shù)學(xué)算式,且不具備智能計(jì)算功能.本文提出了一種基于多重幾何特征和CNN的手寫算式識別的解決方案,可有效提高手寫算式識別的準(zhǔn)確率,并以此為基礎(chǔ)設(shè)計(jì)了手寫算式識別系統(tǒng),解決了數(shù)學(xué)算式智能計(jì)算問題,實(shí)現(xiàn)了手寫算式的自動評閱,可應(yīng)用于中小學(xué)課堂.

1 相關(guān)工作

1.1 圖像預(yù)處理

圖像預(yù)處理效果的好壞直接影響到字符識別的準(zhǔn)確率.本文采取的圖像預(yù)處理步驟如圖1所示.

圖1 圖像預(yù)處理

原始圖像來源于手機(jī)或平板電腦等數(shù)字拍照設(shè)備,由于應(yīng)用場景為各類中小學(xué)課堂,學(xué)生拍照會出現(xiàn)角度傾斜、光照不均等情況.預(yù)處理時,首先基于頂點(diǎn)提取算法[13]對原始圖像進(jìn)行傾斜校正,接著采用自適應(yīng)的高斯閾值分割算法對傾斜校正圖像進(jìn)行二值化.為有效去除圖像噪聲,保證圖像分割質(zhì)量,本文采用高斯去噪算法對二值化圖像進(jìn)行降噪操作,并基于圓形膨脹算法連接圖像中的斷裂筆劃,生成原始圖像的黑白圖.然后,依據(jù)字符切分算法[14]對黑白圖進(jìn)行切分,得到單個字符圖像.最后對字符圖像進(jìn)行重心歸一化和尺寸歸一化[15],生成了28×28 像素的目標(biāo)圖像.

1.2 數(shù)據(jù)準(zhǔn)備

本文在MNIST 數(shù)據(jù)集的0～9 十類數(shù)字字符的基礎(chǔ)上,新增了“+,–,×,÷,<,>,=,(,),√”等10 類常用數(shù)學(xué)符號.收集了不同年齡段的學(xué)生和部分成人的手寫體數(shù)據(jù),并以此為基礎(chǔ),經(jīng)平移、旋轉(zhuǎn)、縮放、腐蝕、膨脹、加噪等數(shù)字圖像處理算法,形成了每類數(shù)學(xué)符號圖像約為9000 張,總計(jì)92 429 張的數(shù)學(xué)符號訓(xùn)練集.并將其和MNIST 數(shù)據(jù)集合并,生成了手寫數(shù)學(xué)算式的字符訓(xùn)練庫EQU-MNIST,該數(shù)據(jù)集包含20 類手寫字符,合計(jì)162 429 條數(shù)據(jù).

2 基于CNN的字符識別

2.1 字符識別

文中用于單個字符識別的卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)[16]如圖2所示,網(wǎng)絡(luò)模型包含兩個卷積層、兩個池化層和兩個全連接層.

圖2 CNN 模型

標(biāo)準(zhǔn)輸入為一張28×28 像素的圖像.第一層卷積層設(shè)定有32 個5×5 大小的卷積核,輸出32 張28×28像素的特征圖.然后設(shè)定第一個池化層的大小為2×2,經(jīng)歷一次池化操作,圖像塊大小從28×28 縮小到14×14,得到深度為32的特征圖.將第二層卷積核設(shè)定為5×5,數(shù)量是64,再經(jīng)過一個2×2的池化層可得到64張7×7 像素的特征圖.最后是兩個全連接層,第一個全連接層的神經(jīng)元個數(shù)為1024,第二個全連接層的神經(jīng)元個數(shù)為20.即文中的字符分類數(shù),標(biāo)簽與字符的對應(yīng)關(guān)系如表1所示.

表1 標(biāo)簽字符對應(yīng)關(guān)系

2.2 實(shí)驗(yàn)測試及分析

為驗(yàn)證CNN 模型的泛化性能,實(shí)驗(yàn)統(tǒng)計(jì)了模型對數(shù)字和新增數(shù)學(xué)符號的識別準(zhǔn)確率.訓(xùn)練集為EQUMNIST 字符訓(xùn)練庫,測試集來自不同年齡段多名學(xué)生的手寫體數(shù)據(jù),包括每類字符1000 張,合計(jì)20 000 張的標(biāo)準(zhǔn)化字符圖像.實(shí)驗(yàn)結(jié)果如圖3所示.

觀察圖3柱狀圖的趨勢可以發(fā)現(xiàn),除“1”“7”“>”“)”4 類字符外,其他字符的識別準(zhǔn)確率都穩(wěn)定在98.5%以上,而最低的也達(dá)到97%以上,說明本文的CNN 模型對新的數(shù)據(jù)集也具有良好的適應(yīng)能力.同時,97%以上的字符識別率也保證了本文分類模型的可應(yīng)用性.

3 基于多重幾何特征的手寫算式識別

雖然CNN 分類算法在單個字符識別上已經(jīng)達(dá)到97%以上的識別率,可直接進(jìn)行整式的判別,卻無法識別小數(shù)、分?jǐn)?shù)、指數(shù)、根式等具有復(fù)雜二維空間結(jié)構(gòu)的手寫數(shù)學(xué)算式.為此,本文提出一種基于多重幾何特征的脫機(jī)手寫算式識別算法,算法流程如圖4所示:首先,提取待識別手寫算式的幾何特征;然后,基于不同算式所屬知識點(diǎn)的學(xué)段,結(jié)合多重幾何特征定義結(jié)構(gòu)解析規(guī)則,判定算式類別,實(shí)現(xiàn)識別模型,并重點(diǎn)針對小猿口算、作業(yè)幫(家長版)未實(shí)現(xiàn)的初中知識點(diǎn)中的復(fù)雜指數(shù)和根式識別進(jìn)行優(yōu)化;最后,采用分治算法實(shí)現(xiàn)由以上各種算式組合嵌套的復(fù)合手寫算式(見圖5)識別.

圖4 手寫算式識別算法流程圖

圖5 復(fù)合手寫算式樣例

3.1 多重幾何特征提取

文中設(shè)定原始圖像的左上角坐標(biāo)為坐標(biāo)原點(diǎn),坐標(biāo)軸為X 軸水平向右,Y 軸豎直向下.因此經(jīng)圖像預(yù)處理后的字符圖像g(x,y)除有效像素值外,還包含一組四元組信息(xmin,ymin,xmax,ymax),即圖6中字符最小外包矩形的左上角坐標(biāo),右下角坐標(biāo).基于以上信息,本文選取字符寬高比 (WHR),中心坐標(biāo)(xcenter,ycenter),質(zhì)心坐標(biāo)(xmass,ymass)作為單個字符的幾何特征,結(jié)構(gòu)模型如圖6所示.

圖6 字符幾何特征

字符幾何特征的定義如下:

定義1.圖像的質(zhì)心,也稱為圖像的重心.將圖像中每一點(diǎn)的像素值理解成此點(diǎn)處的質(zhì)量.圖像的質(zhì)心反映了目標(biāo)像素值的集中位置.假設(shè)圖像g(x,y)的(p+q)階矩為:

依據(jù)(p+q)階 矩定義圖像g(x,y)的質(zhì)心坐標(biāo).

以上定義反映的是單個字符的幾何特性,不能有效地表達(dá)相鄰字符間的空間位置關(guān)系.為進(jìn)一步實(shí)現(xiàn)算式符號的重組識別,本文基于單個字符的幾何特征,選取高度比 (HR),寬度比(WR),質(zhì)心偏移角度 (α),中心偏移量 (δ),水平重疊區(qū)間比(HOR),垂直重疊區(qū)間比(VOR),多字符中心坐標(biāo)(Xcenter,Ycenter)作為判斷算式類別的幾何特征.文中設(shè)定目標(biāo)字符序號為2,前一字符序號為1,后一字符序號為3.字符對的結(jié)構(gòu)模型如圖7所示,以前一字符的質(zhì)心坐標(biāo)為坐標(biāo)原點(diǎn),坐標(biāo)軸為X 軸水平向右,Y 軸豎直向上.

字符對幾何特征的定義如下:

定義2.如圖7所示,依據(jù)字符對的質(zhì)心坐標(biāo)定義質(zhì)心偏移角度.質(zhì)心偏移角度反映了相鄰字符間的相對位置關(guān)系.

圖7 字符對幾何模型

定義3.基于前一字符的高度值和字符對的中心坐標(biāo)定義中心偏移量.中心偏移量反映了相鄰字符在豎直方向上的緊鄰度.

定義4.據(jù)字符的四元組信息定義水平重疊區(qū)間比,垂直重疊區(qū)間比.HOR,VOR分別反映了相鄰字符在豎直方向和水平方向上的投影重合度.

其中,m ax(v1,···,vn)表示n個值中的最大者,min(v1,···,vn)表示n個值中的最小者,[m,n]表示端點(diǎn)為m,n的閉區(qū)間,len([m,n])表示區(qū)間長度,即len([m,n])=n?m.

定義5.于多個字符的二維坐標(biāo)定義多字符中心坐標(biāo):

3.2 小數(shù)和分?jǐn)?shù)識別

小數(shù)點(diǎn)通常位于小數(shù)運(yùn)算中相鄰兩個字符的偏下位置,因此本文基于字符高度,中心坐標(biāo),相鄰字符識別結(jié)果等特征,設(shè)定小數(shù)運(yùn)算的判定規(guī)則如下:

如果目標(biāo)字符與相鄰兩個字符滿足上述判定規(guī)則,則說明字符間屬于小數(shù)關(guān)系,文中設(shè)定小數(shù)點(diǎn)的字符標(biāo)記為20,進(jìn)一步得到小數(shù)識別算法流程如圖8所示.

圖8 小數(shù)識別算法流程圖

分?jǐn)?shù)是由分子、分號和分母組合的具有上中下位置關(guān)系的數(shù)學(xué)算式.本文選取寬高比,中心偏移量,水平重疊區(qū)間比,多字符中心坐標(biāo)作為分?jǐn)?shù)運(yùn)算的幾何特征識別指標(biāo).在識別分?jǐn)?shù)時均轉(zhuǎn)換為等價的除法運(yùn)算,同時,添加一組圓括號保證分?jǐn)?shù)運(yùn)算轉(zhuǎn)換為除法運(yùn)算時的優(yōu)先級.具體識別算法流程如圖9所示.

圖9中的分?jǐn)?shù)識別算法只能識別真分?jǐn)?shù),假分?jǐn)?shù)等常見分?jǐn)?shù),為使識別算法能夠完全實(shí)現(xiàn)中小學(xué)數(shù)>學(xué)課堂中的分?jǐn)?shù)判別,本文進(jìn)一步處理類似于等帶分?jǐn)?shù).基于分?jǐn)?shù)識別算法,設(shè)計(jì)帶分?jǐn)?shù)的識別算法如算法1.

算法1.分?jǐn)?shù)識別算法.輸入:原始識別列表oriList輸出:帶分?jǐn)?shù)識別結(jié)果串resultStr Step 1.逆序遍歷原始識別列表oriList,記錄帶分?jǐn)?shù)的整數(shù)系數(shù)在列表中的終止索引endIndex,起始索引startIndex.Step 2.基于索引從原始列表oriList 中提取帶分?jǐn)?shù)的整數(shù)系數(shù)列表,并依據(jù)表1標(biāo)簽字符對應(yīng)關(guān)系轉(zhuǎn)換成整數(shù)字符串integerStr.Step 3.基于終止索引endIndex 從原始列表oriList 中提取帶分?jǐn)?shù)的真分?jǐn)?shù)字符串fractionStr.Step 4.將帶分?jǐn)?shù)的整數(shù)系數(shù)字符串與真分?jǐn)?shù)字符串相加,生成結(jié)果字符串resultStr=“(”+integerStr+“+”+fractionStr+“)”.

圖9 分?jǐn)?shù)識別算法流程圖

3.3 指數(shù)和根式識別優(yōu)化

指數(shù)運(yùn)算屬于典型的上下結(jié)構(gòu)的數(shù)學(xué)算式,指數(shù)一定位于底數(shù)的右上角位置,因此本文基于字符高度,高度比,質(zhì)心偏移角度多重幾何特征,設(shè)定指數(shù)運(yùn)算的判定規(guī)則:

如果相鄰兩個字符滿足上述判定規(guī)則,則說明字符間屬于指數(shù)關(guān)系,進(jìn)一步得到指數(shù)識別算法的偽代碼如下:

其中,函數(shù)isexponential 基于判定規(guī)則實(shí)現(xiàn)相鄰字符指數(shù)關(guān)系的判別,函數(shù)list2str 依據(jù)表1將標(biāo)記列表轉(zhuǎn)換成識別字符串.

為實(shí)現(xiàn)對根式識別模型的優(yōu)化,首先需要完成對特殊符號根號的判別,而根號(√)與表1中的字符對勾(√)在形態(tài)上十分相似,如果僅依據(jù)CNN 模型進(jìn)行識別,可能會導(dǎo)致最終分類結(jié)果的錯誤,進(jìn)而對根式的判別帶來干擾.因此,本文提取根號的拐點(diǎn)特征和半包圍結(jié)構(gòu)特征,實(shí)現(xiàn)根號識別算法見算法2.

算法2.根號識別算法.輸入:字符圖像image輸出:識別結(jié)果result(True or False)Step 1.基于角點(diǎn)提取算法獲取字符的拐點(diǎn)信息,并對其進(jìn)行編號(如圖10(a)所示),如果拐點(diǎn)個數(shù)小于4,則result=False;否則,執(zhí)行Step2.Step 2.依據(jù)根號的①②③拐點(diǎn)信息定義半包圍結(jié)構(gòu)的有效區(qū)域(如圖10(b)所示).HORVOR Step 3.基于,判斷半包圍結(jié)構(gòu)的有效區(qū)域內(nèi)是否存在其他字符,如果不存在,則result=False;否則result=True.

基于算法2,本文依據(jù)“減法”思想完成根式的識別:首先從字符圖像集中移除根號,再進(jìn)行根指數(shù)和根底數(shù)的識別,最后完成根式字符串的構(gòu)建,具體算法實(shí)現(xiàn)如下:

算法3.根式識別算法.輸入:字符圖像集images輸出:根式識別結(jié)果串radicalStr

Step 1.遍歷字符圖像集images,基于算法2 判斷是否存在根號,如果存在,則執(zhí)行Step2;否則,返回根式識別結(jié)果串radicalStr.Step 2.基于根號的②③拐點(diǎn)信息提取根指數(shù)圖像,識別分類并轉(zhuǎn)換為根指數(shù)字符串indexStr.Step 3.基于根式轉(zhuǎn)指數(shù)的運(yùn)算規(guī)則,若indexStr為空,則indexStr=“1/2”;否則,indexStr=“1/”+indexStr.HORVOR Step 4.依據(jù)根號的半包圍結(jié)構(gòu)的有效區(qū)域,結(jié)合,,提取根底數(shù)圖像,識別分類并轉(zhuǎn)換為根底數(shù)字符串baseStr.Step 5.構(gòu)建根式識別字符串radicalStr=“pow(”+baseStr+“,”+indexStr+“)”.

圖10 根號的結(jié)構(gòu)特征

根式識別算法如算法4.

3.4 復(fù)合算式識別

數(shù)學(xué)算式具有二維空間結(jié)構(gòu),在水平分布的基礎(chǔ)上,分?jǐn)?shù)、指數(shù)、根式還具有其內(nèi)嵌結(jié)構(gòu),這種特征使得復(fù)合算式識別過程適合用數(shù)據(jù)結(jié)構(gòu)中的樹來表示.如圖11所示,本文采用分治算法實(shí)現(xiàn)復(fù)合數(shù)學(xué)算式的識別,具體識別過程如圖11所示.

圖11 復(fù)合算式識別

圖11描述了手寫復(fù)合算式的識別過程:首先,基于分治算法,結(jié)合已實(shí)現(xiàn)的手寫算式識別算法(見圖4)將復(fù)合算式逐層分解,直至所有的簡單算式(如小數(shù),分?jǐn)?shù),指數(shù)以及根式)和單個字符都位于樹的最底層,作為樹的葉子節(jié)點(diǎn).然后,基于運(yùn)算規(guī)則將這些簡單算式和字符向上合并,直到生成樹的根結(jié)點(diǎn)為止,即手寫復(fù)合算式被識別出來.以樹的第二層第一個節(jié)點(diǎn)(從左往右)為例,依據(jù)手寫算式識別算法將該算式判定為分?jǐn)?shù);接著提取分子筆劃部分,并將這部分筆劃序列按照字符切分、手寫算式識別的處理方式遞歸進(jìn)行,直到所有節(jié)點(diǎn)均不可再拆分為止,然后逐層將子節(jié)點(diǎn)的識別結(jié)果串組合生成父節(jié)點(diǎn)的識別序列,最終得到分子的識別結(jié)果串,同理,得到分母的識別結(jié)果串;再將分子,分號,分母三者的識別結(jié)果串組合作為一個新的識別序列添加到根節(jié)點(diǎn)的子識別序列中.

4 實(shí)驗(yàn)測試與分析

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

基于以上研究,設(shè)計(jì)并實(shí)現(xiàn)基于多重幾何特征和CNN的脫機(jī)手寫算式識別系統(tǒng).系統(tǒng)環(huán)境參數(shù)信息如表2所示.

表2 系統(tǒng)環(huán)境參數(shù)信息

實(shí)驗(yàn)測試數(shù)據(jù)來自不同年齡段32 名學(xué)生(小學(xué)生10 名,初中生10 名,大學(xué)生12 名)的76 幅手寫體數(shù)學(xué)算式圖像,合計(jì)2660 個手寫算式,算式類別及數(shù)量分布如表3所示.

表3 算式類別及數(shù)量

4.2 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證識別算法的有效性,本文采用算式識別準(zhǔn)確率作為評價標(biāo)準(zhǔn),數(shù)學(xué)定義如下:

其中,p表示算式識別準(zhǔn)確率,TN表示正確識別算式的個數(shù),FN表示錯誤識別算式的個數(shù).

本文設(shè)定圖像分辨率、光照、噪聲等圖像特征參數(shù)作為影響實(shí)驗(yàn)結(jié)果的自變量.采用控制變量法驗(yàn)證不同特征參數(shù)對算式識別率的影響,參數(shù)取值及對應(yīng)的實(shí)驗(yàn)結(jié)果如表4所示.

表4 參數(shù)取值及對應(yīng)的實(shí)驗(yàn)結(jié)果

圖12 圖像分辨率對算式識別率的影響

圖13 光照對算式識別率的影響

圖14 噪聲對算式識別率的影響

觀察圖12～圖14中折線圖的走勢,每組實(shí)驗(yàn)的折線圖并未完全重合,說明圖像分辨率、光照、噪聲等圖像特征參數(shù)對實(shí)驗(yàn)結(jié)果有一定的影響,但仍在合理范圍內(nèi).同時,本文系統(tǒng)在九組實(shí)驗(yàn)中的算式識別準(zhǔn)確率基本穩(wěn)定在80% 以上,算式平均識別率也維持在88.15%～90.43%之間,驗(yàn)證了該系統(tǒng)在不同條件下均具有較好的穩(wěn)定性,可靠性和實(shí)用性.

為驗(yàn)證手寫算式識別算法對復(fù)雜指數(shù)和根式識別的優(yōu)化效果,進(jìn)一步評價系統(tǒng)的性能,將本文系統(tǒng)與目前市場上主流的小猿口算、作業(yè)幫(家長版)進(jìn)行對比實(shí)驗(yàn),比較不同系統(tǒng)的算式識別準(zhǔn)確率,測試集采用本文的實(shí)驗(yàn)測試數(shù)據(jù).系統(tǒng)識別效果截圖見圖15,實(shí)驗(yàn)結(jié)果如表5所示.

由圖15可知,本文的手寫算式識別算法實(shí)現(xiàn)了對初中知識點(diǎn)中復(fù)雜指數(shù)和根式識別的優(yōu)化.同時,分析表5可知,本文系統(tǒng)的算式識別率最高,相比其他系統(tǒng)的優(yōu)勢十分明顯,進(jìn)一步驗(yàn)證了本文系統(tǒng)的實(shí)用性.

圖15 3 個系統(tǒng)識別效果截圖

表5 不同系統(tǒng)算式識別率對比

5 結(jié)論與展望

脫機(jī)手寫算式識別一直是智慧教育領(lǐng)域研究的熱點(diǎn)與難點(diǎn),本文重點(diǎn)針對中小學(xué)數(shù)學(xué)課堂中的手寫算式,提出了一種基于多重幾何特征和CNN的脫機(jī)手寫算式識別的解決方案,有效地提高了手寫算式識別的準(zhǔn)確率,并以此為基礎(chǔ)設(shè)計(jì)實(shí)現(xiàn)了脫機(jī)手寫算式識別系統(tǒng),解決了數(shù)學(xué)算式智能計(jì)算的問題,實(shí)現(xiàn)了手寫算式的自動評閱,將應(yīng)用于陜西省數(shù)所中小學(xué)的課堂教學(xué)中.依托該系統(tǒng)可以高效便捷地完成學(xué)生作業(yè)的批閱,減輕教師負(fù)擔(dān),減少重復(fù)勞動和主觀誤判,顯著提高課堂效率,具有很強(qiáng)的實(shí)際意義.