Can Demirkesen
email: candemirkesen@gmail.com

Hocine Cherifi
email: hocine.cherifi@u-bourgogne.fr

A Comparison of Multiclass SVM Methods for Real World Natural Scenes

Categorization of natural scene images into semantically meaningful categories is a challenging problem that requires usage of multiclass classification methods. Our objective in this work is to compare multiclass SVM classification strategies for this task. We compare the approaches where a multi-class classifier is constructed by combining several binary classifiers and the approaches that consider all classes at once. The first approach is generally termed as "divide-and-combine" and the second is known as "all-in-one". Our experimental results show that all-in-one SVM outperforms the other methods.

Introduction

Rapidly growing need for natural image classification challenges both image content representation studies and classification techniques. A performing multiclass classifier is needed when classifying natural scenes. From model-based methods to learning algorithms, there are many choices for an appropriate classifier. Among these, support vector machines (SVMs) appear to be a good candidate because of their ability to generalize in high-dimensional spaces without the need to add a prior knowledge. The appeal of SVMs is based on their strong connection to the underlying statistical learning theory. For several pattern classification applications [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF] [START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF], SVMs have been shown to provide better generalization performance than traditional techniques such as neural networks [START_REF] Kreßel | Pairwise Classification and Support Vector Machines[END_REF].

SVM is basically conceived for binary classification. The idea is to separate two classes by calculating the maximum margin hyperplane between the training examples. Several methods have been proposed to extend SVM in order to classify more than two classes because classification problems are mostly multi class. Image classification is naturally a multi class problem as well. Currently there are two major approaches for extending SVM to multiclass classification: [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF] considering all data in a single optimization. [START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF] Combining several binary SVM classifiers; generally the first approach is called 'all-in-one' (AIO). and the second 'divide-and-combine' The main methods for divide-and-combine are One-Against-All (OAA), One-Against-One (OAO) and Directed Acyclic Graph (DAG). There is some work in the literature [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF], [START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF] comparing these methods for classical datasets like iris, wine, glass, letter etc. In [START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF], OAA, OAO MaxWins (with majority voting), DAG and AIO are compared.

The authors show that there is not one method that performs best for every dataset but that OAO MaxWins and DAG perform better with large number of classes. In [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF], OAO MaxWins, OAA, DAG and Neural Networks are compared. The authors show that the methods have comparable performance on accuracy and error rate but that OAO and DAG need less time for training phases. This conclusions point out that one should compare these methods for a specific classification problem, in this case image classification, because the best method can depend on the problem at hand. In [START_REF] Ren | Applying Multi-Class SVMs into Scene Image Classification[END_REF], OAO MaxWins, OAO-Pairwise Coupling, DAG and Neural Networks are compared for natural texture images like grass, leaves, brick etc. using a mixed color and texture representation. The authors conclude that OAO MaxWins and DAG have almost the same performance and they are both better then neural networks in terms of accuracy. In [START_REF] He | Multiclass SVM Based Land Cover Classification With Multi-Source Data[END_REF], OAO MaxWins, OAA, DAG, maximum likelihood and back propagation neural networks are compared for satellite images like water, construction, wood, bare soil etc. using topographical raster data for image representation. According to their results OAO with MaxWins majority voting is the most performing in terms of accuracy. In [START_REF] Foody | A Relative Evaluation of Multiclass Image Classification by Support Vector Machines[END_REF], AIO, neural networks, discriminant analysis and decision trees are compared for land cover images using random pixels for image representation. It is shown that AIO SVM outperforms other techniques in accuracy.

Despite all these studies there is not a fully complete comparison of multi-class SVM classification methods. The comparisons in [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF] and [START_REF] He | Multiclass SVM Based Land Cover Classification With Multi-Source Data[END_REF] do not cover OAO pairwise coupling and AIO. In [START_REF] Ren | Applying Multi-Class SVMs into Scene Image Classification[END_REF], OAA and AIO are missing. Even in the most complete comparison [START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF], OAO-Pairwise Coupling method is missing. In addition to our knowledge there is not one comparison of these methods for classification of real world natural scenes like forest, coast, mountain or city view categories and previous results show that performances are greatly influenced by nature of the data. Another criticism to existing work is that only one performance measure is used. Different performance criteria measure different tradeoffs in the predictions made by a classifier, and it is possible that a learning method performs well on one metric, but be suboptimal on other metrics. Because of this it is important to evaluate algorithms on a broad set of performance metrics.

In this paper, we evaluate and compare all of the multiclass SVM methods mentioned above on a challenging image database by following an experimental approach. We compare performance of the methods for natural image categorization task using global and local image representations. We perform an extensive evaluation using multiple performance measures. The rest of the paper is organized as follows: Section 2 introduces multiclass methods. In section 3 features used for image representation are briefly presented. Section 4 describes performance measures that we use in experimentations. Experimental results are given in section 5 and finally conclusion in section 6. fusion. In classification step an instance x is classified by all of the binary classifiers. In the fusion step, classification outputs are combined together to provide a decision.

One Against One SVM Classifiers

One-Against-One (OAO) method involves N(N-1)/2 binary SVM classifiers. Each classifier is trained to separate each pair of classes. There are different strategies used to combine these binary classifiers. The main strategies widely used in literature are 'Pairwise Coupling' and a majority voting strategy which is called 'MaxWins'. When classifiers are combined through majority voting scheme, the class with maximal number of votes is the estimation. In pairwise coupling [START_REF] Kreßel | Pairwise Classification and Support Vector Machines[END_REF], a pairwise probability

