基于信息擴(kuò)散與聚集的脫機(jī)手寫字符重心定位方法

王寅同,王燕清,肖文潔

(南京曉莊學(xué)院 智能信息處理重點實驗室,江蘇 南京 211171)

0 引言

脫機(jī)手寫體文本識別是目前文字識別領(lǐng)域的最困難問題之一[1-4],與聯(lián)機(jī)手寫識別相比,缺少必要的字符位置和軌跡信息,其中后者可以根據(jù)字符位置和書寫經(jīng)驗來近似獲得,因此字符位置的判定對脫機(jī)手寫體文本識別效率的影響甚大。脫機(jī)手寫字符書寫隨意性導(dǎo)致相鄰字符之間的位置關(guān)系復(fù)雜性,造成脫機(jī)手寫體文本中的字符位置定位要比印刷體字符定位難得很多,尤其是行傾斜、不規(guī)則行片段以及粘連字符的文本中的字符位置判定[5-7]。

目前脫機(jī)手寫文本的字符位置判定主要是由字符切分來實現(xiàn),常用的切分技術(shù)有基于統(tǒng)計的切分方法、基于字形結(jié)構(gòu)切分和基于識別的漢字切分方法等。其中,基于統(tǒng)計的切分方法是根據(jù)字符的總體統(tǒng)計分布特征,確定字符之間的界線,判別時以字符的平均字符寬度作輔助判別,統(tǒng)計分布特征的代表性和穩(wěn)定性對切分的正確性及收斂性起很重要作用,如投影法(Project Methods,Pros)和連通域法(Connected Components Method,CCs)[8-9],這些方法適合漢字字符間距較寬,無粘連字符的切分,盡管算法效率高,但不能適用于粘連或交叉字符串的切分?；诠P劃結(jié)構(gòu)切分是一種很有潛力的切分方法,可以從另一個角度解決筆畫粘連問題。常見的筆畫分割方法有筆畫連接盒的動態(tài)算法和黑游程跟蹤提取筆畫算法兩種[10-13]。有學(xué)者提出采用先提取筆畫再合并的方法,但該方法對漢字切分的好壞很大程度上依賴于筆畫提取的好壞,其主要應(yīng)用障礙就在于準(zhǔn)確提取筆劃難度較大。如何有效地提取筆劃信息仍有待進(jìn)一步研究。此外筆畫先提取后合并使算法過于復(fù)雜?；谧R別的字符統(tǒng)計切分方法是將字符切分和識別視為整體,切分后的字符送入相應(yīng)分類器并獲得一個分類結(jié)果,再由分類結(jié)果反作用于字符切分,從而獲得更有效的字符切分效果,這一過程不斷地迭代,直至滿足某一終止條件[12,14-15]。該方法結(jié)合了前兩類方法的優(yōu)點,能獲得更好的字符切分效果,但對于有限的時間和空間資源下獲得字符切分結(jié)果的情況卻是不適用,時間復(fù)雜度和空間復(fù)雜度遠(yuǎn)超過前兩類方法。

與上述字符切分相比,脫機(jī)手寫字符重心定位方法具有自身的獨特之處,即將字符軌跡上的像素點視為信息源,每個信息源以某種方式進(jìn)行信息擴(kuò)散與聚集以形成文本圖像的信息矩陣,再由信息矩陣的局部峰值分析獲得字符重心定位。該方法既可以準(zhǔn)確地得到單個字符在文本圖像中的位置,又可以由字符重心來區(qū)分單體、左右或上下結(jié)構(gòu)的字符。對于傾斜文本行、不規(guī)則文本片段以及粘連字符的脫機(jī)手寫體文本,字符重心定位方法能夠快速準(zhǔn)確地區(qū)分不同字符,進(jìn)而為后續(xù)的單或多字符識別以及非顯著切分式文本識別提供有力的支持。為此,本文做了如下三個方面的工作:(1)基于連通域分析法進(jìn)行文字高度估計,多個離散位置的像素點進(jìn)行連通域分析以獲得對應(yīng)文字或部首的連通區(qū)域,能夠避免單一像素點所產(chǎn)生的連通導(dǎo)致字符高度估值偏差;(2)基于信息擴(kuò)散的文本圖像信息量矩陣,該矩陣的局部峰值對應(yīng)漢字重心位置,而信息量低谷區(qū)分不同字符。(3)信息量矩陣的局部峰值分析,將信息量的局部峰值位置或區(qū)域的中心設(shè)置為對應(yīng)字符的重心以完成字符重心定位這一目標(biāo)。

1 脫機(jī)手寫字符重心定位方法

對于脫機(jī)手寫體文本圖像而言,圖像的二維數(shù)組表示形式為X={xij}a×b,其中i和j分別代表圖像的第i行和第j列;xij代表圖像的第i行j列上的像素值,二值化處理后的像素取值為0或1;a和b分別代表脫機(jī)手寫文本圖像的高和寬。

1.1 實現(xiàn)原理

重心是在重力場中物體處于任何方位時所有各組成質(zhì)點的重力的合力都通過的那一點。在脫機(jī)手寫體字符重心定位研究中,字符重心可以理解為字符中所有像素點合力作用下的點[16]。字形對稱的字符重心是其所在區(qū)域的中心位置。反之,字形不對稱的字符重心將偏向于筆跡像素點密集的一側(cè)。與真實物體重心性質(zhì)不同,真實物體的重心不一定在物體上,如一根彎曲的竹子重心往往偏向于內(nèi)弧側(cè),而單個字符重心則處于字符所占區(qū)域中,該區(qū)域是由字符的最左、最右、最上和最下四個極值位置的像素點共同確定的。因此,脫機(jī)手寫體字符重心可以用于定位不同字符在文本圖像中所對應(yīng)的位置。

圖1給出了脫機(jī)手寫體文本的字符重心定位流程圖,主要包括脫機(jī)手寫文本圖像預(yù)處理、字符高度估計、信息量矩陣構(gòu)造和信息量局部峰值分析四個方面。對待識別的脫機(jī)手寫體文本圖像進(jìn)行預(yù)處理能夠減少噪聲信息對后續(xù)識別效率的影響;運用連通域分析法進(jìn)行字符高度估計,并將其作為一個自適應(yīng)變量,它與文本圖像的字符大小直接關(guān)聯(lián);運用信息量傳遞方式構(gòu)造脫機(jī)手寫體文本的信息量矩陣,形成筆跡像素點的信息聚集;運用信息量矩陣的局部峰值分析以完成字符重心定位。

Fig.1 Flow chart of the offline handwritten character centroid localization圖1 脫機(jī)手寫字符重心定位流程圖

本文的研究重點在脫機(jī)手寫文本字符重心定位問題,即對待識別的脫機(jī)手寫體文本圖像進(jìn)行預(yù)處理能夠減少噪聲信息對后續(xù)識別效率的影響?？紤]到脫機(jī)手寫體文本圖像來源的多樣化,如掃描儀、照相機(jī)、手持移動等設(shè)備,對這些設(shè)備獲得的彩色或灰度圖像進(jìn)行圖像灰度化、背景色移除和圖像二值化等操作,完成字符與背景分離。進(jìn)一步地,可以對二值化圖像進(jìn)行濾波去噪聲信息處理,以降低噪聲信息對字符重心定位的影響。

1.2 基于連通域的文字高度估計

基于連通域的文字高度估計能夠自適應(yīng)不同文本的字符高度或同一文本不同區(qū)域的字符高度,避免固定字符高度對脫機(jī)手寫字符重心定位的不利影響。字符高度h作為一個自適應(yīng)量,與脫機(jī)手寫文本圖像的字符大小存在直接關(guān)聯(lián)。為了更好地運用連通域分析法進(jìn)行字符高度估計,給出相鄰像素點和連通域概念,其中前者中每個像素點存在八個相鄰像素點(除邊緣位置),分別處于該像素點的左、右、上、下、左上、右上、左下和右下八個位置;后者中每個連通域是由若干個筆跡像素點組成的序列,該連通域的高度是由最上方的筆跡像素點位置與最下方的筆跡像素點的位置之差。

運用連通域分析法進(jìn)行文字高度估計,具體步驟如下:步驟一：以文本圖像的左上角和右下角為極限位置,隨機(jī)選擇k個位置點,即{(x1,y1),(x2,y2),…,(xk,yk)},其中k≥10;步驟二：獲取每一個隨機(jī)位置點的最鄰近筆跡像素點,當(dāng)該位置點的像素值為1,則最鄰近像素點為自身。對第i個隨機(jī)位置點(xi,yi)而言,最鄰近筆跡像素點(xi,yi)應(yīng)滿足如下條件:

(1)

1.3 基于信息擴(kuò)散與聚集的信息量矩陣構(gòu)造

