Øyvind Kolås    pippin@gimp·org twitter bitcoin patreon  

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 small footprint code/logic size 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.



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, for some more - and recent tuned examples of a_dither see the image viewer terminal viewer/tv.

NB: numbers in the code below are editable!

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

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 :), I consider a-dither public domain.

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 , august 2013