Memory organization and method for multiple variable digital data transformation

• US 5,684,981 A
• Filed: 01/18/1995
• Issued: 11/04/1997
• Est. Priority Date: 01/18/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jones, Arlin R.
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/375,096
• Time in Patent Office: 1,021 Days
• Field of Search: 395/109, 395/119, 395/127, 395/131, 395/138, 395/510, 395/516, 345/112, 345/153-155, 345/185-187, 345/189, 345/190, 345/199, 345/200, 358/518, 358/519, 358/523, 358/525, 358/455, 358/456, 382/162, 382/167, 364/723
• US Class Current: 345/566
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77

Abstract

A method and device for multidimensional data transformation is disclosed. A multidimensional, non-linear data memory storage construct provides simultaneous access to data in all dimensions without duplication of memory. For "n" dimensions, 2ⁿ locations describe the smallest subarea location in the multidimensional construct. Therefore, 2ⁿ memory banks are provided in which to store corresponding interpolation data. By recognizing that boundary points of the n-dimensions are common, duplication of memory is avoided by providing an addressing and sorting mechanism which allows interpolation of stored data correlated to the input data.

Claims

1. A device for transforming multiple variable, non-linear input data, where "n" is the number of variables, and for providing interpolated output data, comprising:

a set of 2ⁿ memory means, each having an input and an output, for storing transform data correlated to said input data at discrete addressable locations therein and for providing said transform data at each output;

address generating means, connected to each of said memory means'"'"' input, for receiving a first set of predetermined bits of said input data and for providing an address to access one location of each of said memory means per input access cycle in accordance with said first set of predetermined bits of said input data, said memory means providing accessed transform data at each output of said memory means, respectively;

sorting means for sorting said transform data, having

first input means, connected to each said memory means output, respectively, for receiving accessed transform data from said locations,

second input means connected to receive a first predetermined subset of said first set of predetermined bits of said input data such that said transform data is ordered in accordance with said first predetermined subset of said first set of predetermined bits of said input data, and

output means for outputting sorted transform data; and

interpolating means for interpolating said sorted transform data with a second set of predetermined bits of said input data, having

first input means, connected to said output means of said sorting means, for receiving said sorted transform data,

second input means connected to receive said second set of predetermined bits of said input data, and

output means for outputting interpolated output data based on interpolating said sorted transform data with said second set of predetermined bits of said input data.

2. The device as set forth in claim 1 wherein said memory means further comprise:

input means for receiving a signal determinative as to which variable of said input data multiple variables is to be transformed during a current input access cycle.

3. The device as set forth in claim 1, wherein said set of 2ⁿ memory means comprises:

means for emulating a n-dimensional spatial construct wherein said transform data is stored such that each correlated variable of said transform data can be accessed in one access cycle without duplication of said set of 2ⁿ memory means.

4. The device as set forth in claim 3, wherein said means for emulating a n-dimensional spatial construct further comprises:

a memory device emulating an array of polyhedral constructs, each polyhedral having 2ⁿ vertices and wherein each vertex has a designator representative of one said memory means.

5. The device as set forth in claim 4, further comprising:

each said memory device having a plurality of addressable locations representative of the vertices of said polyhedral construct wherein said transform data is stored at addressable locations such that all vertices of any polyhedral in said array can be accessed in parallel by accessing each memory device once during a single access cycle.

6. The device as set forth in claim 4, further comprising:

said addressable locations each containing a transform data word stored in a memory device which is addressable corresponding to its vertex designator such that any vertex can be retrieved simultaneously without conflict regardless of where in the n-dimensional space of the construct that vertex exists.

7. The device as set forth in claim 3, wherein n=3, said means for emulating a n-dimensional spatial construct further comprises:

eight memory banks having addressable locations representative of the eight vertices of a cube wherein said transform data is stored such that all eight vertices can be accessed in parallel by accessing each memory bank during a single access cycle.

8. The device as set forth in claim 3, said means for emulating a n-dimensional spatial construct further comprises:

a 4×

4×

4 cubic construct (n=3), each cube having eight vertices; and

each vertex is a designated as a separate memory bank "M", where M has the range 0-7, such that each diagonally adjacent cube has vertex designations mirroring its said diagonally adjacent cube,

whereby any vertex of said construct can be retrieved simultaneously without conflict.

9. The device as set forth in claim 8, wherein said input data is an eight bit digital data word for each said variable represented as X, Y and Z, said sorting means further comprises:

means for concatenation of said first set of predetermined bits of said input data in accordance with the function;

space="preserve" listing-type="equation">X(t,s,r)+X(q)&

