Krzysztof Misztal
email: krzysztof.misztal@fis.agh.edu.pl

Jacek Tabor
email: tabor@ii.uj.edu.pl

Mahalanobis distance-based algorithm for ellipse growing in iris preprocessing

Keywords: Mahalanobis distance, ellipse growing, ellipse detection, pattern recognition, feature extraction

We introduce a new algorithm for ellipse recognition. The approach uses Mahalanobis distance and statistical and analytical properties of circular and elliptical objects. At first stage of the algorithm the starting configuration of initial ellipse is defined. Next we apply a condition which describes how much the shape is ellipse-like on the boundary points. The algorithm can be easily applied to detection of elliptical objects also on grayscale images. Moreover, we discuss the improvement in iris image preprocessing.

Introduction

Efficient ellipse and circle detection is one of the key tasks in image processing which is widely applied in various computer vision problems, in particular in the computation of the position of 3-D objects in robotic applications [START_REF] Nguyen | A real-time ellipse detection based on edge grouping[END_REF][START_REF] Greggio | Robotcub implementation of real-time least-square fitting of ellipses[END_REF], in the eye tracking in human-computer interfaces [START_REF] Takegami | An algorithm for model-based stable pupil detection for eye tracking system[END_REF], in face detection in biometric identification [START_REF] Jain | Fddb: A benchmark for face detection in unconstrained settings[END_REF], in character recognition [START_REF] Jin | An improved handwritten chinese character recognition based on localized ellipse model[END_REF]. Consequently the extraction of elliptic shapes form images has captured the interest of researchers for a long time [START_REF] Wong | A survey on ellipse detection methods[END_REF]. The methods used for this task can be categorized into several groups. The most widely used is based on Hough transform [START_REF] Illingworth | A survey of the hough transform[END_REF] which takes edge map of image as an input. Other group is based on the least square methods which mostly cast the ellipse fitting problem into a constrained matrix equation problem [START_REF] Fitzgibbon | Direct least square fitting of ellipses[END_REF][START_REF] Prasad | Methods for ellipse detection from edge maps of real images[END_REF]. Next category uses neural networks to find fast and approximately sufficient solutions [START_REF] Chiang | Detecting and recognizing traffic lights by genetic approximate ellipse detection and spatial texture layouts[END_REF]. The last group is focused on hybrid approach which makes it more flexible and efficient in many cases [START_REF] Dufrenois | Ellipse fitting with uncertainty and fuzzy decision stage for detection. application in videomicroscopy[END_REF][START_REF] Prasad | A hybrid approach for ellipse detection in real images[END_REF][START_REF] Chia | A split and merge based ellipse detector with self-correcting capability[END_REF][START_REF] Mai | A hierarchical approach for fast and robust ellipse extraction[END_REF][START_REF] Tabor | Detection of elliptical shapes via cross-entropy clustering[END_REF].

In this paper we introduce a new algorithm based on ellipse-growing idea which may help in iris preprocessing, and consequently in iris pattern recognition. A basic limitation of the current iris recognition methods [START_REF] Daugman | High confidence visual recognition of persons by a test of statistical independence[END_REF] is that they

(a) (b)
Fig. 1: Iris image reconstruction. Fig. 1a -original eye image with extracted iris and pupil. After the reconstruction (Fig. 1b) the shape of the iris was changed and it looks like a circle.

require an "on-axis" image of the eye. Clearly in most "real-life" pictures we have only a side-view of the eye, see Fig. 1a, which consequently yields that the eye resembles an ellipse instead of a circle. There are same approaches to deal with this problems which are based on the change in the representation, see [START_REF] Daugman | New methods in iris recognition[END_REF][START_REF] Chun | Iris recognition for iris tilted in depth[END_REF][START_REF] Dorairaj | Performance evaluation of non-ideal iris based recognition system implementing global ica encoding[END_REF]. We use slightly different approach which allows to use original Daugman's recognition process -namely we modify the picture by respective affine transformation so that the iris becomes circle-shaped. To do so we fit an optimal ellipse to the pupil of an eye, and apply to the picture the affine operation which transformes this ellipse into a circle, see Fig. 1b, which consequently transforms the iris almost into a circle.

To apply the above mentioned procedure we construct a new ellipse extraction method which is based on the Mahalanobis distance and uses the statistical and analytical properties of circular and elliptical objects. In the first step we use thresholding for finding the starting configuration of cluster -initial ellipse shape 3 . Next we use the specified condition to decide whether to add or not the points from the cluster boundary. Since during the calculation we examine just the boundary points of our cluster the calculation proceeds relatively fast. This condition verifies whether the current boundary element fits (with possible error δ) into the optimal ellipse fitted to the data with the use of Mahalanobis distance. More precisely, we add the boundary point x to the data-cluster C if

x -µ C Σ C = (x -µ C ) T Σ -1 C (x -µ C ) ≤ 2 + δ
, where µ C and Σ C denote the mean and covariance of C. The procedure is repeated until no boundary point belonging to the set satisfies the condition. The main advantage of the proposed method is that no complicated mathematical computation is involved in the implementation. Moreover, it is suitable for ellipse growing and ellipse extraction even on grayscale digital images and can be used for higher dimensional data.

The remainder of the paper is organized as follows: in the next section we present basics of the Mahalanobis distance. Moreover we provide a natural and intrinsic characterization of elliptical shapes, which is proper even in higher dimensions. In the third section we look more closely at the outcome information from the growing cluster. We use its characterization to correct the image. In section 4 we provide the results of experiments to illustrate the performance of our method. Finally, the last section contains some concluding remarks and possible directions of future investigations.

Theoretical background

In this section for the convenience of the reader we present a brief exposition of the Mahalanobis distance and indicate how these information can be used to construct ellipse growing algorithm.

It is well-known that the Euclidean distance between two points x and y in real space is given by

x -y = (x -y) T I(x -y), for x, y ∈ IR N .
where T denotes the transpose operation and I is an identity matrix.

It follows immediately that all points with the same distance from the origin x -0 = c satisfy x 2 1 + . . . + x 2 n = c 2 , which means that all components of an observation x contribute equally to the Euclidean distance of x from the center. But this situation in same cases is not optimal as we often prefer a distance such that components with high variability should have different weight than components with low variability. This can be obtained by using the Mahalanobis distance [START_REF] Mahalanobis | On the generalized distance in statistics[END_REF] defined for a positive definite matrix Σ by

x -y Σ = (x -y) T Σ -1 (x -y). (1)
In this case the set of all points with the same distance c from a given point

x 0 {x ∈ IR N |(x -x 0 ) T Σ(x -x 0 ) = c 2 }, (2)
describes and ellipsoid with center at x 0 . If x 0 = 0 then (2) is the general equation of ellipsoid centered at the origin. One can easily see that instead of calculating the Mahalanobis distance xy Σ we can equivalently transform the points by the matrix Σ -1/2 and compute the Euclidean distance of transformed points:

x -y Σ = Σ -1/2 x -Σ -1/2 y , see Fig. 2.
Let C denote the given subset of IR N . By µ C we denote the mean value of C, and by Σ C we mean covariance matrix of C. If we want to fit the Mahalanobis distance to our data set C, as Σ we take the covariance matrix Σ C of C. Remark 1. It is worth noting that Mahalanobis distance can be treated as a Euclidean distance in a transformed space, where the mean of the data C is transformed into zero:

C x → Σ -1/2 C (x -µ C ) ∈ IR N .
Fig. 2 presents the modification of origin given by this operation.

We are going to present some important observations crucial in the construction of our algorithm with the use of Mahalanobis distance. Consider the data uniformly distributed over the circle4 B(0, R) := {x ∈ IR 2 : x ≤ R} of radius R ≥ 0.

Remark 2. Consider the circle B(x 0 , R) with radius R on the plane. Then the covariance matrix Σ of the uniform probability distribution on B(x 0 , R) is given by Next theorem is essential for algorithm construction.

Σ = R 2 4 I. (3)
Theorem 3. Consider the uniform probability density on the ellipse E ⊂ IR 2 with covariance Σ E . Then

E = B Σ E (µ E , 2). ( 4
)
Proof. By applying the transformation described in Remark 1 we can reduce our reasoning to the case when E = B(0, R). Then by (3)

B Σ E (0, 2) = {x : x Σ E ≤ 2} = {x : x 2 Σ E ≤ 4} = {x : x T ( R 2 4 I) -1 x ≤ 4} = {x : x T x ≤ R 2 } = B(0, R) = E.
Fig. 3 presents the the given data-sets C (or more precisely the uniform density on the data) with fitted ellipses given by formula (4) in the presented objects. Observe that on the true ellipse E, by Theorem 3 the set E will coincide with B Σ E (µ E , 2). Thus two allow the increase, or more precisely, the grow, of the ellipse we allow error level δ > 0. In other words we allow to add a point to our data-cluster C if it satisfies the condition

