Recherche par similarité de couleur : cube, GiST et un convertisseur Lab fait main

Il fallait donc un espace de couleur où "distance numérique" et "différence perçue" coïncident à peu près, et un moyen de faire cette recherche sur un catalogue de plusieurs milliers d'items sans recalculer la distance de chacun à chaque requête.

Pourquoi Lab et pas RGB

L'espace CIE L*a*b* a été construit précisément pour ça, avec une échelle pensée pour que la distance euclidienne entre deux points corresponde approximativement à la différence perçue entre deux couleurs :

Ça change tout côté implémentation : si on stocke le Lab de chaque couleur, "trouve la couleur perceptuellement la plus proche" devient un problème de plus proche voisin dans un espace euclidien à trois dimensions, un problème que les bases de données géométriques savent résoudre efficacement.

Le pipeline de conversion

Convertir un hex en Lab n'est pas une formule à un coup, c'est une chaîne de trois transformations :

Voici la partie centrale, écrite à la main dans l'ETL qui alimente le catalogue :

const D65 = { Xn: 95.047, Yn: 100.0, Zn: 108.883 }; 
 
function srgbToLinear(c: number): number {
  return c <= 0.04045 ? c / 12.92 : ((c + 0.055) / 1.055) ** 2.4;
}
 
function fxyz(t: number): number {
  return t > 216 / 24389 ? Math.cbrt(t) : (24389 / 27 * t + 16) / 116;
}
 
export function hexToLab(hex: string): [number, number, number] {
  const r8 = parseInt(hex.slice(0, 2), 16);
  const g8 = parseInt(hex.slice(2, 4), 16);
  const b8 = parseInt(hex.slice(4, 6), 16);
 
  const r = srgbToLinear(r8 / 255);
  const g = srgbToLinear(g8 / 255);
  const b = srgbToLinear(b8 / 255);
 
  // sRGB linéaire → XYZ (D65). Matrice tirée de IEC 61966-2-1.
  const X = (r * 0.4124564 + g * 0.3575761 + b * 0.1804375) * 100;
  const Y = (r * 0.2126729 + g * 0.7151522 + b * 0.0721750) * 100;
  const Z = (r * 0.0193339 + g * 0.1191920 + b * 0.9503041) * 100;
 
  const fx = fxyz(X / D65.Xn);
  const fy = fxyz(Y / D65.Yn);
  const fz = fxyz(Z / D65.Zn);
 
  const L = 116 * fy - 16;
  const a = 500 * (fx - fy);
  const bb = 200 * (fy - fz);
  return [L, a, bb];
}

Concrètement, un hex à six caractères se découpe en trois octets, un par canal :

Ce n'est pas de la magie mathématique, juste une suite d'étapes bien connues et documentées depuis des décennies (la matrice de passage RGB linéaire vers XYZ vient directement de la norme IEC 61966-2-1). L'important est de l'implémenter une seule fois, correctement, avec un test de non-régression, plutôt que d'invoquer une dépendance externe pour trois multiplications matricielles¹.

1. Le même fichier existe à l'identique côté application web, avec un commentaire qui dit explicitement pourquoi : les deux implémentations doivent produire des valeurs alignées avec ce qui a été précalculé et stocké en base. ↩

Précalculer plutôt que recalculer

À la place, le calcul se fait une seule fois, à l'ingestion. L'ETL convertit chaque hex en Lab et l'insère directement sous forme de type cube (l'extension PostgreSQL du même nom, pensée pour des points dans un espace à N dimensions) :

CREATE EXTENSION IF NOT EXISTS cube;
 
CREATE TABLE skinator_item_colors (
  item_id   INTEGER   NOT NULL REFERENCES skinator_items(id) ON DELETE CASCADE,
  position  SMALLINT  NOT NULL,
  hex       CHAR(6)   NOT NULL,
  lab       CUBE      NOT NULL,
  PRIMARY KEY (item_id, position)
);
 
CREATE INDEX idx_skinator_item_colors_lab_gist
  ON skinator_item_colors USING GIST (lab); 

Et l'insertion elle-même construit le cube directement depuis les trois composantes Lab calculées côté ETL :

INSERT INTO skinator_item_colors(item_id, position, hex, lab)
VALUES ($1, $2, $3, cube(ARRAY[$4::float8, $5::float8, $6::float8])) 

Le travail lourd (la chaîne de conversion sRGB vers XYZ vers Lab) est fait une fois par couleur, hors du chemin critique, pas une fois par requête utilisateur.

Le choix d'index : cube et GiST

Stocker du Lab dans une colonne ne suffit pas à rendre la recherche rapide, il faut aussi que la base puisse chercher "les points les plus proches d'un point donné" sans parcourir toute la table. C'est exactement ce que fait l'index GiST (Generalized Search Tree) sur une colonne cube : il organise les points dans une structure arborescente qui permet d'élaguer la recherche géométriquement, comme un R-tree le ferait pour des coordonnées géographiques.

Une fois cet index en place, PostgreSQL expose un opérateur de distance, <->, entre deux cubes. Voici la requête qui l'utilise, en sous-requête corrélée pour prendre la couleur dominante la plus proche parmi les swatches d'un item :

applyColorOrdering(query: Query, lab: [number, number, number]): Query {
  const [l, a, b] = lab;
  return query
    .select('skinator_items.*')
    .select(
      db.raw(
        `(
          SELECT MIN(c.lab <-> cube(ARRAY[?::float8, ?::float8, ?::float8]))
            FROM skinator_item_colors c
           WHERE c.item_id = skinator_items.id
        ) AS delta`,
        [l, a, b],
      ),
    )
    .orderByRaw('delta ASC NULLS LAST') 
    .orderBy('id', 'desc');
}

Pour chaque item, la sous-requête calcule la distance minimale entre ses couleurs et la couleur cible, et le tri se fait sur cette colonne calculée.

La leçon : indexer la bonne chose