洪水填充算法详解

洪水填充算法（Flood Fill Algorithm），也被称为种子填充算法，从Photoshop的"油漆桶工具"到扫雷游戏的空白区域扩展，再到医学图像分析中的区域分割，洪水填充算法都发挥着核心作用。

一、洪水填充算法基础概念

1.1 定义与核心思想

洪水填充算法是一种用于在二维网格中连通区域内填充特定颜色或值的算法。其核心思想源于现实生活中的"洪水泛滥"过程：从一个起始点开始，向四周扩散，直到遇到边界条件（如不同颜色、障碍物等）为止。

1.2 典型应用场景

• 图像编辑软件：如Photoshop的油漆桶工具，用于快速填充颜色
• 游戏开发：扫雷游戏中空白区域的扩展、地图区域划分
• 计算机视觉：医学图像分析中的器官分割、遥感图像中的土地类型分类
• 路径规划：寻找迷宫中的连通区域、机器人探索未知环境

1.3 算法核心要素

• 种子点（Seed Point）：起始填充的位置
• 目标颜色（Target Color）：需要被替换的原始颜色
• 替换颜色（Replacement Color）：用于填充的新颜色
• 连通性规则：定义相邻像素的连接方式（4-邻接或8-邻接）

二、算法实现方式

2.1 递归深度优先搜索（DFS）实现

递归DFS是洪水填充算法最直观的实现方式，其基本思路是：从种子点开始，递归地填充所有相邻且颜色相同的像素。

public class FloodFillDFS {// 4-邻接方向数组（上、下、左、右）private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int rows = image.length;int cols = image[0].length;int targetColor = image[sr][sc];// 若目标颜色与新颜色相同，直接返回if (targetColor == newColor) {return image;}// 从种子点开始DFS填充dfs(image, sr, sc, targetColor, newColor, rows, cols);return image;}private void dfs(int[][] image, int r, int c, int targetColor, int newColor, int rows, int cols) {// 边界检查：超出图像范围或颜色不匹配，停止递归if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != targetColor) {return;}// 填充当前像素image[r][c] = newColor;// 递归处理四个方向的相邻像素for (int[] dir : DIRECTIONS) {dfs(image, r + dir[0], c + dir[1], targetColor, newColor, rows, cols);}}public static void main(String[] args) {FloodFillDFS solver = new FloodFillDFS();int[][] image = {{1, 1, 1},{1, 1, 0},{1, 0, 1}};int[][] result = solver.floodFill(image, 1, 1, 2);for (int[] row : result) {for (int pixel : row) {System.out.print(pixel + " ");}System.out.println();}}
}

2.2 迭代广度优先搜索（BFS）实现

为避免递归可能导致的栈溢出问题，可使用队列实现BFS版本的洪水填充算法。

import java.util.LinkedList;
import java.util.Queue;public class FloodFillBFS {private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int rows = image.length;int cols = image[0].length;int targetColor = image[sr][sc];if (targetColor == newColor) {return image;}Queue<int[]> queue = new LinkedList<>();queue.offer(new int[]{sr, sc});image[sr][sc] = newColor; // 标记为已访问while (!queue.isEmpty()) {int[] curr = queue.poll();int r = curr[0];int c = curr[1];// 遍历四个方向for (int[] dir : DIRECTIONS) {int nr = r + dir[0];int nc = c + dir[1];// 检查边界和颜色匹配if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && image[nr][nc] == targetColor) {image[nr][nc] = newColor;queue.offer(new int[]{nr, nc});}}}return image;}public static void main(String[] args) {FloodFillBFS solver = new FloodFillBFS();int[][] image = {{0, 0, 0},{0, 1, 1}};int[][] result = solver.floodFill(image, 1, 1, 2);for (int[] row : result) {for (int pixel : row) {System.out.print(pixel + " ");}System.out.println();}}
}

2.3 两种实现方式的对比

特性	递归DFS实现	迭代BFS实现
代码复杂度	简单，直观	稍复杂，需维护队列
空间复杂度	O(m*n)（最坏情况下的递归深度）	O(m*n)（最坏情况下的队列大小）
执行顺序	深度优先，可能导致栈溢出	广度优先，逐层填充
适用场景	小规模图像，代码简洁性优先	大规模图像，避免栈溢出问题

三、算法优化策略

3.1 处理边界条件

• 检查目标颜色与替换颜色是否相同：若相同则直接返回原图，避免无限循环
• 边界检查：在访问每个像素前，确保其坐标在有效范围内
• visited 数组优化：对于不可修改原图的场景，使用额外数组标记已访问像素：

boolean[][] visited = new boolean[rows][cols];
// 在填充前检查：!visited[nr][nc] && image[nr][nc] == targetColor

3.2 处理非连通区域

