一种新的快速图像细化算法研究与实现

摘要:关于细化的算法有多种,针对模板匹配的rosen算法的不足之处,该文又提出一种新的快速细化算法,并进行了计算机仿真,结果显示改进的算法无论在细化质量上更为实用,消除了毛刺和笔划断裂现象,可用于进一步的文字及图像识别软件的开发。

关键词:汉字识别;细化算法;特征提取;图像处理

中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)16-4482-03

A New Fast Image Thinning Algorithm and Implementation

YAO Yao,WANG Wei, WANG Ai-ju

(Zhongzhou University, Zhengzhou 45044, China)

Abstract: There are many methods of thinning, in this paper, rosen algorithm is compared with the new algorithm. this paper suggests a new thinning algorithm method. Simulation results show that our algorithm has considerable improvement in quality over the existing methods, and the "delimits break" and "thir hair" phenomena disappeared. It can be further used in the development of CCR software.

Key words: Chinese character recognition; thinning algorithm; feature extraction; image processing

汉字识别(Chinese Character Recognition,简称CCR)和图像识别是模式识别的一个重要分支,是中文信息处理中汉字自动高速输入的一种主要手段。它与语音识别一起,成为目前智能信息输入中两个亟待解决的难题。细化是汉字识别和图像识别预处理中最重要的技术之一。

1 细化方法的分类

近二十年来,人们提出了许多细化算法,Suen等人调查了不下100种细化方法,并将其分为两类:一类是以象素迭代删除为基础的方法;另一类是以非象素为基础的方法。前者又叫窗口法,是利用一个窗口算子依次从左到右,从上到下移动,根据某种准则,确定中心象素的保留或删除,它又进一步分为串行和并行两种方法。串行细化即是一边检测满足细化条件的点一边删除细化点,并行细化即是检测细化点的时候不进行点的删除只进行标记,而在检测完整幅图像后一次性去除要细化的点。后者是利用汉字或图像结构特征的细化方法,能获得高质量的细化效果,但算法复杂,计算量大。

2 模板匹配的Rosen细化算法

关于细化(如图1 中的3×3 窗口) , 做如下定义:

(1) 串行处理:在3×3 的窗口中对某一元素进行检测, 若发现该点是可删除点, 就立即删除;

(2) 并行处理:在全部检测完汉字图像边缘上的点后同时改变所有可删除点的值;

(3) 若x0为黑点且x1, x2, ., x8中只有一个黑点,称x0为端点;

(4) 若3×3 窗口中只有x0为黑点,称x0为孤立点。

(5) 若x0为黑点且x1, x3, x5, x7中仅有一白点, 称x0为边界点;

(6) 若删除黑点x0会破坏图形的连续性, 则称x0为断点;

(7) 若黑点x0的3×3 窗口中x3= 0, 称x0为上边缘点;

(8) 若黑点x0的3×3 窗口中x5= 0, 称x0为左边缘点;

(9) 若黑点x0的3×3 窗口中x7= 0, 称x0为下边缘点;

(10) 若黑点x0的3×3 窗口中x1= 0, 称x0为右边缘点

Rosen 采用的是模板匹配的细化算法, 该方法利用Sherman 的技术, 将细化应满足的最终结果作为已知信息定义为模板(用3×3 的窗口表示) , 然后对待识汉字图像进行搜索, 将与已知模板匹配的象素x0保留。Rosen 模板的制定准则:(1) x0不是边界点; (2) x0是端点或是孤立点; (3) 若删除x1, x3, x5, x7, x0 会成为断点;(4) 从上、下、左、右边缘点中保留断点。根据准则,Rosen 定义出下列8 个模板(如图3)。上述模板中,x,y 中至少有一个为1,空表示取值任意。

Rosen 细化算法中, 采用了并行处理操作, 从上、下、左、右4 个方向4 次循环完成一次轮廓剥离。其算法为:

do

