Method and apparatus for multi-dimensional interpolation

[0002] 1. Field of the Invention

[0003] 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.

[0004] 2. Description of the Related Art

[0005] 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.

[0006] What is needed is a technique to determine the sequence in which coefficients are selected for interpolation.

[0007] 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.

[0008] 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.

[0009] It is an object of the present invention to provide a system that allows an N-dimensional interpolation to be efficiently performed.

[0010] 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.

[0011] It is an additional object of the present invention to provide a technique that determines the sequence of coefficients in the interpolation.

[0012] It is also an object of the present invention to provide a system which efficiently chooses which vertices to use for interpolation.

[0013] 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.

[0014] 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.

[0015] 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.

[0016] FIG. 1 depicts a system of the present invention.

[0017] FIG. 2 illustrates an interpolation path through a cube determined according to the present invention.

[0018] FIG. 3 depicts the flow of operations of the invention.

[0019] FIG. 4 depicts an interpolation path through a hypercube according to the present invention.

[0020] The present invention achieves very high speed N-dimensional interpolation performance through the use of an algorithm that requires no large tables or other overhead to determine which grid points to use or what coefficients to use in performing the interpolation. The invention involves selecting a path through the multi-dimensional hyper-cube from a base vertex to an opposite corner of the cube. This path then is used to specify the sequence of interpolation operations.

[0021] The present invention is implemented in a color management system 10, such as depicted in FIG. 1. In a typical color management system an input source 12 of an image (still or motion), such as a scanner, a storage device (like a CD ROM), a camera, a communications network, etc., provides an image to a computer 14, such as desk top or lap top type personal computer. The input image will typically be digital color values in a particular color space, such as the three-dimensional scanner RGB color space. The computer converts the color values from the input-color space into values in an output color space, such as CRT RGB for a display or CMYK for a color printer. In such a conversion several transforms may be involved to transform into and out of a device independent color space, resulting in a number of different transforms being involved. The converted color values are then provided to the target output device, such as display 16 or printer 18. As another example, a six channel input image intended for a Hi-Fi printing process may be converted to RGB space to allow it to be viewed on a CRT.

[0022] In order to transform between color spaces, several different conversions occur using one-dimensional and N-dimensional tables. The N dimensional tables are sometimes called grid tables. N, one-dimensional input tables 22 perform scaling and other functions and provide modified input color values to M,N-dimensional grid tables 24. The inputs to the grid tables 24 typically include an integer part and a fractional part. The grid tables 24 are provided to convert the N input color values, where N is typically 3 or more in color processing, from one color space into M output color values possibly in another color space, where M is typically 3 or more in color processing. M, one-dimensional output tables 26 perform any necessary additional shaping.

[0023] Due to memory space requirements the grid table 24 typically does not include a table entry for each input and output value. As a result, the table is somewhat sparsely populated. This requires that the grid table values be interpolated when the input value does not correspond to a grid point. For example, if the input value for device1 XYZ=(1.7,3,5) and the grid points fall on even integer values, the output value for device2 must be interpolated for X=1.7. To do this the corresponding output grid values for device2 for X=1 and X=2 need to be obtained. If the corresponding output grid values for device2 are 10 and 20, respectively, then a linear interpolation will result in the first component of the output value being 17.

[0024] An important aspect of the present invention is the determination of a path through the N-dimensional cube from a base vertex to a vertex on an opposite corner of the cube. This path can then be used to perform an efficient interpolation. This path determines the sequence of the interpolation. A simple example using a three-dimensional cube 40 where N is 3 and M is 1, as depicted in FIG. 2, will first be discussed. In this cube 40 the base vertex is vertex A and the opposite vertex is vertex G. With three dimensions and eight vertices A-H there are 3! possible shortest paths along the edges of the cube from A to G resulting in six possible paths in this example.

[0025] Assume that the input value is X,Y,Z=(5.7,6.3,3.4). To determine the path through the cube the invention first isolates the fractional parts, such that Xf,Yf,Zf=(0.7,0.3,0.4). These fractional parts are then ranked from largest to smallest such that the rank Xr,Yr,Zr=(1,3,2). This ranking governs the path through the cube. As depicted in FIG. 2 by the thick line the path, as specified by the ranking, is A-B-F-G. The path determines which N+1 vertex subset of the 2^Nvertices will be used and how they are combined with the fractional values. Based on this path, during the interpolation process, the interpolation for the x-axis is performed first, followed by the z-axis which is followed by the y-axis. Note that the interpolations along the path need not be done sequentially, but could be performed in a non-sequential order, such as randomly, if desired.

