M Toutain

X Desquesnes

A Elmoataz

O Lézoray

A Unified Geometric Model For Virtual Slide Images Processing

In this paper, we propose a unified framework to address the problem of cytological computeraided diagnosis. Such an approach relies on our previously introduced formalisms: general formulation of discrete functional regularization, PDEs based morphology and geometric diffusion on graphs. The approach is illustrated through two applications in cytopathology, with examples of nucleus extraction and classification.

INTRODUCTION

Traditionally, cytopathologists take a diagnostic decision by studying morphological and texture features of cellular components (cytoplasm and nuclei), seen through a microscope. This is a complex process as a cytological slide can contains millions of cells on which abnormal cells (affected by a cancer) are often very rare or fortunately absent. During the last decade, the advent of fast and efficient high-resolution slide scanners along with the development of computer vision has opened the way to using digital pathology as a diagnosis tool. However, computeraided diagnosis involves many tasks, from the acquisition of the cytological slide to the final classification of each cell. Indeed, the digital image can be preprocessed for enhancement, and analyzed to extract cellular objects. The extracted objects might also be preprocessed, and analyzed to extract some features in order to perform a classification. In this work, we use our recently proposed framework of partial difference equations (PdEs) based morphology on graphs to address the problem of cytological computer-aided diagnostic through different subproblems: image preprocessing, cell extraction and cell classification. The rest of this paper is organized as follows.

In Section 2, we introduce the microscopic imaging problems and propose a strategy to address them. In Section 3, we provide definitions and notations on graphs that will be used in the next sections. Sections 4, 5, and 6 present the different steps of our methodology for processing virtual slide images. Section 7 concludes this paper.

MICROSCOPIC IMAGING PROBLEMS

In this section, we briefly introduce pathology and virtual slide images, in order to propose our approach to process such data.

This work was supported under a doctoral grant of the Conseil Régional de Basse Normandie and of the Coeur et Cancer association in collaboration with the Department of Anatomical and Cytological Pathology from Cotentin Hospital Center.

Modeling

Pathology is roughly composed of two sections: cytology and histology. For both these sections, the visual inspection of cellular specimens and histological sections through a light microscope plays an important role in clinical medicine and biomedical research. Cytology literally means the study of cells. It studies morphological features of human body fluid cells which are put on a glass slide and stained. The study of the modification of the main cellular components (nucleus and cytoplasm) is the fundament of the cytological study. The morphological features of cells are visually evaluated by cytotechnologists and cytopathologists and these features involve several notions including size, shape, color, texture and topography. The interaction between nucleus and cytoplasm is also of interest: the position of the nucleus in the cytoplasm, the nucleus-cytoplasm area ratio, the position of nucleols in the nucleus, the color and the granularity of the cytoplasm.

Virtual slide images

In this paper we focus on virtual slide images of cytological slides stained with Feulgen and Papanicolaou coloration. Virtual slides are digitized images of slides. A Leica SCN 400 digital microscopical scanner is used to completely digitize our slides at 40× magnification scale. The resulting images are compressed with a quality of 75% in JPEG compression format. To facilitate the visualization and the processing, scanned samples acquired by the scanner are directly stored as an irregular pyramid where each level of the pyramid is an underresolved version of the highest resolution image (the pyramid base). The images being very large (about 80000 × 80000 at the highest resolution), each resolution level is split into image tiles (of size 512 × 512) in a nonoverlapping layout. The usual size of a compressed slide image is about 2 Gygabytes.

Image object oriented modeling As discussed above, image processing methods are of high interest to provide Image Decision Guided Systems (IDGS) to perform prognostic, diagnostic and early detection of cancer. For the case of problems in pathology, image processing can be used for several tasks: quantification of cellular content (DNA, proteins, color), recognition and sorting of cellular types, extraction of cellular groupings or clusters and of their topographic relations. In terms of image processing problems, the objectives concern segmenting or analyzing objects at different levels: cellular or cellular grouping level. Cytological images have common properties and can be described by an image object-oriented modeling. First of all, the images have to be acquired in color. This is essential to follow the exact visual way the pathologists evaluate microscopic images. For a microscopic image, one can always divide it into two parts: the background and the rest of the image, namely the objects to be extracted. The background is always close to a given color and is usually homogeneous even if some debris or artifacts can occur (some mucus for instance). The rest of the image is composed of the elements of interest for the pathologists. In this work, we use an image object-oriented modeling of the elements of an image: they can be classified and characterized in terms of size, shape, color and texture. Before trying to conceive any image segmentation technique, a pool of representative images has to be built to have a model of the problem which is as close as possible to reality. Once this database has been constructed, a segmentation strategy can be conceived. Our approach for processing cytological virtual slide images is illustrated in fig. 1. First step is the simplification of images that directly come from the slide's images at the highest resolution. Simplification can be seen as a pre-processing step, in order to ease the second step : segmentation. Here we separate nuclei from anything else in the slide. Once segmentation is done, we have detected all the nuclei in the slide image. The last step of our strategy (classification) is first to extract features of the segmented nuclei, then to classify these nuclei, according to their feature vector. Simplification, segmentation, and classification are performed with partial differential equations (PDEs) on graphs.

Our proposed scheme

PRELIMINARIES ON GRAPHS AND NOTATIONS

As the core structure of our approach, in this section we provide notations and basics on weighted graphs. We recall our formulations of differences, morphological differences and gradients on weighted graphs [START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF], ?]).

Notations : We assume that any discrete domain can be modeled by a weighted graph. Let G = (V, E, w) be a weighted graph composed of two finite sets: V = {u 1 , ..., u n } of n vertices and E ⊂ V × V a set of weighted edges. The weight function w : V × V → [0, 1] represents a similarity measure between two vertices of G. According to w, the set of edges is defined as:

E = {(u, v)|w(u, v) = 0}.
We denote by N (u) the neighborhood of a vertex u, i.e., the subset of vertices that share an edge with u, and the notation v ∼ u means that v ∈ N (u). In this paper, graphs are assumed to be connected, undirected and with no self loops. We denote by H(V ) and H(E) the Hilbert spaces of functions that assign a real value to each vertex, respectively edge, of G. Let us consider A, a subset of V . The outer and inner boundary sets of A are respectively denoted

∂ + A and ∂ -A, with ∂ + A = {u ∈ A c |∃v ∈ A, v ∼ u} and ∂ -A = {u ∈ A|∃v ∈ A c , v ∼ u} where A c is the complement of A.
Operators on Weighted Graphs: Given a weighted graph G = (V, E, w) and a function f ∈ H(V ), the weighted gradient operator or weighted difference operator, noted G w :

H(V ) → H(E) is defined on an edge (u, v) ∈ E by (G w f )(u, v) def = w(u, v)(f (v) -f (u))
(1) Based on the weighted gradient operator definition, two weighted directional gradient operators are defined. The weighted directional external and internal gradient operators are defined as

G ± w : H(V ) → H(E), by (G ± w f )(u, v) def = w(u, v)(f (v) -f (u)) ±
(2) with the following notations: (x) + = max(x, 0) and (x) -= -min(x, 0). The weighted gradient of a function f ∈ H(V ) at vertex u is defined as the vector of all weighted gradients with respect to the set of edges (u, v) ∈ E

(∇ w f )(u) def = ((G w f )(u, v)) v∈V .
(3) This operator corresponds to the local variation of the function f at the vertex u and measures the regularity of f in the adjacent neighborhood N (u). Hence the L 2 -norm of the weighted gradient operator is

||(∇ w f )(u)|| 2 = v∼u w uv (f (v) -f (u)) 2 1/2 . ( 4
)
In the sequel, the weighted gradient will refer to this gradient defined on vertices. Similarly, the weighted morphological internal and external gradients at a vertex u are expressed as

(∇ ± w f )(u) = ((G ± w f )(u, v)) v∈V (5) with the following L p (p ∈ {1, 2}) and L ∞ norms ||(∇ ± w f )(u)|| p = v∼u w p/2 uv |(f (v) -f (u)) ± | p 1/p , ||(∇ ± w f )(u)|| ∞ = max v∼u ( √ w uv |(f (v) -f (u)) ± |). (6)

IMAGE SIMPLIFICATION / FILTERING

As described in the previous section, our proposed scheme to address the problem of processing virtual slide images is to separate it into the three following problems: preprocessing, cell extraction, and classification, all under our graph based framework. In this section, we focus on the preprocesing step. While working on very large data (such as virtual slides), many algorithms become inefficient due to the mass of data to process, and the variability of the data. A simple and efficient way to avoid this problem is to work on a simplified version of the data. In this paper, we consider cytology slide images, with Feulgen and Papanicolaou coloration. Feulgen coloration is quite computer-vision-friendly, because the slide can be seen as a set of two easily separable classes: the background (in grey) and the nucleus (in pink). Papanicolaou coloration is the most used in cytology, and stains cytoplasms in light green and nuclei in dark blue. However, the nuclei boundaries are often unsharp due to refractiveness or mucus artifacts standing around the nucleus. In order to ease the segmentation step, we use filtering as a preprocessing step for this kind of coloration.

Simplification of the images

In image processing, the graph data-structure is commonly used to represent a digital image. For our filtering process, we use a grid graph, which is a natural structure corresponding to the definition of digital images: vertices represent pixels and edges represent pixel adjacency relationship. From the previous definitions, we introduce here the weighted p-Laplace operator ∆ p w f (u) at vertex u :

∆ p w f (u) = v∼u γ(u, v)(f (v) -f (u)), (7)
where

γ(u, v) = w(u, v)(||(∇ w f )(u)|| p-2 2 + ||(∇ w f )(v)|| p-2 2
). (8) In the case where p = 1 and 2, we have the definitions of the standard graph curvature ∆ 1 w f (u) = κf and graph Laplace ∆ 2 w f (u) = ∆f operators. More details on these definitions can be found in [START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF].

Discrete regularization framework To regularize a function f 0 ∈ H(V ) using the p-Laplace operator (7), we consider the following general variational problem on graphs:

min f ∈H(V ) {E w,p (f, f 0 , λ) = R w,p (f ) + λ 2 ||f -f 0 || 2 }. (9)
The intuition behind regularization is to provide a smoother version of an initial function f 0 (with the regularizer term) while keeping it close to the initial function (with the fitting term). The first term, R w,p (f ), is the regularizer and is defined as the discrete Dirichlet form of the function

f ∈ H(V ) : R w,p (f ) = 1 2 u∈V ||∇ w f (u)|| p 2 .
The second term is the fitting term. λ ≥ 0 is a fidelity parameter called the Lagrange multiplier which specifies the trade-off between the two competing terms. Both terms of E w,p (f, f 0 , λ) in ( 9) are strictly convex function of f [START_REF] Chan | The digital tv filter and nonlinear denoising[END_REF]). By a standard argument in convex analysis, this optimization problem has a unique solution for p = 1 and 2 which satisfies, for all u ∈ V :

∂ ∂f (u) E w,p (f, f 0 , λ) = ∆ p w f (u) + λ(f (u) -f 0 (u)) = 0. ( 10
)
Equation ( 10) can be viewed as the discrete analogue of the Euler-Lagrange equation. Using the p-Laplacian formulation (equation. ( 7)) in equation ( 10), the optimization problem solution is also the solution of the following system of equations. For all u ∈ V ,

λ + v∼u γ(u, v) f (u) - v∼u γ(u, v)f (v) = λf 0 (u). ( 11
)
To approximate the solution of the minization (9), we can linearize this system of equations and use the Gauss-Jacobi method to obtain the following iterative algorithm:

   f (0) (u) = f 0 (u), f (t+1) (u) = λf 0 (u) + v∼u γ (t) (u, v)f (t) (v) λ + v∼u γ (t) (u, v) . ( 12
)
where γ (t) (u, v) is the γ function (in equation ( 8)) at the iteration step t. At each iteration of the algorithm, the value of f at step (t + 1), for a vertex u, only depends on two quantities: the original value f 0 and the sum of the weighted existing values f (t) in the neighborhood of u. By using different formulations of w and different values of p, a family of linear and nonlinear filters is obtained. Indeed, when p = 2 and w(u, v) = 1 one obtains the linear diffusion on graphs. When p = 1 and w(u, v) = 1 one recovers the TV digital filter [START_REF] Chan | The digital tv filter and nonlinear denoising[END_REF]). The reader can note that this isotropic regularization corresponds to the weighted discrete transcription of the regularization functional in the continuous case. The interested reader can refer to [START_REF] Elmoataz | Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing[END_REF] for more details on the formulation and the connections with other formalisms.

Image filtering Through the values of the p parameter, the discrete regularization (10) describes a family of linear and nonlinear filters. This image filtering/denoising can be viewed as an image simplification that can ease the seed extraction step. Before processing acquired cytological whole slide, they are split into thousands (it varies, depending on the size of the acquired virtual slide) of 1024 × 1024 tiled images. All images presented in this paper are very small details extracted from some of the processed tiled images and obviously can not represent the hugeness of digital slides. , with d(u, v) the Minkowski distance of order 2 in the RGB color space, on a Feulgen cytological image represented by an 8-adjacency grid-graph, i.e., a graph that connects a pixel to its neighbors in a 3 × 3 spatial window centered on the pixel. During regularization, each color channel is processed separately. Fig. 2(c) and 2(d) show a filtered version of the v * channel of the CIELUV color space (see [START_REF] Ohta | Colorimetry: fundamentals and applications[END_REF] for details on color spaces) of a Papanicolaou stained image (v * caracterising a bluegreen opposition, and being the most discriminant to extract nuclei for Papanicolaou staining), with p = 2 and w(u, v) = e

-(f (v)-f (u)) 2 σ 2 e - (xv -xu ) 2 2σ 2 s + (yv -yu ) 2 2σ 2 s
, with (x u , y u ) and (x v , y v ) the corresponding spatial coordinates in the image of, respectively, u and v. In this case, we construct a grid graph with edge connections in a spatial square window of width related to σ s . One can note that this last weighting function permits to recover a bilateral filter [START_REF] Tomasi | Bilateral filtering for gray and color images[END_REF]).

IMAGE SEGMENTATION

In this section we focus on the cell extraction step of our strategy. To extract cells, we perform a segmentation of the simplified images obtained from the pre-processing step. As the algorithm we detail in this section performs a label propagation, we first extract seeds from the simplified images that will be used as initial labels to propagate. We first provide details and recalls on PdEs based morphology to introduce our methods, which is also based on the previous definitions provided on graphs and operators on graphs. We then make a link with the static version of the eikonal equation (for further details, see [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF]), and show the use of front propagation for initial label propagation. Results are shown in the last part of this section.

Eikonal equation on weighted graph

PdEs based Morphology Discrete dilation and erosion on weighted graphs are defined by

∂ t f (u) = +||(∇ + w f )(u)|| p and ∂ t f (u) = -||(∇ - w f )(u)|| p , (13
) respectively. These equations ( 13) constitute a PdEs based framework [START_REF] Ta | Nonlocal pdesbased morphology on weighted graphs for image and data processing[END_REF]) that extends algebraic and continuous morphological operators to graphs. Such a framework has been involved in the transcription of geometric PDEs from continuous domains, to graphs of arbitrary topology. To solve these dilation and erosion process (equations 13), we use the iterative scheme proposed in [START_REF] Ta | Nonlocal pdesbased morphology on weighted graphs for image and data processing[END_REF]. For the dilation : f t+1 (u) = f t (u) + ||(∇ + w f t )(u)|| p , and for the erosion :

f t+1 (u) = f t (u) - ||(∇ - w f t )(u)|| p .
Indeed, given, a set of vertices A ⊂ V and using external and internal graph boundaries, the equation of dilation over A can be intuitively interpreted as a growth process that adds vertices from ∂ + A to A. By duality, erosion over A can be interpreted as a contraction process that removes vertices from ∂ -A. Let Γ be a parametrized curve evolving on a domain Ω. A very common way to describe the evolution of Γ, popularized by [START_REF] Sethian | Level set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision[END_REF], is to embed the curve in a function φ(x, t) such that the evolving curve Γ t can be provided by the 0-level set of φ. Once formulated as a level set problem, the curve evolution amounts to solving the following equation:

∂φ ∂t = F|∇φ|. (14)
In [START_REF] Desquesnes | Pdes level sets on weighted graphs[END_REF], a transcription of ( 14) has been proposed to weighted graphs, that can be expressed as a morphological process with the following sum of dilation and erosion.

∂φ ∂t (u) = F + ||(∇ + w φ)(u)|| + F -||(∇ - w φ)(u)||, (15)
where F ∈ H(V ) controls the front propagation. Such a formulation enables recovery of geometric diffusion models such as mean curvature motion, active contours, or a graph based transcription of the eikonal equation. The eikonal equation is also a very popular equation in computer graphics and computer vision which is involved in many applications. Numerous methods have been proposed to solve it on Cartesian grids and some particular non-Cartesian domains (see [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF] and references therein). Recently, two adaptations of the eikonal equation have been proposed, first as a time dependent version [START_REF] Ta | Nonlocal pdesbased morphology on weighted graphs for image and data processing[END_REF]), then as a static version [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF]) which is expressed as

||(∇ - w f )(u)|| p = P (u), ∀u ∈ V, f (u) = 0, ∀u ∈ V 0 , (16)
where V 0 ⊂ V corresponds to the initial set of seeds vertices, and P a potential. Such adaptations are expressed using the PdEs based morphological erosion, and can be linked with the general geometric PdE equation (15). In [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF], a label propagation algorithm has been proposed based on the resolution of ( 16), that enables the propagation of many labels on a graph. The propagation is performed from a set of seeded vertices and until all vertices of the graph are marked with a label. This algorithm enables many applications on graphs, such as geodesic distance computation on graphs, image segmentation and data clustering.

Nuclei extraction by label propagation

Seeds extraction In [START_REF] Desquesnes | Pdes-based morphology on graphs for cytological slides segmentation and clustering[END_REF], a method is proposed to automatically extract seeds from the simplified Feulgen image resulting from the preprocessing step.

As we can see in fig. 2, the background is homogeneous and can be automatically and roughly detected as the biggest region of similar pixels (in the sense of color variance). Such pixels become the seeds of the background label (see fig. 3(a)). For Papanicolaou stained images, an H-minima method (see [START_REF] Soille | Morphological image analysis: principles and applications[END_REF] for details on H-minima) is used on the simplified version to automatically get seeds from the nuclei. Considering the set S of nuclei seeds, an erosion is performed on S c to get non-nuclei seeds that do not overlap potential nuclei (see fig.

Label propagation

Once background seeds have been extracted, they are propagated on the image grid-graph until being stopped by nuclei boundaries. Using equation ( 6) and equation ( 16), we get for p = +∞:

v∼u w p/2 uv max(0, (f (u) -f (v))) p = P (u), p ∈ {1, 2}, (17)
and for p = +∞:

max v∼u ( √ w uv max(0, f (u) -f (v))) = P (u), p = ∞. (18)
For the sake of clarity, we only present here the solution for the L ∞ norm formulation (18):

x = n min j=1 (a j + h j C), (19)
where x = f (u), n = card(N (u)), a i = {f (v i )|v i ∈ N (u) with i = 1, ..., n}, h j = 1/ √ w uv , and C = P (u).

Further details on the front propagation algorithm can be found in [START_REF] Desquesnes | Eikonal equation adaptation on weighted graphs: fast geometric diffusion process for local and non-local image and data processing[END_REF]. The stopping criterion is held by the potential P of equation ( 16), as

P (u) = 1/((µ N -f (u)) 2 -(µ B -f (u)) 2 + K(u)), (20)
where µ N and µ B are respectively the mean color of nuclei and background, K is the graph-curvature term that constrains the label evolution to produce smooth regions.

The global solution (over the entire graph) is computed in a simple way: let N B be a narrow band of vertices to update (where the distance has to be computed), A a list of already updated vertices, and F A a set of vertices which are not in one of these sets. The algorithm is initialized as follows: the initial seeds set (V 0 ) is added to A, vertices on the outside boundary of A are added to N B, and the remaining vertices compose F A. The computed distance at a vertex u is indeed the distance to the nearest seed from u (with respect to the graph topology, the weighting function w, and the potential P ). So the front arriving at a vertex u is necessarily coming from the nearest seed of u, and it becomes easy to associate the right label with it, looking at the labels of the neighbors of u (at least one being marked by the front already passed). The labeling process can be summarized by the following formula: each time f (u) is updated, the label L(u) is given by

L(u) = L(v)|v ∈ N (u), f (v) < f (u) and f (v) wuv = min z∼u ( f (z) wuz ). ( 21
)
The results of this segmentation scheme are illustrated in fig. 3

OBJECT CLASSIFICATION / CLUSTERING

In this section, we show that data classification problems can be addressed using the same framework as in the previous sections. Examples on Feulgen stained cytological images will be used to illustrate our method.

As said previously, the last step of our scheme is to classify nuclei extracted from the segmentation step, to determine if some are abnormal. This is a data classification problem, into two (or more) classes: the data to classify is the set of nuclei, and typical classes are normal and abnormal.

Characteristics extraction

To begin with, we have to represent nuclei as data to classify. From the segmentation process, we first compute characteristics on each extracted nucleus (area, compacity, ...), which form a feature vector describing each nucleus.

Classification

The classification problem can finally be seen as a semisupervised graph clustering problem, where the data is represented as a k-nearest-neighbor graph (each feature vector is represented by a vertex which is connected to its k most similar vertices in the whole graph, according to a similarity function). The clustering is performed using the previously seen label-propagation algorithm on graphs, with a label per class. Label seeds are given by a reference data set (where the class of each nucleus is known), the entries of which are added to the graph. Such a clustering method is illustrated in fig. 4 with a 4-labels semisupervised graph clustering example. Using graph based label propagation for clustering the set of nuclei has two main advantages. First there is no classifier training, and modifying the reference data set does not imply to retrain a classifier (as it is the case while using neural networks for example). Second, graphs intrinsically provide a representation of the organization of the different classes and the position of each nucleus in each class. Such information can be of crucial importance for cytopathologists in the case of ambiguous cells.

CONCLUSION

In this paper, we proposed a graph based approach using a general formulation of discrete functional regularization, PDEs based morphology and geometric diffusion on weighted graphs of arbitrary topology to address the problem of cytological computer-aided diagnosis. The approach is very general and has been illustrated both on Papanicolaou and Feulgen stained slides. In both cases, the proposed unified methodology has given very good and promising results.

  Fig. 1. System overview.

Fig

Fig. 2 .

 2 Fig. 2. Examples of cytological image pre-processing.(a) initial Feulgen stained image. (b) Preprocessed image using discrete regularization framework. (c) initial Papanicolaou stained image (gynecology). (d) Filtered version of v * channel of CIELUV color space of the initial image.

  3(c) for illustration).

