您的位置: 首页  >  文章  >  图像分割经典算法--《泛洪算法》（Flood Fill）

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

分类: 文章 • 2025-03-24 19:36:33

1.算法介绍

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

2.算法分类

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

（1）四邻域泛洪

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

传统递归方式

传统的四邻域泛洪算法的思想是对于像素点(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)
  {
    screenBuffer[y][x] = newColor; 
    floodFill4(x + 1, y    , newColor, oldColor);
    floodFill4(x - 1, y    , newColor, oldColor);
    floodFill4(x    , y + 1, newColor, oldColor);
    floodFill4(x    , y - 1, newColor, oldColor);
  }
}

四邻域泛洪算法改进

递归方式非常消耗内存，若所需着色的面积非常大，会导致溢出现象。因此，下面我们将介绍四邻域泛洪算法的非递归方式。
这里我们使用一个栈（或队列）来存储未被着色的点，然后依次将存在于着色空间内的点的上下左右的点加入栈（或队列），依次着色直到栈（或队列）为空。基于栈（或队列）的显式实现（有时称为“Forest Fire算法”）在下面的伪代码中显示。 它类似于简单的递归解决方案，除了它不是进行递归调用，而是将节点推送到栈（或队列）中以供使用：

伪代码表示（Queue Way）

Flood-fill (node, target-color, replacement-color):
  1. If target-color is equal to replacement-color, return.
  2. If color of node is not equal to target-color, return.
  3. Set Q to the empty Queue.
  4. Set the color of node to replacement-color.
  5. Add node to the end of Q.
  6. While Q is not empty:
  7.     Set n equal to the first element of Q.
  8.     Remove first element from Q.
  9.     If the color of the node to the west of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 10.     If the color of the node to the east of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 11.     If the color of the node to the north of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 12.     If the color of the node to the south of n is target-color,
             set the color of that node to replacement-color and add that node to the end of Q.
 13. Continue looping until Q is exhausted.
 14. Return.

代码实现（Stack Way）

void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop
  emptyStack();
 
  static const int dx[4] = {0, 1, 0, -1}; 
  static const int dy[4] = {-1, 0, 1, 0}; 
 
  if(!push(x, y)) return;
  while(pop(x, y))
  {
    screenBuffer[y][x] = newColor;
    for(int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        if(!push(nx, ny)) return;
      }
    }
  }
}

（2）八邻域泛洪

图像分割经典算法--《泛洪算法》（Flood Fill）
八邻域算法是将一个像素点的上下左右，左上，左下，右上，右下都进行着色。

递归方式

void floodFill8(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)
  {
    screenBuffer[y][x] = newColor;
 
    floodFill8(x + 1, y    , newColor, oldColor);
    floodFill8(x - 1, y    , newColor, oldColor);
    floodFill8(x    , y + 1, newColor, oldColor);
    floodFill8(x    , y - 1, newColor, oldColor);
    floodFill8(x + 1, y + 1, newColor, oldColor);
    floodFill8(x - 1, y - 1, newColor, oldColor);
    floodFill8(x - 1, y + 1, newColor, oldColor);
    floodFill8(x + 1, y - 1, newColor, oldColor);
  }
}

非递归方式（借用栈的方式）

void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
  if(newColor == oldColor) return; //avoid infinite loop
  emptyStack();
 
  static const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  static const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; 
 
  if(!push(x, y)) return;
  while(pop(x, y))
  {
    screenBuffer[y][x] = newColor;
    for(int i = 0; i < 8; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
        if(!push(nx, ny)) return;
      }
    }
  }
}

（3）描绘线算法(Scanline Fill)

利用填充线来加速算法， 它不是在堆栈上推动每个潜在的未来像素坐标，而是检查相邻线（前一个和下一个）以找到可能在未来通过中填充的相邻段， 线段的坐标（开始或结束）被推到堆栈上。 在大多数情况下，该扫描线算法至少比每像素算法快一个数量级。
图像分割经典算法--《泛洪算法》（Flood Fill）
该算法的过程是：先将一条线上的像素点进行着色，然后依次向上下扩张，直到着色完成。算法实现如下：

递归方式

void floodFillScanline(int x, int y, int newColor, int oldColor){
	if(newColor==oldColor) return;
	if(screen[x][y]!=oldColor) return;
	int x1=x;
	while(x1<w&&screen[x1][y]==oldColor){
	    screen[x1][y]=newColor;
	    x1++;
	}
	x1=x-1;
	while(x1>=0&&screen[x1][y]==oldColor){
	    screen[x1][y]=newColor;
	    x1--;
	}
	x1=x;
	while(x1<w&&screen[x1][y]==newColor){
	    if(y<h-1&&screen[x1][y+1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1++;
	}
	x1=x-1;
	while(x1>0&&screen[x1][y]==newColor){
	    if(y>0&&screen[x1][y+1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1--;
	}
	x1=x;
	while(x1<w&&screen[x1][y]==newColor){
	    if(y<h-1&&screen[x1][y-1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1++;
	}
	x1=x-1;
	while(x1>0&&screen[x1][y]==newColor){
	    if(y>0&&screen[x1][y-1]==oldColor) floodFillScanline(x1,y+1,newColor,oldColor);
	    x1--;
	}
}

非递归方式

void floodFillScanline(int x, int y, int newColor, int oldColor){
	if(newColor==oldColor) return;
	if(screen[x][y]!=oldColor) return;
	emptyStack();
	int x1;
	bool spanAbove, spanBelow;
	if(!push(x,y)) return;
	while(pop(x,y)){
	    x1=x;
	    while(x1>0&&screen[x1][y]==oldColor) x1--;
	    x1++;
	    spanAbove = spanBelow = 0;
	    while(x1<w&&screen[x1][y]==oldColor){
	        screen[x1][y]=newColor;
	        if(!spanAbove&&y>0&&screen[x1][y-1]==oldColor){
	            if(!push(x1,y-1)) return;
	            spanAbove=1;
	        }
	        else if(spanAbove&&y>0&&screen[x1][y-1]!=oldColor){
	            spanAbove=1;
	        }
	        if(!spanBelow&&y<h-1&&screen[x1][y+1]==oldColor){
	            if(!push(x1,y+1)) return;
	            spanBelow=1;
	        }
	        else if(spanBelow&&y<h-1&&screen[x1][y+1]!=oldColor){
	            spanBelow=1;
	        }
	        x1++;
	    }
	}
}

（4）大规模行为（Large-scale behaviour）

用于控制洪水填充的主要技术将是以数据为中心或以流程为中心。

以数据为中心（data-centric）

以数据为中心的方法可以使用堆栈或队列来跟踪需要检查的种子像素。使用邻接技术和队列作为其种子像素存储的4向泛洪填充算法产生扩展的菱形填充。
效率：每个像素填充检查4个像素（8个填充为8个像素）。
图像分割经典算法--《泛洪算法》（Flood Fill）

以流程为中心（process-centric）

以流程为中心的算法必须使用堆栈。使用邻接技术和堆栈作为其种子像素存储的4路泛洪填充算法产生具有“后续填充的间隙”行为的线性填充。 这种方法尤其适用于较旧的8位计算机游戏。
效率：每个像素填充检查4个像素（8个填充为8个像素）。
图像分割经典算法--《泛洪算法》（Flood Fill）

3.参考

以下为本博客的参考内容：

1.“Flood fill” - Wikipedia
https://en.wikipedia.org/wiki/Flood_fill

2.“FloodFill（泛洪算法)”
https://blog.****.net/lion19930924/article/details/54293661

3.“图像处理------泛洪填充算法(Flood Fill Algorithm) 油漆桶功能”
https://blog.****.net/mao0514/article/details/47041409

相关推荐