Asier Marzo
email: asier.marzo@unavarra.es

Benoît Bossavit
email: benoit.bossavit@unavarra.es

Martin Hachet
email: martin.hachet@inria.fr

Combining Multi-touch Input and Device Movement for 3D Manipulations in Mobile Augmented Reality Environments

Keywords: Mobile Augmented Reality, manipulation, multi-touch. ACM Classification H.5.1. Information interfaces and presentation: Artificial, augmented, and virtual realities

Nowadays, handheld devices are capable of displaying augmented environments in which virtual content overlaps reality. To interact with these environments it is necessary to use a manipulation technique. The objective of a manipulation technique is to define how the input data modify the properties of the virtual objects. Current devices have multi-touch screens that can serve as input. Additionally, the position and rotation of the device can also be used as input creating both an opportunity and a design challenge. In this paper we compared three manipulation techniques which namely employ multi-touch, device position and a combination of both. A user evaluation on a docking task revealed that combining multitouch and device movement yields the best task completion time and efficiency. Nevertheless, using only the device movement and orientation is more intuitive and performs worse only in large rotations.

INTRODUCTION

Mobile Augmented Reality (MAR) is a visualization technique which superimposes virtual content over the real environment on a mobile device. Currently, it has reached a mature state as it is supported by most handheld devices and numerous MAR apps are available. This was made possible by the advances in mobile technologies as well as by the progresses in computer vision and graphics techniques. Nonetheless, the way of interacting with these augmented environments is to some point still unclear and thus constitutes a bottleneck for the appearance of highly interactive MAR applications. To interact with a virtual environment, one of the most important tasks is the manipulation of virtual objects. For example, in MAR the task of manipulation is required as soon as the user needs to position and orientate 3D virtual objects in the real environment, as illustrated on Figure 1.

At this time, mobile devices offer multi-touch screens as a standard input. Additionally, in MAR applications, the position and orientation of the device in the real world can be known. Therefore, the challenge is to determine which of these input modalities are better suited for MAR 3D manipulation and if it is beneficial to combine them.

RELATED WORK

In this study, we are focused on manipulation techniques that can be implemented in normal handheld devices and that may achieve efficient interactions. Therefore, we excluded input modalities such as finger or hand tracking as they are not stable on current mobile devices. Similarly, although some studies have used additional devices in combination with the phone, we preferred to concentrate on the input space offered by a standard mobile.

The first study using a mainstream mobile device to manipulate virtual objects in MAR employed different input modalities to separately translate or rotate an object [START_REF] Henrysson | Virtual object manipulation using a mobile phone[END_REF]. According to the authors, the best strategy was to map the physical translations of the device to the virtual object translations, and to use the keypads to rotate the object. In later studies keypad, tilt and finger tracking were compared as an input method to complement device movement [START_REF] Henrysson | Experiments in 3D interaction for mobile phone AR[END_REF]. Despite finger tracking being promising, keypad input for rotations outperformed the rest of the methods. Multi-touch screens were not tested as they were not widespread yet.

More recently, a user study compared the performance of touch gestures and finger tracking [START_REF] Bai | Freeze view touch and finger gesture based interaction methods for handheld augmented reality interfaces[END_REF]. The former input modality could be used while pointing with the device to the virtual object (free-touch) or in a freeze-touch mode. The freeze-touch mode consists in manipulating the object from the point of view of a selected still frame; thus it is not necessary to point to the object during the process. Finger tracking performed two times worse in terms of task completion time (TCT) and accuracy; freeze-touch was slightly better than free-touch but not significantly. The techniques described above were designed to manipulate only 2DOF and none of them employed the device movement alone or in combination with other techniques.

A current study aimed at comparing touch modality with device movement [START_REF] Mossel | 3DTouch and HOMER-S: intuitive manipulation techniques for onehanded handheld augmented reality[END_REF]. They concluded that moving the device was better than using the touch screen for translating or rotating virtual objects. Nonetheless, the employed techniques used only one-hand interactions and no hybrid approach was tested.

In a previous preliminary study we observed that combining multi-touch and device movement could be beneficial [START_REF] Marzo | Poster] Combining Multi-touch and Device Movement in Mobile Augmented Reality Manipulations[END_REF]. In this paper, we analyse more thoroughly the usage of each modality and also report qualitative feedback.

INTERACTION TECHNIQUES

Three interaction techniques to manipulate virtual objects in MAR environments are described in this section.

Multi-touch

Various multi-touch techniques have been developed to manipulate objects with 6DOF [3][7]. However, most of them do not adapt well to small handheld devices. For instance, with small screens, it is difficult to use more than two fingers simultaneously. Similarly, although widgets are a current trend in manipulations for touchscreens [START_REF] Cohé | tBox: a 3d transformation widget designed for touch-screens[END_REF], they are not adequate for small screens due to cluttering issues and fat finger problems. We conducted a pilot study with 6 subjects to determine which technique was better suited for 6DOF manipulations on handheld devices. This led us to propose a variation of the DS3 technique [START_REF] Martinet | Integrality and separability of multitouch interaction techniques in 3D manipulation tasks[END_REF].

The resulting manipulation technique uses one finger to move the object along a plane parallel to the device that pass through the object. The interaction with two fingers serves various purposes. Firstly, the distance between the two fingers modifies the position across the line that joins the object and the device; therefore, a zoom gesture will bring the object closer and a pinch gesture will move it away (Z-Dist). Secondly, the angle variation of the vector that joins the two fingers is transferred to the rotation of the object across the view axis (Z-Rot). Lastly, the displacement of the middle point between the two fingers controls an Arcball rotation [START_REF] Shoemake | ARCBALL: a user interface for specifying three-dimensional orientation using a mouse[END_REF]. This last part of the technique differs from the original DS3 technique that uses a constraint solver. This solver tries to preserve contact points between the fingers and the object, which is not appropriate on small screens. To maximize the interaction surface, the Arcball rotation of this technique employs the entire screen as the virtual ball, instead of using only the object.

Device Position and Rotation

The most straightforward approach to manipulate a virtual object with the device is to transfer the translation and rotation applied to the device (input) to the translation and rotation of the object (output). This technique may work for translations. Nonetheless, orienting the device to rotate the object may be problematic, as the user will lose sight of the manipulated object in the screen.

Previous approaches [START_REF] Henrysson | Virtual object manipulation using a mobile phone[END_REF] [START_REF] Henrysson | Experiments in 3D interaction for mobile phone AR[END_REF][8] employed the grasping technique in which the position and orientation of the object remain constant relatively to the device. In the pilot study, this technique appeared as the most suitable one for manipulating virtual objects using only device movements. It keeps the object inside the virtual field of view and the metaphor of grasping the objects helps the users to understand how the objects will behave. The users can clutch the manipulation by touching or not the screen.

Hybrid

This third approach mixes multi-touch screen input and device movements. Previous work [START_REF] Henrysson | Virtual object manipulation using a mobile phone[END_REF] suggests that for object translation, using the device movement is the most efficient way; and that for rotation, using the keypad is the best option. We took into account these suggestions by combining the grasping technique for translation with a touch control for rotation. The most used technique to perform general rotations is Arcball [START_REF] Shoemake | ARCBALL: a user interface for specifying three-dimensional orientation using a mouse[END_REF]. Therefore, since one-finger touch input is not dedicated to translations anymore, it is used to perform Arcball rotations in view space. The Hybrid technique also supports the use of two fingers to supplement the Arcball rotation (Z-Rot and Z-Dist gestures).

USER STUDY

We conducted a user study to compare the three modalities associated with the interaction techniques described above. The study involved 12 people (2 female and 10 male). Participants' age ranged from 24 to 40 (M=27.3, SD=8.9).

Participants had medium experience with 3D and three users were left-handed. The experiment was performed using a 3 rd generation iPod. The software ran under iOS 6, was developed using C++ and used Vuforia SDK for the tracking. The participants were seated in front of a table that reached below their chests. A paper marker is needed to achieve the tracking. It was printed on a 49x34 cm paper sheet and was placed on the table.

