毕业设计（论文）-填充算法论文.doc

《毕业设计（论文）-填充算法论文.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-填充算法论文.doc（27页珍藏版）》请在三一文库上搜索。

1、江西理工大学 2014 届本科毕业生设计（论文） 1 摘 要 区域填充问题在计算机图形中是很常见的，是个很基础，务必解决的问题， 尤其是在图像处理的过程中。一般来说，要对一幅图像进行处理就必然会用到 许多算法，而区域填充就是其中的基本算法之一，不仅如此，区域填充在图像 处理目标分析图形压缩机及计算机图形学其他分支中也有广泛的应用。所 以从图形学发展到现在，区域填充一直受到许多学者的青睐，他们不停的探索 和研究区域填充算法，如今几经出现了很多的区域填充算法，包括传统的区域 填充算法和改进的区域填充算法。传统的区域填充算法的填充出来的结果是不 够完善的，还存在很多的不足，而且算法的效率也很低，本论

2、文就是在介绍扫 描线填充算法和种子填充算法的基础上，结合两者的优点，然后指出自动填充 算法，这种填充算法具有的最大优点是适用于任何复杂的区域。实现这种算法 的方法有两种，一种是基于缝隙码的，另一种是基于链码的，经过填充效率测 试和评估，相较以前都有不少的改进，所以他们都属于改进型的区域填充算法。 本文最后基于求封闭图形面积的思想提出了基于曲线积分的区域填充算法，该 算法最大的特点就是能填充任何封闭区域，算法速度较快，而且填充效率也很 高，能适应各种图形的区域，填充结果的重复性也相当的好，该算法与其他区 域填充算法的最大不同是，它是通过图形图像的轮廓边界像素点来判断是否为 区域的内点，传统的算法

3、则是需要不断重复判断像素点是否为区域内的点。我 们知道，多边形填充算法要求区域的形状是简单点的，它是对区域形状有一定 限制的；而种子填充算法的首要条件是知道区域内的一点，并把它作为种子， 其次还要判断像素点是否在区域内，这个判断过程是不停的重复的，直到找到 全部的区域内像素点，而基于曲线积分的区域填充算法则可以从根本上克服这 两种填充算法的弊端。 关键词：计算图形学；区域填充；填充算法；曲线积分： 江西理工大学 2014 届本科毕业生设计（论文） 2 ABSTRACT In this paper .Region filling algorithm is one of the basic pro

4、blem of computer graphics .image region filling algorithm is basic algorithm of image processing .and is widely used in image processing .target analysis .graphics compressor and computer graphics . So area filling has been research hot spots .Traditional region filling algorithm is incomplete filli

5、ng results and algorithm efficiency is not high question .the analysis of the two traditional area filling algorithm principle .introduces four kinds of the improved area filling algorithm respectively .and on the efficiency of these algorithms were analyzed .and on this basis .put forward a new geo

6、metry area filling algorithm .this algorithm is based on the curve integral and closed area .the basic principle of the algorithm is fast computing speed .strong adaptability graphics .good repeatability and dont need to fill results area points repeated judgment can fundamentally overcome the polyg

7、on filling algorithm for regional shape has certain limitation speed filling algorithm requires know area as well as to the pixels in the area of the disadvantages of repeated judgment the algorithm can accurately adapted to any kind of scanning the boundary curve area filling process. Key words: Ca

8、lculation of graphics: Area filling: Filling algorithm: Sean line algorithm: 江西理工大学 2014 届本科毕业生设计（论文） 3 第一章 绪论 1.1 区域填充的背景、目的和意义 所谓区域填充就是先找到一个种子，这个种子通常就是区域内的一点，然 后将种子点的颜色设定为指定的颜色，最后让种子“成长” ，不断扩展延伸直到 整个区域都变为同种子一样的颜色。区域填充所用到的算法也是计算机图形与 图像处理的基本算法之一，在图像处理目标分析图形压缩机及计算机图形 学其他分支中也有广泛的应用。所以在图形学方面，区域填充一直受到国内

9、外 许多学者的青睐，成了他们探索与研究的热点。在光栅图形学中，点阵形式的 点的集合就叫做区域，区域要具有一定的连通性是区域填充算法的前提，它要 求该区域要么是 4 连通区域，要么是 8 连通区域。 传统的填充算法有很多种，其中种子子填充算法和扫描线填充算法都是比 较有名的。种子填充算法要求区域是四连通区域，或者是八连通区域，言而总 之区域要有一定的连通性。种子填充存在着算法效率低的缺点，而且许多像素 都要经过数次入栈，还存在着存储相邻的点时需要消耗很多的栈空间，不仅如 此，当要对许多的对象进行填充时，种子点会一个一个的选取，这无疑就降低 了算法的效率，在某些复杂的情况下，选择种子点也是相当的困

