Eric Bittar
email: eric.bittar@imag.fr

Nicolas Tsingos
email: nicolas.tsingos@imag.fr

Marie-Paule Gascuel
email: marie-paule.gascuel@imag.fr

Automatic Reconstruction of Unstructured 3D Data: Combining a Medial Axis and Implicit Surfaces

Keywords: Shape reconstruction, implicit surfaces, medial axis

 . Initialisation, however, is more robust and e cient since there is computation of the medial axis of the set of points. Instead of subdividing existing skeletons in order to re ne the object's surface, a new reconstruction algorithm progressively selects skeleton-points from the precomputed medial axis using an heuristic principle based on a \local energy" criterion. This drastically speeds up the reconstruction process. Moreover, using the medial axis allows reconstruction of objects with complex topology and geometry, like objects that have holes and branches or that are composed of several connected components. This process is fully automatic. The method has been successfully applied to both synthetic and real data.

Introduction

With the recent development of advanced range-imaging sensors, automatic object reconstruction from sets of sample points has became a very important issue in Computer Graphics. It can be used for mixing real and synthetic objects in production applications, or for speeding up the modelling of complex shapes like character faces. Reconstruction techniques are also needed in many application elds such as inverse engineering, simulation, and medical imaging. Although many di erent approaches have already been proposed, robust methods lack for reconstructing unstructured sets of points. Methods must be applicable to complex geometrical and topological objects, including those which contain holes, branches, and possibly several connected components,even without any a-priori information. This paper presents a fully automatic reconstruction algorithm based on both medial axis and implicit surfaces that solves this problem.

Previous approaches

One of the most common approaches for reconstruction consists in deforming a surface or a volume in order to t the set of data points. Energy-minimising curves known as \snakes", were introduced by Kass, Witkin and Terzopoulos [START_REF] Kass | Snakes: Active contour models[END_REF] . The idea has been widely used and developed [START_REF] Terzopoulos | Constraints on deformable models: Recovering 3D shape and nonrigid motion[END_REF] , and the active contour has turned to an active surface deformed by internal forces such as pressure and by external forces based on the data set [START_REF] Cohen | Deformable Models for 3D Medical Images using Finite Element and Balloons[END_REF] . Most of the time implementation relies on splines, but Miller proposes a geometrically deformable model based on triangles [START_REF] Miller | Geometrically deformed models: A method for extracting closed geometric models from volume data[END_REF] . Sclaro and Pentland [START_REF] Pentland | Generalized implicit functions for computer graphics[END_REF] t a super-quadric using modal deformations and displacement maps. Terzopoulos and Metaxas use a physically-based approach for local and global deformations of superquadrics [START_REF] Terzopoulosand | Dynamic 3D models with local and global deformations:Deformablesuperquadrics[END_REF] . All these methods reconstruct xed topological surfaces.

A few recent papers describe more general models, that can handle objects of various topologies. Delingette 9 introduces \Simplex Meshes" which enable the user to adapt topology interactively. Other approaches change the topology in a purely automatic way, such as Leitner who uses an adaptative spline surface [START_REF] Leitner | Segmentation dynamique d'images tridimensionnelles[END_REF] , and Lachaud and Bainville who derive their model from triangulation [START_REF] Lachaud | A discrete adaptative model following topological modi cations of volumes[END_REF] .

Another way to by-pass the limitation of snakes to xed topological type is to use local techniques. Szeliski reconstructs objects using physically-based interacting particles [START_REF] Szeliski | Surface Modeling with Oriented Particle Systems[END_REF] . Hoppe introduces a graph traversal technique in [START_REF] Hoppe | Surface reconstruction from unorganized points[END_REF] to approximate tangent planes at each data point. For every point in space, he calculates a signed distance to the nearest tangent plane which acts as a local linear approximation of the surface to be reconstructed. The reconstructed surface is then de ned as the zero-set of this distance function, and a polygonal representation is computed from a spatial partitionning technique. In [START_REF] Hoppe | Piecewise Smooth Surface Reconstruction[END_REF] , the author completes the method by a piecewise smooth surface optimisation in order to obtain more accurate representation and better recovery of sharp features. Boissonnat 5; 6 derives his reconstruction methods from the Delaunay triangulation of the set of data-points. Edelsbrunner and M ucke 10 introduce a parameter that tunes the degree of detail while deriving a shape from a Delaunay triangulation. Attali 1 computes the Vorono graph of the points to build the \skeleton" of the object and reconstruct its shape. The main limitation of these techniques is that they do not work well with unstructured sets of points, and cannot handle very noisy databases.

Muraki [START_REF] Muraki | Volumetric shape description of range data using blobby model[END_REF] is the rst to use implicit surfaces generated by skeletons for shape reconstruction. These surfaces have the advantage of modelling smooth free-form shapes in a very compact way, and permit an easy de nition of a \distance" to the set of data-points that can be used for energy minimisation. However, the method developped in [START_REF] Muraki | Volumetric shape description of range data using blobby model[END_REF] is very slow, and does not fully exploit the potential of implicit surfaces.

Overview

