一种基于缝隙码的区域填充算法

第 12卷 第 11期 2007年 11月 中国图象图形学报 Journal of Image and Graphics Vol_12．No．11 NOV．。2007 一 种基于缝隙码的区域填充算法 陈优广 顾 国庆 王 玲 (华东师范大学信息科学技术学院，上海 200062) 摘 要 提出了一种基于缝隙码的区域填充算法。给出了单条缝隙码的填充算法 ，及多连通区域或整幅图像的快 速填充算法 ，能填充任意复杂图像区域，对多连通区域或整幅图像填充时，算法只对图像区域填充，不用对区域外 或区域内部的孔洞进行填充，对非二值图像 ，该算法不需要辅助内存空间。实验结果表明，对比现有的算法，本文 算法具有速度快、效率高等优点。 关键词 缝隙码 区域填充 填充算法 中图法分类号 ：TP391．41 文献标识码 ：A 文章编号 ：1006—8961(2007)11-2086-07 A RegiOn Filling Algorithm Based on Crack Chain Code Description CHEN You—guang，GU Guo—qing，WANG Ling (School of Information Science and Technology，East China Normal University，Shanghai 200062) Abstract The paper proposed a region filling algorithm based on crack chain code description． The algorithm of single crack chain code and a fast filling algorithm about the complicated connecting region or the global image are given，in which only the image regions is filled． Compared with the conventional algorithms，this algorithm requires no storage and works well for any complex regions．Experimental results prove that it is faster and more efficacious． Keywords crack chain code，region filling，filling algorithm 1 引 言 区域填充是计算机图形学的基本问题之一。基 于链码的填充是图像图形处理的基本算法，且广泛 应用于图像处理、目标分析、图像压缩及计算机图形 学中。因此区域填充一直是人们研究的热点。 传统的填充算法主要有奇偶性检测 ¨和种子 填充 两大类。种子填充的缺点是需要栈结构， 因而需要较大的存储空间以实现栈结构 ，而且在有 多个对象需要填充时，种子点的逐个选取会降低效 率，在某些复杂情况下，种子点的选择非常困难；在 奇偶检测法中，由于交叉点可能为多重交点，会导致 在统计交叉点数目时，容易出现错误，而且水平直线 状的边缘线也会导致错误判断。 链码最 早 是 由 Freeman提 出，分 为 4方 向 Freeman链码和 8方向 Freeman链码 ，随着链码的广 泛应用，很多文献提出了当轮廓是以链码形式给出时 的填充算法 ，且它们都能取得比传统算法正确 而快速的填充结果，分析被填充区域轮廓的8方向链 码编码属性，并将轮廓点分成孤立点、标志点和忽略 点、不存在点，从而很好地解决了删除孤立点或将一 个孤立点当作两个点的问题，这样就能避免产生错 误的线段编号，从而取得正确的填充结果。 Chang等人设计 了一 种从 光栅表示到 Freeman 缝隙码表示的算法 ¨，本文简称之为缝隙码。它不 同于4方向Freeman链码，Freeman缝隙码记录区域 边界像素边的 4方向码值。虽然 Freeman链码与 Freeman缝隙码可以相互转换 ，但是把缝隙码转 换为 Freeman链码还是需要花费时 间，所 以研究基 于缝隙码的填充算法有理论意义和实用价值的。为 此给出了一种基于缝隙码的区域填充算法，给出单 收稿日期：2006-06-30；改回日期：2006-08-22 第一作者简介：陈优广(1971一 )，男 ，讲师。华东师范大学信息科学技术学院系统分析与集成专业博士研究生。主要研究方向为图像 处理与模式识别。E-mail：ygehen@cc．eenu．edu．cn 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 第 11期 陈优广 等 ：一种基于缝 隙码的区域填充算法 条缝隙码的填充算法，及多连通区域或整幅图像的 快速填充算法 ，算法能 自动选取种子。对 比现有 的 算法 ，该算法不需要辅助内存空间 ，能填充任意复杂 图像区域，尤其对多连通区域或整幅图像的填充时， 不存在孔洞的重复填充问题。实验结果表明，本文 算法具有速度快 、容易实现等优点。 2 现有的基于链码的填充算法分析 CAI最早给出了利用链码进行填充的算法，提 出了对轮廓点按链码属性进行分类，来解决奇偶性 填充算法存在的问题 ，算法用到了一个与图像等 大的辅助内存，需要扫描图像中的每一个像素点。 后来 Chang和 Frank提 出了一 种快速 、低 内存消耗 的算法 ，算法较 CAI算法提高了效率，然而其需 用一个表来记录孤立点和标记点，对表的排序花费 了大量 的时间。Tang则给 出离散格伦定理 ¨和基 于此定理的填充算法 ，通过计算从某一点 出发 的 整条轮廓线的积分，来判断该点是否是区域内部点， 令像素 t的坐标为(x ，Y )，那么判断 t在区域内部 或外部的计算 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 如下： △( P— ，Yp—Y )X sign( P，YP) E L r0 ( ，Y )在区域的外部 【1 ( ，Y )在区域的内部 其中，L是边界点的有序集合。符号函数 sign( ，Y) 根据点( ，Y)的进出链码，其取值 由表 1给出，其 中，一1表 示左 端 点 ，1表 示 右端 点。△( ，Y)= 耵 二IJ 。 ng采用 的是种子填充算 法 ，需要很大的计算量 。 Ren给出了一种把链码分解成简单子链的填充 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，为了解决 由于轮廓不连续光滑造 成的一些 点被跟踪多次的问题 ，该算法把链码分解成多条简 单子链 ，通过简单子链 的填充给出了整条链 的填充 算法，但算法没有给出区域内轮廓的填充算法，也无 法同时填充多条轮廓。 Ren最 近 又 给 出 了 一 种 新 的 快 速 的 基 于 Freeman链码的填充算法 ，并在该文中对前 4种 方法的不足给出详尽描述，它提出了一种新的自动 选取种子的方法，通过统计进出轮廓点的链码的纵 坐标和来判断该点是填充起点、终点或是跳过点。 用 sum表示进 出轮廓点的链码 的纵坐标和。当 表 1 TANG 左右端点表 Tab．1 TANG — — LUT Ci+1 0 l 2 3 4 5 6 7 sum>0时，轮廓点为填充起点；当 sum<0时，轮廓 点为填充终点；当 sum；0时，轮廓点为填充跳过 点。该方法把种子填充 和奇偶填 充相结合 ，其 思想 是发现种子 ，按奇偶填充法进行填充 ，对每条链码 的 填充，算法复杂度为 a+0(n)，其中，a为图像区域 面积，n为图像边界的长度。目前为止文献[10]中 Ren的算法是最优的。 但是 Ren的算法在对 多连通 区域 的填充时 ，存 在对洞的重复填充 问题 ，导致时间的浪费 ，影响了效 率，如图 1所示。 图 1 多连通 区域 Fig．1 Complicated connecting region 令 ／7,。、a 表示区域的外边界和区域面积，／7, 、n 表示区域的内边界和洞的面积，那么利用 Ren的算 法，需要分别对区域的外边界和内边界填充，对每一 条区域边界 ，Ren的算法要遍历边界点 4遍 ，区域点 一 遍 ，如 图 1所示 ，需要填充的点为 4n1+a1+a2+4n2+a2=4(／7,1+／7,2)+a1+2a2 本文给出了一种基 于缝 隙码 的填充算法 ，针对 多连 通区域或整幅图像的填充时，给出了只需对图像区 O O × O 一 一 一 一一 _ _ _ i x × O O 一 一 一 二 伯 × O O O 一 一 一 一一 l l l l O O × O 一 # l l l l × × 0 D 一 碉 O O × × 一 一 一 一一 ” ㈡ 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 2088 中国图象图形学报 第 12卷 域像素填充的快速算法，不需要对区域外 (包括孔 洞)像素进行填充，算法很好地解决了多连通区域 洞的重复填充问题。 3 区域边界的缝隙码表示及其性质 按逆时针或顺时针方向沿着图像边界像素的边 行走一周，依次记录其方向码，就得到图像边界的缝 隙码，加上起始点坐标，边界就可以用缝隙码唯一确 定下来。除非特殊说明，本文给出的缝隙码都是按 逆时针方向行走 的。 如图2所示，像素顶点坐标在 u． 坐标系取值 为整数，像素坐标在 ．Y坐标系下取整数，u一 坐标 系可由 Y坐标系向左向上平移半个像素获得。图 2所示的区域边界 的缝隙码 可表示为 {(u。， ) 3232323O3OO3OO1OO101 t2123221 12}。(u0， )是 区 域边界像素的顶点P在 “． 坐标系下的坐标。 J 1 2 0 ， r 3 图2 4方向码与区域轮廓的缝隙码 Fig．2 Four directions code and crack code of contour 缝隙码记录的是封闭的区域边界的 4方向码序 列，令 ．s。、．s 、．s：、．s，分别表示缝隙码中码值为 0、1、 2、3的个数，那么有 S。=S：，S =S，。由区域边界的 连通性原理 ，有以下性质成立。 性质 用水平直线与区域边界相交，令 与 分别表示水平直线与区域边界缝隙码相交的码 值为 1和3的个数，那么有 M =M，，且方向码 1和 方向码 3是交互出现的。 与 Freeman链码不同，缝隙码记录的是经过边界 像素边的方向码，起始点为边界像素的顶点。表 2定 表 2 坐标偏移表 OFFSET—LUT Tab．2 OFFSET — LUT C 0 1 2 3 注：C为缝隙码，du、山 为 C从当前位景迁移到下一个位置的坐 标增量 。 义了像素顶点坐标随方向码变化的坐标偏移量。 已知起始点和缝隙码，根据表 2给出的坐标偏 移表 OFFSET—LUT，可以很容易获得区域边界像素 顶点坐标。像素坐标值与其左上顶点在 u一 坐标系 下的坐标相等。令( ，Y)为边界像素坐标，(u， )为 该像素的一个顶点坐标，e为以(u， )为始点的方向 码，那么像素坐标( ，Y)与(u， )和方向码 e的关系 ( ，Y)= u， ，e)如下 ： 当 e=0时 ，( ， )=(“， 一1) 当 e=1时 ，( ，Y)=(u一1， 一1) 当 e=2时 ，( ，Y)=(u一1， ) 当 e=3时 ，( ，Y)=(u， ) 缝隙码表示的边界轮廓可以看作是一个多边形，其 角度变化可由表 3给出。 表 3 链码角度变化表 Angle—LUT(A) Tab．3 Angle — LUT(A) 0 — 90 × 90 90 0 — 90 × × 90 0 — 90 — 90 × 90 0 令 n一1 ．s =A[Cn-1][c。]+∑A[c ][c ] 其中，A[i][ ]由表 3给出。 如果 S =360，那么轮廓为区域外边界，否则轮 廓为内边界。 4 基于缝隙码的区域填充 只考虑经过边界像素的左右边的方向码。那么 有 3种可能 ，如图3。 定义 若像素的左边有方向码 3经过且其右边 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 第 11期 陈优广等：一种基于缝隙码的区域填充算法 l圈 圈1 l圈1 图3 边界像素与左右缝隙码的 3种位置关系 Fig．3 Three types of position of crack code and contour pixel 没有方向码经过，称该像素为 L一像素，若像素的右 边有方向码 1经过且其左边没有方向码经过，称该 像素为 R一像素，若边界像素的左右两边都有方向 码经过，那么称像素为 LR一像素。如图3所示，标记 L的为 L_像素，标记 R的为 R一像素，标记 LR的为 LR 一 像素。 令 P( ，Y)为区域边界上的像素点，c 为经过 该像素某边的方向码。 If c =3 then点 P为 L_像素 If c =1 then点 P为 R一像素 If点 P为 L_像素 and点 P为 R一像素 then点 P为 LR一像素。 定理 1 用一水平直线与区域边界相交，那么 水平直线与区域边界相交的 L一像素和 R一像素个数 相等，且 L_像素和 R一像素相互间隔出现。 证明 用水平直线与区域边界相交，由性质，缝 隙码与该直线相交的方向码 1和方向码 3的个数相 同，且是交互出现的，由定义 1，除去 LR一像素，剩下 的方向码 1和方向码 3就分别对应着边界的 L一像 素和 R一像素，且交互出现。 如图4所示，虚线与区域边界相交的 L_像素与 R 一 像素个数相等，且交互出现。 由定理 1，L一像素可以看作填充种子点，L一像 素和 R一像素又满足奇偶填充原理。对于单条缝隙 码的填充算法可以描述为：首先遍历缝隙码，确定边 界的L一像素和 R一像素，并计算围线角度，确定围线 方向；然后对所有的L一像素，作为填充起始点，对区 域外边界，从左向右填充，对区域内边界从右向左填 充，直到 R一像素结束；最后填充边界像素。算法需 要扫描边界像素顶点3遍，区域内部点一遍。 定义围线缝隙码类 ： struct Crackchain{ int U。，v。； ／／缝隙码的起始点 long n； ／／缝隙码的长 int％e； ／／缝隙码 } 算法 1：单链的填充 samp1eChainFill(img，W，h，ck，co1) 图4 单条轮廓的左右边界像素示意图 Fig．4 A demo of left and right pixel of single contour 其中，img为填充图像，w和 h分别为图像的宽和 高，ck为缝隙码类 ，col为填充色。 (1)用 1，r，lr分别表示边界上的 L_像素、R一像 素和 LR一像素，定义中间变量，并初始化。用 ．s 来 统计链码角度变化，S =0。 (2)遍历链码，标记边界的左右像素，并判断其 围线方 向 U=ck．u0；v=ck．vO； pc=ck．e[n一1]； for(i=0；i0)fig=1；else fig：一1； 这里 fig=1时，边界为区域外边界，否则为内边 界。A[ ][_『]的值由表3给出，函数(x，Y)=func(u， 维普资讯 http://www.cqvip.com http://www.lw23.com ??? ???? http://www.lw23.com ??? ???? 2090 中国图象图形学报 第 l2卷 v，nc)见 3节定义 ，以下同。 (3)填充区域内部像素 U=ck．u0；v=ck．v0； for(i=0；i