[css-color-4] Gamut Mapping Algorithm and Color Banding

[facelessuser]

I'll preface this by saying I'm not entirely sure what the top priority is in the gamut mapping, so maybe this amount of banding is perfectly acceptable.

So the gamut mapping algorithm, I assume, is balancing the best possible match with speed, so there will be a bit of a trade-off, and in some cases may be some concessions.

The current algorithm seems to want to minimize calling the distancing algorithm as much as possible, which makes sense as that will provide the greatest speed. So, the algorithm breaks the binary search loop as soon as the chroma reduction yields a color outside the gamut but within the JND range from the clipped form of the chroma reduced color. The color can fall anywhere within this window and it will kick out. In a gradient with other colors that should be fairly close, banding can occur.

I've implemented the CSS color gamut mapping algorithm as outlined in the spec, but I've also implemented a variant that tries to keep the color on the high end of the JND to prevent reducing the chroma more than necessary. When doing this, the results provide smoother transitions. The variant only performs the distancing on iterations where the color is out of gamut and kicks out as soon as it is close-ish to the upper end of the JND from its clipped counterpart. Obviously, there is a tradeoff in speed, but not as bad as performing the distancing on every iteration.

I'll admit, the banding can be kind of subtle, and sometimes a little less so, and again, I'm not sure if this is an acceptable amount or not, figured it would be worth bringing it up as I imagine a system doing lots of gamut mapping could produce some banding, but speed is also a concern.

[svgeesus]

The current algorithm seems to want to minimize calling the distancing algorithm as much as possible, which makes sense as that will provide the greatest speed.

That was more of a consideration when we were working in CIE LCH and using ΔE2000. Less so with the simple ΔEOK formula.

While it is an intent to make the computation performant enough to be implementable, I wouldn't say speed was the primary criterion (else we would just use per-component clip which is super fast). The primary motivator was perceptual hue preservation with minimal chroma reduction.

So, the algorithm breaks the binary search loop as soon as the chroma reduction yields a color outside the gamut but within the JND range from the clipped form of the chroma reduced color.

That doesn't affect the speed that much, and is not done for speed. It is done to avoid excessive chroma reduction with slightly-concave upper gamut boundaries, which was a severe problem.

I've implemented the CSS color gamut mapping algorithm as outlined in the spec, but I've also implemented a variant that tries to keep the color on the high end of the JND to prevent reducing the chroma more than necessary. When doing this, the results provide smoother transitions. The variant only performs the distancing on iterations where the color is out of gamut and kicks out as soon as it is close-ish to the upper end of the JND from its clipped counterpart. Obviously, there is a tradeoff in speed, but not as bad as performing the distancing on every iteration.

That sounds very interesting and is entirely consistent with the aims of the CSS gamut mapping algorithm.

Could you take a shot at expressing it in terms of a modified pseudocode from the spec?

[svgeesus]

I should also add that I am trying not to over-constrain implementations, in particular if they prefer to find the gamut volume intersection geometrically rather than by binary search. I'm not sure I have been successful in that though, or whether anyone cares about that aspect.

[facelessuser]

I've actually had some more time to play with this and experiment. I don't think you actually have to change the algorithm, just the limit. I would tentatively suggest moving from 0.02 to 0.003.

The issue is that when you have two adjacent colors, which are already some distance apart, and then you have a full JND range of 0.02 in which you are allowed to clip, if you clip one on the low end and one on the high end, coupled with the distance of the already adjacent colors, you maximize the worst-case distance and push things over to a more abrupt change in color. What I was originally doing is ensuring consistency of when the clipping occurs, clamping it on the high end as it seems to yield better performance, but if you just reduce the window, it seems you can avoid the issue that way as well, and it is still faster.

I think 0.003 seems to look pretty ok so far. I'm doing a little more testing, but so far it give the best performance while eliminating the banding.

[facelessuser]

I should also add that I am trying not to over-constrain implementations, in particular if they prefer to find the gamut volume intersection geometrically rather than by binary search. I'm not sure I have been successful in that though, or whether anyone cares about that aspect.

This is good to know.

Could you take a shot at expressing it in terms of a modified pseudocode from the spec?

Yeah, I'm imagining that squeezing the window by using 0.003 takes us closer to an almost pure chorma reduction case which is not the intention. As the geometry of a color space may have some less favorable shapes, squeezing that window could cause us to miss a higher chroma resolution as we might pass right by them.

So, here is some pseudo code for the option of keeping the ∆E matching close to the upper limit of the JND. This ensures adjacent colors are mapped similarly to reduce worst case scenario of greatly maximizing the color distance with adjacent colors. This also ensures we favor the upper edge of the JND to catch the higher chroma resolution when possible.

