Data structure for efficient access to variable-size data...

Details Data structure for efficient access to variable-size data... Data structure for efficient access to variable-size data...

1999-12-23

2002-12-31

Metjahic, Safet (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06502097

ABSTRACT:

TECHNICAL FIELD
The present invention pertains to storage, manipulation, and transmission of variable-size data objects. A data structure that stores variable-size data objects also facilitates efficient access to the variable-size data objects. In one use, the data structure stores light field information to facilitate selective and efficient access to the light field image information.
BACKGROUND OF THE INVENTION
Digital information can be represented as a series of data objects to facilitate processing and storing the digital information. For example, a digital audio or video file can be represented as a series of data objects that contain digital audio or video samples. More generally, a data object is an aggregation of digital information that is related along spatial, temporal, conceptual, or any other lines of significance.
When a series of data objects represents digital information, processing the series is simplified if the data objects are equal size. For example, suppose a video sequence of uncompressed, equal-size images is stored in a data structure. Using an ordinal number of an image in the video sequence, and knowing the size of images in the sequence, a particular image in the video sequence can be accessed as an offset from the beginning of the data structure.
Although access to equal-size data objects in a series is relatively straightforward, in some applications, use of equal-size data objects leads to inefficient storage and transmission. For example, when a video sequence is compressed, video frames may compress to varying sizes. By representing such digital information in variable-size data objects [“VSDOs”], storage and transmission is made more efficient.
Accessing a particular VSDO within a series of VSDOs is relatively complicated, however. Due to the variable sizes of the data objects preceding the VSDO to be accessed, the starting position of the VSDO to be accessed cannot be known based upon an ordinal series number. Thus, to access a VSDO, the VSDOs that precede the VSDO to be accessed must be traversed.
FIG. 3
shows a prior art data stream
100
for a compressed image. The data stream
100
starts with a header
110
. Blocks
120
of data, corresponding to entropy-coded, quantized transform coefficients for blocks of the image, follow the header
110
. The blocks
120
have variable length. Each block indicates its end with an end of block code
130
. After an end of block code
130
, the following block
120
begins. The data stream
100
ends with an end of stream code
140
.
Consider, for example, a decompression and display technique in which data in every block
120
of data stream
100
is accessed and decoded in order to display the compressed image in data stream
100
. Starting from the beginning of the data stream
100
, blocks
120
are accessed and decoded in a linear manner until the end of stream code
140
is reached. Although linear retrieval of blocks is time consuming, every block that is retrieved is also used. Similarly, if a video sequence is encoded into a data stream such as data stream
100
, each block of data is retrieved and used to display the video sequence.
In contrast, consider a light field rendering operation, which has different characteristics than a video display operation. In a light field rendering operation, light field samples dispersed throughout a light field are retrieved and processed to estimate a view from some arbitrary point in space.
A light field models the light characteristics of an object or static scene, for example, by capturing light intensity and color values along a surface around a static scene. To map a light field to a computational framework requires a discrete representation.
FIGS. 1 and 2
depict a discretized light field
10
. Light field
10
includes a set of spatially-related light field images of an object
20
.
FIG. 1
shows expanded views of light field images
12
and
14
. A light field image comprises a two-dimensional arrangement (s,t) of data values such as values from a color space. Light rays from the object
20
that pass through a light field image (s,t) also pass through a focal point
32
in the (u,v) plane. A (s,t,u,v) grid point is indexed with (i,j,p,q). Capture and generation of light fields, different parameterizations of light fields, and light field image rendering, as well as other aspects of light fields, are described in Gortler et al., “The Lumigraph,” Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 43-54 [“the Gortler reference”] and Levoy et al., “Light Field Rendering,” Computer Graphics Proceedings, Annual Conference Series, 1996, pp. 31-42 [“the Levoy reference”].
Storage and transmission of light fields present difficulties due to the amount of digital information in a typical light field. An illustrative light field consists of 16×16 focal points in the focal plane (u,v). If each light field image has a resolution of 256×256 and stores 24-bit RGB values, the total amount of storage is: 16×16×256×256×3 bytes=48 Mbytes. Compression of light field information can reduce the representation of the light field image information, usually at some cost to the quality of the information and the speed of accessing the information. Compression of light field information typically results in VSDOs.
In addition to the considerable storage and transmission requirements for a light field, manipulation of light field images presents considerable memory and processing requirements. Light field rendering is the process of creating a view of an object or static scene based upon a light field, e.g., by interpolating from known light field image values. During light field rendering, parts of selected light field images are retrieved to construct a view from a novel perspective. Depending on the perspective of the novel view being rendered, different light field images are retrieved. Because rendering typically uses different parts of different light field images according to a complex pattern of access, random access to parts of light field images facilitates rendering. Unfortunately, loading multiple light field images into random access memory (to facilitate random access to dispersed light field samples) consumes large amounts of memory given the size of a typical light field image. Moreover, even after light field images are loaded into memory, light field operations are computationally complex, especially when decompression of the light field information is required. These high memory and processing requirements hinder real time rendering, especially for serialized rendering operations.
To return to
FIG. 3
, suppose that during a light field rendering operation only the light field information in Block n
126
needs to be accessed. The starting point of block n
126
is not known in advance. The sizes of the blocks
120
preceding block n
126
are not known in advance. Even though only information in block n
126
is needed, it is necessary to start retrieving blocks in a linear manner from the beginning of the data stream
100
. This linear, sequential retrieval wastes resources because many blocks that are retrieved are not used in the rendering operation. This inefficiency is exacerbated when numerous non-sequential, dispersed light field samples must be retrieved. Furthermore, retrieval of block n
126
can be disrupted by corruption of the data preceding block n
126
in the data stream
100
.
SUMMARY OF THE INVENTION
The present invention pertains to efficient storage, manipulation, and transmission of digital information with variable-size data objects [“VSDOs”]. A data structure contains digital information in a series of VSDOs for efficient storage and transmission of the digital information. Using the data structure, particular VSDOs within the data structure are selectively, rapidly, and efficiently accessed. For example, using the data structure to store data for a light field data stream, selective portions of the data stream can be rapidly an

Affiliated with

Also associated with

Rating

Data structure for efficient access to variable-size data... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data structure for efficient access to variable-size data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for efficient access to variable-size data... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2953434