收稿日期：!“#$“#$“%；修返日期：!“#$“%$!?52 0?6A5B7C DA E5?56 ($=:F=B G2 0A2=HIJ K=$，HIJ M5=$FL，N4J OL$32，G4P1 Q5=$（!“#$% H52 0?6A5B7C；;22: .5B；4567$8922:!) 引言区域填充算法是一种将区别于背景颜色的具有连通性的前景颜色全部填充为填充颜色的算法。区域填充的方法在计算机图形图像学中是一种基本而又重要的操作， 在计算机辅助设计、 交互式图形设计、 动画、 图像处理等实际领域中有着广泛的应用， 其填充结果的完备性和填充过程的高效高速是区域填充算法的度量标准。传统的填充算法大致可以分为奇偶性检测和种子填充两大类别。奇偶性检测算法的基本思想是 “一条直线与任何一条封闭曲线 （一个连通区域的轮廓） 相交偶数次” ， 每一对交点都代表了扫描线穿过区域的一个区间； 这种算法的缺点在于首先要求取区域轮廓线， 且实际情况中并非 “一直线与轮廓必相交偶数次” ， 在填充时必须考虑水平边界和局部极值点的问题， 要达到结果的完备性需要复杂的控制策略， 在对轮廓线进行各种标注的前提下再施行填充 （称为边标志算法） ， 所需轮廓标注数据的存储空间近似等于原区域存储空间， 在时间和空间上损失了算法的效率 （在轮廓线已被求取的情况下， 此算法损失的效率稍有改善） 。种子填充则是指定一个区域内部的点作为种子， 然后以该像素为起点蔓延至区域内所有像素（E?: E5?） ； 此算法无需事先求取轮廓也无需求取交点并排序， 而是需要有一个区域内的种子点， 此种子点可以位于区域的任意位置， 尤其对于一些目标查找或模板匹配的领域， 种子点容易获取， 算法效率较高。其缺点是种子填充时需要频繁地对种子实施出入栈操作且有可能造成区域内像素的重复访问。针对这种传统的种子填充算法的缺陷， 扫描线种子填充算法进一步发现堆栈内包含的一些重复的和不必要的信息， 在不间断的扫描线区段内只取一个种子， 一定程度上改善了种子填充算法的效率， 但是经典算法仍然存在上述的问题。扫描线种子填充算法已经被广泛应用， 不仅在计算机辅助设计和图像处理方面， 在一些对算法速度要求很高的视频流处理和工业自动化方面也有很多例子， 这些地方对于算法的实时性要求强烈， 在数据量已经很大的情况下， 算法的实现速度是一个很现实的问题。不少学者对算法进行了完备性和高效高速上的研究， 提出了一些很有价值的改进算法。其中有的改进算法!， 算法的改进#!， “ ， 此像素若为区域内像素则将其填充， 若仍非区域内像素才认为已经到达边界， 对于 !%$， “ 施以同样的思路， 要考察其右侧的 !%$?!， “ 是否为区域内像素才可以下结论。在当前扫描线上的区段填充完毕之后要进行上下相邻扫描线的入栈和回溯， 为了避免重复的回溯， 要考察当前扫描线“ 上求得的区段端点 !#， !$ 和其种子区段端点 !%#， !%$ 的关系。对于四连通区域， 若新的区段端点只比原区段多出一个像素 （如图 “ （/） ， !#!%# !） 则认为无须回溯； 若新的区段端点 比原区段多出超过一个像素 （如图 “ （/） ， !$ !%$?!） 则认为必须回溯， 做法是将多出来的区段重新以纵坐标 “%压入堆栈。对于八连通区域， 若新的区段端点只比原区段多出一个像素的时候 （如图 “ （=） ， !#A !%#） 就认为必须进行回溯， 将只含一个像素的区段 !#， !# ， “%压入堆栈； 若新区段端点比原区段多出超过一个像素就更加有必要做与四连通情况一样的回溯操作。# =3； +A%A B !“#$%在填充过程中,根据相邻扫描线上填充区间的关系判断是否需要回溯和产生新 的填充区间,有效避免了不必要的回溯和像素的重复判读.提高了填充效率.3.期刊论文 刘相滨.胡峰松.张邦基 一种新的区域种子填充算法 -计算机工程与应用2002,38(8)在未知边界的区域种子填充算法中,改进扫描线算法1具有非常高的填充效率,但它只适用于四连通区域,为此,文章提出了一种新的基于边界跟踪的填充 算法,该算法弥补了文献1算法的不足,可以填充任意的四连通或八连通区域,而在填充效率上仅比其略低几个百分点,因此更具有实际应用性.引证文献(1条)引证文献(1条)1.金永.王召巴 浮法玻璃带缺陷自动检测技术研究期刊论文-传感器与微系统 2008(12)本文链接：http:/d.g.wanfangdata.com.cn/Periodical_jsjyyyj200606058.aspx 授权使用：武汉大学(whdx)，授权号：1b511d38-a8d0-4478-9fdc-9e3401885cdd 下载时间：2010年11月20日