Stack Overflow en réccursif

Version imprimable

Bonjour,

Voilà je travaille actuellement sur un algo de traitement de l'image. Le but étant de reconnaitre les formes sur une image binarisée (noir et blanc). Mon algo se base sur un théorie que j'ai pensée à force de m'énerver sur les algos classiques qui ne marchent pas ^^

Je parcours mon image en long et en large, et lorsque je trouve un pixel interessant ( en noir) je lance ma boucle réccursive qui va chercher tous les voisins à partir de ce pixel noir, et les voisins des voisins... etc...

Apres avoir été confronté à une tonne de stack overflow... j'ai compris que d'augmenter la taille de la pile pourrait suffir à débugguer mon programme. En effet, le code fonctionne tres bien, cependant, j'ai besoin des parametres de pile suivants :

taille de la réserve de pile : 4000000
taille de validation de pile : 10000

(soit : /STACK:4000000,10000 )

Est ce normal d'en arriver là pour faire tourner un algo réccursif qui ne me parrait pas si "bourrin" que ça ?

PS : je tourne sous Visual C++ express

Voilà le code utilisé :
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 ImagePGM pgm_bin("test.pgm"); Binaire bin2(200); //seuil de binarisation S2D<unsigned char> s_bin = bin2(pgm_bin.GetData()); pgm_bin.Save("test_binarise.pgm"); S2D<int> C(pgm_bin.Width(),pgm_bin.Height()); C.set(0); int classe = 1; for(int i=1 ; i<pgm_bin.Width(); i++) for(int j=1 ; j<pgm_bin.Height(); j++) { //Si il dépasse le seuil on le récupere (et si il n'est pas déjà classé) if((s_bin[j][i] > 200) && (C[j][i] == 0)) { select_classe(&s_bin, &C, i, j, classe, 200); classe++; cout << "classe " << classe << endl; //system("pause"); } }
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 /** Fonction récursive de selection d'une classe par propagation **/ void select_classe( S2D<unsigned char>* s_bin, S2D<int>* C, int w, int h, int classe, int seuil) { /* 1 | 2 | 3 4 | X | 5 6 | 7 | 8 */ //cout << "Appel en ["<<w<<"]["<<h<<"]"<<endl; //cas d'arret if(((*s_bin)[h][w] > seuil) && ((*C)[h][w] == 0)) { //on marque le courant. (*C)[h][w] = classe; //cout<<"On marque C["<<h<<"]["<<w<<"] avec la classe "<<classe<<endl; //system("pause"); /* //les voisins sont > seuil ou encore non classés if(((*s_bin)[h-1][w-1] > seuil) && ((*C)[h-1][w-1] == 0)) //1 select_classe(s_bin, C, w-1, h-1, classe, seuil); */ if(((*s_bin)[h][w-1] > seuil) && ((*C)[h][w-1] == 0)) //2 select_classe(s_bin, C, w-1, h, classe, seuil); /* if(((*s_bin)[h+1][w-1] > seuil) && ((*C)[h+1][w-1] == 0)) //3 select_classe(s_bin, C, w-1, h+1, classe, seuil); */ if(((*s_bin)[h-1][w] > seuil) && ((*C)[h-1][w] == 0)) //4 select_classe(s_bin, C, w, h-1, classe, seuil); if(((*s_bin)[h+1][w] > seuil) && ((*C)[h+1][w] == 0)) //5 select_classe(s_bin, C, w, h+1, classe, seuil); /* if(((*s_bin)[h-1][w+1] > seuil) && ((*C)[h-1][w+1] == 0)) //6 select_classe(s_bin, C, w+1, h-1, classe, seuil); */ if(((*s_bin)[h][w+1] > seuil) && ((*C)[h][w+1] == 0)) //7 select_classe(s_bin, C, w+1, h, classe, seuil); /* if(((*s_bin)[h+1][w+1] > seuil) && ((*C)[h+1][w+1] == 0)) //8 select_classe(s_bin, C, w+1, h+1, classe, seuil); */ } return; }
Merci de vos conseils.

04/11/2007, 15h42
Médinoc

Ça me parait pas très normal en effet.
Vu qu'il n'y a aucune grosse variable locale dans ton code, il faut vraiment que ta fonction descende à un niveau impressionnant pour que ça plante comme ça...
04/11/2007, 17h37
Jean-Marc.Bourguet
Citation:

Envoyé par Ange_blond

Est ce normal d'en arriver là pour faire tourner un algo réccursif qui ne me parrait pas si "bourrin" que ça ?

Il me semble plutôt bourrin dans son utilisation de la récursivité. Dans le pire cas, tu as une profondeur d'appel récursive égale au nombre de points de ta classe. Plutôt que de la récursivité, je placerais les points encore à examiner dans une FIFO (une pile revient à ton algo récursif, en pire); une structure associative peut avoir des avantages.

Tu peux essayer aussi d'être intelligent et de ne pas placer dans la FIFO des choses redondantes (par exemple le point 3 si tu as déjà mis le point 2:
Code:

1 2 1234 5678
04/11/2007, 21h35
Ange_blond
Citation:
Envoyé par Jean-Marc.Bourguet

Tu peux essayer aussi d'être intelligent et de ne pas placer dans la FIFO des choses redondantes (par exemple le point 3 si tu as déjà mis le point 2:

Code:

1 2 1234 5678
En fait, d'apres l'algo, les choses se présentent ainsi :

1 2 3
4 X 5
6 7 8

Avec X étant le pixel en cours d'analyse. Si le voisin 2 est selectionné comme étant correct (ou non) le voisin 3 doit etre traité au meme niveau. le test au début de la fonction récursive permet de ne pas traiter le voisin 3 si on l'a déjà traité dans les appels réccursifs du voisinage de 2. Dans tous les cas, chaque pixel qui sera traité par la fonction réccursive sera utilisé par 7 autres appels. C'est tres fortement redondant, mais normalement grace aux tests ça devrai aller vite et bien et je suis surpris que ça s'enfonce si loin dans la pile.

Je vais essayer mettre des tests supplémentaires avant chaque appel réccursif pour éviter d'empiler des appels qui vont retourner du vide, mais je ne sais pas si ça va vraiment alleger la chose.

Dans le dernier des cas je retournerai en itératif, mais je l'ai tenté et j'ai échoué lamentablement à plusieurs reprises...

Merci, je vous tiens au courant.
04/11/2007, 21h44
Jean-Marc.Bourguet
Admettons que tu as la situation suivante:
Code:

1 2 3 4 5 6 7 ------- -ABCDE- -FGHIJ- -KLMNO- -PQRST- -UVWXY- -------
Et que tu partes de C. Tu vas visiter les pixels dans l'ordre: CBAFKPUVQLGHMRWXSNIDEJOTY avec à chaque fois un appel récursif. Pas sûr que ce soit l'idéal.
06/11/2007, 13h27
Ange_blond

je te rapelle que l'ago fonctionne dans l'ordre : haut - droite - bas - gauche

Donc sur ton exemple, je crois plutôt que ça donnerait :

CDJEOTYXS...

(obtenu en déroulant à la main sur un brouillon les appels)

Mais la question n'est pas là, car je ne suis pas sur que de blinder les tests avant la récursivité réduise le nombre d'appels... mais ça se tente :?
06/11/2007, 13h33
Jean-Marc.Bourguet

Citation:

Envoyé par Ange_blond

je te rapelle que l'ago fonctionne dans l'ordre : haut - droite - bas - gauche

Donc sur ton exemple, je crois plutôt que ça donnerait :

CDJEOTYXS...

(obtenu en déroulant à la main sur un brouillon les appels)

Pas d'importance. Le principe est le meme

Citation:

Mais la question n'est pas là, car je ne suis pas sur que de blinder les tests avant la récursivité réduise le nombre d'appels... mais ça se tente :?

Ca depend comment tu fais tes tests. A mon avis, c'est possible de s'en sortir avec de la recursivite mais c'est plus complique qu'en manipulant une structure de donnee explicitement, meme si celle-ci est un pile (comme je l'ai deja ecrit, il me semble qu'une file aura de meilleurs resultats, mais c'est a confirmer).
06/11/2007, 23h50
Ange_blond

Je ne me sens pas assez à l'aise pour me tenter une pile moi même... et je ne vois pas non plus comment augmenter les tests pour éviter de saturer la pile...

Pour le moment je vais changer de lib de traitement d'image pour le projet, alors la priorité n'est plus vraiment là, sachant qu'en plus ça fonctionne (techniquement) donc bon...

En tout cas merci du coup de main, je ne clos pas le topic tout de suite, car si la lib se prend bien en main, je ferai surement un retour pour poser ou non un nouvel algo.

Merci.

Une pile c'est un simple vecteur... pas d'affolement !

un truc genre (pseudocode):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
vector<point> pile;
// on initialise la pile avec les éléments à traiter initiaux
for (int x = 0; x < width(); ++x) {
   for (int y = 0; y < height; ++y) {
       point pt(x,y);
       if (condition(pt))
           pile.addLast(pt);
   }
}
// ensuite on traite....
while (pile.size()>0) {
    point pt = pile.getLast();
    pile.removeLast();
    // traitement du point "pt"
    // un nouveau point à ajouter ?
    point nouveauPt;
    if (!pile.contains(nouveauPt))
        pile.addLast(nouveauPt);
}

C'est par ce genre de code qu'on fait un algorithme A* par exemple.

07/11/2007, 11h29
Ange_blond

Oui en effet le A* à besoin de deux piles, mais disons que là à la base je pensais que le récursif se suffirait à lui même... et si je fait une pile, je en connais pas sa dimension, alors faut gérer ça dynamiquement... bref je pensais pas que ça irait chercher si loin pour une chose si... basique.
merci
12/11/2007, 14h34
Ange_blond

Bon, de toute évidence je ne trouverai pas mieux en terme de rapidité et de simplicité, donc tant pis pour la pile...

Merci à tous pour votre aide et vos conseils.