Data compression system and technique

• US 6,983,074 B1
• Filed: 06/14/2001
• Issued: 01/03/2006
• Est. Priority Date: 06/14/2000
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Clauson, Jon D., Hondl, Christopher P.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/880,085
• Time in Patent Office: 1,664 Days
• Field of Search: 382/166, 382244-246, 382/253, 382162-167, 382/239, 382/243, 358/3.05, 358/504, 358/539, 358/578, 358/119, 345/589, 345/597, 345600-611, 345/569, 341/95, 341 50- 51, 341106-107, 341/60, 341/65, 341/87, 341/67, 348/409.1, 348/421
• US Class Current: 382/244
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04N 1/644 using a reduced set of representative colours, e.g. each representing a particular range in a colour space

Abstract

Methods and apparatus, including computer program products, are used to compress a true color image in such a way that the compressed image may be decompressed by a decompression method according to a dictionary-based compression technique. A color table defines a mapping from true colors to index color values. A set of zero or more candidate strings for a current pixel in the image is identified in a compression dictionary. Each candidate string corresponds to a string of pixels in the image, with the last pixel of the string corresponding to the current pixel. Each candidate string approximately matches the corresponding image pixel string. If the set of candidate strings for the current pixel is empty, one of the candidate strings for the previous current pixel is selected, and a code for the selected string is added to a compressed representation of the image.

Claims

1. A method for compressing an image, the method comprising:

receiving an image, the image being defined by pixels, each pixel having a true color, for decompression by a selected dictionary-based decompression technique;

receiving a color table that defines a mapping from true colors to index color values;

identifying a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identifying in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in a image, the last pixel of the string corresponding to the current pixel, and each candidate string approximately matching a corresponding image string; and

if the set of candidate strings for the current pixel is empty, selecting one of the candidate strings for the previous current pixel, and adding a code for the selected string to a compressed representation of the image.

2. The method of claim 1, wherein the compressed representation is embedded in a GIF file.

3. The method of claim 1, wherein two strings are an approximate match, if at each string position the true color from one of the two strings approximately matches the true color from another of the two strings.

4. The method of claim 3, wherein two colors are approximate matches if a distance between them is less than a threshold.

5. The method of claim 4, wherein the distance between two colors is measured using a standard Euclidean distance metric.

6. The method of claim 4, wherein the distance between two colors is measured using a weighted Euclidean distance metric.

7. The method of claim 4, wherein the threshold varies across the image.

8. The method of claim 1, wherein two strings are approximate matches if an aggregate distance between the two strings is less than a threshold value.

9. The method of claim 1, wherein the selected dictionary-based compression technique implements an LZW algorithm.

10. The method of claim 9, wherein the candidate string that is selected is a string whose selection causes a minimum increase in a size of an LZW dictionary.

11. The method of claim 1, further comprising:

calculating an error amount between the true color of the candidate string pixel corresponding to the current pixel and the true color of the current pixel; and

distributing the error amount to modify pixels in the image before processing them for compression.

12. The method of claim 11, wherein the error amount is distributed according to an error diffusion technique.

13. The method of claim 12, wherein the error diffusion technique is a Floyd-Steinberg technique.

15. The method of claim 11, further comprising receiving a prefix string and setting the prefix string to the selected candidate string.

16. The method of claim 11, wherein if the set of candidate strings for the current pixel is empty then the added code maps to a string that includes a current prefix string plus a selected index color value that is selected from the index color value as corresponding to the true color value nearest to the true color of the pixel.

17. The method of claim 16, wherein the current prefix string is a selected index color value for a previous current pixel.

18. The method of claim 16, wherein the current prefix string is a selected candidate string for a previous current pixel.

14. A method of compressing an image defined by pixels, each pixel having a true color, for decompression by a selected dictionary-based decompression technique, the method comprising:

receiving the image;

identifying a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

receiving a color table that defines a mapping from true colors to index color values;

identifying in a compression dictionary a set of zero or more candidate strings for a current pixel in the image, each candidate string corresponding to a concatenation of a candidate prefix string related to previous current pixels and an index color value related to the current pixel, in which the candidate prefix string exactly matches a prefix string in the compression dictionary and in which the index color value is an indication of true color in the color table that is an approximate match to a true color value of the current pixel in the image; and

selecting one of the candidate strings for the previous current pixel if the set of candidate strings for the current pixel is empty, and adding a code for the selected string to a compressed representation of the image.