We propose a new method for reconstructing a closed object of complex unknown topology with an implicit surface generated by skeleton-points. The method uses only an unstructured set of data-points scattered on the object's surface; no further information, such as normals to the surface at each data-point, is needed. In the rst step, we calculate a medial axis from the set of points. Then, we use smart implicit surfaces providing local shape control to initialise and then progressively re ne surface reconstruction. Skeleton-points generating the iso-surface are automatically selected from the medial axis elements during an iterative process. Energy minimisation steps are performed at each iteration in order to adjust the skeleton's parameters. This reduces the nal number of skeletons used.

In the rest of this paper Section 2 introduces implicit surfaces generated by skeletons, discusses the previous techniques for reconstruction with implicit surfaces, and presents the basis of the approach. Section 3 de nes the medial axis of a set of points and shows how it can be used for initialising the positions and parameters of the skeleton-points that generate the iso-surface. Section 4 presents the iterative algorithm that progressively adds skeletons in order to perform precise reconstruction while limiting the number of skeletons used. We present results and conclusion in Section 5.

2. Principles of shape reconstruction with implicit surfaces 2.1. Iso-surfaces generated by skeletons Developed up to now as a tool for free form modeling 30; 29; 4; 3 , iso-surfaces generated by skeletons constitute a good alternative to traditional implicit surfaces directly de ned by an analytical equation. Using skeletons that are simple geometric primitives facilitates the design and o ers compact storage of complex shapes.

An implicit surface S generated by a set of skeletons Si(i = 1::n) with associated \ eld functions" fi is de ned by: S = fP 2 IR 3 = f(P) = isog where f(P) = n X i=1 fi(P) iso is a given scalar iso-value. The skeletons Si can be any geometric primitive admitting a well de ned distance function. The eld functions fi are monotonically decreasing functions of the distance to the associated skeleton. They can be de ned, for instance, by exponential functions 2 , by pieces of polynomials 20; 30 , or by parametrized procedural functions [START_REF] Kacic | Controlled blending of procedural implicit surfaces[END_REF] .

The surface surrounds a volume de ned by f(P) iso, and normal vectors are directed along the gradient of f. The examples of implicit surfaces given in Figure 1 show how the eld function can be used for tuning the way implicit primitives blend together.

Previous approaches for reconstruction with implicit surfaces

Muraki [START_REF] Muraki | Volumetric shape description of range data using blobby model[END_REF] presents an automatic method for generating an implicit shape description from range data that include both scattered points and normal vectors to the surface at those points. The surface used for reconstruction is de ned by Blinn's \Blobby Model" 2 . Only skeleton-points Si = (xi; yi; zi) are used, and elds are expressed as exponential functions of the distance d(P; Si): fi(P) = bi e ?a i d(P;S i ) where bi can be either positive or negative. A \negative skeleton" ,i.e., a skeleton with a negative eld, reduces the implicit volume, while positive skeletons extend it. The principle of the reconstruction algorithm consists in minimising an energy representing the \distance" between the current implicit surface and the data. The reconstructed shape is iteratively re ned by subdividing some skeleton-points into two new ones, and optimising their parameters according to the energy function.

However, no satisfying way is proposed to select which skeleton points must be divided, leading to a very intensive computation process which forbids the use of this method for detailled objects. Moreover, the choice of an exponential eld function doesn't localise the reconstruction process. Every part of the surface is in uenced by all the skeleton-points, including those that are distant. Adding new skeletons to the representation modi es the shape everywhere, even in areas that are already reconstructed well. Finally, the initialisation proposed with a single skeleton-point positionned at the center of mass of the data does not seem appropriate for objects of complex topology, such as objects with holes.

Tsingos et al. [START_REF] Tsingos | Semi-automatic reconstruction of implicit surfaces for medical applications[END_REF] present a semi-automatic method for reconstruction with implicit surfaces. As in [START_REF] Muraki | Volumetric shape description of range data using blobby model[END_REF] , skeletons are progressively subdivided to re ne reconstruction, but e ciency is improved by use of a selection criterion based on \local skeleton energy". In order to hold objects of complex topology and geometry, initialisation is interactively performed by the user who has to de ne an initial set of skeletons and a number of slightly overlapping \reconstruction windows". Results are good, but the experiments we did with this method show that a lot of time has to be spent trying some positions for the initial skeletons and for the reconstruction windows. This can be a problem since, despite optimisation, reconstruction does not run at interactive rates.

For most applications, a fully automatic method seems more appropriate. This is the issue addressed in this paper by introduction of medial axis to provide an automatic and robust way of initialising and adding skeletons.

Combining a medial axis and implicit surfaces

Iso-surfaces generated by skeletons are very convenient for reconstruction, since they provide an easy way to de ne an energy which gives a current \distance" to the data, they de ne a smooth surface, and they o er a very compact representation of the object for only positions of skeleton-points and associated eld parameters have to be stored.

As shown in the previous section, neither initialising the set of skeletons with a single primitive nor asking the user to perform the initialisation is a good solution. Moreover, splitting existing primitives in two is ine cient since the new skeletons are introduced at the same site, so the optimisation process has to \drag" them over a non negligible distance.

Consequently, we propose a new method that exploits medial axis information computed from the data to both initialise and progressively re ne the set of skeleton-points. The idea is to iteratively select these points from a pre-computed set of candidates. This is done in two steps:

We compute the medial axis of the data-points and tune its resolution in order to obtain a representation of the object by an appropriate number of spheres. This step takes the object's topology into account, and provides a set of candidate primitives to be used for reconstruction. The center of each sphere can be used for positionning a skeleton-point, while its radius gives information on the eld function to be chosen. In order to perform smooth surface reconstruction while using only a few of the medial axis primitives, we run an iterative process that progressively selects useful primitives from the medial axis data, uses them as new skeletons for the implicit surface, and tunes their parameters in order to obtain a better data t. The heuristic we use for quickly selecting which primitive to add next is based on the choice of a function with local support for expressing the eld functions. The two next sections detail the two steps of this algorithm.

Medial axis

The \medial axis" [START_REF] Pfaltz | Computer representation of planar regions by their skeletons[END_REF] is a lling-out of an object with balls. It can be intuitively considered as the set of points that are the farthest \inside" the object, forming a \skeleton" that gives information on the object's topology and geometry. Thus, these points seem very good candidates for becoming skeletons of an iso-surface that represents the object.

De nitions

Let us consider a set S of spheres that are included inside the object.

Maximal sphere: a maximal shpere is a sphere of S that is not included in any other sphere of S. Medial axis: the medial axis is the locality of the centers of the maximal spheres of the object, associated with their radii.

Medial axis extraction

We use an approach based on discrete geometry, for which an approximation of the object as a set of voxels is required. To obtain this representation, we rst divide a bounding box for the set of data-points into a uniform 3D lattice. Then, we have to identify voxels to be labelled as \inside voxels".

1. Space partitionning: Voxels containing data points are labelled as \border voxels" which means that they will be crossed by the surface to be reconstructed.

2. Labelling the inside: Finding where the inside is located is not easy for an object of any topology that may have several connected components. Thus, the outside is labelled rst. We start at a voxel located at a corner of the 3D lattice, and propagate the information \outside voxel" to all its unlabelled neighbors. The inner voxels are those that have not been reached at the end of this process. The border voxels are not entirely included in the object, so we do not consider them as inner voxels. This method works for most applications, but would not hold the case of a closed object containing a closed hole. In other words, the outside is supposed to have a single connected component.

Distance map computation and Medial-axis extraction:

Once the border and the inside of the object are de ned, a distance-map is computed based on the Chamfer distance giving a distance between each innner voxel of the object and the outside. Then, we use a local criterion for extracting the medial axis. A detailled description of the algorithm we use is given in Appendix A.

Tuning the medial axis resolution according to the data

Low resolution medial axis may miss the object's details (see Figure 2 (a)), but resolution cannot be increased to any value. If we represent the inner volume of the object as a function of the resolution (de ned as the number of voxels in one edge of the cubic lattice), we see that this function grows to a maximum, and then decreases (see Figure 3). After the peak, the resolution is so high that the voxels labelled as \border voxel" do not de ne a closed surface anymore. In this case, the inside/outside separation cannot be correctly established (see Figure 2 (c)).

In practice, the resolution parameter that is chosen (see Figure 2 (b)) must represent a good compromise between the quality of the nal reconstruction and the number of medial axis elements, which increases with resolution and in uences the processing time. We set it at the middle of the area where volume increases.

Turning medial axes into implicit surfaces

Since an isolated skeleton-point generates an implicit sphere, a simple solution would be to directly use the medial axis points for generating blended iso-surfaces. The eld function characteristics could be computed from the radii of medial axis spheres, with sharp tangents in order to limit blending between neighboring spheres.

However, this approach would have major limitations. The surface obtained would not be smooth, since sharp eld functions are needed to generate a surface that is close to the set of maximal spheres.

Some artifact in the reconstructed shape would be produced, since the medial axis is not minimal, in the sense that a medial axis sphere may be included in the union of some other spheres. Using all these overlapping spheres for implicit reconstruction would locally move the surface away from the data points. Thus, our idea is to further exploit the blending properties of implicit surfaces in order to generate an isosurface from only a small subset of the medial axis points. This leads to both a more precise and a more compact representation of the reconstructed shape.

The next section explains how we use the medial axis for selecting and adding new skeletons in an iterative way, progressively re ning the object's representation. This new method avoids the intensive computational process of splitting skeletons used in previous approaches.

Creation and re nement of the implicit surface

The basic idea is to progressively select some of the medial axis elements, turn them into skeletons with associated eld functions, and adjust their parameters in order to improve the quality of reconstruction. To achieve this, the de nition of a robust and e cient selection heuristic is a very important point. The use of local eld functions permits de nition of such an heuristic.

This section describes the choice of eld functions, and then gives details about the selection heuristic and the general reconstruction algorithm.

De nition of local eld functions

Local eld functions that become zero with their derivatives at a certain radius of in uence R have been introduced for optimising eld computations during the design of complex objects [START_REF] Wyvill | Data structure for soft objects[END_REF] . Another bene t is that such elds o er local control on the implicit surface, which is particularly important for a reconstruction process since optimising skeletons in an area should not modify an adequate reconstruction of the data already obtained elsewhere. As shown in the next section, the use of local eld will also simplify the de nition of a local selection criterion for turning a medial axis into an implicit surface.

