Lossy method for compressing pictures and video

• US 6,897,977 B1
• Filed: 11/20/2000
• Issued: 05/24/2005
• Est. Priority Date: 11/20/2000
• Status: Expired due to Term

• 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:
  US09/718,879
• Time in Patent Office: 1,646 Days
• Field of Search: 358/1.1, 358/1.15, 358/1.12, 358/1.13, 358/1.9, 382/232, 382/242, 382/243, 345/420, 345/418
• 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 for compressing image data corresponding to an image comprising a plurality of pixels defining a grid, each pixel having at least one component value, comprising:

dividing the grid into at least one rectangular area;

for each rectangular area;

dividing the rectangular area into a number of triangles, each triangle defining a boundary comprising three edges;

for each of triangle;

identifying the vertices of the triangle;

determining predicted pixel component values for at least a portion of the pixels enclosed within and/or on the boundary of the triangle;

comparing the predicted pixel component values with actual values of said at least one component value to determine if a similarity threshold is met;

processing a next triangle if the similarity threshold is met, otherwise,

dividing the triangle into two new triangles, each

defining a boundary and comprising three edges; and

reiteratively repeating identifying the vertices, predicting pixel component values, and comparing actual and predicted pixel component values to determine if a similarity threshold is met for each existing triangle and any new triangles that are created; and

generating compressed image data defining each triangle that is created and actual and predicted pixel component values within the triangle.

2. The method of claim 1, wherein the compressed image data comprises at least one string, the method further comprising compressing said at least one string using a data compression algorithm.

3. The method of claim 1, wherein at least a portion of the triangles are defined by data identifying pixels coincident with or proximate to a set of vertices for the triangle, and the predicted pixel component values for those triangles are determined by interpolating actual pixel component values at the vertices of each triangle.

4. The method of claim 1, wherein the predicted pixel component values are determined by interpolating actual component values corresponding to pixels that lie on and/or proximate to the edges of each triangle.

5. The method of claim 1, wherein the image is a grayscale image, and said at least one component value comprises a grayscale intensity level.

6. The method of claim 1, wherein the image comprises a color image, and said at least one component value comprises three color component values.

7. The method of claim 6, wherein the three color component values comprise a Red component value, a Green component value, and a Blue component value, further comprising converting the Red, Green, and Blue component values into luminance/chrominance component values.

8. The method of claim 7, wherein said comparing of the predicted pixel component values to determine if the similarity threshold is met comprises giving a similarity determination that compares predicted and actual luminance component values greater weight than a similarity determination that considers predicted and actual chrominance component values.

9. The method of claim 1, further comprising:

determining if a texture map can be applied to pixels of a given triangle to meet the similarity threshold; and

storing data identifying the pixels within and/or on the triangle boundary and data corresponding to the texture map for any triangle for which it is determined that texture mapping can be applied.

10. The method of claim 1, wherein each of said at least one rectangle comprises a square.

11. The method of claim 10, wherein the image comprises a plurality of pixels contained within a rectangular grid, and wherein the rectangular grid is divided into a number of non-overlapping squares that contain all of the pixels within the rectangular grid.

12. The method of claim 1, wherein at least one triangle comprises a right angle corner and a hypotenuse, and where dividing said at least one triangle into two triangles comprises dividing said at least one triangle along a line connecting a midpoint of the hypotenuse to the right angle corner.

13. A method for reproducing an image based on a set of compressed image data corresponding to an original image comprising a plurality of pixels defining a grid, said compressed image data including data defining a plurality of triangles and pixel component values corresponding to each of said plurality of triangles, comprising:

extracting a first set of vertices for a first of the triangles;

determining first component values of pixels within the first triangle;

rendering first triangle in accord with the first set of vertices and first component values determined for the first triangle;

extracting a second set of vertices for a second of the triangles, the second triangle being nested within the first triangle;

determining second component values of pixels within the second triangle;

rendering the second triangle in accord with the second set of vertices and second component values determined for the second triangle.

14. The method of claim 13, wherein at least either the first component values are determined as a function of component values at the first vertices of the first triangle, or the second component values are determined as a function of component values at the second vertices of the second triangle.

15. The method of claim 14, wherein at least either the first component values are determined by interpolating component values at the first vertices of the first triangle, or the second component values are determined by interpolating component values at the second vertices of the second triangle.

16. The method of claim 13, wherein at least either the first component values are determined as a function of component values corresponding to pixels defining first edges of the first triangle, or the second component values are determined as a function of component values corresponding to pixels defining second edges of the second triangle.

17. The method of claim 13, further including:

applying texture mapping to the pixels contained within the second triangles.

