Random Dithering

Classical Algorithm - Developed Algorithms

This is the bubble sort of dithering algorithms.  It is not really acceptable as a production method, but it is very simple to describe and implement.  For each value in the image, simply generate a random number 1..256; if it is greater than the image value at that point, plot the point white, otherwise plot it black.  That's it.  This generates a picture with a lot of "white noise", which looks like TV picture "snow".  Though the image produced is very inaccurate and noisy, it is free from "artifacts" which are phenomena produced by digital signal processing.

Many techniques exist for the reduction of digital artifacts like these, most of which involve using a little randomness to 'perturb' a regular algorithm a little.  Random dither obviously takes this to extreme.

I should mention, of course, that unless your computer has a hardware-based random number generator (and most don't) there may be some artifacts from the random number generation algorithm itself.

While random dither adds a lot of high-frequency noise to a picture, it is useful in reproducing very low-frequency images where the absence of artifacts is more important than noise.  For example, a whole screen containing a gradient of all levels from black to white would actually look best with a random dither.  In this case, ordered dithering would produce diagonal patterns, and error dispersion would produce clustering.

For efficiency, you can take the random number generator "out of the loop" by generating a list of random numbers beforehand for use in the dither.  Make sure that the list is larger than the number of pixels in the image or you may get artifacts from the reuse of numbers.  The worst case would be if the size of your list of random numbers is a multiple or near-multiple of the horizontal size of the image, in which case unwanted vertical or diagonal lines will appear.

Exemplifying: