H Daher

D Gaceb

V Eglin

S Bres

N Vincent

Ancient handwritings decomposition into graphemes and codebook generation based on Graph coloring

We present in this paper a new method of analysis and decomposition of handwritten documents into glyphs (graphemes) and their associated code book. The different techniques that are involved in this paper are inspired by image processing methods in a large sense and mathematical models implying graph coloring. Our approaches provide firstly a rapid and detailed characterization of handwritten shapes based on dynamic tracking of the handwriting (curvature, thickness, direction, etc.) and also a very efficient analysis method for the categorization of basic shapes (graphemes). The tools that we have produced enable paleographers to study quickly and more accurately a large volume of manuscripts and to extract a large number of characteristics that are specific to an individual or an era.

Introduction

This paper is part of the project ANR GRAPHEM 1 . It represents a methodological contribution for handwriting characterization and classification that must e used to assist the paleographers in their delicate task of writings' expertise. We are especially interested in ancient Latin manuscripts of the Middle Ages before the emergence of printing. On such manuscripts, we must face several constraints due to the bad conditions of handwriting preservation and especially of ink degradations. Furthermore, the execution rules of writing are in paleography very strict: some letters and letter combination can be only produced by a unique 1 ANR Graphem Project 2007-2010. http://liris.cnrs.fr/graphem/ dynamic movement. In our study, it is necessary to take into account all these constraints and some execution specificities of writings of the Middle Age period. In this context, our objective is to:

-Produce a decomposition of writings into coherent graphemes while avoiding some backward movement of the pen.

-Produce a robust and flexible construction of Shapes Code Books that are representative to the distribution and graphemes. We will show how these elements can be used for the recognition of the different writing styles of manuscripts. We present in the following sections the weakness of conventional methods and the principle of our approach that has been designed to be adapted to ancient handwriting documents. In details, we present:

-A decomposition approach into graphemes that is based on the detection of the center line directly on the grayscale image.

-A classification approach of graphemes by graph coloring that has never been exploited in such context.

Decomposition of manuscripts into graphemes

This decomposition is done in two steps: -The path tracing and medial axis detection, -The decomposition of the extracted path into graphemes.

Path tracing and medial axis detection

Existing methods

Nowadays there exist a wide variety of tracing and medial axis (or skeleton) detection methods of strokes.

In the literature, these methods can be grouped into four categories based on (for details see [START_REF] Daher | A New approach for centerline extraction in handwritten strokes…[END_REF]):

-Morphological thinning: thinning is to gradually remove the points of the contour shape, while maintaining its topological features. These methods require a prior binarization step of grayscale images. This can lead to a great loss of information when the documents are ancient (with poor quality) and produces degraded binary lines, broken characters, merged or biased (holes, noise) [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF] [START_REF] Maio | Direct Gray-Scale Minutiae Detection In Fingerprints[END_REF]. These degradations often distort the skeleton of the stroke and cause significant errors in stroke matching [START_REF] Suh | Stroke extraction from gray-scale character image[END_REF]. These limitations lead to other skeletonization methods that are applied directly on grayscale images, like the methods that are base on the 2D potential fields [START_REF] Grigorishin | Skeletonisation: An Electrostatic Field Based Approach[END_REF]. Such approaches require costly operations of smoothing, but they are more robust to image degradations.

-Distance transform: the distance map of an object is to associate to every point its distance to the closest edge point. The local maxima of the distance map correspond exactly to the points of the skeleton of the object. Several distances were used in this context (Euclidean [START_REF] Danielsson | Euclidean Distance Mapping[END_REF], Chamfer [START_REF] Rosenfeld | Distance Functions on Digital Pictures[END_REF], etc.) mostly applied on binary images rather than grayscale images.

-Heuristics: these methods are directly applied on grayscale images using heuristics to set a large number of parameters that manage the detection of the medial axis. They were originally developed to extract the skeleton of fingerprints and their results are clearly more robust on degraded image than the two previous families [3] [8].

-Edge detection: these methods use the edge to navigate along the lines and to detect the medial axis by correlation between a line and its two edges. In this context, they proposed an interesting iterative approach in [START_REF] Zhang | A novel tracing algorithm for high throughout imaging Screening of neuron-based assays[END_REF] that detects the center line in images of neurons. Other methods that are founded on the same principle are used for road tracing in satellite images [10] [11]. This type of methods cannot be applied easily on degraded manuscripts where the contours of strokes are often distorted and discontinuous and where the contour tracing algorithm may be lost in these parasite channels.

Our medial axis detection method

Our approach is applied directly on grayscale images of ancient manuscripts. It combines the aspects of the three previous categories cited above offering a tracking and medial axis detection of the path that is more precise and robust to degradations for this type of documents. That is why; our method combines many concepts in the same time:

-It uses the concept of Xu et al. [START_REF] Xu | An improved algorithm for vessel centerline tracking in coronary angiograms[END_REF] to be able to navigate along the strokes and to extract the medial axis without using the contours. It takes into account the change of curvature of the trajectory at each point of the path where we must find the next point. This approach ensures good robustness to discontinuities encountered in the ancient manuscripts.

-In the method of Xu et al. the user must arbitrary initialize the starting points and directions. To avoid errors related to the user we use the skeleton that is obtained by the method of Zhang [START_REF] Zhang | A fast parallel algorithm for thinning digital patterns[END_REF] to automatically place the starting points of the stroke that are to be traced in the neighborhood to the ends of strokes. Within this approach, we can automatically associate to detected points the radii values and the stroke directions.

-We improved the method of Xu by using at each point the combination of two complementary directions. a) Geometric direction to insure certain robustness to undesirable bifurcation and crossing situations. b) Intensity direction that guarantees a tracing that is robust against sudden direction changes or thickness along the lines. We also used a dynamic size window to find the next point that will belong to the medial axis. The size of this window varies automatically if the situation is a bifurcation, crossing or a straight line.

-The concept of Frangi [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF] for the detection of blood vessels has been reused in our work. Its approach has some properties that can be compared to black lines in the manuscripts. We have been inspired by Frangi's strategy for automatic, dynamic and progressive calculation of the radius at each point of the path. This strategy allows to avoid using a radius of fixed size imposed by the method of Xu [START_REF] Xu | An improved algorithm for vessel centerline tracking in coronary angiograms[END_REF] (Figure 1).

Figure 1. Line tracing and medial axis detection.

The steps of our method of tracing and detection of the medial axis are summarized in the following algorithm: Mark this point as a visited point this way it will not be visited again by our tracing algorithm.

C) Stopping Criteria

-If we find a bifurcation point and that point has already been visited, we stop the tracing process if we come at a point that is marked as starting point, and this point will be removed from the starting points list.

-Reiteration of the process along the line until a stopping criterion is met.

The following figure shows the centerline extraction results of our method. It is significantly better than that obtained by the conventional method of Zhang. We note that our method detects the medial axis even in situations where the ink is degraded or very bright.

Path decomposition into graphemes

From a methodological point of view, the segmentation of strokes is performed as follows: between each start and stop, all the points involved in the formation of a stroke will be saved in a list with their directions and the thickness. The points of minimum thickness (local minimum) are then marked and offered as a point of cutting, as it is the case in the formation of a line, see Figure 3. In this figure, each segment has a different coloration. We identify by this approach the crossing areas, the points where the feather has been raised or where the feather has been put (see zoom in Figure 3). The decomposition of Figure 3 shows that the letters are formed from adjacent fragments attached to points of minimum thickness. These points are supposed to correspond to posing and raising points.

So as to be able to build an informative shapes codebook for each handwriting of the database, we must proceed to a graphemes classification. We have been interested in an innovative clustering approach of similar graphemes by using the concept of graph coloring that has never been exploited in such context. This method does not require prior knowledge of the number of classes or prior learning and can offer good intra class homogeneity and inter class disparity. It can adapt better adapted to the nature of the graphemes, in contrast to conventional methods which require the prior introduction of many classes and the manual labeling of graphemes. During this previous steps of learning, the user can introduce errors. We can cite for example the method of Zhu [START_REF] Zhu | Language Identification for Handwritten Document Images Using A Shape Codebook[END_REF] and the method of Kumar [16] that are based on the SVM and the method of Schomaker [START_REF] Schomaker | Using codebooks of fragmented connected-component contours in forensic and historic writer identification[END_REF] that is based on the Kohonen map.

Theoretical principle of the graph coloring

Graph coloring is a very important branch of graph theory. Its applications are numerous in various scientific fields (optimization of transportation or communication networks, chemical formulas, etc.). The definitions of graph coloring are simple and real research problems can be expressed in a well structured form. This model was first introduced in the field of documents by Gaceb and Eglin [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]. They adapted it to all the steps of documents analysis (from the physical structure extraction to the recognition) to consolidate the cooperation and exchange of information between different modules. Thanks to its simplicity and its potential for classification, we can develop a novel method for codebook construction.

Types of existing coloring methods

Graph coloring is a tool that permits graph characterization. There are many types of colorations. We can mention, for example, the coloring of nodes (the one that interests us), the coloring of edges and the list coloring [START_REF] Paschos | Optimisation combinatoire5: problèmes paradigmatiques et nouvelles problématiques[END_REF]. The coloring of a graph G(V,E) is a function that affects a color to each node, and is such that two nodes that are connected by an edge (or

Modeling of the grapheme classification problem in terms of graph coloring

The main objective of the combination of a set X={x 1 ,...,x n } of graphemes into many homogeneous groups is to collect as much similar graphemes as possible, in the lowest number of classes. The grouping is based on a similarity criteria S that specifies if a pair of graphemes (x i ,x j ) can be merged into one group or not. This criterion can be based on a distance lower than a threshold. In a practical point of view, we represent each grapheme x i by a node v i ∈ V of a simple graph G and we add an edge E(v i ,v j ) between each pair of dissimilar graphemes (that do not respect the constraint S). The coloring of the nodes of G(V,E) consists in assigning to all nodes a color so that two adjacent nodes (dissimilar) can't have the same color. These colors will correspond to different homogeneous groups that represent the different classes of graphemes. In this problem of clustering, the question of determining the smallest number of homogeneous groups is equivalent to finding the smallest k for which the corresponding graph G admits k-coloring: Thus, it is precisely the chromatic number χ (G) of the graph G that we should determine.

Compared with conventional clustering mechanisms, this modeling has the advantage to easily manage several kinds of ambiguities related to the shape of graphemes.

Construction of the code books

From all graphemes extracted in section 2, we will proceed with the construction of our code book (also called similarity table).

Features extraction

Thus we produce a vectorial description of each of the graphemes, which is then processed to define the similarity criterias that are necessary for the classification. We used according to need two types of descriptors: a topological descriptor of 15 features and a descriptor of 25 Zernike Moments.

Topological features

-10 shape features were extracted from the binary grapheme images. The length and width of the grapheme are used to distinguish between the writing styles and also between the used feathers. The orientation allows to know the inclination of the grapheme and to differentiate between the various executions movements of writing. The thickness of the grapheme allows us to know the thickness of the head of the feather and the writing style. For example, in Gothic manuscripts, the thickness of the head of the feather is large while in the modern manuscripts it is small. The last three features are related to the surface that a grapheme can take in a manuscript, compared to the other graphemes.

-5 curvature features (the direction of the greatest curvature and of the least curvature, the Gaussian and mean curvatures and the laplacian of the curve) are extracted from the grayscale graphemes and are calculated by using the Hessian Matrix [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF]. They represent the shape of the curves of graphemes and reflect the structural properties such as convexity and concavity. They have an important role, because they allow us to differentiate between the style and the era of the writing.

Zernike Moments

The 25 Zernike moments used to describe the graphemes are classified as orthogonal moments (geometric, Legendre, etc...), because they possess the property of invariance to rotation. The Zernike moment ( )

∑ ∑ ⋅ + = x y nm nm V y x f n A θ ρ π , ) , ( 1 *
V nm (ρ,θ)Is a set of complex polynomials in a two dimensional space that form an orthogonal set on the interior of the unit circle (x²+y²=1), with :

( , ) im n m n m V R e θ ρ θ =
Where ρ is the length of the origin vector at the point with coordinates (x,y). θ Is the angle between the vector ρ and the x-axis. R n,m =R n,-m is a radial polynom defined as follows:

( ) ( ) ( ) ( ) 2 2 0 .! 1 ! -S ! ! 2 2 n m S n S n m S n S R n m n m S S ρ ρ - - = - = -  +   -  -         ∑
To calculate the Zernike moments, the center of the binary grapheme is taken as the origin of the coordinate system and pixel coordinates of the image are transformed in a way to be in the domain of the unit circle. As mentioned earlier, the Zernike moments are only invariant to rotation, to become invariant to scaling [START_REF] Teague | Image analysis via the general theory of moments[END_REF] we must normalize the binary image of grapheme by the first order moment m 00 defined as being the area of the grapheme.

Similarity Measure

The dissimilarity between v i and v j is given by the generalized Minkowski distance of order α (α=2: euclidean distance).

( )

1 1 ( , ) Nc k k k i j k Ds g v v α α = = ∑
Nc is the length of the feature vector. g k is the dissimilarity function that compares the features in pairs.

Graph Construction

The construction of a graph G to be colored from a set X={x 1 ,…, x n } of n graphemes (where each node vi corresponds to the descriptor vector of the grapheme x i ) and is mainly based on the computation of the matrix of distances MD s that reflect the dissimilarities Ds(x i , x j ) existing between the pairs of graphemes (x i ,x j ) given by the following equation : MDs[v i ,v j ]= Ds( x i , x j ) with i∈ [1,n] et j∈ [1,n] | (i≠j).

Once MDs is calculated, we associate to X a graph with a higher threshold G ≥S =(V=X, E ≥S ) by using the following equation:

1 si ( , ) ( , )
0 sinon

i j i j S i j Ds x x Ds v v S E , ν ν ≥ = ≥    =    
For not to confuse the term adjacency with the term similarity, it should be noted that two nodes are adjacent if they have a higher dissimilarity threshold S. The threshold S is also called adjacency threshold. This threshold can be adjusted manually by the paleographers or automatically by maximizing the quality of the classification given by ψ [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]:

Graphemes classification

Once the graph G is constructed from the set of grapheme, we apply the graph coloring algorithm of Gaceb and Eglin [START_REF] Gaceb | Improvement of postal mail sorting system[END_REF]. The resulting different colors represent the classes of the graphemes.

Results and application

We present here our grapheme decomposition method on 12 pages of ancient manuscripts from different types. The following set of 4863 graphemes summarizes the number of graphemes obtained by each page: {p1=343, p2=583, p3=643, p4=248, p5=398, p6=528, p7=564, p8=316, p9=499, p10=193, p11=269, p12=279}. This decomposition has been subject to the validation of the paleographers and has obtained their approval.

The following figure shows a sample of the codebook that was constructed from the graphemes of page 12 by graph coloring (see Section 4). It is quite clear that the graphemes that represent the same motion of the feather are grouped in one class. To recognize the style of the manuscripts: each of the 12 manuscript pages pi will be represented by its codebook cb(p i ) of k i classes of graphemes (k i is the chromatic number of the graph coloring) with Where dc is the distance between two classes of graphemes and it is given by: The distances dp between the twelve pages are illustrated table1. We can estimate from table 2 that the style of page 7 is the closest to the one of page 1 and the style of page 2 is the closest to the style of page 10 and so on.

Conclusion

We have presented in this article new methods for handwriting decomposition into graphemes and a robust codebook that is well adapted for the demands of our field. Applying these different methods, we succeed to automatically recognize the style and era of the manuscripts presented in this set of test.

Ψ

  starting points by using the skeleton of Zhang, -Extract their radius, -Start from one of the points of departure, -Determine the next point 0 1 k P + by using dk (Look ahead Distance ), -Compute its direction 0 1 k+ Ψ , b) Determine the next point and adjust its position -Draw a density profile 1 . Matched filtering is applied to the profile to obtain the center point 0 1 k P + and the tracking direction is updated to 1 1 k+ Ψ , this point will have the value of the radius that was computed previously. -Proceed in the same way by computing the density profile at the point 1 1 k P + , focal point in the centerline, and compute its direction 1 k+ Ψ , -

Figure 2 .

 2 Figure 2. Medial axis extraction by, (a) our method, (b) binarisation by using sauvola, (c) the method of zhang,

Figure 3 .

 3 Figure 3. Example of strokes decomposition into graphemes by our method.

  do not have the same color ( property constraint). The colors (or integers) assigned to the nodes of the graph are only used to group the nodes into classes.

Figure 4 .

 4 Figure 4. Construction states of the codebook by graph coloring.

  with the repetition m (n-|m| is even and |m|<n) is defined by:

Figure 5 .

 5 Figure 5. Invariance to rotation of the 25 Zernike moments (n = 8).

  a rg m a x ( ( )} O p tim a l i S S ψ =

Figure 6 .

 6 Figure 6. Samples of the 12 manuscripts.

Figure 7 .

 7 Figure 7. A Sample of page's 12 codebook.

1 (

 1 can estimate the similarity between each pair of pages (p i ,p j ) by the following distance dp:

Table 1 . The distances between the codebooks of the 12 pages.

 1

		1	2	3	4	5	6	7	8	9	10	11	12
	1	0
	2	0.7145	0
	3	0.391 0.459	0
	4	0.3063 0.679 0.3464	0
	5		0.596 0.3353 0.2483	0
	6	0.5464 0.391 0.7943 0.5372 0.4591	0
	7	0.127 0.422 0.3173 0.3419 0.1755 0.3867	0
	8	0.4871 0.448 0.8065 0.5029 0.5351 0.5487 0.2362	0
	9	0.7056 0.231 0.8526 0.7685 0.6276 0.4637 0.4141 0.7529	0
	10 0.8062 0.206 0.728 0.6466 0.6261 0.4637 0.1435 0.7122 0.153	0
	11 0.3437 0.597 0.2586 0.1511 0.2446 0.1863 0.208 0.3852 0.555 0.5772	0
	12 0.3413 0.603 0.3659 0.1331 0.2381 0.3868 0.1741 0.3883 0.589 0.6152 0.2295	0


PHD student H Daher
email: hani.daher@insa-lyon.fr

N Vincents

Senior lecturer V Eglin

S Bres

A New approach for centerline extraction in handwritten strokes: An Application to the constitution of a code book

Keywords: I.5.3 [Pattern recognition]: clustering -similarity measures Algorithms, Measurement, Documentation, Performance, Design, Experimentation, Human Factors Handwriting images, medial axis location, Hessian matrix, handwriting codebook

To obtain a good decomposition of handwritten strokes in manuscript images, the extraction of the medial axis represents a very important step. In this paper, we propose an automatic approach for the extraction of the median axis directly from the gray level images. This approach is based on the orientation and the stroke thickness analysis at different points of the handwritten shapes. This method is robust to degradations of the strokes, background noise and ink irregularities in the support paper. Then, we propose to consider all graphemes and to classify them from the analysis of median axis points. We use this decomposition to produce an identification scheme from various handwriting styles. This work is supported by the ANR GRAPHEM project.

INTRODUCTION

The extraction of the centerline of lines contained in images represents a very important step in many research fields. For example in bioinformatics, the medial axis is used to follow a blood vessel or neurones. In fingerprint analysis, the medial axis is extracted to identification purposes. In satellite image analysis, the medial axis is used for road extraction. In manuscript image analysis, the centerline extraction represents a very important characterisation step that will allow us to compute the stroke thickness, to construct a graph that represents a specific shape or to decompose the strokes that form a letter. In this paper, we are interested in ancient Latin manuscripts from the Middle Ages. In this type of manuscripts we are faced to many problems such as the aging material and ink. In this paper, we propose to extract the centerline directly from the gray scale image, while the literature contains a lot of approaches that perform a binarization as an initial step making the localisation of the stroke easier. Thus, we differ from the methods used today by avoiding the conventional approaches that perform a thresholding and skeletonization of the image. There exist a lot of approaches in this domain that can improve the quality of the binarization and skeletonization algorithms. These methods give good results on regular or less degraded documents. But faced with problems of the aging ink and often poor quality of the documents, such approaches are not really suitable. This paper is organized as follows, section 1 introduces the different concepts of our study and presents the major contributions in the literature in relation with the skeletonization aspect and the extraction of the medial axis in handwritten strokes. Section 2 describes our major contribution in three sections: at first we will present the original algorithm of the ridge line following and we will validate it with respect to the performances that are estimated from the other skeletonization approaches that are most frequently used in the literature.Later on, we will describe in detail our stroke segmentation approach that is based on the stroke thickness which in turn is estimated at each point of the centreline. This section is followed by the construction of a code book from the segmented strokes by using the following features: the standard deviation of the orientations at each point of the centerline and their main directions. In section 3 we will show how the constitution of a codebook for every manuscript might be used in the comparaison of handwritings by analyzing the variability between writers. To conclude this work, the section 4 gives a general overview of the decomposition and the analysis tool of the writings that we have chosen to focus on the centerline and announce the short-term prospects of these contributions.

LITERATURE REVIEW

In this section we will present the previous centerline extraction methods:

-Morphological thinning: thinning is to gradually remove the points of the contour shape, while maintaining its topological features. These methods require a prior binarization step of grayscale images. This can lead to a great loss of information when the documents are ancient and of poor quality [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF] [2] and thus produce degraded binary lines: broken characters merged or biased (holes, noise). These degradations often distort the skeleton of the strokes and cause significant errors in their matching [START_REF] Suh | Stroke extraction from gray-scale character image[END_REF].

-Vornoï diagram: the skeleton of a continuous form is included in the Voronoi diagram points on its border [START_REF] Schmidt | Some ex. of algo. analysis in comput. geometry by means of math. morphology techniques[END_REF]. This approach is defined in a continuous space and produces a connected skeleton. The disadvantage of such methods comes from the difficulty of the sampling of contours that define the quality of the Voronoi diagram and the decomposition of the branches with the help complex stages of post-processing [START_REF] Attali | Squelettes et graphes de Voronoi 2D et 3D[END_REF].

-Distance Transform: the distance map of an object is to associate to every point its distance to the closest contour point. The local maximums of the distance map correspond exactly to the points of the skeleton of the object. Several distances were used in this context (Euclidean [6] [7], Chamfer [START_REF] Rosenfeld | Distance Functions on Digital Pictures[END_REF], etc. mostly applied on binary images and also on grayscale images. With these methods the extraction of the skeleton is very sensible to the deformations of the contours that we usually encounter in our images.

-Heuristics: these methods are applied directly on grayscale images using heuristics to set a large number of parameters that manage the detection of the medial axis. They were originally developed to extract the skeleton of fingerprints and their results are clearly robust and effective on degraded image than the two previous families [2] [9] We can also find the approaches in the domain of medical imaging as the work of Sun [START_REF] Sun | Automated identification of arterial contours in coronay arteriograms by an adaptive tracking algorithm[END_REF] that represented a geometric algorithm of line tracing on X-Ray images. This algorithm is known under the name of "Sun Algorithm". [START_REF] Aylward | Initialization, noise, singularities, and scale in height ridge traversal for tubular object centerline extraction[END_REF] adapted this principle to tubular objects (blood vessels) on 3D grayscale images. The main disadvantage of this method is the absence of self adaption to changes in direction, the diameter and to overlapping and crossing problems of blood vessels or the lines on degraded images.

-Contour detection: These methods use the contour to navigate along the lines and to detect the medial axis by correlation between a line and its two edges. In this context, an interesting iterative approach proposed in [START_REF] Zhang | A novel tracing algorithm for high throughout imaging Screening of neuron-based assays[END_REF] to detect the center line in images of neurons. Other methods that are founded on the same principle are used for road tracing in satellite images [START_REF] Peteri | Detection and extraction of road networks from high resolution satellite images[END_REF] [START_REF] Poz | Automated extraction of road network from medium and high-resolution images[END_REF].

-New technologies have emerged including the wavelets [START_REF] Xinge | Skeletonization of Character Based on Wavelet Transform[END_REF], the partial differential equation (PDE) using diffusion fields [START_REF] Cheriet | Amincissement-sans-segmentation et rehaussement des images de niveau de gris par un filtre de chocs utilisant des champs de diffusion, I-Revues[END_REF], and the 3D approach [START_REF] Sanniti | 2D Grey-level Skeleton Computation: A Discret 3D Approach[END_REF]. These two approaches can skeletonize a grayscale image and avoid all the limitations related to the skeletonization of binary images. Such approaches require multiple iterations of smoothing, but it is more robust to degradations.

CENTERLINE EXTRACTION

Our approach is directly applied on grayscale images of ancient manuscripts. It combines the aspects of the previous categories cited above offering a flexible tracing and a more precise detection of the mexial axis and robust to degradations. This is why we were insipired by the different skeletonization methods of blood vessels in medical images [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF] [START_REF] Xu | An improved algorithm for vessel centerline tracking in coronary angiograms[END_REF]. The blood vessels have comparable properties to the ones of the black lines in handwriting this is why our methods was based on this type of methods.

-It uses the concept of Xu et al. to be able to navigate along the strokes and to extract the medial axis without the need of the contours. It takes into account the change of curvature of the trajectory at each point of the path where we must find the next point. It ensures good robustness to discontinuities encountered in the ancient manuscripts.

-It reinforces this tracing by the automatic initialization of the starting points of line tracing method, the closest possible to the ends of lines. In the method of Xu et al. the user must arbitrary initialize the starting points and directions. To avoid errors related to the intervention of the user and the difficult task of manual initialization, we use the skeleton that is obtained by the method of Zhang and Suen, [START_REF] Zhang | A novel tracing algorithm for high throughout imaging Screening of neuron-based assays[END_REF]. This can also automatically associate to these points the radii and directions that are obtained by the method of Frangi.

-The part of the Frangi method that we use corresponds to the automatic, dynamic and progressive computation of the lines direction and the radius at each point of the path. These properties allow us to avoid the errors that are related to the manual choice of the directions and to avoid the rigidity of the tracing during the use of the fixed size radius imposed by the method of Xu et al.

-We improved the method of Xu et al. by using at each point the combination of two complementary directions. a) Geometric direction to insure certain robustness to undesirable bifurcation and crossing situations. b) Intensity Direction that guarantees a tracing that is robust against sudden direction changes or thickness along the lines. We also used a dynamic size window to find the next point that will belong to the medial axis. The size of this window varies automatically depending if the situation is a bifurcation, crossing or a straight line.

Preprocessing

This part is to explain the various stages of pre-processing that have been applied on images before moving on to the stage of feature extraction. In this step, we use the method of Frangi [START_REF] Frangi | Multiscale Vessel Enhancement Filtering[END_REF]. This method has the advantage of preserving the different structures of the image, even the images that represent degraded structures. In our work, our contribution addresses the extraction of the centerline in black lines that have similar properties fto blood vessels. This approach will particularly enable us to calculate the radius at each point of the image and will be used to decompose the characters into distinct fragments. To initialize the method, we proceed to a convolution of the image with the classical second derivative of Gaussian Gxx, Gxy, Gyy. Then, we construct the Hessian matrix: the authors showed that eigenvalues of the Hessian matrix that verifies the following properties

                  - -         - = 2 2 2 2 0 2 exp 1 2 exp 0 ) ( c S R s V β β Where V 0 = 0 for 0 2 > λ , 2 1 λ λ β = R , 2 1 λ λ + = s , c which
is the norm of the hessian matrix (Frobenius) and beta are used to control the sensibility of the filter, the ratio β R represents the eccentricity. The norm s (Second order structureness) is small when we are in the background with eigenvalues individually small for the lack of contrast. In regions with strong contrast this norm will increase will increase with the presence of at least one of the eigenvalues with greater amplitude. For each value of sigma, we have for each pixel of the image, a matrix that contains the values of the function V0 that are represented byψ . We do the same for the maximum Eigen values 2 λ , and for the directions that are calculated from the eigenvectors . After having constructed the different matrices for each sigma we compare the values ofψ . The maximum value of ψ for each pixel will allow us to extract the maximum value of sigma that represents the value of the line thickness on a given point, if for example the maximum value of ψ is the one of 1 σ then the radius will be equal to 1 σ .

Extraction of the starting points

For the identification of starting points, we extract the skeleton using the method of Zhang and Suen [START_REF] Zhang | A fast parallel algorithm for thinning digital patterns[END_REF] and we locate the end points of the strokes in the skeleton. These points will correspond to the starting points if each segment and we will be extracted them by using the following approach:

          = 0 0 0 0 1 0 0 s
The structuring element s was applied on the skeleton by using the hit and miss operator. s was used in each of his 45° of rotation. These points will serve as starting points for our method of extraction of the medial axis. These points will contain: the principal direction and the thickness of the stroke (see Figure 1). -Proceed in the same way by computing the density profile at the point 1 1 k P + to find the point P k+1 , focal point in the centerline, and compute its direction

1 k + Ψ ,
-Mark this point as a visited point, this way it will not be visited again by our tracing algorithm.

c) Stopping criteria

-If we find a bifurcation point and that point has already been visited, we stop the tracing process if we come at a point that is marked as starting point, and this point will be removed from the starting points list.

-Reiterate the process along the ling until a stopping criterion is met.

Tracking direction

To compute the tracking direction we used a combination of both the geometric direction and the intensity direction. By using a single type of direction, we might have been confronted with difficulties related to sudden changes of direction or diameter (thickness) at different points P calculated from the centerline and which are related to overlapping or superposition of strokes or degradation of the image. The geometric direction is defined as the direction of the current point to the new point. It is estimated and corrected. The successive estimations and corrections, for each point The geometric direction, as indicated by the name, is largely determined by the vessel's geometrical topology. When there is, for example, an abrupt change in curvature from k P to 1 + k P , tracking using geometric direction alone, may cause great deviations. To solve this problem we combined the geometric direction with the intensity direction. The Hessian matrix is defined as follow:

      = Iyy Iyx Ixy Ixx H
Where uv I represent the convolution of the image with a second order derivative Gaussian function. From the Hessian matrix we will extract the eigenvalues. Considering that the strokes are darker than the background, we define the intensity direction as the Hessian eigenvector corresponding to the smaller eigenvalue. The direction of sequential tracking is maintained by multiplying the Hessian eigenvector by the sign of the dot product of it and the current tracking direction k ψ ,that the obtained intensity direction always points to the subsequent sections along the vessel. Let 1 λ and 2 λ be the eigenvalues of the Hessian at point

Look ahead distance

The look-ahead distance is used in the estimation step of the ) (

1 - ∧ ∧ - ∠ = k k k ψ ψ θ .

Intensity profile and dynamic search window

Matched filtering is used in the correction step to obtain the new centerline point. A point on the intensity profile whos filtering output reaches maximum is identified as the centerline point. For matched filtering, the search window size plays an important role. The main idea of using a window size is dynamically is to cope with different geometric configurations that may be encountered during the line following algorithm. In regular cases we have

k R T * = 5
. 1

, such a window size also would allow distortions and inflexions to be adequately dealt with. In a bifurcation case we will have k R T * = 4 so that both the strokes are included in the search range. As a result, a centerline point on one stroke would be identified anyway and the tracking procedure would continue along that stroke. In order to determine the type of geometrical configuration for a new centerline point, we assume a two-step approach; at first we try to distinguish the overlapping situation from the other cases. We first introduce a normalized gray scale parameter τ for each centerline point. , where 0 τ represents the value of τ in the previous segment. In our case we used

5 . 1 = β . When 0 1 βτ τ ≤ + k
the situation is considered to be either normal or bifurcation, and it is further classified using the previous radius

information 2 - k R , 1 + k R , and k R . If k k k R R R ≤ ≤ - - 1 2
, which means that the stroke under investigation is becoming wider, the situation is considered to be bifurcation; Otherwise, the situation is considered to be normal. In Figure 1(a) we considered the situation of intersection encountered in the manuscripts and the situation of degradation of the ink. One can see that the approach is efficient for the extraction of the centreline where the ink is the most degraded.

Similarly, in figure 1(b) we can notice that the centreline extraction is correct in the writing especially on the part where the ink impregnation is very bad. We tested the algorithm on medieval manuscripts in which the strokes are degraded and it is difficult to extract with a standard skeletonization algorithm. In Figure 3 we present the results of the extraction of medial axis in our approach. The first column contains the results of our method.

One can see that we could extract the medial axis even in situations where the ink was degraded. The second column represents the result of binarization by the method of Sauvola chosen because it gave better results on the degraded ancient documents, [START_REF] Stathis | An evaluation survey of binarization algorithms on historical documents[END_REF]. For skeletonization, we used the method of Zhang and Suen [START_REF] Zhang | A fast parallel algorithm for thinning digital patterns[END_REF] which is very efficient in computation time and robustness to noise. In total, we tested more than 8 skeletonization methods that provided noisier and less accurate results in terms of location of the skeleton than the method of Zhang. If we compare the results obtained by skeletonization with our results, we can see that the degraded strokes have disappeared, which will cause an important loss of information. We can see that the result of locating the medial axis allows a very precise localisation of the end of strokes that are confused with the background, compared with a binary or grayscale skeletonization which often truncates the late forms inadequately contrasting.

GRAPHEMES EXTRACTION METHOD

In paleography, the implementing rules of writing are very strict because of the high specificity of feathers and arrows, used to produce shapes, some letters and letter combination can be produced only by a single dynamic execution. It was therefore necessary in this study to take into consideration the specifics of implementation to produce a coherent decomposition of forms, including avoiding certain gestures cusp (backward movement of the pen). From a methodological point of view, the segmentation of strokes is performed as follows: between each start and stop, all the points involved in the formation of a stroke will be saved in a list with their directions and the thickness. The points of minimum thickness (local minimum) are then marked and offered as a point of cutting, as is the case in the formation of a line, see Figure 5.

In this figure, each segment has a different coloration. We identify by this approach the crossing areas, points where the feather has been raised or where the feather has been put (see zoom in Figure 4). The decomposition of Figure 4 shows that the letters are formed from adjacent fragments attached to points of minimum thickness assumed to correspond to the points of raising and posing of the feather. This decomposition has been subject to the validation experts paleographers and has obtained their approval.

CONSTRUCTION OF THE CODEBOOK

From all glyphs extracted from the previous step, we will proceed with the construction of our code book. Thus we produce a vectorized description of the glyphs, which is then processed to define the criteria of similarity. We have chosen to differentiate ourselves from the texture characterization approaches that are commonly used on homogeneous blocks of text, [23] [22], or from the differential characterizing approaches [START_REF] Lee | A new methodology for gray-scale character segmentation and recognition[END_REF]. We have focused on analyzing the glyphs individually. The choice of characteristics is a key point for the final quality of the algorithm.

Because graphemes can have variable sizes, the next step is to describe the images by a vector of characteristics of fixed dimension. The estimates of these descriptors are translated into real values and each is supposed to describe a property of forms such as:

•The roundness of the glyph (curvature vs. linearity).

•The size of the glyph ( width,height)

•The area occupied by black pixels

•The direction of the glyph (dominant orientation)

•Deviation of directions

•The average thickness of horizontal and vertical lines (these values are estimated on the entire image).

•The average number of horizontal and vertical lines ( transition between black and white pixel on a column of the image)

•The maximum curvature

We consider each glyph of the image to be represented by a vector of characteristics consisting of the ten previous descriptors. These descriptors define a feature space where each glyph is represented by a point. For the classification of glyphs, we chose the algorithm of K-means. The final position of the centers of classes given by the K-Means will represent a signature for a given document. For the compilation of this code book, the number of classes is fixed before the classification stage. We used 25 classes for the classification of documents that are presented in this article.

COMPARAISON EXAMPLES

To illustrate this distance and the estimation of the similarity of document or writing, we present in Table 1 below the estimated distances between different samples extracted from handwriting documents of 4 classes. The documents in classes 1, 3 and 4 come from the same period but have been written by different writers. The distance between samples is a great indicator of visual similarity between writing family. Figure 5 below shows a copy of each of these 4 classes. The first image (top right) shows a copy of Class 1, the second shows us a copy of Class 2 and so on.

Comparaison table between the 4 classes

In Table 1, we have projected the distance between the various documents. C xy refers to the document y of the class x. From these values we can deduce that documents of the same class have a greater similarity (lowest distance) that documents from different classes. In addition, documents of class C 2 have a lower similarity with other classes, which verifies our hypothesis that the class C 2 is a time and a writing style very different.

CONCLUSION

We showed that our method of medial axis extraction gives better line following results than the conventional methods of skeletonization which still allowed us to save time in the analysis and to work directly on the complete non threshold shapes (no binarization steps). Degraded strokes were taken into account in our method and we were able to extract the centerline in areas where it is difficult to do with the other methods. Similarly, our method allowed us to work directly on grayscale images without going through the stages of preprocessing, which still allowed us to save time in the analysis. With the segments that are extracted, we construct a set of glyphs that we regroup in a codebook by class similarity. These classes are then used as the signature of each document. We mainly use this method for classification of ancient documents, depending on their origin and type of writing class. However, we are also testing an extension of this algorithm on modern manuscripts, for which the decomposition glyphs pose specific problems and where objective is to identify the writer of the document.

Figure 1 .

 1 Figure 1. (a) The Look-ahead distance d k between the points P k and P k+1 , (b) Line tracing and extraction of the medial axis[24].

  the ideal structure of a black line. The value of the radius is then computed to maximize the function V 0 defined as follows: The function V 0 is a product of exponential functions according to different scale values s (sigma).



Figure 2 .

 2 Figure 2. Example of starting points 3.3 Stroke tracing algorithm The steps of our method of tracing and detection of the medial axis are summarized in the following algorithm: a) Initialization -Detect the starting points by using the skeleton of Zhang, -Extract their radius, -Start from one of the points of departure and determine the next point 0 1 k P + by using k d « Look ahead Distance », and compute its direction 0 1 k + Ψ , b) Determine the next point and adjust its position -Draw a density profile 1 k g + perpendicular to the direction of the

  Image degradation and overlapping strokes, makes the intensity distribution to exhibit rather complicated proprieties and hence tracking in virtue of the intensity direction alone would encounter great difficulties. In our proposed algorithm, tracking directions are updated using a weighted combination of aforementioned geometric directions and

.θθ

  The look-ahead distance is adapted to the change of curvature encountered in the strokes. It is defined as follows: stand for the direction difference between the current and previous centerline points on the current trace segment.k Provide the information of curvature change on the local stroke segment. When the curvature change is small, the value of k θ is small, and vice versa.

Figure 3 .

 3 Figure 3. Centerline extraction example (crossing and ink degradations)

Figure 4 .

 4 Figure 4. Medial axis extraction by, (a) our method, (c) the method of Zhang, (b) binarization by the method of Sauvola,

Figure 5 .

 5 Figure 5. Decomposition of segments into graphemes

Figure 6 .

 6 Figure 6. Classification of the graphemes into 25 clusters Each document is then represented by its code book of at most 25 clusters. We estimate the similarities between documents described by means of these signatures by computing a distance between the signatures. The distance d (D 1 , D 2 ) between D 1 and D 2 is calculated by the distance of each of the centers of the 25 clusters of D 1 to the nearest neighbour of the centers of D 2 . The distance d (D 2 , D 1 ) between D 2 and D 1 is most often different. We take as symmetric distance between D 1 and D 2 , the larger of the two distances d(D 1 , D 2 ) and d(D 2 , D 1 ). document D 1 is represented by n1 centers of classes (barycenters) 1 i C and D2 is represented by n2 centers of classes (barycenters)

Figure 7 .

 7 Figure 7. Example of 4 classes of manuscripts.


Compound-specific isotope analysis for assessing sources and fate of aromatic hydrocarbons in contaminated aquifers

Michaela Blessing, Eric Proust, David

Compound-specific isotope analysis for assessing sources and fate of aromatic hydrocarbons in contaminated aquifers Michaela Blessing*, Eric Proust, David Widory Bureau de Recherches Géologiques et Minières (BRGM), MMA-ISO, Orléans, France Organic compounds deriving from industry, oil spills, improper disposal and/or leaking storage tanks, landfill leachates, household use, motor vehicle emissions as well as agricultural fertilizers and pesticides are responsible for widespread soil and aquifer pollution. The fate and behavior of such compounds in the subsurface depend on a number of physicochemical and biological processes, which may lead to 'natural attenuation'. Determination and quantification of these processes are crucial for contamination risk assessment and sustainable groundwater management. Compoundspecific isotope analysis (CSIA) by online-coupling of capillary gas chromatography and isotope ratio mass spectrometry (GC-IRMS) offers a versatile tool to study the origin and to assess degradation processes of organic pollutants in the environment.

The aim of the present work is to demonstrate the potential of CSIA for studying sources and fate of aromatic hydrocarbons in aquifer systems. Headspace solid-phase micro extraction (hsSPME) was applied as sample pre-concentration and extraction technique allowing for compound-specific carbon and hydrogen isotope analysis (δ 13 C and δD) of volatile compounds, even at concentrations in the low ppb-range. The analytical approach was thoroughly evaluated in terms of its precision, linearity and reproducibility.

