Centre de Mathématiques et de Leurs Applications

Séminaire du jeudi 7 janvier 2010

Orateur: Laurent Najman (ESIEE)

Titre: Optimisation combinatoire par ligne de partage des eaux

Résumé:

Le cadre des graphes aux arêtes valuées pondérées a acquis une importance considérable en analyse et traitement des images ces dernières années, notamment avec l'apparition des algorithmes de type flots maximaux ("graph cuts").

La première partie de cet exposé aborde la ligne de partage des eaux ("watersheds") dans ce cadre. Nous définissons une coupure par ligne de partage de eaux en suivant l'idée intuitive d'une goute d'eau tombant sur une surface topographique. Nous établissons tout d'abord la consistance de ces lignes de partage des eaux : elles peuvent être définies de manière équivalente soit par leurs "bassins d'attraction" (via une propriété de plus grande pente), soit par les "lignes séparant" ces bassins d'attractions (via le principe de la goute d'eau). Nous prouvons ensuite leur optimalité en terme de forêts couvrantes de poids optimal. Nous proposons également un algorithme linéaire pour les calculer, qui est le plus efficace en théorie et en pratique. A notre connaissance, il n'existe pas de cadre théorique discret pour la ligne de partage des eaux permettant de prouver des propriétés similaires.

Dans la deuxième partie, nous étudions un cadre d'optimisation combinatoire pour la segmentation d'images avec marqueurs qui inclut les flots maximaux, les marcheurs aléatoires, et les plus courts chemins. Ces algorithmes peuvent être exprimées au moyen d'une fonctionnelle d'énergie commune, avec différents choix pour un paramètre q agissant en qualité d'exposant sur les différences entre les noeuds voisins. L'introduction d'un nouveau paramètre p qui fixe une puissance pour les poids des arêtes nous permet d'inclure également les lignes de partage des eaux en tant que forêts couvrantes optimales. Nous proposons alors une nouvelle famille d'algorithmes de segmentation, en fixant p pour produire une forêt couvrante optimale, mais en variant la puissance q ; nous obtenons ainsi des algorithmes de lignes de partage des eaux que nous appelons lignes de partages des eaux puissances ("power watersheds"). En particulier lorsque q = 2, ce nouvel algorithme conduit à une segmentation multilabels par ligne de partage des eaux, invariante par changement de contraste et d'échelle, qui est donnée par l'unique optimum global de la fonctionnelle d'énergie. Cet optimum est obtenu en pratique en un temps quasi-linéaire.

En nous plaçant dans ce cadre de minimisation d'énergie, nous ouvrons de nouvelles possibilités, d'une part pour la segmentation traditionnelle par ligne de partage des eaux (par exemple l'utilisation des termes unaires), et d'autre part, plus fondamentalement, pour l'optimisation de modèle généraux par ligne de partage des eaux.

Références:

[1] Jean Cousty, Gilles Bertrand, Laurent Najman, and Michel Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle.
IEEE Transactions on Pattern Analysis and Machine Intelligence. 31 (8).  August 2009. pp. 1362-1374.
http://www.esiee.fr/~info/a2si/Ps/flow_watershedPAMI.pdf

[2] Jean Cousty, Gilles Bertrand, Laurent Najman, and Michel Couprie. Watershed cuts: thinnings, shortest-path forests and topological watersheds.
IEEE Transactions on Pattern Analysis and Machine Intelligence.  To appear, 2010.
http://www.esiee.fr/~info/a2si/Ps/WatershedCutsPAMI-part2-full.pdf

[3]Camille Couprie, Leo Grady, Laurent Najman, and Hugues Talbot. Power watersheds: a new image segmentation framework extending graph cuts, random walker and optimal spanning forest.
12th International Conference on Computer Vision (ICCV'09).  September 2009. pp. 731-738.
http://www.esiee.fr/~najmanl/papers/couprie2009iccv.pdf