Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2001-02-12
2004-03-23
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S586000, C345S643000, C345S089000, C358S003030, C358S003040, C358S003170
Reexamination Certificate
active
06710778
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to halftoning of input image data and is particularly directed to generating a stochastic dither array of the type which generates clusters of dots. The invention is specifically disclosed as a method for generating clustered dots using an “overall” weighting function derived from two functions of two different extents which are subtracted from one another, so that small clusters of dots are formed at locations near a center of the overall weighting function, but at a predetermined radius from this center the overall weighting function limits the chance of such locations from being selected.
BACKGROUND OF THE INVENTION
Halftoning describes the algorithmic process of displaying an image on a device that is capable of representing only a finite, discrete number of tone levels. The position and arrangement of the discrete picture elements should create the illusion of a continuous-tone image (see, Ulichney, “Digital Halftoning,” MIT Press (1987)). Traditional halftoning techniques include clustered-dot ordered dithering, dispersed-dot ordered dithering, and error diffusion.
More recent halftoning techniques include a method using dispersed-dot unordered dithering, which is also known as stochastic dithering, which combines the speed of a dither array with a quality approaching that of error diffusion. Examples of stochastic dithering include: Sullivan and Ray's Correlated Minimum Visual Modulation Patterns (see U.S. Pat. No. 5,214,517), and Sullivan, Ray, and Miller's, “Design of Minimum Visual Modulation Halftone Patterns,” published by IEEE Transactions on Systems, Man and Cybernetics, Volume 21, No. 1, pages 33-38 (January/February 1991)); Parker and Mitsa's Blue Noise Mask (see U.S. Pat. No. 5,111,310); Mitsa and Parker, “Digital Halftoning Technique Using a Blue-Noise Mask,” published in J. Opt. Soc. Am., Volume 9, No. 11, pages 1920-1929 (November 1992)); Ulichney's Void and Cluster Algorithm (see U.S. Pat. No. 5,535,020); Ulichney, “The Void-and-Cluster Method for Dither Array Generation,” Proceedings of the SPIE, Volume 1913, pages 332-343 (September 1993)); and Cooper, Knight, and Love's Minimum Density Variance Method (see U.S. Pat. No. 5,696,606).
Although stochastic dithering performs well in many circumstances, it has certain limitations related to the physical printing process. Similar to conventional error diffusion, stochastic dithering requires reliable reproduction of dispersed dots. However, printers often have difficulty rendering individual, dispersed dots consistently (especially laser or other electrophotographic printers). This causes variation in uniformity and tone. On the other hand, clustered dots, as opposed to dispersed dots, may be rendered with much greater consistency. It could be a significant advantage for certain physical printers to use a hybrid version of halftoning that uses clustered-dot, unordered dithering.
Some clustered-dot unordered (stochastic) dithering methods are beginning to appear. Ostromoukhov may have the earliest such approach, based upon Voronoi polygons. See Ostromoukhov, “Pseudo-Random Halftone Screening for Color and Black and White Printing,” published in Recent Progress in Digital Halftoning, edited by Eschbach, pages 130-134 (1994)—originally in Proceedings of IS&T's 9
th
Non-Impact Printing Conference held on Oct. 4-8, 1993.
More recently, Lau has extended the green noise halftoning approach to generate dither arrays (see Lau, Arce, and Gallagher, “Digital Halftoning Via Green Noise Masks,” to appear in J. Opt. Soc. Am. A, 1999). Lau et al. have filed corresponding patent applications in the United States, see application Ser. Nos. 60/071,649 (filed Jan. 16, 1998) and 09/228,573 (filed Jan. 11, 1999).
Two other documents of interest regarding blue noise dither matrices are, “Methods for Generating Blue-Noise Dither Matrices for Digital Halftoning,” by Spaulding, Miller, and Schildkraut, J. of Electronic Imaging, Volume 6, No. 2, pages 208-230 (April 1997); and Wang and Parker, “Properties of Jointly-Blue Noise Masks and Application on Color Halftoning,” Proceedings of IS&T/SID Seventh Color Imaging Conference, pages 188-193 (November 1999).
Another interesting patent application is WO 99/45697 (by Nilsson), which discloses the use of a band-pass filter to modify the mid-tones of the gray levels used in halftoning an image.
FIGS. 5 and 7
disclose some interesting maps used for halftoning.
A conventional void and cluster algorithm begins with an arbitrary dot pattern, typically consisting of a random arrangement of dots. These dots are then repositioned iteratively until the dots are properly dispersed. This becomes the initial dot pattern. A dither array is now constructed, and dots are removed sequentially from the dot pattern. Each time a dot is removed, its location is marked in the dither array with the appropriate threshold level. Once all dots have been removed, the initial dot pattern is restored. Dots are now added sequentially, while marking the corresponding location in the dither array with the appropriate threshold level.
To disperse the original dot pattern, the largest void (i.e., concentration of non-dots, or “holes”) and the largest cluster (i.e., concentration of dots) are identified. (It should be noted that, in the context of a void and cluster algorithm, a “cluster” is a concentration of dots—the dots need not be physically adjacent.) The pixels at these two locations are swapped, in which the dot located at the largest cluster is moved to the location of the largest void. This process continues iteratively until the swap will turn the largest void into the largest cluster, and vice versa. The result is a dot pattern with the same number of dots as the initial pattern, but with the dots spread out from one another (i.e., dispersed) in a visually pleasing manner.
The process of constructing a threshold array from the initial dot pattern is similar. Dots are removed from the locations forming the largest clusters, and dots are added to the locations forming the largest voids. To locate the largest void and the largest cluster, a simple two-dimensional Gaussian weighting function is used. This weighting function is shifted so that its peak is centered at the location of a dot. (It should be noted that the weighting function, like the threshold array, must be periodic.) For each dot in the image, a shifted weighting function will be accumulated. The smallest and largest values, respectively, determine the void and cluster of the given dot pattern.
The largest void may not necessarily be located at a hole, nor must the largest cluster be located at a dot. For example, suppose that the binary image consists of only four (4) dots, arranged in a cross with a hole in the center. The largest cluster would be located at the center of the cross, which of course means that the cluster is not located at a dot. Obviously, a dot cannot be added to a location which already contains a dot, nor may a dot be removed from a location that is already empty.
As described above, the void and cluster algorithm uses a Gaussian weighting function to determine the location at which each dot should be added or removed. This will yield a dither array—potentially a stochastic dither array—consisting of dispersed dots. However, it is possible to modify the weighting function so that a stochastic dither array of clustered dots is instead formed.
It would be an advantage to provide a new method for generating a clustered-dot, stochastic dither array, in the context of a void and cluster algorithm, understanding that this concept can be applied equally well to other existing stochastic dither array algorithms, such as the minimum density variance method.
SUMMARY OF THE INVENTION
Accordingly, it is an advantage of the present invention to provide a void and cluster-type algorithm that uses a novel weighting function that yields a dither array of clustered dots.
It is another advantage of the present invention to provide a weighting function that wi
Bella Matthew C.
Brady John A.
Gribbell Frederich H.
Lexmark International Inc.
Sajous Wesner
LandOfFree
Method for halftoning using a difference weighting function does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for halftoning using a difference weighting function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for halftoning using a difference weighting function will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3200352