区域填充算法的探究

1、图形学期末作业区域填充算法的探究1摘要本文旨在通过探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与不足，对图形学的区域填充算法有更深入的理解。在准备本报告的同时还加以实验环节，选用扫描线填充算法和扫描线种子填充算法来对算法加以验证、调试和理解。2 区域填充基本知识点介绍2.1多边形扫描转换在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形

2、。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。多边形可分为凸多边形、凹多边形、含内环多边形。（1）凸多边形：任意两顶点间的连线均在多边形内。（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。（3）含内环多边形：多边形内包含有封闭多边形。扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为4个步骤。（1）求交：计算扫描线与

3、多边形各边的交点。（2）排序：把所有交点按x值递增顺序排序。（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。多边形扫描转换算法步骤如下：（1）初始化：构造边表。（2）对边表进行排序，构造活性边表。（3）对每条扫描线对应的活性边表中求交点。（4）判断交点类型，并两两配对。（5）对符合条件的交点之间用画线方式填充。（6）下一条扫描线，直至满足扫描结束条件。2.2区域填充算法这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图2-1所示。内

4、点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。 图2-1 区域的内点表示和边界表示 图2-2 4连通区域和8连通区域区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2-2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。2.2.1区域填充的扫描线算法算法的基本过程如下

5、：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 求出ymin ymax开始结束ymin yy+1 y求出由扫描线y确定的水平线与多边形两个交点（x1，y），（x2，y）将（x1，y）与（x2，y）连接y>ymaxNY图2-3扫描线填充算法流程图区域填充的扫描线算法可由下列3个步骤实现。Step1：求出每条水平扫描线与多边形各边的交点。Step2：将每条水平扫描线上的交点按X值递增的顺序排列。Step3：将交点的交点配成“交点对”。Step4：在交点对间填色

6、。2.2.2区域填充的种子算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。 a) 连通域及其内点 b)

7、填充四连通域 图2-4 四向连通填充算法一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2-4a所示的区域的内部，而四向连通填充算法只能完成如图2-4b的部分填充。3区域填充算法日新月异的发展 上面所提到的区域填充算法，扫描线算法和种子填充算法适用条件苛刻，要么对所要填充的多边形有一定的局限性，要么就是由于采用递归次数太多，区域内的每个像素都引起一次递归，即系统堆栈的一次进出操作，费时费内存。因而许多改进的算法便从减少递归的次数入手来提高算法的效率，区域填充的扫描线种子算法就是其中具有代表性的一个。3.1扫描线种子填充算

8、法3.1.1扫描线种子填充算法的基本思想首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。3.1.2扫描线种子填充算法实现步骤如下：1、初始化堆栈。2、种子压入堆栈。3、while（堆栈非空）(1)从堆栈弹出种子象素。(2)如果种子象素尚未填充，则： a.求出种子区段：xleft、xright;b.填充整个区段。c.检查相邻的上扫描线的xleftxxright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright

9、范围内的最右边的象素，作为新的种子象素依次压入堆栈。d.检查相邻的下扫描线的xleftxxright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleftxxright范围内的最右边的象素，作为新的种子象素依次压入堆栈。 3.1.3扫描线种子填充算法的特点1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。3、种子出栈时，则填充整个区段。4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆

10、栈空间，又可以实施快速填充。3.2基于扫描线种子填充算法的改进 由3.1的描述可以看出，对种子所在扫描线的填充与搜索新种子点的操作是分别进行的，这就需要对大量的像素进行重复判读。为了对当前的扫描线填充和搜索新种子像素，需要对当前扫描线以及其相邻的上下扫描线等3条扫描线进行扫描，这就使得多数扫描线被重复扫描，即使该扫描线上的像素已经全部填充也要被再次扫描。甚至扫描3次，大大降低了程序的效率和运行速度。另外，在该算法中堆栈操作频繁，每搜到一个新的填充区间就要入栈，对每一条扫描线至少有一个区间入栈每次开始另一条扫描线搜索都要先出栈，这不仅占用了大量的储存空间，还降低了算法的效率。针对重复扫描的问题，

11、文献【1】根据当前扫描线与相邻扫描线间的位置关系以及区间端点的坐标大小减少了不必要的重复扫描，缩小了重复扫描区间范围，但是所提出的算法仍然将填充与搜索新种子点的操作分别进行，没有克服堆栈频繁操作的缺点，文献【2】将种子点入栈改为新旧区间端点入栈，并将区间填充与搜索新区间合并进行，进一步减少了重复扫描但是算法中并没有减少堆栈操作的频率，并且对每一条当前扫描线都要判断其相邻的两条扫描线是否需要重复扫描【3】。针对传统区域填充的一些欠缺，文献【4】提出了一种新的区域填充扫描线算法。该算法在处理同一条扫描线上的多个填充区域时，分成向上搜索和向下搜索两种情况进行，每种情况又都可能出现多个搜索新区；在填充

12、过程中，考虑到当前区间左右连续性和上下相关性，只需将出现的新搜索区压入堆栈，不需要将相邻的每根扫描线都压入堆栈，从而减少了像素的重复判读和会回溯区的搜索时间，避免了不必要的进出栈处理，提高了填充效率。为了存储对每个新区进行搜索的起始位置，定义一个栈用以存放其信息，存储结构如下：Typedf Struct Stack_nodeInt xleft;/左边界X坐标Int xright;/ 右边界X坐标Int yscan;/扫描线Y坐标Int direction;/搜索方向Struct Stack_node *next；*Link_Stack;Link_Stack S; 新区入栈的区域填充扫描算法的步

13、骤：Step1:对存储新区信息的堆栈进行初始化；Step2：给定填充区域内一点作为种子点，左搜索左填充，得到左边界xl；右搜索右填充，得到右边界xr ； 将向上搜索的起始信息（xl，xr，y，1）；右搜索右填充得到起始信息（xl，xr，y，-1）分别压入堆栈。Step3：若栈空，则填充过程完成，程序结束；否则，执行以下步骤。Step4：判断当前的搜索过程是在主搜索区还是在新区，若在新区，则将栈顶元素出栈，并将出栈信息作为新区的起始搜索信息；若在主搜索区，则将上次搜索的结果作为对下条扫描线进行填充的信息；Step5：判断当前搜索点是否已经达到该扫描线区域的最右端，若是转Step8，否则，执行以下

14、步骤；Step6：若当前搜索点时区域内的一点，并且未填充，则以其为种子点，左搜索左填充，得到左边界xl；右搜索右填充得到右边界xr；Step7：若找到的第一个可填充区域，则记录下该区的左右边界；若找到多个可填充区域，则将除了第一个以外的其他区压入堆栈；Step8：将向上搜索过程中可能出现的下回溯区和向下搜索过程中可能出现的上回溯区作为搜索新区分别入栈；然后转Step3【4】。3.3 一种基于链队列的种子填充法文献【5】提出了递归种子算法的改进算法，在该算法中使用链队列而不是递归，而且采用先填充后入队列，减少了很多不必要的操作，使得改进后的算法无论是时间还是空间效率都远远优于递归种子填充算法，而

15、且也可以填充任意大小、任意复杂边界的区域。3.3.1 种子算法的改进之一 算法基本思想思路是：从链队列中获得一个像素点，判断其四连通像素点，若没有填充，则填充它，并将它入队列，如此循环，直到队列空为止。对递归种子填充算法的改进之处为： 在递归种子填充算法中堆栈是系统预先设定的，其大小和存储区域已经确定，这对填充的区域大小有明显的限制，当堆栈溢出时，程序就会出错，若堆栈设定很大，又会导致在填充区域不大的情况下，浪费了很多计算机资源，本算法不使用递归，而使用链队列，是因为链队列有两个特点：一是当链队列为空时，它不占用存储空间，只有当数据入链队列时才分配存储空间给它。二是由于在定义链队列前没有限定它

16、的大小，所以从理论上看，有多大的可使用存储空间，就可以建立多大的链队列。 在递归种子填充算法中，采用的是先入栈，出栈后再填充，即当填充某像素点时，不管它的四连通点是否已被填充，都要进入堆栈，这会导致很多的冗余像素点入栈，而本文算法采用的是先填充再入链队列，在入队列之前要判断像素点是否已被填充 若已被填充才入队列 否则不予考虑。这样将会减少入队列的冗余像素，即每一个像素点只入队列一次。3.3.2 种子算法的改进之二 以上算法的改进克服了递归种子填充算法由于一个像素点重复入栈操作而导致速度很慢的问题，但经过研究发现以上改进之后，仍存在很多冗余的检测。如图3-1所示，当像素P出队列时，要检测像素1，

17、3，5，7的颜色是否是填充色或边界色。而当像素1出队列时显然P像素已经被填充，而仍要检测像素P的颜色。同理，当像素3，5，7出队列时分别也要检测像素P的颜色，这样也会浪费一些时间。所以我们在改进一的基础上进一步提出改进二的算法。改进的思路是这样的，设置4个链队列分别记录向上、向下、向左、向右4个方向的填充新种子像素点.若当正在出队的像素点是来自于记录向上的那个队列，不要检测它的下面那个像素点，则在处理某个像素点时只要检测3个连通像素点。这里设置了4个链队列，是否增加了程序的存储开销呢？答案是否定的。因为采用的是链队列，只有当像素入队列时才会占用存储空间。经过对程序的测试可得，第一次改进时，每个

18、像素只入队列一次，同样设4个链队列，每个像素点也只入一次队列，所以总的入队列次数是一样的【5】。图3-2 第一次改进后的像素监测 4程序运行调试作为本次区域填充算法探究的实践部分我选择扫描线种子填充算法和扫描线算法进行调试观测，经过查阅纸质资料、互联网相关内容以及朋友的协助下，最终调试运行成功。5结束语通过查阅大量的图形学区域填充相关资料，总结了近年来在区域填充方面一些算法，并且阐述各自的优劣。分别以扫描线种子填充算法和种子填充算法两条主线探究图形学方面的专家逐步改善区域填充算法提高算法效率的过程。经过近三周的对区域填充算法的进一步学习、整理和总结，更加熟悉了算法本身以及大家一直在试图改善算法的入手点。在整个准备的过程中既有自己的努力，也有他人的帮助，感谢老师本学期给我的指导，同时也感谢两位师兄，他们在