The chosen eld function will be used in a computer-intensive minimisation process. So we need a model that is controlled by very few parameters (in order to limit the dimension of the search space), and that provides e cient computation time as well. Consequently, eld contributions fi that are composed of both a linear and a quadratic curve segment are demonstrated. They have only two parameters (see Figure 4):

The radius ei of the sphere created by a skeleton-point Si alone (ei is characterized by fi(ei) = iso) ; The sti ness ki in ei, that de nes the blending properties of the surface. ki can be used to tune the smoothness of the resulting surface (see Figure 1). Contrary to Muraki who uses both positive and negative eld functions, we use positive elds only. This seems more appropriate for future applications that may involve a physically-based simulation of the deformations of reconstructed objects, for instance with the method presented in [START_REF] Gascuel | An implicit formulation for precise contact modeling between exible solids[END_REF] . The function is expressed by: fi(P) = ?kir + kiei + 1 if r 2 0;ei] fi(P) = kiei(ei ? Ri) + 3ei ? Ri (ei ? Ri) [START_REF] Bloomenthal | Convolution surfaces[END_REF] (r ? Ri) 2 if r 2 ei; Ri] fi(P) = 0 elsewhere Where r = d(P; Si) and Ri = (ei ? 2 k i ) is the radius of in uence.

This leads to only 5 parameters which have to be optimised for each skeleton-point: ei, ki, xi, yi, zi.

A local criterion to e ciently select new primitives

Before the reconstruction process, an implicit primitive (e.g., a skeleton-point provided with a eld function)

is associated with each element of the medial axis: the parameters xi, yi, zi are de ned by the medial axis points, ei is given by the radius of the associated maximal sphere, and ki is set to the inverse of the size of voxels used in the medial axis construction in order to give a signi cant to the size of the area of in uence around each primitive. Then, at each step of the reconstruction process, some of these primitives are added to the iso-surface in order to improve its t with the data. Indeed, the best candidates for insertion are those of the medial axis primitives Si that were not already selected, and which area of in uence correspond to the zone of the surface where the reconstruction is the worst, as depicted in Figure 5.

So, we de ne the selection criterion as:

Ci = m i X j=1 (f(Pj;i) ? iso) 2 !
where the sum is made only on the mi points Pj;i that are inside Si's sphere of in uence. The primitives with greatest Ci will be those selected next.

In practice, we use this criterion for selecting several primitives at each iteration of the algorithm, taking care that they stay well distributed within the object. Then we optimise the parameters of these primitives before performing further selections. Details of this process follow.

The reconstruction algorithm

We associate a ag \chosen primitive" to each medial axis element in order to indicate if it has been inserted to the implicit object or not. We also attach a \chosen point" ag to each data point, in order to indicate wether the point is or is not within the area of in uence of a sphere that has been selected at the current step.

At each reconstruction step: 1. The \chosen point" ag of each data point is reset. 2. As long as some data points have not been selected:

The local criterion Ci associated with each of the non-selected primitives, based on the non-selected data points is calculated, and

The primitive with highest Ci is marked as \chosen primitive", and the data points of its area of in uence are marked as \chosen points".

3. The ei and ki parameters of the primitives that have just been added are optimised, keeping them xed in space (indeed, the medial axis point gives a good estimate of their position). 4. All the parameters of all the skeletons de ning the implicit surface are optimised. This permits reconstruction with fewer skeletons. As in previous approaches, the energy that is minimised during the optimisation steps is de ned from the eld values at the data points P. The number of the data points is ndata. Area of influence of a primitive which "chosen primitive" flag is clear Area of influence of a primitive which "chosen primitive" flag is set

Experimental results

The automatic reconstruction process presented is implemented within the visualisation software AVS on a DEC AXP3000 workstation. The numerical details are given in Table 1.

Medial axes examples

We show the results of medial axes calculations on a synthetic torus, on the torso of a dummy which data points come from a range sensor, and on a vertebra (see Figure 6). The data points of the vertebra have been obtained by segmentation of scanner images. A medial axis computation takes about 10 seconds for these examples. The radii are represented in grey-level: the darkest are the largest.

Samples of reconstruction

This section shows results of reconstruction with the progressive selection algorithm we have de ned (Figures 7, 8 and9). The example of the synthetic \Y" (Figures 7 and8 (c)) demonstrates that the reconstruction works, even if the distance between adjacent slicing planes is large in comparison to the distance between points on the same contour, which is a limitation for other methods, like Hoppe's [START_REF] Hoppe | Piecewise Smooth Surface Reconstruction[END_REF] .

The set of data points of the vertebra which contained 19837 points has been reduced to 2037 points to be used in the reconstruction step.

Conclusion and Future work

A fully automatic surface reconstruction method is presented that can be used on an unstructured set of data points and that can handle objects of complex geometry and topology. The method is based on iso-surfaces generated by skeletons providing a smooth compact representation of complex shapes. The essential principle is to exploit the information given by the discrete medial axis of the set of points to facilitate and accelerate reconstruction. Rather than splitting implicit primitives as in [START_REF] Muraki | Volumetric shape description of range data using blobby model[END_REF] before each optimisation step, a fast and robust algorithm is presented that progressively selects new primitives within the discrete medial axis set. This results in a compact representation of smooth free form shapes, since the number of skeletons selected for the implicit surface generation is much smaller than the discrete medial axis. Reconstruction with still fewer implicit primitives could be performed by constructing more complicated skeletons such as curve segments from the medial axis. Non isotropic eld functions depending on the curve parameter could then be computed for de ning the isosurface.

