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.

To generate the matrix described above:

Get the binary representation of the x coordinate and of the y coordinate within the array. Reverse the order of the bits, then interleave the two numbers (e.g. abc interleaved with def is adbecf). For example, in an 8*8 matrix, the entry at (5, 3) is calculated as follows: the x coordinate is binary 101, the y coordinate is binary 011, the two strings reversed are 101 and 110, interleaved you get 110110, which is the binary number for that entry in the array (54).

The whole array looks like:

  0  32   8  40   2  34  10  42
 16  48  24  58  18  50  26  58
  4  36  12  44   6  38  14  46
 20  52  28  60  22  54  30  62
  1  33   9  41   3  35  11  43
 17  49  25  57  19  51  27  59
  5  37  13  45   7  39  15  47
 21  53  29  61  23  55  31  63
though, of course, a reflection of the matrix through vertical, horizontal, or either diagonal would give equally effective results, or a 90 degree, 180 degree or 270 degree rotation.

There is a generalisation to colour pixels, and to multiple greyscales (rather than just black and white). Imagine a source file with 8 bits of greyscale information, 256 shades of grey, that is to be transformed into a 2-bits-per-pixel file, 4 different shades. In this case, 6 bits of shade are to be dropped from each pixel. Create a matrix, size 8*8 (so there's 2^6 entries). To each 8-bit value in the original file, add the corresponding entry in the matrix (overflows are to count as the maximum permissible value, in this case 255). Now simply drop the least significant 6 bits in every pixel. The result will be an ordered dither 4-shade representation of the original 256-shade picture. To perform ordered dither on a colour picture, take each of the three RGB channels of colour information and treat each seperately as a greyscale image, then recombine the colours at the end.

Log in or register to write something here or to contact authors.