Fig. 3 .

 3 Fig. 3. Feulgen nuclei extraction : (a) Initial labels (in blue) computed on Feulgen stained simplified image. (b) extracted nuclei. (c) Eroded background seeds (in red) and initial nuclei seeds (other colors but black) computed on Papanicolaou stained simplified image. (d) extracted nuclei.

  (b) for Feulgen images and fig. 3(d) for Papanicolaou images. It has been evaluated on a hundred images by a cytopathologist (per nuclei visual assessment) and 98% of the nuclei are extracted and correctly delineated.


Claire-Hélène Demarty
email: claire-helene.demarty@technicolor.com

Cédric Penet
email: cedric.penet@technicolor.com

Markus Schedl
email: markus.schedl@jku.at

Bogdan Ionescu
email: bionescu@imag.pub.ro

Vu Lam Quang
email: lamquangvu@gmail.com

Yu-Gang Jiang
email: yugang.jiang@gmail.com

The MediaEval 2013 Affect Task: Violent Scenes Detection *

This paper provides a description of the MediaEval 2013 Affect Task Violent Scenes Detection. This task, which is proposed for the third year to the research community, derives directly from a Technicolor use case which aims at easing a user's selection process from a movie database. This task will therefore apply to movie content. We provide some insight into the Technicolor use case, before giving details on the task itself, which has seen some changes in 2013. Dataset, annotations, and evaluation criteria as well as the required and optional runs are described.

INTRODUCTION

The Affect Task Violent Scenes Detection is part of the Me-diaEval 2013 benchmarking initiative for multimedia evaluation. The objective is to automatically detect violent segments in movies. This challenge is proposed for the third year in the MediaEval benchmark. It derives from a use case at Technicolor (http://www.technicolor.com), which involves helping users choose movies that are suitable for children in their family. The movies should be suitable in terms of their violent content, e.g., for viewing by users' families. Users select or reject movies by previewing parts of the movies (i.e., scenes or segments) that include the most violent moments. In the literature, the detection of violence was not a lot studied [START_REF] Penet | Multimodal Information Fusion and Temporal Integration for Violence Detection in Movies[END_REF][START_REF] Ionescu | A naive mid-level concept-based fusion approach to violence detection in hollywood movies[END_REF][START_REF] Souza | Violence detection in video using spatio-temporal features[END_REF], until recently when it has gained interest. As most of the proposed methods suffer from a lack of a common and consistent database, and usually use a limited developement set, the task was launched to propose a public and common framework for the research community. This year, among other changes, two definitions of violence will be studied, an objective one and a subjective one (see below). The addition of a subjective definition was motivated by the fact that the one from 2012 has proven to lead to annotations which do not correspond to the use case.

TASK DESCRIPTION

The task requires participants to deploy multimodal features to automatically detect portions of movies containing violent material. For 2013, two definitions of violence are studied.

The first one corresponds to the one used in previous years and was chosen to be as objective as possible. This first definition is the following: violence is defined as "physical violence or accident resulting in human injury or pain". In an attempt to better fit the use case, a second definition is proposed, according to which events of interest are "those which one would not let an 8 years old child see, because they contain physical violence". This year, contrary to the previous challenges, the different runs will alternatively allow the participants to use either only features extracted from the provided DVD, or to use also additional external data (e.g., extracted from the web).

DATA DESCRIPTION

With respect to the use case, the dataset selected for the developed corpus is a set of 25 Hollywood movies that must be purchased as DVDs by the participants. The movies are of different genres and show different amounts of violence (from extremely violent movies to movies without violence). The content extractable from DVDs consists of information from different modalities, namely, visual information, audio signals and subtitles, and any additional metadata present in the DVDs. From these 25 movies, 18 are dedicated to the training process: Armageddon, Billy Elliot, Eragon, Harry Potter 5, I am Legend, Leon, Midnight Express, Pirates of the Caribbean 1, Reservoir Dogs, Saving Private Ryan, The Sixth Sense, the Wicker Man, Kill Bill 1, The Bourne Identity, the Wizard of Oz, Dead Poets Society, Fight Club and Independance Day. The remaining 7 movies, Fantastic Four, Fargo, Forrest Gump, Legally Blond, Pulp Fiction, The God Father 1 and The Pianist, will serve as the evaluation set. As in 2011 and 2012, we tried to respect the genre repartition (from extremely violent to non violent) both in the training and evaluation sets.

GROUND TRUTH

The ground truth 1 was created by several human assessors. In addition to segments containing physical violence (with the two above definitions), annotations also include highlevel concepts for the visual and the audio modalities. Each annotated violent segment contains only one action, whenever it is possible. In the cases where different actions are overlapping, the whole segment is proposed with different actions. This was indicated in the annotation files by adding the tag "multiple action scene". Each violent segment is annotated at frame level, i.e., it is defined by its starting and ending video frame numbers.

Seven visual and three audio concepts are provided: presence of blood, fights, presence of fire, presence of guns, presence of cold weapons, car chases and gory scenes (for the video modality); presence of screams, gunshots and explosions (for the audio modality). Participants should note that they are welcome to carry out detection of the high-level concepts themselves. However, concept detection is not the goal of the task and these high-level concept annotations are only provided for training purposes and only on the training set. For the video concepts, each of them follows the same annotation format as for violent segments, i.e., starting and ending frame numbers and possibly some additional tags. Regarding blood annotations, a proportion of the amount of blood in each segment is provided by the following tags: unnoticeable, low, medium and high. Four different types of fights are annotated: only two people fighting, a small group of people (roughly less than 10), large group of people (more than 10), distant attack (i.e., no real fight but somebody is shot or attacked at distance). As for the presence of fire, anything from big fires and explosions to fire coming out of a gun while shooting, a candle, a cigarette lighter, a cigarette, or sparks was annotated, e.g., a space shuttle taking off also generates fire and thus receives a fire label. An additional tag may indicate special colors of the fire (i.e., not yellow or orange). If a segment of video showed the presence of firearms (or cold weapons) it was annotated by any type of (parts of) guns (or cold weapons) or assimilated arms. By "cold weapon", we mean any weapon that does not involve fire or explosions as a result from the use of gun powder or other explosive materials. Annotations of gory scenes are more delicate. In the present task, they are indicated by graphic images of bloodletting and/or tissue damage. This includes horror or war representations. As this is also a subjective and difficult notion to define, some additional segments showing really disgusting mutants or creatures are annotated as gore. In this case, additional tags describing the event/scene are added. For the audio concepts, each temporal segment is annotated with its starting and ending times in seconds, and an additional tag corresponding to the type of event, chosen from the list: nothing, gunshot, canon fire, scream, scream effort, explosion, multiple actions, multiple actions canon fire, multiple actions scream effort. Automatically generated shot boundaries with their corresponding key frames are also provided with each movie. Shot segmentation was carried out by Technicolor's software.

RUN DESCRIPTION

Participants can submit four types of runs: two of them are shot-classification runs and the others are segment-level runs. For the two shot-classification runs, participants are required to provide violent scene detection at the shot level, according to the provided shot boundaries. Each shot has to be classified as violent or non violent, with a confidence score. These two runs will differ in the data that can be used for the classification: for the first one, only the content of the movie extractable from the DVDs is allowed for feature extraction, whereas in the second one, additional external data (e.g., extracted from the web) can be used. For the two segment-level runs, participants are required to, independently of shot boundaries, provide violent segments for each test movie. Once again, confidence scores should be added for each segment. Similarly to the shot-level runs, the two segment-level runs differ from the type of data allowed for the classification: internal data from the DVDs only vs. internal data plus additional external data. In all cases, confidence scores are compulsory, as they will be used for the evaluation metric. They will also allow to plot detection error trade-off curves which should be of great interest to analyze and compare the different techniques. For both subtasks, i.e., both violence definitions, the required run will be the run at shot-level without external data.

As a first step towards a qualitative evaluation, participants are encouraged to present at the MediaEval workshop a video summary of the most violent scenes found by their algorithms. This will not be evaluated by the organizers this year, but it will serve as a first basis for future evolution of the task.

EVALUATION CRITERIA

As in 2012, the official evaluation metric will be the mean average precision at the N top ranked violent shots. Several performance measures will be used for diagnostic purposes (false alarm and miss detection rates, AED-precision and recall as defined in [START_REF] Temko | Acoustic Event Detection: SVM-Based System and Evaluation Setup in CLEAR'07[END_REF], the MediaEval cost, which is a function weighting false alarms (FA) and missed detections (MI), etc.). To avoid only evaluating systems at given operating points and enable full comparison of the pros and cons of each system, we will use detection error trade-off (DET) curves, plotting P fa as a function of P miss given a segmentation and a score for each segment, where the higher the score, the more likely the violence. P fa and P miss are respectively the FA and MI rates given the system's output and the reference annotation. In the shot classification, the FA and MI rates were calculated on a per shot basis while, in the segment level run, they were computed on a per unit of time basis, i.e., durations of both references and detected segments are compared. Note that in the segment level run, DET curves are possible only for systems returning a dense segmentation (a list of segments that spans the entire video). Segments not in the output list will be considered as non violent for all thresholds.

The annotations, shot detections and key frames for this task were made available by the Fudan University, the Vietnam University of Science, and Technicolor. Any publication using these data should acknowledge these institutions' contributions.

* This year, work has been supported, in part, by the Quaero Program http://www.quaero.org/.


M Novaga
email: novaga@dm.unipi.it

B Ruffini

Brunn-Minkowski inequality for the 1-Riesz capacity and level set convexity for the 1/2-Laplacian

Keywords: fractional Laplacian, Brunn-Minkowski inequality, level set convexity, Riesz capacity

We prove that that the 1-Riesz capacity satisfies a Brunn-Minkowski inequality, and that the capacitary function of the 1/2-Laplacian is level set convex.

Introduction

In this paper we consider the following problem    (-∆) s u = 0 on R N \ K u = 1 on K lim |x|→+∞ u(x) = 0 [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF] where N ≥ 2, s ∈ (0, N/2), and (-∆) s stands for the s-fractional Laplacian, defined as the unique pseudo-differential operator (-∆) s : S → L 2 (R N ), being S the Schwartz space of functions with fast decay to 0 at infinity, such that

F(-∆) s f = |ξ| 2s F(f )(ξ),
where F denotes the Fourier transform. We refer to the guide [START_REF] Di Nezza | Valdinoci Hitchhikers guide to the fractional Sobolev spaces[END_REF]Section 3] for more details on the subject. A quantity strictly related to Problem [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF] is the so-called Riesz potential energy of a set E, defined as

I α (E) = inf µ(E)=1 R N ×R N dµ(x) dµ(y) |x -y| N -α α ∈ (0, N ). ( 2
)
It is possible to prove (see [START_REF] Landkof | Foundations of Modern Potential Theory[END_REF]) that if E is a compact set, then the infimum in the definition of I α (E) is achieved by a Radon measure µ supported on the boundary of E if α ≤ N -2, and with support equal to the whole E if α ∈ (N -2, N ). If µ is the optimal measure for the set E, we define the Riesz potential of E as

v(x) = R N dµ(y) |x -y| N -α , (3)
so that

I α (E) = R N v(x)dµ(x).
It is not difficult to check (see [START_REF] Landkof | Foundations of Modern Potential Theory[END_REF][START_REF] Goldman | Existence and stability for a nonlocal isoperimetric model of charged liquid drops[END_REF]) that the potential v satisfies (-∆)

α 2 v = c(α, N ) µ,
where c(α, N ) is a positive constant, and that v = I α (E) on E. In particular, if s = α/2, then v K = v/I 2s (K) is the unique solution of Problem [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF]. Following [START_REF] Landkof | Foundations of Modern Potential Theory[END_REF], we define the α-Riesz capacity of a set E as

Cap α (E) := 1 I α (E) . (4)
We point out that this is not the only concept of capacity present in literature. Indeed, another one is given by the 2-capacity of a set E, defined by

C 2 (E) = min R N |∇ϕ| 2 : ϕ ∈ C 1 (R N , [0, 1]), ϕ ≥ χ E (5)
where χ A is the characteristic function of the set A. It is possible to prove that, if E is a compact set, then the minimum in ( 5) is achieved by a function u satisfying

   ∆u = 0 on R N \ E u = 1 on E lim |x|→+∞ u(x) = 0. (6)
It is worth stressing that the 2-capacity and the α-Riesz capacity share several properties, and coincide if α = 2. We refer the reader to [START_REF] Lieb | Loss: Analysis[END_REF]Chapter 8] for a discussion of this topic.

