a dither algorithm; small, spatially stable, based on magic numbers and arithmetic.

GIF animations and eink benefit from the spatial stableness; since fewer pixels change during partial changes

The tiny code size; and not LUT makes it suited for micro-controller or direct hardware implementations,

bayer 1.2M a dither 1.3M (addition based) a dither 1.3M (xor based) error diffusion 2.9M

The above videos shows how the dither applies to a bitdepth reduction task of RGB 8:8:8 to RGB 3:3:2 with a total of 256 colors - below is a 1bit dither with various methods on a gray ramp.

original

bayer

addition based

xor based

error diffusion

experiment with the algorithm on a few images; with different levels dithered to on each components, as well as select between some different patterns (pattern = 4 is a good variation for targeting for instance 32 / 64 levels which RGB 565 has.

as of 2014-03-25 ffmpeg master has these dithering methods; the way the addition based GIF above was created is the following commandline:

ffmpeg -i input.mp4 -vf scale=320x180:sws_dither=a_dither -r 10
  -ss 40 -frames 100 -pix_fmt rgb8 output.gif -y

I claim no copyright on the formula; I've merely discovered it. By speculating that something simple like this; without too bad results might exist; and then writing some software to help me look for it. With a better fitness critera; I think better constants for simple formulas with more blue/green noise like results can be found.

The main novelty of a dither is its simplicity/compactness and ease of implementation. For dithering to RGB 565 or 24bit RGB it is sufficient, it is however not faster than using a LUT with dither array, either of a dither's or a much higher quality dither mask like void and cluster. The way a dither is employed is exactly like other dither masks would be - but it is procedural/shader based. If someone comes up with better magic numbers to use on variations of the above formulas, please tell me :)


The part of the big-buck bunny clip chosen is chosen to highlight problems of 'a dither', if I wanted to make a-dither look good I would instead hunt out examples making bayer and error diffusion look bad ;)

Øyvind Kolås, pippin@gimp.org in aug 2013