# Gnral Dveloppement > Algorithme & Mathmatiques > Traitement d'images >  Implementation algorithme Snake

## b_reda31

Bonjour  tous.
Je cherche  implmenter lalgorithme de  SNAKE  pour la segmentation dimage,jai donc cherch un peu partout sur la net ( sites anglais et franais) puis jai consult plusieurs  topics sur ce sujet  dans le forum.
Voici les diffrents points que je crois avoir compris,je vous demanderais SVP de me confirmer ou ventuellement me corriger les points suivants :


1-) Un Snake est un ensemble fini de points (Xi,Yi) o chaque point a un successeur et un prdcesseur ( Pour les contours ferms) .


2-) Lensemble des points du snake ont une position initiale aprs droulement de lalgorithme chaque point se dplacera et ainsi le Snake change de forme.


3-)Concernant le dplacement de chaque point !!l a commence  sembrouiller
Jai essay de schmatiser un peu pour pouvoir mieux comprendre.

Dans la figure les points rouges (1,2,,7) sont ceux qui forment le Snake,les points bleus sont les 8 voisin de chaque point du Snake.


     3-1) Chaque point du Snake prendra la place de lun de ses 8 voisins.

     3-2) LAQUELLE ??
Pour trouver la nouvelle position du point il faut calculer les 8 nergies des 8 points voisins (les poins bleus 1,2,3,,8) pour trouver ainsi les valeur E1,E2,,E8 associes aux nergies de chaque voisin.
Le point rouge se dplacerai ainsi vers le voisin ayant la plus PETITE valeur dnrgie.
EST-CE BIEN CELA ?

     3-3)COMMENT CALCULER CETTE ENERGIE ??
Energie= A*  Energie de continuit + B*  Energie de courbure  + C *    Energie Gradient 
A,B,C sont des paramtres que lUser spcifiera.
Pour ce qui est du calcul des nergies (continuit,courbure,gradient) l je suis vraiment bloqu !
Jai trouv plusieurs formules diffrentes les unes que les autres
Quelquun pourrai mexpliquer  travers le schma comment calculer ces 8 nergies afin de trouver ou est ce que le point du Snake se dplacera. 



Si vous tes arriv jusque l dans la lecture de ce sujet je vous remercie de votre patience ::mouarf::  
Jai vraiment besoin de confirmations pour pouvoir entamer limplmentation.
Merci davance.

Rda

----------


## ToTo13

Bonsoir,

je ne suis pas un spcialiste des snakes, mais voil quelques explications :
 - il me semble qu'un point du snake peut se dplacer de plusieurs pixels, pas seulement sur un huit voisinage.
 - la formule de l'nergie n'est JAMAIS unique, c'est pour cela que tu en as trouv autant de diffrentes. Chaque application a sa propre formule d'nergie.
En gnral, une formule d'nergie est du type : E = Alpha * Einterne + Beta * Eexterne + ... (une srie d'nergies complmentaires : courbure, torsion, nombre de points du snake, ...). Par exemple, dans celui que j'ai utilis pour un projet, je calculais la variance de l'intrieur (Einterne) et de l'extrieur (Eexterne) de mon snake, car je voulais sparer deux zones relativement homognes.

Voil un petit exemple.

----------


## b_reda31

Merci pour ces prcisions,le problme c'est que je ne sais pas exactement comment calculer les nergies Internes et externes,est ce que vous pouvez me montrer  l'aide du Schma comment on peut appliquer la formule
Energie interne = A/2 *||v'(s)||  +  B/2 *||v''(s)|| ??
ainsi que l'energie externe




> *ToTo13*
> Voil un petit exemple.


Ce lien est mort je crois.

----------


## ToTo13

Bonjour,

peux tu dtailler cette formule ?
A et B sont trs certainement deux coefficients qu'il te faut rgler (des paramtres du snake).
Mais que sont v'(s) et v"(s) ?

