Abstract:
A method for processing a digitized continuous tone image for reproducing the image by a printing device, including (a) inputting a tone value of an input pixel of the image; (b) applying a plurality of levelsplit curves to the tone value, thus obtaining a plurality of level values, wherein each specific levelsplit curve of the curves corresponds to a level defined by (i) a combination of a dot density and a dot area; or (ii) an overlap of a plurality of such combinations; (c) inputting the plurality of level values to an error diffuser for obtaining an output pixel value for reproducing the image; wherein a fraction of the output pixels to be filled by an overlap of levels depends on the level values and is independent of the error diffuser

Description:
[0001]     This application claims the benefit of U.S. Provisional Application No. 60/572,834 filed on May 20, 2004. 
     
    
     FIELD OF THE INVENTION  
       [0002]     The present invention relates to the halftoning of continuous tone images for use in reproduction of such images.  
       BACKGROUND OF THE INVENTION  
       [0003]     To print a continuous tone image, customarily a halftoning process is applied to the image. Error diffusion, also indicated as “ED” in this document, is a well-established halftoning technique, especially suitable for printers that are able to produce dispersed dots, such as ink-jet printers.  
         [0004]     Several error diffusion algorithms exist, that may be used for grey scale and for color. One way to extend an algorithm from grey scale to color is to apply the grey-scale algorithm separately on each color component.  
         [0005]     In general, three methods exist to achieve a grey level in an image: area modulated printing, density modulated printing, and the combination of both. In area modulated printing, gray levels are achieved by applying a marking particle (such as ink or toner) to a smaller or larger area of a receiving substrate (such as paper). For ink-jet, this may be achieved by applying a larger quantity of ink, i.e. applying a larger drop size. In density modulated printing, grey levels are achieved by applying different types of marking particles to the receiving substrate, each type having a different density. For ink-jet, different ink densities (such as e.g. light cyan ink and dark cyan ink) may be used.  
         [0006]     More background information on ED can be found in the following three patents, herein each incorporated by reference in their entirety for background information only.  
         [0007]     U.S. Pat. No. 4,680,645 discloses multilevel error diffusion for a grayscale printing device using multiple drop sizes.  
         [0008]     U.S. Pat. No. 5,975,671 discloses an error diffusion method for a printing device having multiple ink densities and dot sizes (or drop sizes); the ED levels are translated by a LUT (look-up table) to density/drop size combinations. More information on multilevel error diffusion in general can be found in this patent.  
         [0009]     U.S. Pat. No. 5,963,714 discloses a multicolor and mixed-mode halftoning method, wherein a printer driver operates a printer capabale of multiple dot-placement geometries or resolutions and multiple inks per color channel. The halftoning includes error diffusion.  
         [0010]     In ordinary bilevel ED a gray value is quantized by means of thresholding. If the gray value is larger than the chosen threshold, the value is quantized to 1, otherwise it is quantized to 0. The quantisation error is distributed over neighboring unprocessed pixels. Therefore not the original pixel value is thresholded, but a modified pixel value which is equal to the original pixel value plus the quantization error the pixel has received from other, already processed, pixels. This feedback mechanism guarantees that the right mean tone value is produced.  
         [0011]     In multilevel ED, the thresholding procedure is replaced by a more general quantization scheme.  
         [0012]     The simplest quantization scheme is to quantize the modified pixel value to the nearest quantization level. The quantization error is once again fed to neighboring unprocessed pixels. The more quantization levels, the smaller the quantization error, and the better the quality of the ED image.  
         [0013]     The multilevels are realized in practice in ink-jet printers by using inks of different densities, multiple drop sizes (in this document, the drop size is the amount of ink applied to a given pixel), or a combination of both. Error diffusion may also be applied to other printing techniques than ink-jet. Thus, in general, a level may be realized by a combination of a dot area (cf. the area modulated printing discussed above) and a dot density (cf. density modulated printing as discussed above). Some multilevel printing devices may provide such combinations wherein the dot area is kept constant; others may provide combinations wherein the dot density is kept constant; still others may provide combinations wherein both the dot area and the dot density may vary.  
         [0014]     In case of a binary ink-jet printer using a light ink and a dark ink we can use a multilevel error diffusion with 3 levels: level 0=no drop of ink, level 1=a drop of light ink, level 2=a drop of dark ink.  
         [0015]     Another example of an ink-jet printer with 6 levels: level 0=no drop of ink, level 1=a small drop of light ink, level 2=a medium drop of light ink, level 3=a large drop of light ink, level 4=a medium drop of dark ink, level 5=a large drop of dark ink.  
         [0016]     While printing with multiple drop sizes is most often implemented in this way, printing with multiple ink densities is more often implemented by applying a set of inksplit curves, a set of lookup tables transforming each gray value into a set of gray values, one for each ink (e.g. light and dark ink). The thus obtained channels are processed independently by error diffusion algorithms to produce the output image channels. This method provides more control over how much light and dark ink is used to produce a certain tone value than the multilevel ED method. The inksplit method is chosen because the extra control on the ink quantities can be used to eliminate drying problems and image artifacts such as banding.  
       SUMMARY OF THE INVENTION  
       [0017]     The present invention includes a method for processing a digitized continuous tone image for printing the image by a printing device, as claimed in independent claim  1 . Preferred embodiments of the invention are set out in the dependent claims. Preferably, a method in accordance with the invention is implemented by a computer program. The invention also includes a system for carrying out such a method, and a computer readable medium including program instructions to carry out such a method. The invention further includes the printed material that is obtained by printing an image, obtained by such a method, on a receiving substrate.  
         [0018]     In a preferred embodiment of the invention a multilevel ED algorithm is provided that allows to specify for each tone the fraction of pixels filled by each of the ED levels.  
         [0019]     The specification may be made via a set of curves which may be hard-coded, read from file, specified by a user through a user interface.  
         [0020]     One embodiment in accordance with the invention includes a computer program product for processing a digitized continuous tone image for reproducing said image by a printing device, wherein the image includes a plurality of pixels. The computer program product includes: 
        first program instructions for inputting a tone value of an input pixel of the image;     second program instructions for applying a plurality of levelsplit curves to said tone value, thus obtaining a plurality of level values, wherein each specific levelsplit curve out of said plurality of levelsplit curves corresponds to a level defined by 
 
 (i) a combination of a dot density and a dot area, to be applied by said printing device to a receiving substrate for reproducing said image; or 
 
 (ii) an overlap of a plurality of such combinations; 
 
 and wherein each specific levelsplit curve defines, for the tone value of the input pixel, which fraction of output pixels of the image when reproduced by the printing device is to be filled by the level corresponding to the specific levelsplit curve when reproducing the tone value; 
    third program instructions for inputting the plurality of level values to an error diffuser for obtaining an output pixel value of an output pixel for reproducing the image; 
 
 wherein a fraction of the output pixels that is to be filled by an overlap of levels depends on the level values and is independent of the error diffuser, the overlap of levels being an overlap of at least a first level and a second level, wherein the first level is a first combination of a first dot density and a first dot area and the second level is a second combination of a second dot density and a second dot area. 
       
 
         [0024]     The computer program product may further include a computer readable medium wherein the first, second and third program instructions are recorded on the medium.  
         [0025]     Another embodiment in accordance with the invention includes a computer program product for processing a digitized continuous tone image for reproducing the image by a printing device, wherein the image includes a plurality of pixels. The computer program product includes: 
        first program instructions for inputting a tone value of an input pixel of the image;     second program instructions for applying a plurality of levelsplit curves to the tone value, thus obtaining a plurality of level values, wherein each specific levelsplit curve out of the plurality of levelsplit curves corresponds to a level defined by a combination of a dot density and a dot area, to be applied by the printing device to a receiving substrate for reproducing the image, and wherein each specific levelsplit curve defines, for the tone value of the input pixel, which fraction of output pixels of the image when reproduced by the printing device is to be filled by the level corresponding to the specific levelsplit curve when reproducing the tone value;     third program instructions for inputting the plurality of level values to an error diffuser for obtaining an output pixel value of an output pixel for reproducing the image; 
 
 wherein a fraction of the output pixels that is to be filled by an overlap of a first level and a second level depends on the level values and is independent of the error diffuser; and 
 
 wherein for each tone value a sum of the plurality of level values is at most equal to 100%. 
       
 
         [0029]     The computer program product may further include a computer readable medium wherein the first, second and third program instructions are recorded on the medium.  
         [0030]     Yet another embodiment in accordance with the invention includes a system for processing a digitized continuous tone image for reproducing the image by a printing device, wherein the image includes a plurality of pixels. The system includes: 
        a first input module for inputting a tone value of an input pixel of the image;     an applicator for applying a plurality of levelsplit curves to the tone value, thus obtaining a plurality of level values, wherein each specific levelsplit curve out of the plurality of levelsplit curves corresponds to a level defined by 
 
 (i) a combination of a dot density and a dot area, to be applied by the printing device to a receiving substrate for reproducing the image; or 
 
 (ii) an overlap of a plurality of such combinations; 
 
 and wherein each specific levelsplit curve defines, for the tone value of the input pixel, which fraction of output pixels of the image when reproduced by the printing device is to be filled by the level corresponding to the specific levelsplit curve when reproducing the tone-value; 
    a second input-module for inputting the plurality of level values to an error diffuser for obtaining an output pixel value of an output pixel for reproducing the image; 
 
 wherein a fraction of the output pixels that is to be filled by an overlap of levels depends on the level values and is independent of the error diffuser, the overlap of levels being an overlap of at least a first level and a second level, wherein the first level is a first combination of a first dot density and a first dot area and the second level is a second combination of a second dot density and a second dot area. 
       
 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0034]     The invention is described with reference to the following drawings without the intention to limit the invention thereto, and in which:  
         [0035]      FIG. 1  diagrammatically shows an embodiment in accordance with the invention; and  
         [0036]      FIG. 2  shows a set of levelsplit curves as used by the embodiment of  FIG. 1 . 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0037]     In a preferred embodiment of the invention, a set of levelsplit curves is used, that define, for each tone value and each level, what fraction of the pixels will be filled by the different levels, i.e. what contribution the different levels make to reproduce a given tone value. In the case of a binary printer the set levelsplit curves may be the set of inksplit curves.  
         [0038]      FIG. 2  shows an example of levelsplit curves for a printing system with three drop sizes (small, medium, large). In diagram  50 , the horizontal axis  51  represents tone value, while the vertical axis  52  represents level value. Each tone value is transformed into a maximum of three level values in this example, as there are three levelsplit curves: curve  53  for the small drop size, curve  54  for medium drop size and curve  55  for large drop size. For example tone value G is transformed into level values G_ 1  and G_ 2 .  
         [0039]     In this drawing, the tone value and level values are in the range 0 to 255. They may of course also be in other ranges; they may also be scaled to the interval 0 to 1, or 0 to 100%, as is generally done in the description below.  
         [0040]     These curves may be designed by a user with the help of a user interface, allowing to draw curves or to specify curves by changing a few numbers, such as the start and end point of the different curves, their maximal height, etc. Alternatively they may be generated by a computer program to optimize certain system properties such as grain, ink amount, banding artifacts, etc.  
         [0041]     A levelsplit curve may also be given in the form of a table.  
         [0042]     As discussed above, a level may be realized by a combination of a dot area, corresponding in ink-jet printing to an ink drop size, and a dot density, corresponding in ink-jet printing to an ink density.  
         [0043]     Moreover, a level may also correspond to an overlap of at least two dot area/dot density combinations, as will now be explained.  
         [0044]     Take again the example with 6 levels discussed above: level 0=no drop of ink, level 1=a small drop of light ink, level 2=a medium drop of light ink, level 3=a large drop of light ink, level 4=a medium drop of dark ink, level 5=a large drop of dark ink. This case may be represented by five levelsplit curves, for levels 1 to 5. We can avoid overlaps of the different levels on a single pixel, by keeping the sum of all curves smaller than or at most equal to one (i.e. 100%). In case we do want to allow for overlaps, we may achieve this in different ways.  
         [0045]     In a first embodiment, the overlaps are defined as additional levels, and we will have a separate curve describing the contribution of such an additional level to the tone value. E.g. in the binary printer example discussed above we may have 4 levels instead of 3: level 0=no drop of ink, level 1=a drop of light ink, level 2=a drop of dark ink, and now additionally level 3=a drop of both light and dark ink on top of each other. We will need 3 levelsplit curves in this case.  
         [0046]     In a second embodiment, we allow that the sum of the levelsplit curves is larger than 1. E.g. when at a particular tone value we have a contribution of 40% of level 1 and 70% of level 2, this will result in a 10% overlap of levels 1 and 2 (10%=40%+70%-100%).  
         [0047]     In both these embodiments, it is possible to specify the exact amount of overlap between each of the levels. This is an additional advantage of using levelsplit curves. When using the classic inksplit curves with standard error diffusion, the overlap between drops of light ink and dark ink is not controlled entirely by the curves, but depends to a large extent on the details of the error diffusion process. Take for example a case with two inksplit curves, and suppose that for a given tone value, level 1 =20% and level 2 =20%. If now, for both levels, an ED algorithm is used that is sufficiently random (e.g. by providing enough noise, or by changing the threshold value in a random way), then the overlap of both levels will be 0.2×0.2=0.04=4%. If, on the other hand, for both levels identically the same error diffuser is used, without noise, then the same pixels will be set for both levels, so that the overlap will be 20%.  
         [0048]     In a preferred embodiment of the invention, the error diffuser is such that the overlap of the levels on a given pixel is controlled by the levelsplit curves and is independent of the error diffuser. This offers the advantage of full control over the specific contributions of the levels to the tone, as well as full control over the overlap between different levels. Moreover, this control may be done outside of the error diffusion process. The overlap may be controlled for printing devices using only one drop size and inks of different densities, for printing devices using multiple drop sizes and an ink of one density, for printing devices using multiple drop sizes and inks of different densities.  
         [0049]     The advantage of laying the full control of level usage outside of the error diffuser is that the error diffuser is far more adaptable to new situations, e.g. new printer type, new inks, new media, other application. It gives a user the possibility to rule out certain levels that may be responsible for certain artefacts such as banding. It offers the possibility to make other trade-offs between graininess and ink usage for different applications, without changing anything to the error diffusion algorithm.  
         [0050]     Moreover, the percentage of white pixels may be controlled as well. It is equal to 1 minus the sum of the levelsplit curves, when expressed in the interval 0 to 1.  
         [0051]     The levelsplit curves may be read from a file or even adapted interactively by a user of the ED.  
         [0052]     In classical multilevel error diffusion, using a multilevel quantiser or multiple thresholds, use of the different levels and their overlaps is only controlled partially and indirectly via manipulation and randomisation of the thresholds, as illustrated already above by the example of the two inksplit curves.  
         [0053]      FIG. 1  shows a preferred embodiment 10 of the invention, wherein the ED algorithm using the levelsplit curves is as follows.  
         [0054]     Suppose we have K levelsplit curves (i.e. K levels other than the one where no ink is applied; K=3 in  FIG. 1 ).  
         [0055]     The input image  20  contains a plurality of pixels  21 . We scan the image, e.g. in a linewise manner.  
         [0056]     For each encountered pixel  21 , we perform the following steps: 
    Step 1: Transform the incoming gray value G to K values G_ 1 , . . . , G_K by the levelsplit curves.     Step 2: Modify the values G_ 1 , . . . , G_K by adding the quantization errors received from neighboring, already processed pixels, G_i→G_i+E_i, i=1, . . . , K (this is feedback  71 , performed by quantizer  70 , in  FIG. 1 )     Step 3: Calculate the sum S=ΣG_i of the modified pixel values. (indicated by reference sign  30  in  FIG. 1 )     Step 4: Find the channel i=imax having the largest value of G_i.     Step 5: Quantization of the values G_i yielding output values O_i: If S is larger than the threshold T (reference  31  in  FIG. 1 ) 
        O_i=1, for i=imax (i.e. set a drop; reference  32 )     O_i=0, for all other i (i.e. no drop of ink; ref.  32 )     Else     O_i=0, for all i    
        Step 6: Diffuse quantization error for all K channels to neighboring, unprocessed pixels (by quantiser  70 ).    
 
         [0067]     When allowing sum values of levelsplit curves larger than 1, step 5 above will be replaced by: 
    Step 5′: Quantization of the values G_i yielding output values O_i: O_i=0, for all i    
 
         [0069]     While S is larger than the threshold T 
        O_i=1, for i=imax     S is replaced by S−1     G_i is replaced by G_i−1     Find the channel i=imax having the largest value of G_i        
 
         [0074]     When the sum of the levelsplit curves is smaller than 2 (=200%), the above while loop is performed no more than 2 times at most.  
         [0075]     The quantized level values  80  are now used to set pixel  91  in output image  90 .  
         [0076]     Other embodiments of an ED algorithm that uses the levelsplit curves are as follows. Instead of using the sum S of pixel values, another function f(G_ 1 , . . . , G_K) may be used. More specifically we may use a linear combination of the G_i, with minor adaptations to the algorithm outlined above.  
         [0077]     Another possibility of changing the algorithm is to group certain levels together (e.g. all levels with a certain drop size, irrespective of their ink density). We can then replace the binary threshold T by a multilevel quantiser. In our example, the output of this quantiser will be No drop/A drop of Light Ink/A drop of Dark Ink/An overlap of Light and Dark Ink. The second quantiser will then decide over the size of the drop.  
         [0078]     As discussed already above, in a preferred embodiment of the invention, the error diffuser is such that the overlap of the levels on a given pixel is controlled by the levelsplit curves and is independent of the error diffuser.  
         [0079]     The following example illustrates this: with two different sets of levelsplit curves, the contributions of two levels to reproduce a given tone value are the same, but the overlap of the levels is different, while nothing is changed to the error diffuser. The first set of curves contains two curves, for levels L 1  and L 2 , so that their sum is at most equal to 100% (these curves represent a combination of a dot density and a dot area, not an overlap). As explained before, the overlap is thus zero. The second set is based on the first set and contains three curves, as follows: 
        L OV =Min {L 1 ,L 2 } (i.e., for each tone value, the value of L OV  is the minimum value of L 1  and L 2 )     L′ 1 =L 1 −L OV       L′ 2 =L 2 −L OV  
 
 For this second set, L OV  gives the overlap of levels L 1  and L 2 ; this overlap is maximal. 
       
 
         [0083]     It is also possible to specify that a particular overlap of two levels is to be zero, or that more overlaps, even all overlaps of all levels are to be zero; this may be advantageous with respect to drying (in these cases, a level means a combination of a dot area and a dot density, not an overlap of two or more of such combinations).  
         [0084]     The present invention can be applied to black and white printing devices and to color printing devices. It is especially suitable for ink-jet printing, but may also be applied to other printing techniques (such as electrophotography). Also, white ink may be used, which may be together with a combination of other inks, e.g. CMYK inks, and possibly on a non-white (e.g. black) receiving substrate.  
         [0085]     Those skilled in the art will appreciate that numerous modifications and variations may be made to the embodiments disclosed above without departing from the scope of the present invention.  
       LIST OF REFERENCE SIGNS  
       [0000]    
       
           10 : embodiment  
           20 : input image  
           21 : input pixel  
           30 : sum  
           31 : threshold  
           32 : drop/no drop  
          G: tone value  
          G_ 1 : level value  
          G_ 2 : level value  
          G_ 3 : level value  
           50 : diagram  
           51 : axis  
           52 : axis  
           53 : levelsplit curve  
           54 : levelsplit curve  
           55 : levelsplit curve  
           70 : quantizer  
           71 : feedback  
           80 : quantized level values  
           90 : output image  
           91 : output pixel