基于加權(quán)貝葉斯的脫機手寫阿文單詞識別

許亞美,何繼愛

(蘭州理工大學(xué) 計算機與通信學(xué)院，甘肅 蘭州 730050)

0 引言

在關(guān)于手寫文字識別的文獻中，阿拉伯文字識別的研究逐漸受到關(guān)注[1-4]。阿拉伯文，簡稱阿文，是西亞阿拉伯地區(qū)和伊斯蘭教信仰者使用的文字，使用者來自不同的國家與民族。阿文字母不能獨立運用，字母相連書寫成單詞后才有語義，因此單詞識別具有實際意義[4]。

阿文共有28個輔音字母、1個復(fù)合字母和12個元音符號，元音字母是在輔音字母上疊加元音符號而構(gòu)成，每個字母根據(jù)在詞中不同位置，有獨立、前連、雙連、后連中的2～4種字符格式，共演變成100個字符[5]。

圖1 手寫阿拉伯單詞結(jié)構(gòu)規(guī)則示例

鑒于上述討論，本文針對手寫阿拉伯文字，提出在組件(即字符或字符的一部分)層面上分解和識別單詞。算法首先建立阿拉伯單詞組件庫，過分割單詞圖像形成組件序列，再結(jié)合形態(tài)特征和位置信息識別各組件并估計其權(quán)重。然后構(gòu)建組件特征至單詞的加權(quán)貝葉斯推理模型，加權(quán)融合組件識別置信度和構(gòu)詞先驗信息，得到最終的單詞識別結(jié)果。

1 阿文單詞的組件分析

阿文單詞組件是根據(jù)29個阿拉伯字母的100個變體字符和12個元音符號的形態(tài)和結(jié)構(gòu)[5]來定義的，指在阿文單詞中相對獨立且可被共享的筆畫區(qū)域塊。根據(jù)組件特征，可將阿文組件分為3類： ①主體組件(main grapheme, MG)： 從字符的主要筆畫中分割出的沿著基線書寫的區(qū)域塊，鑒于多段型組件易被過分割為其他組件，這里去掉多段型組件，并將這類組件分解后以不同于現(xiàn)有組件的新區(qū)域添加到主體組件； ②點組件(dot grapheme, DG)： 延遲筆畫中點筆畫的組合； ③附加組件(affix grapheme, AG)： 延遲筆畫中除DG之外的區(qū)域塊，其中12個元音符號中有些是兩個AG的組合。阿拉伯文字組件庫如表1所示，共包含50個MG、5個DG和9個AG，其中DG和AG的虛線表示其位置在基線的上方或下方。

表1 阿拉伯文字組件庫

圖2 手寫阿文單詞的組件構(gòu)成示例

相比字符，在組件層面分解單詞，不僅有效解決了多段型字符在分割時易產(chǎn)生過分割錯誤的問題，而且通過組件分析使相似字之間的微小差異被放大，從而易于檢出和辨別。

2 阿文單詞的貝葉斯推理模型

貝葉斯推理模型是一種以概率分析和圖論為基礎(chǔ)的數(shù)據(jù)模型，能有效地綜合數(shù)據(jù)的先驗信息和樣本信息，近年來在模式識別領(lǐng)域上的應(yīng)用逐漸被關(guān)注[17-18]。

本文依據(jù)對阿文單詞的組件分析，構(gòu)建自組件特征至單詞類別的貝葉斯推理模型，該模型以單詞的組件特征為起始狀態(tài)節(jié)點，以組件為中間節(jié)點、以單詞類別為終止節(jié)點，形成一個關(guān)系網(wǎng)絡(luò)圖，各狀態(tài)節(jié)點之間的有向弧表示節(jié)點狀態(tài)發(fā)生的關(guān)系和概率，由父節(jié)點指向子節(jié)點，如圖3所示。

圖3 阿文單詞的貝葉斯推理模型

該推理模型的具體解釋如下：

(2)基于單詞類別的模型規(guī)整在本文單詞識別算法中，需要利用單詞貝葉斯推理模型分別計算該單詞樣本至946個單詞類別的后驗概率。由于單詞所包含的各類組件數(shù)目不定，為計算待測樣本至單詞類別的識別概率，設(shè)定一個空組件Φ，代表該處沒有組件，利用空組件Φ規(guī)整樣本特征和單詞類別的模型結(jié)構(gòu)。規(guī)整方法是： 以單詞類別的節(jié)點數(shù)為標準，調(diào)整單詞樣本的節(jié)點，如果樣本的組件節(jié)點個數(shù)較大，則去掉后面多余的組件；反之，則以空組件Φ補全。包含空組件后，組件數(shù)目變更為51個MG、6個DG和10個AG。

