7.5 Eigen Faces

Eigenfaces is a well known Principle Component Analysis (PCA) based face recognition algorithm developed by researchers at MIT [99]. A reimplementation of the Eigenfaces algorithm from researchers at Colorado State University was used in this research [28]. Though the mathematical underpinnings of Eigenfaces are complex, the entire algorithm is simple and has a structure quite amenable to streaming and high statically schedulable ILP. Training images are represented as a set of flattened vectors and assembled together into a single matrix. The Eigen vectors of the matrix are then extracted and stored in a database. The training face images are projected onto a feature space, called face space, defined by the Eigen vectors. This captures the variation between the set of faces without emphasis on any one facial region like the eyes or nose. The projected face space representation of each training image is also saved to a database. To identify a face, the test image is projected to face space using the saved Eigen vectors. The projected test image is then compared against each saved projected training image for similarity. The identity of the person in the test image is assumed to be the same as the person depicted in the most similar training image. The actual algorithm that defines the face space is:

Make Eigen Vectors(ImageList, N, M): ImageList is a set of N training images, where each image is $W\times H$ pixels. M is the number of Eigen vectors that needs to be generated.

  1. Flatten each image into a WH element vector by concatenating all the rows. Let $ImageMatrix$ be the $N\times WH$ matrix containing all the flattened images.
  2. Sum up all the rows of $ImageMatrix$ and divide by N to get an average flattened image. Call this WH element vector as $\psi$.
  3. Subtract the average image $\psi$ from the flattened images in $ImageMatrix$. Let the new $N\times WH$ matrix be $\phi$.
  4. Compute dot products of all possible image pairs. Let $L$ be the new $N\times N$ matrix where $L[i][j]$ = dot product of $\phi[i]$ and $\phi[j]$.
  5. Compute the N Eigen values and corresponding Eigen vectors of $L$. Pick the $M$ Eigen vectors corresponding to the highest Eigen values. Each Eigen Vector is N elements long.
  6. Do a matrix multiplication of each of the selected M Eigen vectors against $\phi$ and save the resulting set of $1\times WH$ sized matrices as a combined $M\times WH$ element $EigenMatrix$ in a database. Save the average image $\psi$ also to the database.
The projection algorithm follows:

Project to Face Space(Image): Image is $W\times H$ pixels in size.

  1. Let $img$ be the flattened $WH$ element vector form of Image.
  2. Load the average image $\psi$ and the $EigenMatrix$ from the database.
  3. Subtract the average image $\psi$ from $img$ to create a new image $img'$.
  4. Take the dot product of $img^{'}$ against each row of $EigenMatrix$ to obtain an M element vector $img''$.
  5. Let $norm=\sqrt{\sum_{i=1}^{M}img^{''}[i]\times img^{''}[i]}$. Divide each element of $img''$ by $norm$. This is the face space representation of Image.
Learning is a matter of projecting all the known faces to the face space and saving the projected representations and the identity of each person.

Learn Faces(ImageList, N, M): ImageList is a set of N training images, where each image is $W\times H$ pixels. A person's name is attached to each image. M is the number of Eigen vectors needed.

  1. Call Make Eigen Vectors(ImageList, N, M)
  2. For each image in $ImageList$, call Project to Face Space(image) and save the resulting projected faces to a database.
Identification is then a simple matter of projecting the test image to face space and computing a similarity score.

Identify(Image): Image is $W\times H$ pixels in size.

  1. Load the saved known projected faces from the database.
  2. proj = Project to Face Space(Image)
  3. Take the dot product of proj against each known projected face. Call this the score.
  4. The known projected face that gets the highest score is considered the identity of the test image.

Binu Mathew