Variable lossy compression

• US 7,062,088 B1
• Filed: 08/28/2001
• Issued: 06/13/2006
• Est. Priority Date: 08/28/2001
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Clauson, Jon D.
• Primary Examiner(s): Patel, Kanjbhai
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/942,048
• Time in Patent Office: 1,750 Days
• Field of Search: 382/166, 382/167, 382/232, 382/239, 382/251, 382/244, 382/238, 382/233, 382/294, 382/284, 382/283, 382/282, 345/626, 345/629, 345/563, 341/63, 341/55, 341/67, 358/517, 358/518, 358/426.13, 358/426.14, 358/426.04, 348/384.1, 348/391.1, 348/394.1, 375/240.01, 375/240.02, 375/240.03, 375/240.08, 375/240.12
• US Class Current: 382/166
• CPC Class Codes: H04N 19/103 Selection of coding mode or of prediction mode
• 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/17 the unit being an image region, e.g. an object

Abstract

Methods and apparatus for generating a compressed image from a source image by compressing the source image using a dictionary based lossy compression algorithm that regionally varies the amount of information loss from the source image based on regional image quality levels contained in an image quality mask. The image quality mask can be an alpha channel of the source image, can be stored as a raster map, or can be stored as a resolution independent function. The regional image quality levels in the image quality mask can be determined by a user, automatically generated from the image, or automatically generated from user input. The dictionary based lossy compression algorithm can be a lossy Lempel-Ziv-Welch (LZW) compression algorithm.

Claims

1. A method for generating a compressed image from a source image, comprising:

receiving a source image;

receiving an image quality mask corresponding to the source image, wherein the image quality mask contains regional image quality levels specifying the degree to which information in corresponding regions of the source image can be lost when generating the compressed image; and

generating the compressed image by compressing the source image using a dictionary based lossy compression algorithm that regionally varies the amount of information loss from the source image based on the regional image quality levels contained in the image quality mask.

2. The method of claim 1, wherein the received image quality mask is an alpha channel of the received source image.

3. The method of claim 1, wherein the lossy compression algorithm is a lossy Lempel-Ziv-Welch (LZW) compression algorithm.

4. The method of claim 1, wherein the received image quality mask is stored as a raster map.

5. The method of claim 1, wherein the received image quality mask is stored as a resolution independent function.

6. The method of claim 1, wherein the received image quality mask is determined by a user.

7. The method of claim 1, wherein the received image quality mask is automatically generated from the received image.

8. The method of claim 1, wherein the received image quality mask is automatically generated from user input.

9. A method for generating a compressed image from a source image, the method comprising:

receiving a source image having an associated image quality mask;

creating a compressed image having a compression table comprising a palletized table of colors and a plurality of identification strings respectively corresponding to each of the colors in the palletized table of colors;

initializing a prefix string with the color value of a first pixel in the source image; and

subsequently processing each pixel in the source image by

creating a search string by concatenating the pixel'"'"'s color value to the end of the prefix string;

determining an image quality value from a corresponding pixel in the image quality mask associated with the source image;

searching the compression table for a color string that matches the search string;

writing the search string to the prefix string to overwrite the prefix string when a matching color string is found; and

generating an identification string to associate with the search string;

writing the identification string and the search string to the compression table;

writing the identification string associated with the prefix string to the compressed image file; and

setting the prefix string to the pixel'"'"'s color value whenever a matching color string cannot be found.

10. The method of claim 9, wherein the image quality value represents the maximum allowable difference between the search string and a color string stored in the compression table.

11. The method of claim 10, wherein a color string stored in the compression table matches a search string when a distance metric between the color string and the search string is smaller than a function of the image quality value.

12. The method of claim 11, wherein the distance metric is a perceptual color distance metric.

13. A computer program product, stored on a machine readable medium, comprising instructions operable to cause a programmable processor to:

receive a source image;

receive an image quality mask corresponding to the source image, wherein the image quality mask contains regional image quality levels specifying the degree to which information in corresponding regions of the source image can be lost when generating the compressed image; and

generate the compressed image by compressing the source image using a dictionary based lossy compression algorithm that regionally varies the amount of information loss from the source image based on the regional image quality levels contained in the image quality mask.

14. The computer program product of claim 13, wherein the received image quality mask is an alpha channel of the received source image.

15. The computer program product of claim 13, wherein the lossy compression algorithm is a lossy Lempel-Ziv-Welch (LZW) compression algorithm.

16. The computer program product of claim 13, wherein the received image quality mask is stored as a raster map.

17. The computer program product of claim 13, wherein the received image quality mask is stored as a resolution independent function.

18. The computer program product of claim 13, wherein the received image quality mask is determined by a user.

19. The computer program product of claim 13, wherein the received image quality mask is automatically generated from the received image.

20. The computer program product of claim 13, wherein the received image quality mask is automatically generated from user input.

21. A computer program product, stored on a machine readable medium, comprising instructions operable to cause a programmable processor to:

receive a source image having an associated image quality mask;

create a compressed image having a compression table comprising a palletized table of colors and a plurality of identification strings respectively corresponding to each of the colors in the palletized table of colors;

initialize a prefix string with the color value of a first pixel in the source image; and

to subsequently process each pixel in the source image by

creating a search string by concatenating the pixel'"'"'s color value to the end of the prefix string;

determining an image quality value from a corresponding pixel in the image quality mask associated with the source image;

searching the compression table for a color string that matches the search string;

writing the search string to the prefix string to overwrite the prefix string when a matching color string is found; and

generating an identification string to associate with the search string;

writing the identification string and the search string to the compression table;

writing the identification string associated with the prefix string to the compressed image file; and

setting the prefix string to the pixel'"'"'s color value whenever a matching color string cannot be found.

22. The computer program product of claim 21, wherein the image quality value represents the maximum allowable difference between the search string and a color string stored in the compression table.

23. The computer program product of claim 22, wherein a color string stored in the compression table matches a search string when a distance metric between the color string and the search string is smaller than a function of the image quality value.

24. The computer program product of claim 23, wherein the distance metric is a perceptual color distance metric.