Adnane Boukhayma
email: adnane.boukhayma@inria.fr

Edmond Boyer
email: edmond.boyer@inria.fr

Video based Animation Synthesis with the Essential Graph

We propose a method to generate animations using video-based mesh sequences of elementary movements of a shape. New motions that satisfy high-level user-specified constraints are built by recombining and interpolating the frames in the observed mesh sequences. The interest of video based meshes is to provide real full shape information and to enable therefore realistic shape animations. A resulting issue lies, however, in the difficulty to combine and interpolate human poses without a parametric pose model, as with skeleton based animations. To address this issue, our method brings two innovations that contribute at different levels: Locally between two motion sequences, we introduce a new approach to generate realistic transitions using dynamic time warping; More globally, over a set of motion sequences, we propose the essential graph as an efficient structure to encode the most realistic transitions between all pairs of input shape poses. Graph search in the essential graph allows then to generate realistic motions that are optimal with respect to various user-defined constraints. We present both quantitative and qualitative results on various 3D video datasets. They show that our approach compares favourably with previous strategies in this field that use the motion graph.

Introduction

3D animation has become a crucial part of digital media production with numerous applications, in particular in the game and motion picture industry. Traditionally, virtual characters are created and animated either manually with, for instance user defined keyframes, or automatically with motion capture data. While manual animations are usually tedious and require artistic expertise, motion capture data allows to animate characters with real motion information extracted from real performances. In addition to significantly reduce the animation cost, the benefit of motion capture data also lies in the fact that movements are real and, therefore, ensure realism to the created animations. Go-ing a step further, recent seminal works in computer animation [6] propose to bypass purely virtual characters and to use real videos for both the creation and the animation of characters. The advantage of this strategy is twofold: it reduces the creation cost and increases realism by considering only real data. Furthermore, it allows to create new motions, for real characters, by recombining recorded elementary movements. In this paper, we consider this synthesis of real motions using videos and propose a new solution to automatically build animations that are as real as possible.

Multi-view capture systems, e.g. [26], can produce 3D videos of human movements. In these 3D videos, shape information is generally encoded in the form of temporal mesh sequences, coherent or not. In order to recombine elementary movements, motion information could be parametrized using skeletal articulated models, as with traditional motion capture systems, and concatenated based on such parametrization. While methods exist that provide articulated motion information, e.g. [START_REF] Vlasic | Articulated mesh animation from multi-view silhouettes[END_REF][START_REF] Gall | Motion capture using joint skeleton tracking and surface estimation[END_REF], this strategy suffers anyway from two drawbacks: First the identification of such information is difficult to perform robustly with generic surfaces that do not always evolve according to the assumed articulated motion model, as with clothes for instance. Second, the use of an intermediate skeletal model makes it difficult to guarantee realism for transitions that finally concern surfaces around skeletons. Another strategy is to avoid the intermediate motion model and to directly consider surfaces or meshes. This is the direction taken by [START_REF] Huang | Human motion synthesis from 3d video[END_REF] who proposed to extend motion graphs, originally designed for skeletal motion capture data [START_REF] Kovar | Motion graphs[END_REF], to structure and recombine motion information with mesh sequences. In such a graph, edges connect consecutive meshes within a sequence and new edges are added between pair of sequences and with respect to a similarity cost between meshes. Although simple and intuitive, motion graphs do not yet guarantee global optimality of created motion paths since such paths are composed of locally optimal edges, i.e. between two sequences, where other paths, through edges not in the motion graph, with better global costs can exist. In order to find such paths and to optimally exploit all the available shape poses, a fully connected graph must be considered.

In light of this, we consider animations that are globally optimal with respect to a defined realism criterion. This criterion derives from physical considerations and takes into account a surface interpolation cost, that measures the amount of surface deformation along a motion segment, as well as a duration cost that accounts for the number of frames of a segment. The first cost tries to preserve shape consistency along a motion segment while the second tries to minimize the number of poses within a segment. Our approach first builds a fully connected graph where every shape pose is connected to all others and where edges weight direct transitions between poses with respect to the realism criterion. To estimate the edge weights, each transition is optimized through dynamic time warping and variable blended segments lengths. In a second step, the graph is pruned and the essential subgraph, that is the union of all shortest path trees rooted at every node, is extracted. The essential subgraph is an optimal structure that contains only the necessary edges to generate the most realistic graph transitions between all pairs of input frames. Finally, the resulting structure is used to generate motion that satisfies user-specified spatial, temporal and behavioural constraints as demonstrated in our results, by solving a standard search optimization problem over the essential graph and with the appropriate cost function. At a lower level, our approach combines mesh non-linear interpolation, with 2D rigid alignments to generate the spatially continuous motion sequence corresponding to a graph walk in the essential subgraph.

To summarize, our contribution is twofold:

• We introduce a transition approach that combines dynamic time warping and variable length blended segments to generate mesh based interpolated transitions that are optimal with respect to a realism criterion.

• We propose the essential graph as an optimal structure to organize several pose sequences of a person movements and from which minimal cost paths are easily identified between two given poses.

In order to evaluate the benefit of the essential graph over the motion graph, we compare both graph structures in a similar context, quantitatively with our criterion, and qualitatively with visual results (see also the accompanying video).

The remainder of the paper is as follows. Section 2 reviews related work. In section 3, we present our graph representation and we explain motion synthesis in Section 5. Section 6 compares our approach with a standard motion graph based strategy and shows results before concluding in Section 7.

Related work 2.1. Motion Data Structures

Traditional motion capture systems provide sparse information on moving shapes in the form of marker positions. Using such markers positioned at joint locations of, for example a human body, it is possible to track the poses of an associated skeletal model. A large body of work is considering such input data to animate virtual characters. To this aim, motion graphs [START_REF] Kovar | Motion graphs[END_REF] are largely used to organize and structure recorded movement sequences of a shape. A motion graph is composed of nodes that represent shape poses and of edges that represent transitions between them. To build such a graph, every consecutive nodes in a temporal sequence are connected. Edges are added to this graph by considering a pose and velocity similarity matrix that encode all possible pairs of poses between two sequences. Local minima found in this matrix, with sometimes thresholding to reduce the number of resulting transitions, define the new edges in the motion graph.

