Friendly Robot Overlord

Dither is a pretty cool idea. It is what happens when you have something that is high quality (like a photo using lots of colours, or a sound wave with high bit-depth) and for some reason you want to reduce the number of colours (or bit-depth). So you are mapping from lots of values down to less values.

The first thing you would expect is that just finding the nearest match gives good results. This is what happens when you take my favourite test photo:

And a very limited set of colours (red, green, blue, black, white), and pick the nearest colour:

We can also reduce it to black and white the same way:

It looks pretty bad, because although each dot in the image is doing its best, we are forgetting that we don't look at individual dots, we look at the picture as a whole.

One way of fixing this, is to add some noise to the image before doing the operation. If you add noise to the image, the parts which were blue before will probably still be blue, but there is a chance that they will be some other colour - especially if they were just bordering on being blue. By adding random noise to the image, each pixel has a random chance of being any of the possible new colours, so it should give ok results. Sorry, I don't have a picture for this one, but this is what most people mean when they talk about dither - adding noise to a signal before quantizing it.

What I thought would be fun would be to try this process instead:

1. Start with the nearest approximation
2. Pick a random pixel
3. Calculate average colour of pixels (in our working/dithered image) nearby (weighted by closeness) (not including this pixel)
4. Choose the colour which minimises the difference in colour between the source image and the average colour of nearby pixels (including this pixel, of whatever colour)
5. Go to 2 (lots of times)

I chose to weight a pixel by '1 / (1 + distance)', for all pixels in a fixed radius. All other pixels had weight 0. I tried this with different radii.

These are the results I got: (radius 3, 5 and 15 respectively)

For black and white it looks like this (radius 5):

It looks different to more conventional dithering algorithms. And there are some weird things (it seems to eat out the inside of blocks of colour). But for an application done in about 20 minutes, I think it is pretty cool.

A more conventional dither: (done by The GIMP) with Floyd-Steinberg dithering.

So it probably conveys the idea of a goat standing on a pole better than my algorithm, so maybe I should call it an 'effect' instead of a dithering algorithm, then I don't have to worry about things like accuracy.