Lossy method for compressing images and video

• US 7,812,993 B2
• Filed: 04/25/2005
• Issued: 10/12/2010
• Est. Priority Date: 11/20/2000
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Hall Aluminum LLC (Intellectual Ventures LLC)
• Inventors: Bright, Walter G.
• Primary Examiner(s): Garcia; Gabriel I
• Application Number:
  US11/113,670
• Publication Number:
  US 20050190980A1
• Time in Patent Office: 1,996 Days
• Field of Search: 358/1.9, 358/1.18, 382/232, 382/236, 382/239, 345/420, 345/423
• US Class Current: 358/1.18
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A recursive scheme is employed to compress image data, wherein areas of a pixel grid corresponding to the image data are divided into increasingly smaller triangles based on the level of detail contained within each triangle. Data is stored defining each of the triangles and actual/predicted component values corresponding to pixels within each triangle. For each triangle, a set of predicted component values are determined, based on actual component values at the vertices of the triangle or actual component values on or proximate to the edges of the triangle. The predicted component values for the pixels are compared with the corresponding actual component values to see if a similarity threshold is met. If met, the processing of a current triangle is complete and the processing of a next triangle begins. If not, the current triangle is divided, and the foregoing process is then repeated. Texture mapping may also be applied.

Claims

1. A method, comprising:

predicting one or more pixel component values for one or more pixels of an area of an image, the image including one or more pixels with associated pixel component values to be compressed;

determining whether the predicted component values of the one or more pixels of the area of the image are similar to actual component values of the one or more pixels of the area of the image; and

dividing the area of the image into a plurality of sub-areas if the predicted component values are not similar to the actual component values.

2. The method of claim 1, wherein the predicting of the one or more pixel component values for one or more pixels of an area of an image comprises predicting the one or more pixel component values for one or more pixels of the area based at least in part on pixel component values of one or more pixels located at one or more boundary locations of the area.

3. The method of claim 2, wherein the area comprises a triangle, the one or more boundary locations comprise one or more vertices of the triangle, and dividing the area of the image into a plurality of sub-areas if the predicted component values are not similar to the actual component values comprises dividing the triangular area of the image into a plurality of triangles if the predicted component values are not similar to the actual component values.

4. The method of claim 1, further comprising dividing a region of the image into a plurality of areas.

5. The method of claim 1, further comprising dividing the image into a plurality of regions.

6. The method of claim 1, wherein the image comprises a grayscale image, and the predicted and/or actual component values comprise grayscale intensity levels.

7. The method of claim 1, wherein the image comprises a color image, and the one or more component values comprise three color component values, a Red component value, a Green component value, and/or a Blue component value, and the method further comprising converting the Red, Green, and/or Blue component values into luminance/chrominance component values.

8. The method of claim 7, wherein the determining of whether the predicted component values of the one or more pixels of the area of the image are similar to actual component values of the one or more pixels of the area of the image comprises comparing predicted and actual luminance component values and comparing predicted and actual chrominance component values, giving greater weight to the comparison of predicted and actual luminance component values than to the comparison of predicted and actual chrominance component values.

9. The method of claim 1, further comprising, after dividing the area of the image into a plurality of sub-areas, determining whether the predicted component values of the one or more pixels of the divided area of the image are similar to actual component values of the one or more pixels of the divided area of the image.

10. The method of claim 9, further comprising further dividing the divided area of the image into a further plurality of sub-areas if the predicted component values are not similar to the actual component values.

11. The method of claim 1, further comprising reiteratively dividing the area into further divided sub-areas, predicting component values, and comparing actual and predicted component values to determine if a similarity threshold is met for one or more sub-areas.

12. The method of claim 1, further comprising generating compressed image data from at least the predicted and actual component values.

13. The method of claim 1, further comprising applying texture mapping to pixels within the divided area of the image.

14. An apparatus, comprising:

a first module configured to predict one or more predicted pixel component values for one or more pixels of an area of an image having a number of pixels with associated pixel component values to be compressed;

a second module operatively coupled to the first module, and configured to determine whether the predicted component values of the one or more pixels of the area of the image are similar to actual component values of the one or more pixels of the area of the image; and

a third module operatively coupled to the second module, and configured to divide the area of the image into a plurality of sub-areas if the predicted component values are not similar to the actual component values.

15. The apparatus of claim 14, wherein the first module is configured to determine the one or more predicted pixel component values for one or more pixels of the area based at least in part on pixel component values of one or more pixels located at one or more boundary locations of the area.

16. The apparatus of claim 14, further comprising a fourth module operatively coupled to the first module, and configured to divide a region of the image into a plurality of areas.

17. The apparatus of claim 14, wherein the image comprises a color image, and the one or more component values comprise three color component values, a Red component value, a Green component value, and/or a Blue component value, and the method further comprising converting the Red, Green, and/or Blue component values into luminance/chrominance component values;

and the second module is configured to compare predicted and actual luminance component values, and predicted and actual chrominance component values, giving greater weight to the comparison of predicted and actual luminance component values.

18. The apparatus of claim 14 further comprising one or more processors, and at least one of the first and second modules is configured to be operated by the one or more processors.

19. An article of manufacture comprising:

storage medium; and

a plurality of programming instructions stored in the storage medium, designed to program an apparatus to enable the apparatus to perform operations including;

predicting one or more pixel component values for one or more pixels of an area of an image, the image including one or more pixels with associated pixel component values to be compressed;

determining whether the predicted component values of the one or more pixels of the area of the image are similar to actual component values of the one or more pixels of the area of the image; and

dividing the area of the image into a plurality of sub-areas if the predicted component values are not similar to the actual component values.

20. A component comprising

first logic configured to predict one or more predicted pixel component values for one or more pixels of an area of an image having a number of pixels with associated pixel component values to be compressed;

second logic operatively coupled to the first logic, and configured to determine whether the predicted component values of the one or more pixels of the area of the image are similar to actual component values of the one or more pixels of the area of the image; and

third logic operatively coupled to the second logic, and configured to divide the area of the image into a plurality of sub-areas if the predicted component values are not similar to the actual component values.

21. The component of claim 20, wherein the first logic is configured to determine the one or more predicted pixel component values for one or more pixels of the area based at least in part on pixel component values of one or more pixels located at one or more boundary locations of the area.