Minutiae fingerprint transactions

• US 7,333,638 B2
• Filed: 01/18/2005
• Issued: 02/19/2008
• Est. Priority Date: 01/18/2005
• Status: Active Grant

• Current Assignee: Lenovo PC International Limited (Lenovo Group Ltd.)
• Original Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Inventors: Chisamore, Seth B., Outlaw, Michael P., Trevathan, Matthew B., Holladay, Christopher E.
• Primary Examiner(s): LE, BRIAN Q
• Application Number:
  US11/037,990
• Publication Number:
  US 20060159316A1
• Time in Patent Office: 1,127 Days
• Field of Search: 382124-126, 382/115, 340/5.52, 340/5.53, 340/5.82, 340/5.83, 358486-497, 358/466, 250/234
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1353 Extracting features related to minutiae or pores

Abstract

Minutiae based fingerprint transactions are validated and authenticated over wireless based communications systems, such as over a Bluetooth wireless based communication system. Minutiae points are unique identification points on a fingerprint where a ridge in the fingerprint joins another ridge or a ridge ends. The combination of any three minutiae points forms a triangle, and the method/algorithm of the present invention uses triangles of minutiae points because triangles are proportional regardless of possible differences in scale of two fingerprints being compared. A first method/algorithm uses a minutiae exchange where triplets of minutiae points are exchanged and form triangles for comparison between an original template of minutiae points and a stored template of minutiae points. A second method/algorithm exchanges three linear equations for three pairs of minutiae points that form triangles for comparison between an original template and a stored template.

Claims

1. A method for authenticating a user, comprising the steps of:

acquiring an image of an original fingerprint of the user at a local authentication device, and identifying minutiae points on the original fingerprint image where a ridge in the fingerprint joins another ridge or a ridge ends, and the combination of any three minutiae points forms a triangle, with triangles being proportional regardless of possible differences in scale of two fingerprints being compared, and the local authentication device determining a reference triangle of three minutiae points in the original fingerprint;

the local authentication device transmitting data relating to the reference triangle of minutiae points in the original fingerprint to a plurality of remote authentication devices, each remote authentication device performing a validation function upon the original fingerprint image utilizing data related to the reference triangle to determine if it has a stored candidate fingerprint in memory having a triangle matching the reference triangle, and if so the remote authentication device sends back to the local authentication device data on two of the minutiae points of the reference triangle to form a reference side, and also sends data on a third new minutiae point, not related to the reference triangle, in the stored candidate fingerprint;

when data on the third new minutiae point is received by the local authentication device, the local authentication device can determine the stored candidate fingerprint not to be a match if the original fingerprint does not have the third new minutiae point, and if the third new minutiae point is validated, the local authentication device sends a fourth new minutiae point to the remote device, and each successive validation transaction results in an additional minutiae point being sent between the local authenticating device and the remote authentication device until the authentication method determines a match.

2. The method of claim 1, wherein the local device sends data on the fourth new minutiae point to all remote devices that were validated in the previous transaction, and any remote device that was not validated during the previous transaction is removed from further validation processing to protect the integrity of the fingerprint.

3. The method of claim 2, wherein the authenticatine method determines a match when a threshold number of minutiae points are validated, and all other remote devices have been removed as a candidate for a match in the authenticating method.

4. The method of claim 1, wherein the authenticating method uses a minutiae exchange where triplets of minutiae points are exchanged and form triangles for comparison between an original template of minutiae points and a stored template of minutiae points.

5. The method of claim 1, wherein the authenticating method uses an exchange of three linear equations for three pairs of minutiae points that form triangles for comparison between an original template of minutiae points and a stored template of minutiae points.

6. The method of claim 1, wherein the local device determining line equations for first, second and third lines connecting first, second and third pairs of minutiae points located on the image of the original fingerprint, wherein the first line has a positive slope, the second line has a negative slope, and the third line has a slope that is not equal to the positive slope or the negative slope, and wherein intersections of the first, second and third lines form a triangle.

7. The method of claim 6, further comprising the step of transmitting the line equations to the plurality of remote devices, wherein each remote device compares the triangle formed by the transmitted line equations to triangles formed by line equations for three pair of minutiae points located on fingerprint images stored within a storage means of the remote device.

8. The method of claim 7, wherein if a remote device determines that the triangle formed by the transmitted lines is congruent to a triangle formed by line equations for pairs of minutiae points located upon a stored fingerprint image, then the remote device transmits three new line equations to the local device for comparison, and the transmittal of line equations between the local device and the remote device continues until either device determines that a triangle being compared is not congruent or a predetermined acceptance threshold has been reached.

9. The method of claim 8, further comprising the step of transmitting the coordinates of the triangle to the remote devices, wherein each remote device compares the coordinates of the transmitted triangle to the minutiae points of their stored fingerprint images to determine if their stored images contain a matching image.

10. The method of claim 1, wherein the transmittal of new minutiae points between the local device and the remote device continues until either device determines that a triangle being compared is not congruent or a predetermined acceptance threshold has been reached.

11. A method for authenticating a user, comprising the steps of:

acquiring an image of an original fingerprint of the user at a local authentication device, and identifying minutiae points on the original fingerprint image where a ridge in the fingerprint joins another ridge or a ridge ends, and the combination of any three minutiae points forms a triangle, with triangles being proportional regardless of possible differences in scale of two fingerprints being compared;

the local authentication device transmitting data relating to selected minutiae points in the original fingerprint to a plurality of remote authentication devices, each remote authentication device performing a validation function upon the original fingerprint image utilizing data related to the selected minutiae points in the original fingerprint to determine if it has a stored candidate fingerprint in memory matching the original fingerprint, and if so the remote authentication device sends back to the local authentication device data on a new minutiae point, not related to the selected minutiae points in the original fingerprint;

when data on the new minutiae point is received by the local authentication device, the local authentication device can determine the stored candidate fingerprint not to be a match if the original fingerprint does not have the new minutiae point, and if the new minutiae point is validated, the local authentication device sends a further new minutiae point to the remote device, and each successive validation transaction results in an additional new minutiae point being sent between the local authenticating device and the remote authentication device until the authentication method determines a match.

12. The method of claim 11, wherein the local device sends data on the further new minutiae point to all remote devices that were validated in the previous transaction, and any remote device that was not validated during the previous transaction is removed from further validation processing to protect the integrity of the fingerprint.

13. The method of claim 12, wherein the authenticating method determines a match when a threshold number of minutiae points are validated, and all other remote devices have been removed as a candidate for a match in the authenticating method.

14. The method of claim 11, wherein the authenticating method uses a minutiae exchange where triplets of minutiae points are exchanged and form triangles for comparison between an original template of minutiae points and a stored template of minutiae points.

15. The method of claim 11, wherein the authenticating method uses an exchange of three linear equations for three pairs of minutiae points that form triangles for comparison between an original template of minutiae points and a stored template of minutiae points.

16. The method of claim 11, wherein the local device determining line equations for first, second and third lines connecting first, second and third pairs of minutiae points located on the image of the original fingerprint, wherein the first line has a positive slope, the second line has a negative slope, and the third line has a slope that is not equal to the positive slope or the negative slope, and wherein intersections of the first, second and third lines form a triangle.

17. The method of claim 16, further comprising the step of transmitting the line equations to the plurality of remote devices, wherein each remote device compares the triangle formed by the transmitted line equations to triangles formed by line equations for three pair of minutiae points located on fingerprint images stored within a storage means of the remote device.

18. The method of claim 17, wherein if a remote device determines that the triangle formed by the transmitted lines is congruent to a triangle formed by line equations for pairs of minutiae points located upon a stored fingerprint image, then the remote device transmits three new line equations to the local device for comparison, and the transmittal of line equations between the local device and the remote device continues until either device determines that a triangle being compared is not congruent or a predetermined acceptance threshold has been reached.

19. The method of claim 18, further comprising the step of transmitting the coordinates of the triangle to the remote devices, wherein each remote device compares the coordinates of the transmitted triangle to the minutiae points of their stored fingerprint images to determine if their stored images contain a matching image.

20. The method of claim 11, wherein the transmittal of new minutiae points between the local device and the remote device continues until either device determines that a triangle being compared is not congruent or a predetermined acceptance threshold has been reached.