R&D LAB Design computationnel Livré Instrument d'image
Tessera-Mosaic
Une image entre, une planche à peindre sort
Toute image est décomposée en aplats, chaque région reçoit un numéro, et il en sort une planche vectorielle imprimable avec légende, sans que l'image quitte l'onglet.
- 96couleurs au plus, libre à partir de 12
- 12étapes dans la chaîne
- 0,8 stemps de calcul le plus long de cette page
- 0requêtes réseau
La planche imprimable, ici sur l'image d'exemple dessinée par l'application au démarrage, sans aucun fichier : 46 régions, 25 couleurs. Contours en trait fin, un chiffre dans chaque région, et dessous la légende avec pastille, numéro, nom de couleur le plus proche, valeur hex et part de surface.
Pourquoi c'est publié
Le passage d'une image à un objet que quelqu'un tient réellement n'est pas un filtre : c'est une chaîne de décisions sous contraintes : segmenter, fusionner, simplifier, étiqueter. Tessera-Mosaic prouve que nous construisons une telle chaîne et la vérifions contre ses propres contraintes, au lieu de montrer une image à la fin et d'espérer.
Une planche à peindre par numéros ressemble à un filtre et n'en est pas un. Le numéro dans une région suppose que la région est assez grande pour être peinte, pas si fine qu'un pinceau n'y entre pas, qu'elle a un endroit où le chiffre tient entier, et que la couleur voisine se distingue des autres. Tessera-Mosaic est la chaîne d'étapes qui satisfait ces quatre conditions à la fois, et trois vues qui vous permettent de juger le résultat avant d'acheter la peinture.
Une photographie n'a pas de régions
Elle a des dégradés, du bruit et des bords qui ne commencent nulle part précisément. Une planche à peindre demande l'inverse : des régions fermées, chacune assez grande pour un pinceau, chacune d'une couleur que l'on peut acheter et retrouver. Entre les deux il n'y a pas un réglage, il y a une chaîne.
Quatre conditions doivent tenir en même temps, sans quoi la planche est inutilisable. Une région a besoin d'assez de surface. Elle ne doit pas être si étroite qu'aucun pinceau n'y entre. Il lui faut un endroit où le chiffre tient entier. Et sa couleur doit rester distincte de ses voisines. Chaque condition prise seule est facile, ensemble elles sont le problème.
La planche ci-contre est calculée à partir d'une photographie de paysage du domaine public, 914 x 1280 pixels, ramenée à 714 x 1000 pixels de travail. Il en sort 239 régions en 24 couleurs, 10,9 m de contour, 0,8 s de calcul. Le pied de page nomme chacun de ces nombres avant toute impression.
Toute la chaîne tourne dans un worker
Douze étapes, lues en six temps
- 01 Vers un espace où la distance signifie quelque chose Le sRGB passe en CIELAB. C'est là seulement qu'un petit écart entre deux couleurs signifie aussi qu'un oeil les sépare mal, et là seulement que l'avertissement de palette est un vrai nombre et non une impression.
- 02 Le bruit part, les bords restent Un filtre bilatéral séparable de rayon 0 à 4 lisse les surfaces et laisse les bords en place, pour que l'étape suivante ne promeuve pas le grain au rang de couleur.
- 03 Calculer la palette k-moyennes pondéré en Lab, amorçage k-means++, 32 itérations de Lloyd, et deux germes ancrés aux 1er et 99e percentiles de clarté pour que lumière et ombre ne se moyennent pas. L'affectation est exacte et sans tramage : un tramage ici ne serait pas un effet, ce serait une région impossible à peindre.
- 04 Les pixels deviennent des régions Un filtre majoritaire trois par trois élimine le mouchetis, puis les composantes 4-connexes sont étiquetées. À partir de là, la chaîne ne travaille plus des couleurs mais des surfaces.
- 05 Fusionner ce qui est trop petit ou trop fin Union-find jusqu'au point fixe, avec la carte de distance recalculée entre les passes. Trop fin est la condition que la plupart des outils ratent : une longue bande étroite passe tous les tests de surface et n'accueille pourtant aucun pinceau.
- 06 Bord, contour, chiffre Les bords sont construits en arêtes et chaînes, chaque chaîne lissée une fois (Douglas-Peucker, Chaikin, Douglas-Peucker), les contours assemblés, les couleurs renumérotées par surface peinte, et alors seulement les chiffres sont posés.
La chaîne construit une mosaïque
La seule décision
Un nombre flottant décidait si une image était peignable
Trois des cinq paliers de palette n'ont longtemps pas livré ce qu'annonçait leur nom. Rich 40, Deep 56 et Full 72 rendaient une poignée de régions et une fraction des couleurs demandées, et d'autant plus mal qu'on en demandait davantage. La planche qui donnait 24 couleurs et 574 régions en Medium revenait en Deep avec 8 couleurs et 9 régions.
La cause tenait en une ligne de la fusion. Le tableau qui porte l'épaisseur de chaque région est un Float32Array, le rayon minimal auquel on la compare est un double. Quand une région absorbait une voisine, l'épaisseur de l'union était inconnue, alors le code y écrivait le rayon minimal, comme une affirmation : cette région compte désormais comme peignable. Un double rangé dans un Float32Array est arrondi, et environ la moitié des valeurs s'arrondit vers le bas.
Quand elle s'arrondissait vers le bas, l'union restait trop fine selon son propre test. Elle absorbait donc encore, et encore, jusqu'à ce qu'il ne reste que quelques dizaines de paquets. Le sens de l'arrondi dépend de la valeur exacte du rayon minimal, laquelle dérive de la taille de palette et du format de papier : elle diffère pour chaque combinaison. La valeur de Medium s'arrondissait vers le haut et fonctionnait. Rich, Deep et Full partageaient une valeur qui s'arrondissait vers le bas.
La preuve était d'une clarté déplaisante : une variation de quatre millionièmes du rayon minimal faisait basculer la même planche entre 574 et 79 régions, et comparer la valeur à son propre arrondi Float32 prédisait la branche obtenue sur douze échantillons sur douze.
La décision a été non pas de réparer la comparaison mais de la supprimer. L'affirmation est aujourd'hui un indicateur distinct porté par la région, le tableau d'épaisseur garde le maximum honnête, et une région déjà fusionnée saute le test de finesse. Plus aucun nombre flottant n'en décide. Depuis, chaque palier livre exactement sa palette sans le moindre nouvel essai : Rich 40 avec 633 régions, Deep 56 avec 618, Full 72 avec 874. Une planche tirée de cette image demande en contrepartie 1,0 à 2,2 s au lieu de 0,6 à 1,0 s, parce que bien plus de régions survivent.
Un nombre posé comme une affirmation était relu comme une mesure.
Ce que 24 couleurs font d'une photographie
Cette vue existe pour une seule question : la palette tient-elle, avant d'être achetée. Ce sont les mêmes 239 régions et 24 couleurs que la planche plus haut, sans les chiffres ni les traits fins.
Chaque entrée de palette connaît sa distance à sa plus proche voisine. Ce seul nombre pilote l'affichage sous le curseur, la nouvelle tentative et le refus lorsqu'une image ne porte pas les couleurs demandées. Ici 5,9 dE séparent la paire la plus proche, et la même photographie porte aussi les 72 couleurs, alors avec 3,7 dE. Un graphique vectoriel plat, lui, sature autour de 50 à 60 couleurs et le dit.
Ce qui entre, ce qui sort
La photographie
- 914 x 1280 pixels, ramenés à 714 x 1000 pour le calcul.
- Des millions de valeurs de couleur, aucune nommée.
- Des dégradés sans bord : où s'arrête le feuillage est une affaire de seuil.
- Aucun plus petit détail. Une branche peut faire un pixel de large.
- Rien n'y dit combien de temps il faudrait pour la peindre.
La planche
- 239 régions fermées, exactement un chiffre dans chacune.
- 24 couleurs, chacune avec pastille, nom le plus proche, valeur hex et part de surface.
- Chaque région au moins 2,4 mm de large sur A4, sinon elle a été fusionnée.
- 10,9 m de contour, 0,8 s de calcul, environ 32 minutes à la main.
- Une page A4 en vectoriel, sans une seule référence externe.
Le même cadrage, deux palettes
Moins de couleurs ne veut pas dire moins de régions
15 couleurs273 régions, paire la plus proche à 7,9 dE, environ 36 minutes à la main. C'est plus de régions qu'à 24 couleurs, et non moins : une palette grossière effiloche la frontière entre feuillage et ciel au lieu de la simplifier.
72 couleurs782 régions, paire la plus proche à 3,7 dE, environ 1 heure 44 à la main. La photographie porte les 72, et l'application affiche ce nombre au lieu de le taire.
Les deux autres vues
Où cela s'applique
- Tout ce qui doit traduire une image en objet fabricable : découpe, appliqué, marqueterie, carrelage, vinyle.
- Les produits où un client dépose sa propre photographie et attend un résultat physique réellement réalisable.
- Tout problème dont la contrainte est une taille minimale et une largeur minimale, et pas seulement un nombre de couleurs.
- Les outils qui, pour des raisons de protection des données, ne peuvent rien téléverser et doivent tourner dans un navigateur.
Crédits : chaque capture montre notre propre application. Cinq d'entre elles montrent un résultat calculé à partir d'une photographie du domaine public : Limestone quarry landscape par Rosendahl, via Wikimedia Commons. Les autres utilisent l'image d'exemple dessinée par l'application elle-même.
Pourquoi c'est publié
Ce que cela signifie pour votre projet
Plus du laboratoire
Méthode Event Scout Un modèle de langage lit les pages d'événements, tout le reste est du code fixe. Il reste une courte liste des journées qui valent le déplacement. 
Recherche appliquée Vellum Bords, perspective, lumière et texte sont calculés sur le téléphone. Un document ne quitte l'appareil que lorsque quelqu'un l'envoie. 
Design computationnel Atlas EV1 Douze chapitres démontent une voiture électrique, jusqu'à une cellule. Aucun fichier de modèle, aucune texture : 327 pièces issues d'un tableau. Besoin de transformer une image en objet fabricable, sous contraintes réelles ? C'est notre genre de problème.
Nous contacter