科技文檔中數(shù)學(xué)表達(dá)式的結(jié)構(gòu)分析與識(shí)別

徐曉宇++宗亞輝++胡欣宇

摘 要：與科學(xué)技術(shù)相關(guān)的文檔中，針對(duì)數(shù)學(xué)表達(dá)式的識(shí)別通常可分為字符的分割與結(jié)構(gòu)的識(shí)別。文章在這一框架下討論了數(shù)學(xué)表達(dá)式的識(shí)別，尤其是在表達(dá)式結(jié)構(gòu)的分析上，采用了優(yōu)化的基準(zhǔn)線結(jié)構(gòu)分析方法。實(shí)驗(yàn)結(jié)果表明，采用上述方法后，數(shù)學(xué)表達(dá)式的識(shí)別率得到了顯著提高。

關(guān)鍵詞：數(shù)學(xué)表達(dá)式；識(shí)別；基準(zhǔn)線；識(shí)別率

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2016）11-00-03

0 引 言

數(shù)學(xué)作為自然科學(xué)的通用語(yǔ)言，在科技的發(fā)展中有著舉足輕重的地位。而數(shù)學(xué)表達(dá)式作為重要的數(shù)學(xué)載體，在科學(xué)技術(shù)相關(guān)文檔中有著廣泛的應(yīng)用。光學(xué)字符識(shí)別（Optical Character Recognition，OCR）系統(tǒng)能夠高效準(zhǔn)確地識(shí)別文檔中的文字，但對(duì)數(shù)學(xué)表達(dá)式卻一直無(wú)法取得較高的識(shí)別率[1]。與普通的文字相比，數(shù)學(xué)表達(dá)式在字符和結(jié)構(gòu)等方面都具有其特殊性[2]。為了能夠更加快捷方便地共享科技文檔等信息，對(duì)數(shù)學(xué)表達(dá)式識(shí)別技術(shù)的研究就變得非常重要。

數(shù)學(xué)表達(dá)式識(shí)別的本質(zhì)是從圖片格式的數(shù)學(xué)表達(dá)式得出其空間結(jié)構(gòu)與邏輯含義。在實(shí)際處理的文檔圖像中，除數(shù)學(xué)表達(dá)式外，還有文本與圖表等，因而表達(dá)式處理的第一步通常是表達(dá)式位置的定位[3-5]。將定位好的表達(dá)式中所包含的所有符號(hào)進(jìn)行切割，并根據(jù)符號(hào)庫(kù)進(jìn)行相應(yīng)的識(shí)別。識(shí)別符號(hào)之后，需研究符號(hào)間的空間關(guān)系及對(duì)應(yīng)的邏輯含義[6，7]。最后將分析結(jié)果按照一定的格式輸出，達(dá)到復(fù)用和易于傳輸?shù)哪康腫8]。

