Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1994-08-03
2002-02-12
Bella, Matthew C. (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S237000, C382S299000, C358S426010, C358S445000, C358S447000, C358S451000
Reexamination Certificate
active
06347159
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 combined screening and error diffusion technique.
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 level” is used to described such data for both black and white and color applications. Standard printers print in a limited 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 limited 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 screening, dithering or halftoning. In such arrangements, over a given area, each grey level pixel within the area is compared to one of a set of preselected thresholds. The set of thresholds comprises a matrix of threshold values or a halftone cell.
FIG. 1
illustrates a block diagram of a typical screening circuit. In this circuit, an unmodified image or video signal is fed into a modulation circuit
1
with a screen value from a halftone screen matrix to produce a modified signal. The modified signal is then thresholded by a binarization circuit
3
to produce a binary output. The binary output represents either the ON or OFF characteristic of the processed pixel.
In this process, the sampled image picture elements are compared with a single threshold, and a black/white decision is made. However, the threshold relationship is modified by modulating the image data with the screen data. The screen data is selected in sequential order from a two-dimensional matrix defined as a halftone cell threshold set. The set of screen values and the arrangement therein determine the grey scale range, frequency, angle, and other properties of the halftone pictorial image.
The effect of such an arrangement is that, for an area where the image is grey, some of the thresholds within the matrix will be exceeded, while others are not. In the binary case, the portions of the matrix, or cell elements, in which the thresholds are exceeded are printed as black, while the remaining elements are allowed to remain white or vice-versa. The effect of the distribution of black and white over the cell is integrated by the human eye as grey.
However, typical screening presents problems in that the amount of grey within an original image is not maintained exactly over an area because the finite number of elements inside each halftone cell only allows the reproduction of a finite number of grey levels. The error arising from the difference between the threshold value and the actual grey level value at any particular cell is, typically, thrown away. This results in loss of image information and creates significant image artifacts, such as banding or false contours that can be seen in smooth image areas. In banding, the image input grey level varies smoothly over an area while the halftoned image has to make a transition from one halftone dot (grey level) to another. This transition can clearly be seen as a band or contour running through smooth image parts.
Another problem associated with screening grey images is the trade-off between the screen frequency and the number of grey levels available. Although it is desirable to use a high frequency screen, the number of grey levels available decreases as the screen frequency increases. One method which has been proposed to increase the number of grey levels as the screen frequency increases is set forth in U.S. Pat. No. 5,317,653 to Eschbach et al. The entire contents of U.S. Pat. No. 5,317,653 are hereby incorporated by reference.
In this method, the grey image is first reduced to a small number of grey levels with error diffusion, and then a line screen with a small number of grey levels and a high frequency is used. This two step process binarizes the image.
However, to implement such a method, a print engine or system requires a multi-level error diffusion process followed by screen thresholding. Typically, the image processing architecture for such machines do not have such a capability. Therefore, it is desirable to achieve the same results, but without departing from the typical image processing architecture of printing system.
SUMMARY OF THE PRESENT INVENTION
A first aspect of the present invention is a method of reducing a number of levels in a multi-level grey scale pixel value representing a pixel and diffusing an error generated from reducing the number of levels. The method receives the multi-level grey scale pixel value having a first resolution. The multi-level grey scale pixel value is screened. The number of levels in the screened multi-level grey scale pixel value is then reduced and an error value is generated as a result of the reduction process. The error value is diffused to multi-level grey scale pixel values of adjacent pixels.
A second aspect of the present invention is a system for reducing a number of levels in a multi-level grey scale pixel value representing a pixel and diffusing an error generated from reducing the number of levels. The system includes input means for receiving the multi-level grey scale pixel value, the multi-level grey scale pixel value having a first resolution. Screening means screens the multi-level grey scale pixel value, and means reduces the number of levels in the screened multi-level grey scale pixel value. Error means generates an error value as a result of the reduction. Error diffusing means diffuses the error value to multi-level grey scale pixel values of adjacent pixels.
A third aspect of the present invention is a method of generating an error value. The method screens a multi-level grey scale pixel value representing a pixel having a first resolution and thresholds the multi-level grey scale pixel value representing the pixel having the first resolution. An error value is generated as a result of thresholding the multi-level grey scale pixel value. The error value has a second resolution lower than the first resolution.
A fourth aspect of the present invention is a system for generating an error value. The system includes screening means for screening a multi-level grey scale pixel value representing a pixel having a first resolution and threshold means for the multi-level grey scale pixel value representing the pixel having the first resolution. Error means generates the error value as a result of thresholding the multi-level grey scale pixel value. The error value has a second resolution lower than the first resolution.
A fifth aspect of the present invention is a printing system for rendering marks on a receiving medium. The system includes receiving means for receiving a multi-level grey scale pixel value representing a pixel having a first resolution and screening means for screening the multi-level grey scale pixel value. Interpolation means converts the screened multi-level grey scale pixel value to a second resolution, the second resolution being higher than the first resolution. Binarization means binarizes the converted multi-level grey scale pixel value so as to output a binary signal and an error value, the error value having a resolution equal to the first resolution. Diffusing means diffuses the error
Metcalfe David J.
Shiau Jeng-Nan
Williams Leon C.
Bella Matthew C.
Henn David E.
Nickerson Michael
LandOfFree
Method and system for processing image information using... 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 processing image information using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for processing image information using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960423