Medial axis extraction

We use a simple local criterion. Each voxel that veri es the local maximum criterion is included to the medial axis.

Local maximum: A voxel v that does not propagate the distance information to any of its neighbours ni(v) of the 3 3 3 lter is called a local maximum:

ni(v) < v + wi 8i

For a technical reason explained in [START_REF] Thiel | Les Distances de Chanfrein en Analyse d'Images: Fondements et Applications[END_REF] , all the values 3 in the distance map must be replaced by the value 1 before using the local maximum criterion.

Figure 1 :

 1 Figure 1: The implicit surface de ned by two skeleton-points that generate the same eld function. The slope used for the eld function on the right side is ten time greater than on the left side.

Figure 2 :Figure 3 :

 23 Figure 2: medial axis of the vertebra, resolution = (a) 24, (b) 42, (c) 58

Figure 4 :

 4 Figure 4: Local eld function with two parameters.

2 !

 2 P) ? iso) next primitive to select Data points with flag "chosen point" set Data points with flag "chosen point" clear

Figure 5 :

 5 Figure 5: A step of the algorithm

Figure 6 :

 6 Figure 6: The data points and the spheres of the medial axis.

Figure 7 :Figure 8 :Figure 9 :

 789 Figure 7: Data points and skeleton-points.

Figure 11 :

 11 Figure 11: Forward and backward half-lter, and their associated weights.

Figure 12 :

 12 Figure 12: Example of the steps of the medial axis calculation in 2D with d3;4.

Table 1 :

 1 Reconstruction statistics

	number of medial axis n. of medial number of object data points resolution axis spheres skeletons Energy E time (sec) of passes nal calculation number
	torus torso Y vertebra	4176 2027 871 19837 2037	22 26 14 42	172 181 16 1050	12 42 10 46	5:46e ?4 3:78e ?3 2:74e ?3 3:14e ?2	163 843 194 3135	1 3 1 1

Appendix A: Medial axis computation Distance map

The distance transform operation uses an image as input where the voxels that are inside the object have the value 1 and the others have the value 0, and replaces the value of the object voxels by the distance from the voxel to the background, i.e., to the nearest background voxel. This is called a distance map.

The Chamfer distance

We use a discrete distance called Chamfer distance d3;4;5 7; 27 to approximate the euclidian distance in 3D. The principle is to give a weighted cost of 3, 4, or 5 to the move from a voxel v0 to each of its 26 neighbours (see Figure 10). The restriction of d3;4;5 in 2D, d3;4, is used as an example (see Figures 10 and12).

Building a distance map

The Chamfer distance allows a rapid distance map computation. Instead of exhaustively testing the whole volume for each inner voxel in order to locate the nearest background voxel, the Rosenfeld method [START_REF] Rosenfeld | Sequentialoperationsin digital picture processing[END_REF] is prefered. The distance information is propagated to all the voxels using two sequential convolution operations on the volume. The convolution lters are the two halves of a 3 3 3 cube, centered on current voxel v0. They are symmetric around v0, the rst half FF contains the voxels vi before v0 in the scanning direction, their local coordinates are (xi; yi; zi) 2 f?1;0;1g [START_REF] Bloomenthal | Convolution surfaces[END_REF] and their weights are wi (3, 4 or 5). The backward half-lter BF contains the voxels vi(?xi; ?yi;?zi) of weights wi. None of the two lters contains 0 (see Figure 11).

Each voxel of the object must have an initial value of 1, the background is 0. The two passes successively replace each voxel value V by a value depending on the voxel neighbours values.

Forward Pass: top to bottom, back to front, and left to right V x; y; z] = minv i 2FF fV x + xi; y + yi; z + zi] + wig Backward Pass: bottom to top,front to back, and right to left V x; y; z] = minv i 2BF fV x; y; z];V x ? xi; y ? yi; z ? zi] + wig

Once we have computed the distance map on the object, we need to select the points that constitute the medial axis.


Yann Busnel
email: yann.busnel@univ-nantes.fr

Patricia Serrano-Alvarado
email: patricia.serrano-alvarado@univ-nantes.fr

Philippe Lamarre
email: philippe.lamarre@univ-nantes.fr

Trust your Social Network According to Satisfaction, Reputation and Privacy

Keywords: H.4 [Information Systems Applications]: Miscellaneous; C.2.4 [Computer-communication networks]: Distributed systems Privacy, Reputation, Satisfaction, Trust

Nowadays we are witnessing a massive usage of social networking sites (Facebook, MySpace, etc.). Those systems facilitate user interaction; however, they disregard users' wellbeing because users are forced to trust the network and to use the system without any guarantees. We consider that this is little satisfactory for systems where the users make the network successful thanks to their interactions.

In this work, we propose to study how to improve users' trust towards the system in terms of reputation, privacy and satisfaction. Despite former separate studies, we argue that these notions are strongly linked and must be analyzed in a correlated way.