國(guó)際上對(duì)數(shù)學(xué)表達(dá)式的識(shí)別研究始于20世紀(jì)60年代，但直到90年代，相關(guān)研究才越來(lái)越受重視?；仡櫼延械慕Y(jié)構(gòu)分析方法，所謂的數(shù)學(xué)表達(dá)式結(jié)構(gòu)分析法是指依據(jù)字符含義、字符大小及空間位置等信息從整體上確定各字符間的位置關(guān)系，相應(yīng)得出數(shù)學(xué)表達(dá)式的結(jié)構(gòu)信息。在最初階段，Anderson提出使用自上而下的結(jié)構(gòu)分析方法，但這種方法略顯粗糙，只能識(shí)別一些簡(jiǎn)單的數(shù)學(xué)表達(dá)式。Lee提出了關(guān)系樹結(jié)構(gòu)分析方法和矩陣分析方法，Lee的方法能夠處理很多稍顯復(fù)雜的單行數(shù)學(xué)表達(dá)式，但對(duì)結(jié)構(gòu)更加復(fù)雜的多行表達(dá)式識(shí)別效果并不好[9]。Okamoto在總結(jié)已有研究成果的基礎(chǔ)上，綜合運(yùn)用自頂向下和自底向上這兩種常用的方法，針對(duì)字符間的水平及垂直方向的位置關(guān)系，統(tǒng)一使用自頂向下的策略，從而將表達(dá)式劃分成多個(gè)子表達(dá)式。對(duì)于略顯復(fù)雜的上下標(biāo)、包含等關(guān)系，則采用自底向上的分析方法[10]。Okamoto的分析方法取得了較為滿意的識(shí)別率，但對(duì)矩陣等特殊類型結(jié)構(gòu)的識(shí)別上，仍然無(wú)法得到滿意的識(shí)別率。Ha提出使用具有一定層次結(jié)構(gòu)的表達(dá)式樹，通常使用表達(dá)式樹的節(jié)點(diǎn)表示對(duì)象。在更進(jìn)一步的劃分中，規(guī)定整體的表達(dá)式使用根部節(jié)點(diǎn)代表，而簡(jiǎn)單對(duì)象和復(fù)合對(duì)象分別使用葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)表示[11]。Fukuda提出以數(shù)學(xué)元件代表各個(gè)符號(hào)，并詳細(xì)說(shuō)明了所有元件的空間關(guān)系，之后按照位置關(guān)系判定表達(dá)式的結(jié)構(gòu)。Winkler使用有向圖描述數(shù)學(xué)表達(dá)式，字符以節(jié)點(diǎn)表示，字符間的關(guān)系則用Yuko，使用網(wǎng)絡(luò)圖表示數(shù)學(xué)表達(dá)式，使用相關(guān)的數(shù)學(xué)方法計(jì)算出符合條件的生成樹，以其來(lái)代表數(shù)學(xué)表達(dá)式的空間分析結(jié)果[12]。該方法受個(gè)別字符識(shí)別錯(cuò)誤的影響不大，且局部識(shí)別錯(cuò)誤對(duì)整體的正確率影響不大。Dimitriadis規(guī)定了句法和語(yǔ)義準(zhǔn)則，將空間位置關(guān)系比較繁雜的表達(dá)式依據(jù)語(yǔ)義準(zhǔn)則劃分為簡(jiǎn)潔的式子，而具體各組成單元間的簡(jiǎn)單關(guān)系則依據(jù)句法準(zhǔn)則分析[13]。Zanibbi和Blostein采用基準(zhǔn)線對(duì)數(shù)學(xué)表達(dá)式進(jìn)行結(jié)構(gòu)分析，通過(guò)創(chuàng)建基準(zhǔn)線結(jié)構(gòu)樹（Baseline Structure Tree， BST）描述數(shù)學(xué)表達(dá)式的結(jié)構(gòu)[14]。這種方法能夠克服諸如方言等特殊符號(hào)的限制，提高了結(jié)構(gòu)分析的準(zhǔn)確率。

本文在借鑒上述文獻(xiàn)所提方法的基礎(chǔ)上，對(duì)基準(zhǔn)線結(jié)構(gòu)法作了優(yōu)化。本文所用的基線結(jié)構(gòu)分析法中，采用過(guò)分割方法對(duì)數(shù)學(xué)表達(dá)式的字符進(jìn)行分割，使用字符比較、特征點(diǎn)提取等手段完成對(duì)數(shù)學(xué)符號(hào)的識(shí)別；而在對(duì)數(shù)學(xué)表達(dá)式的結(jié)構(gòu)進(jìn)行解析時(shí)，采用基準(zhǔn)線結(jié)構(gòu)分析方法。完成字符識(shí)別和結(jié)構(gòu)解析后，以Latex的形式輸出最終的數(shù)學(xué)表達(dá)式解析結(jié)果。

1 字符分割

在字符分割這一階段，通過(guò)一定的數(shù)字圖像處理技術(shù)，將整體的數(shù)學(xué)表達(dá)式切分成多個(gè)字符塊，然后進(jìn)一步切分為獨(dú)立的單一字符。分割作為后續(xù)工作的基礎(chǔ)，必須進(jìn)行正確的分割才能保證之后的識(shí)別具有較高的有效性。比較常見的數(shù)學(xué)表達(dá)式符號(hào)切割方法有投影分割法及連通域分割法。但由于數(shù)學(xué)表達(dá)式自身的特殊性，這些常規(guī)的切割方法應(yīng)用于數(shù)學(xué)表達(dá)式時(shí)，識(shí)別率一般會(huì)降低。為了取得更高的識(shí)別率，常常先通過(guò)連通域分割法進(jìn)行初步分割，提取特殊的包圍結(jié)構(gòu)類型的字符，然后通過(guò)投影分割法切割出更多的字符塊。

