Eigenfaces
By Christopher Clark
CSE 455, Computer Vision
3/8/2012

Objective: In this project we attempted to implement face recognition. We were trying to use PCA or Principle Component Analysis to find a way to described images in a much reduced dimensionality space. We could then use that reduced space to recognize new images as faces and match face pictures from a single user to each other.

Challenges: It was a little challenging to calculate the eigenvectors because it was often hard to find out where the method was going wrong if the output was incorrect. It was also hard to write findface. It was surprisingly tricky to search and keep track of the best sub-images in the image we are scanning for faces.

Lessons Learned: Having done this project I feel much more confident in my knowledge of PCA (which we just started covering in my machine learning class as well) and using eigenfaces. It was an interesting challenge to try and write findface so the eigenfaces could be used to detect faces in an image.

Structure:
    Faces::eigenFaces - Calculates the best n egienfaces using a given list of face images.
    EigFaces::projectFace - Find the coordinate of a face image on a given eigenvector hyperplane
    EigFaces::constructFace - Takes a point on the eigenvector plane and recreates it as a face
    EigFaces::isFace - Identifies whether an image is a face or not
    EigFaces::verifyFace - Guess if a face is a picture of a given user
    EigFaces::recognizeFace - Sorts the user in order of most likely to be the person in a given face picture
    EigFaces::findFace - Scans an image to find the faces in it
Finding the Eigenfaces

First we took a training set of face images. We reduced the resolution and converted them to black and white. From there each image could be thought of as a vector each pixel being a dimension. We reduced this space using PCA. I subtracted the average face from the face then found the covariant matrix of these points. I then computed the eigenvectors of the matrix (actually this we done indirectly, see extra credit). I then took the top n eigen vectors to be used for the rest of the project. Below are those vectors reinterpreted as faces.
Using a 25 x 25 resolution and the neutral class pictures.

Average Face

The top 10 EigenFaces:

1:   2:   3:  4:  5:

 6:  7:  8:  9:  10:
Using the Eigenfaces to Identify Faces
The eigenfaces above form a hyper plane in the space of the possible pictures. I made the assumption that all faces images are close to or on that hyper plane in order to try and identify new faces. First I took an image of the all the people the face could have belonged to and found their coordinates on the hyperplane. When identifying a new face I would project that point onto the hyperplane and find its coordinates on the plane as well. Then I would simply search to find the user image that was closest to the given image on the hyper plane and guess that those two images were of the same person.




Looking at the graph we can see that the increase in accuracy raises very quickly as we add in the first few eigenfaces, which makes senses as the top eigenfaces should be the ones that can be best used to characterize each face. However past 5 eigenfaces additional faces become less helpful or even determental. We can see this reflected in the eigen values of these eigenvectors:
EigenVector 1
Eigen VectorEigen Value
112321061
28632369
35174586
43351286
52359568
61868694
71431015
81191470
91102703
(Note I used the speedup technique so these are actually the eigenvalues of AtransposeA but their relative wieghts still apply)

We can see that the eigenvalues decrease quickly for the first few vectors but then mostly level out showing that the top eigen vectors were considerably better at capturing the variance among the faces the the lower ones. This is also encouraging as it suggests throwing out the lower eigenvectors under the assumption that they were relatively unimportant to describing the images was justified. Overall looking at this data using as many eigen vectors as possible would be preferred as the accuracy is the most consistent and the highest when a large number of eigen vectors we used. However if we want to save on computation using a much smaller number of eigen values we can do so without much loss.

We can also see that using larger eigenfaces did little to improve the accuracy on the set after a certain point. Although 10x10 eigenfaces did notably worse then the other sizes I tested everything else was pretty even in terms of accuracy. Sometimes using smaller eigenfaces was actually better. This might have occurred because the additional information we retained from using a larger eigenfaces was actually unhelpful and mislead us on a couple of images.
The Mistakes
The mistakes that were made mostly seemed reasonable. For instance when identifying:
The top three choices from my algorithm were: 1: 2: 3:

or when identifying:
The top three choices were: 1:  2: 3:
(3 is the correct answer in both cases)

All these faces are pretty similar, especially when we consider the fact the we are using grayscale so one of the most obvoius deciding factor here, skin color, is much harder to see. Otherwise the faces all have similiar shapes and the eyes, mouth, and nose are all in similar position so it is easy to see why the algorithm got them confused. At the least in these cases and in every other case I looked at the right answer would be within the top 5 guesses.
Finding Faces
Here we attempted to find a face and crop out the background or mark all the faces found. I implemented this by scaling the image down to varoius sizes and converting it to grayscale. I would then search each resized image to find the subimage or subimages that were closests to the hyperplane formed by the eigenvectors. The corresponding subimage on the full scale image would then be my best guess for a face. I attempted a couple additional calcuations to try and avoid mistaking plain colored sub-images for faces. However neither the solution suggested in the homework write up or anything I tried seemed to yeild any improvements.  

(again using 25x25 window with 10 eigenfaces found from looking at the neutral class pictures)
Using Parameters( .45, .55, .01)  = (Scale factor start = 45, end = .55. step = .01)
Was cropped to: ->   (awwww)

Parameters( ..03,.11, .001)  was cropped to ->

Marking Faces:
Using a neutral group shot, parameters (.7 .9 .05)

Using one of our class pictures with parameters (.16 .18 .05)


(Full Size Image)
Looking at the last image we can see that a common thing to be mistaken for a face was edges between two different colors, possibly the top color is being miscontrued as hair in gray scale and so in fact looks quite similar to the other face images. An attempt to mitigate this might be to disfavor pictures with sharp gradients but I did not have time to try this. The program was also thrown off when people drastically changed facial expression (like if they were yawning). Most likely this simply was because their facial expression was not easily captured by any of the eigenfaces as they were created using neutral expressions only.
Verifying Faces
Using 10 eigenfaces I tested my program's ability to match images of people smiling with that person's neutral picture. To do this I project the face I wanted to verify onto the eigenface hyper plane and examined its distance from the picture of the user I wanted to verify for. To find the best coefficient mse I tested a range of max coefficient mse values. I was looking for the value which resulted in the least mistakes which I defined to be the number of false negatives (number of times it failed to identify a smiling user picutre correctly) plus the number of false positives (number of times it mistakenly identified a smiling user pciture as belonging to someone else). I tested this by, for each user, seeing if the program could match that user to his or her smiling face pciture correctly and seeing if it correctly rejected matching a different smiling face with the user. The results were:


This results are quite reasonable. With a very low threshold we end up just accepting every picture and thus getting a lot of false positives. However as the threshold gets higher we end up rejecting almost every image and thus getting a lot of false negatives. Thus the best balance is somewhere in the middle where we try and minimize both.

For 25x25 Eigenfaces: The best threshold was 90000: Resulting in 7 false positives and 1 false negative
For 40x40 Eigenfaces: The best threshold was 180000: Resulting in 5 false positives and 3 false negatives
Extra Credit
I implemented the speed up suggestion from the write up where, instead of find the eigen vectors of AATranspose I found the eigen vectors of ATransposeA and multiplied them by A. I also found I had to normalize the resulting vectors so they remained unit vectors. This resulted in calculating the eigen values for a much smaller matrix and thus made the calculations much faster. This provided to make a huge difference to the computation speed of the eigenvetors and allowed by to try using larger the 25x25 sized Eigenfaces in my experiments. I also ran accuracy trails with eigenfaces of several different sizes.