Segmentation en régions : l'histogramme d'homogénéité

Jérôme Darbon - Pablo Musé

DEA MVA 2000-2001

1 Introduction

La segmentation a pour but de déterminer les régions cohérentes d'une image à la fois spatialement et du point de vue de leur contenu. Nous présentons la méthode de Cheng et Sun décrite dans [1] dont le but est la segmentation d'images en couleur.

Cette méthode procède en trois étapes:

1. Détermination des régions uniformes par l'identification des pics significatifs de l'histogramme d'homogénéité. Cette étape prend en compte aussi bien l'information locale que globale.
2. Analyse de l'histogramme de la caractéristique Hue (Teinte) de chaque région obtenue lors de la première étape. Chaque région est alors divisée en sous-régions. Au final, une sous-région a donc une homogénéité à peu près constante et une teinte caractéristique.
3. Fusion des sous-régions pour éviter la sur-segmentation. Le critère de fusion s'appuie sur la distance entre deux couleurs et elle est calculée dans l'espace CIE (L*a*b*).

2 Analyse d'Histogramme d'Homogénéité

2.1 L'homégénéité et l'histogramme d'homogénéité

L'homégénéité est une information locale et correspond au caractère uniforme d'une région. Elle est composée de deux informations sur l'intensité : d'une part son écart-type, d'autre part ses discontinuités (norme du gradient). En chaque point l'écart-type décrit le contraste de l'intensité dans le voisinage du point considéré, et la mesure de discontinuité indique le changement brusque de niveau de gris toujours dans un voisinage de ce point. Pour une représentation RGB, l'intensité $I$ vérifie $I = (R + G + B) / 3$.

Soit $$g_{i,j}$$ l'intensité du pixel $P_{i,j}$ situé à la position $(i,j)$ dans une image da taille $M \times N$.

L'écart-type $v_{i,j}$ du Pixel $P_{i,j}$ est calculé sur une fenêtre de taille $d \times d$ :

$$\displaystyle{ v_{i,j} = \sqrt{\frac{1}{d^2} \sum_{p = i - \... ...{2}}^{p = j + \frac{d - 1}{2}} {{(g_{p,q} - \mu_{i,j})}^2}}} }$$

où $0 \le i,p \le M -1, 0 \le i,p \le N -1$. $\mu_{i,j}$ est la moyenne des niveaux de gris calculée sur la même fenêtre:

$$\mu_{i,j} = \sum_{p = i - \frac{d - 1}{2}}^{p = i + \frac{d ... ...j - \frac{d - 1}{2}}^{p = j + \frac{d - 1}{2}} {{(g_{p,q})}}}$$

La mesure de discontinuité $e_{i,j}$ de l'intensité au pixel $P_(i,j)$ est calculée par l'opérateur de Sobel, sur une fenêtre de taille $t \times t$:

$$e_{i,j} = \sqrt{G_x^2 + G_y^2}$$

où $G_x$ et $G_y$ sont respectivement les composantes du gradient de I au point (i,j) dans les directions $x$ et $y$.

L'écart type $v_{i,j}$ et la mesure de discontinuité $e_{i,j}$ sont normalisés; on obtient alors l'écart type normalisé $V_{i,j}$ et la mesure de discontinuité normalisée $E_{i,j}$. L'homogénéité $H_{i,j}$ est représenté par

$$H_{i,j} = 1 - E_{i,j} \times V_{i,j}$$

Un choix adéquat pour la taille des fenêtres est $d = 5$ et $t = 3$.

2.2 La détection des pics

L'algorithme de détection des pics donné dans [1] est présenté dans cette section. Dans la méthode de segmentation décrite dans [1], il est appliqué à l'histogramme d'homogénéité aussi bien qu'à l'histogramme de teinte de chaque région.

Soit h un histogramme tel que $h(i) \in [0,1]$ avec $0 \le i \le 255$. L'algorithme de recherche des pics est le suivant:

• Trouver tous les pics : trouver l'ensemble $P_0$ des points qui sont des maxima locaux dans l'histogramme.
  
  $$P_0 = \left\{ (i, h(i)) \vert h(i) > h(i-1) \mbox{ et } h(i) > h(i+1), 1 \leq i \leq 254 \right\}$$
  
  

• Trouver les pics les plus significatifs : Les points dans $P_0$ forment une nouvelle courbe. L'opération de l'étape précédente est répétée sur cet ensemble. Nous obtenons donc:
  
  $$P_1 = \left\{ (p_i, h(p_i)) \vert h(p_i) > h(p_i-1) \mbox{ et } h(p_i) > h(p_i+1), p_i \in P_0 \right\}$$
  
  

