Заполнение флудом с использованием стека

Question

Я использую алгоритм рекурсивного заполнения Flood в Java, чтобы заполнить некоторые области изображения. С очень маленькими изображениями это работает нормально, но когда изображение становится больше, JVM выдает ошибку Stack Over Flow.

Вот почему я должен переопределить метод, используя Flood Fill со своим собственным стеком. (Я читал, что это лучший способ сделать это в подобных случаях)

Может кто-нибудь объяснить мне, как его кодировать? (если у вас нет кода под рукой, с псевдокодом алгоритма все будет в порядке)

Я много читал в Интернете, но не очень хорошо понял.

РЕДАКТИРОВАТЬ: я добавил свой рекурсивный код

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;

}

Спасибо!

Answer 1

Вы можете использовать Очередь для удаления рекурсии из алгоритма заливки. Вот несколько основных идей:

1. Есть способ отметить посещенные точки
2. В начале поставьте в очередь начальную точку.
3. Пока очередь не пуста, продолжайте убирать из очереди ее элемент. И с каждым элементом
   1. Заполните его цветом и отметьте только что снятую точку как посещенную
   2. ставить в очередь не посещенные смежные точки, имеющие одинаковый цвет

Ниже приведен мой Java-код для решения аналогичной, но другой проблемы обнаружения BLOB-объектов . Я надеюсь, что вы можете получить некоторые идеи из этого и адаптировать его к проблеме. Код не очень хорошо продуман.

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

    }

}

Тестовый ввод:

Answer 2

вот моя база реализации на основе информации с этой страницы и других, собранных в сети (проверено и работает)

веселись; -)

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

Answer 3

Важным моментом при заполнении паводка является то, обрабатываете ли вы сначала точки глубины или ширины. Сначала глубина - это исходное решение, которое вы рассматривали с использованием стека, а ширина - алгоритмы, показанные ниже с использованием очереди для сохранения точки. Разница существенна при заполнении больших выпуклых пространств. Метод ширины вначале сохраняет идеально выпуклую область, примерно равную краю круга (или краю заливки). Если вы используете метод глубины сначала, вы можете в худшем случае сохранить каждый пиксель в области conxex, это означает, что в худшем случае заполненный заливкой изображения размером 1000x1000 может потребовать 1000000 кадров стека.

Answer 4

Вы должны вернуть последний оператор floodFill, превратив его в хвостовой вызов. Это сэкономит вам место в стеке.