Streamlined tetrahedral interpolation

Details Streamlined tetrahedral interpolation Streamlined tetrahedral interpolation

1998-06-26

2002-10-15

Lee, Thomas D. (Department: 2724)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S522000, C358S525000

Reexamination Certificate

active

06466333

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to tetrahedral interpolation by which an interpolated color output value is interpolated from values in a color look-up table based on a color input value. More particularly, the invention relates to tetrahedral interpolation that is streamlined so as to increase processing efficiency.
2. Description of the Related Art
Tetrahedral interpolation is a known technique by which color output values are obtained through interpolation of color values in a look-up table based on a color input value. One description of tetrahedral interpolation can be found in U.S. Pat. No. 4,275,413 to Sakamoto. According to the technique described there, a color look-up table is arranged into a cubic grid of color input values, with a color output value stored at each vertex of the cubic grid. A cube into which a desired color input value falls is dissected into plural tetrahedrons, and the particular tetrahedron into which the color input value falls is selected. Thereafter, interpolation is performed so as to obtain a color output value corresponding to the color input value based on a weighted sum of the values at the vertices of the dissected tetrahedron.
Interpolation so as to obtain a color output value based on a color input value is desirable because it improves color accuracy, and tetrahedral interpolation is desirable since it improves color smoothness between adjacent color values in adjacent cubes of the look-up table. At the same time, however, since interpolation must be performed for each pixel of a color image (or at least for each previously unprocessed color in a color image), the computational burden to perform tetrahedral interpolation is great.
The computational burden for tetrahedral interpolation is even greater for some computers since one of the steps required for tetrahedral interpolation is a determination as to which dissected tetrahedron a color input value falls. When programming a computer to perform such a determination, it is commonplace to use conditional branches by which the input coordinates of the color input value are compared against the coordinates of the vertices of the dissected tetrahedrons. Such conditional branches are expensive computationally, particularly when embodied in a device driver (such as a printer or a scanner driver) executing in a personal computer. Especially when the personal computer is powered by processors, like Pentium® or Pentium® clone processors, which employ dual processor pipelines together with branch prediction, there are significant processor cycle penalties for making unpredicted branches. Overall, these penalties slow the tetrahedral interpolation process to unacceptable levels. See generally Schmit, “Pentium Processor Optimization Tools”, Academic Press, Inc., 1995, pp. 101-192.
Accordingly, even though tetrahedral interpolation is a desirable feature, it is often omitted when implementing print drivers because of the significant processor penalties associated with its implementation.
SUMMARY OF THE INVENTION
It is an object of the present invention to address the foregoing, by providing a streamlined technique for implementing tetrahedral interpolation, and particularly such a streamlined technique which does not involve conditional branches for determining which of plural dissected tetrahedrons a particular input color value falls.
Specifically, the invention is tetrahedral interpolation for use with a color look-up table which stores color output values at each vertex of a cubic grid of color input values, so as to obtain interpolated color output values for color input values. For each color input value, weights are calculated that depend on values of the color components that together constitute the color input value. The calculated weights are stored in a temporary look-up table that is accessible by an index. Thereafter, the index is calculated by executing a block of code that does not include conditional branches. The block of code calculates the index based on relative magnitude of the plural component values, and preferably is implemented by a block of code that calculates the index based on arithmetic calculations between the component values and not based on branches conditioned on comparisons between the component values. Finally, weights at the indexed location of the temporary look-up table are applied to color output values in the color look-up table so as to obtain the interpolated color output value.
By calculating the index with a block of code that does not include conditional branches, execution of the code is greatly speeded since there are no processor cycle penalties for making unpredicted branches. Accordingly, efficient use of processors is achieved, particularly for processors that involve dual processor pipelines together with branch prediction.
In one preferred embodiment of the invention, the block of code by which indexes are calculated involves the use of arithmetic operations, such as subtractions, which automatically set a condition code based on the outcome of the arithmetic operation. For example, the assembly language command set of a Pentium® processor includes a “sub” command which sets a condition code and the condition code which can be used to determine whether the resultant difference is equal to zero, above zero, or both. Again referring to the Pentium® assembly language command set, the command “setae” sets a register if the condition code indicates that a previous subtraction result was above or equal to zero, and the command “seta” sets a register if previous subtraction result was above zero. The preferred embodiment of the invention uses such set commands so as to construct the index needed to index into the temporary look-up table of weights, all in a block of code that does not include conditional branches.
Use of such arithmetic commands results in an additional benefit that the results of subtractions can also be used in other operations needed for tetrahedral interpolation. In other embodiments, the index is calculated using bit shift commands or masking commands.
The steps of calculating the plural weights, storing the calculated weights, executing the block of code, and applying the weights preferably are repeated for each pixel of an input image, or at least each previously unprocessed color in the input image, so as to derive color output values for each pixel for printout by a printer.
In another aspect, the invention is a method for obtaining plural output color component values from plural input color component values using tetrahedral interpolation. The plural input color component values represent an input color in an input color format. The plural output color component values represent an output color in an output color format. The method is based on a cubic grid, with each axis of the cubic grid corresponding to a type of input color component, and each vertex of the cubic grid corresponds to plural output color component value entries. An entry in the cubic grid is determined that corresponds to a vertex of a cube which includes the input color. Plural weights are calculated based on distances of the plural input color component values from at least one vertex of the cube. The plural weights are stored in a look-up table accessible by an index that indicates which tetrahedron of the cube corresponds to the plural input color component values. The index is calculated and is used to calculate weights in the look-up table. The plural output color component values are obtained by applying the accessed plural weights to the plural output color component value entries corresponding to vertices that form the indicated tetrahedron of the cube. In the method, the index is calculated in a block of code consisting of assembler instructions, all of which are performed regardless of relative values of the input color component values.
In the preferred embodiment, fixed blocks of assembler instructions are also used to calculate the plural weights, store the plural weights, access the plu

Affiliated with

Also associated with

Rating

Streamlined tetrahedral 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 Streamlined tetrahedral interpolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Streamlined tetrahedral interpolation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2957848