基于粘連符號分割和多特征融合的手寫公式識別

付鵬斌，李建君，楊惠榮

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

字符粘連是影響數(shù)學(xué)公式正確識別的一個重要原因.自首次提出數(shù)學(xué)公式識別的概念以來，國內(nèi)外研究者針對識別過程中遇到的粘連問題提出不同的解決方案：Strathy等[1]提出基于結(jié)構(gòu)特征的分割算法，該算法利用字符結(jié)構(gòu)上的特征點對粘連區(qū)域進行切分，但存在手寫體字符特征識別不準(zhǔn)確的問題.Vellasques等[2]、Tamhankar等[3]基于垂直投影，通過連接圖像垂直投影的波峰和波谷得到一條切割粘連部分的路徑，以此來實現(xiàn)切分粘連符號的目的.Congedo等[4]提出滴水算法，通過模擬水的滴落過程來切分粘連符號.Pal等[5]的儲水區(qū)算法利用區(qū)域的大小和位置找到字符的粘連位置，但字符的閾值大小難以把控.以上幾類常見的方法都只能針對水平結(jié)構(gòu)的簡單粘連符號進行裁切，無法解決具有復(fù)雜二維空間結(jié)構(gòu)的粘連符號，而這類粘連符號一般包含著數(shù)學(xué)特殊符號，切分難度更大.隨著深度學(xué)習(xí)的發(fā)展，Wang等[6]、Liu等[7]、Shan等[8]、Zhang等[9]提出基于編碼-解碼器框架的多模態(tài)注意網(wǎng)絡(luò)來進行算式的識別，該方法通過端對端的方式規(guī)避了傳統(tǒng)識別方法中的切分步驟，通過直接訓(xùn)練端對端的網(wǎng)絡(luò)模型得到識別結(jié)果.但該方法需要大量標(biāo)注數(shù)據(jù)用來訓(xùn)練模型，而手寫數(shù)學(xué)公式空間結(jié)構(gòu)復(fù)雜且種類繁多，難以標(biāo)注，方法所需客觀條件較難滿足，達不到應(yīng)用場景需求.

針對以上方法的不足，本文提出一種基于字符兩側(cè)輪廓軌跡特征的裁切方法來獲取粘連符號的切分點和切分方向，同時結(jié)合字符的幾何特性對切分后的字符片段進行多特征融合的特殊符號判別，最終使特殊符號與普通字符分離，達到切分粘連符號的目的.經(jīng)實驗驗證，本方法能有效裁切具有復(fù)雜二維空間結(jié)構(gòu)的粘連符號，同時無須大量數(shù)據(jù)訓(xùn)練模型，具有應(yīng)用性廣的特點.

1 公式圖片預(yù)處理

脫機手寫數(shù)學(xué)公式的識別應(yīng)用場景多是實際的教學(xué)領(lǐng)域，公式圖像的獲取途徑主要是拍攝設(shè)備拍攝或光學(xué)設(shè)備掃描.受光照等外界因素影響，需首先對公式圖像進行預(yù)處理.具體步驟如圖1所示.

圖1 圖像預(yù)處理Fig.1 Image pretreatment

首先采用高斯閾值分割算法和高斯去噪算法[10]對原圖像進行二值化和去噪處理；然后對圖像進行腐蝕、膨脹操作[11]，使字符之間的邊界更加凸出；再進行縱向投影，將公式縱向地分為若干字符塊，如圖2中①；最后針對字符塊進一步分割，如圖2中②，采用八連通域搜索算法，得到多個單連通字符，在該步驟中包含對“i”“j”等由多連通區(qū)域構(gòu)成的字符和“5”“θ”等容易寫成孤立兩筆的字符的合并處理，得到最終待處理的字符對象.

圖2 字符粗切分Fig.2 Character rough-segmentation

經(jīng)過縱向投影和連通域搜索裁切，能實現(xiàn)公式的基本分割，但手寫公式中還存在字符粘連情況，如圖3(a)所示，原圖分離出的一個根式，其中根號與底數(shù)存在粘連點，不能有效分離；而在圖3(b)(c)(d)中，也分別存在與分號、積分、求和這類特殊符號粘連的情況.這些特殊符號和數(shù)字字母之間存在半包圍、上下重疊關(guān)系，右上角、右下角空間位置等復(fù)雜關(guān)系組合，用常規(guī)的裁切方法難以分隔.

圖3 粘連符號示例Fig.3 Examples of adhesive characters

2 粘連符號的切分

2.1 粘連符號的檢測

