Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1999-08-26
2002-08-20
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S154000
Reexamination Certificate
active
06438266
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to topology and geometry compression and coding schemes used in interactively creating, manipulating and transmitting 3-D geometry, especially through remote networked environments.
BACKGROUND OF THE INVENTION
Demand for 3-D imagery in entertainment, advertising, education, medicine, CAD, architecture and elsewhere, is high and increasing. As a result, there is a growing need for more efficient rendering of scanned images of 3-D objects; and more error-resistant transmission and reception of these through error-prone internet, broadcast, and wireless networks to a remote location.
Digital representations of stationary 3-D objects typically consist of large numbers of discrete polygons, encoded by various methods to reflect location, geometric, connectivity, texture, and other surface characteristics. One of the promising current modeling processes involves the use of surface models made up of triangles. Much research for this model has centered on geometry data compression, and incremental and progressive streaming modes of geometric model transmission. An ongoing challenge is to design efficient data structures that encompass both the compactness of a geometric compression scheme and the superior visual quality of a progressive representation.
In an error-prone communication environment, however, it is necessary to also have a more robust mechanism over an unreliable network because data packets may be corrupted or lost. Once an error occurs, quick recovery should be promptly processed for direct interaction with the remote 3-D data set. The decoder must be able to synchronize and continue decoding the received stream instead of requiring retransmission from scratch. To transmit large compressed 3-D data, it is therefore desirable that the encoded bit stream also supports incremental transmission. That is, the receiving party should be able to decode and display whatever information it has received from the server without retransmission.
The fundamental idea in progressive transmission is that most important information of an object is sent first, followed by a series of details. The most important information forms an object at the coarsest level of resolution. The details are used to successively update the coarsest and intermediate meshes. The advantages that progressive transmission offers are numerous: high performance, embedded bit stream which can be truncated at any point by the decoder to create the best corresponding reconstructed 3-D object and exact bit rate control.
Another efficiency currently being applied in the digital representation of 3-D objects is mirroring. Mirroring is the taking advantage of left-right mirror symmetries such as are exhibited in faces/heads and body segments, biological organisms and structures, vehicles, machine parts, and furniture. Mirroring can substantially reduce the amount of data needed to reproduce an image, by transmitting a left-image and then for the right image, only information as to slight asymmetries. The utility of mirroring, however, is in part dependent on availability of an efficient coding, transmission and decoding of the slight asymmetries.
Several teachings in the prior art directed generally to efficient coding, transmission and decoding of 3-D images are noteworthy. One process described in “Arbitrary Topology Shape Reconstruction from Planar Cross Sections”, Bajaj et. al.;
Graphical Models and Image Procession
, 58, 6 (1996), 524-543, is to represent polygonal mesh connectivity as generalized triangle strips, and to compactly express a planar graph via stack operators such that the total number of random accesses to all vertices of the mesh is greatly reduced. Linear predictions are used to quantize and code the vertex positions and attributes. The compression ratio is usually not high, however.
The Topological Surgery (TS) method described in “Optimized Geometry Compression for Real Time Rendering”, Chow, M. M., Proceedings of IEEE Visualization '97, 347-354, is a compression scheme over a set of manifold triangular meshes. TS organizes vertices of a mesh into a vertex spanning tree and triangles into simple polygons which are further grouped to a series of triangle strips. Vertex positions are predicted by linear combinations of the encoded positions of their ancestors in the vertex spanning tree. Geometry and connectivity encoding can be processed separately. The advantage of this scheme lies in its connectivity efficiency, about 2-3 bits per triangle. However, this scheme cannot handle non-manifold meshes directly; and currently it is difficult to design hardware supported decompression algorithms for it, because the random access nature of TS takes up too much bus bandwidth.
In “Geometric Compression”, Deering, M.,
Computer Graphics
(Proc. SIGGRAPH) (1995), 13-20, a further process is noted for decomposing a given mesh into several generalized triangular meshes, as well as a geometry and topology encoding scheme. While optimized for real-time rendering, the process is not compression-efficient.
Most existing compression methods only work correctly on manifold meshes or meshes of even more narrowed classes. To compress a non-manifold polygonal mesh, most methods need to convert it into a manifold mesh in a preprocessing step. In the article “Vector Quantization and Signal Compression”, Gersho et. al.; Norwell, M A:
Kluwer Academic Publishers
, 1992, such a conversion process works by cutting-and-stitching operations over singular vertices and edges. However, since cutting-and-stitching operations ignore vertex coordinates, there may exist two connected components in the resulted manifold mesh that have coincident boundaries. The crack problem arises when positions of coincident vertices are quantized using different predictions.
The article “Vector Quantization”, Grey, R. M. IEEE ASSP Magazine I, 2 (1984), 4-29, describes a mesh with recursive subdivision connectivity to approximate a mesh of arbitrary topology. Wavelets are introduced to do multiresolution analysis of meshes with such connectivity property. Hierarchical quaternary subdivision trees are used to organize the vertices which will be coded in a top-down mode. Prediction coding is used for vertex positions by means of surface fitting. This wavelet-based scheme does not, however, support lossless compression because most meshes do not have subdivision connectivity.
Another scheme suggested in
Handbook of Visual Communications
, Hang et. al. Academic Press, 1995 is the adaptive-refinement Progressive Mesh (PM). It stores a manifold mesh as a low resolution coarse mesh together with an ordered sequence of details that can be used to refine the coarse mesh. Edge collapse and vertex split are two basic operations. Each vertex split operation adds a new vertex and two new triangles and locally refines the coarse mesh. This method, however, also is not compression-efficient.
In the article “View-Dependent Refinement of Progressive Meshes”, Hoppe, H.,
Computer Graphics (Proc SIGGRAPHS) (
1997), 189-198, . . . , a lossy connectivity compression technique is described which outputs a progressively transmittable bit stream. The original simplicial mesh at different resolutions is expressed through successive edge collapse and merging operations, a scheme described in “A Method for the Construction of Minimum-redundancy Codes” Hufffnan, D. A.,
Proceedings of the IRE
40 (1952) 1098-1101. While not being an efficient coding method, its fundamental contribution is its support for the progressive transmission. The method is slightly improved by an idea provided in [“View-dependent Simplification of Arbitrary Polygonal Environments” Luebke et. al.,
Computer Graphics
(Proc SIGGRAPH '97) (1997), 199-208, by integrating the structured bit stream and the attribute stream under certain optimized criteria.
Progressive Forest Split (PFS) described in Progressive Compression of 3-D Models,
IEEE Proceedings of Multimedia Computing and Systems
(Ottowa Canada, 1997), is a compact representation for
Bajaj Chandrajit
Pascucci Valerio
Petijan Eric D.
Zhuang Guozhong
Graves Charles E.
Johnson Timothy M.
LandOfFree
Encoding images of 3-D objects with improved rendering time... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding images of 3-D objects with improved rendering time..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding images of 3-D objects with improved rendering time... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925528