基于改進(jìn)ZS細(xì)化算法的手寫體漢字骨架提取

常慶賀 吳敏華 駱力明

(首都師范大學(xué)信息工程學(xué)院 北京 100048)

0 引 言

手寫體漢字識別是模式識別的重要分支，也是文字識別領(lǐng)域最為困難的問題之一。細(xì)化是手寫體漢字識別與處理中的一個重要環(huán)節(jié)，其又可稱為骨架化，一般是指在保持圖像原像素拓?fù)滏溄雨P(guān)系的前提下，接連刪除圖像邊緣像素直至達(dá)到單個像素寬度骨架的過程。圖像細(xì)化所提取出的骨架不僅是目標(biāo)圖像重要的拓?fù)涿枋?，還減少了圖像中的冗余信息，在圖像分析、信息壓縮、特征提取、模式識別等領(lǐng)域具有非常廣泛的應(yīng)用[1-2]。

現(xiàn)有的細(xì)化算法有：Hilditch細(xì)化算法[3]、Pavlidis細(xì)化算法[4]、基于索引表的細(xì)化算法[5]、基于Voronoi圖的構(gòu)造模型細(xì)化算法[6-7]、基于輪廓篩減的細(xì)化算法[8]、Zhang-Suen細(xì)化算法[9-10]等。在應(yīng)用于細(xì)化手寫體漢字圖像時，由于漢字結(jié)構(gòu)較復(fù)雜，加之手寫體漢字書寫風(fēng)格隨意，Hilditch算法提取的骨架有扭曲變形的現(xiàn)象，且算法需反復(fù)對漢字圖像迭代處理，耗時較長。Pavlidis算法通過并行和串行混合的方式提取骨架，但骨架存在較多冗余像素，難于排除撇、捺以及T行交叉點的畸變并易出現(xiàn)斷點的現(xiàn)象?；谒饕淼募?xì)化算法根據(jù)預(yù)定的規(guī)則建立索引表，按照行列順序比較的形式提取骨架，細(xì)化速度非常快，但細(xì)化受限于索引表，骨架存在較多毛刺，筆畫交叉處和拐角處有畸變?；赩oronoi圖細(xì)化算法需將圖像擬合成多邊形，利用多邊形的邊界特征獲取Voronoi圖進(jìn)而提取骨架，但對于二值圖像，邊界擬合、直線求交比較復(fù)雜且計算量較大。基于輪廓篩減的細(xì)化算法需預(yù)先檢測圖像輪廓，再對輪廓范圍內(nèi)的圖像提取骨架，對圖像噪聲較為敏感，不適用于復(fù)雜圖像的處理。Zhang-Suen細(xì)化算法通過邏輯運算的方式循環(huán)刪除圖像中的非骨架像素點提取骨架，具有迭代少、速度快，保證提取出的漢字骨架中直線、T行交叉和拐角與原圖像一致的特點[11]，但存在骨架毛刺，骨架斜線區(qū)域易出現(xiàn)像素冗余。

本文針對Zhang-Suen細(xì)化算法提取手寫體漢字圖像骨架時出現(xiàn)的問題做出改進(jìn)。引入消除模板消除骨架冗余像素；引入保留模板避免因過度消除冗余像素造成的骨架斷裂；根據(jù)毛刺的特點引進(jìn)門限長度機(jī)制[11]消除多余的毛刺。改進(jìn)后算法所提取的漢字骨架較平滑，無毛刺和冗余像素，能夠完整、正確地突出手寫體漢字的特征。

1 算法研究

手寫體漢字識別中，漢字的結(jié)構(gòu)信息集中體現(xiàn)在漢字骨架中，對手寫體漢字細(xì)化，有利于突出字體形態(tài)特征，減少漢字圖像的數(shù)據(jù)存儲空間，進(jìn)而提高識別效率。細(xì)化算法對文字細(xì)化效果的優(yōu)劣直接影響字體識別的準(zhǔn)確率。細(xì)化算法一般需滿足以下要求[12-13]：

1) 連續(xù)性：保持原有筆畫的連續(xù)性，不能出現(xiàn)筆畫斷裂的現(xiàn)象。

2) 中軸性：骨架應(yīng)盡量是原手寫字體筆畫的中心線。

3) 拓?fù)湫裕阂３衷謱懽煮w的特征結(jié)構(gòu)，即細(xì)節(jié)特征、曲線端點等。

4) 保持性：保持筆畫交叉點特征，避免畸變。

5) 細(xì)化性：字體骨架應(yīng)細(xì)化為寬度為1 bit的單線，即單像素寬。

6) 快速性：算法簡單，執(zhí)行速度快。

細(xì)化算法根據(jù)是否使用了迭代計算，分為迭代細(xì)化算法和非迭代細(xì)化算法[14]。非迭代細(xì)化算法不以像素為基礎(chǔ)，通過一次遍歷的形式生成中值或中心線，進(jìn)而一次性抽取骨架，這種算法處理速度快但容易產(chǎn)生噪聲塊。迭代細(xì)化算法則是通過固定順序反復(fù)檢測并刪除圖像中符合條件的像素，直至得到1 bit寬的圖像骨架。根據(jù)像素檢測所使用的不同方法，迭代算法又可分為串行細(xì)化算法和并行細(xì)化算法。串行細(xì)化算法在第n次迭代的過程中是否刪除目標(biāo)像素點與前n-1次迭代結(jié)果和第n次所檢測的像素情況相關(guān)；并行細(xì)化算法在第n次迭代的過程中是否刪除目標(biāo)像素點只與n-1次迭代結(jié)果相關(guān)。

串行算法對手寫體漢字圖像的細(xì)化結(jié)果依賴于對像素處理的先后順序，像素點的消除或保留不可預(yù)測，并行算法細(xì)化時利用相同的預(yù)定條件檢測圖像中的全部像素點，其細(xì)化結(jié)果具有各向同性，且并行細(xì)化算法具有快速而準(zhǔn)確的特性，一直是人們研究的熱點[15]。

2 算法思想

2.1 基本概念

設(shè)G為二值圖像，P0是圖像G中任意一個值為1目標(biāo)像素點。

定義18-鄰域：與P0相鄰的八個鄰域所組成的像素點集合S={P1,P2,P3,P4,P5,P6,P7,P8}稱為像素點P0的8-鄰域，如圖1所示。

圖1 目標(biāo)像素點的8-鄰域

圖2 目標(biāo)像素點的16-環(huán)域

定義3前景點和背景點：二值圖像中值為1的像素點為前景點，值為0的像素點為背景點。

定義4P0的連接數(shù)：與P0相鄰的8-鄰域中前景像素點的個數(shù)記為N(P0)，與P0相鄰的16-環(huán)域中前景像素點的個數(shù)記為M(P0)。

(1)

(2)

定義5P0的交叉數(shù)：在與P0相鄰的8-鄰域中以順時針為序轉(zhuǎn)一圈，像素點從背景點變化到前景點的總次數(shù)和，記為：

(3)

定義6端點end[16]：若P0的8-鄰域內(nèi)只有一個骨架點像素并且P0本身就是骨架點，稱P0為端點。記為:

(4)

式中：count為當(dāng)前像素點P0的8-鄰域內(nèi)骨架點總數(shù)。

定義7節(jié)點node[16]：若P0的8-鄰域內(nèi)存在兩個或更多骨架點像素，稱P0為節(jié)點。記為：

(5)

式中：count為當(dāng)前像素點P0的8-鄰域內(nèi)骨架點總數(shù)。

定義8生長點grow[17]：若P0的8-鄰域內(nèi)存在三個或更多骨架點像素，并為毛刺起點，稱P0為生長點，其屬于節(jié)點的一種。記為：

(6)

式中：change為當(dāng)前像素點P0的8-鄰域內(nèi)由骨架點到背景點的變化次數(shù)。

定義9步長：以像素為單位，單一像素寬度骨架分支所具有的所有像素點個數(shù)。

定義10毛刺：骨架由于噪聲的影響出現(xiàn)不能反映目標(biāo)結(jié)構(gòu)信息的分支。結(jié)合細(xì)化的迭代次數(shù)得出對于毛刺的判定閾值[18]為：

(7)

式中：L是毛刺長度；ceil表示取大于等于括號內(nèi)的最小整數(shù)；times為圖像細(xì)化迭代的次數(shù)。

2.2 算法定義

