Segmentation d’images texturées par régularisation de graphes

Segmentation d’images texturées par régularisation de graphes

État de l’art des méthodes de caractérisation de textures 

La majorité des algorithmes de segmentation d’images travaille à partir de statistiques de premier ordre concernant la distribution des niveaux de gris : seule l’information relative à la probabilité d’obtenir un pixel d’un niveau de gris donné à un emplacement prédéfini est prise en compte. Cependant, comme cela est décrit dans les travaux de Julesz sur le système psychovisuel humain [Julesz, 1962], et tel que l’illustre trivialement la figure 2.1, deux images de 47 Segmentation d’images texturées par régularisation de graphes  textures « visuellement différentes 1 » peuvent présenter des statistiques de premier ordre identiques. Celles-ci ne sont donc pas suffisamment discriminantes, et limitent la capacité des algorithmes qui en dépendent à traiter des problèmes de vision complexes. Figure 2.1 – Exemples de textures visuellement différentes mais dont les statistiques de premier ordre concernant les niveaux de gris sont identiques. Dans chacune des deux régions, le niveau de gris moyen vaut 192. La notion de texture – bien qu’évidente pour notre cerveau – est relativement complexe à définir. Par ailleurs, comme l’illustre l’ensemble des définitions compilées dans [Tuceryan et Jain, 1990], celle-ci dépend souvent de l’objectif recherché par l’analyse d’une texture. En ce qui nous concerne, le point important est qu’au-delà de l’information relative à l’intensité des pixels, l’organisation spatiale de ces derniers joue un rôle extrêmement important. Ainsi, appliquée aux textures de la figure 2.1, une telle considération permet de mettre en évidence des continuités et discontinuités selon les angles de +45 et -45 degrés. La notion de motifs permet d’offrir une description de plus haut niveau d’une texture, quantifiant ainsi son orientation, sa finesse ou encore sa périodicité. Ces concepts peuvent notamment être définis à l’aide de statistiques de second ordre, c’est à dire d’informations concernant la probabilité de trouver deux pixels de niveaux de gris donnés séparés par une distance et une orientation prédéfinies. Julesz souligne notamment que deux textures ayant des statistiques de second ordre identiques sont visuellement indiscernables. Le rôle précis des différentes méthodes de caractérisation de textures est de fournir une description tonale et spatiale de la répartition des niveaux de gris dans une image. Dans la suite de cette section, nous allons présenter les principales méthodes de caractérisation de textures. 

Caractéristiques d’Haralick 

Haralick considère que la texture d’une image peut être décrite par le nombre et le type de ses primitives tonales ainsi que par leur organisation spatiale [Haralick et al., 1973,Haralick, 1979]. Il propose donc de caractériser une texture à partir d’un ensemble de statistiques de second ordre qui permettent la mise en évidence des motifs dans la distribution et l’agencement des niveaux de gris qui la composent. 1. Julesz ne s’intéresse dans ses travaux qu’à la capacité du cerveau à discriminer sans efforts deux textures distinctes, c’est à dire sans procéder à un examen détaillé de celles-ci. Il s’appuie pour cela sur la notion de matrice de co-occurrences des niveaux de gris 2 . Le but d’une matrice de co-occurrence est de dénombrer les occurrences de paires d’évènements. Dans le cadre de l’analyse de textures, Haralick considère cette paire d’évènements comme étant une transition de niveaux de gris, c’est à dire l’apparition de deux pixels d’intensités données séparés par une relation de voisinage ∆ = (δx, δy) 3 . Une telle matrice recense alors les différentes transitions de niveaux de gris dans l’image. Elle est le plus souvent utilisée sous sa forme normalisée, et représente alors une distribution de probabilités. Soit I une image composée de N niveaux de gris. Étant donnée une relation de voisinage ∆, la matrice de co-occurrence associée à cette image est définie pour chaque paire de niveaux de gris i et j par : C∆(i, j) = Card {(p, q) ∈ I tel que q = p + ∆ et I(p) = i et I(q) = j} , (2.1) ou p et q représentent les coordonnées des pixels, et I(·) l’intensité du niveau de gris aux coordonnées spécifiées. La taille d’une matrice de co-occurrence est quadratiquement proportionnelle au nombre de niveaux de gris dans l’image. Afin de permettre l’émergence de certaines tendances ou schémas dans la matrice, il est important de ne pas considérer un nombre trop important de niveaux de gris, au risque d’obtenir des valeurs statistiquement insignifiantes. Il est ainsi courant de réduire l’étendue des valeurs possibles en ré-échantillonant l’image initiale, projetant ainsi l’ensemble des niveaux de gris dans un espace de taille réduite. Il n’existe cependant aucune règle indiquant le nombre de niveaux de gris nécessaires à une description optimale d’une texture, mais des valeurs situées entre 16 et 32 sont relativement courantes. Dans ses travaux, Haralick ne tient pas compte de la direction de la relation de voisinage. Lors du calcul, il est donc nécessaire de considérer la relation de voisinage initiale ainsi que son opposée : C∆(i, j) = Card {(p, q) ∈ I tel que q = p + ∆ et(I(p) = i et I(q) = j ou I(p) = j et I(q) = i)} . (2.2) La matrice de co-occurrence ainsi générée est symétrique : C∆(i, j) = C∆(j, i). La figure 2.2 présente une image synthétique et la matrice de co-occurrences obtenue pour le décalage ∆ = (1, 0). À partir de la matrice de co-occurrences normalisée, Haralick propose un ensemble de quatorze statistiques permettant d’évaluer différentes propriétés de la texture analysée, telles que son niveau de contraste, sa régularité ou encore son degré d’entropie. Le lecteur intéressé trouvera en annexe A plus d’informations concernant le calcul de ces caractéristiques. Nous y faisons notamment le point sur les différents noms et formulations que la littérature leur associe et discutons de la validité de certaines d’entre elles. Nous en profitons aussi pour compléter les travaux d’Haralick et proposons une interprétation de chacune des caractéristiques ainsi qu’une évaluation de leur domaine de valeurs. 2. Aussi appelée matrice de dépendance spatiale des niveaux de gris, ou encore GLCM (de l’anglais Grey-Level Co-occurrence Matrix).