----------


## b_reda31

> Bonjour,
> 
> peux tu dtailler cette formule ?
> A et B sont trs certainement deux coefficients qu'il te faut rgler (des paramtres du snake).
> Mais que sont v'(s) et v"(s) ?


Bonjour,
A et B sont les parametres de continuit et courbure respectivements (Alpha,Beta)


V(s)=Vs=(Xs,Ys)  Coordonns du point  s  dans le snake.
Je pense donc quil serait plus exacte decrire :
Energie interne(s) = A/2 *||v'(s)|| + B/2 *||v''(s)||

v'(s) et v"(s) sont la driv et driv seconde respectivements de v(s).(driv par rapport   s )
Comment calculer cette driv ?

----------


## pseudocode

> v'(s) et v"(s) sont la driv et driv seconde respectivements de v(s).(driv par rapport   s )
> Comment calculer cette driv ?


par les diffrences finies sur les coordonnes curvilignes ?

----------


## b_reda31

> par les diffrences finies sur les coordonnes curvilignes ?



Je ne connais cette mthode mais vous m'avez ouvert une nouvelle piste.
Merci.

----------


## pseudocode

> Je ne connais cette mthode mais vous m'avez ouvert une nouvelle piste.
> Merci.


 ::mrgreen::  

Dit comme cela a fait trs "pro", mais en fait c'est juste calculer la pente de la droite qui relie 2 points successifs.

----------


## b_reda31

> par les diffrences finies sur les coordonnes curvilignes ?




Voici ce que j'ai trouv:

L'nergie de continuit est lie  : * ||V(i)-V(i-1)||=[X(i)-X(i-1)]+[Y(i)-Y(i-1)]*
Ce qui est donc la distance au carr du point avec son prdcesseur.

L'nergie de courbure est lie  :
*||V(i-1)-2*V(i)+V(i+1)||=[X(i-1)-2*X(i)+X(i+1)]+[Y(i-1)-2*Y(i)+Y(i+1)]*

J'ai donc appliqu ces formules sur le point 2 du snake dans le Schma.Et voici l'nergie interne du point 2 ainsi que ses voisins que j'ai trouv :
*ENERGIE DE CONTINUITE :*

17   16   17
26   25   26
37   36   37 



*ENERGIE DE COURBURE :*


26    10     2 
26    10     2
34    18    10


Maintenant la question que je me pose,dois je DIRECTEMENT multiplier chacune de ces "matrices" par Alpha et Beta et les additionner ou bien je dois  
les "normaliser" avant?? ( par exemple les diviser par une valeur pour qu'ils soient dans la mme "echelle")

----------


## pseudocode

> Maintenant la question que je me pose,dois je DIRECTEMENT multiplier chacune de ces "matrices" par Alpha et Beta et les additionner ou bien je dois  
> les "normaliser" avant?? ( par exemple les diviser par une valeur pour qu'ils soient dans la mme "echelle")


il faut normaliser les donnes avant de faire les calculs d'energie.

----------


## b_reda31

> l faut normaliser les donnes avant de faire les calculs d'energie.


Pouvez vous tre plus prcis?
Comment normaliser les donnes?

----------


## pseudocode

il faut diviser chaque element d'une matrice par la somme des elements de la matrice.

Voila un de mes vieux programmes de snake 2D en Java, pas optimis pour un cachou, mais qui pourra peut-tre t'clairer:



```

```

----------


## b_reda31

Je m y connais pas en Java mais le langage n'a pas l'air si diffrent du C.
Merci PseudoCode,ceci me rendra normment service.

----------


## pseudocode

> Je m y connais pas en Java mais le langage n'a pas l'air si diffrent du C.


Ca ressemble enormment au C++, sans les *, &  et ->.  :;): 




> Merci PseudoCode,ceci me rendra normment service.


Je l'ai lanc chez moi et il a l'air de fonctionner. C'est dj a.  ::P:

----------


## b_reda31

Bonjour,j'ai pass un bon moment  essayer de comprendre ce code,il me reste quelque point qui me sont incomprhensible:


```

```

Comme j'adore les schmas j'en ai encore fais un pour mieux comprendre   ::mrgreen:: 

1-)*LA FONCTION CONTINUITY :*
Elle renvoie   ((Un+Vn)-Dn)/Dn
Que signifie cette valeur?
Minimiser cette valeur reviens  rapprocher les point NEXT et PREV du point P Mais alors pourquoi soustraire ET diviser pas Dn??!!
En quoi cela consiste rellement  minimiser cette nergie?


