US5384902A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for generating a fast inverse table
Assignee: Adobe Inc
•
Filing: 1991-12-24
•
Granted: 1995-01-24
•
Expires: 2011-12-24
Abstract
Abstract A large set of image data values are associated with a smaller set of values, such as color palette look-up table (LUT) indices, to create an inverse table. The larger set of image data values address into the inverse table. The inverse table is simulated as a symmetrical N-dimensional structure in computer memory, with N being the color dimension of the image data values. Generally, a set of star spaces in the structure are captured by the color palette LUT indices; the capturing is based on some relationship such as the relationship between the image data values and the color palette values indexed by the color palette LUT indices. The remainder of the structure spaces are captured by performing a uniform and iterative expansion away from each star space, capturing each uncaptured space encompassed by the expansion until all spaces are captured. The capturing of a space by a particular star corresponds to the entry of the capturing star value (color palette LUT index) into the inverse table at an address corresponding to the captured space. Using this type of iterative process, the inverse table is rapidly filled with color palette LUT indices, which, in turn, identify good approximations of the image data values by the color palette values in the LUT.
Inventors
- 👤 Stephen E. Carlsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 01:53
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/10
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
261 words
A method for generating an inverse table in a computer memory device for associating a large set of source values with a smaller set of destination values, each value in the source set having a binary representation of N components, the method including the steps of: (a) establishing an inverse table in a computer memory device, said inverse table having a number of inverse table entries addressable by a set of source values, wherein each of said source values is r-bits; (b) simulating an N-dimensional symmetrical structure in the computer memory device of size q, wherein q N =2 r , said N-dimensional symmetrical structure comprising spaces having space coordinates, each space coordinate corresponding to an inverse table address; (c) for each destination value of a set of destination values, identifying a star space associated with said destination value, termed star value, based on a relationship between said destination value and said associated star space; (d) initializing a unit counter N-dimensional symmetrical J; (e) until each space in said structure is captured: for each star space: (i) expanding out J spaces from said star space in each of 2N possible directions; (ii) capturing each uncaptured space encompassed by said expansion; and (iii) incrementing unit counter J and returning to substep (i); and (f) for each inverse table address, entering the star value that captured a space associated with said inverse table address, at substep (e)(ii), into said inverse table, whereby each source value is associated with a destination value that is an approximation to said source value based on said relationship.
Claim 2
Independent Claim
261 words
A method for generating an inverse table in a computer memory device for associating a large set of source values with a smaller set of destination values, each value in the source set having a binary representation of N components, the method including the steps of: (a) establishing an inverse table in a computer memory device, said inverse table having a number of inverse table entries addressable by a set of source values, wherein each of said source values is r-bits; (b) simulating an N-dimensional symmetrical structure in the computer memory device of size q, wherein q N =2 r , said N-dimensional symmetrical structure comprising spaces having space coordinates, each space coordinate corresponding to an inverse table address; (c) for each destination value of a set of destination values, identifying a star space associated with said destination value, termed star value, based on a relationship between said destination value and said associated star space; (d) initializing a unit counter N-dimensional symmetrical J; (e) until each space in said structure is captured: for each star space: (i) expanding out J spaces from said star space in each of 2N possible directions; (ii) capturing each uncaptured space encompassed by said expansion; and (iii) incrementing unit counter J and returning to substep (i); and (f) for each inverse table address, entering the star value that captured a space associated with said inverse table address, at substep (e)(ii), into said inverse table, whereby each source value is associated with a destination value that is an approximation to said source value based on said relationship.
Claim 3
Dependent Claim
45 words
A method as claimed in claim 1, wherein said relationship is a closest match relationship between said source values and said destination values, and said substep (c) includes the step of identifying for each destination value the source value that best approximates said destination value.
Claim 4
Dependent Claim
65 words
A method as claimed in claim 1, wherein said destination values are indices into a table of final values with which the source values will be associated, and said relationship is a closest match relationship between said source values and said final values, whereby said number of inverse table entries include destination values, each of which indexes an entry in said table of final values.
Claim 5
Dependent Claim
63 words
A method as claimed in claim 1, wherein said N-dimensional symmetrical structure and said inverse table are a single data structure in the computer memory device, and said substep (e)(ii) of capturing a space with a star value is performed in conjunction with said substep (f) of entering said star value into said inverse table at an address corresponding to said space coordinates.
Claim 6
Dependent Claim
48 words
A method as claimed in claim 1, wherein said step of capturing each uncaptured space includes the step of setting a capture flag for each space when it is captured, such that if said capture flag is set for a particular space, said space is no longer analyzed.
Claim 7
Dependent Claim
59 words
A method as claimed in claim 5, wherein said step of expanding out J spaces from said star space includes the step of determining whether each space encompassed by said expansion is beyond said N-dimensional symmetrical structure, such that said step of capturing each uncaptured space does not analyze any space determined to be beyond said N-dimensional symmetrical structure.
Claim 8
Dependent Claim
40 words
A method as claimed in claim 5, wherein if no spaces are captured at substep (e)(ii) in a given direction w for a given star u, then at substep (e)(i) for star u no expansion is performed in direction w.
Claim 9
Dependent Claim
15 words
A method as claimed in claim 1, wherein unit counter J is initialized to zero.
Claim 10
Dependent Claim
45 words
A method as claimed in claim 1, wherein unit counter J is initialized to an integer and at substep (c) said inverse table is initialized by entering a star value into said inverse table at an inverse table address corresponding to said identified star space.
Claim 11
Independent Claim
274 words
A method for generating an inverse table in a computer memory device for associating a set of image data values with a smaller set of color palette values, each image data value having a binary representation including N components, and each color palette value being associated with a color palette index, the method including the steps of: (a) establishing an inverse table in a computer memory device, said inverse table having a number of inverse table entries addressable by a set of image data values, wherein each of said image data values is r-bits; (b) simulating an N-dimensional symmetrical structure in the computer memory device of size q, wherein q N =2 r , said N-dimensional symmetrical structure comprising spaces having space coordinates, each space coordinate corresponding to an inverse table address; (c) for each color palette value, identifying a star space associated with said color palette value such that the inverse table address corresponding to said star space approximates said color palette value; (d) initializing a unit counter J; and (e) until each space in said N-dimensional symmetrical structure is captured: for each star space: (i) expanding out J spaces from said star space in each of 2N possible directions; (ii) capturing each uncaptured space encompassed by said expansion by entering index associated with the color palette value by which the star space was captured at an inverse table entry address corresponding to said captured space; and (iii) incrementing unit o r and returning to substep (i); whereby said inverse table is filled with color palette indices and can be used during a display process to generate indices into said color palette values.
Claim 12
Independent Claim
274 words
A method for generating an inverse table in a computer memory device for associating a set of image data values with a smaller set of color palette values, each image data value having a binary representation including N components, and each color palette value being associated with a color palette index, the method including the steps of: (a) establishing an inverse table in a computer memory device, said inverse table having a number of inverse table entries addressable by a set of image data values, wherein each of said image data values is r-bits; (b) simulating an N-dimensional symmetrical structure in the computer memory device of size q, wherein q N =2 r , said N-dimensional symmetrical structure comprising spaces having space coordinates, each space coordinate corresponding to an inverse table address; (c) for each color palette value, identifying a star space associated with said color palette value such that the inverse table address corresponding to said star space approximates said color palette value; (d) initializing a unit counter J; and (e) until each space in said N-dimensional symmetrical structure is captured: for each star space: (i) expanding out J spaces from said star space in each of 2N possible directions; (ii) capturing each uncaptured space encompassed by said expansion by entering index associated with the color palette value by which the star space was captured at an inverse table entry address corresponding to said captured space; and (iii) incrementing unit o r and returning to substep (i); whereby said inverse table is filled with color palette indices and can be used during a display process to generate indices into said color palette values.
Claim 13
Dependent Claim
15 words
A method as claimed in claim 10, wherein unit counter J is initialized to zero.
Claim 14
Dependent Claim
46 words
A method as claimed in claim 10, wherein unit counter J is initialized to an integer and at substep (c) said inverse table is initialized by entering a color palette index into said inverse table at an inverse table address corresponding to said identified star space.
References Cited (Backward Citations)
US4901258A
Cited
US5045967A
Cited
US4991122A
Cited
US5062058A
Cited
US4847677A
Cited
US5025249A
Cited
US5038300A
Cited
US4974070A
Cited
US5065147A
Cited
US5235677A
Cited
US4974171A
Cited
US5228120A
Cited
US5003494A
Cited
US5233684A
Cited
US5251298A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-01-23 | 1998-07-25 | 1999-01-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-01-23 | 2002-07-25 | 2003-01-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-01-23 | 2006-07-25 | 2007-01-24 | $7700.00 | Window Closed / Lapsed |