若图像中存在多个不连通但颜色相同的区域，可通过多次调用洪水填充算法实现对不同区域的独立填充。

3.3 扩展连通性规则

• 4-邻接：仅考虑上下左右四个方向的相邻像素
• 8-邻接：考虑上下左右及四个对角线方向的相邻像素

private static final int[][] DIRECTIONS_8 = {{-1, -1}, {-1, 0}, {-1, 1},{0, -1},          {0, 1},{1, -1},  {1, 0}, {1, 1}
};

3.4 性能优化

• 位图标记法：使用额外的二维数组记录已访问的像素，避免重复处理
• 扫描线填充：对于水平连续区域较多的图像，采用扫描线填充可显著减少处理像素数

import java.util.Stack;public class FloodFillScanline {private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}}; // 仅处理上下方向public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int rows = image.length;int cols = image[0].length;int targetColor = image[sr][sc];if (targetColor == newColor) {return image;}Stack<int[]> stack = new Stack<>();stack.push(new int[]{sr, sc});while (!stack.isEmpty()) {int[] curr = stack.pop();int r = curr[0];int c = curr[1];// 向左填充至边界int left = c;while (left >= 0 && image[r][left] == targetColor) {image[r][left] = newColor;left--;}left++; // 恢复有效起始位置// 向右填充至边界int right = c;while (right < cols && image[r][right] == targetColor) {image[r][right] = newColor;right++;}// 检查上下行的连续区域for (int[] dir : DIRECTIONS) {int nr = r + dir[0];if (nr < 0 || nr >= rows) {continue;}// 寻找上下行中与当前行连续的区域int currentCol = left;while (currentCol < right) {// 找到连续区域的起始点while (currentCol < right && image[nr][currentCol] != targetColor) {currentCol++;}if (currentCol >= right) {break;}// 记录起始点并继续寻找下一个区域int startCol = currentCol;while (currentCol < right && image[nr][currentCol] == targetColor) {currentCol++;}stack.push(new int[]{nr, startCol});}}}return image;}public static void main(String[] args) {FloodFillScanline solver = new FloodFillScanline();int[][] image = {{1, 1, 1, 1},{1, 0, 0, 1},{1, 0, 0, 1},{1, 1, 1, 1}};int[][] result = solver.floodFill(image, 1, 1, 2);for (int[] row : result) {for (int pixel : row) {System.out.print(pixel + " ");}System.out.println();}}
}

四、算法的典型应用

4.1 图像编辑工具中的油漆桶功能

• 实现思路：用户点击图像某点，将该点作为种子点，使用洪水填充算法填充相同颜色区域
• 优化方向：支持容差范围（允许填充颜色相近但不完全相同的区域）

4.2 扫雷游戏中的空白区域扩展

• 游戏规则：点击空白区域时，自动扩展显示所有相连的空白区域
• 算法应用：以点击位置为种子点，使用洪水填充算法标记所有相连的空白格子

4.3 医学图像分析中的器官分割

• 应用场景：从CT/MRI图像中分割特定器官（如肝脏、心脏）
• 实现方式：结合阈值分割和洪水填充算法，从手动标记的种子点开始，自动扩展到整个器官区域

4.4 计算机视觉中的区域生长算法

• 核心思想：从种子点开始，逐步合并相似的相邻区域，形成完整的目标对象
• 与洪水填充的关系：洪水填充可视为区域生长的一种特殊情况，基于颜色一致性进行区域扩展

五、局限性与改进方向

5.1 局限性

• 处理大区域效率低：对于大面积连通区域，递归DFS可能导致栈溢出，BFS需要大量内存
• 严格颜色匹配：原始算法要求颜色完全一致，对噪声敏感
• 无法处理复杂边界：对于非均匀边界或渐变区域的处理效果不佳

5.2 改进方向

• 基于容差的填充：允许填充颜色相近的区域，通过设定颜色相似度阈值实现

// 检查颜色是否在容差范围内
private boolean isSimilar(int color1, int color2, int tolerance) {return Math.abs(color1 - color2) <= tolerance;
}

• 自适应边界检测：结合边缘检测算法，在遇到明显边界时停止填充
• 并行优化：对于多核处理器，可采用分块并行填充策略提高效率

算法选择指南

• 小规模图像：优先使用递归DFS实现，代码简洁易维护
• 大规模图像：使用迭代BFS或扫描线填充，避免栈溢出风险
• 复杂场景：结合位图标记和容差机制，提高算法鲁棒性

实践注意事项

• 边界检查：始终确保访问的像素坐标在有效范围内
• 颜色比较：处理浮点数表示的颜色时，使用容差范围而非严格相等
• 性能测试：对大规模图像进行性能测试，根据实际情况选择优化策略

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～