19. A computer program product, tangibly stored on a machine-readable medium for compressing an image defined by pixels, each pixel having a true color, the compressed image able to be decompressed by a selected dictionary-based decompression technique, the product comprising instructions operable to cause a programmable processor to:

receive the image;

receive a color table that defines a mapping from true colors to index color values;

identify a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identify in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image, a last pixel of the string corresponding to the current pixel, and each candidate string approximately matching the corresponding image string;

if the set of candidate strings for the current pixel is empty, select one of the candidate strings for the previous current pixel, and add a code for the selected string to a compressed representation of the image.

20. The computer program product of claim 19, wherein the compressed representation is embedded in a GIF file.

21. The computer program product of claim 19, wherein two strings are an approximate match, if at each string position the true color from one of the two strings approximately matches the true color from another of the two strings.

22. The computer program product of claim 21, wherein two colors are approximate matches if a distance between them is less than a threshold.

23. The computer program product of claim 22, wherein the distance between two colors is measured using a standard Euclidean distance metric.

24. The computer program product of claim 22, wherein the distance between two colors is measured using a weighted Euclidean distance metric.

25. The computer program product of claim 22, wherein the threshold varies across the image.

26. The computer program product of claim 19, wherein two strings are approximate matches if an aggregate distance between the two strings is less than a threshold value.

27. The computer program product of claim 19, wherein the selected dictionary-based compression technique implements an LZW algorithm.

28. The computer program product of claim 27, wherein the candidate string that is selected is a string whose selection causes a minimum increase in the size of an LZW dictionary.

29. The computer program product of claim 19, further comprising instructions operable to cause a programmable processor to:

calculate an error amount between the true color of the candidate string pixel corresponding to the current pixel and the true color of the current pixel; and

distribute the error amount to modify pixels in the image before processing them for compression.

30. The computer program product of claim 29, wherein the error amount is distributed according to an error diffusion technique.

31. The computer program product of claim 30, wherein the error diffusion technique is a Floyd-Steinberg technique.

32. A system comprising a computer-readable storage medium tangibly embodying program instructions for compressing an image defined by pixels, each pixel having a true color, the compressed image able to be decompressed by a selected dictionary-based decompression technique, the program instructions including instructions operable to cause a programmable processor to:

receive the image;

receive a color table that defines a mapping from true colors to index color values;

identify a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identify in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image, a last pixel of the string corresponding to the current pixel, and each candidate string approximately matching the corresponding image string;

if the set of candidate strings for the current pixel is empty, select one of the candidate strings for the previous current pixel, and add a code for the selected string to a compressed representation of the image.

33. The system of claim 32, wherein the compressed representation is embedded in a GIF file.

34. The system of claim 32, wherein two strings are an approximate match, if at each string position the true color from one of the strings approximately matches the true color from the other of the strings.

35. The system of claim 34, wherein two colors are approximate matches if a distance between them is less than a threshold.

36. The system of claim 35, wherein the distance between two colors is measured using a standard Euclidean distance metric.

37. The system of claim 35, wherein the distance between two colors is measured using a weighted Euclidean distance metric.

38. The system of claim 35, wherein the threshold varies across the image.

39. The system of claim 32, wherein two strings are approximate matches if an aggregate distance between the two strings is less than a threshold value.

40. The system of claim 32, wherein the selected dictionary-based compression technique implements an LZW algorithm.

41. The system of claim 40, wherein the candidate string that is selected is a string whose selection causes a minimum increase in the size of an LZW dictionary.

42. The system of claim 32, wherein the program instructions further include instructions operable to cause a programmable processor to:

calculate an error amount between the true color of the candidate string pixel corresponding to the current pixel and the true color of the current pixel; and

distribute the error amount to modify pixels in the image before processing them for compression.

43. The system of claim 42, wherein the error amount is distributed according to an error diffusion technique.

44. The system of claim 43, wherein the error diffusion technique is a Floyd-Steinberg technique.

45. A method of compressing a raster image, for decompression using the LZW algorithm, the method comprising:

receiving the image represented as a raster of original true color values;

receiving a color table that defines a mapping from each true color in a palette of true colors to an index;

identifying a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identifying in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image and satisfying a string match condition with the corresponding string of pixels in the image, the string match condition being satisfied by an exact or an approximate matching of two strings according to the true color values of their pixels; and

