Background removing algorithm - rewrite
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

We currently have a process inside a library that handles image manipulation. Its job is to scan an image and remove its background. it works really well but on convex images it seems to get stuck, its a logical issue I think in how it scans. (linear top down process)

http://pastebin.com/4hzst8Hy

Id like to see if anyone here has a smarter algorithm or approach for scanning the background of the image. What we do now is scan it for a color + threshold, and then replace it either with nothing and end up with transparency or with a color.

here are a couple of examples of what it can do
scan background of the original image and replace with purple
http://screencast.com/t/9KBuFU08
(notice the line on the right side, this is the issue Im trying to solve with convex items

http://screencast.com/t/7m9JXOwms
this is where we scan the white background of the floorplan and then create alpha layer and then apply shadow.. you can see here it does a good job of not violating borders.

Ideally code is in c# or C++ but Im open to best and most performance based solution. Final solution needs to be windows server friendly but can be in any language that gets us to it.

I am not afraid of bonusing participation on this project so fi there is a solution by someone as a starting place I will comp those who provide valuable input and revisions.

awarded to Kefir

Crowdsource coding tasks.

1 Solution

Winning solution

Replace your FloodFill method with this:

public static void FloodFill(PixelManipulator manipulator, Point position, Pixel targetColor, Pixel replaceColor, byte threshold)
    {
        unchecked
        {
            Queue<Point> q = new Queue<Point>((manipulator.Width * manipulator.Height));
            manipulator.Position = position;

            if (!manipulator.Current.Similar(targetColor, threshold))
                return;

            q.Enqueue(manipulator.Position);

            while (q.Count > 0)
            {
                Point n = q.Dequeue();
                if (n.X < 0 || n.Y < 0 || n.X > manipulator.Width || n.Y > manipulator.Height)
                {
                    continue;
                }

                manipulator.Position = n;
                if (manipulator.Current == replaceColor || !manipulator.Current.Similar(targetColor, threshold))
                {
                    continue;
                }

                manipulator.Current = replaceColor;
                q.Enqueue(new Point(n.X - 1, n.Y));  //Left
                q.Enqueue(new Point(n.X + 1, n.Y));  //Right
                q.Enqueue(new Point(n.X, n.Y-1));  //Top
                q.Enqueue(new Point(n.X, n.Y+1));  //Bottom
            }
        }
    }

(http://pastebin.com/jKTy0ztg)

Should work properly for any images.
You did not include your PixelManipulator, Point and Pixel classes so I hope I got them right.

Thanks for the info, here is the other class that was missing http://pastebin.com/qDLz5g37
Qdev almost 5 years ago
So, did the solution fix your issue?
Kefir almost 5 years ago
I've tried my solution with additional code you provided and it works with your example image (http://screencast.com/t/9KBuFU08)
Kefir almost 5 years ago
Cool, I am trying to get my guys to update the lib.
Qdev almost 5 years ago
there is a while() {} loop that never stops, got any ideas?
Qdev almost 5 years ago
You mean while (q.Count > 0)? Can you send an image which causes that?
Kefir almost 5 years ago
From our team - the while loop will exit only if the q Queue is empty. but inside that loop, elements are dequeed and more elements enqueued : Point n = q.Dequeue(); ... then q.Enqueue(new Point(n.X - 1, n.Y)); //Left q.Enqueue(new Point(n.X + 1, n.Y)); //Right q.Enqueue(new Point(n.X, n.Y - 1)); //Top q.Enqueue(new Point(n.X, n.Y + 1)); //Bottom IMO, that's why it never stops
Qdev almost 5 years ago
Can you please provide FloodFill parameter values that you use for that image? Still can't reproduce the bug. We don't enqueue more items when current position is either already updated or not suitable, so eventually the queue must become empty..
Kefir almost 5 years ago
Anyway, there is a modified algorithm which is guaranteed to not have infinite loops: http://pastebin.com/X72TaAfJ. Also it fixes a possible bug when targetColor is already present in the image somewhere.
Kefir almost 5 years ago
trying the new code, here is the reply on the other item target color:FFFFFFFF replace color:ec22c8 threshold: 38 Exception type: AccessViolationException Attempted to read or write protected memory. This is often an indication that other memory is corrupt.
Qdev almost 5 years ago
Ohhh, my bad, bounds check is wrong actually! Here is the fixed version http://pastebin.com/iv3mmmrH
Kefir almost 5 years ago
That did it ! http://screencast.com/t/qJMD0ddiFbyw
Qdev almost 5 years ago
Cool! Anything else?
Kefir almost 5 years ago
All good man!, thx for the hurry on this.
Qdev almost 5 years ago
Kefir, for a bonus might you be able to help out with this. Notice our edges are hard. so its possible to end up with something like this http://screencast.com/t/8wvBpRij3v do you have any ideas on how we might be able to do something similar to how http://clippingmagic.com/ does it. I see it that they do 2 things different from us. They come up with a path they can smooth and they add some alpha value smoothing to the edges so it blends better. Ideas?
Qdev almost 5 years ago
Actually i might be on to a solution for edge detection and contouring. I will make another bounty if we end up needing it. Thx again for the help
Qdev almost 5 years ago
If you need smooth edges, I can do that. We just set alpha channel for edge pixels according to how much they differ from target color and how many non-target color pixels are around.
Kefir almost 5 years ago
Kefir, do you mind putting your email on your profile so i can send you a private note. I want to share some additional code and ideas with you.
Qdev almost 5 years ago
Done, "Let other users contact you privately" enabled.
Kefir almost 5 years ago