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

Florent Dupont

Atilla Baskurt

Multiresolution mesh segmentation based on surface roughness and wavelet analysis

Keywords: Mesh segmentation, classification, multi-resolution analysis, geometric wavelet, lifting scheme, region growing, region merging

published or not. The documents may come

Multiresolution mesh segmentation based on surface

roughness and wavelet analysis.

INTRODUCTION

The complexity of the 3D models, used in computer graphics, have recently increased due to the last progress in sampling techniques. These objects are consequently represented numerically with more and more precision and details in order to answer realism waitings. Triangle mesh is the most common representation for these objects because it's a well adapted model for many applications and for the rendering process. This representation include geometry and topology information which could be expensive for computation, storage, transmission, and display tasks, even if the material involved is more and more competitive. Consequently multiresolution (MR) techniques have emerged, in order to represent data with multiple Level Of Detail (LOD) for progressive transmission and visualisation purposes, where a coarse approximation can subsequently be further improved depending on the user resources and waitings. In order to adapt to the heterogeneity of the material involved, MR analysis is employed to produce such LODs thanks to wavelet transform. This latter transform is mainly used by many authors for progressive compression and visualisation, but also for denoising, filtering or surface editing purposes.

The goal of this work is to benefit from MR analysis to produce a series of segmentations for all resolution levels. Segmentation is used in many computer graphics applications, like mesh compression or simplification which can be simplified on surface patches. For texture mapping, it allows a simplification of the parameterization for high genus meshes. Metamorphosis or animation can also benefit from mesh decomposition in order to establish a correspondance between each part of the objects. Most of existing segmentation algorithms are based on the curvature or planarity information to distinguish the relevant parts of the object. They consist in decomposing the original model in regions having the same characteristics in term of curvature. This treatment is easier when dealing with CAO objects which contain sharp edges and corners that separate generally smooth regions.

In this paper we propose a new mesh segmentation algorithm based on roughness information computed locally on the surface. For some kind of objects, like the Venus model presented in Fig. 4, the obtained regions correspond to semantic parts, because people have a tendancy to distinguish parts according to their frequency. Considering that the roughness of the surface is intrinsically linked to multiresolution, our framework will be able to better take into account this kind of measure.

Having a different segmentation for each resolution level, based on roughness information could be interesting for indexation where each one contains various levels of frequencies while keeping the global form of the initial mesh. Watermarking and compression can also benefit from this framework in order to apply different marks or subdivision schemes according to the visual aspect of the surface. Finally, it can increase the adaptiveness for visualisation and navigation in large scenes purposes, where parts of objects or scenes could be more refined than others, taking into account the user's point of view and interest.

In the next paragraph, we review briefly recent papers dealing with multiresolution analysis and segmentation of triangular meshes. In sect. 3, we detail our segmentation approach based on the coefficients produced by a wavelet decomposition. Sect. 4 presents the results we have obtained. We finish by a discussion and ideas for future work.

RELATED WORK

One of our principal objectives is to develop a new adaptive and progressive mesh compression algorithm, aiming at applying various wavelet decompositions and quantizations dependending on the roughness of the surface. Consequently a surface partition is first needed. Within this framework, we have considered the distribution of the wavelet coefficients norm and polar angle, obtained by a global multiresolution (MR) analysis and which reflects the roughness of the surface. Before detailing our algorithm, we present the existing work done in MR analysis of semi-regular meshes and in mesh segmentation.

State of the art in multiresolution analysis of semi-regular meshes

MR analysis of meshes with arbitrary topology was introduced by Lounsbery 1 who have used a canonical subdivision of the facets and a geometric wavelet transform to obtain multiple resolution levels. He showed that a subdivision scheme can serve as a scaling functions basis in order to extend the wavelet theory for irregular sampled signals like meshes. Most of the algorithms dealing with MR analysis apply it to semi-regular meshes obtained by remeshing techniques and favourable with the extension of the MR analysis scheme proposed by Lounsbery. [START_REF] Lounsbery | Multiresolution Analysis for Surfaces of Arbitrary Topological Type[END_REF] In this way, meshes can be considered as functions via the produced parameterization. These papers diverge by the method used to construct a good approximation of the initial surface with subdivision connectivity, which can be done while refining a coarse mesh, obtained directly from the initial object 2, 3 or by progressive decimations. [START_REF] Lee | MAPS: Multiresolution Adaptive Parameterization of Surfaces[END_REF][START_REF] Guskov | Normal Meshes[END_REF] The first remeshing method 2 proposed within this framework use a partition of the original mesh into Voronoï tiles, computed using the geodesic distance. The coarse model is obtained using the dual construction : the Delaunay triangulation. This latter is then refined by subdivision steps and additional displacements to obtain a semi-regular approximation of the original form. The details missed by the subdivision operation are determined at each resolution level thanks to a local parameterization, based on harmonic maps. In the same way, Gioia [START_REF] Gioia | Reducing the number of wavelet coefficients by geometric partitioning[END_REF] have also used a parameterization based on harmonic maps to produce a semi-regular mesh from a coarse one obtained by a partitioning process. The principal difference between these methods is that the latter take more into account the geometric and visual properties of the initial surface during the construction of the parameterization and the coarsest approximation. Gioia experimentally obtain on average twice less wavelet coefficients than with previous method, for natural and CAD objects, considering the fact that we are dealing with geometric shapes and not just functions.

The other concept for building a semi-regular mesh was introduced by Lee et al. [START_REF] Lee | MAPS: Multiresolution Adaptive Parameterization of Surfaces[END_REF] who have constructed the coarse mesh thanks to a decimated process based on local simplifications of the initial model. Vertex removals are used to progressively build a parameterization of the original object in a hierarchy of meshes. At each step, the vertices choosen to be removed are those that withdraw the fewest geometrical and topological information. The parameterization consists in expressing the decimated vertices as barycentric coordinates of the resulting ones. The Loop subdivision 6 is then used to produce the semi-regular mesh from the coarsest one. The details added at each resolution are represented by 3D vectors. Another famous algorithm based on the same concept 5 benefits from other type of parameterization and a non lifted Butterfly subdivision scheme 7 to concentrate the high-frequency information along the surface normal which could be expressed by a scalar.

The application of the MR analysis on the semi-regular 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 [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][START_REF] Payan | Mean square error approximation for wavelet-based semiregular mesh compression[END_REF] benefit from interpolating subdivision schemes for the low-resolution versions to be good approximations of the original object (in a least-squares sense). In other words, 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] have recently proposed a wavelet construction for the Loop subdivision, based on the lifting scheme. Contrary to Khodakovsky filters, [START_REF] Khodakovsky | Progressive Geometry Compression[END_REF] constructed previously, the wavelet analysis and synthesis are obtained in linear time, providing relatively stable schemes.

All of these previously described algorithms apply a global wavelet decomposition, using the same scheme on the entire surface of the mesh. Our objective is to apply different analysis and synthesis schemes for regions that don't exhibit the same roughness degree, in order to obtain better compression results. For that purpose, we first need a mesh decomposition.

State of the art in mesh segmentation

Image segmentation have received considerable attention since last years, because there is a large number of higher-level image processing problems that can benefit from this decomposition as a preprocessing step. In the same way, lots of work have been done in segmentation of 3D data, mainly based on range images or point clouds representations. But more recently, authors have proposed algorithms for mesh segmentation which can be decomposed in two groups, depending whether they are interpreted in a purely geometric sense or in a more semantic-oriented manner. In the latter case, the object is decomposed in parts corresponding to relevant aspects of the surface of the shape (sub-meshes). This principle can be used for applications seeking the meaningful components of the objects as collision detection, skeletonization, metamorphosis, animation or modeling by parts, which are far from our expectations.

Methods that belong to the first category partition the object in surface patches having common characteristics (planarity, constant curvature, ...). Some of them intend to approximate the object by planar faces and to minimize approximation error between this set of elements and the original surface. [START_REF] Garland | Hierarchical face clustering on polygonal surfaces[END_REF][START_REF] Cohen-Steiner | Variational shape approximation[END_REF] These approximation techniques are particularly useful for mesh simplification and radiosity. Other approaches [START_REF] Mangan | Partitioning 3D Surface Meshes Using Watershed Segmentation[END_REF][START_REF] Sun | Triangle Mesh-Based Edge Detection And Its Application To Surface Segmentation And Adaptive Surface Smoothing[END_REF] use the discrete curvature computed in each vertex with a watershed algorithm adapted from those employed in image segmentation. More recently, Razdan et al. [START_REF] Razdan | A hybrid approach to feature segmentation of triangle meshes[END_REF] have proposed a hybrid approach, which combine the watershed algorithm with a sharp edge extraction. But theses methods tend to extract only regions surrounded by high curvatures and don't handle correctly the boundaries between the patches, which are either fuzzy or jagged. The method developped by Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] overcome these drawbacks using a K-Means classification algorithm [START_REF] Gersho | Vector quantization and signal compression[END_REF] instead of the watershed, in order to more precisely detect curvature transitions, particularly on CAD objects.

We propose to adapt this latter algorithm to natural objects using the wavelet coefficients as roughness measure. They represent the high-frequencies lost during the coarsification of the initial model and reflect the roughness of the surface, as less details are needed in smooth regions than in textured or noisy ones.

PROPOSED METHOD

In this section, we first detail the theory involved to produce the wavelet coefficients. We present then the various MR analysis schemes we have compared to obtain the best mesh decomposition. We finally describe our adaptation of the mesh segmentation algorithm introduced by Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF]

Wavelet theory and lifting scheme

The MR analysis produces a reversible decomposition of a mesh into a serie of approximation meshes and a sequence of wavelet coefficients. Classical MR analysis methods such as wavelet transform are based on the filter bank theory where lowpass and highpass filters are applied in order to obtain respectively approximations and details. For a discrete signal s(t), its Wavelet Transform is explained by this formulation :

