| Previous | Table of Contents | Next |
It is not necessary to process each line left to right. Programs can process even-numbered lines left to right and odd-numbered lines right to left. This is called a serpentine raster, which eliminates artifacts in some images. With the serpentine raster, the Floyd Steinberg algorithm becomes:
| left to right | (1/16) | • | 7 | |
| 3 | 5 | 1 | ||
| right to left | (1/16) | 7 | • | |
| 1 | 5 | 3 |
A similar algorithm exists when images must be processed from bottom to top.
Error diffusion naturally softens images. So, to counteract the smoothing effect, it is useful to sharpen images before processing them. However, note the previously suggested procedure alters pixel values, perhaps several times depending on the algorithm, before they are used. This renders them incapable of being sharpened since sharpening can only occur on original pixel data, not the original pixel data plus the cumulative error. One solution is to maintain a separate error array which is referenced only after calculating the pixel sharpened value.
Another approach discards some of the error which provides a natural contrast enhancement. The larger the error discarded, the more pronounced the contrast. In the extreme case, all error is discarded which is equivalent to a threshold algorithm. One of Bill Adkinson’s favorite error diffusion algorithms, also found in Digital Vision, Inc.’s ComputerEyes/ Pro EYES halftone algorithm documentation, is:
| (1/8) | • | 1 | 1 | |
| 1 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 0 |
which uses 6/8ths of the error, discarding 2/8ths. The algorithm is fast since 1/8th of the error is quickly obtained by shifting the error value right three bits, effectively dividing by 8. However, like all error diffusion algorithms, the repeated memory references place extensive pressure on the processor caches.
A third sharpening technique was developed by Dr. Reiner Eschbach of Xerox’s Webster Research Center and was awarded United States Patent 5,045,952. Rather than select a constant threshold value, this approach allows the threshold to vary depending on the original pixel value, hence its name Threshold Modulation in 1-D Error Diffusion. The VIDEO.C program shows how to use this approach, which is applicable with any error diffusion algorithm.
A fourth, but certainly not final, approach uses unsharp masking. Consider the following situation for the current calculation point x:
| a | b | c |
| d | x | f |
| g | h | i |
Rather than use the current calculation point’s value in the threshold comparison and error calculation, simply substitute:
3*x – (b + d + f + h)/2
which is one way of generating the point’s unsharp mask value.
There are numerous error diffusion variations and implementations. IBM researchers Gerhard Thompson and Gerald Goertzel developed an interesting approach which uses randomization to distribute error, in an attempt to eliminate visual artifacts. Let e be the assignment error and z be a random number between 0.25 and 0.75 which is picked for each pixel and not repeated often. Consider the following error diffusion arrangement:
| • | r | |
| a | b | c |
Where:
This approach is more computationally intensive than others.
The VIDEO.C algorithm provides numerous error diffusion implementations. It should be noted that the original Floyd Steinberg algorithm generates excellent results, particularly when using serpentine rasters and discarding some of the generated error for contrast. However, error diffusion algorithms generally produce output that is difficult to compress compactly and render on many devices because of the isolated points it produces.
| Previous | Table of Contents | Next |