基于方向約束的文字骨架毛刺去除算法

范 靜，顏廷秦，崔 鳴，薛知言

（蘇州市職業(yè)大學 電子信息工程學院，江蘇 蘇州 215104）

圖像骨架提取在圖像特征提取、模式識別等領域具有廣泛的應用[1]。文字骨架提取是文字識別過程的重要環(huán)節(jié)。提取文字骨架往往要求有三個基本特性：連續(xù)性、單像素性、中心性，并且能夠完整地表現(xiàn)出文字的基本結構、筆畫等特征。在骨架提取的過程中，由于提取方法的不同以及噪聲的干擾，都會產(chǎn)生不同程度的毛刺[2]。毛刺的出現(xiàn)會影響后續(xù)的文字識別結果，影響識別率。

1 文字骨架毛刺去除方法及特點

文字骨架毛刺去除方法大致可以分為以下4種：①優(yōu)化骨架提取方法，從而達到去除毛刺的目的[3-4]，但并不普遍適用。②基于模板的毛刺去除方法[5]。③基于區(qū)域重構的毛刺去除方法[6]，利用骨架顯著性指標進行閾值化處理，計算量很大。④通過毛刺長度閾值判別毛刺[7-8]，而不考慮主干與分支的連續(xù)性，有可能會誤刪有效分支（主干），并且在節(jié)點的判斷上僅僅考慮了兩種節(jié)點的情況，未考慮節(jié)點冗余情況，并不具有普適性。

常用的ZS細化算法[9]、LW細化算法[10]、K3M細化算法[11-12]的文字骨架提取效果如圖1所示。

圖1 不同細化算法的文字骨架提取效果

由圖1可知，不同細化算法的文字骨架提取效果均具有毛刺；毛刺與主干相比長度較短；毛刺與主干呈一定方向的夾角。

針對閾值法刪除毛刺會出現(xiàn)節(jié)點冗余以及誤刪骨架本身的情況，本研究在閾值法的基礎上，具有以下創(chuàng)新點：①增加了節(jié)點冗余去除模板，使骨架節(jié)點更清晰，適用于所有文字骨架，鏈碼跟蹤更準確。②在鏈碼跟蹤時不是一味地從節(jié)點向端點跟蹤編碼，而是預分類主干和毛刺，并對其分類編碼，便于計算主干與毛刺的方向夾角。③重新標定了方向鏈碼，解決了鏈碼首尾的不連續(xù)性，據(jù)此計算方向夾角。④在長度閾值的基礎上，增加了根據(jù)夾角閾值選擇性刪除毛刺，提高了毛刺刪除的準確率。

2 毛刺與端點、節(jié)點的關系

去除毛刺的關鍵是找到毛刺線段，并將其轉化為背景色。主干毛刺示意圖如圖2所示。圖2中的線段bc和df應為毛刺，毛刺共同點是起始于與主干的交叉點（b、d），終于端點（c、f）。在連續(xù)的單像素骨架中找到交叉點和端點是去除毛刺的第一步。

圖2 主干毛刺示意圖

2.1 端點與節(jié)點的定義

這里規(guī)定背景像素值為0，骨架像素值為1。理想的骨架像素應該在8鄰域中只有2個骨架像素與之相連接。

定義1一個像素的8鄰域中有且只有一個像素為1的點，則定義此點為端點。

定義2一個像素的8鄰域中有3個或3個以上像素為1的點，則定義此點為節(jié)點（交叉點）。

定義3N（P）為P（x，y）點8鄰域中像素為1的點的個數(shù)。

將原始圖像image1轉存為image2，掃描像素點，當像素點的8鄰域滿足端點或節(jié)點的定義時，在image2中分別對其進行標記并記錄坐標值為

2.2 節(jié)點冗余去除模板

根據(jù)節(jié)點的定義，將滿足條件的骨架像素標記為4，則可能會出現(xiàn)節(jié)點冗余的情況，形成腫塊，如圖3所示。腫塊現(xiàn)象會影響后續(xù)的鏈碼跟蹤，所以這里引入節(jié)點冗余刪除模板，如圖4所示。將冗余的節(jié)點還原標記為默認骨架1。

