CSE 455 Project 2: Eigenfaces

Assigned: Friday, January 22
Due: Friday, February 5 (1:30 PM)

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 a 600-dimensional space because 600 data values are required to represent the intensities 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 (each vector must have unit length). 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.

We are providing an implementation of image resizing (with antialiasing) in my_imresize.m. This will be useful for scaling all of the face images to the same size, as well as detecting faces at multiple scales in new images. In addition, you will almost definitely need to use the built-in Matlab functions eigs or svds to perform PCA.

Input Data

The input data you will be using can be found in class_images.zip, and is divided into several sets:

• smiling_cropped: already cropped images of smiling vision students
• nonsmiling_cropped: already cropped images of vision students wearing their normal sullen expressions
• group: some group photos of students for testing face finding

Code to Write (70%)

Whenever we ask you to write a function function_name, you should put it in a file called function_name.m. Some of these functions can be implemented in one line of Matlab code. For this project, you will also need to write additional code, outside of the required functions, to set up and run your experiments.

1. (10%) Write a function eigenfaces that can be called with the command:

   [avgface eigfaces] = eigenfaces(faces,k)

   This function should use PCA to generate eigenfaces from the set of user faces. It takes two parameters, the set of faces in a cell array of images and the number of eigenfaces to compute. It should return the average face and the set of eigenfaces, in image form. For example, with 32-by-32 faces, avgface should be a 32-by-32 matrix, and eigfaces should be a 32-by-32-by-k matrix.

2. (5%) Write a function project_face that can be called with the command:

   coeffs = project_face(avgface,eigfaces,newface)

   This function should project a face onto the face space to generate a vector of k coefficients, one for each of the k eigenfaces. It takes three parameters, the average face, the set of k eigenfaces, and a new face, and returns a vector of k coefficients.

3. (5%) Write a function construct_face that can be called with the command:

   face = construct_face(avgface,eigfaces,coeffs)

   This function should construct a face from a vector of coefficients. It takes three parameters, the average face, the set of k eigenfaces, and a vector of k coefficients, and returns the reconstructed face.

4. (5%) Write a function is_face that can be called with the command:

   mse = is_face(avgface,eigfaces,face)

   This function should decide (via a continuous value) whether or not an image is a face. It works by projecting the potential face onto face space and computing the mean squared error (MSE) between the projection and the original. The function takes three parameters, the average face, the set of eigenfaces, and a new potential face, and returns the mean squared error.

5. (5%) Write a function compare_faces that can be called with the command:

   mse = compare_faces(avgface,eigfaces,face1,face2)

   This function should decide (via a continuous value) whether or not two face images are of the same person. It works by computing the MSE between coefficients computed from the two images. The function takes four parameters, the average face, the set of eigenfaces, and two new faces, and returns the mean squared error.

6. (10%) Write a function recognize_face that can be called with the command:

   order = recognize_face(avgface,eigfaces,user_coeffs,face)

   This function should sort a set of users (each represented by a set of k coefficients) by closeness to a new face, under MSE. It takes four parameters, the average face, the set of eigenfaces, a matrix of user coefficients, and a new face, and returns a list of indices into the set of users, sorted in decreasing order of similarity to the new face.

7. (25%) Write a function find_faces that can be called with the command:

   [x y s] = find_faces(avgface,eigfaces,img,n,scales)

   This function should search an image and find the n best faces. If two faces overlap, you should only report the better one. The function should search various scales by scaling the input image for every scale in array scales, returning the locations and scales of the best faces. Larger scale values should find larger faces in the image. A scale value of 1 should find faces the same size as your eigenface representation. So, if scales = 1:.1:2, you should search at the scales (1.0, 1.1, ..., 2.0); i.e. from the same size as your eigenfaces to twice as large. To minimize processing time, only consider faces completely inside the image, and put the scaling in the outermost loop. You might want to construct a debug image that shows the score for every pixel position.

   Unless you optimize heavily, your code isn't going to be particularly fast. Searching a single scale may take several minutes. Make sure you keep this in mind and plan to have enough time to run the required experiments.

   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 divide by the variance of the face. Students in past years have also had good luck rejecting faces using color cues. A good debugging technique is to find the correct face scale yourself, and then run the search on only that scale. This is a complicated problem, so don't expect to get perfect results. However, you should be able to find the faces in IMG_5888.JPG in the group directory. Your code will be tested on this.

8. (5%) Write a function draw_faces that can be called with the command:

   draw_faces(img,x,y,s)

   This function should draw the image with green rectangles around the face locations as returned by find_faces.

Hints, Tips, Requirements, Warnings

Here are some general tips, requirements, and things to watch out for that may come in handy as you are coding your project or running your experiments:

• Use eigenface size 25-by-25 or greater for your experiments. You can use smaller eigenfaces such as 15-by-15 for debugging so you won't have to wait a long time.

• If you do anything non-obvious in your code, comment it. Otherwise we won't be able to figure out what you were trying to do and won't be able to give you partial credit if it has a bug.

• To aid you in debugging it is helpful to produce debug images that you can look at and verify that the image contains what you expect. Matlab's imagesc function is good for this.

Experiments (30%)

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 writeup, along with 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. You can write a separate M-file for this, or you can loop directly in Matlab's interactive console.

Testing recognition with cropped class images (10%)

Procedure

1. Use the cropped, non-smiling students (in nonsmiling_cropped) to compute 10 eigenfaces. Show the average face and eigenfaces.
2. Try to recognize the cropped, smiling students. You should expect to get 29 out of 36 correct. Experiment with the number of eigenfaces used. Try using the mean face plus 1 through 35 eigenfaces, skipping even numbers (this is a lot of experiments). Plot the number of faces correctly recognized versus the number of eigenfaces used.

Questions

1. Describe the trends you see in your plots and discuss the tradeoffs. How many eigenfaces should one use? Is there a clear answer?
2. You likely saw some recognition errors; show a couple of these. How reasonable were the mistakes? Did the correct answer at least appear near the top of the sorted results?

Finding faces (10%)

Procedure

1. Use the 10 eigenfaces computed for the previous section to find faces in IMG_5888.JPG in the group directory, and draw green rectangles around the detected faces. You should be able to successfully find the faces.
2. Find a digital picture of yourself, and use your code to find the face.
3. Experiment with the range of scales searched by your find_faces function to find a range that works robustly and accurately.
4. Try to find all the faces in two more difficult photos. First, try IMG_5879.JPG in the group directory. Don't expect to actually find all of the faces here. Then, try another group photo of your choosing. This could be of family and/or friends, or one from the web. The photo should have at least four faces.

Questions

1. What range of scales did you use for each image?
2. Did your attempt to find faces result in any false positives and/or false negatives? Discuss each mistake, and why you think it might have occurred.

Verifying faces (10%)

Procedure

1. Use the cropped, non-smiling students to compute 6 eigenfaces.
2. Use your code (compare_faces) to verify the cropped, smiling student images in the smiling userbase. Test by verifying each student against his or her smiling face, as well as each student against a smiling face which is of someone else.
3. Experiment with various thresholds to find the one that gives the fewest false positives and fewest false negatives.

Questions

1. What MSE thresholds did you try? Which one worked best? What search method did you use to find it?
2. Using the best MSE threshold, what was the false negative rate? What was the false positive rate?

Extra Credit

• (*) 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 video from your morphed faces (Matlab makes this easy with im2frame).

• (*) Try using eigenfaces to recognize images other than faces or to recognize animal faces.

• (*) Similar to recognize_face, write a function that, instead of recognizing a particular person, detects whether or not a given face is smiling. One way to do this might be to compute two different sets of eigenfaces, one based on the smiling faces and one based on the nonsmiling faces, and see which one leads to a better reconstruction of a new image. Or you could compute a single set of eigenfaces from both smiling and nonsmiling faces, and perform the classification in coefficient space. When computing the eigenfaces, you should leave out some of the faces from the provided data and use these for testing.

• (**) Extend eigenfaces to handle changes in illumination and/or viewpoint. You can find a link to additional face databases that may contain such effects here.

• (***) Try using kernel PCA, or some non-linear variant of PCA. A good starting point is the following survey paper. Compare the results to standard PCA.

• (***) Try using "Sensible" PCA, as described in this paper by the late Sam Roweis. Compare the results to standard PCA, both in terms of efficiency of the algorithm and quality of the resulting face detection.

• (****) Implement real-time face detection. A good reference to begin with is here.

Submission

To turn in your project, submit a single zip file to the dropbox at:

https://catalysttools.washington.edu/collectit/dropbox/iansimon/8903