Image analysis – Applications – Personnel identification
Reexamination Certificate
1999-12-22
2001-01-30
Boudreau, Leo H. (Department: 2721)
Image analysis
Applications
Personnel identification
C707S793000, C707S793000
Reexamination Certificate
active
06181807
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of fingerprint processing, and, more particularly, to the field of efficiently searching for a fingerprint match in a relatively large database of fingerprints.
BACKGROUND OF THE INVENTION
Fingerprint matching is a reliable and widely used technique for personal identification or verification. In particular, a common approach to fingerprint identification involves scanning a sample fingerprint or an image thereof, converting it into electrical signals, and storing the image and/or unique characteristics of the fingerprint image. The characteristics of a sample fingerprint may be compared to information for reference fingerprints already in storage to determine identification or for verification purposes.
Unfortunately, comparing a sample fingerprint to a large number of reference fingerprints may be prohibitively expensive and/or simply take too long. Accordingly, fingerprints are typically classified into a plurality of discrete sets and/or subsets in the form of a hierarchical tree to thereby expedite searching. For example, a common top level classification for fingerprints usually differentiates the prints into the classes of: plain whorl, plain loop, tented arch, etc. based upon broad ridge pattern types. These classes may be yet further divided into subclasses. Accordingly, a fingerprint sample to be searched, once itself classified, can be more efficiently compared to only those prints in the respective classes and subclasses of the search tree. For example, U.S. Pat. No. 5,465,303 to Levison et al. describes both the widely used Henry classification system and the Vucetich classification system.
The conventional classification approaches may result in binning of fingerprint types or classifications, wherein a single bin is searched for the matching print. Unfortunately, the bins may still be relatively large thus resulting in lengthy and expensive searching. Moreover, a print is considered either in one bin or another and there is no consideration given to any uncertainty in whether the print is in one bin or another. In other words, there is typically no relation between adjacent bins that would assist in searching. Any degradation in the print quality may also result in it being simply in the wrong bin and thus unmatchable.
When the quality of the original copy of a fingerprint is bad, the print may contain many local distortions of the ridge pattern which may result in incorrect orientation of the fingerprint. U.S. Pat. No. 5,140,642 to Hsu et al. is directed to a method for determining the actual position of a core point of a fingerprint based upon finding ridge flows and assigning a direction code, correcting the ridge flows, and allocating the core point based upon the corrected direction codes. Along these lines, U.S. Pat. No. 5,040,224 to Hara discloses an approach to preprocessing fingerprints to correctly determine a position of the core of each fingerprint image for later matching by minutiae patterns.
Fingerprint minutiae, the branches or bifurcations and end points of the fingerprint ridges, are often used to determine a match between a sample print and a reference print database. For example, U.S. Pat. Nos. 3,859,633 and 3,893,080 both to Ho et al. are directed to fingerprint identification based upon fingerprint minutiae matching.
U.S. Pat. No. 3,959,884 to Jordan et al. discloses a method of classifying fingerprints by converting a fingerprint to a pattern of binary values which define a spatial array of ridges and valleys. A part of the pattern is selected for transformation by a repeatable criteria, such as a circular area having its center at the average center of curvature of the circular ridges of the upper part of the print. The data represented by the selected part is transformed into a plot of a relative position/intensity surface with a predetermined set of first and second coordinates and a variable third coordinate having a value dependent upon the frequency of occurrence of ridges when the origin of the first and second coordinates is taken at multiple positions over the selected area. The surface is divided into multiple areas, the number of areas being equal to the desired number of code elements in a descriptor code to be constructed. The curvature of the surface within each area is preferably quantized to produce the number of code elements. Finally, a descriptor code is constructed by concatenating the code elements in a predetermined order.
U.S. Pat. No. 4,151,512 to Riganati et al. describes a fingerprint classification method using extracted ridge contour data. The ridge flow in the fingerprint pattern and minutiae data are identified and extracted from a fingerprint pattern. Topological data, identifying singularity points such as tri-radii and cores, as well as ridge flow line tracings related to those points are extracted from the ridge contour data. The extracted information is used to automatically perform classification of the fingerprint patterns and/or matching of the fingerprint pattern with patterns stored in a mass file. Classification can be positively determined with a high degree of certainty or alternatively a priority listing of probable classification types can be determined when the classification is made with a low degree of certainty. Where a priority listing is produced, successive bins of the main file are searched in succession according to the priority listing of the probable classification types. When a particular classification type is selected, the extracted minutiae data is then compared with the minutiae data of each of the stored prints within the corresponding particular classification bin of the main file.
U.S. Pat. No. 4,185,270 to Fischer II et al. discloses a process for encoding and verification also based upon minutiae. U.S. Pat. No. 4,210,899 to Swonger et al. discloses an optical scanning fingerprint reader cooperating with a central processing station for a secure access application such as admitting a person to a location or provide access to a computer terminal. U.S. Pat. No. 4,525,859 to Bowles is also directed to minutiae matching and describes a system including, among other things, signal producing means for producing an electrical signal for each point on a matrix of points; and first, second and third determining means operating on subarrays of matrix points. U.S. Pat. No. 4,947,443 Costello discloses a method for verifying the identity of a person using four characteristics from among the six characteristics. The patent also discusses encoding a credit card, bank card, or other document with a code representing a person's fingerprint. upon specific dispersion, mean, and cross-correlation calculations.
Despite a proliferation of attempted fingerprint classification and automated searching approaches, there still exists a need for reliable and efficient automated fingerprint data storage and matching.
SUMMARY OF THE INVENTION
In view of the foregoing background, it is therefore an object of the present invention to provide a method and apparatus for permitting efficient searching of a relatively large database of reference fingerprints.
It is another object of the present invention to provide a method and apparatus for permitting efficient searching of a relatively large database of fingerprints where some of the fingerprints may have degraded quality.
These and other objects, advantages and features in accordance with the present invention are provided by a method for indexing and searching a plurality of reference fingerprints to determine if a sample fingerprint matches one of the reference fingerprints. In one embodiment, the method preferably comprises the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon characteristics of the fingerprints and with the index values being generally evenly distributed and continuous over a relatively large population of individuals; selecting a first subset of the reference fingerprints having index values within a first ra
Boss Mark E.
Schmitt John C.
Setlak Dale R.
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
AuthenTec, Inc.
Boudreau Leo H.
Werner Brian P.
LandOfFree
Methods and related apparatus for fingerprint indexing and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and related apparatus for fingerprint indexing and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and related apparatus for fingerprint indexing and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2519914