Flood Fill implementation

Question

This is my C# implementation of a stack-based flood fill algorithm (which I based on wikipedia's definition). Earlier while coding, I only wanted to see it work. And it did. Then, I wanted to know the number of pixels that was actually filled. So in my code, I changed the return type to int and returned the "ctr" variable. But then ctr turned out to be approximately twice the actual number of filled pixels (I made a separate function with the sole purpose of counting those pixels -- just to know for certain).

Can anyone enlighten as to how and why the variable "ctr" is incremented twice as it should have?

*Pixel class only serves as a container for the x, y, and color values of the pixels from the bitmap.

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;
}

Answer 1

You do check the color of the pixel here:

if (popped.color == oldColor)

But popped.color may be (and apperently is in 50% of the cases) outdated. Because you do not check for duplicates when you insert pixel into your stack you will have duplicates. Upon popping these duplicates, the color attribute would have been saved a long time ago.

Maybe it gets clearer with a drawing:

As an example I took a bitmap with 9 pixels. On the first pane you have the numbering of the pixels, and on the right side you have your stack.

You start with pixel no 5. and push pixels 2, 4, 6 and 8 on the stack. Then you take pixel 2 off and push 1 and 3. In the next step you pop 1 and push 2 and 4 (again!). Then you may take 2 and realise it has already gotten the new color when it was pushed. (A bit late, but better late than never) however: pixel no. 4 is there twice and has remembered the old color twice. So you take pixel no.4 and color it.

Some steps later you have the image filled and still some items on your stack. Because the old color value is still stored inside these items, they get counted again.

While I may have a wrong ordering in the stack, the point stays valid.

Solution to your problem: Quick and dirty (because it it still inefficient)

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

it counts pixels only if the current color is wrong, not the remembered color.

Recommended: Check your Pixels whether they need coloring before pushing them onto the stack.