10、难的。而在扫 描线填充算法中，要就计算出每条扫描线和多边形相交的交点，不仅这计算量 是非常大的，而且效率也很低，而多重交点很有可能就是多边形的交叉点，这 就容易出现在统计交点数目时出现统计错误，而且由于多边形形状的不规则， 多边形很有可能出现水平直线状的边，这时候也会导致判断错误。 江西理工大学 2014 届本科毕业生设计（论文） 4 第二章 计算机图形学的发展和应用 2.1 计算机图形学的简介 计算机图形学研究的就是图形在计算机中的表示（包括存储方式等） ，图形 在计算机中的计算和处理和显示。通俗来说就是利用数学模型转化为图像并在 计算机中显示的一门学科，只不过在整个实现过程中都依据图形的生

11、成原理。 点、线、面、体等几何元素构成了计算机图形学中的图形，灰度、色彩、线宽 等几何属性是图形的重要属性。依照处理计算角度进行分类，图形通常分为几 何图形（图形都是由线条表示的，例如线框图）和明暗图（即是我们平时所说 的真实感图形） ，我们知道一幅栩栩如生的真实感图形图像可以简简单单的由计 算机来产生，所以说真实感图形也是计算机图形学的又一个主要研究领域。因 此，建立所需图形的表示与描述方式是必须的，然后再用某种光照模型，算出 自己设想的所需要的光源、纹理与材质的光照效果这个从侧面也说明计算机图 形学和计算机辅助设计几何图形关系十分密切。事实上，图形学的主要研究内 容可以用“技术”两个字来表

12、述，这里所说的技术指的是用几何场景表示的曲 面造型的技术和实体造型的技术。该技术的目的是实现图形图像的数字化表示。 这从侧面反映了计算机图形学与计算机图像处理的密切关系。 2.2 计算机图形学的发展史 （1）开创阶段（50 年代60 年代） 1950 年，麻省理工（MIT：Massachusetts Inst.of Technology）学院设 计出了第一台图形显示器，它作为计算机旋风 1 号的附件。这个显示器的原理 是用 1 个阴极射线管 CRT（类似于示波器的阴极射线管）来显示一些简单的图 形。在 1958 年，图形学的发展有了一个大的突破，就是 Calcomp 公司研究出了 滚筒式绘图仪

13、，这个绘图仪是联机式数字记录仪的升级版，也是在这年， Gerber 公司研制出了平板式绘图仪，这个仪器的基础是数控机床。在二十世纪 50 年代末期 MIT 学院的实验室，更确切来说是林肯实验室，研发了 SAGE 空中 防御体系，这是首次实现的空防体系，这个防御系统的实现环境是上文提到的 旋风号计算机，这是 CRT 显示器的第一次使用，它不仅有指挥的功能，也具有 控制的功能。在整个二十世纪 50 年代，计算机图形学都是处于准备阶段，属于 我们现在所说的“被动式”发展期。 （2）迅速发展阶段（60 年代初60 年代末） 1962 年，题为“Sketchpad“的一片博士论文出版了，在这片论文中系统

14、 的详细的阐述了人机交互通信的图形系统，它是由 MIT 林肯实验室的 江西理工大学 2014 届本科毕业生设计（论文） 5 Ivan.E.Sutherland 发表的，在文中第一次提出了计算机图形学“Computer Graphics”的概念，并验证了交互计算机图形学是一个极具潜力的和实用性的 研究领域。同年，计算机图形学的一大理论-Bezier 曲线曲面的理论首次被 提出当时的 Pierre Bezier 是雷诺汽车公司顶级的工程师，他作为公司员工， 最成功的地方就是开发设计并实现了高级的 UNISURF 系统。该系统是用来设计 汽车外形的，它用到的理论基础是几何外形理论。两年之后，MIT

15、的教授 Steven A.Coons 首次提出了超限插值的新想法，这个方法就是借助插值构造出 的任意的四条边界曲线来构造曲面。他们成了 CAGD，CAD 的先驱。 （3）发展兴盛时期（70 年代80 年代） 在 70 年代，计算机图形学的发展进入一个飞速发展的的时期。首先是光栅 显示器的出现，使得图形学提早进入发展新高潮，也就在这个时期，各种实用 的 CAD 图形系统逐渐出现在人们视野。由于计算机图形学的飞速发展，区域填 充、基本几何的生成，图形旋转等一系列算法与概念纷纷产生。1974 年，为了 使得图形学标准化，成立了图形标准化委员会，成立不久该委员会便制定并出 版了“核心图形系统” ，之后

16、国际组织先后发布了各种标准，包括接口标准 CGI，文件标准 CGM，核心系统 GKS 及层次交互标准 PHIGS。 在 70 年代，由于实感图形学的出现以及实体造型技术的产生，促进了光栅图形 学发展。在明暗问题这一领域方面，提出了第一个反射模型，该模型是在 20 世 纪 70 年代年由 Bouknight 提出的。与此同时 “漫反射模型+插值”的思想也被 提出了，它是由 Gourand 提出，所以后人都称之为 Gourand 明暗处理。到了 1975 年，简单光照模型被 Phong 提出了，后人干脆将该模型命名为为 Phong 模 型，这些都为真实感图形学的开创奠定了基础。 （4）发展成熟阶段

17、（80 年代至今） 在 1980 年 Whitted 提出的一个光透视模型，即我们通常所说的 Whitted 模 型。他利用光线跟踪的算法成功的实现了自己的模型-Whitted 模型。1984 年， 真实感图形显示算法已逐渐成熟，成熟的标志是光线跟踪算法和辐射度算法的 提出，通过辐射度方法研究人员成功地模拟了理想条件下的漫反射表面间的多 重漫反射效果。在二十世纪 80 年代中期以来，超大规模集成电路的出现与发展， 为图形学的飞速发展提供必要的物质条件。另一方面，随着硬件的发展，计算 机的运算能力的大大的提高了，图形处理速度相应加快，无疑使得图形的各个 研究方向都得到了充分的发展。 到了 90

18、年代中期以来，随着个人 PC 和相应软件的普遍使用，图形学的各 个领域的应用也日趋广泛，这时候图形学已经不是以前的图形学了，变为了集 模式识别、人工智能、虚拟现实于一身的一门学科了。计算机图形学之所以能 在短短的几十年中获得飞速的发展，是因为这门学科能够传递很多信息，成为 江西理工大学 2014 届本科毕业生设计（论文） 6 了传递信息的一个重要媒介。 2.3 计算机图形学的应用 （1）计算机辅助设计与制造（CAD/CAM） 要进行产品设计和制造，就必须借助计算机技术和手段来获得和运用各种 数字信息与图形信息。CAD/CAM 和计算机图形学是紧密联系在一起的。CAD/CAM 是计算机图形学在工

19、业界最具活力的领域，也是应用最广泛的领域。目前，较 多用于飞机、汽车、船舶的外形制作和工厂布局如化工厂等布局以及电子线路， 电子器材等，在电子工业中计算机图形学应用集成电路、印刷电路板、电子线 路和网路分析等方面的优势十分明显。试想一下，用手工设计和绘图一个很复 杂的超级大规模的集成电路板得花多少人力，物力，财力呢，而且能不能画出 来都是个问题，但是若果使用计算机的图形系统相较于人工方法，就能很快进 行图形设计与图形绘画，也就是说我们能够在比较短的时间完成以前长时间才 能完成的工作，自然其相应的后续处理也跟着提前，大大节约了我们时间成本。 基于工程图纸的 3D 形状体积重建（即是从 2D 图形

20、中找出信息然后提取出 有用的 3D 信息，然后通过对信息的分类处理，综合组合等步骤，在 3D 空间恢 复对应二 D 信息，并构建出形体的点，线，面及其相应的拓扑关系，实现重构） 是 CAD 应用领域中的一个重要研究方向。其实我们现在都知道二 D 图纸设计在 工程，建筑，造价，机械制造等方面任然占据主导地位，工程上有非常多的旧 的透视图和投影图片可以利用和借鉴，实际上有许多新的设计是可以凭借对原 有设计的吸收理解，并在其基础上做出相应的合适的修改即可成为新的设计应 用。但是，随着 3D 技术的大热，CAD 技术的发展方向应该变为三 D 几何造型方 向了。但是，在 3D 形体重建还存在理论上的不足

