WO1990004234A1

WO1990004234A1 - Digital half-toning process with error diffusion

Info

Publication number: WO1990004234A1
Application number: PCT/US1989/004581
Authority: WO
Inventors: John S. Bowers; Harry Bowers
Original assignee: Bowers Imaging Technologies, Inc.
Priority date: 1988-10-14
Filing date: 1989-10-13
Publication date: 1990-04-19
Also published as: CA2000705C; CA2000705A1

Abstract

A digital halftoning process with error diffusion reduces visibly discernible artifacts. Gray-scale values of pixles in an image are detected using an optical scanner (5). In the error diffusion process a linear range function and a predetermined threshold value are employed. The range function provides random values which are used to propagate error values, for each pixel, to at least three adjacent pixels, one of which lies on the same line and the other two of which are on an adjacent line. Images are printed based upon the propagated error values using a digital printer (9).

Description

DIGITAL HALF-TONING PROCESS WITH ERROR DIFFUSION

Background of the Invention

Field of the Invention

The present invention relates generally to a method for reproducing continuous tone images and more particularly to a reproduction process based upon digital half-toning with error diffusion.

Prior Art

Continuous-tone images are reproduced by screening processes for conventional half-tone printing. In the processes, picture elements of original images are converted into dots whose diameters vary in size according to the amplitude of light penetrating a screen. More particularly, the dots are larger where more light penetrates a screen and are smaller where less light is present. Such processes can be described as being of the analog type since dot size is the analog of light intensity for individual picture elements, or pixels, of an image. To reproduce a multi-color image, a color-filtered screen is prepared for each of the basic colors; then the segregated colors are printed sequentially with careful mechanical registration of the screens to avoid shadows.

In printing based upon digital half-toning, an image is scanned with an optical scanner which detects and quantifies the light intensity values at preselected pixel locations on the image. The detected data typically comprises quantified representations of gray scale values ranging from about 0 to 255 for each pixel location. To reproduce an image based upon digital halftoning, dots of fixed size are printed at locations corresponding in scale to the original pixel locations. It is well known, for instance, to print about forty thousand spaced-apart dots per square inch. The placement and density of dots printed within a given range determines the spatial resolution and perceived grayness of the area to an observer. For example, if an area is filled with the maximum number of dots, an observer will perceive the area as a dark, solid color. As dot density within a given area decreases, the area will have a successively lighter appearance. Also, the quality of detail in a reproduced image depends upon the number of picture elements that are reproduced.

When many small picture elements are present, fine detail is evident and the picture usually appears to have high resolution and depth. A shortcoming of digital half-toning as currently practiced, however, is that it produces "noisy" or grainy images. It has been suggested to use error diffusion techniques in conjunction with digital half-toning to improve detail resolution in digital half-toning and to provide more values of gray. For example, error diffusion with perturbation is described in Digital Halftoning, by Robert Ulichney (MIT Press, 1987), pp. 265-268. Such techniques are sometimes referred to as spatial dithering.

In digital half-toning with error diffusion the gray scale values at the pixel locations are binary encoded. The typical reference point or "threshold" for binary encoding gray scale values is 126, i.e., half way between the minimum and maximum gray scale values. Thus, the binary number 0 would be assigned to every pixel which has a detected gray scale value less than 125, and a binary 1 would be assigned to every pixel whose detected gray scale value is 126 or

greater. For example, a pixel location which has a detected gray scale value of 100 would be binary

encoded as a binary "0", and a pixel location which has a gray scale value of 145 would be binary encoded as a binary "1".

At this juncture, it can be understood that there will be an encoding error for each pixel location having a gray scale value other than 0 or 255. In the first example above, the magnitude of the encoding error would be 100 units as measured by gray scale values. In the second example above, the magnitude of the encoding error would be 110 units as measured by gray scale values.

Images reproduced by digital half-toning with error diffusion normally have discernible patterns, or artifacts, which are distracting to viewers. Sometimes the artifacts appear as straight lines and other times appear as wiggly or worm-like lines. At still other times, the artifacts have a random, pebble-like

