Imaging devices, such as electrophotographic printers and inkjet printers, form on media a representation of an image by controlling the placement of a colorant, such as particles of toner, liquid toner, or a small volume of ink, on the media. The surface of the media can be subdivided into a two-dimensional matrix of picture elements (pixels). Data defining the image is received by the imaging device. The data defines the image on a pixel by pixel basis in terms of the intensity of the primary colors of the color space used. The data supplied to the imaging device may correspond, on a pixel by pixel basis, to a color value for each pixel. The color value may express the intensity of each of the primary colors in terms of primary color values corresponding to each of the primary colors. For example, if the color value supplied to the imaging device corresponds to an RGB color space, the color value would include primary color values corresponding to the red, green, and blue colors in the color space. Commonly, eight bits are used to specify the intensity of each of the primary color values. The color value is formed from a combination of the primary color values. For example, in an RGB color space using eight bits to define each of the primary color values, the color value for each pixel includes twenty four bits.
The RGB color space is commonly used for displaying images on computer monitors. Computer monitors have the capability to generate the primary colors forming the pixels on the monitor at intensity levels corresponding to the primary color values. For example, with eight bits used to specify each of the red, green, and blue primary color values, 256 intensity levels of each of the primary colors can be generated, thereby allowing over 16 million intensity level combinations.
Imaging devices, such as electrophotographic printers or inkjet printers typically use a CMY or CMYK color space. In a CMY color space, the primary colors are cyan, magenta, and yellow. Ideally, black can be produced by combining the cyan, magenta, and yellow colorant. However, variations in the imaging process and the colorant can make it difficult to produce black by combining the cyan, magenta, and yellow colorants. Therefore, imaging devices frequently include a black colorant, used in place of a combination of cyan, magenta, and yellow colorants, when the color value for a pixel corresponds to black.
If the color values defining the image are specified in an RGB color space and the imaging device uses a CMY color space, a color space conversion is performed. The color space conversion operation may be performed in hardware or it may be performed in software. The result of the color space conversion is three, eight bit values specifying the intensity of the cyan, magenta, and yellow colorant.
Typically, imaging devices, such as electrophotographic printers and inkjet printers, are configured to operate, with respect to the placement of colorant on media, in a binary fashion. That is, the imaging device either places or does not place colorant on the pixel, rather than placing a varying quantity of the colorant, pixel by pixel, to correspond to the primary color values. Therefore to form a representation of the image on the media, colorant is placed on the media in a manner that simulates the effect that would result from placing colorant with a varying intensity corresponding to the primary color values.
A halftoning operation is used to simulate the intensity variation of the primary color values while placing colorant in a binary fashion on pixels. In a halftoning operation, the primary color values are used to determine the pixels on which colorant corresponding to the primary colors will be placed. Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated by reference into this specification in its entirety.
The specific halftoning operation selected for forming the image can have a significant impact on the perceived quality of the result. Consider an image that includes, ideally, a substantially uniform background of a color that is formed in a halftoning operation, with a majority of pixels formed from colorant of one primary color and a minority of pixels formed from colorant of another primary color. In locations where, as a result of the halftoning operation, colorant of the majority primary color and colorant of the minority primary color overlap, a grainy appearance in the background color can result. Although error diffusion halftoning operations can reduce the grainy appearance resulting from the overlap of colorants, error diffusion halftoning operations are computationally and memory intensive. A need exists for a halftoning method that reduces the grainy appearance resulting from the overlap of colorant and is less computationally and memory intensive than error diffusion halftoning operations.