二階段手寫漢字骨架提取優(yōu)化

陳泓漢,王 濤,熊顯航

(1.華南師范大學 人工智能學院,廣東 佛山 528200;2.華南師范大學 計算機學院,廣東 廣州 510631)

0 引 言

圖像細化是在保持原圖像拓撲結(jié)構(gòu)的情況下,抽出圖像的單像素寬度過程[1]。目前細化算法已廣泛應用于運動檢測[2]、農(nóng)作物[3]、裂縫檢測[4-5]、工業(yè)儀表[6]和漢字研究[7]等場景。

文獻[8]提出基于ZS算法的改進方法,通過刪除保留模板得到單像素且毛刺更少骨架。針對骨架多分叉點未合并問題,文獻[9]引入圓盤對其進行合并,繼而修復。方法過程清晰,但分叉點會過度合并。通過骨架輪廓圓盤半徑信息,文獻[10]對畸變處進行修復,該方法過程耗時較多。文獻[11]提出復雜區(qū)域檢測法,并根據(jù)筆段方向及曲率進行修復。該方法只適用字體寬度較細情況。

文中算法借鑒文獻[9-10]中的圓盤概念,考慮漢字方正特性使用矩形進行分叉檢測。采用了二階段聚類合并克服文獻[9]以及文獻[11]存在的問題。根據(jù)區(qū)域畸變程度采用不同范圍修復,同時對畸變區(qū)域歸類,采用相應修復策略。

1 算法描述

提出的改進算法核心優(yōu)化思路可分為兩個階段。第一階段是為了精準找到字體畸變待修復區(qū)域即筆畫的交錯處以及拐點處,通過引入字體寬度Wf概念進行的二階段合并提高對不同字體交叉區(qū)域識別的準確率;第二階段需要劃分畸變區(qū)域類型并采取相應的策略進行修復。

文章在傳統(tǒng)判斷拐點的基礎(chǔ)上,進行二次篩選合并得到符合分叉點特征的點。第二階段是根據(jù)畸變區(qū)域信息,清空畸變區(qū)域重新連接分叉點,形成更符合該手寫漢字風格的骨架連接圖。

1.1 分叉點檢測

目前分叉點檢測方法常見的有角點檢測法[12]和段化法,這兩種方法都是在原始文字圖像上進行處理,存在檢測耗時長以及誤判多等問題。

文章提出的分叉點檢測處理是細化后骨架,分為兩階段,一階段主要是篩選出分叉特征點,二階段為對篩選的特征點簇群進行聚類合并,從而得到準確的單分叉點。

定義1 字體寬度Wf:未經(jīng)細化字體二值圖前景點數(shù)量與細化后的骨架全景點數(shù)量的比例,稱為字體寬度Wf,計算過程如式(1)所示:

(1)

其中,N(S)為細化后骨架圖前景點數(shù),N(0)為原二值圖前景點數(shù)

定義2 向量夾角:局部向量所形成的角度,如aij趨向于1時,表示兩向量為平行關(guān)系,通過余弦相似度可以量化分支的方向關(guān)系,具體計算過程如式(2)所示:

(2)

1.1.1 分叉特征點篩選

得到細化后的骨架與原圖信息,通過計算得到該手寫漢字字體寬度Wf,待篩選的特征點為Sd={P0|A(P0)≥3,P0=1},即該點滿足的8-鄰域存在三個以上的前景點數(shù)。篩選流程如下:

(1)以Wf為范圍對Sd進行分類得到簇群;

(2)從單簇群任選三點形成向量vi、vj;

(3)如aij≠1,加入點集Sdf;

(4)重復遍歷簇群,得到所有滿足的點。

1.1.2 分叉特征點聚類合并

集合Sdf為特征點簇群,不能有效表示單個分叉區(qū)域,因此還需進行聚類合并[13]。為解決過度合并分叉點以及未能正確合并的問題,文中的聚類合并分兩階段進行,一階段篩選區(qū)域畸變程度小的分叉點,二階段合并區(qū)域程度畸變大的分叉點。

在進行聚類合并前,需要了解二階段聚類合并得到的不僅是分叉點,考慮畸變程度不同,待修復面積也應有所區(qū)別,因此引入修復區(qū)域概念。

定義3 修復區(qū)域:動態(tài)矩形的中心為最優(yōu)分叉點PL,動態(tài)邊長為Ldy,未經(jīng)過第二階段聚類合并Ldy為Wf。

