Silvia Curteanu
email: scurtean@ch.tuiasi.ro

Florin Leon
email: florin.leon@tuiasi.ro

Andrei-Ștefan Lupu

Sabina-Adriana Floria

Doina Logofătu
email: logofatu@fb2.fra-uas.de

An Evaluation of Regression Algorithms Performance for the Chemical Process of Naphthalene Sublimation

Keywords: regression, large margin, nearest neighbor, naphthalene sublimation

Different regression algorithms are applied for predicting the sublimation rate of naphthalene in various working conditions: time, temperature, trainer rate and shape of the sample. The original Large Margin Nearest Neighbor Regression (LMNNR) algorithm is applied and its performance is compared to other well-established regression algorithms, such as support vector regression, multilayer perceptron neural networks, classical k-nearest neighbor, random forest, and others. The experimental results obtained show that the LMNNR algorithm provides better results than the other regression algorithms.

Introduction

Machine learning is a subdomain of artificial intelligence whose popularity and success are constantly growing [START_REF] Goodfellow | Deep Learning[END_REF][START_REF] Frank | Data Mining. 4th edn. Practical Machine Learning Tools and Techniques[END_REF]. Its main goal is to extract high-level patterns, i.e. knowledge, from large amounts of raw information, patterns that can provide more abstract and useful insight into the data under study. Many problems in science and social science can be expressed as classification or regression problems, where one does not know an analytical model of some underlying phenomenon, but sampled data is available through experiments or observations, and the aim is to define a predictive model based on those samples. To date, many such algorithms have been proposed, which belong to different paradigms, e.g. neural networks, nearest neighbor, decision trees, support vector machines, Bayesian approaches, etc.

Unfortunately, there is no single best algorithm that can handle the large variety of situations encountered in practice. Each method has its own advantages and disadvantages. They are mainly related to the flexibility or complexity of the models and their generalization capabilities. For a non-trivial pattern, using a very simple model may result in poor performance, whereas using an overly complex model can result in overfitting, i.e. very good results for the training set and poor results for the test set or prediction, in general. Therefore, one must make several choices when dealing with such a problem: first, to establish the most appropriate learning method and, second, to control the complexity of the model generated with that learning method by changing its specific parameters.

In the present paper, we investigate the performance of some well-established algorithms in comparison to an original regression algorithm, namely the Large Margin Nearest Neighbor Regression (LMNNR), which combines the idea of nearest neighbors with that of a large separation margin, typical of support vector machines. The sublimation of naphthalene was chosen to illustrate these methodologies based on the difficulties involved due to the toxicity of the process, in which case predictions on the model become recommended and useful.

We organize our paper as follows. Section II presents a selection of related work about regression algorithms applied for the modeling of chemical processes. Section III describes the dataset used for the experiments and Section IV presents the algorithms employed to model it. Section V describes some experimental results, while Section VI contains the conclusions of our work.

Related Work

There are many applications of artificial intelligence and soft computing methods in the domain of chemical engineering, especially for modeling and optimization. In this section, we review several applications of regression algorithms for chemical processes.

Article [START_REF] Kaneko | Adaptive soft sensor based on online support vector regression and Bayesian ensemble learning for various states in chemical plants[END_REF] proposes a combination of online support vector regression with an ensemble learning system to adapt to nonlinear and time-varying changes in process characteristics and various process states in a chemical plant. [START_REF] Ge | Probabilistic combination of local independent component regression model for multimode quality prediction in chemical processes[END_REF] uses a probabilistic combination of local independent component regression in order to assess the quality of chemical processes with multiple operation modes. [START_REF] Yuan | Locally weighted kernel principal component regression model for soft sensing of nonlinear time-variant processes[END_REF] addresses a non-linear, time-variant problem of soft sensor modeling for process quality prediction using locally weighted kernel principal component regression. [START_REF] Ghaedi | Application of least squares support vector regression and linear multiple regression for modeling removal of methyl orange onto tin oxide nanoparticles loaded on activated carbon and activated carbon prepared from Pistacia atlantica wood[END_REF] uses multiple linear regressions and least squares support vector regression to model and optimize the dependency of methyl orange removal with various adsorption influential parameters. [START_REF] Were | A comparative assessment of support vector regression, artificial neural networks, and random forests for predicting and mapping soil organic carbon stocks across an Afromontane landscape[END_REF] compares the performance of support vector regression, neural network and random forest models in predicting and mapping soil organic carbon stocks.

In [START_REF] Baughman | Neural Networks in Bioprocessing and Chemical Engineering[END_REF], the authors make a thorough presentation of neural networks used for bioprocessing and chemical engineering, with applications in process forecasting, modeling, control of time-dependent systems, and the hybridization between neural networks and expert systems.

The issue of predicting sublimation thermodynamics, such as enthalpy, entropy, and free energy of sublimation using machine learning methods was addressed in [START_REF] Mcdonagh | Are the Sublimation Thermodynamics of Organic Molecules Predictable[END_REF]. Semi-empirical models were used to model systems of solids and supercritical fluids in order to determine sublimation pressures and sublimation enthalpies, and then to model different multiphasic equilibriums [START_REF] Tabernero | On the use of semiempirical models of (solid + supercritical fluid) systems to determine solid sublimation properties[END_REF].

Some of the recent research of the authors of the present paper addressed a performance comparison of different regression methods for a polymerization process with adaptive sampling [START_REF] Leon | Performance comparison of different regression methods for a polymerization process with adaptive sampling[END_REF], a comparison between simulation and experiments for phase equilibrium and physical properties of aqueous mixtures [START_REF] Pirdashti | Phase equilibrium and physical properties of aqueous mixtures of poly (vinyl pyrrolidone) with trisodium citrate, obtained experimentally and by simulation[END_REF], an experimental analysis and mathematical prediction of cadmium removal by biosorption [START_REF] Hlihor | Experimental analysis and mathematical prediction of Cd(II) removal by biosorption using support vector machines and genetic algorithms[END_REF] and the prediction of corrosion resistance of some dental metallic materials with an original adaptive regression model based on the k-nearest-neighbor regression technique [START_REF] Chelariu | Prediction of corrosion resistance of some dental metallic materials with an adaptive regression model[END_REF].

The Naphthalene Sublimation Dataset

Our case study is naphthalene sublimationa physical process of solids that transition directly into vapors. This technique is one of the most convenient methods to study heat and mass transfer. In addition, the rate of sublimation, the amount of solid converted to vapor per time unit and solid area unit is used to study problems related to environment protection, health protection, transportation safety and security, meteorology, by determining the concentration of various substances in the environment and the dynamical properties in a wind tunnel.

In a previous approach [START_REF] Curteanu | Naphthalene sublimation. Experiment and optimisation based on a neuro-evolutionary methodology[END_REF], a series of experiments were performed to investigate the sublimation of the naphthalene samples under atmospheric pressure in air as entrainer, without recycle. Our experimental data fulfill a necessary condition for empirical modeling: a sufficient number of data was obtained which uniformly cover the investigated domain.

The sample weight was measured continuously as a function of time, at different air flow characteristics. The experimental data is then used to calculate the mass transfer rate, the degree of sublimation, the sublimation front position; the influence of air flow characteristics was also evaluated.

More details on experiments and data processing can be found in [START_REF] Curteanu | Naphthalene sublimation. Experiment and optimisation based on a neuro-evolutionary methodology[END_REF], where neural network modeling was performed. In the current work, a more efficient algorithm, LMNNR, was applied, comparatively with other algorithms: linear regression, support vector regression, neural networks, k-Nearest Neighbors, K*, and Random Forest. In addition, a large dataset was used here (1323 instances) including different shapes of the samples, while in [START_REF] Curteanu | Naphthalene sublimation. Experiment and optimisation based on a neuro-evolutionary methodology[END_REF] only spherical samples were considered (150 instances).

