算法介绍 | 泛洪算法(Flood fill Algorithm)

这篇具有很好参考价值的文章主要介绍了算法介绍 | 泛洪算法(Flood fill Algorithm)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法别名:

漫水填充算法、种子填充算法(Seed Fill)

作用:

用于确定连接到多维数组中给定节点的区域,可以用来标记或者分离图像的一部分,实现如Ps中自动选区功能。

基本思想:

顾名思义就像洪水漫过一样,把一块连通的区域填满。

当然水要能漫过需要满足一定的条件,可以理解为满足条件的地方就是低洼的地方,水才能流过去。

在图像处理中就是给定一个种子点作为起始点,向附近相邻的像素点扩散,把颜色相同或者相近的所有点都找出来,并填充上新的颜色,这些点形成一个连通的区域。

算法参数:

  1. 起始节点(start node)
  2. 目标颜色(target color)
  3. 替换颜色(replacement color)

算法实现:

漫水填充算法实现最常见有四邻域像素填充法,八邻域像素填充法,基于扫描线的填充方法。根据代码实现方式又可以分为递归与非递归。

1、四邻域递归实现

泛洪算法,opencv,c++,算法,c++,opencv

将像素点(x,y)周围的上下左右四个点分别进行着色。

//Recursive 4-way floodfill, crashes if recursion stack is full
public void floodFill4(int x, int y, int newColor, int oldColor)  
{  
    if(x >= 0 && x < width && y >= 0 && y < height   
         && getPixel(x, y) == oldColor && getPixel(x, y) != newColor)   
    {   
        setPixel(x, y, newColor); //set color before starting recursion  
        floodFill4(x + 1, y, newColor, oldColor);  
        floodFill4(x - 1, y, newColor, oldColor);  
        floodFill4(x, y + 1, newColor, oldColor);  
        floodFill4(x, y - 1, newColor, oldColor);  
    }     
}

2、八邻域递归实现

泛洪算法,opencv,c++,算法,c++,opencv

将一个像素点的上下左右,左上,左下,右上,右下都进行着色。

public void floodFill8(int x, int y, int newColor, int oldColor)  
{  
    if(x >= 0 && x < width && y >= 0 && y < height &&   
            getPixel(x, y) == oldColor && getPixel(x, y) != newColor)   
    {   
        setPixel(x, y, newColor); //set color before starting recursion  
        floodFill8(x + 1, y, newColor, oldColor);  
        floodFill8(x - 1, y, newColor, oldColor);  
        floodFill8(x, y + 1, newColor, oldColor);  
        floodFill8(x, y - 1, newColor, oldColor);  
        floodFill8(x + 1, y + 1, newColor, oldColor);  
        floodFill8(x - 1, y - 1, newColor, oldColor);  
        floodFill8(x - 1, y + 1, newColor, oldColor);  
        floodFill8(x + 1, y - 1, newColor, oldColor);  
    }     
} 

3、扫描线算法(Scanline Fill):

泛洪算法,opencv,c++,算法,c++,opencv

利用填充线来加速算法, 它不是在堆栈上推动每个潜在的未来像素坐标,而是检查相邻线(前一个和下一个)以找到可能在未来通过中填充的相邻段, 线段的坐标(开始或结束)被推到堆栈上。 在大多数情况下,该扫描线算法至少比每像素算法快一个数量级。 

该算法的过程是:先扫描一行或者一列内的连通像素,然后再上下行或者左右列扫描,可以减少递归栈的深度。

递归方式:

递归实现算法好理解,但当连通的区域很大时,很可能会导致栈溢出

