# Extraction and Recognition of Nonlinear Interval-Type Features Using Symbolic KDA Algorithm with Application to Face Recognition

Authors: P. S. Hiremath; C. J. Prabhakar
Journal: Research Letters in Signal Processing
 (2008)

---

## Abstract

We present symbolic kernel discriminant analysis (symbolic KDA) for face
recognition in the framework of symbolic data analysis. Classical KDA extracts features, which are single-valued in nature to represent face images.
These single-valued variables may not be able to capture variation of each feature in all the images
of same subject; this leads to loss of information. The symbolic KDA algorithm extracts most
discriminating nonlinear interval-type features which optimally discriminate among the classes
represented in the training set. The proposed method has been successfully tested for face
recognition using two databases, ORL database and Yale face database. The effectiveness of the proposed
method is shown in terms of comparative performance against popular face recognition methods
such as kernel Eigenface method and kernel Fisherface method. Experimental results show that
symbolic KDA yields improved recognition rate.


---

## Body

## 1. Introduction

Kernel principal
component analysis (KPCA) [1, 2]
and kernel Fisher discriminant analysis (KFD) [3] have aroused
considerable interest in
the face recogniation problem.  KPCA was originally developed by
Schölkopf et al., in 1998, while KFD was first proposed by Mika et al., in 1999
[3]. Subsequent research saw the development of series
of KFD algorithms. The KFD based algorithms use the pixel intensity values in a face image as
the features for
face recognition. The pixel intensities that are used as features are represented by single
valued variables. However, in many situations same face is captured in different orientation,
lighting, expression and background, which all lead to image variations. The
pixel intensities
do change because of image variations. The use of single valued variables may not be able to
capture the variation of feature values of the images of the same subject. In such a case,
we need to consider the symbolic data analysis (SDA) [4–7],
in which the interval-valued data are
analyzed.In this paper, new appearance based method is proposed in the framework of symbolic data
analysis, namely, symbolic KDA for face recognition, which is a generalization of the
classical KDA to symbolic objects. In the first step, we represent the face images as symbolic
objects (symbolic faces) of interval type variables. Each symbolic face summarizes the
variation of feature values through the different images of the same subject. It also drastically
reduces the dimension of the image space without losing a significant amount of information.In the second step, we apply symbolic KDA algorithm to extract interval type nonlinear
discriminating features. According to this algorithm, in the first phase, we apply kernel
function to symbolic faces, as a result a pattern in the original input space is mapped into a
potentially much higher dimensional feature vector in the feature space, and then performs in
the feature space to choose subspace dimension carefully. In the second phase, we extract
interval type nonlinear discriminating features, which are robust to variations due to
illumination, orientation and facial expression. Finally, minimum distance classifier with
symbolic dissimilarity measure [4] is employed for classification.The remainder of this paper is organized as follows: In Section2, the idea of constructing
the symbolic faces is given. Symbolic KDA is developed in Section 3. In Section 4, the
experiments are performed on the ORL and Yale face database whereby the proposed
algorithm is evaluated and compared with other methods. Finally, conclusion and discussion
are given in Section 5.


## 2. Construction of Symbolic Faces

LetΩ={Γ1,…,Γn} be the collection of n face
images of the database, each of size N×M,
which are first-order objects. Each object Γl∈Ω, l=1,…,n, is described by a
feature vector (Y˜1,…,Y˜p) of length p=NM, where each component Y˜j,j=1,…,p, is a single-valued variable representing the
intensity values of the face image Γl.
An image set is a collection of face images of m different subjects (face classes) and each subject has different
images with varying expressions, orientations, and illuminations. Thus there
are m number of second-order objects
(face classes) denoted by E={c1,c2,…,cm},
each consisting of different individual images, Γl∈Ω,
of a subject. We have assumed that images are belonging to a face class and are arranged
from right-side view to left-side view. The view range of each face class is
partitioned into q subface classes and each subface class contains r number of
images. The feature vector of kth subface class cik of ith face class ci,
where k=1,2,…,q, is described by a vector of p interval variables Y1,…,Yp,
and is of length p=NM.
The interval variable Yj of kth subface class cik of ith face class is described as(1)Yj(cik)=[x¯ijk,x¯ijk], where x¯ijk and x¯ijk are minimum and maximum intensity values,
respectively, among jth pixels of all the images of subface class cik.
This interval incorporates variability of jth feature inside the kth subface class cik.We denote(2)Xik=(Y1(cik),…,Yp(cik)),i=1,…,m,k=1,…,q. The vector Xik of interval variables is recorded for kth subface class cik of ith face class. This vector is called as symbolic face and is represented as
(3)Xik=(αi1k,…,αipk), where αijk=Yj(cik)=[x¯ijk,x¯ijk],j=1,…,p, and k=1,…,q;  i=1,2,…,m.We represent theqm symbolic faces by a matrix X of size (p×qm),
consisting of column vectors Xik, i=1,…,m,k=1,…,q.


