Isidoros Perikos
email: perikos@ceid.upatras.gr

Epaminondas Ziakopoulos
email: ziakopoul@ceid.upatras.gr

Ioannis Hatzilygeroudis

Recognizing Emotions from Facial Expressions using Neural Network

Keywords: Facial Expression Recognition, Feature Extraction, Image Processing, Multilayer Perceptron Neural Network, Human-Computer Interaction

Recognizing the emotional state of a human from his/her facial gestures is a very challenging task with wide ranging applications in everyday life. In this paper, we present an emotion detection system developed to automatically recognize basic emotional states from human facial expressions. The system initially analyzes the facial image, locates and measures distinctive human facial deformations such as eyes, eyebrows and mouth and extracts the proper features. Then, a multilayer neural network is used for the classification of the facial expression to the proper emotional states. The system was evaluated on images of human faces from the JAFFE database and the results gathered indicate quite satisfactory performance.

Introduction

The aim of facial expression recognition is to enable machines to automatically estimate the emotional content of a human face. The facial expressions assist in various cognitive tasks and is well pointed that the expressions provide the most natural and powerful means for communicating human emotions, opinions and intentions. In an early work of Mehrabian [START_REF] Mehrabian | Communication without words[END_REF] it has been indicated that during the face to face human communication only 7% of the information of a message is communicated by the linguistic (verbal) part of the message, i.e. spoken words, 38% by paralanguage (vocal part) and the 55% is communicated by the facial expressions. So, facial gestures constitute the most important communication part in face to face communication.

Analyzing the expressions of a human face and understanding their emotional state can find numerous applications to wide-ranging domains. The interaction between human and computer systems (HCI) would become much more natural and vivid if the computer applications could recognize and adapt to the emotional state of the human. Embodied conversational agents can greatly benefit from spotting and understanding the emotional states of the participants, achieving more realistic interactions at an emotional level. In intelligent tutoring systems, emotions and learning are inex-tricably bound together, and so recognizing the learner's emotional states could significantly improve the learning procedure delivered to him/her [START_REF] Akputu | Facial Emotion Recognition for Intelligent Tutoring Environment[END_REF][START_REF] Shen | Affective e -learning: Using "emotional" data to improve learning in pervasive learning environment[END_REF]. Moreover, surveillance applications such as driver monitoring and elderly monitoring systems could benefit from a facial emotion recognition system, gaining the ability to deeper understand and adapt to the person's cognitive and emotional condition Also, facial emotion recognition could be applied to medical treatment to monitor patients and detect their status. However, the analysis of the human face characteristics and the recognition of its emotional state are considered to be very challenging and difficult tasks. The main difficulty comes from the non-uniform nature of the human face and various limitations such as lightening, shadows, facial pose and orientation conditions [START_REF] Koutlas | An automatic region based methodology for facial expression recognition[END_REF].

In order to classify facial human expression into the proper emotional categories, it is necessary to locate and extract the important facial features which contribute in identifying the expression's emotions. In this work, a facial emotion recognition system developed to determine the emotional state of human facial expressions is presented. Initially, the system analyzes the facial image, locates and measures distinctive facial deformations and characteristics such as the eyes, the eyebrows and the mouth. Each part of the face then is deeper analyzed and its features are extracted. The features are represented as information vectors. The classification of the feature vectors into the appropriate expression emotion is conducted by a multilayer neural network which is trained and used for the classification of the facial expression to the proper emotional category.

The rest of the paper is organized as follows. In section 2, basic topics on face image analysis and emotion recognition are described and also related work is presented. In Section 3, the methodology followed and the system developed is illustrated. In Section 4, the evaluation conducted and the experimental results gathered are presented. Finally, Section 5 concludes our paper and presents direction for future work.

2

Background and Related Work

Background Topics

In the field of facial emotion recognition two types of methods dominate: the holistic methods and the analytical or local-based methods [START_REF] Pantic | Automatic analysis of facial expressions: The state of the art[END_REF]. The holistic methods try to model the human facial deformations globally, which encode the entire face as a whole. On the other hand, the analytical methods observe and measure local or distinctive human facial deformations such as eyes, eyebrows, nose, mouth etc. and their geometrical relationships in order to create descriptive and expressive models [START_REF] Arca | An automatic feature-based face recognition system[END_REF]. In the feature extraction process for expression analysis there are mainly two types of approaches which are the geometric feature based methods and the appearance based methods. The geometric facial features try to represent the geometrical characteristics of a facial part deformation such as the part's locations and model its shape. The appearance based methods utilize image filters such as Gabon wavelets to the whole face or on specific parts to extract feature vectors.

The way that emotions are represented is a basic aspect of an emotion recognition system. A very popular categorical model is the Ekman emotion model [START_REF] Ekman | Basic emotions. Handbook of cognition and emotion[END_REF], which specifies six basic human emotions: anger, disgust, fear, happiness, sadness, surprise. It has been used in several studies and systems that recognize emotional text and facial expressions related to these emotional states. Another popular model is the OCC (Ortony/Clore/Collins) model [START_REF] Ortony | The Cognitive Structure of Emotions[END_REF] which specifies 22 emotion categories based on emotional reactions to situations and is mainly designed to model human emotions in general. In this paper, an analytical approach is implemented for recognizing the basic emotions as defined by Ekman. More specifically, special areas of interest of the human face are analyzed and their geometrical characteristics such as locations, length, width and shape are extracted.

Related Work

Over the last decade there are a lot of efforts and works on facial image analysis and emotion recognition. A recent and detailed overview of approaches and methodologies can be found in [START_REF] Tian | Facial expression recognition[END_REF][START_REF] Verma | A Comprehensive Survey on Human Facial Expression Detection[END_REF]. The work in [START_REF] Aung | A Facial Expression Classification using Histogram Based Method[END_REF], a facial expression classification method based on histogram sequence of feature vector is presented. It consists of four main tasks which are image pre-processing, mouth segmentation, feature extraction and classification which is based on histogram-based methods. The system is able to recognize five human expressions: happy, anger, sad, surprise and neutral based on the geometrical characteristics of the human mouth with an average recognition accuracy of 81.6%. In [START_REF] Murthy | Recognizing facial expressions using eigenspaces[END_REF], authors recognize Ekman basic emotions sad, anger, disgust, fear, happy and surprise in facial expressions by utilizing Eigen spaces and using dimensionality reduction technique. The system developed achieved a recognition accuracy of 83%. The work presented in [START_REF] Thai | A facial expression classification system integrating canny, principal component analysis and artificial neural network[END_REF] recognizes facial emotions based on a novel approach using Canny, principal component analysis technique for local facial feature extraction and artificial neural network for the classification process. The average facial expression classification accuracy of the method is reported to be 85.7%. The authors in the work presented in [START_REF] Přinosil | Combining features for recognizing emotional facial expressions in static images[END_REF], recognize four basic emotions of happiness, anger, surprise and sadness focusing in preprocessing techniques for feature extraction such as Gabor filters, linear discrimination analysis and Principal component analysis. They achieve in their experiments 93.8% average accuracy in images of the Jaffe face database with little noise and with particularly exaggerated expressions and an average accuracy of 79% in recognition on just smiling/non smiling expressions in the ORL database. In [START_REF] Shinohara | Facial expression recognition using fisher weight maps[END_REF], a work that recognizes the seven emotions on Jaffe database using Fisher weight map is presented. Authors utilize image preprocessing techniques such as illumination correction and histogram equalization and the recognition rate of their approach is reported to be 69.7%.

Emotion Recognition System

In this section, we present the emotion recognition system developed and illustrate its functionality. The aim of the system is to endow software applications with the ability to recognize users' emotions in a similar way that the human brain does. The system takes as input images of human face and classifies them regarding the emotional state according to the basic emotions determined by Ekman. The system's steps for the automatic analysis of human facial expressions are presented in Figure 1.

Image Analysis and AOIs determination

Initially, the images of the human face are preprocessed using contrast limited histogram equalization. The histogram equalization is used to enhance the contrast in order to obtain a uniform histogram and also it re-organizes the image's intensity distributions and eliminates lighting effects [START_REF] Rafael C Gonzalez | Digital Image Processing using MATLAB[END_REF]. A Sobel filter is then applied to emphasize edges and transition of the face and after its application, the image of the human face is represented as a matrix whose elements have only two possible values: zero and one. An element that has a value set to one represents an edge of a facial part in the image, such as an edge of an eye or the mouth. More specifically, the system analyzes a facial image as follows:

