We propose a new approach to progressively compress time-dependent geometry. Our approach exploits correlations in motion vectors to achieve better compression. We use unsupervised learning techniques to detect good clusters of motion vectors. For each detected cluster, we build a hierarchy of motion vectors using pairwise agglomerative clustering, and succinctly encode the hierarchy using entropy encod- ing. We demonstrate our approach on a client-server system that we have built for downloading time-dependent geometry.
In recent years, there has been a significant growth in e-commerce and entertainment over the Internet. Triangulated 3D geometric models are starting to appear on the World Wide Web as virtual shopping malls and virtual games become more common. Currently, most of the geometric data are static, i.e., they do not vary with time. However, if one were to look at the 2D world, where images (static 2D data) were followed by video, one can expect time-dependent geometry to become a more common form of data on the Internet of the future. Time-dependent geometry arises in simulations of many naturally occurring phenomena, e.g., water waves, plant growth, molecular dynamics, cloth animation, etc. In this paper, we describe how to compress time-dependent geometry for the purpose of transmission over the World Wide Web.
There has been a great deal of research on compressing static geometry, but very little work has been done on compressing time-dependent 3D geometric data. The work by Lengyel compresses dynamic meshes by solving for few-parameter deformation models and encoding the residuals. The prototype system considered in their work uses affine transform as the deformation model. However, the problem of determining the class of deformation for a vertex is still open, thus limiting the applicability of their algorithm.
We describe the step we have taken towards exploiting motion correlations for good compression of motion vectors. We use ideas from unsupervised learning theory to find good clusters of motion vectors. By encoding vectors within each cluster in its own local coordinate system, we achieve de-correlation of motion vectors. The main contributions of our paper are the following:
- We show that good compression can be achieved by exploiting motion correlations.
- We show that good clusters can be found using the expectation maximization algorithm from unsupervised learning theory.
- We demonstrate a progressive compression scheme for motion vectors suitable for progressive downloads.
- We demonstrate a system that supports progressive download of dynamic, geometric data at varying precisions.
We present the results of running our algorithm on data obtained from a molecular dynamics simulation. The simulation consists of the opening of a channel in an Escherichia coli (E. Coli) bacterium molecule. The data consists of five frames (Frames 0 - 4), and each frame consists of the 3D coordinates of 10585 atoms. With each of the x-, y-, z- coordinates quantized to 16 bits, our algorithm compresses the 10585 motion vectors between frames 0 and 1 to 35.82 bits per atom. The algorithm by Gandoin et al. compresses the same data to 40.48 bits per atom. Our algorithm achieves superior compression rates because atoms exhibit correlations in their motion. We expect similar improvements to hold for motion vectors between other pairs of frames too, since atoms move in a correlated fashion between every successive pair of frames. Our results are superior for other quantization levels too, as seen in Table 1.
Since we use a vector quantization scheme for each frame independently, errors can accumulate. This is a known problem in vector quantization techniques. To address the problem of error accumulation, we encode frame i with respect to a decompressed frame i-1. In other words, the motion vectors between frame i-1 and frame i are the difference between the real data at frame i and the decompressed data at frame i-1. This is shown in Table 2.
Table1. Compression results on molecular dynamics simulation data in number of bits per particle.
(# of Particles)
Molecular Dynamics Simulation (10585)
Table2. Error Accumulation without and with incremental frame encoding.
Errors without Incremental Encoding
Errors with Incremental Encoding
We have described an algorithm to compress time-dependent geometry by treating motion as simple translation. We have proposed a scheme that takes advantage of correlations in motion by detecting interesting clusters using Expectation-Maximization. Currently, our algorithm requires the user to specify the number of clusters. In future work, we plan to automatically determine the best number of clusters. We also plan to extend our work to compress 3D geometric models.
- Unsupervised Learning Applied to Progressive Compression of Time-Dependent Geometry
T. Baby, Y. Kim, and A. Varshney, Computers and Graphics, Vol 29, No. 3, June 2005, pp 451 - 461
This work has been supported in part by the NSF grants: IIS 00-81847, CCF 04-29753, and CNS 04-03313. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.