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