Matching prints with feature collections

• US 8,077,933 B1
• Filed: 09/01/2007
• Issued: 12/13/2011
• Est. Priority Date: 09/06/2006
• Status: Active Grant

• Current Assignee: Fiske Software LLC
• Original Assignee: Fiske Software LLC
• Inventors: Fiske, Michael Stephen
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US11/897,836
• Time in Patent Office: 1,564 Days
• Field of Search: 382/115, 382/124, 382/125, 382/126, 382/127, 382/209, 340/5.82, 340/5.83, 902/3
• US Class Current: 382/124
• CPC Class Codes: G06V 10/993 Evaluation of the quality of the acquired pattern
• CPC Class Codes: G06V 40/50 Maintenance of biometric data or enrolment thereof

Abstract

In one embodiment, biometric authentication, using fingerprints, handprints, retinal scans and voice recognition, may be used as a means of granting access to an individual, for example, to use a device or gain entry to a building, car, computer, airport, website, a bank account, execute a financial transaction, access a military installation, read or obtain confidential information, execute a legal agreement, authenticate a decision, or another entity. In another embodiment, biometric authentication can be used as an alternative to the use of a key or combination or as an additional form of authentication. Access may be in any of a number of forms. In one embodiment a collection of pairs of features from one biometric print is compared to another collection of pairs from another biometric print to determine whether biometric authentication is successful.

Claims

1. A method of measuring how well fingerprints match comprising:

comparing, by a processor of a machine, a pair of features from a first fingerprint with a pair of features from a second fingerprint, deriving a transformation that transforms the first pair of features of the first fingerprint to more closely match the first pair of features of the second fingerprint, and storing the transformation in a memory of the machine;

repeating, by the machine, the comparing and the deriving of the transformation for each of a set of pairs of features on the first fingerprint and a set of pairs of features on the second fingerprint, therein forming a set of transformations;

determining, by the machine, a degree to which each of the transformations of the sets of transformations match one another, and finding a subset of the set of transformations that is the largest group of transformations that match one another within a predetermined tolerance;

computing a matching score for each transformation in the subset;

combining, by the machine, the matching scores of each of the transformations of the subset to form a matching score representing a degree to which the first fingerprint matches the second fingerprint; and

if the matching score for the fingerprints is above a threshold, indicating, by the machine, that the first and second fingerprint match.

2. The method of claim 1 wherein the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are compared based on the distance between the features of the one or more pairs of features in the first fingerprints and the distance between the features of the one or more pairs of features in the second fingerprint.

3. The method of claim 1 wherein the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are compared based on the number of valleys between the features of the one or more pairs of features in the first fingerprints and the number of valleys between the features of the one or more pairs of features in the second fingerprint.

4. The method of claim 1 wherein a pair of features from the first fingerprint is compared with a pair of features from the second fingerprint, if a transformation rotates a first feature of the pair of features on the first fingerprint by an angle to orient a first feature of the pair of features on the second fingerprint that matches an angle of a transformation that orients a second feature of the pair of features on the first fingerprint to match a second feature of the pair of features on the second finger print.

5. The method of claim 1, further comprising determining whether the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are of a same predetermined type;

if it is determined that the first pair of features from the first fingerprint and the first pair of features from the second fingerprint are of the same predetermined feature type, performing the comparing.

6. The method of claim 5 wherein the predetermined feature type is an ending of a ridge.

7. The method of claim 5 wherein the predetermined feature type is a bifurcation.

8. The method of claim 5 wherein the predetermined feature type is a cross-correlation.

9. The method of claim 5 wherein the predetermined feature type is complex, including at least two or more features.

10. The method of claim 5 wherein the predetermined type is a loop, the loop includes at least a valley that is a curve at least as much as a horseshoe shape.

11. The method of claim 1 wherein only a predetermined number of transformations matching scores that are higher than matching scores of transformations not in the set are kept in the set.

12. The method of claim 1 wherein the transformations are affine.

13. The method of claim 1 wherein the transformations are applied to features of the first fingerprint to search for nearby features from the second fingerprint and wherein at least a contribution to the matching score of a particular transformation depends on how many features were found on the second fingerprint by the search.

14. The method of claim 1 wherein a successful match is required for access to an entity.

15. The method of claim 14, wherein the entity is a physical place.

16. The method of claim 14, wherein the entity is confidential information.

17. The method of claim 1 wherein a successful match is required to execute an agreement or transaction.

18. The method of claim 1 wherein a successful match provides a personalization.

19. A machine determining how well fingerprints match-comprising:

a processor;

a memory storing information representing fingerprints, and storing one or more machine readable instructions, which when implemented cause the processor to implement the method including at least;

comparing, by the processor, a first pair of features from one a first fingerprint with a first pair of features from a second fingerprint, deriving a transformation that transforms the first pair of features of the first fingerprint to more closely match the first pair of features of the second fingerprint, and storing the transformation in the memory of the machine;

repeating, by the machine, the comparing and the deriving of the transformation for each of a randomly selected subset of a larger set of pairs of features on the first fingerprint and a set of pairs of features on the second fingerprint, therein forming a set of transformations;

determining, by the machine, a degree to which each of the transformations of the set of transformations match one another, and finding a subset of the sets of transformations that is the largest group of transformations that match one another within a predetermined tolerance;