|M(1), Y(t,s,r)+Y(q)&

|M(k), Z(t,s,r)+Z(q)&

|M(j),

where "t,s,r,q" are contiguous bits and "q" is the least significant bit and said first predetermined subset of said first set of predetermined bits of said input data, and where "l,k,j" are contiguous bits and "j" is the least significant bit of the memory bank number, M, of said set of memory banks.

10. The device as set forth in claim 8, wherein said input data is an eight bit digital data word for each said variable represented as X, Y and Z, said sorting means further comprises:

means for concatenation of said first set of predetermined bits of said input data in accordance with the function;

space="preserve" listing-type="equation">X(7,6,5)+X(4)&

|M(2), Y(7,6,5)+Y(4)&

| M(1), Z(7,6,5)+Z(4)&

|M(0).

11. A device for transforming a first three dimensional color space tristimulus color for a color represented by input data words X(m-1, m-2 . . . 0), Y(m-1, m-2 . . . 0), and Z(m-1, m-2 . . . 0), where m=a total number of bits of a data word, to a second three dimensional color space tristimulus color represented by output data words X'"'"'(m-1, m-2 . . . 0), Y'"'"'(m-1, m-2 . . . 0), and Z'"'"'(m-1, m-2 . . . 0), comprising:

an address generator, having input means and an output means, for receiving a first set of predetermined bits of a first three dimensional color space tristimulus color word via said input means and providing address signals on said output means;

a set of eight memory banks, each having

input means, selectively connected to said output means of said address generator for receiving address signals to access one location of each said memory bank per access cycle in accordance with said first set of predetermined bits;

addressable memory locations storing second three dimensional color space tristimulus color transform words correlated to said first three dimensional color space tristimulus color words;

output means for providing said second three dimensional color space tristimulus color transform words from said locations;

a sorter for sorting accessed location transform words, having

first input means, selectively connected to output means of said memory banks, for receiving said transform words,

second input means, connected to receive a first predetermined subset of said first set of predetermined bits such that said transform words are ordered in accordance with said first predetermined subset as sorted transform words, and

eight output means for outputting said sorted transform words; and

an interpolator for interpolating said sorted transform words with a second set of predetermined bits of said color word, having

eight first input means, connected to said sorter output means, respectively, for receiving said sorted transform words,

second input means, connected to receive said second set of predetermined bits of said color word, and

output means for providing said second three dimensional color space tristimulus color,

whereby said first three dimensional color space tristimulus color for a color represented by data words X(m-1, m-2 . . .

     0), Y(m-1, m-2 . . .

     0), and Z(m-1, m-2 . . .

     0) is transformed to a second three dimensional color space tristimulus color represented by data words X'"'"'(m-1, m-2 . . .

     0), Y'"'"'(m-1, m-2 . . .

     0), Z'"'"'(m-1, m-2 . . .

     0) which are interpolations of said stored second three dimensional color space tristimulus color transform words correlated to said first three dimensional color space tristimulus color words.

12. The device as set forth in claim 11 wherein each said memory banks further comprises:

an input for receiving a signal determinative as to which tristimulus color, X, Y or Z, is to be transformed during a current access cycle.

13. The device as set forth in claim 11, wherein said set of eight memory banks comprises:

means for emulating a three dimensional space construct wherein said transform words are stored such that each word of said transform data can be accessed in one access cycle without duplication of said set of eight memory banks.

14. The device as set forth in claim 13, wherein said means for emulating a three dimensional space construct further comprises:

said set of eight memory banks having addressable locations representative of an array of cubes construct of the eight vertices of a cube wherein said transform words are stored such that all eight vertices on any cubic construct can be accessed in parallel by accessing each memory bank during a single access cycle.

15. The device as set forth in claim 11, wherein said sorter further comprises:

means for concatenation of said first set of predetermined bits of said first three dimensional color space tristimulus color in accordance with the function;

space="preserve" listing-type="equation">X(t,s,r)+X(q)&

|M(1), Y(t,s,r)+Y(q)&

|M(k), Z(t,s,r)+Z(q)&

|M(j),

where "t,s,r,q" are contiguous bits and "q" is the least significant bit and said first predetermined subset of said first set of predetermined bits of said input data, and where "l,k,j" are contiguous bits and "j" is the least significant bit of the memory bank number "M" of said set of memory banks.

16. The device as set forth in claim 15 wherein said interpolator further comprises:

a tri-linear interpolator device.

17. A method for transforming multi-variable, non-linear input data represented by first words representative of each variable, where "n" represents the number of bits in each said first word to be transformed, to an interpolated output data, comprising:

storing second words in a retrievable manner wherein each said second word is a transformation data point correlated to an input data point color;

providing each first word with a predetermined set of bits, "a", where "a" is less than "n", defined as addressing and sorting bits and a predetermined set of data bits, "d", defined as a predetermined data point color;

using said first predetermined set of bits "a" to retrieve predetermined second words from storage locations designated by said predetermined set of bits "a" and to sort said stored second words into a logical order;

interpolating said predetermined second words using said data bits "d" and a non-linear transform based upon the number of variables; and

outputting interpolated second data words.

18. The method as set forth in claim 17, wherein said step of storing second words further comprises:

providing 2^x memories, where x equals the number of variables, each having predetermined second words stored in an organization such that no memory requires more than one access per input data transform event to retrieve said second word correlated to an input data point.

19. The method as set forth in claim 17, wherein said step of using said first predetermined set of bits "a" to retrieve predetermined second words from storage locations designated by said predetermined set of bits "a" and to sort said stored second words into a logical order further comprises:

concatenating a first predetermined subset of said first predetermined set of bits "a" with remaining bits of said first predetermined set of bits "a."

20. The method as set forth in claim 18, wherein said step of using said first predetermined set of bits "a" to retrieve predetermined second words from storage locations designated by said predetermined set of bits "a" and to sort said stored second words into a logical order further comprises:

selecting a first variable of said multi-variables to be transformed and retrieving those second words necessary to obtain a interpolated second data word correlated to said first variable.

21. The method as set forth in claim 20, further comprising:

repeating said step of selecting for each variable of said data to be transformed.

22. A method for transforming color space data from a first tristimulus space construct to a second tristimulus space construct wherein data point colors in each said construct are represented by words representative of a color, where "n" represents the number of bits in each said word, comprising:

storing second tristimulus space data point colors in an individually retrievable mode wherein said second tristimulus space data point colors are each defined as a data point color correlated to a particular first tristimulus space data point color;

providing each first tristimulus space word with a predetermined set of bits, "a", where "a" is less than "n", defined as addressing and sorting bits and a predetermined set of data bits, "d", defined as a predetermined first tristimulus space data point color;

using said first predetermined set of bits "a" to retrieve second tristimulus space data point colors correlated to particular first tristimulus space data point colors from storage locations designated by said predetermined set of bits "a" and to sort retrieved second tristimulus space construct data point colors into a logical order;

interpolating retrieved second tristimulus space data point colors using said data bits "d" and a tri-linear transform; and

outputting interpolated second tristimulus space data point colors.

23. The method as set forth in claim 22, wherein said step of storing said second tristimulus space data point colors further comprises:

providing a set of eight memory banks having said second tristimulus space data point colors are stored in an order such that no memory requires more than one access per transform event.

24. The method as set forth in claim 23, wherein said step of using said first predetermined set of bits "a" to retrieve second tristimulus space data point colors correlated to particular first tristimulus space data point colors from storage locations designated by said predetermined set of bits "a" and to sort retrieved second tristimulus space construct data point colors into a logical order, further comprises:

concatenating a first predetermined subset of said first predetermined set of bits "a" with remaining bits of said first predetermined set of bits "a".

25. The method as set forth in claim 22, wherein said step of using said first predetermined set of bits "a" to retrieve second tristimulus space data point colors correlated to particular first tristimulus space data point colors from storage locations designated by said predetermined set of bits "a" and to sort retrieved second tristimulus space construct data point colors into a logical order, further comprises:

selecting a first variable of said tristimulus color space to be transformed and retrieving those second tristimulus space construct data point colors necessary to obtain an interpolated second data word correlated to said first variable.

26. The method as set forth in claim 25, further comprising:

repeating said step of selecting for each variable of said data to be transformed.

27. The method as set forth in claim 24, wherein said step of concatenating a first predetermined subset of said first predetermined set of bits "a" with remaining bits of said first predetermined set of bits "a" further comprises:

concatenating said first set of predetermined bits of said first three dimensional color space tristimulus color in accordance with the function;

space="preserve" listing-type="equation">X(t,s,r)+X(q)&

|M(1), Y(t,s,r)+Y(q)&

|M(k), Z(t,s,r)+Z(q)&

|M(j),

where "t,s,r,q" are contiguous bits of said first tristimulus space word wherein "q" is the least significant bit and said first predetermined subset of said first set of predetermined bits of data, and where "l, k, j" are contiguous bits and "j" is the least significant bit of the memory bank number, M, of said set of eight memory banks.