图像处理之漫水填充算法(flood fill algorithm)

导语 介绍了漫水填充算法(flood fill algorithm)的基本思想,实现方式和应用场景,OpenCV中floodFill函数的使用方法。

基本思想

漫水填充算法,顾名思义就像洪水漫过一样,把一块连通的区域填满,当然水要能漫过需要满足一定的条件,可以理解为满足条件的地方就是低洼的地方,水才能流过去。在图像处理中就是给定一个种子点作为起始点,向附近相邻的像素点扩散,把颜色相同或者相近的所有点都找出来,并填充上新的颜色,这些点形成一个连通的区域。 漫水填充算法可以用来标记或者分离图像的一部分,可实现类似Windows 画图油漆桶功能,或者PS里面的魔棒选择功能。

算法实现

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

四领域的递归实现:

//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);  
    }     
}

八领域的递归实现:

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);  
    }     
} 

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

递归实现算法好理解,但当连通的区域很大时,很可能会导致栈溢出。关于扫描线算法和这些算法的非递归实现可以参见这里的介绍 http://lodev.org/cgtutor/floodfill.html

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

未知点的判断

通过下面未知点是否应该填充的判断条件,可以更好的理解上述参数的含义。

灰度图固定范围时(flag中设置了 FLOODFILL_FIXED_RANGE ),未知点的判断,只跟种子点比较:

灰度图浮动范围时,未知点的判断,跟相邻的已经填充的点比较:

同理彩色图固定范围时的判断:

彩色图浮动范围时的判断:

eg:通过多次选择背景种子点和调用 floodFill,可以把背景和前景分离开,黑白图是mask图。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一棹烟波

OpenCV角点检测源代码分析(Harris和ShiTomasi角点)

OpenCV中常用的角点检测为Harris角点和ShiTomasi角点。 以OpenCV源代码文件 .\opencv\sources\samples\cpp\t...

4636
来自专栏SeanCheney的专栏

Numpy和MatplotlibPython科学计算——Numpy线性代数模块(linalg)随机模块(random)Python的可视化包 – Matplotlib2D图表3D图表图像显示

Python科学计算——Numpy Numpy(Numerical Python extensions)是一个第三方的Python包,用于科学计算。这个库的前身...

4374
来自专栏数据小魔方

R语言可视化——密度曲线图及其美化!

今天跟大家分享关于密度曲线图及其美化技巧! 密度曲线图可能平时大家用的不多,不过其实没什么神秘,它的功能于直方图一样,都是用于表达连续型数值变量的分布形态。 ...

2715
来自专栏WOLFRAM

用Wolfram语言绘制一笔画环形迷宫

2084
来自专栏数值分析与有限元编程

可视化 | MATLAB划分均匀三角形网格

划分单元网格是随心所欲的,所遵循的原则就是尽量提高计算精度。下面是一个规则区域划分均匀三角形网格的例子。 如图所示,将一个矩形平面区域划分成相同大小的直角三角形...

3214
来自专栏小鹏的专栏

cnn+rnn+attention

下面是单层rnn+attention的代码,若考虑多层rnn请参考博主的:tf.contrib.rnn.static_rnn与tf.nn.dynamic_rnn...

24111
来自专栏Petrichor的专栏

opencv: 颜色空间转换(cv2.cvtColor) 探究(图示+源码)

我们从 OpenCV官网 的Miscellaneous Image Transformations 上,可查到 cv2.cvtColor 这个api的定义如下:

542
来自专栏申龙斌的程序人生

零基础学编程037:小数据分析

R语言内置强大的向量运算,是搞数据分析的强大的编程语言,而Python也毫不逊色。今天就试着分析一下考试成绩表中两门科目的相关性。 问题描述: 有一个CSV文件...

3249
来自专栏深度学习计算机视觉

opencv的初步使用(高斯模糊、边缘检测、灰度化、二值化、闭运算、绘制边缘)

前提:已经配好了opencv+Qt 这里只讲如何使用api,不怎么讲算法原理 既然要用opencv的库,首先把相应的头文件导进去吧 #include <ope...

3525
来自专栏iOSer成长记录

iOS-识别图片中二维码

在iOS的CoreImage的Api中,有一个CIDetector的类,Detector的中文翻译有探测器的意思,那么CIDetector是用来做哪些的呢?它可...

591

扫码关注云+社区