Fingerprint matching method and system

• US 7,356,170 B2
• Filed: 02/12/2004
• Issued: 04/08/2008
• Est. Priority Date: 02/12/2004
• Status: Active Grant

• Current Assignee: Lenovo PC International Limited (Lenovo Group Ltd.)
• Original Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Inventors: Udupa, Raghavendra U., Pandit, Vinayaka D.
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/777,806
• Publication Number:
  US 20050180614A1
• Time in Patent Office: 1,517 Days
• Field of Search: 382/124, 382/125, 382/115, 382/302, 382/116, 382/209, 382/127, 382/126, 382/190, 382/211, 382/260, 382/218, 382/272, 382/266, 382/224, 713/186, 707/6, 707/7, 283/78, 283/69, 283/68, 356/71
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A method of matching a query fingerprint to a plurality of file fingerprints. The method comprises the steps of determining a plurality of partial features of each of the file fingerprints. For each partial feature, derive a list of all file fingerprints which have said partial feature as one of their partial features. Determine a plurality of query partial features of the query fingerprint, and derive a ranked list of the file fingerprints based on identifying the individual query partial features in the partial features of the respective file fingerprints. Then perform one-to-one matching of the query fingerprint with selected ones of the ranked list of the file fingerprints.

Claims

1. A method of matching a query fingerprint to a plurality of file fingerprints, the method comprising the steps of:

determining a plurality of partial features of each of the file fingerprints,

for each partial feature, deriving a list of all file fingerprints which have said partial feature,

determining a plurality of query partial features of the query fingerprint;

identifying file fingerprints comprising partial features that match said query partial features of said query fingerprint;

deriving a ranked list of the file fingerprints based on said identifying; and

performing a one-to-one matching of the query fingerprint only with file fingerprints comprising a pre-determined rank in said ranked list.

2. The method as claimed in claim 1, wherein the method comprises associating a discriminate score with each partial feature based on the number of file fingerprints which have said partial feature as one of their partial features, and the step of deriving the ranked list of the file fingerprints comprises updating scores for matches between the query fingerprint and individual ones of the file fingerprints based on the discriminate scores of one or more partial features identified in the individual file fingerprints as one of the query partial features.

3. The method as claimed in claim 2, wherein the discriminate score is calculated in a manner such that it has higher values for partial features that occur in a smaller number of file fingerprints.

4. The method as claimed in claim 3, wherein the discriminate scores are further based on a total number of partial features in all of the file fingerprints.

5. The method as claimed in claim 1, wherein the partial features comprise minutiae feature sets.

6. The method as claimed in claim 5, wherein the minutiae feature sets each comprise a set of minutiae features for which a geometric separation between any two minutiae in it falls within a predetermined range.

7. The method as claimed in claim 6, wherein a number of minutiae features in each minutiae feature set falls within a predetermined range.

8. A system for matching a query fingerprint to a plurality of file fingerprints, the system comprising:

a database having stored data therein providing a plurality of partial features of each of the file fingerprints and for each partial feature a list of all file fingerprints which have said partial feature;

a processing unit for

determining a plurality of query partial features of the query fingerprint,

identifying file fingerprints comprising partial features that match said query partial features of said query fingerprint, and

deriving ranked list of the file fingerprints based on said identifying; and

a one-to-one fingerprint matching unit for performing one-to-one matching between the query fingerprint and only file fingerprints comprising a pre-determined rank in said ranked list.

9. The system as claimed in claim 8, wherein the processing unit associates a discriminate score with each partial feature based on the number of file fingerprints which have said partial feature as one of their partial features, and updates scores for matches between the query fingerprint and individual ones of the file fingerprints based on the discriminate scores of one or more partial features identified in the individual file fingerprints as one of the query partial features during the deriving of the ranked list of the file fingerprints.

10. The system as claimed in claim 9, wherein the processing unit calculates the discriminate scores in a manner such that it has higher values for partial features that occur in a smaller number of file fingerprints.

11. The system as claimed in claim 10, wherein the processing unit further bases the discriminate score on a total number of partial features in all of the file fingerprints.

12. The system as claimed in claim 8, wherein the partial features comprise minutiae feature sets.

13. The system as claimed in claim 12, wherein the minutiae feature sets each comprise a set of minutiae features for which a geometric separation between any two minutiae in it falls within a predetermined range.

14. The system as claimed in claim 13, wherein a number of minutiae features in each minutiae feature set falls within a predetermined range.

15. A computer program, recorded on a medium, for instructing a computer to conduct a method of matching a query fingerprint to a plurality of file fingerprints, the method comprising the steps of:

determining a plurality of partial features of each of the file fingerprints;

for each partial feature, deriving a list of all file fingerprints which have said partial feature;

determining a plurality of query partial features of the query fingerprint;

identifying file fingerprints comprising partial features that match said query partial features of said query fingerprint;

deriving a ranked list of the file fingerprints based on said identifying; and

performing a one-to-one matching of the query fingerprint only with file fingerprints comprising a pre-determined rank in said ranked list.

16. The computer program as claimed in claim 15, wherein the method comprises associating a discriminate score with each partial feature based on the number of file fingerprints which have said partial feature as one of their partial features, and the step of deriving the ranked list of the file fingerprints comprises updating scores for matches between the query fingerprint and individual ones of the file fingerprints based on the discriminate scores of one or more partial features identified in the individual file fingerprints as one of the query partial features.

17. The computer program as claimed in claim 16, wherein the discriminate score is calculated in a manner such that it has higher values for partial features that occur in a smaller number of file fingerprints.

18. The computer program as claimed in claim 17, wherein the discriminate scores are further based on a total number of partial features in all of the file fingerprints.

19. The computer program as claimed in claim 15, wherein the partial features comprise minutiae feature sets.

20. The computer program as claimed in claim 19, wherein the minutiae feature sets each comprise a set of minutiae features for which a geometric separation between any two minutiae in it falls within a predetermined range.

21. The computer program as claimed in claim 20, wherein a number of minutiae features in each minutiae feature set falls within a predetermined range.