Segmentation d’images (2/2)

Dans le cours précédent, nous avons tenté de résoudre le problème de la segmentation en utilisant une technique de regroupement des couleurs en \(k\) classes à l’aide de l’algorithme des \(k\) moyennes, et avons exploré une méthode de détection des contours basée sur le filtre de Canny. Nous poursuivons dans ce cours en cherchant à relier et unifier ces deux principes.

Segmentation par la méthode des k-moyennes

Détection des contours par filtre de Canny (TP5)

Modélisation probabiliste

Rappel : le problème de la segmentation consiste à trouver une partition du support de l’image \[ \Omega = \bigcup_{i=1\ldots k} \mathcal S_i, \qquad \mathcal{S}_i \cap \mathcal{S}_j = \emptyset \text{ pour }i\neq j \] où \(k\) est le nombre de classes dans l’image.

De façon équivalente, on cherche un étiquetage \(u: \Omega \rightarrow \{1 \ldots k \}\) qui attribue une étiquette (ou label en anglais) à chaque pixel du support de l’image, correspondant aux objets présents dans l’image \(f\).

Maximum a posteriori

Dans un cadre probabiliste, on cherche à modéliser la probabilité d’un étiquetage \(u\) pour une image \(f\) (une observation) donnée. On note \(P(u|f)\) cette probabilité, l’objectif est de trouver l’étiquetage qui maximimse cette probabilité \[ \hat{u}_\mathrm{map} = \arg\max_u P(u|f). \] On appelle \(\hat{u}_\mathrm{map}\) l’estimateur du maximum a posteriori.

Cadre bayésien et modélisation de l’image

En général, il est difficile de modéliser \(P(u|f)\) directement, on utilise pour cela le théorème de Bayes : \[ P(u|f) = \frac{P(f|u) P(u)}{P(f)}. \] Pour une observation \(f\) donnée, maximiser \(P(u|f)\) revient donc à maximiser \(P(f|u) P(u)\), ou de façon équivalente en passant au \(\log\) à minimiser \[ V(u|f) = -\log P(f|u) - \log P(u). \]

Dans la dernière équation, on peut voir le premier terme comme une mesure de la fidélité aux données, alors que le second terme représente un a priori sur la solution que l’on cherche, par exemple sur sa régularité. On va voir en détails ces deux parties du modèle.

Adéquation de l’image à la segmentation (1/3)

On peut supposer que conditionnellement à l’étiquetage \(u\), les observations d’un pixel à l’autre sont indépendantes : \[ P(f|u) = \prod_{p\in\Omega}P(f[p]|u). \] Par ailleurs, l’observation (la valeur de l’intensité au pixel \(p\)) ne dépend que de la classe de ce pixel : \[ P(f[p]|u) = P(f[p] | u[p]), \] il reste à modéliser cette probabilité.

Adéquation de l’image à la segmentation (2/3)

De façon simple, on peut supposer que la distribution des intensités (ou des couleurs) à l’intérieur de chaque classe \(i\) suit une loi gaussienne de moyenne \(\mu_i\) et de variance \(\sigma_i^2\). Ces paramètres peuvent être donnés par l’utilisateur, l’utilisateur peut par exemple fournir l’étiquetage d’une partie de chacun des objets (voir Figure), dont on peut déduire une estimation de \(\mu_i\) et de \(\sigma_i^2\).

Tâche de segmentation semi-automarique : l’utilisateur fournit une indication pour identifier le sujet d’intérêt et l’arrière-plan.

Adéquation de l’image à la segmentation (3/3)

Il existe bien sûr des modèles plus sophistiqués, paramétriques ou non paramétriques, pour décrire la distribution des intensités dans chacune des classes. Dans le cas extrême où on a peu d’information a priori sur une des classes, par exemple pour l’arrière-plan qui en général a une distribution d’intensités plus complexe, on peut utiliser un a priori non informatif, comme une loi uniforme sur l’ensemble des intensités.

