Quality based image compression

• US 20030202707A1
• Filed: 06/12/2003
• Published: 10/30/2003
• Est. Priority Date: 01/28/2000
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Thyagarajan, Kadayam S., Morley, Steven A.
• Granted Patent: US 7,136,534 B2
• Time in Patent Office: Days
• US Class Current: 382/239
• 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/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/93 Run-length coding
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A system and method for quality-based image compression utilizing adaptively sized blocks and sub-blocks of discrete cosine transform coefficient data and a quality based quantization scale factor is claimed. A block size assignment element in an encoder element selects the block or sub-block of an input block of pixel data to be processed. Blocks with variances larger than a threshold are subdivided, while blocks with variances smaller than a threshold are not subdivided. A transform element transforms the pixel values of the selected blocks into the frequency domain. The frequency domain values are quantized either on a block by block basis or a frame by frame basis utilizing a scale factor that correlates with the quality of the image. The data is then serialized and coded in preparation for transmission.

Claims

1. A method of compressing a digital image, the image comprising pixel data, the method comprising the acts of:

reading a block of pixel data;

generating a block size assignment to divide blocks of pixel into sub-blocks of pixel data;

transforming the sub-blocks of pixel data into corresponding frequency domain representations; and

scaling the frequency domain representations into a stream of data, wherein the act of scaling is based on a quality metric, the quality metric based on human perceptual characteristics of the image.

2. The method of claim 1, wherein the act of scaling further comprises the act of providing a frequency weighted mask to said sub-blocks of pixel data, such that the frequency weighting mask provides emphasis to the portions of the image that the human visual system is more sensitive, and provides less emphasis to the portions of the image that the human visual system is less sensitive.

3. The method of claim 1, wherein the act of scaling further comprises the act of quantizing the sub-blocks of pixel data based on the quality of the image.

4. The method of claim 1, wherein the quality metric is a signal to noise ratio.

5. The method of claim 1, wherein the act of transforming performs a Discrete Cosine Transform.

6. The method of claim 1, wherein the act of transforming performs a Discrete Cosine Transform followed by a Differential Quad-tree Transform.

7. The method of claim 5, wherein the act of scaling is on a block by block basis.

8. The method of claim 7, wherein the act of scaling is based on the contrast of the sub-block of pixel data.

9. The method of claim 7, wherein the act of scaling is based on the number of AC coefficients within a sub-block that exceed in magnitude a predetermined threshold.

10. The method of claim 7, wherein the act of scaling is based on the mean square error of the sub-block.

11. The method of claim 5, wherein the act of scaling is on a frame by frame basis.

12. The method of claim 11, wherein the act of scaling is based on the scaling factor of the previous frame.

13. The method of claim 1, wherein the act of generating further comprises the acts of:

determining a variance of pixel values for said block of pixel data;

comparing said variance with a threshold;

making a decision to subdivide the block based on a result of the act of comparing;

if said decision is to subdivide said block, then repeating the acts of determining, comparing, and making for each sub-block until a predetermined criteria is satisfied; and

designating as the block size assignment each block or sub-block that is not further subdivided.

14. The method of claim 13, wherein the step of making a decision calls for a block to be subdivided if the variance is greater than the threshold.

15. The method of claim 14, wherein the threshold is predetermined.

16. The method of claim 14, wherein the threshold is a function of the mean of pixel values of the block or sub-block being evaluated.

17. The method of claim 14, wherein the threshold changes for each level of subdivision.

18. The method of claim 13, wherein the predetermined criteria for no longer repeating the steps of determining, comparing, and making is based on a pre-selected minimum block size of pixel data.

19. The method of claim 1, wherein the act of scaling the coefficient data into a stream of data further comprises zigzag scanning the coefficient data.

20. The method of claim 19, wherein the act of zigzag scanning is performed using an 8×

8 pixel block size.

21. The method of claim 1, wherein the act of scaling further comprises the act of coding the stream of data into a serialized stream of data in preparation for transmission.

22. The method of claim 21, wherein the act of coding comprises a Huffman coder.

23. The method of claim 21, wherein the Huffman coder employs multiple look-up tables to code run-length and non-zero values.

24. The method of claim 23, wherein there are three look-up tables.

25. The method of claim 1, wherein the act of generating is based on the perceptual characteristics of the image.

70. The method of claim 1, wherein the quality metric is a function of a pixel rate.

71. The method of claim 1, wherein the quality metric is a function of an average distortion rate.

26. A quality based image compression system for compressing pixel data, the system comprising:

block size assignment means to divide blocks of pixel into sub-blocks of pixel data;

transform means to transform the sub-blocks of pixel data into corresponding frequency domain representations; and

scaling means to scale the frequency domain representations into a stream of data, wherein the scaling means is based on a quality metric the quality metric based on human perceptual characteristics of the image.

27. The system of claim 26, wherein the scaling means further comprises a frequency weighted masking means to said sub-blocks of pixel data, such that the frequency weighted mask provides emphasis to the portions of the image that the human visual system is more sensitive, and provides less emphasis to the portions of the image that the human visual system is less sensitive.

28. The system of claim 26, wherein the scaling means further comprises a quantizer to quantize the sub-blocks of pixel data based on the quality of the image.

29. The system of claim 26, wherein the quality metric is a signal to noise ratio.

30. The system of claim 26, wherein the transform means performs a Discrete Cosine Transform.

31. The system of claim 26, wherein the transform means performs a Discrete Cosine Transform followed by a Differential Quad-tree Transform.

32. The system of claim 30, wherein the scaling means scales the data on a block by block basis.

33. The system of claim 32, wherein the scaling means is based on the contrast of the sub-block of pixel data.

34. The system of claim 32, wherein the scaling means is based on the number of AC coefficients within a sub-block that exceed in magnitude a predetermined threshold.

35. The system of claim 32, wherein the scaling means is based on the mean square error of the sub-block.

36. The system of claim 26, wherein the scaling means is on a frame by frame basis.

37. The system of claim 35, wherein the scaling means is based on the scaling factor of the previous frame.

38. The system of claim 26, wherein the block size assignment means determines a variance of pixel values for the block of pixel data;

compares the variance with a threshold;

makes a decision to subdivide the block based on a result of the comparing;

wherein if the decision is to subdivide the block, then repeats the determination of variance, the comparison with a threshold, and the decision to subdivide for each subdivided block until a predetermined criteria is satisfied; and

designates as the block size assignment each block or sub-block that is not further subdivided.

39. The system of claim 38, wherein the decision to subdivide calls for a block to be subdivided if the variance is greater than the threshold.

40. The system of claim 39, wherein the threshold is predetermined.

41. The system of claim 39, wherein the threshold is a function of the mean of pixel values of the block or sub-block being evaluated.

42. The system of claim 39, wherein the threshold changes for each level of subdivision.

43. The system of claim 38, wherein the predetermined criteria for no longer subdividing is based on a pre-selected minimum block size of pixel data.

44. The system of claim 26, wherein the scaling further comprises a zigzag scanner.

45. The system of claim 44, wherein the zigzag scanner employs an 8×

8 pixel block size for the zigzag scanner.

46. The system of claim 45, wherein the scaling means further comprises a coder to code the stream of data into a serialized stream of data in preparation for transmission.

47. The system of claim 46, wherein the coder is a Huffman coder.

48. The system of claim 47, wherein the Huffman coder employs multiple look-up tables to code run-length and non-zero values.

49. The system of claim 48, wherein there are three look-up tables.

50. A method of compressing a digital image, the image comprising pixel data, the method comprising the acts of:

reading a block of pixel data;

generating a block size assignment to divide blocks of pixel into sub-blocks of pixel data;

transforming the sub-blocks of pixel data into corresponding frequency domain representations; and

scaling the frequency domain representations into a stream of data, wherein the act of scaling is based on a quality metric, the quality metric based on human perceptual characteristics of the image;

wherein the act of scaling further comprises the act of providing a frequency weighted mask to said sub-blocks of pixel data such that the frequency weighted mask provides emphasis to the portions of the image that the human visual system is more sensitive, and provides less emphasis to the portions of the image that the human visual system is less sensitive; and

wherein the act of scaling further comprises the act of quantizing the sub-blocks of pixel data based on the quality of the image.

51. The method of claim 50, wherein the quality metric is the signal to noise ratio.

52. The method of claim 50, wherein the act of transforming performs a Discrete Cosine Transform.

53. The method of claim 50, wherein the act of transforming performs a Discrete Cosine Transform followed by a Differential Quad-tree Transform.

54. The method of claim 50, wherein the act of scaling is on a block by block basis.

55. The method of claim 54, wherein the act of scaling is based on the contrast of the sub-block of pixel data.

56. The method of claim 54, wherein the act of scaling is based on the number of AC coefficients within a sub-block that exceed in magnitude a predetermined threshold.

57. The method of claim 54, wherein the act of scaling is based on the mean square error of the sub-block.

58. The method of claim 54, wherein the act of scaling is on a frame by frame basis.

59. The method of claim 58, wherein the act of scaling is based on the scaling factor of the previous frame.

60. A quality based image compression system for compressing -pixel data, the system comprising:

block size assignment means to divide blocks of pixel into sub-blocks of pixel data;

transform means to transform the sub-blocks of pixel data into corresponding frequency domain representations; and

scaling means to scale the frequency domain representations into a stream of data, wherein the scaling means is based on a quality metric the quality metric based on human perceptual characteristics of the image;

wherein the scaling means further comprises a frequency weighted masking means to said sub-blocks of pixel data, such that the frequency weighted mask provides emphasis to the portions of the image that the human visual system is more sensitive, and provides less emphasis to the portions of the image that the human visual system is less sensitive; and

wherein the scaling means further comprises a quantizer to quantize the sub-blocks of pixel data based on the quality of the image.

61. The system of claim 60, wherein the quality metric is a signal to noise ratio.

62. The system of claim 60, wherein the transform means performs a Discrete Cosine Transform.

63. The system of claim 62, wherein the transform means performs a Discrete Cosine Transform followed by a Differential Quad-tree Transform.

64. The system of claim 63, wherein the scaling means scales the data on a block by block basis.

65. The system of claim 63, wherein the scaling means is based on the contrast of the sub-block of pixel data.

66. The system of claim 63, wherein the scaling means is based on the number of AC coefficients within a sub-block that exceed in magnitude a predetermined threshold.

67. The system of claim 63, wherein the scaling means is based on the mean square error of the sub-block.

68. The system of claim 63, wherein the scaling means is on a frame by frame basis.

69. The system of claim 68, wherein the scaling means is based on the number and size of block size assignments per frame.