A family of simple
dithering algorithms, aimed at giving similar results to traditional (newspaper-style)
halftoning. The main difference is that the grid used is usually not at as nice an angle, and that newspapers have really small dots. There is no generalisation of the algorithm to
color pixels.
Ordered dithering uses a fixed matrix of thresholds (not included in this writeup). The matrix is a k*k square containing a permutation of the integers 0,...,k^2-1; k^2 must also be the number of greylevels. Common matrices are 8*8, so you'll have to pre-quantise the image to have 64 levels in the common case of images with 256 levels (byte-sized pixels).
The algorithm is simplicity itself: tile the image with the threshold matrix. At each pixel, if its value is greater than the threshold at that point, output a white pixel; otherwise output a black pixel. The algorithm can easily hold just one line of the image (or even just one pixel) in memory at any time.
Clearly, an area with a fixed grey level will be converted to some fixed pattern. This leads to very regular output, but some "boxing" will be apparent. It is harder to correct for larger black dots than white. No "ghosting" appears in the image, since nothing is transmitted between pixels.
The Floyd-Steinberg Dithering Algorithm is a completely different type of dithering algorithm.