Face Feature Extraction using Fast Haar Transform

Face Feature Extraction using Fast Haar Transform

D. Muthu Kumar1 M.E., D. Ramalingam2 M.E.,

1. Assistant Professor, Department of Computer Science and Engineering,Saveetha Engineering College, Thandalam, Chennai 602105.

2. Assistant Professor, Department of Computer Science and Engineering,Saveetha Engineering College, Thandalam, Chennai 602105.

   Abstract – Subspace learning is the process of nding a proper feature subspace from face images and then projecting high- dimensional data onto the learned low-dimensional subspace. The projection operation requires (N*N) oating point multiplications and N*(N-1) floating point additions, which makes the projection process computationally expensive. To overcome this problem, this paper proposes two simple-but- effectives fast subspace learning and image projection methods, Fast Haar Transform (FHT) based Principal Component Analysis and FHT based Spectral Regression Discriminant Analysis. While we apply these methods, we require only 2*(N-1) additions for Feature extraction. The advantages of these two methods result from employing both the FHT for subspace learning and the integral vector for feature extraction. Images for face feature extraction is been taken from face databases. Here three Databases used are ORL Face Databases, YALE Face Databases and FERET Databases. Experimental results on three face databases demonstrated their effectiveness and efficiency. Feature extraction can be done by projecting the high dimensional data in question onto the subspace spanned by the basis vectors. This technique has been widely utilized in the computer vision, data mining, and multimedia processing areas.

   Index TermsFace representation and recognition, fast algorithm, feature extraction, Haar transform, subspace analysis.

   1. INTRODUCTION

      certain building area, computer files, border crossings, or to identify individuals to record information about them such as with criminals.

      1. Face Recognition

         Face recognition is one of most successful applications in computer vision and pattern recognition and the main objective of it is to recognize persons from pictures or video using a stored database of faces. The building of face recognition system is a sophisticated problem because the faces has a lot of variations and may be located in a changed environment. Because of these reasons, the recognition of faces is a challenging problem due to the wide variety of illumination, facial expression and pose variations.

      2. Facial Recognition System

      A facial recognition system is a computer application for automatically identifying or verifying a person from a digital image or a video frame from a video source. One of the ways to do this is by comparing selected facial features from the image and a facial database. It is typically used in security systems and can be compared to other biometrics such as fingerprint or eye iris recognition systems.

      1.1. Digital Image processing

      Digital image processing refers to processing of the image in digital form. Modern cameras may directly take the image in digital form but generally images are originated in optical form. They are captured by video cameras and digitalized.

      The digitalization process includes sampling and quantization. Then these images are processed by the five fundamental processes, at least any one of them, not necessarily all of them.

      1.2 Biometrics

      Biometrics is the study of unchanging measurable biological characteristics that are unique to each individual

      – such as fingerprints or irises. Biometrics can be implemented by: companies, governments, military, border control, hospitals, banks, etc. to either verify a person's identity for something like limiting or allowing access to a

   2. LITERATURE REVIEW

1. Eigen Faces for recognition

   In mathematical terms we wish to find the principal components of the distribution of faces or the Eigen vectors of the covariance matrix of the set of face images treating an image as a pointing a very high dimensional space.

   The approach to face recognition involves the following initialization operations

   1. Acquire an initial set of face images

   2. Calculate the Eigen faces from the training set; keep only the m images that correspond to the highest Eigen values

   3. Calculate the corresponding distribution in M- dimensional weight space for each known individual by projecting their face images onto the face space

      Having initialized the system, the following steps are then used to recognize new face images

      1. Calculate a set of weights based on the input image and the m Eigen faces by projecting the input image onto each of the Eigen faces

      2. Determine if the image is a face at all by checking to see if the image is sufficiently close to face space

      3. If it is a face, classify the weight pattern as either a known person or as unknown

      4. Update the Eigen faces and/or weight patterns

      If the same unknown face is seen several times calculate the characteristic weight pattern and incorporate into the known faces

2. Eigen faces vs. Fisherfaces: Recognition using Class Specific Linear Projection

   A new approach for face recognition algorithm which is insensitive to large variation in lighting direction. The same person with the same facial expression, and seen from the same view point, can appear dramatically different when light sources illuminate the face from different directions.

   Our approach to face recognition exploits two observations:

   1. All of the images of a Lambertian surface, taken from a fixed view point, but under varying illumination, lie in a3D linear subspace of the high dimensional image space.

   2. Because of regions of shadowing, specularities, and facial expressions, the above observation does not exactly hold. In practice, certain regions of the face may have variability from image to image that often deviates significantly from the linear subspace, and consequently are less reliable for recognition.

      Fisher face tends to discount those portions of the image that are not significant for recognizing an individual; the resulting projections tend to mask the regions of the face that are highly variable. Also how well the Fisher face method extend to large databases is also not explained

