Constant bitrate algorithm for block based image compression

• US 6,614,942 B1
• Filed: 12/17/1999
• Issued: 09/02/2003
• Est. Priority Date: 12/17/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meier, Fabian
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/466,398
• Time in Patent Office: 1,355 Days
• Field of Search: 382/232, 382/233, 382/234, 382/235, 382/236, 382/237, 382/238, 382/239, 382/240, 382/241, 382/242, 382/243, 382/244, 382/245, 382/246, 382/247, 382/248, 382/249, 382/250, 382/251, 382/252, 382/253
• US Class Current: 382/251
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A method of compressing image data to achieve a desired compression ratio corresponding to a desired file size. A target compression ratio (the ratio of uncompressed image data to compressed image data) is specified. A subset of the image data is selected. A first quantization parameter is selected, the subset of the image data is compressed using that quantization parameter, and the resulting compression ratio is calculated. A second quantization parameter is then selected, the subset of the image data is compressed using the second quantization parameter, and the resulting compression ratio is calculated. A target quantization parameter corresponding to the target compression ratio is calculated by interpolating between the first quantization parameter and the second quantization parameter and the corresponding compression ratios. The target quantization parameter is applied to the entire set of image data to compress the image data at approximately the target compression ratio. As a result, the size of the file containing the compressed data is approximately the same as the target file size. The present invention allows rate control in less computation time than it takes to compress the image; the time to estimate the target quantization parameter can be done in less computation time than needed to compress the full image.

Claims

1. A method of compressing image data for an image, said method comprising:

a) receiving a target compression ratio specifying a ratio of uncompressed image data to compressed image data;

b) selecting a subset of said image data;

c) compressing image data in said subset using a first quantization parameter;

d) calculating a first compression ratio for said subset;

e) calculating a target quantization parameter based on said first quantization parameter and said first compression ratio, said target quantization parameter corresponding approximately to said target compression ratio; and

f) compressing said image data using said target quantization parameter.

2. The method of compressing image data as recited in claim 1 wherein said image is encoded as a plurality of macroblocks and wherein said step b) comprises the step of:

b1) selecting a subset of said plurality of macroblocks.

3. The method of compressing image data as recited in claim 2 wherein said step b1) comprises the step of:

selecting every n-th macroblock from said plurality of macroblocks to form said subset.

4. The method of compressing image data as recited in claim 2 wherein said step b1) comprises the step of:

selecting macroblocks at random from said plurality of macroblocks to form said subset.

5. The method of compressing image data as recited in claim 2 wherein said step b1) comprises the step of:

using a lookup table to select macroblocks from said plurality of macroblocks to form said subset.

6. The method of compressing image data as recited in claim 1 further comprising the steps of:

compressing image data in said subset using a second quantization parameter;

calculating a second compression ratio for said subset; and

calculating said target quantization parameter by interpolation between said first quantization parameter and said second quantization parameter.

7. The method of compressing image data as recited in claim 1 wherein said compressing is performed using a Joint Photographic Experts Group (JPEG) compression scheme.

8. The method of compressing image data as recited in claim 1 wherein said compressing is performed using a Motion Pictures Experts Group (MPEG) compression scheme.

9. The method of compressing image data as recited in claim 1 wherein said subset includes approximately four to ten percent of said uncompressed image data.

10. A computer system comprising:

a bus;

a processor coupled to said bus; and

a memory unit coupled to said bus, said processor for executing a method for compressing image data for an image, said method comprising the steps of;

a) receiving a target compression ratio specifying a ratio of uncompressed image data to compressed image data;

b) selecting a subset of said image data;

c) compressing image data in said subset using a first quantization parameter;

d) calculating a first compression ratio for said subset;

e) calculating a target quantization parameter based on said first quantization parameter and said first compression ratio, said target quantization parameter corresponding approximately to said target compression ratio; and

f) compressing said image data using said target quantization parameter.

11. The computer system of claim 10 wherein said image is encoded as a plurality of macroblocks and wherein said step b) of said method comprises the step of:

b1) selecting a subset of said plurality of macroblocks.

12. The computer system of claim 11 wherein said step b1) comprises the step of:

selecting every n-th macroblock from said plurality of macroblocks to form said subset.

13. The computer system of claim 11 wherein said step b1) comprises the step of:

selecting macroblocks at random from said plurality of macroblocks to form said subset.

14. The computer system of claim 11 wherein said step b1) comprises the step of:

using a lookup table to select macroblocks from said plurality of macroblocks to form said subset.

15. The computer system of claim 10 wherein said method further comprises the steps of:

compressing image data in said subset using a second quantization parameter;

calculating a second compression ratio for said subset; and

calculating said target quantization parameter by interpolating between said first quantization parameter and said second quantization parameter.

16. The computer system of claim 10 wherein said compression of said image data is performed using a Joint Photographic Experts Group (JPEG) encoding scheme.

17. The computer system of claim 10 wherein said compression of said image data is performed using a Motion Pictures Experts Group (MPEG) encoding scheme.

18. The computer system of claim 10 wherein said subset includes approximately four to ten percent of said uncompressed image data.

19. A method of compressing image data for an image encoded as a plurality of macroblocks, said method comprising:

a) receiving a target compression ratio specifying a ratio of uncompressed image data to compressed image data;

b) selecting a subset of said plurality of macroblocks;

c) compressing image data in said subset using a first quantization parameter;

d) calculating a first compression ratio for said subset;

e) compressing image data in said subset using a second quantization parameter;

f) calculating a second compression ratio for said subset;

g) calculating a target quantization parameter by interpolating between said first quantization parameter and said second quantization parameter, said target quantization parameter corresponding approximately to said target compression ratio; and

h) applying said target quantization parameter to said plurality of macroblocks to compress said image data.

20. The method of compressing image data as recited in claim 19 wherein said step b) comprises the step of:

selecting every n-th macroblock from said plurality of macroblocks to form said subset.

21. The method of compressing image data as recited in claim 19 wherein said step b) comprises the step of:

selecting macroblocks at random from said plurality of macroblocks to form said subset.

22. The method of compressing image data as recited in claim 19 wherein said step b) comprises the step of:

using a lookup table to select macroblocks from said plurality of macroblocks to form said subset.

23. The method of compressing image data as recited in claim 19 wherein said compressing is performed using a Joint Photographic Experts Group (JPEG) compression scheme.

24. The method of compressing image data as recited in claim 19 wherein said compressing is performed using a Motion Pictures Experts Group (MPEG) compression scheme.

25. The method of compressing image data as recited in claim 19 wherein said subset includes approximately four to ten percent of said uncompressed image data.