Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1996-09-24
2001-05-15
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S168000, C382S172000
Reexamination Certificate
active
06233360
ABSTRACT:
FIELD OF THE PRESENT INVENTION
The present invention relates to the conversion of images from multi-level grey scale pixel values to a reduced number of levels pixel values. More specifically, the present invention relates to the conversion of multi-level grey scale pixel values to a reduced number of levels pixel values using a high addressable error diffusion technique with adaptive white and black reference values
BACKGROUND OF THE PRESENT INVENTION
Image information, be it color or black and white, is commonly derived by scanning, initially at least, in a grey level format containing a large number of levels, e.g.: 256 levels for black and white and more than 16 million (256
3
) levels for color. This multi-level format is usually unprintable by standard printers.
The term “grey lever” is used to described such data for both black and white and color applications. Standard printers print in a limed number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Since grey level image data may be represented by very large values, it is necessary to reduce grey level image data to a led number of levels so that it is printable. Besides grey level image information derived by scanning, certain processing techniques, such as computer generation, produce grey level pixel values which require such a conversion.
One standard method of converting grey level pixel image data to binary level pixel image data is through the use of error diffusion. This process, however, assumes that a printer is an ideal device wherein black pixels and white pixels can be rendered not withstanding their effective size. A conventional error diffusion process will be discussed below.
In a conventional error diffusion process, input grey video is inputted to an adder wherein slowscan error, which represents error from the processing of the previous scanline of pixels, stored in a FIFO is added to the input grey video. Moreover, fastscan error from an error distribution circuit is also added to the input grey video at the adder. The fastscan error from the error distribution circuit represents the error from processing the previous pixel in the same scanline. The modified input grey video (Pix
N
) is then fed to a comparator which compares the modified input grey video with a threshold value. Based on the comparison with the threshold value, the comparator outputs a binary output of either 1 or 0. The modified input grey video is also fed to a subtraction circuit and a multiplexer. The subtraction circuit generates a value representative of the difference between a black reference value and the modified input grey video value. This difference is also fed to the multiplexer. The multiplexer selects either the difference value or the modified input grey video value as the pixel error for the presently processed pixel based on the binary output from comparator. This pixel error is fed to the error distribution circuit which utilizes a plurality of weighting coefficients to distribute the error to various adjacent pixels.
However, there is a problem when using conventional error diffusion in that the reference values used for calculating and propagating the error are assumed; ie., the “black” and “white” reference values are assumed which in a typical case would be 255 and 0, respectively, for a write-black printer processing an image having 256 possible grey levels per pixel. Using such an assumption yields undesirable results from an image with a background value less than 255.
It is noted that in a white-black system the original image values are inverted prior to processing thus, the white level for the original image data would be 255, whereas in the write-black system the same white level would be converted to 0. This inversion technique is commonly used in the printing art.
In an image with a background value less than 255 results in an image that is “speckled” with black dots when the image is processed by an error diffusion technique that has made the above assumptions for the reference “black” and “white” values. This artifact is typically compensated for by utilizing a tonal-reproduction correction curve look-up table (TRC LUT) to alter the grey video signal prior to being processed by the conventional error diffusion routine. However, this technique has several disadvantages, namely, a TRC LUT (random access memory) is relatively expensive if it is being utilized in a low-cost digital reprographic machine and there may not be enough time to download the updated TRC values on a scanline-by-scanline basis due to system time constraints.
Therefore, it is desirable to have an error diffusion technique which avoids the generation of “speckled” image and also does not rely on a TRC LUT compensation method. The present invention provides an error diffusion routine that modifies the “black” and “white” reference values based on knowledge of the image's background value and black reference value.
SUMMARY OF THE PRESENT INVENTION
A first aspect of the present invention is a method of diffusing an error generated from thresholding a grey level value representing a pixel. The method determines an actual background value and an actual black reference value for an image to be thresholded; receives the grey level value representing the pixel the grey level value having a first resolution; converts the grey level value to a second resolution, the second resolution being higher than the first resolution; thresholds the converted grey level value; generating an error value as a result of a threshold determination using the determined actual background and black reference values, the error value having a resolution corresponding to the first resolution; and diffuses the error value to grey level values representing adjacent pixels.
A second aspect of the present invention is a system for diffusing an error generated from thresholding a grey level value representing a pixel. The system includes histogram means for determining an actual background value and an actual black reference value for an image to be thresholded; input means for receiving the grey level value representing the pixel, the grey level value having a first resolution; high addressability means for converting the grey level value to a second resolution, the second resolution being higher than the first resolution; threshold means for thresholding the converted grey level value; error means for generating an error value as a result of a threshold determination by the threshold means using the actual background value and black reference value determined by the histogram means, the error value having a resolution corresponding to the first resolution; and error diffusing means for diffusing the error value to grey level values representing adjacent pixels.
A third aspect of the present invention is a method of generating an error from a threshold process. The method determines an actual background value and an actual black reference value for an image to be thresholded; thresholds a grey level value of a pixel having a first resolution; and generates an error value as a result of thresholding the grey level value using the determined actual background and black reference values, the error value having a second resolution, the second resolution being lower than the first resolution.
A fourth aspect of the present invention is a system for generating an error from a threshold process. The system includes histogram means for determining an actual background value and an actual black reference value for an image to be thresholded; threshold means for thresholding a grey level value of a pixel having a first resolution; and error means for generating an error value as a result of thresholding by the threshold means using the actual background value and black reference value determined by the histogram means, the error value having a second resolution, the second resolution being lower than the first resolution.
A fifth aspect of the present invention is
Feng Xiao-fan
Metcalfe David J.
Newell John T.
Triplett Roger L.
Nickerson M J.
Novik Dmitry A.
Tran Phuoc
Xerox Corporation
LandOfFree
Method and system for hybrid error diffusion processing of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for hybrid error diffusion processing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for hybrid error diffusion processing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472923