3. La notation ∆ sera conservée car cette notion de relation de voisinage peut être étendue à des dimensions supérieures. Figure 2.2 – Exemple de matrice de co-occurrences. (a) : une image de taille 4×4 composée de 4 niveaux de gris. (b) : la matrice de co-occurrences calculée pour le décalage ∆ = (1, 0). (c) : la même matrice représentée sous forme de carte. Étant donné que le décalage ∆ définit la direction selon laquelle une texture est étudiée, une matrice de co-occurrences est un outil fortement anisotrope qui ne caractérisera pas de la même manière deux textures de motifs identiques mais d’orientations différentes. Afin d’assurer une invariance à la rotation, Haralick suggère de caractériser une texture selon quatre orientations, 0°, 45°, 90°et 135°, puis de considérer deux vecteurs composés respectivement de la moyenne et de l’écart-type de chacune des quatorze caractéristiques. 

Modèles auto-régressifs 

Un modèle auto-régressif (AutoRegressive Model, ou AR model) est un outil statistique qui vise à exprimer un processus aléatoire discret à valeurs réelles par le biais d’une combinaison linéaire de ses propres valeurs passées : Xt = X p i=1 ϕiXt−i + ε , (2.3) avec X le processus aléatoire et ε un bruit blanc d’écart-type σε dont le but est de donner un caractère non-déterministe au modèle. On appelle « paramètres du modèle » les variables {ϕ1, . . . , ϕp} qui peuvent être considéré comme une représentation spectrale du signal, et donc une caractéristique de textures. Lorsque le modèle fait référence à p variables passées, il est dit d’ordre p. À partir d’un échantillon X = {X1, . . . , Xn}, la conception d’un modèle auto-régressif consiste à estimer les paramètres ϕi ainsi que l’écart-type σε du bruit en optimisant un critère d’attache aux données compte tenu de la présence d’un élément de caractère aléatoire. Plusieurs méthodes sont disponibles, la plupart étant basées sur des outils statistiques : l’estimation du maximum de vraisemblance [Parzen, 1968], les moindre carrés [Akaike, 1969] ou encore les équations de Yule-Walker (application du raisonnement de la méthode des moments à partir d’une estimation des auto-covariances des éléments de l’échantillon) [Chan et Langford, 1982]. D’autres approches, notamment optimisées pour les données 2D, ont plus récemment vu le jour, telles que l’algorithme rapide 2D des moindre carrés récursif en treillis [Alata et Olivier, 2003]. Initialement appliqués à la modélisation et à la prédiction de signaux 1D tels que les séries temporelles [Akaike, 1969], les modèles auto-régressifs ont ensuite été étendus aux signaux 2D pour le traitement d’images, tout d’abord en les considérant comme des signaux 1D, puis en intégrant la structure matricielle des images à la modélisation [Haralick, 1979,Maragos et al., 1984]. Les modèles auto-régressifs sont utilisés dans des applications telles que la synthèse de textures [McCormick et Jayaramamurthy, 1974], la segmentation [Deguchi et Morishita, 1978,Bouman et Liu, 1991,Ergen, 2012], ou encore la compression d’image [Maragos et al., 1984,Debure et Kubato, 1998]. Lorsqu’un tel modèle est appliqué au traitement d’images, excepté pour certains cas de synthèse de textures, la notion de « valeur passée » peut ne plus être pertinente. Le modèle peut ainsi considérer l’ensemble de pixels situés dans un voisinage donné – il est alors qualifié de modèle auto-régressif symétrique (SAR, pour Symmetric AutoRegressive). Dans cette configuration, il est alors possible de rendre le modèle invariant à la rotation : CSAR (Circular Symmetric AutoRegressive model) [Kashyap et Khotanzad, 1986], RISAR (Rotation-Invariant Symmetric AutoRegressive model) [Mao et Jain, 1992]. Enfin, des travaux ont permis d’appliquer cette approche dans un contexte de multirésolution : MR-SAR, MR-RISAR [Mao et Jain, 1992].

Caractéristiques de textures dérivées de méthodes de traitement du signal

 Ces méthodes sont basées sur un principe commun : mesurer la similarité du signal à étudier avec un second signal, connu, possédant des propriétés particulières (fréquence, forme. . . ). La mesure ainsi obtenue permet de quantifier la présence de ces propriétés dans le signal étudié. Mathématiquement, cela consiste à calculer la corrélation croisée entre ces deux signaux. Dans le cadre du traitement de signaux continus à une dimension, si f(·) désigne la fonction à étudier, et g(·) la fonction à laquelle f est comparée, la corrélation croisée (f ? g) entre f et g est obtenue par convolution de f avec le conjugué complexe g¯ de g : (f ? g) = Z ∞ −∞ f(τ ) · g¯(τ ) dτ (2.4) Cette formule est transposable aux signaux discrets, définis sur un support compact, ou encore à plusieurs dimensions. En particulier, lorsque appliquée au traitement d’images 2D, la formule associée à ce calcul de corrélation croisée est : (f ? g) = 1 NM N X−1 x=0 M X−1 y=0 f(x, y) · g¯(x, y) , (2.5) une image de résolution M × N étant ici considérée.