Segmentation deux Segmentation deux classes interactiveclasses interactive
ParPar
Francis BrissetteFrancis BrissetteGuillaume ComeauGuillaume Comeau
Université de SherbrookeUniversité de Sherbrooke3 décembre 20073 décembre 2007
Plan de la présentationPlan de la présentation
► Mise en contexte du projet
► Les méthodes implémentées
► Perspectives
► Conclusion et remerciements
Mise en contexte du projetMise en contexte du projet
► Consiste à regrouper dans une même classe tous les pixels d'une image possédant une ou plusieurs caractéristiques communes.
► Dans une segmentation deux classes, l'image est partitionnée en deux classes, le résultat pouvant être représentée par une image binaire.
Segmentationdeux classes
Qu’est-ce que la Qu’est-ce que la segmentation ?segmentation ?
Les objectifs du projetLes objectifs du projet
► Réaliser un programme simple permettant la segmentation deux classes d'images en niveaux de gris à l'aide de différentes méthodes.
► Permettre la segmentation de plusieurs images reliées sémantiquement, soit par la coupe en tranches d'un objet 3D, soit par le mouvement d'un objet dans l'espace.
► Réaliser l’interface graphique du programme à l'aide de la bibliothèque Qt.
Les méthodes implémentéesLes méthodes implémentées
La méthode du seuilLa méthode du seuil
► Classe tous les pixels ayant une intensité inférieure au seuil dans la classe« arrière-plan » et les autres pixels dans la classe « objet ».
► Trivial à implémenter.
La méthode du seuilLa méthode du seuil
La méthode du seuil La méthode du seuil optimaloptimal
► Version non supervisée de la méthode du seuil.
► Représente l’histogramme de l’image par une mixture de gaussiennes, chaque gaussienne conceptualisant une classe.
► Vérifie, pour une intensité donnée, quelle gaussienne est la plus probable.
► Algorithmes itératifs d’estimation des paramètres des gaussiennes : K-Means ;
Soft K-Means ;
Expectation-Maximization (EM).
La méthode du seuil La méthode du seuil optimaloptimal
La méthode de la La méthode de la baguette baguette magiquemagique
► Utilisateur doit choisir un pixel source ainsi qu’une valeur de tolérance.
► Utilise un algorithme de remplissage par diffusion (Flood Fill ).
La méthode de la La méthode de la baguette baguette magiquemagique
La méthode La méthode ICMICM
► Utilise une approche markovienne : considère l’intensité du pixel courant ainsi que son voisinage. Algorithme itératif.
► Cherche à minimiser l’énergie globale de la segmentation.
► U(xs ,ys ) : terme de vraisemblance : détermine à quelle classe devrait appartenir le pixel courant selon son intensité.
► W(xs ,ys ) : terme d’a priori : détermine à quelle classe devrait appartenir le pixel courant afin qu’il soit cohérant avec son voisinage.
Ss
sssx
xWyxUx ,minargˆ
s
s
sx
xsxss
yyxU
2
2
22ln,
sinon 0
si1,où ,1 tsts
ttss
xxxxxxxW
s
La méthode La méthode ICMICM
La méthode La méthode Graph CutGraph Cut► Utilise également une approche markovienne, mais via un graphe non
orienté.
► Cherche à minimiser la même fonction d’énergie globale, avec les mêmes termes de vraisemblance et d’a priori que la méthode ICM.
► L’image à segmenter est convertie en graphe où chaque pixel est représenté par un nœud intermédiaire. Il y a également deux nœuds terminaux, un pour chaque classe. Les liens possèdent tous un poids.
► Liens entre les nœuds intermédiaires et lesnœuds terminaux : terme de vraisemblance.
► Liens entre les nœuds intermédiaires : terme d’a priori.
► L’algorithme sépare le graphe en deux sections,chacune d'elle devant contenir un nœud terminal.
Y. Boykov, V. Kolmogorov
La méthode La méthode Graph CutGraph Cut
La méthode de Boykov-JollyLa méthode de Boykov-Jolly
► Segmentation interactive.
► Récupère l’approche de la méthode Graph Cut, mais en supportant le concept de contraintes dures spécifiées par l’utilisateur.
► L’utilisateur spécifie des régions dans l’image qu’il veut absolument voir appartenir à la classe « objet » et à la classe « arrière-plan ». Consiste à modifier le poids des liens entre les nœuds intermédiaires et
les nœuds terminaux dans le graphe.
► Sous-méthodes : Basée sur les régions (à l’aide des paramètres des gaussiennes);
Basée sur les régions (à l’aide des histogrammes des classes);
Basée sur les contours.
La méthode de Boykov-JollyLa méthode de Boykov-Jolly
La segmentation 3DLa segmentation 3D
► Récupère l’approche de la méthode Graph Cut.
► Peut être appliquée à la méthode Graph Cut et à la méthode de Boykov-Jolly.
► Consiste à segmenter d’un seul coup plusieurs images reliées sémantiquement, soit par la coupe en tranches d'un objet 3D, soit par le mouvement d'un objet dans l'espace.
► Conceptuellement, la seule différence réside endes liens supplémentaires entre les nœudsintermédiaires des différents étages (images) du graphe.
Y. Boykov, V. Kolmogorov
La segmentation 3DLa segmentation 3D
Segmentation multi-images
PerspectivesPerspectives► Ajouter la reconstruction d’un modèle 3D à l’aide d’OpenGL.
► Permettre un plus grand voisinage dans le graphe(présentement seulement 4 voisins).
► Permettre une segmentation multi-images en 4D (non seulement en 3D).
► Optimiser l’algorithme du Graph Cut lors de l’ajout de contraintes dures spécifiées par l’utilisateur.
► Implémenter l’algorithme du Graph Cut. Présentement, il y a une fuite de mémoire lorsque nous réalisons une segmentation multi-images.
► Ajouter des fonctionnalités dans l’interface graphique : Inversion du résultat de la segmentation.
Outil « Efface » pour la méthode Boykov-Jolly.
Conclusion et remerciementsConclusion et remerciements► Lorsqu’une méthode demande peu ou pas d’interaction de la part de
l’utilisateur, la segmentation ne sera efficace que pour des images peu complexe (ex: objet blanc sur fond noir).
► La méthode de Boykov-Jolly demande une grande interaction avec l’utilisateur, mais donne des résultats très surprenant peu importe la complexité de l’image.
► Nous avons atteints tous les objectifs du projet tout en s’amusant.
► La bibliothèque Qt est fiable, robuste et complète, ce qui nous a énormément simplifié la vie.
► Un remerciement particulier pour le professeur Pierre-Marc Jodoin, sans qui ce projet n’aurait pas eu lieu.
RéférencesRéférences► P.-M. Jodoin. « Chapitre 2 : Segmentation 2D », Cours IMN 559, Vision par ordinateur, [En ligne],
http ://www.dmi.usherb.ca/ jodoin/cours/imn559/ (Page consultée le 27 novembre 2007).
► Y. Boykov, O. Veksler and R. Zabih. « Fast Approximate Energy Minimization via Graph Cuts », in IEEE transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 23, no. 11, pp. 1222-1239, November 2001.
► V. Kolmogorov and R. Zabih. « What energy functions can be minimized via graph cuts ? », in IEEE transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 2, pp. 147-159, February 2004.
► Y. Boykov and V. Kolmogorov. « An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision », in IEEE transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 26, no. 9, pp. 1124-1137, September 2004.
► O. Veskler. « Code for Energy Minimization with Graph Cuts », Olga Veksler, [En ligne],http ://www.csd.uwo.ca/faculty/olga/ (Page consultée le 19 novembre 2007).
► Y. Boykov and M.-P. Jolly. « Interactive organ segmentation using graph cuts », in Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp. 276-286, 2000.
► Y. Boykov and M.-P. Jolly. « Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D images », in International Conference on Computer Vision (ICCV), vol. I, pp. 105-112, July 2001.