Segmentation d’image et métaheuristiques d’optimisation

Segmentation d’image et métaheuristiques d’optimisation

Les métaheuristiques d’optimisation et la segmentation d’image font partie des domaines de recherche les plus actifs. Ces dernières années, plusieurs travaux ont créé le pont entre ces deux champs de recherche. En e et, le problème de segmentation d’image est formalisé comme un problème d’optimisation combinatoire.

D’où l’utilisation des métaheuristiques. De plus, l’ef f icacité des métaheuristiques pour résoudre des problèmes de grande taille a rendu possibles le traitement de plus grandes quantités d’informations, de caractéristiques d’image et de critères de segmentation.

Dans ce chapitre, sans prétendre l’exhaustivité, nous présentons les principales métaheu ristiques d’optimisation en premier lieu (section I.2). Ensuite, nous présentons les importantes familles de méthodes de segmentation, ainsi que leur amélioration à l’aide des métaheuristiques d’optimisation (section I.3).

Les métaheuristiques d’optimisation Les métaheuristiques sont des procédures de haut niveau conçues pour résoudre des pro blèmes d’optimisation dits di ciles. Ce sont en général des problèmes aux données incomplètes, incertaines, bruitées ou confrontés à une capacité de calcul limitée. Les métaheuristiques ont rencontré le succès dans une large variété de domaines.

Cela découle du fait qu’elles peuvent être appliquées à tout problème pouvant être exprimé sous la forme d’un problème d’optimisation de critère(s). Ces méthodes sont, pour la plupart, inspirées de la physique (recuit simulé), de la bio  (algorithmes évolutionnaires)

ou de l’éthologie (essaims particulaires, colonies de fourmis). Dans ce qui suit, nous présentons brièvement les principales métaheuristiques d’optimisation. Nous les classons en deux catégories : métaheuristiques à solution unique et métaheuristiques à population de solutions.

Les métaheuristiques à solution unique Les méthodes à solution unique, plus connues sous le nom de méthodes de recherche locale ou encore méthodes de trajectoire, sont basées sur l’évolution d’une seule solution dans l’espace de recherche. Typiquement, les méthodes de recherche locale démarrent d’une solution unique, puis à chaque itération, la solution courante est déplacée dans un voisinage local en espérant améliorer la fonction objectif.

Les méthodes à solution unique englobent principalement la méthode de descente, la recherche locale itérée, la recherche à voisinage variable, la méthode du recuit simulé et la recherche tabou.

Ces méthodes di èrent essentiellement dans leur manière d’exploiter le voisinage local, i.e, choix des candidats et critères de déplacement. Dans cette section, nous présentons les méthodes les plus utilisées dans les problèmes de segmentation d’image, notamment la méthode de descente, le recuit simulé et la recherche tabou.

La méthode de descente

La méthode de descente représente la technique la plus intuitive et la plus simple dans le domaine de l’optimisation. Appelée aussi hill climbing (par référence à un cas de maximisation de la fonction objectif), cette méthode fonctionne selon le principe suivant : en démarrant d’une solution aléatoire, à chaque itération la solution courante se déplace vers une meilleure solution présente dans son voisinage jusqu’à ce qu’aucune amélioration ne soit plus possible.

Le choix des solutions candidates dans le voisinage peut se faire de deux manières, soit évaluer la fitness de la fonction objectif pour toutes les solutions présentes dans le voisinage puis se déplacer vers la meilleure, soit choisir une solution aléatoire dans le voisinage, puis se déplacer vers cette solution si elle améliore le critère, ou sinon choisir une nouvelle solution. La procédure générale de cette méthode est présentée dans l’Algorithme I.1.