基于神經網絡的印刷體數學公式抽取方法

(河北大學 a.數學與計算機學院；b.圖書館， 河北 保定 071002)

摘要：在分析中文印刷文檔版式及字符特征的基礎上，提出了一種將決策樹與BP神經網絡相結合的數學公式抽取方法。采用決策樹方法將孤立公式從文檔中抽取出來，采用BP神經網絡方法定位內嵌公式。實驗表明，該抽取方法對中文文檔的公式抽取具有較高的正確率、容錯率和速率。

關鍵詞：光學字符識別；特征提取；數學公式抽取；決策樹；BP神經網絡

中圖分類號：TP39141文獻標志碼：A

文章編號：1001-3695(2008)11-3483-03



Research on mathematical formulas extraction from printed document

based on neural network

CHANG Xin-fenga，CUI Jiana，LIU Xiao-yub，TIAN Xue-donga

(a.College of Mathematics Computer， b.Hebei University Library， Hebei University， Baoding Hebei 071002， China)

Abstract:On the basis of the analysis of typographic information and character feature on printed document， an approach combining decision tree and BP neural network was proposed to extract mathematical formulas. Decision tree method was used to extract the isolated formulas lines. BP neural network was used to extract the embedded formulas from the text lines. The experiments show the methods can achieve satisfactory results.

Key words:OCR; feature extraction; mathematical formulas extraction; decision tree; BP neural network

0引言

目前，OCR(光學字符識別)技術已經能夠識別出印刷文檔里的文字、表格，而且速度和準確率都能夠令人滿意。但除文字外，印刷文檔，特別是科技文獻中還含有大量的數學公式。現有的OCR識別技術無法對后者進行處理。然而在科技文檔中，數學公式廣泛存在，并且這些公式一般都比較復雜，如果以圖片方式保存將占據大量空間；而公式的手工錄入相當麻煩，而且很容易出錯。因此，公式的輸入問題是科技文獻數字化的關鍵問題。

公式抽取是公式識別的首要步驟，自公式識別問題提出以來發展緩慢，這與公式抽取存在的困難是分不開的。總的來說，數學公式抽取存在以下難點：a）待識文檔中除了孤立公式外，還存在著大量的內嵌公式；內嵌公式與純文本交雜在一起，很難將它們區分開；b）公式中的字符并不是簡單線性排列，而是以二維結構分布，如矩陣、除式；c）字符的出現位置具有隨機性，相鄰字符間位置關系不確定；d）字符大小隨著字符位置和內容的不同而改變，這使得公式結構更加復雜，增加了字符定位的難度，如上下角標、積分號；e) 同樣的字符由于不同的位置關系可能會有不同的意義，如d、x兩個字符，如果x在d的右下方則可能只是一個普通變量，但如果x在d的右方，大小相等，則可能表示是微分號；f）一些符號易與上下角標混淆，造成誤識，如逗號、引號。

針對這些問題，20世紀90年代中期Lee等人^[1]提出了一種簡單的方法。首先根據文本行自身的特征抽取孤立式公式，然后通過已識別字符來定位內嵌公式。該方法簡單，卻易將文檔中的標題當做孤立公式抽取出來。Lee等人提出的方法是自上而下的，而Fateman等人^[2]的方法是自下而上的，它首先掃描整頁，找到所有的連通體，然后將這些連通體分類合并組合成公式區域，從而將公式抽取出來，并且最終可以給出每個公式字符的確切位置。由于該方法是基于識別結果的，抽取結果受字符識別效果的限制。Inoue等人^[3]提出的系統是專門用來處理日文文檔的，系統把公式行從文本行中提取出來后將這些行分為日文字符區和數學字符區兩部分。其基本思想很簡單，OCR識別器能識別的是日文字符，不能識別的是數學公式，但效果卻不是很理想。在參考前人經驗的前提下，Kacem等人^[4]提出了一種新方法，分為全局分割和局部分割兩部分：首先通過全局分割抽取孤立公式行，然后在此基礎上通過局部分割將內嵌公式抽取出來。此方法不用事先進行字符識別，可以大大提高系統的速度。Jin Jian-ming等人^[5，6]提出了一種利用Parzen窗的方法抽取孤立公式，對于內嵌公式的抽取只適用于二維結構。Garain等人^[7]提出一種通過計算同一行中字符縱坐標的平均值和標準差來判斷是否為孤立公式，但對內嵌公式的抽取則依賴識別結果。