信息量擴(kuò)散與聚集方式構(gòu)造脫機(jī)手寫體文本的信息量矩陣,設(shè)第i行j列非零值的像素點xij含有的信息量為1個單位,對近鄰像素點的信息傳遞量info與它們的距離dist成反比,其中信息傳遞量與距離的函數(shù)關(guān)系info=fun(dist)可以采用一次函數(shù)、二次函數(shù)和對數(shù)函數(shù)等,本文實驗的信息傳遞量與距離設(shè)定為二次函數(shù)關(guān)系。像素點xij信息傳遞影響的最遠(yuǎn)像素距離為k,即該像素點收到像素點xij信息傳播量為0或無窮等于0。為此,對像素點xij構(gòu)造大小(2k+1)×(2k+1)的影響力矩陣info(2k+1)×(2k+1),其中infok+1,k+1=1代表像素點xij對自身信息傳播量為1個單位,而對其鄰近k范圍內(nèi)的像素點xi′j′的信息傳遞量infoi′,j′=fun(disti′j′)。

(2)

其中infoi,j表示2k+1行2k+1列矩陣,info+(i±k,i±k)表示矩陣info+的第i-k到i+k行、第j-k到j(luò)+k列的子矩陣,將信息量矩陣info+對應(yīng)位置的值加上infoi,j并更新。另外,圖像X邊緣像素點的信息量化需要特別處理,如第1行1列的像素點x1,1僅對處于其第四象限的像素點發(fā)揮作用,以及第a行b列的像素點xa,b僅對處于其第二象限的像素點發(fā)揮作用。

1.4 信息量矩陣的局部峰值分析

(3)

Fig.2 Information quantity relation between local peak and nearest neighbor pixels圖2 局部峰值與最近鄰像素點的信息量關(guān)系

1.5 算法實現(xiàn)

基于信息傳遞與聚集的脫機(jī)手寫字符重心定位的算法實現(xiàn)主要包括脫機(jī)手寫文本圖像預(yù)處理、基于連通域的字符高度估計、基于信息擴(kuò)散與聚集的信息量矩陣構(gòu)造和信息量矩陣的局部峰值分析四個部分。OHCCL算法的輸入是待處理的脫機(jī)手寫文本圖像X,字符高度估計的隨機(jī)數(shù)k;輸出是字符重心定位數(shù)據(jù)Y。具體實現(xiàn)內(nèi)容如下:

算法1 基于信息擴(kuò)散與聚集的脫機(jī)手寫字符重心定位方法

輸入:脫機(jī)手寫文本圖像數(shù)據(jù)X={xij}a×b,字符高度估計的隨機(jī)數(shù)k

輸出:字符重心數(shù)據(jù)Ya×b

Step 1 脫機(jī)手寫文本圖像預(yù)處理,對脫機(jī)手寫文本圖像X進(jìn)行灰度化、背景色移除和二值化等預(yù)處理,降低噪聲信息對字符重心定位的影響。

圖3脫機(jī)手寫字符重心定位執(zhí)行效果圖,從圖中可知,這份學(xué)生紙質(zhì)答題試卷的書寫工整、字跡清晰,但是存在字符粘連、文本行傾斜和零散等問題。圖3(a)脫機(jī)手寫文本原始圖,存在深色背景色;圖3(b)已完成預(yù)處理之后的脫機(jī)手寫文本圖像,字符筆跡與文本背景的顏色分別為黑色和白色;圖3(c)運用了信息擴(kuò)散與聚集的脫機(jī)手寫文本圖像的信息量矩陣,圖中顏色由白色至黑色代表了對應(yīng)位置的信息量由少到多的對應(yīng)關(guān)系,其中字符重心偏向于圖中顏色最深的位置;圖3(d)運用了信息量矩陣的局部峰值分析所得到的字符重心,實心圓點代表了字符重心位置。

Fig.3 Offline handwritten character centroid localization demonstration圖3 脫機(jī)手寫字符重心定位的執(zhí)行效果圖

2 實驗結(jié)果及分析

2.1 實驗數(shù)據(jù)集

HIT-MW數(shù)據(jù)庫由哈爾濱工業(yè)大學(xué)計算機(jī)學(xué)院開發(fā),該數(shù)據(jù)庫由780多名書寫者在無監(jiān)督的情況下書寫完成,優(yōu)化出合格的手寫樣本853份,其中無監(jiān)督情況是指在書寫參與者與數(shù)據(jù)庫收集者并不發(fā)生正面接觸,通過郵寄等方式將數(shù)據(jù)庫頁面交與書寫者,書寫者按照自己習(xí)慣的書寫規(guī)則在一塊未經(jīng)分格的區(qū)域書寫題簽上標(biāo)注的內(nèi)容,允許出現(xiàn)涂改、文本行傾斜和交疊等復(fù)雜手寫現(xiàn)象[17]。HIT-MW數(shù)據(jù)庫中的手寫體樣本不是按照孤立的漢字書寫,而是按照一定的規(guī)則從《人民日報》上隨機(jī)抽取的一段200字左右具有一定含義的文字。

