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

• US 7,054,038 B1
• Filed: 01/04/2000
• Issued: 05/30/2006
• Est. Priority Date: 01/04/2000
• Status: Expired due to Fees

• Current Assignee: Ecole Polytechnique Federal de Lausanne
• Original Assignee: Ecole polytechnique fãdãrale de lausanne epfl (Schweizerische Eidgenossenschaft)
• Inventors: Hersch, Roger D., Ostromoukhov, Victor
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US09/477,544
• Time in Patent Office: 2,338 Days
• Field of Search: 358 313- 318, 358/1.9, 358/500, 358/521, 358515-518, 358 319- 32
• US Class Current: 358/3.13
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening
• CPC Class Codes: H04N 1/54 Conversion of colour picture signals to a plurality of signals some of which represent particular mixed colours, e.g. for textile printing

Abstract

The invention provides a method and apparatus for the reproduction of color images by multi-color dithering. Multi-color dithering is an extension of bi-level dithering for halftoning an input image using as primary colors an arbitrary number of inks. The inks may comprise standard inks or non-standard inks such as non-process color inks, opaque inks, metallic inks, variable color inks and fluorescent inks. Multi-color dithering provides a solution for creating artistic multi-color dithered images, whose screen elements are 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 also offers a solution for printers requiring that all inks are printed side by side, without overlaps.

Claims

1. A multi-color dithering method for the reproduction of color input images, the method being characterized by the use of a two-dimensional dither function, the use of an arbitrary number of primary colors and the use of partitions representing relative amounts of primary colors, the method comprising the steps of:

(a) defining a two dimensional dither function G(x,y);

(b) choosing a set of primary colors {C_i} located within a three-dimensional color working space ABC;

(c) 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;

(d) computing the primary color of each output image pixel O(x,y) by a set of substeps comprising;

(i) locating in the input color image an input color location (x′

,y′

) associated to the output image pixel O(x,y) and computing its corresponding color C(x′

,y′

);

(ii) finding N neighbor primary colors {C_j} of C in the ABC color space by using the neighbor finding procedure;

(iii) computing the amount S_j(x,y) of every neighbor primary color C1;

(iv) determining the output primary color O(x,y) at output pixel (x,y) by locating at each position (x,y) a partition P_j(x,y) within which the dither function G(x,y) is situated, where 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), and by assigning to the output primary color O(x,y) the neighbor primary color C_j associated to partition P_j(x,y); and

(e) outputting the multi-color dithered output image on an output device.

2. The method of claim 1, where the dither function is a two-dimensional discrete dither function characterized by two basic translation vectors.

3. The method of claim 2, where the two-dimensional discrete dither function is obtained by discretizing a continuous dither function.

4. The method of claim 2, where the discrete values of the two-dimensional discrete dither function are obtained by incrementing ordinal numbers along a space-filling curve.

5. The method of claim 1, where outputting the multi-color dithered output image consists in printing the multi-color dithered output image.

6. The method of claim 1, where outputting the multi-color dithered output image consists in displaying the multi-color dithered output image on a color display.

7. The method of claim 1, where the chosen set of primary colors {C_i} comprises non-standard inks selected from the set comprising transparent non process color inks, opaque inks, metallic inks, variable color inks and fluorescent inks.

8. The method of claim 7, where the non-standard inks are opaque inks, where the original multi-colored dithered image is prepared at a resolution of R dots/inch and printed at a resolution R_p>

=R with a registration accuracy u_a>

=1/(2R) inch, thereby offering an effective anti-counterfeiting protection, since counterfeiting with printing devices of registration accuracy u_a<

1/R inch yields ink overlaps resulting in strong color shifts.

9. The method of claim 1, where the dither function is a large dither array incorporating artistic screen shapes and where the chosen set of primary colors {C_i} comprises at least one fluorescent ink which under illumination with UV light reveals the artistic screen shapes present in the multi-color dithered output image.

10. The method of claim 1, where the dither function is a large dither array incorporating artistic screen shapes and where preparing the image at a high resolution of R dots/inch and printing it at a resolution R_p>

=R makes it impossible to reproduce the multi-colored dithered image on a copier with a resolution lower than R without heavy degradation of the artistic screen shapes.

11. The method of claim 1, where the chosen set of primary colors {C_i} is identical to the chosen set of inks plus the color of the substrate thereby fulfulling the requirement of printers requiring that inks are always printed side by side.

12. The methods of claim 1, where the neighbor finding procedure uses a subdivision of the color working space ABC into a set of tetrahedra {T_k} having as vertices the chosen set of selected primary colors {C_i}, where the neighbor finding procedure comprises the step of applying to the set of tetrahedra an interior membership test, thereby obtaining tetrahedron T containing input color C(x′

,y′

) and where for every neighbor primary color C_j the computation of their relative amounts S_j(x, y) comprises the step of finding ratios between the Euclidian distances from the input color C(x′

,y′

) to faces of the tetrahedron T and the corresponding Euclidean distances from the same tetrahedron'"'"'s faces to their opposite vertices.

13. An apparatus for color image reproduction by multi-color dithering comprising:

(a) an input color image storage unit operable for storing an input color image made of input color image pixels of color C(x′

,y′

);

(b) a neighborhood calculation unit operable for computing a subset of primary colors {C_j} neighbors of the given input image color C and operable for computing for each neighbor color C_j of the set {C_j} a signal S_j(x,y) giving the relative amount of C_j in respect to input image color C;

(c) a dither function storage unit storing the values of a two-dimensional dither function G(x,y);

(d) a multi-color dithering unit operable for sweeping through all pixels of the output image (x,y), operable for finding the input color C(x′

,y′

) of corresponding input image pixels, 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 signals {S_j(x,y)}, operable for determining a 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);

(e) an output multi-color image storage unit operable for storing the selected primary colors O(x,y) generated by the multi-color dithering unit and operable for forwarding the primary colors making up the output multi-color dithered image to an output device;

(f) an output device operable for converting the output multi-color dithered image into a visible color image.

14. The apparatus of claim 13, where the neighborhood calculation unit is a tetrahedral calculation unit operable for computing and maintaining a subdivision of the color working space 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 tetrahedron selected by the interior membership test the signals S₁(x,y), S₂(x,y), S₃(x,y), S₄(x,y) giving the relative amounts of primary colors C₁, C₂, C₃, C₄.

15. A computing system for multi-color dithering comprising

(a) 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);

(b) 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 image pixel (x,y) 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;

(c) an output device operable for converting the output multi-color image into a visible color image,

where the multi-color dithering software procedure sweeps through output image pixels, finds for each output image pixel (x,y) a corresponding input image pixel color C(x′

,y′

), launches the neighborhood calculation software procedure which computes a subset of primary colors {C_j} neighbors of C(x′

,y′

) as well as their respective amounts {S_j(x,y)}, determines a partition P_j(x,y) within which the two-dimensional dither function G(x,y) is situated and selects a primary color C_j(x,y) associated to P_j(x,y) as output primary color O(x,y).

16. The computing system of claim 15, where the neighborhood calculation software procedure is a tetrahedral calculation software procedure which 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 relative amounts S₁(x,y), S₂(x,y), S₃(x,y) and S₄(x,y) of primary colors C₁, C₂, C₃, C₄.