Ligne de partage des eaux

Figure: Les lignes de partage des eaux en France.

Introduction

La ligne de partage des eaux (LPE) est une notion qui apparaît dès le XIX$^{\mbox{ème}}$ siècle avec, notamment, les travaux de J. C. Maxwell. Un siècle plus tard, elle a été introduite par S. Beucher et C. Lantuéjoul pour la segmentation d'image. Elle constitue désormais l'un des principaux concepts de la Morphologie Mathématique et, dans ce cadre, elle est considérée comme un des opérateurs les plus puissants permettant de segmenter une image. Par exemple, une procédure typique en morphologie mathématique comprend une étape de filtrage de l'image, la détection des contours (gradient), le calcul de la LPE et un post-processing.

Écoulement

Une présentation intuitive de la LPE provient de la topographie. Une image en niveau de gris peut être considérée comme un relief topographique : le niveau de gris de chaque pixel dans l'image est interprété comme son altitude dans le relief topographique (voir Figure b,d). Les bassins et vallées correspondent aux zones sombres de l'image alors que les montagnes et les lignes de crêtes correspondent aux zones claires. Une goûte d'eau tombant sur ce relief suit un chemin descendant jusqu'à atteindre un minimum régional. Les lignes de partage des eaux correspondent aux limites des domaines d'attraction des goûtes d'eau. Dans le cas général cette présentation ne permet pas de dériver des algorithmes efficaces.

Immersion

Une présentation alternative de la LPE, populaire dans la communauté morphologique, est basée sur le paradigme d'immersion : considérons maintenant que la surface du relief est percée d'un trou dans chaque minimum de l'image. Imaginons ensuite que cette surface percée est peu à peu plongé dans un lac. L'eau pénètrent à travers les trous en commençant par immerger les minima. Aux endroits où des eaux provenues de différents minima se rencontrent, des barrages sont érigés. Une fois le relief complètement immergé la surface est partitionnée en régions séparées par des barrages, appelés ligne de partage des eaux. Des algorithmes efficaces pour simuler ce processus sont proposés dans la littérature. Malheureusement les résultats produits ne sont pas toujours satisfaisants.

Ravinement

Une approche originale de la ligne de partage des eaux, appelée LPE topologique, a été proposée par Michel Couprie et Gilles Bertrand. Intuitivement, elle consiste à raviner le relief topographique tout en préservant certaines propriétés topologiques. Lorsqu'un tel processus de ravinement est poussé à l'extrême, les seules crêtes persistantes correspondent aux LPE du relief (voir Figure ). L'avantage de cette approche est qu'elle permet une définition précise de LPE dans le cadre de la théorie des graphes. Cette définition purement discrète est donc bien adaptée aux images digitales. Elle permet d'étudier précisément les propriétés des lignes de partage des eaux. On peut notamment montrer, que la LPE topologique est la seule méthode permettant de préserver une notion de contraste entre les différentes régions de l'image. Dans ce cas, le contraste est défini comme l'altitude minimum à laquelle on est obligé de monter pour aller d'une région à l'autre. Les autres approches présentées ci-dessus ne possèdent pas cette propriété de préservation du contraste. Pour plus de détail sur la LPE topologique, vous pouvez consulter la bibliographie du laboratoire A2SI.

Figure: $(a)$ Une image extraite d'une séquence d'IRM cardiaque;
$(b)$ gradient de $(a)$;
$(c)$ LPE topologique de $(b)$;
$(d)$ relief topographique associé à $(b)$;
$(e)$ relief topographique associé à $(c)$;
$(f)$ crêtes extraites de $(c)$ et $(e)$.