Method for fingerprint indexing and searching

• US 5,841,888 A
• Filed: 01/23/1996
• Issued: 11/24/1998
• Est. Priority Date: 01/23/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Setlak, Dale R., Boss, Mark E., Schmitt, John C.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US08/589,064
• Time in Patent Office: 1,036 Days
• Field of Search: 382/116, 382/124, 382/125, 382/126, 382/127, 382/115, 356/71, 396/15, 340/825.34, 395/606, 395/603, 283/68, 283/69, 283/78, 427/1
• US Class Current: 382/124
• CPC Class Codes: A61B 5/1172 using fingerprinting
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction
• CPC Class Codes: G06V 40/1365 Matching; Classification
• CPC Class Codes: G06V 40/168 Feature extraction; Face representation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method for indexing and searching a plurality of reference fingerprints to determine if a sample fingerprint matches one of the reference fingerprints includes the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon characteristics of the fingerprints and with the index values being generally evenly distributed and continuous over a relatively large population of individuals; selecting a first subset of the reference fingerprints having index values in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints. The step of determining index values for the reference fingerprints and the sample fingerprint preferably comprises determining same based upon ridge flow curvature of the fingerprints. The step of selecting the first subset of reference fingerprints preferably comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset. Apparatus aspects of the invention are also disclosed.

Claims

1. A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of:

determining respective index values for the reference fingerprints and the sample fingerprint based upon ridge flow characteristics of the fingerprints wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals;

sorting the reference index values to define a generally continuous and generally monotonically varying function of the ridge flow fingerprint characteristics of the selected relatively large population of individuals;

selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function within a first range relative to the index value of the sample fingerprint; and

comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints.

2. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining same based upon ridge flow curvature of the fingerprints.

3. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of:

determining a center for each fingerprint;

selecting a predetermined portion of each fingerprint relative to a center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.

4. A method according to claim 3 wherein the step of selecting a predetermined portion of each fingerprint comprises selecting a generally annularly shaped portion of each fingerprint.

5. A method according to claim 1 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.

6. A method according to claim 1 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.

7. A method according to claim 1 further comprising the step of selecting a second subset of reference fingerprints having index values along the generally continuous and generally monotonically varying function within a second range larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.

8. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.

9. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.

10. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.

11. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from fingerprint information developed for the comparing step.

12. A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be at least one-dimensional.

13. A method according to claim 1 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of ridge flow characteristics.

14. A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith a curliness index value based upon an aggregate of a rate of change of ridge direction vectors, the method comprising the steps of:

determining a curliness index value for the sample fingerprint based upon an aggregate of a rate of change of ridge direction vectors of the sample fingerprint wherein the index values are both generally evenly distributed over the relatively large population of individuals;

sorting the reference index values to define a generally continuous and generally monotonically varying function of the aggregate of a rate of change of ridge direction vectors of fingerprints of the selected relatively large population of individuals;

selecting a first subset of the reference fingerprints having curliness index values along the generally even distribution in a first range relative to the curliness index value of the sample fingerprint; and

comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.

15. A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises the steps of:

determining a center of the sample fingerprint;

selecting a predetermined portion of the sample fingerprint relative to the center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.

16. A method according to claim 15 wherein the step of selecting a predetermined portion of the sample fingerprint comprises selecting a generally annularly shaped portion thereof.

17. A method according to claim 14 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.

18. A method according to claim 14 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.

19. A method according to claim 14 further comprising the step of selecting a second subset of reference fingerprints along the generally even distribution having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.

20. A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises determining such index value to be at least one-dimensional.

21. A method according to claim 14 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of an aggregate of a rate of change of ridge direction vectors.

22. A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of:

determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals;

sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals;

selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and

comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.

23. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.

24. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.

25. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.

26. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.

27. A method according to claim 22 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.

28. A method according to claim 22 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.

29. A method according to claim 22 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.

30. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.

31. A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of:

determining a center of each fingerprint;

selecting a predetermined portion of the fingerprint relative to the center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.

40. A method according to claim 31 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.

32. A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals, the method comprising the steps of:

determining respective index values for the reference fingerprints and a sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals;

sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; and

selecting for searching a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint.

33. A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.

34. A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.

35. A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.

36. A method according to claim 32 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.

37. A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.

38. A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of:

determining a center of each fingerprint;

selecting a predetermined portion of the fingerprint relative to the center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.

39. A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith an index value based upon at least one predetermined fingerprint characteristic wherein the index values for the reference and sample fingerprints are both generally evenly distributed and continuous over the relatively large population of individuals and wherein the reference index values are sorted to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals, the method comprising the steps of:

determining the index value for the sample fingerprint based upon the at least one predetermined fingerprint characteristic;

selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and

comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.

41. A method according to claim 39 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.

42. A method according to claim 39 wherein the step of determining an index value for the sample fingerprint comprises determining such an index value based upon ridge flow characteristics of the sample fingerprint.

43. A method according to claim 42 wherein the step of determining an index value for the sample fingerprint comprises the steps of:

determining a center of the sample fingerprint;

selecting a predetermined portion of the sample fingerprint relative to the center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.

44. A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of:

determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals;

sorting the reference index value to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals;

selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint and based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints; and

comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.

45. A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.

46. A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.

47. A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.

48. A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.

49. A method according to claim 44 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.

50. A method according to claim 44 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.

51. A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.

52. A method according to claim 51 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of:

determining a center of each fingerprint;

selecting a predetermined portion of the fingerprint relative to the center; and

calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.