## 3. Acquiring Nonlinear Subspace Using Symbolic KDA Method

Let us consider the matrixX containing qm symbolic faces pertaining to the given set Ω of images belonging to m face classes. The centers xijkC∈ℜ of the intervals αijk=[x¯ijk,x¯ijk] are given by
(4)xijkC=x¯ijk+x¯ijk2, where k=1,…,q,  i=1,…,m, and j=1,…,p.Thep×qm data matrix XC containing the centers xijkC∈ℜ of the intervals for qm symbolic
faces. The p-dimensional vectors XikC=(xi1kC,…,xipkC), X¯ik=(x¯i1k,…,x¯ipk), and X¯ik=(x¯i1k,…,x¯ipk) represent the centers, lower bounds, and upper bounds of the qm symbolic faces Xik,
respectively.LetΦ:ℜp→F be a nonlinear mapping between the input space
and the feature space.The nonlinear mapping,Φ, usually defines a kernel function. Let K∈ℜqm×qm define a kernel matrix by means of dot product
in the feature space:
(5)Kij=(Φ(Xi)⋅Φ(Xj)). In general, the
Fisher criterion function in the feature space F can be defined as
(6)J(V)=VTSbΦVVTSwΦV, where V is a discriminant vector, SbΦ and SwΦ are the between-class scatter matrix and the within-class
scatter matrix, respectively. The between-class scatter matrix and the within-class
scatter matrix in the feature space F are defined below:
(7)SbΦ=1m∑i=1mqi(miΦ−m0Φ)(miΦ−m0Φ)T,SwΦ=1qm∑i=1m∑k=1q(Φ(XikC)−miΦ)(Φ(XikC)−miΦ)T, where XikC denotes the kth symbolic face of ith face class, qi is the number of training symbolic faces in
face class i, miΦ is the mean of the mapped symbolic faces in
face class i,
and m0Φ is the mean across all mapped qm symbolic faces. From the above definitions, we
have StΦ=SbΦ+SwΦ.
The discriminant vectors with respect to the Fisher criterion are actually the
eigenvectors of the generalized equation SbΦV=λStΦV.
According to the theory of the reproducing kernel, V will be an expansion
of all symbolic faces in the feature space. That is, there exist coefficients bL⁢(L=1,2…,qm) such that
(8)V=∑L=1qmbLΦ(XikC)=HA, where H=(Φ(X11C),…,Φ(X1qC),…,Φ(Xm1C),…,Φ(XmqC)) and A=(b1b2⋯bqm).Substituting (8)
into (6), we can obtain the following equation:
(9)J(A)=ATKWKAATKKA, where K is a kernel matrix, W=diag(W1⋯Wm),Wi is a qi×qi matrix whose elements are 1/qi. From the definition of W, it is easy to
verify that W is a qm×qm block matrix. In fact, it is often necessary
to find s discriminant vectors, denoted by a1,a2,…,as,
to extract features. Let V=[a1,a2,…,as].
The matrix V should satisfy the following condition:
(10)V=arg⁡max⁡V(|VTS˜bV||VTSt˜V|), where S˜b=KWK and S˜t=KK.Since, each
symbolic faceXik is located between the lower bound symbolic
face X¯ik and upper bound symbolic face X¯ik,
it is possible to find most discriminating nonlinear interval-type features [B¯ik,B¯ik].The lower bound features of each symbolic faceXik is given by
(11)B¯ik=VlTΦ(X¯ik),l=1,2,…,s, where (12)Φ(X¯ik)=[(Φ(X11C)⋅Φ(X¯ik),…,Φ(X1qC)⋅Φ(X¯ik)),⁢…,(Φ(Xm1C)⋅Φ(X¯ik),…,Φ(XmqC)⋅Φ(X¯ik))]. Similarly, the upper bound features of each
symbolic face Xik is given by
(13)B¯ik=VlTΦ(X¯ik),l=1,2,…,s. Let ctest=[Γ1,Γ2,…,Γl] be the test face class that contains face
images of same subject with different expression, lighting condition and
orientation. The test symbolic face Xtest is constructed for test face class ctest as explained in Section 2. The lower bound
test symbolic face of test symbolic face Xtest is described as X¯test=(x¯1test,x¯2test,…,x¯ptest).
Similarly, the upper bound test symbolic face is described as X¯test=(x¯1test,x¯2test,…,x¯ptest).The interval-type
features[B̲test,B¯test] of test symbolic face Xtest are computed as:
(14)B̲test=VlTΦ(X¯test),B¯test=VlTΦ(X¯test),  where l=1,2,…,s.


## 4. Experimental Results

The proposed symbolic KDA method is experimented with the
face images of the ORL and Yale databases. The effectiveness of proposed method is shown
in terms of comparative performance against two face recognition methods. In particular, we
compared our algorithm with kernel Eigenface
[8] and kernel
Fisherface [9] method.


### 4.1. Experiments Using ORL Database

We assess the feasibility and performance of the proposed symbolic KDA on the face
recognition task using ORL database. The ORL face database is composed of 400 images
with ten different facial views that represent various expressions and orientations for each
of the 40 distinct subjects as shown in Figure1.
We have arranged images of each
face class from right side view to left side view. All the 400 images from the ORL database
are used to evaluate the face recognition performance of proposed method. Six images are
randomly chosen from the ten images available for each subject for training, while the
remaining images are used to construct the test symbolic face for each trial. We have
conducted the experiments using two kernel functions namely, polynomial kernel and
Gaussian kernel.Figure 1
Some typical images of one subject of ORL database.Our goal is to find appropriate kernel function and corresponding optimal kernel parameters
(i.e., the order of the polynomial kernel and the width of the Gaussian kernel) for our
proposed method. The experimental results shows that the order of the polynomial kernel should be three and the width of Gaussian kernel should be four for proposed symbolic KDA
with respect to a minimum distance classifier.After determining the optimal kernel parameters, we set out to select the dimension of
discriminant subspace with respect to two different kernels. Table1 shows optimal subspace
for each method. The optimal parameters for each method with respect to different kernels.
Besides, we find that symbolic KDA features seem more effective than features of other
methods.Table 1
Optimal parameters corresponding to each method with respect to two different kernels.
MethodPolynomial kernelGaussian kernelOrderSubspace dimensionWidthSubspace dimensionKernel Eigenfaces144747Kernel fisherfaces335544Symbolic KDA318424After selection of optimal parameters and optimal subspace for each method with respect to
different kernels, all three methods are reevaluated using same set of training and testing
samples. The average recognition rates for the best case are shown in Table2. The best
performance of the symbolic KDA method is better than the best performance of the kernel
Eigenface and kernel Fisherface method. We note that the symbolic KDA method
outperforms kernel Eigenface method and kernel Fisherface in the sense of using small
number of features.Table 2
Comparison of symbolic KDA method using optimal parameters.
Kernel EigenfaceSymbolic KDAKernel FisherfacePolynomial
kernel55.6191.8684.95Gaussian
kernel58.0589.3981.57In order to examine, whether symbolic KDA is statistically significant and better than other
methods in terms of its recognition rate. We evaluate the experimental results presented in
Table2 using McNemar’s significance test. McNemar’s test is essentially a null hypothesis
statistical test based on a Bernoulli model. If the resulting p-value is below the desired
significance level, the null hypothesis is rejected and the performance difference between two
algorithms is considered to be statistically significant. By this test, we find that symbolic
KDA statistically significant and outperforms kernel Eigenface and kernel Fisherface methods
at a significance level of p=1.012×10−6.The receiver operating characteristic (ROC)
curve in Figure2 reports results for a verification scenario. The equal-error
rate (EER) is the ROC point at which the false-accept rate is equal to the false-reject
rate. The EER for our approach goes from approximately 0.12 to approximately
0.23. The EER for the other methods shows much greater performance degradation.Figure 2
The ROC performance of proposed symbolic KDA Method, Kernel Eigenface Method,
Kernel Fisherface Method and Eigenface Method.


### 4.2. Experiments on the Yale Face Database

