Automated fingerprint classification/identification system and method

• US 5,465,303 A
• Filed: 11/12/1993
• Issued: 11/07/1995
• Est. Priority Date: 11/12/1993
• Status: Expired due to Fees

• Current Assignee: Natwest Bank, NA (Bank of America Corp.), Chemical Bank (London Branch) (JP Morgan Chase & Co)
• Original Assignee: Aeroflex Systems Corp.
• Inventors: Goldberg, Paul B., Levison, Laurence L., Stanek, Scott D.
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/151,020
• Time in Patent Office: 725 Days
• Field of Search: 382/4, 382/5, 382/37, 382/36, 382/38, 283/7, 283/68, 283/69, 283/78, 356/71
• US Class Current: 382/124
• CPC Class Codes: G06V 40/1359 Extracting features related to ridge properties; Determining the fingerprint type, e.g. whorl or loop
• CPC Class Codes: G07C 9/37 using biometric data, e.g. fingerprints, iris scans or voice recognition

Abstract

An automated fingerprint classification and identification system used to determine or verify the identity of an unknown person by comparing one or more of the person'"'"'s fingerprints (i.e., the unknown fingerprints) to known fingerprints stored in a database. The components of the present invention include: (1) an apparatus and method for automatically classifying and storing the fingerprints in the database according to a lesser known manual 10-fingerprint classification method (the Vucetich classification and subclassification method), and (2) an apparatus and method for limiting the search of the database to only those fingerprints that are of the same classification as the unknown fingerprint(s). By endowing the standard automatic fingerprint identification systems with automated fingerprint classification and storage features of the present invention, the present invention reduces the amount of time required for an automated fingerprint identification system'"'"'s "matcher" (the processing unit that searches the database) to complete a database search, thus increasing the speed of the system and/or reducing the number of matchers required to obtain a desired processing speed. By using the Vucetich classification method instead of other commonly used 10-fingerprint classification methods, the efficiency gain is maximized. In practical terms, the effect of the present invention is to lower the cost of the equipment required to perform automated fingerprint searches while preserving the accuracy of state-of-the-art systems.

Claims

1. An automated fingerprint classification and identification apparatus used to determine or verify the identity of an unknown person by comparing one or more of the person'"'"'s unknown fingerprints to known fingerprints stored in a data base, the apparatus comprising:

a fingerprint input subsystem, operable to create a digitized bit-map of the unknown fingerprint and to store said bit-map in a memory of said fingerprint subsystem;

a template creation subsystem, coupled to said fingerprint input subsystem, operable to receive said bit-map of said unknown fingerprint and to create a digitized template based on locations of minutiae points in said bit-map;

a classification subsystem, coupled to said fingerprint input subsystem and said template creation subsystem, operable to receive said bit-map and said template and to assign said unknown fingerprint to a primary Vucetich category based on visually distinct patterns present in said bit-map and digital information extracted from said template, said classification subsystem includes,

(a) means for determining a central feature of said unknown fingerprint, wherein said central feature is the innermost point of said unknown fingerprint;

(b) means for creating a bounding rectangle around said central feature;

(c) means for determining whether said central feature is within a first valley, and if not, then moving said central feature upward until it is within said first valley;

(d) means for generating a colored area by applying a floodfill algorithm to said unknown fingerprint in order to fill in said first valley and at least one valley adjacent to said first valley;

(e) means for classifying said unknown fingerprint as a whorl if said colored area does not touch the border of said bounding rectangle or if said colored area touches the border of said bounding rectangle and at least half of said colored area is above said central feature;

(f) means for classifying said unknown fingerprint as an arch if said colored area touches both sides of said bounding rectangle and approximately half of said colored area is right of said central feature and half of said colored area is left of said central feature; and

(g) means for classifying said unknown fingerprint as a loop if said colored area touches only one side of said bounding rectangle, wherein said loop in an inside loop if said colored area is weighted on said left side and said loop in an external loop if said colored area is weighted on said right side;

an image storage subsystem, coupled to said classification subsystem, said template creation subsystem, and said fingerprint input subsystem, operable to store said bit-map and said template in memory locations that correspond to the primary Vucetich category and also to store known bit-maps and templates of known bit-maps in memory locations that correspond to the primary Vucetich category; and

