Lignes de partage des eaux discrètes : théorie et application à la segmentation d'images cardiaques

The notion of a cleft models a frontier in a graph. Merging two regions, as requested by some image segmentation methods, is not straightforward. We introduce four classes of (fusion) graphs in which these difficulties are progressively avoided. We show that one of these classes is the one in which any cleft is thin. We introduce an adjacency relation, called perfect fusion grid, in which any two neighboring regions can be merged while preserving all other regions.The notion of a topological watershed (TW), used for image segmentation, extend the one of a cleft to vertex-weighted graphs. We extend the properties of clefts in fusion graphs to the case of maps and give a monotone linear-time watershed algorithm on perfect fusion grids. Thanks to line graphs, the properties of TWs in perfect fusion grids are extended to edge-weighted graphs.We investigate in depth the watersheds in edge-weighted graphs. The watersheds can be defned following the intuitive idea of drops of water flowing on a topographic surface. We establish both watershed consistency and optimality. We propose two linear-time algorithmswhich are, to the best of our knowledge, the most efficient watershed algorithms.Based on these results, we develop a software to automatically segment the left ventricular myocardium in 3D+t MR images. Quantitative and qualitative evaluations, based on the comparison with hand-made expert segmentations, assess the quality of the obtained segmentations.La notion de clivage formalise l'idée d'ensemble frontiére dans un graphe. Fusionner deux régions, comme le requièrent certaines méthodes de segmentation d'images, pose des diffIcultés. Nous introduisons quatre classes de graphes (de fusion) dans lesquels ces diffIcultés sont progressivement supprimées. Nous montrons que l'une de ces classes est celle pour laquelle tout clivage est mince. Nous introduisons une relation d'adjacence, appelée grille de fusion parfaite, dans laquelle deux régions voisines peuvent être fusionnées, en préservant toutes les autres régions.La ligne de partage des eaux topologique (LPE) étend la notion de clivage aux graphes dont les sommets sont valués et permet de segmenter une image. Nous étendons les propriétés des clivages dans les graphes de fusion aux cas des fonctions et proposons un algorithme de LPEmonotone et linéaire dans les grilles de fusion parfaites. Grâce à la notion de graphe d'arêtes, les propriétés des LPE dans les grilles de fusion parfaites s'étendent aux graphes à arêtes valuées.Nous étudions en profondeur les LPE dans les graphes à arêtes valuées. Les LPE peuvent y être définies en suivant l'idée intuitive de gouttes d'eau s'écoulant sur un relief topographique. Nous établissons aussi bien la consistance que l'optimalité de cette définition. De plus, nous proposons deux algorithmes linéaires qui, à notre connaissance, sont les plus efficaces pour le calcul des LPE.En nous reposant sur ces résultats théoriques, nous proposons une méthode et développons un logiciel pour la segmentation du ventricule gauche dans des images cardiaques 3D+t par résonance magnétique. La méthode est quantitativement et qualitativement validée par comparaison avec des segmentations manuelles tracées par deux experts cardiologues