Algorithm, Flood Fill ( Depth First Search )

Question

I'm working with Java.
I'm developing a paint program, the "Paint Can" tool is using a Flood Fill algorithm, but it is too expensive.

Here is the code:

private int[] dx = { -1, 0, 1, 0 };
private int[] dy = { 0, 1, 0, -1 };

public void floodFill(int x, int y, Color target_color, Color replacement_color) {
    Stack<Integer[]> stack = new Stack<Integer[]>();
    if (imageBuffer.getRGB(x, y) == replacement_color.getRGB())
         return;
    stack.push(new Integer[] { x, y });
    while (!stack.isEmpty()) {
        Integer[] aux = stack.peek();
        imageBuffer.setRGB(aux[0], aux[1], replacement_color.getRGB());
        stack.pop();
        for (int i = 0; i < 4; i++) {
            if (imageBuffer.getRGB(aux[0] + dx[i], aux[1] + dy[i]) == target_color.getRGB())
                stack.push(new Integer[] { aux[0] + dx[i], aux[1] + dy[i] });
        }

    }
}

Can someone help me make this more efficient?

It takes (for 1020x700 pixel image) about 1200ms to execute.

I think the main thing is you need a better algorithm. http://en.wikipedia.org/wiki/Flood_fill is a good resource. There are some micro optimizations you could make (for example `replacement_color.getRGB()` is evaluated each time, as it `target_color.getRGB()` but I don't imagine this'll make much difference. — Jeff Foster, Nov 03 '11 at 13:30

score 1 · Answer 1 · edited May 23 '17 at 11:43

1

The basic idea of using the queue algorithm, you can read here (+ example).

You can probably find other optimizations and implementations, but I found this one Queue-Linear Flood Fill. You should do the job yourself though.

edited May 23 '17 at 11:43

Community

1
1

answered Nov 03 '11 at 13:25

hovanessyan

30,580
6
55
83

score 1 · Answer 2 · answered Nov 03 '11 at 13:34

One quick easy (and probably small) improvement would be to replace the Stack with an ArrayDeque.

This will allow you to specify a initial capacity AND bring your code more up-to-date. The Vector underlpinning a Stack will need to be expanded many times when the floodFill area contains many pixels. This is wasteful -- but not all that costly

score 0 · Answer 3 · answered Nov 03 '11 at 13:36

I had tried to implement a floodfill algorithm for quite a while about a year ago. I first tried my own solutions, and when they were not performant enough, I went to the internet and found this implementation.

The QuickFill (the actual algorithm starts about halfway down the page) algorithm worked excellently. It would fill my droid milestone's screen (480x854) in under a half second. With newer hardware (or even desktop hardware) it would probably work even faster than that. Of course you will have to port it to Java, but it shouldn't be too difficult, especially if I can do it!

score 0 · Answer 4 · answered Nov 03 '11 at 13:45

I'd say that you've got a lot of memory allocations going on. You allocate a new Integer[] for every pixel. I'd perhaps go with two stacks of primitives (say, array lists like the ones in trove4j), for the x and y to be processed, or at least replace Integer[] with int[].

If that's not enough, perhaps a scanline algorithm would help.

Algorithm, Flood Fill ( Depth First Search )

4 Answers4