Clustering par K-means, segmentation d'image

Etudiant : Paul AUBRY

Tuteur : Jacques-Olivier LACHAUD

Introduction : Clustering par k-means

Le clustering ou algorithme des k moyennes a pour but de regrouper des populations en communautés disposant de critères communs proches, jusqu'à avoir des communautés homogènes qu'on appellera cluster et qui ont pour représentant un centroïde.
Pour déterminer ces clusters, on regroupera les différents éléments en fonction d'une distance. Cette notion de distance est différente en fonction des domaines d'applications.
Le clustering par k-means peut être utilisé pour faire de la segmentation de clientèle, du clustering en Data Mining ou encore sur des images.

Algorithme pour l'image

Algorigramme du Clustering par K-means

Nous allons voir ici, comment procéder de manière théorique, pour réaliser un clustering. Tout d'abord, nous devons choisir k points aléatoirement, qui seront les centroïdes, et un coefficient λ qui nous permettra de calculer les distances.
Ensuite, nous allons affecter chaque point de l'image à un cluster. Pour cela, il faut calculer la distance entre le point, et chaque k. La distance la plus courte nous permettra de déterminer quel cluster choisir.

Un point est représenté de la manière suivante : [ x , y , r , g , b ] .
Avec x et y les coordonnées et r, g, b les composantes de couleurs.

Pour calculer la distance on utilise la formule suivante :

$d=\lambda (x_{1}-x_{2})^{2}+\lambda (y_{1}-y_{2})^{2}+(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}$

Lorsque les clusters sont définis, on calcul la moyenne de chaque cluster, afin de récupérer de nouveaux centres.
On réitère les actions vus précédemment mais cette fois-ci avec les nouveaux centres.
Dès que l'on obtient des centres "stable", on peut modifier l'image.

Réalisation grâce à Python

Pour ce faire, il faut installer plusieurs bibliothèques.

• "numpy", qui va nous servir à effectuer les calculs de manières bien plus rapide.
• "PIL" pour le traitement des images.

from random import *
from PIL import Image
import numpy as np

def clustering(k,coef):
    """Entrée :1 entier un flottant
    Sortie : image modifiée"""
    
    image0 = Image.open("Kowloon-small-329x216.png")
    image = image0

    l = image.width
    h = image.height

    tabImage = imageTab(image)
    tabImageCoeff = coefficiente_valeur(tabImage, l, h)

    centroides = meilleurs_centres(tabImage, tabImageCoeff, k, l ,h, coef, image)
    coeffCentroides = coefficiente_valeur(centroides, l, h)

    distance = distancePoints(tabImageCoeff, coeffCentroides,k,coef)
    indice = distance_plus_courte(distance)

    clusters = attribution_aux_clusters(tabImage,indice,k)
    NumpyClusters = clustersEnNumpy(clusters,k)

    print("En cours de finalisation...")

    for i in range(0,k):
        change_couleur_cluster( NumpyClusters[i] , centroides[i] , image )
        

    image.save(str(k)+"-"+str(coef)+"Kowloon-small-329x216.png")    
    image.show()
    image0.close()
    image.close()

Résultats

Image originale 329 x 216 px	Image modifiée : k=10, coeff = 0,0001
J'ai pu obtenir ces résultats après deux minutes environ. On constate que les détails sont les mêmes, et on obtient des couleurs différentes. Plus le coefficient est petit, plus l'image est sombre.	Image modifiée : k=10, coeff = 0,7
Quand le coefficient est égale à zéro, le traitement se fait juste sur les couleurs de l'image. Le programme fait une moyenne des couleurs.	Image modifiée : k=16, coeff = 0

Image originale 1920 x 1080 px

Image modifiée : k=50, coeff = 0.5

Pour une image de cette taille, une heure de traitement a été nécessaire. On remarque que les formes principales sont les mêmes, ainsi que les couleurs. Au niveau du ciel et du lac, on peut apercevoir que l'image a été traitée.