Wavelet-based data compression

• US 6,144,773 A
• Filed: 02/27/1996
• Issued: 11/07/2000
• Est. Priority Date: 02/27/1996
• Status: Expired due to Term

• Current Assignee: Vulcan Patents LLC
• Original Assignee: Interval Research Corporation
• Inventors: Kolarov, Krasimir D., Lynch, William C., Schroder, Peter, Sweldens, Wim
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E.
• Application Number:
  US08/607,388
• Time in Patent Office: 1,715 Days
• Field of Search: 382/240, 382/248, 364/724.04, 364/724.14, 364/725.01, 364/725.02
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]

Abstract

A technique for compression and expansion of a function defined upon an M-dimensional manifold embedded in N-dimensional space uses a second generation wavelet transform and a modified zerotree bit-encoding scheme. Typically, a function is defined upon a two-dimensional manifold embedded in three-dimensional space, such as a sphere. A geometric base is chosen as a coarse initial model of the manifold. Second generation wavelets for the function are calculated using a triangular subdivision scheme in order to subdivide the geometric base in order to produce a refined triangular mesh. The wavelet coefficients are defined at the vertices of the triangles in the triangular mesh. A tree structure is created in which each node of the tree structure represents an associated triangle of the triangular mesh. Each triangle in the mesh is recursively subdivided into four subtriangles and each associated node in the tree structure also has four children, which correspond to the four subtriangles. Each wavelet coefficient defined at a particular vertex in the triangular mesh is uniquely assigned to a single one of the triangles at a next higher level of subdivision, such that each triangle at the next higher level of subdivision has from zero to three assigned wavelet coefficients. Using a modified zerotree encoding scheme, values of the wavelet coefficients are processed bit plane by bit plane, outputting bits indicative of significant nodes and their descendants. Sign bits and data bits are also output. An expansion technique inputs bits according to the modified zerotree scheme into the tree structure in order to define wavelet coefficients. An inverse second generation wavelet transform is used to synthesize the original function from the wavelet coefficients.

Claims

1. A computer-implemented method for performing wavelet-based compression of data representing a manifold, said method comprising:

identifying a function representing data defined upon an M-dimensional manifold, the manifold being embedded in N-dimensional space where M and N are integers and N is greater than M;

identifying a geometric base used to model the manifold;

calculating wavelets coefficients for the function using a cell subdivision scheme for subdividing the geometric base thereby producing a refined mesh of cells, the wavelet coefficients being associated with said cells within the refined mesh;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

assigning each of said wavelet coefficients to a single node in said tree; and

compressing said wavelet coefficients represented in said tree to produce compressed data representing said function.

2. A method as recited in claim 1 wherein said cell subdivision scheme uses triangular subdivision to produce a refined triangular mesh of triangles and each wavelet coefficient is associated with a single triangle of said triangular mesh.

3. A method as recited in claim 2 wherein each wavelet coefficient is defined at a vertex in the triangular mesh and is uniquely assigned to a single one of the triangles at a next higher level of subdivision such that each triangle has in the range of zero to three assigned wavelet coefficients.

4. A method as recited in claim 2 wherein each node of said tree represents one of:

a triangle of said triangles, an edge of one of said triangles, and a vertex of one of said triangles.

5. A method as recited in claim 1 wherein said manifold represents a substantially spherical three-dimensional object and the geometric base is selected from the group consisting of an icosahedron, an octahedron and a tetrahedron.

6. A method as recited in claim 1 wherein said step of calculating wavelet coefficients uses a lifting scheme for construction of second generation wavelets.

7. A method as recited in claim 1 wherein said step of compressing said wavelet coefficients uses a modified embedded zerotree wavelet (EZW) algorithm.

27. A method as recited in claim 1 wherein said data is defined upon a surface of a three-dimensional object.

8. A computer-readable medium comprising computer-readable program code arranged for performing the following wavelet-based method of compressing data representing a manifold:

identifying a function representing data defined upon an M-dimensional manifold, the manifold being embedded in N-dimensional space where M and N are integers and N is greater than M;

identifying a geometric base used to model the manifold;

calculating wavelets coefficients for the function using a cell subdivision scheme for subdividing the geometric base thereby producing a refined mesh of cells, the wavelet coefficients being associated with said cells within the refined mesh;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

assigning each of said wavelet coefficients to a single node in said tree; and

compressing said wavelet coefficients represented in said tree to produce compressed data representing said function.

28. A method as recited in claim 8 wherein said data is defined upon a surface of a three-dimensional object.

9. A computer-implemented method for performing wavelet-based compression of data representing a surface, said method comprising:

identifying a function representing data defined upon a surface;

identifying a geometric base used to model the surface;

calculating wavelets coefficients for the function using a cell subdivision scheme for subdividing the geometric base thereby producing a mesh of cells, the wavelet coefficients being associated with said cells within the refined mesh;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

assigning each of said wavelet coefficients to a single node in said tree; and

compressing said wavelet coefficients represented in said tree to produce compressed data representing said function.

