# US 2019/0356931 A1 · Image compression and decompression using triangulation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0356931 A1
- Document ID: US20190356931A1
- Status: Published application
- Kind: A1
- Application number: 16/413,992
- Filed: 2019-05-16
- Published: 2019-11-21
- Earliest claimed: 2018-05-17
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: David Marwood; Michele Covell; Shumeet Baluja; Nicholas Milo Johnston; Pascal Massimino
- Web page: https://patentgrep.com/patent/US20190356931A1

## CPC

- H04N 19/119: Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
- H04N 19/90: using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- G06T 9/001: {Model-based coding, e.g. wire frame}
- H04N 19/154: Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion (use of rate-distortion criteria H04N19/147)
- H04N 19/172: the region being a picture, frame or field
- H04N 19/176: the region being a block, e.g. a macroblock
- H04N 19/186: the unit being a colour or a chrominance component
- H04N 19/132: Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
- H04N 19/17: the unit being an image region, e.g. an object
- H04N 19/192: the adaptation method, adaptation tool or adaptation type being iterative or recursive
- H04N 19/20: using video object coding
- H04N 19/54: using feature points or meshes
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

An encoder system can include a pixel grid generator to receive an image having a first dimension, generate a grid having a second dimension, add a plurality of points to positions on the grid, and map a plurality of pixels of the image to the plurality of points. The encoder system can include a color module to assign a color to each of the plurality of points using a color table, a triangulation module to generate a plurality of vertices based on the plurality of points and triangulate the grid using the vertices, and a compression module to compress the vertices as a set of compressed vertex positions and a set of vertex colors.

## Claims

### Claim 1

An encoder system comprising:
a pixel grid generator configured to:
receive an image having a first dimension,
generate a grid having a second dimension,
add a plurality of points to positions on the grid, and
map a plurality of pixels of the image to the plurality of points;
a color module configured to assign a color to each of the plurality of points using a color table;
a triangulation module configured to generate a plurality of vertices based on the plurality of points and triangulate the grid using the vertices; and
a compression module configured to compress the vertices as a set of compressed vertex positions and a set of vertex colors.

### Claim 2 (depends on 1)

The encoder system of claim 1, wherein the second dimension is between four (4) and 400 times smaller than the first dimension.

### Claim 3 (depends on 1)

The encoder system of claim 1, wherein
the second dimension is M,
the grid includes M columns and M rows,
the positions on the grid are located at each block of the grid, a block being at an intersection of a row and a column of the grid, and
the adding of the plurality of points to the positions on the grid includes one of inserting a point at each of the positions on the grid or inserting the plurality of points at a portion of the positions on the grid.

### Claim 4 (depends on 1)

The encoder system of claim 1, wherein
the received image is a first image,
the second dimension is M,
the grid includes M columns and M rows,
the positions on the grid are located at each block of the grid, a block being at an intersection of a row and a column of the grid, and
the adding of the plurality of points to the positions on the grid includes:
inserting a threshold number of points into random positions on the grid,
generating a second image using the points on the grid,
comparing the second image to the first image, and
in response to determining the comparison results in a quality that is greater than a threshold quality difference, the threshold number of points are repositioned on the grid.

### Claim 5 (depends on 1)

The encoder system of claim 1, wherein
the color table is generated based on the received image, and
the color table includes between 8 and 16 colors.

### Claim 6 (depends on 1)

The encoder system of claim 1, wherein
the color table is generated based on the received image, and
the color table includes 6 colors.

### Claim 7 (depends on 1)

The encoder system of claim 1, wherein the triangulation module uses a Delaunay Triangulation technique to triangulate the grid.

### Claim 8 (depends on 1)

The encoder system of claim 1, wherein the received image is a first image, the encoder system further comprising:
an image generator configured to generate a second image using the triangulated grid and a color associated with the vertices, wherein
the generating of the second image includes painting triangles generated by the triangulation module based on a color associated with each a plurality of vertices.

### Claim 9 (depends on 1)

The encoder system of claim 1, wherein the received image is a first image, the encoder system further comprising:
an image generator configured to generate a second image using the triangulated grid and a color associate with the vertices; and
a test module configured to:
perform a quality test based on the first image and the second image,
determine whether the second image satisfies at least one criterion based on the quality test and a size of the second image, wherein the at least one criterion includes a maximum size and quality error,
in response to determining the second image does not satisfy the at least one criterion, select a vertex from the plurality of vertices and remove the selected vertex from the plurality of vertices and return processing to the triangulation module.

### Claim 10 (depends on 1)