• Seuillage : Cette étape se décompose en trois phases :

  -

  La première consiste à enlever les petits pics. Plus précisément, tous les pics dont la hauteur est inférieure à 5% de la hauteur du plus grand sont enlevés.

  -

  Ensuite, si deux pics sont trop près l'un de l'autre, on ne retient que le plus grand. Les auteurs considèrent que deux pics sont proches quand leur distance $(i_2 - i_1)$ est inférieure à 15 pixels.

  -

  Si une vallée entre deux pics n'est pas assez prononcée, alors le pic le moins haut est éliminé. Plus précisément, si $p_1$ et $p_2$ sont les deux pics considérés alors la valeur moyenne $h_{avg}$ entre ces deux points est :
  

  $$h_{avg} = \frac{ \sum_{p_i = p_1}^{p_i = p_2} {h(p_i)}}{ p_2 - p_1 + 1}.$$

  
  

  En introduisant la valeur $h_{mean} = \frac{h(p_2)+h(p_1)}{2}$ qui représente la "mi-hauteur" des deux pics, on décide que la vallée n'est pas assez profonde lorsque $\frac{h_{avg}}{h_{mean}} > 0.75$ ; le pic le moins haut est alors retiré.

2.3 Segmentation en régions d'homogénéité constante

Nous trouvons les modes le plus significatifs dans l'histogramme d'homogénéité en appliquant l'algorithme précédent. L'intensité correspondant aux vallées segmente l'image en des régions homogènes.

3 Segmentation Hiérarchique à partir de la Teinte

3.1 Définition de la teinte

La caractéristique Hue ($H$) peut être obtenue des composantes R, G, B par la transformation non linéaire suivante:

$$H = \arctan\left(\frac{{\sqrt{3}}(G-B)}{(R-G)+(R-B)}\right).$$

Elle correspond à la couleur prédominante d'un objet et est très adaptée à la représentation de la perception subjective des couleurs. C'est la caractéristique la plus utile pour la segmentation des couleurs car elle est peu influencée par les effets d'illumination non uniforme.

La deuxième phase de cette technique de segmentation d'images en couleur consiste alors à analyser l'histogramme de caractéristique Hue. Pour chaque région issue de l'étape 1, chaque région est divisée en sous-régions de couleurs similaires. C'est dans ce sens que la technique décrite est hiérarchique: d'abord on segmente l'image à partir de l'histogramme d'homogénéité, puis à partir des histogrammes de la caractéristique Hue (la hauteur de la hiérarchie est 2 !).

La caractéristique Hue présente un inconvénient: elle n'est pas définie pour un niveau de saturation nul, et elle a un problème d'instabilité pour les bas niveaux de saturation. Pour résoudre cet inconvénient, la méthode que nous décrivons redéfinit $H$ pour les pixels singuliers. Un tel pixel reçoit la moyenne de la teinte de ses huit voisins. Si tous ses voisins correspondent aussi à des points présentant une singularité dans la teinte, sa teinte reste indéfinie jusqu'à l'étape de fusion de régions (section 4.2). Précisons que de tels pixels sont plutôt rares.

3.2 Segmentation hiérarchique

Pour chaque région issue de la segmentation basée sur l'homogénéité, on calcule le $H$ de ses pixels, on le normalise dans l'intervalle $[0,255]$ et on construit l'histogramme la caractéristique Hue. Ensuite on lui applique l'algorithme de détection de pics décrit dans la section 2.2, et finalement on cherche les vallées entre les pics. Puis, on divise l'intervalle de la caractéristique Hue en segments déterminés par les vallées. Chaque segment de l'histogramme de la caractéristique Hue représente une sous-région caractérisée par une couleur similaire. Une fois que toutes les régions ont été caractérisées, on assigne à chaque sous-région sa couleur moyenne, en affectant à chaque pixel les composantes R, G et B correspondantes.

4 Fusion des Régions

4.1 Description CIE de la différence des couleurs

Éventuellement, les deux premières étapes peuvent donner lieu à une sur-segmentation de l'image. Ceci peut arriver lorsque des pixels qui correspondent à une même région visuelle, ont des couleurs qui ne sont pas suffisamment semblables. Une phase de fusion de régions s'avère alors nécessaire. La mesure de dissimilarité utilisée dans cette méthode est fondée sur la représentation CIE(L*a*b*). Elle est issue de la représentation $X$, $Y$, $Z$ définie par la Commission Internationale de l'Éclairage (CIE):

$$\left[\begin{array}{c} X Y Z \end{array} \right] = \lef... ...right) \left[\begin{array}{c} R G B \end{array} \right].$$

Les composantes $L*$, $a*$ et $b*$ sont obtenues de $X$, $Y$ et $Z$ par la transformation non linéaire suivante:

$$L* = 116\left(\frac{Y}{Y_0}\right)^{\frac{1}{3}}-16,$$

$$a* = 500\left[\left(\frac{X}{X_0}\right)^{\frac{1}{3}}- \left(\frac{Y}{Y_0}\right)^{\frac{1}{3}}\right],$$

$$b* = 200\left[\left(\frac{Y}{Y_0}\right)^{\frac{1}{3}}- \left(\frac{Z}{Z_0}\right)^{\frac{1}{3}}\right],$$

où $(X_0,Y_0,Z_0)$ sont les valeurs du blanc standard.

