System and method for deriving a string-based representation of a fingerprint image

• US 6,487,306 B1
• Filed: 02/25/1998
• Issued: 11/26/2002
• Est. Priority Date: 08/22/1997
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (FIG LLC (d/b/a Fortress Investment Group LLC))
• Original Assignee: International Business Machines Corporation
• Inventors: Pankanti, Sharathchandra Umapathirao, Bolle, Rudolf Maarten, Hong, Lin, Jain, Anil K.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/030,595
• Time in Patent Office: 1,735 Days
• Field of Search: 382/124, 382/125, 382/126, 382/127, 382/201, 340/5.83
• US Class Current: 382/125
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

The invention is a system and method for deriving a single dimensional representation for a set of points e.g.,minutiae, in image of a two dimensional pattern of lines, e.g. a fingerprint, by creating a one dimensional (string) representation of one or more points (e.g., minutiae) and the respective attributes of each point therein. A landmark point is selected from the two dimensional image, preferably from the set of the points to be represented in single dimension. The relationships of each of the points with reference to the landmark determines a linear order for the points and the attributes associated with each point.

Claims

1. A system, for deriving a string representation of an image, comprising:

a computer having one or more central processing units (CPUs) and a memory;

one or more images stored in the memory, the image having one or more points;

a reference landmark selector, executed by the CPU, that selects a landmark; and

a representation unit that determines point attributes associated with individual ones of the image points, that orders and merges the point attributes into a first string, and that composes a plurality of first strings into an ordered second string that represents the image, where the point attributes are ordered with respect to the landmark, where individual ones of the plurality of first strings are ordered within the second string also with respect to the landmark, where said representation unit orders the plurality of first bit strings in a linear order with respect to at least one of the point attributes, where the order is determined by a distance between the landmark and the respective point and by an angle subtended by a vector between the landmark and the respective point and a reference line.

2. A method for comparing a two-dimensional input fingerprint representation to a template fingerprint representation, comprising the steps of:

identifying a reference location in both the input fingerprint representation and the template fingerprint representation;

estimating translation (t=(Δ

_x,Δ

_y)) and rotation (−

P) parameters between ridges associated with input minutiae and ridges associated with template minutiae to obtain transformed representations;

converting the transformed representations into polar coordinate representations with respect to the reference location;

representing the polar coordinate representations of the input fingerprint representation and the template fingerprint representation as two symbolic strings having an order with respect to the reference location; and

executing a matching algorithm on the two symbolic strings to generate a matching score that indicates a number of matched corresponding minutiae between the input and template fingerprint representations,

wherein the step of converting the transformed representations into polar coordinate representations comprises a step of computing a tuple comprised of polar coordinate attributes for each minutia, these attributes comprising a radius, an e-angle, and a t-angle, wherein the radius is a Euclidean distance between a given minutia and a respective reference minutia, wherein the e-angle is a counter-clockwise angle subtended by a line segment joining the given minutia and the respective reference minutia with a fixed reference axis passing through the reference minutia; and

wherein the t-angle for the given minutia is a counter-clockwise angle subtended by the line segment joining the given minutia and the respective reference minutia with a minutia orientation vector, and

wherein the step of representing comprises a step of ordering the tuples by increasing e-angle.

3. A method for comparing a two-dimensional input fingerprint representation to a template fingerprint representation, comprising steps of:

identifying a reference location in both the input fingerprint representation and the template fingerprint representation;

estimating translation (t=(Δ

_x,Δ

_y)) and rotation (Δ

θ

) parameters between ridges associated with input minutiae and ridges associated with template minutiae to obtain transformed representations;

converting the transformed representations into polar coordinate representations with respect to the reference location;

representing the polar coordinate representations of the input fingerprint representation and the template fingerprint representation as two symbolic strings; and

executing a matching algorithm on the two symbolic strings to generate a matching score that indicates a number of matched corresponding minutiae between the input and template fingerprint representations,

wherein the step of converting the transformed representations into polar coordinate representations comprises a step of computing a tuple comprised of polar coordinate attributes for each minutia, and wherein the step of executing the matching algorithm on the two symbolic strings employs a plurality of consistency thresholds when comparing polar coordinate attributes of a minutia of the input fingerprint representation to polar coordinate attributes of a minutia of the template fingerprint representation, and wherein at least one of the consistency thresholds is adaptively updated as a function of a number of minutiae that are matched.

4. A system for deriving a string representation of an image, comprising:

a computer having one or more central processing units (CPUs) and a memory;

one or more images stored in the memory, the image having one or more points;

a reference landmark selector, executed by the CPU, that selects a landmark; and

a representation unit that determines point attributes associated with individual ones of the image points, that orders and merges the point attributes into a first string, and that composes a plurality of first strings into an ordered second string that represents the image, where the point attributes are ordered with respect to the landmark, where individual ones of the plurality of first strings are ordered within the second string also with respect to the landmark, and wherein each of the point attributes is represented as a tuple that has an e-angle value, and wherein said representation unit orders said tuples by increasing e-angle values.

5. A system, as in claim 4, where the landmark is one of the points.

6. A system, as in claim 4, where the image is an image of a fingerprint and the points represent minutiae of the fingerprint.

7. A system, as in claim 4, where one or more of the point attributes are determined by a relationship between the landmark and respective point.

