平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即给出一个区域的边界(也可以是没有边界,只是给出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充)。区域填充中最常用的是多边形填色,本文中我们就讨论几种多边形区域填充算法。
一、种子填充算法(Seed Filling)
如果要填充的区域是以图像元数据方式给出的,通常使用种子填充算法(Seed Filling)进行区域填充。种子填充算法需要给出图像数据的区域,以及区域内的一个点,这种算法比较适合人机交互方式进行的图像填充操作,不适合计算机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式,种子填充又可细分为几类,比如注入填充算法(Flood Fill Algorithm)、边界填充算法(Boundary Fill Algorithm)以及为减少递归和压栈次数而改进的扫描线种子填充算法等等。
所有种子填充算法的核心其实就是一个递归算法,都是从指定的种子点开始,向各个方向上搜索,逐个像素进行处理,直到遇到边界,各种种子填充算法只是在处理颜色和边界的方式上有所不同。在开始介绍种子填充算法之前,首先也介绍两个概念,就是“4-联通算法”和“8-联通算法”。既然是搜索就涉及到搜索的方向问题,从区域内任意一点出发,如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素,则用这种方法填充的区域就称为四连通域,这种填充方法就称为“4-联通算法”。如果从区域内任意一点出发,通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素,则这种方法填充的区域就称为八连通域,这种填充方法就称为“8-联通算法”。如图1(a)所示,假设中心的蓝色点是当前处理的点,如果是“4-联通算法”,则只搜索处理周围蓝色标识的四个点,如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点,还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1(b)和图1(c)所示,假如都是从黄色点开始填充,则“4-联通算法”如图1(b)所示只搜索填充左下角的区域,而“8-联通算法”则如图1(c)所示,将左下角和右上角的区域都填充了。
图(1) “4-联通”和“8-联通”填充效果
并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好,应该根据应用环境和实际的需求选择联通搜索方式,在很多情况下,只有“4-联通算法”才能得到正确的结果。
1.1 注入填充算法(Flood Fill Algorithm)
注入填充算法不特别强调区域的边界,它只是从指定位置开始,将所有联通区域内某种指定颜色的点都替换成另一种颜色,从而实现填充效果。注入填充算法能够实现颜色替换之类的功能,这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单,核心就是递归和搜索,以下就是注入填充算法的一个实现:
164void FloodSeedFill(int x, int y, int old_color, int new_color)
165{
166 if(GetPixelColor(x, y) == old_color)
167 {
168 SetPixelColor(x, y, new_color);
169 for(int i = 0; i < COUNT_OF(direction_8); i++)
170 {
171 FloodSeedFill(x + direction_8[i].x_offset,
172 y + direction_8[i].y_offset, old_color, new_color);
173 }
174 }
175}
|
for循环实现了向8个联通方向的递归搜索,秘密就在direction_8的定义:
15typedef struct tagDIRECTION
16{
17 int x_offset;
18 int y_offset;
19}DIRECTION;
|
79DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1} }; |
这个是搜索类算法中常用的技巧,无需做太多说明,其实只要将其替换成如下direction_4的定义,就可以将算法改成4个联通方向填充算法:
80DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; |
图2就是应用本算法实现的“4-联通”和“8-联通”填充效果:
图(2) 注入填充算法实现
1.2 边界填充算法(Boundary Fill Algorithm)
边界填充算法与注入填充算法的本质其实是一样的,都是递归和搜索,区别只在于对边界的确认,也就是递归的结束条件不一样。注入填充算法没有边界的概念,只是对联通区域内指定的颜色进行替换,而边界填充算法恰恰强调边界的存在,只要是边界内的点无论是什么颜色,都替换成指定的颜色。边界填充算法在应用上也非常的广泛,画图软件中的“油漆桶”功能就是边界填充算法的例子。以下就是边界填充算法的一个实现:
177void BoundarySeedFill(int x, int y, int new_color, int boundary_color)
178{
179 int curColor = GetPixelColor(x, y);
180 if( (curColor != boundary_color)
181 && (curColor != new_color) )
182 {
183 SetPixelColor(x, y, new_color);
184 for(int i = 0; i < COUNT_OF(direction_8); i++)
185 {
186 BoundarySeedFill(x + direction_8[i].x_offset,
187 y + direction_8[i].y_offset, new_color, boundary_color);
188 }
189 }
190}
|
关于direction_8的说明请参考上一节,图3就是应用本算法实现的“4-联通”和“8-联通”填充效果(其中颜色值是1的点就是指定的边界):
图(3) 边界填充算法实现
<下一篇:扫描线种子填充算法>
分享到:
相关推荐
资源内容:通过键盘按键,实现正方体的移动,伸缩,旋转等变换 语言:C++ 运行环境:Visual Studio 2013/更高版本
主要介绍了Android多边形区域递归种子填充算法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
该程序演示了包括逐点判别填充、种子递归填充、扫描线填充、活性边表算法在内的多种填充算法测试,用户先在画布上画出一个多边形,然后点击按钮填充,测试算法时间效率
1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高。为了减少算法中的递归调用,节省栈空间的使用,人们提出了很多改进算法,其中一种...
递归实现多边形游戏算法,经过测试,绝对没问题。C实现
基于种子的区域填充采用4连通区域的递归种子填充算法,或扫描线种子填充算法,要求种子点(x,y)可交互输入)。三、线段裁剪和多边形裁剪算法的动画演示实现。(两种线段裁剪算法和H-S多边形逐边裁剪算法)多边形裁剪...
具有多边形和二进制掩码输出的 2D 和 3D 灰度图像集的递归区域增长算法。 此功能的主要目的在于编写干净且高度文档化的代码。 用法: [P, J] = regionGrowing(cIM, initPos, thresVal, maxDist, tfMean, ...
基于种子的区域填充采用4连通区域的递归种子填充算法,或扫描线种子填充算法,要求种子点(x,y)可交互输入)。三、线段裁剪和多边形裁剪算法的动画演示实现。(两种线段裁剪算法和H-S多边形逐边裁剪算法)多边形裁剪...
程序可用递归算法计算出多边形游戏所计算出的最大值。
矢量填充用的是扫描线算法,区域填充也是一种扫描线算法(而不是种子填充,因为种子填充的递归层数太多程序会很慢)。 区域填充必须先拿笔画一个封闭的任意区域,然后使用油漆桶在区域中间填充。存在一个bug,就是...
博客...首先,用多边形逆时针顶点的集合来表示凸多边形。 其次,图形描述-结构描述。 分析,最优子结构性质。 分析,最优三角分解递归结构。 最后,最优值计算。
矢量填充用的是扫描线算法,区域填充也是一种扫描线算法(而不是种子填充,因为种子填充的递归层数太多程序会很慢)。 区域填充必须先拿笔画一个封闭的任意区域,然后使用油漆桶在区域中间填充。存在一个bug,就是不...
基于种子的区域填充采用4连通区域的递归种子填充算法,或扫描线种子填充算法,要求种子点(x,y)可交互输入)。三、线段裁剪和多边形裁剪算法的动画演示实现。(两种线段裁剪算法和H-S多边形逐边裁剪算法)多边形裁剪...
实验一:递归与分治 1. 二分查找 2. 合并排序 3. 快速排序 实验二:回溯 1. 0-1背包问题 2. 装载问题 3. 堡垒问题(ZOJ1002) 4. *翻硬币问题 5. 8皇后问题 6. 素数环问题 7. 迷宫问题 8. *农场灌溉问题(ZOJ2412) ...
此题没能用上递归、分治或其他等一系列方法。以下为推荐思路,鼓励自行思考别的方法。 第一题本为练笔,但我挑选的此题似乎实现起来麻烦。 对不住大家了!若实在觉得繁琐的可跳过此题。:( 但,练练手总没坏处滴 ...
7. 4连通区域的递归种子填充算法,和扫描线种子填充算法,要求种子点(x,y)可交互输入)。 8. 简单三维图形系统:凸多面体的建模、透视投影,隐藏面的消除及基本图形变换(平移、旋转、缩放)。 9. 交互式Bezier...
算法设计与分析课后答案 520页 pdf(王晓东) 算法设计与分析(王晓东)电子教案 PPT 目前我也正看这个 (要是觉得这个不值这个分,说一下,我去你那里随便下一个 把分还你) 第1章 算法概述. 1.1 算法与程序 1.2...
实现二维区域填充种子填充法中的递归填充算法; 实现二维直线段裁剪的Cohen-Sutherland裁剪算法和中点分割裁剪算法。 实现二维图形的平移变换; 实现二维图形的放缩变换; 实现二维图形的旋转变换。(以任意点为参照...
实验内容:1、编程实现DDA算法、Bresenham算法、中点递归算法绘制直线段 2、分析对比三种算法的像素逼近效果和程序执行速度 3、输出要求:每种算法要分别在八个二分之一象限内画一条直线段 实验目的:理解有序边...