Digital halftoning is a technique employing digital image processing to produce a halftone output image from a continuous-tone input image. In the digital halftoning technique, a continuous-tone image is sampled, for example, with a scanner or digital camera, and the samples are digitized and stored in a computer. The digitized samples (or “pixels”) include discrete code values having Ni possible input levels (typically Ni=256, with code values ranging from 0 to 255). To reproduce this image with high quality on an output device which can print No output levels, where No<Ni, it is necessary to produce the sensation of intermediate gray levels by suitably distributing the printed dots in the output image using some form of halftoning technique. One example of an output device requiring halftoning is an inkjet printer, which ejects a volume of ink at each output pixel to reproduce the image. The number of output levels (No) of the printer is the number of possible volumes deposited at each pixel (including 0), and is typically in the range of 2-32.
One prior art method of digital halftoning is known as error diffusion. FIG. 1 shows a block diagram describing a basic error diffusion technique. The continuous-tone input level for one pixel of the input image is shown as X. For purposes of illustration it will be assumed that the continuous-tone input level spans the range from 0 to 255. The input level X is added to a weighted error signal Xfe using a summer 10 to produce a modified input level Xin. (The generation of the weighted error signal Xfe will be discussed shortly.) The modified input level Xin for the current pixel is quantized using a quantizer 20 to form the quantized output level Xo. For a binary error diffusion algorithm, the quantizer 20 will output a 0 for any input level below a threshold (typically code value 128), and a 255 for any input level above the threshold. A summer 30 receives the modified input level Xin and the quantized output level Xo and produces an error signal Xerr representing the error introduced by the quantization process. The error signal Xerr is multiplied by a series of error feedback weights using a weighted error generator 40 to produce the weighted error signal Xfe, which is added to the continuous-tone input levels of nearby pixels which have yet to be processed using summer 10. The propagation of the errors made during the quantization process to the nearby pixels insures that the arithmetic mean of the pixel values is preserved over a local image region.
FIG. 2 shows a typical set of error feedback weights used in the prior art. The error for the current pixel, located at (column,row)=(i,j) of the image, is weighted by the error feedback weights, and added to nearby pixels yet to be processed. In this example, there are four error feedback weights having the same value of ¼, with the sum of the error feedback weights being 1. This ensures that the arithmetic mean of the image is preserved.
When using the standard error diffusion algorithm to process a color image, a technique common in the prior art is to apply the error diffusion algorithm independently to each color channel. See, for example, U.S. Pat. No. 5,757,517 to Couwenhoven, et al. This arrangement is shown for processing an image with cyan (C), magenta (M), and yellow (Y) color channels in FIG. 3. This arrangement is successful at preserving the arithmetic mean of the image data in each color channel, resulting in the correct output color, but suffers from the fact that the placement of the output dots in each color channel is decorrelated, and overprints can unnecessarily occur, resulting in an undesirable noisy, grainy appearance to the printed image. To illustrate this, consider that a 16×16 pixel image containing a 30% tint of uniform CMY code values is to be halftoned to 2 levels (on, off) and printed on an inkjet printer. As shown in FIG. 4, the CMY color channels, when processed independently with the error diffusion algorithm, produce dot patterns that typically resemble the cyan, magenta, and yellow patterns shown as patterns 50, 60, and 70, respectively. In these patterns, the black pixels indicate locations where an ink dot will be printed, and white locations indicate white paper. When these three patterns are printed on top of each other on the page, an output pattern 80 will result. (Due to the black and white reproduction of output pattern 80 in this document, only the luminance of the pattern is shown). Each pixel in the output pattern 80 can be one of eight colors: white; C; M; Y; red (C+Y); green (C+Y); blue (C+M); or black (C+M+Y). The luminance modulation between the darker pixels (R, G, B, or black) and the lighter pixels (white, C, M, or Y) produces an undesirable grainy appearance to the human eye. Interestingly, this is not necessary, since the original input image was a 30% tint of CMY, therefore it should have been possible to produce the output image using non-overlapping patterns such that only white, C, M, or Y are produced at each pixel. The luminance modulation between these colors would be much less, providing a more pleasing result.
Error diffusion methods that attempt to provide correlation between the color channels are known in the prior art. These algorithms are sometimes called “vector error diffusion” algorithms. Chapter 16 of “Digital Color Halftoning”, by H. Kang (SPIE Optical Engineering Press, 1999) describes several vector error diffusion techniques. U.S. Pat. No. 5,375,002 to Kim, et al., discloses a color error diffusion method in which an error look-up table is used to help determine the color of an output pixel. U.S. Pat. No. 5,565,994 to Esbach discloses an error diffusion method in which output signals from one color channel are used to determine threshold values for other color channels to provide some decorrelation between the color channels. U.S. Pat. No. 6,637,851 to Van de Velde, et al., discloses an error diffusion method in which a luminance signal is computed and separately error diffused as an additional channel. The luminance information is then used to guide the selection of the output pixel colors. Typically, the prior art methods are computationally complex, requiring substantial additional processing power or memory.
In U.S. Patent Application Publication No. 2008/0055649, Spaulding et al. have disclosed an error diffusion algorithm incorporating error signal offsets which provides significant image quality improvements with only a modest increase in the computational complexity relative to prior art algorithms. (This algorithm will be discussed in more detail later.) However, it has been found that even this algorithm can run 20-40% slower than algorithms that do not use error signal offsets.
Therefore, there is a need for a color error diffusion method which provides for high quality printed images with reduced graininess, and can be implemented efficiently without requiring substantial additional computing power or memory.