Image dithering (1): half toning

Image dithering, also known as half-toning, is a method for reducing the number of colours in an image, while at the same time trying to retain as much of its "look and feel" as possible. Originally this was required for newspaper printing, where no shades of grey were possible, and only black and white could be printed. So a light grey area would be printed as a few dots of black, but mostly white, and a dark grey area with mostly black, with some white spots. One of the obvious problems is that the image resolution would be decreased, but in fact the human visual system can interpret an image even after a loss of information.

Assuming an image to have grey scales between 0.0 (black) and 1.0 (white), one way of half-toning is to threshold the image against copies of the so-called "Bayer" matrices, of which the first two are:

\[B_2 = \frac{1}{4} \begin{bmatrix} 0&2\\ 3&1 \end{bmatrix}, \qquad B_4 = \frac{1}{16} \begin{bmatrix} 0&8&2&10\\ 12&4&14&6\\ 3&11&1&9\\ 15&7&13&5 \end{bmatrix}\]

See the Wikipedia page for discussions and derivation.

And here's a quick example in Julia:

1Julia> using Images, FileIO, TestImages
2Julia> img = Gray.(testimage("walkbridge.tif"));
3Julia> B4 = Gray.(N0f8.(1/16*[0 8 2 10;12 4 14 6;3 11 1 9;15 7 13 5]));
4Julia> B512 = repeat(B4,128,128);
5Julia> img_halftone = Gray(img .> B512);
6Julia> mosaic(img,img_halftone,nrow=1,npad=10,fillcolour=1)

Note that

1Julia> length(unique(img)), length(unique(img_halftone))
2
3  256, 2

The original image had 256 different grey levels, the new image has only 2 - yet, even if it is a much poorer image, it still retains a lot of the pictorial aspects of the original.