8. A system, as in claim 7, where the point attributes include any one or more of the following:

a distance between the landmark and the respective point, a first angle subtended by a vector between the landmark and the respective point and a reference line, and a second angle determined from a landmark orientation associated with the landmark and a point orientation associated with the respective point.

9. A system, as in claim 4, wherein said representation unit orders the plurality of first bit strings in a linear order with respect to at least one of the point attributes.

10. A system, as in claim 9, where the order is determined by a distance between the landmark and the respective point.

11. A system, as in claim 10, where the order is determined by increasing distance from the landmark.

12. A system, as in claim 4, where the tuples in the first string are compressed.

13. A system, as in claim 4, where the tuples in the first string are encrypted.

14. A system, as in claim 4, where the second string is compressed.

15. A system, as in claim 4, where the second string is encrypted.

16. A method for processing a two-dimensional input fingerprint representation, comprising steps of:

processing the input fingerprint representation to identify a plurality of minutiae, individual ones of the identified plurality of minutiae being described by an attribute tuple having values determined by reference to a landmark feature in the input fingerprint image;

ordering the attribute tuples in accordance with at least one of the values;

representing individual ones of the ordered tuples as a first bit string to provide a plurality of one dimensional first bit strings;

composing the plurality of one dimensional first bit strings into a one dimensional second bit string wherein individual ones of the plurality of first bit strings are arranged in order with respect to the landmark feature; and

wherein said at least one of the values is an e-angle, and wherein said ordering step orders the attribute tuples by increasing e-angles.

17. A method as in claim 16, wherein the order is an order of increasing radial distance.

18. A method as in claim 16, wherein the step of representing individual ones of the ordered tuples as the first bit string comprises a step of concatenating bits representing the values, and wherein the step of composing the plurality of first bit strings into the second bit string comprises a step of concatenating the bits of the plurality of first bit strings.

19. A method for comparing a two-dimensional input fingerprint representation to a template fingerprint representation, comprising steps of:

identifying a reference location in both the input fingerprint representation and the template fingerprint representation;

estimating translation (t=(Δ

_x,Δ

_y)) and rotation (Δ

θ

) parameters between ridges associated with input minutiae and ridges associated with template minutiae to obtain transformed representations;

converting the transformed representations into polar coordinate representations with respect to the reference location;

representing the polar coordinate representations of the input fingerprint representation and the template fingerprint representation as two symbolic strings having an order with respect to the reference location;

executing a matching algorithm on the two symbolic strings to generate a matching score that indicates a number of matched corresponding minutiae between the input and template fingerprint representations, wherein each minutia has at least one attribute represented as a tuple, wherein said at least one attribute is an e-angle, and wherein said representing step orders the attribute tuples by increasing e-angles.

20. A method as in claim 19, wherein the step of estimating translation and rotation parameters transforms the input fingerprint representation into a frame of reference of the template fingerprint representation.

21. A method as in claim 19, wherein the step of converting the transformed representations into polar coordinate representations comprises a step of computing said tuples comprised of polar coordinate attributes for each minutia, these attributes comprising a radius, said e-angle, and a t-angle, wherein the radius is a Euclidean distance between a given minutia and a respective reference minutia, wherein the e-angle is a counter-clockwise angle subtended by a line segment joining the given minutia and the respective reference minutia with a fixed reference axis passing through the reference minutia;

and wherein the t-angle for the given minutia is a counter-clockwise angle subtended by the line segment joining the given minutia and the respective reference minutia with a minutia orientation vector.

22. A method as in claim 21, wherein the step of representing comprises steps of:

quantizing values of the minutiae attributes into discrete values and numbers of bits;

aggregating the quantized values of individual radius, e-angle, and t-angle attributes so that each minutia is represented by a string of bits forming an aggregate vector; and

composing the aggregate vectors into a composite string of bits representing one of the symbolic strings.

23. A method as in claim 19, and further comprising a step of normalizing the matching score as a function that comprises a number of minutia extracted from the template and the input fingerprint representations.

24. A method as in claim 19, wherein the reference location corresponds to a minutia.

25. A method as in claim 19, wherein the reference location corresponds to a ridge-ending minutia.

26. A method as in claim 19, wherein the step of identifying comprises steps of selecting and analyzing pairs of minutiae, one from the input representation and one from the template representation, until a pair of minutiae that meets a predetermined criterion is found.

27. A method as in claim 19, wherein the step of identifying comprises steps of selecting and analyzing pairs of minutiae, one from the input representation and one from the template representation, until a pair of minutiae that exceeds an alignment threshold is found.

28. A method as in claim 19, wherein the step of identifying comprises steps of selecting and analyzing pairs of minutiae, one from the input representation and one from the template representation, until a pair of minutiae that exceeds an alignment threshold is found, wherein an initial pair of minutiae is selected as being a pair closest to a center of mass of minutiae.

29. A method as in claim 19, wherein the step of identifying comprises steps of selecting and analyzing pairs of ridge-ending minutiae, one from the input representation and one from the template representation, until a pair of ridge-ending minutiae that exceeds an alignment threshold is found, wherein an initial pair of ridge-ending minutiae is selected as being a pair closest to a center of mass of minutiae in each of the input representation and the template representation.