Céline Roudet
email: celine.roudet@u-bourgogne.fr

A Region-Based Progressive Coding of Semi-Regular 3-D Meshes for View-Dependent Transmission

Keywords: Geometric wavelets, multiresolution analysis, lifting scheme, progressive mesh compression, progressive coding, 3-D mesh segmentation, view-dependent reconstruction

We first introduce in this paper a new waveletbased segmentation algorithm for three-dimensional (3-D) Semi-Regular (SR) meshes. This method is then considered as a pre-processing step in a view-dependent progressive coding of 3-D meshes. Our segmentation process aims at producing homogeneous regions which have similar frequency amplitudes on the mesh surface, in other words: patches with different degrees of roughness. As a preliminary step of the development of a locally-based Rate-Distortion (R-D) optimized coding scheme, we propose to study the behaviour of the wavelet decomposition in the created patches, during the coding and the view-dependent reconstruction processes. To our knowledge, no previous work has ever considered the influence of the nonrefined parts of a mesh on the more detailed ones, in a viewdependent context. The main contribution of this paper consists in considering three different possible wavelet decompositions, close to the patch borders, and to study their influence during the coding and the view-dependent reconstruction stages. Among these three decompositions, we define a new scheme and finally propose various experimentations to demonstrate that it behaves better than the other classical considerations, for view-dependent reconstruction purposes.

I. INTRODUCTION

Three-dimensional (3-D) objects and scenes find their way into more and more applications, thanks to the ever increasing bandwidth available in modern telecommunication networks, such as the High Speed Internet, or 3G mobile networks. These kinds of models are not only used in medical applications and entertainment (video games or animation films), but also for industrial purposes like car industry (Computer Aided Design framework), simulation or virtual environment contexts.

The triangular mesh is actually the most common representation for these objects and scenes, because it is a suitable model for many applications, like rendering for example. It includes geometry (vertex positions) and connectivity data which can be expensive in terms of computation, storage, transmission and rendering, even with today devices and networks.

Consequently in literature, many progressive mesh compression and transmission schemes have been proposed

(including [START_REF] Hoppe | Progressive Meshes[END_REF] - [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF]), to represent data with multiple Levels of Detail (LOD). With this representation, a coarse approximation can subsequently be further improved depending on the user's devices (network channel and visualization terminal) and expectactions. This scalable representation is commonly obtained with a wavelet transform ( [START_REF] Khodakovsky | Progressive geometry compression[END_REF] - [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF]), because it produces a good decorrelation of the data. The best compression rates on 3-D meshes are currently obtained with a wavelet decomposition, also called Multi-Resolution Analysis (MRA) on Semi-Regular (SR) structures. In SR meshes, the valence of most vertices is equal to six, which produces a very compact representation of the connectivity information.

Most of the state-of-the-art wavelet-based SR mesh compression algorithms ([4] - [START_REF] Payan | An efficient bit allocation for compressing normal meshes with an error-driven quantization[END_REF]) consider a global wavelet decomposition on the mesh surface. Since the 3-D application expectations in terms of realism are always growing, it requires increasingly complex and large polygonal meshes. Consequently view-dependent compression, transmission and rendering methods ( [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] - [START_REF] Hoppe | View-dependent refinement of progressive meshes[END_REF]) have recently emerged, to accelerate the huge amount of computations involved in this context. The principle consists in considering the user's viewing frustrum, to more refine the object regions or scene parts that face toward the viewer. Hoppe [START_REF] Hoppe | View-dependent refinement of progressive meshes[END_REF] was one of the formest to introduce the concept of view-dependent simplification and refinement, for fast and efficient rendering of 3-D irregular meshes (represented with the Progressive Mesh (PM) [START_REF] Hoppe | Progressive Meshes[END_REF] structure).

More recently, several view-dependent compression and transmission algorithms have been developped for SR meshes [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] - [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF]. Gioia et al. [START_REF] Gioia | Real-time reconstruction of wavelet-encoded meshes for view-dependent transmission and visualization[END_REF] proposed a waveletbased view-dependent transmission and visualization algorithm where the wavelet coefficients can be added or suppressed in real-time on a partially reconstructed mesh. Hence the reconstruction of large meshes can be optimized by allocating a major portion of the available bandwidth to visible parts.

Sim et al. developped in 2005 a rate-distortion (R-D) optimized view-dependent SR mesh streaming method [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF]. One of the key points is to add a partitioning of the SR mesh into many segments, in order to optimally allocate bits during the compression process. Another advantage is to give the possibility to progressively transmit the segments independently, according to the client's viewing position. This region-based R-D optimization scheme improves the conventional wavelet-based compression algorithms for SR meshes ( [START_REF] Khodakovsky | Progressive geometry compression[END_REF], [START_REF] Khodakovsky | Compression of normal meshes[END_REF]). The authors considered the same constrained allocation problem as in [START_REF] Lavu | Geometry compression of normal meshes using rate-distortion algorithms[END_REF] and [START_REF] Payan | An efficient bit allocation for compressing normal meshes with an error-driven quantization[END_REF], to formulate their R-D optimization. Moreover, the server can allocate an adaptive bitrate to each segment (based on its visibility priority), to facilitate the interactive streaming of 3-D data. More recently, another view-dependent geometry coding of static 3-D scenes (defined by sets of semi-regular meshes) was proposed by Payan et al. [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF]. The proposed coding scheme combines a segmentation for determining the visible regions, and an allocation process (detailed in [START_REF] Payan | An efficient bit allocation for compressing normal meshes with an error-driven quantization[END_REF]) for improving the visual quality of the encoded scene.

These two previously cited region-based view-dependent coding methods [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] and [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF] define two different segmentations: the first one is fixed during the encoding process, whereas the second one is computed for a determined viewing frustrum. In this paper, we introduce a new SR mesh segmentation algorithm (adapted from the one detailed in [START_REF] Roudet | Multiresolution mesh segmentation based on surface roughness and wavelet analysis[END_REF]). We also propose to study the behaviour of the wavelet decomposition in the created regions, during the coding and the view-dependent reconstruction processes. Our segmentation process can be seen as a pre-processing step and is not dependent on the user's viewing position. It aims at producing homogeneous regions which share similar frequency amplitudes on the mesh surface, in other words: regions with different degrees of roughness.

