Method and system for fingerprint encoding and authentication

• US 6,757,411 B2
• Filed: 10/01/2001
• Issued: 06/29/2004
• Est. Priority Date: 08/16/2001
• Status: Expired due to Fees

• Current Assignee: Liska Biometry, Inc.
• Original Assignee: Liska Biometry, Inc.
• Inventors: Chau, Lam Ko
• Primary Examiner(s): Johnson, Timothy M.
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/965,809
• Publication Number:
  US 20030035569A1
• Time in Patent Office: 1,002 Days
• Field of Search: 382/115, 382/124, 382/125, 382/190, 382/181, 382/288, 382/286, 382/204, 382/203, 340/5.52, 340/5.53, 340/5.82, 340/5.83, 250/221, 345/157, 356/71
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A method, system and computer readable-storage medium for generating an identification code from a fingerprint image exhibiting a plurality of features. The method includes establishing a reference point from the plurality of features, generating at least one metric from the reference point and at least one of the plurality of features and forming the identification code from the at least one metric. Changes in the temperature and humidity of a finger when the image is taken at different times will result in minor variations of the measured features which, upon quantization, result a metric that is invariant from one fingerprint image to the next, for the same finger. This lowers the false rejection rate to an acceptable level. Meanwhile, the metric is sufficiently unique for a given set of features such that the probability of assigning the same metric to two different fingers is lowered to an acceptable level.

Claims

1. A method of generating an identification code from a fingerprint image exhibiting a plurality of features, comprising:

establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

generating at least one metric from the reference point and at least one of the plurality of features; and

forming the identification code from the at least one metric.

2. A method as defined in claim 1, wherein establishing a reference point comprises determining the location of a point on the fingerprint image that is central to the plurality of features.

3. A method as defined in claim 1, wherein establishing a reference point comprises determining the location of a point on the fingerprint image that is central to a subset of the plurality of features.

4. A method as defined in claim 3, wherein said subset of the plurality of features consists of isolated vertices, wherein a vertex is isolated if it is not connected to another vertex.

5. A method as defined in claim 3, wherein said subset of the plurality of features consists of non-isolated vertices, wherein a vertex is non-isolated if it is connected to another vertex.

6. A method as defined in claim 3, wherein establishing a reference point comprises determining which one of the isolated vertices minimizes the maximum distance between itself and all other isolated vertices, said reference point being said one of the isolated vertices.

7. A method as defined in claim 3, wherein establishing a reference point comprises determining which one of the non-isolated vertices minimizes the maximum distance between itself and all other non-isolated vertices, said reference point being said one of the non-isolated vertices.

8. A method as defined in claim 3, wherein the reference point is a first reference point and wherein said subset of the features is a first subset, the method further comprising:

establishing a second reference point by determining the location of a point on the fingerprint image that is central to a second subset of the plurality of features;

wherein generating at least one metric includes determining a distance between the first reference point and the second reference point, said metric being said distance.

9. A method as defined in claim 8, wherein the first subset of the plurality of features consists of isolated vertices and wherein the second subset of the plurality of features consists of non-isolated vertices.

10. A method as defined in claim 1, wherein establishing a reference point comprises determining which one of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features, said reference point being said one of the features.

11. A method as defined in claim 1, wherein the reference point is a first reference point, wherein said subset is a first subset, wherein said one feature is a first feature, the method further comprising:

establishing a second reference point by determining which second feature from a second subset of the plurality of features minimizes the maximum distance between itself and all other features from said second subset of the features, said reference point being said second feature;

wherein generating at least one metric includes determining a distance between the first reference point and the second reference point, said at least one metric including said distance.

12. A method as defined in claim 11, wherein the first subset of the plurality of features consists of isolated vertices and wherein the second subset of the plurality of features consists of non-isolated vertices.

13. A method as defined in claim 11, wherein generating at least one metric includes:

generating a plurality of metrics by determining an average distance between the first reference point and a respective subset of the features, wherein each said subset of the features includes those features in an angular sector measured with respect to an imaginary line that joins the first and second reference points, said at least one metric including said average distance.

14. A method as defined in claim 11, wherein generating at least one metric includes determining an average angle between an imaginary line joining the first and second reference points and each of the plurality of features.

15. A method as defined in claim 1, wherein the reference point is a first reference point, the method further comprising:

establishing a second reference point;

wherein generating at least one metric includes determining a distance between the first reference point and the second reference point, said metric being said distance.

16. A method as defined in claim 1, wherein generating at least one metric includes determining an average distance between the reference point and each of the plurality of features.

17. A method as defined in claim 1, wherein generating at least one metric includes:

determining an average distance between the reference point and each of the plurality of features;

determining one feature for which the distance between the reference point and said one feature is closest to the average distance; and

determining a distance between the reference point and said one feature.

18. A method as defined in claim 1, wherein generating at least one metric includes determining an average distance between the reference point and each feature in a subset of the plurality of features.

19. A method as defined in claim 1, wherein generating at least one metric includes:

determining an average distance between the reference point and each feature in a subset of the plurality of features;

determining one feature in said subset of the plurality of features for which the distance between the reference point and said one feature is closest to the average distance; and

determining a distance between the reference point and said one feature.

20. A method as defined in claim 19, wherein said subset of the plurality of features includes a set of isolated vertices, wherein a vertex is isolated if it is not connected to another vertex.

21. A method as defined in claim 19, wherein said subset of the plurality of features includes a set of non-isolated vertices.

22. A method as defined in claim 1, wherein forming the identification code from the at least one metric includes:

scaling each metric to within a desired range;

applying a many-to-one mapping to each scaled metric, thereby to create at least one respective quantized metric; and

combining the at least one quantized metric to form the identification code.

23. A method as defined in claim 22, wherein said many-to-one mapping maps onto a set of prime numbers.

24. A method as defined in claim 22, wherein said many-to-one mapping maps onto products of pairs of prime numbers.

25. A method as defined in claim 22, wherein said many-to-one mapping maps onto powers of two.

26. A method as defined in claim 22, wherein combining the at least one quantized metric to form the identification code includes concatenating the at least one quantized metric with at least one topologically invariant parameter, thereby to generate the identification code.

27. A method as defined in claim 26, wherein the at least one topologically invariant parameter includes a nullity of a graph defined by the plurality of features.

28. A method as defined in claim 27, wherein the at least one topologically invariant parameter further includes a number of connected pieces of a graph defined by the plurality of features.

29. A method as defined in claim 26, wherein the at least one topologically invariant parameter includes a number of connected pieces of a graph defined by the plurality of features.

30. Computer-readable media tangibly embodying a program of instructions executable by a computer to perform the method of claim 1.

31. A system for generating an identification code from a fingerprint image exhibiting a plurality of features, comprising:

means for establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

means for generating at least one metric from the plurality of features and the reference point; and

means for forming the identification code from the at least one metric.

32. A computer readable storage medium containing a program element for execution by a computing device to implement a system for generating an identification code from a fingerprint image exhibiting a plurality of features, said program element including:

program code for establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

program code for generating at least one metric from the plurality of features and the reference point; and

program code for forming the identification code from the at least one metric.

33. A method of generating an identification code for association with a human finger, comprising:

obtaining a fingerprint image of the finger;

identifying a plurality of features on the fingerprint image;

establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

generating at least one metric from the reference point and at least one of the plurality of features; and

forming the identification code from the at least one metric.

34. A method as defined in claim 33, wherein identifying a plurality of features on the fingerprint image comprises identifying a set of isolated vertices and a set of non-isolated vertices, wherein a vertex is isolated if it is not connected to another vertex and wherein a vertex is non-isolated if it is connected to another vertex.

35. A method as defined in claim 33, wherein identifying a plurality of features on the fingerprint image includes:

identifying all bifurcations, end points, vertices, pores, arcs, circuits, flux lines and creases;

marking off creases while maintaining continuity of a flux line;

using pores existing on ridges to extend continuity of a flux line;

where three arcs join to form a bifurcation defining a ridge and a valley, selecting the point where the ridge meets the valley as one of the plurality of features;

where an end point of an arc appears very close to another arc, selecting this end point as one of the plurality of features; and

ignoring vertices belonging to any circuit and end points taken from a broken flux.

36. A method of generating an identification code for association with a human finger, comprising:

obtaining a plurality of fingerprint images of the finger;

identifying, for each fingerprint image, a respective plurality of features;

establishing, from each plurality of features, a respective reference point;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

generating, from each plurality of features and the respective reference point, a respective metric;

identifying a most frequently occurring metric from amongst the generated metrics; and

forming the identification code as a function of the most frequently occurring metric.

37. A system for generating an identification code for association with a human finger, comprising:

means for obtaining a fingerprint image of the finger;

means for identifying a plurality of features on the fingerprint image;

means for establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

means for generating at least one metric from the reference point and at least one of the plurality of features; and

means for forming the identification code from the at least one metric.

38. A computer readable storage medium containing a program element for execution by a computing device to implement a system for generating an identification code for association with a human finger, the program element including:

program code means for obtaining a fingerprint image of the finger;

program code means identifying a plurality of features on the fingerprint image;

program code means establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

program code means generating at least one metric from the reference point and at least one of the plurality of features; and

program code means forming the identification code from the at least one metric.

39. A computer readable medium storing a program for execution by a computing device to generate an identification code for association with a human finger, the program including the steps of:

a step of generating at least one quantized metric generated as a function of (i) at least one of a plurality of features and (ii) a reference point established from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature.

40. A fingerprint-based user authentication system, comprising:

a database of identification codes uniquely associated with respective users;

an input device for obtaining, from a test user, a first fingerprint image and information identifying a first user; and

a controller connected to the input device and to the database, the controller being operable to;

(a) access the database in order to obtain a first identification code associated with the first user;

(b) process the first fingerprint image in order to generate a second identification code;

wherein processing the first fingerprint image in order to generate a second identification code includes;

identifying a plurality of features on the first fingerprint image;

establishing a reference point from the plurality of features;

wherein establishing a reference point comprises determining which one feature from a subset of the plurality of features minimizes the maximum distance between itself and all others of the plurality of features from said subset of the features, said reference point being said one feature;

generating at least one metric as a function of the reference point and at least one of the plurality of features; and

forming the second identification code from the at least one metric; and

(c) authenticate the test user as the first user by comparing the first and second identification codes to one another.

41. A system as defined in claim 40, wherein authenticating the test user as the first user by comparing the first and second identification codes to one another includes:

if the first and second identification codes are identical, instructing the input device to obtain, from the test user, a second version of the first fingerprint image.

42. A system as defined in claim 41, wherein authenticating the test user as the first user by comparing the first and second identification codes to one another further includes:

determining whether any variations in at least one metric exist amongst two or more versions of the first fingerprint image; and

if no variations exist, concluding that the test user is not the first user.

43. A system as defined in claim 41, wherein authenticating the test user as the first user by comparing the first and second identification codes to one another includes:

concluding that the test user is the first user if the first and second identification codes are identical.

44. A system as defined in claim 41, wherein authenticating the test user as the first user by comparing the first and second identification codes to one another includes:

concluding that the test user is not the first user if the first and second identification codes are not identical.