La segmentation d'images est un domaine de l'informatique où les applications sont nombreuses, ainsi que les methodes permettant de segmenter les images : filtrage, méthodes morphologiques... Nous présentons ici une methode nouvelle exploitant la fusion de régions.
Une région est un ensemble connexe de points de même niveau de gris.
Nous travaillons sur des images multi-niveaux, c'est à dire en plusieurs Niveaux de gris. La premiere étape consiste à détecter dans l'image les régions (ensemble de points connexes) en 4-connexité. Ensuite nous calculons les gradients entre les differentes régions. La fusion de deux regions consite à :
La difficulté consiste dans le choix des régions à fusionner, dans le choix du critère d'arret ainsi que dans la méthode de calcul du gradient ou encore du choix de la couleur à affecter à la nouvelle région.
L'image ci-dessous présente une fusion entre deux regions :
Fusion entre deux régions
Le choix des régions à fusionner est primordial. Il n'existe pas pour le moment de méthode dite meilleure ou optimale pour ce choix. Notre suiveur nous a demandé de fusionner les régions grâce à une file d'attente hiérarchique (ou fah), structure de données qui permet de trier en temps lineaire (pourvu que les données ne puissent prendre qu'un nombre fini de valeurs, ce qui est notre cas) en fait la fah est une extention du fameux radix sort.
Une fah est constituée d'un nombre fini de piles (des fifos), chaque pile représentant une valeur possible du gradient entre deux régions. Lorsqu'une pile est vide, elle est supprimée. Si nous avons un élement à insérer dans une pile qui a disparue, nous l'insérons dans la file d'urgence, ce qui nous évite de chercher la première file non-vide et ainsi de garder un temps linéaire pour l'extraction des élements. Cette méthode est présentée plus avant dans l'article : un algorithme optimal de ligne de partage des eaux de M. Meyer.
Nous insérons dans la fah un lien entre deux régions, ce lien étant caractérisé par le gradient entre les deux régions qu'il lie entre elles.
Pour décider quelles régions fusionner, on extrait l'élement le plus prioritaire de la fah, c'est à dire celui de gradient le plus faible. La fusion implique quelques problèmes : il faut trouver les voisins de cette nouvelle régions, invalider les liens des deux anciennes régions, et insérer dans la fah les liens entre la region nouvellement formée et ses voisins.
On arrête les fusions de régions que lorsqu'il n'y a plus de régions ayant un gradient inférieurs à une limite donnée par l'utilisateur. C'est le seul paramètre que l'utilisateur peut fixer.
Le calcul de la nouvelle couleur peut se faire de plusieurs façons :
Le calcul du gradient permet d'insérer le lien entre deux régions dans la fah. Nous avons en premier lieu utilisé une méthode purement locale (|A-B| où A et B sont les niveaux de gris des régions RA et RB). Cette méthode donne de bons résultats mais ne prend pas en compte le voisinage des régions RA et RB.
Nous avons ensuite utilisé une méthode permettant une pondération grâce au voisinage entre les deux regions.
L'avantage de la fusion est de conserver des informations sur les zones crées. On peut en effet reconstituer les régions obtenues d'apres leur couleur. D'autres méthodes ne le permettent pas (cas du filtrage qui donne une image en noir et blanc). Nous avons fait des essais de recherche de contours avant et apres fusion, et on constate une nette amélioration de l'algorithme, en réduisant la sur-segmentation.
Vous pouvez voir sur cette animation les résultats de la fusion sur une coupe d'un muscle.
Vous pouvez nous contacter par e-mail :
Vous pouvez également contacter notre suiveur qui nous a aidé tout au long de ce projet :
Vous pouvez aussi lire la version on-line de notre rapport.