Metid if interpolation

Abstract

A method of determining a value for a function which is particularly useful for mapping values from one colour space to another comprises a series of steps, as follows. The method is applicable to n-dimensional spaces, but is particularly described for three dimensions. The first step is to establish a three dimensional lattice, the function having values at the lattice points. The next step is to record values of the function for a subset of the lattice points, the lattice points of the subset being known value lattice points. These known value lattice points form a sparse lattice (preferably the sparse lattice points are regularly spaced along orthogonal axes). A value of the function for a given lattice point is established by returning a weighted average of the values of one or more of four known value lattice points defining a tetrahedron 42 touching or enclosing the given lattice point. Each of the lattice points which are intermediate points in a coarse lattice cube 41 is either within, or on the boundary of, at least one tetrahedron 42 whose vertices are four of the vertices of the cube.

1 . A method of determining a value for a function, comprising: 
 establishing an n-dimensional lattice, the function having values at the lattice points, and where n is greater than or equal to two;    recording values for a subset of the lattice points, the lattice points of the subset being known value lattice points; and    establishing a value for a given lattice point by returning a weighted average of the values of one or more of (n+1) known value lattice points defining an n-simplex touching or enclosing the given lattice point.    
     
     
         2 . A method as claimed in  claim 1 , wherein n=3 and the n-simplex is a tetrahedron.  
     
     
         3 . A method as claimed in  claim 2 , wherein a weighted average of all four known value lattice point values is used if the given lattice point is enclosed by the tetrahedron but is not touched by a face of the tetrahedron, a weighted average of three of the four known value lattice point values is used if the given lattice point is on a face of the tetrahedron bounded by the three of the four known value lattice points but is not touched by an edge of the tetrahedron, a weighted average of two of the four known value lattice point values is used if the given lattice point is on an edge of the tetrahedron bounded by the two of the four known value lattice points but is not at a vertex of the tetrahedron, and wherein a value of one of the known value lattice points is used if the given lattice point is also the known value lattice point.  
     
     
         4 . A method as claimed in  claim 3 , wherein a given lattice point close to a known value lattice point is changed to the known value lattice point before calculation of the weighted average.  
     
     
         5 . A method as claimed in  claim 3  or  claim 4 , wherein a given lattice point close to an edge or a face of the tetrahedron is changed to a point lying on the edge or the face of the tetrahedron before calculation of the weighted average.  
     
     
         6 . A method as claimed in any of  claims 3  to  5 , wherein if the given lattice point is enclosed by the tetrahedron but is not touched by a face of the tetrahedron, and the tetrahedron has vertices of known value lattice points with positions A, B, C, D and values a, b, c, d at the respective vertices, and wherein the given lattice point has position P and wherein the volume between four positions is expressed as Vol(position 1 position 2 position 3 position 4), the value p returned is given by:  
         p =( Vol ( ABCP ). d+Vol ( ABDP ). c+Vol ( ACDP ). b+Vol ( BCDP ). a )/ Vol ( ABCD )  
     
     
         7 . A method as claimed in any of  claims 3  to  6 , wherein if the given lattice point is on a face of the tetrahedron bounded by the three of the four known value lattice points but is not touched by an edge of the tetrahedron, the three of the four known value lattice points being A, B and C with values a, b and c respectively, the value p returned is given by p=((Area(BCP). a)+(Area(ACP). b)+(Area(ABP). c)/Area(ABC).  
     
     
         8 . A method as claimed in any of  claims 3  to  7 , wherein if the given lattice point is on an edge of the tetrahedron bounded by the two of the four known value lattice points but is not at a vertex of the tetrahedron, the two of the four known lattice points being A and B with values a and b, the value p returned is given by p=((Distance (AP). b)+(Distance (BP). a))/Distance(AB).  
     
     
         9 . A method as claimed in any preceding claim, wherein the known value lattice points form a sparse lattice with known value lattice points separated from each other by an integer multiple of the distance between adjacent lattice points.  
     
     
         10 . A method as claimed in  claim 9 , wherein said integer multiple is an integer power of two.  
     
     
         11 . A method as claimed in  claim 10 , wherein the integer is 4 and all given lattice points coincide with a value lattice point or lie between two adjacent value lattice points or lie within a triangle described by three adjacent value lattice points.  
     
     
         12 . A method as claimed in  claim 10 , wherein the integer is 8 or more and all given lattice points coincide with a value lattice point or lie between two adjacent value lattice points or lie within a triangle described by three adjacent value lattice points or lie within or lie within a tetrahedron of four adjacent value lattice points.  
     
     
         13 . A method as claimed in  claim 12 , where the integer is 8.  
     
     
         14 . A method as claimed in any of  claims 2  to  13 , wherein the step of establishing a value comprises determining a set of four known value lattice points which form a tetrahedron touching or enclosing the given lattice point, and providing the weighted average from the positions of four known value lattice points, the known values of one or more of the four known value lattice points, and the position of the given lattice point.  
     
     
         15 . A method as claimed in  claim 14 , wherein the step of providing the weighted average comprises using the positions as inputs to a jump table.  
     
     
         16 . A method of mapping values in a first colour space to values in a second colour space, comprising establishing the value in the second colour space by the method of determining a value for a function described in any of  claims 1  to  15 .  
     
     
         17 . A computer programmed to determine a value for a function, by: 
 establishing an n-dimensional lattice, the function having values at the lattice points, and where n is greater than or equal to two;    recording values for a subset of the lattice points, the lattice points of the subset being known value lattice points; and    establishing a value for a given lattice point by returning a weighted average of the values of one or more of (n+1) known value lattice points defining an n-simplex touching or enclosing the given lattice point.    
     
     
         18 . A computer as claimed in  claim 17 , wherein n=3 and the n-simplex is a tetrahedron.  
     
     
         19 . A computer as claimed in  claim 18  wherein the computer is programmed such that a weighted average of all four known value lattice point values is used if the given lattice point is enclosed by the tetrahedron but is not touched by a face of the tetrahedron, a weighted average of three of the four known value lattice point values is used if the given lattice point is on a face of the tetrahedron bounded by the three of the four known value lattice points but is not touched by an edge of the tetrahedron, a weighted average of two of the four known value lattice point values is used if the given lattice point is on an edge of the tetrahedron bounded by the two of the four known value lattice points but is not at a vertex of the tetrahedron, and wherein a value of one of the known value lattice points is used if the given lattice point is also the known value lattice point.  
     
     
         20 . A program storage medium readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for determining a value for a function, said method steps comprising: 
 establishing an n-dimensional lattice, the function having values at the lattice points, and where n is greater than or equal to two;    recording values for a subset of the. lattice points, the lattice points of the subset being known value lattice points; and    establishing a value for a given lattice point by returning a weighted average of the values of one or more of (n+1) known value lattice points defining an n-simplex touching or enclosing the given lattice point.    
     
     
         21 . A program storage medium as claimed in  claim 20 , wherein n=3 and the n-simplex is a tetrahedron.  
     
     
         22 . A program storage medium as claimed in  claim 21 , wherein in the step of establishing a value, a weighted average of all four known value lattice point values is used if the given lattice point is enclosed by the tetrahedron but is not touched by a face of the tetrahedron, a weighted average of three of the four known value lattice point values is used if the given lattice point is on a face of the tetrahedron bounded by the three of the four known value lattice points but is not touched by an edge of the tetrahedron, a weighted average of two of the four known value lattice point values is used if the given lattice point is on an edge of the tetrahedron bounded by the two of the four known value lattice points but is not at a vertex of the tetrahedron, and wherein a value of one of the known value lattice points is used if the given lattice point is also the known value lattice point.