x ∈ B Σ C (µ C , 2 + δ).
With different values of δ we will control how close to an ellipse we want to remain. Consequently, the complete version of the authors' algorithm can be described as follows:

initial conditions choose δ > 0 choose initial configuration of initial ellipse C compute mean value µ C and covariance matrix Σ C of C repeat added ← False for each x in ∂C do if x ∈ B Σ C (µ C , 2 + δ) then C := C ∪ {x} compute mean value µ C and covariance matrix Σ C of C added ← True end if end for until added
The algorithm finds the maximal "almost" ellipse (with given error δ) fitting in the input image by growing set C (Fig. 4). As we know the role of δ is how close to an ellipse we want to stay. However, to start the algorithm we need an explicit construction of the initial configuration of C -we usually select sufficiently large ellipse which fits into our data. To do so we apply the thresholding and some morphological operations (see Fig. 8).

Another important thing is the meaning of the boundary of the cluster ∂C -we understand by this the nearest point which are not the members of the cluster C. In case of digital image we have natural discretization of our space, so we can easily determine the boundary using von Neumann neighborhoods (see Fig. 5). Finally, we can optimize the calculation of the mean value and covariance matrix of cluster C. Following well-known remark shows the formula for on-line calculation of the mean and covariance of the modified data.

Remark 4. Let U, V be subsets of IR 2 , U ∩ V = ∅. We put w U ∪V = w U + w V , p U = w U w U ∪V , p V = w V w U ∪V .
where w U and w V denote the weights (cardinalities) of the sets U and V respectively. Then mean value and covariance matrix of set U ∪ V are given by

µ U ∪V = p U µ U + p V µ V , Σ U ∪V = p U Σ U + p V Σ V + p U p V (µ U -µ V )(µ U -µ V ) T .
The algorithm presented above has the ability to fit the maximal elliptical object in the image. It uses calculated value of Mahalanobis distance with the given error-level δ. Clearly, the error level can change the performance of the algorithm. Fig. 6 presents the output of the algorithm for different values of δ. Let now look at the starting configuration of the cluster. Fig. 7 presents the output of the algorithm for different initial configuration of cluster (the initial choice of set C). In most cases we obtain almost the same results. However there is a possibility to damage the algorithm effect as is presented at Fig. 7d and7h, where we start with initial set C given by an interval. Then the algorithm changes just the horizontal size of the cluster while the vertical stay unchanged.

Experimental results

In this section we present the two connected examples of the algorithm outcome for binary and grayscale iris image formats.

Binary image. In this case we apply our algorithm for thresholded image5 see first row at Fig. 8. The fitted ellipse contain the foreground of the image (marked on black with weight equals 1), since we use just the information obtained after thresholding. Fig. 8a and Fig. 8b presents the initial and outcome Grayscale image. In this case we also use the thresholded image for finding the initial ellipse. However in the next steps of the algorithm we use information about the color in each pixel added to the ellipse. This approach is better because we use full information we have and obtained result is more natural. More advanced example is presented at Fig. 1. As a outcome of the authors' algorithm we obtain the fitted ellipse, which statistical description can be used to define the transformation operation (compare Remark 1). Thus we can transform the iris image to make it more convenient for further processing by iris pattern recognition algorithms.

Conclusions

We presented a new method for ellipse growing based on properties of Mahalanobis distance, which can be used in detection of ellipses in: both binary and grayscale images. The numerical experiments have demonstrated that the algorithm works sufficiently well in both cases. We can apply the algorithm for iris preprocessing in real-life pictures where eyes are photographed sideways. Moreover, we can easily adapt the approach to higher dimensional data (for example in 3D medical images).

In the future work we plan to focus on the automation of the algorithm, in particular in the automatic detection of the necessary parameters (e.g. δ level) and image preprocessing methods (e.g. morphological operations). Furthermore we plan a more complete analysis of the behavior of the algorithm performance.

Fig. 2 :

 2 Fig. 2: Mahalanobis distance vs. Euclidean distance. Fig. (a) -Mahalanobis distance in the original on the data C, Fig. (b) -Euclidean distance in space transformed by the operation x → Σ -1/2 C (x -µ C ).

  Proof of this remark is quite simple and based on the change into polar coordinates (the N -dimensional version can be obtained by spherical representation of N -ball[21, Chap. 8, Thm. 4]).

Fig. 3 :

 3 Fig. 3: Different data-sets with ellipse constructed by equation (4).

  (a) initial configuration (b) 9th iteration (c) 25th iteration (d) 54th iteration

Fig. 4 :

 4 Fig. 4: Fitting ellipse -authors' algorithm iterations.

Fig. 5 :

 5 Fig. 5: The boundary points of the black pixel used in our algorithm.

1 Fig. 6 :

 16 Fig. 6: Different level of δ for the same image may give different results. Fig. 6ainput image. Fig. 6b initial configuration. Points added to cluster at the earlier stage of the algorithm change the result.

Fig. 7 :

 7 Fig. 7: Different initial configuration of the algorithm may give different outcome. The first row present the initial configuration, while the second row -the algorithm outcome.

Fig. 8 :

 8 Fig. 8: Application of the authors' algorithm for detection of the pupil and iris at the grayscale images [22] for binary images (first row) and grayscale images: (a), (d) -initial configuration of a cluster, (b), (e) -final size of the cluster, (c), (f) -fitted ellipse at original image.

This step can be omitted or replaced by other procedure which ends with proper initial configuration of the cluster.

We consider Euclidean norm in this paper.

We use same morphological operations for remove out-layers and reduce noise.

Acknowledgments

This work was supported by the Polish National Centre of Science Grant No. 2012/07/N/ST6/02192.


Magdalena Ladniak
email: mladniak@geol.agh.edu.pl

Adam Piórkowski

Mariusz M Lynarczuk

The data exploration system for image processing based on server-side operations

Keywords: image mining, image processing, databases, user defined functions, image clusterization

In this paper the possibilities for construction of an ad hoc search system to examine large-sized raster image data sets, e.g. rock images or medical images, for analysis of its characteristic parameters are presented. A new solution for image exploration based on any attributes extracted with computer image analysis by using extensions for serverside operations is proposed.

Introduction to image exploration

Most of scientific disciplines belonging to natural sciences are based on experimental data. Although theories, obviously stimulate the development of new branches, but in doubtful cases, experimental verification is of pivotal importance [START_REF] Tadeusiewicz | Data mining as a chance for relative cheap scientific discoveries obtained by looking up seemingly fully explored empirical data. Statystyka data mining w badaniach naukowych[END_REF]. In recent years an increasing need for supporting measurements of rock structures with image analysis methods is observed. These methods are being successfully implemented into researches related to geology [START_REF] Mlynarczuk | Some Remarks on the Application of Image Analysis and Image Processing for the Description of the Geometrical Structures of Rock[END_REF], mining [START_REF] Wierzbicki | Structural aspects of gas and dolomite outburst in Rudna copper mine, Poland[END_REF] and rock mechanics [START_REF] Mlynarczuk | Description and classification of rock surfaces by means of laser profilometry and mathematical morphology[END_REF]. Image data exploration is a current issue. This includes a number of approaches to image mining [START_REF] Wang | Application of fuzzy cluster analysis for medical image data mining[END_REF][START_REF] You | Elliptic Object Features Extraction and Measurement in Image Data Mining[END_REF]. However, many authors often present no solutions enabling computations and restrict themselves to theoretical deliberations. A classification scheme for medical images has been proposed in [START_REF] Mazurkiewicz | A parallel environment for image data mining[END_REF], but this solution requires image processing beyond a database that may pose a problem when integrating with such data exploration systems as Weka or Statistica. The aim of this paper is to consider a possibility for construction of a system for mining a large-sized set of rock microsections by using database-side processing. Such solution avoids a complex construction of heterogenic environment. The weak points of the existing solutions are strong dependence on interfacing with various versions of different software that can make uniform application impossible, especially when the software is updated. The use of external programs for image processing might cause difficulties with file arrangement, description and ordering in the case of large amount of photos. That is why the Authors propose a system that provides data-base side raster image storage and analysis, thus allowing data exploration with the data mining software commonly used. Research on preliminary image clasterization by the describing parameters is proposed.

An approach to image selection using server-side operations

