Roy Michael

Sebti Foufou

Andreas Koschan

Frederic Truchetet

Mongi Abidi

Frederic Truchetet

Mongi Abidi Multiresolution

Michaël Roy
email: m.roy@iutlecreusot.u-bourgogne.fr

Frédéric Truchetet

Multiresolution Analysis for Irregular Meshes

Keywords: Irregular mesh, multiresolution analysis, surface relaxation, surface attributes

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

3D scanners usually produce large amount of raw data containing geometrical data and attributes. Geometrical data describe shape and dimensions of the object and include data relative to a point set on the object surface. Attributes describe object surface properties such as colors, texture coordinates, temperature, etc. The goal of this work is to build a mesh multiresolution analysis that is capable of managing geometrical data and attributes. The attribute management is very important especially for terrain models where the attributes are linked to the nature of the terrain. In some cases, attributes are more important than the terrain itself. For example, weather data sets contain several attributes (e.g. temperature, pressure, humidity, precipitation, etc.) in addition to the terrain (i.e. latitude, longitude and elevation of the weather stations recording the data). User-friendly visualization of these kinds of data sets requires management of the attributes. [START_REF] Walter | Attribute preserving dataset simplification[END_REF] Multiresolution analysis 2 is an efficient framework to represent a data set at different levels of resolution. The analysis decomposes an initial data set into a sequence of approximations and details. The approximations represent the initial data at different levels of resolution. The details encode the data lost by the approximations and can be seen as a frequency spectrum. The main advantage of the multiresolution analysis is its representational and computational efficicency. Multiresolution analysis is a versatile tool to represent general functions and data sets, and gives rise to many applications such as filtering, denoising, compression, editing, etc.

We propose a multiresolution analysis framework for irregular meshes containing multiple attributes (such as colors, texture, curvature, etc.). This framework is based on a popular simplification method called progressive mesh. We use a global downsampling method in order to create disjoint levels of resolution. A fast, local surface relaxation operator is introduced to build a non-uniform subdivision. We show different applications of the multiresolution analysis such as filtering, denoising and simplification of complex models.

In section 1.1, we review mesh multiresolution analysis schemes proposed in the literature. In section 2, we present a new surface relaxation operator and its extension to attribute relaxation. In section 3, we detail the multiresolution analysis scheme. Section 4 presents some experimental results. Conclusion and ideas for future works are given in section 5.

Related Work

Multiresolution analyses based on wavelet theory have started a new research domain on hierarchical methods for computer graphics. [START_REF] Stollnitz | Wavelets for Computer Graphics: Theory and Applications[END_REF] Lounsbery 4 made the connection between wavelets and subdivision to define different levels of resolution. This technique called Subdivision Wavelet Transform makes use of the theory of the multiresolution analysis and of the subdivision rules to construct a multiresolution surface representation for surface with subdivision connectivity. Zorin et al. [START_REF] Zorin | Interactive multiresolution mesh editing[END_REF] proposed a combination of subdivision and smoothing algorithms to construct a set of algorithms for interactive multiresolution editing of complex meshes with arbitrary topology. The authors used Loop subdivision for the estimation of the high resolution mesh from the coarse representation.

Those methods assume that the mesh is semi-regular and use traditional subdivision schemes. More recently, different approaches have been presented in order to deal with irregular meshes. Bonneau 6 introduced the concept of multiresolution analysis over non-nested spaces, which are generated by the so-called BLaC-wavelets, a combination of the Haar function with the linear B-Spline function. This concept was then used to contruct a multiresolution analysis over irregular meshes. Kobbelt et al. [START_REF] Kobbelt | Interactive multi-resolution modeling on arbitrary meshes[END_REF] proposed a multiresolution editing tool for irregular meshes using the discrete fairing method. The authors use the progressive mesh algorithm 8 to build the coarse resolution mesh. A smoothing operator is used to estimate the high resolution mesh. Guskov et al. [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF] presented a series of non-uniform signal processing algorithms designed for irregular triangulation. They used a smoothing algorithm combined with existing hierarchical methods to build subdivision, pyramid, and wavelet algorithms for irregular connectivity meshes. The authors proposed a non-uniform subdivision to build a geometrically smooth mesh with the same connectivity as the original mesh. This subdivision is part of the multiresolution decomposition and its central ingredient is a non-uniform relaxation operator.

Contributions

In this paper, we present a multiresolution analysis framework for irregular meshes containing attributes. Our framework build a mesh pyramid using a simplification and a non-uniform subdivision algorithm. We make the following contributions:

• We present a new surface relaxation operator used for geometric smoothing of triangle meshes. Our scheme is fast, local, and straigtforward to implement.

• We generalize this relaxation operator to surface attributes to build a complete multiresolution analysis.

• We show how to use the multiresolution analysis for irregular meshes in applications such as filtering, smoothing, and adaptive simplification.

SURFACE RELAXATION

Surface relaxation moves the vertices of a mesh in order to minimize an energy function. Surface relaxation has been heavily applied for surface smoothing using a diffusion process. [START_REF] Taubin | A signal processing approach to fair surface design[END_REF][START_REF] Kobbelt | Discrete fairing[END_REF][START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF] The relaxation operator minimizes the curvature of the mesh and generates a smooth mesh. We use a relaxation operator to build a non-uniform subdivision scheme and create smooth estimation of a fine mesh.

Geometric Relaxation

Guskov et al. [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF] proposed a non-uniform relaxation operator which minimizes second order differences D 2 e defined at every edge e in the mesh. [START_REF] Guskov | Multivariate subdivision schemes and divided differences[END_REF] Later we refer to this method as the SOD relaxation. Considering the position p i = {x, y, z} of a vertex v i , the relaxed position Rp i of v i is chosen to minimize the sum of the squares of the second order differences within the support of the vertex v i :

Rp i = j∈V2(i) λ i,j .p j with λ i,j = - e,j c e,i .c e,j e c 2 e,i , (1)
where V 2 (i) represents the 1-ring neighborhood with flaps of the vertex v i (see Fig. 1). The λ i,j are weights of the relaxation operator minimizing the second order differences D 2 e for an edge e. The c e,i are a set of coefficients depending on the geometric position of the mesh vertices. [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF] The computation of the coefficients c e,i requires a local parametrization, known as a hinge map, for every edge in the local neighborhood.

p j Rp i p i (a) SOD relaxation p j α i,j Rp i p i β i,j (b)
Meyer et al. [START_REF] Meyer | Discrete differential-geometry operators for triangulated 2manifolds[END_REF] proposed local and accurate discrete differential-geometry operators. One of these operators was previously used for surface denoising. [START_REF] Desbrun | Implicit fairing of irregular meshes using diffusion and curvature flow[END_REF][START_REF] Schneider | Geometric fairing of irregular meshes for freeform surface design[END_REF] It has been shown 16 that this operator gives similar smoothing results to the SOD relaxation operator presented before. The advantage of these two methods is that they smooth the geometry and do not affect the triangle shapes much. We propose a relaxation operator based on surface curvature minimization. We build our non-uniform relaxation operator using the Meyer differential operator. We refer to the following method as the curvature relaxation. The relaxed position Rp i of a vertex v i is given by:

Rp i = j∈V1(i) λ i,j .p j with λ i,j = cot α i,j + cot β i,j l∈V1(i) cot α i,l + cot β i,l , (2)
where V 1 (i) represents the 1-ring neighborhood. The λ i,j are weights of the relaxation operator minimizing the curvature energy of an edge e i,j where α i,j and β i,j are the angles opposite to the edge e i,j (see Fig. 1).