在對粘連符號進行裁切前首先需要進行粘連符號的檢測.由于粘連符號的大小一般比同一公式中其余普通字符大，同時內(nèi)部筆畫數(shù)相對較多[12].利用這2個特點，提取出寬度、高度、黑白交替變化最大值3個特征來檢測粘連符號塊.

定義1自上而下(自左而右)逐行(列)掃描圖像，統(tǒng)計每一行(列)像素點由黑到白的變化次數(shù)，最后取所有行(列)中最大值,該值即為黑白交替變化最大值.

如圖4所示，該粘連符號的橫向黑白交替變化最大值為虛線l3與圖像的交點個數(shù)5，縱向黑白交替變化最大值為虛線l1與圖像的交點個數(shù)2.

圖4 橫/縱向黑白交替變化Fig.4 Horizontal/vertical alternation of pixels

收集得到1 291條手寫數(shù)學(xué)公式圖片，其中存在粘連符號共199個.對收集得到的粘連符號的寬度、高度、橫/縱向黑白交替變化最大值進行統(tǒng)計，并與原公式全體字符的平均高度、寬度進行對比.統(tǒng)計結(jié)果如表1所示.

表1 粘連符號統(tǒng)計特征及數(shù)量Table 1 Statistical characteristics and quantity of adhesive characters

經(jīng)過統(tǒng)計，98.99%以上粘連符號的平均高度或?qū)挾榷即笥诠秸w字符平均水平的0.85，94.47%以上粘連符號的橫/縱向黑白交替變化最大值都大于3.由此，得到候選粘連符號的篩選流程，具體步驟如下：

首先，以原始圖像的左上角坐標(biāo)為坐標(biāo)原點、坐標(biāo)軸為X軸水平向右、Y軸豎直向下建立直角坐標(biāo)系.遍歷公式圖片中所有單連通字符C1,C2,…,Cn，對每個字符Ci(1≤i≤n)循環(huán)其所有點Pi1,Pi2,…,Pim，每個點Pij包含該點坐標(biāo)信息(xij,yij)，據(jù)此得到每個單連通字符的高度Hi和寬度Wi分別為

Hi=max(yi1,…,yim)-min(yi1,…,yim)+1

(1)

Wi=max(xi1,…,xim)-min(xi1,…,xim)+1

(2)

然后，統(tǒng)計得到所有單連通字符的橫/縱向黑白交替變化最大值.橫向使用一條水平直線從圖像最上側(cè)平移到圖像最下側(cè)，統(tǒng)計與字符的最大交叉點個數(shù)K1；縱向使用一條豎直直線從圖像最左側(cè)平移到圖像最右側(cè)，統(tǒng)計與字符的最大交叉點個數(shù)K2.

最后，遍歷圖片中所有單連通字符C1,C2,…,Cn，依次對每一個字符Ci(1≤i≤n)進行判斷，若滿足

(3)

則該字符為候選粘連符號.

2.2 輪廓雙側(cè)檢測切分算法

對于粘連符號，粘連部位情況[13]見表2.

表2 粘連部位類型Table 2 Touching patterns

可見，對于絕大多數(shù)的粘連情況，在粘連點處兩側(cè)輪廓的變化趨勢都會發(fā)生突變.

定義2從圖像一端點出發(fā)，分別沿著該線的兩側(cè)行進，行進路線為2條由所有圖像連續(xù)邊界點構(gòu)成的曲線.這2條曲線分別定義為圖像內(nèi)輪廓曲線、圖像外輪廓曲線.如圖5中表示的2條有向曲線.

圖5 圖像內(nèi)/外輪廓曲線Fig.5 Inner/outer contour curve of image

如圖6所示，順著某一端點A的兩側(cè)輪廓出發(fā)，當(dāng)未遇到粘連點S時，兩側(cè)輪廓的趨勢是一致的，見圖6中1與1′；而當(dāng)遇到粘連點時，兩側(cè)輪廓的趨勢發(fā)生變化，見圖6中2與2′.

圖6 粘連部位內(nèi)外輪廓趨勢變化Fig.6 Trend of adhesive regions’ inner/outer contour

根據(jù)這個特點，本文提出輪廓雙側(cè)檢測切分算法，通過字符輪廓兩側(cè)的行進趨勢變化來尋找粘連符號的粘連點，進而實現(xiàn)切分粘連符號的目的.主要分為以下幾步：首先得到字符圖像的端點，接著順著端點得到所有輪廓點的鄰接順序，再沿著正反2條輪廓序列尋找粘連點，最后沿著粘連點進行裁切和組合以得到正確的裁切結(jié)果.具體步驟如下.

