基于算術運算的改進細化算法

摘 要： 現有細化算法存在細化不完全及二像素寬斜線過度腐蝕現象，在經典算法基礎上提出一種改進算法。新算法采用算術邏輯運算構造輔助判決條件，完善經典算法的刪除判決，抑制二像素寬斜線過度腐蝕現象，并增加二次掃描，刪除經典算法處理后殘留在斜線上的冗余像素，得到8連接的單像素圖像，保持原算法算術運算快速的優點。實驗結果表明，改進算法能夠有效地避免二像素寬斜線的過度腐蝕，保留原圖像的特征信息，實現字符圖像的完全細化。

關鍵詞： 細化算法； 并行算法； 算術運算； 二像素寬斜線

中圖分類號： TN911?34； TP391 文獻標識碼： A 文章編號： 1004?373X（2013）14?0013?04

Improved thinning algorithm based on arithmetic operation

HAN Jian?feng， SONG Li?li

（School of Information Engineering， Inner Mongolia University of Technology， Huhhot 010080， China）

Abstract： An improved algorithm is proposed based on the classical algorithm because the existing thinning algorithms have the phenomena of inadequate thinning and excessive erosion of two?pixel?wide diagonal lines. The arithmetic and logic ope?

rations are adopted in the new algorithm to construct the assistant judgement condition， so as to complete the deletion judgment of the classical algorithm and restrain the excessive erosion of two?pixel?wide diagonal line. The redundancy pixels residual on diagonal line in the classical algorithm processing are deleted by the added secondary scan to obtain the 8?connected single?pixel image and keep the advantage of fast arithmetic operation of the origional algorithm. The Experimental results show that the new algorithm could effectively avoid the excessive erosion of two?pixel?wide diagonal lines， maintain the feature information of original image and realize the sufficient thinning of character images.

Keywords： thinning algorithm； parallel algorithm； arithmetic operation； two?pixel?wide diagonal line

字符識別的關鍵是提取字符圖像的特征信息。通常使用細化算法去除二值化圖像中的冗余像素，得到線寬為單像素的細化圖像，從而能夠較為容易和準確地提取字符的特征信息。細化算法廣泛地應用于圖像分析、特征提取及模式識別等領域中。

現有多種細化算法，從原理上可分為迭代算法和非迭代算法；從運算過程上可分為并行算法和串行算法。文獻[1]對現有多種經典方法進行了分析和比較，如串行的Hilditch算法、Pavlidis算法等及并行的Rosenfeld算法、Rutovitz算法等。由于并行算法是在每次對圖像的掃描后完成對冗余像素的刪除，而串行算法則是在掃描過程中刪除冗余像素，因此普遍認為并行算法更快，在字符識別中并行細化算法應用更多。其中，基于Rutovitz算法的各并行算法最具代表性，特別是Zhang和Suen所提出的ZS細化算法[1?3]應用最為廣泛。另外還有基于模板匹配的細化算法，多應用于指紋圖像處理等領域，如文獻[4?5]提出的算法等。以上算法的細化過程均是基于對圖像的逐像素掃描，稱為迭代算法或基于像素的算法。此外還有所謂非迭代算法，采用找出圖像關鍵輪廓點并連線的方法描繪圖像特征，常用于OCR（光學字符識別）。各種細化算法在不同應用中具有各自的優缺點，但一般而言，良好的細化算法應當具備條件為：保留完整的拓撲和幾何特性；各向同性；對原圖像的重建或恢復；處理速度快。

實際上，由于迭代算法對圖像的掃描順序或子條件的迭代順序可能不同，導致無法實現嚴格的各向同性。

1 現有細化算法

設圖像中某像素p1的8鄰域如圖1所示。其中，像素值為1的點稱為輪廓點，像素值為0的點稱為背景點。ZS算法采用對圖像逐像素掃描的方法，對輪廓點的8鄰域分兩個步驟進行算術邏輯運算，依據運算結果判斷該像素是否應該刪除。

圖1 8鄰域示意圖

步驟1：若輪廓點p1的8鄰域點滿足條件（1）～（4），則標記p1，本次掃描結束后將標記的像素刪除。

（1）

（2）

（3）

（4）

式中：為p1的8鄰域中非零像素的個數，即：。為像素按照順時針方向旋轉時，像素值由0變1的次數。

步驟2：若輪廓點p1的8鄰域點滿足條件（1），（2）及條件（5），（6），則標記p1，本次掃描結束后刪除標記的像素。

（5）

（6）

步驟1，步驟2反復迭代，直至圖像中沒有可以刪除的點，細化結束。

ZS算法的優點是迭代次數少，運行速度快，同時兼顧連續性，對直線、T型交叉和拐角能夠精確地保持和原圖像一致，圖像基本能夠細化為單像素。

ZS算法的主要缺點是對二像素寬斜線的過度腐蝕。如圖2所示，對于二像素寬的斜線，ZS算法將其細化為單像素短直線，細化結果產生了嚴重的失真。另外，ZS算法對斜線的處理不夠理想，細化圖像的斜線上易殘留冗余像素。多種算法對ZS算法進行了改進，如Lu和Wang提出的LW細化算法[1，6]和文獻[7]所提的EPTA算法（Enhanced Parallel Thinning Algorithm）等。

圖2 ZS算法對二像素寬斜線過度腐蝕

LW算法為了解決對二像素寬斜線的過度腐蝕問題，將ZS算法的條件（1）修改為。即放松了ZS算法的刪除條件，從而避免對二像素寬斜線的過度腐蝕。但顯而易見的是，細化結果中會殘留更多的冗余像素，不能完全細化。EPTA算法將掃描分為兩個階段[7]，第一階段掃描與ZS算法相似，僅增加了一個判決條件，即若所有標記刪除的像素滿足，則將該點保留，以避免對二像素寬斜線的過度腐蝕；第二階段專門刪除斜線上的冗余像素。EPTA算法確實能夠在一定程度上避免二像素寬斜線的過度腐蝕，但其存在較大的局限性。雖然在針對單幅斜線圖像細化時可以避免過度腐蝕，但如果圖像中存在其他輪廓點、且其細化所需迭代次數多于二像素寬斜線圖像時，判決條件失效，仍然會產生對二像素寬斜線的過度腐蝕。如圖3所示，包含二像素寬斜線和字符“0”的圖像，隨著字符“0”增大，其所需迭代次數增多，分別為3次、5次、8次，二像素寬斜線出現了部分的和完全的過度腐蝕現象。

圖3 EPTA算法對二像素寬斜線的細化效果

另外，因為用于刪除斜線冗余的條件約束過少，第二階段掃描不能將冗余像素完全刪除，導致EPTA算法細化不完全。文獻[8?10]同樣是對ZS算法的改進。文獻[8]所提算法的速度有所提高，但未能實現完全細化。文獻[9]提出的算法在ZS算法基礎上利用ZS算法條件的鏡像改善細化效果，上文提到由于并行細化算法在根本上不能實現嚴格的各向同性，因此無法根除ZS算法的斜線冗余。

同時該算法也提出了避免二像素寬斜線過度腐蝕的解決辦法，但可能會出現保留過度的現象。文獻[10]所提算法可以刪除ZS算法處理后殘留在斜線的冗余像素，但未對二像素寬斜線過度腐蝕的問題提出解決辦法。

由此可見，以上對ZS算法的改進在增加處理時間的同時，對于細化效果的改善并不明顯，不能實現完全細化。本文采用算術運算的方法對ZS算法改進，在保留經典ZS算法優點的同時，改善斜線冗余像素過多及二像素寬斜線的過度腐蝕問題。

2 改進的細化算法

定義輪廓點p1的擴展鄰域如圖4所示。

本文所提改進算法采用算術邏輯運算對擴展鄰域的像素進行判斷，確定其是否應被刪除。

圖4 擴展鄰域示意圖

步驟1：掃描圖像，若輪廓點p1滿足條件（1）～（4），且不滿足（7）～（10），則標記，本次掃描結束后，將標記像素刪除；

且：

（7）

且：

（8）

且：

（9）

且：

（10）

步驟2：掃描圖像，若輪廓點p1滿足條件（1），（2），（5），（6），且不滿足（7）～（10），則標記，本次掃描結束后，將標記像素刪除；

步驟3：判斷刪除標記，若標記為1，跳至步驟1；若標記為0，則跳至下一步；

步驟4：掃描圖像，若輪廓點p1滿足條件（11）或條件（12）或條件（13）或條件（14），則刪除之；

（11）

（12）

（13）

（14）

步驟5：判斷刪除標記，若標記為1，則跳至步驟4；若標記為0，則細化結束。

步驟1，2與ZS算法相似，從兩個方向對圖像進行掃描，使用條件（1）～（4）或（1），（2），（5），（6）及條件（7）～（10）確定是否刪除輪廓點。條件（7）～（10）用于避免二像素寬斜線的過度腐蝕現象。如果輪廓點滿足條件（1）～（4），且滿足條件（7）～（10）之一，則該點可能在二像素寬斜線上，應予以保留；若均不滿足，說明其為冗余像素，在本次掃描后將被刪除。改進算法沒有直接修改ZS算法的條件，而是針對二像素寬斜線增加了判決條件，雖然會增加少許處理時間，但既可避免二像素寬斜線的過度腐蝕，又可避免因放寬ZS算法的約束條件而殘留過多冗余像素。

步驟4使用條件（11）～（14）刪除斜線上的殘留冗余像素。若輪廓點滿足條件（11）～（14）之一，則將其刪除，直至完全細化。在實際處理中，與ZS算法相比，通常只需增加兩次迭代即可，保證了改進算法的快速性。

圖5為改進算法對二像素寬斜線以及包含“0”字符的二像素寬斜線細化效果圖?？梢姡疚乃岬母倪M算法，對于避免二像素寬斜線的過度腐蝕現象更具普遍性。

圖5 改進算法對二像素寬斜線的細化效果

3 實驗結果與分析

實驗中采用ZS算法與本文所提改進算法分別對英文字母、阿拉伯數字及漢字進行細化處理，部分實驗結果如圖6～圖8所示。

圖6 英文字母細化效果

ZS算法的細化結果中在多個字符中存在明顯的細化不完全現象，對漢字“彩”的細化結果中甚至出現了過度腐蝕現象。在研究中發現，ZS算法細化后在斜線上殘留冗余像素的原因是細化過程中這些像素不滿足條件（2），因此無法刪除，在多次掃描后仍然會留在圖像中。改進算法則不存在上述問題，細化后得到了單像素、保持8連接的圖像，同時避免了ZS算法、EPTA算法等二像素寬斜線的過度腐蝕現象。

在Pentinm 4 3.0，1 GB內存計算機上針對100幅22×28像素字符圖像的多次實驗中，改進算法平均處理時間3.02 s，而ZS算法為2.36 s，增加的處理時間主要用于過度腐蝕現象的抑制以及斜線上冗余像素的刪除。

圖7 阿拉伯數字細化效果

圖8 漢字細化效果

4 結 語

本文提出了一種采用算術邏輯運算的改進細化算法。針對字符圖像的實驗結果證明，改進算法以增加少量處理時間為代價，能夠實現完全細化，得到單像素且滿足8連接條件的細化圖像，有效避免了ZS算法等經典算法中存在的二像素寬斜線的過度腐蝕現象，完整地保留了字符圖像的特征信息。

參考文獻

[1] LAM L， LEE S W， SUEN C Y. Thinning methodologies： a comprehensive survey [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1992， 14（9）： 869?885.

[2] ZhANG T Y， SUEN C Y. A fast thinning algorithm for thinning digital patterns [J]. Communications of ACM， 1984， 27（3）： 236?239.

[3] GONZALEZ R C， WOODS R E. Digital image processing [M]. 2nd ed. Beijing： Publishing House of Electronics Industry， 2002.

[4] 王家隆，郭成安.一種改進的圖像模板細化算法[J].中國圖象圖形學報，2004，9（3）：297?301.

[5] 梅園，孫懷江，夏德深.一種基于改進后模板的圖像快速細化算法[J].中國圖象圖形學報，2006，11（9）：1306?1311.

[6] LU H E， WANG P S P. A comment on “a fast parallel thinning algorithm for thinning digital patterns” [J]. Communications of ACM， 1986， 29（3）： 239?242.

[7] 包建軍，樊菁.魯棒的二值圖像并行細化算法[J].計算機輔助工程，2006，15（4）：43?46.

[8] 喻擎蒼，蘇斌，李華強.改進的符號圖像并行細化算法[J].計算機工程與設計，2009，30（3）：723?724.

[9] 賀繼剛，楊曉偉，吳廣潮.基于模板保留的快速并行細化算法[J].計算機應用與軟件，2007，24（12）：26?28.

[10] 王朋，張有光，張爍.指紋圖像細化的綜合化算法[J].計算機輔助設計與圖形學學報，2009，21（2）：179?182.