Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-09-23
2003-02-11
Wu, Jingge (Department: 2723)
Image analysis
Image compression or coding
Quantization
Reexamination Certificate
active
06519367
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains to the art of image processing systems and, more particularly, to error diffusion techniques for rendering multibit graylevel images containing continuous tone, text, halftones etc. to a binary pattern of dots for the purpose of printing or displaying on an imaging device. More specifically, the present invention is directed to a dynamic error diffusion process for hybrid screening wherein the error diffusion weighting coefficients are dynamically calculated based on a physical characteristic of the image data being processed.
2. Description of Related Art
BACKGROUND OF THE PRESENT INVENTION
Image information, be it color or black and white, is derived by scanning a large number of gray levels; e.g., 256 levels of black and white and more than 16 million levels of color, gray level image data 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 gray image data to a limited number of levels so that it is printable.
There are many methods of rendering multi-level input gray images on a low level output device. One standard method of converting gray 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 gray 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 gray, 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 given area is integrated by the human eye as gray. Dithering presents problems, however, in that the amount of gray 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 gray level value at any particular cell pixel is simply thrown away. This results in loss of image information. However, proper screen design with more graylevels could result in good output image quality.
Algorithms that convert gray images to binary or other number of level images while attempting to preserve the local density include error diffusion processing. 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, i.e., pixel, corresponds to text and which 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 thresholded.
An example of a typical error diffusion process is fully described in U.S. Pat. No. 5,226,094 to Eschbach entitled “Method for Making Image Conversions With Error Diffusion”, the entire contents of which 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 gray by making the conversion from gray 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 gray level pixel value and the threshold is then forwarded to a selected group of neighboring pixels, in accordance with a weighting scheme.
Modern digital images increasingly include both text and picture images, thus, attempts have been made to develop an algorithm that produces superior results on input images containing both text/edge segments and contone/halftone segments. For example,
FIG. 1
shows such an image. The image is generally designated
10
. Included in the image are text segments
12
,
14
, contone segment
16
and halftone segment
18
. Preferably a system would analyze the input image
10
, recognize the different segments
12
-
18
, and apply the proper processing to each segment. It is typically desirable to apply a high modulation screen to input image data representative of pictorial elements and a low modulation screen plus an error diffusion technique to input image data representative of text/edge elements. It should be noted that the segments could also include halftones further classified by frequency, edge segments, or background segments for example.
One particular method discussed in U.S. Pat. No. 5,317,653, to Eschbach, is assigned to the assignee of the present invention, and is incorporated herein by reference. Eschbach discloses essentially a hybrid or two step approach. A screen is applied to the input image, then that result is error diffused. In such a hybrid screening approach, a conventional screen is applied to the input video resulting in modified video. Unfortunately, in conventional hybrid screening, one error distribution weight is typically used for the entire image. That is, regardless of which segment the method is processing, a pre-programmed flow of error diffused pixels continues downstream. Artifacts from this “overflow” become most noticeable in transitional regions especially between high modulation screening (i.e. contone/halftone) and low modulation screening (i.e. text/edge).
However, it would be desirable to provide for the application of a plurality of screens at various modulations to help in rendering complex images containing a mixture of text and pictorials. For example, in an 8-bit video system the modified video after the application of a screen is obtained as:
Modified Video=255
+S−V
Where S is a screen threshold value and V is the input video value. The dynamic range of the modified video of a 100% modulated screen (ranging between 0 and 255 for an 8 bit system) would be 0→511. On the other hand, use of a 0% modulation screen (i.e. no screening, only error diffusion with a threshold level of 128), results in the modified video having a dynamic range of 128→383. Other intermediate modulations result in a dynamic ranges from X→Y where 0<X<128, and 511>Y>383.
Ideally, for better rendition of different image segments, the pictorials (continuous tone and halftone) need to be “purely” screened (conventional screening) and text/edges need to be error-diffused. While trying to switch between these two rendering schemes based on segmentation classes, image artifacts are generated due to misclassifications in the transition regions. The hybrid screening approach suggested by Eschbach helps in avoiding artifacts by applying screen and performing error-diffusion everywhere. This though, results in “noisy looking” pictorials due to error-diffusion. Thus, a need exists for a method to apply “pure” screen on pictorials and error-diffusion on text/edges without causing any noticeable image artifacts from propagating error selectively in the transition regions.
An improvement over conventional hybrid screening systems disclosed in commonly assigned U.S. application Ser. No. 08/285,324, is assigned to the assignee of the present invention and incorporated herein by reference. The improvement therein pertains to the set of weighting coefficients used by the error diffusion process. While some error diffusion systems used a fixed set of weighting coefficients selected in the design stage for use on all image types, the Ser. No. 08/28
Cook William A.
Nagarajan Ramesh
Tse Francis K.
Fay Sharpe Fagan Minnich & McKee LLP
Wu Jingge
Xerox Corporation
LandOfFree
Method and system for propagating selective amounts of error... 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 propagating selective amounts of error..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for propagating selective amounts of error... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172159