Face Recognition Using LaplacianfacesHe et al. (IEEE Trans PAMI, 2005)presented by Hassan A. KingraviOverview Introduction Linear Methods for Dimensionality Reduction Nonlinear Methods and Manifold Learning LPP and its Connections to LDA and PCA Laplacianfaces for Face Analysis Experiments ConclusionsIntroduction Face Recognition* Many methods developed* An example of the Appearance-Based Method, i.e. templates extracted from given information Current Approach (Laplacianfaces)* Builds on the dimensionality reduction approach* Takes into account the possibility of the distribution of the data on a non-linear subspace by preserving local structure (Locality Preserving Projections)* Generalizes to unseen points (problem in most nonlinear methods)Dimensionality Reduction Images represented as vectors in extremely high-dimensional space Idea is that we can create decision boundaries between different classes of objects Dimensionality reduction is required because:a) Inherent structure of data may not be apparent in high dimensional space; vector can have irrelevant attributes that contain little useful informationb) A projection makes the data more tractable to manage Reduction can be linear (PCA, LDA) or nonlinear (ISOMAP)DR Methods : PCA Projects high-dimensional data to low dimensional subspace Objective function maximizes variance globally: Solution by finding the eigenvectors of the (reduced) covariance matrix .21max ( )niwiyy=−∑12, ,...,kww wDR Methods : PCA Since PCA maximizes global variance, it can be thought of re-representing as much of the original signal as possible. This does NOT mean that the data is projected with an aim for classification; rather, it is compressed. Other methods exist which aim to project the vector based on multiclass discrimination.DR Methods : LDA LDA seeks directions of projection that are efficient for discrimination. The objective function maximizes between-class scatter over within-class scatter:maxTBTwWwSwwS wDR Methods : LDA LDA seeks directions of projection that are efficient for discrimination. LDA is defined in terms of the number of classes of projection; hence, it is a supervised learning algorithm (need to know class labels.) In the face recognition problem, one unique face represents a class. Good performance in general (better than PCA for faces), but still linear.Nonlinear Methods When the linear subspace assumption is violated, for e.g. the figure on the right. The data lies on a nonlinear manifold, a mathematical space where the local area around a point may be Euclidean, but the overall structure may be more complicatedNonlinear Methods Idea: manifolds arise naturally whenever there’s a smooth variation of parameters. Hypothesis; face recognition problems are non-linear in nature. Specifically, images that change smoothly over time (video).Nonlinear Methods: ISOMAP An example of a nonlinear embedding method: ISOMAP. Need to see geodesic structure; solution: graph embeddings. Steps of ISOMAP:a) Find nearest neighbors to each sample (either use a k rule or a radius based on Euclidean distance) and construct a graph of the geodesic.b) Use Dijkstra’s shortest path algorithm to find distances between all points.c) Apply multidimensional scaling.Locality Preserving Projections Problems: ISOMAP is computationally intensive and the embedding’s only defined on actual data points. Solution: Locality Preserving Projections, the method of Laplacianfaces. LPP is a linear method that approximates nonlinear methods (specifically, the Laplacian Eigenmap.) LPP minimizes the following objective function:where 2min ( )ijijijyyS−∑22exp( || || / ), || ||ij ij ijSxxtxx=−− − <εLocality Preserving Projections The resulting mapping amounts to the following eigenvalue problem: L is the Laplacian matrix, i.e. D – S, where S corresponds to the similarity values defined, and D is a column matrix which reflects how important a certain projection is. The more data points that surround a given point, the more “important” it is. Thus, the mapping preserves locality. The given equation corresponds to the Laplace-Beltrami operator on differential manifolds. TTXLX w XDX wλ=LPP and other methods LPP is a linear approximation to nonlinear methods, which takes locality into account. If one aims to preserve global structure only, let the neighborhood grow to infinity; data points are projected in directions of maximal variance, i.e. LPP becomes similar to PCA. LDA preserves discriminating information and global geometric structure; through manipulation, LPP can induce LDA. LDA is supervised, while LPP is unsupervised.Laplacianfaces Method:a) Because can be sparse, the image is first projected onto a PCA subspace.b) The nearest neighbor graph is constructed, like ISOMAP. Laplacianfaces use the knn rule. c) Weights are chosen by the equation.d) The eigenmap is calculated. We get a set of k vectors that represent the new subspace. TXDXijSTTXLX w XDX wλ=Laplacianfaces Results from a mapping to a 2-d space.Experimental ResultsDiscussion & Conclusions Method has higher accuracy than both PCA and LDA approaches. LDA needs more than one sample per class to classify; LPP behaves like PCA. Method is faster than ISOMAP, and generalizes well (not specifically nonlinear.) LPP can also be applied to other machine learning issues.References He et al. “Face Recognition Using Laplacianfaces.” Ricardo Gutierrez-Osuna, Pattern Recognition Slides, Fall
View Full Document
Unlocking...