21、，例如任意曲面的 3D 形体重 建就未能实现，因为，这仍然是当今数学家迄今未解决的世界性难题。 （2）科学计算可视化 计算机硬件每 18 个月就更新一代了，硬件上的发展带动了科学技术的飞速 发展，随着大量的数据与日益剧增的数据使得人们对数据的分析和处理变得越 来越难，不过如果能将这些海量的数据以图形图表的形式表示出来，就会方便 人们寻找大数据中存在的规律。科学计算可视化（Visualization in scientific computation）就是将大量数据以图形的方式可视化出来的一种技 术，该技术涉及到许多的学科，它不仅要用到计算机图形学、图像处理这两门 学科，还要用到计算机视觉、计算

22、机辅助设计等众多学科。计算机科学可视化 的实质就是，大数据图形化表示-计算机显示人通过视觉功能理解 大数据。数据可视化可应用于医学、流体力学、有限元分析、气象分析当中， 江西理工大学 2014 届本科毕业生设计（论文） 7 特别是在医学领域上，可视化有着广阔的发展前途。 （3）计算机艺术 放眼世界当今的美术，艺术人员，尤其是从事商业艺术的人员都是精通计 算机技术的，并且他们热衷于使用计算机软件来实现图形的设计与绘制，也可 以说是从事艺术创作。目前适合他们用的用于美术创作的软件有很多很多很多， 例如，用于 2D 平面图形图像处理的软件有 CorelDraw,Photoshop,PaitShop

23、等 等，而用于专门的图表绘制工具有如 Viso 之类,3D 建模方面和渲染方面的软件 工具有如 3DMAX，Maya 等等，还有一些其他专门用于生成动态图形图像的软件 有如 Alias，Maya，SoftImage，flash 等等。 （4）图形用户界面 图形用户接口就是人们获得计算机使用权的接口。一个容易使用的用户界 面称之为友好的图形化的用户界，有了图形化用户界面，人们在使用计算机及 计算机应用软件是就很方便了，简单来说就是图形用户界面大大的提高了软件 的易用性。我们不妨回顾一下或者不妨想象一下，在 DOS 时代，没有图形界面， 一切都是通过命令行的方式操作计算机，那时的计算机易用性是很差

24、。但是编 写一个图形化的界面是需要花费大量的人力，物力，财力和时间的，在过去， 都是用传统的应用软件来编写项目的，这时候还必须有用于实现与处理和用户 接口相关的问题和功能的代码，这些代码加起来就占了整个代码的 60%，所以 说那是计算机软件的易用性是很差的。但进入 80 年代后，随着 Windows 操作系 统的普及，图形学已经完全融入到了计算机的方方面面。人机交互技术通常是 以 WIVP 为特征的图形用户界面。 （5）真实感图形绘制与自然景物仿真 在计算机图形学中真实感绘制是指将真实世界的场景重现在计算机屏幕上。 那么真实感绘制需要解决哪些问题呢？其实它是以模拟真实物体的物理属性 （例如长，

25、宽，高，亮度，曲率等）为主要任务的。若果从光照模型的角度来 考察真实感图形，它包括简单光照模型和局部的光照模型及整体的光照模型。 从绘制方法上看有光线跟踪算法和辐射度算法。加速算法是真实感绘制中一个 不可或缺的研究重点，加速度算法指的是什么呢？简单来说就是要将接近真实 物体的图形在最短的时间内画出来。物体网络模型的面片简化和基于图形的绘 制是当前真实感图形图像实时设计与绘制的两大热点，十分值得研究。 （6）虚拟现实 虚拟现实技术，简单的说，在计算机中模拟营造出现实环境。它是一门设 备间交互的新技术。能够通过虚拟现实技术在计算机中模拟出如飞机驾驶舱之 类的现场。同时用户还可以应用各式传感器使自己

26、投入到模拟的环境中，从而 让用户直接对该环境实施交互操作，并将现实世界中的信息反馈过来，使人们 江西理工大学 2014 届本科毕业生设计（论文） 8 在计算机的屏幕上感受真实世界到。虚拟现实其实说白了就是一门多学科交叉 的新技术。它集电子，传感，测量，仿真，多媒体，微电子，计算机图形等计 算机技术于一身。而在计算机技术中，又包括计算机图形图像学，物体仿真， 智能系统，网络互连，物联网，互联网，人机接口，UI 设计等计算机技术。而 以上提到的计算机技术的发展推动了虚拟现实技术的进步，反过来，虚拟技术 的兴起也促进相关计算机技术的发展，也推动了其在其他领域的应用，例如在 教育上、医疗上、娱乐影音上

