Tomasz Hachaj
email: tomekhachaj@o2.pl

Marek R Ogiela
email: mogiela@agh.edu.pl

Evaluation of Carotid Artery Segmentation with Centerline Detection and Active Contours Without Edges Algorithm

Keywords: Active contours without edges, lumen segmentation, carotid bifurcation, computed tomography angiography, brain perfusion maps, computeraided diagnosis. 1

The main contribution of this article is a new method of segmentation of carotid artery based on original authors inner path finding algorithm and active contours without edges segmentation method for vessels wall detection. Instead of defining new force to being minimized or intensity metric we decide to find optimal weight of image -dependent forces. This allows our method to be easily reproduced and applied in other software solutions. We judge the quality of segmentation by dice coefficient between manual segmentation done by a specialist and automatic segmentation performed by our algorithm. We did not find any other publication in which such approach for carotid artery bifurcation region segmentation has been proposed or investigated. The proposed algorithm has shown to be reliable method for that task. The dice coefficient at the level of 0.949±0.050 situates our algorithm among best state of the art methods for those solutions. That type of segmentation is the main step performed before sophisticated semantic analysis of complex image patterns utilized by cognitive image and scene understanding methods. The complete diagnostic record (Electronic Health Record -EHR) obtained that way consists private biometric data and its safety is essential for personal and homeland security.

Introduction

Extracting vessels from computed tomography angiography (CTA) is a key requirement for the display and analysis that type of modality [START_REF] Josephson | Evaluation of carotid stenosis using CT angiography in the initial evaluation of stroke and TIA[END_REF]. CTA is a popular medical imaging method that is often used beside standard computed tomography (CT) in acute stroke imaging. Imaging of the carotid arteries is important for the evaluation of patients with ischemic stroke or Transient Ischemic Attack (TIA). There are many automatic methods to perform the task of segmentation that have been yet proposed in literature. That methods can be divided into two groups: model -based and intensity -based. The first group analysis the geometric specificity of vessels, in particular the notions of orientation and tubular shape. The common approach is utilizing some tube detection filters based on analysis of volume Hessian matrix eigenvalues [START_REF] Hachaj | Segmentation and Visualization of Tubular Structures in Computed Tomography Angiography[END_REF]. Those methods are capable to detect any local tubular structure but are sensitive to noises and scanning artifacts. Algorithms among the second group are dedicated mainly for detailed extraction of continues tubular structures. Many of those algorithms are twostep procedures: at first algorithm finds the path within examined vessel, than detects its boundary. In [START_REF] Krissian | A Minimal Cost Path and Level Set Evolution Approach for Carotid Bifurcation Segmentation[END_REF] authors finds minimal cost paths between the Common Carotid Artery (CCA) and both the External Carotid Artery (ECA) and the Internal Carotid Artery (ICA). Then the cylindrical tube around each path is created with a radius of 0.5mm that is later used for the level set evolution algorithm with proper function of the image intensity. Method in [START_REF] Mille | Carotid Lumen Segmentation Based on Tubular Anisotropy and Contours Without Edges[END_REF] is based on a variant of the minimal path method that models the vessel as a centerline and boundary. This is done by adding one dimension for the local radius around the centerline. The crucial step of method is the definition of the anisotropic metric giving higher speed on the center of the vessels and also when the minimal path tangent is coherent with the vessels direction. Segmentation is refined using a region-based level sets.

The main contribution of this article is a new method of segmentation of carotid artery based on original authors inner path finding algorithm and active contours without edges segmentation method for vessels wall detection. Instead of defining new force to being minimized or intensity metric we decide to find optimal weight of image -dependent forces. This allows our method to be easily reproduced and applied in other software solutions. We judge the quality of segmentation by dice coefficient between manual segmentation done by a specialist and automatic segmentation performed by our algorithm. We did not find any other publication in which such approach for carotid artery bifurcation region segmentation has been proposed or investigated.

That type of segmentation is the main step performed before sophisticated semantic analysis of complex image patterns utilized by cognitive image and scene understanding methods. The complete diagnostic record (Electronic Health Record -EHR) obtained that way consists private biometric data and its safety is essential for personal and homeland security.

The results presented in this article are extension of our previous work. Our latest researches were concentrated on automatic analysis of dynamic perfusion computed tomography maps (CTP) in the event of brain stroke [START_REF] Hachaj | Pattern Classification Methods for Analysis and Visualization of Brain Perfusion CT Maps, Computational Intelligence Paradigms in Advanced Pattern Classification[END_REF]. We decided to widen the area of our interest on CTA because the examination of carotid arteries is an important step during assessing the risk of brain stroke [START_REF] Steinman | Flow Patterns at the Stenosed Carotid Bifurcation: Effect of Concentric versus Eccentric Stenosis[END_REF].

Methods

The proposed lumen segmentation method is consisted of two sub-algorithms. After preprocessing step the first algorithm detects the possible path between the start and the end point (it is similar to typical region growing algorithm). In the second step it performs the thinning of previously obtained path. The generated path between the start and point becomes 1 voxel width keeping the same length as path from first step. The second algorithm is an active contours without edges segmentation method. The role of this procedure is to segment the whole lumen of considered vessel. The active contours is computed in axial slices and the starting counter is the sphere with radius of 5 voxels. The center point of each sphere is a voxel taken from path from Algorithm I. The algorithm requires manual indication of two initial points inside both sides of vessel to be segmented. In order to detect bifurcated structures (like CCA -ICA -ECA) three points have to be chosen and the path detection algorithm have to be run two times, ones for CCA -ICA part than for CCA -ECA. After computing both paths the further analysis is performed on all voxels from both obtained paths.

List of symbols used in algorithm description:

Freezed points:=• -already visited points. Narrow band i := • -points, that are visited in i-th step.

Start point -starting point of the path.• End point -end point of the path. Delta value:=0 -maximal accepted difference between neighbor points. S(x j ) -Surrandings of point x j with radius 1 (26 voxels). V(x j ) -Value of vexel density in point x j . Path length -the length of the path (in voxels). Delta value -maximal accepted difference between two voxel densities. If the difference is greater than Delta value, the considered voxel is not included into the path.

In the preprocessing step of first algorithm the volumetric image is convoluted with Gaussian kernel in order to remove noises and scanning artifacts. The image is then thresholded in order to remove voxels that density do not belongs to range: Because the algorithm stops immediately after detecting the end point it will not generate paths that are too long and it is unnecessary to add any penalization term of path length to the edges weighting function.

Algorithm I, step II -thinning of path obtained in step I. The path generated in second step has the same length as previous path but is only one voxel width.

Path:= • -path from End point to Start point Path:=Path∪End point k:=Path length -1 i:=0 x i :=End point While(Start point ∉ Path) X i+1 :=(y j : |V(y j )-V(x i ) |=min|V(y l )-V(x i ) |, (y l ,k) ∈Freezed points, y l ∈S(x i )) Path:= Path∪x i+1 i:=i+1 k:=k-1 End Algorithm I, step II
The second algorithm is based on active contours without edges segmentation procedure [START_REF] Chan | Active contours without edges[END_REF]. The method requires rescaling the CT volume ISO values (densities) so that it does not consist any negative values of voxels. Beside of that the active contours algorithm does not require any preprocessing and is performed on "raw" CT volume data

The basic idea in active contours models or snakes is to evolve a curve, subject to constraints from a given image in order to detect objects in that image [START_REF] Chan | Active contours without edges[END_REF]. Let Σ be a bounded open subset of R 2 . The algorithm is driven by optimization procedure of energy term:

( ) ( ) ∫ ∫ - + - = + ) ( 2 2 ) ( 2 1 2 2 1 1 ) , ( ) , ( ) , ( ) , ( C outside C inside c y x I c y x I c C F c C F (1)
Where: C is the curve that represents the boundary of segmented region in Σ. I(x,y) is pixel intensity value of image to be segmented with coordinates x, y. c 1 is average value of pixels intensity inside region with boundary C. c 2 is average value of pixels intensity outside region with boundary C.

The equation (1) may also consist regularization terms [START_REF] Chan | Active contours without edges[END_REF] and becomes:

∫ ∫ - + - + ⋅ + ⋅ = ) ( 2 2 2 ) ( 2 1 1 2 1 ) , ( ) , ( )) ( ( ) ( ) , , ( C outside C inside dxdy c y x I dxdy c y x I C inside Area C Length C c c F λ λ ν μ (2)
The first term depends on length of the curve, the second on area inside it. Parameters :, <, 8 1 and

8 2 ( 0 , ≥ ν μ , 0 , 2 1 > λ λ
) are constants.

In [START_REF] Osher | Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulation[END_REF] the authors proposed an effective implicit representation for evolving curves and surfaces, which has found many applications, because it allows for automatic change of topology such as merging and breaking, and the calculations are made on a fixed rectangular grid. A given curve C is represented by zero level set of a scalar Lipschitz continuous function

R → Ω : φ such that: { } { } { } ⎪ ⎩ ⎪ ⎨ ⎧ < Ω ∈ = = > Ω ∈ = = = Ω ∈ = ∂ = 0 ) , ( : ) , ( ) ( 0 ) , ( : ) , ( ) ( 0 ) , ( : ) ,
⎩ ⎨ ⎧ < ≥ = 0 0 0 1 ) ( z if z if z H (5) H is the Heaviside function ) ( ) ( 0 z H dz d z = δ (6) Dirac measure.
In numerical solution the non-zero value of * 0 is defined in range ( )

ε ε + -z z ,
, where ε is a small 0 > ε value.

In the rest of this article we assume that 0 = ν and we do not consider area regularization term into calculations.

In order to minimize

) ( ) ( ) ( 2 2 2 2 1 1 = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ - + - - ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∇ ∇ ⋅ = ∂ ∂ c I c I div t λ λ φ φ μ φ δ φ in 0 ≥ t and in Σ ) , ( ) , , 0 ( 0 y x y x φ φ = in Σ (7) 0 ) ( = ∇ n δ δφ φ φ δ in Ω δ Where:
n is the exterior normal of the boundary Ω δ n δ δφ is the normal derivative of Ν at the boundary. The parameters < (curve smoothing term), 8 1 and 8 2 affects results of optimization procedure. In our case we wanted to verify the hypothesis that term 8 1 should have the higher value than 8 2 to perform proper lumen segmentation. That is because we wanted to restrain the excessive grown of segmented area especially when the borders between area of interest and another tissue with similar density is very narrow. In our experiment the smoothing term is set to 55 . 0 = μ that we assumed proper for considered segmentation task.

Results

The proposed algorithm was tested on a set of four CTA volumes of carotid artery with size 512x512x415, 512x512x425, 512x512x432 and 512x512x433 voxels scanned by SOMATOM Sensation 10 CT scanner. The distance between axial slices was 0.7 mm. The segmentation was performed on left and right carotid artery separately. Because of that the experimental set was consisted of eight tubular structures. The volume to be segmented was determined similarly as in comparison protocol in [START_REF] Hameeteman | Carotid lumen segmentation and stenosis grading challenge[END_REF]. It is defined around the bifurcation slice, which was marked as the first (caudal to cranial) slice where the lumen of the CCA appears as two separate lumens: the lumen of the ICA and the lumen of the ECA (external carotid artery). The segmentation contain the CCA, starting at least 20 mm caudal of bifurcation slice, the ICA, up to at least 40 mm cranial of bifurcation slice, and the ECA, up to between 10 and 20 mm cranial of the bifurcation slice. The segmentation was performed at first on CCA -ICA section, than on CCA -ECA, the final segmentation result is the common part of those two. The 8 1 that we took into account was: 1, 2, 4, 6, 8 and 10.

In figure 1 The volume lumen segmentations is evaluated using the dice similarity measure: 2 presents values of dice coefficient between manual segmentation performed by specialist and automatic segmentation performed by our algorithm. The last column consists average value of coefficient for all considered CTA volumes for given 8 1 value (± standard deviation).

Discussion

The detail analysis of segmentation results (table 1) shows that increasing of 8 1 causes increasing of true negative (TN) and false negative (FN) classification of vessel tissues. From the other hand true positive (TP) and false positive (FP) coefficient decreases. That is because less voxels are captured into region surrounded by active contours during algorithms second step. That behavior is also clearly visible in figure 2 if we compare (A) and (F). The segmented region in (F) is thinner and it also does not consist additional false segmented tissue region. The same situation in the axial view is visualized in Figure 3 (A) and(F). The increasing of 8 1 parameter causes also as expected increase of dice coefficient as it is shown in table 2. From the value of 8 1 above 6 we observe the increasing of standard deviation between averaged results. That is because not always the higher value of 8 1 causes the improvement of segmen-tation results (case 5 in table 2). That is because above some value the expansion of counters might be stopped by the force weighted by 8 2 .

Conclusions

The proposed algorithm has shown to be reliable method for the task of carotid bifurcation region segmentation. The dice coefficient at the level of 0.949±0.050 situates our algorithm among best state of the art methods for those solutions. What is more our proposition can easily be implanted using popular image processing libraries that consists parameterizes active contours without edges algorithm. The proposed method has some drawbacks. The first is that the value of 8 1 that results in optimal from medical point of view solution may differ between examined CTA. The second one is long performance time of the segmentation procedure. What is more the first part of the algorithm -the path finding procedure may be difficult to parallelize on SIMD machines (like GPU processors) because that algorithm is highly sequential (not parallel). It is difficult to predict how the region growing procedure will evolve in each step.

Our method requires further investigation in order to find optimal value not only for 8 1 but also 8 2 and curvature -steering μ. The validation of the segmentation should be performed on bigger set of control data. If the result of evaluation will be on acceptable rate we will use this algorithm as the baseline for the further researches on automatic diagnosis of carotid structures. In order to accomplish this task we are planning to create appropriate semantic description of carotid artery similarly to those proposed in [START_REF] Trzupek | Intelligent image content semantic description for cardiac 3D visualisations[END_REF], [START_REF] Trzupek | Semantic modelling of coronary vessel structures in computer aided detection of pathological changes[END_REF]. After correct identification of possible lumen abnormality we will try to integrate the results with already developed by us CTP diagnosis framework. That approach will allow us to create more complex and complete diagnostic records (Electronic Health Record -EHR) that might be very helpful for radiologist in decision -making process. Nowadays EHR becomes a standard in hospital information systems and in the future might be accessed by wireless personal devices in the area of hospital using low-power personal area networks [START_REF] Jara | An Initial Approach to Support Mobility in Hospital Wireless Sensor Networks based on 6LoWPAN (HWSN6)[END_REF]. The proper information flow policy model will forbid a doctor from mixing the personal medical details of the patients [START_REF] Viet Triem Tong | Specifying and enforcing a fine-grained information flow policy : model and experiments[END_REF]. What is more EHR consists private biometric data and its safety is essential for personal and homeland security.

  [min(V(Start point), V(End point)) -40, max(V(Start point), V(End point)) + 200] That step eliminates the uncontrolled propagation of path detection algorithm in regions where tissues has too low or too high density to be part of examined vessel. Algorithm I, step I -detection of path between Start point and End point. Delta value:=-1 While (End point∉Freezed points) Delta value:=Delta value+1 i:=0 Narrow band:= • Narrow band 0 :={Start point} Freezed point:={(Start point, I)} While ( #Narrow band i >0 ∧ End point ∉Freezed points) i:=i+1 ∀x j ∈Narrow band i ∀y k ∈S(x j ) if(|V(x j )-V(y k )|<Delta value) Narrow band i := Narrow band i ∪ y k Freezed point:= Freezed point i ∪ (y k, i) Path length:=i End algorithm I, step I

  respect to Ν we have to solve Euler-Lagrange equation for Ν[START_REF] Chan | A Multiphase level set framework for image segmentation using the Mumford and Shah model[END_REF].

  0

  the carotid arteries segmentation results of all considered CTA volumes are presented

Fig. 1 .

 1 Fig. 1. The carotid arteries segmentation results of all considered CT volumes ( 10 1 = λ

Fig. 2 .

 2 Fig. 2. Detailed view of segmentation results for CTA from figure 1 B, bottom row (right artery). Red line marks the axial slice that is presented later in figure 3.

Fig. 3 .

 3 Fig. 3. Detailed view of segmentation results for CTA from figure 1 B, bottom row (right artery). Red regions are the segmented ICA and ECA tissues.

  and an algorithmically determined arteries tissues. Table

Table 1 .

 1 The TP, FP, TN and FN coefficients values as the function of 8 1 parameter for CTA from figure 1 B, bottom row (right artery).

	81	TP	FP	TN	FN
	1	12596	5380	116111768	48
	2	12496	3538	116113610	148
	4	12542	2042	116115106	102
	6	12516	1223	116115925	128
	8	12446	617	116116531	198
	10	12427	238	116116910

Table 2 .

 2 Values of dice coefficient between manual segmentation performed by specialist and automatic segmentation performed by our algorithm. The last column consists average value of coefficient for all considered CTA volumes for given 8 1 value (± standard deviation).

	81\case	1	2	3	4	5	6	7	8	AVG
	1	0.648	0.535	0.835	0.823	0.764	0.785	0.806	0.745	0.743±0.0
									96
	2	0.765	0.649	0.879	0.872	0.795	0.825	0.863	0.829	0.810±0.0
									71
	4	0.879	0.823	0.924	0.921	0.822	0.886	0.913	0.903	0.884±0.0
									39
	6	0.927	0.899	0.951	0.949	0.835	0.876	0.947	0.929	0.914±0.0
									40
	8	0.953	0.945	0.959	0.968	0.829	0.907	0.969	0.953	0.935±0.0
									44
	10	0.977	0.970	0.956	0.982	0.827	0.923	0.986	0.973	0.949±0.0
									50

Acknowledgments

We kindly acknowledge the support of this study by a Pedagogical University of Krakow Statutory Research Grant.


Mirosław Trzupek
email: mtrzupek@agh.edu.pl

Marek R Ogiela
email: mogiela@agh.edu.pl

Semantic Techniques of Image Retrieval -the Example of a Structural Analysis of Coronary Arteries

Keywords: Semantic image retrieval, content-based image retrieval (CBIR), image understanding systems

Specialised medical databases currently play a major role in archiving and searching for comparable data acquired by different modalities of medical imaging. In the context of storing and searching for data in medical databases, it is of immense importance to find a method of extracting and representing the contents found in the image that would ensure the rapid access and satisfactory results of searches for image information records. What is important, this representation should also be independent of the form of the image. The wide spread of multimedia medical databases that can store not just single images but also video sequences has shown that the problem of effectively searching for images containing specific disease cases that are significant for medical diagnostics is still fraught with great difficulties. This article presents a semantic retrieval methods in medical imaging databases using graph formalisms of syntactic image recognition which contribute to solving these problems. The proposed methods although they are mainly predestined for medical applications can also provide a base for other solutions, particularly for the acquisition and sophisticated semantic analysis of complex image patterns for security and defence reasons.

Introduction

In recent years, digital images have become a constant part of our life, while in the field of medical imaging they significantly contribute to saving this life. It is hard to imagine making a medical diagnosis and treating many disorders without such basic medical imaging apparatuses as X-ray, CT, USG or MRI equipment. Image data obtained by various medical imaging modalities makes it possible to non-invasively look into the patient's body, which means that the popularity of such diagnostic methods is constantly increasing. On the other hand, the increasing availability of medical imaging apparatuses and, as a direct result, the rapidly growing set of images generated by these apparatuses lead to a major glut of image data used in medical diagnostics. In order to fully utilise its potential, this data must be stored in the right way, particularly so that it is easily accessible. In this context, it is worth noting that proposed methodology may also be used in the area that combines security and defence aspects in designing advanced systems for the retrieving, acquisition, storing and sophisticated semantic analysis of complex image patterns and group behaviours.

In the case of medical diagnostics, this field is currently dominated by systems for archiving medical image data, such as PACS (Picture Archiving and Communication Systems). In particular, these systems are now responsible for the correct and secure transmission, storage and retrieval of image data. The way in which single image is searched in a huge set of image data collected in these databases is the major weakness of these systems. Most frequently, this data is searched for by filling out the appropriate fields with search criteria in the form of alphanumeric data (text and numbers), such as: the patient's personal data, the examination date, the examination description or the selection of the appropriate image modality. Figure 1 shows a typical screen shot from a PACS system. The search criteria are entered as attributes in the alphanumeric format mainly because the images stored in such specialised databases also contain alphanumeric information (describing these images) saved, inter alia, in the headers of the archived files (e.g. DICOM files). Certain inaccuracies or ambiguities in the descriptions are more probable where human factor comes into play during inputting the search information. Those inaccuracies may lead to incorrectly assigning the description to a

given image what, in extreme cases, leads to increasing the risk of mistakes. In addition, describing images textually is labour-and time-intensive, and in the case of medical images requires great experience in interpreting their contents, thus posing a risk of important information being omitted in the description. On the other hand, the clear upside of this method of medical data storage is that image information records of interest can be relatively quickly and effectively found in huge resources of specialised medical databases.

Development of Systems for Context-Indexing Images

Systems for indexing images with their contents date back to the 1970s, but very intensive work on developing such systems was done in 1990s and resulted from the rapidly growing quantity of digital image data which made it necessary to look for effective methods of storing, indexing and accessing it [START_REF] Eakins | Towards intelligent image retrieval[END_REF][START_REF] Müller | A review of content-based image retrieval systems in medical applications-clinical benefits and future directions[END_REF]. Another, no less important factor was the rapid development of computer technology, which, in medicine, directly contributed to the design of new, increasingly advanced medical diagnostic apparatuses. This trend could be observed both in the area of professional equipment (e.g. used in medical imaging) and in everyday life (all kinds of devices for capturing images). In addition, the constantly rising computing power of computers made it possible to undertake problems of digital image analysis which could not be solved before due to their high computational complexity (e.g. morphological transformations). The rapid development of computer methods of digital image analysis and processing which started then has now led not only to the accumulation of a huge quantity of image data, but also to elaborating many algorithms for the computer analysis and processing of images. This means that the great volume of data kept in specialised medical databases requires the creation of increasingly effective algorithms for indexing and finding specific cases.

The traditional approach to managing resources of image data is based on indexing images with their alphanumeric descriptions, but if the sets of this type of data are huge, problems arise because the search results are often very far from optimal. This is mainly due to the vast amount of data that can be contained in an image (this is obvious particularly in the case of medical images), as a result of which even the best verbal description cannot fully present the contents of a given image ("a picture is worth a thousand words"). Neither are descriptions using key words of much help, regardless of their incontrovertible advantage stemming from their brevity. This is mainly due to the fact that the elements of interest (areas of interest) of the image greatly depend on the context, so key words that can be used to describe a given image may be different and not necessarily as expected. This demonstrates the importance of researches in the field of image managing and predefined criteria based searching algorithms. What helps in this regard are CBIR (content-based image retrieval) systems based on the idea of finding images according to their contents. The technique most frequently used in these systems is the query by image content (QBIC), in which the user inputs (or draws) an example image, and the system finds images kept in the database that are similar to this set pattern. CBIR systems such as the QBIC [START_REF] Niblack | The QBIC project: querying images by color, texture and shape[END_REF] allow images retrieving according to their visual features such as e.g. their colour, texture, and shape features, etc. The interface of a typical CBIR system is shown in Figure 2. Another, more refined method of searching within image data sets consists in an attempt to explore the contents of the image using its semantic characteristics (e.g. the type of object or event shown in the image). This is of major importance for medical images, as in their specific case, the computer has to try to explore the meaning of the lesions observed in the image and not just to analyse their form. This 2 level distinction (primitive image features and semantic features) is introduced in article [START_REF] Gudivada | Content-based image retrieval systems[END_REF] in connection with looking for effective methods of automatically retrieving, archiving and semantically categorising image data in multi-media databases. The author of article [START_REF] Eakins | Techniques for image retrieval[END_REF] go a step further and distinguish 3 levels (primitive features, logical features, abstract attributes), which, in addition, can then be split into more sub-levels. This article presents methods of semantic image retrieval in medical databases using semantic features of images. There are still a number of unsolved problems associated with the subject defined above, so the authors are presenting a proposal that applies to a certain class of images, specifically images of the coronary vascularisation obtained from diagnostic examinations with the use of computed tomography (CT).

Technologies of Semantic Image Retrieval -Example of CT Images of Coronary Vascularisation

This paper presents the possibility to use graph formalisms of mathematical linguistic to organise, index and support semantically finding and selecting image information. The set of image data consists of images originating from computed tomography (CT) diagnostics. The semantic approach to indexing and searching databases is more effective than traditional retrieval methods, and the search results produced are more correlated with the set pattern in terms of the contents. This is, of course, due to the descriptive capacity of the semantic methods used, which allow images to be grouped semantically, i.e. not according to their form, but to their contents. The methods presented apply to medical images. It has already been suggested that for this image class, it is very important to extract semantic features and then use them to manage sets of image data because images containing similar diagnostic information about the disease process frequently have completely different forms. In such images, the specific shapes of the lesions observed may take many forms due to individual differences between the diagnosed patients.

The presented methodology of automatically creating semantic descriptions of images stored in multi-media medical databases is based on methods of semantically interpreting coronary arteries, successfully used to describe and identify lesions in coronary vascularisation images as part of previous studies by the authors [START_REF] Ogiela | Picture grammars in classification and semantic interpretation of 3D coronary vessels visualizations[END_REF][START_REF] Trzupek | Semantic interpretation of heart vessel structures based on graph grammars[END_REF][START_REF] Trzupek | Linguistic approach in intelligent image content analysis of heart vessel structures[END_REF][START_REF] Trzupek | Intelligent image content semantic description for cardiac 3D visualizations[END_REF]. What is important in creating sequences describing images from a database is a method of effectively transforming the image information contained in these images (which is easily perceived by a human) to a machine format which supports the intelligent, semantic selection of a specific case (easily assimilated by a computer). One possible method consists in the proposed grammar formalisms for the structural analysis of images, in which the analysed image is treated as a hierarchical structure composed of so-called picture primitives. In their previous publications, the authors proposed using graph grammars to describe and model the spatial relations of coronary vascularisation reconstructions [START_REF] Ogiela | Picture grammars in classification and semantic interpretation of 3D coronary vessels visualizations[END_REF][START_REF] Trzupek | Semantic interpretation of heart vessel structures based on graph grammars[END_REF][START_REF] Trzupek | Linguistic approach in intelligent image content analysis of heart vessel structures[END_REF][START_REF] Trzupek | Intelligent image content semantic description for cardiac 3D visualizations[END_REF]. Grammars of this type generate a formal language in the form of graphs which can model the images considered here, and then the graphs obtained can be represented in the form of their characteristic descriptions. So the mechanism presented makes it possible to transform image information contained in images into a machine format, namely a characteristic description of graphs modelling the coronary vascularisation. What is more, this description can be additionally complemented by sequences generated by sequential grammars [START_REF] Trzupek | Intelligent image content semantic description for cardiac 3D visualizations[END_REF] that are used to represent the width graphs of individual coronary vessels (represented by the edges of the graph modelling the coronary vascularisation). Of course, the use of grammar formalisms also offers a number of other possibilities available when indexing with the use of the grammars applied. Apart from characteristic descriptions representing the graph modelling the given structure enhanced with sequences generated by sequential grammars, it is also possible to use mechanisms provided by the introduced grammar, e.g. in the form of a sequence of numbers of derivation rules of this grammar, defined by the set of their productions. The general diagram of retrieving images from a semantically indexed specialised medical database with the use of the above methodology is presented in Figure 3. In this case, semantic searching boils down to comparing the sequence of semantic descriptions representing the contents of individual images stored in the database to the sequence representing the semantic description of the set pattern (the semantic description of the input image which constitutes the set pattern must also be semantically described in accordance with the presented methodology). As the mechanism thus defined should generate results which accurately correspond to the set pattern, there is a risk that these results will include only a few images. To avoid this, a certain threshold of similarity between the semantic description sequence representing the data in the database and the sequence representing the set pattern should be defined. Although this will increase the risk of obtaining results that are not fully satisfactory, it will also raise the number of results similar to the set pattern, which number can be controlled by adjusting the similarity threshold as necessary. In the case of medical images, additional similar results may help the physician in his/her work. The formal definition of the similarity threshold of sequences of indexing keys will form the subject of further research.

To conclude, it is worth noting that in the case of medical databases, a structural description of image contents with the use of the presented linguistic formalisms is more unambiguous than the traditional description methods using e.g. the colour or texture. This is significant because it has direct impact on the results of searches for images similar to the set pattern in multi-media databases, thus producing more results which strongly correlate with the set pattern in terms of the contents of these images.

Summary and Further Research Directions

Image indexing systems currently in use have several major shortcomings, and therefore cannot be fully utilised. First of all, the majority of them is based on an alphanumeric description written by a human, which can be imperfect. It frequently omits information that is significant from an objective point of view, and often contains errors. Also the headers of DICOM files can contain a relatively high proportion of errors [START_REF] Güld | Quality of DICOM header information for image categorization[END_REF], and this can hinder the correct retrieval of all the images looked for. What is more, systems whose operation is based on visual characteristics can usually process low-level attributes (the colour, texture, shape etc.) without being able to identify high-level features (relationships between objects, object types etc.), or they are able to do this only for a very narrow class of images.

Here it should also be stressed that medical images constitute a special class of images in which images completely different graphically may have the same contents, so particularly for these images there is a need of tools that can correctly extract the image contents masked by varied forms. A doctor following diagnostic guidelines frequently wants to review images showing a similar disorder so that the decision he/she takes is based on many premises and is therefore optimal. In this situation, the attempt to find an image that is similar (in terms of its contents, not form) in large alphanumerically indexed databases leads to retrieving a large number of images whose contents may not be correlated with the set pattern. Hence it is obvious that providing the doctor with the appropriate tools allowing databases to be semantically indexed using an example image pattern can contribute to improving the precision of that physician's diagnostic decisions. In this context, the methods of semantically indexing and retrieving images from medical databases, presented in this article using the example of CT images of coronary vascularisation, significantly contribute to solving at least some of the problems associated with the effective storage, indexing and access to this data. It is also obvious that the proposed mathematical linguistic formalisms offer great potential. Of course, the solutions proposed apply only to a selected class of diagnostic images showing coronary vascularisation, but it is possible to adapt the above solutions to another class of images, especially for complex image patterns (e.g. research that combines security and defence aspects) [START_REF] Wolter | Representing humans in system security models: An actor-network approach[END_REF].

It is also worth noting that the solutions described in the literature are frequently dedicated only to a narrow class of images or are limited only to a specific database [START_REF] Ghosh | Review of medical image retrieval systems and future directions[END_REF]. An ideal system would be able to combine these databases and search through a much greater number of available sources of medical images. What is more, sometimes a system, even though dedicated to a broader group of images, does better with patterns from one class and worse with those from another class for which the implemented mechanisms are less suitable. These and many other problems discovered during research on such systems will also form the subject of further intense work by the authors.

Fig. 1 .

 1 Fig. 1. The main window of the K-PACS system supporting viewing a medical database and searching in it [source: K-PACS V1.6.0 DICOM Viewing Software]

Fig. 2 .

 2 Fig. 2. A screen shot of the MedSearch interface [source: MedGIFT Content-based medical image retrieval]

Fig. 3 .

 3 Fig. 3. Using the above methodology to search for information in a semantically-indexed specialised medical database by reference to a set pattern.

Acknowledgments. This work has been supported by the Ministry of Science and Higher Education, Republic of Poland, under project number N N516 478940.


Giovanni Acampora
email: g.acampora@tue.nl

Vincenzo Loia
email: loia@unisa.it

Autilia Vitiello
email: avitiello@unisa.it

Managing Urban Waste Collection through Timed Automata based Fuzzy Cognitive Maps

Keywords: Urban Waste Management System, Computational Intelligence, Cognitive Modeling, Fuzzy Cognitive Maps, Timed Automata, Timed Automata based Fuzzy Cognitive Maps

In the last years, the increasing urbanization has constrained to face the dramatic growth of the urban waste production and the consequent socio-economical and environmental impact. The relevance of finding an optimal waste management further increases when it involves hazardous materials, since they represent a vulnerable infrastructure sector for homeland defense. Although there is a general agreement on the best strategies for solving urban garbage problem, an opportune waste management seems far due to its intrinsic complexity arising from necessity of dealing with several factors which are often in conflict each other. Over the years, several computerized waste management systems, including deterministic models and fuzzy approaches, have been developed aimed at addressing this complex problem. However, all these approaches do not consider relevant factors which could affect decision policies related to waste treatment, i.e., the rapid evolutions and modifications occurring in a complex scenario such as the urban environment. In order to overcome this drawback, this paper presents an innovative waste management simulation system based on a new timed cognitive inference engine, named Timed Automata based Fuzzy Cognitive Map (TAFCM). A TAFCM is able to simulate the dynamic features of a waste management environment thanks to its temporal benefits due to its ability of dealing with the concept of time in a direct way. As shown in the experimental section, TAFCMs represent a suitable and efficient methodology to manage the waste production problem.

Introduction

In last years, urbanization has been one of the most strong and clear changes affecting all the world. The rapid and constant growth of urban population has led to a dramatic increase in urban waste production, with a crucial socio-economic and environmental impact [START_REF] Karadimas | Municipal Solid Waste Generation Modelling Based on Fuzzy Logic[END_REF]. The importance of finding an optimal waste management further increases when it involves hazardous garbage including any radioactive material manufactured, used, transported, or stored by industrial, medical, or commercial processes. Indeed, hazardous waste represents an environmental infrastructure sector vulnerable to attacks and, for this reason, its treatment goes into homeland defense missions. In the last years, legislation and regulations have been instituted in order to guide the management of waste, hazardous and not, and improve waste policies. Nowadays, there is a general agreement on the best strategies for sustainable management of urban waste which consists in minimising waste production and optimizing waste recovery. Indeed, it is proved that the recovery of the waste is an essential way to reduce the natural resource depletion and create alternative energy sources. Moreover, it is necessary to decrease the use of landfill sites which lead to damage human mental and physical health and represents a more suffered problem in big cities where there is no appropriate land filling zones.

However, an appropriate waste management seems far from being attained [START_REF] Karadimas | Municipal Solid Waste Generation Modelling Based on Fuzzy Logic[END_REF], due, above all, to the intrinsic complexity of the problem. Indeed, an optimal urban waste management involves various relative factors, which are often in conflict. The most important factors are mainly economic (e.g., system cost and system benefit), environmental (air emission, water pollution) and technological (the maturity of the technology). This complexity has led to the necessity of developing integrated, computerized systems for obtaining more generalized, optimal solutions for the management of urban waste collection [START_REF] Karadimas | Urban Solid Waste Collection and Routing: the Ant Colony Strategic Approach[END_REF]. In last years, there have been many solutions developed for the implementation of a waste management system which would monitor and manipulate the generated waste. The theoretical approaches in literature refer to issues concerning the conflict between urban residents and the municipality for the selection of sites for waste treatment, transshipment stations and disposal, or the issue of waste collection and transport as well as its impact to human health due to noise, traffic, etc [START_REF] Karadimas | Urban Solid Waste Collection and Routing: the Ant Colony Strategic Approach[END_REF]. Several deterministic models, including Linear Programming (LP) [START_REF] Gnoni | A mixed-integer linear programming model for optimisation of organics management in an integrated solid waste system[END_REF][4] [START_REF] Lund | Linear programming for analysis of material recovery facilities[END_REF], have been exploited for optimizing sitting and routing aspects of waste collection networks. However, uncertainty often plays a prominent role in dealing waste management problems. Possible sources of uncertainty are the random nature of waste production and the vagueness in planning objectives and constraints. For this reason, fuzzy mathematical programming approaches [START_REF] Lei | A type-II fuzzy optimization model for municipal solid waste management[END_REF][7] [START_REF] Chang | A fuzzy goal programming approach for the optimal planning of metropolitan solid waste management systems[END_REF] have been introduced in the waste collection management. However, all these approaches do not consider relevant factors which could affect decision policies related to waste treatment, i.e., the rapid evolutions and modifications occurring in a complex scenario such as the urban environment. The aim of this paper is to present a waste management simulation system capable of supporting a municipal government in their dynamic decisions related to waste treatment and safe disposal. In detail, our proposal is aimed at simulating a waste management environment by using an extension of Fuzzy Cognitive Maps (FCMs), named Timed Automata based Fuzzy Cognitive Maps (TAFCMs) [START_REF] Acampora | On the Temporal Granularity in Fuzzy Cognitive Maps[END_REF]. FCMs can be viewed as inference networks that use cyclic, directed graphs to represent the fuzzy causal relationships among fuzzy concepts. FCMs' inference engine is based on an easy, iterative and numeric process and, consequently, FCMs are able to represent knowledge and implement inference operators with greater flexibility as compared to many other available methods. Nevertheless, in spite of these benefits, conventional FCMs are not capable of dealing with the concept of time in a direct way. For this reason, a new timed cognitive inference engine, i.e., TAFCMs, has been introduced for improving FCMs' time representation of qualitative system dynamics. Thanks to this feature, TAFCMs represent a promising method for implementing a waste management simulation system where decisions to be made are usually dependent on the temporal events. The rest of the paper is devoted to present this new model and show how it is efficiently able to simulate a dynamic waste management environment.

Timed Automata based Fuzzy Cognitive Maps: Basic Concepts

This section discusses about the methodology, i.e., the Timed Automata based Fuzzy Cognitive Maps (TAFCMs), exploited in this work to simulate a dynamic waste management environment. TAFCMs are new inference engines able to model dynamic changes in cognitive representation of a system and, consequently, perform a more realistic and coherent temporal computation. They achieve this aim by exploiting a synergic approach which combines traditional Fuzzy Cognitive Maps (FCMs) and Timed Automata theory [START_REF] Alur | A theory of timed automata[END_REF]. Indeed, a TAFCM can be informally defined as a pair of a timed automaton, used to describe the dynamic evolution of a system, and a FCM, modeling the cognitive behaviour of the system during the first phase of its existence. Therefore, for a complete understanding, it is necessary to know TAFCMs' basic components which, for this reason, will be briefly discussed below before describing TAFCMs in a more detailed way.

Basic Components of TAFCMs: Fuzzy Cognitive Maps and Timed Automata

FCMs are directed graphs with feedback capable of modeling systems through of collection of concepts and causal relations among them. In detail, in the graph, nodes represent concepts, whereas, edges reflect the causal influences among them. The value of a node, contained in the range [0, 1], is the degree to which the concept is active in the system at a particular time, whereas, the value of the weights, positioned on the edges and contained in the interval [-1, 1], represents the amount of influence existing between two concepts incident on an edge. In particular, the casual relationship between two concepts C i and C j can be: positive which means that an increase in the value of concept C i leads to the increase of the value of concept C j , whereas a decrease in the value of concept C i leads to the decrease of the value of concept C j ; or negative which means that an increase in the value of concept C i leads to the decrease of the value of concept C j and vice versa. A graphical representation of a FCM is presented in Fig. 1. Associated with the graphical representation there is a mathematical model that consists of a 1 × n state vector A which includes the values of the n concepts and an n × n weight matrix W which gathers the weights W ij of the interconnections between the n concepts of the FCM. In this model, the value A i for each concept C i is computed by the following rule:

A i = f ( n ∑ j=1 j̸ =i A j W ij + A old i ), (1)
where A i is the activation level of concept at iteration t + 1, A j is the activation level of the concept C j at iteration t, A old i is the activation level of concept C i at iteration t (it is clear that the variable t just represents the iteration number between two successive FCM matrix computation), and W ji is the weight of the interconnection between C j and C i , and f is a threshold function, i.e, a function used to reduce unbounded inputs to a strict range (typically, a sigmoidal function). FCMs have been used in different research [START_REF] Miao | On causal inference in fuzzy cognitive maps[END_REF] and application fields for decision analysis [START_REF] Zhang | Pool2: a generic system for cognitive map development and decision analysis[END_REF] and for distributed cooperative agents [START_REF] Zhang | A cognitive-map-based approach to the coordination of distributed cooperative agents[END_REF]. However, in spite of their wide applicability, FCMs could be not flexible enough to deal with dynamic systems that change their configurations over time, like social and economical environments and the same urban waste management influenced by government decisions occurring in different and unpredictable moments. Hence, the introduction of TAFCMs capable of enhancing the temporal expressive power of FCMs through the exploitation of a timed automaton. Timed automata are standard finite-state non-deterministic automata extended with a finite collection of real-valued clocks providing a straightforward way to represent time related events. The transitions of a timed automaton are labeled with a guard (a condition on clocks), an action or symbol on alphabet Σ, and a clock reset (a subset of clocks to be reset). Timed automata start computations with all clocks set to zero and clocks increase simultaneously and uniformly with time while the automaton state is located in a given node. Different from standard non-deterministic machine, transitions in timed automata can be taken if the clocks fulfill the related guards. By taking transition, all clocks belonging to the clock reset collection will be set to zero, whereas the remaining keep their values [START_REF] Ericsson | Timed automata as task models for event-driven systems[END_REF]. The transitions occur instantaneously. A simple example [START_REF] Alur | A theory of timed automata[END_REF] of a timed automaton is reported in Fig. 2. The start state of the automaton is S 1 . There is a single clock, named x. The annotation x := 0 on an edge corresponds to the action of resetting the clock x when the edge is traversed. Instead, the annotation (x < 2)? represents a clock constraint which means that the edge can be traversed only if the value of the clock x is less than 2. In general, the behavior of the automaton is as follows. The automaton starts in the state S 1 and moves to state S 2 reading the symbol input a. The clock x gets set to 0 along with this transition. While in state S 2 , the value of the clock x shows the time elapsed since the occurrence of the last symbol a. The transition from the state S 1 to state S 2 is enabled only if the value of the clock x is less than 2. The whole cycle repeats when the automaton moves back to state S 1 .

The set of behaviors expressed by a system modeled by means of a timed automaton is defined by a timed language, i.e., a collection of timed words. A timed word is a pair (σ, τ ), where σ = σ 1 σ 2 . . . is an infinite word and τ = τ 1 τ 2 • • • is an infinite sequence of time values τ i ∈ R with τ i > 0, satisfying constraints of monotonicity and progress (see [START_REF] Alur | A theory of timed automata[END_REF]). In detail, if a timed word w = (σ, τ ), it presents the symbol σ i at time τ i . Therefore, if σ i is an event occurrence then the corresponding component τ i is interpreted as the time of occurrence of σ i . As for the timed automaton presented in Fig. 2, the timed language is represented by all words in which a and b alternate and the delay between a and the following b is always less than 2. Therefore, a possible word is w = (σ, τ ), where σ = abab and τ = 0.0, 1.8, 2.2, 3.7. Given the word w = (a, 0.0) → (b, 1.8) → (a, 2.2) → (b, 3.7), the automaton starts in the state S 1 and moves to state S 2 reading the symbol input a at time 0.0. The clock x gets set to 0 along with this transition. While in state S 2 , the value of the clock x increases. When the symbol b is read at time 1.8, the automaton moves from the state S 2 to state S 1 since the clock x has the value 1.8 which satisfies the guard present on the edge. The automaton moves again to the state S 2 when the second symbol a is read at time 2.2. Finally, the automaton moves to state S 1 , when the final symbol b is read at time 3.7. Indeed, at time 3.7, the x value is 1.5, and then, the clock satisfies again the guard.

Formally, this timed behavior is captured by introducing the run concept. Intuitively, a run is a collection of sequential discrete transitions, where each transition denotes an event releasing a task and the guard on the transition (i.e. a temporal constraint) specifies all the possible arriving times of the event. Therefore, by considering the automaton in Fig. 2, the run which corresponds to word w = (a, 0.0) → (b, 1.8) → (a, 2.2) → (b, 3.7) is as follows:

r : ⟨S 1 , [0]⟩ a -→ 0 ⟨S 2 , [0]⟩ b --→ 1.8 ⟨S 1 , [1.8]⟩ a --→ 2.2 ⟨S 2 , [0]⟩ b --→ 3.7 ⟨S 1 , [1.5]⟩.
See [START_REF] Alur | A theory of timed automata[END_REF] for more details about the run concept, and, in general, timed automata.

TAFCMs: Merging of Timed Automata and Fuzzy Cognitive Maps

TAFCMs are new timed cognitive inference engines capable of modeling dynamic complex systems. They enhance the modeling power of FCMs by adding three new timing mechanisms, named Top-time (T-Time), cognitive era and cognitive configuration. In detail, the exploitation of these new cognitive concepts enables FCMs to represent a generic system as a biological entity that lives its existence by crossing a sequence of time periods (cognitive eras), each one representing the longest interval time in which the system does not change its cognitive configuration, i.e., its concepts and causal relationships. In order to implement this new mechanism, TAFCMs exploit a timed automaton whose possible behaviors define all the potential sequences of cognitive eras (and the related cognitive configurations) that the system could cover during its life-cycle. More in detail, TAFCMs improve FCMs by associating each state in a timed automaton with a cognitive configuration which describes the behavior of a system in a time interval. Therefore, informally (see [START_REF] Acampora | On the Temporal Granularity in Fuzzy Cognitive Maps[END_REF] for a mathematical definition), a TAFCM has two components: a timed automaton T M that describes the dynamic evolution of a system and a FCM F 0 modeling the cognitive behavior of the system during first phase of its existence. Once that the automaton computation starts over a given timed word, the state transitions will adaptively modify the initial FCM in order to model time-dependency of the system. In order to transform the structure of a FCM representing a cognitive configuration, the following collection of operators has been introduced:

-To add concepts (⊕); -To add causal relationships ( ); -To remove concepts (⊖); -To remove causal relationships ( ); -To magnify/reduce the strength of a causal relationships ( for an additive modification and for a multiplicative modification); -To magnify/reduce the level of system concept ( † for an additive modification and ‡ for a multiplicative modification).

The mapping between the states of timed automaton T M and the collection of cognitive configurations computable starting from F 0 by applying different sequence of operators is called cognitive evolution, whereas, the progression of the cognitive eras is performed by using the so called cognitive run, i.e., a cognitive extension of the initial idea of the run of a timed automata. As aforesaid, intuitively, a run is a collection of sequential discrete transitions, where each transition denotes an event releasing a task and the guard on the transition (i.e. a temporal constraint) specifies all the possible arriving times of the event. In the context of the cognitive representation, the i th discrete transition can be used to move a system among cognitive eras and release a task changing the cognitive configuration of the system, i.e., transforming the FCM that represents the cognitive configuration during i th cognitive era into a new one modeling the system during (i + 1) th cognitive era. Both the cognitive evolution and the cognitive run are potentially based on the infinite concept in the system. In fact, the cognitive evolution can exploit an infinite application of cognitive operators to compute the mappings between the automaton states and the FCMs representing cognitive configurations, whereas, the cognitive run uses a timed word, defined as a infinite sequence of ordered pairs, to describe the cognitive/dynamic behavior of the system. Consequently, in order to simulate the behavior of a TAFCM during the first n cognitive eras, the annotation of n th -order cognitive evolution and n th -cognitive run has been introduced.

See [START_REF] Acampora | On the Temporal Granularity in Fuzzy Cognitive Maps[END_REF] for a formal definition of cognitive evolution, cognitive run and T-Time, whereas, our discussion about TAFCMs ends with an example taken by [START_REF] Acampora | On the Temporal Granularity in Fuzzy Cognitive Maps[END_REF]. In this sample, a timed cognitive system describing the behavior of an ecosystem formed by three initial elements, predators (P 2 ), preys (P 1 ) and grass for preys (G)) is given. Figs. 3 and4 show, respectively, the initial cognitive configuration F 0 of proposed system and the modified timed automaton T M that defines the dynamic behavior. In order to show how a TAFCM allows to dynamically modify the cognitive concepts of the system, let us consider, for instance, the transition from the state s 0 to s 2 . When the automaton traverses this transition, the new concept hunter (H) is added to system to modify the cognitive concepts, G, P 1 and P 2 in a novel and unpredicted way. This transformation is denoted by the operator ⊕ present on the transition. Moreover, by considering the timed word w = (σ, τ ) = (a, 0.2) → (b, 0.4), we can compute the 3 th -order cognitive run r 3 c (with the clock period k = 0.1) as follows:

r 3 c : ⟨s 0 , [0]⟩ a,⊕ --→ 0.2 ⟨s 1 , [0.2]⟩ b, --→ 0.4 ⟨s 2 , [0.4]⟩, (2)
which defines three cognitive eras, respectively starting at time 0, 0.2 and 0.4. Fig. 5 shows the three corresponding cognitive configurations.

A TAFCM for Urban Waste Management

In this section, we show how a TAFCM can be exploited to simulate and evaluate the behavior of a dynamic waste management system. In general, it is the municipality's responsibility to manage waste including its collection, treatment, and safe disposal. During the term of a municipal government, in its effort to improve the waste management, it may make several decisions in order to modify its political plan. Such decisions are very complex due to great number of the involved factors, often in conflict each other, and usually dependent on the time in which they are taken. In particular, this last feature denotes a dynamic nature of urban waste management problem. Therefore, thanks to its ability to model systems evolving over time, a TAFCM could represent a promising methodology for efficiently designing an urban waste management simulation system. Our idea is to use a TAFCM for comparing different political strategies so to allow municipality to make the most opportune decisions at beginning of its government mandate.

As aforesaid, factors involved in the urban waste management are a lot, but above all, characterized by different nature: economical, social and environmental. In particular, in this work, we consider the following factors:

population: this factor refers to number of residents in the city at issue. It is very important to estimate the amount of produced waste; migration into city: this factor refers to degree of migration which affects the city. It is relevant over years in order to estimate the increasing of the population; modernization: this factor includes all municipality activities aimed at improving life quality of people. For instance, they involve infrastructure and transportation improvements; waste per area: this factor refers to average amount of waste per area produced by population. It represents a critical value which should be maintained under control and minimized; sanitation facilities: this factor includes all activities of municipality and not only devoted to improve health quality of people. disease percentage: this factor refers to number of deseases per 1000 residents.

It is a critical value which should be monitored because its increasing may lead to an sanitation alarm; bacteria per area: this factor refers to average amount of bacteria per area.

It represents a critical value which, obviously, should be minimized in order to improve life quality of people; economical funds: they represent the money reserved to urban waste management. Therefore, for instance, they can be used to build new incinerators, to look for location for new landfills, to promote educational plans or recycling programs, to pay workers responsible for collecting waste door to door or cleaning streets. These municipality's funds could be increased by periodical or one-off government payments.

Starting from all involved factors, there are several possible strategies which the municipality could follow. They belong to these four categories:

waste disposal : it includes all disposal methods such as dumping, landfilling and incineration of waste; waste recycling: it refers to recycling of all materials that can be reprocessed either into the same material (closed loop) or a new product (open loop). Therefore, recycling is not only an alternative to disposal, but it allows also the reduction of the amount of virgin materials used for the manufacture of new products;

waste processing: it includes all activities devoted to the treatment and recovery of materials or energy from waste through thermal, chemical, or biological procedures; waste minimization: it is aimed at decreasing the generation of waste by means of education and optimized production process rather than enhancing technology for handling waste. In detail, minimizing waste production is viewed as result of a maximization of the efficiency of available resources, and as a consequence, it may lead to decrease costs to treat waste to be disposed.

In order to simulate the application of different strategies, a TAFCM composed of the initial FCM F 0 (see Fig. 6) and the timed automaton T M (see Fig. 7) is introduced. In particular, F 0 models the collection of concepts related to waste management, before possible strategies are applied. The mapping between the considered factors and the cognitive concepts is as follows: c 1 ≡ population, c 2 ≡ migration into city, c 3 ≡ modernization, c 4 ≡ waste per area, c 5 ≡ sanitation facilities, c 6 ≡ disease percentage, c 7 ≡ bacteria per area, c 8 ≡ economical funds. The weights characterizing the relations among concepts had been defined by an expert of domain. Instead, the timed automaton T M allows to model municipality strategies by transforming F 0 at right opportunities. However, for sake of simplicity, the reported T M models only two possible strategies belonging to the first presented category (see section 4). The timed automaton T M considers only a clock named x. Each edge of T M is labeled with a symbol, representing an occurred event, a guard, indicating the temporal constraint which x must satisfy to cross transition and a sequence of transformation operators which allows to opportunely modify the initial FCM. In particular, each operator takes in input concepts which are affected by the change and, according to the kind of operator, a real value representing the amount of modification. In this work, the temporal constraint for cognitive transitions is in the unit of Year, whereas, the simulated time duration is equal to a complete municipality mandate (5 years). However, in spite of the implemented TAFCM, the exploited methodology represents a general framework able to efficiently simulate also other, more expanded, waste management scenarios characterized by a greater number of factors, new strategies and a different temporal constraint.

Experimental Results

In this section, we demonstrate how a TAFCM can efficiently simulate a dynamic waste management system. Indeed, our experiment will show how a TAFCM can be used to support municipality's decisions by providing a temporal simulation of all involved factors. In particular, our experiment illustrates how the implemented TAFCM to succeed in supporting municipality's decisions by detecting the best strategy (between the considered strategies) to be followed in order to minimize the waste and bacteria per area with a good use of government funds reserved for urban waste management. In detail, the experiment involves the evaluation of two strategies, named program I and program II. The scenario is the following one. Let us consider a city which is not equipped with technological tools for waste treatment, and hence, the municipality decides to build one of them. Besides, the municipality plans to promote some educational plans in order to teacher people how to minimize the production of waste. The municipality annually receives a fixed amount of economical funds by the central government, and, occasionally, it receives a further economical support. In this scenario, the two considered strategies dissent because of the use of different kinds of technologies:

program I provides to build high quality and expensive technologies that are characterized by a slow aging and cheap maintenance costs; program II provides to build low quality and cheap technologies.

Starting from this description, it is clear the necessity to introduce new factors over time to deal with urban waste management. In detail, they are:

technology: this factor represents technological tools aiding waste treatment such as incinerators; educational plans: this factor refers to a collection of educational programs promoted by the municipality to raise citizen awareness; aging: this factor refers to aging which may affect technological tools.

With the help of the implemented TAFCM (F 0 , T M ), it is possible to decide the best strategy among program I and program II. By taking into account our TAFCM, the two considered strategies correspond, respectively, to two different timed words of the exploited timed automaton T M :

w 1 = (σ 1 , τ ) = (a, 1) → (c, 2) → (e, 3) → (g, 4) w 2 = (σ 2 , τ ) = (b, 1) → (d, 2) → (f, 3) → (g, 4) (3)
Both timed words evolve F 0 through the five years by crossing four cognitive eras whose cognitive configurations are defined, respectively, by cognitive transitions labeled with symbols aceg and bdfg. w 1 and w 2 generate a 4 th -order cognitive evolution with the corresponding 4 th -order cognitive run which represents the application of opportune decisions in a given time.

Now, let's analyze the effects of application of w 1 and w 2 on the initial map F 0 in order to highlight benefits/drawbacks provided by corresponding strategies. During the cognitive runs related to w 1 and w 2 , the TAFCM (F 0 , T M ) evolves through such events as receiving funds from the central government, improving technologies and educational plans. During their cognitive evolutions, both timed words allow to add new concepts to F 0 : c 9 ≡ technology, c 10 ≡ educational plans, c 11 ≡ aging.

The whole municipality's behavior with respect to the timed words w 1 and w 2 is showed, respectively, in Tables 1 and2.

As highlighted by Figs. 8 and9, program I associated with w 1 produces a more effective behavior of the whole municipality decisions because they decrease the value of concepts c 4 and c 7 , respectively, related to waste per area and bacteria per area, and at the same time, it allows municipality to save economical funds (concept c 8 ). Therefore, thanks to the exploitation of a TAFCM, it has been possible to identify the best strategy to be followed.

Conclusions

The management of hazardous and not waste is a significant problem due to socio-economical and environmental impact and the relative homeland defense issues. This paper presents a new method to simulate a dynamic waste management system able to support municipality's decisions by identifying the best strategies to be followed. In particular, the exploited methodology, named Timed Automata based Fuzzy Cognitive maps (TAFCMs), is capable of efficiently managing the waste production problem thanks to its cognitive approach. In detail, TAFCMs allow to model complex systems characterized by a temporal uncertainty, like urban environments, through the exploitation of a double-layered temporal granularity based on the concepts of cognitive configuration, cognitive era and cognitive run. As shown by an experiment, TAFCMs are a promising framework for simulating a dynamic waste management system. However, TAFCMs introduced in this work exploit expert knowledge to design the collection of cognitive eras and configurations representing the temporal behavior of the system under design. Therefore, in the future, our idea is to investigate some machine learning approaches such as evolutionary computation to automatically find suitable cognitives era and configurations for improving the system behavior.

Fig. 1 .

 1 Fig. 1. An example of a simple FCM.

Fig. 2 .

 2 Fig. 2. A Timed Automaton.

Fig. 3 .

 3 Fig. 3. The initial cognitive configuration of ecosystem sample.

Fig. 4 .

 4 Fig. 4. The cognitive timed automaton that describes the dynamic behavior of the ecosystem sample.

Fig. 5 .

 5 Fig. 5. Three cognitive configurations of ecosystem sample. The graph (a) shows the first cognitive configuration F 0 ; the graph (b) shows the cognitive configuration F 1 related to the state s2, obtained by applying the ⊕ operator over the FCM F 0 ; the graph (c) shows the cognitive configuration F 2 related to the state s3, obtained by applying the operator over the FCM F 1 .

3 Fig. 6 .Fig. 7 .

 367 Fig. 6. The cognitive map F 0 .

Fig. 8 .

 8 Fig. 8. Concept values (c4, c8, c7) evolution related to 4 th -order cognitive run of w1.

Fig. 9 .

 9 Fig. 9. Concept values (c4, c8, c7) evolution related to 4 th -order cognitive run of w2.

Table 1 .

 1 Description of the 4 th -order Cognitive Evolutions related to timed word w1

		Operator	Description
		⊕(c9)	High quality (HQ) Technology is added
		†(c8, 0.5)	Municipality increases by 50% its funds
	I cognitive era	(c3, c9, 0.6)	Modernization positively supports
			Technology Maintenance (60%)
		(c9, c8, -0.8) HQ technology reduces by 80%
			the municipality funds
		†(c8, 0.3)	Municipality increases by 30% its funds
		(c9, c8, 1)	HQ Technology positively increases
			municipality funds
		(c9, c4, -0.5) HQ Technology strongly decreases
			garbage per area
		⊕(c10)	Municipality starts Educational Plans
	II cognitive era	⊕(c11) (c11, c9, -0.65) (c10, c4, -0.3) Educational Plans reduce Technology aging starts
			waste per area
		(c10, c8, -0.1) Educational Plans reduce
			municipality funds
		(c3, c10, 0.3)	Modernization positively influences
			Educational Plans
		†(c8, 0.3)	Municipality increases by 30% its funds
		(c9, c8, 0.2)	HQ Technology positively increases
	III cognitive era		municipality funds
		(c9, c4, -0.3) HQ Technology decreases
			waste per area
	IV cognitive era †(c8, 0.3)	Municipality increases by 30% its funds

Table 2 .

 2 Description of the 4 th -order Cognitive Evolutions related to timed word w2

		Operator	Description
		⊕(c9)	Low quality (LQ) Technology is added
		†(c8, 0.5)	Municipality increase by 50% its funds
	I cognitive era	(c3, c9, 0.6)	Modernization positively supports
			Technology Maintenance (60%)
		(c9, c8, -0.2) LQ technology reduces by 20%
			the municipality funds
		†(c8, 0.3)	Municipality increases by 30% its funds
		(c9, c8, 0.3)	LQ Technology slowly increases
			municipality funds
		(c9, c4, -0.3) LQ Technology slowly decreases
			waste per area
		⊕(c10)	Municipality starts Educational Plans
	II cognitive era	⊕(c11) (c11, c9, -0.85) (c10, c4, -0.3) Educational Plans reduce Technology aging starts
			waste per area
		(c10, c8, -0.1) Educational Plans reduce
			municipality funds
		(c3, c10, 0.3)	Modernization positively influences
			Educational Plans
		†(c8, 0.3)	Municipality increases by 30% its funds
		(c9, c8, 0.1)	LQ Technology increases
	III cognitive era		municipality funds
		(c9, c4, -0.25) LQ Technology decreases
			garbage per area
	IV cognitive era †(c8, 0.3)	Municipality increases by 30% its funds


Martin Gilje Jaatun

Karin Bernsmed

Astrid Undheim

Security SLAs -an idea whose time has come?

Service Level Agreements (SLAs) have been used for decades to regulate aspects such as throughput, delay and response times of services in various outsourcing scenarios. However, security aspects have typically been neglected in SLAs. In this paper we argue that security SLAs will be necessary for future Internet services, and provide examples of how this will work in practice.

Introduction

The future Internet will provide an open ecosystem of services that can be mixed and matched according to customers' individual requirements. Service oriented architectures will form the basis for future applications and software products where complex service compositions and dynamic changes and replacement of individual service components will be common practice. New components will be picked not only based on functionality, but also based on their availability, performance, security, quality and price. In order to differentiate themselves in a highly competitive market, service providers will have to front the differentiating advantages of their services in order to attract potential customers.

The obvious downside of complex applications involving multiple providers is that they introduce the specter of uncertainty; it will be difficult for the customers to ensure that the final service compositions, i.e., the products they are paying for, behave as expected and that the individual service components can be trusted. From the customer's point of view, security and trustworthiness through the whole chain of service components may very well be the key issue that differentiates one potential service provider from another.

To illustrate the complexities of a composite service, we will employ the example depicted in Figure 1 [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]. Here, the service provider is a telecom operator with its own voice telephony service who wants to offer a Unified Communications (UC) service to its customers. To do this, it needs to combine its own voice service with conferencing, messaging and presence services from subcontractors. The telecom operator will hence act as a service provider towards the final UC users and as a service customer towards its subcontractors. In the following we will see how the UC provider can offer a defined security level to its customers through the use of Security Level Agreements with its subcontractors. 2 Service Level Agreements A Service Level Agreement (SLA) is a common way to specify the conditions under which a service is delivered. An SLA addresses three fundamental questions: what is delivered; where is it delivered; when is it delivered? The purpose of an SLA is to serve as a binding agreement between the service customer and the service provider. The SLA will help ensure that the service keeps the right level of quality and that customers are credited accordingly in terms of contract violations. SLAs have been used for many years to specify the quality of service delivered to corporate customers by for example telecom operators, as well as for regulating outsourcing contracts in the IT domain. However, SLAs have until recently not received much interest from the public at large. Service Level Agreements come in a variety of forms. Today, a typical SLA states the obligations of the provider, the circumstances under which it is valid, and the penalties if the SLA is broken. An SLA often has both business and technical parts, but here we will focus on the technical part. To verify that the provider delivers service in accordance with the agreement, an SLA usually contains Quality of Service (QoS) parameters. QoS refers to the (measurable) ability of a system to provide the network and computation services such that the customer's expectations are met.

QoS have traditionally covered the dependability and performance characteristics of a service. Service dependability is usually defined as a combination of the service availability (the proportion of time a system delivers service in accordance with the requirements) and service reliability (the system's ability to provide uninterrupted service). Service performance is usually characterized by throughput (the number of bits of data transmitted or processed per second) and delay (the number of seconds used for transmission or processing) [START_REF]International Telecommunication Union: Terms and Definitions Related to Quality of Service and Network Performance Including Dependability[END_REF]. The term QoS usually does not include security, even though several initiatives have tried to extend the term in this respect [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]. Today many service providers offer QoS guarantees as a part of their SLAs, however the focus in most cases is on availability. For example, the SLA for Amazon's Elastic Compute Cloud is in principle limited to the following statement: "AWS will use commercially reasonable efforts to make Amazon EC2 available with an Annual Uptime Percentage (defined below) of at least 99.95% during the Service Year." From the customers' point of view, the lack of guarantees of other non-functional attributes is a major drawback; e.g., a service with very low performance will be perceived as being unavailable.

The Need for Security SLAs

Even though service availability and performance are critical issues, security is often stated as the main barrier against outsourcing critical data and applications to actors where no previous trust relations exist. To mitigate the security risks associated with service oriented architectures, and to increase the trust in the providers, existing security mechanisms and their effectiveness should be formalized in contracts. Since the SLA is used to explicitly state the obligations of the provider, the implemented security mechanisms, their effectiveness and the implications of possible mismanagements should be a part of the SLA. This concept is also known as Quality of Protection (QoP); the ability of a service provider to deliver service according to a set of specific security requirements. In the following we will call such a contract a "security SLA". A security SLA should (at least) include:

-A description of the service that is to be provided -The security requirements that the provider will commit to -The process of monitoring security, including what evidence to collect and present, how the evidence will be collected and who will be responsible for it. -The process of reporting problems, threats or security related incidents. This also includes information on what person to contact when a problem occurs and the acceptable time for resolving the problem. -Consequences for cases when the provider (or customer) breaks the terms stated in the SLA, in terms of service credits or financial compensation.

The service provider may also want to include constraints on the customer behavior and escape clauses defining when statements in the agreement do not apply. -Legal and regulatory issues, including references to existing legislations and directives that may affect the service as well as the terms under which the SLA will not be valid.

To return to our UC example (Figure 1), the UC provider intends to offer a service to end-users that can satisfy a set of security requirements, and in order to accomplish this, it must establish a security SLA with each of the subcontractors. For the messaging service, assume that we have the following security requirements [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]:

1. User profile information must be stored in an encrypted state 2. Only a hashed value of the user password will be stored. 3. A user profile will only require a valid email address and username; age, gender, name, picture and phone number will be optional fields. 4. Information exchanged among the participants must be kept confidential 5. All text messages must be digitally signed 6. Authentication shall be based on symmetric encryption using a trusted third party as authenticator 7. The endpoints of all connections must be mutually authenticated 8. Only one instance of an authenticated user can participate in a communication session 9. Only the service provider will have access to statistical information 10. Asymmetric communication must be stored in an encrypted state and not for more than 48 hours 11. All location data must be logged for a minimum of 48 hours and maximum of 168 hours.

The security SLA also states that problems shall be reported to the messaging provider's contact email address, and that any security breaches and other security notifications shall be reported from the messaging provider to the UC provider's email contact point. General security monitoring shall be performed by an Intrusion Detection System (IDS), with specific filters to verify that no clear text user information, passwords or messages are transmitted. The IDS will detect unauthorized attempts to extract statistical information, and also verify that only one instance of an authenticated user will participate in a session, and check that all messages are signed. Spot-check audits are required to verify that user profile information and passwords are not stored in clear text, and that the logging requirements are fulfilled. In addition to the security requirements, the messaging service is subject to the European Data Retention Directive, requiring logging of communication endpoint IDs for six months.

Managing the SLA

Today's SLAs are usually in textual format; however, in the near future we envision an SLA as a dynamic construct, which will need to be renegotiated as the context changes [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]. There are several possible events that may trigger a change in the security terms; e.g., the user's needs may change during the validity period of an SLA, but more importantly, the provider's ability to provide a given level of security may change, e.g. due to recently discovered flaws in specific components.

We envision an SLA lifecycle as illustrated in Figure 2, which consists of six phases: Providers first publish their SLA templates, and users then initiate negotiation based on these. Once the negotiation is successful, providers and users formally have to commit to the resulting SLA, and the provider effectuates the provisioning. While the service is running, monitoring should ensure that the SLA terms are met, and when the relationship between user and provider comes to an end, the SLA must be terminated. Feedback loops are used when it is necessary to return to the negotiation phase from any of the active phases; e.g., if either of the parties cannot commit to a negotiated SLA, if the provider is unable to provision the service (due to overbooking), or if monitoring reveals that SLA terms are broken. In practice, the contracting period may vary from very short periods like a minute (e.g. the temporary lease of a fiber optic communication channel) to months and years for more stable services (e.g. a backup service for corporate data). For composite services, security SLAs will need to be established between all actors that participate in the final service composition. The SLAs will therefore be negotiated and managed on several layers before a final service can be delivered to the customer; in fact, the customer need not even be aware that different service providers deliver these services. Returning to the UC example, we assume a service delivery and security SLA has been established between the customer and the UC provider, providing voice, instant messaging, presence and conferencing services, with associated security service levels. For the UC provider, the risk of violating the security SLA towards the customer must be handled by ensuring satisfactory security SLAs towards its subcontractors. These agreements may be the results of a traditional Request for Quotation (RFQ) process, in which case the various service providers have a static business relationship and security SLA with the UC provider, or it can be a more dynamic process where the UC provider queries potential service providers on demand. This is related to the publishing phase above.

The necessary negotiation phase is the same irrespective of the publishing scenario chosen. In this specific example, the UC provider has its own voice service, and as long as this can satisfy all voice-related requirements, the UC provider will not query or start negotiations with additional external providers. For the messaging service, provider B is the only one that fulfills all the security requirements listed, and is chosen over providers A and C. The same selection procedure is followed for the remaining services.

After the negotiation phase is completed, the UC provider initiates the commitment phase where the service providers commit to deliver the previously offered service and all parties digitally sign the security SLA. The necessary resources for service provisioning were reserved during the negotiation phase, and the service can easily be provisioned. The UC provider will then monitor the service fulfillment from the service providers, possibly using an external independent auditor, and breaches must be handled accordingly. This may result in renegotiation of the contract or eventually termination of the contract.

For the UC provider, establishing a security SLA towards its subcontractors minimizes the risk of violating the SLA they have committed to with their customers.

Technical Challenges

To facilitate the process of negotiating security SLAs with different potential service providers, to make the comparison of different service offerings simpler, and to simplify the commitment phase of the service lifecycle, there is a need for common industry standards and corresponding templates for machine-readable agreements [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]. However, there are no such templates for security SLAs available today.

Establishing a security SLA is not sufficient in itself; the agreed terms need to be monitored and controlled as well. However, monitoring and controlling security terms are inherently difficult. While other QoS aspects, such as the service availability, can easily be measured and controlled by the users themselves, security tends to be more difficult to monitor. One reason is the nature of service oriented architectures, which are designed to hide the inner workings of the services from the user, exposing only their APIs to the developers. Another reason is that the security requirements are often stated in terms of what should not happen, making it difficult to verify that the preventive mechanisms works as intended, until a breach has already occurred. In addition, the really clever attacks often go unnoticed.

Past, Present and Vision

The interest in and demand for security SLAs has varied throughout the years. Researchers began investigating security SLAs as much as twenty years ago [START_REF] Irvine | Quality of security service[END_REF]. Early work on security agreements was performed by Henning [START_REF] Henning | Security service level agreements: quantifiable security for the enterprise?[END_REF], who already then raised the question whether security can be adequately expressed in an SLA. The interest in security SLAs received a new boost in the late nineties when QoS agreements in IP-based network was a hot topic in the research community, especially in the telecommunication sector [START_REF] Grgic | Agreements in IP-based Networks[END_REF]. Researchers pointed out the need for security as a QoS attribute but did not manage to define service levels that were useful to users and service providers [START_REF] Lindskog | Adding Security to Quality of Service Architectures[END_REF]. A second wave of interest was raised when the increased adoption of Service Oriented Architectures (SOA) drew attention to non-functional attributes, such as security and performance of web services [START_REF]SLA@SOI Consortium: SLA@SOI[END_REF][START_REF] Righi | Sec-mon: An architecture for monitoring and controlling security service level agreements[END_REF][START_REF] Casola | A SLA evaluation methodology in Service Oriented Architectures[END_REF][START_REF] Frankova | Service and protection level agreements for business processes[END_REF]. More recently, the advent of the Cloud concept, which is characterized by elastic and on-demand measurable services, has given rise to a new demand for such agreements [START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF][START_REF] De Chaves | SLA Perspective in Security Management for Cloud Computing[END_REF][START_REF]mOSAIC (Open source API and platform for multiple clouds[END_REF][START_REF] Meland | Expressing Cloud Security Requirements in Deontic Contract Languages[END_REF].

To facilitate dynamic and automatic SLA negotiation between the service consumers and service customers, including renegotiation of SLAs, a machinereadable contract language will be necessary. The WS-Agreement specification [START_REF]Open Grid Forum: Web Services Agreement Specification[END_REF] is a protocol for establishing SLAs between two parties, such as service providers and consumers. It is an open standard and it has been widely adopted for QoS support for service oriented architectures in web and grid contexts. WS-Agreement allows the use of any service term, and is therefore suitable for security agreements as well. The specification provides a template for the agreement, which consists of the name of the agreement (this is optional), the context (the participants and the lifetime of the agreement), and the agreement terms. The agreement terms are used to specify the obligations of the parties and the associated guarantee terms are used to provide assurance to the service consumer on the service quality and/or resource availability offered by the service provider. The current version of WS-Agreement does not include any ontology for incorporating security requirements in the SLAs, but the specification can relatively easily be extended with this feature [START_REF] Meland | Expressing Cloud Security Requirements in Deontic Contract Languages[END_REF].

Conclusion

We believe that the time of security SLAs has finally arrived. A security SLAs will not only ensure that the service consumer receives the required level of security, but may also put restrictions on the consumer, for example in terms of acceptable usage of the outsourced service. Effective security SLAs will also make sure that the service providers and consumers have a common understanding of the service terms. To achieve an open federated ecosystem of independent actors where services can be easily purchased, replaced and terminated whenever necessary, we need to see widespread use of machine-readable security SLAs. This will increase the uptake of service oriented architectures in new domains and foster innovation amongst developers, service providers, service customers, as well as end users.

Fig. 1 .

 1 Fig. 1. Example of Unified Communication as a Composite Service[1]

Fig. 2 .

 2 Fig.2. The SLA lifecycle[START_REF] Bernsmed | Security SLAs for Federated Cloud Services[END_REF]