Viola-Jones Method

Viola-Jones Method

This method is used for frontal face detection and is used in opencv library. Haar Cascade is a classifier which is used for detection of human frontal face.

• The function "cvHaarDetectObjects" in OpenCV performs the actual face detection
• This approach to detecting objects in images combines four key concepts:
- Simple rectangular features, called Haar features
- An Integral Image for rapid feature detection
- The AdaBoost machine-learning method
- A cascaded classifier to combine many features efficiently
• Features used are based on Haar wavelets (Haar wavelets are single wavelength square waves (one high interval and one low interval)). 
• In two dimensions, a square wave is a pair of adjacent rectangles one light and another dark.
• Haar Features are determined by the subtracting the average dark region pixel from the average white region pixel.
• If difference is above threshold, the feature is said to be present else not.
• For hundreds of haar feature detection method of integration is used.
• Small units of image, pixels, are added in such a manner that the integral value for each pixel is the sum of all the pixels above it and to its left.
• Figure below shows, after integration, the value at each pixel location, (x,y), contains the sum of all pixel values within a rectangular region that has one corner at the top left of the image and the other at location (x,y). To find the average pixel value in this rectangle, you'd only need to divide the value at (x,y) by the rectangle's area. But what if you want to know the summed values for some other rectangle, one that doesn't have one corner at the upper left of the image? Figure (b) shows the solution to that problem. Suppose you want the summed values in D. You can think of that as being the sum of pixel values in the combined rectangle, A+B+C+D, minus the sums in rectangles A+B and A+C, plus the sum of pixel values in A. In other words,
  D = A+B+C+D - (A+B) - (A+C) + A.

• A+B+C+D is the Integral Image's value at location 4, A+B is the value at location 2, A+C is the value at location 3, and A is the value at location 1. So, with an Integral Image, you can find the sum of pixel values for any rectangle in the original image with just three integer operations: (x4, y4) - (x2, y2) - (x3, y3) + (x1, y1).
• For selecting specific haar features and to set threshold level AdaBoost machine learning method is used.
• AdaBoost selects a set of weak classifiers to combine and assigns a weight to each. This weighted combination is the strong classifier.
• The acceptance threshold at each level is set low enough to pass all, or nearly all, face examples in the training set (The training set is a large database of faces, maybe a thousand or so). Viola and Jones combined a series of AdaBoost classifiers as a filter chain. During use, if any one of these filters fails to pass an image region, that region is immediately classified as "Not Face."
• If a filter passes an image region, it goes to the next filter in the chain. Image regions that pass through all filters in the chain are classified as "Face." 

Eigenface Algorithm

Constructing Eigenfaces

Eigenface algorithm is used to recognize the detected face. Here is the simple algo for eigenface:

• Collect a bunch (call this number N) of images and crop them so that the eyes and chin are included, but not much else.
• Convert each image (which is x by y pixels) into a vector of length xy.
• Pack these vectors as columns of a large matrix.
• Add xy - N zero vectors so that the matrix will be square (xy by xy).
• Compute the eigenvectors of this matrix and sort them according to the corresponding eigenvalues. These vectors are your eigenfaces. Keep the M eigenfaces with the largest associated eigenvalues.

This procedure relies on computing eigenvectors of an extremely large matrix. If images are of 250x300 pixels, so the matrix would be 75000 by 75000 (around 5.6 billion entries). On the brighter side, there's another way (Karhunen-Loève expansion):

• Collect the N images, crop them, and convert them to vectors.
• Compute the N by N outer product matrix (call it L) of these images. The entry Lij of this matrix is the inner product of image vectors number iand j. As a result, L will be symmetric and non-negative.
• Compute the eigenvectors of L. This will produce N - 1 vectors of length N.
• Use the eigenvectors of L to construct the eigenfaces as follows: for each eigenvector v, multiply each element with the corresponding image and add those up. The result is an eigenface, one of the basis elements for face space.
• Use the same sorting and selecting process described above to cut it down to M eigenfaces.
• Take inner products between the image and each of the eigenfaces and pack these into a vector of length M for transforming an image to face space
• Multiply each of the elements of the face space vector with the corresponding eigenfaces, and add up the result.

Recognizing a known face:

• Transform the image presented for recognition to face space.
• Take inner products with each of the learned face space vectors (think Cauchy-Schwartz).
• If one of these inner products is above the threshold, take the largest one and return that its owner also owns the new face.
• Otherwise, it's an unknown face. Optionally add it to the collection of known faces as "Unknown Person #1".
• If unsure whether an image is a face or not, transform it to face space, then do the inverse transform to get a new image back.
• Use mean-squared-error to compare these two image. If the error is too high, it isn't a face at all.

NOTE: This process does not rely on knowing any faces, just having a set of eigenfaces.