Video compression and decompression using dynamic quantization and/or encoding

• US 6,249,614 B1
• Filed: 03/06/1998
• Issued: 06/19/2001
• Est. Priority Date: 03/06/1998
• Status: Expired due to Fees

• Current Assignee: XVD Technology Holdings Ltd.
• Original Assignee: Alaris, Inc., GT Technologies
• Inventors: Taubin, Felix A., Simileysky, Victor, Malkov, Andrey, Marsavin, Andrey, Kolesnik, Victor D., Kudryashov, Boris D., Bocharova, Irina E.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/036,883
• Time in Patent Office: 1,201 Days
• Field of Search: 382/251, 382/239, 382/238, 382/236, 382/240, 382/44-45, 382/232, 382/250, 382/248, 382/246, 348/405, 375/240.03, 375/240.11, 375/240.19, 375/240.23, 375/240.12, 375/240.22, 375/240.16, 375/240.25, 375/240.2, 375/240.24, 375/240.04, 341/50-51, 341/67, 341/65, 341/61, 358/433, 358/432, 358/402, 358/426
• US Class Current: 382/251
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A method and apparatus for performing video compression and decompression using dynamic quantization and/or encoding. According to one aspect of the compression method, an image is recursively filtered into its constituent components each represented by a matrix of coefficients. Next, the level of correlation of a first of the matrices of coefficients is determined. Based on the level of correlation of this first coefficient matrix, one of a first quantization technique and a second quantization technique is selected. The first coefficient matrix is then quantized using the selected quantization technique.

According to another aspect of the compression method, an image is digitally filtered into its constituent components, each represented by a matrix of coefficients. At least certain matrices are quantized to generated a first quantized matrix. The first quantized matrix is then recursively divided until the first quantized matrix or each of the resulting submatrices is sufficiently dense or sufficiently sparse. Each of the sufficiently dense matrices are encoded using a first technique, while each of the sufficiently sparse matrices are encoded a second technique.

Claims

1. A computer-implemented method of compressing image data comprising:

recursively filtering an image into its constituent components each represented by a matrix of coefficients;

determining a level of correlation of a first matrix coefficients;

selecting one of a first quantization technique and a second quantization technique as a selected quantization technique based on the level of correlation;

quantizing the first matrix of coefficients using the selected quantization technique to generate a first quantized matrix of coefficients;

upon selection of the second quantization technique, dividing the first quantized matrix until the first quantized matrix or each submatrices is sufficiently dense, sufficiently sparse or sufficiently small;

determining a number of significant elements in the first quantized matrix of coefficients;

selecting one of a plurality of coding techniques based on the number of significant elements; and

coding the first quantized matrix of coefficients using the selected coding technique.

2. A computer-implemented method of compressing image data comprising:

recursively filtering an image into its constituent components each represented by a matrix of coefficients;

determining a level of correlation of a first matrix coefficients;

selecting one of a first quantization technique and a second quantization technique as a selected quantzation technique based on the level of correlation;

quantizing the first matrix of coefficients using the selected quantization technique to generate a first quantized matrix of coefficients;

upon selection of the second quantization technique, dividing the first quantized matrix until the first quantized matrix or each submatrices is sufficiently dense, sufficiently sparse or sufficiently small;

encoding sufficiently dense matrices using a first technique;

encoding sufficiently sparse matrices using a second technique;

during said dividing another condition under which the first quantized matrix or a submatrices is not further divided is when that matrix is representable by a zero matrix; and

said method includes encoding matrices, representable by zero as zero matrices.

3. A method for compressing image data comprising:

recursively filtering an image into at least a first and second matrix of coefficients;

quantizing the first and second madix of coefficients using different quantization techniques;

determining a number of significant elements in the first quantized matrix of coefficients;

selecting one of a plurality of coding techniques based on the number of significant elements;

coding the fist quantized matrix of coefficients using the selected coding technique; and

coding the second quantized matrix of coefficients.

4. The method of claim 3, further comprising:

determining a level of correlation for each of the first and second matrix of coefficients;

selecting differential quantization for the first matrix of coefficients based on the level of correlation determined for the first matrix of coefficients; and

selecting hierarchical quantization for the second matrix of coefficients based on the level of correlation determined for the second matrix of coefficients.

5. The method of claim 3, wherein recursively filtering includes performing one or more wavelet decompositions.

6. The method of claim 5, wherein the first matrix of coefficients is a lower frequency component than said second matrix of coefficients.