Following motion graphs, several solutions have been proposed in the literature. [START_REF] Lee | Interactive control of avatars animated with human motion data[END_REF] builds first a directed graph in a similar manner to a motion graph, then subsequently builds a statistical model over it for a more intuitive control. [START_REF] Arikan | Interactive motion generation from examples[END_REF] also creates a graph where nodes represent sequences, and transition edges are added between sequence poses if a similarity cost between them is lower than a user specified threshold. A hierarchical randomized search is used then to generate motions. [START_REF] Safonova | Construction and optimal search of interpolated motion graphs[END_REF] introduces a structure called interpolated motion graphs that consists of interpolating time-scaled paths within a standard motion graph. [START_REF] Zhao | Achieving good connectivity in motion graphs[END_REF] increases the connectivity in a motion graph by using multi-target blending to generate intermediate interpolated motions between some of the dataset sequences and building a well connected motion graph that incorporates these new motions.

[20] constructs an optimization-based graph combining constrained optimization and motion graphs. In the method we present, we also use a graph representation that connects frame poses in temporal sequences. However we consider mesh vertices instead of skeleton joint locations and, more importantly, our graph representation enables paths between any two frames that satisfy global optimality, over pose recombinations, and with respect to surface deformation and transition duration. Some statistical approaches have been proposed to solve the animation problem for skeletal data. [START_REF] Tanco | Realistic synthesis of novel human movements from a database of motion capture examples[END_REF] applies dimension reduction and clustering to the input dataset and constructs a Markov chain with these clusters as states in a first level. A second level consists then of a hidden Markov model that relates the states of the Markov chain to the motion examples. Given a source and destination key frames, the corresponding sequence of clusters is found in the first level, and the most likely succession of motion segments is found in the second. More recently, [18] proposes a graph where nodes represent motion primitives and edges transitions between them. Each node stores a statistical model learned from similar motion segments associated to the same primitive and a transition distribution function is associated to every directed edge. However, unlike skeletal motion capture data and besides their very high dimensionality, 3D mesh motion datasets that are currently available represent mostly limited sets of movements. Thus, such statistical strategies do not adapt to this specific type of data. Additionally, and unlike [18], our solution also solves for random acyclic motion, such as an unstructured dancing sequence (see results for Cathy), which seems hard to decompose into distinctive simple motion primitives. In a graph-less approach, [START_REF] Ikemoto | Quick transitions with cached multi-way blends[END_REF] clusters motion segments and pre-compute a table defining intermediate segments that are used to blend all pairs of cluster medoids. In order to generate a transition from a source segment to a target segment, these two segments are thus blended together with their respective cluster medoid intermediaries. Although this work enables, in principle, transitions between all pairs of frames in the dataset, it requires transition scoring, motion segment clustering and multi-way frame blending that would be difficult to achieve with 3D mesh sequences and without contact information.

Motion Similarity

Measuring motion similarity is an important aspect in animation synthesis. Although [START_REF] Kovar | Automated extraction and parameterization of motions in large data sets[END_REF] argued that logical motion similarity does not necessarily imply numerical motion similarity, most of the works mentioned previously defined some quantitative pose and velocity similarity metric to estimate motion similarity. For instance, [START_REF] Kovar | Motion graphs[END_REF] computes a weighted sum of squared distances between point clouds driven by the skeleton and formed over a window of frames that are 2D rigidly aligned, while [START_REF] Lee | Interactive control of avatars animated with human motion data[END_REF] uses a weighted sum of euclidean differences of joint velocities, skeleton root positions and geodesic distances between joint orientations. Our approach considers mesh based pose distances but is independent of the distance function used for that purpose.

Motion Transition

Another important component of motion synthesis is the generation of transitions between sequences. Gradual frame blending remains yet a reasonable and intuitive solution that is widely used in the literature, either in a start-end [START_REF] Kovar | Motion graphs[END_REF], center-aligned [START_REF] Arikan | Interactive motion generation from examples[END_REF] or left aligned [START_REF] Lee | Interactive control of avatars animated with human motion data[END_REF][START_REF] Safonova | Construction and optimal search of interpolated motion graphs[END_REF] transition form. However, it might generate unpleasant results if incorrectly applied, especially with linear interpolation and unless costly space-time constraints and inverse kinematics are used as in [START_REF] Rose | Efficient generation of motion transitions using spacetime constraints[END_REF]. These limitations can anyway be substantially reduced with motion dynamic time warping. Following a strategy similar to [START_REF] Kovar | Flexible automatic motion blending with registration curves[END_REF], we use dynamic time warping but extend the framework to transitions between mesh sequences. In addition, inspired by the study of interpolated transitions in [START_REF] Wang | Synthesis and evaluation of linear motion transitions[END_REF] that emphasizes the importance of a suitable transition duration, we allow such duration to vary during a transition.

Mesh Sequences

Only a few works consider yet mesh sequences as input data for motion synthesis. They were first introduced in [START_REF] Huang | Human motion synthesis from 3d video[END_REF] in association with motion graphs and frame juxtaposition for transitions, with therefore the limitations mentioned before for transitions and motion graphs. [START_REF] James | Mesh ensemble motion graphs: Data-driven mesh animation with constraints[END_REF] also uses motion graphs but over separate groups arranged in a tree-structured kinematic hierarchy forming the global object. Linear interpolation in the local coordinate frame of each group was sufficient for their type of data. In [START_REF] Zheng | One-to-many: example-based mesh animation synthesis[END_REF], the animation is solved in the skeleton domain using linear blend skinning. Motion Transitions are selected by simple thresholding of a transition cost calculated using the pose parameters and their first derivatives, as in [START_REF] Arikan | Interactive motion generation from examples[END_REF]. Our objective is to solve the animation in the mesh domain, remov-ing therefore the issue of mesh/skeleton conversion, and we propose an elaborated model for the selection and generation of transitions.

More recently, in a work similar to [START_REF] Kovar | Automated extraction and parameterization of motions in large data sets[END_REF] with skeletal data, [5] achieves motion synthesis by temporally aligning and blending logically similar 3D mesh motion sequences, and mapping the blend weights to a high level parameter, thus creating a parametrized motion space. A Parametric motion graph is then built by connecting several parametric motion spaces through pre-computed transitions, as in [9] for skeletal data, or by computing optimal transitions at runtime, as in [6] for 3D meshes. The theory behind parametric motion graphs is similar to that of Fat graphs [START_REF] Shin | Fat graphs: constructing an interactive character with continuous controls[END_REF], inspired by the work of [START_REF] Gleicher | Snaptogether motion: Assembling run-time animations[END_REF]. These methods allow motion synthesis with precise control but only for specific input data and require a high level of supervision. Our objective is different and improves over [START_REF] Huang | Human motion synthesis from 3d video[END_REF] with globally optimal motion sequences generated from a general set of input sequences.

Graph model

