In this project you will create a face recognition system. The program reduces each face image to a vector, then uses Principal Component Analysis (PCA) to find the space of faces. This space is spanned by just a few vectors, which means each face can be defined by just a set of coefficients weighting these vectors. You are given a skeleton program that provides a sophisticated command-line interface as well as most of the image and vector classes and operations you will need. Your job will be to fill in the functions that do PCA, projection into face space, determining if a vector represents a face, verifying a user based on a face, finding a face match given a set of user face information, and finding the size and position of a face in an image. This is a fairly good-sized project, so plan your time accordingly.
PCA is a technique by which we reduce the dimensionality of data points. For example, consider the space of all 20 by 30 pixel grayscale images. This is 600 dimensional space because 600 data points are required to represent the values of the 600 pixels. But suppose we only consider images that are valid faces. Such images may lie in a small subspace of the set of all images. If this subspace is a hyperplane spanned by k vectors, then we can represent any point that lies on this plane with only a set of k coefficients.
To use PCA to do pattern recognition you first take a representative sample of data points and find the subspace with the desired dimensionality that best fits the sample data. This step needs to be done only once. Once it has been done, you can determine if a new point is a valid data point by projecting it onto the subspace and measuring the distance between the point and its projection.
To use PCA for face recognition we must represent each face image as a vector of pixel values. To generate this vector the face image must be cropped and scaled, and its intensity must be normalized. The cropping can either be done by hand or by searching images for faces. This second option is only possible once the face recognition algorithm has already been trained with some input faces.
main --eigenfaces 10 25 25 neutral\list.txt neutral.face
main --projectface interesting\01.tga neutral.face
main --constructuserbase neutral.face neutral\list.txt neutral.user
main --isface test.tga neutral.face 200.0
main --verifyface test.tga neutral.user username neutral.face 60000.0
main --recognizeface test.tga neutral.user neutral.face 10
main --findface testfindface.tga neutral.face 0.10 0.30 0.01 [crop/mark] n cropped_face.tga
All the required work can be done in eigfaces.cpp and faces.cpp. The functions you must fill in are members of classes Faces and EigFaces. A Faces object stores a set of user faces loaded from images. EigFaces is derived from Faces. An EigFaces object stores a set of eigenfaces as well as the average face.
Most of the methods you will have to implement are called from main.cpp, so you should study that file closely to see how these methods are used.
Each of the items below have an upper bound on the number of lines of code needed, not including comments. If you have many more lines of code for a given step than the upper bound, then you may be doing something wrong, or at least making more work for yourself. Be sure to look in vector.h, image.h, and face.h to see what useful functions are already provided for you.
Note that points will not be taken off for making your code longer than necessary, as long as it is correct and well coded. However, you should try your best not to go too far over the upper bound, as it means unnecessary work for you and will make your code more difficult to read and harder to grade.
This method uses PCA to generate eigenfaces from the set of user faces. It takes two parameters, n, the number of eigenFaces to compute, and results, an EigFaces reference parameter where the n computed results should be stored. Use Jacobi::jacobi() to find the eigenvector. You are looking for the top n eigenvectors, so you will need to sort the eigenvectors by eigenvalue. The skeleton provides a function sortEigenValues which sorts the eigenvalues and returns an ordering so you can find the positions of the top eigenvectors in the matrix. However, you can make your own sort routine if you prefer. Once you've computed the ordering, put the top n eigenfaces into results.
Hints: You will need to store the average face in the results by calling setAverage. The matrices and vectors jacobi uses always start indices at one, so you will need to adjust for this when going between these and the Vector objects used everywhere else in the program. Here is the interface to the jacobi routine:
void jacobi(double **a, int n, double d, double **v, int *nrot);
Computes all eigenvalues and eigenvectors of a real symmetric matrix a[1..n][1..n]. On output, elements of a above the diagonal are destroyed. d[1..n] returns the eigenvalues of a. v[1..n][1..n] is a matrix whose columns contain, on output, the normalized eigenvectors of a. nrot returns the number of Jacobi rotations that were required.
Note: The n variable that is passed into the jacobi routine is different than the n that is passed in through the eigenFaces routine.
Lines required: 45
This method projects a face onto the face space to generate a vector of k coefficients, one for each of the k eigenfaces. The parameters are Face, the face to be projected, and coefficients, a reference parameter in which you must store the coefficients computed.
Lines required: 7
This method constructs a face from a vector of coefficients. The coefficients are given in a parameter and the constructed face should be stored in the reference parameter result. You should use only the first k coefficients to produce the reconstruction.
Lines required: 9
This method decides whether an image is a face. It works by projecting the face onto face space and computing the Mean Square Error (MSE) between projection and original. The parameter max_reconstructed_mse is the threshold to use in making the decision. Please return the computed MSE in the reference parameter mse.
Lines required: 10
This method decides if a face is a given user's, given coefficients computed from a different face image from that user. It works by computing the MSE between coefficients computed by projecting the face onto face space and the user's coefficients. Return the MSE in the mse reference parameter.
Lines required: 7
This method is like verifyFace, but instead sorts the userbase by closeness of the match with the face. The userbase is simply a set of names matched with coefficient vectors. Set the mse for each user in the userbase, then sort it. The best match will then be the first user in the userbase.
Lines required: 12
This method searches an image and finds the first n best faces. A struct FacePosition is included to help you out. You can use std::list to keep a list of the top best face positions. Whenever a position is found that is better than the last position in the list, insert it into the proper place in the list such that the list stays sorted, and remove the last element in the list. The exception is if there is already a face position in the list that overlaps the one you just found. In that case you must choose the one with the better face and throw the other away. (Note that this can be tricky to get to work well.)
If the parameter crop is true, then you should return the image cropped to the best face in result. Note that this result must be the same scale and resolution as the original image. If crop is false, then draw bright green boxes around each found face in the original image and return this in result. You can assume that crop will only be true when n is one.
The function should search various scales by scaling the input image for every scale between min_scale and max_scale (simply call the resample method to scale an image). The step parameter controls the distance between scale factors searched. For example, with arguments min_scale=0.1, max_scale=0.5, and step=0.05, the image scales searched will be 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45 and 0.5. You should return the best x and y face position and scale in the reference parameters provided.
Hints: To minimize processing time, only consider faces completely inside the image. Put the scaling in the outermost loop so you only have to resample the image once for every scale factor. You might want to construct and output a debug image that shows the score for every pixel position. Since your scores probably won't happen to be between 0.0 and 255.0, normalize the debug image before you save it.
You may have to do some special processing to prevent the algorithm from getting fooled by low-texture areas or areas close to face space but far from the facial mean. One possible approach is to multiply the MSE by the distance of the face from the face mean and then dividing by the variance of the face. Students in past years have also had good luck rejecting faces using color cues. Maybe you can come up with something better than this for extra credit.
A good debugging technique is to find the correct face scale yourself, and then run the search for only that scale. Once you get it working like that, then move on to getting your code working for a range of scales.
This is a complicated problem, so don't expect to get perfect results. However, you should be able to find most of the the faces in the given group images. Your code will be tested on these.
Lines required: 85
You must complete all of the following experiments to test your code. The results of each experiment, including the answers to all the questions, should be written in your write-up, along a discussion of why you think the experiment turned out the way it did, as well as any unexpected results
Note that some of the experiments may require you to run a
command over and over again. One way to accomplish this is to
use a batch file. Or, if you wish, you can easily add your own
command that takes the place of a string of commands. See the
description of class Main to find out how to do this
In the example commands, we assume that the executable main is being called from inside the faces folder. Hence all the image paths are relative to that location.
main --findface group\test_single.tga neutral.face 0.35 0.55 0.05 crop 1 cropped_face.tga
main --findface group\group07.tga neutral.face 0.3 0.6 0.05 mark 4 marked_faces.tga
If you are unfamiliar with HTML you can use a
simple webpage editor like NVU or KompoZer
to make your web-page. Here are some tips.
Create a zip archive of your submission folder - <Your_Name>.zip and place it the Catalyst submission dropbox before May 14, 11:59pm.
Here is a list of suggestions for extending the program for extra credit. You are encouraged to come up with your own extensions. We're always interested in seeing new, unanticipated ways to use this program!