Face Recognition by Eigen Faces Algorithm

Question

I have $1200$ face images in my training set. There are $2989$ test face images. I am using eigenfaces (PCA) for feature extraction and $k$-means clustering. I even tried all $2989$ test face images as training set images, but no accuracy is achieved.

Source code i tried:

tic

clear all
close all
clc
% number of images on your training set.
M=100;

% Chosen std and mean. 
% It can be any number that it is close to the std and mean of most of the images.
um=60;
ustd=32;

% read and show images(bmp);
S=[];   %img matrix

for i=1:M
    str=strcat(int2str(i),'.jpg');   %concatenates two strings that form the name of the image
    eval('img=imread(str);');

       [irow icol d]=size(img); % get the number of rows (N1) and columns (N2)
       temp=reshape(permute(img,[2,1,3]),[irow*icol,d]);     %creates a (N1*N2)x1 matrix
    S=[S temp];         %X is a N1*N2xM matrix after finishing the sequence
                        %this is our S
end


% Here we change the mean and std of all images. We normalize all images.
% This is done to reduce the error due to lighting conditions.
for i=1:size(S,2)
    temp=double(S(:,i));
    m=mean(temp);
    st=std(temp);
    S(:,i)=(temp-m)*ustd/st+um;
end

% show normalized images

for i=1:M
    str=strcat(int2str(i),'.jpg');
    img=reshape(S(:,i),icol,irow);
    img=img';


end


% mean image;
m=mean(S,2);   %obtains the mean of each row instead of each column
tmimg=uint8(m);   %converts to unsigned 8-bit integer. Values range from 0 to 255
img=reshape(tmimg,icol,irow);    %takes the N1*N2x1 vector and creates a N2xN1 matrix
img=img';       %creates a N1xN2 matrix by transposing the image.

% Change image for manipulation
dbx=[];   % A matrix
for i=1:M
    temp=double(S(:,i));
    dbx=[dbx temp];
end

% Covariance matrix C=A'A, L=AA'
A=dbx';
L=A*A';
% vv are the eigenvector for L
% dd are the eigenvalue for both L=dbx'*dbx and C=dbx*dbx';
[vv dd]=eig(L);
% Sort and eliminate those whose eigenvalue is zero
v=[];
d=[];
for i=1:size(vv,2)
    if(dd(i,i)>1e-4)
        v=[v vv(:,i)];
        d=[d dd(i,i)];
    end
 end

 % sort,  will return an ascending sequence
 [B index]=sort(d);
 ind=zeros(size(index));
 dtemp=zeros(size(index));
 vtemp=zeros(size(v));
 len=length(index);
 for i=1:len
    dtemp(i)=B(len+1-i);
    ind(i)=len+1-index(i);
    vtemp(:,ind(i))=v(:,i);
 end
 d=dtemp;
 v=vtemp;


% Normalization of eigenvectors
 for i=1:size(v,2)       %access each column
   kk=v(:,i);
   temp=sqrt(sum(kk.^2));
   v(:,i)=v(:,i)./temp;
end

% Eigenvectors of C matrix
u=[];
for i=1:size(v,2)
    temp=sqrt(d(i));
    u=[u (dbx*v(:,i))./temp];
end

% Normalization of eigenvectors
for i=1:size(u,2)
   kk=u(:,i);
   temp=sqrt(sum(kk.^2));
    u(:,i)=u(:,i)./temp;
end


% show eigenfaces;

for i=1:size(u,2)
    img=reshape(u(:,i),icol,irow);
    img=img';
    img=histeq(img,255);

end