步驟1首先得到圖像的外輪廓點和方向標(biāo)記.對單連通字符圖像的所有像素點進行遍歷，判斷其是否是輪廓點，輪廓點即為左右上下4個方向中任意一個方向所對應(yīng)位置為空白的像素點.為了方便后續(xù)對輪廓點進行排序，這里對所有輪廓點定義其空白標(biāo)記：對輪廓點4個方向按照上左下右的順序進行遍歷，若哪個方向最先出現(xiàn)空白位置，則該輪廓點的空白標(biāo)記為該方向?qū)?yīng)的標(biāo)記，標(biāo)記按照上左下右的順序依次為1、2、3、4.

圖7中外側(cè)8個黑色像素塊為1個單連通字符圖像的外輪廓點，其中a、h、g三點的空白標(biāo)記為1，b、c兩點為2，d、e兩點為3，f點則為4.

圖7 方向標(biāo)記Fig.7 Direction sign

步驟2得到單連通字符的輪廓點及其對應(yīng)的空白標(biāo)記后，接著利用空白標(biāo)記來形成正確的輪廓順序.空白標(biāo)記的作用是，依據(jù)當(dāng)前像素點的外圍空白情況動態(tài)地調(diào)整搜索路徑，以實現(xiàn)沒有死循環(huán)、無重復(fù)路徑、耗時最短地得到正確的輪廓點順序.

首先隨機選擇一個輪廓點作為起點，并將其放入輪廓點順序序列，隨后進行路徑的搜索，得到與該點相連的下一個輪廓點.搜索規(guī)則為：若當(dāng)前輪廓點的空白標(biāo)記為1，則搜索順序為右上→右→右下→下→左下→左→左上，見圖8(a)；若當(dāng)前輪廓點的空白標(biāo)志位為2，則搜索順序為左上→上→右上→右→右下→下→左下，見圖8(b)；若當(dāng)前輪廓點的空白標(biāo)志位為3，則搜索順序為左下→左→左上→上→右上→右→右下，見圖8(c)；若當(dāng)前輪廓點的空白標(biāo)志位為4，則搜索順序為右下→下→左下→左→左上→上→右上，見圖8(d).按照以上搜索規(guī)則來獲取第1個出現(xiàn)的輪廓點，將其放入輪廓點順序序列，然后對該輪廓點執(zhí)行相同的步驟，直到出現(xiàn)的新輪廓點為起點則搜索結(jié)束.經(jīng)過以上步驟，得到輪廓點順序序列〈P1,P2,…,Pn〉，n為輪廓點個數(shù).

圖8 輪廓點搜索順序Fig.8 Searching order of outline points

步驟3接下來獲取字符的所有端點，將它們作為本算法的出發(fā)點.端點的判定依據(jù)為：遍歷圖像的所有輪廓點，對每個點尋找其8個方向領(lǐng)域，若其領(lǐng)域內(nèi)空白像素塊的個數(shù)大于等于5，則可確定該輪廓點為端點，如圖9中的字符共有7個端點，位置如箭頭所示.得到字符所有端點后，對距離較近的端點進行合并，最終形成端點集合{D1,D2,…,Dk}，k為端點個數(shù).隨機選擇一個端點D1(假定在原輪廓點集合中為Pr)作為出發(fā)點，原輪廓點順序序列〈P1,P2,…,Pn〉轉(zhuǎn)化為〈Pr,Pr+1,…,Pn,P1,…,Pr-1〉.

圖9 端點Fig.9 Endpoint

步驟4經(jīng)過步驟1～3，得到1條以P1作為起始點的圖像輪廓點順序序列〈P1,P2,…,Pn〉.再沿著起始端點向相反方向搜索，可得到1條與原序列相反的圖像輪廓點順序序列〈P1,Pn,Pn-1,…,P2〉.這2條序列分別對應(yīng)圖5(a)(b).

步驟5得到圖像的正反輪廓點順序序列后，計算圖像的外輪廓方向鏈碼.外輪廓方向鏈碼的作用是表示圖像輪廓點順序序列的變化趨勢，其計算方式為：依次遍歷圖像輪廓點順序序列中的輪廓點，若下一個點在當(dāng)前點的上方，鏈碼為1；若在下方，鏈碼為-1；若在右方，鏈碼為2；若在左方，鏈碼為-2.

