L'algorithme des k-moyennes ou k-means est un algorithme de partitionnement ou clustering.

Son but est de répartir un jeu de données en k sous-groupes tels que chaque donnée appartient au groupe dont la moyenne lui est le plus proche.

Relisez la phrase ci-dessus plusieurs fois jusqu'à vous convaincre qu'elle est incompréhensible, et laissez moi tâcher d'expliquer ça en langage humain.

Imaginons un gros tas de données avec des valeurs bien définies. Je veux regrouper ces données en k groupes de façon à ce que chaque groupe soit intuitivement cohérent.

Par exemple, si je suis un supermarché et que je veux cibler des campagnes publicitaires, je vais essayer de répartir mes clients en groupes cohérents (peut-être en fonction de leurs achats ?), même si je n'ai aucune idée au préalable de ce que pourraient bien être ces groupes.

Je peux aussi récupérer la base de données de Wikipédia, extraire tous les articles qui parlent de « Python », et répartir ces articles en différents groupes en fonction du contenu, ce qui ne manquera pas de mettre en évidence les différentes signification du terme (le serpent, le langage de programmation, le revolver, etc.).

Quant à nous, nous allons appliquer l'algorithme k-means à l'imagerie pour découvrir comment nous pouvons extraire une palette de couleur d'une photographie.

Utiliser K-means pour extraire une palette de couleurs

Comme c'est vendredi et que je sais que vous êtes de grands enfants, voici de quoi jouer un peu.

Notez que pour d'obscures raisons techniques, cela peut ne pas fonctionner en fonction de l'url de l'image. Les photos provenant de Flickr ou Wikimedia commons ne poseront pas de problèmes.

Pour ceux que ça intéresse, le code est disponible sur Github. Bon, c'est pas tout ça, on n'est pas non plus là que pour rigoler, hein !

Télécharger et afficher l'image

Pour dessiner sur une page Web, nous allons utiliser l'API Canvas. La première chose à faire, c'est de télécharger l'image dont l'url a été indiquée pour la charger dans ledit canvas.

Notre code HTML se bornera à ça.

<canvas id="canvas"></canvas>
<form id="image-form" method="post" action="#">
    <label for="image-input">Url de l'image</label>
    <input type="input" id="image-input"  />

    <input type="submit" value="Go baby!" />
</form>

Ensuite, voici le code js qui permet de configurer les événements qui vont bien.

// Get html elements
var canvas = document.getElementById('canvas');
var form = document.getElementById('image-form');
var image_input = document.getElementById('image-input');
var k_input = document.getElementById('k');
var n_input = document.getElementById('n');

// Create an empty image element
var img = new Image();
img.crossOrigin = '';

// When the form is submitted, set the "src" attribute
// to start loading the image
form.addEventListener('submit', function(evt) {
    evt.preventDefault();
    img.src = image_input.value + '?uncache=' + (new Date()).getTime();
});

// Wait til the image is loaded before going any further
img.addEventListener('load', function(evt) {
    displayImage(canvas, img);
});

Le mécanisme est assez classique. On créé un élément Image vide. Le fait d'affecter son attribut src va démarrer le chargement de l'image. Une fois ce chargement terminé, un événement load est lancé.

Attention à ne pas tomber dans le piège classique qui consiste à spécifier l'attribut src avant de configurer le listener sur load. Il serait alors possible que ledit événement soit soulevé avant même que l'on ai pu faire quoi que ce soit.

Notez également la configuration de l'attribut crossOrigin. J'ai tellement galéré sur ce problème que ça me déprime rien que d'en parler, alors je vous laisse vous renseigner par vous même.

Une fois tout ceci en place, il nous reste encore à afficher notre image dans notre canvas. Notez qu'on limite assez fortement la taille de l'image pour conserver des performances raisonnables.

var CANVAS_WIDTH = 400;

var displayImage = function(canvas, img) {

    // Resize the canvas to the correct size
    var ratio = img.width / img.height;
    canvas.width = CANVAS_WIDTH;
    canvas.height = CANVAS_WIDTH / ratio;

    // Use the rendering context to draw the image
    var ctx = canvas.getContext('2d');
    ctx.drawImage(img, 0, 0, canvas.width, canvas.height);
};

Tout ceci étant plutôt limpide et parfaitement documenté, je ne vois pas trop l'intérêt de nous attarder plus que nécessaire.

Initialiser les clusters

Première étape de l'algorithme des k-moyennes : initialiser k clusters de manière totalement arbitraire. C'est ce que nous allons faire ici en sélectionne au hasard des pixels dans l'image.

var initializeClusers = function(canvas, k) {
    var x, y;

    // Initialize random clusters
    var clusters = (Array.apply(null, new Array(k))).map(function() {
        x = Math.floor(Math.random() * canvas.width);
        y = Math.floor(Math.random() * canvas.height);

        return {
            x: x,
            y: y,
            hue: getHue(canvas, x, y),
            saturation: getSaturation(canvas, x, y),
            luminosity: getLuminosity(canvas, x, y),
            nb_pixels: 0,
            total_x: 0,
            total_y: 0,
            total_hue: 0,
            total_saturation: 0,
            total_luminosity: 0
        };
    };
    return clusters;
};

Voilà notre structure initialisée. Notez qu'au niveau des couleurs, on travaillera dans l'espace HSL, plus pertinent que RGB.

Itérer pour mettre à jour les k-moyennes

Le cœur de l'algorithme réside en son processus itératif. À chaque itération, nous allons affecter tous les pixels de notre image au cluster adéquat. Ensuite, nous allons mettre à jour les clusters en calculant la nouvelle moyenne.

Le nombre d'itération peut être déterminé à l'avance, ou on peut continuer tant que les clusters ne sont pas stables. Dans le cas moyen, l'algo converge assez vite.

var iterate = function(canvas, clusters) {
    affectPixelsToClusters(canvas, clusters);
    updateClusters(canvas, clusters);
};

Clusteriser les données

Affecter une donnée à un cluster revient à déterminer, pour un paramètre donné, quel est le cluster le plus proche de cette donnée.

En l'occurrence, le paramètre concerné ici est la couleur du pixel.

Notez l'extrême inefficacité de cet algorithme. Notez également que j'ai volontairement laissé les optimisations de côté pour faciliter la compréhension du code.

var affectPixelsToClusters = function(canvas, clusters) {
    var mean;

    for (var x = 0 ; x < canvas.width ; x++) {
        for (var y = 0 ; y < canvas.height ; y++) {
            // Select the cluster the pixel should go into
            cluster_index = getClosestCluster(canvas, clusters, x, y);

            // Update the cluster data
            clusters[cluster_index].nb_pixels++;
            clusters[cluster_index].total_x += x;
            clusters[cluster_index].total_y += y;
            clusters[cluster_index].total_hue += getHue(canvas, x, y);
            clusters[cluster_index].total_saturation += getSaturation(canvas, x, y);
            clusters[cluster_index].total_luminosity += getLuminosity(canvas, x, y);
        }
    }
};

Affecter chaque donnée à un cluster

Ici, nous affectons chaque pixel à un cluster en considérant un seul paramètre : la couleur. C'est à dire que chaque cluster a pour couleur la couleur moyenne de tous les pixels qui le composent, et c'est cette donnée qui sera considérée pour affecter chaque pixel.

Il est intéressant de remarquer que l'on peut très bien décider de considérer d'autres paramètres. Par exemples, si on affecte les pixels en ne considérant que leurs coordonnées dans l'image, on obtiendra au final un sympathique diagramme de Voronoi tel que celui qui illustre ce billet.

Mettre à jour les clusters

Une fois que toutes nos données (nos pixels) ont été affectées à des clusters, l'itération est terminée. Il reste à mettre à jour les clusters, c'est à dire établir la nouvelle moyenne des données qu'il contiennent, et repartir pour un tour.

var updateClusters = function(canvas, clusters) {
    clusters.foreach(function(cluster) {
        cluster.x = cluster.total_x / cluster.nb_pixels;
        cluster.y = cluster.total_y / cluster.nb_pixels;
        cluster.hue = cluster.total_hue / cluster.nb_pixels;
        cluster.saturation = cluster.total_saturation / cluster.nb_pixels;
        cluster.luminosity = cluster.total_luminosity / cluster.nb_pixels;
        cluster.nb_pixels = 0;
        cluster.total_x = 0;
        cluster.total_y = 0;
        cluster.total_hue = 0;
        cluster.total_saturation = 0;
        cluster.total_luminosity = 0;
    });
};

Et c'est tout

C'est à peu près tout pour le code métier. Notez que j'ai volontairement laissé de côté toutes les fonctions d'affichage, les optimisations, etc. pour faciliter la compréhension. Encore une fois, le code est disponible si vous souhaitez approfondir votre étude.

Sur ce, je sais que c'est vendredi et que vous êtes pressé·e·s de rentrer chez vous, alors je vous laisse.