Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-12-08
2004-02-24
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003030
Reexamination Certificate
active
06697169
ABSTRACT:
FIELD OF THE INVENTION
This invention-relates to color image processing, and specifically to color halftoning for digital printing and copying using error diffusion techniques.
BACKGROUND OF THE INVENTION
Halftoning is a technique whereby a multilevel greyscale or color image may be rendered for a printing or display mechanism that is capable of presenting a reduced number of distinct color levels. Halftoning for target devices where dots are either “on” or “off” is referred to as “binary halftoning” because only two levels of each colorant exist. In monochromatic binary halftoning, the rendered image is represented as a collection of black dots on a white background, with the dots being dense in regions of the image that are dark, and sparse in regions of the image that are light. Conversion of a color or continuous greyscale image into a halftoned image requires that the image be sampled, and that a scheme for converting the continuous sampled information be provided. During this process, unwanted patterns may be generated, which patterns need to be eliminated if the final image is to be an accurate and acceptable representation of the original image.
Error diffusion (ED) techniques have been used in digital printing for many years in an attempt to eliminate digitally generated patterns that are perceptible to the human visual system (HVS), however, the complete elimination of these undesirable artifacts has been a problem and has been the focus of much research. Many of the proposed solutions involve systematically modulating the threshold of the error diffusion process rather than holding it constant for the entire image, in fact, the primary way in which the various proposed solutions differ is in how the threshold is modulated.
A number of electronic halftoning techniques are described in Billotet-Hoffinan et al.,
On the error diffusion technique for electronic halftoning
, Proceedings of the SID, Vol. 24/3, 1983. This paper describes hybrid error diffusion techniques wherein the threshold is modulated according to a dither function. Diamond-shaped, Bayer, and ring-shaped dither functions are used, which resulted in the reduction of tendency of the generation of regular textures following error diffusion.
Robert Ulichney, “Digital Halftoning”, MIT Press, 1988, proposes adding random noise to the entire image to defeat the visual artifacts discussed above, however, adding noise, such as the ‘blue’ noise suggested in the paper, to all parts of an image tends to increase graininess.
U.S. Pat. No. 5,014,333, to Miller et al., for Image processor with smooth transitioning between dither and diffusion processes, granted May 7, 1991, discloses an error-diffusion halftoning method wherein a periodic ordered dither matrix is used to define spatially-varying threshold values. The reference describes attenuating the propagated errors in very light and very dark areas. The magnitude of threshold modulation is based on the content of the original image, and the dither matrices vary with the frequency content of the input image, to effect a smooth transition between dither and diffusion processes.
U.S. Pat. No. 5,150,429 to Miller et al., for Image processor with error diffusion modulated threshold matrix, granted Sep. 2, 1992, discloses another error-diffusion halftoning method wherein the threshold matrix is systematically modulated. In, this case, the threshold-modulating pattern is complementary to the known artifact pattern of error diffusion processes. The reference describes a threshold matrix which has sparse threshold modulations arranged along lines that are approximately orthogonal to the prevailing orientation of the worming patterns.
Eschbach,
Error Diffusion Algorithom with Reduced Artifacts,
Proceedings of the IS&T, 45
th
Annual Conference, May 10-15, 1992, pp. 171-173, describes two different error distribution matrices, one for highlights and one for mid-tones, which alleviated the dominant artifacts in each input range. Eschbach asserts that in highlights, the worm-like structures are greatly reduced by means of a modified error-dittusion matrix. Transition artifacts due to switching weight matrices may be avoided by randomizing the location of the transition boundary.
U.S. Pat. No. 5,313,287 to Barton, for Imposed weight matrix error diffusion halftoning of image data, granted May 17, 1994, discloses an error-diffusion halftoning method where the direction of processing scan lines of a source image is selected with blue noise, i.e., such that the direction of processing is biased away from long streaks in the same direction, in order to reduce directional and start-up anomalies. “Serpentine”, “peano”, and other pixel-visitation strategies are also suggested. The pixel values are modified according to a spatially-repeating pattern prior to thresholding. Error diffusion threshold values are modulated with blue noise. Because of the effects of the blue noise, it is possible to distribute the error using a special three-weight filter as opposed to the more traditional larger distribution filters.
U.S. Pat. No. 5,737,453 to Ostromoukhov, for Enhanced error-diffusion method for color or black-and-white reproduction, granted Apr. 7, 1998 describes an error diffusion method in which the threshold is modulated according to a 2D pattern and different diffusion matrices are used for different gray levels. The threshold-modulating pattern is obtained by applying standard error diffusion, with a fixed threshold of 0.5, to a constant gray level image. The constant gray-level image has certain properties, i.e., the gray level is an irrational number, and the resulting threshold-modulating pattern is largely artifact-free.
U.S. Pat. No. 5,809,177 to Metcalfe et al., for Hybrid error diffusion pattern shifting reduction using programmable threshold perturbation, granted Sep. 15, 1998, discloses a method of selectively adding noise based on the input gray level. The input gray signal is modified with either random noise multiplied by a gray-level dependent coefficient or by a predetermined value from a checkerboard or vertical-line pattern. The value from the pattern is dependent upon the gray-level and pixel location of the image data.
The foregoing disclosures illustrate the efforts undertaken to address error diffusion artifacts such as worming. Another category of halftoning techniques is that in which error is not diffused and which incorporates large threshold matrices which are intended to avoid the undesirable patterning of previous “dithering” techniques, which is due to the introduction of energy at low-spatial frequencies to which the human visual system is highly sensitive. This technique also manages to achieve acceptable results. The threshold-matrix design process is intended to produce a resultant image which exhibits the characteristics of so-called “blue noise,” as described by Ulicheney, supra. Blue noise patterns have been found desirable for halftoning because the human visual system is less sensitive to these spatial frequencies. It will be appreciated by those of skill in the art that error diffusion is also considered to achieve this goal, albeit in a very different way. Screens have been successfully produced having an aperiodic, uncorrelated structure without low frequency graininess.
U.S. Pat. No. 5,341,228 to Parker et al., for Method and apparatus for halftone rendering of a gray scale image using a blue noise mask, granted Aug. 23, 1994, discloses a halftoning screening method that uses a blue noise mask. The mask was constructed using a frequency domain procedure. The procedure involves repeated high-pass filtering and spatial-domain dot swapping.
U.S. Pat. No. 5,535,020 to Ulichney, for Void and cluster apparatus and method for generating dither templates, granted Jul. 9, 1996, discloses a method of generating a blue noise screen that avoids the iterative frequency-domain approach. This technique is based on spatial-domain dot swapping between the largest voids and largest clusters of threshold values.
U.S. Pat. No. 5,673,121 to Wang, for Stochast
Feng Xiao-fan
Speigle Jon Mathew
Brinich Stephen
Lee Thomas D.
Sharp Laboratories of America Inc.
Varitz, P.C. Robert D.
LandOfFree
Enhanced error diffusion using a correlated chromatic noise... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced error diffusion using a correlated chromatic noise..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced error diffusion using a correlated chromatic noise... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3342873