Projet-1 L2-Apprentissage

Posted on Thu 10 October 2019 in cours

Projets d'introduction à l'apprentissage automatique : apprentissage non-supervisé

Dans le cadre du cours d'introduction à l'apprentissage, vous devrez réaliser deux mini-projets. Le second projet portera sur une application de l'algorithme des mixtures de gaussiennes.

Le projet sera à réaliser en binôme.

Vous rendrez un rapport au format pdf que vous enverrez à l'adresse suivante aurelien.decelle@u-psud.fr avant le 5 janvier 2020 à 23h59, ainsi que le code source qui a servi à générer les résultats présentés dans le rapport. Evitez autant que possible l'envoie de tout autre fichier que le code et le rapport. Il sera important pour l'évaluation de suivre les points suivants

Sur le rapport
- le rapport comportera une brève introduction, une présentation des résultats et, si nécessaire, les difficultés rencontrées et les solutions envisagées
- le rapport ne doit pas comporter plus de 4 pages (2 feuilles recto/verso).
- chaque figure devra comporter une légende expliquant ce qui est illustré, et la fonction du code permettant de générer la figure (il n'est pas nécessaire de mettre beaucoup de figures). Attention, une pénalité sera appliquée si une figure n'est pas reproductible. Barème : 3 points sur le rendu global. ATTENTION : si le rapport n'est pas rendu, vous perdez automatiquement les 3 points du rapport, ainsi que les 6 points des résultats (donc 9 points).
Sur le code
- il devra être clair et commenté, avec des noms de variables bien choisis
- IMPORTANT : pour chaque figure présentée dans le rapport, vous écrirez une fonction permettant de générer les données (il faudra donc dans le code avoir une fonction spécifique permettant de générer les données). Le code sera évalué globalement sur 3 points.
Evaluation de l'algorithme : il sera possible de rendre le projet à différents stades d'avancement en fonction de ce qui vous a été possible de faire
- algorithme des k-moyennes : si vous n'avez pas pu faire fonctionner l.a mixture de gaussienne, vous pouvez rendre un projet fait avec l'algorithme des k-moyennes (cf premiers tps). Néanmoins un tel rendu vous permettra au maximum d'avoir la note de 13/20 en rendant un rapport correctement écrit
- algorithme de la mixture de gaussiennes : il permet d'avoir la note maximum sur le code qui sera sur 8 points.

Travaux à réaliser

Le jeu de données

Le travail consistera à effectuer une segmentation d'une image par couleur de façon automatique en utilisant l'algorithme de la mixture de gaussiennes. Vous utiliserez l'image suivante MMS. pour ce qui est des tests préliminaires. Vous suivrez ensuite les instructions spécifique à chacune des questions.

Segmentation d'images par couleur

L'idée est la suivante. Une image correspond à un tableau de pixels à deux dimensions. Chaque pixel correspond à un entier codé sur 24 bits: 3 series de 8 bits codant pour les couleurs RVB. On peut donc à partir d'une image créer un nouvel ensemble de point qui correspondrait à associer à chaque pixel une position dans l'espace des couleurs RVB. Concrètement, à chaque pixel seront associées des coordonnées (parfois notées x,y,z dans un espace à 3 dimensions) associées à l'intensité en Rouge, en Vert, et en Bleu, respectivement. Il y aura donc autant de points dans l'espace des couleurs qu'il y a de pixels dans l'image de départ. Vous pouvez utiliser le code suivant pour vous familiariser avec les commandes permettant de lire une image, de récupérer les composantes RVB pour chaque pixel et écrire une nouvelle image (ici on a inversé les couleurs):

import javax.imageio.ImageIO;
import java.awt.image.BufferedImage;
import java.awt.Color;
import java.io.File;
import java.io.IOException;

public class LoadSavePNG
{
    static BufferedImage bi;

    public static void main(String[] args) throws IOException
    {
        String path = "./";
        String imageMMS = path + "mms.png";

        // Lecture de l'image ici
        BufferedImage bui = ImageIO.read(new File(imageMMS));

        int width = bui.getWidth();
        int height = bui.getHeight();
        System.out.println("Hauteur=" + width);
        System.out.println("Largeur=" + height);

        int pixel = bui.getRGB(0, 0);
        //System.out.println("Pixel 0,0 = "+pixel);
        Color c = new Color(pixel);
        System.out.println("RGB = "+c.getRed()+" "+c.getGreen()+" "+c.getBlue());
        // Calcul des trois composant de couleurs normalisé à 1
        double[] pix = new double[3];
        pix[0] = (double) c.getRed()/255.0;
        pix[1] = (double) c.getGreen()/255.0;
        pix[2] = (double) c.getBlue()/255.0;
        System.out.println("RGB normalisé= "+pix[0]+" "+pix[1]+" "+pix[2]);

        int[] im_pixels = bui.getRGB(0, 0, width, height, null, 0, width);

        /** Creation du tableau **/
        Color[] tabColor= new Color[im_pixels.length];
        for(int i=0 ; i<im_pixels.length ; i++)
        tabColor[i]=new Color(im_pixels[i]);

        /** inversion des couleurs **/
        for(int i=0 ; i<tabColor.length ; i++)
        tabColor[i]=new Color(255-tabColor[i].getRed(),255-tabColor[i].getGreen(),255-tabColor[i].getBlue());

        /** sauvegarde de l'image **/
        BufferedImage bui_out = new BufferedImage(bui.getWidth(),bui.getHeight(),BufferedImage.TYPE_3BYTE_BGR);
        for(int i=0 ; i<height ; i++)
        {
        for(int j=0 ; j<width ; j++)
            bui_out.setRGB(j,i,tabColor[i*width+j].getRGB());
        }
        ImageIO.write(bui_out, "PNG", new File(path+"test.png"));

    }
}

La première partie du projet consiste à vérifier que votre algorithme fonctionne pour cette tâche. En utilisant l'image fourni, mettez en place un code permettant d'extraire de l'image les m&ms par couleur (on distingue à l'oeil 6 couleurs, il faudra faire attention au fond et au reflet qui peuvent jouer un rôle). Vous pourrez ici facilitez la tâche de votre algorithme en choississant la position initiale des centres de façon intelligente. Vous devrez donc dans le rapport illustrer le résultat de cette partie et préciser quelle fonction du code est utilisée pour générer les figures.

