Segmentation en régions

Cette technique consiste à faire progressivement grossir les régions autour de leur point de départ.

L'algorithme se compose de deux étapes:

1. Trouver les points de départ des régions
2. Faire grossir les régions par agglomérations des pixels voisins

Points de départ (seeds)

Le choix des points de départ est l'étape est la partie critique de l'algorithme. En effet, l'étape de croissance va utiliser une mesure de similarité pour choisir les pixels agglomérer. Si le point de départ est situé dans une zone non homogène, la mesure de similarité va produire de fortes variations et la croissance va s'arrêter très tôt.

Par conséquent, il convient de choisir les points de départs dans des zones les plus homogènes possibles.

Pour trouver ces zones, on peut réutiliser le principe de décomposition utilisé dans l'algorithme split/merge. Comme la décomposition finale nous donne une liste de blocs homogènes, il suffit de choisir le centre des plus gros blocs pour avoir de bons points de départ.

Croissance (growing)

Cette étape à pour objectif de faire grossir une région en agglomérant des pixels voisins. Les pixels sont choisis afin de maintenir l'homogénéité de la région. Pour cela, nous devons définir un indicateur d'homogénéité. Les pixels voisins sont ajoutés à la région si l'indicateur d'homogénéité reste vrai. La croissance s'arrête lorsqu'on ne peut plus ajouter de pixels sans briser l'homogénéité.

L'algorithme de la croissance est un procédé itératif:

Créer la liste « [S] » des points de départs (triée pour avoir le centre des plus gros blocs d'abord)

Pour chaque pixel « P » dans la liste « [S] » 

	Si le pixel « P » est déjà associé à une région, alors prendre le pixel « P » suivant dans la liste « [S] »
	Créer une nouvelle région « [R] »
	Ajouter le pixel « P »  dans la région  « [R] »
	Calculer la valeur/couleur moyenne de « [R] »

	Créer la liste « [N] » des pixels voisins du pixel « P » 

	Pour chaque pixel « Pn » dans la liste « [N] »
		Si (« Pn » n'est pas associé à une région  ET  « R + Pn » est homogène) Alors
			Ajouter le pixel « Pn » dans la région « [R] »
			Ajouter les pixels voisins de « Pn » dans la liste « [N] »
			Recalculer la valeur/couleur moyenne de « [R] »
		Fin Si
	Fin Pour

Fin Pour

L'indicateur d'homogénéité peut être construit à partir des mesures de similarité.

Indicateur :    " vrai "  si Homogénéite( R ) <= SEUIL,
                " faux "  sinon.

En utilisant la définition de la variance et la formule du calcul de la distance entre 2 couleurs, on obtient :

Homogénéite( R ) = Variance( pixels de R ) = Moyenne(   distance( pixels de R , Moyenne( pixels de R )  ) ^2 )