The literature, which is the Authors known, on this subject is limited to the description of the image processing only on the local computer and using images in the computer local memory or imported from databases. The Authors think that the future of image analysis involves the calculation of the total transfer of database servers. However, desktop computers (in the form of desktops, laptops, tablets, smartphones etc.) will be used only to manage the calculations and to review the obtained results.

The idea of data processing and analysis by using database technologies and statistical tools

Database queries can be processed both with a database-side engine and from the statistical tool level. At baseline the database contains only raw images with a basic description like for example their names. An effect of such query is a set of numerical data and its further analysis depends only on analyst needs. Based on observations he/she can request the database to make an additional measurement for a selected feature and to store the result permanently or temporarily in the database. Such solution enables easy and direct extraction of desired information without the use of surplus software. Information flow and schematic context of analysis for the presented example is presented below (Figure 1). The detailed description of the structure and performance issues of the proposed system are available in the literature [START_REF] Ladniak | Structure of systems for data exploration for raster images[END_REF]. The use of the mechanism of User Defined Functions in a database environment gives the user complete freedom in creating his own image processing operations and advanced algorithms. These algorithms were created by the Authors for the purpose of this study. Absolute freedom in designing a database schema should be emphasized here. The stored images can be taken out by DMBS at the user's request, processed and the results can be placed into a result table. Any number of operations can be involved each time in processing. This may be either a single operation that builds a complex algorithm or a set of cyclic image processing operations. Any number of input images can be processed. In addition, it is possible to write images being partial solutions in the database. The mechanisms used allows easy reference also to these images what is of utmost importance to the creation process and verification of proper operation of new image processing algorithms. The application of the proposed solution enables construction of knowledge base of very large number of parameters. This can be used in the next step in statistical data analysis.

Fig. 1. Information flow and schematic context of analysis

There are many tools for the whole process of converting data into usable knowledge. In study described here Weka (Waikato Environment for Knowledge Analysis) was used. This is an open source software under General Public License. The possibility of direct communication with a database system and graphic presentation of data were utilized in this software. Thanks to provided communication with a database the user's request for image processing is sent directly by doing SQL (Structured Query Language) queries. In practice this indicates a capability to run image analysis routines directly from a statistical tool when the user sees a potential need for an additional analysis. This approach is well known in methods of gaining knowledge from a sets of numerical data, for example in time series analysis [START_REF] Chuchro | The structure of influent time series in wastewater treatment plants[END_REF].

Combination of search criteria

It is often necessary to make a selection based on many criteria concurrently. An example is finding the images for which a group of parameters fulfills the specified standard conditions. The manual solution of this task induces a series of operations to be executed connected with switching between various solutions, e.g. 'get from the database, batch convert, save results to a file, import to statistical tool'. The Authors propose to move such operations onto database platforms, thus allowing uniform combination of search criteria. This consists of constructing appropriate conditions to narrow and group the query result. The solution unifies the data storage method, avoid problems related to entering various access paths to images, systemizes places where addition information on computed parameters are stored and allows return to results at the selected stage of analysis.

Input data

The input data in the system under consideration are images of rock specimen microsections made by the Authors. The process of test material preparation consisted of taking a rock specimen, cutting it into thin discs, impregnating with an adhesive with pigment addition, polishing, taking a photo with a digital camera integrated with a microscope at 100x magnification [START_REF] Mlynarczuk | Application of image analysis and mathematical morphology to quantitative description of rock fracture surface[END_REF]. The impregnation process contributed in gaining clear color marking of pore spaces, its shape and size [START_REF] Mlynarczuk | Stereological description of sedimentary rocks with methods of image analysis[END_REF]. This fact was the basis for selection of segmentation algorithm based on color analysis.

Preprocessing

Image processing is a well known dynamically developing discipline, so its basic issues were omitted here, while referencing to the existing publications [13-17, ?].

In computer image analysis the purpose of transformations is most often to gain a properly segmented binary image. To obtain such image a series of transformations of the input image is carried out. As a result a contrast imaging is obtained where objects (e.g. potential pore cross sections) are clearly distinguishable from the background [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF].

Threshold binarization

To prepare a binary image two segmentation algorithms were tested by using threshold binarization:

-In the first algorithm, the thresholds were chosen empirically based on color analysis and the YIQ color space model was employed. As an input signal represent the chrominance information (I channel) was used. -In the second algorithm, the thresholds were chosen by maximum entropy method [START_REF] Tadeusiewicz | Komputerowa analiza i przetwarzanie obrazow[END_REF]. For further analyses the results of binarization with manually chosen thresholds were used because of better results of the method.

Noise reduction

The next stage of preprocessing was to remove the smallest objects that did not indicate any pore voids. The feature of microscopic measurements is that they are made at a specified magnification. On this basis the object elimination criterion was established. The isolated small areas (here of few pixels in size) were removed. The boundaries of the marked areas were smoothened. To do it the erosion and dilatation operations were used. When these operations are used separately they cause different changes in surface area of objects under transformation. Erosion decreases it, while dilatation increases it. To eliminate this effect the transformations being a superposition of the previous ones, namely opening and closing were used. Opening results in removal of small objects without significant object size changes. The aim of closing is to fill in narrow nicks and small holes inside the object, while having no significant effect on its shape [START_REF] Coster | Precis d'Analyse d'Images[END_REF]. The set of parameters used in analyses is presented below.

Search parameters

The starting point for making automatic measurements is proper segmentation.

In the case of binary images an object should be understood as a set of pixels of brightness 1 connected to each other. Despite the fact that measuring methods are quite well defined, its limitations should be always taken into account. To convert the values of some parameters into nominative values it is necessary to do image calibration, i.e. entering information about its actual dimensions. For reasons of clarity this process was omitted in this paper [START_REF] Mlynarczuk | Potential applications of image analysis and mathematical morphology to stereological analysis of rock structures[END_REF].

-Surface area -area was calculated by summing all pixels within the object.

-Coefficient of porosity -the value of this coefficient was assumed to be the ratio of pore volume to the total volume of tested specimen expressed in percent [START_REF] Jeske | Mechanika gruntow[END_REF]. -Number of objects -the counting process for such objects was carried out by using the labeling algorithm. This consists of viewing the binarized image line by line until a point belonging to the object is encountered. Then it is assigned a label and the values of preceding pixels are analyzed. The labeled vertices are based on associativity to neighbor values. Depending on neighborhood type it is possible to analyze both higher or left neighbor (4connected neighborhood) or three higher and one left neighbor (8-connected neighborhood) [START_REF] Radomski | Determination of specific surface area of the granular materials in aspects of its use in selected technological processes[END_REF]. -Average object chord length -it is possible to determine the average chord lengths at vertical and horizontal. To do it the method consisting of computing the average length of the intersection between the segmented image and the regular set of horizontal/vertical lines was used (refinement was defined symmetrically).

-Specific surface area -specific surface area is understood as the surface area of the skeleton of porous medium per the total volume of this medium [START_REF] Lay | Image processing software -multiple solutions for a single problem[END_REF].

The knowledge of object chord lengths allows specific surface area to be computed from the following formula known from the literature [START_REF] Bodziony | Stereology as image analysys method of agricultural materials[END_REF]:

S = 4 * n N (1)
where: n -number of objects (chords) being superposition of the image and the regular grid of vertical/horizontal lines N -length of all lines belonging to the regular grid -Object perimeter length -to determine approximate length of object perimeters in the photographs the erosion subject image was subtracted from the original one, and then summing of the marked pixels was done.

Analysis results

The described measuring methodology was implemented in detection of potential pore cross sections in rock images. There following rocks were selected: dolomite from Buszewo, dolomite from Baszyna, dolomite from Koscian and limestone from Santok. The photographs were taken under optical microscope equipped with a specialized CCD camera at magnification 100x [START_REF] Ladniak | Structure of systems for data exploration for raster images[END_REF]. The set search criterion was strictly defined values of parameters describing the material shown below in photographs. Sample result of clasterization according to criteria: origin place (Buszewo, Baszyna, Koscian, Santok) and specific surface area (Figure 3), origin place (Buszewo, Baszyna, Koscian, Santok) and number of objects Figure 4). Efficiency The efficiency tests were carried out on the set of 1000 photographs at the standard size of 1024x768 pixels. The Microsoft SQL Server 2012 engine was used based on the performed preminaly tests [START_REF] Ladniak | Structure of systems for data exploration for raster images[END_REF]. For programming the following technologies were used: Transact-SQL, and SQL CLR (CLR -Common Language Runtime) to create procedures that then to be used by the database engine as an external library [START_REF] Radomski | Determination of specific surface area of the granular materials in aspects of its use in selected technological processes[END_REF]. The procedures were stored in The Microsoft.NET 4.5 using C# language. Two computer environments were used:

- The preprocessing performed by using a Transact-SQL language is an extremely time-consuming task. By adding external authorial libraries CLR to the database system and using parallel computing it was possible to speed up the research considerably, thus the system executes the tasks in an adequate time. The Parallel Class (Microsoft.NET 4.5) that provides support for parallel loops and regions was used [START_REF] Toub | Patterns of parallel programming. Understanding and applying parallel patterns with the .Net Framework 4 and Visual C#[END_REF]. The lead times, serial as s and parallel as p, are listed in the table below.

Conclusions

The tests we carried out demonstrate possibilities for construction and practical use of the system (understood as a set of user's database functions) that enables analysis to be carried out based on the results of searching by the specified parameters. The Authors' intention was to present possibilities for construction of a dedicated system to meet the needs of the specified problem related to automatic measurements of rock geological structures where parametrization plays an important role. Execution of complicated conditionally point computations in image analysis is a time-consuming task for the database server, so the Authors undertake research on timing optimization of such solutions. Execution of complicated conditionally point computations in image analysis is a time-consuming task in general [START_REF] Bielecki | Recognition of two-dimensional representation of urban environment for autonomous flying agents[END_REF][START_REF] Bielecka | Fuzzy syntactic approach to pattern recognition and scene analysis[END_REF] so the Authors undertake research on timing optimization of such algorithms implemented on database servers by using more advanced methods of database systems and parallel programming. It was accepted that benefits resulting from independence from various systems, its cooperation (also in the context of versioning) are so such large that further studies are justified and should be continued.

Fig. 2 .

 2 Fig. 2. Sample results of binarization by using methods 1 and 2

Fig. 3 .

 3 Fig. 3. Sample result of graphical clasterization, X axis -origin place (from the left in sequence: Santok (1-250), Koscian (251-500), Baszyna (501-750), Buszewo (751-1000)), Y axis -specific surface area.

Fig. 4 .

 4 Fig. 4. Sample result of graphical clasterization, X axis -origin place (from the left in sequence: Santok (1-250), Koscian (251-500), Baszyna (501-750), Buszewo (751-1000)), Y axis -number of objects.

Table 1 .

 1 Function execution time for selected user defined functions.

				Times [ms]
		Operations:	TSQL 1 2	1	CLR	2
			s	s	s p s p
		Erosion/Dilatation	33167 25741 156 75 64 33
	preprocessing	Opening/Closing Logical: AND, OR Subtracting/Summing Conversions between color spaces Threshold binarization	65967 34331 304 160 125 53 7873 2590 12 7 5 2 7827 2481 14 8 6 3 9437 4321 8 5 11 6 9388 4305 26 17 11 6
		Maximum entropy method	10451 5692 28 18 12 8
		Determination of surface area	1925 975 8 6 4 2
	analysis	Determination of coefficient of porosity Determination of specific surface area Counting the number of objects	1947 1036 8 5 4 2 10986 4087 29 21 13 10 10662 6015 22 -9 -
		Counting the chord diameter length	18302 9965 31 19 13 8

Acknowledgement

This work was financed by the AGH -University of Science and Technology, Faculty of Geology, Geophysics and Environmental Protection as a part of statutory project.


Dariusz Borkowski

Katarzyna Jańczak-Borkowska

Image Restoration using Anisotropic Stochastic Diffusion Collaborated with Non Local Means ⋆

Keywords:

In this paper we explore the problem of the reconstruction of images with additive Gaussian noise. In order to solve this inverse problem we use stochastic differential equations with reflecting boundary and famous non local means algorithm. Expressing anisotropic diffusion in terms of stochastic equations allows us to adapt the concept of similarity patches used in non local means. This novel look on the reconstruction problem is fruitful, gives encouraging results and compares favourably with other image denoising filters.

Introduction

Let D be a bounded, convex domain in R 2 , u : D → R be an original image and u 0 : D → R be the observed image of the form

u 0 = u + η,
where η stands for a white Gaussian noise. We assume that u and u 0 are appropriately regular. We are given u 0 , the problem is to reconstruct u. This is a typical example of an inverse problem [START_REF] Aubert | Mathematical problems in image processing[END_REF].

Problem of image denoising using fully automatic and reliable methods is one of the most important issues of digital image processing and computer vision. Efficient and effective reconstruction of images is an essential element of most image processing and recognising algorithms. Reconstruction algorithms allow us to make initial treatment of data for further analysis, which is very important, especially in astronomy, biology or medicine.

Various techniques were proposed to tackle this inverse problem. One may quote the linear filtering, DCT [START_REF] Yaroslavsky | Local adaptive image restoration and enhancement with the use of DFT and DCT in a running window[END_REF], wavelets theory [START_REF] Chan | Image Processing and Analysis -Variational, PDE, wavelet, and stochastic methods[END_REF][START_REF] Donoho | Ideal spatial adaptation via wavelet shrinkage[END_REF], variational methods [START_REF] Chan | Image Processing and Analysis -Variational, PDE, wavelet, and stochastic methods[END_REF][START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] and stochastic modelling which are generally based on the Markov field theory and Bayesian approach [START_REF] Chan | Image Processing and Analysis -Variational, PDE, wavelet, and stochastic methods[END_REF][START_REF] Geman | Stochastic relaxation, gibbs distributions and the bayesian restoration of images[END_REF][START_REF] Richardson | Bayesian-based iterative method of image restoration[END_REF]. The most important methods in the last decade in image processing have been methods driven by nonlinear diffusion equation [START_REF] Catte | Image selective smoothing and edge detection by nonlinear diffusion[END_REF][START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF][START_REF] Weickert | Theoretical Foundations Of Anisotropic Diffusion In Image Processing[END_REF][START_REF] Weickert | Coherence-Enhancing Diffusion Filtering[END_REF], where some papers [3-7, 17, 26, 27] involve advanced tools of stochastic analysis such as stochastic differential equations. In another class, one could include methods that take advantage of the non-local similarity of patches in the image. Among the most famous, we can name non local means (in short NL-means) [START_REF] Buades | A non local algorithm for image denoising[END_REF][START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF], BM3D [START_REF] Dabov | Image denoising by sparse 3D transform-domain collaborative filtering[END_REF][START_REF] Danielyan | Bm3d frames and variational image deblurring[END_REF][START_REF] Katkovnik | Decoupled inverse and denoising for image deblurring: variational BM3D-frame technique[END_REF], NL-Bayes [START_REF] Lebrun | Implementation of the Non-local Bayes image denoising[END_REF] and K-SVD [START_REF] Aharon | K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation[END_REF][START_REF] Mairal | Sparse representation for color image restoration[END_REF].

In this paper we focus on two methods using to image denoising: anisotropic diffusion and non local means. We propose a method which combines these two approaches. Reconstructed pixel is expressed in terms of stochastic anisotropic diffusion which is itself driven by similarity of patches of the noisy image.

Mathematical Preliminaries

Let D ⊂ R n be a domain with closure D and boundary ∂D. Let T > 0 and by

C([0, T ]; R n ) we denote a set of continuous functions f : [0, T ] → R n . Definition 1. Let y ∈ C([0, T ]; R n ), y 0 ∈ D. A pair (x, k) ∈ C([0, T ]; R 2n
) is said to be a solution to the Skorokhod problem associated with y and D if

1. x t = y t + k t , t ∈ [0, T ], 2. x t ∈ D, t ∈ [0, T ], 3. k is a function with bounded variation |k| on [0, T ], k 0 = 0 and k t = ∫ t 0 n s d|k| s , |k| t = ∫ t 0 1 {xs∈∂D} d|k| s , t ∈ [0, T ],
where n s = n(x s ) is an inward normal unit vector at x s ∈ ∂D.

It is known that if D is a convex set, then there exists a unique solution to the Skorokhod problem [START_REF] Tanaka | Stochastic differential equations with reflecting boundary condition in convex regions[END_REF]. Definition 2. Let (Ω, F, P) be a probability space.

1. An n-dimensional stochastic process X = {X t ; t ∈ [0, T ]} is a parametrised collection of random variables defined on a probability space (Ω, F, P) with values in R n . For each fixed ω ∈ Ω the function X t (ω), t ∈ [0, T ] is called a trajectory of X and is denoted by X(ω).

A filtration

(F t ) = {F t ; t ∈ [0, T ]} is a nondecreasing family of sub-σ-fields of F, i.e. F s ⊆ F t ⊆ F for 0 ≤ s < t ≤ T . By (F X t )
we denote a filtration generated by a process X, i.e. In what follows, by W = {W t ; t ∈ [0, T ]} we shall denote a Wiener process starting from zero. We assume that we are given a point x 0 ∈ D and some function σ : R n → R n × R m . Definition 4. Let Y be an (F t ) adapted process. A pair (X, K D ) of (F t ) adapted processes is called a solution to reflected stochastic differential equation (in short reflected SDE)

F X t = σ(X s ; 0 ≤ s ≤ t). 3. A stochastic process X is adapted to the filtration (F t ) (X is (F t ) adapted) if for each t ∈ [0, T ], X t is F t -
X t = x 0 + ∫ t 0 σ(X s ) dW s + K D t , t ∈ [0, T ], (1)
if (X, K D ) is a solution to the Skorokhod problem associated with

Y t = x 0 + ∫ t 0 σ(X s ) dW s , t ∈ [0, T ] and D.
The process X is called the process with reflection. The proof of existence and uniqueness of the solution to reflected SDEs can be found in [START_REF] Tanaka | Stochastic differential equations with reflecting boundary condition in convex regions[END_REF].

Stochastic Anisotropic Diffusion

Following [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF][START_REF] Weickert | Coherence-Enhancing Diffusion Filtering[END_REF] we propose the following stochastic model of an anisotropic diffusion:

X t = x + ∫ t 0    - (Gγ * u0)x 2 (Xs) |∇(Gγ * u0)(Xs)| , 0 (Gγ * u0)x 1 (Xs) |∇(Gγ * u0)(Xs)| , 0    dW s + K D t ,
where u xi (y) = ∂u ∂xi (y). To avoid false detections due to noise, u 0 is convolved with a Gaussian kernel

G γ (x) = 1 2πγ 2 e - |x| 2
2γ 2 (in practice a 3 × 3 Gaussian mask). The reconstruction pixel is given by

u(x) = E [u 0 (X T )] ≈ 1 M M ∑ i=1 u 0 (X m T (ω i )), (2)
where X m (ω i ) is the approximation of trajectory of stochastic process X and M is the number of Monte Carlo method iterations.

Euler's Approximation

Consider the following numerical scheme

X m 0 = X 0 , (3) X m t k = Π D [X m t k-1 + σ(X m t k-1 )(W t k -W t k-1 )], k = 1, ..., m,
where t k = kh, h = T m , k = 0, 1, ..., m and Π D (x) denotes a projection of x on the set D. Since D is convex, the projection is unique. Theorem 1. Let (X, K D ) be the solution to the reflected SDE [START_REF] Aharon | K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation[END_REF]. If there exists

C > 0 such that ∥σ(x) -σ(y)∥ 2 ≤ C|x -y| 2 , then lim m→+∞ |X m T -X T | = 0 almost surely.
The proof of the above theorem can be found in [START_REF]Euler's approximations of solutions of SDEs with reflecting boundary[END_REF].

Modified Diffusion

The numerical scheme (3) gives good results, but only with a small value of the time-step parameter h = T m (for example h = 0.05). Calculating the mean value using Monte Carlo method for small h is not effective and takes a long time. To omit this problem, we improve the scheme (3) by adding a controlled parameter p [START_REF] Borkowski | Modified diffusion to Image Denoising[END_REF].

X m 0 = X 0 , H m t k = Π D [X m t k-1 + σ(X m t k-1 )(W t k -W t k-1 )], (4)
X m t k =    H m t k , if Θ, X m t k-1 , elsewhere, k = 1, 2, ..., m,
where by Θ we mean the condition

|(G γ * u 0 )(H m t k ) -(G γ * u 0 )(X m t k-1 )| < p.
Note that the parameter p > 0 guarantees that if the image exhibits a strong gradient then the process X m diffuses as a process with small value of the parameter h and at locations where variations of the brightness are small, the process X m can diffuse with a large value of h (for example h = 4). The figure Fig. 1. illustrates a difference between the scheme (3) and the scheme (4). There are shown three examples of trajectories of the process u 0 (X m t ) from the pixel A to the pixel B. Trajectories (I) and (III) were generated using the scheme (3) for large and small value of the parameter h, respectively. Trajectory (II) was generated using the scheme (4) for large h. It is easy to see, that at locations where the image is constant, trajectory (II) diffuses as trajectory (I). At locations where the image has strong gradient, the trajectory (II) is similar to the trajectory (III).

For small h or p = +∞ (in practice p > 255) the numerical scheme ( 4) is equivalent to the scheme (3).

Modified Diffusion with Random Terminal Time

At locations where gradient is large in all directions it is possible that condition Θ does not hold as many times as we would expect. To avoid this we propose Fig. 1. Example of trajectories of the process (Gγ * u0)(X m t ) from pixel A to B: (I)with using the scheme (3) and large h, (II) -with using the scheme (4) and large h, (III) -with using the scheme (3) and small h. the following modification [START_REF] Borkowski | Euler's Approximations to Image Reconstruction[END_REF]:

X m 0 = X 0 , H m t k = Π D [X m t k-1 + σ(X m t k-1 )(W t k -W t k-1 )], X m t k =    H m t k , if Θ, X m t k-1 , elsewhere, k = 1, 2, ..., τ m ,
where τ m = min{k; k ≥ m and Θ is true m times}.

Terminal time τ m guarantees that the numerical simulation of the diffusion trajectory gives at least m values of X m t k which differ from the value in the previous step.

Implementation

The above schemes are simple to implement. Observe that the schemes works well only if the model of the digital image G γ * u 0 is continuous. In practice, we can use a linear interpolation to get the value of the image G γ * u 0 , for any point x ∈ D. We note also that since W t k -W t k-1 ∼ N (0, t k -t k-1 ), it can be approximated by a random number generator of the normal distribution.

Non Local Means Algorithm

In this section we cite results from [START_REF] Buades | A non local algorithm for image denoising[END_REF][START_REF] Buades | A review of image denoising algorithms, with a new one[END_REF][START_REF] Buades | Non-Local Means Denoising[END_REF].

Let v = {v(i)|i ∈ I} be a discrete noisy image and {w(i, j)} be the weights that depend on the similarity between the pixels i and j and satisfy the usual conditions 0 ≤ w(i, j) ≤ 1 and

∑ j w(i, j) = 1. The reconstructed value N L(v)(i)
for a pixel i is defined as a weighted average of all pixels in the image

N L(v)(i) = ∑ j∈I w(i, j)v(j).
The weight w(i, j) depends on the similarity of the intensity gray level vectors of neighbourhoods centred at pixels i and j. Definition 5. A neighbourhood system on I is a family N = {N i } i∈I of subsets of I such that for all i ∈ I,

1. i ∈ N i , 2. j ∈ N i ⇒ i ∈ N j .
The subset N i is called the neighbourhood or the similarity window of i.

The weights can be defined by

w(i, j) = 1 Z(i) e -d(N i ,N j ) s 2
where Z(i) is the normalising factor

Z(i) = ∑ j e -d(N i ,N j ) s 2
and d(N i , N j ) is some measure of distance between intensity gray level vectors of similarity windows. The number s is a parameter that controls the decay of the exponential function.

In original approach [START_REF] Buades | A non local algorithm for image denoising[END_REF] the authors propose to use square windows of fixed size as similarity windows (see Fig. 2) and the distance between neighbourhoods was measured as a decreasing function of the weighted Euclidean distance i.e.

d(N i , N j ) = ∥v(N i ) -v(N j )∥ 2
2,a , where v(N i ) = (v(j), j ∈ N i ) and a > 0 is the standard deviation of the Gaussian kernel.

Patchwise Implementation

By ∥B i,r -B j,r ∥ 2 we denote the Euclidean distance between B i,r and B j,r , where patch B i,r means a neighbourhood of a size 2r + 1 × 2r + 1 pixels centred at i. Patchwise implementation [START_REF] Buades | Non-Local Means Denoising[END_REF] is based on a simple observation. When computing the Euclidean distance ∥B i,r -B j,r ∥ 2 , all pixels in the patch B i,r have the same importance, and therefore the weight F (∥B i,r -B j,r ∥ 2 ), where F is a decreasing function, can be used to denoise all pixels in the patch B i,r and not only i. For computational purposes the searching of similar windows can be restricted from all pixels in the image to some square window B i,f . The denoising of an image v and a certain patch B i,r is equal to

Bi,r = 1 Z ∑ j∈B i,f v(B j,r )w(B i,r , B j,r ), where Z = ∑ j∈B i,f w(B i,r , B j,r
) and the weight function is given by

w(B, Q) = e - max ( ∥B-Q∥ 2 2 -2ρ 2 ,0.0 ) s 2
. Here by ρ we denoted the standard deviation of the noise and by s the filtering parameter set depending on the value of ρ. The weight function is chosen in order to average similar patches up to noise. That is, patches with square distances smaller than 2ρ 2 are set to 1, while larger distances decrease rapidly accordingly to the exponential kernel. By applying the procedure for all patches in the image, we will get (2r + 1) 2 possible estimates for each pixel. These estimates can be finally averaged at each pixel location in order to build the final denoised image

N L(v)(i) = 1 (2r + 1) 2 ∑ j∈Bi,r
Bj,r (i).

Anisotropic Stochastic Diffusion Collaborated with Non Local Means

In this section we propose a new method of the image reconstruction based on modified diffusion with random terminal time and patchwise implementation of non local means. In the case of numerical scheme with random terminal time the reconstructed formula of anisotropic diffusion (2) can be written as

u(x) ≈ M ∑ i=1 1 M u 0 (X m τm (ω i )),
which means that each pixel u 0 (X m τm (ω i )) is weighted with the value 1 M . But since pixels have different intensities we may consider them with different weights depending on their neighbourhood. We follow NL-means algorithm and propose a new method of the image restoration based on modified diffusion but such that the weights depend on patches similarity:

u(x) = 1 Z M ∑ i=1 u 0 (X m τm (ω i ))w(B x,r , B X m τm (ωi),r ).
In the above formula we used the following notations:

Z = M ∑ i=1 w(B x,r , B X m τm (ωi),r ), w(B, Q) = e - max ( ∥B-Q∥ 2 2 -2ρ 2 ,0.0 ) s 2 X m 0 (ω i ) = x, H m t k (ω i ) = Π D [X m t k-1 (ω i ) + σ(X m t k-1 (ω i ))(W t k -W t k-1 )], X m t k (ω i ) =    H m t k (ω i ), if Θ, X m t k-1 (ω i ), elsewhere, k = 1, 2, ..., τ m .
The meaning of the parameters in the new method is the same as in original approaches. This method of the image reconstruction we will call the stochastic diffusion with non local means (in short SDNLM).

Experimental Results

Some measures of quality for our evaluation experiments regarding new method, non local means algorithm, anisotropic Perona-Malik model [START_REF] Perona | Scale-space and edge detection using anisotropic diffusion[END_REF] and anisotropic stochastic diffusion are presented in Table 1, Table 2, Fig. 3 and Fig. 4. The results refer to greyscale images pirate and cameraman corrupted with the Gaussian noise with standard deviation ρ. The maximum values of Peak Signal to Noise Ratio (in short PSNR) and Structural Similarity Index (in short SSIM) obtained using tested methods are given in tables. Parameters of SSIM were set to the default values as recommended by [START_REF] Wang | Image quality assessment: From error visibility to structural similarity[END_REF].

The analysis of the measures of image quality shows that in most cases the new method performs better. Moreover, when comparing the figures one can observe that the image created by the SDNLM is visually more pleasant. The reason for this is that the NL-means approach shows clear evidence of a halo of noise effect around the edges whereas anisotropic diffusions smooth details too much.

Conclusion

In this paper we proposed a new method of digital image denoising. Expressing anisotropic diffusion in terms of stochastic equations allows us to adapt the idea As a future work, the algorithm can be extended to vector valued images, in particular, colour images.

Fig. 2 .

 2 Fig. 2. Idea of NL-means from [8]: Pixels j and k have large weights w(i, j) and w(i, k) because their similarity windows are similar to that of i. The weight w(i, l) is much smaller because the intensity grey values in the similarity windows are very different.

Fig. 3 .Fig. 4 .

 34 Fig. 3. a) Original image: 512 × 512 (top) and 128 × 128 (bottom) b) Noisy image: ρ = 15 c) NL-means: SSIM = 0.9245 d) Stochastic anisotropic diffusion: SSIM = 0.9246 e) Perona-Malik: SSIM = 0.9204 f) New method: SSIM = 0.9257

  measurable random variable.

	Definition 3. Let Y be (F t ) adapted process with continuous trajectories,
	Y 0 ∈ D. We say that a pair (X, K) of (F t ) adapted processes is a solution
	to the Skorokhod problem associated with Y and D, if for almost every ω ∈ Ω,
	(X(ω), K(ω)) is a solution to the Skorokhod problem associated with Y (ω) and D.

