Abstract
Abstract: A key challenge in computer vision applications is detecting objects in an image which is a non-trivial problem. One of the better performing proposed algorithms falls within the Viola and Jones framework. They make use of Adaboost for training a cascade of classifiers. The challenges of Adaboost-based face detector include the selection of the most relevant features which are considered as weak classifiers. However, selection of features based on lowering classification error leads to high computation complexity. To overcome this limitation, a novel genetic Adaboost is proposed in our work. In the same context of optimisation, a selection method based on Pareto concept of the most relevant features referred to as dominant features is proposed. This optimisation allows to reduce the initial feature space by 28%. Moreover, we notice that dominant features with genetic Adaboost further improve the performance of genetic Adaboost, reducing the total number of features by 20%.
Introduction
The human being is more and more interested in reproducing intelligence which is one of the most impressive features of the nature. Researchers are trying to build intelligent machines that have various capabilities. Building machines or robot is probably one of the most challenging problems which humans are trying to solve. Recently, many projects have started with the purpose of learning machine to detect objects. Many classes of objects can be efficiently detected by the way of machine learning techniques such as faces, cars, pedestrians, etc. Faces, pedestrians and cars, have been detected with minimal error rates by learning their appearance using extensive training sets. The most popular sub-problem within the object detection domain which many researchers focus on is face detection.
The interest of research and development in the field of face detection concern many real world applications. It holds the key to many high level applications such as face recognition, human-machine interactions, security and tracking faces among others.
At a first glance, the face detection may not seem very hard namely when considering how the task is easily solved by human. But it is far beyond in reality, it is very difficult to make this task solved by a computer. For this purpose, a number of promising face detection techniques has been developed.
The various techniques proposed in the literature are classified by Yang and Kriegman (2002) into four main categories: knowledge-based, feature invariant, template matching and appearance-based methods.
Knowledge-based methods
These methods make use of the human consent based on the content of face images using rule-based methods. They are characterised by their easiness to come up with simple coded rules. Such rules present features of a face and works well under uncluttered background. These methods are based on a set of simple rules, which typically extract relationships between different facial features.
Feature invariant methods
As their name suggests, they are methods regrouping all feature-based ones. In contrast to knowledge-based approaches, researchers have been trying to find invariant features. Based on the extracted features, they build statistical models describing their spatial relationships related to the existence of a face. Then, the extracted features should be relevant, invariant to pose, lighting conditions, orientation change, etc. Specific facial features either are concerned with geometric features such as eyes, nose, etc. Or they include appearance related characteristics such as colour, texture, edge, shape, intensity, etc. However, one problem with these feature-based algorithms is that invariance can be ensured in open environment context.
Template matching methods
In these methods, the detection is achieved by computing the correlation between standard stored templates of a face and an input image. They are characterised by their simplicity and rapidity. However, they had shown a limitation in terms of robustness because it is difficult to enumerate templates for different possible cases.
Appearance-based methods
In contrast to template matching where templates are defined by experts, these methods use models learned from training sets to represent the variability of facial appearance. Appearance-based methods, which consist in extracting features from pixel intensity of face and non-face images, are based on techniques from statistical analysis to machine-learning. Accordingly, a huge dataset covering all kind of variability in the image, regarding background complexity, illumination conditions, pose and scale, will convey robustness to these kinds of approaches. Moreover, learning makes these techniques potentially applying on different kinds of objects. It is just matter of updating the different feature contributions in the considered objects. The majority of these methods are based on a learning algorithm using a large set of face images in the training process.
One of the better performing algorithms which falls within appearance-based methods is proposed by Jones (2001, 2004) . It uses adaptive boosting (Adaboost), a popular machine learning technique for selecting a set of better performing weak classifiers from a pool of over complete weak classifiers (Freund and Shapire, 1995) . Several machine learning approaches have been proposed to this aim, showing significant improvements in detection in terms of accuracy and speed.
The compromise between fast training and effective features remains a challenging problem in Adaboost-based face detection. Variability in face detection problem related on the one hand to the face representation and on the second hand to background and acquisition condition has guided us to choose the appearance-based approaches based on machine learning.
In these approaches, the main key questions are: what is the most relevant feature to extract for efficient classification? And what is the convenient feature to keep from an over complete pool of the extracted features in the subsequent stages of the algorithm?
Approaches followed in the literature to tackle these problems are based on proposing more relevant features, or focusing on improving the boosting algorithm, or a combination of both approaches.
Limitation in conventional Adaboost training process
In our work, some limitations which are related to the learning process are faced. The weak classifier functionality is to find a weak rule H t : X → Y which is appropriate for a distribution D t . But what we mean by appropriate? Here, the quality of a weak classifier depends on its error, according to the weights:
As noted in the mentioned equation, the error is measured with respect to the distribution D t , on which the weak learner is trained. In practice, the weak learner is an algorithm weighting (by D t ) the training samples. For each iteration in Adaboost algorithm, a new weak classifier is selected according to the error criterion. In some cases, no improvement is made with respect to the detection rate or false positive one.
Some weak classifiers greatly enhance the performances but others do not contribute and even end up with a performance drop. This is can be illustrated by an example of training a single stage of the cascade, adding features through the Adaboost training process, the evolution of the detection rate and false positive rate is given in Table 1 . If we examine the results below, we notice that the first five selected features improve the results in term of the DR and increase the FPR. However, the increase of the FPR can be treated in the subsequent stages in the cascade structure. The 6th selected feature do not contribute to the training process. Also the 12th feature slightly degrade the performance on the validation set in term of FPR. This can be attributed to the fact that, often some of the selected features although leading to lower errors, are irrelevant, which increases the training time and memory resources. A key question here is how to add relevant features without decreasing the training performances?
In the following sections, we try to overcome these limitations by optimisation with genetic algorithms (GAs).
This limitation motivated us to find a search technique of weak classifiers that outperforms the solution based on lowering the classification error. A face detection task is considered as a classifier training problem, searching the parameters for a best modelling of a given training data. In the standard model, we need to specify many parameters and then estimate their values from training data. When these standard models are simple, it is possible to find their optimal parameters by solving equations explicitly. However, when the task becomes more complex, it is very difficult to find the optimal parameters.
In this work, we focus on the optimisation of the feature selection process of the most relevant ones by GAs. In fact, selected features by Adaboost, within a single stage are dependent on each other's and there is no analytic relation between the number of features and the corresponding detection performance. Thus, the optimisation task is nonlinear, hard and then seems to be suitable to be treated by GAs.
Use of GAs takes profit of two advantages. Firstly, GA perform as a searching mechanism to select the most effective features overall the feature space. Secondly, a new method inspired from the Pareto frontier is proposed to construct a frontier composed of the most relevant features referred to as dominant features. The use of GAs comes to improve the selection process by reducing the feature set, keeping on the most relevant and discarding the redundant weak classifiers.
The remaining of this paper is organised as follows: Section 2 describes our methodology for Adaboost optimisation. Section 3 presents experimental results and performances for our face detection system. Finally, Section 4 summarises our work and draws some conclusions.
Methodology for Adaboost optimisation

