Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

SEGMENTATION Module D9 ES322 - Traitement d’Image et Vision Artiﬁcielle Jean-Ch

SEGMENTATION Module D9 ES322 - Traitement d’Image et Vision Artiﬁcielle Jean-Christophe Baillie 2003 1 Segmentation 1 Description du problème Fondamentalement, la segmentation est un processus qui consiste à découper une image en régions connexes présentant une homogénéité selon un certain cri- tère, comme par exemple la couleur. L’union de ces régions doit redonner l’image initiale ([8, 7, 11, 10, 14]). La segmentation est une étape importante pour l’extraction des informations qualitatives de l’image. Elle fournit une description de haut niveau : chaque région est connectée à ses voisines dans un graphe et chaque région porte une étiquette donnant des informations qualitatives comme sa taille, sa couleur, sa forme, son orientation. L’image se réduit donc à un graphe de noeuds étiquetés qui contient presque toute l’information utile au système. Les arcs du graphe peuvent être va- lués précisant si les deux régions connectées sont en simple contact ou si l’une est incluse dans l’autre. D’autres informations topologiques peuvent également être stockées comme par exemple le fait qu’une région est au dessus d’une autre. Selon les techniques de segmentation utilisées, la construction de ce graphe peut être plus ou moins complexe. On regroupe généralement les algorithmes de segmentation en trois grandes classes (voir [14])1 : 1. Segmentation basée sur les pixels 2. Segmentation basée sur les régions 3. Segmentation basée sur les contours La première catégorie travaille sur des histogrammes de l’image. Par seuillage, clustering ou clustering ﬂou, l’algorithme construit des classes de couleurs qui sont ensuite projetées sur l’image. La segmentation est implicite puisqu’on sup- pose que chaque cluster de l’histogramme correspond à une région dans l’image. En pratique, ce n’est pas forcément le cas et il faut séparer les régions de l’image qui sont disjointes bien qu’appartenant au même cluster de couleur. Ces algo- rithmes sont assez proches des algorithmes de réduction de couleur. 1On peut également considérer une quatrième classe qui serait constituées des algorithmes basés sur les régions+contours, voir par exemple [2, 15, 1] 2 La deuxième catégorie correspond aux algorithmes d’accroissement ou de dé- coupage de région. L’accroissement de région est une méthode bottom-up : on part d’un ensemble de petites régions uniformes dans l’image (de la taille d’un ou de quelques pixels) et on regroupe les régions adjacentes de même couleur jusqu’à ce qu’aucun regroupement ne soit plus possible. Le découpage de région est le pendant top-down des méthodes d’accroissement : on part de l’image entière que l’on va subdiviser récursivement en plus petites régions tant que ces régions ne seront pas sufﬁsamment homogènes. Les algorithmes dit “split and merge” sont un mélange de ces deux approches et nous en décrirons deux exemples : le “split and merge” classique et l’algorithme CSC. La troisième catégorie s’intéresse aux contours des objets dans l’image. La plupart de ces algorithmes sont locaux, c’est à dire fonctionnent au niveau du pixel. Des ﬁltres détecteurs de contours sont appliqués à l’image. Le résultat est en général difﬁcile à exploiter sauf pour des images très contrastées. Les contours extraits sont la plupart du temps morcelés et peu précis et il faut utiliser des tech- niques de reconstruction de contours par interpolation ou connaître a priori la forme de l’objet recherché. Formellement, ce type d’algorithme est proche des techniques d’accroissement de région fonctionnant au niveau du pixel. Ces tech- niques purement locales sont en général trop limitées pour traiter des images brui- tées et complexes. Les algorithmes que nous allons présenter et commenter sont : 1. Accroissement de région fonctionnant au niveau du pixel. 2. Split and merge classique (d’après [9]). 3. Algorithme CSC (d’après [12]) : un algorithme de “merge and split” qui donne d’excellents résultats et qui possède un certain nombre de propriétés intéressantes. 2 Accroissement de région Les méthodes d’accroissement de région sont les méthodes de segmentation les plus simples. Le principe est basé sur une approche bottom-up : l’algorithme part de petits éléments de l’image qu’il va tenter de regrouper en éléments plus im- portants. Nous présentons ici la version de base de l’algorithme d’accroissement de région qui fonctionne en agrégeant des pixels. 3 2.1 Principe de fonctionnement Supposons une région de couleur homogène R. Initialement, R = 1 pixel. On va étendre la région R en incluant les pixels situés sur la frontière et dont la couleur est proche de celle de R (la variation de couleur est inférieure à un seuil δ, caractéristique de ce type d’algorithmes). En répétant cette procédure jusqu’à ce qu’il n’y ai plus de pixels de couleur assez proche sur la frontière, on obtient une région de couleur homogène maximale autour du pixel de départ. La région ini- tiale “gonﬂe” en absorbant des pixels de la frontière, jusqu’à stabilité par rapport à la propriété d’homogénéité2. Cette méthode présente deux limitations sévères qui n’en font pas une méthode très efﬁcace : 1. Les régions obtenues dépendent fortement des pixels d’amorçage choisis et de l’ordre dans lequel les pixels de la frontière sont examinés. 2. Le résultat ﬁnal est très sensible à la valeur du seuil δ. Pour illustrer le premier problème, considérons trois pixels adjacents a, b et c dont les intensités respectives sont 8,10 et 11 (par exemple, l’intensité en niveaux de gris). Le seuil est 2. La région initiale est constituée du pixel b. Deux schémas de regroupement pour les points frontière a et c sont possibles (ﬁg 1) Le pixel central b est l’amorce. Compte tenu du seuil δ = 2, a et c sur la frontière devraient être ajoutés à l’amorce b. Si l’on commence par tenter d’aggré- ger a, le résultat du regroupement, noté [ab], a pour intensité moyenne 9 et c s’y ajoute ensuite puisque |11 −9| ≤δ. On a donc regroupé a, b et c. Si maintenant l’algorithme commence par examiner le point frontière c, le groupement de b et c donne [bc] dont l’intensité est 10, 5. Le point frontière a d’intensité 8 est trop éloigné et il est considéré comme appartenant à une autre région. On obtient donc deux groupements au lieu d’un. Ce petit exemple illustre combien l’ordre d’examen des points sur la frontière peu inﬂuencer sur le résultat de l’algorithme. A fortiori, cet algorithme est égale- ment très sensible au choix des amorces. Par ailleurs, comme nous allons le voir, le résultat ﬁnal dépend très sensible- ment du seuil. Une petite variation de ce seuil peu conduire à des modiﬁcations importantes. 2Cette méthode est très générale est peu être appliquée avec n’importe quel critère permettant de décider si l’on doit ajouter ou non un point de la frontière à la région. 4 10 11 8 δ=2 a b c 10 11 8 a b c 9 11 ab c 10 abc 10 11 8 a b c 8 10,5 a bc 8 10,5 a bc FIG. 1 – Deux schémas de regroupement pour des pixels a, b et c Cet algorithme fait parti de la classe d’algorithmes de segmentation dit “lo- caux”. L’opération élémentaire consiste à manipuler des pixels adjacents et l’al- gorithme n’a aucune vision globale du résultat qu’il obtient. Par exemple, il est incapable de détecter que la région qu’il vient de construire est inhomogène3, ce qui est souvent le cas. 2.2 Implémentation Nous présentons ici une méthode classique pour implémenter cet algorithme. On associe à chaque pixel de l’image un index qui est un nombre entier. Le but de l’algorithme va être de donner à chaque pixel une valeur d’index qui corresponde à un numéro de région. Pour connaître ensuite l’étendu de la région n, il sufﬁra d’extraire tous les pixels dont l’index vaut n. L’index de chaque pixel est initialement ﬁxé à -1, valeur indiquant que l’in- dex n’a pas encore été attribué. On parcourt l’image de haut en bas et de gauche à droite. Plaçons nous en cours d’exécution : pour chaque pixel c examiné, on considère les pixels adjacents c1, c2, c3 qui ont déjà été examinés : 3L’algorithme présenté ici ne tient compte que de la valeur moyenne de la couleur. il est donc possible d’obtenir des régions avec un très fort écart type. Une amélioration possible de l’algo- rithme permet de tenir compte de l’écart type sur lequel est ﬁxé un second seuil. 5 C3 C1 C2 C position courante sens de parcours NB : Certaines implémentations de l’algorithme n’utilisent pas c1. Les régions construites peuvent alors présenter des coupures sur des points de connection ar- ticulés autour de deux pixels en diagonale. On va ensuite choisir parmi c1, c2, c3 l’ensemble des pixels dont la couleur est identique à celle de c, à un facteur de tolérance δ près. Si cet ensemble est vide, on crée un nouvel index que l’on attribue au pixel courant c (il existe un compteur d’index qui permet de savoir quel est le prochain nouveau numéro d’index libre). Si cet ensemble n’est pas vide et que chaque pixel le constituant a le même index k, il sufﬁt d’attribuer l’index k au pixel courant c. Dans le cas contraire, la situation est un peu plus complexe. Supposons que c1 et uploads/Geographie/ poly-segmentation-ensta-baillie.pdf