ATTENTION : il est important que les couleurs codées sur des entiers dans [0,255] soit renormalisées dans [0,1] (par une division). N'oubliez pas de le faire au chargement des données, et de refaire la conversion inverse lors de l'écriture de l'image.

Une fois cette partie codée, vous pouvez passer à la suite.

Applications

Si la partie précédente fonctionne, il est demandé de réaliser 3 éléments de la liste ci-dessous.

En choississant une méthode d'initialisation des centres avec aléa, Faites tourner l'algorithme de la mixture de gaussienne avec 10 gaussienne et avec 10 conditions initiales différentes. Calculer pour chacune le score. Comparer les résultats obtenus entre la meilleur et la pire partition.
Faites varier le nombre de centres de $K=2$ jusqu'à $K=10$. Pour chaque valeur de $K$, faites tourner l'algorihme avec 10 conditions initiales différentes. Tracer ensuite la courbe du score de la meilleur partition en fonction de $K$.
Prenez une image de votre de choix et effectuer la segmentation par couleur en faisant attention au choix du nombre de gaussiennes. Commentez vos résultats.
En utilisant les données suivantes: data (colonne 1: coordonnée x, colonne 2: coordonnée y), faites varier le nombre de centres de $K=2$ jusqu'à $K=10$. Pour chaque valeur de $K$, faites tourner l'algorihme avec 10 conditions initiales différentes. Peut-on déduire de la courbe du score en fonction de $K$ le nombre de centres utilisé.
Générer 1000 points en une dimension, avec 500 qui seront distribués selon une gaussienne centrée en -2 et de variance 0.2, et une autre centrée en 3 et de variance 1.5. Montrer que la mixture de gaussienne apprend correctement la densité $\rho_k$, la position et les moyennes des gaussiennes. Tracer sur un graphe, l'histogramme normalisé (l'aide de l'histogramme doit être égale à 1) et par dessus la fonction de répartition correspondant aux deux gaussiennes obtenus.

