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

• US 20050157909A1
• Filed: 03/09/2005
• Published: 07/21/2005
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: Morphotrust USA Incorporated (Advent International Corporation)
• Original Assignee: Identix, Inc. (Advent International Corporation)
• Inventors: Griffin, Paul A.
• Granted Patent: US 7,792,332 B2
• Time in Patent Office: Days
• 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 sample 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; and

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

2. The method of claim 1 wherein constructing the sample space comprises:

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.

3. The method of claim 2 further comprising:

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

4. The method of claim 3 further comprising:

truncating the sample space by eliminating a subset of the sample space modes, the eliminated modes generally having the lowest eigenvalues.

18. The method of claim 1 further comprising selecting the plurality of basis sample elements at random.

19. The method of claim 1 further comprising:

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

mapping the raw matching scores of said data sample into the sample space scores.

20. The method of claim 19 further comprising:

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

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

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

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

21. The method of claim 4 further comprising:

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

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

22. The method of claim 21 further comprising:

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

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

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

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

29. The method of claim 1 wherein the objects are persons, the data samples are face templates, and the method is used to perform face recognition.

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

5. (canceled)

6. (canceled)

7. (canceled)

8. (canceled)

9. (canceled)

10. (canceled)

11. (canceled)

12. (canceled)

13. (canceled)

14. (canceled)

15. (canceled)

16. (canceled)

17. (canceled)

23. (canceled)

24. (canceled)

25. (canceled)

26. (canceled)

27. (canceled)

28. (canceled)

31. 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 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 basis element 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.

32. The system of claim 31 wherein the sample space construction module generates a covariance matrix for the basis elements from the raw matching scores, and determines the eigenvectors and eigenvalues of the covariance matrix, the eigenvectors specifying the sample space modes.

33. The system of claim 32 wherein the sample space construction module further generates a rotation matrix, based on the eigenvectors of the covariance matrix, the rotation matrix mapping raw matching scores into sample space scores.

34. The system of claim 33 further comprising a sample space truncation module for truncating the sample space by eliminating a subset of the sample space modes, the eliminated modes generally having the lowest eigenvalues.

44. The system of claim 31 wherein the plurality of basis sample elements are selected at random.

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

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

35. (canceled)

36. (canceled)

37. (canceled)

38. (canceled)

39. (canceled)

40. (canceled)

41. (canceled)

42. (canceled)

43. (canceled)

45. (canceled)

46. (canceled)