3. SRDA: An Efficient algorithm for Large Scale Discriminant Analysis

   Linear Discriminant Analysis has been a popular method for extracting features that preserves class separability.The projection functions of LDA are commonly obtained by maximizing the between class covariance and simultaneously minimizing the within class covariance. One limitation of this method is the high computational cost especially for large and high dimensional data sets

4. An efficient system for Recognition of human face indifferent Expressions by Some Measured Features of the Face Using Laplacian Operator

   At first ,detect the face from an image ,then two main significant edge lines chin line and nose line are determined and next apply third order polynomial

   regression on these two lines to get a third order polynomial equation with four coefficients for each line.

   The drawback of the method is by taking the average red, green and blue color values for each region. The average color values of two distinct regions may be the same or very near. For this issue it gives some wrong results of recognzing faces.

5. Fast Linear Discriminant analysis using binary bases

   This paper presents a novel subspace representation that has similar discriminative power as LDA, and at the same time, the classification process can be computed very efficiently using NBS.

   Main contributions of this paper include:

   1. A novel efficient discriminative subspace representation called binary LDA which has comparable classification performance as LDA but with much reduced computation.

   2. An LDA guided NBS method to obtain the binary LDA bases each of which is a linear combination of binary box functions.

   3. Theoretical analysis of the properties of B-LDA bases and the associated subspace projection.

   4. The application of the binary LDA method to face recognition.

      .

6. A Fast Feature Extraction Method

   In many subspace analysis algorithms the basis vectors can be obtained by solving a standard or generalized Eigen value decomposition problem. The solutions of many other subspace analysis algorithms have to be solved by iterative manner since their objection functions are not convex.To extract features with less computational cost, an effective feature extraction algorithm known as FHT- PCA.Not only the feature extraction process but also the training process are very fast. The advantage of FHT-PCA comes from introducing fast Haar Transform (FHT) into feature extraction and subspace learning.

7. Fast Haar Transform

The Haar transform set of functions is a complete set of orthonormal rectangular basis functions. In this it is similar to the better known Walsh function set. The Haar basis functions are of special interest because they exhibit the unique characteristic of having both global and local function properties. The Haar basis functions are defined on the closed interval (0, 1), but may be extended periodically outside of the interval. The basis functions are normally collected into ordered subsets called degrees or families. The ordering within each subset is called the order or member number of each function. The mth degree contains 2" more members than the (m – l)th degree

One basic algorithm to perform the discrete Fourier transform, the fast Walsh-Hadamard transform, and the fast Haar transform. At the first stage of the algorithm, N bit reversal calculations are performed, where N = 2n is the length of the sequence. At each successive stage the number

of bit reversal operations is one-half the number at the previous stage. This transform requires on the order of 2N – 2 bit reversal calculations in addition to the usual 2n – 2 fast Haar transform operations.

After all operations at each stage of the flow graph are completed, the results may replace intermediate values from the previous stage. Since the major operations in the Haar transform are simple additions and subtractions the overhead involved in the data movement of intermediate results at each low stage is a major source of speed degradation

3. SUBSPACE LEARNING

Subspace analysis algorithms find basis vectors to represent a subspace according to proper criteria. Feature extraction can be done by projecting the high dimensional data vector in question onto the subspace spanned by the basis vectors. This technique has been widely used utilized in the computer vision, data mining and multimedia processing areas.

Feature extraction is only one of the steps to perform a computer vision or data mining task and many other steps have to compete with the feature extraction step for the limited computational resources. On the other hand, although it is expensive to calculate the basis vectors, they can be obtained in an offline fashion in various applications.

Subspace learning is the process of finding a proper feature subspace and then projecting high- dimensional data onto the learned low-dimensional subspace. The projection operation requires many floating- point multiplications and additions, which makes the projection process computationally expensive. To tackle this problem, this paper proposes two simple-but-effective fast subspace learning and image projection methods, fast Haar transform (FHT) based principal component analysis and FHT based spectral regression Discriminant analysis.

Face image is given as input from Face Image Database for calculating training percentage. In that, we attain a value in percentage format and according to that value, images are been splitted as training image and testing image.

In Training Image, face feature extraction algorithms are used for feature extraction. Algorithms used in my paper are,

• Principal Component Analysis [PCA]

• Spectral Regression Discriminant Analysis [SRDA]

• Fast Haar Transform Principal Component Analysis [FHT PCA]

• Fast Haar Transform Spectral Regression Discriminant Analysis [FHT SRDA]

Subspace based methods have been frequently used in face analysis. Experimental results on face images in order to demonstrate the computational superiority of the

proposed methods, FHT-PCA and FHT-SRDA, over classical PCA and SRDA. The ORL face database, Yale face database, and FERET face database were used in the experiments.

