Very cool paper. Something that bothers me is that the Floyd-steinberg error diffusion without dithering looks superior than the version with the dithering. I think this demonstrates that perceptible patterns in the error (non-linear) don’t always look so bad.
One thing I've found (admittedly with audio) is that you can usually get away with less dither power than is needed to completely linearize the error, at the cost of some harmonics for pathological signals which still ends up being less noticeable than the higher power dither noise.
Right, I think that’s what’s going on in my image example.
I think this is a key lesson to people who apply these types of mathematical techniques to the lossy compression of data meant to be experienced by humans. Random noise is not always preferable to non-linear error, i.e. reducing non-linear error is not necessarily the equivalent of improving the perceived quality of the data in question. It can be but the function that determines what “looks good” or what “sounds good” to humans is probably a bit more complex.
This is something I’ve run into with image compression techniques but it applies here too (quantization being a form of compression). E.g. JPEG compresses images in 8x8 blocks because doing the whole image at once would look horrible. Figuring out the redundant information that can be thrown away with the least impact to image quality is still fundamentally an art.
