Post–segmentation d’image via la métaheuristique des colonies de fourmis

Optimisation par colonies de fourmis

Les algorithmes de colonies de fourmis sont une famille de métaheuristiques d’optimisation inspirées du comportement collectif de fourmis réelles dans leur procédé de dépôt et de suivi de pistes. Ces algorithmes ont été initiés par Dorigo et al. [Dorigo, 1992; Dorigo et al., 1996] en s’inspirant des travaux de Deneubourg et al. [Deneubourg et al., 1983] qui ont modélisé le comportement aléatoire des fourmis.
Le premier algorithme d’optimisation, basé sur les colonies de fourmis, intitulé “Ant System” (AS), a été proposé pour résoudre le problème du voyageur de commerce [Dorigo et al., 1996]. Depuis, plusieurs améliorations et variantes ont vu le jour et ont été appliquées dans plusieurs domaines, avec plus ou moins de succès.
Il était remarqué [Goss et al., 1989; Beckers et al., 1992] que les fourmis réelles sont capables d’emprunter le chemin le plus court entre leur nid et une source de nourriture grâce à un comportement collaboratif collectif, sachant qu’aucun individu n’a une vision globale du parcours.
Le comportement des fourmis est basé sur les principes suivants :
– L’auto-organisation : les fourmis sont capables, en eectuant individuellement des tâches simples, de résoudre des problèmes complexes. Le comportement simple et local de chaque individu fait émerger un modèle (“pattern”, en anglais) de niveau global grâce aux interactions.
– La stigmergie : qui est la technique de communication entre les individus (fourmis) en modifiant, d’une manière dynamique, l’environnement où elles évoluent. En eet, en se déplaçant, les fourmis déposent de la phéromone 1 pour marquer le chemin parcouru.
En absence de cette substance, les fourmis se déplacent aléatoirement dans l’environnement. Par contre, en sa présence, une fourmi la détecte et peut suivre sa trace avec une probabilité proportionnelle à son intensité. Ainsi, plus une piste est parcourue, plus elle est attirante.
– Un contrôle décentralisé : cela signifie qu’il n’y a pas de décision prise à un niveau donné ou par un seul individu. En eet, chaque individu eectue des actions relativement simples en se basant uniquement sur des informations locales de l’environnement, sans le milieu extérieur, provoque chez un congénère des réactions comportementales spécifiques. (dictionnaire Larousse).

Optimisation par colonies de fourmis vision du problème dans sa globalité

– Une hétérarchie dense : par opposition à une structure hiérarchique, où la population est dirigée par un individu, l’hétérarchie dense est une structure horizontale, où les individus sont fortement connectés, agissant ainsi sur les propriétés globales du système.
La figure IV.1 illustre un exemple du processus d’optimisation de chemin entre un nid de fourmis et une source de nourriture. En eet, au début de l’expérience (figure IV.1(a)), les fourmis arrivent au point (A), et comme il n’y a pas de traces de phéromone, elles choisiront l’une des deux directions aléatoirement avec la même probabilité. Les fourmis qui ont emprunté le chemin ACD arriveront, en toute logique, plus rapidement à la source de nourriture que les autres et feront le chemin inverse plus tôt. Ainsi la quantité de phéromone déposée sur le parcours ACD sera plus importante que celle déposée dans ABD. Comme un parcours contenant plus de phéromone a plus de chance d’être emprunté, plus de fourmis vont choisir le parcours ACD (figure IV.1(b)). Ainsi, à terme, le chemin le plus court est renforcé et sera emprunté par la majorité des individus ; de plus, si on considère le phénomène d’évaporation du phéromone, après un certain temps, tous les individus parcourront le chemin le plus court.

Système de fourmis “Ant System” (AS)

Dans cette section, nous décrirons le principe général de l’algorithme “Ant System” proposé dans [Dorigo et al., 1996], appliqué au problème du voyageur de commerce. Initialement, chaque fourmi est placée aléatoirement dans une ville (sommet de graphe), puis se déplace au fil des itérations d’une ville à une autre construisant ainsi un trajet. A chaque itération t, une fourmi k choisie de se déplacer de la ville i où elle se trouve vers une ville j pas encore visitée avec une probabilité pk ij (t) (Eq.(IV.1)) :

Système de colonie de fourmis “Ant Colony System” (ACS)

L’apport majeur dans l’algorithme “Ant Colony System” est l’introduction de la notion de mise à jour locale [Dorigo & Gambardella, 1997; Gambardella & Dorigo, 1996] en plus de la mise à jour qui se produit à la fin de la construction. En eet, pour chaque fourmi (individu) à chaque itération, une mise à jour est eectuée (Eq. (IV.4)) au niveau du dernier chemin (arc) visité.

Contribution à la segmentation d’image par colonie de fourmis

