用队列实现种子填充算法的非递归-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

用队列实现种子填充算法的非递归

用队列实现种子填充算法的非递归

展开
收起
知与谁同 2018-07-21 19:13:10 1720 0
1 条回答
写回答
取消 提交回答
  • 小哇
    一、种子填充算法(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)
    注入填充算法不特别强调区域的边界,它只是从指定位置开始,将所有联通区域内某种指定颜色的点都替换成另一种颜色,从而实现填充效果。注入填充算法能够实现颜色替换之类的功能,这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单,核心就是递归和搜索,以下就是注入填充算法的一个实现:

    164 void 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的定义:

    15 typedef struct tagDIRECTION
    16 {
    17 int x_offset;
    18 int y_offset;
    19 }DIRECTION;

    79 DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1},{0, -1}, {-1, -1} };

    这个是搜索类算法中常用的技巧,无需做太多说明,其实只要将其替换成如下direction_4的定义,就可以将算法改成4个联通方向填充算法:

    80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

    图2就是应用本算法实现的“4-联通”和“8-联通”填充效果:
    2019-07-17 22:55:09
    赞同 展开评论 打赏
问答分类:
问答地址:
相关产品:
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载