基于ocr的數(shù)學(xué)公式結(jié)構(gòu)的分析

基于ocr的數(shù)學(xué)公式結(jié)構(gòu)的分析

1印刷體數(shù)學(xué)公式識(shí)別與結(jié)構(gòu)分析隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，將打印文檔轉(zhuǎn)換為電子文檔是信息交換的重要步驟。借助OCR(OpticalCharactersRecognition，光學(xué)字符識(shí)別）技術(shù)將文檔信息輸入計(jì)算機(jī)，是目前公認(rèn)的信息數(shù)字化的高效手段。現(xiàn)有的文檔識(shí)別與重構(gòu)系統(tǒng)（OCR軟件）對(duì)印刷體文字的識(shí)別率很高，但由于數(shù)學(xué)公式的二維嵌套特性、所包含符號(hào)的復(fù)雜性及數(shù)學(xué)符號(hào)表達(dá)含義的多樣性，使得數(shù)學(xué)公式的自動(dòng)識(shí)別成為模式識(shí)別中的瓶頸問題。而數(shù)學(xué)公式是絕大多數(shù)科技書刊的重要組成部分，甚至一些文獻(xiàn)的核心就是這些公式，失去了公式的文章可能毫無意義。一個(gè)無法處理數(shù)學(xué)公式的識(shí)別系統(tǒng)，在應(yīng)用于富含公式的科技文獻(xiàn)時(shí)，往往失去其應(yīng)用價(jià)值。因此，研究印刷體數(shù)學(xué)公式識(shí)別與重構(gòu)技術(shù)，具有重要的科學(xué)意義和應(yīng)用前景。數(shù)學(xué)公式識(shí)別通常由三部分組成：數(shù)學(xué)公式提取；數(shù)學(xué)公式識(shí)別與結(jié)構(gòu)分析；數(shù)學(xué)公式重構(gòu)。其中，公式結(jié)構(gòu)分析是一個(gè)關(guān)鍵環(huán)節(jié)。從20世紀(jì)的70年代以來，研究人員對(duì)數(shù)學(xué)公式的結(jié)構(gòu)分析做了大量的工作。Anderson采用自頂向下的分析方法，以句法為標(biāo)準(zhǔn)分割識(shí)別。Chang提出了利用結(jié)構(gòu)說明方案來分析公式結(jié)構(gòu)的方法。Lavirotte和Pottier采用上下文相關(guān)文法分析關(guān)鍵字，以改善分析效果。Grbavec和Blostein利用圖來表達(dá)公式結(jié)構(gòu)分析的結(jié)果，并利用了符號(hào)使用的知識(shí)。但上述的方法都存在一些缺點(diǎn)。本文提出了一種利用基準(zhǔn)線構(gòu)建初始結(jié)構(gòu)樹，并利用語法和語義知識(shí)進(jìn)行樹轉(zhuǎn)換。實(shí)驗(yàn)證明，這種方法對(duì)數(shù)學(xué)公式的結(jié)構(gòu)分析效果較好。文中第2部分介紹結(jié)構(gòu)分析的預(yù)處理；第3部分討論結(jié)構(gòu)分析的具體步驟；第4部分是實(shí)驗(yàn)結(jié)果和存在問題的分析。2字符的質(zhì)心生成為了便于結(jié)構(gòu)分析，需要提取函數(shù)名與子表達(dá)式字符串，而要完成這些功能，須對(duì)字符的大小和中心進(jìn)行歸一化。首先計(jì)算字符的外邊框（如圖1所示），并找出中心，然后把字符中心移動(dòng)到指定的位置上。根據(jù)水平和垂直兩個(gè)方向字符黑像素的分布進(jìn)行大小歸一化。需要先計(jì)算字符的質(zhì)心GI和GJ:式中c(i,j）為1時(shí)表示該像素點(diǎn)為黑像（字符像素），為0時(shí)表示該像素點(diǎn)為背景。再計(jì)算水平和垂直方向的散度σI和σJ:最后，按比例將字符線性放大或縮小成規(guī)定散度的點(diǎn)陣。2.1提取函數(shù)名對(duì)字符歸一化后，運(yùn)用最長(zhǎng)字符串匹配的方法，提取函數(shù)型字符（三角函數(shù)，絕對(duì)值abs（），邏輯符號(hào)，等于號(hào)等），并把它看作一個(gè)整體符號(hào)。2.2相鄰字符生成滿足下列條件的連續(xù)字符合并為一個(gè)字符：（1）具有相同大小和中心。（2）兩相鄰字符間的空格小于它們大小。例如2100中1,0,0合并成100。3初始結(jié)構(gòu)樹的構(gòu)建首先利用基準(zhǔn)線找到中心點(diǎn)在同一閾值內(nèi)的字符，根據(jù)各個(gè)字符之間的位置關(guān)系，放在不同的子節(jié)點(diǎn)中，構(gòu)建出初始結(jié)構(gòu)樹；然后利用語法和語義知識(shí)將結(jié)構(gòu)樹轉(zhuǎn)化成以運(yùn)算符為子節(jié)點(diǎn)，操作數(shù)為葉子節(jié)點(diǎn)的樹。3.1確定基準(zhǔn)線的算法數(shù)學(xué)表達(dá)式通過數(shù)學(xué)符號(hào)大小和相互之間的位置關(guān)系來傳遞信息，通過對(duì)數(shù)學(xué)公式中基準(zhǔn)線上字符的分析，就能揭示數(shù)學(xué)公式的含義。具體的步驟如下：步驟1記錄公式中各個(gè)字符的邊框線和中心點(diǎn)坐標(biāo)。對(duì)公式中的每一個(gè)符號(hào)，記錄下它們的邊框坐標(biāo)minX(s),maxX(s),minY(s),maxY(s），以及各個(gè)字符的中心點(diǎn)坐標(biāo)CentroidX(s）、CentroidY(s）和高度H（圖1):步驟2構(gòu)建初始結(jié)構(gòu)樹。以整個(gè)數(shù)學(xué)表達(dá)式（EXPRESSION）作為樹的根節(jié)點(diǎn)（rnode），將公式所用的字符（已提取的字符串和函數(shù)名作為一個(gè)字符看）按minX(s）從小到大的順序存放在列表L(list）中，并作為樹的子節(jié)點(diǎn)。步驟3確定基準(zhǔn)線。對(duì)基準(zhǔn)線的說明如下：(1）基準(zhǔn)線（DL）：對(duì)于s1,s2，…，sn∈L，如果CentroidY(s1)-tH≤CentroidY(si）≤CentroidY(s1)+tH成立，那么B=B∪{si}，B集合中字符所在的直線區(qū)域成為基準(zhǔn)線。其中，s1是首字符，H是首字符的高度，t是閾值（0<t<0.5）。基準(zhǔn)線與符合條件的字符集合一一對(duì)應(yīng)，中心點(diǎn)在這個(gè)高度范圍內(nèi)的字符在同一條基準(zhǔn)線上。例如X2+d+bY=Z中X、+、b、Y、=、Z在同一條基準(zhǔn)線上；2、+、d在另一條基準(zhǔn)線上，所以在X2+d+bY=Z中有兩條基準(zhǔn)線。(2）主基準(zhǔn)線：對(duì)于si∈L，如果（┐SUPER(si,sj））∧（┐SUBSC(si,sj））∧（┐CONTAIN(si,sj))=1成立（其含義見步驟4），并且s1,si∈B，則si所在的基準(zhǔn)線稱為主基準(zhǔn)線。主基準(zhǔn)線上對(duì)應(yīng)集合中的字符不被其他字符嵌套。也就是公式中最左邊的字符所在的基準(zhǔn)線。例如在X2+d+bY=Z中X、+、b、Y、=、Z所在的基準(zhǔn)線為主基準(zhǔn)線。(3）嵌套基準(zhǔn)線：對(duì)于sj∈L，當(dāng)且僅當(dāng)SUPER(si,sj),SUBSC(si,sj),ABOVE(si,sj),BELOW(si,sj),CONTAIN(si,sj）中有一個(gè)為真，sj嵌套si。si所在的基準(zhǔn)線為嵌套基準(zhǔn)線。其中i≠j。嵌套基準(zhǔn)線上的字符，在垂直方向上偏離了某個(gè)字符或被別的字符所包圍。嵌套常用來表示某種隱式運(yùn)算。例如在X2+d+bY=Z中2、+、d所在基準(zhǔn)線為嵌套基準(zhǔn)線，與X之間存在嵌套關(guān)系，表明了前者和后者之間的指數(shù)運(yùn)算。確定基準(zhǔn)線的算法如下：其中Snode＿list是結(jié)點(diǎn)的符號(hào)列表；Symbol(rnode）表示根節(jié)點(diǎn)的字符；Sstart表示符號(hào)列表中的首字符；Hor(Sstart,Snode＿list）是在列表中以Sstart為首字符，從左向右尋找符合條件字符的函數(shù)；Collect＿Regine(BaseLine＿symbol）把符合條件的字符放入相應(yīng)的基準(zhǔn)線上；Symbol(Update＿Baseline）表示將基準(zhǔn)線上的字符放入子結(jié)點(diǎn)；rnode′表示子樹的根接點(diǎn)。步驟4分配字符。把同一基準(zhǔn)線上的字符s1,s2，…，sn放到同一層子節(jié)點(diǎn)中，其他字符放入到其后代子節(jié)點(diǎn)。根據(jù)從左到右閱讀公式的習(xí)慣，按下列規(guī)則存放字符：嵌套基準(zhǔn)線上字符放入到其最左邊字符臨近字符所在節(jié)點(diǎn)的子節(jié)點(diǎn)中。可以用最近鄰法中Euclidean公式計(jì)算距離：同時(shí)用標(biāo)簽標(biāo)注子節(jié)點(diǎn)中字符si其父節(jié)點(diǎn)中字符sj間的位置關(guān)系：SUPER（上標(biāo)），SUBSC（下標(biāo)），ABOVE（上部），BELOW（下部）和CONTAIN（包含）。其定義如下：步驟5判斷是否結(jié)束。判斷最下層子節(jié)點(diǎn)中字符數(shù)是否為1，如果為真，則結(jié)束；否則返回到步驟3。3.2公式分析利用數(shù)學(xué)公式中語法規(guī)則和語義知識(shí)將原來的結(jié)構(gòu)樹，轉(zhuǎn)換以操作符為子節(jié)點(diǎn)、操作數(shù)為葉子節(jié)點(diǎn)的操作符樹。3.2.1作用域越小，分級(jí)越高根據(jù)運(yùn)算符的優(yōu)先級(jí)和它們之間的相關(guān)性，即運(yùn)算符的作用域，作用域大的主導(dǎo)作用域小的。作用域越小，優(yōu)先級(jí)越高。例如X2+d+bY=Z中，“=”的作用域是整個(gè)公式，最大；“+”的作用域是“=”左邊的半個(gè)公式，但“+”比“=”的優(yōu)先級(jí)高。對(duì)公式進(jìn)行語法分析時(shí)，要注意運(yùn)算符的作用域，最后用TXL語法將初始結(jié)構(gòu)樹轉(zhuǎn)換成語法樹。3.2.2語義“-”的重構(gòu)通過分析數(shù)學(xué)公式的語義，能夠識(shí)別隱含的運(yùn)算符（如X2+d+bY=Z中bY之間包含的“*”），分析操作數(shù)類型，根據(jù)上下文消除運(yùn)算符的歧義（“-”可以是分?jǐn)?shù)線，還可以是邏輯非），并記錄操作數(shù)，以便于根據(jù)運(yùn)算的優(yōu)先級(jí)別的同，對(duì)公式中運(yùn)算符排序。語義分析之后，利用樹轉(zhuǎn)換規(guī)則重構(gòu)結(jié)構(gòu)樹。樹轉(zhuǎn)換規(guī)則能夠搜索結(jié)構(gòu)樹，把語法樹轉(zhuǎn)換成一種更嚴(yán)格、緊湊的形式。它是以列舉方式定義的一組規(guī)則，如a*b，轉(zhuǎn)換成[*，a,b]。由于在前面初始結(jié)構(gòu)樹中已標(biāo)明符號(hào)的關(guān)系，簡(jiǎn)化了樹轉(zhuǎn)換規(guī)則。在最后得到的決策樹中，包含了隱含的運(yùn)算符以及操作數(shù)。4試驗(yàn)結(jié)果與問題分析4.1．不同組數(shù)學(xué)公式的測(cè)試結(jié)果實(shí)驗(yàn)結(jié)果表明，對(duì)同一組公式，當(dāng)時(shí)，確定基準(zhǔn)線的正確率為75%，識(shí)別率為72%；當(dāng)時(shí)，基準(zhǔn)線的正確率為79%，識(shí)別率為78%;時(shí)，基準(zhǔn)線的正確率為79%，識(shí)別率為78%;時(shí)，基準(zhǔn)線的正確率為72%，識(shí)別率為71%。選取，對(duì)不同組數(shù)學(xué)公式測(cè)試結(jié)果如表1。這種方法對(duì)于公式的結(jié)構(gòu)分析效果理想，可以