Indexing face templates using linear models

• US 8,331,632 B1
• Filed: 02/13/2009
• Issued: 12/11/2012
• Est. Priority Date: 08/06/2007
• Status: Active Grant

• Current Assignee: National Institute of Standards and Technology (Government of the United States of America), University of South Florida (State University System of Florida)
• Original Assignee: University of South Florida (State University System of Florida), The United States of America As Represented By The Secretary of Commerce
• Inventors: Mohanty, Pranab, Sarkar, Sudeep, Kasturi, Rangachar, Phillips, P. Jonathon
• Primary Examiner(s): Newman, Michael A
• Application Number:
  US12/371,099
• Time in Patent Office: 1,397 Days
• Field of Search: 382/118, 382/115, 382/117, 382/155, 382/159, 382/160, 726/25
• US Class Current: 382/118
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/172 Classification, e.g. identification
• CPC Class Codes: G06V 40/50 Maintenance of biometric data or enrolment thereof

Abstract

A novel, linear modeling method to model a face recognition algorithm based on the match scores produced by the algorithm. Starting with a distance matrix representing the pair-wise match scores between face images, an iterative stress minimization algorithm is used to obtain an embedding of the distance matrix in a low-dimensional space. A linear transformation used to project new face images into the model space is divided into two sub-transformations: a rigid transformation of face images obtained through principal component analysis of face images and a non-rigid transformation responsible for preserving pair-wise distance relationships between face images. Also provided is a linear indexing method using the linear modeling method to perform the binning or algorithm-specific indexing task with little overhead.

Claims

1. A method of modeling an unknown face recognition algorithm, the method comprising:

providing an unknown face recognition algorithm;

providing a training set (X) comprising a plurality of face images;

providing a score matrix (D) containing the scores between pairs of the plurality of face images of the training set produced by the unknown face recognition algorithm, wherein a score is the distance between a pair of the face images;

converting the score matrix (D) to an equivalent Euclidean matrix (DE); and

using stress minimization with iterative majorization to determine a set of coordinates for the training set from the equivalent Euclidean matrix (DE).

2. The method of claim 1, wherein the iterative majorization is initialized by classical multidimensional scaling.

3. A method of modeling an unknown face recognition algorithm, the method comprising:

providing an unknown face recognition algorithm;

providing a training set (X) comprising a plurality of face images;

providing a score matrix (D) containing the scores between pairs of the plurality of face images of the training set produced by the unknown face recognition algorithm, wherein a score is the distance between a pair of the face images;

determining if the score matrix (D) is Euclidean;

computing a plurality of optimal configuration points (Y) from the score matrix (D) using classical multidimensional scaling responsive to the score matrix (D) being Euclidean;

converting the score matrix (D) to an equivalent Euclidean matrix (DE) responsive to the score matrix (D) being non-Euclidean; and

computing a plurality of optimal configuration points (Y) from the distances contained in the equivalent Euclidean matrix (DE) using an initial configuration point (Y(0)) and stress minimization with iterative majorization responsive to the creation of the equivalent Euclidean matrix (DE), wherein the initial configuration point (Y(0)) is computed from the equivalent Euclidean matrix (DE) using classical multidimensional scaling.

4. A method of indexing face templates in a recognition system, the recognition system having a recognition algorithm and a plurality of gallery images, the method comprising:

determining a linear model of the recognition system, wherein determining the linear model comprises;

providing an unknown face recognition algorithm;

providing a training set (X) comprising a plurality of face images;

providing a score matrix (D) containing the scores between pairs of the plurality of face images of the training set produced by the unknown face recognition algorithm, wherein a score is the distance between a pair of the face images;

converting the score matrix (D) to an equivalent Euclidean matrix (DE); and

using stress minimization with iterative majorization to determine a set of coordinates for the training set from the equivalent Euclidean matrix (DE);

providing a probe face image;

projecting the probe face image into the linear model space; and

determining the nearest gallery images.

5. The method of claim 4, further comprising:

comparing the nearest gallery images with the probe face image using the recognition algorithm; and

outputting the nearest gallery image to the probe face image.