Implementation algorithme Snake

Citation:

---

Envoyé par b_reda31

Le problème d'énergie interne étant quasi-résolu reste maintenant le problème de l'énergie Externe :oops: :oops:

je n'ai pas compris grand chose en lisant cette partie de code :aie:,Pouvez vous me donner des explications

---

Hum... La cas va être plus compliqué à expliquer car je me suis un peu "écarté" des méthodes habituelles :P. Mais ça donne de bons résultats alors ça mérite que je m'y attarde un peu (enfin selon moi :roll:).

L'énergie Externe c'est ce qui fait réellement "bouger" le snake, car l'énergie interne ne s'occupe que de le contraindre pour qu'il reste cohérent. On a donc besoin de définir une énergie qui "attire" le snake vers les endroits intéressants.

Dans mon cas (et généralement) on choisit d'attirer le snake vers les forts gradients = les bords des objets. Donc on commence par calculer le gradient:

Code:

---

Channel gradient = new Gradient(3,1.0).filter(image);

---

ici c'est un noyau MDIF 3x3, sigma=1.0 (cf. tuto sur les filtres)

Cette "image" du gradient vaut "255" sur les bords et "0" partout ailleurs (dans le cas idéal).

Maintenant il nous faut une énergie qui pousse les points du snake vers le plus proche "255". Pour cela j'ai calculé la carte des distances sur l'image du gradient (cf. contribution sur Chamfer).

Code:

---

this.force = new Chamfer(true,Chamfer.chamfer5).filter(gradient);

---

Chaque pixel de la carte des distances nous donne la distance (:P) jusqu'au plus proche "255". Il faut donc que le snake se dirige vers les pixels qui ont une valeur faible => on diminue la distance et donc on se rapproche du gradient.

Code:

---

1 2 3

private double extforce(Point p) { return this.force.getValue(p.x, p.y); }

---

On peut voir cela comme une carte en 3D. Le snake descend le long des pentes pour atteindre le minimum (altitude=0)

voila, j'espère que c'est plus clair.

Citation:

---

Envoyé par pseudocode

On peut voir cela comme une carte en 3D. Le snake descend le long des pentes pour atteindre le minimum (altitude=0)

---

en fait d'ailleurs je pense que c'est l'image la plus claire pour expliquer un snake...

L'image originale combinée au gradient donne une image 3D ressemblant (éventuellement) à une carte 3D d'une région montagneuse.. Des pics, des massifs, et des vallées..

Le snake démarrant "n'importe où", on veut qu'il suive le fond des vallées..

Citation:

---

Envoyé par souviron34

en fait d'ailleurs je pense que c'est l'image la plus claire pour expliquer un snake...

---

:merci:

http://xray.club.fr/dvpimg/SnakeAnimation.gif

Citation:

---

Envoyé par pseudocode

Chaque pixel de la carte des distances nous donne la distance () jusqu'au plus proche "255".

---

Soit DIST[x][y]la carte des distances

Dist[x][y]= DISTANCE ENTRE LE POINT (x,y) ET LE POINT LE PLUS PROCHE DE VALEUR 255??
est ce bien cela?!
un point contour n'a pas forcement 255 comme valeur ?!!
Ou peut etre que l'image doit etre "BINARISER" avant ce traitement?!

Citation:

---

Envoyé par b_reda31

Soit DIST[x][y]la carte des distances

Dist[x][y]= DISTANCE ENTRE LE POINT (x,y) ET LE POINT LE PLUS PROCHE DE VALEUR 255??
est ce bien cela?!

---

oui. :king:

Citation:

---

un point contour n'a pas forcement 255 comme valeur ?!!
Ou peut etre que l'image doit etre "BINARISER" avant ce traitement?!

---

oui, l'image du gradient est "binarisée".

Merci,là c'est plus clair :yaisse2:

Je pense que je vais opter pour ta méthode :king:

PS: J'attends de commencer l'implémentation avant de rendre ce sujet résolu.

Merci encore.

Bonjour à tous,
J’ai enfin pu implémenter cet algorithme et j’ai testé les différentes énergies indépendamment les unes des autres :

1-)En prenant compte seulement de l’énergie de continuité (Alpha=1,beta=gamma=0)
La courbe se referme et converge vers un point…ce qui me parait « normal ».

2-)MAIS en prenant en compte seulement l’énergie de courbure (Alpha=gamma=0,beta=1)
Voici ce que j’obtient !!est ce normal ?! (VOIR FIGURE)
J’ai affiché les énergies de voisinage de quelques points et j’ai constaté que pour un point donné il y avait plusieurs voisins dont l’énergie est minimal (les énergies sont égales sur plusieurs points du voisinage)…Le minimum qui sera choisi et donc la première occurrence à partir du voisin « HAUT-GAUCHE » ce qui expliquerai peut être pourquoi la courbe monte vers la gauche ?!!Qu’en pensez vous??

PS:Je tien à ajouter quelques précisions concernant l’implémentation des procédures CONTINUITY et CURVATURE :

Citation:

---

LA FONCTION CONTINUITY :
Elle renvoie ((Un+Vn)-Dn)/Dn
LA FONCTION CURVATURE :
Elle retourne ((Cx*Cx)+(Cy*Cy))/Un*Vn.

---

Concernant la procédure Curvature j’ai divisé par H à la puissance 4 (H étant le Pas initial choisi par l’user) car si je divise par Un*Vn,une division par Zéro pourra se produire lorsqu’un point se superpose avec son successeur ou prédécesseur.
Même chose pour Continuity ,ici j’ai divisé par H².

Citation:

---

Envoyé par b_reda31

J’ai affiché les énergies de voisinage de quelques points et j’ai constaté que pour un point donné il y avait plusieurs voisins dont l’énergie est minimal (les énergies sont égales sur plusieurs points du voisinage)…Le minimum qui sera choisi et donc la première occurrence à partir du voisin « HAUT-GAUCHE » ce qui expliquerai peut être pourquoi la courbe monte vers la gauche ?!!Qu’en pensez vous??

---

oui, c'est exactement ca. Dans mon code, quand toutes les enegies sont égales, c'est la 1ere qui est toujours choisie. Une pincée de "random" dans le calcul de l'energie permet d'arranger cela. ;)

Citation:

---

Concernant la procédure Curvature j’ai divisé par H à la puissance 4 (H étant le Pas initial choisi par l’user) car si je divise par Un*Vn,une division par Zéro pourra se produire lorsqu’un point se superpose avec son successeur ou prédécesseur.
Même chose pour Continuity ,ici j’ai divisé par H².

---

Dans votre code il n y a pas de division par zéro qui se produit?!(cas des points qui se superposent )

Citation:

---

Envoyé par b_reda31

Dans votre code il n y a pas de division par zéro qui se produit?!(cas des points qui se superposent )

---

Si, surement. :P

Ne prend pas trop ce code en modèle. C'était pour expliquer le principe de l'algo et pas pour une utilisation clé-en-main.

Cela dit, si 2 points sont confondus alors (au choix):
1. la courbure est nulle
2. il manque une énergie pour éviter que cela arrive
3. il faut supprimer l'un des deux points

Promis, j'essaierai de poster un code qui marche mieux sous peu. J'ai retrouvé des sources plus récents, il faut que je le remette au propre.