j i p , is obtained from each binary SVM output noted as ) ( , x f j i . ( ) 5 . 0 2 1 + = x f p ij ij . ( 1
)
These pairwise probabilities are coupled into a common set of posterior probabilities i p :

∑ ≠ - = i j j i i p N N p , ) 1 ( 2 .
(2)

The decision function is given by:

) ( max arg ) ( 1 i N i p x c ≤ ≤ = . (3)

DAG SVM classifiers

Directed Acyclic Graph (DAG) SVM is proposed by Platt et al [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF]. Training is the same as the OAO using N(N-1)/2 binary SVMs. However, in the testing phase, a directed acyclic graph with N(N-1)/2 internal nodes and N leaves is used. Testing a sample starts at the root node and it moves to either left or right depending on the output value. Therefore, we go through a path before reaching a leaf node, which indicates the predicted class. An advantage of using a DAG is that its testing time is less than the OAO methods. An example DAG for three classes is given in Figure 1.

One-Against-All SVM classifiers

One-Against-All (OAA) is the most common and simplest approach [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF].

) ( max arg ) ( 1 x f x c i N i≤ ≤ = Where ) (x f i
is the output of the binary SVM classifier trained for class i against all the other classes.

All-in-One

There are certain limitations of the approaches that extend binary SVMs to multi-class problems. One of these limitations is that they do not consider the full problem directly. The one-against-all approach degrade the balance of the training sets (there are far more negative training examples in each binary classifier's training set), and the one-against-one method uses only information from the two classes that it works with. Each one-against-one classifier loses the information from all the remaining classes. All-in-one (AIO) is a more natural approach that considers the multi-class problem directly as a generalization of the binary classification algorithm The idea is similar to the OAA approach. It constructs N two-class rules where the ith function separates training vectors of the class i from the other vectors. Hence there are N decision functions but all are obtained by solving one problem [START_REF] Weston | Support Vector Machines for Multi-Class Pattern Recognition[END_REF]. The decision function is:

) ( max arg ) ( 1 i i N i b x w x c + = ≤ ≤
Where i i b x w + is the hyper plane that separates the class i from the other classes.

Note that for N=2, this formulation reduces to the binary SVM decision function.

Image Representation

Existing image categorization systems in the literature can be generally classified into two categories based on the underlying framework for image content representation. The first category segments the image into some meaningful components and uses them as semantic elements to characterize image content. The second category takes an image as a whole visual appearance and characterizes image contents by using image-based global visual features. These two approaches usually called as local and global have both shortcomings, for instance global approach do not take into account individual objects. And for local approach, image sub-blocks have little correspondence with global semantic of the image. Therefore, local and global representations are used together in order to overcome their shortcomings. The role of local and global information has also been studied by numerous experiments on human participants. These studies have shown that local part-based information and global information are processed separately by human visual system then integrated together [START_REF] Vogel | Categorization of Natural Scenes: Local vs. Global Information[END_REF].

In a previous work we evaluated a collection of local and global features used to represent color, texture, edge and spectral information for binary classification [START_REF] Demirkesen | Local or Global Image Representation for Support Vector Machine Image Categorization[END_REF]. We have shown that texture leads to the highest classification accuracy as a local representation, while spectral information is the most performing global representation. We used co-occurrence matrices to characterize texture information and gist to characterize spectral information. Gist is a low dimensional representation of the scene structure based on the output of filters tuned to different orientations and scales [START_REF] Oliva | Building the Gist of a Scene: The Role of Global Image Features in Recognition[END_REF]. To sum up the previous work, holistic spatial scene properties may be best estimated using spectral information and local information is best described by texture information. The combination of texture and gist improves classification performance in binary classification. The same representations can be adopted for multi class image classification.

Performance Measures

An important aspect of our study is the use of performance criteria to evaluate multi class SVM methods. Classification techniques are now used in many domains, and different performance metrics are appropriate for each domain. There exist numerous performance measures in the literature of image classification domain. For example Precision/Recall measures are used in information retrieval. The most widely used methods are correct classification rate [START_REF] Foody | A Relative Evaluation of Multiclass Image Classification by Support Vector Machines[END_REF], error rate [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF], classification accuracy in percentage [START_REF] Ren | Applying Multi-Class SVMs into Scene Image Classification[END_REF], [START_REF] He | Multiclass SVM Based Land Cover Classification With Multi-Source Data[END_REF] and ROC curves (sensitivity-specificity curves). A brief summary of the measures with the formulas are given in Table 1.

+ -+

Let us consider that instances belong either to a positive class or to a negative class. The entries of a confusion matrix are true positives (TP) correctly classified positive instances, false positives (misclassified negatives), true negatives (correctly classified negatives) and false negatives (misclassified positives). Accuracy is the simplest way to compare two confusion matrices because it is a measure that represents the whole classification not only one class prediction. That is the reason why accuracy is the most widely used measure. In an N classification problem Precision, recall, specificity and F-measure represent the performance of the prediction for only one class. To compute these measures one has to consider the class under investigation as positive and all the other classes as negative. Kappa statistic is used to compare the degree of consensus between raters. In this context it is used to measure the quality of classification. Like accuracy, kappa statistic can represent a confusion matrix with a single value. It varies in interval [-1, 1], 1 for perfect classification and -1 for a classifier that makes wrong decision systematically. Expected values of confusion matrix elements are obtained by:

Image Database

Our image database contains 8 categories of natural scenes: highway(260), streets(292), forest(328), open country(410), inside of cities(308), tall buildings(356), coast(360) and mountain(374) images (Numbers in brackets represent the size of each categories). The database provided by Oliva and Torralba was collected from a mixture of COREL images as well as personal photographs [START_REF] Torralba | Statistic of Natural Image Categories[END_REF]. All images are colored and sized of 256x256 pixels. For each classification experiment 100 images of each category are reserved for test purpose and the remaining images are used as training set. Samples images for the 8 categories are given in Figure 2.

Choice of Modalities

We use our image database to generate two groups of images that contain both four classes. These groups are arranged in such a way that one group contains the four most similar classes and the other the four least similar ones. We use these two groups in the remaining experimentations to compare multiclass classification methods. We suppose that if two classes are similar then the binary classification performance for these classes is low and vice versa. In other words, similarity of two classes varies in the opposite way with binary classification accuracy of these classes. In order to obtain the groups of classes mentioned above we performed binary classifications between every possible pair of classes in our image database (Combination (8, 2) =28) based on a local texture feature that is obtained by extracting four attributes namely energy, entropy, homogeneity and inertia from gray level co-occurrence matrix. This feature is extracted from block of 64x64 pixels. We sorted the binary classification results by accuracy. Keeping in mind that 6 classifiers are needed to build a 4-class classifier the 6 best performing classifiers sufficient to construct a 4-class classifier are selected; these four classes are the most similar ones according to the feature that is used. Following the same procedure the four least similar classes are found. The four most similar classes are Inside of city, Street, Tall building and Mountain and the four least similar classes are Forest, Highway, Coast, Street (Figure 2 and Figure 4). This result is in accordance with ordering based on spectral signature as presented in [START_REF] Torralba | Statistic of Natural Image Categories[END_REF]. For each category the spectral signature is obtained by averaging the power spectra of a few hundred images that belong to this category. The authors showed that spectral signature is very appropriate to discriminate the categories. Categories very close to each other exhibit similar spectral signatures while for more distant categories the shape of the spectral signatures is less similar.

Classification Based on Local Representation

Texture feature that is defined in 5.2 is extracted from images on blocks of 64x64 pixels. The most similar image classes are used for classification. Classification All three performance measures agree on the rank of the strategies under investigation. The results show that the methods are ascendant ordered as AIO, OAA, OAO-MaxWins, OAO-Pairwise Coupling and DAG. One should note that the best performing two strategies (AIO and OAA) have similar training phases. Remaining three methods use the exact same binary classifiers; MaxWins voting strategy is the winner of these last three methods. The most discriminative performance measure is Kappa statistic because it has a wider range comparing to the others. We performed the same experiment using the most similar classes; results are shown in Table 3. Accuracy and kappa statistic perfectly agree with the ordering AIO, OAO-MaxWins, OAO-Pairwise Coupling, OAA and DAG. According to F-measure the ordering is OAO-MaxWins, AIO, OAO-Pairwise Coupling, DAG and OAA. This is due to the surprisingly low recall values of Inside of city and mountain classes. The extreme F-measure values for these two classes decreased the mean F-measure value for OAA and AIO. Accuracy and kappa statistic has not been influenced by that as much as mean F-measure because both accuracy and kappa statistic are calculated in a more global way to summarize the confusion matrix. Note that the overall performance decreased comparing to the previous experiment with the least similar classes.

Classification Based on Global Representation

The least similar classes have been classified using global representation; results are shown in Table 4. The methods are ordered by their performance as AIO, OAO-MaxWins, OAA, OAO-Pairwise Coupling and DAG for all three performance measure. An increase of performance is observed for all five methods comparing to the classification based on texture feature with the same classes. This shows that gist is more discriminative then texture feature. Kappa statistic is the most discriminative performance measure for this classification.

Classification results of the four most similar classes using global representation is shown in Table 5. Methods are ranked as: AIO, OAA, OAO-MaxWins, OAO-Pairwise Coupling and DAG for all the performance criteria. OAO-MaxWins, OAO-Pairwise Coupling and DAG that have the same binary classifiers are grouped together in performance rank. OAA and AIO made a second group with very similar results that can be explained by the similarity of their training phases. Overall performance in this experiment is better than the performances in classifications of the least similar In order to evaluate the redundancy of the performance measures we calculated correlation coefficients. If two measures perfectly agree on every case it means that one of the measures is redundant. Correlation coefficients for different representation systems and for two extremes cases (the least and the most similar classes) are given in Table 6. Correlation coefficients vary in interval [-1, 1]. 1 is for perfect agreement between measures and -1 for disagreement. It is noted that accuracy and kappa statistic are perfectly correlated for each of the cases. So we can use only one of them as measure of performance. Kappa statistic is a better candidate because its range is wider than accuracy. There is perfect agreement between performance measures for all experiments except from the second experiment where this is due to the sensibility of mean F-measure to an extreme case. Table 7 shows the rank of methods under investigation according to mean Fmeasure and kappa statistic separated by '+'. For example, '2+3' means that the rank of a method is 2 according to f measure; 3 according to kappa statistic.

If we exclude the experiment involving the most similar classes with a local representation (B) one should note that performance measures perfectly agree on the rank of the methods without any exception. This is also reflected on the correlation coefficient table where the correlation values are near 1. If we rank the classification strategies according to the total score for these three cases the most performing method is AIO followed by OAA, OAO-MaxWins, OAO-Pairwise Coupling and DAG. Note that the total score of OAO-MaxWins and OAA are very close. If we rank the strategies according to the total score using the four cases (A+B+C+D) the results are identical except for OAO-MaxWins and OAA which switch places. Nevertheless their scores are still very close.

To summarize we can say that AIO is always the most performing method in any situation followed by either OAO-MaxWins or OAA whose performance are very similar. One should note that there is a relation of ordering that remains unchanged for all of the four experiments and with agreement of all three performance measures without exception. OAO-MaxWins > OAO-Pairwise Coupling > DAG. It is an interesting result considering that these methods use the same binary SVM classifiers.

Conclusion

Results show that All-In-One method is the most performing SVM multiclass classification strategy for natural scene classification. This conclusion is confirmed with all four experiments performed on two separate groups of images using two different types of representation, one local, one global. We evaluated five methods, the first, fourth and last places of the ordering are very robust to image representation system and to class proximity. Our work show that the usage of multiple performance measures, multiple image representations and multiple test groups is not only preferable but also necessary because considering experiments separately leads to different performance orderings. An important result is that MaxWins majority voting is always the best performing strategy among the one-against-one strategies.

Fig. 1 .

 1 Fig. 1. Decision DAG for three classes. Each node is a binary classifier.

Fig. 2 .

 2 Fig. 2. Sample images of the database. From top left to bottom right: Forest, Highway, Coast, Street, Inside of city, Street, Mountain, Open Country, Tall building.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Sample images from the least similar classes: Forest, highway, coast, street

  one class from the rest. The winning class is the one that corresponds to the SVM with highest output value i.e. the largest decision function value. This approach may suffer from error caused by markedly imbalanced training sets. The decision function for OAA is :

		1vs3
	1vs2	2vs3
	1	2	3

It involves N binary SVM classifiers, one for each class. Each binary SVM is trained to separate

Table 1 .

 1 Performance measures derived from the confusion matrix

	Measure											Formula
	Precision									TP	/( TP	+	FP	)
	Recall									TP	/( TP	+	FN	)
	Specificity								TN	/( TN	+	FP	)
	F-measure			2.Precision.Recall/(Precision+Recall)
	Accuracy			( TP	+	TN	)	/( TP	+	TN	+	FP	+	FN	)
	Kappa	( TP	+	( TN TP	+	TN FP	) +	( FN TP )	exp -	ected ( TP	exp	TN ected	exp +	ected TN	) exp	ected	)

Table 2 .

 2 Classification results for the least similar classes using local image representation of three performance measure are presented in Table2. Mean Fmeasure is calculated by averaging F-measures of individual classes.

	Methods	MeanFmeas-ure	Accuracy	Kappa
	DAG	0.767	0.767	0.690
	OAO-Pairwise Coupling	0.774	0.775	0.700
	OAO-MaxWins	0.779	0.780	0.706
	OAA	0.783	0.785	0.713
	AIO	0.789	0.790	0.720
	results in terms

Table 3 .

 3 Classification results for the most similar classes using local representation

	Methods	MeanFmeas-ure	Accuracy	Kappa
	DAG	0.579	0.582	0.443
	OAO-Pairwise Coupling	0.592	0.590	0.453
	OAO-MaxWins	0.603	0.600	0.466
	OAA	0.552	0.587	0.450
	AIO	0.598	0.605	0.473

Table 4 .

 4 Classification results for the least similar classes global representation

	Methods	MeanFmeas-ure	Accuracy	Kappa
	DAG	0.874	0.875	0.833
	OAO-Pairwise Coupling	0.891	0.892	0.856
	OAO-MaxWins	0.914	0.915	0.886
	OAA	0.904	0.905	0.873
	AIO	0.941	0.942	0.923

Table 5 .

 5 Classification results for the most similar classes using global representation

	Methods	MeanFmeas-ure	Accuracy	Kappa
	DAG	0.773	0.775	0.700
	OAO-Pairwise Coupling	0.816	0.817	0.756
	OAO-MaxWins	0.819	0.820	0.760
	OAA	0.845	0.847	0.796
	AIO	0.858	0.860	0.813

Table 6 .

 6 Correlation Coefficients between Performance Measures

	Class Similarity	Representa-tion	Fm-Acc	Fm-Kappa	Acc-Kappa
	Least similar	Local	0.9983	0.9987	0.9995
	Most similar	Local	0.6786	0.6581	0.9995
	Least similar	Global	1.0000	0.9999	1.0000
	Most similar	Global	0.9999	1.0000	1.0000
	classes based on local representation which is an interesting conclusion that confirms
	the superiority of the discriminative power of global representation.

Table 7 .

 7 Overall Ranking of the multiclass strategies according to mean F measure and Kappa statistic A: Least similar images and local representation, B: Most similar images and

	local representation C: Least similar images and global representation D:Most similar images
	and global representation
	Methods	A	B	C	D	Total score A+C+D
	AIO	1+1	2+1	1+1	1+1	6
	OAO-MaxWins	3+3	1+2	2+2	3+3	16
	OAA	2+2	5+4	3+3	2+2	14
	OAO-Pairwise Coupling	4+4	3+3	4+4	4+4	24
	DAG	5+5	4+5	5+5	5+5	30

Multi Class SVM2.1 Divide and CombineStrategies described below can be applied to build N-class classifiers using binary SVM classifiers. They can be decomposed in two main steps: (1) classification,[START_REF] Hsu | A Comparison of Methods for Multi-class Support Vector Machines[END_REF]


Can Demirkesen
email: candemirkesen@gmail.com

Hocine Cherifi
email: hocine.cherifi@u-bourgogne.fr

Fusing Image Representations for Classification Using Support Vector Machines

Keywords: image categorization, feature level fusion, classifier fusion. I

In order to improve classification accuracy different image representations are usually combined. This can be done by using two different fusing schemes. In feature level fusion schemes, image representations are combined before the classification process. In classifier fusion, the decisions taken separately based on individual representations are fused to make a decision. In this paper the main methods derived for both strategies are evaluated. Our experimental results show that classifier fusion performs better. Specifically Bayes belief integration is the best performing strategy for image classification task.

INTRODUCTION

Semantic categorization of images requires analysis of many characteristics of an image such as color, texture and edge properties. Categorization based on these characteristics in a separate manner leads to a limited performance. Therefore it seems natural to combine all the available information in order to improve the performance in this task. Fusion of information that allows the needed improvement can be carried out on two levels of abstraction: (1) feature level fusion, (2) classifier fusion. Feature level fusion that is also known as "early fusion" or "pre-classification fusion" consists of integrating different types of information that represents an image. The integration process is performed before any classification or matching stage. Classifier fusion, on the other hand, consists of fusing classifier outputs. In this type of fusion, classification is performed on individual characteristics (features) and classification decisions are fused afterwards. Classifier fusion is also referred to as "late fusion", "decision fusion" or "mixture of experts" [START_REF] Ruta | An overview of classifier fusion Methods[END_REF].

Processing of different types of information by human visual system has been studied by numerous experiments on human participants [START_REF] Vogel | Categorization of Natural Scenes: Local vs. Global Information[END_REF]. These studies have shown that different visual cues are processed separately by human brain then integrated together. This shows the important role of fusing visual cues in image classification task for human. There is no reason for not doing the same for automatic image classification however we do not know if the human visual system performs a feature or a classifier fusion. In order to determine which one is more appropriate for computer vision one should compare the classification performances for each of the two approaches. To our best knowledge there is no work in the literature of image classification that addresses this issue. All related work is based on only one approach. In [START_REF] Spyrou | Fusing MPEG-7 Visual Descriptors for Image Classification,d Artificial Neural Networks: Formal Models and Their Applications -ICANN[END_REF], the authors address the fusion issue by focusing only on feature level fusion methods for the categorization of beach and urban images. More specifically, they use Support Vector Machines (SVM) with merging feature fusion. The authors propose to use PCA for merging the feature vectors if features do not have equivalent magnitude of numerical values. In a video content indexing task [START_REF] Benmokthar | Multi-level Fusion for Semantic Video Content Indexing and Retrieval[END_REF], the authors use two feature fusion strategies to combine features. The first strategy is the so called static feature fusion which consists of merging separate feature vectors into a unique vector. The second strategy is to merge feature vectors using Principal Component Analysis (PCA) to reduce feature dimensionality. The authors conclude that PCA obtain superior results to those obtained by the static feature fusion. These contributions show that PCA is beneficial when features are concatenated into single vector. In [START_REF] Lepistö | Combining Classifiers in Rock Image Classification -Supervised and Unsupervised Approach[END_REF], a classifier technique is used to categorize rock images. The authors propose to use Hamming distance to make the final decision on the classification result vectors (CRVs). The CRVs are generated by separate individual classifiers based on different features. In this work the results cover only classifier fusion and rock images, not natural scenes. In [START_REF] Rahman | A Feature Level Fusion in Similarity Matching to Content-Based Image Retrieval[END_REF], a content based image retrieval task is carried out with a fusion based weighted similarity matching function with experimentally selected weights. The highest weight is assigned to the similarity measure that appears to be the most accurate among the global, semi-global and local similarity measures. The proposed technique and results are not compared with another approach. SVM classifiers trained on color and texture are fused for video classification in [START_REF] Guironnet | Video Classification Based On Low-Level Feature Fusıon Model[END_REF]. A technique called Transferable Belief Model based on Dempster-Shafer theory is used for fusing classifier outputs. TREC 2004 dataset is used containing frames such as boat, beach, basket and airplane from news and advertisement which are not semantic scenes categories. Another classification system is proposed in [START_REF] Tsaı | A Modular Support Vector Image Indexing and Classification System[END_REF] where individual classifiers are trained on color and texture and they are fused using a third SVM classifier which is called as high-level concept classifier. The dataset contains sixty categories all of which are objects and animals. There is no scene categories included and the proposed classifier fusion scheme is not compared with any other fusion approach. A very similar work on indoor/outdoor classification is described in [START_REF] Savakis | A computationnaly efficient Indoor/Outdoor scene classification[END_REF] where the authors use two individual SVM classifiers based on color and texture features. Another SVM classifier is trained on the output of these two classifiers to perform a binary indoor/outdoor classification. In spite of all these works, a systematical and comparative study of feature level fusion and classifier fusion techniques for image classification is still missing. Proposed methods in the literature are generally not compared with other methods. Even in a very complete comparison of audio data classification techniques [START_REF] Moreno-Seco | Comparison of Classifier Fusion Methods for Classification in Pattern Recognition Tasks Multiple Classifier Systems[END_REF], where weighted and unweighted voting strategies are discussed, the feature level fusion approach is missing. The datasets used in these studies contain very specific categories like rock images. However, existing work show that the nature of the data influences classification performance.

In this paper we compare these two approaches for natural scenes using a variety of visual descriptors. We evaluate our results with commonly used performance criteria. The rest of the paper is organized as follows: Section 2 introduces preclassification and post classification techniques. In section 3 features used for image representation are briefly presented. Measures used to evaluate classification performances are described in section 4. Experimental results are given in section 5 and finally conclusion in section 6.

II. FEATURE LEVEL FUSION

Feature level fusion refers to combining information prior to the application of any classifier or matching algorithm [START_REF] Jaina | Score Normalizationin Multimodal Biometric Systems[END_REF]. It is performed by concatenating individual vectors to form a single feature vector. Concatenation of vectors can lead to two major problems. Firstly, the resulting feature vector may have a very large dimensionality, a problem referred to as the 'curse of dimensionality'. There exist a number of techniques to remedy the curse of dimensionality problem by reducing the dimensionality of a feature vector. The most frequently used one is Principal Component Analysis (PCA).

The second problem is the scale effect due to different magnitude of numerical values of the individual feature vectors. Scale effects can be addressed by re-scaling or normalizing feature vectors. A detailed study of normalization techniques can be found in [START_REF] Jaina | Score Normalizationin Multimodal Biometric Systems[END_REF].

III. CLASSIFIER FUSION

Classifier fusion refers to combining information after the classification or matching stage. Information to combine is the classifier output which can either be a class label or numerical output value.

A. Class Label Fusion 1) Majority Voting

Classifiers that produce class labels are generally fused using a voting method. A generalized voting definition is given below. , c i denotes the label of the i th class. Let binary characteristic function be defined as follows:

0 1 ) ( i j c B if if i j i j c d c d (1)
Then the general voting routine can be defined as:

r c d E i ) ( if otherwise m c B c B n j n j t j t j m t 1 1 } ,..., 1 { ) ( ) ( (2)
The case where 0.5 is commonly known as the majority vote.

B. Soft Output Fusion 1) Bayes Average Method

