GDR Mathématiques des Systèmes Perceptifs et Cognitifs

Optimisation Discrète, Graph Cuts et Analyse d'Images

Le 29 Novembre 2005 de 9H à 18H –Salle Dussane, ENS Ulm comment s'y rendre

Organisateurs : Renaud KERIVEN et Laurent COHEN

FORMULAIRE D'INSCRIPTION ------------ LISTE DES INSCRITS

Programme de la journée

Résumés

Tutorial Coupes minimales: introduction et applications en vision et traitement d'images 
Transparents
Renaud Keriven, 
ENS/ENPC,
Dans cet exposé introductif, nous verrons comment, sous le vocable de
« graph-cuts », le problème des coupes minimales dans les graphes a
été adopté par les communautés du traitement d'images et de la vision
par ordinateur comme une méthode importante d'optimisation. Au travers
d'exemples, nous réaliserons à quel point elle a été largement
déclinée et en profiterons pour essayer de dresser un premier bilan de
ses avantages et de ses inconvénients.

Algorithms for MAP estimation in Markov Random Fields 
Transparents
Vladimir Kolmogorov
University College London, 

Résumé

I will review two techniques: (1) maxflow algorithm (a.k.a. graph cuts) for minimizing
submodular energy functions of binary variables, and (2) tree-reweighted message passing algorithm
for approximate minimization of arbitrary MRF energy functions. I will show that these techniques
have a lot in common: they both try to maximize a lower bound on the energy function.

Primal-dual Algorithm for Convex Markov Random Fields
Transparents
Vladimir Kolmogorov
University College London, 
Résumé 

I will present a fast maxflow-based algorithm for miminimizing a subclass of MRF energy functions,
namely functions whose unary and pairwise terms are convex.
For the panoramic image stitching problem the method outperforms other techniques. The paper is available at
http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=971

Surfaces minimales en pratiques

Transparents
Hugues Talbot & Ben Appleton

Récemment nous avons proposé un système simple d'EDP qui permettent de calculer numériquement des surfaces minimales globalement optimales en dimensions arbitraires, en utilisant une extension continue des méthodes de flots maximaux/coupures minimales. Dans cet exposé nous aborderons l'utilisation pratiques de cet algorithme.

Restauration d'image par optimisation exacte de Champs de Markov : 
Les cas de la variation totale, des énergies nivellées et convexes.
 Transparents
Jerome Darbon et Marc Sigelle
Ecole Nationale Supérieure des Télécommunications  
LTCI CNRS UMR 5141 - Dept. TSI (R. C218) 
46 rue Barrault 75634 Paris cedex 13 France
http://tsi.enst.fr/~sigelle/

 Nous présentons différentes approches par coupures minimales pour
 minimiser exactement des énergies markoviennes. Nous reformulons ces
 énergies avec des champs de Markov binaires associés à chaque
 ensemble de niveau d'une image. Nous commencons tout d'abord par
 traiter les modèles du type "convexe + variation totale".  Nous
 géneralisons ensuite cette approche aux cas des énergies dites
 "nivellées". Une seconde géneralisation, différente de la précédente,
 considère le cas ou les termes de regularisation sont
 convexes. Enfin, nous présentons un algorithme original et
 rapide pour le cas des modèles du type "convexe+convexe".
 Tous ces algorithmes calculent des minimiseurs exacts et les complexités
 de ces algorithmes sont présentées. Le tout est illustré par des
 expériences numériques.

ActiveCuts, un algorithme de GraphCut adapté à la Vision

Transparents

Olivier Juan

ENPC

Nous présenterons de nouveaux concepts afin d'améliorer l'efficacité des GraphCuts et les rendre plus appropries aux problèmes de visions.

La nouvelle méthode présentée peut ainsi tirer parti d'une bonne initialisation (Coupe initiale) qui est souvent disponible en vision (problèmes dynamiques, hiérarchiques ou a plusieurs labels).

Dans beaucoup de problèmes, notre algorithme est plus rapide que celui de Boykov-Kolmogorov même dans le cas d'une initialisation éloignée du minimum global. Cependant une initialisation proche améliore grandement la vitesse de convergence.

De plus au cours de l'exécution, notre algorithme extrait une succession de coupes intermédiaires (a cout décroissant), qui peuvent être utilisées pour affiner et accélérer des méthodes itératives. Enfin notre algorithme peut être combiné à d’autres méthodes d’accélération de GraphCut.

TITRE 
Prenom NOM 
Laboratoire 
Institut
Adresse 
Résumé 

TITRE 
Prenom NOM 
Laboratoire 
Institut
Adresse 
Résumé