Zhang-Suen算法是典型的迭代、并行細(xì)化算法，細(xì)化對象是二值圖像，具有速度快，能精確的保持原圖像直線、T型交叉和拐角的特點。Zhang-Suen算法根據(jù)8-鄰域的情況重復(fù)執(zhí)行邏輯運算，當(dāng)符合非骨架點的刪除條件時，對像素進(jìn)行標(biāo)記，在遍歷完全部圖像點陣之后再統(tǒng)一執(zhí)行刪除操作。算法分為兩個子過程，細(xì)化過程如下：

子過程1若同時滿足以下4個條件，則標(biāo)記P0為可刪除的點。

1) 2≤N(P0)≤6

2)N(P0)=1

3)P1×P3×P5=0

4)P3×P5×P7=0

條件1判斷P0是否為端點，如果P0僅有一個鄰點，則為端點，不能被標(biāo)記；如果P0有七個鄰點，為保證骨架的連通性，不能被標(biāo)記。條件2檢測P0的8-鄰域是否有0到1之間的變化，以保證骨架像素點不被標(biāo)記。條件3標(biāo)記8-鄰域東南邊的非骨架像素點。條件4標(biāo)記8-鄰域西北角的非骨架像素點。

子過程2若同時滿足以下四個條件，則標(biāo)記P0為可刪除的點。

1) 2≤N(P0)≤6

2)N(P0)=1

3)P1×P5×P7=0

4)P1×P3×P7=0

條件1、條件2同子過程1。條件3標(biāo)記8-鄰域西北邊的非骨架像素點。條件4標(biāo)記8-鄰域東南角的非骨架像素點。

算法重復(fù)迭代上述兩個子過程，對手寫體漢字圖像中的非骨架像素點進(jìn)行標(biāo)記。在迭代過程中檢測是否有被標(biāo)記的點，若有則繼續(xù)重復(fù)進(jìn)行迭代過程；反之則刪除所有被標(biāo)記的點，細(xì)化算法結(jié)束。此時剩下的點所構(gòu)成的區(qū)域即為骨架。

2.3 改進(jìn)算法

Zhang-Suen算法對手寫體漢字圖像進(jìn)行細(xì)化，發(fā)現(xiàn)細(xì)化所提取的文字骨架普遍存在冗余像素以及骨架毛刺的現(xiàn)象。本文在分析手寫漢字結(jié)構(gòu)特點的基礎(chǔ)上，發(fā)現(xiàn)細(xì)化不完全的冗余像素常見于手寫體漢字骨架的斜線區(qū)域，如圖3所示。由于漢字書寫的隨意性較大，書寫時所用紙張的不同，在手寫體漢字骨架的筆畫邊界處易產(chǎn)生骨架毛刺，如圖4所示。為保證細(xì)化后手寫體漢字骨架的細(xì)化性和拓?fù)湫?，需要對Zhang-Suen算法的結(jié)構(gòu)元素做消除骨架冗余像素和骨架毛刺的改進(jìn)。

(a) 像素冗余圖 (b) 部分斜線區(qū)域放大圖圖3 斜線區(qū)域冗余像素圖

(a) 像素毛刺圖 (b) 部分邊界區(qū)域放大圖圖4 邊界處骨架毛刺圖

2.3.1消除冗余像素

分析Zhang-Suen細(xì)化算法的原理，發(fā)現(xiàn)造成手寫體漢字骨架非單一像素寬的主要原因為圖像中部分像素點不滿足N(P0)=1而未被標(biāo)記刪除。為了消除圖像冗余，保證文字骨架的細(xì)化性，本文提出消除模板，如圖5所示。消除模板可以較好地刪除手寫體漢字骨架斜線區(qū)域的非骨架像素點。

圖5 消除模板

圖5消除模板中P0滿足的5個條件為：

a1 (P1×P7=1)&&(P3+P4+P5+P8=0)

a2 (P5×P7=1)&&(P1+P2+P3+P6=0)

a3 (P1×P3=1)&&(P2+P5+P6+P7=0)

a4 (P3×P5=1)&&(P1+P4+P7+P8=0)

a5P2+P4+P6+P8=0&&P1+P3+P5+P7=3

消除條件a1-a4主要用于消除圖3所示的斜線冗余像素。當(dāng)N(P0)=3時，P0點可能是分叉點，也可能是邊界點。由于分叉點同樣會出現(xiàn)冗余像素，如圖6所示，故引入消除條件a5用于分叉點冗余像素的刪除，如圖7所示。

圖6 分叉點細(xì)化不徹底

圖7 分叉點徹底細(xì)化后

圖8 保留模板

