基于改進ZS細化算法的手寫體漢字骨架提取

常慶賀 吳敏華 駱力明

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

0 引 言

手寫體漢字識別是模式識別的重要分支，也是文字識別領域最為困難的問題之一。細化是手寫體漢字識別與處理中的一個重要環節，其又可稱為骨架化，一般是指在保持圖像原像素拓撲鏈接關系的前提下，接連刪除圖像邊緣像素直至達到單個像素寬度骨架的過程。圖像細化所提取出的骨架不僅是目標圖像重要的拓撲描述，還減少了圖像中的冗余信息，在圖像分析、信息壓縮、特征提取、模式識別等領域具有非常廣泛的應用[1-2]。

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

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

1 算法研究

手寫體漢字識別中，漢字的結構信息集中體現在漢字骨架中，對手寫體漢字細化，有利于突出字體形態特征，減少漢字圖像的數據存儲空間，進而提高識別效率。細化算法對文字細化效果的優劣直接影響字體識別的準確率。細化算法一般需滿足以下要求[12-13]：

1) 連續性：保持原有筆畫的連續性，不能出現筆畫斷裂的現象。

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

3) 拓撲性：要保持原手寫字體的特征結構，即細節特征、曲線端點等。

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

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

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

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

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

2 算法思想

2.1 基本概念

設G為二值圖像，P0是圖像G中任意一個值為1目標像素點。

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

圖1 目標像素點的8-鄰域

圖2 目標像素點的16-環域

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

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

(1)

(2)

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

(3)

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

(4)

式中：count為當前像素點P0的8-鄰域內骨架點總數。

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

(5)

式中：count為當前像素點P0的8-鄰域內骨架點總數。

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

(6)

式中：change為當前像素點P0的8-鄰域內由骨架點到背景點的變化次數。

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

定義10毛刺：骨架由于噪聲的影響出現不能反映目標結構信息的分支。結合細化的迭代次數得出對于毛刺的判定閾值[18]為：

(7)

式中：L是毛刺長度；ceil表示取大于等于括號內的最小整數；times為圖像細化迭代的次數。

2.2 算法定義

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

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

1) 2≤N(P0)≤6

2)N(P0)=1

3)P1×P3×P5=0

4)P3×P5×P7=0

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

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

1) 2≤N(P0)≤6

2)N(P0)=1

3)P1×P5×P7=0

4)P1×P3×P7=0

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

算法重復迭代上述兩個子過程，對手寫體漢字圖像中的非骨架像素點進行標記。在迭代過程中檢測是否有被標記的點，若有則繼續重復進行迭代過程；反之則刪除所有被標記的點，細化算法結束。此時剩下的點所構成的區域即為骨架。

2.3 改進算法

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

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

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

2.3.1消除冗余像素

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

圖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所示的斜線冗余像素。當N(P0)=3時，P0點可能是分叉點，也可能是邊界點。由于分叉點同樣會出現冗余像素，如圖6所示，故引入消除條件a5用于分叉點冗余像素的刪除，如圖7所示。

圖6 分叉點細化不徹底

圖7 分叉點徹底細化后

圖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消除骨架毛刺

由于手寫字體結構的復雜性和書寫的隨意性較大，經過細化后的手寫體漢字骨架仍存在少量毛刺，毛刺破壞了漢字骨架的拓撲性，不利于突出手寫體漢字的形狀特征。

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

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

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

具體步驟如下：

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

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

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

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

步驟5重復執行步驟3直至手寫體骨架像素遍歷完畢。

3 預處理

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

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

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

圖10 孔洞消除模板

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

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

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

4 算法步驟

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

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

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

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

圖13 本文算法工作流程圖

5 實 驗

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

圖14 手寫體漢字二值圖像

圖15 Hilditch細化算法

圖16 Pavlidis細化算法

圖17 基于索引表的細化算法

圖18 Zhang-Suen細化算法

圖19 改進算法

圖20 改進算法局部放大

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

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

表1 細化算法結果比較

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

6 結 語

Zhang-Suen算法是一種較實用且細化速度相對較快的細化算法，但是對手寫體漢字細化時，易出現斜線區域像素細化不完全以及漢字骨架“毛刺”的問題。本文對Zhang-Suen快速并行細化算法作了改進，引進了消除和保留模板，在保證手寫漢字骨架的連續性、拓撲性的基礎上，實現了對手寫字體的完全細化，并且通過門限機制去除了骨架毛刺。細化結果完整保留和突出手寫體漢字的特征信息，對手寫體漢字的識別有著重要作用。