張九龍,王夏妮,張鎮(zhèn)東,郭璐銘

(西安理工大學 計算機科學與工程學院，陜西 西安 710048)

?

一種書法字骨架提取優(yōu)化方法

張九龍,王夏妮,張鎮(zhèn)東,郭璐銘

(西安理工大學 計算機科學與工程學院，陜西 西安 710048)

書法字的骨架提取即細化是書法風格研究的重要先決步驟。針對常見細化算法結(jié)果中產(chǎn)生的鋸齒、非單像素、分叉點畸變和毛刺等問題進行改進。引入一種旋轉(zhuǎn)不變性的細化算法得到漢字的中軸線。接著分以下兩步進行優(yōu)化：首先在保證圖像連通的條件下進行單像素化處理；其次引入最大圓方法進行分叉點合并。實驗結(jié)果表明，兩步法得到的細化結(jié)果是單像素且無毛刺和分叉點的，為后續(xù)筆畫提取和書法風格研究奠定良好的基礎(chǔ)。

圖像形態(tài)學；書法；骨架提??；分叉點檢測；分叉點合并

細化的常見方法有距離變換和輪廓點刪除兩大類。距離變換類的方法對輪廓的細微變化不具有魯棒性，故本文主要研究輪廓點刪除算法。Suen[1]提出了一種經(jīng)典的快速并行細化算法，每次迭代主要去除圖像的邊界點并保留骨架的關(guān)鍵點，在保持筆畫骨架連通性的同時提高了細化的速度和效率，但效果較為粗糙。Gonzalez將骨架定義為目標輪廓點中最大內(nèi)切圓的圓心的集合[2]，但會出現(xiàn)較多骨架斷裂。S.Huang[3]運用Bernstein-Bezier曲線對細化結(jié)果進行擬合來改善分叉點偏移的現(xiàn)象,賈云德在字符圖像線段提取及細化過程[4]中應用了此方法。劉宏申[5]采用形態(tài)學方法中的擊中擊不中方法進行筆畫細化，但其中如何選取結(jié)構(gòu)對元素對細化結(jié)有很大影響。在書法文化計算及應用方面，相關(guān)的部分文獻有吳江琴的書法字檢索[6]和鄧茜蕓的瓦當文字識別[7]等研究。

在擊中擊不中運算中，通常設置模板從四個或八個方向剝離像素。這類算法應用于書法漢字細化的缺陷是有些方向上的筆劃效果不佳，因為漢字筆劃并非只有水平、垂直和對角線方向。本文采用Ahmed提出的旋轉(zhuǎn)不變性細化算法[8]，即A-W方法。該方法能得到字符的中軸線并較好地保持原字符的形狀特征。但該方法的骨架可能存在非單像素寬度，故引入Rockett的單像素化算法[9]進行改進。雖然改進后骨架為單像素的，但分叉現(xiàn)象仍然存在。具體表現(xiàn)為一個四分叉點會畸變?yōu)閮蓚€三分叉點等現(xiàn)象。采用分叉點及特征點判斷算法[10]，確定所有的分叉點和端點。最大圓方法[3]是進行分叉點合并有效的一個方法，本文在確定分叉點后引入該方法合并分叉點，取得了優(yōu)于上述單個方法的細化結(jié)果。

1　A-W細化算法

A-W細化算法包括若干種細化模板，通過迭代匹配，當中心像素點與模板匹配時，則刪除該點，直到圖像不再變化為止。設待處理圖像為二值圖像，1為目標像素點，0為背景像素點。每次迭代的目標是刪除邊界像素點，但前提是不會破壞圖像的連通性。以目標像素點和它的八鄰域像素點組成3*3大小的目標窗口，判斷是否符合以下4種情況之一。

1)若八鄰域全為0，中心像素點則為孤立點，該點不應該被刪除，否則會刪除整個符號。

2)若八鄰域全為1，則中心像素點不屬于邊界，因此不應刪除。

3)若八鄰域的環(huán)狀結(jié)構(gòu)中有1到7個連續(xù)的0，那么就會有7到1個連續(xù)的1。這類分為3個子類：①八鄰域中僅包括1個1，7個0；②八鄰域中只包括2個連續(xù)的1，6個0；③八鄰域中包括至少3個連續(xù)的1，其它為0。

4)八鄰域中白色像素點不是以連續(xù)的形式出現(xiàn)，針對所出現(xiàn)的幾種情況均可做相應處理。

以上4種情況可以歸結(jié)為20種模板[8]，在每次迭代中，將考慮所有的像素點并且刪除和模板匹配區(qū)域的中心點。通過重復上述過程直到圖像不再變化為止，這樣就得到了骨架。

2　兩步法骨架優(yōu)化算法

采用A-W算法進行初步細化后，會存在一些缺陷。如在筆畫的撇和捺的部分存在非單像素寬的線，在筆畫交叉的地方存在多個分叉點，在筆畫端點處出現(xiàn)毛刺，這些都導致骨架失去了原先筆畫的特性。

