Fingerprint verification

• US 20050058325A1
• Filed: 05/30/2001
• Published: 03/17/2005
• Est. Priority Date: 05/30/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Garg, Gaurav, Udupa, Raghavendra U., Sharma, Pramod Kumar
• Granted Patent: US 7,046,829 B2
• Time in Patent Office: Days
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

Fingerprint verification matching a claimant fingerprint with one of a number of recorded enrollee fingerprints uses various adaptations of model alignment techniques involving affine transformation to provide an algorithm providing relatively fast and accurate verification suitable for realtime applications. These techniques involve sampling minutiae into subsets based on geometrical proximity to a particular index minutiae for each subset, eliminating minutiae which are near the fingerprint boundary, ordering the minutiae of each subset in a predetermined manner, classifying each subset in bins which discriminate on the properties of the subsets, checking transformations proposed as matches between fingerprints for consistency with each other, and checking the topological as well as the geometrical correspondence of potentially matching fingerprints. In a preferred form, a score indicative of the correlation between fingerprints is used to ultimately decide whether the fingerprints match.

Claims

1. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

analysing the geometrical correspondence between minutiae of the claimant fingerprint and minutiae of the enrollee fingerprint via affine transformation; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis.

2. The method as claimed in claim 1, further comprising:

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset.

3. The method as claimed in claim 2, wherein minutiae are selected for inclusion in said identified subsets if the geometrical separation between the minutiae and the index minutiae falls within a predetermined range between a finite minimum and a finite maximum.

4. The method as claimed in claim 1, wherein minutiae are eliminated from and/or not selected for inclusion in said identified subsets if the minutiae is determined to be positioned on or near the boundary of the claimant or enrollee fingerprint.

5. The method as claimed in claim 4, wherein a minutiae is determined to be positioned on or near the boundary of a fingerprint if it is less than a predetermined geometrical separation from any one of the sides of a rectangle defined by the co-ordinates of the most outlying minutiae of the fingerprint.

6. The method as claimed in claim 2, wherein the minutiae which are members of said identified subsets are ranked according to a predetermined ordering criterion indicative of a possible correspondence between the minutiae of different identified subsets of the same of different fingerprints.

7. The method as claimed in claim 6, wherein said predetermined ordering criterion is increasing geometrical distance to respective minutiae from a particular index minutiae which is a member of said identified subset.

8. The method as claimed in claim 6, wherein said predetermined ordering criterion is increasing difference in rotational ridge orientation between respective minutiae and a particular index minutiae which is a member of said identified subset.

9. The method as claimed in claim 6, wherein said predetermined ordering criterion is increasing ridge count between respective minutiae and a particular index minutiae which is a member of said identified subset.

10. The method as claimed in claim 6, wherein said predetermined ordering criterion is an increasing distance between respective minutiae and an axis defined by the ridge angle of a particular index minutiae which is a member of said identified subset.

11. The method as claimed in claim 2, wherein said identified subsets are classified in one of a plurality of bins which are defined on the basis of a predetermined metric associated with or derived from properties relating to the minutiae which are members of said identified subsets.

12. The method as claimed in claim 11, wherein said predetermined metric is the largest geometrical separation between any pair of minutiae of an identified subset.

13. The method as claimed in claim 11, wherein said predetermined metric is based on the distribution of ridge counts between pairs of minutiae of an identified subset.

14. The method as claimed in claim 11, wherein said predetermined metric is based on the distribution of geometrical distances of the minutiae from the index minutiae.

15. The method as claimed in claim 11, wherein said predetermined metric is based on the distribution of ridge-orientation rotational distances of the minutiae from the index minutiae.

16. The method as claimed in claim 11, wherein said predetermined metric is based on the distribution of geometrical distances of the minutiae from an axis defined by the ridge angle of the index minutiae.

17. The method as claimed in claim 11, wherein said analysis is performed for identified claimant subsets and identified enrollee subsets which are classified in the same bin.

18. The method as claimed in claim 2, wherein said analysis further includes determining one or more proposed transformations that map one of the identified claimant subsets to one of the identified enrollee subsets, for respective identified subsets that meet a predetermined criterion.

19. The method as claimed in claim 18, wherein said predetermined criterion is geometrical separation, between the minutiae and the index minutiae, within a predetermined range between a finite minimum and a finite maximum.

20. The method as claimed in claim 18, wherein said predetermined criterion is (i) a difference in the distance between the minutiae and the index minutiae below a predetermined distance threshold.

