基于二值圖像的手寫體快速細(xì)化算法*

曹良斌，游莉萍，劉筆余，張軒宇，周愷卿，莫禮平

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

從實際環(huán)境中切分出的手寫體字符圖像常伴隨著邊框粘連、隨機(jī)污點、光照不均勻等現(xiàn)象，因此在應(yīng)用識別算法處理手寫體圖像前，往往需要對手寫體字符圖像進(jìn)行預(yù)處理操作[1-2].手寫體細(xì)化是圖像預(yù)處理的主要步驟之一，其實質(zhì)是求手寫體骨架的過程[3].手寫體細(xì)化算法通過保留圖像中與字符有關(guān)的信息來提取字符特征[4-7]，從而確保輸出的二值圖像畫面清晰、邊緣明顯.筆者針對查表算法的缺點，提出一種充分利用手寫體節(jié)點的快速細(xì)化算法，以期達(dá)到減少模板數(shù)量、縮短匹配過程耗時、優(yōu)化細(xì)化結(jié)果的目的.

1 常見的手寫體細(xì)化算法

1.1 中軸變換算法

圖1 基于中軸變換算法的細(xì)化結(jié)果Fig. 1 Thinning Result Baded on Medial Axis Transformation Algorithm

目前，常用的手寫體細(xì)化算法主要分為中軸變換算法、找中點算法和查表算法[8-9].中軸變換算法主要是計算手寫體筆劃線上的內(nèi)部像素點P到邊界像素點的距離d.若存在2個以上的邊界點到點P的距離最小，則令點P為一個骨架點，所有的骨架點即可組合為骨架.基于中軸變換算法的手寫體細(xì)化結(jié)果如圖1所示.中軸變換算法的主要缺點是：算法復(fù)雜度過高；同一個筆劃中可能出現(xiàn)多個骨架線；對原圖的清晰程度要求非常高；細(xì)化結(jié)果受噪聲影響較大；細(xì)化輸出的骨架在節(jié)點處可能出現(xiàn)斷線，不能保證線條的連通.

1.2 找中點算法

找中點算法主要是通過逐行(或逐列)掃描圖像，找出每一行(列)的連續(xù)像素點，并將像素點的個數(shù)記為H(n).若H(n)為奇數(shù)，則取該行(列)中心的點為細(xì)化結(jié)果；若H(n)為偶數(shù)，則取中間的左點或右點(上點或下點)為該行(列)的細(xì)化結(jié)果.找中點算法的優(yōu)點是原理簡單和運行速度快，主要缺點是無法準(zhǔn)確細(xì)化筆劃較粗的手寫體，以及無法保證細(xì)化結(jié)果的連通性.

1.3 查表算法

設(shè)手寫體一黑色像素點為P，點P的8鄰點為n0～n7，如圖2所示.在查表算法中，根據(jù)點P的8鄰點的像素取值情況判斷其是否為骨架點.判斷規(guī)則是：(1)刪除的點不能影響圖像中各分量的拓?fù)溧徑雨P(guān)系，即連通性；(2)骨架點需保留原始圖像的基本信息.在手寫體二值圖像中，任取一點P為中間點，黑色圖形像素點取值為1，白色背景像素點取值為0.根據(jù)鄰點情況判斷節(jié)點能否刪除.

n7n0n1n6Pn2n5n4n3

圖2點P的8鄰點

Fig.2EightAdjacentPointsofPointP

現(xiàn)舉例說明.設(shè)點P的8鄰點情況如圖3所示.根據(jù)鄰點的情況判斷節(jié)點能否被刪除：圖3a中，點P不能被刪除，因為它是內(nèi)部點，刪除后骨架無法連通；圖3b中，點P不能被刪除，因為刪除它會導(dǎo)致左右點斷開，骨架無法連通；圖3c中，可以刪除點P，因為它不是骨架點，刪除后不影響輸出骨架的連通性.

0001P1000a例10101P1011b例20100P1000c例3圖3 P點的鄰點情況Fig.3 AdjacentPointsofPointP

因為點P的鄰點取值為0或1，8鄰點有256種組合方式，所以查表算法相應(yīng)地需要處理256個模板.查表算法的優(yōu)點是清晰簡潔，主要缺點是：需要256個模板，前期準(zhǔn)備工作煩瑣；執(zhí)行過程中需依次匹配256個模板，耗時多，效率較低；非骨架像素點不一定能被刪除.

