图像分割经典算法--《泛洪算法》（Flood Fill）

1.算法介绍

泛洪算法——Flood Fill，（也称为种子填充——Seed Fill）是一种算法，用于确定连接到多维数组中给定节点的区域。 它被用在油漆程序的“桶”填充工具中，用于填充具有不同颜色的连接的，颜色相似的区域，并且在诸如围棋（Go）和扫雷（Minesweeper）之类的游戏中用于确定哪些块被清除。泛洪算法的基本原理就是从一个像素点出发，以此向周边的像素点扩充着色，直到图形的边界。

2.算法分类

泛洪填充算法采用三个参数：起始节点（start node），目标颜色（target color）和替换颜色（replacement color）。 该算法查找阵列中通过目标颜色的路径连接到起始节点的所有节点，并将它们更改为替换颜色。 可以通过多种方式构建泛洪填充算法，但它们都明确地或隐式地使用队列或堆栈数据结构。
根据我们是否考虑在连接角落处接触的节点，我们有两种变体：分别为八邻域泛洪（八种方向）和四邻域泛洪（四种方向）。

（1）四邻域泛洪

传统递归方式

传统的四邻域泛洪算法的思想是对于像素点(x,y)，将其着色之后将其周围的上下左右四个点分别进行着色。递归实现方式如下：

伪代码表示

Flood-fill (node, target-color, replacement-color):1. If target-color is equal to replacement-color, return.2. If the color of node is not equal to target-color, return.3. Set the color of node to replacement-color.4. Perform Flood-fill (one step to the south of node, target-color, replacement-color).Perform Flood-fill (one step to the north of node, target-color, replacement-color).Perform Flood-fill (one step to the west of node, target-color, replacement-color).Perform Flood-fill (one step to the east of node, target-color, replacement-color).5. Return.

函数实现

void floodFill4(int x, int y, int newColor, int oldColor)
{if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor){scre