4
$\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?

$\endgroup$
3
$\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.

$\endgroup$
  • $\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 '17 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 '17 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 '17 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 '17 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 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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