Segmentation d'une image en matériaux

La segmentation d'une image en matériaux consiste à créer une partition de l'image en régions telle que chaque région soit composée d'un seul matériau. La segmentation d'une image est usuellement définie comme la partition de celle-ci en régions chaque région codant un objet de la scène. Une définition formelle d'un algorithme de segmentation a été donné par Horowitz et Pavlidis [HP76,HP75] en 1975.

Le prédicat $P$ est utilisé pour tester l'homogénéité des ensembles $R_i$. Ces sous-ensembles constituent les régions de l'image. Une segmentation de l'image est donc sa décomposition en un ensemble de régions homogènes, le critère d'homogénéité $P$ restant à déterminer. Zucker [Zuc76] a résumé les conditions de la définition 8 comme suit : la première condition implique que tout pixel de l'image appartienne à une région et une seule. Cela signifie que l'algorithme de segmentation ne doit pas se terminer avant d'avoir traité tous les points. La seconde condition implique que toute région doit être connexe. La connexité des régions étant induite par le voisinage défini sur l'image. La troisième condition implique que chaque région doit être homogène. Enfin, la quatrième condition est une condition de maximalité indiquant que la fusion de deux régions ne doit pas être homogène. Il est important de remarquer que le nombre $n$ de régions formant la partition de l'image reste indéterminé. Il peut donc exister plusieurs segmentations possibles pour un prédicat $P$ donné.

Intuitivement un ``bon'' prédicat $P$ doit nous fournir une région pour chaque objet de l'image. Toutefois, la notion d'objet est généralement assez vague si bien que la problématique de la segmentation est par essence mal définie. La segmentation en matériaux au moins prise comme pré-traitement peut permettre une meilleure définition du problème. La restriction de la problématique de la segmentation à une segmentation en matériaux possède en effet deux avantages fondamentaux :

1. Tout d'abord le but a atteindre par l'algorithme peut être décrit précisément.

2. De plus, notre décomposition de l'image en matériaux peut s'appuyer sur les modèles physiques vus dans la Section 2.2 pour interpréter les valeurs des pixels.

