OpenCV源码解析：FloodFill（漫水填充）函数

快来打我* 2022-05-17 08:42 199阅读 0赞

花木成畦手自栽 ！

先来两张wikipedia上的图，分别为4连通填充和8连通填充的示意图。

![70][]

![70 1][]

FloodFill，一般的翻译是漫水填充，也就是把相邻的满足填充要求的颜色换成某个颜色的过程。填充方式一般是4连通，也就是扩展方向是上下左右4个方向，

![70 2][]

当然你也可以采用8连通填充，把角上那4个也包括进来

![70 3][]

直观地来说，可以这样填充，

### 以stack堆栈为基础的递归填充 ###

一个很简单的递归填充如下所示:

Flood-fill (点node, 目标色, 替换色)
    {
    1. 如果目标色不在可替换范围之内, return.
    2. 把当node的颜色改成替换色.
    3. 填充周边点
    对左边点进行 Flood-fill（左边node,目标色, 替换色）;
    对右边点进行 Flood-fill（右边node,目标色, 替换色）;
    对上边点进行 Flood-fill（上边node,目标色, 替换色）;
    对下边点进行 Flood-fill（下边node,目标色, 替换色）;
    4. Return.
    }

这个填充非常直观，很容易理解，也很容易实现，然而，当图像变大时，产生的大量递归，使得参数不断被入栈，时间上是一个巨大的消耗，而且，如此巨大的堆栈开销，在堆栈有限的嵌入式开发中，或当编译器无法提供这种堆栈时（如Java applets），这种算法是不可取的。

### OpenCV采用的填充方式 ###

OpenCV采用的是逐行填充，他抛弃了递归的堆栈形式，而是通过一个向量（也是一个栈，但不属于系统堆栈，即：std::vector<FFillSegment>\* buffer）来实现填充操作。

其填充函数（v3.4.1）是floodFillGrad\_CnIR，我们来分析一下其源代码。

函数说明：逐行进行漫水填充。

填充方向的说明：因为填充是一行一行填充的，所以dir方向只有UP和DOWN，其中理解这个data\[\]\[\]数组设计，是理解填充的关键。

int data[][3] =
    {
        {-dir, L - _8_connectivity, R + _8_connectivity}, // _8_connectivity=0 or 1
        {dir, L - _8_connectivity, PL - 1},
        {dir, PR + 1, R + _8_connectivity}
    };

Data的解释如下图所示（在4连通填充时, \_8\_connectivity=0），假设已经填充的区域为绿色，当前要填充的行是有Ｌ，Ｒ标记所在的行，假设dir=UP,则-dir=DOWN,

首先填充黄色区域所在的行，填充完后会入栈Ｌ，Ｒ，ＰＬ，ＰＲ这四个参数（意思是Left, Right, Previous Left, Previous Right）；  
在后面该参数出栈后，  
第一步，先填充data\[0\]=\{-dir, L - \_8\_connectivity, R + \_8\_connectivity\}所指定的区域，  
也就是黄色区域的下面那一行，即Ｌ，Ｒ所在的行的底下那行；  
第二步，填充data\[1\]=\{dir, L - \_8\_connectivity, PL – 1\}所指定的区域,  
即填充图中的1,2,3,4,5这几格，此时Left = L - \_8\_connectivity, Right = PL – 1，  
（在填充ＰＬ-ＰＲ这一行时，这是被挡住的左边部分）；  
第三步，填充data\[2\]=\{dir, PR + 1, R + \_8\_connectivity\}所指定的区域,  
即填充图中的6,7,8,9,10这几格，此时Left = PR + 1，Right = R + \_8\_connectivity，  
（在填充ＰＬ，ＰＲ这一行时，这是被挡住的右边部分）；

为了方便理解，我换个说法再解释一次，

首先，当从上一次的Left=PL, Right=PR进行到本行时，先填充图中的黄色部分，在填充过程中会逐步向左右尽可能的区域扩散，直到达到L，R所在的极限位置，然后入栈Ｌ，Ｒ，ＰＬ，ＰＲ这四个参数；  
这４个参数出栈后的填充情况是这样的，  
第一步：填充data参数数组的指定的第一行，即data\[0\]\[?\]，-dir表示向下，即黄色行行所在的下面那行；  
第二步，填充后回过头来看有没有上一次被非填充区域（图中的黑色）挡住的部分，如图所示，标有数字1,2,3,4,5,6,7,8,9,10的部分正好是被挡住的，所以现在回过头来填充，  
因此，Left=data\[1\]\[1\] = L, Right=data\[1\]\[2\]= PL-1，dir=UP,会对左边部分1,2,3,4,5进行填充；Left=data\[2\]\[1\] = PR, Right=data\[2\]\[2\]= R，dir=UP,会对右边6,7,8,9,10部分进行填充，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70][]