The task to perform was a 3D docking similar to Zhai's et al. [START_REF] Zhai | Quantifying coordination in multiple DOF movement and its application to evaluating 6 DOF input devices[END_REF]. Participants were asked to manipulate a bright chair (cursor) in order to overlap it with a static dark chair (target). The target chair was always static, located at the centre of the scene, whereas the cursor was located at different positions and orientations according to the trial. The experiment was divided into 4 blocks of 5 trials each. The order of the trials was: Only translation, Small Simple Rotation, Small Complex Rotation (x2) and Large Complex Rotation. All the trials implied translations.

Small angles ranged from 30 to 60 degrees and large ones from 110 to 180 degrees. Simple rotations implied rotations around one of the primary axes whereas complex ones were performed around a random axis. The distance between the target and the cursor varied from 7 to 15 centimetres. The size of the chairs was 4x4x6 cm. The error tolerance was 1 cm for translation and 12 degrees for rotation. If a participant could not complete the trial in 40 seconds, the trial ended in failure. Selection methods for the objects were removed from the evaluation and the cursor object was always preselected.

Each participant spent approximately 40 minutes for completing the entire experiment. For each condition, the participant had a short training during few minutes. Then, they performed the docking task. Finally, they filled in the NASA TLX questionnaire and a custom questionnaire. The order of the modalities was determined according to a Latin Square. The transformations of the chairs were randomly generated but they were the same for each participant. The timer was stopped when the marker needed to track the device was not visible. This tracking method is a current limitation that will be overcome in the future. For similar reasons, subjects were not allowed to manipulate the marker.

To summarize, the experiment consisted of: 12 participants x 3 techniques x 4 blocks x 5 trials = 720 docking tasks.

RESULTS

Data were analyzed using RM-ANOVA to detect significant effects of technique; T-pair tests with Bonferroni adjustment were used as post-hoc tests. Greenhouse-Geisser correction was applied when sphericity was violated. Only completed tasks were included in the analysis. Success rate was close to 100% across all participants and techniques.

Task Completion Time

Task Completion Time (TCT) represents the average time measured in seconds that the participants needed to complete each trial. TCT split by type of trial and technique is shown on Figure 2, left.

Inefficiency

Inefficiency is the ratio between the length of the real path and the length of the optimal path [START_REF] Zhai | Quantifying coordination in multiple DOF movement and its application to evaluating 6 DOF input devices[END_REF]. Inefficiency is shown on Figure 2, right.

Device Movement and Position

Device movement and speed were measured. They are shown averaged per trial on Figure 3. All the values are reported using the OpenGL coordinate system.

Multi-touch Gestures

We examined the percentage of time that a certain number of fingers were used to interact (Figure 4, left). Specific gestures usage is shown on Figure 4, right. Move and Z-Dist gestures are expressed in the displacement of fingers relatively to the height of the screen (5.5cm). Z-Rot and Arcball are reported in the amount of radians that were applied. All the data are averaged per trial.

Subjective Ratings

The score of the NASA TLX ranges from 0 (low cognitive load) to 100 (high cognitive load). In our case, this test showed a score of 25.23 (SD=18.41) for Hybrid, 31.25 (SD=20.89) for Device and 40.05 (SD=19.59) for Touch.

The results of the custom questionnaire are shown on Figure 5.

DISCUSSION

In average, Hybrid had the lowest TCT. For only translation, Hybrid and Device had similar TCT as they both use the grasping technique; Touch was the worst but not significantly. For small rotations, Hybrid and Device performed similarly because the users always employed the device in Hybrid. Touch performed significantly worse than the other techniques. It seems that for small rotations using the device is better than using multi-touch gestures. For large rotations, Hybrid was the best. Device was the worst in large rotations as the object had to be rotated using successive manoeuvres. This fact is reflected in the high inefficiency that Device had in translation because while rotating the object it was also translated purposelessly. The other two techniques were more efficient in translation but Device was the most efficient in rotation.

The amount of movement in position and rotation of the device is always in the order Device>Hybrid>Touch. In position, there is more movement on the X axis and less in the Y axis. The Hybrid technique reduces the amount of position movement significantly but not for the Y axis since it is the only way of moving the object up. For Touch, position movement was low for all the axes but not for X. This could be caused by the users' necessity of adopting different points of view. In rotation, movement was smaller for X in Device because it was hard to point upwards without losing the target chair or the marker.

Hybrid mitigates this problem as the finger can be used to rotate around the X axis. Furthermore, Hybrid reduces the amount of rotation in all the axes. Speeds follow the same pattern as the amount of movement.

Users spent a similar percentage of time without touching the screen in all techniques. In Touch, the amount of time with one and two fingers is proportional to the DOF that can be controlled with them. The Hybrid technique used the Arcball gesture slightly less than Touch, possibly because the device was used for the remaining rotation. The Z-Dist gesture in Touch is unusually high; we assume that this is caused by small involuntary changes of the distance between the two fingers when the user is performing other two-finger gestures (Arcball or Z-Rot).

NASA TLX showed a tendency of Touch inducing the highest cognitive load and Hybrid the lowest one. In the custom questionnaire, preference was Hybrid >Device>Touch; however, it was easier to move (Q6) and rotate (Q5) with Touch than with Device. Device appeared as the most intuitive (Q1) and Hybrid as the most accurate (Q7). Nonetheless, results were not significant.

A previous study [START_REF] Mossel | 3DTouch and HOMER-S: intuitive manipulation techniques for onehanded handheld augmented reality[END_REF] stated that Device was better than Touch. Differently, our study reveals that they are similar for translation; Device is better for small rotations and Touch for large ones. This difference could be due to the solely use of one-hand techniques. Another study [START_REF] Bai | Freeze view touch and finger gesture based interaction methods for handheld augmented reality interfaces[END_REF] revealed that freeze-touch is better for DOF-constrained manipulations. For constrained manipulations, it could be enough to use Touch or Device. However, none of these studies evaluated a hybrid approach.

CONCLUSION

Three techniques to manipulate virtual objects with 6 DOF have been compared in a MAR environment. Our user study suggests that combining device movement with multi-touch input offers the overall best results. Nonetheless, using only the device performs worse exclusively on large rotations. Using only the device is interesting as it appeared intuitive and removes the necessity of doing touch gestures on the screen.

Figure 1 .

 1 Figure 1. Manipulating virtual objects in a MAR environment. Left) Virtual objects positioned around a real object. Right) Positioning obstacles in a space game.

Figure 2 .Figure 3 .

 23 Figure 2. Left) task completion time grouped by technique and type of trial. Error bars represent standard deviation. Right) Inefficiency in translation and rotation.

Figure 4 .Figure 5 .

 45 Figure 4. Left) percentage of time spent with a certain number of fingers on the screen. Right) specific gestures usage.


Nazim Haouchine
email: nazim.haouchine@inria.fr

Jeremie Dequidt
email: jeremie.dequidt@inria.fr

Marie-Odile Berger
email: marie-odile.berger@inria.fr

Stephane Cotin
email: stephane.cotin@inria.fr

Single View Augmentation of 3D Elastic Objects

Keywords: H.5.1 [Information Interfaces and Presentation]: Multimedia Information Systems-Artificial, augmented, and virtual realities; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-Physically based modeling

This paper proposes an efficient method to capture and augment highly elastic objects from a single view. 3D shape recovery from a monocular video sequence is an underconstrained problem and many approaches have been proposed to enforce constraints and resolve the ambiguities. State-of-the art solutions enforce smoothness or geometric constraints, consider specific deformation properties such as inextensibility or ressort to shading constraints. However, few of them can handle properly large elastic deformations. We propose in this paper a real-time method which makes use of a mechanical model and is able to handle highly elastic objects. Our method is formulated as a energy minimization problem accounting for a non-linear elastic model constrained by external image points acquired from a monocular camera. This method prevents us from formulating restrictive assumptions and specific constraint terms in the minimization. The only parameter involved in the method is the Young's modulus where we show in experiments that a rough estimate of its value is sufficient to obtain a good reconstruction. Our method is compared to existing techniques with experiments conducted on computer-generated and real data that show the effectiveness of our approach. Experiments in the context of minimally invasive liver surgery are also provided.

INTRODUCTION

