Local-information-based uncorrelated feature extraction

Haitao Zhao; Shao-yuan Sun; Zhongliang Jing

doi:10.1117/1.2163873

1 February 2006 Local-information-based uncorrelated feature extraction

Haitao Zhao, Shao-yuan Sun, Zhongliang Jing

Author Affiliations +

Optical Engineering, Vol. 45, Issue 2, 020505 (February 2006). https://doi.org/10.1117/1.2163873

Abstract

In the past few years, the computer vision and pattern recognition community has witnessed the rapid growth of a new kind of feature extraction method, the manifold learning methods, which attempt to project the original data into a lower dimensional feature space by preserving the local neighborhood structure. Among them, locality preserving projection (LPP) is one of the most promising feature extraction techniques. Based on LPP, we propose a novel feature extraction method, called uncorrelated locality preserving projection (ULPP). We show that the extracted features via ULPP are statistically uncorrelated, which is desirable for many pattern analysis applications. We compare the proposed ULPP approach with LPP and principal component analysis (PCA) on the publicly available data sets, FERET and AR. Experimental results suggest that the proposed ULPP approach provides a better representation of the data and achieves much higher recognition accuracies.

1. Introduction

Recently, a new kind of feature extraction method, manifold learning algorithms, based on the local geometry analysis have drawn much attention. Unlike PCA, which aims to preserve the global Euclidean structure of the data space, manifold learning algorithms aim to preserve the inherent manifold structure. Locally linear embedding (LLE), Isomap, Laplacian eigenmap, and locality preserving projection (LPP)¹ are the most important manifold learning algorithms. All of these four algorithms attempt to embed the original data into a submanifold by preserving the local neighborhood structure. They are based on the assumption that the manifold’s intrinsic geometry can be fully determined by the local metric and the neighborhood information. Different from LLE, Isomap, and Laplacian eigenmap, LPP is a linear algorithm. It is quite simple and easy to realize. LPP is originally derived by the discretely approximation of the Laplace Beltrami operator on compact Rimannian manifold. He ¹ have applied LPP on face recognition problem. The application has shown the effectiveness of LPP in discovering the the intrinsic geometrical structure of the data.

Based on LPP, we propose a novel algorithm, called uncorrelated locality preserving projection (ULPP). It shares the same locality preserving character as LPP, but at the same time it requires the basis vectors to be statistically uncorrelated. Uncorrelated attributes are highly desirable in pattern analysis, because they contain minimum redundancy.² However, the basis vectors of LPP are statistically correlated, then the extracted features contain redundant information. Moreover, the overlapped information can distort the distribution of the features and even dramatically degrade the performance of LPP. In this paper, we overcome this problem by putting an uncorrelated constraint on the computation of the basis vectors. This makes the proposed ULPP algorithm much more robust.

2. Locality Preserving Projection

LPP¹ can be explained by spectral graph theory. Let us assume that the $n$ -dimensional data set ${x_{1}, x_{2}, \dots, x_{N}}$ is distributed on a low-dimensional submanifold. We desire to find a set of $d$ -dimensional $(d < n)$ data points ${y_{1}, y_{2}, \dots, y_{N}}$ with the same local neighborhood structure as the data ${x_{1}, x_{2}, \dots, x_{N}}$ . In order to do so, we can construct a weighted graph $G = (V, E, W)$ , where $V$ is the set of all points; $E$ is the set of edges connecting the points; and $W = (w_{i j})$ is a similarity matrix with weights characterizing the likelihood of two points. The criterion function of LPP is as follows:

Eq. 1

\min \sum_{i j} {∥ y_{i} - y_{j} ∥}^{2} w_{i j} .

To make the mapping (embedding) not defined only for the original data set, LPP defines a transformation. That is, $y_{i} = Φ^{T} x_{i}$ , where $Φ = [ϕ_{1}, ϕ_{2}, \dots, ϕ_{d}] ∊ R^{n \times d}$ . Following some algebraic steps, we see that

Eq. 2

\frac{1}{2} \sum_{i j} {∥ y_{i} - y_{j} ∥}^{2} w_{i j} = \frac{1}{2} \sum_{i j} {(Φ^{T} x_{i} - Φ^{T} x_{j})}^{T} (Φ^{T} x_{i} - Φ^{T} x_{j}) w_{i j} = \sum_{k i} ϕ_{k}^{T} x_{i} D_{i i} x_{i}^{T} ϕ_{k} - \sum_{k i j} ϕ_{k}^{T} Diag (x_{i}, \dots, x_{i}) w_{i j} Diag (x_{j}^{T}, \dots, x_{j}^{T}) ϕ_{k} = trace (Φ^{T} X (D - W) X^{T} Φ),

where

X = [x_{1}, x_{2}, \dots, x_{N}]

, and

D = diag (D_{i i})

; its entries are row (or column since

W

is symmetric) sums of

W

,

D_{i i} = Σ_{j} w_{i j}

;

Diag (x, \dots, x)

returns a block diagonal matrix with block entry x.

L = D - W

is the Laplacian matrix.¹

In order to remove the arbitrary scaling factor in the embedding, LPP imposes a constraint as follows:

Eq. 3

Y D Y^{T} = I \Rightarrow Φ^{T} X D X^{T} Φ = I .

This constraint sets the mapping (embedding) scale and makes the vertices with high similarities to be mapped nearer to the origin. Finally, the minimization problem reduces to:

Eq. 4

\underset{\begin{matrix} Φ \\ Φ^{T} X D X^{T} Φ = I \end{matrix}}{argmin} trace (Φ^{T} X L X^{T} Φ) .

The transformation matrix $Φ$ that minimizes the objective function can be obtained by solving the generalized eigenvalue problem:

Eq. 5

X L X^{T} ϕ = λ X D X^{T} ϕ .

Note that the Laplacian matrix can be viewed as the discretely approximation of the Laplace Beltrami operator on compact Rimannian manifold.¹

Based on the matrix $Φ = [ϕ_{1}, \dots, ϕ_{d}]$ , for any instance $u = {[u_{1}, u_{2}, \dots, u_{n}]}^{T} ∊ R^{n}$ , we can define the following linear transform from $R^{n}$ to $R^{d}$ :

Eq. 6

[\begin{matrix} v_{1} \\ v_{2} \\ ⋥ \\ v_{d} \end{matrix}] = [\begin{matrix} ϕ_{1}^{T} \\ ϕ_{2}^{T} \\ ⋥ \\ ϕ_{d}^{T} \end{matrix}] u .

Equation 6 with the constraint 3 forms the LPP transformation. It is easy to obtain the following theorem.

Theorem 1: Any two features $v_{i}$ and $v_{j}$ $(j \neq i)$ in Eq. 6 are correlated.

Proof: Let the covariance matrix of the data ${x_{i}}_{i = 1}^{N}$ be $Ξ$ . It is easy to obtain the following equation:

Eq. 7

E [(v_{i} - E v_{i}) (v_{j} - E v_{j})] = ϕ_{i}^{T} Ξ ϕ_{j} .

With the constraint 3, we have inequality, in general,

Eq. 8

ϕ_{i}^{T} Ξ ϕ_{j} \neq 0 (j \neq i) .

Therefore, we cannot obtain the following equation in general:

Eq. 9

E [(v_{i} - E v_{i}) (v_{j} - E v_{j})] = 0,

thus completing the proof.

3. Uncorrelated Locality Preserving Projection

The algorithmic procedure of uncorrelated locality preserving projection (ULPP) is stated below:

1. Perform PCA projection. We project the data set into a PCA subspace to make the matrix $X D X^{T}$ become nonsingular. Let the transformation matrix of PCA be $Φ_{P C A}$ .
2. Construct the similarity of any two data points. For each sample $x_{i}$ , if $x_{j}$ is among the $m$ -nearest neighbors of $x_{i}$ , set the similarity $w_{i j} = w_{j i} = x_{i}^{T} x_{j}$ ; otherwise, set the similarity $w_{i j} = w_{j i} = 0$ . The similarity reflects the local structure of the data space.
3. Obtain the diagonal matrix $D$ and the Laplacian matrix $L$ .
4. Compute the uncorrelated locality preserving projections. Let $S_{L} = X L X^{T}$ , $S_{D} = X D X^{T}$ and $I = diag (1, 1, \dots, 1)$ for concision. Let ${ϕ_{1}, ϕ_{2}, \dots, ϕ_{k}}$ be the uncorrelated locality preserving projections, thus we define
Eq. 10
$Φ^{(k - 1)} = [ϕ_{1}, ϕ_{2}, \dots, ϕ_{k - 1}] .$

The uncorrelated locality preserving projections ${ϕ_{1}, ϕ_{2}, \dots, ϕ_{k}}$ can be iteratively computed as follows:
- (a) Compute $ϕ_{1}$ as the eigenvector of $S_{D}^{- 1} S_{L}$ associated with the smallest eigenvalue.
- (b) Compute $ϕ_{k}$ as the eigenvector associated with the smallest eigenvalue of the eigenfunction
  Eq. 11
  $P^{(k)} S_{L} ϕ = λ S_{D} ϕ,$
  where
  Eq. 12
  $P^{(k)} = I - Ξ {(Φ^{(k - 1)})}^{T} {(Φ^{(k - 1)} Ξ S_{D}^{- 1} Ξ {(Φ^{(k - 1)})}^{T})}^{- 1} Φ^{(k - 1)} Ξ S_{D}^{- 1} .$
5. Perform the ULPP transformation. Let $Φ^{*} = [ϕ_{1}, ϕ_{2}, \dots, ϕ_{d}]$ . The embedding is as follow:
Eq. 13
$v = Φ_{U L P P}^{T} u,$
where $v$ is a $d$ -dimensional representation of $u$ and $Φ_{U L P P} = Φ_{P C A} Φ^{*}$ .

3.1.

Justification

In this subsection, we provide the justification of our algorithm.

According to the following theorem, we can compute the $k - th$ uncorrelated direction $ϕ_{k}$ as the eigenvector of $P^{(k)}$ [Eq. 12] associated with the the smallest eigenvalue of $P^{(k)}$ .

Theorem 2: The $k - th$ uncorrelated direction $ϕ_{k}$ is the eigenvector corresponding to the smallest eigenvalue of the following eigenfunction:

P^{(k)} S_{L} ϕ = λ S_{D} ϕ,

where

P^{(k)} = I - Ξ {(Φ^{(k - 1)})}^{T} {(Φ^{(k - 1)} Ξ S_{D}^{- 1} Ξ {(Φ^{(k - 1)})}^{T})}^{- 1} Φ^{(k - 1)} Ξ S_{D}^{- 1} .

Proof: Recall the minimization problem of LPP:

\underset{\begin{matrix} Φ \\ Φ^{T} X D X^{T} Φ = I \end{matrix}}{argmin} trace (Φ^{T} X L X^{T} Φ) .

In order to compute the

k - th

uncorrelated direction

ϕ_{k}

, we add the constraints

ϕ_{k} Ξ ϕ_{i} = 0 (i = 1, 2, \dots, k - 1) .

We can use the method of Lagrange multipliers to transform the minimization function to include all constraints. Recall

S_{L} = X L X^{T}

and

S_{D} = X D X^{T}

, we have

Eq. 14

L (ϕ_{k}) = ϕ_{k}^{T} S_{L} ϕ_{k} - λ (ϕ_{k}^{T} S_{D} ϕ_{k} - 1) - \sum_{i = 1}^{k - 1} γ_{i} ϕ_{k}^{T} Ξ ϕ_{i} .

The minimization is performed by setting the partial derivative of

L (ϕ_{k})

with respect to

ϕ_{k}

equal to zero:

Eq. 15

2 S_{L} ϕ_{k} - 2 λ S_{D} ϕ_{k} - \sum_{i = 1}^{k - 1} γ_{i} Ξ ϕ_{i} = 0 .

Multiplying the left side of Eq. 15 by

ϕ_{k}

, we have

Eq. 16

λ = \frac{ϕ_{k}^{T} S_{L} ϕ_{k}}{ϕ_{k}^{T} S_{D} ϕ_{k}} .

Thus,

λ

represents minimization problem to be optimized.

Multiplying the left-hand side of Eq. 15, respectively, by $ϕ_{j}^{T} Ξ S_{D}^{- 1}$ $(j = 1, 2, \dots, k - 1)$ , we have

Eq. 17

2 [\begin{matrix} ϕ_{1}^{T} \\ ϕ_{2}^{T} \\ ⋥ \\ ϕ_{k - 1}^{T} \end{matrix}] Ξ S_{D}^{- 1} S_{L} ϕ_{k} - [\begin{matrix} ϕ_{1}^{T} \\ ϕ_{2}^{T} \\ ⋥ \\ ϕ_{k - 1}^{T} \end{matrix}] Ξ S_{D}^{- 1} Ξ [\begin{matrix} ϕ_{1} \\ ϕ_{2} \\ ⋥ \\ ϕ_{k - 1} \end{matrix}] [\begin{matrix} γ_{1} \\ γ_{2} \\ ⋥ \\ γ_{k - 1} \end{matrix}] = 0 .

Let

Γ^{(k)} = {[γ_{1}, γ_{2}, \dots, γ_{k - 1}]}^{T}

, thus we can obtain

Eq. 18

Γ^{(k)} = 2 {(Φ^{(k)} Ξ S_{D}^{- 1} Ξ {(Φ^{(k)})}^{T})}^{- 1} Φ^{(k)} Ξ S_{D}^{- 1} S_{L} ϕ_{k} .

Since Eq. 15 can be written as

Eq. 19

2 S_{L} ϕ_{k} - 2 λ S_{D} ϕ_{k} - Ξ {(Φ^{(k - 1)})}^{T} Γ^{(k)} = 0,

substituting Eq. 18 into Eq. 19, we have

Eq. 20

