6
$\begingroup$

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:
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)

Quantized

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

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

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.

Dithered 2-color
Dithered 8-color

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. :) $\endgroup$
    – Daffy
    Jun 10, 2017 at 6:59
  • $\begingroup$ 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 $\endgroup$
    – Olli Niemitalo
    Jun 10, 2017 at 7:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daffy
    Jun 10, 2017 at 20:59
  • $\begingroup$ 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? $\endgroup$
    – Daffy
    Jun 10, 2017 at 23:54
  • 2
    $\begingroup$ @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. $\endgroup$
    – hobbs
    Jun 10, 2019 at 21:31
1
$\begingroup$

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.

Dithering using custom implementation

dithered-cat

Dithering using GIMP

dithered-cat using GIMP

Original (For reference)

original un-dithered cat

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.