View
105
Download
0
Category
Preview:
Citation preview
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.
Recommended