2.1單像素化處理

首先，檢測兩個像素寬的地方，即水平方向上兩像素寬[0 1 1 0]和垂直方向上兩像素寬[0 1 1 0]T，并利用骨架的連通性進行單像素處理。算法的基本思想是為每個中心像素點和它的八鄰域構(gòu)造一個無向連通圖，若刪除中心像素點不會造成不連通，則刪除，否則不應該刪除。

圖1為處理前的兩像素寬的情況。其中，(a)為某次細化后的初步結(jié)果，中間的兩個像素點1組成了水平方向上雙像素寬的線；(b)為構(gòu)造的無向連通圖，可見若刪除x0不會影響圖的連通性，所以可以將其刪除；(c)為無向連通圖對應的鄰接矩陣。

圖2列舉另一種中心點不應被刪除的情況。(a)為初步細化的結(jié)果；(b)為構(gòu)造的無向連通圖，若刪除x0，則會導致圖不連通，所以這種情況下不應該刪除。

為每個符合兩像素寬的像素點及其八鄰域構(gòu)造鄰接矩陣，更方便進行判斷是否應該刪除中心像素點。圖3為單像素化處理前后的局部放大圖。

圖1　細化后局部像素情況Fig.1　Local pixels after thinning

圖2　中心像素點不應該被刪除的反例Fig.2　Counter example for the fact that center points should not be deleted

圖3　單像素化處理結(jié)果對照Fig.3　Result with reduced single pixel in width

2.2分叉點合并

單像素化處理之后，還沒有解決分叉點畸變的缺陷。例如圖4所示，原來的一個4分叉點被轉(zhuǎn)為兩個3分叉點，并且在筆畫端點處有毛刺。在此首先檢測分叉點和端點等特征點，然后引入最大圓方法進行分叉點合并和毛刺去除。

圖4　一個4分叉點轉(zhuǎn)化為兩個3分叉點Fig.4　Two 3-fork points split by a 4-fork point

2.2.1特征點檢測

2.2.2最大圓算法描述

最大圓算法是以原始筆畫內(nèi)的最大內(nèi)切圓為范圍，將圓內(nèi)距離近的分叉點聚類為一個點，從而將多個分叉點合并為最終的特征點。下面給出該算法的描述：

1)以特征點為圓心，初始半徑R=0；

2)圓心不變，半徑值R=R+1，畫圓；

3)判斷圓內(nèi)像素點是否都在筆畫范圍內(nèi)，由于筆畫中的像素點值為1，所以只需檢測圓內(nèi)所有像素點的值是否全部為1，“是”則執(zhí)行第二步，“否”則認為已經(jīng)超出筆畫范圍，取R=R-1為最大圓半徑；

4)進行特征點聚類合并。計算每一對特征點之間的距離，對每一對特征點f1、f2，若Distance(f1,f2)≤R1+R2，則這兩個點聚為一類。隨后以每一類的聚類中心點來代替這類中所有的點。

最大圓方法的結(jié)果如圖5所示。分叉點處細化的放大如圖6所示，可以看出交叉點處的細化結(jié)果有了很大改善。

圖5　分叉點合并Fig.5　Fork points merging

圖6　交叉點處細化結(jié)果放大圖對比Fig.6　Amplified result of thinning at fork point

3　實驗及比較

本文總共進行了3部分實驗，分別為書法字的各算法細化結(jié)果比較、若干標準字庫上的結(jié)果比較以及算法性能分析實驗?，F(xiàn)分別描述如下。

實驗1書法字體的各算法細化結(jié)果比較實驗

以《多寶塔碑》中的佛字為例進行實驗，該字縱橫及交叉筆劃具有一定的代表性。將本文方法與Z-S方法、最大內(nèi)切圓方法、擊中擊不中方法、A-W方法進行對比，細化結(jié)果如圖7所示?？梢钥闯霰疚乃惴ㄈコ嗣獭⒎植娴热毕荩瑑?yōu)于其他算法。

圖7　幾種骨架提取算法結(jié)果的比較Fig.7　Comparison of skeleton extraction of several algorithms

實驗2若干標準字庫上的細化結(jié)果比較實驗

為了驗證算法的結(jié)果，在楷體、宋體、黑體、隸書等標準字庫上運行了實驗。每種字庫均采用96*96的模板，各字體抽取1 000個漢字進行細化。部分細化對照結(jié)果見圖8所示。圖中每一個字的三種細化效果從左至右依次為Z-S方法、A-W方法及本文方法。

圖8　Z-S方法、A-W方法及本文方法的效果Fig.8　Thinning results of the use of Z-S, A-W and our method

可以看出，在常見三種字體上，本文方法均取得了優(yōu)于Z-S方法和A-W方法的效果。

實驗3算法的性能比較實驗

骨架像素點的個數(shù)和端點個數(shù)也是用來衡量細化算法優(yōu)劣的一種指標。很多細化算法都會產(chǎn)生非單像素寬的線和毛刺，多種細化算法得到的骨架像素的個數(shù)和端點個數(shù)可以用來表征算法性能。仍以實驗1中的佛字為例，所得結(jié)果見表1。

