Face recognition is an important problem in computer vision. For this
project, we implemented face recognition with eigenfaces. First, we took
a set of sample faces (as w x h images) which could be treated as vectors
in wh dimensional space. Thus, the faces form a lower dimensional space
embedded in this larger space (wh dimensional space). To find a basis for
the smaller space, we can use PCA
(
principle component analysis
). In this, we compute a matrix, A, of dimension
(wh x m) from the input faces where m is the number of faces. Then, by
computing the eigenvectors of AAT, we can compute a basis
for the space of faces. Then, by taking the vectors with the largest
eigenvalues, we can approximate the space of faces with a small number of
basis vectors. Then, we can represent a face, x as
x = xaverage + a1 v1 + ...
+ ak vk where the vs are eigenvectors and the as
are coefficients. As we can see, this process can be sped up by considering
the eigenvectors of ATA.
Implementation
There are several methods in the code that important for the computation of
eigenfaces.
Faces::eigenFaces - This method finds the eigefaces using PCA
as described above or using the speedup described in the extra credit
section. It uses a built in method that computes the eigenvectors of
matrix using the
Jacobi method
. Then, these eigenvectors and the average face from the sample
set are stored.
EigFaces::projectFace - Given our eigenfaces, this method
projects a face onto the space of faces by computing the magnitude of
the coefficients of the eigenvectors required to reconstruct the face.
EigFaces::constructFace - This converts a coordinate vector
into a face image by multiplying the coordinates by the eigenvectors
EigFaces::isFace - This method projects an image into the
space of faces and reconstructs the image from the coordinates and
then computes the mse (mean squared error) between the original and
reconstructed images.
EigFaces::verifyFace - This method determines if a specified
face belongs to a specified user. This is done by projecting the known
user's face and the candidate face into the space of faces and then
computing the mse between the coefficient vectors.
EigFaces::recognizeFace - This method takes an input face and
ranks the most likely "owner" of that face from a list of known users.
EigFaces::findFace - This method searches over an image and
finds the n most likely locations of a face in the image and either
marks them or crops the image to the "best" solution to the face problem.
Challenges
The hardest part of this project was dealing with the horrible
documentation of the code. The mathematics was easy enough to follow, but
the hardest bug to find was due to the fact that Image::Crop and Face::SubImage
did not do the same thing, though their method signatures seemed to suggest that
they would.
Experiments
Testing Recognition with Cropped Class Images
In this experiment we computed 10 eigenfaces from our set of faces.
The faces are shown below, along with the average face.
With these eigenfaces, we achieved an accuracy of 24 out of 33 images.
Graphing the performance of the recognizer against the number of
eigenfaces yields the graph below:
Questions
As the number of eigenfaces increase, the number of faces that are
correctly recognized tends to increase with a few small decreases of 1
face recognized. However, the increase is highest for the first few
faces and plateaus around face 5. This follows the intution behind
the ordering of our eigenfaces: The vectors that we add initially are
the most important as they have the highest eigenvalues. The later
eigenfaces have lower eigenvalues and thus are not as important to the
overall representation of the face. There's not a clear answer as to
how many eigenfaces are needed. It's pretty clear that, beyond 20
eigenfaces, the gain is virtually nonexistent. However. Note that the
performance at 9 eigenvectors is at least as good as the performance
of 10 to 20 eigenvectors and is often much better.
Many of the recognition errors were reasonably small in the the actual
matching face was pretty high up on the list. An instance of this is when
the algorithm mistook the following face
for this image
rather than
Note that the lips in the first and second image are similar where as
the lips differ between the first and third images. Additionally, the
curvature of the bottom left of the image of the first two images makes
it unsurprising that algorithm made a mistake here.
Cropping and finding faces
In this experiment, we computed 10 eigenfaces and then used them to crop
elf.tga, shown below:
The cropped image looks like this
The algorithm also recognizes two faces as shown below
I decided that I couldn't find a portrait of myself on the
web, so I just cropped a test image so that it looked like a
portrait. The image is shown below
Below are results from all of the groups
And here is the test image
Questions
For the elf image, I scaled from 0.45 to 0.55 by 0.01 as the
instructions stated. For the group shots, I scaled from 0.5 to 1
by 0.1. For the test image and the portrait derived from the test image,
I scaled from 0.1 to 0.5 by 0.01.
I was fortunate enough to not have any errors in the final images.
However, when I used an improper scale, I often found some errors,
in the image. To deal with these errors, I varied the scale range,
which made it much easier to find faces. Earlier, my algorithm only
achieved 50% accuracy on the group images. However, this accuracy
increased to 100% on the group images after I used image.crop instead
of face.subImage when I extracted a candidate face in findFaces. This is
Verify Face
In this experiment, we created a set of 6 eigenfaces and a userbase
from the set of netural faces. Then, we ran the recognition method
against a smiling face belonging to that person and a smiling face
that belongs to another person.
Questions
I wrote a script to do the experiment listed above. Then, I collected
the MSEs over several runs. With a little bit of scripting, I was able
to sort the MSEs for the proper matches and the mismatches. Thus, I had
two ascending lists of errors. To find the error that minimize the total
number of misclassifcations, for each MSE in the
list of proper matches, I computed the error rate given a threshold at
that MSE (in both the proper matches and the mismatches) and then took
the lowest error rate over all thresholds. The
best MSE threshold was 100000.
Using the best threshold, I correctly recognized 29 of the 33 faces,
falsely rejecting 4 of the 33 faces. I also correctly rejected 28 of
the 33 faces, falsely rejected 5 of the faces.
Extra Credit
A small speedup
Computing the eigenvectors of AAT is very costly as it is a
wh x wh matrix. For a 50x50 image, this is a 2500 dimensional space. As
most matrix operations are O(n2) or O(n3), this is
incredibly expensive.
Given that we can vary the size of the image, but the
number of training images is fixed, we should instead compute the
eigenvectors of ATA, which is an m x m matrix. By doing this,
we can easily vary the height and width of the eigenfaces. This works
because the rank of AAT is equal to the rank of ATA.
Morphing faces
We can treat any two faces as vectors x and y in the space.
Then, we can draw a line between the two vector by using the equation
tx + (1-t)y. Thus, by evaluation this function at points
between the two faces, we can morph one face into another as shown below.
In this animation, we morph from my face into my friend's face and beyond.
Note that you will need a browser with Javascript to view this animation.
for this image
rather than
Note that the lips in the first and second image are similar where as
the lips differ between the first and third images. Additionally, the
curvature of the bottom left of the image of the first two images makes
it unsurprising that algorithm made a mistake here.