[0026] A typical interpolation, which is performed on a per pixel basis in a color conversion, starts with determining 52 a base vertex, as depicted in FIG. 3. This can be done in a number of different ways. For example, the base vertex can be determined by rounding the input value down to the nearest integer or truncating the fractional part to leave only the integer part. In the example previously mentioned the base vertex of the XYZ value discussed above would be (5,6,3). Because the input table processes that are performed in a color management system already provide the integer and fractional parts of the input value, it is preferred that the integer and fractional parts already produced be used. The opposite corner or vertex can be obtained by adding one to all of the axial components of the base vertex. For example, the opposite vertex or corner would be (6,7,4). The other corners of the cube can be obtained by adding one to each of the axial components at a time, that is, the corners are (5,6,4), (5,7,3), (5,7,4), (6,6,3), etc.

[0027] Next, a sort list for the ranking step is initialized 54 which involves isolating the fractional parts of the input value. The fractional values are then ranked. This can be done in a number of different ways, however, the preferred approach is to perform a network sort 56 as described in Practical Algorithms for Programmers, by Binstock and Rex, Addison-Wesley, 1995, incorporated by reference herein.

[0028] The system then effectively enters a loop in which the interpolations are performed and accumulated. The first step of the loop is to select 58 the axis on which interpolation is to be performed. The interpolation is then performed 60 and the interpolated value is accumulated 62. Note that in the first cycle of the loop the base vertex output value is loaded into the accumulator. If the last interpolation has not been performed 64, the system returns for a selection of the next axis for interpolation. For example, if the interpolation is for a ten dimensional hyper-cube, the loop would be executed ten times. Otherwise, the result is output 68.

[0029] To illustrate a more complex example, a four dimensional input value will be interpolated. In this example, a hypercube 80 with four dimensions where N equals 4 and M equals 1 will be used, as depicted in FIG. 4. Assume that the input value is XYZW=(3.7,3.0,4.9,7.2). This results in the ranking Xr,Yr,Zr,Wr=(2,4,1,3). This produces a path through the cube 80 of A-B-C-D-E, as illustrated by the heavy line in FIG. 4. Based on this path, the interpolations are z-axis, x-axis, w-axis and y-axis. During the interpolation, the accumulator ACC starts with the output value A and the values B-E correspond to the output values for the corresponding grid points. At the start

[0030] ACC=A  (1)

[0031] In the first cycle

[0032] ACC=A+(B−A)dz  (2)

[0033] where dz=0.9.

[0034] In the second cycle

[0035] ACC=A+(B−A)dz+(C−B)dx  (3)

[0036] where dx=0.7.

[0037] In the third cycle

[0038] ACC=A+(B−A)dz+(C−B)dx+(D−C)dw  (4)

[0039] where dw=0.2.

[0040] In the final cycle

[0041] ACC=A+(B−A)dz+(C−B)dx+(D−C)dw+(E−D)dy  (5)

[0042] where dy=0.0.

[0043] Note that this equation can be rearranged to:

[0044] ACC=A(1−dz)+B(dz−dx)+C(dx−dw)+D(dw−dy)+Edy  (6)

[0045] The interpolations of equations 5 and 6 are linear interpolations and other interpolation methods could be used instead. Equation 5 represents an embodiment which for convenience is called a “difference of vertices” method while equation 6 represents an embodiment called a “difference of fractions” method. The C code provided in the Appendix provides a more detailed description of the process of the invention and supports M output values. The two embodiments are presented, both giving the same results. The “difference of vertices” method requires more adds but uses fewer multiplies than the “difference of fractions” method and results in a different code implementation as shown in the Appendix. Since on many microprocessors multiplies can be much more time consuming than adds, the difference of vertices method can be faster even though the total number of operations is higher.

[0046] The process of the present invention can be stored on a storage medium, such as a floppy disk, and provided to a color management system user for execution within a color management system. The process can also be transmitted over a network, such as the Internet, to a user rather than being distributed using a storage medium.

[0047] By providing an algorithm with the least overhead through avoiding the use of large tables or complicated decision making processes, this technique provides faster interpolation speed with no loss of quality when compared to other multi-dimensional interpolation methods.

[0048] The present invention has been described with respect to using the invention for interpolations in color processing. The invention could also be used for finite element analysis, volume imaging or other situations where interpolations in multiple dimensions are involved. The invention has been described as being suitable for implementation in a personal computer type machine. The invention could also be implemented in specialized hardware such as a parallel processor or a customized chip particularly because of the low overhead involved in obtaining results with the invention and because of the independence of the invention form the number of dimensions involved.

[0049] The many features and advantages of the invention are apparent from the detailed specification and, thus, it is intended by the appended claims to cover all such features and advantages of the invention which fall within the true spirit and scope of the invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation illustrated and described, and accordingly all suitable modifications and equivalents may be resorted to, falling within the scope of the invention.

[0050] A-G Vertices

[0051] 10 system

[0052] 12 Input source

[0053] 14 Computer

[0054] 16 Display

[0055] 18 Printer

[0056] 22 Input table

[0057] 24 Grid table

[0058] 26 Output table

[0059] 40,80 Cube

[0060] 52-68 Operation steps