US6144773A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Wavelet-based data compression
Assignee: Vulcan Patents LLC
•
Filing: 1996-02-27
•
Granted: 2000-11-07
•
Expires: 2016-02-27
Abstract
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.
Inventors
- 👤 Krasimir D. Kolarov
- 👤 William C. Lynch
- 👤 Peter Schroder
- 👤 Wim Sweldens
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 11:09
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/60; H04N19/63; H04N19/64; H04N19/647; G; G06; G06T; G06T9/00; G06T9/40
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
137 words
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.
Claim 2
Dependent Claim
137 words
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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Dependent Claim
53 words
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.
Claim 5
Dependent Claim
36 words
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.
Claim 6
Dependent Claim
34 words
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.
Claim 7
Dependent Claim
24 words
A method as recited in claim 1 wherein said step of calculating wavelet coefficients uses a lifting scheme for construction of second generation wavelets.
Claim 8
Dependent Claim
23 words
A method as recited in claim 1 wherein said step of compressing said wavelet coefficients uses a modified embedded zerotree wavelet (EZW) algorithm.
Claim 9
Dependent Claim
142 words
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.
Claim 10
Dependent Claim
142 words
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.
Claim 11
Dependent Claim
116 words
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.
Claim 12
Dependent Claim
116 words
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.
Claim 13
Dependent Claim
36 words
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.
Claim 14
Dependent Claim
53 words
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.
Claim 15
Dependent Claim
36 words
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.
Claim 16
Dependent Claim
34 words
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.
Claim 17
Dependent Claim
24 words
A method as recited in claim 9 wherein said step of calculating wavelet coefficients uses a lifting scheme for construction of second generation wavelets.
Claim 18
Dependent Claim
23 words
A method as recited in claim 9 wherein said step of compressing said wavelet coefficients uses a modified embedded zerotree wavelet (EZW) algorithm.
Claim 19
Dependent Claim
30 words
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.
Claim 20
Dependent Claim
121 words
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.
Claim 21
Dependent Claim
121 words
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.
Claim 22
Dependent Claim
106 words
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.
Claim 23
Dependent Claim
106 words
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.
Claim 24
Dependent Claim
37 words
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.
Claim 25
Dependent Claim
53 words
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.
Claim 26
Dependent Claim
36 words
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.
Claim 27
Dependent Claim
34 words
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.
Claim 28
Dependent Claim
32 words
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.
Claim 29
Dependent Claim
20 words
A method as recited in claim 18 wherein said step of uncompressing uses a modified embedded zerotree wavelet (EZW) algorithm.
Claim 30
Dependent Claim
30 words
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.
Claim 31
Dependent Claim
111 words
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.
Claim 32
Dependent Claim
111 words
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.
Claim 33
Dependent Claim
19 words
A method as recited in claim 1 wherein said data is defined upon a surface of a three-dimensional object.
Claim 34
Dependent Claim
19 words
A method as recited in claim 8 wherein said data is defined upon a surface of a three-dimensional object.
Claim 35
Dependent Claim
17 words
A method as recited in claim 9 wherein said surface is a surface of a three-dimensional object.
Claim 36
Dependent Claim
17 words
A method as recited in claim 17 wherein said surface is a surface of a three-dimensional object.
Claim 37
Dependent Claim
17 words
A method as recited in claim 18 wherein said surface is a surface of a three-dimensional object.
Claim 38
Dependent Claim
17 words
A method as recited in claim 26 wherein said surface is a surface of a three-dimensional object.
Claim 39
Independent Claim
113 words
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.
Claim 40
Independent Claim
113 words
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.
Claim 41
Dependent Claim
15 words
A method as recited in claim 33 wherein said complex geometry is a three-dimensional object.
References Cited (Backward Citations)
US4190861A
Cited
US4155097A
Cited
US5124930A
Cited
US5014134A
Cited
US5068911A
Cited
US5384725A
Cited
US5101446A
Cited
US5148498A
Cited
US5287529A
Cited
US5359627A
Cited
US5262958A
Cited
US5315670A
Cited
US5321776A
Cited
US5272478A
Cited
US5363099A
Cited
US5412741A
Cited
US5414780A
Cited
US5381145A
Cited
US5929860A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-11-07 | 2004-05-08 | 2004-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-11-07 | 2008-05-08 | 2008-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-11-07 | 2012-05-08 | 2012-11-07 | $7700.00 | Window Closed / Lapsed |