3 單詞識別算法整體流程

本文基于加權(quán)貝葉斯的阿文單詞識別算法，首先將阿文單詞分割為組件序列，再進行組件識別和組件加權(quán)系數(shù)估計，最后通過加權(quán)貝葉斯推理，計算單詞后驗概率并獲得單詞識別結(jié)果。具體算法描述如下。

3.1 組件分割

本文采用我們在以前工作[19]中所提出的主體分割和附加聚類算法(main segmentation and additional clustering,MSAC)，對脫機阿文單詞進行組件分割，組件分割的流程如圖4所示，主要包括以下幾個步驟。

圖4 MSAC組件分割流程

(1)預(yù)處理對脫機阿文單詞進行預(yù)處理，包括二值化、歸一化、斷筆修復(fù)、傾斜校正和細化，其中二值化是灰度255置1，其余置0；歸一化為寬度512，高度等比例縮放；斷筆連接是兩筆畫間距小于筆畫寬度的3/2時進行修復(fù)；傾斜校正范圍是±30°；細化采用Z-S+Holt算法[19]。

(2)筆畫提取首先通過連通域檢測提取單詞筆畫，根據(jù)點閾值判定點筆畫，再對除去點筆畫后的剩余筆畫進行Hough變換，并根據(jù)其峰值點找到基線位置，獲取基線域，然后將與基線域連通的筆畫確定為主要筆畫，其他筆畫為延遲筆畫。

(3)主體分割和MG序列獲取在基線域內(nèi)計算主要筆畫的垂直差分投影[20]，取其極小值點為MG切分點，自MG切分點，垂直分割主要筆畫得到主體組件，按位置自右至左記作M=(M1,M2, …,Mn)。

(5)DG序列和AG序列的獲取聚類后的點群作為點組件，按位置自右至左，記作D=(D1,D2, …,Dm)，除去MG和DG以外的單個筆畫構(gòu)成附加組件，按位置自右至左記作A=(A1,A2, …,Al)。

3.2 組件子分類和識別

本文結(jié)合組件分割時獲得的位置信息，提出一種新的多級混合式組件識別算法，首先根據(jù)位置信息和組件類型將所有組件預(yù)分類為8個子類，然后針對MG、AG、DG三類組件，根據(jù)各自的結(jié)構(gòu)特點，設(shè)計不同的特征提取和分類器，在各自所屬的子類范圍內(nèi)再進一步分類。組件子類的描述如表2所示。

表2 阿拉伯文組件的8個子類

表2中，MG根據(jù)其在連體段中所處的位置可分為獨立(S, stand alone)、前連(FC, front-connection)、雙連(m, middle)、后連(BC, behind-connection)[5]等4個子類，DG和AG各自根據(jù)其位于基線的上方或下方可分為上方(up-diacritics)和下方(down-diacritics)兩個子類，于是共有MG-S、MG-FC、MG-M、MG-BC、DG-U、DG-D、AG-U、AG-D等8個組件子類。

對于DG，由于點的數(shù)目特征確切直觀，于是直接根據(jù)點數(shù)目nd(nd=1, 2, 3)計算點組件的識別距離，并對點數(shù)目的差值加1以避免距離為0情況。設(shè)組件特征向量為x，那么點組件識別距離的計算如式(1)所示。

其中，di(x)代表組件x對第i類候選的識別距離，NS是組件子類別數(shù)，對于DG-U，NS=3；對于DG-D，NS=2。

對于MG和AG，采用輪廓Freeman上、下、左、右4方向鏈碼結(jié)合彈性網(wǎng)格特征提取(elastic mesh directional features, EMDF)[22]。考慮到MG和AG的面積比例，網(wǎng)格大小對MG取8×8，對AG取4×4。采用MQDF分類器[23]計算MG和AG的識別距離，如式(2)所示。

其中，μi是均值向量，λi,k代表協(xié)方差矩陣的第k個特征值，φi,k是其對應(yīng)的特征向量，r是主軸個數(shù)，r

另外，對3.2節(jié)中所描述的空組件Φ，規(guī)定空組件的特征為全0向量。

3.3 置信度轉(zhuǎn)換和權(quán)重估計

3.3.1 識別置信度轉(zhuǎn)換

根據(jù)組件分類器輸出的識別距離dj(x),j=1, …,NS，采用softmax函數(shù)對識別距離進行置信度轉(zhuǎn)換，得到組件識別置信度，計算如式(3)所示。

(3)

其中,p(qj|x)代表組件x至第j類候選的識別置信度，NS是組件子類別數(shù)。

若上述估計出的識別置信度在不同子類范圍，則需要將其擴張到統(tǒng)一的MG、DG或AG組件空間，擴張方法如式(4)所示。