Our study focuses on carbon and hydrogen isotope fractionation of aromatic hydrocarbons such as benzene and toluene (BTEX), and the possibility how to evaluate biodegradation processes in situ according to the Rayleigh-equation. Results obtained at sites with two different contamination scenarios will be presented: The first location is situated at a former coal carbonization plant; the second site represents a typical contamination due to a leaking underground storage tank at a fuel station. In addition to the possibility for assessing the extent of biodegradation of organic contaminants in soil and groundwater systems, we will demonstrate how isotope signatures can help revealing different pollution sources. Limitations and challenging aspects of the method will be critically addressed. *m.blessing@brgm.fr, BRGM Orléans, MMA-ISO, 3 Avenue Claude Guillemin, BP 36009, 45060 Orléans cedex 2, France.


André Lage Freitas

Nikos Parlavantzas
email: nikos.parlavantzas@irisa.fr

Jean-Louis Pazat
email: jean-louis.pazat@irisa.fr

Cost Reduction Through SLA-driven Self-Management

A main challenge for service providers is managing service-level agreements (SLAs) with their customers while satisfying their business objectives, such as maximizing profits. Most current systems fail to consider business objectives and thus to provide a complete SLA management solution. This work proposes an SLA-driven management solution that aims to maximize the provider's profit by reducing resource costs as well as fines owning to SLA violations. Specifically, this work proposes a framework that comprises multiple, configurable control loops and supports automatically adjusting service configurations and resource usage in order to maintain SLAs in the most costeffective way. The framework targets services implemented on top of large-scale distributed infrastructures, such as clouds. Experimental results demonstrate its effectiveness in maintaining SLAs while reducing provider costs.

I. INTRODUCTION

Service-based systems are built by integrating looselycoupled services from a range of providers. To handle varying service loads, providers are increasingly taking advantage of large-scale distributed infrastructures, such as clouds and grids, which deliver remote resources in a flexible, on-demand fashion. A major challenge for service providers is managing such infrastructures in order to meet their business objectives while maintaining conformance to service-level agreements (SLAs) with customers.

A large part of the research on SLA management in serviceoriented architectures (SOAs) targets composite services; that is, services composed of simpler services, and thus shielded from the details of the underlying infrastructure. SLA management in this context typically involves replacing services by more suitable ones [START_REF] Irmert | Runtime adaptation in a service-oriented component model[END_REF], [START_REF] Consortium | Taxonomy of Adaptation Principles and Mechanisms[END_REF]. Such work does not address how basic, atomic services guarantee QoS properties, which invariably requires managing the underlying distributed infrastructure, and is the focus of this paper. A significant amount of work has focused on SLA management for large-scale distributed applications, such as e-science applications deployed on grids, or multi-tier enterprise applications deployed on clusters [START_REF] Hasselmeyer | Towards SLA-Supported Resource Management[END_REF], [START_REF] Benkner | A Generic QoS Infrastructure for Grid Web Services[END_REF], [START_REF] Antonio | SLAWs: Towards a Conceptual Architecture for SLA Enforcement[END_REF]. However, such work does not address meeting the business objectives of service providers, such as maximizing profit.

This paper proposes a generic framework to assist service providers in honoring SLAs while reducing the costs of infrastructure usage. The proposed framework integrates a rich set of QoS management mechanisms supporting the complete SLA life-cycle, from SLA template creation to service termination. To manage infrastructure usage, the framework builds on a simple interface, compatible with modern grid and IaaS cloud APIs. To accommodate fluctuating service loads and unpredictable failures, the framework includes flexible support for self-adaptation in the form of multiple interacting control loops. Importantly, the control loops build on replaceable adaptation strategies, which can be combined in multiple ways, thus extending the applicability of the framework.

The rest of the paper is structured as follows. Section II introduces the Qu4DS (Quality Assurance for Distributed Services) framework while its adaptation strategies are exposed in Section III. Section IV discusses aspects of service provisioning, how Qu4DS profiles service providers and the assumptions on which it relies. Next, the Section V explains implementation details along with the service provider flac2ogg. Section VI discusses about the evaluation, its environment and the results. Ultimately, related works are commented in Section VII followed by the conclusion in Section VIII.

II. QU4DS

A. Architecture

Qu4DS main goal is to provide SLA self-management that minimizes service provider's costs. Costs mean the payment of fines due to SLA violations, i.e. requests abortions, and the price for using the infrastructure. In order to decrease the costs on resource acquisition, Qu4DS shares the pool of booked resources among distinct contracts. With respect to minimizing fine payments, Qu4DS chooses the more suitable request to be aborted to handle the lack of resources and it manages the execution of treating requests by ensuring the agreed QoS. In order to deal with the environment dynamism, Qu4DS takes advantage of self-adaptation mechanisms based on strategies that reacts to certain events at runtime. Additionally, even though these features help on improving the service reputation, their most important advantage is the impact on increasing the service provider profit.

The Qu4DS architecture is described by Figure 1. Based on the cloud architecture layers, Qu4DS places itself in the PaaS (Platform as a Service) layer by using resources from an IaaS (Infrastructure as a Srevice) provider in order to provide a support to the upper SaaS (Service as a Service) layer. In the SaaS layer, customers contact the Web Service (WS) in order to establish a contract. The contract proposal is forwarded to the SLA Negotiator that asks the QoS Translator to translate its QoS to the resource configuration able to ensure such QoS. The SLA Negotiator then checks through the infrastructure management interface whether the resource requirements can be met. If so, the SLA Negotiator configures and deploys the service instance on the infrastructure through the job management interface and commits the contract agreement to the right customer which is now able to send requests.

When a customer sends a request, the SLA Negotiator asks the request arrivals control loop whether it can be treated. If so, the SLA Negotiator forwards the request to the right service instance deployed on the infrastructure. The service instance prepares the distributed tasks necessary to treat the request based on its configuration and asks Qu4DS to execute the tasks. These tasks are also deployed by Qu4DS on the infrastructure through the job management interface and monitored by the job faults and job delays control loops. If their executions are successful, Qu4DS answers the service instance the result of the tasks which are used to finish the request treatment. As follows, the instance tells Qu4DS that the request is treated and it forwards the result to the right customer. If any of the control loops informs that the request could not be treated, the SLA Negotiator aborts the request, tells the customer about such SLA violation and computes the penalties.

B. Interfaces

Qu4DS interacts with the underlying infrastructure through the infrastructure management interface. As this interface abstracts over operating systems images, it can be easily implemented on top of existing IaaS cloud APIs, which provide operations to create and manage virtual machine (VM) instances. The infrastructure management interface is as follows: Qu4DS is then allocated at the PaaS layer, however it is still useful to define a higher-level interface to let it manage service instances on top of the bare IaaS resources. Thereby we define a job management interface based on SAGA (Simple Grid API) [START_REF] Goodale | Saga: A simple api for grid applications -high-level application programming on the grid[END_REF]. This interface leverages the job abstraction and defines the operations over them as well as callbacks for monitoring purpose. The abstraction level, the operations and the job life-cycle (Cf. Figure 2) were extended from the SAGA Task Model. Moreover, we assume that the VM images deployed on the IaaS layer include an implementation of the job management interface. The job management interface exposes the following operations:

• InfraJob createJob(InfraJobDescription jobDescription) Creates a job based on a description whose only mandatory attribute is the binary file to be executed.

III. SELF-ADAPTATION

The employment of adaptation mechanisms depends on the Qu4DS request life-cycle which is described by Figure 3. When a customer sends a request, a request is created containing information about its SLA and further dynamic information as the input data. Its state is automatically set to NEW and Qu4DS decides whether it can be treated or not. If it cannot be treated, it gets an ABORTED state. Else, the request is set to TREATING and keeps that state untill the end of the request treatment. If the request is successfully treated, it is then considered TREATED, otherwise it is ABORTED. Additionally, during the request treatment, Qu4DS registers information about request abortions in order to compute the penalties subsequently. driven by request arrivals events and is then applicable to NEW requests. It is in charge of checking whether this just-arrived request can be treated or not. The request arrivals control loop asks the QoS Translator the request resource requirements and then checks their availability with the infrastructure. If the resource requirements can not be met, the control loop decides if it will abort this request or another request that is being treated and is able to free enough resources to fit the resource requirements.

The other control loops ensure the proper execution of requests and operate over TREATING requests. Indeed, these control loops act as self-healing mechanisms in order to prevent SLA violations. While the job faults control loop reacts to job faults events by providing reliable request treatment, the job delays control loop reacts to job delays and ensures performance aspects of the request treatment.

In addition, the control loops take decisions based on the adaptation strategy to which each control loop is configured. The adaptation strategies are thus driven by high-level guidelines which are summarized as minimizing the service provider cost on fine payments. Thereby, we have designed the following adaptation strategies described in Table I

IV. COST-REDUCED SERVICE PROVISIONING

A. Service-Level Agreement

We compiled a basic SLA scheme based on common aspects of current SLA specifications [START_REF] Andrieux | Web Services Agreement Specification (WS-Agreement)[END_REF], [START_REF] Ludwig | Web Service Level Agreement (WSLA) Language Specification[END_REF] as followed exposed. The SLA templates are thus created by filling the values of priority, th, x. The collected information includes the proper response time threshold (rp threshold ) to process a given amount of data d, the job execution time threshold (j threshold ) and the calculation of both standard deviations rp st dv and j st dv respectively. The first metrics calculated by the QoS Translator is the job execution time threshold j threshold which is defined in the following equation where e 1 and e 2 are adjusting coefficients:

j threshold = e 1 × j mean + e 2 × j st dv (1)
Then it calculates the request response time rp threshold . It represents the response time threshold that should be ensured to not imply an SLA violation since if the request elapsed time r etime is greater than rp threshold , then the request is aborted. Next, rp threshold is defined where ad overhead is a fixed time in seconds to consider the overhead due to adaptation actions during request treatment.

rp threshold = rp mean +rp st dv +ad overhead +j threshold (2)
As follows, it sets the adaptation threshold ad threshold which defines if there is still enough time to trigger an adaptation action:

ad threshold = rp mean + rp st dv (3)
Ultimately, the QoS Translator calculates the throughput th in the following equation where d is the size of the data used to profile:

th = d rp threshold (4)

C. Assumptions