In a series of works (see for instance [START_REF] Caffarelli | Convexity of Solutions to Some Classical Variational Problems[END_REF][START_REF] Colesanti | Salani Quasi-concave Envelope of a Function and Convexity of Level Sets of Solutions to Elliptic Equations[END_REF][START_REF] Korevaar | Convexity of Level Sets for Solutions to Elliptic Ring Problems[END_REF] and the monography [START_REF] Kawohl | Rearrangements and Convexity of Level Sets in[END_REF]) it has been proved that the solutions of (6) are level set convex provided E is a convex body, that is, a compact convex set with non-empty interior. Moreover, in [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF] (and later in [START_REF] Colesanti | The Brunn-Minkowski inequality for p-capacity of convex bodies[END_REF] in a more general setting and in [START_REF] Colesanti | The BrunnMinkowski Inequality for the n-dimensional Logarithmic Capacity of Convex Bodies[END_REF] for the logarithmic capacity in 2 dimensions) it has been proved that the 2-capacity satisfies a suitable version of the Brunn-Minkowski inequality: given two convex bodies K 0 and K 1 in R N , for any λ ∈ [0, 1] it holds

C 2 (λK 1 + (1 -λ)K 0 ) 1 N-2 ≥ λ C 2 (K 1 ) 1 N-2 + (1 -λ) C 2 (K 0 ) 1 N-2 .
We refer to [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF][START_REF] Gardner | The Brunn-Minkowski inequality[END_REF] for a comprehensive survey on the Brunn-Minkowski inequality.

The main purpose of this paper is to show the analogous of these results in the fractional setting α = 1, that is, s = 1/2 in Problem [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF]. More precisely, we shall prove the following result.

Theorem 1.1. Let K ⊂ R N be a convex body and let u be the solution of Problem (1) with s = 1/2. Then (i) u is level set convex, that is, for every c ∈ R the set {u > c} is convex;

(ii) the 1-Riesz capacity Cap 1 (K) satisfies the following Brunn-Minkowski inequality:

for any couple of convex bodies K 0 and K 1 and for any λ ∈ [0, 1] we have

Cap 1 (λK 1 + (1 -λ)K 0 ) 1 N-1 ≥ λCap 1 (K 1 ) 1 N-1 + (1 -λ)Cap 1 (K 0 ) 1 N-1 . ( 7
)
The proof of the Theorem 1.1 will be given in Section 2, and relies on the results in [START_REF] Cuoghi | Convexity of level sets for solutions to nonlinear elliptic problems in convex rings[END_REF][START_REF] Colesanti | The Brunn-Minkowski inequality for p-capacity of convex bodies[END_REF] and on the following observation due to L. Caffarelli and L. Silvestre.

Proposition 1.2 ([7]

). Let f : R N → R be a measurable function and let U : R N × [0, +∞) be the solution of

∆ (x,t) U (x, t) = 0, on R N × (0, +∞) U (x, 0) = f (x).
Then, for any x ∈ R N there holds

lim t→0 + ∂ t U (x, t) = (-∆) 1 2 f (x).
Eventually, in Section 3 we provide an application of Theorem 1.1 and we state some open problems.

Proof of the main result

This section is devoted to the proof of Theorem 1.1.

Lemma 2.1. Let K be a compact convex set with positive 2-capacity and let (K ε ) ε>0 be a family of compact convex sets with positive 2-capacity such that K ε → K in the Hausdorff distance, as ε → 0. Letting u ε and u be the capacitary functions of K ε and K respectively, we have that u ε converges uniformly on R N to u as ε → 0. As a consequence, we have that the sequence C 2 (K ε ) converges to C 2 (K), and that the sets {u ε > s} converge to {u > s} for any s > 0, with respect to the Hausdorff distance.

Proof. We only prove that u ε → u uniformly as ε → 0 since this immediately implies the other claims. Let Ω

ε = K ∪ K ε . Since u ε -u is a harmonic function on R N \ Ω ε , we have that sup R N \Ωε |u ε -u| ≤ sup ∂Ωε |u ε -u| ≤ max 1 -min ∂Ωε u, 1 -min ∂Ωε u ε . (8)
Moreover, by Hausdorff convergence, we know that there exists a sequence (r ε ) ε infinitesimal as ε → 0 such that u, min

K ε ⊂ K + B rε ,
Kε+B(2rε) u ε . (9)
Since the right-hand side of ( 9) converges to 1 as ε → 0, from ( 8) we obtain

lim ε→0 sup R N \Ωε |u ε -u| = 0,
which brings to the conclusion.

Remark 2.2. Notice that a compact convex set has positive 2-capacity if and only if its H N -1 -measure is non-zero (see [START_REF] Evans | Measure theory and fine properties of functions[END_REF]).

Proof of Theorem 1.1. We start by proving claim (i). Let us consider the problem

       -∆ (x,t) U (x, t) = 0 in R N × (0, ∞) U (x, 0) = 1 x ∈ K U t (x, 0) = 0 in x ∈ R N \ K lim |(x,t)|→∞ U (x, t) = 0. ( 10
)
By Proposition 1.2 we have that U (x, 0) = u(x) for every x ∈ R N . Notice also that, for any c ∈ R, we have

{u ≥ c} = {(x, t) : U (x, t) ≥ c} ∩ {t = 0}
which entails that u is level set convex, provided that U is level set convex. In order to prove this, we introduce the problem

   ∆ (x,t) V (x, t) = 0 in R N +1 \ K V = 1 x ∈ K lim |(x,t)|→∞ V (x, t) = 0 (11)
whose solution is given by the capacitary function of the set K in R N +1 , that is, the function which achieves the minimum in Problem (5).

Since K is symmetric with respect to the hyperplane {t = 0} (where it is contained), it follows, for instance by applying a suitable version of the Pólya-Szegö inequality for the Steiner symmetrization (see for instance [START_REF] Brock | Weighted Dirichlet-type inequalities for Steiner Symmetrization[END_REF][START_REF] Burchard | Steiner symmetrization is continuous in W 1,p[END_REF]), that V is symmetric as well with respect to the same hyperplane. In particular we have that ∂ t V (x, 0) = 0 for all x ∈ R N \ K. This implies that V (x, t) = U (x, t) for every t ≥ 0. To conclude the proof, we are left to check that V is level set convex. To prove this we recall that the capacitary function of a convex body is level set convex, as proved in [START_REF] Colesanti | The Brunn-Minkowski inequality for p-capacity of convex bodies[END_REF]. Moreover, by Lemma 2.1 applied to the sequence of convex bodies K ε = K + B(ε) we get that V is level set convex as well. This concludes the proof of (i).

To prove (ii) we start by noticing that the 1-Riesz capacity is a (1-N )-homogeneous functional, hence inequality ( 7) can be equivalently stated (see for instance [START_REF] Borell | Capacitary inequalities of the Brunn-Minkowski type[END_REF]) by requiring that, for any couple of convex sets K 0 and K 1 and for any λ ∈ [0, 1], the inequality Cap

1 (λK 1 + (1 -λ)K 0 ) ≥ min{Cap 1 (K 0 ), Cap 1 (K 1 )} ( 12
)
holds true.

We divide the proof of ( 12) into two steps.

Step 1.

We characterize the 1-Riesz capacity of a convex set K as the behaviour at infinity of the solution of the following PDE   

