Method for Producing a Multitone Image

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

1. Field of the Invention

This invention relates to a method for producing multitone image data from data representative of an original image and, in particular, for producing multitone image data with a set of N output darkness levels U greater than 2 from original darkness values V.sub.o representative of an original image. An alternative approach is described in a commonly assigned application to Michael Speciner, Ser. No. 07/810,462, now allowed.

2. Description of Related Art

Any photograph, painting, etc., consisting of a broad range of tones or gradation of tones is known as a continuous tone image or picture. In paintings, changing the pigment concentration or the amount of deposit of the printing media on a substrate modulates the color values throughout an entire picture. In photography, the different tones are created by varying amounts of silver, which appears black, in image areas.

In most forms of printing, tones cannot be reproduced by varying concentrations or amounts of ink. Many printing processes can print only a solid density of a color in an image area, while no ink prints in a non image area. In order to reproduce the varying tones of a continuous tone original image, a halftone process can be used to convert the original image into a pattern of very small and clearly defined dots. More specifically, the original image can be scanned with a light beam using an image scanner to obtain an electronic signal containing image information in the form of intensity levels or optical density variations corresponding to elemental picture areas, known as pixels, of the original picture. Then a thresholding technique can be used to generate data or an output that can cause a dot to be printed in a pixel of the halftone reproduction if the intensity level or optical density variation of the corresponding pixel in the original image exceeds a predetermined value. The output can be stored in a memory or used directly to drive a recorder, such as an exposing device, a printer or a computer display.

In halftoning processes, each dot in the reproduced image has the same tonal value or optical density. Various tones in the original are represented in the halftone image by a large number of evenly spaced dots which can have different sizes. Larger dots produce darker tones. Smaller dots or fewer dots make lighter tones. Halftones have the appearance of continuous tone images because of the limited resolving power of the human eye. When viewed at a normal reading distance, the individual dots blend into and appear like a "continuous" tone.

A rather different halftoning technique is based on the idea that there is an error associated with each halftone pixel which is the difference between its darkness value (which can only be reproduced by a printed dot or the absence of a printed dot) and the darkness value of the corresponding continuous tone original image pixel. If this error is distributed to neighboring pixels before the halftone thresholding is performed for them, the sum of the errors in a region can be minimized, thus faithfully reproducing the average darkness value in the region. The Floyd-Steinberg algorithm produces good halftone images using this technique. For further information on the Floyd-Steinberg algorithm, see "An Adaptive Algorithm for Spatial Grey Scale," by R. W. Floyd and L. Steinberg in SID 75 Digest, Society for Information Display, 1975, pages 36-37.

In the reproduction of color images, the original multicolored image is typically scanned through separate sets of colored filters to produce four separate image signals, corresponding to three primary colors and, possibly, black. The chosen primary colors for color printing are typically cyan, magenta and yellow. The chosen primary colors for a color computer display are typically red, green and blue. The separate signals are processed as described above. In other words, a color separation signal representative of a pattern of very small and clearly defined dots is generated for each of the colors where the dots in each of the patterns has the same tonal value or optical density throughout that pattern. Then the patterns for each color must be combined.

For instance, an exposing device may produce black and white film transparencies, corresponding to each of the cyan, magenta, yellow and black color separation signals, known as color separation transparencies or color separations for short. The color separations are used to make printing plates. The printing plates are mounted on a printing press to print, in registration, four overlapping single colored images to reconstruct the multicolored original.

The electronic output signals may also be used to directly drive a color printer or a computer display to produce a reconstructed multicolored image without ever producing actual color separations or printing plates.

It is desirable to provide a method for producing a multitone image using a set of at least 3 output darkness values (or levels) for at least one output color from data representative of an original image.

The present invention is related to a method for producing a multitone image corresponding to an array of output pixels (i, j) using a set of at least 3 output darkness levels U(i,j) for at least one output color from original darkness values V.sub.o (s,t) of an array of input pixels (s,t) representative of an original image, comprising:

determining one of the output darkness levels U(i, j) corresponding to selected ones of the original darkness values V.sub.o (s,t) using the following equations:

E.sub.in (i,j)=a*E.sub.out (i,j-1)+b*E.sub.out (i-1, j+1)+c*E.sub.out (i-1, j)+d*E.sub.out (i-1, j-1),

U(i,j)= (N-1)V.sub.o (s,t)+E.sub.in (i,j)+1/2 ,

E.sub.out (i,j)=(N-1)V.sub.o (s,t)+E.sub.in (i,j)-U(i,j),

where a, b, c and d are constants; and