其中，p(ωi|x)為擴張后的組件識別置信度，i= 1, …,N，對于MG，N=NM=51；對于DG，N=ND=6；對于AG，N=NA=10。

3.3.2 組件權(quán)重估計

實驗發(fā)現(xiàn)，單詞中各組件的識別可靠度不同。當(dāng)某組件的候選類別里具有相似字符時，相似字符對應(yīng)的識別置信度往往較為相近，這時該組件的識別結(jié)果不太可靠；反之，當(dāng)某一候選識別置信度相較其他候選顯著地高，則說明該組件前幾候選中沒有相似字符的情況，識別結(jié)果較為可靠。本文算法試圖在單詞識別中對結(jié)果較可靠的組件給予較大的權(quán)重，以提高最終的單詞識別率，考慮以組件識別置信度的熵值的分布來表述可靠性，組件權(quán)重估計的計算如式(5)所示。

(5)

其中，λk是第k個組件的權(quán)重系數(shù)，p(ωi|xk)是第k個組件的第i類候選識別置信度，N是組件類別數(shù)，NG是該組件所在單詞中的組件總數(shù)。

3.4 單詞識別

單詞識別的原理是計算待測樣本至單詞類別的識別置信度(即后驗概率)，然后按照置信度自大至小的順序輸出候選單詞類別，整個識別過程包括訓(xùn)練階段和識別階段。

3.4.1 訓(xùn)練階段

在訓(xùn)練階段完成對單詞貝葉斯模型推理中狀態(tài)轉(zhuǎn)移概率的獲取。其中:

(1) 對于表示單詞和組件構(gòu)成關(guān)系的轉(zhuǎn)移概率p(WI|Mi),I= 1, …,NW,i=1, …,NM;p(WI|Dj),j=1, …,ND,p(WI|Ak),k=1, …,NA。采用最大似然估計進行參數(shù)學(xué)習(xí)，統(tǒng)計數(shù)據(jù)來自阿拉伯文語料庫，先由阿文字母使用頻率[24]轉(zhuǎn)化得到各組件的先驗概率，再對各單詞類別的組件構(gòu)成統(tǒng)計得到單詞內(nèi)各組件和單詞的聯(lián)合概率，然后用條件概率公式計算得到組件至單詞的條件概率，即轉(zhuǎn)移概率。

3.4.2 識別階段

其中，Vi(i=1, …,NG)表示貝葉斯推理模型中與單詞WI相關(guān)聯(lián)的狀態(tài)節(jié)點，有NG=n+m+l，pa(·)表示節(jié)點Vi的父節(jié)點集，Sh表示該父節(jié)點集的路徑分布。

結(jié)合圖3中所述的模型結(jié)構(gòu)，如式(7)所示。

用組件權(quán)重系數(shù)λk(k=1, …,n+m+l)對式(7)進行修正，得到式(8):

(8)

于是，組件特征為x的待測樣本，其單詞首選識別結(jié)果為最大后驗概率對應(yīng)的單詞類別，如式(9)所示。

4 實驗

算法性能在IFN/ENIT v2.0手寫阿拉伯文字數(shù)據(jù)庫[6-7]上驗證，該數(shù)據(jù)庫包含946個突尼斯城市/村莊名，共32 492個脫機阿文單詞樣本，分為編號為a、b、c、d和e的五個組[6-7]。以下各實驗均使用a～d組數(shù)據(jù)訓(xùn)練，使用e組數(shù)據(jù)測試，算法用VC++6.0編程，運行環(huán)境是2.6G Intel i5-4300M CPU、4.0 GB內(nèi)存的PC機。

4.1 組件分割性能分析

為評估分割結(jié)果，使用三個度量標準： 準確率、召回率和誤檢率。準確率是算法所獲得分割點中正確的比率；召回率指真值分割位置中能被算法正確檢出的比率；誤檢率=1-準確率，包括過分割和錯分割兩種錯誤，其中過分割是將一個組件分割成多個組件，而錯分割則指分割邊界不正確。

本實驗在IFN/ENIT v2.0數(shù)據(jù)庫[6-7]上測試三種過分割算法的性能，使用a～d組數(shù)據(jù)進行訓(xùn)練，測試數(shù)據(jù)是e組6 033個單詞樣本所包含的65 884個組件分割點。算法1即本文過分割MSAC 算法。算法2是采用文獻[15]提出的最少像素定位結(jié)合最優(yōu)拓撲結(jié)構(gòu)篩選的手寫阿文過分割算法。算法3是采用文獻[16]提出的基于改進垂直投影和模板匹配的啟發(fā)式手寫阿文過分割算法。

