CODEWITHSUNDEEP
javaimage-processingstack-overflowflood-fill
Dylan Katz
Dylan Katz

Reputation: 194

Recursive flood-filling overflows stack

I'm working on an algorithm to take images and separate the black and white chunks of pixels, unfortunately, it always seems to overflow the stack. Here's the suspected class:

package me.dylan.eat;

import java.awt.Point;
import java.awt.Rectangle;
import java.awt.image.BufferedImage;
import java.util.ArrayList;

public class Cell {
    public Point location = new Point(0, 0);

    public Cell(int x, int y) {
        location.x = x;
        location.y = y;
    }

    public void recurseNeighbors(ArrayList<Cell> universe, BufferedImage img) {

        if (!universe.contains(this)) {
            universe.add(this);
            ArrayList<Cell> neighbors = CellUtil.assimilateNeighbors(location, img, new Rectangle(0,0,0,0));
                        //get all neighbors of the same color
            for (Cell c : neighbors) {
                if (!universe.contains(c)) {
                    c.recurseNeighbors(universe, img);
                }
            }
        }
    }
}

EDIT: The image is 640x480, is that too big? The exception is thrown on line 23.

Upvotes: 1

Views: 575

Answers (2)

Mario Rossi
Mario Rossi

Reputation: 7799

You can also increase the stack size. Personally, I prefer to keep algorithms recursive if that's the natural thing to do. This obviously as long as application requirements / restrictions allow.

The way of doing this is JVM-dependent. If you are using Hotspot,

java -Xss50m <rest of your command line>

should do. 50m stands for 50 MB. Try bigger values and even a 64-bit JVM if needed (let me know, I'm not 100% sure a 64-bit JVM will make much difference, if any).

The default value for stack size is also JVM-dependent, but usually goes from 300 KB to 1 MB. You would be increasing it by a factor of 50x to 165x.

Please note that these instructions increase the stack size of every thread in the JVM. If you have too many of them, you could prefer creating a separate thread for your process specifying an individual stack size for it. Please also note that honoring or ignoring this parameter is also JVM-dependent.

Upvotes: 0

Jason C
Jason C

Reputation: 40335

640x480 is too big. Worst case you'll end up 640*480 = 307200 levels deep.

You have a few options. Option 1 is to not do it recursively, instead maintain a queue of pixels to be processed. Initialize the Queue with the first round of Cells to be checked, then while the queue is not empty, remove the front item, process it, and add new Cells to be processed to the queue.

Option 2 is an iterative approach, such as the ones described here (a queue-based approach is described there as well).

While recursion seems like a natural way to implement a flood fill, in practice it generally hits stack limitations and iterative or queue based algorithms run more efficiently.

Depending on your goal, you may also want to consider an entirely different approach, such as union-find (where two cells are equivalent if they are both the same color), which will give you a list of all black and white groupings in your image in O(log n) time (where n is pixel count), in a single pass.

Upvotes: 2

Related Questions