US 7,515,740 B2Grant

Face recognition with combined PCA-based datasets

Issue Date:2009-04-07

•34 Claims

•5 Drawing Sheets

Abstract

A face recognition method for working with two or more collections of facial images is provided. A representation framework is determined for a first collection of facial images including at least principle component analysis (PCA) features. A representation of said first collection is stored using the representation framework. A modified representation framework is determined based on statistical properties of original facial image samples of a second collection of facial images and the stored representation of the first collection. The first and second collections are combined without using original facial image samples. A representation of the combined image collection (super-collection) is stored using the modified representation framework. A representation of a current facial image, determined in terms of the modified representation framework, is compared with one or more representations of facial images of the combined collection. Based on the comparing, it is determined which, if any, of the facial images within the combined collection matches the current facial image.

Metadata

Assignees

FotoNation Vision Limited
National University of Ireland

Inventors

Peter Corcoran
Gabriel N. Costache

Application Information

Application Number:US 11/833,224

Filing Date:2007-08-02

Priority Date:2006-08-02

Art Unit:2624

Classifications

IPC:

G06K9/00

Patent Drawings (5 sheets)

Description

PRIORITY

[0001] This application claims the benefit of priority to U.S. provisional patent application No. 60/821,165, filed Aug. 2, 2006, which is hereby incorporated by reference.

BACKGROUND OF THE INVENTION

[0002] Face tracking technology has been recently introduced into consumer digital cameras enabling a new generation of user tools for the analysis and management of image collections (see, e.g., http://www.fotonation.com/index.php?module=company.news&id=39, wherein the entire site www.fotoination.com is incorporated by reference. In earlier research, it had been concluded that it should be practical to employ face similarity measures as a useful tool for sorting and managing personal image collections (see, e.g., P. Corcoran, G. Costache, Automated sorting of consumer image collections using face and peripheral region image classifiers, Consumer Electronics, IEEE Transactions on Volume 51, Issue 3, August 2005 Page(s):747-754; G. Costache, R. Mulryan, E. Steinberg, P. Corcoran, In-camera person-indexing of digital images Consumer Electronics, 2006, ICCE '06. 2006 Digest of Technical Papers, International Conference on 7-11 January 2006 Page(s):2; and P. Corcoran, and G. Costache, Automatic System for In-Camera Person Indexing of Digital Image Collections, Conference Proceedings, GSPx 2006, Santa Clara, Calif., October 2006, which are all hereby incorporated by reference). The techniques described in this research rely on the use of a reference image collection as a training set for PCA based analysis of face regions.

[0003] For example, it has been observed that when images are added to such a collection there is no immediate requirement for retraining of the PCA basis vectors and that results remain self consistent as long as the number of new images added is not greater than, approximately 20% of the number in the original image collection. Conventional wisdom on PCA analysis would suggest that as the number of new images added to a collection increases to certain percentage that it becomes necessary to retrain and obtain a new set of basis vectors.

[0004] This retraining process is both time consuming and also invalidates any stored PCA-based data from images that were previously analyzed. It would be far more efficient if we could find a means to transform face region data between different basis sets.

[0005] In addition, it has been suggested that it is possible to combine training data from two or more image collections to determine a common set of basis vectors without a need to retrain from the original face data. This approach has been developed from use of the “mean face” of an image collection to determine the variation between two different image collections.

[0006] The mean face is computed as the average face across the members of an image collection. Other faces are measured relative to the mean face. Initially, the mean face was used to measure how much an image collection had changed when new images were added to that collection. If mean face variation does not exceed more than a small percentage, it can be assumed that there is no need to recompute the eigenvectors and to re-project the data into another eigenspace. If, however, the variation is significant between the two collections, then the basis vectors are instead re-trained, and a new set of fundamental eigenvectors should be obtained. For a large image collection, this is both time consuming and inefficient as stored eigenface data is lost. It is thus desired to have an alternative approach to a complete retraining which is both effective and efficient.

SUMMARY OF THE INVENTION

[0007] A face recognition method for working with two or more collections of facial images is provided. A representation framework is determined for a first collection of facial images including at least principle component analysis (PCA) features. A representation of said first collection is stored using the representation framework. A modified representation framework is determined based on statistical properties of original facial image samples of a second collection of facial images and the stored representation of the first collection. The first and second collections are combined without using original facial image samples. A representation of the combined image collection (super-collection) is stored using the modified representation framework. A representation of a current facial image, determined in terms of the modified representation framework, is compared with one or more representations of facial images of the combined collection. Based on the comparing, it is determined whether one or more of the facial images within the combined collection matches the current facial image.

[0008] The first collection may be updated by combining the first collection with a third collection by adding one or more new data samples to the first collection, e.g., according the further face recognition method described below.

[0009] Data samples of the first collection may be re-projected into a new eigenspace without using original facial images of the first collection. The re-projecting may instead use existing PCA features.

[0010] Training data may be combined from the first and second collections.

[0011] The method may be performed without using original data samples of the first collection.

[0012] The first and second collections may contain samples of different dimension. In this case, the method may include choosing a standard size of face region for the new collection, and re-sizing eigenvectors using interpolation to the standard size. The samples of different dimension may be analyzed using different standard sizes of face region.

[0013] The modified representation framework may be generated in accordance with the following:

[0014]

C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{(N^{C 1} + N^{C 2})} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T}

[0015] A further face recognition method for working with two or more collections of facial images is also provided. Different representation frameworks are determined for first and second collections of facial images each including at least principle component analysis (PCA) features. Different representations of the first and second collections are stored using the different representation frameworks. A modified representation framework is determined based on the different representations of the first and second collections, respectively. The first and second collections are combined without using original facial image samples. A representation of the combined image collection (super-collection) is stored using the modified representation framework. A representation of a current facial image, determined in terms of the modified representation framework, is compared with one or more representations of facial images of the combined collection. Based on the comparing, it is determined whether one or more of the facial images within the combined collection matches the current facial image.

[0016] The PCA features may be updated based on first eigenvectors and first sets of eigenvalues for each of the first and second collections. The updating may include calculating a new set of eigenvectors from the previously calculated first eigenvectors of the first and second collections.

[0017] The method may be performed without using original data samples of the first and second collections.

[0018] The first and second collections may contain samples of different dimension. A standard size of face region may be chosen for the new collection. Eigenvectors may be re-sized using interpolation to the standard size. The samples of different dimension may be analyzed using different standard sizes of face region.

[0019] The modified representation framework may be generated in accordance with the following:

[0020]

\hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] ++ \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T}

[0021] One or more storage media may be provided having embodied therein program code for programming one or more processors to perform any of the methods described herein.

BRIEF DESCRIPTION OF THE DRAWINGS

[0022] FIG. 1 illustrates the application of PCA to a raw dataset.

[0023] FIG. 2 illustrates the combining of two different PCA representations of datasets in accordance with a preferred embodiment.

[0024] FIG. 3 illustrates the combining of PCA representations of datasets with supplemental raw data in accordance with a preferred embodiment.

[0025] FIG. 4 shows several plots of eigenvalue distributions for both a first and a second collection for both the classical PCA method and a method in accordance with a preferred embodiment.

[0026] FIGS. 5a-5d illustrate first eigenfaces from both a first and a second collection for both the classical method and a method in accordance with a preferred embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0027] PCA analysis is a very common technique used signal processing for reducing data dimensions and in pattern recognition for feature extraction. The main disadvantage of the technique is that the resulted PCA features are data dependent which means that they have to be re-computed every time the data collection changes its format due to merging or splitting between multiple independent datasets or adding/deleting data samples from a given dataset. Embodiments of the invention are described below for combining multiple PCA datasets. Embodiment are also provided for updating one PCA dataset when data samples are changed using the old PCA values and the statistical properties of the PCA space of each dataset without using the original data values. This is very useful when the original data values are no longer available or when is not practical to re-use them for very large data collections.

[0028] Face recognition tasks are described for two cases. The first case is when it is desired to combine two face collections already analyzed using PCA without applying PCA analysis on the merged face collection. The second case is when it is desired to add new face samples to one collection already trained using PCA. The described methods are shown to yield at least similarly effective results as the classical approach of applying the PCA algorithm on the merged collection, while involving far less computational resources.

[0029] The techniques provided herein offer a significant saving in computational effort and are quite robust and offer high repeatability in the context of eigenface analysis. The algorithm of re-computing the new eigenspace is preferably similar to the approach described in Hall P., Marshalland D., and Martin R. “Adding and Subtracting Eigenspaces” British Machine Vision Conference, Vol 2, 1999, pp: 463-472; and Hall P., D. Marshall, and R. Martin. “Merging and splitting eigenspace models.” PAMI, 22(9), 2000, pp: 1042-1048, which are each hereby incorporated by reference. The data samples may be re-projected into the new eigenspace without using the original data samples (the original faces), and instead using the old data projections (the old principal components).

[0030] A formal theoretical explanation of this method is provided below, and it is demonstrated that it is be broadly applicable to other applications when PCA based analysis is employed. A theoretical basis of principle component analysis as it is applied to eigenface analysis of face regions is next described. Preferred and alternative approaches to combining training data from multiple, previously-trained, datasets are then discussed. We next present the results of some experiments with image collections drawn from very different sources and demonstrate the practical results of applying our technique. Finally a description of the application of this technique in building practical tools and an application framework for the analysis, sorting and management of personal image collections is given.

Theory

[0031] Principal Component Analysis (PCA) is one of the most common approaches used in signal processing to reduce the dimensionality of problems where we need to deal with large collections of data samples. PCA is a linear transformation that maps the data to a new coordinate system so that the greatest variance across the data set comes to lie on the first coordinate or principal component, the second greatest variance on the second coordinate, and so on. These basis vectors represent the eigenvectors of the covariance matrix of the data samples and the coefficients for each data sample are the weights, or principal components of that data sample. Unlike other linear transformations, such as DCT, PCA does not have a fixed set of basis vectors. Its basis vectors depend on the data set.

[0032] PCA can be used for reducing dimensionality in a dataset while retaining those characteristics of the dataset that contribute most to its variance, by keeping lower-order principal components and ignoring higher-order ones. One of the advantages of PCA is that we need only compare the first 20 principle components out of a possible 1028 components where we use face regions of 32×32 pixel size. Calculating the distance between the principal components of two given data samples allows a measure of similarity between the two samples to be determined.