27、、科技生产上、工业制造上，建筑上和商业上。 （7）计算机动画 随着计算机图形学的不断发展，计算机硬件也不断发展，运算速度大幅度 的提高，这时人们已经不满足于单纯的静态图形图像了，他们也开始追求一幅 幅动起来的图像吧画面，在这种情况下如何利用计算机使得图像画面动起来就 成了一个新的研究方向。计算机动画实质是使一幅一幅静态的图像（这些图像 都是会对前一幅图像做出一小部分修改的） ，然后使这些画面快速连续播放，利 用人的视觉残留效应，就会产生动态的场景。 就发展历史而言，是卡通片催生了早期的计算机动画的产生，主要原理是 生成几幅关键帧（所谓关键帧就是在动画中起着关键作用的静态图像） ，之后， 利用计

28、算机对相邻关键帧之间进行插值，生成若干幅中间帧，使得中间帧关联 起关键帧。在连续播放时，一定的速度下，有一定间隔的 2 个关键帧就被有机 的结合起来了。说到内容，在计算机动画方面可谓是多姿多彩，计算机动画发 展了这么久经过一个个人的努力，现在实现动画的方法也有多种了，例如有图 像变形，2D 形状混合实现，轴旋转变形的方法，2D 自由形体变形法（FFD Free-From Defonnation）等。就目前而言有种崭新的方法，它是借助物理模型 来实现一幅幅图像动起来的效果的，这种方法需要用到许许多多的弹性力学方 程和流体力学的方程来计算出动画过程中最能体现适合真实世界的运动规律。 江西理工大学

29、2014 届本科毕业生设计（论文） 9 第三章 区域填充算法的原理和方法 3.1 区域填充基本知识 在计算机图形学中，有两种方法表示多边形：一种是顶点法，这种方法记 录的是多边形的顶点序列，特点是直观，占内存少，易实现，缺点是不能直接 对多边形进行填充，而是需要先对对多边形进行扫描以确定是否为内点；另一 种是点阵法，这种方法记录的是多边形所覆盖的像素点，特点是能直接判断是 否为内点，方便填充，缺点是无法明确表示多边形的几何信息。 在多边形中，若果它的表示是从顶点法转为点阵法，则称这个过程为多边 形的扫描转换，多边形有凸多边形（所谓凸多边形是指，图形中任意两点之间 的连线所形成的线段都在该多边形

30、内的图形）和凹多边形（所谓凹多边形是指， 图形中存在两点之间的连线所形成的线段不在该多边形内的图形）之分。 3.2 传统的区域填充扫描线算法 扫描线填充算法的基本思想：首先按顺序（通常是按扫描线先后顺序）计 算出多边形边界与线的交点，其次是根据交判断哪些点是在区域内哪些是在区 域外，最后就是用特定颜色显示边界内的像素。考察每一条扫描线，因为每一 条线与多边形的交点都是成对出现的，如图 3-1,y=8 的这条扫描线与多边形 江西理工大学 2014 届本科毕业生设计（论文） 10 的边界交点为 A，B，C，D，则扫描线上 A、B 点，C、D 点 pppppp 543210 之间的像素都位于多边形之

31、内，都是多边形的内的，所以 A、B 为一个填充区段， C、D 为一个填充区段。对 A,B 与 C,D 这两区内点所有像素按要求的颜色进行 设置显示，这就是完成一条线的填充工作，循环以上的步骤，继续下一条扫描 线来实现填充，直到政府图像都填充完成。 以下 4 个步骤，是多边形的每条扫描线的填充过程： （1） 求交点：就是交点-这些交点是计算扫描线和多边形各边形成的 （A、D、C、B） （2） 交点排序：把（1）中得到的所有交点按一定的顺序排列，这里是以递增 的顺序进行排序的(A、B、C、D) （3） 交点配对：相邻的两个交点进行配对，第一个和第二个交点配对，第三 个和第四个交点配对，如此下去，很

32、容易想象每对交点区段都是计算机 扫描线与多边形重合的区间，准确来说就是一个两者相交的区间(A、B) (C、D) （4） 区间填色：把（3）得到的那些相交区间里面的所有象素点设置成多边形 颜色，相反，把相交区间外的所有的象素设置成与背景一致的颜色。 但扫描线法还存在以下两个个问题： 问题一：只有当交点的个数是偶数时才能确保填充的正确性 问题二：多边形边界上像素的取舍问题，即如何避免填充扩大化？ 针对问题一的我解决方法是：确定两相邻边与扫描线的位置关系。若扫描线只 经过顶点的时候，且多边形的两条那边分别都位于扫描线的两侧，这时交点的 个数就按一个来计算；当多边形的两条边都位于扫描线的上方，这时交点

