L'algorithme k-means dans le cadre du traitement de l'image

Note préliminaire : dans la suite, $d$ est issue de la distance euclidienne.

Il procède ainsi (on note $S$ la fonction qui à un point de $\{0..n\}\times\{0..m\}$ associe son niveau de gris) :

1. Choisir $k$ niveaux de gris (distincts) $y_1$, $y_2$ ... $y_k$ (on les appelle centres des classes)
2. Construire les $k$ classes $C_i$ telles que $C_i=\{x \vert d(y_i,S(x))<d(y_j,S(x)) \text{ } \forall j\neq i \}$
3. Recalculer le centre des classes : $y_i=\frac{\sum_{x\in C_i} S(x)}{\vert C_i\vert}$
4. Reconstruire les $k$ nouvelles classes en retrourant à l'étape 2. Si les nouvelles classes ne sont pas différentes des anciennes, s'arrêter.