using the output darkness levels U(i,j) to produce the multitone image representative of the original image.

The invention can be more fully understood from the following detailed description thereof in connection with accompanying drawings described as follows.

FIG. 1 illustrates a schematic system for reproducing images.

FIG. 2 illustrates an output pixel and associated reproduction error distribution factors.

FIG. 3 illustrates an original sample image divided into 6 pixels.

FIG. 4 illustrates a reproduction of the original sample image of FIG. 3 using the process of the present invention.

Throughout the following detailed description, similar reference characters refer to similar elements in all figures of the drawings.

Referring to FIG. 1, there is shown a system of various electronic or other machine elements typically used by the graphic arts industry to facilitate image reproduction including black and white and colored image reproduction. It should be understood that the depicted system is schematic and should not be considered as limiting to the present invention, but the depicted system is simply used as an aid to this description so as to better understand the scope of this invention.

In view of the above, FIG. 1 illustrates an image scanner 10 comprising means 12 for generating and directing a beam 14 of light for illuminating an original image 16 that we intend to eventually reproduce. The image 16 can be, for instance, a continuous tone black and white (or color) photograph. Alternatively, the image 16 can be, for instance, a continuous tone black and white (or color) transparency. The generating and directing means 12 can, for instance, cause the beam 14 to scan the image 16 in a sequential raster fashion. The scanner 10 includes a light detector 18 can be used to collect the light reflected from a photograph 16. Alternatively or in addition, the scanner 10 may include a light detector 20 which can be used to collect the light transmitted through a transparency 16. The image scanner 10 then generates an electrical video signal output which contains image information for each picture element or pixel of the original image 16. A filter wheel 22 can contain a plurality of filters, such as 3 filters and a clear space, positioned between the image 16 and the detector 18 to filter the beam 14 reflecting from the photograph 16, so that specific image information for each of three preselected colors, i.e., magenta, cyan and yellow, as well as black is obtained for each scanned picture element or pixel. A similar filter wheel 24 can be used to filter the beam 14 passing through the transparency 16.

The information for the four colors, black being also considered a color comprising a gray scale of tones such as are found in a black and white picture, may be obtained simultaneously and outputted in four parallel channels, by splitting the beam 14 through the filters in the filter wheel 22 or 24 and using four detectors 18 or 20, or it may be sequential, each color obtained after a complete scan of the image, or any other variation. Preferably, an analog to digital (A/D) converter 26 will be included in the scanner 10 to provide a digital output image density signal value for each of the four colors for each pixel. For each pixel, the output values from the A/D converter 26 can be referred to as original color separation image optical density values or data D.sub.o. The original color separation image optical density values D.sub.o are sent to a processor unit 30 which may include a computer 32 with appropriate software adapted to process the image data prior to sending the data to a means for displaying a reproduced or copy image. The displaying means may include a recorder or printer 34 or a computer monitor 36, such as a color monitor. The processor unit 30 may include means 38 for providing operator input, such as a keyboard, a mouse and/or other devices.

Optical density values do not change linearly from light to dark, so the original color separation image optical density values or data (D) can be converted to linear darkness values (V) by any means, such as using the Bartleson-Breneman equation which is as follows:

Regardless of the apparatus and method employed, original color separation image linear darkness values V.sub.o (s,t) are obtained or generated for each picture element or pixel (s,t) of an original image for each color to be used in the reproduction.

For reproduction of a monochrome black and white original image, a single set of original color separation image linear darkness values V.sub.o (s,t) is obtained where the color is defined to be black. The original color separation image linear darkness values V.sub.o (s,t) corresponding to the color black can be referred to as values K.sub.o (s,t). Typically, for reproduction of a multi-color image on a computer color display monitor, a set of original color separation image linear darkness values V.sub.o (s,t) is obtained for each color to be used in displaying the image. Such colors consist of red, green and blue resulting in original color separation image linear values R.sub.o (s,t) , G.sub.o (s,t) and B.sub.o (s,t) , respectively. Using a scanner that generates 8 bits of binary information for each input pixel (s,t), each original darkness value K.sub.o, R.sub.o, B.sub.o and G.sub.o can have any integer value between and including 0 and 255. When printing a reproduction on a printer, the set of colors preferably consist of cyan, magenta, yellow and black, where black is defined as a color. The original color separation image linear darkness values V.sub.o (s,t) corresponding to the colors cyan, magenta and yellow can be referred to as values C.sub.o (s,t) , M.sub.o (s,t) and Y.sub.o (s,t), respectively. The C.sub.o, M.sub.o and Y.sub.o values are real numbers within the range of 0.ltoreq.V.sub.o .ltoreq.1.

