侯立斐，張 靜，霍玲玲

(遼寧師范大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧 大連 116081)

骨架是一種重要的圖像目標(biāo)幾何特征，利用骨架表示原始圖像，可以在保持圖像重要拓?fù)涮卣鞯那疤嵯?，減少圖像中的冗余信息。因此，骨架被廣泛應(yīng)用于圖像目標(biāo)的形狀分析、信息壓縮、特征提取、模式識(shí)別等領(lǐng)域。

自1967年Blum等[1]首先采用中軸表示連續(xù)平面上的圖形以來，人們已經(jīng)相繼提出了許多圖像骨架提取算法。呂岳等[2]提出了一種使用并行細(xì)化算法，該細(xì)化算法提取出的圖像骨架避免了過度腐蝕，雖然具有良好的連通性，但此方法獲得的骨架寬度往往大于一個(gè)像素。張若文等[3]提出了一種快速簡便的圖像骨架變換方法，該算法利用起飛、著陸法對(duì)圖像進(jìn)行距離變換，利用局部方向最大值搜索法進(jìn)行骨架提取，此方法既可操作于二維圖像，也可操作于三維圖像，但對(duì)于不同的圖像可能會(huì)得到相同的骨架結(jié)構(gòu)。楊義軍等[4]提出了復(fù)雜帶狀圖像的快速三角剖分與骨架化算法，但該算法不適合提取寬度變化不規(guī)則圖像的骨架。

本文基于李小軍[5]提出的TrueType字體中心骨架線提取算法研究，提出一種新的基于內(nèi)切圓的中心骨架線提取算法。該算法首先獲取字體的邊緣，將字體的邊緣像素點(diǎn)按順時(shí)針方向存儲(chǔ)于數(shù)組I_edge中，以任意一點(diǎn)為起點(diǎn)按特定步長取點(diǎn)，迭代計(jì)算每個(gè)步長范圍內(nèi)的內(nèi)切圓，最后將各內(nèi)切圓的圓心連接起來得到漢字的骨架。該算法不僅適用于TrueType字體，對(duì)其他的字體(如隸書、楷體、宋體、黑體等)同樣適用，而且提取的骨架具有良好的連通性和對(duì)稱性。

1 邊緣提取和邊緣點(diǎn)的選取

欲提取書法漢字的骨架，首先需要檢測(cè)書法漢字的邊緣，提取邊緣信息，然后迭代計(jì)算每個(gè)步長范圍內(nèi)的內(nèi)切圓。

1.1 邊緣提取

邊緣是在已有的書法漢字圖像中提取出來的。本文中用到的字體是Windows系統(tǒng)字體中的華文隸書、黑體、華文楷體和華文新魏等，如圖1所示。

圖1 Windows輸入的字體

有了字體圖像，首先標(biāo)記出圖像中的前景點(diǎn)、背景點(diǎn)和邊界。為了提取出漢字的邊緣，需先對(duì)漢字進(jìn)行邊緣檢測(cè)?，F(xiàn)有的邊緣檢測(cè)方法很多，如Roberts算子、Sobel算子、Laplacian算子、Canny算子、Prewitt算子等。本文的目的是為了得到漢字的邊界，待處理的字體圖像為灰度圖像，所以本文采用Canny算子[6]進(jìn)行邊緣檢測(cè)，具體步驟如下：

(1)用高斯濾波器對(duì)漢字圖像進(jìn)行平滑處理；

(2)用一階偏導(dǎo)的有限差分計(jì)算梯度的幅值和方向；

(3)保留局部梯度最大的點(diǎn)，抑制非極大值，確定邊緣；

(4)用雙閾值算法檢測(cè)和連接邊緣。

得到漢字的邊緣檢測(cè)結(jié)果如圖2所示，將所得的漢字邊緣存入數(shù)組I_edge中。

圖2 對(duì)原始字體進(jìn)行邊緣檢測(cè)的結(jié)果

1.2 邊緣點(diǎn)的選取

采用本文的算法提取漢字的骨架，提取出漢字的邊緣。首先按特定步長選取邊緣點(diǎn)，在存放邊緣的數(shù)組I_edge中，從任意一點(diǎn)開始，以n個(gè)點(diǎn)為一個(gè)步長取點(diǎn)(n為整數(shù)，n取的越小，所得的骨架越接近漢字的真實(shí)骨架，本文取n=10)，在曲率變化比較大的點(diǎn)處斷開，保留該點(diǎn)，然后從這一點(diǎn)開始繼續(xù)以10個(gè)點(diǎn)為一個(gè)步長取點(diǎn)，直到取完所有的點(diǎn)。

2 內(nèi)切圓的計(jì)算

圖3所示為與直線AB相切的內(nèi)切圓，假設(shè)從A點(diǎn)開始選取點(diǎn)，下一個(gè)滿足條件的點(diǎn)為B，曲線AB可以近似用直線AB表示，過直線AB做半徑為R0的圓與直線AB相切于直線AB的中點(diǎn)M，圓的圓心C在過直線AB的中點(diǎn)M的垂直線上，改變圓半徑R0的大小 (圓始終與直線AB相切于M點(diǎn)并且圓心在過M點(diǎn)的垂線上)并計(jì)算其他邊緣點(diǎn)到圓心C的距離，直到找到邊緣點(diǎn)到圓心C的距離無限接近R0的點(diǎn)，此時(shí)圓即為所求的此步長范圍內(nèi)的內(nèi)切圓。保存圓心C和半徑R0，繼續(xù)計(jì)算下一個(gè)步長范圍內(nèi)的內(nèi)切圓，依次找到所有步長范圍內(nèi)的內(nèi)切圓后，所有內(nèi)切圓的圓心所連成的直線即為漢字的骨架。

漢字骨架提取的主要實(shí)現(xiàn)步驟為：

圖3 與直線AB相切的內(nèi)切圓

(1)提取漢字的邊緣，并將邊緣點(diǎn)保存到數(shù)組I_edge中；

(2)在數(shù)組I_edge中，從任意一點(diǎn)開始以 10個(gè)點(diǎn)為一個(gè)步長取點(diǎn)；

(3)取前兩個(gè)點(diǎn) A和 B，連接 A、B兩點(diǎn)，在直線 AB上取中點(diǎn)M；

(4)求過直線AB中點(diǎn)M點(diǎn)的法線；

(5)做內(nèi)切圓，圓心在法線上并與直線AB相切于點(diǎn)M；

(6)使內(nèi)切圓的半徑為最小半徑 R0(設(shè) R0=0.5)；

(7)增大圓半徑R0(R0=2R0)，計(jì)算出圓半徑為 R0時(shí)的圓心C；

(8)計(jì)算書法漢字邊緣所有的點(diǎn)到圓心C的距離，如果距離小于圓半徑R0，則保存該點(diǎn)到一個(gè)列表內(nèi)；

(9)如果計(jì)算完所有的邊緣點(diǎn)后列表為空，返回步驟(7)重新執(zhí)行；

(10)如果列表不空，則令 R0=R0/2；

(11)微調(diào)R0(R0=R0+△r)的大小并計(jì)算圓半徑為 R0時(shí)的圓心C，計(jì)算列表內(nèi)所保存的每個(gè)點(diǎn)到圓心C的距離。重復(fù)步驟(11)反復(fù)調(diào)整圓半徑R0，直到找到邊緣點(diǎn)到圓心的距離無限接近圓半徑R0。此時(shí)圓即為所求的其所在步長范圍內(nèi)的內(nèi)切圓。

(12)保存所求的圓心和半徑，返回步驟(3)重新計(jì)算下一個(gè)步長范圍內(nèi)的內(nèi)切圓和半徑。

按照以上算法迭代計(jì)算完一個(gè)漢字的所有邊緣的內(nèi)切圓后，將所有內(nèi)切圓的圓心依次連接起來即得到漢字的骨架。

3 漢字模糊區(qū)域骨架點(diǎn)計(jì)算

