Image analysis – Image enhancement or restoration – Image filter
Reexamination Certificate
1998-07-31
2002-01-01
Lee, Thomas D. (Department: 2724)
Image analysis
Image enhancement or restoration
Image filter
C382S251000
Reexamination Certificate
active
06335989
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to halftone images, and more particularly to methods of generating screens for printing halftone images on printing engines.
2. Art Background
A printer can be designed to print a picture as a halftone or gray scale image. For a halftone image, each pixel of the image either has a dot printed or not printed. For a gray scale image, each dot on a pixel is refined to have one of many gray levels. Halftoning creates the illusion of continuous tone images by judicious arrangement of binary picture elements, simulating the continuous tone image.
A halftone image is usually easier and cheaper to generate than a gray scale image. Many relatively low cost printers are specifically designed to print halftone images. For a printer to print a gray scale image, the image must first be transformed to a halftone image using a screen or set of screens. One objective of the printing industry is to develop appropriate transformation techniques so that the halftone image becomes virtually indistinguishable from the gray scale image.
One prior art method transforms a gray scale image to a halftone image by means of a dither matrix. The gray scale image has many gray levels and many pixels. Each pixel has a value. The dither matrix occupies a physical space and has numerous elements, each with a value. The dither matrix is mapped over the halftone image to generate the halftone image. For a gray scale image that is larger than the dither matrix, the dither matrix is replicated or tiled to cover the entire image. Each pixel in the grayscale image is compared to an element in the dither matrix. If the gray scale image pixel has a larger value, no dot is printed in the corresponding halftone image position. The halftone image created has the same number of gray level patterns as the number of gray levels in the gray scale image. A darker area in the gray scale image is represented in the halftone image by a gray patterns with more dots.
In order to generate a halftone image using the above method, the dither matrix must be carefully designed. The elements in the matrix should not be generated by a random number generator, as a fully random pattern would create a halftone image that is noisy, corrupting the content of the image.
One prior art method of designing a dither matrix is known as the void-and-cluster method. A general discussion of this method can be found in “The Void and Cluster Method for Dither Array Generation” by Robert Ulichney, published in IS&T/SPIE
Symposium on Electronic Imaging: Science and Technology
, San Jose, Calif., 1993.
Another method of generating stochastic screens is found in “Perception of binary texture and the generation of halftone stochastic screens” by J. Dalton, published in IS&T/SPIE 1995
International Symposium on Electronic Imaging: Science and Technology
, San Jose. Calif., 1995.
Another prior art uses an error diffusion method to generate the halftone image. This method analyzes every pixel of the gray scale image one at a time to decide if a dot is to be printed in its halftone image. Errors from each pixel are “diffused” to subsequent neighboring pixels. Such pixel-to-pixel calculation requires intensive computation, taking much more time to generate the halftone image than a method applying dither matrices. Additionally, the error diffusion method is not suitable for vector graphics, because the values of pixels on a halftone image may not be calculated sequentially. A discussion of the error diffusion method can be found in “An Adaptive Algorithm for Spatial Grayscale” by Floyd and Steinberg, Proceeding of the Society for Information Display, Vol. 17, pp. 75-77, 1976.
Another dither matrix approach by the present inventor is described in U.S. Pat. No. 5,317,418, “Halftone Images Using Special Filters” incorporated by reference herein. This approach, stochastic in nature, produce scattered dots resulting in very uniform patterns in the absence of dot-to-dot interactions in the printing engine. In the case of printing engines where dot-to-dot interactions are present, such as in laser printers, these screens produce patterns that are rough and grainy. What is needed is a method of generating stochastic screens suitable for use in printing engines having dot-to-dot interactions, such as laser printers.
SUMMARY OF THE INVENTION
The present invention provides a method of generating a halftone image from a gray scale image using a dither matrix. The value of every pixel in the halftone image is determined by a direct comparison of the value in a pixel in the gray scale image to the value in an element of the matrix. The method is suitable for both raster and vector graphics, and is also suitable for printing engines having dot-to-dot interactions.
Briefly and in general terms, each of the halftone image, the gray scale image, and the dither matrix occupy physical two-dimensional areas. The three areas are substantially equal to each other. In some cases it may be advantageous to use a dither matrix smaller than the halftone and grayscale images; in this case the dither matrix patterns are replicated or tiled to cover the desired area. Both the halftone image and the grayscale image have many pixels, and each pixel has a value. The dither matrix has many elements, each with a value.
The method of the present invention compares the value of each pixel of the gray scale image with the value of an element in the dither matrix. The result of the comparison determines the value of the corresponding halftone image pixel.
The dither matrix is generated by many patterns, each pattern corresponding to one gray level pattern of the halftone image. Each pattern has many elements, each with a value. The value of each element in a given pattern is determined by a special filter.
According to the present invention, a donut filter is used. Donut filters have the characteristic of peaks occurring away from the current pixel, where the filters of the prior art centered the peak on the current pixel. These prior art filters have the effect of expelling dots, producing a dispersed pattern. The donut filters of the present invention, with peaks away from the current pixel cause a clustering of dots.
Stochastic clustered dot screens are generated by first selecting a transition level within the grayscale range of the image. For the lightest gray levels, lighter than the transition level, a first filter is used to design the halftone pattern. The width of the first filter depends on the gray level. Once the transition level has been reached, a donut filter is used to design the halftone pattern. Dots in the halftone pattern at the transition level serve as seeds where clustered dots are grown. By selecting the transition level at the lightest gray level, the donut filter is used for all gray levels. Clustered halftone dot patterns produced by the donut filter are moire free, and have a halftone noise very similar to the grain noise in photographs, this producing a printed image better resembling a real photograph.
REFERENCES:
patent: 5317418 (1994-05-01), Lin
patent: 5333211 (1994-07-01), Kanda et al.
patent: 5568572 (1996-10-01), Shu
patent: 5592592 (1997-01-01), Shu
patent: 5832122 (1998-11-01), Shimazaki
patent: 5966507 (1999-10-01), Lin
patent: 0 422 588 (1991-04-01), None
Robert W. Floyd, and Louis Steinberg, “An Adaptive Algorithm for Spatial Greyscale”, Proceeding of the Society for Information Display, vol 17, pp. 75-77, 1976.
Robert Ulichney, “The Void-and-Cluster Method for Dither Array Generation”, IS&T/SPIE Symposium on Electronic Imaging: Science and Technology, San Jose, CA 1993.
John Dalton, “Perception of Binary Texture and the Generation of Stochastic Halftone Screens”, ISF&T/SPIE 1995 International Symposium on Electronic Imaging: Science and Technology, San Jose, CA 1995, SPIE vol. 2411, pp. 207-220.
Brinich Stephen
Hewlett--Packard Company
Lee Thomas D.
LandOfFree
Halftone printing using donut filters does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Halftone printing using donut filters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Halftone printing using donut filters will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2836875