3.16. Dithering   

From Heckbert (1982)

The basic strategy of dithering is to trade intensity resolution for spatial resolution. That is, by averaging the intensities of several neighbouring pixels, one can get colours not represented by the colourmap. If the resolution we are using is high enough, the eye will do the spatial blending for us. Taking advantage of this, it is possible to reproduce many colour images using only four colours.

The dithering technique looked at here is due to Floyd and Steinburg (1975). Their algorithm compensates for the quantisation error introduced at each pixel by propagating it to its nearest neighbours. If the propagation is directed only to pixels below or to the right of the "current pixel", we can do both quantisation and propagation in one top-to-bottom pass over the image. The code of such an algorithm would look something like this:

for i=0 to NI-1 do

   for j=0 to NJ-1 do

   begin

      x = c(i,j);                       (read a colour)

      k = p(x);                         (find nearest rep.)

      f(i,j) = k;                       (draw quantised image)

      e = x - y(k);                     (quantisation error)


      (distrib. in 3 directions)

      c(i,j+1) = c(i,j+1) + e*3/8;

      c(i+1,j) = c(i+1,j) + e*3/8;

      c(i+1,j+1) = c(i+1,j+1) + e/4;

   end