S_{L} ϕ_{k} - λ S_{D} ϕ_{k} - Ξ {(ϕ^{(k - 1)})}^{T} {(Φ^{(k)} Ξ S_{D}^{- 1} Ξ {(Φ^{(k)})}^{T})}^{- 1} Φ^{(k)} Ξ S_{D}^{- 1} S_{L} ϕ_{k} = 0,

or in another form

Eq. 21

[I - Ξ {(Φ^{(k - 1)})}^{T} {(Φ^{(k - 1)} Ξ S_{D}^{- 1} Ξ {(Φ^{(k - 1)})}^{T})}^{- 1} Φ^{(k - 1)} Ξ S_{D}^{- 1}] S_{L} ϕ_{k} = λ S_{D} ϕ_{k},

thus completing the proof.

4. Experiment Results

4.1.

Experiments on FERET Data Set

FERET³ is a very popular database. Face image variations in the FERET database include pose, illumination, facial expression, and aging. In our experiment, we use a subset of the FERET data set. The data set we selected contains 72 people and 6 images for each individual. All images are aligned by the centers of the eyes and mouth and then scaled with resolution $112 \times 92$ . We randomly select 3 images from each person for training, while the rest of the images of each individual are selected for testing. The experiments are repeated 20 times and the average accuracies of rank 1 to rank 3 are recorded and shown in Table 1. The results show ULPP gives the best performance. The recognition accuracy of ULPP increases from 85.90% with rank 1 to 91.07% with rank 3, which is about 10% higher than the recognition accuracy of LPP.

Table 1

Recognition accuracies (%) comparison of FERET data set.

	Eigenface	LPP	ULPP
Rank 1	58.61	72.64	85.90
Rank 2	63.70	78.22	89.49
Rank 3	68.22	81.39	91.07

4.2.

Experiments on AR Data Set

AR⁴ is also a popular database. Face image variations in the AR database include illumination, facial expression, and occlusion. In our experiment, 952 images (119 individuals, 8 images per person), which involve large variations in facial expression, are selected. We manually cropped the face portion of the images. All the cropped images are aligned at the centers of eyes and mouth and then normalized with resolution $112 \times 92$ . We randomly select 4 images from each person for training, while the rest of the images of each individual are selected for testing. The experiments are repeated 30 times and the average accuracies of rank 1 to rank 3 are recorded and shown in Table 2. From Table 2, it can be seen that ULPP outperforms the other two methods. The recognition accuracy of ULPP increases from 80.32% with rank 1 to 86.51% with rank 3, which is about 5% higher than the recognition accuracy of LPP.

Table 2

Recognition accuracies (%) comparison on AR data set.

	Eigenface	LPP	ULPP
Rank 1	70.58	72.42	80.32
Rank 2	79.07	77.96	84.44
Rank 3	83.40	80.43	86.51

5. Conclusion

This paper presents a novel feature extraction method, called uncorrelated locality preserving projection (ULPP). ULPP can extract uncorrelated features which contain minimum redundancy and are highly desirable for many applications. In this paper, we present a theoretical study on ULPP and provide an implementation of it. The experiments on face image data show the superiority of ULPP over the other both PCA and LPP.

Acknowledgment

This project is partially supported by National Natural Science Foundation of China (60502042) and 2010 Shanghai EXPO Special Project (2004BA908B07, 04DZ05807).

References

1.

X. He, S. Yan, Y. Hu, P. Niyogi, and H. Zhang, “Face recognition using Laplacianfaces,” IEEE Trans. Pattern Anal. Mach. Intell., 27 (3), 328 –340 (2005). 0162-8828 Google Scholar

2.

J. Ye, R. Janardan, Q. Li, and H. Park, “Feature extraction via generalized uncorrelated linear discriminant analysis,” (2004). Google Scholar

3.

P. J. Phillips, H. Moon, S. A. Rizvi, and P. J. Rauss, “The FERET evaluation methodology for face-recognition algorithms,” IEEE Trans. Pattern Anal. Mach. Intell., 22 (10), 1090 –1104 (2000). https://doi.org/10.1109/34.879790 0162-8828 Google Scholar

4.

A. M. Martinez and R. Benavente, “The AR face database,” (1998). Google Scholar

Citation Download Citation

Haitao Zhao, Shao-yuan Sun, and Zhongliang Jing "Local-information-based uncorrelated feature extraction," Optical Engineering 45(2), 020505 (1 February 2006). https://doi.org/10.1117/1.2163873

Published: 1 February 2006

Access the abstract

JOURNAL ARTICLE
3 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

CITATIONS

Cited by 10 scholarly publications.

Explore citations on Lens.org

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Feature extraction

Principal component analysis

Aerospace engineering

Databases

Detection and tracking algorithms

Statistical analysis

Computer vision technology

1.

Introduction

2.

Locality Preserving Projection