The experiments were
conducted using Yale database to evaluate the excellence of the symbolic KDA
for frontal face recognition under different nondark backgrounds. The Yale face
database consists of a total of 165 images obtained from 15 different people,
with 11 images from each person.  Figure3 shows some typical
images of one subject of Yale face database. We preprocessed these images by
aligning and scaling them so that the distances between the eyes were the same
for all images and also ensuring that the eyes occurred in the same
co-ordinates of the image. The resulting image was then cropped. The images
were not manually arranged as done in previous set of experiments using ORL
database (Section 4.1). In our experiments, 9 images were randomly chosen from
each class for training, while the remaining two images were used to construct
test symbolic face for each trial.Figure 3
Some typical images of one subject of Yale face database.The
experiments were conducted using two different kernels, namely, polynomial kernel
and Gaussian kernel. The order of the polynomial kernel should be 2 and the width of
Gaussian kernel should be four for proposed symbolic KDA with respect to a minimum
distance classifier.After finding optimal kernel parameter
(degree 2) for the symbolic KDA method, the experiments were conducted to find
optimal subspace for proposed symbolic KDA, kernel Fisherface, and kernel Eigenface
method. The recognition rates, training time, and optimal subspace dimension for
Kernel Fisherface, Kernel Eigenface, and symbolic KDA are listed in Table3. From
Table 3, the symbolic KDA method with polynomial degree two has
recognition rate 89.00% using only 15 features, where as Kernel Fisherface method requires
42 features to achieve 87.15% recognition rate. This is due to the fact that first few
eigenvectors of symbolic PCA account for highest variance of training samples and these few
eigenvectors are enough to represent image for recognition purposes. Hence, improved
recognition results can be achieved at less computational cost by using symbolic KDA, by
virtue of its low dimensionality. The experimental results obtained using Yale face database
shows that the proposed symbolic KDA performs well on images with non dark backgrounds.Table 3
Comparison of classification performance
using Yale face database.
Methodskernel Fisherfaceskernel Eigenfacessymbolic KDARecognition rates (%)87.1583.2889.00Training time (seconds)48.34668.75138.324Feature dimension425415


## 4.1. Experiments Using ORL Database

We assess the feasibility and performance of the proposed symbolic KDA on the face
recognition task using ORL database. The ORL face database is composed of 400 images
with ten different facial views that represent various expressions and orientations for each
of the 40 distinct subjects as shown in Figure1.
We have arranged images of each
face class from right side view to left side view. All the 400 images from the ORL database
are used to evaluate the face recognition performance of proposed method. Six images are
randomly chosen from the ten images available for each subject for training, while the
remaining images are used to construct the test symbolic face for each trial. We have
conducted the experiments using two kernel functions namely, polynomial kernel and
Gaussian kernel.Figure 1
Some typical images of one subject of ORL database.Our goal is to find appropriate kernel function and corresponding optimal kernel parameters
(i.e., the order of the polynomial kernel and the width of the Gaussian kernel) for our
proposed method. The experimental results shows that the order of the polynomial kernel should be three and the width of Gaussian kernel should be four for proposed symbolic KDA
with respect to a minimum distance classifier.After determining the optimal kernel parameters, we set out to select the dimension of
discriminant subspace with respect to two different kernels. Table1 shows optimal subspace
for each method. The optimal parameters for each method with respect to different kernels.
Besides, we find that symbolic KDA features seem more effective than features of other
methods.Table 1
Optimal parameters corresponding to each method with respect to two different kernels.
MethodPolynomial kernelGaussian kernelOrderSubspace dimensionWidthSubspace dimensionKernel Eigenfaces144747Kernel fisherfaces335544Symbolic KDA318424After selection of optimal parameters and optimal subspace for each method with respect to
different kernels, all three methods are reevaluated using same set of training and testing
samples. The average recognition rates for the best case are shown in Table2. The best
performance of the symbolic KDA method is better than the best performance of the kernel
Eigenface and kernel Fisherface method. We note that the symbolic KDA method
outperforms kernel Eigenface method and kernel Fisherface in the sense of using small
number of features.Table 2
Comparison of symbolic KDA method using optimal parameters.
Kernel EigenfaceSymbolic KDAKernel FisherfacePolynomial
kernel55.6191.8684.95Gaussian
kernel58.0589.3981.57In order to examine, whether symbolic KDA is statistically significant and better than other
methods in terms of its recognition rate. We evaluate the experimental results presented in
Table2 using McNemar’s significance test. McNemar’s test is essentially a null hypothesis
statistical test based on a Bernoulli model. If the resulting p-value is below the desired
significance level, the null hypothesis is rejected and the performance difference between two
algorithms is considered to be statistically significant. By this test, we find that symbolic
KDA statistically significant and outperforms kernel Eigenface and kernel Fisherface methods
at a significance level of p=1.012×10−6.The receiver operating characteristic (ROC)
curve in Figure2 reports results for a verification scenario. The equal-error
rate (EER) is the ROC point at which the false-accept rate is equal to the false-reject
rate. The EER for our approach goes from approximately 0.12 to approximately
0.23. The EER for the other methods shows much greater performance degradation.Figure 2
The ROC performance of proposed symbolic KDA Method, Kernel Eigenface Method,
Kernel Fisherface Method and Eigenface Method.