所謂漢字的模糊區(qū)域是指漢字筆劃交叉或相連的地方。在模糊區(qū)域處用內(nèi)切圓的方法提取骨架會(huì)出現(xiàn)局部骨架偏離原始骨架的情況。圖4所示筆劃交叉的區(qū)域用基于內(nèi)切圓的方法可能會(huì)產(chǎn)生一些微小的偏離中心的骨架，所以模糊區(qū)域需要特殊處理。標(biāo)記曲率變化大的四個(gè)點(diǎn) A、B、C、D，圖 5(a)所示為過任意三點(diǎn)做與這三個(gè)點(diǎn)相切的內(nèi)切圓，使這個(gè)內(nèi)切圓的圓心到另一個(gè)點(diǎn)的距離與其他三點(diǎn)到圓心的距離的差值最小，標(biāo)記所找到內(nèi)切圓的圓心。標(biāo)記曲率變化大的兩個(gè)點(diǎn)E、F，然后過這兩個(gè)點(diǎn)做與這兩點(diǎn)相切的內(nèi)切圓，如圖5(b)所示。逐漸改變內(nèi)切圓的半徑，找到第三個(gè)點(diǎn)到圓心的距離無限接近以上兩點(diǎn)到圓心的距離，標(biāo)記此時(shí)圓心的位置。找到圓心之后，將此圓心與分支區(qū)域的圓心相連便得到了書法漢字的骨架。

圖5 漢字交叉區(qū)域和相連區(qū)域骨架點(diǎn)計(jì)算

4 實(shí)驗(yàn)結(jié)果分析及討論

采用本文方法計(jì)算的漢字骨架提取的結(jié)果。如果不考慮模糊區(qū)域，對(duì)所有的邊緣按特定步長計(jì)算內(nèi)切圓得到的骨架(以王和女為例)如圖6所示。

圖6 基于內(nèi)切圓方法得到的字體骨架

由于在字體的模糊區(qū)域，邊緣點(diǎn)不能總是按特定步長選取。于是在曲率變化較大的點(diǎn)處斷開，所以計(jì)算得出的模糊區(qū)域的骨架不能保證對(duì)稱性，經(jīng)過對(duì)模糊區(qū)域進(jìn)行特殊處理之后，所得到以上Windows字體的骨架如圖7所示。

圖7 模糊區(qū)域經(jīng)特殊處理之后所得的骨架提取結(jié)果

從圖7可以得出，使用基于內(nèi)切圓的方法以及對(duì)漢字模糊區(qū)域進(jìn)行特殊處理之后，所得到的漢字骨架能基本保持與原字體結(jié)構(gòu)一致，并且在漢字的模糊區(qū)域能夠保持平滑與連通。

本文的算法源于參考文獻(xiàn) [6]，但該方法僅適用于TrueType字體。由于TrueType字體是一種矢量字體，由一系列直線、二次貝塞爾曲線和三次貝塞爾曲線組成，具有無級(jí)縮放而不失真的優(yōu)點(diǎn)，所以曲線段上的坐標(biāo)點(diǎn)可通過求解一定的參數(shù)方程獲取。而本文的算法不僅適用于TrueType字體，而且也適用于其他字體，如隸書、楷體、宋體、黑體等，并且在筆劃交叉區(qū)域計(jì)算所得的骨架也最終得到了滿意的效果。

本文以TrueType字體中心骨架線提取算法研究為基礎(chǔ)，由于其局限性提出了一種適合于多種字體的一種基于內(nèi)切圓的骨架提取算法。常規(guī)的基于像素剝離的細(xì)化算法雖然能快速獲取骨架，但獲取的骨架不攜帶原始書法漢字的線寬信息，且拐角信息容易丟失。而本文的算法簡單靈活、易于實(shí)現(xiàn)，并且計(jì)算所得的骨架不僅攜帶漢字的原始線寬信息，而且骨架具有良好的對(duì)稱性和連通性。

[1]BLUM H.A transformation for extracting new description of shape[A].Model for the Perception of Speech and Visual[C].Cambride， Massachusetts： MIT Press， 1967.362-380.

[2]呂岳，施鵬飛.一種使用并行細(xì)化算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2000(4)：53-56.

[3]張若文，滕奇志，孫曉剛，等.一種快速簡便的圖像骨架變換方法[J].信息與電子工程，2003(1)：1-5.

[4]楊義軍，孟祥旭，等.復(fù)雜帶狀圖像的快速三角剖分與骨架化算法 [J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003(10)：1270-1274.

[5]李小軍，方江龍，蔣知峰.TrueType字體中心骨架線提取算法研究[J].機(jī)械制造，2010，48(1)：19-21.

[6]陳宏希.基于邊緣保持平滑濾波的canny算子邊緣檢測(cè)[J].蘭州交通大學(xué)學(xué)報(bào)，2006，25(1)：86-90.