Fingerprint feature correlator

• US 6,134,340 A
• Filed: 12/22/1997
• Issued: 10/17/2000
• Est. Priority Date: 12/22/1997
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: TRW Inc. (Northrop Grumman Corporation)
• Inventors: Hsu, Shi-Ping, Evans, Bruce W.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): CAGE, SHAWN B
• Application Number:
  US08/995,330
• Time in Patent Office: 1,030 Days
• Field of Search: 382/124, 382/125, 382/209, 382/258, 382/259, 382/116, 283/69, 356/71
• US Class Current: 382/124
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 40/1365 Matching; Classification

Abstract

A device, and a method for its operation, for verifying a person'"'"'s identity by comparing in a correlator (18) selected features of a reference fingerprint image, generated in a sensor (10) from the fingerprint of a person of known identity, with a subject fingerprint image taken from a person whose identity is to be verified. In an enrollment procedure, a fingerprint from a person of known identity is analyzed in an enrollment processor (14) to locate multiple reference patches that together are distinctive to that person'"'"'s fingerprint. The reference patch images are stored, together with their locations in the image, in a reference image storage unit (16). When a subject fingerprint image is later provided, every reference patch is compared with every possible patch of similar size in the subject image, to find a set of candidate match locations in the subject image. Then a subset of the candidate match locations is selected such that the candidate match locations in the subset are practically geometrically congruent with the locations of a corresponding subset of reference patches. A verification match is declared based on the number candidate match locations in the selected subset that satisfies this geometric constraint.

Claims

1. A fingerprint feature correlator for high-speed verification of a person'"'"'s identity, comprising:

a fingerprint sensor, for generating a digital image of a fingerprint;

an enrollment processor for extracting, from a fingerprint image generated by the fingerprint sensor from the fingerprint of an identified person, multiple reference patches that together uniquely identify the image, each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

reference image storage means, for storing reference patch images and locations provided by the enrollment processor;

a correlation processor, for searching an entire subject fingerprint image generated by the fingerprint sensor from the fingerprint of a person seeking identity verification, for instances of pixel patterns similar to the stored reference patch images, and for generating a set of candidate match locations in the subject image;

a geometric constraint checking processor, for attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy, and for determining whether there is a match between the subject image and the stored reference image; and

an image preprocessor, for converting the digital image of the fingerprint to binary form and to a standard orientation;

and wherein the enrollment processor includes

means for thinning the binary image to obtain skeletal images of ridges and valleys in the fingerprint;

means for analyzing the skeletal images to locate bifurcation features in the ridges and valleys;

means for selecting reference patches based on feature density, and storing the reference patch positions in the reference image storage means; and

means for extracting reference patch images from the skeletal images of the ridges and valleys and storing the reference patch images in the reference image storage means with the corresponding reference patch locations.

2. A fingerprint image feature correlator as defined in claim 1, wherein the correlation processor includes:

an array of correlator units, each for comparing a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

an address generator, for generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image; and

a result collection memory, for recording pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image.

5. A fingerprint image feature correlator as defined in claim 2, wherein:

each correlator unit includes a counter for recording a count indicative of the degree of match between a reference patch and a patch of the subject image; and

the correlation processor further includes means for saving the contents of the counters in the result collection memory on completion of a comparison of all pixels in the reference patches, and means for saving a subject image location with each count, and means for resetting the counters to begin a comparison with other locations in the subject image.

7. A fingerprint image feature correlator as defined in claim 1, wherein the geometric constraint checking processor includes:

means for determining the distances between all possible pairs of reference patches;

means for determining the distances between all possible pairs of distinct match candidates;

means for selecting a feasible subset of the distinct match candidates such that the distances between all possible pairs in the feasible subset are approximately equal to the distances between corresponding pairs of reference patches; and

means for declaring a match based on the size of the feasible subset.

3. A fingerprint feature correlator for high-speed verification of a person'"'"'s identity, comprising:

a fingerprint sensor, generating a digital image of a fingerprint;

an enrollment processor for extracting, from a fingerprint image generated by the fingerprint sensor from the fingerprint of an identified person, multiple reference patches that together uniquely identify the each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

reference image storage means, for storing reference patch images and locations provided by the enrollment processor;

a correlation processor, for searching an entire subject fingerprint image generated by the fingerprint sensor from the fingerprint of a person seeking identity verification, for instances of pixel patterns similar to the stored reference patch images, and for generating a set of candidate match locations in the subject image; and

a geomertric constraint checking processor, for attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy, and for determining whether there is a match between the subject image and the stored reference image;

wherein the correlation processor includes

an array of correlator units, each for comparing a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

an address generator, for generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image wherein each reference patch is compared with every possible patch position in the subject image; and

a result collection memory, for recording pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image;

and wherein the address generator further includes means for generating rotated reference patch addresses in such a way that a rotated image of each reference patch is also compared with each possible patch of the subject image.

4. A fingerprint image feature correlator as defined in claim 3, wherein the means for generating rotated reference patch addresses includes means for storing multiple sets of two-dimensional offset addresses, each set of offset addresses defining a different rotation angle, and wherein each reference patch is compared with each possible patch of the subject image at multiple orientation angles.