## 4.2. Experiments on the Yale Face Database

The experiments were
conducted using Yale database to evaluate the excellence of the symbolic KDA
for frontal face recognition under different nondark backgrounds. The Yale face
database consists of a total of 165 images obtained from 15 different people,
with 11 images from each person.  Figure3 shows some typical
images of one subject of Yale face database. We preprocessed these images by
aligning and scaling them so that the distances between the eyes were the same
for all images and also ensuring that the eyes occurred in the same
co-ordinates of the image. The resulting image was then cropped. The images
were not manually arranged as done in previous set of experiments using ORL
database (Section 4.1). In our experiments, 9 images were randomly chosen from
each class for training, while the remaining two images were used to construct
test symbolic face for each trial.Figure 3
Some typical images of one subject of Yale face database.The
experiments were conducted using two different kernels, namely, polynomial kernel
and Gaussian kernel. The order of the polynomial kernel should be 2 and the width of
Gaussian kernel should be four for proposed symbolic KDA with respect to a minimum
distance classifier.After finding optimal kernel parameter
(degree 2) for the symbolic KDA method, the experiments were conducted to find
optimal subspace for proposed symbolic KDA, kernel Fisherface, and kernel Eigenface
method. The recognition rates, training time, and optimal subspace dimension for
Kernel Fisherface, Kernel Eigenface, and symbolic KDA are listed in Table3. From
Table 3, the symbolic KDA method with polynomial degree two has
recognition rate 89.00% using only 15 features, where as Kernel Fisherface method requires
42 features to achieve 87.15% recognition rate. This is due to the fact that first few
eigenvectors of symbolic PCA account for highest variance of training samples and these few
eigenvectors are enough to represent image for recognition purposes. Hence, improved
recognition results can be achieved at less computational cost by using symbolic KDA, by
virtue of its low dimensionality. The experimental results obtained using Yale face database
shows that the proposed symbolic KDA performs well on images with non dark backgrounds.Table 3
Comparison of classification performance
using Yale face database.
Methodskernel Fisherfaceskernel Eigenfacessymbolic KDARecognition rates (%)87.1583.2889.00Training time (seconds)48.34668.75138.324Feature dimension425415


## 5. Conclusions

In this paper, we propose a novel symbolic
KDA method for face recognition. Symbolic data representation of face images
using interval-type features are desirable facial features to cope up with the variations
due to illumination, orientation, and facial expression changes. The
feasibility of the symbolic KDA has been tested successfully on frontal face
images of ORL and Yale databases. Experimental results show that symbolic KDA
method with polynomial kernel leads to improved recognition rate at reduced computational cost.The
proposed symbolic KDA has many advantages compared to other popular appearance-based
methods. The drawback of other appearance-based methods is that in order to
recognize a face seen from a particular pose and under a particular
illumination, the face must have been previously seen under the same
conditions. The symbolic KDA overcomes this limitation by representing the
faces by interval-type features so that even the faces seen previously in
different poses, orientations, and illuminations are recognized. Another
important merit is that we can use more than one probe image with inherent variability of a face
for face recognition, this yields improved recognition rate. This is clearly
evident from the experimental results. We observe from the experimental results
that the proposed symbolic KDA method yields improved recognition rate in terms
of time and feature reduction compare to other kernel-based methods.The main
drawback of our proposed symbolic KDA method is that pose variation is limited up
to 20 degree orientation and the performance of proposed method decreases on
face images with pose variation greater than 20 degree orientation. The
proposed method did not achieve 100% accuracy, this is due to the fact that
while constructing the symbolic faces, there may be chance of misalignment of
coordinates of eyes, mouth, and nose because of different facial expressions in
training images. It can be
observed in experimental results obtained using Yale face database, which contains face images
with different facial expressions. Moreover, the performance of the proposed
symbolic KDA method decreases on images with more variation in facial
expressions of Yale face database compared to performance on images with less
variation in facial expressions of ORL face database.



---

*Source: 486247-2008-05-07.xml*