Admin CliCours
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).
Télécharger le document complet