(-∆) 1/2 v K = 0 in R N \ K v K = 1 in K lim |x|→∞ |x| N -1 v K (x) = Cap 1 (K)
We recall that, if µ K is the optimal measure for the minimum problem in (2), then the function

v(x) = R N dµ K (y) |x -y| N -1
is harmonic on R N \ K and is constantly equal to I 1 (K) on K (see for instance [START_REF] Goldman | Existence and stability for a nonlocal isoperimetric model of charged liquid drops[END_REF]). Moreover the optimal measure µ K is supported on K, so that |x| N -1 v(x) → µ K (K) = 1 as |x| → ∞. The claim follows by letting v K = v/I 1 (K).

Step 2.

Let K λ = λK 1 + (1 -λ)K 0 and v λ = v K λ . We want to prove that v λ (x) ≥ min{v 0 (x), v 1 (x)}
for any x ∈ R N . To this aim we introduce the auxiliary function

v λ (x) = sup min{v 0 (x 0 ), v 1 (x 1 )} : x = λx 1 + (1 -λ)x 0 ,
and we notice that Step 2 follows if we show that v λ ≥ v λ . An equivalent formulation of this statement is to require that for any s > 0 we have

{ v λ > s} ⊆ {v λ > s}. (13)
A direct consequence of the definition of v λ is that

{ v λ > s} = λ{v 1 > s} + (1 -λ){v 0 > s}.
For all λ ∈ [0, 1], we let V λ be the harmonic extension of

v λ on R N × [0, ∞), which solves    -∆ (x,t) V λ (x, t) = 0 in R N × (0, ∞) V λ (x, 0) = v λ (x) in R N × {0} lim |(x,t)|→∞ V λ (x, t) = 0. (14) Notice that V λ is the capacitary function of K λ in R N +1 , restricted to R N × [0, +∞). Letting H = {(x, t) ∈ R N × R : t = 0}, for any λ ∈ [0, 1] and s ∈ R we have {V λ > s} ∩ H = {v λ > s}.
Letting also [START_REF] Goldman | Existence and stability for a nonlocal isoperimetric model of charged liquid drops[END_REF] as above we have that

V λ (x, t) = sup{min{V 0 (x 0 , t 0 ), V 1 (x 1 , t 1 )} : (x, t) = λ(x 1 , t 1 ) + (1 -λ)(x 0 , t 0 )},
{ V λ > s} = λ{V 1 > s} + (1 -λ){V 0 > s}.
By applying again Lemma 2.1 to the sequences K ε 0 = K 0 + B(ε) and K ε 1 = K 1 + B(ε), we get that the corresponding capacitary functions, denoted respectively as V ε 0 and V ε 1 , converge uniformly to V 0 and V 1 in R N , and that V ε λ , defined as in [START_REF] Goldman | Existence and stability for a nonlocal isoperimetric model of charged liquid drops[END_REF], converges uniformly to V λ on R N × [0, +∞).

Since V ε λ (x, t) ≤ V ε λ (x, t) for any (x, t) ∈ R N × [0, +∞), as shown in [9, pages 474 -476], we have that V λ (x, t) ≤ V λ (x, t). As a consequence, we get

{v λ > s} = {V λ > s} ∩ H ⊇ { V λ > s} ∩ H = λ{V 1 > s} + (1 -λ){V 0 > s} ∩ H ⊇ λ{V 1 > s} ∩ H + (1 -λ){V 0 > s} ∩ H = λ{v 1 > s} + (1 -λ){v 0 > s}
for any s > 0, which is the claim of Step 2.

We conclude by observing that inequality [START_REF] Di Nezza | Valdinoci Hitchhikers guide to the fractional Sobolev spaces[END_REF] follows immediately, by putting together Step 1 and Step 2. This concludes the proof of (ii), and of the theorem.

Remark 2.3. The equality case in the Brunn-Minkowski inequality [START_REF] Caffarelli | An extension problem related to the fractional Laplacian[END_REF] is not easy to address by means of our techniques. The problem is not immediate even in the case of the 2-capacity, for which it has been studied in [START_REF] Caffarelli | On the Case of Equality in the Brunn-Minkowski Inequality for Capacity[END_REF][START_REF] Colesanti | The Brunn-Minkowski inequality for p-capacity of convex bodies[END_REF].

Applications and open problems

In this section we state a corollary of Theorem 1.1. To do this we introduce some tools which arise in the study of convex bodies. The support function of a convex body K ⊂ R N is defined on the unit sphere centred at the origin ∂B(1) as

h K (ν) = sup x∈∂K x, ν .
The mean width of a convex body K is

M (K) = 2 H N -1 (∂B(1)) ∂B(1) h K (ν) dH N -1 (ν).
We refer to [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF] for a complete reference on the subject. We observe that, if N = 2, then M (K) coincides up to a constant with the perimeter P (K) of K (see [START_REF] Bucur | Optimal convex shapes for concave functionals[END_REF]). We denote by K N the set of convex bodies of R N and we set

K N,c = {K ∈ K N , M (K) = c}.
The following result has been proved in [START_REF] Bucur | Optimal convex shapes for concave functionals[END_REF].

Theorem 3.1. Let F : K N → [0, ∞) be a q-homogeneous functional which satisfies the Brunn-Minkowski inequality, that is, such that F (K + L) 1/q ≥ F (K) 1/q + F (L) 1/q for any K, L ∈ K N . Then the ball is the unique solution of the problem

min K∈K N M (K) F 1/q (K) . (16)
An immediate consequence of Theorem 3.1, Theorem 1.1 and Definition 4 is the following result.

Corollary 3.2. The minimum of I 1 on the set K N,c is achieved by the ball of measure c. In particular, if N = 2, the ball of radius r solves the isoperimetric type problem min K∈K 2 ,P (K)=2πr

I 1 (K). ( 17
)
Motivated by Theorem 1.1 and Corollary 3.2 we conclude the paper with the following conjectures: Conjecture 3.3. For any N ≥ 2 and α ∈ (0, N ), the α-Riesz capacity Cap α (K) satisfies the following Brunn-Minkowski inequality: for any couple of convex bodies K 0 and K 1 and for any λ ∈ [0, 1] we have

Cap α (λK 1 + (1 -λ)K 0 ) 1 N-α ≥ λCap α (K 1 ) 1 N-α + (1 -λ)Cap α (K 0 ) 1 N-α . ( 18
)
Conjecture 3.4. For any N ≥ 2 and α ∈ (0, N ), the ball of radius r is the unique solution of the problem min K∈K N ,P (K)=N ω N r N-1

I α (K). (19)

  where B(r) indicates the ball of radius r centred at the origin.

Acknowledgements

The authors wish to thank G. Buttazzo and D. Bucur for useful discussions on the subject of this paper.


Introduction 1

There are two basic approaches for Data Assimilation:

Variational Methods

Kalman Filter

Both lead to minimize a cost function :

J(u) = 1 2 (V -1 b (u -u b ), u -u b ) X + 1 2 (V -1 o (C ϕ -y ), C ϕ -y ) Yo , (1)
where u b ∈ X is a prior initial-value function (background state), y ∈ Y o is a prescribed function (observational data), Y o is an observation space, C : Y → Y o is a linear bounded operator. We get the same optimal solution ū

Introduction 2

ū is the solution of the Optimality System :

∂ϕ ∂t = F (ϕ) + f , t ∈ (0, T ) ϕ t=0 = u, (2)
∂ϕ * ∂t + (F ′ (ϕ)) * ϕ * = C * V -1 o (C ϕ -y ), t ∈ (0, T ) ϕ * t=T = 0, (3)
V -1 b (u -u b ) -ϕ * t=0 = 0 (4)
Analysis Error Covariance 1: True solution and Errors

We assume the existence of a "true" solution u t and an associated "true" state ϕ t verifying:

   ∂ϕ t ∂t = F (ϕ t ) + f , t ∈ (0, T ) ϕ t t=0 = u t . (5)
Then the errors are defined by :

u b = u t + ξ b , y = C ϕ t + ξ o with covariances V b andV o
Analysis Error Covariance 2: Discrepancy Evolution

Let δϕ = ϕ -ϕ t , δu = u -u t .
Then for regular F there exists φ =

ϕ t + τ (ϕ -ϕ t ), τ ∈ [0, 1], such that ∂δϕ ∂t -F ′ ( φ)δϕ = 0, t ∈ (0, T ), δϕ| t=0 = δu, (6) ∂ϕ
* ∂t + (F ′ (ϕ)) * ϕ * = C * V -1 o (C δϕ -ξ o ), ϕ * t=T = 0, (7) V -1 b (δu -ξ b ) -ϕ * | t=0 = 0. ( 8
)
Analysis Error Covariance 3: Exact Equation for Analysis Error

Let us introduce the operator R(ϕ) : X → Y as follows:

R(ϕ)v = ψ, v ∈ X , ( 9
)
where ψ is the solution of the tangent linear problem

∂ψ ∂t -F ′ (ϕ)ψ = 0, ψ| t=0 = v . (10)
Then, the system for errors can be represented as a single operator equation for δu:

H(ϕ, φ)δu = V -1 b ξ b + R * (ϕ)C * V -1 o ξ o , (11)
where The operator H(ϕ, φ) : X → X can be defined by

H(ϕ, φ) = V -1 b + R * (ϕ)C * V -1 o CR( φ). ( 12
∂ψ ∂t -F ′ ( φ)ψ = 0, ψ| t=0 = v , (13)
- ∂ψ * ∂t -(F ′ (ϕ)) * ψ * = -C * V -1 o C ψ, ψ * t=T = 0, (14)
H(ϕ, φ)v = V -1 b v -ψ * | t=0 . ( 15
)
The operator H(ϕ, φ) is neither symmetric, nor positive definite. ϕ = φ = θ, it becomes the Hessian H(θ) of the cost function J 1 in the following auxiliary DA problem: find δu and δϕ such that

J 1 (δu) = inf v J 1 (v ),
where

J 1 (δu) = 1 2 (V -1 b (δu -ξ b ), δu -ξ b ) X + 1 2 (V -1 o (C δϕ -ξ o ), C δϕ -ξ o ) Yo , (16) and δϕ satisfies the problem ∂δϕ ∂t -F ′ (θ)δϕ = 0, δϕ t=0 = δu. ( 17
)
Analysis Error Covariance 5 : Analysis Error Covariance via Hessian

The optimal solution (analysis) error δu is assumed to be unbiased, i.e. E [δu] = 0, and

V δu • = E [(•, δu) X δu] = E [(•, u -u t ) X (u -u t )]. ( 18
)
The best value of ϕ and φ independent of ξ o , ξ b is apparently ϕ t and using

R( φ) ≈ R(ϕ t ), R * (ϕ) ≈ R * (ϕ t ), (19)
the error equation reduces to

H(ϕ t )δu = V -1 b ξ b + R * (ϕ t )C * V -1 o ξ o , H(•) = V -1 b + R * (•)C * V -1 o CR(•).
(20) We express δu from equation (??)

δu = H -1 (ϕ t )(V -1 b ξ b + R * (ϕ t )C * V -1 o ξ o
) and obtain for the analysis error covariance 21)

V δu = H -1 (ϕ t )(V -1 b + R * (ϕ t )C * V -1 o CR(ϕ t ))H -1 (ϕ t ) = H -1 (ϕ t ). (
Analysis Error Covariance 6 : Approximations

In practice the 'true' field ϕ t is not known, thus we have to use an approximation φ associated to a certain optimal solution ū defined by the real data (ū b , ȳ ), i.e. we use

V δu = H -1 ( φ). (22)
In (Rabier and Courtier,1992), the error equation is derived in the form

(V -1 b + R * (ϕ)C * V -1 o CR(ϕ))δu = V -1 b ξ b + R * (ϕ)C * V -1 o ξ o . (23)
The error due to transitions R( φ) → R(ϕ t ) and R * (ϕ) → R * (ϕ t ); we call it the 'linearization' error. The use of φ instead of ϕ t in the Hessian computations leads to another error, which shall be called the 'origin' error.

Posterior Covariance : Bayesian Approach 1

Given u b ∼ N (ū b , V b ), y ∼ N (ȳ , V o )
, the following expression for the posterior distribution of u is derived from the Bayes theorem:

p(u|ȳ ) = C • exp (- 1 2 (V -1 b (u -ūb ), u -ūb ) X )• exp(- 1 2 (V -1 o (C ϕ -ȳ ), C ϕ -ȳ ) Yo ). ( 24
)
The solution to the variational DA problem with the data y = ȳ and u b = ū is equal to the mode of p(u, ȳ ) (see e.g. Lorenc, 1986;Tarantola, 1987). Accordingly, the Bayesian posterior covariance is defined by :

V δu • = E [(•, u -E [u]) X (u -E [u]) (25)
with u ∼ p(u|ȳ ).

∂ φ ∂t = F ( φ) + f , ϕ t=0 = ū, (27)
∂ φ * ∂t + (F ′ ( φ)) * φ * = C * V -1 o (C φ -ȳ ), φ * t=T = 0, (28)
V -1 b (ū -ūb ) -φ * t=0 = 0 (29)
With perturbations :

u b = ūb + ξ b , y = ȳ + ξ o , where ξ b ∈ X , ξ o ∈ Y o . δu = u -ū, δϕ = ϕ -φ, δϕ * = ϕ * -φ * . ∂δϕ ∂t = F (ϕ) -F ( φ), δϕ t=0 = δu, ( 30
)
∂δϕ * ∂t +(F ′ (ϕ)) * δϕ * = [((F ′ ( φ)) * -F ′ (ϕ)) * ] φ * +C * V -1 o (C δϕ-ξ o ), (31) V -1 b (δu -ξ b ) -δϕ * t=0 = 0. ( 32
)
Posterior Covariance : Exact Errors Equations

Introducing φ1 = φ + τ 1 δϕ, φ2 = φ + τ 2 δϕ, τ 1 , τ 2 ∈ [0, 1], we derive the exact system for errors:

∂δϕ ∂t = F ′ ( φ1 )δϕ, δϕ t=0 = δu, ( 33
)
∂δϕ * ∂t + (F ′ (ϕ)) * δϕ * = [(F ′ ( φ2 )) * φ * ] ′ δϕ + C * V -1 o (C δϕ -ξ o ), (34) V -1 b (δu -ξ b ) -δϕ * t=0 = 0, (35)
equivalent to a single operator equation for δu:

H(ϕ, φ1 , φ2 )δu = V -1 b ξ b + R * (ϕ)C * V -1 o ξ o , (36)
where Posterior Covariance : Operator H H(ϕ, φ1 , φ2 ) : X → X is defined by solving:

H(ϕ, φ1 , φ2 ) = V -1 b + R * (ϕ)(C * V -1 o C -[(F ′ ( φ2 )) * φ * ] ′ )R( φ1
∂ψ ∂t = F ′ ( φ1 )ψ, ψ t=0 = v , (38)
- ∂ψ * ∂t -(F ′ (ϕ)) * ψ * = [(F ′ ( φ2 )) * φ * ] ′ ψ -C * V -1 o C ψ, (39)
H(ϕ, φ1 , φ2 )v = V -1 b v -ψ * t=0 . (40)
If we had ϕ = φ1 = φ2 , H(ϕ) becomes the Hessian of the cost function in the original DA problem, it is symmetric and positive definite if u is a minimum of J(u). The equation is often referred as the 'second order' adjoint (Le Dimet et al., 2002).

As above, we assume that E (δu) ≈ 0, and we consider the following approximations

R( φ1 ) ≈ R( φ), R * (ϕ) ≈ R * ( φ), [(F ′ ( φ2 )) * φ * ] ′ ≈ [(F ′ ( φ)) * φ * ] ′ . (41) F.-X.
∂ϕ ∂t + 1 2 ∂(ϕ 2 ) ∂x = ∂ ∂x ν(ϕ) ∂ϕ ∂x , (50)
ϕ = ϕ(x, t), t ∈ (0, T ), x ∈ (0, 1),
with the Neumann boundary conditions

∂ϕ ∂x x=0 = ∂ϕ ∂x x=1 = 0 (51)
and the viscosity coefficient

ν(ϕ) = ν 0 + ν 1 ∂ϕ ∂x 2 , ν 0 , ν 1 = const > 0. ( 52
)
Two initial conditions u t = ϕ t (x, 0) are considered (case A and case B), Numerical Example : Squared Riemann distance The mean deviation vector σ is defined as follows:

µ(A, B) = M i=1 ln 2 γ i 1/2 . Case µ 2 (V 3 , V) µ 2 (V 2 , V) µ 2 (V 1 , V) µ 2 (V e 3 , V) µ 2 (V e 2 , V) µ 2 (V e 1 , V
σ(i) = V 1/2 (i, i).
The reference mean deviation σ(x) (related to V). Cases B6, B9. In the linear case the covariances coincide

In the nonlinear case strong discrepancies can occur.

Algorithms for the estimation and the approximation of these covariances are proposed.

Gejadze, I.,Shutyaev, V., Le Dimet, F.-X. Analysis error covariance versus posterior covariance in variational data assimilation problems. Q.J.R.Meteolol. Soc. (2013).

F

  S. with u b = ūb , y = ȳ :

F

  )

	Analysis Error Covariance 4 : H Operator
	F.-X. Le Dimet (INRIA)	Posterior covariance	September 27, 2013	9 / 1

  ConclusionVariational and Bayesian approaches of DA lead to the minimization of the same function For Error Estimation we obtain two different concepts Analysis Error Covariance for the Variational Approach Posterior Covariance for the Bayesian Approach

	Absolute errors in the correlation matrix: ǫ 3 , ǫ e 3 , ǫ e 1 (case Absolute errors in the correlation matrix: ǫ 3 , ǫ e 3 , ǫ e 1 (case Absolute errors in the correlation matrix: ǫ 3 , ǫ e 3 , ǫ e 1 (case
	A2) A8) B6)
		0.14 0.16						case B9 case B6		a)	a) a)
		0.12
		0.1								b)	b) b)
	σ	0.08
		0.06
		0.04
											c)	c) c)
		0.02
		0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1
								x
	F.-X. Le Dimet (INRIA) F.-X. Le Dimet (INRIA) F.-X. Le Dimet (INRIA) F.-X. Le Dimet (INRIA)				Posterior covariance case A2 Posterior covariance case A8 Posterior covariance case B6 Posterior covariance			September 27, 2013 September 27, 2013 September 27, 2013 September 27, 2013	25 / 1 26 / 1 27 / 1

September 27, 2013

Posterior Covariance : Bayesian Approach 2

In order to compute V δu by the Monte Carlo method, one must generate a sample of pseudo-random realizations u i from p(u|ȳ ). We will consider u i to be the solutions to the DA problem with the perturbed data u b = ūb + ξ b , and

Further we assume that E [u] = ū, where ū is the solution to the unperturbed problem in which case V δu can be approximated as follows

Posterior Covariance via Hessian

The exact error equation (??) is approximated as follows

where

Now, we express δu :

and obtain an approximate expression for the posterior error covariance

) where H( φ) is the Hessian of the cost function J 1 computed at θ = φ. Other approximations of the posterior covariance:

Posterior Covariance : "Effective" Estimates

To supress the linearization errors, the 'effective' inverse Hessian may be used for estimating the analysis error covariance (see Gejadze et al., 2011):

The same is true for the posterior error covariance V δu :

First, we substitute a possibly asymmetric and indefinite operator H(ϕ, φ1 , φ2 ) by H(ϕ):

Next, by assuming H(ϕ)H -1 (ϕ) ≈ I we get

Finally, by assuming H -1 (ϕ) ≈ H -1 (ϕ) we obtain yet another approximation


Guy Royer

Hongfei Zhang

Philippe Eudes

Rachid Moustabchir

Damien Moreau

Muriel Jaffré

Youssef Morabit

Benjamin Particelli

Fission of actinides through quasimolecular shapes

  L'archive ouverte pluridisciplinaire

Introduction

The analysis of the fission cross sections of actinides and of their ground and isomeric state properties indicates the existence of double-humped potential barriers. The fission probability and the angular distribution of the fragments suggest also the existence of hyperdeformed states in a deep third well in several Th and U isotopes [1][2]. It is also necessary to suppose fission barrier heights of 5-10 MeV to explain the stability of superheavy elements of charge 112-118 [3][4].

The fission shapes were firstly investigated by minimizing the sum of the surface and Coulomb energies using a development of the radius in Legendre polynomials. This leads to decay paths through very elongated shapes with shallow neck or no neck. Within a Generalized Liquid Drop Model (GLDM) taking into account the mass and charge asymmetries, the proximity energy, and the shell and pairing energies, it has been demonstrated that there is a degeneracy between the energy of quasimolecular shapes and the energy of elongated shapes with a shallow neck. Most of the binary and ternary fission,  and light nucleus emission and fusion properties have been also reproduced in this quasimolecular shape valley [5][6][7][8][9]. The purpose of this work is to investigate the actinide region remaining in this peculiar fusionlike shape path, taking into account the ellipsoidal deformations of the fission fragments, studying with this GLDM all the possible mass and charge asymmetries, accounting for shell and pairing energies.

a Corresponding author: royer@subatech.in2p3.fr

Potential barriers

