Palette order affects output

[makew0rld]

This issue was originally made for the didder repo, so didder commands are referenced.

---

This is a strange and important bug.

These are the two commands:

didder -i input.png -o test.png  -p 'black red white' edm FloydSteinberg
didder -i input.png -o test2.png -p 'black white red' edm FloydSteinberg

input.png is this image:

Here are the respective outputs:

Obviously, they should be exactly the same. This only occurs with edm and does not depend on the matrix used. This does not seem to occur with the upstream dither library, indicating the problem is with the didder code.

[Shrinks99]

Can replicate the same results with the commands posted. Wacky bug.

original image

test1.png

test2.png

[makew0rld]

Note: the correct image is test2.png, where the palette order is black white red. This is what the dither library outputs in my tests.

[makew0rld]

Here is the most minimal test case I could find.

Original image, a 2x2 PNG of only the color #FFCC00:

Direct link: https://user-images.githubusercontent.com/25111343/117172919-42aaf100-ad9a-11eb-8410-f56eba406f58.png

Here are the two outputs, scaled up with -u 50:

[makew0rld]

This test can actually be replicated by the dither library. Transferring issue there now.

[makew0rld]

Ok, I have figured out the problem.

When quantization error is applied to the bottom right pixel, the final (linear, 16-bit) value is 65535, 65535, 0, equivalent to #ffff00, pure yellow. This color is then compared against the (linearized) palette to find the nearest color, using Euclidean distance.

The Euclidean distance (without square root) of white (16-bit) to the yellow is 1073709056. And from red to the yellow? Also 1073709056.

The nearest color is evaluated in a loop, and a "best" value is compared against, with only lower distances being let through. Since red and white distances are equal, whether red or white is specified first in the palette will determine which wins out.

---

What is the solution to this? Having palette order affect output is problematic and unexpected for users.

But ultimately this appears to be subjective! In @Shrinks99's example black white red looks clearly better, but in my original example it's less clear-cut and it could be said that black red white looks better.

Mathematically they are equivalent, but not to the human eye. And the preferred image seems to be context dependent, like it's nicer for the parrot's feathers to all match, while it's nicer for game on the table to look different than the background.

Telling users to switch around palette order if things look bad is not really feasible. For larger palettes this becomes an annoying problem requiring a script, and in most cases it won't affect anything at all and would just be a pointless worry. Is there any solution possible, or is this just inherent to dithering?

[makew0rld]

The diffusion coefficients have the property that if the original pixel values are exactly halfway in between the nearest available colors, the dithered result is a checkerboard pattern. For example, 50% grey data could be dithered as a black-and-white checkerboard pattern. For optimal dithering, the counting of quantization errors should be in sufficient accuracy to prevent rounding errors from affecting the result.

From Wikipedia

Using uint32 values (but still uint16 colors) did not change anything. Neither did using float32 for all linear values and converting at the last moment. Both of these increase accuracy but affected nothing in the end. I'm unsure why no checkerboard is appearing. Maybe this is something I need to do in my code, like alternate between the two colors when they're equal? What if more than two are?

[makew0rld]

@KelSolaar sorry to bother you but I was wondering if you had any input on this.

[makew0rld]

If a checkerboard is what is desired here, then it is all the second images that are correct, the palette of black white red. I've tested, and a palette of white red black produces the same result. Is a palette sorted in descending order the way to go then? More analysis is needed to determine the implications of this, and whether it only applies to this case, to these colors, to Floyd-Steinberg, to error diffusion, etc.

[makew0rld]

This issue has been fixed in the weighted branch, which produces the same image no matter the order (at least for the examples above). It always outputs the correct second image. For more information on how this fix came to be, see https://github.com/makeworld-the-better-one/didder/issues/14. This issue will be closed once the branch is merged.

[makew0rld]

Branch was merged in #12