Stack Overflow : (FloodFill) récursivité sur tableau de pixels

Version imprimable

Bonjour, merci de votre attention.

Voilà, je cherche a coder une fonction qui effectue une coloration par détection de contours. J'ai opté pour un tableau de pixel en 2 dimensions. Jusqu'ici pas de problème (conversion Image/int[][] puis vice versa et affichage ok) .
Le problème vien à la récurcivité. J'ai un Stack Overflow 9 fois sur 10 sur une image de 100x100 et a tous les coups si mon image est plus grande.

Donc voici l'erreur :

Exception in thread "main" java.lang.StackOverflowError
at paint.model.ImgPix.recursiveColorise(ImgPix.java:223)
at paint.model.ImgPix.recursiveColorise(ImgPix.java:223)
...
...

Voici la fonction récursive ainsi que celle qui l'amorce :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 /** * int[][] tab2Drgb : Tableau en 2 dimenssion de pixel int * int x, int y : Coordonnée de départ de la recursivité * Color c : Couleure de remplacement * @return : le nouveau tableau */ public static int[][] colorize(int[][] tab2Drgb, int x, int y, Color c){ //On récupère la couleure à remplacer final int OLDRGB = tab2Drgb[x][y]; //On convertis en int rgb la couleure de remplacement final int NEWRGB = c.getRGB(); ImgPix.recursiveColorise(tab2Drgb, x, y,OLDRGB, NEWRGB); return tab2Drgb; } public static void recursiveColorise(int[][] tab2Drgb, int x, int y, final int OLDRGB, final int NEWRGB){ //On applique la transformation de couleur au pixel courent tab2Drgb[x][y]= NEWRGB; //On récupere les dimenssion du tableau int wid = tab2Drgb.length; int hei = tab2Drgb[0].length; //Appel récurcif if(y+1 <wid && tab2Drgb[x][y+1]==OLDRGB && tab2Drgb[x][y+1]!=NEWRGB ){ ImgPix.recursiveColorise(tab2Drgb, x, y+1, OLDRGB,NEWRGB); } if (x+1 < hei && tab2Drgb[x+1][y]==OLDRGB && tab2Drgb[x+1][y]!=NEWRGB){ ImgPix.recursiveColorise(tab2Drgb, x+1, y,OLDRGB, NEWRGB); } if (0 < x && tab2Drgb[x-1][y]==OLDRGB && tab2Drgb[x-1][y]!=NEWRGB) { ImgPix.recursiveColorise(tab2Drgb, x-1, y, OLDRGB,NEWRGB); } if(0 < y && tab2Drgb[x][y-1]==OLDRGB && tab2Drgb[x][y-1]!=NEWRGB){ ImgPix.recursiveColorise(tab2Drgb , x, y-1,OLDRGB, NEWRGB); } }
Si je ne met que 3 appels de recusiveColorise (que je supprime un If) je n'ai pas d'Overflow.
Je suppose que ma récursivité est infinie, mais je ne trouve pas d'où ca viens. Je me casse les dents dessus depuis pas mal d'heure et je n'ai pas trouvé de réponse fonctionnelle sur mon amis Google.
Pourtant mon algorythme semble etre le même que celui proposé ici :
http://en.wikipedia.org/wiki/Flood_fill

Citation:

Flood-fill (node, target-color, replacement-color):
1. If the color of node is not equal to target-color, return.
2. If the color of node is equal to replacement-color, return.
3. Set the color of node to replacement-color.
4. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
Perform Flood-fill (one step to the east of node, target-color, replacement-color).
Perform Flood-fill (one step to the north of node, target-color, replacement-color).
Perform Flood-fill (one step to the south of node, target-color, replacement-color).
5. Return.

J'ai mis ma fonction en return int[][] et j'ai calqué la structure de ce précédent algorythme mais en vain, j'obtiens le même résultat.
J'ai déjà tout passé en dynamique et j'obtiens le même résultat.

Merci pour vos lumières.

