使用堆栈进行洪水填充

我在Java中使用recursionFlood填充algorithm来填充图像的某些区域。 对于非常小的图像，它可以正常工作，但是当图像变大时，JVM会给我一个堆栈溢出错误。

这就是为什么我必须用自己的堆栈使用洪水填充来重新实现该方法的原因。 （我读过这是在这种情况下做到这一点的最好方法）

任何人都可以解释我如何编码？ （如果你手边没有代码，那么algorithm的伪代码就可以）

我在互联网上阅读了很多，但是我还没有很好的理解。

编辑：我添加了我的recursion代码 

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; }

谢谢！

您可以使用Queue从floodfillalgorithm中删除recursion。 这里有一些基本的想法：

  1. 有一个方法来标记访问点
  2. 开始时，排队起点。
  3. 队列不为空时，继续出列其元素。 并与每个元素
    1. 填写它的颜色，并将刚刚出列的点标记为已访问
    2. 排队未访问的具有相同颜色的相邻点

以下是我的Java代码来解决类似但不同的斑点检测问题。 我希望你能从中得到一些想法，并能适应这个问题。 代码虽然不是很好的考虑因素。 

 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 ((px >= 0) && (px < bimg.getWidth() && (py >= 0) && (py < bimg .getHeight()))) { if (!painted[py][px] && isBlack(bimg, px, py)) { painted[py][px] = true; pixelCount++; queue.add(new Point(px + 1, py)); queue.add(new Point(px - 1, py)); queue.add(new Point(px, py + 1)); queue.add(new Point(px, py - 1)); } } } System.out.println("Blob detected : " + pixelCount + " pixels"); } } } } catch (IOException ex) { ex.printStackTrace(); } } }

testinginput：

替代文字

这里是我的实施基础从这个网页的信息和其他人收集在networking上（testing和工作）

玩的开心 ;-） 

 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,px,py, srcColor, color.getRGB())) { queue.add(new Point(px,py - 1)); queue.add(new Point(px,py + 1)); queue.add(new Point(px - 1,py)); queue.add(new Point(px + 1,py)); } } } 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; }

你应该返回最后的floodFill语句，把它变成一个尾巴呼叫。 这将节省您的堆栈空间。

填补洪水的一个重要的一点是，如果你先处理点深度或宽度优先。 深度首先是您使用堆栈的原始解决scheme，广度优先是下面显示的algorithm使用队列来存储点。 填充大凸面空间时，差别很大。 宽度的第一种方法大致存储在完美的凸面区域上的圆形边缘（或填充边缘）。 如果使用深度优先方法，则最坏情况下可能会在conxex区域中存储每个像素，这意味着在最坏的情况下，1000×1000的图像填充可能需要1000000个堆栈帧。

Interesting Posts