1. Apply histogram equalization to enhance the contrast of the image. A zone's pixel density is found by the average sum of consecutive rows of this matrix. So, in his way, pixel density of a zone shows the complexity of the face in each particular zone. The zone with the highest complexity contains the eyes and the eyebrows. The stages of the image analysis are presented in Figure 2.

AOI Analysis and Feature Extraction

The extraction of the proper facial feature is considered to be the most important step in facial expression recognition and is based on finding sets of features that convey meaningful information about the facial expression. Features extracted represent the geometrical characteristics of the facial part's deformation such as the part's height, width and model the element's shape. After the successful AOI isolation, the analysis of each AOI is performed in an effort to simplify the gathered information and extract the proper feature values. The analysis procedure implemented has seven steps:

1. Measure the average brightness of the face. 2. Set a brightness threshold.

3. Relate the brightness threshold to the average brightness. 4. Find the product of the brightness threshold and the average brightness. 5. Set a brightness filter. 6. Apply the brightness filter to the AOI. 7. Cut of the excess AOI noise using proper masks.

Application of an effective brightness filter has the effect to simplify an AOI in a way so all the data containing the emotional state of the face are left unaltered while all the irrelevant to the task data are discarded. The AOIs, after the filter application, are represented more smoothly and the information vectors can be easily extracted. To measure the average brightness, it is necessary to apply a facial mask to isolate the face area from the background image and the model's hair since these areas do not affect the brightness of the face. A series of 5 more sub masks must also be applied as a final step to reduce excess noise in the marginal areas of the AOI. The features extracted for each AOI are the following (see Figure 3 As mentioned above the recognition of the expressions' emotional content is determined based on the five AOIs. Each AOI is represented geometrically by five [START_REF] Filko | Emotion recognition system by a neural network based facial expression analysis[END_REF] values therefore the length of the information vector representing the facial expression is 25. The information vector contains all the information needed to classify a face into each of the seven basic facial emotional states.

Neural Network Classification

The classification of the facial expression to the proper emotional category is made based on a Multi-Layer Perceptron Neural Network (MLPNN) which enables higher flexibility in training and also great adaptation to the problem of emotional classification [START_REF] Filko | Emotion recognition system by a neural network based facial expression analysis[END_REF]. The MLPNNs are feed-forward neural networks and can be used for the classification of multi-class, nonlinear problems. In our methodology, the MLPNN used for the classification of the facial expressions has three hidden layers, containing 13, 9 and 5 neurons respectively. Since there is no standard method to select the number of hidden layers and neurons due to the nature of the Neural Networks, the selection is often, as in this case, the architecture with the best performance. The input layer has 25 sensory neurons to match the length of the information vectors. The output layer has 3 neurons, that is, to classify the seven different classes. The output neurons combined produce a binary 3-digit sequence and each sequence is mapped to a class. The MLPNN network is trained using the back propagation supervised learning technique which provides a systematic way to update the synaptic weights of multi-layer perceptron networks.

Experimental Study

Data Collection

The methodology and the system developed were evaluated on facial images from the Japanese Female Facial Expression Database (JAFFE) [START_REF] Lyons | Coding facial expressions with Gabor wavelets[END_REF]. Jaffe database contains 213 images of seven facial expressions angry, disgust, fear, happy, sadness, surprise and the neutral expression, posed by 10 different Japanese female models of young age. Each image has resolution of 256 x 256 pixels. The seven facial expressions (6 basic facial expressions and 1 neural expression) as posed of a JAFFE model are illustrated in Figure 4 Fig. 4. The seven facial expressions as posed by a JAFEE model.

A Face Matrix is represented as 256 x 256 pixel square matrix. The elements of the matrix represent the pixels of the Jaffe model's face. Each element of the face matrix ranges from 0 to 255. An element with a value between 0 and 255 represent a gray pixel of the image. An element with the value 0 represents a completely black pixel of the original image, while an element with the value 255 represents a completely white pixel, thus making the Face Matrix a Brightness Matrix.

System Evaluation

For the evaluation of the system's performance two datasets were created from the Jaffe database, the training dataset and the test dataset. The training dataset contains 140 facial images, 20 for each one of the seven facial emotions. The test dataset contains a total of 73 images, at least 9 images for each emotional state. The training dataset is inputted into the MLPNN, and the weights of the neurons are calculated in an optimal way. After the training phase is completed, the system's performance is evaluated on the test dataset. The results gathered are presented in Table 1. The results show a good performance of the system. More specifically, from the corpus of 73 tested, it correctly identified the emotional state in 56 images. So, the general accuracy of the system is 76,7 % which indicates a good performance.

A noticeable point is that the system had a very good performance in identifying happiness emotion. This is due to the fact that in general and also in the database, this is a very strong emotion and is almost always expressed with vivid facial expression deformations. In contrast, the system lacks in recognizing the anger emotion. We believe that the main reason that the anger emotion is poorly classified is that the Jaffe models express this emotion in an inconsistent way regarding its valence. Specifically, in some cases, the models express anger emotion extremely, in an almost theatrical way while other models express the same emotion more natural in a smooth way.

Conclusion and Future Work

In this paper, an automatic facial expression recognition system is presented. The aim of the system developed is to analyse and recognize the emotional content of human facial expressions. The system initially analyzes the facial image, locates and measures distinctive human facial deformations such as the eyes, the eyebrows and area of the mouth and extracts the proper features. The features extracted try το model the geometrical characteristics of each area part of the human face. Finally, for the categorization, a multilayer perceptron neural network is trained and used. The experimental study conducted indicates quite promising performance. However, there are some points that the system could be improved. Initially, evaluating the system on different facial expression databases such as the ORL and the Cohn-Kanade facial expression databases will give us a better insight of or methodology's performance. Moreover, currently the face analysis and the determination of the AOIs work on still frontal images of human face and so, a challenging extension will be to detect and analyse facial expressions from different poses. Furthermore, the system's classification approach is based on a multilayer perceptron neural network. Extending the classification method by using a neuro-fuzzy approach could improve the system's accuracy in recognising the emotional state. Exploring this direction is a key aspect of our future work.

Fig. 1 .

 1 Fig. 1. The work flow chart of the system

2 . 5 .

 25 Apply a Sobel filter to emphasize edges and transition of the face. 3. Cut the face into eight horizontal zones. 4. Measure each zone's pixel density. Select the zone with the highest pixel density. This zone contains the eyes and the eyebrows. 6. Locate the eyes and eyebrows. 7. Locate the mouth in the center of the zone.

Fig. 2 .

 2 Fig. 2. The analysis stages of the facial image.



  H1: The height of the far left part of the eyebrow.  H2: The height of the part found on the 1/3 of the distance between the far left part and far right part of the eyebrow.  H3: The height of the part found on the 2/3 of the distance between the far left and far right part of the eyebrow.  H4: The height of the far left part of the eyebrow.  L1: The length of the eyebrow. Right eyebrow  H5: The height of the far left last part of the eyebrow.  H6: The height of the part found on the 1/3 of the distance between the far left and far right part of the eyebrow.  H7: The height of the part found on the 2/3 of the distance between the far left and far right part of the eyebrow.  H8: The height of the far left part of the eyebrow.  L2: The length of the eyebrow. Left eye  H9: The height of the far left part of the eye.  H10: The height of the part found on the 1/2 of the distance between the far left and far right part of the eye.  H11: The height of the far right part of the eye.  W1: The width of the eye.  L3: The length of the eye. Right eye  H12: The height of the far right part of the eye.  H13: The height of the part found on the 1/2 of the distance between the far left and far right part of the eye.  H14: The height of the far left part of the eye.  W2: The width of the eye.  L4: The length of the eye. Mouth  H15: The height of the far left part of the mouth.  H16: The height of the part found on the 1/2 of the distance between the far left and far right part of the mouth.  H17: The height of the far left part of the mouth.  W3: The width of the mouth.  L5: The length of the mouth.

Fig. 3 .

 3 Fig. 3. Features extracted from each AOI.

Table 1 .

 1 Performance results of the classification.

	Average accuracy	76,7 %
	Precision	78,9%
	F-measure	77,8%