33、个数 就按两个来计算；当多边形的两条边都位于扫描线的下方，这时交点个数不计 图 3-1 多边形 PP0510 . PP 江西理工大学 2014 届本科毕业生设计（论文） 11 算。而当扫描线和多边形的水平边重合时，可不考虑该情况，即不计算交点个 数。 针对问题二的解决方法是：规定落在右边界和上边界的像素点都不进行填充， 而落在左边界和下边界的像素点必须进行填充。 为了提高扫描线的效率，每当处理一扫描线时，可将之相交的边进行求求 交。在计算机图形学中，称这样的多边形边为活性边，然后将多边形的活性边 与交点横坐标值按递增顺序放于同一链表中，我们称这样的链表为活性边表 （AET） 。如图 3-3 图

34、图4 4. .4 40 0 多多边边形形 P P1 1 P P5 5 P P4 4 P P3 3 P P2 2 O O1 12 23 34 45 56 67 78 8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 图 3-2 多边形 6 62 20 0 P P4 4P P5 5 A AE ET T指指针针 5 5 7 7. .5 5 0 0. .5 5 P P3 3P P2 2 扫扫描描 线线 4 4 6 62 20 0 P P4 4P P5 5 A AE ET T指指针针 7 78 8 - -1 1 P P2 2P P1 1 扫扫描描 线线 5 5 7 72 24 4 P P5 5

35、P P1 1 A AE ET T指指针针 7 77 7 - -1 1 P P2 2P P1 1 扫扫描描 线线 6 6 图图4 4. .4 42 2 活活动动边边表表 图 3-3 活性边表（AET） 江西理工大学 2014 届本科毕业生设计（论文） 12 我们假定扫描线与活性边的交点的横坐标 x 相交点的横向坐标用英文字母 X 表示,那么下一条扫描线与这活性边的交点就没有必要重复花时间计算了，只 要增加一个适当的增量即可，这里我们用符号 X 表示，下面，我们就利用数 学知识推导上面这个结论。 假设多边形的那一条边的直线方程为：，而当前扫描线以及0cbyax 下一条扫描线与这条边的交点分别用英文

36、字母组表示、则： y x i i, y x i i 1 1, 0cba y x i i 0 1 1 cba y x i i 由此得 cb a y x i i 1 1 1 由于，所以：1 1 yy ii ; a b cb a x y x i i i 1 1 1 其中， 为常数。abx xx ii / 1 在增量法进行计算时，我们需要知道一条边不会再下一条扫描线相交是在 什么时候，这方便我们及时把该边从活性边表中删掉。综上所述，活性边表的 结点应为对应边保存如下内容：第 1 是保存当前扫描线与多边形的那一条边的 交点的横坐标的值 X；第 2 是保存从当前扫描线与下一条扫描线间的局部增量 的值 X；

37、第 3 项保存这一条边的所交的最高的扫描线的号码y max 在实际操作的过程，为了方便建立于更新活性的边表，我们需要多做一步， 那就是建立一个边表，该边表是特意为每一条计算机扫描线建立，是专门用来 保存边信息的，这里用单词 NET 表示，而且将它放在这条扫描线的第一次出现 的边上。换句话说就是，如果存在一条边的比较低的端点这里用表示，那 ymin 么这条边就存放在扫描线的新边表 NET 中，如图 3-4 ymin 7 72 24 4 7 78 8 - -1 1 6 62 20 0 3 36 6 - -2 25 56 60 0. . 5 5 1 1 5 5 4 4 3 3 2 2 6 6 7 7

38、 P P 5 5P P 1 1 P P 2 2P P 1 1 P P 4 4P P 5 5 P P 3 3P P 4 4 P P 3 3P P 2 2 ? ? 4 4. . 4 41 1 ? ? ? ? ? ? ? ? ? ? ? ? 江西理工大学 2014 届本科毕业生设计（论文） 13 算法过程： Void polyfill (polygon,color) int color；多边形 polygon for(每一条扫描线 i) 对新边表头指针 NETi进行初始化； 在新边表 NETi中存放 Ymin=1 的边； y=最低扫描线号； 初始化活性边表 AET 为空； For(各扫描线 i) 把