None of the two previous algorithms ( [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] and [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF]) and no other paper (to our knowledge) has ever considered the influence of the non-refined parts of a mesh on the more detailed ones, in a view-dependent context. In the wavelet-based SR mesh compression setting, a subdivision scheme is used as a prediction operator during the MRA, to reduce the details lost during this coarsification process (regarded as wavelet coefficients). The most used prediction scheme for SR meshes is the Butterfly subdivision stencil [START_REF] Dyn | A butterfly subdivision scheme for surface interpolation with tension control[END_REF] (illustrated in Fig. 1 (picture (b)). The main contribution of this paper consists in considering three different possible applications of this stencil, close to the patch borders, and to study their influence during the coding and the view-dependent reconstruction processes. We propose various experimentations to demonstrate that, among these three schemes, the one we have developped can reduce the bandwidth requirement for 3-D mesh view-dependent transmission.

The remainder of this paper is organized as follows. We begin by an explanation of the MRA on meshes in Section II, which produces the wavelet coefficients. The wavelet-based segmentation algorithm we developped is then described in Section III. The different patch-aware applications of the Butterfly prediction are detailed in Section IV. Experimental results are presented in Section V, together with possible applications of our framework. As a conclusion, discussions and ideas for future work are given in the last section.

II. MR ANALYSIS ON SR MESHES

In this section, we first detail the theory involved to produce wavelet coefficients on SR structures, with a lifting scheme formulation (second generation wavelets). A SR mesh is obtained thanks to a remeshing stage, which consists in resampling an input model (with irregular connectivity). We present then the concept of the state-of-the-art SR remeshing and MRA algorithms. The MRA produces a reversible mesh decomposition into a series of approximation meshes (called "hierarchy" hereinafter) and a sequence of details: the wavelet coefficients. We finally describe the averaging rule we applied to represent all the details lost during this simplification process, in only one coarse mesh of the "hierarchy".

A. Wavelet Theory and Lifting Scheme

Mallat first introduced in 1989 [START_REF] Mallat | A theory for multiresolution signal decomposition: The wavelet representation[END_REF] the dyadic MRA and linked the wavelet transform to the filter bank theory. This MRA formulation, defined for finite energy functions, is formally described for a series of imbricated subspaces (V m ) m∈Z ⊂ L 2 (R) in which an orthonormal scaling function basis is determined. The orthogonal projection of a discrete signal s(t) into the scaling function family forms a set of approximations, obtained by the application of a lowpass filter, followed by a uniform subsampling. To recover the high frequencies lost after the application of the lowpass filter (for any approximation in the level i), we have to take into account the W i space, which is the orthonormal complement of the V i space in V i-1 . These wavelet coefficients are hence obtained by a highpass filtering.

Considering the filter bank theory, it's not always possible to construct analysis tools with good properties for compression purposes. Consequently most of the methods have benefited from the lifting scheme formulation, introduced by Sweldens [START_REF] Sweldens | The lifting scheme: A new philosophy in biorthogonal wavelet constructions[END_REF]. It moreover reduces computational costs and memory allocation, by first splitting the signal (S operator in Fig. 1, picture (a)) into even and odd components by using lazy wavelets. The following lifting steps (P and U operators in Fig. 1, picture (a)) produce a modification of this lazy wavelet basis in order to add the desired properties. These operations can be simplified thanks to the lifting formulation with finite filters. Hence, the multi-resolution synthesis is simply obtained by an inversion of the order and sign of the analysis lifting operators.

The most used prediction operator (P ) on SR meshes (the Butterfly scheme [START_REF] Dyn | A butterfly subdivision scheme for surface interpolation with tension control[END_REF]) is illustrated in Fig. 1 (picture (b)). The update operator (U ) is used to preserve the mean value of the signal. For compression purposes, the decomposition ends up with a normalisation step (N ), which is used to The most used prediction operator on SR meshes: the Butterfly subdivision stencil [START_REF] Dyn | A butterfly subdivision scheme for surface interpolation with tension control[END_REF], which allows to predict the position of each newly added (odd) vertex (in red) thanks to its coarser (even) neighboors.

adjust the scale between the odd and the even coefficients, so as to decompose the surface in a normalised basis.

One of the lifting scheme advantages is that it can be applied to irregular point sets like meshes. In practice, we use a resampling of the irregular meshes (known as remeshing), to regularize the connectivity and to benefit from a more compact representation of the connectivity data.

B. Remeshing and Wavelets on Meshes

MR analysis for triangle meshes with arbitrary topology was introduced by Lounsbery [START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF] who demonstrated that a subdivision scheme can serve as a scaling function basis to extend the wavelet theory for irregular sampled signals like meshes. The compression performances are then highly dependent on the quality of the parameterization defined during the SR remeshing.

The main SR remeshing algorithms implemented in this context [START_REF] Lee | MAPS: multiresolution adaptive parameterization of surfaces[END_REF], [START_REF] Guskov | Normal meshes[END_REF], [START_REF] Guskov | Manifold-based approach to semi-regular remeshing[END_REF], rely on the same philosophy. They aim at reducing the parametric information (tangential set of wavelet coefficients), to represent details only with their geometric attributes. For that purpose, a mesh simplification is used to produce a coarse mesh (called the base complex). The challenge consists in minimizing the distortion produced during the parameterization of the input model, when mapping each curved surface to its associated coarse triangle in the base complex. Finally, the resampling stage used to produce the SR mesh from the base complex may vary, but is always obtained with subdivision surfaces.

The Normal Mesh algorithm [START_REF] Guskov | Normal meshes[END_REF] we considered to obtain the SR models presented in this work, applies a recursive piercing procedure and unlifted Butterfly wavelets to concentrate the high-frequency information along the surface normal. The resulting meshes are ideally suited for progressive compression purposes, because almost all of the geometric details are expressed with a single scalar. This algorithm currently produces one of the best remeshes for compression purposes, but only for closed surfaces.

Given SR meshes with the fewest connectivity and parametric data to encode, efficient data structures and process- ing algorithms are used to get closer to the methods used for data sampled on regular grids. The application of the MRA on SR meshes, resulting from these latter algorithms, and mainly used for progressive compression purposes, can be based on various subdivision schemes. Most of the existing methods have benefited from interpolating subdivision filters (and in the most cases from the Butterfly stencil) for the lowresolution versions to be good approximations of the original object (in a least-squares sense).

Each mesh refinement, processed during the MR synthesis, is based on canonical quadrisections applied on every facet. This one-to-four triangle construction consists in adding three new vertices in the middle of each coarse edge. The prediction operation followed by the wavelet coefficient addition enable to recover the real position of these newly added vertices. Consequently the common representation of the wavelets consists in associating them with their corresponding coarse edges, as we can see in Fig. 2, on the first three decompositions of the Horse model.

Most of the actual state-of-the art mesh compression methods ([4] - [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF]) apply a global wavelet decomposition (same lifting filters on the entire surface). Since the considered prediction schemes generate smooth finite surfaces, another kind of prediction, quantization and/or coding could be examined for the non-smooth parts of the mesh. We developped our segmentation process in this sense and considered only Normal meshes in our study, since they have been proven to provide the best compression rates.

C. Wavelet Coefficients seen as a Segmentation Criterion

We propose to study the wavelet coefficient amplitude distribution in the "hierarchy" produced by a global MRA. Our goal is to create regions on the mesh surface with different degrees of roughness: reflected by the wavelet coefficient amplitude. We illustrate in Fig. 3, 4 and 5 the normalized distribution of the coefficient amplitude, on various resolution levels of the Horse and Venus models (remeshed by the Normal Mesh [START_REF] Guskov | Normal meshes[END_REF] algorithm). We applied a Gaussian normalization on the amplitude distributions (represented in Fig. 3, picture (c)), whose goal is to narrow extreme values. It hence allows to easier classify and segment a mesh with the considered criterion, since we can retain only the most represented samples. The application of this statistical technique (known as a confidence interval) is possible because the related histogram (depicted for the Venus model in Fig. 3, picture (b)) has a Gaussian-like normal distribution. Given the distribution averaging (x) and the standard deviation (σ), 95% of the population is kept in the chosen confidence interval.

On the globally smooth models we studied, the coefficient magnitude distributions allow to identify high curvatures characterizing the eyes, nose, mouth or ears, and also the object tips (neck or feet). This spreading emphasizes also the textured parts, such as the hair of the Venus head. These experimental amplitude distributions corroborate our previous hypothesis about the faculty of the subdivision surfaces to well predict the mesh smooth parts. Moreover even in globally smooth models, there remain some areas where other considerations should be employed.

In the Horse and Venus first four resolution levels (Fig. 4 and5), the same main features are underlined, but the fineness of these highlighted high frequencies is quite different in each level. Since we aim at producing a segmentation that identifies clearly the high frequencies lost during the coarsification process, a global consideration of all the coefficient amplitudes in the entire "hierarchy" is required. The segmentation algorithm we used in this context was conceived to apply on one mesh at a time. Consequently instead of segmenting all the approximations, we propose to compute an averaging of all the wavelet coefficient amplitudes.

We chose to segment one of the coarsest resolution levels, for each coarse triangle to be assigned a unique region number. It gives us the opportunity to independently treat each produced region, without being forced to remesh them, in the case where a subdivision connectivity is not encountered. Hence the chosen coarse level determine the number of resolution levels involved in the patch-independent MRA. Considering this setting, the averaging rule we adopted is illustrated in Fig. 6. Each edge of the coarse level is then associated to two children edges (called f ae in Fig. 6) in the immediatly finer mesh. We applied a weighted averaging where each coefficient norm is multiplied by 2 d , to take into account the decrease of the wavelets in the "hierarchy" (explained in Section II-A) -d = 0 for the coarsest edges and increasing integer values for the finer decompositions.

III. WAVELET-BASED CLASSIFICATION AND SEGMENTATION

Given the wavelet norms, averaged on one of the coarsest decompositions, we used an extension of the algorithm developped by Lavoué et al. [START_REF] Lavoué | A new CAD mesh segmentation method, based on curvature tensor analysis[END_REF], to create a mesh segmentation. This method is based on a K-Mean classification [START_REF] Gersho | Vector quantization and signal compression[END_REF].

A. Mesh Classification and Segmentation Algorithms

In the past twenty years, much work has been done in shape decomposition because of its utility in many computer graphic applications. These methods are usually designed to solve specific problems and are difficult to compare. Some applications use segmentation principles to simplify treatments like texture mapping, parameterization, mesh editing, deformation or compression on complex meshes with a high genus, for example. They are generally faster and more simple on surface patches homeomorphic to a disc. The partitioning criterion generally used in this setting is the discrete curvature or the planarity information. Our segmentation process use a different criterion together with an adaptation of the classification and segmentation algorithms implemented by Lavoué et al. [START_REF] Lavoué | A new CAD mesh segmentation method, based on curvature tensor analysis[END_REF].

They used a curvature tensor estimation [START_REF] Cohen-Steiner | Restricted Delaunay triangulations and normal cycle[END_REF] to compute the principal curvature values in each vertex. The produced segmentations delimit smooth regions surrounded by sharp edges on CAD objects. Our adaptation replaces this curvature criterion by our previously defined wavelet norm averaging.

The K-Mean classification algorithm was first used to create two groups of vertices (referred as clusters): one with the smallest amplitudes (represented in dark blue in next figures, and referred as the smooth cluster) and the other with the highest ones (in light green). After several iterations, starting with two randomly determined centroïds, each vertex is then associated to a cluster C i and a "roughness value" r i . Homogeneous connex patches are then deduced with a region growing and labeling algorithm adapted from [START_REF] Lavoué | A new CAD mesh segmentation method, based on curvature tensor analysis[END_REF]. More precisely, the studied measure is transmitted from vertices to triangles, starting from seed triangles whose incident three vertices belong to the same cluster. Thanks to this framework, a mesh decomposition in a small number of regions can be created at any given resolution level.

B. Segmentation results

We illustrate in Fig. 7 to 9 the different steps involved in our segmentation process, respectively for the Horse, Venus and Skull Normal models. Colors used for the patches were randomly chosen. The arrows in the pictures serve to indicate which region will be further studied in the rest of the paper. The result of our averaging rule is depicted on meshes which have a various number of vertices (because different numbers of resolution levels were considered). It has a tendancy to stump the isolated details and sharpen the very important ones (highlighted in various resolutions). The number of created patches is fully dependent on the choice of the coarse level. We examined different choices, to study the influence of the chosen coarse level, on the further detailed experimentations.

Given the segmentations of the Normal models on a coarse level, the final stage of our pre-processing consists in projecting the coarse regions on the original SR model. This stage is simply realized incrementally, resolution per resolution, where the four children facets associated to each coarse triangle are assigned the same cluster and region number as their father triangle. The resulting fine segmentations can now be the input of our patch-independent MRA, detailed in the following.

IV. REGION-BASED MRA FOR VIEW-DEPENDENT RECONSTRUCTION

As a preliminary step of the development of a locallybased R-D optimized coding scheme, we propose to detail in this Section the three different applications of the Butterfly stencil we examined close to the patch borders, during the region-based MRA and coding.

In our first consideration (designed later by "No PB": for No Patch Borders taken into account), the unlifted Butterfly wavelet decomposition is realized as if any patch was defined. This rule is accurate if a uniform reconstruction of each patch is adopted (with approximately the same L 2 error orders, in each region). In other cases, an alteration of the quality of some regions can appear due to the influence of the "poor" reconstructions of their neighboors, for example.

For these other cases (which don't necessarily involve a uniform reconstruction of each patch, like view-dependent transmission and rendering), we propose to examine two different adaptations of the Butterfly stencil close to the patch borders. These two adaptations (designed later by "PB") will be applied when each patch is seen as an independent non-closed surface. With this latter setting, any region can influence its neighboors during the "non-uniform" region-based reconstructions.

Fig. 10 shows the amplitude and polar angle (the angle between each coefficient and its related surface normal vector) distributions for each of the three rules. We can deduce that the two predictions associated to the "PB" consideration (histograms on the middle and on the bottom) are not as good as the classical ("No PB") one (on the top), because the wavelet amplitude and polar angle distributions are generally more dispersed. The first rule we considered (close to the patch borders) uses two extensions of the classical Butterfly stencil (illustrated in Fig. 11) to predict the new vertices situated on the borders (picture (a)) or surrounded by extraordinary vertices (picture (b)), as it can appear close to the patch borders.

The goal of our new rule (designed later by "PB SYM") is to recreate the "missing coarse vertices" in the classical Butterfly stencil (illustrated in Fig. 1). These vertices are missing because we take into account the patch borders in the MRA. The position of these created "ghost vertices" is deduced from the other real coarse vertices involved in the Butterfly stencil. We illustrate in detail in Fig. 12 the concept we used for deducing them, with a tendancy to favor the diagonal symmetry. We also enumerate all the possible cases we can encounter and for the ones for which a diagonal Figure 12. Definition of our new scheme, used when some of the coarse vertices are missing in the Butterfly stencil, due to patch borders (illustrated with big dashed lines). Top left: classical Butterffly stencil; Top right: method used to recreate the "missing coarse vertices" in the Butterfly stencil. We favor the diagonal symmetry (computed thanks to the red vertices in the next pictures), but for the cases where it is not possible, we define an equivalent rule (illustrated with colours in the middle of this figure). The different configurations are highlighted with big rectangles, when only a coarse vertex (top in red), two coarse vertices (middle in blue) or three coarse vertices (bottom in green) are missing.

symmetry cannot be computed, we define an equivalent rule (illustrated with colours in the middle of Fig. 12).

In Fig. 10, we can observe that our new rule distributions (on the bottom) are closer to the classical ("No PB") ones (on the top). Moreover we have the possibility to perfectly decode some regions of a mesh while other are at the same time "poorly" reconstructed.

V. EXPERIMENTAL RESULTS AND APPLICATIONS

We present in this Section, various experimental results we obtained on the Normal meshes, segmented with our wavelet-based partitioning algorithm, but any other kind of SR mesh segmentation could also have been considered, like the ones implemented by Sim et al. [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] or by Payan et al. [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF].

We first propose a visual comparison of the mesh distortion in Fig. 13. We compared two different "viewdependent" reconstructions of the segmented Skull model (produced by the "No PB" consideration). Hence we com-Figure 13. Mesh distortion on two different "view-dependent" reconstructions, presented on the entire mesh (top) and on the non-smooth cluster (bottom) of the Skull segmented model (illustrated in Fig. 9). Patch borders are not taken into account during the MRA (referred as the "No PB" consideration) and any wavelets are added on the smooth cluster. In the left pictures any prediction operator is considered, whereas in the right ones the Butterfly prediction is used. The colours depend on the magnitude of the local L 2 errors, from the minimal (blue) to the maximal (red) value. These pictures were realized thanks to the "Mesh" software [START_REF] Aspert | MESH: Measuring errors between surfaces using the hausdorff distance[END_REF].

puted the L 2 errors with the "Mesh" software [START_REF] Aspert | MESH: Measuring errors between surfaces using the hausdorff distance[END_REF], on the entire Skull model (in comparison with the irregular original model), and also on its non-smooth cluster. In the left part any prediction operator nor wavelets (only canonical quadrisections) were considered on the smooth cluster. Hence it can be interpreted as a non-visible part in a view-dependent consideration, whereas the other cluster is perfectly decoded. The only difference in the right part is that the Butterfly prediction was used in the smooth cluster. As expected, these pictures show that a less important distortion can be obtained with the Butterfly prediction, when patch borders are not taken into account during the MRA ("No PB").

This assumption is also confirmed by the Table I. It results from a computation of the L 2 errors for the "No PB" and "PB" considerations, with or without a Butterfly prediction on the smooth region(s). The distortion is presented for all the segmentated models we previously commented, only for one of their non-smooth regions (indicated with an arrow in Fig. 7 to 9). In each studied mesh region, the smallest L 2 errors are emphasized with bold characters. The same errors are obtained in the last two columns, because we used a "PB" consideration which doesn't depend on the prediction used in the neighbooring smooth cluster and thus gives the smallest distortions. For each model, the "No PB" consideration associated with a Butterfly prediction in the smooth cluster always gives the better results than without any prediction.

We finally present the bitrate-PSNR curves in Fig. 14, computed by only taking into account the non-smooth region of the segmented Skull model (the Butterfly prediction is used -without any wavelets-in the smooth region). The bitrate is reported with respect to the number of vertices in the semi-regular (SR) mesh. These curves were obtained with the view-dependent geometry coding (developped by Payan et al. [START_REF] Payan | View-dependent geometry coding of 3D scenes[END_REF]), which we adapted to our segmentation process.

P SNR = 20 log 10 peak/d, where peak is the bounding box diagonal and d the L 2 relative error, corresponding to the following L 2 distance d(X, Y ) between the surfaces X and Y:

d(X, Y ) = 1 area(X) x∈X d(x, Y ) 2 dx 1 2 ,
where d(x, Y ) is the Euclidean distance from a point x on X to the closest point on Y. The results we deduced from the Table I are confirmed by the repartition of the curves (the "PB" consideration gives the best results at any bitrate). Moreover we can notice that our new prediction scheme (associated to the "PB SYM" consideration) performs better than the other "PB" rule, for view-dependent reconstruction purposes. For the "No PB" consideration, we can see that the two curves reach quickly their asymptotic value which is linked to the L 2 errors illustrated in the bottom part of the Fig. 13.

VI. CONCLUSION AND FUTURE WORK

A new wavelet-based segmentation algorithm for SR meshes was introduced as a pre-processing step of a viewdependent geometry coding and transmission of 3-D scenes. Our segmentation process aims at constructing regions with different degrees of roughness, reflected by the wavelet coefficient amplitudes (associated to each resolution level). The simplification meshes were obtained with an unlifted Butterfly wavelet decomposition on Normal meshes. As a preliminary step of the development of a locally-based R-D optimized coding scheme, we have studied the behaviour of the wavelet decomposition in the created regions, during the coding and the view-dependent reconstruction processes. We particularly investigated three different possible wavelet decompositions, close to the patch borders. One of them is a new consideration and has given the best results for viewdependent reconstruction purposes.

As an extension of the current work, some future research can be performed in the following areas. First, we may consider the patch-independent R-D optimized compression and coding. New prediction schemes and coding techniques could be proposed for the non-smooth regions (where the predictions with actual subdivision schemes can be improved), together with more subjective distortion metrics, based on human vision. Our goal will be to improve the compression bitrates on natural objects, which can be composed of non-smooth textured parts. A possible issue could consist in conceiving a statistical analysis model of the surface. The critical elements could hence serve to regenerate the same visual aspects and high frequencies of the studied surface. Another interesting consideration would be to take into account the surface anisotropy, to better predict shapes with features like sharp creases, corners or rough textures. Moreover, a fractal analysis could also be adopted in noisy regions.

We could also conceive our segmentation process differently, by better analysing the decrease of the wavelets and their relation to the surface discrete roughness or saliency. Finally other applications could benefit from our patch-based MRA, like watermarking. It would allow to apply different marks according to the visual aspect of the surface. Another interesting problem which can benefit from our framework are the error-resilient mesh encoding techniques.

Figure 1 .

 1 Figure 1. (a) Principle of the lifting scheme for the decomposition of a fine mesh (M k ) into a coarser one (M k-1 ). D k+1 represents the details lost during the simplification. (b)The most used prediction operator on SR meshes: the Butterfly subdivision stencil[START_REF] Dyn | A butterfly subdivision scheme for surface interpolation with tension control[END_REF], which allows to predict the position of each newly added (odd) vertex (in red) thanks to its coarser (even) neighboors.

Figure 2 .

 2 Figure 2. (a) Original Normal Horse model; (b-d) Wavelet coefficients represented as 3-D vectors (in red) linked to the edges of the first three decompositions (multiplication factor used to emphasize them: 10).

Figure 3 .

 3 Figure 3. Distribution of the wavelet coefficient norm, on the first resolution level of the Normal Venus model. (a) Original model; (b) Histogram of the normalized coefficient norms associated to every resolution level; (c) The Gaussian normalization method we used to define a confidence interval (in red); (d) Color scale used in this figure and the next ones.

Figure 4 .

 4 Figure 4. Gaussian normalized distributions of the wavelet coefficient norm, on the first four resolution levels of the Normal Horse model.

Figure 5 .

 5 Figure 5. Gaussian normalized distributions of the wavelet coefficient norm, on the first four resolution levels of the Normal Venus model.

Figure 6 .

 6 Figure 6. Wavelet "fine averaging association". For an edge en in a coarse decomposition, we compute an averaging of its wavelet norm and the norms of its finer associated edges (fae) in all the existing resolution levels.

Figure 7 .

 7 Figure 7. Illustration of the different steps involved in our classification and segmentation processes, on the 5 th level of the Normal Horse model. (a) Averaging of the wavelet norms in the 5 th level followed by (b) the K-Mean classification and (c) segmentation in 5 regions; (d) Fine projection of the segmentation on the SR original model whose features can be better appreciated with a Phong shading (e).

Figure 8 .

 8 Figure 8. Illustration of the different steps involved in our classification and segmentation processes, on the 6 th (left) and the 4 th (right) levels of the Normal Venus model. (a, c, f) Averaging of the wavelet norms in a coarse level followed by (b, d) the K-Mean classification and (g) segmentation in 6 regions (on the 4 th level). Three regions are obtained in the 6 th decomposition (left). (e) Fine projection of the 4 th level segmentation on the SR original model.

Figure 9 .

 9 Figure 9. Illustration of the different steps involved in our classification and segmentation processes, on the 5 th level of the Normal Skull model. (a) Averaging of the wavelet norms in the 5 th level. The segmentation in two regions is illustrated in the SR original model, whose features can be better appreciated with a Phong shading (c, e).

Figure 10 .

 10 Figure 10. Amplitude (left) and polar angle (right) distributions in every resolution level of the Venus Normal segmented model (right segmentation of Fig. 8 considered). The red boxes highlight the differences noticed in the two "PB" distributions (middle: classical rulebottom: our new rule), in comparison with the distributions for which the classical Butterfly stencil was used, without taking into account the patch borders (top).

Figure 11 .

 11 Figure 11. (a) Special Butterfly stencil used to predict the red vertex, situated on the mesh border (for non-closed 3-D meshes); (b) Extension of the classical Butterfly stencil for extraordinary vertices (scheme proposed by Zorin et al. [23]).

Figure 14 .

 14 Figure 14. Bitrate-PSNR curves for the non-smooth region of the segmented Skull model, where the Butterfly prediction is used (without any wavelets) in the smooth region. The bitrate corresponds to the bit allocation after quantization in the SR non-smooth patch.

Table I L

 I 2 ERRORS FOR THE "NO PB" AND "PB" CONSIDERATIONS, ON THE REGIONS INDICATED WITH AN ARROW IN FIG. 7 TO 9. ANY PREDICTION OPERATOR OR THE BUTTERFLY PREDICTION TOGETHER WITH ANY WAVELETS WERE CONSIDERED ON THE SMOOTH CLUSTER, WHEREAS THE OTHER CLUSTER WAS DECODED PERFECTLY. Vsr' = number of vertices in the SR mesh. 'Butt' = the Butterfly prediction was used in the smooth cluster.

		nb lev	# Vsr	No PB	No PB Butt	PB	PB Butt
	Venus part.	6	21,545	9.053.10 -4	4.107.10 -4	8.301.10 -7	8.301.10 -7
	Venus part.	4	76,193	1.345.10 -4	1.015.10 -4	1.456.10 -6	1.456.10 -6
	Horse part.	5	7,857	6.414.10 -5	5.616.10 -5	7.775.10 -8	7.775.10 -8
	Skull part.	5	56,865	5.260.10 -4	3.433.10 -4	5.990.10 -7	5.990.10 -7

'nb lev' = number of resolution levels. '#

ACKNOWLEDGMENT I would like to address special thanks to Frédéric Payan for his R-D optimization code he gave and explained me. I would like to thank also Marc Antonini for the opportunity he offered me to work on his team in the I3S lab, in Sophia-Antipolis. I finally don't forget Andrei Khodakovsky who has provided me the remeshed models used in this work.


Céline Roudet
email: croudet@liris.cnrs.fr

Florent Dupont

Atilla Baskurt

Semi-Regular 3D Mesh Progressive Compression and Transmission based on an Adaptive Wavelet Decomposition

Keywords: Adaptive compression, view-dependent reconstruction, ROI decoding, mesh segmentation, mesh classification, multiresolution analysis, geometric wavelet, lifting scheme

We introduce a new patch-based multi-resolution analysis of semi-regular mesh surfaces. This analysis brings patch-specific wavelet decomposition, quantization and encoding to the mesh compression process. Our underlying mesh partitioning relies on surface roughness (based on frequency magnitude variations), in order to produce patches, representative of semantic attributes of the object. With current compression methods based on wavelet decomposition, some regions of the mesh still have wavelet coefficients with a non negligible magnitude or polar angle (the angle with the normal vector), reflecting the high frequencies of the model. For each non-smooth region, our adaptive compression chain provides the possibility to choose the best prediction filter adjusted to its specificity. Our hierarchical analysis is based on a semi-regular mesh decomposition produced by second-generation wavelets. Apart from progressive compression, other types of applications can benefit from this adaptive decomposition, like error resilient compression, view-dependent reconstruction, indexation or watermarking. Selective refinement examples are given to illustrate the concept of ROI (Region Of Interest) decoding, which few people has considered, whereas it is possible with JPEG2000 for images.

INTRODUCTION

Three dimensional objects and scenes find their way into more and more applications, thanks to the ever increasing bandwidth available in modern telecommunication networks, such as the High Speed Internet, or 3G mobile networks. At the same time, user expectations for rendering require increasingly complex 3D models. A triangle mesh is actually the most common representation for objects and scenes. This modelling includes geometry and topology information, which can be expensive in terms of computation, storage, and transmission, even with today's devices and networks. Multiresolution (MR) techniques for triangle meshes with arbitrary topology was introduced by Lounsbery, 1 in order to represent data with multiple Levels of Detail (LOD). This scalable representation is commonly produced by a wavelet transform, which was extended for irregular sampled signals like meshes. Two approaches are possible, considering directly the irregular structure or using a subdivision scheme as a scaling function basis. In the latter case, the canonical quadrisection produced by the subdivision schemes imposes to apply an analysis on semi-regular (SR) meshes. These are considered as functions via the parameterizations inherently defined by the remeshing.

In this paper, we consider the SR surface representation because the target applications do not impose a lossless compression scheme. This paradigm delivers efficient data structures and processing algorithms, closer to the ones used for data sampled on regular grids.

The main SR remeshing algorithms rely on the same philosophy, reducing most of the connectivity and parametric information from the mesh. This way, details are represented only with geometric attributes. For that purpose, the mesh is simplified to produce the base complex on which the input model will be parameterized.

Two approaches are considered: chartification or progressive decimations. Finally, the resampling stage may vary but is always based on subdivision connectivity construction.

The first inception was introduced by Eck et al. 2 They partitioned the original mesh into Voronoï tiles. Its dual construction (the Delaunay triangulation) was used to produce the coarse model. However, it is possible to take more into account the geometric and visual properties of the initial surface, during the base complex construction. Gioia 3 experimentally obtained on average twice less wavelet coefficients than with the previous method, for natural and CAD objects. They both used harmonic maps to construct the local parameterization, which minimizes the distortion when mapping a curved surface to the plane.

The other class of methods use progressive decimations based on constructing a mesh hierarchy thanks to the vertex removal or edge collapse operation. In the MAPS algorithm, [START_REF] Lee | Maps: Multiresolution adaptive parameterization of surfaces[END_REF] the vertices chosen to be removed are those that withdraw the fewest geometrical and topological information. A conformal mapping, consisting in expressing the decimated vertices as barycentric coordinates, is used, together with the Loop subdivision to produce the SR mesh. But Guskov et al. observed that this decimating context is favorable for constructing a global parameterization. They used it together with a recursive piercing procedure and unlifted Butterfly wavelets in their Normal Mesh algorithm. [START_REF] Guskov | Normal meshes[END_REF] The resulting meshes are ideally suited for progressive compression, because most of the geometric details are concentrated along the surface normal, expressed with a single scalar. This algorithm currently produces one of the best remeshes for compression, but only for closed surfaces.

Because most of the previously described algorithms suffered from smoothness artefacts at patch boundaries, a new class of algorithms appeared. They construct a globally smooth parameterization associated with the decimation [START_REF] Khodakovsky | Globally smooth parameterizations with low distortion[END_REF] or chartification [START_REF] Guskov | Manifold-based approach to semi-regular remeshing[END_REF] principles. The smoothness of the parameterization is obtained not only within each coarser triangle, but also across patch boundaries and corners. It is also directly related to how well the mesh can be compressed, together with providing good approximations and no degenerated mesh elements.

The application of the MR analysis on the meshes, resulting from these latter algorithms may be based on various subdivision schemes. Most of the existing methods [START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF][START_REF] Gioia | Reducing the number of wavelet coefficients by geometric partitioning[END_REF][START_REF] Khodakovsky | Compression of normal meshes[END_REF] benefited from interpolating subdivision filters to provide numerical stability of the fitting operation. But other authors [START_REF] Bertram | Biorthogonal loop-subdivision wavelets[END_REF][START_REF] Li | Unlifted loop subdivision wavelets[END_REF] recently proposed a wavelet construction based on the Loop subdivision and the lifting scheme. They managed to overcome the Khodakovsky [START_REF] Khodakovsky | Progressive geometry compression[END_REF] filter drawbacks by constructing stable schemes for the wavelet analysis and synthesis with a linear time complexity. These actual state of the art mesh compression methods, presented before, generally apply a global wavelet decomposition, using the same filters on the entire surface. The produced coefficient amplitude and polar angle are hence heterogeneously distributed. They mainly depend on the remeshing algorithm and the prediction power of the considered scaling functions.

Contributions:

The previous diagnostic encouraged us to propose a new MR analysis framework designed to improve the compression bitrates and produce a more flexible 3D visualization, adapted to user resources and expectations. This framework uses a segmentation algorithm based on the wavelet coefficient magnitude, which every remeshing or compressing algorithm tends to minimize. Each produced partition share surface roughness homogeneity, inherently reflected by wavelet coefficient magnitude. They are ideally suited for adapting the decomposition, quantization and/or encoding steps, in order to reduce the information to encode or set up view-dependent refinements. Our main contribution is the use of our adaptive framework to propose a ROI decoding based on the user's point of view. The results we obtained, when considering view-dependent reconstructions of the "Horse" model, showed significant bitrate improvements compared to view-independent approaches.

OVERVIEW OF OUR APPROACH

The main features of our framework are presented in Fig. 1 and detailed in the following sections.

The input of the analysis is a semi-regular mesh M sr obtained by applying a remeshing algorithm on an original irregular mesh M ir . A global wavelet analysis first decomposes this SR model into n coarser meshes M 1 , M 2 , ..., M n . Then, a shape segmentation method, [START_REF] Roudet | Multiresolution mesh segmentation based on surface roughness and wavelet analysis[END_REF] presented in Section 3, processes the wavelet coefficient magnitude in all resolution levels. Any particular mesh M i of this hierarchy can be the "support" for the classification and segmentation steps. We compared the application of these last-mentioned steps on the first and last (M c ) decomposition levels. Hence it is easy to compute a global mean measure which takes into account the entire hierarchy on which each coefficient reveals the high frequencies lost during all the coarsifications applied from the original model. The goal of this segmentation is to construct homogeneous regions according to the coefficient magnitude, that every remeshing or compressing algorithm tends to minimize.

Once we have partitioned the first resolution level, we project it on the coarsest resolution level M c , to provide thereafter, the possibility to compress independently each constructed partition. We chose a projection rather than a patch remeshing, to preserve the initial remeshing properties. Then a patch refinement is necessary for both considered rules, to conclude our hierarchical partitioning. These stages are described in Section 4 together with the locally adapted MR analysis we used. Finally our experimental results are presented in Section 5, showing the additive information needed for proposing a patch independent coding. Other possible applications (which can benefit from the described redundancy) are finally illustrated.

On the synthesis side, after an independent entropy and zerotree decoding, the coarsest patches are first glued and followed by a reversed wavelet transform. The reconstructed object M rec can finally be compared to the original one, so as to evaluate the distortion.

SHAPE PARTITION ALGORITHM

To obtain regions gathering common characteristics, most of the existing segmentation algorithms are based on the planarity information of the faces [START_REF] Garland | Hierarchical face clustering on polygonal surfaces[END_REF][START_REF] Cohen-Steiner | Variational shape approximation[END_REF] or the discrete surface curvature computed in each vertex. [START_REF] Sun | Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing[END_REF][START_REF] Razdan | A hybrid approach to feature segmentation of triangle meshes[END_REF] The watershed algorithm used by these latter approaches tend to extract only regions surrounded by high curvatures and do not handle correctly the boundaries between patches, which are either fuzzy or jagged. The method developed by Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] overcomes these drawbacks thanks to a K-Mean classification algorithm instead of the watershed, together with boundary rectifications, in order to more precisely detect curvature transitions on CAD objects.

We adapted their algorithm, formerly conceived for the compression of CAD objects, with sharp edges and corners that generally separate smooth regions. Our extension uses the same concepts based on the production of homogeneous partitions. However we consider the wavelet coefficient magnitude instead of the principal curvature values.

Wavelet coefficients as a segmentation criterion

The decorrelation power of the wavelets has been demonstrated for images, by its incorporation in the JPEG2000 standard, and even for meshes in the MPEG4 standard. We propose to study the wavelet coefficient magnitude distribution associated to a global MR analysis on Normal Meshes. [START_REF] Guskov | Normal meshes[END_REF] But the input model can also be remeshed by any algorithm, regardless of its wavelet distribution characteristics.

The non-lifted butterfly wavelet transform used for this task belong to the class of second-generation wavelets introduced by Sweldens, 18 specifically designed to adapt to irregular point sets. For the usual 3D models, subdivision surfaces are a well adapted prediction in homogeneously smooth regions, because they generate a smooth finite surface. Consequently the highest coefficient magnitudes are associated to the high frequencies (features, textures or noise) of the model. A segmentation based on their polar angle can also be considered if the SR model results from a different kind of remeshing algorithm, like MAPS. [START_REF] Lee | Maps: Multiresolution adaptive parameterization of surfaces[END_REF] However the distribution histogram produced by a Normal Mesh (presented in the last picture of Fig. 3) is too narrow around zero for applying this kind of classification, even after a Gaussian Normalization (used in our results).

For 3D meshes, the facet refinement during the MR synthesis, consists in first applying a canonical quadrisection. For each triangle, the position of the three newly added vertices is obtained by the prediction operation, followed by the wavelet coefficient addition. Consequently wavelets are commonly represented in association with their corresponding coarser edges, as we can see in Fig. 2. The classification and segmentation algorithms we adapted were formerly designed to partition mesh data associated to vertices. We tested different scenarii considering directly the edge-associated information or the data means computed on incident vertices or facets. The vertex-based classification produced the best results.

We indicate in Fig. 3 several coefficient distributions on the "Venus" model. A Gaussian normalization was used, to trim extreme values of the interval, leading to even better results. This confidence interval creation is possible because the associated histograms (presented in Fig. 3) have a Gaussian normal distribution. But as the segmentation algorithm can only be applied on one mesh of the hierarchy, we propose to aggregate all the coefficients in one mesh so as to take into account all the high frequencies lost during the coarsification produced by the subdivision context. Picture (f ) of Fig. 3 illustrates this kind of aggregation, on the first resolution level. We compare it with our second aggregation rule in next subsection.

On globally smooth models, the coefficient magnitude distribution allows to identify high curvatures characterizing the eyes, ears, feet or the nose of the "Rabbit" and "Horse" models. This distribution emphasizes also the textured parts, such as the hair of the "Venus" head. For them, another prediction scheme, decomposition or quantization can provide better compression results.

Mesh classification and segmentation stages

Our adaptation of the classification algorithm of Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] was first used to create two groups of vertices, one with the smallest amplitudes and the other with the highest ones. We indicate the results obtained for the coefficient magnitude, in our context, but it is also possible to combine other criteria (for example the polar angle, for some kinds of remeshing). The construction of the partitions, using the region growing algorithm, consists in transmitting the studied measure from vertices to triangles, starting from seed triangles having their three vertices on the same cluster. In comparison to Lavoué algorithm, we didn't use the region merging step, aiming at reducing the oversegmentation, because our coarse projection associated to the first aggregation rule or the coarse classification produced by our second rule already play this role.