以上這些研究為公式抽取提供了一些有效的方法。但需要指出的是，這些方法都不是針對中文文檔的，它們不能直接用于中文文檔中數學公式的抽取。針對此問題，本文提出了一種利用決策樹方法^[8]進行孤立公式行抽取，利用BP神經網絡^[9]進行內嵌公式抽取的方法。該方法不依賴字符識別，實驗表明能夠達到較高的正確率和速率。

1印刷文檔中數學公式的抽取

根據中文文檔自身的特點：以方塊字為主，文字的高度幾乎相等（標點除外），首先對印刷文檔進行水平投影找到行的上下邊界，并根據閾值進行行間合并，再進行垂直投影找到行的左右邊界和各水平連通塊（水平坐標有重疊的連通體）用矩形框標志；再對水平連通塊進行水平投影，找到各水平連通塊上下邊界。系統流程如圖1所示。

11孤立公式行的抽取

因為孤立公式行和文本行在排版風格上有許多差異，不經過字符識別直接區分孤立公式行和非孤立公式行是可行的， 孤立公式行的抽取比較簡單。利用以下特征可以將它們區分開：a)獨立公式行通常比純文本行要高；b)公式行一般居中；c)公式行的密度比純文本行小；d)有注釋行的公式行右空白很小，且左空白相對較大。

1)特征提取

(1)提取行特征

a)行中心X坐標C=(Lk.right-Lk.left)/2。

b)行中字符Y坐標的標準差為

SD=ni=1(Yi-i)/(n-1)

其中：i=ni=1Yi/n

c)行密度D=NBP/Lk.width×Lk.height。

(2)提取文檔特征

a)左邊距LM=min(Xmin(Lk))k=1，…，nl。

b)右邊距RM=max(Xmax(Lk))k=1，…，nl。

其中：Lk表示印刷文檔中文本的第k行；C、LM和RM的定義如圖2所示；Yi表示文本行中字符的最大y坐標值；n表示文本行中的字符個數；nl表示文檔中的文本行個數。

2）利用決策樹方法進行孤立公式抽取

采用ID3算法^[8]通過自頂向下構造決策樹。對印刷文檔中文本行中心C、行中字符Y坐標的標準差SD和行密度D三個屬性特征進行分析。公式為

gain(S，A)≡entropy(S)-v∈values(A)(|Sv|/|S|)entropy(Sv)(1)

表示一個屬性A相對樣例集合S的信息增益。其中S的熵entropy(S)≡ci=1-pi log2 pi；values(A)是屬性A所有可能值的集合；Sv是S中屬性A的值為v的子集；c為屬性取值個數；pi是S中屬于類別i的比例。

對4 851條訓練樣本計算各屬性的信息增益如下：gain(S，C)=0.471，gain(S，SD)=0.154，gain(S，D)=0.127。屬性C的信息增益最高，將其作為根節點，并創建可能值的分支。C≤(center-t1)和C≥(center-t2)的后繼節點熵為0，使之成為一個葉子節點；C≥(center-t1) and C≤(center+t2)的后繼節點還有非0的熵在此節點下進一步展開。重復前面的過程，選擇一個新的屬性來分割訓練樣本，直到滿足以下兩個條件中的任一個：a）所有的屬性已經被這條路徑包括；b）與這個節點關聯的所有訓練樣本都具有相同的目標屬性值。

判斷公式行的決策樹如圖３所示。其中：center=(RM-LM)/2；ti是經過樣本數據訓練得出的閾值。由圖３產生出五條判斷公式行與文本行的規則。

規則1if C＞=center+t2then Lk=M。

規則2if C＞=center+t1 and C<=center+t2 and SD>=t3 and D＞=t4 then Lk=M。

規則3if C＞=center+t1 and C<=center+t2 and SD>=t3 and D

規則4if C＞=center+t1 and C<=center+t2 and SD＜t3 then Lk=T。

規則5if C<=center+t1 then Lk=T。

以上規則中，M表示公式行，T表示非公式行。對非公式行進行內嵌公式的抽取。

12內嵌公式的抽取

