System and method for multi-dimensional lookup table interpolation

• US 20060041609A1
• Filed: 08/20/2004
• Published: 02/23/2006
• Est. Priority Date: 08/20/2004
• Status: Abandoned Application

• Current Assignee: Toshiba Corporation, Toshiba Tec Corporation (Toshiba Corporation)
• Original Assignee: Toshiba Corporation, Toshiba Tec Corporation (Toshiba Corporation)
• Inventors: Pellar, Ronald J.
• Application Number:
  US10/923,382
• Publication Number:
  US 20060041609A1
• Time in Patent Office: Days
• US Class Current: 708/290
• CPC Class Codes: G06F 1/03 working, at least partly, by table look-up G06F1/025 takes precedence
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: H04N 1/6019 using look-up tables H04N1/6025 takes precedence

Abstract

A technique for using a one or two dimensional table lookup to provide the appropriate index and fraction for a second lookup table. The second lookup table can be a multi-dimensional lookup table. The one or two dimensional lookup table allows nonlinear conversion between input values and output values obtained from the second lookup table using standard linear interpolation techniques. The one or two dimensional lookup table can nonlinearly map input values to nodes in the second lookup table, nonlinearly map fractional values, or both.

Claims

1. A system, comprising

a sparse multi-dimensional lookup table containing a plurality of nodes, the plurality of nodes having corresponding output values;

and

an interpolation lookup table for mapping input values to corresponding nodes in the sparse multi-dimensional lookup table;

wherein an input value received by the interpolation lookup table is converted to an output value based on the mapping of the interpolation lookup table to the sparse multi-dimensional lookup table.

2. The system of claim 1, wherein the sparse multi-dimensional lookup table is linearly spaced.

3. The system of claim 2, wherein the mapping of the interpolation lookup table to the sparse multi-dimensional lookup table is nonlinear.

4. The system of claim 1, wherein the interpolation lookup table is configured to receive n input values, the sparse multi-dimensional lookup table having m nodes, where n and m are integers greater than zero, and n is greater than m.

5. The system of claim 1, wherein the interpolation lookup table is configured to produce a fractional value corresponding to a space between the corresponding node for the input value and a next node.

6. The system of claim 5, further comprising a linear interpolator, the linear interpolator configured to receive the fractional value from the interpolation lookup table, and the output value corresponding to the input value from the sparse multi-dimensional lookup table and producing an adjusted output value based on a linear interpolation of the fractional value combined with the output value.

7. The system of claim 6, wherein the fractional values are nonlinearly spaced in the interpolation lookup table.

8. The system of claim 7, wherein the mapping of input values from the interpolation to the output values in the sparse multi-dimensional lookup table is non-linear.

9. The system of claim 8, wherein the interpolation lookup table is configured to receive n input values, the second lookup table having m nodes, where n and m are integers greater than zero, and n is greater than m.

10. The system of claim 1, wherein the interpolation lookup table is a one-dimensional floating point lookup table, and wherein floating point values are produced by summing the indices and fractions.

11. The system of claim 1, wherein the interpolation lookup table is a two-dimensional lookup table, wherein one dimension provides the indices into the sparse multi-dimensional lookup table and a second dimension provides a fractional value.

12. A system, comprising

means adapted for determining an output value by looking up a node in a linearly spaced sparse multi-dimensional lookup table, the node corresponding to a corresponding output value;

and

means adapted for receiving an input value and responsive the input value to employ an interpolation lookup table to convert the input value to an index corresponding to the node in the linearly spaced sparse multi-dimensional lookup table

wherein the means adapted for determining an output value is responsive to the means adapted for receiving an input value.

13. The system of claim 12, wherein the interpolation lookup table nonlinearly converts the input value to the index.

14. The system of claim 12, wherein the means adapted for receiving an input value is configured to receive n input values, the means adapted for determining an output value table having m nodes, where n and m are integers greater than zero, and n is greater than m, the interpolation lookup table maps the n input values to the m nodes.

15. The system of claim 12, further comprising

means adapted for interpolating;

wherein the means adapted for receiving an input value is configured to produce a fractional value corresponding to a distance between consecutive output values in the linearly spaced sparse multi-dimensional lookup table; and

wherein the means adapted for interpolating calculates an interpolated fractional value corresponding to the fractional value of the distance between output values and adds the interpolated fractional value to the output value.

16. The system of claim 15, wherein the fractional value produced by the means adapted for receiving is non-linear.

17. The system of claim 15, wherein the interpolation lookup table is a one-dimensional floating point table.

18. A computer readable medium of instructions, comprising:

means adapted for obtaining an output value from a sparse multi-dimensional lookup table based on an index value; and

means adapted for receiving an input value and converting the input value to a corresponding index value using an interpolation table.

19. The computer readable medium of instructions of claim 18, wherein the relationship between the input value and the corresponding index value is nonlinear.

20. The computer readable medium of instructions of claim 19, further comprising

means adapted for interpolating;

wherein the means adapted for receiving is configured to produce a fractional value corresponding to a distance between output values stored in the multi-dimensional lookup table; and

wherein the means adapted for interpolating calculates an interpolated fractional value corresponding to the fractional value of the space between output values and adds the interpolated fractional value to the output value.

21. The computer readable medium of instructions of claim 20, wherein the means adapted for receiving is configured to produce fractional values nonlinearly.

22. A method for performing nonlinear interpolation using a linear spaced sparse lookup table, comprising:

receiving an input value to convert to an output value;

converting the input value to an index value using an interpolation lookup table; and

retrieving an output value from the multi-dimensional lookup table based on the index value.

23. The method of claim 22, wherein the interpolation lookup table provides a non-linear relationship between the input value and the index value.

24. The method of claim 22, further comprising:

the converting the input value further comprising producing a fractional value based on a distance between nodes of the linear spaced multi-dimensional lookup table;

interpolating the fractional value to produce a fractional output value; and

adjusting the output value based on the fractional output value.

25. The method of claim 24, wherein the fractional value is non-linear.

26. The method of claim 24 wherein the converting the input value uses an interpolation lookup table that has floating point values, corresponding to the index and fractional value.