GB2294174A

GB2294174A - Digital gray scale image halftoning including error diffusion and selective image adjustment

Info

Publication number: GB2294174A
Application number: GB9520882A
Authority: GB
Inventors: Hwai Tzuu Tai; Thomas Joseph Wetzel
Original assignee: Eastman Kodak Co
Current assignee: Eastman Kodak Co
Priority date: 1994-10-14
Filing date: 1995-10-12
Publication date: 1996-04-17
Anticipated expiration: 2015-10-12
Also published as: GB9520882D0; GB2294174B; DE19536108A1

Description

2294174

POST MODULATION GRAY SCALE ERROR DIFFUSION BASED METHOD OF UNIFIED DOCUMENT IMAGE RENDERING Field of the Invention

The present invention relates to the field of encoding pictorial imagery for reproduction on display or printing systems, and more particularly, to method and apparatus for digital gray scale halftoning of images. Background of the Invention

In the area of digital printing (terms such as "printing", "printer" and the like are used herein to encompass both printing and displaying), gray level has been achieved in a number of different manners. The representation of gray level by binary printers has been the object of a variety of algorithms. Binary printers are capable of making a mark, usually in the form of a dot, of a given, uniform size and a specified resolution. It has been common to place the marks according to a variety of geometrical patterns such that a group of marks when seen by the eye gives a rendition of an intermediate tone between the density of the background (usually white paper stock) and total coverage, or solid density.

Continuous tone images contain an apparent continuum of gray levels. As an approximation to continuous tone images, pictorial imagery has been represented via binary halftone technologies. In order to record or display a halftone image with a scanning system, one cell or super pixel of the printing surface consists of a j by k (expressed "jxk") matrix of sub-elements, where j and k are positive integers. A halftone image is reproduced by printing the respective sub-elements or leaving them blank. That is, by suitably distributing the printed 10210.DOC/3-Oct-95 -2 marks. In binary halftone technologies, each subelement, or dot is the same size.

In gray scale writing systems, different dot sizes or dot densities can be developed by using either time modulation or intensity modulation. Exposure systems such as laser or LED systems provide multiple choices of dot densities at each pixel that can be deployed in gray scale halftoning. These multiple choices of dot densities give more design freedom for the design of gray scale dot formation than is pos3ible with a binary exposure system. The variation of dot pattern design and dot level selection has enriched the art of image rendering in gray scale halftoning.

Documents can be categorized into three different image types: text and line art, continuous tone, and halftone. Normal documents are usually composites of these three basic image types. Human expectations of the image reproduction characteristics are different for the different image types. Continuous tone and halftone documents require tone scale preserving methods that can reproduce a large number of gray levels. In digital systems, halftone images need special processing to minimize Moir& patterns that can result from sample aliasing during the scanning process. Text images require fewer gray levels and typically have an S-shaped tone reproduction curve. The sharpness of the text image must be preserved.

The image-type specific processing has been practiced extensively within the page description language in the electronic document creation process.

A photograph is normally scanned in, manipulated, and then rendered using suitable halftoning methods having accurate tone reproduction, while text is created 10210.DOC/3-Oct-95 directly from the designed font with artistic styles before they are merged into a document. When a hard copy of this electronic document is produced on mediums like paper or film, the image quality can be 5 optimized.

However, in the reprographic environment of the digital copy process, the document originates in hard copy form; not in electronic form. The scanner itself cannot distinguish different image types that are embedded in the document. This processing must be performed on the scanned digital image. Many efforts in image segmentation and image recognition research have been performed to separate text, continuous tone and halftone areas within a document. They are successful to a certain extent (not 100%), and mostly with non- overlapping areas within a document. Image segmentation methods can fail in more complex documents which are becoming more typical in the reprographic environment. Further, image segmentation methods tend to create hard transitions between image, types. That transition can create an unnatural appearance at boundaries. It is preferable to have a unified rendering approach, which can modify its rendering characteristics according to the image type with gradual transition at boundaries between image types. Also, complex document areas (i.e., text embedded within a photograph) are often misclassified, which results in reproduction artifacts. This kind of image artifact is intolerable in a good document reproduction system.

In the electrophotographic process, it is desirable to have large flat areas of the image rendered with a screen structure that can produce more gradations and reduce the impact of artifacts from the printing process. It is therefore preferable to have 10210.DOC/3-Oct-95 flat areas rendered with a screen structure and halftone and text areas rendered without the screen structure. Summary of the Invention

It is an object of the present invention to provide a gray scale, error diffusion based unified document rendering method that does not suffer from the artifacts associated with hard decision segmentation described above.

It is another object of the present invention to improve the picture rendition of a gray scale error diffusion process with the introduction of a screen structure, while maintaining the sharpness of text'and halftone regions.

