# Why does this image look so bad when dithered with a certain palette?

I'm trying to write software to create a mosaic of one big image made up of a bunch of smaller images. The result is okay, but I think it would be better if I used dithering.

My problem is that dithering is giving even worse results and I don't know why.

Here's the original:

Here's the same image quantized (no dithering) with the following palette (in (R,G,B) format):

(162, 143, 66)
(128, 148, 168)
(120, 99, 100)
(31, 39, 97)
(126, 116, 103)
(203, 35, 9)
(57, 81, 43)
(104, 101, 98)


Not great, but workable. About what I'd expect.

Now here's the same image dithered using Floyd-Steinberg:

Pretty much unrecognizable. What's going on here?

To make sure my dithering algorithm was implemented properly, here's the same image dithered using 2-color and 8-color palettes.

Both of these are a whole lot better than the other one. Why is that?

I think what's going on is something analogous to CCD sensor blooming.

The badly working palette does not cover the extreme color values of the original image. Floyd–Steinberg dithering works by error diffusion, where the error in color at a pixel being processed is spread to nearby pixels not yet processed, to the right and to some of the pixels on the next pixel row. With the kitten, you have near-black and near-white areas, and in those areas the algorithm – working like a bulldozer – will accumulate more and more error because the colors it can use will always fall short the same way, and when it finally comes out of the problem area, the accumulated error is so large that it takes many pixels to get rid of it, smudging the image.

In other words, if the image has out-of-gamut colors, you get problems. If a color is inside any polyhedron formed by any of the palette colors, then it is in gamut and can be reproduced by alternating colors from the palette. In other words, the color is in the convex hull of the palette colors. If it's not in the convex hull of the palette colors, it is out of gamut. Gamut mapping before dithering would resolve the problem.

• So in my case, I have a color gamut with (in this case) 8 primary colors, and I have to use gamut mapping to project the original image inside the gamut of the palette? I'm not sure how to do gamut mapping just yet, but I want to be sure I know what I'm looking for. :) Jun 10 '17 at 6:59
• That's right, and "gamut mapping" can mean almost anything. You can replace each out-of-gamut color with its nearest (by some metric) in-gamut color or you can make all of the colors in the image duller. See dba.med.sc.edu/price/irf/Adobe_tg/manage/renderintent.html Jun 10 '17 at 7:17
• So here's an update on this project. I have it convert all the palette colors to xyz (discarding the z), then draw a convex polygon around it to get the gamut. Then, to test if this idea is viable, I simply replace every out-of-gamut color with the nearest palette color. After that, dithering works like a charm. Thanks for your help :) Though I wanted to ask, do you have any tips for getting the nearest in-gamut color given an out-of-gamut color? I was gonna use some stuff to find the nearest point on the polygon, but there might be a better way. Jun 10 '17 at 20:59
• After having it find the closest point in the polygon for each out-of-gamut pixel (the polygon being the convex polygon formed from the XYZ values of the palette colors), I'm still getting weird results. Much better than before, but still smearing. After mapping gamut. After dithering. I believe this is due to the same effect earlier, that there are areas of near-black that the palette can't handle. Do you have any suggestions? Or should I open a new question? Jun 10 '17 at 23:54
• @Daffy A simplistic, but possibly good enough, approach would be to contract everything towards the center of the xyz space until no points lie outside the gamut. Or (possibly better), contract until 80 to 99% of the points are in the gamut, and then contract the points that are still outside individually towards the center until they lie just on the hull. This sacrifices smooth tone in the name of contrast, and you can control the tradeoff by adjusting the percentage. Jun 10 '19 at 21:31

I know this is an old/answered question, but I wrote an arbitrary-palette positional dithering implementation a while back which might be of interest to whoever stumbles upon this question. Positional dithering was more interesting for my use-case, but I find that positional dithering is much easier to reason about and implement anyway. Most of this information probably applies to other dithering methods too.

One important thing I figured out the hard way is to always take luminance/luma into account when comparing colors. Sacrificing ~33% color accuracy for twice the detail is almost always worth it, especially for small palettes. Typical dithering algorithms do not do this (Especially those designed for well-distributed palettes like CGA/EGA or grayscale), but when introducing arbitrary palettes, luma becomes very important. You can see this when looking at the GIMP version below.

The color distance function I used was inspired by bisqwit.