种子填充算法改进[权威资料]
种子填充算法改进
摘要:本文对种子填充算法进行了分析，提出了使用基于8-连通的射线扫描算法，减少了大量的种子点重复出栈入栈操作，节省了大量存储空间和存取时间。并改进了在填充中出现的填充溢出现象。经过实验验证，该算法能够快速填充给定的不规则区域，提高了填充效率。
关键词:区域填充 种子点 八连通 射线 不规则区域
TP391.41 A 1007-9416(2012)11-0135-02
常用的填充算法可分为两大类:扫描转换和种子填充。前者着重解决由多边形轮廓线所围的区域的填色问题。后者适用于任意形状轮廓线所围成的区域，但缺点是要求区域必须闭合且一次只能填充一个单连通区域。
种子填充法是区域填充的一种基本方法，其基本原理为:只要在某个区域内有一个已知像素，就能从此像素出发找到区域内所有其他像素，并对它们进行填充。根据区域的特性，种子填充法可分为4连通和8连通二种，分别是指从区域中某一像素出发，可以通过上、下、左、右四个方向或者上、下、左、右、左上、左下、右上、右下八个方向移动的组合，在不越出区域边界的前提下，达到区域内的任意像素。传统的种子填充法存在着占用空间多，效率不高以及对一些连通区域不能正确填充等缺陷，本文就种子填充8连通算法提出了改进。
1、简单种子填充算法
传统的边界填充算法，是选择或输入种子点坐标(x，y)、填充色和边界色。算法从(x，y)开始检测相邻位置是否是边界颜色，若不是就用填充色着色，并检测其相邻位置。该过程延续到已经检测完区域边界颜色范围内的所有像素为止。算法步骤如下[1]:
(1)种子像素入栈;
(2)执行如下三步:a)栈顶像素出栈;b)将出栈像素设置成填充色;c)检查出栈像素的8-邻接点，若其中某个像素不是边界色且未置成填充色，则把该像素入栈。
(3)检查栈是否为空，若栈非空重复步骤(2)，若栈为空则结束。
该填充算法过程是很简单的，可以在用户先勾画出图的轮廓，然后选择颜色和填充模式，然后在拾取种子点，系统会自动给图的内部填充所需要的颜色和图案，用途比较广泛。然而该算法需要很大的空间实现栈的结构用来存放种子点，并有大量种子进栈，有些像素甚至会入栈多次，降低了算法的效率。形式上最简捷的种子填充算法是基于递归的方法，但是这种方法没有考虑像素之间的关系，由于同一像素会重复入栈，造成内存溢出，程序崩溃。
1.1 一些改进的种子填充算法
填充算法在真实图形生成、图象处理、计算机艺术，高精度字体的显示等多种领域中有着重要的应用，因此目前有较多的种子填充算法的改进算法。
范慧琳等[2]提出了利用基本的y-x算法解决了复杂多边形的种子填充算法;陆玲[3]提出来利用种子设置填充色的顺序，改进了种子点重复入栈的问题;胡云等[4]利用给定的种子点产生一个新的种子点，然后利用双种子点进行填充提高了填充的效率，一定程度上避免了种子点的重复入栈。
1.2 改进算法的不足
但是不管那种改进算法，在程序实现时，都会在使用八连通种子填充算法时，因为填充区域的特点，出现填充区域溢出的现象。由于八连通填充的特点，会检测右上，左上，左下，左上四个点(也即1，3，5，7点)的颜色值，如图1所示。也即若2，8点是边界点，就会把区域外点1入栈，在填充时就会溢出，需要改进。
2、种子填充算法的改进
2.1 改进算法描述
确定填充区域边界颜色，选取种子点以及填充颜色。选取普通一维数组作为保存种子点坐标的栈。
算法步骤描述如下:
(1)检测种子点是否为边界点或已设置填充颜色;
(2)如果不是或没有，则设置种子点颜色为填充色，否则，检测栈是否为空，不为空则栈顶像素出栈，若为空则结束;
(3)种子点入栈(假设种子点坐标为(x，y));
(4)执行如下操作:a)检测栈是否为空，如不为空，栈顶像素出栈;否则，结束;b)检索种子点上、右上、右、右下、下、左下、左、左上八个方向的像素点是否边界点。如果全是边界点，则忽略，转至a)。否则执行c);c)按顺时针，设置不是边界点的各方向像素颜色为填充色。以这些点为射线起点，单方向递增，也即(如图1):如种子点1，坐标为(x-1，y+1)，在此方向上的下一点坐标为(x-2，y+2)，以此递增并设置填充色，直到边界点的前一像素点，此点入栈，编号为?(如图2所示)。逐次设置其他方向上的点，逐一入栈后，转至a)。
2.2 改进算法分析
改进的算法使用普通数组存储像素点坐标，数据结构上实现简单。在第一次种子点入栈产生新的种子点(最多8个)后，再按顺时针沿某个方向延伸填充，填充到边界点时停止产生第二批种子点，然后再以这个种子点向其它7个方向填充，因此最多需要的存储空间为8*7。在实际填充试验中需要的存储空间要远小于这个数值(约为1/2)。另外，由种子点向8个方向延伸填充，以及在种子点入栈前填充种子点颜色，避免了种子点大量重复入栈。
填充溢出问题。如1.1所述，8-连通区域的特点容易在填充过程中溢出。所以在算法步骤(1)和a)中增加了边界点2，4，6和8像素点是否边界点的检测，可以解决了8-连通填充溢出的问题。
3、结语
经过VC++6.0程序设计实现验证，改进的射线填充算法减少了种子点大量入栈，以及重复入栈的问题，使用了8向射线延伸填充，节省存储空间。增加了边界检测条件，防止了8-连通填充时溢出现象，提高了填充的准确性，防止程序崩溃。本算法在减
少存储空间，防止了填充溢出等方面进行了改进，优化了填充算法，提高了填充的效率。
参考文献
[1]陆枫，何云峰等.计算机图形学基础[M].北京:电子工业出版社，2012.6.
[2]范慧琳，张全伙.复杂多边形的填充算法[J].华侨大学学报，1996，17(1).
[3]陆玲.平面区域简单种子填充算法的改进[J].南华大学学报，2005，19(4)，11,13.
[4]胡云，李盘荣.一种改进的种子填充算法[J].安庆师范学院学报，2006，12(1):55,56.
[5]刘万春等.一种实时高速的八连通区域填充算法[J].计算机应用研究，2006(6):177,179.
阅读相关
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
总结文档:基于无线传感器网络的能量有效成簇算法研究 基于变换域离散小波变换音频水印算法研究 多脉冲激光测距信号处理技术研究 基于MPEG—4的视频水印算法研究 一种基于非监督判别语义特征提取的文本分类算法 电力系统自动化技术的研究与应用 一种提取印鉴方法的研究 红外拼接技术在电力设备检测中的应用 基于GPSGPRS的嵌入式终端系统的研究与实现 存在奇异值的非平稳谐波电流分析研究 企业电子商务发展与网络应用 计算机网络技术的应用及其发展 IT运维自动化技术在电力系统内的应用 基于WiFi的医院智能无线查房系统研究 导频污染及EVDO网络优化实例分析 三维GIS在水利工程信息管
*本文若侵犯了您的权益，请留言。*
【学术
论文
政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载
】【总结报告】 【演讲致辞】【领导讲话】 【心得体会】 【党建材料】 【常用范文】【论文中心】 【应用文档】 免费阅读下载
![种子填充算法改进[权威资料]](https://swf.iask.com/316XC1t3Odz.jpg?ssig=OzVsywbs8T&Expires=1719307138&KID=sina,ishare&range=0-337011)
浙公网安备 33021202002483