2.2 實驗設(shè)置

脫機(jī)手寫字符重心定位方法通過字符筆跡像素點的信息量擴(kuò)散與聚集以獲取脫機(jī)手寫文本中的字符重心,投影法(Pros)[7]和連通域法(CCs)[8]作為兩種參與比較的經(jīng)典字符重心定位方法,其中投影法實現(xiàn)字符重心定位的前提是文本的行信息已知。由于手寫風(fēng)格、文本排版和字符結(jié)構(gòu)等差異,導(dǎo)致OHCCL方法獲得單字符的重心數(shù)目存在不確定性,大體上可以歸為四類,即“0重心”“1重心”“2重心”和其他。“0重心”代表字符重心定位失敗,未能準(zhǔn)確獲得對應(yīng)字符重心;“1重心”代表獲得對應(yīng)字符重心且唯一;“2重心”代表獲得對應(yīng)字符重心的數(shù)目等于2;其他代表獲得對應(yīng)字符重心的數(shù)目大于等于3。考慮到中文字符的單一結(jié)構(gòu)、上下或左右結(jié)構(gòu),脫機(jī)手寫字符重心定位的準(zhǔn)確率由“1重心”和“2重心”共同決定。對于給定的脫機(jī)手寫體文本而言,“0重心”的字符數(shù)為m0,“1重心”和“2重心”所對應(yīng)的字符數(shù)為m1,其他情況所對應(yīng)的字符數(shù)為m2,那么脫機(jī)手寫文本的字符總數(shù)目n=m0+m1+m2,字符重心定位的準(zhǔn)確率定義為:

(4)

字符重心定位的丟失率定義為:

(5)

2.3 實驗結(jié)果

從表1可知,Pros和CCs的中文字符重心的定位準(zhǔn)確率分別為85.31%和91.55%,而OHCCL方法對中文字符重心的定位準(zhǔn)確率達(dá)到98.70%,丟失率率僅為0.32%,定位準(zhǔn)確率提升了15.70%和7.81%。在數(shù)字字符的定位準(zhǔn)確率上,Pros和CCs準(zhǔn)確率分別為87.80%和94.23%,OHCCL方法在數(shù)字定位的準(zhǔn)確率為94.82%。由于各個標(biāo)點符號在不同行的相對位置及與字符或數(shù)字的間隙差異,CCs取得了最優(yōu)標(biāo)點符號的定位準(zhǔn)確率,其值為95.58%,Pros和OHCCL標(biāo)點符號的定位準(zhǔn)確率分別為81.04%和95.14%。

中文字符具有“外圓內(nèi)方”的特征,有利于字符筆跡像素點的信息量聚集以獲得對應(yīng)字符的重心,但也存在部分結(jié)構(gòu)復(fù)雜的中文字符獲得了過多的字符重心,即其他情況為0.98%。數(shù)字字符和標(biāo)點符號的筆跡信息量少和非規(guī)范的書寫風(fēng)格也放大他們的字符重心定位的丟失率,對應(yīng)的丟失率分別為5.18%和4.86%。

表1 HIT-MW字符重心定位結(jié)果(%)

3 總結(jié)與展望

針對脫機(jī)手寫文本的傾斜文本行、不規(guī)則行片段和粘連字符等問題,提出了一種基于信息擴(kuò)散與聚集的脫機(jī)手寫體字符重心定位方法,該方法通過字符筆跡像素點的信息傳播方式實現(xiàn)信息聚集形成局部峰值而相鄰字符之間產(chǎn)生信息量低谷,字符重心設(shè)為信息量的局部峰值位置或區(qū)域的中心。該方法的優(yōu)點是在字符重心定位過程中擺脫了文本行概念的束縛,減少了傾斜文本行的糾正、不規(guī)則文本行片段的規(guī)整以及連筆字符的過切分等操作,使得脫機(jī)手寫字符重心定位的步驟更簡潔且貼近實際應(yīng)用。本文所實驗的數(shù)據(jù)集規(guī)模還較小,下一步工作是擴(kuò)大真實數(shù)據(jù)集的規(guī)模、形成公開學(xué)生答題試卷數(shù)據(jù)集并深入研究脫機(jī)文本結(jié)構(gòu)分析與識別。