{ 对于黑点x0,若x0为孤立点或端点,继续搜索

(1) 若上边缘点的3×3 窗口与模板Ⅱ至 Ⅷ 匹配,继续搜索

(2) 若下边缘点的3×3 窗口与模板Ⅰ及Ⅱ至 Ⅷ 匹配,继续搜索

(3) 若左边缘点的3×3窗口与模板Ⅰ,Ⅱ及 Ⅳ 至 Ⅷ 匹配,继续搜索

(4) 若上边缘点的3×3 窗口与除模板Ⅳ 外的模板匹与,继续搜索

(5) 否则,标记x0

} while (无点可删)

细化的结果

图4为Rosen细化结果,显然,该算法造成笔划断裂的现象。

上面所提到的细化算法,基本上符合了汉字或图像细化的要求,但却有不足之处:算法容易造成笔划断裂现象。因而,有必要提出一种新的图像细化算法。

3 一种新的快速图像细化算法

传统的细化算法一般都是采用迭代的方法,逐步去除边缘点。一般迭代算法只采用局部窗口,具有容易产生畸变、无法消除较大的边缘噪音、细化速度慢等缺点。还有一些细化算法,虽然采用了全局信息,甚至还采用了局部信息,但只针对某些特定的环境,对环境的依赖性较强。本文提出了一种新的细化算法,充分利用图像的全局和局部信息,只需对图像进行一次遍历,就可以对图像实现快速精确的细化。为了方便起见,本文假设处理对象为二值图像,高为h个象素,宽为w个象素,背景颜色为白色,前景颜色为黑色。

3.1 算法描述

本文算法流程图如图5。

3.2 划分图像

在对图像扫描的过程中,同时对图像进行划分。通过执行划分算法,只需遍历一次,就可以把整个图像分为若干个色块。例如:根据划分算法,图6中的(a)和(b)都划分为b1,b2,b3三部分,(c)则被划分为b1,b2,b3,b4四部分。

3.3 建立无向图

我们用无向图的顶点来表示色块,用无向图的弧来表示色块与色块之间的关系。如果两个色块之间是上下紧密相连的(如图6(a)中的b1和b2,b1和b3都是上下紧密相连的,而图6(a)中的b2和b3却不是上下紧密相连的),则说它们所对应的顶点之间有弧存在,否则就不存在弧。这样定义了顶点和弧,我们就可以建立图像的无向图。

3.4 局部细化

由划分算法可知,每一个色块都是由若干在Y方向上相邻的线段组成的。对于一个色块的每一条线段,经过其中点分别作0°,45°,90°,135°方向的直线,分别得到这些直线在被处理图像上的线段长度:d0,d45,d90,d135。如果d90≥ d0或d45≥d0或d135≥d0,则称图像在此线段处的走向为垂直走向,否则为水平走向。如果图像在某个区域内的所有线段上走向都是垂直走向(水平走向),就称图像在此区域内的走向为垂直走向(水平走向)。这样一来,一个色块就有可能被分为一个或多个区域,图像在这些区域或是垂直走向的,或是水平走向的。通过算法,就可以求出一个色块的中心线。从算法中看到,与求垂直走向区域的中心线不同的是:在求水平走向区域的中心线时,所求的中点有可能不在该区域内,而在其相邻区域或相邻色块中,这样就有可能造成相邻区域或相邻色块的中心线之间重叠,因此区域的中心线必须由那些在该区域范围内的点组成。

3.5 连接产生骨架

得到所有色块的中心线以后,接下来的工作就是根据各个色块在无向图中的关系,连接产生整个图像的骨架。

由上面的划分算法可知,在扫描图像的过程中,只有遇到分叉时,才对图像进行划分,生成新的色块。由于三分叉和三分叉以上的情况处理起来十分复杂,且在实际应用中很少遇到,这里只介绍常见的二分叉情况的处理办法。对于二分叉情况,又可以分两种情况来处理:

1) 如图7(c),b2和b3分别与b1的两端相连,同时b2和b3分别与b4的两端相连。对于这种分叉情况,直接按照各个色块之间的相邻关系,对它们的中心线进行首尾连接即可。

2) 如图7(a),b2和b3都与b1的同一端相连,是上分叉的;图7(b)中,b1和b2都与b3的同一端相连,是下分叉的;由于上分叉和下分叉的处理方法一样,下面就只介绍处理上分叉的算法。

∥数组aL1,aL2, aL3分别存放色块b1, b2, b3的中心线上的点;

∥数组aB1存放色块b1的中线段;n1表示数组aB1的大小;

∥d0表示正常情况下被处理的图像的线宽;C表示色块中两线段长度的最大差值;

∥lflag,rflag分别表示左右两边处理情况,值为TURE表示处理结束;

i:=0;lflag:=FALSE; rflag:= FALSE;

d:=d0/2; oldd1:=d;olddr:=d;

while i〈n1 do begin

get P(Xm,Ym) from aL1;get线段(P(X1,Yl),P(Xr,Yr)) from aB1;

dl:=Xm-Xl; dr:=Xr-Xm;

ifulflag And abs (d1-oldd1)〈c then begin

if abs(d1-d)≤0 then lflag:-TURE;

else begin

oldd1:= d1; addP(Xm,Ym)to aL2;

ifurflag then deleteP(Xm,Ym) from aL1;

end

end;

ifurflagAnd abs (dr-olddr)〈 cthenbegin

if abs (dr-d)≤0then rflag:=TURE;

else begin

olddr:=dr;add p (xm,ym) from aL3;

ifurflag then delete p(xm,ym) from aL1;

end

end;

if lflag And rflag then i:=n1;

else i:=i+1;

end。

例如:图8是一个分叉的图像,共有三个色块b1,b2,b3,它们的中心线为S1E1,S2E2,和S3E3。利用上面算法分别求得S2P12与S3P13。其中点P12和P13都在S1E1上,且S1E1上的P12E1部分被去掉。最后得到整个图像的骨架S1-P13-P12-S2-E2 和S1-P13-S3-E3。

3.6重描图像

得到图像的骨架后,首先采用线性插值对骨架进行平滑处理;然后,对骨架进行分段,把它分成若干个曲线或直线段;最后分别应用画曲线或直线的算法,画出整个被处理的骨架。

4 结束语

本文在比较了原有细化算法的基础上,针对它们的缺点,提出了一种新的快速细化算法,不仅实现了一般的细化,而且还严格避免了笔划断裂现象的出现,进一步保持了拓扑结构的不变性。另外由于本算法能消除毛刺,而且对轮廓噪声有较大的免疫力,且细化的速度较前两种算法有很大的提高,所以本算法有较好的适应性,有利于大规模的软件开发和研制。细化效果如图9所示。

参考文献:

[1] 周新伦.一种并行细化算法及其硬件实现放案[J].模式识别与人工智能,1994,7(1):1-6.

[2] 方卫宁,邹华.二值模式的一种快速细化算法[J].图像识别与自动化,1994,(1):16-19.

[3] 钱乐秋.文字图形的快速细化算法[D].自动化,1981,5(1):90-94.

[4] 赵珀璋,张松芝.中文信息处理技术[M].北京:宇航出版社,1990.

[5] 卢军,陶刚,李吉桂.一种新的指纹图像细化方法[J].现代计算机,2000,11:42-44.

[6] 唐海勇,唐海刚,邵岩.线条纹图像的细化[P].哈尔滨理工大学学报,2000,4(8):50-53.

[7] 王贵林,卿斯汉.几个门限群签名体制[J].计算机学报,2000:11(10):1362-1332.

[8] 周冠雄.计算机模式识别[M].武汉:华中工学院出版社,1986.

[9] 荆仁杰,叶秀清,徐胜勇,陈存椿.计算机图像处理[M], 浙江:浙江大学出版社,1990

[10] Lam L,lee S W.Suen C Y.Thinning Methodologies A Comprehensive Survey.IEEE[M].Trans,PAMI, 1992, 14(9):869-883.

[11] Sherman H.A quasi2top lo logical method for the recognition of line pat terns[M],Information P rocess2ing, Proceeding of a UN ESCO Conference in Paris in 1959, 1232-1235.

[12] James L.Anonakos.The Pentium Microprocessor [M].Prentice Hall, 1997.