Method and apparatus for generating digital halftone images by multi color dithering

[0001] The present invention relates generally to the field of digital image synthesis and, more particularly to digital color image reproduction, digital color image printing, digital color image display and anti-counterfeiting protection. The invented method and apparatus enable generating digital halftone images by multi-color dithering. The invented method and apparatus are particularly effective for generating images on color printers printing with more colors than cyan, magenta, yellow and black, and for generating images incorporating microstucture patterns (micro-characters, symbols and ornaments) made of a combination of standard and non-standard inks. Non-standard inks comprise non-process colors, opaque inks, and special inks such as metallic ink, variable color inks and fluorescent inks. The generated images are displayed on color displays or printed on physical output devices such as ink-jet printers, electrophotographic printers, offset printers or gravure printers.

[0002] The reproduction of color images requires in the general case (1) separating the image colors (for example red, green and blue) into the set of available printable colors (for example cyan, magenta, yellow and black), (2) halftoning each of the printable color layers and (3) printing the halftoned image or visualizing it on a display device.

[0003] Most existing color halftoning techniques are based on the independent halftoning of each of the contributing color layers. In offset and in many electrographic printers, the color halftone layers are generated independently at angles of 15, 45, 75 degrees in order to avoid interferences between the cyan, magenta and black layers. Ink-jet printers often use error-diffusion to halftone each of the color layers independently.

[0004] Existing approaches for color separation with non-standard inks consider that color layers can be printed independently from one another. This is true as long as the inks are transparent and as long as the dots of each screen are randomly positioned with respect to the dots of the other screens, as assumed by the Neugebauer equations (see G. L. Rogers, “Neugebauer Revisited: Random Dots in Halftone Screening”, Color Research and Applications, Vol. 23, No. 2, pages 104–113, 1998).

[0005] If these assumptions are not true, halftoning each of the color layers independently may generate color shifts depending on the amount of superposition between screen dots of individual halftone layers. As long as the inks are transparent, the color shifts are small and the reproduction fidelity can be ensured by calibrating the printing device (see H. R. Kang, Color Technology for Electronic Imaging Devices, SPIE Publication, 1997, chapter 12).

[0006] Some applications however require that different inks be always printed side by side without overlapping. This is the case, for example, when printing with opaque inks as taught by inventor H. Kueppers in U.S. Pat. No. 4,812,899, issued Mar. 14, 1989. Different inks must also be printed side by side for some printing devices as taught by J. Gereadts and S. Lenczowski, “Océ's productive colour solution based on the Direct Imaging Technology”, Proceedings of the IS&T International Conf. On Direct Imaging Technology, Vol. NIP-13, 1997, pages 728–733.

[0007] Manufacturers of valuable documents, such as banknotes, identity cards and checks make often use of the high registration accuracy of their original printing equipment to create a graphic design which is both visually pleasant and difficult to imitate using standard printing processes (see Rudolf L. VanRenesse, Optical Document Security, Artech House 1998, chapter 6). In addition, they may use non-standard inks (sometimes also called custom inks), i.e. inks which have a color different from process colors Cyan, Magenta, Yellow and Black to reproduce images and graphic designs. Similar anti-counterfeiting techniques are used to print commercial packages which need to be protected against illegal counterfeits (drugs, cosmetics, etc.).

[0008] One prior art method of generating a dither pattern for an RGB value, is taught by D. N. Weise and H. Gunter Zieber in U.S. Pat. No. 5,485,558, issued Jan. 16, 1996. That method is limited to applications, mainly display applications, where one can associate to each input color pixel a dither array, for example an 8×8 array, in order to reproduce that color pixel. Since the dither array must remain of small size, that method does not allow to create at the screening layer artistic screen shapes. Another prior art method of color halftoning is to use vector error-diffusion in color space, as taught by J. Sullivan and R. L. Miller in U.S. Pat. No. 5,070,413, issued Dec. 3, 1991. However, error-diffusion has the drawback of inducing considerable dot gain, compared with clustered dot dithering methods. In addition, error-diffusion does not allow to create user-defined screen shapes.

[0009] The present invention discloses a new multi-color dithering method which automatically enforces side by side printing of several color and/or metallic ink layers. Thanks to a user definable dither function or dither array of freely chosen size, multi-color dithered images may incorporate identifyable screen shapes, for example artistic screen shapes, which can be used for document authentication. Combined with color separation by tetrahedral interpolation, multi-color dithering enables printing images made of non-standard inks.

[0010] The invented method is a non-trivial generalization of ordered dither halftoning, which uses spatial dithering in order to obtain clustered-dot or dispersed-dot binary patterns on output devices (see H. R. Kang, Digital Color Halftoning, SPIE Press/IEEE Press, 1999, chapters 13 and 14).

[0011] The present invention provides a method and apparatus and a preferred implementation as a computing system for the reproduction of color images by a new method that will be called hereinafter “multi-color dithering”. Multi-color dithering is characterized by the use of a two-dimensional dither function and the use of an arbitrary number of inks and superposition of inks as primary colors. The inks may comprise standard inks and non-standard inks such as non-process colors, opaque inks, metallic inks and variable color inks. Multi-color dithering provides a solution for printing color images with a freely chosen set of standard or non-standard inks. It also provides a solution for creating artistic multi-color dithered images incorporating a microstructure made of artistic color screen shapes such as micro-letters, symbols and ornaments. When printed at high resolution and at high registration accuracy, multi-color dithering using large dither arrays incorporating artistic dither shapes provides an effective solution for preventing counterfeiting. The use of non-standard inks offers additional protection. Multi-color dithering offers also a solution for printers requiring that all inks are printed side by side, without overlaps.