一階段聚類合并是為了得到緊密的分叉點簇群。根據(jù)單簇群中坐標的x、y均值,得到修復區(qū)域的PL坐標,Ldy為字體寬度Wf。此時細化得到的骨架畸變較小區(qū)域已被正確識別,依然存在未能正確合并的情況,因此需要二階段的聚類合并操作。同時為了防止合并錯誤,引入了定義4、5。

定義4 延展分支特征點:分叉特征點P0可以不經(jīng)過任何其他分叉特征點到達端點。

定義5 標準T型分叉特征點:分叉特征點P0在矩形Ldy為字體寬度Wf局部范圍內(nèi)滿足標準十字以及T型的骨架結(jié)構(gòu)。

在第二階段,距離min Pts為字體寬度Wf,得到待合并點簇Smerge。同時補充了3個限制條件防止過度合并,具體如下:

(1)如單簇待合并分叉點數(shù)超過3,任取三點形成aij,aij→1滿足合并條件;

(2)單簇中存在兩個以及以上延展分支特征點,則該簇不滿足合并條件;

(3)單簇中存在一個或多個標準T型分叉特征點,則該簇不滿足合并條件。

條件1、2主要是防止手寫字體局部筆畫過于密集導致分叉點的誤合并;條件3主要是避免標準的細化骨架結(jié)構(gòu)被過度合并。三個限制條件合理保留了傳統(tǒng)細化算法可準確細化的區(qū)域,同時也避免了局部最優(yōu)分叉點過于密集產(chǎn)生,以至于過度合并丟失了骨架應有的細節(jié)。結(jié)果如圖1所示。

圖1 合并局部最優(yōu)分叉點結(jié)果

經(jīng)過第二階段合并后修復區(qū)域的邊長Ldy以及中心坐標PL,分別為:

Ldy=max(xmax-xmin,ymax-ymin)

(3)

PL=(xmin+Ldy,ymin+Ldy)

(4)

其中,xmin、xmax、ymin、ymax為Smerge中待合并點的修復區(qū)域中x、y坐標的最小和最大值,經(jīng)過二階段得到的待修復分叉點(PL,Ldy)的集合用Sdy表示。

1.2 分叉點修復

根據(jù)二階段聚類合并得到的待修復集合Sdy,分析集合Sdy中(PL,Ldy)形成動態(tài)矩形與骨架形成的交界點。同時依據(jù)漢字筆段形成規(guī)律[14-15],結(jié)合待修復區(qū)域與骨架相交點信息,將分叉點進行歸納分類。

為了更好地進行分析,歸納出定義6～11五種類型的畸變區(qū)域?qū)罄m(xù)修復策略。

定義6 交界點可延展性:如延展Wf的距離,得不到骨架上的點則認為不可延展。

定義7 四通區(qū)域類型:交界點集數(shù)為4,各點滿足交界點集四邊界有且僅有一點。

定義8 三通區(qū)域類型:分叉點交界點集數(shù)為3,其中四邊界各有且僅有一點,且各邊界點都具有可延展性。

定義9 毛刺區(qū)域類型:分叉點交界點集數(shù)為3,其中四邊界各有且僅有一點,同時僅存在一邊界點具有不可延展性。

定義10 拐角區(qū)域類型:交界點集中個數(shù)為2,其中四邊界各有且僅有一點,兩邊界為相鄰關(guān)系。

定義11 多通區(qū)域類型:四邊界存在任意一邊界存在兩個及以上的交界點。

待修復分叉點類型如圖2所示。

圖2 待修復分叉點類型

圖3為交叉區(qū)域類型歸類流程,具體描述如下:

圖3 交叉區(qū)域類型歸類流程

(1)遍歷集合Sfix中的元素點,如該區(qū)域滿足毛刺區(qū)域類型定義,則可直接歸類;

(2)單邊界判斷,如該點四邊界點集存在任意邊界,存在兩個及以上的分支,歸類為多通區(qū)域類型;

(3)根據(jù)交界點集Num進行分類,如Num為2,歸類為拐角區(qū)域類型;

(4)匹配分析為根據(jù)分支局部斜率找到于與走勢相近的分支,如圖2中四通區(qū)域類型,南北分支的局部斜率aij→1,則可將南北分之判定為匹配關(guān)系;

(5)得到匹配關(guān)系后,根據(jù)當前交界點集Num為3歸類為三通區(qū)域類型,否則為四通區(qū)域類型。

通過上述交叉區(qū)域類型歸類流程,可得到相應區(qū)域類型,接下來需要根據(jù)相應的區(qū)域類型展開修復工作。