1-)*LA FONCTION CURVATURE :*
Elle retourne ((Cx*Cx)+(Cy*Cy))/Un*Vn.
Tq Cx=Ux+Vx,Cy=Uy+Vy.

Mme question pour cette fonction,qu'elle est la "signification" (sens) du rsultat?( Qu'est ce qu'il reprsente)


Merci d'avance.

Rda.

----------


## pseudocode

> Bonjour,j'ai pass un bon moment  essayer de comprendre ce code,il me reste quelque point qui me sont incomprhensible:


J'ai donn ce code pour montrer le principe gnral de l'algorithme: 

>pour chaque point du snake
--> calcul de l'energie sur le voisinage 3x3
--> normalisation
--> recherche de la plus faible energie
--> dplacement du point du snake
>fin pour

Les fonctions d'energies utilises sont des experimentations personnelles diverses et varies (et sans doute fausses). Je vais tacher de retrouver une implmentation plus aboutie et je la posterai dans "contribuez". Pour l'instant je vais essayer de me souvenir et d'expliquer celles la:




> *LA FONCTION CONTINUITY :*
> Elle renvoie   ((Un+Vn)-Dn)/Dn
> Que signifie cette valeur?


Hum... Cette nergie est minimale lorsque les 3 points sont aligns. Donc elle encourage les points du snake a former une ligne droite. A mon avis, j'ai du crer cette fonction spcialement pour "coller" aux bords du carr.  ::koi:: 




> *LA FONCTION CURVATURE :*
> Elle retourne ((Cx*Cx)+(Cy*Cy))/Un*Vn.
> Tq Cx=Ux+Vx,Cy=Uy+Vy.


C'est la courbure standard, la mme que dans ta formule mais crite de manire plus "vectorielle":

c = u + v = (prev-p) + (next-p) = prev - 2*p + next




> qu'elle est la "signification" (sens) du rsultat?( Qu'est ce qu'il reprsente)


Les fonctions d'nergies sont l pour contraindre les mouvements du snake. Tu peux aller fureter sur le web pour trouver des fonctions d'nergies "habituelles", mais le mieux c'est de les crer toi mme suivant ce que tu souhaites faire.

----------


## b_reda31

> LA FONCTION CURVATURE :
> Elle retourne ((Cx*Cx)+(Cy*Cy))/Un*Vn.
> Tq Cx=Ux+Vx,Cy=Uy+Vy.







> C'est la courbure standard, la mme que dans ta formule mais crite de manire plus "vectorielle":
> 
> c = u + v = (prev-p) + (next-p) = prev - 2*p + next


Ah oui c'est vrai, mais alors pourquoi diviser le rsultat par Un*Vn ?
et dans l'nergie de continuit on divise par Dn, Pourquoi?!

----------


## pseudocode

> Ah oui c'est vrai, mais alors pourquoi diviser le rsultat par Un*Vn ?


parceque c'est une drive, donc il faut diviser par le "pas" = la distance entre les points. D'ailleurs dans la formule "standard" tu dois dja avoir cette division.




> et dans l'nergie de continuit on divise par Dn, Pourquoi?!


Bonne question. A mon avis ca ne sert  rien  ::aie:: . 

