Method of Non-Overlapping Color Printing

The disclosure in the appendix contains material to which a claim of copyright protection is made. The copyright owner has no objection to the facsimile reproduction of any one of the patent documents or the patent disclosure as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves all other rights whatsoever.

The invention relates generally to printing systems for printing color documents. More specifically, to such printing systems having the capability of printing non-overlapping colors.

Color marking engines capable of printing non-overlapping additive colorants (red, green, blue), such as the Kodak ImageSource 70 C/P electrophotographic color printer are known. Previously such color marking engines have not been used to print multicolor images such as photographs because the printers were not believed capable of producing commercially acceptable image quality. They were used as accent color printers which could produce only a limited number of colors.

Normally color printers employ cyan, magenta, yellow and black to produce color prints. By overlaying these colorants, it is possible to make most colors. These printers are often called process color printers.

Accent color printers can place several colorants on the page. Since they cannot overlay colorants, they can only make colors which are shades of the available colorants plus white if the print receiving medium is white, or the underlying color of the print receiving medium if it is not white. Accent color printers are typically cheaper to manufacture than process color printers.

From the forgoing, it can be seen that it would be advantageous to have a method of extending the gamut of colors printable by an accent color printer, and in the event that the color printer is supplied with a set of three primary colorants, for printing most of the colors currently printable with process color printers.

The present invention is directed to overcoming one or more of the problems set forth above. Briefly summarized, according to one aspect of the present invention, a multi color printing method employing a color printer capable of non-overlapping color printing using M colorants, where M is greater than two, includes the steps of: providing a digital color image having multi-bit color pixels; separating the digital color image into three multi-bit color primary components; converting each multi-bit component into a 1-bit component using a digital halftoning technique; assigning a single printer colorant to each output image pixel based on the 1-bit color components. The printer colorants are assigned by: dividing the image into n-tuples, each pixel in an n-tuple having a unique designation N; assigning N-member combinations of N-1 printer colorants and no colorant that appear as combinations of 1-bit color components; and setting an output to the Nth member of an N-member combination based on the corresponding combination of 1-bit color components. The image is then printed using the assigned colorants.

One of the main advantages of the present invention over the prior art is that the user can print almost all colors on an accent color printer. There is no need to modify any description of the full color digital image, making the method independent of the page description language used. Since the method can produce most colors, there is no need to have a user specify color re-mapping (i.e. red digital image color to green printed color) as is presently required in accent color printers. According to another aspect of the invention, when a particular additive primary color is missing from an image, the corresponding colorant for that color need not be printed, thereby using only the minimum number of colorants needed for any given printed page. This provides an advantage over process color printers in printing speed.

These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.

FIG. 1 is a flow chart illustrating the general method of the present invention;

FIG. 2 is a block diagram of the printing system capable of employing the method of the present invention;

FIG. 3 is a block diagram showing the major steps used in processing a digital image according to the present invention;

FIG. 4 is a diagram representing a portion of a digital image useful in describing the step of separating and converting the digital image into 1-bit subtractive color primary separations;

FIG. 5 is a flow chart showing an example of the details of the method used to separate and convert the digital image from multi-bit to one bit subtractive color primaries; and

FIG. 6 is a flow chart showing an example of the details needed to assign printer colorants.

To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.

The present invention employs the general principle that the apparent color of neighboring differently colored pixels when viewed from a sufficient distance will appear as a different color that is the combination of the different colors of the neighboring pixels. The invention employs the technique of converting a multi-bit digital color image to 1-bit color components using any halftoning technique with a further restriction that the whole image is divided into n-tuples of neighboring pixels, wherein each pixel in the n-tuple has a unique designation N. The term n-tuple as used herein means that the image is divided into non-overlapping groups of n pixels. Within each n-tuple combinations of available printer colorants are printed to produce the appearance of the desired output color. The number n is determined by the maximum number of printer colorants and no colorant that will be combined in a neighborhood to produce a desired output color.

For example, if colorants capable of producing black and the three additive primary colors red, green and blue are provided in the printer, and the print medium (e.g. paper) is white, most of the colors commonly produced by process color printer can be produced on an accent color printer using combinations of at most, two of the available output colors. Thus in this case, the n-tuples would have just two members which could be designated Odd and Even.

If colorant combinations other than a complete set of primaries are used, the number of colorants in a neighborhood to produce the desired output color appearance may be greater than two. For example if a combination of additive and subtractive primaries (e.g. red, yellow and blue) are used the n-tuple may have three members. The color green in this example would be produced by two yellow pixels and one blue pixel in a 3-tuple.

FIG. 1 is a flow chart illustrating the general method of the present invention. As shown in FIG. 1, the multi-bit digital image is first separated (1) into three multi-bit color primary components. Each multi-bit color primary component is then converted (2) to a 1-bit color primary component using any known digital color image halftoning technique such as dithering or error diffusion. Finally, a single printer colorant is assigned (3) to each pixel of the image using n-tuples of pixels and N-member combinations of available printer colorants and no colorant as described above.

Referring now to FIG. 2, a specific example of a system useful for practicing the method of the present invention, for example a system for printing documents having color images, is generally designated 10. The system includes a scanner 12 for scanning color photographic prints to produce a digital image file. The scanner 12 may be for example an Epson 800-C.TM. color scanner that produces 24 bit color digital image files from color photographic prints. The scanner 12 is connected to a central processing unit (CPU) 14, for example a Sun Microsystems Sparcstation 2.TM. workstation running a desktop publishing application such as Framemaker from Frame Technology on the Sun Solaris.TM. operating system. The system 10 includes a mass storage device 16, such as a magnetic disk drive for storing the data files generated the desktop publishing application. Operator interface devices such as a keyboard 18 and mouse 20 are connected to the CPU 14 to allow an operator to control the system. A printer 22, such as a Kodak ImageSource 70 Copier/Printer is connected to the CPU 14 for printing documents containing color images generated by the application. The printer 22 includes a programmable raster image processor (RIP) 24 connected to drive a color marking engine 26. The RIP 24 converts the page description language commands generated by the desktop publishing application to commands for driving the color marking engine 26. The color marking engine is provided with red, green, blue and black toners, and is capable of applying any one of the toners to a given pixel in the output image, but is not capable of overlapping the toners.

The page description language generated by the desktop publishing application defines each output pixel in terms of 24-bit color components (8-bits red, 8-bits green and 8-bits blue) in a page description language (e.g. PostScript or PCL). The RIP 24 interprets the page description language into rasterized 24-bit color components as is known in the prior art. The RIP 24 then converts the rasterized 24-bit color components to 3-bit additive color plus 1-bit black components (1-bit red, 1-bit green, 1-bit blue, and 1-bit black) for driving the color marking engine 26.

As shown in FIG. 3, the RIP 24 processes the rasterized 24-bit color components by first extracting an 8-bit black component (27). This is done by a process known in the art as "under color removal", wherein the color components of a pixel are examined and a minimum value common to all of the color components is assigned to black and subtracted from the remaining color components. In the prior art, it is known to remove all or some percentage of black. According to the preferred embodiment of the present invention, 100% of the black is removed. Next, the remaining primary colorants are converted (28) into three 8-bit primary color components. The RIP 24 then converts (30) the 8-bit primary color components and the 8-bit black component to 1-bit subtractive color primary components as described in detail below. The RIP 24 then (32) converts the 1-bit subtractive color primary components plus black to non-overlapping 1-bit additive color primary components plus black as described in further detail below.

Optionally, to increase printing speed, the RIP 24 may be programmed to detect (34) an unused printer toner for a page, and command the printer to skip the printing process for the unused color. Finally, the RIP 24 sends the non-overlapping 1-bit color components to the marking engine to print the color image.

