---

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.

Principal Component Analysis

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.

Project package

You should download the source code and test faces.

1. eigenfaces: The skeleton code for the project. You can use Visual Studio (Windows) or Makefile(Linux) to compile it. (NOTE: In Visual Studio, please use the project in the release mode.)
2. faces:
   • faces > group : Has photos of students, four at a time, in neutral and interesting poses.
   • faces > neutral: Cropped faces of students in neutral expressions.
     
   • faces > interesting: Cropped faces of students in interesting expressions.

The skeleton code is large, but please take the time to get some familiarity with the classes and methods it provides. There is a lot of useful functionality included, like vector and image operations, which would take a lot of time to write yourself. The program uses a command line interface. Calling it with no arguments will produce documentation on the available commands. It should be simple to add your own functionality in case you want to tackle some extra credit, or add commands to facilitate your experimentation. At the minimum you will only need to modify two files, faces.cpp, and eigfaces.cpp, but you will still need to understand the contents of most of the other classes. Here is a description of the classes in the skeleton code. You will need to read this page to understand the organization of the code. It also gives information on numerous methods that you will need to call in your code, so please read it very carefully.

Running the code

You will need the executable main. Open the console (using the cmd command from start menu in Windows or the standard console in Linux) and navigate to the faces folder. The instructions in this section assume that the above executable is in the same folder. Hence the image paths are all relative to this location. If that is not the case, replace main with the full path to the executable - <path>\main. The code can run in following modes -

1. Computing eigenfaces:

   main --eigenfaces 10 25 25 neutral\list.txt neutral.face

   This will generate the first ten 25 pixel wide by 25 pixel high eigenfaces using the targa files listed in neutral/list.txt and save the eigenfaces database in neutral.face.


2. Projecting a face onto eigenfaces:

   main --projectface interesting\01.tga neutral.face

   This projects a face from the image interesting\01.tga onto the eigenfaces computed in the previous step (neutral.face) and re-projects the face's coefficient vector back using the eigenfaces. It generates two images - original.tga and reconstruction.tga. Former is the same image as interesting\01.tga and the latter is the reconstructed face using the eigenfaces. The reconstructed face will be very close to the original if the eigenfaces are sufficiently able to explain this face.


3. Creating a user base:

   main --constructuserbase neutral.face neutral\list.txt neutral.user

   This computes the coefficient vectors for all files in the neutral\list.txt using the eigenfaces from neutral.face and stores the results in neutral.user.


4. Is the image a face?:

   main --isface test.tga neutral.face 200.0

   This computes the MSE (mean squared error) between test.tga and its representation onto face space. If the MSE is below 200.0, it is determined to be a face, otherwise it is determined to be not a face.


5. Verify a user's face:

   main --verifyface test.tga neutral.user username neutral.face 60000.0

   This verifies whether the image test.tga is the face of the user with name username. It computes the MSE between the face's coefficients and the user's coefficients. If the MSE if below 60000, the face is determined to be the user's face. Please note that the username is all but the last 4 characters from the corresponding line in the list.txt file from which the eigenfaces (neutral.face) and the userbase (neutral.user) were created. For example, in the above steps these two were created using neutral\list.txt. So a sample username can be a line from that file minus the last four characters ('.', 't', 'g' and 'a'), for instance neutral\01. This will verify the face against the face in image - neutral\01.tga.


6. Recognizing a face:

   main --recognizeface test.tga neutral.user neutral.face 10

   This tries to match the face in the image test.tga in the user base (neutral.user) using the eigenfaces (neutral.face) and returns the top 10 matches. It does so by computing the MSE between the test face's coefficients and each user's coefficients.


7. Finding a face:

   main --findface testfindface.tga neutral.face 0.10 0.30 0.01 [crop/mark] n cropped_face.tga

   This searches the image testfindface.tga for n faces at scales 0.10 to 0.30 with step 0.01 and crops the image to the found face. The cropped image is saved in cropped_face.tga. If the command line argument is mark instead of crop, then a box is drawn around the detected face. You can assume that crop is only given when n is given as 1.

To Do: Coding

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.

1. Implement Faces::eigenFaces:

   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

2. Implement EigFaces::projectFace:

   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

3. Implement constructFace:

   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

4. Implement isFace:

   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

5. Implement verifyFace:

   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

6. Implement recognizeFace:

   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

7. Implement findFace:

   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

To Do: Experiments

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.

1. Testing recognition with cropped class images
   Procedure
   • Use the cropped, neutral students (within the neutral folder) to compute 10 eigenfaces. Show the average face and eigenfaces.
   • Use the same set of images to compute a userbase.
   • Have the program recognize the photos in the interesting images folder. You should expect only about 70% accuracy with 10 eigenfaces.
   • Experiment with the number of eigenfaces used. Try using the mean face plus 1 through 21 eigenfaces, at a granularity of 2 (this means a lot of experiments! Writing a little script will make this a lot easier!). Plot the number of faces correctly recognized versus the number of eigenfaces used.
   Questions:
   • Describe the trends you see in your plots. Discuss the tradeoffs; how many eigenfaces should one use? Is there a clear answer?
   • You likely saw some recognition errors; show images of a couple. How reasonable were the mistakes? Did the correct answer at least appear highly in the sorted results?


2. Cropping and finding faces
   Procedure
   • Use the eigenfaces file computed in the previous experiment.
   • Use your program to crop the group\test_single.tga image.
     

     main --findface group\test_single.tga neutral.face 0.35 0.55 0.05 crop 1 cropped_face.tga

     Following are results you should be getting -
     
     

     Input Image	Cropped Image

     
     
   • Find a digital picture of yourself; if you really don't have one, use any portrait on the web. Use your program to crop the picture to the face.
   • Experiment with min_scale, max_scale, and step parameters to find ones that work robustly and accurately.
   • Mark the faces in two different group photos of students. For example,
     

     main --findface group\group07.tga neutral.face 0.3 0.6 0.05 mark 4 marked_faces.tga

     Following are results you should be getting -
     
     

     Marked image

     
     Try your code with other group photos and make a note of cases where it works really well and where it doesn't, along with plausible reasons for the same.
     
     
   • Find and try another group photo. This could be of family and/or friends, or one from the web. The photo should have at least four faces. We encourage you to choose a photo where the faces are of different sizes (for example, people standing at different distances from the camera). This will help you see the effect of working with multiple scales.
     
     
   Questions
   • What min_scale, max_scale, and scale step did you use for each image?
   • Did your attempt to find faces result in any false positives and/or false negatives? Discuss each mistake, and why you think they might have occurred.


3. Verify Face
   Procedure
   • Use the eigenfaces and userbase files computed in the first experiment.
   • Have the program verify the cropped, interesting student images. Test by verifying a student's interesting face with himself or herself, as well as with someone else.
   • Experiment with various thresholds to find the one that gives the fewest false positives and fewest false negatives.
   Questions
   • What MSE thresholds did you try? Which one worked best? What search method did you use to find it?
   • Using the best MSE threshold, what was the false negative rate? What was the false positive rate?

What to turn-in

Please organize your submission in the following folder structure.

<Your_Name>                                                    [This is the top-level folder]
<Your_Name>  => Source                                  [Place the source code in this subfolder]
<Your_Name>  => Executable                            [Windows/Linux executable]
<Your_Name>  => Artifact
<Your_Name>  => Artifact => index.html            [Writeup about the project, see below for details of what to put here.]
<Your_Name>  => Artifact => images/               [Place all your images used in the webpage here.]

In the artifact webpage, please put,

• A short description of what worked well and what didn't. If you tried several variants or did something non-standard, please describe this as well.
• Describe your results of experiments listed above and answer the listed questions.
• Describe any extra credit with supporting examples.

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.

How to Turn In

Create a zip archive of your submission folder - <Your_Name>.zip and place it the Catalyst submission dropbox before May 14, 11:59pm.

Extra Credit

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!

• Implement morphing; given two images, compute an animation that shows one being transformed continuously into the other, using the eigenfaces representation. Also, try transforming an image "away" from another one, to exaggerate differences between two faces (make a face more male, more female...). Make a video from your morphed faces, e.g. using Adobe Premier. You will need to fill the function EigFaces::morphFaces in eigfaces.cpp. Run the main executable without any commands to see its command line usage.
• Try using eigenfaces to recognize images other than faces or to recognize animal faces.
• Plot recognition rates for other image resolutions. Smaller resolutions may have better recognition. Why? What's the optimal resolution for a face?
• Implement the following speedup. This is a good extra credit item to try early on, as it will reduce the time taken to do the experiments!
• Worth two extra credits. Extend eigenfaces to handle changes in illumination and/or viewpoint. You can find an additional face database that may contain such effects here.
• Worth four extra credits. Try using kernel PCA, or some non-linear variant of PCA. A good starting point is the following survey paper. Compare the results using standard PCA.
• Worth four extra credits. Try using "Sensible" PCA, as described in this paper. Compare the results to standard PCA, both in terms of efficiency of the algorithm and quality of the resulting face detection.
• Worth four extra credits. Implement real-time face detection (multiple frames per second). Here is a good reference to begin with.

---