It is also an object of the present invention to provide a graceful transition between image types without introducing segment artifacts.

- It is yet another object of the present invention to provide a gray scale, error diffusion based unified document rendering method that does not suffer from the artifacts associated with hard decision segmentation described above, and which modifies the rendered (output) pixel's value after error diffusion, instead of the original pixel's value, at certain designated locations such as in the lower contrast image area. Thus, a designed screen structure can be placed in a specified location (such as in low contrast image areas) without modification by error diffusion. The error diffusion process, in keeping the image's mean value constant, will then calculate and distribute the error to the neighboring pixels. The designated screen dots then become the kernels (centers) of the half-tone dot in which a variety of dot shapes can be formed by the error diffusion process.

10210.DOC/3-Oct-95 The present invention also provides for modifying, after error diffusion, a digitized image received as signals representing input pixel values for a plurality of pixels. The need for adjustment of a pixel of interest in a local window of pixels is determined, those pixels determined to need adjustment are adjusted after error diffusion is applied.

In a preferred embodiment, the determination of the need for adjustment of a pixel is effected by calculating an image feature value for the pixel of interest and comparing the calculated image feature value to a predetermined threshold value. The image feature for the pixel of interest may be the edge gradient strength of the local window of pixels or the local contrast of the local window of pixels. The determination of the need for adjustment of a pixel may be further effected by determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value. The adjustment may include modulation of the pixel with a predetermined screen structure.

In another preferred embodiment, the determination of the need for adjustment of a pixel is effected by calculating an image feature value for the pixel of interest and comparing the calculated image feature value to a predetermined threshold value. The image feature for the pixel of interest may be the edge gradient strength of the local window of pixels or the local contrast of the local window of pixels.

The determination of the need for adjustment of a pixel may be further effected by determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value. The adjustment may include modulation of the pixel with a predetermined screen structure.

10210.DOC/3-Oct-95 The invention, and its objects and advantages, will become more apparent in the detailed description of the preferred embodiments presented below.

Brief Description of the Drawings

For a better understanding of the present invention, reference will now be made, by way of example only, to the accompanying drawings in which:

Figure 1 is a block diagram of an apparatus according to the present invention for reproducing an image; Figure 2 is a functional block diagram of the operation of controller 16 of Figure 1 according to a preferred embodiment of the present invention; Figures 3(a), 3(b), and 3(c) are descriptive illustrations of the concept of edge gradient strength; Figures 4(a) and 4(b) are descriptive illustrations of the concept of local contrast index; Figure 5 is a functional block diagram of the operation of controller 16 of Figure 1 according to another preferred embodiment of the present invention; Figure 6 is a functional block diagram of the operation of controller 16 of Figure I according to a further preferred embodiment of the present invention; Figure 7 is a functional block diagram of the operation of controller 16 of Figure I according to a yet another preferred embodiment of the present invention; and Figure 8 is an illustration of the system of Figure 6 in more detail.

10210.DOC/3-Oct-95 Detailed Description of the Invention

Figure 1 illustrates an apparatus which reproduces a document 10, which document may contain one or more areas of different types of images. For example, document 10 may contain areas of text, areas of continuous tone images, and/or areas of halftone images.

The image on document 10 is converted to a series of digital signals representative of the densities of corresponding pixel areas of the document by a conventional scanner 12. These signals are sent to a memory 14. Under the direction of a controller 16, the signals may be modified and provided as gray level signals for each pixel through a frame store 17 to a printer 18 and/or a display 20. Printer 18 and/or display 20 reproduces document 10 by energizing each individual pixel according to the corresponding gray level as modified (or not modified) by controller 16. Memory 14, frame store 17, printer 18, and display 20 are of conventional hardware design. Specific implementation blocks within controller 16 will be described in more detail below and in conjunction with the process of the present invention.

Figure 2 is a functional block diagram of the operation of controller 16 of Figure 1 according to a preferred embodiment of the present invention. Image data from scanner 12 (Figure 1) is applied to a feature calculation functional block 22, whereat an image feature value is calculated in a local window of nxn pixels. In general, an image feature is any image characteristic which can be extracted from the image pixels. For example, image features include density, granularity, line or orientation structure, etc.; and can be represented in the form of histograms, mean values, etc. In the present invention, however, only 10210.DOC/3-Oct-95 those image features which utilize first order pixel statistics (such as edge gradient strength or local contrast) are of interest.

As used herein, the phrase "edge gradient strength" means the difference of neighboring pixel values centered at the pixel of interest. Referring to Figure 3(a), the edge gradient of pixel X in the y direction is the difference between the values of pixel 1 and pixel 2. This can be illustrated as the difference between the two shaded pixel areas shown in Figure 3(b). The edge gradient of pixel X in the x direction is the difference between the values of pixel 3 and pixel 4 in Figure 3(a). This too can be illustrated as the difference between the two shaded pixel areas shown in Figure 3(c). Thus, the edge gradient at X is the greater of edge gradient x and edge gradient y.

