Majida Albakoor

Khalid Saeed
email: k.saeed@pb.edu.pl

Mariusz Rybnik
email: mariuszrybnik@wp.pl

Mohamad Dabash

FE8R -A Universal Method for Face Expression Recognition

Keywords: face expression, feature extraction, feature encoding, slant tracking, Artificial Neural Networks

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

Introduction

Face recognition is one of the most intensively searched topics in biometrics. Its applications are among others behaviour interpretation, human-machine interaction and interfaces. Various data representations and classification methods were proposed [START_REF] Gu | Feature points extraction from face[END_REF][START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions[END_REF]. A derivation of the topic is recognition of psychological emotions with the use of face image or video [START_REF] Hedaoo | Feature Tracking and Expression Recognition of Face Using Dynamic Bayesian Network[END_REF].

The problem was addressed by different approaches using various data representations and classifiers [START_REF] Gu | Feature points extraction from face[END_REF] [START_REF] Gao | Median null(sw)-based method for face feature recognition[END_REF][START_REF] Cui | Feature extraction using fuzzy maximum margin criterion[END_REF]. The efforts in face recognition have been largely motivated by industrial interests [START_REF] Gordon | Face Recognition Based on Depth Maps and Surface Curvature[END_REF]. Many algorithms were proposed, the majority of the proposed methods, however, fail to achieve satisfactory performance level for face expressions [START_REF] Saeed | Object Classification and Recognition using Toeplitz Matrices[END_REF], especially for the recognition of face expressions [START_REF] Saeed | Object Classification and Recognition using Toeplitz Matrices[END_REF][START_REF] Saeed | Region growing based segmentation algorithm for typewritten and handwritten text recognition[END_REF].

The authors propose a new feature extraction algorithm to recognize eight facial expressions: anger, disgust, fear, happiness, natural, sadness, surprise and cry, called FE8R algorithm. The data is from MUG Facial Expression Database [START_REF] Aifanti | The MUG Facial Expression Database[END_REF] and color FERET Database [START_REF] Phillips | The FERET evaluation methodology for face recognition algorithms[END_REF], with addition of cry expression. The proposed approach relies on essential object detection then geometric feature analysis using directional encoding to feed Artificial Neural Network classifiers.

The paper is organized as follows: section 2 presents state of the art in the area, section 3 describes the proposed approach in detail, section 4 presents some experiments and result discussion, finally section 5 discusses the conclusions and future work.

State of the art

Face expression recognition is a problem closely related to segmentation (finding the face in the image) and facial feature extraction (selection of characteristic points, shapes or areas). Face expression recognition may be defined as the analysis of selected facial features to detect predefined face expression classes, like anger or smile. Therefore it could be seen as a classification problem [START_REF] Pantic | Facial Expression Recognition[END_REF]. Commonly recognized emotions are {anger, disgust, fear, happiness, sadness, surprise} as seen in [START_REF] Keltner | Facial expression of emotion[END_REF][START_REF] Chen | Facial Expression Recognition via Non-Negative Least-Squares Sparse Coding[END_REF]. In this paper the authors distinguish also two other expressions: cry and natural.

Similar approaches

Many approaches depend on feature extraction to produce a feature vector. It may consist of two types of features: geometric features (shape and location of segmented features) [START_REF] Lin | Facial Expression Recognition Based on Geometric Features and Geodesic Distance[END_REF] or appearance features (based on the texture properties of the skin in certain areas) [START_REF] Zeng | A survey of affect recognition methods: Audio, visual, and spontaneous expressions[END_REF][START_REF] Kumbhar | Facial Expression Recognition Based on Image Feature[END_REF]. Appearance features may be seen as a template matching problem, applied to the emotion recognition area [START_REF] Brunelli | Face recognition: features versus templates[END_REF].

In [START_REF] Youssif | Automatic Facial Expression Recognition System Based on Geometric and Appearance Features[END_REF] authors use feature vectors as an input to the Artificial Neural Network with Radial Basis Function neurons (RBF ) in order to recognize facial expressions. The face image is divided into three regions of interest: mouth, nose and eyes with eyebrows. After applying unsharpen filter using certain threshold, the facial characteristic points (FCPs) are detected. FCPs lengths are calculated using Euclidean distance. Two angles in the mouth area are computed to represent geometric features, similarly the two remaining regions, the nose and the eyes. 19 geometric features and 64 appearance features form the input for the RBF neural network.

Authors in [START_REF] Bashyal | Recognition of facial expressions using Gabor wavelets and Learning Vector Quantization[END_REF][START_REF] Kumbhar | Facial Expression Recognition using Gabor Wavelet[END_REF] propose an approach for coding facial expressions using Gabor wavelets. Gabor filters are applied to each image, featured by 34 fiducial points to produce Gabor filter bank response. This results in a feature vector of length 612 (34 fiducial points with 18 filter responses per point) that represents the facial expressions. PCA (Principal Component Analysis) technique [START_REF] Nabizadeh | Automatic Facial Expression Recognition Using Modified Wavelet-Based Salient Points and Gabor-Wavelet Filters[END_REF] is used to arrange the feature vector in order of descending variance and is truncated at desired length. This is to find out, if the length of feature vector is sufficient for correct recognition of facial expressions. Input vectors are classified by LVQ neural network. In the study, the length of the feature vector was set to 90 and the sub-class size varied from 35 to 77 to classify seven different expressions.

Authors in [START_REF] Guo | Learning From Examples in the Small Sample Case: Face Expression Recognition[END_REF] recognize 7 expressions: angry, disgust, fear, happy, natural, sad, and surprise. They use Gabor filters for facial feature extraction and 6 classification methods. Their major contribution is the analysis of the behaviour of various classifiers (simplified Bayes, AdaBoost, FDLP, SVM, FSLP) in the case of small number of training examples per class. The method proposed by authors (FSLP) reached 92.4% of correct emotion recognition over 213 images of 10 people in this case.

Authors in [START_REF] Gomathi | Human Facial Expression Recognition using MANFIS Model[END_REF][START_REF] Gomathi | A Neuro Fuzzy approach for Facial Expression Recognition using LBP Histograms[END_REF] use neuro-fuzzy approach to recognize the following expressions: happy, fear, sad, angry, disgust and surprise. The image is segmented into three regions, from which the uniform Local Binary Pattern (LBP ) texture features distributions are extracted and represented as a histogram descriptor. LBP is called uniform if the binary pattern contains at most two bitwise transitions from 0 to 1 or vice versa. When it is considered circular, the operator labels of each pixel in a Gray-level image are considered, with the pixel in question at the center and 3 x 3 neighborhood pixel variations formed to 8-bit binary code. The facial expressions are then recognized using Multiple Adaptive Neuro-Fuzzy Inference System (MANFIS ) [START_REF] Khandait | Comparative Analysis of ANFIS and NN Approach for Expression Recognition using Geometry Method[END_REF].

This paper algorithm recognizes the largest amount of expressions. It is based on geometric feature extraction and encoding, with ANN used as classifiers. Detailed results are given in chapter 4.

Comparison

A short comparison of the authors' approach in this paper and similar approaches is presented in table 1, with additional remarks below. Geometric&Appearance Features 300 x 300, grayscale 6 96% [START_REF] Bashyal | Recognition of facial expressions using Gabor wavelets and Learning Vector Quantization[END_REF] Gabor wavelets, LVQ grayscale 7 90% [START_REF] Guo | Learning From Examples in the Small Sample Case: Face Expression Recognition[END_REF] Gabor wavelets, various classifiers 256 x 256, grayscale 7 92.4% [START_REF] Gomathi | Human Facial Expression Recognition using MANFIS Model[END_REF] neuro-fuzzy and LBP binary 7 94.29% this paper FE8R various, unscaled 8 ∼95%

1. The approach described in [START_REF] Youssif | Automatic Facial Expression Recognition System Based on Geometric and Appearance Features[END_REF], based on geometric and appearance features, uses as input images scaled to an array of 300 by 300 pixel with 8-bit precision for grayscale values. The recognition rate reported is between 93.5% to 96%. 2. In the approach with Gabor wavelets [START_REF] Bashyal | Recognition of facial expressions using Gabor wavelets and Learning Vector Quantization[END_REF], generalization accuracy is reported to be from 87.51% to 90.22%. The recognition rate is close to uniform for all expressions including fear. The network does not acquire 100% correct classifications, even for training database. 3. In the approach [START_REF] Guo | Learning From Examples in the Small Sample Case: Face Expression Recognition[END_REF] the emphasis is put on the small number of cases in the learning database. The reported accuracy for small number of classes (10 people) is 92.4%. 4. In the approach [START_REF] Gomathi | Human Facial Expression Recognition using MANFIS Model[END_REF], using neuro-fuzzy and LBP, a classification accuracy rate of 94.29% is reported.

The work presented in this paper does not require input image scaling. The obtained rate of recognition is comparable, despite the fact that number of recognized expressions increases to 8.

The proposed approach: FE8R algorithm

The authors propose a complex approach to face expression classification, called FE8R algorithm. The proposed approach relies on the selection of so called essential objects (EO) and analysis of geometric features using either directional encoding or direct feed to Artificial Neural Network classifier. Translation and scaling issues need to be dealt with at (mostly automated) preprocessing stage.

The face image is converted into grayscale. The image is normalized if required, by adjusting the intensity using minimum and maximum of intensity values in the image. The contrast is enhanced by histogram equalization. Filtration using median filtering is used to reduce the noise and preserve the edges. The image is rotated by a suitable angle degree. Also the image edges are detected. The work area and its center are calculated depending on dividing the image into four quarters and the characteristic objects are detected using the coordinates of the minimum and maximum points of each object and the object perimeter is larger than the major-axis of the formed ellipse for the studied object. The characteristic object is reduced to get EO, by applying the gradient value between the x-axis and the major axis ranked in [-15,+35] degrees. The number of EO is reduced by at least 80%. Two methods are applied, the first method is depending on the slant, we fix the center of the object and study the slant from the starting-point. We consider the slant changing is acting so that the slant changing is examined by testing the alternate of slant sign. By slant progression analysis, one can consider the face expression as happy or sad. The second method uses feature coding, we extract the objects important points. These points are coded by BPCC algorithm [START_REF] Albakoor | BPCC approach for Arabic letters recognition[END_REF]. Filtered code is dealt with to form an array of 81 elements. Then the array is scaled to consider as the input of ANN backpropagation network.

Two classification methods are used: the first tracks points on the basis of fixed slant, where the slant is calculated depending on the object center point and the face center, whilst the second encodes the data for ANN.

Two ways are applied the first is by slant variation after fixing the object center based on its starting-point. If the slant variation is clear without alternating slant sign compared with its preceding value, then noticeably, the face is classified as happy. If we have variation with slant sign alternating, the face is sad. The second way considers extracting the characteristic points by defining the end-points, start-points, branch, and turning pixels. The object is coded depending on the detected pixels using eight digit pairs with two passes counterclockwise. Code is filtered according to eight chosen basic pairs. Calculations are made to form an array of 9x9 elements added to the percentage of distributed points in each part of the studied character. Hence the resulting matrix is formed by 85 elements. Finally, the matrix is passed to ANN for classification.

Subsequent phases of the algorithm are detailed in the following sections.

Face image preprocessing

Face image requires preprocessing to improve the image quality [START_REF] Saeed | K3M: A universal algorithm for image skeletonization and a review of thinning techniques[END_REF][START_REF] Mancas | Segmentation Using a Region Growing Thresholding[END_REF][START_REF] Tremeau | A region growing and merging algorithm to color segmentation[END_REF][START_REF] Brown | A Survey of Image Registration Techniques[END_REF]. The first step is converting the color image into grayscale image, as shown in Fig. 1a. The second step is image normalization with two phases [START_REF] Saeed | A New feature extraction method for TMNN-based Arabic character classification[END_REF]: first by adjusting the intensity regarding minimum and maximum intensity values, second by enhancing the contrast with histogram equalization, as shown in Fig. 1b,c. The third step is filtering using median filter in order to reduce noise, as presented in Fig. 1d. A median filter is considered more effective than convolution, when the goal is to simultaneously preserve the edges [START_REF] Delac | Face Recognition[END_REF]. In the fourth step, if required, the image is rotated by a suitable angle around its center (the rotation procedure in [START_REF] Tremeau | A region growing and merging algorithm to color segmentation[END_REF] is used), as shown in Fig. 1e. The fifth step is detecting the edges by Canny method [START_REF] Canny | A Computational Approach to Edge Detection[END_REF] with the threshold 0.08 and sigma 1 (determined empirically), as depicted in Fig. 1f.

Extraction of characteristic objects

The authors consider that the horizontal lines (or edges) are more influential for face expressions, so the idea is to find this type of edges. After the edges are detected, the work area and its center are determined and represented as 16 x 8 squares. Studied object is enclosed in ellipse and the characteristic objects are extracted using the minimum and maximum coordinates of each object [START_REF] Gu | Feature points extraction from face[END_REF][START_REF] Hess | Facial Feature Extraction Based on the Smallest Univalue Segment Assimilating Nucleus (SUSAN) Algorithm[END_REF] and the gradient between the x-axis and major axis [START_REF] Brown | A Survey of Image Registration Techniques[END_REF], as shown in Fig. 2. The characteristic objects boundaries are drawn in blue. Among all characteristic objects some are labeled as essential objects, depending on the slant. The authors have considered that the difference between the x-axis and major ellipse axis is between -15 and +35 degrees (determined empirically). Two methods are applied; the first is slant analysis of ConvexHullK [START_REF] Barber | The quickhull algorithm for convex hulls[END_REF] points to transform them into suitable input of ANN, the second method is encoding the important points of basic objects depending on BPCC algorithm to recognize anger, disgust, fear, happiness, natural, sadness, surprise and cry expressions.

Feature extraction algorithm

Feature extraction leads to detection and selection of essential objects. This is given as a flowchart in Fig. 3. Detailed steps of feature extraction are as follows:

1. The center point of face M(X k, Y k) is found in the image. 2. Work area is calculated and its center is detected. The area is defined as the middle of face space containing the eyes, nose and mouth. That space is a) The first one is applied on the slant, which is calculated starting from the fixed point being the object center and the second point is the face center. The images are from Mug Database [START_REF] Aifanti | The MUG Facial Expression Database[END_REF] (plus a set of images prepared by the authors for cry expression) and applied for 8 expressions (anger, cry, disgust, fear, happiness, natural, sadness, surprise). Then the characteristic points of essential objects are computed by two different ways and processed by ANN as 100 features for the first method and 81 for the second. It was applied also on FERET Database [START_REF] Phillips | The FERET evaluation methodology for face recognition algorithms[END_REF] for 4 expressions (cry, sad, laugh and smile) and the recognition accuracy was over 90% in this way. i) For each detected essential object the following steps are performed:

-The Convex Hull points [START_REF] Gordon | Face Recognition Based on Depth Maps and Surface Curvature[END_REF] are found. They are denoted by Con-Hull Poi. -The search for start and end point of object starts from the firstquarter and goes counterclockwise, after the face image is divided into four-quarters. The point is considered as start point or end point if the sum of the 8-neighboring pixels of the tested point is equal to 1. They are denoted by Start Poi and End Poi.

ii) The slant between ConHull-point and the face center is calculated as in Equation 1.

Slant 1 = (ConHull P oi Y -Center i Y ) (ConHull P oi X -Center i X) (1)
iii) The slant between ConHull-point and the object center is formed as in Equation 2.

Slant 2 = (ConHull P oi Y -Center P oi Y ) (ConHull P oi X -Center P oi X) (2)
iv) The slant average Mslant is calculated as in Equation 3:

M Slant = (Slant 2 + Slant 1 ) /2 (3)
v) The steps from ii) to iv) are repeated for all ConHull-points of the object. Fig. 4 (b,c,d,e,f) present the ConvexHull points, essential objects and face center as well as the way to perform required calculations. vi) The steps from i) to v) are repeated for each essential object. The result is a slant vector that is scaled up to 100, to be the input of ANN. b) The second way is to use feature encoding by extracting the important points (start-point and end-point of straight piece, start-point and endpoint of object) of essential objects. These points are encoded using the BPCC algorithm consideration. Fig. 4 (h-j) present these points. Essential objects are formed into an array of 81 elements. The array is then considered as the input to Backpropagation ANN. The recognition accuracy in its maximum possibly achieved value was 95%.

Selecting essential objects from characteristic objects

Less important characteristic objects detected in the image (about 80%) are eliminated, leaving only essential objects. An example for detected essential objects is depicted in Fig. 4. Fig. 5 and Fig. 6 present examples of characteristic and essential objects, characteristic object boundaries are blue and yellow whilst the essential object boundaries are green. Four images from MUG database [START_REF] Aifanti | The MUG Facial Expression Database[END_REF] are shown in Fig. 5, a sample 'cry' image produced by the first author is presented in Fig. 6.

Configuration of backpropagation Artificial Neural Networks

For the first method, the Convex Hull points are defined, the slant between points and the center of objects, then face center are found. The average of slant is calculated, scaled to be 100 features as a good input to ANN.

For the second case, FBPCC method [START_REF] Albakoor | BPCC approach for Arabic letters recognition[END_REF] is applied on the essential objects, the important points (start, end and branch points) are detected. These points are coded during two counterclockwise passes: first diagonal, then perpendicular. Eight sets of binary pairs are used to filter the resulted objects. Filtered data is formed into an array of 81 elements.

The neural network contains 81 neurons in the input layer, and {550; 350; 250} neurons in the 3 hidden layers. The number of neurons in the output layer is 8 neurons to indicate various face expressions anger, cry, disgust, fear, happiness, natural, sadness, surprise. The training parameters of the ANN are set up according to these values: the momentum coefficient is 0.25, the learning rate is 0.05 and the sum square error is 0.00000585. This ANN uses bipolar function as an activation function. The ANN weights and biases are generated randomly. The value range of the input vector is between -1 and +1.

Results and discussion

ANN is trained on 52 faces, 4 images, 8 expressions with 184273 epochs. The faces are taken from MUG Facial Expression Database [START_REF] Aifanti | The MUG Facial Expression Database[END_REF] and color FERET Database [START_REF] Phillips | The FERET evaluation methodology for face recognition algorithms[END_REF] with different face expressions. After training, the ANN is tested on a new set of faces (generalization database). We tested the ANN on 32 new samples that can be split into 8 groups. We noticed some errors of ANN recognizing of facial expressions which is improved using FBPCC method [START_REF] Albakoor | BPCC approach for Arabic letters recognition[END_REF].

By comparing the results of the two methods, we noticed there were some error rates in the possibility of distinguishing between the angry, disgusted and fear expressions, also between sad and cry expressions, between happy, natural and disgusted. The main reason for such errors comes from the fact that the work is neglecting the vertical objects and focusing on the horizontal characteristic objects. The range therefore is raised sometimes and decreased other times.

Conclusions and future work

This paper proposes a new approach for classification of eight face expressions: anger, cry, disgust, fear, happiness, natural, sadness, surprise. Most important paper contribution is the design and implementation of a feature extraction method. It is based on detection and selection of characteristic objects in the image. The preselected characteristic objects are studied in two ways: the first uses slant tracking, the second is based on feature encoding using BPCC algorithm with classification by Backpropagation Artificial Neural Networks. The correct classification rates were close to 50% and 95% respectively. The second method was proved to be fast and produced promising results. The method is unsupervised, flexible and can be adopted to recognize even more face expressions. The proposed method provides high efficiency for face expression and could be recommended for further research and studying. Future works in this area will include increasing the number of classes (various face expressions), application of other, possibly more viable, classification methods, and testing proposed approach on other databases, preferably with many subjects. Moreover, the authors are working on the ways of considering vertical oriented objects in order to increase the distinguishing rate of the similar expression features like those of sad and cry.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Face image preprocessing: (a) color image, (b) normalized image, (c) image after histogram equalization, (d) image after median filter, (e) rotated image, (f) edge detection

Fig. 3 . 6 .

 36 Fig. 3. The flowchart of the essential objects detection and selection

Fig. 4 .

 4 Fig. 4. Characteristic points of essential objects detected in the image (a): (b) Convex Hull points in blue, essential objects center in red, (c) two points of ConHulks points in cyan, (d-f) present the distance between the ConHulks and its object center (face center) shown by yellow arrows, movement goes counterclockwise. (h-j) present essential points: start-point and end-point of straight piece in green, start-point and end-point of object in red and branch point in magenta.

Fig. 5 .

 5 Fig. 5. Four images from MUG database [9]. Examples of characteristic and essential objects. Consequent columns are: a) Original color image, b) Black and white image after edge-detection, c) Image with detected Characteristic object boundaries in blue and yellow, face center is marked with the red point d) essential objects in green with centers in red.

Fig. 6 .

 6 Fig. 6. A sample 'cry' image prepared by the first author. Examples of characteristic and essential objects. Consequent columns are: a) Original color image, b) Black and white image after edge-detection, c) Image with detected Characteristic object boundaries in blue and yellow, face center is marked with the red point d) essential objects in green with centers in red. Characteristic object boundaries are blue and yellow and the essential are in green.

Table 1 .

 1 Comparison with other approaches

	Ref.	Approach	Input	Expr. Recogn. rate
	[17]

Acknowledgments This work was supported by grant number S/WI/1/2013 from Bialystok University of Technology and funded from the resources for research by Ministry of Science and Higher Education. The work was also partially supported by NeiTec.


Anna Burduk
email: anna.burduk@pwr.wroc.plkamil.musial@student.pwr.wroc.pl

Kamil Musial

Kamil Musiał

Optimization of Chosen Transport Task by Using Generic Algorithms

Keywords:

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

Introduction

The main purpose of transportation in a company is the system organization and synchronization of physical flow of materials from manufacturers or wholesalers to consumers through all phases of the process, in accordance with the principles of logistics management [START_REF] Ayough | GA and ICA approaches to job rotation scheduling problem: considering employee's boredom[END_REF][START_REF] Jachimowski | Simulated annealing algorithm for the multi-level vehicle routing problem[END_REF][START_REF] Krenczyk | Integration Production Planning and Scheduling Systems for Determination of Transitional Phases in Repetitive Production, Hybrid Artificial Intelligent Systems[END_REF][START_REF] Zegordi | A multi-population genetic algorithm for transportation scheduling[END_REF]. Expenditure on transport a large part of total costs, which make the difference between the cost of goods producing and price paid by the consumer. In addition, some of the goods should be transported as quickly as possible due to the limited period of validity. These reasons tend to pay attention to the problem of transport optimizing [START_REF] Yusoff | Solving vehicle assignment problem using evolutionary computation[END_REF]. At the same time the continuous technological and information advances guarantees the emergence of new methods that can be successfully used in solving transport problem. Transport issues are most often used to [START_REF] Jachimowski | Simulated annealing algorithm for the multi-level vehicle routing problem[END_REF][START_REF] Sahu | Solving the assignment problem using genetic algorithm and simulated annealing[END_REF]:

 optimal products transport planning, taking into account the minimization of costs, or time of execution  optimization of production factors distribution in order to maximize production value, profit or income.

Genetic algorithms belong to group of stochastic algorithms. The basic principle of their functioning is based on the imitation of biological processes, namely the processes of natural selection and heredity. Genetic algorithms are gaining more and more areas of applications in the scientific, engineering and even in business circles, as an effective tool for efficient searching [START_REF] Ayough | GA and ICA approaches to job rotation scheduling problem: considering employee's boredom[END_REF][START_REF] Guvenir | Multicriteria inventory classification using a genetic algorithm[END_REF]. The reason for this is obvious: genetic algorithms are a simple and at the same time powerful tool to search for better solutions. In addition, they are free from the essential constraints imposed by the strong assumptions about the search space, ie. continuity, existence of derivatives, modality of the objective function, etc.. A typical problem solved by genetic algorithm consists of [START_REF] Burduk | Artificial neural networks as tools for controlling production system and ensuring their stability[END_REF][START_REF] Govindan | Product recovery optimization in closed-loop supply chain to improve sustainability in manufacturing[END_REF][START_REF] Jachimowski | Simulated annealing algorithm for the multi-level vehicle routing problem[END_REF][START_REF] Nissen | Evolutionary algorithms in management science. An overview and list of references[END_REF]:

 optimization problem -finding the best solution of all allowable,  a set of allowable solutions -the set of all possible solutions to the task (not only the optimal),  the evaluation function (adjustment) -the function that determines the quality of each possible solution. It establishes an ordinal relationship on the set of feasible solutions. In other words, because this function, one can sort all the solutions from best to worst solution of the problem,  coding method -a function that represents each acceptable solution in the form of string code, which is in the form of a chromosome. Basically, more interesting should be the inverse function. This is a function that, on the basis of chromosome, creates a new feasible solution. In fact, to solve the task the only basic function is required, analogous to nature. Nature has complicated 'knowledge' on how to create an adult from an embryo. I would be enough that each of the individuals will be stored in the memory of genotype, on the basis of which he was created.

2

The mathematical model of transport -production task

In the following example optimization of transport -production tasks for the processing of milk will be considered. For network of collection points and processing plants, according to its algorithm, the cost-optimal distribution of transport tasks has been determined. It is assumed that the functions defining the costs of conversion are polynomials of the second degree. To solve the problem a program written in MATLAB based on the genetic algorithm, equalizing marginal costs is used. Enterprise processing a uniform material has m collection points and n plants processing this material. Additional information should be known:

 unit cost of transportation from any collection point to individual processing plants,  amount of material collected at each point of supply,  functions defining the cost of the material processing at each plant, depending on the size of the processing.

Features defining the costs of conversion are convex and square functions. They take into account only the variable costs, which depend on the size of production. The entire acquired material must be transported to the plant and converted there. It is assumed that plants are able to process the supplied amount of material (the possibility of processing by plants are known). This increases the production capacity of plants, but also results in an increase in the unit cost of production. Rising costs of conversion are a natural limitation of the size of production of each establishment.

It is needed to establish a plan of material supplies to individual plants and processing of raw materials in these plants, so the total costs of transport and processing were minimal. The following designations have been adopted: i -the number of the collection (supplier number), j -number of the processing plant (recipient number),

x ij -the amount of raw material transferred from the i-th supplier to the j-th recipient,

x j -the amount of raw material processed by the j-th recipient, a i -the amount of raw material, which must be send by i-th supplier, c ij -the unit cost of transport from the i-th supplier to the j-th recipient, f j (x j ) -the cost of processing x j units of raw material in the j-th plant (at j-th recipient).

Furthermore assumed that the convex cost function f i is a second degree polynomial of the form:

f j (x j ) = c j x j + e j x j 2 , c j ,e j > 0 (1)
where:

c j -describes the minimum unit cost of processing, e j -determines the growth rate of unit cost.

The first derivative of this function is determined by the marginal cost of processing:

F J '(X J ) = C J + 2 E J X J (2)
while the second derivative -the rate of increase in the marginal cost:

F J " (X J ) = 2 E J (3)
The average cost of processing the j-th plant is determined by the formula:

K J P (X J ) = C J + E J X J (4)
The problem of determining the optimal supply plan of raw material and its processing can be presented in the form of a non-linear decision task.

Variables x ij and x j are sought that:

∑ ∑ 𝑐 𝑖𝑗 𝑛 𝑗=1 𝑚 𝑖=1 x ij +∑ 𝑓 𝑗 𝑛 𝑗=1 (𝑥 𝑗 ) → 𝑚𝑖𝑛. (5)
By the conditions:

∑ 𝑥 𝑖𝑗 = 𝑎 𝑖 ; (𝑖 = 1, … , 𝑚), 𝑛 𝑗=1 (6)
∑ 𝑥 𝑖𝑗 = 𝑥 𝑗 ; (𝑗 = 1, … , 𝑛) 𝑚 𝑖=1 (7)
𝑥 𝑖𝑗 , 𝑥 𝑗 ≥ 0;

(𝑖 = 1, … , 𝑛) (8)
The objective function ( 5) minimizes the total cost of transport and processing. Condition [START_REF] Jachimowski | Simulated annealing algorithm for the multi-level vehicle routing problem[END_REF] provides that each supplier will send all owned raw material. Condition [START_REF] Krenczyk | Integration Production Planning and Scheduling Systems for Determination of Transitional Phases in Repetitive Production, Hybrid Artificial Intelligent Systems[END_REF] forces the processing in the j-th plant of all the raw material to which it is delivered. Task (5 -7) is the task of quadratic programming with a special -transport structure.

It can be solved by using an algorithm equalizing the marginal cost, which is based on genetic algorithm. Marginal cost, the cost of which the manufacturer incurs due to the increased size of production of the good by one unit. It is the increase in total costs associated with producing an additional unit of a good. If the plant increases its production by one unit, then the total cost of production will increase. The difference in the size of the costs manufacturer incur earlier and costs incurred after the increase in production is a marginal cost. It is, therefore, the cost of producing an additional unit of a good.

The concept of marginal cost can also be formulated in relation to the consumer and is then taken as the cost of acquiring an additional unit of a good. The marginal cost is an important micro-economic category. It was observed that for typical business processes marginal costs initially decrease with the increase in production until the technological minimum is reached. Further increase of production over a minimum of technology, however, increases the unit cost of further increases in production and thus rising marginal costs. This observation is important in microeconomic analysis of the behavior of the manufacturer and determining the optimal level of production. According to economic theory, marginal cost cannot be negative. This means that the increase in production may entail reducing the total cost.

Method of equalizing the marginal cost based on genetic algorithm consists of:  determination of the best possible, an acceptable solution output,  improvement of new solutions X 1 , X 2 , ..., by offset equalizing marginal costs.

A string of new obtained solutions X 1 , X 2 , ..., X r ,…., does not need to be finished. It is therefore interrupted at some point of calculations. It is important, however, that the final solution does not deviate too far away (in terms of objective function value) from the optimum solution. JCC algorithm comes down to the following steps:

1. Determine the initial solution:

a) for the i-th supplier (i = 1, ..., m) the route with minimal marginal cost is set, b) on the selected route an entire supply of i-th supplier is located, c) update the marginal costs in the column of the selected route.

Then move on to the next vendor, and repeating steps (a) -(c) until the supply is disposed for all suppliers.

2. Make sure the current solution Xr meets the criterion of optimality. If so, the final solution is optimal. If not-return to step 3. 3. Make sure the solution Xr is ε -accurate. If so, finish the calculations. If not, go to step 4. 4. Improving the solution by shifting equalizing marginal costs and return to step 2.

Having designated solution Xr and the matrix of marginal costs Kr for each supplier, lets settle the differences between the maximum realized cost and the minimal cost.

3

Solving the problem of transport and production using a genetic algorithm

The study involved the delivery of milk (about 2 000 m 3 /month). The task was formulated as follows: Six suppliers (in 6 cities): D1, D2, D3, D4, D5, D6 supplies milk to two factories: S1, S2, with restrictions: S1: can accept and process 700 or 1000 m 3 of milk, S2: can accept and process 1 500 m 3 of milk.

Data are summarized in Table 1 below and include:

unit transportation costs (in PLN per km), offered monthly deliveries Ai (m 3 ), monthly demand of factories Bj (m 3 ). The task is solved with the help of developed in MATLAB genetic algorithm equipped with a graphic interface GUI. The aim of the task is to determine the opti-mal marginal cost of "material processed" transport from any supplies, to one of two factories, taking into account its processing capacity.

Solving the transport-production problem of in the general scheme of genetic algorithm

Population.

The first step is to number all suppliers. Created chromosome has a length such as the number of suppliers. In the following genes another supplier is saved. For example, if the gene number 1 "represents" city X and gen number 2 city Y it means that the provider moves from town X to Y. In this way, genes in the chromosome are arranged exactly as the city cycle. For a sample of six cities connected with road, a sample chromosome mapping cycle may look like this:

[1 4 6 2 3 5]
The evaluation function (cost).

The function of evaluation is the total minimum cost of transport and processing.

Selection.

Simulation using the roulette wheel assigns the probability of choosing each individual directly on the basis of a single evaluation function. The sum of the probabilities assigned to each chromosome is equal to 1, which means that if the area of a circle is the sum of the values of the objective function of population individuals, then each of them is associated with a circle section. In the current example, it six fields exist.

Crossover.

One-point crossover. Individuals are combined sequentially in pairs: Among the offspring duplicates of existing individuals may appear. Duplicates do not bring anything to the database all the genes are subjected to forced mutation.

Mutation.

After giving birth to offspring, approx. 50% of generation mutates.

Solution to the problem in MATLAB

After entering all necessary data, information about the correct solution of the problem is obtained (Fig. 1). On the y-axis the accuracy of the solution (in %), and on the x-axis the number of iterations (max = 5) is given. The calculations examined several variants, the supply of milk did not change but both demand (processing capacity), and processing costs (description of function) were variable. For example, variant v1 adopted by Table 1 the following demand: for factory S1 -700 m 3 / month, and for the factory S2 -1500 m 3 / month. Also, based on studies carried out it was assumed that the processing functions have the following form: f 1 (x 1 ) = 15x 1 + 0,2 x 1 2 and f 2 (x 2 ) = 15x 2 + 0,1x 1 2

In the case of variant V2 (data according to Table 1) adopted the demand: for factory S1 -1 000 m 3 / month and for the factory S2 -1500 m 3 / month. Processing functions have the form: f 1 (x 1 ) = 10x 1 + 0,2 x 1 2 and f 2 (x 2 ) = 10x 2 + 0,1x 1 2

Summary of results

Collective summary of results is shown in Table 2. There is placed sample of simulation results conducted for several variants, which are varied in parameters of processing function, transportation costs, the possibility of processing by individual factory. Statement contains the best results.

Fig. 1 .

 1 Fig. 1. The dialog box of the program -the relationship of the accuracy and the number of iterations If the solution is optimal-accurate results in a table showing the following information:  amount of processing at the individual plants,  the total cost of the transportation and processing of milk,  the cost of transport,  the cost of processing,  average costs,

Fig. 2 .

 2 Fig. 2. Terms of the calculation in the program for variant v1

Table 1 .

 1 Unit transportation costs, supply and demand

						Factories
	Suppliers	Supply A j [m 3 ]	S1	Variant v1	S2	S1	Variant v2	S2
	D1	400	5			60	5		60
	D2	70	40			60	40		60
	D3	100	70			15	70		15
	D4	300	70			5	70		5
	D5	420	100		50	100	50
	D6	200	100		80	80		100
	Demand B j [m 3 ]	700	1500	1000	1500

The chart shows that the total cost of the task for variant v1 is 267 420 PLN and it is more than 40 000 PLN higher than the costs of the variant v2. This difference is primarily due to the fact that for small factories processing costs are higher than for larger ones.

Summary

The study shows that the effective use of resources spent on process management is only possible through system logistics solutions that will be effective in terms of technical information and simultaneously optimized in terms of financial outlay. The proposed work approach using solving the problem of production and transport costs with convex function should facilitate decision-making processes of transport and production management. Genetic algorithms fully confirmed its effectiveness for the problem, minimizing total costs of transport and processing.

Unlikely the classic optimizing methods that give determined outcome, the Genetic Algorithms do not guarantee finding the best solution. An efficient GA using is complex because of mutation-random component. Executing the same algorithm for the same task a few times may obtain various results.

The relationship of the accuracy and the number of iterations (Figure 1) has been obtained and showed to find out how many iterations should be performed to achieve adequate (not random) results. Task become more complex when computing time is also significant and it is necessary to guarantee find the optimum between result accuracy and computing time or when it is required to clearly determinate if obtained solution is the best one.


Josef Hrabal

David Seidl
email: david.seidl@vsb.czmichal.krumnikl

Michal Krumnikl

Pavel Moravec

Petr Olivka
email: petr.olivka@vsb.cz

The Radio Direction Finding with Advantage of the Software Defined Radio

Keywords: Radio direction finding, Doppler antenna, Software-defined radio, SDR

The radio-frequency engineering recently has gone through extensive development. Software-Defined Radio (SDR) plays an important role in this development, bringing new possibilities to radio-frequency engineering and enables us to look at existing radio technologies in a new, innovative way. One such technology is a Doppler antenna, which allows us to find the direction from which the radio signal of given frequency is being transmitted. The SDR allows us to design and construct a highlysimplified system based on the Doppler antenna array. This paper deals with the design and implementation of such system used for the localization using the Doppler effect and the tests of the designed Doppler antenna system.

Introduction

Radio Direction Finding (RDF) is the measurement of the direction from which a received signal was transmitted. This has many applications in different sectors. The RDF is used for example in the navigation of ships and aircrafts, for tracking wildlife, and to locate not only emergency transmitters but also illegal or interfering ones.

Nowadays, most of the radio frequency bands are occupied. Fast classification and location of the source of an illegal or interfering transmitters could be very helpful, especially when transmitters or networks are being built and maintained. The classification and locating can be simplified thanks to software defined radio (SDR).