四通區(qū)域類型修復策略根據(jù)得到的匹配關(guān)系集合,處理流程如下:

(1)將兩相匹配的邊界點按照局部斜率進行延展;

(2)存在未處理的點,計算兩點到PL與匹配點相交的直線距離,取最小距離方案將未處理點與之相連。

由圖4可看出,常見的四通區(qū)域類型根據(jù)分支匹配進行準確修復,修復后區(qū)域走勢自然,也很好地解決了筆畫錯誤粘貼問題。

圖4 四通區(qū)域類型修復

三通區(qū)域類型修復策略處理流程如下:

(1)如存在匹配關(guān)系集合,則將匹配的邊界點按局部斜率延展相連;

(2)未處理的點按該點的局部斜率進行延展,連接到匹配分支形成的直線上;

(3)如不存在匹配關(guān)系,則將待修復點集都連接到PL上。

如圖5所示,骨架交錯區(qū)域發(fā)生畸變,此處的筆畫走勢顯得抖動,不符合實際字體的特點。通過局部斜率將筆畫延展相交在一起,正確還原了筆畫趨勢。

圖5 三通區(qū)域類型修復

拐角區(qū)域類型處存在毛刺問題并沒形成單獨分支,產(chǎn)生的毛刺是因為細化發(fā)生輕量畸變。因此對該區(qū)域進行局部斜率重連,因此采取的拐點區(qū)域類型修復策略為:

(1)將各交界點按照局部斜率延展,得到相交點;

(2)交界點連接到相交點上。

經(jīng)過拐點修復策略后的骨架效果如圖6所示,其產(chǎn)生的毛刺都被有效處理,局部筆畫抖動基本消失。

圖6 拐角區(qū)域類型修復

毛刺區(qū)域類型因存在邊界點具有不可延展性導致該區(qū)域存在較大的毛刺,相關(guān)結(jié)果如圖7所示,毛刺區(qū)域類型修復策略的處理流程如下:

圖7 毛刺區(qū)域類型修復

(1)得到未能延展的交界點Pex;

(2)清除Pex到端點間的前景點;

(3)將其余的交界點按局部斜率延展相交。

漢字結(jié)構(gòu)產(chǎn)生多通區(qū)域類型都是多筆畫的聚集點,對多通策略的處理流程如下:

(1)通過修復信息Sdy得到分叉點PL;

(2)將交界點連接到分叉點PL上。

由于不同筆畫在這個分叉點匯集,筆畫的斜率以及粗細導致細化算法在此處是必然發(fā)生畸變的,修復策略將不同的分支邊界點連接到二階段合并得到的最優(yōu)分叉點上,效果如圖8所示。

圖8 多通區(qū)域類型修復

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

通過實驗驗證文中算法的有效性。實驗環(huán)境如下:操作系統(tǒng)為windows10,處理器為英特爾7700k,16G運行內(nèi)存,使用跨平臺計算機視覺OpenCV。使用顏真卿的楷書作品《多寶塔碑》、田英章《弟子規(guī)》以及《九成宮醴泉銘》共967個楷書字體作為實驗數(shù)據(jù)。

2.1 交叉點檢測算法對比

在使用細化算法得到骨架后,首先通過計算原圖像有效點與骨架有效點比例得到Wf后,根據(jù)提出的交叉點檢測算法得到待修復集合Sdy,為更好量化不同分叉點檢測算法的性能,提出相關(guān)定義12～16。

定義12 人工標注分叉點Pmark:對實驗數(shù)據(jù)的原圖進行人工處理,標記所有分叉區(qū)域的中心位置點作為Pmark。

定義13 分叉點檢測準確率BRR:如單Pmark有且僅被Sdy集合中(PL,Ldy)形成的動態(tài)矩形覆蓋,則認為該被正確識別。分叉點檢測準確率BRR等于被正確識別的分叉點數(shù)占人工標注分叉點數(shù)的比率。

定義14 過度合并分叉點率ORR:Sdy集合中(PL,Ldy)形成的動態(tài)矩形覆蓋兩個及以上Pmark,則認為存在過度合并的情況。ORR等同于過度合并的Pmark與人工標注分叉點數(shù)的比率。

定義15 未合并分叉點率URR:Sdy集合中存在兩個及以上(PL,Ldy)形成動態(tài)矩形覆蓋單Pmark,則認為Sdy集合存在未能正確合并情況。URR等同于未合并的(PL,Ldy)數(shù)與人工標注分叉點數(shù)的比率。

定義16 錯誤檢測率ER:Sdy集合中存在(PL,Ldy)形成動態(tài)矩形未能覆蓋任何Pmark。ER等同于未能覆蓋任何Pmark的(PL,Ldy)數(shù)與人工標注分叉點數(shù)的比率。

圖9為文中交叉點檢測算法與最大圓盤法[9]以及復雜區(qū)域檢測算法[11]的對比實驗結(jié)果。從左到右依次書寫字體原圖,最大圓盤法過程分析圖,最大圓盤法結(jié)果,復雜區(qū)域檢測算法結(jié)果以及文中算法得出的交叉點結(jié)果。

圖9 不同交叉點檢測算法結(jié)果對比

從對比結(jié)果可以看出,最大圓盤法[9]存在過度合并的問題,導致最終在分叉點密集區(qū)域,多分叉點被錯誤識別成單分叉點。復雜區(qū)域檢測算法[11]對畸變程度較大的區(qū)域進行未正確識別合并,從而導致單分叉點檢測成兩個或以上的分叉點。文中提出的二階段檢測法正確識別到分叉點,同時對畸變區(qū)域范圍也作出更準確動態(tài)調(diào)整。

表1 分叉點檢測算法準確率 %

2.2 骨架修復對比

實驗中,絕大部分骨架畸變區(qū)域都被二階段檢測算法很好地識別檢測到。受文獻[16]中相似度計算方法以及文獻[17]提出的骨架特征不變量描述接合點啟發(fā),此處將人工標注正確的骨架與經(jīng)優(yōu)化算法得到的骨架進行重合度比較,作為衡量不同細化算法的性能指標。表2中的數(shù)據(jù)是指識別到的分叉區(qū)域按照修復類型進行修復,未修復導致的原因是不滿足文章提出的修復類型,導致不能找到相應的修復策略,可以看出通過二階段檢測出的分叉區(qū)域都能很好歸類成修復類型,并采取了相應的修復。修復效果對比如圖10所示。

表2 細化實驗效果統(tǒng)計

圖10 不同骨架提取算法結(jié)果

定義17 策略覆蓋率SCR:待修復集合Sfix歸類成區(qū)域類型的成功率,策略覆蓋率SCR等同于歸類區(qū)域類型個數(shù)占人工標注分叉區(qū)域數(shù)量的比率。

定義18 骨架提取準確率ERR[11]:對畸變區(qū)域進行人工標注骨架,ERR等同于重合骨架點數(shù)占標注骨架總點數(shù)比率,若所提骨架與標準骨架一致,則所有骨架點應重合。

根據(jù)表2數(shù)據(jù)可以得出,未能修復區(qū)域主要是因為分叉區(qū)域得不到歸類的區(qū)域類型。從SCR可知,對于區(qū)域類型歸類已經(jīng)很好覆蓋不同筆畫交錯形成的畸變區(qū)域,文獻[11]提出的骨架提取準確率可以很好地作為修復效果量化指標。為進一步量化區(qū)域修復的效果,通過對比標注骨架與文中的修復策略得到的優(yōu)化區(qū)域骨架重合比率,驗證文中算法的有效性。提出的優(yōu)化算法在二階段聚類合并因為限制條件判斷過程,導致算法的時間會增多,而文獻[9]在計算最大圓盤方面消耗以及計算圓盤與骨架交點的計算時間花銷占重較大。

文獻[9]方法根據(jù)最大圓盤獲取到中心點進行連接,對于拐角處的修復有著不錯效果,由于沒有三通以及四通分叉區(qū)域筆畫走勢延伸等分析,修復方面效果不足。因此可得出文章提出的優(yōu)化算法更高效可行。

3 結(jié)束語

文章提出的交叉點檢測算法更合理適用字體寬度Wf以及動態(tài)矩形概念識別分叉點,經(jīng)實驗驗證可更準確識別分叉區(qū)域。通過提出的修復策略可覆蓋絕大部分字體畸變的區(qū)域,修復后的骨架更能反映出手寫漢字的特征,筆畫會更為順暢且交叉以及拐角區(qū)域的筆畫走勢更為自然。提出的優(yōu)化算法是基于細化后骨架結(jié)果進行修復,不針對具體細化算法畸變問題,可適用范圍更廣。

二階段優(yōu)化算法適用于較為規(guī)則的手寫漢字,對于筆畫走勢靈活或是筆畫相對潦草的草書等風格字體,該算法修復效果不足。因此后續(xù)工作會針對走勢更靈活、潦草的草書[18]進行相應研究以及骨架提取優(yōu)化。