The data gathered from experiments contains four variables as inputs: the shape of the sample (i.e. pallets, small pills, large pills and rods), time, air speed (the trainer) and temperature, and one output: the speed of naphthalene sublimation.

Consequently, the modeling purpose was to evaluate the performance of the process, quantified by the sublimation rate depending on process time, entrainer temperature, and entrainer flow rate.

In order to apply the instance-based methods, the data is normalized between 0 and 1, independently for each numerical attribute.

Fig. 1. Statistics of the inputs and the output of the naphthalene sublimation dataset

Fig. 1 presents some statistics regarding the distribution of the data before normalization: the histogram for the first discrete input and a box plot for each numerical input, showing the minimum value, the first quartile, the median, the third quartile and the maximum value. For the output, two box plots are included, with a linear and a logarithmic scale. The output has values between 0.003 and 832.98, with the mean of 34.95 and the median of 9.24. There are a few greater values far from the median, but they are not outliers; they are important results of the process, difficult to learn, and which need to be handled accordingly by the regression models.

The goal of the paper was to find a good model for the naphthalene sublimation data. The first step was to apply classical methods, with known good performance, implemented in Weka [START_REF] Hall | The WEKA data mining software: an update[END_REF]. This was intended to constitute a basis for comparison with the original LMNNR algorithm. From the large number of algorithms in Weka, a few were selected which, in previous studies, were noticed to yield good performance for a large number of regression problems. Thus, neural networks, support vector machines, nearest neighbor, K-Star and random forest were selected. The details about their structure and operation are given below.

It must be emphasized that these techniques have very different nature and assumptions, and, by comparing the LMNNR results with the best results obtained with either of these classical algorithms, we can underline that the algorithm proposed by the authors is, in fact, a good alternative for regression.

Classical Algorithms

Neural networks in the form of multilayer perceptrons (MLP) are often used in classification and regression problems. The structure of an MLP contains an input layer, an output layer and one or more hidden layers of neurons. Each neuron sums the weighted input data of the neurons in the previous layer, to which another term (bias) is added, and the result is sent to the neurons in the next layer through a nonlinear transformation called an activation function. Each connection has an associated weight. In the training process, the weights and biases are adjusted such that the output of the network should match the desired output of the vectors from the training set. The training algorithm used most often is back-propagation [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF]. It aims to minimize the mean-squared error between the desired output and the computed one using the gradient descent method.

The Epsilon-Support Vector Regression (ε-SVR) algorithm tries to approximate the desired continuous output within a tolerating error ε while using the idea of the large margin characteristic of support vector machines [START_REF] Smola | A tutorial on support vector regression[END_REF]. When the data is not linearly separable, the ε-SVR algorithm uses kernels to transform them into a higherdimensional space. There are several types of functions that can be used as kernels, e.g. polynomial or radial basis functions (RBF). If some training instances still do not satisfy the constraints, slack variables are introduced to allow some errors (soft margin). The number of these erroneous instances can be controlled with a cost parameter C. If the value of C is decreased, a larger number of incorrectly classified training instances is allowed, which can however lead to better generalization.

The k-Nearest Neighbor (kNN) algorithm is based on the choice of k nearest neighbors using a distance function as a criterion and the output is computed by aggregating the outputs of those k training instances. As a distance function, one can use Euclidian or Manhattan distance, usually particularizations of the Minkowski distance. Choosing the value of k is important. If k is too small, then the classification can be affected by the noise in the training data, and if the value of k is too large, then distant neighbors can affect the correctness of the results. To avoid the difficulty of finding an optimum value for k, one can weight the neighbor influence. The neighbors have a greater weight as they are closer to the instance, while those farther apart have a smaller weight.

The K-Star algorithm [START_REF] Cleary | An instance-based learner using an entropic distance measure[END_REF] is an instance-based classifier that very much resembles the k-Nearest Neighbor algorithm presented before. Its novelty comes from the usage of an entropy metric in its similarity function, rather than the usual distance metric. It has been shown in the literature that such an approach has beneficial outcomes for certain industry-related problems [START_REF] Painuli | Tool condition monitoring using K-star algorithm[END_REF]. The K-Star algorithm can also be used for regression purposes, similarly to how k-Nearest Neighbor is used.

A random forest [START_REF] Breiman | Random Forests[END_REF] is composed of a collection of classification or regression trees. Each tree is generated using random split tests on slightly different training set generated using bagging. The output of a new instance is computed by aggregating the outputs of the individual trees.

The Large Margin Nearest Neighbor Regression Algorithm

The performance of the above algorithms was compared to that of an original algorithm, Large Margin Nearest Neighbor Regression (LMNNR) [START_REF] Leon | Evolutionary algorithm for large margin nearest neighbour regression[END_REF][START_REF] Leon | Large margin nearest neighbour regression using different optimization techniques[END_REF].

The support vector machines, in a classification context, rely on the idea of finding a large margin between classes by solving an optimization problem. This idea was used in conjunction with the k-Nearest Neighbor method, also for classification [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]. Its main assumption is to change the distance metric of the kNN space by using a matrix:

   .
) , (

j i T j i j i M d x x M x x x x    (1)
If M is a diagonal matrix, the weights of the neighbors are:

  . ' 1 ) ' , ( 1 ) ' , ( 1 2 
     n i i i ii M d x x m d w M x x x x (2)
Equation ( 2) involves a single, global matrix M for all the instances. However, it is possible to have different distance metrics for the different instances or groups of instances. Thus, prototypes can be used which are defined as special locations in the input space of the problem, and each prototype P has its own matrix P M . When computing the distance weight to a new point, an instance uses the weights of its nearest prototype, i.e. P ii m instead of m ii in equation ( 2). Finding the appropriate matrices is achieved by solving an optimization problem. In a simplified formulation, the objective function F, which is to be minimized, takes into account two criteria with equal weights, F 1 and F 2 , described below. In order to briefly explain the expressions of these functions, the following notations were made, where d M means the weighted square distance function using the weights we search for:

d ij = d M (x i , x j ), d ik = d M (x i , x k ), g ij = |f(x i ) -f(x j )|, g ik = |f(x i ) -f(x k )|.
The first criterion is:

 , 1 1 ) ( 1 ij n i i N j ij g d F        (3)
where N(i) is the set of the nearest k neighbors of instance i, e.g. k = 3. Basically, this criterion says that the nearest neighbors of i should have similar values to the one of i, and more distant ones should have different values.

The second criterion is expressed as follows:

     . 0 , 1 1 1 max 1 ) ( ) ( 2              n i i N j i N l il ik ij ij g d g d F (4)
Here, the distance to the neighbors with close values (the positive term) is minimized, while simultaneously trying to maximize the distance to the neighbors with distant values (the negative term). An arbitrary margin of at least 1 should be present between an instance with a close value and another with a distant value.

For optimization, both an evolutionary algorithm and an approximate differential method following the central difference definition of the derivative can be used. The estimated output of a new query instance x q is computed as follows. Its k nearest neighbors are identified using the distance metric from equation [START_REF] Goodfellow | Deep Learning[END_REF]. The weights of these neighbors are computed with equation ( 2) and then normalized: . ) , (

) , ( ) , ( 1    k j q j d q i d q i n d M M M w w w x x x x x x (5)
Finally, the output is computed as a weighted average of the neighbor outputs:

   . ) , ( ~1 i k i q i n d q f w f M x x x x     (6)

Results and Discussion

In this section, the choice of parameters for different regression methods is explained.

For each algorithm, multiple experiments with different parameter values were performed. The tables containing the results only display those with the best performance in terms of correlation coefficient (r) and root mean square error (RMSE).

In order to compare the performance of the various algorithms, the crossvalidation method with 10 folds was used. Also, since an objective comparison was intended, the data set was randomly divided into 10 groups (iteratively one for test and the rest for training) and the same groups were used by all the algorithms. It was considered that this methodology is particularly important to compare the algorithms implemented in Weka with the original implementation of the LMNNR algorithm.

The results obtained for individual test groups, although interesting, were omitted in the results section, and only the aggregated results are displayed in the following tables.

Parameters of Regression Methods

Multilayer Perceptron Neural Network (MLP).

For the problem at hand, repeated experiments showed that a neural network produces best results when given a low learning rate. The momentum parameter also has a great impact on learning. Its optimal value tends to be around 0.4 or 0.5. The number of hidden layers was automatically chosen by Weka. This option yielded the best outcomes because the optimal number of hidden layers tends to vary between cross-validation sets, making it hard to achieve similar performance with manually chosen values. The encoding for the discrete input is "one-hot", leading to 7 inputs and 1 output. The best network architecture was the one with one hidden layer containing 4 neurons with sigmoid activation functions, and with the output neuron with a linear activation function. 1000 epochs for training were found to be an acceptable compromise between the quality of the resulting model and the overall training time.

Support Vector Regression (SVR). The Epsilon-SVR algorithm achieved a very good overall fit if the kernel used was based on radial basis functions. The kernel type choice was vastly influential on the outcome. RBF, therefore, yielded a correlation that was at least 20% better than all of the other options (linear, polynomial and sigmoid). The best results were obtained with relatively large values of the parameters: γ = 14, C = 10, whereas ε was best kept at a low value, i.e. ε = 0.001. Fine-tuning these parameters helped improve the algorithm performance significantly, such that the final correlation was the best out of all the algorithms tested with Weka.

k-Nearest Neighbor (k-NN). The optimal number of neighbors used in this algorithm is in this case 2. The correlation dropped significantly if the number of neighbors was increased above this value. The search method used was the linear nearest neighbor search. A slight improvement was achieved by using the Manhattan distance as metric, instead of the Euclidean distance.

K-Star (K * ). The only numeric parameter that this algorithm takes, the global blending index, was optimal at low values. In the experiments, the value 3 was used. The parameter, however, influenced the outcome in a slight manner (~5% correlation improvement). The entropic auto blend functionality provided by Weka was turned off for these experiments.

Random Forest (RF). In the case of this algorithm, the number of trees parameter plays an important role in the overall performance. Several tests were conducted to determine the optimal value of this parameter and the best outcome was recorded with a value of approximately 200 trees. Although the difference in performance obtained by optimizing this parameter was only around 3%, it allowed Random Forest algorithm to yield one of the best correlations for the data.

Large Margin Nearest Neighbor Regression (LMNNR). For this algorithm, the parameters are the number of prototypes, the number of optimization neighbors and the number of regression neighbors. Different combinations of values for these parameters were attempted. Since the LMNNR results are not deterministic, because the initialization of the matrices is random and then optimized, the best results were included out of 100 algorithm runs for each configuration.

A Comparison Between Algorithm Performance

In Tables 1 and2, one can see the best results achieved with the use of the regression algorithms presented in the previous section. Five out of the six algorithms tested show a very good correlation of the data (~0.9) and come in a very short range from one another. Linear regression, which is included only for comparative reasons, achieves a low total correlation. This emphasizes the nonlinearity of the problem at hand. ɛ-SVR and Random Forest yield the best, almost identical, predictions. kNN and K-star present similar results, despite the different metrics they use in their similarity functions.

From Table 2, it can be seen that the LMNNR results are clearly better than the results obtained by other well-established regression algorithms.

Unlike the problems studied in previous works [START_REF] Leon | Evolutionary algorithm for large margin nearest neighbour regression[END_REF][START_REF] Leon | Large margin nearest neighbour regression using different optimization techniques[END_REF], it can be seen that more prototypes are needed for this particular problem. 5 prototypes provide the best results in terms of correlation coefficient. This shows that this dataset is more difficult to learn using a unique distance metric and that different regions of its input space have different characteristics with can be properly addressed with the use of prototypes.

Fig. 2 shows a comparison between the predictions of the model and the desired data, for the case with 5 prototypes, 5 regression neighbors and 5 optimization neighbors from Table 2, which yields the highest correlation coefficient r. One can see that the two datasets are quite close. An exception is e.g. the data point with the value of 1. Since Fig. 2 presents the results for the 10 testing sets of the crossvalidation process put together, the data point with a maximum value in the test set cannot be correctly approximated by the model relying on the rest of the data in the training set. The LMNNR algorithm is based on the nearest neighbor paradigm, and therefore it cannot extrapolate to a value that is larger than any value in the training set. Furthermore, one can see that most of the data has small output values, and only 0.8% of the normalized data has output values above 0.5. This contributes to the difficulty of the model to approximate higher output values.

Conclusions

The results obtained by the LMNNR algorithm proposed by the authors are better than those provided by other classical regression algorithms. These predictions are important for the chosen process, avoiding or, at least, minimizing the number of experiments made in toxicity conditions, and saving materials and energy. In addition, the developed modeling methodologies can be easily adapted and applied to other chemical engineering processes.

The promising results of LMNNR determine the planning of other applications and methodologies that include this algorithm. As a future direction of investigation, one can consider its further refinement in order to automatically detect the optimal values of its parameters, namely the number of prototypes, the number of regression neighbors and the number of optimization neighbors.

Fig. 2 .

 2 Fig. 2. Comparison between the predictions of the model and the desired data

Table 1 .

 1 The best results obtained for optimized configurations by algorithms in Weka

	Algorithm	Parameters	r	RMSE
	ɛ-SVR	C: 10; ε: 0.001; γ: 14; kernel: RBF	0.91514	0.04022
	Random Forest	number of features: 1; number of trees: 200	0.91332	0.03965
	k-NN	k: 2; Manhattan distance	0.90639	0.04022
	K *	global blend: 3	0.89025	0.04450
	MLP	learning rate: 0.1; momentum: 0.4; number of training epochs: 1000	0.88344	0.04615
	Linear Regression		0.64395	0.07277

Table 2 .

 2 The best results obtained with the original LMNNR algorithm

	Number of prototypes	Number of neighbors regression	Number of neighbors optimization	r	RMSE
	1	3	3	0.93151	0.036118
	1	5	5	0.93052	0.036276
	1	10	10	0.92426	0.03825
	2	3	3	0.94097	0.033554
	2	5	5	0.9365	0.035707
	2	10	10	0.93416	0.037173
	3	3	3	0.94067	0.033251
	3	5	5	0.93698	0.036821
	3	10	10	0.93428	0.036797
	5	3	3	0.94185	0.033915
	5	5	5	0.94425	0.034913
	5	10	10	0.93614	0.036856

Acknowledgments

This work was supported by the "Program 4, Fundamental and Border Research, Exploratory Research Projects" financed by UEFISCDI, project no. 51/2017.


Anitta Thomas
email: thomaa@unisa.ac.za

Aurona J Gerber

Alta Van Der Merwe
email: alta.vdm@up.ac.za

Ontology-Based Spatial Pattern Recognition in Diagrams

Keywords: Spatial Patterns, Diagrams, Ontology, Ontology Reasoner, OWL, UML Class Diagrams, SVG

Diagrams are widely used in our day to day communication. A knowledge of the spatial patterns used in diagrams is essential to read and understand them. In the context of diagrams, spatial patterns mean accepted spatial arrangements of graphical and textual elements used to represent diagram-specific concepts. In order to assist with the automated understanding of diagrams by computer applications, this paper presents an ontology-based approach to recognise diagram-specific concepts from the spatial patterns in diagrams. Specifically, relevant spatial patterns of diagrams are encoded in an ontology, and the automated instance classification feature of the ontology reasoners is utilised to map spatial patterns to diagram-specific concepts depicted in a diagram. A prototype of this approach to support automated recognition of UML and domain concepts from class diagrams and its performance are also discussed in this paper. This paper concludes with a reflection of the strengths and limitations of the proposed approach.

Introduction

Diagrams are widely used in our day to day communication, and different types of diagrams are used for various purposes in different domains. Prominent diagrams used in Computing include flow charts, state chart diagrams and Unified Modelling Language (UML) diagrams. A noticeable aspect of these diagrams is that they have generally accepted visual syntax, which are spatial patterns consisting of graphical and textual elements [START_REF] Marriott | Visual Language Theory, chap. A Survey of Visual Language Specification and Recognition[END_REF][START_REF] Minas | Syntax Definition with Graphs[END_REF] to indicate diagram-specific concepts in the diagrams. This study only considers diagrams that have established visual syntax irrespective of whether it is formally or informally specified. The knowledge of these visual patterns is essential to read and understand diagrams.

Numerous approaches have been used to generate declarative specifications of various aspects of diagrams including their spatial patterns, and these specifications have been used to implement applications to either recognise or generate diagrams. The majority of these approaches are grammar-based approaches, and the prominence of these approaches stems from their success in natural language specifications [START_REF] Marriott | Visual Language Theory, chap. A Survey of Visual Language Specification and Recognition[END_REF]. However, the number of diagram specification techniques that have sufficient supporting literature, freely-available tools and literature that indicates their current use remains small.

Ontologies is a prominent knowledge representation technique, which has been successfully used to realise knowledge-based applications. An ontology, in general, is a model of domain knowledge designed for a specific purpose. Ontologies are used, in general, for two main purposes; as a formal vocabulary of concepts in a domain or as a knowledge source from which additional knowledge can be derived. Logic-based ontologies have the benefit of being able to use the automated reasoning capabilities of existing ontology reasoners to verify and infer additional information from them [START_REF] Halland | Investigations into the use of SNOMED CT to enhance an OpenMRS health information system[END_REF]. The Web Ontology Language (OWL), a logic-based ontology language, has a rich set of current literature, proven value in numerous application domains and freely-available tools [START_REF] Hitzler | Foundations of Semantic Web[END_REF][START_REF] Kashyap | The Semantic Web: Semantics for Data and Services on the Web[END_REF].

In this paper, we present the results of a study that developed and evaluated an ontology-based approach to recognise spatial patterns in diagrams. In this approach, relevant spatial patterns of diagrams are encoded in an OWL ontology, and the automated instance classification feature of the ontology reasoners is utilised to map spatial patterns to diagram-specific concepts depicted in a diagram. The proposed approach is then instantiated in a prototype to recognise concepts from Scalable Vector Graphics (SVG) files of UML class diagrams using an ontology of relevant spatial patterns. Furthermore, the performance of the prototype in terms of its time usage and correctness is tested with a sample set of class diagrams. Automated recognition of concepts from diagrams can be a useful building block to generate automated summaries of diagrams, which can, for example, be useful for visually impaired users in reading the information depicted in diagrams.

The novel contributions of this study are three-fold; firstly a generic ontologybased approach to recognise diagram-specific concepts from diagrams is presented. Secondly an implementation, albeit a prototype, demonstrates the feasibility of the proposed approach, and thirdly, automated semantic interpretation of limited scope of class diagrams in SVG format using an ontology of spatial patterns is demonstrated.

This paper is structured into seven sections. In section 2, the proposed ontology-based approach and a generic application design that uses this approach are presented. A prototype that follows this ontology-based approach to recognise UML and domain concepts in class diagrams of SVG format is presented in section 3. Section 4 presents a discussion on the performance of the prototype. In Section 5, a discussion of the pros and cons of the proposed ontology-based approach is included. Section 6 includes a brief summary of related work and a conclusion is provided in section 7.

Ontology-based Spatial Pattern Recognition

Diagrams with established visual syntax consist of well-defined spatial patterns for diagram-specific concepts. For example, Figure 1 depicts (a) a decision (b) a state (c) a class used in flow charts, state diagrams and UML class diagrams respectively. In this example, decision, state and class are domain-specific concepts, which are represented using established spatial patterns, which consist of spatial configurations of graphical and textual elements. For example, a state in state diagrams can be represented using a circle and a text, where the text is contained in the circle. Additionally the text in the circle is generally considered as the description of the state, so in this case the string A will be read as state A. In our proposed approach, recognising domain-concepts in diagrams is achieved using an ontology of visual patterns. The first step in this approach is to create a ontology of visual patterns of diagrams. The model of visual patterns in the ontology should be aligned with the goals of the applications in which it will be used. An application for diagram interpretation that uses this ontology can then be realised using the generic design depicted in Figure 2. In the generic design, the component Diagram processor will process the diagram to extract graphical and textual primitives as well as the spatial relationships between these primitives, which is then amended to the ontology of visual patterns. The ontology reasoner can then process, using instance classification, this amended ontology to indicate the diagram-specific concepts depicted in the diagram. In Section 3, the generic design given in Figure 2 is modified to implement a prototype that extracts UML and domain concepts from SVG files of class diagrams.

Prototype: Automated Extraction of UML concepts from class diagrams in SVG format

The aim of the prototype is to realise automated interpretation of a limited form of class diagrams using a relevant spatial patterns ontology. The file format of A class diagram, in general, is a UML model that models a system or some aspect within some domain. The metamodel of class diagrams is defined in UML [START_REF]Object Management Group: Object Management Group Unified Modeling Language (OMG UML) Version 2[END_REF]. In the developed prototype, the concepts extracted automatically from class diagrams include elements from both the domain model and UML metamodel. For example, referring to Figure 1(C), the notation can be seen as the UML concept (metaclass) Class, and the string A, representing the class name, can be seen as a concept from the domain model. The proposed approach of automated extraction of concepts is relevant when class diagrams do not contain explicit representations of models, for example, in the XML metadata interchange format XMI [START_REF]About the XML Metadata Interchange Specification Version 2[END_REF]. Any non-UML complaint tool, for example a general-purpose free sketching application, can generate class diagrams without explicit model information. One can find numerous class diagrams on web pages that are only available as images without explicit model information.

An Ontology of Spatial Patterns for Class Diagrams

The central component of the prototype is a dedicated ontology of spatial patterns to support recognition of concepts from class diagrams. In order to develop the ontology, decisions had to be made about how to model the spatial patterns, how to indicate which spatial patterns correspond to which UML concepts and which relevant spatial patterns need to be encoded in the ontology.

UML class diagrams are specified in the Classes package of the UML 2.4.1 specification [START_REF]Object Management Group: Information technology -Object Management Group Unified Modeling Language (OMG UML)[END_REF]. This package includes fifty six concepts that can be used to represent an object oriented model in class, package and object diagrams. Moreover, a concept can have more than one spatial pattern. In other words, a concept can be illustrated in different ways. As the developed ontology is to be tested with a prototype, a finite set of UML concepts and spatial patterns was selected to be included in the ontology. This selection was based on which concepts and notations are typically used in class diagrams and also discussed in UML 2.4.1 specification [START_REF]Object Management Group: Information technology -Object Management Group Unified Modeling Language (OMG UML)[END_REF].

The spatial patterns were modelled as spatial configurations of primitive elements and spatial relationships between these elements. This modelling approach was used because it aligns with the OWL constructs, classes and properties [START_REF] Horrocks | OWL 2 Web Ontology Language: Direct Semantics (Second Edition)[END_REF], where an OWL class represents a set of objects and a property describes a possible relationship between objects [START_REF] Horridge | A Practical Guide to Building OWL Ontologies using Protégé 4 and CO-ODE Tools[END_REF]. The developed ontology consists of numerous OWL classes and they are used to represent either a primitive element or a UML concept. For example, the graphical object rectangle is a graphical primitive used in class diagrams, so an OWL class named Rectangle is added in the ontology to represent all instances of rectangles in class diagrams. A set of spatial relationships were also selected, which were then added as properties in the developed ontology. The spatial pattern for a UML concept was then modelled as the class definition of the corresponding OWL class. If the selected UML concept had more than one spatial pattern, the OWL class corresponding to the concept encoded multiple spatial patterns. The OWL class (corresponding to UML concepts) definitions encoded spatial patterns in terms of existing OWL classes (corresponding to UML concepts and primitive elements) and properties (corresponding to spatial relationships).

Due to space limitations, the entire ontology cannot be included in this paper. Interested readers may refer to [START_REF] Thomas | Visual Syntax of UML Class and Package Diagram Constructs as an Ontology[END_REF][START_REF] Thomas | An Investigation into OWL for Concrete Syntax Specification Using UML Notations[END_REF] for details about the ontology. For illustrative purposes, consider the UML concept class, which has numerous spatial patterns -Figure 3 and (hasTangentialProperPartOf some Line))