Radio Direction Finding

The RDF is nearly as old as radio itself. Earliest experiments in the radio direction finding were carried out by Heinrich Hertz in 1888. Since then many types of radio direction finding techniques were discovered. The mostl frequently used ones are the Watson-Watt and the Doppler technique.

Watson-Watt radio direction finding system

The first one from the mentioned techniques is older and was introduced by Robert Watson-Watt before the World War II. It utilises an antenna array consisting of four equidistant vertical elements (known as Adcock antenna [START_REF] Adcock | Improvement in means for determining the direction of a distant source of electromagnetic radiation[END_REF]) and two separated precisely calibrated receivers. The angle of arrival (AoA) is then determined from the signals level difference. The presence of two receivers is the main disadvantage of this technique [START_REF] Rdf Products | Basics of the Watson-Watt Radio Direction Finding Technique[END_REF]. The second technique uses the Doppler effect. This effect was described by Austrian physicist Christian Doppler in 1842 in Prague. Most people associate the Doppler effect with acoustic waves, but the theory is also applicable to radio waves as well. This well known effect describes a difference between the observed and emitted frequency of a wave for an observer which is moving relatively to the source of the waves.

Doppler radio direction finding system

The earliest Doppler direction finding systems used a single antenna placed on a fast rotating turntable. As the receiving antenna approaches the transmitter, the frequency increases and as the antenna recedes from the transmitter, the frequency decreases. The receiver then observes a frequency modulated signal at a rate equal to the frequency of the rotation (rotation tone). The received signal is then de-modulated by FM receiver, which then produces the demodulated rotation tone. The angle of arrival is then determined from the phase offset between the original and the demodulated rotation tone [START_REF] Whale | A Rotating Interferometer for the Measurement of the Directions of Arrival of Short Radio Waves[END_REF].

Spinning the turntable fast enough to produce high frequency signal efficiently is very difficult. Because of this, the physically rotated antenna could be replaced by an antenna array. This array can consist of three or more separate omnidirectional antennas placed evenly along the perimeter of a circle. Each of the antenna is switched successively to make an illusion of the physical rotation. This modified system is known as the Pseudo-Doppler direction finding system and is a result of combination of the Earp and Godfrey system [START_REF] Earp | Radio direction-finding by the cyclical differential measurement of phase[END_REF] and the Whale system [START_REF] Whale | A Rotating Interferometer for the Measurement of the Directions of Arrival of Short Radio Waves[END_REF].

Block diagram of a simple Pseudo-Doppler direction finding system is shown in the Fig. 1. The Pseudo-Doppler antenna array is located in the top left corner of the image. In this case the array is assembled from four omnidirectional antennas. The antenna array is then connected to the antenna switch. This switch is driven by the antenna control unit and its purpose is to handle sequential switching of the antennas in the array. The radio signal then runs to a FM receiver, where is demodulated. In the next step, the audio output of the receiver is fed into a band-pass audio filter which passes frequencies within a range of rotation tone and rejects frequencies outside that range. To determine the angle of arrival, phase offset of this filtered audio signal is needed. This is carried out by the Zero-cross detector block. In the last step, phase offset of the signal is compared with the rotation tone and the angle of arrival is obtained.

Software Defined Radio

SDR is a radio communication system where components (such as demodulators, filters, amplifiers, etc.) that have been typically implemented in hardware are instead implemented as a software on a personal computer. The concept of SDR is not new, its origins can be tracked back to 1970's. For a long time computers were too slow to accomplish this task. As price of SDR hardware decreased in last years, SDR has gained a lot of popularity and its applications can be found in many sectors.

The main purpose of a SDR receiver is to transform desired frequency to an intermediate frequency and then convert it to digital data by a high speed A/D converter. Result of this process is a stream of digital information which represents the original radio signal by values of its sine and cosine component.

For the testing purposes, we decided to use the 860 MHz band which is regulated by general authorization VO-R/10/05.2014-3 and does not require a licence to use it. Band 860 MHz contains ultra short waves (λ ∼ 35 cm) which allows us to combine antenna switch and antenna array base easily. The maximum spacing between each separate antenna of the array is limited to less than λ 2 [START_REF] Peavey | The single channel interferometer using a pseudo-doppler direction finding system[END_REF]. Too small spacing increases mutual coupling between antennas, which in turn increases amplitude directivity of the antennas and reduces the Doppler tone strength in the receiver.

Because we wanted to include more usage scenarios in one design, we decided to make the antenna array as universal as possible. The Pseudo-Doppler antenna array with eight omnidirectional antennas mounted is depicted in Fig. 2. Each The classic antenna switch interconnection uses several passive components. The mechanism of antenna switching is described in [START_REF] Kossor | A Doppler Radio -Direction Finder Part 2[END_REF]. Fig. 3 shows the classic antenna switch circuit of Pseudo-Doppler antenna.

When we use antenna array with only four antennas, this circuit is sufficient. But for a larger number of antennas, the interconnection would become more complicated. Further, it is necessary to ensure that all used electrical components for antenna switching have the same electrical characteristics for each switched antenna. Should the characteristics of the components for individual antennas differ, the accuracy of the whole system would be negatively influenced and the performance of the whole Pseudo-Doppler system would suffer.

The switching element used according to Fig. 3 is a semiconductor diode D7 . . . D14. The highest attainable frequency for antenna switching is dependent on the characteristics of the used diode. When we introduce signal to J1-1 . . . J1-4 connectors, the corresponding antenna is disabled. To control the antenna switch, we need another integrated circuit -a shift register, which ensures the gradual antenna switching with specified frequency.

Our implementation of Doppler antenna array uses eight individual antennas. We have used HMC253 integrated circuit -which is suitable for highfrequency signal switching -to build high frequency electronic antenna switch. The HMC253 integrated circuit is able to process radio signal up to 3.5 GHz Fig. 3. Classic antenna switch for Pseudo-Doppler circuit [START_REF] Kossor | A Doppler Radio -Direction Finder Part 2[END_REF] with maximum switching frequency of 10 MHz, which significantly exceeds the attainable switching frequency for classic antenna switch.

The use of HMC253 circuit also significantly simplified the antenna switch circuitry. On the other hand, the disadvantage is that HMC253 circuit is presently available only with QFN socket, which is harder to mount on the PCB. The circuitry design is based on the HMC253 data sheet [START_REF] Devices | GaAs MMIC SP8T Non-reflective switch, DC -3.5 GHz[END_REF] and it is shown in Fig. 4. The HMC253 integrated circuit is placed in the center of the antenna array. The signal from individual antennas is sent to HMC253 integrated circuit through a coupling capacitor, each antenna is also loaded by a resistor. Insertion loss is less than 1.7 dB in the entire bandwidth. The communication is done by a simple parallel interface consisting of three binary input pins which select the connected antenna based on the address derived from their logical values -each binary combination connects one of the eight inputs to the output [START_REF] Devices | GaAs MMIC SP8T Non-reflective switch, DC -3.5 GHz[END_REF].

On one hand, one of the greatest advantage of HMC253 integrated circuit is higher antenna switching frequency. On the other hand, the antenna switching in this case is discrete switching. However, to ensure the correct function of Pseudo-Doppler antenna, the switching should be smooth and the transition gradual, which means that the influence of an antenna should decrease and at the same time the influence of the following antenna should increase. In the classic antenna switch, this effect is attained by charging and discharging of the capacitors, which ensure that the antennas are turned on and off smoothly. This is not possible with the selected HMC253 integrated circuit, and the effect has to be achieved by high-frequency antenna switching, which imposes higher requirements on the further signal processing.

Signal Processing Using GNU radio

Signal processing is based on the well known open source project GNU Radio [START_REF]The Free and Open Software Radio Ecosystem[END_REF]. This software development toolkit provides a signal processing runtime and processing modules with convenient tools for creating software radio implementations. As a software defined radio receiver we used the HackRF One from Great Scott Gadgets company [START_REF] Scott | HackRF One[END_REF] which is a very powerful and affordable open source hardware platform. Part of the Pseudo-Doppler direction finding system which is implemented in the software is enclosed by an orange box in Fig. 5. To achieve a good synchronization between the data stream and the antenna rotation, the internal clock of the HackRF One is used. Other tasks like tuner settings, FM demodulation or band-pass filtering are implemented in a very simple way with the help of the GNU Radio modules. On the other hand, comparison of a phase offset is a much harder task.

The filtered signal cannot be compared directly because of the different power levels, interferences etc. The Fig. 6 depicts processing of both rotation tones and angle of arrival calculation. The output data stream must be converted from the time domain to the frequency domain. This is done by Fast Fourier Transformation (FFT). Part of the data, whose size is equal to the size of the FFT window, is captured by the Stream to Vector module and processed by the FFT module and converted back to a data stream by the Vector to Stream module. The data are in the frequency domain now and the data relevant to the rotation tone can be now separated. This is done by the Skip Head and Keep 1 in N modules. The Eq. ( 1) is used to determine the number of the data samples to be skipped.

N = f s f r N F F T , (1)
where:

N Number of elements to skip f s Sample rate f r Rotation tone frequency N F F T Size of FFT
Since all digital samples of the signal are represented as complex numbers, the phase of the rotation tone is determined by their argument. The argument is obtained by the Complex to Arg module for each of the rotation tones. The phase offset, which is equal to the angle of arrival, is obtained after subtracting tones from each other. Purpose of the Add const module is to calibrate angle of arrival with respect to the north. This calibration is needed after each start of the system. Automatic calibration with usage of the HackRF One is a subject of a future work.

