Recursivite ...

Signaler
Messages postés
252
Date d'inscription
mercredi 25 octobre 2000
Statut
Membre
Dernière intervention
1 mai 2005
-
Messages postés
455
Date d'inscription
samedi 26 octobre 2002
Statut
Membre
Dernière intervention
6 avril 2004
-
Salut a tous,

J'ai un gros probleme, et je comprend pas pourquoi ...
Je suis entrain de m'arracher les cheveux depuis le debut de l'aprem
et la, ca va plus du tout ...

Alors voila : je souhaite "labeliser" une image binaire (2 couleurs : blanc=255, noir=0).
Labeliser consiste a attribuer une couleur a chaque ensemble de pixels blancs. Pour le
faire, je me suis dit, genial, vive le recursif. et il est entrain de me rendre dingue ...

Pour stocker les images d'entree et de sortie, j'utilise une classe CImage. Elle contient les
dimensions de l'image, et un tableau permettant de stocker les valeurs lues dans le fichier.

Voici le main:

int main(int argc, char *argv[])
{
char nom[255];
int i, j;

//Construction des objets image nécéssaires
CImage image(atoi(argv[1]),atoi(argv[2]),0,0);
//nb_lignes,nb_colonnes en parametres ...
CImage inter(atoi(argv[1]),atoi(argv[2]),0,0);
CImage label(atoi(argv[1]),atoi(argv[2]),0,0);

//Mise à jour des noms
strcpy(nom,argv[3]);
image.MAJnom_image(nom);

strcpy(nom,argv[4]);
label.MAJnom_image(nom);

image.Ouverture();
image.Lecture();
image.Fermeture();

for (i=0;i<label.nbL;i++)
for (j=0;j<label.nbC;j++)
label.image_memoire[i][j] = 0;

inter.Labelisation(image,label);

label.Ecriture();
label.Fermeture();

return 0;
}

Voila les fonctions utilisees:

void CImage::Labelisation(CImage image, CImage label)
{
int i, j, val_label = 1;

for (i=0;i<nbL;i++)
for (j=0;j<nbC;j++)
{
if (image.image_memoire[i][j] == 255)
{
label.image_memoire[i][j] = val_label;
Label_Voisi(image,label,i,j);
val_label++;
}
}
}

void CImage::Label_Voisi(CImage image, CImage label, int i, int j)
{
int k, l;

for (k=i-1;k<=i+1;k++)
for (l=j-1;l<=j+1;l++)
{
if (k >= 0 && k < image.nbL && l >= 0 && l < image.nbC && (k != i && l != j))
{
if (image.image_memoire[k][l] == 255 && label.image_memoire[k][l] == 0)
{
label.image_memoire[k][l] == label.image_memoire[i][j];
Label_Voisi(image,label,i,j);
}
}
}
}

L'idee : parcourir l'image de depart. Si le pixel est noir, on ne fait rien.
Si le pixel est blanc, on lui affecte une valeur de label (incrementee des que
l'on change de zone), puis on regarde tous les pixels autour et on recommence ...
d'où l'idee du recursif ...
Ca devrait marcher!!!Toutes les conditions sont posees ... mais ca marche pas.
VC++ me met un Stack Overflow au debugage (apparement au bout de 38 iterations de
la fonction Label_Voisi ??!!??!!??!!).

Si vous avez une idee, je suis hyper preneur.
Merci d'avance (c un peu urgent)
ioupix@yahoo.fr pour les precisions

4 réponses

Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
25
Salut,
Stack Overflow est le danger qui menace toute func recursive. On a fait des bouquins entiers sur la maniere de transformer de recursif vers iteratif. Je pense que dans ton cas cela va te faire un tres bon exercice.
Quand tu fais une func recursive, pose toi toujours la question de savoir combien d'octets tu mets sur la pile a chaque tour(les params) et combien d'appels recursifs la pile pourra supporter (sizeParams * tours).
ciao...
Messages postés
252
Date d'inscription
mercredi 25 octobre 2000
Statut
Membre
Dernière intervention
1 mai 2005

Et comment sait-on combien d'appels recursif la pile peut supporter?
Messages postés
455
Date d'inscription
samedi 26 octobre 2002
Statut
Membre
Dernière intervention
6 avril 2004
8
bonsoir,
je ne juge pas la de perspicacité (ou non) de la récursion ici.
Ce qui me surprend est de deviner que ta classe CImage possède un tableau [nbL][nbC] => volumineux et de voir que les passages dans les fonctions se font PAR VALEUR , ce qui est très couteux en pile.

Attention encore !
D'autre part, la classe possède donc un (double) pointeur et elle doit nécessairement être canonique, c'est à dire avoir un constructeur de copie non trivial qui s'occupe de dupliquer proprement le tableau (et peut-être un opérateur= si tu veux permetre l'affectation) et non pas simplement une copie du pointeur qui ne manque pas de provoquer un trap à la libération mémoire (au delete[]...).
encore une remarque sur l'avant dernière ligne de code, je crois apercevoir un au lieu d'un
Messages postés
455
Date d'inscription
samedi 26 octobre 2002
Statut
Membre
Dernière intervention
6 avril 2004
8
oui
par défaut la pile (Stack) est taillée à 1 Mo
ceci est paramètrable au niveau du linkeur
Project/Settings/Link/Category Output => reserve