Essaye de reprendre les formules "standards" que tu avais donnes, ca sera plus simple que d'essayer de comprendre les miennes.

----------


## b_reda31

> D'ailleurs dans la formule "standard" tu dois dja avoir cette division.


Non il n y pas de division,je pense que le pas a t suppos gal  1.




> Je vais tacher de retrouver une implmentation plus aboutie et je la posterai dans "contribuez"


Merci pour tous ces claircissements  ::king::

----------


## b_reda31

Le problme d'nergie interne tant quasi-rsolu reste maintenant le problme 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

----------


## pseudocode

> Le problme d'nergie interne tant quasi-rsolu reste maintenant le problme de l'nergie Externe   
> 
> je n'ai pas compris grand chose en lisant cette partie de code ,Pouvez vous me donner des explications


Hum... La cas va tre plus compliqu  expliquer car je me suis un peu "cart" des mthodes habituelles  ::P: . Mais a donne de bons rsultats alors a mrite que je m'y attarde un peu (enfin selon moi  ::roll:: ).

L'nergie Externe c'est ce qui fait rellement "bouger" le snake, car l'nergie interne ne s'occupe que de le contraindre pour qu'il reste cohrent. On a donc besoin de dfinir une nergie qui "attire" le snake vers les endroits intressants.

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


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

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


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



```

```


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

voila, j'espre que c'est plus clair.

----------


## souviron34

> 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 combine au gradient donne une image 3D ressemblant (ventuellement)  une carte 3D d'une rgion montagneuse.. Des pics, des massifs, et des valles..

Le snake dmarrant "n'importe o", on veut qu'il suive le fond des valles..

----------


## pseudocode

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


 ::merci::

----------


## b_reda31

> 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?!

----------


## pseudocode

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




> 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 "binarise".

----------


## b_reda31

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

Je pense que je vais opter pour ta mthode  ::king:: 

PS: J'attends de commencer l'implmentation avant de rendre ce sujet rsolu.

Merci encore.

----------


## b_reda31

Bonjour  tous,
Jai enfin pu implmenter cet algorithme et jai test les diffrentes nergies indpendamment les unes des autres :

1-)En prenant compte seulement de lnergie de continuit (Alpha=1,beta=gamma=0)
La courbe se referme et converge vers un pointce qui me parait  normal .

2-)MAIS en prenant en compte seulement lnergie de courbure (Alpha=gamma=0,beta=1)
Voici ce que jobtient !!est ce normal ?! (VOIR FIGURE)
Jai affich les nergies de voisinage de quelques points et jai constat que pour un point donn il y avait plusieurs voisins dont lnergie est minimal (les nergies sont gales sur plusieurs points du voisinage)Le minimum qui sera choisi et donc la premire occurrence  partir du voisin  HAUT-GAUCHE  ce qui expliquerai peut tre pourquoi la courbe monte vers la gauche ?!!Quen pensez vous??

PS:Je tien  ajouter quelques prcisions concernant limplmentation des procdures CONTINUITY et CURVATURE :





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






Concernant la procdure Curvature jai divis par H  la puissance 4 (H tant le Pas initial choisi par luser) car si je divise par Un*Vn,une division par Zro pourra se produire lorsquun point se superpose avec son successeur ou prdcesseur.
Mme chose pour Continuity ,ici jai divis par H.

----------


## pseudocode

> 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 premire 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 pince de "random" dans le calcul de l'energie permet d'arranger cela.  :;):

----------


## b_reda31

> Concernant la procdure Curvature jai divis par H  la puissance 4 (H tant le Pas initial choisi par luser) car si je divise par Un*Vn,une division par Zro pourra se produire lorsquun point se superpose avec son successeur ou prdcesseur.
> Mme chose pour Continuity ,ici jai divis par H.


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

----------


## pseudocode

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


Si, surement.  ::P: 

Ne prend pas trop ce code en modle. 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 rcents, il faut que je le remette au propre.

----------

