Mathematical morphology and graphs: application to interactive medical image segmentation

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.