步驟6通過步驟5中計算規(guī)則得到輪廓點鏈碼序列〈R1,R2,…,Rn〉后，接下來開始尋找2個鏈碼序列的突變點，并根據(jù)突變點將2個鏈碼序列劃分成若干子序列〈R1,R2,…,Ri〉,〈Ri+1,Ri+2,…,Rj〉,…,〈Rt,Rt+1，…,Rn-1〉，其中前后子序列的鏈碼不一致，而每個子序列中的鏈碼都相等.記錄所有子序列的長度及鏈碼，最終得到一個方向的輪廓趨勢序列〈〈l1,s1〉,〈l2,s2〉,…,〈lm,sm〉〉(li為子序列的長度，si為對應(yīng)的鏈碼，si∈{1,-1,2,-2}，i≤m).最后從前往后同時遍歷2段輪廓趨勢序列，若二者對應(yīng)輪廓趨勢子序列中的鏈碼相等，且二者子序列長度的差值小于一定的閾值，則繼續(xù)往后遍歷；否則，2段子序列中發(fā)生突變的位置對應(yīng)原圖的點為候選粘連點，如圖10(a)中切分點所示，結(jié)束遍歷.若遍歷結(jié)束，沒有子序列滿足上述條件，則該字符不是粘連符號.

圖10 切分點與切分結(jié)果Fig.10 Cut point and cut results

若存在候選粘連點，根據(jù)正反輪廓趨勢序列在該點處的鏈碼，可得到2條切線.通過2條切線將原字符從粘連點處一分為三，切分結(jié)果見圖10(b).

2.3 過切分合并

此時得出的是過切分結(jié)果，還需從切分出的3塊子圖中找出正確的組合，才能得到正確的字符圖像.需對3塊子圖進行兩兩合并，見圖11，對合并后的字符圖像和單獨子圖，進行特殊符號的檢測和識別.若存在特殊符號，則完成粘連符號的裁切任務(wù)；否則，從原圖像另外一個端點出發(fā)，重復(fù)步驟4～6.若從所有端點出發(fā)都未能得到正確的切分結(jié)果，說明該字符圖像中不存在特殊符號，后續(xù)按照普通字符的粘連情況處理.

圖11 過切分子圖組合Fig.11 Combinations of over-segmented subgraphs

3 公式符號的檢測與識別

公式中存在2類符號：一類是大小、形狀相對固定的普通數(shù)學(xué)符號；另一類是大小不固定、形狀不規(guī)則的特殊符號，如根號、求和號、積分號等.無法用常規(guī)的算法對2類符號統(tǒng)一進行識別檢測，因此將其從公式中正確剝離、提取識別至關(guān)重要.

3.1 多特征融合的特殊符號檢測識別

本文結(jié)合寬度、高度、角點個數(shù)、投影輪廓、旋轉(zhuǎn)對稱等幾何特性，對經(jīng)2.2切分算法得到的過切分字符片段，經(jīng)合并組合后進行特殊符號的識別檢測.經(jīng)統(tǒng)計[14]，常見特殊符號包括以下4類：根號、分號、積分號、求和號.

3.1.1 根號的識別

根號由一條折線構(gòu)成，其圖像中存在3個突變點，如圖12中箭頭所示，被突變點分割的線段保持固定的斜率，而前后線段的斜率發(fā)生較大的變化.根據(jù)這種斜率趨勢的變化，采用上輪廓投影斜率作為根號的判別特征.

圖12 根號及其突變點Fig.12 Diagram of radical and its breakpoint

定義3自上而下逐列掃描圖像，由每列的第1個黑色像素點組成的輪廓曲線稱之為上輪廓投影，見圖13.上輪廓中后一點與前一點的高度的差值為上輪廓投影斜率，見圖14.

圖13 上輪廓投影Fig.13 Upper contour projection

圖14 上輪廓投影斜率Fig.14 Slope of upper contour projection

由此可得根號的識別算法步驟如下.

步驟1算法輸入：字符圖像image.

步驟2從左到右依次從圖像頂端向下垂直作投影，記錄其與每一列相交的第1個黑色像素點對應(yīng)的高度值hi，并最終依次合并，形成上輪廓點序列L:〈h1,h2,…,hn〉.

步驟3遍歷上輪廓點序列L，對序列中的值進行兩兩相減得到斜率ri=hi-hi-1，最終合并所有斜率得到上輪廓斜率序列S:〈r1,r2,…,rn-1〉.

步驟4對上輪廓斜率序列S進行預(yù)處理，在不影響局部變化趨勢的前提下對干擾點進行抹平.

步驟5遍歷上輪廓斜率序列S，記錄斜率突變點i及其前后段的斜率大小.若滿足以下2種情況之一，則點i為突變點：1)后段斜率ri與前段斜率ri-1之積小于0；2)前段斜率ri-1小于0同時后段斜率ri與前段斜率ri-1之差小于等于2.

