Video compression scheme using wavelets

• US 6,370,197 B1
• Filed: 07/23/1999
• Issued: 04/09/2002
• Est. Priority Date: 07/23/1999
• Status: Expired due to Term

• Current Assignee: Mind Fusion, LLC (Ascend Innovation Management, LLC)
• Original Assignee: Memorylink Corporation
• Inventors: Stocker, Kenneth Alan, Clark, Derek Rand, Roberts, Teddy Paul, Schafer, Lucinda Ellen
• Primary Examiner(s): BRITTON, HOWARD W
• Application Number:
  US09/360,388
• Time in Patent Office: 991 Days
• Field of Search: H04/N.730, 375/240.19, 375/240.11, 382/248, 708/203, 708/400, 708/401, 709/247
• US Class Current: 375/240.19
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

Data elements, preferably representative of video data, are logically divided into blocks. In a bit-wise fashion, each block is inspected to determine whether the data elements for that block may be represented in a highly compact format. If a given block may not be represented in this manner, it is sub-divided into blocks having smaller dimensions. This process of identifying suitable blocks and sub-dividing is recursively repeated until minimum block dimensions are reached. The same result may be achieved through the use of a plurality of ascending tables that are constructed by repetitively forming tables of reduced data elements. The plurality of ascending tables is traversed and, based on the reduced data elements, blocks of data are identified that are susceptible to the highly compact format. Wavelet transforms are preferably used to provide video data to be compressed.

Claims

1. A method of processing video data for compression, the method comprising steps of:

(A) providing the video data as input data, each data element of the input data being represented by a predetermined number of bits; and

(B) for at least one bit position of a plurality of bit positions representative of the predetermined number of bits;

(i) grouping data elements of the input data to provide a plurality of data blocks each having block dimensions smaller than the input data;

(ii) when all data elements of the data block comprise a first bit value at the bit position, outputting the first bit value as representative of all data elements of the data block at the bit position; and

(iii) when any data element of the data block comprises a second bit value at the bit position, outputting the second bit value and recursively treating each data block of the plurality of data blocks as the input data in accordance with steps (i) through (iii) until minimum block dimensions are reached.

2. The method of claim 1, wherein step (B) further comprises a step of:

(iv) when the minimum block dimensions are reached, outputting, for each data block of the plurality of data blocks, a data bit representative of each data element of the data block at the bit position.

3. The method of claim 2, wherein step (B)(iv) further comprises steps of:

(a) when the data bit representative of the data element comprises the second bit value and when a tag bit corresponding to the data element is not set, for each data element of the data block, outputting a sign bit corresponding to the data element; and

(b) setting the tag bit corresponding to the data element.

4. The method of claim 1, further comprising steps of:

(C) identifying a maximum data element having greatest magnitude in the video data;

(D) determining a most significant bit of the maximum data element that is set to the second bit value to identify a log bit position; and

(E) outputting data representative of the log bit position.

5. The method of claim 4, wherein the plurality of bit positions are treated in order from the log bit position to a least significant bit position.

6. The method of claim 1, wherein the minimum block dimensions correspond to 2×

2 blocks.

7. The method of claim 1, wherein the video data comprises wavelet coefficients resulting from wavelet transform of any one of luma data, chroma red data and chroma blue data.

8. The method of claim 1, wherein the data elements are represented in signed magnitude format.

9. The method of claim 1, wherein the first bit value is a binary zero value and the second bit value is a binary one value.

10. A method of processing data for decompression to provided decompressed video data, the method comprising steps of:

(A) providing a data storage area as an output storage area, each data element of the data storage area being represented by a predetermined number of bits;

(B) receiving compressed video data to provided received bits;

(C) for at least one bit position of a plurality of bit positions representative of the predetermined number of bits;

(i) grouping data elements of the output storage area to provide a plurality of data blocks each having block dimensions smaller than the output storage area;

(ii) when one of the received bits, corresponding to a data block of the plurality of data blocks, comprises a first bit value, storing the first bit value in each data element of the data block at the bit position;

(iii) when one of the received bits, corresponding to a data block of the plurality of data blocks, comprises a second bit value recursively treating the data block as the output storage area in accordance with steps (i) through (iii) until minimum block dimensions are reached.

11. The method of claim 10, wherein step (C) further comprises a step of:

(iv) when a data block of the plurality of data blocks has the minimum block dimensions, storing, in each data element of the data block, a corresponding one of the received bits at the bit position.

12. The method of claim 11, wherein step (C)(iv) further comprises a step of:

(a) for each data element of the data block, when the corresponding one of the received bits comprises the second bit value and when a tag bit corresponding to the data element is not set, storing a subsequently received one of the received bits as a sign bit corresponding to the data element; and

(b) setting the tag bit corresponding to the data element.

13. The method of claim 10, wherein the received bits comprise data representative of a log bit position, the log bit position indicative of a most significant bit of the data elements of the data storage area that is to be set to the second bit value.