Table 1 .

 1 Maximum values of PSNR

Image Noise NL-means Stoch. anisotropic Perona-New method

		ρ algorithm [10]	diffusion [6]	Malik [21]
	Pirate	10	33.0394	32.0450	32.8268	33.1379
		15	30.7474	30.5158	30.8167	30.8944
		20	29.6731	29.3619	29.5095	29.6914
	Cameraman 10	35.3814	35.2304	34.9002	35.8238
		15	32.9025	33.7815	32.8394	33.8727
		20	32.1931	32.2683	31.2357	32.1571

Table 2 .

 2 Maximum values of SSIMfrom non local means approach. The new method takes what is the best both from anisotropic diffusion and non local means method: reconstructed image is smooth and at the same time details are preserved.

	Image Noise NL-means Stoch. anisotropic Perona-New method
		ρ algorithm [10]	diffusion [6]	Malik [21]
	Pirate	10	0.9562	0.9533	0.9519	0.9558
		15	0.9245	0.9246	0.9204	0.9257
		20	0.8952	0.8935	0.8913	0.8974
	Cameraman 10	0.9600	0.9583	0.9436	0.9606
		15	0.9334	0.9369	0.9173	0.9393
		20	0.9214	0.9144	0.8838	0.9196

⋆ This research was supported by the National Science Centre (Poland) under decision number DEC-2012/07/D/ST6/02534


