In this project, we applied the concepts of linear algebra, namely vector spaces and bases, to create a set of many-dimensional vectors to exemplify and ultimately guide the recognition of faces. The main concept used was eigenvectors, which are well-suited to the problem because they described the set of non linearly independent images which best encapsulated the space of faces.

The most challening part of the project was getting the optimized eigenvector code to run. I learned that I had to normalize the scaled vectors I got in order to get MSEs which were not off the charts and projected faces which were not pure blocks of black and white (these projected faces were actually how I realized that my eigenvectors must have values that are either incredibly big or incredibly small and that I therefore needed to scale them).

As a result of writing the eigenvector code, I have a better understanding of how a space of any vectors (but most importantly, images) can be described using just a small set. Aside from gaining insight into how face detection algorithms work, I learned how basic vector operations can create really impressive results.

The code in the project uses eigenvectors to detect faces, by first building a basis and then projecting on to it, observing the resulting error. This is done by the use of matrix operations to find the eigenvectors of a matrix of vectors (to find the basis elements) and then using regular dot product operations to project onto the space of faces. Images are then scanned for the points which are most "face-like" -- the ones that differ the least from their face spacep projections. This works because the eigenvectors act as the best descriptors for the space of faces, and the closer an image is to its face representation in this space, the more likely it is to be a face.

The project is structured as follows:

• Faces::eigenFaces - this method creates a matrix from the given images and then uses eigenvector decomposition to find the best basis for these images, as well as the average face, which is like the "origin" of all faces. I actually did the extra credit, which uses clever matrix multiplication (and symmetry of the equation A * A^T * A) to make the matrix on which the eigenvalues are computed smaller.
• EigFaces::projectFace - Given the space of eigenfaces, this finds the coefficients that make the given image a part of this space. The coefficients are the components of each eigenvector used in the reconstruction of the face in face space.
• Faces::constructFace - Reconstructs a face from the given coefficients by multiplying each eigenface with its corresponding coefficients and adding them all together
• Faces::isFace - Detects if an image is a face by finding its face space projection, reconstructing it in face space from these coefficients, and computing the error between the original image and the reconstruction. This error is checked against a threshold to determine if the image is a face
• Faces::verifyFace - Similar to isFace, detects if an image is a specified user by computing the error between the given image's projection into face space and the user's projection, checking the difference error against a threshold
• Faces::recognizeFace - Finds the error between the given image and each user as above, ranks the users by lowest error to identify to which user the face belonds
• Faces::findFace - Scans the image and finds the most "face-like" regions by treating each pixel as the origin of a face and finding the regions with the smallest mean squared error.
• Faces::morphFace - Finds the face between two given faces, weighted by a distance, by projecting each face onto face space and then drawing a line between the coefficients

I followed the procedure to do the experiments. This meant writing several cmd scripts to create and then parse data. The plot of the accuracy v. number of eigenfaces is below

Q1: The number of correct matches seemed to even out at 22/23 pretty quickly. Anything above 5 eigenfaces seems to be okay, and going all the way up to 31 eigenfaces only increases the accuracy to 24 -- just a small amount. There isn't really a clear answer to how many eigenfaces to use, because there is a huge range that yields the same results

Q2: Some incorrect faces and their "best matches" appear below (this was taken from one of the "best match" image sets of 33 eigenvectors:

Each of the badly matched faces is highly distorted, which might explain the miss. For the leftmost face, the correct match appears third, for the middle, the correct match appears third, and for the rightmost face, the correct match appears sixteenth: two are close, one is not (possibly because of the distortion -- sideways angle and huge mouth)

I followed the methodology provided to do the experiments. I found pictures of myself and used a group from the class to do the experiments. My eigenfaces are below.

Q1: The scales are provided below each image as they appear

Q2: Yes, sometimes I got false positives. When I chose images with faces that were tilted to the side, smiling, or obstructed, the program would detect some (usually noisy) area as a face. A concrete example is below. I believe this occurred because the eigenfaces are perfectly straight, while the human faces are not - so an area of "interest" might be more face-like than a tilted face.

main --findface stock.tga faces10.face .5 .9 .1 mark 5 out.tga

My program works fairly well when I play around with the scale parameters and try to detect from the right photos

main --findface elf.tga faces10.face .45 .55 .01 crop 1 out.tga

main --findface me.tga faces10.face .3 .6 .05 mark 1 out.tga

main --findface class_images\group\group_smiling(5).tga eigenface .4 .9 .1 mark 3 out.tga

main --findface class_images\group\group_neutral(11).tga eigenface .4 .9 .1 mark 3 out.tga

I found that for the class images a scale of .4 to .9 by steps of .1 does the trick. For a bigger face, a smaller scale is required, which leads to error when the face needs to be shrunk down a lot to fit a 25x25 eigenface.

I wrote a batch script which verified each user against him or herself and then a batch script which verified user i against user (i+1), as this was easiest to script and, probabilistically speaking, should create results as typical as any random choice of negative matches, as the faces are ranked in no particular order

Q1: Instead of trying explicit thresholds, I collected the MSEs and used excel to compare the ranges of the thresholds. I used a binary search technique to find the optimal threshold: I would go halway between the current max and min in my head until I converged to one value

Q2: With a threshold of 88,000-90,000, the false positive rate is 6/33 and the false negative rate is 4/33

I tried to see if this technique could be used, without modification, to detect cats. To do this, I created a database of 25 cat pictures and computed the average and the eigencats.

The detector works fairly reasonably on pictures of cats which are straight on. The biggest challenge was finding pictures of cats where the heads are not tilted and the cats are not squished together enough as to obstruct each other.

For this part, I delineated between faces. This was done by computing the line between the coefficients of the projected faces and choosing the point the provided distance away. For my class morph, I used a set of 33 80x100 eigenfaces to create the most dramatic effect.

I also experimented with fewer eigenfaces. I could make faces in the whole spectrum: here are two faces with distances -.5, 0, .5, 1, and 1.5:

As expected, morphing away from a face (distance < 0 or > 1) creates a more jittery, less "face-like" face, as we are moving directly away from a face as opposed to in between two faces.

I also did the eigenface speedup as suggested in the extra credit section. The main challenge was figuring out why my eigenvectors were yielding such huge MSEs -- it was because I had forgotten to normalize!