Image compression system and method having optimized quantization tables

• US 5,724,453 A
• Filed: 07/10/1995
• Issued: 03/03/1998
• Est. Priority Date: 07/10/1995
• Status: Expired due to Fees

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Ratnakar, Viresh, Livny, Miron
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/500,000
• Time in Patent Office: 967 Days
• Field of Search: 382/239, 382/250, 382/251, 348/405, 358/432, 358/433, 340/825.8, 364/514 C, 379/67, 395/600
• US Class Current: 382/251
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A digital image compression preprocessor for use in a discrete cosine transform-based digital image compression device is provided. The preprocessor includes a gathering mechanism for determining discrete cosine transform statistics from input digital image data. A computing mechanism is operatively coupled to the gathering mechanism to calculate a image distortion array and a rate of image compression array based upon the discrete cosine transform statistics for each possible quantization value. A dynamic programming mechanism is operatively coupled to the computing mechanism to optimize the rate of image compression array against the image distortion array such that a rate-distortion-optimal quantization table is derived. In addition, a discrete cosine transform-based digital image compression device and a discrete cosine transform-based digital image compression and decompression system are provided. Also, a method for generating a rate-distortion-optimal quantization table, using discrete cosine transform-based digital image compression, and operating a discrete cosine transform-based digital image compression and decompression system are provided.

Claims

1. A digital image compression preprocessor for use in a discrete cosine transform-based digital image compression device, the preprocessor comprising:

(a) gathering means for determining discrete cosine transform statistics from input digital image data, wherein the discrete cosine transform statistics include counts related to the number of times each of a plurality of discrete cosine transform coefficients derived from the input digital image data takes a value;

(b) computing means, operatively coupled to the gathering means, for calculating an image distortion array and a rate of image compression array based upon the discrete cosine transform statistics for each of a plurality of possible quantization values; and

(c) quantization table generating means, operatively coupled to the computing means, for optimizing the rate of image compression array against the image distortion array to derive a rate-distortion-optimal quantization table.

2. The digital image compression preprocessor of claim 1 wherein the gathering means comprises means for determining discrete cosine transform statistics from input digital image data by dividing the input digital image data into fixed length image blocks, applying a discrete cosine transform to each fixed length image block to generate a corresponding block of discrete cosine transform coefficients for each fixed length image block, and counting a number of times each discrete cosine transform coefficient has a non-zero value for all of the fixed length image blocks divided out of the input digital image data.

3. The digital image compression preprocessor of claim 2 wherein the computing means comprises means for calculating the rate of image compression array by calculating entropy of each discrete cosine transform coefficient when quantized by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value.

4. The digital image compression preprocessor of claim 3 wherein the computing means comprises means for calculating the image distortion array by calculating error produced when quantizing each discrete cosine transform coefficient by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value.

5. The digital image compression preprocessor of claim 4 wherein the quantization table generating means comprises means for deriving the rate-distortion-optimal quantization table by calculating a least distortion array containing the least distortion produced for each discrete cosine transform coefficient at each rate of image compression as a function of the image distortion array and the rate of image compression array, calculating an array of quantization values which produced each entry in the least distortion array, and determining the rate-distortion-optimal quantization table at least as a function of the array of quantization values which produced each entry in the least distortion array.

6. The digital image compression preprocessor of claim 5 wherein the quantization table generating means comprises means for discretizing values in one of the image distortion array and the rate of image compression array to integral values prior to the deriving of the rate-distortion-optimal quantization table.

7. The digital image compression preprocessor of claim 1 wherein the quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a total image distortion requirement to derive a rate-distortion-optimal quantization table having a maximal rate of image compression with a total image distortion less than the total image distortion requirement.

8. The digital image compression preprocessor of claim 1 wherein the quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a rate of image compression requirement to derive a rate-distortion-optimal quantization table having a minimal total image distortion with a rate of image compression greater than the rate of image compression requirement.

