How do I properly do gamut mapping for an image?

Question

I asked this question earlier. To summarize, dithering an image with a specific palette was causing the image to look smeared and very discolored.

Thanks to Olli Niemitalo, I found out my issue was because the colors in the original image (particularly the near-blacks and near-whites) were outside the gamut of the palette I had. As a result, Floyd-Steinberg dithering was piling up tremendous error levels which were being carried over to the next pixels. I confirmed this to be true by replacing every out-of-gamut color with the nearest color from the palette (which are guaranteed to be in the gamut, by definition). Trying to dither after doing this yielded better results.

What I'm having trouble with is finding the nearest color inside the gamut of my palette, given another color. Here's my current method:

1. Convert palette colors from sRGB to XYZ.
2. Interpret them as a collection of 2D points on a grid (discarding Z)
3. Draw a convex polygon around the points to determine the gamut.
4. For each pixel in the image
   1. Convert the pixel from sRGB to XYZ
   2. If the pixel's XY values are not in the polygon, find the nearest point that is inside it.
   3. Convert this result back to sRGB (using the new X and Y values, and the original Z value)
   4. Replace that pixel in the image with the new color

After all that, dither with Floyd-Steinberg.

This is the palette I'm working with (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)

Original image:

Gamut mapping (attempt):

Dithering:

That certainly looks better than the original problem I was having, but it's still troublesome. I'm sure I'm getting the gamut mapping procedure wrong somehow, and I suspect it has to do with discarding Z, but I have no idea how to proceed. Googling this yielded only Photoshop instructions, which isn't what I'm looking for.

Answer 1

Wikipedia page Gamut puts it nicely:

Generally, the color gamut is specified in the hue–saturation plane, as a system can usually produce colors over a wide intensity range within its color gamut; [...]

But you don't have the general case. Without black for example, you can't produce darker shades of all colors even if they are within the gamut projected onto the XY plane. So you will need to determine the 3-d gamut polyhedron. The gamut is a polyhedron in an intensity-linear (gamma=1.0, linear gamma) RGB or XYZ color space, because intensities of color components mix additively in additive color mixing.

You have additive color mixing in the kind of dithering that you do. If someone looks at the picture from afar, they only see the average intensities of the color components of the pixels. This is not the same as for example average squared intensities, so gamma matters. In dithering, the error calculation and the residual error diffusion arithmetic should be done in an intensity-linear color space.

3-d gamut mapping is not going to be trivial. First you need to find the convex hull of the set of color coordinate points in your palette, in an intensity-linear color space. Then you need to check if a wanted color is inside or outside the convex hull. If it's outside, you need to map it to the surface of the convex hull, which is (the union of) a set of triangles in 3-d space. Here the easiest mapping might be to find the nearest point on the convex hull.

Better results might be had by using a perceptual color difference metric like CIEDE2000. However, this makes finding the nearest point a non-trivial optimization problem, possibly non-convex. Possibly the perceptual color difference metric would also give better results in dithering, just at the step where you choose from the palette the color to use.