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!
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.
The traditional flood-fill algorithm takes three parameters: a start node, a target color, and a replacement 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.
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 .
You can use Queue to remove recursion from floodfill algorithm. Here are some basic ideas:
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:
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With