Thanks to this framework, a mesh decomposition in a finite number of regions can be created at a given resolution level, as we can see in Fig. 4 and 5 for the "Venus" and "Horse" models. The colors used for the partitions were randomly chosen. For every classification picture, the dark color is always associated to the smooth cluster. Since our goal consists in an independent analysis and synthesis adapted to the specificity of each patch or the user's point of view, we need to apply a separate MR analysis or synthesis in each produced partition. We describe, in the next section, the method used and comment on the rest of the pictures.

LOCAL MULTIRESOLUTION ANALYSIS COMPUTED ON PRODUCED PARTITIONS

In order to analyze, quantify, and encode separately each connex region, we need to decompose independently each one into several levels. That's why we considered two different strategies in association with our two aggregation rules. We obtained good approximations on the coarsest level, in comparison with the former segmentation linked to the first resolution level. The final stage projects back the approximations on the finest model (the original one), to begin the local analysis.

Projection of the segmentation in the hierarchy

We now detail the projection of our first considered classification (based on the first aggregation rule), on the coarser resolution levels. If we assume that the segmentation was computed on the resolution level n, the projection will start on the immediately coarser level (n + 1) and will continue until the coarsest level or until the produced regions are too far away from the initial ones.

The coarse triangle cluster affiliation is determined according to its incident four finer facets. In the rule we adopted (illustrated in Fig. 6), if at least three of the four fine triangles belong to a given cluster, the corresponding coarser triangle will also belong to this cluster. If an equality occurs, we favor the non smooth cluster (light color in Fig. 6) to ensure no feature is left out in the non-smooth cluster.

