Method of compressing digital images

• US 20020172418A1
• Filed: 05/16/2001
• Published: 11/21/2002
• Est. Priority Date: 02/21/2001
• Status: Active Grant

• Current Assignee: BOLY Media Holdings Company Limited
• Original Assignee: BOLY Media Holdings Company Limited
• Inventors: Hu, Xiaoping
• Granted Patent: US 6,823,082 B2
• Time in Patent Office: Days
• US Class Current: 382/166
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A method of compressing digital representations of images stores the images in multiple subsampling quality scales in a progressive manner such that a higher quality scale contains only data incremental to the data in an adjacent lower quality scale. The data in each quality scale is transformed, quantized, and entropy encoded. A discrete wavelet cosine transformation combining frequency transformation features of a discrete cosine transformation and spatial transformation features of a wavelet transformation is provided. Sequences of subsampling quality scales are provided for multi-scale representations of images. A novel context selection method is used which treats color components and coefficients of different positions differently. An image compressed in a given quality scale can be transmitted or decompressed progressively allowing progressive downloading or transmission over the Internet.

Claims

1. A method of compressing a digital representation of an image into a one-dimensional bitstream, the digital representation comprising a two-dimensional array of pixels wherein a primary color component and secondary color components are associated with each pixel, the method comprising:

representing the image in a series of quality scales of progressively decreasing quality, wherein a higher quality scale comprises more data than a lower quality scale, and wherein lower quality scales are formed from higher quality scales by decreasing the number of stored color components or by decreasing the number of pixels;

representing the image in terms of quality scales in terms of a base quality scale image and differential images wherein a differential image at a given quality scale is the difference between the image at the given quality scale and a representation of the image scaled up from a reconstructed representation at the adjacent lower quality scale, the reconstructed representation determined by a process comprising;

transforming the image into a set of coefficients associated with known functions,

quantizing the set of coefficients by dividing by quantization values and rounding to integer values,

dequantizing the set of quantized coefficients by multiplying by the quantization values, and

performing the inverse transform associated with the known functions to produce a reconstructed representation;

representing the base quality scale image and the differential images as integer values by a process comprising transforming to a set of coefficients associated with known functions and quantizing the set of coefficients by dividing by quantization values and rounding to integer values; and

encoding the integer values corresponding to the lowest quality scale and the differential images by a lossless ordered statistics encoding process to produce a one-dimensional bitstream.

2. The method of claim 1 wherein the primary color component is green and the secondary color components are red and blue.

3. The method of claim 1 wherein the primary color component is luminance and the secondary color components are chrominances.

4. The method of claim 1 wherein the series of quality scales comprises quality scales selected from the group consisting of a first quality scale wherein all color components are present at each pixel;

a second quality scale wherein the primary color component and one secondary color component are present at each pixel;

a third quality scale wherein a primary color component is present at each pixel and quadruple as many primary color components as each secondary color component are present;

a fourth quality scale wherein one color component is present at each pixel and twice as many primary components as secondary components are present;

a fifth quality scale derived from the first quality scale by reducing the number of pixels in the horizontal direction and in the vertical direction by dividing each dimension by an integral factor;

a sixth quality scale derived from the fourth quality scale, wherein the primary color component and one secondary color component are present at each pixel; and

a sixth quality scale derived from the fourth quality scale, wherein a primary color component is present at each pixel and quadruple as many primary color components as each secondary color component are present.

5. The method of claim 1 wherein transforming to a set of coefficients associated with known functions is applying a two-dimensional transform, the two-dimensional transform combining frequency transform features and multi-resolution transform features.

6. The method of claim 5 wherein applying the two-dimensional transform comprises applying a one-dimensional transform to rows of the two-dimensional array of pixels and applying the one-dimensional transform to columns of the two-dimensional array of pixels.

7. The method of claim 6 wherein the one-dimensional transform is defined from a discrete cosine transform and a permutation function whereby the output elements of the transform are separated into a first portion and a second portion, the first portion containing lower scales of representation of input to the transform.

8. The method of claim 7 wherein the one-dimensional transform is defined recursively.

9. The method of claim 8 wherein the one-dimensional transform is the discrete wavelet cosine transform.

10. The method of claim 1 further comprising dividing the lowest quality scale representation and the differential images into blocks of dimension M by M wherein M is an integral power of 2 before transforming to a set of coefficients.

11. The method of claim 10 further comprising forming a block of dimension M by M from a block of dimension J by K, wherein J and K are not integral powers of 2, by adding elements to the block of dimension J by K such that the set of coefficients after transformation has at most J×

K nonzero values.

12. The method of claim 1 wherein the lossless ordered statistics encoding process comprises context prediction of quantized coefficients, ordering, and arithmetic encoding, wherein context prediction is performed separately for each color component, and wherein for the primary color component, the context comprises a positional index and neighboring coefficients of primary color pixels, for a first secondary color component, the context comprises a positional index, coefficients of neighboring first secondary color components, and the coefficient of the primary color component of the same positional index, and for a second secondary color component, the context comprises a positional index, neighboring second secondary color coefficients, and the coefficients of the primary and first secondary color components of the same positional index.

13. The method of claim 12 wherein context prediction divides the quantized coefficients into groups, wherein a first group comprises the coefficient corresponding to a lowest positional index, a second group comprises a first row of coefficients excluding the first group coefficient, a third group comprises a first column of coefficients excluding the first group coefficient, and a fourth group comprises the remaining coefficients, and wherein the context is different for each group.

14. The method of claim 5 wherein the lossless ordered statistics encoding process comprises context prediction, ordering the two-dimensional array of pixels into a one-dimensional array, and arithmetic encoding, wherein ordering comprises partitioning the two-dimensional array into four equally sized regions ordered as upper left, upper right, lower left, and lower right, and repeatedly partitioning each region into four equally sized subregions ordered as upper left, upper right, lower left, and lower right until a subregion is one pixel by one pixel in size.

15. A method of reconstructing a digital representation of an image compressed by the method of claim 1, the reconstruction method comprising:

recovering context prediction probability tables used in compression;

decoding integer values corresponding to the base quality scale representation and the differential images;

reverse ordering each decoded integer value to a two-dimensional position in an array of pixels;

multiplying each decoded integer value corresponding to the base quality scale and the differential images by the quantization value;

performing the inverse transform associated with the known functions to reconstruct the digital representation of the base quality scale and the differential images;

upscaling the digital representation of an image at a lower quality scale to the next higher quality scale; and

adding a differential image at a given quality scale to the upscaled image at the given quality scale to reconstruct the digital representation at the given quality scale.

16. The method of claim 15 wherein for a primary color component, a context used in context prediction tables comprises a positional index and neighboring coefficients of primary color pixels, for a first secondary color component, a context comprises a positional index, coefficients of neighboring first secondary color components, and the coefficient of the primary color component of the same positional index, and for a second secondary color component, a context comprises a positional index, neighboring second secondary color coefficients, and the coefficients of the primary and first secondary color components of the same positional index.

17. The method of claim 16 wherein context prediction tables are associated with quantized coefficients considered in groups, wherein a first group comprises the coefficient corresponding to a lowest positional index, a second group comprises a first row of coefficients excluding the first group coefficient, a third group comprises a first column of coefficients excluding the first group coefficient, and a fourth group comprises the remaining coefficients, and wherein the context is different for each group.

18. The method of claim 15 wherein the inverse transform associated with the known functions is the inverse of a transform combining frequency transform features and multi-resolution transform features.

19. The method of claim 18 wherein the inverse transform is defined recursively from an inverse discrete cosine transform and a permutation function, and wherein the input elements of the inverse transform are separated into a first portion and a second portion, the first portion containing lower scales of representation of input to the transform.

20. The method of claim 19 wherein the inverse transform is an inverse discrete wavelet transform.

30. An apparatus comprising instructions for reconstructing a digital representation of an image compressed by the method of claim 1, the instructions comprising instructions for:

recovering context prediction probability tables used in compression;

decoding integer values corresponding to the base quality scale representation and the differential images;

reverse ordering each decoded integer value to a two-dimensional position in an array of pixels;

multiplying each decoded integer value corresponding to the base quality scale and the differential images by the quantization value;

performing the inverse transform associated with the known functions to reconstruct the digital representation of the base quality scale and the differential images;

upscaling the digital representation of an image at a lower quality scale to the next higher quality scale; and

adding a differential image at a given quality scale to the upscaled image at the given quality scale to reconstruct the digital representation at the given quality scale.

31. The apparatus of claim 30 wherein for the primary color component, the context used in context prediction tables comprises a positional index and neighboring coefficients of primary color pixels, for a first secondary color component, the context comprises a positional index, coefficients of neighboring first secondary color components, and the coefficient of the primary color component of the same positional index, and for a second secondary color component, the context comprises a positional index, neighboring second secondary color coefficients, and the coefficients of the primary and first secondary color components of the same positional index.

32. The apparatus of claim 31 wherein context prediction tables are associated with quantized coefficients considered in groups, wherein a first group comprises the coefficient corresponding to a lowest positional index, a second group comprises a first row of coefficients excluding the first group coefficient, a third group comprises a first column of coefficients excluding the first group coefficient, and a fourth group comprises the remaining coefficients, and wherein the context is different for each group.

33. The apparatus of claim 30 wherein the inverse transform associated with the known functions is the inverse of a transform combining frequency transform features and multi-resolution transform features.

34. The apparatus of claim 33 wherein the inverse transform is defined recursively from an inverse discrete cosine transform and a permutation function, and wherein the input elements of the inverse transform are separated into a first portion and a second portion, the first portion containing lower scales of representation of input to the transform.

35. The apparatus of claim 34 wherein the inverse transform is an inverse discrete wavelet transform.

21. A sequence of subsampling representations of decreasing length for compressing a digital representation of an image, the digital representation comprising a two-dimensional array of pixels wherein a primary color component and secondary color components are associated with each pixel, the sequence comprising:

a first subsampling representation wherein all color components are present at each pixel;

a second subsampling representation wherein the primary color component and one secondary color component are present at each pixel;

a third subsampling representation wherein a primary color component is present at each pixel and quadruple as many primary color components as each secondary color components are present;

a fourth subsampling representation derived from the first subsampling representation by reducing the number of pixels in the horizontal direction and in the vertical direction by dividing each dimension of the two-dimensional array by an integral factor;

a fifth subsampling representation derived from the fourth subsampling representation wherein the primary color component and one secondary color component are present at each pixel; and

a sixth subsampling representation derived from the fourth subsampling representation wherein a primary color component is present at each pixel and quadruple as many primary color components as each secondary color component are present.

22. A sequence of subsampling representations of decreasing length for compressing a digital representation of an image, the digital representation comprising a two-dimensional array of pixels wherein a primary color component and secondary color components are associated with each pixel, the sequence comprising:

a first subsampling representation wherein all color components are present at each pixel;

a second subsampling representation wherein the primary color component and one secondary color component are present at each pixel;

a third subsampling representation wherein a primary color component is present at each pixel and quadruple as many primary color components as each secondary color components are present; and

a fourth subsampling representation wherein one color component is present at each pixel and twice as many primary components as secondary components are present.

25. The apparatus of claim 24 wherein transforming to a set of coefficients associated with known functions is applying a transform defined recursively from a discrete cosine transform and a permutation function whereby the output elements of the transform are separated into a first portion and a second portion, the first portion containing lower scales of representation of input to the transform.

26. The apparatus of claim 25 wherein the transform is a discrete wavelet cosine transform.

27. The apparatus of claim 24 wherein the lossless ordered statistics encoding process comprises context prediction of quantized coefficients, ordering, and arithmetic encoding, wherein context prediction is performed separately for each color component, and wherein for the primary color component, the context comprises a positional index and neighboring coefficients of primary color pixels, for a first secondary color component, the context comprises a positional index, coefficients of neighboring first secondary color components, and the coefficient of the primary color component of the same positional index, and for a second secondary color component, the context comprises a positional index, neighboring second secondary color coefficients, and the coefficients of the primary and first secondary color components of the same positional index.

28. The apparatus of claim 27 wherein context prediction divides the quantized coefficients into groups, wherein a first group comprises the coefficient corresponding to a lowest positional index, a second group comprises a first row of coefficients excluding the first group coefficient, a third group comprises a first column of coefficients excluding the first group coefficient, and a fourth group comprises the remaining coefficients, and wherein the context is different for each group.

23. A context prediction method for forming probability tables for use in an entropy encoding process in compressing a digital representation of an image into a bitstream, the digital representation comprising a two-dimensional array of pixels wherein a primary color component and secondary color components are associated with each pixel, the context prediction method comprising:

determining separate contexts for each color component, wherein for a primary color component, the context comprises a positional index and neighboring coefficients of primary color pixels, for a first secondary color component, the context comprises a positional index, coefficients of neighboring first secondary color components, and the coefficient of the primary color component of the same positional index, and for a second secondary color component, the context comprises a positional index, neighboring second secondary color coefficients, and the coefficients of the primary and first secondary color components of the same positional index.

24. An apparatus comprising instructions for performing a method of compressing a digital representation of an image into a one-dimensional bitstream, the digital representation comprising a two.-dimensional array of pixels wherein a primary color component and secondary color components are associated with each pixel, the method comprising:

representing the image in a series of quality scales of progressively decreasing quality, wherein a higher quality scale comprises more data than a lower quality scale, and wherein lower quality scales are formed from higher quality scales by decreasing the number of stored color components or by decreasing the number of pixels;

representing the image in terms of quality scales in terms of a base quality scale image and differential images wherein a differential image at a given quality scale is the difference between the image at the given quality scale and a representation of the image scaled up from a reconstructed representation at the adjacent lower quality scale, the reconstructed representation determined by a process comprising;

transforming the image into a set of coefficients associated with known functions,

quantizing the set of coefficients by dividing by quantization values and rounding to integer values,

dequantizing the set of quantized coefficients by multiplying by the quantization values, and

performing the inverse transform associated with the known functions to produce a reconstructed representation;

representing the base quality scale image and the differential images as integer values by a process comprising transforming to a set of coefficients associated with known functions and quantizing the set of coefficients by dividing by quantization values and rounding to integer values; and

encoding the integer values corresponding to the lowest quality scale representation and the differential images by a lossless ordered statistics encoding process to produce a one-dimensional bitstream.

29. An apparatus comprising instructions for providing a compact representation of digital data for use in compressing a digital representation of an image into a one dimensional bitstream, the instructions comprising instructions for:

transforming the data by a transform combining frequency transform features and multi-resolution transform features wherein the transform is defined recursively from a discrete cosine transform and a permutation function whereby the output elements of the transform are separated into a first portion and a second portion, the first portion containing lower scales of representation of input to the transform; and

storing the output elements on a digital storage medium.