MET AHEURISTIQUES D’OPTIMISATION E T SEGMENTATION

MET AHEURISTIQUES D’OPTIMISATION E T SEGMENTATION

FORMULATION DU PROBLEME DE LA SEGMENTATION

Dans cette section, nous montrons que la segmentation d’une image par l’approche « basée région », ou par seuillage, peut se ramener à un problème d’optimisation, le plus souvent NP‐difficile (Horaud, et al., 1995). D’où la nécessité d’utiliser une métaheuristique. La segmentation d’une image I utilisant un attribut d’homogénéité A, est fréquemment définie comme une partition 1,…, P = R Rn de I, telle que : 1. ,i I = ∪R i n ∈[1, ] 2. Ri est connexe, ∀ ∈i n [1, ] 3. ( ) vrai A Ri = , ∀ ∈i n [ ] 1, 4. ( ) faux AR R i j ∪ = , ∀ ∈i n [ ] 1, , pour tout couple (R R i j , ) de régions connexes.

Nous faisons observer que l’unicité de la segmentation n’est pas garantie par ces quatre conditions. Les résultats de segmentation dépendent non seulement de l’information contenue dans l’image, mais aussi de la méthode utilisée pour traiter ces informations. Généralement, pour réduire le problème de la non unicité de la solution, le problème de la segmentation est régularisé par une contrainte d’optimisation d’une fonction F, caractérisant la qualité d’une bonne segmentation. Donc, une cinquième condition est ajoutée aux quatre premières : où F est une fonction décroissante et ( ) PA I est l’ensemble des partitions possibles de I. Il est clair que la condition 5 ne résout pas entièrement le problème d’unicité de la segmentation.

Il demeure des cas où plusieurs segmentations peuvent avoir la même valeur optimale. Ce qui explique la nécessité d’appliquer des algorithmes à base de métaheuristiques. La détermination d’un vecteur de seuils optimaux (une configuration) dans l’espace des niveaux de gris rend la segmentation des images assimilable à un problème d’optimisation. D’où notre approche de la segmentation au travers des techniques destinées à résoudre ce type de problèmes. Un aperçu des différents critères de segmentation d’images a été présenté dans le chapitre précédent. Comme nous pouvons le constater, cet ensemble de critères n’est pas exhaustif, à l’instar des nombreux articles récents en traitement d’images.

La conclusion à laquelle nous sommes parvenus, est qu’il n’existe pas de critère unique et suffisant pour segmenter de manière optimale toutes les images. Ceci nous a conduits à des schémas de systèmes (algorithmes) de segmentation qui regroupent plusieurs critères. Pour résoudre un problème segmentation d’images, il faut donc optimiser plusieurs critères simultanément. C’est dans cet objectif que nous faisons appel  à l’optimisation multiobjectif (multicritère).   Cette reformulation du problème de la segmentation d’images en un problème d’optimisation multiobjectif, nous conduit à la section suivante, où nous allons présenter les différentes approches dans ce domaine, dont certaines sont très peu utilisées en traitement d’images. 

L’OPTIMISATION MULTIOBJECTIF

L’optimisation multiobjectif est née du besoin en industrie de satisfaire plusieurs critères contradictoires, simultanément. Les bases de cette optimisation ont été posées par Pareto et Edgeworth au 19ème siècle (Pareto, 1896).

Ses théories trouvent leurs premières applications en économie et ces dernières années dans les sciences pour l’ingénieur (Talbi, 1999; Fonseca, et al., 1995; Gandibleux, et al., 2004; Hao, et al., 1999; Reeves, 1995; Reyes‐Sierra, et al., 2006; Collette, 2002a).   Les approches de résolution des problèmes multiobjectif peuvent être réparties en trois classes : approches basées sur la transformation du problème en un problème mono‐objectif (simple objectif), approches non‐Pareto et approches Pareto. Ces dernières sont décrites dans les paragraphes suivants. 

TRANSFORMATION EN UN PROBLEME MONO‐OBJECTIF

Cette approche, qualifiée d’approche naïve de l’optimisation multiobjectif (MO) (Collette, et al., 2002b), consiste tout simplement à transformer un problème multiobjectif en un problème mono‐ objectif, dont il existe de nombreuses méthodes de résolution (Collette, et al., 2002b; Agrafiotis, 2001). Parmi les méthodes qui utilisent cette approche, nous pouvons citer les méthodes d’agrégation (Sugeno, 1974; Srinivas, et al., 1995), les méthodes ε‐contraintes (Coello, et al., 1995), les méthodes de programmation par but et min‐max (Coello, et al., 1995).