Facsimile and static presentation processing – Facsimile – Specific signal processing circuitry
Reexamination Certificate
1999-05-10
2001-01-09
Coles, Edward L. (Department: 2722)
Facsimile and static presentation processing
Facsimile
Specific signal processing circuitry
C358S443000, C358S451000, C358S451000, C358S453000, C382S166000, C382S171000
Reexamination Certificate
active
06172773
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to image-processing, and more particularly to providing an output image through dithering which is perceptually similar to an input image using fewer chrominance or luminance levels than are used by the original input image.
BACKGROUND OF THE INVENTION
As it is known in the art, imaging systems are used to translate a given input image to an output image. For example, a computer screen may register a given input image which is subsequently transferred to an output device, such as a printer. A problem may exist when transferring a multi-level chrominance or luminance (color or brightness) input image to an image generating output device because typical output devices are capable of displaying fewer chrominance or luminance levels for each pixel than are found in the input image.
Commonly, the effect of shading is achieved through digital halftoning, wherein each input level is simulated by varying the ratio of output chrominance or luminance levels in a small area of the screen. A drawback of digital halftoning is that visually sharp edges may be found in a resultant output image due to neighboring output pixels with different output chrominance or luminance levels. Dithering, which adds distinct integer values to the each pixel, was introduced to alleviate the sharp edges seen in halftoned output images. The conversion of an input image pixel array to an output image pixel array using dithering is well known in the art, see for example Robert A. Ulichneys
Digital Halftoning
, MIT Press, 1987, Chapter 5.
Ordered dithering uses a dither matrix whose elements are integer threshold values. The dither matrix is commonly smaller than the input image, and repeatedly laid down over the image in a periodic manner, thus tiling the input image. An example of a 4×4 dither matrix
250
tiled over a 16×16 input image
200
is shown in FIG.
1
. Each element of the dither matrix
250
is an integer representing a threshold value. For example, with a bilevel output device, the threshold value determines whether or not an input pixel at that location will be turned “on”, i.e. a black pixel or “off”, i.e. a white pixel. When the input pixel chrominance or luminance value is greater than the threshold value, the pixel is turned “on”, if the chrominance or luminance value of the pixel is less than or equal to the threshold value, the pixel is turned “off”. For example, if the 16×16 input image in
FIG. 1
had 16 possible chrominance or luminance levels {0, 1, 2 . . . 15} for display on a bilevel output device, a given pixel
210
would be black only if the chrominance or luminance value of the original pixel of the input image
200
is greater than a 5, for example. Note that the highest threshold in the dither matrix is 14, thus ensuring that all input pixels with an chrominance or luminance level of 15 (the highest possible chrominance or luminance level in this example) will always be turned “on” in the output image. Because the dither matrix thresholds essentially determine which pixels of the input image will be displayed on the output device, the ordering of the threshold values in the dither matrix is related to the quality of the output image.
Various ordered dithering methods for arranging threshold values within a dither matrix have been developed. One problem with these ordered dithering methods is that regular patterns appear in the output images due to the tiling of the ordered dither matrix over the input image. This provides an output image which appears artificially processed. In addition, the ordered dither matrices tend to produce an output image with increased low frequency spatial characteristics. Low frequency spatial characteristics in an output image introduce residual visual artifacts which diminish the quality of the output image.
One approach to overcome this problem is the use of randomness to break up the rigid regularity of ordered dither. An example of the use of randomness is discussed by J. P. Allebach in 1976 in a paper entitled
Random Quasi-Periodic Halftone Process
, J. Opt. Soc. Am., vol. 66, pp. 909-917. Subsequent efforts by T. Mitsa and K. Parker are described in
Digital Halftoning Using a Blue Noise Mask
, Proc. SPIE, Image Proc. Algorithms and Techniques II, February 25-March 1, vol 1452, pp 47-56. Mitsa and Parker present a method to produce a “blue noise mask” ordered dither matrix for use in generating an output image with given spatial frequency domain characteristics, mimicking the “blue noise” patterns achieved with a compute intensive error diffusion algorithm described by Robert A. Ulichney in
Digital Halftoning
, Chapter 8, MIT Press, 1987. However, one problem with Mitsa and Parker's approach is that the complex process of generating the “blue noise mask” increases hardware complexity.
SUMMARY OF THE INVENTION
According to one aspect of the invention, an apparatus for dithering an input image to produce an output array for representation on an output device comprises an input device to store input image pixels having a first plurality of chrominance or luminance levels; a dithering system including a dither template comprising an M by N matrix of integer threshold values, the uniform distribution of threshold values throughout the dither template possessing homogeneous attributes; a normalizer unit for normalizing the threshold values of the dither template for storage in a dither matrix according to the first plurality of chrominance or luminance levels of the input image pixels and a second plurality of chrominance or luminance levels of the output array; a summation unit to add the input image pixel chrominance or luminance values to the normalized threshold values of the dither matrix; and a quantizer unit to adjust summation unit output to a closest output array chrominance or luminance level.
An improved method for ordering the threshold values of the dither template includes the steps of providing a binary pattern array of first and second type bit elements also having M by N locations and a rearranging the bit elements in the array. In particular the step of rearranging the bit elements includes the step of wrapping around indices of the bit elements to iteratively move the bit elements at the peripheries of the array to bit element locations within the pattern array until the pattern of bit elements is uniformly distributed, that is the first and second type bit elements are isotopically distributed in all directions. The selection of a bit for movement within the pattern array is dependant on the binary value of the bit and a spatial characteristic of the bit to all remaining bits of a predetermined binary value, for example with the binary value of “1”. The spatial characteristic used in the selection process differs depending on the binary value of the bit element.
For example, for each pattern array bit element having a value “0”, the rearrangement method locates the “0” bit element which has the lowest number of neighboring “1” bit elements. This “0” bit element is termed the largest void location. In contrast, for each pattern array bit element having a value “1”, the rearrangement method locates the “1” bit element with the highest number of neighboring “1” bit elements. This “1” bit element is termed the largest cluster location. Thus, the rearrangement method moves the “1” bit element from the largest cluster location to the largest void location.
When a bit element with a value of “1” which has the largest number of neighboring “1” bit elements would, if the binary value of the bit element were a changed to a “0”, also be the “0” bit element with the smallest number of neighboring “1” bit elements, the “0” bit elements and “1” bit elements are uniformly distributed throughout the pattern array, (that is, the “0” and “1” bit elements are isotopically distributed in all directions) and consequently the bit elements form a pattern with homogeneous attributes. The pattern array is subsequently used as a working binary pattern for choosing
Cesari and McKenna LLP
Coles Edward L.
Compaq Computer Corporation
Wallerson Mark
LandOfFree
Void and cluster apparatus and method for generating dither... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Void and cluster apparatus and method for generating dither..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Void and cluster apparatus and method for generating dither... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2439415