The Bayesian methods can be applied to the classifier fusion under the condition that the outputs of the classifier are expressed in posterior probabilities. Effectively combination of given likelihoods is also a probability of the same type, which is expected to be higher than the probability of the best individual classifier for the correct class.

If the outputs of the multiple classifier system are given as posterior probabilities that an input sample x comes from a particular class C i , I=1,..,m P(x c i /x), it is possible to calculate an average posterior probability taken from all classifiers:

K k i K E x C x P K x x P 1 i ) / ( 1 ) / c ( (3)
2) Bayes Belief Integration The approach mentioned above treats equally all the classifiers and does not explicitly consider different errors produced by each of them. These errors can be comprehensively described by means of confusion matrix given by:

) ( ) 1 ( ) ( 1
) ( ) 1 ( 1 ) ( 11 ... ... ... k M M k M k M k k n n n n PT (4)
where rows correspond to classes: c 1 ,...,c M from which the input sample was drawn from and columns denote the classes to which the input sample was assigned by the classifier e k .

The values ) (k ij n express how many input samples coming from class c i were assigned to class c j . On the basis of the confusion matrix PT k it is possible to build the belief measure of correct assignment as given by:

) ) ( / ( )) ( / ( k k i k i j x e c x P x e c
x Bel [START_REF] Lepistö | Combining Classifiers in Rock Image Classification -Supervised and Unsupervised Approach[END_REF] Where i=1,...,M; j=1,...,M+1 and

M i k ij k ij k i n n j x e c x P 1 ) ( ) ) ( / ( (6)
Having defined such a belief measure for each classifier we can combine them in order to create new belief measure of the multiple classifier system as follows:

K k i K k k k i i c x P j x e c x P c x P i Bel 1 1 ) ( ) ) ( / ( ) ( ) ( (7)
The probabilities used in the above formula can be easily estimated from the confusion matrix. The class with the highest combined belief measure: Bel(I) is chosen as a final classification decision. Alternatively selection of any class may be rejected if the combined belief is smaller than a specified threshold value. The decision function for a new instance x is as follows:

) ( max arg ) ( 1 i Bel x c K i (8)

IV. EXPERIMENTAL SETUP

A. Visual Descriptors

Existing image categorization systems in the literature can be generally classified into two categories based on the underlying framework for image content representation. In the first category the image is segmented into some meaningful components that are used as semantic elements to characterize image content. Or a regular grid is applied to divide the image in sub blocks. The second category takes an image as a whole visual appearance and characterizes image contents by using image-based global visual features. In a previous work we evaluated multi-class classification strategies for SVM. We have compared different image representations and concluded that texture leads to the highest classification accuracy as a local representation, while gist is the most performing global representation. We used feature level fusion to combine these representations for multi-class classification [START_REF] Demirkesen | A Comparison of Multiclass SVM Methods for RealWorld Natural Scenes[END_REF]. In this work we use two extra representations which are color layout descriptor and edge orientation histogram. Color layout descriptor is a compact and resolution-invariant MPEG-7 visual descriptor defined in the YCbCr color space and designed to capture the spatial distribution of color in an image or an arbitrary-shaped region. The feature extraction process consists of four stages. The input image is partitioned into 8x8 = 64 blocks, each represented by its average color. A DCT transformation is applied on the resulting 8x8 image. The resulting coefficients are zig-zag-scanned and only 6 coefficients for luminance and 3 for each chrominance are kept, leading to a 12-dimensional vector. Finally, the remaining coefficients are quantized [START_REF] Manjunath | Color and texture descriptors[END_REF]. Edge histogram descriptor captures the spatial distribution of edges. Four directions of edges (0 ±, 45 ±, 90 ±, 135 ±) are detected in addition to non-directional ones. The input image is divided in 16 non-overlapping blocks and a block-based extraction scheme is applied to extract the five types of edges and calculate their relative populations, resulting in a 80dimensional vector. Our texture representation is obtained by extracting four attributes namely energy, entropy, homogeneity and inertia from gray level co-occurrence matrix. This feature is extracted from blocks of 64x64 pixels. Since our images are 256x256 pixel it leads to 16x4=64-dimensional vector. We use gist to characterize spectral information. Gist is a low dimensional representation of the scene structure based on the output of filters tuned to different orientations and scales [START_REF] Oliva | Building the Gist of a Scene: The Role of Global Image Features in Recognition[END_REF]. Our gist feature is a 476-dimensional vector.

B. Image Database

Our image database contains 8 categories of natural scenes: highway(260), streets(292), forest( 328), open country(410), inside of cities(308), tall buildings(356), coast(360) and mountain(374) images (Numbers in brackets represent the size of each categories). The database provided by Oliva and Torralba was collected from a mixture of COREL images as well as personal photographs [START_REF] Oliva | Building the Gist of a Scene: The Role of Global Image Features in Recognition[END_REF]. All images are colored and sized of 256x256 pixels. For each classification experiment 100 images of each category are reserved for test purpose and the remaining images are used as training set. Samples images for the 8 categories are given in Figure 1. We used our image database to obtain 4 couples such that they are visually the most similar categories. These couples are Street-Inside of city, Tall building-Street, Mountain -Tall building and Mountain-Inside of city. The reason why we have chosen the most similar categories is to obtain worst case scenarios for binary classification. We suppose that if two classes are similar then the binary classification performance for these classes is low and vice versa. In other words, similarity of two classes varies in the opposite way with binary classification accuracy of these classes. The strategy used to find the most similar classes is described in a previous work [START_REF] Demirkesen | A Comparison of Multiclass SVM Methods for RealWorld Natural Scenes[END_REF]. It is in accordance with visual judgment. Note that the street scene and inside of city scene in figure 2 are very similar but they belong to different classes.

V. EXPERIMENTAL RESULTS

A. Feature Level Fusion

To evaluate feature fusion strategies, we performed a set of binary classification experiments using the most similar classes. The reason for choosing the most similar classes is to see the difference between results in a larger scale. We preferred binary classification for the simplicity and clarity of the results. It is sufficient to illustrate the difference between the compared strategies.

In each experiment we used all of the image representation described in paragraph 3. For feature level fusion these representations are fused by concatenating the corresponding feature vectors. Normalization can be performed in two ways. The first one is to normalize each individual feature vector then concatenate those in order to obtain one large vector. We term this as pre-normalization. The second way is to concatenate the individual feature vectors first then to normalize the obtained larger vector. This can be termed as post-normalization. PCA is applied like the postnormalization. A large vector that contains multiple feature vectors is processed to obtain the principle components. The resulting feature vector is smaller in dimension. In a previous work we had compared several normalization functions and we concluded that z-score lead to the highest accuracies among the other functions namely decimal, minmax, tanh and median normalization functions. Therefore we used the z-score as a normalization function in our experiments to transform the features into a common numerical range. Classification results using feature level fusion for the four modalities in terms of accuracy are given in the following table. According to these results PCA is more performing than normalization techniques independently of the modalities which is in accordance with the results in the literature. Prenormalization and post-normalization lead to very similar results however pre-normalization is slightly better. This can be explained by the original input distribution of the features is better retained by performing the pre-normalization. This conclusion indicates that it is preferable to use PCA not only for the better classification accuracy but also for the performance increment in training phase due to the smaller size of feature vector. We compared majority voting as class label fusion, Bayes average and Bayes Belief Integration as soft output fusion methods using the same modalities. Classification results are shown in Table 2. The most performing method is Bayes belief integration with a slight difference with Bayes average method.

B. Classifier Fusion

One should note that soft output fusion strategies lead to better performance than class label fusion. This means that fusing numerical classifier outputs is preferable than fusing decisions. This is due to better interpretation of the information provided by the classifiers.

C. Comparison of Feature Level Fusion and Classifier

Fusion Table 3 illustrates the classification results obtained using the best methods derived from both strategies. Results show that Bayes Belief Integration method outperforms PCA in each of the binary classifications. This result shows that classifier fusion is advantageous for this task. For each of the binary classifications, accuracies are higher in classifier fusion. This can be explained by the fact that the classifier fusion methods use more resources then feature fusion methods. For instance, to perform a binary classification using classifier fusion, four individual binary classifiers are trained each of which on a single feature. On the other hand using feature level fusion this task could be carried out using only one binary classifier.

Classifier fusion outperforms feature level fusion. The least performing classifier fusion method which is the majority voting leads to better results than the most performing feature level fusion.

VI. CONCLUSION

We have presented a comparison feature level fusion and classifier fusion for natural scene image classification using SVM. According to our results classifier fusion strategies seem to perform better that the feature level fusion strategies. This conclusion is confirmed with all experiments performed on four modalities of image groups using all types of image representation namely color, texture, edge and gist.

In order to improve classification accuracies one should treat image representation individually not concatenate them.

Which means classifier fusion is more appropriate then feature level fusion to have high classification performance. Furthermore, fusion of individual classifiers should be done in a numerical output level not in decision level.

  The decision vector d formed by the output of the classifiers is defined as:

Fig. 1 .

 1 Fig. 1. Sample images of the database. From top left to bottom right: Forest, Highway, Coast, Street, Inside of city, Street, Mountain, Open Country, Tall building.

Fig. 2

 2 Fig. 2 Sample images of two least similar and two most similar classes. From left to right: Highway, Forest, Street and Inside of city.

TABLE I .

 I

		FEATURE LEVEL FUSION
	Modalities	Pre Normalization	Post Normalization	PCA
	Street-Inside of city	0.55	0.53	0.58
	Tall building-Street	0.69	0.66	0.71
	Mountain -Tall building	0.66	0.69	0.70
	Mountain-Inside of city	0.74	0.75	0.77

TABLE III .

 III FEATURE LEVEL FUSION VS. CLASSIFIER FUSION

		Feature Level Fusion	ClassifierFusion
	Modalities	PCA	BayesBeliefIntegration
	Street-Inside of city	0.58	0.66
	Tall building-Street	0.71	0.80
	Mountain -Tall building	0.70	0.83
	Mountain-Inside of city	0.77	0.88


C Demirkesen¹
email: candemirkesen@gmail.com

H Cherifi¹

An Evaluation of Divide-and-Combine Strategies for Image Categorization by Multi-Class Support Vector Machines

Keywords: image categorization, multiclass classification, support vector machines

Introduction

Increasing need for image organization and retrieval triggers new research of multiclass image classification methods. From model-based methods to learning algorithms, there are many choices for an appropriate classifier. Among these, support vector machines (SVMs) appear to be a good candidate because of their ability to generalize in high-dimensional spaces without the need to add a prior knowledge. However, achieving high image classification accuracy is quite challenging. SVM is originally designed for binary classification [START_REF] Boser | A training algorithm for optimal margin classi¯ers[END_REF]. The idea is to separate two classes by calculating the maximum margin hyper plane between the training examples. Several methods have been proposed to extend SVM in order to classify more than two classes because classification problems are mostly multi class. Image classification is naturally a multi class problem as well. Basically there are two major approaches for extending SVM to multiclass classification: [START_REF] Boser | A training algorithm for optimal margin classi¯ers[END_REF] considering all data in a single optimization. [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF] Combining several binary SVM classifiers; generally the first approach is called 'allin-one' (AIO) [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF], and the second 'divide-and-combine'. Due to several complexity issues the all-in-one method is generally avoided in favor of divide-and-combine approach. The main methods for divide-and-combine are One-Against-All (OAA) also known as 'winner-takes-all' [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF], One-Against-One (OAO) implemented by four different strategies: (1) MaxWins majority voting [START_REF] Friedman | Another approach to polychotomous classification[END_REF], [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF] pairwise coupling [START_REF] Hastie | Classification by pairwise coupling[END_REF], (3) error correcting codes [START_REF] Dietterich | Solving multiclass problem via error-correcting outputcode[END_REF], [START_REF] Friedman | Another approach to polychotomous classification[END_REF] directed acyclic graph (DAG) [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF], Half-Against-Half (HAH) [START_REF] Lei | Half-Against-Half Multiclass Support Vector Machines[END_REF]. There is some work in the literature comparing these methods for classical datasets like iris, wine, glass, letter etc. In [START_REF] Hsu | A Comparison of Methods for Multiclass Support Vector Machines[END_REF], OAA, OAO MaxWins and DAG are compared. The authors show that there is not one method that performs best for every dataset but that OAO MaxWins and DAG perform better with large number of classes. In [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF], OAO MaxWins, OAA, DAG and Neural Networks are compared. The authors show that the methods have comparable performance on accuracy and error rate but that OAO and DAG need less time for training phases. HAH, OAO MaxWins, OAA and DAG are compared in [START_REF] Lei | Half-Against-Half Multiclass Support Vector Machines[END_REF]. It is shown that HAH is competitive with the others in accuracy. This conclusions point out that one should compare these methods for a specific classification problem, in this case image classification, because the best method can depend on the problem at hand. In [START_REF] Ren | Applying Multi-Class SVMs into Scene Image Classification[END_REF], OAO MaxWins, OAO-Pairwise Coupling, DAG and Neural Networks are compared for natural texture images like grass, leaves, brick etc. using a mixed color and texture representation. The authors conclude that OAO MaxWins and DAG have almost the same performance and they are both better then neural networks in terms of accuracy. In [START_REF] He | Multiclass SVM Based Land Cover Classification With MultiSource Data[END_REF], OAO MaxWins, OAA, DAG, maximum likelihood and back propagation neural networks are compared for satellite images like water, construction, wood, bare soil etc. using topographical raster data for image representation. According to their results OAO with MaxWins majority voting is the most performing in terms of accuracy. Despite all these studies there is not a fully complete comparison of multi-class SVM classification methods. The comparisons in [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF] and [START_REF] He | Multiclass SVM Based Land Cover Classification With MultiSource Data[END_REF] do not cover OAO pairwise coupling. In [START_REF] Ren | Applying Multi-Class SVMs into Scene Image Classification[END_REF], OAA and ECOC are missing. Even in the most complete comparison [START_REF] Crammer | On the algorithmic implementation of multiclass kernel-based vector machines[END_REF], OAO-Pairwise Coupling method is missing. In addition to our knowledge there is not one comparison of these methods for classification of real world natural scenes like forest, coast, mountain or city view categories and previous results show that performances are greatly influenced by nature of the data. In this paper, we evaluate and compare all of the divideand-combine multiclass SVM methods mentioned above on a challenging image database by following an experimental approach. We compare performance of the methods for natural image categorization task using global and local image representations. The rest of the paper is organized as follows: Section 2 introduces multiclass methods. In section 3 features used for image representation are briefly presented. Experimental results are given in section 5 and finally conclusion in section 6.

Binary Classification by SVM

Support vector machines have strong theoretical foundations and excellent empirical successes. We consider SVMs in the binary classification setting. In their simplest form, SVMs are hyper planes that separate the training data by a maximal margin.

We are given the training data {x1 ... xn} in some space X and their labels {y1 … yn} where yi in {-1, l}.The objective is to find a hyperplane which divides the set of instances such that all the points with the same label are on the same side of the hyperplane [START_REF] Lei | Half-Against-Half Multiclass Support Vector Machines[END_REF]. This amounts to finding w and b so that

( ) , 0 > + ⋅ b x w y i i N i ,..., 1 = (1)
If a hyperplane satisfying (1) exists, it is possible to write

( ) , 1 min 1 ≥ + ⋅ ≤ ≤ b x w y i i N i N i ,..., 1 = (2)
Once w and b are calculated the decision function is: ( )

) ( b x w sign x f + ⋅ = (3)

K-Classification by Divide-and-Combine

Strategies described below can be applied to build N-class classifiers using binary SVM classifiers. They can be decomposed in two main steps: (1) classification, (2) fusion. In the classification step an instance x is classified by all of the binary classifiers. In the fusion step, classification outputs are combined together to provide a decision.

One-Against-One SVM classifiers

One-Against-One (OAO) method involves N(N-1)/2 binary SVM classifiers. Each classifier is trained to separate each pair of classes. There are different strategies used to combine these binary classifiers.

MaxWins Majority Voting

Each of the N(N-1)/2 SVMs casts one vote for its favored class, and finally the class with most votes wins. This strategy must address the case of equality between the votes of the classes. This weakness can be rectified by adding a very simple rule to the original algorithm. For example, [START_REF] Hsu | A Comparison of Methods for Multiclass Support Vector Machines[END_REF] propose to decide the class with smaller index if two classes are equally voted.

Pairwise Coupling

In pairwise coupling [START_REF] Hastie | Classification by pairwise coupling[END_REF], a pairwise probability p ij is obtained from each binary SVM output noted as f ij (x).

( ) 5 . 0 2 1 + = x f p ij ij (1) These pairwise probabilities are coupled into a common set of posterior probabilities i p ∑ ≠ - = i j j i i p N N p ) ( ) 1 ( 2 , σ (2)
Where σ (.) is one of the functions presented in Table 1.

σ ( )

j i p , σ PWC1 ( ) ij ij p p = σ PWC2 ( ) ⎩ ⎨ ⎧ ≥ = otherwise x ifp p ij ij , 5 . 0 , 1 σ PWC3 ( ) ⎩ ⎨ ⎧ ≥ = otherwise p p ij ij , 0 5 . 0 , 1 σ PWC4 ( ) 5 . 0 2 / 1 1 1 - - + = ij p ij e p σ Table 1.

Examples of pairwise coupling functions

The decision function is given by:

) ( max arg ) ( 1 i N i p x c ≤ ≤ = (3)

DAG SVM classifiers

Directed Acyclic Graph (DAG) SVM is proposed by Platt et al [START_REF] Platt | Large Margin Dags for Multiclass Classification[END_REF]. Training is the same as the OAO using N(N-1)/2 binary SVMs. However, in the testing phase, a directed acyclic graph with N(N-1)/2 internal nodes and N leaves is used. Testing a sample starts at the root node and it moves to either left or right depending on the output value. Therefore, we go through a path before reaching a leaf node, which indicates the predicted class. An example DAG for three classes is given in Figure 1.

Error Correction Output Coding

Error-correcting output coding (ECOC) is another oneagainst-one combination strategy [START_REF] Dietterich | Solving multiclass problem via error-correcting outputcode[END_REF]. A unique binary string of length L called codeword is assigned to each class. L binary classifiers are built by learning L function.

A set of 6-bit codewords assigned to four classes is shown in Table 2, where the columns f 1 ,…, f 6 represent the classifiers to be trained. All columns are distinct and each classifier learned is a disjunction of the classes. For

example, f 2 (x) = 1 if x is in class 1 or 4. Class 1 f 2 f 3 f 4 f 5 f 6 f 1 1 1 1 1 1 1 2 0 0 0 1 1 1 3 0 0 1 1 0 0 4 0 1 0 1 0 1
⎩ ⎨ ⎧ = 0 1 i c if otherwise f i 0 ≥
The generated codeword C is compared to the preassigned codewords for each class; the closest class in terms of Hamming distance between the codewords gives the classification of x.

One-Against-All SVM classifiers

One-Against-All (OAA) is the most common approach [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF]. It involves N binary SVM classifiers, one for each class. Each binary SVM is trained to separate one class from the rest. The winning class is the one that corresponds to the SVM with highest output value i.e. the largest decision function value. This approach may suffer from error caused by imbalanced training sets.

Half-Against-Half multi-class SVM

In Half-Against-Half (HAH), similar classes are grouped together as a bigger category. Two categories are obtained from the dataset and then matched against each other. The structure of the classifier is the same as a decision tree with each node as binary SVM. The classification procedure goes from root to the leaf guided by the binary SVMs. Given that similar or close classes are grouped together for training phase the biggest challenge is to determine the optimum divisions [START_REF] Lei | Half-Against-Half Multiclass Support Vector Machines[END_REF]. A sample decision tree for classifying four classes is given in Figure 2. extracted from the whole image without segmenting or dividing it into sub-blocks.

These two approaches have both advantages and disadvantages. For example when global image representation is used, an individual object in the image may have due care or attention. Small details can be neglected. When local representation is used global semantic of the image is not taken into account. Spatial relationship between regions or objects is not considered.

When the role of local and global representation has been studied by experiments on humans, it is noted that local and global information are separately processed by human visual system then integrated together. In a previous work we evaluated a collection of local and global features used to represent color, texture, edge and spectral information for binary classification [START_REF] Demirkesen | Local or Global Image Representation for Support Vector Machine Image Categorization[END_REF]. We have shown that texture leads to the highest classification accuracy as a local representation, while gist is the most performing global representation. We used co-occurrence matrices to characterize texture information. Gist is a low dimensional representation of the scene structure based on the output of filters tuned to different orientations and scales. It is calculated using power spectrum of the image and a series of Gabor filters [START_REF] Oliva | Building the Gist of a Scene: The Role of Global Image Features in Recognition[END_REF]. To sum up the previous work, holistic spatial scene properties may be best estimated by gist and local information is best described by texture information. The combination of texture and gist improves classification performance in binary classification. The same representations can be adopted for multi class image classification.

5 Experimental Results

Image Database

Our image database contains 8 categories of natural scenes: highway(260), streets(292), forest( 328), open country(410), inside of cities(308), tall buildings(356), coast(360) and mountain(374) images (Numbers in brackets represent the size of each categories). The database provided by Oliva and Torralba was collected from a mixture of COREL images as well as personal photographs [START_REF] He | Multiclass SVM Based Land Cover Classification With MultiSource Data[END_REF]. All images are colored and sized of 256x256 pixels. For each classification experiment 100 images of each category are reserved for test purpose and the remaining images are used as training set. Sample images for the 8 categories are given in Figure 3. We use our image database to generate two groups of images that contain both four classes. These groups are arranged in such a way that one group contains the four most similar classes and the other the four least similar ones. We use these two groups in the remaining experimentations to compare multiclass classification methods. We suppose that if two classes are similar then the binary classification performance for these classes is low and vice versa. In other words, similarity of two classes varies in the opposite way with binary classification accuracy of these classes. In order to obtain the groups of classes mentioned above we performed binary classifications between every possible pair of classes in our image database (Combination (8, 2) =28) based on a local texture feature that is obtained by extracting four attributes namely energy, entropy, homogeneity and inertia from gray level co-occurrence matrix. This feature is extracted from block of 64x64 pixels. We sorted the binary classification results by accuracy. Keeping in mind that 6 classifiers are needed to build a 4-class classifier the 6 best performing classifiers sufficient to construct a 4-class classifier are selected; these four classes are the most similar ones according to the feature that is used. Following the same procedure the four least similar classes are found. The four most similar classes are Inside of city, Street, Tall building and Mountain and the four least similar classes are Forest, Highway, Coast, Street (Figure 4 and Figure 5). This result is in accordance with ordering based on spectral signature as presented in [START_REF] He | Multiclass SVM Based Land Cover Classification With MultiSource Data[END_REF]. For each category the spectral signature is obtained by averaging the power spectra of a few hundred images that belong to this category. The authors showed that spectral signature is very appropriate to discriminate the categories. Categories very close to each other exhibit similar spectral signatures while for more distant categories the shape of the spectral signatures is less similar.

Comparison of Pairwise Coupling Functions

The goal of this paragraph is to compare the pairwise coupling functions defined in 3.1.2. Once the best of these functions is found the further comparison of the methods will cover only the pairwise coupling method with the best performing function only. This will increase the readability and clarity of further results and help us to analyze the results in a more appropriate manner. Results are given in terms of accuracy which is the most widely used performance measure in image classification domain. Accuracy is the simplest way to compare two confusion matrices because it is a measure that represents the whole classification with a single value. It varies in interval [0,1], 1 for perfect classification and 0 for a classifier that makes wrong decision systematically. The results obtained using the most similar dataset are in accordance with the previous results. The only difference is that the accuracy values are lower.

Comparison of OAO against other strategies

We performed the same experiments for HAH and OAA. For all the experiments, HAH is always the least performing strategy. As shown in Table 6, OAO-MaxWins rank first for global representation while OAA wins for local representation. The results are inverted when we performed the experiment with the most similar classes. In fact the performances are so close that it is very difficult to choose between the two of them.

Conclusion

We evaluated Divide-and-combine multi-class SVM methods. Results show that OAO-MaxWins and OAA are the most performing strategies for combining binary classifiers in natural scene classification task. This conclusion is confirmed by experiments performed on two separate groups of images using two different types of representation, local and global. Our work shows that the usage of multiple image representations and multiple test groups is not only preferable but also necessary because considering experiments separately leads to different performance orderings.

Fig. 1 .

 1 Fig. 1. Decision DAG for four classes. Each node is a binary classifier

Fig. 2 .

 2 Fig. 2. Decision tree for classifying four classes. Each node is a binary classifier

Fig. 3 . 5 . 2 Fig. 4 .Fig. 5 .

 35245 Fig. 3. Sample images of the database. From top left to bottom right: Forest, Highway, Coast, Street, Inside of city, Street, Mountain, Open Country, Tall building 5.2 Choice of Modalities

Table 2 .

 2 Error-correcting output codes for four-class problem with minimum Hamming distance of two.

	To classify a test example x, the L SVM outputs are
	combined to generate a codeword	C =	( 1 c	,...,	c	L	)	as
	follows:

Table 3

 3 The same experiment is repeated for the classification of the most similar classes. Results are given in Table4. The ranking of the functions remain the same except for PWC3 and PWC4 for global representation only. The winner is PWC1 again for this experiment. According to these result we can conclude that the most performing pairwise coupling function is PWC1.

	shows the classification results of the least similar
	classes using local and global representations. Texture
	representation as a local representation used in this
	experiment is defined in 5.2. Gist used as a global
	representation is described in 3.
		Local	Global
	PWC1	0.775	0.892
	PWC2	0.760	0.883
	PWC3	0.710	0.835
	PWC4	0.692	0.822
	Table 3. Classification results for the least similar classes
		using pairwise coupling
	According to the results in Table 3, PWC1 is the most
	performing pairwise coupling function among the four
	different functions. Functions are ranked as PWC1 to
	PWC4.

Comparison of the one-against-one strategies

  To evaluate the one-against-one strategies, we performed a set of experiments. We used both local and global image representation as mentioned in the previous paragraph. Two extreme cases have been investigated namely the classification of the most and the least similar classes. Classification results in terms of accuracy for the least similar classes using global and local representations are given in Table5.

	Methods	Local	Global
	DAG	0.767	0.875
	PWC1	0.775	0.892
	ECOC	0.780	0.900
	OAO-MaxWins	0.780	0.915

Table 5 .

 5 Classification results for the least similar classes using one-against-one strategies.

	According to the classification accuracies, the ordering of
	the multi-class SVM methods in ascendant performance is
	DAG, PWC1, ECOC, and OAO-MaxWins. The ordering
	is not influenced by the type of image representation. It
	seems that we can consider two classes of strategies with
	similar performances. The most performing class contains
	ECOC and OAO-MaxWins, while the least performing
	class group DAG and PWC1.
	An increase of performance is observed for all methods
	comparing to the classification based on local texture
	feature with the same classes. This shows that global
	representation is more discriminative then local.

Table 6 .

 6 Considering the least similar classes, we first regrouped Highway and Street classes against Forest and Coast. For the most similar classes, Street and Inside of city are joined and Tall building and Mountains formed the other group. In Table6the performances of both strategies with the best OAO method in terms of accuracy are compared. Classification results for the least similar classes of OAO against other strategies.

	Methods	Local	Global
	HAH	0.770	0.878
	OAA	0.785	0.905
	OAO-MaxWins	0.780	0.915

Authorized licensed use limited to: ULAKBIM UASL -Galatasaray Universitesi. Downloaded on February 26, 2009 at 04:44 from IEEE Xplore. Restrictions apply.


Thibault Lemattre

Bruno Denis

Jean-Marc Faure

Jean-Franc ¸ois Pétin

Patrick Salaün

Designing operational control architectures of critical systems by reachability analysis

This paper presents a method that eases the design of the operational architecture of a control system by providing, from the knowledge of some characteristics of the functions that the control system must ensure and a generic model of controller, an assignment solution of these functions that satisfies capabilities and distribution constraints. This method relies on the verification of a reachability property on a network of communicating automata that models the assignment process. The benefit of this proposal is illustrated by a non-trivial case study from industry.

I. INTRODUCTION

Whatever the process, the operational control architecture of an industrial process is composed of several controllers (PLCs or real-time industrial computers) which gather information from the process through sensors, execute the functions that are required to control correctly the process (physical parameters regulation, tasks synchronization, operation modes management, ) and generate signals towards the process. A controller is then a physical device that permits to implement one or several control functions by providing the necessary hardware resources and in particular logic and analogic interfaces from/to the process.

Moreover, for critical processes like for instance power production and distribution, several kinds of controllers with different integrity levels are to be used to build the operational architecture. Safety-related functions must indeed be implemented in controllers with a high integrity level, with several internal redundancies, while implementation of less critical functions requires controllers with lower integrity levels.

Design of the operational control architecture of a critical process requires then to assign all the necessary control functions to controllers, while satisfying constraints that are related to:

• the capabilities (numbers of the different kinds of resources) of the controllers; • the distribution of functions, because two functions may or may not be combined into a single controller according to their safety levels. In the current industrial practice, the assignment of functions to controllers is performed in a non-automated way, based on the expertise of designers, and is a tedious and timeconsuming task. This paper aims to address this problem by proposing a method (Figure 1) which provides, from the knowledge of the characteristics of the control functions to implement and a generic model of controller, an assignment solution respecting the capabilities and distribution constraints.

This proposal is based on the verification of a reachability property in a discrete state space. Such an approach has been already used successfully in [START_REF] Behrmann | Production scheduling by reachability analysis -a case study[END_REF] and [START_REF] Subbiah | Short-Term Scheduling of Multi-Product Batch Plants with Sequence-Dependent Changeovers Using Timed Automata Models[END_REF]. This contribution differs from these two references because time is not considered in an assignment problem. It should be also emphasized that this work constitutes a prerequisite for the evaluation of the time performances of the operational architecture. The results obtained in this field by using simulation techniques ( [START_REF] Marsal | Evaluation of Response Time in Ethernet-based Automation Systems[END_REF], [START_REF] Meunier | Temporal performance evaluation of control architecture in automation systems[END_REF], [START_REF] Dmitry | An Evaluation of Network Response Time using a Coloured Petri Net Model of Switched LAN[END_REF]), formal verification [START_REF] Ruel | Finding the bounds of response time of networked automation systems by iterative proofs[END_REF], or algebraic approaches [START_REF] Addad | Modeling and Response Time Evaluation of Ethernet-based control Architectures using Timed Event Graphs and Max-Plus Algebra[END_REF], assume indeed that the processing times of the controllers are known, which of course requires that all functions have been previously assigned.

The paper is organized as follows. The elements of the problem (control functions, controllers, and assignment constraints) are formally defined in Section II. Section III describes the way to obtain automatically an assignment solution by reachability analysis, while the implementation of this principle by using a formal verification tool is detailed in Section IV. The value of this contribution is shown in Section V thanks to two cases studies: a simple case with an illustrative purpose, and a larger one to emphasize scalability. Prospects for further work are given in Section VI.

II. MODELLING OF THE ELEMENTS OF THE PROBLEM

This section aims at presenting all the notations used and at illustrating the assignment process on a toy example. The following assumptions are retained for this study:

• a controller can host between 0 to n functions, as long as the assignment constraints are met; • a function must be assigned to one and only one controller; • a function cannot be decomposed into smaller ones;

• there is no hierarchy of functions.

A. Notations used

Let F be the set of functions f i , with i ∈ {1, .., L} and C the set of controllers c j , with j ∈ {1, .., M}, L and M ∈ N * . The assignment of the function f i to the controller c j will be denoted by c j ← f i .

1) Formal definition of a function: A function f i ∈ F is defined as a 5-tuple (SL i , NI i l , NI i a , NO i l , NO i a ) with: • SL i ∈ SL (Safety Level); the lower the safety level is, the more critical the function is. In the sequel of this paper, the functions are ranked in four levels; hence, the set SL is SL = {1, 2, 3, 4}; • NI i l , NI i a ∈ N: numbers respectively of logic and analogic input data of the function;

• NO i l , NO i a ∈ N: numbers respectively of logic and analogic output data of the function.

2) Formal definition of a controller: A controller c j ∈ C is defined as a 5-tuple (CF j , LI j max , AI j max , LO j max , AO j max ) with: • CF j ∈ CF (Criticality Factor) 1 , the lower the criticality factor is, the more reliable the controller is; the initial value (when no function is assigned to controller c j ) of CF j is 0, ∀ j. CF j is changed during the assignment process while respecting the distribution constraints given in 3; • LI j max , AI j max ∈ N maximum numbers of respectively logic and analogic input interfaces of the controller; • LO j max , AO j max ∈ N maximum numbers of respectively logic and analogic output interfaces of the controller.