W T s(t) (m, n) =< ψ m n , s >= a -m 2 0 +∞ -∞ s(t)ψ * (a -m 0 t -nb 0 )dt.
where m, n ∈ Z, a 0 > 1, b 0 > 0 and ψ * corresponds to the complex conjugation of ψ.

The choice of a 0 and b 0 produces different tilings of the time-frequency plane. The most used technique is the dyadic analysis, introduced by Mallat [START_REF] Mallat | A theory for multiresolution signal decomposition: The wavelet representation[END_REF] in 1989 to link the wavelets and the filter bank theories, where a 0 = 2 and b 0 = 1. This MR analysis formulation, defined for finite energy functions, is formally described for a serie of imbricated subspaces (V m ) m∈Z ⊂ L 2 (R) in which an orthonormal basis of scaling functions is determined. This family of functions {ϕ m n ; n ∈ Z} is defined by dilations and translations of a mother scaling function ϕ(t) and expressed by the following formula :

ϕ m n (t) = 2 -m/2 ϕ(2 m t -n).
The orthogonal projection of s(t) into the scaling functions family forms an approximation of the signal, which is interpreted as a lowpass filter followed by a uniform subsampling. To recover the high frequencies losts during the preceding step, we have to consider the W m spaces, which are the orthonormal complements of the V m space in the V m-1 one. The wavelets, defined by ψ m n (t) = 2 -m/2 ψ(2 m t -n), form an orthonormal basis of the W m spaces and are used as highpass filtering in order to collect the missed details. This formulation can be applied to meshes, using subdivision as lowpass filtering, as defined by Lounsbery and shown in Fig. 1. But in practice it's interesting to benefit from wavelets having at least one vanishing moment, especially for compression purposes in order to benefit from a decrease of the wavelet coefficients through the resolution levels. The orthogonality of the wavelets with the scaling functions is also sought to obtain the best approximations in a least square sense which is important for visualisation and to improve coding performances. This orthogonalisation means that < ϕ j i ,ψ j k > = 0 for each pair (i,k) ∈ Z 2 , < f, g > being defined as the inner product between the functions f and g. The inner product on a triangular mesh M , was first defined by Lounsbery and is computed with the following formula :

< f, g >= τ ∈∆(M ) 1 Area(τ ) s∈τ f (s).g(s).ds
where ∆(M) denotes the set of triangular faces of M and ds is the usual Euclidean area form for the triangles τ in R 3 . But it's not always possible to construct analysis tools having such properties from the filter bank theory. Consequently most of the methods benefit from the lifting scheme formulation, introduced by Sweldens [START_REF] Sweldens | The lifting scheme: A custom-design construction of biorthogonal wavelets[END_REF] which moreover reduce computational costs and memory allocation by first splitting the signal into even and odd components using lazy wavelets and represented by S in Fig. 2. The following lifting steps of Fig. 2 produce a modification of this biorthogonal wavelet basis in order to add the desired properties. These operations are equivalent to a factorization of the pair of complex filters which can be simplified by the lifting formulation. Hence, the MR analysis is simply obtained with finite filters by an inversion of the order and signs of the synthesis lifting matrices.

The prediction operator (P ) is used to predict odd components from even ones, in order to obtain smaller coefficients by better approaching the higher level mesh than with a canonical quadrisection. The update operator (U ) is used to preserve the mean value of the signal and corresponds to the addition of the previously cited properties, like orthogonalisation of the scaling functions ϕ with the wavelets ψ. This latter property is applied to minimize the norm of the orthogonal projection of the ψ j i on the V j spaces, ∀i, j ∈ Z, with respect to the inner product. Hence the wavelets are expressed by :

ψ j i = ϕ j+1 i + k∈∇j α ik ϕ j k
with ∇ j defined as the set of vertices of M j .

The coefficients α ik of this latter equation are the solution of a linear system which depends on the desired properties. In practice, the orthogonalisation is relaxed in order to obtain finite filters. For compression purposes, the decomposition ends up with a normalisation step (N ), which is used to adjust the scale between odd and even coefficients so as to decompose the surface in a normalised basis.

Construction of various lifting schemes

In the framework of our segmentation perspective, based on roughness, we have compared different interpolant prediction schemes associated or not with an update step. The following interpolant schemes were choosen because they produce a more stable decomposition than with approximant ones :

• the midpoint scheme which corresponds to a canonical quadrisection of the facets (addition of the new vertices in the middle of each edge) ;

• the Butterfly scheme introduced by Dyn et al., 7 which produces a C 1 limit surface for meshes having a regular topology. Moreover it's the interpolant scheme with the smallest stencil which allows to reduce computational costs ;

• the extension of the Butterfly scheme proposed by Zorin et al. [START_REF] Zorin | Interpolating subdivision for meshes with arbitrary topology[END_REF] who have introduced new masks for extraordinary vertices while preserving the simplicity and the behaviour of the original scheme. The new weights are computed with a discrete Fourier transform and a principal component analysis. Unlike the other interpolant schemes, it produces comparable results than with approximant stencils ;

• a Butterfly extension we have proposed with smaller stencils than those used by Zorin et al. for extraordinary vertices.

We also have compared two formulations of the lifting scheme where the prediction and the update steps can be reversed. For this latter step, we only have employed a 0-ring stencil, taking into account Certain et al. [START_REF] Certain | Interactive multiresolution surface viewing[END_REF] assumptions. They indeed have compared experimentally the performance of the lazy, 0-, 1-and 2-disk wavelets to know how quickly the geometric error decreases as a function of the number of wavelet coefficients or polygons in the model. The experimental results have shown that the lazy wavelets perform slightly worse than the k-disk ones, but there is no significant difference between the various values of k. Moreover, the wavelets with smaller supports are likely to be more stable numerically, which is important as the number of levels increases.

Finally, the MR analysis framework was applied on semi-regular meshes obtained by the two most famous algorithms which define a parameterization on a hierarchy of meshes. The first is called MAPS [START_REF] Lee | MAPS: Multiresolution Adaptive Parameterization of Surfaces[END_REF] and the other produces Normal meshes. [START_REF] Guskov | Normal Meshes[END_REF]

Wavelet decomposition for segmentation purposes

The mesh segmentation in surface patches having a quasi-constant roughness has been computed using an adaptation of the algorithm proposed by Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] (originally conceived for CAD objects). This latter exploits the principal curvature values, computed in each vertex using the estimation of the curvature tensors defined by Cohen-Steiner and Morvan. [START_REF] Cohen-Steiner | Restricted delaunay triangulations and normal cycle[END_REF] More precisely, they first have used a pre-processing step to detect sharp edges, particularly found in optimized triangulated CAD objects, where curvature is theoretically not defined. As we intend to treat natural objects and not specifically CAD ones, we don't have considered this sharp features detection.

Several authors have proposed different algorithms for estimating the curvature tensors, [START_REF] Cohen-Steiner | Restricted delaunay triangulations and normal cycle[END_REF][START_REF] Taubin | Estimating the tensor of curvature of a surface from a polyhedral approximation[END_REF][START_REF] Meyer | Discrete Differential-Geometry Operators for Triangulated 2-Manifolds[END_REF] but the one introduced by Cohen-Steiner and Morvan, [START_REF] Cohen-Steiner | Restricted delaunay triangulations and normal cycle[END_REF] based on the Normal Cycle, has given better results even for CAD objects. Once these tensors have been estimated, their eigenvalues represent the principal curvature values (kmin and kmax) and have been used in Lavoué et al. classification algorithm. In this paper, we propose to replace this curvature information by our previously detailed roughness measure, to obtain a different segmentation for natural objects.

Wavelet coefficients used to reflect surface roughness

The contribution of this work is the use of the wavelet coefficients norm and polar angle (the angle between each coefficient and its corresponding surface normal vector), obtained by the various schemes explained in sect. 3.2, to differentiate mesh regions in term of roughness. We have considered two ranges for the polar angle measure. The first lies between 0 and π/2 and doesn't differentiate vectors with opposite directions from those having the same, unlike the second which lies between 0 and π. We obtain a hierarchy of mesh segmentations having less and less high-frequencies, in which the wavelet coefficients are linked to edges.

The histograms presented at the first row of Fig. 3 show the non-uniform distribution of these measures for all the coefficients linked to the first decomposition level edges and obtained with the midpoint analysis. In order to compare these quantities with two other roughness measures linked to the vertices and to make the adaptation of the Lavoué et al. algorithm possible, we have computed for each vertex the mean of the values associated with its incident edges. The corresponding normalized distributions can be seen at the second row of Fig. 3.

The first roughness measure we have used for comparison was defined by Lavoué et al. [START_REF] Lavoué | Perceptually driven 3D distance metrics with application to watermarking[END_REF] who have considered a local sphere centered in each vertex in which they have computed the standard curvature deviation σ x . They have employed it to measure the visual similarity between 3D meshes. The second algorithm used to reflect roughness compute the normal difference between the model and a smoothed version obtained using a Laplacian smoothing. These quantities are shown for the Venus and rabbit models at the first row of Fig. 4 and5.

Classification algorithm based on roughness

The classification algorithm of Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] is then used to create K groups of vertices that could be userdefined. The vertices are classified according to our roughness values, associated with the Euclidean distance in the roughness space. After several iterations, starting with K randomly determined centroïds, each vertex is then associated to a cluster C i and a roughness value r i . A cluster regularization (merging of small or similar clusters) d-f) Normalized distribution of the mean values computed for each vertex from its incident edges. The wavelet coefficients norm have been increased by a factor in order to stretch the distribution originally concentrated near the origin is finally added. For our purposes, two clusters are sufficient in order to separate only smooth regions from rough ones. Considering more clusters leads to a too detailed classification which produces over-segmentation. The next step consists in constructing quasi-similar roughness connex regions composed of triangles from the two groups of vertices obtained in the roughness space.

