OpenCV4入门教程064：漫水算法

索引地址：系列索引

漫水算法

种子填充算法

种子填充算法是从多边形区域内部的一点开始，由此出发找到区域内的所有像素。

种子填充算法采用的边界定义是区域边界上所有像素具有某个特定的颜色值，区域内部所有像素均不取这一特定颜色，而边界外的像素则可具有与边界相同的颜色值。

具体算法步骤：

标记种子（x,y）的像素点
检测该点的颜色，若他与边界色和填充色均不同，就用填充色填充该点，否则不填充
检测相邻位置，继续上一步。这个过程延续到已经检测区域边界范围内的所有像素为止。

当然在搜索的时候有两种检测相邻像素：四向连通和八向连通。四向连通即从区域上一点出发，通过四个方向上、下、左、右来检索。而八向连通加上了左上、左下、右上、右下四个方向。

这种算法的有点是算法简单，易于实现，也可以填充带有内孔的平面区域。但是此算法需要更大的存储空间以实现栈结构，同一个像素多次入栈和出栈，效率低，运算量大。

扫描线填充算法

扫描线种子填充算法不再采用递归的方式处理“4-联通”和“8-联通”的相邻点，而是通过沿水平扫描线填充像素段，一段一段地来处理“4-联通”和“8-联通”的相邻点。这样算法处理过程中就只需要将每个水平像素段的起始点位置压入一个特殊的栈，而不需要象递归算法那样将当前位置周围尚未处理的所有相邻点都压入堆栈，从而可以节省堆栈空间。应该说，扫描线填充算法只是一种避免递归，提高效率的思想，前面提到的注入填充算法和边界填充算法都可以改进成扫描线填充算法，下面介绍的就是结合了边界填充算法的扫描线种子填充算法。

扫描线种子填充算法的基本过程如下：当给定种子点(x,y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft,xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

扫描线种子填充算法可由下列四个步骤实现：

(1)初始化一个空的栈用于存放种子点，将种子点(x,y)入栈；

(2)判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x,y)，y是当前的扫描线；

从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xLeft和xRight；