14. The method of claim 13, wherein the plurality of bit positions are treated in order from the log bit position to a least significant bit position.

15. The method of claim 10, wherein the minimum block dimensions correspond to 2×

2 blocks.

16. The method of claim 10, wherein the decompressed video data comprises wavelet coefficients resulting from wavelet transform of any one of luma data, chroma red data and chroma blue data.

17. The method of claim 10, wherein the data elements are represented in signed magnitude format.

18. The method of claim 10, wherein the first bit value is a binary zero value and the second bit value is a binary one value.

19. A method of processing video data for compression, wherein the video data has been processed via a discrete wavelet transform to provide wavelet coefficients, the method comprising steps of:

(A) storing the wavelet coefficients as data elements in a level 0 table, each wavelet coefficient being represented by a predetermined number of bits and the level 0 table forming a portion of a plurality of ascending tables;

(B) constructing other tables of the plurality of ascending tables by performing steps of, for J=1 to K;

(i) grouping the data elements from the level (J−

1) table to provide a plurality of data element blocks;

(ii) for each data element block of the plurality of data element blocks, forming a reduced data element by bitwise logically OR'"'"'ing the data elements forming the data element block, wherein the data elements of the data element block are children of the reduced data element; and

(iii) storing the reduced data elements in a level (J) table of the plurality of ascending tables.

20. The method of claim 19, wherein each data element block of the plurality of data element blocks comprises a 2×

2 block.

21. The method of claim 19, wherein the video data comprises at least one of luma data, chroma red data and chroma blue data.

22. The method of claim 19, wherein the wavelet coefficients are represented in signed magnitude format.

23. The method of claim 19, wherein the wavelet coefficients comprise a tag bit.

24. The method of claim 19, further comprising steps of:

(C) identifying a maximum wavelet coefficient having greatest magnitude in the level 0 table;

(D) determining a most significant bit of the maximum wavelet coefficient that is set to a binary one value to identify a log bit position; and

(E) outputting data representative of the log bit position.

25. The method of claim 24, further comprising steps of:

(F) performing at least one descending tree search on the plurality of ascending tables, wherein each descending tree search uniquely corresponds to a bit position of a plurality of bit positions inclusively between the log bit position and a least significant bit position.

26. The method of claim 25, wherein each descending tree search further comprises a step of:

(i) traversing the plurality of ascending tables and identifying a binary value of each data element of the plurality of ascending tables at the bit position and outputting compressed data in accordance with steps of;

(a) when a binary zero value is identified for a data element in the level 0 table, outputting a binary zero value representative of the data element at the bit position;

(b) when a binary one value is identified for a data element in the level 0 table, outputting a binary one value representative of the data element at the bit position;

(c) when a binary zero value is identified for a data element in the level (J) table for any J=1 to K, outputting a binary zero value representative of all descendants of the data element at the bit position, and thereafter skipping the step of identifying for all descendants of the data element at the bit position; and

(d) when a binary one value is identified for a data element in the level (J) table for any J=1 to K, outputting a binary one value and recursively treating the children of the data element in accordance with steps (a) through (d).

27. The method of claim 26, wherein step (i)(b) further comprises steps of:

(1) when a tag bit corresponding to the data element is not set, outputting a sign bit corresponding to the data element; and

(2) setting the tag bit corresponding to the data element.

28. The method of claim 25, wherein the bit position is initially the log bit position and is decremented for each successive descending tree search.

29. The method of claim 27, further comprising steps of:

(G) providing a plurality of decoded ascending tables comprising decoded level (J) tables for J=0 to K, each data element of the plurality of decoded ascending tables being represented by a predetermined number of bits;

(H) receiving the compressed data and the data representative of the log bit position; and

(I) populating the plurality of decoded ascending tables by performing at least one descending tree decoding based on the compressed data, wherein each descending tree decoding uniquely corresponds to a decoded bit position of a plurality of bit positions inclusively between the log bit position and a least significant bit position.

30. The method of claim 29, wherein each descending tree decoding further comprises a step of:

(J) traversing the plurality of decoded ascending tables and storing in each data element of the plurality of decoded ascending tables, at the decoded bit position, a binary value of the compressed data in accordance with steps of;

(i) when a binary zero value is identified from the compressed data and a data element from the level 0 table is to be populated, storing a binary zero value in the data element at the decoded bit position;

(ii) when a binary one value is identified from the compressed data and a data element from the decoded level 0 table is to be populated, storing a binary one value in the data element at the decoded bit position;

(iii) when a binary zero value is identified from the compressed data and a data element in the decoded level (J) for J=1 to K is to be populated, storing a binary zero value, at the decoded bit position, in all descendants in the decoded level 0 table of the data element and thereafter skipping the step of storing, at the decoded bit position, for all descendants of the data element; and

(iv) when a binary one value is identified from the compressed data and a data element in the decoded level (J) for J=1 to K is to be populated, storing a binary one value, at the decoded bit position, in the data element and recursively treating the children of the data element in accordance with steps (i) through (iv).