Region growing and merging algorithms

We have used the region growing and labeling algorithm of Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] in order to transmit the roughness information from vertices to triangles, starting from seed triangles having their three vertices on the same cluster. This treatment is then followed by a region merging algorithm which mainly aims at reducing the oversegmentation resulting from the growing step. This latter operation consists in constructing a region adjacency graph, where the nodes represent the regions produced by the preceding step and the edges an adjacency relation between two of them. A reduction of the graph is then processed where the smallest edge is eliminated at each iteration, resulting in a merging of the two corresponding parts. The graph reduction stops when the region number reaches a queried number or when the weight of the smallest edge is larger than a given threshold. This reduction is based on the similarity distance D ij which gather curvature similarity, size and common perimeter of the two regions. We are actually working to enrich D ij with a roughness similarity distance in order to obtain better results. The reader can refer to the corresponding paper [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] for a more detailed presentation of these algorithms.

Thanks to this framework, we are now able to apply various subdivision schemes and wavelet coefficients quantizations, each one of them adapted to the surface roughness.

EXPERIMENTAL RESULTS

The results shown have been computed with an application implemented in C++ that uses the Computational Geometry Algorithm Library (CGAL). 28 Our classification and segmentation methods, based on roughness measures, were tested on the semi-regular objects obtained thanks to the two remeshing algorithms considered (provided by Caltech). Examples are given for the most revealing objects in term of roughness : the Venus and the rabbit models. Fig. 4 and 5 present the various steps of our algorithm for these models.

Comparison of wavelet decomposition

The distribution of the wavelet coefficients norm, presented at the second row of Fig. 4 and on the model (e) of Fig. 5 is comparable with those obtained considering the two other roughness measures, detailed in sect. 3.3.1 and visible at the first row of Fig. 4 and5. The wavelet coefficients norm have been increased by a factor to stretch the distribution originally concentrated near the origin (as we can see on the first histogram of Fig. 3), allowing a better classification. We can see that these measures reflect the different aspects of the mesh surface, even for the Venus second decomposition level which has approximately 4 2 times less vertices than the original object.

The study of the obtained results have shown that the inversion of the prediction and update steps does not have a meaningful signification. In the same way, the update operation doesn't modify significantly the results, so we don't have presented it in our figures.

While observing the various distributions of the coefficients norm, presented at the second row of Fig. 4, we can notice that the results obtained with the midpoint and Butterfly analysis on the Normal mesh are comparable. Nevertheless the Butterfly scheme allow a better differentiation between smooth and rough parts. This tendancy to obtain smaller wavelet coefficients in smooth regions with the Butterfly scheme can be explained because a better prediction is used. The distributions obtained on the model remeshed by the MAPS algorithm ((g) and (h) models of Fig. 4) are less significant. The same remarks have been noticed on the rabbit model.

The model (k) of Fig. 4 and (g) of Fig. 5 emphasize that the polar angle measure computed by the Butterfly scheme on the Normal mesh is not significant for our purposes. It can be explained because this latter remeshing algorithm uses a Butterfly subdivision scheme to construct the semi-regular mesh having its high-frequency details concentrated in the surface normal.

Taking into account the direction of the wavelet coefficients relating to their associated surface normal produces a distribution which better detects the high curvatures and differentiate the regions having a close roughness measure than with the other quantities. This observation is totally appropriate for segmenting the rabbit model for which the coefficients norm distribution is not as significant as for the Venus one. Moreover, for these two considered ranges, the distribution appears more significant on the Normal mesh. Consequently, in order to benefit from the best distributions for all of our roughness measures, we have considered the midpoint analysis on the Normal meshes for the following steps of our algorithm.

Finally, the various butterfly schemes, presented in sect. 3.2 have given comparable results for all the considered quantities, hence we have presented the results for the simpler one (classical scheme using the same stencil for regular and extraorinary vertices).

Mesh classification and segmentation results

The classification and segmentation results can't be computed directly on the semi-regular finer model, in order to benefit from the wavelet coefficients norm and polar angle. But it's easy to project the measure obtained on the finer mesh for our adaptive compression purpose. The models (m-p) of Fig. 4 and(i-l) of Fig. 5 illustrate the classification and segmentation steps of our algorithm. As explained previously in sect. 3.3.2, the 2-clusters classification have given the best results for the two models.

On the rabbit model, the classification is more difficult because the mesh have globally a more constant roughness than on Venus model. To obtain a good segmentation we then have mainly based the classification on the polar angle distribution which better differentiate the regions than with the norm measure. Moreover the consideration of the polar angle quantities (in addition to the norm) have produced a better segmentation of the Venus hair. The colors used for separating the connex regions were randomly generated and are not associated with a special value.

We can see that the high frequencies are globally well partitioned, but some of them, appearing in the initial mesh can't be considered. In order to obtain a better segmentation we could use a propagation of the roughness information in the coarser levels. We are actually working on a graph construction which could help us to propagate this information in all the resolution levels.

CONCLUSION AND FUTURE WORK

We have presented a new MR analysis for mesh segmentation in regions having the same surface properties in term of roughness. The main contribution of this work is the use of the lifting scheme to build a hierarchy of segmentations, each one of them keeping the global appearance of the object at different levels of detail. Our framework is able to treat any kind of semi-regular mesh and its originality comes from using the wavelet coefficients to reflect the meshes surface rougness. The next step in this work is to use the resulting hierarchy of segmentations for building a local wavelet analysis which could serve for adaptive compression, visualisation, smoothing, denoising or watermarking.

The presented results show that the wavelet coefficients norm and polar angle are relevant measures to identify the roughness of the surface for the two analysed models. But the results could be improved by considering the variance and the histogram distribution of the various measures in order to better counterbalance them. This latter remark could also serve to automatically process the region merging threshold which remains a user defined parameter.

Finally, the boundaries of the segmented regions we have obtained can be cleaned by using the boundary rectification of Lavoué et al. [START_REF] Lavoué | Curvature tensor based triangle mesh segmentation with boundary rectification[END_REF] But as this algorithm is more adapted for CAD objects, the Katz and Tal 29 fuzzy decomposition, based on the geodesic distance could be adapted to give better results for natural objects.

Figure 1 .

 1 Figure 1. Decomposition of a polyhedral surface.

Figure 2 .

 2 Figure 2. Principle of the lifting scheme for the decomposition of a fine mesh (M k ) into a coarser one (M k-1 ) and details (D k-1 ).

Figure 3 .

 3 Figure 3. Distribution of the wavelet coefficients norm and polar angle for the first resolution level of the Venus model (midpoint analysis). (a-c) Distribution obtained taking into account all the coefficients, linked to the model edges. (d-f) Normalized distribution of the mean values computed for each vertex from its incident edges. The wavelet coefficients norm have been increased by a factor in order to stretch the distribution originally concentrated near the origin

Figure 4 .

 4 Figure 4. (b,c) Distribution of the surface roughness computed with two different algorithms on the 2 nd resolution level of the Venus model ; (d) Color scale used for (b,c) and (e-l) models ; (e-h) Distribution of the logarithm of the wavelet coefficients norm on the 2 nd resolution level, for various prediction schemes, using two different remeshing algorithms (the values have been increased by 5 to stretch the distribution, originally concentrated near the origin) ; (i-l) Distribution of the logarithm of the wavelet coefficients polar angle on the 2 nd resolution level ; (m) Classification of the 2 nd resolution level into two clusters based on the wavelet coefficients norm and polar angle (midpoint analysis on a Normal Mesh) ; (n,p) Resulting 10 connex patches obtained by the region growing and merging algorithms.

Figure 5 .

 5 Figure 5. (b,c) Distribution of the surface roughness computed with two different algorithms on the 1 st resolution level of the rabbit model ; (d) Color scale used for (b,c) and (e-h) models ; (e-h) Distribution of the logarithm of the wavelet coefficients norm and polar angle on the 1 st resolution level (midpoint and butterfly analysis on a Normal Mesh). The norm has been increased by 5 to stretch the distribution, originally concentrated near the origin ; (i) Classification of the 1 st resolution level into two clusters mainly based on the wavelet coefficients polar angle distribution (midpoint analysis on a Normal Mesh) ; (j,l) Resulting 20 connex patches obtained by the region growing and merging algorithms.

ACKNOWLEDGMENTS

This work is supported by France Télécom R&D Rennes within the framework of the CoSurf project.


Loïc Hélouët

surname.name Albert Benveniste

Document based modeling of Web services choreographies using Active XML

Keywords: Web services, composition, Active XML, choreographies

This paper proposes a document based framework for the modeling of web-based choreographies involving a tight combination of workflow and data management. Our starting point is Active XML proposed by S. Abiteboul -AXML documents are XML documents with embedded service calls. We enhance Active XML with a rich notion of interface and we propose an effective technique to decide if provided services and needs of callers (defined as interfaces) are compatible. We also explicitly take distribution into account and allow for the composition of distributed AXML systems.

I. Introduction

E-business and supply chain management involve a combination of widely distributed workflow systems and data/information management. According to [START_REF] Wang | A framework for document-driven workflow systems[END_REF], these systems can be viewed from one of the following perspectives:

• Workflow based perspective, in which process is emphasized. Web services and their orchestrations are now considered an infrastructure of choice for managing business processes and workflow activities over the Web infrastructure [START_REF] Van Der Aalst | Workflow Management: Models, Methods, and Systems[END_REF]. BPEL [START_REF] Andrews | Business Process Execution Language for Web Services[END_REF] has become the industrial standard for specifying orchestrations.