10. A method as recited in claim 9 wherein said cell subdivision scheme uses triangular subdivision to produce a triangular mesh of triangles and each wavelet coefficient is associated with a single triangle of said triangular mesh.

11. A method as recited in claim 10 wherein each wavelet coefficient is defined at a vertex in the triangular mesh and is uniquely assigned to a single one of the triangles at a next higher level of subdivision such that each triangle has in the range of zero to three assigned wavelet coefficients.

12. A method as recited in claim 10 wherein each node of said tree represents one of:

a triangle of said triangles, an edge of one of said triangles, and a vertex of one of said triangles.

13. A method as recited in claim 9 wherein said surface is a substantially spherical three-dimensional object and the geometric base is selected from the group consisting of an icosahedron, an octahedron and a tetrahedron.

14. A method as recited in claim 9 wherein said step of calculating wavelet coefficients uses a lifting scheme for construction of second generation wavelets.

15. A method as recited in claim 9 wherein said step of compressing said wavelet coefficients uses a modified embedded zerotree wavelet (EZW) algorithm.

16. A method as recited in claim 9 wherein said surface is an M-dimensional manifold embedded in N-dimensional space, where M and N are integers and N is greater than M.

29. A method as recited in claim 9 wherein said surface is a surface of a three-dimensional object.

17. A computer-readable medium comprising computer-readable program code arranged for performing the following wavelet-based method of compressing data representing a surface:

identifying a function representing data defined upon a surface;

identifying a geometric base used to model the surface;

calculating wavelets coefficients for the function using a cell subdivision scheme for subdividing the geometric base thereby producing a mesh of cells, the wavelet coefficients being associated with said cells within the refined mesh;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

assigning each of said wavelet coefficients to a single node in said tree; and

compressing said wavelet coefficients represented in said tree to produce compressed data representing said function.

30. A method as recited in claim 17 wherein said surface is a surface of a three-dimensional object.

18. A computer-implemented method for performing wavelet-based uncompression of compressed data defined upon a surface, said method comprising:

identifying a geometric base to model the surface that uses a mesh of cells;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

uncompressing said compressed data into wavelet coefficients;

assigning each of said wavelet coefficients to a single node in said tree; and

performing data synthesis on the wavelets coefficients to produce said data defined upon said surface, said data synthesis using a cell subdivision scheme to subdivide the geometric base to produce said mesh of cells.

19. A method as recited in claim 18 wherein said cell subdivision scheme uses triangular subdivision to produce a refined triangular mesh of triangles and each wavelet coefficient is associated with a single triangle of said triangular mesh.

20. A method as recited in claim 19 wherein each wavelet coefficient is defined at a vertex in the triangular mesh and is uniquely assigned to a single one of the triangles at a next higher level of subdivision such that each triangle has in the range of zero to three assigned wavelet coefficients.

21. A method as recited in claim 19 wherein each node of said tree represents one of:

a triangle of said triangles, an edge of one of said triangles, and a vertex of one of said triangles.

22. A method as recited in claim 18 wherein said surface is a substantially spherical three-dimensional object and the geometric base is selected from the group consisting of an icosahedron, an octahedron and a tetrahedron.

23. A method as recited in claim 18 wherein said step of uncompressing produces second generation wavelets, and said step of performing data synthesis uses a lifting scheme on said second generation wavelets.

24. A method as recited in claim 18 wherein said step of uncompressing uses a modified embedded zerotree wavelet (EZW) algorithm.

25. A method as recited in claim 18 wherein said surface is an M-dimensional manifold embedded in N-dimensional space, where M and N are integers and N is greater than M.

31. A method as recited in claim 18 wherein said surface is a surface of a three-dimensional object.

26. A computer-readable medium comprising computer-readable program code arranged for performing the following wavelet-based method of uncompressing compressed data defined upon a surface:

identifying a geometric base to model the surface that uses a mesh of cells;

creating a tree representation of said mesh in which each node of the tree represents a cell of said mesh;

uncompressing said compressed data into wavelet coefficients;

assigning each of said wavelet coefficients to a single node in said tree; and

performing data synthesis on the wavelets coefficients to produce said data defined upon said surface, said data synthesis using a cell subdivision scheme to subdivide the geometric base to produce said mesh of cells.

32. A method as recited in claim 26 wherein said surface is a surface of a three-dimensional object.

33. A method for performing wavelet-based compression of data defined upon a complex geometry, said method comprising:

identifying a geometric base used to model said complex geometry;

calculating wavelets coefficients for said data using a lifting scheme and triangular subdivision to produce a mesh of triangles, said wavelet coefficients being associated with triangles within said mesh;

creating a tree representation of said mesh in which each node of the tree represents a triangle of said mesh;

assigning each of said wavelet coefficients to a single node in said tree; and

encoding said wavelet coefficients represented in said tree using a modified embedded zerotree wavelet (EZW) algorithm to produce compressed data representing said complex geometry.

34. A method as recited in claim 33 wherein said complex geometry is a three-dimensional object.