The phrase "local contrast" means the pixel value difference between the maximum pixel value and the minimum pixel value in the defined neighborhood of the pixel of interest. Referring to Figures 4(a) and 4(b), X is the pixel of interest. Pixel 1 is the pixel of maximum value in the 5x5 window illustrated, and pixel 2 is the pixel of minimum value in the window. The locations of pixels 1 and 2 will, of course, change from window to window.

Pixels which exhibit small image feature values generally occur in flat field image areas with low contrast and small edge gradient characteristics.

These pixels are the most likely to benefit from adjustments, such as modulation with a predetermined screen structure to reduce the graininess of the flat field area that is typical in electrophotographic systems.

10210.DOC/3-Oct-95 After the image feature value is calculated, it is evaluated at functional block 24 such as, for example, by comparison to a predetermined threshold value. If the image feature value is less than the threshold value, and if the mean (average) pixel value of the defined nxn neighborhood is above the background density (e.g., 0.2 density), an adjustment according to the present invention will be effected at functional block 26 before an error diffusion process is applied at functional block 30 (as illustrated in Figure 2) or after the error diffusion process is applied at functional block 30 (as illustrated in Figure 6). Image areas with higher contrast and/or large edge gradients (such as text or halftones) will not be modulated. Accordingly, such adjustments are applied only to those pixels that have been identified according to the process set forth above. Otherwise, the pixel will not be adjusted.

The modulation or screen structure described herein is only one kind of illustration using a simple address calculation. It can be applied to more complex addressing methods which include the tile or template approach used in ordered dither halftoning as illustrated in Figures 5 and 7.

Selection Of Pixels To Be Modified In this simple address method, the following calculations are performed to determine which pixels will be modified:

(x + y) modulus n = 0, and (x - y) modulus n = 0 where x is the pixel column address, y is the pixel row address, and n is a selected modulus value. The expression (x + y) modulus n = 0 means that the remainder of a value, which is the sum of and y, divided by a value n is zero (i.e., no 10210.DOC/3-Oct-95 remainder). Put another way, if (x + y)/n is an integer, and (x - y)/n is also an integer, then the pixel is selected to be modified. For example:

(100 + 32) modulus 4 = 0, while (100 + 32) modulus 5 = 2.

Similarly with regard to the expression (x - Y) modulus n 0:

(100 32) modulus 4 = 0, while (100 - 32) modulus 5 = 3.

Selection Of The Modulus Value "n" The value of n is selected by the desired screen frequency. The selected value on n adjusts the screen frequency as shown in the following table:

Dot n Screen Screen Pitch Frequencv Anale 400 dpi 4 141 LPI 450/1350 00 dpi 6 94 LPI 450/1350 Pixel Modification The modulation to the pixel can be a fixed offset (a constant value will be added to the original pixel no matter what the original pixel values are); proportional to the pixel value (a fixed percentage is added to the pixel); or any general function of the pixel value (such as a nonlinear function of the original pixel value). The modulation applied must preserve the mean value of the image over a small area. For example, when (x - y) modulus 4 equals zerof a constant gray value of 25 is added along a 135 angle. When (x + y) modulus 4 equals zero, a constant gray value of -25 is added along a 450 angle.

Gamma correction is provided at function block 28 to modify the pixel value so that the pixel 10210.DOC/3-Oct-95 will be marked with a correct dot density in the output device. Gamma correction is a well known operation to persons skilled in the art. If the pixels are gamma-corrected, different corrections may be applied to the pixels of flat field and/or low contrast image areas than are applied to high contrast and/or large edge gradient image areas.

Figure 8 illustrates the post-modulation system in somewhat more detail. Assume that the 8-bit representation X of the value of an original pixel is 150 out of a possible 255 levels. Assume further the there is an accumulated error Xe value of 25. The unmodified pixel value X=150 is added at 32 to the accumulated error value Xe=25 to obtain a summed value of 175.

A thresholder 34 renders a lower-bit signal Y from the 8-bit input, based on the predetermined threshold values Tl, T2, etc. for example, to render a 2-bit signal, there would be three threshold values, such as, say, T1=64, T2=128, and T3=192. Thus, in the example, an output value of Y=2 is rendered for the current pixel of original value X=150, and modified value X=175, by the thesholding process.

In the case that there is no output pixel adjusting signal from local image structure analysis operation 36, the rendered 2-bit pixel value Y of 2 is output to an output image pixel box 38 of Figure 6.