圖8保留模板中P0滿足的4個條件為：

b1P1×P3×P4+P6=1

b2P2×P3×P5+P8=1

b3P4×P5×P7+P2=1

b4P1×P2×P7+P4=1

2.3.2消除骨架毛刺

由于手寫字體結(jié)構(gòu)的復(fù)雜性和書寫的隨意性較大，經(jīng)過細(xì)化后的手寫體漢字骨架仍存在少量毛刺，毛刺破壞了漢字骨架的拓?fù)湫裕焕谕怀鍪謱戵w漢字的形狀特征。

毛刺長度一般難以歸納，但相對于骨架中心來說，骨架的長度一般遠(yuǎn)大于毛刺長度[19]，所以利用這一個特性，設(shè)定一個門限值L，選取最小步長分支進(jìn)行毛刺的判定與消除。

c1N(P0)≥2‖M(P0)≥2

c2S(P0)=3&&M(P0)≥3&&N(P0)≥3

具體步驟如下：

步驟1遍歷細(xì)化后的單像素寬度手寫體漢字骨架，若當(dāng)前骨架像素點P0符合條件c1或c2時，該點可能為節(jié)點node或生長點grow。

步驟2檢測該像素點P0是否為毛刺的起始位置，以端點end為起點對分支進(jìn)行掃描，記端點到該點的長度值為步長K。

步驟3取最小步長與閾值L進(jìn)行比較，若該分支的步長K小于閾值L，則標(biāo)記該分支，并計算分支所在節(jié)點node或生長點grow的總分支數(shù)，若總分支數(shù)大于2，則該分支判定為毛刺，刪除該分支。

步驟4若該節(jié)點node或生長點grow刪除分支后的余留分支數(shù)等于2，則通過P0的8-鄰域像素分析刪除該點是否會導(dǎo)致骨架斷點，影響骨架連通性。若沒有出現(xiàn)斷點，則保留該點；若出現(xiàn)斷點，則刪除該點。

步驟5重復(fù)執(zhí)行步驟3直至手寫體骨架像素遍歷完畢。

3 預(yù)處理

手寫字體漢字與印刷體漢字有所不同，不同類型的書寫工具、不同紙張以及書寫時所用的不同力度等情況導(dǎo)致手寫體漢字圖像難以細(xì)化。

分析Zhang-Suen算法原理發(fā)現(xiàn)，手寫體漢字圖像中由書寫不當(dāng)所造成的凹凸點和孤立點會對骨架的提取結(jié)果造成較大的影響。為了能更好地抽取出圖像中的手寫漢字骨架，減少干擾因素對細(xì)化時可能產(chǎn)生的影響，有必要在手寫體漢字圖像細(xì)化之前對圖像做預(yù)處理[20]。本文設(shè)置了數(shù)個模板對手寫體漢字圖像進(jìn)行預(yù)優(yōu)化，在細(xì)化算法開始執(zhí)行之前，調(diào)用模板對手寫體漢字圖像進(jìn)行預(yù)處理操作。首先調(diào)用圖9的凹凸點和孤立點消除模板消除圖像凹凸點和孤立點。如果前景點P0的8-鄰域滿足圖9的四個模板，則將前景點P0更改為背景點。其次調(diào)用圖10的四個模板消除文字圖像中可能出現(xiàn)的孔洞，若前景點P0的8-鄰域滿足圖10的四個模板，則將P0的8-鄰域全部像素點更改為前景點像素。

圖9 凹凸點和孤立點消除模板

圖10 孔洞消除模板

圖11與圖12中對比了未經(jīng)模板處理和經(jīng)模板處理過的二值手寫體漢字圖像，圖像中矩形區(qū)域標(biāo)注了改進(jìn)的地方。實驗證明：經(jīng)過預(yù)處理后的手寫體漢字圖像填補(bǔ)了手寫體漢字圖像原有的孔洞，孤立的噪聲塊消失，字體邊緣的凹凸點變得光滑。

(a) 預(yù)處理前二值圖像 (b) 局部放大圖11 預(yù)處理前的文字圖像效果

(a) 預(yù)處理后二值圖像 (b) 局部放大圖12 預(yù)處理后的文字圖像效果

4 算法步驟