In the OWL code above, Rectangle, Line and String are the OWL classes in the ontology to represent graphical primitives rectangle and line, and textual primitive (one line of text) respectively. hasNonTangentialProperPartOf and hasTangentialProperPartOf are properties (corresponding to spatial relationships) encoded in the ontology, and they correspond to the spatial relationships N T P P -1 and T P P -1 of RCC-8 [START_REF] Cohn | Qualitative Spatial Representation and Reasoning with the Region Connection Calculus[END_REF] respectively. The spatial pattern encoded in the ontology for the concept class takes into account its different spatial patterns, especially those depicted in Figure 3.

Prototype Design and Implementation

The prototype achieves automated interpretation of class diagrams in several steps. The first step involves extracting primitives and spatial relationships be-tween the primitives from an input diagram, which is used to generate OWL code specific for the input diagram. In the second step, the generated OWL code is added to the ontology described in Section 3.1. In the third step, the ontology reasoner performs instance classification on the updated ontology. In the fourth step, the results of the instance classification and the reasoner justifications for the results of instance classification are processed to extract the desired interpretation for the given diagram.

The prototype has a design with three main components namely SVG processor, OWL code generator and writer and Interpretation processor to realise automated interpretation of class diagrams. The inputs to the prototype are class diagrams in SVG format and the ontology described in Section 3.1, and the final output is the interpretation, which in this case is a list of nodes and links in the diagram. The overall design of the prototype is given in Figure 4. The functionality of each component is described below.