Firstly, the macroscopic contributions to the deformation energy E derived from this GLDM energy are shown in Fig. 1 for the 160 Dy nucleus. The surface and proximity energies E s and E n change drastically at the contact point since the surface is constant after the separation and the nuclear attraction is greatest at the contact point. Nevertheless, the total energy varies gently even around the contact point. Moreover the barrier height corresponds to the fission barrier height [5]. In the Fig. 2 the deformation energies of the 234 U nucleus corresponding to different shape sequences without and with proximity energy contribution are compared. The potential energy calculated using quasimolecular shapes without taking into account the proximity energy, the so-called Coulomb barrier, is very energetically unfavourable . On the contrary, when the proximity energy is included for the same shape sequence, the barrier height may be compared with the barrier height of the potential energy for usual elongated and little or not creviced shapes. Furthermore, a double-humped barrier appears even macroscopically for the compact and necked shapes. This shows clearly that the comparison between the two shape sequences must be re-examined when the additional proximity energy term is taken into account. The two spheroid shapes would be also highly competitive with regard to the usual elongated shapes if the proximity energy was included. The picture of the Businaro-Gallone point assuming that, macroscopically, asymmetric fission is favoured for light systems and symmetric fission for heavy nuclei is also observed in the quasimolecular shape path (see Fig. 3). More generally, it has been proved that the potential barrier heights in this valley correspond precisely to the fission barrier heights [5,9].

Fission 2013

The dependence of the potential barriers on the mass of the decaying nucleus is displayed in Fig. 4. With increasing mass appear macroscopically a plateau and a second external relative minimum and internal peak due to the proximity energy and then the possibility of isomeric states. In Fig. 5 the shell and pairing energies have been introduced as well as the ellipsoidal deformations of the fragments to calculate the different exit channels of 240 Pu. Multiple-humped potential barriers appear. The heights of the two peaks are displayed on Fig. 6. The height of the first peak is almost constant since it depends on the shell effects around the ground state. The shell effects and the proximity energies flatten the potential energy surface and generate a shallow second minimum. The second maximum, the saddle-point, corresponds to the transition from compact and creviced one-body shapes to two touching oblate ellipsoids. The height of this second peak generally increases with the asymmetry but the shell and pairing energies lead to strong distortions from this general behaviour. The barrier for the most probable exit channel is also shown on Fig. 7. The scission point corresponds to the vanishing of the proximity energy and the effective separation of the fragments . It occurs on an energy plateau corresponding to the fragment kinetic energy plus an excitation energy. The evolution of the shell effects and shapes of the fragments play a main role during the descent from the saddlepoint to the scission point (see also [10]).

Shallow third minimum and peak appear in specific asymmetric exit channels where one fragment is close to a double magic quasi-spherical nucleus while the other one evolves from oblate to prolate shapes. Then the third peak corresponds to two separated spheres and the maximum of the shell effects. Such triple-humped barriers do not appear in symmetric exit channels.

The heights of the two peaks of the potential barriers roughly agree with the experimental data [9].

Fission half-lives

Within this asymmetric fission model the decay constant is simply the product of the assault frequency by the barrier penetrability. For shapes near the ground state the selected inertia is largely above the irrotational flow value since a large amount of internal reorganization occurs at level crossings [9]. For highly deformed shapes the reduced mass is reached asymptotically. The experimental spontaneous fission half-lives and theoretical predictions are compared in Table 1. There is a rough agreement with most of the experimental data on 26 orders of magnitude for the actinides. The same approach has been applied to superheavy elements. The GLDM leads to too low half-life values assuming that Z=114 is the next proton magic number. A better agreement is obtained selecting Z=116. Finally the last column of table 1 gives the values obtained with an improved version of the GLDM [11] which uses slightly different parameters and calculates the shell effects from a Woods-Saxon potential, the pairing energy being shape dependent. 2.9  10 -2 3.9  10 -5

5.1  10 -8

6.9  10 -2

Summary and conclusion

Potential barriers of actinides in the quasimolecular shape path have been studied within a generalized liquid drop model including the nuclear proximity energy and microscopic corrections. Double-humped potential barriers and large deformed minima lodging possibly isomeric states appear. The external saddle-point corresponds to the transition from one-body creviced shapes to two touching ellipsoids. The scission point, where the effects of the nuclear attractive forces between the fragments vanish, lies at the end of an energy plateau below the saddle-point. The energy on this plateau corresponds to the fragment kinetic energy plus an excitation energy. The barrier heights roughly agree with the experimental data. The shell and pairing effects play a main role to decide the most probable decay path. The predicted half-lives follow most of the experimental data. A shallow third minimum and a third peak appear in specific asymmetric exit channels where one fragment is close to a double magic quasispherical nucleus, while the other one evolves from oblate to prolate shapes.

1 .

 1 Contribution of the Coulomb, surface and nuclear proximity energies to the total deformation energy E of the 160 Dy versus the distance between the mass centers. The dotted line indicates the contact point between spherical fragments.

Figure 2 .

 2 Figure 2. Fission barriers of 234 U : the dotted and thick full curves correspond to the potential for quasimolecular shapes without and with proximity energy, the thin full curve gives the energy of elongated shapes while the chain curve is the energy of two separated oblate spheroids without proximity contribution.

Figure 3 .

 3 Figure 3. Macroscopic fission barriers as functions of the decay asymmetry (A 1 -A 2 )/(A 1 +A 2 ) and the distance between the mass centers r for the two 86 Kr and 205 At nuclei.

Figure 4 .

 4 Figure 4. Macroscopic barriers of the symmetric fission in the beta-stability valley and in the quasimolecular shape valley.

Figure 5 .

 5 Figure 5. Multiple-humped microscopic barriers for 240 Pu as a function of the heaviest fragment mass.

Figure 6 .

 6 Figure 6. Heights of the inner and outer peaks of the fission barrier versus the mass of the heaviest fragment.

Figure 7 .

 7 Figure 7. Asymmetric fission barrier of a 240 Pu nucleus emitting a magic nucleus 128 Sn. The dashed curve corresponds to the macroscopic energy within the twosphere approximation for the two-body shapes while the solid line includes the microscopic corrections and the ellipsoidal deformations of the fragments.

2  10 - 4 5. 2  10 - 5 3. 5 

 210421055 10 -8

Table 1 .

 1 Comparison between experimental and theoretical spontaneous fission half-lives.

	Nucleus	T 1/2, exp (s)	T 1/2 (s) [9, Z=114] T 1/2 (s) [9, Z=116]	T 1/2, (s) [11]
	234 U	4.7  10 23
	236 U	7.8  10 23
	238 U	2.6  10 23
	239 Pu	2.5  10 23
	240 Pu	3.7  10 18
	243 Am	6.3  10 21
	243 Cm	1.7  10 19
	245 Cm	4.4  10 19
	248 Cm	1.3  10 14
	249 Bk	6.1  10 16
	250 Cf	5.2  10 11
	253 Es	2.0  10 13
	255 Es	8.4  10 10
	250 Fm
	254 Fm
	255 Md
	257 Md
	259 Md
	252 No
	254 No
	256 No
	252 Lr
	256 Lr
	259 Lr
	256 Rf
	258 Rf
	260 Rf
	255 Db
	258 Sg
	262 Sg
	264 Hs
	286 Fl


Mahsa Najafzadeh

Marc Shapiro

Improving the scalability of geo-replication with reservations *

Geo-replicated systems improve performance and fault tolerance by replicating data on sites in different physical locations. These systems often eschew guaranteeing strong consistency because of performance loss and scalability and instead choose eventually consistency. Although eventual consistency improves performance especially in large scale but it might violate system invariants. In this work, we exploit reservation techniques to strengthen eventual consistency, by adding safety guarantees. We define a consistency model called RPB that takes the advantages of eventual consistency while providing stronger guarantees, including causality and safety properties.

Introduction

In cloud computing systems, geo-replication copies data in multiple data centers, in order to bring data close to the client. This aims to improve performance, by avoiding slow long-haul communication, and to improve availability and fault tolerance thanks to redundant data. However, in the presence of failures, system designers must choose to maintain either availability (and performance) or consistency -both are not possible together [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF].

The recent proposal by Li et al. [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF] enables both approaches to co-exist, by classifying operations as red and blue. Blue operations commute with all others; they are fast and available even when disconnected; they ensure causal eventual consistency [START_REF] Mahajan | Consistency, availability, and convergence[END_REF]. For instance, in a bank account application, credit operations are blue, i.e., the user can add to his account in all circumstances.

Red operations must be mutually ordered, requiring system-wide synchronisation; they ensure strong consistency. In the banking application, debits are red, because the system needs to stop a debit that would make the balance negative. If the client cannot connect with the bank server, all debits are blocked.

The system is available even when the network partitions as long as the application invokes only blue operations [START_REF] Brewer | CAP twelve years later: How the "rules" have changed[END_REF]. If the workload is dominated by blue operations, performance is improved. However, the red-blue classification is conservative. An operation that might not commute, even rarely, is classified as red. For instance, in the bank example, debits are always red, even when the account has a high balance and the amount of the debit is small.

In this work, we identify another class of operations, called purple, that commute in well-defined states, and propose a reservation mechanism to identify and leverage such states. Returning to the example, a particular bank branch could reserve a portion of the account's balance, say 1 000 e out of a balance of 10 000 e, for a particular amount of time. This gives the branch the capability to make any number of debits, up to 1 000 e until the end of the day, without communicating. Of course, a (batched) summary of the debits must be sent to the bank's main servers before the reservation expires.

Since a blue operation never conflicts, it can execute at a replica without remote synchronisation. The operation propagates asynchronously, to ensure it executes durably at every replica. In contrast, a red operation requires a strong synchronisation protocol such as two-phase commit, where the first phase checks for conflicts, and the second phase makes it durable.

De-coupling these different concerns, the purple protocol has three phases. Acquiring a reservation ensures that future purple operations will not conflict. Local purple execution with appropriate reservation occurs without any synchronisation. Releasing a reservation, either explicitly or by it timing out, ends the reservation guarantees. Purple execution is as fast and available as blue operations, while reservations ensure guarantees as strong as red operations.

A possibly-conflicting operation lacking proper reservation cannot be handled as purple; it must be treated as red.

Reservation is similar to a kind of a lock or escrow [START_REF] O'neil | The escrow transactional method[END_REF], generalised to non-numeric data types [START_REF] Preguiça | Reservations for conflict avoidance in a mobile database system[END_REF]. This paper further extends the reservation technique to georeplicated clouds.

The rest of this paper is structured as follows. In Section 2, we define our Red-Purple-Blue (RPB) model, motivating with use cases. Section 3 describes the RPB protocol. We discuss fault tolerance in Section 4. Section 5 presents some concluding results and future work.

2 Red-Purple-Blue Consistency

System model