2 改進(jìn)的手寫體細(xì)化算法

2.1 算法相關(guān)說明

給定一黑色像素點P，坐標(biāo)為P(x,y).點P的4鄰點分別為點集n2(x+1,y),n6(x-1,y),n4(x,y-1),n0(x,y+1)；8鄰點分別為點集n3(x+1,y-1),n4(x,y-1),n5(x-1,y-1),n6(x-1,y),n7(x-1,y+1),n0(x,y+1),n1(x+1,y+1),n2(x+1,y).8鄰點中取值為1的黑色像素點的個數(shù)為N(P).點P的8鄰點和4鄰點如圖4所示.

n7(x-1,y+1)n0(x,y+1)n1(x+1,y+1)n6(x-1,y)P(x,y)n2(x+1,y)n5(x-1,y-1)n4(x,y-1)n3(x+1,y-1)

圖4點P的8鄰點和4鄰點

Fig.4EightAdjacentPointsandFourAdjacentPointsofPointP

2.2 算法思想及流程

改進(jìn)的手寫體快速細(xì)化算法，需先建立一張合理的索引表來記錄哪些情況可以標(biāo)記點P，哪些情況不可以標(biāo)記點P.算法思想：掃描手寫體二值圖像，將二值圖像中的點P及其鄰點情況與索引表匹配，根據(jù)匹配結(jié)果來判斷點P是否被標(biāo)記；二值圖像中的點P都被掃描完后，統(tǒng)一刪除所有的標(biāo)記點；執(zhí)行刪除步驟后，對二值圖像進(jìn)行新一輪的掃描，循環(huán)反復(fù)，直到掃描過程中沒有任何一點被標(biāo)記，此時剩下的點就是骨架點；將骨架點與優(yōu)化骨架寬度模板匹配，進(jìn)一步減小骨架寬度.算法流程如圖5所示.

圖5 算法流程Fig. 5 Algorithm Procedures

2.3 算法步驟

(ⅰ)對于手寫體二值圖像中的每一個黑色像素點P，根據(jù)以下規(guī)則判定點P是否被標(biāo)記：

(1)若N(P)=0，1，8，則標(biāo)記點P.

(2)若N(P)=2，5，6，且點P的鄰點是連續(xù)的(如圖6所示，鄰點n0，n1，n5，n6，n7取值為1，其余點取值為0)，則標(biāo)記點P，否則不標(biāo)記.

1111P0100

圖6N(P)=5,鄰點n0,n1,n5,n6,n7連續(xù)為1時的匹配模板

Fig.6MatchingTemplatewithN(P)=5andAdjacentn0,n1,n5,n6,n7being1

(3)若N(P)=3，點P能夠與圖7中任一模板匹配，則標(biāo)記點P.

0100P10011100P10000111P00000101P0100圖7 N(P)=3時的匹配模板Fig.7 MatchingTemplatewhenN(P)=3

(4)若N(P)=4，點P能夠與圖8中任一模板匹配，則標(biāo)記點P.

0111P01001100P1001圖8 N(P)=4時的匹配模板Fig.8 MatchingTemplatewhenN(P)=4

(5)若N(P)=7，點P的4鄰點有任意一點取值為0，且點P能夠與圖9中任一模板匹配，則標(biāo)記點P.

1011P11111110P11111111P01111111P1101圖9 N(P)=7,4鄰點有任意一點取值為0時的匹配模板Fig.9 MatchingTemplatewhenN(P)=7andanyoftheFourAdjacentPointsis0

(6)若點P能夠與圖10中的任一模板匹配，則不標(biāo)記點P，以保持線條的連通.

x0x1P1111x0xx001100P000x00000P1101100000x000P001100x

x0000P10001xx11x0P10x11x000x01P0x100圖10 保證線條連通的匹配模板Fig.10 MatchingTemplateGuaranteeingLineConncetion

(ⅱ)若圖像中所有點P都未被標(biāo)記，則執(zhí)行步驟3；否則令所有被標(biāo)記的點P取值為0，返回執(zhí)行步驟1.

(ⅲ)為減小骨架寬度，檢查圖像中的每一個點P.若點P能夠與圖11中任一模板及它們分別旋轉(zhuǎn)90°,180°,270°所得的模板匹配，則令點P取值為0，算法結(jié)束.

