Facsimile and static presentation processing – Static presentation processing
Reexamination Certificate
1998-06-23
2002-04-16
Moore, David (Department: 2722)
Facsimile and static presentation processing
Static presentation processing
C358S525000, C358S515000, C358S506000, C358S530000, C382S167000, C382S162000
Reexamination Certificate
active
06373580
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system that performs a multi-dimensional interpolation typically used in color processing and, more particularly, one in which the sequence of the interpolation is governed by a ranking of the fractional parts of the point or value to be interpolated.
2. Description of the Related Art
Current color management techniques are based on the use of color transforms that include multi-dimensional “grid” tables to embody a given color mapping. When processing pixel data through a color transform or when composing or combining transforms it is necessary to interpolate in the N-dimensional tables (where N is the number of input dimensions) because storing the value of the mapping for every possible input would lead to impractically large data structures. Kodak's color management module or CMM uses a linear interpolation technique to interpolate in the grid tables. A linear method can give good quality and speed characteristics. The high evaluation speed is partly a consequence of the fact that only N+1 grid points are required to perform an interpolation (other techniques such as trilinear require more points, 2{circumflex over ( )}N in the case of trilinear or its higher dimensional equivalents). However, achieving the fastest evaluation speed also requires a good algorithm for determining which N+1 points to use (out of the possible 2{circumflex over ( )}N in the surrounding hypercube) and determining which coefficients to use in performing the interpolation.
What is needed is a technique to determine the sequence in which coefficients are selected for interpolation.
Current linear interpolations give acceptable performance when N=4 but degrade quickly as the number of input dimensions increases. However, transformations involving more than 4 input dimensions are gradually becoming necessary. For example, processing images originating in a space designed for “Hi-Fi” printing requires between 5 and 8 input dimensions corresponding to the number of inks used.
What is needed is a technique that allows an arbitrarily high number of dimensions to be involved in interpolation and to provide accurate and fast results in such as situation.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a system that allows an N-dimensional interpolation to be efficiently performed.
It is another object of the present invention to provide a system that does not require large tables or other overhead to determine which grid coefficients or components to use in an interpolation.
It is an additional object of the present invention to provide a technique that determines the sequence of coefficients in the interpolation.
It is also an object of the present invention to provide a system which efficiently chooses which vertices to use for interpolation.
It is a further object of the present invention to provide a process that can be used regardless of the number of input dimensions or output dimensions in the interpolation.
The above objects can be attained by a system that ranks the sequence of grid point interpolations by the fractional components of the point or value to be interpolated. An N-dimensional interpolation is performed according to this sequence.
These together with other objects and advantages, which will be subsequently apparent, reside in the details of construction and operation as more fully hereinafter described and claimed, reference being had to the accompanying drawings forming a part hereof, wherein like numerals refer to like parts throughout.
REFERENCES:
patent: 4275413 (1981-06-01), Sakamoto et al.
patent: 4511989 (1985-04-01), Sakamoto
patent: 4578812 (1986-03-01), Yui
patent: 5325217 (1994-06-01), Nagler et al.
patent: 5390035 (1995-02-01), Kasson et al.
patent: 5544052 (1996-08-01), Fujita et al.
patent: 5581376 (1996-12-01), Harrington
patent: 5748195 (1998-05-01), Nin
patent: 5943058 (1999-08-01), Nagy
patent: 5977977 (1999-11-01), Kajiya et al.
patent: 6031642 (2000-02-01), Vondran, Jr.
patent: 6043909 (2000-03-01), Holub
Dialog OneSearch, Feb. 5, 1998.
Eastman Kodak Company
Kianni Kaveh
Moore David
Woods David M.
LandOfFree
Method and apparatus for multi-dimensional interpolation 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 and apparatus for multi-dimensional interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for multi-dimensional interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2857345