Face Recognition: Comparative Study between Linear [602028]

Face Recognition: Comparative Study between Linear
and non Linear Dimensionality Reduction Methods

BOUZALMAT Anissa
Sidi Mohamed Ben Abdellah
University Department of
Computer Science Faculty of
Science and Technology
Route d'Imouzzer B.P.2202
Fez 30000 Morocco
[anonimizat] BELGHINI Naouar
Sidi Mohamed Ben Abdellah
University Department of
Computer Science Faculty of
Science and Technology
Route d'Imouzzer B.P.2202
Fez 30000 Morocco
[anonimizat] ZARGHILI Arsalane
Sidi Mohamed Ben Abdellah
University Department of
Computer Science Faculty of
Science and Technology
Route d'Imouzzer B.P.2202
Fez 30000 Morocco
[anonimizat] KHARROUBI Jamal
Sidi Mohamed Ben Abdellah
University Department of
Computer Scien ce Faculty of
Science and Technology
Route d'Imouzzer B.P.2202
Fez 30000 Morocco
[anonimizat]

Abstract —In the field of face recognition, the major challenge
that encountered classification algorithms, is to deal with the high
dimensionality of the space representing data faces. M any
methods have been used to solve the issue, o ur focus, in this
paper, is to compare the efficiency (in the term of complexity and
recognition rate ) of linear and non linear dimensionality
reduction methods. We study the influence of high and low
dimensionality of features using PCA, LDA, ICA and Sparse
Random Projection.
Experiments show that projecting the data onto a lower –
dimensional subspace us ing non linear method give a high face
recognition rate.
Keywords —Face Recognition; dimensionality reduction, Gabor
Filter; Sparse Random Projection; PCA; LDA; ICA
I. INTRODUCTION
Actually, facial researches represent an important and
active topic in the fiel d of computer vision. Often, facial data
generates features with high dimension representation space.
Indeed, direct recognition with original produce a heavy
burden of computation. For that, input vectors have to be
compressed into a low dimensional featu re space before
classification.
In the literature, several methods have been proposed to
extract and to reduce the dimension of facial data. The purpose
of the extraction and the reduction procedures consist to
extract relevant data from face images.
Many features extractions methods have been used to
represent facial data, among which, Gabor filters has been
emerged as robust technique of face images representation [ 1]
[2]. However, the high dimensional Gabor feature vectors
caused the method to be compu tationally very expensive.
Researchers in face recognition have adapted many linear
and non linear technique s to this purpose . In the first category,
the widely used techniques are: the principal component
analysis(PCA), the linea r discriminant analysis ( LDA) and
Independent Component Analysis (ICA);
The PCA method [3,4,5] has many advantages when using
it as feature extraction method, but it is not suitable to perform separability of various classes. To address this inconvenient,
LDA has been proposed to make up for the deficiency of PC A
[6]. A nother method has also been offered to reduce the
dimensionality of facial data named Independent
ComponentAnalysisthat finds better basis b y recognizing the
high-order relationships between the pixels of images [7].
For the second category, R andom Projection was emerged
as non-linear and powerful method for dimensionality
reduction. It represents a computationally simple and efficient
method that preserves the structure of the data without
introducing major distortion [8].
In this work, different method: PCA, LDA, ICA,RP were
used for feature reduction and Naïve Bayes method was
usedin the classification process . Experiments were conducted
using two face databases : ORL Face Database [ 9] and the
Allfaces Database [10]
II. GABOR FILTERS
Gabor filters is used in the presentation of data at different
scales and orientations. The Extraction information is based on
the use of a bankof Gabor filters [11], 8 orientations and 5
resolutions.
The 2D Gabor filter is formed by modulating a complex
sinusoid by a Gaussian function where each filter is defined
by:

 222 2- 2-
( , , , ) exp exp * , -exp 12 2 22k x y k
Gabor x y ik x y  

 
       

The parameters that control Gabor filters are described in
[12].
The param eters (x,y) represents a 2 -dimensional input
point. The parameters µ and ν define the orientation and scale
of the Gabor kernel. ||.|| indicates the norm operator, and σ
refers to the standard deviation of the Gaussian window in the
kernel.

The wave vector K µυis defined as:
exp (2)i
kk
 

