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

摘 要：與科學(xué)技術(shù)相關(guān)的文檔中，針對數(shù)學(xué)表達式的識別通?？煞譃樽址姆指钆c結(jié)構(gòu)的識別。文章在這一框架下討論了數(shù)學(xué)表達式的識別，尤其是在表達式結(jié)構(gòu)的分析上，采用了優(yōu)化的基準線結(jié)構(gòu)分析方法。實驗結(jié)果表明，采用上述方法后，數(shù)學(xué)表達式的識別率得到了顯著提高。

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

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2016）11-00-03

0 引 言

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

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

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

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

1 字符分割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果和識別率計算

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

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

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

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

4 結(jié) 語

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

參考文獻

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

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

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

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

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

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

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

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

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

[10]田學(xué)東，吳麗紅，趙蕾蕾，等.基于多特征模糊模式識別的公式符號關(guān)系判定[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.