An undistributed error E of 15 occurred due to the output value Y of 2. That is, the 2-bit value Y of 2 represents an 8-bit value of 160 determined as follows:

(192-128)/2 + 128 = 160, and the difference between 175 and 160 is 15. This error E of 15 is then distributed at 32 as a normal error diffusion process.

10210.DOC/3-Oct-95 However, in the case that there is an output pixel adjusting signal from local image structure analysis operation 36, the rendered 2-bit pixel value Y of 2 is modified to another output value, for example Y=3. The rendered pixel value Y of 3 is then inputted to output image pixel box 38 for the current pixel. In so doing, the screen structure is placed in a specified location without modification by the error diffusion.

Once again, an error occurred at the current pixel, this time due to the output value Y of 3. The 3-bit value Y=3 represents an 8-bit value of 160 determined as follows: (255-192)/2.+ 192 = 223.5, and the difference between 175 and 223.5 is 48.5. This error E of -48.5 is then distributed at 32 as a normal error diffusion process.

The invention has been described in detail with particular reference to preferred embodiments thereof, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention.

10210.DOC/3-Oct-95

Claims

CLAIMS:

1. A method for modifying a digitized image received as signals representing input pixel values for a plurality of pixels, said method comprising the steps of:

determining the need for adjustment of a pixel of interest in a local window of pixels; adjusting those pixels determined to need adjustment; and applying error diffusion to the adjusted and non-adjusted pixels.

2. A method as set forth in Claim 1, wherein the determination of the need for adjustment of a pixel is effected by:

calculating an image feature value for the pixel of interest; and comparing the calculated image feature value to a predetermined threshold value.

3. A method as set forth in Claim 2, wherein the image feature for the pixel of interest is the edge gradient strength of the local window of pixels.

4. A method as set forth in Claim 2, wherein the image feature for the pixel of interest is the local contrast of the local window of pixels.

5. A method as set forth in Claim 2 wherein the determination of the need. for adjustment of a pixel is further effected by determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value.

6. A method for modifying a digitized image received as signals representing input pixel values for a plurality of pixels, said method comprising the steps of:

10210.DOC/3-Oct-9= applying error diffusion to the received image signals; determining the need for adjustment of a pixel of interest in a local window of pixels; and after error diffusion, adjusting those pixels determined to need adjustment.

7. A method as set forth in Claim 6, wherein the determination of the need for adjustment of a pixel is effected by:

8. A method as set forth in Claim 7, wherein the image feature for the pixel of interest is the edge gradient strength of the local window of pixels.

9. A method as set forth in Claim 7, wherein the image feature for the pixel of interest is the local contrast of the local window of pixels.

10. A method as set forth in Claim 7 wherein the determination of the need for adjustment of a pixel is further effected by determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value.

11. Apparatus for modifying a digitized image received as signals representing input pixel values for a plurality of pixels, said apparatus comprising:

means for determining the need for adjustment of a pixel of interest in a local window of pixels; means for adjusting those pixels determined to need adjustment; and 10210.DOC/3-Oct-95 means for applying error diffusion to the adjusted and non-adjusted pixels.

12. Apparatus as set forth in Claim 11, wherein the means for determining the need for adjustment of a pixel includes:

means for calculating an image feature value for the pixel of interest; and means for comparing the calculated image feature value to a predetermined threshold value.

13. Apparatus as set forth in Claim 12, wherein the image feature for the pixel of interest is the edge gradient strength of the local window of pixels.

14. Apparatus as set forth in Claim 9, wherein the image feature for the pixel of interest is the local contrast of the local window of pixels.

15. Apparatus as set forth in Claim 12, wherein the means for determining the need for adjustment of a pixel further comprises means for determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value.

16. Apparatus for modifying a digitized image received as signals representing input pixel values for a plurality of pixels, said apparatus comprising:

means for applying error diffusion to the received image signals; means for determining the need for adjustment of a pixel of interest in a local window of pixels; and means, applicable after error diffusion, for adjusting those pixels determined to need adjustment.

10210.DOC/3-Oct-95

17. Apparatus as set forth in Claim 16, wherein the means for determining the need for adjustment of a pixel includes:

means for calculating an image feature valu for the pixel of interest; and means for comparing the calculated image feature value to a predetermined threshold value.

18. Apparatus as set forth in Claim 16, wherein the image feature for the pixel of interest is the edge gradient strength of the local window of pixels.

19. Apparatus as set forth in Claim 16, wherein the image feature for the pixel of interest is the local contrast of the local window of pixels.

20. Apparatus as set forth in Claim 16, wherein the means for determining the need for adjustment of a pixel further comprises means for determining if the mean pixel value of the local window of pixels is greater than a predetermined background density value.

10210.DOC/3-Oct-95