[0012] The invented method comprises the steps of (1) defining a two dimensional dither function G(x,y); (2) choosing a set of primary colors {C_i} located within a three-dimensional color working space ABC, where ABC stands for RGB, CIE-XYZ, CIE-LAB or any other color space; (3) initiating a neighbor finding procedure which renders neighboring primary colors {C_j} of a given input color C in the three-dimensional color space ABC; (4) computing the primary color of each output image pixel O(x,y) by a set of substeps; and (5) outputting the resulting color output image on a printing or a display device. To define a two-dimensional dither function, one may either build it or take an existing two-dimensional dither function, often implemented as a dither array or a dither matrix. The substeps for computing the primary color of each output image pixel O(x,y) comprise (1) locating in the input color image an input color location (x′,y′) and computing its corresponding color C(x′,y′); (2) finding the N neighbor primary colors {C_j} of C(x′,y′) in the ABC color space by using the neighbor finding procedure; (3) computing the amount S_j(x,y) of every neighbor primary color C_j; (4) determining the output primary color O(x,y) at output pixel (x,y) by determining at each position (x,y) the partition P_j(x,y) within which the dither function G(x,y) is situated; and (5) by assigning neighbour primary color C_j associated to partition P_j(x,y) to the output pixel primary color O(x,y). Partitions P_j represent at each pixel (x,y) the respective amounts S_j(x,y) of neighbouring colors C_j.

[0013] With modern technology, a preferred embodiment of a multi-color dithering apparatus is a computing system storing in its memory an input color image, the values of a two-dimensional dither function, a neighborhood calculation software procedure, a multi-color dithering software procedure and the resulting output multi-color dithered image. Its central processing unit interacts with the computing system's memory, runs the neighborhood calculation and multi-color dithering software procedures, computes for each output multi-color image pixel an output primary color selected from a set of primary colors, stores the resulting output color-dithered image in memory and forwards it to an output device, for example a printer or a display device.

[0043] The present invention concerns a color halftoning technique using an arbitrary set of primary colors, as shown in FIG. 9A. The set 900 of primary colors fills in a non-uniform manner a three-dimensional color space ABC. ABC stands for any convenient representation of a three-dimensional color space, such as RGB, CIE-XYZ, CIE-LAB, or any other representation known in the art.

[0044] The term “primary color” refers to a color which belongs to the set of colors available to reproduce a color image. Such colors are generally the colors of the available inks and of the allowed superpositions of two or more layers of inks in the case of transparent inks. In the case of a metallic ink, the color associated to the metallic ink is the color that is being captured when the effect of specular reflection is cancelled (for example when measured with an instrument that avoids capturing specular reflection). In the case of a variable color ink, the color associated to the variable color ink color used for multi-color dithering is one of its possible colors, i.e. the color which appears when the image is viewed at a certain desired display angle. In the case of a fluorescent ink, the color associated with the fluorescent ink is the color that is perceived or measured under normal light (for example a light source A or D65).

[0045] The ordered dither method known in the prior art is clearly illustrated for the one-dimensional case by FIGS. 2A, 2B and 2C. FIG. 2A shows a one-dimensional input signal S(x) in the range [0 . . . 1]. The input signal S(x) is compared with a dither threshold function (also called dither function) T(x) shown in FIG. 2B. A set of black spans 230 is generated for coordinates x where S(x)<T(x), as shown in FIG. 2C. These black spans represent the inked areas obtained by dithering the input signal. This method is only based on the comparison of the input signal value with the dither threshold value. This method is conceptually simple and computationally efficient.

[0046] In the prior art two-dimensional case (see FIG. 5), a two-dimensional dither threshold function T(x,y) (also called two-dimensional dither function or spot function) is provided. In most cases, the two-dimensional dither threshold function T(x,y) is a discrete dither function with dither threshold values 540 associated to the elementary cells of the dither tile 500 paving the plane (see FIG. 5). The tiling is usually characterized by two basic translation vectors 510 and 520. A dither tile represents the spatial extent of one period of a repetitive discrete dither function. A simple and straightforward way of generating the set of dither threshold values 540 consists in constructing the double spiral path 530 which fills the dither tile 500, as shown in FIG. 5. The values of the basic dither tile are generated by simply increasing the ordinal number along the path 530. The generated ordinal numbers are normalized by a normalization coefficient of value 1/S, where S is the area of the dither tile (number of individual elementary cells). Such a spiral path is responsible for the clustered appearance of both the white and the black areas of the halftoned image.

[0047] An alternative prior art method of creating a discrete dither function (also called dither array) is to sample a continuous dither function at each dither tile cell and to replace successive sample values by successive ordinal numbers in the range [0 . . . S−1], where S is the number of elementary cells in the dither tile (or dither array). Again, the generated ordinal numbers are normalized by a normalization coefficient of value 1/S, where S is the area of the dither tile (number of individual cells). Further prior art methods of creating dither functions are described in the book written by H. R. Kang, Digital Color Halftoning, SPIE Press/IEEE Press, 1999, chapters 13 and 14.

[0048] In order to explain the invented multi-color dithering menthod starting from the prior art ordered dithering method, let us first consider a one-dimensional case shown in FIGS. 3A–3D. Instead of considering the one-color input signal S(x) in FIG. 2A, we consider two signals: color C1 input signal S₁(x) and color C2 input signal S₂(x), as shown in FIG. 3A. Color C1 can be considered to be the ink color, and color C2 the white paper color. S₁(x) and S₂(x) can be assumed to be the relative normalized (i.e. S₁(x)+S₂(x)=1) amounts of ink color and white paper color, expressed as values between 0 and 1. Functions S₁(x) and S₂(x) can be combined in a color distribution map made of two partitions P1 and P2 as shown in FIG. 3D. This map shows, for every coordinate x, the proportions of input color signals S₁(x) and S₂(x). By construction, the color distribution map splits the vertical strip of height 1 into two adjacent vertical partitions, which represent input color signals S₁(x) and S₂(x). In FIG. 3D, partition P1 corresponds to the input color signal S₁(x) and partition P2 corresponds to the input color signal S₂(x). The lower boundary of P1 is 0 and its upper boundary is S₁(x). The lower boundary of P2 is S₁(x) and its upper boundary is 1. Referring to FIG. 3B, a simple dither function G(x) identical to the dither threshold function T(x) (FIG. 2B) is provided, having the range [0 . . . 1].