a search subsystem, coupled to the image storage subsystem, operable to compare said template of said unknown fingerprint to templates of said known fingerprints that are of the same primary Vucetich category as said unknown fingerprint, and to produce a result indicating a probability that said unknown fingerprint is identical to one of said known fingerprints.

2. The apparatus of claim 1, further comprising a user interface subsystem, coupled to said search subsystem and to said image storage subsystem, operable to display said digital result to a human operator.

3. The apparatus of claim 1, wherein the image storage subsystem further comprises memory locations which correspond to subcategories of said primary Vucetich category.

4. The apparatus of claim 1, wherein said primary Vucetich category is one of a plurality of primary Vucetich categories including:

an arch fingerprint category, an internal loop fingerprint category, an external loop fingerprint category, and a whorl fingerprint category.

5. The apparatus of claim 3, wherein said subcategories are visually distinct patterns present in said primary Vucetich category.

10. The system of claim 1, wherein said digitized template contains a plurality of minutiae points, wherein if said digitize template does not contain a certain threshold number of said minutiae points, a user is allowed to edit said template to add additional minutiae points to said digitized template.

11. The system of claim 1, further comprising means for automatically determining which subcategory of the Vucetich fingerprint classification system the unknown fingerprint corresponds.

13. The system of claim 1, wherein said generating means applies said floodfill algorithm to said unknown fingerprint to said first valley and at least two valleys adjacent to said first valley.

6. In an automated fingerprint classification and identification system for determining or verifying the identity of an unknown person by comparing one or more of the person'"'"'s unknown fingerprints to known fingerprints stored in a database, a method comprising the steps of:

storing the known fingerprints in the data base, having a plurality of memory locations, each one of said memory locations correspond to a primary category of a fingerprint classification system, wherein said fingerprint classification system is a Vucetich fingerprint classification system;

receiving one of the unknown fingerprints;

automatically determining to which primary category of the Vucetich fingerprint classification system the unknown fingerprint corresponds, wherein said Vucetich fingerprint classification system has four primary categories, wherein said automatically determining step includes the steps of,

(a) determining a central feature of said unknown fingerprint, wherein said central feature is the innermost point of said unknown fingerprint;

(b) creating a bounding rectangle around said central feature;

(c) determining whether said central feature is within a first valley, and if not, then moving said central feature upward until it is within said first valley;

(d) generating a colored area by applying a floodfill algorithm to said unknown fingerprint in order to fill in said first valley and at least one valley adjacent to said first valley;

(e) classifying said unknown fingerprint as a whorl if said colored area does not touch the border of said bounding rectangle or if said colored area touches the border of said bounding rectangle and at least half of said colored area is above said central feature;

(f) classifying said unknown fingerprint as an arch if said colored area touches both sides of said bounding rectangle and approximately half of said colored area is right of said central feature and half of said colored area is left of said central feature; and

(g) classifying said unknown fingerprint as a loop if said colored area touches only one side of said bounding rectangle, Wherein said loop in an inside loop if said colored area is weighted on said left side and said loop in an external loop if said colored area is weighted on said right side;

comparing said unknown fingerprint to said known fingerprints of said data base that are of the same Vucetich classification primary category as the unknown fingerprint indicated by said automatically determining step; and

determining whether a match exists between said unknown fingerprint and one of the known fingerprints of the same Vucetich classification primary category.

7. The method of claim 6, wherein the data base further comprises memory locations which correspond to subcategories of at least one of said primary categories of the Vucetich fingerprint classification.

8. The method of claim 6, wherein said primary categories of said Vucetich fingerprint classification system include an arch fingerprint category, an internal loop fingerprint category, an external loop fingerprint category, and a whorl fingerprint category.

9. The apparatus of claim 7, wherein said subcategories are visually distinct patterns present in said primary Vucetich fingerprint classification system.

12. The method of claim 6, further comprising the step of automatically determining which subcategory of the Vucetich fingerprint classification system the unknown fingerprint corresponds.

14. The method of claim 6, wherein said step of generating a colored area applies said floodfill algorithm to said unknown fingerprint to said first valley and at least two valleys adjacent to said first valley.