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

Il fallait donc un modèle de couleur où "distance numérique" et "différence perçue" coïncident à peu près, et un moyen de faire cette recherche directement dans PostgreSQL, sur une table de plusieurs milliers d'éléments, sans recalculer la distance de chaque item à chaque appel.

La solution tient en trois briques : convertir chaque couleur en Lab, la stocker dans une colonne de type cube, et laisser un arbre GiST trouver les plus proches voisins. On va voir qu'il y a un piège dans la dernière. Mais avant d'y venir, un détour utile : "recherche par similarité" ne désigne pas du tout la même chose selon la donnée qu'on manipule.

Recherche par similarité dans PostgreSQL : quel outil pour quelle donnée ?

PostgreSQL propose plusieurs extensions pour la similarity search, et les fonctionnalités de chacune répondent à un problème précis. Le tableau ci-dessous les résume :

Les trigrammes découpent le contenu d'une colonne text en séquences de trois caractères et mesurent la proportion qu'ils partagent : parfait pour retrouver un mot mal orthographié, par exemple dans les noms d'items, mais inutile pour comparer des teintes. Ils fonctionnent mieux sur des colonnes courtes, quelques mots tout au plus, et un index GIN de trigrammes les rend rapides sur de gros volumes. La fonction word_similarity() va plus loin en cherchant le mot le plus proche à l'intérieur d'une phrase. La recherche plein texte avec tsvector, elle, découpe les mots d'un document et normalise chaque mot (racinisation, mots vides, configuration french pour le français) : c'est l'outil du texte, pas des nombres, et une colonne tsvector précalculée évite de refaire ce découpage à chaque recherche. Par exemple :

CREATE TABLE items (id SERIAL PRIMARY KEY, name TEXT NOT NULL, description TEXT);
CREATE TABLE documents (id SERIAL PRIMARY KEY, body TEXT, embedding vector(1536));
 
-- Trigrammes : l'opérateur % filtre, la fonction similarity() donne un score
SELECT name, similarity(name, 'Wakfou') AS score
  FROM items
 WHERE name % 'Wakfou';
 
-- Un mot proche à l'intérieur d'un texte plus long
SELECT name FROM items WHERE word_similarity('cape', name) > 0.6;
 
-- Plein texte en français
SELECT id FROM documents
 WHERE to_tsvector('french', body) @@ to_tsquery('french', 'couleur & recherche');

Le cas de pgvector est plus intéressant, parce qu'une couleur en Lab est, après tout, un vecteur de trois nombres. Mais pgvector est pensé pour les embeddings produits par un modèle d'IA, des vecteurs de plusieurs centaines ou milliers de dimensions, avec des index approximatifs (HNSW, IVFFlat) qui sacrifient un peu de précision pour tenir à cette échelle. Pour trois dimensions, l'extension cube suffit largement : elle est livrée avec PostgreSQL dans les modules contrib, gère des points jusqu'à 100 dimensions par défaut, et sa recherche GiST est exacte¹.

1. Un projet qui a déjà pgvector pour ses embeddings pourrait tout aussi bien utiliser une colonne vector(3) pour les couleurs. Ici, cube évite simplement d'ajouter une dépendance externe au serveur. ↩

Pourquoi Lab et pas RGB

L'espace CIE L*a*b* est le modèle de couleur de référence en colorimétrie. Il 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 :

Pour donner un ordre de grandeur, un ΔE autour de 2,3 est souvent cité comme le seuil d'une différence tout juste perceptible, et au-delà d'une dizaine, l'écart saute aux yeux. Il existe des formules plus fidèles, comme CIE94 ou CIEDE2000, mais elles ne sont plus des distances euclidiennes : aucune structure géométrique ne peut les exploiter directement. CIE76 garde la propriété qui compte ici.

Ç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 hex vers Lab

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

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

Chaque paire hexadécimale est lue comme un nombre en base 16, ramenée entre 0 et 1, puis passe dans la chaîne de conversion. Le blanc de référence n'est pas un détail : en changer décale toutes les valeurs Lab obtenues. Voici la fonction 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];
}