9. The digital image compression preprocessor of claim 1 wherein the digital image compression device utilizes joint photographic experts group (JPEG) image compression standard algorithms and wherein the quantization table generating means comprises means for configuring the rate-distortion-optimal quantization table for use with the joint photographic experts group (JPEG) image compression standard algorithms.

10. The digital image compression preprocessor of claim 1 wherein the digital image compression device utilizes motion picture experts group (MPEG) image compression standard algorithms and wherein the quantization table generating means comprises means for configuring the rate-distortion-optimal quantization table for use with the motion picture experts group (MPEG) image compression standard algorithms.

11. The digital image compression preprocessor of claim 1 wherein the digital image compression device utilizes H.261 video compression standard algorithms and wherein the quantization table generating means comprises means for configuring the rate-distortion-optimal quantization table for use with the H.261 video compression standard algorithms.

12. A discrete cosine transform-based digital image compression device, comprising:

(a) discrete cosine transformer means for dividing input digital image data into fixed length image blocks and generating a corresponding block of discrete cosine transform coefficients for each fixed length image block by applying a discrete cosine transform to each fixed length image block;

(b) quantization table generator, operatively coupled to the discrete cosine transformer means, which generates a rate-distortion-optimal quantization table, comprising;

(i) gathering means for determining discrete cosine transform statistics from each block of discrete cosine transform coefficients, wherein the discrete cosine transform statistics include counts related to the number of times each discrete cosine transform coefficient from the blocks takes a value;

(ii) computing means, operatively coupled to the gathering means, for calculating an image distortion array and a rate of image compression array based upon the discrete cosine transform statistics for each of a plurality of possible quantization values; and

(iii) quantization table generating means, operatively coupled to the computing means, for optimizing the rate of image compression array against the image distortion array to derive the rate-distortion-optimal quantization table;

(c) quantizing means, operatively coupled to the discrete cosine transformer means and the quantization table generating means, for generating a corresponding block of quantized discrete cosine transform coefficients for each block of discrete cosine transform coefficients by quantizing each block of discrete cosine transform coefficients with the rate-distortion-optimal quantization table; and

(d) entropy coding means, operatively coupled to the quantizing means, for entropy coding each block of quantized discrete cosine transform coefficients to form a corresponding compressed block such that a sequence of all of the compressed blocks forms the compressed digital image data.

13. The digital image compression device of claim 12 wherein the entropy coding means comprises means for entropy coding each block of quantized discrete cosine transform coefficients with Huffman codes to exploit similarities across the quantized discrete cosine transform coefficients.

14. The digital image compression device of claim 12 further comprising input means, operatively coupled to the discrete cosine transformer means, for receiving the input digital image data from a device external to the digital image compression device.

15. The digital image compression device of claim 14 wherein the device external to the digital image compression device is selected from the group consisting of a serial communications port, a parallel communications port, a data network interface, a public switched telephone network adapter, an optically-encoded disk drive, a magnetically-encoded disk drive, and a radio communication unit.

16. The digital image compression device of claim 12 further comprising transmitting means, operatively coupled to the entropy coding means, for transmitting the compressed digital image data and the rate-distortion-optimal quantization table to a device external to the digital image compression device.

17. The digital image compression device of claim 16 wherein the device external to the digital image compression device is selected from the group consisting of a serial communications port, a parallel communications port, a data network interface, a public switched telephone network adapter, an optically-encoded disk drive, a magnetically-encoded disk drive, and a radio communication unit.

18. The digital image compression device of claim 12 wherein:

(a) the quantization table generator gathering means comprises means for determining discrete cosine transform statistics from input digital image data by dividing the input digital image data into fixed length image blocks, applying a discrete cosine transform to each fixed length image block to generate a corresponding block of discrete cosine transform coefficients for each fixed length image block, and counting a number of times each discrete cosine transform coefficient has a non-zero value for all of the fixed length image blocks divided out of the input digital image data;

(b) the quantization table generator computing means comprises means for calculating the rate of image compression array by calculating entropy of each discrete cosine transform coefficient when quantized by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value;

