1. Field of the Invention
The present invention generally relates to 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.
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. The original forms of these arrays used periodic patterns of threshold values which can have an unpleasant rendering at certain colors or grey levels.
One says that a mask is periodic if the size of the mask has (approximately) the minimal size required for a given number, L+1, of distinct grey levels to be rendered or if the arrangement of threshold values within the mask purposely forms periodic structures. In this context, aperiodic usually means "long period" which means that each of the L+1 threshold values is repeated a relatively large number of times in the mask in an aperiodic way. A typical example of an aperiodic mask is a large random one.
Too much randomness in the design of a dither array 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.
However, such 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 where one should cluster:
the black dots to improve both the consistency of the printed dots and the control of the dot overlaps, and PA1 the white dots to ensure they remain visible when rendering very dark grey levels. PA1 1. The mask generates clusters, which is desirable for certain applications and even mandatory for some of them. PA1 2. The clusters are placed and grown in an aperiodic way which is partly random but visually pleasing.
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 multicell array, which includes several single-cluster threshold arrays. In a multicell 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. Traditional multicell masks are considered periodic and the order and manner in which the cells are grown commonly generates unpleasant periodic patterns at several grey levels.
Once a mask is devised for halftoning grey scale pictures, prior art allows it to be used 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.
Most of these techniques and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Mass. (1987) by R. Ulichney, which is a general reference for digital halftoning.
One could be tempted to build blue noise masks by modifying existing methods to favor the formation of clusters. However, this generates unpleasant configurations of black dots for a large number of grey levels. The object of this invention is 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.
Existing halftone masks are either periodic, with or without clustering, or aperiodic, preferably blue noise. Blue noise masks do not have clustering.
This invention has the following advantages over existing methods by combining the advantages of clustering and blue noise patterns:
Thus, this invention can be used where clustering is advantageous while avoiding global regularity or periodicity.