[0049] The invented multi-color dithering method consists in determining for every coordinate x within which partition of the color distribution map the dither function G(x) is situated (FIG. 3C):

• • [0050] when the dither function G(x) is situated within partition P2, representing the amount of input signal S₂(x) of primary color C2, spans 330 of primary color C2 are generated.
  • [0051] when, in turn, the dither function G(x) is situated within partition P1, representing the amount of the input signal S₁(x) of primary color C1, spans 331 of primary color C1 are generated.

[0052] By construction, primary colors C1 and C2 are laid out side by side, without holes or overlaps.

[0053] Referring now to FIG. 4, the same mechanism of determining within which partition of the color distribution map the dither function G(x) is situated can be applied to the case of any number of independent input color signals. Let S₁(x), S₂(x), S₃(x) and S₄(x) be the relative normmalized (i.e. S₁(x)+S₂(x)+S₃(x)+S₄(x)=1) amounts of four color input signals of primary colors C1, C2, C3 and C4, as shown in FIG. 4A. Any of the colors C1, C2, C3 and C4 can be the white paper color (or the background color); the others are the primary colors used to halftone the image. A color distribution map shown in FIG. 4C can be created, applying the same method as in the previously described two-color case. It comprises four separate partitions which represent the amount of the four primary colors C1, C2, C3 and C4. In FIG. 4B, partition P1 represents the amount of input signal S₁(x) of primary color C1. The lower boundary of P1 is 0 and its upper boundary is S₁(x). Partition P2 represents the amount of input signal S₂(x) of primary color C2. The lower boundary of P2 is S₁(x) and its upper boundary is S₁(x)+S₂(x). Partition P3 represents the amount of input signal S₃(x) of primary color C3. The lower boundary of P3 is S₁(x)+S₂(x) and its upper boundary is S₁(x)+S₂(x)+S₃(x). Partition P4 represents the amount of input signal S₄(x) of primary color C4. The lower boundary of P4 is S₁(x)+S₂(x)+S₃(x) and its upper boundary is 1.

[0054] FIG. 4C shows the color dithering process for the one-dimensional four-color variant of the invented multi-color dithering method:

• • [0055] when the dither function G(x) is situated within partition P1, representing the amount of input signal S₁(x) of primary color C1, the primary color C1 is generated;
  • [0056] when the dither function G(x) is situated within partition P2, representing the amount of input signal S₂(x) of primary color C2, the primary color C2 is generated;
  • [0057] when the dither function G(x) is situated within partition P3, representing the amount of input signal S₃(x) of primary color C3, the primary color C3 is generated;
  • [0058] when the dither function G(x) is situated within partition P4, representing the amount of input signal S₄(x) of primary color C4, the primary color C4 is generated.

[0059] By construction, primary colors C1, C2, C3 and C4 are laid out side by side, without holes or overlaps.

[0060] Referring to FIGS. 6–8, one-dimensional multi-color dithering can be extended to two-dimensional multi-color dithering, which is of practical interest because printing on a two-dimensional support (paper, films etc.) is the main purpose of color halftoning.

[0061] Like in prior art bi-level dithering, the continuous one-dimensional dither function G(x) may be replaced as shown in FIGS. 6–8 by a discrete two-dimensional dither function G(x,y). The dither function G(x,y) shown as example in FIG. 6 forms a repetitive tile 600 which paves the plane. Tile cells incorporate the discrete values G(x,y). This tile is characterized by two basic translation vectors 610 and 620. A set of discrete values of the dither function G(x,y) can be obtained by incrementing ordinal numbers 640 in the range [0 . . . S−1], where S is the area of the basic tile 600 expressed as the number of elementary cells, along the space-filling curve 630 which fills the tile and by subsequent normalization with the normalization coefficient 1/S.

[0062] Another example of construction of the basic tile and of the discrete dither function G(x,y) is shown in FIG. 7. The dither function G(x,y) in FIG. 7 forms a square tile 700, characterized by two basic translation vectors 710 and 720. A set of discrete values of the dither function G(x,y) can be obtained by incrementing ordinal numbers 740 along the space-filling curve 730 and by subsequent normalization with normalization coefficient 1/S.

[0063] FIG. 8 illustrates the mechanism of the invented halftoning method, in the example of four primary colors C1, C2, C3 and C4, and the two-dimensional discrete dither function G(x,y) shown in FIG. 7. Let us imagine an input color image C having a uniform color, which is reproduced by the weighted sum of the primary colors C1, C2, C3 and C4:

[0064]

	C = S1(x,y)*C1 + S2(x,y)*C2 + S3(x,y)*C3 + S4
	(x,y)*C4 where
	S1(x, y) = 0.24	S2(x, y) = 0.20
	S3(x, y) = 0.28	S4(x, y) = 0.28

[0065] Applying the multi-color dithering mechanism described above to the color distribution map derived from the values of input signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) leads to the color dithered image shown in the area representing the top half (850) of FIG. 8. Each tile incorporates an area 810 filled with the primary color C1; an area 820 filled with the primary color C2; an area 830 filled with the primary color C3, and an area 840 filled with the primary color C4.