21. The method as claimed in claim 18, wherein said predetermined criterion is (ii) a difference in ridge counts below a predetermined number threshold.

22. The method as claimed in claim 18, wherein said predetermined criterion is, (iii) for either or both of the corresponding minutiae and the index minutiae a difference in ridge angle orientation below a predetermined angular threshold, after transformation.

23. The method as claimed in claim 1, wherein said analysis involves determining a plurality of proposed transformations proposed as matches between the claimant fingerprint and the enrollee fingerprint, in which the proposed transformations are each checked for consistency with each other.

24. The method as claimed in claim 23, wherein the proposed transformations comprise those transformations that map one of the identified claimant subsets to one of the identified enrollee subsets.

25. The method as claimed in claim 23, wherein the consistency checking involves determining differences in parameters of the respective transformations.

26. The method as claimed in claim 23, wherein two transformations are considered to be consistent with each other if the differences between transformation parameters of the two transformations are all below respective predetermined thresholds.

27. The method as claimed in claim 26, wherein the transformation parameters (x, y, β

) represent two parameters of translation (x, y) and a parameter of rotation (β

).

28. The method as claimed in claim 24, wherein the proposed transformations which are checked for consistency are limited to a predetermined number of transformations which achieve the greatest correspondence between their respective identified claimant and enrollee subsets.

29. The method as claimed in claim 28, wherein the correspondence between respective identified subsets is assessed in terms of the number of minutiae from the respective identified subsets that are deemed to match within a predetermined tolerance.

30. The method as claimed in claim 28, wherein a mutually consistent subset of the proposed transformations is identified as a result of the consistency checking.

31. The method as claimed in claim 1, wherein said determination involves checking whether there is topological correspondence between selected identified claimant and enrollee subsets of minutiae.

32. The method as claimed in claim 31, wherein topological correspondence is determined by (i) providing a ridge count metric calculated by incrementing a ridge count for each instance of matching pairs of minutiae in the respective identified claimant and enrollee subsets in which the difference in ridge counts is less than a predetermined threshold;

and (ii) providing a ridge angle metric calculated by incrementing a ridge angle count for each instance of matching minutiae in the respective identified claimant and enrollee subsets in which the difference in ridge angle, taking into account the rotational component of the proposed transformation, is below a predetermined threshold.

33. The method as claimed in claim 2, wherein said determination involves calculating a score representative of the correspondence between a claimant fingerprint and the enrollee fingerprint for use in determining that the claimant fingerprint and the enrollee fingerprint match, if the scores exceed a predetermined minimum value.

34. The method as claimed in claim 33, wherein the score is determined based on one or more of the following factors:

(i) the number of corresponding pairs of minutiae from respective identified subsets that have a difference in ridge counts below a predetermined number threshold;

(ii) the number of corresponding minutiae from respective identified subsets that have a difference in ridge angle orientation below a predetermined angular threshold, after affine transformation;

(iii) the proportion of minutiae which have corresponding minutiae in the other fingerprint; and

(iv) proportion of mutually consistent transformations.

35. The method as claimed in claim 34, wherein the score is calculated as a weighted average of values of any two or more of the listed factors.

36. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset, and members of the identified subsets are selected on the basis of whether the geometrical separation between the minutiae and the index minutiae falls within a predetermined range between a finite minimum and a finite maximum;

classifying the identified subsets in one of a plurality of bins which are defined on the basis of a predetermined metric associated with or derived from properties relating to the minutiae which are members of said identified subsets;

analysing the geometrical correspondence between minutiae of the identified subsets of the claimant and enrollee fingerprints via affine transformation; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis.

37. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset;

analysing the geometrical correspondence between minutiae of the identified subsets of the claimant and enrollee fingerprints via affine transformation, in which (i) a plurality of transformations are proposed that map one of the identified claimant subsets to one of the identified enrollee subsets, for respective identified subsets that meet a predetermined criterion, and (ii) the proposed transformations are checked for consistency with each other; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis.

38. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset;

analysing the geometrical correspondence between minutiae of the identified subsets of the claimant and enrollee fingerprints via affine transformation; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis, in which (i) it is checked whether there is topological correspondence between selected identified claimant and enrollee subsets of minutiae, and (ii) a score representative of the correspondence between a claimant fingerprint and the enrollee fingerprint is calculated to determine that the claimant fingerprint and the enrollee fingerprint match, if the scores exceed a predetermined minimum value.

39. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset, and members of the identified subsets are selected on the basis of whether the geometrical separation between the minutiae and the index minutiae falls within a predetermined range between a finite minimum and a finite maximum;