To convert the 8-bit primary color components plus the 8-bit black component to 1-bit subtractive color primary components plus 1-bit black according to the present invention, first consider the whole page 36 as being divided up into 2-tuples having Even pixels 38 and Odd pixels 40, as illustrated in FIG. 4. This division of the pixels is chosen so that neighboring pixels will be treated with identical or nearly identical threshold values as described below. Although the example shows pairs of neighboring adjacent diagonal pixels being identified, other schemes such as pairs of vertically or horizontally adjacent neighbors, or nearly adjacent neighbors (e.g. pairs of pixels separated by one or several other pixels) can be employed. The diagonally adjacent scheme has the benefit that the human visual response is less acute for diagonal detail, and therefore pixel patterns resulting from the method of the present invention are less visible to the human viewer.

Referring now to FIG. 5, each pixel on the page 36 is processed as follows (41). The three 8-bit primary color values for the pixel at a particular X,Y location are temporarily stored (42). An 8-bit Cyan portion is extracted (44) from the temporarily stored color values by converting the temporarily stored primary color values to C,M,Y space and extracting the Cyan component. The particular conversion of the three 8-bit primary color values depends on their color space, and will be trivial if the color space is already C,M,Y. Otherwise, any known appropriate color space transformation may be applied to the primary color values to convert them to C,M,Y values.

A test is made (46) to determine if the pixel is an Even pixel (see FIG. 3). If the pixel is an Even pixel, a test (48) is made to determine if the Cyan value is greater than some upper threshold, e.g. 2/3 of the maximum possible Cyan value (i.e. 170 out of a possible 255). If the Cyan value is greater than 2/3 of the maximum, the Cyan bit is set to 1 (50); if not, it is set to 0 (52). If the pixel is Odd, a test (54) is made to determine if the Cyan value is greater than some lower threshold, e.g. 1/3 of the maximum possible Cyan value (i.e. 85 out of a possible 255). If the Cyan value is greater than 1/3 of the maximum, the Cyan bit is set to 1 (56); if not, it is set to 0 (58). The actual threshold values are not critical to the performance of the present invention, but are selected to produce the most pleasing gray scale appearance of the output image. Experiments have shown that although other threshold values will produce more pleasing results for some images, 2/3 and 1/3 work the best for a large population of images.

Next, an 8-bit Magenta portion of the temporarily stored color values is extracted (60), and a Magenta bit is assigned (62) by repeating the steps (46)-(58) for Magenta. Next, an 8-bit Yellow portion of the temporarily stored color values is extracted (64), and a Yellow bit is assigned (66) by repeating the steps (46)-(58) for Yellow. Finally, a Black bit is assigned (68) by repeating the steps (46)-(58) for Black.

Referring now to FIG. 6, the process of assigning 1-bit non-overlapping additive color primary values to each pixel on the output page will be described. As was the case with the input image described in FIG. 4, each pixel on the output page is assigned to be either Odd or Even corresponding with the assignment of pixels on the input page image 36. For each pixel on the page at position (X,Y) (70), a test is made (72) to see if the Black bit is a 1. If so, the output pixel is assigned a Black value of one (1) (74), and the additive primaries Red, Green, and Blue are all set to zero (0) and the process continues with the next pixel. A one indicates that the corresponding toner will be printed and zero indicates that it will not be printed. If the Black bit is not a one, a test is made (76) to determine if the Cyan bit is a one (1). If so, a test is made (78) to determine if the Magenta bit is a one (1) and if it is, the output pixel is assigned (80) a Blue value of one (1) and the other additive primaries, including black are set to zero (0) and the process continues with the next pixel. If the Magenta bit is a zero (0), a test is made (82) to determine if the Yellow bit is a one (1), and if so, the Green component of the output pixel is set to one (1) and the other components are set to zero (0) 84 and the process continues with the next pixel. If the Yellow bit is zero (0), a test is made (86) to see if the pixel is an Even pixel. If the pixel is even, the Blue component of output pixel is set to one (1) (88) and the other components are set to zero (0) and the process continues with the next pixel. If the pixel is Odd, the Green component of the output pixel is set to one (1) (90) and the other components are set to zero (0) and the process continues with the next pixel. Since blue and green when viewed next to each other will appear cyan, this portion of the process results in reproducing a very close approximation of the desired color of the output image.

