Abstract: This study describes a system for tracking multiple faces in an input video sequence using facial convex hull based facial segmentation and robust hausdorff distance. The algorithm adapts skin color reference map in YCbCr color space and hair color reference map in RGB color space for classifying face region. Then, we obtain an initial face model with preprocessing and convex hull. For tracking, this algorithm computes displacement of the point set between frames using a robust hausdorff distance and the best possible displacement is selected. Finally, the initial face model is updated using the displacement. We provide an example to illustrate the proposed tracking algorithm, which efficiently tracks rotating and zooming faces as well as existing multiple faces in video sequences obtained from CCD camera.
INTRODUCTION
Detecting and locating human faces and facial features in an image or image sequences are important tasks for the applications like model-based coding of video sequences, recognition or identification of faces and intelligent human-computer interaction. Up to now, much work has been done on detecting and locating faces in gray-scale images and the method like mosaic and template-based[1,2], neural network- based[3] and example-based[4] have been well studied by many researchers. These methods, however, are all computationally expensive and some of them can only deal with the frontal faces with little variation in size and viewpoint. To solve these problems, recently, color-based face detection has become a new direction and exhibited a better performance[5]. Several approaches have been published so far for the detection of facial regions and facial features using color and some other information. For example, the method to automatically segment out a persons face from a given image that consisted of a head-and-shoulders view of the person and a complex background scene[6]. The face-like regions were first detected using color information and then the geometric knowledge of faces was used for further verification[7]. The above two approaches are fast and elaborate, yet they just considered single face and the background was not complex. Wu et al.[8] introduced a fuzzy pattern matching method for face detection in a complex background by using skin and hair color distribution rate, but it does not work when the facial region is not ellipse-like or the image includes rotating face or turning face. The face-like regions were detected using quantized skin color regions merging and wavelet packet analysis[9]. This method can detect faces with various sizes and different poses; however, it is also computationally expensive due to its complicated segmentation algorithm and time-consuming wavelet package analysis.
Once faces have been segmented in an initial image, they have to be tracked through the video sequence. Tracking facial motion is useful in many applications, such as expression analysis, animation, teleconferencing or face-based biometric person authentication. A robust face tracking algorithm should be insensitive to partial occultation’s and shadows, to changes in face orientation, scale and lighting conditions and it should also be computationally simple. Besides the general purpose tracking methods, there are some approaches that are specially designed to track faces or facial features. This way, the technique presented[10] characterizes each feature point using Gabor wavelets and could individually track each point by a phase-based displacement estimation. Other techniques introduced the constrain of real time processing. In this framework[11] located and tracked the dominant face in the scene based on skin color information. Finally, a snake-based approach for tracking facial features was developed[12] that included motion estimation in the energy minimization process of the snake. This allows for large displacements of the contour and for a more robust feature tracking.
This study address a new and effective multiple faces tracking algorithm, which involves face with orientation and a various of size, without much computation using convex hull and robust hausdorff distance. Our method suggests two kinds of problems how to determine the initial face model and how to do the face model update. In this study, we determine the initial face model from intersection relationship (ICH) between the convex hull of skin color regions (SCH) and convex hull of hair color regions (HCH) and track the face of next frames by robust hausdorff distance measure[13,14].
The performance of the proposed algorithm is shown by an experiment. Experimental results show that the proposed algorithm successfully and efficiently tracks rotating and zooming faces as well as multiple faces in a video sequence.
SKIN AND HAIR COLOR SEGMENTATION
Color segmentation: The head of a human consists of a face region and a hair region. Therefore, this study uses two kinds of color reference maps for stable and accurate face segmentation. One is a skin color reference map and another is a hair color reference map.
The first work is classifying pixels of the frame p in video sequence into skin color and non-skin color. In order to do so, we use a skin color reference map in YCbCr color space like[7]. Let's define skin color range of Cb and Cr in YCbCr color space as RCb and RCr, respectively and we call the skin color range as skin color reference map. The RCb= [77 127] and RCr= [133 173] is defined by Chi and Ngan[7], which propose a set of regularization processes that are based on the spatial distribution and the corresponding luminance values of the detected skin color pixels and this approach overcomes the restriction of motion analysis and avoids the extensive computation of the ellipse-fitting method. With this skin color reference map, the skin color segmentation can now begin. Lets call the set of pixel of frame extracted from the skin color reference map as the skin likeness region. Since we are utilizing only the color information, the segmentation requires only the chrominance component of the frame. The skin color likeness is described as:
| (1) |
For hair color segmentation, we make the hair color region in RGB color space. A race in this study is limited as an oriental having black hair. Usually, the hair color has an insensitive property For hair color segmentation, we make the hair color region in RGB color space. A race in this study is limited as an oriental having black hair. Usually, the hair color has an insensitive property to luminance. Then, we use RGB color space for hair color segmentation. Lets define hair color ranges of R, G and B in RGB color space as RR= [0 30], RG= [0 30] and RB= [0 30] in experience, respectively and we call the hair color range as hair color reference map.
We extract the image points falling inside respective hair color reference map for hair color segmentation. Lets call the set of pixel of frame extracted from the hair color reference map as the hair likeness region. We can find the set of pixels of the hair likeness regions of a frame in video sequence from Eq. 2
| (2) |
In the next step, we apply the opening operator to remove the noises and we find the skin and hair color region, which is final region of preprocessing.
Face segmentation algorithm based on convex-hull: A convex polygon has the property that any line connecting any two points inside the polygon must itself lie entirely inside the polygon[15]. Then, we define set of points constructing the convex polygon as convex hull.
This study proposed an effective face segmentation algorithm using the property of convex-hull. Usually, the skin and hair color regions with intersection of them have a very strong possibility that they may be the face and hair.
After assigning label to each color region, we make the set of the pixels in the convex-hull of hair color region as Hj and that of skin color region and intersection region as Fi, Iij, respectively. (I = 1~n, j = 1~m)
| (3) |
where, n [.] is 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.
FACE TRACKING ALGORITHM
Robust hausdorff distance: The use of the hausdorff distance for binary image comparison and computer vision was originally proposed by Huttenlocher et al.[16]. In this study, we can track using face model constructing set of outline points surrounding a face region in frame. Let’s call the set of outline points surrounding a face region as convex hull’s information.
The hausdorff distance measure computes the distance between the points obtained from the convex hull’s information in a frame p and the convex hull’s information in frame p+1. The conventional hausdorff distance between two point sets, the convex hull’s information of initial model in the frame p, M = {m1,...,mNM} and that of update model in the frame p+1, C = {c1,....,cNc} of sizes NM and Nc, respectively is defined as
| (4) |
| (5) |
| (6) |
For every model point m, the distance to the nearest convex hull’s information c is computed, then the maximum value is assigned to h(M,C). Also, for convex hull’s information of current frame c, the maximum distance to the nearest model point m is calculated, then it is assigned to h(C,M). Hausdorff distance is the larger value of the two maxima. That is, h(M,C)=d means that every point of the model is within the distance d from some convex hull’s information. But, there are some problems in Eq. 5 and 6.
If the model or object is outlying, the hausdorff distance will be very large, even if most of the points are matched well.
Thus, we use a robust hausdorff distance measure[13] proposing a robust hausdorff distance based on the robust statistics such as M-estimation to reduce the problems. The direct distance hR(M,C) is defined as:
| (7) |
where, dc(m) represents the minimum distance at point m to the convex hull’s information of current frame C and the cost function ρ is defined by
| (8) |
where, τ is a threshold to eliminate outliers. It is useful to reduce the effect of outliers and to compare portion of images. In this study, we implement above robust hausdorff distance to track a face in video sequences. The algorithm is as follows.
It is assumed that the hausdorff distance is smaller than a threshold T. A small shape change in all directions, the displacement t ∈ T of a face model is obtained by minimizing the following formula :
| (9) |
That is, hM(M+t, C) and hM(C-t, M) and are computed, then the larger of the two is selected as hM(M, C). When it is made the smallest value by t, t is selected as the best possible displacement.
The initializing of a face model: First of all, the face position has to be determined. We presented a face model in an input image frame using face segmentation algorithm. Let’s call the convex hull‘s information of the frame p as Mx (x=1~m') and m' denotes the number of the convex hull’s information in the frame p.
The right figure on the Fig. 1 shows convex hull’s information in the frame p.
Model update: Since the tracked object can rotate or change its shape, it is necessary to update the corresponding model every frame. We invest the face regions using face segmentation algorithm to the new model of frame p+1 for finding the best possible displacement t. Let‘s call the convex hull’s information of the frame p+1 as Cy(y=1~n') and n denotes the number of the convex hull’s information in the frame p+1.
If the x is equal to the y, we shift the face model of the frame p to the new position of best match to update these parts, which was located by the robust hausdorff distance or else we consider the face model of frame p as initial model for tracking the new face again.
| (10) |
When the model of the frame p is shifted to the new position with the displacement t. the part of convex hull’s information with t that belongs to the updated model is selected by the following equation.
| (11) |
The selection of σ is very critical. If σ is too small, we have little tolerance to the shape change. If it is too large, some nearby noises are determined as new model. In our experiment, it is 3 pixels is used.
| Fig. 1: | The initial model |
| Fig. 2: | Skin and hair color region in 1st frame |
| Fig. 3: | Initial face model |
| Fig. 4: | Two people tracking |
| Fig. 5: | Tracking in case of closing two faces |
EXPERIMENTAL RESULTS
We have applied the proposed tracking algorithm to track multiple faces in video sequence containing faces, which is obtained by CCD camera. The obtained images are 160 120 RGB model images of laboratory environment. The host computer administering the hole system uses IBM PC Pentium III 700 MHZ.
First, we segment skin and hair likeness regions from the background using skin and hair color reference map. An initial face model is obtained from SCH with ICH. Finally, the model is updated or initialized according to relationship between the number of convex hull’s information of the frame p and that of the frame p+1. Figure 2 and 3 show skin and hair color regions and the initial model in the frame p, respectively. Figure 4 and 5 represent the tracking results of multiple faces from video frame with robust hausdorff distance and the algorithm has the robust property when the frame includes rotating or zooming face.
CONCLUSIONS
A new tracking algorithm based on robust hausdorff distance was presented. A model of the face was automatically derived and matched against subsequent frames using the robust hausdorff distance. To accommodate for rotation and changes in shape, the model was updated every frame by a novel update technique that consists of two components for slowly and rapidly changing or moving parts. Matching the model based on robust hausdorff distance using convex hull's information is remarkably robust from the noise. The new position is accurately detected even when the face undergo large changes in shape or the background is moving because of analyzing the color of successive frames using the proposed face segmentation algorithm. Also, the system can track the multiple moving faces from sequence or the rotating face.