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

侯立斐，張 靜，霍玲玲

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

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

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

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

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

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

1.1 邊緣提取

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

圖1 Windows輸入的字體

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

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

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

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

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

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

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

1.2 邊緣點的選取

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

2 內切圓的計算

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

漢字骨架提取的主要實現步驟為：

圖3 與直線AB相切的內切圓

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

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

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

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

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

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

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

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

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

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

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

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

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

3 漢字模糊區域骨架點計算

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

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

4 實驗結果分析及討論

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

圖6 基于內切圓方法得到的字體骨架

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

圖7 模糊區域經特殊處理之后所得的骨架提取結果

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

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

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

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

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

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

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

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