一種改進的漢字骨架提取算法

侯立斐，張 靜，霍玲玲

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

骨架是一種重要的圖像目標幾何特征，利用骨架表示原始圖像，可以在保持圖像重要拓撲特征的前提下，減少圖像中的冗余信息。因此，骨架被廣泛應(yīng)用于圖像目標的形狀分析、信息壓縮、特征提取、模式識別等領(lǐng)域。

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

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

1 邊緣提取和邊緣點的選取

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

1.1 邊緣提取

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

圖1 Windows輸入的字體

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

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

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

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

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

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

圖2 對原始字體進行邊緣檢測的結(jié)果

1.2 邊緣點的選取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 漢字模糊區(qū)域骨架點計算

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

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

4 實驗結(jié)果分析及討論

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

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

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

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

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

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

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

[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]呂岳，施鵬飛.一種使用并行細化算法及其實現(xiàn)[J].計算機工程與設(shè)計，2000(4)：53-56.

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

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

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

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