Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
2000-01-31
2002-03-12
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S001800, C358S534000
Reexamination Certificate
active
06356363
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to a method for halftoning digital color images and is particularly directed to the use of interlocked threshold arrays or interlocked dot profiles. The invention is specifically disclosed in which images are rendered using a dither matrix representing correlated dot patterns, where the dots of each dot pattern are arranged to minimize a function of the variances in the number of dots per region across an appropriate range of region sizes, and in which each color plane threshold array is generated while considering the threshold arrays for all of the other color planes so as to become interlocked; or in which multiple threshold arrays are generated for a single color plane, but while each of these threshold arrays is generated, the other arrays for that color plane are considered so as to become interlocked.
BACKGROUND OF THE INVENTION
Halftoning describes the process of displaying an image on a device which 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. Using the traditional halftoning techniques of clustered-dot ordered dither and dispersed-dot ordered dither, undesirable visual patterns often appear, caused by the fact that the dots are placed along a distinct, rectangular (or sometimes hexagonal) grid. For colored images, there is the additional disadvantage of moire patterns, resulting from the interaction of the spatial frequencies of the halftone patterns of the individual primary colors.
To overcome some of these difficulties, halftoning methods which incorporate randomness have been developed to eliminate the distinctly periodic patterns of ordered dither. In addition, colored images rendered with random dither are free of moire patterns. The earliest attempts to incorporate randomness used white noise, in which all spatial frequencies were represented equally. Although images rendered with white noise dither are free of periodic artifacts, the images nevertheless looked too grainy, which is caused by the presence of low spatial frequencies in the halftone pattern. If the low frequency or “pink noise” content of the signal is eliminated, the remaining “blue noise” retains only higher spatial frequencies. In a book titled
Digital Halftoning
, by R. A. Ulichney, it was disclosed that images rendered with blue noise dither possess sharp detail and are free of the visual artifacts of ordered dither.
Blue noise, or more generally, dispersed-dot stochastic halftoning offers superior visual quality. The earliest blue noise method, error diffusion, considers the quantization error in neighboring pixels when deciding how to quantize the current pixel. Other techniques incorporate models of the printing device's physical behavior, or human visual perception, or a combination of both considerations. Examples of these other techniques include the minimum visual modulation approach described in an article titled
Design of Minimum Visual Modulation Halftone Patterns
, by J. Sullivan, L. Ray, and R. Miller; modified error diffusion, disclosed in an article titled
Model
-
Based Halftoning
, by T. N. Pappas and D. L. Neuhoff; least-squares model-based halftoning, disclosed in an article titled
Least
-
Square Model
-
Based Halftoning
, by T. N. Pappas and D. L. Neuhoff; and direct binary search, disclosed in an article titled
Model
-
based Halftoning Using Direct Binarm Search
, by M. Analoui and J. P. Allebach.
The minimum visual modulation approach described by Sullivan et al. builds a set of 256 binary images (one for each gray level) by optimizing each binary image according to a human visual modulation transfer function. The minimization technique of simulated annealing leads toward an optimal solution, however, the computational costs of each comparison is expensive, requiring a Fourier transform of each potential dot profile. The advantage is that, once this set has been generated, an image may be rendered quickly by simply matching each gray level to the appropriate binary image. The other conventional techniques offer better quality, but all rely upon image-dependent feedback, and require substantially more computation when rendering the image.
Halftoning using a dither array sacrifices some of the qualities of the image-dependent model-based approaches, but offers considerably greater speed when rendering the image. A dither array is a two-dimensional arrangement of numbers used to produce a halftone pattern. In typical applications, the numbers will be integers in the range from zero (0) through two hundred and fifty-five (255), inclusive. To produce a halftone pattern for a gray level “g” in the range of 0≦g≦255, every location in the dither array <g will be marked with a dot. Each resulting “dot profile” (i.e., a binary image representing a constant gray level) must necessarily be a subset of all darker dot profiles. Typically, a dither array is created one dot profile at a time.
It is usually impractical to create a dither array as large as the image which is to be rendered. Therefore, the dither array typically is “tiled,” or repeated periodically, as many times as needed to cover the image. Accordingly, the dither array must be free of any visual artifacts which would result in periodic patterns. The primary advantage of a dither array is its speed, which is due to the fact that for each pixel in the image, it is necessary to check only a single threshold value in the dither array.
An early dispersed-dot stochastic dither array was an adaptation of Sullivan's ,minimum visual modulation approach. By imposing the additional constraint that the bit patterns be “correlated” with one another, a dither array could be generated instead of using a set of 256 uncorrelated bit patterns (i.e., dot profiles). This conventional correlation approach was described in U.S. Pat. No. 5,214,517, by Sullivan et al.
A later patent, U.S. Pat. No. 5,111,310, by Parker et al. discloses the use of a blue noise mask. The Parker blue noise mask builds successive levels of the dither array by filtering the Fourier transform of each dot profile with a blue noise frequency distribution. The filtered dot profile is compared against the original dot profile to determine where dots should be added or removed, in order to create the next level (either higher or lower in gray scale level). Ulichney's void-and-cluster algorithm, disclosed in an article titled
The Void
-
And
-
Cluster Method for Dither Array Generation
, by R. A. Ulichney provides a fast, simple algorithm for generating a blue noise dither array, based upon the spatial distances between the pixels in each dot profile. Although this method is quick, its quality falls short of the optimal solution. Improvements have been made to both the blue noise mask and the void-and-cluster algorithm, discussed in an article titled
Modified Approach to the Construction of the Blue Noise Mask
, by M. Yao and K. J. Parker, and a patent titled
Halftone Images Using Special Filters
, U.S. Pat. No. 5,317,418, by Qian Lin. Both of these conventional approaches are presently susceptible to local minima, as they are based upon greedy optimization techniques.
Stochastic screening combines the high quality of error diffusion with the high speed of screening by use of a threshold array. For color printing, stochastic screens may be used for each color plane. In some situations, each color plane must be rendered individually, without any knowledge of the other color planes. In one example, a “dot-on-dot” method uses the same threshold array for each color plane. Another example is a “shifting” method which shifts the threshold array by a different offset distance for each color plane. Another method called “fixed partitioning” divides (i.e., partitions) the threshold range into “N” equally sized subranges, which are then used as the lightest set of subranges for each of the N planes.
When multiple color planes are combined together (i.e.
Cooper Brian Edward
Love Shaun Timothy
Brinich Stephen
Gribbell Frederick H.
Lambert D. Brent
Lee Thomas D.
Lexmark International Inc.
LandOfFree
Method for halftoning using interlocked threshold arrays or... 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 interlocked threshold arrays or..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for halftoning using interlocked threshold arrays or... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838019