此外還需分析解決常見的字符粘連，即由于某些字符聚集程度稍大，需要進(jìn)行再分割。對(duì)數(shù)學(xué)表達(dá)式符號(hào)作再分割處理時(shí)，常選用投影法，并以投影圖的波谷作為分割依據(jù)。在通常情況下，波谷不止一個(gè)，若要從中選擇正確的分割點(diǎn)，則應(yīng)通過(guò)可信度對(duì)各種分割組合進(jìn)行排序，并選擇可信度較高的分割方案作為最后的分割結(jié)果。但是需要注意的是，數(shù)學(xué)表達(dá)式中的=、÷、<<、>>、i等字符是一個(gè)整體，不能被進(jìn)一步分割。假如這種類型的符號(hào)在過(guò)分割切斷被切割，則需進(jìn)行復(fù)合。首先確定各被分割部分所處的位置，然后將它們重新合并，構(gòu)成新的正確的識(shí)別結(jié)果。

2 結(jié)構(gòu)分析

在進(jìn)行結(jié)構(gòu)分析之前，先介紹一些相關(guān)概念：

（1）字符屬性。每個(gè)需要處理的字符應(yīng)有以下屬性：

①輸入屬性：字符的身份及邊框?qū)傩裕?/p>

②附加屬性：不同數(shù)學(xué)表達(dá)式符號(hào)的類型，各符號(hào)的質(zhì)心所屬種類，數(shù)學(xué)符號(hào)的質(zhì)心所處位置。

（2）域。文字節(jié)點(diǎn)的域指嵌套基準(zhǔn)線的類型，有Above，Below，Super，Subsc，Tleft，Bleft，Hor共7種，其定義如圖1所示。

（3）基準(zhǔn)線結(jié)構(gòu)樹（BST）。以BST為工具解析數(shù)學(xué)表達(dá)式的空間位置關(guān)系。

在基本的結(jié)構(gòu)樹中，比較常見的有文字節(jié)點(diǎn)和域節(jié)點(diǎn)。文字節(jié)點(diǎn)通常作為數(shù)學(xué)表達(dá)式中的基準(zhǔn)線，以便于數(shù)學(xué)表達(dá)式的結(jié)構(gòu)分析。這兩種類型的節(jié)點(diǎn)按照相關(guān)層次結(jié)構(gòu)交替排列。

為了能夠更加高效方便地解析數(shù)學(xué)表達(dá)式的結(jié)構(gòu)，需要提前對(duì)數(shù)學(xué)表達(dá)式的結(jié)構(gòu)進(jìn)行預(yù)處理。在此過(guò)程中，某些諸如sin、cos之類的數(shù)學(xué)公式符號(hào)需要合并；如果存在某些明顯的語(yǔ)法類錯(cuò)誤，都需要在預(yù)處理過(guò)程中進(jìn)行糾正。常見的函數(shù)型字符有三角函數(shù)（如sin（），tan（）），數(shù)值函數(shù)（如abs（）），邏輯符號(hào)（如if，and，or）。在進(jìn)行數(shù)學(xué)表達(dá)式的預(yù)處理時(shí)，必須將這些邏輯上為統(tǒng)一整體的符號(hào)有效整合，并將對(duì)應(yīng)的特征屬性等進(jìn)行相應(yīng)更正。更正之后表達(dá)式中的組成成分更加清晰，在對(duì)表達(dá)式結(jié)構(gòu)進(jìn)行解析時(shí)能夠更加高效快捷。如圖2所示，表達(dá)式中的“min”在進(jìn)行過(guò)分割之后，若不整合，簡(jiǎn)單的解析會(huì)使得其下的“2”被遺漏，造成分析失敗。

在對(duì)空間操作進(jìn)行處理時(shí)，需按照鄰近的符號(hào)間特征屬性和空間位置分析。如果確實(shí)存在，則需增添相應(yīng)的操作符，從而有效提高對(duì)數(shù)學(xué)表達(dá)式的空間結(jié)構(gòu)和邏輯含義的分析。如果缺少匹配字符，則加入相應(yīng)的替代符，以順利分析表達(dá)式的結(jié)構(gòu)。操作碼的誤識(shí)可根據(jù)前后字符的關(guān)系加以分析，如可得出數(shù)學(xué)表達(dá)式字符的特征屬性，即可認(rèn)定改正是準(zhǔn)確的；否則要用相應(yīng)的標(biāo)志符替代。結(jié)構(gòu)分析預(yù)處理之后就是正式的數(shù)學(xué)表達(dá)式結(jié)構(gòu)解析，其目標(biāo)是針對(duì)解析識(shí)別的結(jié)果得到一顆結(jié)構(gòu)樹。本文采用基準(zhǔn)線結(jié)構(gòu)方法，其過(guò)程如圖3所示。

