CONTRIBUTION A LA SEGMENTATION  PAR MET AHEURISTIQUES EN OPTIMI SATION MONO‐OBJECTIF   

CONTRIBUTION A LA SEGMENTATION  PAR MET AHEURISTIQUES EN OPTIMI SATION MONO‐OBJECTIF   

Dans  ce  chapitre,  nous  présentons  six  méthodes  de  segmentation  d’images  basées  sur  des  métaheuristiques. Notre but est de proposer de nouveaux critères de segmentation et d’adapter les  métaheuristiques  suivantes :  recuit  simulé (Nakib,  et  al.,  2006a)  ,  recuit  microcanonique  (Nakib, et  al., 2007b), OEP (Nakib, et al., 2007c; Nakib, et al., 2007a), colonies de fourmis, et non pas de faire  une étude comparative de ces différentes métaheuristiques. Le chapitre sera terminé par une étude  comparative de résultats de segmentation sur des images synthétiques. Les  images  réelles  de  test  que  nous  avons  choisies  pour  illustrer  les  différentes  méthodes,  sont  présentées sur la figure 3.1. Ces images sont issues de la base de données de l’université de Berkeley (Berkekey, 2007). Nous faisons remarquer que le nombre de classes, dans ce chapitre, est supposé  connu a priori. En  pratique,  le  problème  d’approximation  d’histogramme  est  un  problème  d’optimisation  non  linéaire  avec  des  minima  locaux.  La  figure  3.2  illustre  cette  problématique.  Lors  de  l’utilisation  d’un algorithme de recherche local (Gauss‐Newton) pour la segmentation (Synder, et al., 1990), sur  les figures 3.2 (a) et (c), la méthode permet d’avoir un bon résultat de segmentation et une bonne  approximation de l’histogramme, respectivement, grâce à une bonne initialisation de l’algorithme de  Gauss‐Newton.  Cependant,  sur  les  figures  3.2.  (b)  et  (d),  les  résultats  obtenus  sont  moins  bons,  du  fait  d’une  mauvaise  initialisation  de  l’algorithme.

L’objet  de  cette  section  est  d’introduire  la  métaheuristique du recuit simulé, adaptée au cas continu (RSC), afin d’améliorer les performances du  seuillage  d’images  à  partir  de  l’histogramme,  tout  en  évitant  la  phase  critique  d’initialisation  de  l’algorithme  d’optimisation.  Ce  problème  a  déjà  été  traité  dans  la  littérature  avec  l’approche  OEP  (Chap.  2,  section  2.4).  Cependant,  nous  avons  voulu  adapter  la  métaheuristique  du  recuit  simulé,  notamment  pour  améliorer  les  performances  de  la  segmentation  et  garder  l’avantage  de  l’utiliser  comme une boîte noire, notamment pour les biologistes. Pour  un  histogramme  donné,  l’algorithme  qui  permet  de  trouver  le  seuil  optimal  est  détaillé  dans  (section  1.4.2)  Avant  de  rechercher  les  seuils  optimaux,  il  faut  déterminer  les  paramètres  des  gaussiennes qui permettent de reconstruire l’histogramme de l’image d’origine. Les deux critères les  plus utilisés sont le critère du maximum de vraisemblance et celui de l’erreur quadratique moyenne.  Pour un histogramme donné, l’erreur de reconstruction est définie par l’expression suivante:Plusieurs  travaux  ont  été  publiés,  portant  sur  l’adaptation  du  recuit  simulé  afin  de  résoudre  des  problèmes  d’optimisation  en  continu  (Dréo,  et  al.,  2003),  dans  différents  domaines  d’applications  (électronique (Siarry, et al., 1997), chimie (Agrafiotis, 2001), …). Pour plus d’informations, on pourra  consulter (Dréo, et al., 2003).

Notre  approche  consiste  à  ajuster  la  valeur  de  la  constante  de  Boltzmann  durant  la  simulation,  de  telle  sorte  que  la  probabilité  d’accepter  les  solutions  dégradantes  à  la  température  finale  soit  un  nombre « faible » prédéfini (0,5%). Pour adapter le recuit simulé au cas continu, nous définissons un  paramètre de contrôle de la discrétisation de l’espace de recherche. Nous ajustons automatiquement  ce  paramètre,  en  fonction  du  taux  d’acceptation  des  modifications  tentées,  tout  au  long  de  la  descente de température. Enfin, nous avons défini un pas de discrétisation de l’espace de recherche  (un pas différent pour chaque paramètre).<<<  (idem pour les seuils si dérivant de l’image moyennée). Pour résumer, le  problème  de  la  segmentation  revient  à  chercher  dans  l’espace  des  vecteurs  de  segmentation  potentiels celui qui maximise l’entropie totale donnée parl’expression (3. 5) :Notre contribution dans cet algorithme consiste à ajouter une « liste tabou », qui contient toutes les  configurations déjà évaluées. Cette modification nous permet d’éviter de revisiter les configurations  déjà évaluées, afin de réduire le nombre d’évaluations de la fonction objectif. L’utilisation  du  recuit  microcanonique  permet  d’avoir  de  bons  résultats  de  segmentation  et  une  reproductibilité  meilleure,  du  fait  de  l’absence  de  caractère  stochastique  dans  la  recherche  de  la  solution optimale. Le seul caractère probabiliste est celui de la recherche dans le voisinage.

Du point  de  vue  vitesse  de  convergence,  cet  algorithme  est  plus  rapide  que  le  recuit  simulé,  ce  qui  est  en  accord avec la comparaison faite dans (Herault, et al., 1993).Dans  cette  section,  nous  présentons  un  algorithme  basé  sur  une  mesure  d’information  appelée  l’ »entropie  exponentielle ».  Cet  algorithme  permet  de  pallier  aux  problèmes  de  l’entropie  de  Shannon,  celle‐ci  n’est  pas  définie  pour  les  probabilités  nulles.  Afin  d’accélérer  la  convergence  de  l’algorithme  du  recuit  microcanonique  (MC),  nous  avons  hybridé  avec  ce  dernier  l’algorithme  du  simplex  de  Nelder‐Mead  (NM).  Nous  allons  présenter  l’entropie  exponentielle  et  l’étendre  au  cas  bidimensionnel, afin de prendre en compte l’information spatiale (Nakib, et al., 2007b).