Muhammad Kazim
email: muhammad.kazim@seecs.edu.pk

Rahat Masood

Awais Muhammad

Abdul Ghafoor Shibli
email: awais.shibli@seecs.edu.pk

Abbasi

Security Aspects of Virtualization in Cloud Computing

Keywords: Cloud computing, Cloud virtualization security, Cloud service provider, Hypervisor, Virtual machines, Disk images

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cloud computing is becoming popular among IT businesses due to its agile, flexible and cost effective services being offered at Software, Platform and Infrastructure level. Software as a Service (SaaS) allows users to access applications hosted by different vendors on Cloud via internet. Platform as a Service (PaaS) enables developers to code, test and deploy their applications on IaaS. In Infrastructure as a Service (IaaS) model, Cloud providers offer services such as computing, network, storage and databases via internet. IaaS is the base of all Cloud services with PaaS and SaaS both built upon it. The primary features of IaaS are elasticity and virtualization [START_REF] Orlando | Cloud computing service models[END_REF].

Virtualization enables a single system to concurrently run multiple isolated virtual machines (VMs), operating systems or multiple instances of a single operating system (OS). However, there are still open challenges in achieving security for Cloud virtualization. Research has been done to explore major security issues related to virtualization in Cloud. The standard bodies in computing security including National Institute of Standard Technologies (NIST) [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF], Cloud Security Alliance (CSA) [START_REF] Brunette | Security guidance for critical areas of focus in cloud computing v2.1[END_REF], and Payment Card Industry Data Security Standard (PCI DSS) [4] have issued guidelines on virtualization technologies. These guidelines discuss security issues related to virtualization in Cloud and provide recommendations for secure virtualization environments. However, the holistic view of virtualization security has not been presented in a composed form. Furthermore, there is need to investigate existing virtualization security solutions proposed in literature to mitigate different attacks.

This paper analyzes the security issues of Cloud virtualization from three different aspects including the security requirements, attacks and security solutions of virtualization. Therefore, the contribution of this paper is three-fold. This paper: i) presents general requirements for securing Cloud virtualization environment, ii) describes possible attacks that can be launched on different virtualization components (hypervisor, VMs, images), and iii) describes solutions and architectures to provide protection against these different attacks that lead towards a secure virtualization environment.

This paper is organized as follows: Section 2 reviews the security requirements that must be followed to secure virtualization environment. Section 3 describes the major threats and attacks scenarios related to Cloud, section 4 provides existing security solutions for virtualization. Conclusion is given in section 5.

Security Requirements of Virtualization

Different virtualization approaches can be applied to various system layers including hardware, desktop, operating system, software, memory, storage, data and network. Full virtualization is a form of hardware virtualization that involves complete abstraction of underlying hardware and provides better operational efficiency by putting more work load on each physical system [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF]. Full virtualization can be categorized into two forms: i) bare metal virtualization and ii) hosted virtualization. Bare metal approach is mostly used for server virtualization in large computing systems like Cloud computing as it provides better performance, more robustness and agility. The architecture of bare metal based virtualization generally used in Cloud is shown in Fig. 1. The unique characteristics of virtualization along with their benefits also have some drawbacks. Each component of virtualization needs to be secured from the possible threats. In general, before planning and implementing security of any system it is important to understand the security requirements of that environment. This section presents general requirements to prevent virtualization layers attacks in Cloud.