Test in Real-Life Conditions

The final testing of the designed radio direction finding system was carried out in the open area with minimum of the obstacles. The AoA was measured from distance of 100 meters in 10 degrees increments. The result of this measurement is depicted in the Fig. 7. The Figure shows the expected AoA in degrees on x axis and the deviation between expected and measured AoA on y axis. As we can see, deviation angle of the system is less than 20 degrees. The reasons for that low accuracy could be the ground slope of the area used for testing. The elevation level varied during the test and could be source of the low accuracy.

An interesting topic for future research will be the influence of the transmitter distance on Pseudo-Doppler antenna and the used antenna switching model. The use of specialized switching circuit instead of classic passive components brought both advantages and disadvantages. The influence of the new switching circuity on measurement precision has yet to be addressed.

We have tried to minimize the influence of the obstacles and the terrain profile on the measurements. The obstacles generally lead to reflections and the reflected signal negatively influences the measurement. Reflections generated step changes in measured values (angles), which complicates the use of Pseudo-Doppler antenna system inside in a closed environment or in a rugged area with many buildings.This was only the first test in real conditions and the development of the system continues.

Conclusion

The software defined radio brought new possibilities to many sectors and the implementation of the radio direction finding system is not an exception. The prototype of the Pseudo-Doppler direction finding system based on the software defined radio was presented in this article. The proposed Doppler antenna array was designed, constructed and tested. The original hardware based design of the Doppler system was reimplemented in the software. The paper has focused on the most complex parts of the proposed implementation.

The main advantage of the designed system is the possibility to analyse the entire bandwidth, which the software defined radio can provide at once. The number of the parallely analysed signals is limited only by the performance of the used computer. This is an enormous improvement against the traditional hardware implementation, where a separate receiver is needed for each individual signal.

Fig. 1 .

 1 Fig. 1. Pseudo-Doppler block diagram

Fig. 2 .

 2 Fig. 2. Pseudo-Doppler antenna array

Fig. 4 .

 4 Fig. 4. New design antenna switch for Pseudo-Doppler circuit

Fig. 5 .Fig. 6 .

 56 Fig. 5. Pseudo-Doppler block diagram with SDR

Fig. 7 .

 7 Fig. 7. AoA deviation


Wladyslaw Homenda

Agnieszka Jastrzebska
email: a.jastrzebska@mini.pw.edu.pl

Piotr Waszkiewicz

Anna Zawadzka

Pattern Recognition with Rejection Combining Standard Classification Methods with Geometrical Rejecting

Keywords: pattern recognition, classification, rejecting option, geometrical methods

The motivation of our study is to provide algorithmic approaches to distinguish proper patterns, from garbage and erroneous patterns in a pattern recognition problem. The design assumption is to provide methods based on proper patterns only. In this way the approach that we propose is truly versatile and it can be adapted to any pattern recognition problem in an uncertain environment, where garbage patterns may appear. The proposed attempt to recognition with rejection combines known classifiers with geometric methods used for separating native patterns from foreign ones. Empirical verification has been conducted on datasets of handwritten digits classification (native patterns) and handwritten letters of Latin alphabet (foreign patterns).

Introduction

The task of pattern recognition is a classical machine learning problem. As an input we pass a training dataset, consisting of labelled patterns belonging to c classes. In the process we expect to form a model that assigns correct labels to new patterns (new observations).

It is important to have in mind that patterns in their original form are often some sort of signal, for instance images or voice recordings. Due to the fact that the original patterns are often collected using some signal-acquiring devices, we may encounter patterns that do not belong to any of the proper classes. Such situation may happen, when the device that we have used to acquire data has been automatically reset due to power outage and poor default calibration distorts the segmentation process. Another scenario is when we collect data in a noisy (out of lab) environment and apart from proper patterns there are a lot of unexpected residual ones. The problem with such patterns, say -garbage patterns, is that we cannot predict their characteristics and therefore we cannot include information about them in the model training process.

The motivation for our study is to provide algorithmic approaches used for distinguishing proper patterns, that we call native patterns from garbage and erroneous patterns, that we call foreign patterns. The task described in this paper we call foreign patterns rejection. The design assumption is to provide methods based on native patterns only. In this way the framework that we propose is truly versatile and it can be adapted to any pattern recognition problem in an uncertain environment, where foreign patterns may appear.

The study focuses on designing methods for recognition with rejection and employs them to (a) distinguish native patterns from foreign ones and (b) improve classification quality of native patterns. A specific objective of this study is to examine the cooperation of various standard classifiers (SVMs, random forests and kNNs) with geometric methods used for rejection. We focus on the influence of rejection mechanisms on native patterns classification, i.e., improvement of Fine Accuracy measure. The proposed methods are empirically verified on datasets of handwritten digits (native patterns) and handwritten Latin letters (foreign patterns).

We would like to emphasise that the novelty of the contribution presented in this paper is not in the methods that we use, but in how we employ them and on what we achieve with them.

The remainder of this paper is organized as follows. Section 2.1 presents the background knowledge on foreign patterns detection present in the literature. Sections 2.2 and 2.3 address background algorithms, present in the literature. Section 3 presents the proposed approach. In Section 4 we discuss experiments. Section 5 concludes the paper and highlights future research directions.

Preliminaries

Data collection and processing are vital study problems across multiple domains of science. Along with a substantial automation of data acquisition we face difficulties that appear due to poor data quality. The research we present in this paper has been motivated by the issue of contaminated datasets, that apart from proper patterns contain garbage.

In this section we start the discussion with a review of relevant literature positions in machine learning that tackle the issue of contaminated datasets. Then, in order to provide a self-contained description of the employed methods we present backbone literature algorithms applied. In what follows we present the Minimum Volume Enclosing Ellipsoid (MVEE) algorithm and a suite of three classification methods: Random Forests (RF), Support Vector Machines (SVM), and K-Nearest Neighbors algorithm (kNN). Listed methods are employed in various configurations to native patterns classification with foreign patterns rejection. Our approach, based on those algorithms, is discussed in Section 3.

Literature Review

The rejecting option in pattern recognition problem has gained a rather weak attention despite its importance in practice. Also, there is a relatively short list of papers raising the problem of rejecting foreign patterns, cf. [START_REF] Homenda | Rejecting Foreign Elements in Pattern Recognition Problem. Reinforced Training of Rejection Level[END_REF] for a short survey.

Here we only hint some issues present in literature. Due to space limitations we are neither able to comprehensively cover the subject, nor can we provide a deep background of the methods employed in this study.

Discussion on approaches related to foreign patterns rejection may start with one-class classification methods. Especially, there are two noteworthy examples: centroid-based methods and One-Class Support Vector Machine.

Centroid-based methods rely on distinguishing cluster centres (centroids). Region reserved for proper patterns is usually defined by the distance between centre and the furthest proper pattern.

One-Class SVM has been introduced in [START_REF] Scholkopf | Support Vector Method for Novelty Detection[END_REF]. While "regular" SVM algorithm forms hyperplane separating two classes, the One-Class SVM separates data points from the entire feature space. Notably, the One-Class SVM provides a soft decision rules, as there is a ν parameter determining the fraction for outliers.

When it comes to the study on actual foreign patterns rejection, there are relatively few papers to review. This issue, in spite of its importance, remains somehow neglected. Among notable studies one may mention rank-based methods, for instance ones described in [START_REF] Bertolami | Rejection strategies for offline handwritten text line recognition[END_REF][START_REF] Burger | Dempster-Shafer based rejection strategy for handwritten word recognition[END_REF][START_REF] Elad | Pattern detection using maximal rejection classiffier[END_REF][START_REF] Hempstalk | One-class classification by combining density and class probability estimation[END_REF][START_REF] Scheme | Confidence-based rejection for improved pattern recognition myoelectric control[END_REF][START_REF] Tax | Growing a multi-class classifier with a reject option[END_REF][START_REF] Wang | A Support Vector Hierarchical Method for multi-class classification and rejection[END_REF]. In a nutshell, mentioned papers propose to attach confidence scores along with class labels. Rejection occurs when none of native class labels was assigned with a satisfying confidence.

Ellipsoids for Foreign Patterns Rejection

Both native and foreign patterns are represented with a vector of features extracted from the pattern of interest. Features are usually real numbers, therefore every pattern is a point in a multidimensional Euclidean space. What is more, we may propose a hypothesis that the set of native patterns belonging to the same class forms a cluster in the feature space. Assuming that this assumption is correct, we may be able to find minimal enclosing boxes for each native class.

In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. As opposed to convex hull, which is the most accurate point set container with smallest volume and which is enclosed by linear hyperplanes. Bounding boxes are far less complex. In many cases, when there is a need for computing convex hull and testing inclusions of other points, an approximation of such hull can be used, which helps in reducing time needed for computations, since most of alternative methods have lower construction and inclusion-testing complexities. Some of such approaches include using figures like hypercubes, diamonds, spheres or ellipsoids to successfully enclose given set of points.

When comparing highlights and drawbacks of each method from two perspectives: computational complexity and ease of point inclusion testing, ellipsoids seem to be a reasonable choice. Constructed ellipsoid is superior to the minimal cuboid in many ways. It is unique, gives better approximation of the object it contains and if E(S) is the bounding ellipsoid for a point set S with convex hull C(S) in dimension d, then:

1 d E(S) ⊆ C(S) ⊆ E(S)
, where scaling is with respect to the centre of E(S).

To sum up, adaptation of the smallest enclosing box problem to foreign patterns rejection, or native patterns identification, seems to be a very natural approach. The justification is fairly simple: if we enclose patterns belonging to native classes, using for instance ellipsoids, formed geometrical model will discriminate a region of the features space reserved for native patterns between a region where we may encounter foreign patterns. With this premise in mind, let us present a detailed description of the MVEE algorithm.

MVEE problem is solved by several known algorithms that can be categorized as first-order, second-order interior-point or combination of the two. For small dimensions d, the MVEE problem can be solved in O(d O(d) m) operations using randomized or deterministic algorithms [START_REF] Todd | On Khachiyan's Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids[END_REF]. In this paper the algorithm based on Khachiyan solution is used.

An ellipsoid in its centre form is given by the formula:

E = {x ∈ R n |(x -c) T A(x -c) ≤ 1}
where c ∈ R n is the centre of the ellipse E and A ∈ S n ++ is a positive definite matrix. Points lying inside the ellipsoid satisfy (x i -c) T A(x i -c) ≤ 1 + ε, where ε parameter defines the error margin in determining point belonging to ellipsoid, i.e. it allows to enlarge the ellipsoid.

However, constructing minimal volume bounding ellipsoid is not a convex optimization problem. It turns out that the solution is not easily obtainable so the dual problem has to be found. For a more precise and in depth solution description see [START_REF] Todd | On Khachiyan's Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids[END_REF]. The main problem, when using ellipsoids as identifiers, lies in constructing them. Two main factors that decide about identification effectiveness are tolerance and acceptance parameters. Tolerance can be viewed as a threshold for ellipsoid construction accuracy. The lower the parameter is, the better minimal volume ellipsoid is created. On the other hand, even with a good training set, there is a risk of including native patterns that lie outside of the created ellipsoid. Acceptance parameter has been introduced to prevent such unwanted behaviour. It defines a threshold for point rejection for points lying outside of the created figure.

Native Patterns Classification

The task of native patterns classification relies on forming a model based on a labelled training dataset that assigns proper class labels to new patterns. There is a multitude of classification algorithms, among which we have selected three different ones that are used in our methods. It is necessary to emphasize that if someone would like to adapt our method to their own domain, those algorithms could be substituted with some other classification tools that may be more efficient in that domain. Without further ado let us move towards a brief description of the methods that we apply in our study.

Support Vector Machines are a set of supervised learning methods used for classification, regression and outliers detection. The SVM algorithm relies on a construction of hyperplane with a maximal margin that separates patterns of two classes [START_REF] Cortes | Support-vector networks[END_REF]. SVMs are effective in high dimensional spaces, memory efficient, and quite versatile with many kernel functions that can be specified for the decision function. Although in some cases, where the number of features is much greater than the number of samples, this method can give poor results, and is not cost-efficient when calculating probability estimates. However, it is well suited for the problem presented in this paper. For a multi-class classification "one-againstone" approach is used. For c classes c • (c -1)/2 classifiers are constructed, each one is trained with data from two different classes. In our study we use decimal digits as classes. Therefore, the following 45 class-against-class SVMs are built: "0 vs 1", "0 vs 2", . . . "0 vs 9", "1 vs 2", . . . "1 vs 9", . . . "8 vs 9". Classification decision is taken by a voting method, i.e. a new pattern subjected to classification is counted to the most frequent class among these 45 binary classifiers. The case when two or more classes are most frequent, a second choice decision is made for actual classification. For instance, the closest pattern from most popular classes or minimal sum of distances from the processed pattern to ones from most popular classes may decide.

Random Forests is a popular ensemble method. The main principle behind ensemble methods, in general, is that a group of "weak learners" can come together to form a "strong learner". In the Random Forests algorithm ( [START_REF] Breiman | Random Forests[END_REF]) the weak learners are decision trees, which are used to predict the membership of objects in the classes. For vector of independent variables representing one object they calculate the value of the class the object belongs to by dividing value space into two or more subspaces. More precisely, an input data is entered at the top of the tree and as it traverses down the tree the data gets bucketed into smaller and smaller sets. In this method a large number of classification trees is generated. To grow each tree a random selection with replacement is made from the examples in the training set D. Those subsets D k are called bootstrap training sets. At each node m variables are selected at random out of the set of input variables and the best split on these m is used to split the node. After a relatively large number of trees is generated, they vote for the most popular class. Random Forests join few important benefits: (a) they are relatively prone to the influence of outliers, (b) they have an embedded ability of feature selection, (c) they are prone to missing values, and (d) they are prone to overfitting. k-Nearest Neighbors is an example of a "lazy classifier", where the entire training dataset is the model. There is no typical model building phase, hence the name. Class membership is determined based on class labels encountered in k closest observations in the training dataset [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF]. In a typical application, the only choice that the model designer has to make is selection of k and distance metrics. Both are often extracted with a help of supervised learning procedures.

Methodology

In general, there are two approaches that could be used to determine whether an object is rejected (classified as foreign). The first one assumes use of classification methods, which originally were not designed for rejecting. In the second approach classifiers are used only as a classification tool, whereas rejecting is realized by other methods, for instance geometrical figures or unsupervised cluster analysis. In this paper let us focus on the latter.

External Global and Local Rejecting

While ellipsoids are good for identification of native patterns region, they lack in pattern classification quality. This is caused by the fact that ellipsoids may overlap with each other, which results in conflicts when we want to univocally assign class labels. Although this can be solved by calculating distance between those patterns and each ellipsoid's centre, or by taking the value of ellipsoid-inclusion equation as a classification measure, tests have proven that such approaches are more prone to errors than other "standard" classifiers mentioned in this paper. Considering both strengths and weaknesses of classifiers and identifiers (for native region identification), the combined solution has been prepared that employs both tools (classifiers and ellipsoids), making use of their advantages.

Classifiers have high success rate, but cannot distinguish between foreign patterns and native ones. Contrary to that, ellipsoids tend to be better in rejecting foreign patterns, what makes them good at identifying patterns that should not be classified. The natural way of dealing with that problem would be to use ellipsoids as first-entry identifier that purifies input set by removing foreign patterns. The result of such rejection would be sent to the chosen classifier that would classify remaining native patterns. Due to the order of actions in this processing scenario we call this global rejection scheme. Schema of this method is presented in the left part of Figure 1. Please note that we show there a case of imperfect rejection/classification task, i.e. rejected and misclassified native patterns, as this is typically the case in real-world problems.

Another way of using ellipsoids as identifiers is to treat them as correction tools for an already classified dataset. This means that foreign patterns are not removed before classification. Instead, class-corresponding ellipsoid are employed to reject foreign patterns classified to the corresponding class. This is somewhat different from the previous approach because patterns can be rejected even if there is an ellipsoid that would pass inclusion test. The schema of this classification/rejection scenario can be seen in the right side of Figure 1. Because rejection occurs at the local level of each native class we call this approach a local rejection scheme.

Quality Evaluation

In order to evaluate the quality of the proposed methods patterns from the following groups are counted:

-CC (Correctly Classified) -the number of correctly classified patterns, i.e. native patterns classified as native ones with correct class label, -TP (True Positives) -native patterns classified as native (no matter, into which native class), -FN (False Negatives) -native patterns incorrectly classified as foreign, -FP (False Positives) -foreign patterns incorrectly accounted as native, -TN (True Negatives) -foreign patterns correctly accounted as foreign.

These numbers are then used to form measures reflecting specific aspects of classification and rejection, cf. Table 1. Notions that we use are well-known in the domain of pattern recognition, cf. [START_REF] Homenda | Rejecting Foreign Elements in Pattern Recognition Problem. Reinforced Training of Rejection Level[END_REF]:

-Strict Accuracy measures classifier's performance. It is the ratio of the numbers of all correctly classified patterns to all ones being processed. -Accuracy is a "softer" characteristic derived from the Strict Accuracy. Accuracy describes the ability to distinguish between native and foreign patterns.

The difference is that we do not require that the native patterns are labelled with their proper class label. -Native Precision is the ratio of the number of not rejected native patterns to the number of all not rejected patterns (i.e. all not rejected native and foreign ones). The higher the value of this measure, the better ability to distinguish foreign patterns from native ones. Native Precision does not evaluate how effective identification of native patterns is. -Native Sensitivity is the ratio of the number of not rejected native patterns to all native ones. The higher the value of Native Sensitivity, the more effective identification of native patterns. Unlike Native Precision, this measure does not evaluate separation between native and foreign patterns. -Strict Native Sensitivity takes only correctly classified native patterns and does not consider native patterns, which are not rejected and assigned to incorrect classes, unlike Native Sensitivity, where all not rejected native patterns are taken into account. -Fine Accuracy is the ratio of the number of native patterns classified to correct classes, i.e. assigned to their respective classes, to the number of all native patterns not rejected. This measure conveys how precise is correct classification of not rejected patterns. -Foreign Precision corresponds to Native Precision, i.e. it is the ratio of the number of rejected foreign patterns to the number of all rejected elements. -Foreign Sensitivity corresponds to Native Sensitivity. -Precision and Sensitivity are complementary and there exists yet another characteristic that combines them: the F-measure. It is there to express the balance between precision and sensitivity since these two measures affect each other. Increasing sensitivity can cause a drop in precision since, along with correctly classified patterns, there might be more incorrectly classified.

Experiments

In this section we move towards description of a series of experiments where we apply rejection strategies discussed theoretically in Sections 3. 1. In what follows we describe datasets, experiments' settings, and results.

Datasets

We present a study on handwritten digits recognition and handwritten letters (from the Latin alphabet) rejection. In other words, native patterns set is made of digits (it is a ten class problem), while foreign patterns are 26 different handwritten letters. The justification to assume such foreign dataset for testing purposes is that appearance of other real-world symbols, but not belonging to any proper class, is a common issue in a character recognition problem. We would like to stress again, that foreign patterns do not participate in the model building phase. The entire scheme is based on native patterns only. Handwritten letters are used only for rejection mechanisms quality evaluation. Samples of processed patterns are displayed in Figure 2.

The native training dataset consisted of 10,000 handwritten digits with approximately 1,000 observations in each class taken from publicly available MNIST database [START_REF] Lecun | The MNIST database of handwritten digits[END_REF]. We split each class in proportion ca. 7:3 and as a result we got two sets. The first one includes 6,996 patterns and is used for training. The second set, the test set, contains 3,004 patterns. The dataset of foreign patterns contains 26,383 handwritten Latin letters, ca. 1,000 letters in each class. This dataset was created by 16 students, writing about 70 copies of each letter.

All patterns were normalized and feature vectors comprising of 106 numerical features were created. Examples of features are: maximum/position of maximum values of projections, histograms of projections, transitions, offsets; raw moments, central moments, Euler numbers etc. The best first search for the optimal feature subset has been performed using FSelector R package [START_REF] Romanski | Package FSelector[END_REF] and then analysis of variance was employed to select good features. The final feature vector contained 24 elements. We considered features standardization but the training data is sufficiently consistent (there are no outliers), so we normalized those features to bring linearly all values into the range [0,1].

Experimental Settings

Solutions presented in this paper have been implemented in Python programming language, using scientific libraries [16,17,18]. The MVEE algorithm, available as MATLAB code has been rewritten in Python language, using NumPy library for matrix representation and operations. Several tests have been performed in order to find best suited method parameters for both classifiers and identifiers. For finding those values the Grid Search [18] has been used for SVM and RF. MVEE parameters. Each ellipsoid was created and used with two parameters: tolerance and acceptance. The tolerance argument was used during creation phase, as "accuracy measurement". Lower value means that created enclosing figure is more fitted to the construction set. Acceptance parameter defines how far can a point lie outside the ellipsoid to still be identified as belonging to it. In other words, it treats enclosing ellipsoid as being bigger than it really is. Parameters tests involved computing effectiveness of MVEE algorithm for certain tolerance and acceptance values. We tested values from such ranges:

-tolerance = [0.5, 0.2, 0.1, 0.01] -accuracy = [0.1, 0.01, 0.001, 0.0005]

The results revealed that for the given training and test sets the best parameter combination was tolerance=0.5 and accuracy=0.1 and those values were used in the final, combined method described later in this document.

SVM parameters. SVM method available in the Scikit package offers a few built-in kernels that were used during computations: radial basis function and polynomial. Additionally, there are two more parameters that were tested: C (described as penalty parameter C of the error term), and γ (known as kernel coefficient). Values that were tested:

-kernel = ['rbf', 'poly'] -C = [1, 2, 4, 5, 16] -γ = [2 -1 , 2 -2 , 2 -3 , 0, 00025]
The best found combination of those parameters used rbf kernel along with C=8 and γ = 2 -1 values.

Results of Experiments

In this section we present the results of our experiments. We use quality measures presented in Section 3.2. We investigate classification quality, rejection quality and rejection's impact on classification quality. We compare two scenarios: global (rejection on is the entire dataset) and local (rejection mechanism is separate for each native class).

Influence of Rejection on Native Patterns Classification Adding a rejection mechanism, ideally, may be a method for improvement of classification rates. It would be perceived as a positive side of the rejection mechanism, if it would be able to reject those native patterns, which would be incorrectly classified when there is no rejection mechanism at all. Trained models partially fulfill this wish. Conducted tests, reported in Table 2, show that Fine Accuracy improved for both local and global rejection schemes and for all classifiers. This means that we have a better recognition rate (the proportion of correctly classified patterns) in the data that was accounted as native. However, we have to notice that both rejection mechanisms rejected some native patterns. Hence, Strict Accuracy and Strict Native Sensitivity are slightly higher when we do not have any rejection mechanism.

Results indicate that performing pattern rejection after their initial classification (the local rejection scheme), brings better results than using the global scheme. This could be explained by the fact that in the local rejection scheme we use one ellipsoid per each class and we apply those ellipsoids after classification. First, let us mention that for the global rejection all rejection rates are the same for all classifiers. This is due to the specificity of this model, where rejection occurs first, so classification procedure does not modify the content of the set subjected to rejection. However, the global approach turned out to be slightly worse than the local approach.

Results show that in the local rejection model all classifiers combined with ellipsoids behave well and provide similar quality of rejection.

Conclusions

Enhancing classifiers' ability to classify objects by coupling them with ellipsoids for foreign patterns rejection has proven to yield good results. Conducted experiment on handwritten digits contaminated with handwritten letters showed that the local rejection scenario with fine-grained rejection ellipsoids one per each native class perform better than the global approach with a single, but less finegrained rejection mechanism. We also report that the differences in classification ratios in the local rejection model coupled with different classifiers turned out to be very slight. SVM turned out to be the best, and its advantage is visible when we evaluate the rate of native patterns that were rejected that wanted to reject, because otherwise they would have been classified into incorrect class.

We are aware that to truly confirm obtained results, test should be repeated on different data sets. Described in this paper set consisting of letters and digits, although being very large, might not match wide spectrum of problems.

Let us conclude this paper by saying that various adaptations of the idea of foreign patterns rejection have a vital role in modern machine learning. It is needless to mention areas such as text mining, fraud detection, or medical diagnosis systems where we deal with various reincarnations of the foreign patterns. From this perspective we believe that the study in this direction is worth further efforts.

Fig. 1 :

 1 Fig. 1: Ellipsoids employed for rejecting: global rejection (left part) and local rejecting (right part). Questions marks (?) stand for foreign patterns, circles, squares, triangles and pentagons -for native patterns.

Fig. 2 :

 2 Fig. 2: Sample of: native patterns (top) and foreign patterns (bottom).

Fig. 3 :

 3 Fig. 3: Quality evaluation for global and local rejection schemes realized with ellipsoids with different classifiers: random forests, SVMs, and kNNs.In contrast, in the global scheme we have a joint set of ellipsoids that we apply to the entire dataset. In the local rejection scenario native patterns identification regions are applied individually to each subset obtained from the classifier. As a result there is a chance that classification would contribute to foreign patterns filtration. The same conclusion, about superiority of local rejection over global one concerns strict classification error ratios.When comparing the overall quality achieved by mechanisms based on different classifiers we see a slight advantage of SVM. Separating Letters from Digits Figure3presents rejection results. We compare various quality measures for models constructed based on random forests, SVM, and kNN with ellipsoids for the global and the local rejection schemes.First, let us mention that for the global rejection all rejection rates are the same for all classifiers. This is due to the specificity of this model, where rejection occurs first, so classification procedure does not modify the content of the set subjected to rejection. However, the global approach turned out to be slightly worse than the local approach.Results show that in the local rejection model all classifiers combined with ellipsoids behave well and provide similar quality of rejection.

Table 1 :

 1 Quality measures for classification and rejection.

  Random Forests parameters. The Scikit library was used to test random forests. Random forests with the following number of trees were tested: 1, 2, 3, 5, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150. It turned out that the best number of trees to build the forest was 100. kNN parameters. We tested the following values of k (the number of neighbours): 1, 2, 3, 4, 5, 10, 20, 30, 40, 50. The best found value of k was four. There is also one parameter -metric, but we use the standard Euclidean metric.

Table 2 :

 2 Classification with random forests, svms and knn and rejection with ellipsoids on the set of native patterns: no rejection vs. local and global rejections. Notice that all three measures turn to the same proportion CC/TP for no rejection mode.

			No rejection	Global rejection	Local rejection
	Basic Classifier	RF SVM kNN	RF SVM kNN	RF SVM kNN
	Data Set		Native Patterns, Train Set
	Strict Accuracy	1	0.985 0.955 0.941 0.938 0.936 0.942 0.942 0.942
	Fine Accuracy	1	0.985 0.955	1	0.987 0.972	1	0.989 0.984
	Strict Native Sens.	1	0.985 0.955 0.879 0.852 0.854 0.864 0.857 0.845
	Data Set		Native Patterns, Test Set
	Strict Accuracy 0.952 0.966 0.930 0.946 0.946 0.944 0.951 0.952 0.953
	Fine Accuracy 0.952 0.966 0.930 0.972 0.982 0.959 0.977 0.985 0.976
	Strict Native Sens. 0.952 0.966 0.930 0.842 0.852 0.831 0.837 0.845 0.825

Acknowledgment

The research is partially supported by the National Science Center, grant No 2012/07/B/ST6/01501, decision no DEC-2012/07/B/ST6/01501.