Turning a photo into a cross stitch chart: picking threads with CIEDE2000

A cross stitch chart looks like a pixel art problem. Shrink the photo, reduce the palette, done. Then you stitch it, and the sky has a stripe of grey-green nobody asked for.

I built a browser tool that turns photos into charts, and most of the interesting work was in one question: which threads should this picture use? Unlike a normal palette, you can't invent colours. DMC stranded cotton has 489 of them, and every colour you choose is another skein to buy and another thread change.

Why RGB distance gets it wrong

The obvious way to match a pixel to a thread is Euclidean distance in RGB. It's cheap and it's wrong in a visible way, because equal steps in RGB aren't equal steps to the eye. Two dark greens can be numerically far apart and look the same, while two pale skin tones can be numerically close and look different.

So every colour goes through the same pipeline first:

1. sRGB bytes to linear light (undo the gamma curve).
2. Linear RGB to CIELAB, with a D65 white point.
3. Compare in Lab with CIEDE2000.

CIEDE2000 is long, with corrections for lightness, chroma and the awkward blue region, so I wouldn't write it from memory. The paper by Sharma, Wu and Dalal (2005) publishes test pairs, and those belong in your unit tests.

Speed matters too. A large chart can have hundreds of thousands of pixels, so the hot paths write Lab values into a typed array rather than allocating an object per pixel:

export function rgbToLabInto(r: number, g: number, b: number, out: Float32Array | Float64Array, o: number): void { linearToLabInto(SRGB_TO_LINEAR[r], SRGB_TO_LINEAR[g], SRGB_TO_LINEAR[b], out, o); } 

SRGB_TO_LINEAR is a 256-entry lookup table, so the gamma step costs one array read.

Choosing the threads: greedy, from a fixed list

Quantisation methods such as k-means produce colours that don't exist as thread. You can snap them to DMC afterwards, but two clusters may land on the same skein, and you end up with fewer colours than you asked for.

Working from the fixed list avoids that. The tool adds one thread at a time, always the one that brings the pattern closest to the photo, until it reaches the requested count. Simplified, the idea is:

// Simplified sketch, not the production loop. function pickThreads(pixels: Lab[], threads: Thread[], count: number): Thread[] { const chosen: Thread[] = []; while (chosen.length < count) { let best = threads[0]; let bestError = Infinity; for (const thread of threads) { const error = totalError(pixels, [...chosen, thread]); if (error < bestError) { bestError = error; best = thread; } } chosen.push(best); } return chosen; } 

Each stitch then takes the closest of the chosen threads. A side effect I liked is that the choices are nested: the first 12 threads of a 30-colour run are a sensible 12-colour palette. That makes it natural to show versions with 12, 20 and 30 colours side by side and highlight the fewest that stay close to the image.

The bit nobody warns you about: buying the thread

A chart isn't finished until you know how much floss to buy. Stitches per skein depends on the cloth, because a coarser cloth uses more thread per stitch. With 2 strands, the tool assumes:

Isolated stitches waste more thread, because you travel to them and tie off. A stitch with fewer than three same-colour neighbours (out of eight) counts as scattered and costs 1.5 times as much. To keep the maths exact, the code works in half-stitch units:

const units = 2 * solid + 3 * scattered; return Math.max(1, Math.ceil((units * strands) / (4 * STITCHES_PER_SKEIN[fabric]))); 

So 3,000 solid stitches on 14-count with 2 strands gives 6000 × 2 / (4 × 1500) = 2 skeins. These are estimates, since real usage varies with tension and how you travel, which is why the result always rounds up.

What I'd tell someone starting this

• Convert to Lab first, and test CIEDE2000 against the published pairs.
• Treat the thread list as the palette, rather than snapping to it at the end.
• Let people compare colour counts. "How many colours?" is a budget question as much as a quality one.

If you want to see the steps from the stitcher's side, from cropping to the printed chart, here's the step-by-step guide. Everything runs in the browser, so the photo never leaves the device.

This post was written with AI assistance.