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

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

Вот почему я должен переопределить метод, используя 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;

}

Спасибо!

12 голосов | спросил dafero 6 Maypm10 2010, 21:43:43

4 ответа


0

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

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

    }

}

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

альтернативный текст

ответил Gant 6 Maypm10 2010, 22:05:27
0

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

веселись; -)

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;
}
ответил fdsfdsfdsfds 4 52016vEurope/Moscow11bEurope/MoscowFri, 04 Nov 2016 14:48:23 +0300 2016, 14:48:23
0

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

ответил Puppy 6 Maypm10 2010, 22:08:15
0

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

ответил RolfS 26 J000000Saturday14 2014, 02:34:59

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132