Computer Vision: Face Detection with Support Vector Machines

 One component on Face Detection is the support vector machines. Detecting faces is finding human faces in images.

We will look at a few different aspects of face detection techniques, including a few classifiers and a couple of machine learning problems as well.

The first question is: Why do we want to detect faces in the first place? Search engines are very effective at face detection. We can prune results saying that we are only look for images of xxxx in them. Another system is tagging people with faces in amages, and now people are tagging faces with high accuracy. Then there is surveillance and monitoring. There are conferences dedicated to all of the faces and images. 

Let's now talk about humans. How do humans detect faces? We don't know for sure, but we think we have a description of a model of faces in our memory and match images to that model. There's also gamma neurons, which fire when we come accross a specific person, whether it's our grandmas and Jennifer Aniston. Finally, there is some parallel computing going on, we can do this on multiple scales and faces depending on how far or close they are.

We slide windows of different sizes at each location, and match the window to face model.   

For each of these windows, we extract features from the image, from a representation of an image to get a formal representation of faces. In the second step, we match these features to the model of the face to make a decision whether the window matches a face or not. To make this decision, we use machine learning algorithms, and then we look at a couple of decision.

For each window, extract the features, and then use some machine learning algorithm for classification, for 2-way decisions. 

We want to discriminate face/non-face. The features from a face and non-face images are very different. Typically we need to evaluate millions of windows in an image, and it can be done for many milliseconds at a time. 

                                                                               Face

                           No face. Both are very good looking but one is a human and the other isn't.

Facial components are easy to compute but the rest is not. 

These are good candidates for facial features. Given these 2 requirements, let's go into SIFT. The problem is that SIFT can be very slow to compute. 

Here is what the facial components have.

Model David Gandy. 

The question is do we need to check different sizes for face detection? Yes, we do! We have to consider a few distinct sizes. 

There are certain applications that are subject for concern, and there are systems that will still use these 2 features. 

Fortunately, there is 1 features which has been quite popular for face detection, and they are called the Haar filters. White is +1 black is -1. There are a lot of values and for HAAR filters, there are 2 values, +1 and -1. 

The filters are fixed and pre-defined like Gaussian Filters and Laplacian Filters. There is no real fixed number of filters, but there is a general recipe for creating these filters, which you can follow to create any number of these filters. 

It's not obvious that these filters can be used as interest points, because these are not defined for image pixels but image windows. These are not useful for image stitching, not for local points, but more for windows. All that the feature is doing is extracting some type of representation from the tasks. The Haar features are a very general tool that extend beyond facial recognition, and these are extremely useful where speed is an issue. 

This high-level intuition is that these filters look like the gradient filters that we saw earlier. This is because computing gradients is like taking the difference of neighboring pixels. Some filters compute a horizontal difference of pixel directions at a courser scale. Image locations where there is a strong horizontal gradient will get a high response. Not it there is uniform noise. If we have a different filter. like Hd, they are sensitive to intensity gradients in the diagonal direction. These features are not as sophisticated as sift-like features. 

SIFT is robust to the scale of objects as well. Haar features have a scale to a certain extent by computing these features at different scales. 

Speed nearly compensates for limited flexibility. Remember white means +1 and black means -1.

The correlation is a weighted sum of the image pixels. This is where the special structure of the filter comes in, with +1 and -1. It means that a correlation. We want to take the difference of the sum of pixel intensities in the white area vs the black area. 

The computation costs can be expensive, there can be over a trillian (N x M - 1) computations just to process one image. Can we exploit the special structure of these filters. Can we share the computation results across multiple of these computations. Can we leverage filters to get the measurements right? 

Suppose there is an integral image, for every location, you store the sum of the intensities of all the pixels to the left of a location and above a location. We will store all of the pixels for a particular rectangular window. We then get a data structure called the integral image, which stores the sum of the integral of pixel intensities. For an [i,j] set it stores the sum of all the pixel intensities from [0,0] to [i,j]. 

We can use integral imaging to compute the sum of pixel intensities in a rectangular window. 

First we see in a green shaded region and see the sum of a rectangular window. The problem is certain windows are wayyy too large, and we want to reduce the size of the window and remove the pixels that are not 100% essential. 

Again we are going to find values in this integral image corresponding to chunks of the pixels we want to remove. We subtract the value from the first one and subtract certain corners to get certain values. 

In here the sum is Hp - Hq - Hs + Hr, and we can compute the sum of these pixels with only and exactly 3 additions. 

To take the sum of pixels and the white window and the sum of pixels in the black windows, we need 7 computations. 

The computation is constant, regardless of the size of the filter. 

A purpose will be defeated if an integral image itself takes some time. 

Ha = Hb + Hc - Hd + Ia

Use raster scanning, we only need 3 operation for each location. Regardless of image content, we still get it to compute the integral image content. We, as a result can compute feature vectors extremely fast, so this is really useful. 

How do we decide whether a window contains a face or not.   Suppose we use N Haar filters, and there will be n Numbers, and a way to represent these HAAR filters are points in N-dimensional space. 

Features are represented as features in n-dimensional space. Feature vectors are defined as windows, so we have one feature vector for every window. Face is represented in green, and non-face is represented in red. We can represent a vector as a point in N-dimensional space. The green point is positive examples, and the red samples represent negative examples. With these labelled training examples, we can start thinking about designing a classifier. 

What's the simple example to use prior training examples to assign a label to a new point? The simplest algorithm conceptually is to find a point which is closest, and see whether a closes point is green or red. There can also be False Positives and false negatives, one that is classified as faces, when it is really not. This happened in close intervales or whenever a picture is in the border between face and not face. 

Overall, the nearest neighbor classifier is a strong algorithm. Another idea is to use a decision boundary of the surface. We can find a decision boundary, and we want to figure out which side of a boundary a new sample lies on. This could be very simple, and the operation can be done extremely fast. We start with a linear boundary, which in 2D space is just a line. 

Lets say the coefficient of a line is w1 and w2. We can write the line equation compactly as the follows: 

The side will be correlated with whether the value of the expression and positive or negative.

We can do a test within a constant amount of time, even with over a million training samples. A linear boundary in 3 direction will be a plane and w1f1 + w2f2 + w3f3 + b = 0. 

If we go to n dimensions, meaning the features are n-dimensional vectors, the linear boundary is a n - 1 dimensional hyperplane and the same compact form is written w1f1 + ... + wnfn = 0. The computation time does not depend on the number of training samples. All I need to do is to take the dot product. 

Next, I want to talk about how to actually find a boundary. We use support vector machines for this, which maximizes. the diagonal distance cumulative between the line and the points.  In practice there are certain lines to prefer, even if they perfectly fit all of the points. We are going to use the metric with the maximum distance from all the points, because this will give us the most robustness for the new data set. We want the maximum probability of correct classifications. 

We want to maximize the safety margin, which is how thick some line can be before it hits a feature training point. 

Noise can affect everything, and other things will classify.  

A classifier that uses the linear boundary with the maximum margin is called the support vector machine, one of the most common algorithms for classification. This is good to know about. The support vectors are the sample that are the closest to the boundary, and they should be able to support the boundary. It can be shown that the decision boundary and margin depend only on the support vectors. 

How do we find this line? Given a set of training images, for each training image, we have a label λ1 λ2, etc. and the goal is to find the boundary with the maximum margin ρ.

The distance should be at least ρ / 2.

so the equation is the following that takes both of the cases: 

This was for each training sample (fi, λi). In matlab, there is a function for training an SVM for training the parameters of this boundary (called svmtrain). 

Once we have the boundary, the classification algorithm is quite simple. Given a feature vector, we compute the distance d of the feature of the boundary. If the distance is more than half of the margin and less than negative half of the margin, then it is/not is a face. If it is within a margin it is probably a face or not a face depending on the side that the boundary lies on. The time taken to process a fram can be very fast and can detect faces or not. 

No algorithms are robust enough to work in applications. More recently, people have started more challenging methods to work for side poses. Overall, this is a very important application, but still remains of interest. 

If d > 0 or d < ρ / 2 probably face

if d < 0 or d > - ρ / 2 probably not a face. 

Thank you for reading.