(3)kmax
k=vνf
(4)μ 8


Kmax is the maximum frequency, and fυ is the spatial
frequency between kernels in the frequency domain. In our
configuration , 5 different scales and 8 orientations of Gabo r
wavelets are used, e.g. ν € {0, …, 4} and µ € {0, …, 7}. Gabor
wavelets are chosen with the parameters :
f= 2 =π
k=max 2

III. LINEAR METHODS
In this paragraph , we describethree linear techniques of
extraction and reduction feature : Princ ipalcomponent analysis
(PCA), independent componentanalysis (ICA) and linear
discriminate analysis (LDA).
A. PCA
Turk and Pentland [13] have proposed the Principal
component analysis (PCA) as a basic tool for feature
extraction. The main advantage of this met hod is to reduce the
dimension of the data without losing much information. If we
suppose that there are P images Ii(i=l,2, –,P), each image is
denoted as a column vector xi , and the dimension is N. The
mean of the images is given by:

15P
i
ixxP

the covariance matrix of images is given by :
 
1116PT T
ii
iC x x x x XXPP   

Where
 12, ,…,P X x x x x x x    the projection space is
made up of the eigenvectors which correspond to the
significant eigenvalues when N>>P, the computati onal
complexity is increased .we can use the singular value
decomposition (SVD), theorem to simplify the computation
.the matrix X, whose dimension is N*P and rank is P, can be
decomposed as:
1
27TX U V

1
28 UX 

Where:
 1 2 1 2, ,…, , …PP diag        
, are the nonzero
eigenvalues of
TXX . And
 1 2 1 2 , , ,…, , , ,…,T
NP X X U u u u V v v v  are
orthogonal matrices.
iu
is the eigenvector of
TXX ,
ivis the eigenvector of
TXX
and the
i is the corresponding eigenvalue.
iu
is calculated by following :
11,2,…, 9ii
iU Xv i P


The d eigenvectors
12, ,…,d U u u u d P
corresponding to the d significant eigenvalues are selected to
form the projection space and the sample feature is obtained
by calculating.
B. LDA
LDA known also as Fisher’s Discriminate Analysis [14], is
another dimensionality reduction method, it gives a subspace
in which the between -class scatter (extra personal variability)
is as large as possible, while the within -class scatter
(intrapersonal variability) remains constant. Indeed, the
subspace pr oduced by LDA, discriminates the classes -faces in
optimal manner.
We have a set of C -class and D -dimensional samples:
12, ,…Nx x x

1N
of which belong to class
1w,
2N to class
2w and
cN to
class
cw , In order to find a good discrimination of these
classes we need to define a measure of separation, We define a
measure of th e within -class scatter by Eq. (10 ):
 (10)
icT
i i i
xwS x x 
  

Where :
1c
wi
iSS
 and
1
iii
xwixN

And the between -class scatter Eq. (11 ) becomes:

1(11)CT
B i i i
iSN    
  

Where :
111 C
ii i
xxNNN

Matrix
T B WS S S is called the total scatter . Similarly ,
we define the mean vector and scatter matrices for the
projected samples as:

1icT
W i i
i y wS y y 
   

1cT
B i i i
iSN    
      

Where:
11,
ii
y w yiyyNN


From our derivation for the two -class problem, we can
write:
T
BBS W S W and
T
WWS W S W
Recall that we are looking for a projection that maximizes
the ratio of between -class to within -class scatter. Since the
projection is no longer a scalar (it has C−1 dimensions), we
use the determinant of the scatter matrices to obtain a scalar
objective function Eq. (12 ):
 (12)T
BB
T
W WS W S WJWW S W S


And we will seek the projection matrix W* that maximizes
this ratio It can be shown that the optimal projection matrix
W* is the one whose columns are the eigenvectors
corresponding to the largest eigenvalues of the following
gener alized eigenvalue problem Eq. (13 ) :
* * * * *.. arg max – (13)1 2 -1TW S WBw w w w Ț S S Wii BW c TW S WW 


SB is the sum of C matrices of rank ≤1 and the mean vectors
are constrained by :
11C
i
ic

