Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-05-15
2001-12-04
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S182000, C345S215000, C345S440000, C707S793000, C707S793000, C382S232000
Reexamination Certificate
active
06326965
ABSTRACT:
The present invention is related to co-pending patent application Ser. No. 09/079,662, entitled “Interactive Retrieval and Caching of Multi-dimensional Data,” by Castelli et al., filed of even date herewith. This co-pending application and the present invention are commonly assigned to the International Business Machines Corporation, Armonk, NY. This co-pending application is hereby incorporated by reference in its entirety into the present application.
FIELD OF THE INVENTION
The present invention relates to information handling systems and in particular to the compression interactive retrieval of multi-dimensional data including but not limited to digital images, audio, video, and multi-dimensional lattice data.
BACKGROUND
Computer networks create powerful environments for the search and retrieval of distributed information. However, due to bandwidth limitations, computer networks are often not suited for interactively browsing large amounts of data. As a result, retrieving and displaying large images can be a slow process. Image compression is effective in reducing the amount of data for storing and transmitting images, however, most image compression algorithms are optimized for rate and distortion performance rather than to facilitate interactive image retrieval. The interactive retrieval of large images is a form of browsing in which the views of portions of the image data are successively retrieved in a drill-down or roll-up fashion.
Hierarchical data structures such as the wavelet packet tree, as taught by Coifman, et al., [Coifman, et al., 92], and the spatial quad-tree, as taught by Samet [Samet, 84], can be used to decompose images into a hierarchies of views. They use tree-based data structures to arrange the views of the image data into parent-child dependency relationships. The views of the images can be generated by decomposing the parent elements or by synthesizing together the children elements. Coifman, et al. taught a method for selecting the view elements in the wavelet packet tree in order to represent the image data completely and without information loss. Similar methods can be applied to the spatial quad-tree for representing the image data by a complete set of spatial segments.
In the wavelet packet tree, the view elements correspond to various spatial-frequency subbands. In particular, some of these subbands correspond to low-resolution views of the image data. However, none of the view elements in the wavelet packet tree correspond to spatial segments of the image data. On the other hand, the view elements in the spatial quad-tree correspond to various spatial segments of the image data, but only at full resolution.
The spatial quad-tree and wavelet packet tree can be integrated in a graph data structure as taught by Smith and Chang [Smith and Chang, 97]. The view elements in the space and frequency graph correspond to spatial segments of the various spatial-frequency subbands. Some of the view elements in the space and frequency graph correspond to the spatial segments of the low-resolution views of the image data. Smith and Chang developed a method for selecting the view elements in the space and frequency graph in order to optimize the compression of the image data in terms of rate-distortion performance. The method decomposes the image data into a redundant set of view elements, assigns each view element a compression cost and selects a complete and non-redundant set of view elements based on the compression costs. The selected view elements can be used to reconstruct the image data. However, Smith and Chang did not explore the use of the space and frequency graph for accessing or constructing the segmented multi-resolution views of the image data needed by applications that involve the interactive retrieval of the images.
The Flashpix image format has been used for progressively retrieving large images over the Internet using the Internet Imaging Protocol. The user-applications compose views of the images by retrieving tiles from the Flashpix files at the server [Eastman Kodak Co. 1996]. In order to speedup the retrieval of multi-resolution image views, the Flashpix-based servers store multiple versions of the image at different scales, which results in a redundancy of information of 133% [Burt and Adelson 1983]. The Flashpix format is also capable of storing the image non-redundantly, but, it then requires added processing to extract the image views. In both cases, the Flashpix-based systems do not reuse data at the client to reduce data transmission in drill-down or roll-up browsing.
There is benefit in storing the images in forms that allow the images to be rapidly browsed and retrieved by remote client applications in a drill-down fashion. Furthermore, there is added benefit of storing the data in a compressed form without adversely impacting the speed at which the image views are extracted or generated.
SUMMARY OF THE INVENTION
In accordance with the aforementioned needs, the present invention is directed towards an apparatus and method for ingesting, compressing and retrieving images and multi-dimensional lattice data. The invention has features that enable the following:
1. Compression: the data is decomposed into view elements, and a set of the view elements is selected, compressed, and stored to generate a compressed representation of the data.
2. Server-side view construction: the view elements are selectively retrieved from storage, decompressed, and processed to generate the views of the data.
3. Client-side progressive view construction: the client caches the view elements and processes them in combination with view elements retrieved from the server to generate views of the data.
The present invention has features for ingesting the data in units of spatial blocks and for performing the decomposition into view elements using the spatial block units. In general, the present invention has features for reading and writing the view elements and views in units of spatial blocks. These features enable the present invention to handle the ingestion, decomposition, compression, and view retrieval for large images using computer devices that have limited storage and processing capabilities.
An apparatus and method for representing and retrieving data using view elements utilizes a view element data structure that contains node and transition elements. An apparatus and method for representing and retrieving data using view elements places the view elements into the node elements of the data structure and defines transition elements of the data structure that indicate the methods for processing view elements in the view element data structure in order to generate other view elements in the data structured
An apparatus and method for representing and retrieving data using view elements can decompose the data in space or spatial-frequency to construct a tree-based hierarchy view element data structure.
An apparatus and method for representing and retrieving data using view elements can decompose the data jointly in space and spatial-frequency to construct a graph-based hierarchy view element data structure.
An apparatus for representing and retrieving data using the view elements indexes the view elements according to their position in the view element data structure.
An apparatus for representing and retrieving data using view elements makes a selection of view elements from the view element data structure in order to represent the data using view elements and to generate views of the data using view elements.
An apparatus for representing and retrieving data using view elements develops a program for processing the selected view elements in order to generate views and other view elements.
An apparatus for representing and retrieving data using view elements utilizes a client-side view element data structure and view element cache in order to enable the progressive and interactive retrieval, or drill-down and roll-up browsing of images over a computer network.
REFERENCES:
patent: 5384725 (1995-
Castelli Vittorio
Li Chung-Sheng
Smith John Richard
F. Chau & Associates LL
International Business Machines Corp.
Nguyen Kimbinh T.
Zimmerman Mark
LandOfFree
Interactive representation and retrieval of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interactive representation and retrieval of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive representation and retrieval of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2567585