 |
Description  |
|
|
FIELD OF THE INVENTION
The present invention is directed towards compiling and using look-up
tables storing calculated difference values required for conversion of
colors defined in a first color space to colors defined in a second color
space, and more particularly to a method of reducing redundancy in such
storage for more efficient operation.
CROSS REFERENCE
Cross reference is made to the following co-pending application U.S. Ser.
No. 07/955,075, filed Oct. 1, 1992, entitled "Color Printer Calibration
Architecture", by R. J. Rolleston et al. (assigned to the same assignee as
the present application).
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 and U.S. Pat. No. 4,511,989 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.
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. Scanners commonly operate with colors defined in
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 correct transform of those values. In the case of
computer generated images, colors defined by the user at the user
interface of his workstation are immediately converted into color space
values and directed out of the system as defined in the document colors.
Printers 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. Thus, while a
printer system receives information in a first color space, it must
convert that information to print in a second color space.
The desirability of operating in a tristimulus color space with subsequent
conversion to a printer colorant color space is well known, such 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 color input values, the values are printed
in normal operation of the printer, and measurements are made of those
colors to determine what the actual color printed was in response to the
color specification. As previously noted, most printers have non-linear
response characteristics.
In U.S. Pat. No. 4,500,919 to Schreiber, and U.S. Pat. No. 4,275,413 to
Sakamoto, the information derived was placed into look-up tables, stored
in a memory, perhaps ROM memory or RAM memory where the look-up table
relates input color space to output color space. The look-up table is
commonly a three dimensional table since color space is three dimensional.
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 and points therebetween in the volume of the
cube defining colors resulting from the combinations of the additive
primary colors. A similar construct can be made for the printer, with axes
representing cyan, magenta, and yellow. Black is usually a separate toner
which is added separately. In the 8-bit system suggested, there will be,
however, over 16 million possible colors (256.sup.3). There are clearly
too many values for a 1:1 mapping of RGB to CMYK. Accordingly, as proposed
in U.S. Pat. No. 4,275,413 to Sakamoto, only a relatively small number of
samples are made at the printer, perhaps on the order of 1000-4000.
Therefore, the look-up tables (LUT's) consist of a set of values which
could be said to be the intersections for corners of a set of rectangular
parallelepipeds mounted on top of one another. Colors falling within each
rectangular 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 accuracy of the desired
result.
The interpolation methods described all require information about the
grids, and particularly, require information about the distance between
adjacent points in space on the grid. The input color space grid has nodes
spaced at regular intervals, and accordingly the distance values are
derived by simple monotonic functions. The output color space grid is
empirically measured and accordingly the nodes are at irregular intervals,
which are often not describable by simple functions. In the example of
FIG. 1, the regular array of data values in the input color space LUT are
indicated by X's, and the point marked with an O is to be derived by
interpolation therefrom (as will become apparent, this is a simplified two
dimensional example). The LUT holds the value of the function H(x,y) for
the points (x[i], y[j]) where x[i]and y[j]are some set of discrete values
referred to as the grid points, node points, or lattice points and i runs
from 0 to M-1 and j runs from 0 to N-1 (thus giving an M.times.N LUT
size). In an example illustrated in FIG. 2, three dimensional tetrahedral
interpolation is reduced to two dimensions or triangular interpolation and
the value for the desired point is given by:
H(x,y)=H[i][j]+.DELTA.x.(H[i+1][j]-H[i][j])+.DELTA.y.(H[i+1][j+1]-H
[i+1][j])
where
.DELTA.x=(x-x[i])/(x[i +1]-x[i]),
and
.DELTA.y=(y-y[j])/(y[j+1]-y[i]).
The equations are modified appropriately if the point lies in the upper
triangle.
Notice that the differences between the known table values (i.e.
(H[i+1][j]-H[i][j]), etc . . . ) must be calculated for the interpolation
of each color which falls within the triangle defined by
(i,j)-(i+1,j)-(i+1,j+1) and therefore using this difference. When
performing interpolations for a large number of pixels (i.e. an scanned
image) it may be advantageous to compute all the possible differences
once, store them, and then use them when needed. The tradeoff in doing
this is the time for computing the differences during each interpolation
operation versus the cost of having to store and access the differences.
The easiest way to store and access these differences is to go to each
rectangle in the plane (or rectangular solid in the three dimensional
space) and compute all the differences associated with that rectangle.
With reference to FIG. 2, in the two dimensional example this means that
four differences for each node point in the table must be stored:
.DELTA.H.sub.x1 [i][j]=H[i+1][j]-H[i][j]
.DELTA.H.sub.x2 [i][j]=H[i+1][j+1]-H[i][j+1]
.DELTA.H.sub.y2 [i][j]=H[i][j+1]-H[i][j]
.DELTA.H.sub.y1 [i][j]=H[i+1][j+1]-H[i+1][i]
These differences correspond to the differences in the x-direction along
the top and bottom of a rectangle with the H[i][j] at the lower left hand
node, and the differences in the y-direction along the left and right hand
sides of the triangle formed by the diagonal of this rectangle. In the
three dimensional case, 12 difference values are stored. This is a
significant memory overhead, and methods of reducing the overhead are
desired.
The references cited herein are incorporated by reference for the
teachings.
SUMMARY OF THE INVENTION
In accordance with the invention, there is provided a method and apparatus
for storing difference information which reduces redundancy of stored
information, and therefore storage space, while minimally affecting
processing time.
In accordance with one aspect of the invention, in a system for converting
from a first color space to a second color space, where a set of
empirically derived output colors are stored, mapped to selected input
colors distributed through the color space, and wherein for an input color
which is not mapped to an output color, an interpolation process is used
to provide an output color, there is provided a method of improving the
efficiency of the interpolation value including:
calculating means for calculating the distance in color space between each
known color and each known neighboring color, and producing a set of
difference signals representing the distances;
a difference memory, storing the difference signals received from the
calculating means, the difference signals stored at a plurality of
addresses in the difference memory associated with the known color for
which the difference signals are calculated;
control means, controlling the storage of the digital difference signals,
and directing from the calculating means to the difference memory at
addresses associated with a known color only such digital difference
digital distance signals as have not been previously stored for a
neighboring known color;
the control means controlling the retrieval of the difference signals for
interpolation processing from addresses associated with the known color
and neighboring known colors, as required to provide the correct distance
signals for interpolation processing.
As described, the interpolation calculation requires a plurality of
difference signals representing the distances to a set of neighboring
colors in space. However, at least some of the plurality of difference
signals required for interpolation of a color within the boundary defined
by the known color and the set of neighboring colors are also required for
interpolation of another color within the boundaries defined by a
neighboring known color and its set of neighboring known colors.
Accordingly, rather than redundantly storing the difference values, a
storage and retrieval scheme is used which only stores non-redundant
difference signals, and retrieves from addresses associated with
neighboring colors the appropriate difference signals for a given
interpolation calculation.
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:
FIG. 1 illustrates the use of interpolation in determining relationship
between disparate color spaces;
FIG. 2 illustrates the required variables for one type of color space
interpolation;
FIG. 3 is a block diagram of a scanning/printing system with color
transformation, for converting device independent image descriptions to
device dependent image descriptions;
FIG. 4 is a block diagram showing the color space transform element of FIG.
3 in greater detail;
FIG. 5 shows the difference signal to be stored in a look-up table
associated with each node;
FIG. 6 illustrates for a three dimensional space the required difference
signals, for a point P in space, a set of possible tetrahedra for
interpolation and an indication of the difference signals stored for a
given node;
FIG. 7 shows a simplified interpolation system using the present invention;
and
FIG. 8 illustrates a method for computing the tabulated differences.
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. 3. 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 R, G, B 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 printer 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). 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. 4, 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, which includes a three dimensional
look-up table stored in a device memory 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. The values
stored in the look-up table can be empirically derived, as in Sakamoto, or
calculated or extrapolated based on empirical information, as in Po-Chieh
Hung, "Tetrahedral Division Technique Applied to Colorimetric Calibration
for Imaging Media", Annual Meeting IS&T, N.J., 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; and James
M. Kasson et al., "A Tetrahedral Interpolation Technique for Color Space
Conversion", presented at IS&T/SPIE Electronic Imaging, January, 1993. For
a color space conversion method using more than three dimensions, refer to
U.S. Pat. No. 4,511,989 to Sakamoto.
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 some 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 spectraphotometer 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 look-up 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.
As noted, and in accordance with the invention, given a table of data on a
rectangular grid, interpolation is used to find the values of the function
at points which are not included in the table. The differences between the
known table values (i.e. in FIG. 1, 2, or 3 (H[i+1][j]-H[i][j]), etc.)
must be calculated each time we wish to interpolate a point which falls
within the region using this difference for interpolation. When processing
a large number of pixels (i.e. an image) it may be advantageous to compute
all the possible differences once, store them, and then use them when
needed. The trade off in doing this is that you save the cost of computing
the differences multiple times, and you pay the price of having to store
and access the differences. With reference now to FIG. 5, the storage
space needed for these difference values can be reduced by eliminating
redundancy, and using a more complex addressing or indexing scheme to
access any needed differences for the interpolation of a given color.
Notice that the difference (H[i+1][j]-H[i][j]) will be stored as
.DELTA.H.sub.x1 in node [i][j]and as .DELTA.H.sub.x2 in node [i][j-1].
This redundancy occurs at each node interface in the LUT. The redundancy
can be removed if we store only the differences connected with the node
point at each node point. That is, store only .DELTA.H.sub.x1 (as
.DELTA.H.sub.x) and .DELTA.H.sub.y2 (as .DELTA.H.sub.y) with the node
point at [i][j]. This means that to do an interpolation in the lower
triangle as indicated above, one would have to access .DELTA.H.sub.x from
the current location, and .DELTA.H.sub.y from the location [i+1][j].
Likewise, to do an interpolation in the upper triangle, one would access
.DELTA.H.sub.y from the current location, and AHx from the location
[i][j+1]. Accordingly, after finding the index of which rectangle you are
in, you determine which tetrahedron you are in, and then calculate a new
set of indices to access the differences required.
With reference to FIG. 6, a rectangular volume in a three dimensional color
space is shown, with nodes (i, j, k), (i+1, j, k), (i+1, j, k+1),
(i,j,k+1), (i, j+1, k), i+1, j+1, k), (i+1,j+1,k+1), (i,j+1,k+1). Once
again, these nodes represent color space coordinates for which there is an
empirically determined color conversion. The color differences are
lettered A through L. For each node, only those differences reflecting the
distance to adjacent nodes in one direction. Thus, for node (i, j, k),
differences A, B and C are stored, reflecting the distance to adjacent
nodes in the increasing value direction.
FIG. 7 shows a simplified interpolator 40, which has a signal input
receiving Rc, Gc, Bc values. The signals are converted into two parts, an
index m part directed to origin determination 100, identifying which
rectangular region the color signal is in, and a fraction n part directed
to tetrahedron determination 102, identifying which tetrahedron the color
signal is in. The output signals from origin determination 100 and
tetrahedron determination 102 are directed as an input signal into address
controller 104, which directs appropriate address signals to the look-up
table shown as 106, which has as a physical embodiment any electronic
signal storage device, such as RAM, to cause the table to output the
appropriate difference signals. Any interpolation requiring differences A,
B, or C will obtain the needed differences by referencing the look up
table 106 at location (i+1,j,k), any interpolation requiring difference
signals D or E will obtain the needed difference signals by referencing
the look up table 106 at location (i+1, j, k) and so on for the remaining
differences E through L. It will be noted that the appropriate index
signals are indexed to a plurality of nodes. However, the nodes are
predictable in that they represent nodes no more than 1 unit from the
origin defining the rectangular space.
The output of LUT 106 is directed to a signal adder 108, which adds the
value at the index point to the appropriate combinations of difference
signals and fraction signals n to derive the interpolated value in the new
color space, deriving the printer driver signals C.sub.x,M.sub.x,Y.sub.x.
With reference now to FIG. 8, an arrangement for calculating the difference
values is shown as calculating processor 198. A series of clocks 200, 202,
and 204 provide an incrementing signal through the total number of entries
in the look-up table, as information to address controller 210. Address
controller 210 retrieves from LUT 212 values for each clock cycle,
representing the empirically derived color values for each successive
input value. These empirically derived values are successively stored in
latches 220 and 222, which in turn direct pairs of signals to a difference
circuit 224 to determine the difference between successive signals. These
signals are directed to address controller 104, which stores the values at
appropriate locations in look-up table 106.
It will no doubt be appreciated that values unique to each cell may still
be derived and stored for each cell. It will also be appreciated that the
referred-to difference values may be a higher order function of multiple
difference values.
It will no doubt be appreciated that while we have shown the use of the
invention in the conversion of a device independent color space to a
device dependent color space, the invention applies equally as well to
conversions to any transformation from a first space to a second, device
independent or device dependent.
The invention has been described with reference to a particular embodiment.
Modifications and alterations will occur to others upon reading and
understanding this specification. It is intended that all such
modifications and alterations are included insofar as they come within the
scope of the appended claims or equivalents thereof.
* * * * *
|
|
 |
|
 |
Description |
|
