区域填充算法的研究

本文由天空乐园大学生旅游网整理分享

摘要

区域填充算法是计算机图形学的一个重要研究课题．传统的区域填充算法存在填充结果不完备及算法效率不高的问题，在分析了两种传统区域填充算法的原理的基础上，详细阐述了四种改进的区域填充算法，并对算法的效率性能进行比较分析，指明了区域填充算法未来的研究热点，着重探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与足，对图形学的区域填充算法有更深入的理解介绍种子填充算法及其改进算法。 关键词：区域填充；填充算法；扫描线算法；种子填充算法

1 引言

区域填充是指用不同的颜色、灰度、线条或符号填充一个有界区域，该区域可以是带孔的，也可以是不带孔的．它是计算机图形学的一项重要内容，在交互式图形设计、真实感图形显示、计算机辅助设计、图形分析等领域有着广泛的应用，一直是研究的热点．传统的区域填充算法有两种，一种是通过确定横跨区域的扫描线的覆盖间隔来填充的扫描线算法，另一种是从给定的位置开始填充直到指定的边界为止的种子填充算法．扫描线算法主要用来填充比较简单的标准多边形区域，比如圆、椭圆以及其他一些简单的多边形，它对轮廓线的形状有一定的要求，在处理复杂区域时往往失效．种子填充算法可以解决边界比较复的多边形区域填充问题，它必须首先确定一个或者多个区域内部的点作为种子点，并赋予填充色，然后以该点为起点，用四向连通方法或八向连通方法找到区域内的所有点填充。扫描线算法在处理带水平边的凹拐点时不能正确填充，这是该算法的一个突出问题，但由于利用了扫描线上象素之问的连贯性，因此具有较高的效率．最简单直观的种子填充算法采用递归方法，由于进行大量的出入栈操作，因此效率很低，在填充较大的区域时，要求分配较大的堆栈空问，不仅浪费了内存，也可能出现堆栈溢出现象．填充结果的完备性和填充过程的高效高速是区域填充算法的度量标准．在传统区域填充算法的基础上，很多文献提出了更加正确高效的算法．本文介绍四种改进的区域填充算法，并对其进行比较分析。

2 区域填充基本知识点介绍

2.1多边形扫描转换

在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。

多边形可分为凸多边形、凹多边形、含内环多边形。 （1）凸多边形：任意两顶点间的连线均在多边形内。

（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。 （3）含内环多边形：多边形内包含有封闭多边形。

扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为4个步骤。 （1）求交：计算扫描线与多边形各边的交点。 （2）排序：把所有交点按x值递增顺序排序。

（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。

（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。

多边形扫描转换算法步骤如下：

1

（1）初始化：构造边表。

（2）对边表进行排序，构造活性边表。

（3）对每条扫描线对应的活性边表中求交点。 （4）判断交点类型，并两两配对。

（5）对符合条件的交点之间用画线方式填充。 （6）下一条扫描线，直至满足扫描结束条件。

2.2区域填充算法

这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图1所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。

○表示边界点●表示内点

图1 区域的内点表示和边界表示 图2 4连通区域和8连通区域

区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。 2.2.1区域填充的扫描线算法

扫描线算法是按照扫描线顺序，计算扫描线与多边形的相交区间，再用颜色显示这个区间，区间的端点则是扫描线与多边形边界线的交点，可以通过计算获得．要完成这个扫描转换过程，首先计算扫描线与多边形各边的交点，然后对求得的交点进行排序，接下来利用奇偶配对求出扫描线与边形的相交区间，最后对这些相交区问填色．由于扫描线是一组连续的水平平行的直线，因此在计算其与多边形的交点时较容易，因为交点的纵坐标已知，即扫描线的编号，则可根据多边形的数学表达式求出交点的横坐标．对交点进行排序时采用横坐标由小到大的顺序，便于相交区间的确定．对于已经排序的交点，使用奇偶配对法确定相交区间，如：交点a。与交点a2为一对，交点a。与交点a4为一对，代表直线ala2和a3a4是扫描线与多边形的相交区间，al-,a2、a。、a4是相交区间的各端点．填充时则可以直接用填充色将相交区问的各端点连接．

扫描线算法采用邻接链表的数据结构，每条扫描线在该表中都对应有一项，利用初始边表OET与活动边表AET记录扫描线与多边形相交的情况．该算法效率较高，但填充结果的完备性不好，在处理复杂区域时，往往不能正确填充．