39、新边表 NETi中的边表点使用排序法，这里使用插入 排序法进行插入 AET 表，使之按横坐标的值 X，的递增顺 序排列； 遍历 AET 表，把互相配对的交点的相应的区间（左闭右开） 上的像素（x，y）,用函数 drawpixel(x,y,color)实现像 素的改写并改变颜色值； 遍历 AET 表，并将 Ymax=i 的结点从 AET 表中删除，同时 把 Ymaxi 结点的按 x 值递增 X； 若允许多边形的边自己与自己相交，则用冒泡排序法对 AET 表重新排序； 扫描线算法具有一定的局限性，用它来填充的区域都是标准的比较简单的 区多边形，比如圆，椭圆以及其他一些简单的多边形，当填充这些多边形

40、时， 算法的效率较高，但填充出来结果不具有较好的完备性，且对区域轮廓线的形 图 3-4 扫描线的新边表（NET） 江西理工大学 2014 届本科毕业生设计（论文） 14 状有一定要求，在复杂区域进行填充是时，通常不能进行正确的处理，也不能 得到正确的填充结果。 3.3 传统的种子填充算法 种子填充指先将区域的一点赋予指定的颜色，然后将这颜色扩展到整个区 域的过程，种子填充算法的另一种叫法是边界填充算法，有一定连通性的区域 才能用种子填充算法进行填充，不然就会失效，种子填充算法的基本思想是： 首先假定区域由封闭轮廓线围成，且已经给出了轮廓线内某一点是，然后开始 搜索区域轮廓线内的其他点，但被收索

41、的点要求是和种子点相邻的。如果轮廓 线内没有收索到相邻的点，则说明已经到轮廓线的边界；如果在轮廓线之内收 索到了相邻的点，那么这个相邻点就成了新的种子点，继续搜索下去。算法从 一个像素点开始，而且该像素点必须位于多边形的内部，该算法要检测该像素 点的颜色，如果它与边界色不同，也和填充色不相同，那么就用填充色显示该 点，然后检测与它相邻位置，来确定他们是否是边界色和填充色，如果不是， 就填充这个相邻相邻点。这个过程要一直进行下去，直到将所有位于区域边界 范围内的像素都检测完为止。 八连通域或四连通域的区域都很适合用种子填充算法进行填充操作。四连 通域，就是从区域内任意一点出发，通过左，右，上，下

42、四个方向就能到达区 域内的任意一个像素点，这种填充算法称为四向连通算法；而所谓八连通域指 的是区域内的任何一个像素，都可由从区域内任意一点，通过它的坐标轴方向 和对角线方向（即上，下，左，右，左上，左下，右下，右上八个方向）而达 到，这种填充方法我们通常叫做为八向连通算法。 种子填充的算法相当的简单，且很容易实现，相比于扫描线填充算法，种 子填充算法可以对复杂区域进行填充，填充结果的完备性也教好，但不足的是 有些像素可能会多次的入栈，这无疑算法效率大打折扣，而且要实现一个栈结 构就要耗费相当大的存储空间，不仅如此区域内每一像素都需要一次递归，进/ 出栈，既费时也费内存。 34 几种改进的区域填

43、充算法介绍 （1）适用于任何复杂区域的全自动填充算法 随着图像信息的广泛应用，人们对图形自动化处理程度的要求越来越高， 从遥感影像的计算机自动化处理与识别可见一斑。具有通用性的算法与自动化 程度这两个问题已经在图像自动处理方面变得更受关注，甚至比效率也更受关 注，文献【1】提出一种注入式反像填充算法（ICF） 。该算法在种子填充算法的 基础上进行改进，能适用于任何复杂区域的全自动填充。 注入式反向填充算法，其基本思想是先填充目标区域外的像素，且先从一 江西理工大学 2014 届本科毕业生设计（论文） 15 个像素点开始，逐个逐个点实现直到形成整个目标区域的逻辑非区域。ICF 的 基本原理是由边

44、界轮廓线提出信息得到轮廓线围成的图形的最小的外接矩形， 根据的就是边界的轮的廓序列点，并将上述的那个外接矩形向四个方向（即是 通常我们说的上、下、左、右四个方向）都各自扩展一个像素点，使得区域填 充的图形的轮廓边界上的所有的点序列都在目标填充区域逻辑非区域简单而言 就是其外部的非目标的待填充区域上，不难想象，这样就可以取出上述矩形边 界轮廓上的任意一在边界上的像素点，这个特殊的像素点即是就是作为初始的 种子点的，注意是在非目标填充区域中的，在确定了上文提到的非目标填充区 域的初始像素点（就是上述的种子点）之后，我们需要创建一个栈准确来说是 一个堆栈，然后就是将前面所说的种子点 push 到栈里