步驟6統(tǒng)計突變點的個數(shù)R，并將突變點i的橫縱坐標(biāo)xi、yi及其前后段斜率ki-、ki+按照橫坐標(biāo)遞增的順序排列，得到突變點信息序列L:〈〈x1,y1,k1-,k1+〉,〈x2,y2,k2-,k2+〉,…，〈xR,yR,kR-,kR+〉〉.若突變點信息序列L同時滿足以下幾項，則可判定該字符圖像為根號：1)突變點的個數(shù)R等于3；2)3個突變點的橫坐標(biāo)滿足x10和k1+<0和k2-<0和k2+>0和k3->0.否則該圖像不是根號.

步驟7輸出識別結(jié)果result.

3.1.2 分號的識別

分號是一條較長的水平直線，此處使用上輪廓斜率序列S:〈r1,r2,…,rn〉、寬高比θ、縱向黑白交替變化數(shù)N來作為分式判別的特征.

若圖像同時滿足以下條件，則該字符被識別為分號：1)寬高比θ≥2；2)縱向黑白交替變化數(shù)恒為1；3)上輪廓斜率穩(wěn)定，保持在0左右.

3.1.3 積分號的識別

積分號具有旋轉(zhuǎn)對稱的特點，即將圖像的下半部分從幾何中心處旋轉(zhuǎn)180°，其與圖像的上半部分大致重疊，見圖15(a).同時積分號一定寬度范圍內(nèi)的點的斜率滿足先增大后減小的規(guī)律，見圖15(b)中虛線范圍內(nèi)的點a、b、c、d，滿足kakd.最后利用積分號形狀較為狹長的特點，加上寬高比這一特征，可得積分號的識別規(guī)則.

圖15 積分號部分特征Fig.15 Some features of integral sign

3.1.4 求和號的識別

求和號中存在一個寬度界限，在該界限范圍內(nèi)縱向黑白交替變化數(shù)恒為4.同時，該范圍內(nèi)的圖像可被劃分成如圖16(a)的3個區(qū)域，3個區(qū)域內(nèi)的縱向空白像素長度的變化滿足遞增或遞減的規(guī)律，如圖16(a)中①③區(qū)間的縱向空白像素長度從左到右依次遞增，而②區(qū)間的縱向空白像素長度從左到右始終遞減.

圖16 求和號部分特征Fig.16 Some features of summation sign

求和號的筆畫都是筆直的線段，線段的交叉點較為明顯，這類點被稱作角點，如圖16(b)中的a、b、c、d、e五點都是角點.求和號的角點個數(shù)N及其相互位置關(guān)系滿足以下規(guī)律：1)N=5；2)xa>xc,xb>xc,xdyc,ye>yc.若字符圖像的特征滿足上述所有條件，則可判定該字符為積分號.

3.2 普通字符識別

經(jīng)統(tǒng)計，數(shù)學(xué)公式中常用數(shù)學(xué)普通符號類型如表3所示.

表3 常用數(shù)學(xué)符號Table 3 Common mathematical symbols

針對普通字符，采用卷積神經(jīng)網(wǎng)絡(luò)模型[15]進行識別.網(wǎng)絡(luò)模型包含2個卷積層、2個池化層和2個全連接層.網(wǎng)絡(luò)模型見圖17.

圖17 卷積神經(jīng)網(wǎng)絡(luò)模型Fig.17 Model of convolutional neural network

經(jīng)過模型訓(xùn)練，單字符的識別率達到了98.85%，達到了預(yù)期目標(biāo).錯誤的原因主要是幾類易混字符的誤判，如1和l、a和α.

4 結(jié)構(gòu)解析與整體公式識別

經(jīng)過前面的裁切與識別，得到單個數(shù)學(xué)公式中所有單字符的識別結(jié)果.本文利用數(shù)學(xué)特殊符號與其相鄰字符位置關(guān)系進行公式的語義解析，以實現(xiàn)公式的整體識別.

特殊結(jié)構(gòu)中一般包含如下特殊符號：根號、分號、積分號、求和號.它們與周圍普通字符之間的位置關(guān)系見圖18.

圖18 特殊符號及其周邊位置關(guān)系Fig.18 Position relations between special symbols and their surrounding characters

這4類復(fù)雜結(jié)構(gòu)加上上下標(biāo)結(jié)構(gòu)構(gòu)成了數(shù)學(xué)公式中需要結(jié)構(gòu)解析的主要部分.針對這幾類復(fù)雜結(jié)構(gòu)，本文提出各自的解析算法.

以下算法是整體結(jié)構(gòu)的解析算法，用于判斷對某結(jié)構(gòu)使用什么具體的解析算法.

輸入：一個字符塊的單字符識別列表[P1,P2,…,Pi,…,Pn].

輸出：識別結(jié)果result.

