Image analysis – Color image processing – Compression of color images
Reexamination Certificate
2000-03-17
2004-02-24
Chen, Wenpeng (Department: 2624)
Image analysis
Color image processing
Compression of color images
C358S525000
Reexamination Certificate
active
06697520
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method of interpolation between known values to find intermediate values.
2. Description of the Related Art
Interpolation has a number of applications, particularly in the field of image processing. A particularly important use is in color mapping: the taking of values in one color space and mapping them on to corresponding values in another color space. Color mapping is important, because different devices may function best or most naturally in a particular color space. For example, a scanner may advantageously use the additive color space RGB (Red, Green, Blue), whereas a printer may more advantageously use the subtractive color space CMY (Cyan, Magenta, Yellow). There are a large number of other color spaces in common use: CieLab, CMYK, YC
b
C
r
, LUV and LHS are examples. To allow devices using different color spaces to interact, a method is needed to convert data from the color space of one device to the color space of another.
Such conversions can generally be carried out with a mathematical formula (though not a trivial one, as such mappings will typically be non-linear). The most satisfactory approach to computation in such cases is to use a lookup table. The difficulty with using a lookup table is that this may need to be extremely large—for example, a full table for conversion from a 24 bit RGB color space to a 24 bit CMY color space would require 48 MByte of memory, which is clearly unacceptably large. The solution, set out in UK Patent 1369702 and U.S. Pat. No. 3,893,166, is to store in the table only a coarse (sparse) lattice of points in the color space, and to use linear interpolation to compute the values between these points. In this approach, only values for every 2
N
points are stored in each of the input dimensions (plus the last point in every dimension). Choice of N is important—if low, then the table will be large, and if high, interpolation will not approximate with sufficient accuracy. If N=4, the conversion above is reduced in size to a more acceptable 14.4 KByte.
FIG. 1
illustrates the problem. Input color space components
1
are provided in three dimensions (a, b, c). For the values in each of these dimensions, the higher bits a
u
,b
u
,c
u
(from the highest bit to bit N) are used to find a coarse lattice point
2
, and more particularly the cube
3
in the coarse lattice containing the point of interest. The lowest bits a
l
,b
l
,c
l
are then used to determine the output components
4
with values x,y,z in the output color space using interpolation.
A number of interpolation techniques have been developed. The best known is trilinear interpolation, which uses a weighted average of values at the eight vertices of a cube in the sparse lattice to obtain the output. Trilinear interpolation is shown in FIG.
2
. Values are known for the coarse lattice points
21
. In a first linear interpolation step, a weighted average is taken between one of the sets of points and another of the sets of points (at opposite faces of the cube formed by the coarse lattice points
21
). This generates four first linear interpolation points
22
(though alternative choices
23
,
24
could also have been made). The second linear interpolation step involves interpolation between these four points to give two second linear interpolation points
25
(using the earlier alternative choices for first linear interpolation points, again alternative second linear interpolation points
26
,
27
could be chosen). Whichever route is followed, the third linear interpolation step between the two second linear interpolation points provides the third linear interpolation point
28
and hence the output value.
Trilinear interpolation, and most other known interpolation processes, require eight table accesses (essentially, one access for each vertex). An improvement on this is provided by radial interpolation, described in British Patent Application No. 9826975.6. Radial interpolation has the advantage that it requires only five table accesses, rather than eight. Various other interpolation approaches are known, but none of these provides any significant reduction in computational complexity.
It is desirable to try and still further improve interpolation by reducing further computational complexity, and in particular by reducing as far as possible the total memory consumption for processes such as color mapping.
SUMMARY OF INVENTION
Accordingly, the invention provides a method of determining a value for a function, comprising: establishing an n-dimensional lattice having a plurality of lattice points, the function having values at the lattice points, wherein n is a positive integer 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 determining the values of only m of (n+1) known value lattice points defining an n-simplex touching or enclosing the given lattice point, wherein m is a positive integer equal to the number of n-simplexes of non-zero volume whose vertices consist of the given lattice point and n of the (n+1) known value lattice points, and by returning a weighted average of said m of the known value lattice points.
This approach is highly advantageous, as it ensures that the value for any given lattice point can be found with a maximum of (n+1) look up operations from the table of given value lattice points (the sparse lattice). If these look up operations have a critical effect on the performance of the overall system—which may be the case, particularly where the values for the sparse lattice are packed, to minimize storage requirements - then this minimization of look up operations can have a real effect on speed, in particular.
While this approach is valid for n-dimensional spaces, it is of most interest here for three-dimensional spaces (as would typically be used in color mapping). The approach is particularly effective where n=3, and the known value lattice points define a tetrahedron. Four is now the maximum number of look up operations required.
Whereas four is a maximum number of look up operations required, for many cases preferred embodiments of the invention can reduce this number to three, two, or one. Advantageously, 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.
In particular embodiments, the average number of table look up operations can be reduced further. For example, where a given lattice point is close to a known value lattice point, the given lattice point may be changed to the known value lattice point hence avoiding need for calculation of any weighted average, thus reducing the number of table look up operations required to one (from, typically, four) for such cases.
Advantageously, the known value lattice points form a sparse lattice with known value lattice points separated from each other by an integer multiple (preferably an integer power of two) of the distance between adjacent lattice points. A particularly preferred value for the integer is 8.
In a preferred approach, 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 p
Chen Wenpeng
Hewlett-Packard Development Company L.C.
LandOfFree
Method of color 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 of color interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of color interpolation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3341473