Lossy method for compressing pictures and video
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
30 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (26, 27, 28, 29, 30)
-
Specification