由于內嵌公式是在文本行中，利用版式信息很難將其與文本區分開。由于一部分文本與內嵌公式特征極為相似，文本與內嵌公式的分類界面很不規則，BP神經網絡理論上可以逼近任意非線性連續函數，且結構簡單、使用較為廣泛，算法也很成熟，可以大規模并行處理，自主訓練學習、自組織和容錯能力高。為此采用多層BP神經網絡進行內嵌公式提取。

121特征提取

提取行中水平連通塊特征：

a)高度差H=|h-h0|。

b)密度D=NBP/(w×h)。

c)寬高比R=w/h。

其中：h、h0、NBP和w分別表示水平連通塊高度、平均高度、黑像素個數和寬度。用P={H，D，R}作為用于公式塊抽取的屬性集。

122利用改進的BP網絡算法進行公式抽取

定義輸入層為三個節點對應P的三維分量，輸出層為一個節點。關于隱層數及其節點數的選擇比較復雜，采用網絡結構增長型方法，即先設置較少的節點數對網絡進行訓練，并測試學習誤差；然后逐漸增加節點數，直到學習誤差不再有明顯減少為止。BP網絡模型如圖４所示。隱層和輸出層神經元模型的傳遞函數采用Sigmoid函數：

f(x)=1/（1+exp(-x)）(2)

將150條字符塊P向量特征數據作為訓練集，包括60條漢字字符特征數據，90條公式字符特征數據。

利用改進的BP算法進行訓練：

a)初始化變量及參數。相關系數、最小均方誤差e、訓練步長η、輸入層節點n_in，隱層節點數n_hidden、輸出層節點數n_out、訓練數據個數p，對權值wji(j層到i層的權值)賦予隨機較小的非零數。設置最大迭代次數，超出最大迭代次數強制退出訓練。

b)進行逐個樣本的訓練，將樣本P各分量送入輸入層上，并設置目標輸出t。如果樣本數據為文本特征，令t=0.1；如果樣本數據為公式特征，令t=0.9。

c)開始進行前向傳播，隱層節點輸出為yi=f(ui+θi)。其中ui=n_inj=1wjixi；xi為輸入層節點值對應P的三維分量。輸出層節點輸出為o=f(uj+θj)。其中uj=n_hiddeni=1wjixj；xj為隱層的輸出值。θi為隱層節點閾值，θj為輸出層節點閾值。

d)計算誤差。根據實際輸出與目標輸出計算輸出層各節點誤差δo=o(1-o)(t-o)；根據輸出層各節點誤差計算隱層各節點誤差δh=yi(1-yi)n_outi=1wjiδo。

e)采用動量—自適應學習速率調整方法進行誤差反向傳播調整權值。標準BP算法實質上是一種簡單的最速下降靜態尋優方法，在修正wji(n)時，只按照第n步的負梯度方向進行修正，沒有考慮到以前積累的經驗，即以前時刻的梯度方向，從而常常使學習過程發生振蕩，收斂緩慢。動量法權值調整算法的具體做法是：將上一次權值調整量的一部分迭加到按本次誤差計算所得的權值調整量上，作為本次的實際權值調整量，即Δwji(n)=-ηδoxj+αΔwji(n-1)；隱層與輸入層權值調整量為Δwji(n)=-ηδhxj+αΔwji(n-1)（其中：α為動量系數，通常0＜α＜0.9）；增加一個慣性項αΔwji(n-1)，使得在碰到變化較小的局部極小值時，權值可以繼續向前改變，減小陷入局部極值的概率。

f)統計誤差。采用均方誤差的方法克服了標準BP算法中誤差計算方法使迭代次數增加的弊端，因而定義誤差函數為e=1/(p×n_out)pm=1n_outi=1(om-tmi)2。其中：om為網絡實際輸出；tmi為網絡目標輸出；p為訓練樣本數目。

經過實驗，由圖5可知當隱層節點數為10時得到的平均誤差值較小，隨著隱層節點數的繼續增加平均誤差無明顯變化，然而隱層節點數越多其時間復雜度越高。所以設置隱層節點數目為10。

實驗表明，采用改進的BP神經網絡提高了學習效率和穩定性。經過12 374次迭代，得到均方誤差最小時的一組權值和閾值，訓練出一個神經網絡（圖4）。