SOD relaxation operator requires to compute one function for every vertex in the 2-ring neighborhood, and to parametrize every edge in the 1-ring neighborhood. It can be shown that the complexity of the SOD relaxation operator is O(4n) where n is the number of vertices in the 1-ring neighborhood. Curvature relaxation operator requires to compute only one function for every vertex in the 1-ring neighborhood. Therefore, it can be shown that the complexity of the curvature relaxation operator is O(n). Table 1 shows the computation time for the SOD relaxation and the curvature relaxation operators applied to different models. This experiment was performed on a PC with a Pentium 4 at 2.4GHz and with 512MB of memory. The SOD relaxation operator works at about 25,000 vertices per second, while the curvature relaxation operator works at about 100,000 vertices per second. SOD relaxation operator is slowed down by the extended neighborhood requirement and the local parametrization computed for each edge in the local neighborhood. Figure 2 shows the effect of surface relaxation on a non-planar triangulation such as the eye of the mannequin head (Fig. 2(a)). Semi-uniform schemes like the discrete Laplacian (Fig. 2(b)) relaxe a vertex by replacing the vertex with the average of its 1-ring neighbors. The semi-uniform scheme tries to make edge lengths as uniform as possible, which leads to undesired tangential drifts, generating triangles of similar sizes. Non-uniform shemes (Figs. 2(c)-2(d)) smooth the geometry without affecting the triangle shapes much. We see that the two methods shown gives similar visual results.

Attribute Relaxation

Meshes coming from real world scenes usually contain attributes such as colors, texture coordinates, temperature, radiation, etc. We assume that the attributes are intrisincally linked to the surface. We want to extend the previous relaxation operator to include the attributes. The basic idea is to relax the attributes according the surface geometry.

A vertex v is now represented as a set (a 1 , . . . , a N ) of N attributes a n . We define an application f n (v) = a n that gives the n th attribute a n associated with the vertex v. The geometrical position of the vertex is then simply defined as an attribute of that vertex. We generalize the previous relaxation operator to an attribute a n as follows:

Rf n (v i ) = j∈V1(i) λ i,j .f n (v j ), (3)
where the λ i,j are defined as in Equation 2, and only depends on the geometry of the surface. Predicted attributes are relaxed in terms of curvature energy of the analysed surface. Thus, this relaxation operator guaranties smooth attribute variation.

Figure 3 shows the relaxation of color attributes on the swirl model * (Fig. 3(a)). This model is a part of a regular sphere, so the curvature is constant and so are the λ i,j coefficients of the relaxation formula. Figure 3 (b) shows the result after 1 iteration of the relaxation operator, and Fig. 3(c) shows the result after 20 iterations. We see that the color values are uniformly smoothed following the surface curvature.

MULTIRESOLUTION ANALYSIS

Multiresolution analysis provides a framework that rigorously defines various approximations and fast analysis algorithms. This framework decomposes an original data set into a sequence of levels of resolution. We use a decomposition scheme based on the Burt-Adelson pyramid [START_REF] Burt | The laplacian pyramid as a compact image code[END_REF] and allows the creation of mesh pyramid. [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF] We start from the finest mesh M 0 and compute a sequence of meshes M k (1 ≤ k ≤ K) as well as oversampled differences D k between meshes. A level of resolution is defined by a couple (M k , D k ), except for the finest level which is M 0 . To go from M k to M k+1 , we follow the diagram in Fig. 4. The decomposition of one level of resolution is decomposed in three steps:

Subdivision Simplification M k M k+1 D k+1 S k
• Simplification. The simplification downsamples the initial mesh M k by removing some vertices, giving the coarse mesh M k+1 . The coarse mesh M k+1 is an approximation of the initial fine mesh M k .

• Subdivision. The subdivision upsamples the coarse mesh M k+1 by inserting the previously removed vertices, and relaxes all the vertices, giving an estimation S k of the fine mesh.

• Detail computation. The difference between the fine mesh M k and the subdivided mesh S k gives the detail coefficients D k+1 associated with the mesh M k+1 . The details are computed for every vertex of the fine mesh M k .

To construct the mesh pyramid, we need downsampling, upsampling, and relaxation operators. The reconstruction scheme is simply obtained by inverting the decomposition scheme. We start with a coarse mesh M k+1 , subdivide it and add the details D k+1 in order to recover the fine mesh M k .

In this section, we explain the global downsampling and upsampling methods used respectively in the simplification and in the subdivision. Then we detail the decomposition algorithm that creates the levels of resolution, and the reconstruction algorithm used to recover the initial fine data set.

Global Downsampling and Upsampling

The decomposition is based on an incremental mesh decimation, where the basic step consists of removing one vertex and of re-triangulating the remaining hole. Since our decomposition should be invertible, however, we have to choose a decimation method that is also invertible. An invertible mesh decimation method was introduced in the Progressive Mesh (PM) framework. [START_REF] Hoppe | Progressive meshes[END_REF] In the PM setting, a sequence of edge collapses simplifies the mesh, while a sequence of vertex splits recovers the initial mesh. In our framework, an half-edge collapse provides the atomic downsampling step, and a * http://graphics.cs.uiuc.edu/∼garland/research/quadrics.html vertex split becomes the atomic upsampling step. We prefer half-edge collapse operation because it does not introduce new vertex positions but rather sub-samples the original mesh. [START_REF] Kobbelt | A general framework for mesh decimation[END_REF] Thus, it enables the construction of nested hierarchies on unstructured meshes that can facilitate further applications. [START_REF] Wu | Fast mesh decimation by multiple-choice techniques[END_REF] The central ingredient of our framework is the global downsampling that removes an independent set of vertices (i.e. vertices which are not connected by an edge) per level of detail. This technique was presented by Kobbelt 7 in order to achieve optimal performance with his multi-level smoothing algorithm. Our global downsampling method selects an independent set of vertices, labled odd vertices, to be removed by a sequence of half-edge The inverse operation (i.e. global upsampling) required for the recontruction operation re-inserts the previously removed vertices to create a mesh topologically identical to the initial one. The original PM framework always reconstructs the original mesh. In order to generate a smooth approximation of the original mesh, we split each step of the PM refinement into a topological operation (vertex insertion) and a geometric operation which places the re-inserted vertices at their original position. In our subdivision scheme, the geometric operation is performed by the relaxation operator presented in section 2 to create a smooth approximation of the fine mesh.

Different methods can be used to select the odd vertices, and thus the half-edge collapses to perform. Our algorithm performs an incremental selection by selecting one odd vertex and locking all adjacent vertices, labled even vertices. The selection ends when no more vertices can be selected. By selecting an odd vertex in order to remove it, we also select the even vertex it will merge with. In other words, we directly select an half-edge collapse. The selection of the odd vertices can be done with different methods. We choose the Quadric Error Metric from Garland et al. [START_REF] Garland | Surface simplification using quadric error metrics[END_REF] because it minimizes the length of the details and retains the visual appearance of the simplified mesh.

Decomposition

The decomposition creates a sequence of levels of resolution, where each of them is composed by an approximation mesh and a set of details associated to the vertices. The creation of one level of resolution requires two major steps: simplification and subdivision. The simplification creates the coarse mesh according to the initial mesh. The subdivision approximates the fine mesh according to the coarse mesh. The details are given as the difference between the initial and the approximated fine mesh. The creation of a level of resolution for a mesh can be broken down into four steps:

• Select odd vertices. Starting from a fine mesh M k , a set vertices, odd vertices, is selected to be removed. The remaining vertices composing the coarse mesh are the even vertices. The selection of the odd vertices is done using a global downsampling method discribed before.

• Relax vertices. The vertices of the mesh are relaxed to create a smooth approximation of the fine mesh. All the attributes a n of every vertices are relaxed:

∀v k i ∈ M k , Rf n (v k i ) = j∈V1(i) λ k i,j .f n (v k j ) with n ∈ [1, N ], (4)
where the λ i,j are defined in Equation 2, and are stored for the reconstruction. The attributes of every vertex v k i are relaxed according the surface geometry represented by the λ i,j coefficients.