Besides BPEL, the Orc formalism has been proposed to specify orchestrations, by W. Cook and J. Misra at Austin [START_REF] Misra | Computation orchestration[END_REF]. • Information based perspective, which emphasizes the information dimension, viewing processes as operations that are triggered as a result of information changes. Information centric systems typically rely on database oriented technologies.

Today, technologies in use for these two aspects are mostly separated. The WIDE approach [START_REF] Ceri | Wide: A distributed architecture for workflow management[END_REF], [START_REF] Chan | A specification language for the wide workflow model[END_REF] was a first attempt toward tightly combining them. This attempt was further developed in [START_REF] Wang | A framework for document-driven workflow systems[END_REF], where the three dimensions of process, information, and organization, are considered. In response to the same need, the notion of "business artifact" has been proposed at IBM as a framework tightly combining workflow and data management [START_REF] Nigam | Business artifacts: An approach to operational specification[END_REF]. See [START_REF] Hull | Artifact-centric business process models: Brief survey of research results and challenges[END_REF] for a brief survey, and [START_REF] Abiteboul | Modeling and verifying active XML artifacts[END_REF] for a use of business artifacts in the context of Active XML, i.e., closer to our present study.

The above attempts (with the exception of [START_REF] Abiteboul | Modeling and verifying active XML artifacts[END_REF]) do not build on top of the reference for documents manipulation, namely XML [START_REF]The Extensible Markup Language (XML) 1.0[END_REF]. Active XML (AXML) [START_REF] Abiteboul | The active XML project: an overview[END_REF] was proposed by Serge Abiteboul et al. as a high-level specification language tailored for data-intensive, distributed, dynamic Web services. It mainly consists in XML documents with embedded service calls. It allows for lazy evaluation: services can return structured data that contain references to services that have to be called to continue the evaluation of the returned values if needed. AXML offers mechanisms to store and query structured data distributed over entities called peers but does not provide ways to define control flows. AXML was then extended with guarded service calls to capture control flows [START_REF] Abiteboul | Static analysis of active XML systems[END_REF], [START_REF] Abiteboul | Modeling and verifying active XML artifacts[END_REF]. However, distribution in Guarded AXML is only reflected through the localization of a service, and some guards apply to the whole system, without considering distribution of information. On the other hand, distribution and decentralization are central concepts in Service Oriented Architectures, in which software components know each other only through their interfaces. Interfaces must depict precisely the data that will be sent as an input to a service, and the expected valid returns. A component uses a service only if the service interface fulfills its needs.

In this paper we further build on top of Guarded AXML by, first, proposing a notion of interface, and, second, taking distribution into account explicitly. The resulting model is called Distributed Active XML. It offers a notion of composition that allows enriching in a modular way a set of peers owning services with more peers offering more services. Our extensions to the existing framework are illustrated through an existing case study, the Dell supply chain.

The paper is organized as follows. Section II recalls the needed background on AXML. The Dell supply chain example is discussed in section III; this is a challenging case, as it is a choreography that combines workflow and data management; the detailed modeling of the Dell supply chain example can be found in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]. Section IV is the core of this paper, and presents our model of Distributed Active XML; a detailed and fully formal presentation can be found in the extended paper [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]. Issues of decidability and complexity are reported in section V; again, details are found in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]. Section VI concludes this work and draws some perspectives on future work on AXML platforms.

II. Documents, patterns, and queries

In this section we give a sketch of the background material on documents that is used in Active XML. A more precise and formal definition can be found in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]. An AXML description consists in (active) XML documents and services distributed over a set of agents called peers. Information owned by each peer is stored as XML documents. In this framework, documents are unranked and unordered forests F (i.e., sets of trees T ) whose non terminal nodes are labeled with tags and whose leaves are labeled with data or service calls. Documents are hence used to specify records as in usual XML databases but also workflows in the form of "things to do" (todo's for short). Todo's appear in documents as service calls, represented with nodes labeled by !f (where f is the name of a service). Examples of documents are found in Figure 2, top, and in Figure 4. A service call is marked with a "!" to indicate that the service is to be called, with a "?" to indicate that the service is being processed, or has no mark to indicate that the service call has been completed to its end. Documents can be tested using patterns. A pattern is a tree with two types of edges: / to indicate the child relation, and / / to indicate the descendant relation, where "descendant" means any finite iteration of "child". Internal nodes of patterns can be labeled with tags or with the special label ⋆ to refer to an arbitrary tag. Leaves can be labeled with tags, data, service calls, or variables. These patterns are exactly those defined in [START_REF] David | Complexity of data tree patterns over XML documents[END_REF], and without variables, correspond to a fragment of Xpath frequently used in the literature [START_REF] Miklau | Containment and equivalence for a fragment of xpath[END_REF]. An example of pattern is found on Figure 1, diagram on the left. This pattern checks for the presence of an order in a document. Patterns can be given conditions which are constraints relating their variables of the following form: X ∼ Y , where Testing a pattern B on a document F consists in searching for a matching of B into F , i.e., a map µ, from the nodes of B to the nodes of F , respecting child and descendant relations, mapping the root of B to a root of a tree in F , and preserving the labels, with ⋆ interpreted as any label. Matchings are not required to be injective. Pattern B of Figure 1 document, there are three different maps sending pattern B onto the unique tree in F . Intuitively, each mapping corresponds to a recorded Order in the document. A document F satisfies a pattern B, written F |= B iff there exists at least one matching from B to F . Documents can be transformed by means of queries. A query is a pair Q = B → H, where B is called the body and H the head of the query. In a query, the body is a pattern and the head is a forest, where each tree possesses a special node called the constructor node, shown with brackets. Figure 1 shows an example of query. A query operates on a documents F as follows: first, all matchings of pattern body into F are computed. These matchings define the valuations of variables in body. Then, each valuation is used to replace the variables in the subtrees of pattern head rooted at constructor nodes by their valuation, or by a nondeterministically chosen value if the variable does not appear in the body part. If the head pattern contains some constraints, then these valuations must be chosen consistently. The result of the query is then computed by replacing in the head the subtrees rooted at constructors by the subtrees computed from the mappings.

∼ ∈ {=, =, ≤}. Q = ⋆ Order name X Object Y Price Z -→ users {client} X Sold {Product} Y B offer
The result of applying query Q of Figure 1 to document F of Figure 2, top, is shown on of Figure 2, bottom. Note that variable B offer is chosen nondeterministically in {yes, no}. Choosing nondeterministic values for variables was not originally proposed in [START_REF] Abiteboul | Static analysis of active XML systems[END_REF] (though it could be emulated by some additional service), but seems an interesting way to allow for uncontrolled choices in modeled systems. In particular, non-determinism allows for the description of open systems (the environment can then be modeled as non-deterministic services) and also allows for underspecification of some parts of an AXML system.

At this point we did not model service calls, that were just introduced as distinguished labels. We will provide a semantics of calls and develop our model of Distributed Active XML (DAXML) in the following sections.

III. Motivation

In this section we motivate our approach with an interesting example, the Dell supply chain. This case study combines aspects of Web stored data management -the Dell Web portal -and complex distributed supplier chain involving logistics. Data are important and structured, both in the Dell catalog and in the processing of the supplier chain. The underlying workflow is rich and is a choreography [START_REF] Misra | Computation orchestration[END_REF] since there is no central orchestrator. Our study relies on the well documented description [START_REF] Kapuscinski | Inventory Decisions in Dell's Supply Chain[END_REF].

A. The Dell supply chain example

This example works as follows. After a customer places an order, either by phone or through the Internet on www.dell.com, Dell processes the order through financial evaluation (credit checking) and configuration evaluation (checking the feasibility of a specific technical configuration), which takes two to three days, after which it sends the order to one of its manufacturing plants in Austin, Texas. These plants can build, test, and package the product in about eight hours. The general rule for production is first in, first out, and Dell typically plans to ship all orders no later than five days after receipt. In most cases, Dell has significantly less time to respond to customers than it takes to transport components from its suppliers to its assembly plants. To compensate for long lead times and buffer against demand variability, Dell requires its suppliers to keep inventory on hand in the Austin revolvers (for "revolving" inventory). Revolvers are small warehouses located within a few miles of Dell's assembly plants. Each revolver is shared by several suppliers. Inventory in revolvers is owned and managed by suppliers and charged to Dell indirectly through component pricing.

To help suppliers make good management decisions, Dell shares its forecasts with them once per month.

The overall architecture of the Dell supply chain is shown on Figure 3. Boxes denote peers (actors of the system), and multiple boxes indicate that there exist several instances of the considered peer. The customer and adjacent arrows are not within the scope of our model, so we will only provide the expectations of the customer in the form of an interface. As the "Dell supervisor" involves monitoring (a topic in itself) and a lot of algorithmic inventory management, we leave aside this part of the application. The Dell supply chain involves several services, which are summarized in Table I. Observe that the last three services need access to the revolver.

B. Services, calls & distribution

Service specification uses the tree pattern matching mechanism defined in section II to define guards, and queries (in the spirit of Xquery [START_REF] Consortium | Xquery 1.0: An XML query language[END_REF]) to create new documents out of existing ones. Services decompose into a call -submitting a query -and a return -receiving a response and inserting it in the due place in the document. Both call and return are specified using guarded queries over documents. A call to a service usually proceeds as follows. When the service is owned by the peer calling it, the call consists in applying a query to the peer's document. The result of this query is defined to create a temporary working space (called the workspace of the service call) used to process the call (which can take several steps of computation if the workspace still contains todo's). A service call returns when one of its return queries is applicable to the workspace, i.e. when one of the guards of its return queries becomes true. The result of the considered query is then computed and inserted in the caller's document close to the node at which the service was requested.