[0033] The basis vectors for PCA are not fixed, thus when new data samples are added to a data set there are issues as to the validity and applicability of the PCA method. In particular, two situations which may arise include the following:

- [0034] (i) There are two collections of data which are already analyzed using PCA and it is desired to determine a common basis vector set for the combined collection and, ideally, transform the predetermined PCA descriptors without having to recalculate new descriptor sets for each item of data; and
- [0035] (ii) There is an existing collection of data which is analyzed using PCA and it is desired to add a significant number of new raw data items to this dataset.

[0036] The classical solution for either of these cases is to recalculate the full covariance matrix of the new (combined) dataset and then recalculate the eigenvectors for this new covariance matrix. Computationally, however, this is not an effective solution, especially when dealing with large collections of data.

[0037] A different technique is provided herein to calculate the basis vectors, the eigenvalues and to determine the principle components for the new collection. The first eigenvector and the first set of eigenvalues are used from each collection in case (i), and preferably only these. The first eigenvector and the first set of eigenvalues from the original collection and the new data are used in case (ii). These have the advantages that the original data samples need not be saved in memory, and instead only the principle components of these samples are stored. Also, the new set of eigenvectors are calculated from the eigenvectors originally calculated for each collection of data. A detailed mathematical description of these techniques are provided below.

PCA Mathematical Model

[0038] To begin, assume a collection of N data samples S_iwith i={1,N}. Each data sample is a vector of dimension m with m<N. The first step consists in changing the collection of data so that it will have a zeros mean, which is done by subtracting the mean of the data samples

[0039]

({Mean}_{S} = \sum S_{i} / N)

from each sample. The PCA algorithm consists in computing the covariance matrix Cov_SSusing eq. 1:

[0040]

\begin{matrix} {Cov}_{SS} = \frac{1}{N} [S - {Mean}_{S}] \times {[S - {Mean}_{S}]}^{T} & (1) \end{matrix}

[0041] The matrix S is formed by concatenating each data vector S_i. The size of the covariance matrix is equal to m×m and is independent of the number of data samples N. We can compute the eigenvector matrix E=[e₁e₂. . . e_m] where each eigenvector e_ihas the same dimension as the data samples m and the eigenvalues [v₁v₂. . . v_m] of the covariance matrix using eq 2:
Cov_SS=E×V×E^T (2)
where the matrix V has all the eigenvalues on the diagonal and zeros in rest.

[0042]

\begin{matrix} V = [\begin{matrix} v_{1} & 0 & \dots & 0 \\ 0 & v_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & v_{m} \end{matrix}] & (3) \end{matrix}

[0043] We can reconstruct each data samples using a linear combination of all eigenvectors using eq. 4.
S_i=E×P_i+Mean_S (4)
where P_irepresents the principal component coefficients for data sample S_iand can be computed by projecting the data sample on the coordinates given by the eigenvectors using eq 5.
P_i=E^T×[S_i−Mean_S] (5)

[0044] By arranging the eigenvalues in descending order we can approximate the covariance matrix by keeping only a small number of eigenvectors corresponding to the largest values of the eigenvalues. The number of eigenvalues is usually determined by applying a threshold to the values, or maintaining the energy of the original data. If we keep the first n<m eigenvalues and their corresponding eigenvectors, the approximation of the covariance matrix can be computed as:
Côv_SS=Ê×{circumflex over (V)}×Ê^T (6)
with V=[v₁v₂. . . v_n]

[0045] The data can be as well approximated using only the first n principal coefficients which correspond to the eigenvectors with largest variations inside the data collection.
Ŝ_i=Ê×P_i+Mean_S (7)

[0046] The standard results of applying PCA to a raw dataset are illustrated in FIG. 1.

Dataset Combination Scenarios

[0047] Let's assume that we have one collection of data C¹which is analyzed using PCA algorithm which means we have its eigenvectors E^C1=[e^C1₁e^C1₂. . . e^C1_n1], the eigenvalues [v^C1₁v^C1₂. . . v^C1_n1] the PCA coefficients for each sample in the collection Pc^C1and supplementary we also stored the mean data sample in the collection Mean^C1. We also can assume at this moment that the original data samples are no longer available for analysis or is not practical viable to access them again. This fact is important when working with very large datasets where it will be time consuming to re-read all datasamples for applying classical PCA or when working with temporary samples that can be deleted after they are first analyzed (e.g. when working with images for face recognition the user may delete some used to construct PCA based models).

[0048] Now we consider two different cases where the data in the collection will be changed:

- [0049] (i) either a new collection of data which was already analyzed using PCA has to be added to the original collection in order to form a super-collection, or
- [0050] (ii) a new set of raw (unanalyzed) data samples are to be added to the collection in order to update it.

[0051] Lets consider the first case of combination:

Combining Two Collections of PCA Data

[0052] Let's assume we want to combine collection C^ldescribed above with another collection of data C²also PCA analyzed with eigenvectors E^C2=[e^C2₁e^C2₂. . . e^C2_n2], eigenvalues [v^C2₁v^C2₂. . . v^C2_n2], the PCA coefficients Pc^C2and the mean data sample Mean^C2. We want to combine the two collections into a super collection C without accessing the original data from the two collections S^C1and S^C2(S^C1and S^C2are data matrices where each column S^C1_jrepresented a vector data sample). The mean sample in the collection can be computed as:

[0053]

\begin{matrix} Mean = \frac{N^{C 1} * {Mean}^{C 1} + N^{C 2} * {Mean}^{C 2}}{N^{C 1} + N^{C 2}} & (8) \end{matrix}

where N^C1and N^C2represent the number of data samples in each collection. It is easy to prove [5] that the covariance of the super collection Cov_Ccan be computed as:

[0054]

\begin{matrix} {Cov}_{C} = \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 1} - Mean) (S^{C 2} - Mean)] \times {[(S^{C 1} - Mean) (S^{C 2} - Mean)]}^{T} = \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 1} - {Mean}^{C 1})] \times {[(S^{C 1} - {Mean}^{C 1})]}^{T} + \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2})] \times {[(S^{C 2} - {Mean}^{C 2})]}^{T} + \frac{1}{N^{C 1} + N^{C 2}} \frac{N^{C 1} N^{C 2}}{N^{C 1} + N^{C 2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} {Cov}_{C 1} + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} {Cov}_{C 2} + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times [({Mean}^{C 1} - {Mean}^{C 2})] & (9) \end{matrix}

[0055] As was stated above we cannot re-compute the covariance matrix using eq. 2 which requires all of the original data samples, in our case the original faces. There are two options: either we store the complete covariance matrices from the two collections and use them to compute the exact values of the covariance matrix of the supercollection or we can approximate each covariance matrix using the eigenvalues and eigenvectors from each individual collection, viz:

[0056]

\begin{matrix} C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} & (10) \end{matrix}

[0057] If we assumed that from each collection the eigen decomposition (number of eigenvectors retained) was done so that the energy of the dataset is conserved we can assume (prove later in tests) that the face space given by eigen-decomposition of the covariance matrix of the super collection will be close to the estimated face space given by the eigen-decomposition of the estimated covariance matrix given by eq. 9.

[0058] In other words we have to show that the estimated eigenvectors and eigenvalues using the covariance matrix computed in eq 9 are close to the eigenvectors and eigenvalues computed applying classical PCA on the concatenated supercollection. Not all eigenvectors will be similar, only the ones corresponding to the highest variations in the datasets (with the largest corresponding eigenvalues).

[0059] The reconstruction of a combined dataset from two independently trained PCA data representations is illustrated in FIG. 2.

[0060] Another issue that may need to be addressed is the case where the two collections of data contain samples of different dimension. For example, in face recognition it might be necessary to combine two collections of faces that were analyzed using different standard sizes of face region. In this case we should choose a standard size of face region for the super collection (e.g. the minimum of the two sizes used), resizing using interpolation the eigenvectors of the combined collection to this standard size

[0061] Once we have determined the covariance matrix of the super collection we can use the eigen decomposition again and compute the eigenvectors E=[e₁e₂. . . e_n] and the eigenvalues V=[v₁v₂. . . v_n] of the super collection. The number of eigenvalues kept for analysis n is independent of n₁and n₂. Once we have the eigenvectors we can project the data samples. Remember that we don't have the original data samples to project them easily so we have to re-create them from the old PCA coefficients. If we want to re-create a data sample we can use eq. 4. The result represents the data sample from which the mean data sample in collection 1 was subtracted so the exact value of the data sample is computed as:
Ŝ_i_{C1,C2}=Ê^{C1,C2}×P_i_{C1,C2}+Mean^{C1,C2} (11)

[0062] We have to subtract the mean of the super collection Mean (eq. 8) from this data sample. We can re estimate the Pc coefficients for each data sample in the super collection as:
{circumflex over (P)}c_i^{C1,C2}=Ê^T×[E^{C1,C2}×P_i^{C1,C2}+Mean^{C1,C2}−Mean] (12)

[0063] In this case we assume that we have the collection of data C¹described and we want to add new N^C2data samples that are not analyzed already. The sample matrix is S^C2and their mean value is Mean^C2. The new covariance matrix will be computed as:

[0064]

\begin{matrix} \hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{2} & (13) \end{matrix}

[0065] Applying the same algorithm as described in (1) we compute the new eigenvectors and eigenvalues. Using eq. 13 we can update the PCA coefficients of the initial collection and to compute the PCA coefficients of the new data samples we use:
{circumflex over (P)}c_i^C2=Ê^T×[S_i^C2−Mean] (14)
where the Mean matrix can be computed using eq. 8.

[0066] This situation where additional raw data is added to a dataset with a (trained) PCA representation is illustrated in FIG. 3.

Experimental Results

[0067] We applied the method described in the previous section for our purpose: face recognition. We used an initial test collection of 560 faces (56 individuals each with 10 faces). The images are separated randomly into two datasets: the training dataset containing half of the faces and the remaining half were used as a testing dataset.

[0068] Two separate tests were performed by splitting the training faces into two collections with different number of faces. The faces were randomly attached to one of the initial collections:

- [0069] 1. Test A: we split the training collection into 2 collections each with 140 faces and performed classification tasks using three cases: simple concatenation of PCA coefficients without updating, classical combination using data samples and the proposed method.
- [0070] 2. Test B: using two collections one with 240 faces and the other with the remaining 40 faces in two cases: the classical approach and the proposed method. Also for this test we used both scenarios: combining two collections of PCA data and adding new data to a trained collection.

