2D mesh geometry and motion vector compression

• US 6,047,088 A
• Filed: 10/01/1997
• Issued: 04/04/2000
• Est. Priority Date: 12/16/1996
• Status: Expired due to Term

• Current Assignee: Rakuten, Inc. (Rakuten Group, Inc.)
• Original Assignee: Sharp Laboratories of America Incorporated (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Van Beek, Petrus J. L., Tekalp, Ahmet Murat
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US08/942,313
• Time in Patent Office: 916 Days
• Field of Search: 382/232, 382/236, 382/244, 382/243, 382/253, 382/233, 382/238
• US Class Current: 382/243
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/517 by encoding
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques

Abstract

A system and method of encoding and decoding a dynamic mesh includes encoding and decoding a mesh geometry of a set of node points and encoding and decoding a mesh node motion vector for each node point.

Claims

1. A method of encoding and decoding a dynamic mesh having a temporal sequence of mesh models, comprising:

encoding and decoding a first mesh model in the temporal sequence of the dynamic mesh, by encoding and decoding the geometry of a set of mesh node points in the first mesh model; and

encoding and decoding subsequent mesh models in the temporal sequence of the dynamic mesh, by encoding and decoding the deformable motion of each mesh model, represented by a mesh node motion vector for each node point.

2. The method of claim 1 wherein said encoding and decoding of a mesh geometry includes compressing a mesh topology of a Delaunay type.

3. The method of claim 1 wherein said encoding and decoding of a mesh geometry includes compressing a mesh topology of a uniform type.

4. The method of claim 1 wherein said encoding and decoding of the deformable motion of a mesh model includes:

compressing the motion vectors for each node point using a linear traversal of the node points that is independent of a triangular mesh topology; and

predicting, using at least first order prediction, subsequent motion vectors for each node point.

5. The method of claim 4 wherein said predicting includes encoding and decoding prediction errors using variable length codes.

6. The method of claim 4 which includes traversing and ordering the mesh node points for a Delaunay type mesh.

7. The method of claim 4 which includes traversing and ordering the mesh node points for a uniform type mesh.

8. The method of claim 1 wherein said encoding and decoding of the deformable motion of a mesh model includes:

compressing the motion vectors for each node point using a breadth-first traversal of the mesh triangles;

deriving a unique ordering of the node points; and

predicting, using at least second order prediction, subsequent motion vectors for each node point.

9. The method of claim 8 wherein said predicting includes encoding and decoding prediction errors using variable length codes.

10. A method of encoding and decoding a dynamic mesh having a temporal sequence of mesh models and a set of polygonal patches therein, comprising:

encoding and decoding a first mesh model in the temporal sequence of the dynamic mesh, by encoding and decoding the geometry of a set of mesh vertices in the first mesh model; and

encoding and decoding subsequent mesh models in the temporal sequence of the dynamic mesh, by encoding and decoding the deformable motion of each mesh model, represented by a mesh node motion vector for each vertex.

11. The method of claim 10 wherein said encoding and decoding of a mesh geometry includes compressing a mesh topology of a Delaunay type.

12. The method of claim 10 wherein said encoding and decoding of a mesh geometry includes compressing a mesh topology of a uniform type.

13. The method of claim 10 wherein the polygons are triangles and said encoding and decoding of the deformable motion of a mesh model includes:

compressing the motion vectors for each vertex using a linear traversal of the vertices that is independent of a triangular mesh topology; and

predicting, using at least first order prediction, subsequent motion vectors for each vertex.

14. The method of claim 13 wherein said predicting includes encoding and decoding prediction errors using variable length codes.

15. The method of claim 13 which includes traversing and ordering the mesh vertices for a Delaunay type wash.

16. The method of claim 13 which includes traversing and ordering the mesh vertices for a uniform type mesh.

17. The method of claim 10 wherein said encoding and decoding of the deformable motion of a mesh model includes:

defining triangles throughout the mesh;

compressing the motion vectors for each vertex using a breadth-first traversal of the triangles and the vertices of the triangles;

deriving a unique order of the node points; and

predicting, using at least second order prediction, subsequent motion vectors for each vertex.

18. The method of claim 17 wherein said predicting includes encoding and decoding prediction errors using variable length codes.

19. A system for encoding and decoding an animated image represented by a dynamic mesh, wherein the dynamic mesh has a temporal sequence of mesh models in a fixed topology, each having a set of node points and motion vectors for the node points;

comprising;

an encoder subsystem for encoding the mesh models of the dynamic mesh and an image texture including;

a texture encoder for encoding the texture of an image and for producing an image bitstream therefrom;

a mesh encoder for encoding a mesh sequence;

said mesh encoder including a geometry encoder for encoding the geometry of the mesh, and a mesh motion encoder for encoding the motion vectors of the mesh; and

for generating a mesh coded bitstream therefrom;

a decoder subsystem for decoding the mesh models of the dynamic mesh and an image texture, including;

a texture decoder for decoding the texture of an image from an image bitstream;

a mesh decoder for decoding said mesh encoded bitstream, including a geometry decoder for decoding the geometry of the mesh, and a mesh motion decoder for decoding the motion vectors of the mesh; and

an animation application for combining the decoded texture data and the decoded mesh, and for generating an animated image therefrom.