L'espace CIE(L*a*b*) est bien adapté du point de vue perceptif pour mesurer la différence entre les couleurs (ce qui n'est pas vrai pour la représentation RGB). La différence entre deux couleurs de coordonnées $(L_1,a_1,b_1)$ et $(L_2,a_2,b_2)$ dans la base CIE(L*a*b*) est:

$$\Delta E = {\left[(L_1-L_2)^2+(a_1-a_2)^2+(b_1-b_2)^2\right]}^{\frac{1}{2}}.$$ (1)

La possibilité d'exprimer les différences de couleur pour la perception humaine par une distance euclidienne est une propriété remarquable.

4.2 Le critère de fusion

Si le nombre de régions obtenues par les étapes précédentes est $k$, alors il y a $k$ couleurs dans l'image pré-segmentée. La différence de couleur pour chaque paire de région est calculée par (1). L'écart-type $\sigma$ de la liste des différences de couleur s'exprime ainsi:

$$\sigma = \sqrt{ \frac{1}{n} \sum_{i=1}^{n}{\left( D_i - \mu \right)^2}}$$

où $\mu$ est la moyenne des différences de couleur, $D_i$ est la la $i^{e}$ différence de couleur, et $n = \frac{k(k-1)}{2}$ est le nombre total de différences. On fixe le seuil pour la fusion des régions à $T = \mu - \sigma$. Le processus de fusion est itératif :

1. Les deux régions qui ont la plus petite différence de couleur sont fusionnées si cette différence est inférieure à $T$.
2. On recalcule $\mu$, $\sigma$ et $T$.
3. Si la plus petite différence est inférieure à $T$, alors on retourne en $1$; sinon on sort de la boucle.

5 Résultats

Les expériences ont été menées sur lena, un tableau de Kandinsky (comp10), house, airplane , un tableau de Cézanne (lauves), et pills.

Les résultats sont présentés de la façon suivante:

1. L'image originale.
2. L'image d'intensité.
3. L'image de l'écart-type.
4. L'image de discontinuité.
5. L'image d'homogénéité.
6. L'histogramme dans le domaine de l'homogénéité. La légende de cette image indique les indices des pics par "()", et les creux des vallées sans "()". Par exemple, pour un histogramme qui présente deux pics en 100 et 150, et donc trois vallées. Et si le minimum de chaque vallée est 0, 120 et 255, alors nous notons cette configuration : "0 (100) 120 (150) 255".
7. L'image divisée en régions uniformes selon l'histogramme d'homogénéité.
8. L'image de la caractéristique Hue.
9. Les histogrammes de la caractéristique Hue pour chaque région homogène.
10. L'image segmentée.

Nous remarquons que les images segmentées sont de bonne qualité. Le nombre de couleurs dans ces images est faible et permet cependant de garder les structures principales. Mais cette méthode ne parvient pas à segmenter les petites structures qui peuvent être importante. Par exemple, dans l'image house, le blanc de la maison est fusionné avec le ciel.

L'algorithme est fragile à la détection des pics des histogrammes. Par exemple, nous observons que pour l'image lena, l'algorithme de détection de pics élimine un pic important (indice 106). Il considère que la vallée n'est pas assez creusée. Nous proposons alors une modification de cette méthode. Elle consiste à modifier le calcul de $h_{avg}$ dans la troisième étape de l'algorithme de détection des pics. Au lieu de calculer $h_{avg}$par

$$h_{avg} = \frac{ \sum_{p_i = p_1}^{p_i = p_2} {h(p_i)}}{ p_2 - p_1 + 1}$$

nous remplaçons cette formule par :

$$h_{avg} = \frac{ \sum_{p_i = \frac{p_2-p1}{4}}^{p_i = \frac{3(p_2-p1)}{4}} {h(p_i)}}{ p_2 - p_1 + 1}$$

C'est-à-dire que nous redéfinissons l'intervalle sur lequel nous calculons la moyenne. Au lieu de la calculer sur tout l'intervalle compris entre deux pics, nous ne la calculons que sur le deuxième et troisième quart de celui-ci.

Le résultat de la segmentation avec cette modification est présenté pour lena et pour pills. Nous remarquons qu'avec cette modification, l'algorithme récupère la région bleue de l'image lena originale. Pour l'image pills, l'algorithme modifié permet de récupérer deux couleurs supplémentaires: l'unique rouge récupéré par la méthode originale se décompose en trois qualités de rouge qui correspondent à des types de pilules différentes.

6 Conclusion

La méthode de segmentation d'images en couleur décrite dans [1] est une méthode simple qui permet d'obtenir de bons résultats. Cependant, l'algorithme d'extraction des pics les plus significatifs dans un histogramme est souvent trop sévère. Ceci a pour conséquence que certaines images sont sous-segmentées. Cet aspect nous a amené à modifier légèrement cet algorithme afin de capturer certains pics importants ; et donc d'obtenir une segmentation plus fine.

7 Programme

Le programme est disponible ici.

Bibliographie

1

H. Cheng - Y. Sun.
A hierarchical approach to color image segmentation using homogeneity.
IEEE Transactions on Image Processing, 9(12):2071-2082, 2000.