Compression (points bonus)

Pour les plus téméraires, il est possible de s'attaquer à l'application suivante. En faisant des clusters/groupes/centres de points dans l'espace des couleurs, on peut faire une simplification de l'image (une compression) en remplaçant la couleur d'un pixel par la couleur du centre (dans l'espace des couleurs) auquel le point appartient (d'après votre classification). Si les centres sont suffisamment nombreux et bien choisis, l'image simplifiée sera fidèle à l'image de départ.

Compresser votre image en utilisant 5, 10, 15 puis 20 centres. Pour chaque compression, vous utiliserez plusieurs conditions initiales et choisirez la meilleur partition.

Barème approximatif

rapport 3 pts
qualité du code 3 pts
justesse de l'algorihme 8 pts
résultats 6 pts

Ce barème n'est qu'indicatif puisque qu'entrera en compte la cohérence globale du rendu.

Rappel

Choisir les conditions initiales

Pour faire tourner l'algorithme de la mixture de gaussiennes, il faut choisir des conditions initiales pour la position des gaussiennes, la variance de chacune ainsi que la proportion de données dans chacune des gaussiennes. Pour les centres, vous pouvez utiliser les méthodes vu en cours. Pour la variance et la densité on peut imaginer les deux solutions suivantes:

Prendre des variances de l'ordre de grandeur du jeu de données (~$0.5$ ou plus petit pour les couleurs), et des $\rho_k=1/K$.
Faire tourner un algorithme des k-moyennes et utiliser le résultat du partitionnement pour initialiser les autres paramètres

Equations pour la mixture de gaussienne

Assignement :

$$ r_k^{(d)} = \frac{ \rho_k \prod_{i=1}^D \frac{1}{\sqrt{2\pi (\sigma_i^{(k)})^2}} \exp\left[-\frac{(x_i^{(d)} - m_i^{(k)})^2}{2 (\sigma_i^{(k)})^2}\right] }{\sum_{l=1}^{K} \rho_l \prod_{i=1}^D \frac{1}{\sqrt{2\pi (\sigma_i^{(l)})^2}} \exp\left[-\frac{(x_i^{(d)} - m_i^{(l)})^2}{2 (\sigma_i^{(l)})^2}\right] } $$

Mise à jour (on notera $R_k=\sum_{d=1}^M r_k^{(d)}$) :

$$ m_i^{(k)} = \frac{\sum_{d=1}^M r_k^{(d)} x_i^{(d)} }{R_k} \\ (\sigma_i^{(k)})^2 = \frac{\sum_{d=1}^M r_k^{(d)} (x_i^{(d)} - m_i^{(k)})^2}{R_k} \\ \rho_k = \frac{R_k}{M} $$

Calcul du score

Après convergence, en utilisant $\vec{m}^{k}$ et $\rho_k$, le score pour une donnée (d) est

$$ \mathcal{L}^{(d)} = \log \left[ \sum_{k=1}^{K} \rho_k \prod_i \frac{1}{\sqrt{2\pi(\sigma_i^{(k)})^2}} \exp\left(-\frac{(x_i^{(d)} - m_i^{(k)})^2}{2(\sigma_i^{(k)})^2} \right) \right] $$

Et on obtient le score total en calculant la moyenne : $\mathcal{L} = M^{-1} \sum_d \mathcal{L}^{(d)}$.

aaah