分别检查与当前扫描线相邻的y- 1和y+ 1两条扫描线在区间[xLeft,xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；

借助于堆栈，上述算法实现步骤如下：

1、初始化堆栈。
2、种子压入堆栈。
3、while（堆栈非空）{
　　　(1)从堆栈弹出种子象素。
　　　(2)如果种子象素尚未填充，则：
　　　　　　a.求出种子区段：xleft、xright;
　　　　　　b.填充整个区段。
　　　　　　c.检查相邻的上扫描线的xleft<= x <= xright区间内,是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleft<= x <=xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。
　　　　　　d.检查相邻的下扫描线的xleft<= x <= xright区间内，是否存在需要填充的新区段，如果存在的话，则把每个新区段在xleft<= x <= xright范围内的最右边的象素，作为新的种子象素依次压入堆栈。
　}

这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。这里比较难理解的一点就是为什么只是检查新扫描线上区间[xLeft,xRight]中的像素？如果新扫描线的实际范围比这个区间大（而且不连续）怎么处理？我查了很多计算机图形学的书籍和论文，好像都没有对此做过特殊说明，这使得很多人在学习这门课程时对此有挥之不去的疑惑。本着“毁人”不倦的思想，本文就罗嗦解释一下，希望能解除大家的疑惑。

如果新扫描线上实际点的区间比当前扫描线的[xLeft,xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。如图（4）所示：

floodfill

图（4）新扫描线区间增大且连续的情况

假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6,10）和（8,10）两个种子点入栈。接下来的循环会处理（8,10）这个种子点，根据算法第3步说明，会从（8,10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。

如果新扫描线上实际点的区间比当前扫描线的[xLeft,xRight]区间大，而且中间有边界点的情况，算法又是怎么处理呢？算法描述中虽然没有明确对这种情况的处理方法，但是第4步确定上、下相邻扫描线的种子点的方法，以及靠右取点的原则，实际上暗含了从相邻扫描线绕过障碍点的方法。下面以图（5）为例说明：

floodfill

图（5）新扫描线区间增大且不连续的情况

算法第3步处理完第5行后，确定了区间[7,9]，相邻的第4行虽然实际范围比区间[7,9]大，但是因为被（4,6）这个边界点阻碍，使得在确定种子点（4,9）后向左填充只能填充右边的第7列到第10列之间的区域，而左边的第3列到第5列之间的区域没有填充。虽然作为第5行的相邻行，第一次对第4行的扫描根据靠右原则只确定了（4,9）一个种子点。但是对第3行处理完后，第4行的左边部分作为第3行下边的相邻行，再次得到扫描的机会。第3行的区间是[3,9]，向左跨过了第6列这个障碍点，第2次扫描第4行的时候就从第3列开始，向右找，可以确定种子点（4,5）。这样第4行就有了两个种子点，就可以被完整地填充了。

漫水填充算法

原算法中,种子虽然代表一个区段,但种子实质上仍是一个象素,我们必须在种子出栈的时候计算种子区段,而这里有很大一部分计算是重复的.而且,原算法的扫描过程如果不用mask的话,每次都会重复扫描父种子区段所在的扫描线,而用mask的话又会额外增加开销

所以,对原算法的一个改进就是让种子携带更多的信息,让种子不再是一个象素,而是一个结构体.该结构体包含以下信息:种子区段的y坐标值,区段的x开始与结束坐标,父种子区段的方向(上或者下),父种子区段的x开始与结束坐标。

structseed{
    int y,
    int xleft,
    int xright,
    int parent_xleft,
    int parent_xright,
    bool is_parent_up
};

这样算法的具体实现变动如下

1、初始化堆栈.
2、将种子象素扩充成为种子区段(y,xleft, xright, xright+1, xrihgt, true), 填充种子区段,并压入堆栈.(这里有一个构造父种子区段的技巧)
3、while（堆栈非空）
{
　(1)从堆栈弹出种子区段。
　(2)检查父种子区段所在的扫描线的xleft<= x <= parent_xleft和parent_xright<= x <= xright两个区间,如果存在需要填充的新区段,则将其填充并压入堆栈.
　(3)检查非父种子区段所在的扫描线的xleft<= x <= xright区间,如果存在需要填充的新区段,则将其填充并压入堆栈.
}

另外,opencv里的种子填充算法跟以上方法大致相同,不同的地方是opencv用了队列不是堆栈,而且是由固定长度的数组来实现的循环队列,其固定长度为max(img_width,img_height) * 2.并且push与pop均使用宏来实现而没有使用函数.用固定长度的数组来实现队列(或堆栈)意义是显然的,能大大减少构造结构,复制结构等操作,可以大大提高效率.

函数原型：

int floodFill(InputOutputArray image, 
              Point seedPoint, 
              Scalar newVal, 
              Rect* rect=0, 
              Scalar loDiff=Scalar(), 
              Scalar upDiff=Scalar(), 
              int flags=4 );

int floodFill(InputOutputArray image, 
              InputOutputArray mask, 
              Point seedPoint,
              Scalar newVal, 
              Rect* rect=0, 
              Scalar loDiff=Scalar(), 
              Scalar upDiff=Scalar(), 
              int flags=4 );

参数说明：

第一个参数，InputOutputArray类型的image, 输入/输出1通道或3通道，8位或浮点图像，具体参数由之后的参数具体指明。
第二个参数， InputOutputArray类型的mask，这是第二个版本的floodFill独享的参数，表示操作掩模,。它应该为单通道、8位、长和宽上都比输入图像 image 大两个像素点的图像。第二个版本的floodFill需要使用以及更新掩膜，所以这个mask参数我们一定要将其准备好并填在此处。需要注意的是，漫水填充不会填充掩膜mask的非零像素区域。例如，一个边缘检测算子的输出可以用来作为掩膜，以防止填充到边缘。同样的，也可以在多次的函数调用中使用同一个掩膜，以保证填充的区域不会重叠。另外需要注意的是，掩膜mask会比需填充的图像大，所以 mask 中与输入图像(x,y)像素点相对应的点的坐标为(x+1,y+1)。
第三个参数，Point类型的seedPoint，漫水填充算法的起始点。
第四个参数，Scalar类型的newVal，像素点被染色的值，即在重绘区域像素的新值。
第五个参数，Rect*类型的rect，有默认值0，一个可选的参数，用于设置floodFill函数将要重绘区域的最小边界矩形区域。
第六个参数，Scalar类型的loDiff，有默认值Scalar( )，表示当前观察像素值与其部件邻域像素值或者待加入该部件的种子像素之间的亮度或颜色之负差（lower brightness/color difference）的最大值。
第七个参数，Scalar类型的upDiff，有默认值Scalar( )，表示当前观察像素值与其部件邻域像素值或者待加入该部件的种子像素之间的亮度或颜色之正差（lower brightness/color difference）的最大值。
第八个参数，int类型的flags，操作标志符，此参数包含三个部分，比较复杂，我们一起详细看看。
- 低八位（第0~7位）用于控制算法的连通性，可取4 (4为缺省值) 或者 8。如果设为4，表示填充算法只考虑当前像素水平方向和垂直方向的相邻点；如果设为 8，除上述相邻点外，还会包含对角线方向的相邻点。
- 高八位部分（16~23位）可以为0 或者如下两种选项标识符的组合：
  FLOODFILL_FIXED_RANGE - 如果设置为这个标识符的话，就会考虑当前像素与种子像素之间的差，否则就考虑当前像素与其相邻像素的差。也就是说，这个范围是浮动的。
  FLOODFILL_MASK_ONLY - 如果设置为这个标识符的话，函数不会去填充改变原始图像 (也就是忽略第三个参数newVal), 而是去填充掩模图像（mask）。这个标识符只对第二个版本的floodFill有用，因第一个版本里面压根就没有mask参数。
- 中间八位部分，上面关于高八位FLOODFILL_MASK_ONLY标识符中已经说的很明显，需要输入符合要求的掩码。Floodfill的flags参数的中间八位的值就是用于指定填充掩码图像的值的。但如果flags中间八位的值为0，则掩码会用1来填充。

测试代码1

//---------------------------------【头文件、命名空间包含部分】----------------------------
//      描述：包含程序所使用的头文件和命名空间
//------------------------------------------------------------------------------------------------
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/opencv.hpp>
using namespace cv;

//-----------------------------------【main( )函数】--------------------------------------------
//      描述：控制台应用程序的入口函数，我们的程序从这里开始
//-----------------------------------------------------------------------------------------------
int main() {
    Mat src = imread("1.jpg");
    imshow("Original", src);
    Rect ccomp;
    floodFill(src, Point(50, 300), Scalar(155, 255, 55), &ccomp, Scalar(20, 20, 20),
              Scalar(20, 20, 20));
    imshow("Result", src);
    waitKey(0);
    return 0;
}

测试结果：

floodfill

测试代码2

//---------------------------------【头文件、命名空间包含部分】----------------------------
//      描述：包含程序所使用的头文件和命名空间
//------------------------------------------------------------------------------------------------
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <iostream>
using namespace cv;
using namespace std;

//-----------------------------------【全局变量声明部分】--------------------------------------
//      描述：全局变量声明
//-----------------------------------------------------------------------------------------------
Mat  g_srcImage, g_dstImage, g_grayImage, g_maskImage; //定义原始图、目标图、灰度图、掩模图
int  g_nFillMode      = 1;                             //漫水填充的模式
int  g_nLowDifference = 20, g_nUpDifference = 20; //负差最大值、正差最大值
int  g_nConnectivity = 4;     //表示floodFill函数标识符低八位的连通值
int  g_bIsColor      = true;  //是否为彩色图的标识符布尔值
bool g_bUseMask      = false; //是否显示掩膜窗口的布尔值
int  g_nNewMaskVal   = 255;   //新的重新绘制的像素值

//-----------------------------------【ShowHelpText( )函数】----------------------------------
//      描述：输出一些帮助信息
//----------------------------------------------------------------------------------------------
static void ShowHelpText() {
    //输出欢迎信息和OpenCV版本
    printf("\n\n\t\t\t非常感谢购买《OpenCV3编程入门》一书！\n");
    printf("\n\n\t\t\t此为本书OpenCV3版的第50个配套示例程序\n");
    printf("\n\n\t\t\t   当前使用的OpenCV版本为：" CV_VERSION);
    printf("\n\n  ----------------------------------------------------------------------------\n");

    //输出一些帮助信息
    printf("\n\n\t欢迎来到漫水填充示例程序~");
    printf("\n\n\t本示例根据鼠标选取的点搜索图像中与之颜色相近的点，并用不同颜色标注。");

    printf("\n\n\t按键操作说明: \n\n"
           "\t\t鼠标点击图中区域- 进行漫水填充操作\n"
           "\t\t键盘按键【ESC】- 退出程序\n"
           "\t\t键盘按键【1】-  切换彩色图/灰度图模式\n"
           "\t\t键盘按键【2】- 显示/隐藏掩膜窗口\n"
           "\t\t键盘按键【3】- 恢复原始图像\n"
           "\t\t键盘按键【4】- 使用空范围的漫水填充\n"
           "\t\t键盘按键【5】- 使用渐变、固定范围的漫水填充\n"
           "\t\t键盘按键【6】- 使用渐变、浮动范围的漫水填充\n"
           "\t\t键盘按键【7】- 操作标志符的低八位使用4位的连接模式\n"
           "\t\t键盘按键【8】- 操作标志符的低八位使用8位的连接模式\n\n");
}

//-----------------------------------【onMouse( )函数】--------------------------------------
//      描述：鼠标消息onMouse回调函数
//---------------------------------------------------------------------------------------------
static void onMouse(int event, int x, int y, int, void *) {
    // 若鼠标左键没有按下，便返回
    //此句代码的OpenCV2版为：
    // if( event != CV_EVENT_LBUTTONDOWN )
    //此句代码的OpenCV3版为：
    if (event != EVENT_LBUTTONDOWN)
        return;

    //-------------------【<1>调用floodFill函数之前的参数准备部分】---------------
    Point seed = Point(x, y);
    int   LowDifference =
        g_nFillMode == 0
            ? 0
            : g_nLowDifference; //空范围的漫水填充，此值设为0，否则设为全局的g_nLowDifference
    int UpDifference =
        g_nFillMode == 0
            ? 0
            : g_nUpDifference; //空范围的漫水填充，此值设为0，否则设为全局的g_nUpDifference

    //标识符的0~7位为g_nConnectivity，8~15位为g_nNewMaskVal左移8位的值，16~23位为CV_FLOODFILL_FIXED_RANGE或者0。
    //此句代码的OpenCV2版为：
    // int flags = g_nConnectivity + (g_nNewMaskVal << 8) +(g_nFillMode == 1 ?
    // CV_FLOODFILL_FIXED_RANGE : 0); 此句代码的OpenCV3版为：
    int flags =
        g_nConnectivity + (g_nNewMaskVal << 8) + (g_nFillMode == 1 ? FLOODFILL_FIXED_RANGE : 0);

    //随机生成bgr值
    int  b = (unsigned)theRNG() & 255; //随机返回一个0~255之间的值
    int  g = (unsigned)theRNG() & 255; //随机返回一个0~255之间的值
    int  r = (unsigned)theRNG() & 255; //随机返回一个0~255之间的值
    Rect ccomp;                        //定义重绘区域的最小边界矩形区域

    Scalar newVal =
        g_bIsColor ? Scalar(b, g, r)
                   : Scalar(r * 0.299 + g * 0.587 +
                            b * 0.114); //在重绘区域像素的新值，若是彩色图模式，取Scalar(b, g,
                                        //r)；若是灰度图模式，取Scalar(r*0.299 + g*0.587 + b*0.114)

    Mat dst = g_bIsColor ? g_dstImage : g_grayImage; //目标图的赋值
    int area;

    //--------------------【<2>正式调用floodFill函数】-----------------------------
    if (g_bUseMask) {
        //此句代码的OpenCV2版为：
        // threshold(g_maskImage, g_maskImage, 1, 128, CV_THRESH_BINARY);
        //此句代码的OpenCV3版为：
        threshold(g_maskImage, g_maskImage, 1, 128, THRESH_BINARY);
        area = floodFill(dst, g_maskImage, seed, newVal, &ccomp,
                         Scalar(LowDifference, LowDifference, LowDifference),
                         Scalar(UpDifference, UpDifference, UpDifference), flags);
        imshow("mask", g_maskImage);
    } else {
        area = floodFill(dst, seed, newVal, &ccomp,
                         Scalar(LowDifference, LowDifference, LowDifference),
                         Scalar(UpDifference, UpDifference, UpDifference), flags);
    }

    imshow("Result", dst);
    cout << area << " 个像素被重绘\n";
}

//-----------------------------------【main( )函数】--------------------------------------------
//      描述：控制台应用程序的入口函数，我们的程序从这里开始
//-----------------------------------------------------------------------------------------------
int main(int argc, char **argv) {
    //载入原图
    g_srcImage = imread("lena.jpg", 1);

    if (!g_srcImage.data) {
        printf("读取图片image0错误~！ \n");
        return false;
    }

    //显示帮助文字
    ShowHelpText();

    g_srcImage.copyTo(g_dstImage);                     //拷贝源图到目标图
    cvtColor(g_srcImage, g_grayImage, COLOR_BGR2GRAY); //转换三通道的image0到灰度图
    g_maskImage.create(g_srcImage.rows + 2, g_srcImage.cols + 2,
                       CV_8UC1); //利用image0的尺寸来初始化掩膜mask

    //此句代码的OpenCV2版为：
    namedWindow("Result", WINDOW_AUTOSIZE);

    //创建Trackbar
    createTrackbar("负差最大值", "效果图", &g_nLowDifference, 255, 0);
    createTrackbar("正差最大值", "效果图", &g_nUpDifference, 255, 0);

    //鼠标回调函数
    setMouseCallback("Result", onMouse, 0);

    //循环轮询按键
    while (1) {
        //先显示效果图
        imshow("Result", g_bIsColor ? g_dstImage : g_grayImage);

        //获取键盘按键
        int c = waitKey(0);
        //判断ESC是否按下，若按下便退出
        if ((c & 255) == 27) {
            cout << "程序退出...........\n";
            break;
        }

        //根据按键的不同，进行各种操作
        switch ((char)c) {
                //如果键盘“1”被按下，效果图在在灰度图，彩色图之间互换
            case '1':
                if (g_bIsColor) //若原来为彩色，转为灰度图，并且将掩膜mask所有元素设置为0
                {
                    cout << "键盘“1”被按下，切换彩色/"
                            "灰度模式，当前操作为将【彩色模式】切换为【灰度模式】\n";
                    cvtColor(g_srcImage, g_grayImage, COLOR_BGR2GRAY);
                    g_maskImage = Scalar::all(0); //将mask所有元素设置为0
                    g_bIsColor = false; //将标识符置为false，表示当前图像不为彩色，而是灰度
                } else //若原来为灰度图，便将原来的彩图image0再次拷贝给image，并且将掩膜mask所有元素设置为0
                {
                    cout << "键盘“1”被按下，切换彩色/"
                            "灰度模式，当前操作为将【彩色模式】切换为【灰度模式】\n";
                    g_srcImage.copyTo(g_dstImage);
                    g_maskImage = Scalar::all(0);
                    g_bIsColor  = true; //将标识符置为true，表示当前图像模式为彩色
                }
                break;
                //如果键盘按键“2”被按下，显示/隐藏掩膜窗口
            case '2':
                if (g_bUseMask) {
                    destroyWindow("mask");
                    g_bUseMask = false;
                } else {
                    namedWindow("mask", 0);
                    g_maskImage = Scalar::all(0);
                    imshow("mask", g_maskImage);
                    g_bUseMask = true;
                }
                break;
                //如果键盘按键“3”被按下，恢复原始图像
            case '3':
                cout << "按键“3”被按下，恢复原始图像\n";
                g_srcImage.copyTo(g_dstImage);
                cvtColor(g_dstImage, g_grayImage, COLOR_BGR2GRAY);
                g_maskImage = Scalar::all(0);
                break;
                //如果键盘按键“4”被按下，使用空范围的漫水填充
            case '4':
                cout << "按键“4”被按下，使用空范围的漫水填充\n";
                g_nFillMode = 0;
                break;
                //如果键盘按键“5”被按下，使用渐变、固定范围的漫水填充
            case '5':
                cout << "按键“5”被按下，使用渐变、固定范围的漫水填充\n";
                g_nFillMode = 1;
                break;
                //如果键盘按键“6”被按下，使用渐变、浮动范围的漫水填充
            case '6':
                cout << "按键“6”被按下，使用渐变、浮动范围的漫水填充\n";
                g_nFillMode = 2;
                break;
                //如果键盘按键“7”被按下，操作标志符的低八位使用4位的连接模式
            case '7':
                cout << "按键“7”被按下，操作标志符的低八位使用4位的连接模式\n";
                g_nConnectivity = 4;
                break;
                //如果键盘按键“8”被按下，操作标志符的低八位使用8位的连接模式
            case '8':
                cout << "按键“8”被按下，操作标志符的低八位使用8位的连接模式\n";
                g_nConnectivity = 8;
                break;
        }
    }

    return 0;
}