computing a matching score for each transformation in file subset;

combining, by the machine, the matching scores of each of the transformations of the subset to form a matching score representing a degree to which the first fingerprint matches the second fingerprint; and

if the matching score for the fingerprints is above a threshold, indicating, by the machine, that the first and second fingerprint match.

20. The machine of claim 19 wherein the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are compared based on the distance between the features of the one or more pairs of features in the first fingerprints and the distance between the features of the one or more pairs of features in the second fingerprint.

21. The machine of claim 19 wherein the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are compared based on the number of valleys between the features of the one or more pairs of features in the first fingerprints and the number of valleys between the features of the one or more pairs of features in the second fingerprint.

22. The machine of claim 19 wherein a pair of features from the first fingerprint is compared with a pair of features from the second fingerprint, if a transformation that rotates a first feature of the pair of features on the first fingerprint by an angle to orient a first feature of the pair of features on the second fingerprint that matches an angle of a transformation that orients a second feature of the pair of features on the first fingerprint to match a second feature of the pair of features on the second finger print.

23. The machine of claim 19, further comprising

determining whether the one or more pairs of features from the first fingerprint and the one or more pairs of features from the second fingerprint are of a same predetermined type;

if it is determined that the first pair of features from the first fingerprint and the first pair of features from the second fingerprint are of the same predetermined feature type, performing the comparing.

24. The machine of claim 23 wherein the predetermined feature type is an ending of a ridge.

25. The machine of claim 23 wherein the predetermined feature type is a bifurcation.

26. The machine of claim 23 wherein the predetermined feature type is a cross-correlation.

27. The machine of claim 23 wherein the predetermined feature type is complex, including at least two or more features.

28. The machine of claim 23 wherein the predetermined feature type is a loop, the loop includes at least a valley that is a curve at least as much as a horseshoe shape.

29. The machine of claim 19 wherein only a predetermined number of transformations matching scores that are higher than matching scores of transformations not in the set are kept in the set.

30. The machine of claim 29 wherein the transformation are affine.

31. The machine of claim 29 wherein the transformations are applied to

features of first said fingerprint to search for nearby features from other said fingerprint.

32. The machine of claim 19 wherein a successful match is required for access to an entity.

33. The machine of claim 32, wherein the entity is a physical place.

34. The machine of claim 32, wherein the entity is confidential information.

35. The machine of claim 19 wherein a successful match is required to execute an agreement or transaction.

36. The machine of claim 19 wherein a successful match provides a personalization.

37. A method of claim 19 wherein the cross foliation is represented by at least coordinates indicating a location of a feature,

an angle of orientation of a string of pixels associated with the location of the feature, and

a string of values in which each value represents

whether the pixel is located at a ridge and

whether the pixel is located at a valley.

38. A method of measuring how well fingerprints match comprising:

for each of a set of pairs of features on a first fingerprint determining a cross foliation of at least one feature of one pair of features on the first fingerprint and a cross foliation of at least one feature of a second pair of features;

determining whether the cross foliation of the at least one feature of the one pair of features on one fingerprint and the cross foliation of the at least one feature of the second pair of feature match within a tolerance;

comparing, by a machine having a processor and memory unit, one or more pairs of features from the first fingerprint with one or more pairs of features from the second fingerprint wherein the pairs including a pair of features from the first fingerprint and a pair or features from the second fingerprint, that have been compared, if the one or more pairs of features from the first fingerprint have a cross foliation that matches a cross foliation of a feature of a pair of features on the second fingerprint, the one or more pairs of fingerprints, and compared based on one or more of the following;

the distance between the pairs of features on the first finger print;

the number of valleys between the pairs of features on the first finger print;

angles of features in the first fingerprint and the second fingerprint;

predetermined feature types of features in the pairs of features of the first fingerprint;

the method also includes at least deriving a transformation that matches one pair of features from the first fingerprint with another pair of features from the second fingerprint;

repeating, by the machine, the comparing and the deriving of the transformation for each of a set of pairs of features on the first fingerprint and a set of pairs of features on the second fingerprint, therein forming a set of transformations;

determining, by the machine, a degree to which each of the transformations of the set of transformations match one another, and finding a subset of the set of transformations that is the largest group of transformations that match one another within a predetermined tolerance;

computing a matching score for each transformation in the subset;

combining, by the machine, the matching scores of each of the transformations of the subset to form a matching score representing a degree to which the first fingerprint matches the second fingerprint; and

if the matching score for the fingerprints is above a threshold, indicating, by the machine, that the first and second fingerprint match.

39. The method of claim 38 wherein the transformation derived is applied to features of the first fingerprint to search for nearby features from the second fingerprint.

40. The method of claim 39 wherein the transformations are applied to features of the first fingerprint to search for nearby features from the second fingerprint and wherein at least a contribution to the matching score of a particular transformation depends on how many features were found on the second fingerprint by the search.

41. The method of claim 38 wherein the set of pairs of features includes pairs of features in which each feature of a particular set of the pairs is within a predetermined range of distances of each other.

42. The method of claim 38, wherein the set of pairs of features includes pairs of features in which each feature of a particular set of the pair is within a predetermined range of valley counts.

43. The method of claim 38 wherein the pairs of features of the set of pairs of features are randomly chosen.