Perceptual Colour Quantization: Why Naive RGB Distance Fails

Yes, this one started as a Minecraft project. Stay with me — the game turned out to be a good excuse to spend a weekend on a problem that lives almost everywhere: how do you match a colour to the nearest colour, when "nearest" has to mean what the human eye sees, not what the maths says?

Minecraft maps render from a fixed palette of around 50 colours. A photograph has millions. To show a photo in-game you have to collapse those millions down onto the palette, and the quality of the result lives or dies on how you define "closest". The file format at the end is incidental plumbing. The interesting engineering is all in that one word.

The naive answer, and why it's wrong

Reach for the obvious approach first: treat each colour as a point in RGB space, measure the Euclidean distance to every palette colour, pick the smallest. It works, in the narrow sense that it runs and produces output. It also looks bad.

The problem is that RGB distance and perceived distance aren't the same thing. Two colours can sit close together in RGB and still look obviously different to a person — and the reverse happens just as often. Your eyes aren't a uniform ruler across the spectrum; they're far more sensitive to green than to blue, a quirk of how the cone cells are distributed. Straight Euclidean distance treats every channel as equal, so it confidently picks "nearest" colours that your eye reads as plainly wrong.

The fix is to weight the distance by how we actually see — heaviest on green, and biasing red and blue by the average red level:

$$ d = \sqrt{\left(2 + \frac{\bar{r}}{256}\right) \Delta R^2 + 4 \cdot \Delta G^2 + \left(2 + \frac{255 - \bar{r}}{256}\right) \Delta B^2} $$

This isn't colorimetrically pure. If you want pure, you convert into a perceptual colour space like CIELAB and compute ΔE properly — and for a colour-critical pipeline that's the right answer. But this weighting is cheap, runs per pixel with no colour-space conversion, and the output is night-and-day better than raw RGB. For map art, "approximate perceptual weighting, fast" beat "technically correct, slower" without much of a contest. Knowing which of those you actually need is most of the skill.

One wrinkle: the target palette has grown across game versions, so the lookup isn't one fixed table — it's keyed by version, so the same photo renders correctly regardless of which one someone's playing. A small thing, but it's the difference between "works on my machine" and "works for the person actually playing".

Then you serialise the grid of palette indices into the game's binary map format — a tagged, gzip-compressed structure. This is where I lost the most time to the least interesting problem. The game doesn't validate your file and tell you what's wrong — malformed data just silently fails to load. No error, no map, no clue. A few rounds of that and you develop a deep, personal respect for a format's byte layout.

Processing the pixels

The mechanical part is unglamorous: decode the image, resize to map dimensions (128×128 for a single map), pull the raw pixel buffer, walk every pixel through the quantizer, hand the result to serialisation. A raw buffer is just a flat array of channel values, so grabbing a pixel is index arithmetic:

$$ \text{index} = (y \times \text{width} + x) \times \text{channels} $$

Pull the R, G, B, run the match, move on. Two things are worth knowing here regardless of your tools. First, per-pixel work is CPU-bound, so an image library backed by native code earns its place the moment you might process large uploads — a naive high-level loop over millions of pixels is exactly the wrong hot path. Second, it's easy to leave intermediate copies of the image lying around between transforms; a little profiling to find the buffers you never needed pays for itself quickly.

Structuring the service

The service splits along responsibilities: the domain (colour matching, the map model), the use case ("convert this image"), the I/O edges (image decoding, storage), and the transport (the HTTP surface). For something this small that's arguably more structure than it needs — and I'd push back on anyone applying it by reflex to every tiny service. Here it earned its keep in two concrete ways.

First, testability: the quantization logic tests in isolation, with no image decoding or HTTP anywhere near it. Second, extensibility: adding a second output format — a schematic for building the map block-by-block in-game — touched only the edges, and the core logic didn't move at all. That's the test of a boundary: when requirements change, does the blast radius stay small?

One habit worth stealing regardless of stack: describe each endpoint with a schema and validate against it automatically. The schema becomes the request contract and the documentation in the same place, instead of validation being something you hope you remembered to write.

Storing results

Converted files go to object storage, and users get a download link that expires after a set time. That keeps the service stateless — no files to babysit on the server, no cleanup job for abandoned conversions. Worth knowing when you serve downloads rather than just store them: object-storage egress pricing dominates the bill, so it's a line item to check before you're surprised by it, not after.

The takeaway

The colour science was the genuinely interesting part. I went in assuming colour matching was a solved, boring problem and came out with a real feel for colour spaces, perceptual distance, and why sRGB isn't as straightforward as it looks.

And the principle travels well beyond a game: whenever you approximate a continuous space with a discrete one — colours, audio, embeddings, any lossy mapping — the metric you optimise against has to model the consumer, not just the data. Naive Euclidean distance is almost always the wrong default. It's just usually wrong in ways less visible than a photo that came out looking like someone spilled the wrong paint.