Independent decompositions

Once the projection on the finest level is completed, the mesh can be locally analyzed, considering for example two different prediction schemes according to the cluster affiliation of each patch, to separate treatments on smooth parts from rough sites. But we can also think of a patch-based specific and different treatment, depending on its high frequency level. In any cases, it produces as many "wavelet files" as created regions.

Zerotree and entropy coding

We have considered to encode the wavelet coefficients with the Khodakovsky et al. [START_REF] Khodakovsky | Progressive geometry compression[END_REF] zerotree representation, which is based on the coefficient distribution in the MR analysis hierarchy. Their code uses the parent-child coefficient correlations, minimizing the significant bits to encode at each step. Moreover the highest order bits of the largest magnitude coefficients are sent first. This strategy allows to obtain, for each bitrate, the best reconstructed model that produces the smallest distortion. A scalar quantization is generally used, so there are indeed three independent coders (one for each coordinate). Finally, an arithmetic coding is added to further compress the data.

Apart from the wavelets, the compression file size also includes the scale coefficients corresponding to the encoding of the coarsest mesh. We used the embedded coarsest geometry encoding method of Khodakovsky et al., [START_REF] Khodakovsky | Progressive geometry compression[END_REF] where the coarsest geometry is stored with the zerotree representation. The connectivity is compressed with a single rate (Touma and Gotsman [START_REF] Touma | Triangle mesh compression[END_REF] ) coder.

