數(shù)學公式識別技術(shù)研究

1、莎z #丄兇擁諮妙妙e 了“產(chǎn)八 v fv wu.northwestern polytechnical university ming decollege本科畢業(yè)設計論文題目數(shù)學公式識別技術(shù)研究專業(yè)名稱學生姓名指導教師 畢業(yè)時間畢業(yè)震任務書一、題目數(shù)學公式識別技術(shù)研究二、指導思想和目的要求1、利用已有的專業(yè)知識，培養(yǎng)學生解決實際工程問題的能力;2、鍛煉學生的科研工作能力和培養(yǎng)學生的團結(jié)合作攻關(guān)能力;三、主要技術(shù)指標1. 研究數(shù)學公式識別算法；2. 完成演示程序u!進度和要求第01周第02周:英文翻譯;第03周第04周:學習圖像處理與模式識別算法;第05周第10周: 研究公式識別算法;第11周第

2、16周:設計演示程序;第17周第18周:撰寫畢業(yè)設計論文，論文答辯;五、主要參考書及參考資料koutroumbas3machinepublicat ions2012markov models for pattern recogni t ion: from theory to appl icationsgernot a. fink, springer; 2nd ed. 20142 pattern recognition sergios theodoridis 、 konstantinos、academic press; 4 edition 2008learning in action paper

3、back peter harrington， manning學生 指導教師系主任錯誤！未指定書簽。隨著計算機技術(shù)的發(fā)展和信息技術(shù)與課程的整合，信息化教育越來越受到人 們的關(guān)注。多媒體教學的使用,迫切需要將傳統(tǒng)的鍵盤輸入轉(zhuǎn)化為手寫輸入以提 高課堂的教學效率。但由于手寫數(shù)學公式本身的特點，如數(shù)學符號的相似字符較 多，而r些比較復雜的數(shù)學公式存在著上/下標的定位問題，導致了手寫數(shù)學公 式的識別會相對困難一些。一個手寫的數(shù)學公式識別系統(tǒng),總體上分為字符識別 和公式的結(jié)構(gòu)分析兩個主要的步驟。其中，字符識別是公式識別的基礎(chǔ)。字符識 別分類器的設計直接影響到識別系統(tǒng)的識別率。而結(jié)構(gòu)分析是公式識別的關(guān)鍵。 本

4、文第一章介紹了數(shù)學公式的研究背景，國內(nèi)外的研究現(xiàn)狀以及相關(guān)的一些商業(yè) 化的產(chǎn)品，介紹了數(shù)學公式識別的一般步驟以及本文所做的工作。介紹了一般數(shù) 學符號的預處理和特征提取，以及木文所提出的預處理方法和邊界特征提取方法 和變換進行高維空間的降維，和一些常用的字符識別的一些方法，提出了組合分 類器的思想，以及木文所用的最小距離分類器和改進的神經(jīng)網(wǎng)絡算法對數(shù)學符號 的識別，目的是在能夠識別數(shù)學公式的基礎(chǔ)上,增加了學習的功能，以便今后識別 能力的擴展。然后對數(shù)學公式識別的結(jié)構(gòu)分析和數(shù)學公式的輸出做了闡述。主要 介紹了 £|己如何設計并實現(xiàn)卬刷體數(shù)學公式識別系統(tǒng)，提出了口己的設計思路與 模塊劃分并

5、編寫程序?qū)崿F(xiàn)。木文對公式分析與識別部分做了較深入的研究，主要從以下幾個方面進行了 改進：在公式字符識別階段，針對公式自身的特點，捉出了一種基于連通域搜索的 公式字符切分算法，并通過公式字符識別結(jié)果的反饋信息對粘連字符實行切分， 以改善字符分割的質(zhì)量，在實驗中采用該切分算法取得了比較好的效果。在公式結(jié)構(gòu)分析階段，以公式字符的識別結(jié)果為基礎(chǔ)，根據(jù)字符的結(jié)構(gòu)布局, 采用“自頂向下”和“自底向上”思想相結(jié)合的策略對數(shù)學公式進行結(jié)構(gòu)分析。構(gòu)建數(shù)學公式的符號關(guān)系樹。關(guān)鍵詞：公式識別，二維語法，數(shù)學公式識別，結(jié)構(gòu)分析abstractwith the integration of computer techn

6、ology and the development of information technology and curriculum, information technology education has been paid more and more attention. the use of multimedia teaching, the urgent need to the traditional keyboard input into the handwriting input to improve the efficiency of classroom teaching. bu

7、t because the handwriting characteristics of mathematical formula itself, such as the similar characters more mathematical symbols, and some of the more complex mathematical formulas exist problems / subscript position, led to the recognition of handwritten mathematical formula will be harde匚 a hand

8、written mathematical formula recognition system, two main steps in the analysis structure is divided into character recognition and the general formula. among them, character recognition is the basis of formula recognition. design of character recognition classifier directly affect the recognition s

9、ystem. the structure analysis is the key formula recognition. in this paper, the first chapter introduces the research background of handwritten mathematical formula, the domestic and international research status and some business related to the mathematical formula recognition, introduces the gene

10、ral steps and the work done in this pape匚 the pretreatment and feature extraction, the general mathematical symbols, as well as the pretreatment methods and boundary features in high dimension space of dimension reduction method of extraction and transformation in this paper, introduces some common

11、methods of character recognition, the classifier, and identification of neural network bp algorithm used in this paper, the minimum distance classifier and the improvement of mathematical symbols, the purpose is to recognize mathematical formula, increases the learning function, extended for future

12、identification ability. then the output structure analysis and mathematical formula of mathematical formula recognition.mainly introduced how to design and realize the handwritten mathematical formula recognition system, and proposes a new design and module partition their and programming.this paper

13、 makes a research on the formula analysis and recognition part, mainly from the following several aspects of the improvement:in the stage of formula character recognition, according to the characteristics of the proposed formula, a formula for character segmentation algorithm based on connected doma

