EigenFaces

The PCA approach to face recognition, popularly known as EigenFaces happened courtesy a couple of MIT students, who decided to use hard core mathematics to derive one of the first algorithm for Face Recognition. The original paper can be found here. In principal, this Algorithm performs a linear transformation, converting a point[a face] in high dimension image space  to a point[face] in lower dimension subspace[ eigenspace].

It is one of the earliest approach in face recognition and is a fairly accurate algorithm. The one major plus point of using eigenFaces approach is that it is extremely fast, a quality desirable in real life applications. However, it does suffers from luminance variation and pose variation. It is also not suited to handle cases of partial occlusion.


Enlisting all the data structures before the algorithm ensures clarity throughout the tutorial. If you have any confusion later on in the algorithm, you can simply cross check the dimensions of the formula.

faces: n x d
       matrix in which each row is a linear array of pixels of a facial image
eigenVectors: n x n
       each row corresponds to a eigenVector of size n. They are all mutually orthogonal
eigenValues: 1 x n
       each entry is the eigenValue of the corresponding eigenVector. 
eigenPCA: k x n
       top k eigenVectors are decided based on their eigenValues and stored in eigenPCA matrix.  
eigenFaces: k x d
       affect of each eigenVector on each face in the faces matrix is stored in the eigenFaces matrix
weights:  n x k
       affect of each eigenFace on each face in the face matrix is stored in the weights matrix
affect: 1 x k
       affect of each eigenFace on the test image is stored in the affect matrix

Before stating the algorithm, it is worth mentioning that eyes, nose and eyebrows carry the bulk of the information required for identification and therefore should be in the image to give any sort of respectable accuracy. Diving head first into the algorithm, we process it in several modular steps.

1. Input-    read the training images via any imaging library and convert the training images from RGB to gray scale format. Convert each image into a pixel array and store it as a row in the faces matrix.
Various imaging libraries which can be used for this purpose are PIL, openCV etc.
                                                                                                                                                                

2. Adjusting-  calculate a mean face by taking the average of all the rows in the faces matrix. Then
subtract from each row(facial image) the mean face. We call the resultant matrix adjustedFaces.

                    adjustedFaces = faces - meanFace
                                                                                                                                                                

3. Covariance-  calculate the covariance matrix as square of adjustedFaces. If adjustedFace_tr is the transpose of the adjustedFace matrix. This is a symmetric square matrix.
         
                    covariance = adjustedFace * adjustedFace_tr
                                                                                                                                                                

4. EigenValues- calculate the eigenVectors along with their corresponding eigenValues from the covariance matrix. EigenVectors thus obtained are mutually orthogonal. Again, it is better to use a function for this step. if working with matlab, use the eig() function.

                  eigenValues,eigenVectors =linalg.eigh(covariance)

                                                                                                                                                                

5. PCA-  sort the eigenVectors in descending order according to their eigenValues. We select the top k eigenVectors and store them in a matrix eigenPCA. PCA is used to ensure that we discard the most insignificant of features. However keeping it too low a number often means a high dependency is placed on only a few features. Generally about 3/4 of the number of total EigenVectors should do the trick

                  k = ceil.(len(eigenVectors) * 0.75)
                  eigenPCA = sortedEigenVectors[:k]
Hereafter whenever  we talk about eigenVectors, we mean the ones in eigenPCA
                                                                                                                                                                

6. EigenFaces-  calculate affect of each eigenVector on each face.
             
                  EigenFaces = eigenPCA x adjustedFaces_tr
                                                                                                                                                                

7. weights- We calculate affect of each eigenFace on each face. Each row of weights matrix stores the weight of all EigenFaces for one face image. Therefore in each column, we get the weight of one eigenFace on all the faces. let EigenFaces_tr be the transpose of EigenFaces

                   weights = adjustedFaces x EigenFaces_tr

Each row of weights matrix corresponds to the feature vector for one input training image.
                                                                                                                                                                


8. Testimage- Take input the test image. Preprocess as mentioned in step 1. Store it in a vector Testimage. Calculate affect of each eigenFace on the Testimage and store it in affect vector.

                    affect = Testimage x eigenFace_tr

affect vector is the corresponding feature vector of the test image.
                                                                                                                                                                

 9.a Model- Use the rows of weight matrix(read feature vectors) to fit and train a model to help in Face Recognition later on. The model can be any machine Learning one like RBF Neural Networks, SVM. At a later stage, we input a test image's feature vector affect to the model and expect it to output if it belongs to the same person or not. 