For the purpose of explaining the present invention, when original red, green and blue separation image linear darkness values V.sub.o (s,t) are provided, we will convert them to corresponding original cyan, magenta and yellow separation image linear darkness values V.sub.o (s,t) using the following equations:

The present invention comprises a method for producing a multitone image corresponding to an array of output pixels (i,j) from original darkness values V.sub.o (s,t) for at least one color of an array of input pixels (s,t) representative of an original image. Preferably the original image is a continuous tone image. However, the original image can have any form. The original image can even be a virtual image, such as computer generated virtual image, as opposed to a real or actual image.

The present method is adapted to use a set of output (or destination) darkness levels U for each color to be used in the reproduction. The set comprises a number N which is greater than 2 for at least one of the colors used in the reproduction. The number for each set can be the same or different. In a typical halftoning process, the total number N of output darkness levels U used to reproduce each color is two, a first level where the single tone dot is "on" and a second level where the single tone dot is "off". In the multitoning process of the present invention, there are at least 3 output (or destination) darkness levels U available for each output pixel (i,j). For instance, like the halftoning process, a first one of the output darkness levels U can be where a first black (or other color) tone dot is "on", a second output darkness level U can be where the first black (or other color) tone dot is "off" and a third level U can be a second tone or shade of the color intermediate between the first level and the second level.

Typical graphics adaptors or controllers for color monitors provide a total of 256 palette indices P. As a result, the product of the number of output darkness levels U for each of the colors used can not exceed 256. While it is reasonable to make the number of output darkness levels U the same for each color, this may not be the best possible distribution because the visual system is not equally sensitive to the individual colors. In terms of computational efficiency, it is preferred to assign 5 equally spaced output darkness levels U to each color. This makes the output darkness interval between adjacent levels to be 1/4 of the total of the intervals. It further makes the set of output or reproduction darkness values V.sub.r to be {0, 1/4, 1/2, 3/4, 1} where the values 1/4, 1/2, and 3/4 are intermediate gray levels or tonal shades between the value 0 (representing dot "off") and the value 1 (representing the use of the darkest dot of the set of output tones). It further uses less than half (i.e., 5*5*5=125) of the possible 256 palette indices P.

Thus, if not already accomplished, the method of the present invention includes establishing a set of output darkness levels U to be used for each color in the reproduction.

After the set(s) of output darkness levels U are established for each color, the process of the present invention includes determining or selecting one of the preestablished set of output darkness levels U corresponding to selected ones of the original darkness values V.sub.o of the input pixels (s,t) .

If the number of input pixels (s,t) is the same as the number of output pixels (i,j), then one of the preestablished set of output darkness levels (U) can be determined or selected for each of the original darkness values V.sub.o of the input pixels (s,t). If the number of input pixels (s,t) is more than the number of output pixels (i,j), then certain ones of the original darkness values V.sub.o of the input pixels (s,t) can be skipped in selecting or determining one of the preestablished set of output darkness levels U for corresponding original darkness values V.sub.o of the input pixels (s,t). If the number of input pixels (s,t) is less than the number of output pixels (i,j), then output darkness levels U are determined or selected for each of the original darkness values V.sub.o of the input pixels (s,t) and such output darkness levels U can be repeated for extra output pixels (i,j).

In a first embodiment, in order to determine or select the output darkness levels U corresponding to the original darkness values V.sub.o of the input pixels (s,t), the following equations are used:

where a, b, c and d are constants such that a+b+c+d is equal to or substantially equal to 1. Further, the half brackets " " indicate the floor function which is the highest integer less than or equal to the real number contained in the brackets. For instance, the floor function of 1.3, (i.e., 1.3 ) is 1. Further, -1.3 is -2.

In a second embodiment, the output darkness levels U corresponding to the original darkness values V.sub.o of the input pixels (s,t) are determined or selected using equations (5) and (6) . However, instead of equation (7) , E.sub.out (i,j) is calculated using the following equation:

where F[X] is the sign extended fraction part of the real number X.

A sign extended fraction part is determined by first subtracting the floor of the real number from the real number. Then if the result is greater than or equal to 1/2, then subtract 1 from the result to obtain the sign extended fraction part. For instance, the sign extended fraction part of 1.7 is determined by first subtracting 1. Then since the result which is 0.7 is determined by greater than 1/2, 1 is subtracted from 0.7 leaving -0.3 which is the sign extended fraction part of 1.7. On the other hand, if the result is less than 1/2, then the sign extended fraction part is the result.