Tâche de segmentation semi-automarique : l’utilisateur fournit une indication pour identifier le sujet d’intérêt et l’arrière-plan.

Champs de Markov et régularité

En ce qui concerne la modélisation de l’étiquetage, on peut faire l’hypothèse que la carte \(u\) est constante par morceaux, c’est-à-dire que les pixels voisins appartiennent le plus souvent au même objet. Les champs de Markov constituent un modèle probabiliste qui permet de capturer ces contraintes contextuelles.

Définition

Soit \(G=(S, A)\) le graphe non orienté constitué des pixels de l’image (\(S = \Omega\)) et dont les arcs correspondent aux voisinages directs entre pixels (voir Figure). Un champ de Markov sur \(G\) est une famille de variables aléatoires \(\{X_p, p \in \Omega\}\) telle que \[ P(X_p | \{X_q, q\in S - \{p\}\}) = P(X_p | \{X_q, \{p, q\}\in A\}). \]

Intuitivement, cela signifie que la connaissance apportée par toute l’image pour déterminer la probabilité conditionnelle d’un pixel donné peut se résumer dans la simple connaissance des pixels voisins.

Le graphe d’adjacence d’une image ; les pixels sont matérialisés par des points, le pixel central (en bleu) a pour voisins les 4 pixels adjacents (en rouge).

Équivalence avec champs de Gibbs (1/2)

Le théorème d’Hammersley-Clifford établit l’équivalence entre la propriété de Markov et une distribution de Gibbs. Une distribution de Gibbs sur un graphe est une distribution qui peut s’écrire \[ P(x) = \frac{1}{Z} \exp\left(-\sum_{C\in \mathcal{C}} V_C(x)\right) \] où \(\mathcal C\) est l’ensemble des cliques du graphe \(G\), et \(Z\) est une constante (de normalisation).

Rappel : une clique \(C\) est un ensemble (maximal) de sommets du graphes tel que toute paire de sommets de \(C\) est dans \(A\).

Équivalence avec champs de Gibbs (2/2)

Dans notre graphe d’adjacence, les cliques sont constituées des paires de sommets voisins. Pour un étiquetage \(u\) donné et \(p, q\) deux pixels voisins, on peut prendre pour le potentiel \(V_{p,q}(u)\) la définition suivante : \[ V_{p, q}(u) = \begin{cases} \beta & \text{si }u[p] \neq u[q]\\ -\beta & \text{si }u[p] = u[q]\\ \end{cases} \]

Le rôle du paramètre \(\beta\) (choisi une bonne fois pour toutes) est d’équilibrer l’influence relative du critère de régularité par rapport au critère d’attache aux données.

Optimisation stochastique (1/2)

En reprenant les notations de la partie précédente, on doit donc minimiser \[ V(u|f) = \sum_{p\in \Omega} \frac{(f[p] - \mu_{u[p]})^2}{\sigma^2_{u[p]}} + \sum_{\{p, q\} \in A} V_{p, q}(u). \]

Constat : il est impossible d’envisager une recherche exhaustive, on a \(|\Omega|^k\) étiquetages possibles (exemple pour une segmentation binaire, image de 1 megapixel, \(10^{12}\) solutions possibles).

Optimisation stochastique (2/2)

Algorithme de Métropolis-Hastings avec recuit-simulé :

1. on démarre d’un étiquetage aléatoire \(u_0\),
2. on sélectionne un pixel \(p\) aléatoirement et on change son étiquette
3. on calcule la différence de potentiel \(\delta V\) induite par ce changement

• si le potentiel baisse, on conserve le changement
• si le potentiel augmente, on conserve le changement avec probabilité \(\exp(-\delta V / T)\), où \(T\) est un paramètre de « température ».

Cet algorithme permet d’éviter de tomber trop rapidement dans un minimum local d’énergie. En général on part d’une température élevée, qu’on fait baisser au cours de l’optimisation.

Méthode basée sur les graphes

Objectif du TP : implémenter une technique d’optimisation du critère précédent (sous conditions) basée sur la recherche d’une coupe minimale dans un graphe.