How to find the nearest palette color when dithering in RGB

Question

I maintain an image dithering library and command line tool. When I was initially developing the library, I was trying to figure out how to match dithered RGB values (containing quantization error or randomness, whatever the dithering algo does), to the given palette of allowed output colors. Eventually I learned that the best method is not something psycho-visual, but in fact a simple calculation of Euclidean distance, as long as linearized (gamma-expanded) values are used. As a reason, I was told this by Thomas Mansencal (unfortunately the original quote source is lost):

You can factor out the observer [the human] because what you are interested in here is basically energy conservation. The idea being that for a given pool of radiant power emitters, if you remove a certain number of them, by how much must the radiant power of the remaining ones be increased to be the same as that of the full pool. It is really a ratio and doing those operations in a linear space is totally appropriate!

And I wrote on my blog:

This helped it click for me. Dithering can be thought of as trying to reconstruct the “radiant power” of the original pixel colours, while restricted to a certain set of “emitters”, aka the palette colours. It is only with linearized RGB values that we can properly measure the radiant power.

This however, does not seem to be the full story. So far I have encountered two cases where results don't seem to make sense from a human perspective, where colors are being lost. You can see them here and here.

Eventually, I came across a potential solution: at time of comparison, weight each channel (still linearized) according to human vision. So green is the highest weighted, blue is the lowest, etc. This tweaks the idea of "radiant power" from before to better match how humans experience it, as what we call luminance.

And so finally, my question: is this the right thing to do? I have found researching this topic quite difficult, and I have no academic background in it. I am hoping someone with more knowledge can tell me whether I'm on the right track or totally off base, and most importantly, if there is any research or academically-grounded software that does what I am proposing. I will be writing some test software to see if it looks good, but I would like more assurance of correctness then just "looks good on a few test cases".

Answer 1

Dithering is a pretty complex subject that I've had probably a half dozen folks ask me about over the years.

My visceral answer is that a dithering approach is effectively constructing a value between some other values.

What most folks will tend to arrive at is the notion of photometric luminance to guide the dithering formula, which is certainly about half of the equation if we leave out the complexities of vision assemblage of information on the fly, and all of the nightmare fuel that comes from that.

The interesting nuance is the projection of the luminance. Should it be uniform tristimulus luminance to sample from, or a more perceptually-aligned "brightness-like" distribution.

My guts always lean toward the idea that when we are guessing / fabricating a value that does not exist, from some samples of other values, that the proper "construction" of the value should be based on how an observer might perceive it. That is, a perceptual like distribution.1

For a simple test, I'd suggest using something very simple like L* from Lab for guessing and constructing intermediate values.

For values that carry chrominance, and with the tremendous assumption that the values are relative to BT.709 / sRGB, the "correct" weighting would be 0.2126 R + 0.7152 G + 0.0722 B. Note that this weighting can only be properly derived from uniform tristimulus, which means you do not want to weight encoded values, but rather the uniform tristimulus version (sometimes called "linear" but yikes...)

For sRGB encoded values, a simple 2.2 power function will decode the encoded values to uniform tristimulus, avoiding another rabbit hole.

Good luck.

1 For more information about why a uniform-with-respect-to-loose-perception is more sensible for guessing / constructing values between values, see page 51 of "A Fresh Look at Generalized Sampling" by Nehab and Hoppe.