Ce n'est pas de la magie mathématique, juste une suite d'étapes 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'ajouter une dépendance 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 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); 

La table tient en quatre colonnes : l'item, la position de la couleur dans sa palette, le hex d'origine et le point Lab. L'insertion en SQL appelle la fonction cube() avec un tableau de trois éléments, les composantes L, a et b calculées côté ETL. C'est le seul endroit où le modèle Lab entre dans la base. Quand un item est réimporté, le plus sûr est de remplacer toutes ses couleurs dans une seule transaction : les transactions PostgreSQL étant isolées, une recherche concurrente lit soit l'ancien état, soit le nouveau, jamais un item à moitié mis à jour.

BEGIN;
 
DELETE FROM skinator_item_colors WHERE item_id = $1;
 
INSERT INTO skinator_item_colors (item_id, position, hex, lab)
VALUES ($1, $2, $3, cube(ARRAY[$4::float8, $5::float8, $6::float8])); 
-- … une ligne par couleur de l'item
 
COMMIT;

Le travail lourd, la conversion sRGB vers XYZ vers Lab, est fait une fois par couleur, hors du chemin critique, et pas une fois par requête utilisateur.

Cube et GiST : chercher sans tout parcourir

Stocker du Lab dans une colonne ne suffit pas à rendre la recherche rapide : il faut aussi que la base puisse trouver "les points les plus proches d'un point donné" sans parcourir toute la table. C'est ce que permet un 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.

L'extension expose trois opérateurs de distance entre cubes : <-> pour la distance euclidienne (notre ΔE CIE76), <#> pour la distance de Manhattan et <=> pour la distance de Tchebychev. C'est le premier opérateur qui nous intéresse. Mais il y a un piège : GiST ne sait accélérer qu'une seule forme de requête.

Le piège de la sous-requête corrélée

La première idée est d'ajouter à chaque item une colonne calculée, la distance minimale entre ses couleurs et la cible, puis de trier dessus :

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');
}

Le résultat est correct, mais EXPLAIN ANALYZE sur le SQL généré montre que GiST n'est jamais sollicité : PostgreSQL parcourt tous les items, retrouve leurs couleurs par la clé primaire, calcule le MIN pour chacun, puis trie l'ensemble. On retombe sur un O(n) à chaque appel, simplement déplacé de l'application vers le SGBD.

La version qui exploite vraiment GiST

Le parcours de plus proche voisin (KNN) de GiST ne s'active que lorsque le tri porte directement sur la table indexée, par colonne <-> valeur constante, avec un LIMIT. Rien de plus en SQL, mais la forme compte. On cherche donc d'abord les couleurs les plus proches, puis on remonte aux items :

WITH plus_proches AS (
  SELECT c.item_id,
         c.lab <-> cube(ARRAY[$1::float8, $2::float8, $3::float8]) AS delta
    FROM skinator_item_colors c
   ORDER BY c.lab <-> cube(ARRAY[$1::float8, $2::float8, $3::float8]) 
   LIMIT 500
)
SELECT i.*,
       MIN(p.delta) AS delta,
       CASE
         WHEN MIN(p.delta) < 2.3 THEN 'quasi identique'
         WHEN MIN(p.delta) < 10  THEN 'proche'
         ELSE 'éloignée'
       END AS proximite
  FROM plus_proches p
  JOIN skinator_items i ON i.id = p.item_id
 GROUP BY i.id
 ORDER BY delta ASC, i.id DESC
 LIMIT 50;

La couleur cible arrive sous forme de tableau ARRAY[l, a, b], transformé en cube à la volée : c'est une constante pour la requête, donc GiST peut s'en servir comme point de départ. Le LIMIT de la CTE doit rester confortablement au-dessus du nombre d'items voulus multiplié par le nombre de couleurs par item, puisqu'un même item peut apparaître plusieurs fois parmi les candidats. Le CASE final est un simple bonus : il permet d'afficher une étiquette lisible plutôt qu'une valeur brute de ΔE.

La leçon : indexer la bonne chose, et sous la bonne forme