Search code examples
c#flood-fill

c# how to make flood fill work over color gradients?

I am not very experienced in c# yet and have to write a flood fill algorithm that also works when there is a slight change in color (like a shadow in a picture). I found a stack-based 4-way algorithm which I modified to also change pixels that have a slightly different value in the RGB-spectrum than the one before (the whole "RGB-Test" part) instead of only an area with a single color:

private void FloodFill2(Bitmap bmp, Point pt, Color targetColor, Color replacementColor)
    {
        Stack<Point> pixels = new Stack<Point>();
        pixels.Push(pt);

        while (pixels.Count > 0)
        {
            Point a = pixels.Pop();
            if (a.X < bmp.Width && a.X > 0 &&
                    a.Y < bmp.Height && a.Y > 0)//make sure we stay within bounds
            {
                // RGB-Test Start
                green = false;
                red = false;
                blue = false;

                if (bmp.GetPixel(a.X, a.Y).G > targetColor.G)
                {
                    if (targetColor.G - bmp.GetPixel(a.X, a.Y).G > (-20))
                    {
                        green = true;
                    }
                }
                else
                {
                    if (bmp.GetPixel(a.X, a.Y).G - targetColor.G > (-20))
                    {
                        green = true;
                    }
                }

                if (bmp.GetPixel(a.X, a.Y).R > targetColor.R)
                {
                    if (targetColor.R - bmp.GetPixel(a.X, a.Y).R > (-20))
                    {
                        red = true;
                    }
                }
                else
                {
                    if (bmp.GetPixel(a.X, a.Y).R - targetColor.R > (-20))
                    {
                        red = true;
                    }
                }

                if (bmp.GetPixel(a.X, a.Y).B > targetColor.B)
                {
                    if (targetColor.B - bmp.GetPixel(a.X, a.Y).B > (-20))
                    {
                        blue = true;
                    }
                }
                else
                {
                    if (bmp.GetPixel(a.X, a.Y).B - targetColor.B > (-20))
                    {
                        blue = true;
                    }
                }
                // RGB-Test End

                if (red == true && blue == true && green == true)
                { 
                    bmp.SetPixel(a.X, a.Y, replacementColor);
                    pixels.Push(new Point(a.X - 1, a.Y));
                    pixels.Push(new Point(a.X + 1, a.Y));
                    pixels.Push(new Point(a.X, a.Y - 1));
                    pixels.Push(new Point(a.X, a.Y + 1));
                }
            }
        }
        //refresh our main picture box
        pictureBox1.Image = bmp;
        pictureBox1.SizeMode = PictureBoxSizeMode.Zoom;
        return;
    }

The problem is now that it will stop if the gradient in the image is getting too strong, which then looks like this: https://i.sstatic.net/15jhd.png

As a solution I thought of changing the "targetColor" to the new color of the pixel that is currently being changed, so that it can "travel" over the gradient and only stop if there suddenly is too big of a difference in color.

But here comes the problem of my little knowledge with stacks and c# in general, because with a first attempt of modifying this part of the code like this

if (red == true && blue == true && green == true)
                { 
                    newColor = bmp.GetPixel(a.X, a.Y); // added this
                    bmp.SetPixel(a.X, a.Y, replacementColor);
                    pixels.Push(new Point(a.X - 1, a.Y));
                    pixels.Push(new Point(a.X + 1, a.Y));
                    pixels.Push(new Point(a.X, a.Y - 1));
                    pixels.Push(new Point(a.X, a.Y + 1));
                    targetColor = newColor; // and this
                }

I get results that look like that: https://i.sstatic.net/U52mF.png

This is weird because it does exactly what it should but just not everywhere it is supposed to and only in the form of some stripes across the picture.

I thank you for every solution and other ideas on how to make this work properly.

Solution

  • My approach to this problem was to also store in stack information about color that was checked when point was added to stack so e.g. we checked pixel (10,15) with colour (255,10,1), and during that we added to stack pixel (10,16) with information about previous color of (10,15), and during pixel check we compare its colour to previous one. Changes I made:

    1) include information about color of prev pixel in stack: for that I used c# construct named touple:

    Stack<(Point point, Color target)> pixels = new Stack<(Point, Color)>();
pixels.Push((pt, target));

    2) while working with stack we get pair pixel/targetColour

        var curr = pixels.Pop();
    var a = curr.point;
    Color targetColor = curr.target;

    3) While adding points to stack we also include old pixel color:

    var old = bmp.GetPixel(a.X, a.Y);
bmp.SetPixel(a.X, a.Y, replacementColor);
pixels.Push((new Point(a.X - 1, a.Y), old));
pixels.Push((new Point(a.X + 1, a.Y), old));
pixels.Push((new Point(a.X, a.Y - 1), old));
pixels.Push((new Point(a.X, a.Y + 1), old));

    Code after some refactoring:

    void FloodFill2(Bitmap bmp, Point pt, Color target, Color replacementColor)
{
    Stack<(Point point, Color target)> pixels = new Stack<(Point, Color)>();
    pixels.Push((pt, target));

    while (pixels.Count > 0)
    {
        var curr = pixels.Pop();
        var a = curr.point;
        Color targetColor = curr.target;

        if (a.X < bmp.Width && a.X > 0 &&
                a.Y < bmp.Height && a.Y > 0)//make sure we stay within bounds
        {
            var tolerance = 10;
            var green = Math.Abs(targetColor.G - bmp.GetPixel(a.X, a.Y).G) < tolerance;
            var red = Math.Abs(targetColor.R - bmp.GetPixel(a.X, a.Y).R) < tolerance;
            var blue = Math.Abs(targetColor.B - bmp.GetPixel(a.X, a.Y).B) < tolerance;

            if (red == true && blue == true && green == true)
            {
                var old = bmp.GetPixel(a.X, a.Y);
                bmp.SetPixel(a.X, a.Y, replacementColor);
                pixels.Push((new Point(a.X - 1, a.Y), old));
                pixels.Push((new Point(a.X + 1, a.Y), old));
                pixels.Push((new Point(a.X, a.Y - 1), old));
                pixels.Push((new Point(a.X, a.Y + 1), old));
            }
        }
    }
    //refresh our main picture box
    pictureBox1.Image = bmp;
    pictureBox1.SizeMode = PictureBoxSizeMode.Zoom;
    return;
}

    Final effect:

    Final effect