步驟1循環(huán)遍歷[P1,P2,…,Pi,…,Pn]，若字符Ci的識別結(jié)果Pi為根號、分號、積分號、求和號，執(zhí)行相應(yīng)解析規(guī)則，得到解析結(jié)果r，并放入結(jié)果result中.執(zhí)行步驟2.

步驟2遍歷檢查列表中未被解析的剩余字符.若列表中剩余字符無4類特殊符號，則解析完畢，執(zhí)行步驟3；否則，執(zhí)行步驟1.

步驟3返回識別結(jié)果result.

4.1 根式解析算法

根據(jù)根號與其底數(shù)構(gòu)成半包圍、與其指數(shù)構(gòu)成左上右下的空間位置關(guān)系，提出根式解析算法解析步驟.

輸入：Pi被識別為根號的單字符識別列表[P1,P2,…,Pi,…,Pn].

輸出：識別結(jié)果result.

步驟1判斷根號Pi前是否存在其他字符.若Pi前存在其他字符，則執(zhí)行步驟2;否則，該根式的根指數(shù)為2，根指數(shù)字符串n默認(rèn)為空，執(zhí)行步驟3.

步驟2對Pi前的字符進行篩選，根據(jù)根指數(shù)分布在根號左上角的位置和根指數(shù)字符串的大小小于根號的大小這2個特點，得到根指數(shù)字符列表[P1,P2,…,Ps]，其中s≤i-1.然后遞歸地解析根指數(shù)字符列表，得到根指數(shù)字符串n.執(zhí)行步驟3.

步驟3對Pi后面的字符進行篩選，根據(jù)根底數(shù)在根號半包圍結(jié)構(gòu)中的特點，得到根底數(shù)字符列表[P1,P2,…,Pt]，其中t≤n-i，對根底數(shù)字符列表遞歸解析，得到根底數(shù)字符串a(chǎn).執(zhí)行步驟4.

步驟4合并根號、根指數(shù)n和根底數(shù)a這三部分，result=[sqrt,a,n].執(zhí)行步驟5.

步驟5返回識別結(jié)果result.

4.2 分式解析算法

由分子、分母分別位于分號正上方、正下方的空間位置關(guān)系，可提出以下解析步驟：

步驟1首先對單字符識別列表進行循環(huán)篩選，根據(jù)分子、分母與分號的位置關(guān)系分別得到分子字符列表[P1,P2,…,Ps]和分母字符列表[P1,P2,…,Pt]，其中s+t≤n-1.

步驟2分別遞歸地解析2個列表，得到分子字符串a(chǎn)和分母字符串b.

步驟3合并得到解析結(jié)果[/,a,b].

4.3 積分解析算法

根據(jù)積分號與上、下底數(shù)構(gòu)成左下右上和左上右下的空間位置關(guān)系，提出以下解析步驟：

步驟1遍歷積分號Pi后所有字符，篩選得到區(qū)間下界字符列表[P1,P2,…,Ps]和區(qū)間上界字符列表[P1,P2,…,Pt]，其中s+t≤n-1.

步驟2若積分號Pi沒有積分區(qū)間，則區(qū)間上界字符串a(chǎn)和區(qū)間下界字符串b皆為空；否則遞歸解析區(qū)間下界字符列表和區(qū)間上界字符列表，得到解析后的結(jié)果a和b.

步驟3合并得到最終解析結(jié)果[int,a,b].

4.4 求和解析算法

由求和上標(biāo)、下標(biāo)分別位于求和號正上方、正下方的空間特點，可提出以下解析步驟.

步驟1遍歷求和號后所有字符，篩選得到下標(biāo)字符列表[P1,P2,…,Ps]和上標(biāo)字符列表[P1,P2,…,Pt]，其中s+t≤n-1，上下標(biāo)的篩選標(biāo)準(zhǔn)是：下標(biāo)字符位于求和號的正下角，上標(biāo)則位于求和號的正上方，同時上下標(biāo)字符的大小都小于求和號的大小.

步驟2篩選完畢后，若該求和號沒有上下標(biāo)，則上標(biāo)字符串a(chǎn)和下標(biāo)字符串b皆為空，否則遞歸解析上下標(biāo)字符列表，得到解析后的結(jié)果a和b.

步驟3合并得到最終解析結(jié)果[sum,a,b].

4.5 整體公式識別

對于沒有特殊結(jié)構(gòu)的數(shù)學(xué)公式，可以按照從左到右的順序?qū)巫址淖R別結(jié)果進行直接合并.如圖19中的普通數(shù)學(xué)公式，經(jīng)過前面一系列步驟得到單個字符的識別結(jié)果[’2’，’a’，’×’，’3’，’b’，’=’，’4’，’c’]，接下來直接合并得到最終識別結(jié)果字符串“2a×3b=4c”.