7. The method of claim 3, wherein quantizing the first and second matrix of coefficients using different quantization techniques includes:

differentially quantizing the first matrix of coefficients; and

hierarchically quantizing the second matrix of coefficients.

8. The method of claim 7, wherein differentially quantizing includes:

performing a two dimensional differential quantization.

9. The method of claim 7, wherein hierarchically quantizing includes:

dividing the second matrix of coefficients into submatrices until each submatrix can either be replaced by a zero submatrix or is sufficiently small;

replacing all submatrices that can be replaced by zero submatrices; and

quantizing all submatrices that are not replaceable by zero submatrices.

10. The method of claim 7, wherein:

the method further includes determining a quantization step size; and

quantizing all submatrices that are not replaceable by zero submatrices is performed using the quantization step size.

11. The method of claim 10, determining the quantization step size includes determining the quantization step size as a function of the energy represented in the second matrix of coefficients.

12. The method of claim 9, wherein dividing includes:

dividing the second matrix of coefficients into submatrices;

for each submatrix, performing;

determining a energy level of the submatrix;

if the energy level of the submatrix is sufficiently low, then determining the submatrix can be replaced; and

if the energy level of the submatrix is not sufficiently low, then recursively dividing the submatrix into smaller submatrices until each submatrix can either be replaced or is of a sufficiently small size.

13. The method of claim 3, wherein said coding the first quantized matrix of coefficients further comprises:

dividing the first quantized matrix until the first quantized matrix or each submatrices is sufficiently dense, sufficiently sparse, or sufficiently small;

encoding sufficiently dense matrices using a first coding technique;

encoding sufficiently sparse matrices using a second coding technique.

14. The method of claim 13, wherein:

during said dividing another condition under which the first quantized matrix or a submatrices is not further divided is when that matrix is representable by a zero matrix; and

said method includes encoding matrices, representable by zero as zero matrices.

15. The method of claim 13 wherein said encoding sufficiently dense matrices includes performing a huffman code.

16. The method of claim 13 wherein said encoding sufficiently sparse matrices includes performing combinatorial coding.

17. A computer-inmplemented method of compressing image data, said method comprising:

digitally filtering an image into its constituent components each represented by a matrix of coefficients;

quantizing at least certain coefficients of a first matrix to generate a first quantized matrix;

dividing the first quantized matrix until the first quantized matrix or each submatrices is sufficiently dense, sufficiently sparse, or sufficiently small;

encoding sufficiently dense matrices using a first technique;

encoding sufficiently sparse matrices using a second technique;

during said dividing another condition under which the first quantized matrix or a submatrices is not further divided is when that matrix is representable by a zero matrix; and

said method includes encoding matrices, representable by zero as zero matrices.

18. A method of compressing a quantized matrix representing image data, said method comprising:

determining which of a plurality of sets of elements includes significant elements, wherein sets in the plurality of sets of elements are either rows or columns of the quantized matrix;

encoding how the significant elements are distributed over the plurality of sets of elements;

encoding values and positions of the significant elements in the plurality of sets of the elements that contain significant elements, wherein said encoding values and positions of the significant elements in the plurality of sets of elements include encoding positions and values of significant elements in a first and second of the plurality of sets of elements using different techniques based on the number of significant elements in the first and second sets.

19. The method of claim 18 further including preliminarily:

determining the number of columns and rows that contain significant elements;

selecting either the columns or rows to form the plurality of sets of elements based on how many columns and how many rows contain significant elements.

20. The method of claim 18, wherein said encoding which of the plurality of sets of elements containing significant elements includes:

generating a binary vector identifying the positions of either columns or rows that contain significant elements; and

combinatorily encoding the binary vector.

21. The method of claim 18, wherein said encoding how the significant elements are distributed over the plurality of sets of elements includes:

generating a binary distribution vector with ones on positions with numbers equal to the significant element number of each set.

22. The method of claim 18, wherein said encoding data identifying values and positions includes:

encoding the positions and values of the significant elements in the plurality of sets of elements, separately.

23. The method of claim 22, wherein said encoding the values and positions of the significant elements in the plurality of sets of elements separately include:

generating a binary vector for a first of the plurality of sets of elements, said binary vector identifying positions of significant elements in the first set;

combinatorily encoding the binary vector.

24. The method of claim 18, wherein said encoding values and positions of the significant elements in the plurality of sets of elements include:

encoding positions and values of significant elements in a first and second of the plurality of sets of elements using different techniques based on the number of significant elements in the first and second sets.