在方向上，要注意入栈时用的是

ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir ); // j+1=>L,   i-1=>R,   L=>PL,   R=>PR

## 源码详解 ##

先说一下OpenCV的范围比较函数Diff8uC3。  
假设像素差允许范围是20，那么对RGB中任一个channel（假设为c，c=1,2,3），有interval\[c\]=40,  
选取的像素a的值离像素b值的差要满足范围为<=20，也就是  
abs(a\[0\]\[c\] - b\[0\]\[c\])<=20  
这个算法等价于  
\-20 <= (a\[0\]\[c\] - b\[0\]\[c\]) <= 20  
也等价于  
0 <= (a\[0\]\[c\] - b\[0\]\[c\] + 20 ) <= interval\[c\] = 40  
即程序中采用的代码（通过这种变换，把大小范围的判断变成一次性的判断），  
(unsigned)(a\[0\]\[c\] - b\[0\]\[c\] + 20 ) <= interval\[c\]

struct Diff8uC3
    {
        Diff8uC3(Vec3b _lo, Vec3b _up)
        {
            for( int k = 0; k < 3; k++ )
                lo[k] = _lo[k], interval[k] = _lo[k] + _up[k];
        }
        bool operator()(const Vec3b* a, const Vec3b* b) const
        {
            return (unsigned)(a[0][0] - b[0][0] + lo[0]) <= interval[0] &&
                   (unsigned)(a[0][1] - b[0][1] + lo[1]) <= interval[1] &&
                   (unsigned)(a[0][2] - b[0][2] + lo[2]) <= interval[2];
        }
        unsigned lo[3], interval[3];
    };

下面来看主函数floodFillGrad\_CnIR的源码