SVG processor:

The aim of this component is to extract relevant graphical and textual primitives, and the spatial relationships between these primitives in the input class diagram. Relevant primitives are graphical and textual elements visible to the user and also specified in the ontology. When extracting relevant graphical and textual primitives, their relevant geometric features are also extracted in order to calculate relevant spatial relationships specified in the ontology.

Different SVG files can generate visibly same image, which is attributed to different ways to encode graphics in SVG. Due to differences in SVG modelling, the models of SVG were restricted for this prototype. However, the chosen models require processing, both XML and geometrical, of SVG elements to determine visible graphical primitives and the spatial relationships between the primitives.

OWL code generator and writer:

The OWL code generator and writer component consists of two sub-components; one to generate OWL code relating to the input diagram and the second one to write this generated OWL code to the ontology described in Section 3.1. The output from SVG processor is used to create the OWL code, which includes unique names, types of all the primitives and spatial relationships between them. The generated OWL code is then written to a copy of the .owl file containing the visual patterns ontology, which means each input diagram has a unique ontology file.

Interpretation processor: Interpretation processor invokes the ontology reasoner with the visual patterns ontology output of OWL code generator and writer to produce the interpretation. There are two steps taken by Interpretation processor to obtain the desired interpretation.

Fig. 5. A simple class diagram

The first step is to use the instance classification feature of the reasoner to obtain the instances of OWL classes that represent relevant UML concepts in the ontology. Specifically, lists of all primitives encoded in the ontology that are classified as instances of OWL classes of interest are obtained. For example, Interpretation processor obtains the list of all rectangles that are classified as instances of the OWL class UMLClass meaning that these rectangles form part of spatial patterns that represent the UML concept class.

In the second step, Interpretation processor processes the justifications of the results of instance classification from the first step to obtain relevant node pairs that satisfy relevant links. In particular, justifications of the results of instance classification of OWL classes that correspond to only UML concepts that represent links are selected for further processing. This selection is because UML concepts that represent links are modelled in terms of nodes in the class diagrams. For example, the spatial pattern encoded for the UML concept inheritance consists of graphical primitives, triangle and line(s), as well as node(s) (examples of nodes include classes and interfaces). If the reasoner inferred that an instance of OWL class triangle is an instance of the OWL class inheritance, the justifications for this instance classification would contain the information about the node(s) that led to this inference. Thus by processing these justifications one can extract the node pairs that satisfy relationship links.

Input and output:

The inputs to the prototype are class diagrams in SVG format, and the spatial patterns ontology for class diagrams. An intermediate output of the prototype is a modified spatial patterns ontology that contains input diagram-specific information in addition to the spatial patterns. The final output is a textual summary of the interpretation, i.e. lists of all relevant nodes and links in the input diagram.

To illustrate the output produced by the prototype, consider the simple class diagram depicted in Figure 5.

The textual interpretation produced for this diagram is Class[A, B, C, D], Inheritance[(A, B)], Association[(B, C)] and Dependency[(D, B)].

Note that the textual interpretation contains a summary of the domain model in terms of UML concepts; A, B, C and D refer to domain concepts and Class, Inheritance, Association and Dependency refer to UML concepts.

Implementation: SVG processor and OWL code generator and writer are written in C++ without the use of any external libraries. Interpretation processor is written in Java because the OWL API is a Java API [START_REF] Hitzler | Foundations of Semantic Web[END_REF], and it makes use of the OWL API version 3.5.0 and the OWL reasoner HermiT [6]. Additionally, Interpretation processor makes use of the clarkparsia library to obtain justifications from the OWL reasoner.

Prototype Performance

An initial evaluation of the prototype was conducted using fifteen class diagrams. The SVG file sizes of the class diagrams varied from 2 kB to 59 kB. As expected the larger files have larger number of SVG elements and graphical representations in the diagrams than smaller files. The number of XML elements varied from 15 to 640 in the sample SVG files and the number of actual graphical and textual primitives visible in the diagrams varied from 2 to 205.

For the initial evaluation, precision, recall and processing times of the prototype for the sample class diagrams were noted. The average precision and recall of the final interpretation results were 0.95 and 0.98 respectively. However, the lowest precision of 0.78 and recall of 0.76 were recorded for certain class diagrams. The main cause for mistakes in diagram interpretation was incorrect modelling of spatial patterns for certain UML concepts, which led to certain UML concepts identified incorrectly as well as certain UML concepts not identified in the diagrams.

