# US 2006/0041609 A1 · System and method for multi-dimensional lookup table interpolation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0041609 A1
- Document ID: US20060041609A1
- Status: Published application
- Kind: A1
- Application number: 10/923,382
- Filed: 2004-08-20
- Published: 2006-02-23
- Earliest claimed: 2004-08-20
- Inventors: Ronald Pellar
- Web page: https://patentgrep.com/patent/US20060041609A1

## CPC

- G06F 1/03: working, at least partly, by table look-up (G06F1/025 takes precedence)
- G06T 11/10: Texturing; Colouring; Generation of textures or colours (retouching, inpainting or scratch removal G06T5/77)
- H04N 1/6019: {using look-up tables (H04N1/6025 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 1)

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.

### Claim 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.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 12)

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.

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 15)

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

### Claim 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.

### Claim 19 (depends on 18)

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

### Claim 20 (depends on 19)

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.

### Claim 21 (depends on 20)

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

### Claim 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.

### Claim 23 (depends on 22)

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

### Claim 24 (depends on 22)

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.

### Claim 25 (depends on 24)

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

### Claim 26 (depends on 24)

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.
