Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Flood fill using a stack

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!

like image 997
dafero Avatar asked May 06 '10 17:05

dafero


People also ask

What are flood fill techniques?

Flood fill is an algorithm mainly used to determine a bounded area connected to a given node in a multi-dimensional array. It is a close resemblance to the bucket tool in paint programs. The most approached implementation of the algorithm is a stack-based recursive function, and that's what we're gonna talk about next.

What are the three flood fill techniques you can use in your sketch?

The traditional flood-fill algorithm takes three parameters: a start node, a target color, and a replacement color.

How flood fill works if the area we want to paint has more than one interior color?

When boundary is of many colors and interior is to be filled with one color we use this algorithm. In fill algorithm, we start from a specified interior point (x, y) and reassign all pixel values are currently set to a given interior color with the desired color.

What are the disadvantages of flood fill algorithm?

Disadvantages of Flood Fill : Flood fill algorithm is not advisable for filling larger polygons as quite larger stack is required for them . Also it is slow since it requires a recursive function call to be given to the getpixel ( ) command time and time again .


2 Answers

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:

alt text

like image 87
Gant Avatar answered Sep 19 '22 12:09

Gant


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;
}
like image 45
Phil Avatar answered Sep 17 '22 12:09

Phil