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

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