表3給出了三種過分割算法的組件分割性能比較，可以看出，本文組件分割算法(算法1)性能良好，獲得97.78%準確率和98.05%召回率。算法1針對過分割的誤檢率僅有0.96%，對于錯分割的誤檢率為1.26%，均遠低于另外兩種算法。良好的組件分割性能是本文基于分割策略的單詞識別算法實施的基礎(chǔ)。

表3 組件分割性能比較

4.2 組件識別性能分析

本實驗所使用的組件樣本通過對IFN/ENIT v2.0數(shù)據(jù)庫[6-7]樣本進行手動分割得到，訓(xùn)練數(shù)據(jù)是來自該數(shù)據(jù)庫a～d組的共305 042個組件，測試數(shù)據(jù)是來自e組的71 917個組件。實驗對比兩種識別算法的性能。算法1即本文多級混合式的手寫阿文組件識別算法。算法2是文獻[25]提出的脫機阿文字符識別算法，該算法基于神經(jīng)網(wǎng)絡(luò)分類器，并結(jié)合了統(tǒng)計和結(jié)構(gòu)特征。

表4列出了兩種識別算法分別對MG、DG和AG的識別結(jié)果比較，可以看出，本文組件識別算法(算法1)相較算法2性能較好，這是因為本文多級混合式的手寫阿文組件識別算法根據(jù)組件分割時的位置信息預(yù)分類組件，又為MG、DG和AG設(shè)計不同的特征提取和分類器，能獲得較好的識別效果。而且，算法1使用距離分類器，因而相較算法2神經(jīng)網(wǎng)絡(luò)分類器的耗時少。對DG組件，算法1獲得的識別率較算法2高2.11%，因為本文算法考慮了三種點連筆的情況，因而對書寫連筆較多的樣本組識別率高。

表4 組件識別性能比較

4.3 單詞識別性能分析

本實驗使用IFN/ENIT v2.0數(shù)據(jù)庫[6-7]的a～d組進行訓(xùn)練，訓(xùn)練數(shù)據(jù)包括單詞樣本26 459個，字符樣本212 211個，組件樣本305 042個，測試數(shù)據(jù)是e組的6 033個單詞樣本。實驗對比了四種算法的性能，算法1、2和3基于切分識別，算法1是本文手寫阿文單詞識別算法；算法2是文獻[13]提出的基于多邊形近似描述結(jié)構(gòu)特征和多邊形模糊匹配的阿文單詞識別算法；算法3采用文獻[14]提出的結(jié)合縱、橫向掃描模板和支持向量機(support vector machine,SVM)分類器的手寫阿文單詞識別算法；算法4基于整詞識別，由文獻[10]提出，采用滑動窗統(tǒng)計特征結(jié)合多流隱馬爾可夫模型(hidden Markov models,HMM)分類器。表5總結(jié)了四種算法的單詞識別性能。

表5 單詞識別性能比較

可以看出，本文算法(算法1)性能良好，單詞首選識別率為90.03%，證實了該算法的有效性。分析來說，首先，在分割單元方面，對比算法1和算法2、3可知，本文基于組件的分解和建?？梢詼p少過分割錯誤，在組件層面識別單詞，能將相似詞間的微小差異定位至不同組件，并且在分割時考慮到點筆畫的三種連寫形式，有效解決了手寫文字筆畫粘連的識別難點，進而有效提高了單詞識別率。其次，對比識別策略可知，本文基于切分識別的算法1獲得的識別率稍高于基于整詞識別的算法4，而識別所需的訓(xùn)練基元是50個MG、9個AG和3個點連筆，共62個組件，訓(xùn)練所需類別數(shù)目小且固定，算法向大規(guī)模詞匯識別的可擴展性較強。最后，在耗時方面，由于分割模塊會部分增加算法復(fù)雜度，切分識別策略相比整詞識別策略，算法的運行時間較長。

5 結(jié)束語

脫機手寫阿文單詞書寫粘連，筆畫形態(tài)復(fù)雜，文字特征很難準確提取。本文將阿文單詞分解為組件，并設(shè)計多級混合式分類器來識別組件，再通過單詞加權(quán)貝葉斯模型的構(gòu)建和推理來獲取單詞識別結(jié)果。算法不但能檢測和辨識到相似單詞間的微小差異，而且對書寫連筆、筆畫漂移等手寫復(fù)雜情況具魯棒性。另外，算法訓(xùn)練所需組件類別有限，易于向大詞匯量識別任務(wù)擴展。

算法目前的識別錯誤主要出現(xiàn)在書寫潦草、點筆畫連寫不規(guī)整和點筆畫丟失的情況。下一步研究期望通過提高組件識別率和改進單詞結(jié)構(gòu)模型來獲得更好的單詞識別性能。