Flood fill using a stack

Question

I am using the recursive Flood fill algorithm in Java to fill some areas of a image. With very small images it works fine, but when de image becomes larger the JVM gives me a Stack Over Flow Error.

That's the reason why I have to reimplement the method using a Flood Fill with my own stack. (I read that's the best way to do it in these kind of cases)

Can anyone explain me how to code it? (if you don't have the code at hand, with the pseudo-code of the algorithm will be fine)

I've read a lot in the Internet but I haven't understood it very well.

EDIT: I added my recursive code

public void floodFill(int x, int y, Color targetColor,Color replacementColor) {

    if (img.getRGB(x, y) != targetColor.getRGB()) return;

    img.setRGB(x, y, replacementColor.getRGB());
    floodFill(x - 1, y, targetColor, replacementColor);
    floodFill(x + 1, y, targetColor, replacementColor);
    floodFill(x, y - 1, targetColor, replacementColor);
    floodFill(x, y + 1, targetColor, replacementColor);

    return;

}

Thanks!

Answer 1

You can use Queue to remove recursion from floodfill algorithm. Here are some basic ideas:

1. Have a way to mark visited points
2. At the beginning, queue the start point.
3. While the queue is not empty, continue dequeuing its element. And with each element
   1. Fill its color and mark just-dequeued point as visited
   2. Enqueue unvisited adjacent points that has the same color

The below is my Java code to solve similar but different problem of blob detection. I hope you can get some ideas from this and can adapt it the the problem. The code is not well-factored though.

package blobdetector;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import javax.imageio.ImageIO;
import javax.management.Query;

public class Main {

    public Main() {
    }

    public static boolean isBlack(BufferedImage image, int posX, int posY) {

        int color = image.getRGB(posX, posY);

        int brightness = (color & 0xFF) + ((color >> 2) & 0xFF)
        + ((color >> 4) & 0xFF);
        brightness /= 3;

        return brightness < 128;
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("ERROR: Pass filename as argument.");
            return;
        }

        String filename = args[0];
        // String filename =
        // "C:\\Users\\Natthawut\\Desktop\\blob.jpg";
        try {
            BufferedImage bimg = ImageIO.read(new File(filename));

            boolean[][] painted = new boolean[bimg.getHeight()][bimg.getWidth()];

            for (int i = 0; i < bimg.getHeight(); i++) {
                for (int j = 0; j < bimg.getWidth(); j++) {

                    if (isBlack(bimg, j, i) && !painted[i][j]) {

                        Queue<Point> queue = new LinkedList<Point>();
                        queue.add(new Point(j, i));

                        int pixelCount = 0;
                        while (!queue.isEmpty()) {
                            Point p = queue.remove();

                            if ((p.x >= 0)
                                    && (p.x < bimg.getWidth() && (p.y >= 0) && (p.y < bimg
                                            .getHeight()))) {
                                if (!painted[p.y][p.x]
                                                  && isBlack(bimg, p.x, p.y)) {
                                    painted[p.y][p.x] = true;
                                    pixelCount++;

                                    queue.add(new Point(p.x + 1, p.y));
                                    queue.add(new Point(p.x - 1, p.y));
                                    queue.add(new Point(p.x, p.y + 1));
                                    queue.add(new Point(p.x, p.y - 1));
                                }
                            }
                        }
                        System.out.println("Blob detected : " + pixelCount
                                + " pixels");
                    }

                }
            }

        } catch (IOException ex) {
            ex.printStackTrace();
        }

    }

}

Test input:

Answer 2

here is my implementation base on infos from this page and others gathered on the web (tested and working)

have fun ;-)

public static void floodFillImage(BufferedImage image,int x, int y, Color color) 
{
    int srcColor = image.getRGB(x, y);
    boolean[][] hits = new boolean[image.getHeight()][image.getWidth()];

    Queue<Point> queue = new LinkedList<Point>();
    queue.add(new Point(x, y));

    while (!queue.isEmpty()) 
    {
        Point p = queue.remove();

        if(floodFillImageDo(image,hits,p.x,p.y, srcColor, color.getRGB()))
        {     
            queue.add(new Point(p.x,p.y - 1)); 
            queue.add(new Point(p.x,p.y + 1)); 
            queue.add(new Point(p.x - 1,p.y)); 
            queue.add(new Point(p.x + 1,p.y)); 
        }
    }
}

private static boolean floodFillImageDo(BufferedImage image, boolean[][] hits,int x, int y, int srcColor, int tgtColor) 
{
    if (y < 0) return false;
    if (x < 0) return false;
    if (y > image.getHeight()-1) return false;
    if (x > image.getWidth()-1) return false;

    if (hits[y][x]) return false;

    if (image.getRGB(x, y)!=srcColor)
        return false;

    // valid, paint it

    image.setRGB(x, y, tgtColor);
    hits[y][x] = true;
    return true;
}

Answer 3

An important point in flood fill is if you are processing points depth first or breadth first. Depth first is the original solution you were looking at using a stack, breadth first are algorithms shown below using a queue to store point. The difference is substantial when filling in big convex spaces. A breadth first method stores on a perfectly convex area roughly the circle edge (or fill edge). If you use a depth first method you may in worst case store every pixel in the conxex area, that means that in worst case a 1000x1000 image flood filled may require 1000000 of stack frames.

Answer 4

You should return the last floodFill statement, turning it into a tail call. This will save you stack space.