14、in search, and the formula of the character recognition result feedback is applied to segment the character, in order to improve quality of character segmentation, the segmentation algorithm used in the experiment has achieved fairly good results.in the formula structure analysis, to identify the fo

15、rmula character based on the results, according to the structure character, the htop-downh and hbottom-uph thought of the method of combining mathematical formula structure analysis. constructing mathematical formula for the symbol relation tree.keywords: formula recognition, two-dimensional grammar

16、, mathematical formula recognition, structure analysis目錄摘要iiabstract iv第1章前言11. 1課題研究的背景和意義11. 2國內(nèi)外公式識別研究狀況和進展21. 3數(shù)學公式識別技術(shù)所要解決的問題以及采用的方法31. 4數(shù)學公式識別技術(shù)研究取得的成果及意義41.4.1符號識別的方法41.4.2符號分割51.4.3分隔符的識別5第2章數(shù)學公式識別系統(tǒng)概況62.1數(shù)學公式的特點62.1.1數(shù)學公式屮的符號62.1.2數(shù)學公式的運算符號62. 13含義的不確定性72. 2數(shù)學公式識別系統(tǒng)的組成結(jié)構(gòu)72. 3數(shù)學公式識別的難點9第3章 數(shù)

17、學公式識別的相關(guān)技術(shù)103. 1圖像預處理103. 1. 1圖像的二值化處理103. 1.2圖像的平滑去噪113. 1.3圖像的細化113. 2常用的幾種字符切分方法113. 2. 1基于結(jié)構(gòu)分析的切分123.2.2以識別為基礎(chǔ)的切分123. 3粘連字符的切分143. 3. 1基于外部特征的粘連字符切分143. 4數(shù)學公式識別中常見的錯誤15第4章公式分析與識別164. 1公式字符識別164. 1. 1預處理164. 1.2公式字符的切分174. 1.3公式符號歸一化234. 14公式字符的識別244. 2公式結(jié)構(gòu)分析254. 2. 1結(jié)構(gòu)分析預處理254. 2. 2結(jié)構(gòu)信息預處理264. 2

18、. 3公式結(jié)構(gòu)分析算法的實現(xiàn)304.2.4公式結(jié)構(gòu)分析結(jié)果31第5章總結(jié)335. 1論文總結(jié)335. 2下一步工作33致謝35參考文獻36畢業(yè)設計小結(jié)391.1課題研究的背景和意義隨著人類社會信息化程度的口益提高，將卬刷文檔轉(zhuǎn)化成相應的電了文檔成 為一個亟待解決的問題。利用ocr （optical character recognition,光學字符 識別）技術(shù)將印刷文檔輸入計算機，是口前公認的信息數(shù)字化的高校手段。經(jīng)過 兒十年的發(fā)展，ocr技術(shù)已經(jīng)進入了實用階段，而且其速度和準確率也達到了令 人滿意的程度。近年來，在ocr技術(shù)的基礎(chǔ)上，結(jié)合字體識別、表格識別技術(shù)， 已經(jīng)初步實現(xiàn)了原文版面的重

19、構(gòu)與再現(xiàn)，這樣就可以方便的編輯和排版。但冃前 這類文檔識別系統(tǒng)（ocr軟件）對數(shù)學公式束手無策，只能按照圖像進行保存這 樣就不能對文章的公式進行編輯也不能依據(jù)公式內(nèi)容對文章進行檢索。絕大多數(shù) 科技文獻的核心內(nèi)容就是數(shù)學公式，失去了公式的文章也毫無意義。所以印刷文 檔屮數(shù)淫公式的處理在ocr系統(tǒng)屮占舉足輕重的地位。木課題研究的是數(shù)學表達式中符號的識別，木課題研究的實際意義可以分為 以下幾個方面：（1）數(shù)學公式的檢索，提高文獻的科技性。在科技高速發(fā)展的現(xiàn)代，許多科技文獻中包含大量的公式，它們有的和文檔種的 文字混雜在一起（內(nèi)嵌），冇的公式獨占一行，由于目前沒冇一種ocr能夠正確 的識別文獻中的數(shù)學

20、公式，這些公式都是以圖片的形式存在的。當人們對科技文 獻數(shù)字化時，其中的格式只能按照圖像格式進行保存，而不能加以識別分析。這 樣就不能依據(jù)公式對文章進行檢索，而有的文章的核心內(nèi)容就是這些公式，失去 了公式的文章可能毫無意義，因而降低了文章的科技性和應用性。（2）使公式的輸入自動化，解決手動輸入的低效率問題。隨著計算機的普及，在各領(lǐng)域內(nèi)有越來越多的人耍借助于就計算機來解決科學上 問題，當人們想驗證或重用某些數(shù)學公式時，只能使用專門的計算機軟件（如 matlab）或數(shù)學排版軟件（如公式編輯器）按照其語法規(guī)則重新輸入，即使是使 用可視化的數(shù)學公式軟件輸入速度也不可能得到太大的提高。由于數(shù)學表達式處

21、了英文字符和阿拉伯數(shù)字外，還包括許多特殊的字符和希臘字母，使其輸入過程 復雜繁瑣，既耗吋又費力，且速度慢。長期以來計算機數(shù)據(jù)輸入因其速度慢、誤 碼率高而成為計算機應用中的“瓶頸”。（3）節(jié)省空間，提高網(wǎng)絡傳輸速度。隨著互聯(lián)網(wǎng)的廣泛的使用，人們傳遞信息的方式有原來的郵寄信件的形式轉(zhuǎn) 向現(xiàn)在的電子郵件，省時又省力。而含冇大量公式的文獻在網(wǎng)絡的傳輸中，由于 公式的圖像格式占空間極大，影響傳輸速率。正是這些因素引起人們的注意開始 著手這一課題的研究。1.2國內(nèi)外公式識別研究狀況和進展公式識別問題于1968年由anderson在他的博士論文屮首次提出，但直到九 十年代才成為研究的熱點。數(shù)學公式識別技術(shù)發(fā)

