Eigenfaces Group - Algorithmics

Constructing Eigenfaces

This procedure is a form of principle component analysis. First, the conceptually simple version:

• Collect a bunch (call this number N) of images and crop them so that the eyes and chin are included, but not much else.
• Convert each image (which is x by y pixels) into a vector of length xy.
• Pack these vectors as columns of a large matrix.
• Add xy - N zero vectors so that the matrix will be square (xy by xy).
• Compute the eigenvectors of this matrix and sort them according to the corresponding eigenvalues. These vectors are your eigenfaces. Keep the M eigenfaces with the largest associated eigenvalues.

Unfortunately, this procedure relies on computing eigenvectors of an extremely large matrix. Our images are 250x300, so the matrix would be 75000 by 75000 (5.6 billion entries!). On the bright side, there's another way (the Karhunen-Loève expansion):

• Collect the N images, crop them, and convert them to vectors.
• Compute the N by N outer product matrix (call it L) of these images. The entry L_ij of this matrix is the inner product of image vectors number i and j. As a result, L will be symmetric and non-negative.
• Compute the eigenvectors of L. This will produce N - 1 vectors of length N.
• Use the eigenvectors of L to construct the eigenfaces as follows: for each eigenvector v, multiply each element with the corresponding image and add those up. The result is an eigenface, one of the basis elements for face space.
• Use the same sorting and selecting process described above to cut it down to M eigenfaces.

Transforming an image to face space

This procedure is exactly what you would expect for the usual Hilbert space change of basis.

• Take inner products between the image and each of the eigenfaces and pack these into a vector of length M

The inverse face space transform

Again, just what you would expect.

• Multiply each of the elements of the face space vector with the corresponding eigenfaces, and add up the result.

"Learning" a face

• Transform it to face space
• Record the resulting vector (which will be much smaller than the image).

Recognizing a known face

• Transform the image presented for recognition to face space.
• Take inner products with each of the learned face space vectors (think Cauchy-Schwartz).
• If one of these inner products is above the threshold, take the largest one and return that its owner also owns the new face.
• Otherwise, it's an unknown face. Optionally add it to the collection of known faces as "Unknown Person #1".

Evaluating "face-ness" of an image

• If unsure whether an image is a face or not, transform it to face space, then do the inverse transform to get a new image back.
• Use mean-squared-error to compare these two image. If the error is too high, it isn't a face at all. Note that this process does not rely on knowing any faces, just having a set of eigenfaces.

This procedure could also serve for searching for faces in a larger image. At least, that's what the MIT people us it for.