The data flow are now ready to be transmitted over the network and reconstructed on the client side. All the analysis stages we described need to be reversed on the decoder side. We now present the possible applications of our framework.

EXPERIMENTAL RESULTS AND APPLICATIONS

Compression results

Fig. 7 exhibits three rate/distortion (r/d) curves produced with the global MR analysis (blue) and our local extension with its two aggregation rules (green and red), for three studied models. The non lifted butterfly wavelets were used everywhere for both global and local cases. The remeshing error indicated in this figure, corresponds to the distortion produced by the underlying SR remeshing. This limit represent the highest quality the considered encoders can reach.

P SN R = 20 log 10 peak/d where peak is the bounding box diagonal and d the L 2 relative error, corresponding to the following L 2 distance d(X, Y ) between the surfaces X and Y :

d(X, Y ) = 1 area(X) x∈X d(x, T ) 2 dx 1 2 .
This distance was computed with the MESH tool 20 by taking the max of d(X, Y ) and d(Y, X). The rate is reported in bits per vertex (b/v) according to the number of vertices in the original irregular input mesh. We can see the amount of extra information necessary for the local analysis compared to the global one, using a common treatment for all the regions of the surface.

The associated number of created regions and the percentage of the identified clusters (which can be smooth or rough) are reported in Table 1, for a better understanding of the curves. This table also compares the segmentations produced by both aggregation rules. First of all, we can see that the second rule has a tendency to produce a less amount of regions, which generally denotes fewer boundary edges. This observation is interesting for compression purposes, for which the number of additional information produced by our independent coding will be smaller. However the clusters produced by this second rule are visually less accurate when we compare them to the finest classification displayed at the beggining of each previous figure. The extra cost of our local framework when applying the same treatment to each partition can be evaluated to 3 or 4 dB in average compared to the global treatment, for a bitrate greater than 0.5 b/v. The redundancy introduced by the partitioning can be compensated by a well adapted decomposition on each region, that can counterbalance the redundant information added by our local analysis. For smooth clusters, the prediction produced by the Butterfly subdivision scheme appears really accurate because the wavelet coefficients are close to zero. For other regions, higher details are generally needed to represent high frequencies, so another type of prediction can be a benefit to counterbalance our redundancy problems.

Apart from compression, our framework can also serve as a basis for lots of other applications. We present in the next section two examples, when considering selective refinement depending on the user's resolution terminal or point of view. Subdividing smooth partitions can be sometimes sufficient when visualizing the object in a low resolution device. Finally, if the user is interested in visualizing only a given mesh region, the coarsest resolution level can be sufficient for other partitions. (c,e) Reconstructions produced with the non lifted Butterfly subdivision, followed by the wavelet addition in the non smooth parts. We have reported the corresponding coding file size in bytes and L 2 error in units of 10 -4 for each considered reconstruction.

object and send each region individually or sequentially to the client, in order to optimize their resolution according to their visibility. These latter methods are generally robuster to transmission errors than global approaches.

Such as the work recently published by Cheng et al., [START_REF] Cheng | The progressive mesh compression based on meaningful segmentation[END_REF] we propose a part-based mesh reconstruction with different focuses depending on the user's expectations. Our method can decode perfectly the full details of a meaningful part, without doing it for other patches. Moreover we obtain a better rendering for the identified "non meaningfull" regions using the subdivision surfaces, instead of keeping the coarse facets. We illustrate this improvement in Fig. 8, which also demonstrate that for the identified smooth patches, the wavelets are generally not needed for objects visualized on low resolution screens. It can hence accelerate the rendering with a comparable visual quality. For each reconstruction, illustrated in Fig. 8, we specified the corresponding compressed file size in Kbytes and the L 2 error in units of 10 -4 (Hausdorff distance). Pictures (a) and (f ) present the reconstructions obtained when applying a global synthesis for comparison.

