Aller au menu - Aller au contenu
Inscris-toi au e-camp "Héberge ton jeu Facebook sur Azure" de Microsoft vendredi 25 mai à 13h30 !

Algorithme de remplissage

Récursion très longue

Pour accéder à cette section
Connectez-vous !
connexion_rpx

Résolu Le problème de ce sujet a été résolu

Page 1 
Auteur Message
2 visiteurs sur ce sujet (2 anonymes)
Page 1 
Hors ligne engu # Posté le 27/01/2012 à 23:54:27
Avatar
Bonsoir à tous,
je vous expose rapidement mon problème :
j'utilise cet algorithme de remplissage d'une surface : Wikipédia : Algo de remplissage par diffusion
J'ai pas trouvé plus efficace, je pensais pouvoir m'en sortir avec ça, et pourtant.
Sur des images relativement petites, tout va bien (100*100 pixels).
Seulement, je travaille sur des images en réalité bien plus grande (minimum 540 * 720 pixels).
Alors mon programme est stoppé pour "boucle infinie" ou "récursion infinie", alors qu'elle est seulement très longue.
Comment résoudre ce problème ?
Merci d'avance,
Engu

P.S. : mon programme sera de toutes façons relativement lent, il fait du traitement vidéo image par image.
Publicité # Posté le 27/01/2012 à 23:54:27

Hors ligne zyd # Posté le 28/01/2012 à 00:11:01

Salut,

As-tu vu cette remarque ?

Citation : Wikipédia
La formulation recursive précédente, si elle possède l'avantage d'être intuitive par sa formulation, est souvent inemployée en pratique, en particulier dans des environnements d'exécution où la pile d'appel des fonctions est fortement contrainte ou réduite.


En clair, si tu as implémenté la première version présentée, c’est sûr que la pile d’appel grandira vite (et quand elle est pleine, tu as un joli message d’erreur et ton programme est interrompu).

Comment as-tu implémenté ton algorithme ? dans quel langage ? Dis-nous en davantage !

Sais-tu ce qu’est cette pile d’appel dont il est question ci-dessus ?

Bonne prog,
--
Zyd.
Hors ligne engu # Posté le 28/01/2012 à 00:20:17
Avatar
Oui je l'avais vue, sur un autre site mais l'idée est là.
J'ai bien implémenté cette version (mais en un peu modifié, car en fait je dois remplir des formes creuses, mais dans le creux on peut retrouver une forme à colorier, etc...).

Sinon, implémenté de manière très simple : on part d'un pixel, on diffuse. Puis on repart d'un pixel non traité, et on diffuse (en changeant de couleur ou pas). On répète jusqu'à ce que tous les pixels soient traités.
Je l'ai implémenté en C (avec la SDL pour tester sur une image, mais j'utiliserai surement une autre bibliothèque plus tard).
Si vous voulez, je posterai le code (dans la journée, je ne l'ai pas sous la main et il faut que j'y mette un minimum d'ordre).
Sinon la pile d'appel, je ne connais pas le détail mais le principe oui je comprends bien ce qu'il se passe.
Utilisez cette implémentation :
Secret (cliquez pour afficher)
Code : Autre
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

remplissage4(pixel, colcible, colrep)
 début
   Soit P une pile vide
   si couleur(pixel) \neq colcible alors sortir finsi
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     couleur(n) \leftarrow colrep
     si couleur(n nord) = colcible alors Empiler n nord sur P finsi
     si couleur(n sud)  = colcible alors Empiler n sud  sur P finsi
     si couleur(n est)  = colcible alors Empiler n est  sur P finsi
     si couleur(n ouest)= colcible alors Empiler n ouest sur P finsi
   fintantque
 fin

suffira-t-il à résoudre mon problème ? Si oui, je vais aller voir un peu plus comment implémenter des piles.
Hors ligne PatJ # Posté le 28/01/2012 à 00:29:09
Ça ne marchera jamais !
Avatar

Ville : Cachan
Pays : France métropolitaine
Études : ENS Cachan
Cette réponse a aidé l'auteur du sujet Cette réponse a aidé l'auteur du sujet
Voilà une petite optimisation mémoire, qui t'évitera bien des soucis:

Code : Autre
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

remplissage4(pixel, colcible, colrep)
 début
   Soit P une pile vide
   si couleur(pixel) \neq colcible alors sortir finsi
   couleur(n) \leftarrow colrep
   Empiler pixel sur P
   Tant que P non vide
   faire
     Dépiler n de P
     si couleur(n nord) = colcible alors 
      couleur(n nord) \leftarrow colrep
      Empiler n nord sur P
     finsi
     si couleur(n sud)  = colcible alors
      couleur(n sud) \leftarrow colrep
      Empiler n sud  sur P
     finsi
     si couleur(n est)  = colcible alors
      couleur(n est) \leftarrow colrep
      Empiler n est  sur P
     finsi
     si couleur(n ouest)= colcible alors
      couleur(n ouest) \leftarrow colrep
      Empiler n ouest sur P
     finsi
   fintantque
 fin
Message publié sous licence CC-BY-SA
 
Hors ligne engu # Posté le 28/01/2012 à 00:34:53
Avatar
Merci, j'essaye d'implémenter ça dès que possible (je risque d'ailleurs d'avoir moins de temps que prévu...) et je vous tiens au courant :)
Hors ligne mohman # Posté le 06/02/2012 à 22:44:43
Mon avatar :
Avatar

Études : SUPINFO Canada à Montréal
Un bon lien à ce sujet (méthode récursive et itérative) : http://lodev.org/cgtutor/floodfill.html
Image utilisateur
 

Retour au forum "Autres langages, outils et approches" ou à la liste des forums

Pour accéder à cette section
Connectez-vous !
connexion_rpx