6

这是我基于堆栈的洪水填充算法的 C# 实现(我基于维基百科的定义)。早些时候在编码时,我只想看到它工作。它确实做到了。然后,我想知道实际填充的像素数。所以在我的代码中,我将返回类型更改为 int 并返回“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;
}
4

2 回答 2

7

您确实在此处检查像素的颜色:

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)

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

推荐:在将它们推入堆栈之前检查您的像素是否需要着色。

于 2013-01-31T20:05:12.313 回答
0

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

如果您更改 Pixel 以在其构造函数中获取指向图像的指针,您可以重新读取颜色(即,将颜色设置为读取当前颜色的 get 属性),或者跟踪已经填充的坐标并且不要再推动那些时间。

[编辑]

如果从接受的答案中看不出来,GetPixel 会返回一个 Color - 一种值类型。可以把它想象成一个 int,它对当时像素的 RGB 值进行编码。

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

如果您的目标是学习,我建议您将图像数据复制到一个数组中进行处理并再次返回 - 大多数经典图像算法使用 GetPixel() 并没有多大乐趣。

于 2013-01-31T20:08:51.880 回答