R-D optimized compression of 3-D mesh sequences based on principal component analysis

ABSTRACT

We propose an effective compression algorithm for three-dimensional (3-D) mesh sequences, based on principal components analysis (PCA). PCA achieves a coding gain by representing a mesh sequence with a small number of singular vectors. We develop a rate model and a distortion model for the singular vectors and propose an adaptive bit allocation scheme to maximize the coding performance. Specifically, we determine the quantizer step size for each singular vector to minimize the distortion, subject to the constraint on the overall bit rate. Simulation results demonstrate that the proposed algorithm provides much better rate-distortion (RD) performance than the conventional PCA coders.

REFERENCES

• 1: Jerome Edward Lengyel, Compression of time-dependent geometry, Proceedings of the 1999 symposium on Interactive 3D graphics, p.89-95, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300533]
• 2: J.-H. Yang, C.-S. Kim, and S.-U. Lee, "Compression of 3D triangle mesh sequences based on vertex-wise motion vector prediction," IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 12, pp. 1178--1184, Dec. 2002.
• 3: Lawrence Ibarria , Jarek Rossignac, Dynapack: space-time compression of the 3D animations of triangle meshes with fixed connectivity, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 4: E. S. Jang, D. K. Kim, S. Y. Jung, M. J. Han, S. O. Woo, and S. J. Lee, "Interpolator data compression for MPEG4 animation," IEEE Trans. Circuits Syst. Video Technol., vol. 14, no. 7, pp. 989--1008, July 2004.
• 5: M. Alexa and W. Müller, "Representing animations by principal components," EUROGRAPHICS 2000, vol. 19, no. 3, pp. 291--301, June 2000.
• 6: Z. Karni and C. Gotsman, "Compression of soft-body animation sequences," Computers & Graphics, vol. 2004, no. 28, pp. 25--34, June 2004.
• 7: Mirko Sattler , Ralf Sarlette , Reinhard Klein, Simple and efficient compression of animation sequences, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073398]
• 8: D. Kalman, "A singularly valuable decomposition: The SVD of a matrix," The College Mathematics Journal, vol. 27, no. 1, Jan. 1996.
• 9: G. H. Sullivan and T. Wiegand, "Rate-distortion optimization for video compression," IEEE Signal Proc. Magazine, vol. 1, no. 98, pp. 74--90, Nov. 1998.
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Design, Theory