[0066] The clustered behavior of separate color areas is insured by the nature of the space-filling curve (FIG. 7, 730) which provides the successive cell numbers 800 of the dither function G(x,y). Various well-known space-filling curves like Hilbert's or Peano's space-filling curves, arranged to fill a tile, can meet the requirement of clustered behavior.

[0067] By choosing an appropriate space-filling curve which governs the process of generation of the dither function G(x,y), one can enhance a particular behavior of the halftoning process.

[0068] A further method of generating a discrete dither function consists in transforming a bi-level shape design into a grayscale intensity image by using a commercial image processing software package (Adobe PhotoShop, for example) and by applying histogram equalization to obtain the values of the discrete dither function.

[0069] Techniques known in the art for the creation of dither threshold functions, respectively dither arrays can be applied to create the dither functions used in multi-color dithering (see H. R. Kang, Digital Color Halftoning, SPIE Press/IEEE Press, 1999).

[0070] There are many reasons for printing with non-standard inks. One may want to enlarge the gamut of the printed image by printing for example with red, green and blue inks in addition to process colors cyan, magenta and yellow. One may also want to print with non-standard colors, in order to prevent counterfeiting documents with standard color copiers and printers printing only with cyan, magenta, yellow and black inks. For example, commercial goods packages, checks, identity cards and valuable documents need to be appropriately protected. Further protection may be given by printing with special inks, for example variable color inks, metallic inks or fluorescent inks (see Rudolf L. VanRenesse, Optical Document Security, Artech House 1998, chapters 7 and 9).

[0071] Let us assume that we have a set of primary colors, made of a freely chosen combination of standard (i.e. process color inks) and non-standard inks. Non-standard inks may comprise transparent non process color inks, opaque inks, metallic inks, variable color inks and fluorescent inks. An input color image is to be reproduced with the selected set of primary colors. One triplet of values C_j given in the three-dimensional space ABC is associated to each of the primary colors j.

[0072] Let us now explain how relative normalized amounts of primary colors, i.e. how input signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) can be generated with respect to a given set of primary colors 900 in the three-dimensional working space ABC. According to a prior art method from the field of computational geometry (see for example J. D Boissonat, M. Teillaud, “A Hierarchical Representation of Objects: The Delaunay tree” Proceedings of the 2nd annual ACM Symposium on Computational Geometry, Yorktown Heights, N.Y., Jun. 2–4, 1986, pp. 260–268), a non-ambiguous process of subdivision of the space ABC into a set of tetrahedra having as vertices the primary colors 900 can be provided. FIG. 9B shows an example of such a subdivision into a set 910 of tetrahedra having as vertices the primary colors 900. The external boundary of the set 910 of all available tetrahedra whose vertices are the set 900 of available primary colors is often called the printable color gamut.

[0073] For an arbitrary input color C there are two possibilities: if it is located inside the set 910 given by the set of available primaries 900, color C is said to be “in gamut”, or if it is located outside the set 910 given by the set of available primaries 900, color C is said to be “out of gamut”. Without loss of generality, let us consider only the case of “in gamut” input colors: otherwise, a specific gamut-mapping method, which projects the colors from outside the color gamut back into the color gamut, should be provided (see E. J. Stollnitz, V Ostromoukhov, D. H. Salesin, Reproducing Color Images Using Custom Inks, Proceedings of SIGGRAPH 98, Annual Conference Series, 1998, pages 267–274).

[0074] For any input color C inside the gamut, a tetrahedron can be found which contains the input color. FIG. 10 shows a tetrahedron 1060 of the set 910 which contains an input color C. We would like to represent the input color C as a barycentric combination of the primary colors V1, V2, V3 and V4, vertices of the tetrahedron enclosing input color C. With a symbolic mathematical software package, for example Mathematica (http:www.wolfram.com) it is easy to show that the relative amounts of primary colors S₁(x,y), S₂(x,y), S₃(x,y), S₄(x,y) can be computed as follows.

[0075] The amount of primary color S₁(x,y) associated with the vertex V1 is computed as the ratio between the Euclidean distance 1010 from the input color C to the tetrahedron's face V2-V3-V4, opposite to the vertex V1, and the Euclidean distance from the vertex V1 to the tetrahedron's face V2-V3-V4.

[0076] Similarly, the amount of primary color S₂(x,y) associated with the vertex V2 is defined as the ratio between the Euclidean distance 1020 from the input color C to the tetrahedron's face V1-V3-V4, opposite to the vertex V2, and the Euclidean distance from the vertex V2 to the tetrahedron's face V1-V3-V4.

[0077] Similarly, the amount of primary color S₃(x,y) associated with the vertex V3 is defined as the ratio between the Euclidean distance 1030 from the input color C to the tetrahedron's face V1-V2-V4, opposite to the vertex V3, and the Euclidean distance from the vertex V3 to the tetrahedron's face V1-V2-V4.

[0078] Similarly, the amount of primary color S₄(x,y) associated with the vertex V4 is defined as the ratio between the Euclidean distance 1040 from the input color C to the tetrahedron's face V1-V2-V3, opposite to the vertex V4, and the Euclidean distance from the vertex V4 to the tetrahedron's face V1-V2-V3.

[0079] Amounts of primary colors S_j(x,y) are also referred to as input signals S_j(x,y). These signals are input signals for the subsequent multi-color dithering step.

[0080] When using real inks for the primary colors, one can allow as primary colors the colors resulting from the combinations of two or more inks by defining explicitly for each allowed combination of inks an additional color C_k which becomes part of the set of primary colors 900 (FIG. 9A).

[0081] The reproduction of color images by the invented multi-color dithering method comprises the following steps:

Step G1:

