Méthodes de segmentation d’images à base de graphes

Introduction Un reproche qui peut être fait aux algorithmes traditionnels de traitement d’images est le manque de flexibilité des structures de données impliquées. L’organisation sous forme de simple grille génère en effet d’importantes contraintes vis-à-vis de leur exécution, limitant leur potentiel. Cela s’illustre particulièrement pour des problématiques liées à la « forme » des données. Par exemple, de nombreux algorithmes sont – sur le principe – capables de traiter des données de plus grande dimension, telles que des images tri-dimensionnelles ou encore des vidéos. Cependant, si un tel algorithme n’a pas été dès l’origine implémenté de façon à supporter des données de plus haute dimension, il est relativement complexe de le faire évoluer dans ce sens, et des développements spécifiques sont souvent requis 1 . De par leur structure, les graphes sont capables de représenter tout domaine discret. Il est ainsi possible de construire une représentation d’une image à l’aide d’un graphe en associant un nœud du graphe à chaque pixel. Par la suite, en établissant des relations entre les nœuds correspondants à des pixels voisins dans l’image, il est possible d’obtenir un graphe dont la topologie reflète l’organisation initiale des pixels, notamment les relations de voisinage. Cette représentation est beaucoup plus souple. Étant donné qu’il n’y a plus de notion de « bord de l’image », exécuter un algorithme sur une région d’intérêt – qu’elle soit rectangulaire ou non – peut simplement revenir à travailler sur un sous-graphe composé uniquement des nœuds appartenant à cette région. Par ailleurs, la structure de graphe faisant abstraction des dimensions de l’image, il est envisageable de traiter des données bi et tridimensionnelles exactement de la même manière ; seule l’étape de construction du graphe nécessite d’être adaptée aux données manipulées. Comme nous le verrons plus loin dans ce chapitre, de nombreux outils de traitement d’images basés sur les graphes reposent sur des algorithmes issus d’autre domaines, principalement de la théorie des graphes. Il devient alors possible de concevoir des algorithmes de traitement d’images à partir d’approches conçues pour des problématiques totalement différentes. Réciproquement, les graphes rendent possible d’appliquer des algorithmes de traitement d’images à des données qui ne sont pas des images. Ainsi, un algorithme de débruitage peut, par exemple, servir à lisser un maillage [Elmoataz et al., 2008]. Ce chapitre constitue un état de l’art des méthodes de traitement d’images à base de graphes. Nous réaliserons tout d’abord un rappel de notions usuelles de la théorie des graphes, puis enchaînerons sur les différentes méthodes permettant de représenter une image à l’aide d’un graphe. Nous terminerons ce chapitre par une revue des différentes familles de méthodes de segmentation d’images basées sur les graphes. 

Généralités sur les graphes, définitions et notations

 Un graphe est une représentation d’un ensemble d’éléments dans laquelle des relations peuvent être établies entre toutes paires d’éléments. Ceux-ci sont représentés par des nœuds, et les relations par des arêtes. Un graphe G = (V, E) est ainsi composé d’un ensemble V = {V1 . . . VN } de N nœuds et d’un ensemble E ⊂ V × V d’arêtes. Dans ce manuscrit, nous ne nous intéressons qu’aux graphes simples (il n’existe pas d’arête reliant un nœud à lui-même et il y a au plus une arête reliant deux nœuds) et non-orientés (si une relation existe entre deux nœuds, celle-ci est symétrique). Deux nœuds u, v ∈ V reliés par une arête (u, v) ∈ E sont dit adjacents ou encore voisins. Cette relation est notée u ∼ v. Réciproquement, l’arête (u, v) est dite incidente aux nœuds u et v. Le voisinage N (u) d’un nœud u correspond quant à lui à l’ensemble des nœuds adjacents à u : N (u) = {v ∈ V tel que (u, v) ∈ E}

Graphes de similarité

 La plupart des méthodes de segmentation d’images à base de graphes utilisent des graphes de similarité. Leur rôle est de permettre la représentation de relations entre les composantes de l’image possédant des caractéristiques semblables, la fonction de pondération servant alors à moduler ces relations en représentant un « degré de similarité ». Ces composantes peuvent être de différents types. Comme évoqué précédemment, avec une approche bas niveau, chaque nœud représente un pixel de l’image. Nous verrons plus loin qu’il est également possible de considérer des éléments de plus haut niveau, tels que des régions de l’image, permettant ainsi de diminuer la taille du graphe et d’accélérer son traitement. Le point commun entre les différents types de composantes est qu’il leur est associé un ou plusieurs attributs les caractérisant, représentés par des fonctions de H(V ) ou Hm(V ). Ceux-ci correspondent aux données à traiter et peuvent, là encore, être de types très différents : coordonnées [Bougleux et al., 2007], intensité du niveau de gris [Felzenszwalb et Huttenlocher, 2004,Grady, 2006], caractéristiques colorimétriques [Shi et Malik, 2000, Lezoray et al., 2007], caractéristiques de textures [Shi et Malik, 2000], patchs d’images [Lezoray et al., 2008]. . . Nous reviendrons dans un prochain chapitre sur les principales méthodes de caractérisation de textures. La construction d’un graphe de similarité peut être découpée en trois étapes, que nous allons détailler dans les sections suivantes : – la sélection de l’ensemble des nœuds, – la sélection de l’ensemble des arêtes, – la sélection de la mesure de similarité. 