INTRODUCTION

Recently, several sites, built on social networks, are webbased applications that allow users worldwide to publish potentially any kind of information (personal, professional, etc.), and interact with each other through services provided by the applications. Current examples of famous social networking applications include Facebook, MySpace, Twitter, Delicious and LinkedIn. In those large-scale networks, the more users are numerous and the amount of shared information is larger, the more the system is interesting and at-tractive 1 . Users then make the network successful thanks to their interactions. However, actual systems disregard users' wellbeing. In fact, specific individual needs are generally not taken into account. Users are forced to trust the system, without any guarantees. Current systems aim to be considered as trustworthy in terms of efficiency and reliability, but ignore other subjective aspects like users' expectation or privacy of used data and resources. In general, they neglect users' satisfaction in favor of cost saving.

On the other hand, network size endlessly increases. Most of current social networks mainly rely on a client-server communication paradigm through which users (clients) connect to a web site (server, possibly geographically distributed for performance purposes) in order to make use of a wide set of available services. Those kind of systems are good for simplicity of use, deployment and maintenance but data privacy is completely ignored. As this approach currently reaches their bounds, numerous fully distributed solutions are designed and recent outcomes argue for their feasibility [START_REF] Buchegger | PeerSoN: P2P Social Networking -Early Experiences and Insights[END_REF][START_REF] Antonio Cutillo | Privacy Preserving Social Networking Through Decentralization[END_REF][START_REF] Tribler | Tribler: A Fully Distributed File-Sharing System[END_REF]. Peer-to-peer (P2P) paradigm facilitates scalability but also brings up some problems. Since peers are heterogeneous, some might be faulty or malicious, and cannot ensure services that provide enough quality. In order to restrain those behaviors, several systems attempt to increase user's trust toward the system by using reputation mechanisms [START_REF] Sepandar | The Eigentrust algorithm for reputation management in P2P networks[END_REF][START_REF] Singh | TrustMe: Anonymous Management of Trust Relationships in Decentralized P2P Systems[END_REF][START_REF] Zhou | PowerTrust: A Robust and Scalable Reputation System for Trusted Peer-to-Peer Computing[END_REF]. Those mechanism can be used to help peers to distinguish good from bad partners which eventually enhances the users' satisfaction.

Reputation mechanisms require a size-able degree of sensitive information which can be personal, professional, behavioral, etc. Unfortunately, this goes against the privacy rights of individuals. In fact, the Organization for Economic Cooperation and Development (OECD) provides some guidelines that systems should consider in data privacy management (cf. Section 2.3) [START_REF]Guidelines on the Protection of Privacy and Transborder Flows of Personal Data[END_REF].

The aim of this position paper is to put down some milestones of a complementary 3-facet analysis (satisfaction, reputation and privacy) to allow users to trust the system. Our objective is to allow the deployment of fully decentralized architectures, which can define different degrees of users' trust towards the system in terms of, mainly, privacy, reputation and satisfaction (global and individual), according to different applicative contexts. Nevertheless, it is obvious that user's trust is not only linked to reputation, satisfaction and privacy, but our work consists in a first step and we have make the choice to start with this focus. This paper is organized as follows. Section 2 introduces the three dimensions of our current work. Then, Section 3 presents the links that we identify between these dimensions. Section 4 presents the objectives of our proposition. We finally conclude and raise some open issues in Section 5.

SOME CONCEPTS TO TRUST THE SYS-TEM

In this section, we briefly introduce the three dimensions used in this work. In the literature, they have been studied separately but we argue that they are intrinsically connected when trusting the system is a main challenge.

Satisfaction

Studying user satisfaction is generally motivated by an attempt to improve information systems. A full satisfaction requires a system which both provides results of good quality and is also usable accordingly to the user needs. For example, in the field of information retrieval, per-query answers relevance measures [START_REF] Cleverdon | The significance of the cranfield tests on index languages[END_REF][START_REF] Voorhees | Evaluation by highly relevant documents[END_REF][START_REF] Sanderson | Information retrieval system evaluation: effort, sensitivity, and reliability[END_REF] provide standardized, repeatable measurements of search result quality while usability studies [START_REF] Bilal | Children's use of the yahooligans! web search engine: Ii. cognitive and physical behaviors on research tasks[END_REF][START_REF] Jansen | A review of web searching studies and a framework for future research[END_REF] try to measure the user experience in a more direct way. Recently, in the context of query allocation and routing services, users' satisfaction -with respect to the system comportment -has been studied [START_REF] Bakhouya | A Query Routing Approach Based on Users' Satisfaction for Resource Discovery in Service-Oriented Networks[END_REF][START_REF] Quiané-Ruiz | A Self-Adaptable Query Allocation Framework for Distributed Information Systems[END_REF]. It is defined as a long run notion evaluating the capacity of the system to follow the intentions of each participant. For instance, a data provider can be satisfied even if sometimes the system imposes queries he does not intend to treat, or a data consumer is satisfied because "in general" she receives answers from the providers she prefers. Here, quality of results is a private notion that is assumed to be used by a data consumer to decide which providers she prefers.