[0071] All faces were resized to 16×16 pixels, gray scale images were used and the number of PCA coefficients used in the classification stage was always 20. For classification the nearest neighbourhood method was preferred and the Euclidean distance between feature vectors was used.

[0072] FIG. 4 represents the variation of the first 50 eigenvalues using the classical approach of combining two collections and the proposed method along with the eigenvalue variations inside the two separate collections. It can be noticed that the variations between the classical approach of combining the method and the proposed approach are very similar close to identical in the first part of the graph where the classical eigenvalues can not be noticed.

[0073] In order to see how the eigenvectors differ from the classical combination compared with the proposed method FIG. 2 shows the first eigenfaces from each collection along with the first eigenfaces obtained using the classical combination and the proposed method. It can be noted that the representation using the two methods have almost identical distributions.

[0074] It can be noted that the first eigenvector obtained applying the classical PCA over the combined collection is similar with the first eigenvector obtained using our approach and both of them are really different compared with the first eigenvector from each of the two sub-collections that we want to combine.

[0075] For Test A our second scenario is unlikely because the collections have the same number of samples so we tested only the first scenario: combining the two collections. The results are given in the first table.

[0076]

TABLE 1

Recognition Rates for Test A
	Combining collections

	Simple concatenation	48.32%
	Classical combination	84.28%
	Proposed method	85.23%

[0077] For Test B we used both scenarios: combining two collections (one having 240 data samples and the other having only 40 samples) and adding new sample to one collection. The results are given in Table 2.

[0078]

TABLE 2

Recognition Rates for Test B
	Combining	Adding samples
	collections	to collection

	Simple concatenation	62.14%	Na
	Classical combination	84.28%	84.28%
	Proposed method	84.64%	83.14%

[0079] It can be observed that in both tests the proposed combination method had the results very close to the classical approach of completely re-analyzing the newly combined collection using PCA. On the other hand, as expected, if the PCA coefficients are not updated after combination or the addition of multiple samples to the collection the recognition rate drops significantly. For our test case, adding 16% of new images to a collection produced more than a 20% decline in the recognition rate.

[0080] Techniques have been described for updating the PCA coefficients of data samples when the collection of data changes due to adding new data or combining two collections of data previously analyzed using PCA into a super collection. An advantage of the techniques is that they do not require that the original dataset is preserved in order to update its coefficients. This is very helpful when analyzing large collections of data and mandatory when the original data is lost. Another advantage is that the technique is much faster than the classical method or recomputing of the PCA coefficients using the original dataset, because the dimension of the PCA data is significantly smaller than the dimension of the original data, and one of the properties of the PCA algorithm is its dimensionality reduction. For example, if a face image raw data sample has 64×64 pixels, about 5 k of pixel data is used in storing it in order to keep that data sample. Now, if there are 100 faces, then 500 k of data space is involved. In a PCA representation, probably 20-30 basis vectors are used to describe each face. That means that 100 images can be stored using about 3000, or 3 k of data, which is more than 130 times less than storing the raw data samples. So, an advantage of the technique is that the original face images are not needed as the technique regenerates them from the PCA representation framework.

[0081] While an exemplary drawings and specific embodiments of the present invention have been described and illustrated, it is to be understood that that the scope of the present invention is not to be limited to the particular embodiments discussed. Thus, the embodiments shall be regarded as illustrative rather than restrictive, and it should be understood that variations may be made in those embodiments by workers skilled in the arts without departing from the scope of the present invention as set forth in the claims that follow and their structural and functional equivalents.

[0082] In addition, in methods that may be performed according to the claims below and/or preferred embodiments herein, the operations have been described in selected typographical sequences. However, the sequences have been selected and so ordered for typographical convenience and are not intended to imply any particular order for performing the operations, unless a particular ordering is expressly provided or understood by those skilled in the art as being necessary.

[0083] All references cited above, as well as that which is described as background, the invention summary, the abstract, the brief description of the drawings and the drawings, are hereby incorporated by reference into the detailed description of the preferred embodiments as disclosing alternative embodiments.

Claims

We claim:

1. A face recognition method for working with two or more collections of facial images, and using a processor to carry out the method, wherein the method comprises:

(a) determining a first representation framework for a first collection of facial images including at least principle component analysis (PCA) features;

(b) storing a representation of said first collection using said first representation framework;

(c) determining a modified representation framework based on statistical properties of original facial image samples of a second collection of facial images and the stored representation of the first collection;

(d) combining the stored representation of the first collection and the second collection without using original facial image samples including back-projection the second collection into the first representation framework, combining the back-projected representation of the second collection and the stored representation of the first collection into a combined image collection (super-collection), and forward projecting the combined collection into the second representation framework;

(e) storing a representation of the combined image collection (super-collection) using said modified representation framework;

(f) comparing a representation of a current facial image, determined in terms of said modified representation framework, with one or more representations of facial images of the combined collection; and

(g) based on the comparing, determining whether one or more of the facial images within the combined collection matches the current facial image.

2. The method of claim 1, further comprising, prior to (b), updating said first collection by combining the first collection with a third collection.

3. The method of claim 2, wherein the updating comprises adding one or more new data samples to the first collection.