輸入為以字符特征屬性所表示的字符串，除此之外，還需添加使用邊框代表的相應(yīng)空間位置，這些信息在數(shù)學(xué)表達(dá)式的結(jié)構(gòu)分析與識(shí)別中具有無(wú)可替代的重要作用。最終的分析識(shí)別結(jié)果則按照結(jié)構(gòu)樹的格式輸出，另外一種常見的輸出格式為L(zhǎng)atex?；鶞?zhǔn)線結(jié)構(gòu)法的大致過(guò)程如下所示：

（1）采用SF（）表示搜索算法，根據(jù)這種算法確定數(shù)學(xué)公式的起始字符。

（2）采用SFP（）表示另外一個(gè)搜索算法，根據(jù)此算法確定主基準(zhǔn)線的確切位置。

（3）針對(duì)每個(gè)字符的域內(nèi)，使用搜索函數(shù)SFS（）搜索得到次基準(zhǔn)線的開始字符。

（4）使用搜索函數(shù)SFP（）求得次基準(zhǔn)線，按照這樣的步驟循環(huán)，得到整個(gè)數(shù)學(xué)表達(dá)式的結(jié)構(gòu)樹。

需要說(shuō)明的是，極限、矩陣等相關(guān)數(shù)學(xué)表達(dá)式其結(jié)構(gòu)相對(duì)更加復(fù)雜，經(jīng)常需要在常規(guī)方法的基礎(chǔ)上加以引申，使用更加符合其結(jié)構(gòu)特征的結(jié)構(gòu)分析方法提高識(shí)別率。

此外，由于脫機(jī)表達(dá)式的結(jié)構(gòu)是固定的，不像聯(lián)機(jī)數(shù)學(xué)表達(dá)式那樣能夠進(jìn)行調(diào)整，便于結(jié)構(gòu)分析，故需要對(duì)上述算法作出以下調(diào)整：

（1）SFP（）函數(shù)域值的選用：閾值選用通常由字符的高度來(lái)決定，其選用非常寬松，但假設(shè)字符是“-”或“=”，比較小，除了要選用規(guī)定的最小閾值外，還要按照鄰接字符的尺寸大小得出閾值。靈活選用閾值可以更準(zhǔn)確的分析結(jié)果。

（2）域值界限的定義：通常情況下，在某些脫機(jī)公式中，數(shù)學(xué)表達(dá)式符號(hào)之間的關(guān)系有時(shí)是模糊的，即個(gè)別符號(hào)無(wú)法準(zhǔn)確說(shuō)明其所在的空間域或算法中出現(xiàn)疊加的域，Subsc延長(zhǎng)到Upper Threshold，Super延長(zhǎng)到Lower Threshold，Above延長(zhǎng)到RightWall。為了減少如上重疊造成的多識(shí)，可以通過(guò)分析Super（Subsc）完成。

（3）域的合并：為了有利于表示和輸出，常將帶有Bleft與Tleft域的Limits字符與Super、Subsc合并，從而使結(jié)構(gòu)描述更加真實(shí)。

3 實(shí)驗(yàn)結(jié)果和識(shí)別率計(jì)算

通過(guò)采用本文所屬的字符識(shí)別和結(jié)構(gòu)分析方法，能夠有效識(shí)別數(shù)學(xué)表達(dá)式，識(shí)別率比較高。表達(dá)式識(shí)別結(jié)果如圖4所示，上方是圖片格式的數(shù)學(xué)表達(dá)式，下方為識(shí)別結(jié)果。

對(duì)于某些結(jié)構(gòu)不清晰的表達(dá)式，識(shí)別效果并不太好，表達(dá)式識(shí)別失敗示例如圖5所示。由于“-”和“∫”的空間關(guān)系不清晰，所以沒有被識(shí)別，而這些問題需要在后續(xù)算法中進(jìn)一步優(yōu)化和改進(jìn)。

根據(jù)上述理論，本文分別從雜志和書本上選擇了一些數(shù)學(xué)公式，并用如圖6所示的三個(gè)指標(biāo)作為識(shí)別結(jié)果的判斷標(biāo)準(zhǔn)。