表1　幾種細化算法性能比較

從表1可以看出，本文方法雖然骨架像素個數(shù)多于Z-S方法、最大內(nèi)切圓方法，但主要是因為這兩種方法存在斷裂和不連通。本文方法的骨架像素數(shù)少于擊中擊不中方法、A-W方法，因為這兩種方法存在非單像素寬的線條且存在毛刺。本文端點個數(shù)最少證明連通性好以及毛刺少。這說明骨架多處斷裂、連通性差會導致骨架像素個數(shù)過少及端點個數(shù)多，而非單像素寬的線過多將導致骨架像素個數(shù)多。

4　結(jié)　語

本文研究書法字的骨架提取算法，針對常見算法出現(xiàn)的鋸齒、非單像素、分叉點畸變和毛刺等問題，主要從單像素化和分叉點檢測及合并兩個方面進行了改進。所引入的單像素化是在保證圖像連通的條件下進行的，不會出現(xiàn)骨架斷裂現(xiàn)象。接著應用最大圓方法進行分叉點合并。實驗結(jié)果表明，本文取得的骨架無毛刺和分叉點，優(yōu)于其它算法。

[1]ZHANG T Y，SUEN C Y.A fast parallel algorithm for thinning digital patterns[J].Communications of ACM,1984,27(3):236-239.

[2]GONZALEZ R C,WOODS R E.Digital image processing[M].2nd ed.Lebanon:Prentice Hall,2002:420-453.

[3]LIAO C W，HUANG J S.Stroke segmentation by Bernstein-Bezier curve fitting[J].Pattern Recognition,1990,23(5):475-484.

[4]劉峽壁,賈云得.一種字符圖像線段提取及細化算法[J].中國圖象圖形學報,2005,10(1):48-53.

LIU Xiabi,JIA Yunde.A character image line-segment extraction and thinning algorithm[J].Journal of Image and Graphics,2005,10(1):48-53.

[5]劉宏申.擊中擊不中變換在筆畫細化中的應用[J].安徽工業(yè)大學學報(自然科學版),2002,19(3):251-253.

LIU Hongshen.Application of hit-miss transformation in thinning chokes of character[J].Journal of Anhui University of Technology,2002,19(3):251-253.

[6]俞凱,吳江琴,莊越挺.基于骨架相似性的書法字檢索[J].計算機輔助設計與圖形學學報,2009,21(6):746-751.

YU Kai,WU Jiangqin,ZHUANG Yueting.Calligraphy characters retrieval based on skeleton similarity[J].Journal of Computer-Aided Design & Computer Graphics,2009,21(6):746-751.

[7]鄧茜蕓,周明全,武仲科,等.面向瓦當文字識別的改進水平集骨架提取[J].中國圖象圖形學報,2014,19(9):1324-1331.

DENG Qianyun,ZHOU Mingquan,WU Zhongke,et al.Skeleton extraction using improved level set methods in eaves' text recognition[J].Journal of Image and Graphics,2014,19(9):1324-1331.

[8]AHMED M，WAED R.A rotation invariant rule-based thinning algorithm for character recognition[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2002,24(12):1672-1678.

[9]ROCKETT P I.An improved rotation-invariant thinning algorithm[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2005,27(10):1671-1674.

[10]LIU K,HUANG Y S,Suen C Y.Identification of fork points on the skeletons of handwritten Chinese characters[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,1999,21(10):1095-1100.

(責任編輯楊小麗)

An optimization algorithm for Chinese characters skeleton extraction

ZHANG Jiulong,WANG Xiani,ZHANG Zhendong，GUO Luming

(School of Computer Science and Engineering,Xi’an University of Technology Xi’an 710048,China)

Character skeleton extraction is one of the important preprocessing steps for the calligraphy style evaluation.Traditional thinning algorithms have the drawbacks of zigzag,nonsingle pixel,fork point distortion,spurious branches,etc.This study aims at solving these problems.Based on a rotation invariant algorithm the provisional skeleton is obtained,with two steps taken to optimize the result.First,with the guarantee of the connectedness of skeleton,we perform a process by which to reduce the skeleton to single pixel in width.Second,we employ the maximum circle method to merge the fork points.The experimental results show that the two-step optimization can obtain a better skeleton compared with some common methods.

image morphology; Chinese calligraphy; skeleton extraction; fork point detection; fork point merging

10.19322/j.cnki.issn.1006-4710.2016.01.007

2015-11-25

國家自然科學基金資助項目(61401355)；陜西省教育廳專項科研計劃資助項目(2013JK1135)；西安市碑林區(qū)科技計劃資助項目(GX1410)

張九龍，男，副教授，博士，研究方向為圖像處理與模式識別。E-mail:zhangjiulong@xaut.edu.cn

TP391.4

A

1006-4710(2016)01-0035-04