The average time used by the prototype was under a minute for the sample class diagrams. However, the longest time taken was approximately 7 minutes for the sample set. Based on the times recorded for each process in the prototype, it was noted that accessing justifications from the reasoner using the clarkparsia library was the most time-intensive process, taking up to an average of 97% of the total time used by the prototype.

The prototype demonstrates high precision and recall, which is highly desirable even though the sample set was relatively small. However, the time taken for accessing justifications of reasoner seems unreasonably high in comparison to the times taken by other processes in the prototype. Overall, the performance of the prototype is deemed satisfactory and it encourages further evaluation with larger number of diagrams, and improvements to the prototype. Improvements to the prototype will include modifications to the spatial patterns ontology to improve precision and recall, as well as the use of other available libraries to obtain justifications from the ontology reasoner to improve its time usage.

Discussion

The ontology-based approach presented in this paper can be applied to any type of diagrams with well-established spatial patterns, and thus the design in Figure 2 can be reused in other diagram interpretation applications. This paper also showed an example of how the general design in Figure 2 was adapted and instantiated in an interpretation application for class diagrams with promising results.

It should be noted that the scope of interpretation of diagrams using this approach is dependant on how the spatial patterns are modelled in the ontology. Similarly, the content of the spatial patterns ontology influences all the processes in the design in Figure 2. For example, which primitives should be extracted in Diagram processor is directed by the model encoded in the ontology. This tight coupling between the spatial patterns ontology and all the components in the general design may limit the reusability of program codes from one diagram interpretation application to another.

Diagram processor tries to extract graphical and textual primitives from the input diagram, which is indeed a form of mapping from raster or scalar data to semantic concepts of graphical shapes and text. Thus it may be possible to use a different type of ontology to support the functionality of Diagram processor.

Use of justifications from the ontology reasoner seems to be a feasible way to obtain necessary information for the diagram interpretation scope of the developed prototype. However, it is possible that using justifications may not work for other diagram interpretation scopes. Although processing justifications was a bottle neck in the prototype, there are other ways to access justifications from the reasoners. One possibility is to use the Protégé [START_REF][END_REF] API instead of clarkparsia library to access the justifications.

Currently the prototype provides a textual summary of the class diagram. However, it is possible to format the summary in XMI since it is the recommended format for model exchange among UML tools [START_REF]Object Management Group: Object Management Group Unified Modeling Language (OMG UML) Version 2[END_REF].

Related Work

In [START_REF] Kirasić | Ontology-Based Design Pattern Recognition[END_REF], an ontology-based approach to recognise design patterns in program codes is proposed, where the ontology consists of models of design patterns and the reasoner is used to identify design patterns from an input program. The approaches in [START_REF] Kirasić | Ontology-Based Design Pattern Recognition[END_REF] and in this paper are similar but the difference is that the former is applied to the analysis of program codes in text and the latter is applied to the analysis of diagrams.

In [START_REF] Salameh | SVG-to-RDF Image Semantization[END_REF], a framework to realise domain-based Resource Description Framework (RDF) annotation of SVG images is presented. In this framework, the SVG image is initially processed to extract relevant graphical features, which is used to create a layer of RDF data. In order to provide semantic annotation, the application uses a RDF database relevant for the domain in order to compute similarities between the given image and the semantic concepts in the database. The semantic annotation generated by the application is also checked by a domain expert, which is fed back into the RDF domain database. Comparing the prototype discussed in this paper and the annotation framework presented in [START_REF] Salameh | SVG-to-RDF Image Semantization[END_REF], it is evident that both approaches use declarative domain knowledge to assist with the interpretation of SVG images. However, the approach in this work is focussed on spatial patterns in diagrams, and how an ontology of such patterns can be used for diagram interpretation.

Ontology-based approaches have been successfully used in the field of image analysis -see examples of such studies in [START_REF] Fiorini | Semantic image interpretation of gamma ray profiles in petroleum exploration[END_REF][START_REF] Hudelot | Towards a Cognitive Platform for Semantic Image Interpretation[END_REF][START_REF] Maillot | Towards ontology-based cognitive vision[END_REF]. In the field of image analysis, single to multiple ontologies are used in an application, and what is modelled in the ontology differs from domain knowledge to generic knowledge relevant for describing images in general. The ontology-based approaches used in image analysis may be adapted for semantic interpretation of diagrams, or generic ontologies used in image processing may be applied in Diagram processor or SVG processor in Figures 2 and4 respectively. The primary focus of ontologies in the current work is to model spatial patterns in diagrams, and to reuse the automated reasoning features of ontology reasoners for diagram interpretation.

There are numerous works that combine UML and OWL, which can be roughly classified into two categories. The first category deals with model translations from UML to OWL or RDF (examples of such studies include [START_REF] Gasević | Converting UML to OWL Ontologies[END_REF][START_REF] Tong | Construction of RDF(S) from UML Class Diagrams[END_REF][START_REF] Zedlitz | From UML to OWL 2[END_REF]) and the second category focuses on reasoning about the models represented in UML diagrams (examples of such studies include [START_REF] Berardi | Reasoning on UML Class Diagrams[END_REF][START_REF] Khan | Consistency of UML Class, Object and Statechart Diagrams using Ontology Reasoners[END_REF]). These two categories of works assume that the models represented in diagrams are easily accessible, so that they can focus on the translation of UML models into OWL. However, the prototype presented in this work is useful when the models have to be read from the class diagrams. In other words, the developed prototype reads the models in the class diagrams using a visual syntax ontology. Thus an OWL ontology is used to infer the model specified in the class diagram. Once the models in the class diagrams have been read, then the approaches specified in [START_REF] Berardi | Reasoning on UML Class Diagrams[END_REF][START_REF] Gasević | Converting UML to OWL Ontologies[END_REF][START_REF] Khan | Consistency of UML Class, Object and Statechart Diagrams using Ontology Reasoners[END_REF][START_REF] Tong | Construction of RDF(S) from UML Class Diagrams[END_REF][START_REF] Zedlitz | From UML to OWL 2[END_REF] can be used to translate these models into OWL, and to reason about class diagrams, if required.

Conclusion

This paper presented an approach to represent spatial patterns of diagrams in an ontology, which is then used for diagram interpretation using instance classification feature of ontology reasoners. This ontology-based approach was used to realise a prototype to interpret UML class diagrams in SVG format. The performance of the prototype was evaluated with a small set of sample class diagrams, which showed promising results that support the need for further improvements to and evaluations of the prototype.

Fig. 1 .

 1 Fig. 1. Notations of (a) a decision (b) a state (c) a class used in flow charts, state diagrams and UML class diagrams respectively