[0082] Define a two-dimensional dither function G(x,y). It may either be large and cover the full output image space or be a repetitive tile which paves the plane. A repetitive tile is characterized by two basic translation vectors and by a set of discrete values, one for every elementary cell of the tile. One possible way of building the discrete values consists in incrementing ordinal numbers along a space-filling curve which walks through the elementary cells of a tile. A two-dimensional dither function G(x,y) can be stored in a dither function storage unit.

Step G2:

[0083] Choose a set of primary colors {C_i} located within a three-dimensional color working space ABC, where ABC stands for any convenient representation of a three-dimensional color space, such as RGB, CIE-XYZ, CIE-LAB, or any other color space representation used in the art. Usually the set of primary colors {C_i} represents the set of available basic colors used for reproduction, such as, for example, a set of Pantone inks. The set of primary colors contains also the permitted superpositions of pure inks. It can also represent the set of available basic colors used to represent an image (for example, many TIFF color images are represented by a set of 256 basic colors). A primary color may also be the color associated with a metallic ink, with a variable color ink seen from a certain angle, or with a fluorescent ink seen with normal light.

Step G3:

[0084] Initialize a procedure defining a neighborhood in three-dimensional color space, for example a procedure which renders neighbor primary colors {C_j} of a given input color C expressed in the three-dimensional color working space ABC, where j is an integer number in the range [0 . . . N_neighbors−1] and where N_neighbors expresses the number of considered neighbors.

Step G4:

[0085] For every individual pixel (x,y) of the output image (resulting dithered image), apply steps G4.1 to G4.4. The coordinates (x,y) of each pixel of the output image define the corresponding value of the two-dimensional dither function G(x,y).

[0086] Step G4.1: Find the corresponding location (x′,y′) in the input color image in the same way as in prior art bi-level dithering and determine color C(x′,y′) at that location. Usually, a linear interpolation technique is used to derive color C from the colors of neighboring input image pixels, i.e. pixels located in the neighborhood of loation (x′,y′). Nevertheless, other interpolation techniques known in the art can be equally applied. The input color C(x′,y′) in general does not belong to the set of primary colors {C_i}.

[0087] Step G4.2: Find the neighbor colors {C_j} among the primary colors {C_i}, using the procedure rendering the neighbors of a given input colour in the ABC color working space.

[0088] Step G4.3: In order to reproduce input color C(x′,y′), compute for neighbor colors {C_j} their relative normalized amounts, i.e. their corresponding signals {S_j(x,y)}.

[0089] Step G4.4: At the current (x,y) pixel, determine the partition within which the two-dimensional dither function G(x,y) is situated and accordingly, put the corresponding output primary color O(x,y) at pixel (x,y) of the output image. Proceed according to the following detailed rules:

[0090] if dither function G(x,y) is situated within partition P1, i.e. 0<G(x,y)<=S₁(x,y), O(x,y) is assigned the neighbor color C₁;

[0091] if dither function G(x,y) is situated within partition P2, i.e. S₁(x,y)<G(x,y)<=S₁(x,y)+S₂(x,y), O(x,y) is assigned the neighbor color C₂;

[0092] . . .

[0093] if dither function G(x,y) is situated within partition PN, i.e. S₁(x,y)+ . . . +S_j-1(x,y)<G(x,y)<=S₁(x,y)+ . . . +S_N(x,y), O(x,y) is assigned the neighbor color C_N, where N is the number of neighbor colors in set {C_j}.

[0094] In a preferred embodiment, steps G3–G4 and substeps G4.1 to G4.4 can be implemented as steps P3–P4 and substeps P4.1 to P4.4 as described below.

Step P3 (Preferred Embodiment of Step G3):

[0095] In order to define a neighborhood in 3D color space, subdivide the color working space ABC into a set of tetrahedra {T_k}, which do not intersect each other and whose vertices are the set of primary colors. According to known results in computational geometry, such a subdivision is always possible, for any set {C_j} of primary colors. A subdivision according to Delauney has been extensively studied (see for example J. D Boissonat, M. Teillaud, “A Hierarchical Representation of Objects: The Delaunay tree”, Proceedings of the 2nd annual ACM Symposium on Computational Geometry, Yorktown Heights, N.Y., Jun. 2–4, 1986, pp. 260–268). We consider only non-degenerate tetrahedra, i.e. tetrahedra which have a non-zero volume.

Step P4 (Preferred Embodiment of Step G4):

[0096] For every individual pixel (x,y) of the output image, apply the steps P4.1–P4.4:

[0097] Step P4.1: Find the corresponding location (x′,y′) in the input color image and determine color C(x′,y′) at that location as explained in step G4.1.

[0098] Step P4.2: Find the tetrahedron T in the tetrahedral subdivision {T_k} which contains color C(x′,y′). The simplest method of finding the tetrahedron T consists in applying to candidate tetrahedra T_i of the set {T_k} an “interior membership test” to verify if color C(x′,y′) is inside tetrahedron T_i (see section “Interior Membership Test” below). The tetrahedron of the set {T_k} which contains the color C(x′,y′) is designated as T. The 4 vertices of T are the neighbors of color C and designated as primary colors C₁, C₂,C₃,C₄. Techniques speeding up the search of tetrahedron T containing color C can be applied (see for example P. C. Hung, Colorimetric calibration in electronic imaging devices using a look-up-table model and interpolations, Journal of Electronic Imaging Vol. 2, No. 1, pp. 53–61, January 1993, section 3.1, page 56).

[0099] Step P4.3: Find the four ratios between the Euclidian distances from the input color C(x′,y′) to every of the four faces of the tetrahedron T found in step P4.2, and the Euclidean distances from the same tetrahedron's faces to their opposite vertices, according to the technique described in section “Color separation for non-standard inks”. These four ratios define the values of input signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y), associated to the current output image pixel (x,y).

[0100] Step P4.4: At the current (x,y) pixel, determine the partition within which the two-dimensional dither function G(x,y) is situated and accordingly, put the corresponding output primary color O(x,y) at pixel (x,y) of the output image. Proceed according to the following detailed rules:

[0101] if dither function G(x,y) is situated within partition P1, i.e. 0<G(x,y)<=S₁(x,y), O(x,y) is assigned color C1 associated with the vertex of tetrahedron T used in step P4.3 to define the signal S₁(x,y);

[0102] if dither function G(x,y) is situated within partition P2, i.e. S₁(x,y)<G(x,y)<=S₁(x,y)+S₂(x,y), O(x,y) is assigned color C2 associated with the vertex of the tetrahedron T used in the step P4.3 to define the signal S₂(x,y);

[0103] if dither function G(x,y) is situated within partition P3, i.e. S₁(x,y)+S₂(x,y)<G(x,y)<=S₁(x,y)+S₂(x,y)+S₃(x,y), O(x,y) is assigned color C3 associated with the vertex of the tetrahedron T used in the step P4.3 to define the signal S₃(x,y);

[0104] if dither function G(x,y) is situated within partition P4, i.e. S₁(x,y)+S₂(x,y)+S₃(x,y)<G(x,y)<=S₁(x,y)+S₂(x,y)+S₃(x,y)+S₄(x,y), O(x,y) is assigned color C4 associated with the vertex of the tetrahedron T used in step P4.3 to define the signal S₄(x,y).

[0105] The procedure described in Step P4.2 applies the so-called “interior membership test” in order to check if an input color C(x′,y′) in three-dimensional color space ABC is inside a tetrahedron T defined by its four vertices. Referring to FIG. 10, the input color C is defined as the triplet (x,y,z) in the three-dimensional space ABC 1050. Within the present section, we assume that the 3 axes defining the three-dimensional space ABC are the x, y and z axes. An arbitrary tetrahedron T is defined by its four vertices V1=(x1,y1,z1), V2=(x2,y2,z2), V3=(x3,y3,z3) and V4=(x4,y4,z4). Every set of three vertices of the tetrahedron T forms a triange, i.e. a tetrahedron's face lying within a single plane:

[0106] vertices V1=(x1,y1,z1), V2=(x2,y2,z2) and V3=(x3,y3,z3) define the tetrahedron's face V1-V3-V2 and the corresponding plane_V1V3V2;

[0107] vertices V1=(x1,y1,z1), V2=(x2,y2,z2) and V4=(x4,y4,z4) define the tetrahedron's face V1-V2-V4 and the corresponding plane_V1V2V4;

[0108] vertices V1=(x1,y1,z1), V3=(x3,y3,z3) and V4=(x4,y4,z4) define the tetrahedron's face V1-V3-V4 and the corresponding plane_V3V1V4;

[0109] vertices V2=(x2,y2,z2), V3=(x3,y3,z3) and V4=(x4,y4,z4) define the tetrahedron's face V2-V3-V4 and the corresponding plane_V2V3V4.

It should be noted that the normals to the so-defined planes plane_V1V3V2, plane_V1V2V4, plane_V3V1V4, and plane_V2V3V4 are always directed to the inside of the considered tetrahedron T.

[0110] The “interior membership test” can be formulated as follows:

[0111]

	dist (pt_xyz, plane_V2V3V4) > 0 &&
	dist (pt_xyz, plane_V3V1V4) > 0 &&
	dist (pt_xyz, plane_V1V2V4) > 0 &&
	dist (pt_xyz, plane_V1V3V2) > 0

[0112] where && stands for the AND logical operator and where the Euclidean distance from the point pt_xyz given by its coordinates (x,y,z) to a plane defined by the tetrahedron's vertices {V_j} can be calculated as follows (standard three-dimensional distance computation procedure, based on the Hessian normal form, see Bronstein, Semendyayev, Handbook of Mathematics, Springer, 3rd revised edition, 1997, section 2.6.6.2, p 208):
dist(pt_—xyz, plane_—W1W2W3)=(a*x+b*y+c*z+d)/Sqrt[(a*a+b*b+c*c)]

[0113] where a, b, c and d are expressed by the coordinates of the vertices W1=(x1,y1,z1), W2=(x2,y2,z2) and W3=(x3,y3,z3):

[0114]

	a = −(y2*z1) + y3*z1 + y1*z2 − y3*z2 − y1*z3 + y2*z3;
	b = x2*z1 − x3*z1 − x1*z2 + x3*z2 + x1*z3 − x2*z3;
	c = −(x2*y1) + x3*y1 + x1*y2 − x3*y2 − x1*y3 + x2*y3;
	d = x3*y2*z1 − x2*y3*z1 − x3*y1*z2 + x1*y3*z2 + x2*y1*z3 −
	x1*y2*z3;

Note that the formal parameter plane_W1W2W3 in the procedure
dist (pt_xyz,plane_W1W2W3) stands for the real coordinate sets plane_V2V3V4, plane_V3V1V4, plane_V1V2V4 and plane_V1V3V2.
The same point to plane distance computation procedure as above can be used to compute the Euclidian distances in section “Color separation for non-standard inks”.

[0115] An alternative “Interior Membership Test” is described in section 3.1, page 56 in P. C. Hung, “Colorimetric calibration in electronic imaging devices using a look-up-table model and interpolations”, Journal of Electronic Imaging Vol. 2, No. 1, pp. 53–61, January 1993, section 3.1.

