Patent US3812616A successfully refreshed from Google Patents.
US6335800B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of multidimensional interpolation for color transformations
Assignee: Xerox Corp
•
Filing: 1998-12-11
•
Granted: 2002-01-01
•
Expires: 2018-12-11
Abstract
Abstract An electronic imaging system includes a receiver for receiving a digital representation of an input image, and a conversion processor for converting the input image to an output image, typically defined by distinct color spaces. The conversion processor is configured as a multidimensional look up table containing nodes at each of series of predefined input addresses. Each node is preloaded with an output color value corresponding to the input addresses. The look up table can accommodate a more efficient placement of nodes within N-dimensional space by a particular method of multidimensional interpolation. The method includes applying an interpolation algorithm in N-1-dimensional space, and then performing a 1-dimensional linear interpolation in the remaining dimension between the resulting values. Such a method allows for nodes to be allocated to rapidly changing areas within the color space represented by the LUT, while less dynamic areas can be suitably served by fewer nodes.
Inventors
- 👤 Thyagarajan Balasubramanian
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 09:55
CPC Classifications
G; G06; G06F; G06F15/00; G06F17/00; G06F17/10; G06F17/17; G06F17/175; H; H04; H04N; H04N1/00; H04N1/46; H04N1/56; H04N1/60; H04N1/6016; H04N1/6019
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
141 words
A method of transforming an input color to an output color using a multidimensional color transformation table comprising a plurality of nodes where each node contains an output color value, the method comprising: non-rectangularly spacing the plurality of nodes within an input color space defined by the multidimensional color transformation table; receiving the input color comprising an input color address; selecting from the plurality of nodes, a first set of nodes and a second set of nodes, each set adjacent to the input color; interpolating the output color values from the first set of nodes to produce a first output color boundary and interpolating the output color values from the second set of nodes to produce a second output color boundary; and performing a one-dimensional interpolation between the first output boundary and the second output boundary to produce the output color.
Claim 2
Independent Claim
141 words
A method of transforming an input color to an output color using a multidimensional color transformation table comprising a plurality of nodes where each node contains an output color value, the method comprising: non-rectangularly spacing the plurality of nodes within an input color space defined by the multidimensional color transformation table; receiving the input color comprising an input color address; selecting from the plurality of nodes, a first set of nodes and a second set of nodes, each set adjacent to the input color; interpolating the output color values from the first set of nodes to produce a first output color boundary and interpolating the output color values from the second set of nodes to produce a second output color boundary; and performing a one-dimensional interpolation between the first output boundary and the second output boundary to produce the output color.
Claim 3
Dependent Claim
36 words
The method of transforming an input color as set forth in claim 1 where the selecting step comprises: continuing selecting from the sets of nodes further subsets of nodes until subsets of four nodes are achieved.
Claim 4
Dependent Claim
30 words
The method of transforming an input color as set forth in claim 2 where the interpolating step comprises: interpolating in 2-dimensions the color values of the subsets of four nodes.
Claim 5
Dependent Claim
34 words
The method of transforming an input color as set forth in claim 3 where the performing step comprises: continuing performing one-dimensional interpolations on successive results of the 2-dimensional interpolations until all dimensions are interpolated.
Claim 6
Dependent Claim
76 words
The method of transforming an input color as set forth in claim 1 where the multidimensional color transformation table comprises N input dimensions where N is an integer greater than one, the color transformation table being configured as a plurality of N−1-dimensional tables disposed along a remaining input dimension, the method further comprising: noting in the input color a first component associated with the N−1-dimensional tables and a second component associated with the remaining input dimension.
Claim 7
Dependent Claim
80 words
The method of transforming an input color as set forth in claim 5 where the selecting step comprises: selecting from the plurality of N−1-dimensional tables: a first table being one of the N−1-dimensional tables adjacent to the second component based on the noting step, a second table being one of the N−1-dimensional tables oppositely adjacent to the second component based on the noting step; and identifying in each of the selected tables a plurality of nodes surrounding the first component.
Claim 8
Dependent Claim
57 words
The method of transforming an input color as set forth in claim 6 where the interpolating step comprises: interpolating the output color values from the nodes identified in the first table to produce a first output boundary, and interpolating the output color values from the nodes identified in the second table to produce a second output boundary.
Claim 9
Dependent Claim
54 words
The method of transforming an input color as set forth in claim 5 where the non-rectangular spacing step comprises: placing the plurality of nodes in the input space such that the output color values contained in ones of the nodes are significantly distinct from the output color values contained in others of the nodes.
Claim 10
Dependent Claim
50 words
The method of transforming an input color as set forth in claim 5 where the non-rectangular spacing step comprises: placing the plurality of nodes in the input space such that selected ones of the N−1 dimensional tables contain a number of nodes different than others of the N−1 dimensional tables.
Claim 11
Dependent Claim
48 words
The method of transforming an input color as set forth in claim 5 where the non-rectangular spacing step comprises: placing the plurality of nodes in the input space such that selected ones of the N−1 dimensional tables contain arrangements of nodes different than others of the N−1-dimensional tables.
Claim 12
Dependent Claim
128 words
In an electronic imaging system which includes a receiver for receiving a digital representation of an input image element in a first color space defined by N dimensions, where N is an integer greater than one; a conversion processor for converting the input image element to an output image element; and an image output apparatus producing the output image element on an output medium, the conversion processor comprising: an N-dimensional look up table defining a plurality of non-rectangularly placed nodes loaded with an output image value; an N−1-dimensional interpolator producing a first and a second output image boundary value associated with N−1 dimensions of the input image element; and a 1-dimensional interpolator providing the output image element by interpolating between the first and second output image boundary values.
Claim 13
Dependent Claim
128 words
In an electronic imaging system which includes a receiver for receiving a digital representation of an input image element in a first color space defined by N dimensions, where N is an integer greater than one; a conversion processor for converting the input image element to an output image element; and an image output apparatus producing the output image element on an output medium, the conversion processor comprising: an N-dimensional look up table defining a plurality of non-rectangularly placed nodes loaded with an output image value; an N−1-dimensional interpolator producing a first and a second output image boundary value associated with N−1 dimensions of the input image element; and a 1-dimensional interpolator providing the output image element by interpolating between the first and second output image boundary values.
Claim 14
Dependent Claim
33 words
The electronic imaging system of claim 11 where the look up table comprises: a plurality of nodes each loaded with an output image value significantly distinct from output image values at other nodes.
Claim 15
Dependent Claim
41 words
The electronic imaging system of claim 11 where the look up table comprises: a plurality of N−1-dimensional tables spaced along a remaining input dimension, where selected ones of the tables contain a number of nodes different from others of the tables.
Claim 16
Dependent Claim
41 words
The electronic imaging system of claim 11 where the look up table comprises: a plurality of N−1 -dimensional tables spaced along a remaining input dimension, where selected ones of the tables contain arrangements of nodes different from others of the tables.
Claim 17
Dependent Claim
15 words
The electronic imaging system of claim 11 where the image output apparatus comprises a printer.
Claim 18
Dependent Claim
15 words
The electronic imaging system of claim 11 where the image output apparatus comprises a copier.
References Cited (Backward Citations)
US4275413A
Cited
US4992861A
Cited
US4941039A
Cited
US5420979A
Cited
US5208911A
Cited
US5428465A
Cited
US5719956A
Cited
US5649072A
Cited
US5739927A
Cited
US5991511A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-12-31 | 2005-07-02 | 2006-01-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-12-31 | 2009-07-02 | 2010-01-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-12-31 | 2013-07-02 | 2014-01-01 | $7700.00 | Window Closed / Lapsed |