22、展如此緩慢，與數(shù)學公式自身特 點給公式識別所帶來的困難是分不開的。首先，數(shù)學公式屮所包含的符號種類特 別多，如英文字母、希臘字母、運算符號等；而且根據(jù)這些符號所起作用的不同, 在尺寸、位置、形態(tài)上很大差異，例如上下標的尺寸遠小于一般符號，而功能符 號（如h）尺寸會比一般符號好很多；構(gòu)成函數(shù)的字符多為正方形，而表示變量 的字符多為斜體。另外公式符號筆畫少、相似性高、不易區(qū)分。因此公式符號的 切分與識別遠比簡單的一維分布的普通文本復雜的多。到目前為止，已有一些文章專門探討數(shù)學公式處理某一方面的基木方法，如: 公式含義的分析，公式的定位，符號的切分識別等。也冇一些文章不但提出了基 木處理方法，還構(gòu)造

23、了比較完整實驗系統(tǒng)或針對特定情況處理的實際系統(tǒng)，但還 沒有成型的產(chǎn)品問世。多數(shù)論文在討論中沿用了傳統(tǒng)的切分和識別方法，沒有考 慮到公式的特殊情況。在為數(shù)不多的涉及公式符號切分和識別的方法屮，切分環(huán) 節(jié)多是利用投影或間隙特性，而識別方法仍采用傳統(tǒng)的模板匹配法、結(jié)構(gòu)分析法 和神經(jīng)網(wǎng)絡法等。okamoto和miac21提出的系統(tǒng)首先運用了遞歸目標結(jié)構(gòu)分析法 來分割字母和符號，同吋建立關(guān)系樹，然后用傳統(tǒng)的模板匹配法識別符號。lee 提出了一個識別印刷體數(shù)學公式的系統(tǒng)。首先運用傳統(tǒng)的統(tǒng)計方法來識別單個字 母和符號，然后用面向過程的方法將二維結(jié)構(gòu)的公式轉(zhuǎn)換為一維結(jié)構(gòu)的字符串。 lee和wang提出了既能識

24、別文木又能識別數(shù)學公式的系統(tǒng)，在理解公式的同吋 應用特征提取技術(shù)和最近鄰算法來識別算法來識別字符，建立符號關(guān)系樹來描述 表達式。此外，還捉出了用于糾正識別錯誤的一些啟發(fā)式規(guī)則。fateman設計了 一個典型的系統(tǒng)，該系統(tǒng)能成功將的排好版的數(shù)學公式轉(zhuǎn)換成lisp表達式。對 識別部分采用了不同的方法，如計算用的hausdorff距離和符號灰度值的計算。對 結(jié)構(gòu)分析部分而言，運用了一個簡單的遞歸降序分割法。該實驗表明最初的由上 而下的設計面臨噪聲數(shù)據(jù)時應用很有限，因此，一個更加結(jié)構(gòu)化的由上至下的方 法替代它獲得了高水平的性能。國內(nèi)對數(shù)學公式識別的研究尚處于起步階段，冃而還沒有成形的卬刷體公式 識別的

25、系統(tǒng)問世，主要研究機構(gòu)冇南開人學機器智能研究所，哈爾濱工程人學自 動化學院，沈陽工業(yè)大學和大連理工大學等等，已有40多篇相關(guān)的論文發(fā)表。綜上所述，卬刷體數(shù)學公式的識別是當前ocr識別技術(shù)研究的難點，距離實 用述冇很大的距離。1.3數(shù)學公式識別技術(shù)所要解決的問題以及采用的方法數(shù)學表達式的識別研究到今天，經(jīng)過研究者們的努力，已經(jīng)取得了一定的成 績。但是，隨著技術(shù)的進步以及人們認識的深入，數(shù)學表達式的識別述存在許多 問題，等待研究者們更進一步的研究。根據(jù)現(xiàn)階段的研究情況，簡耍提出以下幾 點。模糊問題-一當表達式?jīng)]有被正確打印或書寫吋，模糊將會出現(xiàn)，有研究者 建議用上下文信息來解決這一問題，可提供多個

26、答案來參考，這問題的研究仍處 于初期，冇待更進一步的研究。在過去，一些研究者在沒有任何實驗結(jié)杲報告的情況卞，將他們所強調(diào)的純 理論性的問題公布出來。而對于那些進行了實驗的人，他們的性能評估方法粗略 的可分成以下三個主要類別。一是依據(jù)測試結(jié)果是正確的識別還是錯誤的識別來 分類，二是依據(jù)被測試表達式的符號的識別速率進行分類，三是對一個或兒個書 寫著工整寫出來的典型表達式進行識別，結(jié)呆所冇的表達式都能夠被正確的識別 出來，這一實驗的目的是顯示這一方法至少對那些典型表達式有用。數(shù)學表達式是由可能非常大的一組字母和字符組成，并且不同學科的表達式 的符號具冇其專業(yè)的語言特性，這使得現(xiàn)冇的系統(tǒng)不得不利用_些

27、符號組和語法 限制條件，當一個識別系統(tǒng)被應用于其他領(lǐng)域時，就需要進行語法修改，甚至有 時候需要重新設計一個系統(tǒng)，這就對研究者們提出了一個強烈要求，設計一個通 用性比較強的系統(tǒng)來進行數(shù)學表達式的識別?，F(xiàn)階段數(shù)學表達式的應用主要是在程序的編輯上，也許不久的將來，基于筆 寫計算機程序和智能輔助系統(tǒng)將被研究用于學生的數(shù)學學習。這i切都需要研究 者們付出更多的努力來實現(xiàn)它們。伴隨著基于筆寫計算技術(shù)近來的高漲和光學掃描技術(shù)的發(fā)展，我們己經(jīng)擁有 了將數(shù)學表達式輸入到計算機屮的所冇必備的碩件設備，關(guān)鍵的問題是數(shù)學表達 式的口動識別，即更重要的在于軟件方面了。數(shù)學表達式有兩個主要階段組成， 即符號識別和結(jié)構(gòu)識別