When a peer calls a service owned by another peer, it places a new occurrence of service call in the distant peer's document, together with some parameters collected on its own document. When this distant service is completed, the distant peer sends back the result of his computation to the calling peer. Services calls and returns are executed in any order when their guards are true. The firing policy is local to each peer, which can be either eager (try to replace all service nodes tagged by some !f ), lazy (perform service call only when needed), localized (focus first on the services of some tree/subtree), etc. So far, we hide all the details of this machinery, which will be made clear during the specification of (part of) the Dell example. A more formal presentation of our model is also provided in subsequent sections and in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]. The Dell supply chain decomposes into several peers, namely the Customer, the W ebstore, the P lant, the Revolvers, the Suppliers, the Bank, and the Supervisor. An example of document owned by peer Webstore is given in Figure 4. It contains one order that has been posted to the WebStore, represented by a subtree with root Order, that contains a call node with !DellOrder Service Description DellOrder Returns a computer to a customer in conformance with the order form GiveOrderId Gives a new identifier to a computer order form CheckCredit Checks whether a customer has sufficient credit; performed by the bank RejectOrder Rejects an order if customer has insufficient credit on his bank account or order incorrect ProcessOrder Collects and assemble items, and delivers the assembled computer GetItem Gets a given item from the revolver DecrementInventory Removes one item from the revolver RefuelInventory Adds a certain number of items to the revolver tag. The parameters of the command appear as siblings of the call node. The document also contains a catalog, that lists types of computers together with their price.

We assume that peers are distinct computation units or actors in the system, and do not have direct access to the documents or internal machinery of other peers. Hence a peer sees another peer through the services it provides, i.e. via interfaces depicting the relations between inputs to a service during call, and the expected results that may be returned. More precisely, an interface consists of a pattern depicting the allowed parameters of a call, a list of patterns depicting the shape of returned documents, and a constraint over the variables of these patterns.

Let us illustrate interfaces with an example. In the dell supply chain, customers see service DellOrder provided by the Webstore only through an interface I DellOrder . This interface is shown on Figure 6. It consists of two patterns and an assertion. Call pattern I C specifies that the customer should submit a product reference, a catalog price, and his credit card information to the Webstore. In turn, the customer expects the delivery of the ordered product, as specified by the return pattern I R . Together with an additional assertion [X ′ C = X C ], this interface specifies that, when calling DellOrder service, the customer should receive the computer she ordered.

Let us detail how the Webstore implements the DellOrder interface in Figure 7. The call guard for the corresponding DellOrder service is simply true, which means that a call to service DellOrder can be processed by the Webstore as soon as a node tagged by !DellOrder exists in the document. The call query Q C of the DellOrder service copies all the needed parameters and creates instances of service calls (GiveOrderId, CheckCredit, RejectOrder, ProcessOrder) that have to be completed to process the order. Note that this also requires that the order has been correctly filled, and that the ordered reference appears in the catalog. When this is not the case, the order will not be processed.

The returned value depends on whether the order was accepted or rejected. Here, the implementation of the DellOrder service consists of a set of two guarded return

queries, namely (G 1 , Q R 1 ) and (G 2 , Q R 2 )
. Query Q R 1 returns a delivery certificate, but can only be executed when the order has been processed in due form, which is described by guard G 1 . Query Q R 2 returns a rejected order when guard G 2 holds, that is when the order was tagged as rejected by service RejectOrder due to, either a negative answer from the bank, or an incorrect filling of the order form. Observe that the service specified in Figure 7 is not a correct implementation of the interface specified in Figure 6. The main reason is that the customer was too optimistic in not considering possible rejection of her payment by the bank. The interface of Figure 6 should in fact be corrected accordingly, i.e include a pattern for the rejection case -this is not done here to save space.

Further specifying the services GiveOrderId, CheckCredit, RejectOrder, and ProcessOrder, would complete the description of the DellOrder service by the Webstore. Among these, the first three are internal services held by the Webstore, whereas ProcessOrder is a service held by the Plant, a different peer. Hence, the latter should be specified as an interface when seen from the Webstore, with corresponding implementation by the Plant -this mimics what we did in figures 6 and 7.

The implementation of ProcessOrder is shown in part on Figure 5. The call query of this service creates as many instances of service GetItem as there are parts (we show only one); each instance is given a unique identifier X Ident . Service GetItem is owned by the plant. The return guard G R requires that each item has been properly obtained by the Plant (this process is not described in this shortened version of the case study). The return query of ProcessOrder is then simply Q R = true → processed , thus enabling the guard G R 1 of DellOrder, see Figure 7. The following reasoning can be performed on the Del-lOrder system. It is easily seen that the service performs as specified, provided that the order is not rejected. Rejection can occur either because the order was not properly filled, or because the bank did not approve the transaction. Now, satisfying the guard G R of ProcessOrder is in the hands of the peers supplier : they are responsible for maintaining the stock at appropriate level. This is a separate issue that can be checked based on the following information: 1/ what is the query rate for each item by the plant, 2/ how frequently suppliers check stock level at the revolvers, and, 3/ what is the critical stock level, for each item, that will cause the supplier to refuel this stock. This is a more difficult property for checking, but it is now local to the peers Revolvers and Suppliers, and does not need a system wide analysis.

Q C = a DellOrder Computer Name XC self -→ {Computer} Name XC item !IGetItem X Ident G R = a AssembleOrder Computer GetItem got it

C. Discussion

Based on the case study, several remarks can be stated: a) Documents and workflow must be handled on an equal basis: the supplier chain involves a complex workflow that is a combination of several orchestrations: the Webstore orchestrates the progressive transformation of the order into a computer for delivery; then, each supplier maintains independently the stock level at the revolver. On the other hand, checking that the order form is properly filled and conforms information from the catalog is a data issue. However, data and workflow tightly interact through guards, which involve pattern matching on documents, and through service calls and returns, which modify documents. b) Services are specified in a declarative way: this is done by specifying guarded call and return queries over XML documents. We use tree patterns and queries to state when a service can be invoked, what parameters must be given when calling it, when it is ready to complete, and what it can return. Hence, the control flow of a service execution is not explicitly given. Interfaces are defined in a similar way, and thus can be compared with the function that a service offers. We will show that this offers opportunities for efficient analysis, by replacing a distant service by an interface for it. c) A service can involve recursively other services for its completion: the DellOrder service of Figure 7 is a typical example. Calling it adds the result of the call query to the documents owned by the Webstore as a temporary workspace. This additional document contains fresh instances of GiveOrderId, CheckCredit, etc., which must be evaluated. Computing an answer to a call may involve several recursive calls to other sub-services. With an ad hoc use of guards, a high-level service can then play the role of an orchestration of sub-services.

IV. Distributed Active XML

A. Services as Functions

Services are owned by peers. They are captured by the notion of "function", whereas external services as seen by another peer are modeled by "interfaces". Definition 1: A function is divided into call and a return part. The call part consists in a guarded query (G C , Q C ) and the return part in a set of a guarded queries (G R i , Q R i ) i∈1..n . Guarded queries are simply pairs consisting of a guard (a pattern) and a query. The query can be applied to a document only if the associated guard holds on the considered document.

Let us consider a function DellOrder, with call query (true, Q C ) and return queries

(G R 1 , Q R 1 )(G R 2 , Q R 2 ) , where Q C , G R 1 , G R 2 , Q R 1 , Q R 2 are
the guards and queries of Figure 7. As the call guard of DellOrder is true, this service can be evaluated as soon as a document contains a !DellOrder node. Consider for example the initial document of Figure 4, call it F . The DellOrder service can be called by peer Webstore. The call query applies to the document owned by the WebStore.

Applying DellOrder to F with its description in Figure 7 proceeds as follows. First, the body of the call query Q C is applied to F while node labeled self in the body is mapped to node labeled !DellOrder in F . Valuations for the variables result, namely X N =Smith, and so on. The selected values are then assigned to the corresponding variables in the head of call query Q C , and the resulting document is put in a workspace WS pointing to node ?DellOrder of document F ; note the shift from mark ! to ? for DellOrder, indicating evaluation in progress. Initial document F is augmented with WS . Usually, workspaces are trees with root labeled by distinct tags of the form a f for each service name f . This allows in particular specifying that a query applies to a workspace, or checking that a service is under evaluation on a peer. As a consequence of the DellOrder call, new service calls appear for evaluation by the different peers that own each new service, thus further modifying the status of the document.

If, as a result, return guard G R 1 holds in the workspace, then return query Q R 1 can be applied. The result Q R 1 (W S), that is a forest containing the reference of the order, the actual reference of the assembled computer, and a node with tag delivered is appended as a sibling to the calling node, and the workspace WS is deleted. If, however, return guard G R 2 holds in the document, then return query Q R 2 can be applied to the workspace, which appends a forest containing the reference of the order, and a node with tag rejected, and deletes the workspace. In both cases, the calling node with tag ?DellOrder is relabeled with Dellorder, indicating that the call is completed. The move from a document F 0 to another document F 1 as the result of a call to and a return from service f are written F 0 ⊢ f,call func F 1 and F 0 ⊢ f,ret func F 1 , respectively, and we simply write F 0 ⊢ f func F 1 to refer to any of the above two cases.

!GiveOrderId !CheckCredit !RejectOrder !ProcessOrder G R 1 = a DellOrder processed , Q R 1 = a DellOrder OrderId Y ActualComputer Name X ′ C Price X processed -→ {OrderId} Y {ActualComputer} Name X ′ C Price X delivered G R 2 = a DellOrder rejected , Q R 2 = a DellOrder OrderId Y rejected -→ {OrderId} Y rejected

B. External services as interfaces

