Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1998-12-11
2002-01-01
Nguyen, Madeleine (Department: 2622)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S525000, C382S167000
Reexamination Certificate
active
06335800
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to the digital imaging arts. It finds particular application to multidimensional interpolations for color transformations to enable more efficient placement of nodes in a look up table and will be described with particular reference thereto. It is to be appreciated however, that the proposed invention may also be applied to any type of look up table or conversion means processing a complex function.
Computers and other electronic equipment typically depict color in 3-D coordinates such as RGB. Many printers, on the other hand, print in either three-dimensional colorant space, cyan, magenta, yellow (CMY) or four-dimensional colorant space, cyan, magenta, yellow, and black (CMYK) which correspond to the input values, e.g. RGB. Frequently, a device independent color space is used as an intermediate representation of the image. A common choice for such a device independent space is a luminance-chrominance space, denoted generically as LC
1
C
2
. In use, translations are then needed from input RGB to LC
1
C
2
, and from LC
1
C
2
to printer colorant space. A common example of a luminance-chrominance space is CIE L*a*b*.
Unfortunately the translation between these, and other, standards is not linear. Indeed, because the characterization and correction between input and output color spaces is complex, often transformations are implemented with a multidimensional lookup table (LUT). Consider, as an example, a transformation T from a 3 dimensional input space, e.g. scanner RGB, to a 3 dimensional output space e.g. CIE L*a*b*. The LUT then consists of a 3 dimensional rectangular grid of N
R
×N
G
×N
B
nodes, where N
I
is the number of grid locations along the I-th axis, I=R,G,B. At each node location, an L*a*b* value is stored. The transformation T is then approximated by locating for a given input RGB, the enclosing rectangular cell, and then performing 3-D interpolation among the L*a*b* values stored at the cell vertices or nodes.
A problem with multidimensional grids that are based on the typical rectangular structure described above is that as the input dimensionality increases, the size of the LUT increases exponentially. To give an idea, if N
j
=16 (this is a common choice for 3-D grids), then for 3-D input, we have 4K nodes in the LUT; for 4-D input there are 64K nodes; and 5 input signals result in 1M nodes. In many applications, color transformation LUTs are 3-dimensional, and hence storage and memory requirements are not very significant issues. However, a common example where the input dimensionality is greater than 3, would be the characterization function for a printer employing 4 or more inks. This requires a transformation from N-dimensional colorant space (N>3) to some 3-D calorimetric space. In such situations, the size of the LUT does become a considerable problem. The only way to keep the LUT to an acceptable size is by limiting the number of nodes along each input dimension; thus potentially sacrificing accuracy.
An additional difficulty with multidimensional rectangular grids is that the 4K nodes, for example, are dispersed evenly throughout the color space represented by the rectangular grid. This uniform dispersal causes some of the output data stored in the grid nodes to correspond to insignificant or imperceptible changes in output tone or color vis-a-vis neighboring nodes. In other words, several distinct input addresses produce essentially the same output, effectively wasting some of the storage potential of the LUT.
Consider a 3-D example of a LUT that transforms RGB to L*a*b* using a conventional LUT structure. Referring to
FIG. 1
, the 3-dimensional LUT can be envisioned as a cube
10
containing nodes at preselected addresses along axes R, G, and B. An input color
12
defined by input color address components R
in
, G
in
, B
in
, typically will not coincide with the preselected addresses. Thus, the input color address components R
in
, G
in
, B
in
, are used to determine the 8 vertices V
1
, . . . , V
8
most closely adjacent to the input color
12
. The output L*a*b* value that corresponds to the input color
12
is approximated by some form of 3-D interpolation from output color values stored within the 8 vertices V
1
, . . . , V
8
. Common forms of 3-D interpolation are trilinear, tetrahedral, and prism interpolation. Note should be taken that typical interpolation algorithms depend on a rectangular grid or node structure (i.e. the grid is a 3-D 5×5×5 lattice of nodes).
The present invention provides an alternate structure for the multidimensional LUT, that provides greater flexibility in placing the nodes, than is allowed by the conventional grid. This allows a more efficient scheme for positioning the nodes where needed, and thus promises a reduction in LUT size in addition to overcoming other problems.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, a method of transforming an input color to an output color using a multidimensional color transformation table is provided. The table includes a plurality of nodes each containing an output color value. The method comprises a specific type of non-rectangular spacing of the plurality of nodes within a color space defined by the transformation table. An input color is received adjacent to which a first set of nodes and a second set of nodes are selected. Output color values from the first and second set of nodes are interpolated producing a first and second output color boundary. A one dimensional interpolation is then performed on the first and second boundaries producing the output color.
In accordance with another aspect of the present invention, the transformation table defines N input dimensions, where N is an integer greater than 1. The table is configured as a plurality of N−1 dimensional arrays or tables disposed along a remaining input dimension. The method includes noting in the input color a first component associated with the N−1 dimensional tables, and a second component associated with the remaining input dimension.
In accordance with another aspect of the present invention, the selecting step includes selecting from the plurality of N−1 dimensional tables both (1) a first table being one of the N−1 dimensional tables adjacent to the second component; and (2) a second table being one of the N−1 dimensional tables oppositely adjacent to the second component. In each of the selected tables, a plurality of nodes surrounding the first component is then identified.
In accordance with another aspect of the present invention, the nonrectangularly spacing step includes loading a plurality of nodes surrounding the first component is then identified.
In accordance with another aspect of the present invention, the nonrectangularly spacing step includes loading a plurality of nodes throughout the color space represented by the table such that the output color value of selected ones of the nodes are significantly distinct from output image values of other nodes.
In accordance with another embodiment of the present invention, an electronic imaging system includes a receiver for receiving an input image defined by N dimensional color space, where N is an integer greater than 1. A conversion processor is also included to convert the input image to an output image. The conversion processor includes an N dimensional lookup table defining a plurality of nodes each loaded with an output image value. An N−1 dimensional interpolator produces a first and second output image boundary value associated with N−1 dimensions of the input image. A one dimensional interpolator, interpolates between the first and second output image boundary values to provided the output image.
In accordance with another aspect of the present invention, the lookup table comprises a plurality of N−1 dimensional tables spaced along a remaining input dimension. Selected tables contain arrangements of nodes different than selected others of the tables.
One advantage of
Fay Sharpe Fagan Minnich & McKee LLP
Nguyen Madeleine
Xerox Corporation
LandOfFree
Method of multidimensional interpolation for color... 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 of multidimensional interpolation for color..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of multidimensional interpolation for color... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824156