appearance.

Summary of the Invention In the preferred embodiment, the present invention provides a digital half-toning process with error diffusion comprising the steps of:

detecting gray scale values at preselected pixel locations in an image;

for each detected gray scale value at the preselected pixel locations, determining upper and lower limits of a range function which generally linearly depends on the detected gray scale values and has upper and lower limits between 0 and 1 respectively;

selecting first and second values which are randomly located between the upper and lower limits of the range function;

if the detected gray scale value at a preselected pixel location is less than a predetermined threshold value, encoding the pixel location as a binary 0, assigning a first error value for the

preselected pixel location equal to its detected gray scale value multiplied by the first of the selected randomly located values and assigning a second error value for the preselected pixel location equal to its detected gray scale value multiplied by the second of the selected randomly located values;

if the detected gray scale value at a preselected pixel location is greater than the threshold value, encoding the pixel location as a binary 1, assigning a first error value for the preselected pixel location which equals the first of the selected

randomly located values multiplied by a quantity equal to the detected gray scale value less 255, and assigning a second error value for the preselected pixel location which equals the second of the selected randomly located values multiplied by a quantity equal to the detected gray scale value less 255;

then, for each preselected pixel location, propagating the first and second assigned error values to at least three adjacent preselected pixel locations, one of which lies on the same line as the preselected pixel location and the other two of which are on an adjacent line; and

printing images by digital half-tone printing based upon values of the preselected pixel locations that have been encoded after distribution of the assigned error values.

In one particularly preferred embodiment, the lower limit of the range function is between about 0 and 0.2, and varies linearly with the detected gray scale value of a preselected pixel location. More particularly, the lower limit, w_min, of the range function preferably is determined by the following equation:

w_mιn =

128 x 0.2

and the upper limit, w_max, of the range function is determined by the following equation:

w_max = 1 - x 0.6

where Z is the detected gray scale value at a preselected pixel location. Alternatively, the upper and lower limits of the range function can be determined from the graph of Figure 3.

In one aspect of the invention there is provided a digital half-toning process with error diffusion, comprising the steps of:

detecting gray scale values at preselected pixel locations in an image;

for each detected gray scale value at the preselected pixel locations, determining upper and lower limits of a range function which depends on the detected gray scale values, and selecting first and second values which are randomly located between the upper and lower limits of the range function;

if the detected gray scale value at a preselected pixel location is less than a predetermined threshold value, encoding the pixel location as a binary 0, assigning a first error value for the preselected pixel location equal to its detected gray scale value multiplied by the first of the selected randomly located values and assigning a second error value for the preselected pixel location equal to its detected gray scale value multiplied by the second of the selected randomly located values;

then, for each preselected pixel location, distributing the first and second assigned error values to at least three adjacent preselected pixel locations, one of which lies on the same line as the preselected pixel location and the other two of which are on an adjacent line; and

In another aspect of the invention there is provided a digital half-toning process with error diffusion comprising the steps of:

detecting gray scale values at preselected pixel locations in an image;

for each detected gray scale value at the preselected pixel locations, determining upper and lower limits of a range function which generally linearly depends on the detected gray scale values and has upper and lower limits between 0 and 1, respectively;

Brief Description of the Drawing

Figure 1 is a functional block diagram of a digital half-toning system which operates according to the process of the present invention;

Figure 2 schematically shows a field of picture elements or pixels; and

Figure 3 shows a function for use in the process of the present invention.

Description of the Preferred Embodiments

Figure 1 shows generally a system for digital printing. The components of the system of Figure 1 are an image scanner 5 of the kind conventionally used for making color separations, a digital computer 7, and a digital printer 9. The components of the system are conventional but, as will be described below, can be advantageously operated to provide digital half-toning with error diffusion. Generally speaking, the system of Figure 1 operates on a photographic transparency, although it can operate on a photographic print or a high-resolution printed original. In operation of the system, scanner 5 digitizes picture elements of an image according to gray scale values and provides the resulting digital information to computer 7. By manipulating the digital information with computer 7, an image can be retouched, adjusted, recomposed, and modified using conventional graphics software. Then the digital image information is binary encoded and operated upon by the half-toning algorithm with error diffusion as described below. For printing, the error- diffused information is provided to digital printer 9 which reproduces the encoded information on a suitable medium. The error-diffused half-toning information can also be presented for display on a CRT (cathode ray tube) screen.