Service Provider Requirements

A report by Alert Logic [START_REF]State of cloud security report: Targeted attacks and real world hacks[END_REF] shows that 50 percent of Cloud users consider service provider security as a major threat. However, the impact of Cloud service provider on Cloud virtualization security has also not been discussed comprehensively in literature.

To secure the virtualization hardware, (Cloud) service provider must limit access of hardware resources to authorized person. Similarly, proper access control should be implemented in the management layer, so that each administrator has access only to its concerned data and software. The service provider also need to provide strong authentication mechanisms to users. Furthermore, security principles for the development of trusted computing system such as economy of mechanism, complete mediation, open design, principle of least privilege, psychological acceptability must also be followed by the service provider.

Hypervisor Requirements

Hypervisor provides the necessary resource management functions that enable sharing of hardware resources between the VMs. Hypervisor must maintain the isolation between VMs and support multiplexing of multiple VMs on single hardware platform [START_REF] Szefer | Eliminating the hypervisor attack surface for a more secure cloud[END_REF]. It must ensure that no application from any VM can directly take control of it as a host to modify the source code of hypervisor and other VMs in the network. Hypervisor should also monitor the guest OS and applications in VMs to detect any suspicious behavior [START_REF] Szefer | A case for hardware protection of guest vms from compromised hypervisors in cloud computing[END_REF].

Programs that control the hypervisor must be secured using similar practices used for security of programs running on servers. Similarly access to the hypervisor must be restricted. Other security measures to secure hypervisor include installing updates to the hypervisor, restricting administrator access to the hypervisors management interfaces and analyzing hypervisors logs to see if it is functioning properly [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF].

Virtual Machine Requirements

Limit on VM resource usage has to be assigned so that malicious VMs can be restricted from consuming extra resources of the system [4]. Moreover, isolation between virtual machines should be provided to ensure that they run independently from each other. To secure the guest OS running in virtual machines, best practices for the security of physical machines must be followed that include updating the OS regularly for patches and updates, using anti-virus software, securing internet and email and monitoring of guest OS regularly [START_REF] Brunette | Security guidance for critical areas of focus in cloud computing v2.1[END_REF].

Privileged VM (Dom0) is the first domain started by XEN hypervisor after boot. It is responsible for monitoring the communication between the remote users and guest VMs. Dom0 is also responsible for creating and destroying all guest VMs and providing device drivers to the guest VMs. Dom0 should boot the guest VMs without tampering them. The state of the VM saved as a disk file in Dom0 must remain confidential, and it must not be tampered [START_REF] Kong | Protecting the confidentiality of virtual machines against untrusted host[END_REF].

Guest Image Requirements

Hypervisors use disk images (host files used as disk drive for guest OSs) to present guest OSs with virtual hard drives. Guest OS images can be moved and distributed easily, so they must be protected from unauthorized access, tampering and storage. To securely manage the guest OS images they must be examined and updated regularly according to the requirements. Unnecessary images must not be created and if any image is useless it must be removed from system [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF]. Whenever VM is migrated from one physical machine to another, images on previous disks should be completely removed. Similarly, data on old broken disks should also be removed before they are discarded. Furthermore, backup of the virtual machines images must be maintained.

VM checkpoint is a feature that allows the users to take snapshot of VM image in the persistent storage. Snapshot records the state of the running image that contains all components of the guest OS. Snapshot is generally captured as a difference between the image and the running state. The major function of checkpoint is to restore VM to its previous state if the VM enters any undesired state. However, the snapshot access should be given to authorized users and checkpoint must be used only to return VM to a stable and non-malicious state [START_REF] Gofman | Sparc: a security and privacy aware virtual machinecheckpointing mechanism[END_REF].

Attacks on Virtualization

Each component of virtualization layer can act as an attack vector to launch multiple attacks on the system. Attacks that target different components of virtualization environment may result in security issues such as compromise of complete Cloud infrastructure, stealing of customer data and system hacking. This section discusses different attack scenarios at virtualization environment in Cloud.

Service Provider Attacks

If the attacker has physical access to the Cloud hardware, he may run malicious application or code in the system to damage the VMs by modifying their source code and changing their functionality. With the help of physical access to system, attackers can also launch cross VM side channel attacks. These attacks include CPU cache leakage to measure the load of other virtual web server on the network [START_REF] Jin | Architectural support for secure virtualization under a vulnerable hypervisor[END_REF]. Moreover, if access control is not implemented properly, different administrators such as network admin and virtualization admin might access the customer data that they are not authorized to access. These activities will result in security compromises such as loss of data confidentiality and unauthorized traffic monitoring.

Service provider has to ensure that software deployed on Cloud are built using proper coding practices. Flawed coding can result in web application attacks such as SQL Injection, Cross Site Scripting, Denial of Service and Code Execution etc. Alert Logic [START_REF]State of cloud security report: Targeted attacks and real world hacks[END_REF] report shows web application attacks to be the most common attacks on Cloud environment, impacting almost 52 percent customers.

Hypervisor Attacks

A Cloud customer can lease a guest VM to install a malicious guest OS, which attacks and compromises the hypervisor by changing its source code in order to gain access to the memory contents (data and code) of VMs present in the system [START_REF] Szefer | A case for hardware protection of guest vms from compromised hypervisors in cloud computing[END_REF]. With more features in hypervisor its increased code size has resulted in design and implementation vulnerabilities. To control the complete virtualization environment malicious hypervisors such as BLUEPILL rootkit, Vitriol and SubVir and are installed on the fly, which give attacker the host privileges to modify and control VMs [START_REF] Ibrahim | Emerging security challenges of cloud virtual infrastructure[END_REF]. This technique used by malicious software to take complete control of the underlying operating system by hiding itself from administrator and security software is called hyperjacking.

Another attack in which program running in one VM can get root access to the host machine is called VM Escape [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF]. It is done by crashing the guest OS to get out of it and running an arbitrary code on the host OS. Therefore, such malicious VMs can take complete control of the host OS. Escaping the guest OS allows the VMs to interact with the hypervisor and provides them access to other guest OS on the system as well. Fig. 2 shows that the attacker from his virtual machine (VM 2) is able to escape his VM. VM 2 is used to compromise the hypervisor which is further used to launch attacks on other VMs (VM 1) in the system.

Virtual Machines

Hypervisor

Hardware

VM 1 VM 2

Fig. 2: VM Escape attack (Source: [START_REF] Szefer | A case for hardware protection of guest vms from compromised hypervisors in cloud computing[END_REF])

Virtual Machine Attacks

Malicious programs in different virtual machines can achieve required access permissions to log keystrokes and screen updates across virtual terminals [START_REF] Reuben | A survey on virtual machine security[END_REF] that can be exploited by attackers to gain sensitive information. The privileged host virtual machine Dom0 can be compromised by attacker to either tamper boot process of guest VMs or access all guest VMs including their memory, disk space and network traffic. By controlling Dom0 attacker can create too many virtual machines to consume all resources of the system or destroy any virtual machine containing important data by launching DOS attack at Cloud. Furthermore, the saved state of guest virtual machine as a disk file appears in plaintext to Dom0. Attacker can compromise the integrity and confidentiality of the saved VM state and when restored VM may not function as desired [START_REF] Kong | Protecting the confidentiality of virtual machines against untrusted host[END_REF].

Guest Image Attacks

Unnecessary guest OS images in Cloud can result in different security issues if the security of each image is not maintained [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF]. If a malicious guest OS image is migrated to another host, it can compromise the other system as well. Furthermore, creating too many images and keeping unnecessary images can consume resources of the system which can be used as a potential attack vector by attacker to compromise the system [START_REF] Hoffman | Guide to security for full virtualization technologies[END_REF]. When VMs are moved from one physical machine to other, data of VM images might still exist on previous storage disks that attacker can access. Similarly, attackers might also recover some data from old broken disks [START_REF] Brunette | Security guidance for critical areas of focus in cloud computing v2.1[END_REF]. The security of image backup is also an issue. By gaining access to the backup images attacker can extract all information and data.

Attacker can access VM checkpoint present in the disk that contain VM physical memory contents and can expose sensitive information of VM state. A new checkpoint can be created by attacker and loaded in system to take VM to any state desired by attacker. If all the checkpoints in storage are accessed, information about previous VM states can be obtained [START_REF] Gofman | Sparc: a security and privacy aware virtual machinecheckpointing mechanism[END_REF].

Security Solutions for Virtualization