[0116] In order to produce artistic multi-color dithered color images, i.e. color images whose screen elements are made of artistic color screen shapes (letters, symbols, ornaments) and to produce images whose high level of detail make counterfeiting very difficult (security documents such as banknotes, checks, identity cards, passports, etc.), one must generate very large discrete dither functions, also called dither arrays, incorporating artistic screen shapes. Techniques for generating high-quality large dither arrays are described in an article written by the inventors (see V. Ostromoukhov, R. D. Hersch, Multi-Color and Artistic Dithering, Proceedings Siggraph '99, ACM Computer Graphics Proceedings, Annual Conference Series, 1999, 425–432). An example of a large dither array incorporating artistic screen shapes generated according to these techniques is given in FIG. 11 (dither levels G(x,y) between 0 and 1 are represented by increasing intensities, from black to white). With this dither array, we can reproduce a color image with a given set of primary colours. In the present example, we consider as input color image a color wedge with the following colors at its wedge vertices (RGB values are given as a triplet of discrete values between 0 and 255):

[0117] lower-left: Purple (Pantone 2612 CVU, RGB={128, 64, 127}),

[0118] upper left: unsaturated Green (close to Pantone 577 CVU, RGB={128, 191, 127}),

[0119] upper right: Yellow-Orange (Pantone 129 CVU, RGB={255, 191, 32}),

[0120] lower right: Warm Red (Pantone Warm Red CVU, RGB={255, 64, 32}).

[0121] The resulting multi-color dithered image using primary colors cyan (C), magenta (M), yellow (Y), red (R), green (G), blue (B), black (K) and white (W) is shown in FIG. 12. Only colors yellow (Y), magenta (M), red (R), green (G), black (K), and white (W) are needed to reproduce the color image wedge given above. The separations resulting from color separation and multi-color dithering are the magenta (M) layer (FIG. 13), the yellow (Y) layer (FIG. 14), the red (R) layer (FIG. 15), the green (G) layer (FIG. 16), the black (K) layer (FIG. 17) and the white (W) layer (FIG. 18).

[0122] Altenatively, one may use in addition to primary colors cyan (C), magenta (M), yellow (Y), red (R), green (G), blue (B), black (K) and white (W) an additional brown-gold (D) non-standard primary color close to Pantone 145 CVU (RGB=193, 130, 10). FIG. 19 shows the corresponding resulting multi-color dithered image. The separations comprise the brown-gold (D) non-standard color layer (FIG. 20), the magenta (M) layer (FIG. 21), the yellow (Y) layer (FIG. 22), the red layer (FIG. 23), the green (G) layer (FIG. 24) the black (K) layer (FIG. 25), and the white (W) layer (FIG. 26). Both examples show that each output pixel only belongs to one primary color layer and that primary colors are only printed side by side (no overlap of primary colors).

[0123] When prepared at a high resolution of R dots per inch (dpi), for example 1200, 2540 or 4000 dpi and printed at a resolution R_p>=R, these multi-color dithered images are extremely difficult to reproduce by potential counterfeiters. An attempt to photocopy such a multi-color dithered image with a photocopying device of resolution lower than R results in a heavy degradation or a loss of the artistic shape (micro-letters, symbols, ornaments) and in the loss of the original non-standard ink primary colors. Non-standard inks are primary colors selected specifically for preventing counterfeiting, i.e. colors which are significantly different from process colors cyan, magenta and yellow. They may be transparent or opaque. Non-standard inks comprise also metallic inks, variable color inks and fluorescent inks.

[0124] Printing a multi-color dithered image with non-standard opaque inks at a high registration accuracy, for example at a registration accuracy u_a>=1/(2R) inch, makes counterfeiting extremly difficult to achieve. This is due to the fact that printing at a registration accuracy u_a<1/R inch yields ink overlaps which induce strong color shifts.

[0125] Printing a multi-color dithered image with one or several non-standard fluorescent inks allows to reveal the artistic dot shape when the printed image is examined under UV light. The incorporation of one or several fluorescent inks into the multi-color dithered output image provides a good anticounterfeiting protection, since it is extremely difficult to counterfeit a color image made of a combination of non-fluorescent and fluorescent inks.

[0126] The combination of dither functions comprising artistic screen shapes and primary colors comprising non-standard inks offers therefore a variety of strong anti-counterfeiting protection means.

[0127] Some applications require that different inks be always printed side by side without overlapping. This is for example the case when printing with opaque inks as taught by inventor H. Kueppers in U.S. Pat. No. 4,812,899, issued Mar. 14, 1989. Different inks must also be printed side by side for some printing devices as taught by J. Gereadts and S. Lenczowski, “Océ's productive colour solution based on the Direct Imaging Technology”, Proceedings IS&T International Conf. On Direct Imaging Technology, Vol. NIP-13, 1997, pages 728–733. In these cases, no superimpositions of inks are allowed. The chosen set of inks plus the color of the substrate (generally paper white) forms the set of primary colors. By construction, multi-color dithering ensures that all primary colors are printed side by side. Theferore multi-color dithering offers a solution for printing on printers requiring side by side printing of primary colors.

[0128] An apparatus for color image reproduction by multi-color dithering is shown in FIG. 1.

[0129] An input color image storage unit 110 stores an input color image made of input color image pixels of color C(x′,y′).

[0130] A neighborhood calculation unit 120 is operable for computing a subset of primary colors {C_j} neighbors of a given input image color C and for computing for each neighbor color C_j of the set {C_j} a signal S_j(x,y) giving the relative normalized amount of C_j in respect to input image color C. The preferred embodiment of the neighborhood calculation unit is a tetrahedral calculation unit operable for computing and maintaining a subdivision of the color working space ABC into a set of tetrahedra, operable for applying the interior membership test and operable for computing from an input image color C and from primary colors C₁, C₂,C₃,C₄ forming the vertices of the tetraheder selected by the interior membership test the signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) giving the relative normalized amounts of primary colors C₁, C₂,C₃,C₄.

[0131] A dither function storage unit 160 stores the values of a two-dimensional dither function G(x,y).

