1 洪水填充算法（DFS）
在图像处理领域，洪水填充算法是一项旨在实现区域填充和图像分割的关键技术。这一算法的核心思想是从一个起始点开始，通过探索相邻的像素并根据特定条件进行颜色替换，逐步填充整个连通区域。这为图像编辑、计算机视觉以及其他相关领域提供了一种高效、灵活的解决方案。
在计算机科学中，深度优先搜索（DFS）是一种用于遍历或搜索图和树等数据结构的算法。洪水填充算法正是基于DFS思想的一种应用，通过递归或栈的方式探索图像中的像素，实现了对连通区域的快速填充。
下面我的代码展示了使用C++语言实现的一种简单而直观的洪水填充算法。通过定义链表节点和栈结构，我成功地构建了一个能够处理图像填充任务的基础框架。该算法在图像处理软件中被广泛应用，为用户提供了便捷的填充工具，同时在计算机科学的教学和研究中也经常作为经典案例进行讨论。
洪水填充算法的应用不仅局限于图像编辑，还延伸至医学图像分析、计算机辅助设计以及虚拟现实等领域。其灵活性和高效性使其成为处理图像中连通区域的理想选择。通过深入理解洪水填充算法，我们能够更好地应用于实际场景，并挖掘出更多图像处理领域的创新可能性。这一算法无疑是图像处理工具箱中的一把强大工具，为处理图像中的复杂任务提供了可靠的解决方案。
2 数据结构及思维导图
深度优先搜索（DFS）
链表（ListNode 结构）：
设计目的：用于构建栈数据结构，存储洪水填充算法中需要处理的像素坐标。
属性：int x, y：表示像素的二维坐标。
ListNode* next：指向链表中下一个节点的指针。
操作：构造函数 ListNode(int x_, int y_)：初始化节点，设置坐标和 next 指针。
栈（Stack 类）：
设计目的：用于实现深度优先搜索（DFS）的迭代，存储待处理的像素坐标。
属性：ListNode* top：指向栈顶节点的指针。
操作：构造函数 Stack()：初始化栈，将栈顶指针置为空。
bool isEmpty() const：检查栈是否为空。
void push(int x, int y)：将新的像素坐标入栈。
void pop()：弹出栈顶节点。
int topX() const：返回栈顶节点的 x 坐标。
int topY() const：返回栈顶节点的 y 坐标。
洪水填充算法（floodFill 函数）：
设计目的：使用深度优先搜索迭代版本，填充相邻区域的像素。
输入参数：int image[10][10]：表示图像的二维数组。
int rows, int cols：图像的行数和列数。
int x, int y：洪水填充的起始点坐标。
int newColor：新的颜色值。
操作：利用栈进行深度优先搜索，修改相邻区域的像素颜色。
3 核心代码
使用链表的堆栈的基本实现。它具有检查堆栈是否为空 （）、将新元素推送到堆栈 （）、弹出顶部元素 （） 以及检索顶部元素 （ 和 ） 的坐标的功能。StackisEmptypushpoptopXtopY
函数使用堆栈来实现泛洪填充算法。它从指定点开始，并继续填充原始颜色的连接像素，直到不再有这样的像素。它将每个像素的颜色更新为新颜色。floodFill(x, y)
4 代码结果
（2,2） 处的像素及其连接区域已填充了泛滥填充算法已正确识别并填充了从指定点开始的原始颜色的连接像素。
该结果验证了洪水填充算法的成功应用，并在输出图像中用新颜色突出显示了填充区域。
5 算法优缺点
算法的优点：
单纯：洪水填充算法的实现相对简单，使其可用于广泛的应用。
效率：在许多情况下，该算法可以有效地填充连续区域，尤其是在使用堆栈或队列迭代实现时。
内存效率：此实现中基于堆栈的方法有效地使用内存来跟踪要处理的像素。
适用性：该算法适用于特定区域需要用新颜色填充的场景。
算法的缺点：
堆栈溢出风险：如果连接的区域太大，递归或基于堆栈的实现可能会导致堆栈溢出错误。这可以通过使用带有循环的迭代方法或增加堆栈大小来缓解。
在大图像上的性能：由于该算法的递归或迭代性质，该算法可能无法在大型图像或区域上发挥最佳性能，从而导致潜在的性能问题。
断开连接的区域：基本洪水填充算法假定要填充的区域已连接。如果存在多个具有相同原始颜色的断开连接的区域，则每个区域都需要单独调用。
边界检查开销：该算法涉及频繁的边界检查，这可能会增加开销，尤其是在图像尺寸较大的情况下。
缺乏优化：此实现不包括某些优化，例如维护访问的数组以避免重新处理像素或合并多线程以进行并行处理。
对起点的依赖性：结果可能会因具有相同原始颜色的区域内的起点而异。
6 附件之源代码
#include <iostream>
#include <stack>
// 定义链表节点
struct ListNode {
int x, y;
ListNode* next;
ListNode(int x_, int y_) : x(x_), y(y_), next(nullptr) {}
};
// 定义栈结构
class Stack {
private:
ListNode* top;
public:
Stack() : top(nullptr) {}
bool isEmpty() const {
return top == nullptr;
}
void push(int x, int y) {
ListNode* newNode = new ListNode(x, y);
newNode->next = top;
top = newNode;
}
void pop() {
if (!isEmpty()) {
ListNode* temp = top;
top = top->next;
delete temp;
}
}
int topX() const {
return top->x;
}
int topY() const {
return top->y;
}
};
// 洪水填充算法的实现
void floodFill(int image[10][10], int rows, int cols, int x, int y, int newColor) {
int originalColor = image[x][y];
if (originalColor == newColor) {
return; // 避免重复填充
}
Stack stack;
stack.push(x, y);
while (!stack.isEmpty()) {
x = stack.topX();
y = stack.topY();
stack.pop();
if (x < 0 || x >= rows || y < 0 || y >= cols || image[x][y] != originalColor) {
continue;
}
// 修改当前像素的颜色
image[x][y] = newColor;
// 将相邻像素入栈
stack.push(x + 1, y);
stack.push(x - 1, y);
stack.push(x, y + 1);
stack.push(x, y - 1);
}
}
int main() {
int image[10][10] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1, 1, 1, 1, 1},
{1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
int rows = 10;
int cols = 10;
// 在(2,2)处进行洪水填充，将0替换为2
floodFill(image, rows, cols, 2, 2, 2);
// 输出填充后的图像
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
std::cout << image[i][j] << " ";
}
std::cout << std::endl;
}
return 0;
}