步驟11) 對圖像按照按從上到下、從左到右的順序遍歷，尋找前景點P0； 2) 若前景點P0滿足Zhang-Suen算法設(shè)定的迭代條件，則標(biāo)記P0為可刪除的點；3) 在遍歷完手寫體漢字圖像后，刪除所有被標(biāo)記的點，得到初步細(xì)化的手寫體漢字骨架。

步驟21) 對細(xì)化后提取的手寫體漢字骨架進(jìn)行遍歷，尋找前景點P0； 2) 若前景點P0滿足刪除模板a1-a5，則標(biāo)記該點為可刪除的點，再檢測該像素點是否符合保留模板條件，若符合則去除標(biāo)記為可刪除的點，否則繼續(xù)遍歷； 3) 在遍歷完手寫體漢字圖像后，刪除所有被標(biāo)記的點，得到像素為1 bit寬的手寫體漢字骨架。

步驟31) 遍歷單一像素寬度的手寫體漢字骨架，尋找前景點P0； 2) 若前景點P0為節(jié)點node或生長點grow，則循環(huán)計算細(xì)化后骨架各個分支步長，取其中小步長與閾值進(jìn)行比較，刪除符合條件的分支毛刺，得到無毛刺的手寫體漢字骨架。

算法工作流程如圖13所示。

圖13 本文算法工作流程圖

5 實 驗

為驗證改進(jìn)算法的細(xì)化效果，實驗選取了860幅不同的手寫體漢字圖進(jìn)行細(xì)化處理。在運行改進(jìn)算法的同時，使用Hilditch細(xì)化算法、Pavlidis細(xì)化算法、基于索引表的細(xì)化算法、Zhang-Suen細(xì)化算法以及改進(jìn)算法對其中20幅不同手寫體漢字圖像進(jìn)行細(xì)化對比實驗。在Windows 7操作系統(tǒng)的PC機(jī)上，硬件配置為Inter(R) Core(TM) i7-6700 CPU 3.4 GHz，8 GB RAM，使用Visual Studio 2015開發(fā)環(huán)境并使用OpenCV 3.4.1計算機(jī)視覺庫對手寫體漢字圖像進(jìn)行實驗，圖14-圖20為部分圖像細(xì)化效果。

圖14 手寫體漢字二值圖像

圖15 Hilditch細(xì)化算法

圖16 Pavlidis細(xì)化算法

圖17 基于索引表的細(xì)化算法

圖18 Zhang-Suen細(xì)化算法

圖19 改進(jìn)算法

圖20 改進(jìn)算法局部放大

通過對比各個細(xì)化算法對手寫體漢字的骨架提取效果得出：改進(jìn)算法所提取出的骨架能夠保持漢字形狀特征，骨架像素寬度為1 bit，且不存在毛刺。

在相同配置環(huán)境下采用本文算法與其他細(xì)化算法對隨機(jī)選取的20幅手寫字體圖像進(jìn)行細(xì)化處理，并以實驗中的平均結(jié)果為例進(jìn)行分析。實驗結(jié)果如表1所示。

表1 細(xì)化算法結(jié)果比較

可以看出：五個算法中索引表細(xì)化算法細(xì)化速度最快，但對手寫體漢字骨架的處理效果最差，不能準(zhǔn)確表示手寫體漢字的結(jié)構(gòu)特征。Zhang-Suen細(xì)化算法速度次之，細(xì)化結(jié)果上有了很大改善，但提取出的漢字骨架存在毛刺，并且不能保證斜線區(qū)域的像素寬度為1 bit。本文改進(jìn)算法的速度和Zhang-Suen細(xì)化算法接近，但去除了骨架毛刺和像素冗余，能夠準(zhǔn)確、完整地提取手寫體漢字骨架。

6 結(jié) 語

Zhang-Suen算法是一種較實用且細(xì)化速度相對較快的細(xì)化算法，但是對手寫體漢字細(xì)化時，易出現(xiàn)斜線區(qū)域像素細(xì)化不完全以及漢字骨架“毛刺”的問題。本文對Zhang-Suen快速并行細(xì)化算法作了改進(jìn)，引進(jìn)了消除和保留模板，在保證手寫漢字骨架的連續(xù)性、拓?fù)湫缘幕A(chǔ)上，實現(xiàn)了對手寫字體的完全細(xì)化，并且通過門限機(jī)制去除了骨架毛刺。細(xì)化結(jié)果完整保留和突出手寫體漢字的特征信息，對手寫體漢字的識別有著重要作用。