科技文檔中數學表達式的結構分析與識別

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

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

關鍵詞：數學表達式；識別；基準線；識別率

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

0 引 言

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

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

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

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

1 字符分割

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

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

2 結構分析

在進行結構分析之前，先介紹一些相關概念：

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

①輸入屬性：字符的身份及邊框屬性；

②附加屬性：不同數學表達式符號的類型，各符號的質心所屬種類，數學符號的質心所處位置。

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

（3）基準線結構樹（BST）。以BST為工具解析數學表達式的空間位置關系。

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

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

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

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

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

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

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

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

需要說明的是，極限、矩陣等相關數學表達式其結構相對更加復雜，經常需要在常規(guī)方法的基礎上加以引申，使用更加符合其結構特征的結構分析方法提高識別率。

此外，由于脫機表達式的結構是固定的，不像聯機數學表達式那樣能夠進行調整，便于結構分析，故需要對上述算法作出以下調整：

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

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

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

3 實驗結果和識別率計算

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

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

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

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

4 結 語

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

參考文獻

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

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

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

[4]徐曉蓉.印刷體數學表達式識別系統的設計與實現[D].桂林：廣西師范大學，2005.

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

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

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

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

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

[10]田學東，吳麗紅，趙蕾蕾，等.基于多特征模糊模式識別的公式符號關系判定[J].計算機工程與應用，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.