利用訓練后的BP神經網絡進行內嵌公式抽取。預進行內嵌公式塊抽取的原始圖像如圖6所示；抽取各水平連通塊的高度差、密度和寬高比特征，如表１所示。當BP網絡輸出小于等于05時，判定為文本塊；當BP網絡輸出＞0.5時，判定為公式塊。最后將抽取出的公式塊進行合并組成內嵌公式，合并的條件為公式塊之間沒有文本塊。抽取效果如圖７所示。

表1對圖６中圖像水平連通塊提取特征計算BP網絡輸出與判定結果

塊編號高度差H密度D寬高比R網絡輸出判定結果

020.261.030.13文本

140.171.030.12文本

2520.150.650.90公式

340.381.030.02文本

400.330.910.09文本

5３0.411.050.07文本

2實驗結果及改進

對230篇中文科技印刷文檔進行了掃描分析，此文檔包括813條孤立公式行，1 413條內嵌公式，抽取的結果如表2所示。表中準確率是指抽取結果中公式的比例；成功率是指文檔中公式被正確抽取的比例。

表2公式抽取的結果

公式抽取數量實際數量準確率/%成功率/%

孤立公式8428139194.2

內嵌公式1 5041 41385.791.2

合計2 3462 22687.692.2

在進行孤立公式行抽取時必然存在根據特征信息產生誤識的可能。如果誤識為孤立公式行，可以用訓練后的BP網絡對行中的水平連通塊進行計算，如果全部輸出小于等于0.5，則判斷此行為文本行；如果誤識為文本行，用BP網絡對行中的水平連通塊進行計算，如果全部輸出都大于0.5，則表明此行為公式行。這樣可以防止OCR系統的識別錯誤，并且使公式行與文本行的識別率得到了提高。內嵌公式抽取的主要錯誤在于：極個別漢字與公式塊的特征向量值相同，造成誤識。數學公式抽取效果如圖7所示。

3結束語

本文的方法可以將中文印刷文檔的絕大部分數學公式抽取出來。對于孤立公式行采用決策樹方法抽取較之以前的Parzen窗方法速度更快而且正確率有所提高；對于內嵌公式，由于漢字其自身的特點，不可避免地會在抽取公式時產生誤識。比如左右結構的漢字，可能被分成兩個塊來進行判斷，就有可能誤識為公式塊；一些特殊的標點符號，

其特征與公式塊特征極為相似，可能產生誤識，如“—”“一”等。根據此方法的特點，在不影響OCR系統識別的情況下，將孤立公式行識為文本行是可取的。以上問題可在以下幾個方面加以解決：改進特征或增加新特征；將公式識別器拒識的部件返回給文本識別器進行識別；根據左右部件的類別經過簡單的語義分析進行分類。



參考文獻：

［1］

LEE H J，WANG J S.Design of mathematical expression recognition system[J].Pattern Recognition Letters，1997，18(3):289-298.

[2]FATEMAN R，TOKUYASU T，BERMAN B.Optical character recognition and parsing of typeset mathematics[J].Journal of Visual Commun and Image Representation，1996，7(1): 2-15.

[3]INOUE K，MIYAZAKI R，SUZUKI M.Optical recognition of printed mathematical documents[C]// Proc of the 3rd Asian Technology Conference in Mathematics.1998:280-289. 

[4]KACEM A，BELAD A，AHMED M B.Automatic extraction of printed mathematical formulas using fuzzy logic and propagation of context[J].International Journal of Document Analysis and Recognition，2001，4(2):97-108.

[5]JIN Jian-ming，HAN Xiong-hu，WANG Qing-ren.Mathematical formulas extraction[C]//Proc of the 7th InternationalConference on Document Analysis and Recognition.Washington DC:IEEE Computer So-ciety，2003:1138-1141.

[6]田學東，張立平，楊捧.基于統計特征的數學公式抽取方法的研究[J].計算機工程，2006，32(19)：211-213.

[7]GARAIN U，CHAUDHURI B B.Identification of embedded mathema-tical expressions in scanned documents[C]//Proc ofthe 17th International Conference on Pattern Recognition.Washington DC:IEEE Computer Society，2004:384-387.

[8]QUINLAN J R.Simplifying decision trees[J].International Journal of Man-Machine Studies，1987，27(3):221-234.

[9]SCHIFFMANN W，JOOST M，WERNER R.Comparison of optimized backpropagation algorithms[C]//Proc of the European Symposium on Artifical Neural Networks.1993:97-104.