Service provisioning depends on how the service provider business model which includes defining the SLA prices and fines. In order to model such requirements, let us rely on the following assumptions and equations that define details of the service provisioning.

Assumption 1: The service provider's profit is given by the difference between its total revenue and total costs on fine payments and infrastructure utilization.

Based on Assumption 1, the Equation 5 defines the service provider's profit P t given an operational time t. The nt i=0 p i is the sum of provider's revenue from all agreed contracts where n is the total number of contracts and p i is the total revenue of a contract in such a way that p i = p type +p priority , where p type is the price of a contract whose SLA type is type and p priority is the price of the priority chosen by p i . Let us define the set F t as the set of all fines during t where f k ∈ F , hence |Ft| k=1 f k means the sum of all the fines the service provider has to pay during t. Last, c t × a t is the total cost for all booked resources during t where c t is the price for using a single resource during t and a t is the total amount of booked resources.

P t = nt i=0 p i - |Ft| k=1 f k -c t × a t (5)
Assumption 2: If all requests are violated, the service provider will make zero profit.

Let us define the Equation 6 which calculates the maximum frequency a customer can reach by means of number of requests during the contract duration t for contract i :

φ maxi = t rp i threshold (6)
Based on Assumption 2 and supposing that customers perform the maximum feasible number of requests (φ maxi ) per t, we deduce from Equation 5 the fine price of the contract i where r i is the number of resources required by i:

f i = p i -c t × r i φ maxi (7)
Assumption 3: The service provider wants to share the resources distinct contracts in order to save costs on resources acquisition.

Thus let us assume that the service instances are deployed on dedicated resources and that the execution of their distributed tasks will share further resources. We then reduced g% from the total amount of shared resources. The following equation defines a as the total number of acquired resources by the service provider; where n is the total number of contracts, type is the SLA type, u type is the number of contracts of type SLA type and w type is the number of distributed tasks type requires:

a = n + (100 -g) 100 × platinum type=silver u type × w type (8)
V. IMPLEMENTATION AND CASE STUDY

A. Qu4DS Components

We implemented the infrastructure management interface based on the Grid'5000 [START_REF] Cappello | Grid'5000: A large scale and highly reconfigurable grid experimental testbed[END_REF] which was used as the IaaS layer. We then customized a Grid'5000 image 1 as we would customize an Amazon EC2 image, for instance. In such an image there are all required programs and libraries to execute Qu4DS including an implementation of the job management interface. When a resource is booked, it will be automatically operational and will contain the needed programs installed and configured to Qu4DS.

The implementation of the job management interface follows a layered design. The higher-level layer is the actual implementation of the job management interface that deals with job life-cycle state management (Cf. Figure 2). Moreover, it keeps Qu4DS informed about job metrics following the publish/subscribe pattern which maps job raw metrics (i.e., UNIX process metrics) to job higher-level metrics and job states. The middle layer is implemented by the common InfrastructureBackend abstract class that enables the use of distinct underlying job batch systems. In addition, if it is configured to simulate job misbehave, it will randomly choose the jobs will present faults and/or delays. Currently, two backend implementations are available: one that supports the XtreemOS grid [START_REF] Cortes | XtreemOS: a Vision for a Grid Operating System[END_REF] and another more generic on top of SSH (Secure Shell). The latter allows to let the job management implementation be used on any operating system that allows SSH connections to it and provides the Bash command-line interpreter.

Concerning the implementation of the control loops, they rely on an event-condition-action decision engine. The adaptation strategies that will govern them are loaded from Qu4DS configuration file and applied at runtime. Thereby, when an event is received, it is compared to the strategy conditions to decide whether it will trigger an adaptation or not. Moreover, while the request arrivals control loop always reacts to the arrival of new requests, the other control loops check more specific conditions. They check if there is enough time to adapt (r etime < ad threshold , Cf. Equation 3) and whether the misbehaving job is already a job replacement since replacements should not be replaced.

The negotiation and provision interface was implemented as a SOAP Web Service whose interface defines both negotiation and provision operations as follows:

• List<String> getListOfContractTypes() Gets the list of SLA templates.

B. Case Study: flac2ogg Service Provider

The current Qu4DS implementation addresses distributed service implementations based on the Master/Worker paradigm. The service instance represents the master deployed on the infrastructure while the distributed tasks represent its workers. Qu4DS assists the development of such services by freeing service developers from managing workers and by ensuring their proper execution conforming time constraints and re-acting to job faults. Nevertheless, Qu4DS also deploys and manages the master on the infrastructure

We have then implemented the flac2ogg service provider that encodes FLAC [START_REF]Free Lossless Audio Codec[END_REF] audio files to OGG [START_REF]The Xith Open Source Community[END_REF] as illustrated by Figure 4. Based on SLA templates, customers establish contracts with the service provider by defining the desired throughput th QoS (MB/secs) and the priority. The SLA Negotiator gets the translation of the QoS as the amount of resources necessary to satisfy the QoS and checks based on the number of booked resources if accepting this contract will not compromise its provision capacity. Then the SLA Negotiator configures the master to the right number of workers that can provide the required throughput and deploys it on the infrastructure. Once the master is deployed, an RMI connection is automatically configured to Qu4DS hence establishing a bi-lateral communication channel between the master and Qu4DS.

When a request sent by customer reaches the master through the SLA Negotiator, it splits the FLAC file in w number of workers, sets each worker to work on a split part and asks Qu4DS to execute the workers. Qu4DS wrappers the workers as jobs, submit them through the job management to be executed in parallel. The job metrics callbacks will be the triggers for the job faults and job delays control loops according to the adaptation strategy. When the workers finish encoding the FLAC parts, Qu4DS answers the master which merges them and calls the SLA Negotiator to let it forwards the OGG audio to the right customer.

VI. EVALUATION

A. Calibrating Qu4DS to flac2ogg

We profiled the flac2ogg service provider based on a 194MB FLAC file which means approximatively thirty minutes of recorded audio. Figure 5 depicts the representation of customers' demand by means of a request scheduling for contract duration t = 1800 seconds. The beginning of the bars represents the start time of each request and the end represents rp i threshold along the Time-axis in seconds. The Y-axis represents the customers' contract IDs whose total number is fifteen. Their priorities were whose chosen randomly where the boldness the line is, the highest priority it has. With respect to the SLA type, the first five contracts hold silver SLA type, the next five gold while platinum SLA types contracts vary from the eleventh to the fifteenth. It is important to remark that even though the end of some requests may overlap the beginning of others, it does not necessarily mean that they will be running in the same time. For instance, if a request was gracefully executed with no need to adapt, it will probably finish in time rp mean + rp st d v and not in time rp i threshold . Moreover, although the mean of requests per hour was set to 75% of φ max , the actual request frequency φ i for each customer i was got from a Poisson number generator which explains why the total number of requests of contracts that hold the same SLA type are not the same. Additionally, we reduced two requests from φ max theoretical calculus (Cf. Equation 6) to make it feasible on empirical situations -to let them have a short waiting time between two requests and to have some spare time to shift request scheduling thus better representing a dynamic environment.

B. Scenarios and Testbed

The evaluation scenarios were defined based on the combination of the adaptation strategies as described by Table III. Further, the amount of jobs that were configured to misbehave was 10% for fault jobs and 10% for delayed jobs too knowing that a job could not be fault and late simultaneously which means that eighteen jobs were faulty as well as other eighteen were delayed. With respect to the late jobs, their never stopped aiming at letting them compromise the agreed throughput in order to force Qu4DS to adapt in case of Scenarios A. Additionally, all the contracts were established before starting the request scheduling to ensure that the time to establish the contracts would not compromise the request scheduling punctuality.

An evaluation was then performed in other to know Qu4DS effectiveness on SLA-drive self-management. The goal is to understand the benefit of employing distinct adaptation strategies given a customer demand. The experiments were performed on Grid'5000 resources which have the same characteristics: 8-core 2.5 GHz CPU, 32GB RAM memory computers interconnected through a Gigabit network connection. In order to set the number of booked resources, Qu4DS relied on Equation 8 thus setting a = 43 resources. Moreover, we assumed that the cost of using a resource was c 1800 = 0.05 e.

C. Results

The Figures 6 and7 expose the results of the aforementioned evaluation scenarios. Each cluster represents the percentage of TREATED and ABORTED requests for each contract ID. Moreover, the profit of each sub-scenario is also exposed knowing that the maximum profit a scenario could touch is P 1800 = 15.225, i.e., if there are no SLA violations. When analyzing the results, the first important aspect to observe is effectiveness of strategies SRFJ and SRLJ which is evident when comparing the percentage of aborted requests on Scenarios A and B as well as the profit. This was an expected behavior since FJV and LJV automatically abort requests when either a job fault or delay occurs in order to free the resources before letting the request elapsed time reach its threshold.

Interestingly, the results show the presence of a non expected behavior: the RVC strategy was more efficient than expected. It performed even better than the VBP in the Scenario A. The explanation is that all the adaptation strategies do not consider the future consequences on the request scheduling when taking decision. Indeed, it is obvious that they do not do this since they do not rely on predicting customers' demand. Thereby, random choices of which request should be aborted might better fit to the request scheduling as it really happened in Scenario A. Actually, the way both VFC and VBP strategies act mimics a greedy algorithm which is not often suitable to achieve optimal values. However, we should consider these strategies efficient once we can observe that in Scenario B they both assured greater profit against RVC, mainly the VFC strategy that reached the greatest profit in Scenario A.

Moreover, there was not a significant difference among the profits of the same Scenario even though they clearly aborted distinct percentage of requests. It is owing to the fact that the amount of requests was not that high for the amount of booked resources along with the fact that requests were well dispersed thereby there were not rush moments on the request scheduling.

VII. RELATED WORK

With regard to the SLA management, SOC has widely investigated how services can be discovered, composed, monitored and managed in order to guarantee the proper execution of service-based applications. For instance, SLA negotiation specifications such as WS-Agreements [START_REF] Andrieux | Web Services Agreement Specification (WS-Agreement)[END_REF] and WSLA [START_REF] Ludwig | Web Service Level Agreement (WSLA) Language Specification[END_REF] specify how services can be negotiated, how to described the Quality of Service (QoS) and provides guidelines for monitoring and auditing service behaviors. Moreover, other approaches address further specific aspects of SLA management such as appliance on resource management [START_REF] Hasselmeyer | Towards SLA-Supported Resource Management[END_REF], SLA enforcement [START_REF] Antonio | SLAWs: Towards a Conceptual Architecture for SLA Enforcement[END_REF] and an integrated SLA management [START_REF] Theilmann | A Reference Architecture for Multi-Level SLA Management[END_REF]. Nevertheless, in [START_REF] Pereira | Service Level Agreement Enforcement for Differentiated Services[END_REF], the author proposes a hierarchical SLA management which enforces SLA on top of distinct adaptation policies. This approach relies on policies that adjusts the network traffic based on current QoS values and guided by highlevel objectives. However, these aforementioned approaches do not specifically tackle SLA self-management with precise techniques that aim at profit increase by means of reducing costs. They commonly address QoS assurance however not considering further aspects that impact on cost reduction.

The SLA@SOI project [START_REF] Theilmann | A Reference Architecture for Multi-Level SLA Management[END_REF] addresses a similar problem with this work, but in a different way. Specifically, SLA@SOI proposes an integrated architecture for SLA management that associates SLAs with multiple elements of the software stack at multiple layers. On the other hand, Qu4DS addresses SLA management at a single (PaaS) layer. Furthermore, the SLA@SOI project provides a set of highly generic building blocks, intended to be applicable to arbitrary deployment contexts. Qu4DS provides a complete management solution for web-service providers that build on utility infrastructures, while allowing extensibility with respect to adaptation strategies and infrastructure technologies.

VIII. CONCLUSIONS

This paper has presented a framework, Qu4DS, that facilitates SLA management for services built on distributed infrastructures, such as IaaS clouds. The framework contributes to increasing the provider profit by dynamically managing services and resources, taking into account SLA prices, fines, and infrastructure costs. The framework is modularly structured as a set of control loops configured with replaceable adaptation strategies, thus increasing its applicability to different application domains and adaptation objectives. The framework includes mechanisms for SLA negotiation and QoS translation, thus supporting in an integrated way the full SLA life-cycle, from contract negotiation to service termination. The paper has also presented detailed experimental results demonstrating that the framework can effectively increase provider profits and maintain SLA compliance in dynamic environments.

We intend to continue this work in several ways. First, we intend to add support for dynamically adjusting the number of booked resources to match current demand and to avoid overprovisioning, taking full advantage of the elastic capabilities of cloud infrastructures. Second, we intend to develop additional adaptation strategies and to evaluate them in the context of various workload and infrastructure conditions. Supporting the automated selection of suitable adaptation strategies is a longer-term goal of this work.

IX. ACKNOWLEDGMENTS

The research leading to these results has received funding from the European Community's Seventh Framework Programme [FP7/2007-2013] under grant agreement 215483 (S-CUBE). Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

Fig. 1 .

 1 Fig. 1. Qu4DS Architecture.

Fig. 2 .

 2 Fig. 2. The job life-cycle extended from the SAGA Task life-cycle.

Fig. 3 .

 3 Fig. 3. Qu4DS request life-cycle.

Fig. 4 .

 4 Fig.4. The flac2ogg service provider encodes FLAC audio files to OGG based on the Master/Worker pattern. In this example, the number of worker w is set to two.

Fig. 5 .

 5 Fig. 5. The request scheduling took into account a mean of φ = 75% of φmax. Contract priorities were chosen randomly.

Fig. 6 .

 6 Fig. 6. Results of Scenario A: SRFJ and SRLJ activated.

Fig. 7 .

 7 Fig. 7. Results of Scenario B: FJV and LJV activated.

  Gets all the jobs submitted to the specific resource.• void registerCallback(InfraJob job, String metric, boolean on, Observer observer) Enables or disables event notification of job metrics, e.g., state, elapsed time, resource on it runs, utilization of CPU and memory and so forth.

	• boolean runJob(InfraJob job, String
	resourceAddress)
	Launches an already created job (NEW state) on a specific
	resource. If the resourceAddress is null, it chooses the
	resource based on a previously configured scheduling policy.

• boolean cancelJob(InfraJob job) Cancels the execution of a RUNNING, MIGRATING or SUSPENDED job. • boolean cancelAllJobsOnResource (InfraResource resource) Cancels all jobs on the specified resource. • int checkpointJob(InfraJob job) Saves the current execution flow of a RUNNING job without suspending it. • boolean suspendJob(InfraJob job) Suspends the execution of a RUNNING job. • boolean resumeJob(InfraJob job) Continues the execution of a SUSPENDED job. • boolean resumeJob(InfraJob job, int checkpointVersion) Continues the execution of a SUSPENDED job based on a specific checkpoint. • boolean migrateJob(InfraJob job, String resourceAddress) Migrates the job to the specific resource. • List<InfraJob> getAllJobs(int reservationId) Gets all submitted jobs within the current set of reserved resources. • List<InfraJob> getJobs(String jobState) Gets all submitted jobs within the current set of reserved resources whose state is jobState. • List<InfraJob> getJobsOnResource(String resourceAddress)

  .

		Request Arrival Strategies
	Name		Description
	VFC (Violation based	Aborts the request whose fine is the cheap-
	on Fine Cost)		est.
	VBP (Violation Based	Aborts the request with lowest priority.
	on Priority)
	RVC (Random Viola-	Random choice of request to be aborted.
	tion Criterion)
			Job Fault Strategies
	Name		Description
	FJV (Faulty Job im-	Aborts the request immediately.
	plies Violation)
	SRFJ (Single Re-	Replaces the fault job once. If the same job
	Submission of Faulty	is faulty again, aborts the request.
	Jobs)
			Job Delay Strategies
	Name		Description
	LJV (Late Job implies	Aborts the request immediately.
	Violation)
	SRLJ	(Single	Replaces the delayed job once. If the same
	Replacement	of	job gets late again, aborts the request.
	Late Jobs)

TABLE I QU4DS

 I ADAPTATION STRATEGIES ARE TRIGGERED BY THE ARRIVAL OF NEW REQUESTS, THE OCCURRENCE OF JOB FAULTS AND DELAYS.

  Customer's obligations: are not allowed to exceed the maximum request frequency φ max , i.e., the maximum number of requests per t. -Provider's obligations: should provide the agreed service and ensure its QoS. -Price model: pay-per-use based on the SLA type and varies according to the priority. While p low = 0, it is added x e for each priority level it increases. -SLA type: [ silver | gold | platinum ] -Priority: [ low | normal | high ] -Price: p type + p priority Qu4DS relies on profiling the service provider to collect information to fill the QoS table managed by the QoS Translator and calculate further data used by Qu4DS. The QoS table values are then used to create the SLA templates.

	• QoS
	-Throughput (amount of data / sec): th
	-Priority level: priority
	B. Profiling

• Parties -Service Customer -Service Provider

