Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-01-29
2001-04-24
Amsbury, Wayne (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C345S419000
Reexamination Certificate
active
06223183
ABSTRACT:
This application is related to patent application Ser. No: 09/079,986 now U.S. Pat. No. 6,014,671 entitled “Interactive Retrieval and Caching of Multi-dimensional Data,” by Castelli et al., IBM Docket No. YO998191 and to co-pending patent application Ser. No. 09/079,662 now pending entitled “Interactive Representation and Retrieval of Multi-dimensional Data Using View Elements,” by Castelli et al., IBM Docket No. YO998191.
FIELD OF THE INVENTION
The present invention relates generally to a method for describing and indexing views of multi-dimensional lattice data such as images, video and audio in space, time, frequency and resolution; and further to a method for describing aggregate sets of the views to form tilings, partitionings and hierarchical decompositions of the multi-dimensional lattice data. The present invention also relates to the use of space and frequency view descriptions to provide an abstraction layer between stored/compressed data and multimedia applications; to provide a view description interface for audio-visual content description schemes; for communicating view requests and descriptions between client and server in image, video, and audio retrieval applications; to describe multi-dimensional shapes in terms of sets of views; to add annotations and meta-data to images, video and audio in order to specify information about locations, sizes and resolutions of regions, objects and segments in space, time, frequency and resolution, and to specify the construction of feature descriptors that utilize statistical measures computed from regions in space, time, frequency and resolution.
BACKGROUND OF THE INVENTION
Multimedia search, retrieval and filtering applications need a standard reference system to specify regions, locations and sizes along the dimensions of space, time, resolution, and frequency. For example, this requirement is being addressed by MPEG-7, which is standardizing the interface for multimedia content search and retrieval. The objective of MPEG-7 is to improve the ability by which audio-visual content is indexed, searched, browsed, filed and filtered in a large number of multimedia storage and retrieval applications.
The audio-visual search and filtering applications need to deal with the dimensions of space, time, resolution, and frequency explicitly, such as when referring to spatial regions of images, temporal units of video, low-resolution versions of images, or frequency bands of audio. The applications also need to be able to refer to regions and locations in space, time, resolution and frequency without concern for the underlying storage and compression formats for the image, video and audio data. The applications need this higher-level interface to insulate them from the specific details of the data bit-streams and view extraction methods. In order to enable this abstraction, a description scheme is needed for specifying location, size and division along the dimensions of space, time, frequency and resolution as they pertain to the image, video and audio data, and for relating the views of the data with the data storage formats.
Independent of the compression and storage formats, digital multimedia content such as images, video and audio has an inherent lattice structure. For example, image data consists of pixels which are samples on a 2-D spatial grid. Similarly, audio and video data consists of samples in time, or in space and time, respectively. Spatial and temporal views, such as spatial quadrants of an image or temporal segments of video, correspond to the data in parts of the lattice. Frequency views, such as low-resolution images, wavelet subbands, or temporal-frequency channels, correspond to segments of the data after having been transformed into the frequency domain. Together, the notion of segmentation in space and frequency permits the development of a general notion of views of lattice date as follows: a view is a region in multi-dimensional space (including time) and multi-dimensional frequency (including resolution) that has location and size. Since audiovisual applications need to deal with views all the time, a description scheme is needed to describe views.
Previously, methods have been developed for describing regions of images. The TIFF image format provides the aide to specify tiling of images in space, as described in the TIFF Revision 6.0 by the Adobe Developers Association (Jun. 23, 1992). In the TIFF image format, each tile corresponds to a rectangular region of the image. In another approach, the Flashpix image format provides the ability to specify tiling of images at a finite number of resolutions, as detailed by Eastman Kodak Company authors in “FlashPix Formal and Architecture White Paper” (Jun. 17, 1996). Each Flashpix tile corresponds to a rectangular region of the image at a particular resolution. More general tilings can have location and size in space and frequency as demonstrated in the space and frequency graph, as taught by J. R Smith and S. -F. Chang, in “Space and Frequency Adaptive Wavelet Packets”, Proc. IFEP. Intern. Conf on Acoustics, Speech and Signal Proc., ICASSP-95, Detroit, Mich., (May 1995) and in “Joint Adaptive Space and Frequency Basis Selection”, Proc. IEEE Intern. Conf on Image Processing, ICIP-97, Santa Barbara, Calif., (October 1997). In the space and frequency graph, each view element corresponds to a multi-dimensional rectangular region in space and frequency that corresponds to the data of the image belonging to a spatial region and a frequency range.
While these examples illustrate specific types of decompositions of image and video data, they do not provide a general system for describing views produced by decompositions in space and frequency. A system is needed in order to enable interoperability between image and video systems in dealing with a diversity of decompositions and views of the data
SUMMARY OF THE INVENTION
In accordance with the aforementioned needs, the present invention is directed towards a method for uniformly describing space and frequency views of multidimensional lattice data, including regions, tilings and hierarchical decompositions of image, video, audio content, and time series data in space, time, frequency and resolution. The space and frequency view description scheme provides a way to specify regions in space, time, frequency and resolution in term of space and frequency views. This allows specification of concepts such as “half resolution”, “upper right quadrant” or “high pass band”, such as when referring to views of an image. The space and frequency view description scheme also provides a way to index these view, which is important in applications of progressive retrieval in which a client application can send requests for views of images stored at a server in terms of an index value. The space and frequency view description scheme handles the details concerning the access and relationship of views with different resolutions, spatial locations and sizes.
The invention, by providing a uniform description scheme, provides an abstraction layer between image, video and audio description schemes and multimedia applications and the stored, compressed data, which then allows the data to be referenced and accessed in terms of space and frequency views. Furthermore, the invention provides for the creation and use of a view indexing system using a space and frequency graph (SFGraph) data structure. View requests and descriptions between client and server in retrieval applications can then be communicated using the inventive description scheme, and, multidimensional shapes can be described in terms of sets go of views. Moreover, attributes to objects, annotations, meta-data and descriptors that specify information about locations, sizes, and regions in space, time, frequency and resolution can be added using the invention; and the derivation of descriptors that utilize statistical measures computed from regions in space, time, frequency and resolution can be specified.
REFERENCES:
patent: 5384725 (1995-01-01), Coifman et al.
patent: 5555409 (1996-09-
Li Chung-Sheng
Smith John R.
Amsbury Wayne
Coby Frantz
Dougherty Anne Vachon
Ellenbogen Wayne L.
International Business Machines - Corporation
LandOfFree
System and method for describing views in space, time,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for describing views in space, time,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for describing views in space, time,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549416