3D Mesh Compression

3D meshes and mesh sequences are currently used in a number of domains, from entertainment to industry. This chapter begins by considering certain basic points of information theory, the sampling and quantization notions needed to reduce the quantity of data and notions of rate-distortion. It then discusses multiresolution analysis. This consists of decomposing a mesh into a series of resolution levels, for example by using wavelet transformations. The chapter then presents monoresolution coding methods based on highly effective connectivity coders, associating prediction techniques. Other progressive compression techniques, based on iterative simplification processes or guided by geometry, may be used to obtain satisfactory levels of compression with additional functionality. Sequence compression algorithms, fewer in number, are discussed considered in the next section, before addressing the definition of classic and perceptual metrics which may be used to evaluate the effectiveness of compression techniques.

Bibliography

[AHN 11] AHN J.-K., LEE D.-Y., AHN M., et al., “R-D optimized progressive compression of 3D meshes using prioritized gate selection and curvature prediction”, The Visual Computer, vol. 27, no. 6–8, pp. 769–779, April 2011.
10.1007/s00371-011-0565-z
Web of Science® Google Scholar
[ALE 00] ALEXA M., MÜLLER W., “Representing animations by principal components”, Computer Graphics Forum, vol. 19, pp. 411–418, 2000.
10.1111/1467-8659.00433
Web of Science® Google Scholar
[ALL 01a] ALLIEZ P., DESBRUN M., “Progressive encoding for lossless transmission of triangular meshes”, Proceedings of the 28th annual conference on Computer graphics and interactive techniques (SIGGRAPH '01) ACM, New York, USA, pp. 195–202, 2001.
10.1145/383259.383281
Google Scholar
[ALL 01b] ALLIEZ P., DESBRUN M., “Valence-driven connectivity encoding of 3D meshes”, Computer Graphics Forum, vol. 20, no. 3, pp. 480–489, 2001.
10.1111/1467-8659.00541
Web of Science® Google Scholar
[ARC 11] ARCILA R., Séquences de maillages: classification et méthodes de segmentation, PhD Thesis, Université Claude Bernard - Lyon I, November 2011.
Google Scholar
[BOU 07] BOULFANI-CUISINAUD Y., ANTONINI M., “Motion-based geometry compensation for DWT compression of 3D mesh sequences”, Image Processing, 2007 (ICIP 2007) IEEE International Conference on, IEEE, vol. 1, I-217–I-220, 16 September–19 October 2007.
Web of Science® Google Scholar
[CHE 07] CHENG I., YING L., BASU A., “Packet-loss modeling for perceptually optimized 3D transmission”, Advances in Multimedia, vol. 2007, pp. 1–10, 2007.
10.1155/2007/95218
Google Scholar
[CIG 98] CIGNONI P., ROCCHINI C., SCOPIGNO R., “Metro: measuring error on simplified surfaces”, Computer Graphics Forum, IEEE Computer Society Press, vol. 17, no. 2, pp. 167–174, 1998.
Web of Science® Google Scholar
[COH 99] COHEN-OR D., LEVIN D., REMEZ O., “Progressive compression of arbitrary triangular meshes”, Proceedings of the conference on Visualization '99: celebrating ten years (VIS '99), pp. 67–72, 1999.
Google Scholar
[COR 07] CORSINI M., GELASCA E.D., EBRAHIMI T., et al., “Watermarked 3-D mesh quality assessment”, IEEE Transactions on Multimedia, vol. 9, no. 2, pp. 247–256, 2007.
10.1109/TMM.2006.886261
Web of Science® Google Scholar
[COU 11] COURBET C., HUDELOT C., “Taylor prediction for mesh geometry compression”, Computer Graphics Forum, vol. 30, no. 1, pp. 139–151, 2011.
10.1111/j.1467-8659.2010.01838.x
Web of Science® Google Scholar
[DEE 95] DEERING M., “Geometry compression”, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques (SIGGRAPH'95), ACM Siggraph, pp. 13–20, 1995.
10.1145/218380.218391
Google Scholar
[DEV 00] DEVILLERS O., GANDOIN P.-M., “Geometric compression for interactive transmission”, Proceedings of the conference on Visualization '00, IEEE Computer Society Press, no. 8, pp. 319–326, 2000.
Web of Science® Google Scholar
[GAN 02] GANDOIN P.-M., DEVILLERS O., “Progressive lossless compression of arbitrary simplicial complexes”, Proceedings of the 29th annual conference on Computer graphics and interactive techniques (SIGGRAPH '02), ACM, no. 8, pp. 372–379, 2002.
Google Scholar
[GER 92] GERSHO A., GRAY R., Vector Quantization and Signal Compression, Kluwer Academic Publishers, 1992.
10.1007/978-1-4615-3626-0
Google Scholar
[GUM 98] GUMHOLD S., STRASSER W., “Real time compression of triangle mesh connectivity”, Proceedings of the 25th annual conference on Computer graphics and interactive techniques (SIGGRAPH '98), ACM, no. 8, pp. 133–140, 1998.
10.1145/280814.280836
Google Scholar
[GUP 02] GUPTA S., SENGUPTA K., KASSIM A., “Compression of dynamic 3D geometry data using iterative closest point algorithm”, Computer Vision and Image Understanding, vol. 87, no. 1, pp. 116–130, 2002.
10.1006/cviu.2002.0987
Web of Science® Google Scholar
[GUS 00] GUSKOV I., VIDIMCE K., SWELDENS W., et al., “Normal meshes”, Computer Graphics Proceedings, SIGGRAPH, pp. 95–102, 2000.
Web of Science® Google Scholar
[HAN 07] HAN S.-R., YAMASAKI T., AIZAWA K., “Time-varying mesh compression using an extended block matching algorithm.”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 11, pp. 1506–1518, 2007.
10.1109/TCSVT.2007.903810
Web of Science® Google Scholar
[HOP 96] HOPPE H., “Progressive meshes”, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (SIGGRAPH '96), ACM, pp. 99–108, 1996.
10.1145/237170.237216
Google Scholar
[IBA 03] IBARRIA L., ROSSIGNAC J., “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, Eurographics Association, pp. 126–135, 2003.
Google Scholar
[ISE 00] ISENBURG M., “Triangle fixer: edge-based connectivity compression”, in Proceedings of 16th European Workshop on Computational Geometry, pp. 18–23, 2000.
Google Scholar
[ISO 00] ISO/IEC 15444–1:2000, “Information technology – JPEG 2000 image coding system – Part 1: Core coding system”, 2000.
Google Scholar
[KAM 12] KAMMOUN A., PAYAN F., ANTONINI M., “Sparsity-based optimization of two lifting-based wavelet transforms for semi-regular mesh compression”, Elsevier Computers and Graphics, vol. 36, pp. 272–282, 2012.
10.1016/j.cag.2012.02.004
Web of Science® Google Scholar
[KAR 00] KARNI Z., GOTSMAN C., “Spectral compression of mesh geometry”, Proceedings of the 27th annual conference on Computer graphics and interactive techniques (SIGGRAPH '00), ACM Press/Addison-Wesley Publishing Co., no. 8, pp. 279–286, 2000.
10.1145/344779.344924
Google Scholar
[KAR 04] KARNI Z., GOTSMAN C., “Compression of soft-body animation sequences”, Computers & Graphics, vol. 28, no. 1, pp. 25–34, 2004.
10.1016/j.cag.2003.10.002
Web of Science® Google Scholar
[KHO 02] KHODAKOVSKY A., ALLIEZ P., DESBRUN M., et al., “Near-optimal connectivity encoding of 2-manifold polygon meshes”, Journal of Graphical Models, vol. 64, nos. 3–4, pp. 147–168, 2002.
10.1006/gmod.2002.0575
Web of Science® Google Scholar
[KIM 11] KIM J., NAM C., CHOE S., “Bayesian AD coder: mesh-aware valence coding for multiresolution meshes”, Computers & Graphics, vol. 35, pp. 1–6, 2011.
10.1016/j.cag.2011.03.023
Web of Science® Google Scholar
[KOV 99] KOVACEVIC J., SWELDENS W., “Wavelet families of increasing order in arbitrary dimensions”, IEEE Transactions on Image Processing, vol. 9, no. 3, 1999.
Google Scholar
[KRO 01] KRONROD B., GOTSMAN C., “Efficient coding of non-triangular mesh connectivity”, Journal of Graphical Models, vol. 63, pp. 263–275, 2001.
10.1006/gmod.2001.0555
Web of Science® Google Scholar
[KRO 02] KRONROD B., GOTSMAN C., “Optimized compression of triangle mesh geometry using prediction trees”, International Symposium on 3D Data Processing, Visualization and Transmission, IEEE Computer Society, pp. 602–608, 2002.
10.1109/TDPVT.2002.1024124
Google Scholar
[LAV 06] LAVOUÉ G., DRELIE GELASCA E., DUPONT F., et al., “Perceptually driven 3D distance metrics with application to watermarking”, SPIE, vol. 6312, SPIE, pp. 63120L–63120L–12, August 2006.
Google Scholar
[LAV 11] LAVOUÉ G., “A multiscale metric for 3D mesh visual quality assessment”, Computer Graphics Forum, vol. 30, no. 5, pp. 1427–1437, 2011.
10.1111/j.1467-8659.2011.02017.x
Web of Science® Google Scholar
[LEE 98] LEE A.W.F., SWELDENS W., SCHRÖDER P., et al.., “MAPS: multiresolution adaptive parameterization of surfaces”, Computer Graphics Proceedings (SIGGRAPH 98), ACM Siggraph, pp. 95–104, 1998.
Google Scholar
[LEE 12] LEE H., LAVOUÉ G., DUPONT F., “Rate-distortion optimization for progressive compression of 3D mesh with color attributes”, The Visual Computer, vol. 28, no. 2, pp. 137–153, 2012.
10.1007/s00371-011-0602-y
PubMed Web of Science® Google Scholar
[LEN 99] LENGYEL J.E., “Compression of time-dependent geometry”, Proceedings of the 1999 symposium on Interactive 3D Graphics, I3D '99, ACM, New York, pp. 89–95, 1999.
10.1145/300523.300533
Google Scholar
[LEW 06] LEWINER T., CRAIZER M., LOPES H., “GEncode: geometry-driven compression for general meshes”, Computer Graphics Forum, vol. 25, no. 4, pp. 1–10, 2006.
10.1111/j.1467-8659.2006.00990.x
Web of Science® Google Scholar
[LOU 94] LOUNSBERY J., Multiresolution analysis for surfaces of arbitrary topological type, PhD Thesis, University of Washington, Seattle, 1994.
Google Scholar
[LOU 97] LOUNSBERY M., DEROSE T., WARREN J., “Multiresolution analysis for surfaces of arbitrary topological type”, ACM Transactions on Graphics, vol. 16, no. 1, pp. 34–73, 1997.
10.1145/237748.237750
Web of Science® Google Scholar
[PAJ 00] PAJAROLA R., ROSSIGNAC J., “Compressed progressive meshes”, IEEE Transactions on Visualization and Computer Graphics, vol. 6, no. 1, pp. 79–93, 2000.
10.1109/2945.841122
Web of Science® Google Scholar
[PAN 05] PAN Y., CHENG I., BASU A., “Quality metric for approximating subjective evaluation of 3-D objects”, IEEE Transactions on Multimedia, vol. 7, no. 2, pp. 269–279, 2005.
10.1109/TMM.2005.843364
Web of Science® Google Scholar
[PEN 05] PENG J., KUO C.-C.J., “Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition”, ACM Transactions on Graphics (TOG), vol. 24, no. 3, pp. 609–616, 2005.
10.1145/1073204.1073237
Web of Science® Google Scholar
[PEN 10] PENG J., KUO Y., ECKSTEIN I., et al., “Feature oriented progressive lossless mesh coding”, Computer Graphics Forum, vol. 29, no. 7, pp. 2029–2038, 2010.
10.1111/j.1467-8659.2010.01789.x
Web of Science® Google Scholar
[POP 97] POPOVIĆ J., HOPPE H., “Progressive simplicial complexes”, Proceedings of the 24th annual conference on Computer graphics and interactive techniques (SIGGRAPH '97), ACM Press/Addison-Wesley Publishing Co., no. 8, pp. 217–224, 1997.
10.1145/258734.258852
Google Scholar
[ROS 99] ROSSIGNAC J., “Edgebreaker: connectivity compression for triangle meshes”, IEEE Transactions on Visualization and Computer Graphics, vol. 5, no. 1, pp. 47–61, 1999.
10.1109/2945.764870
Web of Science® Google Scholar
[SCH 95] SCHRÖDER P., SWELDENS W., “Spherical wavelets: efficiently representing functions on the sphere”, Proceedings of SIGGRAPH 95, ACM, pp. 161–172, 1995.
10.1145/218380.218439
Google Scholar
[SEU 07] SEUNG-RYONG HAN., YAMASAKI T., AIZAWA K., “Time-varying mesh compression using an extended block matching algorithm”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 11, pp. 1506–1518, 2007.
10.1109/TCSVT.2007.903810
Google Scholar
[SHA 48] SHANNON C., “A mathematical theory of communication”, Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
10.1002/j.1538-7305.1948.tb01338.x
Web of Science® Google Scholar
[SOR 03] SORKINE O., COHEN-OR D., TOLDEO S., “High-pass quantization for mesh encoding”, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing (SGP '03), Eurographics Association, no. 10, pp. 42–51, 2003.
Google Scholar
[SZY 01] SZYMCZAK A., KING D., ROSSIGNAC J., “An edgebreaker-based efficient compression scheme for regular meshes”, Computational Geometry, vol. 20, nos. 1–2, pp. 53–68, 2001.
10.1016/S0925-7721(01)00035-9
Web of Science® Google Scholar
[TAU 98a] TAUBIN G., ROSSIGNAC J., “Geometric compression through topological surgery”, ACM Transactions on Graphics, vol. 17, no. 2, pp. 84–115, 1998.
10.1145/274363.274365
Web of Science® Google Scholar
[TAU 98b] TAUBIN G., GUÉZIEC A., HORN W., et al., “Progressive forest split compression”, SIGGRAPH, ACM Press, New York, pp. 123–132, 1998.
Google Scholar
[TOR 12] TORKHANI F., WANG K., CHASSERY J.-M., “A curvature tensor distance for mesh visual quality assessment”, International Conference on Computer Vision and Graphics, 2012.
Google Scholar
[TOU 98] TOUMA C., GOTSMAN C., “Triangle mesh compression”, in DAVIS W.A., BOOTH K.S., FOURNIER A. (eds), Graphics Interface, Canadian Human-Computer Communications Society, pp. 26–34, 1998.
Web of Science® Google Scholar
[TUR 84] TURAN G., “Succinct representations of graphs”, Discrete Applied Mathematics, vol. 8, pp. 289–294, 1984.
10.1016/0166-218X(84)90126-4
Web of Science® Google Scholar
[VAL 99] VALETTE S., KIM Y., JUNG H., et al., “A multiresolution wavelet scheme for irregularly subdivided 3D triangular mesh”, IEEE International Conference on Image Processing, Kobe, Japon, vol. 1, pp. 171–174, October 1999.
Google Scholar
[VAL 09] VALETTE S., CHAINE R., PROST R., “Progressive lossless mesh compression via incremental parametric refinement”, Computer Graphics Forum, vol. 28, no. 5, pp. 1301–1310, 2009.
10.1111/j.1467-8659.2009.01507.x
Web of Science® Google Scholar
[VAS 11] VASA L., SKALA V., “A perception correlated comparison method for dynamic meshes”, IEEE Transactions on Visualization and Computer Graphics, vol. 17, no. 2, pp. 220–230, 2011.
10.1109/TVCG.2010.38
PubMed Web of Science® Google Scholar
[VAS 12] VASA L., RUS J., “Dihedral angle mesh error: a fast perception correlated distortion measure for fixed connectivity triangle meshes”, Computer Graphics Forum, vol. 31, no. 5, pp. 1715–1724, 2012.
10.1111/j.1467-8659.2012.03176.x
Web of Science® Google Scholar
[WAN 12] WANG K., TORKHANI F., MONTANVERT A., “A fast roughness-based approach to the assessment of 3D mesh visual quality”, Computers & Graphics, vol. 36, no. 7, pp. 808–818, 2012.
10.1016/j.cag.2012.06.004
Web of Science® Google Scholar
[ZHA 07] ZHANG J., OWEN C.B., “Octree-based animated geometry compression”, Computers and Graphics, vol. 31, no. 3, pp. 463–479, 2007.
10.1016/j.cag.2006.12.002
Web of Science® Google Scholar

3D Video: From Capture to Diffusion