Segmentation en régions


précédentsommairesuivant

III. Décomposition/Fusion (Split/Merge)

Cette technique enchaîne les 2 phases suivantes :

1. Découper itérativement l'image jusqu'à avoir des blocs contenant exclusivement des pixels similaires.
2. Regrouper les blocs voisins s'ils sont similaires

Les deux phases sont nécessaires afin de garantir que les régions obtenues sont à la fois homogènes et également les plus grandes possibles. Chaque phase étant indépendante, on peut les étudier séparément.



La décomposition (split)

La méthode couramment utilisée consiste à faire une dichotomie par blocs de l'image. Pour cela, on commence par définir un bloc de la taille de l'image, puis on examine le contenu de ce bloc. Si le bloc est homogène (= contient exclusivement des pixels similaires) alors on arrête la décomposition. Sinon, on découpe le bloc en 4 sous-blocs et on examine le contenu de chaque sous-blocs.

Image non disponible
Décompositions successives des blocs



Et ainsi de suite jusqu'à ce qu'il n'y ait plus besoin de décomposer les blocs. Le résultat obtenu est donc un ensemble jointif de blocs de différentes tailles qui recouvre entièrement l'image.

Image non disponible
Décomposition finale



L'implémentation la plus simple pour cette méthode consiste à définir une structure d'arbre appelée QuadTree. C'est un arbre dans lequel chaque nœud représente un bloc. Chaque nœud possède donc 0 sous-nœud (bloc homogène) ou 4 sous-nœuds (bloc non-homogène).

Image non disponible
Représentation sous forme de Quadtree



La décomposition finale est définie par les blocs associés aux feuilles de l'arbre. On obtient ainsi une liste de blocs de différentes tailles et positions. Si la structure du QuadTree permet une navigation aisée entre bloc conteneur (parent) et sous-blocs (enfants), elle ne permet pas de naviguer facilement entre des blocs voisins. Pour cela, il est préférable de construire et d'utiliser le graphe d'adjacence.



La sur-segmentation (over segmentation)

La méthode de décomposition décrite ci-dessus entraîne la création systématique de 4 sous-blocs en cas de non-homogénéité. Cependant, dans les dernières itérations, la décomposition en 4 sous-blocs n'est normalement pas nécessaire. En effet, parmi les 4 sous-blocs créés, plusieurs sont similaires.

Image non disponible
La décomposition en 4 peut faire apparaître des blocs similaires (ici les blocs 1, 2 et 3)



De plus, chaque bloc étant traité isolément de ses voisins, certains sous-blocs, parfois de tailles différentes, seront à la fois similaires et jointifs.

Image non disponible
Les décompositions successives peuvent faire apparaître des blocs similaires (ici les blocs A et B)



Au final, l'image va contenir de nombreux petits blocs jointifs et similaires. Ce phénomène, inhérent à la méthode de décomposition, s'appelle la sur-segmentation. La prochaine étape de l'algorithme va donc être de regrouper les blocs jointifs et similaires en une seule région.



La fusion (merge)

Cette étape à pour objectif d'identifier les régions qui composent l'image en regroupant les blocs jointifs et similaires.

Il faut tout d'abord définir le critère de similarité entre blocs. Le plus simple est d'étendre la définition de similarité entre pixels définie lors de l'étape de décomposition. Ainsi, on peut assimiler un bloc à un " gros " pixel en calculant sa valeur/couleur moyenne, et en utilisant le graphe d'adjacence pour naviguer vers les blocs voisins.

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

 
Sélectionnez

Créer la liste « [K] » des blocs associés aux feuilles du QuadTree

Pour chaque bloc « B » dans la liste « [K] » 

	Créer une nouvelle région « [R] »
	Retirer « B » de « [K] » et l'ajouter dans « [R] »
	Calculer la valeur/couleur moyenne de « [R] »

	Créer la liste « [N] » des blocs voisins du bloc « B » 

	Pour chaque bloc « Bn » dans la liste « [N] »
		Si (« Bn » est dans « [K] »)  ET (« Bn » et « [R] » sont similaires) Alors
			Retirer « Bn » de « [K] » et l'ajouter dans « [R] »
			Ajouter les blocs voisins de « Bn » dans la liste « [N] »
			Recalculer la valeur/couleur moyenne de « [R] »
		Fin Si
	Fin Pour

Fin Pour



Cet algorithme construit les régions une par une, en regroupant progressivement les blocs jointifs autour d'un bloc de départ. L'algorithme amalgame les blocs adjacents à la région, formant ainsi une région de plus en plus grande.

Image non disponible
Agrégation itérative des blocs similaires au bloc 1



Il est conseillé de trier les blocs de la liste " K " par taille décroissante. L'algorithme commence ainsi par construire les régions en commençant par les plus grands blocs, ce qui améliore la stabilité du calcul de la valeur/couleur moyenne de la région.

Image non disponible Image non disponible
Résultat intermédiaire de la fusion. On construit d'abord les grandes régions Résultat final de la fusion (1926 régions)

précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Ce document est issu de http://www.developpez.com et reste la propriété exclusive de son auteur. La copie, modification et/ou distribution par quelque moyen que ce soit est soumise à l'obtention préalable de l'autorisation de l'auteur.