APP下载

二值图像的快速细化算法

2012-08-22王广伟

科技视界 2012年14期
关键词:层数细化骨架

余 樑 王广伟

(浙江海洋学院数理信息学院 浙江 舟山 316000)

0 引言

在图像处理领域,处理大量的图像信息之前,往往需要对图像进行预处理,以便于后面的图像分析、图形理解和图形特征提取等。图像细化就是对于图像预处理方法的一种,特别在文字识别、指纹识别与图像理解中,对图像进行细化有效的提高了处理效率,减少数据冗余。

1 像的细化分析

图像的细化主要是针对二值图而言,对图像的细化过程实际上是求该图像骨架的过程。所谓的骨架,可以理解为图像的中轴:长方形的骨架,是长方向的中线;圆形的骨架,是圆心这一点。

常用的细化算法有查表细化和逐层剥取细化。

查表细化是建立一个公认合理的索引表。规定黑色值1,白色值0;从上到下,从左到右依次逐个判断每一个点,碰到当前点为黑色,然后通过公式(图 1),计算出当前点的值,所得的值对照索引表(图2)中值,若deletemark=0,该点删除,deletemark=1,该点保留为黑色。反复扫描直到不再变化。

图1 公式规则

常用的逐层剥取细化算法有Hilditch,该算法通过判断图像中属于边界点而不是连通点,就可以去掉此点,这是一种反复扫描的过程。如果对于一个矩形区域(图3),从左上角开始到右下角,每次扫描可以讲矩形最外面一层剔去,层层剥离后,最终剩下最中间的一条线(图4)。

图2 索引表

图3 细化前图

图4 灰色即剥取点

综合以上分析,上述算法处理图像时都需要反复对图像进行扫描,删除可剔除点。若图像较粗,扫描次数大量增加,因此效率低下,适合于小图或者少量图像处理。

2 细化算法

本算法基于逐层剥取理念,快速细化算法改进了反复扫描的过程,顺序、逆序搜索两次,确定每个点的层数,通过层数可判断该点属于边界点还是骨架,因而优化算法的效率,大量减少程序运算时间。

以下是对于算法的详细步骤(规定黑色值1白色值0):

第一步,从上到下,从左到右依次扫描每一个点,若当前点(x,y)为黑点时,需判断其右上、上、左上和左四点的情况(图 5)。 (x-1,y+1) (x-1,y) (x-1,y-1) (x,y-1) 这四点可以理解为当前点是被该四点包围,该点层数即四点层数最小值多一层;如果当前点(x,y)为白色,层数值赋为0。

图5 上至下左至右F值

图6 下至上右至左G值

第二步,自下而上,自右而左,与第一步相似的判断每个点的状态,若当前点是黑点,于是判断其左下、下、右下和右四点的情况(图6)。 (x+1,y-1) (x+1,y) (x+1,y+1) (x,y+1)四点包围了当前点,同样取这四点层数的最小值加1作为该点层数值;如果当前点(x,y)为白色,层数值赋为0。

与此同时,既然已经求得每一个点上包围层数值和下包围层数值,每个点的实际层数其实就是两种层数值中最小值(图 7)。

图7 取点的层数值M值

第三步,从上到下,从左到右依次扫描每一个点,此时需要判断该点8方向(图7)范围内所有点层数的情况。如果当前点的层数值是周围相邻点中最大,该点即保留;如果当前点的层数值并非最大,该点即可删去。

综上步骤,即完成了该图像细化的全部过程,算法只需遍历3次,就能将一幅图像进行快速细化。

3 结果分析

图8-0 原图

图8-1 快速细化算法

图8-2 索引表算法图

图8-3 Hilditch细化算法

图9-0 原图

图9-1 快速细化算法

图9-2 索引表算法

图9-3 Hilditch算法

从图像上(图8-0图9-0)可以看出,上述3种算法都能有效细化图像,得到图像骨架;在索引表细化及Hilditch细化中保持了图像的连通性,但出现大量毛刺;快速细化算法则出现部分断裂,但较高描述图像形态。

表1

从表1也可发现,在线条较细的图像中(图8-0),三种算法运行时间几乎相同;而在线条较粗的图像中(图9-0),快速细化算法运算时间明显优于其余两种,再将图像(图9-0)等比例放大一倍后,快速细化算法运算时间约原图像的3倍,而其余两种算法则需6-7倍,从而看出快速细化算法的优势。

[1]田刚,马琨.数字图像处理在等差条纹骨架线提取中的应用[J].

[2]韩九强.机器视觉技术及应用[M].高等教育出版社,2009.

[3]Rafael C.Gonzalez Richard E.Woods.冈萨雷斯数字图像处理[M].电子工业出版社,2003.

[4]卞维新,徐德琴,王俊书.基于两极复合式指纹图像细化算法的研究[J].贵州工业大学学报:自然科学版,2005,34(3):80-84.

[5]王家隆,郭成安.一种改进的图像模板细化算法[J].中国图象图形学报,2004,9(3):297-301.

[6]梅园,孙怀江,夏德深.一种基于改进后模板的图像快速细化算法[J].中国图象图形学报,2006,11(9):1306-1311.

[7]王业琳,宁新宝,尹义龙.指纹图像细化算法的研究[J].南京大学学报:自然科学,2003,39(4):468-475.

猜你喜欢

层数细化骨架
填筑层数对土石坝应力变形的影响研究
浅谈管状骨架喷涂方法
上海发布药品包装物减量指南
MoS2薄膜电子性质随层数变化的理论研究
“细化”市场,赚取百万财富
“住宅全装修”政策亟需细化完善
住在哪一层
基于数据分析的大气腐蚀等级细化研究
内支撑骨架封抽技术在突出煤层瓦斯抽采中的应用
铁骨架配合物凝胶的合成、表征及催化性能