• Compute details. We compute the details needed for the reconstruction. The details are given by the difference between the relaxed and the original vertices:

∀v k i ∈ M k , d k+1 n (v k i ) = f n (v k i ) -Rf n (v k i ) with n ∈ [1, N ], (5)
where d k+1 n (v k i ) represents the detail of the attribute a n of the vertex v k i . The details are computed for the N attributes of every vertex v k i . We note

d k+1 (v k i ) the set {d k+1 n (v k i )} of details of the attributes of the vertex v k i , with n ∈ [1, N ].
And we note D k+1 the set {d k+1 (v k i )} of details for every vertex. • Remove odd vertices. Finally, the odd vertices are removed by a sequence of half-edge collapses to create a coarse approximation M k of the initial mesh M k .

Note that the details are computed for the odd and the even vertices. This leads to an overrepresentation of the fine mesh (i.e. an optimal representation would compute the details only for the removed vertices). Starting from a fine mesh M k , the coarse level of resolution is given by the couple (M k+1 , D k+1 ).

Reconstruction

The reconstruction is simply the reverse operation of the decomposition. A fine mesh is created using a coarse mesh and the details attached to it. Attributes of one vertex v k i of the fine mesh M k are reconstructed by relaxing the attributes using the λ i,j coefficients computed during the decomposition, and by adding the details of the coarse level. The reconstruction of a fine level of resolution can be broken down into three steps:

• Insert odd vertices. First the odd vertices are re-inserted using vertex splits into the coarse mesh M k+1 so that the new mesh M k has exactly the same topology as the initial fine mesh M k .

• Reconstruct odd vertices. The newly re-inserted vertices are reconstructed using the following reconstuction formula for the odd vertices:

f n ( v i k ) = j∈V1(i) λ k i,j .f n (v k+1 j ) + d k+1 n (v k i ) with n ∈ [1, N ]. (6)
The reconstruction of the odd vertices creates an intermediate mesh M k where the even vertices are the vertices of the coarser mesh M k+1 and the odd vertices have been recontructed according to the even vertices.

• Reconstruct even vertices. Finally the even vertices are reconstructed from the vertices v j k of the intermediate mesh M k using the following reconstruction formula:

f n (v k i ) = j∈V1(i) λ k i,j .f n ( v j k ) + d k+1 n (v k i ) with n ∈ [1, N ]. (7)
The even vertices of the fine mesh M k are recontructed according to the vertices of the approximate fine mesh M k .

APPLICATIONS

In this section, we present different applications of the multiresolution analysis of irregular meshes. Geometric applications are presented, such as filtering and denoising. Applications involving attribute management are shown, such as adaptive simplification.

Filtering

We can apply some signal processing filters to a multiresolution model. Figure 5 shows three different filters applied on the Venus model † (Fig. 5(a)). Low pass filtering (Fig. 5(b)) is performed by setting to zero all the details of the 6 finest levels. We see that the low pass filter achieves a smooth result, as expected. Stopband filtering (Fig. 5(c)) is performed by setting to zero all the details from level 6 to level 9. We see that intermediate details are removed, while fine details are preserved. Enhancement filtering (Fig. 5(d)) is performed by multiplying by two all the details from level 6 to level 9. We see that mid-level details are emphazised. These results are similar to those presented in Daubechies' work. 21

Denoising by Soft Thresholding

In this section we extend the concept of soft-thresholding to 3D meshes. Wavelet shrinkage is a popular method used to denoise data. The idea is to transform the data into the wavelet basis, where the large coefficients are mainly the signal, and smaller ones represent the noise. By suitably modifying these coefficients, the noise can be removed from the data.

It is important to understand the wavelet shrinkage methods as a denoising algorithm and not as a smoothing algorithm. Denoising attempts to remove whatever noise is present and to retain whatever signal is present regardless of the frequency content, while smoothing removes high frequencies and retains low frequencies. [START_REF] Taswell | The what, how, and why of wavelet shrinkage denoising[END_REF] The soft thresholding method [START_REF] Donoho | De-noising by soft-thresholding[END_REF][START_REF] Fodor | Denoising through wavelet shrinkage: an empirical study[END_REF] has proved its efficiency and its robustness for denoising appplications. In the setting of multiresolution analysis of irregular meshes, geometric details d are represented by a vector in 3D. Therefore, the soft thresholding rule has to be adapted to 3D vectors, but the principle remains the same. The operator nulls all values of d for which d ≤ λ and shrinks the vector d toward the origin by an amount of λ if d > λ. Given threshold λ for data d in 3D space, the soft thresholding is defined by:

δ λ (d) = 0, d ≤ λ d -d d .λ, d > λ . (8)
Figure 6 shows results of denoising the Jared model 6(a). This model was acquired with a RIEGL LMS-Z210 timeof-flight laser range scanner mounted on a van. The noise comes from the vibrations of the van and the limited accuracy of the scanner. This model was denoised using the soft thresholding on the five finest levels of details (Fig. 6(b)). Notice that the model is nicely smoothed, while keeping important geometrical features such as sharp edges. Soft thresholding is a fast, efficient denoising method and gives good results. Moreover, our methods requires only one pass over the model.

Adaptive simplication

Our decomposition method creates a mesh pyramid, and so a hierarchy of meshes at different levels of resolution. Bonneau 6 discussed the advantages of threshold reconstruction against level reconstruction. Level reconstruction results from applying the reconstruction algorithm (section 3.3) up to a certain level. Threshold reconstruction inserts vertices in the mesh according to the length of their details. Only vertices with a detail length superior to a given threshold will be inserted into the reconstructed mesh. Moreover our method used the PM framework which has proved its efficiency for view-dependent and adaptive visualization of irregular meshes. [START_REF] Hoppe | View-dependent refinement of progressive meshes[END_REF] An adaptative reconstruction (and thus simplification) of a multiresolution mesh can be done as follows:

• Sort the list of removed vertices according to the length of their details for each type of detail.

• Reconstruct a new mesh by inserting vertices with detail length superior to a given threshold.

To avoid the construction of a degenerate mesh, for each vertex inserted we have to also insert the vertices to which the newly inserted vertex depends on in the coarser levels. The reconstruction can be guided by the user in case of the presence of several attributes. The user can specify only one type of attribute to be taken in account for the reconstruction (geometrical attributes should always be considered). (b), where the color attributes have been considered for the reconstruction. The threshold can be fixed manually or it can be fixed interactively in case of visualization. The threshold changed according to given criteria (such as framerate, visibility).

CONCLUSION AND FUTURE WORK

We have presented a new multiresolution analysis for irregular meshes with multiple attributes. We have presented a fast, local surface relaxation operator, and shown how to extend this operator to the attributes. A complete multiresolution analysis framework has been detailed. We introduced denoising through soft thresholding for irregular meshes. This method requires only one pass over the model, and keeps important features such as sharp edges. Results show the efficiency of our framework through a number of applications including filtering, denoising, and adaptive simplification. Future works will address feature detection and adaptive visualization of complex models.

Figure 2 .Figure 3 .

 23 Figure 2. Smoothing of the eye of the mannequin (a) using different relaxation operators. The semi-uniform scheme (b) smoothes the surface but distorts the geometry. Non-uniform schemes (c)-(d) only smooth the geometry and preserve triangle shapes.

Figure 4 .

 4 Figure 4. Mesh multiresolution analysis scheme using Burt-Adelson like pyramid.

  Given a threshold λ for monodimensional data d, the rule δ λ (d) = sgn(d) max(0, |d|λ) defines soft thresholding, the operator δ λ nulls all values of d for which |d| ≤ λ and shrinks toward the origin by an amount of λ all values for which |d| > λ.

  (a) Initial model. (b) Low pass filter. (c) Stopband filter. (d) Enhancement filter.