28、。在本文中我們依據(jù)識別過程的每個階段介紹了許多方 法，在符合識別小使用了模板匹配、結(jié)構(gòu)、神經(jīng)網(wǎng)絡、統(tǒng)計學等方法，在結(jié)構(gòu)分 析中大部分是采用語法規(guī)則依據(jù)上下文來分析數(shù)學表達式。顯然，數(shù)學表達式識 別屮述冇一些問題等待人們一些問題去解決，隨著我們將數(shù)學表達式應用到實際 中后，會有更多的應用性問題顯現(xiàn)出來，那時就需要研究者們?nèi)ソ鉀Q更多復雜的 難題，去完善數(shù)學表達式的識別系統(tǒng)。1.4數(shù)學公式識別技術(shù)研究取得的成果及意義141符號識別的方法公式中字符的識別，即識別系統(tǒng)的低級識別是要分割并識別出數(shù)學公式中的 所有符號。就具體的分割方法就不做研究，在數(shù)學表達式屮存在一些比較特殊的 符號，在隨后簡單的分析一下

29、。一般系統(tǒng)都采用連通體的方法來進行字符分割的。 要對以下三種情況進行連通體合并：字符在垂直方向可分為多個連通體，例如“i、j、二”等；字符在水平方向可分為多個連通體，例如“、>>”等；大連通體包含小聯(lián)通體，例如“o”。經(jīng)過三十多年的研究，許多現(xiàn)存符號識別技術(shù)己經(jīng)能夠獲得相當令人滿意的 結(jié)果。但是這些識別技術(shù)屮大多數(shù)技術(shù)只能識別獨立的符號，而在數(shù)學公式屮存 在復合的字符，為了止確識別數(shù)學公式首先必須將符號準確的分割出來，因此有 符號的識別符號的分割兩大階段。1.4.2符號分割符號的分割首先采用公式定位技術(shù)，確定公式的位置，然后對公式中的毎一 個符號根據(jù)分割技術(shù)進行分割，符號分割最基本

30、的方法是將所冇物理結(jié)構(gòu)獨立的 部分分成一組，而像i、j、二這樣的符號有多組分構(gòu)成，我們必須將相關(guān)聯(lián)的部 分連起來以正確的識別這類單個的字符和字母，還有如、類符號，在它們的冇效 區(qū)域內(nèi)通常包含其他的字符，即子表達式?，F(xiàn)存的比較突出的分割方法有以下幾 種：（1）兩個分類模塊結(jié)合法，采用數(shù)據(jù)驅(qū)動分類模塊建立給定數(shù)學表達式的 關(guān)系樹，根據(jù)x軸和y軸上的對象可以決定如何將數(shù)據(jù)分類，然后用知識驅(qū)動分 類模塊嘗試修正出數(shù)據(jù)模塊建立的關(guān)系樹，試著將不同的部分聯(lián)系到一起。（2）通過水平和垂直結(jié)構(gòu)分割，將給定數(shù)學表達式分割為各組分，對含有 多個組成部分的符號要進行額外的檢查。（3）用符號的bounding box

31、es法將符號從數(shù)學表達式屮表達出來，又陳遞 歸x-y分割法，其中x為水平分割，y為垂直分割。1.4.3分隔符的識別符號被正確的分割后，我們擁有了一系列作用值得對象，但尚不知道符號 在數(shù)學公式中的準確意義。理論上我們可以在他們被設計相應的數(shù)據(jù)類別時應用 符號識別方法進行識別。經(jīng)過多年的研究，不同的方法被用于不同的符號識別， 現(xiàn)在被研究的主要的識別方法有模板匹配法、結(jié)構(gòu)分析法、神經(jīng)網(wǎng)絡法以及其它 的統(tǒng)計方法。第2章數(shù)學公式識別系統(tǒng)概況數(shù)學公式是絕大多數(shù)科技文獻的重要組成組成部分，由于包含許多鍵盤無法 直接輸入的特殊符號，手工輸入困難，因此，研究公式自動輸入技術(shù)勢在必行。 公式口動分析與識別技術(shù)研究

32、的主要困難來門于公式的二維歐套結(jié)構(gòu)和所包含 符號含義的不確定性。2.1數(shù)學公式的特點在文檔中，數(shù)學公式在結(jié)構(gòu)上區(qū)別于一般文字的主要特點是:將大小不一定 完全相同的符號按一定的規(guī)則排列成一個二維層次結(jié)構(gòu)。主要體現(xiàn)在以下幾個方 面：2丄1數(shù)學公式中的符號數(shù)淫公式符號可分為基本符號和特殊符號，如綁定符號、界定符號、運算符 號等，它們有口己的組織準則，如加號必須有2個操作數(shù)等。對于基本的符號一般有以下形成規(guī)則：（1）大小相同且相鄰的數(shù)字應該是一 個整體，相鄰但大小不同的就不能成為一個整體，如5浙就不能作為一個整體。（2）兒個相鄰的字母有可能形成一個整體，如函數(shù)名（tan ,sin）等，但有時 也代表2

33、個變量的乘積，如cd,它表示c*d。（3）除了字母和數(shù)字的其它符號應 該獨自形成一個整體。對于特殊的符號一般有以下3種：（1）綁定關(guān)系符號，如：分數(shù)線、等， 它們同作用域屮子表達式綁定在起，比如：屮綁定兩個子表達式3、i+e （2） 界定符號，如括號它將界定符號間的內(nèi)容看作一個完整的部分，它具有更高的運 算優(yōu)先權(quán)。（3）運算符號，如：+、-、等，它們都約束著各自的操作數(shù)。 2.1.2數(shù)學公式的運算符號數(shù)學公式的運算符號包括顯式運算符號和隱式運算符號。顯式運算符號就是 通常的運算符號，可以根據(jù)它們的運算優(yōu)先權(quán)規(guī)則來確定運算關(guān)系。如果公式不 是線性的。如c+b/d,可以根據(jù)運算符號的作用域來確定它

34、們的運算關(guān)系。隱式 運算符號曲相對位置來確定運算關(guān)系，而沒有明顯的運算符號，如上標、下標式 的乘號。例如cd表示變量c和變量d相乘：在2a'p a是2的上標，而在b3»p 3 是b的下標。2.1.3含義的不確定性同樣的符號，在不同的位置，其表示的含義可能不相同。例如，i員i點可能表 示乘，可能表示小數(shù)點。在一些數(shù)學公式圖像還可能是噪聲等。比如dy在公式 中dy表示積分變元,而在公cd+dy中表示d和y相乘。2.2數(shù)學公式識別系統(tǒng)的組成結(jié)構(gòu)科技文檔不僅包含普通文字、圖像、圖形，還包含大量的數(shù)學公式。數(shù)學公 式識別系統(tǒng)的構(gòu)建經(jīng)過三個步驟：公式提取、公式分析與識別和公式的重構(gòu)。印

35、刷體數(shù)學公式識別過程如圖2. 1所示。其中橢圓的部分是公式分析和識別部分， 也是整個識別系統(tǒng)的核心部分。何1）掃描輸入圖像：原始圖像通過光電掃描儀、數(shù)碼攝像機、ccd器件或電 子傳真機等獲得二維圖像信息。2）圖像預處理：包括對原始圖像去噪、傾斜校正或各種濾波處理。3）數(shù)學公式的提?。簲?shù)學公式與普通文字區(qū)別很大，在科技文獻中，在很多 情況都是文本和數(shù)學公式混合在一起的，耍想真正處理數(shù)學公式，就必須 從原始的圖像中找出數(shù)學公式所在的區(qū)域，以便以后使用專門的方法處理， 所以，識別前需要從文檔中找出數(shù)學公式，即頁面分割，這是公式識別的第 一步。4）公式分析與識別：一般分為兩個階段：字符識別和結(jié)構(gòu)識別。

36、在字符識別 階段，主耍是采用恰當?shù)乃惴▽ψ饺〕龅臄?shù)學公式進行精確的切分，從切 分得到的單個公式字符圖像上提取統(tǒng)計特征和結(jié)構(gòu)特征，包括為此而做的細 化，歸一化等步驟，并從學習得到的特征庫找到與待識公式字符相似度最高 的字符類；在公式結(jié)構(gòu)分析階段，主要是在正確的切割并識別公式的每個符 號的基礎(chǔ)上，采用某種最佳策略分析符號之間的關(guān)系并進行公式符號組合， 進而確定公式符號間空間關(guān)系、符號間邏輯關(guān)系，達到理解公式含義的目的, 并將公式的分析結(jié)果用關(guān)系樹或分析樹的形式表現(xiàn)出來。公式分析與識別部 分是整個卬刷體公式識別系統(tǒng)的關(guān)鍵環(huán)節(jié)，它直接影響整個識別系統(tǒng)的性能 和效率。5）數(shù)學公式的重構(gòu)：利用前面兩部分的

37、分析、識別結(jié)果，生成通用的、公式 的原貌的電子文檔，以便進一步排版、儲存等，從而避免了手工輸入的這一 繁重勞動。冋m/圖像預處理數(shù)學公式的提取 數(shù)學公式的切分公式字符特征的提取公式字符的識別數(shù)學公式的結(jié)構(gòu)分析圖2.1印刷體數(shù)學公式識別的簡單過程公式識別模塊是整個數(shù)學公式識別系統(tǒng)的關(guān)鍵環(huán)節(jié)。由于公式屮包含數(shù)字、 英文字母、希臘字母、運算符號等多種類型的字符和符號，大小不一，正斜體變 化頻繁，且在空間上呈二維嵌套分布，使得傳統(tǒng)的、比較成熟的ocr核心對公式 符號的切分準確率和識別率都很低。因此，有必耍針對公式的特點，研究專門的 公式符號切分和識別算法。公式符號的識別性能直接影響結(jié)構(gòu)分析和重構(gòu)等環(huán)節(jié)

38、 的正常進行，并最終影響公式識別系統(tǒng)的整體指標，鑒于公式符號的獨特之處， 研究準確性高，適應公式特點的字符切分與識別方法，是十分重要的。因此，它 是數(shù)學公式識別系統(tǒng)的核心。2. 3數(shù)學公式識別的難點數(shù)學公式識別技術(shù)如此緩慢，是與數(shù)學公式本身的特點分不開的。在數(shù)學 公式屮，字符和符號是按二維嵌套結(jié)構(gòu)分布的，并冃字符大小不一樣，這使得 公式字符定位和識別相當困難，總的來說，數(shù)學公式識別存在著以卜幾個難點： 公式中字符出現(xiàn)的位置是隨機的，沒冇一定的規(guī)律，冇吋只能根據(jù)上下文來 判斷一個字符是否為公式字符的一部分，這給公式小字符定位帶來很大的困 難。 一些公式屮的字符存在粘連現(xiàn)彖，嚴重彩響了切分和識別。

39、公式中一些字符有很多部件組成，寬窄不一，給切分造成了不便。本文對公式分析和識別做了較深入的研究。在公式字符識別階段，提出了一 種基于連通域搜索的公式字符切分算法，并利用基于識別的切分方法，通過公式 字符識別結(jié)果的反饋信息對粘連公式字符實行再切分，進而實現(xiàn)了公式字符的高 效切分和識別；在公式結(jié)構(gòu)分析階段，以公式字符的識別結(jié)呆為基礎(chǔ)，根據(jù)公式 字符的結(jié)構(gòu)布局，采用“自頂向下”與“ 口底向上”相結(jié)合的策略對數(shù)學公式進 行結(jié)構(gòu)分析，構(gòu)建數(shù)學公式的識別系統(tǒng)，以備公式重構(gòu)使用。第3章數(shù)學公式識別的相關(guān)技術(shù)公式識別與分析是公式識別系統(tǒng)的必要環(huán)節(jié)，公式字符切分的好壞與公式結(jié) 構(gòu)分析的準確與否直接彩響數(shù)淫公式的

40、識別效果，因此，選擇一種恰當?shù)墓阶?符切分算法和最佳的公式結(jié)構(gòu)分析策略是止確識別數(shù)學公式的關(guān)鍵。本章主耍介 紹了圖像處理和幾種常用的字符切分技術(shù)和傳統(tǒng)的公式結(jié)構(gòu)分析策略。3.1圖像預處理圖像處理，包括圖像增強、圖像復原，圖像分割、邊緣檢測等，它的輸入是 圖像，輸岀是經(jīng)過處理的圖像。在自動處理數(shù)學公式系統(tǒng)中，因現(xiàn)在只研究印刷 體的識別，故只需要進行圖像處理屮的圖像的分割和邊緣檢測即可。圖像識別，它是模式識別的一個分支，輸入是圖像，輸出是圖像的分類和結(jié) 構(gòu)描述。圖像理解，它屈于人工智能領(lǐng)域。它的輸入是圖像，輸出是對圖像的理 解和描述。3.1.1圖像的二值化處理預處理是字符識別的重要環(huán)節(jié)之一，它把

41、原始圖像轉(zhuǎn)換成識別器所能接受的 表達形式(二值化)，消除一些與類別無關(guān)的因素(尺寸與位置的固定化)。我們 在電腦屏幕上看到的圖像都是由許多的點構(gòu)成的，這些點稱z為像素，是用掃描 的方法進行顯示的，圖像掃描后以一個二維的像素矩陣點陣形式存儲在計算機內(nèi) 部，就稱之為位圖。現(xiàn)今人多數(shù)掃描儀在進行二值圖像掃描時，都是通過一個固 定的閾值將圖像的灰度值做二值化處理，如公式所示：f (x, y)其屮k稱為二值化閾值，當釆樣點(x, y)的灰度值f(x, y)大于或等于k值， f(x, y)取,小于k時,取0,表示背景部分。3.1.2圖像的平滑去噪數(shù)字圖像在生產(chǎn)過程中，曲于數(shù)字化設備等原因經(jīng)常受到噪音污染，

42、因此對 數(shù)字圖像應進行去噪處理。傳統(tǒng)的去噪?yún)鸱椒ㄊ腔诟道锶~變換的信號去噪?yún)鸱?法，可以使得信號和噪音的重疊部分盡可能小，這樣就可以在頻域通過時，不需 改變?yōu)V波方法而將信號和噪音分隔開。但如果信號和噪音的頻域重合時，用這種 方法進行去噪處理的效果較茅。這一缺陷使得眾多的學者們開始尋找更好的解決 方法。小波變化的粗至精的多分辨分析能力和在吋域和頻域突出信號的局部特征 的能力在圖像處理、計算機視覺、模式識別等領(lǐng)域表現(xiàn)了巨大的前景，許多學者 研究了將小波變化用于噪聲的去除。去噪聲的方法如下：(1) 計算離散小波變換。(2) 在小波變化域?qū)π〔ㄏ禂?shù)進行閾值處理。(3) 計算逆離散小波變換。3. 1.3

43、圖像的細化在計算機模式識別屮，為了方便圖像特征的抽取，一般都先進行圖像的細化 處理。圖像細化就是把二值圖像中具有一定寬度的細條狀區(qū)域變成一條薄線，細 化處理能去除字符上不影響連通性的輪廓像索，獲得單位寬度的中心骨架。圖像 細化大大壓縮了原始圖像的數(shù)據(jù)量，并能保持其形狀的基木拓撲結(jié)構(gòu)不變，為字 符識別中的輪廓跟蹤及特征抽取等后續(xù)工作奠定了基礎(chǔ)。細化應滿足以下條件：(1) 將條形區(qū)域變成一條薄線；(2) 薄線應位于原條形區(qū)域的中心；(3) 薄線應保持原圖像的拓撲特性。3.2常用的幾種字符切分方法字符切分是將版面分析得到的文本塊切分成單字圖像，以利于ocr的處理。 字符切分近幾年來一直是ocr領(lǐng)域中

44、的關(guān)鍵問題。較高的單子識別正確率與無限 制印刷體或手寫體文木的識別正確率之間的差距正說明了這一點。而且口前在文 字識別領(lǐng)域所取得大部分進展都可歸功于文字切分水平的提高。同樣，數(shù)學公式 的識別也受限于公式字符的切分。傳統(tǒng)的字符切分主要有三種基本方式：其一，是基于基本結(jié)構(gòu)的切分，即從 圖像特征中尋找字符切分規(guī)則，該方法主要是根據(jù)字符的形狀和特征結(jié)構(gòu);其二, 是基于整體策略的切分，即系統(tǒng)將字符串作為一個整體進行詞識別而不是字識 別，在這種方法加入了上下文關(guān)系等先驗知識；其三，是以識別為基礎(chǔ)的切分， 通過識別反饋判斷切分結(jié)果是否正確。3.2.1基于結(jié)構(gòu)分析的切分這類方法主要是利用了漢字是方塊字的幾何特

45、性，如每個漢字的寬和高都基 木相同，字與字之間的間距也大致相同等，將文木分割成多個有意義的單元。lu 等人提出了兩種基于字符結(jié)構(gòu)分析的垂直投影切分算法。（1）第一種切分算法主耍依據(jù)字寬和零值劃分的空白間隙，采用投影的方 法切分字符。該算法的缺點就是，在字符粘連的情況卜顯得無能無力。（2）另一種切分方法是周期字間距檢測法（gdp）o首先，該方法利用多行 垂直投影部分去檢測待切分區(qū)域屮最合適的偏移和傾斜度的大小，傾斜度的估計 是基于垂直投影的平均字間距長。如果這兩種方法的估計超過了經(jīng)驗閾值，或估 計的傾斜度大小遠大于平均字行高度，則字體并不是固定大小，需用其他方法， 一般在具體確定切分參數(shù)時，根據(jù)