6. A fingerprint feature correlator for high-speed verification of a person'"'"'s identity, comprising:

a fingerprint sensor, for generating a digital image of a fingerprint;

an enrollment processor for extracting, from a fingerprint image generated by the fingerprint sensor from the fingerprint of an identified person, multiple reference patches that together uniquely identify the image, each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

reference image storage means, for storing reference patch images and locations provided by the enrollment processor;

a correlation processor, for searching an entire subject fingerprint image generated by the fingerprint sensor from the fingerprint of a person seeking identity verification, for instances of pixel patterns similar to the stored reference patch images, and for generating a set of candidate match locations in the subject image; and

a geometric constraint checking processor, for attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy, and for determining whether there is a match between the subject image and the stored reference image;

wherein the correlation processor includes

an array of correlator units, each for comparing a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

an address generator, for generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image; and

a result collection memory, for recording pixel match count

data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image;

and wherein each correlator unit includes a counter for recording a count indicative of the degree of match between a reference patch and a patch of the subject image, and the correlation processor further includes means for saving the contents of the counters in the result collection memory on completion of a comparison of all pixels in the reference patches, and means for saving a subject image location with each count, and means for resetting the counters to begin a comparison with other locations in the subject image;

and wherein the correlation processor further includes means rendered operative at the conclusion of all matching operations of the correlation processor, for selecting a set of match candidates from the results saved in the result collection memory.

8. A method for verifying a person'"'"'s identity using fingerprint feature correlation, the method comprising the steps of:

sensing a fingerprint of an identified person wanting to enroll a fingerprint image;

generating a digital image of the fingerprint;

enrolling the fingerprint image, by finding and extracting multiple reference patches that together uniquely identify the image, each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

storing the extracted reference patch images and their locations in a reference image memory;

sensing a subject fingerprint image of a person wanting identity verification;

generating a digital subject fingerprint image from the sensed subject fingerprint image;

searching the entire subject fingerprint image for instances of pixel patterns similar to any of the stored reference patch images;

generating a set of candidate match locations in the subject image;

attempting to locate in the set of candidate match locations a subset of candidate match locations that geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy;

determining whether there is a match between the subject image and the stored reference image; and

preprocessing the digital image, by converting the digital image of the fingerprint array to binary form and to a standard orientation;

and wherein the enrolling step includes

thinning the binary image to obtain skeletal images of ridges and valleys in the fingerprint;

analyzing the skeletal images to locate bifurcation features in the ridges and valleys;

selecting reference patches based on feature density; and

extracting reference patch images from the skeletal images of the ridges and valleys.

9. A method as defined in claim 8, wherein the comparing step includes:

comparing, in a correlator unit that is one member of an array of correlator units, a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image; and

recording, in a result collection memory, pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image.

12. A method as defined in claim 9, wherein:

each step of comparing in a correlator unit includes recording a count indicative of the degree of match between a reference patch and a patch of the subject image; and

the method further comprises the steps of saving the counts in the result collection memory on completion of a comparison of all pixels in the reference patches, saving a subject image location with each count, and resetting the counts to begin a comparison with other locations in the subject image.

14. A method as defined in claim 8, wherein the step of attempting to locate in the set of match candidates a subset of match candidates that is geometrically congruent with a corresponding subset of reference patches, includes:

determining the distances between all possible pairs of reference patches;

determining the distances between all possible pairs of distinct match candidates;

selecting a feasible subset of the distinct match candidates such that the distances between all possible pairs in the feasible subset are approximately equal to the distances between corresponding pairs of reference patches; and

declaring a match based on the size of the feasible subset.

10. A method for verifying a person'"'"'s identity using fingerprint feature correlation, the method comprising the steps of:

sensing a fingerprint of an identified person wanting to enroll a fingerprint image;

generating a digital image of the fingerprint;

enrolling the fingerprint image, by finding and extracting multiple reference patches that together uniquely identify the image, each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

storing the extracted reference patch images and their locations in a reference image memory;

sensing a subject fingerprint image of a person wanting identity verification;

generating a digital subject fingerprint image from the sensed subject fingerprint image;

searching the entire subject fingerprint image for instances of pixel patterns similar to any of the stored reference patch images;

generating a set of candidate match locations in the subject image;

attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to desired degree of accuracy; and

determining whether there is a match between the subject image and the stored reference image;

wherein the comparing step includes

comparing, in a correlator unit that is one member of an array of correlator units, a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image; and

recording, in a result collection memory, pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image;

and wherein the step of generating addresses further includes generating rotated reference patch addresses in such a way that a rotated image of each reference patch is also compared with each possible patch of the subject image.

11. A method as defined in claim 10, wherein the step of generating rotated reference patch addresses includes storing multiple sets of two-dimensional offset addresses, each set of offset addresses defining a different rotation angle, and wherein each reference patch is compared with each possible patch of the subject image at multiple orientation angles.

13. A method for verifying a person'"'"'s identity using fingerprint feature correlation, the method comprising the steps of:

sensing a fingerprint of an identified person wanting to enroll a fingerprint image;

generating a digital image of the fingerprint;

enrolling the fingerprint image, by finding and extracting multiple reference patches that together uniquely identify, the image, each reference patch containing a plurality of fingerprint ridge or valley bifurcation features;

storing the extracted reference patch images and their locations in a reference image memory;

sensing a subject fingerprint image of a person wanting identity verification;

generating a digital subject fingerprint image from the sensed subject fingerprint image;

searching the entire subject fingerprint image for instances of pixel patterns similar to any of the stored reference patch images;

generating a set of candidate match locations in the subject image;

attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically conqruent with a corresponding subset of reference patch locations, to a desired degree of accuracy; and

determining whether there is a match between the subject image and the stored reference image;

wherein the comparing step includes

comparing, in a correlator unit that is one member of an array of correlator units, a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image;

generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixel in the subject image, wherein each reference patch is compared with every possible patch position in the subject image; and

recording, in a result collection memory, pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image; and

wherein

each step of comparing in a correlator unit includes recording a count indicative of the decree of match between a reference patch and a patch of the subject image; and

the method further comprises the steps of saving the counts in the result collection memory on completion of a comparison of all pixels in the reference patches, saving a subject image location with each count, and resetting the counts to begin a comparison with other locations in the subject image;

and wherein the method further comprises the step, performed at the conclusion of all matching operations, of selecting a set of match candidates from the results saved in the result collection memory.

15. A fingerprint feature correlator for high-speed verification of a person'"'"'s identity, comprising:

a fingerprint sensor, for generating a digital image of a fingerprint;

an enrollment processor for extracting, from a fingerprint image generated by the fingerprint sensor from the fingerprint of an identified person, multiple reference patches that together uniquely identify the image;

reference image storage means, for storing reference patch images and locations provided by the enrollment processor;

a correlation processor, for searching a subject fingerprint image generated by the fingerprint sensor from the fingerprint of a person seeking identity verification, for instances of pixel patterns similar to the stored reference patch images, and for generating a set of candidate match locations in the subject image; and

a geometric constraint checking processor, for attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy, and for determining whether there is a match between the subject image and the stored reference image;

wherein the correlation processor includes

an array of correlator units, each for comparing a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image,

an address generator, for generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image, and

a result collection memory, for recording pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image;

and wherein each correlator unit includes a counter for recording a count indicative of the degree of match between a reference patch and a patch of the subject image;

and wherein the correlation processor further includes means for saving the contents of the counters in the result collection memory on completion of a comparison of all pixels in the reference patches, and means for saving a subject image location with each count, and means for resetting the counters to begin a comparison with other locations in the subject image;

and wherein the correlation processor further includes means rendered operative at the conclusion of all matching operations of the correlation processor, for selecting a set of match candidates from the results saved in the result collection memory;

and wherein the means for selecting a set of match candidates includes means for discarding match candidates that are positioned in the subject image relatively close to a better candidate.

16. A method for verifying a person'"'"'s identity using fingerprint feature correlation, the method comprising the steps of:

sensing a fingerprint of an identified person wanting to enroll a fingerprint image;

generating a digital image of the fingerprint;

enrolling the fingerprint image, by finding and extracting multiple reference patches that together uniquely identify the image;

storing the extracted reference patch images and their locations in a reference image memory;

sensing a subject fingerprint image of a person wanting identity verification;

generating a digital subject fingerprint image from the sensed subject fingerprint image;

searching the subject fingerprint image for instances of pixel patterns similar to any of the stored reference patch images;

generating a set of candidate match locations in the subject image;

attempting to locate in the set of candidate match locations a subset of candidate match locations that is geometrically congruent with a corresponding subset of reference patch locations, to a desired degree of accuracy; and

determining whether there is a match between the subject image and the stored reference image;

wherein the comparing step includes

comparing, in a correlator unit that is one member of an array of correlator units, a selected pixel from a reference patch with a selected pixel in the subject image, wherein the entire array simultaneously compares the selected pixel from each of a plurality of reference patches with a plurality pixels in a block of pixels from the subject image,

generating a sequence of addresses for accessing successive pixels in the plurality of reference patches, and another sequence of addresses for accessing successive blocks of pixels in the subject image, wherein each reference patch is compared with every possible patch position in the subject image, and

recording, in a result collection memory, pixel match count data pertaining to every possible match candidate position in the subject image, along with match candidate locations in the subject image;

and wherein each step of comparing in a correlator unit includes recording a count indicative of the degree of match between a reference patch and a patch of the subject image;

and wherein the method further comprises the steps of saving the counts in the result collection memory on completion of a comparison of all pixels in the reference patches, saving a subject image location with each count, and resetting the counts to begin a comparison with other locations in the subject image;

and wherein the method further comprises the step, performed at the conclusion of all matching operations, of selecting a set of match candidates from the results saved in the result collection memory;

and wherein the step of selecting a set of match candidates includes discarding match candidates that are positioned in the subject image relatively close to a better candidate.