圖19 普通公式Fig.19 Regular formula

而對于含有特殊結(jié)構(gòu)的算式，先使用前幾小節(jié)中的解析規(guī)則對結(jié)構(gòu)進行解析，將復(fù)雜算式結(jié)構(gòu)解析完畢后，再將整體進行合并.若公式較為復(fù)雜，包含多個嵌套特殊結(jié)構(gòu)，則使用樹形結(jié)構(gòu)來遞歸地進行解析，見圖20.首先根據(jù)垂直投影將公式切分成若干子圖，再依次對子圖進行解析：若當(dāng)前子圖中沒有特殊結(jié)構(gòu)，則直接合并單字符形成識別結(jié)果；否則根據(jù)各個特殊結(jié)構(gòu)的特點，解析成特定的形式，若其中仍存在特殊結(jié)構(gòu)，則繼續(xù)遞歸地往下解析，直到所有的特殊結(jié)構(gòu)都解析完畢，最后從下往上合并，形成公式的識別結(jié)果.

圖20 復(fù)雜公式解析樹Fig.20 Parse tree of complex formula

5 實驗結(jié)果與分析

本文測試數(shù)據(jù)根據(jù)來源分為4類：第1類采自中學(xué)學(xué)生答卷中真實的手寫數(shù)學(xué)公式圖片，第2類為實驗室課題組師生手寫的公式，第3類為CROHME2019離線數(shù)學(xué)公式數(shù)據(jù)集[16]中包含有根號、分號、積分號和求和號的公式圖片，第4類為NIST19手寫字符串?dāng)?shù)據(jù)集中的部分普通文本粘連數(shù)據(jù).下文中統(tǒng)一以簡寫學(xué)生數(shù)據(jù)、實驗室數(shù)據(jù)、CROHME2019數(shù)據(jù)和NIST19數(shù)據(jù)來分別指代這4類手寫數(shù)據(jù).表4中給出了各類數(shù)據(jù)的數(shù)量，其中普通粘連字符的含義是指僅由數(shù)字、英文或普通數(shù)學(xué)符號構(gòu)成的粘連字符，特殊粘連的字符是指粘連部分包含分號、根號、積分號或求和號這4類數(shù)學(xué)特殊符號的粘連字符.

表4 測試數(shù)據(jù)Table 4 Test data

部分測試圖片見圖21，其中(a)為學(xué)生書寫的數(shù)學(xué)公式圖片，(b)為實驗室課題組師生手寫的數(shù)學(xué)公式，(c)為CROHME2019離線數(shù)學(xué)公式數(shù)據(jù)集中的公式圖片，(d)為NIST19手寫字符串?dāng)?shù)據(jù)集中的粘連字符串圖片.

圖21 部分測試數(shù)據(jù)Fig.21 Sometest data

本文設(shè)計了2組實驗，一組驗證本文輪廓雙側(cè)檢測切分算法的裁切效果，另一組驗證添加該算法后公式整體的識別效果.本文引入了切分正確率(CR)、公式識別率(RR)、公式第二識別率(SRR)[17]和運算時間4個評價指標(biāo)來作為評判標(biāo)準(zhǔn)，部分?jǐn)?shù)學(xué)定義為

(4)

(5)

(6)

式中：CN表示正確切分的粘連符號個數(shù)；WN表示粘連符號的總數(shù);RN表示完全識別正確的公式個數(shù)；SRN表示最多只有一個字符被識別錯誤的公式個數(shù)；AN表示公式總數(shù).由定義可知，CR越大，粘連字符被正確裁切的比例越高，裁切算法的裁切效果越好；RR、SRR越大，整體公式被正確識別的比例越高，公式整體識別的效果越好.

5.1 輪廓雙側(cè)檢測切分算法的裁切效果實驗

本組實驗中，將本文提出的裁切方法與滴水分割算法[18]、垂直投影切分算法[19]及基于馬爾可夫隨機場的切分算法[20]分別進行了對比，實驗結(jié)果見表5、6.表5中，數(shù)據(jù)1、2、3分別指代學(xué)生數(shù)據(jù)、實驗室數(shù)據(jù)和CROHME2019數(shù)據(jù)中的全體粘連字符.CR表示切分正確率，定義如式(4)所示.表6中，測試數(shù)據(jù)為NIST19手寫字符串?dāng)?shù)據(jù)集中的普通粘連字符.

表5 數(shù)學(xué)粘連字符切分對比實驗Table 5 Segmentation contrast experiment of mathematical touching characters

