# US 2019/0320183 A1 · Encoding cost aware edge selection for improved progressive mesh compression

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

- Number: US 2019/0320183 A1
- Document ID: US20190320183A1
- Status: Published application
- Kind: A1
- Application number: 15/951,944
- Filed: 2018-04-12
- Published: 2019-10-17
- Earliest claimed: 2018-04-12
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Michael Hemmer; Pierre Alliez; Cedric Portaneri
- Web page: https://patentgrep.com/patent/US20190320183A1

## CPC

- G06T 9/00: Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00)
- H04N 19/14: Coding unit complexity, e.g. amount of activity or edge presence estimation (H04N19/146 takes precedence)
- G06T 9/001: {Model-based coding, e.g. wire frame}
- H04N 19/65: using error resilience
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

An encoder includes a processor and a memory. The encoder may perform a method of progressive compression. In one example implementation, the method may include determining a priority value for each edge of a plurality of edges, the priority value of an edge of the plurality of edges determined based on an error metric value and an estimated encoding cost associated with the edge. The method may further include determining a set of edges for collapse, the set of edges determined from the plurality of edges based on the priority values and collapsing the set of edges and generating vertex split information. In some implementations, the method may include entropy encoding the vertex split information.

## Claims

### Claim 1

A computer-implemented method of progressive mesh compression, comprising:
determining, by an encoder, a priority value for each edge of a plurality of edges, the priority value of an edge of the plurality of edges determined based on an error metric value and an estimated encoding cost associated with the edge;
determining, by the encoder, a set of edges for collapse, the set of edges determined from the plurality of edges based on the priority values; and
collapsing, by the encoder, the set of edges and generating vertex split information.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
entropy encoding, by the encoder, the vertex split information.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
transmitting, from the encoder, the generated vertex split information to a decoder in response to a message received from the decoder.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
determining, by the encoder, the error metric value associated with collapse of each edge of the plurality of edges; and
determining, by the encoder, the estimated encoding cost associated with collapse of each edge of the plurality of edges.

### Claim 5 (depends on 1)

The method of claim 1, wherein the estimated encoding cost associated with an edge is estimated based on determined residual values associated with the edge.

### Claim 6 (depends on 1)

The method of claim 1, wherein the estimated encoding cost associated with an edge is estimated based on determined residual values associated with the edge, and wherein the determined residual values are based on a determined correction value associated with a predicted vertex location and an actual vertex location.

### Claim 7 (depends on 1)

The method of claim 1, wherein the estimated encoding cost associated with the edge is estimated based on determined residual values associated with the edge, and wherein the determined residual values are based on an estimated length of an associated residual vector.

### Claim 8 (depends on 1)

The method of claim 1, wherein determining the set of edges for collapse based on the priority values further comprises:
determining an independent set of edges for collapse based on the priority values, and each edge of the independent set of edges not blocked by other edges of the plurality of edges.

### Claim 9 (depends on 1)

The method of claim 1, wherein the collapse of an edge further comprises:
collapsing the edge using a full-edge or a half-edge collapse operation.

### Claim 10

An encoder, comprising:
a processor; and
a memory, the memory including instructions configured to cause the processor to:
determine a priority value for each edge of a plurality of edges, the priority value of an edge of the plurality of edges determined based on an error metric value and an estimated encoding cost associated with the edge;
determine a set of edges for collapse, the set of edges determined from the plurality of edges based on the priority values; and
collapse the set of edges and generating vertex split information.

### Claim 11 (depends on 10)

The encoder of claim 10, further comprising instructions to cause the processor to:
entropy encode the vertex split information.

### Claim 12 (depends on 10)

The encoder of claim 10, further comprising instructions to cause the processor to:
transmit the generated vertex split information to a decoder in response to a message received from the decoder.

### Claim 13 (depends on 10)

The encoder of claim 10, further comprising instructions to cause the processor to:
determine the error metric value associated with collapse of each edge of the plurality of edges; and
determine the estimated encoding cost associated with collapse of each edge of the plurality of edges.

### Claim 14 (depends on 10)

The encoder of claim 10, wherein the estimated encoding cost associated with an edge is estimated based on determined residual values associated with the edge.

### Claim 15

A non-transitory computer-readable storage medium having stored thereon computer executable program code which, when executed on a computer system, causes the computer system to perform a method of progressive mesh compression, comprising:
determining, by an encoder, a priority value for each edge of a plurality of edges, the priority value of an edge of the plurality of edges determined based on an error metric value and an estimated encoding cost associated with the edge;
determining, by the encoder, a set of edges for collapse, the set of edges determined from the plurality of edges based on the priority values; and
collapsing, by the encoder, the set of edges and generating vertex split information.

### Claim 16 (depends on 15)

The computer-readable storage medium of claim 15, further comprising code for:
entropy encoding, by the encoder, the vertex split information.

### Claim 17 (depends on 15)

The computer-readable storage medium of claim 15, further comprising code for:
transmitting, from the encoder, the generated vertex split information to a decoder in response to a message received from the decoder.

### Claim 18 (depends on 15)

The computer-readable storage medium of claim 15, further comprising code for:
determining, by the encoder, the error metric value associated with collapse of each edge of the plurality of edges; and
determining, by the encoder, the estimated encoding cost associated with collapse of each edge of the plurality of edges.

### Claim 19 (depends on 15)

The computer-readable storage medium of claim 15, wherein the estimated encoding cost associated with an edge is estimated based on determined residual values associated with the edge.

### Claim 20 (depends on 15)

The computer-readable storage medium of claim 15, wherein the estimated encoding cost associated with an edge is estimated based on determined residual values associated with the edge, and wherein the determined residual values are based on a determined correction value associated with a predicted vertex location and an actual vertex location.