En morphologie mathématique, l'algorithme de la ligne de partage des eaux (LPE), proposé par Digabel et Lantuéjoul, est un algorithme de segmentation d'images, ce qui revient à décomposer une image en régions homogènes.

La ligne de partage des eaux utilise la description des images en termes géographiques. Une image peut en effet être perçue comme un relief si l'on associe le niveau de gris de chaque point à une altitude. Il est alors possible de définir la ligne de partage des eaux comme étant la crête formant la limite entre deux bassins versants.

Pour l'obtenir, il faut imaginer l'immersion d'un relief dans de l'eau, en précisant que l'eau ne peut pénétrer dans les vallées que par ses minima. La ligne de partage des eaux est représentée par les points où deux lacs disjoints se rejoignent au cours de l'immersion.

Il est à noter que la ligne de partage des eaux n'est pas locale. En particulier, elle n’est pas liée à des structures locales (lignes de crête, escarpement,…). La LPE n’est pas un concept LOCAL. Vous ne pouvez pas, avec la seule connaissance locale du voisinage d’un point, répondre à la question : Ce point appartient-il à une ligne de partage des eaux?

Une des difficultés à la mise en oeuvre de cette analogie intuitive est qu'elle laisse beaucoup de liberté quant à sa formalisation. Il existe deux classes principales d'implémentation : l'une est basée sur un algorithme récursif d'immersion [Vincent 91] et une autre basée sur l'utilisation de fonctions de distances géodésiques [Meyer 88]. Leur définition algorithmique ainsi que leur analyse critique est donnée dans l'article de Jos B.T.M. Roerdink et Arnold Meijster [Roerdink-Meijster 01]. Nous utiliserons par la suite la fonction intégrée à matlab et basée sur l'algorithme de Vincent - Soille.

Notons enfin que l'on n'applique pas la LPE à l'image originale mais à son gradient (morphologique). Cela créé ainsi des ligne de partage des eaux aux points de discontinuités du niveau de gris, ce qui est intéressant pour les applications de segmentation.

Observons maintenant le résultat de la LPE sur une image naturelle simple.

Illustration de la sur segmentation

La LPE du gradient est sur-segmentée, même si comme ici, l'image originale est homogène. Ceci est dû au fait que les images gradient des images naturelles contiennent un grand nombre de minima (dû au bruit du système de prise de vue par exemple ou à variations locales non significatives des niveaux de gris ou encore aux textures des régions). Chaque minimum génère un bassin versant dans la LPE.

Concernant la connexité, on peur envisager l'utilisation de la 4-connexité ou bien de la 8-connexité. Tout dépendra du type d'image et du type de traitement à effectuer. Dans le cadre de la ligne de partage des eaux on utilisera par défaut la 8-connexité.

Il existe plusieurs méthodes qui permettent de pallier à cette sur-segmentation.

• La première consiste à filtrer l'image originale afin de supprimer tous les minima non-significatifs : c'est l'approche filtrage.
• La deuxième consiste à choisir le nombre de minima locaux et donc le nombre de zones que l'on souhaite mettre en évidence grâce à la LPE : c'est l'approche marqueurs (swamping).
• Enfin une première LPE peut servir de marqueur pour une seconde, et la zone qu'elle délimite donne lieu à une image mosaïque. Cette image n'est plus construite par pixels, mais comme graphe planaire. Elle est susceptible à son tour d'être traité par LPE, filtrage, swamping, versions conditionnelles... C'est un processus itératif qui donne donc lieu à une segmentation hiérarchique.

Ceci correspond à un paradigme de segmentation c'est à dire la structure utilisée pour la segmentation à base de LPE. Elle autorise la combinaison des différentes méthodes de prétraitements suscitées.

 

Nous testerons l'efficacité des prétraitements sur 3 images photographiques : lena, afmsurf (J.C. Russ, The Image Processing Handbook, Third Edition, 1998), et l'image cell. Ci dessous les images originales (à gauche) avec le résultat de la LPE (à droite).

 

L'image de lena est une image riche de détails et de difficultés pour la segmentation : la faible différence de contraste du haut du chapeau, complexité des plumes. Néanmoins certaines de ces caractéristiques sont relativement faciles à extraire comme l'épaule par exemple. C'est une bonne image de test pour la segmentation.

 

L'image afmsurf est une image aux contours relativement précis mais flous, et qui surtout s'interceptent. La différence de contraste entre objets différents est variable dans l'image.

Cell est une image typique pour ce genre de segmentation : des cellules avec des niveaux de gris semblables et qui parfois se chevauchent, ce qui rend leur segmentation difficile. Elle se prête particulièrement aux méthodes utilisant la reconstruction de l'image à partir de marqueurs.