9.b Matching- calculate distance of test image feature vector from feature vectors stored in weights matrix. Distance can be euclidean, Mahalanobis, etc. Classify image as belonging to the same person or not based on whether the distance calculated is within the threshold(a experimental value:default=1)
                                                                                                                                                                

*Algorithm ends

However the algorithm mentioned above is a classic implementation mentioned in the research paper which first introduces this technique. It is not the most efficient and accurate technique for applying Eigenfaces.
Many variants have come up which significantly outperfom the classic implementation.

In my experience, The classic implementation gives a success rate of 50-60% while an efficient implementation yielded 75% accuracy performance. Note that these are informal measures, but were performed rigorously.

side note: if you have read papers that quote >90% accuracy for any 2D face recognition algorithm, ignore their results. They are bullshit and are taken in extremely constrained environment not at all related to any real life scenario.

Alternative Implementation:

I. We can implement a different matching technique altogether once we have the eigenFaces in step 6.In this alternate version, the sequence of steps [beginning from 7] look like:

6. Let the eigenface vectors represent a logical subspace. Then this subspace is shown by the eigenFaces matrix. We project the test image in this subspace.

                                    meanEF = numpy.mean(eigenFaces,axis=0)
                                    ProjectedTestImage = (TestImage - meanEF)*eigenFaces.transpose()
_________________________________________________________________________________
                                   
7. After that, we reverse project the test image from the eigenspace to the image space. This is achieved by reversing the above steps. i.e.
           
                                    NewTestImage = (ProjectedTestImage * eigenFaces )+ meanEF
_________________________________________________________________________________
8. As a distance metric, we compare the distance between the test image and the new test image. If this distance is above a threshold distance, we classify the testImage as belonging to  a different person.

                                    dist = numpy.linelg.norm(NewTestImage - TestImage)
                                    if dist < threshold:
                                         samePerson=true
                                    else:
                                         samePerson=false
________________________________________________________________________________

II Another alternative is to perform a non linear mapping from image space to eigenspace instead of the linear mapping we currently employ. It means we change the style in which we compute the covariance matrix. We don't do a simple dot product anymore. We make use of kernels. Yes, these are the same kernels you read about in Support Vector Machines. For those who do not know about them, might consider reading /*[link]this*/ first. For our purpose, we may use either:

polynomial kernel     K = (x . y)**d   where d>0
gaussian kernel         K = e**((|x-y|**2)/2*sigma *sigma)   where sigma ->standard deviation
sigmoid kernel         K = /* Insert formula here*/

Data set:
For implementation purposes, for optimal accuracy, it is advisable to have approximately 15. images per person in your dataset . Research shows that after top 10 eigenvectors, the eigenvalues grow stagnant. A value less than 15.would mean not exploiting the eigenfaces fully while more than 15 would increase processing uselessly. Also try to ensure that in all the images of a person, the faces captured vary in expression. Basically the more varied the training data, the better result expectancy is there.

The value of k[number of eigenvectors to consider] should be chosen carefully. Ideally it should be 10 or 12. Intuitively it makes great sense as you have a dataset of 15 images of each person of which you select the top 10[which are most similar to the test image] for verification purposes. For explanation of how we zeroed in on the number 10, refer here.


Preprocessing:
To have any amount of satisfactory accuracy[i.e >70%], eigenfaces require a lot of pre-processing. The eyes and nose need to be at the same position in every image. Images should be straight[apply rotation for correction to obtain straight images]. It has been found that mouth does not contribute any significant features, therefore can be cropped out. Also apply histogram equalization to account for variable illumination across the image.
Research has shown that slightly blurred image perform better than perfect images. Therefore you may also consider applying a Gaussian filter[or any other] to blur the images slightly.

Further Reading:
A few of the famous blog posts on eigenfaces, worth reading are:

• bytefish [quality post useful when actually implementing eigenfaces]
• scholaropedia [For those comfortable with formal notations]
• article [For those who like simplified and informal theory]

Libraries:
Many libraries come with integrated Eigenfaces modules, for the ease of those who couldn't be less bothered about coding intricacies.

OpenCV in particular has a great implementation, whose details, both conceptual and coding vise can be found here. Although installing it is cumbersome, I definitely recommend downloading openCV, for prototyping EigenFaces as well as other algorithm to first check if they fit the solution requirements for the problem concerned.


To look into other face recognition algorithms, read my earlier post, here.