##### TP K-MOYENNES


import matplotlib.pyplot as plt
import numpy as np
import numpy.random as rd


##### LECTURE DE L'IMAGE

A = plt.imread('Katherine_Johnson_300x300.png')


#### EXTRACTION DES COULEURS différentes
def liste_couleurs(image:np.array)->list:
    taille = np.shape(image)        # On mémorise le nombre de lignes et de
    nL,nC = taille[0], taille[1]    #   colonnes de l'image
    L = []                          # Initialisation de la liste des couleurs
    for i in range(nL):             # On parcourt tous les pixels de l'image'
        for j in range(nC):         # et on ajoute chaque couleur à la liste
            pixel = (image[i,j,0],image[i,j,1],image[i,j,2])
            L.append(pixel)
    S = set(L)          # Crée un set : ensemble des valeurs distinctes de L
    L = list(S)         # Convertit le "set" en liste
    L = [L[i] for i in range(len(L)) if i%10==0]
    return L            # On renvoie 1/10 de la liste de toutes les couleurs


################## ALGORITHME K-MOYENNE

##########

def dist(p:tuple,q:tuple)->float:
    N= len(p)
    s = 0
    for k in range(N):
        s += (p[k] - q[k])**2
    return np.sqrt(s)


## Question 4
#def initialise_centroides(donnees:list,k:int)->list:











## Question 5
#def plusProcheCentre(x:tuple,Lc:[tuple])->(tuple,int):













## Question 6
#def calcul_classes(donnees:list,Lc:list)->list:






## Question 7
#def barycentre(L_points:[tuple])->tuple:










## Question 8
def calcul_1_centre(donnees:[tuple],Lclasses:[int],j)->tuple:
    Lpoints_classej = []    # Initialisation de la liste des points de classe j
    for i in range(len(donnees)):       # on parcourt les indices des données
        x = donnees[i]                  # pour chaque point x des données
        if Lclasses[i]==j:              # si x est dans la classe d'indice j
            Lpoints_classej.append(x)   # on ajoute x dans la liste des points
                                        # Ligne à compléter
    return centre_j

########
def calcul_k_centres(donnees:[tuple],Lclasses:[int],k:int)->[tuple]:
    Lcentres = []
    for j in range(k):
        centre_j = calcul_1_centre(donnees,Lclasses,j)
        Lcentres.append(centre_j)
    return Lcentres


#######
def actualise_centres(donnees:[tuple],Lcentres:[tuple])->([tuple],float):
    k=len(Lcentres)
    Lclasses = calcul_classes(donnees,Lcentres)
    new_centres=calcul_k_centres(donnees,Lclasses,k)
    dmax=0
    for i in range(k):
        d=dist(Lcentres[i],new_centres[i])
        if d>dmax:
            dmax=d
    return new_centres,d

#######
def kmoyenne(donnees:[tuple],k:int)->[tuple]:
    # initialisation et affichage des centroïdes
    Lcentres = initialise_centroide(donnees,k)
    print('Centres initiaux:')
    print(np.array(Lcentres))
    # Actualisation des centroïdes et incrémentation du compteur
    Lcentres,d = actualise_centres(donnees,Lcentres)
    compteur=1
    print('Compteur =',compteur,'d =',d)
    while d > 1e-3 and compteur < 100:  # tant que nouveaux centres trop différents
        Lcentres,d = actualise_centres(donnees,Lcentres)
        compteur+=1
        print('Compteur =',compteur,'d =',d)
    return Lcentres


######## APPLICATION

## Question 12
def nouvelle_image(image:np.array,k:int)->np.array:
    donnees = liste_couleurs(image)     # On récupère 1/10 des couleurs de image
    Lcentres = kmoyenne(donnees,k)      # Apprentissage des Kmeans
    print(np.array(Lcentres))           # Affiche le résultat de l'apprentissage
    print("Apprentissage terminé. Reconstruction de l'image. Patientez !")
    Dim = np.shape(image)           # On mémorise les dimensions de l'image
    new_image=np.ones(Dim)          # On crée une image blanche de même taille
    nL,nC = Dim[0],Dim[1]           # Nombres de lignes et colonnes de l'image
    for i in range(nL):             # On parcourt tous les pixels de l'image
        for j in range(nC):         #  et on attribut à chaque pixel de la
            pixel = image[i,j]      #  nouvelle image la couleur la plus proche
                                    # Ligne à compléter
    return new_image

def trace_image(image:np.array,k:int):
    new_image = nouvelle_image(image,k)
    plt.close()
    plt.imshow(new_image)
    plt.show()
    plt.imsave('Katherine_Johnson_300x300_bis.png',new_image)

## Question 13
# On constate que la convergence de l'algorithme (stabillisation des centroîdes)
# se fait avec une vitesse aléatoire. Cette convergence n'est pas assurée et il
# peut même parfois une divergence
# Cette convergence n'est ni régulière ni même assurée