Algorithme de croissance de région
L'algorithme de croissance de région (en anglais region growing) fait partie des algorithmes couramment utilisés dans le domaine de la segmentation d’images, mais aussi de nuages de points ou de maillages. Il s'agit d'une approche dite ascendante qui fonctionne par agrégation en tenant compte de critères de proximité et d'homogénéité vis-à-vis de la région en cours de formation.
Principe modifier
L'algorithme se décompose en deux étapes :
- Création d'une région et sélection d'un élément de départ (autrement appelé graine/germe ou seed en anglais).
- Croissance de cette région par incorporation d'éléments similaires faisant partie de son voisinage.
La phase de croissance s'arrête lorsque plus aucun des éléments faisant partie du voisinage de la région ne peut y être incorporé.
L'algorithme est généralement répété jusqu'à ce que chaque élément de l'ensemble de données considéré ait été attribué à une région (n répétitions aboutissant alors à n régions). Les éléments évoqués sont les pixels dans le cas d'une image, les points dans le cas d'un nuage de points ou bien les sommets ou les faces dans le cas d'un maillage.
Le fonctionnement de l'algorithme est rendu possible par la définition préalable d'un prédicat, mesurant le degré de similarité d'un élément donné avec la région en cours de formation. Il peut par exemple s'agir de la différence entre le niveau de gris de la région en cours de formation au sein d'une image et le niveau de gris d'un pixel candidat (si cette différence est inférieure au seuil fixé, alors le pixel candidat est intégré à la région ; sinon il est rejeté). De même, la notion de voisinage est un élément central du fonctionnement de l'algorithme. Celle-ci est relativement facile à définir dans le cas des images (cellules adjacentes dans un tableau) ou des maillages (sommets adjacents dans un graphe), mais plus ambiguë dans le cas des nuages de points (l'absence de connectivité entre les points oblige à effectuer une recherche des plus proches voisins).
Remarques modifier
L'algorithme de croissance de région s'avère relativement simple à conceptualiser et à implémenter. Sa pertinence dépend cependant de la définition a priori d'un prédicat adéquat. Ses paramètres (seuils servant à définir la notion de similarité) doivent faire l'objet d'ajustements en fonction du contexte (résolution des données, présence de bruit, etc.).
