[C] Recursivité : limite ?

Recherche :

Dernière réponse
Sujet : [C] Recursivité : limite ?
rufo	ça y est, j'ai implémenté l'algo, et ça marche nickel :) ça fait, le même boulot qu'en récursif, mais en plus rapide (2 fois moins de temps!) et je suis plus limité en taille d'images comme avant (7575 :() Il n'en reste pas moins que l'algo principal, lui, reste tout de même assez long (15 mins pour une image en 100100)...

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

rufo

ça y est, j'ai implémenté l'algo, et ça marche nickel :) ça fait, le même boulot qu'en récursif, mais en plus rapide (2 fois moins de temps!) et je suis plus limité en taille d'images comme avant (75*75 :()
Il n'en reste pas moins que l'algo principal, lui, reste tout de même assez long (15 mins pour une image en 100*100)...

rufo

Mara's dad a écrit a écrit :

Rufo,

Si j'ai bien compris en quoi mon algo n'est pas bon, c'est que tu utilise le même seuil pour tester tous le pixel. Je pensait que chaque pixel avait son propre seuil !

Sinon, ton algo à l'air plus optimisé, ce qui ne m'étonne pas !
J'avis pas cherché l'optimisation, juste à ne pas être récursif.

Si l'idée te conviens, et bien, çà me va !

Celà dit, y'a surement moyen d'optimiser encore. Je pense à essayer de trouver une manière de ne pas tester plusieurs fois les mêmes pixels. Mais j'ai peur que ce ne possible qu'avec un algo beaucoup plus compliqué.

Je cherche, mais juste par plaisir !

Au fait, çà sert à quoi ton truc ?

ce petit algorithme est une croissance de région. A partir d'un pixel, on veut trouver tous les pixels voisins qui sont > à tm, un niveau de gris. Mais cet algo fait parti d'un algo beaucoup plus compliquer qui permet, en théorie (et j'ai prouvé que c'était pas toujours vrai, dans certaines conditions), de détecter automatiquement les contours d'une image en niveaux de gris, sans avoir à régler un seul paramètre. Mais là, je peux pas t'en dire plus sur le principe de cet algo car il fait l'objet de recherches (pas encore publié). Des méthodes plus classiques dépendent d'un seuil tm (là encore) mais que l'utilisateur doit saisir. Avec cet algo, c'est pas la peine...
Mais merci beaucoup pour ton aide en tout cas :) A cause de cette récurcivité, on pouvait tester que sur des images de 75*75 pixels (avec mon TB800, l'algo met 10 mins avant de sortir l'image traitée, on l'affiche via IrfanView, comme ça on a pas à programmer une interface pour afficher des images, astuce). Maintenant, on n'est plus limité, seulement faut pas être pressé. Lundi j'ai soutenance. 20 mins d'oral et 10 mins de démo. Vu qu'on a que des P166 et P200 à mon école, y'aura pas de démo lol...:)

Mara's dad

Rufo,

Si j'ai bien compris en quoi mon algo n'est pas bon, c'est que tu utilise le même seuil pour tester tous le pixel. Je pensait que chaque pixel avait son propre seuil !

Sinon, ton algo à l'air plus optimisé, ce qui ne m'étonne pas !
J'avis pas cherché l'optimisation, juste à ne pas être récursif.

Si l'idée te conviens, et bien, çà me va !

Celà dit, y'a surement moyen d'optimiser encore. Je pense à essayer de trouver une manière de ne pas tester plusieurs fois les mêmes pixels. Mais j'ai peur que ce ne possible qu'avec un algo beaucoup plus compliqué.

Je cherche, mais juste par plaisir !

Au fait, çà sert à quoi ton truc ?

[edit]--Message édité par Mara's dad--[/edit]

rufo	alors Mara's dad, t'en penses quoi de ma solution?

rufo

bon, ton algo, il est faux... mais par contre j'ai repris ton idée, qui elle était très bien. Tiens, voilà l'algo modifié. Dis-moi ce que tu en penses.

TAB = matrice de l'image complète
Tab_Pixels = pm // contient les pixels trouvés et qui ensuite seront
cherché à leur tour
Nb_Trouve = 1 // correspond à la taille de Tab_Pixels
i = 0 // Indice du pixel à rechercher dans Tab_Pixels
ici, Tab_Pixels[i] donne pm

Fonction Principale(tm)
{
Tant que (i < Nb_Trouve)
{
// Tester les 8 voisins de Tab_Pixels[i]
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x-1, Tab_Pixels[i].y-1, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x-1, Tab_Pixels[i].y, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x-1, Tab_Pixels[i].y+1, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x, Tab_Pixels[i].y-1, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x, Tab_Pixels[i].y+1, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x+1, Tab_Pixels[i].y-1, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x+1, Tab_Pixels[i].y, tm)
Nb_Trouve += Tester(TAB, Tab_Pixels[i].x+1, Tab_Pixels[i].y+1, tm)

// on se déplace d'un cran dans Tab_Pixels, pour changer de pixel de recherche
i++
}

return(Tab_Pixels)
}

Fonction Tester(x, y, tm)
{
Si (Q=TAB[x,y] exite) alors
{
Si (Q.NdG > tm) alors
{
Si (Q n'appartient pas déjà à Tab_Pixels) alors
{
Tab_Pixels = Tab_Pixels + Q // on ajoute Q à la fin de Tab_Pixels
return 1
}
}
}

return 0
}

la fonction Appartient(Tableau de pixels, pixel) permet de vérifier simplement si pixel
n'existe pas déjà dans le tableau de pixels. On vérifie
si (Tab_Pixels[i].x == pixel.x) et (Tab_Pixels[i].y == pixel.y) et
(Tab_Pixels[i].NdG == pixel.NdG) alors return 1
sinon return 0

voilà. En tout cas, merci de ton aide... Sans toi, j'aurais pas pensé à faire ça :))))))))))))))))))))

rufo	merci beaucoup Mara's dad...Laisses-moi le temps de voir si ce que tu as fait marche.

Mara's dad

J'ai pas testé bien sûr ! mais c'est l'idée.

Code :

Pseudo-code pas standard !
// TAB <- tableau de tous les pixels !
Tableau_pixels = vide // Tableau des pixel qu'on cherche
Tableau_init = vide // Tableau des pixel testé par la boucle
Tableau_trouvés = pixel_cherché // Tableau des pixels trouvé par la boucle
Fonction Principale()
{
Nb_trouvé=1
TANT QUE Nb_Trouvé > 0
{
// On initialise le tableau des pixels a testés par la boucle avec le contenu de ceux trouvés la fois d'avant. (la première fois, avec le pixel de départ)
Tableau_init = clone(Tableau_Trouvé)
// On vide le tableau des pixels trouvé
Tableau_Trouvés = vide
Nb_Trouvé = 0
Pour( T=0; T < Taille(Tableau_init); T+)
{
Pixel = Tableau_init[T]
// On enlève le pixel du tableaux général pour pas le retester
TAB -= Pixel
// Essayer les 8 pixels qui entourent le pixel courant.
Nb_Trouvé += Tester( Pixel, Pixel.x-1, Pixel.y-1 )
Nb_Trouvé += Tester( Pixel, Pixel.x-1, Pixel.y )
Nb_Trouvé += Tester( Pixel, Pixel.x-1, Pixel.y+1 )
Nb_Trouvé += Tester( Pixel, Pixel.x, Pixel.y-1 )
Nb_Trouvé += Tester( Pixel, Pixel.x, Pixel.y+1 )
Nb_Trouvé += Tester( Pixel, Pixel.x+1, Pixel.y-1 )
Nb_Trouvé += Tester( Pixel, Pixel.x+1, Pixel.y )
Nb_Trouvé += Tester( Pixel, Pixel.x+1, Pixel.y+1 )
}
}
}// Fin fonction principale
Fonction Tester( P, x, y )
{
si existe( Q= TAB[x,y] )
{
si Q.Niveau_Gris > P.seuil
{
// On ajoute le pixel aux tableau des pixels trouvés ce coups çi et au tableau de tous les pixels trouvé depuis le début.
Tableau_Trouvé += Q
Tableau_Pixel += Q
RETURN 1
}
}
RETURN 0
}Fin fonction tester

C'est-y çà ?

rufo

voilà le code...mais je sais pas si ça va être lisible sur cette page...

CPixel *Croissance_Region(CImagePGM &ImageTr, CPixel pm, unsigned char tm, CPixel *Set_G)
{
CPixel *Voisins, *Temp ;
int i ;
long int cpt, j ;

Voisins = Next(ImageTr, pm) ;

for(i = 0 ; i < 8 ; i++)
{
// doit-on perndre en compte le pixel?
if (Voisins[i].Lire_Actif() != -1)
{
if (Voisins[i].Lire_NdG() > tm)
{
cpt = 0 ;
if (Set_G != NULL)
{
// Ajout de ce pixel dans l'ensemble G
while ((Set_G[cpt].Lire_Actif() == 1) || (Set_G[cpt].Lire_Actif() == -1))
cpt++ ;
if (Existe_Deja(Set_G, cpt, Voisins[i]) != VRAI)
{
// Recopie de Set_G dans Temp
Temp = new CPixel[cpt] ;
for(j = 0 ; j < cpt ; j++)
Temp[j] = Set_G[j] ;
delete Set_G ;

// Recopie de Temp dans Set_G
Set_G = new CPixel[cpt+1] ;
for(j = 0 ; j < cpt ; j++)
Set_G[j] = Temp[j] ;
delete Temp ;

// Ajout du pixel
Set_G[cpt] = Voisins[i] ;

// Relance de Croissance de région sur Voisins[i]
Temp = Croissance_Region(ImageTr, Voisins[i], tm, Set_G) ;
Set_G = Temp ;
}
}
else
{
Set_G = new CPixel[1] ;

// Ajout du pixel
Set_G[cpt] = Voisins[i] ;

// Relance de Croissance de région sur Voisins[i]
Temp = Croissance_Region(ImageTr, Voisins[i], tm, Set_G) ;
Set_G = Temp ;
}
}

}
}

delete Voisins ;

return Set_G ;
}

voici la classe CPixel
/************************************************************************************
***** Classe CPixel *****
*************************************************************************************/

class CPixel
{
private:
unsigned char NdG ; // Niveau de gris du pixel (entre 0 et 255)
int x ; // Coordonnée colonne du pixel
int y ; // Coordonnée ligne du pixel
int Actif ; // Pixel à prendre en compte si Actif = 1, pixel à ignorer si Actif = -1

public:
CPixel() ;
CPixel(CPixel &p) ;
CPixel(int yy, int xx, unsigned char N, int Act) ;

int Lire_x() ;
int Lire_y();
unsigned char Lire_NdG() ;
int Lire_Actif() ;

void Ecrire_x(int nx) ;
void Ecrire_y(int ny) ;
void Ecrire_NdG(unsigned char nNdg) ;
void Ecrire_Actif(int act) ;

int operator==(CPixel pxl) ;
int operator<(CPixel pxl) ;
int operator>(CPixel pxl) ;
CPixel & operator=(CPixel pxl) ;
} ;

rufo	par e-amil, ce sera plus facile...

rufo

Mystereetbouledegomme a écrit a écrit :

Ne serait ce t'il pas plus facile si tu me donnes le
code ... Car l'eplication n'est pas tres tres clair ...

tu veux le code que de la fonction de croissance de région? si c'est ça, oui, je peux te le passer. Si tu veux avoir l'algo complet (dans quel contexte cette fonction est utilisée) alors je peux pas, because c'est un algo "secret" (y'a une recherche dessus)

rufo

Mara's dad a écrit a écrit :

Si je comprend bien :
A partir un pixel donné, il faut dresser la liste des pixels voisins dont le niveau de gris est inférieur au seuil du pixel de départ, et des pixels voisins des voisins suivant les mêmes conditions, jusqu'à ce qu'on ne trouve plus de pixels ?

Si c'est bien çà, c'est sûr que la tentation de faire de la récursivité est grande, mais y'a moyen de s'en sortir autrement avec des boucles et un tableau des pixels trouvés à chaque tour.

la condition, c'est pas inférieur, mais supérieur...Mais bon, ça change rien.

en tout cas, si t'a une solution, donnes-là moi...Merci :)

Mara's dad

Si je comprend bien :
A partir un pixel donné, il faut dresser la liste des pixels voisins dont le niveau de gris est inférieur au seuil du pixel de départ, et des pixels voisins des voisins suivant les mêmes conditions, jusqu'à ce qu'on ne trouve plus de pixels ?

Si c'est bien çà, c'est sûr que la tentation de faire de la récursivité est grande, mais y'a moyen de s'en sortir autrement avec des boucles et un tableau des pixels trouvés à chaque tour.

mystereetbouledegomme

Ne serait ce t'il pas plus facile si tu me donnes le
code ... Car l'eplication n'est pas tres tres clair ...