Therefore , SBwill be of rank (C−1) or less and this means
that only (C−1) of the eigenvalues 𝜆will be non -zero . The
projections with maximum class separ ability information are
the eigenvectors corresponding to the largest eigenvalues of
1
WBSS
.
We seek (C−1) projections
1,2 1,c yy by means of
( 1)c
projection vectors wi arranged by columns into a projection
matrix
1 2 1[ | | …| ]:TT
c i i W w w w y w x y W x     .
C. ICA
Barlett and. al. [7 ] has been proposed two architecture for
ICA method . The architecture 1 aimed at finding a set of
statistically independent basis images while the architecture 2
finds a factorial code. In this paper, the architecture 1 has been
used. This process involves the following two initial steps:
1. The face images in the database are organized as a
matrix X in which each row corresponds to an image.
2. The face database i s processed to obtain a reduced
dataset in order to reduce the computation efficiency of the
ICA algorithm. The reduced dataset is obtained from the first
m principal component (PC) eigenvectors of the image
database. Hence the first step is applying PCA t o determine
the m PCs, then the ICA algorithm is performed on the
principal components using the mathematical procedure
described in [ 7].
IV. NON LINEAR METHOD : RANDOM PROJECTION
Random projections consist of mapping a high
dimensional data set into a lower d imensional space. The idea
is to preserve the structure of the original data while reducing the number of dimensions it possesses. Distinct from other
methods of dimensionality reduction, this technique is quite
easy to implement (for example, to find proj ecteddata with
PCA, it is necessary to compute the covariance matrix,
calculate eigenvectors, etc… ).The random projection method
multiplies the vector of original data X n by a random matrix
RP Є Rn*k, the result is an output vector Y Є Rk : Y = RP * X .
A ma jor property of this method is that it approximately
preserves the lengths of the original points, as well as the
distances between them. We note that linear methods do not
respect local distances. This means that there are no
guarantees on whether the dis tance between a pair of points in
the original sub -space will be anywhere near the distance in
the new projected sub -space. In contrast, random projections
work by preserving all pairwise distances with a high
probability. Projections also offer formula fo r the lowest
dimension ―k‖, while other methods like PCA, LDA or PCA
do not offer such theory. Indeed, authors in [15] prove that if
we reduce dimension from n to k (k>= O(log(n)/є2)), then
pairwise distances can be preserve up to a factor of (1 ± e).
Johnson and Lindenstrauss lemma proves only the existence
of such k, and does not explicitly determine how it can be
formulated. Menon [16] presents some works explaining how
to find such an explicit formulation for the reduced dimension
―k‖.In what concer n the choice of the random projection
matrix R, Initially, it were done with a normal matrix, where
each entry Rij was an independent, identically distributed
N(0,1) variable.
Achlioptas provided two sparse matrixes [17]:
111612 23 0 (14)1 311 216ij ijp
p
r and r p
p
p   
  

Li et al. [18] propose the very -sparse projection matrix:
112
10 1 (15)
112ijps
r s ps
ps
  



Based on studies presented on [19], we will use, in the
experimental section, Achlioptas’s sparse matrix projection
defined by :
112(16)112ijp
r
p


V. SIMULATION AND EXPERIMENTS
In our experiments, the face image database used is a
collect of 40 Persons from [9] and [10]database. These face
images varies in facial expression and motion.
In ORL database [9], e ach person is represented by 10
samples, 5 images were u sed for training and 5 for test.
In all faces database [10], e ach person is represented by 20
samples , 10 images were used for training and 10 for test .
We reduced the dimension of all images to 1024 (width*
height =32*32 ) by bilinear interpolation method .
The general architecture adopted for the face recognition
task is shown in Fig. 1.

After the feature extraction methods, we apply different
reduction dimensionality methods. It refers to the process of
taking a data set with a certain number of dimensions, and
creating a new data set with a lower number of dimensions ;
the goal is to capture only pertinent information.
In the classification process , we use the Naive
Bayes algorithm offered by the Weka tools [20].This one can
be trained very efficiently in a supervised learning setting . The
principle of naive Bayes classifier is combining probability
model with decision rule. His major advantage is that it
requires only small training data to estimate necessary
parameters for classification.
In thefollowing , we will compare the influence of the
feature’s d imension ( high and low ) using PCA, LDA, ICA an d
Sparse Random Projection. As low dimension, we consider
the original data extracted from face images and as high
dimension, we consider generated data obtained after the
introduction of the extraction method Gabor filters that
produce s a vector of more than 40000 attributes .
The experiment s were done on a Pentium 4 , 2 GHz, 1 GO
RAM.
Tables (I, II, III, IV ) bellow show the obtained results (in
term of efficiency and time of execution) when considering
data with different dimensions values.

