Kolås: A dither algorithm [LWN.net]

Øyvind "pippin" Kolås of GIMP and GEGL fame has posted an extremely compact, "spatially stable" dithering algorithm that he believes will prove useful in applications like creating animated GIFs and e-ink videos. Spatial stability means that the color of a particular pixel will not change if the original image pixel is static beneath it; this property can cut the file size of animated GIFs considerably and saves on e-ink refreshes. Kolås notes that the small code size "makes it suited for micro-controller or direct hardware implementations," and believes the algorithm used is in the public domain.

(Log in to post comments)

Kolås: A dither algorithm

Posted Aug 15, 2013 15:26 UTC (Thu) by nettings (subscriber, #429) [Link]

Your comment is not very insightful.
Sure, the graininess of "a dither" is worse than for the other dithering methods, but it was quite educating to me to learn about all the things that can go wrong in dithering motion pictures, and it all depends on what you optimize for.
I was quite surprised to find that the third dither (the error diffusing one) became quite irritating to me - even though any still is largely superior, the constant flickering was quite irritating. On the other hand, the constant canvas-type grain of "a dither" was a lot less intrusive.

Kolås: A dither algorithm

Posted Aug 17, 2013 1:05 UTC (Sat) by dgm (subscriber, #49227) [Link]

I don't agree that the graining is worse. Compare the first and second pics (bayer vs. addition methods). Blocks are easy to discern in the bayer method, while "a dither" manages to get a more continuous and pleasant image.
I have to agree, though, that there's something unpleasant on the error diffusion one, but I can't find an explanation for it.

Kolås: A dither algorithm

Posted Aug 17, 2013 10:42 UTC (Sat) by jospoortvliet (subscriber, #33164) [Link]

A dither also seems to lose data - see that there is more detail in gradients in the diffusion and bayer methods.

Kolås: A dither algorithm

Posted Aug 22, 2013 12:30 UTC (Thu) by epa (subscriber, #39769) [Link]

If you use dithering to convert a high-colour-depth source to 24 bits per pixel RGB, or perhaps even to 15 bits per pixel, then there will not be any perceptible difference between different dithering algorithms (although any dithering will still look better than an undithered downsampling). So this new spatially stable algorithm may cut the file size of a moving picture without affecting the quality.

I agree, if you are dithering down to 256 colours or less, there is a tradeoff to be made where the non-stable dithers can look better.