A phone photo can contain millions of distinct colors. A skein of embroidery floss comes in one. And the world's most common thread brand, DMC, sells only around 500 colors total. Turning a photo into a stitchable cross-stitch pattern is therefore not an image-resizing problem - it is a color-replacement problem with a hard physical constraint: every pixel in the final chart has to name a thread you can actually buy.
I build Threaded, a browser-based cross-stitch and needlepoint pattern maker, and these constraints shaped every interesting decision in it. Here is how the color science works, and where the naive approach breaks.
Stop measuring distance in RGB
The obvious way to match a pixel to a thread is Euclidean distance in RGB space. It fails immediately, because RGB is not perceptually uniform. Two greens that are 40 RGB units apart can look identical to a human; two dark blues 40 units apart look clearly different. If you quantize in RGB, skin tones drift, shadows get muddy, and the stitched result looks wrong even though the math minimized "distance."
The standard fix is to convert to CIELAB (Lab), a color space designed so that one unit of distance roughly equals one unit of perceived difference. The pipeline is:
- Linearize sRGB. Each channel is gamma-encoded; undo it (the piecewise sRGB transfer function, roughly pow 2.2).
- Convert to XYZ with the standard sRGB matrix, D65 white point.
- Convert XYZ to Lab, which separates lightness (L) from the green-red (a) and blue-yellow (b) opponent axes.
Now distance means something a stitcher's eye agrees with.
Delta E: 1976 vs 2000
Once in Lab, the simple Euclidean formula (CIE76) is already usable, but it still misjudges saturated colors. The modern answer is CIEDE2000, which adds compensation terms for lightness, chroma, and hue, plus a rotation term that fixes blue-region weirdness. The formula is ugly - around 15 intermediate values - but it is a pure function of two Lab triples, so caching makes it cheap enough for per-pixel work.
Whichever distance function a converter uses, one optimization is universal: precompute the converted value of every thread in every supported library once, offline. Thread colors are fixed data. In Threaded's case, the thread libraries (49 of them, including DMC, Anchor, and Madeira) ship to the browser as static data - at runtime, only the photo's pixels need converting.
Palette reduction is nearest-neighbor search
After conversion, every pixel needs its closest thread. With 500 threads and a 512 x 512 pattern, that is on the order of 130 million distance computations - the kind of thing k-d trees were invented for, though a tight typed-array loop with precomputed values goes a long way too.
The subtler problem is that you do not want 500 threads in one pattern. Stitchers buy floss by the skein, so the palette must shrink to something like 10-40 colors. Two classic options:
- Median cut: fast, deterministic, but loves splitting large color regions into near-identical halves while rare-but-important colors (the red of a cardinal) get merged away.
- K-means in Lab space: better perceptual clusters, but nondeterministic unless seeded, and it happily invents cluster centers that correspond to no real thread.
A practical trick either way: after clustering, snap every cluster center to the nearest real thread. You get perceptually sensible groups and a bill of materials that exists in the real world.
The constraint nobody expects: stitchability
Here is where photo-to-pattern conversion diverges from image compression. Floyd-Steinberg dithering would make the on-screen preview look great. It also produces "confetti": isolated single stitches of one color surrounded by another. Confetti is miserable to stitch - constant thread changes, messy backs, wasted floss. So a pattern maker has to optimize for something image algorithms ignore: region contiguity.
This is enough of a real problem that Threaded ships a dedicated Confetti Remover tool for brushing away isolated off-color stitches after generation, on top of keeping palettes small by default. A slightly less accurate chart with clean shapes stitches beautifully; an accurate one full of confetti gets abandoned in a drawer.
The histogram is the shopping list
Once every cell owns a thread ID, the materials list is just a histogram. Stitch counts per color, divided by the stitches a skein supports at the chosen fabric count, give skein quantities. This is also why the color pipeline has to be deterministic end-to-end: if the chart and the shopping list ever disagreed, someone would run out of floss mid-project.
Putting it together
Threaded (https://threaded.diy) runs the whole flow in the browser with nothing to install: upload a photo, choose a canvas size and thread library, and you get a gridded chart with symbols, a manageable palette matched to real floss, exact stitch and skein counts, and a print-ready PDF. The free plan covers the full editor with one saved design, no account required.
The part I find satisfying is that none of the steps is individually exotic. The craft is in respecting the constraint that the output is not an image. It is a set of instructions a person will spend forty hours executing with a needle - and every "good enough" color decision ships in physical form.
Top comments (0)