Intuitively, a participant is satisfied by the system process if the latter meets its intentions in the long term (i.e. matching users' expectations as a way to figure satisfaction). The satisfaction of participants may have a deep impact on the system, because they may decide whether to stay or to leave the system based on it. In [START_REF] Quiané-Ruiz | A Self-Adaptable Query Allocation Framework for Distributed Information Systems[END_REF], a complete model is proposed that characterizes autonomous participants by formally defining the adequacy, satisfaction, and allocation satisfaction of a participant.

Whatever the system (information retrieval, query or ressource allocation, social network, etc.), in order to define her intentions and strategy, a participant needs information about the system itself and its participants. Similarly, the system needs information about the participants to adapt himself to individual intentions and to evaluate participants' satisfaction. So, on one hand, there are needs of information about participants while on the other hand, the principles of privacy require sensitive information not to be disclosed.

As a consequence, a solution has to be built on the core idea of compromize, equilibrium of which may differ from one participant to the other.

Reputation

It is expected that systems remain reliable, efficient and secure even if they evolve or increase. Reputation systems contribute to this goal in systems based on a large-scale network composed by numerous autonomous and potentially untrusted participants. As proposed in [START_REF] Marti | Taxonomy of Trust: Categorizing P2P Reputation Systems[END_REF], a reputation system design can be divided in three main basic blocks: information gathering, scoring and ranking, and response.

Depending on the application context, these blocks can take various states. Application context includes expected user behavior (e.g., churn, reliability, privacy, anonymity) as well as adversarial goals and power (e.g., selfish peers, malicious peers, traitors, whitewashers) or environment limitation (e.g., centralized vs decentralized).

Several decentralized solutions [START_REF] Bethencourt | Signatures of Reputation: Towards Trust Without Identity[END_REF][START_REF] Chen | Seprep: A novel reputation evaluation model in peer-to-peer networks[END_REF][START_REF] Sepandar | The Eigentrust algorithm for reputation management in P2P networks[END_REF][START_REF] Remondino | How users' participation affects reputation management systems: The case of p2p networks[END_REF][START_REF] Singh | TrustMe: Anonymous Management of Trust Relationships in Decentralized P2P Systems[END_REF] have been recently proposed. For instance, among the most cited ones, Eigentrust [START_REF] Sepandar | The Eigentrust algorithm for reputation management in P2P networks[END_REF] presents a PageRank-like algorithm that computes a global reputation rating by using transaction reports and the rating of the reporting peer. TrustMe [START_REF] Singh | TrustMe: Anonymous Management of Trust Relationships in Decentralized P2P Systems[END_REF] imposes that a transaction certificate be pairwise established before any transaction between involved peers takes place. Pow-erTrust [START_REF] Zhou | PowerTrust: A Robust and Scalable Reputation System for Trusted Peer-to-Peer Computing[END_REF] constructs a trust overlay network to model the trust relationships among peers.

All these approaches need potentially sensitive information which can be personal, professional, behavioral, etc. that lead to privacy breaches. Recently, some studies have been proposed in order to ensure efficient reputation mechanisms, under classical anonymous assumption [START_REF] Androulaki | Reputation systems for anonymous networks[END_REF][START_REF] Bethencourt | Signatures of Reputation: Towards Trust Without Identity[END_REF]. These approaches permit to reach an interesting but challenging tradeoff between reputation and privacy purposes. The latter are presented below.

Privacy

Data privacy is the right of individuals to determine for themselves when, how and to what extent information about them is communicated to others [START_REF] Westin | Privacy and Freedom[END_REF]. It has been treated by many organizations and legislations which have defined well accepted principles. According to the OECD guidelines [START_REF]Guidelines on the Protection of Privacy and Transborder Flows of Personal Data[END_REF], data privacy should consider:

• collection limitation;

• purpose specification;

• use limitation;

• data quality

• security safeguards;

• openness

• individual participation;

• accountability. modify her privacy preferences freely. In general, those preferences are defined in "privacy policies" (PP). Inspired form P3P [START_REF] Cranor | The Platform for Privacy Preferences 1.0. (P3P 1.0) Specification[END_REF], we consider that PPs should consider authorized users, allowed operations, access purposes, access conditions, retention time, obligations and the minimal trust level necessary to allow data access.

Privacy concerns individual choices of human beings, it is thus important to allow each individual to determine and

Efforts are being realized to offer solutions to personal distributed data privacy. In [START_REF] Aimeur | Towards a Privacy-Enhanced Social Networking Site[END_REF], authors propose a privacyenhanced social networking site oriented to satisfy privacy awareness and customization, data minimization and data sovereignty. PriServ [START_REF] Jawad | A Data Privacy Service for Structured P2P Systems[END_REF], is a privacy service for P2P systems that proposes functions to publish and request private data by taking into account the PPs of data owners (in particular, access purpose, operations and authorized users).

Hello World [START_REF] Ludwig | HelloWorld: An Open Source, Distributed and Secure Social Network[END_REF], is a distributed social network that focus on authentication, decentralization and security. Their objective is to give the control of their data to data owners by letting them to manage their data privacy. [START_REF] Antonio Cutillo | Privacy Preserving Social Networking Through Decentralization[END_REF] proposes a social networking based on P2P systems. It uses and propose techniques to trust users in the system, anonymization of traffic, pseudonyms, etc. to offer privacy protection to users.

CONCEPT INTERACTIONS

Interactions and dependencies of the three concepts that we are concerned on, can be taken from different points of view. This paper analyzes a first point of view which surely may evolve.

We consider that different levels of users' satisfaction, reputation and privacy have direct repercussion on the trust towards the system. Figure 1 shows some links among those concepts. The center box corresponds to the trust towards the system as it is a main issue. We consider that each user of the system can have her own perception of the level of trust she can have in the system. But also, the system can be considered globally as trusted or not.

The satisfaction notion depends on the objectives/intentions/motivations of each user when using the system. Then, a user can have a satisfaction perception that can be influenced only by its local vision of the system, or by a global one. The global vision means that each user can perceive the interaction of other users in the system even if she is not concerned.

Reputation is constructed from the interaction and feedback of users. The reputation system is supposed to calculate individually the trustworthy level of users and the set of those levels may indicate the trustworthy of the global system.

Privacy concerns the respect of individual PPs. A system may in general respect the user' privacy but eventually some users may be unhappy because they consider that their personal privacy is not respected2 . Guaranteeing PPs' respect has an important influence on the system. Reputation and satisfaction mechanisms may need more or less private information to work efficiently.

Interactions among these three concepts can be complementary or antagonistic, for instance:

• the more a user trusts towards the system, the more she is satisfied, and the more she is satisfied, the more she trusts towards the system.

• In the same way, the more the reputation mechanism is efficient, the more users trust towards the system, and the more a user trusts towards the system, the more she contributes honestly to the reputation mechanism.

• Similarly, the more the reputation mechanism is efficient, the more users are satisfied, and the more a user is satisfied, the more the reputation mechanism will be efficient.

• It is possible that the reputation mechanism be efficient and concludes that the majority of users are untrustworthy. In this case, users will not trust the system even if they continue to contribute to the reputation mechanism.

• Concerning privacy, the more information is gathered, the more the reputation mechanism is efficient. And the less a user trusts towards the system, the less she discloses information. Finally, the more a user's privacy is respected, the more this user is satisfied and inversely.

OBJECTIVES

The first issue we are working on is identifying the common, but also the incompatible, properties of the three considered dimensions (cf. left side of Figure 2). Clearly, privacy and reputation are closely related by the quantity/type of shared information. Concerning satisfaction and privacy, one link is the privacy respect which depends on, for instance, the respect of user's PPs. The relationship between reputation and satisfaction can be for instance the efficiency of reputation mechanism. Thus, different levels of privacy and reputation guarantees may lead to different levels of satisfaction. Therefore, reaching a point located in the intersection area of all these dimensions (i.e., Area A in the figure) represents a good tradeoff to attend a high level of trust towards the system. In addition, our main objective is to define a generic metric that takes into account all these dimensions and helps the designer to maximize the users' trust towards the system while respecting the system/application constrains.

Privacy

The right side of Figure 2 illustrates the mutual impact of privacy, reputation and satisfaction in the following terms.

• Privacy. It represents the satisfaction in terms of privacy guarantees which can be the amount of information that it is not necessary to share within the system or the respect of PPs.

• Reputation. It represents the satisfaction of the reputation mechanism in terms of power as reliability, efficiency and most of all, consistency with the reality.

• Satisfaction. In this context, it represents the global users' satisfaction according to the first two axes.

The figure shows that the less the amount of shared information is, the most the privacy satisfaction is. However, that implies a low reputation satisfaction range. Obviously, both dimensions have an antinomic impact. Nevertheless, we can infer that the same global satisfaction can be reached by using different settings, which depend on the applicative context requirements.

Finally, the main aim of our study is to find a method to obtain the right settings in order to maximize the user' trust towards the system. The latter could be reach by finding the best tradeoff between all the proposed dimensions that leads to the point located as far as possible on the right of the satisfaction axis.

CONCLUSION AND OPEN ISSUES

Social networks actually take an important place in our everyday life. However, most of social systems do not take into account user's trust as an aim. In our works, we propose to increase the users' trust towards the system by designing some methods to raise the aforementioned aim in terms of reputation, privacy and satisfaction. In our opinion, these three dimensions are hardly linked and have to be studied in a correlated way.

Nevertheless, it is obvious that user's trust is not only linked to reputation, satisfaction and privacy, but our work consists in a first step and we have make the choice to start with this focus. Moreover, each of these dimensions has to be handled more generally than the preliminary examples presented in this position paper (quantity of shared information, efficiency of reputation system, and so forth).

There is numerous open questions, for example, to identify the common and the incompatible properties of the three dimensions, but also, to define generic metrics that takes into account these dimensions and helps the designer to maximize the users' trust towards the system while respecting the system and/or application constrains.

Figure 1 :

 1 Figure 1: Relationship among the identified dimensions.

Figure 2 :

 2 Figure 2: Spatial representation of our 3-facet characterization and mutual impact of the two main settable aspects on global satisfaction.

This attraction can be viewed from different points of view, e.g., users who want to communicate with their friends, or commercial entities who are interested in data for business issues.

Privacy breaks can be due to specific malicious users or to the system itself. They should not be treated in the same manner and should not imply the same consequences.