Method and system of transitive matching for object recognition, in particular for biometric searches

• US 6,920,231 B1
• Filed: 06/30/2000
• Issued: 07/19/2005
• Est. Priority Date: 06/30/2000
• Status: Expired due to Term

• Current Assignee: Morphotrust USA Incorporated (Advent International Corporation)
• Original Assignee: Indentix Incorporated
• Inventors: Griffin, Paul A
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US09/607,488
• Time in Patent Office: 1,845 Days
• Field of Search: 382/115, 382/118, 382/124, 235/380, 340 51- 592, 340 552- 553, 340 58- 586, 704/246, 704/273, 902/3, 902/4, 902/25, 351/204
• US Class Current: 382/115
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• 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/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands

Abstract

A method and system of transitivity matching suitable for object recognition, and in particular biometric recognition such as face or fingerprint recognition, is provided. The invention provides a means for pre-encoding object match information from each set of raw object sample data or scores from an underlying recognition algorithm. A sample space is constructed and the raw scores are mapped into that space. Preferably, a recognition space is also constructed and the same space scores are further mapped into the recognition space. Each space may be truncated to remove dispensable modes of that space. The distance between object data samples encoded in the sample space or the recognition space can be more rapidly determined, and the encoded data samples are also significantly compressed, compared to the raw scores.

Claims

1. A method of constructing a vector space in which a data sample relating to an object may be encoded, comprising:

providing a raw matching score between each of a plurality of basis sample elements and each of a plurality of data samples in a first sample database;

the samples in the first sample database being out-of-sample with respect to the basis sample elements;

constructing a sample space from the raw matching scores, the sample space being defined by a basis set of sample modes, by generating a covariance matrix for the basis elements from the raw matching scores; and

determining the eigenvectors and eigenvalues of the covariance matrix, the eigenvectors specifying the sample space modes;

generating a rotation matrix, based on the eigenvectors of the covariance matrix, the rotation matrix mapping raw matching scores into sample space scores; and

truncating the sample space by eliminating a subset of the sample space modes, the eliminated modes generally having the lowest eigenvalues, by determining a sample space score between each of a plurality of data samples in a second sample database and each of the sample space modes, the samples in the second sample database being out-of-sample with respect to the basis sample elements and the samples in the first sample database; and

selecting a cut-off for eliminating a subset of sample space modes based on the distribution of said sample space scores for each of the sample space modes, the distribution being indicative of how well a sample space mode is able to discriminate between samples.

2. The method of claim 1 wherein the sample space scores are normalized with respect to each sample space mode and selecting a cut-off is further based on determining when the distributions of the normalized sample space scores for each sample space mode start to vary by more than an acceptable amount.

3. A method of constructing a vector space in which a data sample relating to an object may be encoded, comprising:

providing a raw matching score between each of a plurality of basis sample elements and each of a plurality of data samples in a first sample database, the samples in the first sample database being out-of-sample with respect to the basis samples elements;

constructing a sample space from the raw matching scores, the sample space being defined by a basis set of sample space modes;

determining a first common object sample space score between each of a plurality of data samples in a first common object sample database and each of the sample space modes

determining a second common object sample space score between each of a plurality of data samples in a second common object sample database and each of the sample space modes, the first and second common object sample databases each having a set of different samples for the same objects; and

constructing a recognition space from the first common object sample space scores and the second common object sample space scores, the recognition space being defined by a basis set of recognition space modes.

4. The method of claim 3 wherein the sample space scores are normalized with respect to each sample space mode before constructing the recognition space.

5. The method of claim 4 wherein constructing the recognition space comprises:

generating a second covariance matrix for the sample space modes from the first common object sample space scores and the second common object sample space scores; and

determining the eigenvectors and eigenvalues of the second covariance matrix, the eigenvectors of the second covariance matrix specifying the recognition space modes.

6. The method of claim 5 further comprising:

generating a second rotation matrix, based on the eigenvectors of the second covariance matrix, the second rotation matrix mapping sample space scores into recognition space scores.

7. The method of claim 6 further comprising:

truncating the recognition space by eliminating a subset of the recognitions pace modes, the eliminated recognition space modes generally having the highest eigenvalues of the second covariance matrix.

8. The method of claim 7 wherein truncating the recognition space comprises:

determining a recognition space score between each of a plurality of data samples in a third sample database and each of the recognition space modes, the samples in the third sample database being of objects not sampled in the basis samples, the samples in the first sample database, the samples in the first common object database, or the sample in the second common object database; and

selecting a cut-off for eliminating a subset of recognition space modes based on the distribution of said recognition space scores for each of the recognition space modes, the distribution being indicative of whether a recognition mode is generally unsuitable for recognizing different samples of the same object.

9. The method of claim 8 wherein selecting a cut-off is further based on determining when the distributions of the recognition space scores for each sample space mode start to vary by more than an acceptable amount.

10. The method of claim 3 further comprising:

before constructing the recognition space, truncating the sample space by eliminating a subset of the sample space modes; and

truncating the recognition space by eliminating a subset of the recognition space modes.

11. The method of claim 3 wherein the recognition space is constructed using linear discriminant analysis.

12. The method of claim 3 wherein the recognition space is constructed using non-linear discriminant analysis.

13. The method of claim 3 further comprising selecting the plurality of basis sample elements at random.

14. The method of claim 3 further comprising:

providing a raw matching score between said data sample and each of the plurality of basis sample elements;

mapping the raw matching scores of said data sample into sample space scores; and

mapping the sample space scores of said data sample into recognition space scores.

15. The method of claim 14 further comprising:

encoding known data samples into recognition space scores in the recognition space, and storing the recognition space scores in a reference database;

encoding the data sample as a probe data sample into recognition space sores in the recognition space;

measuring the distance between the recognition space scores for the probe data sample and each known data sample in the recognition space; and

determining which encoded known data sample is nearest to the encoded probe data sample in the recognition space.

16. The method of claim 10 further comprising:

providing a raw matching score between said data sample and each of the plurality of basis sample elements;

mapping the raw matching scores of said data sample into truncated sample space scores; and

mapping the sample space scores of said data sample into truncated recognition space scores.

17. The method of claim 16 further comprising:

encoding known data samples into truncated recognition space scores in the truncated recognition space, and storing the recognition space scores in a reference database;

encoding the data sample as a probe data sample into truncated recognition space scores in the truncated recognition space;

measuring the distance between the truncated recognition space sores for the probe data sample and each known data sample in the truncated recognition space; and

determining which encoded known data sample is nearest to the encoded probe data sample in the truncated recognition space.

18. The method of claim 3 wherein the objects are persons, the data samples represent faces of the persons, and the method is used to perform face recognition.

19. The method of claim 3 wherein the objects are persons, the data samples represent fingerprints of the persons, and the method is used to perform fingerprint recognition.

20. For use in object recognition, a space construction and encoding system comprising:

a sample space construction module for receiving a data sample relating to an object to be encoded, a plurality of basis sample elements, and a plurality of data samples in a first sample database, the samples in the first sample database being out-of-sample with respect to the basis samples;

the sample space construction module providing a raw matching score between each of the plurality of basis sample elements and each of the plurality of data samples in the first sample database, and constructing a sample space from the raw matching scores, the sample space being defined by a basis set of sample space modes;

a recognition space construction module for receiving a plurality of data samples in a first common object sample database and a plurality of data samples in a second common object sample database, the first and second common object samples databases each having a set of different samples for the same objects;

wherein the recognition space construction module determines a first common object sample space score between each of the plurality of data samples in the first common object sample database and each of the sample space modes and further determines a second common object sample space score between each of the plurality of data samples in the second common object sample database and each of the sample space modes, the recognition space construction module constructing a recognition space from the first common object sample space scores and the second common object sample space scores, the recognition space begin defined by a basis set of recognition space modes.

21. The system of claim 20 wherein the sample space scores are normalized with respect to each sample space mode before construction of the recognition space.

22. The system of claim 21 wherein the recognition space construction module generates a second covariance matrix for the sample space modes from the first common object sample space scores and the second common object sample space scores, the recognition space construction module further determining the eigenvectors and eigenvalues of the second covariance matrix, the eigenvectors of the second covariance matrix specifying the recognition space modes.

23. The system of claim 22 wherein the recognition space construction module further generates a second rotation matrix, based on the eigenvectors of the second covariance matrix, the second rotation matrix mapping sample space scores into recognition space scores.

24. The system of claim 23 further comprising a recognition space truncation module for truncating the recognition space by eliminating a subset of the recognition space modes, the eliminated recognition space modes generally having the highest eigenvalues of the second covariance matrix.

25. The system of claim 20 further comprising:

a sample space truncation module for truncating the sample space by eliminating a subset of the sample space modes; and

a recognition space truncation module truncating the recognition space by eliminating a subset of the recognition space modes.

26. The system of claim 20 wherein the recognition space construction module uses linear discriminant analysis in constructing the recognition space.

27. The system of claim 20 wherein the recognition space construction module uses non-linear discriminant analysis in constructing the recognition space.

28. The system of claim 20 wherein the plurality of basis sample elements are selected at random.

29. The system of claim 20 wherein the objects are persons, the data samples represent faces of the persons, and the system is used to perform face recognition.

30. The system of claim 20 wherein the objects are persons, the data samples represent fingerprints of the persons, and the system is used to perform fingerprint recognition.