PCA & SVM Face Recognition

Jul 08 2018 ComputerVision

PCA Introduction

PCA(Principal Component Analysis) is a common method for Dimensionality Reduction.

Algorithm Procedure

  1. centralize the sample: $x_i \leftarrow x_i - \frac{1}{m} \sum_{i=1}^{m} x_i$;
  2. compute the covariance matrix of the sample: $XX^T$;
  3. compute eigen values of the covariance matrix $XX^T$;
  4. extract top $d’$-th eigen values and its corresponding eigen vectors $w_1, w_2, …, w_{d’}$.

In this example, I use PCA algorithm to do Dimensionality Reduction among face pictures:the origin size of face pictures are $112 \times 92$ , which will be vectorize to $112 \times 92 = 10304 $ dimensional vectors. Using PCA to reduce the dimension of these vectors for our face matching later.


SVM Introduction

SVM(Support Vector Machine) is a binary classification method.

The hyperplane for classification is:

Its objective function for optimization is: ( $\alpha_i$ is the Lagrange Multiplier)

$\phi(x)$ can map $x$ to a high dimension. $K(x_i, x_j) = \phi(x_i)\cdot\phi(x_j)$ is the Kernel Function, which is used for some nonlinear classifier. Here is a list of common kernel functions:

Name Expression
Linear kernel function $K(x_i, x_j) = x_i^T x_j$
Gaussian kernel function $K(x_i, x_j) = exp(-\frac{\Vert x_i - x_j \Vert ^2}{\delta^2})$

In this example, I will use an One-VS-One Multiclass SVM method to classify the low-dimension features which we extract from PCA.


Face Recognition Procedure

  1. Vectorize every face picture ($m, n$) to ($m\times n, 1$). Suppose we have $l$ images, vectorize each image as a vector, then stack them togther, then we get a $(m \times n, l)$ matrix as our initial matrix;
  2. Centralize this matrix: compute the average of each row form a $(m \times n, 1)$ dimension vector, then let each column minus this vector to get the centralized matrx;
  3. Calculate the covariance matrix of the centralized matrix, and get its eigen values and eigen vectors, then we sort the top-k of them from largest to smallest; (we get a k-dimension eigen values here)
  4. Project the matrix to the new k-dimension feature;
  5. Train our One-VS-One Multiclass SVM model;
  6. Read the test images, then do 1 and 2 to form our test data;
  7. Use the trained model to classify test data;
  8. Compute the accuracy.

Code

For implementation details, please visit https://github.com/techping/pca-face-recognition .