Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
2000-01-19
2004-04-13
Williams, Kimberly (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003030, C358S518000, C358S534000, C382S167000, C382S252000
Reexamination Certificate
active
06721063
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The invention relates to a system and method for controlling colors rendered by a printer or displayed on a monitor using more than three colors, excluding black, to reduce the visibility of error diffusion dot patterns with similar image quality as vector error diffusion, but with much less computation than using semi-vector quantization.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owners have no objection to the facsimile reproduction, by anyone, of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
2. Description of Related Art
Scalar error diffusion is a well known technique for reducing continuous tone images to a pattern of black and white spots for rendering using a binary device. A process for error diffusion is disclosed in an article entitled “An Adaptive Algorithm for Spatial Grayscale” by Robert W. Floyd and Louis Steinberg, Proceedings of the Society of Information Display, Vol. 17, pp. 75-77 (1976), hereby incorporated by reference in its entirety. That process uses an algorithm that analyzes whether to render a dot at a certain location within an image based on a comparison of the continuous tone data with a threshold value. Grayscale levels within the continuous tone image above a chosen threshold are assigned a dot to be rendered and those below the threshold are not assigned a dot to be rendered. If the threshold corresponds to midway between black and white, the method always chooses the closer of black and white. The inherent error resulting from such a choice is propagated in specified amounts to adjacent picture elements or pixels not yet analyzed to change the pixels prior to thresholding. This method produces a representation of a grayscale tone over a small area encompassing several dots that is more accurate than conventional halftoning. Hence, the error in the intensity of the digital image is diffused and, on average, zero.
The fraction of the error added to each neighboring pixel depends on a set of weights, the total error being multiplied by the weight corresponding to a given neighboring pixel and then added to the value of that neighbor pixel. The choice of weight can greatly affect the image quality, and much has been said about weights appropriate for giving pleasing results. Examples of weights other than those in the original Floyd and Steinberg algorithm may be found in papers by Jarvis, Judice, and Ninke, “A Survey of Techniques for Display of Continuous-Tone Pictures on Bilevel Displays”, Computer Graphics and Image Processing, Vol. 5, pp. 13-40, (1976), Stucki, “Image Processing for Document Reproduction”, Advances in Digital Image Processing, pp. 177-218, New York, Plenum, (1979), and Fan, “A Simple Modification of Error Diffusion Weights”, Proceedings of the IS&T 46th Annual Conference, pp. 113-114, Boston (1993) and in U.S. Pat. No. 5,353,127 to Shiau et al., hereby incorporated by reference in their entireties.
In the case of color, however, one cannot just apply simple scalar error diffusion to each color component independently. To do so would produce noisy images. For example, a light blue can be produced by magenta and cyan pixels. But if the magenta and cyan are processed independently, then some pixels may have both magenta and cyan, yielding blue, while others have no color at all, giving white. This mixture of white, blue, magenta and cyan will have more contrast and look noisier than pixels of magenta and cyan alone. The process of independently processing each channel can result in any and all of the eight possible pixel colors distributed over an image area.
However, the problem of image noisiness can be reduced by a method of vector error diffusion. In vector error diffusion processing methods, the color chosen for each pixel is the color in a selected color space closest to the desired value, where the desired value is the input value adjusted by the errors diffused from neighboring pixels. This modification tends to confine the pixel colors to a subset near the input value and reduces noise. What is known as vector error diffusion was described in a paper by Venable et al., “Selection and Use of Small Color Sets for Pictorial Display”, Proceedings of the IS&T Annual Meeting, Rochester (1990) and in a paper by Miller et al. “Color Halftoning Using Error Diffusion and a Human Visual System Model”, Proceedings of the IS&T Annual Meeting, Rochester, (1990), hereby incorporated by reference in their entireties.
In vector error diffusion, colors are treated as points in a three-dimensional space, with the colors printable or displayable at given pixel discrete locations within that space. When a continuous tone color is to be displayed, the closest displayable or printable colorant is selected. The error, i.e., the difference between the input color and added error, and the output colorant, is calculated as a vector in color space. Here, the “closeness” might be the simple distance in color space or a weighted distance based on the human visual model. The vector is the difference between the desired, ideal, color and the available colorant. The error associated with that vector is then diffused in the same way as in scalar error diffusion.
There are, however, some problems with vector error diffusion. One such problem is the difficult three-dimensional computation required to find the closest colorant at each pixel. Second, the method is unstable for ideal colors that are near the boundary of the available color gamut provided by,an image rendering device. With these ideal color values, the addition of error adjustment from neighboring pixels can take a requested ideal color value out of the available color gamut. As a result, the nearest colorant to the requested color generates an error that leads even further outside the gamut. As a result, the vector error diffusion process collapses or produces unstable results. A third problem with some implementations of vector error diffusion is that processing may still not select the optimal set of colorants. For example, the vector error diffusion method may produce a gray from white and black pixels, where a smoother image might be produced if cyan, magenta and yellow were used because there would be less luminance contrast.
U.S. patent application Ser. No. 6,072,591, entitled “Sum and Difference Error Diffusion” filed by Steven J. Harrington on Jun. 30, 1997, assigned to the same assignee as the present invention and hereby incorporated by reference in its entirety, teaches a significantly different process for color error diffusion. Rather than applying vector or scalar error diffusion directly to the colors, this process minimizes errors by using the sum and differences of the colors. Using this method, error diffusion is only carried out on three channels with a simple decision tree selecting the output color at each pixel. However, that method for color error diffusion is not applicable when more than three colors other than black are used during color image rendering. Therefore, the process disclosed in U.S. patent application Ser. No. '691 is not applicable when there is more than one way to render a given requested color using various combinations of many colors. This is because the process was designed for use with a cmyk image rendering system.
Additionally, U.S. Pat. No. 6,014,233, entitled “Error Diffusion for Color Images with Semi-Vector Quantization”, filed by Zhigang Fan and Steven J. Harrington on Jun. 9, 1998, assigned to the same assignee as the present invention and incorporated by reference in its entirety, teaches a method for color error diffusion that uses both sum and difference and scalar error diffusion. Sum and difference error diffusion is performed on the two darkest colors of the three colors used in a system to render color images. Scalar error diffusion is performed on the remaining, lightes
Oliff & Berridg,e PLC
Vida Melanie
Williams Kimberly
Xerox Corporation
LandOfFree
Image rendering system and method using sum and difference... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image rendering system and method using sum and difference..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image rendering system and method using sum and difference... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3269093