Open Office format paper

Microsoft Word format paper

Project source code and sample images

FACIAL RECOGNITION AND IDENTIFICATION

COMS6998-3 VISUAL DATABASES

Brian Schneider CVN

May 7, 2004.

The semester long project I have worked on is a facial recognition, and identification application. Facial recognition, and identification could be used in a multitude of applications, from identifying a suspects face to a known criminal, to an alternative for a conventional password for a computer terminal. Biometrics are not easily forged in the way today's conventional passwords are (through sharing, guessing, compromising, etc). The use of biometrics as a security measure is far from a perfected science, and is an ongoing study. Therefore, as is true for any biometric security system, false positives and negatives each play a role. My implementation of facial recognition and identification is solely based on the Eigenface approach described by Matthew Turk and Alex Pentland in their paper, Eigenfaces for Recognition (http://www.cs.ucsb.edu/~mturk/Papers/jcn.pdf). Special thanks to Matthew Turk who was kind enough to answer many of my questions in reference to his method of finding a face in a large image using face space.

My application was developed and tested on Linux Red Hat 8.0 using Qt development libraries by Trolltech version 3.3.2 which can be obtained at http://www.trolltech.com/download/qt/x11.html . When installing Qt, it must be compiled with the multi threaded option on, which should also enable OpenGL. The code has not been tested on any other platforms, but I suspect that it will run with minimal to zero modifications on windows, Unix, and Mac Os X.

My application depends on a simple directory structure. The working directory of the application needs a directory called faces. The faces directory contains the facial images of the users. The format of the filenames in this directory is username-imagedescription.extension . All of the images in the face directory must have the same width and height, i.e the same number of pixels. Facial recognition works effectively when there are a large number of different faces ( > =15).

Feedback from the GUI is limited, so watching the xterm where the application is started from will give feedback as to what the application is doing. Upon application startup, the files from the faces directory are read in, and the following is displayed in the xterm:

myWidth = 92, myHeight = 112

compute average vector

compute covariance matrix

calculate eigenvectors and eigenvalues

sort eigenvalues

done sort

allocate 15 eigenfaces

eigenfaces allocated

Number of users = 40

This information is telling us the width and height of the training faces in the faces directory, along with the status of the application. It computes the average vector, which is the average face, then computes the covariance matrix from where the eigenvectors and eigenvalues are calculated. The eigenvectors are sorted from largest corresponding eigenvalues to smallest. These eignevectors are the eigenfaces used for detection and identification. The number of eigenfaces calculated is equal to the number of images in the faces directory. Not all of the possible eigenfaces are needed for satisfactory results. I have found that 15 eigenfaces suit my needs, and is the maximum number eigenfaces used. If there are fewer than 15 faces in the faces directory, the number of face images is the number of eigenfaces used.

After these values are calculated the GUI is displayed.

On the left side of the application, the most significant eigenface is displayed. The right side is the average face. This has no real significant use as far as the application is concerned, but was used for debugging purposes.

Selecting File->Add User from the menu, hitting Ctrl-A, or clicking on the icon will bring up the User Configuration Menu. This menu allows you to add and delete users, and modify the images used to describe a user. Each user can have multiple images associated with them. These images are NOT used independently. The user is described as the average of all of their images. The information displayed in the User Configuration menu is read from the faces directory. Adding and deleting faces through this menu, results in copying and deleting files to and from the faces directory. The filenames are manipulated by the application to meet the required format discussed previously.

The Combo Box on the top of the dialog box lists all of the users. Currently the user with username 1 is selected. All the faces that are associated with user 1 are in the List Box below. As can be seen this user has two associated images. The first image is currently in the faces directory, and the second is going to be added to the users profile if the OK button is clicked. The file 8.pgm will be copied into the faces directory using the filename 1-8.pgm. Images are added to a users profile by selecting the user from the Combo Box, and clicking the “...”button. All file dialogs look like the above image. When an image file is selected, the image preview is displayed on the right side of the file dialog. Images are deleted from a users profile by right clicking on the List Box item and selecting delete from the pop up menu. The delete button should work here, but time did not permit me to implement this functionality. If all images are deleted from a user profile, the user is effectively removed. Users can be added by typing a user name into the Comb Box and hitting enter. This will then cause a file dialog to appear, and an image for the user can be selected. Currently it is up to the user to select an image that is the correct width and height to be added to the database. Incorrect width and height have undefined results. This automatic scaling should be done here, but time did not permit. Hitting the OK button commits all modifications to the database, and results in a recalculation of the average face and eigenface. For large existing databases, this recalculation is not necessary, but once again, time did not permit for this logic to be implemented. The cancel button discards all changes.

Selecting File->Login from the menu, hitting Ctrl-L, or clicking on the

icon will bring up a file dialog for an image to be selected for facial recognition and identification. The directory named orl_faces has been supplied with 40 different users with multiple shots of each, downloaded from http://www.cam-orl.co.uk/facedatabase.html . The xterm displays the following information:

find face

step = 1

val = 23901011.312427 at x= 0, y=0

min_val=4888

distance = 4273791.106583, threshold = 7574177.052423

All values will be described, but for right now, we will concentrate on the last line. This tells us that the closest matching user for this image is a scalar distance away, which is less than the defined threshold for a user to match up. Therefore the GUI displays what user the image matched. In the case where a user has multiple images in their user configuration, the first image is displayed.

We can see here that the images on the left correctly match the users on the right.

The threshold and number of eigenfaces used is set so that this is not always the case. Sometimes an incorrect match is calculated.

Although these two faces look similar, they are not the same person.

These two don't look like each other at all. The accuracy of the recognition greatly depends on the number of eigenfaces used in the calculations, as well as the threshold values. The more eigenfaces used, the longer calculations take to compute, and the tighter the thresholds are to the images, the less frequently images are matched. Accuracy is increased with more eigenfaces and lower threshold.

The eigenface approach to facial recognition is also very dependent on scaling. The size of the eigenfaces must be very close to the size of the face in an image. This can be done in two ways. Either the eigenfaces can be scaled, or the image we are trying to find a matching face is scaled. Each of these methods have the same final results. The difference is where you take the performance hit. Scaling the eigenfaces adds a great deal of processing work when creating the database, and scaling the image on the fly slows down the recognition speed. My application scales the input image on the fly. Scaling is done as a function of the relation of the input image size and the size of the eigenfaces. The input image can be scaled up to two times its size. This scaling is especially useful in finding a face in a larger image.

The following is an example of the application finding my face in a larger image. During this time, my face is not part of the database (not a user in the User Configuration).

At this point, I feel that the application has found the face as good as it will, without identifying the face (correctly so). So I then hit the Stop Finding Face button. Then I right click on the found face image, and select Save Image from the pop up menu. The face image is saved with width and height of the eigenfaces. The image can then be used to create a profile for the new user in the User Configuration dialog, and subsequently be correctly recognized. While playing with the application, I found that complex backgrounds can really cause errors in finding a face. At the different scales the image is processed, very different things are found in the image that are closest to a face. Finding a face is also a very processor intensive task.

The algorithm used for finding a face in a large image is based on the enhancements described in the Eigenface for Recognition paper in the section Using “Face Space” to Locate the Face. This process is comprised of moving a window which has the dimensions of the width and height of the eigenfaces across the entire large image. This sub image calculation is done at all points in the image. The sub image that matches face space the closest is classified as a face. I do not use a threshold on the face space value, and just return the closest image. I have implemented an additional optimization because this process is so computationally intensive. Instead of moving the window one pixel at a time, the window is moved multiple pixels (number of steps is a function of the size of the image compared to the size of the eigenface). The sub image found, closest to face space is then recursed into the operation, and the step size is recalculated. The sub image is given a buffer around it the size of the step size. When the step size goes to one, the image is returned as the found face. The image is compared to all faces, and if there is a match, the process is over. If there is no match, the image is scaled larger until a face is found, or the image is scaled to two times its size. The stepping optimizations in conjunction with the Matthew Turk and Alex Pentland equation greatly increases the speed of finding a face, opposed to the brute force method discussed in the paper.

Although the eigenface approach is a great start to solving the problem of facial recognition and identification, I do not feel it is accurate enough for uses such as facial passwords as a replacement to conventional passwords. I could see this method being used in conjunction with conventional passwords, but for a front line of security, I don't feel it is consistently accurate enough. The system could also easily be tricked by a user holding an image in front of their face, or wearing a mask etc. Much work still lies in the field of facial recognition.

BIBLIOGRAPHY

Turk, Matthew, Pentland, Alex. Eigenfaces for Recognition. Massachusetts Institute of Technology, 1991.

“PCA approach.” <http://www.cs.nthu.edu.tw/~dr918308/ResearchforPCA.htm>

“Jacobi” <http://students.cs.byu.edu/~cs521/project/code/assign3/jacobi.c>