Data structure for efficient access to variable-size data objects

• US 6,502,097 B1
• Filed: 12/23/1999
• Issued: 12/31/2002
• Est. Priority Date: 12/23/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shum, Heung-Yeung, Chan, Shing-Chow
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): ALAUBAIDI, HAYTHIM J
• Application Number:
  US09/471,932
• Time in Patent Office: 1,104 Days
• Field of Search: 707/1, 707/3, 707/103, 707/100, 348/426
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06T 2207/20228 Disparity calculation for image-based rendering
• CPC Class Codes: G06T 7/97 Determining parameters from multiple pictures depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85

Abstract

A data structure includes variable-size data objects [“VSDOs”] and enables selective and efficient retrieval of data in particular VSDOs. The data structure includes multiple packets. Each packet includes a reference count field, a references field, and an objects field. The references field stores references to VSDOs within the data structure. The reference count field indicates the number of references stored in the references field. The objects field stores the actual VSDOs. To access a particular VSDO, an accessing unit traverses the reference count fields of the multiple packets until the accessing unit finds a packet that includes the reference to the particular VSDO. The accessing unit accesses the particular VSDO based upon the reference. To further improve the efficiency of an access operation, packets form metapackets. A metapacket header sums the reference count fields of the packets within the metapacket. To access a particular VSDO, an accessing unit traverses the metapacket headers until the accessing unit finds a metapacket that includes a packet having the reference to the particular VSDO. Based upon the reference, the accessing unit accesses the particular VSDO. Storing light field information in VSDOs using the data structure facilitates efficient light field operations and light field operations at selective levels of refinement.

Claims

1. A computer-readable medium having stored thereon a data structure for storing variable-size data objects, the data structure comprising one or more packets, a packet comprising:

a references data field containing data representing references to locations of variable-size data objects;

an objects data field containing data representing at least parts of one or more variable-size data objects; and

a reference count data field containing data representing a number k related to a number of references in the references data field, wherein during an access operation for a particular variable-size data object in the data structure, the number k in the reference count data field is examined to determine whether the references data field of the packet includes a reference to the location of the particular variable-size data object.

2. The computer-readable medium of claim 1 wherein the references data field precedes the objects data field, and wherein the reference count data field precedes the references data field.

3. The computer-readable medium of claim 1 wherein k is the number of references in the references data field of the packet.

4. The computer-readable medium of claim 1 wherein k is the total number of references in the references data fields of the packet and preceding packets in the data structure.

5. The computer-readable medium of claim 1 wherein the packet comprises n-bit units.

6. The computer-readable medium of claim 5 wherein n is a multiple of 8, whereby the packet is byte-aligned.

7. The computer-readable medium of claim 5 wherein the packet comprises 2ⁿ n-bit units, wherein each of the references in the references data field is a single n-bit unit.

8. The computer-readable medium of claim 1 wherein the packet length is m bits, and wherein a reference in the references data field is of length log₂(m).

9. The computer-readable medium of claim 1 wherein the reference count data field further contains error detection and/or error correction data.

10. The computer-readable medium of claim 1 wherein at least one reference in the references data field refers to a variable-size data object located at least partially within the packet.

11. The computer-readable medium of claim 1 wherein at least one reference in the references data field refers to a variable-size data object located within a second packet.

12. The computer-readable medium of claim 1 wherein the references data field further contains error detection data and/or error correction data.

13. The computer-readable medium of claim 1 wherein the references in the references data field comprise size values for variable-size data objects.

14. The computer-readable medium of claim 1 wherein the references in the references data field comprise pointers to locations within the data structure.

15. The computer-readable medium of claim 1 wherein the variable-size data objects include information for a light field image.

16. The computer-readable medium of claim 15 wherein light field image information is compressed.

17. The computer-readable medium of claim 1 wherein, if a variable-size data object only partially fits within the objects data field of the packet, the objects data field of the packet contains data representing part of a split variable-size data object, and the objects data field of a second packet contains data representing the remainder of the split variable-size data object.

18. The computer-readable medium of claim 17 wherein the references data field of the first packet includes a reference corresponding to the split variable-size data object, and wherein the number k in the reference count data field of the first packet counts said reference corresponding to the split variable-size data object.

