OSA's Digital Library

Optics Express

Optics Express

  • Editor: Michael Duncan
  • Vol. 10, Iss. 6 — Mar. 25, 2002
  • pp: 274–279
« Show journal navigation

Algorithm for detecting human faces based on convex-hull

Minsick Park, Chang-Woo Park, Mignon Park, and Chang-Hoon Lee  »View Author Affiliations


Optics Express, Vol. 10, Issue 6, pp. 274-279 (2002)
http://dx.doi.org/10.1364/OE.10.000274


View Full Text Article

Acrobat PDF (421 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

In this paper, we proposed a new method to detect faces in color based on the convex-hull. We detect two kinds of regions that are skin and hair likeness region. After preprocessing, we apply the convex-hull to their regions and can find a face from their intersection relationship. The proposed algorithm can accomplish face detection in an image involving rotated and turned faces as well as several faces. To validity the effectiveness of the proposed method, we make experiment with various cases

© Optical Society of America

1. Introduction

Face detection from an image is a key problem in human computer interaction studies and in pattern recognition researches. Many researchers on automatic face detection have been proposed recently [1–7

1. H. Wu, Q. Chen, and M. Yachida, “ Face Detection From Color Images Using a Fuzzy Pattern Matching Method,” IEEE Trans on Pattern Analysis And Machine Intelligence 21, 557–562 (1999) [CrossRef]

].

The researchers of face detection are divided into a various of approaches.

The feature-based approaches required the detection and measurement of salient facial points[3

3. A. Samal and P.A. Iyengar, “Automatic recognition and analysis of human faces and facial expressions: a survey,” Pattern Recogintion 15, 65–77 (1992) [CrossRef]

] used geometrical distances and angles between primary facial features such as eyes, nose and mouth to classify faces using an economic representation of the face where the elements were based on their relative positions and sizes. A template-matching strategy was based on the earlier work of [4

4. C. S. Choi, K. Aizawa, H. Harashima, and T. Takebe “Analysis and synthesis of Facial Image Sequences in Model-Based Image Cording,” IEEE Transactions on Circuits and Systems for Video Technology 4, 257–275, (1994) [CrossRef]

] using feature-based templates of the mouth, eyes and nose, in addition to whole face templates. [5

5. S. Ho and H. Huang, “Facial Modeling from an Uncalibrated Face Image Using Flexible Generic Parameterized Facial Models,” IEEE Transactions on Systems, Man, and Cybernetic-Part B 31, 706–719 (2001) [CrossRef]

] suggested that the expected shape of geometric features could be used to construct deformable templates in which templates could be translated, rotated and deformable to fit the best representation of their shape present in the image.

Face detection based on Principal Components Analysis(PCA) was also reported [7

7. A. Pentland, B. Moghaddam, and T. Starner, “View-based and modular eigenspaces for face recognition,” Proceedings of IEEE Conference on Computer Vision & Pattern Recognition, Seattle, WA. IEEE Computer Society Press, 84–91.

] and Oriented Difference of Gaussians convolution [8

8. P. J. B. Hancock, A. M. Burton, and V. Bruce, “Preprocessing images of faces: correlations with human perceptions of distinctiveness and familiarity,” Proceedings of IEE Fifth International Conference on Image Processing and its Applications, Edinburgh, Scotland. (1995)

] and Gabor wavelet transform [9

9. S. J. McKenna, S. Gong, and J. J. Collins, Face tracking and pose representation, in R. B. Fisher and E. Trucco (Eds.), Proceedings of British Machine Vision Conference, 755–764 (1996)

] have also been performed before PCA to provide a greater level of invariance than found using gray-level pixel information. Instead of detecting faces by following a set of human-designed rules, alternative approaches were based on neural networks [2

2. S. Y. Lee, Y.K. Ham, and R.-H. Park, “Recognition of Human Front Faces Using Knowledge-Based Feature Extraction and Neuro-Fuzzy Algorithm,” Pattern Recognition 29, 1,863–1,876 (1996) [CrossRef]

], [6

6. P. Juell and R. Marsh, “A Hierachical Neural Network for Human Face Detection, Pattern Recognition,” 29, 781–787 (1996)

] or fuzzy pattern[1

1. H. Wu, Q. Chen, and M. Yachida, “ Face Detection From Color Images Using a Fuzzy Pattern Matching Method,” IEEE Trans on Pattern Analysis And Machine Intelligence 21, 557–562 (1999) [CrossRef]

].

However, low-level computer vision algorithms such as feature-based approaches were not powerful enough to find out all possible face regions and there were not likely to perform well in case of small faces or low quality images. The deformable templates were computationally expensive and not robust to everyday variation. Also, although the PCA was a very efficient designed specifically to characterize face region, it was not invariant to image transformations such as scaling, shift of rotation in its original form and requires complete relearning of the training data to add new individuals to the database. Although performance of pattern method approaches reported was quite well, and some of them could detect non-frontal faces, the approaches were extremely computationally expensive.

This paper addresses a new and simple face detection algorithm that can detect faces with different size and rotation. We find the face candidate by skin and hair color like [1

1. H. Wu, Q. Chen, and M. Yachida, “ Face Detection From Color Images Using a Fuzzy Pattern Matching Method,” IEEE Trans on Pattern Analysis And Machine Intelligence 21, 557–562 (1999) [CrossRef]

] and the face by adapting intersection relationship(ICH) between a convex-hull of skin color regions(SCH) and a convex-hull of hair color regions(HCH).

2. Proposed Face Detection Algorithm

2.1 Detecting Skin color regions and hair color regions

In order to extract the skin and hair likeness regions, they are detected by color detection method of [1

1. H. Wu, Q. Chen, and M. Yachida, “ Face Detection From Color Images Using a Fuzzy Pattern Matching Method,” IEEE Trans on Pattern Analysis And Machine Intelligence 21, 557–562 (1999) [CrossRef]

] which use Skin Color Distribution(SCDM) and Hair Color Distribution(HCDM). Also, we convert them into binary image and apply the opening operator to remove a noise. And the label to them is assigned.

Fig.1 Skin and hair likeness regions

2.2 Face Detection based on convex-hull

A convex polygon has the property that any line connecting any two point inside the polygon must itself lie entirely inside the polygon[10

10. Z. Hussain, Digital Image Processing (New York, Ellis Horwood limited, 1991)

]. Therefore, The convex hull of a set of points in the plane is defined to be the smallest convex polygon containing them all.

This paper proposed new face detection algorithm using the property of convex-hull. Usually, the skin and hair likeness regions with intersection of them have a very strong possibility that they may be the face and hair.

After assigning label to each region, we make the set of the pixels in the convex-hull of hair likeness region as H j and that of skin likeness region and intersection region as Fi , Iij , respectively. (i = 1~n, j = 1~m)

Iij=FiHjSet the value of pixels inFiifn[Iij]>τ0otherwise
(1)

where,

  • n[·] : the number of element in the set
  • n and m denote the number of the set of the pixels in the convex-hull

    surrounding skin likeness regions and that of hair likeness regions

  • the pixel value ‘1’ represents the pixel comprising the face region.
Fig.2 Face Detection

Figure.2 shows the face detection procedure via convex-hull in an image. Using equation (1), we can select the F 1 and H 8 , where we choose τ as 10. Consequently, F 1 can be decided to be a face region.

3. Experiments and Result

We implemented our method on a PC compatible computer with a 700MHz. We tested our algorithm on 80 still color images. The images were chosen from a CCD camera, a digital camera or Internet, and consisted of both indoor scenes and outdoor scenes. Among them, 48 are images including one face and 32 are images including multi-face. We used the image of 320×240 pixel. The proposed algorithm was compared with conventional methods, PCA and Template based method, and the average performance and detection time are shown in Table 1 and 2.

Table 1. The Detection rate by two traditional methods and proposed method

table-icon
View This Table
| View All Tables

Table 2. The average detection time by two traditional methods and proposed method

table-icon
View This Table
| View All Tables

As shown in Table 1, and 2, our detection algorithm has several good performances. First, the proposed algorithm shows the average detection rate of 91% in spite of including complex background. In addition, our algorithm can detect faces of images with rotated face, deformed face and face of difference size, while most of the traditional detection methods do not have these performances. Another good performance of our approach is its high efficiency, the average detection time is about 0.3s(the shortest is 0.2s for one face and the longest is 0.5s for 4 faces), while the template- and neural-network-based approaches generally need several seconds. Therefore, our method is more accurate and stable method for face detection.

The experimental results of face detection are as followings.

Fig.3 Experimentally resultant image involving several faces
Fig.4 Experimentally resultant image involving turned face
Fig.5 Experimentally resultant image involving the rotated image

4. Conclusion

Our method may also give some false positives under some condition, whose reasons under concern include the following:

  1. Hairstyle : Faces with special hair styles, such as skinhead, or wearing a hat, may fail to be detected.
  2. If people wear a clothe of skin color, the clothes may be treated as a skin color.
  3. If two or more faces are too close, the skin parts of them may be merged together.

The most important reason is that we only use the convex-hull and ignore all the details about facial features during the face detection. Checking if there are facial feature in these face candidates can help improving the face detection rate.

References and links

1.

H. Wu, Q. Chen, and M. Yachida, “ Face Detection From Color Images Using a Fuzzy Pattern Matching Method,” IEEE Trans on Pattern Analysis And Machine Intelligence 21, 557–562 (1999) [CrossRef]

2.

S. Y. Lee, Y.K. Ham, and R.-H. Park, “Recognition of Human Front Faces Using Knowledge-Based Feature Extraction and Neuro-Fuzzy Algorithm,” Pattern Recognition 29, 1,863–1,876 (1996) [CrossRef]

3.

A. Samal and P.A. Iyengar, “Automatic recognition and analysis of human faces and facial expressions: a survey,” Pattern Recogintion 15, 65–77 (1992) [CrossRef]

4.

C. S. Choi, K. Aizawa, H. Harashima, and T. Takebe “Analysis and synthesis of Facial Image Sequences in Model-Based Image Cording,” IEEE Transactions on Circuits and Systems for Video Technology 4, 257–275, (1994) [CrossRef]

5.

S. Ho and H. Huang, “Facial Modeling from an Uncalibrated Face Image Using Flexible Generic Parameterized Facial Models,” IEEE Transactions on Systems, Man, and Cybernetic-Part B 31, 706–719 (2001) [CrossRef]

6.

P. Juell and R. Marsh, “A Hierachical Neural Network for Human Face Detection, Pattern Recognition,” 29, 781–787 (1996)

7.

A. Pentland, B. Moghaddam, and T. Starner, “View-based and modular eigenspaces for face recognition,” Proceedings of IEEE Conference on Computer Vision & Pattern Recognition, Seattle, WA. IEEE Computer Society Press, 84–91.

8.

P. J. B. Hancock, A. M. Burton, and V. Bruce, “Preprocessing images of faces: correlations with human perceptions of distinctiveness and familiarity,” Proceedings of IEE Fifth International Conference on Image Processing and its Applications, Edinburgh, Scotland. (1995)

9.

S. J. McKenna, S. Gong, and J. J. Collins, Face tracking and pose representation, in R. B. Fisher and E. Trucco (Eds.), Proceedings of British Machine Vision Conference, 755–764 (1996)

10.

Z. Hussain, Digital Image Processing (New York, Ellis Horwood limited, 1991)

OCIS Codes
(110.2960) Imaging systems : Image analysis
(110.2970) Imaging systems : Image detection systems

ToC Category:
Research Papers

History
Original Manuscript: December 20, 2001
Revised Manuscript: March 8, 2002
Published: March 25, 2002

Citation
Minsick Park, Chang-Woo Park, Mignon Park, and Chang-Hoon Lee, "Algorithm for detecting human faces based on convex-hull," Opt. Express 10, 274-279 (2002)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-10-6-274


Sort:  Journal  |  Reset  

References

  1. H. Wu, Q. Chen and M. Yachida, �Face Detection From Color Images Using a Fuzzy Pattern Matching Method,� IEEE Trans. Pattern Anal. Mach. Intell. 21, 557-562 (1999). [CrossRef]
  2. S. Y. Lee, Y. K. Ham, and R.-H. Park, �Recognition of Human Front Faces Using Knowledge-Based Feature Extraction and Neuro-Fuzzy Algorithm,� Pattern Recognition 29, 1863-1876 (1996) [CrossRef]
  3. A. Samal and P. A.Iyengar, �Automatic recognition and analysis of human faces and facial expressions: a survey,� Pattern Recogintion 15, 65-77 (1992). [CrossRef]
  4. C. S. Choi, K. Aizawa, H. Harashima, T. Takebe �Analysis and synthesis of Facial Image Sequences in Model-Based Image Cording,� IEEE Trans. Circuits Syst. for Video Tech. 4, 257-275, (1994). [CrossRef]
  5. S. Ho, H. Huang, �Facial Modeling from an Uncalibrated Face Image Using Flexible Generic Parameterized Facial Models,� IEEE Trans. Syst. Man Cybern. 31, 706-719 (2001) [CrossRef]
  6. P. Juell and R. Marsh, �A Hierachical Neural Network for Human Face Detection," Pattern Recognition 29, 781-787 (1996).
  7. A. Pentland, B. Moghaddam, and T. Starner, �View-based and modular eigenspaces for face recognition,� Proceedings of IEEE Conference on Computer Vision & Pattern Recognition, Seattle,WA. IEEE Computer Society Press, 84-91.
  8. P. J. B.Hancock, A. M. Burton, V. Bruce, �Preprocessing images of faces: correlations with human perceptions of distinctiveness and familiarity,� Proceedings of IEEE Fifth International Conference on Image Processing and its Applications, Edinburgh, Scotland (1995).
  9. S. J. McKenna, S. Gong and J. J. Collins, Face tracking and pose representation, in R. B. Fisher and E. Trucco (Eds.), Proceedings of British Machine Vision Conference, 755-764 (1996)
  10. Z. Hussain, Digital Image Processing ( New York, Ellis Horwood limited, 1991)

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig.1 Fig.2 Fig.3
 
Fig.4 Fig.5
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited