吳家明, 李家豪, 包慶鵬, 方 濤

(上海工程技術(shù)大學(xué) 數(shù)理與統(tǒng)計學(xué)院, 上海 201620)

數(shù)學(xué)公式在眾多領(lǐng)域的文獻資料中都大量存在.在數(shù)學(xué)、物理類科技期刊論文中,數(shù)學(xué)公式甚至占到整個論文篇幅的50%.它們在文檔中有的獨立占用一行,有的和其他文字混雜在一起.隨著互聯(lián)網(wǎng)的興起,知識共享理念深入人心,但在對科技文獻數(shù)字化時,由于數(shù)學(xué)公式本身的復(fù)雜性,目前的軟件和硬件均不能完全正確識別文獻中的數(shù)學(xué)公式.這些公式多以圖像形式存儲在各種格式的文件中,由于不能依據(jù)圖像形式的公式對文章進行檢索,讀者就無法依據(jù)數(shù)學(xué)公式檢索文獻,即使依據(jù)其他手段檢索到含有目標數(shù)學(xué)公式的文獻,當讀者想驗證或重新編輯這些數(shù)學(xué)公式時,也只能使用專門的數(shù)學(xué)公式輸入插件,如MathType或數(shù)學(xué)排版軟件LaTex,按照其語法規(guī)則重新輸入.由于數(shù)學(xué)表達式除英文字符、阿拉伯數(shù)字和希臘字母之外,還包括許多特殊的、大小不一、形式各樣的符號,這使其輸入過程比較復(fù)雜,極大降低了相關(guān)領(lǐng)域知識共享與信息檢索的效率,因此數(shù)學(xué)公式的自動識別越來越重要.

自1968 年Anderson[1]在其博士論文中首次提出公式識別問題以來,越來越多的學(xué)者參與到這一問題的研究中:Belaid等[2]使用從上到下和從下到上兩個句法分析算術(shù)和三角函數(shù)方程的自動識別問題;Lee等[3]利用統(tǒng)計方法提出一個識別印刷體數(shù)學(xué)表達式的系統(tǒng);我國學(xué)者肖建于等[4]提出基于凸殼和模糊識別的數(shù)學(xué)公式識別方法,該方法能明顯提高字符空間關(guān)系判別的識別率,識別正確率可達93.5%;Maclean等[5]針對手寫體數(shù)學(xué)公式,提出一種使用關(guān)系語法和模糊集解析二維輸入的新方法;劉婷婷等[6]基于支持向量機的方法識別數(shù)學(xué)公式,識別正確率可達98%.

1 根號幾何特征分析

字符識別通常采用比對算法,即將分割好的單字符與字模比對,取方差最小字模為識別結(jié)果.但此方法對根號的識別非常困難,這是因為根號長短不一、高低不同,難以用通常的比對方法進行識別.不同于手寫數(shù)學(xué)公式,印刷體數(shù)學(xué)公式書寫相對規(guī)范,幾何特質(zhì)明顯,因此可考慮通過根號的幾何特征來實現(xiàn)精準識別.

定義1設(shè)X為一個數(shù)學(xué)公式二值化圖片,按照從上到下,從左到右的統(tǒng)計原則,第一個黑色像素點坐標(xup,yup)稱為X的上角點,最后一個黑色像素點坐標(xdown,ydown)稱為X的下角點.

圖1給出3種數(shù)學(xué)公式二值化圖片的上角點和下角點.類似地,可定義X的左角點和右角點.

圖1 3種數(shù)學(xué)公式角點示意圖Fig.1 Corner sketches of three kinds of mathematical formula

定義2設(shè)X為一個數(shù)學(xué)公式二值化圖片,按照從左到右、從上到下的統(tǒng)計原則,第一個黑色像素點坐標(xleft,yleft)稱為X的左角點,最后一個黑色像素點坐標(xright,yright)稱為X的右角點.

定義3設(shè)X為一個數(shù)學(xué)公式二值化圖片,(xup,yup)和(xdown,ydown)分別為X的上角點和下角點,假設(shè)xdown≤xup,如果對于任意x∈(xdown,xup),點(x,y)均為X的黑色像素點,其中