4. The method of claim 1, further comprising re-projecting data samples of the first collection into a new eigenspace without using original facial images of the first collection.

5. The method of claim 4, wherein the re-projecting uses existing PCA features.

6. The method of claim 1, further comprising combining training data from said first and second collections.

7. A method according to claim 1, which does not use original data samples of the first collection.

8. The method of claim 1, wherein the first and second collections contain samples of different dimension, and the method further comprises:

(i) choosing a standard size of face region for the new collection, and

(ii) re-sizing eigenvectors using interpolation to the standard size.

9. The method of claim 8, wherein said samples of different dimension were analyzed using different standard sizes of face region.

10. The method of claim 1, further comprising generating the modified representation framework according to the following:

C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} .

11. A face recognition method operable on two or more collections of images, one or more of said images containing one or more facial regions, and using a processor to carry out the method, wherein the method comprises:

(a) determining distinct representation frameworks for first and second sets of facial regions extracted from corresponding image collections each framework including at least principle component analysis (PCA) features;

(b) storing representations of said first and second sets of facial regions using their respective representation frameworks;

(c) determining a third, distinct representation framework based on the representations of the first and second sets of facial regions;

(d) combining the stored representation of the first and the second sets of facial regions without using original facial image samples including back-projecting the sets of facial regions into their respective representation frameworks, combining the two back-projected representations of these sets of facial regions into a combined dataset, and forward projecting the combined dataset into the third representation framework;

(e) storing a representation of the combined dataset using said third representation framework;

(f) comparing a representation of a current facial region, determined in terms of said third representation framework, with one or more representations of facial images of the combined dataset; and

(g) based on the comparing, determining whether one or more of the facial images within the combined dataset matches the current facial image.

12. The method of claim 11, further comprising updating the PCA features based on first eigenvectors and first sets of eigenvalues for each of the first and second sets of facial regions.

13. The method of claim 12, wherein the updating comprises calculating a new set of eigenvectors from the previously calculated first eigenvectors of the first and second sets of facial regions.

14. A method according to claim 11, which does not use original data samples of the first and second sets of facial regions.

15. The method of claim 11, wherein the first and second sets of facial regions contain samples of different dimension, and the method further comprises:

(i) choosing a standard size of face region, and

(ii) re-sizing eigenvectors using interpolation to the standard size.

16. The method of claim 15, wherein said samples of different dimension were analyzed using different standard sizes of face region.

17. The method of claim 11, further comprising generating the third representation framework according to the following:

\hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] ++ \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} .

18. One or more processor readable media having program code embodied therein for programming one or more processors to perform a face recognition method for working with two or more collections of facial images, wherein the method comprises:

(a) determining a first representation framework for a first collection of facial images including at least principle component analysis (PCA) features;

(b) storing a representation of said first collection using said first representation framework;

(d) combining the stored representation of the first collection and the second collection without using original facial image samples including back-projecting the second collection into the first representation framework, combining the back-projected representation of the second collection and the stored representation of the first collection into a combined image collection (super-collection), and forward projecting the combined collection into the second representation framework;

(e) storing a representation of the combined image collection (super-collection) using said modified representation framework;

(g) based on the comparing, determining whether one or more of the facial images within the combined collection matches the current facial image.

19. The one or more media of claim 18, wherein the method further comprises, prior to (b), updating said first collection by combining the first collection with a third collection.

20. The one or more media of claim 19, wherein the updating comprises adding one or more new data samples to the first collection.

21. The one or more media of claim 18, wherein the method further comprises re-projecting data samples of the first collection into a new eigenspace without using original facial images of the first collection.

22. The one or more media of claim 21, wherein the re-projecting uses existing PCA features.

23. The one or more media of claim 18, wherein the method further comprises combining training data from said first and second collections.

24. A one or more media according to claim 18, wherein the method does not use original data samples of the first collection.

25. The one or more media of claim 18, wherein the first and second collections contain samples of different dimension, and the method further comprises:

(i) choosing a standard size of face region for the new collection, and

(ii) re-sizing eigenvectors using interpolation to the standard size.

26. The one or more media of claim 25, wherein said samples of different dimension were analyzed using different standard sizes of face region.

27. The one or more media of claim 18, wherein the method further comprises generating the modified representation framework according to the following:

C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} .

28. One or more processor readable media having program code embodied therein for programming one or more processors to perform a face recognition method for working with two or more collections of facial images, wherein the method comprises:

(b) storing representations of said first and second sets of facial regions using their respective representation frameworks;

(c) determining a third, distinct representation framework based on the representations of the first and second sets of facial regions;

(e) storing a representation of the combined dataset using said third representation framework;

(f) comparing a representation of a current facial region, determined in terms of said third representation framework, with one or more representations of facial images of the combined dataset; and

(g) based on the comparing, determining whether one or more of the facial images within the combined dataset matches the current facial image.

29. The one or more media of claim 28, wherein the method further comprises updating the PCA features based on first eigenvectors and first sets of eigenvalues for each of the first and second sets of facial regions.

30. The one or more media of claim 29, wherein the updating comprises calculating a new set of eigenvectors from the previously calculated first eigenvectors of the first and second sets of facial regions.

31. A one or more media according to claim 28, wherein the method does not use original data samples of the first and second sets of facial regions.

