How do I get a flood fill algorithm to cope with closed circles?

Question

I have an application that accepts images as input and removes the background on which the image was taken. For example, if you pass in an image of a book on a blanket, the resulting image will be just the book with a transparent background.

The problem I have is when you input an image that has a large empty space in it, e.g. an elastic band. The floodfill algorithm starts at the corners of the image and removes the background of the picture, but of course it never makes it into the interior of the elastic band.

Is there a way of implementing this such that I can take an image of a closed circle against a background and get back just the loop itself, with no background inside or outside it?

Answer 1

This question, and its answers address a very similar problem.

Answer 2

You could always resample the image after every flood fill, and restart it whenever you find a color that matches the original background.

Flood fill algorithms are designed to start in one spot, and from there fill a constrained area, an area of similar colors. The circle does not match that background color, so the fill algorithm doesn't "jump" it to find others.

The solution is to flood different areas.

Here is a very crude, recursive, slow flood fill algorithm (from memory, untested):

public void floodfill(Image img, int x, int y, Color oldColor, Color newColor) {
    // Check boundary
    if (img.contains(x, y)) {
        // Get current pixel color
        Color currentColor = img.getColor(x, y);
        // Check color match
        if (currentColor.equals(oldColor)) {
            // Set to new color
            img.setColor(x, y, newColor);

            // Start again on each of the neighbors
            floodFill(img, x - 1, y, oldColor, newColor);
            floodFill(img, x + 1, y, oldColor, newColor);
            floodFill(img, x, y - 1, oldColor, newColor);
            floodFill(img, x, y + 1, oldColor, newColor);
        }
    }
}

Answer 3

you can figure out what the predominant color of the background is (Which you should be able to do since you're able to remove the background starting at the corners) and look for that color everywhere else in the image.