[0132] A multi-color dithering unit 130 is operable for sweeping through all pixels of the output image (x,y), operable for finding the input color C(x′,y′) at the corresponding input image loation (x′,y′), operable for launching the neighborhood calculation unit to compute a subset of primary colors {C_j} neighbors of C(x′,y′) as well as their respective normalized amounts expressed as signals {S_j(x,y)}, and operable for determining the partition P_j(x,y) within which the dither function G(x,y) stored in the dither function storage unit 160 is situated, thereby selecting the primary color C_j(x,y) associated to P_j(x,y)as output color O(x,y). Upper and lower boundaries of partitions P₁, P₂, . . . PN are respectively defined by lower boundary 0 and upper boundary S₁(x,y), lower boundary S₁(x,y) and upper boundary S₁(x,y)+S₂(x,y), . . . , lower boundary S₁(x,y)+S₂(x,y)+ . . . +S_N-1(x,y) and upper boundary S₁(x,y)+S₂(X Y)+ . . . +S_N(x,y), where N is the number of colors of the computed subset of primary colors {C_j}, i.e. the number of primary colors contributing to render input color C(x′,y′).

[0133] In the case that the neighborhood calculation unit is embodied by a tetrahedral calculation unit, launching the neighborhood calculation unit to compute a subset of primary colors {C_j} neighbors of C(x′,y′) as well as their respective input signals {S_j(x,y)} consists in requiring the tetrahedral calculation unit to find the tetrahedron containing the input image color C and in computing signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) representing the relative normalized amounts of colors C₁, C₂, C₃ and C₄. Finding the tetrahedron containing the input image color C can be achieved by an interior membership test.

[0134] An output multi-color image storage unit 140 is operable for storing for each output image pixel (x,y) the selected primary color. The output multi-color image storage unit may comprise a pixmap storing the code of the selected primary color O(x,y) resulting from the operations of the multi-color dithering unit. Each member of the set {C_i} of n primary colors C₀ to C_n-1 can be coded as a binary number ranging between 0 and n−1. Alternatively, the output multi-color image storage unit may comprise a multilayer bitmap with one bit per primary color, storing for all non selected primary colors a value of 0 and a value of 1 for the selected primary color O(x,y). The output multi-color image storage unit is also operable for forwarding the resulting output multi-color image to an output device 150.

[0135] The output device is operable for converting the output multi-color image into a visible color image, for example a color image displayed by a color display or a color image printed by a color printer.

[0136] With modern technology, the storage and computing elements as well as the output device which are part of the apparatus can be implemented by a computing system (FIG. 1B). The input color image storage unit 110, the dither function storage unit 160 and the output multi-color image storage unit 140 are all part of the computing system's memory 170. The functions of the neighborhood (tetrahedral) calculation unit and the multi-color dithering unit are implemented by respectively a neighborhood (tetrahedral) calculation software procedure and a multi-color dithering software procedure stored in the computer system's memory and running on the computing system's central processing unit 180 which interacts with said memory for fetching program instructions and for reading and writing data.

[0137] The computing system comprises therefore a memory operable for storing an input color image made of input color image pixels C(x′y′), operable for storing the values of a two-dimensional dither function G(x,y), operable for storing the code of a neighborhood calculation software procedure, operable for storing a multi-color dithering software procedure and operable for storing an output multi-color dithered image O(x,y). The computing system also comprises a central processing unit interacting with said memory and running said neighborhood calculation and multi-color dithering software procedures, operable for computing for each output multi-color image pixel an output primary color O(x,y) selected from a set of primary colors, operable for storing the output primary color O(x,y) in memory and operable for forwarding the resulting output multi-color dithered image to an output device. The computing system also comprises an output device operable for converting the output multi-color image into a visible color image.

[0138] The preferred embodiment of the neighborhood calculation software procedure is a tetrahedral calculation software procedure. This procedure computes and maintains a subdivision of the color working space into a set of tetrahedra, applies an interior membership test and computes from an input image color C and from primary colors C₁, C₂,C₃,C₄ forming the vertices of the tetrahedron selected by the interior membership test the signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) giving the relative normalized amounts of primary colors C₁, C₂, C₃, C₄. The multi-color dithering software procedure sweeps through all pixels (x,y) of the output image, finds corresponding input image pixel colors C(x′,y′), calls the tetrahedral calculation software procedure to find the tetrahedron T containing the input image color C and to compute the signals S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y), determines the partition P_j(x,y) whithin which the two-dimensional dither function G(x,y) is situated and selects the primary color C_j(x,y) associated to P_j(x,y) as output color O(x,y).

[0139] The invented multi-color dithering method is extremely flexible: it accommodates the use of a freely chosen set of primary colors (standard and non-standard inks) and the use of a freely designed dither function having any desired size. One may create either small repetitive dither functions (respectively dither arrays) or large dither functions (dither arrays), up to dither functions (dither arrays) covering the whole surface of the output image. With large dither arrays, one can easily generate identifyable screen shapes, for example artistic screen shapes (FIGS. 11–26). Such artistic screen shapes provide additional document authentication means. The invented multi-color method allows to reproduce original picture edges with the highest possible fidelity, thanks to the fact that at each output pixel, (1) the unit interval is partitioned into as many partitions as contributing primary colors and (2) in order to select the output image pixel's primary color, the partition within which the dither function is situated is determined. FIG. 27 gives an example where the input image consists of uniform color C_a followed by a sharp transition to color C_b. Input image color C_a is to be reproduced by the following amounts of primary colors: 25% C1, 25% C2, 25% C3 and 25% C4. Input image color C_b is identical to primary color C3. One may verify that exactly starting from the point of transition between C_a and C_b, the dither function G(x) is located in partition P3 and that therefore color C3 is selected as output primary color.