Quand: le mardi 29 mai 2018, à 14h00
Où: en salle G08, à Télécom SudParis (Evry)
Titre :Power Watershed, ou la ligne de partage des eaux revisitée: vers l’infini, et au delà.
Résumé :
La ligne de partage des eaux (watershed) est un outil issue de la morphologie mathématique, originellement utilisée pour la segmentation d’images. Ces dernières années, nous avons proposé un cadre rigoureux pour la définir, avec des algorithmes efficaces implémentant les définitions, permettant des applications non seulement sur des images, mais aussi en classification et en clustering de données générales, par exemple en exploitant conjointement des réseaux convolutionnels.
Dans cet exposé, nous nous focaliserons sur un théorème d’équivalence [4] de la ligne de partage des eaux avec les arbres de poids minimum. Une extension récente (appelée PowerWatershed) de ce résultat repose sur la Gamma-convergence, pour un certain type de fonctionnelles énergétiques [1]. Cette extension permet de combiner de manière rigoureuse les optimisations de type arbre de poids minimum avec d’autres types d’optimisation, comme les marches aléatoires ou le clustering spectral.
Il est connu que les arbres de poids minimum proposent une façon efficace de faire du clustering, mais que ces algorithmes sont sujets à des fuites (effet de chaine). De plus, il n’est pas possible d’imposer de contrainte (par exemple de régularité) sur le bord des clusters. L’idée intuitive de nos principaux résultats est de calculer un arbre de poids minimum aux endroits faciles, c’est à dire le centre des clusters, et d’appliquer un algorithme plus évolué sur un « bord étendu », afin d’imposer des contraintes. Cette idée est similaire à ce qui se fait en pratique quand la taille des données est grande: dans de tels cas, on commence souvent par réduire la taille des données avec un premier algorithme de clustering, comme par exemple un arbre de poids minimum. Un regard différent sur notre proposition est donc le suivant: en nous reposant sur des principes fondamentaux, nous introduisons une théorie et des algorithmes pour combiner la réduction de données et le clustering ou la classification par optimisation. Nous illustrerons cette théorie avec des applications, notamment en segmentation d’images et de données (marcheur aléatoire) [2] et en clustering spectral [3].
Bibliographie:
[1] Laurent Najman. Extending the PowerWatershed framework thanks to G-convergence. SIAM Journal on Imagine Sciences, 2017.
[2] Camille Couprie, Leo Grady, Laurent Najman, Hugues Talbot. Power Watersheds: A Unifying Graph Based Optimization Framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2011, 33 (7), pp.1384-1399. <10.1109/TPAMI.2010.200>.
[3] Aditya Challa, Sravan Danda, B S Daya Sagar, Laurent Najman. Power Spectral Clustering. 2018.
[4] Jean Cousty, Gilles Bertrand, Laurent Najman, Michel Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2009, 31 (8), pp.1362-1374.
Biographie :
Laurent Najman a obtenu un diplôme d’ingénieur de l’Ecole des Mines de Paris en 1991, un doctorat en mathématiques appliquées de l’Université Paris-Dauphine en 1994 avec les félicitations du Jury, et l’Habilitation à Diriger les Recherches de l’Université de Marne-La-Vallée en 2006. Il a travaillé pour le Laboratoire Central de Recherche de Thomson-CSF pendant trois ans sur des problèmes de segmentation d’images infrarouges. En 1995, il a rejoint une start-up nommée Animation Science en tant que directeur de la recherche et le développement. La technologie des systèmes de particules pour l’informatique graphique et la visualisation scientifique, développée par la société sous sa direction technique, a reçu plusieurs récompenses, dont le «Prix européen de technologie de l’information 1997» décerné par la Commission européenne (programme Esprit) et le Conseil européen des sciences appliquées et de l’ingénierie, et l’un des « Hottest Products of the Year 1996 » décerné par le journal Computer Graphics World. En 1998, il rejoint Océ Print Logic Technologies en tant que chercheur-senior. Il y a travaillé sur divers problèmes d’analyse d’images pour la numérisation et l’impression. En 2002, il rejoint le département informatique de l’ESIEE Paris, où il est professeur et membre du Laboratoire d’Informatique Gaspard-Monge, Université Paris-Est.