(c) the quantization table generator computing means comprises means for calculating the image distortion array by calculating error produced when quantizing each discrete cosine transform coefficient by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value; and

(d) the quantization table generator quantization table generating means comprises means for deriving the rate-distortion-optimal quantization table by calculating a least distortion array containing the least distortion produced for each discrete cosine transform coefficient at each rate of image compression as a function of the image distortion array and the rate of image compression array, calculating an array of quantization values which produced each entry in the least distortion array, and determining the rate-distortion-optimal quantization table at least as a function of the array of quantization values which produced each entry in the least distortion array.

19. The digital image compression device of claim 18 wherein the quantization table generator quantization table generating means comprises means for discretizing values in one of the image distortion array and the rate of image compression array to integral values prior to deriving the rate-distortion-optimal quantization table.

20. The digital image compression device of claim 12 wherein the quantization table generator quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a total image distortion requirement to derive a rate-distortion-optimal quantization table having a maximal rate of image compression with a total image distortion less than the total image distortion requirement.

21. The digital image compression device of claim 12 wherein the quantization table generator quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a rate of image compression requirement to derive a rate-distortion-optimal quantization table having a minimal total image distortion with a rate of image compression greater than the rate of image compression requirement.

22. The digital image compression device of claim 12 wherein the quantization table generator quantization table generating means comprises means for configuring the rate-distortion-optimal quantization table for use with image compression standard algorithms such that the digital image compression device utilizes an image compression standard algorithm selected from the group consisting of a joint photographic experts group (JPEG) image compression standard algorithm, a motion picture experts group (MPEG) image compression standard algorithm, and a H.261 video compression standard algorithm.

23. A discrete cosine transform-based digital image compression and decompression system, comprising:

(a) a transmitting device which receives input digital image data, generates compressed digital image data, and transmits the compressed digital image data and a rate-distortion-optimal quantization table over a communication channel, the transmitting device comprising;

(i) discrete cosine transformer means for dividing the input digital image data into fixed length image blocks and generating a corresponding block of discrete cosine transform coefficients for each fixed length image block by applying a discrete cosine transform to each fixed length image block;

(ii) quantization table generating means, operatively coupled to the discrete cosine transformer means, for generating the rate-distortion-optimal quantization table by determining discrete cosine transform statistics from each block of discrete cosine transform coefficients, wherein the discrete cosine transform statistics include counts related to the number of times each discrete cosine transform coefficient from the blocks takes a value, calculating an image distortion array and a rate of image compression array based upon the discrete cosine transform statistics for each of a plurality of possible quantization values, and optimizing the rate of image compression array against the image distortion array to derive the rate-distortion-optimal quantization table;

(iii) quantization means, operatively coupled to the discrete cosine transformer means and the quantization table generating means, for generating a corresponding block of quantized discrete cosine transform coefficients for each block of discrete cosine transform coefficients by quantizing each block of discrete cosine transform coefficients with the rate-distortion-optimal quantization table; and

(iv) entropy coding means, operatively coupled to the quantizing means, for entropy coding each block of quantized discrete cosine transform coefficients to form a corresponding compressed block such that a sequence of all of the compressed blocks forms the compressed digital image data; and

(b) a receiving device which receives the compressed digital image data and the rate-distortion-optimal quantization table from the communication channel and generates decompressed digital image data, the receiving device comprising;

(i) decoding means for decoding each entropy-coded compressed block in the received compressed digital image data into a corresponding block of quantized discrete cosine transform coefficients;

(ii) dequantizing means, operatively coupled to the decoding means, for generating a corresponding block of discrete cosine transform coefficients for each block of quantized discrete cosine transform coefficients based on the received rate-distortion-optimal quantization table; and

(iii) inverse discrete cosine transformer means, operatively coupled to the dequantizing means, for generating a corresponding decompressed block of fixed length digital image data for each block of discrete cosine transform coefficients by applying an inverse discrete cosine transform to each block of discrete cosine transform coefficients such that a sequence of all of the decompressed blocks forms the decompressed digital image data.

