Subscribe Now Subscribe Today
Research Article

Face Detection Based on Graph Structure and Neural Networks

H.K. Bashier, E. Abdu Abusham and F. Khalid
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Face detection plays an important role in many applications such as face recognition, face image database and video surveillance. In this study a novel face detection algorithm has been introduced with accurate results. The method is based on the idea of Local Graph Structure (LGS) and neural network. LGS features are derived from a general definition of texture in a local graph neighbourhood. The features are based on dominating set of pixels on certain sub-graph of the image, once the features are extracted then neural network is applied as a classifier. The experiments results on CBL face database images demonstrated the effectiveness of the proposed method.

Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

H.K. Bashier, E. Abdu Abusham and F. Khalid, 2012. Face Detection Based on Graph Structure and Neural Networks. Trends in Applied Sciences Research, 7: 683-691.

DOI: 10.3923/tasr.2012.683.691

Received: November 05, 2011; Accepted: June 22, 2012; Published: July 24, 2012


Detection of faces considered one of the visual tasks for human, human beings can detect face effortlessly. Face detection is essential step towards many sophisticated biometrics recognition, multimedia and computer vision applications. The challenging difficulty of face detection as it needs to account for all possible appearance variation caused by change in occlusions, illumination, facial features, etc. In addition, it has to detect faces that appear at different scale, pose and localize an unknown number of faces from given a still or video image. Regardless of all these difficulties, remarkable advancement has been made in the last decade and many systems have revealed inspiring real-time performance. The current advances of these algorithms have also made considerable contributions in detecting other objects such as cars and humans movement. The problems of face detection require to know about the information impeded in the face itself and the way this information is exploited differs and can be categorized into two main categories the first is features-based, which attempt to extract features of the image and match it against the information of the face features, the other category is image-based or view-based which works directly with the image as a two dimensional array of intensity values and attempts to classify the input windows into two classes, a face or none face class, this category implicitly extract and learns the features from the training set without explicitly identifying the features and their relation to each other, this categorization also applies for general object classification (Yang, 2004). In general, the classification of single image detection methods fall into four categories; some methods obviously have common characteristics are discussed:

Knowledge-based methods: These methods aim to find the general knowledge from the typical face image; it takes in the consideration the relationship of the general facial feature
Feature invariant approaches: Feature invariant approaches consider the local structure of the face which is the potential feature this feature does not affect with illumination, pose and angle
Template matching methods: The template matching method is used for face detection and localization (Wang and Li, 2011), therefore a series number of face patterns are stored so that later for face detection process these patterns are used to do the matching while using the correlation or Euclidean distance, these patterns serve as templates for matching, Another research is carried to use to template matching for face recognition (Park and Park, 2006)
Appearance-based methods: The appearance-based methods are almost similar to template matching, the only difference is that the appearance-based method is used the training images to extract the features and then these features are learned by any machine learning such as Adaptive Boosting (AdaBoost)-learning; hence these learned features are then used for the detection


This section illustrate how face detection done for the above methods. Knowledge-based there’s (Multiresolution rule-based method (Yang and Huang, 1994). In Feature invariant there were some works been don such as in facial features (Grouping of edges (Kirby and Sirovich, 1990; Yow and Cipolla, 2005), texture (Space Gray Level Dependence (SGLD) matrix of face pattern (Dai and Nakano, 1996), skin color (Mixture of Gaussian) (Yang and Waibel, 1996; Mckenna et al., 1998) and multiple features (integrated of skin color size and shape (Kjeldsen and Kender, 1996). Template matching is one of the popular approaches in face detection, in this approach there are two ways the first one is predefined face template as it uses shape template (Craw et al., 1992) secondly there’s Deformable templates as there was work which is Active Shape Model (ASM) (Lanitis et al., 1995). There’s also appearance-based method where there were a lot of work been done for instance in eigenface there was eigenvector decomposition and clustering (Turk and Pentland, 1991a), distribution-based Gaussian distribution and multilayer perception (Sung and Poggio, 1998), machine learning approaches are also been used in Ensemble of neural networks and arbitration schemes (Rowley et al., 1998), SVM with polynomial kernel (Osuna et al., 1997), joint statistics of local appearance and position (Schneiderman and Kanade, 1998), Higher order with Hidden Markov Model (HMM) (Rajagopalan et al., 1998) and Kullback relative information (Lew, 2002; Colmenarez and Huang, 1997) which it uses information theoretical approach. Some other detection methods had indeed been shown in several papers (Pakazad et al., 2011; Park and Park, 2006).

Appearance-based methods: As it has been stated above, there are a series of problems that we encounter such as pose, angle, illumination and etc so these unpredictable backgrounds give an attention to face detection in facial features.

Hence, the need to handle the problem of detecting faces in several images considering the mess background. From this point of view there’s a new research area that need to be discussed which is treating the face detection as a pattern recognition problem due to the fact that face detection need to solve the problem of illumination, pose, angle, detection of several faces in mess backgrounds and etc., which these problem lead to say that in order to solve them there’s a need to get the pattern such as the local feature or etc. This eradicates the possible of modeling error due to partial or incorrect face knowledge. The basic approach in processing face detection is via training images where there’s a 2D array which used to store two type of classes, the first class is a face class which contains a series of face features that is used to detect whether the detected region is a face or not and the second class is contains the features of non-face which is stored in this 2D array as well, then the correlation coefficient or Euclidean distance is used to calculate the distance of the input image to classify whether it falls in the face class or in the non-face class.

Image based approach is used where there’s a need for Appearance-based method such as Eigenface and etc., this approach is based on template matching (Liu and Wang, 2000), due to the fact that this algorithm uses a wind scanning method since it requires the detection of face region inside the input image, but there are variation of implanting this algorithm in almost all image-based systems. In the following sections the image-based approaches have been divided into three classes, linear subspace methods, neural networks and statistical approaches. In each division a brief description is highlighted and followed by our proposed method.

Linear subspace methods: Human faces images lie in a subspace of the overall image space. To represent the subspace of images, several approaches can be used. Neural approaches such as Artificial Neural Networks (ANN) but there are also quite a lot of techniques more very much related to standard multivariate statistical analysis which can be applied. In this part we explain some of these techniques, including Linear Discriminant Analysis (LDA), Principal Component Analysis (PCA) and Factor Analysis (FA). Sirovich and Kirby (1987) developed a technique using principal component analysis to efficiently of faces, represented in terms of eigenvectors (covariance matrix of the distribution). Each subject face in the face set can then be approximated by a linear combination of the largest eigenvectors, which commonly referred to as eigenfaces, using appropriate weights. Turk and Pentland (1991b) later developed this technique for face recognition. Their method based on nature of the weights of eigenfaces exploits the distinct nature of the weights of eigenfaces in individual face representation. Since the face reconstruction by its principal components is an approximation, a residual error is defined in the algorithm as a preliminary measure of “faceness.” This residual error which they termed “distance-from-face-space” (DFFS) gives a good indication of face existence through the observation of global minima in the distance map. Represent human faces. By given a set of different face images, the first step in the method is to find the principal components of the distribution. Some other methods had indeed been shown in several papers (Khan et al., 2004; Abusham and Kiong, 2009; Krishnamoorthy and Bhavani, 2007; Wang and Zhang, 2011; Wang and Li, 2011; Li et al., 2011; Wakaf and Saii, 2009).

Neural networks: Neural networks have turn out to be a popular method for pattern recognition problems, such as face detection. Neural networks today are much more than just the simple multilayer perceptron. The wide spread use of neural networks in pattern recognition where it has been use in committee-ensemble classification, complex learning algorithms, modular architectures, auto associative and compression networks. For face recognition, it states that the neural approaches can be applied for all parts of the system and this had indeed been shown in several papers (Turk and Pentland, 1991b; Lin et al., 1997; Samal and Iyengar, 1992).

Statistical approaches: Apart from neural networks and linear subspace methods, there are also a number of statistical techniques that are used for face detection. Such as face detection based on support vector machine, information theory and Bayes’ decision rule. Based on an earlier work of maximum likelihood face detection, Colmenarez and Huang (1997, 2002), proposed a new system based on Kullback relative information (Kullback divergence). Face images from the training data set of each class are analysed as observations of a random process and are characterized by two probability functions. Two popular methods among these techniques are Local Binary Pattern (LBP) and Gabor wavelets.


The idea of Local Graph Structure (LGS) comes from a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge. The domination number γ (G) is the number of vertices in a smallest dominating set for G.

LGS works with the six neighbours of a pixel, by choosing the target pixel C as a threshold, then we start by moving anti clockwise at the left region of the target pixel C, If a neighbour pixel has a higher gray value than the target pixel (or the same gray value) then assign a binary value equal to 1 on the edge connecting the two vertices, else we assign a value equal to 0. After finish on the left region of graph we stop at the target pixel C and then we move in a horizontal way (clockwise) to the right region of the graph and we apply the same process till we get back to the target pixel C (Fig. 1).

To produce the LGS for pixel (xd, yd) a binomial weight 2p is assigned to each sign s(gd-gn). These binomial weights are summed:

Image for - Face Detection Based on Graph Structure and Neural Networks


Image for - Face Detection Based on Graph Structure and Neural Networks

where, p = 7. p = 7, 6,..., 0.

Image for - Face Detection Based on Graph Structure and Neural Networks
Fig. 1(a-b): Local graph structure with (a) Direction and (b) Binary symbols


The scaled conjugate gradient algorithm is based on conjugate directions is used. The algorithm combines the model-trust region approach, with the conjugate gradient approach. We considered a network with a 3 layers, the input layer is a vector constituted by 256 units of neurons (nxn pixel input images). The hidden layer has 80 neurons and the output layer is a single neuron which is active to 1 if the face is presented and to 0 otherwise.


Figure 2 illustrates the block diagram of the proposed method. Before the image is passed to the system for classification; the image is pre-processed to remove unwanted noise from lighting and the environment using Local Graph Structure (LGS). The scaled conjugate gradient network decides whether the image belongs to the face or non face class based on information learned from during training as in Fig. 3 shows the histogram for face images. The output indicates whether the original input image is thought to contain a face or not.


The proposed method has been proved to be useful in image processing and pattern recognition tasks. The method works as follow; a decimal representation of the image is obtained by taking the binary sequence as a binary number between 0 and 255. To calculate decimal representation of pixels, LGS not only accounts for its relative relationship with its neighbours but also with the relationship between the pixels that form the local graph of the target pixel C , while discarding the information of amplitude and this makes the resulting LGS values very insensitive to illumination intensities. The 8-bit binary series with binomial weights consequently result in 256 different patterns in total for the pixel representation. A new generated image from original image Fig. 2 using LGS, a histogram of the LGSs for original image is calculated. Histogram of LGSs image representing the distribution of 256 patterns across the face image. The advantage of LGS; Firstly it is a local measure, so LGS in a certain region will not be affected by the illumination conditions in other regions.

Image for - Face Detection Based on Graph Structure and Neural Networks
Fig. 2: Block diagram

Table 1: Training rate of proposed method
Image for - Face Detection Based on Graph Structure and Neural Networks

Table 2: Accuracy rate of proposed method
Image for - Face Detection Based on Graph Structure and Neural Networks

Image for - Face Detection Based on Graph Structure and Neural Networks
Fig. 3: Face histograms

Secondly it is a relative measure and is invariant to any monotonic transformation such as shifting, scaling or logarithm of the pixel-values. Therefore it can be invariant to a certain range of illumination changes.

To assess the performance of the proposed method on face detection CBCL Face Database [27] was used. The dataset consists of 6228 images divided into three sets, training (90%), testing (5%) and validation (5%). LGS was applied to find the histograms for the entire training and testing set (Fig. 3), the histograms of processed images were fed to the neural network as input and Table 1 illustrate the result of training rate obtained by the proposed method.

Mean Square Error (MSE) is the average error squared difference between outputs and target. Lower values are better and zero means no error. %E is percent error indicates the fraction of samples which are misclassified. A value of 0 means no misclassification, 100 indicates maximum misclassifications. The accuracy rate of the experiments is shown in Table 2 and Fig. 4.

Image for - Face Detection Based on Graph Structure and Neural Networks
Fig. 4(a-d): Illustration of ROC for the accuracy of the algorithm, (a) Traning ROC, (b) Validation ROC, (c) Test ROC and (d) All ROC

We believe that the main explanation for the better performance of the proposed method over other techniques, it takes in consideration the relationship between the pixels that form the local graph of the target pixel C and consideration tolerance to monotonic gray-scale changes in the images. Additional advantage of the proposed method is the computational efficiency, beside simplicity the method is quit fast so that it can be easily applied in many fields, such as image processing, pattern recognition, medical image as pre-processing step.


This study presents a novel and efficient algorithm for face detection based on Local Graph Structure (LGS) and neural network. The features of local graph structure are derived from a general definition of texture in a local graph neighbourhood. The advantages of our method over other methods it’s invariant to illumination changes, computational efficiency and fast so that it can be easily applied in real-time system. The method assigns weight for target pixels by considering not only the relationship of one pixel to its neighbours but also the relationship between the pixels that form the local graph of the target pixel, this feature is unique to the proposed method and lead to improve the image appearance and subsequently the recognition performance.


The authors thank the MIT Center for Biological and Computation Learning for using their CBCL Face Database.


1:  Colmenarez, A. and T. Huang, 2002. Maximum likelihood face detection. Proceedings of the 2nd International Conference on Automatic Face and Gesture Recognition, October 14-16, 2002, Killington, VT, USA, pp: 307-311
CrossRef  |  

2:  Rajagopalan, A.N., K.S. Kumar, J. Karlekar, R. Manivasakan and M.M. Patil, 1998. Finding faces in photographs. Proceedings of the 6th International Conference on Computer Vision, January 4-7, 1998, Bombay, India, pp: 640-645
CrossRef  |  

3:  Lanitis, A., C.J. Taylor and T.F. Cootes, 1995. An automatic face identification system using flexible appearance models. Image Vision Comput., 13: 393-401.
CrossRef  |  

4:  Samal, A. and P.A. Iyengar, 1992. Automatic recognition and analysis of human faces and facial expressions: A survey. Pattern Recog., 25: 65-77.

5:  Colmenarez, A.J. and T.S. Huang, 1997. Face detection with information-based maximum discrimination. Proceedings of the Conference Computer Vision Pattern Recognition, June 17-19, 1997, San Juan, Puerto Rico, pp: 782-787
CrossRef  |  

6:  Park, C.W. and M. Park, 2006. Fast template-based face detection algorithm using quad-tree template. J. Applied Sci., 6: 795-799.
CrossRef  |  Direct Link  |  

7:  Osuna, E., R. Freund and F. Girosit, 1997. Training support vector machines: An application to face detection. Proceedings of the Computer Society Conference on Computer Vision and Pattern Recognition, June 17-19, 1997, San Juan, Puerto Rico, pp: 130-136
CrossRef  |  

8:  Abusham, E.E.A.A. and W.E. Kiong, 2009. Non-linear principal component embedding for face recognition. J. Applied Sci., 9: 2625-2629.
CrossRef  |  Direct Link  |  

9:  Yang, G.Z. and T.S. Huang, 1994. Human face detection in a complex background. Patten Recog., 27: 53-63.
Direct Link  |  

10:  Wang, G. and W. Zhang, 2011. Neighborhood preserving fisher discriminant analysis. Inform. Technol. J., 10: 2464-2469.
CrossRef  |  Direct Link  |  

11:  Rowley, H.A., S. Baluja and T. Kanade, 1998. Neural network-based face detection. Pattern Anal. Mach. Intell., 20: 23-28.
CrossRef  |  

12:  Schneiderman, H. and T. Kanade, 1998. Probabilistic modeling of local appearance and spatial relationships for object recognition. Proceedings of the Conference Computer Vision and Pattern Recognition, July 1998, IEEE Computer Society, pp: 45-51
CrossRef  |  

13:  Craw, I., D. Tock and A. Bennett, 1992. Finding face features. Comput. Vision, 588: 92-96.
CrossRef  |  

14:  Yang, J. and A. Waibel, 1996. A real-time face tracker. Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision, December 2-4, 1996, Sarasota, FL , USA., pp: 142-147
CrossRef  |  

15:  Yow, K.C. and R. Cipolla, 1997. Feature-based human face detection. Image Vision Comput., 15: 713-735.
CrossRef  |  

16:  Sung, K.K. and T. Poggio, 1998. Example-based learning for view-based human face detection. IEEE Trans. Pattern Anal. Mach. Intell., 20: 39-50.
Direct Link  |  

17:  Sirovich, L. and M. Kirby, 1987. Low-dimensional procedure for the characterization of human faces. J. Opt. Soc. Am. A, 4: 519-524.
CrossRef  |  Direct Link  |  

18:  Yang, M.H., 2004. Recent advances in face detection. IEEE ICPR Tutorial, Cambridge, United Kingdom.

19:  Kirby, M. and L. Sirovich, 1990. Application of the Karhunen-Loeve procedure for the characterization of human faces. IEEE Trans. Pattern Anal. Mach. Intell., 12: 103-108.
CrossRef  |  Direct Link  |  

20:  Turk, M. and A. Pentland, 1991. Eigenfaces for recognition. J. Cognit. Neurosci., 3: 71-86.
CrossRef  |  Direct Link  |  

21:  Lew, M.S., 2002. Information theoretic view-based and modular face detection. Proceedings of the Second International Conference on Automatic Face and Gesture Recognition, October 14-16, 1996, Killington, VT, USA, pp: 198-203
CrossRef  |  

22:  Turk, M.A. and A.P. Pentland, 1991. Face recognition using eigenfaces. Proceedings of the Computer Society Conference on Computer Vision and Pattern Recognition, June 3-6, 1991, Maui, HI., USA., pp: 586-591
CrossRef  |  Direct Link  |  

23:  Khan, M.A.U., M.K. Khan, M.A. Khan, M.T. Ibrahim, M.K. Ahmed and J.A. Baig, 2004. Principal component analysis of directional images for face recognition. Inform. Technol. J., 3: 290-295.
CrossRef  |  Direct Link  |  

24:  Krishnamoorthy, R. and R. Bhavani, 2007. Face recognition system based on orthogonal polynomials. J. Applied Sci., 7: 109-114.
CrossRef  |  Direct Link  |  

25:  Kjeldsen, R. and J. Kender, 1996. Finding skin in color images. Proceedings of the 2nd International Conference on Automatic Face and Gesture Recognition, October 14-16, 1996, Killington, VT, USA, pp: 312-317
CrossRef  |  

26:  Lin, S.H., S.Y. Kung and L.J. Lin, 1997. Face recognition/detection by probabilistic decision-based neural network. Neural Networks, 8: 114-132.
CrossRef  |  

27:  Pakazad, S.K., F. Hajati and S.D. Farahani, 2011. A face detection framework based on selected face components. J. Applied Sci., 11: 247-256.
CrossRef  |  

28:  Mckenna, S.J., S. Gong and Y. Raja, 1998. Modelling facial colour and identity with gaussian mixtures. Pattern Recognition, 31: 1883-1892.
CrossRef  |  

29:  Li, W., Y. Lin, H. Li, Y. Wang and W. Wu, 2011. Multi-channel gabor face recognition based on area selection. Inform. Technol. J., 10: 2126-2132.
CrossRef  |  Direct Link  |  

30:  Dai, Y. and Y. Nakano, 1996. Face-texture model based on SGLD and its application in face detection in a color scene. Pattern Recognit., 29: 1007-1017.
CrossRef  |  

31:  Liu, Z. and Y. Wang, 2000. Face detection and tracking in video using dynamic programming. Proc. Int. Conf. Image Process., 1: 53-56.
CrossRef  |  

32:  Wang, Z. and S. Li, 2011. Face recognition using skin color segmentation and template matching algorithms. Inform. Technol. J., 10: 2308-2314.
CrossRef  |  Direct Link  |  

33:  Wakaf, Z. and M.M. Saii, 2009. Frontal colored face recognition system. Res. J. Inform. Technol., 1: 17-29.
CrossRef  |  Direct Link  |  

©  2021 Science Alert. All Rights Reserved