泛洪填充实现

Question

这是我基于维基百科定义实现的基于堆栈的泛洪算法的C#代码。在编码时，我只想看到它起作用。它确实做到了。然后，我想知道实际上有多少像素被填充了。因此，在我的代码中，我将返回类型更改为整数，并返回“ctr”变量。但是“ctr”变量实际上是填充像素数量的两倍左右（我编写了一个单独的函数，其唯一目的是计算这些像素 - 只是为了确定）。

可以有人告诉我为什么变量“ctr”会增加两倍？

*Pixel类仅用作位图像素的x，y和颜色值的容器。

public Bitmap floodfill(Bitmap image, int x, int y, Color newColor)
{
    Bitmap result = new Bitmap(image.Width, image.Height);
    Stack<Pixel> pixels = new Stack<Pixel>();
    Color oldColor = image.GetPixel(x, y);
    int ctr = 0;

    pixels.Push(new Pixel(x, y, oldColor));

    while (pixels.Count > 0)
    {
        Pixel popped = pixels.Pop();

        if (popped.color == oldColor)
        {
            ctr++;
            result.SetPixel(popped.x, popped.y, newColor);

            pixels.Push(new Pixel(popped.x - 1, popped.y, image.GetPixel(x - 1, y));
            pixels.Push(new Pixel(popped.x + 1, popped.y, image.GetPixel(x + 1, y));
            pixels.Push(new Pixel(popped.x, popped.y - 1, image.GetPixel(x, y - 1));
            pixels.Push(new Pixel(popped.x, popped.y + 1, image.GetPixel(x, y + 1));
        }
    }

    return result;
}

- libzz

---

如果 ctr 意思是 counter，那么把它叫做 counter 是没有问题的。 - Austin Salonen

Answer 1

你需要检查这里像素的颜色：

if (popped.color == oldColor)

但 popped.color 可能已过时（在50%的情况下似乎是如此）。因为您在将像素插入堆栈时未检查重复项，所以会出现重复项。在弹出这些重复项时，颜色属性早已保存。

也许通过绘图可以更清楚：

我拿了一个有9个像素的位图作为例子。第一个窗格中有像素编号，在右侧有您的堆栈。

您从像素5开始。并将像素2、4、6和8推入堆栈。然后您取出像素2并推入1和3。在下一步中，您弹出1并推入2和4（再次！）。然后您可能会拿出2，并意识到它在被推入时已经获得了新的颜色。（有点晚，但总比没有好）但是：像素4出现了两次，并记住了旧的颜色两次。所以您取出像素4并着色。

几步之后，您会发现图像已填充，但仍有一些项目在您的堆栈中。由于旧的颜色值仍存储在这些项目中，它们被再次计数。

虽然我可能对堆栈的排序有误，但要点仍然有效。

解决方案：

快速且不完美的（因为仍然效率低下）

if (image.GetPixel(popped.x, popped.y) == oldColor)

仅当当前颜色错误时，它才会计算像素，而不是记住的颜色。

建议：在将像素推入堆栈之前，请检查它们是否需要上色。

- DasKrümelmonster

---

我理解你的观点。但随后弹出的像素（具有旧颜色）不应再次推入（在下一次迭代中），因为它的颜色属性已经被 SetPixel 函数改变了。 - libzz

我扩展了我的回答，希望图示能够让它更加清晰明了。就你的评论而言：如果你没有实现某些黑魔法（或者说扩展方法），Bitmap.SetPixel() 绝对不会改变存储在 Pixel 对象中的 Color 值。它甚至不知道你的 Pixel 类存在！ - DasKrümelmonster

谢谢！我现在明白了我忽略的地方。我会尝试你的建议！非常感谢您制作图纸的努力! ^_^ - libzz

Answer 2

如果Pixel只是保存传递给它构造函数的颜色，那么在像素填充后，它不会更新颜色，因此可以使ctr每个像素增加多次。

如果您将Pixel更改为在其构造函数中使用图像指针，则可以重新读取颜色（即使颜色成为读取当前颜色的get属性），或跟踪已经填充的坐标并且不要第二次推送它们。

[编辑]

如果从接受的答案中不明显，GetPixel返回一个Color-值类型。将其视为编码该时间点像素的RGB值的int。

如果您想快速执行填充，请查找Graphics.FloodFill示例。

如果您的目标是学习，我建议将图像数据复制到数组中进行处理，然后再复制回来-大多数经典图像算法使用GetPixel()并不好玩。

- Peter Wishart

---

但是当我推动像素时，它基于图像本身而不是Pixel类。因此，我认为它们不会再进入if语句了。因此，（据说）不会增加ctr。 - libzz

是的，我们的讲师教了我们使用Bitmapdata进行字节指针处理。我已经转换了我的代码，它运行得非常快（在我修改它以避免插入已经插入的像素后，速度更快了）。不过还是谢谢你的建议。 - libzz