La méthode que nous proposons est un processus de post-traitement visant à corriger les erreurs de la segmentation produite par un algorithme de segmentation basée-régions. La première étape de notre méthode est la détection des erreurs potentielles. La deuxième étape consiste à corriger ces erreurs. L’étape de détection est décrite dans la section II.3.3. Une fois les pixels potentiellement mal classés détectés, le problème consiste à réaecter chacun d’eux à sa nouvelle classe en minimisant un certain critère. Ce problème est un problème d’optimisation combinatoire. Pour le résoudre, nous avons opté pour la métaheuristique des colonies de fourmis. Cette méthode est détaillée dans les sections suivantes.

Représentation et initialisation

Dans notre méthode, chaque pixel détecté comme potentiellement mal classé peut être considéré comme une fourmi. Le déplacement des fourmis d’une ville à une autre représente par analogie le changement d’appartenance d’un pixel aux diérentes classes. Cependant, quelques diérences subsistent. Dans notre modèle, une solution est construite après un seul changement de classe pour tous les pixels, alors que, dans le problème du voyageur de commerce, une solution est construite après un tour complet des fourmis. De plus, dans notre modèle, un pixel peut ne pas changer de classe, mais il est considéré comme un déplacement (dépôt de phéromone). Initialement, les traces de phéromone sont déposées dans toutes les directions possibles, i.e. toutes les réaectations possibles des pixels. La valeur de densité de phéromone initiale · (0) est fixée constante à ·init.

Processus de construction

A chaque itération t, chaque pixel k change son label actuel i et prend le label de l’un des pixels (j) présents dans son voisinage immédiat N3◊3 , en fonction de la fonction de transition de probabilité (Eq. (IV.1)).

Résultats expérimentaux

Dans cette section, nous présentons des résultats expérimentaux de la méthode proposée sur la base d’images synthétiques. Cette méthode est appliquée comme un processus de posttraitement de segmentation.
La base d’images utilisée contient des images synthétiques de taille 128 ◊ 128, contenant 2, 3, 4 ou 5 classes et aectées de bruits Gaussien, Uniforme ou sel & poivre. Les bruits Gaussien et uniforme sont d’une variance de 0, 002 jusqu’à 0, 01 avec un pas de 0, 02 (les images sont normalisées dans l’intervalle [0, 1]). Le bruit sel & poivre est d’un taux variant de 1% jusqu’à 5% avec un pas de 1%. La mesure de performance utilisée est la mesure de cohérence de la segmentation SA définie dans l’équation (II.17). Cette mesure représente le taux de pixels bien classés. La valeur retenue est la moyenne de 10 exécutions.
Nous avons appliqué notre méthode après utilisation des méthodes de segmentation basées sur la logique floue (car réputées pour leurs performances) : FCM, FCM-S1, FCM-S2 et FLICM.
La figure IV.2 montre un exemple d’image, de la base utilisée, contenant 5 classes et aectée d’un bruit Gaussien de variance 0, 008. Les résultats de segmentation de cette image avec les méthodes FCM, FCM-S1, FCM-S2 et FLICM, avec et sans utilisation de post-segmentation, sont présenté dans les figures IV.3, IV.4, IV.5 et IV.6, respectivement. Dans ces figures, on remarque que les résultats de segmentation sont améliorés dans les cas d’utilisation de la postsegmentation. Néanmoins, le résultat de la méthode FCM avec post-segmentation n’est pas acceptable. Cela est dû à la qualité de la segmentation sans post-segmentation. En eet, la méthode que nous proposons est basée sur les pixels de confiance. Un nombre très faible de ces pixels ne peut pas conduire à une correction acceptable.
Le tableau IV.1 donne les résultats quantitatifs des résultats de segmentation des diérentes méthodes, avec et sans utilisation de la post-segmentation. On remarque que la méthode proposée, pour les quatre méthodes, arrive à améliorer les résultats de la segmentation.

Conclusion

Dans ce chapitre, nous avons présenté une méthode de post-segmentation qui permet de corriger les erreurs de segmentation produites par les méthodes de segmentation basées-régions. La méthode développée permet de détecter et de reclasser les pixels potentiellement mal classés.
Ces pixels sont ceux situés au niveau des frontières entre régions, là où se produisent généralement les erreurs. Une fois ces pixels détectés, on est confronté à un problème d’optimisation combinatoire. Pour résoudre ce problème, nous avons utilisé la métaheuristique d’optimisation par colonie de fourmis dans sa version “Ant Colony System”. La méthode proposée a été testée sur une base d’images synthétiques contenant plusieurs types et taux de bruit, pour corriger les résultats de segmentation de plusieurs algorithmes de segmentation. Les résultats montrent que notre méthode permet de corriger la majorité des erreurs.