Eigenface Algorithm

Constructing Eigenfaces

Eigenface algorithm is used to recognize the detected face. Here is the simple algo for eigenface:

• 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.

This procedure relies on computing eigenvectors of an extremely large matrix. If images are of 250x300 pixels, so the matrix would be 75000 by 75000 (around 5.6 billion entries). On the brighter side, there's another way (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 Lij of this matrix is the inner product of image vectors number iand 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.
• Take inner products between the image and each of the eigenfaces and pack these into a vector of length M for transforming an image to face space
• Multiply each of the elements of the face space vector with the corresponding eigenfaces, and add up the result.

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".
• 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: This process does not rely on knowing any faces, just having a set of eigenfaces.