To cater the attacks on virtualization environment different security solutions have been proposed in literature. This section discusses those security solutions for each component of virtualization architecture. By implementing these security solutions the attacks discussed in section 3 can be mitigated or at least the impact of those attacks on virtualization environment can be minimized.

Service Provider Security

Unauthorized person should not have physical access to the virtualization hardware of the system. In order to protect VMs from unauthorized access by Cloud administrators, each VM can be assigned access control that can only be set through Hypervisor. The three core principles of access control namely identification, authentication and authorization will restrict admin access from unauthorized data and system components. Moreover, if any administrator is involved in security compromise, access control implemented in Cloud can help identify that person. Web application attacks can be prevented by installing an application layer firewall infront of web facing applications and by having the customer code reviewed for common vulnerabilities [4].

An online identity management community OpenID has been integrated with an open source Cloud platform OpenStack to provide identity management in Cloud [START_REF] Khan | Openid authentication as a service in openstack[END_REF]. Sandra R. et al. [START_REF] Rueda | Flexible security configuration for virtual machines[END_REF] proposed an architecture using SELinux, XEN, IPsec as tools to enforce Mandatory Access Control (MAC) policies at VM, OS and network layers. These MAC policies control the communication between VMs based on application templates that can be configured by administrators dynamically. Furthermore, the security requirements of virtualized environment differ from that of physical system, Cloud service provider must make sure that the security tools for vulnerability assessment also include the virtualization tools used [START_REF] Brunette | Security guidance for critical areas of focus in cloud computing v2.1[END_REF].

Hypervisor Security

Hypersafe is a system that maintains code integrity of the Hypervisor. It extends the hypervisor implementation and prevents its code modification by locking down the write-protected memory pages. It secures the Hypervisor against the control-flow hijacking attacks by protecting its code from unauthorized access [START_REF] Wang | Hypersafe: A lightweight approach to provide lifetime hypervisor control-flow integrity[END_REF]. VM Escape attack can only be executed through a local physical environment. Therefore, the physical Cloud environment must be prevented from insider attacks. The interaction between guest machines and host OS must also be properly configured [START_REF] Reuben | A survey on virtual machine security[END_REF].

In order to stop one VM from affecting or communicating with other VMs isolation must be properly implemented and maintained by hypervisor. Moreover, further possible attack vectors on hypervisors can be reduced by hardening the hypervisor [4]. These techniques include separating the duties of administrative functions, restricting the hypervisors administrator access to modify, create or delete hypervisor logs, and monitoring the hypervisor logs regularly.

Virtual Machine Security

Administrator must deploy a software or application that stops VMs from using extra resources unless authorized. Moreover, a light weight process must run on a virtual machine that collects logs from the VMs and monitors them in real time to fix any tampering of VMs. The guest OS and applications running on it must be hardened by using best security practices. These practices include installing security software such as anti-viruses, anti-spyware, firewall, Host Intrusion Prevention System (HIPS), web application protection, and log monitoring in guest OS [4]. Protection of VMs by different security practices is shown in Fig. 3. To identify the faults in guest OS Dan P. et al. [START_REF] Pelleg | Vigilantout-of-band detection of failures in virtual machines[END_REF] proposed a system called "Vigilant". It utilizes virtualization and machine learning methods to monitor VMs through hypervisor without putting any monitoring agent in VMs (outof-band detection). Flavio L. et al. [START_REF] Lombardi | Secure virtualization for cloud computing[END_REF] proposed Advanced Cloud Protection System (ACPS) that monitors and protects the integrity of OS in guest VMs. The periodic monitoring of executable system files is done to check the behavior of Cloud components. It uses virtual introspection techniques to deploy guest monitoring machine in system without being noticed by attacker on guest VM. Hence any suspicious activity on the guest OS can be blocked.

To protect the newly created virtual machines for users (guest VMs) from compromised privileged virtual machine Dom0, a protocol is designed by Jinzhu Kong [START_REF] Kong | Protecting the confidentiality of virtual machines against untrusted host[END_REF]. Hypervisor generates a pair of secret keys, Kernel and the initrd image are kept encrypted all the time with the secret key Kimg. First the user attests the Cloud server through Trusted Platform Module (TPM), if attestation succeeds then user sends a boot request to the Dom0 which then boots the guest domain. The guest VM executes the wrapping code and requests Hypervisor to decrypt kernel and initrd images. Hypervisor encrypts this request with its private key and asks user for key to decrypt kernel so that a VM can be created. The user sends private key Kimg encrypted under the public key of Hypervisor. Hypervisor decrypts the user message, and the private key Kimg is used to decrypt the kernel, initrd images and to launch the guest virtual machine. In this way the newly created VM is secured from compromised Dom0. The complete workflow is shown in Fig. 4. To avoid the VM storage attacks, before saving the state of the virtual machine in Dom0 its encryption can be done using AES-256, where key can be any random initialization vector. The hash of the encrypted state can be taken using MD5. When the virtual machines are to be restored, the new hash can be taken to verify the integrity of saved virtual machine. If the hash of the restored state and hash of the saved state match it means that the virtual machine state is not altered [START_REF] Kong | Protecting the confidentiality of virtual machines against untrusted host[END_REF]. Fig. 5 shows the secure storage of saved VM state.

User

Saved VM state

Store at disk Calculate Hash

Encrypt using AES 256

Fig. 5: Securing the saved VM state

Guest Image Security

Organizations using virtualization must have a policy to manage the creation, usage, storage and deletion of images. Image files must be scanned for the detecting viruses, worms, spyware and rootkits that hide themselves from security software running in guest OS. J. Wei et al. [START_REF] Wei | Managing security of virtual machine images in a cloud environment[END_REF] proposed an image management system to efficiently manage images in Cloud and detect security violations in images. It proposes the use of filters, virus scanners and rootkit detectors to provide protection against potentially compromised images. Nuwa [START_REF] Zhou | Always up-todate: scalable offline patching of vm images in a compute cloud[END_REF] is a tool designed to apply efficient patching to VM images in Cloud. By analyzing patches, Nuwa rewrites the patching scripts so that they can be applied offline. As a result, the installation scripts for online patching can be applied to images when they are offline.

When VMs are to be migrated from one physical machine to another, Cloud admin must recheck and ensure that all data is removed from previous or broken disks. To protect the backup VM images cryptographic techniques such as encryption may be employed to encrypt all backup images. If any VM is deleted then its backup must also be removed from system. Furthermore, to protect VM images from storage attacks, Cloud provider must encrypt the complete VM images when not in use [START_REF] Brunette | Security guidance for critical areas of focus in cloud computing v2.1[END_REF].

Checkpoint attacks can be prevented by encrypting the checkpoint files. Another mechanism to provide security to Checkpoints is SPARC. SPARC is a mechanism designed to deal with security and privacy issues resulting from VM checkpoint. SPARC enables users to select applications that they want to checkpoint so sensitive applications and processes cant be checkpointed. Table 1 shows the summary of different security aspects of virtualization discussed in the paper.

Conclusion

The security of cloud cannot be maintained unless its virtualization environment is secured. Although different virtualization approaches exist, bare metal virtualization approach is commonly used in large computing systems such as Cloud for server virtualization. This paper presents general architecture of bare metal virtualization and covers security aspects of its different components. Cloud virtualization environment can be compromised by different attacks at service provider, hypervisor, virtual machines, guest operating system and disk images. The attack scenarios at these components are discussed in the paper. To provide security to the virtualization environment, general requirements for virtualization security and different existing security schemes that provide security to virtualization environment have also been discussed. Therefore, the holistic picture of virtualization security in Cloud is provided through structured analysis in which security requirements, attacks and solutions correspond to each other.

Addressing these security aspects will lead towards more extensive research on secure Cloud virtualization environment. In future, an assessment criteria needs to be proposed by which we can analyze the effectiveness of security solutions of virtualization against the specific attacks.

Fig. 1 :

 1 Fig. 1: Bare metal virtualization architecture

Fig. 3 :

 3 Fig. 3: VM security by firewall, anti-virus and anti-spyware

Fig. 4 :

 4 Fig.4: Secure VM boot protocol (Source:[START_REF] Kong | Protecting the confidentiality of virtual machines against untrusted host[END_REF])

  If isolation is not properly implemented covert channels can be used for unauthorized communication with other VMs in the system. Attackers can use Trojans, malwares and botnets for traffic monitoring, stealing critical data, and tampering the functionality of guest OS. Conficker, Zeus botnet, command and control botnet communication activity are the examples of such attacks that result in data destruction, information gathering and creation of backdoors for attackers. Attacks through buggy software, viruses and worms can exploit the guest OS in VMs. Furthermore, unpatched VM operating systems can be exploited by zero day attacks.