In this second embodiment, E.sub.out (i,j) can be determined using equation (8) prior to calculating U(i,j) for the same pixel (i,j). If E.sub.out (i,j) is determined before U, then instead of using equation (6), U can be determined from equation (7) rewritten as follows:

Preferably, N-1 is a power of 2. For instance, N=2, 3, 5, 9, etc. Further, preferably the multiplication by N-1 in equations (6)-(9) is done by a binary shift.

In each embodiment, the respective computations are performed for each output pixel (i,j) in sequential raster fashion . For instance, E.sub.in (i,J) , U(i,j) and E.sub.out (i,j) are first calculated for output pixel (1,1). Then E.sub.in (i,j), U(i,j) and E.sub.out (i,j) are calculated for adjacent or neighbor pixels in the scan line 1, one at a time, each time increasing j by 1 until E.sub.in (i,j), U(i,j) and E.sub.out (i,.sub.j) are determined for each pixel (1,j). Then the same is accomplished for successive scan lines, increasing i by 1 each time until E.sub.in (i,j), U(i,j) and E.sub.out (i,.sub.j) are determined for all pixels (i,j). It should be pointed out that E.sub.out (i,j) need not be determined for the last pixel in the last scan line since this error is not distributed to another pixel.

Like the Floyd-Steinberg algorithm used in halftone processes, the above equations used in the present multitone process are based on the principle that there is an error value associated with each multitone output pixel (i,j) which is the difference between its output darkness value V.sub.r (i,j) and the darkness value V.sub.o (s,t) of the corresponding original image pixel (s,t). Thus, this error is distributed to neighboring pixels in determining which output darkness value V.sub.r will be assigned to output pixels (i,j). The relation between U and V.sub.r is U=(N-1)V.sub.r.

This error distribution concept is illustrated in FIG. 2. In FIG. 2, one output pixel (i, j) is illustrated with an error value E.sub.out. Certain percentages or fractions of the output error value E.sub.out will be distributed to neighboring output pixels to accumulate an input error E.sub.in for each output pixel (i,j) where the input error E.sub.in is used in the calculation of the ouput darkness level U(i,j) of the particular pixel (i,j). The first output pixel (1,1) will have no input error E.sub.in associated with it. The letters a, b, c and d in FIG. 2 represent the fractions or weighting factors of the output error value E.sub.out (i,j) that will be added to the input error E.sub.in of four adjacent neighbor output pixels. The fractions or weighting factors a, b, c and d can be determined experimentally. Preferably, a=7/16, b=3/16, c=5/16 and d=1/16.

Then the output darkness levels U(i, j) are used to produce the multitone image representative of the original image. If more than one ouput color is used, the output darkness levels U(i,j) are selected or determined for each color independently as described above. Then the output darkness levels U(i,j) for each color are used to produce the multitone and multi-color image representative of the original image. The image produced can be a visible image reproduced on a substrate, such as paper, or a computer display screen. Alternatively, the image can be a virtual image stored in memory in the computer 32 or elsewhere.

To illustrate the above described method of the present invention, an example is provided determining the output darkness levels U(i,j) associated with one color for a set of 6 output pixels (i, j) corresponding one to one to original darkness values V.sub.o (i,j) of 6 input pixels (s,t), where (1) i and s are 1 or 2 and (2) j and t are 1, 2 or 3. FIG. 3 represents an original image which has been divided into 6 pixels, specifically original or input pixels (1,1) , (1,2) , (1,3) , (2,1) , (2,2) , and (2,3) . FIG. 4 represents the reproduced image using the multitone process of the present invention.

The number N of tones or output darkness levels U chosen or established is assumed to be 3, (i.e., levels 0, 1 and 2) which are equally spaced providing a corresponding set of output darkness values V.sub.r comprising 0, 1/2 and 1. For the purposes of this illustration, the original darkness value V.sub.o of each one of the 6 input pixels (s,t) is assumed to be 1/3.

First, regarding output pixel (1,1), the input error E.sub.in (1,1) associated with it is 0. The output darkness level U(1,1) corresponding to the original darkness value U(1,1) Of the input pixel (1,1) is determined using equation (6) as follows: ##STR1## Thus, as illustrated in FIG. 4, the corresponding output pixel (1,1) will be reproduced with the output darkness value V.sub.r (1,1) being 1/2.

Next the output error value E.sub.out associated with this determination is calculated using equation (7) as follows: ##EQU1##

