基于算术运算的改进细化算法
基于算术运算的改进细化算法
作者：韩建峰宋丽丽
来源：《现代电子技术》2013年第14期
摘要：现有细化算法存在细化不完全及二像素宽斜线过度腐蚀现象，在经典算法基础上提出一种改进算法。新算法采用算术逻辑运算构造辅助判决条件，完善经典算法的删除判决，抑制二像素宽斜线过度腐蚀现象，并增加二次扫描，删除经典算法处理后残留在斜线上的冗余像素，得到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）