算法的基本过程如下：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

2

图3扫描线填充算法流程图

区域填充的扫描线算法可由下列3个步骤实现。 Step1：求出每条水平扫描线与多边形各边的交点。

Step2：将每条水平扫描线上的交点按X值递增的顺序排列。 Step3：将交点的交点配成“交点对”。 Step4：在交点对间填色。 2.2.2区域填充的种子算法

种子填充算法又称为边界填充算法。其基本思想是：种子填充算法是从多边形区域内部的一点开始，由此出发找到区域内的所有像素．该算法采用的边界定义是：区域边界上所有像素均具有某个特定的颜色值；区域内部所有像素均不取这一特定颜色；而边界外的像素则可具有与边界相同的颜色值．根据边界定义，算法从多边形区域内部的一个像素点开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点．然后检测相邻位置的各个像素点，以确定它们是否与边界色和填充色均相同，若不相同，就填充该相邻点．这个过程持续到已经检测完区边界范围内的所有像素点为止．

从当前点检测相邻像素有4向连通和8向连通两种方法．4向连通方法指的是从区域上一点出发，可通过上、下、左、右4个方向的移动，在不越出区域的前提下，到达区域内的任意像素点；8向连通方法则可以通过左、右、上、下、左上、右上、左下、右下这8个方向的移动来到达．

种子填充算法简单，易于实现，可以处理复杂区域的填充问题，填充结果的完备性较好．但是这种算法需要很大的存储空间以实现栈结构，同一个像素多次人栈和出栈，所花费的时间也很多，导致算法效率不高

种子填充算法常用四连通域和八连通域技术进行填充操作。

3

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。 从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

a) 连通域及其内点 b) 填充四连通域

图4 四向连通填充算法

一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图4(a)所示的区域的内部，而四向连通填充算法只能完成如图4(b)的部分填充。

3 区域填充算法日新月异的发展

上面所提到的区域填充算法，扫描线算法和种子填充算法适用条件苛刻，要么对所要填充的多边形有一定的局限性，要么就是由于采用递归次数太多，区域内的每个像素都引起一次递归，即系统堆栈的一次进出操作，费时费内存。因而许多改进的算法便从减少递归的次数入手来提高算法的效率。下面介绍几种改进的区域填充算法

3.1复杂连通区域的扫描线填充算法

传统的扫描线算法不能处理复杂连通区域的填充，文献[1]基于扫描线算法的原理，提出一种能够处理复杂连通区域的扫描线填充算法，该算法通过分析水平扫描线与复杂连通区域轮廓线相交的各种可能情况，可以快速计算交点． 复杂连通区域的扫描线填充算法采用单链表结构记录轮廓线和交点，无需交点排序的过程，包括求交、交点flex,区域填充三个步骤．在求扫描线与廓线的交点时，首先确定扫描线纵坐标的变化范围，然后根据轮廓线每一边界点与其前驱、后继之间的盛间关系，初步求得各条扫描线与轮廓线的交点，接下来对求得的交点进行修剪，得到正确的扫描线交点链表．在交点配对时，对于每条扫描线的交点链表中的交点仍采用奇偶配对方法，确定扫描线与复杂连通区域的相交区问撮后提取配对交点所确定的相交区间内的像素，将其设置为相应的颜色，完成填充过程．

轮廓线每一个边界点与扫描线之间的关系有相交、相切、重叠和半交半切四种类型．关系不同，所求取的交点在数量上也有所不同．如果边界点与扫描线相交，则交点数为1；如果相切，则交点数为2；如果重叠，交点数为0，即无交点；如果半交半切，则交点数为I.在半交半切情况下会产生多余的交点，通过标记法将

4

多余的交点进行修剪．这样，求交之后无需对交点进行排序，可以直接进入交点配对阶段．

3.2 基于链码的填充算法

链码最早是由Freeman提出，分为4方向Freeman链码和8方向Freeman链码．以链码形式表示区域轮廓的填充算法比传统算法具有更正确的填充结果，以及更高速的填充效率彳艮多文献对填充区域轮廓的8方向链码编码属性进行分析，将轮廓点分成孤立点、标志点、忽略点和不存在点四种类型，这样能很好地解决删除孤立点或将一个孤立点当作两个点的问题，避免产生错误的线段编号，从而取得正确的填充结果，但仍存在计算量大、数据结构复杂的问题，影响了算法的效率． 文献[2]将栅栏填充算法移植到链码的填充算法中，提出了一种更高效的填充算法．栅栏指的是一条过多边形顶点且与扫描线垂直的直线，它把多边形分为两半，按任意顺序处理多边形的每条边，但在处理每条边与扫描线的交点时，将交点与栅栏之问的像素取补填充．该算法根据边界的8方向Freeman链码，求出图像区域的水平方向的中分线作为栅栏，并定义了一种新的边界点分类表，将边界上的点分为左端点、右端点和孤立点，对边界上的左右端点与栅栏问的像素取补来填充区域。

栅栏是根据8向Freeman链码的坐标增量表和初始点坐标来计算，即区域水平中分线．区域填充根据边界点的类型来进行，如果边界点为孤立点，则该点的颜色取补填充；如果边界点为左端点，那么需要判断边界点与栅栏的关系，如果边界点位于栅栏左边，则从该点开始向右填充到栅栏，否则从栅栏开始向右填充到该边界点的前一像素；如果边界点为右端点，且位于栅栏左边，那么像从该边界点的后一位开始向右填充到栅栏，否则从栅栏开始向右填充到该边界点的前一像素．遍历一遍链码，根据以上的填充规则，就可以完成区域填充．

3．3 基于缝隙码的填充算法

Freeman缝隙码记录的是区域边界像素边的4方向码值，不同于4方向Freeman链码．按逆时针或顺时针方向沿着图像边界像素的边行走一周，依次记录其方向码，就得到图像边界的缝隙码，加上起始点坐标，边界就可以用缝隙码唯一确定下来，

这是一种适应不同需要的编码形式．

文献[3]提出了基于缝隙码的填充算法，利用种子填充和奇偶填充相结合，根据经过像素边的缝隙码，确定填充的开始像素和终止像素，并给出了单条缝隙码的填充算法，及多连通区域或整幅图像的快速填充算法．该算法根据经过边界像素的左右边的方向码的情况，定义了左像素、右像素和孤立像素3种类型的区域边界点．

单条缝隙码的填充算法首先遍历缝隙码，确定轮廓边界的左像素和右像素并计算像素边角度，确定像素边方向；然后将所有的左像素作为填充起始点，对区域外边界从左向右填充，对区域内边界从右向左填充，直到遇到右像素结束；最后填充区域边界像素．

多连通区域或整幅图像的填充算法首先遍历所有缝隙码，确定边界像素的左像素和右像素；然后，遍历所有区域边界像素，如果像素为左像素，那么以此为起点从左向右填充，直到遇到右像素结束，填充图像区域内像素点；最后，填充所有区域边界像素．

5

3．4 任意复杂区域的自动填充算法

随着计算机图形学的广泛应用，人们对图像自动化处理越来越关注．在区域填充方面，如何利用计算机自动确定种子点，其算法的自动化程度及通用性成为研究的重点．文献[4]提出一种反向注入式填充算法(IcF算法)，该算法在种子填充算法基础上进行改进，能够适应任意复杂区域的全自动填充．

ICF算法首先对目标填充区域(含区域轮廓)以外的部分进行填充，且从一个点开始，扩展到整个非目标填充区域．在非目标填充区域填充完成后，做逻辑取反操作，从而完成目标填充区域的填充．

ICF算法根据给定的边界轮廓线获得该轮廓线图形的最tJ,~b接矩形，然后将该矩形向上、下、左、右4个方向各扩大一个像素，使得填充区域的边界点全部包含在矩形的内部．这样，矩形边界上的所有点都在目标填充区域的外部且在非目标填充区域上，从而可以取该矩形边界上的任意一点作为非目标填充区域的初始种子点．确定非目标填充区域的初始种子点之后，建立一个堆栈，并将该种子点作为初始点入栈．栈非空时弹出栈顶像素进行填充，并以此像素为中心，8一邻域寻找未填充且未入栈的像素，并将该邻域中所有满足这一条件的像素入栈．循环执行上述的操作，直到栈为空．非目标填充区域填充完毕之后，根据填充结果将矩形区域的全部范围进行逻辑取反操作，从而获得目标填充区域。

3.5 算法的比较分析

文献[1]提出的算法在填充时，假设复杂连通区域的外轮廓线的边界点数为，内轮廓线的边界点数为，则需要遍历外轮廓线2次，内轮廓线1次，修剪扫描线交点链表的过程相当于遍历内、外轮廓线各1次，遍历边界点的总规模仅为，而且由于采用链表结构记录轮廓线和交点，无需切割轮廓线，无需交点排序的过程，因此实现简单、具有较快的速度．但该算法对于特殊的边界区域会发生重复填充的现象，当图形内部需要填充的颜色与边界颜色不同时，边界颜色还将被改变．如扫描线与填充区域的孔洞边界重叠时，就会发生这种现象． 文献[2]提出的算法是基于区域边界的Free—man链码的原理，能够得到更正确的填充结果和更高的填充效率．该算法定义了一种新的边界点分类表，把图形学中的栅栏算法移植到链码的填充算法中，比复杂度为area+O(n)的Ren算法163少遍历两遍边界点，因此对于大多数图像，算法速度优于Ren算法．在填充时无需对边界点进行标记，无需使用辅助的内存空间和额外的标志色，因此算法更容易实现．但是在处理复杂多连通区域时，存在对孑L洞的重复填充问题，导致时间的浪费，影响了效率．

文献[3]基于Freeman缝隙码提出了两种算法．单条缝隙码的填充算法在处理图像的单连通区域时，能进行很好的填充，但如果图像中存在多连通区域，边界存在包含关系，则会出现孔洞的重复填充问题，另外，对于复杂的图像，当获得的边界缝隙码混杂时，利还会导致填充混乱．多连通区域或整幅图像的填充算法则避免了以上问题，该算法只需对区域内像素填充，对区域外像素(包括孔洞)不进行填充，也适用于单连通区域．基于缝隙码的填充算法能自动选取种子，对非二值图像，不需要辅助内存空问，对比现有的基于链码的Ren算法网，减少了边界点的遍历次数，提高了算法效率，对多连通区域或整幅图像填充时，不存在孑L洞的重复填充问题．

文献[4]提出的ICF算法在传统种子填充算法基础上，引入了填充区域边界图形

6

的最小外接矩形，使得初始种子点可以完全由计算机自主确定，实现了区域填充的完全自动化和算法的普遍适用性．对含有多个目标填充区域且密集分布时，ICF算法具有很高的效率，但对于有孔洞的区域，该算法需要将该区域内、外边界分别进行自动填充，并将2次结果进行逻辑与运算，才能获得正确的填充结果．

3.6 几种算法的总结总结

目前，大多数区域填充算法的研究都致力于填充结果的完备性和填充的高速高效，也取得了一定的成果．随着计算机图形学技术的发展，区域填充算法在很多领域得到了广泛应用，这使得对填充算法的研究不仅局限于效率和完备陛方面，如何实现填充的完全自动化和算法的通用性也成为研究热点．

4 种子填充算法

4.1扫描线种子填充算法

4.1.1扫描线种子填充算法的基本思想

首先填充当前扫描线上的位于给定区域内的一区段，然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段，如果存在，则依次把它们保存起来。反复这个过程，直到所保存的各区段都填充完毕。 4.1.2扫描线种子填充算法 实现步骤如下：

1、初始化堆栈。 2、种子压入堆栈。 3、while（堆栈非空） {

(1)从堆栈弹出种子象素。

(2)如果种子象素尚未填充，则： a.求出种子区段：xleft、xright; b.填充整个区段。

c.检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在

需要填充的新区段，如果存在的话，则把每个新区段在xleft≤x≤xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。

d.检查相邻的下扫描线的xleft≤x≤xright区间内，是否存在

需要填充的新区段，如果存在的话，则把每个新区段在 xleft≤x≤xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。

}

4.1.3扫描线种子填充算法的特点

1、该算法考虑了扫描线上象素的相关性，种子象素不再代表一个孤立的象素，而是代表一个尚未填充的区段。 2、进栈时，只将每个区段选一个象素进栈（每个区段最右边或最左边的象素），这样解决了堆栈溢出的问题。

3、种子出栈时，则填充整个区段。

7

4、这样有机的结合：一边对尚未填充象素的登记（象素进栈），一边进行填充（象素出栈），既可以节省堆栈空间，又可以实施快速填充。

4.2基于扫描线种子填充算法的改进

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

针对重复扫描的问题，文献[5]根据当前扫描线与相邻扫描线间的位置关系以及区间端点的坐标大小减少了不必要的重复扫描，缩小了重复扫描区间范围，但是所提出的算法仍然将填充与搜索新种子点的操作分别进行，没有克服堆栈频繁操作的缺点，文献[6]将种子点入栈改为新旧区间端点入栈，并将区间填充与搜索新区间合并进行，进一步减少了重复扫描但是算法中并没有减少堆栈操作的频率，并且对每一条当前扫描线都要判断其相邻的两条扫描线是否需要重复扫描[7]。

针对传统区域填充的一些欠缺，文献[8]提出了一种新的区域填充扫描线算法。该算法在处理同一条扫描线上的多个填充区域时，分成向上搜索和向下搜索两种情况进行，每种情况又都可能出现多个搜索新区；在填充过程中，考虑到当前区间左右连续性和上下相关性，只需将出现的新搜索区压入堆栈，不需要将相邻的每根扫描线都压入堆栈，从而减少了像素的重复判读和会回溯区的搜索时间，避免了不必要的进出栈处理，提高了填充效率。

为了存储对每个新区进行搜索的起始位置，定义一个栈用以存放其信息，存储结构如下：