ORL Face Database:

The ORL database contains face images collected from 40 subjects, 10 images per subject. For training, we randomly selected five images per subject, and used the remaining images for testing. In this way, we run the system five times and obtain five different training and testing sets. Average results on these data sets are reported here.

YALE Face Database:

The Yale database contains 165 images of 15 individuals and each individual consists of 11 images. This database involves variations in facial expression and illumination. Seven images of each individual are randomly chosen for training, while the remaining four images are used for testing. In this way, the system is run five times and obtain five different training and testing sets. Average results on the data sets are reported here. In these experiments, the angle threshold and the image size is 64 x 64.

FERET Face Database:

A subset of the FERET face database was used . The subset contains 1394 images of 197 subjects with 7 images per subject. The filenames of the 7 images are marked with two character strings: ba, bj, bk, be, bf, bd, and bg. This database involves variations in expression, pose, and others. As in the experiments on the Yale face data base, the angle threshold is set and the image size is 64 x 64. Experimental results on these three face databases demonstrate the effectiveness and efficiency of the Feature Extraction algorithms.

3.1 Module Specifications

Applying human visual property in the recognition of faces, people can identify face from very far distance, even the details are vague. That means the symmetry characteristic is enough to be recognized. Human face is made up of eyes, nose, mouth and chin etc. To detect the eyes is very important in face feature extraction. Common method to locate eyes is based on the property of valley points of luminance in eye-areas. Combining the point searching with directional projection and the symmetry of two eyeballs to locate eyes.

In a general way we can improve the accuracy of location by using the relationship between two eyes. Firstly, we need to locate the sensitivity area of two eyes. The centres of eyes are located by searching the valley points in the local luminance image.

As a biometric, facial recognition is a form of computer vision that uses faces to attempt to identify a person or verify a persons claimed identity. Regardless of specific method used, facial recognition is accomplished in a five step process.

1. First, an image of the face is acquired.

2. Second, software is employed to detect the location of any faces in the acquired image.

3. Once the facial detction software has targeted a face, it can be analyzed.

4. The fourth step is to compare the template generated in step three with those in a database of known faces.

5. The final step is determining whether any scores produced in step four are high enough to declare a match.

4. ALGORITHMS USED

1. PRINCIPAL COMPONENT ANALYSIS

   Principal component analysis (PCA) involves a mathematical procedure that transforms a number of possibly correlated variables into a number of uncorrelated variables called principal components, related to the original variables by an orthogonal transformation. Depending on the field of application, it is also named the discrete KarhunenLoève transform (KLT), the Hotelling transform or proper orthogonal decomposition (POD).

   PCA is the simplest of the true eigenvector-based multivariate analyses. Often, its operation can be thought of as revealing the internal structure of the data in a way which best explains the variance in the data.

   Principle

   1. Linear projection method to reduce the number of parameters

   2. Transfer a set of correlated variables into a new set of uncorrelated variables

   3. Map the data into a space of lower dimensionality

   4. Form of unsupervised learning

      Properties

      1. It can be viewed as a rotation of the existing axes to new positions in the space defined by original variables

      2. New axes are orthogonal and represent the directions with maximum variability

2. Extraction using PCA

Eye features are identified relative to the position of the mouth, by searching for regions which satisfy some statistical, geometrical, and structural properties of the eyes in frontal face images. On detecting a feature set containing a mouth and two eyes, PCA analysis is performed over a normalized search space relative to the distance between the two eyes. In test image, one image is acquired as input and mean, covariance and Eigen values are calculated. It is been normalized as feature and it is been compared to the features in training section. If features are matched, equivalent image is been found. If not matched, no image is detected.

Computing PCA using Covariance method and Eigen Vectors

The goal is to transform a given data set X of dimension M to an alternative data set Y of smaller dimension L. Equivalently; we are seeking to find the matrix

Y, where Y is the KarhunenLoève transform (KLT) of matrix X:

Y = KLT{X}

Organize the data set

Suppose you have data comprising a set of observations of M variables, and you want to reduce the data so that each observation can be described with only L variables, L < M. Suppose further, that the data are arranged as a set of N data vectors X1Xn with each representing a single grouped observation of the M variables.

• Write X1Xn as column vectors, each of which has M rows.

• Place the column vectors into a single matrix X of dimensions M × N.

  Calculate the empirical mean

• Find the empirical mean along each dimension m = 1, …, M.

• Place the calculated mean values into an empirical mean vector u of dimensions M × 1.

  Calculate the deviations from the mean

  Mean subtraction is an integral part of the solution towards finding a principal component basis that minimizes the mean square error of approximating the data. Hence we proceed by centering the data as follows:

• Subtract the empirical mean vector u from each column of the data matrix X.