A digital half-toning process with error

diffusion will now be described with reference to

Figure 2. The purpose of the process is to adjust binary encoded values at selected pixel locations so that a reproduced image can provide the illusion of a continuous tone image without discernible artifacts.

In the field in Figure 2, each dot represents one pixel location on a continuous tone image which is presented for scanning. For purposes of discussion it can be assumed that scanning proceeds from left to right across each of the pixel rows and sequentially from the top to the bottom of the field. Obviously, variations on the scanning pattern are possible. For example, scanning could proceed from left to right across one row of pixels, and then from right to left across the next lower row, and so forth in a serpentine pattern.

For color printing, the field of Figure 2 must be sequentially viewed through color filters. Each field is usually scanned several times, each time with a different filter. Alternatively, a field can be scanned once with each picture element having multiple exposures, each exposure being to a different filter. Color filtering does not, however, affect the essential steps in the error diffusion process. In the field of Figure 2, the location of each pixel can be described by its cartesian coordinates. For purposes of discussion, an arbitrary pixel "P" in Figure 2 can be identified at location (x,y). It should be noted that pixel P is in the interior of the field and therefore has eight immediately adjacent neighbors. It should also be noted that four of the pixels neighboring pixel P will be scanned before it and four of the neighboring pixels will be scanned after it. In Figure 2, the neighboring pixel to the immediate right of pixel P is designated by arrow d₁, the neighboring pixel immediately below pixel P is designated by arrow d₃, and the pixel diagonally below pixel P in the direction of scanning is designated by arrow d₂. Thus, the pixel designated by arrow d₁ has coordinates (x+1,y), the pixel designated by arrow d₃ has coordinates (x,y+1), and the pixel identified by arrow d₂ has coordinates (x+1,y+1).

For purposes of discussion, the digital half- toning and error diffusion process can be assumed to begin at pixel location (x,y) in Figure 2, and the magnitude of the detected gray scale value of pixel P at this location can be assumed to be a number Z. When Z is between the threshold value and the maximum gray scale value (255), the magnitude of the encoding error will be a negative number equal to Z minus 255 gray scale units. When Z is a number between 0 and the threshold value, the magnitude of the encoding error is simply equal to the value Z in gray scale units. In the following description the encoding error will be referred to by the symbol e_x,y, where the subscript identifies a pixel location by its cartesian coordinates. In practice the threshold value is normally constant. However, it is possible that the threshold value could be randomly varied, or dithered, in a relatively narrow range about a fixed central value (e.g., 128). In that case, another degree of randomness would be introduced into the error diffusion process.

In the process of the present invention the gray scale values, Z, of pixels are used as the arguments of range functions. One example of range functions, w_min and w_max, is shown in Figure 3. In this example, the range functions provide variable minimum and maximum limits which are linearly dependent upon the detected gray scale values, Z, of pixels. For pixel values ranging between 0 and 128, the smallest minimum value of the range function w_min is 0, and the largest minimum value is 0.2. Also, for pixel values Z between 128 and 255, the smallest minimum value of the range function w_min is 0, and the largest minimum value is 0.2. Algebraically, the range function w_min can be approximated as follows:

w_min =

Further in Figure 3, the pixel values Z between 0 and 128, the smallest maximum value of the range function w_max is 0.4, and the largest maximum value is 1.0. For pixel values between 128 and 255, the smallest maximum value of the range function w_max is 0.4, and the largest maximum value is 1.0. Algebraically, the range function w_max can be approximated as follows:

w_max = 1 - x 0.6

