使用堆栈填充洪水 [英] Flood fill using a stack

问题描述

我在Java中使用递归Flood填充算法来填充图像的某些区域。
对于非常小的图像，它工作正常，但当de image变大时，JVM会给我一个Stack Over Flow Error。

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.

这就是为什么我必须使用我自己的堆栈使用Flood Fill重新实现该方法。 （我认为在这种情况下这是最好的方法）

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.

编辑：我添加了我的递归代码

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;

}

谢谢！

推荐答案

您可以使用Queue从floodfill算法中删除递归。以下是一些基本想法：

You can use Queue to remove recursion from floodfill algorithm. Here are some basic ideas:

1. 有办法标记访问点


2. 一开始，排队起点。


3. 当队列不为空时，继续将其元素出列。并使用每个元素
   
   

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. 填充其颜色并标记刚出列的点作为已访问


2. 将未访问的相邻点排入队列相同的颜色

以下是解决类似但不同问题的Java代码 blob detection 。我希望你能从中得到一些想法，并能够解决问题。但代码并没有很好的考虑。

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

    }

}

测试输入：

这篇关于使用堆栈填充洪水的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！