• Store mean-subtracted data in the M × N matrix B.

  B = X – uh

  where h is a 1 × N row vector of all 1s: h[n] = 1 for n = 1N

  Find the covariance matrix

• Find the M × M empirical covariance matrix C

  from the outer product of matrix B with itself: C = E [B B] = E [B.B*] = 1/N B.B*

  where

  E is the expected value operator,

  is the outer product operator, and

  * is the conjugate transpose operator. Note that if B consists entirely of real numbers, which is the case in many applications, the "conjugate transpose" is the same as the regular transpose.

  Find the eigenvectors and eigenvalues of the covariance matrix

• Compute the matrix V of eigenvectors which diagonalizes the covariance matrix C:

  where D is the diagonal matrix of eigenvalues of

  C. This step will typically involve the use of a computer-based algorithm for computing eigenvectors and eigenvalues.

• Matrix D will take the form of an M × M diagonal matrix, where

  is the mth eigenvalue of the covariance matrix C, and

• Matrix V, also of dimension M × M, contains M column vectors, each of length M, which represent the M eigenvectors of the covariance matrix C.

• The eigenvalues and eigenvectors are ordered and paired. The mth eigenvalue corresponds to the mth eigenvector.

  Rearrange the eigenvectors and eigenvalues

• Sort the columns of the eigenvector matrix V and eigenvalue matrix D in order of decreasing eigenvalue.

• Make sure to maintain the correct pairings between the columns in each matrix.

  Compute the cumulative energy content for each eigenvector

• The eigenvalues represent the distribution of the source data's energy among each of the eigenvectors, where the eigenvectors form a basis for the data. The cumulative energy content g for the mth eigenvector is the sum of the energy content across all of the eigenvalues from 1 through m:

  Select a subset of the eigenvectors as basis vectors

• Save the first L columns of V as the M × L matrix

  W:

  W [p,q] = V [p,q] for p = 1M q = 1L where 1 L M

• Use the vector g as a guide in choosing an appropriate value for L. The goal is to choose a value of L as small as possible while achieving a reasonably high value of g on a percentage basis. For example, you may want to choose L so that the cumulative energy g is above a certain threshold, like 90 percent. In this case, choose the smallest value of L such that

  Convert the source data to z-scores

• Create an M × 1 empirical standard deviation vector s from the square root of each element along the main diagonal of the covariance matrix C:

• Calculate the M × N z-score matrix:

  (divide element-by-element)

• Note: While this step is useful for various applications as it normalizes the data set with respect to its variance, it is not integral part of PCA/KLT!

  Project the z-scores of the data onto the new basis

• The projected vectors are the columns of the matrix Y = W* . Z = KLT {X}

• W* is the conjugate transpose of the eigenvector matrix.

• The columns of matrix Y represent the Karhunen Loeve transforms (KLT) of the data vectors in the columns of matrix X.

An important statistical property of eye image regions is that they correspond to high intensity variance as a result of the fact that human eyes generally contain both black and white regions. Such regions can be identified by computing their variances.

1. CONCLUSION

   Feature extraction from face image database named as ORL face image database, YALE face image database and FERET face image database using PCA algorithm for training image was calculated and stored in database. Likewise, test images also follow the same procedure for feature extraction. Also face recognition process is followed using PCA algorithm.

   My further work is to perform the feature extraction process from face image databases named as ORL face image database, YALE face image database and FERET face image database using various other face feature extraction algorithms which are Fast Haar Transform (FHT) based Principal Component Analysis, Spectral Regression Discriminant Analysis and FHT based SpectralRegression Discriminant Analysis and compare the performance of these algorithms in face recognition.

2. REFERENCES

1. D. Cai, X. He, and J. Han, SRDA: An efficient algorithm for largescale discriminant analysis, IEEE Trans. Knowl. Data Eng., vol. 20, no. 1, pp. 112, Jan. 2008.

2. J. Pan, Y. Pang, X. Li, Y. Yuan, and D. Tao, A fast feature extraction method, in Proc.. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, 2009, pp. 17971800

3. P. R. Roeser and M. E. Jernigan, Fast Haar transform, IEEE Trans. Comput., vol. C31, no. 2, pp. 175177, Feb. 1982.

4. M. Turk and A. Pentalnd, Eigenfaces for recognition, J. Cognitive Neurosci., vol. 3, no. 1, pp. 7186, 1991.

5. P. N. Belhumeur, J. P. Hespanha, and D. J. Kriegman, Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection, IEEE Trans. Pattern Anal. Mach. Intell., vol. 19, no. 7, pp. 711720, Jul. 1997.

6. P. R. Roeser and M. E. Jernigan, Fast Haar transform, IEEE Trans. Comput., vol. C31, no. 2, pp. 175177, Feb. 1982