According to the present invention, the range functions w_min and w_max are employed to calculate pseudo-random weights r₁, r₂, and r₃. For calculation of pseudo-ransom weight r₁, a random number is

selected; then the random number is multiplied by the numerical range between w_min and w_max, and the resultant product is added to w_min. In practice, the random selection process does not employ a random number generator but (to minimize processing time) uses a look-up table of uniformly distributed random numbers expressed as decimals. An identical procedure is followed to calculate weight r₃. Then the sum of the pseudo-random weights r₁ and r₃ is subtracted from the unity to yield a third pseudo-random weight r₂; that is, r₂ = 1.0 - r₁ - r₃.

The pseudo-random weights r₁, r₂, and r₃ are used to propagate, or spread, error values to the pixels at locations (x+1,y), (x+1,y+1) and (x,y+1), respectively. More particularly, the error (err) propagated to the pixel located at (x+1,y) from the pixel located at (x,y) is determined by multiplying the weight r₁ by the encoding error. For pixel P that is err₁ = r₁ x e_x,y. Likewise, the error propagated to the pixel located at (x,y+1) is err₂ = r₂ x e_x,y.

Finally, the error propagated to the pixel located at (x+1,y+1) is err₃ = r₃ x e_x,y. Thus, the propagated errors err₁, err₂, and err₃ can be understood to be pseudo-randomized error values which are diffused, or distributed, to pixels neighboring pixel P in the directions of the arrows d₁, d₂, and _d3, respectively, of Figure 2.

It should be noted that the propagated errors can be either positive or negative. Also, it should be understood that pixels with detected gray scale values of either 0 or 255 do not generate error values. That is, error values are not diffused from pixels having error values of 0 and 255, but error values can be diffused to such pixels. For binary encoding purposes, the gray scale value of the pixel located at (x+1,y) becomes the detected gray scale value for that pixel location plus the propagated error err₁. Likewise, the gray scale value of the pixel located at (x+1,y+1) becomes the detected gray scatle value for that pixel plus the propagated error err₂. Finally, the gray scale value of the pixel located at (x,y+1) becomes the detected gray scale value at that pixel plus the propagated error err₃. It should be understood that the above-described error diffusion process continues with successively scanned pixels. Thus, the binary encoding error for the pixel located at (x+1,y) will reflect the propagated error err₁, as well as the error propagated from other previously scanned pixel locations. In turn, the error value for pixel location (x+1,y) is weighted by the pseudo-random process and then diffused to the pixels located at (x+2,y), (x+1,y+1), and (x+2,y+1). The process continues for each pixel in a row and then begins again at the first pixel on the next lower row.

In practice, special error assignment rules must be provided for the first and the last pixel locations in a row. For the pixel location last scanned in a row, a convenient rule is that an encoding error is assigned only to the pixel located immediately below.

For the pixel first scanned in a row, a convenient rule is that its assigned error value reflects only the error assigned from the pixel immediately above. The above-described error diffusion process can be summarized as follows. First, in accordance with the range distribution function of Figure 3, the range of w_min, w_max is determined by the gray scale value of the pixel located at (x,y). Then the following

calculations are made:

1. r₁ = RANDOM [w_min(pixel_(x,y)), w_max(pixel_(x,y))]

2. r₃ = RANDOM [w_min(pixel_(x,y)), w_max(pixel_(x,y))]

3. r₂ = 1.0 - r₁ - r₃

4. For each input pixel location (x,y), if the detected gray scale value of the pixel at that location is less than the preselected threshold value, then

pixel (x,y) is black, and