We assume a multi-tier system model, consisting of clients, application servers, and data servers. Data servers, located in data centres, are entrusted with storing data and applying updates durably; we assume that every data centre replicates all the data. Both kinds of servers are assumed reliable, i.e., they may crash but recover with their durable state intact. A client is located at the edge of the network and can access the system only through an application server.

Application logic executes on application servers, called scouts, which initiate red, purple and blue operations. We assume that a scout caches recently-accessed objects and stores reservations. Physically, a scout can be located where most convenient: in a data centre, in a network point-of-presence (PoP), or even in a trusted virtual machine in the client's computer. A scout located close to a client will improve responsiveness and availability (if it has enough cached objects and reservations); one close to a data server will get better consistency and can be shared among multiple clients. However, discussion of the trade-offs is out of our scope; for illustration purposes, we will assume that a scout is located at a PoP, in the cloud infrastructure, to preferentially serve nearby clients.

Red, purple and blue operations

Consider operations on some shared database. 1 Recall that an object is replicated at all data servers, and at a subset of the scouts (cached). Operations are invoked at some scout.

As mentioned, RPB supports three types of update operations: red, purple and blue. All operations are causally ordered [START_REF] Mahajan | Consistency, availability, and convergence[END_REF]; additionally, conflicting red operations are totally ordered with one another [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF]. A blue operation executes at some replica without remote synchronisation, and propagates to other replicas asynchronously. A red operation is strongly consistent, i.e., conflicting red operations execute in the same mutual order at all replicas; this incurs a significant synchronisation cost, which increases with contention. Blue operations are always available; red operations are not available when the network partitions.

A purple operation requires an appropriate reservation. The reservation ensures that the purple operation will not conflict with concurrent operations, thus ensuring strong consistency guarantees, just like red operations. However, as reservation is secured in advance, a purple operation can execute without synchronisation and propagate asynchronously, just like a blue operation. A purple operation with appropriate reservation is available (assuming the data it needs is in cache) despite network partitions and data server crashes.

Commutativity

Two operations are said to commute unconditionally with one another if executing them in any mutual order yields the same result, whatever the state. For instance, increments to a shared counter x commute with one another: concurrent operations inc(x, 1) and inc(x, 2) can safely be ordered inc(x, 1); inc(x, 2), at one server and inc(x, 2); inc(x, 1) at another, since in both cases the end result is to increment x by 3.

An operation is said unconditionally commutative if it commutes unconditionally with all other operations. An unconditionally-commutative operation can be classified as blue.

For instance, assuming a counter supporting increment, decrement, and read-value operations, the inc and readval operations commute unconditionally. More generally, all the operations of a Conflict-free Replicated Data Type (CRDT) are unconditionally commutative [START_REF] Shapiro | Conflict-free replicated data types[END_REF]. CRDTs include many useful data types, such as counters, sets, graphs, and sequences [START_REF]Convergent and commutative replicated data types[END_REF].

An operation may be conditionally commutative, i.e., it commutes with all other operations, but only in certain states. For instance, consider a non-negative shared counter y: operations dec(y, 4) and dec(y, 5) commute if y ≥ 9, but otherwise not, since at least one of the decrements fails. In the red-blue model [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF], a conditionally commutative operation is always red; in our RPB model, it can be purple.

Reservation mechanism

A reservation promises, to the scout that holds it, that the system is in a state that allows the scout to run the corresponding conditionally commutative operations as purple. A reservation is valid only for a certain duration (it is a lease [START_REF] Gray | Leases: An efficient fault-tolerant mechanism for distributed file cache consistency[END_REF]).

A reservation is a contract, between the data servers and the scout, that guarantees that concurrent applications (invoked by other scouts) will not break the promise provided by the reservation. The scout may invoke purple operations locally, as long as it does not exceed the capabilities of its reservation. If transmitted and received by data servers in time, the operation(s) will become durable. However, if the scout does not hold sufficient reservation, or it times out, the same operations run as red. We describe the protocol and how it tolerates faults later in this paper.

Reservation is a kind of lock but there are differences between the traditional locks in database and the reservation. While locking a resource in database is completely transparent, the scouts have a full control over the reservation. The scouts request reservations and determine their terms. In addition, a database lock is held until the end of a transaction whereas a reservation can span multiple transactions in a scout.

Use Cases

In this section, we take a look at some scenarios in which purple operation is natural or beneficial.

Online shopping

Online shopping offers different operations, including browsing, searching, adding products to a shopping cart, placing and canceling an order, in which different levels of consistency are possible. For example, canceling an order is blue, whereas buying an item needs strong consistency, to avoid selling an item that is not in stock. A branch store or bulk-buying agency may reserve or put an option on a number of items. Then, buying is purple.

Bank application

Bank operations such as deposit or add-interest can execute independently, because they are unconditionally commutative [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF]. However, withdrawal is red, otherwise, concurrent clients could make large withdrawals, leading to negative balance. However, if a branch or a user reserves a portion of the current balance in advance,

3.

4.

Reques t reserva tion

Collaborative tools

Conflict-free Replicated Data Types (CRDT) [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF] avoid conflicts when users independently modify the same document in a collaborative application. Thanks to CRDTs, concurrent operations such as editing a document [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF], or creating and removing files, can be made unconditionally commutative (blue operations).

However, some operations are not. For instance, in a file system, atomically moving a directory must be serialisable; otherwise, cycles might occur if the destination path is concurrently modified. Reserving a directory path gives a user the capability to independently perform moves within the reserved subtree (purple). This is especially useful for mobile computing. If a user plans to travel and work disconnected, she may reserve a subtree, to be able to perform any operation, including moves within the reserved subtree.

Basic purple protocol

The basic protocol gives a scout a time-limited permission to invoke, run, and propagate corresponding purple operations, without waiting for any other server. In the next section, we will discuss fault tolerance. The full protocol is as follows, illustrated in Figure 1: 1. A scout requests and receives a reservation from the data servers. 2. The scout invokes one or more operations, and updates its local cache accordingly. (This step may occur either before or after Step 1.) 3. The scout propagates its operations to (a sufficient number of) data servers, which forward the operation to all replicas (i.e., to one another, and possibly to the scouts that cache the updated objects.) Upon receiving, the replicas also execute the operations. 4. The scout receives an acknowledgment from the data servers. 5. The scout sends any remaining reservation back to the data servers.

Note that in many cases, the protocol can be simplified. If the scout already has sufficient reservation, it may skip Step 1. If the operation exhausts the reservation, or just waits for the reservation to time out, Step 5 can be omitted. If the operations are unconditionally commutative, then both Steps 1 and 5 can be omitted: this is the blue protocol. Acquiring (Step 1), invoking, propagating (Step 3), and releasing (Step 5) can be compressed into a single two-phase commit protocol: this is the red protocol.

Although acknowledgement is required (Step 4), it is not necessary to wait for it: the scout can perform other reservations or operations immediately.

To illustrate, consider a travel agency that sells tickets for an event. For example, it might start by putting an option (a reservation in the RPB protocol) on a number of tickets. Once this is done, it can sell tickets to its clients without fear that the seats will be unavailable. The acknowledgment in Step 4 ensures the sale is durable, and visible to all replicas, but the agency can sell more tickets without waiting for the ack. At the end of the lease, the data servers automatically cancel any unconsumed reservation. This approach increases the autonomy and availability of the travel agency, and decreases the load on the data servers.

So far we focused on the scout's perspective. Consider now the protocol from the perspective of the data servers. One option is to use a primary-backup approach. A primary data server is assigned to each data object, which is responsible to handle the reservation requests on the object. A non-primary data server may forward requests from its scouts to the primary, but can also cache reservations locally to respond more quickly, as illustrated in Figure 2.

To avoid having a single point of failure, an alternative is to use a consensus protocol, such as Paxos [START_REF] Lamport | The part-time parliament[END_REF], among data servers.

When a scout propagates its operations to a data server (Step 3), the latter propagates it further to other data centers and scouts.

Fault tolerance

The red operations abort under the synchronous protocols such as two-phase commit when the network partitions, whereas the purple operations proceed their execution during failures using the proper reservations and delay their confirmation. Reservation allows to separate two consistency requirements for strong operations: conflict avoidance and durability. The scouts relax conflict checking when running purple operations, as they only need to confirm their reservations with the data server at some later time before the end of lease time. Thus, reservation minimizes the overhead when retrying red operations that block or abort due to failures.

Reservation enables our Red-Purple-Blue protocol to recover from various failures. Because a communication or scout failure can lock a data object forever. We avoid such blocking situations by including a deadline per reservation. For example, if a scout crashes, the data server preserves all its reservations until they expire and after that, any state kept for those reservations at the server is garbage collected.

Each data server records the detail of granted reservations on stable logs and hence honors all reservations despite failures. When a non-primary data server fails, the replacement server in the data center resumes propagation for the confirmed reservations that have not yet been fully propagated. A primary data server failure can be handled by using a Paxos-based reconfiguration service. The reconfiguration service selects an another data server for the data objects that their primary server is down. When a failed primary data server recovers, it must synchronize with its replacement data server to take over its responsibility.

Communication failures are recovered by sending the propagation messages with the same operation ID repeatedly until an acknowledge received. If a data server has already acked an operation and received the same operation ID again, the data server sends the acknowledgment message again, assuming the previous ack was lost. If it does not receive an acknowledgment by timeout, the purple operation reverts to red. In such case, the red operation can later fail. Thus, it is important to understand that the result of a purple operation must be considered tentative, although with a very high probability of becoming definitive. When using a fault-tolerant protocol in the servers, such as Paxos, a purple operation typically only fails if the client becomes disconnected. A client can decrease the likelihood of such event by using only reservations with validity longer than the typical failure period.

Conclusion

In this paper, we introduce a consistency model(RPB) allowing to support both weakly consistent and strongly consistency operations. Our consistency model optimizes committing operations that need stronger guarantees than eventual consistency. The optimization is based on holding reservations that allows operations run asynchronously, while taking into account their consistency requirements. Reservation provides some permissions over data that guarantee consistency.

In our ongoing studies, we plan to implement our RPB model in geo-replicated clouds and compare it with other state of the art solutions. There are two performance criteria of interest. The first criterion is the average number of round-trip messages is needed to commit a strong operation, while the second one is the percentage of operations that can commit locally.

We are also investigating to integrate service level agreements with our reservation mechanism to satisfy the quality of services. In addition, we try to reduce the overhead of reservation control messages using forecasting techniques and provide a framework to define the reservation semantics.

  Figure 1: Reservation/purple protocol

Figure 2 :

 2 Figure 2: Server perspective of reservation-purple protocol

Hereafter we consider only updating operations. An operation may refer to a single update, or to a transaction containing several reads and updates.

This research is supported in part by ANR project ConcoRDanT (ANR-10-BLAN 0208).