Ce dernier avantage a de nombreuses conséquences pratiques. En effet le prédicat $P$ utilisé en segmentation est souvent défini à l'aide des distances entre les couleurs de pixels. On peut par exemple imposer qu'une région soit homogène si la couleur de chacun de ses pixels est à une certaine distance de la couleur moyenne de la région. On peut également imposer que la distance entre deux pixels adjacents de la région ne dépasse pas un certain seuil. Toutefois, nous avons vu dans la section 2.2 que deux pixels adjacents correspondant au même matériau et au même objet peuvent avoir des intensités très différentes (voir par exemple le profil d'intensité sur la Figure 2.10). Ces limitations du processus de segmentation sont essentiellement dues à l'absence d'un modèle nous permettant d'interpréter la distance entre deux pixels adjacents. La segmentation en matériaux permet de ce baser sur des modèles physiques permettant d'interpréter les valeurs des pixels et leur différences. Ce processus ne fournit pas une segmentation en objets mais peut être utilisée comme première étape d'un processus de segmentation plus complet fournissant un ensemble de régions pas simplement homogènes mais composées d'un unique matériau que l'on peu éventuellement identifier. Les processus de plus haut niveau sont dans ce cas grandement simplifiés.

La majorité des algorithmes de segmentation en matériaux sont basés sur les modèles de Shafer [Sha85] ou Healey [Hea89] (Section 2.2.5). Nous allons dans cette Section établir les fondements de ces méthodes.

Le modèle de Shafer [Sha85](Section 2.2.5) exprime l'irradiance sur un capteur de la caméra par la somme d'une composante Lambertienne et d'une composante Spéculaire :

$$L(\lambda,\theta_i,\theta_r,g)=m_{diff}(\theta_i,\theta_r,g)c_{diff}(\lambda)+ m_{spec}(\theta_i,\theta_r,g)c_{spec}(\lambda)$$

Si nous considérons que les angles $\theta_i,\theta_r$ et $g$ sont fonctions de la position $(x,y)$ du pixel cette équation se réécrit :

$$L(\lambda,x,y)=m_{diff}(x,y)c_{diff}(\lambda)+ m_{spec}(x,y)c_{spec}(\lambda)$$ (6.5)

Notez que dans un tel modèle les valeurs respectives de $m_{diff}$ et $C_{diff}$ ainsi que celles de $m_{spec}$ et $C_{spec}$ ne peuvent être déterminées qu'à un facteur multiplicatif prés. Shafer pose donc, sans perte de généralité : $0\leq m_{diff}(x,y)\leq 1$ et $0\leq m_{spec}(x,y)\leq 1$.

Étant donné une caméra couleur, la couleur d'un pixel $I(x,y)$ se déduit de l'irradiance sur ses capteurs par :

$$\forall i \in \{1,2,3\} \quad C_i(x,y)=\int_{\lambda_1}^{\lambda_2}L(\lambda,x,y)c_i(\lambda)d\lambda$$

où $C_i(x,y)$ représente la $i^{\mbox{{\\lq e}me}}$ composante de $I(x,y)$ et $(c_i(\lambda))_{i\in\{1,2,3\}}$ représentent la sensibilité de la caméra aux $3$ composantes (usuellement le rouge, le vert et le bleu ). Les deux longueurs d'ondes $\lambda_1$ et $\lambda_2$ représentent les deux bornes de sensibilités de la caméra ( $\lambda_1\approx 450nm$ et $\lambda_2\approx 700nm$).

Si nous reprenons l'équation 6.5 nous obtenons :

$$\forall i \in \{1,2,3\} \quad C_i(x,y)=m_{diff}(x,y)\int_{\lambda... ..._{spec}(x,y)\int_{\lambda_1}^{\lambda_2}c_{spec}(\lambda)c_i(\lambda)d\lambda+$$

Donc :

$$I(x,y)=m_{diff}(x,y)C_{diff}+m_{spec}(x,y)C_{spec}$$ (6.6)

avec

$$\forall i\in \{1,2,3\} \quad \left(C_{diff}\right)_i=\int_{\lambda_1}^{\lambda_2}c_{diff}(\lambda)c_i(\lambda)d\lambda$$ et $$\left(C_{spec}\right)_i=\int_{\lambda_1}^{\lambda_2}c_{spec}(\lambda)c_i(\lambda)d\lambda$$

L'équation 6.6 nous montre donc que pour un matériau l'information couleur a priori tridimensionnelle est en fait bidimensionnelle puisque l'ensemble des couleurs d'un matériau est contenu dans le plan défini par $C_{diff}$, $C_{spec}$. Plus précisément, puisque nous supposons $m_{diff}$ et $m_{spec}$ bornés entre 0 et $1$, l'ensemble des couleurs d'un matériau est contenu dans le parallélogramme défini par les vecteurs $C_{diff}$ et $C_{spec}$ (Figure 6.1). Notons que dans le cas d'un seul illuminant un des coins du parallélogramme doit être l'origine de l'espace (cas où $m_{diff}=m_{spec}=0$).

Le modèle de Healey est basé sur une décomposition supplémentaire en métaux et diélectriques. On obtient en en effet à partir de l'équation 2.20 :

$$I(x,y)=\left\{ \begin{array}{ll} M_{spec}(x,y)C_{spec}&\mbox{ Pou... ...diff}&\mbox{ Pour les di{\'e}lectriques inhomog{\\lq e}nes}\\ \end{array}\right.$$

Donc l'ensemble des couleurs d'un métal peut être décrit par une droite. Alors qu'a priori l'ensemble des couleurs d'un diélectriques inhomogène peut être d'écrit par un parallélogramme.

Klinker [HSW92a] a affiné cette description en remarquant que dans le cas d'un diélectrique non homogène les points tels que le vecteur $C_{spec}$ n'est pas négligeable correspondent à des zones de l'image fortement illuminées. De tels points correspondent à des zones très localisées dans l'image pour lesquelles on peut négliger les variations de la composante diffuse. Si nous nous référons au modèle de Nayar (Section 2.2.4). Un telle approximation, revient à négliger les variations de la composante Lambertienne lorsque le lobe spéculaire ou le pic spéculaire n'est pas négligeable.

La répartition des couleurs dans le parallélogramme de Shafer n'est donc pas uniforme mais suit une distribution similaire à celle représentée sur la Figure 6.2. L'ensemble des couleurs d'un diélectrique non homogène dans des régions non hautement éclairées peut donc être décrit uniquement par le vecteur $C_{diff}$. Dans le cas d'une zone de l'image hautement illuminée la composante de ce vecteur sur $C_{diff}$ reste constante (valeur $m_{ds}$ sur la Figure 6.2) alors que les variations se produisent sur le vecteur $C_{spec}$. L'histogramme des couleurs d'un matériau a donc la forme d'un $T$ renversé et légèrement distordu. On peut également obtenir un histogramme en $L$ si $m_{ds}$ est égal à la valeur maximum $m_{dmax}$ sur l'axe $C_{diff}$. Une étude de l'illumination d'un cylindre à amené Klinker [HSW92a] à conclure que le seuil $m_{ds}$ ne pouvait se trouver que dans la seconde moitié de l'intervalle des variations $[0,m_{dmax}]$. Cette hypothèse confirmée par des expériences sur des images réelles est appelée l'hypothèse des 50% supérieurs. Nous appellerons respectivement les lignes définies par $C_{diff}$ et $m_{ds}C_{diff}+C_{spec}$ la ligne diffuse et la ligne spéculaire.

Cette modélisation de l'ensemble des couleurs d'un matériau nous permet d'interpréter l'ensemble des couleurs du voisinage d'un point. En effet, étant donné un pixel de l'image et un fenêtre centrée sur celui-ci, l'ensemble des couleurs des pixels contenus dans cette fenêtre peut avoir une dimension 0, $1$, $2$ ou $3$. La dimension de cet ensemble de couleurs peut être testée en utilisant les valeurs propres de la matrice de covariance de l'ensemble de couleurs (Section 5.2.1, équation 3).

• Dans le cas d'une fenêtre de dimension 0, le point considéré ne peut se trouver que sur un matériau avec une faible courbure ou sur une zone mal éclairée de ce même matériau.

• Dans le cas ou la fenêtre a pour dimension $1$, la couleur du pixel se trouve sur la ligne diffuse ou sur la ligne spéculaire d'un matériau. La fenêtre peut également intersecter deux matériaux de telle façon que les couleurs de l'un deux sont situées sur la ligne diffuse alors que celles de l'autre corresponde à un seul point de la ligne diffuse. Le fenêtre intersecte alors une zone plate ou peu éclairée du second matériau.

• Si la fenêtre à pour dimension $2$ la fenêtre est soit incluse dans un seul matériau avec les lignes diffuse et spéculaire soit intersecte deux matériaux de telle façon qu'une seule des deux droites de chaque matériau est comprise dans la fenêtre.

• Dans le cas de fenêtre de dimension $3$, le pixel peut se trouver
  • soit dans un seul matériau. La troisième dimension est dans cas créée par le bruit d'acquisition.

  • soit à l'intersection de deux matériaux avec les deux droites diffuses et spéculaires pour l'un et une seule de ces droites pour l'autre.

  • Enfin la fenêtre peut également avoir intersecté une frontière entre au moins $3$ matériaux.

Le cas ou le pixel est dans une fenêtre de dimension $3$ est évidemment celui pour lequel on a le moins d'information. Il est toutefois remarquable de pouvoir faire de telles hypothèses à partir d'une fenêtre centrée sur un pixel.

Klinker [HSW92a] utilise cette classification pour décomposer l'image en matériaux. Schématiquement, sa méthode de segmentation se déroule de la façon suivante.

1. Décomposer l'image en fenêtre et étiqueter chaque fenêtre en fonction de sa dimension.

2. Fusionner les fenêtres adjacentes de même dimensions si l'ensemble obtenu a la même dimension.

3. Raffiner la segmentation de toutes les régions de dimension $1$ par une croissance de région lancée au centre de la région. L'ensemble des couleurs de chaque région de dimension $1$ correspond alors à une ligne diffuse ou à une ligne spéculaire.

4. Fusionner des régions de dimension $1$ entre elles si l'ensemble des couleurs obtenues à une configuration en $T$ ou en $L$. Ces fusions sont contraintes par l'hypothèse des 50% supérieurs. Les régions obtenues ont pour dimension $2$.

5. Lancer un algorithme de croissance de région dans chaque région générée à l'étape précédente. Cet algorithme agrège à la région les pixels des régions de dimension $2$ compatibles avec la configuration des couleurs de la région initiale.

Notons que les pixels de dimensions 0 et $3$ ne sont pas directement utilisés par l'algorithme. En effet l'information liée à ces pixels est difficilement exploitable et ces pixels sont absorbés par les étapes de croissance de région dans des régions de dimension $1$ ou $2$.

La méthode présenté par Klinker utilise une approche ascendante. Healey [Hea95] a présenté une méthode comparable basée sur une approche descendante.

La méthode d'Healey néglige initialement la composante spéculaire des diélectriques inhomogènes. On a donc pour les métaux comme pour les diélectriques une équation de la forme :

$$L(\lambda,x,y)=M(x,y)c(\lambda)$$

où $M$ représente $M_{spec}$ pour les métaux et $M_{diff}$ pour les diélectriques (équation 2.20). De même $c$ représente $C_{spec}$ pour les métaux et $C_{diff}$ pour les diélectriques.

Donné les fonctions de sensibilité $(c_i)_{i\in \{1,2,3\}}$ de la caméra, la couleur $(C_i)_{i\in\{1,2,3\} }$ d'un pixel est donnée par :

$$\forall i \in \{1,2,3\} \quad C_i=\int_{\lambda_1}^{\lambda_2}M(x,y)c(\lambda)c_i(\lambda)d\lambda =M(x,y)K_i$$ avec $$K_i=\int_{\lambda_1}^{\lambda_2}c(\lambda)c_i(\lambda)d\lambda$$

Si nous notons par $K$ le vecteur $(K_1,K_2,K_3)$, la couleur I(x,y) d'un pixel est donc égale à :

$$I(x,y)=M(x,y)K$$

L'ensemble des couleurs d'un matériau appartient donc à une droite de vecteur directeur $K$.

Si nous normalisons les coordonnées de chaque pixel par sa norme dans $L_2$ nous obtenons :

$$\forall i \in \{1,2,3\} \quad \frac{C_i}{\Vert I(x,y)\Vert}= \fra... ...)K_i}{\sqrt{M(x,y)^2\left(K_1^2+K_2^2+K_3^2\right)}}= \frac{K_i}{\Vert K\Vert}$$

Les coordonnées normalisées d'un pixel sont donc indépendantes de la géométrie. Notons qu'un résultat similaire aurait été obtenu en utilisant la norme $L_1$ plutôt que la norme $L_2$. Toutefois, la norme $L_2$ permet de définir une distance entre les droites qui ne dépend que de l'angle formé par celles-ci. Inversement la norme $L_1$ conduit à la définition d'une distance dépendant simultanément de l'angle entre les deux droites et de l'angle que forme une de ces deux droites avec un des axes de coordonnée. La norme $L_2$ est donc utilisée préférentiellement à la norme $L_1$.

La segmentation d'une image se ramène donc à une reconnaissance de droites dans l'espace couleur ou à la reconnaissance d'un ensemble de distributions normales dans l'espace normalisé par $L_2$. C'est cette dernière option que choisi Healey. Un matériau $m_i$ est caractérisé par sa moyenne $\mu_i$ et sa matrice de covariance $\Sigma_i$ (Section 5.2.1, équation 3). La distribution des couleurs dans le matériau est alors modélisée par la distribution normale $N(\mu_i,\Sigma_i)$ définie par

$$p(C/m_i)=\frac{1}{2\pi\sqrt{2\pi}\sqrt{\vert\Sigma_i\vert}}e^{-\frac{1}{2}(C-\mu_i)^t\Sigma_i^{-1}(C-\mu_i)}$$

La normalisation et effectué en considérant plutôt la distribution $N(\hat{\mu_i},\widehat{\Sigma_i})$ avec :

$$\hat{\mu_i}=\frac{\mu_i}{\Vert\mu_i\Vert}$$ et $$\widehat{\Sigma_i}=\frac{\Sigma_i}{\Vert\mu_i\Vert^2}$$

Donné la modélisation de chaque matériau, la classification d'une couleur $C$ a un matériau parmi $M$ s'effectue en utilisant les fonctions suivantes basées sur la théorie de la décision de Bayes [DH73] :

$$g_i(\widehat{C})=\log(p(\widehat{C}/m_i))+\log(p_i)$$

où $\widehat{C}=\frac{C}{\Vert C\Vert}$ et $p_i$ représente la probabilité qu'une couleur prise au hasard appartienne à $m_i$.

Si nous supposons que tous les matériaux sont équitablement représentés $p_i$ devient indépendant de $i$ et l'équation précédente peut se simplifier en :

$$g_i(\widehat{C})=-\frac{1}{2}(\widehat{C}-\hat{\mu_i})^t\widehat{... ...}^{-1}(\widehat{C}-\hat{\mu_i})-\frac{1}{2}\log(\vert\widehat{\Sigma_i}\vert ).$$ (6.7)

La couleur $C$ est alors affectée au matériau $i$ pour lequel $g_i(\widehat{C})$ est maximum.

Donné cette méthode de classification, Healey commence par appliquer un opérateur gradient sur l'image. L'idée sous-jacente est de caractériser les zones correspondant à seul matériau comme des zones de faible gradient. Notons toutefois que cette supposition est discutable. En effet, l'opérateur gradient va non seulement réagir à des changements de matériaux mais également à de brusque changement de géométrie sur un objet composé d'un seul matériau.

Donné l'image de gradient Healey décompose l'image à l'aide d'un quadtree [CP95] et initialise une liste vide de matériaux. Tout noeud du quadtree couvrant une zone de l'image de faible gradient est supposé composé d'un seul matériau. Healey calcule donc sa couleur moyenne normalisée :

$$\hat{\mu}=\frac{\mu}{\Vert\vert\mu\Vert}$$ avec $$\mu=\sum_{(x,y)\in R}I(x,y)$$

où $R$ représente la région couverte par le noeud du quadtree.

La moyenne $\hat{\mu}$ est alors comparée aux $M$ matériaux présents dans la liste à l'aide de l'équation 6.7. Si la valeur maximum de $g_i(\hat{\mu})$ est supérieure à un seuil $T$ la région est affectée à un des matériaux de la liste. Sinon Healey considère que la région est composée d'un nouveau matériau et celui-ci est ajouté à la liste en utilisant les données de la région $R$.

La méthode de Healey segmente donc l'image en un ensemble de régions, tel que l'ensemble des couleurs de chaque région décrit une droite dans l'espace de couleurs. Il convient ensuite de fusionner les régions adjacentes composée d'un seul matériau telle que l'une des régions correspond à la droite diffuse tandis que l'autre correspond à la droite spéculaire. Schématiquement, une fusion est réalisée entre deux régions si :

1. Les couleurs des pixels de la région supposée correspondre à la ligne spéculaire ont des composantes supérieures ou égales à celle de la région correspondant à la ligne diffuse.

2. Les droites des deux régions se coupent en un point vérifiant l'hypothèse des $50\%$ supérieurs.

La méthode de Healey repose donc sur une découpe récursive de l'image afin d'obtenir des patchs de surface composés d'un seul matériau. Malgré l'approche différente de celle de Klinker, ces deux méthodes sont basés sur les mêmes idées de base :

1. Exprimer la réflectance d'un matériau comme un produit d'un terme dépendant de la géométrie et d'un terme dépendant des longueurs d'ondes,

2. utiliser cette modélisation pour décrire la structure de l'ensemble des couleurs d'un matériau.

Donné une telle modélisation, l'algorithme de segmentation fusionne ou découpe des régions en se guidant sur les modèles décrivant les matériaux. De nombreuses adaptations de ces algorithmes ont été développées [Hea89,Bri90,HSW92b,FF95,Sha02]. Toutefois, l'idée principale de ces algorithmes repose généralement sur les deux points mentionnés précédemment.