最終的識(shí)別結(jié)果如表1所列，分析可知，采用基準(zhǔn)線法可使數(shù)學(xué)表達(dá)式的分析與識(shí)別能夠得到較高的正確率，得到相對(duì)滿意的結(jié)果。

4 結(jié) 語(yǔ)

針對(duì)數(shù)學(xué)表達(dá)式結(jié)構(gòu)的分析，本文提出了優(yōu)化的基準(zhǔn)線結(jié)構(gòu)算法，能夠很好地識(shí)別結(jié)構(gòu)較為復(fù)雜的數(shù)學(xué)表達(dá)式。由實(shí)驗(yàn)可知，本文所用方法具有較高的識(shí)別率。但數(shù)學(xué)表達(dá)式自身的二維結(jié)構(gòu)決定了對(duì)其進(jìn)行結(jié)構(gòu)分析時(shí)還會(huì)面臨很多難題，還需對(duì)其存在的諸多問題進(jìn)行更深入的研究。例如某些操作符的空間結(jié)構(gòu)比較復(fù)雜，僅通過(guò)位置關(guān)系很難分析，應(yīng)根據(jù)上下文語(yǔ)義加以分析。另一個(gè)值得關(guān)注的問題即為數(shù)學(xué)符號(hào)本身的二義性，要解決該問題，只能結(jié)合上下文的語(yǔ)義信息進(jìn)行辨別。針對(duì)這些問題，在后續(xù)的研究中將嘗試通過(guò)建立語(yǔ)法規(guī)則、引入機(jī)器學(xué)習(xí)等以完善數(shù)學(xué)表達(dá)式的識(shí)別。

參考文獻(xiàn)

[1]趙學(xué)軍.手寫數(shù)學(xué)表達(dá)式自動(dòng)識(shí)別的研究[D].重慶：重慶大學(xué)，1998.

[2]張建成，洪留榮.聯(lián)機(jī)手寫數(shù)學(xué)表達(dá)式識(shí)別方法綜述[J].淮北師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，29（3）：40-47.

[3]王科俊，林桂芳，王黎斌，等.數(shù)學(xué)表達(dá)式識(shí)別方法綜述[J].自動(dòng)化技術(shù)與應(yīng)用，2003，22（8）：1-6.

[4]徐曉蓉.印刷體數(shù)學(xué)表達(dá)式識(shí)別系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].桂林：廣西師范大學(xué)，2005.

[5]陳洪波，王強(qiáng)，徐曉蓉，等.數(shù)學(xué)表達(dá)式的自動(dòng)識(shí)別[J].廣西科學(xué)，2004，11（1）：20-26.

[6]李峰，吳微.英文科技文檔識(shí)別中數(shù)學(xué)公式定位新方法[J].大連理工大學(xué)學(xué)報(bào)，2009，49（1）：139-143.

[7]宋昭，李芬.基于專家系統(tǒng)的公式識(shí)別器的實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2005，31（13）：38-39，136.

[8]張志偉，孔凡讓，劉維來(lái)，等.中文科技文檔中的數(shù)學(xué)表達(dá)式定位[J].中文信息學(xué)報(bào)，2007，21（4）：86-91.

[9]李中付，華宏星，宋漢文，等.模態(tài)分解法辨識(shí)線性結(jié)構(gòu)在環(huán)境激勵(lì)下的模態(tài)參數(shù)[J].上海交通大學(xué)學(xué)報(bào)，2001，35（12）：1761-1765.

[10]田學(xué)東，吳麗紅，趙蕾蕾，等.基于多特征模糊模式識(shí)別的公式符號(hào)關(guān)系判定[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（5）：186-188.

[11]Chan K F， Yeung D Y. Error detection， error correction and performance evaluation in on-line mathematical expression recognition[J]. Pattern Recognition， 2001， 34（8）： 1671-1684.

[12]Chan K F， Yeung D Y. Mathematical expression recognition：a survey[J]. International Journal on Document Analysis and Recognition， 2000， 3（1）： 3-15.

[13]Awal A M， Mouchere H， Viard-Gaudin C. Towards handwritten mathematical expression recognition[C]. 2009 10th International Conference on Document Analysis and Recognition. IEEE， 2009： 1046-1050.

[14] Lee H J， Lee M C. Understanding mathematical expressions in a printed document[C]. Document Analysis and Recognition， 1993， Proceedings of the Second International Conference on. IEEE， 1993： 502-505.