Sélection de l’ensemble des nœuds 

En ce qui concerne la sélection de l’ensemble des nœuds, l’approche la plus naturelle consiste à représenter chaque donnée par un nœud du graphe [Chan et al., 2001,Bougleux, 2007,Lezoray et al., 2008]. L’intérêt est ici d’avoir une représentation la plus fine possible des interactions entre les données. Malheureusement, le nombre d’arêtes potentielles augmentant de façon quadratique avec le nombre de nœuds, ce niveau de détails peut avoir un coût non négligeable. Cela est particulièrement vrai dans le cadre du traitement d’images où les données manipulées sont les pixels, dont le nombre peut être relativement important. Nous verrons dans la section suivante les solutions qui permettent de conserver les problèmes de segmentation solvables tout en maintenant un maximum d’informations utiles. L’alternative consiste à réduire le nombre de nœuds en employant une approche de type « superpixel ». Cela revient à appliquer un algorithme de clustering comme prétraitement de l’image dans le but de produire une sur-segmentation de celle-ci. La partition ainsi obtenue est constituée de régions (ou superpixels) présentant une très faible variabilité intrarégion. Le but de cette étape de clustering n’étant pas d’anticiper sur la segmentation finale 2 , cette propriété est extrêmement importante. En effet, c’est elle qui permet de regrouper des pixels dont la dissociation – du fait de leur très forte ressemblance – n’aurait fourni aucune information supplémentaire à l’algorithme de segmentation qui sera par la suite appliqué. Cette approche a notamment été utilisée dans [Ta, 2009], où l’auteur utilise l’algorithme de partitions d’énergie [Arbeláez et Cohen, 2004] pour effectuer une sur-segmentation des images et créer ses graphes, réduisant ainsi le nombre de nœuds à moins de 3 % du nombre initial de pixels. Le lecteur intéressé pourra se référer à [Achanta et al., 2012] pour un état de l’art des méthodes de « superpixellisation ».

Sélection de l’ensemble des arêtes 

Choisir l’ensemble des arêtes consiste à définir la topologie du graphe, en particulier par la spécification du voisinage de chaque nœud. Avant d’entrer dans le détail des méthodes existantes, il faut garder à l’esprit qu’il est difficile de prédire quelle topologie de graphe permettra d’obtenir les meilleurs résultats. Le choix des heuristiques sous-jacentes est dépendant de l’algorithme utilisé et des données à traiter [Maier et al., 2008]. Les méthodes de construction que nous allons décrire se basent généralement sur une mesure de distance permettant d’évaluer la proximité de deux nœuds. Cette proximité n’est cependant pas nécessairement géométrique ; elle peut tout à fait se baser sur une notion de similarité des caractéristiques associées aux nœuds, ou encore combiner distance géométrique et caractéristique. De nouveau, il n’existe pas de règle permettant de définir la mesure la plus adaptée ; ce choix devra être fait en fonction de l’objectif recherché et des données à traiter.

Sélection de la mesure de similarité

 La similarité de deux nœuds est généralement inversement proportionnelle à la distance les séparant. À ce titre, il est tout à fait envisageable de pondérer la relation entre deux nœuds u et v à l’aide de la mesure de distance définie précédemment, en fixant par exemple wuv = (µ(u, v) + ε) −1 , avec ε un réel positif proche de zéro permettant d’éviter toute instabilité numérique. Cependant, en particulier pour les domaines organisés tels que les images, une approche différente est généralement employée : la topologie du graphe est construite à l’aide d’heuristiques purement géométriques – permettant ainsi de limiter l’étendue des voisinages – tandis que la mesure de similarité est calculée à partir des données. Une mesure de distance, telle que celles présentées précédemment, est alors pondérée à l’aide d’une fonction de transfert décroissante, comme une fonction inverse : wuv = (σ · µ(u, v) 2 + ε) −1 .