This section details the steps involved in the construction of the essential graph for mesh based motion segments. The input data is a set of temporally aligned sequences of 3D triangulated meshes, i.e. meshes present the same topology and vertex connectivity over all sequences. These sequences represent a model, typically but not necessarily a human, undergoing arbitrary movements with no prior restrictions on the nature of the movements. It should be noticed here that while we consider meshes as input, the graph construction is independent of the pose model used and could be applied with other models including articulated models.

A directed weighted graph structure is drawn from the input sequences, where nodes are sequence frames, corresponding to shape poses, and edges represent possible transitions between them. Edge weights account for both the surface interpolation cost of transitions and their duration. Initially, edges in the graph connect successive frames in the input sequences, as shown in figure 1. Since these edges correspond to natural transition, their surface interpolation cost is low, zero in practice in our implementation, and their duration cost is one time unit (assuming uniform temporal sampling). From this initial graph, a fully connected graph is built where additional edge weights are estimated using a static pose similarity metric and dynamic time warping, as detailed in section 3.2. In a last step, the essential graph is extracted from the fully connected graph by pruning edges that do not contribute to minimal cost paths in the graph.

Pose similarity metric

We define a static distance function between two given shape poses. Such basic distance will be used further at various stages of our approach, for instance when estimating the cost of a dynamic transition that involves several intermediate poses. Given two poses i and j, we first rigidly align them by finding the rigid transformation that minimizes the weighted sum of squared distances between mesh vertices, where the rigid transformation is composed of a translation in the horizontal plane (i.e. the plane parallel to the motion) and of a rotation around the vertical axis. Weights are used, for instance, to give more importance to torso vertices with humans. Once aligned, one could take the residual of the alignment cost as the distance between the poses. However, this residual does not account for the mesh geometry [START_REF] Sorkine | Laplacian surface editing[END_REF] . We use instead local deformations [2] or deformation gradients as referred to in [START_REF] Sumner | Deformation transfer for triangle meshes[END_REF]32], as explained below.

For every pair of corresponding triangles (v 1 , v 2 , v 3 ) and (v 1 , v 2 , v 3 ) in a pair of meshes, we compute the following unique transform matrix:

T = (v1 -v3, v2 -v3, n) -1 . v 1 -v 3 , v 2 -v 3 , n , (1)
where n and n are the triangle unit normals. We perform polar decomposition on this linear transformation matrix to extract the orthogonal rotation component R m , and symmetric scale/shear component S m for triangle m, and also store them for later purposes such as pose interpolation:

T = RmSm. (2)
Combining the Riemannian metric of the Lie goup of rotations SO(3), and Frobenius norm for symetric 3x3 matrices, we define our pose similarity metric between frames i and j as follows:

d(i, j) = m∈T riangles 1 √ 2 log (Rm) F + wm Sm -I 3 F . ( 3
)
Through weighting factors w m , we give more importance to the rotation term. In practice, we use the same value w m = 0.01 for all mesh triangles. In order to validate this distance function, we have conducted experiments with skeleton based mesh animations for which skeleton pose distances are assumed to capture exact shape pose distances. Comparisons between distance matrices obtained with pairs of sequences show that the above distance function gives better results than the sum of squared distances mentioned previously, i.e. distances (3) present higher correlations with skeleton pose distances.

Graph edge weights

Weights attributed to edges in our graph should ideally capture the realism of the transitions they represent. Assuming that a realistic transition should involve as little surface deformation as possible, we introduce a metric that measures the minimum surface interpolation cost between any pair of nodes in the graph. It involves several intermediate poses for that purpose, which makes it different from the static pose similarity. This metric, in addition to the

Pose distance matrix

Figure 2. In order to generate an interpolated transition between frame i and j, we gradually blend source and destination segments [i, i + l i i,j -1] and [j -l j i,j + 1, j] using dynamic time warping that finds the minimum-cost path joining element (i; j -l j i,j + 1) to element (i + l i i,j -1; j) in the pose distance matrix between the two segments frames. This path should be continuous, not reverse direction, and not exceed 3 consecutive vertical or horizontal steps. The resulting path defines the temporal warps w i i,j and w j i,j .

transition duration, allows us to quantitatively evaluate the realism of a transition.

In order to generate a smooth interpolated transition from frame i in a source sequence to a frame j in a destination sequence, we consider a window of successive frames of size l i in the source sequence starting at frame i: [i, i + l i -1], and a similar window of successive frames of size l j in the destination sequence ending at frame j: [j -l j +1, j]. These are the source and destination segments whose frames are to be blended gradually so as to generate a smooth transition between frames i and j. First, these two segment frames are temporally aligned with warps w i and w j respectively and with respect to the pose metric defined previously in section 3.1. We use a standard dynamic time warping algorithm [19] to estimate the best temporal warps. In addition, following [START_REF] Wang | Synthesis and evaluation of linear motion transitions[END_REF] who argued that a transition duration in skeletal motion interpolation should be comprised between a third of a second and 2 seconds, we allow segment lengths l i and l j to vary between boundaries l min and l max that correspond to these values. We choose the transition with the least total surface deformation cost D(i, j) through the interpolation path (see figure 2).

D(i, j) = min l i ,l j ,w i ,w j ,L t∈ 0,L d(w i -1 (t), w j -1 (t)), (4)
where d(, ) is the pose similarity metric defined in equation (3), and L is the transition duration, i.e. the length of the interpolation path found by the dynamic time warping optimization (see figure 2).

Since the transition duration L is uniquely defined for a given set of values (l i , l j , w i , w j ), expression (4) rewrites:

D(i, j) = min l i ,l j ∈ l min ,lmax [ min w i ,w j t∈ 0,L d(w i -1 (t), w j -1 (t)]
Dynamic time warping

.

The optimal parameters found with the above optimization, i.e. (l i i,j , l j i,j , w i i,j , w j i,j , L i,j ), will be used later on for motion synthesis.

For each pair of nodes i and j in the graph, we define the weight E ij of the directed edge (i, j) as the weighted sum of the optimal surface deformation cost D i,j = D(i, j) and the associated duration cost L i,j : E ij = D i,j + αL i,j . In the case where frames i and j belong to the same sequence, with i < j, it might be unnecessary to consider an interpolated transition if its cost is greater than α(j -i), that is the cost of going from i to j through the original motion sequence. The following expression summarizes the definition for the edge weight E i,j between poses i and j. If i and j do not belong to the same sequence :

Ei,j realism = Di,j surface deformation + α Li,j duration , (5)
Else :

Ei,j = min[α(j -i), Di,j + α Li,j], i < j.

The weight α represents the ratio of tolerance between surface deformation and transition duration. This user defined coefficient allows for some flexibility on the admissible surface deformation during a transition and with respect to time duration.

At this stage all nodes are connected in the graph with directed weighted edges, hence forming a complete digraph (see figure 1). The resulting structure is analogous to a quasi-semi-metric space, (I, E), where I is the set of nodes and E : I × I → R + is the asymmetric function defined in equations( 5) and(6). In the next stage, we proceed with the extraction of the essential subgraph from this complete digraph.

Essential subgraph

In a traditional motion graph, edges between sequences are obtained by selecting minima in transition cost matrices between pairs of sequences. This strategy is intuitive but yet not globally optimal, as transitions between sequences other than minima might give better total cost to a graph walk if the minimized criterion considers also duration for instance, which is an important constraint for motion synthesis. We propose therefore a global and principled strategy that consists of extracting the best paths between any pairs of poses and to keep only edges in the graph that contribute to these paths. This corresponds to extracting the essential sub-graph from the complete digraph induced from the input sequences. Unlike previous methods, ours ensures the existence of at least one transition between any two nodes in the graph, which potentially yields to a better use of the original data with less dead ends trimming.

For every pair of nodes in the graph, we use Dijkstra algorithm to find the path with the least cost joining the source node to the destination node. The cost of a path p = [n 1 , n 2 , ..., n N ] that goes through nodes n 1 , n 2 , ..., n N is defined as:

J(p) = J([n1, n2, ..., nN ]) = i∈ 1,N -1 En i ,n i+1 . (7)
Once the optimal paths joining all pairs of nodes are found, all edges that do not belong to any of these paths are pruned. This gives an optimally connected graph which contains only the necessary edges to connect every pair of nodes with the best possible path cost in terms of realism (see figure 1). This resulting structure is also referred to as the union of shortest path trees rooted at every graph node, and its density is proportional to the α factor introduced in equations 5 and 6. The following sections explain how to use this structure to generate new animations.

High-level constraints

We consider in this part constrained navigation in the essential graph with various user-specified constraints such as spatial, temporal and behavioural constraints. We cast motion extraction as a graph search problem that consists of finding the walk p = [n 1 , n 2 , ..., n N ] with minimal total error cost J c (p) as follows: [START_REF] Gleicher | Snaptogether motion: Assembling run-time animations[END_REF] where j c ([n 1 , ..., n i-1 ], n i ) is a scalar function evaluating the additional error of adding node n i to walk [n 1 , ..., n i-1 ] with respect to the user specification. Since a graph node might be visited more than once in this search, a halting condition must be specified to prevent the search from infinite recursion. In order to demonstrate the interest of essential graphs for animation purposes, we implement two scenarios with different types of constraints. In both scenarios, the graph search was solved using Depth-First algorithm with Branch-and-Bound to reduce the computational complexity.

Jc(p) = Jc([n 1 , n 2 , ..., n N ]) = i∈ 1,N jc([n 1 , ..., n i-1 ], n i ),
3D Behavioural path synthesis: In this scenario (see figure 5) the user provides a 3D curve that the character's center of mass should follow as closely as possible. Additionally, some parts of this path may impose specific types of motion taken from the dataset. This kind of constraints better adapts to datasets with a variety of basic motions involving locomotion activities, and for which there are significant displacements of the character in space. This is the case with our dataset Thomas. In this example, the cost function jc measures the 3D distance between the added frame to the current generated path and the point along the input 3D curve with the same arc length as the added frame along the generated path.

Pose/Time constraint: In this scenario the user provides a sequence of poses with associated times of occurrence. The search generates the motion sequence that satisfy as much as possible these pose/time constraints. This type of constraint adapts well to sequences of random unplanned activities, such as dance footages as in our dataset Cathy. The search problem is solved here for every two successive query poses separately, and the cost function j c measures the duration cost of adding a node to the current generated path. The halting condition occurs when the duration of the travelled path between source and destination poses exceeds the desired duration.

Motion synthesis

In this section, we explain how a walk in the essential subgraph is converted into a continuous stream of motion in the form of a 3D mesh sequence. A walk path is represented by a node sequence, where every pair of successive nodes should correspond to an edge in the essential subgraph. We browse the path and sequentially generate the purely original or newly interpolated motion segments corresponding to every pair of consecutive nodes in the path. Interpolated segments are generated using the optimal transition scheme introduced in section 3.2. That is, temporally warped source and destination motion segments are blended by gradually aligning and interpolating the matched frame meshes as well as the displacement of their respective centres of mass. Finally, we perform a rigid alignment (as explained in section 3.1) at the junction between two consecutive motion segments to obtain a spatially continuous motion stream.

Pose interpolation: In order to interpolate frame meshes, we use a variant of Poisson shape interpolation [START_REF] Xu | Poisson shape interpolation[END_REF]. Our experiments demonstrate that this strategy performs better compared to linear vertex interpolation or as rigid as possible approaches [START_REF] Sorkine | Laplacian surface editing[END_REF]. Using gradient field manipulation [START_REF] Botsch | On linear variational surface deformation methods[END_REF] notations, the 3 × 3 per-face gradient of the mesh for triangle m can be expressed as follow:

Gm =   (v1 -v3) T (v2 -v3) T n T   -1   1 0 -1 0 1 -1 0 0 0     v1 T v2 T v3 T   . (9)
A global 3M × N gradient operator G can then be yielded, where M and N are the total numbers of mesh triangles and vertices respectively:

   G1 . . . GM    = G    v T 1 . . . v T N    . (10)
In order to interpolate poses with interpolation parameter λ ∈ [0, 1], the interpolated rotation and scale/shear, extracted previously from per-face gradient deformations (see section 3.1), are applied to each per-face gradient which yields new gradients Gm :

Tm = e λ log(Rm) ((1 -λ)I3 + λSm) , (11) Gm = TmGm.

(

) 12
The following standard Poisson system is then solved for new mesh vertex positions ṽ1 ... ṽ1 , with a Dirichlet boundary condition imposing to the interpolated mesh center of mass to be at the same location as the original one.

G T DG ∆    ṽT 1 . . . ṽT N    = G T D div    G1 . . . GM    , ( 13
)
where D is a diagonal 3M × 3M mass matrix containing the triangle areas. We note that the left hand operator of this equation is equivalent to a discrete Laplace-Beltrami operator with cotangent weights. To insure the unicity of the solution, we perform a double interpolation using the source and target meshes and we linearly interpolate the resulting meshes.

Results

To evaluate our framework, we recorded two datasets of temporally consistent mesh sequences, with 5000 vertices and 10000 faces per mesh, and a frame rate of 50fps. These datasets were obtained using multi-view reconstruction and temporal tracking. The Thomas dataset contains 2633 frames of a male actor performing basic locomotion activities, and the Cathy dataset has 1910 frames of a female actress performing random dancing. We also applied our method to standard datasets of 3D mesh sequences, such as Dan and JP datasets [START_REF] Starck | Surface capture for performancebased animation[END_REF] [4], the Capoeira dancer dataset [26] and the Adobe dataset [START_REF] Vlasic | Articulated mesh animation from multi-view silhouettes[END_REF]. Transition approach: Our transition approach combining dynamic time warping and variable length blended segments offers substantial improvements in the visual results.

Compared to a standard interpolated transition, our transitions show less visual flaws such as surface distortion (see figure 3) and foot-skate, and also compensates for the differential in velocity between source and destination motions through temporal warping. Graph structure: Given a dataset of mesh sequences, we want to generate motions joining all frames minimizing a joint cost of surface interpolation and duration. To this end, we construct an essential graph and a motion graph, and compute the costs of optimal paths joining every pair of frames in the dataset. In order to compare graph structures independently of the transition approach, we use the same transition cost for both methods. To construct a motion graph, we compute transition cost matrices between all pairs of sequences and select the local minima within them as transition points. In the original paper implementation, it is also recommended to only accept local minima below an empirically determined threshold to reduce the computational burden. We deliberately ignore this measure to obtain a highly connected motion graph to better challenge our method. Note that we do not compare to existing extensions of the motion graph since our primary objective is to evaluate the initial structure that is used to select optimal transitions and we believe that many of these extensions could anyway apply to the essential graph as well. Figure 6 presents the total costs of all the optimal paths using both our method and the standard motion graph. The plots show clearly that our method outperforms standard motion graphs quantitatively for various values of the α parameter that weights surface deformation and path duration contributions in the cost. Additionally, we show some visual results where motion graphs fail to find graph walks as short and costless as essential graphs (see figure 4).

Conclusion

We presented a new strategy for automatic motion generation using temporally aligned 3D mesh sequences. This method introduces the essential graph as the organizing data structure for motion information. This structure identifies all the shortest paths in the fully connected graph of shape poses. It appears to be a good alternative to motion graphs that improves realism and better exploits the input information. In addition, the method proposes interpolated transitions between 3D surface meshes in place of frame concatenations.

Our contributions also include an approach to estimate frame to frame transition using Poisson pose interpolation. It combines variable-length source and destination motion segments along with dynamic time warping. In addition, we present a new motion transition cost function that evaluates a realism criterion. Although there is no standard objective way of measuring motion transition realism, neither for skeletal data nor for 3D surface data, other than perceptual evaluation, the criterion that we introduced in this work achieved satisfactory results in that respect and over the datasets we experimented. In practice, we have observed only very few mesh distortions and abrupt changes in the generated motions while such artifacts are often present with standard interpolated transitions.

Nonetheless, we have also experienced artifacts which might appear during transitions and such as foot-skate, which is a common issue in motion synthesis with multitarget blending. With skeletal data, this issue is partially dealt with by annotating the input data with contact information and taking this annotation into consideration while generating transitions, and also by applying inversekinematics on transitions to erase the foot-skate effect from them [START_REF] Kovar | Footskate cleanup for motion capture editing[END_REF]. Although mesh sequence annotation seems to be more complicated, a similar approach could be applied on 3D mesh sequences.

Figure 1 .

 1 Figure 1. Overview of the proposed video based animation synthesis pipeline.

Figure 3 .

 3 Figure 3. (a) Our transition with Dynamic time warping and variable length blended segments, (b) Standard interpolated transition, both using Poisson pose interpolation

Figure 4 .

 4 Figure 4. Illustration of motion graphs failures to find a graph walk as short and costless as the essential graph regardless of the transition approach. Input poses are in green. Note that input destination pose rotation around the vertical axis is estimated by the algorithm in both cases. (a) Essential graph, (b) Motion graph.

Figure 5 .Figure 6 .

 56 Figure 5. 3D Behavioural path synthesis (Section 4). Green meshes are original and red ones are interpolated.


http://submissions.mirasmart.com/ISMRM2017/ViewSubmission.aspx?sbmID=6048 Double-Spoke Slab-Selective Ramp Pulse Design for UHF TOF MR Angiography Double-Spoke Slab-Selective Ramp Pulse Design for UHF TOF MR Angiography Gaël Saïb , Vincent Gras , Franck Mauconduit , Nicolas Boulant , Alexandre Vignaud , Denis Le Bihan , Laurent Le Brusquet , and Alexis Amadon CEA/DRF/I2BM/NeuroSpin/UNIRS, Gif-Sur-Yvette, France, Siemens Healthineers France, Saint-Denis, France, CEA/DRF/I2BM/NeuroSpin, Gif-Sur-Yvette, France, Laboratoires des Signaux et Systèmes, Université Paris-Saclay/CentraleSupélec/CNRS, Gif-sur-Yvette, France

Synopsis Synopsis

Recently, the use of TOF with parallel transmission at Ultra High Field demonstrated an improvement in vessel-to-Recently, the use of TOF with parallel transmission at Ultra High Field demonstrated an improvement in vessel-tobackground contrast and spatial resolution. This study further investigates the in-vivo feasibility to correct for blood background contrast and spatial resolution. This study further investigates the in-vivo feasibility to correct for blood flow saturation effects in TOF slabs with a new double-spoke ramp pulse design optimization at 7T while mitigating in-flow saturation effects in TOF slabs with a new double-spoke ramp pulse design optimization at 7T while mitigating inplane TOF heterogeneities. plane TOF heterogeneities.

Purpose Purpose

The use of spoiled gradient-echo TOF at Ultra High Field (UHF) MRI recently demonstrated an improvement in vessel-to-background contrast and spatial resolution . However, radiofrequency (RF) field heterogeneities hinder the full visualization of the intravascular network . As previously reported , the method proposed hereby aims at compensating blood saturation effects by addressing a ramp of variable flip angles (FA) across a TOF slab while improving in-plane FA homogeneity by introducing a new 3D parallel transmission (pTX) pulse design optimization.

Method Method

Slice selection in-plane B1 heterogeneities can be compensated using k "spokes" , especially in the pTX context: traditionally, complex weights of a predesigned RF waveform are optimized for each spoke and each channel by addressing a Magnitude Least Squares (MLS) two-dimensional problem. For TOF slab selection with a ramp of variable flip angles , this first approach is adopted here by predesigning a TONE or VUSE RF waveform. This was obtained by multiplying the frequency response of a TBW=9 sinc by the desired FA ramp, and by taking the inverse Fourier transform of the resulting profile. Then the 2D FA-target consists in a uniform slice in the middle of the slab. In a second approach, RF waveforms are a priori unknown and determined for every channel and spoke by addressing a full MLS three-dimensional problem targeting voxels in the slab with the desired FA profile, and all other voxels in the head with zero. Experiments were performed on a 7T scanner (MAGNETOM, Siemens AG, Healthineers, Erlangen, Germany) with an 8-Tx/Rx Rapid head array (RAPID Biomedical GmbH, Rimpar, Germany). B0 and B1-maps were acquired in a preliminary step to build the full k-space encoding matrix in the Small Tip Angle approximation. In the doublespoke experiments, the first spoke was placed in the center of the k -k plane while the second spoke was located at one inverse RF wavelength away from it (= 8m ) . Both 2D and 3D optimizations were achieved with a variable exchange method initialization and Matlab's (The Mathworks, Natick, MA, USA) active-set algorithm under strict constraints on local and global SAR, average power and peak amplitude. A 4.5-cm isocenter slab-selective TONE pulse was first tested on a doped spherical water phantom with a 20 to 40° FA ramp. The constrained pulse design was carried out for TR=20ms, which led to choose a pulse duration of 3ms to properly achieve the desired flip angle pattern. FA measurements in the slab were performed with an AFI sequence to corroborate the FA pattern observed with Bloch equation simulations. Thus, the flip angle 3D distribution for the standard circularly polarized (CP) mode, static RF shimming (1-spoke) and 2-spokes were compared in terms of in-plane homogeneity and FA-ramp fidelity. An experiment was then conducted on a healthy informed volunteer using a spoiled GRE TOF pTX sequence with the following parameters: TR/TE = 20ms/7.8ms, resolution = 0.5x0.5x0.1mm , slice oversampling = 36.4% and TA=3.80min. The FA ramp was then changed into a non-linear VUSE profile between 9 and 40° to address low flow velocity (5 cm/s). Flow compensation was activated in slice and read directions to prevent blood motion artifacts.

Results and Discussion

Results and Discussion

Based on simulations, the Normalized Root Mean Square Error (NRMSE) with respect to target FA's in the slab was 37.1% for the CP mode, 19.2% for RF shimming, and 9.5% for the 2-spoke excitation (Figure 1). Simulated flip angle maps and AFI measurements were in good agreement. The RF shimming slightly improved the FA homogeneity compared to the CP mode despite the apparition of a hole in the center of the FA map. Nonetheless, this outcome was avoided using a second spoke. The 3D 2-spoke excitation significantly improved the flip angle inplane homogeneity and ramp profile compared to the CP mode and more conventional pulse designs. In vivo results are presented in Figure 2 and Table 1 showing the outperforms of the 3D design to enhance details in the Maximal Intensity Projection (Figure 3).

Conclusion Conclusion

The visualization of the small arteries of the distal territories is significantly better using pTX. In addition, the 3D design distinctly improved the definition of the small vessels located in the posterior cerebral region compared to the traditional 2D design. Thus, this study demonstrates the ability to correct for blood flow saturation effects inside TOF rather large slabs in spite of intrinsic RF heterogeneities, with double-spoke pTX excitation tailored for a ramp profile at 7T.

  Figures Figures

Figure 1

 1 Figure 1: Simulated and Experimental flip angle maps of central axial and coronal slices of a spherical water phantom obtained from 20 to 40°T ONE pulses designed to select a 4.5 cm-central slab.

  Figure 1: Simulated and Experimental flip angle maps of central axial and coronal slices of a spherical water phantom obtained from 20 to 40°T ONE pulses designed to select a 4.5 cm-central slab.

  Figure 1: Simulated and Experimental flip angle maps of central axial and coronal slices of a spherical water phantom obtained from 20 to 40°T ONE pulses designed to select a 4.5 cm-central slab.

Figure 2 :

 2 Figure 2: FA maps of a 4.5-cm slab in three orientations of a human brain for a 9-40° VUSE target profile (from Bloch simulation). On the right, this profile is plotted along the slice direction and across the magnet isocenter. In red: target FA ramp; in blue: result of the Bloch simulations.

Table 1 :

 1 Normalized Root Mean Square Error achieved by the different excitation modes. Notice how the 3D design outperforms the others according to both criteria.

Figure 3 :

 3 Figure3: Axial MIP acquired with a TOF pTX sequence using a VUSE CP mode, 1-spoke, 2D and 3D 2-spoke excitations. Source images were not corrected for reception profiles. Note how much finer the network of blood vessels extends as the pulse design becomes more sophisticated.

Acknowledgements Acknowledgements

The authors wish to thank Chantal Ginisty for her precious help on MIP images post-treatment. We are grateful to Lucie Hertz Pannier, MD, PhD, for her advices and clinical evaluation of the in-vivo angiograms.


Djamel Eddine Khelladi

Reda Bendraou

Marie-Pierre Gervais

SAC-OCL: A Tool for A Semi Automatic Co-evolution of OCL Constraints

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

Introduction

In Model-Driven Engineering, Object-Oriented Models (OOM) play an essential role to capture the dierent aspects of a system [START_REF] Hutchinson | Empirical assessment of mde in industry[END_REF]. This covers the system's architecture, its data structure or its design and GUI classes. A OOM alone is insucient to capture all the relevant aspects and information of a domain specication [START_REF] Mezei | An optimizing ocl compiler for metamodeling and model transformation environments[END_REF]. To overcome this limitation, the Object Constraint Language (OCL) [START_REF] Omg | Object constraints language (ocl)[END_REF] is used to dene constraints on top of OOMs. For instance, the Unied Modeling Language (UML) [START_REF]OMG. Unied modeling language[END_REF] metamodel (an OOM) in version 2.4.1 contains more than 750 OCL constraints expressing well-formedness rules. Whenever an OOM is evolved, its OCL constraints may become invalid and need to be co-evolved accordingly. However, existing tools have so far overlooked two main issues: 1) the existence of multiple and semantically dierent resolutions, and 2) a resolution can be applicable only to a subset of OCL constraints.

1) An impacted OCL constraint by an OOM evolution can be resolved with syntactically and/or semantically dierent resolutions. For instance, the change "multiplicity generalization of a property p from a single value to multiple values" requires the OCL constraints to work on a collection of values, e.g. by introducing an iterator. Alternative resolutions must be considered since multiple iterators with dierent semantics exist, e.g. forAll(), exists() etc.

