La couleur est un vecteur : k-means et pipette

De quelle couleur est ton chat ?

Dans la carte « Le Chat Étoile », tu peux envoyer la photo de ton chat, et le chat en 3D prend son pelage. Quand j'ai écrit ça, j'ai eu l'impression de demander à l'ordinateur « de quelle couleur est ce chat ? », une question qu'un enfant résout d'un coup d'œil.

Ancien prof de maths, mon premier réflexe a été de faire la moyenne de tous les pixels. C'est propre, c'est une ligne. Résultat : un brun terne, qui n'est ni le roux du chat ni le gris-bleu du mur derrière lui. Une moyenne de deux groupes ne ressemble à aucun des deux. Il fallait d'abord séparer les groupes, puis moyenner chacun.

Cette séparation s'appelle le k-means, et elle repose sur une idée simple qui change le regard : une couleur n'est pas une teinte, c'est un point dans l'espace.

Une couleur, c'est trois coordonnées

Un pixel, c'est trois nombres : rouge, vert, bleu. Entre 0 et 255 sur une image, entre 0 et 1 dans three.js (new THREE.Color(0.88, 0.53, 0.23)). Trois nombres, c'est un vecteur, exactement comme la position de la leçon 2. Chaque pixel est un point dans un cube dont les arêtes sont les axes r, g et b.

Dans ce cube, deux couleurs proches sont deux points proches. Et « proche » a une définition que tu connais déjà : la distance euclidienne, celle de Pythagore en 3D.

