Multimedia compression system with additive temporal layers

• US 6,392,705 B1
• Filed: 07/07/1997
• Issued: 05/21/2002
• Est. Priority Date: 03/17/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaddha, Navin
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US08/888,422
• Time in Patent Office: 1,779 Days
• Field of Search: 348/414, 348/417, 348/418, 348/388, 348/422, 348/405, 348/416, 348/413, 348/407, 348/412, 708/146, 375/240.24, 375/240.19, 375/240.11, 375/240.12
• US Class Current: 348/388.1
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/527 Global motion vector estimation

Abstract

A multimedia compression system for generating frame rate scaleable data in the case of video, and, more generally, universally scaleable data. Universally scaleable data is scaleable across all of the relevant characteristics of the data. In the case of video, these characteristics include frame rate, resolution, and quality. The scaleable data generated by the compression system is comprised of multiple additive layers for each characteristic across which the data is scaleable. In the case of video, the frame rate layers are additive temporal layers, the resolution layers are additive base and enhancement layers, and the quality layers are additive index planes of embedded codes. Various techniques can be used for generating each of these layers (e.g., Laplacian pyramid decomposition or wavelet decomposition for generating the resolution layers; tree structured vector quantization or tree structured scalar quantization for generating the quality layers). The compression system further provides for embedded inter-frame compression in the context of frame rate scalability, and non-redundant layered multicast network delivery of the scaleable data.

Claims

1. A data compression system, comprising:

a vectorizer configured to convert data into a series of data vectors;

a predictor configured to make a prediction of a current data vector based on at least one previous data vector, the predictor being coupled to the vectorizer for receiving the data vectors;

a segmentor configured to segment the current data vector into a plurality of sub-vectors based on the prediction, the segmentor being coupled to the predictor for receiving the prediction, wherein the segmentor utilizes quadtree decomposition; and

a hierarchical lookup table comprising a plurality of lookup tables, the hierarchical lookup table configured to map the plurality of sub-vectors to a set of codes by successive utilization of the plurality of lookup tables in stages so that one of the codes is generated in response to each of the sub-vectors, the hierarchical lookup table being coupled to the segmentor for receiving the plurality of sub-vectors.

5. The system of claim 1, wherein the at least one previous data vector is a neighboring data vector to the current data vector.

6. The system of claim 1, wherein the prediction is obtained through a prediction lookup table configured to map the at least one previous data vector to the prediction.

7. The system of claim 1, wherein the set of codes comprise codes of different lengths.

8. The system of claim 1, wherein the set of codes comprise non-embedded codes.

9. The system of claim 1, wherein the data vectors are blocks of pixels of an image represented by the data.

2. A data compression system, comprising:

a vectorizer configured to convert data into a series of data vectors;

a predictor configured to make a prediction of a current data vector based on at least one previous data vector, the predictor being coupled to the vectorizer for receiving the data vectors;

a segmentor configured to segment the current data vector into a plurality of sub-vectors based on the prediction, the segmentor being coupled to the predictor for receiving the prediction, wherein the plurality of sub-vectors comprise two sub-vectors of different sizes; and

a hierarchical lookup table comprising a plurality of lookup tables, the hierarchical lookup table configured to map the plurality of sub-vectors to a set of codes by successive utilization of the plurality of lookup tables in stages so that one of the codes is generated in response to each of the sub-vectors, the hierarchical lookup table being coupled to the segmentor for receiving the plurality of sub-vectors.

15. The system of claim 2, wherein the at least one previous data vector is a neighboring data vector to the current data vector.

16. The system of claim 2, wherein the prediction is obtained through a prediction lookup table configured to map the at least one previous data vector to the prediction.

17. The system of claim 2, wherein the set of codes comprise codes of different lengths.

18. The system of claim 2, wherein the set of codes comprise non-embedded codes.

19. The system of claim 2, where the data vectors are blocks of pixels of an image represented by the data.

3. In a computer system, a method of compressing data, comprising:

receiving data as input;

converting the data into a series of data vectors;

making a prediction of a current data vector based on at least one previous data vector,

segmenting the current data vector into a plurality of sub-vectors, wherein segmenting the current vector comprises quadtree decomposition; and

utilizing a hierarchical lookup table comprising a plurality of lookup tables, mapping the plurality of sub-vectors to a set of codes by successive utilization of the plurality of lookup tables in stages so that one of the codes is generated in response to each of the sub-vectors.

10. The method of claim 3, wherein the at least one previous data vector is a neighboring data vector to the current data vector.

11. The method of claim 3, further comprising obtaining the prediction through a prediction lookup table configured to map the at least one previous data vector to the prediction.

12. The method of claim 3, wherein the set of codes comprise codes of different lengths.

13. The method of claim 3, wherein the set of codes comprise non-embedded codes.

14. The method of claim 3, wherein the data vectors are blocks of pixels of an image represented by the data.

4. In a computer system, a method of compressing data, comprising:

receiving data as input;

converting the data into a series of data vectors;

making a prediction of a current data vector based on at least one previous data vector;

segmenting the current data vector into a plurality of sub-vectors, wherein the plurality of sub-vectors comprise two sub-vectors of different sizes; and

utilizing a hierarchical lookup table comprising a plurality of lookup tables, mapping the plurality of sub-vectors to a set of codes by successive utilization of the plurality of lookup tables in stages so that one of the codes is generated in response to each of the sub-vectors.

20. The method of claim 4, wherein the at least one previous data vector is a neighboring data vector to the current data vector.

21. The method of claim 4, further comprising obtaining the prediction through a prediction lookup table configured to map the at least one previous data vector to the prediction.

22. The method of claim 4, wherein the set of codes comprise codes of different lengths.

23. The method of claim 4, wherein the set of codes comprise non-embedded codes.

24. The method of claim 4, wherein the data vectors are blocks of pixels of an image represented by the data.