Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-03-16
2003-02-04
Coles, Edward (Department: 2622)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S003220, C382S270000
Reexamination Certificate
active
06515770
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to digital halftoning techniques for printing a picture on a two-dimensional medium in printers. This invention is a method and apparatus to construct calibrated dither masks adaptable to most printers in such a way that the threshold values can be adapted to the printer so that the printer can print the originally intended number of distinct tone (e.g., grey or color) levels. This adaptation can be done computationally so that the time it takes is not prohibitive. The present invention builds on and improves upon previous techniques because the resulting calibrated dither mask is such that there is no need for a tone reproduction curve in the halftoning process.
2. Background Description
Most printers can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance. In fact, the rest of the discussion will be specialized to the case of grey scale images and their rendering by black and white printers to facilitate the presentation.
We will be concerned with bilevel, fixed pixel size printers (for instance laser printers). Such printers are usually considered to have two fundamental characteristics: the pixel density, say d dpi (dots per inch), which can be interpreted as telling us that the ideal pixel size is 1/d inches by 1/d inches (where d typically varies from about 300 to about 3000) and the mechanical dot gain which is a number describing how much bigger the printed dot is compared to a perfect 1/d by 1/d square.
Consider now some grey scale image to be printed with a digital printer. We assume that this image is of size h by v, where h and v are expressed in inches to be consistent with the unit used in the dot resolution description. It is then convenient to interpret this image as a matrix I of size H=h×d by V=v×d in the following way:
One thinks of the image as covered by little squares of size 1/d by 1/d called pixels.
Then each pixel p, can be designated by its horizontal ordering number i (say from left to right) and its vertical ordering number j (say from top to bottom); thus, the location of p is specified by the pair (i,j).
To the pixel (i,j) one assigns the value val between 0 and 1, where 0 corresponds to white, 1 corresponds to black, and more generally, val corresponds to the grey level of this particular pixel.
Given a matrix such as I, a digital halftoning algorithm will associate to it a H by V printing decision matrix M whose entries M(i,j) are either 0 or 1, where 0 now means that no dot will be printed by the digital printer at pixel (i,j), while a 1 means that a dot is to be printed.
One of most frequently used methods of preparing such a matrix M, consists in using some dither mask D. Such a mask, defined either in hardware or in software, can be thought of as a matrix of numbers. We assume that D is a W by L matrix with entries between 0 and 1. One uses D to generate M by setting
M
(
ij
)=1 if
I
(
i,j
)>
D
(
i
mod
W,j
mod
L
),
M
(
i,j
)=0 if
I
(
i,j
)<
D
(
i
mod
W,j
mod
L
).
In these formulas, the mod notation should be understood as follows: If a and b are two integers, a mod b is the remainder of the division of a by b. The formulas for M justify the name of threshold levels for the entries of D. We denote by T the set of threshold values of D. The number of distinct threshold values determines the number of distinct grey levels which could be printed with D on a printer with perfect 1/d by 1/d pixels. In fact, if the image I is some uniform grey level g
1
, only those pixels with D(i mod W,j mod L)<g get printed. As a consequence, except in the case when D is designed for a specific printer, since the dot gain is unknown, one chooses the threshold values to be evenly distributed between 0 and 1. The book “
Digital Halftoning
” by R. Ulichney (MIT Press Cambridge, Mass. 1987), which is a general reference on digital halftoning contains several methods of generating dither masks. In the patent application “
Clustered Aperiodic Mask
” by G. R. Thompson et al., Ser. No. 08/943,881, filed Oct. 3, 1997, a method is disclosed to generate a dither mask which can have a large number of grey levels.
To calibrate the printer for printer characteristics such as dot gain, prior art uses a tone reproduction curve (TRC), a function which describes the relationship between the intended grey and the actual grey printed by the printer. This is usually implemented as a look-up table. For instance, in U.S. Pat. No. 5,309,177 issued to Shoji et al., a TRC is used as a look-up table to correct the image data to be printed. In U.S. Pat. No. 5,347,369 issued to Harrington, a method is disclosed to obtain the TRC without special equipment.
Problems to Be Solved
If the dither mask D is used on a printer P, because of the way P prints dots, the printed version of each individual grey level will be different from what is intended. In prior art, one usually corrects this problem by using a (printer dependent) tone reproduction curve T which describes the relationship between the grey that you instruct the printer to print and the grey the printer actually prints. For example, instructing the printer to print a uniform patch of grey level g could result in a patch with grey level g′. The relation between various values of g and corresponding values g′ is embodied in a tone reproduction curve, T(g), which specifies the output grey level for a given input grey level. In other words, T(g)=g′. The tone reproduction curve is then used either to transform the grey level at each (i,j) before it is compared to the threshold value D(i,j), or to transform the entries of D. This can result in the number of distinct grey levels which can be printed being less than the number of distinct values in the original matrix D. Specifically, this happens when D consists entirely of a sequence of k consecutive integers from 1 through k, and T is a non-linear mapping onto 1 through k. Then some input integers are mapped onto the same output integer and the number of distinct output integers is less than the number of input integers, k.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method and apparatus to construct calibrated dither masks adaptable to most printers in such a way that the threshold values can be adapted to printer P so that printer P can print the originally intended number of distinct tone levels. This adaptation can be done computationally so that the time it takes is not prohibitive. Furthermore, the resulting calibrated dither mask is such that there is no need for a tone reproduction curve in the halftoning process.
Several methods are available which allows one to compute an approximation N
1
(M, P) of the image a printer P will print given the matrix M. If a dither mask is to be prepared to print d distinct grey levels with essentially any printer P, we will prepare a master mask D
0
with some number d
0
of threshold levels, where d
0
is significantly larger than d. For each of these threshold levels, t, one can easily compute the matrix M(t) corresponding to a constant grey level t. In other words, we print a patch of constant input grey level t of the size of M using the dither matrix D
0
. As mentioned above, one deduces easily from there the matrix N
1
(M(t), P) if the specificity of P is known in a convenient way. We then select the d−1 values of t which give the closest approximations to the grey levels 1/d, 2/d, . . . , (d−1)/d, and call t
1
, t
2
, . . . , t
d−1
the corresponding values of t in increasing order.
In other words, we print patches for all d
0
distinct grey values in D
0
and mea
Rao Ravishankar
Thompson Gerhard R.
Tresser Charles P.
Wu Chai W.
Coles Edward
Kaufman Stephen C.
Mitchell Monica
LandOfFree
Dither mask generation with calibration-independent number... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dither mask generation with calibration-independent number..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dither mask generation with calibration-independent number... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173417