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.
Tim Danner
<tdanner@rice.edu>,
Indraneel Datta
<kashent@rice.edu>
Last modified: Fri Dec 17 20:43:02 CST 1999