If the Cyan bit of the pixel was zero (0), a test is made (92) to determine if the Magenta bit of the pixel is a one (1). If so, a test is made (94) to determine if the Yellow bit is a one (1),a and if so, the output pixel is set to Red (96) and the process continues with the next pixel. If the Yellow bit is a zero, a test is made (98) to determine if the pixel is Even, and if so the output is set to Red (100) and the process continues with the next pixel. If the pixel is Odd, the output is set to Blue (102) and the process continues with the next pixel. Since red and blue when viewed next to each other will appear magenta, this portion of the process results in reproducing a very close approximation of the desired color of the output image.

If the Magenta bit of the pixel was zero (0), a test is made (104) to determine if the Yellow bit is a one (1). If it is, a test is made (106) to see if the pixel is Even, and if so, the output pixel is set to Green (108) and the process continues with the next pixel. If the pixel is Odd, the output is set to Red (110) and the process continues with the next pixel. Since red and green when viewed next to each other will appear yellow, this portion of the process results in reproducing a very close approximation of the desired color of the output image.

Finally, if all the bits (Cyan, Magenta, Yellow and Black) were zero (0), the output pixel is made white (112), assuming that the printing medium is white.

The processing steps shown in FIG. 6 can be summarized in Table 1 below.

In the example shown in Table 1, the n-tuple is a 2-tuple with pixels designated as Even or Odd. The N members, where N=2, of the combinations of printer colorants and no colorant are indicated in the two right-hand columns of each row.

It should be noted that the order of processing the 1-bit Cyan, Magenta and Yellow subtractive primaries described in FIG. 6 is not important, and other processing orders, with appropriate modifications to account for the fact that preceding colors have already been tested and determined to be zero (0).

The method of the present invention was employed to process 24-bit full color digital images produced by scanning photographic film and printing the processed images on a 4 color electrophotgraphic printer having red, green, blue and black toners. The results were generally acceptable for office and business applications and represented a marked improvement over prior art accent color images.

In an example where the printer colorants are Red, Yellow, Blue and Black, the n-tuples will have 3 members and the corresponding assignments of printer colorants would appear as shown in Table 2.

A listing of a computer program written in the C language running on a Sun work station for performing the method of the present invention is included as Appendix A.

The invention has been described with reference to a preferred embodiment. However, it will be appreciated that variations and modifications can be effected by a person of ordinary skill in the art without departing from the scope of the invention. ##SPC1##

1 separate digital image into 3 multi-bit primary components step

2 convert to 3 1-bit components step

3 assign single printer colorant to each pixel step

10 color document printing system

12 scanner

14 central processing unit

16 mass storage device

18 keyboard

20 mouse

22 accent color printer

24 raster image processor

26 color marking engine

27 8-bit black component extracting step

28 primary colorant component converting step

30 1-bit subtractive color component converting step

32 1-bit additive color component converting step

34 determine unused colorant step

36 whole page

38 Even pixel

40 Odd pixel

41 get color value at X,Y step

42 store color value step

44 extract 8-bit Cyan portion step

46 determine if Even pixel step

48 test if Cyan value greater than upper threshold

50 set Cyan bit to one step

52 set Cyan bit to zero step

54 test if Cyan value greater than lower threshold

56 set Cyan bit to one step

58 set Cyan bit to zero step

60 extract Magenta portion step

62 assign Magenta bit step

64 extract Yellow portion step

66 assign Yellow bit step

68 assign Black bit step

70 get pixel value at X,Y step

72 test if Black bit is one

72 set output to Black step

76 test if Cyan bit is one

78 test if Magenta bit is one

80 set output to Blue step

82 test if Yellow bit is one

84 set output to Green step

86 test if Even pixel

88 set output to Blue step

90 set output to Green step

92 test if Magenta bit is one

94 test if Yellow bit is one

96 set output to Red step

98 test if Even pixel

100 set output to Red step

102 set output to Blue step

104 test if Yellow bit is one

106 test if Even pixel

108 set output to Green step

110 set output to Red step

112 set output to no colorant step