Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-03-31
2003-08-12
Rogers, Scott (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003140, C358S003160, C358S003190, C358S003260
Reexamination Certificate
active
06606168
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present inventions relates to halftone patterns generally used for printing and image display, and in particular, to stochastic halftone patterns.
2. Description of the Related Art
Most printers (and some displays) are binary—they can either print a fixed-size dot on the paper or not at each point in a discrete array. There is no inherent gray scale capability. See R. Rylander, “Electronic Halftones”, presented at the “Lasers in Graphics” conference, ca. 1990, which is incorporated herein by reference.
Virtually all images, on the other hand, contain a continuum of shades from black to white (or a full range of colors). To simulate these varying shades (or colors), binary printers and displays either adjust the size of dots, or adjust the spacing between the dots. Halftone screens are used to determine how large to make the dots or how far apart to space them to represent a particular image.
Most conventional halftone screens use fixed spot positions at a well defined pitch (frequency), and vary the size of the spot to change shade. The high level of periodicity in conventional halftone screens can produce significant moire or interference effects when an image having strong periodic structures is halftoned, or screens are superimposed for multi-color printing.
Stochastic screens greatly reduce, or even eliminate, this periodicity. Removing the periodicity from the halftone texture in turn greatly reduces the appearance of moiré or interference effects. Moiré effects can also be reduced or eliminated when multiple stochastic halftone screens are combined for color printing.
The term “stochastic screening” can be applied to any halftone process that is aperiodic in nature, producing random or pseudo-random, irregular textures. Most stochastic screens can also be categorized as “dispersed dot” screens, representing different shades by varying the number of isolated, same-size spots per unit area, rather than using different size spots at fixed locations, as with conventional halftone screens.
A widely used form of stochastic screening is the “error diffusion” process introduced by Floyd and Steinberg, (R. Floyd and L. Steinberg, “An Adaptive Algorithm for Spatial Grey Scale”, SID Digest, pp. 36-37 (1975)), and the various modifications that have since appeared in the literature. The original error diffusion algorithm was not in itself “stochastic”, but completely deterministic. The dot pattern of a halftone raster image was determined by comparing the value of each continuous tone pixel of the input image added to an accumulated error term with a threshold value to make an “all-or-nothing” decision (print a spot at that raster point or not). The difference between the desired shade and the minimum (paper) or maximum (ink) shade actually used is then added to the error term. While the image was generally processed in a strict raster fashion, the errors were not simply pushed into the next raster-order pixel, but given a two-dimensional distribution in a way that produces subjectively pleasing textures for most shades.
Error diffusion produces a dot sequence with shade-dependent duty factor. While some shades correspond to simple duty factors (i.e., a medium gray would be printed as a simple on-off-on checkerboard pattern), most do not, resulting in textures that exhibit locally coherent patterns disturbed by semi-regular phase jumps in the attempt to reconcile some fractional duty cycle with the integer addressability of the raster device. These phase jumps (which look similar to crystal dislocations) make noise-free synthetic (computer-generated) images processed with conventional error diffusion generally unpleasant.
The inevitable low level noise in “natural” (scanned) images adds a randomizing element that suppresses the formation of significant coherent pattern areas. The benefits of intentionally adding low level noise have been recognized in several modifications of the error diffusion technique, making it truly “stochastic”. (See R. J. Rolleston and S. J. Cohen, “Halftoning with Random Correlated Noise”, J. Electron. Imag., 1(2) pp. 209-217 (April 1992); K. T. Knox and R. Eschback, “Threshold Modulation in Error Diffusion”, J. Electron. Imag., 2(3) pp. 185-192 (July 1993)). Other attempts to improve the appearance involve changing the weights or the size of the neighborhood for error distribution, or modification of the raster path through the image (serpentine, peano curve, etc.) (see R. Stevens, A. Lehar and F. Preston, “Manipulation and Presentation of Multidimensional Image Data Using the Peano Scan”, IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI-5, No. 5, pp. 520-526 (1983)).
Error diffusion processes have the advantage of being dynamic, capable of adjusting their bit-rate on the fly for an optimal pattern at any shade level. The same dynamic behavior is also a disadvantage, however, in that the processes are causal—they only “know” past pixels. This leads to various hysteresis and edge-related artifacts. In addition, the improvements to the original, fully determinative, technique require additional calculations per point, compromising the performance of what is in its basic form already a relatively slow process.
Very fast halftone processing that produces images with textures similar to error diffusion results can be achieved through the use of a “Blue Noise Mask” (T. Mitsa and K. J. Parker, “Digital Halftoning Technique Using a Blue-Noise Mask”, J. Opt. Soc. Am. A 9, pp. 1920-1929 (1992); M. Yao and K. J. Parker, “Modified Approach to the Construction of a Blue Noise Mask”, J. Electron. Imag. 3(1) pp. 92-97 (Jan. 1994); U.S. Pat. No. 5,111,310 (Parker et al.); U.S. Pat. No. 5,341,228 (Parker et al.); U.S. Pat. No.5,477,305 (Parker et al.); U.S. Pat. No. 5,543,941 (Parker et al.)). With this technique, a matrix of threshold values is computed to exhibit a so-called blue-noise spectrum in the Fourier domain. The value of each pixel in an image is then compared to the threshold value in the corresponding cell of the matrix. If it is above the threshold value, it is considered a 1 (solid ink or image dot), and if it is below the threshold value, it is considered a 0 (blank paper or screen). Pixels values matching the threshold value can be considered a 1 or a 0 at the designer's choice, or shifted one way or the other on a random or pseudo-random basis.
With a blue noise mask, the calculation per pixel is just a simple comparison of shade values with corresponding mask values, so printing or displaying an image is quite fast. However, such pre-computed threshold matrices (masks) may not necessarily produce optimal (i.e., “shade-adaptive”) textures. The spot distributions must be monotonic (constrained by previous shade textures), but they are anticipatory or non-causal and can produce more spatially isotropic and homogeneous textures that are insensitive to image structures. In addition, generating the blue noise mask with appropriate statistical and visual characteristics as described by Parker et al. is quite complicated, requiring iterative manipulations in the Fourier (spatial frequency) domain for each shade value.
More important, the blue-noise spectrum masks are heavily biased toward high frequencies. The emphasis of high spatial frequencies in dispersed dot patterns is an advantage in minimizing the visibility of halftone textures particularly on low addressability printers (such as ink jet or electrostatic) as long as the printer has sufficient resolution to properly render individual spots. The number of resolvable spots in a unit area is limited by the addressability and by the minimum spot size which an imaging engine, such as a printer or display screen, is capable of making. When the frequencies of the halftone exceed the capability of the engine, the spots blur together, a form of dot gain. The resulting image then in fact emphasizes low frequencies, which is usually highly undesirable as it generates visually obtrusive patterns in the image.
Dalton has suggested the use of a “ban
3M Innovative Properties Company
Peters Carolyn V.
Rogers Scott
LandOfFree
Narrow band, anisotropic stochastic halftone patterns and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Narrow band, anisotropic stochastic halftone patterns and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Narrow band, anisotropic stochastic halftone patterns and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3111004