3) Assignment constraints: Two types of constraints determine the assignment of functions in this study:

1) capabilities constraints in terms of numbers of inputs/outputs of the controllers, 2) constraints on distribution of functions.

• capabilities constraints ;

Let:

-

F j = { f i ∈ F|c j ← f i } be the set of functions f i which are assigned to c j ; -I j = {i ∈ {1, ..., L}|c j ← f i }.
1 This feature is also termed Integrity Level.

Then the following four conditions must hold:

∀ j ∈ {1, ..., M} ∑ i∈I j NI i l ≤ LI j max (1) ∑ i∈I j NI i a ≤ AI j max (2) ∑ i∈I j NO i l ≤ LO j max (3) ∑ i∈I j NO i a ≤ AO j max (4)
• distribution constraints ; A relation ℜ from SL to CF then defines the possible associations between the safety level of a function and the criticality factor of a controller : ∀ j ∈ {1, ..., M} such that Card(F j ) > 0, SL i ℜ CF j . For safety reasons, the functions must be assigned to the controllers according to their safety levels. The most critical functions (SL i = 1) must be gathered in controllers which do not host any less critical function. The other functions may be gathered in a single controller as follows:

safety level 2 functions with safety level 3 functions; safety level 3 with safety level 4 functions. Hence, a controller c j must host, when all functions have been assigned:

only safety level 1 functions, its criticality factor is then equal to 1; safety level 2 and 3 functions only, its criticality factor is then equal to 2; safety level 3 and 4 functions only, its criticality factor is then equal to 3. The relation ℜ is then defined as follows:

ℜ = {(1, 1), (2, 2), (3, 2), (3, 3), (4, 3)} ⊂ SL ×CF (5)
This relation is depicted graphically in figure 2.

B. Illustration of the assignment of functions

This toy example is based on a set of five functions f 1 , f 2 , f 3 , f 4 , f 5 , whose safety level is in {1, 2} ⊂ SL, and which are defined as follows:

• f 1 = (2, 5, 4, 1, 3) • f 2 = (1, 5, 6, 2, 4) • f 3 = (2, 1, 3, 6, 4) • f 4 = (1, 6, 8, 5, 2) • f 5 = (1, 3, 4, 5, 2)
These functions have to be assigned on a set of three controllers c 1 , c 2 , c 3 , whose capabilities are the same: ∀ j ∈ {1, 2, 3}, LI j max = AI j max = LO j max = AO j max = 10 One possible assignment of these functions to the three controllers is described in Figure 3. This solution was obtained by first assigning the function f 1 to the controller c 1 , thus fixing the value of its criticality factor to CF 1 = 2. The function f 2 was then assigned to the controller c 2 , thus fixing the value of its criticality factor to CF 2 = 1. Then the function f 3 was assigned to the controller c 1 because its safety level is consistent with CF 1 = 2 and the sums of the numbers of inputs/outputs of the two functions do not exceed the capabilities of the controller. The function f 4 was then assigned to the controller c 3 because the sums of logic and analogic inputs of functions f 2 and f 4 are beyond the capabilities of the controller c 2 . The function f 5 was finally assigned to controller c 2 , because the remaining capabilities of the controller c 3 were too small for f 5 be assigned to it. It should be noted that this solution is not unique. As the controllers have the same numbers of inputs/outputs, other satisfactory solutions can be obtained through a circular permutation of controllers or simply by swapping two controllers. These solutions are equivalent to the one detailed above, provided no other constraint is introduced. Fig. 3. Example of assignment of five functions to three controllers III. METHOD PROPOSED The method proposed for the automatic assignment of functions is based on two principles:

• modelling the assignment problem as a set of competing question-response mechanisms between models, in the form of communicating automata, of assignment requests and of requests acceptances; • investigating whether the execution of this set, which is a network of communicating automata, can lead to a state reachable from the initial state where all functions are assigned. This section first presents the formalism used to construct the request and acceptance models, which are then detailed. The state of the network of automata characterizing the assignment of all functions is then defined, which allows to state the reachability property searched.

A. Definition of the formalism used

The formalism used is a network of automata communicating through shared variables and synchronized by transition labels. An automaton A is a N-tuple A = (S, X, L, T, S m , s 0 , v 0 ), where:

• S is a finite set of locations; • X is a set of n integer variables; • L is a set of labels which can be decomposed into three disjoint sets L i , L o , L l , where -L i is the set of reception labels; -L o is the set of emission labels; -L l is the set of local labels (internal labels of an automaton).

• T is a set of transitions (s, l, g, m, s ) ∈ S ×L×G×M ×S, where G is the set of guards (conditions on the variables of X) and M is the set of updates on the valuations of variables; • S m is a set of marked locations; • s 0 is the initial location; • v 0 is the initial valuation of variables. A trace (or execution) of A is a succession of evolutions from the initial state:

(s 0 , v 0 ) t1 → (s 1 , v 1 ) t2 → (s 2 , v 2 )... tn → (s n , v n ).
A network of automata NA = A 1 A 2 ... A n is defined as NA = (S, X, L, T, S m , s 0 , v 0 ), with:

• S ⊆ S 1 × S 2 × ... × S n • X = X 1 ∪ X 2 ∪ ... ∪ X n • L = L 1 ∪ L 2 ∪ ... ∪ L n • T ⊆ S × L × G × M × S,

B. Generic models of assignment request and of requests acceptance

Figures 4 and5 present respectively the generic model of an assignment request sent by a function and of the acceptance of requests by a controller; these models are denoted δ and α. The following conventions are used in these models:

• the initial locations are indicated by a source arc;

• the marked locations are indicated by two concentric circles; • the location names are in bold;

• the label names are in italics and followed by an ! (resp.

?) for emission (resp. reception) labels; • the variables updates are underlined. Moreover, the guards which are always true and the internal labels are not shown for brevity.

1) Assignment request model: The initial location of the model is 'Function not assigned'. Only one transition, which corresponds to the emission of an assignment request can be fired from this location. Once this request has been emitted, the model waits (in the location 'Assignment Possible?') for the response from an acceptance model, which can be:

• Refusal, then the model returns to the initial location;

• Ok, then the model evolves to the location "Function assigned" which is a terminal marked location. 2) Requests acceptance model: From the initial location, which is also marked, this model can evolve to the location 'Checking constraints' only upon reception of a request from an instance of a model δ for the function ' f k = (SL k , NI k l , NI k a , NO k l , NO k a )'. From this location, three transitions may be fired:

• The first transition whose guard is termed 'Violation of one of the assignment constraints' represents the violation of one of the assignment constraints of distribution or capabilities, and the label Refusal is then emitted. The guard 'Violation of one of the assignment constraints' is then true iff at least one of the following fifth conditions is not satisfied:

∑ i∈I j NI i l + NI k l ≤ LI j max (6) ∑ i∈I j NI i a + NI k a ≤ AI j max (7) ∑ i∈I j NO i l + NO k l ≤ LO j max (8) ∑ i∈I j NO i a + NO k a ≤ AO j max ( 9
)
((CF j = 1 ∧ SL k = 1)∨ (CF j = 2 ∧ (SL k = 2 ∨ SL k = 3))∨ (CF j = 3 ∧ (SL k = 3 ∨ SL k = 4))) (10)
• The second transition whose guard is termed 'First assignment' represents the acceptance of a request whereas no other function has been previously assigned to the controller (guard 'First assignment' true). This guard is true iff conditions ( 6) to ( 9) are satisfied and:

CF j = 0 (11)
The variables ∑ NO i a , are updated. The criticality factor CF j remains unchanged. In the latter two cases, the label Ok is emitted.

From the location 'Analysis of the state of the controller', two evolutions are possible which correspond to:

• the fact that all capabilities of the controller have been reached :

∑ i∈I j NI i l = LI j max ; ∑ i∈I j NI i a = AI j max ; ∑ i∈I j NO i l = LO j max ; ∑ i∈I j
NO i a = AO j max ; the guard 'No other possible assignment' is then true and the model evolves to the marked location 'Controller saturated'; • the fact that at least one capability of the controller is not reached (guard 'other possible assignment' true), then the model evolves to the initial location 'Controller waiting'. This model is a network of communicating automata NA = δ 1 δ 2 ... δ L α 1 α 2 ... α M that includes:

• as many instances (δ 1 , δ 2 , ..., δ L ) of the model in Figure 4 as there are functions, • M instances (α 1 , α 2 , ..., α M ) of the model in Figure 5;

the choice of M will be discussed in Section IV. A synchronous evolution of two automata is possible only if these two automata emit and receive one of the following label pairs:

• Request! and Request?;

• Ok! and Ok?;

• Refusal! and Refusal?. To avoid inconsistencies such as the fact that an instance α i emits a reply to an instance δ j which is not the one having emitted the assignment request, the question-response mechanism must be designed as a critical section protected by a semaphore. The achievement of this critical section is described in figure 6 with the semaphore 'Lock'.

An instance δ j can emit a request only when Lock is equal to zero. As this Boolean variable is set by an instance α i when it receives a request and reset when it emits the response (Refusal or Ok) to this request, the questionresponse mechanism between an instance δ k and an instance α i cannot be interrupted, i.e. only these two instances may be involved in the assignment process from the emission of the request to the response.

D. Definition of the reachability property searched

All the functions are assigned when the marked location is reached in all the instances of δ . In this case, the active location of the instances of α may be the terminal location or the initial location, which are both marked. Hence, the reachability property to check can be informally stated as follows: From the initial state, is it possible to reach a state of the network of automata such that the active location is a marked location in all the automata of the network?

IV. IMPLEMENTATION WITH A FORMAL VERIFICATION TOOL A. Finding a solution

The techniques of formal verification by model checking [START_REF] Bérard | Systems and Software Verification[END_REF] aim to prove that a model satisfies or does not satisfy a formal property, which may be a reachability property. It is hence natural to consider the implementation of the method proposed by using such a technique. This requires first to formally state the property searched, given in textual way in the previous section. Using the quantifiers of the CTL temporal logic, this property, noted P, can be written: P: EF Full assignment Full assignment designating the state of the network such that the active location is a marked location for all automata. This property is verified if there exists at least one trace from the initial state of the network which reaches the state Full assignment.

The search for an assignment solution can be performed by proving that the network of automata NA satisfies the above property, which will be noted: NA |= P. This proof obviously depends on the number M of instances of α. For example, it is pointless to try to assign two functions (L = 2) to a single controller (M = 1) if these functions have inconsistent safety levels. However, we can note that if: ∀i, ∀ j, NI i l ≤ LI j max , NI i a ≤ AI j max , NO i l ≤ LO j max , NO i a ≤ AO j max , M = L surely leads to a positive proof. An examination of the trace leading to the state Full assignment generally shows in this case that some controllers are not used; only a number N < M of controllers are hosting one or more functions.

B. Lessening the number of necessary controllers

The iterative proof process of algorithm 1 has been then developed to reduce the number of controllers used in the operational architecture. The first proof is performed with M = L. If Card(I) controllers do not hold any function at the end of the assignment process, then another proof is attempted with a number of instances of α equal to M -Card(I) -1, and so on till the proof is negative.

V. CASE STUDIES A. Choice of the formal verification tool

Several model-checking-based formal verification tools, such as NuSMV, SPIN, UPPAAL, may be considered for achieving the reachability analysis on which the search for an assignment solution relies. The UPPAAL tool [START_REF] Behrmann | UPPAAL implementation secrets[END_REF] was selected because it has a very ergonomic graphical interface and can provide an execution trace even in case of positive proof. It is important to note that only these features have motivated this choice; the ability of this tool to check l ∈ {0, ..., 9}, NO i a } ∈ {0, ..., 9}. The controllers used are all the same and their characteristics are: ∀ j ∈ {1, ..., M}, LI j max = AI j max = LO j max = AO j max = 32. A first reachability analysis was conducted, providing an assignment solution in which some controllers are not hosting any function; the number of really useful controllers is N = 37. The analysis performed with M = 36 also provides a solution. The number of controllers required to achieve the operational architecture cannot however be reduced further, as the analysis performed with M = 35 controllers does not provide any solution. The assignment solution hence uses at least N = 36 controllers.

I c j CF j F j ∑ i∈I j NI i l ∑ i∈I j NI i a ∑ i∈I j NO i l ∑ i∈I j NO i a c 1 3 { f 12 , f 13 } 7 13 3 4 c 2 2 { f 3 , f 4 , f 5 , f 6 , f 8 ,
Table IV shows the durations of the different reachability analyses conducted in this case study. These values show that the approach proposed is quite feasible in the industrial context of operational control architectures design.

VI. CONCLUSIONS AND FUTURE WORKS

This paper has first shown that assignment of control functions with different safety levels on controllers can be formalized as a constraint satisfaction problem with arithmetic constraints on integers that represent capabilities constraints and logic constraints that model constraints on distribution of functions. A novel approach to solve this issue has then been proposed. This contribution is based on reachability analysis in a network of communicating automata which models the assignment process. The treatment of a non-trivial example, by using a common verification tool has shown scalability of this proposal. Ongoing works are aiming at introducing new capabilities and distribution constraints and to propose not only one assignment solution but a set of solutions. Comparison to other methods, like integer linear programming, is also planned on the basis of several case studies.

Fig. 1 .

 1 Fig. 1. Aim of the study

Fig. 2 .

 2 Fig. 2. Relation between Safety Level and Criticality Factor

  where G is the set of guards (conditions on the variables of X) and M is the set of updates on the valuations of variables• S m = S 1 m × S 2 m × ... × S n m • s 0 = s 1 0 × s 2 0 × ... × s n 0 • v 0 : X ← N isthe initial valuation of variables. An evolution of NA(s, v) t → (s , v ) is possible if: • an evolution occurs in one of the automata by firing a transition t containing a local label, the guard being satisfied; • two transitions t α k ,t β m of a pair of automata (A α , A β ) with t α k containing the label l α k ∈ L α and t β m containing the label l β m ∈ L β such that l α k = l β m are fired simultaneously, the guards of these transitions being satisfied.

Fig. 4 .

 4 Fig. 4. Generic model of assignment request (δ )

Fig. 5 .

 5 Fig. 5. Generic model (α) of requests acceptance

1 Fig. 6 .

 16 Fig. 6. Semaphore use

  T. Lemattre, B. Denis, J.-M. Faure are with LURPA, ENS Cachan, 61 av. du President Wilson, 94235 Cachan Cedex, France {lemattre,denis,faure}@lurpa.ens-cachan.fr T. Lemattre, P. Salaun are with Electricite de France, Recherche & Developpement, 6 quai Watier, 78400 Chatou, France {thibault.lemattre,patrick.salaun}@edf.fr

	J.-F.	Petin	is	with	CRAN,	UMR	7039	CNRS,Nancy
	Universite, BP 70239, 54506 Vandoeuvre les Nancy, France

jean-francois.petin@cran.uhp-nancy.fr

TABLE

  Unmeasurable: Too small to be measured by simple means randomly distributed as follows: ∀i ∈ {0, ..., L}, SL i ∈ {1, 2, 3, 4}, {NI i l ∈ {0, ..., 9}, NI i a ∈ {0, ..., 9}, NO i

		f 16 }	30	26	32	23
	c 3 3	{ f 11 , f 14 , f 15 , f 17 , f 18 , f 19 }	23	32	22	20
	c 4 1	{ f 1 , f 2 , f 7 , f 9 , f 10 , f 20 }	28	27	21	21
			TABLE III
	DURATION OF THE REACHABILITY ANALYSIS FOR THE SET OF
		FUNCTIONS OF TABLE I
	Initial number of controllers	20		5	4
		Duration	Unmeasurable Unmeasurable 6 s

Algorithm 1 Search of an assignment solution lessening the number of controllers INPUTS: Features of the L functions f i ∈ F = (SL i , NI i l , NI i a , NO i l , NO i a ), ∀i ∈ {1, ..., L} Features of a generic controller LI max , AI max , LO max , AO max OUTPUTS: Minimum number N of controllers for an operational architecture.

List of the functions assigned to each controller

properties on timed models does not constitute a selection criterion, as the communicating automata considered in this work are not timed.

In the following case studies, the UPPAAL parameters have been set so that reachability analysis be done depth first to fasten analysis.

B. First case study

This case aims to illustrate the approach. The functional architecture consists of twenty functions which are defined in Table 1, and the controllers features are as follows: ∀ j ∈ {1, ..., M}, LI j max = AI j max = LO j max = AO j max = 32 A first reachability analysis with an initial number of controllers M = 20 provides a solution in which only N = 5 controllers are hosting at least one function (15 controllers are not used). By performing a new analysis with an initial number of controllers M = 4, a more compact solution can be found, in which 4 controllers are actually used. It is not possible to further reduce the number of controllers, as an analysis with M = 3 does not provide any solution. The final assignment solution for N = 4 controllers is detailed in Table II.

The durations of the various analyses required to obtain this solution are given in Table III.

C. Second case study

To assess scalability of the proposal, a study based on 200 functions was subsequently undertaken. These 200 functions are all different from each other, and their characteristics are