classifying the identified subsets in one of a plurality of bins which are defined on the basis of a predetermined metric associated with or derived from properties relating to the minutiae which are members of said identified subsets;

analysing the geometrical correspondence between minutiae of the identified subsets of the claimant and enrollee fingerprints via affine transformation, in which (i) a plurality of transformations are proposed that map one of the identified claimant subsets to one of the identified enrollee subsets, for respective identified subsets that meet a predetermined criterion, and (ii) the proposed transformations are checked for consistency with each other; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis, in which (i) it is checked whether there is topological correspondence between selected identified claimant and enrollee subsets of minutiae, and (ii) a score representative of the correspondence between a claimant fingerprint and the enrollee fingerprint is calculated to determine that the claimant fingerprint and the enrollee fingerprint match, if the scores exceed a predetermined minimum value.

40. A method of fingerprint verification suitable for determining whether a claimant is one of a number of enrollees, the method comprising:

analysing a claimant fingerprint and an enrollee fingerprint to determine whether the fingerprints match, in which said analysis involves determining the geometrical correspondence between minutiae of the claimant fingerprint and minutiae of the enrollee fingerprint via affine transformation;

wherein said analysis is performed using identified claimant subsets of minutiae from said claimant fingerprint and/or identified enrollee subsets of minutiae from said enrollee fingerprint, each of the identified subsets having an associated index minutiae which is a member of that identified subset.

41. An apparatus suitable for fingerprint verification in which it is determined whether a claimant is one of a number of enrollees, said computer program product comprising:

means for sampling a claimant fingerprint;

means for accessing a database of enrollee fingerprints;

means for identifying minutiae of an enrollee fingerprint and minutiae of a claimant fingerprint, from the sampled claiment fingersprint and accessed anrollee fingersprint respectively;

means for analysing the geometrical correspondence between minutiae of the identified subsets of the claimant and enrollee fingerprints via affine transformation;

means for determining determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis.

42. The apparatus as claimed in claim 41, further comprising:

means for selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset.

43. A computer program product having a computer readable medium having recorded therein a computer program suitable for fingerprint verification in which it is determined whether a claimant is one of a number of enrollees, said computer program comprising code means for performing the following steps:

identifying minutiae of an enrollee fingerprint, and minutiae of a claimant fingerprint;

analysing the geometrical correspondence between minutiae of the claimant fingerprint and minutiae of the enrollee fingerprint via affine transformation; and

determining whether the claimant fingerprint and the enrollee fingerprint match on the basis of said analysis.

44. The computer program product as claimed in claim 43, further comprising code means for performing the following steps:

selecting identified subsets of the enrollee minutiae and identified subsets of the claimant minutiae, in which each of the identified subsets has an associated index minutiae which is a member of that identified subset.

45. The computer program product as claimed in claim 44, wherein minutiae are selected for inclusion in said identified subsets if the geometrical separation between the minutiae and the index minutiae falls within a predetermined range between a finite minimum and a finite maximum.

46. The computer program product as claimed in claim 43, wherein minutiae are eliminated from and/or not selected for inclusion in said identified subsets if the minutiae is determined to be positioned on or near the boundary of the claimant or enrollee fingerprint.

47. The computer program product as claimed in claim 44, wherein the minutiae which are members of said identified subsets are ranked according to a predetermined ordering criterion indicative of a possible correspondence between the minutiae of different identified subsets of the same of different fingerprints.

48. The computer program product as claimed in claim 44, wherein said identified subsets are classified in one of a plurality of bins which are defined on the basis of a predetermined metric associated with or derived from properties relating to the minutiae which are members of said identified subsets.

49. The computer program product as claimed in claim 44, wherein said analysis further includes determining one or more proposed transformations that map one of the identified claimant subsets to one of the identified enrollee subsets, for respective identified subsets that meet a predetermined criterion.

50. The computer program product as claimed in claim 43, wherein said analysis involves determining a plurality of proposed transformations proposed as matches between the claimant fingerprint and the enrollee fingerprint, in which the proposed transformations are each checked for consistency with each other.

51. The computer program product as claimed in claim 43, wherein said determination involves checking whether there is topological correspondence between selected identified claimant and enrollee subsets of minutiae.

52. The computer program product as claimed in claim 44, wherein said determination involves calculating a score representative of the correspondence between a claimant fingerprint and the enrollee fingerprint for use in determining that the claimant fingerprint and the enrollee fingerprint match, if the scores exceed a predetermined minimum value.