// Squared distance between two colours [r, g, b]
const d2 = (a, b) => (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2;

const orange = [224, 136, 58];
const grey   = [104, 118, 138];
d2(orange, grey);   // 21124, so a distance of about 145

On a calculé 120² + 18² + 80² = 21124, et sa racine, environ 145, serait la vraie distance. Dans le code du Chat Étoile, il n'y a pas de racine, et ce n'est pas un oubli.

Comparer les carrés suffit : la racine carrée est croissante, donc si d² (A) < d² (B), alors d (A) < d (B). Pour trouver le centre le plus proche d'un pixel, il suffit de comparer des carrés. Sur des milliers de pixels et plusieurs centres, on économise des milliers de racines pour le même résultat. Le cube entier mesure au plus 255 × √3 ≈ 442 d'un coin à l'autre.

La moyenne, c'est un centre de gravité

En physique, le centre de gravité de plusieurs masses est leur moyenne pondérée par les positions. C'est la même opération ici : la moyenne de plusieurs couleurs est le centre de gravité de leurs points. Trois pixels d'un poil du chat, (220, 130, 60), (230, 140, 50) et (222, 138, 64), donnent (224, 136, 58), un roux qui se trouve au milieu du petit nuage qu'ils forment.

Ça marche tant que les points forment un seul nuage. Mélange le roux du chat et le gris-bleu du mur à parts égales : le centre de gravité tombe en (164, 127, 98), un brun qui n'est dans aucun des deux nuages, au milieu du vide. C'est le piège de ma moyenne générale.

La même idée sert à la pipette de la carte : quand tu cliques sur la photo, on ne lit pas un seul pixel (trop de grain, un poil plus clair, un reflet) mais la moyenne d'un petit carré de 7 × 7 = 49 pixels autour du clic.

k-means : trouver les nuages

L'algorithme tient en quatre phrases. On choisit k centres de départ. On affecte chaque pixel au centre le plus proche. On déplace chaque centre au centre de gravité des pixels qu'il vient de recevoir. Et on recommence avec les nouveaux centres. Voici l'extrait réel du Chat Étoile (guessCoat, légèrement raccourci) :

// samples = [[r, g, b], ...], one pixel out of 7 of the middle of the photo
const samples = [];
for (let i = 0; i < pixels.length; i += 4 * 7) samples.push([pixels[i], pixels[i + 1], pixels[i + 2]]);

// 5 starting centres, spread along the list of samples
let centres = Array.from({ length: 5 }, (_, k) => samples[Math.floor((k + 0.5) / 5 * samples.length)]);

for (let round = 0; round < 10; round++) {
  const sums = centres.map(() => [0, 0, 0]);
  counts = centres.map(() => 0);
  for (const [i, px] of samples.entries()) {
    let best = 0, bestD = Infinity;
    centres.forEach((c, k) => {
      const d = (c[0] - px[0]) ** 2 + (c[1] - px[1]) ** 2 + (c[2] - px[2]) ** 2;
      if (d < bestD) { bestD = d; best = k; }
    });
    owner[i] = best;                                   // assignment
    sums[best][0] += px[0]; sums[best][1] += px[1]; sums[best][2] += px[2]; counts[best]++;
  }
  centres = centres.map((c, k) => counts[k] ? sums[k].map((v) => Math.round(v / counts[k])) : c);  // new centres
}

On n'échantillonne qu'un pixel sur 7 : pour une photo de 640 × 480, la zone centrale compte environ 110 000 pixels, qui deviennent 15 800 points. Assez pour dessiner les nuages, 7 fois moins de travail. Les cinq centres de départ sont répartis sur la liste (aux positions 10 %, 30 %, 50 %, 70 % et 90 %) : pas de hasard, donc le même résultat à chaque fois pour la même photo.

Trois limites à connaître : (1) k est choisi avant, l'algorithme ne devine pas combien de groupes existent : trop petit, il fusionne le chat et son ombre, trop grand, il coupe le roux en deux. (2) Le résultat dépend des centres de départ : deux départs différents peuvent finir sur deux découpages différents. (3) Il converge toujours, car la somme des distances au carré ne peut que diminuer, mais peut-être vers un découpage médiocre. Le code se contente de 10 tours, largement assez pour une photo.

Ton tour : regarde les nuages bouger

Sous la scène, la « photo » (un chat roux sur un mur gris-bleu, dessiné par le code). Dans la scène, le cube RGB qui tourne. Chaque point est un pixel placé à sa couleur, les grosses sphères sont les centres. Clique sur « Itération suivante » et regarde les centres glisser vers le centre de leur nuage, pendant que les points prennent la couleur de leur centre. Le chat 3D prend la couleur du groupe principal. Essaie ensuite k = 2, puis k = 8, puis « Relancer » avec des centres au hasard, et clique sur la photo pour voir la pipette poser un point blanc dans le cube.

🧊 Démo 3D · pixels, centres et k-means

Ce que tu aurais dû remarquer

Les premières itérations déplacent beaucoup les centres, puis le déplacement total s'effondre jusqu'à 0 : l'algorithme a convergé. Avec k = 2, le roux et le gris-bleu se séparent, mais l'ombre se range d'un côté ou de l'autre. Avec k = 8, un même roux se coupe en nuances. Après plusieurs « Relancer », on tombe parfois sur un découpage un peu différent, signe que le départ compte. Et le chat reste roux tant que le groupe orange domine, malgré le mur gris très présent : on y vient dans un instant.

Du nuage au pelage, et la pipette

Reste à choisir quel groupe est le pelage. Le plus gros n'est pas toujours le bon : un mur gris occupe souvent plus de place que le chat. Alors le Chat Étoile pondère la taille de chaque groupe par sa saturation, c'est-à-dire l'écart entre sa composante la plus forte et la plus faible :

// Grey backgrounds and shadows are common in photos: favour the coloured clusters.
const saturation = ([r, g, b]) => (Math.max(r, g, b) - Math.min(r, g, b)) / (Math.max(r, g, b) || 1);
const clusters = centres.map((c, k) => ({ c, n: counts[k], k })).filter((x) => x.n > samples.length * 0.05)
  .sort((a, b) => b.n * (0.35 + saturation(b.c)) - a.n * (0.35 + saturation(a.c)));

On écarte les groupes de moins de 5 % des points, puis on trie par taille × (0,35 + saturation). Le roux, très saturé, gagne contre un gris plus nombreux. Et pour la pipette, c'est le même geste de moyenne sur un carré, juste après dans le code :

const d = photoCtx.getImageData(Math.max(0, x - 3), Math.max(0, y - 3), 7, 7).data;
const avg = [0, 0, 0];
for (let i = 0; i < d.length; i += 4) { avg[0] += d[i]; avg[1] += d[i + 1]; avg[2] += d[i + 2]; }
card.coat[pickKey] = toHex(avg.map((v) => Math.round(v / (d.length / 4))));

La limite du RGB : la distance dans le cube RGB n'est pas celle que voit l'œil. Deux verts à 30 unités l'un de l'autre peuvent sembler identiques, deux bleus à 30 unités paraître très différents. Des espaces comme Lab sont construits pour que la distance colle à la perception. Pour deviner le pelage d'un chat, le RGB suffit largement.

Règle d'or : avant de calculer une « moyenne », demande-toi si les données forment un seul groupe. Si non, sépare d'abord (k-means), moyenne ensuite. Et quand tu n'as besoin que de savoir qui est le plus proche, compare les carrés.

Astuce : pour vérifier un k-means, regarde le déplacement total des centres à chaque tour, comme dans la démo. Quand il tombe à 0, tu peux t'arrêter, et tu n'as pas besoin de deviner un nombre de tours.

What colour is your cat?

In the "Star Cat" card, you can upload your cat's photo, and the 3D cat takes on its coat. When I wrote that, I felt I was asking the computer "what colour is this cat?", a question a child answers at a glance.

As a former maths teacher, my first reflex was to average all the pixels. It is clean, it is one line. The result: a dull brown that is neither the cat's ginger nor the grey-blue wall behind it. The average of two groups looks like neither of them. I first had to separate the groups, then average each one.

That separation is called k-means, and it rests on a simple idea that changes how you see things: a colour is not a shade, it is a point in space.

A colour is three coordinates

A pixel is three numbers: red, green, blue. Between 0 and 255 in an image, between 0 and 1 in three.js (new THREE.Color(0.88, 0.53, 0.23)). Three numbers make a vector, exactly like the position in lesson 2. Each pixel is a point in a cube whose edges are the r, g and b axes.

In that cube, two similar colours are two close points. And "close" has a definition you already know: the Euclidean distance, Pythagoras in 3D.

// Squared distance between two colours [r, g, b]
const d2 = (a, b) => (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 + (a[2] - b[2]) ** 2;

const orange = [224, 136, 58];
const grey   = [104, 118, 138];
d2(orange, grey);   // 21124, so a distance of about 145

We computed 120² + 18² + 80² = 21124, and its square root, about 145, would be the real distance. In the Star Cat code there is no root, and that is not an oversight.

Comparing squares is enough: the square root is increasing, so if d² (A) < d² (B), then d (A) < d (B). To find the nearest centre to a pixel, comparing squares is enough. Over thousands of pixels and several centres, you save thousands of roots for the same result. The whole cube is at most 255 × √3 ≈ 442 from corner to corner.

The mean is a centre of gravity

In physics, the centre of gravity of several masses is the weighted mean of their positions. It is the same operation here: the mean of several colours is the centre of gravity of their points. Three pixels from a patch of fur, (220, 130, 60), (230, 140, 50) and (222, 138, 64), give (224, 136, 58), a ginger sitting in the middle of the small cloud they form.

That works as long as the points form one cloud. Mix the cat's ginger and the wall's grey-blue in equal parts: the centre of gravity lands at (164, 127, 98), a brown that lies in neither cloud, in the empty space between. That is the trap of my overall average.

The same idea powers the card's eyedropper: when you click on the photo, it does not read a single pixel (too much grain, a lighter hair, a glint) but the mean of a small square of 7 × 7 = 49 pixels around the click.

k-means: finding the clouds

The algorithm fits in four sentences. Pick k starting centres. Assign each pixel to the nearest centre. Move each centre to the centre of gravity of the pixels it just received. And start again with the new centres. Here is the real extract from the Star Cat (guessCoat, slightly shortened):

// samples = [[r, g, b], ...], one pixel out of 7 of the middle of the photo
const samples = [];
for (let i = 0; i < pixels.length; i += 4 * 7) samples.push([pixels[i], pixels[i + 1], pixels[i + 2]]);

// 5 starting centres, spread along the list of samples
let centres = Array.from({ length: 5 }, (_, k) => samples[Math.floor((k + 0.5) / 5 * samples.length)]);

for (let round = 0; round < 10; round++) {
  const sums = centres.map(() => [0, 0, 0]);
  counts = centres.map(() => 0);
  for (const [i, px] of samples.entries()) {
    let best = 0, bestD = Infinity;
    centres.forEach((c, k) => {
      const d = (c[0] - px[0]) ** 2 + (c[1] - px[1]) ** 2 + (c[2] - px[2]) ** 2;
      if (d < bestD) { bestD = d; best = k; }
    });
    owner[i] = best;                                   // assignment
    sums[best][0] += px[0]; sums[best][1] += px[1]; sums[best][2] += px[2]; counts[best]++;
  }
  centres = centres.map((c, k) => counts[k] ? sums[k].map((v) => Math.round(v / counts[k])) : c);  // new centres
}

It only samples one pixel out of 7: for a 640 × 480 photo, the central area holds about 110,000 pixels, which become 15,800 points. Enough to draw the clouds, 7 times less work. The five starting centres are spread along the list (at 10%, 30%, 50%, 70% and 90%): no randomness, so the same photo always gives the same result.

Three limits to know: (1) k is chosen beforehand, the algorithm does not guess how many groups exist: too small and it merges the cat and its shadow, too large and it splits the ginger in two. (2) The result depends on the starting centres: two different starts can end on two different splits. (3) It always converges, since the sum of squared distances can only go down, but maybe towards a mediocre split. The code settles for 10 rounds, plenty for a photo.

Your turn: watch the clouds move

Under the scene, the "photo" (a ginger cat on a grey-blue wall, drawn by the code). In the scene, the rotating RGB cube. Each point is a pixel placed at its colour, the big spheres are the centres. Click "Next iteration" and watch the centres slide towards the middle of their cloud, while the points take their centre's colour. The 3D cat takes the main group's colour. Then try k = 2, then k = 8, then "Restart" with random centres, and click the photo to see the eyedropper drop a white point in the cube.

🧊 3D demo · pixels, centres and k-means

What you should have noticed

The first iterations move the centres a lot, then the total movement collapses to 0: the algorithm has converged. With k = 2, the ginger and the grey-blue separate, but the shadow lands on one side or the other. With k = 8, a single ginger splits into shades. After several "Restart" clicks, you sometimes land on a slightly different split, a sign that the start matters. And the cat stays ginger as long as the orange group dominates, despite the very present grey wall: we get there in a moment.

From cloud to coat, and the eyedropper

We still have to choose which group is the coat. The biggest is not always the right one: a grey wall often takes more room than the cat. So the Star Cat weights each group's size by its saturation, that is the gap between its strongest and weakest component:

// Grey backgrounds and shadows are common in photos: favour the coloured clusters.
const saturation = ([r, g, b]) => (Math.max(r, g, b) - Math.min(r, g, b)) / (Math.max(r, g, b) || 1);
const clusters = centres.map((c, k) => ({ c, n: counts[k], k })).filter((x) => x.n > samples.length * 0.05)
  .sort((a, b) => b.n * (0.35 + saturation(b.c)) - a.n * (0.35 + saturation(a.c)));

Groups under 5% of the points are dropped, then the rest is sorted by size × (0.35 + saturation). The highly saturated ginger beats a more numerous grey. And for the eyedropper, it is the same averaging gesture on a square, right after in the code:

const d = photoCtx.getImageData(Math.max(0, x - 3), Math.max(0, y - 3), 7, 7).data;
const avg = [0, 0, 0];
for (let i = 0; i < d.length; i += 4) { avg[0] += d[i]; avg[1] += d[i + 1]; avg[2] += d[i + 2]; }
card.coat[pickKey] = toHex(avg.map((v) => Math.round(v / (d.length / 4))));

The limit of RGB: distance in the RGB cube is not what the eye sees. Two greens 30 units apart can look identical, two blues 30 units apart can look very different. Spaces like Lab are built so that distance matches perception. To guess a cat's coat, RGB is plenty.

Golden rule: before computing an "average", ask whether the data forms a single group. If not, separate first (k-means), average afterwards. And when you only need to know who is nearest, compare squares.

Tip: to check a k-means, watch the total centre movement at each round, as in the demo. When it drops to 0 you can stop, and you do not have to guess a number of rounds.

Prochaine étape

Tu as maintenant tous les outils : repère, vecteurs, matrices, sinus, physique, lumière et couleur. Il reste à les voir travailler ensemble. Les deux scènes complètes du Labo, le Chat Étoile et Feu & Glace, sont là pour ça.

Voir le Labo 3D →