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

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

(北京工業大學 信息學部,北京 100124)

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

鑒于以上研究成果不能較好地識別具有復雜空間組合及包含關系的脫機手寫數學算式,且不具備智能計算功能.本文提出了一種基于多重幾何特征和CNN的手寫算式識別的解決方案,可有效提高手寫算式識別的準確率,并以此為基礎設計了手寫算式識別系統,解決了數學算式智能計算問題,實現了手寫算式的自動評閱,可應用于中小學課堂.

1 相關工作

1.1 圖像預處理

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

圖1 圖像預處理

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

1.2 數據準備

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

2 基于CNN的字符識別

2.1 字符識別

文中用于單個字符識別的卷積神經網絡結構[16]如圖2所示,網絡模型包含兩個卷積層、兩個池化層和兩個全連接層.

圖2 CNN 模型

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

表1 標簽字符對應關系

2.2 實驗測試及分析

為驗證CNN 模型的泛化性能,實驗統計了模型對數字和新增數學符號的識別準確率.訓練集為EQUMNIST 字符訓練庫,測試集來自不同年齡段多名學生的手寫體數據,包括每類字符1000 張,合計20 000 張的標準化字符圖像.實驗結果如圖3所示.

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

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

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

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

圖5 復合手寫算式樣例

3.1 多重幾何特征提取

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

圖6 字符幾何特征

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

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

依據(p+q)階 矩定義圖像g(x,y)的質心坐標.

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

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

定義2.如圖7所示,依據字符對的質心坐標定義質心偏移角度.質心偏移角度反映了相鄰字符間的相對位置關系.

圖7 字符對幾何模型

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

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

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

定義5.于多個字符的二維坐標定義多字符中心坐標:

3.2 小數和分數識別

小數點通常位于小數運算中相鄰兩個字符的偏下位置,因此本文基于字符高度,中心坐標,相鄰字符識別結果等特征,設定小數運算的判定規則如下:

如果目標字符與相鄰兩個字符滿足上述判定規則,則說明字符間屬于小數關系,文中設定小數點的字符標記為20,進一步得到小數識別算法流程如圖8所示.

圖8 小數識別算法流程圖

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

圖9中的分數識別算法只能識別真分數,假分數等常見分數,為使識別算法能夠完全實現中小學數>學課堂中的分數判別,本文進一步處理類似于等帶分數.基于分數識別算法,設計帶分數的識別算法如算法1.

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

圖9 分數識別算法流程圖

3.3 指數和根式識別優化

指數運算屬于典型的上下結構的數學算式,指數一定位于底數的右上角位置,因此本文基于字符高度,高度比,質心偏移角度多重幾何特征,設定指數運算的判定規則:

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

其中,函數isexponential 基于判定規則實現相鄰字符指數關系的判別,函數list2str 依據表1將標記列表轉換成識別字符串.

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

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

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

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

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

圖10 根號的結構特征

根式識別算法如算法4.

3.4 復合算式識別

數學算式具有二維空間結構,在水平分布的基礎上,分數、指數、根式還具有其內嵌結構,這種特征使得復合算式識別過程適合用數據結構中的樹來表示.如圖11所示,本文采用分治算法實現復合數學算式的識別,具體識別過程如圖11所示.

圖11 復合算式識別

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

4 實驗測試與分析

4.1 實驗環境及數據

基于以上研究,設計并實現基于多重幾何特征和CNN的脫機手寫算式識別系統.系統環境參數信息如表2所示.

表2 系統環境參數信息

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

表3 算式類別及數量

4.2 實驗結果及分析

為驗證識別算法的有效性,本文采用算式識別準確率作為評價標準,數學定義如下:

其中,p表示算式識別準確率,TN表示正確識別算式的個數,FN表示錯誤識別算式的個數.

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

表4 參數取值及對應的實驗結果

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

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

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

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

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

由圖15可知,本文的手寫算式識別算法實現了對初中知識點中復雜指數和根式識別的優化.同時,分析表5可知,本文系統的算式識別率最高,相比其他系統的優勢十分明顯,進一步驗證了本文系統的實用性.

圖15 3 個系統識別效果截圖

表5 不同系統算式識別率對比

5 結論與展望

脫機手寫算式識別一直是智慧教育領域研究的熱點與難點,本文重點針對中小學數學課堂中的手寫算式,提出了一種基于多重幾何特征和CNN的脫機手寫算式識別的解決方案,有效地提高了手寫算式識別的準確率,并以此為基礎設計實現了脫機手寫算式識別系統,解決了數學算式智能計算的問題,實現了手寫算式的自動評閱,將應用于陜西省數所中小學的課堂教學中.依托該系統可以高效便捷地完成學生作業的批閱,減輕教師負擔,減少重復勞動和主觀誤判,顯著提高課堂效率,具有很強的實際意義.