Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1994-08-03
2002-07-30
Bella, Matthew (Department: 2721)
Image analysis
Image compression or coding
Quantization
C382S299000, C358S426010, C358S451000
Reexamination Certificate
active
06427030
ABSTRACT:
FIELD OF THE PRESENT INVENTION
The present invention is directed to the reduction of the number of levels of a multilevel grey scale pixel value representing an image to a number of levels renderable by an output device utilizing dynamic error diffusion. More specifically, the present invention is directed to a dynamic error diffusion process wherein the error diffusion weighting coefficients are dynamically established based on a physical characteristic of the image data being processed.
BACKGROUND OF THE PRESENT INVENTION
Image information, be it color or black and white, is derived by scanning, initially at least, in a grey level format containing a large number of levels; e.g., 256 levels of black and white and more than 16 million levels or color, thus, grey level image data may be presented as a large multi-level value. The large multi-level value is usually unprintable by standard printers since standard printers print a limited number of levels, either a spot or no spot in a binary printer, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is necessary to reduce the multi-level grey image data to a limited number of levels so that it is printable.
There are many methods of rendering multi-level input grey images on a low level output device. One standard method of converting grey level pixel image data to binary level pixel image data is through the use of dithering or halftoning processes. 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 effect of such an arrangement is that, for an area where the image is grey, some of the thresholds will be exceeded, while others are not. In the binary case, the pixels in the area in which the threshold is exceeded are printed as black, while the remaining pixels are allowed to remain white. The effect of the distribution of black and white over the the given is integrated by the human eye as grey. Dithering presents problems, however, in that the amount of grey 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 grey level value at any particular cellpixel is simply thrown away. This results in loss of image information.
Algorithms that convert grey images to binary or other number of level images while attempting to preserve the local density exists include among them error diffusion. Error diffusion can render complex images that contain a mixture of text and picture data reasonably well. The utilization of error diffusion can eliminate the need to have image segmentation which identifies which image data, pixel, corresponds to text and which image data, pixel, corresponds to a picture. Normally, this identification process is necessary so that the picture aspect of the document can be screened and the text aspect of the document can be threshold.
An example of a typical error diffusion process is fully described in U.S. patent application, Ser. No. 07/600, 542, entitled “Method for Image Conversions With Error Diffusion.” The entire contents of this U.S. patent application, Ser. No. 07/600, 542, are hereby incorporated by reference. More examples of error diffusion processes with modifications to the error calculation and weight allocation are fully described in U.S. Pat. No. 4,924,322 to Kurosawa et. al., U.S. Pat. No. 4,339,774 to Temple, and U.S. Pat. No. 4,955,065, to Ulichney. The entire contents of U.S. Pat. No. 4,924,322, U.S. Pat. No. 4,339,774, and U.S. Pat. No. 4,955,065 are hereby incorporated by reference.
Error diffusion attempts to maintain grey by making the conversion from grey pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference between the grey level pixel value and the threshold is then forwarded to a selected group of neighboring pixels, in accordance with a weighting scheme.
FIG. 1
illustrates a typical error diffusion circuit. As illustrated in
FIG. 1
, image data is fed into a threshold circuit
1
along with a threshold value. The threshold circuit
1
compares the image data with the threshold value to determine whether the image data is equal to or greater than the threshold value. In a binarization case, if the image data is greater than or equal to the threshold value, the threshold circuit
1
outputs image data equal to a logical 1 value. On the other hand, if the image data is less than the threshold value, the threshold circuit
1
outputs a logical 0 value.
In this thresholding process, an error value is generated by the threshold circuit
1
. This error value is fed into an error distribution circuit
3
wherein the error term is multiplied by a plurality of weighting coefficients, wherein each weighting coefficient is associated with a certain pixel that is to receive a portion of the error value. In other words, the error distribution circuit
3
distributes the error generated by the threshold circuit
1
to pixels which are adjacent to the pixel being presently processed according to a set of weighting coefficients.
As noted above, typically when utilizing error diffusion, there is not a need to utilize image segmentation. This is due to the fact that typical error diffusion can render an image of acceptable quality not withstanding the characteristics of the image data being processed. This is due in part to the fact that the error from the threshold process is distributed to adjacent or downstream pixels. However, an important aspect of the error diffusion process is the weighting of this distribution of the error to neighboring pixels to ensure the rendering of an acceptable quality image.
FIGS. 7-9
show known distribution and weighting schemes. The distinction between the weighting and distribution schemes shown is in the size of the error distribution matrix or number of neighboring pixels over which error is distributed, which also requires somewhat different weighting schemes. In these Figures, as well as in other Figures showing error diffusion matrices, each cell shows the weighting value.
In conventional image rendering devices utilizing error diffusion, the set of weighting coefficients for the error diffusion process is selected in the design stage wherein the same weighting coefficients are used in processing all image types. A problem noted with the selection of a single set of error diffusion weighting coefficients for a standard error diffusion algorithm is production of different artifacts in regions of differing image types or image processing operations. These artifacts can affect the appearance quality of the image being rendered because the selection of the set of weighting coefficients results from the balancing of desired image quality for a particular image type and the actual image quality generated by the image rendering device. In other words, one set of weighting coefficients may produce a high quality image for halftone images, but render an image of lower quality for text data; whereas another set of weighting coefficients may render a high quality image for continuous tone image data, but render an image of lower quality for halftone image data. Thus, it is desirable to utilize an error diffusion process which is capable of optimizing the image quality for all different types of image characteristics and image types.
SUMMARY OF THE PRESENT INVENTION
One 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 image characteristic of a pixel within an image and thresholds the pixel. An error value is generated as a result of the threshold process. A set of weighting coefficients is selected from a plurality of possible weighting coefficient sets based on the image characteristic of the pixel and the error value is diffused to adjacent pixels based on the selected set of weighting coefficients.
A second aspect of the present
Metcalfe David J.
Shiau Jeng-Nan
Williams Leon C.
Bella Matthew
Xerox Corporation
LandOfFree
Method and system for image conversion utilizing dynamic... 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 image conversion utilizing dynamic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for image conversion utilizing dynamic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861698