Remi Brouet

Alla Sheffer

Laurence Boissieux

Marie-Paule Cani

Design Preserving Garment Transfer

Keywords: CR Categories: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-; Garment modeling, geometry processing, transfer methods, resizing

Figure 1: Design preserving garment transfer: (left) transfer of a multi-layer outfit from a woman to a young girl; automatically graded patterns (bottom) shown to scale. The zoomed-in source and target patterns for the back panel highlight the subtle changes in shape. (right) Dancer outfit transferred from the female in the center to a variety of other characters. c Laurence Boissieux 2012

Introduction

Modeling of complex real or virtual garments is a highly time consuming and knowledge intensive task. For instance, it took an experienced computer artist three hours to generate the woman's outfit in Figure 1 (left), a process that included creating 2D patterns, placing them on the mannequin, running cloth simulation and then iteratively adjusting patterns and parameters, repeating the process until the desired effect was achieved. If we wished to design a similar looking outfit for a young girl who has very different proportions, see Figure 1 (left), this tedious process would need to be repeated practically from scratch. Consequently, dressing a large number of virtual characters in similarly designed outfits, Figure 1 (right), is currently prohibitively time consuming, even if state-of-the-art garment modeling interfaces such as [START_REF] Umetani | Sensitive couture for interactive garment editing and modeling[END_REF]] are used.

In real-life, professional pattern makers adapt garments to people with different proportions and body-types through a complex process known as grading or pattern grading. Manual grading aims to preserve the design or look of the garment while adjusting it to fit the proportions of the new wearer [START_REF] Moore | Concepts of Pattern Grading: Techniques for Manual and Computer Grading[END_REF]]. This process requires significant specialized expertise and relies on a set of precomputed rule tables for standard body sizes. Applying a similar process to virtual garments can be especially challenging since the characters to be dressed often have non-standard body proportions for which no rule-tables exist. While skinning-type garment transfer techniques [START_REF] Cordier | Made-to-measure technologies for an online clothing store[END_REF][START_REF] Wang | Design automation for customized apparel products[END_REF] adjust the garment to fit the target character's proportions reasonably well, they often fail to preserve the original design, requiring manual editing to recover it [START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF].

Instead, we focus on automatic design preserving garment grading or transfer, introducing a method that produces garments that fit the proportions of the new wearer while retaining the original design as much as possible. As emphasized in the literature, garment transfer is an ill-posed problem. Formalizing what makes a garment look the same on characters of different body shapes, although the input and output garment surfaces obviously differ, is in itself a challenge. Therefore, our first contribution, presented in Section 3, is to analyze professional pattern-grading criteria and reexpress them in terms of geometric requirements for garment-mesh transfer. We then introduce a garment transfer algorithm that satisfies these requirements, as our main contribution. We formulate garment transfer as a constrained optimization problem which optimizes design preservation subject to a number of geometric constraints arising from proportionality, plausibility and other considerations elaborated upon in Section 3. To efficiently generate the graded garments we solve this problem using an iterative process, where each iteration consists of solving a quadratic minimization problem.

As demonstrated by the results, our method enables fully automatic, realistic, design preserving transfer of garments between characters with vastly different body shapes and proportions. Consequently, it significantly simplifies the modeling of new dressed characterspre-existing wardrobes can be instantly transferred from one character to another without the need for any specific user skill. Our method also allows efficient generation of large groups of similarlydressed characters for the film industry -e.g. warriors, workers, dancers, etc, without the usual restriction to clone-like models.

Plausible virtual garments have a low distortion mapping to a set of 2D patterns, enabling texture mapping and actual manufacturing. Our design preservation criteria, as discussed in Section 3 explicitly aim to preserve plausibility. Thus given the 2D patterns for the source garments, our method directly generates the 2D patterns for the transferred one (Figure 1, middle).

Related work

Previous research relevant to our work can be roughly split into three areas: general garment modeling approaches, grading and transfer methods for garments, as well as resizing and transfer methods for other domains.

Garment modeling

The traditional process for virtual garment modeling [START_REF] Protopsaltou | A body and garment creation method for an internet-based virtual fitting room. Advances in Modeling[END_REF] begins with the design of 2D patterns. These patterns are then stitched together and lifted to 3D, where a physics-based simulation is used to generate the final 3D shape. The process is hard to control, and needs to be iterated until the designer is satisfied with the results. Using this approach requires tailoring skills, a significant time investment, and experience with physical simulation tuning. Sketch-based garment modelers [START_REF] Decaudin | Virtual garments: A fully geometric approach for clothing design[END_REF][START_REF] Turquin | A sketch-based interface for clothing virtual characters[END_REF][START_REF] Robson | Context-aware garment modeling from sketches[END_REF] generate a 3D garment model from user-sketched 2D silhouettes of the garment. This significantly speeds up and simplifies the design process. However, these methods do not achieve the same garment complexity and realism as the traditional work-flow, and still require a significant amount of user input per outfit. Thus they do not replace an automatic transfer method.

Interactive garment modeling systems [START_REF] Volino | From early virtual garment simulation to interactive fashion design[END_REF][START_REF] Umetani | Sensitive couture for interactive garment editing and modeling[END_REF]] allow for instant 3D feedback in response to changes in garment patterns by using a real-time physics-based simulation. Umentani et al. [2011] use such an interactive setup to quickly adapt patterns to a new character. However this process still relies on the user's ability to make the right design choices in order to achieve the desired look for the transferred garment. Similarly, the modeling framework of [START_REF] Harmon | Interference aware geometric modeling[END_REF] helps resolve contacts and intersections in an interactive modeling environment but leaves the design choices up to the user.

Garment Transfer or Grading:

The easiest way to transfer a garment from one character to another is to apply a physical simulation to place the garment on the new character. This solution is clearly inadequate, and produces a result that looks like a person wearing someone else's wrong size garment. In real-life, garment grading is applied to the 2D sewing patterns and follows a complex set of high-level rules that vary significantly for different garment styles [START_REF] Moore | Concepts of Pattern Grading: Techniques for Manual and Computer Grading[END_REF]. In this process tailors first aim to scale the patterns to reflect changes in a number of key distances between the source and target wearers: hip or waist circumference, arm length, neck to waist length, etc. The challenge in this step is that distances along parallel curves can scale nonuniformly, requiring subtle, uneven, changes in pattern shape (see the skirt patterns in Figure 2). Consequently, this process remains manual and knowledge-intensive, as the designers need to decide how to preserve the original design while adjusting these distances. Computer-aided grading software, e.g. [eTelestia ; Optitex ; Fash-ionCAD ], attempts to simplify this step by providing users with easy access to key-distance based sizing tables and automated grading rules. These systems are largely limited to a pre-defined set of grading rules and rely on user expertise to select the appropriate rules for each garment. Since a small set of distances cannot not fully describe the difference in proportions and body shape between people, a further refinement step is often necessary to obtain the desired look. This step involves a physical fitting process followed by additional alterations. For virtual characters who typically do not conform to standard body size tables, this process is particularly challenging as even the distance based scaling must typically be done completely manually.

As grading is a highly useful tool in generating both real and virtual garments, attempts have been made to automate it by operating directly in 3D. Several methods, e.g. [START_REF] Wang | Design automation for customized apparel products[END_REF][START_REF] Wang | Volume parameterization for design automation of customized free-form products[END_REF], use variations of skinning techniques to do so. However, as pointed out by [START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] and illustrated later on in Figure 13 skinning significantly changes the shape of loose garments, violating both the original design intent and plausibility. Consequently, [START_REF] Cordier | Made-to-measure technologies for an online clothing store[END_REF] apply skinning only to tight areas of the garment. They then globally scale the garment patterns for the loose parts along two major axes based on changes in wearer's height and hip circumference. Such axial scaling often results in poorly shaped garments (Figure 3, bottom) and is inconsistent with the much more complex process used by professional graders (Figure 2). By smoothly modifying the entire garment surface our method is able to preserve the source design (Figure 3, top). To preserve the design [START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] introduce an interactive transfer system where users correct a skinning generated garment by manually tracing the desired garment outlines in a number of views. Instead, we aim for a fully automatic design-preserving solution.

Resizing and Transfer (non garment):

As part of the effort to simplify the creation of virtual 3D content, researchers have developed a variety of transfer and resizing techniques for different types of data. Properties to be transferred between different shapes range from textures and geometric details [START_REF] Kraevoy | Cross-parameterization and compatible remeshing of 3d models[END_REF][START_REF] Takayama | Geobrush: Interactive mesh geometry cloning[END_REF] to deformation or animation [START_REF] Sumner | Deformation transfer for triangle mesh[END_REF][START_REF] Kircher | Editing arbitrarily deforming surface animations[END_REF][START_REF] Ben-Chen | Spatial deformation transfer[END_REF]. Our work follows this trend, extending the range of transferable content.

Deformation and geometry transfer methods, e.g. [START_REF] Kircher | Editing arbitrarily deforming surface animations[END_REF][START_REF] Ben-Chen | Spatial deformation transfer[END_REF][START_REF] Sumner | Deformation transfer for triangle mesh[END_REF][START_REF] Bokeloh | Pattern-aware deformation using sliding dockers[END_REF] often use a notion of shape preservation. However, the formulations they typically use penalize shear. These formulations cannot be used in a garment transfer setup where, as discussed in Section 3, proportional shearing based on changes in body proportions is not only unavoidable, but in fact often desirable. To realistically resize man-made objects, [START_REF] Kraevoy | Non-homogeneous resizing of complex models[END_REF] minimize changes in surface normal. Their observation about normals reflecting the global shape directly applies to our setup (Section 3). However, our challenge is quite different due to the other considerations that garment transfer must satisfy. Specifically their volumetric solution approach cannot support the constraints arising from proportionality and plausibility which need to be balanced against shape preservation.

The Geometry of Garment Grading

Before developing a garment transfer method we must ask what a user's expectations from a transferred garment are [START_REF] Moore | Concepts of Pattern Grading: Techniques for Manual and Computer Grading[END_REF]. A common statement of these transfer, or grading, requirements is that "the purpose of grading is to proportionally increase or decrease the size of a pattern, while maintaining shape, fit, balance, and scale of style details." [Threads ]. The following sections discuss the geometric formulation of these criteria, and then give an overview of our method.

Grading criteria

Proportion and Scale: The proportionality, or proportional increase/decrease of size, requires the resized garment to preserve the relative location of garment features with respect to the character's limbs and body. For instance: a knee-length skirt needs to remain knee-length independent of a change in a character's height, a dress waistline needs to remain on the waist, and a side zipper need to stay on the side. The proportional scaling of details reinforces proportionality, requiring not only to preserve feature location but to scale those appropriately. From a geometry processing viewpoint, proportionality and scale combined can be paraphrased as a single relative location requirement, where we associate a reference location on the body with each point on the garment and preserve the direction from one to the other during transfer, preventing the garment from sliding along or twisting around the body.

Shape:

The shape preservation criterion requires grading to preserve the overall look or design of the input garment. E.g. a straight skirt should remain straight, boot-cut jeans should retain the bootcut, and so on. The mother-daughter dresses in Figure 4 (right) provide an illustration of shape preserving manual grading which successfully handles large differences in proportions. From our observations of professionally graded garments, confirmed in a discussion with a fashion designer, expert graders allow for significant changes in the geometry of the garments to accommodate changes in proportions but aim to preserve the slope or tangent plane orientations across the garment surface whenever possible. Thus for instance the hem width of bell-bottom jeans designed for a taller person is increased proportionally to height to maintain the bell slope. Consequently, we restate shape preservation in geometric terms as preservation of garment surface normals.

Fit:

The fit criterion reflects preservation of local distance between the garment and the wearer. As discussed above, the distance to the body in loose areas is often expected to change significantly to preserve shape; hence, this criterion is largely enforced in tight regions. Even for these regions fit preservation is often a design choice, a designer may selectively relax fit in some locations to more closely adhere to the source garment shape. A typical example is transfer of a skirt or pants to a fuller person, where designers typically loosen the garment on the lower half of the belly to achieve a visually skinnier look [START_REF] Freeth | Maintaining design aesthetics : case studies investigating grading for body shape variation : the translation of garment designs to fit fuller figured women[END_REF]]. Geometrically, fit preservation can be expressed as forcing the garment points that are very close to the source character's body to remain close to the target character after the transfer.

Balance: Lastly, the term balance refers to the hang of the garment around the body which is largely controlled by the orientation of the patterns with respect to the weave directions of the selected fabric. As such, it is orthogonal to the geometric considerations involved in transferring a 3D virtual garment, where one can always assume that the patterns remain correctly oriented.

In addition to the criteria above, we must consider two extra plausibility criteria that are implicit in real garment grading.

Manufacturability:

Real garments need to be manufactured from planar fabric panels. As real-world fabric has a limited stretchability, the Gaussian curvature of the transferred 3D garment has to be bounded in the interior of each panel. The shape preservation metric previously discussed implicitly keeps the curvature low, since for a surface with a priori low Gaussian curvature, preserving normals implicitly preserves curvature. However, manufacturability needs to be explicitly considered when processing regions where fit is enforced. In these areas the garment follows the shape of the body and therefore can be affected by increase in body surface curvature, see Figure 8 (a,b). To preserve manufacturability professional graders either selectively relax the fit thus reducing curvature, or introduce complex changes to patterns, such as multiple darts and gussets, to maintain the fit. In this paper we opt for the former option, selectively relaxing fit to minimize curvature increase.

Collision Avoidance: Real garments clearly cannot intersect the wearer's body or underlying clothing layers. Thus when transferring a garment to a larger person, designers increase pattern size to preserve shape and avoid fabric stretching or worse tear.

Method Overview

Our garment transfer method operates directly on 3D garments and finds a satisfactory balance between the criteria listed above: shape, relative location, fit, manufacturability, and collision avoidance.

The input to our method is a dressed source character model, possibly with the associated 2D clothing patterns, and a target character, all represented by manifold triangular meshes. We assume that the characters are posed in a similar pose, and that a dense correspondence or cross-parameterization is predefined between them. We also assume that both characters are rigged, i.e. have an animation skeleton. There are a large number of cross-parameterization methods, especially when it comes to rigged models, which can be easily used to satisfy these requirements [START_REF] Sheffer | Mesh parameterization methods and their applications[END_REF][START_REF] Chang | Skeleton-driven animation transfer based on consistent volume parameterization[END_REF]].

We break the transfer process into two steps (Figure 5): a skinninglike initialization that generates a proportionally scaled reference garment (Section 4) and a global design preserving optimization (Section 5). To efficiently preserve the shape of the source garment, we restate normal preservation in terms of per-triangle transformation gradient. We introduce a transformation gradient based formulation which balances normal, relative location, and fit preservation and can be solved using an efficient iterative solver (Sections 5.1 and 5.2). In Sections 5.3 and 5.4, we show how to combine this minimization with collision avoidance and multi-layer garment processing, leading to the final iterative algorithm that generates the desired transferred garment.

Proportional Scaling

The first step of our method generates a proportionally scaled version of the input garment which satisfies the relative location and fit criteria (Figure 5,b). This scaled version is then used as a starting point for the normal preserving optimization which generates the target transferred garment. Our proportional scaling method can be seen as an extension of smooth skinning, where the combination of constant positions in several skeleton frames is replaced by a combination of constant offset vectors from a set of adequately chosen reference points on the character model. Using skin-based offsets allows our method to cope with changes in body shape, such as arm thickness, in addition to handling changes in skeletal proportions.

Selecting reference points

To perform the proportional scaling we first associate each garment vertex pg with pairs (p b , pm) of relevant bone and character skin points. We call these pairs reference points. Note that using the closest skin point as a reference [START_REF] Cordier | Made-to-measure technologies for an online clothing store[END_REF][START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] is not necessarily the best choice (see Figure 6, left), as it can cause points to slide along the body on the target character. As-signing references orthogonally to the local bone directions reduces such sliding, resulting in better relative location preservation, most notable along garment boundaries. Therefore, the reference point pairs we select correspond to local minima of a function expressing distance to the character model in a direction orthogonal to the local bone (see Figure 6), computed as follows. , where we set σ = 0.1. In most cases this function has a clear single minimum (Figure 6, right), which we select as the reference. When two identical or very close minima exist, we assign both as references. This is typically the case in areas in-between the legs of the character or under the arms (see Figure 6, center). Finally, each point pg is associated with an offset o = pg -pm for each reference pair (p b , pm).

Proportional scaling using offset vectors

We use the computed reference points and offsets to obtain the proportionally scaled locations pg for each garment point with respect to the target character. First, for each reference pair (p b , pm) on the source character, we use the cross-parameterization to obtain the corresponding pair of points (p b , pm) on the target. Each point pg has one, or more, reference pairs. If it has a single reference pair (p b , pm), we set pg = pm + o * v bm , where v bm is a unit vector in the direction of (p b , pm). If there are several reference pairs for the garment vertex pg, we use a weighted sum of the positions dictated by each reference, using non-linear weights to get a sharp transition, w1 = arctan (5 * (t-0.5)+ π

2 ) π and w2 = 1 -w1, where t is the coordinate of the projection of the garment vertex pg on the segment between the two relevant bone reference points.

Figure 5, (b) shows the output of the proportional scaling step. Note that garment borders and other features keep their relative location with respect to the character's body and limbs, while the use of skin based offset accounts for changes in body shape between the input and output character, preserving fit. At the same time, the results clearly do not account for shape preservation, necessitating the main step of the algorithm described next.

Shape Preserving Garment Transfer

As-2D-as-possible Deformation

Preservation of garment shape requires the normals of the garment mesh triangles to remain constant or near-constant during transfer.

In general, expressing normal preservation as a function of vertex positions leads to a non-linear, hard to control optimization. Hence, existing deformation and resizing methods, e.g. [START_REF] Bokeloh | Pattern-aware deformation using sliding dockers[END_REF] tend to penalize both out-of-plane rotations and 2D deformations. To penalize all rotations, [START_REF] Kraevoy | Non-homogeneous resizing of complex models[END_REF]] use a volumetric formulation with global scaling constraints. Their approach can not be extended to our setup as we require a much finer level of control. To efficiently penalize rotations, while allowing for 2D deformations we express normal preservation via transformation gradients. This formulation allows for a solution mechanism based on iterative linear minimization of a quadratic functional. Contrary to previous gradient based methods, which aim to either preserve known transformation gradients [START_REF] Sumner | Deformation transfer for triangle mesh[END_REF] or to search for as-rigid-as-possible ones [START_REF] Igarashi | Asrigid-as-possible shape manipulation[END_REF]; Sorkine and Alexa 2007], we search for as-2D-as-possible transformation gradients.

Following [START_REF] Sumner | Deformation transfer for triangle mesh[END_REF] we label the vertices of each source garment triangle t as p1, p2 and p3 and add a virtual vertex p4 computed by offsetting p1 by the triangle normal. We then define the 3x3 matrix representing the local triangle frame as P t = (p4 -p1, p4 -p2, p4 -p3). The gradient of the triangle transformation from the source to the target garment can then be written as P t (P t ) -1 where P t i is the local frame after the deformation. Normal preservation for all the mesh triangles is thus expressed as the minimization of:

E shape = t || P t (P t ) -1 -T t || 2 F (1)
where ||.||F is the Frobenius norm for matrices, and the unknown target triangle gradients T t are constrained to be 2D-only transformations defined in the plane of the source triangle, i.e. applying T t to t preserves the triangle's normal.

Solver:

The numerical challenge we face is to enforce the 2Donly constraints on T t while solving for both p, the target vertex positions, and T t , the target gradients, subject to the additional constraints listed in Section 5.2. To compute a solution we use an iterated least-squares process which alternates between updating T t while keeping p fixed, and vice versa. We start by setting p to the positions p of the vertices after the proportional scaling based initialization (Section 4). We then iterate the two subsequent steps.

Updating T t : To update T t given the current value of p, one option is to perform QR decomposition of the gradient P t (P t ) -1 and use the nonrotational component as the new 2Donly transformation gradients. However such decomposition discards the in-plane rotations, which in our case we want to allow. Instead we compute T t as follows (see inset figure): we project each triangle to the corresponding plane using the reference normal n t on the source garment:

p t i = pt i -< pt i , n t > n t
obtaining a local frame P t = (p 4 -p 1 , p 4 -p 2 , p 4 -p 3 ). Typically, || P t (P t ) -1 -P t (P t ) -1 || < || P t (P t ) -1 -T t ||. If this is the case we set T t = P t (P t ) -1 , otherwise T t is unchanged. Consequently the update step is guaranteed to never increase the value of the optimized functional. Since the same is true for the vertex solve, the optimization is guaranteed to converge.

Vertex solve: With T t fixed, the solution for p minimizing the quadratic equation ( 1) reduces to a simple linear system, which we solve in combination with the constraints detailed below. Since the positions do not change significantly between iterations, we use an iterative CG solver with the previous positions as an initial guess.

Accounting for relative location and fit constraints

To generate a properly transferred garment the shape preservation term described by Equation 1 needs to be combined with terms enforcing preservation of relative locations and fit. Both of these are by construction satisfied by the vertex positions p of the proportionally scaled garment computed by the initialization step (Section 4).

To introduce these considerations into the shape-preserving formulation we consider the local frame(s) defined by the relationship between each vertex p on the proportionally scaled garment and its associated reference skeleton point(s) p b . Each frame is formed by the directions d b of the corresponding skeleton bone, the unit vector dq collinear to (p b , p), and their cross product dt (by construction dq is typically orthogonal to d b ).

To enforce relative location preservation we use the following term

E rl = p αp(< p -p, d b > 2 + < p -p, dt > 2 ).
(2)

The two components of the sum aim at preventing the garment from sliding along or twisting around the skeleton respectively. For interior vertices in loose regions we use a low αp = 0.5 prioritizing shape preservation at the expense of minor inaccuracy in relative locations. Along garment boundaries and seams where any twisting or displacement would be very noticeable, as well as in the tight regions, we set αp = 1000. As relative location does not dictate any constraints on the distance between the character's body and the garment, the component of p -p aligned with dq is unconstrained.

To enforce fit in tight regions, specified as described below, the relative location term is augmented with a fitting term, explicitly constraining this distance,

E fit = β t∈F p∈t < (p -p, dq > 2 (3)
where the set F contains the triangles in the regions deemed tight, and β = 1000. The triangles in F are also removed from the shape energy term E shape as in this case there is no reason to preserve their normals. Using the two terms above, the energy functional to be minimized in the iterative process described in Section 5.1 is set to:

E = E shape + E rl + E fit (4)
Given the degree of freedom provided by varying the distance to the character's body, we typically can simultaneously preserve both relative location and shape in the loose regions pretty well.

Selecting the Tight Regions: As stressed in Section 3, in reallife grading the selection of the region where fit should be preserved is a design choice [START_REF] Freeth | Maintaining design aesthetics : case studies investigating grading for body shape variation : the translation of garment designs to fit fuller figured women[END_REF]]. The simplest selection would be based on a distance threshold. However this choice is problematic when the body curvature grows significantly between the source and target characters -e.g. from a regular female to a pregnant one (Figure 8,b). In this case, preserving tightness can increase the garment's Gaussian curvature making manufacturing a challenge and creating an unappealing look. Instead, we opt for the selective relaxation technique described in Section 3, relaxing fit in areas where the normal to the source garment points downward or sideways. We thus assign to F triangles with all vertices located closer than a distance threshold from the model, and whose normals n t on the source garment are pointing upward. This strategy leads to consistently believable transferred garments, such as the overalls in Figure 8 (d). Note, that completely relaxing the fit across the model can lead to implausible results (Figure 8,c), with the male character looking like he wears a bra. The reason is that lacking physical context the method cannot distinguish between upward pointing garment areas which are a product of garment-body interaction, as is the case for the overall, and those formed by design (e.g. through bra type seaming). Our tightness setup assumes the former scenario, as it is a more likely one.

Handling collisions

The transfer process as described so far does not explicitly prevent garment interpenetrations with the target character or selfintersections. Self-intersections are very rare and and can be easily resolved by any standard post process that moves vertices apart without any changes to the overall garment design. In contrast, body-collisions typically occur when transferring a garment to targets with more protruding parts than the source (Figure 9, a) and indicate a need to add more fabric to accommodate the change in body shape. Note that collisions can only occur in the loose regions of the garment, as the fit constraint prevents interpenetrations in tight regions. To add more fabric and prevent collisions during transfer we take advantage of the local frames (d b , dq, dt) associated with each vertex (Section 5.2). Using these frames collision avoidance can be paraphrased as

< p -pm, dq >≥ (5)
In other words, the garment has to be farther away from the bone than the skin of the model. Combining this constraint with strong preservation of relative location, one can theoretically avoid all in- tersections with the body. The practical challenge is in enforcing such inequalities efficiently.

Solution Mechanism:

To implement efficient collision avoidance we opt for an active set approach especially tailored for our needs. Standard active set methods [START_REF] Nocedal | Numerical optimization[END_REF] replace inequalities by strategically selected equality constraints, using an iterative addition and removal process. In our case,we leverage knowledge about the problem setup at hand, to develop an efficient solution method where only strictly necessary equalities are added and consequently never removed. This modification makes the solution both faster and robust.

We first optimize the energy functional in Equation 4with no collision constraints, and then iteratively introduce collision-resolving equality constraints and repeat the optimization as long as collisions persist. Specifically, we observe that in our setup resolving collisions higher-up along the body often resolve those below, while the opposite practically never happens. In general, once we move vertices away from the body, shape preservation pulls those below away as well, while vertices higher up are held in place due to fit constraints typically enforced in the tight regions on the shoulders. This is likely due to garment interaction under gravity. Knowing this, we use a top to bottom equality enforcement strategy. We obtain best results by adding constraints very gradually, two by two (to account for symmetries often present in garment models). After each collision processing step, we repeat the optimization (Equation 4). This iterative process leads to better results than introducing the constraints all at once, see Even with the very gradual introduction of equalities, the collisions are typically resolved in just a few iterations; see Table 1 for permodel counts.

Extension to layers of garments

Real-life outfits often consist of multiple layers either fully separate, such as a dress with an under-skirt (Figure 1), or stitched together, such as a dress with multiple ruffle layers (Figure 10), or a jacket with outside pockets . Our transfer method easily extends to this case. We incrementally process each fabric layer, starting with the layer closest to the body and proceeding to the outer one.

At each stage, we treat the already processes layers as part of the current character model. The outermost surface of this model is then used to compute the proportionally scaled version of the next source layer, used to initialize the subsequent optimization process.

Pattern Extraction

To obtain patterns for the transferred garment, we cut it along the seams indicated on the source and use the ABF++ parameterization method [START_REF] Sheffer | Abf++: fast and robust angle based flattening[END_REF] to parameterize the resulting charts. We found that this approach provides an optimal time-quality tradeof. It performs equally well to more time consuming stretch minimization techniques. At the same time it creates better, more sym- metric, patterns than faster, linear methods [START_REF] Sheffer | Mesh parameterization methods and their applications[END_REF]] in cases where the source and consequently target garments are not perfectly developable. We automatically discard darts that are no longer necessary, i.e. ones effectively closed by the parameterization. The L 2 -stretch [START_REF] Sheffer | Mesh parameterization methods and their applications[END_REF]] between the garments and the patterns we computed was in the range of 1.0002 to 1.003 (ideal value is 1), indicating negligible distortion. Figures 1 and11 show patterns created using our approach. Patterns created this way are well suited for texturing or physical simulation. However they tend to have somewhat wavy outlines, sub-optimal for actual manufacturing. To regularize those, one can apply standard methods which approximate nearly straight outline segments by straight lines, and nearly circular ones by perfect arcs [START_REF] Mehra | Abstraction of man-made shapes[END_REF]].

Results and discussion

Throughout the paper we demonstrate the results of our method on a variety of models. We show results both in the canonical pose in which the transfer was processed (e.g. Figures 5,12) and after simulation in alternative poses (e.g. Figure 1 and associated video).

The latter demonstrate that, consistent with user expectations, the transfer process preserves design similarity between the source and target garments in general and not just in a particular pose. Figures 1 (left) and 10 show believable transfer of complex layered outfits between models with significant differences in proportions and body shape. Figure 1 (right) further reinforces the method's robustness to large changes in proportions and shape and highlights the suitability of our method for transferring garments to large crowds of highly diverse, often unrealistic, virtual characters. Figure 12 shows transfer of typical real-life garments to increasingly differ- Validation: In addition to visual inspection by non-experts and amateur tailors, we had the results evaluated by a fashion designer, Nurit Perla (www.talia-designer-clothes.com), who concluded that our outputs satisfy all the criteria used in traditional grading. We further validated the approach by making a dress for an actual doll (Figure 11). We transferred the source dress to a 3D model of the doll, which has very different proportions from the source character, and then used the resulting patterns to make the actual dress.

The resulting dress maintains the design and style of the source while nicely fitting the doll's dimensions, showcasing our method's applicability for transferring real-life garments.

Comparison: Existing garment transfer methods can be split into three groups: skinning based [START_REF] Wang | Design automation for customized apparel products[END_REF][START_REF] Wang | Volume parameterization for design automation of customized free-form products[END_REF]], axis-aligned scaling [START_REF] Cordier | Made-to-measure technologies for an online clothing store[END_REF]], and user-assisted [START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF]. Figure 3 provides a comparison between axis-aligned scaling combined with physical simulation and our result. While the scaled skirt is baggy and has an uneven hem length, ours faithfully reflects the source design. Figure 13 provides a comparison of our result to those of [START_REF] Wang | Design automation for customized apparel products[END_REF]] and [START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] Statistics: Table 1 summarizes the statistics for our models. For typical virtual garments with five to twelve thousand triangles, our transfer process takes one to two minutes to generate the target outfit on a standard desktop PC (Intel Core 2 Duo T6400 2GHz). The runtime largely depends on the number of collisions that need resolution.

Limitations:

The main limitation of our method is its sensitivity to the setting of the tight region tolerance, as unfortunately different input virtual models have different minimal offsets between the garment and the character, depending on the original modeling setup. Accordingly, the tightness tolerance needs to be adjusted depending on the model source. The output quality is also dependent on the quality of the cross-parameterization between the source and target characters. Lastly, our method is limited to manifold meshes; we did not find this to be a restriction, as most virtual garments are represented as such.

Conclusion

By automating garment transfer, our work greatly simplifies the generation of dressed characters, currently one of the more tedious and difficult task for computer artists. It enables transfer of both virtual and real-life garments between characters with very different body shape and proportions automatically adapting source patterns to fit the transferred garment. Our technique lets non-expert users to adapt pre-existing wardrobes to their characters of choice, removing the tailoring knowledge barrier. It is directly applicable to clothing crowds of arbitrary characters, as it requires no per-output tweaks. The two key components of our approach are a geometric formulation, and subsequent efficient optimization, of the set of criteria used in manual pattern-grading.

Our method has three main limitations. We rely on purely geometric considerations in the setting of the tight regions. Reverse engineering designer intent can be an interesting topic for future research. Similarly we ignore the impact of fine cloth mechanics on the shape of real-life or simulated output garments. However as demonstrated by the figures and the accompanying video our outputs retain the source design following simulation. Lastly, the method is sensitive to the quality of the cross-parameterization between the source and target models.

Possible improvements of the method include further speedup through the use of tailored solvers, such as [START_REF] Ascher | On the modified conjugate gradient method in cloth simulation[END_REF]] and pattern regularization consistent with tailoring approaches. It would be very interesting to apply our method to resizing of other 3D shapes, comparing the results with state of the art [START_REF] Kraevoy | Non-homogeneous resizing of complex models[END_REF][START_REF] Bokeloh | Pattern-aware deformation using sliding dockers[END_REF].

Figure 12: Transfer of garments to progressively more different models (front and side views): a stockier shorter female, a pregnant female, and an exaggerated male character. The texture on the transferred dresses was generated using the automatically computed patterns.

Discontinuities (e.g. the line under the chest) reflect seam locations.

Figure 2 :

 2 Figure 2: Traditional patterns for a skirt for small and large sizes ( c LaurenceBoissieux2012).

Figure 3 :

 3 Figure 3: (top) Automatic transfer of a skirt inspired by Figure 2 from a tall model (a) to a short and stocky one (b). (bottom) Scaling the skirt patterns (c) naively according to difference in height and hip circumference (d) results in uneven hem length and baggy skirt (e).

Figure 4 :

 4 Figure 4: Mother-daughter dresses: (left) traditional grading; (right) our variation. c Laurence Boissieux 2012

Figure 5 :

 5 Figure 5: Algorithm Overview: Given the dressed source character and a target one (a), we first proportionally scale the 3D garment to obtain a transferred version that satisfies proportionality and fit (b). Then, an iterative optimization process combines the source garment normals and the positions generated by the scaling to obtain a design preserving transferred garment (c).

  Given a garment vertex pg, we first compute its closest points p b on each bone of the animation skeleton (p b is possibly an extremity). For each bone, we define pm as the input character point closest to pg along the segment [p b , pg]. Such a point necessarily exists since p b is inside, and pg outside the character model. To select one or more reference points we consider both the distance from pg to each of the intersections pm and the angle between the bone axis v b and the vector pg -p b as we prefer these two vectors to be orthogonal. The pairs (p b , pm) we select as reference for pg are those that minimize a combination of these two metrics pm, pg e -<v b ,v> 2 σ 2

Figure 6 :Figure 7 :

 67 Figure 6: (left) Selecting closest skin points m1 and m2 as reference points for p1 and p2 is suboptimal, as they can move apart on the target character, causing an undesirable vertical displacement. Selecting the orthogonal direction, will map both points to a circle around the same bone point, preserving the relative height. (center) Association to multiple reference points is necessary to correctly account for regions roughly equidistant to multiple bones. (right) Association must depend on angle as well as distance to nearest intersection, giving preference to p 1 m over p 2 m .

Figure 8 :

 8 Figure 8: The impact of fit settings: (a) source; (b) enforcing fit across all the tight regions on a pregnant female leads to undesirable increase in curvature and focuses attention on the belly; (c) with no fitting enforced the garment transferred to a male looks implausible. (d) Our results for both models with fit enforced selectively.

Figure 9 :

 9 Figure 9: Collision resolution order: (a) unconstrained solution with step one collisions highlighted, (b) converting all collisions into equality constraints at once leads to undesirable artifacts on the belly (see inset zoom). (c) Incremental solution within one iteration resolves all collisions on the chest (step two collisions highlighted) and in a few iterations generates better transfer results with all collisions resolved (d).

  Figure 9 (b) versus Figure 5 (c). The actual collision detection can be done very efficiently by intersecting the segment(s) p -p b (where p b is the reference bone point associated with p) with the mesh representing the target character and performing an inside/outside test by comparing skeletongarment vs skeleton-character distances. While in theory the garment can intersect other areas on the skin, this had never happened in practice. In the case of penetration, we recompute p by projecting the vertex a small distance outside the model along the current segment p -p b and add the highest triangle adjacent to the vertex to F (Figure 9, c), treating the triangle as tight fitting for further computations.

Figure 10 :

 10 Figure 10: A multi-layer flamenco dress transferred from a woman to a girl. The undistorted texture highlights our method's ability to automatically generate appropriate patterns. c Laurence Boissieux 2012

Figure 11 :

 11 Figure 11: Validation on a real dress: we transferred the woman's dress on the top-left to a Numina doll model c Dollcis (top-right) and used the patterns to make an outfit for the real doll (bottom). The virtual source and real graded patterns for the front and back of the dress at bottom right. c Laurence Boissieux 2012

Figure 13 :

 13 Figure13: Top: A dress (a) transferred to a fatter model using skinning[START_REF] Wang | Design automation for customized apparel products[END_REF]] (b) shows visible artifacts along silhouettes. On this dress (c,d) our automatic method (yellow) generates slightly better results than the user assisted approach of[START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] (blue) (arrows point to undesirable artifacts). Bottom: When transferring a dress (Figure12, top) to a more different pregnant model, using the indicated user-specified profiles (a)[START_REF] Meng | Flexible shape control for automatic resizing of apparel products[END_REF] (blue) generate severe artifacts, in a dress which is not physically plausible (floating around the belly). In contrast, our automatically generated output (yellow) reflects the input design.

Table 1 :

 1 Result statistics (left to right): model, size in triangles (shown once per source input), transfer time, reference point computation (Section 4.1, done once per source model), number of iterations overall, and number of resolved collisions. For the flamenco dress the numbers for the three layers are combined. the output garments of Meng et al. and ours are of comparable quality. Note however that Meng et al. use manually traced profile curves, with a subset of those shown in the figure, to generate the output dress. Our transferred dress is generated automatically.However, close examination reveals artifacts on the dress created by the user-assisted technique, not present in our outputs. The differences are drastically more pronounced when a dress is transferred form a non-pregnant to pregnant model (bottom). The result of Meng et al. retains the "skinning" effect around the belly, leading to an unnaturally looking and physically implausible result. In contrast, as demonstrated throughput the paper on this and other inputs our method can handle extreme changes in body shape and proportions, while preserving source design.

	Model	# ∆	runtime	init	# iter.	# coll.
	Short woman dress	8178	61s	15s	19	15
	Pregnant w. dress		189s		64	57
	Man dress		99s		34	18
	Pregnant woman Tunic	9102	70s	16s	23	13
	Man over-all	11631	181s	19s	46	34
	Pregnant w. over-all		112s		28	18
	Short w. t-shirt/trousers	6282/7563	14s/ 36s	10s/10s	3/12	0/9
	Pregnant w. t-shirt/trousers		76s/137s		39/57	34/38
	Man t-shirt/trousers		32s/32s		10/10	7/9
	Girl 60s dress	11864	86s	8s	20	13
	Doll 60s dress		171s		43	38
	Girl layers	6274/5979	11s/10s	9s/ 9s		0/2
		5322	16s	9s	12	4
	Girl flamenco	18560	76s	11s	12	5
	Girl dancer top/bottom	4879/8809	89s/17s	5s/3s	38/10	32/6
	Male dancer top/bottom		40s/23s		14/15	8/8
	Tall dancer top/bottom		37s/21s		13/13	7/7
	Fat dancer top/bottom		199s/49s		81/36	67/23

]. The models were graciously provided by the authors. As clearly demonstrated by Figure

13

(b) skinning-like approaches create undesirable artifacts, avoided by our method. For similarly proportioned source and target models such as the dress in Figure

13

(top),

Acknowledgements

We would like to thank Nurit Perla for her valuable input and result evaluation and Paul Pham for permission to use the Numina doll. This research was partially funded by NSERC, Killam fund, MITACS and GRAND NCEs, and by the ERC advanced grant EX-PRESSIVE.


Valmi Dufour-Lussier

Florence Le Ber

Jean Lieber

Laura Martin
email: laura.martin@mirecourt.inra.fr

Adapting Spatial and Temporal Cases

Keywords: adaptation, case-based reasoning, qualitative algebra, spatial reasoning, temporal reasoning

Qualitative algebras form a family of languages mainly used to represent knowledge depending on space or time. This paper proposes an approach to adapt cases represented in such an algebra. A spatial example in agronomy and a temporal example in cooking are given. The idea behind this adaptation approach is to apply a substitution and then repair potential inconsistencies, thanks to belief revision on qualitative algebras.

Introduction

Qualitative spatial and temporal reasoning (QSTR) as a research domain has been active since the beginning of the 1980s. The paradigm has been exploited to help solve planning and constraint satisfaction problems, but rarely within casebased reasoning (CBR). Nevertheless, many domains in which QSTR is used could be addressed with CBR because the knowledge involved is usually contextual and incompletely formalised. This is the case in the domain of landscape agronomy, in which knowledge is acquired from farm surveys and from schematic descriptions of the spatial organisation of farming territories. Another example is the cooking domain, in which some knowledge is of a temporal nature.

This paper proposes an approach for the adaptation of spatial and temporal cases, which is based on a process integrating substitution and revision-based adaptation. One may, for instance, want to replace a plot of maize with a plot of a different crop in a farm, or to replace mushrooms with carrots in a recipe. Mere substitution is insufficient, because not all crops, nor ingredients, are used in the same way. It is therefore supplemented with a belief revision process through which the spatial representation of the farm or the temporal representation of the recipe are changed to be consistent with domain knowledge.

Section 2 justifies the paper's approach by introducing two examples from the farming and cooking domains. Section 3 then introduces the formal notions required for the approach, namely in terms of CBR, revision-based adaptation, and QSTR. The approach is then defined in details in section 4, and an algorithm is described in section 5. Section 6 illustrates those formal notions and the results of the algorithm using the two examples introduced in section 2. Related work is discussed in section 7. Section 8 concludes and presents some future work.

Introduction of the running examples

This section describes two examples in which a mere substitution would not yield an acceptable adaptation of a retrieved case with respect to the target problem. In the first example, the spatial adaptation of a farm must take into account agronomic knowledge about the location of fields with respect to the environment and cropping constraints. In the second example, the temporal adaptation of a risotto recipe must take into account cooking knowledge about the length required to cook different vegetables.

A spatial, agronomic example

Spatial adaptation is illustrated using the example of Miscanthus allocation practices in agriculture. Miscanthus is a perennial grass currently promoted as a renewable source of energy in Europe to produce high yield of biomass with low input [START_REF] Clifton-Brown | Miscanthus biomass production for energy in Europe and its potential contribution to decreasing fossil fuel carbon emissions[END_REF]. Its potential to reduce greenhouse gas emission is dependent to its spatial allocation into farmlands [START_REF] Hillier | Greenhouse gas emissions from four bioenergy crops in England and Wales: Integrating spatial estimates of yield and soil carbon balance in life cycle analyses[END_REF], therefore modelling spatial land use changes into farmlands is of great interest.

CBR can be used to model Miscanthus spatial allocation. The problem is the a crop production requirements and the farm description, and the solution is a crops spatial allocations. A farm description is defined by a cropping plan (the crop proportions/allocations into farmland) and by the spatial farmland features (e.g. the spatial relations of plots with buildings, woodland and rivers).

In this example, illustrated by figure 1, a farmer who wants to cultivate Miscanthus is considered. A case corresponding to a maize farm could be retrieved (figure 1a), based on real cases surveyed in France [START_REF] Martin | L'insertion territoriale des cultures biomasses pérennes : le cas du miscanthus par dix agriculteurs de Côte d'Or[END_REF] and expert knowledge which identify similarities in Miscanthus and maize allocation requirements regarding temperature and soil moisture [START_REF] Zub | Agronomic and physiological performances of different species of Miscanthus, a major energy crop. a review[END_REF].

Replacing maize with Miscanthus (which is usually harvested from February to March in France) comes with a spatial constraint in the agronomic domain knowledge. Because access to plots by harvesting machinery is impaired by excess soil water in winter, Miscanthus must not be allocated near a river, in a flood-risk area, whereas maize can be planted up to a legal 5 metres from rivers.

Therefore, it is expected that the adaptation process would not only replace maize by Miscanthus, but also reduce the size of the plot so that it doesn't overlap with the flood plain of any nearby river (figure 1b). A better adaptation may break the plot into two parts and retain maize cultivation in the flood plain to ensure that this part of the farmland remains productive (figure 1c).

A temporal, cooking example

Temporal adaptation is illustrated through recipe adaptation, in the spirit of Taaable [START_REF] Cojan | Knowledge extraction for improving case retrieval and recipe adaptation[END_REF], a CBR application for cooking. If a user asks for a carrot risotto recipe and none is found in the case base, Taaable may retrieve a mushroom risotto recipe and suggest reusing it with mushrooms replaced with carrots.

Say the mushrooms are added to the rice 2 minutes before the end, and the cooking domain knowledge indicates that carrots must be cooked for 25 minutes in order to be done, whereas the rice must be cooked for 18 minutes. A proper adaptation would require not only the lengthening of the cooking time of the vegetables, but also a reordering of the actions in the recipe.

Background

Case adaptation

In this paper, Source, Target and DK respectively denote the case to be adapted, the target case and the domain knowledge. Source and Target are required to be consistent with DK. 6 Given Source and Target, the adaptation aims at building a new case, AdaptedCase. This case is built by adding some information to the target case (intuitively, Target specifies only the "problem part" of the query), and it has to be consistent with DK.

It is assumed that a matching step precedes the adaptation process, providing links between Source and Target. It is represented by a substitution σ, mapping descriptors of Source to descriptors of Target. As an example, in the system Taaable, matching is performed during retrieval [START_REF] Cojan | Knowledge extraction for improving case retrieval and recipe adaptation[END_REF]. This process, applied to the cooking example of the previous section, would have returned σ = mushroom carrot. In the following, this preprocessing step of adaptation is considered to be given and, thus, σ is an input of the adaptation process described in section 4.

Belief revision and revision-based adaptation

Belief revision. In a given representation formalism, a revision operator maps two knowledge bases ψ and µ to knowledge base ψ µ, the revision of ψ by µ. Intuitively, ψ µ is obtained by making a minimal change of ψ into ψ , so that the conjunction of ψ and µ, ψ ∧ µ, is consistent. Then, ψ µ is this conjunction. The notion of minimal change can be modelled in various ways, so there are various revision operators. However, postulates have been proposed for such an operator, such as the AGM postulates [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF]. These postulates have been applied to propositional logic [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] and well studied in this formalism. Given a distance dist on the set U of the interpretations, an operator dist can be uniquely defined (up to logical equivalence) as: the set of models of ψ dist µ is the set of models of µ that have a minimal distance to the set of models of ψ.

Revision-based adaptation. Given a revision operator , -adaptation consists simply in using this revision operator to perform adaptation, taking into account the domain knowledge:

AdaptedCase = (DK ∧ Source) (DK ∧ Target) (1)
The intuition behind revision-based adaptation is to reduce adaptation to an inconsistency repair. It has been studied in propositional logic [START_REF] Lieber | Application of the Revision Theory to Adaptation in Case-Based Reasoning: the Conservative Adaptation[END_REF] and, more generally, in metric spaces [START_REF] Cojan | Conservative adaptation in metric spaces[END_REF]. It has been generalised to multiple case adaptation using integrity constraint belief merging in [START_REF] Cojan | Belief merging-based case combination[END_REF]. Its principle has also been applied to adaptation in an expressive description logic [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF]. This paper applies it, with some differences, to qualitative constraint networks.

Qualitative representation of spatial and temporal knowledge

Definitions. A qualitative algebra is a relation algebra that defines a set B of binary relations applicable between two variables, usually representing points, intervals or regions. Allen interval algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF], for instance, introduces 13 basic relations between intervals, corresponding to the 13 possible arrangements of their lower and upper bounds. 7 relations are illustrated in figure 2a. The 6 others are the inverse of the first 6 (eq is symmetric).

IN DU [START_REF] Pujari | INDU: An interval & duration network[END_REF] extends the set of Allen relations by combining them with relations over the interval durations. For 7 Allen relations, there is only one possible duration relation (e.g. i {d} j implies that the duration of i is shorter than the duration of j). For the other 6, all three duration relations <, = and > are possible. This yields a total of 25 basic relations. They are written as r s , where r is an Allen relation and s is a duration relation.

Region connection calculi [START_REF] Randell | A spatial logic based on regions and connection[END_REF] are well-known spatial algebras. The most usual, RCC8, introduces 8 relations between regions, as shown in figure 2b. Qualitative knowledge can be represented as qualitative constraint networks (QCNs). A QCN is a pair (V, C), where V is a set of variables, and C is a set of constraints of the form V i C ij V j with V i , V j ∈ V , and C ij a set of the basic relations defined by the algebra (C ij is a relation that is a disjunction of the basic relations, i.e. i {r 1 , r 2 } j means that i is related to j with either r 1 or r 2 ). In IN DU, shortcut notations r ? and ? s respectively represent the Cartesian product of r and all possible duration relations and the product of s and all possible Allen relations (e.g., {m}

b is before m meets o overlaps s starts d is during f finishes eq equals (a) Allen interval algebra basic relations. X Y X {DC} Y X Y X {EC} Y X Y X {PO} Y X Y X {EQ} Y Y X X {TPP} Y Y {TPPi} X Y X X {NTPP} Y Y {NTPPi} X (b) RCC8 basic relations.
? = {m < , m = , m > }; {d} ? = {d < }; {?} = = {b = , m = , o = , eq = , oi = , mi = , bi = }.
A scenario is a QCN S = (V S , C S ) such that for each V i , V j ∈ V S , there exists one constraint V i {r} V j ∈ C S . S satisfies the QCN N = (V N , C N ) if S and N have the same set of variables and each constraint relation in S is a subset of the corresponding constraint relation in N . A scenario is consistent if a valuation can be provided for the variables such that all constraints are observed, and a QCN is consistent if it has a consistent scenario. Two QCNs are said to be equivalent if every scenario of the former is a scenario of the latter and vice-versa.

Revision of QCNs.

A QCN is a knowledge base and thus, the issue of revising a QCN ψ by a QCN µ can be addressed. In [START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF], such a revision operator is (b) For RCC8 [START_REF] Randell | A spatial logic based on regions and connection[END_REF].

Fig. 3: The relation neighbourhood graphs of two common qualitative algebras. defined, 7 following the idea of an operator dist (cf. section 3.2), where an interpretation is a scenario, a model of a QCN is a scenario that satisfies it, and a distance dist between scenarios/interpretations is defined as follows.

First, a distance d between basic relations of the considered algebra is defined. Formally, a neighbourhood graph whose vertices are the relations of the algebra is given, and d(r, s) is the distance between r and s in the graph. It represents closeness between relations. For instance, b and m are close (d(b, m) = 1) since they express similar conditions on the boundaries of the intervals (for the lower bounds: = for both; for the upper bounds: < for b and = for m). Figure 3 presents such graphs, respectively for Allen algebra and RCC8. d makes it possible to define dist, a distance between two scenarios S = (V, C S ) and T = (V, C T ) based on the same set of variables V, as:

dist(S, T ) = Vi,Vj ∈V,i =j d(r S (V i , V j ), r T (V i , V j )) (2)
where r S (V i , V j ) is the relation r such that

V i {r} V j ∈ C S .
Given two QCNs ψ and µ, the revision of ψ by µ returns the set R of scenarios satisfying µ that are the closest ones to the set of scenarios satisfying ψ. 84 Formalisation

Representation of the adaptation problem

Parametrised QCNs. It is assumed that the variables of the considered QCNs can be parametrised by elements of a given set P. A parameter p ∈ P is either a concrete parameter, p ∈ CP, or an abstract parameter, p ∈ AP: P = CP ∪ AP, CP ∩AP = ∅. A concrete parameter denotes a concept of the application domain, e.g. mushroom ∈ CP for the cooking example. In this example, the formal interval cooking(mushroom) represents the temporal interval of the mushroom cooking. The domain knowledge DK = (V DK , C DK ) is a set of constraints, for example:

C DK =       
cooking(rice) ? = 18 min (rice requires 18 min of cooking) cooking(x) {m} ? cooked(x) (when the action of cooking x is finished, x is cooked) 18 min ? < 25 min (18 min is shorter than 25 min)

       (3)
where rice ∈ CP and x ∈ AP. An abstract parameter must be understood with a universal quantification over the concrete parameters; e.g. cooking(x) {m} ? cooked(x) entails cooking(mushroom) {m} ? cooked(mushroom). Let N 1 and N 2 be two QCNs.

N 1 ∧ N 2 is the QCN N = (V, C) such that V = V 1 ∪ V 2 and
C contains the constraints of C 1 , the constraints of C 2 , and the constraints that are deduced by instantiation of the abstract parameters by concrete parameters appearing in N 1 and N 2 (technically, this instanciation of x ∈ AP to p ∈ CP is a unification [START_REF] Goguen | What is unification? In: Resolution of Equations in Algebraic Structures[END_REF]). For example, if N 1 = C DK defined by equation ( 3) and N 2 = ({cooking(tomato), cooked(tomato)}, ∅), then

N 1 ∧N 2 = (V, C) with C = C DK ∪ {cooking(tomato) {m} ? cooked(tomato)}.
Substitutions. The atomic substitution σ = p q, where p, q ∈ P, is the function from P to P defined by σ(a) = q if a = p a otherwise . A substitution is a composition σ 1 ; . . . ; σ n of atomic substitutions σ i . 9 Let σ = p q be an atomic substitution. σ is concrete if p, q ∈ CP. σ is an atomic abstraction if p ∈ CP and q ∈ AP. σ is an atomic refinement if p ∈ AP and q ∈ CP. A concrete substitution (resp., an abstraction, a refinement) is a composition of concrete atomic substitutions (resp., of atomic abstractions, of atomic refinements). Any concrete substitution σ can be written σ = α ; where α is an abstraction and is a refinement, as the following equation illustrates:

mushroom carrot = mushroom x ; x carrot
where mushroom, carrot ∈ CP and x ∈ AP. This can be shown as follows. First, σ can be written p 1 q 1 ; . . . ; p n q n with p i , q i ∈ CP and p i = p j if i = j. 10 Let x 1 , . . . , x n be n abstract parameters, let α i = p i x i , let i = x i q i , let α = α 1 ; . . . ; α n , and let = 1 ; . . . ; n . α is an abstraction, is a refinement and σ = α ; .

Let σ be a substitution. σ is extended on qualitative variables by applying it to their parameters. For example, if σ = mushroom carrot then 9 The composition of σ and σ , denoted by σ ; σ , is the function that associates to p ∈ P, σ ; σ (p) = σ (σ(p)) ∈ P. 10 Which can be shown inductively thanks to the following lemmas: (1) if p = q then p q ; p q = p q, (2) p q ; q r = p r, and (3) if p = p , q = p and q = p, then p q ; p q = p q ; p q.

σ(cooking(mushroom)) = cooking(carrot). Then, σ is extended to a

constraint c = (V i C ij V j ) by σ(c) = (σ(V i ) C ij σ(V j )).
Finally, σ is extended on a QCN by applying it to its variables and constraints:

σ((V, C)) = (σ(V ), σ(C)) where σ(V ) = {σ(V i ) | V i ∈ V } and σ(C) = {σ(c) | c ∈ V }.
Adaptation problem. An adaptation problem is given by a tuple (Source, Target, DK, σ). Source and Target are the representations of the source and target cases by QCNs with concrete variables (i.e. not parametrised by any abstract parameter). DK is a QCN representing the domain knowledge. σ = p 1 q 1 ; . . . ; p n q n is a concrete substitution such that each p i (resp., q i ) parametrises a variable of Source (resp., Target). DK ∧ Source and DK ∧ Target are assumed to be consistent (cf. section 3.1). The goal of adaptation is to build a consistent QCN AdaptedCase that entails DK ∧ Target, whose qualitative variables are obtained by applying σ on the qualitative variables of Source, and that is obtained thanks to minimal modification of DK ∧ Source.

Principles of revision-based adaptation of a QCN

A first idea to perform the adaptation, given a tuple (Source, Target, DK, σ), is to apply σ on Source, thus obtaining a QCN DK ∧ σ(Source) that may be inconsistent, and then restoring consistency. Although this gives a good intuition of the revision-based adaptation of a QCN, it is not consistent with the irrelevance of syntax principle. 11 . Indeed, any two inconsistent knowledge bases (e.g. two inconsistent QCNs) are equivalent: their sets of models are both empty. Thus, at a semantic level, repairing an inconsistent knowledge base is meaningless. By contrast, revision aims at modifying a consistent knowledge base with another consistent one, the conjunction of which may be inconsistent. This is one reason why we do not follow straightforwardly this first idea. Another reason is more practical: using revision of QCNs makes it possible to exploit the work of [START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF].

The revision-based adaptation consists first in decomposing σ in an abstraction α and a refinement : σ = α ; (cf. previous section). Then, α is applied to Source: a QCN DK ∧ α(Source) is built that is necessarily consistent since DK ∧ Source is consistent and every constraint of DK ∧ α(Source) corresponds to a constraint of DK ∧ Source. In other words, DK ∧ Source is consistent and is more or equally constrained as DK ∧ α(Source), so DK ∧ α(Source) is consistent.

The third step involves revision. The idea is to make a revision of ψ by µ where ψ = DK ∧ α(Source) and µ = DK ∧ Target ∧ N where N represents the following statement: "Each qualitative variable V i of α(Source) is constrained to be equal to its refinement (V i )." For this purpose, the relation eq for equality is used:12 V i eq (V i ). Therefore, N = (V , C ) where

V = α(V ) ∪ σ(V ) C = {V i eq (V i ) | V i ∈ α(V )}
µ is consistent since DK ∧ Target is and since each constraint V i eq (V i ) of N either is a tautology (when V i does not contain any abstract parameter refined by ) or links a variable V i that does not appear in DK ∧ Target with (V i ).

Then, ψ µ gives a set of scenarios and AdaptedCase is chosen among them. . For each pair of scenarios, the distance is calculated using equation [START_REF] Hillier | Greenhouse gas emissions from four bioenergy crops in England and Wales: Integrating spatial estimates of yield and soil carbon balance in life cycle analyses[END_REF]. The distance between a scenario S of µ and ψ is the smallest distance between S and any scenario of ψ. The distance between the QCNs µ and ψ is the smallest distance between a scenario of µ and the QCN ψ. Once all scenarios of µ and of ψ have been compared pair-wise, the distance between µ and ψ is known and the scenarios of µ equal to this distance are returned. Only consistent scenarios are to be considered. Path-consistency of a scenario 13 is a necessary and sufficient condition for consistency. 14

This condition is verified in time

O(|V | 3 ) if, for each V i , V j , V k ∈ V , r(V i , V k ) ∈ r(V i , V j ) • r(V j , V k ). All inconsistent scenarios are discarded.
Optimisations. Because of the complexity, limiting the search space is essential. Considering that the minimum of sums is never less than the sum of minimums, a lower bound on the distance between two QCNs can be obtained in time O(|V | 2 • |B| 2 ) by computing the pair-wise minimal distance for each constraint and summing those. Empirically, it appears that the actual distance is usually closer to this lower bound than to the maximal bound, which is a function of the length of the longest path in the neighbourhood graph.

Therefore, it is often profitable to set an initial upper bound on the distance between ψ and µ which is equal to the lower bound, and search incrementally. This search can be further optimised by computing the lower bound on the distance between a scenario S of µ and ψ, which can be done in time O(|V | 2 ). This bound makes it possible to discard altogether certain scenarios of µ and thus avoid having to generate all the scenarios of ψ over again. Of course, whenever a scenario of µ is found to be at an acceptable distance to a scenario of ψ, incremental search means it is not necessary to examine other scenarios of ψ.

Another worthwhile optimisation in problems larger than a few variables is computing the algebraic closure of the QCNs, which is obtained by enforcing path-consistency. That is, for each

V i , V j , V k ∈ V , C ik is replaced with C ik = C ik ∩ (C ij • C jk ) where • is extended on 2 B × 2 B → 2 B by R • S =
r∈R,s∈S r • s. This is repeated until stability, i.e. no relation is changed after considering all 3-tuples of variables.

The optimisations proposed herein maintain the completeness and correctness of the algorithm, but they may prove insufficient to obtain a usable system. We think that approximation algorithms may give satisfactory results while running significantly faster. This will be the subject of future work.

Application on the running examples

This section revisits the examples from section 2. First, the agronomic example is taken in its simple form (where only Miscanthus is cultivated) to illustrate the algorithm. Then, the formalisation and the results are shown and discussed for the more complex form of the agronomic example and for the cooking example.

Simple agronomic problem

Consider a farm with one maize plot being adjacent to a river. To address the fact that there is a difference in possible agricultural uses between the bed of the river and the zone with flood risks, it is broken in two regions, low water channel and flood plain, such that the former is a proper part of the latter and that their boundaries don't touch. This is expressed in RCC8 as low water channel {NTPP} flood plain. The fact that a maize plot is adjacent to a river is represented as plot(maize) {EC} low water channel.

A farmer wishes to cultivate Miscanthus in a similar setting, prompting the retrieval of the farm case just described. A substitution must be applied: σ = maize Miscanthus = maize x ; x Miscanthus. An important knowledge about Miscanthus is that it must not be cultivated in a zone susceptible to flooding, which can be expressed as plot(Miscanthus) {DC, EC} flood plain.

In this example, ψ contains the constraints The first step in the algorithm is to add missing variables and constraints. In the example, all four variables are present in both QCNs, but some relations are missing, e.g. between plot(Miscanthus) and low water channel. A constraint plot(Miscanthus) {DC, EC, PO, TPP, NTPP, TPPi, NTPPi, EQ} low water channel is therefore added to both µ and ψ.

This manipulation may complexify the QCNs, which is part of the reason why computing the algebraic closure is interesting. Here, the amount of potential scenarios is reduced from 1024 to 16 for ψ, and from 1024 to 4 for µ.

Then, the lower bound on the distance between ψ and µ is computed. Here, the lower bound is 3, which happens to be the distance between ψ and µ. Only one scenario T of µ is found at this distance:

ψ µ = {T } = {(V T , C T )} with C T =               
low water channel{NTPP} flood plain low water channel{DC} plot(x) low water channel{DC} plot(Miscanthus) flood plain{EC} plot(x) flood plain{EC} plot(Miscanthus) plot(x) {EQ} plot(Miscanthus)

              
The distance is the sum of the following replacements: EC becomes DC between plot(x) and low water channel (d = 1), {TPP, NTPP, PO} becomes EC between flood plain and plot(x) (d = 1), and {DC, EC, NTPPi, PO} becomes EQ between plot(x) and plot (Miscanthus) (d = 1).

In this scenario, the region plot(x) was reduced in order not to overlap with flood plain as it was equated to plot (Miscanthus). This corresponds to the allocation shown in figure 1b. It can be seen that the modification is indeed minimal, as the plot becomes externally connected to the flood plain, maximising the area used for Miscanthus cultivation. For instance, a result including flood plain {DC} plot(Miscanthus) would have been consistent with the domain knowledge but would not have constituted a minimal modification of ψ. Therefore, the adaptation is successful.

Complete agronomic problem

To obtain the more productivity-increasing adaptation described in section 2.1, the plot region is broken into plot1(x) and plot2(y), and = x Miscanthus ; y maize. In ψ, the only information about both plots is that they are externally connected to the low water channel.

The revision algorithm returns 5 scenarios. All of them address the domain knowledge and the constraint to maximise the size of the Miscanthus plot, but they vary in their allocation of maize. One corresponds to the allocation shown in figure 1c. The other ones are similar.

This example also shows that the algorithm handles multiple substitutions.

Cooking example

Most temporal aspects of recipes can be represented in IN DU by reifying cooking actions, ingredient states, and durations as intervals. For instance, the following could be included in the domain knowledge: cooking(carrot) {m} ? cooked(carrot) and cooking(carrot) ? = 25 min, with the provision that, e.g. 18 min ? < 25 min.

In such a simple problem, combining constraints is straightforward and makes it possible to limit the amount of variables. The problem described in section 2.2 can be compressed to just 4 variables by replacing duration intervals by duration relations between the relevant action intervals. In this representation, ψ contains

C DK =    cooking(rice) ? < cooking(carrot) cooking(rice) {m} ? serve cooking(carrot) {m} ? serve    C α(Source) = cooking(x){f < }serve
In Taaable, there is no firm adaptation constraint from Target (C Target = ∅) therefore µ contains simply the constraints

C DK =    cooking(rice) ? < cooking(carrot) cooking(rice) {m} ? serve cooking(carrot) {m} ? serve    C = {cooking(x) ? = cooking(carrot)}
The revision algorithm returns two scenarios which are predictably distinguished only by the duration relation between serve and the other actions, since this relation is defined as being unimportant in the domain knowledge.

One scenario T = (V T , C T ) is such that C T is    cooking(x){m > }serve, cooking(x){eq = }cooking(carrot) cooking(carrot){m > }serve, cooking(x){fi > }cooking(rice) cooking(rice){m > }serve, cooking(carrot){fi > }cooking(rice)   
In both scenarios, the lengthening of the vegetable cooking is associated with the inversion of the relation between the vegetable and the rice, i.e. f < becomes fi > , which corresponds to the expected order inversion between the start of both actions. Therefore, the adaptation is successful.

Related Work

Some recent work deals with a combination of CBR and spatial reasoning, for instance in order to improve web services for spatial information [START_REF] Osman | Semantic spatial web services with case-based reasoning[END_REF], or for spatial event prediction in hostile territories [START_REF] Li | Spatial event prediction by combining value function approximation and case-based reasoning[END_REF]. Older work already underlined the interest of CBR to analyse geographical data, e.g. for soil classification [START_REF] Holt | Case-Based Reasoning and Spatial Analysis[END_REF]. We worked on a CBR system to help agronomists analysing farm surveys [START_REF] Ber | Modeling and comparing farm maps using graphs and case-based reasoning[END_REF]. The model was based on conceptual graphs, with labelled vertices and edges, describing the spatial organisation of farm territories. The assumption was that similar spatial organisations correspond to similar functional organisations. The spatio-functional cases were represented within a description logic system, and reasoning relied on a combination of hierarchical classification (in the description logic sense), CBR and QSTR.

Several research work focused on the representation of time within the CBR framework. Most were interested in the analysis or in the prediction of temporal processes (e.g. breakdown or disease diagnosis starting from regular observations or successive events). The temporal aspect is generally taken into account from sequences of events or sometimes from relative or absolute time stamps [START_REF] Dojat | Scenario recognition for temporal reasoning in medical domains[END_REF][START_REF] Ma | A Framework for Historical Case-Based Reasoning[END_REF][START_REF] Sánchez-Marré | An approach for temporal case-based reasoning: Episode-based reasoning[END_REF]. Particularly, the problem of temporal adaptation has been given much attention in CBR with a workflow representation [START_REF] Minor | Towards case-based adaptation of workflows[END_REF]. Only a few work [START_REF] Jaczynski | WWW assisted browsing by reusing past navigations of a group of users[END_REF][START_REF] Dørum Jaere | Representing temporal knowledge for case-based prediction[END_REF] adopted a qualitative representation of time, such as the Allen interval algebra. In [START_REF] Dørum Jaere | Representing temporal knowledge for case-based prediction[END_REF], cases are represented by temporal graphs and the retrieval step is based on graph matching. In [START_REF] Jaczynski | WWW assisted browsing by reusing past navigations of a group of users[END_REF], cases are indexed by chronicles and temporal constraints, which are represented with a subset of Allen relations. Case-based planning (CBP, see e.g. [START_REF] Munoz-Avila | Case-Based Plan Adaptation: An Analysis and Review[END_REF]) is a research field which also deals with time. The main difference between classical CBP and our approach is that they deal with different types of knowledge: CBP deals with the achievement of goals and models actions by their applicability and effects, whereas our approach, applied to a process represented by temporal constraints between actions, deals with the known constraints between actions reified as intervals. Theoretically, these approaches could be combined, but they are generally designed for different purposes: classical CBP usually deals with efficiency and uses complete problem-solving knowledge whereas our approach deals with incompletely described knowledge (e.g. the effects of cooking actions are incompletely formalised).

Conclusion

Qualitative algebras are important to the field of knowledge representation and are especially useful for qualitative reasoning on space and on time, but their use in CBR has received very little attention so far. This paper focuses on the adaptation of cases represented in a qualitative algebra. A landscape agronomy example uses the spatial algebra RCC8, and a cooking example uses the temporal algebra IN DU. This adaptation uses the principles of revision-based adaptation and combines it with a matching between the source and target cases.

A prototype for adaptation of cases represented in a qualitative algebra has been implemented in Perl and applied to the examples of this paper, but it is very time-consuming and requires a lot of improvement in order to be integrated into an operational system like Taaable. Several optimisations are planned. First, the program can be optimised thanks to certain characteristics of the revision problem that are not taken into account by the current prototype:

-The fact that the source case usually represents a specific problem-solving episode, thus the QCN Source is usually satisfied by only few scenarios. -The fact that the difference between QCNs arise because of σ, which should therefore be looked upon as the possible origin of inconsistencies.

Second, the study of how a process of "repair propagation" in a QCN can be designed is planned. This is similar to the classical constraint propagation algorithm, and can also be likened to the adaptation process presented in [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF]. As the landscape agronomy example shows, the QCN can appear in the query of the CBR system. This means that for such an application, the comparison of QCNs also has to be done at retrieval time. A future work will be to study how to implement such a retrieval process.

At a more abstract level, this work, as well as all the previous studies on the use of belief revision and belief merging for single and multiple case adaptation (cf. section 3.2), shares some intuitive ideas with the notion of reuse based on asymmetric and symmetric amalgams (see, e.g. [START_REF] Manzano | Amalgam-based reuse for multiagent casebased reasoning[END_REF]). A precise comparison between these two general approaches to adaptation remains to be carried out.

  Another adapted case: a maize and Miscanthus farm.

Fig. 1 :

 1 Fig. 1: Crop spatial allocation example.

Fig. 2 :

 2 Fig. 2: Two common qualitative algebras.

C

  DK = {plot(Miscanthus) {DC, EC} flood plain} C α(Source) = low water channel{NTPP} flood plain plot(x) {EC} low water channel and µ contains the constraints C DK = {plot(Miscanthus) {DC, EC} flood plain} C Target = {low water channel {NTPP} flood plain} C = {plot(x) {EQ} plot(Miscanthus)}

  Input and Output. The revision algorithm takes as input ψ = DK∧α(Source), µ = DK∧Target∧C , as well as a relation neighbourhood graph and a transitivity table for the algebra used. The neighbourhood graph enables to define a distance d between relations and the transitivity table defines a relation composition function• : B × B → 2 B , for example, m • mi = {eq, f, fi} in Allen algebra.The revision algorithm returns a set of scenarios of µ and their distance to ψ.Algorithm. First, it is necessary to ensure that all variables in either QCN are present in the other QCN as well. All pairs of variables that have no relation associated to them are given the relation B-the unspecified relation.The algorithm must then generate all the scenarios of µ and of ψ and measure their distance pair-wise. The amount of scenarios for a given QCN is of the order of O |B|

	5 Algorithm and implementation
	|V |•(|V |-1)
	2

If a case Source from the case base is inconsistent with the domain knowledge, a consistency maintenance process should be triggered to restore this consistency. If a query to the CBR system is inconsistent with the domain knowledge, it either should be rejected (e.g. "I want a recipe with apples but without fruit" is rejected by Taaable since DK entails that apples are fruits), or DK should be modified.

Technically, the authors of[START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF] define a merge operator taking a coercive QCN as a parameter. A revision operator can be defined using this merge operator.

This slightly differs from the definition of revision given in section 3.2 where ψ µ is a knowledge base, not a set of models. This is due to the fact that there may be no QCN that has R as set of scenarios satisfying it.

This states that an inference remains valid when replacing formulas by logically equivalent formulas. This principle is usually observed in belief revision[START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF], i.e. if ψ ≡ ψ and µ ≡ µ , then ψ µ ≡ ψ µ .

eq is eq = for IN DU and EQ for RCC8.

A scenario is path-consistent if, in each 3-tuples (Vi, Vj, V k ) of variables, for each consistent valuation of Vi and Vj, there exists a consistent valuation of V k . In RCQs, this is checked with transivity tables indicating the possible results of the composition of any two relations.