The first observation is that the single subdivision applied on the smooth regions produces good reconstructions with a lower L 2 error than without any subdivision. More specifically, with approximately twice fewer bytes, we obtain a good reconstruction of the "Horse" model, which preserves the important characteristics of the object. This decompression can be sufficient for a visualization on a low resolution device. The "Feline" model is also well reconstructed with our first local rule, but the file size reduction is less significant because it contains a more features and textured parts.

Regarding a given Hausdorff distance (e 1 ), we finally compared the visual quality of two different reconstructions, considering our local approach (used to produce picture (e) of Fig. 8), and the global synthesis. The results, illustrated in Fig. 9, highlight that for the same Hausdorff distortion, our reconstruction better preserves the features (feet and head), for which a more important number of bits were allocated than for the body. "Horse" head was zoomed in, to better appreciate it. This observation is highlighted by the second distortion measure we have considered (e 2 ). This objective structural distortion measure (called MSDM) was introduced by Lavoue et al [START_REF] Lavou | Perceptually driven 3d distance metrics with application to watermarking[END_REF] in 2006. MSDM uses geometric metrics, based on curvature analysis computed on local windows in the analysed mesh. The objects are hence compared and evaluated through a subjective experiment, based on human evaluation of a set of distorted objects. Similar objects have a distortion close to 0. Left picture remembers the original irregular mesh. The reconstruction presented in the middle, was produced with our local framework where subdivision is only followed by wavelet addition in non-smooth regions. Right reconstruction was obtained from a global wavelet decomposition. We have reported the corresponding coding file size in bytes (B). The distortion errors e1 and e2 correspond respectively to Hausdorff distance (in units of 10 -4 ) and Lavoué et al. [START_REF] Lavou | Perceptually driven 3d distance metrics with application to watermarking[END_REF] MSDM metric.

