This paper presents a new and compact 3D representation for nonrigid objects using the motion vectors between two consecutive frames. Our method relies on an Octree to recursively partition the object into smaller parts. Each part is then assigned a small number of motion parameters that can accurately represent that portion of the object. Finally, an adaptive thresholding, a singular value decomposition for dealing with singularities, and a quantization and arithmetic coding further enhance our proposed method by increasing the compression while maintaining very good signal-noise ratio. Compared to other methods that use tri-linear interpolation, Principle Component Analysis (PCA), or non-rigid partitioning (e.g., FAMC) our algorithm combines the best attributes in most of them. For example, it can be carried out on a frame-to-frame basis, rather than over long sequences, but it is also much easier to compute. In fact, we demonstrate a computation complexity of for our method, while some of these methods can reach complexities of and worse. Finally, as the result section demonstrates, the proposed improvements do not sacrifice performance since our method has a better or at least very similar performance in terms of compression ratio and PSNR. 1. Introduction As the technology for graphics processing advances, so does the details in the 3D models used for animation. So, despite these advances, when storing, transmitting, or rendering such models, the need for fast and compact representations is the same as it was a few years ago. In that sense, two categories of systems can be found in the literature: the time-independent methods and the time-dependent methods. The first and most traditional category is the time-independent, and it was first introduced in [1]. In that case, a 3D object is represented using its geometric properties at that moment. That is, 3D points [2, 3], triangular meshes, surface normals, edge orientations [4–7], wavelet coefficients [8, 9], and other features of the object are analyzed within a single time instant, or frame. These methods have advantages in terms of the quality of the model, but they are of course not very compact. On the other hand, time-dependent methods exploit the temporal relationship of these same types of features in order to increase compression. In one of the first systems to be reported [10], but also in more recent ones [11–15], the basic idea is to encode the motion of the 3D object. That is, the difference between consecutive frames, rather than the properties of the object in the frames. In order to
References
[1]
M. Dearing, “Geometry compression,” in Proceedings of the 22nd Annual Conference on Computer Graphics (SIGGRAPH '95), pp. 13–20, Los Angeles, Calif, USA, August 1995.
[2]
Y. Huang, J. Peng, and M. Gopi, “Octree-based progressive geometry coding of point clouds,” in Proceedings of Eurographics Symposium on Point-Based Graphics, pp. 103–110, 2006.
[3]
R. Schnabel and R. Klein, “Octree-based point cloud compression,” in Proceedings of Eurographics Symposium on Pointbased Graphics, pp. 111–120, 2006.
[4]
C. Touma and C. Gotsman, “Triangle mesh compression,” in Proceedings of Graphics Interface Conference, pp. 26–34, Canadian Human-Computer Communications Society, Vancouver, Canada, June 1998.
[5]
J. Rossignac, “3D compression made simple: edgebreaker with zip and warp on a corner-table,” in Proceedings of IEEE Conference on Shape Modelling and Applications, pp. 278–283, 2001.
[6]
A. Szymczak, “Optimized edgebreaker encoding for large and regular triangles meshes,” in Proceedings of Data Compression Conference (DCC '02), p. 472, Snao Bird, Utah, USA, 2002.
[7]
T. Lewiner, H. Lopes, J. Rossignac, and A. W. Vieira, “Efficient Edgebreaker for surfaces of arbitrary topology,” in Proceedings of the 17th Brazilian Symposium of Computer Graphic and Image Processing and 2nd Ibero-American Symposium on Computer Graphics, pp. 218–225, Curitiba, Brazil, October 2004.
[8]
M. Weeks and M. Bayoumi, “3D discrete wavelet transform architectures,” in Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS '98), vol. 4, pp. 57–60, Monterey, Calif, USA, May-June 1998.
[9]
F. F. Rodler, “Wavelet-based 3D compreesion with fast random access for very large volume data,” in Proceedings of the 7th Pacific Conference on Computer Graphics and Applications, p. 108, 1999.
[10]
J. E. Lengyel, “Compression of time-dependent geometry,” in Proceedings of the Symposium on Interactive 3D Graphics, pp. 89–95, Atlanta, Ga, USA, April 1999.
[11]
J. Zhang and C. B. Owen, “Octree-based animated geometry compression,” in Proceedings of Data Compression Conference (DCC '04), pp. 508–517, Snowbird, Utah, USA, March 2004.
[12]
S. Gupta, K. Sengupta, and A. A. Kassim, “Compression of dynamic 3D geometry data using iterative closest point algorithm,” Computer Vision and Image Understanding, vol. 87, no. 1–3, pp. 116–130, 2002.
[13]
P.-F. Lee, C.-K. Kao, J.-L. Tseng, B.-S. Jong, and T.-W. Lin, “3D animation compression using affine transformation matrix and principal component analysis,” IEICE Transactions on Information and Systems, vol. E90-D, no. 7, pp. 1073–1084, 2007.
[14]
K. Mamou, T. Zaharia, and F. Prêteux, “Famc: the MPEG-4 standard for animated mesh compression,” in Proceedings of International Conference on Image Processing (ICIP '08), pp. 2676–2679, San Diego, Calif, USA, October 2008.
[15]
N. Stefanoski and J. Ostermann, “Spatially and temporally scalable compression of animated 3D meshes with MPEG-4/FAMC,” in Proceedings of the 15th International Conference on Image Processing (ICIP'08), pp. 2696–2699, San Diego, Calif, USA, October 2008.
[16]
J. Zhang and J. Xu, “Optimizing octree motion representation for 3D animation,” in Proceedings of the 44th Annual Southeast Conference, pp. 50–55, Melbourne, Fla, USA, March 2006.
[17]
J. Zhang, J. Xu, and H. Yu, “Octree-based 3D animation compression with motion vector sharing,” in Proceedings of the 4th International Conference on Information Technology-New Generations (ITNG '07), pp. 202–207, Las Vegas, Nev, USA, April 2007.
[18]
K. Mamou, T. Zaharia, F. Preteux, A. Kamoun, F. Payan, and M. Antonini, “Two optimizations of the MPEG-4 FAMC standard for enhanced compression of animated 3D meshes,” in Proceedings of the 15th IEEE International Conference on Image Processing (ICIP'08), pp. 1764–1767, San Diego, Calif, USA, October 2008.
[19]
M. Alexa and W. Müller, “Representing animations by principal components,” Computer Graphics Forum, vol. 19, no. 3, pp. 411–418, 2000.
[20]
R. Amjoun and W. Stra？er, “Efficient compression of 3D dynamic mesh sequences,” Journal of the WSCG, vol. 15, no. 1–3, pp. 99–107, 2007.
[21]
I. Guskov and A. Khodakovsky, “Wavelet compression of parametrically coherent mesh sequences,” in Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 136–146, Grenoble, France, 2004.
[22]
F. Payan and M. Antonini, “Wavelet-based compression of 3D mesh sequences,” in Proceedings of the 2nd IEEE International Conference on Machine Intelligence (ACIDCA-ICMI '05), Tozeur, Tunisia, November 2005.
[23]
K. Muller, A. Smolic, M. Kautzner, and T. Wiegand, “Rate-distrotion optimization in dynamic mesh compression,” in Proceedings of IEEE International Conference on Image Processing, pp. 533–536, Atlanta, Ga, USA, October 2006.
[24]
M. Sattler, R. Sarletter, and R. Klein, “Simple and efficient compression of animation sequences,” in Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 209–217, Los Angeles, Calif, USA, 2005.
[25]
Q. Gu, J. Peng, and Z. Deng, “Compression of human motion capture data using motion pattern indexing,” Computer Graphics Forum, vol. 28, no. 1, pp. 1–12, 2009.
[26]
J.-H. Yang, C.-S. Kim, and S.-U. Lee, “Compression of 3-D triangle mesh sequences based on vertex-wise motion vector prediction,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 12, pp. 1178–1184, 2002.
[27]
L. Ibarria and J. Rossignac, “Dynapack: space-time compression of the 3D animations of triangle meshes with fiexed connectivity,” in Proceedings of the ACM SIGGRAPH/Eurographics Sysmposium on Computer Animation (SCA '03), pp. 126–135, 2003.
[28]
M. Tournier, X. Wu, N. Courty, E. Arnaud, and L. Revéret, “Motion compression using principal geodesics analysis,” in Proceedings of ACM Siggraph/Eurographics Symposium on Computer Animation (SCA '08), July 2009.
C. L. Jackins and S. L. Tanimoto, “Oct-trees and their use in representing three-dimensional objects,” Computer Graphics and Image Processing, vol. 14, no. 3, pp. 249–270, 1980.
[31]
T. H. Cormen, R. L. Rivest, C. E. Leisersonc, and C. Stein, Introduction to Algorithms, McGraw-Hill, New York, NY, USA, 2003.
[32]
Y. Chen and G. Medioni, “Object modeling by registration of multiple range images,” in Proceedings of IEEE International Conference on Robotics and Automation, vol. 3, pp. 2724–2729, Sacramento, Calif, USA, April 1991.
[33]
S. Rusinkiewicz and M. Levoy, “Efficient variants of the ICP algorithm,” in Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling, pp. 145–152, Quebec City, Canada, 2001.
[34]
H. Chui, J. Rambo, J. Duncan, R. Schultz, and A. Rangarajan, “Registration of cortical anatomical structures via robust 3D point matching,” in Proceedings of the 16th International Conference Information Processing in Medical Imaging (IPMI '99), pp. 168–181, Visegrád, Hungary, June-July 2003.
[35]
A. Rangarajan, H. Chui, and E. Mjolsness, “A relationship between spline-based deformable models and weighted graphs in non-rigid matching,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, pp. I897–I904, Kauai, Hawaii, USA, December 2001.
[36]
H. Chui and A. Rangarajan, “A new point matching algorithm for non-rigid registration,” Computer Vision and Image Understanding, vol. 89, no. 2-3, pp. 114–141, 2003.
[37]
N. Okada and M. Hebert, “Fast 3D tracking of non-rigid objects,” in Proceedings of IEEE International Conference on Robotics and Automation, vol. 3, pp. 3497–3503, Taipei, Taiwan, September 2003.