46、漢字形狀和結(jié)構(gòu)特點，主觀的加入一些邏輯判 斷。該切分方法的缺點是：（1）分析漢字形狀和結(jié)構(gòu)特點時工作量較大，且比較 繁瑣，例如從語言文字學的角度出發(fā)對漢字結(jié)構(gòu)進行了分析。（2）對漢字的形狀、 結(jié)構(gòu)的分類沒有確切的最優(yōu)解，例如目前尚無“部件”概念的明確定義；（3）描 述規(guī)則比較復雜，其至需要專家系統(tǒng)；（4）不易擴展功能，如增加字體或漢字、 數(shù)學公式、英文混排時，原規(guī)則需耍較大的改變。最主耍是數(shù)學公式中字符大小 不一，用基于結(jié)構(gòu)分析的方法對公式字符進行切分，誤切率很高，比如根號表達 式屮的公式符號就不能正確切分，所以基于結(jié)構(gòu)分析的切分方法對數(shù)學公式的適 應性欠佳。3.2.2以識別為基礎(chǔ)的切分這類方

47、法的基本原理是以識別信度作為切分標準，利用一個大小可變的滑 動窗口來得到若干候選切分序列，每一序列作為一個整體用其識別結(jié)果進行評 價。評價簡單的歸于各個切分塊的識別情況，也可以基于詞匯和語法、詞義等上 下文知識。在這類方法中，字符切分是字符識別的副產(chǎn)品，而字符識別本身可由 上卜文分析得到的。基于識別的切分方法主要涉及到以卜技術(shù)：滑動窗口方法、 閉環(huán)切分識別和多假設方式。（1）kovalesky對滑動窗口法做了如下描述：用一個固定窗口沿一行字符圖像 移動，把落入的窗口的部分送入識別器，若與原型相匹配，滿足某些識別條件， 則予以承認。不過kovalesky也指岀，在實踐中仍會岀現(xiàn)一些差錯，這是由于

48、兩 個相鄰字符的一部分落入窗口時可能會與第三個字符相似，例如相鄰的字符“0”和“c”可能組成一個字符。為此kovalesky建議要將正行字符一起考慮。（2）casey和nany提出了一個閉環(huán)切分識別方法，只有一個字行能被分割成一 組，可識別字符時才接受這個句子。它們的方法可用圖3-1表示。窗口參數(shù)圖3-1閉壞切分識別方法示意圖該算法以整行字符作為輸入，曲一個切分監(jiān)督器ss把窗口初始化為整個圖 像的寬度，如果圖像中只有一個字符，則分類器一開始就認出該字符。如果分類 器拒識，則從右側(cè)開始縮小閱讀窗口，直至分類器能夠有效識別窗口內(nèi)圖像或者 窗口變得太小。如果分類器成功識別字符序列,ss記錄該識別效果

49、，標記窗口右 側(cè)為截舍點，復位閱讀窗，左側(cè)對應丁截舍點，而右側(cè)仍然是原圖像末尾。重復 上述操作直到整個切分過程結(jié)束。（3）多假設識別方法包括以下兩個步驟；首先，產(chǎn)生若干假設切分。然后, 選擇最佳假設，這種最佳假設就成為最佳切分路徑，從而得到切分結(jié)果。由于這種基于識別的切分技術(shù)可以容忍遠大運算量及其具冇上述兩個特點， 因此它能夠比其它兩種切分方法更適于手寫漢字的切分。(4) 該方法首先用一個切分算法對整個圖像進行“最大可能”的切分，不 考率是否將字符切錯或切碎，這樣就可以將這些切分點進行組合，得到一系列的 候選切分方案，然后對切分后的字符進行識別，從識別的結(jié)果屮選取一個最好的 切分方案作為切分結(jié)

50、果。在文獻中有一個這種方法的簡單例子，它由一個切分算 法得到大量的候選切分點，然后將相鄰的候選切分點進行組合，并對切分后的字 符進行識別，如果識別結(jié)果得到較高的可信度，就將組合后的切分點作為切分最 佳切分方案。曲于該算法可以通過大量的先驗知識來進行切分指導和判斷，所以 它在具有一定先驗知識的領(lǐng)域應用前景很廣。3.3粘連字符的切分出于印刷質(zhì)量或其它問題，在包含數(shù)學公式的印刷文檔中粘連的字符。為了 正確識別這些字符，必須對粘連字符進行切分。粘連字符的切分技術(shù)可以別分為 兩類：基于外部特征的方法和基于識別的方法。3.3.1基于外部特征的粘連字符切分這類方法是通過統(tǒng)計字符吊圖像每一列的黑像素在水平方向

51、上的投影，查找 連續(xù)字符之間的空白區(qū)域和粘連區(qū)域，確定分割點的位置。其特點是速度比較快, 實現(xiàn)較簡單，但該方法存在以下不足：(1) 對粘連程度的限制比較苛刻只能適應簡單粘連的情況。(2) 即使對簡單粘連的情況，也要求粘連區(qū)在垂直方向不宜過寬，至少應明 顯小于字符的筆畫寬度才能定位，針對該點的不足，文獻通過腐蝕粘連字符的 外輪廓來減弱粘連程度，但改進算法僅適用于粘連處兩側(cè)冇較強波峰情況，且 只能減少一到兩行像素寬度，作用有限。(3) 由于字符可能存在退化現(xiàn)象，該方法常將一個獨立字符中的細筆畫誤認 為粘連區(qū)，如字符u就冇可能因底部被切開而誤認為11。如圖3-3所示。圖3-3字符的退化3.4數(shù)學公式

