武汉学院计算机图形学论文-基于扫描线填充算法的改进型区域填充算法实现.docx

武汉学院计算机图形学 课程论文题 目： 基于扫描线填充算法的改进型区域填充算法实现 系 别：  专业、 班级： 姓 名：  学 号：  指 导 教 师：  完 成 时 间：  摘要： 针对现有区域填充算法在填充效率或准确性方面的不足，通过深入分析扫描线像素置及颜色间的相关性，建立了一种新的扫描线回溯判断依据和颜色判断规则。具体实现时，采用向上、向下两个方向的扫描堆栈，简化了扫描线填充算法的复杂性，使算法更易理解，最终经Vc+进行了实现。实验结果表明，该算法有很高的效率和精度，达到了预期效果。关键词：扫描线算法；区域填充；回溯；种子点 区域填充是一种基本的计算机图形操作技术，在计算机辅助设计、交互式图形显示、动画、图像处理等实际领域中有着广泛的应用。随着图象实时处理技术的发展，对区域填充算法的要求也越来越高。目前，区域填充常采用的填充算法，依原理不同有基于4连通、8连通域的种子填充算法和基于像素相关性原理的扫描线填充算法。虽然种子填充算法相对简单，但由于其没有考虑像素间的相关性，每个像素都可能多次人栈，效率很低，当填充面积较大时，甚至会出现系统崩溃。而扫描线填充算法，因其具有更高的效率，在商业软件中得到了大量的应用。在这种背景下，本文通过分析当前各种扫描线改进算法的优缺点，提出了一种高效的扫描线填充算法，有效提升了扫描线填充算法的效率和精度。 1 扫描线算法现状分析 经典扫描线算法的填充步骤如下：步骤1：(初始化)堆栈置为空，将给定的种子点( ，)，)压人堆栈； ·步骤2：(出栈)若栈空则结束。否则取栈顶元素( ，Y)，以Y作为当前扫描线。步骤3：(填充并确定种子点所在区段)从种子点( ，Y)出发，沿当前扫描线向左、右两个方向填充，直到非内部。分别标记区段的左、右端点坐标为 2和XI"。步骤4：(并确定新的种子点)在区间xl， r中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压人堆栈，返回步骤2。 在扫描整个填充区域过程中，许多行被扫描过不止一次，并且像素点也进行不止一次的判断，这就降低了程序的效率和运行速度。为改善扫描线算法的效率，通过消除经典算法中像素点颜色判读的重复操作对原算法进行改进；采用压人区段端点的方法，消除了原算法中端点与种子点分开操作时的重复扫描问题，提高了效率；通过区段端点的比较，建立了回溯扫描条件，有效提高了填充效率；采用广度优先的思想，力图在广度上对区域进行完整填充，有一定的意义；通过坐标与方向建立了特殊的栈，采用与类似的回溯判断条件，加快了区域填充速度；在借助改进算法的基础上，将填充由4连通域扩展到了8连通域；总结了多种当前改进算法，并对各自算法的优缺点进行了讨论，对算法的提升和总结具一定意义；从可能出现的漏填出发，提出了一种新、旧区段的扫描线方法。在以上各种算法中由于采用了回溯判断进行设计，有效减小了重复判断情况，效率最高。然而也有相对不足的地方，如中介绍的算法，在区域判断时，要分多个部分进行判断，并且区段分的较多时，进栈也相对较烦琐，同时实现时，对像素颜色判断分别进行了填充色及边界色两次判断，也影响了效率。2 改进的扫描线填充算法21 区域填充基础 这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图1所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程. 区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图2所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。本文主要讨论四连通情况。22 区域像素间的相关性分析针对任意一个封闭区域(如图3所示)，其内点经分析有如下规律：(1)任何一个内点均可经过四连通的方式连通在一起。(2)在一条扫描线中，可能有多个区段(每个区段指具有连续内点的段)，每一个区段对应的全部为内点。在图2所示的各条扫描线中，对应的区段个数如表1所示。（3)设扫描线的一个区段表示为(正，xR，Y)，其中以为区段的左边界， 为区段的右边界，Y为区段的扫描线。从该区段开始进行填充，如向上填充，与该区段相连通的上方一区段表示为(xUL，xUR，Y一1)。如果xL>她吧，则可能出现回溯现象，即通过区段(此 ，xL，Y一1)由向上的填充方向改为向下填充，可能在(xUL，xL，Y)中找到新的区段。同理，当 >xR时，可能在(xR，xUR，Y)中找到新的区段。如图2中，由扫描线8向上扫描，扫描线7对应的区段就满足向下回溯条件，同时扫线3对应的右区段向上扫描，扫描线2对应的区段，也满足向下回溯条件。(4)从一个区段( ，xR，Y)向下填充时，如果其对应的下方一区段为(xDL，xDR，Y+1)，当xDL<xL或xDR>xR，则需要向上进行回溯。(5)从一个区段( ，xR，Y)向上填充时，其上一连通区段描述为(xUL，xUR，Y一1)，当xUR<xR时，在(xUR，xR，Y一1)中可能存在新的区段。同理向下填充时，也存在可能漏填的区域。(6)从一个区段向上填充时，采用四连通中的向上连通即可，如区段(她，xR，Y)向上填充时，只需从像素(正，Y一1)开始判断该点是不是边界点即可。如不是边界点，必为内点。当找到第一个内点，则可通过该内点向左、右进行连通扩展。23 新填充算法 由22节分析可知，在进行填充时，分向上向下填充两种情况，且填充后还可能有回溯、漏填等情况出现，填充算法相对复杂。为简化算法的实现，在填充实现时，可采用向上、向下两个堆栈分别进行操作，使填充步骤清晰明了。具体算法步骤如下：步骤1：(初始化)，清空向上、向下堆栈；步骤2：(初始点压栈)，由给定的一点( ，Y)，分别向左、向右扫描，只要该点不是边界点，则进行填充，直到运行到边界点为止，至此得到一个区段(儿，xR，Y)；并向上、向下压栈；步骤3：(向上填充)，如果向上堆栈为空，转向步骤5，否则向上堆栈出栈，出栈对应值记为(UpXL，UpXR，】，)，从像素(UpXL，Upr一1)开始，向右进行非边界点判断，如果直到(UpXR，Vpr一1)都没有遇非边界点，则转向步骤5如果遇到非边界点(UpX，Upr一1)，则转向步骤4；步骤4：(向上填充堆栈处理)由给定的一点(UpX，Y一1)，分别向左、向右扫描，只要该点不是边界点，则进行填充，直到边界点为止，至此得到一个新区段(xUL，Y一1)，并将(xUL，xUR，Y一1)人向上堆栈。如果xUL<UpXL，则( 观，UpXL，Y一1)人向下堆栈，如果xUR>UpXR，则(UpXR，她 ，Y一1)人向下堆栈。如果她 < UpXR，则(xUR，UpXR， y)人向上堆栈。步骤5：(向下填充)，如果向下堆栈为空，转向步骤7，否则向下堆栈出栈，出栈对应值记为(DoXL，DoXR，DoY)，从像素(DoXL，DoY+1)开始，向右进行非边界点判断，如果直到(DoXR，DoY+1)都没有遇非边界点，则转向步骤7如果遇到非边界点(DoX，DoY+1)，则转向步骤6；步骤6：(向下填充堆栈处理)由给定的一点(DoX，DoY+1)，分别向左、向右扫描，只要该点不是边界点，则进行填充，直到边界点为止，至此得到一个新区段(xDL，xDR，Y+1)，并将(xDL，DR，Y+1)入向下堆栈。如果xDL<DoXL，则(xDL，DoXL，Y+1)人向上堆栈，如果xDR>DoXR，则(DoXR，xDR，Y+1)人向上堆栈。如果xDR< DoXR，则(xDR，DoXR，DoY)人向下堆栈；步骤7：(结束)如果向上堆栈和向下堆栈已空，则结束，否则转步骤3。3 算法的具体实现 为验证算法的有效性，本文采用VC+对算法进行了实现。下面给出实现的关键代码。 int UpCurStartX，UpCurEndX，UpCurY；向上堆栈弹出值的存储变量 int DownCurStartX，DownCurEndX，DownCurY；向下堆栈弹出值的存储变量 BOOL Orient；当前填充的方向，如果是TRUE，代表向上，如果是FALSE，则代表向下 void CUuDlg：FillMarmer(int x，int y)具体填充函数 int i； upxuhao=0；向上堆栈指针清零 downxuhao=O；向下堆栈指针清零 UpCurY：1；第一次点扫描置该变量为一l SearchAndSet(x，Y)；将种子进行扩充 while(upxuhao>0 l I downxuhao>o)H果向上或向下堆栈非空 if(upxuhao>o)果向上堆栈非空 if(PoPUpStack()=true)向上堆栈弹出 Orient=TRUE； for(i=UpCurS ；i<=UpCurEndX；i+)在弹出区间内，从左边开始扫描 if(GetPixel(i，UpCurY1)! =Boundery)如果找到非边界点 SearchAndSet(i，UpCurY一1)；将找到的点进行左右扩展，并进行栈处 i= UpCurEndX+1： 向下堆栈弹出 void CUuDlg：SearchAndSet(int x，int y)给定点左右扩展及栈处理函数 int PreX，Left，Right； PreX=x；Left=一1； Right= 一1； SetPixel(x，Y)；当前点置填充色*给定点左右扩展* while(1)向左查询 X一一； if(x>0) if(GetPixel(x，Y)!=Boundery)N果为非边界点 SetPixel(x，Y)；置填充色elseLeft=X+1；x=一1； else break；X=PreX； if(Left=：一1)Left=x；while(1) 向右查询 x+； If(x>0) if(GetPixel(x，Y)!=Boundery)如果为非边界点 SetPixel(x，y)；置填充色 elseRight=x一1； x=一4； else break； if(Right=一1、 Right=PreX ； *堆栈处理* if(UpCurY=一1)如果是第一次查询 PushDownStack(Left，Right，Y)；第一次，向下入栈PushUpStack(Left，Right，Y)；第一次，向上入栈return；向上堆栈处理 if(Orient：=TRUE)果是向上弹出栈 if(UpCurEndXRight>1)向右继续搜索有没有可用区域 PushUpStack(Right，UpCurEndX，UpCurY)； if(RightLeft)>1)当前区段入栈 PushUpStaek(Left，Right，Y)；将当前查询值向上压栈 if(RightUpCurEndX>1)回溯判断 PushDownStaek(UpCurEndX，Right，Y)；向下压栈if(UpCurStartXLeft>1)PushDownStaek(Left，UpCurStartX，Y)；向下压栈 向下堆栈处理4 实验结果整个算法实现后，对常见图形进行了填充实验，部分填充效果如图4所示。 5 结束语 整个算法在设计之初，针对重复扫描问题进行了重点研究，通过上、下分开的堆栈，彻底解决了重复扫描问题，同时采用回溯判断算法，有效避免了漏填的发生。在像素颜色具体判断时，只采用与边界点判断的方法，很好降低了像素的判断次数。 设填充区域内点个数为',，边界点个数为n，向上人栈和向下人栈的次数为N1，N2，则整个算法进行比较的次数为：m+n+3 X(N1+N2) 像素位的个数为m个，颜色判断的次数为m+r次。参照文献14所提供的效率计算式，进行部分修正后得整个算法的效率为：在效率公式中，分子代表所有像素个数，分母代表算法进行的总比较次数，由效率公式可知，整个算法已完全消除重复判断现象，并且颜色判断只进行一次，有极高的效率。同时由于每次出栈操作都要进行回溯判断和漏填判断，因此整个效率是小于l的。 整个算法针对矩形填充区域效率是最高的，假设有100行200列的矩形区域，最外一圈的点阵为边界，则其填充效率为：通过以上分析可以看出，整个改进算法具有较高的效率和准确度，可为区域填充算法提供一定的参考。参考文献1李春雨等计算机图形学理论与实践【M北京：北京航空航天大学出版社，2004：47562柳朝阳对区域填充扫描线算法的改进J计算机工程专刊，1994，10：4694723柳朝阳，李叔梁压人区段端点的区域填充扫描线算法J计算机辅助设计与图形学学报，1996，8(6)：4154194王三福，李莉，张念喜对区域填充算法的一点改进J天水师范学院学报，2006，26(2)：17205欧阳春娟，欧阳迎春基于广度优先搜索的扫描线填充算法J井冈山师范学院学报(自然科学)，2005，6：33356张荣国，刘煜新区入栈的区域填充扫描线算法J计算机工程，2O06，3：63647ttJ万春，刘建君，朱玉文，陈小春一种实时高速的八连通区域填充算法J计算机应用研究，2006，6：1771798秦晓薇区域填充算法的研究J赤峰学院学报(自然科学版)，2011，6：47499降爱莲，谢克明压入新、旧区段的区域填充扫描线算法J计算机工程与应用，2006，17：43451o降爱莲重写区段左端点的4向填充扫描线算法J太原理工大学学报，2OO6，31(3)：277280