0.4 Algorithms

Algorithms

Modified viola-jones face detection

First we detect the face using a Viola-Jones based algorithm. The exact algorithm we used is outlined by Lienhart, et al. [3] . This algorithm uses an extended set of Haar Features to determine where a face is in an image.

Figure 1 : Extended set of Haar-like features used in the algorithm we applied. The Intensity values for each feature will be the sum of the white region minus the sum of the black region. [3]

When a Haar-like wavelet passes over an image, edges become intensified as edges will have a large difference between the white and black regions of the wavelets (Fig. 2 ) By setting a high enough intensity threshold, the points above the threshold will likely be edges. An image of a face will exhibit many edges at different facial landmarks. In order to ascertain if a windowed region of the image is a face, several sweeps of different Haar features are done in order to ensure high enough accuracy of detecting a face. Detection of a face should also be attempted with several window sizes as face size within an image can vary.

This method would be very time-consuming and computationally expensive if all Haar features were swept over all possible windows of the entire image. In order to speed this up, a cascade of feature classifiers is used (Fig. 3 ). At each stage of the cascade, less and less common Haar features with more strict rules are added in order quickly throw out windows that do not contain a face. If the image passes one stage of the cascade, this will weakly indicate the presence of a face. However, if it passes all classifiers, there will be a high confidence level that a face is present.

Figure 2 : Cascade of feature classifiers. [2]

A nice demonstration of how using a cascade of Haar wavelets for face detection works is hosted by the University of St. Andrews ( Haar Wavelet Face Detection Demo ). This example illustrates very clearly how a weak classifier cascade drastically speeds up computation time.

Shi-tomasi corner detection

Shi-Tomasi corner detection is based upon Harris-Stephens corner detection, just with different threshold parameters. Therefore, we start explaining the algorithm by defining the Harris corner detector operator[1] :

• E - Sum of squared differences between the original and moved window
• u - x direction window displacement
• v - y direction window displacement
• w ( x , y ) - Weighting function of the window, either a gaussian or a window of ones.
• I ( x + u, y + v ) - intensity of the moved window
• I ( x , y ) - intensity of the original window

The detector essentially scans the image with a window of size x by y , for places where there is a large change in intensity in both the x and y directions.

In order to simplify the above expression, we use a first order Taylor series approximation of

I ( x + u, y + v ) – I ( x , y ) :

Then changing to a matrix representation gives:

Then defining M as the structure tensor from above:

The determination of R , which is the parameter that indicates the importance of the point as a corner is done by taking the minimum of the two eigenvalues of this matrix.

where

This is the Shi-Tomasi modification of the Harris and Stephens corner detection algorithm[5] . While the Harris and Stephens algorithm was more computationally efficient, the Shi-Tomasi algorithm was found to be more accurate. Since the original Harris and Stephens paper, the computational cost of computing eigenvalues has become less and less significant, so the Shi-Tomasi algorithm is now more commonly used.

Mouth curvature detection

Using the corners detected using the Shi-Tomasi algorithm, we use a least squares method to fit a second-order polynomial to the edge points detected [4] . From the second order term we get a measure of the curvature of the points detected in the mouth region.