We aim at distributing active XML, and to this extend, distant services should be perceived only through the functionalities they provide. This notion is captured by interfaces. Figure 6 depicts an interface for the DellOrder service. This interface can be seen by the customer, who can thus say something about 1/ what parameters she must submit to the service call, and 2/ what are the possible returns of the service. Definition 2: An interface is a pair (I C , {I R i } i∈1..n ) consisting of a call and a set of return patterns, possibly enhanced with constraints over variables of I C and I R i , i ∈ 1..n. Interfaces can be seen as descriptions of distant services. When such services are not explicitly provided, it seems interesting to study the evolution of a system under any implementation. This is captured as follows. Document F 0 can move to document F 1 under interface

I = (I C , {I R i } i∈1..n ), written F 0 ⊢ I intf F 1 , if 1/ F 0 satisfies I C ,
and 2/ the increment F 1 \F 0 satisfies some I R i , i ∈ 1..n. In the following, we will also use interfaces to depict the functional needs of some peer, and relate local needs to a distant implementation (an access to a local function provided by another peer). However, we need to ensure that a service provides a correct implementation before connecting an interface and a function. This is formalized under the notion of implementation: Definition 3: A function f implements an interface I, written f ||= I iff 1/ for every document F in which I C holds, there is a matching from the body of the call query Q C f of f to F , and 2/ every document returned by f satisfies at least one return pattern I R i . Assertions of I must be satisfied as well, if any.

Intuitively, condition 1/ means that when parameters of a call satisfy the call pattern of an interface, then they will be correct inputs to a service, and condition 2/ means that all returned values are compatible with the expected results specified in the interface. The function in Figure 7 is not an implementation of the interface in Figure 6, as the rejection case is not considered by the interface. Observe that interfaces involve no guard, and that relation f ||= I does not involve the call guard of f ; the reason for this is that guards must be tested at the peer owning the service.

Relation ||= is formally defined in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF], where it is shown that it can be brought back to two instances of a query containment [START_REF] Schwentick | Xpath query containment[END_REF], [START_REF] Miklau | Containment and equivalence for a fragment of xpath[END_REF], plus an instance of pattern matching problem. Implementation relation ||= is shown to be decidable and of complexity Co-Nexp-Time under some assumptions on the domains of variables and on the type of constraint used in the interface.

C. The Distributed Active XML model

An Active XML system S, as described in [START_REF] Abiteboul | Static analysis of active XML systems[END_REF] consists of a set P of peers, a set Φ int of functions -the internal services -and a set Φ ext of interfaces -the external services -both located on one of the peers. For each initial document F 0 , S gives raise to a set of possible runs, which are the possible sequences F 0 ⊢ F 1 ⊢ . . . of documents obtained by performing moves under calls to internal and external services contained in F 0 , and to the new service calls that result, inductively.

AXML systems do not consider the effect of distribution, and external services are just underspecified (via interfaces in our definition, and via DTDs in the original AXML model). In particular we have to describe the effect of a call to a distant service that implements an interface. We first enhance our previous notion of AXML system to take distribution and implementation into account, and then consider the semantics of DAXML.

Definition 4: A Distributed AXML system (DAXML system) S = (P; Φ int , Φ ext ; L; γ) is a tuple comprising:

• a set P of peers,

• two disjoint sets Φ int and Φ ext of functions and interfaces, • a location map L : Φ int ∪ Φ ext → P, and • an implementation map γ : Φ ext → Φ int which is a partial function such that γ(I) ||= I for each interface I ∈ Φ ext . It is required that L(γ(I)) = L(I), reflecting that service interfaces are used by distant peers other than the one owning the service.

DAXML systems compose as follows: S 1 ξ S 2 is given by: P

= P 1 ∪ P 2 , Φ int = Φ 1 int ∪ Φ 2 int , L = L 1 ∪ L 2 , Φ ext = Φ 1 ext ∪ Φ 2 ext
, and γ = γ 1 ∪ γ 2 ∪ ξ, where the pairing map

ξ : Φ 1 ext ∪ Φ 2 ext \ D(γ 1 ) ∪ D(γ 2 ) → Φ 1 int ∪ Φ 2 int
assigns interfaces of one system to functions of the other system implementing them. The parallel composition is only defined if L 1 and L 2 agree on the common part of their respective domains, and similarly for γ 1 and γ 2 . Distributed documents: Documents are distributed over peers: a document is thus a forest F , and there exists a map ℓ such that ℓ(F ) ∈ P localizes each tree F of forest F on a peer. Distribution of documents is an important issue, as a peer should not have direct access to data or services owned by another peer. In the original AXML model, services are called and guards are evaluated over a global document, regardless of who owns the data. We propose an interpretation of distribution that allows access to remote data and services only via distant service calls. Distributed AXML documents located on a peer p contain references to services provided by p (nodes with labels of the form !f with f ∈ L -1 (p)∩Φ int ) and references to interfaces (nodes with labels of the form !I with I ∈ L -1 (p) ∩ Φ ext ). Each peer knows exactly which service on which distant peer implements its external functions.

The first easy cases are local service and interface moves. A local call to a service or interface owned by a peer p only modifies the part of the distributed document owned by p. Let us call this part of the distributed document F p . Then, there is a local move F ⊢ F ′ from document F to document F ′ iff there is a move from F p to some F ′ p as defined in sections IV-A and IV-B, and the rest of the document located on other peers does not change (i.e. F \F p = F ′ \F ′ p ). We only allow local interface moves for interfaces that are not implemented.

The remaining case is then distant service calls. An external call to an implemented interface I = (I C , {I R i } i∈1..n ) can be performed if a peer p owns a node labeled by !I. Calling I consists in replacing label !I by ?I in F p , and appending to the peer that implements I (say with a service g) a new tree with root a I , that contains a node labeled !g and the smallest set of subtrees of F p where I C holds. This can be considered as sending to a peer a request to execute g with some parameters, and creating a distant workspace. Note that this move is only allowed for implemented interfaces.

A return from a an external service call can be performed only when the distant service has been completed, that is the previously created distant workspace contains a node labeled g, with no ! or ? mark. The computed result is deleted from the callee's document, and appended as a sibling of the external calling node in the caller's document. The label of the calling node is then set to I.

We will not give more details on the semantics of DAXML, and refer to [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF] for a complete operational description. In the rest of the paper, we will simply write F ⊢ F ′ and say that there is a move from F to F ′ when F ′ is a distributed document obtained after executing some operation (internal/external call or return) from F . We say that F is deadlocked if there exists no F ′ such that F ⊢ F ′ . A run of a system S from a distributed document F 0 is an infinite sequence ρ = F 0 , . . . , F n , .. of instances over S, such that for every i, either F i ⊢ F i+1 or F i is deadlocked and F i = F i+1 . We denote by Runs(F 0 , S) the runs of S starting at F 0 .

Locality in DAXML: Let S be a DAXML system and R ⊂ P be a subset of its set of peers. One can restrict S to R, written S |R , by simply restricting the set of functions and interfaces to those located on R, and restricting the location map accordingly.

Similarly, for F a distributed document for S, we can restrict F to its subset of trees located on R, written F |R . Then, a run ρ = F 0 , F 1 , . . . of S can be projected over R, written Π R (ρ), by 1/ considering the sequence of restrictions F 0|R , F 1|R , . . . , and, 2/ only keeping, in the so restricted run, changes that are local to R. For R a singleton {q}, Π q (ρ) records what can be seen from peer q in run ρ. Local runs satisfy the following property for every system S and distributed document F 0 [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]: Π R (Runs(F 0 , S)) ⊆ Runs(F 0|R , S |R ) which expresses that the local view, by a subset of peers, of any run of the overall system, conforms with the set of runs specified by replacing distant calls by their interfaces. This property is important, as it allows to check locally for safety properties such as the absence of a bad pattern in any run of an AXML system.

V. Issues of decidability and complexity

Issues of decidability and complexity impacted our design choices in the following aspects of our model: how interfaces should be defined, and what kind of property can be checked on a DAXML system. We begin with the notion of interface and study the implementation relation.

A. Complexity of the implementation relation

The first question is that of the complexity of pattern matching F |= P . Obviously, testing if T |= P is an NPcomplete problem as soon as variables are used (which allows encoding a SAT problem). We can reduce complexity of pattern matching, and then, of implementation, by stating assumptions regarding variables or the shape of patterns. The child-only assumption holds when a pattern does not use descendant edges. The finite-domain assumption holds when variables range over finite domains.

The following result is proved in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF]: let I be an interface and f be a function which variables range over finite domains, and such that additional constraints do not involve at the same time variables of I C and {I R i } i∈1..n (that is we forbid expressions of the form X < Y , (X = α) =⇒ (Y = β), etc. when X is a variable of I C and Y a variable of I R i for some i ∈ 1..n). Then, deciding whether f ||= I is a Co-NexpTime problem. However, without the finite domain assumption, or with generic constraints on variables, f ||= I becomes an undecidable problem.

Observe that our implementation relation (definition 3) is not tractable with assertions such as the side conditions of functions and interfaces in the examples of figures 6 and 7. The reason is that considering them would immediately lead to undecidability of the implementation relationthis fact is explained in the next paragraph. However, it is still possible to leave the assertions aside when verifying implementation, and to handle them separately (for instance at runtime).

B. Reachability and Tree-LTL logic

It is shown in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF] that it is undecidable whether a pattern P is reachable by some run of a DAXML system S starting from a given initial document F 0 . This undecidability result is not related to distribution; it holds already with a single peer and internal services only [START_REF] Abiteboul | Static analysis of active XML systems[END_REF]. It can be avoided if negative patterns are forbidden in guards (they are considered in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF], but we did not allow them for simplicity) and if unbounded recursive calls between functions are forbidden too.

A consequence is that some restrictions on assertions are also needed to keep implementation decidable. Consider for instance the assertion [X ′ C = X C ] in figures 6 and 7. Ensuring it is a reachability problem as it amounts to requiring that X ′ C can reach a prescribed value in some run. This is undecidable unless stringent assumptions are made, as we have seen. Hence, allowing any type of assertion in the implementation relation leads to undecidability.

More complex properties on the runs of DAXML systems can be formulated using formulas from the logic Tree-LTL [START_REF] Abiteboul | Static analysis of active XML systems[END_REF], defined by the following grammar:

φ ::= Qpattern | φ ∧ φ | ¬φ | φ U φ | φ,
where Qpattern is a Qpattern, i.e., a pattern P in which some variables are declared free and universally quantified over the formula, and ∧, ¬, U , have the usual meaning of LTL. It is shown in [START_REF] Hélouët | Distributed active XML and service interfaces[END_REF] that our new notions of interface and DAXML system keep complexity and decidability issues unchanged as compared to the original results of [START_REF] Abiteboul | Static analysis of active XML systems[END_REF] concerning guarded AXML: distribution comes for free.

VI. Conclusion and perspectives

This paper has introduced an XML based distributed framework for services choreographies, thus supporting information and workflow management in a unified framework. We have defined a rich notion of service interface for this framework. Distant calls via interfaces ensure interoperability between agents of a system, but also encapsulation of data and services in peers. Interfaces are useful to analyse partially specified designs where some implementations are only known via their interfaces. We see this as a promising research direction.

Our model relies on a querying mechanism that uses tree patterns (a fragment of Xpath). However, AXML can easily be adapted to other query mechanisms (possibly with different decidability issues). Finally, let us mention that an experimental AXML platform has been developed by the Active XML community (www.activexml.net). This implementation relies on standards for web services and is then open to all systems implementing these standards.

Figure 1 .

 1 Figure 1. An example of nondeterministic query Q = B → H; B is a pattern and H is a forest.

  can be successfully tested on document F of Figure2, top. For the considered

Figure 2 .

 2 Figure 2. A sample document F (top) and a result of query Q(F ) (bottom), for Q as in Figure 1.

Figure 3 .

 3 Figure 3. Architecture of the example.

Figure 4 .

 4 Figure 4. Initial document.

Figure 5 .

 5 Figure 5. ProcessOrder as implemented by the plant.

Figure 6 .

 6 Figure 6. I DellOrder , external view from customer as an interface, with its assertion ˆX′ C = X C ˜.

Figure 7 .

 7 Figure 7. DellOrder, implementation by Webstore.

Acknowledgment: We are indebted to Serge Abiteboul, Victor Vianu, and Luc Segoufin, for fruitful discussions on this work.

This work was partially funded by the ANR national research program DOTS (ANR-06-SETI-003), DocFlow (ANR-06-MDCA-005) and the project CREATE ActivDoc.


Philippe Halfon
email: philippe.halfon@alphabio.fr

Sophie Pérusat

Marc Bourlière

Jean-Pierre Bronowicki

Pascale ; Trimoulet

Yves Behnamou

Vincent Leroy

Patrick Marcellin

Juliette Foucher

Guillaume Pénaranda

Victor Ségalen

Virologie Ea2968 Behnamou

Yves Leroy

Vincent Marcellin

Hepatology Foucher

Yves Benhamou

Guillaume Penaranda

Geneviève Chêne

Patrice Couzigou

Philippe Pr

MD Halfon

Neutralizing antibodies to interferon alpha and circulating interferon in patients with chronic hepatitis C non-responding to pegylated interferon plus ribavirin retreated by pegylated interferon alpha-2a and ribavirin (ANRS HC16 GAMMATRI substudy*

Keywords: second line treatment, neutralizing antibody, hepatitic C, nonresponders pegylated, IFN: interferon, RIBA, ribavirin, Second line treatment, Neutralizing antibody, Hepatitis C virus, Nonresponders

come

Neutralizing antibodies to interferon alpha and circulating Interferon in chronic hepatitis C patients non-responding to pegylated interferon plus ribavirin re-treated by Peg-Interferon alpha-2a and ribavirin (ANRS HC16 GAMMATRI substudy*)

INTRODUCTION 1

Chronic hepatitis C is a major cause of liver disease, with worldwide prevalence 2 estimated at 3% [WHO., 2000]. Only a minority of those infected spontaneously clear 3 HCV. Of patients who become chronic carriers, 70-80% may progress to cirrhosis and 4 hepatocellular carcinoma [START_REF] Hoofnagle | Course and outcome of hepatitis C[END_REF][START_REF] Micallef | Spontaneous viral clearance following acute hepatitis C infection: a systematic review of longitudinal studies[END_REF]Thomas and Seeff, 5 2005]. 6

Response to interferon (IFN) α-2a  and ribavirin (RIBA) combination therapy for the 7 treatment of chronic hepatitis C viral (HCV) infection varies largely among patients. 8

Indeed, with a combination of pegylated (PEG) IFN α-2a or α -2b plus RIBA for 24 or 48 9 weeks depending on genotype, currently the standard of care for patients with chronic 10 hepatitis C, up to 50-60% of patients are non-responders or experience relapse after 11 treatment ends [START_REF] Seeff | Natural history of chronic hepatitis C[END_REF]. Many hypotheses have been proposed to explain the 12 absence of response to IFN. Recent data suggest that host genetics may be useful for 13 predicting drug response, and they also support the notion that IL28B could play a role 14 in the treatment of HCV and in other diseases treated with IFN [START_REF] Ge | Genetic variation in IL28B predicts hepatitis C treatment-induced viral clearance[END_REF]15 McCarthy et al.;[START_REF] Rauch | Genetic Variation in IL28B Is Associated With Chronic Hepatitis C and Treatment Failure: A Genome-wide Association Study[END_REF][START_REF] Suppiah | IL28B is associated with response to chronic hepatitis C interferonalpha and ribavirin therapy[END_REF][START_REF] Thomas | Genetic variation in IL28B and spontaneous clearance of hepatitis C virus[END_REF]. 16 A possible explanation for the lack of response is the development of neutralizing 17 antibody to interferon, as shown in case series [START_REF] Van Der Eijk | Antibodies neutralizing peginterferon alfa during retreatment of hepatitis C[END_REF]]. There have not 18 been reports so far on large unselected series of re-treated patients to study formally the 19 association between neutralizing antibody and the response to treatment. 20

In the setting of a clinical trial, relationships were assessed between either IFN 21 (endogenous or not) or neutralizing antibody to IFN α-2a levels and virological response 22 to a second-line treatment with PEG IFN α-2a + RIBA. 23 24 25

PATIENTS AND METHODS 26

Patients: In a phase II, multicentric, non-comparative trial (ANRS HC16 GAMMATRI), 27 patients received PEG IFN α-2a (180µg/week) in combination with RIBA (1000 mg/d if 28 <75 kg, 1200 mg otherwise) for 48 weeks. IFN gamma-1b was added to this 29 combination if patients did not experience a virological response at the 12-week visit, 30 defined as a decrease in HCV RNA greater than 2 log 10 copies/ml relative to the 31 For this study, the definition of treatment response was a decrease in HCV RNA greater 40 than 2 log 10 copies/ml at week 12 relative to baseline values. Another criterion of 41 treatment response was undetectable HCV RNA at week 12 or 28. 42

Measurements: HCV RNA was measured at week 12 using TaqMan PCR (Roche 43 Diagnostics) (lower limit of detection 15 UI/ml) in a central laboratory to assess early 44 response. IFN levels and neutralizing antibody to IFN α-2a were retrospectively 45 measured on stored sera at baseline and weeks 4 and 12. Measurements were 46 performed by technicians who were blinded to the individual response to treatment. 47

Neutralizing antibodies to IFN α-2a were determined using a quantitative sandwich 48 enzyme-linked immunosorbent assay (ELISA) for antibodies directed to IFN α-2a 49 (Bender Med-Systems Diagnostic) with a limit of detection at 1.38 ng/ml. IFN α-2a 50 levels were measured using a quantitative sandwich enzyme-linked immunosorbent 51 assay (ELISA) for IFN α-2a (Bender Med-Systems Diagnostic) with a limit of detection 52 at 3.3 pg/ml. For the computation of statistical parameters, undetectable values were 53 assigned a value of zero. 54 antibody to IFN α-2a could be measured in all the patients, except for one responder 63 who had no stored serum available and was excluded from the analysis. Non-64 responders and responders to the initial phase of the second-line treatment did not differ 65 statistically: baseline age (median age 47 vs. 50 years), HCV RNA (median 6.8 vs. 6.4 66 log10 copies/ml), gender (70% vs. 73% males), genotype (genotype 1: 91% vs. 80%). 67

