Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
2000-06-14
2004-12-07
Lee, Thomas D. (Department: 2624)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003160, C358S534000, C358S535000
Reexamination Certificate
active
06829063
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to systems and methods for generating halftone images, and more particularly, to a method of designing sets of color matrices that tile together for use in creating color halftone images.
2. Description of the Prior Art
Digital halftoning refers to any process that creates the illusion of continuous-tone images by judicious arrangement of the binary picture elements, such as ink drops in the case of inkjet printers. Thus, halftoning is printing the simulation of a continuous-tone image, such as a shaded drawing or photograph with groups or cells of color or black dots. The dots are placed in such a way that they appear to the human eye to be a single color.
There are many halftoning techniques, each with its own method for laying down dots. Suppose a source color image is represented by the red, green and blue components. The simplest way of halftoning a color image using a dither matrix is to halftone each color plane independently using the same dither matrix. Each color defines a color concentration level. The term “color concentration level” for a color image is analogous to the term “gray level” for a black and white image.
FIG. 1
shows a representation of a printing system for generating a color print image. The image planes
110
a
,
110
b
,
110
c
are representative of the red, green and blue color components of an image. A single dither matrix
120
is used to halftone each image independently to create halftone images
130
a
,
130
b
,
130
c
. To create the halftone images
130
a
,
130
b
,
130
c
, pixel values in the image planes
110
a
,
110
b
,
110
c
are compared to the corresponding entries in the dither matrix
120
to determine which of the pixel values should be turned on or off. Halftoning is accomplished by a simple pointwise comparison of the source image
110
against a predetermined threshold array or mask. For every point or pixel in the source image, depending on which point value is larger (i.e., the image or the mask), either a 1 or 0, respectively, is placed at the corresponding location in the binary output image.
Let the red, green and blue components of the source image
110
at pixel (m,n) be r(m,n), g(m,n) and b(m,n), respectively. If the dither matrix threshold value at the same position is t(m,n), then one of the most commonly used halftone rules is:
if r(m,n)<t(m,n), print a cyan dot at (m,n);
if g(m,n)<t(m,n), print a magenta dot at (m,n);
if b(m,n)<t(m,n), print a yellow dot at (m,n).
Unfortunately, the basic halftoning technique described above creates an unacceptable level of artifacts in the resulting halftone image, leading to poor image quality. In response to this problem, U.S. Pat. No. 5,812,744 to Allebach et al. (hereinafter referred to as “the '744 patent”) describes a method of jointly designing a single set of color dither matrices. Referring to
FIG. 2
, which is taken from the '744 patent, the method described in the '744 patent generates a separate dither matrix
210
a
,
210
b
,
210
c
for each separate color image plane
220
a
,
220
b
,
220
c
, respectively. According to the '744 patent, using a set of dither matrices (i.e., a separate dither matrix for each color plane) reduces the halftone texture and increases the sharpness of the halftone image without increasing the complexity of the computations required.
While the methods described in the '744 patent clearly provided improvements to the existing technology, the set of dither matrices needed for the '744 scheme consumes more memory than a single dither matrix for all color planes as utilized by the prior art. Accordingly, it is desirable to develop a mechanism that reduces the memory requirements while maintaining or improving the print quality provided by the dither matrices provided by the '744 patent.
Moreover, halftoning in accordance with teachings of the '744 patent occasionally introduces undesirable periodic artifacts that stem from having a single set of dither matrices for use in the halftoning process. As the desktop printers increase in resolution (e.g. with 120+dpi), the conventional 128×128 screens can produce a distinctive periodicity in the printed images.
In addition, it would be desirable to be able to encode information into a halftone image to determine the source of the print. As can be appreciated, the ability to identify the source of any print would have useful application in authentication and fraud detection (e.g., counterfeit detection). Unfortunately, when there is a single set of dither matrices, as is provided by the '744, it is not possible to encode information into the resulting halftone image. Instead, multiple sets of dither matrices that can be utilized to halftone an image are required in order to encode information into the halftone image.
An example of using two sets of dither matrices (instead of one) to encode watermark information into dither hafltone images is described in “Watermarking of Dither Halftoned Images,” written by Z. Baharav and D. Shaked, and published in the Proceedings of SPIE, Vol. 3657 as part of the IS&T/SPIE Conference on Security and Watermarking of Multimedia Contents, San Jose, Calif., January 1999. However, this example is limited to black and white images.
As can be appreciated, such a security system is dependent on a mechanism to design or generate multiple sets of dither matrices that can be utilized to encode information and yet at the same time tile together seamlessly for good print quality. One approach to designing multiple sets of dither matrices that can tile together seamlessly is described in “Aperiodic Micro Screen Design using DBS and Training,” written by D. Kacker and J. Allebach, and published in the Proceedings of SPIE, Vol. 3300 as part of the IS&T/SPIE Conference on Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III, San Jose, Calif., January 1998. Unfortunately, this screen design method is only applicable to monochrome images. Accordingly, it is desirable for there to be a mechanism for designing color dither matrices that tile together seamlessly so that a watermark system, as described above, can be implemented for color images.
Unfortunately, there is no current approach to design multiple sets of color dither matrices. Furthermore, as noted previously, any approach must consider the memory requirements of these multiple sets of dither matrices. It is preferable that the storage requirements of these sets of dither matrices be the same or less than the storage needed by the single set of dither matrices.
Accordingly, there remains a need for a method of generating multiple sets of color dither matrices that occupy less storage space, increases halftone image quality, and that enable the encoding of information in the halftone image.
SUMMARY OF THE DISCLOSURE
A method for jointly designing at least two sets of dither matrices is described. First, a mosaic color tile is generated for a first concentration level according to a design tile map. The mosaic color tile includes at least a first color tile and a second color tile where each color tile has a color tile concentration level (CTCL) and a color tile number (CTN). Second, a color fluctuation metric is computed for the mosaic color tile. Next, the pixels in the first color tile are modified by an operation (e.g., a swap operation) while maintaining the first concentration level. Then, a color fluctuation metric is re-calculated on the mosaic color tile with all first color tiles being replaced with the modified first color tile (i.e., everywhere the first color tile appears in the mosaic color tile as specified by the design tile map). The steps of modifying the color tiles and re-calculating the color fluctuation metric for the modified mosaic tile is performed until the metric is below a predetermined metric level or until further changes yield only a small decrease in the metric (i.e., the decrease in the metric is less than a p
Allebach Jan P.
Lin Qian
Hewlett--Packard Development Company, L.P.
Lee Thomas D.
LandOfFree
Method for designing sets of color matrices that tile together does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for designing sets of color matrices that tile together, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for designing sets of color matrices that tile together will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323039