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

(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048)

?

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

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

(西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048)

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

圖像形態(tài)學(xué)；書(shū)法；骨架提??；分叉點(diǎn)檢測(cè)；分叉點(diǎn)合并

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

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

1　A-W細(xì)化算法

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

1)若八鄰域全為0，中心像素點(diǎn)則為孤立點(diǎn)，該點(diǎn)不應(yīng)該被刪除，否則會(huì)刪除整個(gè)符號(hào)。

2)若八鄰域全為1，則中心像素點(diǎn)不屬于邊界，因此不應(yīng)刪除。

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

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

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

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

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

2.1單像素化處理

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

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

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

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

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

圖2　中心像素點(diǎn)不應(yīng)該被刪除的反例Fig.2　Counter example for the fact that center points should not be deleted

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

2.2分叉點(diǎn)合并

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

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

2.2.1特征點(diǎn)檢測(cè)

2.2.2最大圓算法描述

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

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

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

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

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

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

圖5　分叉點(diǎn)合并Fig.5　Fork points merging

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

3　實(shí)驗(yàn)及比較

本文總共進(jìn)行了3部分實(shí)驗(yàn)，分別為書(shū)法字的各算法細(xì)化結(jié)果比較、若干標(biāo)準(zhǔn)字庫(kù)上的結(jié)果比較以及算法性能分析實(shí)驗(yàn)?，F(xiàn)分別描述如下。

實(shí)驗(yàn)1書(shū)法字體的各算法細(xì)化結(jié)果比較實(shí)驗(yàn)

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

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

實(shí)驗(yàn)2若干標(biāo)準(zhǔn)字庫(kù)上的細(xì)化結(jié)果比較實(shí)驗(yàn)

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

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

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

實(shí)驗(yàn)3算法的性能比較實(shí)驗(yàn)

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

表1　幾種細(xì)化算法性能比較

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

4　結(jié)　語(yǔ)

本文研究書(shū)法字的骨架提取算法，針對(duì)常見(jiàn)算法出現(xiàn)的鋸齒、非單像素、分叉點(diǎn)畸變和毛刺等問(wèn)題，主要從單像素化和分叉點(diǎn)檢測(cè)及合并兩個(gè)方面進(jìn)行了改進(jìn)。所引入的單像素化是在保證圖像連通的條件下進(jìn)行的，不會(huì)出現(xiàn)骨架斷裂現(xiàn)象。接著應(yīng)用最大圓方法進(jìn)行分叉點(diǎn)合并。實(shí)驗(yàn)結(jié)果表明，本文取得的骨架無(wú)毛刺和分叉點(diǎn)，優(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]劉峽壁,賈云得.一種字符圖像線段提取及細(xì)化算法[J].中國(guó)圖象圖形學(xué)報(bào),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]劉宏申.擊中擊不中變換在筆畫(huà)細(xì)化中的應(yīng)用[J].安徽工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),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]俞凱,吳江琴,莊越挺.基于骨架相似性的書(shū)法字檢索[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),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]鄧茜蕓,周明全,武仲科,等.面向瓦當(dāng)文字識(shí)別的改進(jìn)水平集骨架提取[J].中國(guó)圖象圖形學(xué)報(bào),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.

(責(zé)任編輯楊小麗)

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401355)；陜西省教育廳專(zhuān)項(xiàng)科研計(jì)劃資助項(xiàng)目(2013JK1135)；西安市碑林區(qū)科技計(jì)劃資助項(xiàng)目(GX1410)

張九龍，男，副教授，博士，研究方向?yàn)閳D像處理與模式識(shí)別。E-mail:zhangjiulong@xaut.edu.cn

TP391.4

A

1006-4710(2016)01-0035-04