Ligne de partage des eaux (segmentation)

Ligne de partage des eaux

Représentation du principe de l’algorithme : considérer l'image comme un relief.

Type	Algorithme de segmentation d'image
Sigle	LPE
Surnom	Watershed (en)
Inventeur	Serge Beucher et Christian Lantuéjou
Date d'invention	1979
Nommé en référence à	Ligne de partage des eaux en géographie

En traitement d'images, la segmentation par ligne de partage des eaux désigne une famille de méthodes de segmentation d'image issues de la morphologie mathématique qui considèrent une image à niveaux de gris comme un relief topographique, dont on simule l’inondation.

Principe de base

L'idée de base derrière toutes les méthodes de segmentation basées sur la ligne de partage des eaux est de considérer une image à niveaux de gris comme un relief topographique. Il s'agit alors de calculer la ligne de partage des eaux dudit relief. Les bassins versants ainsi obtenus correspondent aux régions de la partition.

Si on considère l'image à niveaux de gris comme une fonction de $\mathbb {R} ^{2}$ dans $\mathbb {R}$ suffisamment régulière, on peut alors définir proprement la ligne de partage des eaux. Cependant, dans le cas discret (fonctions de $\mathbb {Z} ^{2}$ dans $\mathbb {Z}$), qui correspond mieux aux images considérées, il n'existe pas à ce jour de définition consensuelle de cette transformation. Plusieurs algorithmes ont été proposés pour la calculer, donnant autant de définitions, pas toujours équivalentes.

On peut classer les algorithmes de construction de la ligne de partage des eaux en trois catégories. Les algorithmes par inondation simulent une montée progressive du niveau d'eau à partir des minima du relief. Les algorithmes par ruissellement suivent, à partir de chaque pixel de l'image, la ligne de plus grande pente jusqu'à atteindre un minimum. Finalement, les algorithmes topologiques proposent une déformation progressive du relief, préservant certaines caractéristiques topologiques, jusqu'à ce qu'il soit réduit à une structure fine correspondant à la ligne de partage des eaux.

• 
  Image initiale en niveaux de gris.
• 
  Une représentation en 3D de l'image initiale.
• 
  Une segmentation de l'image initiale.
• 
  Une représentation en 3D de la segmentation de l'image initiale.

Inondation

Toutes images en niveau de gris peuvent être considérées comme une surface topographique. La montée des eaux consiste à immerger la surface topographique dans de l'eau. À chaque fois que la hauteur des eaux atteint la hauteur d'un label, un nouveau bassin versant est créé dont la couleur est celle du label. À chaque fois que deux bassins de couleurs différentes se rencontrent, on empêche leur fusion en créant une digue, nommée ligne de partage des eaux. En revanche si les deux bassins sont de même couleur, ils fusionnent.

Complexité

Les algorithmes de calcul de la ligne de partage des eaux les plus efficaces ont une complexité qui dépend linéairement du nombre de pixels de l'image, ce qui les classe parmi les méthodes de segmentation les plus rapides. Cela les rend particulièrement attrayants dans des applications traitant des images de grande taille, telles que les images à trois dimensions.

Utilisation

En pratique, un algorithme de ligne de partage des eaux n'est que rarement appliqué directement à l'image originale. On commence classiquement par une étape de filtrage, puis — étape essentielle — on procède au calcul d'un gradient ou, plus généralement, au calcul d'une image indiquant les zones de transition qu'on cherche à détecter. On peut pour cela utiliser le module du gradient euclidien, un gradient morphologique, un gradient couleur, ou toute autre méthode adaptée. Le calcul de la ligne de partage des eaux n'est alors que la dernière étape de la procédure de segmentation.

On est souvent confronté à un problème de sur-segmentation lorsqu'on utilise une ligne de partage des eaux : on obtient alors bien plus de régions que souhaité. Plusieurs stratégies sont envisageables pour résoudre ce problème, telles que : un filtrage adapté ; le choix de marqueurs indiquant les sources de l'inondation ; ou l'utilisation d'une approche hiérarchique.

Une application industrielle de la segmentation par la ligne de partage des eaux est la détection automatique de motifs sur une surface . C'est une technique d'analyse de l'état de surface développée dans la norme ISO 25178. La segmentation, alliée à une technique de réduction de la complexité d'un arbre codant les relations entre les points topologiques, permet de ne retenir que les points significatifs jouant un rôle prépondérant dans une fonction mécanique (lubrification, étanchéité, contact).

Bibliographie

• Serge Beucher et Christian Lantuéjoul. Use of watersheds in contour detection. Dans International workshop on image processing, real-time edge and motion detection (1979).

• Serge Beucher et Fernand Meyer. The morphological approach to segmentation: the watershed transformation. Dans Mathematical Morphology in Image Processing (Ed. E.R. Dougherty), pages 433-481 (1993).

• Fernand Meyer. Un algorithme optimal pour la ligne de partage des eaux. Dans 8^e congrès de reconnaissance des formes et intelligence artificielle, Vol. 2 (1991), pages 847-857, Lyon, France.

• Luc Vincent et Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations, dans IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583-598.

• L. Najman et M. Schmitt. Watershed of a continuous function. Dans Signal Processing (Special issue on Mathematical Morphology.), Vol. 38 (1994), pages 99-112.

• L. Najman et M. Schmitt. Geodesic saliency of watershed contours and hierarchical segmentation. Dans IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, Num. 12 (1996), pages 1163-1173.

• J.B.T.M. Roerdink et A. Meijster. The watershed transform: definitions, algorithms, and parallellization strategies. Dans Fundamenta Informaticae 41 (2000), p. 187-228.

• Laurent Najman, Michel Couprie et Gilles Bertrand. Watersheds, mosaics, and the emergence paradigm. Dans Discrete Applied Mathematics, Vol. 147, Num. 2-3(2005), Pages 301-324.

Voir aussi

Article connexe

• Méthode des surfaces de niveau

Liens externes

• Introduction à la ligne de partage des eaux (en Anglais)
• Ligne de Partage des Eaux Topologique avec articles, présentations et code source (en Anglais et Français)
• Population un logiciel simple et libre d'utilisation pour se familiariser avec le traitement d'image contenant l'algorithme d'immersion