3D recovery and augmentation of deformable objects in a monocular context is a challenging problem with many potential applications in computer graphics, augmented reality and medical imaging. The difficulties originate from the fact that the problem is underconstrained. To overcome this problem, various approaches have been considered with the aim to provide additional contraints and solve the ambiguities. Many approaches introduced deformation models which are often learned from training data and derive models with few degrees of freedom. A lot of papers have been devoted to inelastic materiels such as papers, sails, clothes . . . and make use of the inextensibilty constraint, ensuring that the distance between points remains constant. Other geometric or shading constraints have been proposed to handle materials that can stretch. However, the additional constraints that are used are not always suited to the properties of the object. That is the reason why we advocate in this paper the use of a mechanical model within a non-linear elasticity framework to enable reconstruction and augmentation of highly deformable objects. Our model only requires the knowledge of the Figure 1: Three-dimensional reconstruction and augmentation of elastic objects from a single view under several elongations. Our approach is able to handle extensibility of the material when undergoing elongation. In (top) the camera view of the re-textured elastic object and in (bottom) the recovered 3D shape form showed from a different view.

Young's modulus. Mechanical models have been seldom used in the past due the difficulty to acquire the parameters of the model and the complexity of non-linear models which precludes real time algorithms. In this paper, we propose an efficient real-time algorithm for recovery and augmentation of highly elastic objects in a monocular context. We also show that a rough estimation of the Young's modulus is sufficient to obtain a good reconstruction while imposing sufficient boundary constraints. Applications of the method are provided in the context of augmented reality for minimally invasive liver surgery. Augmented Reality techniques are considered as a well-suited approach in order to enrich visual feedback of surgeons during minimally invasive procedures [START_REF] Nicolau | Augmented reality in laparoscopic surgical oncology[END_REF] where surgeons do not directly manipulate the organ but interact with the organ using instruments inserted through small incisions around the abdominal cavity. Visualization of additional pre-operative information -such as tumors-in the field of view of the surgeon requires to track in real time possibly large elastic deformations of the liver. Existing techniques that take into account organ elasticity [START_REF] Haouchine | Image-guided simulation of heterogeneous tissue deformation for augmented reality during hepatic surgery[END_REF] [START_REF] Pratt | Dynamic guidance for robotic surgery using image-constrained biomechanical models[END_REF] have been proposed. These methods rely on a combination of a stereo estimation of organ motion and on biomechanical models to characterize the elastic behaviour. Despite the fact that these methods yield good results, stereo-laparoscopic cameras are uncommon compared to mono-laparoscopic camera (less than 1%), which motivated us to investigate this limitation.

The paper is organized as follows. Existing techniques for 3D recovery of elastic objects are presented in Section 2. Our method is explained in Section 3, 4 and 5. The obtained results are exposed in Section 6 and show that the method is able to cope with large elastic deformation in a various dataset including surgery data.

In the early works on augmented reality for deformable objects, registration of images of a deforming surface was obtained by computing dense 2D/2D transformations using points correspondences. A parametric representation of the deformation or regularization techniques were needed to prevent excessive wrinkling of the surface in the presence of erroneous correspondences. In [START_REF] Bartoli | Direct estimation of non-rigid registration[END_REF], Bartoli et al. take advantage of a rich texture information to perform points matching between images, allowing a 2D deformation motion model to be computed using Radial Basis Mapping. Pilet et al. [START_REF] Pilet | Fast non-rigid surface detection, registration and realistic augmentation[END_REF] proposed a template-based fast and robust tracking for handling deformations. This approach uses a set of wide baseline feature matches assuming a well textured surface and combines 2D deformable meshes with a robust estimation technique. Zhu et al. [START_REF] Zhu | Progressive finite newton approach to real-time nonrigid surface detection[END_REF] demonstrate that a Finite Newton algorithm and an efficient factorization method can reduce the number of iterations of the previous method to solve the optimization problem. In order to handle the more challenginging case of deformation with self occlusions, Gay-Belille et al. [START_REF] Gay-Bellile | Direct estimation of nonrigid registrations with image-based self-occlusion reasoning[END_REF] considered the occluded pixels as self-occlusion area that forces the wrap to shrink instead of outliers. Inspired by this self-occlusion shrinking method, Hilsmann et al. [START_REF] Hilsmann | Realistic cloth augmentation in single view video under occlusions[END_REF] proposed an approach exploiting an optical flow extended by a specific illumination model which jointly estimates deformation and illumination and can cope with self-occlusions through an occlusion map computed from local statistical color models. In [START_REF] Pizarro | Feature-based deformable surface detection with self-occlusion reasoning[END_REF], self occlusions are detected as outliers based on the assumption that the surface to detect is locally smooth.

However, these methods based on 2D images transformations are well suited to smooth deformations but are not suitable for highly elastic objects. In fact, elastic deformations in the 3D space can lead to highly complex 2D deformations in the image plane, especially due to self occlusions, making inappropriate the use of regularization contraints. For these reasons, state-of-the art methods perform 3D reconstruction of deformable surfaces in a monocular context since elasticity constraints are often known or can be expressed in a more natural way on the 3D objets. Recovering the 3D shape of a deformable surface from a monocular video and a template (a reference image of the surface for which the 3D shape is known) can be ambiguous. Therefore additional consistency constraints are required to solve ambiguities. The inextensibility constraint is widely used to recover and augment objets as sheets of paper, sails, tee-shirts. . . [START_REF] Shen | Monocular 3-d tracking of inextensible deformable surfaces under l2-norm[END_REF][START_REF] Perriollat | Monocular template-based reconstruction of inextensible surfaces[END_REF]. Methods differ in the way inextensibility is considered as a hard constraint or a penalty term and also in the efficiency of the convex or non-convex optimization associated to the procedure. In the general case, global smoothness constraints are common to resolve the ambiguities of 3D reconstruction. Many papers ressort to a linear description of feasable object deformation. Most of the time, it is generated from a representative sample of possible shapes using a dimensionality reduction process [START_REF] Salzmann | Surface deformation models for nonrigid 3d shape recovery[END_REF][START_REF] Salzmann | Linear local models for monocular reconstruction of deformable surfaces. Pattern Analysis and Machine Intelligence[END_REF]. Some works attempt to overcome the need to provide plausible constraints on the deformation by using richer sources of information. In [START_REF] Moreno-Noguer | Capturing 3d stretchable surfaces from single images in closed form[END_REF] a closed-form solution constrained by shading informations was introduced to capture stretching surface. This method assumes a Lambertian surface with a single point light source and yield good results. However, the strong assumptions on the lighting make the method hard to generalize in all environments. Other methods have been designed to cope with non smooth deformations, as folding. Salzmann et al. [START_REF] Salzmann | Convex optimization for deformable surface 3-d tracking[END_REF] propose to solve the problem as a convex minimization of the reprojection error formulated as a Second Order Cone Programming (SOCP). The method restricts the motion from one frame to the next but do not impose unwarranted surface smoothness, making it possible to recover sharp folds.

Recently, many examples of mechanical-based tracking methods have emerged. For instance the approach in [START_REF] Agudo | Finite element based sequential bayesian non-rigid structure from motion[END_REF], where a combination of Finite Element Modelling with and Extended Kalman Filter shows the efficiency of physics-based method. In [START_REF] Wuhrer | Tracking complete deformable objects with finite elements[END_REF], a lin-ear finite element method is used to predict the deformation. The approach described in [START_REF] Malti | Monocular templatebased 3d reconstruction of extensible surfaces with local linear elasticity[END_REF] relies on the minimization of a stretching energy subject to external image constraints. The problem is formalized as a non-linear minimization that unifies geometric constraints assuming a projective camera and mechanical constraints assuming local linear elasticity. This method shows effective results but is however limited to compressible objects by considering the Poisson ratio as the unique mechanical parameter.

Contribution