則稱X擁有首一特征線.

對數(shù)學(xué)排版軟件LaTeX中數(shù)學(xué)公式輸入插件MathType的單字符集以及大小寫、英文字母集進行統(tǒng)計,擁有首一特征線的字符集為{≠,*,,?,∧,∨,?,Δ,,記為CandidateSet.顯然僅通過判斷數(shù)學(xué)公式二值化圖像是否擁有首一特征線,不能唯一確定該數(shù)學(xué)公式中是否帶有根號,必須增加新的判斷規(guī)則.根據(jù)根號的幾何特征,根號左角點和下角點之間距離嚴格大于零,即xdown-xleft>0.根據(jù)這一特征條件,CandidateSet減少為{≠,*,?,∨,?,,

另外,根號的首一特征線的斜率為負,即

通過以上分析,可以根據(jù)數(shù)學(xué)公式二值化圖像是否具有以下特征來唯一確定數(shù)學(xué)公式中是否存在根號:

1) 擁有斜率為負的首一特征線;

2) 左角點和下角點間距大于零;

3) 上角點所在水平線存在連續(xù)不間斷黑色像素點.

2 根號次數(shù)確定

第1步,注意到公式中3與其附近的根號是完全分離的.實際上,它被夾在y=yup,y=yleft,x=xleft和x=xdown這4條直線之間,因此可以據(jù)此將3從根式中分離出來.

第2步,制作數(shù)字1～9字模用于比對,每個字模一般為一個N×N的0-1矩陣;

第3步,將切割好的3標準化為一個N×N矩陣,并與9個數(shù)字字模一一比對,方差最小字模所代表的數(shù)字,即根式次數(shù).

3 算法設(shè)計與程序?qū)崿F(xiàn)

基于Matlab開發(fā)語言,設(shè)計下面的算法.

第1步,讀入數(shù)學(xué)公式圖片,并將其二值化,二值化后的數(shù)學(xué)公式圖片保存在矩陣A中.

第2步,根據(jù)印刷體數(shù)學(xué)公式的規(guī)范性,兩個單字符間有一定的空白間隔.利用這一特性對矩陣A中每一列進行檢測,若連續(xù)兩列元素均為1,則可在這些列處對A進行切割,切割后矩陣記為B,其個數(shù)設(shè)為n.

第3步,對每個矩陣B(i),i=1,2,…,n,確定其上、下、左、右角點坐標.

第4步,對每個矩陣B(i),判斷其是否擁有斜率為負的首一特征線,左下角點間距是否大于零,以及上角點所在水平線是否存在連續(xù)不間斷黑色像素點,如果3個邏輯判斷結(jié)果均為真,則斷定B(i)中含有根號;否則斷定B(i)中沒有根號.

第5步,對含有根號字符的矩陣B(i),將夾在y=yup,y=yleft,x=xleft和x=xdown4條直線之間的部分切割出來,標準化后存放在臨時矩陣BT中.

第6步,制作數(shù)字1～9字模,將BT與9個數(shù)字字模比對,記下方差最小字模所對應(yīng)的數(shù)字,即為BT(i)的根號次數(shù).

對于來自不同類型文檔的200個公式截圖,使用上述算法進行識別,所有公式中的根號全部正確識別,識別正確率達100%.使用Inter i5-3470 3.2 GHz處理器,2 GB內(nèi)存,耗時5.845 s,其中200張公式截圖讀入時間為4.136 s,識別程序僅耗時1.709 s.

4 結(jié) 語

數(shù)學(xué)公式因其字符的復(fù)雜性,導(dǎo)致傳統(tǒng)OCR技術(shù)無法對其進行有效識別.而根號又與其他數(shù)學(xué)字符大不相同,其長短、高低隨著公式的不同有較大變化,識別難度較大.本文基于根號的幾何特征,提出首一特征線的概念,并結(jié)合根號的其他幾何特征,設(shè)計根號的識別算法,試驗結(jié)果表明該算法有較高的識別率.