void floodFillScanline(int x, int y, int newColor, int oldColor){
	if(newColor==oldColor) return;
	if(screen[x][y]!=oldColor) return;
	int x1=x;
	while(x1<w&&screen[x1][y]==oldColor){
	    screen[x1][y]=newColor;
	    x1++;
	}
	x1=x-1;
	while(x1>=0&&screen[x1][y]==oldColor){
	    screen[x1][y]=newColor;
	    x1--;
	}
	x1=x;
	while(x1<w&&screen[x1][y]==newColor){
	    if(y<h-1&&screen[x1][y+1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1++;
	}
	x1=x-1;
	while(x1>0&&screen[x1][y]==newColor){
	    if(y>0&&screen[x1][y+1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1--;
	}
	x1=x;
	while(x1<w&&screen[x1][y]==newColor){
	    if(y<h-1&&screen[x1][y-1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1++;
	}
	x1=x-1;
	while(x1>0&&screen[x1][y]==newColor){
	    if(y>0&&screen[x1][y-1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1--;
	}
}

非递归方式:

void floodFillScanline(int x, int y, int newColor, int oldColor){
	if(newColor==oldColor) return;
	if(screen[x][y]!=oldColor) return;
	emptyStack();
	int x1;
	bool spanAbove, spanBelow;
	if(!push(x,y)) return;
	while(pop(x,y)){
	    x1=x;
	    while(x1>0&&screen[x1][y]==oldColor) x1--;
	    x1++;
	    spanAbove = spanBelow = 0;
	    while(x1<w&&screen[x1][y]==oldColor){
	        screen[x1][y]=newColor;
	        if(!spanAbove&&y>0&&screen[x1][y-1]==oldColor){ //这里判断出了上行的元素可以被染色,可能为了修改screen的访存连续性,所以这里没修改。而且你改了上行的值,却没考虑其四周,会有完备性的问题。
	            if(!push(x1,y-1)) return;
	            spanAbove=1;
	        }
	        else if(spanAbove&&y>0&&screen[x1][y-1]!=oldColor){
	            spanAbove=0; //不压入重复过多的元素
	        }
	        if(!spanBelow&&y<h-1&&screen[x1][y+1]==oldColor){
	            if(!push(x1,y+1)) return;
	            spanBelow=1;
	        }
	        else if(spanBelow&&y<h-1&&screen[x1][y+1]!=oldColor){
	            spanBelow=0;
	        }
	        x1++;
	    }
	}
}

4、OpenCV 的 floodFill 函数

在OpenCV中,漫水填充算法由floodFill函数实现,可以从指定的种子点开始填充一个连通域。连通性由像素值的接近程度来衡量。

OpenCV2.X 有两个C++重载的floodFill函数:

/* fills the semi-uniform image region starting from the specified seed point*/
CV_EXPORTS int floodFill( InputOutputArray image,
                          Point seedPoint, 
                          Scalar newVal, 
                          CV_OUT Rect* rect=0,
                          Scalar loDiff=Scalar(), 
                          Scalar upDiff=Scalar(),
                          int flags=4 );

/* fills the semi-uniform image region and/or the mask starting from the
   specified seed point*/
CV_EXPORTS int floodFill( InputOutputArray image,
                          InputOutputArray mask,
                          Point seedPoint, 
                          Scalar newVal, 
                          CV_OUT Rect* rect=0,
                          Scalar loDiff=Scalar(), 
                          Scalar upDiff=Scalar(),
                          int flags=4 );

• image 要处理的图片,既是入参也是出参,接受单通道或3通道,8位或浮点类型的图片。如果提供了Mask而且设置了 FLOODFILL_MASK_ONLY 的flag,输入图像才不会被修改,否则调用本方法填充的结果会修改到输入图像中。

• mask 掩码图像,既是入参也是出参,接受单通道8位的图片,要求比要处理的图片宽和高各大两个像素。mask要先初始化好,填充算法不能漫过mask中非0的区域。比如可以用边缘检测的结果来做为mask,以防止边缘被填充。做为输出参数,mask对应图片中被填充的像素会被置为1或者下面参数指定的值。因此当多次调用floodFill方法,使用同一个mask时,可以避免填充区域叠加和重复计算。 因为 mask比image大,所以image中的点 p(x,y),对应mask中的点 p(x+1, y+1)

• seedPoint 填充算法的种子点,即起始点

• newVal 填充的颜色

• loDiff 最小的亮度或颜色的差值

• upDiff 最大的亮度者颜色的差值

• rect 可选的输出参数,返回一个最小的矩形,可以刚好把填充的连通域包起来。

• flags  

 - 低八位[0-7]表示连通性,默认值4表示四领域填充,8表示八领域填充。    

- [8-15]位表示用来填充mask的颜色值[1-255]默认是1    

- 比如flag值(4|(255«8)) 表示使用四领域填充,mask填充色值是255。

- 剩余的位有两个值可以单独设置或者用(|)同时设置:      

FLOODFILL_MASK_ONLY 表示不修改原始输入图像,只把结果输出到mask图中,在mask中将填充区域标上前面flag中指定的值。newVal的参数值将被忽略。

FLOODFILL_FIXED_RANGE 表示待填充像素只和种子点比较。如果不设置这个标记,表示待填充的像素是和相邻的像素比较(相当于差值范围是浮动的),这种情况下填充区域的像素可能会和种子点相差越来越大。

参考链接

以下为本博客的参考内容:文章来源地址https://www.toymoban.com/news/detail-624981.html

  1. 图像处理之漫水填充算法(flood fill algorithm) - 腾讯云开发者社区-腾讯云 (tencent.com)
  2. Flood fill Algorithm // 谭邵杰的计算机奇妙旅程 (ustc.edu.cn)
  3. 图像分割经典算法--《泛洪算法》(Flood Fill)_我的她像朵花的博客-CSDN博客_泛洪算法

到了这里,关于算法介绍 | 泛洪算法(Flood fill Algorithm)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】Filling Bookcase Shelves 填充书架

    给定一个数组 books ,其中 b o o k s [ i ] = [ t h i c k n e s s i , h e i g h t i ] books[i] = [thicknessi, heighti] b oo k s [ i ] = [ t hi c kn ess i , h e i g h t i ] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。 按顺序 将这些书摆放到总宽度为 shelfWidth 的书架上。 先选几本书放在书架上

    2024年02月08日
    浏览(78)
  • 【C++】STL 算法 - 累加填充算法 ( 元素累加算法 - accumulate 函数 | 元素填充算法 - fill 函数 )

    在 C++ 语言 的 标准模板库 ( STL , STL Standard Template Library ) 中 , 提供了 accumulate 元素累加算法函数 用于 将 一个容器中的元素 进行累加操作 ; accumulate 元素累加函数 将 输入容器 的 [ 起始迭代器, 终止迭代器 ) 范围 内的 元素 在一个基础值 的 基础上 进行累加 , 得到一个累加值

    2024年01月22日
    浏览(64)
  • 贪心算法(Greedy Algorithm)

    贪心算法(Greedy Algorithm)是一种解决优化问题的算法策略。在贪心算法中,每一步都会选择当前情况下最优的选择,而不考虑未来的后果。 贪心算法的基本思想是通过局部最优选择达到全局最优。它并不保证一定能得到全局最优解,但在某些情况下可以得到近似最优解或者

    2024年02月09日
    浏览(40)
  • 遗传算法 (Genetic Algorithm, GA)

    遗传算法(Genetic Algorithm,简称GA)起源于对生物系统所进行的计算机模拟研究,是一种随机全局搜索优化方法,它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象,从任一初始种群(Population)出发,通过随机选择、交叉和变异操作,产生一群更适合

    2024年02月05日
    浏览(37)
  • Algorithm_01--C#递归算法

    ///递归算法本质: ///1、方法的自我调用 ///2、有明确的终止条件 ///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件     问题:程序在输入1000后(即1到1000的和),程序会出现异常。 解答:百度后得出结论,栈溢出异常。 1、递归方法在每次调用自身时,

    2024年02月06日
    浏览(37)
  • 遗传算法(Genetic Algorithm,GA)

    这是一篇关于遗传算法的总结博客,包括算法思想,算法步骤,python实现的两个简单例子,算法进阶(持续更新ing)。 遗传算法的应用很多,诸如寻路问题,8数码问题,囚犯困境,动作控制,找圆心问题(在一个不规则的多边形中,寻找一个包含在该多边形内的最大圆圈的

    2023年04月17日
    浏览(44)
  • 算法笔记:KM算法(Kuhn-Munkres Algorithm)

    带权二分图的最优匹配 问题 算法笔记:匈牙利算法_UQI-LIUWJ的博客-CSDN博客  匈牙利算法的一个问题是,找到的匹配不一定是最优匹配 因为算法将每个匹配对象的地位视为相同的,在这个前提下求解最大匹配 而很多时候,二部图连边是带权重的,在这个基础上的匹配才更贴近

    2023年04月09日
    浏览(36)
  • 【algorithm】算法基础课---二分查找算法(附笔记 | 建议收藏)

    🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 📣系列专栏:AcWing算法学习笔记 💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊 ✉️ 如果无聊的话,就来逛逛我的博客栈吧 stack-frame.cn 关于我

    2024年01月18日
    浏览(39)
  • Algorithm_01--C#递归算法01

    ///递归算法本质: ///1、方法的自我调用 ///2、有明确的终止条件 ///3、每次调用时,问题规模在不断减少。通过递减,最终到达终止条件     问题:程序在输入1000后(即1到1000的和),程序会出现异常。 解答:百度后得出结论,栈溢出异常。 1、递归方法在每次调用自身时,

    2024年02月06日
    浏览(49)
  • 关于Secure Hash Algorithm加密算法

    一、概述 SHA(Secure Hash Algorithm)加密算法是一种广泛应用的密码散列函数,由美国国家安全局(NSA)设计,用于保障数据的安全性和完整性。SHA算法经历了多个版本的更新,目前主要应用于各种网络安全和数据加密领域。 SHA在线加密 | 一个覆盖广泛主题工具的高效在线平台

    2024年02月04日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包