OpenCV中泛洪填充算法解析与应用

泛洪填充(Flood Fill)很多时候国内的开发者称它为漫水填充，该算法在图形填充与着色应用程序比较常见，属于标配。在图像处理里对二值图像的Hole可以通过泛洪填充来消除，这个是泛洪填充在图像处理中很经典的一个用途，此外还可以通过泛洪填充为ROI区域着色。这个在图像处理也经常用到。让我们首先看一下泛洪填充算法本身，然后再说一下在图像处理中的应用场景。

泛洪填充算法

通常泛洪填充需要从一个点开始，这个点可以随机选择的一点，但是一定要在填充区域内部，然后它就会进行四邻域或者把邻域寻找对周围像素完成填充，直到遇到跟指定随机点像素值不同的像素为止，也可以认为是到达了区域边界。通过邻域像素寻找实现填充速度比较慢、不是泛洪填充好的实现方式，最常见与快速的泛红实现是基于扫描线算法的，步骤如下：

1.首先从开始点出发进行垂直方向列的扫描，填充

2.然后以填充点开始进行每一行的扫描与填充

3.继续以每一行新填充的像素为开始点，执行1,2步骤

4.直到区域所有点都完成填充为止。

图示如下：

第一步：假设有图像如下，红色表种子像素点。

首先进行竖直方向的扫描，填充结果如下：

然后以填充的红色像素为起始点，开始水平方向的扫描填充，结果如下：

用水平方向被填充像素点为种子像素点，继续竖直方式扫描填充，结果如下：

以填充的像素点为种子像素点继续水平方向扫描，结果如下：

这样就完成了对整个区域的填充。从上面的例子可以看出，泛洪填充可以通过递归方式编码实现，但是基于递归方式编码实现有个致命的缺点，对大图填充时候容易导致栈溢出，所以更常用的基于队列或者栈的数据结构实现非递归的泛洪填充。OpenCV中的实现主要是基于栈的扫描线算法实现泛洪填充。

应用场景一：

通过泛洪填充算法实现对二值图像对象区域中Hole填充

运行显示原图如下：

填充以后结果如下：

实现代码如下：

应用场景二：

通过泛洪填充实现对ROI区域的着色， 跟上个例子使用API唯一不同地方是带了mask参数。运行结果如下：

实现代码如下：