基于神經(jīng)網(wǎng)絡(luò)的印刷體數(shù)學(xué)公式抽取方法

(河北大學(xué) a.數(shù)學(xué)與計(jì)算機(jī)學(xué)院；b.圖書館， 河北 保定 071002)

摘要：在分析中文印刷文檔版式及字符特征的基礎(chǔ)上，提出了一種將決策樹與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合的數(shù)學(xué)公式抽取方法。采用決策樹方法將孤立公式從文檔中抽取出來，采用BP神經(jīng)網(wǎng)絡(luò)方法定位內(nèi)嵌公式。實(shí)驗(yàn)表明，該抽取方法對中文文檔的公式抽取具有較高的正確率、容錯(cuò)率和速率。

關(guān)鍵詞：光學(xué)字符識(shí)別；特征提取；數(shù)學(xué)公式抽取；決策樹；BP神經(jīng)網(wǎng)絡(luò)

中圖分類號(hào)：TP39141文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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(光學(xué)字符識(shí)別)技術(shù)已經(jīng)能夠識(shí)別出印刷文檔里的文字、表格，而且速度和準(zhǔn)確率都能夠令人滿意。但除文字外，印刷文檔，特別是科技文獻(xiàn)中還含有大量的數(shù)學(xué)公式。現(xiàn)有的OCR識(shí)別技術(shù)無法對后者進(jìn)行處理。然而在科技文檔中，數(shù)學(xué)公式廣泛存在，并且這些公式一般都比較復(fù)雜，如果以圖片方式保存將占據(jù)大量空間；而公式的手工錄入相當(dāng)麻煩，而且很容易出錯(cuò)。因此，公式的輸入問題是科技文獻(xiàn)數(shù)字化的關(guān)鍵問題。

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

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

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

1印刷文檔中數(shù)學(xué)公式的抽取

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

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

因?yàn)楣铝⒐叫泻臀谋拘性谂虐骘L(fēng)格上有許多差異，不經(jīng)過字符識(shí)別直接區(qū)分孤立公式行和非孤立公式行是可行的， 孤立公式行的抽取比較簡單。利用以下特征可以將它們區(qū)分開：a)獨(dú)立公式行通常比純文本行要高；b)公式行一般居中；c)公式行的密度比純文本行小；d)有注釋行的公式行右空白很小，且左空白相對較大。

1)特征提取

(1)提取行特征

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

b)行中字符Y坐標(biāo)的標(biāo)準(zhǔn)差為

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坐標(biāo)值；n表示文本行中的字符個(gè)數(shù)；nl表示文檔中的文本行個(gè)數(shù)。

2）利用決策樹方法進(jìn)行孤立公式抽取

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

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

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

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

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

規(guī)則1if C＞=center+t2then Lk=M。

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

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

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

規(guī)則5if C<=center+t1 then Lk=T。

以上規(guī)則中，M表示公式行，T表示非公式行。對非公式行進(jìn)行內(nèi)嵌公式的抽取。

12內(nèi)嵌公式的抽取

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

121特征提取

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

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

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

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

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

122利用改進(jìn)的BP網(wǎng)絡(luò)算法進(jìn)行公式抽取

定義輸入層為三個(gè)節(jié)點(diǎn)對應(yīng)P的三維分量，輸出層為一個(gè)節(jié)點(diǎn)。關(guān)于隱層數(shù)及其節(jié)點(diǎn)數(shù)的選擇比較復(fù)雜，采用網(wǎng)絡(luò)結(jié)構(gòu)增長型方法，即先設(shè)置較少的節(jié)點(diǎn)數(shù)對網(wǎng)絡(luò)進(jìn)行訓(xùn)練，并測試學(xué)習(xí)誤差；然后逐漸增加節(jié)點(diǎn)數(shù)，直到學(xué)習(xí)誤差不再有明顯減少為止。BP網(wǎng)絡(luò)模型如圖４所示。隱層和輸出層神經(jīng)元模型的傳遞函數(shù)采用Sigmoid函數(shù)：

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

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

利用改進(jìn)的BP算法進(jìn)行訓(xùn)練：

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

b)進(jìn)行逐個(gè)樣本的訓(xùn)練，將樣本P各分量送入輸入層上，并設(shè)置目標(biāo)輸出t。如果樣本數(shù)據(jù)為文本特征，令t=0.1；如果樣本數(shù)據(jù)為公式特征，令t=0.9。

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

d)計(jì)算誤差。根據(jù)實(shí)際輸出與目標(biāo)輸出計(jì)算輸出層各節(jié)點(diǎn)誤差δo=o(1-o)(t-o)；根據(jù)輸出層各節(jié)點(diǎn)誤差計(jì)算隱層各節(jié)點(diǎn)誤差δh=yi(1-yi)n_outi=1wjiδo。

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

f)統(tǒng)計(jì)誤差。采用均方誤差的方法克服了標(biāo)準(zhǔn)BP算法中誤差計(jì)算方法使迭代次數(shù)增加的弊端，因而定義誤差函數(shù)為e=1/(p×n_out)pm=1n_outi=1(om-tmi)2。其中：om為網(wǎng)絡(luò)實(shí)際輸出；tmi為網(wǎng)絡(luò)目標(biāo)輸出；p為訓(xùn)練樣本數(shù)目。

經(jīng)過實(shí)驗(yàn)，由圖5可知當(dāng)隱層節(jié)點(diǎn)數(shù)為10時(shí)得到的平均誤差值較小，隨著隱層節(jié)點(diǎn)數(shù)的繼續(xù)增加平均誤差無明顯變化，然而隱層節(jié)點(diǎn)數(shù)越多其時(shí)間復(fù)雜度越高。所以設(shè)置隱層節(jié)點(diǎn)數(shù)目為10。

實(shí)驗(yàn)表明，采用改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)提高了學(xué)習(xí)效率和穩(wěn)定性。經(jīng)過12 374次迭代，得到均方誤差最小時(shí)的一組權(quán)值和閾值，訓(xùn)練出一個(gè)神經(jīng)網(wǎng)絡(luò)（圖4）。

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

表1對圖６中圖像水平連通塊提取特征計(jì)算BP網(wǎng)絡(luò)輸出與判定結(jié)果

塊編號(hào)高度差H密度D寬高比R網(wǎng)絡(luò)輸出判定結(jié)果

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實(shí)驗(yàn)結(jié)果及改進(jìn)

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

表2公式抽取的結(jié)果

公式抽取數(shù)量實(shí)際數(shù)量準(zhǔn)確率/%成功率/%

孤立公式8428139194.2

內(nèi)嵌公式1 5041 41385.791.2

合計(jì)2 3462 22687.692.2

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

3結(jié)束語

本文的方法可以將中文印刷文檔的絕大部分?jǐn)?shù)學(xué)公式抽取出來。對于孤立公式行采用決策樹方法抽取較之以前的Parzen窗方法速度更快而且正確率有所提高；對于內(nèi)嵌公式，由于漢字其自身的特點(diǎn)，不可避免地會(huì)在抽取公式時(shí)產(chǎn)生誤識(shí)。比如左右結(jié)構(gòu)的漢字，可能被分成兩個(gè)塊來進(jìn)行判斷，就有可能誤識(shí)為公式塊；一些特殊的標(biāo)點(diǎn)符號(hào)，

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



參考文獻(xiàn)：

［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]田學(xué)東，張立平，楊捧.基于統(tǒng)計(jì)特征的數(shù)學(xué)公式抽取方法的研究[J].計(jì)算機(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.