Search

Medical imaging is one of the most active research topics in image analysis. Analyzing and segmenting medical images in a clinical context remains a challenging task due to the multiplicity of imaging modalities and the variability of the patients characteristics and pathologies. Medical image processing also requires a human supervision for interpretation and validation purposes. The numerous applications and the huge amount of medical image data need complex software that combine high level graphical user interfaces as well as robust and fast interactive image analysis tools. Recent research in image segmentation has highlighted the potential of graph based methods for medical applications. These new tools have generated a great interest in the imaging community. Graph theory is the framework used in this thesis to propose innovative image segmentation tools. The focus of this thesis is both theoretical and practical. On the theoretical level, we study properties of minimal spanning trees, shortest paths trees and minimal cuts and we revisit these notions for image segmentation purposes. It allows us to derive new theoretical links between minimal spanning trees, shortest paths trees and minimal multi-terminal cuts. These results highlight the possibilities and the limitations of each technique for image segmentation problems. In a second step, we propose some theoretical and practical improvements of image segmentation based on graph cuts. This structure is particularly interesting for solving a fairly large variety of energy minimization problems. Our strategy is based on the use of the region adjacency graph produced by the watershed transform from mathematical morphology. The combination of morphological and graph cuts segmentation permits us to speed up and define new classes of energy functions that can be minimized using graph cuts. The use of region graphs gives promising results and can potentially become a leading method for interactive medical image segmentation. The third point of this thesis details some qualitative and quantitative studies of medical image segmentation problems, which is the initial motivation of this work. We show that the developed methods are well suited for various medical image segmentation problems. We study applications to surgery simulation, radiotherapy planning and tumors delineation. We show by a quantitative analysis that the combination of morphological and graph cuts segmentation methods outperforms several recent and state of the art tools. This study shows that our methods can be used in a clinical context. The last point of the thesis revisits and extends some classical graph based image segmentation tools. We revisit the well known watershed transform from the point of view of path optimization and path algebra. We recall existing properties of the watershed transform and propose some clear definitions of the watershed transform on graphs. Finally we also propose new extensions of the minimal graph cut problem for image segmentation purposes. New types of constraints are included in the classical minimal graph cut problem, which bring this standard problem into the linear programming framework. This class of combinatorial optimization problems is particulary interesting for image segmentation purposes since it provides a general framework for various constrained image segmentation problems such as boundary constrained minimal cuts and various geometric constrained minimal cuts. These new methods show great potential for various image segmentation scenarios.; La recherche en imagerie médicale est une des disciplines les plus actives du traitement d'images. La segmentation et l'analyse d'images dans un contexte clinique reste un problème majeur de l'imagerie médicale. La multiplicité des modalités d'imagerie, ainsi que les fortes variabilités des structures et pathologies à analyser rendent cette tâche fastidieuse. Dans la plupart des cas, la supervision de spécialistes, tels que des radiologistes, est nécessaire pour valider ou interpréter les résultats obtenus par analyse d'images. L'importante quantité de données, ainsi que les nombreuses applications liées à l'imagerie médicale, nécessitent des outils logiciels de très haut niveau combinant des interfaces graphique complexe avec des algorithmes interactifs rapides. Les récentes recherches en segmentation d'images ont montré l'intérêt des méthodes à base de graphes. L'intérêt suscité dans la communauté scientifique a permis de développer et d'utiliser rapidement ces techniques dans de nombreuses applications. Nous avons étudié les arbres de recouvrement minimaux, les coupes minimales ainsi que les arbres de chemins les plus courts. Notre étude a permis de mettre en lumière des liens entre ces structures a priori très différentes. Nous avons prouvé que les forêts des chemins les plus courts, ainsi que les coupes minimales convergent toutes les deux, en appliquant une transformation spécifique du graphe, vers une structure commune qui n'est autre qu'une forêt de recouvrement minimale. Cette étude nous a aussi permis de souligner les limitations et les possibilités de chacune de ces techniques pour la segmentation d'images. Dans un deuxième temps, nous avons proposé des avancées théoriques et pratiques sur l'utilisation des coupe minimales. Cette structure est particulièrement intéressante pour segmenter des images à partir de minimisation d'énergie. D'une part, nous avons montré que l'utilisation de graphes de régions d'une segmentation morphologique permet d'accélérer les méthodes de segmentation à base de coupe minimales. D'autre part nous avons montré que l'utilisation de graphes de régions permet d'étendre la classe d'énergie pouvant être minimisée par coupe de graphes. Ces techniques ont toutes les caractéristiques pour devenir des méthodes de référence pour la segmentation d'images médicales. Nous avons alors étudié qualitativement et quantitativement nos méthodes de segmentation à travers des applications médicales. Nous avons montré que nos méthodes sont particulièrement adaptées à la détection de tumeurs pour la planification de radiothérapie, ainsi que la création de modèles pour la simulation et la planification de chirurgie cardiaque. Nous avons aussi mené une étude quantitative sur la segmentation de tumeurs du foie. Cette étude montre que nos algorithmes offrent des résultats plus stables et plus précis que de nombreuses techniques de l'état de l'art. Nos outils ont aussi été comparés à des segmentations manuelles de radiologistes, prouvant que nos techniques sont adaptées à être utilisée en routine clinique. Nous avons aussi revisité une méthode classique de segmentation d'images : la ligne de partages des eaux. La contribution de notre travail se situe dans la re-définition claire de cette transformation dans le cas des graphes et des images multi spectrales. Nous avons utilisé les algèbres de chemins pour montrer que la ligne de partages des eaux correspond à des cas particuliers de forêt des chemins les plus courts dans un graphe. Finalement, nous proposons quelques extensions intéressantes du problème des coupes minimales. Ces extensions sont basées sur l'ajout de nouveaux types de contraintes. Nous considérons particulièrement les coupes minimales contraintes à inclure un ensemble prédéfini d'arêtes, ainsi que les coupes minimales contraintes par leur cardinalité et leur aires. Nous montrons comment ces problèmes peuvent être avantageusement utilisé pour la segmentation d'images.

We consider the following problem: given a labelled directed graph $G$ and a regular expression $R$, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies $R$. The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation of a query language, ${\bf G}^+$, based on this observation. We show that the problem is in general intractable, but present an algorithm than runs in polynomial time in the size of the graph when the regular expression and the graph are free of conflicts. We also present a class of languages whose expressions can always be evaluated in time polynomial in the size of both the graph and the expression, and characterize syntactically the expressions for such languages.