Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-12-02
2004-03-16
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003030, C358S003050, C382S252000
Reexamination Certificate
active
06707576
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to digital halftoning of continuous tone images and, more particularly, to a method of error diffusion for digital halftoning.
Digital halftoning is a technique for rendering continuous tone images on display devices that are incapable of producing the number of levels of luminance or chrominance that are contained in the original image. By way of example, digital halftoning is used to print images having continuous gray levels on printers that are only capable of binary output; that is, printing (or not printing) a black dot. Likewise, digital halftoning may be used to display continuous tone color images on displays that are only capable of rendering a limited number of combinations of red, green, and blue.
To render an image with a halftoning process, the colors of the image's picture elements or pixels are sampled and quantized. The color of a pixel may be represented by the levels of the composite luminance and chrominance signals. The luminance of the pixels of continuous tone gray images is quantized into gray levels for rendering with binary output devices. Typically, gray tones are quantized with 256 levels facilitating description of a pixel by eight data bits. For color displays, the composite luminance and chrominance signals are converted to individual “red, green, and blue” signals or “cyan, magenta, yellow, and black” signals as required by digital color output devices.
To print or display an image with halftoning, the image is decomposed into a grid of halftone cells each containing a number of picture elements or pixels. The gray of an area of the original image is simulated by printing or displaying black pixels distributed throughout the halftone cells of the corresponding area of the rendered image. Likewise, colors not included in an output device's color pallette are simulated by distributing pixels throughout the halftone cell printed or displayed with “nearby” colors available from the pallette. Digital halftoning is effective because of the tendency of the human visual system to ignore fine detail and primarily sense the overall intensity of an area of an image.
One common technique for digital halftoning is error diffusion or spatial dithering. Error diffusion was first disclosed by Floyd and Steinberg in
AN ADAPTIVE ALGORITHM FOR SPATIAL GRAYSCALE
, Proceedings of the Society for Information Display, vol.17-2, pages 75-77 (1976). In the error diffusion technique the color of each pixel of the original image is measured and quantized. An input color signal representing the measured color of the pixel plus an error diffusion adjustment is compared to a preselected threshold or boundary signal that divides the signals representing the available display colors in the device's pallette. A display color nearest the original color is selected and the output device is instructed to render the subject pixel in this display color. The error or difference between the adjusted input color signal for the subject pixel and the display color chosen from the pallette is determined. The error is divided according to a weighting function to create a plurality of diffusion adjustment factors. The diffusion adjustment factors are fed back to the input and added to the input color signals for pixels neighboring the first pixel. The adjusted input color signal is, therefore, the measured color value of the pixel plus the accumulated adjustment factors resulting from quantization errors in selecting display colors for neighboring pixels. In other words, the quantization error resulting from selecting a color for a pixel from a limited pallet is diffused over the area neighboring that pixel. The portion of the error distributed to each pixel and the dimensions and shape of the neighborhood over which the error is distributed differ for several specific variants of the error diffusion technique.
While error diffusion is one of the most effective and common techniques for digital halftoning, the signal delay of the process can generate undesirable artifacts in the output image. In highlight and shadow areas, error diffusion can produce “worms,” transient noise, and edge delays. In midtone areas, error diffusion can produce unpleasant patterning and pattern shifts. Adding noise to the boundary to randomize the threshold decision or utilizing multiple diffusion filters with varying adjustment factor weighting have been suggested as ways to reduce or eliminate these artifacts. However, these techniques either reduce the quality of the output image or increase the processing delay and often the cost of the halftoning processor.
What is desired, therefore, is a method for error diffusion for halftoning that significantly reduces or eliminates artifacts in the rendered image and which does not adversely impact image quality, the latency of the halftoning process, or unduly complicate the halftoning processor.
BRIEF SUMMARY OF THE INVENTION
The present invention overcomes the aforementioned drawbacks of the prior art by providing a technique for selecting an output color for a subject pixel by comparing an input color signal to a boundary separating available output colors. The input color signal is adjusted, at least in part, to reflect a relationship between the output color and the input color signal for another pixel. The boundary is adjusted, at least in part, to reflect a change in the magnitude of a noise source.
REFERENCES:
patent: 4654721 (1987-03-01), Goertzel et al.
patent: 5045952 (1991-09-01), Eschbach
patent: 5051804 (1991-09-01), Morse et al.
patent: 5051844 (1991-09-01), Sullivan
patent: 5070413 (1991-12-01), Sullivan et al.
patent: 5208871 (1993-05-01), Eschbach
patent: 5268774 (1993-12-01), Eschbach
patent: 5313287 (1994-05-01), Barton
patent: 5353127 (1994-10-01), Shiau et al.
patent: 5375002 (1994-12-01), Kim et al.
patent: 5402245 (1995-03-01), Motta et al.
patent: 5473439 (1995-12-01), Pappas
patent: 5493416 (1996-02-01), Fan
patent: 5555103 (1996-09-01), Anderson
patent: 5561751 (1996-10-01), Wong
patent: 5581371 (1996-12-01), Spaulding et al.
patent: 5582582 (1996-12-01), Chapman
patent: 5592590 (1997-01-01), Jolly
patent: 5592592 (1997-01-01), Shu
patent: 5668638 (1997-09-01), Knox
patent: 5673121 (1997-09-01), Wang
patent: 5692109 (1997-11-01), Shu
patent: 5696602 (1997-12-01), Cooper et al.
patent: 5712927 (1998-01-01), Kim et al.
patent: 5726772 (1998-03-01), Parker et al.
patent: 5727453 (1998-03-01), Tippmann
patent: 5737413 (1998-04-01), Akiyama et al.
patent: 5737452 (1998-04-01), Schiller
patent: 5737453 (1998-04-01), Ostromoukhov
patent: 5739917 (1998-04-01), Shu et al.
patent: 5745259 (1998-04-01), Ulichney
patent: 5748785 (1998-05-01), Mantell
patent: 5757517 (1998-05-01), Couwenhoven et al.
patent: 5757976 (1998-05-01), Shu
patent: 5809177 (1998-09-01), Metcalfe et al.
patent: 5835238 (1998-11-01), Mantell
patent: 5835687 (1998-11-01), Brown et al.
“Recent Progress in Digital Halftoning,” ed. Reiner Eschbach, Society for Imaging Science & Technology, 1994.
Uwe Meyer-Gruhl, “Improvements for Color Dithering,” Forschungsgruppe Bildverstehen (FG BV), Informatik IX, Technische Universität München, Orleansstr. 34, 81667, p. 1-4, München, Germany.
Ulichney,Digital Halftoning, 1996, Fifth printing, pp. 1-362, Massachusetts Institute of Technology.
“Digital Halftoning”, www.ee.ubc.ca/home/comlab1/i...www/techpapger/introip/manual04.html, Apr. 6, 1999.
Mulligan, “Improving Digital Halftones by Exploiting Visual System Properties,” www/vision.arc.nasa,gov/publications/asilpap.html, Mar. 2, 1999, NASA Ames Research Center, Moffett Field, CA.
“SID 99' Late news and Withdrawn Papers,” The Society for Information Display, www.sid.org.html.
SPIE- The International Society for Optical Engineering;Image Processing Algorithms and Techniques II;MehmenT. Civanlar, Sanjit K. Mitra, anad Robert J. Moorehead II; vol. 1452, Feb. 25, 1991; pp. 47-56.
SID—Society For Information Display, Digest of Technical Papers,Comparison and Ptimization of Computer-Generated Digital Halftone Pictures, Pe
Chernoff Vilhauer McClung & Stenzel LLP
Lee Thomas D.
Sharp Laboratories of America Inc.
LandOfFree
Noise modulation error diffusion of digital halftoning does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Noise modulation error diffusion of digital halftoning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Noise modulation error diffusion of digital halftoning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268872