19. The computer-readable medium of claim 18 wherein the references data field of the second packet lacks a reference corresponding to the split variable-size data object, and wherein the number k in the reference count data field of the second packet omits a count for a reference corresponding to the split variable-size data object.

20. The computer-readable medium of claim 1 wherein, if a reference to a variable-size data object fits within the references data field of the packet, but none of said variable-size data object fits within the objects data field of the packet, said reference to the variable-size data object comprises a null value, and the objects data field of a second packet contains data representing the entire variable-size data object.

21. The computer-readable medium of claim 20 wherein the references data field of the second packet lacks a reference corresponding to said entire variable-size data object.

22. The computer-readable medium of claim 1 wherein the data structure further comprises one or more metapackets, a metapacket comprising:

at least two packets; and

a header data field containing data representing a number j related to a total number of references within the references data fields of the packets of the metapacket.

23. The computer-readable medium of claim 1 wherein a composite data structure includes the data structure for storing variable-size data objects.

27. A method for accessing the particular variable-size data object stored in the data structure of claim 1, the method comprising:

receiving a numerical selection m, wherein m corresponds to the particular variable-size data object to be accessed;

retrieving the m^th reference of the data structure; and

accessing the particular variable-size data object based upon the retrieved reference.

28. A method for accessing the particular variable-size data object stored in the data structure of claim 1, the method comprising:

a) receiving a numerical selection m, wherein m corresponds to the reference to the particular variable-size data object to be accessed;

b) based at least in part upon the number k of the reference count data field of the packet, determining whether the packet contains the reference to the particular variable-size data object,

and if so, accessing the particular variable-size data object based upon the reference;

and if not, repeating act (b) using a next packet in the data structure as the packet.

29. The method of claim 28 wherein the determining comprises:

adding k to a cumulative reference count;

comparing m to the cumulative reference count;

if m is less than or equal to the cumulative reference count, retrieving the reference to the particular variable-size data object within the packet.

30. The method of claim 28 wherein the determining comprises:

comparing m to k;

if m is less than or equal to k, retrieving the reference to the particular variable-size data object within the packet;

wherein if m is greater than k, act (b) further comprises, before the repeating, setting m to equal m minus k.

31. A method for accessing the particular variable-size data object stored in the data structure of claim 22, the method comprising:

a) receiving a numerical selection m, wherein m corresponds to the reference to the particular variable-size data object to be accessed;

b) based at least in part upon the number of the header data field of the metapacket, determining whether the metapacket contains the reference to the particular variable-size data object,

and if so, accessing the particular variable-size data object based upon the reference;

and if not, repeating act (b) using a next metapacket in the data structure as the metapacket.

32. The method of claim 31 wherein the determining comprises:

adding j to a cumulative metapacket reference count;

comparing m to the cumulative metapacket reference count;

if m is less than or equal to the cumulative metapacket reference count, retrieving the reference to the particular variable-size data object within a references data field of a packet of the metapacket.

33. The method of claim 31 wherein the determining comprises:

comparing m to j;

if m is less than or equal to j, retrieving the reference to the particular variable-size data object within a references data field of a packet of the metapacket;

wherein if m is greater than j, act (b) further comprises, before the repeating, setting m to equal m minus j.

34. A method for filling the data structure of claim 1, the method comprising,

for each of the variable-size data objects, iteratively writing to the reference count data field, the references data field, and the objects data field.

35. A method of communicating the data structure of claim 1, the method comprising

formatting the variable-size data objects into the one or more packets in a transmitter, and

transmitting the one or more packets by the transmitter.

24. A computer-readable medium having stored thereon a data structure for storing variable-size data objects, the variable-size data objects including information for spatially related views of an object or scene, the data structure comprising one or more packets, a packet comprising:

a references data field containing data representing references to locations of variable-size data objects;

an objects data field containing data representing at least parts of one or more variable-size data objects, wherein the variable-size data objects include information for spatially related views of an object or scene; and

a reference count data field containing data representing a number k related to a number of references in the references data field, wherein during an access operation for a particular variable-size data object in the data structure, the number k in the reference count data field is examined to determine whether the references data field of the packet includes a reference to the location of the particular variable-size data object.

25. The computer-readable medium of claim 24 wherein the spatially related views are light fields.

26. The computer-readable medium of claim 24 wherein the spatially related views are surface textures.