52、識別中常見的錯誤數(shù)學公式的二維嵌套特性、所包含符號的復雜性及多樣性，使得數(shù)學公式的 識別出現(xiàn)錯誤，常見的錯誤冇：（1）常規(guī)ocr字符切分方法主要用于一維線性結(jié)構(gòu)文字，而公式的結(jié)構(gòu)是二 維的，所以傳統(tǒng)的字符切分方法對數(shù)學公式中包含特殊字符（如：”等）的表 達式切分錯誤，例如，利用傳統(tǒng)的字符切分方法對圖3-4所示的數(shù)學公式進行切 分，“”中的子表達式就不能被正確分割。（2）特征的選擇和捉取沒有固定的標準，由于對特征選擇不當，會造成一些 相似字符識別不清,如o,0, d, s, s,5«如圖3-5所示。（3）數(shù)學公式符號之間的空間關(guān)系比較復雜，出于對數(shù)學公式結(jié)構(gòu)分析策略 選擇不佳，容易造成

53、一些空間運算符識別錯誤，如圖3-6所示。圖3-4公式的誤切示例識別結(jié)果原始公式圖3-5公式中相似字符誤識示例原始公式識別結(jié)果圖3-6公式中空間運算符的誤識示例第4章公式分析與識別公式分析和識別是整個數(shù)學公式識別系統(tǒng)的關(guān)鍵環(huán)節(jié)，直接影響對公式的理 解與重構(gòu)，一般來說此階段的工作分為兩部分：公式字符識別和公式結(jié)構(gòu)分析。 4.1公式字符識別在ocr領(lǐng)域，現(xiàn)冇的識別技術(shù)已經(jīng)能夠獲得相當令人滿意的結(jié)果。但是這些 識別技術(shù)往往只能識別獨立的符號。而數(shù)學公式中存在復合結(jié)構(gòu)的符號，這給識 別工作帶來了很多困難。為了正確識別數(shù)學公式，首先必須將公式符號準確的分 割出來。符號的識別階段包括三個階段，即預處理（平滑

54、去噪）、符號切分（分 離符號）、符號識別。因為預處理相對來說比較簡單，容易得到理想的結(jié)果，預 處理過程后得到了細化的二值化公式圖像。因此在公式符號識別階段，符號的分 割和符號的識別成為研究者們主要研究的目標。整個公式字符識別過程如圖4-1 所示。圖4-1數(shù)學公式字符的識別過程示意圖4.1.1預處理噪聲是對數(shù)淫公式識別效果產(chǎn)生彩響的因素。然而在現(xiàn)實系統(tǒng)屮，噪聲是不可避免的。可以采用圖像平滑等技術(shù)來去除噪聲，從而加強有用信息。4.1.2公式字符的切分目前，在印刷體文本等規(guī)范文字符號的切分和識別方面，已經(jīng)冇了比較成熟 的方法。而專門針對印刷體數(shù)學公式的分割識別方法，迄今為止，還沒有取得滿 意的實用成

55、果。首先數(shù)學公式字符的分割做一個簡單了解。我們首先使用前而介紹的圖像預處理方法對其二值化并進行去噪和細化，得 到效果比較理想的圖片作為輸入。公式的字符分割可以使用連通域法。定義對于二值圖像，1代表有像索，0 代表無像素。1. 以一個值為1的點為起 點，向八領(lǐng)域搜索各個1值點；2. 對各個1值點再進行同 樣的八領(lǐng)域搜索，直到遇到像索值0且八領(lǐng)域值都為0的點；3. 記錄這次搜索途徑1值 的點的坐標，建立新的數(shù)組，就分割岀一個字符；4. 遞歸分割直到遍丿力各個 點，就可以分割出各個字符，并分別存入數(shù)組中。4.1. 2.1數(shù)學公式中的符號具有如下特點：（1）字符木身的形態(tài)不規(guī)范（有很多希臘字符）。（2

56、）大小、字體等變化較多。（3）字符集較大。常見的公式符號見圖4-2：圖4-2部分數(shù)學公式的符號示意圖現(xiàn)已提出的比較典型數(shù)學的數(shù)學公式切分方法冇以下幾種：faure和wang設計了一種手寫體數(shù)學表達式的系統(tǒng)。問在這個系統(tǒng)屮分為 基于數(shù)據(jù)的模塊和基于知識的分割模塊。前者首先建立公式的關(guān)系樹，利用圖像 在x軸和y軸的投影來決定如何分割公式，但這很難分割出含有“”和分數(shù)線 的公式；后者用于調(diào)整前面的關(guān)系樹，如將一個有多個組成部分的符號（如“”、 “”、“”）合并成整體。okamoto等通過水平和垂直方向投影的遞歸分割方法來分割印刷體數(shù)學公 式。冋但這種算法對諸如“”、“”、“ ”類的符號的分割需要一些

57、額外的處理。smithies等提出一種數(shù)學公式切分算法。刪首先，利用該算法產(chǎn)生所有可 能的分割基元，然后，符號識別器根據(jù)他們的口j信度進行基元的合并。這種算法 簡單而且速度快，但出錯較多，而且需要人工糾錯。這兒種典型的切分方法在對數(shù)學公式字符進行切分時，各有利弊，切分結(jié)果 你很理想。本文通過對上述方法的分析，真的這些切分方法中存在的問題，捉出 了一種基于連通域搜索的切分算法。采用這種算法對公式字符進行分割，能獲得 較好的切分結(jié)果。4. 1.2.2基于連通域搜索的切分算法描述該算法只需要對公式圖像進行“自頂向下”和“自底向上”遍歷，就可以將 圖像屮的所冇連通區(qū)域坐標信息記錄下來，供分析、處理使用。其核心思想是開 辟了一塊陳為“中介緩沖區(qū)”的、能夠儲存一行圖像數(shù)據(jù)的內(nèi)存單元。利用此緩 沖區(qū)來記憶當前掃描行以前各行的行程鄰近情況。在掃描開始之前，將“中介緩 沖區(qū)”清0,在每一次掃描行之前，將“中介緩沖區(qū)”屮不為0的點置1,將當 前行不為0的點置2,這樣，在將當前行與“中介緩沖區(qū)”進行“或”運算后, “屮介緩沖區(qū)”各點的值就反映出了當前行及英以前行之間的