1. let origin_OKLCH be origin converted from origin color space to the OKLCH color space
2. if the Lightness of origin_OKLCH is greater than or equal to 100%, return { 1 1 1 origin.alpha } in destination
3. if the Lightness of origin_OKLCH is less than than or equal to 0%, return { 0 0 0 origin.alpha } in destination
4. let inGamut(color) be a function which returns true if, when passed a color, that color is inside the gamut of destination
5. if inGamut(origin_OKLCH) is true, convert origin_OKLCH to destination and return it as the gamut mapped color
6. otherwise, let delta(one, two) be a function which returns the deltaEOK of color one compared to color two
7. let JND be 0.02
8. Let EPSILON be 0.001
9. let clip(color)| be a function which converts color to destination, converts all negative components to zero, converts all components greater that one to one, and returns the result
10. set min to zero
11. set max to the OKLCH chroma of origin_OKLCH
12. let lower_bound_in_gamut be a boolean that represents when the min chroma is still found to be in gamut and set it to true
13. set current to origin_OKLCH
14. set clipped to clip(current)
15. set E to delta(clipped, current)
16. if E < JND return clipped as the gamut mapped color
17. repeat the following steps
    1. set chroma to (min + max) / 2
    2. set current to origin_OKLCH and then set the chroma component to chroma
    3. if lower_bound_in_gamut is true and inGamut(current) is true, set min to chroma and continue to repeat these steps
    4. otherwise, if inGamut(current) is false carry out these steps:
       1. set clipped to clip(current)
       2. set E to delta(clipped, current)
       3. if E < JND check and follow these steps
          1. if (E - JND) < EPSILON is true, return the clipped color, otherwise folow these steps:
             1. set lower_bound_in_gamut to false
             2. set min to chroma and continue
       4. otherwise, set max to chroma and continue to repeat these steps

If anything is unclear, I figure I'd post some real code (in Python). Hopefully, this makes sense.

class OklchChroma(Fit):
    """Algorithm to gamut map a color using chroma reduction and minimum ∆E."""
    NAME = "oklch-chroma"
    EPSILON = 0.001
    LIMIT = 0.02
    DE = "ok"
    SPACE = "oklch"
    MIN_LIGHTNESS = 0
    MAX_LIGHTNESS = 1

    @classmethod
    def fit(cls, color: 'Color', **kwargs: Any) -> None:
        """Gamut mapping via Oklch chroma."""

        space = color.space()
        mapcolor = color.convert(cls.SPACE)
        lightness = mapcolor.lightness

        # Return white or black if lightness is out of range
        if lightness >= cls.MAX_LIGHTNESS or lightness <= cls.MIN_LIGHTNESS:
            mapcolor.chroma = 0
            mapcolor.hue = NaN
            clip_channels(color.update(mapcolor))
            return

        # Set initial chroma boundaries
        low = 0.0
        high = mapcolor.chroma
        clip_channels(color.update(mapcolor))
        lower_in_gamut = True

        # Adjust chroma if we are not under the JND yet.
        if mapcolor.delta_e(color, method=cls.DE) >= cls.LIMIT:
            while True:
                mapcolor.chroma = (high + low) * 0.5

                # Avoid doing expensive delta E checks if in gamut
                if lower_in_gamut and mapcolor.in_gamut(space, tolerance=0):
                    low = mapcolor.chroma
                else:
                    clip_channels(color.update(mapcolor))
                    de = mapcolor.delta_e(color, method=cls.DE)
                    if de < cls.LIMIT:
                        # Kick out as soon as we are close enough to the JND.
                        # Too far below and we may reduce chroma too aggressively.
                        if (cls.LIMIT - de) < cls.EPSILON:
                            break

                        # Our lower bound is now out of gamut, so all future searches are
                        # guaranteed to be out of gamut. Now we just want to focus on tuning
                        # chroma to get as close to the JND as possible.
                        lower_in_gamut = False
                        low = mapcolor.chroma
                    else:
                        # We are still outside the gamut and outside the JND
                        high = mapcolor.chroma

[danburzo]

I've also recently implemented the css-color-4 gamut mapping algorithm along with a few other related ideas and published a demo. Barring any implementation mistakes, I can confirm the issues with banding and discontinuities (#7071) with the algorithm described in the spec. I'm plotting hue slices of the various uniform color spaces (CIELCH, OKLCH, etc). I imagine authors will use lch() and oklch() across the entire range of expected coordinates, so we want these plots look uniform and contain intuitive values at the extremes. To highlight a recent interaction, users may expect vivid lch() blacks such as lch(0% 95 328) to still be black, and presumably vivid whites to be white.