error = value of pixel_(x,y(

or else,

pixel_(x,y) is white, and

error = pixel_(x,y) - 255.

5. Then the distributed error values are calculated as follows:

err₁ = r₁ * e_x,y'

err₂ = r₂ * e_x,y, and

err₃ = r₃ * e_x,y.

6. Then the error values are distributed to

neighboring pixel locations as follows:

pixel_(x+1,y) = pixel_(x+1,y) + err₁

pixel_(x+1,y+1) = pixel_(x+1,y+1) + err₂

pixel_(x,y+1) = pixel_(x,y+1) + err₃.

Although the preferred embodiments of the process of the present invention have been described, those skilled in the art will appreciate that additions, modifications, substitutions and deletions not specifically described in the foregoing may be made to the preferred embodiment of the process without

departing from the spirit and scope of the invention as defined by the following claims. (As modified,

however, the process may not provide the same excellence of results as the preferred embodiments.)

As one example of a modification, the above- described error diffusion process could be operated such that encoding errors are propagated only to two pixels adjacent each sampled pixel. As another

example, the error diffusion process could be operated such that error assignments are interchanged (e.g., arrow d₃ in Figure 2 might be interchanged with arrow d₂). Also, modifications to the range functions can be made, especially in terms of slope and intercept values.

Claims

What is claimed is:

1. A digital half-toning process with error diffusion, comprising the steps of:

detecting gray scale values at preselected pixel locations in an image;

then, for each preselected pixel location, distributing the first and second assigned error values to at least three adjacent preselected pixel locations. one of which lies on the same line as the preselected pixel location and the other two of which are on an adjacent line; and

2. A digital half-toning process according to Claim 1 wherein the range function is linear.

3. A digital half-toning process according to Claim 2 wherein the upper and lower limits of the range function are between 0 and 1, respectively.

4. A digital half-toning process according to Claim 3 wherein the lower limit of the range function has a minimum value between about 0 and about 0.2.

5. A digital half-toning process according to Claim 4 wherein the lower limit of the range function varies linearly with the detected gray scale value of a preselected pixel location.

6. A digital half-toning process according to Claim 5 wherein the lower limit, w_min, of the range function is determined as follows:

w_min = x 0.2

where Z is the detected gray scale value at a preselected pixel location.

7. A digital half-toning process according to Claim 5 wherein the upper limit, w_max, of the range function is determined as follows: w_max = 1 -

x 0.6

where Z is the detected gray scale value at a preselected pixel location.

8. A digital half-toning process according to Claim 1 wherein the two values which are randomly located between the upper and lower limits of the range function are selected from a set of values that are uniformly spaced between the upper and lower limits of the range function.

9. A digital half-toning process according to Claim 1 wherein the upper and lower limits of the range function are determined from a graph such as shown in Figure 3.

10. A digital half-toning process with error diffusion comprising the steps of:

detecting gray scale values at preselected pixel locations in an image;

11. A digital half-toning process according to Claim 10 wherein the lower limit of the range function has a minimum value between about 0 and 0.2.

12. A digital half-toning process according to Claim 11 wherein the lower limit of the range function varies linearly with the detected gray scale value of a preselected pixel location.

13. A digital half-toning process according to Claim 12 wherein the lower limit, w_min, of the range function is determined as follows: w_min = I2" 28I x 0.2

₁₂1₈

where Z is the detected gray scale value at a preselected pixel location.

14. A digital half-toning process according to Claim 12 wherein the upper limit, w_max, of the range function is determined as follows:

U

w_max = 1 -

128 x 0.6

where Z is the detected gray scale value at a preselected pixel location.

15. A digital half-toning process according to Claim 10 wherein the two values which are randomly located between the upper and lower limits of the range function are selected from a set of values that are uniformly spaced between the upper and lower limits of the range function.

16. A digital half-toning process according to Claim 10 wherein the upper and lower limits of the range function are determined from the graph of Figure 3.

17. A digital half-toning process according to Claim 10 wherein the lower limit, w_min, of the range function is determined as follows:

= 1

w_min

128 x 0.2

and the upper limit, w_max, of the range function is determined as follows:

w_max = 1 - l¹²1⁸2^"8^Zl x 0.6

where Z is the detected gray scale value at a preselected pixel location.

18. A digital half-toning process according to Claim 17 wherein, for a preselected pixel location having coordinates (x,y), the first and second error values are propagated to pixel locations having coordinates (x+1,y) and (x+1,y+1), respectively.