Incremental printing of symbolic information – Ink jet – Controller
Reexamination Certificate
2001-03-29
2002-11-05
Nguyen, Trinh (Department: 2861)
Incremental printing of symbolic information
Ink jet
Controller
C347S043000
Reexamination Certificate
active
06474766
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of halftone image production. In particular, the present invention relates to an apparatus and a method for creating a dither matrix in a less compute-intensive manner for use in a color printing environment.
2. Description of Related Art
The use of halftone patterns is required whenever printing graphics with traditional inks upon paper. Halftone techniques arose because the continuously varying gradations of gray scale and colors cannot be directly printed by offset, dot-matrix, ink-jet, and other printer technologies that utilize the deposition of constant-shaded dots of black or colored ink. A common early halftone technique utilized a uniform screen, as shown in FIG.
1
. The segment of uniform screen
10
includes many cells, of which cell
12
is exemplary. Changing the density of gray scale using the uniform screen
10
may be performed by enlarging or shrinking the size of the ink dot corresponding to each cell. A light gray may be shown by making the ink dots relatively small in size. Conversely, a darker gray may be shown by making the ink dots relatively larger. The ink dot placed at a cell may be of any shape, with the square dots shown in
FIG. 1
merely serving as examples.
The uniform screen
10
may be extended to cover an entire image. This is a simple process of uniformly extending the existing screen pattern, and requires no more than simple geometric calculations. However, the uniform screen
10
of
FIG. 1
has certain visual drawbacks. The human visual system (HVS) is very sensitive at recognizing unintentional patterns, called artifacts, caused by the use of a halftone pattern. The HVS is most sensitive to slowly-varying in space (“low frequency”) artifacts and much less sensitive to rapidly-varying in space (“high frequency”) artifacts. The literature on the subject often characterizes the HVS as possessing a “low-pass filter”. Additionally, the HVS is much more sensitive to patterns falling on a horizontal or vertical line. In the
FIG. 1
example, the cells line up along line
14
. Line
14
forms an angle of &thgr; degrees from a horizontal line
16
. It is well-known in the art that the HVS is least sensitive to artifacts when &thgr; is around 45 degrees.
A better approach is illustrated in the dither pattern of FIG.
2
. The dither pattern
20
includes a large number of cells, of which a typical one is cell
22
. There are more blank spaces between the dots of dither pattern
20
so this would correspond to a light gray. More dots could be added for a darker shade of gray. The cells of dither pattern
20
have been arranged so that repetitive patterns, recognizable by the HVS, are minimized. It would appear on first glance that such a useful dither pattern
20
is “random”, but a truly random pattern would include clumps of cells and also empty spaces. Hence the dither pattern
20
would more correctly be described as evenly but not regularly patterned.
The dither pattern
20
of
FIG. 2
corresponds to a particular percentage of cells being selected for ink-dot placement. In order to allow for differing percentages of cells being selected, a related dither matrix to dither pattern
20
may be created. A dither matrix is a dither pattern with an ordering scheme for including cells depending upon the ratio of ink dots filled cells to total cells required. For clarity, a dither matrix
30
is shown in
FIG. 3
a
with a limited number of cells. In practice, a much larger number of cells would be defined and used in a dither matrix. To create dither matrix
30
from dither pattern
20
, each cell such as exemplary cell
22
may have associated with it a threshold value, selected from a sequence from 1 through A, where A is the total number of cells in a dither pattern. For example, the threshold value stored in ordered cell
32
is the number 13. This means that if the ratio of dark cells to total cells is 13/A, then a proper pattern is for the printer to place ink dots at all ordered cells with a threshold value of 13 or less.
In order to extend the dither matrix
30
to cover an entire image, dither matrix
30
is replicated and applied as tiles. In
FIG. 3
b
a typical tiling scheme is illustrated. A replicated copy matrix
40
of dither matrix
30
is placed at locations in a grid
42
covering the size of the image required.
A useful dither pattern such as dither pattern
20
is not easily created. One method of creating such a useful dither pattern, well-known in the art, is to use the technique known as error diffusion. In this method, first a two dimensional transfer function V
ij
that models the perceived responsiveness to patterns of the HVS is created. V
ij
is called a modulation transfer function (MTF). Then, a two dimensional function p
ij
that describes the location of all the selected cells in a given dither pattern is defined. Finally, a cost function that approximates the amount of artifacts seen by a human, depending upon V
ij
and a given p
ij
, is created. In one embodiment, the cost function Cost(p
ij
) is given by Equation 1 below.
Cost
(
p
ij
)
=
∑
i
=
1
N
∑
j
=
1
N
V
2
ijPijP
*
ij
Equation
1
where Pij is the discrete Fourier transform (DFT) of the given pattern p
ij
.
One method of selecting the least-objectionable pattern p
ij
for use in a dither pattern is to evaluate the cost function for all such patterns p
ij
, and then select one of the p
ij
corresponding to the minimum value of the cost function. This is not practicable. The number of such possible combinations p
ij
representing M cells selected in a dither pattern of N by N cells is (N
2
!)/M!(N
2
−M)!. This is an enormous number even for smaller dither patterns such as 32 by 32, and the number increases substantially for desired dither patterns of 256 by 256 or even 1024 by 1024 cells. Evaluating Equation 1 for such large numbers of candidate patterns is computationally intensive, and for all but the smallest sizes of dither patterns is impractical with reasonable amounts of computer resources.
An additional issue in printing colors with dither matrices, such as dither matrix
30
, is that inks are transparent to varying degrees. If the same dither matrix were used for differing primary colors, such as cyan, magenta, and yellow, this would result in placing the different color's ink dots roughly on top of one another. Light would then have to pass through multiple layers of ink to reflect off the base paper sheet. Having light pass through such multiple layers may produce unwanted multiple internal reflections and other similar optical effects that will yield impure colors when viewed.
SUMMARY
A system and method for color printing is disclosed. In one embodiment, the method for color printing begins by printing a first primary color, usually cyan, with the aid of a previously generated dither matrix. The method continues by deriving a new dither matrix from the previously generated dither matrix by moving each position in the previously generated dither matrix a short random distance, thereby forming a corresponding position in the new dither matrix for printing another primary color, usually magenta. In an alternate embodiment, a new dither matrix is derived from the previously generated dither matrix by inverting the positions in the previously generated dither matrix to the positions of the new dither matrix. In other embodiments, additional dither matrices may be derived by a process of shifting the previously generated dither matrix horizontally or vertically and wrapping around the edges of the original dither matrix. Additional new dither matrices may be created in a similar manner for use in printing other primary colors or black.
REFERENCES:
patent: 5111310 (1992-05-01), Parker et al.
patent: 5323247 (1994-06-01), Parker et al.
patent: 5341228 (1994-08-01), Parker et al.
patent: 5477305 (1995-12-01), Parker et al.
patent: 5543941 (1996-08-01), Parker et al.
patent: 5708518 (1998-01-0
Blakely , Sokoloff, Taylor & Zafman LLP
Nguyen Trinh
Sony Corporation
LandOfFree
System and method for color dither matrix creation using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for color dither matrix creation using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for color dither matrix creation using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2978847