I. Principe et fonctionnement intuitif de la méthode des contours actifs▲
Un contour actif est un ensemble de points qu'on va tenter de déplacer pour lui faire épouser une forme. Il s'agit d'une technique d'extraction de données utilisée en traitement d'images. L'idée de cette méthode est de déplacer les points pour les rapprocher des zones de fort gradient tout en conservant des caractéristiques comme la courbure du contour ou la répartition des points sur le contour ou d'autres contraintes liées à la disposition des points.
Au démarrage de l'algorithme, le contour est disposé uniformément autour de l'objet à détourer puis il va se rétracter pour en épouser au mieux les formes. De la même manière, un contour actif peut aussi se dilater et tenter de remplir une forme, il sera alors situé à l'intérieur de celle-ci au démarrage de l'algorithme.
À chaque itération, l'algorithme va tenter de trouver un meilleur positionnement pour le contour pour minimiser les dérives par rapport aux contraintes utilisées. L'algorithme s'arrêtera lorsqu'il ne sera plus possible d'améliorer le positionnement ou simplement quand le nombre maximum d'itérations aura été atteint. On utilise les notions d'énergies interne et externe pour caractériser respectivement la forme du contour et tous les éléments qui lui sont propres, et le positionnement du contour sur l'image en tenant compte des lignes de gradient.
Voici un exemple de déroulement d'une recherche en contour actif pour détourer un objet :
II. Itérations de l'algorithme▲
Chaque itération peut se représenter de la manière suivante :
- calcul des énergies interne et externe, caractérisant le contour lui-même et son positionnement sur l'image :
- pour chaque point du contour, détermination d'une nouvelle position, sur laquelle le contour devrait mieux minimiser les écarts de contraintes ;
- arrangement du contour pour qu'il respecte des contraintes d'écartement entre les points, de régularité de points…
Les énergies peuvent être calculées dans un espace réduit (l'image discrétisée à chaque point du snake) ou bien dans le domaine image, en considérant une spline reliant tous les pixels du snake. Cette méthode, bien que plus rigoureuse mathématiquement, n'offre pas de réelles améliorations et demande davantage de temps de calcul.
II-A. L'énergie interne▲
L'énergie interne ne dépend pas de l'image ni de la forme à détourer, elle ne dépend que des points du contour. Elle regroupe des notions comme la courbure du contour ou la régularité d'espacement des points. En effet, le contour doit conserver une forme arrondie en minimisant les dérivées d'ordre 1, 2… et doit empêcher un point de se détacher trop loin du reste du contour. Idéalement, l'énergie interne est minimale pour un cercle où tous les points sont régulièrement espacés.
Grande liberté est laissée au concepteur pour imaginer toutes les heuristiques qu'il voudra.
Voici deux heuristiques de calcul d'énergie interne :
// Calcul de l'écartement entre les points
private double f_uniformity(Point prev, Point next, Point p) {
// length of previous segment
double un = distance2D(prev, p);
// mesure of uniformity
double avg = snakelength/snake.size();
double dun = Math.abs(un-avg);
// elasticity energy
return dun*dun;
}// Calcul de la rigidité du snake
private double f_curvature(Point prev, Point p, Point next) {
int ux = p.x-prev.x;
int uy = p.y-prev.y;
double un = Math.sqrt(ux*ux+uy*uy);
int vx = p.x-next.x;
int vy = p.y-next.y;
double vn = Math.sqrt(vx*vx+vy*vy);
double EPSILON = 1E-5;
if (un < EPSILON || vn < EPSILON) return 0;
double cx = (vx+ux)/(un*vn);
double cy = (vy+uy)/(un*vn);
// curvature energy
double cn = cx*cx+cy*cy;
return cn;
}II-B. L'énergie externe▲
L'énergie externe correspond à l'impact du contour sur l'image. Pour la calculer, il faut considérer l'opposé de la valeur de son gradient (ou de toute autre représentation mettant en jeu les contours à épouser) en chaque point du contour. Cette énergie externe doit théoriquement être minimale si le contour épouse parfaitement la forme à extraire.
Notez qu'on ne considère l'opposé du gradient que pour avoir une énergie externe minimale à la convergence de l'algorithme.
On pourra utiliser une représentation en gradient et en flot pour ajouter de l'information dans les zones uniformes où le gradient est nul, de manière à guider le snake vers le bord le plus proche. Encore une fois, le programmeur est entièrement libre dans l'élaboration de ses heuristiques.
Voici deux heuristiques de calcul d'énergie externe :
// Attirer le snake vers les bords
private double f_gflow(Point cur, Point p) {
// gradient flow
int dcur = this.flow[cur.x][cur.y];
int dp = this.flow[p.x][p.y];
double d = dp-dcur;
return d;
}qui représente l'accroche du snake sur les zones de fort gradient
// Accroche des points sur les zones de fort gradient
private double f_inertia(Point cur, Point p) {
double d = distance2D(cur, p);
double g = this.gradient[cur.x][cur.y];
double e = g*d;
return e;
}II-C. Utilisation des deux énergies▲
Chaque position du contour actif donne une énergie interne et une énergie externe dont la somme doit être minimisée et influencera les mouvements des points du contour actif. La grande difficulté de l'utilisation des snakes réside dans le choix des pondérations à donner à chaque énergie. Traditionnellement il est d'usage d'utiliser un paramètre pour l'énergie interne et un autre pour l'énergie externe, mais un réglage plus fin peut s'opérer en ajoutant des paramètres différents pour des aspects différents de l'énergie interne ou de l'énergie externe.
On pourra ainsi avoir :
- un paramètre pour pondérer l'énergie dégagée par la mauvaise courbure du snake ;
- un autre pour pondérer l'énergie dégagée par le non-respect de l'écartement régulier entre ses points ;
- un autre pour pondérer l'énergie dégagée par le positionnement sur les lignes de gradient de l'image ;
- …
II-D. Modifications du contour▲
Après avoir calculé l'énergie globale dégagée par le contour et par son positionnement sur l'image, il convient de déterminer comment le faire évoluer pour minimiser cette énergie. Pour cela, une méthode simple et intuitive est d'observer les pixels voisins immédiats de chaque point du contour pour déterminer pour chacun d'eux l'énergie globale du snake, chaque meilleur voisin devenant un point du contour.
Il est nécessaire que le contour possède toujours suffisamment de points pour être sûr de bien calculer son énergie globale, en particulier son énergie externe qui sera plus précise en tenant compte de davantage de points. C'est la raison pour laquelle il peut s'avérer pertinent de rajouter ou de supprimer des points à chaque itération si des contraintes ne sont pas suffisamment respectées. Par exemple, on pourra rajouter un point au snake si ses voisins sont trop éloignés. À l'inverse, on pourra supprimer un point s'il est trop près de ses voisins.
Outre le fait de calculer plus efficacement les énergies, l'ajout de points est nécessaire dès lors que le snake change de taille. Nous ne connaissons pas a priori la taille de l'objet à extraire au début de l'algorithme, il n'est donc pas totalement absurde de revoir le nombre de points au cours de son déroulement.
Voici des illustrations des grandes étapes du déroulement d'un snake :
|
|
|
|
|
|
On remarque notamment la position de départ en cercle entourant entièrement la forme à détourer puis la progression du snake dans les concavités.
III. Faiblesses des snakes, cas de non-convergence totale▲
Déjà abordé, le positionnement des paramètres des différents éléments des énergies reste un point très délicat à prévoir, surtout si on commence à tenir compte de beaucoup d'aspects de chaque énergie. De plus, ces valeurs sont liées à la forme à extraire. La forme va beaucoup jouer, notamment dans ses concavités où les points du snakes ne peuvent s'aventurer sans pénaliser leur énergie interne en augmentant leur courbure. Les pondérations s'obtiennent le mieux via un tuning après déjà plusieurs exécutions pour affiner les résultats ou le comportement fin du snake.
Les contours actifs s'avèrent très pertinents pour isoler des formes convexes régulières et idéales. Pour l'extraction de formes comportant beaucoup de concavités franches, il faudra diminuer l'impact du non-respect de cette contrainte pour privilégier l'écartement entre les points ou même l'énergie externe. C'est ce qu'on peut remarquer sur cette image résultat où l'on aperçoit la divergence du snake à la base des feuilles du trèfle. Et comme on pouvait s'y attendre, le snake converge parfaitement sur les bords externes des feuilles, là où les contraintes de son énergie interne sont les mieux respectées.
Un autre aspect non négligeable, mais non directement lié à la méthode des snakes réside dans l'image à analyser. En effet, celle-ci doit être la plus pure possible pour effacer au maximum le bruit qui pourrait amener à un pic de gradient sur lequel le snake pourrait rester accroché. Une fois accroché, il n'aurait que son énergie interne pour s'en décrocher et continuer sa route. Voici un exemple d'image de travail nettoyée et mettant en évidence des données de guidage pour l'énergie externe : les lignes de fort gradient et le flot.
Et dernier point difficile à généraliser, la position des points au démarrage de l'algorithme : le snake doit entièrement entourer la forme dans le cas d'un rétrécissement et il doit entièrement être contenu dans celle-ci dans le cas d'une dilatation. Sinon on se retrouvera dès le début avec des problèmes d'énergie externe.
IV. Remerciements▲
Je remercie toute l'équipe de la rubrique Algorithmes et Traitement d'Images pour leurs remarques constructives et particulièrement pseudocode pour ses explications de code ;) ainsi que olsimare pour sa relecture.
Vous pouvez télécharger une version directement utilisable, en format JAR sur le forum.