Typedf Struct Stack_node{ Int xleft;//左边界X坐标 Int xright;// 右边界X坐标 Int yscan;//扫描线Y坐标 Int direction;//搜索方向 Struct Stack_node *next； }*Link_Stack; Link_Stack S;

新区入栈的区域填充扫描算法的步骤：

Step1:对存储新区信息的堆栈进行初始化；

Step2：给定填充区域内一点作为种子点，左搜索左填充，得到左边界xl；右搜索右填充，得到右边界xr ； 将向上搜索的起始信息（xl，xr，y，1）；右搜索右填充得到起始信息（xl，xr，y，-1）分别压入堆栈。

Step3：若栈空，则填充过程完成，程序结束；否则，执行以下步骤。

Step4：判断当前的搜索过程是在主搜索区还是在新区，若在新区，则将栈顶元素出栈，并将出栈信息作为新区的起始搜索信息；若在主搜索区，则将上次搜索的结果作为对下条扫描线进行填充的信息；

8

Step5：判断当前搜索点是否已经达到该扫描线区域的最右端，若是转Step8，否则，执行以下步骤；

Step6：若当前搜索点时区域内的一点，并且未填充，则以其为种子点，左搜索左填充，得到左边界xl；右搜索右填充得到右边界xr；

Step7：若找到的第一个可填充区域，则记录下该区的左右边界；若找到多个可填充区域，则将除了第一个以外的其他区压入堆栈；

Step8：将向上搜索过程中可能出现的下回溯区和向下搜索过程中可能出现的上回溯区作为搜索新区分别入栈；然后转Step3[8]。

4.3 一种基于链队列的种子填充法

文献[9]提出了递归种子算法的改进算法，在该算法中使用链队列而不是递归，而且采用先填充后入队列，减少了很多不必要的操作，使得改进后的算法无论是时间还是空间效率都远远优于递归种子填充算法，而且也可以填充任意大小、任意复杂边界的区域。

4.3.1 种子算法的改进之一

算法基本思想思路是：从链队列中获得一个像素点，判断其四连通像素点，若没有填充，则填充它，并将它入队列，如此循环，直到队列空为止。对递归种子填充算法的改进之处为：

(1)在递归种子填充算法中堆栈是系统预先设定的，其大小和存储区域已经 确定，这对填充的区域大小有明显的，当堆栈溢出时，程序就会出错，若堆栈设定很大，又会导致在填充区域不大的情况下，浪费了很多计算机资源，本算法不使用递归，而使用链队列，是因为链队列有两个特点：一是当链队列为空时，它不占用存储空间，只有当数据入链队列时才分配存储空间给它。二是由于在定义链队列前没有限定它的大小，所以从理论上看，有多大的可使用存储空间，就可以建立多大的链队列。

(2)在递归种子填充算法中，采用的是先入栈，出栈后再填充，即当填充某 像素点时，不管它的四连通点是否已被填充，都要进入堆栈，这会导致很多的冗余像素点入栈，而本文算法采用的是先填充再入链队列，在入队列之前要判断像素点是否已被填充 若已被填充才入队列 否则不予考虑。这样将会减少入队列的冗余像素，即每一个像素点只入队列一次。 4.3.2 种子算法的改进之二

以上算法的改进克服了递归种子填充算法由于一个像素点重复入栈操作而导致速度很慢的问题，但经过研究发现以上改进之后，仍存在很多冗余的检测。如图3-1所示，当像素P出队列时，要检测像素1，3，5，7的颜色是否是填充色或边界色。而当像素1出队列时显然P像素已经被填充，而仍要检测像素P的颜色。同理，当像素3，5，7出队列时分别也要检测像素P的颜色，这样也会浪费一些时间。所以我们在改进一的基础上进一步提出改进二的算法。

改进的思路是这样的，设置4个链队列分别记录向上、向下、向左、向右4个方向的填充新种子像素点.若当正在出队的像素点是来自于记录向上的那个队列，不要检测它的下面那个像素点，则在处理某个像素点时只要检测3个连通像素点。

这里设置了4个链队列，是否增加了程序的存储开销呢？答案是否定的。因为采用的是链队列，只有当像素入队列时才会占用存储空间。经过对程序的测试可得，第一次改进时，每个像素只入队列一次，同样设4个链队列，每个像素点也

9

只入一次队列，所以总的入队列次数是一样的[9]。

图5 第一次改进后的像素监测

4.4程序运行调试

作为本次区域填充算法探究的实践部分我选择扫描线种子填充算法和扫描线算法进行调试观测，经过查阅纸质资料、互联网相关内容以及朋友的协助下，最终调试运行成功。

5 结束语

通过查阅大量的图形学区域填充相关资料，总结了近年来在区域填充方面一些算法，并且阐述各自的优劣。分别以扫描线种子填充算法和种子填充算法两条主线探究图形学方面的专家逐步改善区域填充算法提高算法效率的过程。经过近三周的对区域填充算法的进一步学习、整理和总结，更加熟悉了算法本身以及大家一直在试图改善算法的入手点。在整个准备的过程中既有自己的努力，也有他人的帮助，感谢老师本学期给我的指导。

10

参考文献

[1]张志龙，李吉成，沈振康．一种新的快速复杂连通区域扫描线填充算法[J]．计算机工程与应用，2004(31)：6—8．

[2]巨志勇，陈优广．一种新的基于链码的填充算法．计算机工程[J]，2007，33(17)：211—215．

[3]陈优广，顾国庆，王玲．一种基于缝隙码的区域填充算法[J]． 中国图象图形学报，2007，12(11)：2086-2092．

[4]柳稼航，方涛，杨建峰．适用于任意复杂区域的全自动填充方法[J]．计算机工程．2008，34(4)：238—240． [5]余腊生，沈德耀.扫描线种子填充算法的改进[J].计算机工程，2003，29（10）：70-72.

[6]降爱莲，谢克明.压入新、旧区段的区域填充扫描线算法[J].计算机工程与应用，2006，（17）：43-45.

[7]郭文平，龙帮强.扫描线种子填充算法的改进[J].2008.4,27(2)：48-51. [8]张荣国，刘焜.新区入栈的区域填充扫描线算法[J].2006.3,32(5)：63-65. [9]陈元琰，陈洪波.一种基于链队列的种子填充法[J].2003.9,21(3)：31-33. [10]秦晓薇.区域填充算法的研究[J].赤峰学院学报.2011.6,27(6):47-49. [11]潘云鹤，董金祥，陈德人．计算机图形学—— 原理、方法及应用(修订版)[M]．北京：高等教育出版社，2003，l2：26～37． [12]孙家广，胡事民．计算机图形学基础教程[M]．北京：清华大学出版社，2005，2：22～28．

[13](美)David F．Rogers．计算机图形学的算法基础(第2版) [M]．北京：机械工业出版社，2002．99—10.

[14]Chang Fu，Chen Chunjen，Lu Ch~en．A lin—ear time component labeling algorithm using

contour tracing technique[J]．Computer Visionand Image Understanding，2004，93 (2)：206—220.

[15]Tang G Y． A discrete version of green’8 theorem [J]．IEEETransactions on Pattern

Analysis and Machine Intelligence， 1982，4(3)：242～250．

11