24. The digital image compression and decompression system of claim 23 wherein the communication channel is selected from the group consisting of a serial communication line, a parallel communication line, a data network, a public switched telephone network, an optically-encoded disk, a magnetically-encoded disk, and a radio communication link.

25. The digital image compression and decompression system of claim 23 further comprising input means, operatively coupled to the transmitting device, for receiving the input digital image data from a device external to the digital image compression and decompression system.

26. The digital image compression and decompression system of claim 25 wherein the input means is selected from the group consisting of a serial communications port, a parallel communications port, a data network interface, a public switched telephone network adapter, an optically-encoded disk drive, a magnetically-encoded disk drive, and a radio communication unit.

27. The digital image compression and decompression system of claim 23 wherein the quantization table generating means is configured to generate the rate-distortion-optimal quantization table by:

(a) determining discrete cosine transform statistics from input digital image data by dividing the input digital image data into fixed length image blocks, applying a discrete cosine transform to each fixed length image block to generate a corresponding block of discrete cosine transform coefficients for each fixed length image block, and counting a number of times each discrete cosine transform coefficient has a non-zero value for all of the fixed length image blocks divided out of the input digital image data;

(b) calculating the rate of image compression array by calculating entropy of each discrete cosine transform coefficient when quantized by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value;

(c) calculating the image distortion array by calculating error produced when quantizing each discrete cosine transform coefficient by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value; and

(d) deriving the rate-distortion-optimal quantization table by calculating a least distortion array containing the least distortion produced for each discrete cosine transform coefficient at each rate of image compression as a function of the image distortion array and the rate of image compression array, calculating an array of quantization values which produced each entry in the least distortion array, and determining the rate-distortion-optimal quantization table at least as a function of the array of quantization values which produced each entry in the least distortion array.

28. The digital image compression and decompression system of claim 27 wherein the quantization table generating means comprises means for discretizing values in one of the image distortion array and the rate of image compression array to integral values prior to deriving the rate-distortion-optimal quantization table.

29. The digital image compression and decompression system of claim 23 wherein the quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a total image distortion requirement to derive a rate-distortion-optimal quantization table having a maximal rate of image compression with a total image distortion less than the total image distortion requirement.

30. The digital image compression and decompression system of claim 23 wherein the quantization table generating means comprises means for optimizing the rate of image compression array against the image distortion array with respect to a rate of image compression requirement to derive a rate-distortion-optimal quantization table having a minimal total image distortion with a rate of image compression greater than the rate of image compression requirement.

31. The digital image compression and decompression system of claim 23 wherein the quantization table generating means comprises means for configuring the rate-distortion-optimal quantization table for use with image compression standard algorithms such that the digital image compression and decompression system utilizes an image compression standard algorithm selected from the group consisting of a joint photographic experts group (JPEG) image compression standard algorithm, a motion picture experts group (MPEG) image compression standard algorithm, and a H.261 video compression standard algorithm.

32. A method for generating a rate-distortion-optimal quantization table for use in a discrete cosine transform-based digital image compression process, the method comprising the steps of:

(a) determining discrete cosine transform statistics from input digital image data, wherein the discrete cosine transform statistics include counts related to the number of times each of a plurality of discrete cosine transform coefficients derived from the input digital image data takes a value;

(b) calculating an image distortion array and a rate of image compression array based upon the discrete cosine transform statistics for each of a plurality of possible quantization values; and

(c) optimizing the rate of image compression array against the image distortion array to derive the rate-distortion-optimal quantization table.

33. The method of claim 32 wherein the determining step comprises determining discrete cosine transform statistics from input digital image data by dividing the input digital image data into fixed length image blocks, applying a discrete cosine transform to each fixed length image block to generate a corresponding block of discrete cosine transform coefficients for each fixed length image block, and counting a number of times each discrete cosine transform coefficient has a non-zero value for all of the fixed length image blocks divided out of the input digital image data.

34. The method of claim 33 wherein the calculating step comprises calculating the rate of image compression array by calculating entropy of each discrete cosine transform coefficient when quantized by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value.

35. The method of claim 34 wherein the calculating step comprises calculating the image distortion array by calculating error produced when quantizing each discrete cosine transform coefficient by each possible quantization value as a function of the counted number of times each discrete cosine transform coefficient has a non-zero value.

36. The method of claim 35 wherein the optimizing step comprises deriving the rate-distortion-optimal quantization table by calculating a least distortion array containing the least distortion produced for each discrete cosine transform coefficient at each rate of image compression as a function of the image distortion array and the rate of image compression array, calculating an array of quantization values which produced each entry in the least distortion array, and determining the rate-distortion-optimal quantization table at least as a function of the array of quantization values which produced each entry in the least distortion array.

37. The method of claim 35 wherein the optimizing step comprises discretizing values in one of the image distortion array and the rate of image compression array to integral values prior to the step of deriving the rate-distortion-optimal quantization table.

38. The method of claim 32 wherein the optimizing step comprises optimizing the rate of image compression array against the image distortion array with respect to a total image distortion requirement to derive the rate-distortion-optimal quantization table having a maximal rate of image compression with a total image distortion less than the total image distortion requirement.

39. The method of claim 32 wherein the optimizing step comprises optimizing the rate of image compression array against the image distortion array with respect to a rate of image compression requirement to derive the rate-distortion-optimal quantization table having a minimal total image distortion with a rate of image compression greater than the rate of image compression requirement.

40. The method of claim 32 wherein the method is modified such that the generated rate-distortion-optimal quantization table is configured for use with an image compression standard algorithm selected from the group consisting of a joint photographic experts group (JPEG) image compression standard algorithm, a motion picture experts group (MPEG) image compression standard algorithm, and a H.261 video compression standard algorithm.

41. A discrete cosine transform-based digital image compression method having the step of generating a rate-distortion-optimal quantization table as claimed in claim 32 and further comprising the steps of:

(a) dividing input digital image data into fixed length image blocks and generating a corresponding block of discrete cosine transform coefficients for each fixed length image block by applying a discrete cosine transform to each fixed length image block;

(b) generating a corresponding block of quantized discrete cosine transform coefficients for each block of discrete cosine transform coefficients by quantizing each block of discrete cosine transform coefficients with the rate-distortion-optimal quantization table; and

(c) entropy coding each block of quantized discrete cosine transform coefficients to form a corresponding compressed block such that a sequence of all of the compressed blocks forms the compressed digital image data.

42. The method of claim 41 wherein the entropy coding step comprises entropy coding each block of quantized discrete cosine transform coefficients with Huffman codes to exploit similarities across the quantized discrete cosine transform coefficients.

43. A method for operating a discrete cosine transform-based digital image compression and decompression system having the steps of discrete cosine transform-based digital image compressing as claimed in claim 41 and further comprising these steps of:

(a) transmitting the compressed digital image data and a rate-distortion-optimal quantization table over a communication channel;

(b) receiving the compressed digital image data and the rate-distortion-optimal quantization table from the communication channel;

(c) decoding each entropy-coded compressed block in the received compressed digital image data into a corresponding block of quantized discrete cosine transform coefficients;

(d) generating a corresponding block of discrete cosine transform coefficients for each block of quantized discrete cosine transform coefficients based on the received rate-distortion-optimal quantization table; and

(e) generating a corresponding decompressed block of fixed length digital image data for each block of discrete cosine transform coefficients by applying an inverse discrete cosine transform to each block of discrete cosine transform coefficients such that a sequence of all of the decompressed blocks forms decompressed digital image data.

44. The method of claim 43 wherein the steps of transmitting and receiving utilize a communication channel selected from the group consisting of a serial communication line, a parallel communication line, a data network, a public switched telephone network, an optically-encoded disk, a magnetically-encoded disk, and a radio communication link.