Relleno de inundación usando una stack

Estoy usando el algoritmo de relleno de inundación recursivo en Java para llenar algunas áreas de una imagen. Con imágenes muy pequeñas funciona bien, pero cuando la imagen se hace más grande, la JVM me da un error de acumulación de flujo.

Esa es la razón por la cual tengo que volver a implementar el método usando un Flood Fill con mi propia stack. (He leído que es la mejor manera de hacerlo en este tipo de casos)

¿Alguien puede explicarme cómo codificarlo? (Si no tiene el código a mano, con el pseudo-código del algoritmo estará bien)

He leído mucho en Internet, pero no lo he entendido muy bien.

EDITAR: agregué mi código recursivo

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

¡Gracias!

    Puede usar Cola para eliminar la recursión del algoritmo floodfill. Aquí hay algunas ideas básicas:

    1. Tener una forma de marcar los puntos visitados
    2. Al principio, ponga en cola el punto de inicio.
    3. Mientras la cola no está vacía, continúe eliminando su elemento. Y con cada elemento
      1. Llene su color y marque el punto recién dequeado como visitado
      2. Encola puntos adyacentes no visitados que tengan el mismo color

    El siguiente es mi código Java para resolver un problema similar pero diferente de detección de blobs . Espero que puedan obtener algunas ideas de esto y puedan adaptarlo al problema. Sin embargo, el código no está bien factorizado.

     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 queue = new LinkedList(); 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(); } } } 

    Entrada de prueba:

    texto alternativo

    aquí está mi base de implementación en las informaciones de esta página y otras recostackdas en la web (probadas y en funcionamiento)

    que te diviertas 😉

     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 queue = new LinkedList(); 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; } 

    Debería devolver la última instrucción floodFill, convirtiéndola en una llamada final. Esto te ahorrará espacio en la stack.

    Un punto importante en el llenado de inundación es si está procesando la profundidad de los puntos primero o ancho primero. La profundidad primero es la solución original que estaba buscando usando una stack; la amplitud primero son los algoritmos que se muestran a continuación usando una cola para almacenar puntos. La diferencia es considerable cuando se rellenan espacios convexos grandes. Un primer método de amplitud almacena en un área perfectamente convexa aproximadamente el borde del círculo (o borde de relleno). Si utiliza un primer método de profundidad, en el peor de los casos puede almacenar cada píxel en el área conxex, lo que significa que en el peor de los casos una inundación de imagen de 1000×1000 puede requerir 1000000 de marcos de stack.