TABLE I. RESULTS BEFORE APPLYING GABOR FILTER S (ALLFACES
DATABASE )
All faces
Database (Original features N=32*32)

Linear method Non Linear method RP
Dimension
(N)
PCA
N=400

LDA
N= 39
ICA
N=400 N=1000 N=700 N=500 N=260
Efficience
(%)
89,4 66,4 73,2 96 93 90,8 85
Time
execution
( Second) 30 s 22 32,3 16,11 18,13 21,2 22,43

TABLE II. RESULTS BEFORE APPLY ING GA BOR FILTERS (ORL DATABASE )
ORL
Database (Original features N=32*32)

Linear method Non Linear method RP
Dimension
(N)
PCA
N=200

LDA
N= 39
ICA
N=200 N=1000 N=700 N=500 N=260
Efficience
(%)
91,4 60 87 98 95,22 92,5 90
Time
execution
( Second) 21,3 17 22,1 10,31 13,8 15,5 16,8

Tables (I, II) use original data (wit hout introducing Gabor
filters).
According to the Tables (I,II) , we remark that the
efficiency and the time of execution changes according to the
dimension .
When we increase the dimension on the RP method the
efficiency becomes important and the time of execution
becomes small , we can also remark that the efficienc y of the
RP method (whe n N = 1000 , N = 700 , N=500 ) is more
effective compared to PCA, LDA and ICA methods. In
contrast, the efficiency of PCA is better than RP when N=260.

Tables (III, IV ) show the obtained results after applying
Gabor filters (the dimension of feature vectors become
N=40960 ).
TABLE III. RESULTS AFTER APPLYING GABOR FILTERS (ALL FACES
DATABASE ALL)
All faces
Database (Gabor features N=40960)

Linear method Non Linear method RP
Dimension
(N)
PCA
N=400

LDA
N= 39
ICA
N=400 N=1000 N=700 N=500 N=260
Efficience
(%)
88,7 77,14 83,1 96,44 94 91,8 80,67
Time
execution
( Second) 80 44,2 62,3 22,11 30 34,2 32,43
Dimensional ity
reduction using:
PCA, LDA, ICA
and RP Classification Originaldata
n=1024
Applying Gabor
filters
N = 40960

TABLE IV. RESULTS AFTER APPLYING GABOR FILTERS (ORL DATABASE )
ORL
Database (Gabor features N=40960)

Linear method Non Linear method RP
Dimension
(N)
PCA
N=200

LDA
N= 39
ICA
N=200 N=1000 N=700 N=500 N=260
Efficience
(%)
94 80 90 98,23 97,11 96,5 84,6
Time
execution
( Second) 43 23,8 35,3 12,6 18 20,4 25

When applying Gabor filter , we observe that the efficiency
of the RP method (when N = 1000 , N = 700 , N=500) gives a
good performance compared to PCA, LDA and ICA methods.
In contrast, the efficiency of PCA and ICA is better than RP
when N=260.
We can also remark an improvement in the term of the
recognition rate accuracy in Table s (III, IV) compared to
results obtained in Table s (I, II) and w hen we incre ment the
dimension on the RP method the efficiency becomes
important and the time of execution becomes small .
VI. CONCLUSION
We have presented, in this paper, a comparative study
between different methods for dimensionality reduction . We
have concluded that RPis an optimal method, which is able to
operate quickly even when the number of dimen sions that we
are working with was very high.
These results are due to the reduction process of PCA,
LDA and ICA being to capture the directions of maximal
variance and project the data onto these directions, which
means that, local distances were not respected. In other word,
the distance between any pair of points may be arbitrarily
distorted.
In the term of complexity, PCA, LDA and ICA have a
runtime that depends on the number of original dimensions,
which means that when th is one grows , algorithms take too
long time to run. In contrast, random projections involve only
a matrix multiplication. We realize that random projections
have a much better runtime.
References
[1] R.Rao and D.Ballard. ―An active vision architecture based on iconic
representations‖, Artificial Intelligence, pp.461 -505,1995.
[2] B.Schiele and J.Crowley. ―Recognition without correspondence using
multidimensional receptive field histograms‖. On Computer
Vision,2000.
[3] L. Sirovich and M. Kirby. Low -dimensional procedur e forthe
characterization of human faces. Journal of the OpticalSociety of America A – Optics, Image Science and Vision,4(3):519 –524, March
1987.
[4] M. Kirby and L. Sirovich. Application of the karhunenloeve procedure
for the characterization of human faces.IEEE Transactions on Pattern
Analysis and Machine Intelligence, 12(1):103 –108, 1990.
[5] M. Turk and A. P. Pentland, ―Eigenfaces for recognition‖,Journal of
Cognitive Neuroscience, vol. 3, no. 1,pp. 71–86,1991.
[6] P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman,―Eigenfaces vs.
Fisherfaces: recognition using classspecific linear projection‖, IEEE
Transactions on PatternAnalysis and Machine Intelligence, vol. 19, no.
7,pp. 711 –720, 1997.
[7] M. Bartlett, J. Movellan, and T. Sejnowski. Facerecognition by
indepe ndent component analysis. IEEETrans. on Neural
Networks,13(6):1450 –1464, November2002.
[8] Aditya Krishna Menon, ―Random projections and applications
todimensionality reduction‖, Phd thesis, School of
InformationTechnologies The University of Sydney Australia, 2007 .
[9] ORL, 1992. The ORL face database at the AT&T (Olivetti) Research
Laboratory. Available from :
http://www.uk.research.att.com/facedatabase.html
[10] "Essex face database –allface s", University of Essex, UK, http://cswww.
essex.ac.uk/mv/allfaces/index . html.[allfaces] "Essex face database –
allface s", University of Essex, UK, http://cswww.
essex.ac.uk/mv/allfaces/index. html.
[11] J.Essam Al Daoud, ‖Enhancement of the Face Recognition Using a
Modified Fourier -Gabor Filter‖,Int. J. Advance.Soft Comput.Appl., Vol.
1, No. 2, 2009.
[12] AnissaBouzalmat, NaouarBelghini, ArsalaneZarghili, Jamal
Kharroubi&AichaMajda, » Face Recognition Using Neural Network
Based Fourier GaborFilters & Random Projection»International Journal
of Computer Science and Security (IJCSS), Volum e (5) : Issue (3),
2011.
[13] [M. A. Turk and A. P. Pentland, "Face Recognition Using Eigenfaces,"
in IEEE CVPR), 1991,pp. 586 -591.
[14] P. N. Belhumeur, J. P. Hespanha et D. J. Kriegman, "Eigenfaces vs.
Fisherfaces recognition using class specific linear projection ", IEEE
Transactions on Pattern Analysis and Mac hine Intelligence,19(7),
pp.711 –720, 1997 .
[15] W.B. Johnson and J. Lindenstrauss, ―Extensions of Lipschitz mappings
into a Hilbert space‖, Conference in Modern Analysis and Probability,
pages 189 –206, 1984.
[16] Adity a Krishna Menon, ―Random projections and applications to
dimensionality reduction‖, Phd thesis, School of Information
Technologies The University of Sydney Australia, 2007.
[17] Dimitris Achlioptas, ―Database -friendly random projections:Johnson –
Lindenstrauss wi th binary coins‖, Journal of Computer and System
Sciences, 2003.
[18] Ping Li, Trevor J. Hastie, and Kenneth W. Church.―Very sparse random
projections‖. In KDD ’06: Proceedings of the 12th ACM SIGKDD
.international conference on Knowledge discovery a nd data min ing,
2006, p 287 –296.
[19] N. Belghini, A. Zarghili, J. Kharroubi, A. Majda, ―Sparse Random
Projection and Dimensionality Reduction Applied on Face
Recognition‖, International Conference on Intelligent Systems & Data
Processing, Gujarat, India : 2011. pp. 78 -82.
[20] On line : http://www.cs.waikato.ac.nz/ml/weka