SIViP DOI 10.1007/s11760-015-0859-0
ORIGINAL PAPER
Segmentation-based compression scheme for 3D animated models Meha Hachani1 · Azza Ouled Zaid1 · William Puech2
Received: 16 April 2015 / Revised: 16 December 2015 / Accepted: 18 December 2015 © Springer-Verlag London 2016
Abstract This paper presents an efficient compression algorithm for animated three-dimensional (3D) meshes. First, a segmentation approach is applied to achieve the motion estimation. The main idea is to exploit the temporal coherence of the geometry component by using the heat diffusion properties. The motion of the resulting regions is accurately described by 3D affine transforms. These transforms are computed at the first frame to match the subsequent ones. Second, in order to achieve a good compression performance, an efficient rate control mechanism is proposed to quantize the temporal prediction errors. At this stage, a rate-distortion model is used for quantizing the residual information. Comparative coding tests, for irregular 3D mesh sequences, were conducted to evaluate the coding efficiency of the proposed compression scheme. Simulation results show very promising performances. Keywords 3D affine transforms · Segmentation · Bit allocation · Heat diffusion · Compression
1 Introduction The recent technological advances in the fields of telecommunication, computer graphics and multimedia allow access
B
Meha Hachani
[email protected]
1
Communication Systems Laboratory, National Engineering School of Tunis, University of Tunis El Manar, B.P. 37, le Belvédère, 1002 Tunis, Tunisia
2
LIRMM UMR CNRS 5506, Montpellier University, 34095 Montpellier Cedex 5, France
to an ever finer 3D dynamic modeling of the world. The critical challenges with 3D animated models lie in their rendering, storage and speed transmission over channels with limited bandwidth. In this context, the need for efficient compression techniques is crucial. The first animated compression algorithm, proposed by Lengyel [1], is based on the affine transformations. A mesh is partitioned into different regions, and a rigid-body motion is computed for each region. Doing so, the deformation in a region is only represented by a set of affine transformations, instead of the displacements of all the vertices in the same region. Affine transformations have also been used by Mamou et al. [2]. The authors proposed a 3D mesh compression scheme, based on a skinning animation technique. The segmentation process is based on 3D affine transforms in order to obtain the frame-wise motion of each region by weighting previous affine transforms. Motion compensation is then performed followed by discrete cosine transform (DCT) of residual errors. A relevant compression method, proposed by Alexa and Müller [3], performs the PCA of geometry covariance matrix to reduce spatial correlation. Karni and Gostman [4] have extended this technique by applying a second-order linear predictive coding (LPC) on PCA components, to exploit the temporal coherence. This algorithm has been shown to be efficient only for sequences with few global motions. In addition, it is penalized by its high time and memory complexity. More recently, Lee et al. [5] proposed to improve Alexa and Müller’s compression algorithm by optimizing the number of key frames. The drawback of these methods is that the number of key frames may be quite high. Consequently, their effectiveness is diminished when applied to dense meshes with high number of vertices. In Müller et al. [6], the authors introduced a dynamic 3D mesh coder based on rate-distortion optimization. Both of
123
SIViP
the spatial partition and the prediction mode are determined using the Lagrangian cost function. A rate-distortion optimization model has also been used by Payan and Antonini [7]. To exploit temporal coherence, the authors proposed to use a temporal wavelet filtering. During the encoding step, the quantization of the wavelet coefficients is optimized by a temporal model based on bit allocation mechanism. Váša and Skala [8] proposed a 3D dynamic compression scheme Coddyac based on principal component analysis PCA which allow encoding the vertex trajectories rather than the whole frames. In order to predict the PCA coefficient values, the authors have chosen the parallelogram predictor based on the EdgeBreaker mesh traversal algorithm. The memory requirements of this method do not depend on the complexity of the meshes. However, the proposed algorithm cannot be used in the case of a long sequence of meshes with very simple geometry. The authors presented an extension of the Coddyac scheme [8] based on PCA in Váša and Skala [8]. The authors added a mathematically based non-uniform quantization technique, which is practically proven to be efficient. Bici nad Akari et al. [9] proposed three predictive coding approaches based on weighted spatial prediction. The authors introduced a weighted spatial prediction scheme in the first contribution. Then, in the second one, they integrated a refinement step. Finally, they introduced an angle-based predictor. The proposed structures achieve a significant improvement in the prediction error accuracy and the compression rate. Particularly, Bici et al.’s coding method is suitable for low-delay streaming scenarios. In this work, we propose a compression system for dynamic 3D meshes. Our contributions are twofold. First, we introduce a novel segmentation scheme, based upon ideas from Morse theory, to partition the first mesh of the sequence into submeshes having independent deformations. The best affine transformations that represent the displacements of the submeshes over the subsequent frames are then computed and encoded. Second, we propose to increase the compression performance by using a bit allocation mechanism that optimizes the selection of quantizer step sizes to be applied on the affine transform coefficients. We experimentally show that compared to the reference methods, the proposed coding scheme offers good compression performance. Furthermore, the use of rate control mechanism allows supporting specific needs of applications, networks and terminals. The rest of this paper is organized as follows. In Sect. 2, we describe in detail the various blocks constituting our compression scheme. In Sect. 3, we investigate the performance of our coding system. Finally, in Sect. 4, we conclude with our final remarks.
123
Fig. 1 Block diagram of the proposed coding scheme
2 Proposed approach This section describes our coding system, which is illustrated in the block diagram (see Fig. 1). The central contribution of our work is twofold: An implicit segmentation method is integrated in the coding chain in order to obtain a high precision of the motion estimation. Additionally, a rate control paradigm is used to increase the compression efficiency while keeping the computational complexity relatively low. 2.1 Compression scheme Our approach consists in representing the geometry of the mesh sequence by a piecewise affine geometry predictor minimizing the prediction errors. This is accomplished by exploiting the partition obtained by a segmentation algorithm. The obtained key vector π = {1, . . . , V } associates each of the mesh vertices with the index k of the cluster to which it belongs. This key vector is coded using the lossless arithmetic coder. The connectivity information is coded only once using a static 3D mesh encoder. We privilege using the progressive lossless mesh encoder of Valette et al. [10], which is based on incremental parametric refinement (IPR). In our setting, the vertex coordinates are quantized to 12 bits per coordinate. Experiments have shown that the IPR method provides very competitive results compared to previous work in terms of rate/distortion trade-off, Valette et al. [10]. During the prediction procedure, the first mesh of the sequence is taken as a reference frame. The motion estimation consists in describing the affine motion of clusters k ∈ {1, . . . , K } at frames i ∈ {1, . . . , F} by an affine transforms ATik . The latter is computed as follows with respect to the reference frame: ATik
= arg min A
v∈π
Aχ1v − χiv 2
,
(1)
SIViP
where A is 4 × 4 matrix representing an affine transform and χiv is a 4D vector that designates the homogeneous coordinates of the vertex v at frame i. The piecewise affine predictor of the frame i from the reference frame (frame 0) is expressed as follows: χˆ iv =
K
Wkv ATik χ0v ,
(2)
k=1
where Wkv , defined in (3), is the optimal weight vector that controls the motion influence of all the clusters k ∈ {1, . . . , K } over the vertex v. Vertex motions in each cluster are obtained by weighting the corresponding affine transforms. The homogeneous estimated coordinates of the vertex v at frame i are provided from the set ATik and Wkv : Wkv
= arg min A
K F−1 i=0
ATik χ0v
k=1
− χiv .
(3)
The two matrices ATik and Wkv are quantized and encoded by using the arithmetic coder. It is worth noting that these two matrices represent the motion information which highly influences the motion compensation accuracy, and consequently the reconstruction quality. For this reason, we proposed to use a rate control mechanism to efficiently calculate the quantizer step sizes during the quantization stage. The proposed bit allocation procedure is reviewed in Sect. 2.3 in more detail. The residual error is calculated as a simple difference between the original 4D vector, representing the homogeneous coordinates of the vertex v at frame i and the estimated one. We note that the prediction error vector, relative to each vertex v, is represented by floating point components with low magnitudes (that tend to zero). We proposed using the normalized scientific notation of the floating point components, to encode separately the signs, exponents and mantissas of the original vertex and the estimated one. This process allows realizing lossless compression with high precision. 2.2 Segmentation approach The main contribution consists in partitioning dynamic meshes based upon ideas from Morse theory Shinagawa et al. [11]. The proposed scalar function μ mainly depends on the set of feature points located on the extremity of the reference mesh. The set of feature points containing the significant information of the mesh are extracted based on the diffusion distance. To extract the set of feature points, we extended the method proposed by Tierny et al. [12]. Based on Tierny et al.’s approach, the extraction process begins with searching for the
most geodesically distant points v1 and v2 . These points are used to find two local property groups based on two geodesic functions associated with each of the vertices v1 and v2 . This method extracts successfully a set of well-localized feature points. Unfortunately, these feature points are very sensitive against topological changes. To overcome this problem and ensure stability under eventual perturbations over time, we proposed to use the diffusion distance dt2 instead of the geodesic one. Previous studies [13–15] have shown that global properties of the shape are detected through the behavior of heat diffusion over longer time, whereas local properties are detected through the behavior of heat diffusion over short time. For a given surface S, dt2 measures the connectivity distance between two points x, y ∈ S at a given time t according to: dt2 (x, y) = kt (x, x) + kt (y, y) − 2kt (x, y) = i∞ e(λi t) (φi (x) − φi (y))2 .
(4)
It is worth mentioning that the heat kernel kt (x, x) does not admit an explicit function; it can be computed based on the Laplace–Beltrami operator [13,15] , with λi and φi designating the ith eigenvalues and eigenfunctions of the Laplace–Beltrami, respectively. We suggest to use the solution proposed in Belkin et al. [13] to approximate the Laplace–Beltrami operator and calculate the set of its eigenvalues and eigenfunctions. Note that for small t values, the variation of the heat kernel function is large but decays as t increases. Therefore, to ensure an accurate detection of feature points, we scale the temporal domain logarithmically. This gives a more faithful approximation of local shape properties at the choosing time range [t1 , t2 ]. Let vi be one of the two farthest points (vi ∈ {v1 , v2 }). The set of feature points f vi corresponding to vi is given by: f vi = dt2 (v, vi ) =
t2
kt (v, v)+kt (vi , vi )−2kt (v, vi )d log t.
t1
The elements belonging to both f v1 and f v2 groups constitute the set of feature points F. Thus, F = f v1 ∩ f v2 will be used as origin to compute the scalar function. According to the Morse theory [11], a continuous scalar function defined on a closed surface characterizes the topology of the surface on its critical points. In our work, we propose to define an appropriate continuous function μ computed as the sum of the eccentricity from vertex v to each one of the feature points. Assuming that the surface S is approximated through a discrete triangular mesh M, for each vertex v ∈ M, μ(v) is established by: μ(v) =
1 dt2 (v, p)area( p), area(M)
(5)
p∈F
123
SIViP
where area(M) is the surface area of M, F represents the set of feature points, which are extracted in the first step, and area( p) is the area that p occupies. Finally, for a given frame, we obtain a vector that contains all the values of μ function. Depending on the μ values, the vector is split into intervals according to the number of connected components associated with each interval. Contiguous intervals with the same number of connected components are merged into a single interval. The process is repeated iteratively in order to reduce the number of clusters. At each step, the system performs a fusion operation on the interval groups that have the same number of connected components. The iterative loop stops when all the resulting intervals admit a different number of connected components. The computation of μ values in the discrete domain may prevent the detection of region boundaries. In order to adjust the segmentation boundaries and guarantee an accurate detection of region boundaries with respect to deep surface concavities, a refinement step has been integrated in the proposed segmentation scheme. Note that each region boundary is considered as a level set associated with a value of μ. During the refinement step, to identify a perceptually salient decomposition, we only consider the concavity problem. The optimal value of μopt should determine a boundary that matches a deep concavity profile on the object surface. In other words, μopt should be close to the closest critical point, μc . The determination of μopt value may thus be regarded as an optimization problem, which consists in minimizing the concavity function E concave (μ) of each region boundary associated with a value of μ: E concave (μ) = min(K min (c((μ),R) (t)) ⊗ G σ (t)), μ
(6)
order to attain the target bit-rate Rt . For a given subband Si and a quantizer step size q, the contribution to total distortion Di (q) from subband Si is defined by the mean-square error, given by: 1 Mean (Si − ((Si /q) × q))2 , 3
Di (q) =
(7)
where the mean is taken over all the coefficients in Si and “/ ” denotes division followed by rounding to the nearest integer. Similarly, define the bit-rate contribution Ri (q) as: 1 Entropy{(Si /q)}, 3
Ri (q) =
(8)
where the entropy is calculated over all the components in Si using statistical models. It is worth mentioning that the total distortion is calculated by considering only the distortion due to the quantization of the three coordinate subbands. Consider that the total dis3 Di , tortion is an additive metric, calculated as D = i=1 and that the total bit-rate of the code stream is given by 3 Ri . Given an input 3 subbands with a target bitR = i=1 rate Rbudget , one wants to select the set of quantization step sizes Q = {qi : i = 1, . . . , 3} to minimize the total distortion D: 3
D(Q) =
Di (qi ),
(9)
i=1
subject to the bit-rate constraint: R(Q) =
3
Ri (qi ) ≤ Rbudget − Rs − R f f ,
(10)
i=1
being K min (.) a function returning the sequence of K min curvature values, computed according to Taubin [16], along the boundary profile, and c((μ),R) (t) the curve-parameterized with respect to the normalized arc-length t. In fact, c((μ),R) (t) represents the subset of μ values corresponding to the boundary of region R. Convolution ⊗ with a Gaussian smoothing kernel G σ (t) leads to smoothing values of the K min . Consequently, the minimum identification will be more stable.
with Rs and R f f being the bit-rates of the side information and the reference frame, respectively. The rate-distortion problem can be formulated as follows:
2.3 Rate control
min J (λ) = D(Q) + λ((R(Q) + Rs + R f f ) − Rbudget ), (12)
The rate control mechanism is the core of our compression scheme. For a target bit-rate Rbudget , our rate control process allows to minimize the distortion of the finally obtained code stream. This process is performed on the prediction error data, which is split into 3 subbands of the 3 coordinates x, y and z. The rate-distortion trade-off is determined by calculating the adequate quantizer step size, for each subband, in
where λ is the Lagrangian multiplier and J (λ) is the Lagrangian cost. For a fixed λ, J (λ) is minimized when
123
(P) ⇐⇒
minimize D(Q) under constraint R(Q) = Rt .
(11)
Using Lagrange multiplier, Eqs. 9 and 10 are equivalent to the following unconstrained problem: Q
∂ J (λ) = 0, ∂ D(Q) ∂ J (λ) = 0. ∂ R(Q)
(13) (14)
SIViP Table 1 Properties of the tested dynamic meshes
Cow
Vertices
Frames
2904
204
The mean-square error denoted by E(Π ) is defined by:
Connected components 1
Dance
7061
201
1
Chicken
3030
400
41
Snake
9179
134
1
It is important to note that for a given Lagrange multiplier, the resulted λ and J (λ) might not meet the overall rate constraint. Therefore, we should find the optimal Lagrange multiplier λopt such that the total bit-rate would be equal to Rbudget . In our work, λopt is obtained by using the bisection method described in Krongold et al. [17].
3 Experimental results In order to evaluate the proposed segmentation approach, we consider some 3D dynamic meshes named: Dance, Chicken, Cow and Snake. These models are characterized by their various motions and complexities. Table 1 summarizes their properties, expressed in terms of numbers of vertices, frames and connected components.
E(Π ) =
T K 1 χiv − Aik χ1v 2 , V × T × D2 v∈π i=1 k=1
k
where V and T denote the number of vertices and the number of frames of the mesh sequences, respectively. D is the bounding box diagonal of the first frame. Aik is the 3D affine transform associated with the region (πk ) at frame i, and χiv is a vector that consists of the homogeneous coordinates of the vertex v at frame i. To assess the performances of our proposed compression scheme, we evaluate the introduced distortion as a function of the attained bit-rates. The quality degradation is assessed using two error metrics: – The KG error introduced by Karni and Gostman [4]. The latter, expressed in percent, corresponds to the relative discrete L2-norm in both time and space. – The root-mean-square error RMSE defined as the mean value of the frame to frame. The latter is computed over all the frames of the sequence. The bit-rates are expressed in terms of bits per vertex per frame (bpvf). 3.3 Performance results
3.1 Parameter setting in the segmentation algorithm 3.3.1 Segmentation accuracy Two parameters intervene in the proposed segmentation method. The first one is the parameter, which is used to detect the feature points. Experimentally, we found that = 0.074 performs better compared to the other tested values. The second parameter, to be fixed, is the time range [t1 , t2 ], used in the computation of the scalar function μ. First, we compute the pair of (λi , φi ) of the Laplace–Beltrami operator, using the solution proposed in Belkin et al. [13]. Then, we select a timescale t = 2λ1 1 , that makes the time selection invariant to the scale of the processed mesh M. Finally, to ensure an accurate detection of feature points, we scale the temporal domain logarithmically at the choosing time range Av Av [t1 = 2λ1 1 A Mi , t2 = 2λ1 2 A Mi ]. Avi /i = 1, 2 is the area associated with the farthest vertices v1 and v2 , and A M is the global area of M.
Figure 2 depicts some segmentation results for Dance and Snake sequences. From this figure, we can see that the segmentation process allows to partition the mesh into rigid clusters consisting of topologically connected vertices which are characterized by similar motion properties. The results reported in Table 2 present the values of the squared error E(.) before and after the refinement step. The
3.2 Evaluation criteria To evaluate the performance of the proposed segmentation method, we choose the mean-square error, introduced by the motion compensation procedure. The objective is to obtain a partition Π = (πk )k∈1,...,K of the whole mesh into K regions.
Fig. 2 Segmentation results on four selected frames, extracted from Dance and Snake sequences
123
SIViP Table 2 Evaluation of the mean-square error of the motion compensation E(Π ) E(Π0 )
Nb iterations
E(Π )
Dance
0.0023
19
0.0012
Cow
0.0028
16
0.0016
Snake
0.0024
25
0.0014
number of iterations has also been provided in order to evaluate the convergence rate. From these results, we can notice that on average, the refinement step converges after 20 iterations. The motion estimation error is 0.0014 against 0.0025 without using the refinement step. Thus, we conclude that the refinement post-processing stage allows increasing, significantly, the motion estimation accuracy. 3.3.2 Compression performance In order to assess the performance of our compression scheme, we conduct some comparisons with previous methods from the state of the art. For a fair comparison, we divided our tests on two sets according the used distortion metric. In the first set of comparisons, we retain the KG error as a quality metric. To perform the comparisons, WSP [9] and FAMC [18,19] algorithms are used as references: – The weighted spatial prediction (WSP) [9] algorithm, described earlier in Sect. 2, integrates three prediction structures, – Frame-based Animated Mesh Compression (MPEG-4 FAMC) [18,19], based on skinning approach [2] and Context-Adaptive Binary Arithmetic coding. In the second set of comparisons, the RMSE is used as distortion metric, whereas RT [20], D3DMC [21], GV [22] and skinning algorithms are taken as references: – The RT clustering-based approach [20] consists in splitting the mesh into subparts whose motion is expressed only in terms of rigid transforms (RT). The object’s motion is described by a set of rigid motion parameters associated with each cluster. – Dynamic 3D Mesh Coder D3DMC [21] is a clusteringbased method, where the motion field is described by a set of motion vectors represented by an octree structure. – The geometry video (GV) [22] algorithm applies a global affine motion compensation procedure. It uses a stretch minimizing parametrization and a conventional video encoding approach to encoding a geometry image sequences. The latter is obtained by applying a uniform sampling on the parametric domain.
123
– The skinning [2] algorithm, described earlier in Sect. 2, is a piecewise affine predictor coupled with a DCT representation of the prediction errors. Figure 3 illustrates the rate/distortion curves obtained by using WSP [9], FAMC [18,19] and our method for Cow, Chicken and Dance sequences. From Fig. 3, we can see that on average, our coding scheme systematically yields superior compression performance when compared to WSP and FAMC reference coders. Furthermore, the rate/distortion curves show that the FAMC offers the worst results, except for Chicken sequence, which seems to be better compressed by FAMC. Figure 4a illustrates the rate/distortion results obtained by D3DMC [21], skinning [2] and our method for Chicken sequence. From this figure, we can notice that D3DMC codec leads to the best performances. For all the tested bit-rates, our codec slightly outperforms the skinning algorithm. The gap between the bit-rate-distortion curves representing our method and the skinning algorithm may be explained by the fact that our segmentation approach exploits the temporal coherence of the geometry component based on heat diffusion properties. Additionally, the accuracy of the vertices distribution on the border between clusters has been enhanced by exploiting the curvature information. Figure 4b depicts the plots of RMSE variation as a function of bit-rates for Snake sequence. The RMSE curves in Fig. 4b clearly show that the proposed codec outperforms the state of the art for low bit-rates. Specifically, at 2.7 bpvf, our codec achieves around 70 % lower distortion than RT method. The compression results of our codec, GV and skinning for Dance sequence are illustrated in Fig. 4c. When examining the figure in its whole, it is very clear that the proposed coding scheme surpasses the state of the art at low bit-rates (<3 bpvf). 3.3.3 Complexity evaluation In order to assess the time complexity of the proposed coding scheme, we have split our coding algorithm into 3 parts: segmentation part SP, motion estimation part MEP and prediction error computation part PEP. In Table 3, the processing time of each part is illustrated separately. Depending on the number of vertices in the 3D mesh and the number of frames in the sequence, the full processing time varies from 726 to 9823 ms. We have notice also that the segmentation part takes longer than the other. This can be explained by the fact that we use the heat kernel principal to compute the scalar function, what amounts to computing the eigenvalues and eigenvectors of the Laplacian matrix. 3.3.4 Discussions To reduce the motion estimation error, our coder uses a faithful segmentation technique based on heat diffusion prop-
SIViP
Fig. 3 Rate/distortion performances for Cow, Chicken and Dance sequences
erties. Also the accuracy of the vertices distribution, on the border between clusters, has been enhanced by exploiting the curvature information. We notice that the refinement post-processing stage using by our segmentation algorithm
Fig. 4 Rate/distortion performances for Chicken (a), Snake (b) and Dance (c) sequences
converges on average 20 iterations. This refinement process allows reducing the motion estimation error. All these reasons justify the good results, for our coder, obtained in terms of distortion when comparing our method to the reference one.
123
SIViP Table 3 Average execution times for Cow, Dance Chicken and Snake models SP (ms) Cow
551
MEP (ms)
PEP (ms)
Bitrates (bpvf)
146
29
2.13
Dance
9568
189
66
1.05
Chicken
3511
167
34
1.2
Snake
6256
178
51
1.34
Additionally, Computing a piecewise affine predictor allows minimizing the temporal prediction errors. Their quantification is subsequently optimized using the bit allocation strategy, which allows obtaining the best results in terms of bitrates and introduced distortion. The main disadvantage of our algorithm is related to the high computational complexity of the segmentation procedure which is quadratic with the number of vertices. Calculating the eigenvalues and eigenvectors of the Laplacian matrix makes our compression algorithm sensitive in the case of irregular meshes. However, in the case of semi-regular and regular meshes, our technique leads to a satisfactory performance compared to the state of the art.
4 Conclusion In this paper, we presented a hybrid coding system adapted to dynamic 3D meshes. In order to perform accurately the motion estimation, we integrated a segmentation process. The obtained partition is used in order to compute a piecewise affine predictor which minimizes the prediction errors. The rate/distorsion performance of our encoder is improved by optimizing the quantization of the temporal prediction errors using a rate control mechanism. Preliminary experimental results have shown that our approach leads to a satisfactory performance. Compared to the state of the art, our compression results are very promising. In our future work, we plan to improve the performance of the proposed scheme in terms of reconstruction quality. The main idea consists in automatically selecting the number of clusters that provides a lower-quality degradation distortion.
References 1. Lengyel, J.: Compression of time-dependent geometry. In: ACM Symposium on Interactive 3D Graphics, pp. 89–96 (1999) 2. Mamou, K., Zaharia, T., Prteux, F.: Multi-chart geometry video: a compact representation for 3D animations. In: IEEE 3DPVT, pp. 711–718 (2006)
123
3. Alexa, M., Müller, W.: Representing animations by principal components. Comput. Graph. Forum 19(3), 411–418 (2000) 4. Karni, Z., Gostman, C.: Compression of soft-body animation sequences. Comput. Graph. 28, 25–34 (2004) 5. Lee, P.F., Kao, C.K., Tseng, J.L., Jong, B.S., Lin, T.W.: 3D animation compression using affine transformation matrix and principal component analysis. IEICE Trans. Inf. Syst. E90-D 7, 1073–1084 (2007) 6. Müller, K., Smolic, A., Kautzner, M., Eisert, P.: Rate-distortionoptimized predictive compression of dynamic 3d mesh. Signal Process. Image Commun. 9, 812–828 (2006) 7. Payan, F., Antonini, M.: Temporal wavelet-based compression for 3D animated models. Comput. Graph. 31, 77–88 (2007) 8. Váša, L., Skala, V.: Coddyac: connectivity driven dynamic mesh compression. In: 3DTV Conference, pp. 145–154 (2007) 9. Bici, M.O., Akari, G.B.: Improved prediction methods for scalable predictive animated mesh compression. J. Vis. Commun. Image Represent. 22, 577–589 (2011) 10. Valette, S., Chaine, R., Prost, R.: Progressive lossless mesh compression via incremental parametric refinement. Eurograph. Symp. Geom. Process. 28(5), 1301–1310 (2009) 11. Shinagawa, Y., Kunii, T., Kergosien, Y.: Surface coding based on morse theory. IEEE Comput. Graph. Appl. 11(5), 66–78 (1991) 12. Tierny, J., Vandeborre, J.P., Daoudi, M.: Enhancing 3D mesh topological skeletons with discrete contour constrictions. Vis. Comput. 24, 155–172 (2008) 13. Belkin, M., Sun, J., Wang, Y.: Discrete Laplace operator on meshed surfaces. In: Proceedings of SOCG, pp. 278–287 (2008) 14. Hsu, E.P.: Stochastic Analysis on Manifolds. American Mathematical Society, Providence (2002) 15. Meyer, M., Desbrun, M., Schroder, P., Barr, A.H.: Discrete Differential Geometry Operators for Triangulated 2-manifolds. In: Visualization and Mathematics III, pp 35–57. Springer, Berlin, Heidelberg (2003) 16. Taubin, G.: Estimating the tensor of curvature of a surface from a polyhedral approximation. In: International Conference on Computer Vision, pp. 909–907 (1995) 17. Krongold, B.S., Ramchandran, K., Jones, D.L.: Computationally efficient optimal power allocation algorithm for multicarrier communication systems. In: Proceedings of International Conference on Communications, pp. 1018–1022 (1998) 18. Mamou, K., Zaharia, T., Preteux, F.: FAMC: The mpeg-4 standard for animated mesh compression. In: 15th IEEE International Conference on Image Processing, pp. 2676–2679 (2008) 19. Stefanoski, N., Ostermann, J.: Spatially and temporally scalable compression of animated 3D meshes with MPEG-4/FAMC. In: Proceedings of the IEEE International Conference on Image Processing, pp. 2696–2699 (2008) 20. Collins, G., Hilton, A.: A Rigid Transform basis for animation compression and level of detail. In: ACM Symposium on Interactive 3D Graphics, pp. 21–29 (2005) 21. Müeller, K., Smolic, A., Kautzner, M., Eisert, P., Wiegand, T.: Predictive compression of dynamic 3D meshes. IEEE Int. Conf. Image Process. 1, 621–624 (2005) 22. Briceno, H.M., Sander, P.V., McMillan, L., Gortler, S., Hoppei, H.: Geometry videos: a new representation for 3D animations. In: ACM Siggraph Symposium on Computer Animation, pp. 13–146 (2003) 23. Váša, L., Skala, V.: COBRA: compression of the basis for PCA represented animations. Comput. Graph. Forum 28(2), 1529–1540 (2010)