if the set of candidate strings for the current pixel is empty, selecting one of the candidate strings for the previous current pixel, and adding a code representing the selected candidate string to a compressed representation of the image.

46. A method of claim 45, wherein a last pixel of the string corresponds to the current pixel and has a true color that is one of the palette colors, the true color of the last pixel of the string satisfying a pixel match condition with a base color of the current pixel, the base color of the current pixel being a true color derived from the original true color of the current pixel, the pixel match condition being satisfied by an exact or an approximate matching of two true colors.

47. The method of claim 46, wherein the base color of the current pixel is the same as the original true color of the current pixel.

48. The method of claim 46, wherein the base color of the current pixel is the original true color of the current pixel plus or minus an error value.

49. The method of claim 45, wherein the pixels of the string are represented in the string by indices from the color table.

50. The method of claim 45, wherein the string match condition is satisfied if at each string position the true color from one of the two strings approximately matches the true color from another of the two strings.

51. The method of claim 45, wherein the string match condition is satisfied if an aggregate distance between the two strings is less than a threshold value.

52. The method of claim 45, wherein the candidate string that is selected is a string whose selection causes a minimum increase in the size of a compression dictionary.

53. A method of compressing a raster image, for decompression by a selected dictionary-based decompression technique, the method comprising:

receiving an image represented as a raster of original true color values;

receiving a color table that defines a mapping from each true color in a palette of true colors to an index;

identifying a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identifying in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image and satisfying a string match condition with the corresponding string of pixels in the image, the string match condition being satisfied by an exact or an approximate matching of two strings according to the true color values of their pixels;

if the set of candidate strings for the current pixel is empty, selecting one of the candidate strings for the previous current pixel, and adding a code representing the selected candidate string to a compressed representation of the image;

calculating an error amount between the true color of the candidate string pixel corresponding to the current pixel and the true color of the current pixel; and

distributing the error amount to modify a base color of one or more pixels in the image, the base color of a pixel being a true color derived from the original true color of the pixel.

54. The method of claim 53, wherein the error value is distributed according to an error diffusion technique.

55. The method of claim 54, wherein the error diffusion technique is a Floyd-Steinberg technique.

56. A method of claim 53, wherein a last pixel of the string corresponds to the current pixel and has a true color that is one of the palette colors, the true color of the last pixel of the string satisfying a pixel match condition with the base color of the current pixel, the pixel match condition being satisfied by an exact or an approximate matching of two true colors.

57. The method of claim 56, wherein the base color of the current pixel is the same as the original true color of the current pixel.

58. The method of claim 56, wherein the base color of the current pixel is the original true color of the current pixel plus or minus an error value determined by one or more error amounts.

59. A computer program product, tangibly stored on a machine-readable medium for compressing a raster image, for decompression using the LZW algorithm, the product comprising instructions operable to cause a programmable processor to:

receive an image represented as a raster of original true color values;

receive a color table that defines a mapping from each true color in a palette of true colors to an index;

identify a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identify in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image and satisfying a string match condition with the corresponding string of pixels in the image, the string match condition being satisfied by an exact or an approximate matching of two strings according to the true color values of their pixels; and

if the set of candidate strings for the current pixel is empty, select one of the candidate strings for the previous current pixel, and add a code representing the selected candidate string to a compressed representation of the image.

60. A computer program product, tangibly stored on a machine-readable medium for compressing a raster image, for decompression by a selected dictionary-based decompression technique, the product comprising instructions operable to cause a programmable processor to:

receive an image represented as a raster of original true color values;

receive a color table that defines a mapping from each true color in a palette of true colors to an index;

identify a current pixel in the image, in which the current pixel is associated with exactly one previous current pixel;

identify in a compression dictionary a set of zero or more candidate strings for the current pixel in the image, each candidate string corresponding to a string of pixels in the image and satisfying a string match condition with the corresponding string of pixels in the image, the string match condition being satisfied by an exact or an approximate matching of two strings according to the true color values of their pixels;

if the set of candidate strings for the current pixel is empty, select one of the candidate strings for the previous current pixel, and add a code representing the selected candidate string to a compressed representation of the image;

calculate an error amount between the true color of the candidate string pixel corresponding to the current pixel and the true color of the current pixel; and

distribute the error amount to modify a base color of one or more pixels in the image, the base color of a pixel being a true color derived from the original true color of the pixel.