IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Stack Overflow en réccursif


Sujet :

C++

  1. #1
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut Stack Overflow en réccursif
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  2. #2
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    Ç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...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  3. #3
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation Envoyé par Ange_blond Voir le message
    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:


  4. #4
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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:

    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.

  5. #5
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Admettons que tu as la situation suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  6. #6
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut
    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

  7. #7
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation Envoyé par Ange_blond Voir le message
    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

    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).

  8. #8
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut
    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.

  9. #9
    Expert confirmé

    Homme Profil pro
    Ingénieur systèmes et réseaux
    Inscrit en
    Février 2007
    Messages
    4 253
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur systèmes et réseaux
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Février 2007
    Messages : 4 253
    Billets dans le blog
    3
    Par défaut
    Une pile c'est un simple vecteur... pas d'affolement !

    un truc genre (pseudocode):
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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.

  10. #10
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut
    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

  11. #11
    Membre émérite
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Par défaut
    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.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [GNU-Prolog][Mémoire] Local stack overflow
    Par Maxoo dans le forum Prolog
    Réponses: 15
    Dernier message: 04/06/2008, 22h15
  2. stack overflow: question insoluble
    Par coyotte507 dans le forum SDL
    Réponses: 3
    Dernier message: 19/12/2006, 17h50
  3. Stack OverFlow
    Par Goundy dans le forum Langage
    Réponses: 2
    Dernier message: 24/12/2005, 21h35
  4. Problème de stack overflow
    Par heider dans le forum Langage
    Réponses: 13
    Dernier message: 22/09/2005, 19h50
  5. Stack overflow
    Par portu dans le forum Langage
    Réponses: 3
    Dernier message: 26/11/2003, 15h16

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo