区域填充算法的研究

区域填充算法的探究摘要区域填充算法是计算机图形学的一个重要研究课题．传统的区域填充算法存在填充结果不完备及算法效率不高的问题，在分析了两种传统区域填充算法的原理的基础上，详细阐述了四种改进的区域填充算法，并对算法的效率性能进行比较分析，指明了区域填充算法未来的研究热点，着重探究区域填充算法尤其是扫描线种子填充算法和种子填充算法近年来的发展状况，比较它们之间的优点与足，对图形学的区域填充算法有更深入的理解介绍种子填充算法及其改进算法。关键词：区域填充；填充算法；扫描线算法；种子填充算法本文由天空乐园大学生旅游网整理分享11引言区域填充是指用不同的颜色、灰度、线条或符号填充一个有界区域，该区域可以是带孔的，也可以是不带孔的．它是计算机图形学的一项重要内容，在交互式图形设计、真实感图形显示、计算机辅助设计、图形分析等领域有着广泛的应用，一直是研究的热点．传统的区域填充算法有两种，一种是通过确定横跨区域的扫描线的覆盖间隔来填充的扫描线算法，另一种是从给定的位置开始填充直到指定的边界为止的种子填充算法．扫描线算法主要用来填充比较简单的标准多边形区域，比如圆、椭圆以及其他一些简单的多边形，它对轮廓线的形状有一定的要求，在处理复杂区域时往往失效．种子填充算法可以解决边界比较复的多边形区域填充问题，它必须首先确定一个或者多个区域内部的点作为种子点，并赋予填充色，然后以该点为起点，用四向连通方法或八向连通方法找到区域内的所有点填充。扫描线算法在处理带水平边的凹拐点时不能正确填充，这是该算法的一个突出问题，但由于利用了扫描线上象素之问的连贯性，因此具有较高的效率．最简单直观的种子填充算法采用递归方法，由于进行大量的出入栈操作，因此效率很低，在填充较大的区域时，要求分配较大的堆栈空问，不仅浪费了内存，也可能出现堆栈溢出现象．填充结果的完备性和填充过程的高效高速是区域填充算法的度量标准．在传统区域填充算法的基础上，很多文献提出了更加正确高效的算法．本文介绍四种改进的区域填充算法，并对其进行比较分析。2区域填充基本知识点介绍2.1多边形扫描转换在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。顶点表示是用多边形的顶点序列来表示多边形，特点直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息，但便于帧缓冲器表示图形，是面着色所需要的图形表示形式。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。多边形可分为凸多边形、凹多边形、含内环多边形。（1）凸多边形：任意两顶点间的连线均在多边形内。（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。（3）含内环多边形：多边形内包含有封闭多边形。扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为4个步骤。（1）求交：计算扫描线与多边形各边的交点。（2）排序：把所有交点按x值递增顺序排序。（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。多边形扫描转换算法步骤如下：2（1）初始化：构造边表。（2）对边表进行排序，构造活性边表。（3）对每条扫描线对应的活性边表中求交点。（4）判断交点类型，并两两配对。（5）对符合条件的交点之间用画线方式填充。（6）下一条扫描线，直至满足扫描结束条件。2.2区域填充算法这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图1所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。○表示边界点●表示内点图1区域的内点表示和边界表示图24连通区域和8连通区域区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。2.2.1区域填充的扫描线算法扫描线算法是按照扫描线顺序，计算扫描线与多边形的相交区间，再用颜色显示这个区间，区间的端点则是扫描线与多边形边界线的交点，可以通过计算获得．要完成这个扫描转换过程，首先计算扫描线与多边形各边的交点，然后对求得的交点进行排序，接下来利用奇偶配对求出扫描线与边形的相交区间，最后对这些相交区问填色．由于扫描线是一组连续的水平平行的直线，因此在计算其与多边形的交点时较容易，因为交点的纵坐标已知，即扫描线的编号，则可根据多边形的数学表达式求出交点的横坐标．对交点进行排序时采用横坐标由小到大的顺序，便于相交区间的确定．对于已经排序的交点，使用奇偶配对法确定相交区间，如：交点a。与交点a2为一对，交点a。与交点a4为一对，代表直线ala2和a3a4是扫描线与多边形的相交区间，al-,a2、a。、a4是相交区间的各端点．填充时则可以直接用填充色将相交区问的各端点连接．扫描线算法采用邻接链表的数据结构，每条扫描线在该表中都对应有一项，利用初始边表OET与活动边表AET记录扫描线与多边形相交的情况．该算法效率较高，但填充结果的完备性不好，在处理复杂区域时，往往不能正确填充．算法的基本过程如下：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。3图3扫描线填充算法流程图区域填充的扫描线算法可由下列3个步骤实现。Step1：求出每条水平扫描线与多边形各边的交点。Step2：将每条水平扫描线上的交点按X值递增的顺序排列。Step3：将交点的交点配成“交点对”。Step4：在交点对间填色。2.2.2区域填充的种子算法种子填充算法又称为边界填充算法。其基本思想是：种子填充算法是从多边形区域内部的一点开始，由此出发找到区域内的所有像素．该算法采用的边界定义是：区域边界上所有像素均具有某个特定的颜色值；区域内部所有像素均不取这一特定颜色；而边界外的像素则可具有与边界相同的颜色值．根据边界定义，算法从多边形区域内部的一个像素点开始，先检测该点的颜色，如果它与边界色和填充色均不相同，就用填充色填充该点．然后检测相邻位置的各个像素点，以确定它们是否与边界色和填充色均相同，若不相同，就填充该相邻点．这个过程持续到已经检测完区边界范围内的所有像素点为止．从当前点检测相邻像素有4向连通和8向连通两种方法．4向连通方法指的是从区域上一点出发，可通过上、下、左、右4个方向的移动，在不越出区域的前提下，到达区域内的任意像素点；8向连通方法则可以通过左、右、上、下、左上、右上、左下、右下这8个方向的移动来到达．种子填充算法简单，易于实现，可以处理复杂区域的填充问题，填充结果的完备性较好．但是这种算法需要很大的存储空间以实现栈结构，同一个像素多次人栈和出栈，所花费的时间也很多，导致算法效率不高种子填充算法常用四连通域和八连通域技术进行填充操作。4从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。a)连通域及其内点b)填充四连通域图4四向连通填充算法一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图4(a)所示的区域的内部，而四向连通填充算法只能完成如图4(b)的部分填充。3区域填充算法日新月异的发展上面所提到的区域填充算法，扫描线算法和种子填充算法适用条件苛刻，要么对所要填充的多边形有一定的局限性，要么就是由于采用递归次数太多，区域内的每个像素都引起一次递归，即系统堆栈的一次进出操作，费时费内存。因而许多改进的算法便从减少递归的次数入手来提高算法的效率。下面介绍几种改进的区域填充算法3.1复杂连通区域的扫描线填充算法传统的扫描线算法不能处理复杂连通区域的填充，文献[1]基于扫描线算法的原理，提出一种能够处理复杂连通区域的扫描线填充算法，该算法通过分析水平扫描线与复杂连通区域轮廓线相交的各种可能情况，可以快速计算交点．复杂连通区域的扫描线填充算法采用单链表结构记录轮廓线和交点，无需交点排序的过程，包括求交、交点flex,区域填充三个步骤．在求扫描线与廓线的交点时，首先确定扫描线纵坐标的变化范围，然后根据轮廓线每一边界点与其前驱、后继之间的盛间关系，初步求得各条扫描线与轮廓线的交点，接下来对求得的交点进行修剪，得到正确的扫描线交点链表．在交点配对时，对于每条扫描线的交点链表中的交点仍采用奇偶配对方法，确定扫描线与复杂连通区域的相交区问撮后提取配对交点所确定的相交区间内的像素，将其设置为相应的颜色，完成填充过程．轮廓线每一个边界点与扫描线之间的关系有相交、相切、重叠和半交半切四种类型．关系不同，所求取的交点在数量上也有所不同．如果边界点与扫描线相交，则交点数为1；如果相切，则交点数为2；如果重叠，交点数为0，即无交点；如果半交半切，则交点数为I.在半交半切情况下会产生多余的交点，通过标记法将5多余的交点进行修剪．这样，求交之后无需对交点进行排序，可以直接进入交点配对阶段．3.2基于链码的填充算法链码最早是由Freeman提出，分为4方向Freeman链码和8方向Freeman链码．以链码形式表示区域轮廓的填充算法比传统算法具有更正确的填充结果，以及更高速的填充效率彳艮多文献对填充区域轮廓的8方向链码编码属性进行分析，将轮廓点分成孤立点、标志点、忽略点和不存在点四种类型，这样能很好地解决删除孤立点或将一个孤立点当作两个点的问题，避免产生错误的线段编号，从而取得正确的填充结果，但仍存在计算量大、数据结构复杂的问题，影响了算法的效率．文献[2]将栅栏填充算法移植到链码的填充算法中，提出了一种更高效的填充算法．栅栏指的是一条过多边形顶点且与扫描线垂直的直线，它把多边形分为两半，按任意顺序处理多边形的每条边，但在处理每条边与扫描线的交点时，将交点与栅栏之问的像素取补填充．该算法根据边界的8方向Freeman链码，求出图像区域的水平方向的中分线作为栅栏，并定义了一种新的边界点分类表，将边界上的点分为左端点、右端点和孤立点，对边界上的左右端点与栅栏问的像素取补来填充区域。栅栏是根据8向Freeman链码的坐标增量表和初始点坐标来计算，即区域水平中分线．区域填充根据边界点的类型来进行，如果边界点为孤立点，则该点的颜色取补填充；如果边界点为左端点，那么需要判断边界点与栅栏的关系，如果边界点位于栅栏左边，则从该点开始向右填充到栅栏，否则从栅栏开始向右填充到该边界点的前一像素；如果边界点为右端点，且位于栅栏左边，那么像从该边界点的后一位开始向右填充到栅栏，否则从栅栏开始向右填充到该边界点的前一像素．遍历一遍链码，根据以上的填充规则，就可以完成区域填充．3．3基于缝隙码的填充算法Freeman缝隙码记录的是区域边界像素边的4方向码值，不同于4方向Freeman链码．按逆时针或顺时针方向沿着图像边界像素的边行走一周，依次记录其方向码，就得到图像边界的缝隙码，加上起始点坐标，边界就可以用缝隙码唯一确定下来，这是一种适应不同需要的编码形式．文献[3]提出了基于缝隙码的填充算法，利用种子填充和奇偶填充相结合，根据经过像素边的缝隙码，确定填充的