32. The one or more media of claim 28, wherein the first and second sets of facial regions contain samples of different dimension, and the method further comprises:

(i) choosing a standard size of face region, and

(ii) re-sizing eigenvectors using interpolation to the standard size.

33. The one or more media of claim 32, wherein said samples of different dimension were analyzed using different standard sizes of face region.

34. The one or more media of claim 28, wherein the method further comprises generating the third representation framework according to the following:

\hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] ++ \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} .

Patent Citations (11)

Patent	Date	Inventor	Cited By
US5164992(A)	1992-11-01	Turk et al.	Applicant
US5642431(A)	1997-06-01	Poggio et al.	Applicant
US5710833(A)	1998-01-01	Moghaddam et al.	Examiner
US6430307(B1)	2002-08-01	Souma et al.	Applicant
US7046339(B2)	2006-05-01	Stanton et al.	Applicant
US2006/0006077(A1)	2006-01-01	Mosher	Applicant
US2006/0120599(A1)	2006-06-01	Steinberg et al.	Applicant
US2006/0140055(A1)	2006-06-01	Ehrsam	Applicant
US2006/0140455(A1)	2006-06-01	Costache et al.	Applicant
WO2007/142621(A1)	2007-12-01		Applicant
WO2008/015586(A2)	2008-02-01		Applicant

Non-Patent Literature (12)

PCT Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration, for PCT Application No. PCT/IB2007/003985, dated Jun. 17, 2008, 20 pages.Applicant
Hall P., et al., Merging and Splitting Eigenspace Models, IEEE Transactions on Pattern Analysis and MachineIntelligence, IEEE Service Center, Los Alamitos, CA, US, vol. 22, No. 9, Sep. 1, 2000, pp. 1042-1049, XP008081056, ISSN: 0162-8828.Applicant
Hall, P., et al., Adding and subtracting eigenspaces with eigenvalue decomposition and singular value decomposition, Image and Vision Computing, Guildford, GB, vol. 20, No. 13-14, Dec. 1, 2002, pp. 1009-1016, XP008089613, ISSN: 0262-8856.Applicant
Hall, P., et al., Adding and Subtracting eigenspaces, Proceedings of the British Machine Vision Conference, XX, XX, vol. 2, Sep. 16, 1999, pp. 453-462, XP00809611.Applicant
B. Kusumoputro, et al., Development of 3D Face Databases by Using Merging and Splitting Eigenspace Models, WSEAS Trans. on Computers, vol. 2, No. 1, 2003, pp. 203-209, retrieved from URL: http://www.wseas.us/e-library/conferences/digest2003/papers/466-272.pdf on Sep. 16, 2008.Applicant
Liu, X., et al., Eigenspace updating for non-stationary Process and its application to face recognition, Pattern Recognition, Elsevier, GB, vol. 36 No. 9, Sep. 1, 2003, pp. 1945-1959, XP004429544, ISSN: 0031-3203.Applicant
Corcoran, Peter, et al., Automated sorting of consumer image collections using face and peripheral region image classifiers, IEEE Transactions on Consumer Electronics, IEEE Service Center, New York, NY, US, vol. 51, No. 3, Aug. 1, 2005, pp. 747-754, XP00809612, ISSN: 0098-3063.Applicant
Javier Melenchon, et al., Efficiently Downdating, Composing and Splitting Singular Value Decompositions Preserving the Mean Information, Pattern Recognition and Image Analysis Lecture Notes in Computer Science, LNCS, Springer Berlin Heidelberg, BE, vol. 4478, Jan. 1, 1900, pp. 436-443, XP019060614, ISBN: 978-3-540-72848-1.Applicant
Jun Zhang, et al., Face Recognition: Eigenface, Elastic Matching, and Neutral Nets, Proceedings of the IEEE, vol. 85, No. 9, Sep. 1997, p. 1423-1435.Applicant
Peter M. Hall, David Marshall, and Ralph R. Martin, Incremental Eigenanalysis for Classification, British Machine Vision Conference, p. 286-295, XP008091807.Applicant
Peter Corcoran, and Gabriel N. Costache, Combining PCA-based Datasets without Retraining of the Basis Vector Set, IEEE PC Jul. 24, 2007.Applicant
PCT Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration, for PCT Application No. PCT/US2007/75136, dated Oct. 1, 2008, 9 pages.Applicant

Abstract

Description

PRIORITY

[0001] This application claims the benefit of priority to U.S. provisional patent application No. 60/821,165, filed Aug. 2, 2006, which is hereby incorporated by reference.

BACKGROUND OF THE INVENTION

SUMMARY OF THE INVENTION

[0010] Training data may be combined from the first and second collections.

[0011] The method may be performed without using original data samples of the first collection.

[0013] The modified representation framework may be generated in accordance with the following:

[0014]

C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{(N^{C 1} + N^{C 2})} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T}

[0017] The method may be performed without using original data samples of the first and second collections.

[0019] The modified representation framework may be generated in accordance with the following:

[0020]

\hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] ++ \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T}

[0021] One or more storage media may be provided having embodied therein program code for programming one or more processors to perform any of the methods described herein.

BRIEF DESCRIPTION OF THE DRAWINGS

[0022] FIG. 1 illustrates the application of PCA to a raw dataset.