• Terms -Description: the service functional requirements -Duration: t time unit -

  Table II shows the QoS table together with rp i threshold and φ maxi (Cf. Equations2 and 6) where e 1 = 1.5 and e 1 = 3 (Cf. Equation1).

	SLA	Throughput	Resource	rpi threshold	φmax i
	Type i	(MB/sec)	Configura-	(secs)	(#req/t)
			tion
	Silver	1.49	2 workers	130	11
	Gold	1.90	3 workers	102	15
	Platinum	2.34	6 workers	83	19

TABLE II QU4DS

 II QOSTABLE CALIBRATED BASED ON A 194MB FLAC FILE. THE THROUGHPUT WAS CALCULATED BASED ON rp i threshold .


Dr Thomas M Klapötke

Burkhard Krumm

F Xaver Steemann

Klaus-Daniel Umland

Herbert Schumann

Nitramine, a New Sensitive Explosive Combining a Nitrate Ester with a Nitramine

Keywords: Explosives, Nitramines, Nitrate ester Explosives, Nitramines, Nitrate ester

Nitro functionalized compounds comprise a large substance class and are the most popular explosive materials. Recent research furnished a solid energetic nitrate ester of potential interest. This work is concerned with the synthesis and characterization of novel aliphatic nitramine compounds with similar features.

Introduction

Ever since the discovery of nitroglycerine (1 in Scheme 1) by Ascanio Sobrero in 1846 [1], chemists have investigated nitrated and nitro functionalized compounds for the use as energetic substances. These endeavours furnished e.g. pentaerythritol tetranitrate (PETN, 2 in Scheme 1), a very powerful aliphatic nitrato compound, which is not as easy to detonate by means of shock or friction as is nitroglycerine.

Recent research led to the synthesis of 2,3-bis(hydroxymethyl)-2,3-dinitrobutane-1,4-diol tetranitrate (NEST-1, 3 in Scheme 1) [START_REF] Chavez | [END_REF].

Whereas nitroglycerine becomes handy only when mixed with desensitizing agents such as cellite in the composition dynamite, other aliphatic nitrates, e.g. PETN and NEST-1, display sensitivities against mechanical stress that allow safe use of the pure compounds.

With remarkable structural similarity to nitroglycerine, the nitramine 4 is reported to be explosive as well. Literature about this compound is rather scarce, despite the huge amount of data available on ethyl analogon 5 and on other nitramine compounds [3].

In this paper, the new nitro-aliphatic nitramine bis(1,3dinitratoprop-2-yl) nitramine (6 in Scheme 1) is presented as the most recent outcome of the quest for highly energetic compounds of reduced sensitivity and 4 is investigated more closely.

Scheme 1. Investigated nitro compounds.

Results and Discussion

The synthesis of bis(1,3-dinitratoprop-2-yl) nitramine (6) was performed via nitration of the hydroxy-amine bis-(1,3dihydroxyprop-2-yl)-amine, which in turn can be obtained from 1,3-dihydroxyacetone as reported [4]. Bis-(nitratomethyl)-nitramine (4) was obtained from the reaction of bis-(chloromethyl)-nitramine [5] with silver nitrate.

Compound 4 decomposes upon longer exposure to humidity.

The respond of the compounds to stress was tested in form of impact by a drop hammer and friction imposed by a friction tester apparatus. The test procedures detailed in EC 440/2008 [6] were used for the determination of sensitivities.

In case of 1, 3 and 5, the literature values [1,2,7] are given in Table 1. should result in a significant decrease in sensitivity, the steric effects of the linkage of two 1,3-dinitratoprop-2-yl moieties seem to almost compensate the de-sensitizing effect. For compound 3, where the linkage is a simple C-C single bond, this effect obviously is stronger as for the nitramine-linked dimer 6. From this, substitution of nitrato functionalities by C-linked nitro groups seem to de-sensitize even more than does the introduction of a nitramine functionality.

The friction sensitivity should be mostly influenced by the mechanical properties of the substance such as its hardness.

Therefore, much more force would be necessary to The asymmetric unit represents one formula moiety (Fig. 1). Because the present study is focussed on nitrate ester compounds, energetic properties have to be discussed. In order to predict energy release as well as detonation characteristics (pressure, temperature and velocity), the enthalpies of formation and densities can be used in conjunction with the EXPLO5 thermodynamic code [START_REF] Suceska | EXPLO 5 Program[END_REF].

A simple estimation of the enthalpies of formation can be done by increment calculations using average increment enthalpy values from the literature [START_REF] Sagadeev | [END_REF]. Intramolecular interactions between nitro or nitrato functionalities can be taken into account. Using the measured and reported enthalpies of formation, the EXPLO5 computer code [START_REF] Suceska | EXPLO 5 Program[END_REF] calculates the detonation parameters of the compound at the CJ point with the aid of the steady-state detonation model. A modified Becker-Kistiakowski-Wilson equation of state is used to model the system. The CJ point is found from the Hugoniot curve of the system by its first derivative [11]. The resulting heats of detonation (Q v ), detonation temperatures (T), pressures (p) and velocities (D) are shown in Table 3, as are the oxygen balances (Ω).

Conclusions

The new nitramine 6 might have some advantages in comparison to NEST-1 (3) and the well-established PETN (2), e.g. its very low friction sensitivity, a low melting point and a decomposition temperature of 166 °C (2: ca. 185 °C [1], 3: 141 °C [START_REF] Chavez | [END_REF]). Unfortunately, the impact sensitivity of 6 is only slightly lower than for nitroglycerine (1), therefore only applications of 6 in desensitized mixtures seem reasonable.

Experimental Section

Synthesis of bis(1,3-dinitratoprop-2-yl) nitramine (6, KBX)

Nitric acid (100 %, 1.8 mL, 41 mmol) was cooled to 10 °C and dissolved in glacial acetic acid (4.4 mL, 46 mmol). Upon slow addition of bis(1,3-dihydroxyprop-2-yl) amine (0.96 g, 5.8 mmol) in acetic acid (2.3 mL, 41 mmol), the ice bath was removed and the solution stirred for 72 hours at ambient temperature.

Water (25 mL) was added and the solution extracted with dichloromethane (8 × 25 mL). Aqueous and organic layers were saturated with sodium carbonate and the aqueous layer was again extracted with dichloromethane (4 × 25 mL). The united organic layers were washed with water (25 mL), dried over magnesium sulfate and evaporated. Column chromatography (dichloromethane, silica gel) furnished 1.6 g (72 %) KBX ( 6) as pale yellow oil.

Single crystals were obtained from a saturated solution in dichloromethane by slow diffusion into n-hexane.

Structure Determination

The single crystal X-ray diffraction data of 6 were collected using an Oxford Xcalibur3 diffractometer with a Spellman generator (voltage 50 kV, current 40 mA) and a KappaCCD detector. The data collection was undertaken using the CrysAlis CCD software [12] and the data reduction was performed with the CrysAlis Red software [13]. The structure was solved with Sir-92 [14] and refined with Shelxl-97 [START_REF] Sheldrick | Program for the Refinement of Crystal Structures[END_REF] implemented in the program package WinGX [START_REF] Farrugia | [END_REF] and finally checked using Platon [START_REF] Spek | A Multipurpose Crystallographic Tool[END_REF]. Selected data and parameters from the X-ray data collection and refinement are given in Table X. The crystallographic informations file (cif) on 6 has been deposited with the Cambridge Crystallographic Data Centre under the depository number CCDC-775656. Copies of the data can be obtained free of charge on application to The Director, CCDC, 12 Union Road, Cambridge CB2 1EZ, UK (Fax: int. code + (1223)336-033; e-mail for inquiry: fileserv@ccdc.cam.ac.uk; email for deposition: deposit@ccdc.cam.ac.uk).

Figure 1 .

 1 Figure 1. Asymmetric unit of 6. Crystal data: C 6 H 10 N 6 O 14 , M = 390.18, a = 6.1227(2) Å, b = 10.4051(2) Å, c = 22.3943(2) Å, U = 1426.67(6) Å 3 , T = 100 K, 8282 reflections measured, 2410 unique (R int = 0.031) which were used in calculations. The final wR(F 2 ) was 0.067 (all data).

  a) EXPLO5 values based on CBS-4M results; b) For 3 the reported value was calculated theoretically With high detonation velocity and pressure, the nitrate ester 3 turns out to be the most promising energetic substance, comparable to PETN (2), the nitrato nitramines 4 and KBX (6) display slightly lower detonation values. The lowest values are observed for nitroglycerine (1) and DINA (5), both in the same range.

6: 1 H 7 (

 17 NMR (RT, CDCl 3 ): δ = 5.52 (m, 1 H; CH), 4.82 (m, 2 H; CHH), 4.66 (m, 2 H; CHH) ppm. 13 C NMR (RT, CDCl 3 ): δ = 74.CH), 68.0 (CH 2 ) ppm. 15 N NMR (RT, CDCl 3 ): δ = -49.1 (NO 2 ), -49.2 (ONO 2 ) ppm. IR: ν (cm -1 ) = 3025 w, 2965 w, 2914 w, 2852 w, 1631 vs, 1526 w, 1292 m, 1267 vs, 1086 w, 1015 m, 896 w, 824 s, 751 m, 699 w, 625 w. Raman (400 mW): ν (cm -1 ) = 2986 (100), 2774 (13), 1647 (18), 1457 (17), 1292 (56), 857 (41), 555 (17). Elemental analysis: Calcd. (C 6 H 10 N 6 O 14 ), found (%): C 18.5, 18.7; H 2.6, 2.7; N 21.5, 20.7. DSC (crystals): mp: ~25 °C, decomposition > 165 °C. K ow = 172.4. E dr < 0.5 J (liquid). F r < 353 N.

Table 1 .

 1 Mechanic sensitivities.

	Compd.	E dr / J	F r / N
	1	0.2	353
	2	3	60
	3	2.7	74.5
	4	2	56
	5	6	n.d.
	6	0.5	353
	Formal substitution of the central HCONO 2 moiety in 1 with
	the nitramino moiety NNO 2 leads to the nitramine 4. Its
	impact sensitivity was found to be significantly lower.

Compound 3 can be seen as dimer of nitroglycerine (1) derived by C-C linkage. The sensitivities of 3 are comparable to PETN

[START_REF] Chavez | [END_REF]

. If the central nitrato functionality in 1 was omitted and a nitramine-linked dimer formed, compound 6 would formally be obtained. As Table

1

indicates, compound 6 is only slightly less sensitive towards impact as 1. Because the introduction of a nitramine moiety into an energetic alkylnitrato compound (e.g. 4 and 5)

Table 2

 2

	lists the calculation results as

Table 2 .

 2 Enthalpies of formation (in kJ/mol).

		Calculated (group	Measured / Calculated a
		additivity)
	1	-371	-371 [7]
	2	-532	-593 [7]
	3	-674	-469 (CBS-4M)
	4	-102	-108
	5	-279	-276 [7]
	6	-379	-1055 / -1068 (CBS-4M)
	a) values from bomb calorimetric measurements unless noted
	otherwise
	For substances 1, 2, 4, and 5 good agreement between
	calculated and measured enthalpies is observed. For the
	more heavily branched nitrato alkyls 3 and 6, measurement
	and increment calculation widely disagree. Obviously, the
	intramolecular interactions in these molecules are not
	adequately represented by the increment values from
	literature. For compound 6, calorimetric measurements
	confirm the CBS-4M result.

Table 3 .

 3 Detonation parameters.

	ρ (g/cm 3 )	(kJ/kg) Ω (%) Q v	(kbar) T (K) p	(m/s) D	D meas. (m/s) b
	1 1.591 +3.52 -6037 4629 236 7752 7600 (1.59)[1]
	2 1.760 -10.12 -5923 4423 318 8652 8400 (1.7) [1]
	3 1.917	0	-6569 4814 367 9023 a	9100[2]
	4 1.860 +15.09 -5426 4303 315 8525
	5 1.488 -21.65 -5473 4057 217 7645 7580 (1.47)
						[1]
	6 1.817 -12.30 -4683 3650 285 8245 a

Table 4 .

 4 Crystallographic data of 6.

	formula	C 6 H 10 N 6 O 14
	molecular weight / g/mol	390.18
	temperature / K	100
	crystal dimensions / mm	0.11 × 0.15 × 0.29
	crystal system	orthorhombic
	space group	P2 1 2 1 2 1
	a / Å	6.1227(2)
	b / Å	10.4051(2)
	c / Å	22.3943(2)
	V / Å 3	1426.67(6)
	Z	4
	ρ calc / g/cm 3	1.8166
	µ / mm -1	0.182
	F(000)	800
	θ range / °	3.79-30.09
	index ranges	-8 ≤ h ≤ 8
		-13 ≤ k ≤ 14
		-19 ≤ l ≤ 31
	reflections, measured	8282
	reflections, unique	2410 (R int = 3.1 %)
	R1, wR2 (2σ)	0.0291 / 0.0590
	R1, wR2 (all)	0.0448 / 0.0656
	data/restraints/parameters	2410 / 0 / 235
	GOOF of F 2	0.984
	residual densities / e/Å 3	0.229 / -0.240
	.

Acknowledgment

The authors are indebted and wish to thank Ms. C. Evangelisti for the CBS-4M calculations, Dr. M. Scherr for the X-Ray structure determination and Mr. S. Huber for the bomb calorimetric measurements. Financial support of this work by the Ludwig-Maximilian University of Munich (LMU), the U.S. Army Research Laboratory (ARL), the Armament Research, Development and Engineering Center (ARDEC), the Strategic Environmental Research and Development Program (SERDP) and the Office of Naval Research (ONR Global, title: "Synthesis and Characterization of New High Energy Dense Oxidizers (HEDO) -NICOP Effort") under contract nos. W911NF-09-2-0018 (ARL), W911NF-09-1-0120 (ARDEC), W011NF-09-1-0056 (ARDEC) and 10 WPSEED01-002 / WP-1765 (SERDP) is gratefully acknowledged.

Wiley-VCH ZAAC