Segmentation en régions

Cette technique consiste à faire grossir simultanément toutes les régions jusqu'à ce que l'image soit entièrement segmentée.

Cette technique tire son nom d'une analogie avec la géophysique. On peut en effet considérer les valeurs d'intensité des pixels d'une image comme une information d'altitude. Dans ce cas on peut représenter cette image (appelée carte d'élévation) comme un terrain en 3 dimensions. Le principe est alors de remplir progressivement d'eau chaque bassin du terrain. Chaque bassin représente une région.

Lorsque l'eau monte et que deux bassins se rejoignent, la ligne de rencontre (i.e. la ligne de partage des eaux) est marquée comme une ligne de frontière entre 2 les régions.

L'algorithme se compose de deux étapes:

1. Générer une carte d'élévation à partir de l'image de départ
2. Remplir progressivement les bassins

Carte d'élévation (elevation map)

La carte d'élévation est une image dont les valeurs représentent une altitude. Pour construire cette image nous allons partir du gradient de l'image.

Dans la carte d'élévation, on assigne l'altitude la plus élevée (HMAX) aux pixels ayant un fort gradient ainsi qu'aux bords de l'image. Cela nous donne les lignes de crête.

La valeur d'altitude des autres pixels est calculée en fonction de l'éloignement de la ligne de crête : plus on s'éloigne de la ligne de crête, plus l'altitude doit décroître. La formule pour calculer la valeur d'altitude d'un pixel est donc :

Altitude(Pixel) = HMAX - distance(Pixel, ligne_de_crête)

Remarque : on peut calculer la distance entre un pixel et la ligne de crête en utilisant les masques de " Chamfer ".

Remplissage des bassins par infiltration (flooding)

Il existe de nombreux algorithmes permettant de réaliser le remplissage des bassins (cf " The Watershed Transform: Definitions, Algorithms and Parallelization Strategies " , Roerdink and Meijster, 2001 )

Nous détaillons ici un algorithme utilisant la technique de croissance de région vue précédemment. Dans cet algorithme, le remplissage des bassins est un procédé itératif qui consiste à élever progressivement le niveau de l'eau de zéro à HMAX. A chaque itération, on doit remplir les bassins existants (extension des régions) et éventuellement créer les nouveaux bassins (nouvelles régions).

Pour NIVEAU de 0 à HMAX 

	/*** Action 1 : Etendre les régions existantes ***/

	Pour chaque Région  « [R] » dans la liste « [Régions] »
		Faire croître « [R] »  jusqu'à l'altitude NIVEAU
	Fin Pour

	/*** Action 2 : créer les nouvelles régions ***/

	Pour chaque pixel « P » à l'altitude NIVEAU
		Si « P » n'est pas associé à une région Alors
			Créer une nouvelle région « [R]» dans la liste « [Régions] »
			Ajouter le pixel « P » dans la région « [R] »
			Faire croître « [R] » jusqu'à l'altitude NIVEAU
		Fin Si
	Fin Pour

Fin Pour