rufo

Mystereetbouledegomme a écrit a écrit :

Apparement pas donne moi une bonne idee de ton algo et je verrai si je peux t'aider...

voilà. Je passe à ma fonction un objet (pm) de classe Cpixel (qui contient la ligne et la colonne du pixel dans l'image et son niveau de gris NdG), un unsigned char tm qui est le seuil (un NdG aussi) et un pointeur sur un tableau de Cpixel (Set_G), qui va contenir tous les pixels autour de pm qui ont leur NdG > tm. Donc, au début, on regarde les 8 voisins du pixel pm pour vérifier si certains d'entre-eux (ou tous) ont leur NdG > tm. pour ça, j'ai une fonction Next(CPixel pm) qui me renvoit les 8 voisins de pm (leur statut, un autre attribut de Cpixel) vaut -1 si un voisin n'est pas valide (cf les pm qui serainent dans les coins de l'image) et 1 dans le cas contraire et j'ai fait une boucle for sur ce tableau de 8 pixel. si Voisins[i]->NdG > tm alors on relance la fonction de croissance de région en ne prenant plus comme graine (au 1er appel de ma fonction de croissance de région, c'est pm) pm mais Voisins[i]. Et c'est reparti pour un tour, comme ça jusqu'à ce qu'on ne trouve plus de pixels autour de pm ou de ses voisins (et des voisins des voisins,...). Bien entendu, à chaque fois, avant de relancer la fonction de croissance de région, on sauve dans Set_G (le tableau de cpixels) Voisins[i].

mystereetbouledegomme

Apparement pas donne moi une bonne idee de ton algo et je verrai si je peux t'aider...

mystereetbouledegomme

Ben vas y lis mon post ca devrait t'aider quand meme...

rufo

gizmo a écrit a écrit :

Ok, donc si j'ai bien compris, ton systeme d'extension est semblable a celui du démineurs quand on tombe sur une case a valeur 0. Dans ce cas, la dérécursification est très simple, j'ai du faire un tel truc en permière candi.
Si tu ne vois pas comment, tu peux aussi essayer de reconstruire completement un algo de manière non récursive dès le départ, c'est pas plus compliqué mais c'est une vue de l'iesprit qui convient mieux a cerains.

ben tu vois, je suis vraiment pas fan de la récurcivité, mais là, pour faire ma croissance de région, je vois vraiment pas comment la faire en itératif... Un petit coup de pouce, svp? :)

rufo

Mystereetbouledegomme a écrit a écrit :

avec un do while (!stack.isEmpty() c'est meme encre mieux)
:D :D :D

ben merci beaucoup pour ces précisions. Je savais pas qu'il y avait en VC++ un objet stack...
le seul ennui (par rapport à ton exemple) c'est que tu fixe une limite à ta récurcivité (i<16), alors que dans mon cas, à part le nombre de pixels de mon image, je ne connais pas la limite de ma croissance de région...

cthulhu

autant pour moi ;)

cthulhu

ok, je prefere...

mystereetbouledegomme

avec un do while (!stack.isEmpty() c'est meme encre mieux)
:D :D :D

cthulhu

alors tu fai comment en c++?

mystereetbouledegomme

Petite precision pour la derecu avec stack il vaut mieux faire un do while sinon il rentre pas ...

cthulhu

wep, suis arrive en retard au boulot... obligé de me branler apres cet evenement....

mystereetbouledegomme

Fais pas le malin, ca doit etre du au fait que tu as graver ton premier 90 minutes ce matin :D

cthulhu

Mystère> sois pas négatif comme ca, moi je trouve ca pas tout a fait nul à chier.
C'est presque à la limite du potable. ;)

gizmo

rufo a écrit a écrit :

non, pas très, en fait... mais le pb réside dans le fait que ma recherche est récursive. Je sais si c'est possible de l'éviter. Tu vois, je pars d'un pixel et la recherche va s'étendre tout autour de lui. La région va grossir de plus en plus.

Ok, donc si j'ai bien compris, ton systeme d'extension est semblable a celui du démineurs quand on tombe sur une case a valeur 0. Dans ce cas, la dérécursification est très simple, j'ai du faire un tel truc en permière candi.
Si tu ne vois pas comment, tu peux aussi essayer de reconstruire completement un algo de manière non récursive dès le départ, c'est pas plus compliqué mais c'est une vue de l'iesprit qui convient mieux a cerains.