Lignes de partage des eaux discrètes : théorie et application à la segmentation d'images cardiaque
Directeur de thèse : Laurent Najman

Laboratoires impliqués:
(1) Fédération de Cardiologie, Hopital Henri-Mondor, Créteil.
(2) Laboratoire A2SI, Groupe ESIEE
(3) Iinstitut Gaspard-Monge, Université de Marne-la-Vallée

Télécharger le manuscrit

Résumé

Pour son intérêt en topographie, son utilité dans la gestion des ressources et son importance comme barrière géopolitique, la ligne de partage des eaux (LPE) est étudiée dès le 19ème siècle par Maxwell et Jordan. Un siècle plus tard, elle est introduite par Digabel et Lantuéjoul comme une étape fondamentale pour la segmentation d'images en morphologie mathématique. Cette thèse s'intéresse aux aspects théoriques de la LPE dans les espaces discrets et à son application pour l'analyse d'images cardiaques spatio-temporelles.

Classification de quelques approches discrètes de ligne de partage de eaux

Le premier chapitre de cette thèse présente quatre approches de la LPE qui sont parmi les plus populaires en analyse d'images : LPE par inondation, topographique, inter-pixel (par inondation) et topologique. Chacune d'elles cherche à vérifier une propriété ou une autre dérivée d'idées intuitives provenant de la topographie. Nous classifions ces méthodes en fonction de cinq propriétés qui correspondent à l'une ou l'autre de ces idées intuitives: aucune de ces méthodes ne satisfait les cinq propriétés. Cela pose donc la problématique théorique de la thèse : l'existence d'une notion de LPE vérifiant cet ensemble de propriétés.

Graphes de fusion : clivages et propriétés de la fusion de régions

Les méthodes de fusion de régions utilisées en analyse d'images améliorent une segmentation initiale (obtenue, par exemple, par LPE) en fusionnant des paires de régions voisines. Nous considérons une segmentation comme un ensemble de régions connexes séparées par une frontière. Si l'ensemble frontière ne peut pas être réduit sans fusionner deux régions, nous disons alors qu'il s'agit d'un clivage.
Dans un cadre général de graphes, certaines configurations de points ne permettent pas de fusionner deux et uniquement deux régions. Nous définissons quatre classes de graphes de fusion dans lesquels les situations problématiques sont peu à peu supprimées. L'un des résultats principaux est que l'une de ces classes est celle dans laquelle tout clivage est mince. Nous donnons des caractérisations locales de deux de ces classes de graphes et prouvons que les deux autres ne peuvent pas être caractérisées localement.
Aucune des relations d'adjacence usuelles employées pour analyser des images bidimensionnelles et tridimensionnelles ne vérifie des propriétés de fusion satisfaisantes. Nous introduisons la grille de fusion parfaite pour Z^n, c'est à dire pour les images digitales de dimension quelconque. Il s'agit d'un graphe régulier dans lequel deux régions voisines peuvent toujours être fusionnées en supprimant de l'ensemble frontière les points adjacents aux deux régions.

Graphes de fusion pondérés : lignes de partage des eaux et fusion de régions

Nous étendons les propriétés des graphes de fusion aux cas des graphes à sommets pondérés. La notion de LPE topologique étend celle de clivage au cas des fonctions de pondération. En fait, elle fournit une définition en termes rigoureux de la notion de LPE d'un graphe à sommets pondérés et permet de prouver des propriétés importantes qui ne sont pas garanties par la plupart des algorithmes de LPE.
Nous étendons la notion de minceur ensembliste aux fonctions et étudions la classe des graphes dans lesquels toute LPE topologique est une fonction mince. Nous exhibons une caractérisation de cette classe et montrons les liens forts entre minceur des LPE topologiques et les classes de graphes de fusion.
Nous étudions les LPE dans les graphes de fusion parfaits. Nous proposons un algorithme d'immersion monotone et démontrons sa justesse alors qu'en général un tel algorithme n'existe pas. L'avantage principal est de réduire à un temps linéaire la complexité pour calculer des séparations correspondant à des LPE topologiques. Contrairement au cas général, dans ce cadre de travail, les séparations obtenues par LPE topologiques sont toujours des clivages minces. Les graphes de fusion parfaits, constituent donc un premier cadre de travail (adapté, entre autre, aux procédures de fusion de régions) dans lequel les LPE vérifient un jeu de propriétés mathématiques remarquables.
Grâce à la notion de graphe d'arêtes, un concept classique en théorie des graphes, les propriétés des graphes de fusion parfaits s'étendent aux graphes à arêtes pondérées.

Ligne de partage des eaux dans les graphes à arêtes pondérées

Nous étudions en profondeur les LPE dans les graphes a arêtes pondérées. Elles peuvent y être définies en suivant l'idée de gouttes d'eau s'écoulant sur un relief topographique. La consistance de ce cadre de travail est établie : les LPE peuvent y être caractérisées aussi bien par leurs bassins d'attraction (régions) à travers une propriété de plus grande pente que par les lignes qui les séparent (bord) à travers le principe de la goutte d'eau. Ensuite, nous établissons, par un théorème d'équivalence, l'optimalité (en termes de forêt couvrante de poids minimum) de ces LPE. Finalement, nous montrons les liens mathématiques avec les forêts de plus courts chemins et les LPE topologiques. A notre connaissance, aucune autre approche discrète de LPE ne vérifie toutes ces propriétés.
Afin de calculer ces LPE, nous introduisons une transformation d'amincissement qui consiste à abaisser la valeur de certaines arêtes qui satisfont une propriété simple qui peut être testée localement. Nous montrons que cette transformation permet d'obtenir une LPE et, plus remarquablement, que toute LPE peut être obtenue par cette transformation. Nous dérivons deux algorithmes linéaires qui sont, à notre connaissance, les plus efficaces - en théorie et en pratique - parmi les stratégies existantes de calcul de LPE.
Finalement, nous présentons quelques illustrations en segmentation d'images qui montrent que l'approche proposée peut s'avérer plus précise que celle dans les graphes à sommets pondérés.

Segmentation d'images cardiaques spatio-temporelles

Reposant sur la LPE dans un graphe (4D) à arêtes pondérées et sur des opérateurs classiques de la morphologie mathématique, nous développons un logiciel pour segmenter automatiquement le myocarde ventriculaire gauche dans des images 4D (3D+t) par résonance magnétique de type ciné.
Grâce à la comparaison avec des segmentations manuelles effectuées par deux cardiologues, nous démontrons la précision des contours obtenus automatiquement. Sur 18 patients la distance moyenne entre surfaces extraites automatiquement et manuellement est égale à 1.42 +- 0.36 mm et 1.55 +- 0.23 mm pour respectivement les frontières endocardiques et epicardiques. Pour chaque contour, cela correspond à un déplacement moyen inférieur à la taille d'un voxel. La fraction d'éjection (FE) et la masse myocardique (MM), deux paramètres critiques dans les diagnostics cardiaques, peuvent être dérivées des segmentations. L'analyse statistique démontre une bonne corrélation (0.98 et 0.99 pour respectivement la FE et la MM) entre les paramètres dérivés des segmentations automatiques et ceux dérivés des segmentations manuelles.
Pour mettre en avant le gain obtenu grâce à la méthode 4D, nous comparons ces résultats à une variante utilisant uniquement des LPE 3D (une par image 3D). Nous démontrons ainsi que la procédure 4D proposée permet de maintenir la cohérence temporelle entre les segmentations successives au cours du cycle cardiaque.