Figure 5 .

 5 Figure 5. Filtering of the Venus head.

Figure 6 (

 6 Figure 6(c) shows the simplified version of the model in Fig.6(b), where the color attributes have been considered for the reconstruction. The threshold can be fixed manually or it can be fixed interactively in case of visualization. The threshold changed according to given criteria (such as framerate, visibility).

Curvature relaxation Figure 1. Relaxation

		buddha	bunny	dragon	horse
	Vertices Faces SOD relaxation Curvature relaxation	543,652 1,087,716 69,451 871,414 96,966 35,947 437,645 48,485 21.70s 1.49s 17.14s 1.91s 5.02s 0.40s 3.95s 0.41s

of a vertex pi. SOD relaxation requires an extended neighborhood and a local parametrization for every edge of the 1-ring neighborhood (the bold edges). Curvature relaxation is computed according to the angles opposite to the edge ei,j in the 1-ring neighborhood.

Table 1 .

 1 Computation time for SOD relaxation and curvature relaxation operators applied to different models from Stanford University.

† http://www.cyberware.com/samples

ACKNOWLEDGMENTS

This work was supported by the University Research Program in Robotics under grant DOE-DE-FG02-86NE37968, by the DOD/TACOM/NAC/ARC Program, R01-1344-18, and by FAA/NSSA Program, R01-1344-48/49. The authors would like to thank Yohan Fougerolle for his helpful comments, and Brad Grinstead for the Jared model.


Michaël Roy

Sebti Foufou

Frédéric Truchetet

MULTIRESOLUTION ANALYSIS FOR IRREGULAR MESHES WITH APPEARANCE ATTRIBUTES

Keywords: multiresolution analysis, irregular meshes, appearance attributes, adaptive visualization

We present a new multiresolution analysis framework based on the lifting scheme for irregular meshes with attributes. We introduce a surface prediction operator to compute the detail coefficients for the geometry and the attributes of the model. Attribute analysis gives appearance information to complete the geometrical analysis of the model.We present an application to adaptive visualization and some experimental results to show the efficiency of our framework.

INTRODUCTION

3D scanners usually produce huge data sets containing geometrical and appearance attributes. Geometrical attributes describe shape and dimensions of the object and include data relative to a point set on the object surface. Appearance attributes describe object surface properties such as colors, texture coordinates, etc.

Multiresolution analysis is an efficient framework to represent a data set at different levels of detail, and to provide frequency information. It gives rise to many applications such as filtering, denoising, compression, editing, etc. Many papers present the multiresolution analysis and the wavelet transform in computer graphics domain. Here we refer to [START_REF] Stollnitz | Wavelets for Computer Graphics: Theory and Applications[END_REF] as an introduction.

The goal of this work is to build a multiresolution mesh analysis managing both geometric and appearance attributes. Attribute management is very important especially for terrain models where the attributes are linked to the nature of the terrain. In some cases, attributes are more important than the terrain itself. The main contributions of this work are the use of the lifting scheme for the multiresolution analysis of irregular meshes with attributes, and the application of the proposed multiresolution framework to detail coefficient dependent visualization of meshes.

In section 2, we review multiresolution mesh analysis schemes proposed in the literature. In section 3, we detail the proposed multiresolution analysis framework. Section 4 presents some experimental results and the application of the proposed method to detail-dependent visualization. Conclusion and ideas for future extensions are given in section 5.

2.

Related Work [START_REF] Lounsbery | Multiresolution analysis for surfaces of arbitrary topological type[END_REF] made the connection between wavelets and subdivision to define different levels of resolution. This technique makes use of the theory of multiresolution analysis and of the subdivision rules to construct a multiresolution representation for surfaces with subdivision connectivity. [START_REF] Zorin | Interactive multiresolution mesh editing[END_REF] proposed a combination of subdivision and smoothing algorithms to construct a set of algorithms for interactive multiresolution editing of complex meshes with arbitrary topology. [START_REF] Bonneau | Multiresolution analysis on irregular surface meshes[END_REF] introduced the concept of multiresolution analysis over non-nested spaces, which are generated by the so-called BLaC-wavelets. This concept was then used to contruct a multiresolution analysis over irregular meshes. [START_REF] Kobbelt | Interactive multi-resolution modeling on arbitrary meshes[END_REF] proposed a multiresolution editing tool for irregular meshes using the progressive mesh algorithm [START_REF] Hoppe | Progressive meshes[END_REF] to build the coarse resolution mesh, and a smoothing operator to estimate the high resolution mesh. [START_REF] Guskov | Multiresolution signal processing for meshes[END_REF] presented a series of non-uniform signal processing algorithms designed for irregular triangulation, a smoothing algorithm combined with existing hierarchical methods is used to build subdivision, pyramid, and wavelet algorithms for meshes with irregular connectivity. Recently, [START_REF] Valette | Wavelet-based multiresolution analysis of irregular surface meshes[END_REF] presented a new wavelet-based multiresolution analysis of irregular surface meshes using a new irregular subdivision scheme. The method is a fine-to-coarse decomposition, and use a complex simplification algorithm in order to define surface patches suitable for their irregular subdivision scheme.

MULTIRESOLUTION ANALYSIS

Multiresolution analysis provides a framework that rigorously defines various approximations and fast analysis algorithms. This framework constructs iteratively approximation and detail parts forming successive levels of resolution of the original data set. The details capture the local frequency content of the data set, and are used to exactly reconstruct the original data set.

Classical multiresolution analysis frameworks (such as wavelet transform) cannot be applied to irregularly sampled data sets. Sweldens, 1998 proposed the lifting scheme that allows the multiresolution analysis of irregular samples.

We propose a multiresolution analysis framework suitable for triangular irregular meshes with appearance attributes. This framework decomposes a mesh in a series of levels of detail, and computes detail coefficients at each level.

Split

Predict Predict Merge

M k M k M k-1 odd k-1 even k-1 odd k-1 even k-1 D k-1 Figure 1.
Multiresolution mesh analysis framework.

The multiresolution mesh analysis framework is presented in Fig. 1. The decomposition is represented on the left part of the figure. Starting from a fine mesh M k , two groups of vertices (odds and evens) are defined by the split operator. The odd vertices are designated to be removed, and the even vertices remain to create the coarse mesh M k-1 that approximates the inital mesh. The odd vertices are predicted using the predict operator, and then substracted to the original odd vertices to give the detail coefficients D k-1 . The last step is the removal of the odd vertices from the initial mesh using a downsampling operator. The reconstruction is shown on the right part of the figure and is simply the inverse scheme. Starting from a coarse mesh M k-1 , the odd vertices are re-inserted using an upsampling operator. The odd vertices are predicted using the predict operator, and then exactly reconstructed by adding the detail coefficients D k-1 . In the following paragraphs, we detail the different steps required to build the multiresolution mesh analysis framework.

Downsampling and Upsampling

We employ the Progressive Mesh (PM) framework [START_REF] Hoppe | Progressive meshes[END_REF] to build downsampling and upsampling operators. In the PM setting an edge collapse provides the atomic downsampling step, and a vertex split becomes the atomic upsampling step. For the downsampling, we use the half-edge collapse operation, which does not introduce a new vertex position but rather subsamples the original mesh. Thus, it enables the contruction of nested hierarchies on unstructured meshes that can facilitate further applications. The downsampling operator removes about 33% of the vertices per level.

Split and Merge

The split operator takes a given mesh and selects the even and the odd vertices. The later are designated to be removed using half-edge collapse operations. In order to do global downsampling and upsampling, the odd vertices are defined as a set of independent vertices (not directly connected by an edge). Different methods can be used to select the odd vertices, and thus the half-edge collapses to perform. Our algorithm performs an incremental selection by selecting one odd vertex and locking all adjacent vertices (even vertices). The selection ends when no more vertices can be selected. By selecting an odd vertex in order to remove it, we also select the even vertex it will merge with. In other words, we directly select a half-edge collapse. The Quadric Error Metric from Garland and Heckbert, 1997 is used as a criterion for the selection of the odd vertices because it minimizes the length of the details and retains the visual appearance of the simplified mesh. Since the upsampling is completly done with vertex split operations, the merge operator is not required.

Predict

The predict operator estimates the odd vertices using the even vertices. We propose a prediction operator that uses the local surface geometry. Meshes coming from real world scenes usually contain appearance attributes such as colors, texture coordinates, etc. Also, we consider the vertex position and the normal vector as geometric attributes. Attributes are considered as vectors in Euclidian space defined on each vertex of the mesh. So a vertex is represented as an array composed of m attribute vectors (a 1 , . . . , a m ) where each a n is an attribute vector. We define an application f n (v) = a n that gives the attribute vector a n of the attribute n associated with the vertex v. Our predicition operator estimates each odd vertex v k i from the mesh M k as a set of attributes f n (v k i ) given by :

f n (v k i ) = j∈V k 1 (i) w k i,j .f n (v k j ).
(1)

V k 1 (i) represents the one-ring neighborhood of the vertex v k i . The w i,j are weights of the relaxation operator minimizing the curvature energy of an edge e i,j [START_REF] Meyer | Discrete differential-geometry operators for triangulated 2-manifolds[END_REF] :

w k i,j = cot α i,j + cot β i,j l∈V k 1 (i) cot α i,l + cot β i,l , (2)
where α i,j and β i,j are the angles opposite to the edge e i,j . Predicted attributes are relaxed in terms of curvature energy of the analysed surface. This relaxation operator guaranties smooth variation of the attributes. This method also assumes that the attributes are linked to the surface. The w i,j coefficients are computed during the decomposition, and need to be stored to be re-used for the prediction step in the reconstruction.

EXPERIMENTAL RESULTS

We present an application of our multiresolution framework to adaptive visualization. Our method uses the PM framework, which has proved its efficiency for view-dependent visualization of meshes [START_REF] Hoppe | View-dependent refinement of progressive meshes[END_REF]. The PM framework selects the vertices to display using visiblity criteria. We improve this selection using the detail coefficients of the analysis. If the detail coefficient length of a vertex is below a given threshold, the vertex is declared as irrelevant and thus is removed from the mesh.

Figure 2 shows view-dependent visualization of the Buddha and the Earth model. On both Figures 2(a) and 2(b), the viewport used to visualize the models is shown as the yellow pyramid. We see that invisible vertices are removed using frustrum and backface culling. Irrelevant vertices are removed by thresholding the detail coefficients.

Figure 3 shows view and detail dependent visualization of the Buddha model using the viewport represented in Fig. 2(a). The original model, from Stanford University, contains 543.652 vertices and 1.087.716 faces. Figure 3(a) shows the model visualized using only frustrum and backface culling. Figures 3(b) and 3(c) show the Buddha model visualized with our detail dependent technique. Each figure shows the result of different values of the threshold (the higher the threshold, the coarser the resolution). We see that important geometrical features of the model such as the high curvature regions are preserved.

Figure 4(a) shows a model of the earth with color attributes. Figure 4(b) shows the same model simplified using our method. The detail coefficients of the color attributes are thresholded to remove irrelevant vertices. Detail dependent simplification insures the preservation of attribute features (e.g. the coastlines). The advantage of our method is that it allows more advanced visualization by computing the relevance of the vertices using the detail coefficients. Combinations of several attributes can be performed to improve the result of the simplification.

CONCLUSION AND FUTURE WORK

We have presented a new multiresolution analysis for irregular meshes based on the lifting scheme. Our framework manages attributes such as color, normals, etc. Our method is easy to implement and results show the efficiency of the analysis over the attributes, which allows more complete multiresolution analysis. The next step in this work will focus on feature detection using detail orientation in order to build a semi-automatic denoising algorithms for scanned models.

Figure 2 .

 2 Figure 2. View and detail dependent visualization of the Buddha model in (a) and the Earth model in (b). Both figures show the viewport used to visualize the models. Wireframe representation is overlaid on each model.

Figure 3 .

 3 Figure 3. Detail dependent visualization of the Buddha model in (a). Figures (b) and (c) show two different values of the detail threshold used to segment the geometric details.

Figure 4 .

 4 Figure 4. Adaptive visualization according to the color detail coefficients. Original model is shown in (a), and simplified model in (b). Relevant vertices are selected by thresholding the color detail coefficients. The model is a sphere with color representing the elevation of the earth from the ETOPO5 data set.


Mamoun Gharbi

Pierre-Vincent Paubel

Aurélie Clodic

Ophélie Carreras

Rachid Alami

Jean-Marie Cellier

Toward a better understanding of the communication cues involved in a human-robot object transfer

Handing-over objects to humans (or taking objects from them) is a key capability for a service robot. Humans are efficient and natural while performing this action and the purpose of the studies on this topic is to bring human-robot handovers to an acceptable, efficient and natural level.

This paper deals with the cues that allow to make a handover look as natural as possible, and more precisely we focus on where the robot should look while performing it. In this context we propose a user study, involving 33 volunteers, who judged video sequences where they see either a human or a robot giving them an object. They were presented with different sequences where the agents (robot or human) have different gaze behaviours, and were asked to give their feeling about the sequence naturalness. In addition to this subjective measure, the volunteers were equipped with an eye tracker which enabled us to have more accurate objective measures.

I. INTRODUCTION

Fetch and carry abilities form the building blocks of what a service robot is intended to do. To support these abilities, a number of developments have been achieved in the humanrobot interaction community, in terms handover location computation and task-oriented motion planning.

However, it appears that in front of a humanoid robot (with a head like a PR2), arm and base movement are not sufficient to achieve such tasks in a satisfying manner. We notice that people tend to anthropomorphize the robot and infer that the robot should use hand-eye coordination as humans do. This means that the robot should not only compute its arm movement but also a movement of its head. In this paper, we seek to find which head movement (or pattern of movements) should be added to robot arm movement to enable more natural interaction.

We focus on the way a robot should use its gaze cues (in our case head movement) to support a joint action involving robot arm movement. To achieve this goal, we conducted a multidisciplinary study involving psychologists and roboticists. We have chosen to study a simple task where a user (the giver) sets an object down on a table in the direction of another user (the receiver). Our study explores two cases for the giver: a human and a robot (Figure 1).

We have chosen to limit the study to a basic movement in order to concentrate on non-verbal cues that should be produced by the giver toward the receiver. 1 CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France name.surname@laas.fr 2 Univ de Toulouse, INSA, LAAS, F-31400 Toulouse, France 3 CLLE-LTC UMR 5263 UT2J-CNRS, Toulouse, France {pierre.paubel,carreras,cellier}@univ-tlse2.fr 4 Univ de Toulouse, LAAS, F-31400 Toulouse, France A brief analysis of this kind of gesture between two humans shows the significance of two variables to judge this feature:

• Speed of the gesture (more or less fast movements) and • Gaze direction of the giver toward the receiver Our task is not a handover but consists in setting down the object, and our aim is to find which "coordination smoothers" ( [START_REF] Vesper | A minimal architecture for joint action[END_REF], [START_REF] Becchio | Toward you the social side of actions[END_REF]) should be added to the robot motion to look more natural to the human it interacts with. Use of gaze cues have already been studied in HRI context [START_REF] Mutlu | Designing gaze behavior for humanlike robots[END_REF], [START_REF] Strabala | Towards seamless human-robot handovers[END_REF], [START_REF] Boucher | I reach faster when i see you look: gaze effects in human-human and human-robot face-to-face cooperation[END_REF], [START_REF] Staudte | Visual attention in spoken humanrobot interaction[END_REF], [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF] and this paper should be considered as complementary to these studies. We seek to confirm, in a controlled experimental context, results that have been already exhibited. In addition, what could be credited to our work is the study of gaze behaviour for both the giver (H or R) and the receiver during a give action. The closest studies in the field to our knowledge are [START_REF] Boucher | I reach faster when i see you look: gaze effects in human-human and human-robot face-to-face cooperation[END_REF] and [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF]. In the first one, authors do a similar study over a different action, while the second does not analyze the receiver gaze.

II. GENERAL HYPOTHESIS

Our first general hypothesis comes from our subjective experience: the movement will be considered as more natural if it includes the use of gaze cues, e.g. a robot with a fixed head will be considered less natural than one with a moving head. We have also considered the sequence of the gaze focus steps (the order in which object and receiver are looked at) to see if a specific pattern emerges, with a human or a robot giver.

Our second hypothesis is that gaze movement of the receiver will be directed toward the head and toward the object. We want to see here if the head and the object of a man or a robot giver are looked at in the same way.

Our third hypothesis is exploratory and concerns the effect of the movement speed with respect to the evaluation of its naturalness.

III. RELATED WORKS

There have been a number of contributions concerning motion generation for a humanoid robot and more specifically for its arm(s) in a human-robot interaction context.

A. Human-Aware Motion Generation

Sisbot et al. [START_REF] Sisbot | A human-aware manipulation planner[END_REF] presented a general motion generation framework for a manipulator robot to produce a robot behaviour that can be called social in the sense that it tends to respect social rules. This framework has been validated by a user study (Dehais et al. [START_REF] Dehais | Physiological and subjective evaluation of a human-robot object hand-over task[END_REF]) and has been extended in Mainprice et al. [START_REF] Mainprice | Sharing effort in planning human-robot handover tasks[END_REF] by taking into account, at handover motion planning level, how the human can participate to the task.

Cakmak et al. [START_REF] Cakmak | Human preferences for robot-human hand-over configurations[END_REF] focused on the choice of handover configuration by an evaluation of how humans would prefer being handed an object by a robot. They found that configurations learned from the human were preferred over planned configurations (even if these latter provide better reachability of the object). They concluded in saying that while a planning approach has the potential to produce configurations that are practical, it was insufficient in addressing usability, naturalness and appropriateness for the task.

Strabala et al. [START_REF] Strabala | Towards seamless human-robot handovers[END_REF] attempted to codify a procedure for seamless human-robot handovers through a handover structure. The authors proposed that the robot should be able to handle social norms and should be readable enough to enable the human to infer the what, when and where of the handovers (as it is proposed in a more general way for joint action by Sebanz and Knoblich [START_REF] Sebanz | Prediction in joint action: What, when, and where[END_REF]). They proposed e.g. a turn-taking pattern based on giver actions, face direction and gaze. They found that people could easily understand humanlike cues performed by a robot, and that they preferred these cues to machine-like ones. Among these cues, the gaze is an important one.

B. Gaze Management

Gaze analysis allows the receiver to make hypothesis on the cognitive activity handled by the giver, and a number of researchers tried to codify and implement this cues on robots.

Mutlu [START_REF] Mutlu | Designing gaze behavior for humanlike robots[END_REF] studied the use of social gaze cues in communication on several robotics platforms (ASIMO, Robovie and Geminoid) and showed the importance of gaze in such a context and that the use of well-defined gaze patterns could enhance human-robot communication experience.

Boucher et al [START_REF] Boucher | I reach faster when i see you look: gaze effects in human-human and human-robot face-to-face cooperation[END_REF] observed that one of the current roadblocks in the elaboration of smooth and natural human-robot cooperation is the coordination of robot gaze with the ongoing interaction and tried to identify pertinent gaze cues in human-robot cooperation. They found that humans could reliably exploit robot gaze to allow them to perform in an anticipatory manner in a cooperative task.

Interestingly, in a study oriented toward gaze cues in human-human interaction, Furlanetto et al. [START_REF] Furlanetto | Through your eyes: incongruence of gaze and action increases spontaneous perspective taking[END_REF] showed that eliminating gaze cues by blurring the actors face did not reduce perspective-taking, suggesting that in the absence of gaze information, observers rely entirely on the action. Intriguingly, perspective-taking was higher when gaze and action did not signal the same intention, suggesting that in presence of ambiguous behavioural intention, people are more likely to take the others perspective to try to understand the action.

Staudte et al. [START_REF] Staudte | Visual attention in spoken humanrobot interaction[END_REF] explore visual attention in spoken humanrobot interaction and found that robot gaze which was congruent with an uttered sentence helped human interlocutors to faster judge utterances than if robot gaze was absent (and on the other hand, when robot gaze was incongruent with the utterance, it slowed people down).

Moon et al. [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF] exploited human-like gaze cues during human-robot handovers and found on one side that subjects reached for the object significantly faster when the robot directed its gaze toward the intended handover location than when no gaze cues were used. On the other side, subjects tended to perceive handover as more natural when the robot provided turn-taking gaze.

This shows the importance of gaze in such task. However what this could mean? In fact, the robot would be able to achieve the task without gaze; it has only to control its arm. But this seems not enough.

C. About Joint Action

Let us try to situate this work in the global frame of joint action. Sebanz et al. [START_REF] Sebanz | Joint action: bodies and minds moving together[END_REF] proposed as a working definition: "joint action can be regarded as any form of social interaction whereby two or more individuals coordinate their actions in space and time to bring about a change in the environment". They propose that successful joint action depends on the abilities "(i) to share representations, (ii) to predict actions, and (iii) to integrate predicted effects of own and others actions".

Vesper et al. [START_REF] Vesper | A minimal architecture for joint action[END_REF] established that a minimal architecture for joint action should be able to handle, besides the goal, tasks representation (possibly shared), monitoring and prediction processes, what they call coordination smoothers. They argued that "where joint action requires precise coordination in time or space, there are often limits on how well X s actions can be predicted. One way to facilitate coordination is for an agent to modify her own behaviour in such a way as to make it easier for others to predict upcoming actions."

In the same direction, Becchio et al [START_REF] Becchio | Toward you the social side of actions[END_REF] showed that it is possible to differentiate the kinematics of an action performed by an agent acting in isolation from the kinematics of the very same action performed within a social context. They explain that social context shapes action planning and that, in the context of a social interaction, flexible online adjustments take place between partners.

We suggest that gaze cues could hold this role of coordination smoother in helping the human in front of the robot to better understand robot behaviour and help the robot to achieve its movement in a more natural way.

IV. MATERIALS AND METHODS

A. Participants

33 volunteers participated to the experiment (age range 22-38, M=27, SD = 3.5; 21 males, 12 females). There were not famliar to robots or to work with a robot. 15 watched human videos and 18 watched robot videos. All participants had normal uncorrected vision. Two volunteers have to be excluded from subsequent analyses due to a technical problem that damaged eye-tracking data (unreliable calibration).

B. Experimental Set-up

The experimental situation implies watching a video where a giver (Human or Robot), seated behind a table, takes the object with his right hand, and put it on the table so that the receiver, behind the video camera, can reach it. We use an experimental setup quite similar as the one of Staudte et al [START_REF] Staudte | Visual attention in spoken humanrobot interaction[END_REF]. This setup can be found not interactive enough (we will come back to this choice in section VII). In this study, we are trying to isolate gaze cues and movement velocity in order to find some hints about the use of these factors in our context. Moreover, it has been proposed by Kiesler [15] and Woods [START_REF] Woods | Comparing human robot interaction scenarios using live and video based methods: towards a novel methodological approach[END_REF] that video-based scenario can enable us to infer valuable results.

The experiment took place in a room where temperature and luminosity were kept constant. Participants faced a computer screen where the video was presented. Eye movements were recorded using an EyeLink 1000 remote eye tracker (SR Research Ltd., Mississauga, Ontario, Canada). This eye tracker possesses a spatial accuracy greater than 0.5 • and a 0.01 • spatial resolution. The sampling rate was set to 1000 Hz. The camera was placed at a distance of 20 cm from the screen and the eye-camera distance was 60 cm. We used a display screen DELL 19 with a refresh rate of 75 Hz and a resolution of 1024x768 pixels. A forehead rest was used to maintain these distances and to avoid heads movements. All eye tracking data were extracted using the SR Research default centroid algorithm. Simulation room enlightenment was maintained constant (19 lux).

In the experiment, we manipulated 3 variables: (1) the type of giver (Human or Robot), (2) the speed of the movement and (3) the gaze behaviour. The Robot was a PR2 and the Human was a white man (65 years old). Videos were shot to be as similar as possible (see figure 1). Three different speeds of the arm movement were presented: normal, rapid, and slow. Videos were accelerated and decelerated so that the movement remains relatively natural. The duration of the slow (3750 ms), normal (2250 ms), and rapid videos (1750 ms) were identical for the human and for the robot. Six different sequences were created for the gaze behaviour, their timelines are displayed figure 2: • O the giver looks only at the object, while the object is moving, the giver looks at the center of the object • R the giver looks only at the receiver • RO the giver looks at the receiver at the beginning, then when its arm (and the object in it) starts moving it starts to look at the object and stays on it till the end • ORO the giver looks at the object at the beginning, then when its arm is moving it starts to look at the receiver till the end of the motion. When the motion is over it looks at the object again till the end • OR the giver looks at the object at the beginning, then when its arm is moving it starts to look at the receiver and keeps this position till the end • ROR the giver looks at the receiver at the beginning, then, when its arm is moving (and the object in it) it starts to look at the object till the end of the motion.

When it is over it looks at the receiver again till the end.

The human moved only his eyes whereas the robot (PR2) moved its head to simulate a gaze. Imai and al. [START_REF] Imai | Robot mediated round table: Analysis of the effect of robot's gaze[END_REF] established that the perception of the robot gaze is coupled to the robots head orientation. Examples of those videos are available here http://homepages.laas.fr/magharbi/userstudy.html

C. Procedure

Participants were told that they had to evaluate a movement naturalness presented on a video. We made the choice, for methodological reasons, to use a very neutral formulation to not influence the judgment of the user. The same choice have been done concerning the question asked. It is one of the three that has been used in [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF], whereas in [START_REF] Boucher | I reach faster when i see you look: gaze effects in human-human and human-robot face-to-face cooperation[END_REF] there were no subjective evaluation.

Participants were familiarized with the situation by watching a first video, a bit different from the experimental ones. The experimental session was composed of 18 trials: 3 (speed) x 6 (gaze). In a trial, the participant pressed a button to begin the video. Immediately after the video, he/she rated the perceived naturalness of the movement on a 5 points Likert scale presented on the screen. Between trials, participants had to complete a digital logical suite, to break the dullness of the task. The order of trials was

D. Subjective measurement

To assess participants subjective experience, they had to rate perceived naturalness after each video, with a 5-point scale (5 for perfectly natural, 1 for not natural at all).

E. Oculometric measurement

Classical dependent variables in eye-tracking studies include the number and duration of fixations on areas of interest. In this study, the areas of interest (AOIs) were (1) the giver's face and (2) the object. Those AOIs were static, as depicted in figure 3. As video duration changed between experimental conditions, we computed the percentage of dwell time spent on AOIs to study the distribution of the visual attention.

F. Instructions

We considered that viewing the videos, the interpretation of the gesture objective was clear so no comments were done on that aspect to the participants. The instruction and the question were very neutral, in order to not influence the user judgement. They were only asked to rate the previous sequence naturalness as explained section IV-D. Note that the instruction and questions were written in the participant mother tongue (French)

V. RESULTS

We performed a mixed-design analysis of variance to examine the effects of (1) the gaze behaviour, (2) the speed movement, and (3) the type of giver on our subjective and oculometric dependent variables. Subjective and eye tracking data have been analysed with the software package Statistica 8.0 (Statsoft, Tulsa, Ok, USA).

A. Subjective measurements

Gaze Behaviour:

Results indicated a main effect of the gaze behaviour on the naturalness ratings, F(5, 145)=15.034, p<.001 (figure 4). Post-hoc paired comparisons showed that OR and ROR gaze behaviour are significantly judged more natural than the Movement speed: Results indicated a main effect of the movement speed on the naturalness ratings, F(2, 58)=10.354, p<.001. Fishers LSD post-hoc comparisons showed that the normal and the rapid speed movement conditions are judged more natural than the slow speed movement condition (highest p-value in the post hoc table equal to .004). No significant difference was found between the normal and the fast speed conditions (p=.16).

Type of giver (Human vs. Robot): Interestingly, there was no significant difference in the results between the two types of givers (F(1, 29)=1.988, p=.16). Moreover, no interaction was found between the three main manipulated factors. This result suggests that the effects of (1) movement speed and (2) gaze behaviour described above are not influenced by the type of giver (human or robot).

B. Eye tracking measurements

Distribution of the visual attention between the face of the giver and the object: Overall, results indicated a significant difference between the mean percentage of dwell time spent on the face of the giver and the mean percentage of dwell time spent on the object (F(1, 29)=59.848, p<.001). Participants tend to focus mainly their visual attention on the face of the giver.

The detailed analysis (see figure 5) showed an interaction between the type of giver and the gaze behaviour. Firstly, when the giver is a human, there is no effect of the giver gaze behaviour on the mean percentage of dwell time spent on the face of the giver (F(5, 65)=0.807, p=.54), nor on the mean percentage of dwell time spent on the object (F(5, 65)=1.004, p=.42). The main result here is that, when the giver is human, participants focus mainly their visual attention on the face of the giver to provide a judgement concerning the naturalness of the task, independently of the giver gaze behaviour. Secondly, when the giver is a Robot, results indicated a main effect of the gaze behaviour on the mean percentage of dwell time spent on the face of the giver (F(5, 80)=12,82, p=.001), and on the mean percentage of dwell time spent on the object (F(5, 80)=6.264, p=.001). Fishers LSD posthoc comparisons showed that participants focus more on the face of the robot for the three types of gaze behaviour ORO, OR and ROR than for the three others conditions R, O, RO (highest p-value in the post hoc table equal to .04). On the other hand, participants focus less on the object for the same three types of gaze behaviour ORO, OR and ROR than for the two others conditions R, O (highest p-value in the post hoc table equal to .05). However, gaze behaviours OR and ROR are not significantly different of the condition RO (lowest p-value equal to 0.26). If we take the human giver as a reference, the oculometric pattern with a robot giver is identical to the one of a human giver only for the ORO, OR and ROR conditions. Finally, no effect of the movement speed was found (F(2, 58)=1.798, p=.43), and the reader may find useful to know that there was no difference between the two blocks of video presentation (F(1, 29)=0.947, p=.33).

Pupil size: Results indicated a strong main effect of the type of giver on pupil size variations, with larger pupil diameters when the giver is a robot (F(1, 29)=12.803, p<.001). Results also revealed a main effect of the gaze behaviour (F(5, 145)=3.050, p<.001). However, post-hoc paired comparisons showed only one significant difference, with smaller pupil size in the OR gaze behaviour condition (highest p-value equal to .03 in the post hoc table). No effect of the movement speed was found (F(2, 58)=1.798, p=.17). Finally, results indicated a significant difference between the two blocks of video presentation (F(1, 29)=26.155, p<.001), with smaller pupil size during the last block, what could be reasonably considered as a training effect.

VI. DISCUSSION

The results presented in section V give a number of hints about humans preference in our setup.

A. First Hypothesis

Subjective measurement concerning gaze behaviour confirms that the behaviour seems more natural when the giver uses its gaze, more precisely OR (the giver looks at the Object then at the Receiver) and ROR (the giver looks at the Receiver then at the Object and then at the Receiver again). This first result strengthens our first hypothesis: when the giver does not send gaze cues (O case (the giver looks only at the Object), and R case (the giver looks only at the Receiver), the interaction lacks naturalness. However, gaze movements order seems to affect as well these results: ROR and OR are preferred to ORO (the giver looks at the Object then at the Receiver then at the Object again), which is preferred to RO. We observe a OR (Object then Receiver) pattern at the end of the movement that could be considered as an acknowledgement/turn-taking signal from the giver to the receiver. Note that the variable "type of giver (human or robot)" does not affect the subjective naturalness rating.

B. Second Hypothesis

Concerning the distribution of visual attention between the giver's face and the object, results are different according to the type of giver. When the giver is a human, there is no effect of the giver gaze behaviour on the distribution of the visual attention. The receiver focuses mainly his visual attention on the face of the human. We believe this behaviour is normal for humans as the face is the most expressive part of the body and humans are used to focus on the face to determine a number of features. When the giver is a robot, we can distinguish two cases: O, R and RO cases: The receiver visual attention is shared between the face and the object. That means, receiver will not focus either on the face or on the object but may go from one to the other. We interpret this as the receiver being lost in this kind of situations. Further analysis of eye tracking data is needed to validate this interpretation. ORO, OR and ROR cases: The visual attention is mainly focused on the head of the robot. In those cases, we found the same pattern of visual attention as in the human giver.

Consequently, our second hypothesis is not validated (it holds only for movements judged as less natural, otherwise receiver visual attention is mostly focused on the giver).

C. Third Hypothesis

Concerning the speed of movement, the slow one is considered less natural than the rapid and normal ones. This study was not meant to study deeply this aspect. However, this corroborates our third hypothesis which is in fact an intuitive observation of roboticists that robot slowness is an issue when we have to evaluate it.

D. General results

Taken together, the results on the perceived naturalness of the movement and the ones on the oculometric pattern of the receiver seem to put forward two main conditions: OR and ROR. Those two conditions are not only perceived as more natural than the others (with a robot or a human giver) but they present a similar oculometric pattern of the receiver (with a human or a robot giver). It seems that the final OR is important. When the giver, at the end of the movement, moves the gaze from the object to the receiver, it may signal the end of the exchange. The fact that the receiver looks mainly at the face also in the ORO condition may be interpreted in the same sense: when the robot ends its movement on the object, the receiver seeks an acknowledgement on the robot head (our first look at more detailed eye-tracking results seems to corroborate this interpretation).

Our study is more about the movement itself rather than its initiation, however, our preferred patterns meet the ones found in [START_REF] Strabala | Towards seamless human-robot handovers[END_REF]. That is at the beginning of the action, the robot is looking at the object or at the receiver. We also showed that the gaze at the end of the exchange seems also important. We found that some patterns are considered as more natural than others, whereas [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF] did not find any difference on that aspect. In the robot case, this is confirmed by objective measurements. These patterns tend to confirm our first intuition and findings about handover condition [START_REF] Moon | Meet me where i'm gazing: how shared attention gaze affects human-robot handover timing[END_REF], [START_REF] Strabala | Towards seamless human-robot handovers[END_REF] or in a cooperative task [START_REF] Boucher | I reach faster when i see you look: gaze effects in human-human and human-robot face-to-face cooperation[END_REF] that stated that a human exploits the gaze of the robot when it is present.

The difference in the pupil size between the two types of givers (human or robot) might have different explanations: more curiosity or cognitive load induced by the observation of non-familiar, unknown machine. In the general eyetracking literature, pupil diameters have been found to increase along with cognitive demands [START_REF] Kahneman | Pupil diameter and load on memory[END_REF] and emotional load [START_REF] Bradley | The pupil as a measure of emotional arousal and autonomic activation[END_REF]. In this context, the difference in the pupil size between the two types of givers (human or robot) might have different explanations: more curiosity or cognitive load induced by the observation of non-familiar, unknown machine.

VII. CONCLUSION AND FUTURE WORK

In this paper, we seek to find which head motion or pattern of head motions should be added to arm motion to enable more natural interaction. This study is a joint initiative between a robotics and a psychology team. We have made the deliberate choice to use videos instead of direct interaction (H-H or H-R) following methodological considerations. It is difficult to reproduce exactly the same behaviour for several experimental subjects of a given condition and in the mean time enough heterogeneous and stable between experimental conditions. Through this choice, we give priority to methodological quality of experimental conditions comparisons to the detriment of the ecological validity. However, we have made this choice because we believe that such a study, with controlled experimental conditions, can help the HRI community to build upon a common basis and help check which questions have been already answered (and with which answers) and which questions are still open.

We have found that OR (the giver looks at the Object then at the Receiver) and ROR (the giver looks at the Receiver then at the Object and then at the Receiver again) are preferred patterns for our task. We plan to integrate such results into robot motion planning algorithm and to test it on a real robot. We will also carry on the analysis of eyetracking results to study more precisely where the receiver is looking at, and when. This will serve two goals. The first one is to analyse if this could help us to draw shared attention gaze pattern during the movement. The second one is to get data about where and when a receiver looks at in order to integrate such knowledge onto a receiver robot.

Fig. 1 .

 1 Fig. 1. Snapshots of the videos used to evaluate the movement naturalness.

Fig. 2 .

 2 Fig. 2. the timing of the different gaze behaviours according to were the givers looks.

Fig. 3 .

 3 Fig. 3. The AOIs used in the oculometric measurement randomized. The session (18 trials) was repeated one time. Thus, participants watched and rated 36 videos in all.

Fig. 4 .

 4 Fig. 4. Naturalness ratings as a function of the gaze behaviour and the speed movement four others conditions R, O, RO, ORO (highest p-value in the post hoc table equal to .003). No difference was found between (1) the two conditions OR and ROR (p=. 70) and (2) the three conditions R, O and RO (lowest p-value equal to 0.48). Finally, the condition ORO is significantly judged more natural than the two gazes behaviour R and O (highest p-value equal to .03).Movement speed: Results indicated a main effect of the movement speed on the naturalness ratings, F(2, 58)=10.354, p<.001. Fishers LSD post-hoc comparisons showed that the normal and the rapid speed movement conditions are judged more natural than the slow speed movement condition (highest p-value in the post hoc table equal to .004). No significant difference was found between the normal and the fast speed conditions (p=.16).Type of giver (Human vs. Robot): Interestingly, there was no significant difference in the results between the two types of givers (F(1, 29)=1.988, p=.16). Moreover, no interaction was found between the three main manipulated factors. This result suggests that the effects of (1) movement speed and (2) gaze behaviour described above are not influenced by the type of giver (human or robot).

Fig. 5 .

 5 Fig. 5. Distribution of the visual attention between AOIs as a function of the gaze behaviour and the type of giver

ACKNOWLEDGMENT

This work was conducted within the EU SAPHARI project funded by the E.C. division FP7-IST under contract ICT-287513, and within "Coopération et Interaction Robot-Humain" (CIRH), Maison des Sciences de l'Homme et de la Société de Toulouse, (MSHST), Université Fédérale de Toulouse Midi-Pyrénées.