表6 NIST19粘連字符切分對比實驗Table 6 Segmentation contrast experiment of NIST19 touching characters

從表5可以看出，滴水分割算法對公式的切分效果好于垂直投影算法.而本文算法由于考慮了公式中特殊字符的特征，效果明顯優(yōu)于前2種算法.對表5中的3類數(shù)據(jù)結(jié)果進行縱向?qū)Ρ?，實驗室?guī)熒鷶?shù)據(jù)的切分正確率最高，中學(xué)生數(shù)據(jù)次之，CROHME數(shù)據(jù)最低，印證了切分效果的優(yōu)劣與數(shù)據(jù)本身的潦草、粘連程度相關(guān)性大.

對普通粘連字符的處理，本文輪廓雙側(cè)檢測切分算法實際是滴水分割算法的延續(xù)，文獻[20]中的基于馬爾可夫隨機場的切分算法，其適用范圍也是不含特殊公式符號的普通字符串.因此，將本文算法與文獻[20]中的普通粘連字符串裁切效果進行對比實驗，由表6可知效果基本一致.

在切分速度方面，本文算法對于單個數(shù)學(xué)粘連符號和普通粘連符號的平均切分耗時見表5、6最后一列，分別為5.8、4.9 ms左右，遠(yuǎn)小于馬爾可夫隨機場切分算法耗時，比滴水分割算法稍慢，證明了本文算法的效率.

5.2 公式識別效果實驗

第2組實驗是對手寫數(shù)學(xué)公式的整體識別率實驗.分別在學(xué)生數(shù)據(jù)、實驗室數(shù)據(jù)和CROHME2019數(shù)據(jù)上進行，從第一識別率(RR)，第二識別率(SRR)及識別時間上，驗證本文所提手寫公式識別方法的有效性.部分公式的識別效果如圖22所示，實驗整體結(jié)果如表7、8所示.

圖22 數(shù)學(xué)公式識別結(jié)果Fig.22 Recognition results of mathematical formula

表7 公式整體識別實驗Table 7 Formula recognition experiment

由表7可知，在公式整體的識別率上，本文手寫公式識別策略對中學(xué)生數(shù)據(jù)和實驗室?guī)熒鷶?shù)據(jù)整體識別正確率較高.在允許1個字符被誤識的條件下，識別率分別達到90.4%和94.1%.單個公式的識別平均時間82.5 ms，對于一張包含20個公式的圖片的識別時間在1.6 s左右，處于可接受的范圍.但對于CROHME2019公式數(shù)據(jù)集，本文手寫公式識別策略不是很理想，整體公式的第一識別率和第二識別率分別為58.1%和63.1%.與參加CROHME2019脫機數(shù)學(xué)公式識別競賽[17]相比，前面還有幾支隊伍成績較好，本文整體公式識別率位于中下游，如表8所示.分析原因，本文方法重點考慮對特殊數(shù)學(xué)符號的正確切分和特殊符號識別率的提高，而忽視了模型對其他普通單個字符識別率的提升，因此，公式中任何一個字符的識別錯誤，都會導(dǎo)致整體公式的識別錯誤.數(shù)據(jù)集方面，本文一直采用在校中小學(xué)學(xué)生的手寫數(shù)據(jù)進行實驗，沒有針對CROHME2019數(shù)據(jù)集進行研究，而CROHME2019中的單個字符書寫方式與學(xué)生手寫數(shù)據(jù)差別很大，也降低了整體公式的識別率.

表8 CROHME2019競賽結(jié)果對比Table 8 Comparison of CROHME2019 results

6 結(jié)論

1)實驗表明，本文的輪廓雙側(cè)檢測切分方法可以有效切分具有復(fù)雜二維空間結(jié)構(gòu)的粘連符號，彌補了傳統(tǒng)裁切方法的不足.根據(jù)特殊符號與普通符號形態(tài)上的差別，并采用多特征相融合的方式，可有效實現(xiàn)特殊符號的正確判別.根據(jù)特殊符號與周圍字符的空間位置關(guān)系，可得到整體公式結(jié)構(gòu)的解析結(jié)果，實現(xiàn)數(shù)學(xué)公式的自動識別.

2)針對整體公式在CROHME2019數(shù)據(jù)集上識別率不高的問題，本文通過改進模型，提高了對CROHME2019數(shù)據(jù)集中部分普通單字符的識別率，效果比較明顯，公式整體識別率也得到提升，但受限于算力，沒有做完整的實驗.后期實驗可在繼續(xù)優(yōu)化識別特殊公式符號的基礎(chǔ)上，做單個字符的識別率的提升，從而提升公式的整體識別率.