Remplissage à l'aide d'une pile

Je suis en utilisant la récursivité remplissage de l'algorithme en Java afin de combler certaines zones d'une image.
Avec de très petites images, il fonctionne très bien, mais quand de l'image devient plus grand, la JVM me donne un tas Sur le Flux d'Erreur.

C'est la raison pour laquelle j'ai réimplémenter la méthode à l'aide d'un pot de peinture avec mon propre pile. (J'ai lu que c'est la meilleure façon de le faire dans ce genre de cas)

Quelqu'un peut-il m'expliquer comment code? (si vous n'avez pas le code à la main, avec le pseudo-code de l'algorithme sera très bien)

J'ai lu beaucoup de choses sur Internet mais je ne l'ai pas compris très bien.

EDIT: j'ai ajouté mon code récursif

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;

}

Merci!

Wikipédia: Inondation algorithme de remplissage
Si vous deviez afficher votre code existant (ou un résumé de celui-ci), quelqu'un pourrait être en mesure de vous dire comment l'écrire d'une manière qui n'est pas récursive, si c'est ce que vous êtes après.
Je vous conseille de choisir l'un de la file d'attente basé sur des algorithmes qui y sont présentées, elles sont plus faciles à mettre en œuvre que d'une pile à base de solution, à mon avis.
Merci pour la réponse, j'ai essayé de mettre en œuvre avec l'explication de Wikipedia, mais je ne sais pas comment. C'est la raison pour laquelle je fais ici une question. Si quelqu'un pourrait-il m'expliquer avec d'autres mots, je serai très reconnaissant.

OriginalL'auteur dafero | 2010-05-06

Vous pouvez utiliser la Queue pour retirer la récursivité de remplissage de l'algorithme. Voici quelques idées de base:

Avoir un moyen de marquer les points de visite
Au début de la file d'attente au point de départ.
Alors que la file d'attente n'est pas vide, continuent la file d'attente de son élément. Et avec chaque élément
1. Remplir sa couleur et sa marque just-dequeued point que la visite
2. Mettre en file d'attente non visités points adjacents qui a la même couleur

Le ci-dessous mon code Java pour résoudre similaire, mais différent problème de blob de détection. J'espère que vous pouvez obtenir des idées à partir de cela et peut s'adapter, c'est le problème. Le code n'est pas bien compte.

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

Entrée de Test:

Remplissage à l'aide d'une pile

Mmmm je vois...mais comment puis-je adapter votre code? J'ai besoin de la peinture verte certains domaines, par exemple: toutes les zones noires de l'image. Merci pour tout!
Dans l'exemple de code, ce que fait le programme est l'incrémentation de la valeur de pixelCount variable. Peut-être vous voulez setRGB à ce point à la place? Aussi, l'analyse de l'ensemble de la zone de l'image pour chaque blob. Vous pouvez les remplir qu'une seule goutte, de commencer à le remplir à certain point.
Ouais! - Je l'obtenir! Sans votre aide ne serait pas possible!! Juste que j'ai changer la ligne "pixelCount++" par "img.setRGB(p.x, p.y, de la Couleur.VERT.getRGB());" et c'est tout! Je suis très reconnaissante!! Merci beaucoup!
Magnifique, je ne sais pas comment je n'avais pas pensé à cette solution. Fonctionné sans problème dans mon code!

OriginalL'auteur Gant

voici ma mise en œuvre de la base sur les infos de cette page et les autres se sont rassemblés sur le web (testé et de travail)

avoir du plaisir 😉

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

Travaillé comme un charme.Je vous remercie beaucoup.

OriginalL'auteur fdsfdsfdsfds

1

Vous devez retourner le dernier de remplir la déclaration, en la transformant en une queue d'appel. Cela vous fera économiser de l'espace de pile.

La queue de la récursivité peut toujours être convertis en un processus itératif de format. Cela permettrait d'économiser encore plus d'espace de pile.
Merci à vous deux!

OriginalL'auteur Puppy
1

Un point important dans le pot de peinture est si vous traitez des points de parcours en profondeur d'abord de l'étendue de la première. Parcours en profondeur d'abord est la solution originale que vous cherchez à l'aide d'une pile, de la largeur de la première sont des algorithmes indiqué ci-dessous à l'aide d'une file d'attente pour stocker point. La différence est importante lors du remplissage dans de grands espaces convexes. D'une ampleur première méthode stocke sur un parfaitement convexe zone à peu près le cercle de bord (ou de remplissage de pointe). Si vous utilisez un parcours en profondeur d'abord la méthode peut dans le pire des cas stocker chaque pixel de l'conxex de la zone, ce qui signifie que dans le pire des cas, un 1000x1000 image d'inondation rempli peut exiger 1000000 de la pile d'images.

À préciser (cmiiw) d'une pile à base de structure de données (filo file d'attente) serait en largeur d'abord, le remplissage à partir d'un bord convexe vers l'intérieur, wheras de pile, la récursivité serait profondeur d'abord. Un fifo file d'attente, par comparaison, serait de travailler à partir de l'origine vers l'extérieur, en chaque point est traité dans l'ordre présenté. Fifo files d'attente ont tendance à avoir plus de surcharge, si vous ne pouvez pas cultiver un tampon en anneau w/o la copie de

OriginalL'auteur RolfS

Vous devez vous connecter pour publier un commentaire.