圖3 節(jié)點冗余

在圖4模板中，0代表背景像素點，1代表骨架像素點，X代表任意值，不影響刪除模板的判斷。在image1中根據(jù)節(jié)點坐標遍歷節(jié)點，當節(jié)點的8鄰域像素點滿足節(jié)點冗余刪除模板條件，則在image2中將其8鄰域內(nèi)已標記的冗余節(jié)點還原為默認骨架，如表1所示。若image1中某P點滿足冗余條件，則將image2中對應的Pi替換成1。

表1 刪除image2中的冗余節(jié)點

圖4 節(jié)點冗余刪除模板

3 基于方向約束的鏈碼跟蹤方法

3.1 鏈碼跟蹤

鏈碼跟蹤是利用起始點和跟蹤點的方向碼來描述曲線的延伸方向。常用的鏈碼跟蹤有8連通鏈碼和4連通鏈碼，本文使用的8連通鏈碼如圖5所示。單像素連續(xù)骨架圖如圖6所示。

圖6 單像素連續(xù)骨架圖

3.1.1 利用8連通鏈碼跟蹤骨架

根據(jù)定義P0（3,3）、P1（8,8）是節(jié)點，P2（6,10）、P3（10,10）是端點。從節(jié)點P1開始行程跟蹤，并標記跟蹤過的像素，直到跟蹤到下一個節(jié)點或者端點，共跟蹤到三條分支。骨架鏈碼跟蹤如圖7所示。

圖7 骨架鏈碼跟蹤

骨架在方向編碼時分為兩類：

1）節(jié)點跟蹤到節(jié)點，預分類為主干。主干在編碼時方向為終點到起點；

2）節(jié)點跟蹤到端點，預分類為分支。分支在編碼時方向為起點到終點。

如：P1→P0主干，根據(jù)8連通鏈碼，得到鏈碼為77777。

P1→P2分支，根據(jù)8連通鏈碼，得到鏈碼為11。

P1→P3分支，根據(jù)8連通鏈碼，得到鏈碼為77。

3.1.2 計算分支長度

分支長度可以利用已得到的8連通鏈碼來計算。Ne為偶數(shù)鏈碼的個數(shù),No為奇數(shù)鏈碼的個數(shù),Nc為鏈碼方向發(fā)生變化的個數(shù)，則鏈碼長度L為

其中：A=1；；C=0。由此可得，P1到P2分支的長度;P1到P3分支的長度。

3.2 方向約束

若僅通過分支長度是否小于毛刺閾值來判斷毛刺，可能會造成分支的誤刪。比如，若毛刺閾值,則線段P1P2、P1P3都將被刪除。但線段P1P3與骨架主干的延伸方向一致，是骨架的一部分而并非毛刺，此時，需要引入方向約束。

方向約束是將毛刺的延伸方向與主干的延伸方向的夾角，與預先設定的角度閾值進行比較，當分支與主干夾角大于角度閾值時，則此分支定義為毛刺。方向夾角可轉化為方向鏈碼差實現(xiàn)，如0方向和1方向鏈碼差為1。注意，雖然1方向和7方向與0方向的夾角均為45°，但是鏈碼差是不相同的，分別為1和7。在計算鏈碼差前，需將鏈碼重新標定為

式中：MN為新鏈碼值；MO為原鏈碼值。計算節(jié)點引出的各分支與主干的2到3個鏈碼均值，將分支的鏈碼均值與主干的鏈碼均值相減，若此分支鏈碼差大于鏈碼角度閾值，則判別為毛刺。

3.3 毛刺去除的方法

毛刺去除的算法如圖8所示。其步驟如下：

圖8 毛刺去除算法

1）遍歷骨架元素，根據(jù)端點、節(jié)點的定義分別標記并記錄其坐標，利用節(jié)點冗余模板，刪除冗余的節(jié)點標記和坐標。

2） 從節(jié)點開始，對各分支進行鏈碼跟蹤，并記錄分支坐標。若分支跟蹤到的結束點為節(jié)點，則將此線段分類為主干，并從結束點向開始節(jié)點方向進行方向編碼；若分支跟蹤到的結束點為端點，則將此線段分類為分支，并從開始節(jié)點向結束點方向進行方向編碼，計算分支鏈碼長度。

3） 將同一節(jié)點引出的分支鏈碼長度與毛刺長度閾值進行比較。若分支長度小于長度閾值，則進行下一步；若各分支均大于長度閾值，則計算下一個節(jié)點。

4） 對主干和分支的鏈碼重新標定，并計算各分支與主干的鏈碼差，若鏈碼差大于鏈碼角度閾值，則認定此分支為毛刺，并將其刪除。

5）若各節(jié)點遍歷結束，則輸出圖像。

4 實驗結果與分析

4.1 實驗效果

為了驗證方向約束對文字骨架毛刺的去除效果，實驗采用的原始圖像為細化之后的連續(xù)單像素文字骨架，然后使用本文算法進行毛刺去除處理。本實驗中角度閾值Cth=0.95。設圖像的短邊長為Lma，則毛刺的長度閾值為

式中n可根據(jù)文字的實際情況調(diào)節(jié)大小。

例1.“永”字的骨架毛刺去除效果，如圖9所示。圖9 (a)為已通過細化的“永”字骨架；圖9(b)為僅通過長度閾值來刪除毛刺的效果；圖9(c)為在長度閾值判別毛刺的基礎上加入了方向約束刪除毛刺的效果。

由圖9可以看出，原始圖像在“永”字的勾和捺處有兩處毛刺，僅僅通過毛刺長度閾值刪除毛刺，誤刪了文字本身骨架（捺處的文字骨架），通過方向約束可以有效地保護文字本身骨架，毛刺刪除效果更佳。

圖9 “永”字的骨架毛刺去除效果

例2.“波”字的骨架毛刺去除效果，如圖10所示。

圖10 “波”字的骨架毛刺去除效果

由圖10可以看出，經(jīng)過比較，僅通過長度閾值比較會刪除“波”字的點、撇和捺處的骨架，見圖10（a）已圈出部分，而方向約束可以保留這三處骨架，使文字骨架更完整。

例3.多文字骨架毛刺去除效果，如圖11所示。

圖11 多文字骨架毛刺去除效果

由圖11可以看出，方向約束法可以很好地去除文字毛刺，并完整地保留了文字本身的骨架，為后續(xù)的文字識別提高了可靠性。

4.2 實驗結果的比較分析

本實驗將100組分辨率為150×150的文字圖片進行骨架化去毛刺處理，從運行時間以及刪除毛刺效果兩個方面對閾值法和方向約束法進行了對比。兩種算法運行時間對比如表2所示。兩種算法刪除毛刺效果對比如表3所示。

表2 兩種算法運行時間對比 /s

表3 兩種算法刪除毛刺效果對比

由表2可知，閾值法由于并未對毛刺方向進行計算，所以運行時間略短于方向約束法，但是并沒有顯著的差異。

由表3可知，閾值法共刪除了367條毛刺，方向約束法通過方向性共刪除了341條毛刺。通過人工判別，方向約束法共保留了閾值法刪除保留的26條骨架中，22條為文字本身骨架（閾值法錯誤刪除），4條毛刺由于與主干夾角較小被錯誤保留；兩種算法均錯誤刪除了6條骨架，閾值法除此之外，還錯誤刪除了方向約束法保留的22條文字本身骨架，共錯誤刪除28條骨架。從刪除和保留的準確率來看，方向約束法提高了刪除毛刺的準確率，效果明顯。

5 結論

1）針對文字骨架的提取，提出了一種基于方向約束的鏈碼跟蹤毛刺去除方法。在節(jié)點的判斷上引入節(jié)點冗余模板，更好地判斷了骨架節(jié)點，防止節(jié)點冗余現(xiàn)象。在毛刺長度閾值判斷的基礎上，通過毛刺延伸方向與主干延伸方向的夾角閾值來判別毛刺，特別當文字骨架延伸段長度與毛刺長度相似時，骨架容易被錯誤去除。實驗結果表明，此方法能很好地去除毛刺并保留文字骨架，效果良好。

2）對于毛刺長度閾值，本文通過圖像短軸的實際情況調(diào)節(jié)，并未考慮文字本身的骨架主干長度，有待進一步研究。