In the processing of images for various purposes, such as compression, transmission, storage and reproduction, it is often necessary to quantize the data which defines an image. For instance, the individual picture elements, or pixels, of a monochrome image might be defined by eight-bit grayscale values which define a range of 0-255. The lowest grayscale value might represent pure black, and the highest grayscale value is conversely defined as pure white. All of the intermediate values in the range 1-254 define grayscale values having proportionate mixtures of black and white. While it is possible to separately display each of these individual grayscale values on a CRT monitor or the like, most printers are not capable of discretely representing such a large range of values. Accordingly, when the image is to be printed, it is necessary to quantize the eight-bit grayscale values to a lesser number of levels that can be accommodated by the printer. For example, if the printer is only capable of printing uniform black dots, all of the grayscale values must be converted to a binary value, i.e. zero or one.
One form of conversion is to perform a simple thresholding operation, in which each grayscale value is individually rounded up or down to the closest binary value. However, such an approach results in high contrast images which lack any tonal qualities. Accordingly, more sophisticated quantization approaches have been developed in an effort to more accurately reproduce the tonal characteristics of an image. One such approach is known as error diffusion. Basically, in the error diffusion process, the difference between the actual grayscale value of a pixel and its quantized value is determined, and this difference, or error, is added to one or more neighboring pixels in the image. As a result of this process, most of the pixels in a shadow region of an image might be quantized to a value of zero, but a certain number of pixels in the region are converted to a value of one. More particularly, white dots are dispersed throughout a predominantly black region, to create the impression of an intermediate grayscale level within the region. The converse effect occurs in highlight regions, where black dots are distributed throughout an otherwise white region.
While the error diffusion process functions to increase the tonal characteristics of a reproduced image, it can also lead to certain artifacts within the image. One artifact of particular concern is known as a "worm" artifact, which is most prevalent in the shadow and highlight regions of an image. In general, the highlight and shadow regions of an image are considered to be those portions of the image represented by grayscale levels which are within about 15% of the minimum and maximum grayscale levels in the image. In the context of the present invention, the term "dot" is used to identify a white pixel in a shadow region, or a black pixel in a highlight region. In other words, a dot has a quantized value which is complementary to the grayscale values associated with the region. Since dots are relatively rare in the highlight and shadow areas, they can be readily perceived by a viewer if they are spaced too closely to one another. Often, they are perceived as arbitrarily shaped lines, or "worms", rather than a uniform gray level that they are intended to represent.
Various methods have been proposed in the past to reduce or eliminate "worm" artifacts and the like. Examples of such proposed methods include modulation of the error diffusion threshold with noise, or processing the image with a serpentine scanning procedure, or the like. However, these proposed methods have not been totally successful in attempts to eliminate the artifacts.