1. Technical Field
The invention relates to digital halftoning. More particularly, the invention relates to the production of threshold arrays in the digital halftoning process using filtering and sparse image techniques, resulting in minimal gray scale variance and geometric artifacts.
2. Description of the Prior Art
Threshold arrays are an important component in displaying or printing digital image data. The digital image data must be transformed or processed so that computer display terminals with various grey level capacities, laser printers, dot matrix printers and inkjet printers, many having different resolutions and aspect ratios, all render an image represented by the image data in a similar way. An image processor associated with or configured for each such output device transforms the digital data to a form tailored to the characteristics of that particular device.
Digital halftoning is a key function of such a processor. Halftoning is the process that approximates continuous tone colors (or gray scale) by a pattern of pixels that can achieve only a limited number of discrete colors or gray levels. The most familiar case of this is the rendering of gray tones with black and white pixels.
There are two classes of ordered dither halftoning techniques known in the art. They are clustered-dot and dispersed-dot ordered dithering. Clustered-dot ordered dithering uses variable-size halftone dots at a fixed spacing. The addition of device pixels at a dot's outer edge increases the covered area and the size of the dot. When viewed from a distance, the larger the dot size, the greater the area covered and the darker the image area. Dispersed-dot ordered dithering is preferred when the display device is capable of displaying an isolated black or white pixel. It uses a fixed-size, smaller dot at variable spacing to achieve the same effect as clustered-dot ordered dithering. Variation in dot spacing varies the number of dots in a given area, or dot frequency. In such technique, a denser dot distribution provides a darker image area. On some display devices, each dot comprises up to four or five device pixels. Dispersed-dot ordering provides a dot distribution based upon the shade variations in the original image. The dot distribution is optimized to be the best representation possible for the particular display device.
Ordered dithering is generally implemented using a threshold array, also known as a dither matrix. Typically, each element in the threshold array represents a dither threshold value and is mapped through a Cartesian coordinate system to pixel locations on the continuous tone original and on the output medium. Ordered dither algorithms generate binary halftone images by comparing reflected light from pixels of an original continuous tone image to corresponding threshold values stored as elements in the threshold array.
A threshold array is used to directly control the individual pixels in a halftone image. A threshold array is much like a sampled image because it is a rectangular array of pixel values. However, it is defined entirely in device space, and the sampled values typically occupy 8 bits each. Each element within the threshold array is assigned a threshold value which represents the tonal value at which the pixel is turned on. When deciding whether to turn the pixel on, an image processor checks the pixel's location in the halftone image, determines the tonal value of the image at that exact location, and compares this tonal value with the pixel's threshold value in the threshold array. If the tonal value exceeds the threshold value, the pixel is turned on when the image is created by the imaging system. The effect of the distribution of black and white over the display image is integrated by the human eye as gray.
It would require a very large memory to store the threshold array for a screen large enough to be superimposed on an entire original image. Therefore, it is not uncommon for a threshold array to be replicated and tiled over the entire device space. Each pixel of device space is mapped to a particular element of the threshold array. Only one copy of the threshold array need be stored. Threshold values stored in this fashion are usually mapped to pixel locations on the continuous tone original through a Cartesian coordinate system, modulo the dimensions of the repeating array.
Halftoning with a particular homogeneous threshold array has become known as a "Bayer matrix." A Bayer matrix is an optimally homogeneous ordered threshold array. The goal in generating a threshold array is to order the samples so that, as each successive position or point is turned on, the total two-dimensional ensemble of "on" points remains as homogeneously arranged as possible for each gray level to be simulated. However, the homogeneous arrangement of a Bayer matrix creates a regular geometric pattern that is visible in the display image.
U.S. Pat. No. 5,317,418 issued to Lin on May 31, 1994, is a method for generating a halftone image from a gray scale image by means of a dither matrix. The matrix contains many patterns, each of which represent one gray level of the gray scale image. A positive filter is used to create the patterns in the matrix. The value of each pixel in the gray scale image is compared to the value of an element in the dither matrix, as described above.
Threshold arrays are also used in U.S. Pat. No. 5,542,029 issued to Karlsson on Jul. 30, 1996. The method involves the uses of overlapping threshold arrays rather than tiled threshold arrays to reduce the required size of the repeating threshold array.
Dispersed-dot ordered dithering presents problems, however, in that the amount of gray within an original image is not maintained over an area, i.e. the error arising from the difference between the threshold value and the actual gray level value at any particular cell is simply thrown away. This results in a loss of image information. Halftoning also introduces patterns, anomalies, or coarse quantization artifacts which are visible in the image areas where the scene has little variation (also known as banding).
A technique known as error diffusion is used in the art and makes implicit use of an eye model. It shapes the noise, i.e. the difference between the gray scale image and the halftone image, so that it is not visible by the eye. The error diffusion technique produces noise with most of the noise energy concentrated in the high frequencies, i.e., so-called blue noise. Thus, it minimizes the low-frequency artifacts. However, since error diffusion does not make explicit use of the eye model, it is not easy to adjust when the eye filter changes, for example, with printer resolution or viewer distance. It does accomplish good resolution by spreading the dots.
An example of blue noise masking techniques is demonstrated by U.S. Pat. No. 5,543,941 issued to Parker et al. on Aug. 6, 1996. It describes a technique for rendering a halftone image of a gray scale image by utilizing a pixel-by-pixel comparison of the gray scale image against a blue noise mask. The gray scale image is scanned in on a pixel-by-pixel basis and compared on a pixel-by-pixel basis to an array of corresponding data points contained in a blue noise mask stored in an array in PROM or computer memory to produce the desired halftone image.
U.S. Pat. No. 4,339,774 issued to Temple on Jul. 13, 1982, implements error diffusion in generating a dispersed dot halftone image from a continuous tone input image. Error diffusion is also used in U.S. Pat. No. 5,321,525 issued to Hains on Jul. 14, 1994, to create well-formed printable dots in a clustered dot halftone image.
Eye modeling is used to create a diagonal correlation dither matrix in U.S. Pat. No. 5,526,438 issued to Barton on Jun. 11, 1996. The matrix forces diagonal correlation of adjacent dots in the output image. The desired result is a masking of any artifacts through the favoring of diagonal pixels over horizontal or vertical pixels in an effort to produce visually unobtrusive output dot patterns.
In the same manner, U.S. Pat. No. 5,124,803 issued to Troxel on Jun. 23, 1992, uses angled, overlapping screen tiles to create a halftone image. The angled screen tile boundaries are generated in response to selected integers which, together with the number of screen dots along a side of the tile in the direction of screen pitch measurement, determine the limit of the magnitude of screen angle error. This method minimizes moire patterning in the resulting digital halftone color image.
U.S. Pat. No. 5,422,742 issued to Ostromoukhov et al. on Jun. 6, 1995, is a method and apparatus for automatic high-speed generation of digital angled halftone screens. A scanning dither array is introduced which is used for obtaining screens approximating the irrational angles which are generally required by high-quality color reproduction. The method enables color separations to be generated which minimize moire effects, interferences, and artifacts.
Error diffusion and an eye model are utilized in U.S. Pat. No. 5,469,268 issued to Neuhoff et al. on Nov. 21, 1995, to create a halftone image corresponding to gray scale input image. An optimized halftone image is produced by finding the binary image that causes a combination of printer and visual models to match the output of the visual model in response to the original gray scale image.
The aforementioned prior art methods attempt to mask the presence of artifacts in the resulting halftone display image. However the actual artifacts are still present, but may be less evident to the human eye at certain distances or resolutions. Nevertheless, the artifacts still exist. It would be highly desirable to be able to create a halftone image without the presence of artifacts.