ADAPTATION DE L’APPROCHE PARETO A  LA SEGMENTATION 

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.