A Face Detection Method Based on Image Processing and Improved Adaptive Boosting Algorithm

Face detection and recognition are two key tasks in digital image processing [12, 13]. Among them, face detection has been regarded as a key research direction. Most face detection methods are based on either features or statistical rules.

The feature-based methods detect faces in the light of knowledge rules, feature invariance rules or template matching rules. Based on knowledge rules, the face detection methods are not highly efficient [14]. Based on feature invariance rules, the face detection methods cannot capture the facial features well, under the changes of attitude, angle and expression [15]. Based on template matching rules, the face detection methods incur an excessive computing load, making it difficult to establish standard models [16].

The statistical rule-based methods extract and use the common rules of faces through training on numerous face samples. The most popular statistical rule-based method is AdaBoost [6]. On the upside, Adaboost face detection features high robustness, high detection rate and low FRR. On the downside, the algorithm lacks an optimization mechanism for parameters, and requires lots of samples and long time in training, failing to achieve a good real-time performance.

To solve the above problems, many scholars have studied and improved the AdaBoost algorithm. For instance, Lee et al. [17] proposed a novel weight adjustment factor, and applied it to the weighted support vector machine (SVM), serving as the weak classifier in AdaBoost algorithm. Li et al. [18] improved the AdaBoost algorithm by a new weighting coefficient solving method, which determines weighting coefficients based on both error rate and the recognition rate of positive samples. Dou and Chen [19] presented an improved AdaBoost algorithm with weighted vectors, in which each class is weighted based on its probability of being recognized by basic classifiers; the weighting process helps to effectively prevent overfitting. Zhang et al. [20] added Q-statistic to the training of weak classifiers to determine the correlation and remove similar rectangular features. Zhang et al. [21] optimized the weights of AdaBoost weak classifiers with the improved bacterial foraging optimization. Taherkhani et al. [22] designed a hybrid algorithm called AdaBoost-CNN (convolutional neural network), which lightens the heavy computing load of classic AdaBoost in handling massive training data by reducing the learning time in component estimation. Wang et al. [23] proposed a new sparse AdaBoost as the integration framework to enhance system generalization. Based on Boolean function, Windeatt et al. [24] put forward a spectral analysis method to approximate the decision boundary of the classifier set. The above methods either reduces the training time or lowers the FRR, failing to solve all the said defects simultaneously.

This paper develops a novel AdaBoost algorithm for face detection. Firstly, the original image was subjected to light treatment and noise removal. Then, the solving formula of weighting coefficients was optimized by adding the weights and parameters that promotes the recognition of positive samples. Through the optimization, the cascade AdaBoost classifiers can achieve a low FAR under a high detection rate. Moreover, the dual threshold method was introduced to reduce the number of weak classifiers that constitute each strong classifier, thereby reducing training time and speeding up the detection. Finally, the original weights of samples were multiplied with different weighting coefficients, making abnormal samples less lightly to be selected in the next round of training. The effectiveness of the improved algorithm was fully demonstrated through simulation.

4.1 AdaBoost algorithm

In AdaBoost algorithm, weak classifiers are developed through sample training. Then, the most powerful weak classifiers are selected based on Haar-like eigenvalues, and cascaded into strong classifiers [28, 29]. By classification ability, the strong classifiers are ranked in ascending order (Figure 6).

In actual target detection problems, only a small portion of samples are positive. Under the cascade structure, most samples are filtered out by the classifiers at the front end. Only a few samples can pass through all the classifiers on different stages. Therefore, the cascade structure greatly simplifies the computation, and promotes the efficiency of face detection.

1.6.png

The workflow of AdaBoost algorithm can be described as follows:

Step 1. Input the training set: (x₁, y₁), (x₂, y₂), ..., (x_n, y_n), where $x_{i} \in X, y_{i} \in Y=\{-1,1\}$.

Step 2. Initialize sample weights: w₁(i)=1/n;

Step 3. Iterate t=1, 2, ..., T times and search for T weak classifiers h_t;

(a) For the j-th Haar-like feature of each sample, design a simple classifier h_j:

${{h}_{j}}(x)=\left\{ \begin{matrix}   1 & {{p}_{j}}{{f}_{j}}(x)<{{p}_{j}}{{\delta }_{j}}  \\   0 & \text{ otherwise }  \\\end{matrix} \right.$     (1)

where, f_j(x) is the j-th eigenvalue; δ_j is the treshold; p_j is the bias that determines the sign of the inequality (p_j=+1 or -1). Then, adjsut δ_j and p_j to minimize the weighted error rate ε_j:

${{\varepsilon }_{j}}=\sum\limits_{{{h}_{j}}\left( {{x}_{i}} \right)\ne {{y}_{i}}}{{{\text{w}}_{j}}}(i)$      (2)

(b) Select the smallest ε_t from all ε_j values to serve as the weak classifier h_t of the current iteration.

(c) Solve the weighting coefficient of h_t:

${{\alpha }_{t}}=\frac{1}{2}\ln \left( \frac{1-{{\varepsilon }_{t}}}{{{\varepsilon }_{t}}} \right)$    (3)

(d) Update sample weights:

${{w}_{t+1}}(i)=\frac{{{w}_{t}}(i)\exp \left( -{{\alpha }_{t}}{{y}_{i}}{{h}_{t}}\left( {{x}_{i}} \right) \right)}{{{z}_{t}}}$     (4)

where, Z_t is the normalization factor:

${{Z}_{t}}=\sum\limits_{i}{{{w}_{t}}}(i)\exp \left( -{{\alpha }_{t}}{{y}_{i}}{{h}_{t}}\left( {{x}_{i}} \right) \right)$       (5)

Step 4. Combine weak classifiers into a strong cascade classifier:

$H(x)=\left\{ \begin{matrix}   1 & \sum\limits_{t=1}^{T}{{{\alpha }_{t}}}(i){{h}_{t}}(x)\ge 0.5\sum\limits_{t=1}^{T}{{{\alpha }_{t}}}  \\   0 & \text{ otherwise }  \\\end{matrix} \right.$      (6)

where, $\alpha_{t}=\log \left(\frac{1}{\beta_{t}}\right)$.

4.2 Improved AdaBoost algorithm

4.2.1 Expanded sample library

The detection effect of AdaBoost algorithm hinges on the diversity of training samples [30, 31]. The algorithm will perform poorly in detection, if the type of samples to be detected is not contained in the training set. The larger and more diverse the sample library, the better the training result.

To diversify training samples, this paper adds the translation, rotation and mirror images (Figure 7) of each sample to the sample library. The detection result will be improved, if the expanded library contains the type of samples to be detected. Therefore, the types of training samples were selected depending on those of the images to be detected.

1.7.png

Figure 7. (a) Original image; (b) Translation image; (c) Rotation image; (d) Mirror image

1.8.png

Figure 8. Distribution of face and nonface samples

4.2.2 Improved construction method for weak classifiers

(1) Determining weak classifiers by dual threshold method

In Step 3 of AdaBoost algorithm, a simple classifier h_j (j=1, 2, ..., l) for l features should be solved to build a weak classifier h_t. Each simple classifier h_j needs to search M times, where M is the number of samples. Then, T weak classifiers are needed to form a strong classifier. Suppose l=20,000 and T= 200, and it takes 0.5s to train a simple classifier h_j. Then, the total training lasts 20,000×0.5×200≈555.5h, that is, 23 days.

The accuracy of AdaBoost algorithm is positively correlated with the size and diversity of the training library. Hence, a long training time is necessary to improve the detection accuracy. To shorten the excessively long training time, the original AdaBoost algorithm was improved as follows.

Figure 8 above shows the eigenvalue distribution of face and nonface samples. It can be seen that face and nonface images are distributed unevenly. The face images are at the center, while nonface images are on two sides. In the AdaBoost algorithm, each weak classifier only has a threshold as the upper or lower limit of the eigenvalue. Under the above distribution, dual threshold simple classifier has better classification effect.

Therefore, the dual threshold method was adopted to solve weak classifiers, that is, two thresholds were taken as the upper and lower limits of each weak classifier. Each dual threshold weak classifier is equivalent to two single-threshold weak classifiers. In this way, the number of weak classifiers is reduced, and the training time is shortened.

The specific process is detailed below:

Step 1. Determine the distribution curves of face and nonface images f₁(x) and f₂(x), where x is the eigenvalue.

Step 2. Solve the x_max corresponding to the maximum value of f₁(x)-f₂(x).

Step 3. Search for x₁ and x₂ that make f₁(x)=f₂(x) from x_max to the left and right. If the two values are found, the two thresholds of the weak classifier: δ₁=x₁ and δ₂=x₂; otherwise, take the boundary points as the thresholds.

(2) Optimzing the weighting coefficient formula

In traditional AdaBoost algorithm, the weighting coefficients of weak classifiers are solved based on the upper limit of minimum error rate. If the FRR is low, the algorithm cannot achieve a good performance. Therefore, the weighting coefficient formula is optimized in this research.

The weighting coefficients of weak classifiers should not be optimized solely based on error rate. Since AdaBoost mainly recognizes the classes of samples, the recognition ability of positive samples and the reliability of weak classifiers should also be considered to combine weak classifiers into strong classifiers. The reliability equals the recognition rate divided by acceptance rate. Taking these two factors into account, the weighting coefficients can be solved by:

${{\alpha }_{t}}=\frac{1}{2}\ln \left( \frac{1-{{\varepsilon }_{t}}}{{{\varepsilon }_{t}}} \right)+k\cdot \frac{\left( 1-{{\varepsilon }_{t}} \right)}{\rho }\cdot \left( 1-{{\varepsilon }_{t}} \right)$     (7)

where, k is a constant that lowers the upper limit of the minimum error rate in the t-th iteration (multiple tests have shown that k=1/120 brings the best detection effect); ρ is the acceptance rate of positive samples ($\rho=\frac{N_{c p}}{N_{p}+N_{n}}$, where N_cp is the number of correctly classified positive samples; N_p and N_n are the number of positive and negative samples in the sample set, respectively). When the error rate remains the same, the weak classifiers with stronger recognition ability of positive samples and higher reliability should be assigned a higher weight.

The following proves that the optimized weighting coefficient formula can improve the H(x_i) value distirbution of samples, and thus promote the performance of the weak classifiers.

Assuming that $\gamma=\frac{\left(1-\varepsilon_{t}\right)^{2}}{\rho}$, the weighted sum of H(x_i) corresponding to sample x_i can be obtained as:

$\begin{align}  & H\left( {{x}_{\text{i}}} \right)=\sum\limits_{t}{{{\alpha }_{t}}}{{h}_{t}}\left( {{x}_{i}} \right)=\sum\limits_{t}{\left[ \frac{1}{2}\ln \left( \frac{1-{{\varepsilon }_{t}}}{{{\varepsilon }_{t}}} \right)+\gamma  \right]}{{h}_{t}}\left( {{x}_{i}} \right) \\ & =\sum\limits_{t}{\frac{1}{2}}{{h}_{t}}\left( {{x}_{i}} \right)\ln \left( \frac{1-{{\varepsilon }_{t}}}{{{\varepsilon }_{t}}} \right)+\sum\limits_{t}{\gamma }{{h}_{t}}\left( {{x}_{i}} \right) \\\end{align}$     (8)

The first term on the right side of formula (8) is the same as the traditional AdaBoost algorithm. Thus, the following focuses on the second term on that side. Assuming that $H_{\Delta}\left(x_{\mathrm{i}}\right)=\sum_{t} \gamma h_{t}\left(x_{i}\right)$, the positive samples satisfy:

$\sum\limits_{{{y}_{i}}=1}{{{H}_{\Delta }}}\left( {{x}_{i}} \right)=\sum\limits_{{{y}_{i}}=1}{\gamma }\sum\limits_{t}{{{h}_{t}}}\left( {{x}_{i}} \right)$     (9)

The corresponding negative samples satisfy:

$\sum\limits_{{{y}_{i}}=-1}{{{H}_{\Delta }}}\left( {{x}_{i}} \right)=\sum\limits_{{{y}_{i}}=-1}{\gamma }\sum\limits_{t}{{{h}_{t}}}\left( {{x}_{i}} \right)$     (10)

Let (N_p+N_n)ρ and N_p-(N_p+N_n)ρ be the number of positive samples correctly and incorrectly recognized in the t-th iteration, respectively. Then, we have:

$\sum_{y_{i}=1} h_{t}\left(x_{i}\right)$$=\left(N_{p}+N_{n}\right) \rho \cdot 1+\left[N_{p}-\left(N_{p}+N_{n}\right) \rho\right] \cdot(-1)$$=2\left(N_{p}+N_{n}\right) \rho-N_{p}$     (11)

Substituting formula (11) into formula (9), we have:

$\begin{align}  & \sum\limits_{{{y}_{i}}=1}{{{H}_{\Delta }}}\left( {{x}_{i}} \right)=\sum\limits_{t}{\gamma }\sum\limits_{{{y}_{i}}=1}{{{h}_{t}}}\left( {{x}_{i}} \right) \\ & =\sum\limits_{t}{\gamma }\left[ 2\left( {{N}_{p}}+{{N}_{n}} \right)\rho -{{N}_{p}} \right] \\\end{align}$    (12)

Let $\left(N_{p}+N_{n}\right) \cdot \varepsilon_{t}$ be the total number of samples incorrectly recognized by the t-th weak classifier. Then, the number of incorrectly recognized samples can be expressed as $\left(N_{p}+N_{n}\right) \cdot \varepsilon_{t}-\left[N_{p}-\left(N_{p}+N_{n}\right) \rho\right] .$ Hence, the number of incorrectly recognized negative samples can be obtained as: $N_{n}-\left\{\left(N_{p}+N_{n}\right) \cdot \varepsilon_{t}-\left[N_{p}-\left(N_{p}+N_{n}\right) \rho\right]\right\} .$ Then, we have:

$\begin{align}   & \sum\limits_{{{y}_{i}}=-1}{{{h}_{t}}}\left( {{x}_{i}} \right) \\  & =\left\{ {{N}_{n}}-\left[ \left( {{N}_{p}}+{{N}_{n}} \right)\cdot {{\varepsilon }_{t}}-\left[ {{N}_{p}}-\left( {{N}_{p}}+{{N}_{n}} \right)\rho  \right] \right] \right\}\cdot (-1) \\  & +\left\{ \left( {{N}_{p}}+{{N}_{n}} \right)\cdot {{\varepsilon }_{t}}-\left[ {{N}_{p}}-\left( {{N}_{p}} \right) \right. \right.\left. \left. \left. +{{N}_{n}} \right)\rho  \right] \right\}\cdot 1 \\ & =2\left( {{N}_{p}}+{{N}_{n}} \right)\cdot {{\varepsilon }_{t}}+2\left( {{N}_{p}}+{{N}_{n}} \right)\rho -\left( 2{{N}_{p}}+{{N}_{n}} \right) \\\end{align}$      (13)

If ε_t<0.5 during the training, the following can be derived from formula (13):

$\begin{align}  & \sum\limits_{{{y}_{i}}=-1}{{{h}_{t}}}\left( {{x}_{i}} \right) \\ & <2\cdot \left( {{N}_{p}}+{{N}_{n}} \right)\cdot 0.5+2\left( {{N}_{p}}+{{N}_{n}} \right)\rho -\left( 2{{N}_{p}} \right.\left. +{{N}_{n}} \right) \\ & ={{N}_{p}}+{{N}_{n}}-2{{N}_{p}}-{{N}_{n}}+2\left( {{N}_{p}}+{{N}_{n}} \right)\rho  \\ & =2\left( {{N}_{p}}+{{N}_{n}} \right)\rho -{{N}_{p}} \\\end{align}$       (14)

From formulas (10), (12), and (14), we have:

$\begin{align}  & \sum\limits_{{{y}_{i}}=1}{{{H}_{\Delta }}}\left( {{x}_{i}} \right)=\sum\limits_{t}{\gamma }\sum\limits_{{{y}_{i}}=-1}{{{h}_{t}}}\left( {{x}_{i}} \right) \\ & <\sum\limits_{t}{\gamma }\left[ 2\left( {{N}_{p}}+{{N}_{n}} \right)\rho -{{N}_{p}} \right]=\sum\limits_{{{y}_{i}}=1}{{{H}_{\Delta }}}\left( {{x}_{i}} \right) \\\end{align}$       (15)

The above theoretical analysis proves that the optimized weighting coefficient formula meets the detection requirements. By extending the distribution of positive and negative samples to both sides, the trained classifiers can realize a lower FAR, when the FRR is fixed. Under a constant error rate, the classifiers with a stronger ability to recognize positive samples are given greater weighting coefficeints, further improving the face detection rate of the classifiers.

(3) Updating sample weights with two thresholds

The sample weight update formula (4) was improved as follows:

${{w}_{t+1}}(i)=\left\{ \begin{matrix}   \frac{{{w}_{t}}(i)\exp \left( -{{\alpha }_{t}}{{y}_{i}}{{h}_{t}}\left( {{x}_{i}} \right) \right)}{{{Z}_{t}}},{{e}_{t}}(i)\le {{\varepsilon }_{t}}  \\    {{\beta }_{1}}\times \frac{{{w}_{t}}(i)\exp \left( -{{\alpha }_{t}}{{y}_{i}}{{h}_{t}}\left( {{x}_{i}} \right) \right)}{{{z}_{t}}},{{\varepsilon }_{t}}<{{e}_{t}}(i)\le 2{{\varepsilon }_{t}}  \\    {{\beta }_{2}}\times \frac{{{w}_{t}}(i)\exp \left( -{{\alpha }_{t}}{{y}_{i}}{{h}_{t}}\left( {{x}_{i}} \right) \right)}{{{z}_{t}}},{{e}_{t}}(i)>2{{\varepsilon }_{t}}  \\\end{matrix} \right.$      (16)

where, β₁ and β₂ are two weight adjustment factors; e_t(i) is the relative error of a weak classifier:

${{e}_{t}}(i)=\left| \frac{{{h}_{t}}\left( {{x}_{i}} \right)-{{y}_{i}}}{{{y}_{i}}} \right|,i=1,2,3,\cdots n$      (17)

If the relative error e_t(i) of training samples is more than twice the weighted error rate, the samples must contain a gross error. These samples should be given a smaller weight, making them less likely to be selected to train weak classifiers in the next round. Hence, the weights of such samples should be multiplied by a smaller-than-one adjustment factor β₂=0.78.

If the relative error e_t(i) of training samples is less than twice the weighted error rate, the samples must contain a large stochastic error. These samples should be given a larger weight, making them more likely to be selected to train weak classifiers in the next round. Hence, the weights of such samples should be multiplied by a greater-than-one adjustment factor β₁=1.1.

The weight update limits the weight divergence of weak classifiers, thereby improving the accuracy of face detection.

(4) Implementing the improved AdaBoost algorithm

The improvement mainly focuses on Step 3 on the traditional algorithm. Steps 1, 2, and 3 are the same as the traditional steps. The improved version of Step 3 is detailed below:

Step 3. Iterate t=1, 2, ..., T times and search for T weak classifiers h_t;

(a) For the j-th Haar-like feature of each sample, design a simple classifier h_j through training by dual threshold method, that is, find the thresholds δ₁ and δ₂ that minimize weighted error rate \varepsilon_{j}=\sum_{h_{j}\left(x_{i}\right) \neq y_{i}} \mathrm{w}_{t}(j), and compute the relative absolute error of weak classifiers e_j(i):

${{h}_{j}}(x)=\left\{ \begin{matrix}   1 & {{\delta }_{1}}<{{f}_{j}}(x)<{{\delta }_{2}}  \\   0 & \text{ otherwise }  \\ \end{matrix} \right.$    (18)

(b) Select the smallest ε_t from all ε_j values to serve as the weak classifier h_t of the current iteration.

(c) Solve the weighting coefficient of h_t by formula (7).

(d) Update sample weights by formula (16).

This paper designs and verifies an improved AdaBoost algorithm for face detection. Firstly, the original image quality was improved through light treatment and noise removal, and the training set was expanded to enhance detection accuracy. Next, the dual threshold method was introduced to reduce the number of searches, which indirectly shortens the training time and improves the detection speed. After that, the weighting coefficient formula was optimized, ensuring that the classifiers can achieve a low FAR under a high detection rate. Finally, the sample weights were updated with two thresholds. The improved algorithm requires a much shorter training time than the traditional AdaBoost algorithm, especially when there are lots of training samples. Simulation results show that our algorithm greatly improves the training speed and detection effect of the traditional algorithm. The future research will extend the algorithm to multi-class object detection, and further improve the training speed and detection accuracy of the algorithm.