In this paper, we propose a novel face detection method based on the MAFIA algorithm. Our proposed method consists of two phases, namely, training and detection. In the training phase, we first apply Sobel's edge detection operator, morphological operator, and thresholding to each training image, and transform it into an edge image. Next, we use the MAFIA algorithm to mine the maximal frequent patterns from those edge images and obtain the positive feature pattern. Similarly, we can obtain the negative feature pattern from the complements of edge images. Based on the feature patterns mined, we construct a face detector to prune non-face candidates. In the detection phase, we apply a sliding window to the testing image in different scales. For each sliding window, if the slide window passes the face detector, it is considered as a human face. The proposed method can automatically find the feature patterns that capture most of facial features. By using the feature patterns to construct a face detector, the proposed method is robust to races, illumination, and facial expressions. The experimental results show that the proposed method has outstanding performance in the MIT-CMU dataset and comparable performance in the BioID dataset in terms of false positive and detection rate.
Face detection is a fundamental problem in many computer vision applications. It can be used to locate a face, and as a front–end for applications such as face recognition system, surveillance and security system, human computer interaction (HCI) system, etc. Face is a highly non-rigid object. The challenge of detecting human faces from an image mostly comes from the variation of human faces such as races, illumination, facial expressions, face scales, head poses (off-plane rotations), face tilting (in-plane rotations), occlusions, etc. Also, environment issues such as lighting conditions, image quality, and cluttered backgrounds may cause great difficulties.
Many face detection methods have been proposed. These methods can be classified into three categories [1]: knowledge-based and feature invariant methods, template matching methods, and appearance-based methods.
The knowledge-based and feature invariant methods locate the features of a face such as eyes, nose, mouth, or even skin color, and then group them together by considering their geometrical relationships [2], [3] and [4]. Bhuiyan et al. [5] proposed a method to convert pixels in color images from the RGB model to the YIQ model to find skin colors and group them into skin regions. Chiang et al. [3] presented a model to convert pixels from the RGB model to the r–g plane and find skin and lip colors in an image between two parabolas on that plane. Once the skin regions are located in an image, facial components or features like eyes, eyebrows, nose or mouth can be detected within these skin regions. A skin region with proper facial components is reported as a face candidate. Lee et al. [6] used the directional template and blob map to locate major facial features, i.e., two eyes and a mouth. Usually, a verification process such as facial components’ geometrical relations is needed to reduce false positives [7]. One major problem about knowledge-based and feature invariant methods is that it is hard to translate human knowledge into well-defined rules. If the rules are too strict, they may fail to detect human faces. On the other hand, if the rules are too general, they may result in too many false positives.
Template matching methods aim to find face features that exist even when the pose or lighting conditions are varying [1]. Usually, a standard face template (pattern) is manually predefined or constructed by a function. The existence of a face is determined based on the similarity or correlation between the input image and the standard face pattern in terms of eyes, nose, mouth, and face contour. Silhouettes have also been used as templates for locating face candidates [8]. Bhuiyan et al. [5] formed the template of a face image, which is obtained from averaging the gradation levels of pixels of face samples. The template face image is then shifted through the whole image to find the location with the most suitable matches. Jesorsky et al. [9] used a face template to roughly locate a face candidate. Then an eye template is exploited to verify the located face candidates. One disadvantage of template matching methods is that it is not easy to obtain a good template from training face images. Another disadvantage is that it is difficult to enumerate templates for different poses.
In contrast to template matching methods, appearance-based methods learn templates from training samples (faces and non-faces) instead of learning from experts; therefore the training process is usually time-consuming. However the detection speed of these methods is usually fast, sometimes even real-time. This category of methods includes statistical methods [10], neural networks [11], [12] and [13], support vector machines (SVM) [14], [15] and [16], and multiple classifier combination [17], [18] and [19].
Shih and Liu [15] proposed the DFA-SVM method which integrates the discriminating feature analysis, distribution-based face class modeling, and SVM. Heisele et al. [16] built a 5-level hierarchy of SVM classifiers with lower level classifiers rejecting most parts of the background, and the upper level classifiers performed the detailed detection. Then, PCA is applied to the top-level classifier to choose relevant image features. With the combination of a hierarchy of SVM classifiers and feature reduction, the detection process is speeded up in comparison with similar classification methods [20].
Viola and Jones [17] proposed an object detection scheme, which is fast enough for real-time applications and can be effectively applied to face detection. This is accomplished by the integration of a new image representation called integral image, a learning algorithm based on AdaBoost [21], and a cascade scheme is to combine the boosted classifiers. Roth et al. [22] proposed a method, called SNoW, for detecting faces with different features, expressions, and poses under different lighting conditions. Nilsson et al. [23] proposed an extended version of the SNoW classifier by a split-up process. One of the drawbacks of the SNoW-based methods is that they require a large number of face and non-face patches. Cristinacce and Cootes [24] used a joint shape and texture appearance model to generate a set of region template detectors, where a face is detected by aggregating the responses of these detectors.
One problem of the appearance-based methods is that it needs a lot of positive and negative training examples, and the learning process is very time-consuming. Another problem is that the learned result is hard to interpret, thus is difficult to be adjusted to fit various applications.
Of the three categories of methods mentioned above, the disadvantages of these methods are (1) the knowledge and the relation of the features is hard to define, (2) the training process of the appearance-based methods is time-consuming, or (3) a good template is hard to obtain.
Therefore, in this paper, we propose a data mining approach to obtain the features patterns of human faces automatically and efficiently. We first apply Sobel's edge detection operator, morphological operator, and thresholding to each training image, and transform it into an edge image. Next, we use the MAFIA [25] algorithm to mine the maximal frequent patterns from those edge images and obtain the positive feature pattern. Similarly, we can obtain the negative feature pattern from the non-edge images, each of which is a complement of an edge image. Based on the positive and negative feature patterns mined, we construct a face detector containing three cascaded classifiers to prune non-face candidates. That is, we not only focus on the traditional facial feature patterns like eyes or mouth, which are called positive feature pattern, but also focus on the facial regions that do not contain any facial feature patterns like cheeks, which are called negative feature pattern.
Unlike knowledge-based and feature invariant methods, our proposed method can find the feature patterns automatically. Moreover, by using both the positive and negative feature patterns to construct a face detector, our proposed method is robust to races, illumination, and facial expressions.
The rest of the paper is organized as follows. The preliminary concept and problem definitions are described in Section 2. Our proposed method is presented in detail in Section 3. The performance analysis is shown in Section 4. Finally, the conclusions and future work are discussed in Section 5.
We proposed a novel face detection method by integrating the maximal frequent pattern algorithm. An edge image of facial features is derived by applying Sobel's edge detection operator, morphological operator, and thresholding. We use the MAFIA algorithm to mine the maximal frequent patterns from edge and non-edge images of human faces and obtain the positive and negative feature patterns. Based on the positive and negative feature patterns mined, we construct a face detector containing three cascaded classifiers to prune non-face candidates. In the detection phase, we apply a window to slide across a testing image in different scales. For each sliding window, we input it to the variance, face feature, and kd-tree-based SVM classifiers. If the sliding window passes these three classifiers, it is considered as a human face.
Since the proposed method not only utilizes the positive feature pattern but also the negative feature pattern, it can capture most of features in a human face. The facial patterns of human faces in terms of edges do not change much in various conditions. Thus, the proposed method is robust to races, illumination, and facial expressions.
The experimental results show that the proposed method has outstanding performance in the MIT-CMU dataset and comparable performance in the BioID dataset in terms of both false positive and detection rate. Besides the better performance, one advantage of the proposed method is that unlike knowledge-based methods, we can obtain the feature patterns without requiring any prior knowledge. We can efficiently obtain the positive and negative feature pattern from the training images using the MAFIA algorithm. Compared to the appearance-based methods, the proposed method does not need a lot of positive and negative training examples and takes very little training time to generate the feature patterns. Furthermore, the feature patterns mined are interpretable. We can relate each part of the feature patterns to the facial components like eyebrows, eyes, nose, mouth, or cheeks. Thus, we can easily modify the feature patterns to fit different applications.
The positive and negative feature patterns are important features to face detection. However, it has some limitations. First, if an image is too blurred or lack of important facial features, we may not be able to extract the features to detect faces. Another limitation is that the feature patterns may change if the poses of faces are largely changed. In the future, we will extend the proposed method to use not only facial components in terms of edges but other information to detect or recognize human faces. Also, we will extend our proposed method to handle rotated faces. Finally, by replacing the training images, we can obtain the maximal frequent patterns of other kinds of objects and then detect them.