template<typename _Tp, typename _MTp, typename _WTp, class Diff>
    static void
    floodFillGrad_CnIR( Mat& image, Mat& msk,
                       Point seed, _Tp newVal, _MTp newMaskVal,
                       Diff diff, ConnectedComp* region, int flags,
                       std::vector<FFillSegment>* buffer )
    {
       int step = (int)image.step, maskStep = (int)msk.step;
       // step 是线的大小(行的跨度)，也就是一行占多少个byte,等于 width*channels 
       // maskStep是指mask一行占多少个byte，一般是width+2, 参考cv::floodFill的源码
       uchar* pImage = image.ptr();  // image的起始位置
       _Tp* img = (_Tp*)(pImage + step*seed.y); // img是种子所在的行的起始位置
       uchar* pMask = msk.ptr() + maskStep + sizeof(_MTp);

这里要注意，pMask是指MASK的对应的image的起始地址，注意MASK在各个方向都要比image大一个字节，所以这里代码中有+maskStep+sizeof(\_MTp) ，sizeof(\_MTp)= sizeof(uchar) = 1；

![70 4][]

接下来所有的解释，都在源码中，有些没有使用注释符，因为注释之后颜色太淡了，不利于观看。

mask是对应img的，表示seed在MASK中的行

_MTp* mask = (_MTp*)(pMask + maskStep*seed.y); 
        int i, L, R;
        int area = 0;
        int XMin, XMax, YMin = seed.y, YMax = seed.y;

下面这句判断填充时是8连通还是4连通（4连通\_8\_connectivity＝0; 8连通\_8\_connectivity＝1）  
8连通填充：x边上8个点，符合色彩条件的都填充，   
4连通填充：x边上4个点，符合色彩条件的才填充，

int _8_connectivity = (flags & 255) == 8;

下面，如果设置FLOODFILL\_FIXED\_RANGE为这个标识符的话，就会考虑当前像素与种子像素之间的差，因为种子像素是不变的，所以这个差值的范围是不变的（大多数图像处理中，使用的就是这种情况）；否则，就考虑当前像素与其相邻像素的差，取决于不同的位置，这个范围是浮动的。

int fillImage = (flags & FLOODFILL_MASK_ONLY) == 0;

接下来，下面这句，如果设置FLOODFILL\_MASK\_ONLY标识符的话，函数不会去填充改变原始图像, 而是去填充掩模图像（MASK）。也就是说，当(flags & FLOODFILL\_MASK\_ONLY) == 0为true时,填充原图像。

int fillImage = (flags & FLOODFILL_MASK_ONLY) == 0;
    
    
        FFillSegment* buffer_end = &buffer->front() + buffer->size(), 
                     *head = &buffer->front(), 
                     *tail = &buffer->front();
    
        L = R = seed.x;
        if( mask[L] )
            return;
    
        mask[L] = newMaskVal; 
        _Tp val0 = img[L];

下面两个while的作用：如果种子点所在行如果满足色彩要求,就把相应的mask位设置为newMaskVal，比如0xFF

if( fixedRange )
    　　{
            while( !mask[R + 1] && diff( img + (R+1), &val0 ))
                mask[++R] = newMaskVal;
    
            while( !mask[L - 1] && diff( img + (L-1), &val0 ))
                mask[--L] = newMaskVal;
        } 
        else 
        { 
            while( !mask[R + 1] && diff( img + (R+1), img + R ))
                mask[++R] = newMaskVal;
    
            while( !mask[L - 1] && diff( img + (L-1), img + L ))
                mask[--L] = newMaskVal;
        }
    
        XMax = R; // 本行已经填充的位置的最大值（最右边）
        XMin = L; // 本行已经填充的位置的最小值（最左边）

将开始状态入栈(也就是向量buffer),这里，prevL=R+1, prevR=R, dir = UP  
每ICV\_PUSH一次，就执行一次tail++，参考ICV\_PUSH宏定义

ICV_PUSH( seed.y, L, R, R + 1, R, UP ); // 入栈（1）

再看后面的while循环，这里head == tail的条件，只有在完全填充完之后，才能得到满足。

循环中各个参数的含义：YC = y current, PL = previous Left, PR = previous Right, dir = direction (这个direction只有UP=1和DOWN=-1，因为是逐行填充)。

举例说明：上一次填充的行是YC=10，入栈了YC+dir=11; 那么本次出栈的是YC=11, YC+dir=12，在后面的for循环中，是先处理第12行，得到要填充的区域，然后入栈第12行，处理完毕后再填充11行，然后再回到while看有没有完全填充完11反方向的行，有的话就填充完，然后继续循环。

值得注意的是：  
ICV\_PUSH( YC + dir, j+1, i-1, L, R, -dir ); 其作用是入栈下一个填充行；

data参数中，第一个参数为-dir，为什么？注意看int data\[\]\[3\]的定义，假设上一行到本行10的方向是UP（dir=1，所以也就是YC + dir＝11），入栈时方向是-dir；出栈（1）时，得到的dir就是－1，dir=data\[0\]\[0\]＝-(-1)，负负得正，这样在data\[0\]\[\]参数首先得到处理时，依然是最有可能需要得到填充的区域。

while( head != tail )
        {
    	   
            int k, YC, PL, PR, dir; 
           
            ICV_POP( YC, L, R, PL, PR, dir ); // 出栈（1）当前填充行  
    
            int data[][3] =
            {
                {-dir, L - _8_connectivity, R + _8_connectivity},
                {dir, L - _8_connectivity, PL - 1},
                {dir, PR + 1, R + _8_connectivity}
            };
    
            //该行可填充的像素的宽度
            unsigned length = (unsigned)(R-L); 
    
            if( region )
            {
                //填充的面积（总像素个数）
                area += (int)length + 1; 
    
    　　　　　 　//下面，是重新设定本次填充的范围（上下左右的极限值）
                if( XMax < R ) XMax = R;
                if( XMin > L ) XMin = L;
                if( YMax < YC ) YMax = YC;
                if( YMin > YC ) YMin = YC;
            }
    
            for( k = 0; k < 3; k++ )
            {
                dir = data[k][0];
                img = (_Tp*)(pImage + (YC + dir) * step); // 更新当前行的地址
                _Tp* img1 = (_Tp*)(pImage + YC * step);   // 上一次(刚处理完)的行的地址
                mask = (_MTp*)(pMask + (YC + dir) * maskStep); // 对应的当前MASK地址
                int left = data[k][1]; 
                int right = data[k][2]; 
     情况(I) FLOODFILL_FIXED_RANGE，当前像素与种子像素之间的差在设定范围内
                if( fixedRange )
                //如果该行有满足色采条件的像素点，则把该行的MASK全部设置为newMaskVal
                //并将相应的参数入栈，
                    for( i = left; i <= right; i++ )
                    {
                        if( !mask[i] && diff( img + i, &val0 ))
                        {
                            int j = i;
                            mask[i] = newMaskVal;
                            while( !mask[--j] && diff( img + j, &val0 ))
                                mask[j] = newMaskVal;
    
                            while( !mask[++i] && diff( img + i, &val0 ))
                                mask[i] = newMaskVal;
                            
                            ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir ); // 入栈（2）
                        }
                    }
    
    情况(II) !FLOODFILL_FIXED_RANGE，当前像素与相信像素之间的差在设定范围内
    且不为8连通填充
                else if( !_8_connectivity )
                    for( i = left; i <= right; i++ )
                    {
                        if( !mask[i] && diff( img + i, img1 + i ))
                        {
                            int j = i;
                            mask[i] = newMaskVal;
                            while( !mask[--j] && diff( img + j, img + (j+1) ))
                                mask[j] = newMaskVal;
    
                            while( !mask[++i] &&
                                  (diff( img + i, img + (i-1) ) ||
                                   (diff( img + i, img1 + i) && i <= R)))
                                mask[i] = newMaskVal;
    
                            ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                        }
                    }
    
    情况（III） 8 连通填充的情况
                else
                    for( i = left; i <= right; i++ )
                    {
                        int idx;
                        _Tp val;
    
                        if( !mask[i] &&
                           (((val = img[i],
                              (unsigned)(idx = i-L-1) <= length) &&
                             diff( &val, img1 + (i-1))) ||
                            ((unsigned)(++idx) <= length &&
                             diff( &val, img1 + i )) ||
                            ((unsigned)(++idx) <= length &&
                             diff( &val, img1 + (i+1) ))))
                        {
                            int j = i;
                            mask[i] = newMaskVal;
                            while( !mask[--j] && diff( img + j, img + (j+1) ))
                                mask[j] = newMaskVal;
    
                            while( !mask[++i] &&
                                  ((val = img[i],
                                    diff( &val, img + (i-1) )) ||
                                   (((unsigned)(idx = i-L-1) <= length &&
                                     diff( &val, img1 + (i-1) ))) ||
                                   ((unsigned)(++idx) <= length &&
                                    diff( &val, img1 + i )) ||
                                   ((unsigned)(++idx) <= length &&
                                    diff( &val, img1 + (i+1) ))))
                                mask[i] = newMaskVal;
    
                            ICV_PUSH( YC + dir, j+1, i-1, L, R, -dir );
                        }
                    }
            }
    	    
            // 这里才是真正的填充当前行 
            img = (_Tp*)(pImage + YC * step); 
            if( fillImage ) 
                for( i = L; i <= R; i++ ) 
                    img[i] = newVal; 
            /*else if( region )
             for( i = L; i <= R; i++ )
             sum += img[i];*/
        }
    
        if( region )
        {
            region->pt = seed;
            region->label = saturate_cast<int>(newMaskVal);
            region->area = area;
            region->rect.x = XMin;
            region->rect.y = YMin;
            region->rect.width = XMax - XMin + 1;
            region->rect.height = YMax - YMin + 1;
        }
    }
    
    }

总结：OpenCV的填充原理其实很简单，就是一行一行找，然后把还没填充的区域入栈。用向量栈替代递归时所需要的系统堆栈。理解了这些东西之后，就不难理解每一行代码的具体含义。

参考资料

【1】 [https://en.wikipedia.org/wiki/Flood\_fill][https_en.wikipedia.org_wiki_Flood_fill]

[70]: /images/20220517/79d522b26a464623a4a08085d8506cc0.png
[70 1]: /images/20220517/29fbbaa492b3415a92f595ae7bd93a08.png
[70 2]: /images/20220517/755afc80c1df4c65aed09b18eca21219.png
[70 3]: /images/20220517/ffd53354d1484b8eade03ed36c065a1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70]: /images/20220517/502007648fae4cdb86b036da3c21e2e8.png
[70 4]: /images/20220517/5ed352f81a704d11b3bc6f9a27fa5049.png
[https_en.wikipedia.org_wiki_Flood_fill]: https://en.wikipedia.org/wiki/Flood_fill