Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Patent
1996-02-27
2000-11-07
Au, Amelia
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
382248, 36472505, G06K 936, G06F 1715
Patent
active
061447730
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.
REFERENCES:
patent: 4155097 (1979-05-01), Lux
patent: 4190861 (1980-02-01), Lux
patent: 5014134 (1991-05-01), Lawton et al.
patent: 5068911 (1991-11-01), Resnikoff et al.
patent: 5101446 (1992-03-01), Resnikoff et al.
patent: 5124930 (1992-06-01), Nicolas et al.
patent: 5148498 (1992-09-01), Resnikoff et al.
patent: 5262958 (1993-11-01), Chui et al.
patent: 5272478 (1993-12-01), Allen
patent: 5287529 (1994-02-01), Pentland
patent: 5315670 (1994-05-01), Shapiro
patent: 5321776 (1994-06-01), Shapiro
patent: 5359627 (1994-10-01), Resnikoff
patent: 5363099 (1994-11-01), Allen
patent: 5381145 (1995-01-01), Allen et al.
patent: 5384725 (1995-01-01), Coifman et al.
patent: 5412741 (1995-05-01), Shapiro
patent: 5414780 (1995-05-01), Carnahan
patent: 5929860 (1999-07-01), Hoppe
"Image coding using wavelet transform", by Antonini et al., IEEE trans. On Image Processing, vol. 1, No. 2, Apr. 1992.
Hoppe et al. (Hoppe), "Mesh optimization", Siggraph 1993.
IPEA, International Preliminary Examination Report, May 27, 1998, EPO.
IPEA, Written Opinion (PCT Rule 66) EPO, Munich, Germany. Feb. 25, 1998.
M.H. Gross, et al., Fast Multiresolution Surface Meshing, 1995, IEEE.
Geoffrey Dutton, Locational Properties of Quaternary Triangular Meshes, 1990, Proceedings of the 4th International Symposium on Spatial Data Handling.
Peter Schroder, et al., Spherical Wavelets: Efficiently Representing Functions on the Sphere, 1995, Computer Graphics Proceedings, Annual Conference Series.
Leila De Floriani, et al., Hierarchical Triangulation for Multiresolution Surface Description, Oct. 14, 1995, ACM Transactions on Graphics, vol. 14, No. 4.
Gyorgy Fekete, et al., Sphere quadtrees: a new data structure to support the visualization of spherically distributed data, 1995, SPIE, vol. 1259. Abstract only--pages missing.
David Abel, et al., Advances in Spatial Databases, Jun. 1993, Third International Symposium.
"The research group directed by Prof. Tony DeRose at the University of Washington is currently conducting research concerned with the efficient representation of polygonal models with complicated geometry." Sep. 1995.
Geometric Compression Through Topological Surgery, Jan. 18, 1996, Presented at Stanford University.
Amir Said, A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, May 1993, IEEE Int. Symp. on Circuits and Systems.
Said, et al., Image Compression Using the Spatial-Orientation Tree, 1993, IEEE.
Schroder, et al., Spherical Wavelets: Efficiently Representing Functions on the Sphere, University of South Carolina.
Stephane G. Mallat, Multiresolution Approximations and wavelet orthonormal bases of L.sup.2 (R), Sep. 1989, Transactions of the American Mathematical Society, vol. 315, No. 1.
Cohen, et al., Biorthogonal Bases of Compactly Supported Wavelets, 1992, Communications on Pure and Applied Mathematics, vol. XLV, 485-560.
Ingrid Daubechies, Orthonormal Bases of Compactly Supported Wavelets, 1988, Communications on Pure and Applied Mathematics, vol. XLI 909-996.
Wim Sweldens, The Lifting Scheme: A Custom-Design Construction of Biorthogonal Wavelets, Nov. 1994 (revised Nov. 1995).
Jerome M. Shapiro, Embedded Image Coding Using Zerotrees of Wavelet Coefficients, Dec. 1993, IEEE, vol. 41, No. 12.
Schroder, et al., Spherical Wavelets: Texture Processing, pp. 1-11.
Kolarov Krasimir D.
Lynch William C.
Schroder Peter
Sweldens Wim
Au Amelia
Interval Research Corporation
Miller Martin E.
LandOfFree
Wavelet-based data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Wavelet-based data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wavelet-based data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1649827