2) A given resolution strategy is not always applicable for all OCL constraints. Figure 1 illustrates this issue. It depicts an evolution of an OOM where the property score is pushed from the superclass Course to the subclass Project. The Fig. 1: An evolution and co-evolution example. two constraints become invalid because score is no more accessible in Course. The rst constraint that uses the pushed property score through the reference courses, can be co-evolved by introducing an If expression that rst checks whether courses references an instance of the subclass Project so that score is accessible. In contrast, the second OCL constraint whose context (i.e. the element on which an OCL constraint is specied) is dened on the pushed property score, is co-evolved dierently by updating its context. Clearly, a resolution strategy cannot be applied for all impacted OCL constraints by the same change.

Existing tools [3,2,10,9,1] neither consider the two above issues, nor interact with the user.

In [START_REF] Khelladi | Metamodel and constraints co-evolution: A semi automatic maintenance of ocl constraints[END_REF] we addressed these issues by presenting an ecient approach for a semi automatic co-evolution of OCL constraints. We proposed a set of resolutions while considering alternative resolutions per impacted OCL constraint. We identied with a systematic analysis three inuencing factors that we rely on to propose the appropriate resolutions that can be applied to an impacted OCL constraint. To detect the OOM's evolution we use our previous tool [START_REF] Khelladi | Ad-room : a tool for automatic detection of refactorings in object-oriented models[END_REF][START_REF] Khelladi | Detecting complex changes during metamodel evolution[END_REF].

This paper presents SAC-OCL a tool that supports our previous work with a graphical user interface in the form of an Eclipse plugin. It allows to co-evolve OCL constraints that are impacted by the OOM's evolution. To demonstrate the usefulness of SAC-OCL, we validate it on six open-source case studies. The results show that we are able to co-evolve the impacted OCL constraints near to the user intent by reaching an average correct co-evolution rate of 92%.

Tool's Description

The conceptual framework of SAC-OCL has been already published in [START_REF] Khelladi | Metamodel and constraints co-evolution: A semi automatic maintenance of ocl constraints[END_REF]. In this section we present an overview of its main aspects. Figure 2 shows the workow phases of the tool: 1 detecting OOM's evolution, 2 identifying impacted OCL constraints, 3 proposing alternative and the appropriate resolutions for each impacted OCL constraint, and 4 applying automatically the resolutions. The entry point of our tool is the detected OOM's changes during evolution 1 . We start by loading the evolution trace and the specied OCL constraints Fig. 2: Overall approach and the SAC-OCL workow. to be parsed. Phase 2 runs an impact analysis to identify the impacted OCL constraints that need to be co-evolved. After that, the appropriate resolutions are proposed for each impacted constraint 3 . The user conrms the resolution to be applied for each impacted constraint among the proposed alternative ones. Finally, the selected resolutions are automatically performed in phase 4 .

OOM's Evolution

During evolution two types of changes are considered in phase 1 : a) Atomic changes that are additions, removals, and updates of a metamodel element, and b) Complex changes that consist in a sequence of atomic changes combined together [START_REF] Herrmannsdoerfer | An extensive catalog of operators for the coupled evolution of metamodels and models[END_REF]. Our previous tool AD-ROOM [START_REF] Khelladi | Ad-room : a tool for automatic detection of refactorings in object-oriented models[END_REF] considers all atomic changes and seven complex changes: move property, pull property, push property, extract super class, atten hierarchy, extract class, and inline class [START_REF] Herrmannsdoerfer | An extensive catalog of operators for the coupled evolution of metamodels and models[END_REF].

Identication of Impacted OCL Constraints

To identify the impacted OCL constraints we run an impact analysis at the level of the Abstract Syntax Tree (AST) of the OCL constraints (phase 2 ). Before identifying where an AST is impacted, we compute the Table 1 that lists for each metamodel element e, all OCL constraints using e with references to the AST nodes using e. Those references will be further used in the resolution step. Thus, for each change on an OOM element e i , we access the impacted OCL constraints and we access exactly the impacted AST nodes. Note that during the co-evolution, Table 1 is updated accordingly w.r.t. the applied resolutions. For instance, when a rename element e occurs, it is also renamed in the table.

Resolutions and Selection Process of the Appropriate Ones

In [START_REF] Khelladi | Metamodel and constraints co-evolution: A semi automatic maintenance of ocl constraints[END_REF] we rst conducted a systematic analysis that allowed us to identify three inuencing factors that must be considered to propose the appropriate resolu- impacted element is accessed. We then proposed a set of resolutions to co-evolve the impacted OCL constraints (can be found in [START_REF] Khelladi | Metamodel and constraints co-evolution: A semi automatic maintenance of ocl constraints[END_REF]). When dening each resolution we already specify under which inuencing factors each resolution will be proposed. Each resolution is implemented as a transformation function that updates the AST by adding, removing, or updating nodes.

When an OCL constraint is impacted by an OOM change, the process of Figure 3 is used to select a subset of the appropriate resolutions to be proposed to the user (phase 3 ). It starts with all the available resolutions from Table ?? and excludes a subset of resolutions based on the inuencing factors. The rst factor we consider is the metamodel change that excludes resolutions that are not associated to the given change (step 1). After that the two last factors are similarly considered (step 2 and 3) to further reduce the set of appropriate resolutions. This process is followed for each impacted part of an OCL constraint.

Implementation

The tool is implemented as an Eclipse IDE plugin to ease its use by software engineers who are already familiar with development IDEs like Eclipse. It supports the co-evolution of OCL constraints dened in an OCL le on both Ecore [START_REF] Steinberg | EMF: eclipse modeling framework[END_REF] and UML CD [START_REF]OMG. Unied modeling language[END_REF] models. The core functionalities are implemented with Java (4568 LoC) interfacing with our AD-ROOM [START_REF] Khelladi | Ad-room : a tool for automatic detection of refactorings in object-oriented models[END_REF] plugin. Figure 4 part 1 shows the OOM to be evolved. Figure 4 part 2 shows the OCL constraints to be co-evolved. In a rst step, the OOM evolution (atomic and complex changes) are taken as input with the OCL constraints. After performing the impact analysis, the impacted OCL constraints are highlighted to the user Fig. 4: Screenshot of the Eclipse plugin Tool SAC-OCL. as well as the impacting reason (i.e. the OOM change) for a prompt and a better understanding, as shown in Figure 4 part 3. Figure 4 part 4 shows the subset of the proposed resolutions that the user chooses from in a dropdown menu for each impacted OCL constraint. The user's eort is to select the resolutions to be applied automatically afterwards (phase 4 ). See the demonstration video: https://youtu.be/qLn2u0J2Wow. [START_REF] Herrmannsdoerfer | An extensive catalog of operators for the coupled evolution of metamodels and models[END_REF] Evaluation

We evaluated our tool on six open-source case studies that are Ecore metamodels (OOMs) with their associated OCL constraints from the OMG specication, namely: the UML Class Diagram (UML CD), the Structured Metrics metamodel (SMM), the Unied Prole for DoDAF/MoDAF (UPDM), the National Information Exchange Model (NIEM), the EXPRESS Information Modeling Language (EXPRESS), and the Requirements Interchange Format (ReqIF).

The evaluation process consisted in comparing how the OCL constraints were manually co-evolved in practice against how the same OCL constraints are co-evolved with our tool. In the experiment, the authors play the user role. We aimed at co-evolving the OCL constraints as close as possible to the co-evolution in practice, for an objective comparison. We highlight the obtained results. Table 2 presents the results of the measured co-evolution percentage. For four case studies, we reached 100% co-evolution percentage, whereas in UML CD and SMM, we had respectively 72%, 80% and 83% of co-evolution percentage. An average of 92% (syntactically) and 93% (semantically) correct co-evolution is reached in our evaluation. These results show that our approach can eciently support the user with a co-evolution near to her intent and needs.

However, some constraints where co-evolved dierently in our approach than in practice. We further investigated these cases in particular for UML CD and SMM case studies. We noticed that those cases were due to a refactoring that changed their semantic either by removing/adding a part in the constraint. Or by replacing some elements in the original constraint with other elements that are dierently typed. For example, constraint 1 is impacted by the renaming of GeneralizableElement to PackageableElement. It is co-evolved by our approach as follows from (1) to (2) by propagating the rename. However, in practice the context of constraint (1) was changed to the subclass Classifier instead of applying a rename. Therefore, the semantic is slightly dierent since the applicability scope of the new constraint is reduced to elements of type Classifier. context GeneralizableElement inv: not self.allParents()-> includes(self) -( 1) context PackageableElement inv: not self.allParents()-> includes(self) (2)

Related Work

Here we give a succinct related work to OCL co-evolution. Demuth et al. [START_REF] Demuth | Supporting the co-evolution of metamodels and constraints through incremental constraint management[END_REF] proposed an approach for OCL co-evolution based on templates. They provided 11 templates that dene a xed structure for OCL constraints. Hassam et al. [START_REF] Hassam | Assistance system for ocl constraints adaptation during metamodel evolution[END_REF] proposed to co-evolve OCL constraints using QVT [START_REF] Omg | Query/views/transformations (qvt)[END_REF] a transformation language. Similarly, Markovic et al. [START_REF] Markovic | Refactoring OCL annotated UML class diagrams[END_REF] proposed to refactor, based on QVT, OCL constraints annotated on UML class diagrams when these last evolve. Kusel et al. [START_REF] Kusel | Systematic co-evolution of ocl expressions[END_REF] discussed the impact of metamodel evolution on OCL expressions and proposed to resolve impacted expressions. Cabot et al. [START_REF] Cabot | Automatic integrity constraint evolution due to model subtract operations[END_REF] focused on the metamodel change delete element. In particular, they aimed at removing only a sub part of the OCL constraint that is using the deleted element. All existing approaches [START_REF] Demuth | Supporting the co-evolution of metamodels and constraints through incremental constraint management[END_REF][START_REF] Hassam | Assistance system for ocl constraints adaptation during metamodel evolution[END_REF][START_REF] Markovic | Refactoring OCL annotated UML class diagrams[END_REF][START_REF] Cabot | Automatic integrity constraint evolution due to model subtract operations[END_REF][START_REF] Kusel | Systematic co-evolution of ocl expressions[END_REF] consider only the metamodel change as a factor to propose a resolution. Thus, they dene for each metamodel change only a unique resolution. In contrast, we propose alternative resolutions while considering three inuencing factors instead of one, i.e. the OOM change.

Conclusion

We presented SAC-OCL a tool for a semi automatic co-evolution of OCL constraints dened on OOMs. SAC-OCL is designed to consider alternative res-olutions and to propose the appropriate resolutions for each impacted OCL constraint. It is implemented as a plugin for the Eclipse IDE a wide-spread development environment for software developers. The evaluation illustrates our tool's ability to co-evolve OCL constraints near to the user intent while releasing the burden of manual co-evolution from the user.

Fig. 3 :

 3 Fig.3: Process of selecting the appropriate resolution strategies per impacted part of a constraint and per metamodel change. tions for an impacted OCL constraints. The three factors are highlighted in the framebox here under. 1. The OOM change of an element e. 2. Location of the impacted element e in an OCL constraint: (a) e is used in the context of an OCL constraint (b) e is used in the OCL expression through a navigation path. 3. The context of the impacted constraint, to know from which class theimpacted element is accessed. We then proposed a set of resolutions to co-evolve the impacted OCL constraints (can be found in[START_REF] Khelladi | Metamodel and constraints co-evolution: A semi automatic maintenance of ocl constraints[END_REF]). When dening each resolution we already specify under which inuencing factors each resolution will be proposed. Each resolution is implemented as a transformation function that updates the AST by adding, removing, or updating nodes.When an OCL constraint is impacted by an OOM change, the process of Figure3is used to select a subset of the appropriate resolutions to be proposed to the user (phase 3 ). It starts with all the available resolutions from Table?? and excludes a subset of resolutions based on the inuencing factors. The rst factor we consider is the metamodel change that excludes resolutions that are not associated to the given change (step 1). After that the two last factors are similarly considered (step 2 and 3) to further reduce the set of appropriate resolutions. This process is followed for each impacted part of an OCL constraint.

Table 1 :

 1 Impact Identication on OCL constraints.

OOM Elements OCL Constraints References To AST Nodes e1 OCL1, ... ref1, ref2, ...

Table 2 :

 2 Correct Co-evolution Percentage (%).

	UML CD SMM UPDM NIEM EXPRESS ReqIF
	Syntactically correct co-evolution % 72%	83% 100% 100% 100%	100%
	Semantically correct co-evolution % 80%	83% 100% 100% 100%	100%

Acknowledgment. The research leading to these results has received funding from the industrial innovation Project MoNoGe under grant FUI -AAP no. 15.