next up previous
suivant: Hystéresis monter: Segmentation par régions : précédent: Introduction

Sous-sections

Segmentation par la méthode des k-means

La méthode des k-means est un outil de classification classique qui permet de répartir un ensemble de données en $k$ classes homogènes. La plupart des images (photos, dessins vectoriels 2D, synthèses 3D, ...) vérifient localement des propriétés d'homogénéité, notamment en terme d'intensité lumineuse. L'algorithme des k-means permet donc d'apporter une solution à la segmentation d'images.


Présentation

La méthode des k-means a été introduite par J. McQueen [10] en 1971 et mise en \oeuvre sous sa forme actuelle par E. Forgy [5]. De nombreuses variantes se sont succédées depuis afin d'étendre ses capacités de classification (séparations non linéaires) : kernel k-means [15] (k-means basée sur des méthodes à noyaux), améliorer ses performances : global-k-means [8], $k$-Harmonic means [14], automatiser le choix du nombre de clusters : Gaussian-means [6], $X$-means [11].  
 
Dans le cadre de la classification non supervisée, on cherche généralement à partitionner l'espace en classes concentrées et isolées les unes des autres. Dans cette optique, l'algorithme des k-means vise à minimiser la variance intra-classe, qui se traduit par la minimisation de l'énergie suivante :
$\displaystyle E$ $\textstyle =$ $\displaystyle \frac{1}{2}\sum_{c\in\mathcal{C}}{\sum_{x\in c}{\vert\vert x-m_c}\vert\vert^2}$ (1)
  $\textstyle =$ $\displaystyle \frac{1}{2}\sum_{c\in\mathcal{C}}{\char93  c\times V(c)}$ (2)
$\displaystyle E$ $\textstyle =$ $\displaystyle \frac{1}{2}\sum_{x\in\mathcal{D}}{\min_{c\in\mathcal{C}}{\vert\vert x-m_c}\vert\vert^2}$ (3)

avec $\mathcal{C}$ l'ensemble des clusters et pour chaque cluster $c$, $m_c$ son centre (appelé noyau), $V(c)$ sa variance, $\char93  c$ le nombre de ses éléments et $\mathcal{D}=\bigcup_{c\in\mathcal{C}}{c} $ l'ensemble des données que l'on cherche à classer.

Algorithme

La minimisation de l'énergie (1) peut se réaliser par une descente de gradient sur les noyaux dont les propriétés de convergence ont été étudiées par [3]. Elle peut se traduire par les étapes suivantes :
1.
initialisation des noyaux.
2.
mise à jour des clusters.
3.
réévaluation des noyaux.
4.
itérer les étapes 2. et 3. jusqu'à stabilisation des noyaux.
 
 
L'algorithme 1 (p. [*]) présente ces étapes de façon plus formelle.

Convergence et initialisation des k-means

L'algorithme ainsi défini converge vers un minimum local de l'énergie, qui se traduit par une partition de l'espace des données en des classes séparées par des hyperplans et réalise une tessellation de Voronoï basée sur les noyaux des clusters.  
 
La qualité de la solution ainsi trouvée dépend fortement des noyaux initiaux. De plus la sensibilité de l'algorithme à l'initialisation est d'autant plus grande que la dimensionalité des données est grande [4].  
 
De nombreuses stratégies ont été élaborées afin d'établir une bonne initialisation aux k-means :  
 
Certaines variantes de l'algorithme des k-means sont moins sensibles aux noyaux initiaux :


\begin{table}
% latex2html id marker 268
\begin{tabular*}{\linewidth}{l}
\hlin...
...
\textbf{Fin tant que}\\
\textbf{Fin}\\
\hline\\
\end{tabular*} \end{table}

Choix du nombre $k$ de clusters

L'algorithme classique des k-means laisse un paramètre libre : le nombre de clusters, ce qui dans le cas de la segmentation d'images correspond au nombre d'intensités utilisées pour représenter l'image. Généralement le choix de $k$ est fait empiriquement en sélectionnant la valeur de $k$ qui minimise l'énergie (1).  
 
Différents critères permettent d'estimer le nombre de clusters en minimisant la distance intra-classes et à maximiser la distance inter-classes (par exemple en segmentation d'images couleurs [12]).  
 
De nombreuses stratégies permettent de déterminer le nombre de clusters pendant le déroulement de l'algorithme. Ces méthodes sont basées sur un processus itératif au cours duquel on choisit de subdiviser les clusters précédemment établis en se basant sur un critère statistique (par exemple grâce aux BIC : Bayesian Information Criterion) : Gaussian-means [6] et $X$-means [11].  
 
Une méthode spécialement adaptée à la segmentation d'images couleurs a été développée par L. Lucchese [9]. Cette technique réalise une première classification par la méthode des k-means dans l'espace des chrominances UV, suivie de plusieurs classifications successives dans l'espace des luminances Y.

k-means et segmentation d'images

Les méthodes de classification (clustering) issues de l'analyse de données permettent de regrouper des objets possédant des propriétés similaires. Elles constituent donc une approche naturelle pour réaliser une segmentation d'images.  
 
La méthode des k-means a été très utilisée dans ce contexte [13], d'une part pour sa simplicité de mise en \oeuvre et d'autre part car elle peut fournir une bonne approximation de la segmentation recherchée. Néanmoins cette méthode souffre d'un défaut qui a son importance en segmentation d'images : elle introduit des discontinuités spatiales assez fortes aux frontières des classes. Des méthodes de régularisation sont donc généralement employées pour renforcer la connexité et ainsi réduire le nombre de composantes connexes de chaque classe.

Résolution des problèmes de connexité spatiale

De nombreuses variantes de l'algorithme des k-means introduisant des informations de cohérence spatiale ou de connexité ont été développées pour améliorer la qualité de la segmentation réalisée par cette méthode.  
 
Certaines approches consistent en la minimisation d'une énergie modifiée :

\begin{displaymath}
E=\lambda D + (1-\lambda)V^{*}
\qquad\textrm{avec}\quad 0\leq\lambda\leq 1
\end{displaymath}

$D$ est une mesure de connexité spatiale des classes et $V^{*}$ l'énergie des k-means normalisée.

 
 
D'autres méthodes s'ajoutent en tant que post-traitement aux k-means afin de régulariser la segmentation initiale :


next up previous
suivant: Hystéresis monter: Segmentation par régions : précédent: Introduction
Omar El Ganaoui -- Matthieu Perrot