01x1P0x00x1x1P1x0x圖11 優(yōu)化后減少像素的匹配模板Fig.11 MatchingTemplateofPixedDecreaseAfterOptimization

2.4 算法分析

該算法簡化了查表算法的256個模板，并剔除了一些不必要的模板.根據(jù)算法的規(guī)則，需從查表算法的256個模板中選擇44個標(biāo)記模板用于判斷像素點P是否被標(biāo)記，并且增加了15個優(yōu)化模板用于改進(jìn)原查表算法骨架不唯一、骨架寬度過大的缺點.相比于傳統(tǒng)的查表細(xì)化算法，手寫體快速細(xì)化算法不再一一遍歷P點周圍的鄰點，而是根據(jù)N(P)值進(jìn)行相應(yīng)的分類與匹配，使得算法具有細(xì)化速度快，細(xì)化結(jié)果準(zhǔn)確的優(yōu)點.

3 實驗結(jié)果及討論

3.1 算法細(xì)化效果驗證

圖12示出對給定的一個字符按照手寫體快速細(xì)化算法步驟進(jìn)行細(xì)化操作的效果.對比原字符和細(xì)化效果發(fā)現(xiàn)，細(xì)化后的圖像保留了基本骨架，沒出現(xiàn)斷點、毛刺等情況，顯示了良好的細(xì)化效果.

圖12 手寫體快速細(xì)化算法效果驗證Fig. 12 Effect Verification of the Fast Thinning Algorithm of Handwriting

3.2 軟件運行效果

在Visual Studio 2013軟件中利用C#語言實現(xiàn)手寫體快速細(xì)化算法.圖13示出用戶在軟件中手寫輸入的小寫字母、大寫字母、數(shù)字經(jīng)運行算法后的細(xì)化效果.對比原字符和細(xì)化效果發(fā)現(xiàn)，該算法能準(zhǔn)確細(xì)化小寫字母、大寫字母、數(shù)字等圖像，且完好保留手寫體骨架.

圖13 軟件運行效果Fig. 13 Software Operation Effect

4 結(jié)語

通過分析手寫體節(jié)點與周圍像素鄰點的相對位置，提出了一種手寫體快速細(xì)化算法.算法繼承了查表算法清晰簡潔的優(yōu)點，并在查表算法的基礎(chǔ)上，整理和簡化了冗雜的模板，選擇更具有代表性的模板作為標(biāo)記樣本，減小了問題規(guī)模，降低了算法復(fù)雜度.實驗結(jié)果表明：改進(jìn)的手寫體細(xì)化算法完好地保留了手寫體骨架，字符特征被完好地提取出來；細(xì)化結(jié)果邊距明顯、無粘連邊框，能較好地應(yīng)用于文字識別、圖像處理和模式識別等領(lǐng)域.

[1] 姜 文，劉立康.基于聯(lián)合兩種特征的手寫體維文字符識別[J].計算機(jī)工程與應(yīng)用，2017，53(5)：192-196.

[2] 牟少敏，杜海洋，蘇 平，等.一種改進(jìn)的快速并行細(xì)化算法[J].微電子學(xué)與計算機(jī)，2013,42(1):53-55.

[3] 趙丹丹,王華彬,陶 亮,等.改進(jìn)的EPTA并行細(xì)化算法[J].計算機(jī)工程與應(yīng)用，2016,52(9):196-201.

[4] 韓建峰，宋麗麗.基于算法運算的改進(jìn)細(xì)化算法[J].現(xiàn)代電子技術(shù)，2013，36(14)：13-16.

[5] 薛玉利，彭玉華，周新虹.基于實值Gabor變換的掌紋識別[J].計算機(jī)工程與應(yīng)用，2007,43(6):216-219.

[6] 康文雄，鄧飛琪.利用模板和鄰域信息的靜脈骨架提取新算法[J].中國圖象圖形學(xué)報，2010，15(3):378-384.

[7] STERNBY J,MORWING J,ANDERSSON J,et al.On-Line Arabic Handwriting Recognition with Templates[J].Pattern Recognition,2009,42(12):3 278-3 286.

[8] 賀繼剛，楊曉偉，吳廣潮，等.基于模板保留的快速并行細(xì)化算法[J].計算機(jī)應(yīng)用與軟件，2007，24(12):26-28.

[9] 王家隆，郭成安.一種改進(jìn)的圖像模板細(xì)化算法[J].中國圖象圖形學(xué)報，2004，9(3):297-301.