Fig. 2 .

 2 Fig. 2. The components of a generic diagram interpretation application that uses the spatial patterns ontology

  depicts a few of them. In the developed ontology an OWL class, named UMLClass is created with its class definition encoding the spatial patterns of the UML concept class. The OWL class definition of UMLClass that contains the spatial pattern is listed below: Class: UMLClass EquivalentTo: (Rectangle and (hasNonTangentialProperPartOf some String)) or (Rectangle and (hasNonTangentialProperPartOf some String)

Fig. 3 .

 3 Fig. 3. Different depictions of the UML concept class

Fig. 4 .

 4 Fig. 4. Prototype design


A Kallipolitis

I Maglogiannis

Content Based Image Retrieval in Digital Pathology Using Speeded up Robust Features

Keywords: Digital Pathology, Laboratory Information System, Content Based Image Retrieval (CBIR), Speeded Up Robust Features (SURF), Whole Slide Imaging (WSI)

The recent expand in the utilization of Whole Slide scanners in Digital Pathology gave birth to a production of massive amount of data and the need of integration of Digital Pathology Systems (DPS's) into modern Laboratory Information Systems (LIS's). In this context, the problem of automatically retrieving a particular image from a large set of digital images that contains similar medical visual content has gained fruitful ground. This work investigates the fast and consistent properties of the Speeded-Up Robust Features (SURF) algorithm in order to search in the content of a digital pathology image, detect and find similarities for content-based image retrieval. An important aspect of this work is the diversity of Whole Slide Scanners. The proposed methodology that involves the process of the comparison of digital pathology images, mostly WSI, with the use of the SURF algorithm was proved robust to various condition changes.

Introduction

Digital Pathology was meant to solve many problems that physicians in this domain had faced in the earlier years, mainly associated with the management and preservation of tissue samples, the inability of conducting tele medical consultations and the lack of advanced computer based systems for diagnosis, analysis and education. Nevertheless, the transition to a new digital era of pathology brought up many new challenges. A vast amount of data is created every second as the digital image produced by a glass slide has a typical size of 3GB along with its metadata. Analyzing such images in order to recognize patterns and similarities against images found in medical books and atlases have been proven tedious and time-consuming tasks for pathologists. There is an immense need for automated and fast book, database and storage systems screening. Furthermore, the variety of whole slide scanners vendors led to the building of a new "Babel" tower, where each DPS speaks a different language as far as hardware, operating systems, formats of digital images and communicating protocols are concerned [START_REF] Goode | Openslide: A vendorneutral software foundation for digital pathology[END_REF]. To address these two challenges, the paper describes a system that, at first stage, is able to translate the different formats of WSI and, at second, detects similarities in pathology images. The system can also import medical books in pdf format and extract the images found in them for storage and analysis along with whole slide images. A general overview of the system is shown in figure 1.Inputs to content based image retrieval system can be whole slides images, images extracted from digital pathology books (literature) and local storage or digital pathology databases. One of these images represents the query image and the others the test images. These inputs, digital images to their whole, are imported in the system, processed and the output of the process is the set of images that bear the greatest resemblance to the query image.

Fig. 1 General view of image retrieval system

The remainder of this paper is structured in 5 sections, as follows: Section 2 presents the related work, while Section 3 describes the proposed methodology for image retrieval. Section 4 describes the system in practice and Section 5 reports the experiments conducted and the corresponding results. Finally, Section 6 concludes the paper.

Related Work

The discipline of pathology has well accepted its "digital" character, since several years of evolution transforming the conventional LISs (Laboratory Information Systems) to their modern digital pathology version. This new version embodies several technologies such as Relational Database Management Systems (RDBMSs), Structured Query Language (SQL), eXtensible Markup Language (XML) and, most significantly, WSI (Whole Slide Imaging) [START_REF] Park | Anatomic Pathology Laboratory Information Systems[END_REF]. The process of WSI is based on Whole Slide Scanners that produce Whole Slide Images and, more than often, participate in DPSs (Digital Pathology Systems), whose integration/ cooperation within the LIS's have improved the functionality of the later in means of diagnostic assistance, educational tools and quality control [START_REF] Ellin | Interoperability between Anatomic Laboratory Information Systems and Digital Pathology Systems[END_REF]. Through DPSs and Whole Slide Scanners, glass slides that are used in light microscopes by pathologists to observe and examine specimens taken from surgery, are transformed into Whole Slide Images (digital slides). The digital slides can be read by viewing software in order to navigate into a vast range of standard magnifications of sectors of the specimen. However, the variety of manufacturers that are involved in the production of different whole slide scanners poses a complicity factor in the process of reading and viewing such images. This complicity factor is explained by the fact that each digital slide, which is produced by a brand scanner, has a certain format, different from all the other formats produced by other scanners. This lack of uniformity between formats of digital slides that are produced by different manufacturers will continue to exist despite the recent efforts for the creation of standards that will pose certain patterns and regulations in the process of WSI [START_REF] Singh | Standardization in Digital Pathology: Supplement 145 of the DICOM standards[END_REF]. Apart from the difficult task of handling heterogeneous whole slide images, this paper proposes a solution to the problem of retrieving images from a dataset of digital images that are similar to a query image. Once the first technical task of deploying a universal digital image viewer is completed successfully, most formats of digital slides are available for preview, analysis, interpretation and handling. In the vast bank of data that digital images can provide, similarities are tracked and found between a query image and a dataset of images for the scope of retrieving the most similar image/s. For the purpose of detecting specific areas of interest where similarities can be found, a local feature representation, using the SURF algorithm [START_REF] Mehta | Content Based Sub-Image Retrieval System for High Resolution Pathology Images Using Salient Interest Points[END_REF], of the image is proposed due to the algorithm's promising properties concerning speed and robustness to variations. With the exploitation of SURF, interest points are, first, detected in an image and, then, the image is described by multiple 64d vectors, created in each interest point. Consequently, the image from the dataset that bears the most similarities with the query image is selected and retrieved. Similarities are defined by the score that is nominated to its image of the dataset when their interest points are compared with the interest points of the query image, not by the "naive" one-to-one comparison but by the implementation of the nearest neighbor algorithm with kdtrees.

The procedure of retrieving the image with the most similarities to the query image (best score) is explained in CBIR (Content Based Image Retrieval) methodology. For many years, image retrieval was based on text found in the meta-data attached to digital images. Text based image retrieval had faced several challenges from the early 70s up to today, mainly, concerning human effort to add annotations to images and inconsistencies between textual meta data information which describes visual content. These unsolved challenges lead to the advance of CBIR in the 80s, which has stepped forward to gain excessive terrain as a preferred method of solving image retrieval problems. In CBIR, images are indexed by their visual content automatically without the need of human intervention. CBIR can be performed in images that are represented either globally, or locally. As explained in [START_REF] Velmurugan | Content-Based Image Retrieval using SURF and Colour Moments[END_REF], local feature representations can provide the localized information of interest from a small region of the whole slide image, whereas global feature representations fail to contribute to image retrieval due to the fact that the produced global signature depicts the whole image and not the small area of interest. In reference to relevant research work that has been conducted in CBIR and Digital Pathology, Neville Mehta et al., in [START_REF] Shyu | Local versus Global Features for Content-Based Image Retrieval[END_REF], retrieves sub-images from whole slide images using scale-invariant feature extraction algorithm SIFT (Scale Invariant Feature Transform). However, SURF algorithm has been proven to be fast, more accurate and reliable than SIFT. K. Velmurugan et al., in [START_REF] Govindaraju | A Novel Content Based Medical Image Retrieval using SURF features[END_REF], used a combination of SURF and Color Moments to retrieve similar images of general context. The basic assumption to combine Color Moments in order improve the results of SURF algorithm lies on the fact that SURF is applied on gray scale images. In [START_REF] Goode | Openslide: A vendorneutral software foundation for digital pathology[END_REF], S. Govindaraju and G. P. Ramesh Kumar propose a novel CBIR system using SURF and Bag of Words to detect resemblances in medical images.

Results are compared with the use of both SIFT and SURF algorithms with the latter to prove better.

Methodology

The method, which is proposed in this paper to solve the image retrieval problem, consists of four ( 4) stages (illustrated in figure 2), as follows: i) Image preprocessing, ii) Image analysis, iii) Feature extraction and iv) Image retrieval.

Starting from the input of our system, they can be digital images downloaded from the Internet, selected regions of interest from whole slide images or images extracted from digital pathology atlases. One of these images represents the query image and all the others comprise the dataset from which the system will detect the image with the best similarity to the query image (output of the system). The following paragraphs discuss briefly the 4 stages. i) Image pre-processing. In this first stage the system creates the input images whether they take part in the search dataset, or they constitute the query image. It is important to note that not all images are ready to be analyzed by the system, as they may be contained in a PDF file or they need to be extracted from a whole slide image (being a part of it). In the case of handling .pdf files, the initial .pdf file is being processed by the system and all images are extracted in a folder by means of a java library called PDFBOX. Should a whole slide image be used, another java library called OPENSLIDE, reviewed in [START_REF] Goudas | An Advanced Image Analysis Tool for the Quantification and Characterization of Breast Cancer in Microscopy Images[END_REF], offers its functionality in order for the whole slide images to be read, previewed, and processed. If the input image is a simple digital image the system's task is trivial. In the end of this stage all digital images are ready to be analyzed, as they enter the following stage of image analysis. ii) Image analysis. Each digital image is being analyzed and the interest points are detected using the fast Hessian detector of SURF algorithm. The detector function is divided in two basic steps: 1. Tracking of interest points by means of the determinant of the approximated Hessian Matrix. This is accomplished by the use of filter boxes and integral images.

Detection of interest points by means of the non-maximum suppression technique.

In the end of this stage all interest points from all images are detected. iii) Feature extraction. Since all interest points are detected, the descriptor of SURF algorithm creates a 64-dimension vector that, uniquely describes each robust interest point of all images. The descriptor function is summarized in two basic steps, involving the orientation assignment to each interest point using Haar wavelets responses and the vector computation by adding Haar wavelets responses in horizontal and vertical axis. In the end of this stage each image has interest points that are described by 64-dimension vectors in a unique and robust manner. iv) Image retrieval. In the last stage the images with the highest score are selected. The score is calculated by adding the number of matches between the interest points of the query image and the candidate image. A match is found by calculating the Euclidean distance between vectors of the descriptors. This process is not accomplished in a naive way (one-by-one exhausting search), but by means of linear nearest neighbor search to avoid large computational cost. The results of the abovementioned methodology are influenced by the parameters of the SURF algorithm. In the following lines a laconic definition of the parameters of the parameters octaves and threshold is given in order to provide an understanding of their role in the implementation of SURF. Hessian threshold: The minimum value of the determinant of the Fast Hessian Matrix for a feature point should be selected. This parameter is closely connected to the repeability of the algorithm, which means that by lowering the threshold the outcome is weaker feature points with less repeatability. Octaves: A series of filter response maps obtained by convolving the same input image with a filter of increasing size. The Gaussian pyramid of the scale space is divided into octaves, which in turn are divided into layers. The increase of octaves detects larger features but costs in time. Layers: The next level of division of the scale space. Initial step: The initial sampling step, which is doubled for each next octave. This value determines how many pixels separate each pixel in the given pyramid octave. In the next Section we discuss the usage scenarios of the implemented system.

4

The System in Practice

An application was development in java programming language utilizing the libraries Openslide (www.openslide.org), ImageJ Surf (www.labun.com/imagej-surf), and PDFBOX (www.pdfbox.apache.org). The GUI of the application, as depicted in figure 3, is divided in two panels, the screen panel and the control panel. Four basics buttons are provided on the upper section of the main menu, as follows:

• Simple Image/WSI • Open Image • Convert PDF to file • Close App
The functionality of each button is briefly described below. a. Simple Image/WSI. By pressing this button the type of the query image is selected.

The user can choose between two options: Simple digital image or whole slide image. b. Open Image. Selected query image is read and opened in order to be viewed and processed (for WSI). c. Convert PDF to file. A digital pathology atlas can be selected and converted in a folder of digital images.

d. Close App. Self-explained. Once a query image is selected, the requested image is visible in the screen panel section, as shown in figure 3. In this case the query image is a whole slide image produced by a Trestle whole slide scanner and its format is single-file pyramidal tiled TIFF (tagged image file format). In the control panel additional functionality appears by means of two new panels, SURF parameters and properties, and three buttons: compare image to handbook, compare image to folder and reset points. By using the SURF parameters panels the user can specify the parameters of the SURF algorithm for the detection and description of interest points. In the properties field the user can view the meta-data that are stored in a whole slide image in reference to the image attributes. The buttons serve the purpose of choosing the dataset of digital images that will be compared to the query image. By choosing dataset of images and query image, the process of image retrieval begins and in the end the result appears in the screen and the image/s with the most similarities to the query image is/are shown. The number of interest points increases as the image gets brighter and decreases as the image gets darken. However, the increase of the number of interest points does not necessarily mean increase of the numbers of matches between the query and test image. The influence of the variations in brightness is slightly stronger when the pathology image gets darken (22% less matches) in respect to the brightest image (19% less matches).

The second set of experiments refers to rotation transformations. Results are illustrated in figure 5.

Fig.5 Graph of matches found between query image and test image and interest points found in test image as the rotation changes

The worst case for the rotation transformations occurs at 120 degrees (37% less matches), which is more intense that the worst case for brightness transformations.

Transformations related with the scale up and down of the query image are also tried out to check the effect of these transformations to the function of SURF algorithm.

The results are shown in figure 6. As it is projected by the graph (figure 6) the effect of minimizing the query image is devastating more than any other transformation performed (97% less matches).

Maximizing the image has a smoother impact to the algorithm with a 33% decrease on matches. Apart from the experiments performed with reference to the transformations of the query image, tests were conducted with the different values of the following parameters octaves, hessian threshold, explained earlier in Section 3, are assigned to check the influence of these variations.

The results for variations of the octaves and the threshold parameter are shown in figure 7 and8.

Conclusion

The retrieval of digital pathology images in references to similar images found in medical literature, storage systems and medical databases is the main goal of the work presented in this paper. The proposed methodology deploys a speeded up robust feature extraction technique along with a viewer that reads whole slide images. The experiments conducted confirm that the SURF algorithm fulfills the process efficiently and fast, mainly due to the small computational effort (integral images, box filters). To give a rough estimation of speed, the system compares 573 images (with the sized of 2.12 GB) extracted from a medical atlas called "Surgical Pathology of the Gastronomical System" in 5 minutes. The specific processing time refers to a desktop computer with a 3.06 GHz Intel "Core 2 Duo" Processor (E7600) and 4GB RAM. Moreover, the robustness of SURF algorithm is verified to all brightness, rotation and scale up variations of the query image apart from the scale down transformation where the efficiency of the system is proven relatively low. Even in the worst case scenario (37% less matches) the final outcome of the system is not compromised, because the remaining matches are adequate for the system to correctly classify the query image in most cases. The initial goal of the system was the retrieval of specific images that bear resemblance to others. Nevertheless, results extracted from experiments, which are performed on cancer cells digital images, imply the capability of the system to classify an image to a certain class. A suggestion for future work would be to apply the Visual Bag of Words technique to create a single vector from each image and use the results for machine learning classification. Concluding, this work might be considered as a significant adjunct tool for pathologists in their everyday work, assisting them in searching atlases, electronic books and other electronic resources for similar cases to the one that they have in front of them. Additional evaluation with real users is required to validate this assumption.

Fig. 2 .

 2 Fig. 2. Workflow diagram of the proposed methodology (Magenta boxes correspond to input/output, light green to processing steps and dark green refers to intermediate objects)

Fig. 3

 3 Fig. 3 Main menu of the application

Fig. 4 .

 4 Fig. 4. Graph of matches found between query image and test image and interest points found in test image as the brightness changes

Fig 6 .

 6 Fig 6. Graph of matches found between query image and test image and interest points found in test image as the scale changes

Fig. 7 Fig. 8

 78 Fig. 7 Graph of matches found between query image and test image and interest points found in the query image as the octave parameter changes

Table 1 .

 1 Confusion matrix of classification of 24 images in four classes (control, drug, radiation, drug n radiation)

	Actual class