Error diffusion with partial dots method and system

Details Error diffusion with partial dots method and system Error diffusion with partial dots method and system

2001-03-09

2004-08-17

Rogers, Scott (Department: 2626)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S003050, C358S003160, C358S003170, C358S003190, C358S003220, C358S003230, C358S003260

Reexamination Certificate

active

06778299

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to image processing, and more particularly, to an error diffusion with partial dots method and system.
BACKGROUND OF THE INVENTION
In the area of digital printing, representation of the intensity of an image region on paper, i.e., the gray level, has been the object of a wide variety of algorithms published in the last decade. Digital printers are defined as those printers that are capable of making a mark, usually in the form of a dot, at a specified resolution in marks per unit length, typically dots per inch (dpi), on paper. To use such a digital printer to give the impression of gray level intensity, it has been common to place the marks, or dots, on the paper according to a variety of geometrical patterns such that a group of dots and dotless blank spots when seen by the eye gives a rendition of an intermediate tone between the initial paper stock, usually white, and total ink coverage, or solid density. In the ensuing paragraphs, discussions will be made in terms of white paper stock; it is understood that white paper stock is used as an illustration and not as a limitation of any invention.
An obvious problem arises when the resolution of the dot matrix on the paper is not very high, for example, 100 dpi or less, and the geometrical patterns being used become particularly visible to the eye. In this case the viewer is distracted from the image being represented by the image artifacts of geometrical patterns themselves and perceives the impression of an image of poor quality. The obvious solution to this problem is to work at very high resolutions, for example, 300 dpi or greater, so that those artifacts are less perceived and their negative effects become less glaring.
In 1976, Robert W. Floyd and Louis Steinberg published a paper in the Proceedings of the S.I.D., Vol. 17/2, entitled “An Adaptive Algorithm for Spatial Greyscale”. In it they described an algorithm which they called “Error Diffusion” (ED). This algorithm provides a method for a gray scale with bilevel devices, that is, dot or no dot. According to this prior art scheme, gray level data representing a continuous tone image is subjected to a thresholding process whereby gray levels above a chosen threshold, for example, 50%, are assigned a dot to be printed and those below are not assigned a dot. The coarseness of this method is compensated for by keeping, track of the intensity error due to this process and propagating this error in specified amounts to adjacent picture elements, or “pixels”, to weight the pixels in the thresholding process. This approach results in a more accurate representation of a grey tone over a small area encompassing several dots. Hence, perception of the image artifacts is diminished, and a better quality gray scale image is generated. Furthermore, the ED algorithm retains good edge quality in generated images to minimize the inherent “fuzziness” of a bilevel generated image.
It has been observed by subsequent investigators that the ED approach, even at resolutions of 300 dpi, still suffers severe limitations in producing quality images. Specifically, with the ED approach in producing gray scale images, the dots of a binary printer are of greater diameter than the separation of the addressable points; therefore, they can overlap. This overlapping then produces a nonlinear response to the representation of the grey tone discretization. In addition, the thresholding process also introduces undesirable patterns or textures that are visible to the eye when certain grey levels are printed.
U.S. Pat. No. 4,680,645 entitled, “Method for rendering grayscale images with variable dot sizes,” by G. J. Dispoto. L. R. Mather, and J. D. Meyer, describes a method of halftoning that uses error diffusion with variable dot sizes to improve printing results. In this prior art approach, a lookup table is constructed with a list of dot sizes that a printer can produce, and the corresponding gray levels. For the gray level in an input image pixel, the nearest reproducible gray level is located in the lookup table and designated as the output gray level. The error between the input gray level and the output gray level is distributed to its surrounding pixels. This results in a halftone pattern with minimum contrast (i.e., at any particular gray level, the halftone pattern consists of the closest two dot sizes that will reproduce this gray level). White pixels are eliminated as early as possible when a gray ramp from white to black is printed.
An extension of using error diffusion with variable dot sizes that results in maximum contrast is described in U.S. Pat. No. 5,615,021 entitled, “Print N-tone images with imperceptible dots,” by Q. Lin.
FIG. 8
depicts the halftoning process described in U.S. Pat. No. 5,615,021. Suppose the input image is represented at some resolution D dots per inch (dpi). The first step is to halftone the image using multilevel error diffusion, whereby each pixel in image A is represented using more than 1 bit. Next, each pixel in image A is mapped to a binary superpixel, or block of pixels, wherein the dots are clustered together. The output is a binary halftone image rendered at a higher resolution than the input image. The dots are clustered together, but the dot cluster centers are spaced regularly.
One drawback of this approach is that the approach leads to a halftone of dot clusters arranged on a regular, rectangular lattice. This arrangement prevents the full utilization of the maximum capacity for rendering details that a printer is capable of. In other words, in the language of printing, this approach effectively reduces the “lines per inch” (lpi) of the print. In some aspects of appearance, this may resemble the results of a traditional clustered-dot halftoning. For that reason, it is reasonable to expect this prior art approach may lead to moiré{acute over ( )} artifacts, which is undesirable.
Based on the foregoing, there remains a need for a method and system for halftoning images that overcomes the disadvantages set forth previously.
SUMMARY OF THE INVENTION
A halftoning method and system that employs maximum contrast error diffusion with partial dots. According to one aspect of the present invention, a halftoning algorithm is provided that uses partial dots in highlight areas, and transitions to full dots in the mid-tone and shadow areas, thereby resulting in no visible dots in the printed image. Preferably, the partial dots are generated by utilizing a sub-pixel pulse modulation.
According to one embodiment of the present invention, a method of halftoning that uses error diffusion with partial dots is provided. First, an input picture element (input pixel) that has a picture level (e.g., gray level) is received. Next, a reproducible gray level is generated based on the gray level of an input pixel. Then, a corrected gray level is generated based on the gray level of an input pixel and an error amount (e.g., error propagated or diffused from adjacent areas or pixels). A determination is made whether the corrected gray level is in a predetermined relationship with a threshold. When the corrected gray level is in a predetermined relationship with the threshold, the reproducible gray level (partial dot) is provided as output. When the corrected gray level is not in a predetermined relationship with a threshold, a zero value is provided as output. It is noted that the output gray level and the corrected gray level are provided to an error distribution module for calculating an error and for propagating or diffusing the error to future adjacent areas or pixels.


REFERENCES:
patent: 4680645 (1987-07-01), Dispoto et al.
patent: 5077615 (1991-12-01), Tsuji
patent: 5359433 (1994-10-01), Nagase
patent: 5615021 (1997-03-01), Lin
patent: 5748336 (1998-05-01), Kakutani
patent: 5812744 (1998-09-01), Allebach et al.
patent: 6108450 (2000-08-01), Ueda
patent: 6602003 (2003-08-01), Kakutani
patent: 0398763 (1990-11-01), None
patent: 0719033 (1996-06-01), None
patent: WO 93/26116 (1993-12-01), None
Ulicheny, Robert “D

Affiliated with

Also associated with

Rating

Error diffusion with partial dots method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error diffusion with partial dots method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error diffusion with partial dots method and system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3318470