Client-Side Color Quantization: Euclidean Distance in RGB Space

1. The Scale of the Problem

Color quantization sounds simple until you try to do it on a large image in a browser.

A normal 24-bit sRGB image has 256 possible values for each of its three channels, which gives roughly 16.7 million possible colors. A pixel-art palette might have 16 colors. The original Game Boy has four shades.

So at the most basic level, the job is just this: take a pixel from the original image and decide which palette color it should become.

The trouble is the number of pixels involved.

A 1920 × 1080 image contains 2,073,600 pixels. With a 16-color palette, a brute-force implementation checks all 16 palette entries for every pixel. That's about 33 million distance calculations for one pass over the image.

For an offline program written in C++, that's not especially interesting. In a browser, it can become noticeable very quickly, particularly when the image is being regenerated every time the user moves a slider.

And the quantizer isn't the only thing running. The browser still has to handle pointer events, repaint the interface, update controls, and draw the canvas.

That changes the problem a little. The question isn't simply whether the algorithm produces the right palette. It also has to do enough work quickly enough that the interface still feels responsive.

That was the part worth optimizing.

2. The First Easy Win: Don't Calculate What You Don't Need

The obvious way to compare two RGB colors is Euclidean distance:

For every pixel, we calculate this distance to each palette color and keep the smallest one.

The formula is fine. The square root is the unnecessary part.

We're only comparing distances with each other. If one color has a squared distance of 100 and another has a squared distance of 121, taking the square root doesn't change which one is smaller. The same is true for any pair of non-negative values.

So there is no reason to calculate it.

Instead of:

the comparison can just use:

Nothing about the actual nearest-color decision changes.

This is one of those optimizations that is almost too simple to call an optimization. The important thing is that the calculation happens millions of times. A small amount of unnecessary work becomes less small when it sits inside the innermost loop.

There is another problem, though. Even after removing the square root, RGB distance is still making an assumption that doesn't hold particularly well for human vision.

3. RGB Has a Problem: Equal Numbers Don't Mean Equal Perception

RGB is a useful way to store an image, but it wasn't designed to describe how people perceive differences between colors.

The three channels don't contribute equally to perceived brightness. Changes in green are generally much more noticeable than similar changes in blue, and treating all three channels as equally important can produce some strange choices when reducing a photograph to a small palette.

With ordinary Euclidean distance, a change of 20 in red, green, or blue contributes exactly the same amount:

That is convenient for the computer, but not particularly close to the way the eye behaves.

For a small retro palette, this can become surprisingly visible. A sky, a face, or a patch of foliage can end up mapped to a palette color that is numerically close in RGB space but looks wrong once the image is actually reduced.

The fully correct solution would be to convert the colors into a perceptual color space and perform the comparison there. That's a reasonable approach for applications where color accuracy is the main concern.

For a browser-based pixel-art tool, I found it more useful to keep the calculation simple and bias the RGB channels instead.

One practical weighting is:

Green gets the largest weight, blue the smallest, and red sits between them.

This isn't meant to be a replacement for a proper perceptual color model. It's just a cheap way of making the distance calculation behave a little less like three completely independent numbers.

And because the calculation is still just a few multiplications and additions, it fits nicely inside the pixel loop.

The next problem is more interesting.

Even if the distance calculation is cheap, we're still doing it for every pixel.

4. Most Pixels Aren't Really New Colors

Consider a photograph with two million pixels.

It sounds like there are two million colors to process, but that's not really what happens.

Large areas of an image tend to contain repeated values or values that are very close to one another. A blue section of sky can contain thousands of pixels with exactly the same RGB value. A wall, a shadow, or a large area of grass can do the same thing.

That means the quantizer can end up solving the same question over and over again:

“I've seen this RGB value before. Which palette color did it belong to?”

There's no reason to answer that question twice.

The simplest way to take advantage of this is to cache the result.

An RGB color can be packed into a single integer:

The three 8-bit channels fit neatly into 24 bits:

That integer can then be used as the key in a Map.

The first time a particular RGB value appears, the code calculates its distance to every palette entry and stores the winning palette index. When the same RGB value appears again, the result can be read directly from the cache.

The important thing here isn't that Map is somehow magically fast. It's that the expensive part of the operation is no longer being repeated for colors we've already processed.

This tends to help quite a bit with photographs because color values aren't distributed uniformly across the entire 24-bit RGB space. A two-million-pixel image does not normally contain two million completely different colors.

The actual number of unique values depends heavily on the image, of course. A noisy photograph, a gradient, and a flat illustration behave very differently. But for the kind of images this tool is meant to process, caching can remove a large amount of repeated work.

There is one more implementation detail that matters here: the inner loop itself.

5. Keep the Pixel Loop Boring

JavaScript gives you several ways to represent an image in memory, but not all of them are equally pleasant when you're touching millions of pixels.

For canvas image data, Uint8ClampedArray is the obvious choice. Each channel is stored directly as an 8-bit value, which matches the way ImageData is represented by the browser.

The important thing is to avoid creating little JavaScript objects while walking through the image.

Something like this is convenient:

But doing that millions of times creates a lot of short-lived objects for the garbage collector to deal with.

The faster version is much less interesting:

Read the values directly, calculate the result, write it back, and move on.

The palette can stay in a small array outside the loop. The memoization cache can also be reused rather than rebuilt unnecessarily for every operation.

There isn't much elegance to this code. That's actually a good sign.

When an image-processing loop is running millions of times, I would rather have a handful of predictable operations than a beautifully abstract set of helper objects and callbacks.

The browser doesn't care how clean the architecture looks from the outside. It cares how much work is happening in that loop.

6. Putting the Pieces Together

At this point, the quantizer is doing something fairly simple.

For each pixel, it first checks whether that RGB value has already been processed. If it has, the previous palette choice can be reused. If not, the code compares the pixel with the palette using the weighted squared RGB distance and stores the result.

The pixel data itself stays in typed arrays, and the inner loop doesn't create temporary objects along the way.

So the basic flow is roughly:

None of these ideas is particularly exotic.

That's also the point.

The original brute-force version wasn't doing anything complicated. It was simply doing the same small amount of work an enormous number of times. Once the image is several million pixels wide, that matters much more than whether the distance formula itself looks sophisticated.

For a tool that runs entirely in the browser, responsiveness becomes part of the algorithm. If changing a palette setting makes the interface freeze for a second or two, it doesn't really matter that the final image is technically correct.

The useful part of these optimizations is that they attack different sources of wasted work.

Removing the square root makes each comparison cheaper. Weighting the channels changes the comparison without requiring a more expensive color model. Memoization avoids repeating comparisons for colors we've already seen. Typed arrays and a simple inner loop keep the JavaScript side of the operation predictable.

And that is really all the quantizer needs to be.

It doesn't need a complicated framework around it. It needs to get through a very large number of pixels without making the browser feel like it has stopped responding.

For a pixel-art tool, that is just as important as getting the colors right.