Second, regarding output pixel (1,2), the input error E.sub.in (1,2) associated with output pixel (1,2) is determined using equation (5): ##EQU2## The output darkness level U(1,2) corresponding to the original darkness value V.sub.o (1,2) of the input pixel (1,2) is determined using equation (5) as follows: ##STR2## Thus, as illustrated in FIG. 4, the corresponding output pixel (1,2) will be reproduced with the output darkness value V.sub.r (1,2) being 1/2.

Next the output error value E.sub.out associated with this determination is calculated using equation (7) as follows: ##EQU3##

Third, regarding output pixel (1,3), the input error E.sub.in associated with output pixel (1,3) is determined using equation (5): ##EQU4## The output darkness level U(1,3) corresponding to the original darkness value V.sub.o (1,3) of the input pixel (1,3) is determined using equation (6) as follows: ##STR3## Thus, as illustrated in FIG. 4, the corresponding output pixel (1,3) will be reproduced with the output darkness value V.sub.r (1,3) being 0.

Next the output error value E.sub.out associated with this determination is calculated using equation (7) as follows: ##EQU5##

Fourth, regarding output pixel (2,1), the input error E.sub.in associated with output pixel (2,1) is determined using equation (5): ##EQU6## The output darkness level U(2,1) corresponding to the original darkness value V.sub.o (2,1) of the input pixel (2,1) is determined using equation (6) as follows: ##STR4## Thus, as illustrated in FIG. 4, the corresponding output pixel (2,1) will be reproduced with the output darkness value V.sub.r (2,1) being 0.

Next the output error value E.sub.out associated with this determination is calculated using equation (7) as follows: ##EQU7##

Fifth, regarding output pixel (2,2), the input error E.sub.in associated with output pixel (2,2) is determined using equation (5): ##EQU8## The output darkness level U(2,2) corresponding to the original darkness value V.sub.o (2,2) of the input pixel (2,2) is determined using equation (6) as follows: ##STR5## Thus, as illustrated in FIG. 4, the corresponding output pixel (2,2) will be reproduced with the output darkness value V.sub.r (2,2) being 1/2.

Next, the output error value E.sub.out associated with this determination is calculated using equation (7) as follows: ##EQU9##

Sixth, regarding output pixel (2,3), the input error E.sub.in associated with pixel (2,3) is determined using equation (5): ##EQU10## The output darkness level U(2,3) corresponding to the original darkness value V.sub.o (2,3) of the input pixel (2,3) is determined using equation (5) as follows: ##STR6## Thus, as illustrated in FIG. 4, the corresponding output pixel (2,3) will be reproduced with the output darkness value V.sub.r (2,3) being 1/2.

The output error value E.sub.out associated with this determination is not needed. Thus, it doesn't need to be calculated.

As can be seen from FIG. 4, the output image has four pixels with darkness values equal to 1/2 and two pixels with darkness values of 0. This is a good reproduction of the pixels (s,t) in the original image because the average intensity over the output pixels (i,j) equals the average intensity of the input pixels (s,t) where intensity is defined as 1 minus the darkness value.

If the output image is to be displayed on a color monitor, one can convert the output darkness levels U(i,j) for each color for each pixel to a single palette index P(i,j) using the equation:

where (1) N.sub.c, N.sub.m and N.sub.y are the number N of output darkness levels U for the colors cyan, magenta and yellow, respectively, and (2) U.sub.c, U.sub.m and U.sub.y are the output darkness levels U for the colors cyan, magenta and yellow, respectively.

As an example, assume for one output pixel (i,j), U.sub.c =1, U.sub.m =2 and u.sub.y =4. (These would have been determined using equation (6) or (9).) Further, assume N.sub.c =N.sub.m =N.sub.y =5. Plugging the numbers into equation 10, we get: ##EQU11##

Then the palette index P(i,j) can be set to or used with a look-up table of red, green and blue voltage values needed to display the corresponding darkness values V.sub.r for the combination of the 3 output colors (i.e., red, green and blue).

In implementing the process of the present invention, it is preferred to use a computer to perform the various calculations needed to generate output darkness levels U(i,j) corresponding to original color separation values V.sub.o (s,t) for input pixels (s,t). An illustrative software embodiment for performing the method of the present invention is included in an Appendix A to this specification and appears immediately before the claims. In this appended software embodiment of the present invention, the number N of output darkness levels U is 5 for each of the set of output colors comprising cyan, magenta and yellow. This software program is written in the C language for the Sun Sparcstation or the Sun 3/60 Workstation.

Those skilled in the art, having the benefit of the teachings of the present invention as hereinabove set forth, can effect numerous modifications thereto. These modifications are to be construed as being encompassed within the scope of the present invention as set forth in the appended claims.