Подтвердить что ты не робот

Наполнение потоком с использованием стека

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

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

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

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

EDIT: я добавил свой рекурсивный код

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;

}

Спасибо!

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Ниже приведен код 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();
        }

    }

}

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

alt text

Ответ 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;
}

Ответ 3

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

Ответ 4

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