With the current algorithm, I believe the JND would have to be lowered out of existence: when the JND becomes small enough to eliminate banding, it's virtually indistinguishable from simple chroma reduction.

Here are some of the related ideas I've tried (just to get them out of the way):

• fuzzy definition of in-gamut at each step of the binary search (either the candidate color is in gamut, or its clipped version is under JND distance) — this could work with a minuscule & arbitrarily-established JND.
• reduce-cl tries to reduce lightness along with chroma — converging to any naive choice of destination point looks quite bad, so the line needs to be at least hue-dependent (like Björn Ottosson explored)

I will try to implement @facelessuser's proposed algorithm & plot some results.

[danburzo]

I've implemented @facelessuser's algorithm under css-color-4-smooth in the demo and it seems — as long as I understood & implemented it correctly — equivalent (visually and I think algorithmically) with the fuzzy method, that is: at each step of the search, consider it a success when either the color is in gamut, or its clipped version is closer than JND to it.

In the source code, you can compare toGamutCSSColor4Smooth to toGamutFuzzy.

[facelessuser]

The basic idea with my implementation is:

• if the out of gamut color is out of gamut, but under the JND when you start, to just clip it and return it
• if it is beyond the JND, reduce chroma just until it is in the high end of the JND.

It's honestly similar to Color.js's approach but cuts the ∆E calls by probably half.

With the way the current CSS algorithm works, you can end up reducing one color to the low end of the JND and an adjacent color on the high end of the JND. If this happens, you have something like 2 * JND difference between them, plus any natural color difference between the two colors. That creates the banding.

Also, keeping the JND on the high end lets you catch any weird geometric quirks of a color space. When gamut mapping with Lch instead of Oklch, there was a problem with Display P3 yellow being reduced too aggressively, and this was just because of the weird shape of the LCH slice. Reducing chroma on the high end helps it catch the peak. This is obviously less of a problem when using Oklch, but Oklch seems to have other issues in the green-ish blue region.

Below, you can see how the gamut mapping line would have missed the peak had it not been reduced to the high end of the JND.

[facelessuser]

@danburzo cool demo by the way 🙂. And yes, the results seem very similar to the fuzzy implementation.

[danburzo]

Here are the two algorithms, shown as a diff for clearer comparison:

+let lower_bound_in_gamut = true;
 let start = 0;
 let end = candidate.c;
 let ε = 0.001;
 let e;
 while (end - start > ε) {
 	candidate.c = (start + end) * 0.5;
-	if (inGamut(candidate)) {
+	if (inGamut(candidate) && lower_bound_in_gamut) {
 		start = candidate.c;
 	} else {
 		clipped = clipToGamut(candidate);
 		e = delta(candidate, clipped);
 		if (e <= jnd) {
-			start = candidate.c;
+			if (jnd - e < ε) {
+				return clipped;
+			} else {
+				lower_bound_in_gamut = false;
+				start = candidate.c;
+			}
 		} else {
 			end = candidate.c;
 		}

They converge to the same solution, but your proposed version has the following optimizations:

• when we've left the gamut, the lower_bound_in_gamut flag prevents further gamut computations, which we already know return false from now on
• if you happen to land very close to the upper bound of the out-of-gamut-but-within-JND range, return early instead of letting the binary search converge to the same solution.

[facelessuser]

I would further suggest swapping to the following to avoid doing unnecessary in gamut checks as well:

-	if (inGamut(candidate) && lower_bound_in_gamut) {
+	if (lower_bound_in_gamut && inGamut(candidate)) {

[danburzo]

Oops, I had arranged it like that for symmetry but that kind of contradicts my when we've left the gamut, the lower_bound_in_gamut flag prevents further gamut computations, which we already know return false from now on statement 🤪

[svgeesus]

EDIT: Has two bugs, do not use, see later, corrected version

Here is my tester code, using color.js but re-implementing the GMA from the pseudocode above. I found that epsilon cold be reduced without noticeable impact on runtime. In general this algorithm is running 4-5x faster than the current color.js one (which uses CIE LCH as the GM space and deltaE2000 as the distance metric, and also makes more in-gamut checks and uses more large objects):

    const JND = 0.02;
    const ε = 0.0001;


    function gamutMap (origin, destination) {
        // OKLCH is the CSS GMA working space
        let origin_OKLCH = to(origin, 'oklch');
        let L = origin_OKLCH.coords[0];
        // return media white or black, if lightness is out of range
        if (L >= 1) return {space: destination, coords: [1, 1, 1], alpha: origin.alpha};
        if (L <= 0) return {space: destination, coords: [0, 0, 0], alpha: origin.alpha};
        // otherwise, return origin in destination, if in gamut
        if (inGamut(origin, destination)) return to(origin, destination);
        // set up for OKLCH chroma reduction
        let min = 0;
        let max = origin_OKLCH.coords[1];
        let min_inGamut = true;
        let current = clone(origin_OKLCH);
        let clipped = clip(current, destination);
        // but first check if we are "close" to in gamut
        let E = deltaEOK(clipped, current);
        if (E < JND) return clipped;
        // now actually binary search for the in-gamut chroma value
        // console.log("pre-checks complete, still here, doing actual gamut mapping");
        while (max - min > ε) {
            let chroma = (min + max) / 2;
            current.coords[1] = chroma;
            if (min_inGamut && inGamut(current, destination)) {
                min = chroma
            } else {
                clipped = clip(current, destination);
                E = deltaEOK(clipped, current);
                if (E < JND) {
                    if (E - JND < ε) {
                        return clipped;
                    } else {
                        min_inGamut =  false;
                        min = chroma
                    }
                } else {
                    max = chroma;
                }
            }
        } //  end of chroma reduction loop
    }

Live versions:

• CIE Lab explorer
• OKLab explorer

[facelessuser]

Yeah, the speed and reduced color banding make this an obvious winner for me :). Happy to see your formal results match what I was observing.

[triple-underscore]

The upadated spec text reflects the above code:

if (E < JND) {
    if (E - JND < ε) {...

but E - JND (< 0) < ε is always true.
(May be a typo of "if (JND - E < ε)" ?)

[facelessuser]

That does look like a typo and is likely to give some incorrect results.

It's likely that this would cause the algorithm to kick out too fast.

[svgeesus]

but E - JND (< 0) < ε is always true.

It is indeed, oops.

(May be a typo of "if (JND - E < ε)" ?)

Yes. Which, once corrected, reveals the second bug in the code I posted above; almost always, the clipped value is returned but sometimes, while (max - min > ε) becomes false and then we ... unceremoniously drop off the end without returning a result (/facepalm).

It's likely that this would cause the algorithm to kick out too fast.

It did; the speedup advantage has now reduced, but it is still 2-3x faster than color.js current (OKLCH chroma, deltaE2000).

[svgeesus]

    const JND = 0.02;
    const ε = 0.0001;


    function gamutMap (origin, destination) {
        // OKLCH is the CSS GMA working space
        let origin_OKLCH = to(origin, 'oklch');
        let L = origin_OKLCH.coords[0];
        // return media white or black, if lightness is out of range
        if (L >= 1) return {space: destination, coords: [1, 1, 1], alpha: origin.alpha};
        if (L <= 0) return {space: destination, coords: [0, 0, 0], alpha: origin.alpha};
        // otherwise, return origin in destination, if in gamut
        if (inGamut(origin, destination)) return to(origin, destination);
        // set up for OKLCH chroma reduction
        let min = 0;
        let max = origin_OKLCH.coords[1];
        let min_inGamut = true;
        let current = clone(origin_OKLCH);
        let clipped = clip(current, destination);
        // but first check if we are "close" to in gamut
        let E = deltaEOK(clipped, current);
        if (E < JND) return clipped;
        // now actually binary search for the in-gamut chroma value
        // console.log("pre-checks complete, still here, doing actual gamut mapping");
        while (max - min > ε) {
            let chroma = (min + max) / 2;
            current.coords[1] = chroma;
            if (min_inGamut && inGamut(current, destination)) {
                min = chroma
            } else {
                clipped = clip(current, destination);
                E = deltaEOK(clipped, current);
                if (E < JND) {
                    if (JND - E < ε) {
                        return clipped;
                    } else {
                        min_inGamut =  false;
                        min = chroma
                    }
                } else {
                    max = chroma;
                }
            }
        } //  end of chroma reduction loop
        return current;
    }

[facelessuser]

It did; the speedup advantage has now reduced, but it is still 2-3x faster than color.js current (OKLCH chroma, deltaE2000).

Yep, that is much more like my measured gains, still really good though.

[devongovett]

@svgeesus should we update WPT to account for the changes in e30aec4? When I tried to update Lightning CSS to use the new algorithm, I got a bunch of test failures. For example, color-mix(in hsl, color(display-p3 0 1 0) 100%, rgb(0, 0, 0) 0%) is now rgb(0, 251, 41) instead of rgb(0, 249, 66). https://github.com/web-platform-tests/wpt/blob/dda6cb1e287b24031d52adeb481e948f4d8dde0b/css/css-color/parsing/gamut-mapping.html#L18 I see that WebKit also still implements the old algorithm.

[svgeesus]

should we update WPT to account for the changes in e30aec4?

Yes, we should.