18. The method of claim 13, wherein said determining of first and second component values include converting respective first and second luminance/chrominance color model data to first and second red, green and blue (RGB) color components for the pixels of the first and second triangles.

19. A system for compressing image data corresponding to an image comprising a plurality of pixels defining a grid, each pixel having at least one component value, comprising:

a memory in which machine instructions are stored; and

a processor coupled to the memory for executing the machine instructions, said processor implementing a plurality of functions when executing the machine instructions, including;

dividing the grid into at least one rectangular area;

for each rectangular area;

dividing the rectangular area into a number of triangles, each triangle defining a boundary comprising three edges;

for each of triangle;

identifying the vertices of the triangle;

determining predicted pixel component values for at least a portion of the pixels enclosed within and/or on the boundary of the triangle;

comparing the predicted pixel component values with actual values of said at least one component value to determine if a similarity threshold is met;

processing a next triangle if the similarity threshold is met, otherwise,

dividing the triangle into two new triangles, each

defining a boundary and comprising three edges; and

reiteratively repeating identifying the vertices, predicting pixel component values, and comparing actual and predicted pixel component values for each existing triangle and any new triangles that are created; and

generating compressed image data defining each triangle that is created and actual and predicted pixel component values within the triangle.

20. The system of claim 19, wherein at least a portion of the triangles are defined by data identifying pixels coincident with or proximate to a set of vertices for the triangle, and the predicted pixel component values are determined by interpolating actual pixel component values at the vertices of each triangle.

21. The system of claim 19, wherein the predicted pixel component values are determined by interpolating actual component values corresponding to pixels that lie on and/or proximate to the edges of each triangle.

22. The system of claim 19, wherein the image comprises a color image, and said at least one component value comprises a Red component value, a Green component value, and a Blue component value, and wherein execution of the machine instructions by the processor further implements the function of converting the Red, Green, and Blue component values into luminance/chrominance component values.

23. The system of claim 19, wherein execution of the machine instructions by the processor further implements the functions of:

determining if a texture map can be applied to pixels of a given triangle to meet the similarity threshold; and

storing data identifying the pixels within and/or on the triangle boundary and data corresponding to the texture map for any triangle for which it is determined that texture mapping can be applied.

24. The system of claim 19, wherein the image comprises a plurality of pixels contained within a rectangular grid, and wherein the rectangular grid is divided into a minimum number of non-overlapping squares that contain all of the pixels within the rectangular grid.

25. An article of manufacture for compressing image data corresponding to an image comprising a plurality of pixels defining a grid, each pixel having at least one component value, comprising:

a memory media adapted to be used with a computer; and

a plurality of machine instructions stored on the memory media, said machine instructions effecting a plurality of functions when executed by the computer, including;

dividing the grid into at least one rectangular area;

for each rectangular area;

dividing the rectangular area into a number of triangles, each triangle defining a boundary comprising three edges;

for each of triangle;

identifying the vertices of the triangle;

determining predicted pixel component values for at least a portion of the pixels enclosed within and/or on the boundary of the triangle;

comparing the predicted pixel component values with actual values of said at least one component value to determine if a similarity threshold is met;

processing a next triangle if the similarity threshold is met, otherwise,

dividing the triangle into two new triangles, each defining a boundary and comprising three edges; and

reiteratively repeating identifying the vertices, predicting pixel component values, and comparing actual and predicted pixel component values for each existing triangle and any new triangles that are created; and

generating compressed image data defining each triangle that is created and actual and predicted pixel component values within the triangle.

26. The article of manufacture of claim 25, wherein at least a portion of the triangles are defined by data identifying pixels coincident with or proximate to a set of vertices for the triangle, and the predicted pixel component values are determined by interpolating actual pixel component values at the vertices of each triangle.

27. The article of manufacture of claim 25, wherein the predicted pixel component values are determined by interpolating actual component values corresponding to pixels that lie on and/or proximate to the edges of each triangle.

28. The article of manufacture of claim 25, wherein the image comprises a color image, and said at least one component value comprises a Red component value, a Green component value, and a Blue component value, and wherein said functions effectuated when executed by the computer further include the function of converting the Red, Green, and Blue component values into luminance/chrominance component values.

29. The article of manufacture of claim 25, wherein said functions effectuated when executed by the computer further include the functions of:

determining if a texture map can be applied to pixels of a given triangle to meet the similarity threshold; and

storing data identifying the pixels within and/or on the triangle boundary and data corresponding to the texture map for any triangle for which it is determined that texture mapping can be applied.

30. The article of manufacture of claim 25, wherein the image comprises a plurality of pixels contained within a rectangular grid, and wherein the rectangular grid is divided into a minimum number of non-overlapping squares that contain all of the pixels within the rectangular grid.