The encoder system of claim 1, wherein the received image is a first image, the encoder system further comprising:
an image generator configured to generate a second image using the triangulated grid and a color associate with the vertices; and
a test module configured to:
perform a quality test based on the first image and the second image,
determine whether the second image satisfies at least one criterion based on the quality test and a size of the second image, wherein the at least one criterion includes a maximum size and quality error,
in response to determining the second image does not satisfy the at least one criterion, at least one of:
displacing a vertex of the plurality vertices,
adding a vertex to the plurality vertices,
removing a vertex from the plurality of vertices,
reassigning the color associated with at least one of the plurality of points,
removing one of the colors of the color table, and
modifying one of the colors of the color table, and
return processing to the triangulation module.

### Claim 11

A method of compressing an image, the method comprising:
receiving an image having a first dimension;
generating a grid having a second dimension;
adding a plurality of points to positions on the grid;
mapping a plurality of pixels of the image to the plurality of points;
assigning a color to each of the plurality of points using a color table;
generating a plurality of vertices based on the plurality of points;
triangulating the grid using the vertices; and
compressing the vertices as a set of compressed vertex positions and a set of vertex colors.

### Claim 12 (depends on 11)

The method of claim 11, wherein
the second dimension is M,
the grid includes M columns and M rows,
the positions on the grid are located at each block of the grid, a block being at an intersection of a row and a column of the grid, and
the adding of the plurality of points to the positions on the grid includes one of inserting a point at each of the positions on the grid or inserting the plurality of points at a portion of the positions on the grid.

### Claim 13 (depends on 11)

The method of claim 11, wherein
the received image is a first image,
the second dimension is M,
the grid includes M columns and M rows,
the positions on the grid are located at each block of the grid, a block being at an intersection of a row and a column of the grid, and
the adding of the plurality of points to the positions on the grid includes:
inserting a threshold number of points into random positions on the grid,
generating a second image using the points on the grid,
comparing the second image to the first image, and
in response to determining the comparison results in a quality that is greater than a threshold quality difference, the threshold number of points are repositioned on the grid.

### Claim 14 (depends on 11)

The method of claim 11, wherein the triangulation uses a Delaunay Triangulation technique to triangulate the grid.

### Claim 15 (depends on 11)

The method of claim 11, wherein the received image is a first image, the method further comprising:
generating a second image using the triangulated grid and a color associated with the vertices, wherein
the generating of the second image includes painting triangles generated by the triangulation based on a color associated with each a plurality of vertices.

### Claim 16 (depends on 11)

The method of claim 11, wherein the received image is a first image, the method further comprising:
generating a second image using the triangulated grid and a color associate with the vertices;
performing a quality test based on the first image and the second image;
determining whether the second image satisfies at least one criterion based on the quality test and a size of the second image, wherein the at least one criterion includes a maximum size and a quality error;
in response to determining the second image does not satisfy the at least one criterion, selecting a vertex from the plurality of vertices and removing the selected vertex from the plurality of vertices; and
returning to the triangulating step.

### Claim 17 (depends on 11)

The method of claim 11, wherein the received image is a first image, the method further comprising:
generating a second image using the triangulated grid and a color associate with the vertices;
performing a quality test based on the first image and the second image;
determining whether the second image satisfies at least one criterion based on the quality test and a size of the second image, wherein the at least one criterion includes a maximum size and quality error;
in response to determining the second image does not satisfy the at least one criterion, at least one of:
displacing a vertex of the plurality vertices,
adding a vertex to the plurality vertices,
removing a vertex from the plurality of vertices,
reassigning the color associated with at least one of the plurality of points,
removing one of the colors of the color table, and
modifying one of the colors of the color table, and returning to the triangulating step.

### Claim 18

A method of decompressing a compressed image, the method comprising:
receiving a compressed image file, the compressed image file including at least one of a header, a compressed color table, a compressed color table index, and a compressed triangulation;
decompressing at least one of the compressed color table, the compressed color table index, and the compressed triangulation;
generating a grid having an M×M dimension based on a grid size;
assigning one of a plurality points to each position of the grid based on the decompressed triangulation file;
assigning a color index value to each of the plurality of points based on the decompressed triangulation file;
mapping a color to each of the plurality of points based on an associated color index value;
triangulating the grid using the plurality of points as vertices; and
generating a reconstructed image based on the vertices and triangles associated with the triangulation.

### Claim 19 (depends on 18)

The method of claim 18, comprising:
improving a quality associated with the reconstructed image using Stacked-Hourglass network, wherein
the Stacked-Hourglass network includes at least two hourglasses, and an intermediate supervision is applied using an intermediate loss module that can be split off an output of each Hourglass.

### Claim 20 (depends on 18)

The method of claim 18, wherein
generating the reconstructed image includes painting triangles generated by the triangulation based on a color associated with each a plurality of vertices, and
at least one of the triangles generated by the triangulation painted using an interpolation technique.