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

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.

Pour calculer la distance on utilise la formule suivante :

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 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

Transformation des données en tableaux

def imageTab(fichier):
    """fonction qui récupère toutes les infos du fichier image, pour les convertir
    en tableaux numpy."""
    
    l = fichier.width
    h = fichier.height

    res = []

    for x in range(0,l):
        for y in range(0,h):
            r,g,b = fichier.getpixel((x,y))

            res += [ x, y, r, g, b]

    tab = np.array(res, dtype=float)

    nTab = tab.reshape(l*h,5)

    return nTab


def coordonnees_alea(k, l, h, image):
    """donne k coordonnees et leurs couleurs"""
    
    res = []
    
    for i in range(0,k):

        x = randint(0,l-1)

        y = randint(0,h-1)

        r,g,b = image.getpixel((x,y))
        
        res = res + [[x, y, r, g, b]]

        tab = np.array(res, dtype=float)
       

    return tab

Calcul des distances

def coefficiente_valeur(tab, l, h):
    """Entree : tableau numpy
    Sortie : tableau numpy avec les coordonnées et les couleurs entre 0 et 1"""

    tab2 = np.zeros((len(tab),5), dtype=float)
    
    tab2[:,0] = tab[:,0] / l
    tab2[:,1] = tab[:,1] / h
    tab2[:,2] = tab[:,2] / 255
    tab2[:,3] = tab[:,3] / 255
    tab2[:,4] = tab[:,4] / 255
    
    return tab2


def distancePoints(tab1, tab2, k, coef):
    """donne la distance en couleur entre 2 points
    Entrée : deux tableaux numpy 
    Sortie : un tableau numpy avec les distances entre les points de l'image et les k"""

    taille = len(tab1)

    nTab = np.zeros((taille,k),dtype=float)

    for i in range(0,taille):
        for j in range(0,k):
            nTab[i][j] = coef*( tab1[i][0] - tab2[j][0] )**2 + coef*( tab1[i][1] - tab2[j][1] )**2 + ( tab1[i][2] - tab2[j][2] )**2 + ( tab1[i][3] - tab2[j][3] )**2 + ( tab1[i][4] - tab2[j][4] )**2
            
    return nTab


def distance_plus_courte(tab):
    """Entrée : tableau numpy avec les k distances pour chaque points
    Sortie : tableau numpy des indices où la distance est la plus petite"""

    indice = np.argmin(tab,axis=1)
    
    return indice

Attribution aux clusters

def kTab(k):
    """Entrée : un entier k
    Sortie: un tableau de k tableaux vide"""
    
    tab = []
    
    for i in range(0,k):
        
        tab = tab + [[]]
      
    return tab


def attribution_aux_clusters(tabImage, tabIndice, k):
    """Entrée : 2 tableaux Numpy, un avec les info de l'image, et les indices des distances les plus courtes
    Sortie : tableau de tableaux numpy des clusters"""

    cluster = kTab(k)
    
    for i in range(0,len(tabImage)):

        indice = tabIndice[i]

        cluster[indice] += [tabImage[i].tolist()]

    return cluster


def clustersEnNumpy(tab,k):
    """Entrée : un tableau de tableaux de tableaux de points, un nb de cluster
    Sortie : un tableau de tableaux Numpy"""

    Ntab = kTab(k)

    for i in range(0,k):
        Ntab[i] = np.array(tab[i],dtype=float)

    return Ntab

Nouveaux Centroïdes

def NouveauxCentres(tab,k):
    """Entrée : tableau de tableaux numpy avec les coordonnées des points appartenant à un cluster
    Sortie : un tableau Numpy avec les du nouveaux centres"""

    Nclusters = np.zeros((k,5),dtype=float)

    for i in range(0,k):

        moy = ( np.sum(tab[i],axis=0) / len(tab[i]) )
        moy = moy.astype(int)

        Nclusters[i] = moy

    return Nclusters


def calculCentres(tabImage, tabImageCoeff, tabCentre, k , l, h, coeff):
    """fonction qui reprend toutes celles précédentes, pour calculer un nouveau centre"""

    coeffCentre = coefficiente_valeur(tabCentre, l , h)
    distance = distancePoints(tabImageCoeff, coeffCentre,k,coeff)
    indice = distance_plus_courte(distance)
    clusters = attribution_aux_clusters(tabImage,indice,k)
    NumpyCluster = clustersEnNumpy(clusters,k)

    res = NouveauxCentres(NumpyCluster,k)

    return res


def meilleurs_centres(tabImage, tabImageCoeff,k,l,h,coeff,image):
    """Entrée : 2 tableaux Numpy avec les infos de l'image (1 coefficienté et l'autre non), 3 entiers, 1 flottant et une procédure d'ouverture d'image)
    Sortie : un tableau Numpy, le centre optimal du cluster"""

    centre = coordonnees_alea(k, l, h, image)
    nouveauCentre = calculCentres(tabImage, tabImageCoeff, centre,k,l,h,coeff)
    i = 0
    print("Execution en cours :  0 %")
    while i < 10:
        centre = nouveauCentre
        nouveauCentre = calculCentres(tabImage, tabImageCoeff, centre,k,l,h,coeff)
        print("Execution en cours : "+str(i+1)+"0 %")
        i = i +1

    return nouveauCentre

Modification des couleurs de l'image

def change_couleur_cluster(tabCluster, tabCentre, image):
    """Entrée : tableau numpy de points d'un cluster
    Sortie : zone de couleur changée"""

    numpyCluster = tabCluster.astype(int)
    NtabCluster = numpyCluster.tolist()

    numpyCentres = tabCentre.astype(int)
    NtabCentres = numpyCentres.tolist()
    
    
    for i in range(0,len(NtabCluster)):

        image.putpixel( (NtabCluster[i][0] , NtabCluster[i][1]   ), ( NtabCentres[2], NtabCentres[3], NtabCentres[4] ) )

Fonction finale, le clustering

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()