[0023] FIG. 2 illustrates the combining of two different PCA representations of datasets in accordance with a preferred embodiment.

[0024] FIG. 3 illustrates the combining of PCA representations of datasets with supplemental raw data in accordance with a preferred embodiment.

[0025] FIG. 4 shows several plots of eigenvalue distributions for both a first and a second collection for both the classical PCA method and a method in accordance with a preferred embodiment.

[0026] FIGS. 5a-5d illustrate first eigenfaces from both a first and a second collection for both the classical method and a method in accordance with a preferred embodiment.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Theory

- [0034] (i) There are two collections of data which are already analyzed using PCA and it is desired to determine a common basis vector set for the combined collection and, ideally, transform the predetermined PCA descriptors without having to recalculate new descriptor sets for each item of data; and
- [0035] (ii) There is an existing collection of data which is analyzed using PCA and it is desired to add a significant number of new raw data items to this dataset.

PCA Mathematical Model

[0039]

({Mean}_{S} = \sum S_{i} / N)

from each sample. The PCA algorithm consists in computing the covariance matrix Cov_SSusing eq. 1:

[0040]

\begin{matrix} {Cov}_{SS} = \frac{1}{N} [S - {Mean}_{S}] \times {[S - {Mean}_{S}]}^{T} & (1) \end{matrix}

[0042]

\begin{matrix} V = [\begin{matrix} v_{1} & 0 & \dots & 0 \\ 0 & v_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & v_{m} \end{matrix}] & (3) \end{matrix}

[0046] The standard results of applying PCA to a raw dataset are illustrated in FIG. 1.

Dataset Combination Scenarios

[0048] Now we consider two different cases where the data in the collection will be changed:

- [0049] (i) either a new collection of data which was already analyzed using PCA has to be added to the original collection in order to form a super-collection, or
- [0050] (ii) a new set of raw (unanalyzed) data samples are to be added to the collection in order to update it.

[0051] Lets consider the first case of combination:

Combining Two Collections of PCA Data

[0053]

\begin{matrix} Mean = \frac{N^{C 1} * {Mean}^{C 1} + N^{C 2} * {Mean}^{C 2}}{N^{C 1} + N^{C 2}} & (8) \end{matrix}

where N^C1and N^C2represent the number of data samples in each collection. It is easy to prove [5] that the covariance of the super collection Cov_Ccan be computed as:

[0054]

\begin{matrix} {Cov}_{C} = \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 1} - Mean) (S^{C 2} - Mean)] \times {[(S^{C 1} - Mean) (S^{C 2} - Mean)]}^{T} = \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 1} - {Mean}^{C 1})] \times {[(S^{C 1} - {Mean}^{C 1})]}^{T} + \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2})] \times {[(S^{C 2} - {Mean}^{C 2})]}^{T} + \frac{1}{N^{C 1} + N^{C 2}} \frac{N^{C 1} N^{C 2}}{N^{C 1} + N^{C 2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} {Cov}_{C 1} + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} {Cov}_{C 2} + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times [({Mean}^{C 1} - {Mean}^{C 2})] & (9) \end{matrix}

[0056]

\begin{matrix} C \hat{o} v_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{N^{C 2}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 2} \times {\hat{V}}^{C 2} \times {\hat{E}}^{C 2^{T}}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{T} & (10) \end{matrix}

[0059] The reconstruction of a combined dataset from two independently trained PCA data representations is illustrated in FIG. 2.

[0064]

\begin{matrix} \hat{C} {ov}_{C} = \frac{N^{C 1}}{N^{C 1} + N^{C 2}} [{\hat{E}}^{C 1} \times {\hat{V}}^{C 1} \times {\hat{E}}^{C 1^{T}}] + \frac{1}{N^{C 1} + N^{C 2}} [(S^{C 2} - {Mean}^{C 2}) \times {(S^{C 2} - {Mean}^{C 2})}^{T}] + \frac{N^{C 1} N^{C 2}}{{(N^{C 1} + N^{C 2})}^{2}} [({Mean}^{C 1} - {Mean}^{C 2})] \times {[({Mean}^{C 1} - {Mean}^{C 2})]}^{2} & (13) \end{matrix}

[0066] This situation where additional raw data is added to a dataset with a (trained) PCA representation is illustrated in FIG. 3.

Experimental Results

[0068] Two separate tests were performed by splitting the training faces into two collections with different number of faces. The faces were randomly attached to one of the initial collections:

- [0069] 1. Test A: we split the training collection into 2 collections each with 140 faces and performed classification tasks using three cases: simple concatenation of PCA coefficients without updating, classical combination using data samples and the proposed method.
- [0070] 2. Test B: using two collections one with 240 faces and the other with the remaining 40 faces in two cases: the classical approach and the proposed method. Also for this test we used both scenarios: combining two collections of PCA data and adding new data to a trained collection.

[0076]

TABLE 1

Recognition Rates for Test A
	Combining collections

	Simple concatenation	48.32%
	Classical combination	84.28%
	Proposed method	85.23%

[0078]

TABLE 2

Recognition Rates for Test B
	Combining	Adding samples
	collections	to collection

	Simple concatenation	62.14%	Na
	Classical combination	84.28%	84.28%
	Proposed method	84.64%	83.14%