Admin CliCours
ADAPTATION DE L’APPROCHE PARETO A LA SEGMENTATION
Ce chapitre est consacré au développement d’une méthode de segmentation basée sur l’optimisation multiobjectif par l’approche Pareto (SMOP). Ce type d’approche est déjà présenté dans la section 2.3.3. Le principe consiste à optimiser plusieurs critères de segmentation, et à trouver la solution qui permet d’avoir un compromis entre les différents critères. Pour résoudre ce problème, nous utilisons l’algorithme de référence en optimisation multiobjectif : NSGA‐II. C’est la deuxième version de l’algorithme NSGA (« Non dominated Sorting Genetic Algorithm ») (Deb, et al., 2002). La figure 6.1 illustre le principe de base de la segmentation par optimisation multiobjectif au sens de Pareto. Dans la première section de ce chapitre, nous formulons le problème de segmentation d’images par optimisation multiobjectif suivant l’approche Pareto. La deuxième section est consacrée aux différents critères utilisés dans l’algorithme. La métaheuristique utilisée décrite est dans la troisième section. Dans la quatrième section, nous présentons l’algorithme de segmentation. Des résultats de segmentation des images test maison et avion sont présentés dans la cinquième section. La sixième section est réservée à l’étude comparative de notre méthode avec celles déjà développées et celles issues de la littérature. Enfin, nous présentons, dans la septième section, les résultats de segmentations d’images IRM. Cette approche consiste à utiliser la notion de dominance pour faire converger la population vers un ensemble de solutions efficaces, et sélectionner, en fin d’analyse, la solution optimale, au sens d’un compromis entre les différentes fonctions objectif. Ce concept permet donc d’avoir un ensemble de solutions, dans lequel nous ne retiendrons que la solution de compromis, afin de ne pas favoriser un critère par rapport à un autre.
L’ALGORITHME NSGA‐ II
DansNSGA‐II, la complexité de calcul a été réduite grâce à la modification de la procédure de tri de la population, en la répartissant en plusieurs fronts. La complexité totale de l’algorithme est de l’ordre Dans la première version de l’algorithme NSGA, une fonction de partage des performances (« sharing ») était utilisée pour maintenir la diversité. Cependant, cette procédure est fortement consommatrice en temps de calcul. De plus, elle exige le réglage de plusieurs paramètres. Dans NSGA‐II, les auteurs ont remplacé la fonction de partage de performance par une fonction de remplacement (« crowding »). Le principe consiste à définir deux attributs à chaque individu : plus élevé est privilégiée. En d’autres termes, lorsque deux solutions en compétition ont le même rang, celle qui est située dans une région où il y a peu de points est choisie. Cette procédure permet d’avoir un front de Pareto bien étalé. La figure 6.3 illustre le principe de fonctionnement de NSGA‐II. A chaque itération, une population d’enfants Qt de taille N est engendrée à partir d’une population Pt de parents de même taille. Les deux populations sont alors combinées dans une population Rt de taille 2xN. Cette nouvelle population est triée en plusieurs fronts, selon le degré de non‐dominance. Une fois la procédure de tri terminée, une nouvelle population Pt+1 de taille N est alors créée à partir des solutions des différents fronts de Rt. Comme la taille de Rt est le double de Pt+1, tous les fronts qui ne pourront pas être contenus dans Pt+1 sont supprimés. Dans le cas où le nombre de solutions est supérieur au nombre de places, les individus ayant l’attribut idistance élevé sont choisis, tandis que les autres sontDans l’expression (6.4), les pij sont les valeurs normalisées de la matrice COO. Cette matrice permet de caractériser les textures présentes dans l’image. La figure 6.4 illustre respectivement, en trois dimensions, les matrices de cooccurrence des images tests maison et avion.
Tout d’abord, il faut reproduire NSGA‐II et l’adapter au problème de la segmentation d’images (Algorithme 6.1). Le choix de cet algorithme de référence s’explique par sa réputation dans le domaine de l’optimisation multiobjectif. De plus, il nécessite peu de réglages de paramètres. Une étude récente (Shukla, et al., 2007) a montré qu’il obtient de bonnes performances sur différents problèmes en multiobjectif. Nous utilisons un opérateur de sélection par tournoi. Son principe est le suivant : à partir de la population totale (parents et enfants), une moitié de la population est prise de manière aléatoire pour participer au tournoi. La moitié la plus faible des individus participant à ce tournoi est à son tour éliminée, tandis que l’autre est gardée. Nous avons fixé le nombre de tournois à 5.
Télécharger le document complet