The main contribution of this paper is to provide an efficient method to capture and augment a 3D elastic surface from a single viewpoint. By assuming a prior knowledge of the material elasticity (represented by the Young's modulus), large strains of more than 130% can be efficiently handled. To the best of our knowledge, no similar method has been proposed in the case of monocular camera.

NON LINEAR ELASTIC MODEL

The choice of a relevant constitutive model is essential as it will determine the set of deformations we are able to capture and estimate while discriminating non-plausible material configurations induced by tracking errors. Two important assumptions are also made in order to reduce the complexity of the deformation model and the number of related parameters. First, the material of the deformable object will be homogeneous meaning that a uniform deformation will lead to equal (in magnitude) forces for any points of the object. Second, the material will also considered as isotropic meaning that the response to a deformation is independent of the orientation of the deformation. Moreover computation time is also a key constraint as the targeted application should be interactive.

Interactive (or at least computationally fast) models for deformable solids have been a major topic in the computer graphics community. Several reports or surveys have been published to provide an exhaustive overview of state-of-the-art methods [START_REF] Gibson | A survey of deformable modeling in computer graphics[END_REF][START_REF] Nealen | Physically based deformable models in computer graphics[END_REF][START_REF] Sifakis | Fem simulation of 3d deformable solids: A practitioner's guide to theory, discretization and model reduction[END_REF]. In that context, Saint Venant-Kirchhoff model [START_REF] Sifakis | Fem simulation of 3d deformable solids: A practitioner's guide to theory, discretization and model reduction[END_REF] appears to be an ideal compromise because it is able to handle non-linear deformations, is rotationally invariant and is simple enough compared to other non-linear model and therefore can be computed at interactive rates. Several downsides however exists such as incorrect stress estimation under extreme compression and sometimes the requirement to use non-linear solvers to compute the motion over time. Incorrect stress estimation under any large deformations is not a major issue in our context since we are interested in capturing an accurate deformation field and since the stress field is not measurable with camera images. Recent works in simulation or in haptics rendering have proposed computationally fast non-linear solvers such as [START_REF] Silcowitz-Hansen | A nonsmooth nonlinear conjugate gradient method for interactive contact force problems[END_REF] which leverages the pre-requisites of use non-linear solvers with Saint Venant-Kirchhoff model.

A Saint Venant-Kirchhoff (StVK) material is a material for which the Green-Lagrange strain tensor E ∈ R 3x3 is computed as a non-linear (quadratic) function of the deformation gradient F ∈ R 3x3 as:

E = 1 2 (F T F -I) (1)
where I ∈ R 3x3 is the identity matrix. The computation of the strain tensor maybe computationnaly intensive and several approaches have been investigated for interactive uses. For instance, Barbic and James [START_REF] Barbič | Real-time subspace integration for st. venant-kirchhoff deformable models[END_REF] uses model reduction and pre-computation reduced coordinates while Zhong et. al. [START_REF] Zhong | A real time finite element based tissue simulation method incorporating nonlinear elastic behavior[END_REF] uses pre-computed relation between surface and internal nodes. In this paper, the elegant approach of Kikuuwe et. al. [START_REF] Kikuuwe | An edge-based com-putationally efficient formulation of saint venant-kirchhoff tetrahedral finite elements[END_REF] is chosen since it does not require pre-computation nor does it make any assumption of the deformations that will be generated. To do that, fast computation is conducted using dedicated yet simple data-structures (tetrahedronsharing edge-pairs). We will detail the main points of Kikuuwe et.

al. but we encourage the reader to refer to [START_REF] Kikuuwe | An edge-based com-putationally efficient formulation of saint venant-kirchhoff tetrahedral finite elements[END_REF] for complete analysis and implementation details. If v is a point in the deforming medium and v 0 is its initial location, F can be expressed as

F = ∂ v ∂ v 0
Since E is symmetric, its form is as follows:

E =    ε xx ε xy ε zx ε xy ε yy ε yz ε zx ε yz ε zz    (2)
and the 6 independent coefficients may be placed in a single vector ε using Voigt notation:

ε = [ε xx , ε yy , ε zz , 2ε xz , 2ε yz , 2ε zx ] T (3)
Computing E is often conducted by using a strain energy density w that will be integrated over the whole deforming medium X through the following equation:

E = X w dX (4)
An isotropic homogeneous Saint Venant-Kirchhoff material has w expressed with the following equation:

w = ε T D ε/2 (5)
where D ∈ R 6x6 is the following matrix:

D =          λ + 2µ λ λ 0 0 0 λ λ + 2µ λ 0 0 0 λ λ λ + 2µ 0 0 0 0 0 0 µ 0 0 0 0 0 0 µ 0 0 0 0 0 0 µ          (6)
where λ and µ are Lamé coefficients and can be computed thanks to the elastic parameters of the material E and ν. E is the Young's modulus and is a measure of the stiffness of the material while ν is the Poisson's ratio and estimates the compressibility of the material.

For a deforming medium of arbitrary shape, it is often convenient to discretize the shape using elementary and simple elements. Tetrahedral decomposition is often considered since efficient meshing algorithms exist 1 . For a tetrahedron t, let us consider the edge e among the 6 possibles edges of t, e being connected two vertices v i and v j . Be l e = v iv j and l 0 e = v 0 iv 0 . Assuming that the deformation gradient F is constant in the neighbor of t and has the value F t , l e can be estimated as F t l e . The equation ( 1) can be used to write:

l T e E t l e = 1 2 l T e (F T t F t -I)l e l T e E t l e = 1 2 ( l e 2 -l 0 e 2 ) (7)
l 0 e can also be written in Voigt notation using the variable q 0 e defined as:

q 0 e =          (v i .x -v j .x) 2 (v i .y -v j .y) 2 (v i .z -v j .z) 2 (v i .x -v j .x)(v i .y -v j .y) (v i .y -v j .y)(v i .z -v j .z) (v i .z -v j .z)(v i .x -p j .x)          (8)
1 for instance CGAL library http://www.cgal.org where for each value .x, .y, .z is the first / second / third component of the considered vector. The previous equation is the rewritten by using Voigt notations as:

q 0T e ε t = 1 2 ( l e 2 -l 0 e 2 ) (9)
This equation is considered for a single edge e but is suitable for the other edges. By considering the 6 edges of the tetrahedron t, we obtain the following equation:

Q t ε t = 1 2 L t ( 10
)
where Q t = [q 0 0 , q 0 1 , q 0 2 , q 0 3 , q 0 4 , q 0 5 ] T (q e for the 6 possibles edges) and

L t = [ l 0 2 -l 0 0 2 , l 1 2 -l 0 1 2 , .
. .] T (again for the 6 possible edges). It should be noted that Q t ∈ R 6x6 and L t ∈ R 6 . Q t is invertible if the 4 points are not linearly dependent and therefore ε t can be estimated as:

ε t = 1 2 Q -1 t L t ( 11
)
enabling to compute the strain energy in the tetrahedron t with

W t = ε T t D ε t /2 (12)
Therefore the total strain energy W = ∑Wt of the medium as a function of the edge lengths of the tetrahedral mesh and elastic parameters. Eventually the forces exerted on the vertices can be computed as:

f (v) = ∂W ∂ v T (13)
For computation purposes, a global stiffness matrix is also computed as:

K(v) = ∂ f (v) ∂ v (14)
as it allows for a displacement dv (such as v ′ = v + dv) of the vertices of the mesh to compute the resulting forces as:

f (v) = K(v) × dv (15)
This is a convenient equation that relates forces to any displacement of the vertices but again it should be reminded that the matrix K(v) should be recomputed after every deformation to remain valid.

PROBLEM FORMULATION

The non-rigid surface reconstruction from a single view can be formalized as the minimization of a reprojection error. By assuming a known and constant projection matrix P, the projection of a point M = (X,Y, Z) in the image is given by: (16) where P k is the k th row of the projection matrix P.

m = x y =
For a set of n point, minimizing the reprojection error with respect to the point m = ( x, ŷ) that correspond to the projection of M in the image amount to minimize the quantity:

n ∑ i=1 P 1 M i P 3 M i -xi , P 2 M i P 3 M i -ŷi (17)
In practice, additional penalties functions are used to obtain a wellconstrained system. This constraints are often based on the inextensibility property of the surface to be recovered. Since such constraints cannot be considered in our case, we propose to consider the elastic registration as a stretching energy minimization problem that accounts for the internal forces of the mechanical and external forces emanated from the visual tracking. We here assume that the following data are available:

• The projective matrix P assuming orthographic projection.

• The correct initial alignment of the mesh (in rest configuration) on the image.

• A set T of paired point between the set of features U = {u i ∈ R 2 } from visual tracking and the vertices of the mesh V = {v i ∈ R 3 } related to the mechanical model.

• The Young's modulus E that represent the elasticity of the mechanical model.

At initialization each feature u i is associated with a 3D point ûi by intersection the line of sight with the surface. ûi is expressed as a barycentric combinaison of the neighbouring vertices N i of the mesh: ûi = ∑ j∈N i γ i j v j . We assume that this linear relation remains valid during the deformation. At any later time, the stretching energy induced by the visual tracking is defined as:

∑ i∈T 1 2 α v i -P( ûi ) 2 ( 18
)
where α can be seen as a stiffness and is experimentally chosen to at the same order of magnitude of the Young's modulus. In order to obtain a system that is sufficiently constrained to give good results, we add to the system a set B of boundary constraints by using the term:

v i = Q i f or i ∈ B ( 19
)
where Q i is the known boundary conditions that can be seen as a set of fixed vertices. The minimization problem is then formulated as a constrained minimization between internal elastic energy and stretching energy and can be written as follows:

minE(v) = ∑ t W t + ∑ i∈T 1 2 α v i -P( ûi ) 2 sub ject to v i = Q i f or i ∈ B ( 20
)
where W t is the strain energy of a tetraherdon related to a Saint Venant-Kirchhoff material and which is depending on the position of the vertices. The expression of W t is detailed in the equation [START_REF] Hilsmann | Realistic cloth augmentation in single view video under occlusions[END_REF].

RESOLUTION

The equation ( 20) is a classical constrained minimization problem. We choose to solve this equation by formulation a linear complementary problem (LCP) that will be solved with a Gauss-Seidel algorithm using the approach in [START_REF] Guébert | Unified processing of constraints for interactive simulation[END_REF]. Finding the minimum of energy is conducted by deriving and setting to zero the equation [START_REF] Peterlík | Modeling and real-time simulation of a vascularized liver tissue[END_REF]. This leads to an equality between internal elastic forces and stretching forces and this is equivalent of finding the equilibrium state of the material due to external forces. Indeed kinetic energy is not considered since we are not interesting in capturing transient motions because first, the materials used are very soft and second, the acquisition rate is high enough; therefore the deformation exhibit no significant transient motion. The method proposed in [START_REF] Guébert | Unified processing of constraints for interactive simulation[END_REF] is a two-steps solver that is able to find a constrained minimum by considering first a free-motion and second applying a corrective motion to satisfy our boundary conditions. The reader may refer to [START_REF] Guébert | Unified processing of constraints for interactive simulation[END_REF] for implementation details. Even if our approach is static (without dynamic due to kinetic energy of the material), it can easily be adapted to dynamic motion with the same method by adding a non-linear differential equation solver such as an implicit Euler with a conjugate gradient [START_REF] Faure | SOFA: A Multi-Model Framework for Interactive Physical Simulation[END_REF].

EXPERIMENTAL RESULTS

In this section we present the results obtained using our method and the comparison conducted with existing techniques. We report results obtained on three type of data: Silicone-made data, computergenerated data and liver data during in-vivo surgical procedure. To test the ability of our approach to capture 3D elastic deformations, we capture several video sequences of a silicone-like object undergoing different type of stretching deformation. We quantify the three-dimensional shape recovery error with respect to a ground truth while visual assessment is reported on surgical data. We use the SURF [START_REF] Bay | Speeded-up robust features (SURF)[END_REF] for image point correspondence where the number of detected point can be easily tuned. Note that other descriptors can easily been plugged to the framework and take advantage of recent work on vision-based tracking of living tissue [START_REF] Yip | Tissue tracking and registration for image-guided surgery[END_REF].

Computer-generated Data

We used the framework Sofa [START_REF] Faure | SOFA: A Multi-Model Framework for Interactive Physical Simulation[END_REF] to generate elastic deformations of a silicone-like object with a Young's Modulus of E = 0.25 MPa. A force F is applied on the object to produce a 3D deformation (cf Figure 2). A video sequence of the deformations is captured with a virtual camera (diag(500,500,1)). The external stifness parameter is set to be equal to the synthetic force α = F. The Figure 2 illustrate the results obtained by calculating the Hausdorff Distance between the tracked and simulated mesh where we report an average error of 3.16 mm for the simulation 1 and 2.90 mm for the simulation 2.

We also conduct experiments on the same set of data where we vary the Young's Modulus value. The plot 3 shows that small variation of E slightly affect the registration error in comparison with the large errors that produce greater or lower values. In the mean time, we notice that a value of α close to the Young's Modulus gives the best results in term of accuracy.

It should be emphasized that a further sensitivity study is required to identify the most influential parameters of the simulation. The conducted experiments only highlight that an approxi-mate value of the Young's Modulus is enough to yield convincing registration results. In fact, depending on the way the constraints on the deformable structure are modeled, the resulting deformation can be entirely independent of the Young's Modulus. The reader may refer to [START_REF] Miller | On the prospect of patient-specific biomechanics without patient-specific properties of tissues[END_REF] for a more detailed study on the impact of material properties when dealing with soft-tissue simulation.

Real Data

We test our method on a silicone-like object with a size of 100 × 100 × 10 mm 3 composed of linear P1 tetrahedral elements characterized by a Young's Modulus E = 0.25 MPa. The image are acquired with a monocular camera at 30 fps with an image resolution of 640 × 480. The implementation is done in C++ on a PC with and Intel i7 M620 2.76GHz processor.

2D Surface Registration and Retexturing

The aim of conducting tests on 2D surface is to be able to measure the registration error w.r.t the deformation of the object. Since the boundaries of the object can be easily extracted in the image, a way to quantify this error is to compute the distance beween the silhouette computed from the recovered 3D object and the actual boundaries extracted in the image. The results reported in the plot 4 gives the small 2D error even when the elongation increases (more than 120%). The relation between the accuracy of the augmentation and the number of tetrahedron elements is also reported in figure 4 where we can notice that a finer mesh resolution reduce the registration error.

In order to ensure real-time achievement, a compromise has to be found between the number of elements and the computation time. While a large number of elements permits to obtain an accurate registration, it also increases the computation time. The Table 6.2.1 gives the average errors and computation time w.r.t the mesh resolution.

3D Shape Recovery and Augmentation

For the three-dimensional reconstruction we propose to test our approach on 4 types of deformations, with extensibility up to 130% as illustrated in Figure 6. We calculate the euclidean distance between the reconstructed surface and a ground truth obtained with Structure from Motion techniques [START_REF] Snavely | Photo tourism: Exploring photo collections in 3d[END_REF]. We compare our method with 3 existing approaches: a template-based method for isometric and conformal surface reconstruction described in [START_REF] Bartoli | On templatebased reconstruction from a single view: Analytical solutions and proofs of well-posedness for developable, isometric and conformal surfaces[END_REF] the code of which is freely available, a classic mass-spring model and a mechanicalbased approach that considers a linear Strain/Stress formulation [START_REF] Cotin | Real-time elastic deformations of soft tissues for surgery simulation[END_REF].

The plots and the resulting shapes are illustrated in Figure 7.

Deformation 1: By stretching the object with an elongation of 30%, we force the surface to fold. The linear FEM and the templatebased approach fail to correctly recover the 3D shape. The nonlinear method gives the lowest error with 2.62 mm with only 26 detected features.

Deformation 2:

The surface is constrained with a rigid beam and stretched to produce a triangle-like shape. Only the mass-spring models was not able to recover the deformation. The templatebased approach yields good results. However, the mechanical methods report the more accurate registration with very close error: 2.52 mm for the Linear FEM and 2.44 mm for out method. The number of features extracted is 28 for all the methods except the templatebased where 237 features are necessary to yield good results.

Deformation 3: The object is elongated down and constrained at the center of the object. The four methods succeed to recover the the shape deformation with 174 extracted features. Our method outperforms the others with an error of 2.06 mm.

Deformation 4: Our approach gives the smallest error with 1.69 mm where the extensibility is about 130%. The object highly elongated during the deformation and produces a 3D shape by partially folding. The template-based method fails to recover the stretched shape while the mass-spring and linear FEM models give relatively good shape representations.

Surgical data

Our aim is to assess the robustness of our approach in a real environment (specular lights, beating heart, respiratory motion, instrument occlusions) and the ability of our non-rigid registration in recovering 3D shapes from a single view. In our past works on liver augmentation [START_REF] Haouchine | Image-guided simulation of heterogeneous tissue deformation for augmented reality during hepatic surgery[END_REF], we mainly consider deformations of the liver that mainly occurs in a fronto-parallel plane but not very in depth. In addition, visual features were acquired in 3D thanks to a stereovision set-up. Here a general motion of the liver is considered, with possible folds, in the monocular context which is a much more complex situation. We test our approach on an video of in-vivo porcine liver showing one of the liver lobe undergoing elastic deformation during a minimally invasive surgery. We used a monocular laparoscopic camera from Karl Storz Endoscopy acquiring video stream in 25 FPS with image resolution of 720 × 576 pixels and data computed from pre-operative scans. This data permits to generate the necessary mesh for a correct modelling of the liver in three steps: segmentation, volume generation and parametrisation.

Segmentation: The volume issued from CT-scanner is used to generate the liver surface. This segmentation is done semimanually using active contour techniques (Snake) using the software itksnap 2 .

Volumetric mesh generation: Volumetric mesh are necessary for a finite element modelling. To generate this volume from surface we use CGal library. The number of elements is to be chosen carefully in order to ensure real-time performance as long as sufficient accuracy.

Parametrisation: The elastic parameter (Young's modulus) is set according to [START_REF] Peterlík | Modeling and real-time simulation of a vascularized liver tissue[END_REF] to E=27 KPa with a model composed of 3914 linear P1 tetrahedral elements.

These steps are commonly performed before a surgical procedure which permit to our framework to easily take advantages of the data. The Young's modulus is extracted from a textbook and does not suit exactly the considered liver. The results illustrated in the Figure 8 report a visually correct 3D elastic augmentation of the liver model on the laparoscopic image with a good 3D shape recovery.

CONCLUSION

In this paper, we have proposed a real time and efficient method to capture and augment highly elastic objects from a single view. This method makes use of a mechanical model of the deformable object in the context of non linear elasticity. With respect to many existing approaches, this method makes it possible to avoid the definition of adhoc constraints to solve the ambiguities of reconstruction. Experiments conducted in the paper prove that the method is flexible in the sense that a classical model -the St Venant-Kirchhoff modelhas proven to be sufficient to handle various applications with a good accuracy. The orthographic projection is currently used in our method in the image term since the minimization is easier than with the perspective projection. Integration of a fully perspective model will be done in the very near future. Moreover, handling partial and self-occlusions is also one axe of future development since our experiments highlight that a few number of image point are sufficient to yield good results.

Figure 2 :

 2 Figure 2: 3D registration error on two computer-generated sequences. The applied forces are represented with red arrows and the tetrahedral elements in blue, for (a) simulation 1 where two forces in opposite directions are applied and (b) simulation 2 where a single force is applied.

Figure 3 :

 3 Figure 3: 3D registration error on with variation of the Young's Modulus for simulation 1 and simulation 2: Small variation of the Young's Modulus value slightly affect the reconstruction while distant values highly increase the errors.

Figure 4 :

 4 Figure 4: Registration error with respect to object elongation with a variation of mesh resolution: With an adequate number of tetrahedral elements the projection error can be significantly reduced.

Figure 5 :

 5 Figure 5: Selected frames during a 2D elastic surface augmentation of the silicone-like material when being stretched up to 120%, with (top) input images (middle) registered mesh (bottom) surface retexturing.

Figure 6 :

 6 Figure 6: Selected frames showing the overlay of the mesh on the images with the silicone-like data with (a) deformations 1, (b) deformation 2 (c) deformation 3 and (d) deformations 4.

Figure 8 :

 8 Figure 8: 3D elastic augmentation of the mechanical model on the laparoscopic images acquired form a monocular camera. The augmentation is effective (left) even when the deformation generated by the instrument force the lobe of the liver to fold (right).

Figure 7 :

 7 Figure 7: 3D shape recovery of a silicone-like material deformation: Our method produce the lowest error in comparison with other methods on 4 type of deformations and extensibility with (a) and (c) deformation 1, (b) and (d) deformation 2, (e) and (g) deformation 3 and (f) and (h) deformation 4.

  PM = P 11 X+P 12 Y +P 13 Z+P 14 P 31 X+P 32 Y +P 33 Z+P 34 P 21 X+P 22 Y +P 23 Z+P 24 P 31 X+P 32 Y +P 33 Z+P 34

		P 1 M
	=	P 3 M P 2 M
		P 3 M

Table 1 :

 1 Impact of the number of elements on the computation time.

	Number of elements	256	576	1024	1600
	Average 2D Error (px) 27.66 18.55 17.61 16.72
	Frame rate (fps)	29	17	9	5

http://www.itksnap.org


Jane Hunter
email: j.hunter@uq.edu.au

Chih-Hao Yu

Supporting Multiple Perspectives on 3D Museum Artefacts through Interoperable Annotations

Keywords: 3D annotations, tags, semantics, interoperability, ontologies

Increasing numbers of museums and cultural institutions are using 3D laser scanning techniques to preserve cultural artefacts as 3D digital models, that are then accessible to curators, scholars and the general public via Web interfaces to online galleries. Museums are finding the cost of providing metadata for such collections prohibitive and are keen to explore how they might exploit Web 2.0 social tagging and annotation services to capture community knowledge and enrich the contextual metadata associated with their collections. Although there exist some annotation services for 3D objects, they are designed for specific disciplines, not Web-based or depend on proprietary software and formats. The majority also only support the attachment of annotations to whole objects -not points, 3D surface regions or 3D segments. This paper describes the 3DSA (3D Semantic Annotation) system developed at the University of Queensland that enables users to attach annotations to 3D digital artefacts. The 3DSA system is based on a common interoperable annotation model (the Open Annotations Collaboration (OAC) model) and uses ontology-based tags to support further semantic annotation and reasoning. This common approach enables annotations to be re-used, migrated and sharedacross annotation clients and across different 3D and 2.5D digital representations of the one cultural artifact. Such interoperability is essential if cultural institutions are to easily harness knowledge from a broad range of users, including curators, students and remote Indigenous communities, with different client capabilities.

Introduction and Objectives

Advances in 3D data acquisition, processing and visualization technologies are providing museums and cultural institutions with new methods for preserving cultural heritage and making it more accessible to scholars, traditional owners and the public, via online search interfaces. Increasing numbers of museums are using 3D scanning techniques to overcome the limitations of 2D data representations and to improve access to high quality surrogates of fragile and valuable artefacts via the Internet [START_REF] Hunter | Using the semantic grid to build bridges between museums and indigenous communities[END_REF][START_REF]3D digital preservation of cultural heritages[END_REF][START_REF] Rowe | A prototype digital library for 3D collections: Tools to capture, model, analyze, and query complex 3D data[END_REF][START_REF] Isler | Building a 3D Virtual Museum of Native American Baskets[END_REF]. The trend is increasingly towards the use of 3D laser scanners to capture precise 3D digital models that can be accurately analysed, measured and compared. However there are a number of challenges that come with building online collections of 3D museum objects, making them accessible to different types of users and enabling their classification and the attachment of community knowledge through tags and annotations.

Firstly, the file size of the 3D digital objects is often problematic for many users who are unable to quickly and easily download and render the objects due to limited bandwidth, CPU, graphics cards or the need for specific 3D rendering software. Secondly, as the size of online collections of 3D artefacts grows, the ability to enable search and browsing across these distributed repositories becomes more difficult. Museums are finding the cost of providing metadata and rich contextual information for their collections prohibitive and are keen to explore how they might exploit social tagging and annotation services [START_REF] Chun | Steve.museum: An Ongoing Experiment in Social Tagging, Folksonomy, and Museums[END_REF]. High quality tags and annotations -attached to both the complete object as well as to specific segments or features -have the potential to significantly improve the relevance of retrieved search results. Although there already exist some annotation services for 3D objects, they are designed for specific disciplines or depend on proprietary software and formats. The majority also only support the attachment of annotations to the whole objects -not to 3D points, surface regions, 3D parts or segments (e.g., the handle on a pot).

Hence the aims of the work described here are to develop services to support the following:

 Workflows for streamlining the generation of multiple alternative digital representations (high resolution, medium resolution and low resolution) of each 3D museum object in high-quality, standardized and widely used formats;  Web-based, easy-to-use, 3D tagging/annotation tools that support the attachment of annotations to points, surface regions or 3D segments (i.e., meaningful parts or features) on a 3D model. The difficulty lies in specifying the particular feature of interest via simple drawing, selection and segmentation tools. For example, drawing the boundary of a 3D surface feature or a 3D segment can be very difficult and time consuming.  Tagging and annotation tools that enable annotations/tags to be automatically attached to, migrated between and displayed, for different digital versions (high, medium, low resolutions) of each museum artifact;  Semantic annotation tools -that use machine-understandable tags drawn from an ontology. Our aim is to use the CIDOC-CRM [START_REF] Jung | Immersive Redlining and Annotation of 3D Design Models on the Web[END_REF] ontology, which has been designed specifically for the museum community, but to extend it with discipline-specific sub-ontologies (e.g., Indigenous Carvings).

Ontology-based annotations are valuable because, in addition to supporting validation and quality control, they allow reasoning about the annotated resources, enabling it to become part of the larger Semantic Web;  A common model for attaching annotations to 3D artefacts regardless of their format. Such a model also enables re-use and display of annotations across different annotation clients. Our aim is to evaluate the Open Annotations Collaboration (OAC) model for supporting the migration of annotations between multiple versions of a 3D object and using different annotation clients.

156 Jane Hunter and Chih-hao Yu

Related Work

Most prior work in the field of 3D annotations has focused on the annotation of discipline-specific objects -for example, architectural and engineering CAD drawings [START_REF] Jung | Immersive Redlining and Annotation of 3D Design Models on the Web[END_REF][START_REF] Jung | Annotating and sketching on 3D web models[END_REF], 3D crystallography models [START_REF] Hunter | Collaborative Annotation of 3D Crystallographic Models[END_REF] and 3D scenes [START_REF] Kadobayashi | 3D Model Annotation from Multiple Viewpoints for Croquet[END_REF]. All of these systems enable users to attach annotations to 3D models and to browse annotations added by others, asynchronously. However they are all limited to the disciplinespecific format of the target objects. Adobe Acrobat 3D also provides a 3D JavaScript API that allows annotation of 3D CAD models or U3 objects stored in PDF using a proprietary SDK. However the documentation is lengthy and attaching annotations is a programmatic exercise [23]. A survey of existing systems failed to reveal any interoperable, collaborative, Web-based annotation systems for 3D models of museum artefacts, that enable descriptive text or semantic tags to be attached (either to the whole object or a point or region on the object) -and then saved to enable later, asynchronous searching, browsing and response, by other users.

Projects such as SCULPTEUR [START_REF] Addis | New Ways to Search, Navigate and Use Multimedia Museum Collections over the Web[END_REF], the Princeton 3D search engine [START_REF]Princeton 3D model search engine[END_REF] and Columbia Shape Search [START_REF] Hunter | A Framework to enable the Semantic Inferencing and Querying of Multimedia Content[END_REF] use a combination of machine learning (to extract colour, pattern and shape) and application semantics (who, what, where, when etc.) to automatically cluster 3D objects. However these projects fail to take advantage of communitygenerated tags and annotations drawn from ontology-directed folksonomies. Hunter et al [START_REF] Hollink | Evaluating The Application of Semantic Inferencing Rules to Image Annotation[END_REF][START_REF] Hunter | A Framework to enable the Semantic Inferencing and Querying of Multimedia Content[END_REF][START_REF] Little | Rules-By-Example -A Novel Approach to Semantic Indexing and Querying of Images[END_REF] have previously applied semantic inferencing rules to enable the automated high-level semantic annotation of 2D images from low-level automatically-extracted features -and demonstrated improvements in concept-based search performance. Hunter et. al. have also developed annotation tools for 3D museum artefacts, based on the Annotea model [START_REF] Schroeter | A Synchronous Multimedia Annotation System for Secure Collaboratories[END_REF]. But this previous work has only enabled the attachment of tags and comments to 3D points and/or views of the complete object.

Other relevant prior work is in the area of segmentation of 3D models [START_REF] Attene | Semantic Annotation of 3D Surface Meshes based on Feature Characterization[END_REF][START_REF] Shamir | A survey on mesh segmentation techniques[END_REF] and the attachment of semantic annotations to segments [START_REF] De Floriani | A Java3D framework for inspecting and segmenting 3D models[END_REF][START_REF] Attene | Part-based Annotation of Virtual 3D Shapes[END_REF]. Previous segmentation approaches have involved mesh segmentation approaches and manual or user-guided approaches [START_REF] Ji | Easy mesh cutting[END_REF][START_REF] Funkhouser | Modeling by example[END_REF]. The ShapeAnnotator [START_REF] Attene | Semantic Annotation of 3D Surface Meshes based on Feature Characterization[END_REF] focuses on automatic segmentation to separate a 3D object into different segments. The ShapeAnnotator is not Web-based and does not enable users to annotate whatever region they select -only pre-identified segments. It also does not display textures for 3D models, which makes unattractive to cultural institutions. Our aim is to adopt an approach similar to Ji et al [START_REF] Ji | Easy mesh cutting[END_REF] to perform the automated segmentation and to apply and evaluate it within the context of a specific collection of 3D museum artefacts.

As far as we are aware, there are currently no open-source tools that: enable Webbased semantic annotation of 3D museum objects; that use ontology-based semantic tags; or that enable easy tagging of points, surface regions or 3D parts on a 3D digital object. Finally we are unaware of any system that enables the easy migration of tags/annotations between different digital versions of the one 3D object -a critical requirement if museums are going to engage with users from a range of different communities and with access to variable computer capabilities.

Supporting Multiple Perspectives on 3D Museums Artefacts through Interoperable Annotations The case study in which different users from different backgrounds (curators, scholars, students, public) annotate and tag a museum object (represented in different digital formats) -and then share and aggregate those annotations -is an ideal case study for evaluating the OAC model. Fig. 2 below illustrates how the OAC is relevant to the 3DSA application through a simple example in which user "jane" attaches the textual annotation "Wik totem" to a point on a 3D object. This annotation is automatically migrated across the three digital representations of this object.

158

Jane Hunter and Chih-hao Yu

Case Study

To evaluate the proposed annotation services, we are currently using Indigenous wooden ceremonial sculptures from the Wik peoples of Western Cape York. This collection of wooden, ochre-painted sculptures is held in the UQ Anthropology Museum. Indigenous artists from Cape York are interested in emulating and extending the techniques used by artists from these earlier periods. They would like to be able to access high resolution 3D versions of the sculptures without having to travel to Brisbane for long periods. In addition, the UQ Art Museum is developing an exhibition around these sculptures, to open in 2010. The aim of this project is to work with the UQ Anthropology Museum curators, Indigenous artists from Cape York and the UQ Art Museum to develop a virtual collection of 3D models which can be used for remote access, collaborative annotation, knowledge sharing, exhibition development and the evaluation of this project's outcomes.

Implementation

Generating the 3D Models

The first phase of the project involves scanning each artefact using a Konica Minolta Vivid9i non-contact 3D laser scanner and generating the different 3D digital models using GeoMagic software. Each museum artefact is initially scanned into a VRML format, stored in Collada format using Autodesk Maya and converted into O3D format (Google's 3D scene graph API)) using Google's converter. The 2.5D file (FlashVR format) is generated by capturing a series of images from the O3D file. At this stage, the project has generated a sample set of Indigenous artefacts for evaluation purposes. More artefacts from a variety of backgrounds and materials, will be scanned in the future to more fully evaluate the search and indexing features.

A high quality 3D digital model for a cultural heritage artefact contains 50-200 MB of data and 20-50,000 polygons. However, many users don't have the bandwidth, computational power or graphics cards capable of downloading and rendering such objects in a timely fashion -or enabling real-time interaction (panning, rotating, zooming) with the 3D models. In order to support users with limited computation power or bandwidth, we generate four different representations of each artefact:  Archival quality 3D model (Raw 3D data): for storage purposes only, not accessible online.  High quality 3D model for users who have standard CPU and internet speed.  Low quality 3D model -compressed version for users with limited CPU, graphics card or slow internet.  2.5D VR object -non-3D version, suitable for users who do not have a graphical processor and with a very slow internet connection.

System Design and Implementation

Using the 3D objects generated via the scanning and conversion process described above, we have developed a Web interface to a gallery of objects. Users can search and browse the gallery of 3D objects via thumbnails, a tag cloud and keyword search. The 3DSA annotation prototype (shown in Fig. 4) is also accessible via a link from the project website's 3D gallery 1 . A high-level view of the system architecture is shown below in Fig. 3. 1 http://www.itee.uq.edu.au/~eresearch/projects/3dsa 160 Jane Hunter and Chih-hao Yu  2.5 VR object viewer -this was developed using Adobe Flex, a free, open source framework for building web applications using ActionScript 3.0.  Annotation storage -is implemented using AJAX and Danno, an HTTP-based repository that provides APIs for creating, updating, deleting and querying annotations and replies, and for bulk upload and harvesting of annotations [START_REF] Danno | [END_REF].  User interface -this was developed using AJAX, PHP and jQuery, a JavaScript Library that simplifies HTML document traversing, event handling, animating, and Ajax interactions for rapid web development [START_REF]jQuery Official Website[END_REF].

Fig. 4 shows a screen shot of the prototype in use. On the left hand side, are the different versions of the artefact being annotated -users choose the most appropriate for their environment. In the center is the display panel showing the currently selected 3D object and attached annotations. On the right hand side is the annotation search and browse panel. Clicking on the "New Annotation" button displays a new panel that enables users to enter the contextType of the annotation (object, point, region, segment), the Type of annotation (tag, comment, query, feedback) and the body of the annotation. The creator and date/time information is also captured. The complete details/metadata for a chosen annotation are displayed in the bottom centre panel.

Fig. 4 Screen shot of the 3DSA Annotation Prototype

After the user enters the annotation data, they can specify the context/point on the object to which it is attached. (Region and Segment annotations are still under development). After saving the annotation, the system then determines if there are other representations of this artifact available. If there are, then the annotation context is re-calculated to automatically migrate the annotation to the other formats (e.g., from 3D high-res to 2.5D Flash). For example transferring a 3D coordinate (X, Y, Z) to 2D coordinate (X, Y), the formula below is implemented [START_REF] Koci | Computer Graphics Unveiled -World, View and Projection Matrix Unveilded[END_REF]: . ; ;

Supporting Multiple Perspectives on 3D Museums Artefacts through Interoperable Annotations

Discussion

Feedback from museum curators on the 3DSA system has been extremely positive.

They are very excited about the added dimensions and details that 3D scanning can offer but they realize that there are a number of barriers preventing wide-spread adoption of 3D digital formats in online museum collections, including: the time it takes to generate the 3D objects, the size of the files, the time to download and render the files and the graphical and computational power required to support real-time rendering and interactive panning, zooming and rotating. In this paper we firstly describe workflows to streamline the generation of multiple 3D/2.5D digital representations of museum artefacts to satisfy the anticipated range of users and users' computer capabilities, whilst still maximizing quality and minimizing effort.

We have then demonstrated a prototype to enable the attachment of communitygenerated tags and annotations to 3D digital objects. We have also demonstrated how the Open Annotations Collaboration Model can be extended and applied to support interoperability of annotations across clients, across target objects in different digital formats and their attachment to segments (points, regions, 3D parts) of 3D/2.5D digital objects. The complex algorithms for mapping annotations between objects of different resolution have been comprehensively tested and have demonstrated high performance -both speed and accuracy. User evaluations of the annotation prototype have identified a number of improvements to the user interface, including the need for greater consistency in annotation displays between the O3D and Flash plug-ins.

Future Work and Conclusions

In this paper we describe a Web-based 3D annotation service that does not entail a steep learning curve to create/edit/view annotations attached to 3D digital objects. Annotations can be easily created and attached to 3D digital objects via the O3D or Flash browser plug-ins. Annotations can be attached to 3D objects in different formats (high-res, med-res, low-res (2.5D)) and are automatically migrated between them. This enables both users with access to high-end computers and users with slow computational or graphical processors or limited bandwidth, to use the 3DSA tool and to share annotations across platforms and 3D digital formats.

Future aims include adding support for the new WebGL format that will be supported by major browsers (Safari, Chrome, Firefox, Opera). We also plan to explore how users attach annotations to surface regions and 3D segments. In addition, we plan to allow tags to be extracted from folksonomies and/or the CIDOC/CRM ontology (ontology-directed folksonomies), to support faceted search. As such, this project differs from projects such as SCULPTEUR, the Princeton 3D search engine and Columbia Shape Search, in which indexing is entirely based on machine learning and semantics but fails to take advantage of folksonomic tags. By combining both usergenerated tags and automatic feature extraction, we will significantly enhance the discovery of 3D cultural artefacts and associated content. The outcome will be an online digital repository/gallery of 3D cultural heritage artefacts enriched with both 162 Jane Hunter and Chih-hao Yu manually-generated and automatically-generated metadata to enable fast accurate search and retrieval of 3D objects by both museum experts and the general public.

Finally, we have begun experimenting with the QR codes [33] to enable museum visitors to retrieve community-generated annotations via their iPhones. QR codes (small printable tags) can be generated from the 3DSA web pages, and attached to the physical museum artefacts in the exhibition. This enables museum visitors with the QR code app on their iPhone, to retrieve the related 3DSA web page that displays the 3D digital version with aggregated annotations. This is a very exciting development with significant potential that will also require further testing and evaluation.

To conclude, the 3DSA system represents a highly innovative approach to cultural heritage that combines the best of Web 2.0, Semantic Web and mobile technologies to maximize the preservation, capture, dissemination and re-use of knowledge about cultural heritage.

2 . 1 The

 21 Open Annotations Collaboration (OAC) Data ModelThe lack of robust interoperable tools for annotating across heterogeneous repositories of digital content and difficulties sharing or migrating annotation records between users and clients -are hindering the exploitation of digital resources by many scholars. Hence the Open Annotations Collaboration (OAC) was established to facilitate the emergence of a Web and Resource-centric interoperable annotation environment that allows leveraging annotations across the boundaries of annotation clients, annotation servers, and content collections. To this end, an annotation interoperability specification consisting of an Annotation Data Model (Fig.1) has been developed. Fundamental principles that were adopted by the OAC include:  The core entities of an annotation (Annotation, Content, Target) are independent Web resources that are URI-addressable and hence discoverable and re-usable;  The Annotation Target (the object being annotated) and the Annotation Content (the body of the annotation) can each be any media type;  Annotation Targets and Content are frequently segments of Web resources;  The Content of a single annotation may apply to multiple Targets or multiple annotation Contents may apply to a single Target;  Annotations can themselves be the Target of further Annotations.

Fig. 1 .

 1 Fig.1. The Alpha OAC Data Model[START_REF]CIDOC Conceptual Reference Model[END_REF]

Fig. 2 .

 2 Fig. 2. Instance of the OAC model within the 3DSA application

Fig. 3 .

 3 Fig. 3. Screen-shot of the Web-based 3D Annotation prototype 3DSA The Annotation prototype was developed using a combination of Web 2.0 technologies and third party services including:  3D viewer -Google's O3D scene graph API, provides a browser plug-in with a shader-based, low-level graphics API and a high level Javascript library. O3D is flexible, extensible [17], cross-compatible, open source and Google's proposal as an open Web standard for 3D [18].

Supporting Multiple Perspectives on 3D Museums Artefacts through Interoperable Annotations

Acknowledgments

. The work described in this paper has been funded by Microsoft Research Asia through the e-Heritage program and through a University of Queensland Major Equipment and Infrastructure (MEI) grant. The Open Annotations Collaboration component has been funded by the Andrew W. Mellon Foundation.