ROI decoding

We also considered applications where the user is interested in a caracteristic part of the mesh, as for example "Horse" head. In this context, we compared in Fig. 10 two reconstructions of the "Horse" model, with similar local distortion computed in "Horse" head (with Hausdorff distance). We also compared the compressed file sizes, associated to view-independent method (global: on top of the figure) and our view-dependent approach (down), for which the underlying segmentation is mentioned. In this latter case, our method is able to transfer and decode only details associated to the considered region. The other wavelet coefficients can be sent afterwards, when the user's point of view changes.

Hence, for a similar visual quality (when user's interest only focuses on the head region), our approach saves more than 50% of the bitrates. Sim et al. [START_REF] Sim | Rate-distortion optimized compression and view-dependent transmission of 3-D normal meshes[END_REF] obtained comparable results with their optimized bit allocation which takes into account only visible disjoint fragments in the mesh. Since our mesh partitioning isolates features which generally correspond to semantic object parts, the user's ROI selection can be quicker with our method, because the actual ROI we can consider are tightly linked to our underlying segmentation. Hence, instead of indicating a set of facets or fragments corresponding to the desired ROI, the user just need to select a partition produced by our prior segmentation. In this context, our first partitioning rule gives clearly better results, except for "Horse" model for which our two segmentations are very close.

CONCLUSION AND FUTURE WORK

The main contribution of this work is the use of our patch-based decomposition framework, to propose a viewdependent visualization, adapted to user's resources and expectations. This framework was formerly conceived to apply different decompositions, quantizations and coding treatments on specific identified regions. It provides an entire adaptive compression chain, based on any prior segmentation of the mesh surface. Our algorithm is fast and applicable to any semi-regular triangulated surface. We showed that the redundancy introduced by the local MR analysis can be compensated by a well adapted treatment on each analyzed region.

We first propose, as a future work, to improve the prediction schemes in identified non smooth regions (where actual subdivision schemes don't propose good predictions). It can hence reduce the wavelet coefficients, and improve the compression bitrates on natural objects. We can think to account for the anisotropy of the surface causing these high coefficients. Moreover, fractal analysis could also be considered in noisy regions.

Figure 1 .

 1 Figure 1. Main features and stages of our framework which aims at locally encoding a semi-regular mesh Msr (remesh of the original irregular model Mir). This allows a robust and efficient reconstruction Mrec on the client side.

Figure 2 .

 2 Figure 2. Left: Original Normal "Rabbit"; Right: Wavelet coefficients represented as 3D vectors linked to edges of the 1 st resolution level (multiplication factor: 20).

Figure 3 .

 3 Figure 3. Distribution of wavelet coefficient magnitudes on the Normal "Venus". The decomposition was produced with the non lifted Butterfly scheme. (a) Original Normal "Venus" model; (b) Histograms of the normalized coefficient magnitude for all resolution levels; (c) Color scale used for the next figures; (d) Distribution of the normalized coefficient magnitude on 1 st decomposition level; (e) Same distribution but using a Gaussian normalization; (f) Distribution means of all the Gaussian normalized magnitudes grouped on the 1 st level; (g) Histograms of the normalized polar angle for all resolution levels.

Figure 4 .

 4 Figure 4. Classifications and segmentations based on the coefficient magnitude for our two different rules, on Normal "Venus". (a, e) Distribution mean of all Gaussian normalized coefficient magnitudes grouped on the 1 st and last level; (b, f) Two-clustered classification on the 1 st and last level; (c) Classification projection on the coarsest level; (d, g) Resulting segmentation on the finest mesh.

Figure 5 .

 5 Figure 5. Classifications and segmentations based on the coefficient magnitude for our two different rules, on Normal "Horse". (a) Original Normal "Horse" model; (b, f) Distribution mean of all Gaussian normalized coefficient magnitudes grouped on the 1 st and last level; (c, g) Two-clustered classification on the 1 st and last level; (d) Classification projection on the coarsest level; (h) Partitions obtained after the region growing step; (e, i) Final regions projected on the finest mesh.

Figure 6 .

 6 Figure 6. Example of the coarse facet cluster affiliation determination, after two successive coarsifications with our projection rule, used in association with our first aggregation rule. The smooth cluster is represented in dark color.

Figure 7 .

 7 Figure 7. Rate-distortion curves for the studied 3D models remeshed by the Normal Mesh or MAPS algorithms. We considered the global MR analysis (blue curves) and our local extension with its two aggregation rules (green and red curves). The non lifted butterfly wavelets were used everywhere for both global and local cases.

Figure 8 .

 8 Figure 8. Possible reconstructions with our flexible local framework on the "Horse" and "Feline" models. (a, f) Reconstruction obtained from a global wavelet decomposition. (b, g) Two-clustered classifications using the first aggregation rule and projected on the coarsest level; (d) same classification but based on the second rule for the "Horse" model.(c, e) Reconstructions produced with the non lifted Butterfly subdivision, followed by the wavelet addition in the non smooth parts. We have reported the corresponding coding file size in bytes and L 2 error in units of 10 -4 for each considered reconstruction.

Figure 9 .

 9 Figure 9. "Horse" model reconstructions based on local and global considerations, with the same reconstruction error.Left picture remembers the original irregular mesh. The reconstruction presented in the middle, was produced with our local framework where subdivision is only followed by wavelet addition in non-smooth regions. Right reconstruction was obtained from a global wavelet decomposition. We have reported the corresponding coding file size in bytes (B). The distortion errors e1 and e2 correspond respectively to Hausdorff distance (in units of 10 -4 ) and Lavoué et al.[START_REF] Lavou | Perceptually driven 3d distance metrics with application to watermarking[END_REF] MSDM metric.

Figure 10 .

 10 Figure10. Compressed file size comparison for "Horse" model analysed with global method (top) and our adaptive approach (down). For both reconstructions, local distortion computed in "Horse" head is equivalent.

Table 1 .

 1 Characteristics of our two segmentation rules on three usual models remeshed by two different algorithms.'# vtx' = number of vertices and '# face' = number of faces on SR models. '# reg. 1/2' = number of regions obtained with the first/second aggregation rule. '% rough' = rough triangle rate on the underlying classification.

		# vtx	# face	# reg. 1 % rough # reg. 2 % rough
	Venus Normal 163,842 327,680	12	30%	5	38%
	Venus MAPS	198,658 3297,312	16	47%	7	43%
	Horse Normal 112,642 225,280	6	27%	5	36%
	Feline Normal 258,046 516,096	11	33%	9	27%

We also would like to improve the rate/distortion (r/d) results produced by our local wavelet analysis. Following the work done by Payan et al. 26 and Sim et al., 23 we would like to further optimize the wavelet quantization and bit allocation for each produced patch, with respect to its distortion contribution to the entire surface. The principle is to use a Lagrangian optimization in each subband of each region.

Other applications could benefit from our partitioned analysis, like watermarking. It would allow to apply different marks according to the visual aspect of the surface. Another interesting point is that partition coding includes extra information that improves the reliability of data transmission in telecommunication channels. So another possible application would be error-resilient 3D mesh coding.