After successfully getting Error Diffusion working, I decided to see if I could get Ordered Dithering working. Ordered Dithering is a technique akin to the half-toning you see on images in newspapers. From an image made up of many colours you can create an image made up of only a handful of colours stippled such a way as to give the illusion of many colours.
There are several excellent explanations of Ordered Dither on the web for the curious written by people who actually know what they are talking about - I would recommend this one and this one.
Ordered Dithering is much simpler than Error Diffusion (which is probably why it took me longer to get it working!). As it's a much simpler process it's lightning fast in comparison, even when coded in Python.
As a test, I took John Liven's picture of a Somerset cottage.
Photo: John Livens
Then I converted the image to the BBC Micro's MODE 2 (which has just eight colours) using an ordered dither with a 2 x 2 threshold matrix.
BBC MODE2, Ordered Dither, 2x2 matrix
As you can see above, it produces a very pleasing regular patterning on the colours - to allow you to compare, here is the same image with Floyd-Steinberg Error Diffusion:
BBC MODE2, Floyd-Steinberg Error Diffusion
On a small image such as this, larger grids don't really add much. Here is an ordered dither using a 4 x 4 threshold matrix:
BBC Micro MODE2, Ordered dither, 4x4 matrix
But, the proof of the pudding is in the eating. If you have The GIMP installed on your computer you might like to try the ordered dither filter for yourself - it's available from here.