Sce OUADFEL SALIMA PDF
Sce OUADFEL SALIMA PDF
Sce OUADFEL SALIMA PDF
Thèse
En vue de l'obtention du diplôme de
Doctorat en Informatique
Contributions à la Segmentation
d’images basées sur la résolution
collective par colonies de fourmis
artificielles
Présentée le 04/07/ 2006
par
OUADFEL SALIMA
Devant le jury composé de :
Président N. Bouguechal Prof., Université de Batna
Examinateurs L. Hamami MC., l’E .N.P.A
A. Moussaoui MC., Université de Setif
A. Zidani MC., Université de Batna
Rapporteur M. Batouche Prof., Université de Constantine
2
3
Remerciements
Je remercie mon mari pour le soutien et ses encouragements pour la finalisation de ce travail.
4
Résumé
Le travail présenté dans cette thèse décrit une nouvelle approche pour la segmentation
d’images. Cette approche s’inspire des comportements collectifs et auto-organisé des fourmis
dans la nature. Elle se base sur une population de fourmis artificielles simples capables de
s’auto-organiser pour faire émerger une segmentation optimale.
Dans un premier temps, on s’est inspiré du comportement collectif de tri de couvain observé
chez les fourmis pour développer une méthode de classification non supervisée. Les pixels de
l’image sont initialement placés sur un tableau de cases représentant l’environnement des
fourmis. Selon une fonction de similarité locale, les fourmis vont déplacer les pixels d’une
case à une autre dans le but d’obtenir des classes homogènes et bien séparées. La méthode
testée sur des images synthétiques et réelles a montré son efficacité et sa capacité à extraire un
nombre correct de classes avec une partition de bonne qualité en comparaison à l’algorithme
classique Kmeans.
Dans un second temps, le comportement collectif de recherche de nourriture a été utilisé pour
la segmentation d’images basée sur les champs de Markov. L’image est segmentée en
maximisant la probabilité a posteriori (MAP) utilisant des algorithmes inspirés de la
métaheuristique « Optimisation par les Colonies de Fourmis ». Une colonie de fourmis
artificielles construit de nouvelles partitions selon un processus itératif et stochastique en
utilisant une information heuristique et des traces de phéromones artificielles. Les nouvelles
partitions sont ensuite optimisées en utilisant un algorithme de recherche local. Une étape de
diversification est aussi introduite afin de diversifier la recherche. Les résultats obtenus
donnent de bons résultats comparés à ceux obtenus par d’autres méthodes d’optimisation.
Abstract
The work described a new approach for image segmentation. This approach is inspired from
some swarm and auto-organized comportments of real ants in the nature. It is based on a
population of artificial and simples ants capable of auto-organized in order to emerge an
optimal segmentation.
In the first part of the work, we have used the self-organizing and autonomous brood sorting
behavior observed in real ants for unsupervised image classification. Ants move on a discrete
array of cells represented the ants’ environment. Ants may move pixels that are scatted within
the cells of the array according to a local similarity function. In this way, ants form clusters
without the initial knowledge of the number of clusters and initial partition. Experimental
results on synthetic and real images demonstrate the ability of the method to extract the
correct number of clusters with good clustering quality compared to the results obtained from
the classical clustering algorithm Kmeans.
In the second part, the food hunting comportment has been used for image segmentation
based on the Markov Random Field. The image is segmented by maximizing the a posteriori
probability (MAP) using algorithms inspired from the ant colony optimization metaheuristic.
A colony of artificial ants build new partitions within a stochastic iterative process, by adding
solution components to partial solutions using a combination of heuristic information and an
artificial pheromone trail. The new partitions found by ants are then optimized using a local
search algorithm. Pheromone trails are reinforced according to the quality of the partitions
found by the best ant. A diversification phase is also used to diversify the search. The
experimental results presented outperform those obtained with other optimization methods.
Figure 5.6. Evolution de l’index de Rand sur l’image synthtique1. ................................. 131
Figure 5.7. Exemples d’images segmentées par l’algorithme AntClust........................... 132
Bibliographie…....………………………………………………………………………….175
12
Chapitre 1
Introduction générale
Chapitre 1. Introduction Générale ....................................................................................... 13
1.1 Contexte de l’étude : la vision par ordinateur .......................................................... 13
1.2 La segmentation d’images........................................................................................ 15
1.3 Motivations............................................................................................................... 16
1.4 Résolution de problèmes par émergence.................................................................. 17
1.5 Contributions............................................................................................................ 19
1.6 Structure et contenu de la thèse................................................................................ 21
13
Cette théorie a été résumée par Radu Horaud et Olivier Monga [Horaud, 1995] de la manière
suivante : « La vision est un processus de traitement de l’information. Elle utilise des
stratégies bien définies afin d’atteindre ses buts. L’entrée d’un système de vision est
constituée par une séquence d’images. Le système lui-même apporte un certain nombre de
connaissances qui interviennent à tous les niveaux. »
David Marr fut le premier à rechercher une formalisation scientifique du problème de vision.
Il proposa à la fin des années 70, un paradigme de la vision définit de la façon suivante[Marr,
1980] :
Ses travaux ont permis d’engendrer un grand nombre d’application en donnant une
formulation algorithmique aux différents points de son paradigme.
14
Une partie des traductions algorithmiques du paradigme de David Marr, qui a débouché sur
des algorithmes efficaces, est organisée en trois grands niveaux tel qu’illustré à la figure 1.1:
Haut
niveau Surfaces, objets, etc.
Ces niveaux sont parcourus selon une approche ascendante, où les structures obtenues sont de
plus en plus complexes selon le niveau de représentation utilisé.
Le cadre général dans lequel s’inscrit cette thèse est celui de la segmentation d’images. Cette
opération a pour objectif d’extraire à partir d’une image numérique des indices visuels ou des
primitives pertinentes permettant de la représenter sous une forme plus condensée et
facilement exploitable dont dépend la performance des systèmes de vision artificielle.
15
∀i, Ri ≠ φ
∀i ≠ j, Ri ∩ R j = φ
I = ∪i Ri
1. Les méthodes de segmentation par contours basées sur la recherche des discontinuités
locales présentes dans l’image.
Bien que le problème de la segmentation d’images ait fait l’objet d’une vaste littérature [Pal
1993], ce problème est encore loin d’être résolu et la segmentation, telle qu’elle est définie
n’est évidemment pas unique [Cocquerez 1995a]. Le choix d’une méthode est lié à plusieurs
16
facteurs tels que les spécificités de l’image a traiter (présence de texture, présence de
dégradations, non homogénéité de régions,…), conditions d’acquisition, du type d’indices
visuels a extraire ainsi que des contraintes d’exploitation. Ballard a exprimé cette difficulté
comme suit: « the most severe chicken-and-egg problem of static computer vision is the
segmentation problem. It is difficult to separate figure from ground without recognizing
objects, and it is difficult to recognize objects if they are not separated from the background
and other objects » [Ballard 1992]. De plus, elle n’est pas une fin en soi et de sa qualité
dépend des résultats des traitements ultérieurs obtenus à partir les primitives extraites. Les
régions extraites peuvent être présentées comme entrées pour un système de reconnaissance
d’objets ou bien pour un processus de prise de décision.
1.3 Motivations
La segmentation est un problème mal posé au sens de Hadamard [Tikhonov, 1974], comme
est le cas pour de nombreuses tâches de vision artificielle, à cause de la non unicité de
l'incertitude et de l'instabilité des solutions par rapport aux données d'entrées. C’est aussi un
problème complexe, tant du point de vue de la formulation du problème que de point de vue
de choix de la technique de résolution et est confrontée au problème d’ambiguïté et de bruit
qui affecte certains pixels. Ces difficultés expliquent le fait qu’il soit donc difficile de définir
une bonne segmentation d’une image et que le problème de segmentation reste ouvert jusqu’à
ce jour.
Ce travail de thèse est consacré aux méthodes de classification qui considèrent une classe
comme un ensemble de pixels connexes ou non, possédant des intensités similaires. Le
problème de partitionnement revient à chercher une partition qui regroupent d’une manière
optimale les N pixels de l’image en K classes (clusters) de telle sorte que les pixels d’une
même classe soient plus proche entre eux en terme d’un (ou plusieurs) critère, qu’avec les
pixels des autres classes. On peut essayer de résoudre ce problème par une méthode brute en
engendrant toutes les partitions possibles et à retenir celle qui minimise au mieux le critère de
partitionnement. Malheureusement, la taille de l’espace des partitions possibles est de l’ordre
Nk
de O . La classification se ramène alors à un problème d’optimisation complexe NP-
K!
difficile pour lequel les méthodes locales s’avèrent très vite impraticables même pour une
image de petite taille.
Les méthodes de partitionnement sont dites supervisées lorsque des informations a priori sont
introduites dans le processus de construction de classes, et non supervisés quand aucune
connaissance n’est disponible. L’inconvénient majeur des méthodes de partitionnement
supervisées classique est qu’elles exigent de connaître au préalable le nombre possible de
17
classes de pixels ainsi qu’une bonne partition de départ dont dépend le résultat final de
classification. Ces contraintes rendent l’utilisation de ces algorithmes peu intéressante quand
on veut segmenter automatiquement une image.
Depuis quelques années, les chercheurs informaticiens ont trouvé en le monde naturel, une
source d’inspiration inépuisable pour la conception de nouveaux systèmes informatiques. Il
s’agit de puiser dans les comportements des êtres naturels de nouvelles approches pour la
18
Tous ces systèmes naturels présentent un point commun : l’ émergence d’un comportement
global collectif et complexe à partir de simples interactions entre des insectes simples dotés
d’une intelligence très réduite et ne possédant qu’une vision très partielle de leur
environnement[Bonabeau, 1999]. Ce comportement émergeant leur permet de résoudre
collectivement des problèmes très complexes
Parmi ces systèmes, on trouve les méthodes d’optimisation par essaim particulaires inspirés
de l'étude de l'organisation de groupes d'animaux, [Eberhart, 2001], les algorithmes inspirés
des essaims d’insectes volants [Aupetit, 2003], et les systèmes de fourmis artificielles
largement utilisés ces dernières années pour résoudre des problèmes de classification ou
d’optimisation [Dorigo, 1991]. Il s’agit d’une nouvelle approche qui s’intéresse aux
comportements individuels des fourmis réelles, aux interactions entre ces entités autonomes et
à l’émergence au niveau supérieur de l’ensemble du système de comportements complexes
pouvant être qualifié d’intelligent.
19
1.5 Contributions
Cette thèse part du constat simple que les colonies de fourmis résolvent des problèmes
complexes, bien que l'intelligence d'une fourmi soit limitée. Les travaux menés dans le cadre
de cette thèse portent sur différents aspects :
Deux approches sont possibles pour développer de nouvelles méthodes basées fourmis
comme on le verra dans cette thèse. La première approche modélise la faculté des fourmis à
trier collectivement leur couvain ou à construire des cimetières. Ce modèle est relativement
simple et est très stimulant pour résoudre le problème du partitionnement Les algorithmes à
base de ce modèle ont été proposés pour la première fois par Deneubourg et son équipe
[Deneubourg, 1990]et ont été adapté par la suite au problème de la classification non
supervisée par d’autres chercheurs dans différents domaines.
sont utilisés depuis avec succès pour la résolution des problèmes d’optimisation combinatoire.
Ces algorithmes ont été regroupés sous le nom générique de « Optimisation par Colonies de
Fourmis » (OCF)..
Globalement, les algorithmes présentés dans cette thèse sont basés sur des processus
stigmergiques [Grassé, 1959]. Chaque fourmi dispose d’un comportement individuel
influencé par le comportement des autres fourmis qui évoluent dans le même environnement.
Le comportement collectif est assuré par la stigmergie et par l’environnement qui est
considéré comme la mémoire collective de la colonie. Les principales caractéristiques de
notre approche sont les suivantes : :
21
La distribution : Elle offre intrinsèquement des algorithmes distribués qui peuvent employer
le calcul parallèle tout à fait facilement.
L’Adaptabilité : étant donné qu‘il n’y a aucun contrôle central dans nos algorithmes de
segmentation les interactions locales des entités individuelles permet une grande adaptabilité
du système global. Cette propriété permet à l’ensemble sans explicitation de but ni
mécanismes de communication, de s’adapter globalement à des configurations différentes
grâce à la combinaison des adaptations locales effectuées en parallèle.
La Simplicité : comme on le verra dans la suite de cette thèse, on peut concevoir un système
collectif au fonctionnement complexe à partir d’individus très simples et donnant de très bons
résultats.
- Chapitres 2,3, et 4 dédiés aux éléments d’état de l’art : ils ont pour but de présenter
une tentative de synthèse des différents domaines auxquels nous avons touché dans le
cadre de cette thèse à savoir l’émergence et son application en informatique, les
fourmis informatiques et la segmentation d’images.
Le troisième chapitre est consacré aux différents travaux inspirés par les comportements
collectifs des fourmis. Après une introduction générale sur les fourmis réelles, le chapitre se
focalise d’une part sur la métaheuristique OCF et ses domaines d’application et d’autre part
sur les algorithmes inspirés du tri de couvain chez les fourmis.
Le chapitre 7 est réservé à une conclusion générale sur l’ensemble de nos travaux ainsi
qu’aux améliorations qui pourrait être apportées et aux perspectives qu’elle offre.
23
Chapitre 2
Le phénomène d’ émergence
et l’informatique
Chapitre 2. Le phénomène d’émergence et l’informatique................................................ 24
2.1 Introduction .............................................................................................................. 24
2.2 Caractérisation d’un phénomène émergent .............................................................. 25
2.3 L’auto-organisation comme technique d’émergence ............................................... 26
2.3.1 Définitions........................................................................................................ 27
2.3.2 Les mécanismes de l’auto-organisation ........................................................... 28
2.4 L’intelligence en essaim........................................................................................... 30
2.5 Emergence et systèmes artificiels collectifs............................................................. 30
2.5.1 Algorithmes évolutionnaires et algorithmes génétiques .................................. 31
2.5.2 Les réseaux de neurones................................................................................... 36
2.5.3 Algorithmes à essaims de particules ................................................................ 40
2.5.4 Les algorithmes de fourmis artificielles ........................................................... 42
2.6 Conclusion................................................................................................................ 44
24
« L’Émergence : apparition plus ou moins soudaine d'une idée, d'un fait social,
politique,économique ».D’après Petit Larousse Illustré.
2.1 Introduction
Bien que l’émergence soit encore aujourd’hui l’une des notions les plus floues et les plus
discutées, elle est actuellement la plus utilisée pour la conception des systèmes artificiels. Son
origine viendrait d’après Ali et Zimmer [Ali, 1997], du postulat datant de l’antiquité Grèce :
"le tout est plus que la somme de ses parties". Ce concept se retrouve aussi dans des écrits de
Thalès et Anaximandre et bien plus tard dans le "tout avant les parties" d’Aristote et dans les
écrits de J. W. von Goethe fondateur de la théorie de la "gestalt".
Entrée 1 Sortie 1
Entrée 2 Sortie 2
Entrée n Sortiem
Entrée 1 Sortie 1
Entrée 2 Sortie 2
Entrée n Sortie m
D’une manière intuitive, la notion d’émergence peut être définie comme une propriété
macroscopique d’un système qui ne peut pas être déduite à partir de son fonctionnement
microscopique. On parle d’émergence quand il y a apparition de structures, et de
comportements plus complexes que ceux des entités qui forment le système. Ces
comportement sont non programmés explicitement et donc non prévisibles. Cette propriété
initialement dans les domaines de la biologie, de la thermodynamique est reprise depuis
quelques années dans le domaine de l’informatique et a été exploitée pour la conception des
systèmes artificiels.
Selon le premier point de vue, l’émergence doit être définie afin de reconnaître un phénomène
émergent. Plusieurs définitions de l’émergence ont été proposées dans la littérature. Nous
tirons à partir d’elles des propriétés inter-reliées et communes qui permettent d’identifier un
phénomène comme émergent:
Du point de vue concepteur d’un système produisant un phénomène émergent, le système doit
présenter les caractéristiques suivantes :
Un état proche de l’équilibre : Au lieu de s’intéresser aux points qui conduisent à l’équilibre
du système, on s’intéresse au voisinage de ces points, comme en théorie de la complexité. En
de tels points, l’apparition de phénomènes non prévisibles explique le caractère inattendu de
l’émergence [Prigogine, 1977].
Les attracteurs : Contrairement aux premiers systèmes pour lesquels il n’existait qu’un seul
attracteur valide qui menait à l’équilibre, les systèmes émergents possèdent différents types :
le point fixe, le cycle limite et l’attracteur étrange. Ces attracteurs ne sont pas pré-donnés et ne
dictent pas au système l’état à atteindre, mais plutôt les moyens de passer d’état en état
[Goldstein, 1999].
l’approche cartésienne classique pour laquelle la tâche globale est décomposée en sous-tâches
car les étapes de résolution ne peuvent pas être programmées explicitement au départ.
L’approche émergentiste se révèle donc comme un moyen de passage entre l'activité du
“micro-niveau” (les interactions locales entre les composants du système et celui du “macro-
niveau” (le comportement global). Tenant compte des définitions présentées dans le
paragraphes précédent, il apparaît que l’auto-organisation est un élément essentiel pour
l’obtention d’un phénomène émergent. Dans ce qui suit, nous allons définir le terme « auto-
organisation » ainsi que son principe.
2.3.1 Définitions
Depuis son apparition dans les domaines de biologie, de chimie et de physique, l’utilisation
du terme « auto-organisation » s’est largement répandue ces dernières années pour la
conception des systèmes informatiques artificiels. Plusieurs définitions du concept d’auto-
organisation existent dans la littérature. Nous pouvons en citer les suivantes :
Définition1: « L'auto-organisation est une description d'un comportement, elle a une valeur
heuristique et elle permet d'indiquer un phénomène. Elle est condamnée à rester une simple
description, tant qu'on ne se préoccupe pas de rechercher le mécanisme qui est à son
origineé »[Varela, 1988]
bas niveau du système. De plus les règles spécifiant les interactions entre composantes du
système sont suivies en utilisant uniquement des informations locales sans références au
modèle global » [Camazine, 2000].
Définition 6 : « Tout processus au cours duquel des structures émergent au niveau collectif
(ou plus généralement apparition d’une structure à l’échelle N + 1 à partir d’une dynamique
définie à l’échelle N), à partir de la multitude des interactions entre individus, sans être codées
explicitement au niveau individuel.» [Théraulaz, 1997].
Toutes ses définitions font référence les mêmes concepts : structuration, organisation,
interaction, autonomie et enfin émergence d’un comportement global à partir de plusieurs
comportements locaux [Georgé, 2004]. L’auto-organisation peut être alors définie comme un
moyen permettant à un système de se structurer et de se maintenir sans aucune intervention de
l’extérieur. Chaque composant du système réagit aux stimulus par des règles locales simples
et modifie ainsi son environnement et donc le comportement des autres composants (par
exemple le dépôt de traces de phéromones chez les fourmis). De ce processus émerge une
intelligence collective qui permet au système de réaliser des tâches difficiles voire complexes
non explicites. On voit là que le concept d’émergence et fortement lié à celui de l’auto-
organisation.
La gestion des flux : ce sont des moyens de communication entre les composants du système
et avec leur environnement. La communication peut être directe par messages ou signaux ou
bien indirecte par le biais de modifications de l’environnement. Cette deuxième possibilité de
communication a été appelée par le chercheur Pierre-Paul Grassé « stigmergie » [Grassé,
1959] à partir des racines stigma qui signifie piqûre, et ergon. qui veut dire travail ou oeuvre.
En effet Grassé a montré vers la fin des années 1959 que chez les termites, la construction
d’une battisse est guidée par la construction elle même et ne dépendait pas seulement des
termites bâtisseuses : l'insecte ne dirige pas son travail mais il est guidé par lui [Grassé 1959].
Ainsi, toute nouvelle forme construite, devient un nouveau point de départ matériel pour les
autres termites produisant ainsi une nouvelle forme stimulante, qui peut orienter et déclencher
en retour une nouvelle activité bâtisseuse chez les autres membres de la colonie. Grâce à la
stigmergie, les termites arrivent à s’auto-organiser pour réaliser un travail collectif sans
aucune coordination directe.
Dans une approche basée sur l’intelligence en essaim, les entités formant l’essaim ont un
comportement relativement simple, que l’on ne peut pas qualifié d’intelligent. Cependant ces
comportements individuels peuvent faire émerger grâce à des interactions locales inter-
individus et avec l’environnement des règles locales un comportement complexe, adaptatif
sans aucun contrôle central. « Dans les sociétés d’insectes, le «projet» global n’est pas
programmé explicitement chez les individus, mais émerge de l’enchaînement d’un grand
nombre d’interactions élémentaires entre individus, ou entre individus et environnement. Il y
a en fait intelligence collective construite à partir de nombreuses simplicités
individuelles.»[Deneubourg,1991]. L’intelligence en essaim tente alors de simuler les
mécanismes produisant ce type de comportements, afin de proposer de nouvelles techniques
pour la résolution de problèmes.
premier est que le calcul n’est pas explicité, ni programmé à l’avance mais est de nature
émergente. On parle alors de « calcul émergent » ou « emergent computation » [Forrest
1990]. Le deuxième point est qu’ils sont constitués d’entités dont le comportement est en
général très simple et réactif, cependant ils sont simples capables, au niveau du groupe, de
comportements d’apprentissage, d’adaptation aux changements, de robustesse vis-à-vis des
cas non prévus. Pour cette raison, ces systèmes sont généralement qualifiés de « systèmes
collectifs intelligents».
La plupart des applications utilisant ce type de systèmes l’ont été dans le domaine de
l’optimisation. Il s’agit de maximiser ou de minimiser une fonction objectif afin de trouver les
meilleurs solutions à un problème donné. C’est généralement un problème NP-complet, pour
lequel les méthodes exactes classiques ne donnent pas de bons résultats en un temps
acceptable d’où la nécessité d’utiliser des heuristiques. Dans la suite, nous allons présenter
certains de ses systèmes.
En 1859, Charles Darwin évoqua, dans son livre « De l’origine des espèces par voies de
sélection Naturelle » [Darwin, 1859], les premiers principes de la théorie de l’évolution. Selon
lui l’évolution des systèmes vivants au cours des générations s’opère en deux étapes : la
sélection et la reproduction :
• La sélection naturelle est le mécanisme central qui opère au niveau des populations, en
entraînant la mort sélective des plus faibles et la survie des individus les mieux adaptés à leur
environnement.
De son côté, John Mendel, le fondateur de la génétique, avait effectué des travaux sur
l ‘hérédité, entre 1859 et 1866 [Mendel, 1865] qui expliquent les lois de transmission des
caractères à travers les générations dans le cadre d’une reproduction sexuée. Les
caractéristiques héréditaires sont ainsi localisées dans le génome, qui constitue le patrimoine
génétique de chaque individu. Le patrimoine génétique est composé de gènes, codant les
protéines responsables de l’architecture et du fonctionnement au niveau cellulaire. Les gènes
constituent, à ce titre, l’unité sémantique du langage génétique. La reproduction sexuée met
32
La synthèse des ses deux théories augmentée de la découverte de l’ADN a donné naissance au
néo-darwinisme qui a inspiré plus tard les chercheurs informaticiens pour le développement
des modèles artificiels de l’évolution intégrant des propriétés telles que la mutation et le
croisement et leur application au domaine de l’optimisation. Parmi ces modèles on trouve une
classe d’algorithmes regroupés sous le nom générique les algorithmes évolutionnaires (AE)
apparus dans les années 70 avec les travaux de Ingo Rechenberg et ceux de Hans-Paul
Schwefel [Schwefel, 1981].
Comme exemple des AE, les Algorithmes génétiques (AG) sont certainement la branche des
AE la plus connue et la plus utilisée de ces techniques qui se différencient dans leurs façons
de coder les individus (donc modéliser le problème à résoudre) et par leur façon de faire
évoluer la population, mais ces versions sont toutes basées sur les mêmes principes de base.
Une étude comparative de ses méthodes est présentée dans [Hoffmeister, 1991].
Le principe de base est de mimer ces deux mécanismes pour faire évoluer une population de
solutions (représentant des individus) afin d’obtenir des solutions de qualité de plus en plus
meilleure. Un algorithme génétique est simple à mettre en œuvre et se décrit par les points
suivants :
1) Choix d’un codage approprié pour les individus de la population. Ce codage doit être
complet et capable de coder toutes les solutions possibles. Dans un premier temps,
Holland a utilisé un codage sous forme de chaîne de bits de longueur fixe afin de
maintenir le plus possible l’analogie avec la structure protéinique de l’ADN. Le
codage binaire possède l’avantage supplémentaire de fournir un langage quasi-
universel, indépendant du problème traité. Le codage binaire d’un individu est appelé
33
Individu ou chromosome
évaluation
f (10110110) = 4
Point de croisement
Echange de l’information
Changement de l’information
Figure 2.5. Opérateur de mutation appliqué à deux chromosomes codés sur 8 bits.
Toutefois, la recherche d’une solution par les AG ne garantit pas l’obtention d’une solution
optimale. Une population initiale mal choisie, une convergence trop rapide vers un optimum
local, etc., peuvent bloquer le processus de résolution. Il n’existe pas de méthodes qui
permettent de dire quelle est la taille optimale de la population, quel est le meilleur codage,
quel taux de mutation et de croisement utiliser. Ces paramètres de fonctionnement dépendent
de l’application et, bien souvent, ils sont fixés de façon empirique.
36
2.5.1.2 Références
Plusieurs types d’évolution ont été développés, donnant naissance à différents types d’AE
qu’on peut regrouper en trois grandes classes : les algorithmes génétiques [Holland, 1975];
[Goldberg, 1989], les stratégies d’évolution, [Rechenberg, 1973 ; Schwefel, 1981] et [Herdy,
1991], la programmation évolutive, [Fogel, 1966], et la programmation génétique, [Koza,
1992 ; Koza 2003]. On peut aussi citer les travaux d’Evelyne Luthon [Lutton 2003]qui
utilisent les fractales pour la compréhension des fonctionnement du calcul évolutionnaire ainsi
que celui de Michel Sebag [Ratle, 2003] qui s’intéresse de plus prés à la programmation
génétique.
Les réseaux de neurones formels sont des modèles théoriques de traitement de l’information
inspirés des observations relatives au fonctionnement des neurones biologiques et du cortex
cérébral. Par analogie aux neurones biologiques, les neurones artificiels ont pour but de
reproduire des raisonnements « intelligents » d’une manière artificielle. Ces neurones peuvent
adopter de certaines qualités habituellement propres au biologique, c’est-à-dire, la
généralisation, l’évolutivité, et une certaine forme de déduction.
• Les dendrites qui sont des ramifications du corps cellulaire. Elles permettent au
neurone de capter les signaux lui parvenant de l’extérieur ;
• L’axone généralement plus long que les dendrites, il se ramifie à son extrémité où il
communique avec les autres neurones. Il sert de moyen de transport pour les signaux
émis par le neurone.
37
• Les connexions entre neurones sont réalisées au niveau des synapses, lieu de proximité
d’axone émetteur et de dendrites réceptrices.
Le neurone biologique reçoit des impulsions de ses neurones voisins avec lesquels il est
connecté à travers les synapses. Les influx nerveux transmis par les dendrites sont sommés. Si
la sommation dépasse un seuil, le neurone répond par un influx nerveux ou un potentiel
d’action qui se propage le long de son axone. Si la sommation est inférieure au seuil, le
neurone reste inactif. Les premières cellules qui alimentent le réseau peuvent être constituées
par des capteurs (cellules sensorielles ) comme les cellules de la rétine de l’oeil ,par
exemple.
Un RN est caractérisé par sa topologie (figure 2.9.)qui dépend de la façon dont les neurones
sont reliés (réseaux en couche, complètement connecté, récurrent ), par sa fonction
d’activation (figure 2.10.) et par le mode d’apprentissage utilisé (supervisé, non supervisé).
sorties
Couche cachée
entrées
D’une façon plus générale, on définit un neurone formel par les cinq paramètres suivants :
2.5.2.3 Références
Depuis le neurone de McCulloch et Pitts[McCulloch, 1943] et les travaux de Hebb [Hebb,
1949] sur les modèles d’apprentissage présentés dans son ouvrage « The Organization of
Behavior », les réseaux de neurones ont commencé à évoluer. En 1958, Frank Rosenblatt
proposa le Perceptron [Rosenblatt, 1958]. C’est un réseau de neurones inspiré du système
visuel. Il possède deux couches de neurones: une couche de perception et une couche de sortie
liée à la prise de décision. C’est le premier système artificiel capable d’apprendre par
expérience. Dans la même période, L’Adaline (ADAptive LINar Element) [Widrow ? 1960] a
été présenté par B. Widrow, chercheur américain à Stanford. En 1969, M. Minsky et S.
Papert publient leur livre Perceptrons [Minsky 1969] qui était une critique des propriétés du
Perceptron en montrant qu’il ne peut apprendre que des fonctions séparables linéairement
(figure 2.11).
Cette limitation va avoir une grande incidence sur la recherche dans ce domaine, qui va
fortement diminuer jusqu’en 1972, où T. Kohonen présente ses travaux sur un nouveau
modèle de réseaux de neurones connu sous le nom « les cartes de kohonen ». Les cartes auto-
organisatrices de Kohonen, appelées aussi cartes auto-adaptatives, sont des réseaux de
neurones formels qui vont s’auto-organiser pour réaliser un objectif [Kohonen, 2001]. Ce type
de réseaux tient compte de la proximité géographique des données d’entrées dans le
fonctionnement des neurones. C’est à dire que l’algorithme permet d’assurer que les données
projetées dans un même voisinage sont des données proches. Ces systèmes sont donc
principalement utilisés pour des applications de clustering (regroupement), de topologie ou de
classement de données. Dans une carte de kohonen, tous les neurones de la carte sont
interconnectés. Le plus souvent une grille à deux dimensions est utilisée comme support des
neurones. Les poids des arcs de connexion entre deux neurones dépendent de leur proximité.
Plus deux neurones sont proches, plus leurs poids sont élevés. Le fonctionnement est simple :
on présente un objet en entrée du réseau, et le réseau active en sortie le neurone dont le poids
est le plus proche. Ensuite, les poids sont mis à jour non seulement pour le neurone activé
40
mais aussi pour les neurones voisins de ce dernier. Au cours des itérations, la configuration
du voisinage peut décroître afin de stabiliser les poids.
En 1982 J. Hopfield présente son étude d’un réseau complètement rebouclé [Hopfield, 1982],
dont il analyse la dynamique, suivis des travaux de Rumelhart qui introduisa en 1985 les
réseaux multicouches avec la rétropropgation du gradient [Rumelhart, 1986]comme
algorithme d’apprentissage. De nos jours, les réseaux multicouches et la rétropropagation de
gradient reste le modèle le plus étudié et le plus productif au niveau des applications.
exemples
Catégories
linéairement
séparables Contre
exemple
Dans leur principe de base, les RN reposent entièrement sur les concepts d'auto-organisation
et d'émergence : des règles locales de base d'interaction entre de nombreuses entités qui
produisent au niveau global des comportements de plus haut niveau qui ne sont pas décrits au
sein des règles. Si on leur rajoute en respectant toujours ces principes des capacités de
création de neurones formels et d'apparition de nouveaux liens, ils présentent une technique
intéressante pour la résolution de problèmes par émergence.
des règles locales très simples comme « rester proche des autres individus », « aller dans la
même direction », « aller à la même vitesse », ces animaux sont capables d’éviter un
prédateur par des mouvements d’explosion puis re-forment le groupe originel, tout en
maintenant la cohésion du banc. Dans l’algorithme à essaim de particules, les individus de
l’algorithme sont appelés particules et la population est appelée essaim.
L’approche par PSO trouve ses racines dans les travaux de l’infographiste Craig Reynolds qui
fut le premier à modéliser ce genre de comportement collectif émergent par ses fameux boids
[Reynolds, 1987] (Figure 2.12). Les boids sont des individus autonomes. Chaque individu n'a
qu'une vision locale de son environnement (Figure 2.13)et son comportement va être le
résultat d'une somme d'attractions et de répulsions engendrées par son environnement direct,
codées par des règles très simples (Figure 2.14). :
Figure 2.14. Les trois règles trouvées par Reynolds pour programmer des mouvements
collectifs complexes.
La technique PSO utilise des règles de comportements locaux pour faire émerger à travers une
dynamique collective auto-organisée la valeur optimale d’une fonction de fitness. Chaque
particule est caractérisée par sa position (où la meilleure valeur pour sa fonction de fitness a
été rencontrée) et un vecteur de changement de position (appelé vélocité). À chaque itération,
une particule décide de son prochain mouvement en fonction de sa propre expérience, qui est
dans ce cas la mémoire de la meilleure position qu’elle a rencontrée, et en fonction de son
meilleur voisin. Ce voisinage peut être défini spatialement en prenant par exemple la distance
euclidienne entre les positions de deux particules ou sociométriquement (position dans
l’essaim de l’individu) (figure 2.15.).
Figure 2.15. Règles simples d’application locale utilisées dans un essaim de particules.
Cette méthode est facile à implémenter et donne de très bons résultats. Une présentation plus
détaillée de l’approche par PSO se trouve dans la synthèse en français de Clerc [Clerc, 2002].
L’exemple des fourmis est le plus répandu dans la littérature à cause de leur capacité à réaliser
des tâches hautement complexes à partir des interactions d’insectes simples à l’intelligence
très rudimentaire. [Deneubourg, 1990; Colorni, 1992; Dorigo, 1996; Bonabeau, 1997; Van
Dyke Parunak, 1997; Bonabeau, 1999; Topin, 1999a]. En particulier deux comportements
collectifs ont été principalement étudiés chez les fourmis : l’optimisation de chemin et le tri
des éléments du couvain.
Le second comportement collectif des fourmis concerne leur aptitude à nettoyer leur nid en
organisant collectivement des cimetières composés de cadavres empilés les uns sur les autres.
Le principe est le suivant : plus un cadavre est isolé, plus la fourmi a de chances de ramasser
ce cadavre. La probabilité pour une fourmi porteuse de déposer ce qu’elle transporte suit une
règle inverse : plus le monticule observé est important, plus la probabilité de déposer le corps
au sol sera grande.
2.6 Conclusion
Intuitivement, Le phénomène d’émergence peut être définit comme étant l’apparition d’une
propriété au niveau macroscopique d’un système sans qu’elle soit préalablement programmée
d’une manière explicite ni qu’elle puisse déduite à partir des propriétés des niveaux
microscopiques. Un moyen de mise en œuvre de l’émergence est l’auto-organisation qui fait
référence à un processus au cours duquel le système se restructure, se maintient sans
nécessiter une contrainte explicite qui provient de l’extérieur du système.
Avec la complexité croissante des systèmes informatiques et le besoin d’avoir des systèmes
adaptatifs et dynamiques, les méthodes classiques de résolution de problèmes sont devenues
inefficaces. Ce qui a conduit les chercheurs à explorer de nouvelles voies et de nouveaux
outils de développement. D’où l’utilisation de la notion d’émergence pour la conception de
nouveaux types de systèmes artificiels. L’objectif est de concevoir des systèmes complexes
constitués de petites entités en interaction entre elles et avec leur environnement et dont le
comportement global est émergent et peut être qualifié d’intelligent.
Chapitre 3
Les Fourmis artificielles
3.1 Introduction
Les études éthologistes ont montré que dans la nature, les petites créatures faibles que sont les
fourmis, arrivent à résoudre collectivement des problèmes quotidiens nombreux et trop
complexes pour une seule fourmi tels que : recherche de nourriture, construction du nid,
division du travail et allocation des tâches entre les individus, avec une organisation
excrément structurée et sans aucune supervision. Par les comportements simples de chacune
des fourmis, des interactions limitées à travers une coopération inconsciente, émergent des
comportements collectifs intelligents et des modèles d’auto-organisation [Bonabeau, 2000].
Les fourmis sont devenues dés lors une nouvelle source d’inspiration pour la conception de
méthodes de résolution de problèmes complexes. De plus cette source d’inspiration n’est pas
unique étant donné que les fourmis sont dotées d’une grande diversité de caractéristiques
disjointes et de comportements collectifs variés. Une nouvelle classe d’algorithmes est alors
apparue sous le nom « algorithmes de fourmis artificielles ». Leur popularité est due d’une
part à la facilité de mise en œuvre et d’autre part à la complexité des fonctions réalisables
[Deneubourg, 1990; Colorni, 1992; Dorigo, 1996; Bonabeau, 1997; Van Dyke Parunak, 1997;
Bonabeau, 1999; Topin, 1999a]. Deux comportements collectifs ont été principalement
étudiés chez les fourmis : l’optimisation de chemin et le tri des cadavres.
Le premier comportement appelé aussi fourragement permet aux fourmis de retrouver le plus
court chemin entre leur nid et une source de nourriture grâce à un système de marquage de
phéromones. Ce comportement naturel a été modélisé et transposé à la résolution de
nombreux problèmes d’optimisation combinatoires sous le nom d’une nouvelle
métaheuristique « optimisation par les colonies de fourmis ou OCF ». Le deuxième
comportement collectif des fourmis concerne la capacité de certaines espèces de fourmis à
organiser collectivement des cimetières composés de cadavres empilés les uns sur les autres.
Là aussi, les chercheurs ont exploité ce comportement pour fournir des algorithmes de
classification pour lequel l’informatique classique n’a pas donné de solution satisfaisante.
Dans la suite nous présentons une brève introduction au monde des fourmis, ensuite nous
décrirons en détail chacun des modèles de fourmis artificielles ainsi que les différents
algorithmes qui lui sont associés.
Selon les espèces, les fourmis vivent dans le sol, sous un caillou, dans le bois mort ou dans les
arbres. Certaines fourmis arboricoles construisent leurs nids dans les arbres, en cousant les
feuilles entre elles ou en élaborant une architecture faite de grains de sable, de salive et de
déjections. D'autres, comme les célèbres fourmis “légionnaires” d’Afrique, n'ont pas de nid et
48
se déplacent par centaines de milliers d'individus sur de vastes territoires, à la manière des
nomades.
La fourmi est un insecte exclusivement social vivant en société dans des habitations
collectives : la fourmilière. La fourmilière classique est constituée par un ensemble de cellules
réunies entre elles par un réseau complexe de galeries qui peut être très important. Dans ces
cellules, les fourmis déposent les oeufs, les larves et les nymphes. La fourmilière et ses
environs constituent le centre de la vie communautaire. A l’intérieur de la fourmilière les
tâches sont divisées entre les fourmis selon la spécialité de chacune d’elles. Les activités des
communautés de fourmis sont caractérisées par un certain degré de division du travail
souligné par une différenciation fonctionnelle et anatomique des individus. Une fourmilière
peut abriter de 50.000 à plus de 1.000.000 individus bien différenciés tant au niveau physique
qu’au niveau des comportements et des tâches à accomplir. On les sélectionne en castes :
Les reines : Dans une fourmilière on trouve une ou plusieurs reines. Les reines sont nettement
plus grosses que les autres fourmis et peuvent vivre jusqu'à dix ou quinze ans. Leur rôle se
résume essentiellement à pondre des œufs et sont donc les fondatrices de nouvelles colonies..
Les ouvrières : Elles forment la majorité des habitants de la cité et se chargent de la défense
et de l'entretien de la colonie, qui comprend la construction des galeries, les soins apportés
aux jeunes, la quête de la nourriture, etc...
Les soldats : Ils sont plus massifs que les ouvrières, et possèdent souvent de grosses
mandibules. Leur rôle est de défendre la fourmilière, et de transporter des charges lourdes.
Mais certains, comme chez les fourmis "Grand Galop" Camponotus maculatus, participent
aux soins des larves, et donnent à manger aux fourmis qui le demandent. Chez cette espèce,
qui est la plus grosse fourmi vivant à La Réunion, on peut distinguer des formes
intermédiaires entre la petite ouvrière grêle et le puissant soldat.
Les jeunes sexués ce sont des fourmis femelles et males. Ils sont facilement reconnaissables
par leur plus grande taille, par la présence de deux paires d’ailes membraneuses sur le thorax
et par 3 ocelles disposés en triangle sur le dessus de la tête. Les femelles sont plus grosses que
les mâles. Ce sont les futurs rois et reines qui iront fonder de nouvelles colonies.
Le couvain Il est constitué par les oeufs, les larves et les nymphes. Au bout de quelques jours
les oeufs donnent naissance à des larves qui, bien nourries par les ouvrières pendant 15 jours à
3 semaines, se transforment en nymphes. Pendant la nymphose, la larve ne se nourrit plus.
49
Son corps tout entier subit de profondes mutations internes et externes, qui vont faire d'elle,
petit à petit, une fourmi.
Les communications interindividuelles entre fourmis sont de plusieurs types et varient d'une
espèce à l'autre. Les principaux moyens de communication sont :
La communication sonore : les fourmis peuvent également utiliser des stimuli vibratoire
comme moyen de communication. Elles frappent les parois de la fourmilière avec leur
abdomen pour prévenir les autres. Elles tapotent aussi leurs antennes pour se parler. Ce signal
est utilisé en fonction de l'espèce comme signal de détresse en cas de danger, comme signal
de qualité de l'alimentation pour le recrutement pour une source de nourriture, comme signal
de demande d’aide en cas où la nourriture trouvée est de grande taille..
La totalité des espèces de fourmis vit en effet en communautés49 plus ou moins importantes,
qui sont qualifiées d'"eusociales" par [Wilson, 1985], ce qui signifie qu'elles sont caractérisées
par la présence simultanée et constante des trois critères suivants:
Un problème d’optimisation combinatoire est tout problème d’optimisation pour lequel il faut
trouver une solution optimale avec un espace de recherche de solutions fini mais extrêmement
grand. Ce type de problème est dit « difficile ».
• Les méthodes exactes (déterministes) : elles fournissent une solution optimale au prix
d’un temps de résolution qui risque d’être exponentiel en fonction de la taille des
données du problème.
a)Les heuristiques
Une heuristique est une méthode approchée simple, rapide et dédiée à un problème donné.
Elle exploite les propriétés structurelles d’une solution et tente de la rendre rapidement une
51
b)Les métaheuristiques
Une métaheuristique est une méthode approchée générique dont le principe de
fonctionnement repose sur des mécanismes généraux indépendants de tout problème. Les
métaheuristiques sont stochastiques et donc peuvent éviter d’être piégés dans des minimums
locaux. Elles sont principalement guidées par le hasard (exploration aléatoire de l’espace de
recherche), cependant elles sont souvent alliées à d'autres algorithmes afin d'en accélérer la
convergence.
différents chemins en effectuant des déplacements aléatoires. Une fois qu’un chemin
intéressant (menant à une source de nourriture) est découvert, elles y déposent une quantité de
phéromone renfonçant ainsi son importance et la probabilité d’être choisi par d’autres fourmis
de la colonie. D’un autre côté, les mauvais chemins auront tendance à être oubliés voir même
disparaître avec l’évaporation de la phéromone. Ce procédé basé sur le mécanisme de
rétroaction positive, assure que pendant le fourragement pour la nourriture, les fourmis
utilisent la voie d'accès la plus courte car elle sera le plus imprégnée par la phéromone.
Figure 3.3. Les fourmis suivent indifféremment les deux branches du pont.
53
Figure 3.4. Les fourmis ont tendance à emprunter le même chemin (celui d’en bas).
rapidement la concentration en phéromones sur ce nouveau chemin que celles qui ont choisi
le chemin le plus long. Ainsi la concentration de phéromone sur le plus court chemin va
augmenter, incitant ainsi d’autres fourmis à choisir le chemin riche en phéromones. Du à ce
processus auto-catalytique, les fourmis vont finalement choisir le chemin le plus court (figure
3.6c).
Le PVC est modélisé par un graphe G(V,E) où E est l’ensemble des nœuds représentant les
villes à visiter, et V est l’ensemble des arêtes. Une arête existe entre deux nœuds du graphe
s’il existe un chemin reliant les deux villes qu’ils représentent. On utilise alors un graphe
valué dont les arêtes sont étiquetées par la distance séparant deux villes.
Initialement, m fourmis sont placées aléatoirement sur les nœuds du graphe. Ensuite chacune
des fourmis se déplace d’un nœud à un autre en parcourant les arêtes du graphe. Ce
déplacement dépend de la liste des villes déjà visitées représentant la mémoire de la fourmi et
d’une probabilité fonction de la distance reliant les villes et de la quantité de phéromone
présente sur les arêtes du graphe.
L’algorithme AS est constitué d’un nombre d’itération appelée « cycle ». A chaque cycle,
chaque fourmi k (k = 1…..m) parcourt le graphe en se déplaçant d’un nœud vers un autre. Le
choix du passage d'un nœud i à un nœud j se fait aléatoirement en fonction d'une probabilité
donnée par l'équation 3.1.
(3.1)
0 sinon
Où
• τ ij (t) est la quantité de phéromone présente sur l’arête (i,j). Cette information
dynamique représente la désirabilité acquise de sélectionner j comme destination de i.
• J ik est la liste de villes visitées par la fourmi k placée sur le nœud i. Cette mémoire
joue un double rôle : d’une part elle empêche la fourmi de retourner sur des villes déjà
visiter et d’autre part elle permet la sauvegarde le chemin parcouru par la fourmi afin
de déposer les phéromones à la fin de chaque cycle.
• α et β sont des constantes qui servent à régler l'importance relative que l'on donne à
l’heuristique et à la phéromone. Avec α = 0 seule la visibilité de la ville est prise en
compte et la ville la plus proche est donc choisie à chaque déplacement.
Avec β = 0 seule les traces de phéromones sont prises en compte. Un compromis entre
56
Après n itérations, lorsque toutes les fourmis ont construit un chemin complet, chacune d'elles
calcule la longueur totale parcourue Lk (t ) (somme des distances d'une ville à l'autre). Les
quantités de phéromones sont mises à jour :
m
τ ijt +1 =τ ijt (1− ρ ) + ∑∆τ ijk (t) (3.2)
k =1
où ρ est un coefficient d’évaporation des traces de phéromones présentes sur les arêtes.
∆τ k
ij (t ) représente le cumul de phéromone que chaque fourmi dépose sur l’arête qu’elle a
suivit entre l’itération t et t+1. Cette valeur est inversement proportionnelle à la longueur du
chemin construit par la fourmi: plus le chemin est court, plus il sera chargé en phéromones.
Cette valeur est donnée par :
Q si (i, j) ∈ T k (t ) (3.3)
k
∆ τ (t )= L (t )
k
ij
0 sinon
où T k (t) est le trajet effectué par la fourmi k à l’itération t et Q est un paramètre constant.
Le procédé est alors recommencé jusqu'à ce l'on obtienne une solution optimale ou jugée
acceptable. L’encadré 3.1. décrit le comportement de l’algorithme AS pour le PVC.
- La coordination des différentes fourmis a été sensiblement améliorée par l’apparition d’une
fourmi particulière, la reine [Taillard, 1999]. Cette dernière prend en charge la gestion de la
mémoire collective de la colonie (les traces) et effectue les décisions stratégiques (fouille,
prospection) en fonction de l’évolution globale de la recherche. Elle constitue de fait une sorte
d’agent “intelligent”
Dans la suite de cette section, nous présentons les deux variantes de AS les plus connues.
o Une mise à jour locale est effectuée à chaque fin de cycle d’une fourmi.
o Une mise à jour globale est faite une fois que toutes les fourmis ont terminé
leurs cycles. Seule la fourmi qui a trouvé la meilleure solution est autorisée à
renforcer la phéromone sur tous les arcs constituant son tour.
La mise à jour globale évite de se bloquer dans des solutions sous optimal(minimums
locaux).Tandis que la mise à jour locale a pour effet de réduire, de moins en moins,
l’interactivité des arcs déjà visités par d’autres fourmis, et donc de favoriser l’émergence de
d’autres solutions que celle déjà trouvées pendant les prochains cycles de l’algorithme.
Dans [Stuzle, 1999; Stützle, 2000] Stutzle et Hoos introduisent MMAS algorithme. Les
modifications introduites concernent :
• La mise à jour des traces de phéromones n’est autorisée que par la fourmi ayant trouvé
la meilleure solution.
Learning »)[Semet, 2003].Une bonne synthèse de ces algorithmes est reportée dans [Dorigo,
2004].
D’une manière générale, l’utilisation de OCF nécessite de choisir une représentation formelle
du problème d’optimisation à traiter et de définir le processus de construction de solutions par
les fourmis en utilisant cette représentation.
Suivant cette représentation, les fourmis construisent les solutions possibles en se déplaçant
sur un graphe G =(C,L ) associé au problème d’optimisation, tel que les nœuds sont les
composantes C du problème qui forment les solutions et les arcs sont les transitions possibles
L qui connectent les composantes de C, telle que à chaque transition on associe une fonction
de coût. Les contraintes du problème sont implémentées directement dans les règles de
déplacement des fourmis. Par conséquent, la solution optimale représente le chemin de Coût
minimum.
Chaque connexion (ci ,c j )∈L (arc) peut être pondérée par une valeur de phéromone artificielle
τ ij représentant une mémoire collective de la colonie de fourmis et permettant les interactions
entre les fourmis (stigmergie), et si elle existe une valeur heuristique ηij qui représente une
information a priori propre au problème à résoudre. Pour certains problèmes, les traces de
phéromones et la valeur de l’heuristique peuvent aussi être associées aux composants du
graphe.
• Parcourir le chemin à l’envers pour faciliter la mise à jour des traces de phéromones
une fois la solution générée.
La construction de la solution par une fourmi k se fait d’une manière incrémentale en ajoutant
à chaque déplacement un nouveau composant. Le processus de construction se termine pour
la fourmi k si au moins un des critères de terminaison ek est vérifié.
Quand la fourmi k est sur un nœud Ci elle choisit un prochain nœud C j parmi les nœuds
possibles dans un voisinage accessible Nik . Ce déplacement est choisi en appliquant une règle
de décision probabiliste. Cette règle est soit fonction
• Des informations locales qui sont fonctions des traces de phéromones et de la fonction
heuristique.
Une fois la solution construite, les fourmis mettent à jour la trace de phéromone des
transitions (ou composant) qu’elles ont utilisé. La mise à jour des traces de phéromone peut se
faire de deux manières :
61
• A chaque déplacement d’un nœud Ci vers un nœud C j la fourmi laisse une trace de
phéromone sur l’arc de transition (Ci , C j ) on parle de mise à jour de phéromone en
ligne pas à pas
• Quand la fourmi a terminé la construction d’une solution, elle refait son chemin à
l’envers et mets à jour la trace de phéromone des arcs appartenant à sa solution. On
parle de mise à jour de phéromone en ligne retardée.
En plus de ces règles de comportement des fourmis, un autre processus est introduit :
l’évaporation des traces de phéromones qui permet de décroître les quantités des traces de
phéromones et donc évite que certains ars soient plus favorisés que d’autres à cause de la forte
concentration de phéromone présente sur eux, ce qui peut amener à une convergence rapide
vers une région sous-optimale de l’espace de recherche.
• Ils sont flexibles : ils peuvent être facilement réutilisables pour des versions modifiées
d’un même problème ;
• Ils sont robustes et nécessitent peu de changement pour leur application à de nouveaux
problèmes d’optimisation combinatoires ;
• Lorsqu’une fourmi rencontre un élément du couvain, plus cet élément est isolé, plus
elle a de chance de le ramasser ;
tâche de déplacer les objets en fonction de la concentration des objets de même type dans leur
environnement proche appelé « voisinage »..
Le principe est de regrouper les objets similaires en des groupes sur une grille. Chaque fourmi
peut prendre un objet avec une probabilité fonction de sa similarité avec les objets présents
dans son voisinage et le déposer selon la même probabilité. Après un certain nombre
d’itérations, des groupes d’objets similaires se forment sur la grille. La principale
caractéristique de ces algorithmes est leur coté non supervisé qui permet de découvrir
automatiquement le nombre de groupe adéquat sans intervention extérieure comme dans les
algorithmes classiques de classification. Les opérations de dépôt et de ramassage des objets
sont biaisées par les probabilités Pp et Pd représentées par
k (3.4)
Pp = 1
k1 + f
2
f (3.5)
pd =
k2 + f
f est une estimation du nombre d’objets placés dans le voisinage de la fourmi. k1 et k2 sont
des constantes positives. Quand f << k1 cela signifie qu’il y a peu d’objets dans le voisinage
de l’objet et donc la probabilité de le prendre est élevée (Pd est proche de 1). Inversement
quand f >> k1 la probabilité de prendre l’objet est faible s’il est entouré de plusieurs objets.
Deneubourg et al utilisent les valeurs de k1 = 0.1 et k2 = 0.3.
Comme on le constate le mécanisme de rétroaction positive est présent mais agit d’une
manière différentes par rapport à celui décrit dans les algorithme de OCF. Les fourmis ne
communiquent plus par trace de phéromones mais c’est la distribution des objets sur la grille
qui est à la base de leur communication et coopération indirecte « stigmergie »
Cet algorithme de classification par les fourmis a trouvé ses premières applications en
robotique collective |Beckers, 1994 ; Martinoli, 1999; Melhuish, 1999].
• La similarité entre deux données est mesurée comme une distance euclidienne entre
leur vecteur de caractéristiques.
• La fourmi est capable de percevoir une région Rs de s×s cases autour de sa position
courante sur la grille.
La figure 3.7. représente un exemple de grille utilisé dans l’algorithme de Faieta et Lumer.
Les objets sont représentés par des cases de deux motifs décrivant leurs types et le rectangle
en trait épais est la région perçue par la fourmi.
2
k1 (3.6)
Pp (i)=
k1 + f(i)
avec
65
1 d(i, j)
s 2 ∑ 1− α si f > 0 (3.8)
f(i)= j∈Rs (r(i))
0 sinon
r(i) est la position de l’objet i sur la grille. f(i) est une mesure de similarité moyenne de l’objet
i avec les objets j de son entourage. Le facteur α contrôle la consistance de la fonction de
dissimilarité entre les objets. Si α est trop élevé les objets différents seront mis dans la même
classe dans le cas contraire les objets similaires ne seront pas regroupés ensembles. Les
probabilités de déplacement et de dépôt d’objets deviennent. Les tests ont été menés avec
k1=0.1, k2=0.15, R=9, α= 0.5
L’encadré 3.3. résume les étapes de l’algorithme de Lumer et Faita. A fourmis sont utilisées
pour effectuer la tâche de classification de N objets.
Les résultats obtenus ont montré que l’algorithme génère un nombre de classes qui est très
souvent très éloigné du nombre réel de classes. Afin de remédier à cela, Lumer et Faieta ont
introduit trois extensions au comportement de base des fourmis artificielles :
• Les fourmis se déplacent sur la grille avec une vitesse propre à chacune d’elles
comprise entre 1 et vmax = 6 . Les fourmis les plus rapides sont moins sensibles aux
66
• Chaque fourmi possède une mémoire à court terme lui permettant de se souvenir des
positions des m derniers objets classés. Si une fourmi transporte un objet, elle cherche
dans sa mémoire l’objet déjà classé qui est le plus proche de celui qu’elle transporte.
Si elle le trouve, elle se déplacera (avec une certaine probabilité) vers ce nouvel
emplacement pour y déposer son objet.
• Si au bout d’un certain nombre d’itérations la fourmi stagne (ne fait plus aucun
déplacement) elle peut détruire un groupe en ramassant l’objet le plus éloigné du
groupe.
Dans [Kanade, 2003] Kanade et Hall reprennent les travaux de Monmarché et combinent
l’algorithme de fourmis qu’il a proposé avec l’algorithme classique de classification FCM
[Bezdek, 1981]. Dans une première étape, l’algorithme de fourmis est utilisé initialement pour
fournir une première classification qui sera par la suite raffinée en utilisant l’algorithme FCM.
Dans une seconde étape, les centres de classes obtenus par FCM sont considérés comme de
nouveaux objets à classes. Ces derniers seront par la suite déplacés et fusionnés par les
fourmis. A la fin, les classes obtenues par l’algorithme de fourmis sont une autre fois raffinée
par l’algorithme FCM.
67
Dans sa thèse Labroche a introduit un nouveau modèle à base de fourmis pour la classification
utilisant le système d’identification chimique des fourmis [Labroche, 2002]. Dans la nature,
les éthologistes ont montré que chaque fourmi arrive à reconnaître ses congénères qui
appartiennent à sa colonie à partir d’une odeur coloniale qui est le fruit des apports
génétiques, environnementaux et comportementaux. A partir de ce mécanisme d’identification
un nouvel algorithme de classification a été proposé dans lequel chaque donnée est une
fourmi dont l’odeur est déterminée par les valeurs prises par les attributs décrivant cette
donnée. Les fourmis effectuent des rencontres aléatoires et décident qu’elles appartiennent ou
non à la même classe en fonction de cette odeur.
68
En s’inspirant toujours du comportement des fourmis, Azzag proposa dans [Azzag, 2004] un
nouvel algorithme de classification automatique qui trouve son origine dans la manière dont
les fourmis réelles forment des structures vivantes est proposée. Il s’agit d’une méthode de
classification hiérarchique distribuée qui simule le phéronome d’auto-assemblage observé
chez les fourmis pour regrouper les données selon un arbre. Chaque fourmi représente une
donnée à classer. A partir d’un point de support fixe sur lequel sont situées initialement les
fourmis (répartition des données), ces dernières vont s’accrocher successivement au support,
puis aux fourmis connectées au support, et ainsi de suite jusqu’à ce que, par exemple, une
chaîne de passage soit construite entre deux points. Les fourmis se déplacent sur la structure
vivante et s’accrochent sur celle-ci aux endroits les plus opportuns en fonction du but à
atteindre (plus grande similarité avec les fourmis de la structure).
3.6 Conclusion
Dans ce chapitre, nous avons présenté les algorithmes à base de fourmis artificielles inspirés
de comportement collectif des fourmis pour la résolution des problèmes d’optimisation
combinatoires et le problème de classification automatique. Ces systèmes auto-organisés et
non centralisés utilisent une population de fourmis artificielles autonomes et d’une
intelligence très réduite. Chaque fourmi n’a qu’une perception réduite de son environnement
et ne fait qu’agir/réagir aux différents stimulus venant de son environnement. La coordination
du comportement de la colonie se base sur un processus stigmergique.
Dans OCF, des agents fourmis coopèrent ensemble au sein de leur colonie, en cherchant en
parallèle une solution optimale (ou sous optimale) au problème sous étude. Chaque fourmi
construit une solution candidate même de mauvaise qualité. La solution optimale émerge de la
coopération entre les fourmis. Lors de la construction de sa solution, la fourmi accumule des
informations sur l’environnement parcouru. Ces informations sont stockées sous forme de
taux de phéromones et seront échangées d’une manière indirecte avec les autres fourmis de la
colonie. La construction des solutions est incrémentale selon un processus stochastique. A
chaque étape du processus de construction, la fourmi choisi un élément de la solution parmi
les éléments possibles d’une manière probabiliste guidée par deux mesures : une quantité de
phéromone associée à l’élément et reflétant l’expérience accumulée des autres fourmis, et une
information heuristique propre au problème à résoudre. Une fois qu’une fourmi a terminé la
construction de sa solution, elle met à jour le taux de phéromones qui correspond à ses choix
en fonction de la qualité de la solution qu’elle a trouvé. Cette mise à jour a pour but le
renforcement de la probabilité de choisir les éléments qui conduisent à la bonne solution par
les autres fourmis lors des prochaines itérations. Afin d’améliorer la qualité des solutions et
accélérer la convergence, les algorithmes de fourmis sont très souvent hybridés avec une
méthode de recherche locale.
69
Les algorithmes de fourmis pour la classification non supervisée sont aussi un autre modèle
inspiré du comportement collectif observé chez les fourmis tels que le tri collectif de
couvains, la reconnaissance chimique et l’auto-assemblage. Ces algorithmes peuvent
bénéficier de propriétés intéressantes comme l’optimisation locale et globale de la
classification, l’absence d’information sur une classification initiale des données, le
parallélisme, etc.
70
Chapitre 4
La segmentation d’images
Chapitre 4. La segmentation d’images................................................................................. 71
4.1 Introduction .............................................................................................................. 71
4.2 La vision artificielle ................................................................................................. 71
4.3 Architecture typique d’un système de vision ........................................................... 72
4.4 Techniques de segmentation .................................................................................... 74
4.4.1 Détection de contours....................................................................................... 75
4.4.2 Détection de régions homogènes...................................................................... 78
4.4.3 Les méthodes de classification........................................................................ 87
4.4.4 Les méthodes de segmentation biomimétiques................................................ 99
4.5 Méthodes d’évaluation des résultats de segmentation en régions.......................... 106
4.5.1 Evaluation par comparaison avec une segmentation de référence ................. 107
4.5.2 L’évaluation se référant à l’image originale .................................................. 111
4.6 Conclusion.............................................................................................................. 116
71
4.1 Introduction
Nous présentons dans ce chapitre, le contexte général dans lequel ce travail s’inscrit ainsi que
les différents problèmes abordés au cours de cette thèse. Dans un premier lieu, nous rappelons
brièvement quelques notions attachées à la vie artificielle. Ensuite nous passons en revue les
principales méthodes de segmentations développées dans le cadre de la segmentation
d’images. De nombreux algorithmes ont été proposé dans la littérature durant ces dernière
décennies [Zucker, 1976], [Haralick, 1985] , [Pal, 1993], [Cocquerez,. 1995a], [Freixenet,
2002], [Cho, 1997], [Heath, 1996], [Kara-Falah, 1995], [Palus, 1999], [Ramos, 1999], [Tang ,
1999]. Une étude comparative des méthodes de segmentation peut aussi être retrouvée dans
[Rouquet, 1998], [Salzenstein , 1998]. Ce chapitre porte un intérêt particulier pour les
méthodes de segmentation par classification car c’est le domaine d’application de cette thèse.
Ce tour d’horizon couvre les méthodes classiques de segmentation d’images ainsi que les
heuristiques biomimétiques. Cette présentation n’est pas exhaustive mais permet de présenter
les bases de chacune des techniques de segmentation.
Les applications des systèmes de vision se retrouvent d’ores et déjà dans de nombreuses
sphères d’activités que nous pouvons citer sans être exhaustifs :
· Le contrôle qualité,
· La cartographie aérienne,
72
Un système de vision artificiel peut être considéré comme un ensemble de tâches assurant le
passage d’une image naturelle acquise par des capteurs à une description structurelle puis
sémantique en passant par la segmentation et l’extraction des caractéristiques des objets de la
scène.
David Marr fut le premier chercheur à proposer une méthodologie pour la conception des
systèmes de vision artificielle connu par la suite sous le nom paradigme de Marr [Marr,
1980]. Selon lui, tout système de vision doit contenir trois niveaux (Figure 4.1)
• L'étude et le calcul des primitives présentes dans les images. Ce niveau nécessite, la
définition de modèles mathématiques des différents phénomènes observés dans les
images et servant à leur compréhension.
• L’interprétation
• L'acquisition d'une scène : elle permet de discrétiser l'image réelle continue afin
d’être traiter par l’ordinateur. L’image obtenue est de nature bidimensionnelle
discrète. A chaque élément (pixel) de l'image, correspond un vecteur de
caractéristique qui se réduit le plus souvent au niveau de gris.
• Les prétraitements: Une image brute est toujours entachée de dégradations d’origine
diverses, dont il va falloir essayer de minimiser l’influence afin d’obtenir l’image la
73
Le modèle présenté dans la figure 4.1. correspond à une architecture typique d’un système de
vision, mais d’autres variantes peuvent exister dans la littérature [Boucher, 1999].
Les étapes de vision peuvent aussi être groupées en deux grandes classes d’algorithmes : les
algorithmes bas-niveau qui concernent l’acquisition, les prétraitements, et la segmentation ;
les algorithmes haut-niveau qui groupent l’extraction des mesures et la phase d’interprétation.
La segmentation des images constitue le cœur de tout système de vision et une étape
importante dans le processus d’analyse des images [Cheng, 2001]. Elle a pour objectif de
fournir une description des objets contenus dans l’image par l’extraction de différents indices
visuels tels que les contours des objets, les régions homogènes, les objets 3 D. Ces indices
visuels représentent des phénomènes photométriques et/ou géométrique présents dans
l’image. Ils seront exploités ensuite par les traitements placés en aval pour une description
symbolique de la scène permettant une interprétation et éventuellement une prise de décision.
74
La segmentation peut être basée directement sur le niveau de gris ou la couleur de chaque
pixel ou bien sur un attribut estimée dans le voisinage du pixel, tel que la valeur moyenne, la
variance ou des paramètres de texture plus complexes. La phase de segmentation d’images
n’est pas considérée comme un but en soi [Zhang, 1997 ;Baradez, 2004], mais dépend
fortement aussi bien du type de traitement fixé par l'utilisateur sur les objets présents dans
l’image, que de la nature de l’image (présence de bruit, présence de zones texturées, contours
flous....), ainsi des primitives que l’on cherche à extraire de l’image et qui dépendent des
opérations situées en aval de la segmentation (localisation, calcul 3D, reconnaissance de
formes, interprétation).
Ces aspects, ainsi que les contraintes d’exploitation (complexité algorithmique, aspect temps
réel), justifient la multiplicité des techniques développées dans le domaine de la segmentation
d’image. Jusqu’à ce jour, il n’existe pas de méthode universelle de segmentation d’images.
Toute technique n’est efficace que pour un type d’image donné, pour un type d’application
donné, et dans un contexte informatique donné. En raison de ces contraintes, diverses
stratégies de segmentation ont été proposées dans la littérature. La suite de ce chapitre
présente les stratégies de segmentation les plus utilisées.
Dans la suite de ce chapitre, nous allons décrire quelques algorithmes de ces trois catégories
sans pour autant prétendre à une présentation détaillée de l’ensemble des méthodes de
segmentation. Nous présenterons de façon succincte l’approche « contour » de la
segmentation, puis de façon un peu plus précise l’approche « région » et l’approche
« classification » contexte de ce travail de thèse.
75
Nous présentons dans ce qui suit les principales méthodes de détection de contours.
que les opérateurs de dérivation sont très sensibles au bruit, les images bruitées doivent être
lissées au préalable. Le lissage et la dérivation sont en pratique réunie dans un seul filtre.
L’allure de la dérivée première et de la dérivée seconde est donnée par la figure 4.3. Une zone
de transition dans le signal correspond à un maximum (ou un minimum) local de la dérivée
première et un passage par zéro de la dérivée seconde. L’identification d’une zone de
transition du signal peut être faite par seuillage de la norme de sa dérivée première ou du
passage par zéro de sa dérivée seconde.
Figure 4.4. Dérivées première et seconde d’un contour de type “saut d’amplitude”
Parmi les opérateurs gradient, on trouve le masque de Robert [Roberts 1965], de Prewit
[Prewit 1970], de Sobel [Sobel 1978], de Kirsh [Kirsh 1971]… Ces opérateurs sont faciles à
implémenter, rapides en temps de calcul et donnent de bons résultats pour des images non
bruitées. En cas de présence de bruit, une phase de seuillage est utilisée avant de procéder à
l’application de ces opérateurs. Le problème majeur des techniques exploitant le Laplacien
est sa grande sensibilité aux petites variations non significatives non significatives et qui sont
dues essentiellement à la présence du bruit. Une manière de résoudre ce problème est
d’utiliser un filtre gaussien comme proposé par Marr et Hildreth [Marr,. 1980]. La méthode
consiste à convoler l’image par une gaussienne puis d’appliquer le filtre Laplacien.
Pour améliorer la qualités des contours et pallier aux problèmes de précision de localisation et
d’efficacité de détection, sont apparus les opérateurs de dérivation avec filtrages optimaux. Le
77
filtre optimal est un dérivateur qui permet de détecter des contours en respectant les 3 critères
suivants [Canny, 1986]:
1. Une bonne détection : l'opérateur donne une réponse au voisinage d'un contour ;
2. Une bonne localisation : optimisation de la précision avec laquelle le contour est détecté;
Plusieurs opérateurs optimaux sont apparus dans la littérature. Parmi eux on trouve le filtre de
Canny [Canny, 1986], le filtre de Deriche [Deriche, 1987; Deriche, 1990] et le filtre de Shen
et Castan [Shen, 1986 ; Castan, 1989 ; Shen, 1992].
- Les approches surfaciques : L’image des intensités est considérée comme une surface. Dans
ce cadre, la transition entre deux régions est modélisée par un modèle surfacique. Le contour
est présent quand il y a une bonne corrélation entre le modèle surfacique et une zone de
l’image [Hueckel, 1971].
- Les approches contours actifs : Les contours actifs ou « Snakes » ont été introduits par
Kass et al. [Kass, 1988]. Ils se présentent comme un modèle pour l’extraction des
caractéristiques visuelles dans une image comme les contours d’objet ou les éléments
de frontières. L’idée de base est de positionner, au voisinage du contour à détecter, une
courbe qui sera l’initialisation du contour actif et de la déformer successivement
jusqu’à ce qu’elle coïncide avec la frontière de l’objet .
Une étude plus détaillée des méthodes de détection de contours, peut être trouvée dans
[Hejmans, 1993].
4.4.1.4 Conclusion
A partir de cette brève présentation de l’approche contour, nous pouvons tirer les conclusions
suivantes :
• Les détecteurs de contours donnent de bons résultats quand l’image traitée n’est pas
trop bruitée, dans le cas contraire ils nécessitent l’utilisation de filtres de lissage qui peuvent
affecter les frontières entre les régions homogènes et donc délocaliser les points de contours.
De plus le seuils sont difficiles à fixer sans une information a priori qui n’est pas toujours
disponible. Les filtres optimaux présentent un bon compromis entre une bonne détection et
une bonne localisation.
Il est courant de définir la segmentation d’une image I en terme d‘un prédicat d’homogénéité
P et d’un ensemble de « régions » Ri vérifiant les critères suivants [Zucker, 1976] :
1. I =∪Ri
i
2. Ri ≠φ ∀i ;
3. Rii ∩R j ∀i≠ j ;
4. Ri est connexe ∀i ;
5. P(Ri )=vrai ∀i ;
La vérification de ces conditions est une condition nécessaire et suffisante pour qu’une
partition d’une image soit une segmentation. Rien, toutefois, n’implique l’unicité de cette
segmentation. D’une part le nombre de régions obtenues est variable en fonction des prédicats
d’homogénéité ainsi qu’aux seuils de tolérance contrôlant leur formation. D’autre part ces
critères d’homogénéité doivent s’adapter, à la nature de l’image à segmenter.
• Les méthodes de fusion de régions qui procèdent par agrégation itérative des pixels
(ou de régions). L’algorithme s’arrête quand une segmentation optimale est atteinte au
sens d’un prédicat d’homogénéité.
• Les méthodes de division qui procèdent par division des régions de base en régions
plus petites et de plus en plus homogènes. La division s’arrête quand toutes les régions
produites vérifient un certain critère d’homogénéité.
Nous décrivons dans les paragraphes suivants les méthodes essentielles de chacune de ces
classes.
Agrégation de pixels
Le point de départ est le choix d'un ensemble de pixels appelés « germes ». A chaque germe
on associe un vecteur de caractéristiques. Chaque germe est agrégé avec le premier pixel
80
Les régions ainsi construites dépendent fortement du choix des germes de départ ainsi que de
l’ordre de parcours des pixels agrégés. La plupart des algorithmes de croissance de régions
parcourent l’image de façon prédéterminée de haut en bas et de gauche à droite [Kara-Falah,
1995; Adams, 1994; Menhert,1997]. Kara-Falah [Kara-Falah, 1995] propose une approche
originale pour l’extraction des germes. A partir de la réalisation de n segmentations possibles,
une segmentation consensus est obtenue par une mise en association des différentes régions
des n segmentations. Les noyaux des régions de cette segmentation sont alors considérés
comme des candidats pour être des germes de croissance de régions. Après un test de
stationnarité, seuls les germes qui correspondent à des régions homogènes sont conservés. La
croissance de régions est basée d’une part sur un critère d’homogénéité et sur une information
de contours ce qui permet d’éviter d’éventuels conflits aux frontières des régions.
Cette méthode est facile à implémenter mais pose certains problèmes tels que : le choix du
seuil de similarité: un seuil trop faible crée une sur-segmentation et s’il est trop fort conduit à
une sous-segmentation [Turi, 2001]. Monga propose une méthode de segmentation par
croissance de régions, en utilisant plusieurs prédicats d’uniformité qui sont de plus en plus
tolérants[Monga, 1987]. L'utilisation de prédicats emboîtés permet d’une part de limiter le
problème du choix du prédicat de fusion et d'autre part de corriger des erreurs de
segmentation produite à un niveau supérieur. Cependant le temps de calcul par rapport aux
méthodes de fusion classiques est plus important. Une autre difficulté de cette méthode réside
dans le choix de l’ordre d’emboîtements des prédicats.
81
Dans [Regina, 2001] un algorithme de croissance de région est proposé tel que le critère
d’homogénéité n’est pas fixé au départ mais est définit automatiquement à partir des
caractéristiques de la région à segmenter. La méthode est basée sur un modèle qui décrit
l’homogénéité et la forme de la région à segmenter. Les paramètres du critère d’homogénéité
sont estimés à partir des zones d'échantillon dans la région. Ces endroits sont choisis
séquentiellement à partir d’un point germe, et le critère d’homogénéité est mis à jour sans
interruption.
Dans [Kermad, 1995], une coopération entre une technique de seuillage et celle de fusion
de régions est proposée. Une segmentation initiale est obtenue par seuillage des
histogrammes locaux extraits sur des petites régions de l’image à traiter. Après, une fusion de
régions étiquetées minimisant un critère de similarité est effectuée.
Il existe plusieurs autres représentations pyramidales qui sont utilisées pour la segmentation
d’image. On peut mentionner la pyramide reliée[Burt, 1981], la pyramide reliée pondérée
[Hong, 1984], la pyramide à seuillage dynamique [Home, 1990] et la segmentation par
82
La division de l’image est réalisée selon une structure géométrique. Citons deux structures
possibles :
Niveau
0
Niveau
1
Niveau
3
• Structure de Voronoi: Au départ des germes initiaux sont choisis afin de construire les
polygones de Voronoi. Ensuite de nouveaux germes sont ensemencés d’une manière itérative
à l’intérieur de chaque polygone non homogène, modifiant ainsi le diagramme de Voronoi. Le
processus d’ensemencement de germes se poursuit jusqu’à ce que tous les polygones soient
homogènes ou bien que leurs tailles atteignent un seuil préfixé. Une des différences par
rapport à la structure précédente est que lorsqu'un polygone est partitionné, la topologie de
polygones voisins change aussi, s'adaptant à ce nouveau partitionnement.
continue. La division récursive prend fin quand toutes les régions ont un histogramme uni-
modal.
Chen et Pavlidis [Chen, 1978] reprennent cet algorithme pour segmenter des images au sens
de la texture. Pour évaluer l’homogénéité d’une région, ils suggèrent l’utilisation d’un test
statistique qui suppose que les moyennes des régions ne varient pas trop durant la phase de
division. Cette méthode bien qu’elle soit rapide et de taille mémoire relativement simple, crée
de faux contours entre les régions de l’image. De plus elle n’utilise aucun critère de forme
pour contraindre la fusion, ce qui occasionne parfois des régions particulièrement découpées.
Dans [Brice, 1970] , l’image est tout d’abord divisée en des régions d’intensités constantes.
Des heuristiques sont alors utilisées afin d’obtenir des régions dont les frontières sont
naturelles (faibles). Les régions dont les vecteurs de caractéristiques sont semblables sont
85
fusionnées. Ensuite, les frontières de faible niveau de gris sont supprimées, ce qui permet de
fusionner de nouvelles régions. Des pré-conditions sont prises afin d’éviter de fusionner des
régions de grandes tailles ne présentant que quelque pixels de frontières communes. Malgré
son optimalité et l'indépendance par rapport à l'ordre d'évaluation des arêtes, c'est une
approche séquentielle très coûteuse en temps de calcul.
Dans le même ordre d’idée, O. Monga et B. Wrobel [Monga, 1990] proposent un algorithme
de division/fusion dont la segmentation résultante peut être qualifiée de sous optimale. Pour
chaque critère de fusion, ils introduisent une fonction caractérisant la qualité globale de la
segmentation. L’optimisation se fait localement en déterminant à chaque itération le meilleur
couple de régions adjacentes à fusionner (celui qui minimise un coût local de fusion). A cette
fin, ils proposent d’utiliser la structure de graphe d’adjacence des régions qui évite de
parcourir toute l’image à chaque itération et qui permet une remise à jour facile après chaque
fusion. Dans une telle structure, les nœuds du graphe sont constitués par les régions, affectées
de leurs divers attributs radiométriques, topologiques......, et les arcs entre nœuds définissent
l’adjacence entre les régions : deux nœuds sont reliés par un arc si les deux régions sont
adjacentes. A chacune des étapes de fusion, il faut choisir le meilleur arc, c’est-à-dire choisir
parmi tous les couples de régions vérifiant le prédicat de fusion celui qui minimise la
fonction de qualité locale. De plus, lors de la réalisation de la fusion de deux nœuds, il faut
mettre à jour tous les attributs des nœuds et des arcs modifiés par cette fusion. Pour permettre
86
un accès rapide au meilleur arc, un arbre binaire de recherche est utilisé. La remise à jour du
graphe après chaque fusion est facile. Les attributs du nouveau nœud créé et des arcs
correspondants sont calculés directement à partir de ceux des deux nœuds fusionnés.
L’inconvénient majeur du Quadtree réside dans la rigidité du découpage carré qu’il impose. Il
conduit à un partitionnement global de l’image qui ne respecte pas toujours la forme des
régions présentes dans l’image. Par ailleurs, la phase de regroupement des blocs est sensible à
l’ordre du parcours du Quadtree.
4.4.2.4 Conclusion
• Les méthodes de fusion de régions sont faciles à implémenter, mais introduisent un
temps de calcul trop coûteux car elles impliquent à chaque itération, la recherche des couples
de régions à fusionner. Elles se distinguent selon l’ordre de parcours des différents nœuds du
graphe et selon les critères de fusion [Beveridge, 1989]. Un autre inconvénient des méthodes
de fusion de régions est qu’elles sont très sensibles au bruit car reposent sur des petites
87
régions à fusionner (ou bien des pixels à agréger) et que ces dernières véhiculent peu
d’informations. De plus, la segmentation dépend fortement des germes initiaux..
• Les méthodes de division sont efficaces surtout pour des images simples qui
contiennent peu de régions, et dont l'histogramme présente une bonne séparation entre les pics
afin de faciliter le choix de seuil. D’un autre côté, elles génèrent un effet de sursegmentation
dés qu’une petite variation du critère d’homogénéité est détectée car elles reposent sur des
statistiques globales.
• Les méthodes de division / fusion ont un temps de calcul moins important que les
autres méthodes, étant donné que le nombre de régions à fusionner peut être réduit au cours de
l’étape de division. Cependant elles sont peu robustes et sensibles aux résultats obtenus par la
phase de division. D’un autre côté, cette classe de méthodes conduit à des algorithmes
facilement parallélisables.
I =U Ci
i
Ci = U RCk , ∀ i
k i
Ci ≠φ ∀i ;
C i I C j ∀i≠ j ;
Il n’existe pas une méthode de classification qui peut s’appliquer à tout type d’image et qui
peut fournir un partitionnement optimal et le plus naturel possible. Ce qui explique la grande
diversité de méthodes de classification qui existe dans la littérature. Le choix d’une méthode
est déterminé par différents facteurs tels que le nombre de classes attendues, la forme des
classes extraites ou encore le chevauchement ou non des classes [Jain, 2000].
Il est possible de regrouper les méthodes de classification sous la forme d’une hiérarchie de
méthodes appelée taxonomie. Nous présentons ci-après la taxonomie inspirée de celle de Jain
et. al. dans [Jain, 1988 ; Jain,1999] (voir Figure 4.8.).
Méthodes de classification
Les méthodes de classification peuvent être divisées en méthodes dures et méthodes floues.
Dans une méthode de classification dure, un pixel ne peut être affecté qu’à une seule classe
dans la partition de l’image. Dans une méthode de classification floue, on affecte au pixel un
degré d’appartenance pour chacune des classes de la partition qui indique la probabilité que le
pixel y appartienne. La classe finale du pixel sera celle pour laquelle son degré
d’appartenance est le plus élevé.
Dans la classification supervisée, le nombre de classes est connu et on dispose d’un ensemble
de pixels déjà étiquetés, servant d’ensemble d’apprentissage. Il s’agit alors de pouvoir
associer chaque nouveau pixel à la classe la plus adaptée en se servant des pixels déjà
étiquetés. Dans la classification non supervisée, aucun information sur le nombre et le
89
contenu des classes possible n’est fournit. L’objectif est alors de pouvoir regrouper
automatiquement des pixels considérés similaires dans une même classe. Dans ce cas il
s’agira de définir une fonction de similarité entre pixels qui sera maximum entre les pixels
d’une même classe et minimum avec ceux des autres classes.
Les méthodes hiérarchiques produisent une hiérarchie de classes, telle que plus on descend
dans la hiérarchie plus on trouve des classes homogènes. A l’opposé, les méthodes de
partitionnement déterminent une seule partition.
K
K −1
K N (4.1.)
S(N, K) = 1 ∑(−1) (i )
K! i =1 i
On peut s rendre compte que pour un nombre de classes et de pixels même très réduit, le
nombre de combinaison explose considérablement. Il n’est pas possible alors d’énumérer
complètement les partitions de l’image pour déterminer exactement la valeur optimale du
critère de partitionnement. Une solution possible est d’utiliser des heuristiques qui permettent
de calculer une valeur approchée de la valeur optimale.
cj (4.3.)
Iint ra = ∑∑d 2(xij, µ j )
K
j =1 i =1
Iint er = ∑ c j d 2(µ j , µ )
K (4.4.)
j=1
91
avec :
d(.) est une mesure de distance, la plus connue est la distance euclidienne.
Les méthodes de classification par partitionnement sont fondées sur un processus itératif qui
converge vers une partition qui optimise un critère prédéfini [Hamerly, 2002]. Le nombre de
classes est spécifié a priori ou bien déterminé comme une partie de la méthode. Dans la suite
du paragraphe nous passons en revue les méthodes de partitionnement les plus connues.
Méthodes globales
Les méthodes de segmentation par seuillage global déterminent un seul seuil pour segmenter
l’image entière. La valeur optimale du choix du seuil peut être calculée à partir des niveaux de
gris de chaque pixel ou bien dépendre du voisinage immédiat de chacun d’eux [Kermad
1997]. Dans [Koller, 1995] les auteurs utilisent comme valeurs de seuils, celles qui
minimisent la somme des variances de niveau de gris de chacune des régions dont le nombre
est fixé par l’utilisateur. Quand les vallées sont difficiles à extraire à partir de l’histogramme
de niveau de gris les seuils peuvent être déterminés en analysant la concavité de
l’histogramme [Rosenfeld, 1983]. Pour améliorer la forme de l'histogramme et faciliter le
choix du seuil, certaines techniques sélectionnent les pixels à utiliser pour le calcul de
l’histogramme ou bien introduisent d’autres informations que le niveau de gris des pixels. Par
exemple dans [Watanabe, 1974], Watanabe propose de sélectionner une valeur de seuil qui
maximise la somme des gradients calculée sur tous les points dont le niveau de gris est égal à
la valeur du seuil. Kohler s’est inspiré de cette idée et propose de sélectionner le seuil qui
détecte le plus grand nombre de contours à fort contraste et le plus petit nombre de contours à
faible contraste[Kohler, 1981]. Weszka reprend ces idées et utilise en plus des niveaux de gris
des pixels, une information gradient de chacun d’eux [Weszka, 1974]. Dans son algorithme
L’histogramme n’est calculé que pour les pixels à faible gradient, ce qui permet de creuser les
vallées entre les pics de l’histogramme. Ceci permet de ternir compte des pixels appartenant à
la frontière entre les régions et le fond. De même Katz propose de sélectionner les pixels avec
forte valeur de gradient et de choisir la valeur de gris moyenne de ces pixels [Haralich, 1985].
Toujours dans le même ordre d’idée Hertz et al. présentent dans [Hertz, 1988] une méthode de
segmentation par coopération d’une technique de seuillage de l’histogramme et un opérateur
de détection de contours. Le principe est d’extraire de l’histogramme de l’image, les seuils qui
assurent le meilleur contraste sur les frontières des régions détectées ou une meilleure
93
coïncidence entre ces frontières et des contours préalablement extraits par un détecteur de
contours. D’autres méthodes de seuillage se basent sur la théorie de l’information pour le
calcul des seuils [Kapur, 1985 ; Pun, 1981]. Dans [Kermad, 1995], une coopération entre
une technique de seuillage et celle de fusion de régions est proposée. Une segmentation
initiale est obtenue par seuillage des histogrammes locaux extraits sur des petites régions de
l’image à traiter. Après, une fusion de régions étiquetées minimisant un critère de similarité
est effectuée.
Méthodes locales
À beaucoup d'occasions, quand une image est bruyante ou l'illumination n'est pas bonne, les
seuils fixes ne sont pas capables de segmenter l'image sûrement. Les méthodes de seuillage
adaptatives ont été développées pour traiter de tels problèmes[Haralick,. 1985]. Une technique
classique pour déterminer les seuils localement est présentée dans [Chow, 1972], l’algorithme
partage l’image en de petites fenêtres de taille 33*33 ou 65*65 et calcule pour chacune d’elles
la variance de niveau de gris et l‘histogramme. Si la variance dépasse un certain seuil et si
l’histogramme n’est pas uni-modal, la fenêtre est partagée en utilisant un seuil dans la vallée
de celui ci. Puis par interpolation, ils déterminent un seuil pour chaque pixel de l’image. Dans
[Ohlander, 1975 ; Ohlander, 1979],Ohlander propose une méthode de seuillage par division
récursive de l’image. A partir de l’histogramme de l’image originale, il décompose l’image en
régions telle que pour chacune d’elles un histogramme est calculé. Si l’histogramme d’une
région n’est pas uni-modal, elle est redivisée sinon elle reste inchangée et ainsi de suite. Le
processus se termine quand tous les histogrammes sont uni-modal. Cette technique a été
adaptée par Ohta a adapté cet algorithme pour la segmentation d’images couleur[Ohta, 1980].
Pour plus de détails sur les méthodes de segmentation par seuillage, voir les surveys de
Weszka [Weszka, 1978], Fu et Mui [Fu, 1980], Haralick et Shapiro [Haralick, 1985], Sahoo et
al [Sahoo, 1988] ainsi que l'étude comparative de Lee et Chung [Lee,. 1990].
Fin tantque
L’algorithme s’arrête quand aucun changement significatif des centres des classes n’est
observé d’une itération à une autre ou bien quand un maximum nombre d’itération est
obtenue.
Une version légèrement différente des « centres mobiles » est connue sous le nom de « nuées
dynamiques » [Diday, 1971] ou bien sous le nom de « k_medoids ». Il s’agit d’une extension
de l’algorithme des centres mobiles telle que une classe n’est plus définie par son centre, mais
représentée par un groupe de pixels formant un « noyau » [Hamerly, 2003 ; Halkidi, 2001]. Le
k-means [MacQeen, 1967] est différent de celui des centres mobiles par le fait qu’à chaque
itération, chaque nouvelle affectation d’un pixel à une classe entraîne la remise à jour
immédiate de son centre de gravité.
On notera que ce genre d’algorithmes exige la connaissance du nombre de classes [Lee 2000;
Hamerly 2003]. Connaître le nombre « optimum » de classes présentes dans l’image est un
problème complexe et nécessite une connaissance a priori sur les objets constituants l’image
qui n’est pas toujours disponible. Afin de s’affranchir de cette contrainte, différents
algorithmes de classification dynamique ont été proposés dans la littérature. Parmi ces
algorithmes on cite l’algorithme ISODATA,( Iterative Self-Organizing Data Analysis
Techniques A)[Ball, 1967] et l’algorithme Dynoc (Dynamic Optimal Cluster seek) [Tou,
1979] qui introduisent dans l’algorithme de classification une heuristique qui permet de
modifier le nombre de classes au cours des itérations de la façon suivante:
– Lorsqu’une classe présente une inertie intraclasse supérieure à un seuil fixé par l’utilisateur,
la classe est divisée en deux,
95
– Lorsque la distance entre les centres de gravité de deux classes devient inférieure à un autre
seuil, les classes sont fusionnées.
Une autre variante du K-means est l'algorithme des cmoyennes floues (fuzzy c-means) ou
FCM[Bezdeck, 1981]. La partition floue est basée sur la théorie des ensembles flous définit
par Zadeh [Zadeh, 1965]qui décrit la manière dont sont structurés les ensembles flous et
quelles sont les opérations permises sur ces ensembles. En traitement d'images, les méthodes
de classification floue modélisent le degré d'appartenance d'un pixel à chaque classe, sous
l'hypothèse que ce pixel puisse ne pas appartenir à une classe unique. Chacun des N pixels
appartient à chacune des C classes avec un coefficient d’appartenance u; L’ensemble des
degrés d’appartenance est stocké dans la matrice de la C-partition floue U.
−1 (4.6.)
xi − µ
2
(m −1)
C
∑j = 1 x i − µ
k
u ik =
j
Le paramètre m(1<m<3) contrôle le degré de flou de la partition produite : plus m est grand
plus la partition sera floue. Le choix du paramètre m reste une question délicate, mais en
pratique la valeur 2 est souvent utilisée.
Trois contraintes sont définies pour la C-partition floue. La première impose que les valeurs
des uik soient comprises entre 0 et 1 ce qui signifie que tout pixel appartient à la réunion des
classes. La deuxième impose que l’appartenance d’un pixel soit répartie sur l’ensemble des
classes, sans exclure l’existence de degrés d’appartenance nuls. Enfin, la troisième exprime
que la classification ne produise pas de classe vide afin que tous les pixels soient caractérisés.
Formellement, ces contraintes s’écrivent comme suit:
96
C
(4.8.)
∑u ik =1 ∀ k ∈ [1; n]
i =1
N
(4.9.)
0<∑uik < 1 ∀ i ∈ [1; C ]
k =1
L’objectif de l’algorithme FCM est de trouver U qui minimise la fonction objective suivante :
K N 2 (4.10.)
J FCM = ∑ ∑U ik * xi − µ k
k =1 i =1
Enfin, une ultime étape est nécessaire lorsque le résultat souhaité est une classification non
floue. On parle alors de « défuzzification » telle que chacun des pixels est affecté à la classe
pour laquelle son degré d’appartenance est le plus élevé.
Depuis son apparition la classification floue est devenue très populaire en traitement d’image
en générale et en segmentation plus particulièrement. Dans [Lim, 1990], les auteurs proposent
de segmenter des images selon une décomposition « coarse to fine » en effectuant une
première segmentation par multiseuillage, suivie d’une segmentation plus fine par application
de l’algorithme FCM. Chi et Yan [Chi, 1995] ont développé une méthode de segmentation à
partir de règles de classification floues basés sur trois mesures : la différence d’intensité,
l’écart type et une mesure de contraste locale entre le niveau de gris le plus foncé et le fond de
l’image. Une extension de l’algorithme classique FCM est présenté dans [Liew, 2000] en
prenant en compte l’information spatiale locale. L’utilisation de l’information spatiale locale
permet d’améliorer les résultats de classification et fournit des résultats de segmentation
satisfaisants.
Dans [Bouloudani, 2002] les auteurs traitent le problème de la segmentation automatique des
images couleurs. L’algorithme proposé est similaire à ISODATA. Partant d’un résultat de
classification obtenu à partir de l’algorithme FCM, l’algorithme appliqué d’une manière
itérative, essaye de fusionner deux classes si leur distance est comparable à leur compacité. La
signification quantitative du terme “comparable” est donnée par un paramètre α. Ce paramètre
fixe le niveau de fusion désiré, et par conséquent le niveau de simplification de la
segmentation.
97
- Déterminer les K plus proches pixels présents dans un voisinage immédiat sans tenir
compte de leur classe;
Ce processus est répété jusqu’à ce que tous les pixels soient assignés à des classes [Jain,
1999].
L’intérêt des champs de Markov est qu’ils offrent un cadre mathématique puissant qui permet
une corrélation spatiale des étiquettes entre pixels voisins et donc de régulariser l’étiquetage
[Chellappa, 1993]. De plus le théorème de Hameserly [Geman, 1984] a permis de simplifier
l’écriture des probabilités conditionnelles et faciliter la détermination des paramètres qui
spécifient le modèle Les interactions au niveau du point sont prises en compte par le biais
d’énergies potentielles.
L’intérêt des champs de Markov est qu’ils offrent un cadre mathématique puissant qui permet
une corrélation spatiale des étiquettes entre pixels voisins et donc de régulariser l’étiquetage.
De plus le théorème de Hameserly [Geman, 1984] a permis de simplifier l’écriture des
probabilités conditionnelles et faciliter la détermination des paramètres qui spécifient le
98
modèle Les interactions au niveau du point sont prises en compte par le biais d’énergies
potentielles.
C’est un problème d’optimiser difficile car d’une part la fonction d’énergie globale est loin
d’être convexe, d’une autre part la minimisation doit se faire sur l’ensemble des
configurations de toutes les étiquettes possibles dont le cardinal est très grand. Pour résoudre
ce problème deux classes de méthodes ont été proposées, les algorithmes déterministes de
type ICM [Besag, 1974](Iterated Conditionnel Mode) et les algorithmes stochastiques de type
Recuit Simulé [Geman, 1984; Hu, 1992] et Algorithmes Génétiques [Andrey, 1998;Kim,
2000]. Un aperçu de la modélisation markovienne est présenté en annexe .
Depuis leur apparition, les champs de Markov ont été largement utilisés en segmentation
d’images. Nous pouvons citer les travaux de [Marroquin, 1985] [Lakshmanan, 1989; Derin,
1987; Descombe, 1999; Kervrann, 1995; Panjwani, 1995 ; Krishnamachari, 1997]
[Yamazaki, 1995] [Jaggi, 1998]. Afin d’améliorer la qualité de la segmentation et accélérer la
convergence du processus d’étiquetage, d’autres travaux utilisent une relaxation markovienne
avec une approche multi–échelle [Perez, 1992; Bouman 1994] ou bien une approche
hiérarchique [Kato, 1994;Chardin, 2000].
99
4.4.3.6 Conclusion
• Les techniques de seuillage sont simples à mettre en œuvre et donnent de bons
résultats pour les images bien contrastées. Elles exploitent exclusivement les
informations de niveau de gris sans tenir compte de la position des pixels, ce qui, dans
le cas d’images bruitées, crée des contours très chahutés et une sur-segmentation de
l’image. La taille des régions extraites dépend du choix des seuils qui est souvent une
opération délicate (les modes de l’histogramme ne sont toujours bien séparés par des
vallées) ;
• Les méthodes de classification par partition recherchent pour chaque pixel de l’image
la classe la plus proche en sens d’une distance et convergent vers un minimum local de
l’inertie totale. Ce minimum ne correspond pas nécessairement au minimum global
recherché et dépend de la position initiale des centres de gravité. De plus certaines
méthodes impliquent un nombre k de classes à fixer a priori et distribuent les pixels
sur l’ensemble de ces classes en ignorant l’information spatiale ;
• Les méthodes de classification par champ de markov sont très puissantes pour
analyser les images car elles tiennent compte de la présence du bruit. Le modèle
markovien permet une modélisation simple et pertinente des contextes et interactions
locales de pixels, mais exige un nombre considérable d’itérations pour converger vers
des solutions stables ce qui augmente le temps de calcul.
Les réseaux de neurones ont été utilisés aussi bien pour la détection de contours que pour la
classification de pixels. Par exemple on peut citer les travaux de cortes [Cortes, 1989], ceux
de Babaguchi [Babguchi,1990] qui utilise un réseau de neurones multicouches pour
l’extraction des points de contour. Ces idées ont été reprises par Pinho [Pinho, 1996]qui
utilise comme entrées du réseau les différences de niveau de gris entre les pixels adjacents.
Dans [Pontecorvo, ], les auteurs utilisent un autre type de réseau de neurones, appelé Shunting
Inhibitory Cellular Neural Network pour effectuer une détection de contours. Dans ce type de
réseau, chaque cellule est connectée à celles situées à une certaine distance par rapport à elle.
100
Cette cellule peut être inhibée par celle de son voisinage. Dans [Yin, 1993], les auteurs
présentent une série de tests effectués sur plusieurs types de réseaux de neurones effectuant le
filtrage d’une image en éliminant le bruit qu’elle contient. Un état de l’art sur les méthodes
basées réseaux de neurones pour la détection de contours peut être trouvée dans [Devaux,
1997].
Les cartes de kohonen appelés aussi SOM (Self Organised Maps) [Kohonen, 1984], sont assez
proches de l’algorithme K-means et peuvent être utilisées pour trouver automatiquement le
nombre de classes sans aucune supervision [Pandya, 1996; Moreira, 1996]..Dans [Abrantes,
1996], les auteurs utilisent les cartes de Kohonen pour la détection de contours. Le réseau
prend, comme données d'entrée, les vecteurs de position des arêtes préalablement déterminées
à l'aide d'un opérateur de détection d'arêtes et fournit en sortie une image contours. Bélanger
[Bélanger, 1998] remplace une information rigide que sont les arêtes par une information plus
riche que sont les gradients de l'image.
Les premiers travaux utilisant les AG pour résoudre le problème de classification sont dus à
[Raghavan, 1979]. L’algorithme démarre avec un nombre de classes K est fixé à l’avance et
une population de chromosomes de longueur N (taille de l’image à segmenter). Chaque
chromosome associe une classe à un pixel. Les opérateurs génétiques, utilisés pour générer à
chaque génération une population de partitions possibles, sont une adaptation des opérateurs
génétiques binaires. Le but de l’algorithme est de minimiser une fonction fitness représentant
l’inverse de la variance intraclasse.
Plusieurs variantes de cet algorithme de base ont été introduit par d’autres auteurs dans la
littérature. Bhandarkar et Zhang [Bhandarkar, 1999] utilisent l’algorithme génétique pour
minimiser une fonction fitness qui sera utilisée pour évaluer le résultat de la segmentation. La
population initiale est générée par un processus aléatoire. La représentation de chaque
chromosome contient un tableau d’étiquette, une information contour et un graphe
d’adjacence. Un crossover de deux points est appliqué sur le tableau d’étiquettes et une
mutation sur les contours de pixels sont employés. Dans [Maulik 2003] un partionnement flou
est réalisé en utilisant un algorithme génétique de codage réel. Une classification automatique
sans connaissance a priori du nombre de classes présentes dans l’image est obtenue dans
[Murthy, 1996 ; Tseng, 2001; Bandyopadhyay, 2002]. Dans [Andrey, 1998], un algorithme
génétique distribué est utilisé pour segmenter des images texturées dans le cadre des champs
de Markov. Le système de segmentation repose sur un principe évolutionnaire tel que la
segmentation optimale émerge progressivement des interactions mutuelles entre les
chromosomes de la population sans aucune information fournit a priori. Le système
d’apprentissage génétique proposé par [Bhanu, 1995]permet d’adapter le processus de
segmentation en fonction du type d’image à segmenter et des caractéristiques des objets à
extraire. Dans [Gong, 1999], les auteurs proposent un algorithme génétique pour la
segmentation des images couleur en utilisant la structure Quadtree.
D’autres auteurs ont proposé des approches hybrides en utilisant conjointement les
algorithmes génétiques et des algorithmes de classification classiques tels que K-Means et le
FCM. Ces algorithmes sont utilisés soit en aval de l’algorithme génétique afin de leur fournir
une partition initiale de bonne qualité [Babu, 1993], soit alternativement avec l’AG. Une autre
possibilité est qu’ils servent d’opérateurs génétiques (opérateur de mutation par exemple) afin
d’accélérer la convergence des AG [Krishna,1999]. Dans [Chun, 1996] Chun et Yang utilisent
les algorithmes génétiques pour segmenter des images médicales en minimisant une fonction
fitness floue. L’algorithme FCM est utilisé pour générer une segmentation initiale. Chaque
chromosome de la population est codé par n entiers (n etant le nombre de régions). Un
opérateur de croisement de deux point et une mutation dynamique sont utilisés ensuite pour
optimiser le résultat de l’algorithme FCM à travers un processus de division/fusion.
102
Un agent peut être aussi bien un être physique évoluant dans le monde réel, qu’un être
artificiel évoluant dans un monde virtuel. Tout agent (réel ou virtuel) ne se contente pas de
raisonner, il agit. L’action est un comportement tendant à satisfaire au mieux les buts de
l’agent, au vu de la perception et de la représentation de l’environnement dont il dispose, des
ressources et des compétences qu’il possède et de la teneur des informations échangées. Etant
guidés par des objectifs, les agents sont dits autonomes dans le sens où c’est eux les seuls
pilotes de leur comportement, en décidant à chaque instant de l’action adéquate par rapport à
un éventail de possibilités données.
Un système multi-agent (SMA) est défini dans [Ferber, 1995] comme un système composé
des éléments suivants :
• un ensemble d’objets O. Ces objets sont situés, c’est à dire que pour tout objet, il est
possible, à un moment donné, d’associer une position dans E. Ces objets sont passifs,
c’est à dire qu’ils peuvent être perçus, créés, détruits et modifiés par les agents ;
• un ensemble de relations R qui unissent des objets (et donc des agents) entre eux ;
Les systèmes multi-agents offrent une architecture permettant de faire travailler plusieurs
entités autonomes sur un même problème (en coopération ou en parallèle) à l’aide de
protocoles de communication et de processus d’échange d’informations. Le paradigme Muli-
agents a été largement utilisé avec succès ces dernières années dans le domaine de traitement
d’images en général et dans la segmentation en particulier.
Dans le même ordre d’idée Boucher[Boucher, 1999] propose d’utiliser des agents spécialisés
pour la segmentation et l’interprétation de séquences d’images cytologiques en mouvement .
C’est une approche distribuée où chaque agents est spécialisé pour la reconnaissance d’un
concept de l’image. Le modèle générique d’agents est composé de 4 comportements de base :
perception croissance de région ou de suivi de contour), interaction fusion des primitives,
différenciation interprétation des primitives, reproduction stratégie de focalisation des agents.
Les agents du système sont asynchrones et concurrents Un agent ne travaille que sur une
composante d’une image et peut accéder à toutes les informations du système soit de sa
propre image ou celle de l’image précédente. L’utilisateur interagit avec le système par le
biais de séquenceur qui gère l’exécution des différents agents du système.
Dans [Liu, 1999], la segmentation d’image est abordée sous l’angle des automates cellulaire.
Il s’agit de générer une population d’agents réactifs et de l’adapter de génération en
génération à la distribution de points rencontrés dans l’image. Les agents ont une perception
très réduite de leur environnement et sont dotés de deux types de comportement : la diffusion
et la reproduction de manière à s’adapter au mieux aux variations locales de l’image. Si un
agent perçoit un stimulus dans son environnement, c’est à dire s’il est placé sur un pixel
remplissant certains critères caractérisant l’appartenance à un contour ou à un segment
104
Dans [Richard, 2001], des agents situés coopèrent pour segmenter des IRM cérébrales. On y
trouve diverses catégories d’agents : un agent de contrôle global, des agents de contrôle
locaux et au niveau le plus bas, les agents de segmentation, spécialisés dans la détection des
trois types de tissus cérébraux (matière blanche, matière grise et liquide céphalorachidien). Un
processus de négociation entre régions dans les zones litigieuses est évoqué dans les
perspectives, sans toutefois que de solution soit apportée. Duchesnay [Duchesnay, 2001]
s’appuie sur la structure de pyramide irrégulière pour gérer le processus de fusion de régions
et assurer la convergence de la segmentation; une coopération région-région assez
sophistiquée est mise en œuvre, mais qui ne tire pas suffisamment parti de l’information
contour. Un des aspects intéressants de son approche est l’utilisation d’une procédure de
décimation (récursive) pour le passage du niveau k au niveau k+1. La pyramide se construit
en partant de la base qui représente l’image pré segmentée (par exemple avec l’algorithme
Quadtree jusqu’au dernier niveau de la pyramide comportant le minimum d’information. Les
niveaux de cette pyramide sont des graphes d’adjacence de régions. Dans [Veenman, 2003]
un système multi_agent est utilisé pour la segmentation d’images en régions homogènes.
Initialement l’image est décomposée en de petites régions de la taille d’un pixel. Les agents
sont placés sur une grille 2D représentant l’image à segmenter tel que chacun d’eux est affecté
à un pixel. Les agents coopèrent ensemble à travers un processus de migration de pixels d’un
agent à un autre dans le but d’améliorer un critère d’homogénéité des régions qu’ils
représentent.
D’autres systèmes multi_agents inspirés du comportement des animaux sociaux ont été
proposés dans la littérature. On cite les travaux de Carden [Carden, 2002] qui propose une
approche de segmentation d’images basée sur les idées de Reynolds [Reynlods, 1987 ;
Reynolds, 2001], pour la détection des contours des régions dans une image simple. Bourjot
et ses collègues se sont inspirés du modèle de construction de toiles observé chez les
araignées pour proposer un nouvel algorithme pour la segmentation d’images en régions
homogènes [Bourjot, 1999 ; Bourjot, 2001]. Les agents correspondent aux araignées sont
décrits par deux items comportementaux: le déplacement et la pose d’un fil et, en plus un
105
comportement de retour sur la toile, qui a été introduit afin que l’araignée ne parcourt pas
l’intégralité de l’image et ne tisse toutes les régions ayant le même niveau de gris. L’araignée
est dotée d’un état interne pour permettre une pose contextuelle.
Tel que mi,k est le vecteur de caractéristiques moyen du k ieme cluster de la iieme particule. La
qualité d’une particule est définie par
Avec
(4.17.)
d max(Zi ,xi,) = max ∑d (z p, mik )/ nik
k =1,.., K
∀z p ∈cik
Où zmax est le niveau de gris maximum présent dans l’image ; Zi est la matrice de
correspondance représentant l’affectation des pixels aux classes de la particule i. Chaque
élément zi,k, p indique si le pixel z p appartient au cluster ck de la particule i. w1 et w2 sont des
constantes fixées par l’utilisateur. nik est le nombre de pixels qui sont affectés au cluster ck de
la particule i.
Les résultats obtenus pour la segmentation des images IRM synthétiques et images de satellite
sont de bonne qualité moyennant le contrôle des valeurs des paramètres w1 et w2 .
106
Dans d’autres travaux, l’algorithme PSO est hybridé avec un algorithme de classification
déterministe tel que le K-means [Wu, 2002 ; Chen, 2005] et les cartes de Kohonen pour
améliorer la convergence de l’algorithme [Xiao, 2003].
4.4.4.4 Conclusion
Depuis quelques année les mécanismes biologiques sont devenues une nouvelle source
d’inspiration appelée informatique biomimétique pour les informaticiens dans le domaine de
l’imagerie et en particulier pour la résolution du problème de la segmentation d’images.
L’approche biomimétique, copie et adapte les comportements concepts mis en œuvre par le
monde du vivant pour proposer de nouvelles méthodes de résolution. Ces méthodes ont la
particularité d’utiliser un ensemble d’entités simples capables d’accomplir des tâches
complexes grâce au concept d’émergence et d’auto-organisation. Les réseaux de neurones, les
algorithmes génétiques ou encore les méthodes basées sur les insectes sociaux apportent des
solutions originales pour l’obtention d’une segmentation optimale, et peuvent être couplés
ensemble pour pallier à leur insuffisances tout en réunissant leurs qualités.
L’évaluation des résultats de segmentation peut être effectuée par deux approches différentes.
Dans la première approche, un résultat de segmentation est évalué en prenant en compte des
informations a priori. L’évaluation consiste à mesurer l’écart entre le résultat fourni par un
algorithme de segmentation et une segmentation de référence qui peut être fournie par un
opérateur humain ou bien lorsqu’une segmentation manuelle peut facilement être réalisée.
Ceci revient à effectuer une mesure de dissimilarité entre deux segmentations. La deuxième
approche consiste à se référer à l’image originale en évitant de se rapporter à un résultat de
référence. Dans le cas de la classification ceci revient à se fixer un modèle de l’erreur de
mesure et à estimer la qualité du résultat par rapport à ce modèle. Par contre, dans le cas d’une
107
segmentation ceci revient à effectuer des mesures d’homogénéité des régions ou de contraste
entre régions.
Nous présentons dans la suite de chapitre, les mesures d’évaluation de ces méthodes en
présence ou non d’une vérité terrain. Nous détaillons leurs principes, leurs domaines
d’application, leurs avantages et leurs limitations. Dans la mesure que la segmentation de
contours n’est pas abordée dans cette thèse, nous nous focalisons sur l’évaluation des
méthodes de segmentation en régions ou en classes homogènes
Soit I une image de N pixels. Soit I Seg la segmentation de l’image I en segmentée en CSeg
régions/classes et I Re f la segmentation de référence en CRe f régions/classes que l’on souhaite
obtenir. On note I seg (i) et I ref (i) l’étiquette de la classe/région du pixel pi respectivement dans
l’image segmentée et dans l’image de référence.
• La Pureté d’une classe : La pureté d’une classe ck ∈ I Seg est définit comme le
pourcentage d’étiquettes prédominantes qu’elle contient en respect des étiquettes de classe
l ∈ I ref .
108
nlk (4.19.)
Pureté(ck )=max
l nk
où nk est le nombre de pixels de la classe ck et nlk est le nombre de pixels étiquetés l dans
cette classe. La pureté de la partition P(I Seg ) est alors la pureté moyenne de toutes ses classes.
Elle prend ses valeurs dans l’intervalle [0,1] et doit être maximisée.
• L’entropie d’une classe L’entropie d’une classe est plus représentative que la mesure de
pureté car elle tient compte de la distribution de toues les étiquettes dans la classe
considérée. L’entropie d’une classe est donnée par :
nlk n (4.20.)
Entropie(ck )= 1
∑
Log(N) l nk
log( ik )
nk
N étant le nombre total de pixel de l’image I. L’entropie d’une classification est la moyenne
des entropies de toutes les classes de la partition. La mesure de l’entropie d’une classe prend
ses valeurs dans l’intervalle [0,1] et doit être minimisée.
Yasnoff et al [Yasnoff, 1977] ont proposé des mesures d’évaluation qui quantifient les erreurs
de classification quand les classes des pixels sont connues. La mesure de Yasnoff permet
d’évaluer le taux d’erreur pour un pixel mal classé p proportionnel à la distance entre ce pixel
et le plus proche pixel appartenant à la classe à laquelle p aurait dû être affecté. L’erreur de
segmentation entre un résultat de segmentation I Seg et sa référence I Re f est alors définie
comme suit :
Une autre mesure pour la détection de similarité entre deux segmentation est celle de Vinet
Vinet [Vinet, 1991]. Elle consiste à rechercher les couples de régions ( R i , R j ) les plus
similaires dans les deux segmentations telle que Ri appartient à la segmentation résultat I Seg
et R j à la segmentation de référence I Re f . Pour cela une matrice de recouvrement T(I Seg, I Re f )
est construite tel que chaque élément tij =card(Ri ∩R j ), i =1...CSeg et j =1...CRe f mesure le taux
de recouvrement entre deux classes Ri , R j Il s’agit alors de rechercher d’une manière
récursive les couples de régions (Ri ,R j ) ayant un recouvrement maximal. La mesure de Vinet
est définie comme suit :
D’autres auteurs proposent d’autres types de critères qui s’intéressent en particulier à la bonne
localisation de la frontière des classes obtenues. Pour une classe ck , ces critères tiennent
compte de quatre catégories de pixels(figure 4.11) :
Forme segmentée FN
VP
Forme de référence
FP
Sur la base de ces quatre catégories de pixels, Shufelt propose deux mesures pour évaluer la
qualité de détection de bâtiments [Shufelt, 1999].
BDP = VP (4.27.)
VP+ FN
BF = FN (4.28.)
VP
Enfin, d’autres classes de méthodes d’évaluation évaluent déterminent le taux de pixels bien
classés en calculant la différence entre la segmentation de référence et celle obtenue par un
algorithme de segmentation. pour cela elles comparent toutes les paires de pixels et vérifient à
111
chaque fois si ces pixels sont classés simultanément dans les deux segmentations.. L’index de
Rand R est le plus généralement utilisé dans la littérature et est défini comme suit :
R= a+d (4.29.)
a +b + c + d
avec a, b, c et d des paramètres calculés pour tous les couples de pixels pi et p j de la façon
suivante
a = { i, j \ I ref (i)= I ref (j)∧ I seg (i)= I seg (j)} b= { i, j \ I ref (i)= I ref (j)∧ I seg (i)≠ I seg (j)}
c= { i, j \ I ref (i)≠ I ref (j)∧ I seg (i)= I seg (j)} d = {i , j \ I ref (i)≠ I ref (j)∧ I seg (i)≠ I seg (j)}
L’index de Rand prend ses valeurs dans l’intervalle [0,1]. La valeur élevée de R (tend vers 1)
indique une parfaite correspondance entre la segmentation de référence et celle obtenue par un
algorithme de segmentation.
VIkseg ∪VIk
ref
où Soit Vgk et Vsk qui représentent respectivement le nombre total de pixels appartenant à la
classe ck dans les deux images I seg et I ref . Une bonne segmentation est obtenue quand
J k (I seg, I ref ) est proche de 1 ce qui signifie que la classe ck a été bien extraite
Ce type de mesure présente l’inconvénient de ne compter que les pixels, sans prendre en
considération les propriétés spatiales inhérentes aux pixels mal classés. De plus aucune
information sur les pixels responsables de l’erreur de classification n’est fournie.
2 (4.31.)
∑ I i ∑ I j
g (p ) − g (p )
NR pi ∈ Rk
p j ∈ Rk
Levine(I) = 1- ∑ 2
pi ∈ RK pi ∈ R K
où
Plusieurs variations de cette mesure existent dans la littérature. On cite la mesure de Sahoo
[Sahoo, 1988] définit comme suit :
Avec
NR
2
(4.33.)
Levine2(I seg ) = ∑ ∑ g I (pi )−
Card(Rk ) pi∑
1 g (pi )
I
k =1 p ∈ R
i k ∈ Rk
g I (Ri )− g I (R j ) (4.34.)
Contraste(Ri ,R j )=
g I (Ri )+ g I (R j )
De cette manière, le contraste d’une région par rapport à toutes les régions qui lui sont
adjacentes se calcule comme suit :
pixels situés sur la frontière des deux régions Ri et R j sur le périmètre de la région Ri .
• les régions adjacentes doivent présenter des valeurs significativement différentes pour les
caractéristiques utilisées.
NR
Card(Rk ) (4.37.)
Disparitéint ra(I seg )= 1 ∑ Disparitéint ra(Rk )
NR k =1 Card(I)
et
114
L’importance de la disparité intra-classe d’une région dans le calcul de la disparité globale est
proportionnelle au nombre de pixels de cette région. Il est en effet souhaitable qu’une région
de petite taille ait une influence moindre dans le calcul de la disparité intra-classe globale.
NR
Card(Rk ) (4.38.)
Disparitéint er (I seg )= 1 ∑ Disparitéint er (Rk )
NR k =1 Card(I)
Dans le calcul des disparités intra et inter-classes, la nature des classes segmentées est prise en
compte à savoir uniforme et texturée. Pour le cas d’une classe uniforme la disparité intra-
classe est donnée par la formule suivante :
2 (4.39.)
Disparitéint ra (Ri ) = 255
2 1
∑ g I2(pi )− 1 ∑ g I (pi )
Card(Ri ) pi ∈Ri Card(Ri ) pi ∈R
2
La disparité inter-classes d’une classe se base sur sa disparité avec ses voisines et se calcule
comme suit :
q (i)
avec q (i) le nombre de régions R j voisine à Ri . La disparité entre deux régions uniformes se
calcule de la manière suivante :
g I (Ri ) − g I (R j )
Disparitéint er (Ri , R j ) =
NG (4.41.)
Où NG est le nombre de niveaux de gris dans l’image. Cette mesure calcule la différence
normalisée des niveaux de gris de deux régions uniformes.
Parmi ces critères, on cite la mesure d’évaluation proposée par Liu et Yang [Liu, 1994]qui
incorpore les propriétés suivantes :
115
l’intérieur des régions doit être simple et sans trop de petits trous,
NR
ei2 (4.42.)
Liu (I seg ) = 1
1000 (Card (I))
NR ∑i =1 Card (Ri )
où ei correspond à l’erreur portant sur le niveau de gris moyen de la région Ri ,définit par la
somme des distances euclidiennes entre les niveau de gris des pixels de la région Ri et le
niveau de gris moyen de la région Ri dans l’image segmentée.
Le premier terme de l’équation est un facteur de normalisation qui tient compte de la taille de
l’image. Le second terme pénalise les résultats avec plusieurs petites régions (sur-
segmentation). Le troisième terme pénalise les résultats de segmentation contenant des
régions non homogènes. Ce dernier terme est mesuré par le facteur d’aire parce que l’erreur
de niveau de gris est plus élevée pour de grandes régions. Une bonne segmentation I seg
minimisera la mesure Liu(I seg ) .
En étudiant de plus prés la fonction de Liu et Yang, Borsotti et al [Borssoti, 1998]ont identifié
deS limitations de cette fonction. En effet, dans le cas où l’image segmentée I seg présente
plusieurs petites régions (sur-segmentation), le nombre de régions serait très élevé.
Cependant, l’erreur de niveau de gris de chaque région peut être proche de zéro et Liu(I seg )
sera aussi proche de zéro, ce qui signifie incorrectement que le résultat de la segmentation est
très bon. Le meilleur exemple de cette situation est de considérer chaque pixel comme une
région. Borsotti et al [Borsotti, 1998] ont donc modifié la mesure d’évaluation de Liu et Yang
de manière à pénaliser les résultats de segmentation présentant beaucoup de petites régions
ainsi que des régions non homogènes et pour la rendre plus sensible aux petites variations de
segmentation. la mesure de Borsotti et al est définie comme suit :
Borssoti(I seg ) =
R
ei2
1
10000(Card(I seg )
NR ∑
i =1 1+log(Card(Ri ) )
+
Card(Ri )
Le corps de la somme est composé de deux termes : le premier pénalise les régions non
homogènes (typiquement les grandes), alors que le second terme pénalise les régions dont
l’aire Card(Ri ) est égale à l’aire de beaucoup d’autres régions dans l’image segmentée
(typiquement les petites).Plus la valeur du critère est petite, meilleure est la segmentation
évaluée.
4.6 Conclusion
Dans ce chapitre, nous avons présenté les méthodes de segmentation d’images les plus
connues ainsi que les mesures d’évaluation des résultats de segmentation. L’ensemble des
techniques décrites dans les sections précédentes montre que les méthodes de segmentation
bio-inspirée et en particulier celles basées sur les techniques d’intelligence en essaim
constitue une voie de recherche très intéressante et mérite une étude approfondie en vue de
résoudre des problèmes mal posés dans le domaine de la vision artificielle en général et celui
de la segmentation d’images en particulier. Nous rappelons les principales remarques tirées
des développements précédents.
• Les méthodes basées sur la détection de contours permettent l’extraction des points de
brusque variation d’intensités et représentant les transitions locales entre régions
homogènes dans l’image. Cependant la qualité de la segmentation obtenue dépend
fortement de la présence du bruit dans l’image. Les détecteurs optimaux tendent à
trouver le meilleur compromis entre une bonne détection et une bonne localisation des
contours mais nécessitent l’utilisation de seuils qui peuvent être gênant dans le cas
d’une segmentation non supervisée. D’un autre côté, les algorithmes de détecteurs de
contours produisent des contours ouverts difficiles à fermes dans certaines
configurations, ce qui rend leur exploitation difficile.
• Les méthodes de segmentation basées sur les systèmes multi_agents permettent grâce
aux interactions entres des entités complètement autonomes d’aboutir à une solution
optimale.
• Les résultats obtenus à partir d’un algorithme de segmentation peuvent être évaluer
quantitativement selon deux approches La première approche se réfère à l’image
originale, soit par une quantification a priori de l’erreur de mesure (dans le cas d’une
classification), soit par des mesures d’homogénéité des régions ou de contraste entre
régions (dans le cas d’une segmentation). La deuxième approche consiste à comparer
le résultat fourni par l’algorithme avec une segmentation de référence. La
segmentation de référence est produite par un opérateur humain. La difficulté
inhérente à cette approche est, d’une part de trouver un échantillon d’images test
représentatif de la classe d’images sur laquelle l’algorithme est sensé opérer, et d’autre
part que la notion de bonne segmentation présente un sens identique pour des
observateurs différents. En d’autres termes, il serait souhaitable, si l’on segmente à
vue les images de l’échantillon, que chaque observateur fournisse un résultat
identique.
118
Chapitre 5
Des fourmis pour la
classification
automatique des images
5.1 Introduction
Les méthodes de segmentation par classification de pixels affectent chaque pixel à une classe,
en fonction d’un ou plusieurs attributs de ce pixel. La classification est dite supervisée lorsque
des informations a priori sont utilisées pour la construction de classes sous la forme d’un
ensemble d’apprentissage. Dans le cas où aucune connaissance a priori n’est disponible, on
parle de classification non supervisée. Dans ce type de méthodes, on trouve les méthodes
hiérarchiques qui consistent une suite de partitions emboîtées et les méthodes par
partitionnement qui fournissent une seule partition. De nombreux algorithmes de
partitionnement déterministes existent dans la littérature tels que le K-means et le Fcm et leurs
variantes. Ces algorithmes sont très simples à implémenter et convergent rapidement avec une
solution localement optimale. Cependant leur majeur inconvénients est qu’ils nécessitent de
fournir en entrée une partition initiale de bonne qualité ainsi que le nombre possible de
classes. Ces contraintes rendent l’utilisation de ces algorithmes peu intéressante quand on veut
segmenter automatiquement une image.
Dans le chapitre 3, nous avons montré que les fourmis arrivent à résoudre naturellement et
d’une manière distribuée des problèmes de classification tels que l’organisation du couvain et
le ramassage des cadavres. Ces comportements ont inspiré les informaticiens et ont permis
l’introduction de nouvelles heuristiques pour le problème de la classification. Les premiers
travaux dans ce domaine ont été ceux de Deneubourg et son équipe [Deneubourg, 1990], se
basant sur une colonie de fourmis artificielles qui se déplacent aléatoirement sur une grille
rectangulaire et sont capables de ramasser et de déposer des objets présents sur la grille dans
le but de les regrouper selon in critère de similarité. Ces travaux ont été par la suite améliorés
et étendus à différents domaines d’application comme nous avons constaté dans le chapitre 3.
Dans la suite de ce chapitre, nous présentons tout d’abord les motivations qui nous amenés à
proposer AntClust ainsi que les améliorations que nous avons introduites par rapport aux
algorithmes de classification basés fourmis existants dans la littérature. A la suite de ça, nous
décrivons en détail les différentes étapes de l’algorithme ainsi qu’une étude expérimentale
effectuée sur des images synthétique afin de montrer l’efficacité de la méthode.
• Le nombre de pixels à classer est très important et nécessite une grille de grande taille
afin de pouvoir trouver des cas vides pour placer les pixels déplacés par les fourmis ;
• Le déplacement des fourmis sur la grille étant aléatoire, certaines cases peuvent ne pas
être visitées par les fourmis et donc les pixels qui y sont placés ne seront pas ramassés
en un nombre d’itérations acceptables.
• Le fait que chaque case de la grille ne puisse contenir qu’un seul objet à la fois,
implique qu’une fourmi peut passer un certain temps à trouver une case libre sur la
grille.
121
Pour ces différentes raisons, nous avons abandonné la grille car plusieurs paramètres s’y
rattachent et il n’est pas facile de trouver le paramétrage adéquat.
Dans AntClust, l’environnement des fourmis est un tableau de N cellules reliées chacune à un
emplacement représentant le nid de la colonie, afin de faciliter les déplacements des fourmis
d’une cellule à une autre (Figure5.1). Initialement les N pixels de l’image I à segmenter sont
placés sur le tableau de telle sorte qu’une cellule ne contienne qu’un pixel à la fois. Durant le
processus de classification une cellule peut correspondre à un ou plusieurs pixels de l’image
d’origine. A la fin de l’algorithme le nombre de cellules non vides représente le nombre
possible de classes présentes dans l’image.
C1 CN
…………
Le nid
Figure 6.1.
/* Initialisation*/
Pour chaque pixel pi faire
Placer pi dans une cellule du tableau
Finpour
/* Boucle principale*/
Pour t=1 à tmax faire
Pour chaque fourmi a1 faire
Si état[ a1 ]=porteuse alors
Déplacer a1 vers une cellule ck
Dépôt := faux ;
Dépôt := déposer le pixel pi qu’elle transporte dans ck avec une probabilité
pdépôt(pi , ck )
Si Dépôt = vrai alors
Etat [ a1 ] : = libre ;
Finsi
Sinon
Choisir aléatoirement un pixel pi ;
Déplacer a1 vers la cellule ck contenant pi ;
Porter := faux ;
Porter : = Porter pi de sa cellule avec une probabilité p portere(pi , ck ) ;
Si Porter = vrai alors
Etat [ a1 ] := porteuse ;
Finsi
gris qu’il y a entre le pixel qu’elle porte et les pixels contenus dans la cellule du tableau où
elle voudrait le déposer à l’aide d’un critère de similarité. Plus ce critère de dissimilarité est
important, plus la probabilité de le déposer sera importante. Le déplacement d’un pixel obéit
à un raisonnement inverse. La fourmi évalue le critère de similarité entre le pixel considéré et
les pixels présents dans sa cellule. Plus ce critère est faible, plus la fourmi aura de la chance
de le déplacer de sa cellule. De cette manière, les fourmis génèrent dynamiquement des
classes de niveau de gris homogènes à travers une coopération inconsciente.
Dans notre travail, nous avons adopté la distance euclidienne des niveaux de gris des deux
pixels comprise entre 0 et 1. Nous avons alors :
Le critère d’adéquation entre un pixel pi et les pixels d’une cellule ck contenant nk pixels est
alors définit par la fonction de similarité suivante :
α2 (5.2)
f(pi ,ck )= 1 ∑ 2
nk p j ∈ ck α +d(pi , p j )2
(5.3)
N(N −1) p∑ ∑d(p , p )
avec α = 1 i j
∈I i pj ∈I
Où ngi et ngj sont les niveaux de gris respectifs des pixels pi et p j .α est une constante
représentant la distance moyenne entre deux pixels de l’image I.
La fonction de similarité f(.) atteint son maximum quand le niveau de gris du pixel pi est très
proche de celui des pixels présents dans la cellule ck .
Dans la suite, nous présentons les règles que les fourmis vont utiliser sur le tableau pour
déplacer et déposer les pixels.
déposera le pixel qu’elle transporte. La probabilité de déposer un pixel pi dans une cellule
ck est donnée par la formule suivante :
(
pdepôt(pi , ck ) = 1−cos2 π f(pi ,ck )
2
) (5.4.)
Ainsi, plus la fonction de similarité entre le pixel pi et les éléments de ck est faible (tend vers
0), plus la probabilité de dépôt sera faible. Dans le cas contraire si la fonction de similarité est
importante ( f(pi ,ck ) → 1 ), alors la fourmi a une grande chance de déposer le pixel dans la
cellule( pdepôt(pi , ck ) → 1 ).
La fourmi choisit aléatoirement un pixel pi de l’index et se dirige directement de son nid vers
la position de sa cellule ck dans le tableau. Elle évalue localement la fonction de similarité
f(pi ,ck ) et décide avec une certaine probabilité de ramasser le pixel considéré de sa cellule.
Que cette décision soit négative ou positive, la fourmi revient vers son nid pour terminer son
cycle.
1 si ck =1
(5.5.)
p porter(pi , ck ) = q si ck =2
(
cos2 π f(p ,c )
2 i k
) sinon
le cas contraire, f(pi ,ck ) → 1 , p porter ( pi , c k ) → 0 le pixel a une grande chance de rester dans
sa cellule.
Chaque fourmi mémorise les m derniers objets qu’elle a ramassés ainsi que leurs
emplacements sur tableau. Quand une fourmi transporte un pixel pi , elle consulte sa mémoire
et évalue la possibilité de le placeç è r dans la cellule d’un des pixels qu’elle a déjà
transporté. Pour cela, elle calcule la fonction de similarité f( ) pour chacune des cellules
mémorisées. La cellule candidate à recevoir le pixel pi sera celle pour laquelle la fonction f
est maximum. La fourmi se dirige de son nid avec la cellule candidate et décide d’y déposer
son pixel avec la probabilité pdepôt . Si cette décision est négative, sa mémoire est désactivée et
dans les prochaines itérations, elle tentera de déposer son pixel dans une autre cellule choisie
aléatoirement, jusqu’à ce qu’elle y arrive.
126
Lenna Poivron
Le tableau 5.1. présente pour chacune des images, le nombre de classes(K), le nombre de
niveau de gris présent dans l’image ainsi que l’histogramme associé. Pour les images réelles
l’intervalle optimal pour le nombre des classes est obtenu de [Turi, 2001].
127
Lenna [5,10] 52
Poivron [6,10] 54
Le tableau 5.2 résume les valeurs des paramètres de AntClust et de KMEANS avec lesquels
nous avons obtenu de bons résultats. Ces valeurs sont appliquées pour la segmentation de
toutes les images de test.
Le tableau 5.3. montre les résultats de AntClust et de KMEANS pour la segmentation des
images synthétique en utilisant l’index de Rand et la mesure de l’intra-inter classes. D’après
les valeurs obtenues, on constate comme prévus l’incapacité de KMEANS, à extraire le bon
nombre de classes quand le nombre de classes de départ est éloigné du nombre de classes
originelles. Les résultats de 20-KMEANS sont meilleurs que ceux de 100-KMEANS qui sont
bien sur mieux que ceux de KMEANS.
On constate aussi que l’algorithme KMEANS tend à fournir un nombre de classes égal au
nombre de niveaux de gris présents dans les images à segmenter. Les résultats montrent
clairement que l’algorithme AntClust bien qu’il ne nécessite pas une connaissance du nombre
129
probable de classe, arrive à identifier un nombre égal (ou très proche) du nombre correct de
classes avec un écart type presque nul. D’un autre coté, la qualité de la classification générée
par l’algorithme AntClust est très proche de la qualité optimale comme l’atteste les valeurs de
la valeur intra-inter classes réduite ce qui traduit une bonne homogénéité à l’intérieur des
classes.
Figure 3.10. Résultats de classification des images synthétiques par les algorithmes
KMEANS et AntClust.
La courbe de la figure 5.4. donne pour l’image synthétique 1 l’évolution du nombre de classes
au cours des 3500 itérations.
130
Nombre de classes
2000
1600
1200
800
400
0
1297
1621
1945
2269
2593
2917
3241
3565
3889
325
649
973
1
Nombre d'itérations
Figure 5.4. Evolution du nombre de classes au cours des itérations de AntClust pour
l’image synthétique 1.
La figure 5.5. donne pour l’image synthétique 1 l’évolution de la distance moyenne des pixels
par rapport au centre de la classe où ils ont été placés par les fourmis. La distance moyenne
est nulle au départ car chaque pixel est placé dans une classe. Elle atteint sont maximum de
3,50 au bout de 2700 itérations pour décroître au cours des prochaines itérations jusqu’à
atteindre un minimum de 2,37 à partir duquel les fourmis améliorent la classification sans
réduire le nombre de classes..
Distance moyenne
4,00E+00
3,00E+00
2,00E+00
1,00E+00
0,00E+00
1225
1531
1837
2143
2449
2755
3061
3367
307
613
919
1
Nombre d'itérations
Figure 5.5. Evolution de la distance moyenne des pixels au cours des itérations de
AntClust pour l’image synthétique 1.
rand index
1,00E+00
Rand 8,00E-01
index 6,00E-01
rand index
4,00E-01
2,00E-01
0,00E+00
1029
1286
1543
1800
258
515
772
1Nombre d’itérations
Figure 5.6. Evolution de l’index de Rand sur l’image synthtique1.
Le tableau 5.4. résume les résultats de AntClust et de KMEANS pour la segmentation des
images réelles en utilisant la mesure intra-inter régions. AntClust trouve toujours un nombre
de classes proche de l’optimal. Les résultats obtenus confirment encore une fois la
performance de AntClust pour l’extraction d’une classe optimale comparée à celle de
l’algorithme KMEANS.
La figure 5.7 montre quelques exemples des images segmentées par AntClust avec différents
nombre de classes extraits.
Nb_classes 52 19 52 10.09
(0) (0) (0) (1.789)
Valeur intra-inter classes 4,882 e-01 4,652 e-01 4,882 e-01 3,313 e-01
(0) (0) (0) (0.456)
Poivron KMEANS 20-KMEANS 100-KMEANS AntClust
Nb_classes 54 14 54 7.46
(0) (0) (0) (1.458)
Valeur intra-inter classes 4,887 e-01 4,334 e-01 4,887 e-01 2,462 e-01
(0) (0) (0) (0.433)
Figure 3.11. Résultats de classification des images réelles par les algorithmes
KMEANS et AntClust.
132
Lenna 10
Poivron 7
Poivron 8
5.4 Conclusion
AntClust est une nouvelle approche pour la classification non supervisée des images. Il est
inspiré du comportement de tri de couvain observé chez les fourmis réelles. L’intérêt principal
de cet algorithme est sa capacité à extraire automatiquement les classes présentes dans
l’image sans connaître le nombre de classe a priori et sans partition de départ. Dans les
précédents travaux les fourmis se déplacent sur une grille rectangulaire dont les paramètres
sont difficiles à fixer et ont une grande influence sur la convergence de l’algorithme de
fourmis. Dans AntClust, l’environnement des fourmis est un tableau de cases représentant les
classes de l’image et reliée chacune à un nid collectif afin de faciliter le déplacement des
fourmis. A travers cet environnement, les fourmis interagissent ensemble et construisent des
partitions de bonne qualité en utilisant des règles simples de placement et de déplacement de
133
pixels. AntClust utilise une fonction de similarité locale qui mesure la similarité d’un pixel en
terme de niveau de gris avec les autres pixels présents dans une classe. Les expériences
effectuées montrent que AntClust fournit de très bons résultats sur des images synthétiques et
réelles variées et s’avère comme prévu supérieur à l’algorithme classique KMEANS. De plus
cet algorithme est par sa nature distribué donc facilement parallélisable.
134
Chapitre 6
Résolution collective de
la segmentation par
relaxation Markovienne
Chapitre 6. Résolution collective de la segmentation par relaxation Markovienne....... 135
6.1 Introduction ............................................................................................................ 135
6.2 Motivations............................................................................................................. 135
6.3 Segmentation d’images par classification markovienne ........................................ 136
6.3.1 Modélisation des observations ....................................................................... 137
6.3.2 Modélisation des connaissances a priori ........................................................ 138
6.3.3 L’énergie totale .............................................................................................. 139
6.4 Transposition de OCF à la segmentation d’images par relaxation Markovienne .. 140
6.4.1 Le modèle de représentation .......................................................................... 140
6.4.2 Comportement individuel de la fourmi .......................................................... 141
6.4.3 Le modèle de coopération entre les fourmis .................................................. 141
6.4.4 La construction de partitions .......................................................................... 142
6.4.4.1 Approche constructive................................................................................ 142
6.4.4.2 Approche perturbatrice............................................................................... 149
6.5 Résultats expérimentaux ........................................................................................ 153
6.5.1 Etude de la convergence................................................................................. 157
6.5.2 Etude de la robustesse .................................................................................... 158
6.6 Conclusion.............................................................................................................. 159
135
6.1 Introduction
La segmentation par relaxation Markovienne, contrairement aux méthodes classiques de
segmentation est robuste au bruit, et prend en considération la propriété de régularité spatiale
en plus de la propriété d’homogénéité. La théorie de champs de Markov modélise le problème
de segmentation en terme d’optimisation basé sur le critère du maximum A posteriori (MAP).
La segmentation est alors considérée comme un problème d’étiquetage de pixels où on
cherche à affecter à chaque pixel l'étiquette qui maximise l’estimateur MAP et donc minimise
l’énergie globale. C’est un problème d’optimisation complexe qu’on se propose de résoudre
en transposant le concept de OCF à la résolution collective du problème de segmentation
d’images selon une approche des systèmes multi-agents réactifs
Ce chapitre est organisé comme suit : dans un premier temps nous présentons les motivations
qui nous amenés à utiliser la métaphore des fourmis pour la résolution du problème de la
segmentation dans le cadre des champs de Markov. Dans un deuxième temps, nous décrivons
le principe général de notre méthode de segmentation,
6.2 Motivations
La fonction d’énergie globale est loin d’être convexe, et possède souvent un grand nombre de
minima locaux. La segmentation par eelaxation markovienne fait alors partie de la classes des
problèmes d’optimisation NP-complet. Les algorithmes de relaxation sont souvent utilisé dans
ce genre de problèmes tels que l’algorithme Iterated Conditionnel Mode.(ICM), l’algorithme
Recuit Simulé (RS) et les algorithmes génétiques (AG). ICM est un algorithme de relaxation
déterministe et nécessite qu’une partition initiale soit présentée en entrée et converge
rapidement vers un optimum local qui peut être assez éloigné de la solution recherchée. Le
seul moyen de contourner ce problème est de relancer la méthode avec une autre partition
initial (méthodes multistart). Le RS et les AG sont des algorithmes de relaxation stochastiques
qui permettent d’échapper à ces optimums locaux par une exploration stochastique de
l’espace de solutions. Le problème de segmentation en tant qu’un problème d’optimisation
complexe est un bon candidat pour les algorithmes basés OCF qui sont des algorithmes
stochastiques construisant des solutions d’une manière incrémentale. L'idée de base est de
représenter le problème de segmentation sous la forme d’une graphe et de rechercher
un «meilleur» étiquetage de ces nœuds. Des fourmis artificielles circulent dans ce graphe de
façon aléatoire et incomplète, à la recherche de «bonnes» étiquettes. Elles communiquent
entre elles, à travers l'environnement, en déposant sur les arcs du graphe des traces de
136
phéromone qui tendent à attirer les fourmis artificielles dans une boucle de rétroaction
positive, guidant de manière émergente la colonie vers une solution satisfaisante, si ce n'est la
meilleure.
(1) un ensemble de pixels; (2) un ensemble d’étiquettes; (3) une relation de voisinage entre
les pixels, (4) une relation de compatibilité sur les paires d’étiquettes des pixels voisins et(5)
une fonction objectif mesurant la qualité de chaque partition construite.
Soit Y ={Ys , s∈S }le champ des observations (dans notre cas niveau de gris) représentant
l'ensemble des N pixels de l'image. Il est définit sur l’ensemble S des sites s tel
que S ={s1 , s2,.....sN }. Nous cherchons à mettre en correspondance ce champ Y avec un champ
des étiquettes E={es, s ∈ S } prenant ces valeurs dans un ensemble fin Λ = {1,.....L} tel que L est
le nombre total des classes présentes dans l’image et es =l indique que l’étiquette l est assignée
{
au pixel s. L'espace Ω représente la totalité des configurations possibles e= es ,...,es N sur
1
}
l'image avec et es ∈ Λ .. Nous supposons que les champs Y et E sont des champs markoviens
que nous intégrons dans un formalisme bayésien afin d’utiliser les contraintes issues
d’informations a priori.
)
e =arg max{P(E | Y)} (6.1 .)
Ω
x
(
ys − µes
P(Y | E)=∏ 1 Exp−
)2
− log(σ es )
(6.2 .)
s∈S 2π 2σ e2s
(ys−µes )2 (6.3 .)
P(Y | E)= 1 S Exp −∑ + log(σ es)
s∈S 2σ es
2
(2π )2
( ys − µes )2 (6.4 .)
U(Y | E)=∑ + ln( 2π σ es )
s∈S 2σ e2s
(6.5 .)
P(E)= 1 exp−∑Vc(e)
Z c∈C
Z est une fonction de normalisation. Vc(e) est appelée potentiel d’interactions pour une clique
c. Un sous ensemble c de S est appelé une clique relative au système de voisinage N si tous les
pixels de c sont voisins deux à deux.
Le potentiel d’interaction relatif à l’étiquette es relatif au pixel s, connaissant les étiquettes des
pixels voisins à s (noté V(es / eVs ) est tel qu’il favorise l’appartenance de deux pixels voisins à
la même étiquette. Ainsi l’étiquette la plus probable pour un pixel sera celle la plus présente
dans son voisinage. Il existe dans la littérature de nombreuses modélisations du potentiel
d’interaction
Le modèle de Potts est largement utilisé comme a priori à des fins de segmentation. C’est un
modèle à interactions par paires telle que les cliques sont constituées de pixels voisins. La
fonction potentielle utilisée pénalise alors les cliques non homogènes, c’est à dire les cliques
dont les sites ont des étiquettes différentes. Elle est définie comme suit :
139
Dans ce travail de thèse, nous avons modélisé les connaissances a priori par une fonction
linéaire qui s’écrit comme suit :
∑V(e ,e ) s s'
(6.7 .)
s'∈Vs
V(es / eVs )=
∑1
s'∈Vs
Cette fonction est représentée figure pour un voisinage normalisé variant entre 0 et1
∑V(es ,es')
s'∈Vs
( 0≤ ≤1 ). Le voisinage est normalisé en divisant le nombre de voisins partageant la
∑1
s'∈Vs
U(E)=∑Vc(e) (6.8 .)
c∈C
(ys − µes )2
U(E /Y) = ∑ + ∑ln 2π (σ es )+∑Vc(e)
2σ es
2
1s∈S44 4442s4 ∈S 4444
3 c1 ∈C23 (6.9 .)
U(Y / E) U(E)
Cette minimisation se fait sur l’ensemble des configurations dont le cardinal est très
important. Il n’est pas possible de tester chacune des configurations de l’ensemble Ω.
Plusieurs méthodes de relaxation existent dans la littérature pour pallier ce problème. Nous
avons décidé de s’inspirer du comportement de fourragement observé chez les fourmis pour
résoudre ce problème d’optimisation.
• Modélisation de l’environnement des fourmis par un graphe sur lequel se déplacent les
fourmis la recherche d’un étiquetage optimal pour les pixels ;
141
Dans le cadre de cette thèse, nous avons développé deux approches pour la construction d’une
partition possible
6.4.4.1.1 L’environnement
L’environnement dans lequel évoluent les fourmis est un graphe G = (N; A) tel que :
• N est l’ensemble des nœuds du graphe tel que N =s _ noeuds∪L _ noeuds où les
S_nœuds ∈S sont les nœuds pixels de l’image, et les L_nœuds ∈Λ sont les nœuds
étiquettes possibles. On notera que les L_nœuds sont les nœuds terminaux du graphe
G.
• A est l’ensemble des arêtes du graphe. Chaque S_nœud est relié par une arête à chaque
L_nœud.
Une partition construite par une fourmi k est notée par ek et se présente sous la forme de N
couples de la forme (s, l ) correspondant à l’affectation de l’étiquette l au pixel s.
U(e ) =∑
(y −µ ) 2 (6.11 .)
∑log(σ es )+∑β.V(es /eVss )
s
l es
+
s∈S 2σ 2
es s∈S s∈S
β est un paramètre positif qui contrôle l’influence des pixels voisins (il est mis à1 dans nos
expérimentations). C’est un terme de régularisation. Le problème revient alors à trouver les
couples d’affectation qui correspondent au minimum de la fonction objectif.
143
0 1 …… L-1
S1
S2
……
SN
A partir d’un nœud fictif a appelé nœud de départ, les fourmis explorent en parallèle
l’environnement image et contribuent à l’émergence de la partition optimale. Chaque fourmi
se déplace d’un noeud-pixel vers un autre jusqu’à ce que tous les pixels de l’image soient
traités et exécute le même processus d’étiquetage pour tous les pixels de l’image. Ce
processus est basé sur deux phases : à partir du nœud a, un pixel s est choisi parmi les N
pixels de l’image représentés par s1 ,s2,....sN . Une fois le pixel s choisi, la fourmi doit lui
affecter une étiquette l de l’ensemble Λ . Une fois le pixel étiqueté, la fourmi revient au nœud
a encore, et le processus d’étiquetage est répété tant qu’il existe encore des pixels non encore
étiquetés, ce qui complète la partition de l’image..
Pour une fourmi la base décisionnelle pour le choix d'une étiquette de classe est fournie par la
trace de phéromone artificielle τ (s, l ) associée à la paire (s, l ) qui représente la désirabilité de
mettre es = l dans sa solution, cette information est rendue disponible par des tentatives
précédentes d'autres fourmis. La trace de phéromone est une information numérique codées
dans une matrice de dimension (N ,L) tel que N est la dimension de l’image et L est le nombre
total de classe présentes dans l’image.
144
Une fois que chaque fourmi a établi une solution complète représentant un marquage possible,
ce dernier est amélioré en utilisant une méthode de recherche locale afin d'augmenter sa
qualité. A la fin du processus de classification, les traces de phéromone sont mises à jour
localement pendant la construction de solutions et globalement à la fin de chaque itération
selon la qualité de la meilleure solution trouvée à partir du commencement du processus de
segmentation. L’algorithme s’arrête quand un maximum du nombre d'itérations a été exécuté.
Pour situer les éléments essentiels de notre méthode, nous nous référons au squelette de
l'application (Algorithme 1). On s’attardera sur les éléments suivants : initialisation de la
phéromone, construction d’une partition, modification de la partition, la mise a jour de la
phéromone et la recherche locale
Initialisation
K fourmis sont placées sur le nœud a du graphe. Chaque fourmi k possède un vecteur ek qui
stocke la solution trouvée par la fourmi.
Toutes les valeurs de phéromone τ pour les paires (s, l ) sont initialisées avec une valeur
τ 0 = 1 (N.U(e0)) où e0 est une première solution créée par une heuristique glouton. Les pixels
de l’image sont traités dans l'ordre, et pour chacun d’eux est assignée une étiquette de classe
qui réduit au minimum la fonction locale d'énergie donnée par :
+ log(σ l )+ ∑Vc(x)
(6.12 .)
2σ l2 c : s∈c
Les deux premiers termes de U s représentent l'attache aux données et le dernier terme
introduit une contrainte de régularisation dans le modèle.
Construction de solution
Repeter
Pour chaque fourmi k=1,…..,K Faire
Pour chaque pixel s ∈ S Faire
Avec probabilité q0 :
l = arg max τ(s, u)
u∈Λ
Sinon
Choisir l aléatoirement à partir de l’ensemble des
étiquettes Λ avec une probabilité τ(s, l)
∑τ(s, u)
u∈Λ
Mettre esk = l
Fin pour
Fin pour
∆τ(s, l) =
0 otherwise
Fin pour
Fin pour
Jusqu’à M Itérations
146
La décision d’assigner une étiquette de classe l au pixel s est basée sur la régle pseudo-
aléatoire proposée par Dorigo et Gambardella dans [Dorigo 1997]. La transposition de cette
règle à notre problème est modélisée comme suit [Ouadfel 2003a][ouadfel 2003b].
Soit q un nombre aléatoire uniformément distribué dans [0,1] et q0 une probabilité fixe.
• Autrement on prend une décision aléatoire telle que une étiquette de classe l = 1...L
est choisie avec la probabilité P(s,l)
τ(s, l) (6.14 .)
P(s,l) =
∑τ(s, u)
u∈Λ
Le choix de la valeur de q0 est important. Une valeur trop grande de q0 (proche de 1) rendrait
le choix des étiquettes purement élitiste et le processus d’optimisation s’apparenterait à une
démarche gloutonne. Les risques de stagnation sont alors importants. Une valeur trop petite de
q0 conduirait à des temps de convergence trop importants.
Le modèle d’interaction entre les fourmis est stigmergique. Les fourmis ne communiquent pas
directement mais à travers le changement de la matrice de phéromones. En effet, les traces de
147
phéromones représentent une sorte de mémoire collective entre les fourmis. En modifiant ces
traces, les fourmis modifient la façon dont le problème va être représenté et perçu par eux par
leurs congénères. Le choix de la méthode de modification des traces de phéromones est donc
important, pour obtenir les meilleurs résultats. On considère ici deux stratégies de
modification :
Stratégie de ACS
La mise à jour des traces de phéromones est effectuée de manière locale (par chaque fourmi)
et de manière globale (par la fourmi qui a trouvé la meilleure solution). La mise à jour locale
est effectuée à chaque fois qu’une fourmi termine la construction de sa solution et a pour but
de diminuer la quantité de traces de phéromones associés aux paires (s,l) sélectionnées par la
fourmi afin de réduire son attraction pour les autres fourmis lors de la construction de leurs
solutions et d’encourager ainsi l’exploration des autres choix possibles (d’autres
assignements). La mise à jour locale de phéromone est appliquée selon la formule suivante:
Une fois que toutes ont terminé la construction de leurs solutions, les traces de phéromone
sont alors modifiées. Seule la fourmi qui a trouvé la meilleure partition e gb telle que
U(e gb)=min (U(ek )) , est autorisée à déposer les phéromones additionnelles sur les paires (s, l )
k =1,...., K
appartenant à sa solution. La mise à jour globale est faite en appliquant la règle de mise à jour
globale suivante:
là où
1
U(e gb) if (s, l) ∈ e
gb
∆τ(s, l) = (6.17 .)
0 otherwise
Stratégie de MMAS
Selon cette stratégie, seule la fourmi ayant trouvé la meilleure partition est autorisée à
effectuer une mise à jour de la matrice de phéromone. Cependant les quantités de phéromones
sont bornées dans l’intervalle afin d’éviter la stagnation de la recherche. Elles sont initialisées
au départ à la valeur maximale.
Recherche locale
Les métaheuristiques de colonies de fourmis sont souvent plus efficaces quand elles sont
hybridées avec des algorithmes de recherche locale. Ces derniers sont utilisés pour optimiser
les solutions trouvées par les fourmis et accélérer la convergence de l’algorithme vers les
meilleurs solutions. Chaque solution créée par une fourmi est ainsi améliorée avant son
évaluation. L’algorithme de recherche locale comporte deux composants: la définition d’un
voisinage N(e) permettant d'obtenir les solutions voisines de la solution e et la donnée d’une
stratégie de recherche permettant l’exploration de ce voisinage. L’ensemble N(e)est
l’ensemble des partitions admissibles qui sont atteignables à partir de e en changeant les
affectations des pixels. La stratégie d’exploration la plus simple consiste à aller d’une solution
à une solution voisine qui soit meilleure que la solution courante jusqu’à ce que l'algorithme
s'arrête sur un optimum local. Dans notre algorithme, pour chaque solution e nous
considérons les solutions voisines e' ∈ N(e) et on sélectionne la première solution e’ pour
laquelle U(e') < U(e) , c’est à dire que la première solution qui diminue la fonction objective
globale est retenue. Les solutions voisines d’une solution sont obtenues en permutant les
étiquettes de deux pixels. Le squelette général de l’algorithme de recherche locale est donné
dans l’encadré 6.2).
Soit w = φ
Tant que ( N(e)/ w ≠ φ) Faire
e' = GénérerSolution (e)
Si U(e' ) < U(e) Alors
Retourner e'
Sinon
w = w U e'
Fin tant que
Figure 6.4.
Figure 6.5.
149
Comme dans la méthode précédente, on associe à la partition ek une fonction objectif définie
par
U(e ) =∑
(y −µ ) 2
(6.18 .)
∑log(σ )+∑.V(es / eVss )
s
l es
+ es
s∈S 2σ 2
es s∈S s∈S
corr(s,s')+1 (6.19 .)
η(s,s')= tel que s∈
' Ns
2
Les valeurs de la fonction heuristique sont dans l’intervalle [0,1]. Elles indiquent de degré de
similarité entre les pixels considérés en terme de niveau de gris. Elles tendent vers 1 pour une
forte corrélation et vers 0 dans le cas contraire.
Dans la section suivante, nous présentons en détail les différentes étapes de l’algorithme
proposé (algorithme 6. 3).
151
Fin Pour
Initialisation
Initialement, on associe à chaque fourmi k une partition générée aléatoirement. A chaque
pixel s∈S , on affecte une étiquette l choisie aléatoirement de l’ensemble Λ . Ces partitions
sont ensuite améliorées en utilisant l’algorithme ICM. A partir des K partitions ainsi obtenues,
on choisit la meilleure partition ebest qui minimise la fonction objectif. Chacune des paires (s,
l) est alors initialisée avec la qualité de ebest .
• Si q≤q0 le pixel s’ sélectionné pour être regrouper avec le pixel s dans sa classe est
celui pour lequel le profil phéromone-heuristique est maximum :.
P(s,s')=
∑η(s, j ) .τ (s, j )
β k γ
j∈N s
où
• τ(s,s') est la désirabilité de regrouper les deux pixels s et s’ dans la même classe dans
la nouvelle partition.
Le choix de la valeur de q0 est important car il doit permettre de réaliser un équilibre entre le
mécanisme d’exploration et celui de l’exploitation.
Ensuite, la fourmi ayant trouvé la meilleure partition renforce les valeurs des traces de
phéromone associées à ses couples (s, l) selon la règle suivante
où
La diversification
Dans le cas où la meilleure solution x gb obtenue depuis le début de l’algorithme, n’a pas été
améliorée depuis un nombre d’itération ce qui indique une stagnation ou une convergence
prématurée, on active un processus de diversification qui force une exploration de nouvelles
pistes dans l’espace de recherche. Toutes les valeurs de phéromones sont complètement re-
initialisées à la même valeur et de nouvelles partitions sont générées pour k – 1 fourmis à
l’exception de la keme fourmi à qui on associe la meilleure global partition. Le processus de
génération des nouvelles partitions est basé sur une matrice de fréquences Freq
( )
(Freq s,s'),s∈S,s'∈N s qui représente le nombre de fois où la paire (s,s’) est apparue dans
l'ensemble des solutions. Ces solutions ont été fournies par les fourmis lors des itérations
précédentes. Cette matrice est utilise lors de la diversification, pour générer des solutions
comportant les affectations qui ont été les moins choisies.
Noise=0%
Noise=3%
Noise=5%
Dans un second temps, nous avons utilisé quelques images réelles de la banque
d’images du GdR 134. : une image de maison avec 3 classes et une image de muscle
représentant une section transversale de fibres musculaires
avec 4 classes.
a b
Afin de mieux situer les résultats obtenus nous les avons comparés avec ceux obtenus avec
deux autres méthodes d’optimisation classiques qui sont le Recuit Simulé et les Algorithmes
Génétiques.
Dans la validation des algorithmes présentés dans ce chapitre, nous nous sommes attachés au
fait que l’objectif de tels algorithmes est de vérifier les deux critères suivants : une
convergence vers une solution optimale et la robustesse vis à vis de la présence du bruit. La
satisfaction de ces critères nécessite au préalable d’ajuster les paramètres de contrôles
suivants :
Pour trouver les bonnes valeurs de ses différents paramètres, nous avons effectué plusieurs
exécutions de nos algorithmes de segmentation sur les images de test présentés dans les
figures 6.6. et 6.7 pour diverses valeurs des paramètres de contrôles. Le tableau présente les
valeurs avec lesquelles de bons résultats ont été obtenus.
Valeurs
Paramètres Approche constructive Approche
perturbatrice
ACS MMAS HACSEG
τ min / 0.001 /
q0 0.6 0.6 0.6
ρ 0.01 0.9 0.01
α 0.01 / /
γ / / 1
β / / 2
K 10 15 10
Nmax 2500 2500 2500
.Tableau 6.1. Valeurs initiales des paramètres de nos algorithmes de segmentation
Les paramètres de l’algorithme Recuit Simulé et les Algorithmes Génétiques sont résumés
dans le tableau 6.2.
Fonction objectif
0,4 0,4
Fonction coût
0,3 0,3
ICM ICM
0,2 0,2
ACS ACS
0,1 0,1
0 0
1281
1601
1921
2241
2561
2881
1141
1521
1901
2281
2661
3041
3421
321
641
961
381
761
1
(a) (b)
Dans un second temps, nous avons étudié l’évolution de la fonction de coût en considérant
l’approche de constructive de partition avec les deux stratégies de sélections des étiquettes
ACS et MMAS et l’approche perturbatrice de partitions HACSEG. Le graphe 6.10. montre
que les résultats de ACS et MMAS sont proches mais moins bons que ceux de HACSEG.
0,5
Fonction Coût
0,4
MMAS
0,3
ACS
0,2
HASEG
0,1
0
1 526 1051 1576 2101 2626
Nombre de cycles
158
N= 0% N = 3% N = 5%
20% 40% 20% 40% 20% 40%
LCR 0.86 0.87 0.86 0.85 0.82 0.80
GM 0.91 0.89 0.88 0.88 0.86 0.84
SA WM 0.90 0.86 0.88 0.84 0.83 0.81
LCR 0.85 0.89 0.87 0.86 0.82 0.81
GM 0.96 0.90 0.90 0.88 0.87 0.85
GA WM 0.91 0.86 0.88 0.84 0.83 0.82
LCR 0.88 0.88 0.89 0.87 0.86 0.82
GM 0.95 0.90 0.91 0.89 0.88 0.87
ACS WM 0.93 0.88 0.90 0.85 0.84 0.81
LCR 0.89 0.87 0.87 0.85 0.86 0.82
GM 0.94 0.89 0.90 0.89 0.88 0.86
MMAS WM 0.93 0.88 0.89 0.86 0.84 0.82
HACSEG LCR 0.89 0.89 0.88 0.86 0.87 0.82
GM 0.95 0.90 0.91 0.90 0.88 0.87
WM 0.94 0.89 0.91 0.87 0.85 0.83
Tableau 6.3. . Comparaison des performances des algorithmes (1) SA, (2) GA, (3)ACS-
MRF, (4) HACSEG pour la segmentation des mages IRM.
159
SA 1.130 0.980
GA 1.128 0.950
D’après les valeurs présentées dans le tableau 6.3. et 6.4., on constate que HACSEG obtient
toujours de meilleurs résultats que ACS et MMAS. Cette performance s’explique par le fait
que HACSEG utilise une fonction heuristique pour guider la recherche des fourmis et d’une
autre part l’utilisation d’une fonction de diversification qui permet de mieux explorer l’espace
de solutions.
6.6 Conclusion
La segmentation par relaxation markovienne, est un problème difficile pour qui plusieurs
métaheuristiques ont été proposé. Dans ce chapitre, nous avons présenté une approche basée
sur une colonie d’agents fourmis qui coopèrent ensemble par stigmergie pour la résolution
collective du problème de segmentation L’idée est d’utiliser l’intelligence collective des
fourmis a été utilisée pour la détection de classes dans des images à niveaux de gris tenant
compte des contraintes d’homogénéité et de régularité spatiale. Les algorithmes proposés sont
distribués et se basent sur une colonie de fourmis qui construisent/ modifient en parallèle des
partitions candidates et communiquent via les traces de phéromones accumulées durant les
itérations. La partition optimale émerge à partir de la coopération indirecte des fourmis. Un
algorithme de recherche locale est ajouté afin d’améliorer la qualité des solutions trouvées et
accélérer la convergence de l’algorithme. Une étape de diversification est introduite afin de
diversifier la recherche dans l’espace de solutions.
160
Chapitre 7
Conclusion générale
161
Nous avons proposé de bénéficier du mécanisme de coopération inconsciente chez les fourmis
pour mettre au point de nouvelles approches de segmentation d’images d’inspiration
biomimétiques. La segmentation optimale émerge progressivement des interactions indirectes
entre les fourmis selon un processus stigmergique. Ces fourmis sont très simples et ont une
perception limitée de leur environnement ainsi qu’un mécanisme de sélection d’actions
probabiliste en fonction de l’état de leur environnement.. Nos contributions prennent deux
formes :
Dans un premier temps, nous avons étudié et adapté la capacité des fourmis à rassembler et à
trier les éléments de leur couvain, pour développer un nouvel algorithme de classification non
supervisée a été proposé. L’objectif est de partitionner les pixels d’une image en des classes
pertinentes, sans disposer d’une partition initiale ni d’information sur le nombre d’exacte de
classes présentes dans l’image. Pour cela, nous utilisons une colonie de fourmis artificielles
autonomes qui se déplacent d’une manière asynchrone sur un tableau de cases représentant
leur environnement. Les pixels à classer sont placés initialement sur ce tableau de telle sorte
qu’une case ne contienne qu’un seul pixel à la fois. Les fourmis déplacent les pixels d’une
case à une autre en se basant sur une fonction de similarité entre les pixels d’une même classe.
Grâce à des règles de comportement local très simples, et de la coopération inconsciente
entre les fourmis, la partition optimale émerge.
Dans un second temps, nous nous sommes inspirés du comportement de fourragement chez
les fourmis, modélisé par la métaheuristique OCF (ou ACO), pour proposer une nouvelle
approche de segmentation par relaxation markovienne. Notre motivation est que la
segmentation statistique étant définie comme un problème NP_difficile, est ainsi une très
bonne candidate pour les approches basées métaheuristiques y compris OCF. Les fourmis
construisent des segmentations potentielles d’une manière incrémentale s’appuyant sur les
informations collectées collectivement. Elles communiquent indirectement via des
modifications de l'environnement par l'intermédiaire des traces de phéromones. L'idée
162
fondamentale de cette approche une recherche parallèle par les fourmis d’un étiquetage
correcte des pixels de l’image. Cette recherche est basée sur une structure de mémoire
dynamique (trace de phéromones) incorporant des informations sur l'efficacité des résultats
précédemment.
Dans cette optique, trois algorithmes basés fourmis ont été développés. Les deux premiers
algorithmes utilisent une approche constructive pour générer des segmentations potentielles.
Sans aucune partition de départ, les fourmis construisent selon un processus incrémental des
segmentations en utilisant des règles de sélection des étiquettes selon deux stratégies
différentes : ACS et MMAS. Le troisième algorithme se distingue des aux premiers par le fait
que les fourmis ne construisent pas totalement de nouvelles partitions, mais au contraire
modifient celles déjà existantes. La procédure de modification se base sur l’échange
d’étiquettes des pixels en fonction de leur voisinage immédiat. En plus une fonction de
diversification a été introduite afin de mieux guider les fourmis lors de l’exploration de
l’espace de solutions. La validation de ces algorithmes sur un jeu de test a permis de montrer
leur robustesse vis à vis du bruit et leur capacité à converger vers une solution de bonne
qualité.
La validation des ces algorithmes basés fourmis sur des images synthétiques et réelles a
permis de dégager leurs intérêts en comparants les résultats obtenus avec ceux de méthodes
alternatives de références dans la segmentation d’images.
Perspectives
Les perspectives de cette contribution sont nombreuses, et concernent en particulier deux
points de vue.
En premier lieu, il s’agit en premier de faire une étude théorique pour le choix des valeurs des
paramètres des algorithmes afin de mieux contrôler la qualité des résultats obtenus. En
second, d’étudier la possibilité d’une hybridation des algorithmes de fourmis avec d’autres
algorithmes d’optimisation combinatoires tels que les algorithmes génétiques, les algorithmes
d’optimisation par essaim de particules. Enfin, d’exploiter le parallélisme implicite des
algorithmes basés fourmis afin d’améliorer les temps de convergence. Par exemple, on pourra
associer aux fourmis des processeurs indépendants qui communiqueront entre eux à travers
une mémoire commune qui contiendra les valeurs des phéromones.
En second lieu, la faisabilité des algorithmes proposés, leur simplicité de mise en œuvre ainsi
que la qualité des solutions obtenues comparés aux méthodes classique, nous permettent de
163
Annexe A
A.1 Introduction
Les modélisations Markoviennes ont connu ces dernières années un vif succès, notamment
pour les problèmes de segmentation en régions et en contours. En effet, depuis les travaux de
Geman et Geman [Geman, 1984], les champs de Markov ont été beaucoup utilisé pour la
formalisation théorique des techniques de segmentation précédemment utilisées. Ils offrent un
cadre mathématique cohérent pour l’extraction des régions de l’image, en utilisant
conjointement les données de l’image et les contraintes contextuelles ce qui permet de fournir
de bons résultats de segmentation. La segmentation associée aux champs de Markov se
ramène comme on verra à un problème d’optimisation d’un étiquetage. Le but est alors de
trouver le minimum d’une fonction représentant l’erreur de segmentation commise. Cette
fonction appelée également « énergie » est constituée généralement de deux termes : un relatif
au vecteur de caractéristiques de l’image, et l’autre relatif aux interactions entre les étiquettes
des pixels. La minimisation globale de la fonction d’énergie est un problème NP-complet,
plusieurs algorithmes d’optimisation ont été proposés pour le résoudre.
S =(si ,1≤i≤ N ).
A chaque site s est associe une variable aléatoire Ys, dont la valeur ys appartiennent à un
ensemble Ω= {0,…,255}. L’image est alors considérée comme la réalisation d’un vecteur
aléatoire Y ={Ys ,.s ∈ S }représentant le champ des observations. La segmentation markovienne
a pour objectif d’estimer le champ des étiquettes E ={Es ,.s ∈ S } . Une réalisation des champs Y
et E sont notée respectivement par y ={ys ,.s ∈ S } et e={es ,.s ∈ S }.
• ∀s∈S,s∉Vs
La figure (Figure A.1) illustre les deux voisinages les plus utilisés. Celui dit du premier ordre
« système de voisinage de la 4-connexité » est celui pour lequel chaque site a quatre voisins
qui sont ses quatre plus proches voisins. De même, celui du second ordre « le système de
voisinage de la 8-connexité » est celui pour lequel chaque Vs est constitué des huit plus
proches voisins de s.
Les éléments de Ns(S)définissent les sites voisins de s. Une configuration de voisins de s est
appelée clique. On note C l’ensemble des cliques de S. Une clique est dite d’ordre n si elle
contient n éléments.
166
Définition2 : Cliques
Un sous-ensemble c de S est appelé une clique relative au système de voisinage V si
• c est un singleton ou
Généralement les cliques d’ordre deux sont les plus utilisées afin de réduire les temps de
calcul.
Besag et al. [Besag, 1974] a rendu populaire la relation entre champs markoviens et
distribution de Gibbs, initialement démontrée par le théorème de Hammersley-Clifford
(1971). Ce théorème permet d'accéder à la probabilité globale d'une réalisation : si aucune
réalisation du champ de Markov n'est de probabilité nulle, la probabilité d'une réalisation de
ce champ suit une loi de probabilité de Gibbs.
167
Thèorème de Hammersley-Clifford
Un champ aléatoire E est un champ markovien associé au système de voisinage V si et
seulement si sa distribution de probabilité P(E =e) est une distribution de Gibbs définie
par :
avec Z est une constante de normalisation appelée fonction de partition de Gibbs et est
donnée par :
Z =∑exp{−U(e)}
e
et la fonction d’énergie U(e) est une fonction d’énergie définie localement comme la
somme des potentiels d’interactionsVc qui modélisent les interactions entre sites au sein
des cliques:
U(e)=∑Vc (e)
c∈C
D’un point de vue pratique, la spécification des propriétés locales d’un champ de Markov via
la définition des fonctions potentiels des cliques, traduisant un certain a priori ou une certaine
préférence concernant les interactions locales, se traduit de façon équivalente par la
caractérisation globale du modèle probabiliste. De plus, on vérifie aisement que les
distributions conditionnelles locales s’expriment à l’aide des potentiels associés aux cliques
contenant le site s
Théorème de BAYES
En terme d’analyse bayésienne, la probabilité a posteriori peut être exprimée comme suit :
Comme la réalisation y est connue, P(Y = y) est une constante vis à vis du problème, la
distribution a posteriori P(E =e/Y = y) peut s’exprimer simplement en fonction de la
distribution conditionnelle de Y sachant E, c’est-à-dire P(Y = y / E =e) la vraisemblance des
observations et de la distribution a priori P(E =e) des étiquettes à estimer. Comme les champs
X et Y sont supposés markoviens. On a alors :
exp(−U 2 (E =e))
P(E =e)=
Z
)
On cherche à trouver un estimateur bayesien optimal e parmi l’ensemble des configurations
possibles. Plusieurs estimateurs existent dans la littérature, nous détallions dans la suite trois
principales estimateurs.
) )
e = argmin ∑C(e ,e) P(E =eY = y)
e
) )
a. L’estimateur MAP pour lequel la fonction de coût LMAP =C(e ,e)=1−δ (e ,e)
où δ représente le symbole de Kronecker. Cette fonction de coût pénalise de la
même façon toutes les configurations de e, différentes de la solution
recherchée e Autrement dit, elle pénalise de façon identique une erreur sur un
site et une erreur sur plusieurs sites. L’estimateur du MAP fournit toutes les
configurations les plus probables conditionnellement à la réalisation du champ
des observations. On a
)
e MAP =arg max P(E =e/Y = y )
w∈Ω
)
e MAP =arg min U1 (E =e/Y = y )+ U 2(E =e)
e
)
esMPM =argmax P(es =e's /Y = y)
s∈Λ s
)
esMF = E[(es /Y = y]
L’algorithme le plus généralement utilisé est le recuit simulé. Le recuit simulé « simulated
annealing » est un algorithme stochastique introduit par Kirkpatrick et al [Kirkpatrck, 1983] et
appliqué à la segmentation d’images par [Geman, 1984]. C’est une méthode d’optimisation
dérivée de la méthode de Monté Carlo qui est utilisée pour la simulation des systèmes
thermodynamiques. Le principe de base repose sur le principe du modèle métallurgique qui
consiste à faire chauffer le métal à une température assez élevée et puis à la faire décroître
d’une manière graduelle jusqu’à ce que le métal prenne la forme désirée (refroidissement ).
Dans le cas de la segmentation d’images par les champs de Markov, le recuit simulé permet
de minimiser la fonction d’énergie globale en acceptant des remontées d’énergie
proportionnelles à la température, lui permettant ainsi de sortir des puits d’énergie assez
profonds à une température élevée. Inversement, plus la température est faible, moins ces
sauts d’énergie sont tolérés et par conséquent le système se stabilise.
L’objectif du recuit simulé est de trouver une solution optimale à la fonction objective. Partant
d’une partition S donnée ayant une qualité C(s), on modifie cette configuration en modifiant
les étiquettes des pixels. La nouvelle partition S’est toujours acceptée si sa qualité C(S’) est
meilleure ; dans le cas contraire elle sera acceptée avec une probabilité fonction de la qualité
et de la température. Avec ce procédé, des partitions moins bonnes seront acceptées, ce qui
permet d’éviter d’être piéger dans des optima locaux.
plus vite mais vers un minimum stable correspondant simplement au minimum le plus proche
de la configuration initiale.
L’algorithme le plus connu est celui de ICM Cet algorithme a été introduit par Besag [Besag,
1974] et est largement utilisé dans tous les problèmes impliquant les champs de Markov
introduit à cause de la simplicité de sa mise en œuvre. C’est un algorithme déterministe qui
cherche à minimiser en chaque site l’énergie locale définie ne lui. Pour cela il faudra calculer
cette énergie pour toutes les étiquettes possibles. Cet algorithme converge rapidement vers un
minimum local mais est très sensible à la configuration de départ ainsi que de la stratégie de
balayage des sites.
172
Annexe B
Publication de l’auteur
Revues Internationales
Ouadfel Salima, Batouche Mohamed. MRF-based image segmentation using Ant
Colony System. In Electronic Letters on Computer Vision and Image Analysis . ISSN
1577-5097. September 2003 - Volume 2, Number 1 pp 12-24.
Publications Internationales
Ouadfel Salima, Batouche Mohamed . Ant Colony System with local search for Markov
Random Field Image Segmentation. ICIP (1) 2003: Septembre 14-18 pp. 133-136.
Barcelone Espagne.
Publication Nationales
Ouadfel Salima, Batouche Mohamed Garbay Catherine. Optimisation par les colonies de
fourmis pour la segmentation d’images.7éme Conférence Maghrébine sur la recherche en
Informatique. Du 5-8 Mai 2002. Annaba. Pp : 227-235.
Bibliographie
175
Bibliographie
[Abraham, 2003] A. Abraham, et V. Ramos, Web Usage Mining Using Artificial Ant Colony
Clustering and Genetic Programming. Proc. of the Congress on Evolutionary Computation
(CEC 2003), Canberra, pp. 1384- 1391, IEEE Press.2003
[Abrantes, 1996] A.J. Abrantes, et J. S. Marques, A Class of Constrained Clustering
Algorithms for Object Boundary Extraction. IEEE Transactions on Image Processing, Vol. 5,
no.11. 1996.
[Adams, 1994] R. Adams, et L. Bischof, Seeded region growing, IEEE Transactions on
Pattern Analysis and Machine Intelligence, vol. 16, no. 6, 1994.
[Ali, 1997] S-M.Ali, et R.M. Zimmer, The question concerning emergence, in CASYS'97,
Abstract Book, First International Conference on Computing Anticipatory Systems,
CHAOS asdl, 1997
[Andrey, 1998] P. Andrey, et P. Tarroux,. Unsupervised segmentation of Markov random
field modeled textured images using selectionist relaxation, IEEE Transactions on Pattern
Analysis and Machine Intelligence, 3(20): 252–262, 1998.
[Atlan, 2000] H. Atlan, La finalité, Hors série Science&Avenir, 2000.
[Aupetit, 2003] S. Aupetit, V. Bordeau, N. Monmarché, M. Slimane and G. Venturini
Interactive Evolution of Ant Paintings. IEEE Congress on Evolutionary Computation. 2003.
[Azzag, 2004] H. Azzag, C. Guinot et G. Venturini, . AntTree: web document clustering using
artificial ants. Proceedings of the 16th European Conference on Artificial Intelligence (ECAI
04), p. 480-484, IOS Press, Valencia, Spain 2004.
[Babguchi, 1990] N. Babaguchi, et Yamada, K. K. Kise, and T. Tezuka, Connectionist
Model Binarization,” Proceedings of the 10th International Conference on Pattern
Recognition, vol. 1, pp. 51-56, Atlantic City, New Jersey, USA, June 1990.
[Babu, 1993] G.P. Babu et M.N. Murty. A near-optimal initial seed value selection in k-
means algorithm using a genetic algorithm. 14:763–769, 1993.
[Ball, 1967] G.H. Ball and D.J. Hall, A clustering technique for summarizing multi-variate
data, Behavioral Science, Vol.12, pp. 153-155, 1967
[Ballard, 1982] D. H. Ballard and C. M. Brown, Computer Vision, Prentice-Hall HJ, 1982.
[Bandyopadhyay, 2002] S. Bandyopadhyay et U. Maulik Genetic clustering for automatic
evolution of clusters and application to image classification, Pattern Recognition, vol.35, no.
6, pp. 1197-1208, 2002.
[Baradez, 2004] M-O Baradez, C. P. McGuckin, N. F, R. Pettengell, et A.Hoppe.
Thresholding based on linear diffusion for feature segmentation. Pattern Recognition, 37 (6) :
1131–1148, 2004.
[Beaulieu 1989] J.M. Beaulieu and M. Goldberg, Hierarchy in picture segmentation: a
stepwise optimisation approach, IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 11, no. 2, pp. 150-163, 1989
[Beaulieu, 1989] J.M. Beaulieu and M. Goldberg, Hierarchy in picture segmentation: a
stepwise optimisation approach, IEEE Transactions on Pattern Analysis and Machine
Intelligence, vol. 11, no. 2, pp. 150-163, 1989.
176
[Beckers, 1994] R. Beckers, , O.,Holland, and J. Deneubourg, From local actions to global
tasks : stigmergy and collective robotics . In Proceedings of Artificial Life 4, pages 181–189.
MIT Press. 1994
[Bélanger, 1998] H.Bélanger, Réseau de Kohonen pour la détection des contours d’objets
dans une image à niveau de gris . Maîtrise en technologie des systèmes M.Ing. 1998
[Bellet, 1998] F.Bellet, Une approche incrémentale, coopérative et adaptative pour la
segmentation des images en niveau de gris. Thèse de doctorat, Institut National
Polytechnique de Grenoble, France, juin 1998.
[Bertolino, 1995] P. Bertolino. Contribution des pyramides irrégulières en segmentation
d’images multiresolution. Thèse de doctorat. Institut National Polytechnique de Grenoble.
France. Novembre 1995.
[Besag, 1974] J. E. Besag. Spatial interaction and the statistical analysis of lattice system.
Journal of the royal statistical society,Series B, 36 :192–236, 1974.
[Beveridge, 1989] J.R. Beveridge, J.G. Riffith. R. R. Kohler A.R. Hanson et E. M. Riseman
Segmenting images using localized histograms and region merging IJCV 2 pp. 311-
347,Janvier, 1989
[Bezdeck, 1981] J. C. Bezdeck. Pattern recognition with fuzzy objective function algorithms.
Plenum Press Ed., New York, 1981.
[Bhandarkar, 1999] S. M. Bhandarkar et H. Zhang, Image Segmentation Using
Evolutionary Computation, IEEE Trans. On Evolutionary Comp., Vol. 3, No. 1, pp. 1-21,
April, 1999
[Bhanu,1995] B. Bhanu, S.Lee, , and J. Ming, Adaptive image segmentation using a genetic
algorithm. IEEE Trans. Systems Man Cybernet. 25 (1995), pp. 1543–1567.
[Bonabeau, 1994] E. Bonabeau et G. Theraulaz éditeurs. Intelligence Collective. Collection
Systèmes Complexes. Hermès, Paris, France, novembre 1994.
[Bonabeau, 1997] E Bonabeau et G. Theraulaz G., Auto-organisation et comportements
collectifs : la modélisation des sociétés d’insectes, Auto-organisation et comportement,
Editions Hermès, 1997.
[Bonabeau, 1999] E. Bonabeau, M. Dorigo, G.Theraulaz, Swarm Intelligence : From Natural
to Artificiel Systems, NEW York, Oxford University Press,1999.
[Bonabeau, 2000] E.Bonabeau, G. Theraulaz, L’intelligence en essaim, POUR LA
SCIENCE, 282 (3): pp. 66-73, N° 271 mai 2000.
[Bonnin, 1991] P. Bonnin, Méthode systématique de conception et réalisation d’applications
en vision par ordinateur, Thèse de Doctorat, Décembre 1991.
[Borsotti,1998] M. Borsotti, P. Campadelli, et R. Schettini, Quantative evaluation of color
image segmentation results , Patt. Rec Lett., vol.19, (1998)741-747.
[Boucher, 1999] A. Boucher. Une approche décentralisée et adaptative de la gestion
d’informations en vision. Thèse de doctorat de l’université Joseph Fourrier Grenoble I. 15
Février 1999.
[Bouloudani, 2002] N. Bouloudani, P. Lambert, G. Mauris G., Color Image Processing
Control Using Fuzzy Performance Indicators, IEEE Int. Symp. on Virtual and Intelligent
Measurements Systems (VIMS'2002), Anchorage, USA, May 2002, pp. 79-83.
177
[Bouman, 1994] C.A Bouman, et M. Shapiro, Multiscale random field model for Bayesian
image segmentation. IEEE Transaction . Img. Proc., 3(2): 162-177, March 1994.
[Bourjot, 1999] C.Bourjot, V. Chevrier, A. Bernard, B. Krafft, Coordination par le biais de
l’environnement : une approche biologique, In, actes des 7èmes JFIADSMA, St Gilles les
Bains, pp 237-250, Hermes, 1999.
[Bourjot, 2001] C.Bourjot, V. Chevrier, De la simulation de construction collective à la
détection de régions dans les images à niveaux de gris : l’inspiration des araignées sociales,
JFIADSMA, 2001.
[Brice, 1970] C. R. Brice and C. L. Fennema. Scene analysis using regions. Artificial
Intelligence1 :205-226, 1970
[Bryant, 1979] J. Bryant On the clustering of multidimensional pictorial data. In Pattern
Recognition, number 11, pages 115-125, 1979.
[Bullnheimer, 1997] B. Bullnheimer, R.Hartl, et C. Strauss, Applying the Ant System to the
Vehicle Routing Problems, 2nd Metaheuristic International Conference (MIC-97), Sophia-
Antipolis, France.1997;
[Bureau, 2001] A. Bureau, C. Garbay, M. Dodjat . Coopération entre deux populations
d’agents pour la segmentation. ORASIS’2001 – p.281-290 (2001);
[Burt, 1981] P.J. Burt, T. H. Hong, and A. Rosenfeld. Segmentation and estimation of image
region properties through cooperative hierarchical computation. IEEE Trans. Systems Man
and Cybernetics, 11: 802-809,1981.
[Camazine, 2002] S. Camazine, J-L. Deneubourg , N.R. Franks , J. Sneyd , G. Theraulaz et
E. Bonabeau?Self-Organization in Biological Systems, Princeton University Press, 2002.
[Deneubourg, 1990] J.L Deneubourg, S Aron, S. Goss, et J.M Pasteels, The self-organizing
exploratory pattern of the argentine ant. Dans Journalon insect Behavior, 3: 159-168, 1990.
[Deneubourg, 1991] J.L Deneubourg, S. Goss, N. Franks, A. Sendova-Franks, C. Detrain, et
L. Chretien,. The dynamic of collective sorting robot-like ants and ant-like robots, in J. A.
Meyer and S. W. Wilson (eds), SAB 90 - 1st Conference On Simulation of Adaptive
Behavior: From Animals to Animats, MIT Press. 1991.
[Deriche, 1987] R. Deriche, Using Canny's criteria to derive a recursively implemented
optimal edge detector, International Journal of Computer Vision, p. 167-187, 1987.
[Deriche, 1990] R. Deriche. Fast algorithms for low level vision. IEEE Trans. Pattern
Analysis and Machine Intelligence 12(1)78-87.1990.
[Derin, 1987] H. Derin, et H. Elliot, Modeling and segmentation of noisy and textured
images using gibbs random fields. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 9(1):39-55. 1987.
[Descombes, 1999] X. Descombes, R. Morris, J. Zerubia et M. Berthod. Estimation of
Markov random øeld prior parameters using Markov chain Monte Carlo maximum
likelihood. IEEE Trans. on Image Processing, 8(7) :954–963, 1999.
[Devaux,1997] F. Devaux, Filtrage d’images par réseaux de neurones. Maîtrise en
informatique Université paris 8, 1997.
[Di Caro, 1998] Di Caro, G., Dorigo, M.(1998), AntNet: Distributed Stigmergetic Control
for Communications Networks, Journal of Artificial Intelligence Research (JAIR), (9): p.
317-365..
[Diday, 1971] E. Diday. Une nouvelle méthode en classification automatique et
reconnaissance des formes : la méthode des nuées dynamiques. Revue de Statistique
Appliquée, 18(2) :20–33, 1971.
[Dorigo, 1992] M . Dorigo, Optimization, Learning and Natural Algorithms (in Italian). PhD
thesis, Politecnico di Milano, Italy. 1992
[Dorigo, 1991] M. Dorigo, V. Maniezzo, A. Colorni, Positive feedback as a search strategy,
Technical Report 91-16 Politecnico di Milano, Italy.1991.
[Dorigo, 1996] M. Dorigo, V. Maniezzo, A. Colorni,, The Ant System: Optimization by a
Colony of Cooperating Agents, IEEE Transactions on Systems, Man and Cybernetics-Part B,
1(26): p. 29-41. 1996.
[Dorigo, 1997a] M. Dorigo, M. Gambardella, M. Ant Colony for the Traveling Salesman
Problem, BioSystems, (43): 73-81, 1997.
[Dorigo, 1997b] M. Dorigo, M. Gambardella, Ant Colony System: A Cooperative Learning
Ap. roach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary
Computation Vol 1: p. 53-66 1997.
[Dorigo, 2004] M .Dorigo, T. STUZLE,. Ant Colony Oprimization. MIT Press, Cambridge,
MA, 2004.
[Duchesnay, 2001] E. Duchensnay Agents situés dans l’image et organisés en pyramide
irrégulière.Contribution à la segmentation par une approche d’agrégation coopérative et
adaptative. Thèse deDoctorat de l’Université de Rennes-1 2001.
180
[Forgey, 1965] E.M. Forgey. Cluster analysis of multivarariate data : efficiency versus
interpretability of classification. Biometrics, 21, 1965.
[Forrest, 1990] S. Forrest, émergent computation: self-organizing, collective, and cooperative
phenomena in natural and artificial computing networks, Proceedings of the Ninth annual
CLNS conference, 1990..
[Freixenet. 2002] J. Freixenet, X. Muñoz, D. Raba, J. Marti, et X. Cufi. Yet Another Survey
on Image Segmentation : Region and Boundary Information Integration. ECCV, pages 408–
422, 2002.
[Fu, 1980] K.S. Fu and J.K. Mui, A survey on image segmentation, Pattern
Recognition, vol. 13, p. 3-16, 1980.
[Fuh, 2000] C. Fuh, S. Cho and K. Essig. Hierarchical Color Image Region Segmentation for
Content-Based Image Retreival Systems. IEEE Transactions on Image Processing, vol. 9, no.
1, pp. 156-162, 2000.
[Gambardella, 1997] L. Gambardella, M. Dorigo, HAS-SOP: An hybrid ant system for the
sequential ordering problem, Technical Report (11), IDSIA, Lugano, CH. 1997
[Geman, 1984] S. Geman et D. Geman. Stochastic relaxation, Gibbs distributions, and the
Bayesian restoration of images. IEEETrans. on Pattern Analysis and Machine Intelligence,
6(6) :721–741, novembre 1984.
[Georgé, 2004] J-P Georgé Résolution de problèmes par émergence, Etude d’un
Environnement de Programmation Emergente , Thèse de l’Université Paul Sabatier,
Toulouse, Juillet 2004.
[Germond, 1999] L. Germond Trois principes de coopération pour la segmentation en
imagerie de résonance magnétiques. Thèse de doctorat de l’université Joseph Fourrier
Grenoble I. 11 Octobre 1999.
[Giraudon, 1987] G. Giraudon, Chaînage efficace de contours, Rapport interne
INRIAn°605, janvier 1987.
[Gleizes, 2004] M-P Gleizes Vers la résolution de problèmes par émergence Habilitation à
diriger des recherches de l'Université Paul Sabatier Spécialité : Informatique, 2004.
[Goldberg, 1989] D. Goldberg Genetic Algorithms in Search, Optimization and Machine
Learning, Addison-Wesley, 1989.
181
[Holland, 1999] O.E Holland and Melhuish.C. Stigmergy, self-organization, and sorting in
collective robotics. Artificial Life, 5 :173–202, 1999.
[Hong, 1984] T. H. Hong et A. Rosenfeld. Compact region extraction using weighted pixel
linking in a pyramid. IEEE Trans. Pattern Analysis and Machine Intelligence 6(2):222-229,
1984.
[Hopfield, 1982] J. Hopfield, Neural networks and physical systems with emergent
collective computational abilities, Proceedings of the National Academy of Sciences 79 :
2554-2558,1982.
[Horaud, 1995] R. Horaud and O. Monga, Vision par ordinateur: outils fondamentaux
,edition Hermes, 1995
[Horne, 1990] C. Horne. Unsupervised image segmentation. PhD thesis. Ecole Polytechnique
Fédérale de Lausanne. Switzerland, 1990.
[Horwitz, 1976] S.L. Horowitz, and T. Pavlidis. Picture segmentation by a tree traversal
algorithm. Journal of the association for computing matchinery, 23(2): 368-388.
[Hu, 1992] Hu, Y., Dennis, T.J., 1992. Simulated annealing and iterated conditional modes
with selective and confidence enhanced update schemes. In: Proc. 5th Annual IEEE Symp.
Computer-based Medical Systems, pp. 257–264.
[Hueckel, 1971] M.F Hueckel An operator which locates edges in digitized pictures, J.
Ass.Comput. Mach, vol. 18, nº 1, pp. 113-125, 1971.
[Jaggi, 1998] C. Jaggi Segmentation par méthode Markovienne de l’encéphale humain en
imagerie par résonance magnétique théorie, mise en œuvre et évaluation. Thèse de Doctorat
de l’Université de CAEN. 1998.
[Jain, 1988] A.K Jain et R.C Dubes Algorithms for clustering Data. Prentice Hall Advanced
Reference series, 1988.
[Jain, 1999] A.K. Jain, M.N. Murty, and P.J. Flynn. Data clustering : a review. ACM
Computing Surveys, 31(3) :264*322, 1999.
[Jain, 2000] A. Jain, R.Duin et J.Mao. Statistical Pattern Recognition : A review. IEEE
Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No.1, pp 4-37 , 2000.
[Jolion, 1989] J.M. Jolion. Analyse d’images : le modèle pyramidal. Traitement du Signal.
1989.
[Kapur, 1985] J.N. Kapur, P. K. Sahoo and A. K.C. Wong . A new method for gray-level
picture thresholding using the entropy of histogtram CVGIP 29 pp.273-2851985
[Kara-Falah, 1995] R. Kara-Falah. Segmentation d’images : Coopération, fusion,
évaluation. Thèse de doctorat, Université de Savoie, Juin 1995.
[Kass, 1988] M. Kass A. Witkin , D. Terzopoulos Snakes: Active contour models,
Computer Vision, Graphics, and Image Processing, : pp. 321-331, 1988.
[Kato, 1994] Z. Kato, Modélisation Markoviennes Multiresolutions en vision par ordinateur.
Application à la segmentation d’images SPOT, Thèse de l’Université de Nice Sophia
Antipolis. 1994.
[Kennedy 1995] J. Kennedy , R-C. Eberhart, Particle swarm optimization. In Proceedings of
the 1995 IEEE International Conference on Neural Networks, volume IV, pages 1942-1948,
Piscataway, NJ, 1995. IEEE Service Center.
183
[Lee, 1990] S.U. Lee and S.Y. Chung, A comparative study of several global
thresholding techniques for segmentation, Computer Graphics and Image Processing, vol. 52,
171-190, 1990.
[Lee, 2000] C. Lee and E. Antonsson. Dynamic Partitional Clustering Using Evolution
Strategies.In The Third Asia-Pacific Conference on Simulated Evolution and Learning, 2000.
[Leung, 2000] Y. Leung, J. Zhang and Z. Xu. Clustering by Space-Space Filtering. IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no.12, pp. 1396-1410,
2000.
[Kirkpatrick, 1985] S. Kirkpatrick, D.C. Gelatt, and M.P.Vechhi. Optimization by simulated
annealing. Science, 220 :671–680, May 1983.
[Levine, 1985] M. D. Levine et Ahmed M. Nazif. Dynamic Measurement of Computer
Generated Image Segmentations. IEEE Transaction on Pattern Analysis and Machine
intelligence, PAMI-7(2) : 155–164, March 85.
[Liew, 2000] A.W.C. Liew, S.H. Leung, et W.H. Lau. Fuzzy image clustering incorporating
spatial continuity. IEE Proceedings on Vision Image Signal Processing, 147(2) :185–192,
April 2000.
[Lim, 1990] Y. W. Lim et S. U. Lee. On the color image segmentation algorithm based on the
thresholding and the fuzzy c-means techniques. Pattern Recognition, 23(9) :935–952, 1990.
[Liu, 1994] J. Liu, Y.H. Yang, Multiresolution color image segmentation, IEEE Trans. On
PAMI, 16(7), (1994) 689-700
[Liu., 1999] J. Liu , Y. T. Tang Adaptive Image Segmentation With Distributed Behavior-
Based Agents . IEEE Trans. On PAMI 21(6) – p.544-551 1999.
[Lopès, 1999] A. Lopès, R. Fjørtoft, D. Ducrot, P. Marthon, and C. Le maréchal.
Segmentation of SAR images in homogeneous regions. In C. H. Chen, editor, Information
Processing for Remote Sensing. World Scientific Publishing Co., Singapore, 1999.
[Lumer, 1994] E.D Lumer, et B. Faieta, Diversity and adaptation in populations of clustering
ants, in D. Cli®, P. Husbands, J. Meyer and S. Wilson (eds), From Animals to Animats 3,
Proceedings of the 3rd International Conference on the Simulation of Adaptive Behavior,
The MIT press/Bradford Books.1994.
[Lutton, 2003] E. Lutton, Algorithmes génétiques et algorithmes évolutionnaires, Traité
d'Informatique Industrielle, 2003.
[MacQeen, 1967] L. MacQueen. Some methods for classification and analysis of multivariate
observations. In Proceeding 5th Berkeley Symp., pages 281–297, 1967.
[Maniezzo, 1994] V. Maniezzo, A. Colorni, M. Dorigo,, The Ant System Applied to the
Quadratic Assignment Problem”, Technical Report. IRIDIA. (28), Université Libre de
Bruxelles, Belgium, 1994.
[Marr, 1980] D. Marr, H. Hildreth, Theory of edge detection, Proceedings of the Royal
Society of London B207, p 187-217, 1980.
[Marroquin, 1985] J.L. Marroquin, Optimal Bayesian estimation for image segmentation and
surface reconstruction, MIT.AI.MEMO 893, 1985
[Martinoli, 1999] A. Martinoli, A. Ijspeert, et L. Gambardella, . . A Probabilistic Model for
Understanding and Comparing Collective Aggregation Mechanisms In (Floreano et al.,
1999), pages 575–584. 1999.
185
[Rouquet, 1998] C. Rouquet, P. Bonton, and R. Tomczak, Etude comparative des stratégies
de segmentation non supervisée en régions par champs de markov,” Traitement du Signal,
1998, vol. 15, n° 1, p. 39-55.
[Rumelhart 1986] D.E. Rumelhart, G.E. Hinton, R.J. Williams, Learning internal
representations by error propagation, in: vol. I, Parallel Distributed Processing: Explorations
in the microstructure of Cognition, D.E. Rumelhart and J.L. McClelland, eds., MIT Press,
Cambridge, pp.319-362, 1986.
[Saarinen, 1994] K. Saarinen. Color image segmentation by a watershed algorithm and region
adjacency graph processing. In ICIP’94 : Int. Conf. on Image Processing, pages 1021–1024,
1994.
[Saarinen, 1994] K. Saarinen. Color image segmentation by a watershed algorithm and region
adjacency graph processing. In ICIP’94 : Int. Conf. on Image Processing, pages 1021–1024,
1994.
[Sahoo, 1988] P.K. Sahoo, S. Soltani, A.K.C. Wong and Y.C. Chen, A survey of
thresholding techniques, Computer Vision Graphics and Image Processing,vol. 41, p. 233-
260, 1988.
[Sahoo. 1988] P. K. Sahoo, S. Soltani, A. K. C.Wong, et Y. C. Chen. A survey of
thresholding techniques. CVGIP, 41 : 233–260, 1988.
[Salzenstein , 1998] F. Salzenstein and W. Pieczynski, Sur le choix de la méthode de
segmentation statistique d’images,” Traitement du Signal, 1998, vol. 15, n° 2, p. 119-127.
[Schettini, 1993] R. Schettini. A segmentation algorithm for color images. Pattern
Recognition Letters, 14 :499–506, 1993.
[Schwefel, 1981] H. Schwefel Numerical Optimisation of Computer Models, Wiley,
Chichester, 1981.
[Semet, 2003] Y. Semet, E. Lutton and P.Collet. Ant Colony Optimization for e-learning :
Oberserving the emergence of pedagogic suggestions. In IEEE Swarm Inteligence
Symposium 2003, Indianapolus, Indiana, april 2003.
[Shen, 1986] J. Shen and S. Castan. An optimal linear operator for edge detection. In Proc.
IEEE Computer Society Conference on Computer Vision and Pattern Recognition
(CVPR’86), pages 109--114, Miami Beach, Florida, USA, June 22--26 1986.
[Shen, 1992] [J. Shen and S. Castan_ An optimal linear operator for step edge detection.
CVGIP. Graphics Models and Image Processing.54(2). 112-133, Mars 1992.
[Shufelt, 1999] J. A. Shufelt. Performance Evaluation and Analysis of monocular building
extraction from aerial imagery. Transaction on Pattern Analysis and Machine Intelligence,
21(4) : 311–326, 1999.
[Sobel, 1978] I. Sobel. Neighbourhood coding of binary images for fast contour following
and general array binary processing. Computer Graphics and Image Processing.8:127-
135,1978.
[Solnon, 2000] C. Solnon. Solving permutation constraint satisfaction problems with
artificial ants. In Proceedings of ECAI’2000, IOS Press, Amsterdam, The Netherlands, pages
118–122, 2000.
[Strasters, 1991] K. C. Strasters and J. J. Gerbrands, Three-dimensional image segmentation
using a split, merge and group approach,” Pattern Recognition Letters, 1991, vol. 12, p. 307-
325.
189
[Stützle, 1999] T. Stuzle, H.H. Hoos. The max-min ant system and local search for
Combinatorial Problems, in Meta-heuristics : advances and trends in local search paradigms
for Optimization” by S. VOSS, I.H. OSMAN and C. ROUCAIROL, Kluwer Academic
Publishers, Boston, 1999, p. 313-329.
[Stützle, 2000] T. Stützle, H. H. Hoos, MAX-MIN ant system, Future Generation Computer
Systems, Vol. 16 (2000)
[Syswerda, 1991] Syswerda, G. A study of reproduction in generational and steady-state
genetic algorithms. In Rawlins, editor, Foundation of Genetic Algorithms. Morgan Kaufman,
1991.
[Taillard, 1999] E. Taillard, Ant systems, `Handbook of Applied Optimization”, P.
PARDALOS, M.G.C RESENDE.
[Taillard, 1997] Taillard, L., Gambardella, L. (1997), An Ant Approach for Structured
Quadratic Assignment Problems”, 2nd Metaheuristic International Conference (MIC-97),
Sophia-Antipolis, France.
[Tang, 1999] L. Tang, L. F. Tian, et B. L. Steward. Color Image Segmentation with Genetic
Algorithm for In-Field Weed Sensing. ASAE, 1999.
[Theraulaz, 1997] G. Theraulaz, F. Spitz, Auto-organisation et comportement, Hermès, Paris,
1997.
[Tikhonov, 1974] A. N. Tikhonov, et V.Y. Arsenin, méthodes de résolution de problèmes
mal poses, MIR, Moscou, 1974.
[Topin, 1999] X. Topin Etude de l'auto-organisation par coopération appliquée à
l'apprentissage comportemental de robots fourmis , DEA RCFR – Université Paul Sabatier,
Toulouse Juin 1999.
[Tou, 1974] J. Tou et R. Gonzalez. Pattern Recognition Principles. Addison-Wesley ,
Massachusettsn, USA, 1974.
[Tou, 1979] J. Tou, DYNOC- A Dynamic Optimal Cluster Seeking Technique. International
Journal of Computer and Information sciences, vol.8, no.6, pp. 541-547, 1979.
[Trémeau, 1997] A. Trémeau et N. Borel. A region growing and merging algorithm to color
segmentation. Pattern Recognition, 30 :1191–1203, 1997.
[Tseng, 2001] L.Y. Tseng, S.B. Yang, A genetic approach to the automatic clustering
problem, Pattern Recognition, vol. 34, No. 2, pp. 415-424, 2001
[Turi, 2001] R.H. Turi Clustering-Based Color Image Segmentation, Phd Thesis. Monash
University, Australia 2001.
[Ünsal, 1993] C. Ünsal Self-organization in large populations of mobile robots Master of
Sciences in Electrical Engineering, May 1993, Blacksburg, Virginia.
http://armyant.ee.vt.edu/unsalWWW/cemthesis.html.
[Van de Vijver, 1997] G. Van De Vijver, Emergence et explication, Intellectica : Emergence
and explanation, 1997/2 n°25, ISSN n°0984-0028 185-194, 1997.
[Varela, 1988] F. Varela Autonomie et connaissance : essai sur le vivant Editions du seuil –
1988.
[Veenman, 2003] C.J. Veenman_, M.J.T. Reinders, and E. Backer. IEEE Transactions on
Image Processing, Vol. 12, No. 3, pp. 304-316, March 2003.
190