La méthode de détection par snake, ou contour actif, consiste à placer aux alentours de la forme à détecter une ligne initiale de contour. Cette ligne va se déformer progressivement selon l'action de plusieurs forces qui vont la tirer ou la pousser vers la forme.
Les forces impliquées vont dériver de trois énergies associées au snake:
Détaillons un peu plus ces trois termes d'énergies:
Pour établir les expressions, on considère que notre snake est composé de n points Vi que l'on va définir de facon paramétrique en fonction de l'absisse curviligne s.
Elle va dépendre uniquement de la forme du snake. C'est une contrainte de régularité sur la courbe. Elle s'écrit:
E int = (a(s)).||(Vs(s)|| + b(s)).||(Vss(s)||).
a et b sont les poids respectifs accordés à la dérivée premiere Vs et à la dérivée seconde Vss. On ajustera a et b pour trouver un intermediaire entre un contour souple mais pas forcemment très régulier (et qui pourra alors se caler sur des coins et des angles aigus) et un contour très régulier qui suivra bien le contour sans s'accrocher sur des petites aspérités.
Elle caractérise les éléments vers lesquels on veut attirer le snake sur l'image. Pour notre problème, puisqu'il s'agit de détecter des contours, on va s'intéresser aux lignes de fort gradient:
E image= -gradient(i).
Pour certains problèmes, on peut choisir d'attirer le snake vers des zones présentant d'autres caractéristiques: vers les zones les plus sombres par exemple.
Elle est définie par l'utilisateur selon les spécificités du problème. On peut par exemple imposer une distance minimale ou maximale entre deux points consécutifs du contour actif.Elle va s'exprimer en fonction de V(s) uniquement:
E cont=E cont(s)
L'énergie totale en un point du snake V(s) va donc s'écrire:
E totale(V(s), Vs(s), Vss(s)) = E int(V, Vs, Vss) + E image(V) + E cont(V).
Nous avons affaire à un nombre de points Vi fini. On exprime directement Ei: énergie au point Vi en fonction de tous les points V du snake en utilisant notamment: Vis(s)= Vi - Vi-1 et: Viss(s)= Vi+1 - 2Vi + Vi-1
Ce qui nous permet de discrétiser la formule de Ei: énergie au point Vi sous la forme:
Ei totale(Vi-1, Vi, Vi+1) = E int(Vi-1, Vi, Vi+1) + E image(Vi) + E cont(Vi).
Et donc l'énergie totale du snake vaut:
E totale(Vi-1, Vi, Vi+1) = somme (Ei) = somme (Ei int(Vi-1, Vi, Vi+1) + Ei image(Vi) + Ei cont(Vi)).
Une fois l'énergie totale définie selon les formules précédentes et les contraintes spécifiques du problème, on recherche la position du contour qui va minimiser cette énergie. On se ramène donc à un probleme d'optimisation d'une fonction numérique de plusieurs variables (Les variables seront ici les positions des différents points du snake).
Cette optimisation peut se faire avec une méthode variationnelle classique. Dans notre cas nous utilisons une autre technique dite de programmation dynamique. [Amini et al.].
En fait, vue la forme de E, notre problème se ramène à la question suivante: minimiser une expression de la forme: E(V1, V2, ... Vn) = E1(V1, V2, V3) + E2(V2, V3, V4) +... Ei(Vi, Vi+1, Vi+2)). Une méthode pour optimiser une telle fonction par programmation dynamique est la suivante:
On va commencer par minimiser E1 par rapport à la premiere variable V1. Comme seul E1 dépendait de V1, on a ainsi éliminé cette variable de notre processus d'optimisation. Le minimum obtenu ne dépend plus que de V2 et V3. A l'étape suivante on minimisera S2(V2, V3, V4) = (minV1 E1)(V2, V3) + E2(V2, V3, V4) par rapport a la variable suivante, soit V2, et ainsi de suite, en optimisant progressivement par rapport a toutes les variables. La théorie nous assure alors que la valeur de E ainsi trouvée est bien la valeur minimale absolue et répond donc à notre question.
Appliquons cette methode à notre snake. Nous partons d'un premier contour initialisé par l'utilisateur lui-même. Nous allons le parcourir progressivement et en chaque point éventuellement déplacer le point pour que sa nouvelle position optimise l'énergie du snake.
Chaque point a 9 déplacements possibles a chaque étape comme le montre la figure suivante:
Le déplacement éventuel du point considéré se fait en minimisant le terme d'énergie qui en dépend selon la méthode expliquée plus haut. C'est à dire que pour tout point Vi, on va calculer, pour tout jeu de positions (Vi+1, Vi+2) des deux prochains points, le déplacement (et donc la position finale) optimale de Vi. Puis on passe au point suivant Vi+1 et on optimise son déplacement pour toute position (Vi+2, Vi+3) des deux points suivants. Une fois arrivé au dernier point du snake, Vn, dont on calcule également le déplacement optimal, on va pouvoir remonter le long des points et ainsi retrouver toutes les positions de tous les Vi qui assureront une énergie minimale pour le snake. En pratique, le nombre de déplacements possibles est limité a 9 pour des raisons évidentes de complexité d'algorithme. On va donc itérer plusieurs fois le processus (et reparcourir le snake) jusqu'à ce que les points atteignent leur position optimale.
Les résultats sont les suivants: