基于多向切片中点的快速图像细化算法

文章编号: 100923443 (2005) 0520419205 基于多向切片中点的快速图像细化算法 曹铁勇, 　杨吉斌, 　骆　坚 (解放军理工大学 通信工程学院, 江苏 南京 210007) 摘　要: 在对几种常用细化算法进行探讨之后, 提出了利用骨架上的像素点至少在某个方向上应处于该方 向对象边界的中心点处的特点, 从多个方向对细化对象进行切片, 并利用这些切片中心点集作为原始数据 集, 以快速产生对象骨架的方法。实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明, 本算法与基于击中- 击不中方式和最大圆盘方式的算法相 比, 具有复杂度低, 运算时间少的特点。 关键词: 图像处理; 骨架; 细化; 多向交线中点 中图分类号: TN 911173; E919 文献标识码: A Fa s t im a ge th inn ing a lgo rithm ba s e d on m idpo in ts of m ulti2o rie n ta tion s lice s CA O T ie2y ong , 　YA N G J i2bing , 　L UO J ian ( In st itu te of Comm unicat ions Engineering, PLA U niv. of Sci. & T ech. , N an jing 210007, Ch ina) Abs tra c t: Since a skeleton p ixel shou ld be in the m iddle po in t of one of a pa ir ob ject boundary, based on the d iscu ssion of som e comm on ly u sed th inn ing a lgo rithm s, a fast th inn ing a lgo rithm based on m idpo in ts of m u lt i2o rien ta t ion slices w as pu t fo rw ard. T he experim en t resu lts show tha t th is a lgo rithm is robu st and p recise, and its runn ing t im e is sho rter than large d isc2based o r fit2unfit based th inn ing a lgo rithm. Ke y w o rds: im age p rocessing; sk leton; th inn ing; m idpo in t of m u lt i2o rien ta t ion slice 　　收稿日期: 2005201211. 作者简介: 曹铁勇 (1971- ) , 男, 博士, 副教授; 研究方向: 语 音、图像处理; Em ail: cty- ice@ 163. com. 1　图像细化 如何准确地从原图像中提取 (或识别)出待处理 的对象, 这是基于内容的图像检索研究当前所面临 的最大难题。而对象的提取 (或识别) , 需要其大量的 特征值的支持, 诸如直方图、纹理、轮廓、骨架等等。 细化是图像处理中的一种基本技术手段, 用于 抽取图像骨架, 提取图像的结构信息[ 1, 2 ]。对于由线 段或弧线等组成的窄条状几何对象来说, 骨架是一 个十分重要的特征, 能够用相对较少的像素表述对 象的整体结构, 同时还包含该对象的许多线性特征 信息, 如对象的位置, 整体方向、长度等。因此, 在诸 如指纹识别、文字识别等应用中, 细化是一个重要的 步骤。 常见的细化算法有几种方式, 其中较早的一种 来源于中轴函数M A F (m edia l ax is funct ion ) [ 1 ]。 M A F 方式将所有的边界像素点都视为一个波动产 生源。每个像素的波动都对其相邻像素点产生激励, 使得相邻像素点也产生波动。这种影响由近及远, 因 此所产生的波动在二值图像中传播开来。每个波动 都只影响某个像素点一次, 当 2 个这样的波相遇时, 他们之间相互抵消, 产生一个交点。中轴即位于交点 位置, 由此而产生出对象的骨架。 在M A F 方式中, 同时使用了时间和空间信息 来定义骨架, 并且可以按照骨架产生的过程反向合 成出原始图像。与此相似的还有“火种”细化方式[ 2 ]。 设想在 t= 0 的时刻, 将目标图像的边界各处同时点 燃, 火的前沿以匀速向目标内部蔓延, 当前沿相交时 火焰熄灭, 火焰熄灭点的集合就是目标图像的骨架。 以上 2 种算法的骨架抽取结果都能够较好地反 第 6 卷 第 5 期 2005 年 1 月 解 放 军 理 工 大 学 学 报 (自 然 科 学 版) Jou rna l of PLA U n iversity of Science and T echno logy V o l. 6 N o. 5 O ct. 2005 © 1995-2006 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 映出目标对象中的结构信息, 但是在按照这些方式 构建细化算法时, 会面对大量的计算困难。无论对于 火种方式或中轴方式, 其各点间的相互作用是随着 时间的推移而变化的, 在某点产生变化后, 其周围点 也会受到影响, 因此运算量很大。 数学形态学中与前两种相似的一种细化方式是采 用击中- 击不中原理(h it t ing2m issing based) [ 3, 4 ] , 对 对象进行层层“扒皮”, 逐步将其边界点删除, 直至留 下单像素宽度的线段或点为止。由于边界点的删除 是层层进行的, 因此细化过程中需对对象进行多次 操作, 计算量大, 在对“肥厚”的对象进行细化处理时 尤其明显。 以上细化算法除计算量大外, 对于边界噪声点 的影响也比较敏感。如图 1 所示, 当对象左下方边缘 存在噪声点的情况下, 利用击中- 击不中原理得到 的骨架走向发生变化。 图 1　基于击中—击不中方式的骨架抽取结果 F ig. 1　R esu lt of H 2M based sk leton ex tract ion 数学形态学中的另一种骨架抽取方式是基于最 大内切圆盘概念的 (b iggest2disc based) [ 2, 5 ] , 最大圆 盘完全落于目标图像内, 并且至少有 2 点与目标边 界轮廓相切。骨架的每一个点都对应于一个最大圆 盘的圆心和半径。这种方式抽取的骨架与前两种方 式相比大多数情况下是一致的。图 2 中为一个采用 图 2　基于最大圆盘方式的骨架抽取结果 F ig. 2　R esu lt of B 2D based skeleton ex tract ion 最大圆盘方式的骨架抽取结果。但是, 这种细化算法 面临着另外一种困难: 由于处理对象为数字化图像, 因此圆盘的构建, 特别是小圆盘的构建成为困难。有 些文献中利用方块或多边形来代替, 但这给相切的 检验带来了不便。 此外, 采用这种方式得到的骨架在顶端往往存 在分叉, 在结构上与人为感知的骨架之间存在着差 异。这些分叉导致骨架端点位置的变化, 对于如指纹 比对等需精确确定骨架端点位置的应用来说, 其影 响是十分不利的。 2　基于多向切片中点的细化 通过对骨架各种抽取方式的分析可以得出, 对 于一个连通域对象来说, 骨架应具备以下几个基本 特点[ 6, 7 ]: (1)对象的结构信息由其骨架保持; (2)骨架的拓扑结构为常数; (3) 一个骨架像素点应与至少一个其他骨架像 素点相连, 除非骨架中只有一个像素点; (4)骨架像素点应尽量远离对象的边界点; (5)通过对象边界的骨架垂直线, 在通过另一边界 前惟一地通过骨架, 除非该线过于靠近端点或拐点。 根据以上这些基本特点, 可以分析得出, 一个对 象的骨架至少在某个方向上应处于该方向对象边界 的中心点处。 对于如图 3 中所示的凸集图像 S 来说, 与骨架 K (S ) 垂直相交于点A 的直线同时与骨架的边界相 交, 产生 2 个交点B 和C , 此时A 位于线段B C 的中 点。从图中还可以看出, 因为A 是凸集 S 的几何中 心点, 因此A 也必然是通过A 点与骨架 K (S ) 成非 90°夹角的直线与边界相交形成的线段D E 的中点, 如图 3 所示。另外, 对于所有通过A 点的直线, 当其 方向与图形结构方向走势相同时, 此时其与凸集图 像间的相交线段最长 (凸集图像的长轴)。利用这种 特性, 可以判断该中心点周围凸集图像的骨架方向。 图 3　骨架点及相应的中点示意 F ig. 3　Skeleton and m iddle po in ts 但是, 对于骨架上的非几何中心点来说, 仅当通 过该点的直线与骨架垂直时, 该点才是所形成线段 024 解 放 军 理 工 大 学 学 报 (自 然 科 学 版)　　　　　　　　　　第 6 卷 © 1995-2006 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 的中点, 如图 3 中点A ′所示。另一方面, 对于不同位 置、不同方向的直线, 其与图像相交的线段中点未必 是位于骨架上的。如图 4 所示, 其中: 黑实线表示凸 集 S 的骨架, 虚线表示与骨架成 45°夹角直线相交 于图像边界所形成线段中点的轨迹, 点划线表示与 骨架成 135°夹角的直线相交于图像边界所形成线 段中点的轨迹。由图 4 可见, 当S 骨架上的点偏离几 何中心点A 越远, 其与中心点轨迹间距越大。当然, 随着凸集图形越接近扁平, 这种骨架与中心点轨迹 间的差距就越小。 图 4　骨架、切片中点集的位置示意 F ig. 4　Situat ion of skeleton and slice’s m iddle po in t track s 根据以上的特性, 可以从多方向对凸集图形进 行切片, 求取各切片的中心点, 据此确定部分骨架点 (这里称其为基本骨架点) , 以及该点骨架的走向, 并 对基本骨架点进行延伸, 以达到骨架抽取的目的。当 这种切片的宽度为一个像素时, 将得到连续的中心 点轨迹。当然, 实际处理的很少为凸集图像, 而根据 骨架的特性, 图像拐点或分叉点处的形状将对基本 骨架点的确定带来不利影响。因此算法中需针对这 点进行必要的处理。 为减少算法的复杂度, 本算法中只采取分别与 水平方向成 0°、45°、90°、135°夹角的 4 个方向交线进 行运算。 2. 1　边界点标记 设原始图像中的像素点 ( i, j ) , 当 p ( i, j ) = 0 时, 相应点为黑点; 当 p ( i, j ) = 1 时, 为白色背景 点。算法首先计算 q ( i, j ) : q ( i, j ) = p ( i, j ) 3 ∑i+ 1 m = i- 1 ∑ j+ 1 n= j - 1 p (m , n) , 若 0< q ( i, j ) < 9, 则说明该背景像素点周围至少邻接 了 1 个黑点, 此时该点被标注为边界点 x ( i, j )。边界 点的标定是为了方便算法在骨架延伸阶段的判断。 2. 2　多向切片中点求取 算法对图形对象进行多方向的宽度为 1 个像素 的切片, 记录切片所形成线段的中心点, 以确定基本 骨架点。同时分别记录各中心点各方向切片形成线 段的长度, 以用于确定骨架走向。为减少实际图像中 拐点或交叉点的影响, 将各方向切片中点的前后点 也同样标记为中点。 2. 3　基本骨架点提取 设图像中点 ( i, j ) 同时为 n 个方向交线的中点, 则令 z ( i, j ) = n。由于方向选择的有限, 这里 n< 5。 对于实际图像来说, 其拐点区域和交叉点区域中可 能不存在 z ( i, j ) = 4 的点。此外, 如果仅将 z ( i, j ) = 4 的像素点作为基本骨架点, 则由于其数量有限, 将 不利于后续骨架点的延伸。为克服这种不利因素, 本 算法中将所有 z ( i, j ) ≥3 的像素点都标记为候选基 本骨架点。由于在求取多向交线中点时, 真正中点的 前后点也被标记为中点, 因此此时得到的是图像内 部的几个候选基本骨架点连通区域。 对于每个候选基本骨架点连通区域, 求取最接近 其几何中心的候选基本骨架点作为基本骨架点。此 外, 离几何中心最远且分处几何中心 2 个相反方向的 2 个候选骨架点也将作为基本骨架点被标记出。 得到基本骨架点后, 其余骨架点采用延伸方法 求取。延伸方向按如下规则确定。 对于基本骨架点 ( i, j ) , 若 z ( i, j ) = 4, 则交线长 度最长的方向为该基本骨架点的延伸方向; 若其中 1 对垂直方向交线的长度相等, 则此时不相等的 1 对垂直方向中交线长度最大的方向为该基本骨架点 延伸方向; 若 2 对垂直方向交线的长度都相等, 则此 时该点将不延伸。 若 z ( i, j ) = 3, 则该点不属于中点的交线方向为 该基本骨架点的延伸方向。 2. 4　骨架延伸 仅仅依靠基本骨架点和延伸方向进行延伸是不 够的。这种单方向的延伸使得最后得到的骨架由线 段连接而成, 一条封闭曲线的骨架会变成多边形, 而 这显然对于需要依靠骨架信息得到对象精确结构信 息的应用来说是不可取的。 为解决这个问题, 作者对对象中的像素点 ( i, j ) 进行 z 值聚集处理: z k ( i, j ) = 19 ∑ 1 m = - 1 ∑ 1 n= - 1 z k- 1 ( i + m , j + n) , 其中: z k ( i, j ) 为第 k 次聚集后点 ( i, j ) 处的 z 值结 果。这种多次聚集的结果将使得中点聚集区中心区 域点的 z 值相对增大, 同时也将使得连通对象中的 不连通中点区域连通。 定义所有欲延长的端点队列。随后从队列中逐 124第 5 期　　　　　　　曹铁勇, 等: 基于多向切片中点的快速图像细化算法 © 1995-2006 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 个取出端点, 按延伸方向进行延长。以延长方向的下 一点为中心, 选取垂直于延长方向的 3 个邻接点作 为候选点, 其中具有最大 z 值的点为延伸点。将延伸 点加入骨架, 其延伸方向同该端点。新的骨架点若仍 满足可延伸的条件, 则加入端点队列中。 为从 P 点进行延长, 需满足 2 个条件: (1) P 点的 3 个延伸候选点中无边界点; (2) P 点必须为端点, P 点的 8 邻接点中必须要 有骨架像素点。 当延伸前端碰到边界或骨架中的其他部分时, 延伸进程停止。 当 2 个延伸线相交时, 交点到边界的延伸线应 删除, 如图 5 所示。 图 5　骨架延伸的删除 F ig. 5　D elet ing of skeleton ex tending 3　结果分析 为便于与其他算法进行比较, 采用本算法对图 1、2 中的图像进行了骨架抽取, 其结果与其他算法 的结果一起, 如图 6 所示。其中: 图 6 (a)为本算法运 算中的各点 z 值示意图; 图 6 (b) 为采用本算法得到 的骨架抽取结果; 图 6 (c) 为采用基于击中- 击不中 方式的骨架抽取结果; 图 6 (d) 为基于最大圆盘方式 的骨架抽取结果。 可以看到, 与图 6 (c)相比, 采用本算法所抽取的 骨架在左下角没有大幅度的拐弯, 较忠实地保存了 原图形对象的结构。这是由于本算法中各骨架点的 确定是通过对骨架点所在子区域附近边界点的综合 考虑而得到的, 因此其结果基本不受噪声影响, 即本 算法的稳健性明显强于基于击中- 击不中方式的骨 架抽取算法。 图 6 (d) 结果的骨架端点处存在分叉, 这对于需 利用骨架端点特征进行运算 (如指纹比对)的应用场 合十分不利。而这一点在本算法的结果图 6 (b)中不 存在。因此与基于最大圆盘方式相比, 本算法的结果 具有精确性。 图 6 (a) 的各点 z 值示意图中, 图形对象中灰度 越暗的像素点表示其 z 值越大。从中可以看出, 图像 交叉结构处和端点处的 z 值与主观认为的骨架线不 太相符, 这也导致所抽取的骨架在结构交叉部位有 轻微的扭曲。但在基本骨架点延伸阶段, 各延伸点的 主延伸方向不变, 因此端点处的延伸结果不会出现 大的偏离。 本文所述算法的另 2 个骨架抽取结果, 分别如 图 7、8 所示。其中所采用的图像分别为楷体汉字 “我”和二值指纹图像。从其结果中也可以看出本算 法抽取的骨架保持了原图形对象的结构。 本算法的另一大特点是运算速度快。对算法的 分析表明, 在多向切片中心求取阶段对图像中每个 点计算 4 次, 基本骨架点确定部分只需计算各切片 中心点的 z 值, 骨架延伸部分则只需根据前一骨架 点确定后一个骨架点。由于本算法的大部分计算都 无需考虑全部的图形对象像素点, 因此与前面所述 的几种细化算法相比, 其运算量大大减少。 采用M A TLAB 分别实现了本文提出的算法和 基于击中- 击不中原理的算法, 并在同一台计算机 上对 400 个汉字图形进行细化。统计结果表明, 本文 提出的算法运算时间为基于击中- 击不中原理算法 的 21. 3%。 图 6　各种细化算法结果 F ig. 6　R esu lt of differen t th inn ing algo rithm s 224 解 放 军 理 工 大 学 学 报 (自 然 科 学 版)　　　　　　　　　　第 6 卷 © 1995-2006 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 图 7　汉字细化结果 F ig. 7　R esu lt of Ch inese character th inn ing 图 8　指纹细化结果 F ig. 8　R esu lt of fingerp rin t th inn ing 　　通过对更多图形对象的运算结果分析表明, 本 算法计算类似图 7 对象的效率, 高于对类似图 8 对 象的运算, 其主要原因在于前者与后者相比, 骨架点 数目更少于对象的像素点, 因此算法后期所需的运 算量相对较少。 4　结　语 本文在对图像骨架定义进行探讨的基础上, 提 出了一种新的基于多向切片中点的图像细化算法。 对其结果分析表明, 这种算法具有稳健性、精确性和 计算量小的特点, 具有很强的实用性。该算法已在笔 者的基于纹理的图像检索和指纹特征提取中使用, 效果良好。 参考文献: [ 1 ]　BLUM H. A transfo rm ation fo r ex tract ing new descrip to rs of shape [A ]. Sympo sium M odels fo r Speech and V isual Fo rm , W eian t W haten2D unn Ed [C ]. Cam bridge :M IT P ress, M ass, 1967. [ 2 ]　崔　屹. 图像处理与分析—数学形态学方法及应用 [M ]. 北京: 科学出版社, 2000. [ 3 ]　A RCELL I C. Pattern th inn ing by con tou r tracing [ J ]. Compu ter Graph ics and Im age P rocessing, 1981, 17 (2) : 1302144. [ 4 ]　DAV IS E R , PLUMM ER A P N. T h inn ing algo rithm s: a crit ique and a new m ethodo logy [J ]. Pat tern R ecogn it ion, 1981, 14 (1) : 53263. [ 5 ]　JAN G B K, CH EN R T. A nalysis of th inn ing algo rithm s using athem atical mo rpho logy [J ]. IEEE T ransact ions on Pattern A nalysis and M ach ine In telligence, 1990 (PAM I212) : 5412551. [ 6 ]　SETA ST IAN T B , K IM IA B B. Curves vs skeletons in ob ject recogn it ion [ A ]. P roceedings of 16th In ternat ional Conference on Im age P rocessing [C ]. T hessalon ik i: IEEE Compu ter Society P ress, 2001. [ 7 ]　BECH ER S. D igita l skeletons in euclidean and geodesic spaces[J ]. Signal P rocess, 1994, 38 (1) : 1272 141. [ 8 ]　RUBER TO C D , D EM PST ER A G. A ttribu ted skeleton graph s using m athem atical mo rpho logy[J ]. E lectron L ett, 2001, 37 (27) : 132521327. [ 9 ]　曹铁勇, 杨吉斌. 基于势能平衡的图像骨架抽取算法 [J ]. 东南大学学报: 自然科学版, 2003, 33 (6) : 7242 727. [10 ]　RUBER TO C D. R ecogn it ion of shapes by attribu ted skeleta l graph s[J ]. Pat tern R ecogn it ion, 2004, 37 (1) , 21231. (责任编辑: 程　群) 324第 5 期　　　　　　　曹铁勇, 等: 基于多向切片中点的快速图像细化算法 © 1995-2006 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.