 |
Description  |
|
|
CROSS REFERENCE
Cross reference is made to the following co-pending applications: U.S. Ser.
No. 07/955,075, now U.S. Pat. No. 5,305,119 filed Oct. 1, 1992, entitled
"Color Printer Calibration Architecture", by R. J. Rolleston et al.
(assigned to the same assignee as the present application); U.S. Ser. No.
08/131,168, filed Oct. 4, 1993, entitled "Reduced Storage of Pre-Computed
Difference Tables Used In Color Space Conversion", by R. J. Rolleston
(assigned to the same assignee as the present application); U.S. Ser. No.
08/144,987, now U.S. Pat. No. 5,416,613 filed Oct. 29, 1993, entitled
"Color Printer Calibration Test Pattern" by R. J. Rolleston et al.
(assigned to the same assignee as the present application); U.S. Ser. No.
08/179,284, filed Jan. 10, 1994, entitled "Color Printer Calibration
Architecture", by R. J. Rolleston et a. (assigned to the same assignee as
the present application); U.S. Ser. No. 08/223,194, now U.S. Pat. No.
5,471,324 filed Apr. 5, 1994, entitled "Color Printer Calibration with
Improved Color Mapping Linearity", by R. J. Rolleston (assigned to the
same assignee as the present application); and U.S. Ser. No. 08/254,629,
now U.S. Pat. No. 5,483,360 filed Jun. 6, 1994, entitled "Color Printer
Calibration with Blended Lookup Tables", by R. J. Rolleston et al.
(assigned to the same assignee as the present application).
FIELD OF THE INVENTION
The present invention is directed towards compiling look up tables
representative of printer characteristics, to enable the conversion of
colors defined in a first color space to colors defined in the printer
color space, and more particularly to a method of making such table more
linear.
INCORPORATION BY REFERENCE
The following patents are specifically incorporated by reference: U.S. Pat.
No. 4,500,919 to Schreiber for its teachings of a color conversion system
converting information from RGB to CMYK; U.S. Pat. No. 4,275,413 to
Sakamoto for its teachings of tetrahedral interpolation between first and
second color spaces; and U.S. Pat. No. 2,790,844 to Neugebauer disclosing
the desirability of defining an image in a first standard color space
prior to conversion of the image coordinates to a second printer based
coordinate system, and U.S. Pat. No. 5,296,923 to Hung. The following
articles are also hereby incorporated by reference: Po-Chieh Hung,
"Tetrahedral Division Technique Applied to Colorimetric Calibration for
Imaging Media", Annual Meeting IS&T, NJ, May, 1992, pp. 419-422; Po-Chieh
Hung, "Colorimetric Calibration for Scanners and Media", SPIE, Vol. 1448,
Camera and Input Scanner System, (1991); Sigfredo I. Nin, et al.,
"Printing CIELAB Images on a CMYK Printer Using Tri-Linear Interpolation",
SPIE Proceedings, Vol. 1670, 1992, pp. 316-324; William J. Gordon et al.,
"Shepard's Method of `Metric Interpolation` to Bivariate and Multivariate
Interpolation", Mathematics of Computation, Vol. 32, No. 141, January
1978, pp. 253-264; P. Lancaster et al., "Surfaces Generated by Moving
Least Squares Methods", Mathematics of Computation, Vol. 32, No. 155, July
1981, pp.141-158; Pekka Laihanen, "Colour Reproduction Theory Based on the
Principles of Colour Science", Advances in Printing Science and
Technology, W. H. Banks ed., Pentech Press, London, 1988, pp. 1-36; Pekka
Laihanen, "Optimization of Digital Color Reproduction on the Basis of
Visual Assessment of Reproduced Images", Proceedings of the SID, Vol 30.
No. 3, 1989, pp. 183-190; and Donald Shepard, "A two-dimensional
interpolation function for irregularly spaced data," Proceedings-1968 ACM
National Conference, pp. 517-524.
BACKGROUND OF THE INVENTION
The generation of color documents can be thought of as a two step process:
first, the generation of the image by means of scanning an original
document with a color image input terminal or scanner or, alternatively,
creating a color image on a work station operated in accordance with a
color image creation program; and secondly, printing of that image with a
color printer in accordance with the colors defined by the scanner or
computer generated image. Scanner output is commonly transformed to a
color space of tristimulus values, i.e., RGB (red-green-blue). Commonly,
these values are a linear transformation of the standard XYZ coordinates
of CIE color space, or a corrected transform of those values. In the case
of computer generated images, colors defined by the user at the user
interface of a workstation can be defined initially in color space of
tristimulus values. These colors are defined independently of any
particular device, and accordingly reference is made to the information as
being "device independent".
Printers often have an output which can be defined as existing in a color
space called CMYK (cyan-magenta-yellow-key or black) which is uniquely
defined for the printer by its capabilities and colorants. Printers
operate by the addition of multiple layers of ink or colorant in layers to
a page. The response of the printer tends to be relatively non-linear.
These colors are defined for a particular device, and accordingly
reference is made to the information as being "device dependent". Thus,
while a printer receives information in a device independent color space,
it must convert that information to print in a device dependent color
space, which reflects the gamut or possible range of colors of the
printer.
The desirability of operating in a device independent color space with
subsequent conversion to a device dependent color space is well known, as
shown by U.S. Pat. No. 4,500,919 to Schreiber and U.S. Pat. No. 2,790,844
to Neugebauer, and U.S. Pat. No. 4,275,413 to Sakamoto. There are many
methods of conversion between color spaces, all of which begin with the
measurement of printer response to certain input values. Commonly, a
printer is driven with a set of input values reflecting color samples
throughout the printer gamut, the color samples are printed in normal
operation of the printer. As previously noted, most printers have
non-linear response characteristics.
In U.S. Pat. No. 4,275,413 to Sakamoto, the information derived is placed
into lookup tables, stored in a memory, perhaps ROM memory or RAM memory
where the lookup table relates input color space to output color space.
The lookup table is commonly a three dimensional table since color is
defined with three variables. In RGB space, at a scanner or computer,
space can be defined as three dimensional with black at the origin of a
three dimensional coordinate system 0, 0, 0, and white at the maximum of a
three dimensional coordinate system which an 8-bit system, would be
located at 255, 255, 255. Each of the three axes radiating from the origin
point therefore respectively define red, green, and blue. A similar
construct can be made for the printer, with axes representing cyan,
magenta, and yellow. In the 8-bit system suggested, there will be,
however, over 16 million possible colors (2563). There are clearly too
many values for a 1:1 mapping of RGB to CMY. Accordingly, as proposed in
U.S. Pat. No. 4,275,413 to Sakamoto, only a relatively small number of
samples are used to do the mapping from RGB to CMY, perhaps on the order
of 1,000. Therefore, the lookup tables consist of a set of values which
could be said to be the intersections for corners of a set of cubes
mounted on top of one another. Colors falling within each cubic volume can
be interpolated from the measured values, through many methods including
tri-linear interpolation, tetrahedral interpolation, polynomial
interpolation, linear interpolation, and any other interpolation method
depending on the desired speed and accuracy of the result.
It would be very easy to index device dependent color values or
specifications to device independent color specifications, but that is not
the requirement. Instead, device independent specifications must be mapped
to device dependent specifications. Several problems arise. Of course, the
primary problem is that the printer response is not a linear response. A
second problem is that the color space, and therefore the coordinates
defined in the color space must be maintained as a uniform grid, for
maximum efficiency of some interpolation methods, particularly for
tetrahedral interpolation, a very desirable method of interpolation.
Accordingly, a three dimensional look up table (LUT) may be constructed
which puts device independent input values into a predictable grid
pattern. One method of accomplishing this requirement is by an
interpolation process which derives a value at a desired location as a
function of all (or a significant set) of measured color values. One way
of doing this is to use Shepard's Method (see, for example "Shepard's
Method of `Metric Interpolation` to Bivariate and Multivariate
Interpolation" by W. Gordon and J. Wixom, Mathematics of Computation, Vol.
32, No. 141, January 1978, pp. 253-264). Shepard's Method suggests that a
vector can be thought of as defining the difference between an asked-for
color which was directed to a printer in the printed color. Then, for any
other point in color space which is desired, that point can be thought of
as a vector quantity, derived by averaging over the space all the vectors,
each vector weighted by a function which decreases its effect on the
vector as that vector is further and further away from the point coloring
question. In one useful formula, each vector is weighted by a function of
.sup.1 /.sub.d.spsb.4.
Alternatively the method of Po-Chieh Hung, "Colorimetric Calibration for
Scanners and Media", SPIE, Vol. 1448, Camera and input Scanner System,
(1991), describes a method of inverse tetrahedral interpolation, to the
same effect as the described Shepard's Method (see also U.S. Pat. No.
5,296,923 to Hung, previously incorporated by reference for its
teachings). A requirement of this method is that the color space be
segmented into a set of non-overlapping, space-filling tetrahedrons. This
segmentation requirement is fulfilled by using only data from a full
rectangular array of points, where it is easy to define the mesh of points
which define the tetrahedrons.
A problem encountered in the calibration process is that of having most
colors being reproduced successfully, but having a few regions of color
space that are not well behaved in terms of the empirically derived
calibration model. The addition of a few more calibration points in these
poorly behaved areas, would appear to be a solution to the problem.
However, because inverse tetrahedral interpolation requires a full
rectangular grid of data points, to obtain the "few more calibration
points" in the poorly behaved areas really requires the addition of
hundreds of more calibration points. FIG. 1 illustrates the problem in two
dimensions for simplicity, where a, b, c and d represent colors which
reproduce successfully in a color space transformation, while point e does
not. Adding points P.sub.i, as in FIG. 1A presumably would resolve the
reproduction problem, but that arrangement does not provide a color space
which is readily segmentable into a set of non-overlapping, space-filling
tetrahedrons. This segmentation requirement is fulfilled by using only
data from a full rectangular array of points.
The references cited herein are incorporated by reference for their
teachings.
SUMMARY OF THE INVENTION
In accordance with the invention there is provided a calibration method
providing additional data points to support inverse tetrahedral
interpolation for the derivation of color space transformation look up
tables, without substantially increasing the amount of empirically
measured data.
In accordance with one aspect of the invention, the color printer
calibration method for improving printer accuracy in regions of local
non-linearity includes the steps of: a) starting with filled rectangular
array of color mappings A.sub.0 mapping printer signals to device
independent color space signals; b) empirically deriving a set of color
mappings P.sub.i in an area of interest; c) using a set of planes defined
by the color mappings of A.sub.0, and the set of empirically derived color
mappings P.sub.i, identifying a new set of planes such that each point
defined by A.sub.0 and each point defined by P.sub.i is located at the
intersection of three planes, the intersection points of this expanded
number of planes defining a set of points P.sub.i(expanded) that define a
full rectangular array A.sub.1 of mappings including mappings A.sub.0,
mappings P.sub.i and mappings P.sub.i(expanded) ; d) storing said mapping
A.sub.1 for use in the creation of a new color space transformation LUT
for use with said printer.
In accordance with another aspect of the invention, the method includes,
before step d), the step of substituting into mapping A.sub.1, any
empirically derived mappings from A.sub.0 and any empirically derived
mappings from P.sub.i.
In accordance with yet another aspect of the invention, the method
includes, before step d), the step of replacing mappings in A.sub.1 that
are defined by points from mapping A.sub.0 and near a value of mapping
P.sub.i, with new mapping values which take into account the nearby
P.sub.i mappings.
In using the described method, the goal of obtaining a filled rectangular
or three dimensional mapping is obtained, while additionally improving
calibration results through the use of the new empirical data to describe
color mapping adjacent to the new empirical points.
These and other aspects of the invention will become apparent from the
following descriptions to illustrate a preferred embodiment of the
invention read in conjunction with the accompanying drawings in which:
FIGS. 1A and 1B show the problem addressed by the present invention in a
two dimensional example;
FIGS. 2 and 3 together illustrate an overall system block diagram showing a
color printing system in which the present invention might find use;
FIG. 4 shows the principle of the present invention, whereby after
derivation of new empirical values, a new filled rectangular array must be
generated; and
FIG. 5 illustrates the construction of the new color calibration mapping
using the method and system described herein.
Referring now to the drawings where the showings are for the purpose of
describing an embodiment of the invention and not for limiting same, a
basic system for carrying out the present invention is shown in FIG. 2. In
a system, a scanner 10, such as perhaps the color scanner available in the
Xerox 5775 digital color copiers, which can be calibrated to produce a set
of digital colorimetric or device independent data describing a scanned
image 12, which, by definition can be defined in terms of the colorimetric
R.sub.o,G.sub.o,B.sub.o space. Resulting from the scanning operation is a
set of scanner image signals R.sub.s, G.sub.s, B.sub.s, defined in device
dependent scanner terms. Incorporated into the scanner or another
processing path is a post-scanning processor 14, which provides correction
of scanner image signals R.sub.s, G.sub.s, B.sub.s to colorimetric terms,
R.sub.c, G.sub.c, B.sub.c, typically digital in nature. The values may be
in terms of CIE color space (r,g,b), or the L*a*b* luminance-chrominance
space (LC.sub.1 C.sub.2). A color space transform, indicated by block 20,
such as that described in U.S. Pat. No. 4,275,413 to Sakamoto, is used to
convert the device independent data to device dependent data. The output
of color space transform 20 is the image defined in terms of a device
dependent space, or colorant driving signal C.sub.p, M.sub.p, Y.sub.p,
K.sub.p that will be used to drive a printer 30. In one possible example,
the colorant values represent the relative amounts of cyan, magenta,
yellow, and black toners that are to be deposited over a given area in an
electrophotographic printer, such as, again, Xerox 5775 digital color
copiers. The printed output image may be said to be defined in terms of
R.sub.p,G.sub.p,B.sub.p, which are hoped to have a relationship with
R.sub.o,G.sub.o,B.sub.o such that the printed output image has a color
that is colorimetrically similar to the original image, although that
similarity is ultimately dependent upon the gamut of the printing device.
As described in U.S. patent application Ser. No. 07/955,075 by Rolleston,
entitled "Color Printer Calibration Architecture", black addition for
under color removal and gray balance processing may also be combined into
the color space transform element. Although these features are not
required, they are desirable and are illustrated herein. When we refer to
colorimetric spaces, we are referring to spaces which are transforms of
CIE XYZ space (1931). Such colorimetric spaces are also inherently device
independent. When we refer to device dependent space, we refer to a color
space which is defined only in terms of operation of the device using it.
While many color spaces have three dimensions, it is possible to have
color spaces with less than three dimensions or more than three
dimensions.
With reference now to FIG. 3, and color space transformation and color
correction 20, initially, R.sub.c, G.sub.c, B.sub.c color signals are
directed to an interpolation device 140, which includes a three
dimensional lookup table stored in a device memory 150 such as a RAM or
other addressable memory device, which will meet speed and memory
requirements for a particular device. Color signals R.sub.c, G.sub.c,
B.sub.c are processed to generate address entries to the table which
stores a set of transform coefficients with which the R.sub.c, G.sub.c,
B.sub.c may be processed to convert them to C.sub.x, M.sub.x, Y.sub.x
colorant signals or any multi-dimensional output color space including but
not limited to CMYK or spectral data. Values which are not mapped may be
determined through interpolation.
It will no doubt be recognized that there are many methods of providing a
transform from device independent data to device dependent data, with U.S.
Pat. No. 4,275,413 to Sakamoto describing one method, which itself can be
varied. Once a conversion table is established, a method of interpolation
referred to as tri-linear or cubic interpolation may also be used to
calculate output values from the limited set of input values.
To create the table, a set of color patches are created, preferably
including determined linearization and black addition. This is done by
printing and measuring about 1000 to 4000 patches of printer colors
distributed throughout the color space, i.e., a large set of printer
driving signals are generated, in varying densities of combinations of
C,M,Y,K, and used to drive the printer. The color of each patch is
measured, using a spectrophotometer to determine color in terms of
R.sub.c,B.sub.c,G.sub.c. The measured colors of these patches are used to
build a three dimensional lookup table (LUT) relating
R.sub.c,B.sub.c,G.sub.c defined colors to C.sub.x M.sub.x Y.sub.x defined
colors. Conversions that do not include mapped and measured points may be
interpolated or extrapolated. Reference is made to U.S. patent application
Ser. No. 08/144,987 to Rolleston entitled, "Color Printer Calibration Test
Pattern", filed Oct. 29, 1993, which shows and describes a calibration
test pattern for this purpose.
With reference again to FIG. 2, a calibration image is conveniently stored
in a device memory such as calibration ROM 60, RAM, floppy or the like, or
are generated on the fly with a predetermined generation function. Signals
stored therein are directed to the printer under the control of printer
controller 65. Spectrophotometer 70 (which can alternatively be a
colorimeter, a calibrated densitometer or even a calibrated color scanner)
is used to scan the calibration target and produce R.sub.o G.sub.o B.sub.o
signal values as a function of sensed density, representing the colors of
each scanned patch. Interpatch correlation processor 80 reads the
responses provided from spectrophotometer 70 for each location in the
calibration target and correlates the response with the input CMY signals,
so that an R.sub.c G.sub.c B.sub.c to CMY mapping is generated. The data
derived at interpatch correlation processor 80 is directed to LUT
processor 100, which generates the required lookup tables for storage in
color space transform and color correction 20.
Now the principle of the present invention will be described with reference
to FIG. 1A, 1B and FIG. 4. FIG. 1A is a two dimensional color space
example chosen to simplify the more common problem in three dimensions.
FIG. 1A illustrates the required regular array of data values A.sub.0 with
example mappings indicated by X's at points a, b, c and d. The problem is
that printing a color corresponding to mapping O at point e is desired,
but when that mapping is interpolated using existing data, it does not
provide the expected color. If the surrounding mappings at points a(3,3),
b(3,2), c(4,2) and d(4,3) are correct or acceptable, it may be concluded
that the response of the system in this region of color space is very
non-linear, and that linear interpolation from existing data will produce
errors in the output. An improved characterization of the system response
is required.
To obtain a better characterization of the printing system in this region,
three more color patches are generated (a set referred to as P.sub.i),
generally within the limits of the region, and the printer response is
measured, as indicated by the hollow squares in FIG. 1B. The new patches
P.sub.i are located at (x,y)=(3.5, 2) (3.5, 2.75) and (4, 2.5). The actual
locations and number of these patches can vary.
The newly derived mappings P.sub.i cannot simply be added to the
calibration set, because they will create situations where the region
would not be divisible into non-overlapping space filling triangles (or
tetrahedrons in the 3-D case). In the original data set A.sub.0, two
non-overlapping space filling triangles in this region were formed by the
points [(3,2), (4,2), (4,3)] and [(3,3), (3,2), (4,3)].
The inventive solution, illustrated in FIG. 4, divides the region defined
by these points into sets of smaller squares using linear interpolation
and weighted averaging to estimate required values. This works in the 2-D
case described here, but to maintain continuity across the boundary in the
third dimension it is also necessary to add in an entire line (or plane,
in the 3-D case) of new data points. That is, we must have a value at
x=3.5 for every possible Y value, and we must have a value at y=3.5 and
y=3.75 for every possible X value. The set of new points
(P.sub.i(expanded)) which we must calculate are shown as solid squares in
FIG. 4. Initially, these values are based on the set of mappings A.sub.0.
Note that this process has the effect of maintaining a full and filled
rectangular array of points, even though only a few new points on each
line (or plane) were measured. The points on the line (or plane) which
were not measured are obtained by linear interpolation. This is the same
type of interpolation that would have been done later in the use of the
data set, and is done in regions where we have not seen a problem with
assuming a linear response of the system.
In addition to adding new data points by linear interpolation, the points
which are "near" the new set of measured points (for example; the three
points indicated by black squares at (x,y)=(3.5, 2.5), (3.5, 3.0), and
(4.0, 2.75) in FIG. 1B and FIG. 4) are updated by a weighted averaging
technique, such as Shepard's Method using data from P.sub.i in addition to
data from A.sub.0. Now, the three points at (3.5, 2.5), (3.5, 3.0), and
(4.0, 2.75) in FIG. 4 will be interpolated or evaluated using the values
of (x,y)=(3.5, 2), (3.5, 2.75), (4, 2.5) from the set P.sub.i, and the
values at (x,y)=(4,2), and (4,3) from the set A.sub.0. It is believed that
using these closer points would produce improved printer signals.
These newly derived mappings, which map regular printer signals to
empirically derived colorimetric or device independent signals, are used
initially in an inverse tetrahedral interpolation process, to produce a
mapping of regular colorimetric signals to printer signals. This mapping
is then loaded and used, for example to interpolate printer signals to
produce an improved response for the color represented by the open circle
of FIG. 4.
The inventive method of improving printer linearity suggests that: given a
filled rectangular array of points A.sub.0 mapping printer signals to
device independent or colorimetric color space signals, it is desirable to
add some set of points P.sub.i, were i=1, 2 . . . N, in such a way that a
filled rectangular array of points is derived. This requirement is
accomplished in four steps:
1) Identify a set of planes such that each new point P.sub.i, and each
original point defined by A.sub.0 will be located at the intersection of
three planes in color space;
2) Using the set of points A.sub.0 as a starting condition, interpolate a
new set of points A.sub.1, such that each 3 way intersection of the planes
found in step 1) has an associated mapping. Initially, all values of
A.sub.1 are based on values of A.sub.0.
3) Any points in A.sub.1 which also have measured values defined by a
P.sub.i are updated to the correct (i.e., measured, not interpolated)
values of P.sub.i.
4) Any points in A.sub.1, which are not part of A.sub.0 or defined by a
value P.sub.i, but are near a value of P.sub.i, are modified using nearby
points in either A.sub.0 or P.sub.i with Shepard's interpolation, or some
other interpolation method. In the example above, any interpolated points
contained within or in the box defined by (x, y)=(3,2) and (4,3) are
updated using the three new points and the original values at the corners
of the box.
FIG. 5 illustrates the data flow in the system to accomplish the goals of
the invention. The color space mappings forming mapping set A.sub.0 (the
flawed mapping) will be used as the basis for creating the new mapping set
A.sub.1 (the corrected mapping). Mappings P.sub.i are generated in a
standard manner, but are concentrated in color space in the region where
any non-linearity was noted. The P.sub.i mappings (there m | | |
