（模式識別與智能系統(tǒng)專業(yè)論文）數(shù)學公式圖像識別的自動性能評估.pdf

摘要 數(shù)學公式圖像讓 別是個具有相當難度的前沿課題，許多處理方法都還在探索和嘗試 中。為了小斷改進各種處理方法，提高公式識別系統(tǒng)的整體性能，需要對公式識別的各個 階段以及整體進行自動的測試和性能評估。然而有關性能評估的研究相當少，在本文開始 研究之前，尚沒有對大規(guī)模圖像進行性能評估的實驗結果，這嚴重阻礙了數(shù)學公式識別研 究的進一步發(fā)展。 本文根據(jù)數(shù)學公式本身的二維特性，首次提出采用帶邊屬性的三叉樹結構來表示數(shù)學 公式的以別結果，并首次提出兩科l 基于樹匹配算法( 動態(tài)規(guī)劃算法和b u t d 算法) 的公式 識別自動性能評估方法。其中基于b u t d 算法的性能評估方法是目前唯一能夠發(fā)現(xiàn)公式符 號切割、識別以及公式分析中產生的任意錯誤的評估方法。 關鍵詞 數(shù)學公式圖像識別數(shù)學公式分析自動性能評估 a b s t r a c t t h e1 _ e c o g n i t i o no fm a t h e m a t i c a le x p r e s s i o ni m a g ei sad i f f i c u l ts u b j e c t m a n yr e c o g n i t i o n m e t h o d sa r es t j l it e n t a t i v ei no r d e rt o i m p r o v e t h e s em e t h o d sa n de n h a n c et h e s y s t e m p e r f o r m a n c e ，i t 1 s n e c e s s a r yt oe v a l u a t et h ep e r f o r m a n c eo ft h ee n t i r er e c o g n i t i o ns y s t e m b u t a l s ot h e p m 。f o r m a n c e o fe a c h p h a s e h o w e v e r ，t h er e s e a r c h o n p e r f o r m a n c ee v a l u a t i o n o f m a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o ni s v e r ys c a r c e b e ：f o r eo u rw o r k ，t h e t ei sn or e p o r ta b o u t p e r f o r m a n c e e v a l u a t i o ni na l a r g ev a r i e t y o fi m a g e s ，w h i c hh a s p r e v e n t e dt h ea d v a n c eo f m a t h e m a t i c a le x p r e s s i o nr e c o g n i t i o n ， b e c a u s eo ft h et w o d i m e n s i o n a lf o r m a t t i n go fm a t h e m a t i c a le x p r e s s i o n s ，at r i p l e t t r e e w i t h m a r k e de d g ei s p r e s e n t e dt or e p r e s e n tt h ea n a l y s i sr e s u l to fm a t h e m a t i c a le x p r e s s i o n s t w o a u t o m a t i cp e r f o r m a n c ee v a l u a t i o nm e t h o d so nt h eb a s i so ft r e em a t c h i n ga r ep r o p o s e d ，w h i c h a r e b a s e do nd y n a m i cp r o g r a m m i n g a l g o r i t h ma n db u t d ( b o t t o m - u pa n dt o p d o w n ) a l g o r i t h m ， r e s p e c t i v e l y ，b u t di st h eo n l yk n o w nm e t h o dt h a tc a nf i n da n ye r r o r so fs y m b o ls e g m e n t a t i o n s y m b o lr e c o g n i t i o na n de x p r e s s i o na n a l y s i s ， k e yw o r d s ：m a t h e m a t i c a i e x p r e s s i o ni m a g er e c o g n i t i o n m a t h e m a t i c a le x p r e s s i o na n a l y s i s a u t o m a t i cp c r f o r m a n c ee v a l u a t i o n 第一章引言 1 1 數(shù)學公式圖像識別的意義 數(shù)學是“唯一的國際科學語言”，不受種族、國家、文化和任何方言的限制，不同國 籍的科學人員都可以通過這種共通的符號溝通。這是因為“數(shù)學提供了一種有力的、簡潔 的、準確無誤的交流信息的手段”，正如數(shù)學算數(shù)一書中所說，“所有數(shù)學有用性的 理由都根源于數(shù)學可用作交流信息的有利手段這個事實”。數(shù)學大師華羅庚甚至認為可以 使用數(shù)形關系圖作為與外星人交流的媒介。這是因為在宇宙中，計數(shù)的規(guī)則應該類似，自 然圖形所具備的數(shù)形關系也是普遍的。魏晉時期的大數(shù)學家劉徽不使用任何數(shù)學符號和文 字，不進行任何運算，只用涂有顏色的“青朱出入圖”就把勾股定理清晰地呈現(xiàn)在人們面 f 狩。無怪乎華羅庚會如此感慨。 數(shù)學在“宇宙之大、粒子之微、火箭之速、化工之巧、地球之變、生物之謎、日用之 繁”等各方面都有重要貢獻，而數(shù)學公式是數(shù)學語言的最主要表現(xiàn)形式，所以科技文獻中 包含大量數(shù)學公式。這些文獻被掃描儀掃描，作為圖像數(shù)據(jù)保存入計算機，識別其中的數(shù) 學公式圖像，就是為了獲取公式中包含的信息，使信息的儲存和使用變得容易，實現(xiàn)信息 更好的交流和共享。例如t 研究人員要求能夠輕易重用數(shù)學公式；數(shù)字圖書館要求能夠以 便于編輯、便于查找的方式儲存數(shù)學公式；遠程教育要求能夠以有效的方式在網(wǎng)絡上傳輸 數(shù)學公式。現(xiàn)有的文檔圖像處理系統(tǒng)能夠高速、準確的識別文檔圖像中的普通文本，但是 不能正確處理其中的數(shù)學公式。大多數(shù)情況下，數(shù)學公式的識別結果是一些毫無意義的符 號，如圖卜1 。 = 阿 o ，o 巧 ( a ) 公式掃拙圖像 ( b ) 公式識別結果 圖l l ：一般文檔圖像處理系統(tǒng)識別數(shù)學公式的結果 不能夠正確識別數(shù)學公式圖像會帶來以下問題： 第一，驗證與重用。如果研究人員想要驗證或重用文檔中的數(shù)學公式，就只能使用專 用的數(shù)學計算軟件( 例如m a t l a b 或者m a p l e ) ，或者數(shù)學排版軟件( 例如t b x 或者l a t e x ) ， 按照各自的語法要求重新輸入。這個輸入過程既漫長又令人生厭，而且還要冒著引入新的 錯誤的風險。即便是使用新的可視化的公式輸入軟件( 侈l j o l q s c i e n t i f i cw o r k p l a c e 或者 s c i e n c ew o r d ) ，輸入速度也不可能加快很多。 第：，編輯與查找。以圖像形式保存的數(shù)學公式，既無法編輯修改，也無法實現(xiàn)公式 的查找和檢索。 第三，存儲和傳輸。以圖像形式保存的數(shù)學公式占據(jù)的空間遠遠大于以其他可編輯格 式保存占據(jù)的空間。這樣既耗費了存儲空間，又加大了傳輸量。 為什么目前的文檔圖像處理系統(tǒng)不能識別數(shù)學公式昵? 除了數(shù)學公式與普通文本反映 的內容不同以外，排版結構上也存在很大差別。表1 1 列舉了兩者在結構上的一+ 些區(qū)別。 數(shù)學公式普通文本 符號間位置關系 二維( 2 - d )一維( 卜d ) 字符集英文字符、希臘字符、數(shù)字、文本所屬語言的字符集 運算符等 字號變化頻繁同段落內基本相同 ( 上下標字號小) 風格斜體居多正體居多 基線 不對齊 行內對齊 ( 符號間二維關系) ( b a s e l i n e ) 符號問距不均勻 均勻，字問距，行間距 符號出現(xiàn)頻率 數(shù)學運算符號出現(xiàn)頻繁遵循一般文本的統(tǒng)計規(guī)律 襲1 1 ：數(shù)學公式與普通文本的差異 因此識別數(shù)學公式圖像有著重要的現(xiàn)實意義。 1 2 數(shù)學公式圖像識別的基本步驟 i 旮動數(shù)學公式圖像識別的目的就是從包含有數(shù)學公式的掃描圖像開始，定位其中的公 式，識別公式中的符號，然后根據(jù)符號的內容和相互間位置關系，對公式進行分析，并將 分析結果按照某種1 格式保存，最終實現(xiàn)復用。如圖l 一2 所示，數(shù)學公式泌別的基本步驟可 以分為數(shù)學公式定位、數(shù)學公式識別、數(shù)學公式分析以及數(shù)學公式分析結果的格式轉換輸 出。 無論是數(shù)學公式定位，數(shù)學公式符號識別還是數(shù)學公式分析，都需要對其性能進行有 效的評估，以便準確地定位系統(tǒng)中出現(xiàn)的各種錯誤。 1 3 數(shù)學公式圖像識別自動性能評估的必要性 現(xiàn)實生活中，我們到處都能見到形形色色的“排行榜”，這些“排行榜”實際上就是 對乖物某些方而的性能或功能的一個評價結果，不可否認“排行榜”對事物發(fā)展有著或多 或少的影響。同樣，對于一個軟件系統(tǒng)而言，在設計開發(fā)的整個過程中，在每個階段都需 要對各個模塊和各個功能進行測試和性能評估。有時候測試和性能評價工具的欠缺甚至成 為系統(tǒng)性能提高和改善的制約因素。因為通常設計開發(fā)者在對其中的某一個模塊進, i j = - t 一 個很小的改動，往往就會影響系統(tǒng)性能的方方面面。他們需要花贊大量的時問來分析被修 改以后的系統(tǒng)的性能，而且有時即使花費了很多時間對系統(tǒng)性能的評估仍然不準確。因為 這些分析和評估只是在實驗的基礎上，對一個較小的樣本集進行，而不可能對大的樣本集 進行，因此這些分析的結果一般只有理論上的價值，而沒有實際的價值。 數(shù)學公式圖像識別是一個具有相當難度的前沿課題，許多處理方法都還在探索利嘗試 中。無論是公式的定位，公式符號的識別，還是公式的分析都需襄進行測試和性能評估。 3 有關數(shù)學公式識別系統(tǒng)性能的評測問題至今尚無公認的標準，然而性能評估是非常重要 的。為了比較處理方法的優(yōu)劣，就必須在大規(guī)模集合上進行測試。如果測試過程不能自動 進行，測試規(guī)模就只能很小。 數(shù)學公式行的二維結構決定了公式識別不僅包含符號識別，更重要的是對其結構的分 析，因此數(shù)學公式分析的性能評估顯得尤為重要。同時，也下因為二維結構，使數(shù)學公式 分析的性能評估變得更困難，不能像符號識別那樣僅僅用符號的識別率就能衡量其性能。 雖然已經(jīng)有很多數(shù)學公式分析的方法，然而這些方法分析得到的結果究竟如何，準的 方法效果好，準確性高，目前尚沒有一個公認的評測標準。分析結果的好壞只能由人工評 判，所以目前幾乎所有的方法都只是在幾十甚至十幾個公式集上進行測試，這嚴重阻礙了 數(shù)學公式識別研究的進一步發(fā)展。這就迫切需要開發(fā)出一個工具，使其對數(shù)學公式分析技 術進行自動的性能評估。只有這樣，對它們的性能評估才可能在大樣本集上進行，得出的 評估數(shù)值才真正具有實際意義。因此對這方面的研究也變得非常有價值了。 1 。4 本文的主要內容及結構 數(shù)學公式圖像漢別的各個階段都需要進行有效的測試和性能評估。目前出現(xiàn)的對手寫 體數(shù)學公式識別的性能評估都存在有片面性，性能指標太過籠統(tǒng)以及測試規(guī)模小等缺點， 并不通用。而對于印刷體數(shù)學公式識別的性能評估，只有m o k a m o t o 等人在 1 1 中提出了 一種基于m a t h m l 格式比較的方法，但是他們的方法只能判斷出分析結果是否詐確，并沒 有指出錯誤的原因及修改的方法。由于公式本身的二維特點決定了公式關系用樹表示是非 常恰當?shù)?，所以一般識別結果都采用有層次的樹結構表示，因此本文提出了基于樹匹配的 公式識別自動性能評估的方法。該方法不僅能夠找出符號識別和分析中存在的錯誤，還能 指出錯誤的類型和原因，并以此指導識別方法的修改。作為核心，本文詳細介紹了兩種樹 匹配算法：動態(tài)規(guī)劃算法和b u t d ( b o t t o m u pa n dt o p - d o w n ，因為每一個樹節(jié)點都采用 先自底向上然后自定向下的比較過程) 算法。其中b u t d 算法不僅能夠評估公式分析的一陛 能，還能評估符號切割和識別的性能。最后我們給出了b u t d 算法的實驗結果。 第一章：概述了數(shù)學公式圖像處理的意義和基本步驟，以及數(shù)學公式識別的自動性能 評估在數(shù)學公式處理中的地位。 第二章：給出性能評估的概念和系統(tǒng)性能評估的一般模型。概述公式識別的結果并提 l 乜識別結果的三叉樹表示，同時總結了當前公式識別性能評估的現(xiàn)狀。就此本文提出一個 公式識別的自動性能評估模型和兩種基于樹匹配的性能評估算法：動態(tài)規(guī)劃算法與b u t d 4 算法。 第三章：給出基于動態(tài)規(guī)劃的性能評估算法。由于我們使用帶邊屬性的三叉樹與一般 帶標記的樹結構有所不同，而且節(jié)點匹配的標準也不一樣，因此本文將傳統(tǒng)的動態(tài)規(guī)劃匹 配算法進行了擴充和改進，即把傳統(tǒng)的節(jié)點更改，節(jié)點插入和節(jié)點刪除三種基本編輯操作 擴充為節(jié)點完全替代，節(jié)點內容修改，節(jié)點類型修改，節(jié)點插入，節(jié)點刪除，邊屬性修改 六種基本編輯操作，以滿足公式識別性能評估的特殊需要。對該算法進行了詳細的描述利 分析，并給出一個實例。 第四章：給h _ 基于b u t d 的性能評估算法。動態(tài)規(guī)劃算法由于受到節(jié)點的兄弟次序不 變和祖孫次序不變的約束，在記錄錯誤的時候存在冗余，隱藏了某些錯誤的根本原因，因 此本文根據(jù)實際需要，將動態(tài)規(guī)劃中的編輯操作和錯誤類型進一步擴充，使錯誤類型能夠 直接反映出錯誤的本質原因，并提出新的匹配算法( b u t d ) 。詳細介紹了該算法的流程， 同時給出相應的實例。最后從合理性和效率兩個角度比較了b u t d 算法和動態(tài)規(guī)劃算法， 證明b u t d 算法比動態(tài)規(guī)劃算法更具優(yōu)勢。 第五章：給出了基于b u t d 算法的自動性能評估的實驗結果，并對結果進行了分析和 總結。 第二章數(shù)學公式圖像識別的自動性能評估模型 2 1 性能評估概述 所謂性能評估是指根據(jù)一定的基準數(shù)據(jù)來進行的測試比較。性能評估在比較幾個相似 的復雜系統(tǒng)時非常重要。此外，當一個系統(tǒng)被修改或者被更新版本時，也需要對修改后的 系統(tǒng)的性能做出評估。在這種隋況下，性能評估不僅要對整個系統(tǒng)進行，而且需要對系統(tǒng) 的各個模塊來進行，這樣才有機會發(fā)現(xiàn)系統(tǒng)中的薄弱環(huán)節(jié)，并且給出一個直接面向系統(tǒng)目 標的改進。 2 1 1 性能評估的一般目標 性能評估基本上追求以下三個目標： 提高系統(tǒng)性能并對系統(tǒng)進行質量控制： 比較多個復雜系統(tǒng)； 評估系統(tǒng)的性能，即定義一個系統(tǒng)性能的絕對值。 性能評估的第一個目標是提高或者維護系統(tǒng)的性能。 性能評估的第二個目標是比較多個不同的系統(tǒng)。這在要從幾個系統(tǒng)中選擇一個最好的 系統(tǒng)去完成某項任務時，是非常關鍵的。 性能評估的第三個目標是進行性能評估，給出評價系統(tǒng)性能的一個絕對數(shù)值，這個數(shù) 值可以說l 蟈系統(tǒng)的當前發(fā)展水平。它描述了在不同特征的輸入數(shù)據(jù)情況下，實際系統(tǒng)和理 想系統(tǒng)之間的性能差距。 這些情況下，性能評估的執(zhí)行都是基于系統(tǒng)比較。這種比較可以是兩個系統(tǒng)之問的比 較，也可以是多個系統(tǒng)之問的比較。如果要評價系統(tǒng)性能的絕對值，可以用該系統(tǒng)與所謂 的理想系統(tǒng)進行比較。而所有這些比較的執(zhí)行都使用參考數(shù)據(jù)或者基準( g r o u n dt r u t h 簡 稱g t ) 來作為比較的依據(jù)。 下面，我們給出一個基于上述目標的關于性能評估的更正規(guī)的描述。通常情況一f ，一 個性能評估包含輸入數(shù)據(jù)，一個或多個系統(tǒng)，一個評估函數(shù)和一個評價函數(shù)。 6 一一一。 輸入數(shù)據(jù)兩個系統(tǒng) 評估函數(shù) 評價函數(shù)l - - 一- 一一一一一- 一一一一一一一一一一一_ _ - - _ - _ - _ - - _ - - - _ _ _ - - - 一一_ 一一一一_ 一一一一一一_ 一一一- _ _ - _ _ - - _ 一- 圖2 - 1 ：兩個系統(tǒng)的性能評估模型 1 一一一一。一一一一一一。- 。一一一一一1 輸入數(shù)據(jù)一個系統(tǒng)評估函數(shù)： l 匾亟畫口魚l 墮) 笪l 圃i 圖2 - 2 ：一個系統(tǒng)的性能評估模型 圖2 1 和圖2 - 2 分別表示對兩個系統(tǒng)和一個系統(tǒng)進行比較評估的模型，其中各模塊說明 如下： 輸入數(shù)據(jù)( i n p u t d a t a ) 的選擇對于性能評估來說是非常重要的。輸入數(shù)據(jù)對于系統(tǒng)處 理的般任務應該具有代表性。有的系統(tǒng)本身對它所要完成的任務描述就不清楚，但是對 于一個確定的算法不會出現(xiàn)這種情況。然而這里系統(tǒng)的概念是包含理想系統(tǒng)( 見2 1 2 節(jié)) 的，這個理想系統(tǒng)是存在于設計者的腦海里的。系統(tǒng)所給出的描述可能是系統(tǒng)的理想輸出 或者是一種基準( g t ) 。從實際的角度考慮，這利，方法看上去很合理，因為性能評估通常 要求系統(tǒng)的輸出滿足或者達到一定的要求。 評估函數(shù)( a s s e s s m e n tf u n c t i o n ) 是性能評估的另一個重要部分。評估函數(shù)是根據(jù)系統(tǒng) 的輸出而賦的一個值，這個值可以是基于系統(tǒng)的輸出與對應輸入的比較所得出的值，它定 量地反映了系統(tǒng)輸出的質量。顯然，不同的評估函數(shù)對于系統(tǒng)相同的輸出會有一i 同的結果。 而理想的評估函數(shù)總是能產生一個最優(yōu)的值。評估函數(shù)對于某些系統(tǒng)是比較確定的，但是 對于數(shù)學公式處理系統(tǒng)或公式分析模塊來說就不是很確定了，因此，評估函數(shù)的選擇是一 個很重要的因素。 評價函數(shù)( e v a l u a t i o nf u n c t i o n ) 用于比較幾個不同系統(tǒng)的評估函數(shù)的值。這個函數(shù)繪 出的結果是幾個系統(tǒng)中哪個好哪個壞，或者哪個更好一些。評價結果應當同時指出對輸入 數(shù)據(jù)的分類情況。因此，輸出結果就不應當是：“系統(tǒng)a 比系統(tǒng)b 好”，而是：“在輸入有 字符粘連( t o u c h i n g ) 的情況下，系統(tǒng)a 比系統(tǒng)b 好”?；蛘咻敵鼋Y果中可以包含假設的 測試過程。 如果輸入數(shù)據(jù)、系統(tǒng)、評估函數(shù)和評價函數(shù)都確定了，則性能評估也就確定了。 7 2 1 2 理想系統(tǒng)與理想評估 在此，我們給出理想系統(tǒng)與理想評估的概念。 我們所說的性能評估都隱含著：每個實際系統(tǒng)s y s 都對應一個理想系統(tǒng)d s y s 。這個理 想系統(tǒng)以最優(yōu)的方式解決了實際系統(tǒng)所要解決的問題。由于理想系統(tǒng)是實際系統(tǒng)所希望達 到的目標，實際系統(tǒng)就會試圖將它的輸出向基準靠近。對應于理想系統(tǒng)，也有一個理想的 評估。理想評估總是以期望的方式來評估系統(tǒng)的輸出。如果系統(tǒng)的輸出是理想輸出，則評 估結果就應該是一個最優(yōu)值，否則評估結果就應該差一些。由于實際應用中也許只提供了 有限的信息，使實際的評估含有不精確的因素，因此實際的評估只是理想評估值的一個近 似。理想評估是一個沒有錯誤的評估，不同的目標應該由不同的評估來完成。 因此，理想系統(tǒng)和理想評估相對于實際系統(tǒng)和實際評估是一個沒有錯誤情況的系統(tǒng)模 型和評估模型。我們的目標是要最優(yōu)地近似這些理想模型。 2 1 3 測試基準( g r o u n dt r u t h ) 這里所提到的測試基準就是前面所介紹的基準( g r o u n dt r u t h 簡稱g t ) 。在數(shù)學公式 識別系統(tǒng)中，基準代表系統(tǒng)的最優(yōu)輸出。在性能評估中我們也使用這個詞來表示評估所依 賴的標準，為了定義基準，我們必須考慮這個最優(yōu)是相對于一個什么參考標準而言的，即： 相對于什么最優(yōu)? 。 例如在數(shù)學公式識別系統(tǒng)中，基準主要是為系統(tǒng)的輸出定義的。對于數(shù)學公式處理系 統(tǒng)的輸出，基準就是人對于數(shù)學公式圖像的識別結果。因此，在這種情況下，是人決定什 么足最優(yōu)。例如，圖2 3 所示，也許有人認為t ，a ，c 是同一行的關系，而有入則 認為一a 是1 t 的上標，c 是a 的上標，遇到這種情況，就要考慮是相對誰最優(yōu)? 。 當我們要確定一個系統(tǒng)某些內部模塊輸出的基準，這個最優(yōu)輸出就依賴于浚模塊之后的其 它模塊，所以基準可以在系統(tǒng)任何兩個模塊的接口之間定義。因此，在確定了輸入數(shù)據(jù)， 評估函數(shù)和評價函數(shù)之后，性能評估也可以在系統(tǒng)的任意兩個模塊之間進行。如圖2 - 4 所 示。 總之，我們需要一個評估函數(shù)，這個評估函數(shù)可以出人來確定，也可以山系統(tǒng)的后續(xù) 模塊確定。 不失一般性，我們可以認為評估函數(shù)是一個計算代價的函數(shù)。這個代價就是將系統(tǒng)的 輸出修改成為最優(yōu)輸出所需要花費的代價。這就意味著評估函數(shù)的值總是大于或等于零。 而且系統(tǒng)的輸出結果越好，代價值就越小。對于基準來說，該評價函數(shù)的值應該等于零。 這是一個一般意義上的定義，因為其它函數(shù)都可以很容易地轉化為這種代價函數(shù)的形式。 - 一- - - - 一_ 一一一一一一_ 一_ 一一一一一一一一一一 ：性能評估1 ：基準l c a c 圖2 - 3 性能評估n l性能評估n ； 圖2 - 4 ：基準可以在系統(tǒng)的各個地方定義 定義2 1 ：假設給定系統(tǒng)曲s 和它的輸入數(shù)據(jù)集合i n 。跏。是輸入數(shù)據(jù)i n ( i n 脅) 在基準 中的對應結果，系統(tǒng)s y s 對應的理想系統(tǒng)是l d s y s 理想的評估函數(shù)為l d a s s a 則： i d s y s ( i n ) = g t l , ，且i d a s s ( g t i , 。) = 0 注：一個輸入數(shù)掘可能對應多個基準。因為可能有幾種結果都被認為是最優(yōu)的。但是通常 出現(xiàn)這種情況時，我們就給出一些特殊規(guī)定或說明，從而選定這幾種結果中的一種作為基 準。 2 2 數(shù)學公式圖像識別結果及其自動性能評估現(xiàn)狀 2 2 1 數(shù)學公式圖像識別的結果 圖像i f ，的數(shù)學公式經(jīng)過定位，符號識別和分析之后以某種格式保存即得到公式的識別 結果，因此數(shù)學公式識別的結果實際上等同于公式分析之后所得的結果。 數(shù)學公式分析就是在正確識別公式的每個符號，并且得到包含該符號的最小外接矩形 的j i g ；i l l l 上，分析符號之間的關系并進行組合，理解公式的含義，實現(xiàn)公式版式結構的恢復， 甚至表達式的自動計算，最后將分析結果用某種數(shù)據(jù)結構( 一般是圖或者樹) 表示出來。 根據(jù)最終分析目標的不同，數(shù)學公式分析分為兩種層次m l ： ( 1 ) 版式以別( l a y o u tr e c o g n i t i o n ) ：版式識別要求分析結果足夠恢復該公式的排版樣式， 但是不需要理解整個公式的數(shù)學含義。版式識別結果可以使用l a t 。x 等排版語言輸出。文 獻電子化過程中，為了保證版面的一致，就需要識別數(shù)學公式的版式。 q ( 2 ) 語義識別( s e m a n t i cr e c o g n i t i o n ) ：語義識別要求確切理解整個數(shù)學公式的數(shù)學含 義，即明確表達式的計算順序和函數(shù)的作用域。語義識別結果可以使用m a t l a b 等數(shù)學計算 軟件包的語言輸出。實現(xiàn)數(shù)學公式的自動計算就需要識別公式的語義。 同一公式的版式識別和語義識別的結果并不相同，我們以公式( 2 - 1 ) 為例給出版式 識別結果與語義識別結果。圖2 5 是利用樹結構表示的版式識別結果。圖2 - 6 是利用樹結 構表示的語義識別結果。 由于語義識別的難度遠大于版式識別的難度，因此目前絕大部分數(shù)學公式分析都是以 版式識別為目的。版式識別的分析方法大致可以分為兩種：基于結構的分析方法和基于文 法的分析方法。 基于結構的分析方法就是直接根據(jù)各個符號的內容、大小、相對位置以及符號間的空 t 3 等結構信息判斷出相鄰符號的關系，生成符號組，合并子表達式，從而實現(xiàn)數(shù)學公式分 析的方法。這種分析方法既可以把握公式的整體結構，也可以把握局部符號之間的關系， 能夠處理格式復雜，符號數(shù)目多的公式。結構分析可以較好的識別公式版式，但語義識別 的能力較差。 基于文法的分析方法是通過定義文法來分析數(shù)學公式的含義。這種方法具有很強的語 義識別能力，但是只能處理格式簡單，類型單一，符號數(shù)目少的數(shù)學公式，根本不能滿足 實際需要。 工3 l n 工+ f ( 2 一1 ) i x d x 7 l a t e x 結果輸出： l nx + f r a c x “3 j x i n t _ a “b x d x 圖2 - 5 版面識別結果 m a t l a b 結果輸出： l n ( x ) + ( x “3 u a d ( x 1 ，a ，b ) 圖2 - 6 語義識別結果 得到公式的分析結果之后，我們就可以視其為基準，基于它來評估整個識別系統(tǒng)的性 1 0 能。就目前來況，基于結構的分析方法居多，所以我們后面定義的1 1 種公式關系只反歡了 結構信息，如果定義足夠的關系，那么語義信息同樣也是可以評估的。 2 2 2 數(shù)學公式圖像識別結果的表示 l a t e x 是一種科技排版軟件，常用于數(shù)學文獻的排版，而且l a t e x 格式的源文件是人 可以閱讀并理解的文本格式。因此可以將數(shù)學公式識別結果保存為l a t e x 格式。以下是數(shù) 學公式及相應的l “t b x 表達式： f m ) 如2 毛w 。，( x i ) - ) 、 i n t 一 o l “ i n f t y f f l e f t ( x u i g h t ) d x l p p r o x , s u m “ n ) 一( i = lj w 一 i c a x 一 i f q e f t ( x i h - i g h t ) 】 無論用什么樣的分析方法，公式本身的二維特點決定了公式關系用樹表示是非常恰當 的，所以一般分析結果都采用有層次的樹結構表示，另外我們很容易就能將l 4 t b x 格式轉 化為樹結構。因此，我們提出用一種帶邊屬性的三叉樹來表示數(shù)學公式的分析結果，從這 種三叉樹結構很容易就可以得到公式的版式結構，給人一種直觀的感覺。 根撕人二件寫、閱讀公式的習慣，并參考l 葉e x 語言表示數(shù)學公式的方法我們將數(shù)學 公式劃分成l1 種類型，即：多行表達式( m u l t i l i n ee x p r e s s i o n ) 分式表達式( f r a c t i o n e x p r e s s i o n ) ，根式表達式( r a d i c a le x p r e s s i o n ) ，定界表達式( d e l i m i t e r e x p r e s s i o n ) ，矩陣 表達式( m a t r i xe x p r e s s i o n ) ，組表達式( g r o u p e x p r e s s i o n ) ，堆疊表達式( s t a c k e x p r e s s i o n ) ， 帽子表達式( h a te x p r e s s i o n ) ，角標表達式( s c r i p te x p r e s s i o u ) ，普通表達式( c o m m o n e x p r e s s i o n ) 和基元表達式( p r i m a r ye x p r e s s i o n ) 。圖2 7 至2 一1 7 給出了各種表達式的示 例。 ( z + ) ( z y ) = z 2 一x y + x y y 2 = z 2 一y 2 j i a 2 一b 2 a + b 圖2 - 8 ：分式表達式示例 ( 8 2 3 + 1 2 3 ) 圖2 - 1 0 ：定界表達式示例 x l lx 1 2 x 2 1x 2 2 圖2 一1 2 ：矩陣表達式示例 圖2 7 ：多行表達式示例 1 2 3 _ _ a + b + + y + z 圖2 一1 4 ：帽子表達式示例 z = 2 0 + 3 可 圖2 一1 6 ：普通表達式示例 乒2 + y 2 + 2 z 可 圖2 9 ：根式表達式示例 n i - - - - 1 圖2 一1 1 ：組表達式示例 圖2 1 3 ：堆疊表達式示例 z y 2 圖2 - 1 5 ：角標表達式示例 z 圖2 一1 7 ：基元表達式示例 任意類型的公式都可以用帶邊屬性的三叉樹表示，自然整個數(shù)學公式也可以表示成一 棵三叉樹。樹中每個節(jié)點代表一個數(shù)學符號或一個組元( 如s i n ，l o g ，m i n ，1i m 等) ，節(jié)點 中給出了相應符號的識別結果，位置信息以及公式類型，并且每個節(jié)點至多有三個非空子 節(jié)點。每條邊都有一個屬性值，指出所連接的兩個節(jié)點之間的關系，包括：同行( n e x t ) ， 上標( s u p e r s c r i p t ) ，下標( s u b s c r i p t ) ，組表達式上標( l o pu p s c r i p t ) , 組表達式下標 ( l o i d o w n s c r i p t ) ，分子( n u m e r a t o r ) ，分母( d e n o m i n a t o r ) ，帽子( h a t ) ，堆疊( s t a c k ) ， 根式開方數(shù)( r a d i c a l e x p ) ，根式被開方數(shù)( r a d i c a l m a i n ) ，矩陣起始元素( m a t r f x b e g n ) ， 矩陣結束元素( m a f r i x e n d ) 。對于多行表達式，我們把每一行表達式看成一棵獨立的三叉 樹。這種結構類似于公式的版式結構，但是比版式結構包含更多的語義信息。如圖2 一1 8 所示為公式磐+ 等的三叉樹熟 圖2 1 8 ：公式口f + 蘭 的三叉樹結構示例 l - i j 用帶有邊屬性的三叉樹表示數(shù)學公式的結構，會使某些公式類型“消失”，如定界表達 式( d e l i m i t e r e x p r e s s i o n ) ，堆疊表達式( s t a c ke x p r e s s i o n ) 帽子表達式( c a d e x p r e s s i o n ) 以及伯標表達式( s c r i p te x p r e s s i o n ) ，這些表達式類型信息將保存在相應 子表達式的邊屬性中，而不必在節(jié)點中記錄。這種節(jié)點平衡的三叉樹結構極大的方便了后 續(xù)的基于樹匹配算法的性能評估工作。 2 2 3 自動性能評估的現(xiàn)狀 1 9 6 8 年，a n d e r s o n 在他的博士論文1 1 i 中最早提出了數(shù)學公式的處理問題，在隨后的三 十多年中，有關數(shù)學公式處理的各個方面都有或多或少的研究。由于早期的研究人員主要 致力于理論方面的研究，而沒有實驗結果，因此直到后來刊。提出如何評價一個數(shù)學公式處 理系統(tǒng)的性能問題。在2 0 0 0 年之前的文獻中所提到的評估方法都是針對手寫體數(shù)學公式 的，大致可以歸為三類： ( 1 ) 注重于公式的結構，通過測試只給出兩種結果，即f 確或不正確。 ( 2 ) 只考慮符號的識別率。 ( 3 ) 只對少數(shù)非常典型的公式進行評測，這些公式由少數(shù)固定人員書寫，而且書寫整潔。 這些手寫體數(shù)學公式的評估方法都具有片面性，性能指標太過籠統(tǒng)以及測試規(guī)模小等 缺點，并不通用。k a m f a ic h a n 等在 1 2 中也提到了在線手寫體數(shù)學公式處理系統(tǒng)的性能 評估問題，他們綜合了前人的方法，將錯誤類型分成兩種：公式中符號的識別錯誤和公式 本身結構的錯誤，給出了兩種錯誤率的計算公式，即錯誤個數(shù)除以總數(shù)，但是也僅僅是如 此而已，并沒有說明如何找到那些錯誤，也未提出有效的評測步驟和過程。 對于印刷體數(shù)學公式識別的性能評估，至今只有m o k a m o t o 等人在 1 1 中提出了一種 基于m a t h m l 格式比較的方法。他們將公式的標準分析結果和實際的分析結果都用 m a t h m l 格式表示，在此基礎上進行比較檢查那些典型公式結構( 如角標，分式，根式， 極限，矩陣等) 的分析是否正確。首先，對應的兩個公式結構的圖像坐標一致時，才會比 較兩者的結構類型是否相符臺，因此將子表達式圖像的左上角和右下角坐標作為標記( t a g s ) 加l 入到m a t h m l 格式中，如圖2 1 9 所示。其次，用正確或錯誤表示公式結構比較的結果， 即如果對應的兩個公式結構類型一致，就認為分析是j 下確的，否則認為是錯誤的?？紤]到 盡管整個公式結構可能不完全相同，但是其中某些予表達式結構類型也許是一致的，所以 他們用一利予結構方法來比較兩個子結構。主要步驟如下： 1 從標準分析結果中找每個子表達式最內部的標記： 2 如果這個標記( 比如 ) 在實際分析結果中存在，則 檢查標記內部子表達式的結構類型是否相同。如果不相同，則記錄該子表達式結構類型錯 誤。 4 圖2 一1 9 ：公式結構的m a t h m l 表示 盧 餞 j ：塥i 訕耐i 誦i ；t j “ t - ， ：n 毪戇甥鱗孵州矗睫二： t 由a r t s e l “e l l l 強 ：蘆黼鬻研憾螄嘲 o io _ ，l 1 i q h i -i _ 1 1m - i 2 2 ，帥，黧4 a i i i 釜, i j 她一蚋s 盟j i 3 1 ：n o t f o u n d - o , - jt 的r e c o g n i t i o nr e s h l f 圖2 - 2 0 ：公式結構的比較示例 以圖2 2 0 所示的公式分析結果為例，首先，對于標準分析結果中的標記 ，在實際分析結果中也檢測到了，因此比較標記中兩個子表達式類型 由標記中“m f r a c ”知道，它們具有相同的類型，都為分式，所以這個子表達式分析正確。 1 5 其次，同理可知標i g 中的子表達式分析結果也是正確的 再次，由于標準分析結果中的標記 在實際分析結果巾不存 在，凼此認為該標記中的角標( s u b s u p ) 結構類型分析錯誤。 對于簡單的非常典型的公式結構，mo k a m o t o 的方法效果比較好，但是對于復雜一點 的結構，其比較結果不甚理想，因此該方法沒有很好的通用性。此外，他們只是判斷出分 析結果是否正確，并沒有指出錯誤的原因，這= ；_ i l i 滿足我們評估的宗旨即為系統(tǒng)的設計開發(fā) 者指出問題所在和改進方向。 基于目前的實際情況，實現(xiàn)數(shù)學公式識別的自動性能評估不僅是必要的而且是艱巨的。 2 3 數(shù)學公式圖像識別的自動性能評估模型 2 3 1 自動性能評估模型 為了提高整個公式處理系統(tǒng)的性能，或者比較各種公式處理方法的效果，需要在大規(guī) 模集合上進行測試，因此我們需要構建一個自動性能評估系統(tǒng)來定量地評估公式結果，當 然這是相當困難的。 從2 1 的討論，我們知道為了對數(shù)學公式識別系統(tǒng)進行性能評估，我們需要有一個衡 量性能的尺度，還需要一些基準數(shù)據(jù)，以及一個實用的算法來比較公式分析的結果與基準 數(shù)據(jù)，從而得出性能評估的結果數(shù)據(jù)。對這些結果數(shù)據(jù)迸行統(tǒng)計以后，將最終結果反饋給 設計開發(fā)者，可以幫助他們很快地知道公式分析算法的效果。這些統(tǒng)計結果之中包括對錯 誤的分類，對錯誤嚴重程度的估算，以及對這些錯誤可能產生的原因的分析?；谏鲜隹?慮，我們提出了圖2 2 l 所示的自動性能評估模型，這實際上是將數(shù)學公式識別系統(tǒng)與一 個理想系統(tǒng)進行比較。 下面，對性能評估模型中主要部分作一個簡要說明： 基準數(shù)據(jù)是評估實際識別結果的一個參考標準。在我們的自動性能評估系統(tǒng)中，摹準 數(shù)據(jù)是每個數(shù)學公式的正確的三叉樹結構。我們構造一個標準的數(shù)據(jù)庫。用來存放各個數(shù) 學公式的f 確的三叉樹格式文件。 公式識別的結果數(shù)據(jù)是系統(tǒng)實際識別所得的結果。 格式轉換模塊用于將實際的分析結果轉換為帶邊屬性的三叉樹結構，該模塊可以內嵌 于公式識別系統(tǒng)中，也可以獨立運作。 轉換結果數(shù)掘是將實際的識別結果通過格式轉換所得，是實際識別結果的三叉樹結構。 性能評估算法是自動性能評估系統(tǒng)的核心。一個有效而實用的性能評估算法是真正做 到自動進行性能評估的關鍵，否則就只能紙上談兵。有關性能評估算法參見2 3 2 小節(jié)。 性能評估的結采是各種錯誤的描述文件和統(tǒng)計數(shù)字文件a 性能評估結果的表示工具是性能評估結果的表現(xiàn)形式，我們采用圖形，表格，文術棚 結合的表示方式。 圖2 2 l ：數(shù)學公式識別系統(tǒng)的自動性能評估模型 凡是能將實際以別結果通過格式轉換模塊轉化為帶邊屬性的三叉樹結構的公式識別系 統(tǒng)，都可p j 我們基于該模型構建的自動性能評估系統(tǒng)來評測系統(tǒng)的性能。 2 3 2 性能評估算法概述 根據(jù)2 3l 的自動性能評估模型，我們設計了兩個基于樹匹配的算法來實現(xiàn)上述的評估 方法a 一一是經(jīng)過擴充的動態(tài)規(guī)劃算法，二是b u t d ( b o t t o m u pa n dt o p d o w n ) 算法。要 構建這樣一個自動性能評估系統(tǒng)，關鍵的有兩點： - a 定義性能指標，即從哪些方面來衡量諺! 別結采的好壞。掇據(jù)上述描述，對公式識別結梁 的評估最終是將實際分析得到結果與基準數(shù)據(jù)進行比較，因此我們采用編輯距離表示 1 7 兩棵樹之間的差異，用該距離中出現(xiàn)的各種編輯操作的個數(shù)來定景描述相應的分析錯 誤，并且給出各種統(tǒng)計結果。具體的編輯操作將根據(jù)所使用的樹匹配算法而定，見3 1 小節(jié)。 b 設計出有效的樹匹配算法。彥算法在時間效率上應該是比較快的，否則性能評估占去太 多的時間會給人一種本末倒置的感覺。 在動態(tài)規(guī)劃算法中，我們定義了節(jié)點完全替代，節(jié)點內容修改，節(jié)點類型修改，節(jié)點 插入，節(jié)點刪除，邊屬性修改六種基本編輯操作，而在b u t d 算法中我們定義了節(jié)點內容 修改，節(jié)點類型修改，節(jié)點插入，節(jié)點刪除，節(jié)點分裂，節(jié)點合并，節(jié)點轉移和邊屬性修 改八種基本編輯操作，用這些編輯操作的數(shù)目和比例來評估公式識別方法的性能。其中的 節(jié)點內容修改反映了公式符號識別的性能，其它操作則主要反映了公式分析和符號切割的 性能。兩種樹匹配算法的輸入與輸出分別為： 算法的輸入 按照自動性能評估模型，算法的輸入應該是待比較的公式實際分析結果的轉換結果與 相應的基準數(shù)據(jù)，即公式的三叉樹。 算法的輸出 輸出是比較后的結果描述文件和性能評估的統(tǒng)計數(shù)字文件。結果描述文件中包括對正 確情況的描述和對錯誤情況的描述，錯誤情況根掘不同的編輯操作錯誤進行歸類描述。而 性能評估的統(tǒng)計數(shù)字文件則包含了公式分析的各種錯誤類型的數(shù)目和它們在整個錯誤中 所占的比例以及各種公式類型的分析錯誤率。 在后續(xù)兩章我們會給出兩種算法的詳細描述及相應的實例。 第三章基于動態(tài)規(guī)劃算法的自動性能評估 3 - 1 預備知識 由于我們的自動性能評估系統(tǒng)主要通過樹匹配算法實現(xiàn)性能評估，因此先介紹有關樹 及樹匹配的相關基礎知識。 3 1 1 樹的遍歷 本文所涉及到的樹都是指帶標記的有序樹，即樹中每個節(jié)點都有一個標i , e ( 1 a b e l ) ，甚至 可能有某些附加的信息( 這種信息被稱作節(jié)點的內容) ，并且如果該節(jié)點有子節(jié)點，則子 節(jié)點之間從左至右的順序是固定的。這里所提到的從左到右的順序是指按照某種方式對樹 進行遍歷，得到所有節(jié)點的一個排序，每個節(jié)點在排序中的相對位置。所謂遍歷就是將樹 中每個節(jié)點都訪問一遍，通常有先根遍歷，后根遍歷幾種方式等。先根遍歷就是先訪問根 結點，再訪問它的子節(jié)點；反之，先訪問子節(jié)點再訪問根節(jié)點則稱之為后根遍歷。 由于本文后面介紹的兩個算法都采用后根遍歷，所以在此舉例說明。與一般樹中的節(jié) 點有所不同，我, f i g f i 1 每個節(jié)點代表一種表達式類型，節(jié)點本身的結構比較復雜，而且對各 種表達式處理也有差異，因此整個遍歷過程相對復雜。但是基本的思路仍然與一般的后根 遍歷相同，只是每次訪問到某個節(jié)點時，必須先判斷它的表達式類型，再確定下一步的遍 nk ，3 歷方向。如圖3 - l 所示為公式以，+ 芝 的后根遍歷的結果，其中每個節(jié)點右側的( i ) 表 i = 1 j 示該節(jié)點在后根遍歷排序中的序號。 3 1 2 樹的距離度量 早在1 9 7 9 年i c t a i 就在 9 提出了有關樹與樹之間的比較( 或者稱之為匹配) 問題。 至今，已經(jīng)出現(xiàn)許多解決樹匹配的方法，其中大多數(shù)都采用動態(tài)規(guī)劃來實現(xiàn)，而動態(tài)規(guī)劃 的方法實際上是字符串匹配算法的個推廣。當然，也有一些其他的方法。例如【l o 】中將 樹匹配問題看作一個最優(yōu)化問題，提出一個簡單的遞歸的圈溯算法，但是該算法的運行時 問是指數(shù)級的，相較于動念規(guī)劃算法它的速度要慢。 無瞼用什么方法解決樹匹配問題，首先都必須定義樹之間的距離度量，用以定量地描 述出兩棵樹之間到底相差多少，這是前提條件。得益于字符串匹配問題的解決思路，樹之 1 9 圖3 - 1 ：公式2 產n 。+ 竺_ 二后根遍歷結果 百 3 間的距離也可以用編輯距離表示。因此樹之間的匹配轉化為對兩棵樹進行比較并且找出一 個基本編輯操作( 如捅入，刪除，替代等) 的序列，該序列滿足以下兩個條件： ( 1 ) 按照該序列進行操作能夠將一棵樹轉化成另棵樹； ( 2 ) 在滿足( 1 ) 的所有基本編輯操作序列中，該序列的操作代價最小。 除了編輯距離之外，諸如對齊距離、獨立子樹距離、t o p d o w n 距離以及b o t t o m u d 距離等等都可以用來表示樹之間的距離度量。事實上，這些距離度量都是在編輯距離的基 礎上附加一些限制條件得來的。本文采用編輯距離來度量樹之間的距離，將在后面詳細介 紹。 3 1 3 編輯操作與編輯距離 對于一般的帶標記的有序樹，我們通?？紤]三種基本的編輯操作：節(jié)點的替代( c h a n g e 或r e l a b e l ) ，刪除( d e l e t e