Basic Adaboost
A boosting algorithm is able to construct a strong classifier by a linear combination of weak classifiers chosen from a huge amount of set. The single strong classifier obtained is much more reliable than the weaker ones. The set of weak classifiers that contributes to the final response can be simple in some cases. However, a scheme of training them has been devised in order to have a small error in the final classification. In face detection, each classifier is constructed by a single feature. The time spent in the training process is very important, which can be attributed to the exhaustive search of the features in the whole set. Taking into account this conventional Adaboost, we can wonder whether the selection of weak classifiers based on lowest errors leads to the optimum solution.
Each hypothesis in the training algorithm is constructed using a single feature. The algorithm is described in the following:
• Given a series of samples (x1, y1), ........, (x n , y n ) where y i = 0, 1 for a binary outcome.
• Initialise weights 
where α t = log(1/β t ).
Genetic Adaboost

Basic principle
In this paper, we review the previous researches which investigate the GAs to ameliorate the face detection algorithm (Zhang and Zhang, 2010; Yang et al., 2010) . Then, we will present our contribution. In Chen et al. (2004) , the GAs was exploited to construct a large database by resampling existing faces. In fact, they have expanded the face samples by applying crossover and mutation. In Treptow and Zell (2004) , an evolutionary search was employed within Adaboost framework in single stage classifiers to select accurate features from large features pool in reasonable time. As an amelioration of the Treptow and Zell work, Zalhan et al. (2007a Zalhan et al. ( , 2007b had used the GAs inside the Adaboost framework to select features, which provides better results in the obtained cascade of classifiers in less training time. In their proposed technique referred as GABoost, the GAs carried out an evolutionary search in the feature space which was enriched with more types of features. In our work, we make use of the GAs to further improve the feature selection process in Adaboost. Two constrained objectives can be considered. They are the detection rate which has to be maximised and the false positive rate which has to be minimised. Thus, a multi-objective GA for the optimisation process should be adopted.
GAs formulation
In mono-objective GAs, individuals can be compared easily. However, in multi-objective GAs, this task becomes more complex. There are several methods that are proposed to solve the multi-objective problem.
In the literature, the multi-objective problem has been treated, based on two different approaches. The first one is to bring back a multi-objective formulation to a mono-objective one, referred to as Aggregate method. The second approach, referred to as non-aggregate method, is to try to afford answers taking into consideration the whole of the criteria (Ghribi, 2011; Coello, 1996) .
The entire GAs procedure is summarised as follows (cf., Figure 3 ).
1 Representation: Each individual in the population corresponds to an association of weak classifiers. The number of weak classifiers by individual (denoted by T) is variable and can be changed in the optimisation process.
2 Construction of the initial population: For more efficient detection, decision is preferably made from earlier stages with minimum computing complexity. Thus, less number of classifiers is recommended, so that only hard samples are kept to subsequent stages. When we go forward in the optimisation process, better performances are required from a stage to another. In fact, classification task is getting harder when going forward in the cascade, suggesting more classifiers to be used for better efficiency. In our approach, a maximal dimension of strong classifiers (denoted by T max ) is initialised in GAs and depends on the rank of the current stage
In our proposed method, initial individuals are of variable length. We denote by T i the number of genes in individual I i , with T i < T max . Each gene of I i is denoted by I i,j , j ∈ 〈1, 2, ..., T i 〉. T i and I i,j are generated randomly. Besides, it is well known that the better the initial population the more efficient are optimisation results. For this purpose, we propose a new method for ameliorating the initial population by selecting the more relevant features referred to as dominant features. This method will be explained in details in a separate subsection.
3 Fitness computing: This function makes it possible to evaluate the effectiveness of the chromosomes solutions. It depends on criteria which should be maximised or minimised. The objectives of the used GAs are defined based on the method ε-constraint (Coello, 1996) . This method is based on a minimisation of an objective f i by considering that the other objectives f j with j ≠ i must be lower than a value ε j . In general, the selected objective is the one that the decision maker wishes to optimise in priority:
min ( ) with ( ) ,
In our system, the objective is the maximisation of the detection rate and the false positive rate is considered as a constraint.
4 Reproduction: For this step the elitist method is used, which is intended to prevent the lost of the best individuals. Thus, technically, best individuals are reinserted in the future population and the remainder of the future population is constructed based on the wheel selection method.
5 Crossover: The crossover is an exchange per blocks of elements between two chains to generate one or two others of them. A site of crossover is randomly selected over the length of each parent chromosome and a cut of the chromosome is done. This cut produces two pieces which can be permuted. The resulting children chains contain each a piece inherited from each parent.
6 Mutation: In binary population, some bits of population are chosen to sudden mutation, according to mutation's probability. Their values are then reversed.
7 Population sorting: In this step, we perform the union of populations before and after genetic operations (crossover and mutation), then we sort them according to the detection rate, the best half of the resulted population are chosen to participate in the future generation by the elitism mechanism.
The algorithm is described in the following:
• Given sample images (x1, y1), ........, (x n , y n ) where y i = 0, 1 for negative and positive examples respectively. An individual I i from population at certain generation where I i,j is the element (gene) of the individual. j is the feature index.
• Initialise weights so that w t is a probability distribution. For each feature j, train a classifier h j is restricted to using a single feature. The error is evaluated with respect to w t , ( ) . 2 Update the weights: All GAs steps fall within the conventional ones, except the construction of the initial population step, which is based on dominance concept. Thus, we add some details on the way we select dominant features in the following section.
Dominant feature selection
The concept of dominant features was used in some researches for feature extraction process. For instance in Bamini and Kavitha (2010) , the dominant features which are extracted from the LBP image, called dominant local binary pattern (DLBP), consider the most frequently occurred patterns in a texture image. In their paper, authors demonstrate that a minimum set of 80% patterns can efficiently illustrate the image textural information. In order to ameliorate the performance of the Adaboost in the feature selection process and reduce the training time, the idea is to search the dominant features which are more relevant to classify positive and negative images.
Dominant features
The idea behind the dominant features is based on the best classification rate of an input image I by a single feature f i . A positive/negative image contributes to the classification rate. Starting from the idea that we should not loss any feature that well classifies new image especially negative ones which are harder to be classified. For example, given feature 1, that well classifies two negative images, feature 2 classifies correctly the same two images and another negative image. In this case, feature 2 dominates feature 1. The idea can be illustrated by a simple example (cf., Figure 2 ). In this example, we take five positive images and ten negative ones.
Pareto concept
The concept of dominance is inspired from Pareto (1896) methods, that falls within multi-objective GAs. Pareto methods are based on the concept introduced by Pareto which privileges one research satisfying all the objectives as well as possible. The definition is as follows.
Definition 1: Pareto's concept of dominance in case of minimisation problem
In our case, f k is the right classification rate of image I in the dataset. The Pareto's concept is illustrated by Figure 3 . The algorithm of determining dominant features is described as follows.
• Compute the classification result C i of each single feature.
• Compare C i to labels (C i == labels)
• Compute the Pareto frontier 
Experimental results

Training methodology
We had to choose the cascade parameters and the training samples which determine the number of stages and so the number of features in each stage. The training dataset consists of 130 images with 507 labelled frontal faces. The faces were cropped to images of size 19 * 19 pixels. We had to choose the cascade parameters and the training samples which determine the number of stages and so the number of features in each stage. First, we devote our experiments to a single stage exploration.
Training a single stage
The system was trained using 500 faces and 1,000 non-faces. For the test set, we have used 500 faces and 500 non-faces. Using the Haar-like features, we start by training a single stage to compare the performance of the genetic Adaboost to the conventional Adaboost. According to Table 2 , we notice that the obtained results are better especially in term of the DR. Results are obtained with only ten generations of the GAs. The proposed optimisation process seems to be promising and we should validate it by training a cascade structure. 
Training a cascade structure
The system was trained using 500 faces and 1,000 non-faces. For the validation set, we have used 100 faces and 300 non-faces. For each stage classifier, the minimal detection rate is 0.98 and the maximal false positive rate is 0.5 on the validation data. For the learning process, we have to start with a big number of negative samples. Then, at each stage, only the samples that are classified as positive are kept on the subsequent training set. Thus, the next stage in the process is trained to classify the samples that have been misclassified by the previous stages. Furthermore, a few number of hard samples (like faces) are left to the latest stages of the cascade. Consequently, the number of negative images to train the model and so the number of features per stage decreases and the obtained cascade seems to be not consistent. In order to overcome this problem, we train each layer of the cascade with the same number of negative samples. That is, we add new negative samples for each stage to maintain the initial number of negative samples.
In the training process, we conduct two experiments. The first one was achieved to evaluate the whole set of features using genetic optimisation. The second one was carried out using both the dominant features in the initial population construction and the genetic optimisation. For the negative samples, the number is higher than the number of faces in order to represent faces as well as the background of real images. However, it is a hard task to know a priori the negative images that are more representative of the non-faces class and the number of non-faces that are sufficient to train an efficient cascade.
GA optimisation
It should be underlined that GAs suitability for improving the Adaboost-based face detector performances comes from its stochastic generation of populations. Indeed, GAs performs well on constrained multi-objective problems and are able to explore large nonlinear design spaces. In fact, we use 100 as population size, which was initially an arbitrary number but was confirmed by good results. Since the crossover step should be frequently done, the crossover rate must be high and is generally set to 0.8. Usually in GAs, we use a low value of mutation rate. As we adopt an elitist method in our work which decreases the population diversity, we use high mutation rate to ensure diversity (Table 3 ). Table 4 . The total number for the different stages is 464. Using the GAs optimisation, the number of weak classifiers was reduced considerably (cf., Figure 4 ). In fact, the total number of features was reduced to 57% of that constructed based on the Adaboost method (Jammoussi et al., 2013) . The proposed genetic Adaboost ensures the optimisation of the system performances given a number of features. It was achieved by selecting the most relevant features and eliminating redundancy.
GA-based selection using dominant features in initial population
The application of our method for selecting the dominant features has reduced the number of features by 28%, we obtain 36,150 features. To further demonstrate the powerfulness of the optimisation method, we train a cascaded classifier. The training process is achieved with ten stages and 373 features. The total number of weak classifiers for different stages using dominant features was reduced by 20%. According to the results mentioned above, the number of stages for each cascade is 10, which is relatively small. We obtain high false positives rate due to reduced number of stages in the cascade. Thus, we intend to increase the number of stages in the cascade either by starting by a big number of negative images in the training process or by using somewhat a small database and then adding new negative examples at each stage. 
Comparative study and discussion
Compared to standard Adaboost-based face detector, our proposed method based on GAs reduces considerably the total number of features. The number of weak classifiers is directly related to computation time, especially the first few stages are critical in terms of detection speed since most test windows are rejected by the first weak classifiers in a cascade structure. Consequently, this reduction speeds up the final face detector and makes it easy and less expensive to implement on hardware architecture. Besides, according to Table 4 and Figure 5 , dominant features further improve the results. In fact, dominant features are more relevant and can contribute well on the system performances. 
Training improvement
For the training process, we have to start with a big number of negative samples. Then, at each stage, only samples that are classified as positive are kept on the subsequent training set. Thus, the next stage in the process is trained to classify samples that have been misclassified by the previous stages. Furthermore, a few number of hard samples (like faces) are left to the latest stages of the cascade. Consequently, the number of negative images to train the model and so the number of features per stages decreases and the obtained cascade seems to be not consistent. In order to overcome this problem, we start with a small number of training set and add to it new negative samples at each stage to maintain the initial number of negative samples. One of the main drawbacks of Adaboost face detection is that the result directly tied to the size and consistence of the training datasets.
In the results presented above, the number of new non-faces added to each layer is not very large. That is why the cascade contains many weak classifiers to reach the goal false positive rate, and so the number of weak classifiers with conventional Adaboost is high. Using the GAs optimisation, the number of weak classifiers was reduced considerably. In fact, the total number for the different stages is 464.
Influence of database size
As shown in Figures 6 and 7 , the database size has an important effect on the system's performance. The obtained results with 2,500 faces and 5,000 non-faces are greater than the obtained performances with 500 faces and 1,000 non-faces. 
Conclusions
In this paper, we have proposed the investigation of the GAs within the Adaboost training process for efficient feature selection. Instead of selecting sequentially weak classifiers with Adaboost training process, we proposed to select them at the same time to construct a strong classifier for each layer. The maximum number of features for each layer is fixed in advance and then the features are selected without redundancy. In the same context, to further improve the training process, we have proposed a new approach based on selection of dominant features determined with Pareto concept. This approach is beneficial in reducing the initial feature space. Another advantage of our proposed method, is that it allows to search the dominant features disregarding the features types.
Our proposed method based on both GAs and dominant features makes possible the reduction of the number of features for each layer. The reduction of the number of features obtained by the two proposed methods makes it suitable for hardware implementation. There is still room to further improve the system performances, so our future work consists on applying a Pareto multi-objective method.

{'paper_id': '26685772', 'title': 'Genetic algorithms-based dominant feature selection for face detection application', 's2_url': 'https://api.semanticscholar.org/CorpusID:26685772', 'source': 'S2ORC'}