% Find the weight of each face in the training set.
omega = [];
for h=1:size(dbx,2)
    WW=[];    
    for i=1:size(u,2)
        t = u(:,i)';    
        WeightOfImage = dot(t,dbx(:,h)');
        WW = [WW; WeightOfImage];
    end
    omega = [omega WW];
end
toc
tic
% Acquire new image
% Note: the input image must have a bmp or jpg extension. 
%       It should have the same size as the ones in your training set. 
%       It should be placed on your desktop
ed_min=[];
srcFiles = dir('F:\mat2012 instaled\bin\database\100 trainingset\test\*.jpg');  % the folder in which ur images exists


for b = 1 : length(srcFiles)
    filename = strcat('F:\mat2012 instaled\bin\database\100 trainingset\test\',srcFiles(b).name);
    Imgdata = imread(filename);
    %figure, imshow(Imgdata);

        InputImage=Imgdata;

InImage=reshape(permute((double(InputImage)),[2,1,3]),[irow*icol,1]);
temp=InImage;
me=mean(temp);
st=std(temp);
temp=(temp-me)*ustd/st+um;
NormImage = temp;
Difference = temp-m;

p = [];
aa=size(u,2);
for i = 1:aa
    pare = dot(NormImage,u(:,i));
    p = [p; pare];

end

InImWeight = [];
for i=1:size(u,2)
    t = u(:,i)';
    WeightOfInputImage = dot(t,Difference');
    InImWeight = [InImWeight; WeightOfInputImage];
end
noe=numel(InImWeight);

z(b,:)=InImWeight;

end


IDX = kmeans(z,5)
clustercount=accumarray(IDX, ones(size(IDX)));
%disp(clustercount);
toc

5 different faces are shown below.

Unfortunately, images are not clustered properly. Same faces should be clustered, but different faces are being clustered.

1. Should I have to use still more face images for training?

2. How can accurate clustering be achieved? What is the solution?

Answer 1

Let's review the steps to replicate the Eigen Faces using PCA for face recognition.
The data structure is $ \boldsymbol{X} \in \mathbb{R}^{D \times N}, \; \boldsymbol{y} \in \mathbb{R}^{D} $ where $ D $ is the number of pixels per image, $ N $ is the number of images and $ \boldsymbol{y} $ is the face label (Class).
It requires to column stack the image.
It is also assumed values of the image are in the range [0, 1].

1. Pre Process
   Calculate the mean per feature (Pixel location).
   Remove the mean.
   You may normalize each feature to have a unit standard deviation.
2. Calculate the Covariance Matrix
   Given the data structure the covariance matrix is given by $ \boldsymbol{C} = \frac{1}{N} \boldsymbol{X} \boldsymbol{X}^{T} $.
3. Calculate the Eigen Decompositions (Spectrum) of the Covariance Matrix
   Calculate the eigen decomposition of the covariance matrix: $ \boldsymbol{C} = \boldsymbol{U}^{T} \boldsymbol{\Lambda} \boldsymbol{U} $.
4. Build the Encoder
   Set the number of dimensions, $ d $, of encoded data $ \boldsymbol{Z} \in \mathbb{R}^{d \times N} $. Build the encoder decoder matrix $ \boldsymbol{U}_{d} $ by the $ d $ eigen vectors which matches the $ d $ largest eigen values.
5. Encode Data
   Generate the encoded data matrix $ \boldsymbol{Z} = \boldsymbol{U}_{d}^{T} X $.
6. Per Class Mean
   Calculate the mean coordinates per face (Class).

Now, when there is a new image:

1. Pre Process
   Apply it the same pre processing as all other images (Shift and optimally scaling).
2. Calculate Distance
   Calculate its distance to each class mean.

Now, look for the class with the smallest distance.
If the distance is below a faceRecThr then it is labeled to have the same class. If the distance is above faceRecThr yet below faceThr it it will be labeled as a new class and if it is above faceThr then it is classified as no face image.

The way to optimize the thresholds is by looking at the histograms of the intra class distance and inter class distance.

We also optimized the parameter d according to the separability between the inter and intra class distance.

Using K-Means

You could use K-Means to get the clusters centers.
Yet in that case, the cluster might be composed by other classes as well. So this method will be better.
You may use K-NN with K>3 as the classifier with some logic on the distances.

The code is available at my StackExchange Codes Signal Processing GitHub Repository (Look at the SignalProcessing\Q16709 folder).