Encoding cost aware edge selection for improved progressive mesh compression

• US 10,659,789 B2
• Filed: 04/12/2018
• Issued: 05/19/2020
• Est. Priority Date: 04/12/2018
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hemmer, Michael, Alliez, Pierre, Portaneri, Cedric
• Primary Examiner(s): Mariam, Daniel G
• Application Number:
  US15/951,944
• Publication Number:
  US 20190320183A1
• Time in Patent Office: 768 Days
• Field of Search: 382244, 382232
• CPC Class Codes: 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
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/65 using error resilience

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

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 based on a residual value 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.

2. The method of claim 1, further comprising:

entropy encoding, by the encoder, the vertex split information.

3. 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.

4. 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.

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

6. The method of claim 1, wherein the residual values are based on an estimated length of an associated residual vector.

7. 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.

8. 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.

9. 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 based on a residual value 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.

10. The encoder of claim 9, further comprising instructions to cause the processor to:

entropy encode the vertex split information.

11. The encoder of claim 9, 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.

12. The encoder of claim 9, 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.

13. 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 based on a residual value 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.

14. The computer-readable storage medium of claim 13, further comprising code for:

entropy encoding, by the encoder, the vertex split information.

15. The computer-readable storage medium of claim 13, 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.

16. The computer-readable storage medium of claim 13, 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.

17. The computer-readable storage medium of claim 13, wherein the residual values are based on a determined correction value associated with a predicted vertex location and an actual vertex location.