Tu as permuté wid et hei dans tes tests
wid est la borne supérieure de l'indice x
hei est la borne supérieure de l'indice y

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
...
int wid = tab2Drgb.length;    // Largeur (Nombre maximum de x) 
int hei = tab2Drgb[0].length; // Hauteur (Nombre maximum de y) 
 
//Appel récurcif 
if (y+1 < wid  && tab2Drgb[x][y+1]==OLDRGB  &&  tab2Drgb[x][y+1]!=NEWRGB ){
		ImgPix.recursiveColorise(tab2Drgb, x, y+1, OLDRGB,NEWRGB);
}
if (x+1 < hei && tab2Drgb[x+1][y]==OLDRGB  &&  tab2Drgb[x+1][y]!=NEWRGB){
		ImgPix.recursiveColorise(tab2Drgb, x+1, y,OLDRGB, NEWRGB);
}
...

26/03/2009, 23h32
rebel64

Pour le stack overflow:
Une version itérative de cet algorithme existe...

voir ici http://de.wikipedia.org/wiki/Floodfill
27/03/2009, 01h14
tchize_

tu as oublié les étapes 1 et 2.

De plus, ce floodfill récursif, peut amener, dans le pire des cas, width < height récursions. C'est beaucoup trop. Pour 100x100, t'arrive à 10.000 récursion, la stack est pas assez grande pour stocker tous ces appels. T'as pas une récursion infinie, juste une récursion trop profonde.

Merci beaucoup pour vos réponses.

Non je mettait bien les conditions et les return statement comme il est indiqué dans l'algo.

Petite Erreur de ma part pour les wid et hei, mes images étant de x par x je n'ai pas eu de OutOfBound. Erreur rectifiée, merci.

Je pense que ma récursion est trop profonde en effet. C'est la première fois que ça m'arrive... Il y a une première fois à tout.

Donc je suis obliger de me tourner vers l'algo itératif :mouarf: , qui marche à merveille.

Merci

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
 
	/** 
         * @param tab2Drgb Tableau de pixel en 2 Dimension
         * @param x Coordonnées x du départ du FLoodFill
         * @param y     Coordonnées y du départ du FLoodFill
         * @param NEWRGB Couleur de remplacement
         * @return int[][] - le nouveau tableau de pixel
         */
	public static int[][] iterFloodFill(int[][] tab2Drgb,int x, int y, final int NEWRGB){
 
		final int OLDRGB = tab2Drgb[x][y];
		//Arraylist destiné à stocker les coordonnées des pixels à traiter
		ArrayList<Point> pile = new ArrayList<Point>();
 
			//On récupere les dimenssion du tableau pour nos futurs tests
			int wid = tab2Drgb.length;
			int hei = tab2Drgb[0].length;
 
			//On insert les coordonées de départ dans la pile de traitement
			pile.add(new Point(x,y));
 
			//point destiné a stocker les coordonées courentes
			Point pt;
 
			while(pile.size()>0){
 
				//On retire les coordonnées du pixel que l'on traite
				pt = pile.remove(0); 
				x = pt.x;
				y = pt.y;
 
				//Si le pixel courent est bien de la couleur cible
				if(tab2Drgb[x][y]==OLDRGB){
 
					//On applique le changement de couleur aux coordonnées courentes
					tab2Drgb[x][y]=NEWRGB;
 
					/*Puis on teste les pixels nord sud est ouest,
					 * si il faut y appliquer la nouvelle couleur alors on empile les
					 * coordonnées du pixel
					 */
					if(x+1 < wid && tab2Drgb[x+1][y]==OLDRGB) pile.add(new Point(x+1,y)) ;
					if(y+1 < hei && tab2Drgb[x][y+1]==OLDRGB) pile.add(new Point(x,y+1)) ; 
					if(x>0 && tab2Drgb[x-1][y]==OLDRGB) pile.add(new Point(x-1,y));
					if(y>0 && tab2Drgb[x][y-1] ==OLDRGB) pile.add(new Point(x,y-1));
				}
			}
 
		return tab2Drgb;
	}

Wouuu les Stacks Overflow!! :aie: