Cloud Shao

Adrien Bousseau

Alla Sheffer

Karan Singh

CrossShade: Shading Concept Sketches Using Cross-Section Curves

Keywords: CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-; sketching, product design, sketch-based modeling, non-photorealistic rendering, cross-sections

a) Input curves (b) Estimated normals (c) Shading Figure 1: Concept sketches (a) frequently use cross-sections (drawn in orange) to successfully convey 3D shape with just a handful of lines.

We derive the mathematical properties of cross-section curves and leverage them to automatically estimate surface normals across the drawn objects (b). The resulting normal field allow users to shade the objects using a variety of shading styles and setups (c).

Introduction

Designers use line drawings, or concept sketches, to quickly convey a mental 3D model during the early phases of the design process [START_REF] Pipes | Drawing for Designers[END_REF]]. As illustrated in Figures 1(a) and 2, effective drawings frequently rely on cross-sections and other construction lines as an aid to both the sketching process and the mental reconstruction of a 3D form [START_REF] Robertson | How to Draw Cars the Hot Wheels Way[END_REF][START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. While concept sketches facilitate viewer understanding of 3D shapes, they require a mental leap to imagine the appearance of the drawn object, imbued with specific material properties and lighting. Designers usually convey a more comprehensive 3D-look by artistically shading these sketches (Figure 2 d). This shaded imagery, often referred to as production drawings, is the traditional mode of communicating 3D concepts between designers and their patrons. However, production drawings require significantly more time, effort and expertise to create than the concept sketches on which they are overlaid [START_REF] Pipes | Drawing for Designers[END_REF][START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. They are also often laboriously redrawn for different shading parameters, such as changes in colors, materials or lighting conditions. While modeling the objects in 3D can substitute the manual shading process, for a variety of reasons artists avoid 3D tools at early stages of the design process [START_REF] Pipes | Drawing for Designers[END_REF][START_REF] Cook | Behind the scenes at pixar[END_REF][START_REF] Bae | ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models[END_REF], as explained in Section 2.

Our work bridges the gap between concept sketches and production drawings by facilitating 3D-like shading with user-desired rendering styles and parameters (Figure 1). We target sketches based on cross-sections and use the drawn curves to successfully estimate the surface normals necessary to convey a 3D-look. Designers can use our system to draw curves from scratch or over existing sketches. This approach integrates seamlessly with the traditional sketching workflow since cross-sections are a standard artistic tool for communicating shape and can be added at will to a sketch.

Cross-section curves depict intersections of the imagined 3D surfaces with 3D planes [START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. These curves, and especially their intersections or cross-hairs, carry important perceptual shape information [START_REF] Stevens | The visual interpretation of surface contours[END_REF][START_REF] Knill | Perception of surface contours and surface shape: from computation to psychophysics[END_REF][START_REF] Mamassian | Observer biases in the 3D interpretation of line drawings[END_REF]]. Consequently, designers draw cross-sections at places where they maximize sketch clarity (Figure 2). Despite their ubiquity there is no consensus in the design or perception literature on where cross-sections are drawn or what exactly they aim to convey. To answer these questions we compile insights from design books, sketching tutorials, and perception literature and use those to formulate the connections between the drawn 2D cross-sections and the 3D geometry they convey (Section 3). Specifically, we note that cross-hairs typically represent curves that lie in orthogonal planes and that individual cross-sections simultaneously suggest lines of principal curvature and geodesics. The interconnectivity of crosssection curves enables viewers to resolve conflicts between local cues to arrive at a consistent global interpretation.

We restate these connections in mathematical terms to infer the 3D shape of the cross-section curves from the sketch (Section 4). The extracted 3D cross-sections define 3D surface normals at crosshairs, which we then propagate along and in-between curves using a hybrid lofting approach which aims to align the surface curvature lines with the cross-sections. We validate our observations and algorithm by comparison of surface normals to those perceived by humans, and to ground truth data (Section 5).

The extracted normal field provides for new rendering capabilities, allowing users to dynamically visualize the effects of different materials, lighting conditions and rendering styles over the depicted shape (Section 6).

In summary, we present the first approach to facilitate 3D-like production shading of 2D cross-section based concept sketches. From a technical standpoint, this paper introduces two contributions:

• An explicit mathematical formulation of the relationship between sketched cross-section curves and the 3D geometry they aim to convey.

• An algorithm for extracting a normal field from cross-section curve networks based on the formulation above.

While our goal is not to reconstruct an actual 3D model, our estimated surface normals have the potential to accelerate the 3D modeling phase of the design process. We also note that our work is most relevant in contexts where cross-sections are traditionally used, such as production design of man-made objects, but may also apply in other setups such as cartoon rendering.

Related Work

Production Design Workflow. Concept sketches are widely used in the early stages of product design to quickly illustrate concepts and are then refined and shaded for presentation to the client [START_REF] Pipes | Drawing for Designers[END_REF][START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. In current practice, designers have access to the alternate workflow of transforming concept sketches into a complete 3D model, which can subsequently be shaded. While an approved and finalized concept will indeed undergo this transformation for use in downstream manufacturing processes, this is undesirable for early conceptual design for various reasons. Direct sketching allows designers to express ideas faster, with far fewer preliminary steps and distractions than 3D modeling tools [START_REF] Pipes | Drawing for Designers[END_REF][START_REF] Bae | ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models[END_REF]]. In addition, 3D modeling from sketches is time-consuming, regardless of whether it is undertaken manually using sketches as a reference, or using 3D curve sketching tools and then manually surfacing the collection of curves. Much of this 3D modeling effort is also wasted, given the frequency of iteration in the early design stages [START_REF] Cook | Behind the scenes at pixar[END_REF]].

Colorizing and Shading Sketches. Designers commonly use painting tools such as Alias SketchBook Pro c and Adobe Photoshop c to shade their sketches. More advanced colorization tools propagate scribbles to accelerate the definition of constant color regions in the drawing [Sýkora et al. 2009]. Recent methods support smooth color variations using a few vector primitives [START_REF] Orzan | Diffusion curves: A vector representation for smooth-shaded images[END_REF][START_REF] Finch | Freeform vector graphics with controlled thin-plate splines[END_REF]. Despite these advances, painting convincing 3D-like shading and highlights still requires a great amount of artistic skill and time. Our method goes one step further by deriving surface normals directly from the sketch, allowing users to edit high-level scene properties such as material appearance and lighting instead of color regions.

Sketching 3D models. Although our goal is not to reconstruct a complete 3D model, our work is related to sketch-based modeling methods, reviewed by [START_REF] Olsen | Sketch-based modeling: A survey[END_REF]]. Most such methods, e.g. [START_REF] Igarashi | Teddy: a sketching interface for 3d freeform design[END_REF][START_REF] Nealen | Fibermesh: designing freeform surfaces with 3d curves[END_REF][START_REF] Bae | ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models[END_REF], require users to sketch from multiple views to create an unambiguous 3D shape. Our approach is more related to methods that extract 3D information from a single sketch. Schmidt et al. [2009b] use scaffolds to support single and multi-view sketching of 3D curves. Our approach builds on similar ideas but exploits a different family of construction lines. In addition, we complement the 3D curves with normals across the drawn objects. [START_REF] Gingold | Structured annotations for 2D-to-3D modeling[END_REF] use interactive annotations over a pre-defined set of geometric primitives to facilitate 3D modeling from a single sketch. Our method is not restricted to specific shapes and requires little interaction beyond sketching and labelling cross-sections. [START_REF] Andre | Crosssketch: freeform surface modeling with details[END_REF] use a grid of orthogonal geodesics to generate relief-like 3D models, while [START_REF] Andre | Single-view sketch based modeling[END_REF] allow users to model objects composed of ellipsoids by drawing their two major orthogonal cross-sections. We draw inspiration from both papers, incorporating some of their observations on perception of intersecting contours into our formulation of cross-section properties (Section 3). We further refine them to account for a much more general set of shapes.

Sketching normal and height fields. Our approach is motivated by the work of [START_REF] Johnston | Lumo: illumination for cel animation[END_REF] and Winnemöller et al. [2009] that generate normal maps to shade cartoon images by diffusing silhouette normals inside the drawing. In a related work, [START_REF] Joshi | Repoussé: Automatic inflation of 2d artwork[END_REF] propose a method to inflate a thin-plate spline surface from boundary curves. The underlying assumption of these methods is that the normal or height map in the interior is a convex combination of the contour and silhouette normals or height values, which allows for shading a variety of blobby shapes but is rarely true for product sketches. Our method is especially well suited for this task, allowing for unlimited local normal control through crosssection specification.

Researchers proposed several indirect interfaces for specifying normal maps [START_REF] Zhang | Single view modeling of free-form scenes[END_REF][START_REF] Okabe | Single-view relighting with normal map painting[END_REF][START_REF] Wu | Shapepalettes: interactive normal transfer via sketching[END_REF]]. Instead our method is embedded in the traditional sketching workflow using curves that are commonly drawn by designers, without requiring additional indications apart from curve labeling. All of these methods propagate the known normals using a distance-based convex combination approach. We propose instead a lofting scheme based on Coons interpolation that better preserves the curvature directions provided by the cross-section curves (Figure 5).

Sketch and Contour Interpretation. Automatic line drawing interpretation aim to reconstruct shapes from silhouette and other feature lines [START_REF] Cooper | Line Drawing Interpretation. Springer. (a) Input curves (b) Normals (c) Shading[END_REF]], a challenging and often ill-posed task [START_REF] Malik | Interpreting line drawings of curved objects[END_REF][START_REF] Lipson | Optimization-based reconstruction of a 3d object from a single freehand line drawing[END_REF]. [START_REF] Ecker | Shape from planar curves: A linear escape from flatland[END_REF] address a related problem of depth estimation from planar curves formed by projecting arbitrary lines over a scene. Instead we address the potentially easier and better defined task of deriving 3D normals from artist-drawn cross-section curves, which a priori are positioned to best convey shape. Since there are no clear guidelines on where to draw cross-sections, we attempt to answer this question ourselves. Our work therefore shares many similarities with [START_REF] Cole | How well do line drawings depict shape?[END_REF], where the authors investigate the location of feature lines in line drawings.

There is also a significant body of perception research on how viewers interpret drawn lines, and especially intersecting curves. We discuss these works in detail in the next section.

Understanding Sketched Cross-Sections

While a sparse set of arbitrary cross-sections is too ambiguous to represent 3D shape [START_REF] Ecker | Shape from planar curves: A linear escape from flatland[END_REF]], strategically placed crosssections are widely used by designers to successfully convey 3D surfaces. Unfortunately, design literature provides no single, definitive answer as to where cross-sections should be drawn, what they should represent, and how they are perceived by viewers.

To address these questions we investigated design practices via conversations with designers, video-taped sketching sessions, and reviewed a collection of imagery and design texts [START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF][START_REF] Robertson | How to Draw Cars the Hot Wheels Way[END_REF]]. Viewer perception must, consciously or not, influence designers who ultimately aim to maximize the sketch clarity. Consequently, we combine our observations with findings from perception literature. We use all of these to propose five mathematical properties of designer-drawn cross-sections. and perception studies [START_REF] Stevens | The visual interpretation of surface contours[END_REF]], indicate that designers consistently use orthogonal planes for intersecting crosssections. Mathematically, this relationship can be stated as requiring the plane normals n1 and n2 to satisfy

n1 • n2 = 0.
(1)

t 1 t 2
2. Cross-Sections as Curvature Lines:

Designer conversations, imagery and literature consistently communicate curvature and local reflective symmetries at crosshairs: "Cross-sections on a surface explain or emphasize its curvature", "...bend or transform the object's surface.", "...are added to clarify the intended shape and keep it symmetrical." [START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. This is verified by perception studies which indicate that observers interpret intersecting curves as aligned with the principal lines of curvature [START_REF] Stevens | The visual interpretation of surface contours[END_REF][START_REF] Mamassian | Observer biases in the 3D interpretation of line drawings[END_REF]. Locally this implies that the tangents to the cross-section curves at cross-hairs are orthogonal:

t1 • t2 = 0.
(2)

The more global implication of this observation is that the curvature tensor on the mentally reconstructed 3D geometry around the cross-hairs is aligned with the cross-section curves. Note that, since curvature lines on surfaces are not necessarily planar [do Carmo 1976], cross-section curves may deviate from curvature lines away from cross-hairs. While one can draw cross-sections that do not satisfy plane or tangent orthogonality, see Figure 3, viewers are likely to interpret those as representing a different geometry that conforms to the two criteria.

Cross-sections as Local Geodesics:

A surface curve is a geodesic if it defines the shortest distance between two points. If a planar curve is a geodesic then the surface normal along it lies in the 3D plane of that curve [do Carmo 1976]. Perceptual studies [START_REF] Knill | Perception of surface contours and surface shape: from computation to psychophysics[END_REF]] indicate that, without cues to the contrary, humans perceive intersecting cross-section curves as geodesics. To express this property we first prove that given the plane and tangent orthogonality constraints, the normal to the supporting plane of a geodesic cross-section curve is co-linear with the tangent of the intersecting curve at a cross-hair. The surface normal at a cross-hair n is orthogonal to t1 and t2. If cross-section i is a geodesic then n is also orthogonal to ni. However we cannot have four mutually orthogonal vectors in R 3 , thus ni must be collinear with tj. When both curves are geodesics we have:

t1 × n2 = 0, t2 × n1 = 0. ( 3
)
Under this assumption, the degrees of freedom for both tangents and normals diminish radically [START_REF] Stevens | The visual interpretation of surface contours[END_REF][START_REF] Andre | Crosssketch: freeform surface modeling with details[END_REF].

n 1 n 2 t 1 t 2
While cross-hair plane and tangent orthogonality constraints together force one of the curves to be a surface geodesic (see Appendix), one can easily find crosssection sketches where the second curve is not a geodesic, such as the circular crosssection of a cone (see inset). Despite this, we found a clear tendency by viewers to perceive normals which were as consistent as possible with the geodesic interpretation subject to other visual cues (see Section 5).

4.

Minimal Foreshortening: When drawing a shape, designers favor informative viewpoints that convey most visible surfaces with minimal foreshortening [Eissen and Steur 2011]. Such viewpoints were shown to improve sketchability by [START_REF] Bae | ILoveSketch: as-natural-as-possible sketching system for creating 3d curve models[END_REF]. Isometric and dimetric projections are also commonly used in engineering drawings to avoid excessive foreshortening (see inset).

A single cross-hair is minimaly forshortened when both tangents lie in the viewplane. Using a coordinate frame where z is orthogonal to the view plane, one can capture foreshortening minimization over a cross-hair network by minimizing

(t z 1 ) 2 + (t z 2 ) 2 (4)
over all intersections. The Appendix shows that for a single crosshair this condition is equivalent to the normal alignment preference observed by [START_REF] Stevens | The visual interpretation of surface contours[END_REF]. Thus even though his study does not explicitly address foreshortening, it reinforces the minimal foreshortening hypothesis. Like the geodesic criterion, this is a weak cue, more important when the local surface is near perpendicular to the viewplane, but one that viewers correctly relax in the presence of contradictory cues (see the ellipsoid and inset (c) in Figure 9 ).

Orientation:

The perception of shape from intersecting cross-sections is subject to an inherent ambiguity between opposite normal orientations. The inset Figure illustrates how the same cross-hair can be interpreted as a convex surface with normal pointing down or as a concave surface with normal pointing up. Studies indicate that on average viewers prefer interpretations consistent with a view from above, and with convex rather than concave shape [START_REF] Mamassian | Observer biases in the 3D interpretation of line drawings[END_REF]]. Still, since individual interpretations vary, orientation choice cannot be fully automated in general.

t However, we observe that orientation can be determined uniquely when crosssections extend to a smooth silhouette of the drawn object. A smooth silhouette in our setup is defined as a line where the normal to a smooth surface is perpendicular to the view direction. By definition, the surface in the immediate vicinity of a smooth silhouette must be closer to the viewer than the silhouette itself (see inset). For a cross-section touching a silhouette, the inward pointing tangent at -offset from the intersection must have a positive depth, uniquely determining the orientation. In most concept sketches, the drawn silhouette cross-section intersections are sufficient for both viewers and our algorithm to completely resolve surface normal orientation.

Summary: Our analysis reveals five properties of cross-section curves relating 3D cross-section planes and tangents at cross-hairs, as well as a way to disambiguate the orientation of cross-sections that intersect smooth silhouettes. We validate these properties through a user study in Section 5.

Geometry Estimation Algorithm

Overview

We leverage the properties described above to estimate the normal field across objects in concept sketches based on cross-sections. We represent each sketch as a network of 2D annotated smooth curves, corresponding to cross-sections, smooth silhouettes, and other curves treated as patch boundaries. We use standard vector drawing tools to draw these curves. Our algorithm consists of two main steps illustrated in Figure 4.

Cross-Section Plane Estimation:

For each network of crosssections in the sketch, we estimate the support plane of each curve by casting the different cross-section properties as components in a constrained optimization formulation that solves for the plane normals and relative offsets (Section 4.2, Figure 4 (b)). The plane equations determine the 3D positions of the cross-section curves in a local frame.

Normal Propagation: We use the 3D curves to estimate normals across the drawn object. The surface normals at the cross-hairs are defined by the cross-product of the intersecting 3D tangents. We propagate these normals along and in between the curves in a manner consistent with the perception of cross-sections as principal curvature directions, by relying on a rotation minimizing construction inspired by [START_REF] Biard | Construction of rational surface patches bounded by lines of curvature[END_REF]] (Section 4.3, Figures 4 (c) and(d)).

An alternative workflow would be to use the 3D cross-sections to extract a depth field and use it to obtain normals. However, this alternative is not suitable for our needs. While normals are only affected by the object shape in the immediate vicinity, computing depth values across the entire object requires a global solution.

Moreover such a solution would need to be robust to depth inconsistencies which often show up in artist drawn sketches [Schmidt et al. 2009a]. Our approach which operates directly on normals sidesteps these difficulties. While depth can help with complex shading effects such as shadows, normals are sufficient to generate the aspired 3D look, for production drawings.

In the discussion below we use the view space coordinate frame where x and y are the horizontal and vertical axes of the image plane, and z is the vector pointing out of the plane. Recovering 3D information from 2D data typically requires inverting the projection transformation, a non-trivial task for free-hand sketches where even expert designers don't draw perspective accurately [Schmidt et al. 2009a]. Therefore, the formulation below implicitly assumes orthographic projection, accounting for weak perspective as well as other drawing imperfections through the use of tolerance-based, rather than exact, constraints.

Estimating Cross-Section Curve Planes

Given a network of curves, let ni be the normal to the plane of the ith cross-section and tij be its 3D tangent at the intersection with cross-section j. The 2D curves define the x and y coordinates for each tangent, such that only t z ij is unknown. To obtain the plane normals we combine the five properties above into a constrained minimization formulation. We enforce tangent and plane orthogonality, which are persistently satisfied by designer sketches, using constraints. However to allow for drawing inaccuracies we reformulate those as inequalities:

-≤ ni • nj ≤ -≤ tij • tji ≤ (5)
where = 0.1 = arccos(85 • ) for artist drawn sketches. We use a tighter threshold of = 0.05 for the ground truth comparisons (Section 5) where the 2D tangents are known to be nearly exact.

For a single cross hair combining both constraints with either geodesic alignment (Equation 3) or foreshortening minimization (Equation 4), leads to an under-constrained problem, with a continuous set of solutions. However, if both are enforced, the solution is unique up to orientation. At the same time these two criteria serve as weaker cues which are not always satisfied. We therefore cast the search for the planes as a constrained minimization where the objective function aims to satisfy both properties, subject to the inequalities:

min n i ij ( tji × ni 2 + tij × nj 2 ) + (t z ij ) 2 + (t z ji ) 2 . ( 6
)
The sum goes over all the intersections in a cross-hair network. We found that the equal weight assigned to both terms leads to results consistent with both ground truth comparisons and human perception (Section 5).

We also add equality constraints describing several obvious geometric relationships. Since each tangent is orthogonal to the corresponding normal we have

tij • ni = 0. (7)
Rather than enforcing the normals ni to be unit length, we found it more convenient to assume that n z i = 1 for all i. This equality reduces the degree of several of the terms, in particular making the optimized functional (Equation 6) quadratic and thus easier to minimize. This assumption works in the general position setup, where no cross-sections are perpendicular to the view plane, which is the typical case for concept sketches.

We also recognize that at each cross-hair, the intersecting 3D curves share the same depth z. Using this observation we associate an offset value ci with each plane that represents its location in 3D and express the offset using one equation for each of the planes at each cross-hair position x:

x • ni + ci = 0, x • nj + cj = 0. ( 8
)
Since n z i = n z j = 1, subtracting the two equations eliminates the depth variable and gives the offsets in terms of the normals and the x, y components of the cross-hair position which are known:

xx(n x i -n x j ) + xy(n y i -n y j ) + (ci -cj) = 0. ( 9
)
The offset is relative to one arbitrarily chosen origin cross-hair where we set the position to be (0,0,0) and the two crossing planes to have offset 0.

Solution:

We use the interior point method, as implemented in MATLAB, to solve for the normals and offsets. Since the number of variables is typically very small, we achieve near interactive results even though this is not the most efficient implementation.

A simple counting argument shows that for any loop of n crosssections with n intersections in general position, i.e. with no parallel tangents, the constraints alone fully define the normals up to an orientation choice. In other cases the optimization of the geodesic and foreshortening terms together similarly leads to a sparse set of solutions, defined up to local orientation choice at each cross-hair.

To obtain a consistent set of cross-hair orientations, we specify an initial guess for the optimization which reflects the orientation at two cross-hairs. We observe that for a single cross-hair one can compute an analytic solution which minimizes foreshortening, while enforcing the three other properties.The initial guess for the global solve consists of two such local solutions and zero for all other values.

If the network touches a silhouette curve, we select for the initial guess cross-hairs closest to the silhouette and make an orientation choice consistent with the orientation at the silhouette (Section 3).

If not, we select far apart cross-hairs and perform the optimization four times using the four possible orientation pairs as initial guesses. We then select the solution most consistent with the view from above prior. Users can enforce an alternative solution by fixing the orientation of one or more cross-hairs.

Once the curves' planes are obtained we have an approximation of the curve network in 3D space. We compute the 3D tangents at the intersections such that they lie in their respective planes. The 3D normal at each intersection is the cross product of the two tangents.

Normal Propagation

We use the computed 3D cross-section curves and the normals at the intersections to compute the normals across the object surface. To align the principal curvature directions with the crosssection curves, consistent with viewer perception, we need the normal gradients to align whenever possible with the curves. Existing normal propagation methods such as Lumo [START_REF] Johnston | Lumo: illumination for cel animation[END_REF]] and ShapePalettes [START_REF] Wu | Shapepalettes: interactive normal transfer via sketching[END_REF] do not achieve such alignment, even when the input normals are specified along the boundaries of a rectangular, parameterized domain, see Figure 5 (b,c), let alone when the normals are only specified at a sparse set of intersections or along open curves.

Instead we use a method inspired by the work of [START_REF] Biard | Construction of rational surface patches bounded by lines of curvature[END_REF]. They construct patches bounded by curvature lines from quadruplets of points with associated principal curvature frames, by first generating suitable 3D bounding curves with associated principal curvature frames and then use Coons interpolation to generate patches on which these curves serve as curvature lines. In our case the 3D curves we aim to align with curvature lines are already given, eliminating a significant degree of freedom. To approximate their construction we use a twist-minimizing propagation of principal curvature frames along the 3D cross-section curves and then use a variation of the Coons interpolation to obtain normals across the surface. to the current curve, the surface normal n, and the tangent t2 of the intersecting curve. We propagate those along the curves, such that the principal curvature frame at any point contains the tangent t to the curve at that point. To minimally rotate the rest of the frame we extract the angle of rotation between t1 and t around the axis of rotation t1 × t and apply the same rotation to the other frame components. For a portion of a cross-section curve bounded by only one intersection, this process is sufficient. For a segment bounded by two intersections we smoothly blend the rotated frames, obtained from the two intersections independently, using an arc-length based weighting. We use the normals defined by these frames, shown in Figure 4(c), to compute the normal field across the rest of the shape.

Interpolating Normals in-between Curves. To compute the normal field inside a four sided region bounded by cross-section curves with specified normals, we apply Coons interpolation directly to the curve normals, using discrete bi-linearly blended Coons patches [START_REF] Farin | Discrete coons patches[END_REF]. The obtained results visually align the lines of curvature with the cross-sections capturing the viewer perceived shape, as shown in Figure 4 (d). To apply this step however, we need to pre-process the curve networks to extract the four-sided regions as well as to process regions with different topology.

To obtain a well defined set of manifold regions, we extend "hanging" cross section end-points in the tangent direction to the nearest boundary or silhouette curve. We then extract the region connectivity from the intersecting curves by constructing a planar map [START_REF] Gangnet | Incremental computation of planar maps[END_REF]] which generates a list of regions bounded by curve segments. We distinguish four possible configurations:

1. The region is bounded by 4 cross-section curves. We directly apply Coons interpolation on the quad.

2. The region is bounded by n = 4 cross-section curves. We apply mid-point subdivision to generate n quads from the nsided face (Figure 6(a)). The faces resulting from this subdivision share normals along the artificial segments. To position the midpoint we use the templates described by [START_REF] Nasri | Filling N -Sided Regions by Quad Meshes for Subdivision Surfaces[END_REF]. To assign normals to each boundary between a pair of adjacent quadrilateral faces we use the discrete Coons formulation [START_REF] Farin | Discrete coons patches[END_REF] treating the two faces as a single quadrilateral domain. We then apply Coons interpolation in the interior of each face.

3. The region is bounded by more than 3 consecutive crosssection curves and by a boundary curve. We generate artificial normals along the boundary and we subdivide the resulting nsided face (Figure 6(b)). To assign normals to the boundary curve we copy normals from the opposite cross-section seg-ments and rotate the set of normals so that they agree with the normals of the adjacent segments at the extremities of the boundary (Figure 7).

4. The region is bounded by 2 or 3 consecutive cross-section curves and by boundary curves. We generate a quad that covers all the curves, and trim it to remove extraneous parts (Figure 6(c)). To do so, we first extend the cross-section segments in their tangential directions. We then close the quad with artificial sides that we generate by sweeping the existing crosssection segments against their adjacent segments. We apply Coons interpolation on the quad before trimming.

While other configurations may occur, we didn't observe them in design sketches. If such a configuration shows up users can easily resolve it by introducing additional cross-sections. If a face is bounded by n = 4 segments, we subdivide it (a). If a face is bounded by more than 3 cross-sections and by boundaries, we copy the normals of the cross-sections onto the boundaries via sweeping (b). If a face is bounded by 2 or 3 cross-sections, we create a quad by sweeping each cross-section against its adjacent segment, and trim the quad along the boundaries (c). We first copy normals from the segments opposite to the boundary. We then rotate the set of artificial normals so that they agree with the normals available at the extremities of the segment.

Validation

We validate the use of designer cross-sections for shading concept sketches in general and using our algorithm in particular via a combination of a user study and a ground-truth (GT) comparison. The first part of the study aims at the general question "Do design cross-sections effectively depict 3D shape?" by posing the following queries: Q1. Are viewers persistent, and consistent with each other in their perception of design cross-hairs? Q2. Are viewers accurate in their perception of cross-hairs? Q3. Is the persistence/consistency/accuracy of the perceived crosshairs correlated to a global context, and the geodesic, minimal foreshortening and up-orientation properties of cross-sections?

The study also serves to validate our algorithmic results by measuring similarity between them and viewer perceived cross-hair normals. Lastly we use the example corpus in the study to compare these results to GT normals.

User Study Design

Sketch data-set. We choose a corpus of 11 models (see Figures 8) of varying shape complexity and recognizability, depicted using silhouettes and cross-sections of varying interconnectivity. The corpus comprises 4 artist sketches and 7 ground-truth 3D shapes. While the former can be used to answer questions about persistence and consistency, they cannot be used to evaluate accuracy. Thus, to address accuracy we use ground truth shapes, depicted using cross-sections with orthogonal planes and tangents at cross-hairs. We deliberately select some cross-hairs that violate the geodesic and minimal foreshortening property to address Q3. We address context in Q3 by presenting the sketches in three forms: as complete sketches with cross-sections and silhouettes; as partial cross-sections clipped around cross-hairs at roughly a third of their arc-length; and as isolated crosshairs, randomly translated in the viewplane to mitigate any memory bias (see Figure 9). User Interface. For each cross hair we ask users to interactively specify the surface normal using a line connected to the cross-hair center, providing a 2D projection of the perceived normal. While gauges [START_REF] Koenderink | Surface perception in pictures[END_REF][START_REF] Cole | How well do line drawings depict shape?[END_REF]] are the more typical interface for querying normals, our pilot study, conducted using them revealed a user tendency to orient the gauge by attempting to turn the base into an ellipse whose axes were aligned with the cross-hair in the viewplane, introducing a bias error. Our interface avoids such bias since the cross-hair itself perceptually functions as a base.

User Study Protocol. Participants (25 designers and 30 nondesigners) were shown through a web interface, in random order, 50 to 80 sketches on which a single cross-hair normal was queried. Each cross-hair normal was queried twice at different points in the study. The overal task took 8-15 minutes.

User Study Findings

Overall 2706 normals were specified on 40 complete, 28 partial, and 14 isolated cross-hairs images. We use 2D angles to measure all differences. We found less than a 2 o difference in favor of designers on every measured statistic between designers and nondesigners, indicating similar perceptual acuity, and thus report combined statistics. We account for alternate interpretations when measuring persistence and consistency by reporting the acute angle between normal samples, but also the percentage of samples that are flipped (the angle between the normals is obtuse) (see Table 1). To avoid bias we do not discard outliers, as a result the median value is typically more representative than the average. Q1: Design cross-hairs are persistent, in that the difference between normals set twice by the same viewer at different points in the study is small, with the median standing at 6 o . They are also consistent, measured as a pairwise difference between normals across viewers, with a median of 10.6 o . Q2: Viewer perception of design cross-hairs normals is accurate when compared to GT, with a median of 8 o , and a mean of 14 o validating the orthogonal plane and tangent properties we used to construct our GT data. The deviation of user perceived normals is also comparable to that reported for other line drawing styles [START_REF] Cole | How well do line drawings depict shape?[END_REF]].

Q3:

The impact of global context on cross-hair perception is evident from the increase in the number of flipped orientations, in the computation of each statistic and general deterioration of consistency and accuracy from complete to partial to isolated cross-hairs. User normals on the cone (Figure 9) highlight the importance of context. Without context, (Figure 9 (a,b)) these normals are far from GT and largely consistent with both curves being geodesics, while still minimizing foreshortening (Figure 9 (a,b)). In context, the accuracy increases dramatically. Comparison of user normals on the ellipsoid, with and without context (inset (c)), shows similar effect with respect to foreshortening minimization. In the full context, in the presence of silhouettes, we did not observe flipped orientations. The results for the ashtray (concave) and bump (convex) (Figure 9,(e,d)) both reinforce viewer tendency to perceive the surface orientation as vertical and viewed from above, even when no silhouettes are present. However as demonstrated by the ashtray, the flipped orientation is preferred by a small set of users. For isolated cross-hairs, inputs with no clear up direction ( Figure 9 (a)), users are split almost evenly between the two choices.

Algorithm Validation

Table 1 shows our algorithmic cross-hair normals to be consistent with viewer perceived normals, on both GT and artist drawn inputs, with median difference of 8.5 o . It also highlights the accuracy of our method, showing that the 3D difference between the algorithmic normals and ground-truth data is 2.3 o , a near perfect precision. Figure 10 compares the normals estimated by our method with ground truth normals and normals diffused from silhouettes [START_REF] Johnston | Lumo: illumination for cel animation[END_REF]. While the midpoint subdivision introduces small errors in non-quad faces, our normal fields match ground truth closely and produce convincing shading. In contrast, normals from silhouette do not capture the internal structures of the shapes. 235 7805

Table 1: Summary of our validation data. (Left to right) persistence same user, consistency between users, accuracy wrt. to GT, accuracy with worst 5% of errors removed (notice the significant drop in the standard deviation), consistency wrt. to our solution, accuracy of our solution wrt. to GT.

Results

We tested our method on a variety of inputs, ranging from simple models such as the toothpaste or the sofa (Figure 11), to elaborate products like the car (Figure 13), the coffee-maker (Figure 13), and the camera (Figure 14). In all cases our method reconstructs a believable normal field which lends itself to the subsequent shading.

Rendering. While automatic shading quality can never match the expressiveness of manual artwork, our results capture many of the features commonly used in production drawings. We use the lighting model by [START_REF] Gooch | A non-photorealistic lighting model for automatic technical illustration[END_REF] to mimic illustrative shading. Users can additionally indicate the base color of the object using a standard painting tool. Following designers' practice, we apply the environment maps shown as inset to suggest studio lighting over glossy plastic (Figure 13, coffee-maker) and outdoor lighting over metal and car paint (Figure 14, robot). Finally we keep the cross-sections visible to convey shape, as suggested by [START_REF] Eissen | Sketching: Drawing Techniques for Product Designers[END_REF]. User Interface. Our system is based on an interactive interface where users sketch annotated lines either from scratch or on top of a pre-existing sketch. The accompanying video shows a typical drawing session. We provide a layer based interface to draw surfaces in different depths and support occlusion between overlapping layers. Our implementation of the normal estimation and propagation allows users to create normal fields interactively, with total runtime ranging from less than a second for simple models like the mouse (Figure 4, 2 layers and 14 curves) to around 30 seconds for multilayer sketches like the car (Figure 13, 17 layers, 119 curves). Most users draw layers independently in an iterative process. Users can then choose from a variety of rendering styles.

Conclusions

We presented a method for shading cross-section based concept sketches, enabling designers to easily convert such basic sketches into elaborate production drawings. The technical contribution of of our work is twofold. We identify and formulate five key properties of designer-drawn cross-sections and cross-hairs: orthogonality, alignment with curvature lines, alignment with geodesics, minimal foreshortening, and silhouette-consistent orientation. Then, we use these properties to automatically compute normal fields from sketched cross-section curve networks. Both the properties and the algorithm are validated through a combination of a user study with a ground truth comparison. In this comparison the median difference between our normals and ground-truth at cross-hairs was under three degrees, i.e. we obtained near perfect reconstruction.

Limitations. We make two assumptions about the input sketches.

We assume orthographic or near-orthographic projection (our inequality formulation can account for some perspective deformation, but not all), and general position -i.e. we expect the cross-section planes to not be orthogonal to the view plane, as the alternative is inherently ambiguous. Future Work. We foresee a number of areas for future work. We would like to combine cross-sections with other construction lines as well as other priors for processing different types of sketches. As an example, in addition to disambiguating orientation, smooth silhouettes could be used as an additional term in the optimization to enforce normals to be perpendicular to the view plane along them.

A more ambitious research direction is to extend our method to perform accurate geometry reconstruction, potentially relying on intrinsic symmetries to reconstruct occluded regions.

Figure 13: Results of our method on complex inputs. Insets show the original curves and manual shading for the coffee machine by Schmidt et al.[2009b] , and the user-provided base color for the car and sewing machine.

Figure 2 :

 2 Figure 2: Cross-section curves are commonly used by designers to depict shape variations. Cross-sections emphasize curvature (a) and symmetry (b), c [Eissen and Steur 2008]. Designers explore ideas quickly with concept sketches, some of which are refined and shaded for presentation (d), c Mike Serafin www.memikeserafin.com.

  Recommendations in sketching literature [Eissen and Steur 2008], plane-based 3D shape abstraction [McCrae et al. 2011],

Figure 3 :

 3 Figure 3: Cross-sections that violate tangent or plane orthogonality yield ambiguous drawings which viewers tend to interpret as having an alternative interpretation where both are orthogonal.

Figure 4 :

 4 Figure4: Our algorithm takes as input an annotated sketch (a). Orange curves denote cross-sections, blue curves represent smooth silhouettes, and green curves correspond to other object boundaries. We first optimize for the supporting plane of each cross-section and compute the 3C cross-sections based on those (b). We use the resulting 3D curves to compute 3D normals at each intersection and interpolate normals along the curves (c). We finally generate a normal field in between the curves using Coons' interpolation (d).

Figure 5 :

 5 Figure 5: Solving the Laplace or the Thin-Plate-Spline equations (b,c) propagates normals isotropically. Coons interpolation (d) better preserve the directionality of the curve network.

  At each cross-hair the curvature frame consists of the tangent t1

Figure 6 :

 6 Figure6: Illustration of our strategies to handle non-quad faces. If a face is bounded by n = 4 segments, we subdivide it (a). If a face is bounded by more than 3 cross-sections and by boundaries, we copy the normals of the cross-sections onto the boundaries via sweeping (b). If a face is bounded by 2 or 3 cross-sections, we create a quad by sweeping each cross-section against its adjacent segment, and trim the quad along the boundaries (c).

Figure 7 :

 7 Figure7: Sweeping normals from cross-sections onto boundaries. We first copy normals from the segments opposite to the boundary. We then rotate the set of artificial normals so that they agree with the normals available at the extremities of the segment.

Figure 8 :

 8 Figure 8: User study corpus comprising 4 artist sketches: car, tube, stapler and bump (top row), and 7 ground truth surfaces: cylinder, cone, ellipsoid, ashtray, bowl, trebol, torus (bottom row).

Figure 9 :

 9 Figure 9: Representative user (red), algorithm (black), and GT (green) normals on concept sketches and isolated cross-hairs. Insets (a) and (b) correspond to isolated cross-hairs on the cone and (c) on the ellipsoid. (a) highlights how absent the context viewers perceive the local surface as cylindrical, consistent with both crosshairs being geodesics; In (c) the same effect is evident with respect to foreshortening. With no context viewers select a normal which points more forward rather than sideways.

Figure 10 :

 10 Figure10: Comparison with ground truth normals and normals from silhouettes[START_REF] Johnston | Lumo: illumination for cel animation[END_REF]]. Our normal fields and shading match ground truth closely. Small deviations from ground truth appear in the center of the shape where midpoint subdivision is applied.

  Figure 12provides a visual comparison between sketches manually shaded with SketchBook Pro c and the result of our method.

Figure 11 :

 11 Figure11: Even on simple inputs the shading enabled by our method provides for a much richer, complex 3D look.

Figure 12 :

 12 Figure 12: Comparison between our shading and manually shaded sketches which we used as inspiration. Stapler by Che Yan, robot by Spencer Nugent c on http://www.sketch-a-day.com/.

  Our normal interpolation does not support open regions. As a result, users sometimes need to draw open contours in separate layers and close the regions with additional curves. Figure 15 illustrates how two layers are used to draw the open contour of a bump over a flat surface. Normal continuity across the additional curves could be enforced with a smoothing post-process around the curves.

Figure 15 :

 15 Figure 15: Limitation of our normal interpolation. The open contour of the bump needs to be closed and drawn in a separate layer to form valid regions for the Coons interpolation.

  (a) Traced curves (b) Normals (c) Composite shading (d) Alternative shading

Figure 14 :

 14 Figure 14: Variations on a theme: (top) our method makes it easy to apply different shading styles to models. (bottom) Users can trace over an existing image (a, shown as inset) and composite the resulting shading with the hand drawn sketch (c) or create other shading styles (d) through base color selection. Original sketches from Spencer Nugent c on http://www.sketch-a-day.com/.

Acknowledgments

Many thanks to Mike Boers for help with output rendering, Che Yan for sharing her design expertise, Maneesh Agrawala for fruitful discussions on shading in design sketches, and George Drettakis, Olga Sorkine, Pascal Barla and Romain Vergne for their comments on early versions of the paper. We also thank Koos Eissen, Roselien Steur, Spencer Nugent and Mike Serafin for allowing us to use their inspiring sketches. INRIA acknowledges generous support from Adobe and Autodesk (software and research donation) and NVIDIA (Professor Partnership Program). This research was supported by NSERC, GRAND NCE and MITACS NCE.

Appendix

Given the tangent and plane orthogonality properties, we prove that one of the plane normals must be collinear with the tangent of the other plane (i.e. one of the curves is a surface geodesic). Proof. We have t1 • t2 = 0, n1 • n2 = 0, t1 • n1 = 0, and t2 • n2 = 0. Assuming, t1 is not collinear with n2, then, these two vectors define a plane P , s.t. both t2 and n1 are orthogonal to it (as both are orthogonal to the two spanning vectors). Since a plane allows only one normal (up to sign), then t2 and n1 are co-linear.

Stevens suggests that users perceive the normal to a cross-hair as being orthogonal to the tangent bisector (see inset for notations) [START_REF] Stevens | The visual interpretation of surface contours[END_REF]]. We prove that this is equivalent to locally minimizing foreshortening (t z 1 ) 2 + (t z 1 ) 2 . Proof. Given tangent orthogonality, the local optimum of this term is obtained, given the tangent orientation in the inset, when t z 1 = -t z 2 . Let the outward normal n to the surface be defined as t1 × t2.

. This 2D normal is consequently orthogonal to the 2D bisector of tt1 and t2, b = ((t x 1 + t x 2 )/2, (t y 1 + t y 2 )/2), which is equivalent to the bisector condition.


Jebril Hadi

Christophe Tournassat

Stéphanie Betelu

Ioannis Ignatiadis

Laurent Charlet

Modeling the dioctahedral smectites layer charge variation versus structural Iron reduction level

come

Modeling the dioctahedral smectites layer charge variation versus

structural Iron reduction level Iron is one of the most common redox species in soils and sedimentary rocks. Amongst iron-bearing phases, phyllosilicates might play key roles in various bio-geochemical processes involving redox reactions, where structural Fe (Fe str ) can act as a renewable source/trap of electron.

A large set of data from kinetics, spectroscopic or electrochemical studies on dioctahedral smectites demonstrates that reduction of Fe str impacts many clay properties such as colour, layer charge, swelling pressure, colloidal properties that are linked to layer structural changes. Experiments also suggest that this mechanism is partly reversible, depending on type and properties of the primary oxidized clay, on how the reduction is induced (chemically and/or biologically) and on extent of iron reduction level.

The complexity of the involved mechanisms makes the prediction of Fe str redox properties challenging.

For instance, only empirical models are currently available to quantify structural changes as a function of reduction level. However, a predictive and mechanistic model of these changes is a prerequisite to develop a thermodynamic model for Fe str redox properties.

In this contribution, we propose a mechanistic statistical model to explain 2:1 layer excess negative charge changes induced by structural Fe(III) to Fe(II) chemical reduction (by dithionite). This model completes this published by [START_REF] Drits | A model for the mechanism of Fe 3+ to Fe 2+ reduction in dioctahedral smectites[END_REF] and was calibrated on data from our own and from the literature.

Actually, a large number of studies on Fe str redox properties (E h and kinetics) neglects the major structural changes that occur during redox reactions of this material and that are partially reversible, and are focused in measuring a single E h value. Actually, the complex relationship that exist between the different structural iron sites should lead to consider that not only one but several Fe(II)/Fe(III) poles (classes) must exist in the structure, thus exhibiting gradually decreasing E h values. Hence, further developments of our model will include Crystal Field Theory (CFT) calculation to identify the variety of Fe str redox potential, which arises from the varying Fe str neighbouring inside the same structure and along the redox processes.

Tournassat 1 , S.Betelu 1 , I. Ignatiadis 1 , L.Charlet 2

	1 BRGM, Environment and Processes Division, 3 Avenue Claude Guillemin, BP 36009, 45060 Orléans Cedex,
	France (*corresponding author: j.hadi@brgm.fr)
	2 ISTERRE, BP 53, 38041 Grenoble, Cedex 9, France

J. Hadi 1,* , C.

Acknowledgement

The research leading to these results has received funding from i) the European Union's European Atomic Energy Community's (Euratom) FP7/2007-2011 under grant agreement n° 212287 (RECOSY project) and ii) the ANDRA under the BRGM-ANDRA partnership (CAPTANDRA project, No N°045731SOS).


J Hadi

I Ignatiadis
email: i.ignatiadis@brgm.fr

C Tournassat

L Charlet

E Silvester

Investigations on structural iron electrochemical properties in layered silicates using massive mica electrodes

Nuclear waste repositories are being installed in deep excavated rock formations in some places in Europe to isolate and store radioactive waste. In France, the Callovo-Oxfordian formation (COx) is a potential candidate for a nuclear waste repository. The redox reactivity (kinetics and thermodynamic redox potential) of COx clay rock samples are already under study using microscopic, spectrometric and wet analysis techniques. In order to cross and overcome certain limits by improvement in the knowledge, specific electrodes should be constructed and devoted to the deepening of the electrochemical behaviour of the COx system in different situations. Iron is one of the most common redox species in soils and sedimentary rocks. Iron-bearing phyllosilicates play key roles in various biogeochemical processes. The complexity of the physical and chemical (along with structural) changes involving their structural iron makes the studies of its redox properties challenging. Most of the recent reported efforts were focused on probing Fe redox on finely powdered clay (and often micas) particles, and have been hampered by inadequate interactions between particles and electrodes. Moreover, such experiments usually involve redox probe ions, thus adding supplementary difficulties in the determination of structural iron redox parameters such as redox potential (Eh) and kinetics. The present study aims at qualitatively investigating the above mentioned phenomena on minerals like iron-bearing micas (Table 1). In the current work, we present initial insights regarding efforts to build a direct electrical interface between solid electrodes and conveniently shaped macroscopic mica crystals in order to investigate the redox properties of structural iron in dry and aqueous environments, in the presence of representative perturbations.

A classical three electrode system has been used for voltammetric measurements. Platinum plate (1cm²) was the counter electrode. Potentials have been measured against either silver-silver chloride electrode (Ag-AgCl/3M KCl) or Saturated Calomel Electrode (SCE/KCl sat ) as reference electrodes. Open Circuit Potential (OCP) measurements and Cyclic Voltammetry (CV) were realised as well as Long term OCP measurements, along with pH and other parameters, are also measured. Most of the experiments discussed here have been conducted in unbuffered NaCl or KCl 0.1 M solutions, at 25°C. Anoxic conditions were maintained by first bubbling N 2 and then maintaining a gas layer in the head space of the reactor. Long term measurements showed that in these conditions, pH stays at a value around 8.9

and is stable for several weeks. Experiments realised in buffered solution, at pH 7.5, using 1 mM Piperazine-1,4-bis(2-ethanesulfonic acid) (PIPES) and 2 mM NaOH did not show any observable change. In some experiments, 5 mM ferricyanide (Fe(CN) 6 3-

) have also been used as a redox probe. High resistivities previously have been reported for this type of material, ranging from 1010 to 1015 Ω.cm at room temperature. Given the current flows detection limit of the apparatus used for measuring (~nA), the mm-thick pieces used in first experiments should normally behave like insulating screens on Ag (or maybe Cu-Ag) electrodes, e.g. no current could be measured across the sample with low iron content. OCP measurement consists in measuring the electrode rest potential against a reference electrode, in absence of observable current. It provides a first indication on the type of material present on the support electrode; normally no potential should be measured in absence of an electrically conductive path. Unfortunately, first records showed that OCP can be measured immediately after the immersion of all the first electrodes prepared (Figure 1, left) even on muscovite and lepidolite, clearly indicating the presence of water in the different samples. However, signals obtained for lepidolite and muscovite are less stable and can only be conveniently recorded in absence of external perturbation around the electrode such as vibration or even air movement, whereas signals obtained for the different biotite samples are very stable. Changing parameters in the electrolyte such as pH (figure 1, right) removal of O 2 , or change in Cl-does not seems to affect the measured OCP of this type of electrode as it stay stable for days. Several week-longs monitoring on ten biotite electrodes, dipped in unbuffered NaCl 0.1 M, showed that the OCP slowly decreases and stays stable, at values between 0.1 and 0.14 mV/NHE (data not shown), despite occasional pH oscillation between 4 and 9. Results of these experiments show that several aspects of the designs of such electrodes have to be improved for further experiments. From these observations, we can't preclude that water might participate in the electrical contact between the support electrode and the solution, but we can still hypothesize that it could be due to interlayer traces of water, offering a poorly electrically conductive path in lepidolite and muscovite, whereas another mechanism might participate in the biotite sample. First, lowering of the water content in the mineral must be realised, using smaller crystals, longer drying and vacuuming time, and using more penetrating and impregnating resins. Platinum plates and evaporated platinum or carbon are envisioned for the inert support electrode. Using thinned slices should reduce electrical resistivity of the whole bulk structure, allowing a more convenient observation of the coupled electrons transfers that might occur between separated crystal surfaces. Hence, more suitable cutting techniques, such as wire sawing, should be planned to obtain thinner slices. More mica samples must also be selected, with higher and lower iron contents than the one used in the present experiments. This first set of experiments in interfacing solid electrodes and conveniently shaped mica crystals offers hope that this will be a valuable technique for probing structural iron.

Acknowledgement

The research leading to these results has received funding from i) the European Union's European Atomic Energy Community's (Euratom) FP7/2007-2011 under grant agreement n° 212287 (RECOSY project) and ii) the ANDRA under the BRGM-ANDRA partnership (CAPTANDRA project,No N°045731SOS).

Figure 1 :

 1 Figure 1: (left) OCP measurements recorded after immersion of various electrodes in NaCl 0.1M (pH 7.5). (right) Effects of HCl 0.1M repeated dropwise addition in the bathing electrolyte on a biotite electrode and on a platinum electrode.

Table 1 : List of micas, geographic origins, and structural formulas

 1

	Specie	Origin	Structural formula		Iron content (% wt)
	Biotite 1	Bancroft, Ontario	K 1.74 Na 0.17 [Fe 2+ (Si 5.94 Al 1.98 Ti 0.07 ) O 20 OH 1.97 F 2.04 2.35 Mg 3.18 Mn 0.11 Ti 0.18 ]	14.42%
	Muscovite 1 Madras	K 1.72 Na 0.19 [Al 3.84 Fe 3+ O 20 OH 4	0.13 Mg 0.04 ] (Si 6.1 Al 1.9 )	0.94%
	Lepidolite 2 Unknown K 2 [Al , Li] 3 (Si 6 Al 2 ) O 20 (OH , F) 4	< 0.02%

1: obtained from Ward's Natural Science Establishment: ref 46V1194 (biotite) and ref 46V5474 (muscovite) 2: unknown origin


Sébastien Ménigot

Anthony Novell

Ayache Bouakaz

Senior Member, IEEE Jean-Marc Girault

Improvement of the power response in contrast imaging with transmit frequency optimization

Keywords: Adaptive imaging, contrast agent, optimization

Conventionnal ultrasound contrast imaging systems use a fixed transmit frequency. However it is known that the insonified medium (microbubbles) is time-varying and therefore an adapted time-varying excitation is expected. We suggest an adaptive imaging technique which selects the optimal transmit frequency that maximizes the contrast tissue ratio (CTR). Two algorithms have been proposed to find an US excitation for which the frequency has been optimal with microbubbles.

Simulations were carried out for encapsulated microbubbles of 2µm-radius by considering the modified Rayleigh-Plesset equation for a 2.25MHz transmitted frequency and for various pressure levels (20 kPa up to 420kPa). In vitro experiments have been carried out using a 2.25 MHz transducer and using a programmable waveform generator. Responses of a 1/2000 blood mimicking fluid-diluted solution of Sonovue TM were measured by a 3.5 MHz transducer.

We show through simulations that our adaptive imaging technique allows to reduce the transmit maximal pressure. As for in vitro experiments the CTR can reach 10 dB.

By proposing a close loop system whose frequency adapts itself with the perfused media, throughout the examination, the optimization system adapt itself to the remaining bubbles population thus allowing an increase of the 30% examination duration.

I. Introduction

U LTRASOUND (US) contrast imaging is being investi- gated for tissue function and for targeted therapeutic applications with microbubble ultrasound contrast agents (UCA). Currently technical challenge consists in seeking for an US excitations which should make possible the optimization of the contrast tissue ratio (CTR). This ratio (eqn. 1) can be maximized if the microbubbles backscattered power is maximized. The transmit signal is a factor E-mail : hrefmailto:sebastien.menigot@etu.univtours.frsebastien.menigot@etu.univ-tours.fr, jean-marc.girault@univ-tours.fr c 2009 IEEE. Reprinted, with permission, from Sébastien Ménigot, Anthony Novell, Ayache Bouakaz and Jean-Marc Girault, Improvement of the power response in contrast imaging with transmit frequency optimization, 2009 IEEE International Ultrasonics Symposium (IUS), 20-23 Sept. 2009. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the Université François Rabelais de Tours' products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. of the microbubbles backscattered power.

CT R = E bubbles E BMF (1)
with E bubbles the microbubbles backscattered power and E BMF the tissue backscattered power.

We tackled the problem in a simple way by proposing an adaptive imaging technique which seeks the transmit frequency that maximizes the backscattered power. The use of an adaptive technique is justified by the fact that: 1. during the clinical examination, the insonified medium perfused by the microbubbles is a non-stationary medium (the concentration and the size of bubbles change...) ; 2. the pressure level is unknown because of the diffraction and attenuation effects which vary from one patient to another ; 3. the size and the distribution of the UCA are not precisely known and can differ from one sample to another. To overcome these problems, that is to disregard these unknown factors, it seemed more judicious to propose an US excitation whose frequency is selected in an adaptive way.

II. Methods and materials

A. Methods

The optimization aims to maximize the power of the backscattered signal by an iterative method. The principle consists in measuring the backscattered power from the microbubbles, for a sinus wave excitation first ; secondly in seeking for the optimal transmit frequency by maximizing the backscattered power.

The sinus pulse has been modulated with a Gaussian window(fig. 1) [START_REF] Tranquart | Échographie de contraste, Méthodologie et applications cliniques[END_REF] to avoid the destruction of the microbubbles. The number of cycles has been fixed to 4, whereas the amplitude has been corrected so that the power level was the same for every frequency. Two algorithms have been chosen to find the frequency of the transmit signal which maximizes the backscattered power : the golden section search and the gradient ascent. This choice was obvious because the analytic expression of power according to frequency is unknown.

• Golden section search(GSS) [START_REF] Press | Numerical Recipes in C[END_REF]. This approach has been chosen because it does not need to compute the Emission signal with 4 cycles derivative of power. The first step consists in choosing two frequencies (f 1 and f 2 ) in the analyzed bandwidth and to compute respectively their powers (E 1 and E 2 ). A third frequency f 3 is deduced such as the intervals where the power is maximal, is reduced. In the next iteration, from a reduced intervals, a new frequency f 3 is computed to approach the optimal frequency.

• Gradient ascent(GA) [START_REF] Widrow | Adaptive Signal Processing (Prentice-Hall Signal Processing Series[END_REF]. This one maximizes power with a recurrence relation.

f k+1 = f k + α k • ∇E(f k ) (2)
The gradient is estimated with the discrete gradient. This ratio is nearly null for small power in comparison with the frequency and thus the parameters were normalized.

∇E(f k ) = E k -E k-1 f k -f k-1 (3)
For every sign change of two successive gradients, α k is divided by two.

B. Materials

B.1 Microbubbles

The ultrasound contrast medium was composed of Sonovue TM microbubbles. The mean diameter is 4.5 µm [START_REF] Vos | Acoustical investigation of freely moving single microbubbles[END_REF] and the shell thickness d Se is 1 nm [START_REF] Chetty | P1f-4 high speed optical observations and simulation results of lipid based microbubbles at low insonation pressures[END_REF]. As for the mechanical shell properties, the shear modulus G s is 46 MPa [START_REF] Vos | Method for microbubble characterization using primary radiation force[END_REF] and the shear viscosity is 1 Pa•s.

B.2 Numerical simulations

Numerical simulations for encapsulated contrast bubbles were resolved, using Bubblesim [START_REF] Hoff | Acoustic Characterization of Contrast Agents for Medical Ultrasound Imaging[END_REF], from the modified Rayleigh-Plesset equation. The Sonovue TM properties were used for the microbubbles parameters.

The microbubble echo was computed from only one microbubble immersed in blood. The blood density is 1025 kg•m -3 and the velocity of sound in blood is 1570 m•s -1 .

The transducers effects have been considered. Each transmit and received signals were filtered by the bandwidth of the transmit and the received transducers respectively.

B.3 Acoustical Measurements

Each method was compiled using Matlab R (Mathworks, Natick, MA). The resulting excitation signal was transmitted through a GPIB port (National Instruments, Austin, TX) to an arbitrary function generator (33220A, Agilent, Palo Alto, CA). The signal was then amplified using a power amplifier (Amplifier Research 150A100B, Souderton, PA) and transmitted to a 2.25 MHz PZT single element (Sofranel, Sartrouville, France) focused at 55 mm and with a bandwidth of 74% (fig. 2).

Bandwidth of transducers

Responses of a 1/2000 diluted solution of Sonovue TM microbubbles (Bracco Research, Geneva, Switzerland) were measured by a 3.5 MHz PZT single element transducer with a bandwidth of 63% (fig. 2) also focused at 55 mm and used in receive mode.

The first transducer was used to transmit the signal, whereas the second wich was placed perpendicularly was used to receive the microbubbles echo. This position avoided direct transmission .

Measured echoes were amplified by 30 dB (Pulser-Receivers 5072R, Olympus Panametrics, Waltham, MA, USA) and then visualized on a digital oscilloscope (Tektronix, Beaverton, OR). Signals were transferred to a personal computer through a GPIB port for further analysis. Finally, each signals were compensated by received transducer bandwidth.

The backscattered power was computed from a linear combination of twenty signals, to cancel out the motion of microbubbles. For each iterations, twenty pulses were transmitted and twenty signals were received. With a principal component analysis (PCA), a new received signal which allows to deduce the backscattered power, is computed.

To deduce the contrast tissue ratio (CTR), the microbubbles were injected in a blood mimicking fluid(BMF) "'EU-DFS-BMF-ver.1.2"' (Dansk Fantom Service, Jyllinge, Denmark). For each frequency, the BMF received power (without microbubbles) was determined.

III. Results

A. Simulations

To know the evolution power according to the frequency, a microbubble has been stimulated with 4 cycles and the backscattered signal has been computed for different pressures. The frequency which allows to obtain a maximum power varies with the pressure: for a high pressure, the frequency is lower (fig 3). From the appearance of power, the initial frequencies for the algorithms have been chosen to find the global maximum.

The two methods were applied with three signals of 127, 244 and 370 kPa maximal pressure. Golden section search for a 2-microns microbubble

The backscattered power was stable and maximize after twenty iterations. For each pressure, the optimal frequency is different(2 MHz, 1.6 MHz and 1.39 MHz respectively for 127, 244 and 370 kPa), which was shown by the power according to the frequency.

For a backscattered power, the maximal pressure could be reduced with an optimal frequency III-A. When the signal was transmitted with a 244 kPa pressure (respectively Pressure for the optimal (Golden section search -GSS and Gradient Ascent -GA) and the transducer central frequencies (Without optimization -WO) with the same backscattered power in simulation 370 kPa) and with the 2.25 MHz transducer central frequency, the maximal pressure could be reduced to 22 kPa (respectively 65 kPa) with the same backscattered power.

B. Experiments

A cloud of microbubbles immersed in BMF has been stimulated with two different pressures (244 and 370 kPa). Pressure for the optimal (Golden section search -GSS and Gradient Ascent -GA) and the transducer central frequencies (Without optimization -WO) with the same backscattered power in vitro, loss power (LP) and duration examination gain (DEG) with optimization compared with the case without optimization

Experiment with gradient ascent

The optimal frequency is different according to the pressure(1.4 MHz and 1.2 MHz respectively for 244 and 370 kPa).

The CTR can reach 10 dB and in average 5 dB. For a backscattered power, the maximal pressure could be reduced with an optimal frequency. The reductions are similar to these obtained in simulation. The loss power (LO) was less important when the maximal pressure is reduced (tab II). If a minimal power threshold is fixed, the optimization could increase the duration examination compared with the case without optimization.

IV. Discussions

These optimization methods of backscattered signals need power according to the frequency to follow a convex curve on the interval in which maximum power is sought. If the interval includes one or several local maxima, the optimization could not find the global maximum and another optimization technique should be found. In case of microbubbles, a local maximum appears for the high pres-sures in simulation. However, all cases have a convex curve and for the hight pressure, the local maximum is near to the global maximum which allows to find it.

The optimal frequencies depend on the transmitted pressure. The backscattered power according to the frequency shows that the maximal power shifts forward the low frequency when the pressure increases. The simulations and the experiments optimal frequencies for the highest pressure are lower than these ones for the lowest pressure. The optimal frequencies obtained in simulation are near to these obtained in experiments.

The CTR is optimized with the maximization of backscattered power. The simulation does not allow to know a CTR, because the blood signal is unknown.

By proposing a close loop system whose frequency adapts itself with the perfused media, throughout the examination, the optimization system adapts itself to the remaining bubbles population thus allowing an increase of the 37% examination duration. The optimization allows to reduce the maximal pressure. The pression is a factor of the destruction of the microbubbles. With the same power detection level, the examination duration is extended. The GA seems to be more effective than GSS. Indeed, the maximal power search is not limited in an intervals like with GSS.

The experimental results are not exactly identical because of the non-stationarity of microbubbles. To cancel their motion, we have repeated the experiment. But a high number of repetition and a high value of iterations number could destroy the microbubbles and thus the power could decrease. A trade-off must be found to avoid the destruction of the microbubbles.

V. Conclusion

The optimization allows to maximize the backscattered power and thus to maximize the CTR. These methods allow to find the optimal frequency adapted to microbubbles. However, these results could be improved if the tissue backscattered power was minimized.

The optimal frequency according to the examination duration could allow an extension duration examination with the decrease of maximal pressure.

We can carry on complicating the optimization, firstly by finding the optimal frequency and the optimal amplitude simultaneously.

VI. Acknowlegdement

This work was supported by Agence Nationale de la Recherche (Project ANR 07, Tecsan 015, MONitoring response to THERapy with a novel ultrasound technology).

  Fig.1

Fig. 2

 2 Fig.2

Fig. 3

 3 Fig. 3Power according to the frequency for a 2-microns microbubble

  Fig.4

Fig. 5

 5 Fig. 5Gradient ascent for a 2-microns microbubble

Fig. 6

 6 Fig. 6Experiment with golden section search

  Fig. 7

TABLE I

 I

TABLE II

 II