45、面，在所建的存有种子点 的堆栈不是空的时候就 pop 出当时的栈顶的种子点进行区域像素填充，之后就 以这个种子点的像素点为新的中心点，之后向（8-领域）遍历查找出还没有实 现填充的而且还是没有入栈的像素，并将该区域中的全部满足前面所说条件的 像素点全部 push 进入栈。循环执行“栈顶像素出栈填充查找新种子种子 点压栈”的操作，一直至到所建的存储种子点的栈变为空的堆栈为止。当按照 上述的方法实现了将非目标区域填充后，根据填充结果将矩形区域的进行逻辑 非的意义实现取非操作（就是将非目标区域取反变为填充的是目标区域） ，以此 实现对目标图形的所需区域填充。 适用于任意复杂区域的全自动填充算法的优点

46、是引入了填充区域边界图形 的最小外接矩形，使得初始种子点的确立完全是由计算机自主实现的而非人为 特定选定的，这就是上文有提及的具有完全自动化以及具有普遍适用性这两个 特点的区域填充算法，这个 ICF 算法的优点就是能够快速高效地对含有很多个 具有独立性的目标进行快速高效的令人满意的区域填充，并且当图形密集分布 也具有令人满意的效率；但是缺点是对于有空洞的区域，上述的算法处理起来 就比较麻烦了，不但需要将待填充区域的内边界以及外边界都需要实现自动的 填充，而且还需要将以上的内边结果与外边结果都进行逻辑与运算，才能得到 我们真实想要的填充结果。 （2）一种基于缝隙码的区域填充算法 在文献【2】提出

47、的一种基于缝隙码的区域填充算法，并给出了单条缝隙码 的填充算法及多连通区域或整幅图像的快速填充算法。区域边界的缝隙码可以 按如下方法表示：沿着图像边界像素的边逆时针或顺时针行走一周，依次将它 的方向码记录下来，就得到了区域边界像素的缝隙码，并加上起始点的坐标， 则边界就可用缝隙码唯一的确定下来。 所谓的单条缝隙码的填充算法就是先进行缝隙码的遍历，这样的用意就是 为了确定边界轮廓的右像素点以及左像素点，并计算围线角度，确定围线方向； 江西理工大学 2014 届本科毕业生设计（论文） 16 然后填充的起始点就是由所有遍历所得的左像素点所确定的，这里的填充分为 三步实现，首先，对于区域内部边界，是依

48、照由右到左的方向进行填充的，循 序一直到右边的所有的像素点结束，其次是，对于区域外部边界，是依照由左 到右的方向进行填充的；最后就是剩下填充边界的像素点了。 这里再来介绍一下多连通区域的填充算法或者适用于全图像填充的算法， 第一就是，运用遍历方法，遍历出所有的相关链码，这是用于确定图形轮廓边 界的所有像素点的，而且主要是要区分出左边像素点和右边像素点，然后遍历 所有边界像素点，注意，是所有区域的轮廓与边界像素点，若检测的像素点是 作为左边像素点的，则是依照由左到右的方向进行填充，循序一直到右边的所 有的像素点结束，然后是填充待填充的图像的内部区域像素点，最后就是填充 边界像素点，注意像素点是所

49、有区域中的。 单条缝隙码填充算法的优点是对单连通区域的图像进行填充时，能进行很 好的填充；缺点是会出现空洞或者是重复不断填充的问题，这是因为在待填充 图形图形中存在多连通区域，就是说检测的边界存在复杂的关系，例如是包含 关系。而且还有另一个问题就是对于比较复杂的图形图像难于准确获取边界的 缝隙码，这样就容易导致乱码，乱码是会导致填充混乱的。而多连通区域填充 算法或全图像的区域填充算法是能够有效避免以上问题的，因为这个算法只会 对待填充的区域内部的像素填充，而对区域以外的一切像素点（包括空洞）都 不会进行填充的，所以，这也是能够适用于单连通区域的填充的。 （3）基于链码的填充算法 文献【3】提出了基于计算机图形学栅栏填充算法的，给出了一种新的基于 链码的填充算法。该算法的思想是先根据边界的 Freeman 链码，求出栅栏，这 个栅栏实际上是由图像区域中的水平方向的中分线来决定的。首先我们需要定 义一个分类表，是关于新轮廓边界点的表，然后依据边界点进行分类，将轮廓 边界上的点分为图形