Image analysis – Image compression or coding – Gray level to binary coding
Reexamination Certificate
1999-03-11
2003-07-22
Coles, Edward (Department: 2622)
Image analysis
Image compression or coding
Gray level to binary coding
C382S205000, C358S003160, C358S003190
Reexamination Certificate
active
06597813
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to digital halftoning techniques in printers and, more particularly, to a method and apparatus for halftoning which constructs and utilizes a clustered aperiodic mask in a dithering algorithm such that the amount of clustering can be modulated. The present invention also discloses how to modify masks so as to print different numbers of grey levels and how to construct a larger mask out of a given one.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey colors when viewed from some distance.
The fastest and most commonly used methods for digital halftoning are dithering algorithms which use threshold arrays, also called dither matrices or dither masks. A dither mask, defined either in hardware or in software, can be thought of as matrix of numbers.
Too much randomness in the design of a dither mask blurs the image and yields unaesthetic results. Based on the discovery that blue noise, or noise with the low frequencies attenuated, gives a good visual effect, as described for instance in “Dithering With Blue Noise”,
Proc. IEEE
76, no.1 (1988) pp. 56-79, by R. Ulichney, methods to construct dithering masks with blue noise were proposed for instance in U.S. Pat. No. 5,111,310 to K. J. Parker and T. Mitsa, by M. Yao and K. J. Parker in “Modified Approach to the Construction of a Blue Noise Mask”,
J. of Electronic Imaging
3, no. 1, (1994) pp. 92-97, and in “The Void-and-Cluster Method for Dither Array Generation”,
Proc. SPIE
1913 (1993) pp. 332-343, by H. Ulichney.
These blue noise masks generate dispersed dots, which means in particular that black dots can only cluster if the grey level is dark enough to make it improbable or impossible to have all black dots isolated. As a consequence, they are not practical for laser printers or xerographic printers.
To achieve clustering, one can use a traditional threshold array constructed so that increasing the grey level corresponds to printing larger and larger clusters at a fixed periodicity. This method does not produce unpleasant artifacts. However, either the number of grey levels that can be represented using such a method is too small or the clusters which are generated are too big. To correct these effects, one usually uses a multi-cell array, which includes several single-cluster threshold arrays. In a multi-cell array, several clusters are grown with the same spatial period as in the single-cluster array, but are not grown simultaneously with each other. This allows for additional intermediate grey levels.
Once a mask is devised for halftoning grey scale pictures, prior art allows one to use it for color pictures. The individual color planes are halftoned using rotated periodic masks, in order to avoid moire patterns, or other changes are made to aperiodic masks such as described for instance in U.S. Pat. No. 5,341,228 to K. J. Parker and T. Mitsa in the case of a blue noise mask. Adaptation of masks to halftone images for displaying on a multi-bit device is also standard.
Some of these techniques and others are reviewed in the book
Digital Haltoning,
MIT Press, Cambridge, Mass. (1987) by R. Ulichney, which is a general reference for digital halftoning.
To summarize, two important problems which have been largely unsolved were to produce clustered aperiodic masks and multi-cell masks with no artifacts in the following sense: Typically, a multi-cell clustered dither array, when tested on all possible levels of uniform greys, will generate both good and less acceptable patterns, depending on the uniform grey level to be rendered and on the physical characteristics of the printer. These problems were addressed respectively in applications Ser. Nos. 08/909,535 and 08/943,881 cited above.
It is a common object of these inventions to provide techniques which combine the advantages of blue noise and clustering in order to produce a generally acceptable pattern of halftoning as needed, for instance, in laser or xerographic printers.
More specifically, according to the application Ser. No. 08/909,535, the multi-cell clustered dither array patterns of the prior art are replaced by less periodic ones while preserving all benefits of the classical methods. In this way, the invention leaves the nicest patterns unchanged. The invention includes the modification of the dither array to obtain the advantages of blue noise and clustering. The preferred embodiment of the invention provided an automated process of redistributing the locations of the threshold values in the mask that correspond to bad grey levels. This allowed one to obtain more pleasant “blueish” effects in the rendering of these grey levels. This invention applies as well to correct bad or unpleasant looking patterns in any kind of dither mask, including dispersed order dither masks or blue noise masks.
On the other hand, according to the application Ser. No. 08/943,881, there is provided a method of halftoning of grey scale images by utilizing a pixel-by-pixel comparison of the image against a clustered aperiodic mask in which the clustered aperiodic mask is comprised of a partly random and partly deterministic single valued function which is designed to produce visually pleasing dot configurations when thresholded at any level of grey. The object of this invention was to describe a method which allows one to construct dither masks which are not random since clusters are formed by design (in nice patterns), but still present the same lack of periodicity which makes blue noise pleasant to the eye.
The inventions in applications Ser. Nos. 08/909,535 and 08/943,881 were conceived for high resolution printers, say about 600 dpi (dots per inch) or above, and give excellent results for such printers as determined by field testing against results of previously existing methods. However, they still induce undesirable artifacts when applied to low resolution devices, such as low resolution printers or facsimile machines.
It is also a general problem in digital halftoning that actual printed dots differ, often a lot, from theoretically perfectly square or rectangular pixels. One typical consequence of this effect is that a mask devised to produce some number L+1, of distinct grey levels to be rendered in fact can only render a smaller number of grey levels. Also, modern technologies such as the Post Script Level 3 format, allow one to represent more distinct grey levels than before whenever appropriate masks can be used. It is consequently highly desirable to be able to vary as much as possible the number of distinct grey levels to be rendered. In particular, one would like to be able to adapt a mask with nice properties so as to render a different number of grey levels.
It is also a general problem in digital halftoning that masks which are too small produce undesirable effects due to the fact that a pattern of the size of the mask is visible. In the context of printing, masks which are judged large by current standards are often called aperiodic.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a technique which allows one to extend the advantages of the inventions disclosed in applications Ser. Nos. 08/909,535 and 08/943,881 to a greater variety of printing devices, in particular but not only, some with low resolution such as most facsimile machines. In applications Ser. Nos. 08/909,535 and 08/943,881, the dots are isolated up to a specific grey level, say g
0
, and the dots are clustered for all grey levels greater than g
0
. This present invention has the advantage in that clustering is modulated when constructing the mask from lightest to darkest grey levels. Clustering is modulated
Stanich Mikel J.
Thompson Gerhard R.
Tresser Charles P.
Wu Chai W.
Coles Edward
International Business Machines - Corporation
Kaufman Stephen C.
Mitchell Monica
LandOfFree
Masks with modulated clustering and aperiodicity 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 Masks with modulated clustering and aperiodicity and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Masks with modulated clustering and aperiodicity and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3033850