The median IFN α-2a levels (pg/ml) at weeks 0, 4, and 12 (interquartile range) did not 68 (37%) vs. 6/23 non-responders (26%) at week 12 (p=0.73) (Table 1). Of note in one 76 responder, neutralizing antibody to IFN α-2a was present at week 0 and week 4 but not 77 at week 12. 78 Among 5 of the 6 non-responders with neutralizing antibody to IFN α-2a, neutralizing 79 antibody levels were detectable from week 0 to week 12, and for one of the non-80 responders they were detectable at week 4 and week 12. All responders and non-81 responders who had neutralizing antibody to IFN α-2a had undetectable endogenous 82 IFN at week 0. There was no association between the presence of neutralizing antibody 83 to IFN α-2a and endogenous IFN; only one patient who had endogenous IFN at baseline 84 had neutralizing antibody to IFN α-2a. In addition, there was no significant association 85 between the presence of endogenous IFN α-2a at baseline without any exogenous IFN 86 α-2a and response to treatment (p=0.057). 87 At week 28, nine patients had undetectable HCV RNA: three of the patients had 88 neutralizing antibody to IFN-α at week 12 and one had neutralizing antibody to IFN α-2a 89 at week 0 and week 4. In three responders who had undetectable HCV RNA at week 28, 90 endogenous IFN α-2a was found at the baseline but no exogenous IFN α-2a, but these 91 three patients were not the same as the three patients with neutralizing antibody to IFN 92 α-2a. 93 The present study, which is the largest study examining unselected re-treated patients, 95 showed no association between the response to a 12-week PEG IFN α-2a + RIBA 96 session and neutralizing antibody to IFN α-2a. It was reported previously that if there is 97 an association of the presence of neutralizing antibody to IFN α-2a and the absence of 98 response to IFN α-2a, virological response may be restored or induced in hepatitis C-99 infected patients (patients who might develop an antibody-mediated resistance to 100 conventional recombinant IFN treatment) [START_REF] Van Der Eijk | Antibodies neutralizing peginterferon alfa during retreatment of hepatitis C[END_REF]. The study by Van 101 der Eijk et al. (2006) did not describe the criteria for patient selection. In the present 102 study only few non-responders had neutralizing antibodies to IFN α-2a. Thus the 103 absence of neutralizing antibodies to IFN α-2a might not explain the absence of 104 response. 105 A higher proportion of patients harboring neutralizing antibodies to IFN (39%) was found 106 in the present study compared with the study by [START_REF] Leroy | Role of anti-interferon antibodies in breakthrough occurrence during alpha 2a and 2b therapy in patients with chronic hepatitis C[END_REF] (3 to 107 9%); but [START_REF] Leroy | Role of anti-interferon antibodies in breakthrough occurrence during alpha 2a and 2b therapy in patients with chronic hepatitis C[END_REF] did not find a relationship with initial response but rather with 108

breakthrough. 109

It has been suggested recently that host genetics might be more useful for predicting 110 drug response, as genome-wide association studies have reported associations 111 between IL28B single polynucleotide polymorphisms and the response to antiviral 112 treatment in individuals infected with HCV genotype 1. In these studies, eight single 113 polynucleotide polymorphisms (rs8105790, rs12979860, rs11881222, rs8103142, 114 rs28416813, rs4803219, rs8099917, and rs7248668) of IL28B were analyzed, with a 115 view to identifying associations with the response to PEG IFN α-2a and RIBA [Ge et al., 116 2009;[START_REF] Mccarthy | Replicated Association between an IL28B Gene Variant and a Sustained Response to Pegylated Interferon and Ribavirin[END_REF][START_REF] Rauch | Genetic Variation in IL28B Is Associated With Chronic Hepatitis C and Treatment Failure: A Genome-wide Association Study[END_REF][START_REF] Suppiah | IL28B is associated with response to chronic hepatitis C interferonalpha and ribavirin therapy[END_REF][START_REF] Thomas | Genetic variation in IL28B and spontaneous clearance of hepatitis C virus[END_REF]. 117 118 Isolated cases have been observed but might well be explained by a selection bias of 119 very specific cases in single centers. Among re-treated patients, second-line treatment 120 with PEG IFN α-2a + RIBA yields a virological response in the presence of antibody-121 mediated resistance to conventional IFN treatment, and neutralizing antibody to IFN α-122 2a cannot be considered as a predictor of a virological response among these patients. 123

Nevertheless, there might be circumstances or populations behaving differently. Indeed, 124 Jorns et al. [START_REF] Jorns | Rapid and simple detection of IFNneutralizing antibodies in chronic hepatitis C non-responsive to IFNalpha[END_REF] showed that anti-IFN α-2a antibodies had already 125 developed after the first of four unsuccessful IFN therapies, suggesting that neutralizing 126 antibodies may have contributed to the failure of previous IFN treatment lines. 127 However, would the results be the same if natural IFN were used for the second-line 128 therapy instead of recombinant IFN? Indeed, there are several indications that 129 neutralizing antibodies to recombinant IFNa do not redevelop during natural IFN re-130 treatment and, when still present, they are not able to neutralize all subtypes present in 131 the mixture of natural IFN preparations [START_REF] Antonelli | Neutralizing antibodies to interferon-alpha: relative frequency in patients treated with different interferon preparations[END_REF][START_REF] Antonelli | Antibodies to interferon (IFN) in hepatitis C patients relapsing while continuing recombinant IFN-alpha2 therapy[END_REF]Berg 132 et al., 2001;[START_REF] Milella | Neutralizing antibodies to recombinant alpha-interferon and response to therapy in chronic hepatitis C virus infection[END_REF][START_REF] Milella | Treatment with natural IFN of hepatitis C patients with or without antibodies to recombinant IFN[END_REF][START_REF] Roffi | Breakthrough during recombinant interferon alfa therapy in patients with chronic hepatitis C virus infection: prevalence, etiology, and management[END_REF]. An association of 133 neutralizing antibodies with treatment failure was reported previously [Basso et al., 134 2007;[START_REF] Cornberg | Treatment with daily consensus interferon (CIFN) plus ribavirin in non-responder patients with chronic hepatitis C: a randomized open-label pilot study[END_REF][START_REF] Poynard | Peginterferon alfa-2b and ribavirin: effective in patients with hepatitis C who failed interferon alfa/ribavirin therapy[END_REF][START_REF] Sherman | Peginterferon alfa-2a (40KD) plus ribavirin in chronic hepatitis C patients who failed previous interferon therapy[END_REF][START_REF] Shiffman | Management of patients with chronic hepatitis C virus infection and previous nonresponse[END_REF]135 Taliani et al., 2006;[START_REF] Veldt | Retreatment of hepatitis C non-responsive to interferon. A placebo controlled randomized trial of ribavirin monotherapy versus combination therapy with Ribavirin and Interferon in 121 patients in the Benelux [ISRCTN53821378[END_REF]. Several studies showed that re-treatment with 136 natural IFN was then able to restore or induce a virological response in hepatitis C 137 patients who developed an antibody-mediated resistance to conventional recombinant 138 IFN treatment [START_REF] Antonelli | Neutralizing antibodies to interferon-alpha: relative frequency in patients treated with different interferon preparations[END_REF][START_REF] Antonelli | Antibodies to interferon (IFN) in hepatitis C patients relapsing while continuing recombinant IFN-alpha2 therapy[END_REF]. 139

In conclusion, this study shows that neutralizing antibodies to IFN α-2a can be found at 140 similar levels in patients who respond and who do not respond to a re-treatment by PEG 141

  current study included serum samples during the first 12 weeks when 32 patients received PEG IFN α-2a and RIBA exclusively. 33 Adult patients (18-70 years) were eligible if they had chronic hepatitis C, were non-34 responders to a previous treatment with PEG IFN and RIBA (at least 12 weeks without 35 treatment change and stopped at least 3 months before enrolment), had a Metavir 36 histological score ≥F2, and signed a written informed consent. The protocol was 37 approved by the ethics committee of Haut Lévêque hospital (Pessac, France), and was 38 conducted in compliance with the Declaration of Helsinki. 39

  Statistical analysis:Fisher's exact or Chi-square tests were used to compare 55 proportions. The non-parametric Wilcoxon test was used to compare medians. All 56 calculations were assessed using SAS V9.1.3 software (SAS Institute Inc. Cary, NC) 57 58 59 RESULTS 60 Twenty-three patients were non-responders and 20 patients were responders at week 61 12 to the initial phase of second-line treatment. Levels of IFN α-2a and neutralizing 62

  differ between the 19 responders to initial phase of second line treatment and the 23 69 non-responders :< 3.3 (<3.3-371.4), 1457.3 (106.8-3284.8), and 1652 (90.8-5000); 84.5 70 (3.3-277.4), 1407.4 (120.2-2443.4), and 1620.1 (120.2-2287.1) respectively. Levels 71 reached at weeks 4 and 12 were in the therapeutic range and indicated exposure to 72 exogenous IFN. Neutralizing antibody levels were detectable among 3/19 responders 73 (16%) vs. 5/23 non-responders (22%) (p=0.70) at week 0, among 6/19 responders 74 (32%) vs. 6/23 non-responders (26%) (p=1.0) at week 4, and among 7/19 responders 75

  IFN α-2a + RIBA. Other mechanisms, such as host genetic or immunological factors, 142 need to be identified and investigated in unbiased studies to explain most treatment 143 failures among patients infected chronically by HCV and who adhered to their therapy.

Table 1 :

 1 Endogenous IFN-α, presence of neutralizing antibody to IFN-α, and treatment response at week 12; analysis of 42 patients of the ANRS HC16 GAMMATRI trial

		HCV RNA decrease > 2log10 at week 12
			yes		no
		(responders)	(non-responders)
	Neutralizing antibody to IFN-α
	Week 0
	> 1.38 ng/ml (%) 3	(16)	5	(22)	p=0.700
	Median (IQR*)	0	(0-0)	0	(0-0)
	Week 4
	> 1.38 ng/ml (%) 6	(32)	6	(26)	p=1.000
	Median (IQR*)	0	(0-53)	0	(0-81)
	Week 12
	> 1.38 ng/ml (%) 7	(37)	6	(26)	p=0.057
	Median (IQR*)	0	(0-124)	0	(0-33)
	Interferon α-2a levels
	Week 0
	> 3.3 pg/ml (%)	4	(21)	12	(52)	p=0.057
	Median (IQR*)	0	(0-0)	85	(0-181)
	Week 4
	> 3.3 pg/ml (%)	18	(95)	21	(91)
	Median (IQR*)	1457 (876-1722)	1407 (960-1903)
	Week 12
	> 3.3 pg/ml (%)	19	(100)	22	(96)
	Median (IQR*)	1652 (1147-2633) 1620 (1297-1785)
	Abbreviation: IQR = interquartile range

Page 11 of 11 John Wiley & Sons Journal of Medical Virology

John Wiley & SonsJournal of Medical Virology

Appendix