武汉学院计算机图形学论文基于扫描线填充算法的改进型区域填充算法实现.docx
- 文档编号:17200958
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:11
- 大小:200.59KB
武汉学院计算机图形学论文基于扫描线填充算法的改进型区域填充算法实现.docx
《武汉学院计算机图形学论文基于扫描线填充算法的改进型区域填充算法实现.docx》由会员分享,可在线阅读,更多相关《武汉学院计算机图形学论文基于扫描线填充算法的改进型区域填充算法实现.docx(11页珍藏版)》请在冰点文库上搜索。
武汉学院计算机图形学论文基于扫描线填充算法的改进型区域填充算法实现
武汉学院
《计算机图形学》课程论文
题目:
基于扫描线填充算法的改进型区域填充算法实现
系别:
专业、班级:
姓名:
学号:
指导教师:
完成时间:
摘要:
针对现有区域填充算法在填充效率或准确性方面的不足,通过深入分析扫描线像素置及颜色间的相关性,建立了一种新的扫描线回溯判断依据和颜色判断规则。
具体实现时,采用向上、向下两个方向的扫描堆栈,简化了扫描线填充算法的复杂性,使算法更易理解,最终经Vc++进行了实现。
实验结果表明,该算法有很高的效率和精度,达到了预期效果。
关键词:
扫描线算法;区域填充;回溯;种子点
区域填充是一种基本的计算机图形操作技术,在计算机辅助设计、交互式图形显示、动画、图像处理等实际领域中有着广泛的应用。
随着图象实时处理技术的发展,对区域填充算法的要求也越来越高。
目前,区域填充常采用的填充算法,依原理不同有基于4连通、8连通域
的种子填充算法和基于像素相关性原理的扫描线填充算法。
虽然种子填充算法相对简单,但由于其没有考虑像素间的相关性,每个像素都可能多次人栈,效率很低,当填充面积较大时,甚至会出现系统崩溃。
而扫描线填充算法,因其具有更高的效率,在商业软件中得到了大量的应用。
在这种背景下,本文通过分析当前各种扫描线改进算法的优缺点,提出了一种高效的扫描线填充算法,有效提升了扫描线填充算法的效率和精度。
1扫描线算法现状分析
经典扫描线算法的填充步骤如下:
步骤1:
(初始化)堆栈置为空,将给定的种子点(,),)压人堆栈;·
步骤2:
(出栈)若栈空则结束。
否则取栈顶元素(,Y),以Y作为当前扫描线。
步骤3:
(填充并确定种子点所在区段)从种子点(,Y)出发,沿当前扫描线向左、右两个方向填充,直到非内部。
分别标记区段的左、右端点坐标为2和XI"。
步骤4:
(并确定新的种子点)在区间[xl,r]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。
若存在非边界、未填充的象素,则把每一区间的最右象素作为种子点压人堆栈,返回步骤2。
在扫描整个填充区域过程中,许多行被扫描过不止一次,并且像素点也进行不止一次的判断,这就降低了程序的效率和运行速度。
为改善扫描线算法的效率,通过消除经典算法中像素点颜色判读的重复操作对原算法进行改进;采用压人区段端点的方法,消除了原算法中端点与种子点分开操作时的重复扫描问题,提高了效率;通过区段端点的比较,建立了回溯扫描条件,有效提高了填充效率;采用广度优先的思想,力图在广度上对区域进行完整填充,有一定的意义;通过坐标与方向建立了特殊的栈,采用与类似的回溯判断条件,加快了区域填充速度;在借助改进算法的基础上,将填充由4连通域扩展到了8连通域;总结了多种当前改进算法,并对各自算法的优缺点进行了讨论,对算法的提升和总结具一定意义;从可能出现的漏填出发,提出了一种新、旧区段的扫描线方法。
在以上各种算法中由于采用了回溯判断进行设计,有效减小了重复判断情况,效率最高。
然而也有相对不足的地方,如中介绍的算法,在区域判断时,要分多个部分进行判断,并且区段分的较多时,进栈也相对较烦琐,同时实现时,对像素颜色判断分别进行了填充色及边界色两次判断,也影响了效率。
2改进的扫描线填充算法
2.1区域填充基础
这里的区域指已表示成点阵形式的填充图形,是像素的集合。
区域有两种表示形式:
内点表示和边界表示,如图1所示。
内点表示,即区域内的所有像素有相同颜色;边界表示,即区域的边界点有相同颜色。
区域填充指先将区域的一点赋予指定的颜色,然后将该颜色扩展到
整个区域的过程.
区域填充算法要求区域是连通的。
区域可分为4向连通区域和8向连通区域,如图2所示。
4向连通区域指的是从区域上一点出发,可通过四个方向,即上、下、左、右移动的组合,在不越出区域的前提下,到达区域内的任意像素;8向连通区域指的是从区域内每一像素出
发,可通过8个方向,即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。
本文主要讨论四连通情况。
2.2区域像素间的相关性分析针对任意一个封闭区域(如图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
(5)从一个区段(,xR,Y)向上填充时,其上一连通区段描述为(xUL,xUR,Y一1),当xUR 同理向下填充时,也存在可能漏填的区域。 (6)从一个区段向上填充时,采用四连通中的向上连通即可,如区段(她,xR,Y)向上填充时,只需从像素(正,Y一1)开始判断该点是不是边界点即可。 如不是边界点,必为内点。 当找到第一个内点,则可通过该内点向左、右进行连通扩展。 2.3新填充算法 由2.2节分析可知,在进行填充时,分向上向下填充两种情况,且填充后还可能有回溯、漏填等情况出现,填充算法相对复杂。 为简化算法的实现,在填充实现时,可采用向上、向下两个堆栈分别进行操作,使填充步骤清晰明了。 具体算法步骤如下: 步骤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 如果她 步骤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 如果xDR 步骤7: (结束)如果向上堆栈和向下堆栈已空,则结 束,否则转步骤3。 3算法的具体实现 为验证算法的有效性,本文采用VC++对算法进行了实现。 下面给出实现的关键代码。 intUpCurStartX,UpCurEndX,UpCurY;//向上堆栈弹 出值的存储变量 intDownCurStartX,DownCurEndX,DownCurY;//向下 堆栈弹出值的存储变量 BOOLOrient;//当前填充的方向,如果是TRUE,代表 向上,如果是FALSE,则代表向下 voidCUuDlg: : FillMarmer(intx,inty)//具体填充函数 {inti; up.xuhao=0;//向上堆栈指针清零 down.xuhao=O;//向下堆栈指针清零 UpCurY: ~1;//第一次点扫描置该变量为一l SearchAndSet(x,Y);//将种子进行扩充 while(up.xuhao>0lIdown.xuhao>o)//~H果向上或向下堆栈非空{if(up.xuhao>o)//~果向上堆栈非空 {if(PoPUpStack()==true)//向上堆栈弹出 {Orient=TRUE; for(i=UpCurS~;i<=UpCurEndX;i++)//在弹出区间内,从左边开始扫描 {if(GetPixel(i,UpCurY—1)! =Boundery)//如果找到非边界点 {SearchAndSet(i,UpCurY一1);//将找到的点进行左右扩展,并进行栈处i=UpCurEndX+1: } } } } …………//向下堆栈弹出 } } voidCUuDlg: : SearchAndSet(intx,inty)//给定点左右扩展及栈处理函数 {intPreX,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);//置填充色else{Left=X+1;x=一1;} } elsebreak; } X=PreX;if(Left=: 一1)Left=x; while (1)//向右查询 {x++; If(x>0) {if(GetPixel(x,Y)! =Boundery)//如果为非边界点 SetPixel(x,y);//置填充色 else{Right=x一1;x=一4;} } elsebreak; } if(Right==一1、 Right=PreX; //************堆栈处理**** if(UpCurY==一1)//如果是第一次查询 {PushDownStack(Left,Right,Y);//第一次,向下入栈 PushUpStack(Left,Right,Y);//第一次,向上入栈 return;}//向上堆栈处理 if(Orient: =TRUE)//~果是向上弹出栈 { if(UpCurEndX—Right>1)//向右继续搜索有没有可用区域 {PushUpStack(Right,UpCurEndX,UpCurY);} if((Right—Left)>1)//当前区段入栈 {PushUpStaek(Left,Right,Y);//将当前查询值向上压栈 if(Right—UpCurEndX>1)//回溯判断 {PushDownStaek(UpCurEndX,Right,Y);//向下压栈 } if(UpCurStartX—Left>1) {PushDownStaek(Left,UpCurStartX,Y);//向下压栈} } } ………….//向下堆栈处理 } 4实验结果 整个算法实现后,对常见图形进行了填充实验,部分填充效果如图4所示。 5结束语 整个算法在设计之初,针对重复扫描问题进行了重点研究,通过上、下分开的堆栈,彻底解决了重复扫描问题,同时采用回溯判断算法,有效避免了漏填的发生。 在像素颜色具体判断时,只采用与边界点判断的方法,很好降低了像素的判断次数。 设填充区域内点个数为/'//,,边界点个数为n,向上人 栈和向下人栈的次数为N1,N2,则整个算法进行比较的 次数为: m+n+3X(N1+N2) 像素位的个数为m个,颜色判断的次数为m+r/.次。 参照文献14]所提供的效率计算式,进行部分修正后得整个算法的效率为: 在效率公式中,分子代表所有像素个数,分母代表算法进行的总比较次数,由效率公式可知,整个算法已完全消除重复判断现象,并且颜色判断只进行一次,有极高的效率。 同时由于每次出栈操作都要进行回溯判断和漏填判断,因此整个效率是小于l的。 整个算法针对矩形填充区域效率是最高的,假设有100行200列的矩形区域,最外一圈的点阵为边界,则其 填充效率为: 通过以上分析可以看出,整个改进算法具有较高的效率和准确度,可为区域填充算法提供一定的参考。 参考文献 [1]李春雨等.计算机图形学理论与实践【M].北京: 北京航空航天大 学出版社,2004: 47~56. [2]柳朝阳.对区域填充扫描线算法的改进[J].计算机工程专刊, 1994,10: 469~472. [3]柳朝阳,李叔梁.压人区段端点的区域填充扫描线算法[J].计算 机辅助设计与图形学学报,1996,8(6): 415~419. [4]王三福,李莉,张念喜.对区域填充算法的一点改进[J].天水师 范学院学报,2006,26 (2): 17—20. [5]欧阳春娟,欧阳迎春.基于广度优先搜索的扫描线填充算法[J]. 井冈山师范学院学报(自然科学),2005,6: 33~35. [6]张荣国,刘煜.新区入栈的区域填充扫描线算法[J].计算机工 程,2O06,3: 63—64. [7]~ttJ万春,刘建君,朱玉文,陈小春.一种实时高速的八连通区域填 充算法[J].计算机应用研究,2006,6: 177~179. [8]秦晓薇.区域填充算法的研究[J].赤峰学院学报(自然科学版), 2011,6: 47~49. [9]降爱莲,谢克明.压入新、旧区段的区域填充扫描线算法[J].计 算机工程与应用,2006,17: 43~45. [1o]降爱莲.重写区段左端点的4向填充扫描线算法[J].太原理工 大学学报,2OO6,31(3): 277~280.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 武汉 学院 计算机 图形学 论文 基于 扫描 填充 算法 改进型 区域 实现