Table 2 .

 2 The confusion matrix.

		Joy	Sadness	Surprise	Fear	Disgust	Anger	Neutral
	Joy	12	0	0	0	1	0	0
	Sadness	0	6	0	2	1	1	0
	Surprise	0	0	8	0	0	0	1
	Fear	0	0	0	9	0	0	2
	Disgust	0	1	0	0	8	0	0
	Anger	0	1	0	0	3	6	1
	Neutral	0	0	0	1	2	0	7


Ladislav Lenc
email: llenc@kiv.zcu.cz

Pavel Král

Automatically Detected Feature Positions for LBP Based Face Recognition

Keywords: Automatic Face Recognition, Czech News Agency, Gabor Filter, Local Binary Patterns

This paper presents a novel approach for automatic face recognition based on the Local Binary Patterns (LBP). One drawback of the current LBP based methods is that the feature positions are fixed and thus do not reflect the properties of the particular images. We propose to solve this issue by a method that automatically detects feature positions in the image. These key-points are determined using the Gabor wavelet transform and k-means clustering algorithm. The proposed method is evaluated on two corpora: AT&T Database of Faces and our Czech News Agency ( ČTK) dataset containing uncontrolled face images. The recognition rate on the first dataset is 99.5% which represents 2.5% improvement compared to the original LBP method. The best recognition rate obtained on the ČTK corpus is 59.1% whereas the original LBP method reaches only 38.1%.

Introduction

Recognizing people from digitized images is already an old concept. A great progress was made during the last twenty-five years and the amount of proposed approaches is overwhelming. There are numerous applications of the face recognition such as an access control, tracking people or other systems where an authentication is necessary. There is also a great potential of face recognition in social networks and photo sharing applications.

The recognition of controlled images is considered as a well-resolved problem. However, the face recognition from the ordinary photographs is an open issue yet, because it requires very sophisticated algorithms.

Nowadays, the Local Binary Patterns (LBP) is a very popular algorithm for face representation and recognition. The strength of this algorithm lays in its high ability to capture important information in the images and in its low computational complexity. However, one weakness of the current LBP based methods is that the feature positions are fixed and thus do not respect the properties of the particular images. We would like to solve this issue by proposing an approach to detect feature positions in images automatically. The key-points candidates are determined using the Gabor Wavelet Transform (GWT). K-means clustering algorithm is used subsequently to identify the final points. Another improvement is to compare the features separately instead of concatenating them into one feature as in the case of other existing LBP based methods. To the best of our knowledge, no existing methods use the algorithms in this way. The results of this work will be used by the Czech News Agency ( ČTK1 ) to annotate people in photographs during insertion into the photo-database 2 .

The rest of the paper is organized as follows. Section 2 summarizes important face recognition methods with a particular focus on the local binary patterns. The next section describes the LBP algorithm and the proposed face recognition method. Section 4 evaluates the approach on the AT&T and ČTK corpora. In the last section, we discuss the results and we propose some future research directions.

Related Work

It is possible to divide the existing approaches into two main groups: holistic and feature based methods. The approaches from the first group represent the face image as a whole while methods belonging to the second group use for face representation a set of features. The successful holistic approaches are for example Eigenfaces [START_REF] Turk | Face recognition using eigenfaces[END_REF], Fisherfaces [START_REF] Belhumeur | Eigenfaces vs. fisherfaces: Recognition using class specific linear projection[END_REF] or Independent Component Analysis [START_REF] Bartlett | Face recognition by independent component analysis[END_REF]. These methods achieve good results on controlled data. However, their performance decreases significantly when low quality real data are used.

This issue is partly solved by the feature based approaches. The most important representatives are detailed next. As a pioneer method we can consider Elastic Bunch Graph Matching (EBGM) [START_REF] Wiskott | Face recognition by elastic bunch graph matching[END_REF]. It is based on features created using Gabor wavelet transform. It is later used with many modifications as shown for example in [START_REF] Kepenekci | Face recognition using gabor wavelet transform[END_REF]. This method extracts the feature points automatically based on the Gabor filter responses. Another type of features used for face representation is based on Scale Invariant Feature Transform (SIFT) [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The SIFT features are invariant to rotation, scale and lighting conditions. Later a Speeded-Up Robust Features (SURF) is also used for face recognition as shown for instance in [START_REF] Dreuw | Surf-face: Face recognition under viewpoint consistency constraints[END_REF]. It reaches comparable results as the SIFT, however it has significantly lower computational demands.

In the last couple of years, also Local Binary Patterns (LBP) are successfully used as features for face representation and recognition. The LBP operator was first used for texture representation as presented in [START_REF] Ojala | A comparative study of texture measures with classification based on featured distributions[END_REF]. It is computed from the neighbourhood of a pixel and uses the intensity of the central pixel as a threshold. The pixels are marked either 0 or 1 if the value is lower or greater than this threshold. The binary values are concatenated into one binary string and its decimal value is then used as a descriptor of the pixel.

The first application of LBP for face recognition is proposed by Ahonen et al. in [START_REF] Ahonen | Face recognition with local binary patterns[END_REF]. The face is divided into rectangular regions. In each region a histogram of the LBP values is computed. All histograms are then concatenated into one vector which is used for the face representation. A histogram intersection method or Chi square distance are used for vector comparison. A weighted LBP modification is also proposed in this work. It gives more importance to the regions around the eyes and the central part of the face. The reported recognition rate on the FERET dataset [START_REF] Phillips | The FERET database and evaluation procedure for face recognition algorithms[END_REF] reaches 93% for the original method and 97% for the weighted LBP method.

A modification of the original LBP approach called Dynamic Threshold Local Binary Pattern (DTLBP) is proposed in [START_REF] Li | Face recognition method based on dynamic threshold local binary pattern[END_REF]. It takes into consideration the mean value of the neighbouring pixels and also the maximum contrast between the neighbouring points. It is stated there that this variation is less sensitive to the noise than the original LBP method.

Another extension of the original method is Local Ternary Patterns (LTP) proposed in [START_REF] Tan | Enhanced local texture feature sets for face recognition under difficult lighting conditions[END_REF]. It uses three states to capture the differences between the center pixel and the neighbouring ones. Similarly to the DTLBP the LTP is less sensitive to the noise.

The so called Local Derivative Patterns (LDP) are proposed in [START_REF] Zhang | Local derivative pattern versus local binary pattern: face recognition with high-order local pattern descriptor. Image Processing[END_REF]. The difference from the original LBP is that it uses features of higher order. It thus can represent more information than the original LBP.

An important idea which is proposed already by Ojala in [START_REF] Ojala | A comparative study of texture measures with classification based on featured distributions[END_REF] are so called uniform Local Binary Patterns. The pattern is called uniform if it contains at most two transitions from 0 to 1 or from 1 to 0. It was proved that approximately 90% of the patterns in facial images are uniform. The histogram can then be shortened from 256 intervals (bins) to 59, where the 59th bin is reserved for the non-uniform patterns.

An interesting method which uses uniform patterns is proposed in [START_REF] Yang | A lbp-based face recognition method with hamming distance constraint[END_REF]. The authors state that the histogram bin containing non-uniform patterns dominates among other bins and gives thus too much importance to this bin. Therefore they propose to assign such patterns to the closest uniform pattern. Hamming distance is used for the face comparison. Some methods also combine other preprocessing tools with the LBP. In [START_REF] Tan | Fusing gabor and lbp feature sets for kernel-based face recognition[END_REF] Gabor features and LBP are combined. The Gabor features as well as the LBP features are extracted and transformed using PCA. The features are then combined and used as face representation.

Another method called Local Gabor Binary Pattern Histogram (LGBPH) [START_REF] Xie | Single sample face recognition based on dct and local gabor binary pattern histogram[END_REF] also combines the Gabor wavelet transform and LBP. It first filter the image with a set of Gabor filters and obtains a set of magnitude images. Then the LBP operator is applied to each of the magnitude images.

Note that the common property of all above described LBP methods is that the images are divided into rectangular regions and histograms are computed in each region. All histograms from one image are concatenated and create the face representation.

Method Description

The proposed method is motivated by the assumption that the most representative features must be created in the "important" face points. This set of points where the features are created is calculated dynamically for each image by the Gabor wavelets. Therefore, the feature positions differ for each face image. We also propose to compare the features separately. In order to facilitate the reading of the paper, we shortly introduce next the Gabor wavelets and the LBP algorithm.

Gabor Wavelets

Gabor filter is a sinusoid modulated with a Gaussian. A basic form of a two dimensional Gabor filter is shown in Equation 1.

g(x, y; λ, θ, ψ, σ, γ) = exp (- x + γ 2 ý2 2σ 2 ) cos (2π x λ + ψ) (1)
where x = x cos θ + y sin θ, ý = -x sin θ + y cos θ, λ is the wavelength of the cosine factor, θ represents the orientation of the filter and ψ is a phase offset, σ and γ are parameters of the Gaussian envelope, σ is the standard deviation of the Gaussian and γ defines the ellipticity (aspect ratio) of the function.

The Gabor wavelets are often used in image analysis because of their great ability to capture important information in images.

Local Binary Patterns

The original LBP operator uses the 3×3 neighbourhood of the central pixel. The algorithm assigns either 0 or 1 value to the 8 neighbouring pixels by Equation 2.

N = 0 if g N < g C 1 if g N ≥ g C ( 2
)
where N is the binary value assigned to the neighbouring pixel, g N denotes the gray-level value of the neighbouring pixel and g C is the gray-level value of the central pixel. The resulting values are then concatenated into an 8 bit binary number. Its decimal representation is used for further computation. This approach is illustrated in Figure 1.

The original LBP operator was further extended to use circular neighbourhoods of various sizes and also with different numbers of points. A bilinear interpolation is used to compute the values in the points that are not placed in the pixel centres. The LBP is then denoted as LBP P,R where P is the number of points and R is the radius of the neighbourhood.

Figure 2 depicts the original image and the LBP image after applying the original LBP , LBP 8,1 and LBP 8,2 operators.

Key-point Position Determination

The determination of the feature positions is probably the most important part of the whole algorithm, particularly in the case of real world photographs where the faces are extracted automatically. We decide to adopt and extend the idea proposed by Kepenekci in [START_REF] Kepenekci | Face recognition using gabor wavelet transform[END_REF]. In that work the fiducial points (positions where the features are created) are extracted automatically by the Gabor wavelets. A set of Gabor filters of different orientations and wavelengths is applied to the original image and then the fiducial points are determined from the filter responses.

The filtered images are scanned using a square sliding window W of the size w × w. The window centre (x 0 , y 0 ) is considered to be a fiducial point iff:

R j (x 0 , y 0 ) = max (x,y)∈W R j (x, y) (3)
R j (x 0 , y 0 ) > 1 wi * hi wi x=1 hi y=1 R j (x, y) (4)
where j = 1, ..., N (N is the number of Gabor filters) and wi and hi are image width and height respectively.

K-Means Clustering

The number of points determined in the previous section is usually too high (hundreds) and the points are often concentrated near important facial parts. Moreover, a high number of the points increases significantly the computation complexity. Therefore, we propose to use clustering to identify only the most important points. This idea is supported by the fact that usual LBP based methods use less than 100 points and achieve very good results. We chose the K-means algorithm to cluster the key-points.

Figure 3 shows points detected with different window sizes [START_REF] Wiskott | Face recognition by elastic bunch graph matching[END_REF]25,35) and clustered points for the same window sizes and point counts (100, 75, 50).

Feature Construction

After determining the fiducial points, the features are constructed in these points. Each feature is described by its coordinates and the LBP histogram. The histogram is computed from a square window around the feature point. The resulting histogram is then normalized and can then be interpreted as a vector of the length 256.

In our application, we usually have several training images for each person. It is thus beneficial to use all available images to create the face model. We propose a face specific schema for model creation. The fiducial points determination algorithm and clustering are applied to each training image separately. Then, all obtained features are put together to create the face model of a given person.

Face Comparison

The comparison of two faces is based on the image features extracted according to the above described procedure. Each face is thus represented by a set of features that contain also feature point coordinates. Note that the number of the features in a face model may vary because the model is created from multiple images.

Contrary to the most of LBP based approaches we do not concatenate the feature histograms but compare the features separately. The Chi square statistic is used for computation of the distance of the features f and r:

χ 2 (f, r) = i (f i -r i ) 2 f i + r i (5)
The distance of two faces is defined as:

sim(F, R) = fi min rj ∈N (fi) (χ 2 (f i , r j )) (6)
where N (f i ) is the neighbourhood of the feature f i defined by the distanceT hreshold that specifies the maximum distance within that the features are compared. It means that for each feature of the face F we find the closest feature within the neighbourhood N (f i ) from the face R. The distance of the two faces is computed as a sum of these minimum distances.

The recognized face F is given by the following equation:

F = arg min R (sim(F, R)) (7)
4 Experimental Setup

Corpora

AT&T Database of Faces This database was formerly known as the ORL database. It was created at the AT&T Laboratories3 . The pictures were captured between years 1992 and 1994 and contain the faces of 40 people. 10 pictures for each person are available. Each image contains one face with a black homogeneous background. They may vary due to three following factors: 1) time of acquisition; 2) head size and pose; 3) lighting conditions. The size of pictures is 92 × 112 pixels. A more detailed description of this database can be found in [START_REF] Jain | Handbook of face recognition[END_REF].

Czech News Agency ( ČTK) Database This database is created from realworld photographs owned by the Czech News Agency. The dataset contains the images of 638 people. The database was created automatically from common photographs. The images have significant variations in pose, lighting conditions and also ageing of the objects. The experiments described in this paper will be realized on the cleaned version of this corpus (see [START_REF] Lenc | Face recognition under real-world conditions[END_REF]), which contains up to 10 images for each of the 638 individuals. The testing part contains one image for each person whereas the rest of images are used for training. Note that only the testing part was checked manually.

Experiments on the AT&T Database of Faces

The first series of the experiments was carried out on the AT&T Database of Faces. Its purpose was to show the performance of our method on a controlled database where the face recognition is simple. Ten-fold cross-validation was used for evaluation.

Table 1 shows the recognition rates of the original LBP approach proposed by Ahonen [START_REF] Ahonen | Face recognition with local binary patterns[END_REF] in comparison with our methods. We evaluated our method with three different types of the LBP operator: Original LBP operator, LBP 8,1 and LBP 8,2 . The first two rows show recognition rates when 9 out of 10 images for each person are used for training and 1 for testing. The first row depicts the results with k-means clustering (50 clusters). The second row shows recognition rates without the clustering, it means we used directly all key-points detected by the Gabor wavelet based detection algorithm (see Section 3.3). The last row shows results for only one training example. It should demonstrate the differences between the methods when only one image for training is available. In this case, the clustering is also applied for the proposed approach. The obtained recognition rates show that our method outperforms the original LBP method for all test configurations. Using the LBP 8,2 operator gives the best results. The difference is apparent especially in the case when only one training image is used. If we compare the results with and without clustering, the recognition rates are comparable. However, omitting the clustering causes significantly increased number of features and longer computation time. Therefore the clustering seems to be a good choice for feature number reduction.

Experiments on the ČTK Database

The remaining experiments were performed on the the ČTK database. As a baseline we chose (similarly as in the previous section) the LBP based face recognition algorithm proposed by Ahonen et al. [START_REF] Ahonen | Face recognition with local binary patterns[END_REF]. The recognition rate obtained by this baseline algorithm is only 38.1%.

In this experiment (see Table 2), we compare this baseline with the recognition results and computation times of our proposed approaches with and without the clustering. The original LBP operator is used.

This table shows clearly that both proposed configurations outperform significantly the original approach. Moreover, the clustering decreases significantly the computation time with almost no negative impact on the classification accuracy.

The last experiment (see Table 3) shows recognition rates of our algorithm with varying number of clusters for three LBP operator types. This table shows clearly that the LBP 8,2 operator outperforms significantly the other two ones. The highest recognition rate is obtained with 100 clusters.

Conclusions and Perspectives

We proposed and evaluated a new approach for face recognition based on the LBP features. The main contribution is using automatically detected feature positions instead of fixed positions used in usual LBP based approaches. We use Gabor wavelets for key-point detection. Then, these points are clustered by the k-means algorithm. The next contribution is proposal of a new algorithm for face comparison based on the Chi square statistic. It compares individual features within specified distance. The proposed method is evaluated on the AT&T database of faces and on the ČTK dataset. The recognition rate for the AT&T database is 99.5%. For the more challenging ČTK dataset we obtained recognition rate of 59.1%. We significantly outperformed the baseline approach in all cases.

One possible perspective is applying weighting to the automatically detected key-points. Another possible improvement may be using only uniform patterns or some modification of LBP algorithm such as LTP or LDP.

Fig. 1 .

 1 Fig. 1. An example of the feature computing by the original LBP operator

Fig. 2 .

 2 Fig. 2. An example of the original image and the LBP image after applying the original LBP , LBP8,1 and LBP8,2 operators

Fig. 3 .

 3 Fig. 3. An example of the fiducial points determined with different window sizes (15, 25, 35) (left three ones) and the clustered points for the same window sizes and point numbers (100, 75, 50) (right three ones).

Table 1 .

 1 Recognition rates of the original LBP approach in comparison with our methods

	Method	Baseline	Proposed approaches
		LBP (Ahonen) LBP (original) LBP8,1 LBP8,2
	Training images number	Recognition rate (%)
	9 (k-means)	-	98.0	97.5	99.5
	9 (no clustering)	97.0	97.8	97.8	99.8
	1	60.8	66.8	66.4	68.8

Table 2 .

 2 Recognition rates and computation times of our proposed approaches with and without the clustering, the original LBP operator is used, tested on the Intel Core i5-2300, 2.80GHz, 16GB RAM.

		Clustering No clustering
	Recognition rate (%)	56.4	55.3
	Computation time (s)	6,905	17,476

Table 3 .

 3 Recognition rates for different numbers of clusters. Three types of LBP operators are evaluated.

	LBP type	LBP (original) LBP8,1 LBP8,2
	Cluster count Recognition rate (%)
	50	45.6	45.1	56.4
	75	47.8	46.9	58.6
	100	47.5	46.1	59.1

http://www.ctk.eu

http://multimedia.ctk.cz/en/foto/

http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html

Acknowledgements

This work has been partly supported by the UWB grant SGS-2013-029 and by the project "NTIS -New Technologies for Information Society", European Centre of Excellence, CZ.1.05/1.1.00/02.0090. We also would like to thank ČTK for support and for providing the photographic data.


A García-Manso

C J García-Orellana

Rafael Tormo-Molina

R Gallardo-Caballero

M Macías-Macías

H M González-Velasco

Semi-automatic measure and identification of allergenic airborne pollen

Keywords: Independent Component Analysis (ICA), airborne pollen, pollen allergy, Neural Networks, SVM

Current lifestyle in developed countries makes the practice of outdoor activities to be almost mandatory. But, since these practices such as trekking, biking, horseback, or simply running or walking in urban parks, are made in nature (at least outdoors) not everyone can practice them in optimal physical conditions at any time of the year. We are referring to those who suffer from pollinosis or "hay fever ". This work present the first stages in the development of a semi-automatic system for counting and identifying airborne pollen, using artificial intelligence techniques for recognizing four of the most representative allergenic pollen types. The system consists of a first stage for the location of pollen grains in the slides, and a second whose goal is the identification using Independent Component Analysis (ICA) and neural nets or SVM. The overall success results achieved with our system are about 88%, averaging for all classes.

Introduction

Modern cities have good urban parks or nearby natural environments where its citizens can practice outdoor activities. But, both in these urban parks and in the nearby natural environments, there may be plants producing allergenic pollen for many people. These plants can be natives or even exotic plants used for ornamental purposes, because landscape artists tend to use them in new urban parks. This can cause that many people may not practice outdoor activities, at least not in full physical conditions at any time of year. We are referring to those who suffer from pollinosis or "hay fever ", that is, presenting allergy to certain types of airborne pollen at certain periods of the year in concrete geographical locations. In [START_REF] D'amato | Allergenic pollen and pollen allergy in Europe[END_REF] it can be found a review of the main types of allergenic pollen and the rates of pollen allergy in Europe. There, authors state that the prevalence of pollen allergy is presently estimated to be up to 40%. Count and classification of airborne pollen is a very laborious task that require a lot of time and has to be made by skilled professionals. It is necessary a high level of training to obtain accurate classification results. The study of a preparation (Fig. 1) normally require the identification of a huge number of pollen grains. These analysis can take 2 hours or more, depending on pollen concentration in the sample. Another problem to consider is that the pollen identification can involve some error, because this task is subject to personal perceptions. Normally, the experts work with 400x optical microscopes and when they locate a pollen grain, they need to change the focal plane many times. The pollen grain is a Fig. 1. The slices used to collect the pollen are subjected to a dyeing process. In that way, the pollen grains appear colored over the rest of the surface and others deposed particles in it. Here a frame extracted from a video sequence recorded with a digital camera through the microscope is shown. One can see in the picture the effect of staining the pollen grains. Since, four grains appear fully differentiated from other particles deposited on the adhesive.

tri-dimensional particle which have an aerodynamic size of 15 -40 µm. Therefore, its appearance in the microscope image changes dramatically depending on the chosen focal plane. Furthermore, the pollen grains can present some degree of translucence, depending on the type of treatment they have undergone. And, in this case, it is possible to see its apparent inner structure. In Fig. 1 (image extracted from a video sequence) there are four pollen grains of different sizes and, therefore, differently focused. It can be appreciated that the one located at the upper left corner is fully unfocused, whereas the other three can be seen clearly. In subsequent sequences of the video, this pollen grain will appear well focused and completely defined while the other three will be unfocused. This makes pollen identification a very complicated and challenging task, where it is necessary to consider a number of features such as the grain shape, the polarity, the number of openings and their arrangement and shape, texture features,..., and finally, this is translated to a number of perceptions that each expert can have [START_REF] S-Otero | Computer-aided identification of allergenic species of Urticaceae pollen[END_REF]. In recent decades many works have been proposed aimed at locating and iden-tifying pollen using computer vision techniques. In [START_REF] Gottardini | Use of Fourier transform infrared (FT-IR) spectroscopy as a tool for pollen identification[END_REF], the authors assess the potential of IR spectroscopy of the Fourier transform as an alternative method for fast and realizable identification of some of the pollen grains types that cause a higher rate of allergy. In [START_REF] Holt | Progress towards an automated trainable pollen location and classifier system for use in the palynology laboratory[END_REF], a prototype of a full self-station for counting and identifying of pollen on standard glass slides is presented. In [START_REF] Rodríguez-Damin | Automatic detection and classification of grains of pollen based on shape and texture[END_REF] a system for automatic detection and classification of pollen on standard slides is also proposed. And, as in the previous case, it also uses parameters and texture analysis to obtain the feature vectors. As can be seen, several approaches have already been proposed to get an automatic or semi-automatic counting station and classification of airborne pollen. It is relatively easy to locate the pollen grains on the slide once the sample has been prepared, that is, it has been subjected to a dyeing process so that the pollen grains are colored (Fig. 1). Currently, we are developing a self-station where a video camera linked to a microscope is controlled by a computer to get the sample images. The microscope digital camera set can be moved in the direction of Z axis to fit the focus, while the sample to be analyzed is placed on a standard microscope slide and it can be moved in the XY plane, so that the system can move along the entire surface of the slide capturing conventional light microscope video images. Then, each one of the captured videos is analyzed to select the frames with better definition, which will provide the main information. The selected frames are subjected to a process of feature extraction using Independent Component Analysis (ICA), resulting in a feature vector that it will be the input to a classifier. ICA has been widely used in the last decade as a feature extraction technique for its ability to get a base of functions adapted to every problem [START_REF] Hyvärinen | Natural Image Statistics. A Probablisctic Approach to Early Computational Vision[END_REF], especially for natural images [START_REF] Hyvärinen | Natural Image Statistics. A Probablisctic Approach to Early Computational Vision[END_REF][START_REF] Anjali | A review on natural image denoising using independent component analysis (ICA) technique[END_REF]. Different approaches for the analysis of frames are given in [START_REF] Holt | Progress towards an automated trainable pollen location and classifier system for use in the palynology laboratory[END_REF] and [START_REF] Rodríguez-Damin | Automatic detection and classification of grains of pollen based on shape and texture[END_REF], where dark field images (photograph of the silhouettes) are captured and then analyzed together with shape and texture features.

Dataset

Our aim is to develop a self-station for counting and identifying airborne potentially allergenic pollen. For this reason, we have opted for capturing prototypes from pollen images taken under the same conditions in which palynologists, responsible for this task, carry it out, and not to take the prototypes from a standard database as the European Pollen Database [START_REF] Fyfe | The European Pollen Database: past efforts and current activities[END_REF]. The samples were collected by an aerobiological sensor (7 days recording volumetric spore trap), Hirst type, Burkard 7-day. Once they were treated, we used those samples to record the videos. And from these videos, the pollen prototype images used in this work (Table 1) were captured by means of an algorithmic method. As will be explained in detail in the next section, the algorithm, looks for the frame with higher contrast (larger number of edges), for each pollen grain present in the sample. That will be equivalent to having the better definition, showing a greater amount of characteristic details of each particular pollen grain.

It can be seen in Table 1 how there are different classes that seem very similar. This could be because, in those cases, the pollen grains came from the same fam- ily: Lolium rigidum, Dactylis glomerata, Phalarais minor belong to Gramineae family. However, this is not true for Avena sativa and Avena sterilis which also belong to the Gramineae family. Besides, Calocedrus decurrens and Cypress belong to Cupressaceae family and in the images appear quite different. For this reason, it is very difficult to discriminate among pollen of the same family, even for skilled persons. Therefore, in some experiments the pollen belonging to the same family is treated as the same class.

Methods

Two processes have to be differentiated: first the process followed to segment the pollen grain images in the video sequences, and second the process followed to classify these images.

Segmentation

Videos from standard glass microscope slides containing the grains of pollen were recorded. These videos were recorded by moving the microscope (that is, changing the focal plane) in the direction perpendicular to the slide (Axis Z) for about 100 µm, depending on the pollen sizes and the slides conditions. Furthermore, these conditions determined the speed at which the microscope was moved, because, at this stage of the project development, the movement was carried out by hand. In this way, each video has about 120 to 180 frames. Afterwards, these videos were analyzed to segment the pollen grains contained in them, with the ultimate goal of finding the best image for each pollen grain that appears in each video. Due to the change in the focal plane, it is possible that, when a video has more than one pollen grain, the best frame for segmenting each grain does not match, as can be seen in Fig. 1.

The process is shown in Fig. 2. First, the algorithm calculates the co-occurrence matrix for each frame in each video. The contrast of each frame can be measured from this co-occurrence matrix and, thus, it is possible to select the frame with higher contrast. This frame is used to segment the possible grains of pollen contained in the image. And after that, once the position of each grain of pollen is known, the algorithm analyzes again the video, but now looking each time in the position where the grains of pollen are.

To start the process of segmentation of pollen grains, the frame (color image) with higher contrast is converted to grayscale. And, the pollen grains are segmented by using the histogram and taking into account a series of parameters such as shape factor (pollen grains have a more or less rounded shape), size for each pollen class and others based on the gray value features in each region as deviation and entropy (pollen grains have a semi-translucent inner structure (cytoplasm) and it is not homogeneous in its gray levels).

To find the best frame for each pollen grain the algorithm uses two different processes. One of them consists in using the co-occurrence matrix, equal than to look for the frame with higher contrast, but now, focusing at the regions where the pollen grains are. And the other one consists in using the Fourier transform to find the frame with higher contrast focusing also at the same regions that the previous one. In that way, the algorithm obtains two different sets of images for grains pollen prototypes. Obviously, artifacts (unwanted particles as dust and detritus) are taken as well in this process. These artifacts will be used as image prototypes for background and unwanted particles.

Classification Algorithms

For training our system, a classical scheme to train classifiers was followed, which consists in to use three independent sets of patterns: one for training, one for avoid the overtraining and another for testing [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. For generating each of these sets was applied ICA to the pollen images prototypes. We have used Neural Networks and Support Vector Machine (SVM) [START_REF] Vapnik | The Nature of Statistical Learning Theory[END_REF] classifiers.

Independent Component Analysis, (ICA). ICA is a statistical generative model whose objective is to explain the original data (X) using statistically independent random vectors (S). X can be modeled as X ≈ AS, where S is the matrix of latent independent components and A is the mixing matrix. This technique can be used for feature extraction since the components of X can be regarded as characteristics representing the objects (patterns) [START_REF] Hyvärinen | Natural Image Statistics. A Probablisctic Approach to Early Computational Vision[END_REF]. FastICA algorithm [START_REF] Ripley | FastICA Algorithms to perform ICA and Projection Pursuit[END_REF] was used to build ICA base functions of the pollen image space.

Once a suitable ICA model has been created, it can be expressed, as also with other transformations (wavelets or Gabor filters [START_REF] Gonzalez | Digital image processing[END_REF]), each sample of an image (I) located in (x, y), that is, the pixel gray-scale values (point luminances) in an image, as a linear superposition of some base functions A j (x, y) (rows of the mixing matrix A) called features,

I(x, y) = q j=1 A j (x, y)s j (1)
where the s j are image-dependent coefficients. While the features A j are the same for all patches, all prototypes used to generate the ICA base functions. That is, by estimating an image basis using an ICA algorithm, it can be obtained a basis adapted to the data that can model the image space. The optimal ICA model order is estimated based on the performance of a classifier. Where, the input vectors to this classifier are generated in the following way: first, two different input window sizes, 32 × 32 and 64 × 64, are considered; hence each sample used to build the ICA model was resized accord to the size of the model. The resizing was done using the bilinear interpolation algorithm provided by the OpenCV library [START_REF] Bradski | Learning OpenCV: Computer Vision with the OpenCV Library[END_REF]. For each input size were built 11 ICA models providing a given number of features in the range of 10 to 60.

Neural Networks, (NN). The neural classifier was built with a feed-forward multilayer perceptron which has a single hidden layer. The neural network weights were adjusted with a variant of the classical Back-Propagation (BP) algorithm named Resilient Back-Propagation (Rprop) [START_REF] Riedmiller | A direct adaptive method for faster backpropagation learning. The RPROP algorithm[END_REF]. Rprop is a local adaptive learning scheme performing supervised batch-learning in a multilayer perceptron with faster convergence than the standard BP algorithm.

In this work, the Stuttgart Neural Network Simulator environment SDK [START_REF] Zell | SNNS (Stuttgart Neural Network Simulator)[END_REF] was used to generate and train the neural network classifiers. To avoid local minimum during the training process, each setting was repeated four times, changing the initial weights in the net at random. Furthermore, the number of neurons in the hidden layer was allowed to vary between 50 and 650 in steps of 50 selecting the network that provides the highest success rate over the test subset.

Support Vector Machines, (SVM). LibSVM [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF] library was used with the radial basis function kernel showed in eq. 2. To find the optimal configuration of the classifier, the best values to use for parameters γ and C were studied, varying them between 0.125 and 4 in a nested loop which doubles the value of the corresponding parameter in each round.

K(x i , x j ) = exp(-γ x i -x j 2 , γ > 0) (2)
4 Results

Due to the nature of the dealt problem was decided to do two experiments. In the first (Experiment 1) all classes shown in Table 1 A double training process was done, on the one hand NN classifiers were trained and, on the other hand, SVM classifiers. After training process were obtained the results shown in Tables 2 and3, where can be seen the results obtained over the test subsets. To perform the test, the same sets prototypes in a 10-fold cross validation configuration for the two types of classifiers were used. Therefore, the results are shown using box plots. The total number of prototypes was 1660 with a average distribution in the 10-fold as follow: 167.9 for trash, 134.4 for Cypress, 174.7 for Calocedrus decurrens, 175.1 for Lolium rigidum, 76.5 for Dactylis glomerata, 141.2 for Phalaris minor, 121 for Avena sativa, 105.6 for Avena sterelis, 298.1 for Quercus rotundifolia and 264.9 for Olea europeae. First of all, it has to be said that the training times for the neural nets classifiers were longer than for the SVM classifiers (in average, about 25 minutes for SVM against more than 48 hours for NN). For this reason, after to do a significant number of trainings with NN and to test that the results were worse than with SVM, it was decided not to do more trainings. In tables 2 and 3 one can see the performance obtained by the neural and SVM classifiers depending on the number of features in the inputs vectors. In that way, the results obtained, choosing the median as a standard to select the best value, are shown in Table 4. As can be seen in these tables the performance of the SVM classifiers is better than that of the neural classifiers, about 10 percentage points in all cases. This along with the training time do that, for this problem, the election of the SVM classifiers is much more convenient than NN classifiers. Another points to consider are, on the one hand, that the success results do not seem to depend on the prototypes dimension. At least for the two sizes that were considered. Which indicates that there is information enough in the prototypes of less size. And, in the other hand, the grouping of the classes in Experiment 2 does not seem to improve very much the average success results.

Conclusions

The aim of this study was to test if by mean of an algorithm we were able to count and classify the allergenic airborne pollen in a semi-automatic way. Since, we need the samples already prepared. And from the obtained results, we could say that we have developed an algorithm able to segment well the pollen in the image samples. And the classifier algorithm using SVM carries out about a 90% success. Which, taken into account nature of the problem, is a very promising result. As future work, we have to improve the algorithm to segment the pollen images doing it more adaptable to the samples conditions. And, with the station built, we have also to capture each time more image prototypes of all classes to do more robust the classifier.

Fig. 2 .

 2 Fig. 2. Outline of segmentation algorithm of pollen grains.

Table 1 .

 1 Examples of pollen of each class and of unwanted particles (trash).

	class	samples	class	samples
	Avena sativa		Avena sterilis
	Calocedrus decurrens		Olea europaea
	Cypress		Phalaris minor
	Dactylis glomerata		Lolium rigidum
	Quercus rotundifolia		trash

  are considered independently each from others. That is, in Experiment 1, ten classes are considered. While in the second (Experiment 2), Dactylis glomerata, Phalaris minor and Lolium rigidum are grouped in a same class named Gramineae; Avena sativa and Avena sterelis are also grouped in a same class named Avena, although, they also belong to the Gramineae family. And finally, Calocedrus decurrens and Cypress are grouped in a same class named cypress, although images of those classes appear somewhat different. In that way, only six classes are considered in the Experiment 2.

Table 2 .

 2 Classification results depending on components number obtained for the Experiment 1.

Table 3 .

 3 Classification results depending on components number obtained for the Experiment 2.

Table 4 .

 4 Summary of Tables2 and 3. Maximum value of the median in each case.

		SVM	NN
	Prototypes dim. Experiment 1 Experiment 2 Experiment 1 Experiment 2
	32	87.16→15 comp 86.59→20 comp 76.24→25 comp 79.50→20 comp
	64	86.59→20 comp 86.78→20 comp 77.58→30 comp 79.31→30 comp

Acknowledgments

Presented work in this paper has been funded by "Research program at the Uni. of Extremadura, 2013. Action VII: P. Int. to Research and Technological Development" and "Junta de Extremadura" through GR10018, partially by ERDF.


Junpeng Bao

Yuepeng Zhang

Wenqing Wang

Jun Zeng

De Zhang

Ruiyu Yuan

DX-IFD: An Intelligent Force Deployment System

Keywords: Intelligent Force Deployment, Genetic Algorithm, Topography Analysis

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The modern information technology and computer science have made a deep impact on military. A variety of automatic weapons and systems are changing the way of war. A huge amount of information, which is gathered from battlefields, enemies and ourselves, has to be properly treated on time, otherwise any opportunity is fleeting. In contrast with computer, mankind is good at fuzzy decision making based on knowledge rather than precise computation. It is obviously impossible for a person to manually deal with a large scale of various data in minutes. However, artificial intelligence applications can help us to quickly process big data, analyze miscellaneous situations and find appropriate candidate solutions. Hence, a commander will decide promptly on correct actions with substantial rational power rather than temerity. This paper introduces an Intelligent Force Deployment system DX-IFD, which aims to automatically identify the battlefield features and make the optimized force deployment in terms of the topography, enemy status and our mission. This system can quickly response to the change of battlefield situation, evaluate and create the optimized deployment in different configuration conditions. As a result, DX-IFD improves the force ability to quickly react and occupy the dominant positions in a battle.

Related work

Since 1980s, United States Department of Defense has been studying the application of expert system in the military. Franklin et al. [START_REF] Franklin | Expert System Technology for the Military: Selected Samples[END_REF] introduced some applications for the military expert system and pointed out the key problems existed in the representation and reasoning about the uncertain knowledge and machine learning. In 2012, Haberlin et al. [START_REF] Haberlin | Battle Management System (BMS): An Optimization for Military Decision Makers[END_REF] presented a battle management system based on event simulation and optimization for military decision support. The Turkish army [START_REF] Yıldırım | A Design of Experiments Approach to Military Deployment Planning Problem[END_REF][START_REF] Akgün | Optimization of Transportation Requirements in the Deployment of Military Units[END_REF] researched the simulation system for military deployment and military logistics transport deployment optimization. The system exploited the probability statistics and regression tree to analyze the principal influence factors. Kettani et al. [START_REF] Kettani | A Qualitative Spatial Model For Information Fusion and Situation Analysis[END_REF] in Canadian Department of National Defense proposed a spatial reasoning method to analyze battlefield situation and support military decision.

White et al. [START_REF] White | ScatterD: spatial deployment optimization with hybrid heuristic/evolutionary algorithms[END_REF] presented a hybrid heuristic/evolutionary algorithm for automatically generating spatial deployment plans that minimize power consumption. Aleti et al. [START_REF] Aleti | Component deployment optimization with Bayesian learning[END_REF] put forward Heuristic for Component Deployment Optimization (BHCDO), which constructs solutions based on a Bayesian learning mechanism to improve quality of new deployment architectures. Lian et al. [START_REF] Li | Three-dimensional deployment optimization of sensor network based on an improved Particle Swarm Optimization algorithm[END_REF] proposed a method for 3D deployment optimization of sensor network based on an improved Particle Swarm Optimization (PSO) algorithm. Guan et al. [START_REF] Guan | PSO-based LED deployment optimization for visible light communications[END_REF] also proposed a PSO algorithm to minimize the average outage area rate of the LED deployment scheme in VLC systems.

Chinese researchers studied more on air defense force deployment issues than the land force deployment. The stochastic optimization method is a very popular way.

Wang [START_REF] Wang | Study of Hybrid Force Disposition Based on Particle Swarm Optimization[END_REF] and Xiong et al. [START_REF] Xiong | Improved Particle Swarm Optimization algorithm applied to hybrid force disposition optimization[END_REF] separately introduced the PSO based algorithm for the optimized hybrid deployment of air defense troops. Kong et al. [START_REF] Kong | Study on Modeling Troops Disposition of Army Anti-Aircraft Missile Unit[END_REF] presented a grey comprehensive correlation analysis method and a double bee population evolutionary genetic algorithm for air defense force position optimization problem. Chen [START_REF] Chen | Deployment Optimization for Point Air Defense Based on Memetic Algorithm[END_REF] combined a Genetic Algorithm with a local neighborhood search strategy for the firepower unit deployment issue.

3

The DX-IFD system

System architecture

The DX-IFD system is an intelligent force deployment system based on the topography analysis. It exploits empirical military knowledge to automatically and intelligently deal with the topography information and create optimized force deployment solutions according to the military requirements.

The figure 1 shows the DX-IFD system main workflow. The system is composed of five steps. First, it collects battlefield picture photos by satellites or unmanned aerial vehicles. Second, it analyzes the features in these photos to identify objects, such as plain, hill, river, residential area etc. Third, it determines the fitness value for different types of troops in an area, such as armored troops, artillery troops, and infantry troops etc. At this step, the system employs a rule based uncertainty reasoning scheme to take both military knowledge and geographic into account. Fourth, it makes a digital grey map for each troop type to illustrate its fitness at anywhere of the battlefield, and then grey maps are combined into color maps according to a special order. Finally, it creates the optimized force deployment solutions based on the color fitness maps according to military requirements.

This paper concentrates on the last step, especially on the GA based intelligent force deployment method and the force deployment assessment scheme.

The optimization goal

The force deployment task is to assign blended troop units into most appropriate areas in the given geographic space and satisfy the given military requirements. The troop units are of various types, including headquarters, armored units, artillery units, and infantry units etc. Apparently, the force deployment task is a Constraint Satisfaction Problem in theory, which is a typical Non-deterministic Polynomial (NP) problem. We abstract the problem as follows.

1. The troop units of various types are represented by different sizes of squares that located somewhere in the battlefield map.

2. The fitness of a troop unit in an area is measured by the Relative Average Grey (RAG) value of the unit in the square.

3. The spatial location relationship among all of the deployed units should conform to a certain formation.

4. The spatial relationship between our deployment and the enemy has to satisfy some constraints.

Thus, the optimization goal of the force deployment is to locate k squares on the given color map so as to maximize the entire assessment value on the whole. Namely, it can be described in the following formulas.

C E U R t s D U S t s k i Infantry Armored rs Headquarte u T t s G U t s u u u U U F Max i k       ) , ( . . ) ( . . } , , 2 , 1 { }, , , , { ) ( . . . . ], , , , [ )}, ( { 2 1   
Where u i (i=1,. . .,k) denotes a troop unit, U denotes the whole deployment, F(U) means the entire fitness of the whole deployment, G denotes the given battlefield color map. U,R(U,E) means the spatial relationship between our deployment U and the enemy E.

T(u i ) means the troop type of the u i . S(U) means the spatial location relationship of the

Intelligent deployment algorithm

Genetic Algorithm (GA) is a popular method to effectively solve optimization problem.

It focuses on the representation and assessment of solutions to the problem, rather than precisely mathematical analysis process. The Intelligent deployment algorithm indeed exploits the GA to make the optimized force deployment solutions. It releases us from plenty of complicated uncertain deduction of deployment transformation. The key points of the Intelligent deployment algorithm are the representation and the assessment of force deployment solution.

The representation of force deployment solution

A force deployment solution is represented by a k-dimension vector, called deployment vector, in which each dimension is responsible for a specific troop unit, and the type of a unit corresponds to its position in the vector. The construction of the deployment vector is based on prescient military knowledge that is stored in a database. Naturally, it depends on specific military requirements.

In theory, a unit area consists of 2-dimensional space coordinates and the radius.

But for a given level of the troop unit, the area size is fixed, which can be obtained from the database. In order to reduce the length of the vector and improve the computational efficiency, 2-dimensional space coordinates is only used to represent a unit.

In Genetic Algorithm, a deployment vector (i. The RPC method ensures that optimized formation will be kept after crossing operation.

The assessment of force deployment solution

We present a 10-point score scheme to assess an individual and conform to generally grading habits. A force deployment solution U is assessed from three aspects: unit fitness A(U), formation fitness D(U) and relationship fitness

R(U), i.e. ) ( ) ( ) ( ) ( 2 1 0 U R w U D w U A w U F    (1)
Where the range of each fitness value is [0,1] and the weights (w 0 , w 1 , w 2 ) are adjustable parameters, such as w 0 =4.5, w 1 =2.5, w 2 =3.0.

The unit fitness evaluates how much each deployment unit suits for specific topology. Namely, is a unit deployed to a suitable topography? In practice, it is often not the best solution to put every unit on its best position. When the whole solution is the best, many parts of the solution, i.e. units, may not locate at the best position. A reasonable deployment solution not only makes a tradeoff between all units but also considers the overall formation and the relationship with enemy. It is a complicated multi-parameters optimization problem to find a reasonable deployment solution.

The formation fitness evaluates whether the overall formation of a deployment is reasonable. It refers to the space geometry relation among the deployment units. There is a basic principle, i.e. "Act according to circumstances", the optimized deployment solution must face to the specific topography. Moreover, it must consider the spatial relationship among all units, satisfy certain geometric constraints and follow the basic military principles.

The relationship fitness assesses whether a deployment solution is effective against the enemy according to enemy information. Our deployment should be revised when the enemy position changes. The most basic requirement is that our offensive firepower should be toward the enemy and do not put our back to the enemy. Additionally, we should keep a proper distance with the enemy, neither too close nor too far.

The unit fitness

The unit fitness of a deployment solution is defined as follows.

              U u u p i i i p Grey u U U A ) ( | | 255 1 | | 1 ) ( (2)
Where |U| denotes the number of units in an individual U. |u i | denotes the area of the unit u i . Grey(p) is the actual fitness of a unit type at the point p, i.e. how much the point point p is suitable for the unit u i , which is in the range of [0,255].

The Grey(p) value is read from the fitness grey map of the specific type of unit. For a given battlefield, the grey map depends on the type of deployment unit. For example, an armored unit's grey map is obviously different from an infantry unit on the same field. Because an area where is suitable for infantry, may be adverse to the armored, such as hillside. These fitness grey maps are made at the step 4 of the DX-IFD system main workflow, as shown in the figure 1.

In fact, a pixel grey value needs only 1 byte. But for a colorful RGB image, a pixel has three bytes. Therefore, three grey maps of different unit types can be compounded in a colorful RGB image. It is convenient for data management.

The formation fitness

The formation of a deployment solution should try to meet some rules that describe relatively fixed geometric relationship. The position of the headquarters is defined as the formation's origin. Thus, a formation is described by a serial of unit's polar coordinates that is relative to the headquarters.

The formation fitness of a deployment solution is measured by the deviation between the polar coordinate of the unit and the ideal polar coordinate, i.e.

                                  1 | | 2 2 2 2 2 ) ( exp 5 . 0 ) ( exp 5 . 0 1 | | 1 ) ( U i ri i i di i i er r ed d U U D   (3)
Where d i and ed i respectively denote the straight-line distance and ideal distance between the i-th unit and the headquarters. r i and er i respectively denote the angle and ideal angle between this unit direction and horizontal direction. σ di and σ ri respectively denote the standard deviation of ideal distance and ideal angle. It is defined that first dimension in a deployment vector corresponds to the headquarters.

The relationship fitness

The figure 3 illustrates relations between our deployment and the enemy. 

                                  
Where σ h , σ r and σ d are standard deviation of head unit angle, deployment center angle and deployment center distance respectively. Angles are measured in degree. μ is the sign whether the deployment direction is facing to or back to the enemy, it is defined as follows.

          otherwise d d d d d d h c h c h c , 0 , 1 , 1 ) (  (5)

Experimental results

The figure 4 (a) shows a randomly created deployment solution whose final assessment value is 2.9187. Obviously, its formation is so poor that it cannot effectively attack enemy at all. In the figure, the blue arrow marks the enemy bearing point and the

Conclusions

Intelligent force deployment is a complicated multi-parameter optimization process.

The DX-IFD system combines topography heuristic information and military principles with the Genetic Algorithm to automatically deal with the topography information and create optimized force deployment solutions according to the military requirements. The RPC method is presented to encode the deployment, which ensures the optimized formation will be kept after genetic operations. According to basic military principles, we propose a force deployment assessment scheme which evaluates a deployment solution from three aspects: unit fitness, formation fitness and relationship fitness. The test result shows that the system can automatically generate the optimized deployment solution for the given topography and enemy information. However, some system parameters need to be further refined.

Fig. 1 .

 1 Fig. 1. The DX X-IFD system m main workflow

  e. individual) is encoded into a sequence of code, i.e. a genome. A directly coding strategy takes a troop unit's absolute position as a gene code, which corresponds to the unit's Cartesian coordinates in the battlefield map. But this strategy would destroy deployment formation and is not conducive to a better formation. For example, there are two deployment solutions A and B. A is on the left of the battlefield while B is on the right, then they exchange half of the vector respectively and generate another two new solutions whose part of the units are on the left and the others on the right. Obviously, it is not a valid formation because a deployment cannot be scattered across the whole battlefield.We propose a Relative Position Code (RPC) method, which takes the relative coordinates, i.e. polar coordinates, to code a genome. A genome consists of two parts: polar coordinates of the headquarters and the other deployment units' polar coordinates, as shown in the figure2. The headquarters polar coordinates are relative to the enemy position, but the other units' polar coordinates are relative to the headquarters.

Fig. 2 .

 2 Fig. 2. A deployment vector and Relative Position Code

  The enemy bearing point (the o point) is regarded as the origin of polar coordinate. The distance between o and the deployment center (the c point), denoted as d c , should be as close as possible to an ideal distance d e . The c point is better on the way to the front of enemy. Thus, the direction angle from o to c, denoted as r c , should be opposite to the enemy direction angle r e . The head unit (the h point) is expected to point to the enemy. So the head unit angle r h should equal r c , the distance between o and h, denoted as d h , should less than d c . Considering these factors comprehensively, the relationship fitness is defined as follows.

Fig. 3 .

 3 Fig. 3. The spatial relations between the deployment and enemy

Fig. 4 .

 4 Fig. 4. (a) A worse deployment solution (F(U)=2.9187). (b) A good deployment solution recommended by the DX-IFD system algorithm (F(U)=7.7757)