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

花木成畦手自栽 ！

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

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

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

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

以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* 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部分进行填充，

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

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值的差要满足范围为