Patent US5631972A successfully refreshed from Google Patents.
US5631972A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hyperladder fingerprint matcher
Assignee: Individual
•
Filing: 1995-05-04
•
Granted: 1997-05-20
•
Expires: 2015-05-04
Abstract
Abstract A fingerprint matcher links together minutiae from a search print and minutiae from a file print in a chain to determine if the two prints match. Minutiae are extracted from the images of the search and file prints. Geometric and other relationships between close minutiae in each print are calculated. A table of candidate "steps" is formed. Each step consists of four minutiae, two close search minutiae and two close file minutiae. Each "rung" of the step is a search-file pair, the candidate mating of presumed identical minutiae in the two images. Each "riser" of the step is formed by two close minutiae, search minutiae on the one side and file minutiae on the other. A candidate step is entered into the table if and only if the relationships between search minutiae are similar to those between file minutiae. The number of candidate steps is reduced by requiring that each step adhere to various rules regarding the presence of other steps in the table and the identity of minutiae therein. Maximally long chains of steps are formed which are called "hyperladders", each of which links together surviving steps. The hyperladders are said to be "hyper" because at each search-file pair rung a multiplicity of "riser" pairs may emerge, each to another and different search-file pair "rung". Within the largest hyperladder formed from a given search-file pair of prints the number of links is a measure of the likelihood that the search and file fingerprints are the same, and an indication of a match is returned if the number of links exceeds a predetermined threshold value.
Inventors
- 👤 Stephen Ferris
- 👤 Robert L. Powers
- 👤 Terry Lindh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 22:46
CPC Classifications
G; G06; G06V; G06V40/00; G06V40/10; G06V40/12; G06V40/1365
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
200 words
An apparatus for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising: means for convening a fingerprint to a list of minutiae descriptive of the fingerprint; means for comparing the minutiae of a search fingerprint to the minutiae of one of the plurality of file fingerprints; means for pairing a first of the minutiae of the search fingerprint to a second of the minutiae of the search fingerprint if the attributes of the first and second search minutiae are related within predetermined limits; means for pairing a first of the minutiae Of the file fingerprint to a second of the minutiae of the file fingerprint if the attributes of the first and second file minutiae are related within predetermined limits: means for mating one of the pairs of minutiae of the search fingerprint to one of the pairs of minutiae of the file fingerprint if the attributes of the search pair and the file pair are substantially similar within predetermined limits; means for linking the mated pairs into a chain; and means for indicating a match if the number of links in the chain exceeds a predetermined upper threshold value.
Claim 2
Independent Claim
200 words
An apparatus for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising: means for convening a fingerprint to a list of minutiae descriptive of the fingerprint; means for comparing the minutiae of a search fingerprint to the minutiae of one of the plurality of file fingerprints; means for pairing a first of the minutiae of the search fingerprint to a second of the minutiae of the search fingerprint if the attributes of the first and second search minutiae are related within predetermined limits; means for pairing a first of the minutiae Of the file fingerprint to a second of the minutiae of the file fingerprint if the attributes of the first and second file minutiae are related within predetermined limits: means for mating one of the pairs of minutiae of the search fingerprint to one of the pairs of minutiae of the file fingerprint if the attributes of the search pair and the file pair are substantially similar within predetermined limits; means for linking the mated pairs into a chain; and means for indicating a match if the number of links in the chain exceeds a predetermined upper threshold value.
Claim 3
Dependent Claim
89 words
The apparatus of claim 1 wherein the means for pairing the search minutiae pairs the first and second search minutiae when the first and second search minutiae are in proximity to each other according to their relative positions, wherein the means for pairing the file minutiae pairs the first and second file minutiae when the first and second file minutiae are in proximity to each other according to their relative positions, and wherein the apparatus further comprises means for storing the paired search minutiae and the paired file minutiae.
Claim 4
Dependent Claim
36 words
The apparatus of claim 2 wherein the means for pairing the search minutiae and the means for pairing the file minutiae each relate the pair of minutiae to each other using information local to the minutiae.
Claim 5
Dependent Claim
12 words
The apparatus of claim 3 wherein the local information comprises topological information.
Claim 6
Dependent Claim
19 words
The apparatus of claim 4 wherein the local topological information comprises a count of the ridges separating the pair.
Claim 7
Dependent Claim
13 words
The apparatus of claim 4 wherein the local information further comprises spatial information.
Claim 8
Dependent Claim
278 words
The apparatus of claim 2 wherein each of the means for comparing the minutiae comprises: means for comparing the attributes of the paired minutia of the search fingerprint against the attributes of the paired minutia of one of the file fingerprints; means for measuring a first radial distance from the first search minutia to the second search minutia and for measuring a second radial distance from the first file minutia to the second file minutia; means for measuring a first angular separation of the first search minutia to the second search minutia, and for measuring a second angular separation of the first file minutia to the second file minutia; means for measuring a first orientation angle of the second search minutia with respect to a reference frame of the first search minutia, and for measuring a second orientation angle of the second file minutia with respect to a reference frame of the first file minutia; means for counting a first number of ridges separating the first search minutia and the second search minutia and for counting a second number of ridges separating the first file minutia and the second file minutia; and means for mating the first search minutia with the first file minutia if: the difference between the first radial distance and the second radial distance is within a first predetermined tolerance; the difference between the first angular separation and the second angular separation is within a second predetermined tolerance; the difference between the first orientation and the second orientation is within a third predetermined tolerance; and the difference between the first number of ridges and the second number of ridges is within a fourth predetermined tolerance.
Claim 9
Dependent Claim
37 words
The apparatus of claim 2 further comprising: a table for storing the search pairs and the file pairs; removing a search pair form the table if no corresponding file pairs of minutiae are stored in the table.
Claim 10
Dependent Claim
29 words
The apparatus of claim 1 wherein each of the means for pairing the minutiae comprises means for relating the paired minutiae to each other using a plurality of measurements.
Claim 11
Dependent Claim
24 words
The apparatus of claim 1 further comprising means for storing a large number of the minutiae representative of the file fingerprints in the database.
Claim 12
Dependent Claim
27 words
The apparatus of claim 1 further comprising means for indicating no match if the number of links in the chain is below a predetermined lower threshold value.
Claim 13
Dependent Claim
33 words
The apparatus of claim 1 wherein the means for linking the mated pairs into a chain comprises means for linking mated minutiae to other mated minutiae to form a chain of mated minutiae.
Claim 14
Dependent Claim
66 words
The apparatus of claim 1 further comprising means for forming a chained ladder structure of linked, paired minutiae, the ladder structure having at least one rung and at lease two risers, wherein: each rung of the ladder comprises mated search and file minutiae; one of the risers of the ladder comprises paired search minutiae; and another of the risers of the ladder comprises paired file minutiae.
Claim 15
Dependent Claim
180 words
The apparatus of claim 1 further comprising: means for storing the paired minutiae into a table of quadrant pairs; means for storing the mated pairs in a table; means for building a step from each of the mated pairs stored in the table if the attributes of the mated pairs are substantially similar within predetermined limits; means for linking a plurality of the steps together in a chained ladder structure of the steps, each step having at least one rung and at least two risers, wherein each rung of the ladder comprises mated search and file minutiae, one of the risers of the ladder comprises paired search minutiae, and another of the risers of the ladder comprises paired file minutiae; means for storing each chained ladder structure; means for eliminating any chained ladder structure that is a subset of a larger chained ladder structure; means for counting the number of links in each ladder structure; and means for indicating a match of the search fingerprint and the file fingerprint if the number of links exceeds a predetermined upper threshold value.
Claim 16
Dependent Claim
20 words
The apparatus of claim 14 wherein each rung of the ladder structure may be common to another stored ladder structure.
Claim 17
Dependent Claim
23 words
The apparatus of claim 15 further comprising means for evaluating the compatibility of the steps and for inhibiting the chaining of incompatible steps.
Claim 18
Dependent Claim
40 words
The apparatus of claim 15 further comprising means for sorting the chained ladder structures according to the number of total links in the chain and for determining whether the number of links is greater than the predetermined upper threshold value.
Claim 19
Independent Claim
189 words
A method for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising the steps of: converting a fingerprint to a plurality of minutiae descriptive of the fingerprint; comparing the minutiae of a search fingerprint to the minutiae of one of the plurality of file fingerprints; pairing a first of the minutiae of the search fingerprint to a second of the minutiae of the search fingerprint if the attributes of the first and second search minutiae are related within predetermined limits; pairing a first of the minutiae of the file fingerprint to a second of the minutiae of the file fingerprint if the attributes of the first and second file minutiae are related Within predetermined limits; mating one of the pairs of minutiae of the search fingerprint to one of the pairs of minutiae of the file fingerprint if the attributes of the search pair and the file pair are substantially similar within predetermined limits; linking the mated pairs into a chain; and indicating a match if the number of links in the chain exceeds a predetermined upper threshold value.
Claim 20
Independent Claim
189 words
A method for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising the steps of: converting a fingerprint to a plurality of minutiae descriptive of the fingerprint; comparing the minutiae of a search fingerprint to the minutiae of one of the plurality of file fingerprints; pairing a first of the minutiae of the search fingerprint to a second of the minutiae of the search fingerprint if the attributes of the first and second search minutiae are related within predetermined limits; pairing a first of the minutiae of the file fingerprint to a second of the minutiae of the file fingerprint if the attributes of the first and second file minutiae are related Within predetermined limits; mating one of the pairs of minutiae of the search fingerprint to one of the pairs of minutiae of the file fingerprint if the attributes of the search pair and the file pair are substantially similar within predetermined limits; linking the mated pairs into a chain; and indicating a match if the number of links in the chain exceeds a predetermined upper threshold value.
Claim 21
Dependent Claim
71 words
The method of claim 18 further comprising the steps of: pairing the first and second search minutiae when the first and second search minutiae are in proximity to each other according to their relative positions; pairing the first and second file minutiae when the first and second file minutiae are in proximity to each other according to their relative positions; and storing the paired search minutiae and the paired file minutiae.
Claim 22
Dependent Claim
48 words
The method of claim 19 wherein further comprising the steps of: storing the paired file minutiae into a table; eliminating a particular paired file minutiae from the table if other corresponding paired file minutiae within the table do not confirm the validity of the particular paired file minutiae.
Claim 23
Dependent Claim
249 words
The method of claim 19 wherein the step of comparing the minutiae comprises: measuring a first radial distance from the first search minutia to the second search minutia to the second file minutia; measuring a first angular separation of the first search minutia to the second search minutia, and for measuring a second angular separation of the first file minutia to the second file minutia; measuring a first orientation angle of the second search minutia with respect to a reference frame of the first search minutia, and for measuring a second orientation angle of the second file minutia with respect to a reference frame of the first file minutia; counting a first number of ridges separating the first search minutia and the second search minutia and counting a second number of ridges separating the first file minutia and the second file minutia; and wherein the step of mating One of the pairs of search minutiae to one of the pairs of the file minutiae includes mating the first search minutia with the first file minutia if: the difference between the first radial distance and the second radial distance is within a first predetermined tolerance; the difference between the first angular separation and the second angular separation is within a second predetermined tolerance; the difference between the first orientation and the second orientation is within a third predetermined tolerance; and the difference between the first number of ridges and the second number of ridges is within a fourth predetermined tolerance.
Claim 24
Dependent Claim
69 words
The method of claim 19 wherein the paired minutiae corresponding to the search fingerprint comprises a search pair and wherein the paired minutiae corresponding to the file fingerprint comprises a file pair, the method further comprising the steps of: storing the search pairs and the file pairs in a table; removing a search pair from the table if no corresponding file pairs of minutiae are stored in the table.
Claim 25
Dependent Claim
22 words
The method of claim 18 further comprising the step of linking together mated minutiae to other mated minutiae to form a chain.
Claim 26
Dependent Claim
73 words
The method of claim 18 wherein the step of mating the minutiae includes the step of forming a chained ladder structure of linked, paired minutiae, the ladder structure having at least one rung and at least tow risers, wherein: each rung of the ladder comprises mated search and file minutiae; one of the risers of the ladder comprises paired search minutiae; and another of the risers of the ladder comprises paired file minutiae.
Claim 27
Dependent Claim
165 words
The method of claim 18 further comprising the steps of: storing the paired minutiae into a table of quadrant pairs; mating the paired search minutiae with the paired file minutiae; storing the mated pairs in a mates table; building a step from each of the mated pairs stored in the mates table if the attributes of the mated pairs are substantially similar within predetermined limits; wherein the step of linking the minutiae comprises linking a plurality of the steps together in a chained ladder structure of the steps, each step having at least one rung and at least two risers, wherein each rung of the ladder comprises mated search and file minutiae, one of the risers of the ladder comprises paired search minutiae, and another of the risers of the ladder comprises paired file minutiae; storing each chained ladder structure; eliminating any chained ladder structure that is a subset of a larger chained ladder structure; and counting the number of links in each ladder structure.
Claim 28
Dependent Claim
20 words
The method of claim 25 wherein each rung of the ladder structure may be common to another stored ladder structure.
Claim 29
Dependent Claim
23 words
The method of claim 25 further comprising the steps of: evaluating the compatibility of the steps; and inhibiting the chaining of incompatible steps.
Claim 30
Dependent Claim
40 words
The method of claim 25 further comprising the steps of: sorting the chained ladder structures according to the number of total links in the chain; and determining whether the number of links is greater than the predetermined upper threshold value.
Claim 31
Independent Claim
446 words
A method for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising the steps of: providing a plurality of search minutiae descriptive of the search fingerprint; providing a plurality of file minutiae descriptive of the file fingerprint; pairing the search minutiae that are in proximity to each other according to their relative positions based on information local to the search minutiae; mating the paired search minutiae comprising a first search minutia and a second search minutia with corresponding paired file minutiae comprising a first file minutia and a second file minutia, the mating comprising the steps of: measuring a first radial distance from the first search minutia to the second search minutia and for measuring a second radial distance from the first file minutia to the second file minutia; measuring a first angular separation of the first search minutia to the second search minutia, and for measuring a second angular separation of the first file minutia to the second file minutia; measuring a first orientation angle of the second search minutia with respect to a reference frame of the first search minutia, and for measuring a second orientation angle of the second file minutia with respect to a reference frame of the first file minutia; counting a first number of ridges separating the first search minutia and the second search minutia and for counting a second number of ridges separating the first file minutia and the second file minutia; mating the first search minutia with the first file minutia if: the difference between the first radial distance and the second radial distance is within a first predetermined tolerance; the difference between the first angular separation and the second angular separation is within a second predetermined tolerance; the difference between the first orientation and the second orientation is within a third predetermined tolerance; and the difference between the first number of ridges and the second number of ridges is within a fourth predetermined tolerance; building a step from each of the mated pairs, each step having at least one rung and at least two risers, wherein each rung of the ladder comprises mated search and file minutiae, one of the risers of the ladder comprises paired search minutiae, and another of the risers of the ladder comprises paired file minutiae; placing each step in a ladder table, and linking each step to steps already linked together in the ladder table if the attributes of the steps are compatible, thereby forming a plurality of chained ladder structures; indicating a match if the number of links in any of the chained ladder structures exceeds a predetermined upper threshold value.
Claim 32
Independent Claim
446 words
A method for determining whether a search fingerprint matches any of a plurality of file fingerprints stored in an electronic database, comprising the steps of: providing a plurality of search minutiae descriptive of the search fingerprint; providing a plurality of file minutiae descriptive of the file fingerprint; pairing the search minutiae that are in proximity to each other according to their relative positions based on information local to the search minutiae; mating the paired search minutiae comprising a first search minutia and a second search minutia with corresponding paired file minutiae comprising a first file minutia and a second file minutia, the mating comprising the steps of: measuring a first radial distance from the first search minutia to the second search minutia and for measuring a second radial distance from the first file minutia to the second file minutia; measuring a first angular separation of the first search minutia to the second search minutia, and for measuring a second angular separation of the first file minutia to the second file minutia; measuring a first orientation angle of the second search minutia with respect to a reference frame of the first search minutia, and for measuring a second orientation angle of the second file minutia with respect to a reference frame of the first file minutia; counting a first number of ridges separating the first search minutia and the second search minutia and for counting a second number of ridges separating the first file minutia and the second file minutia; mating the first search minutia with the first file minutia if: the difference between the first radial distance and the second radial distance is within a first predetermined tolerance; the difference between the first angular separation and the second angular separation is within a second predetermined tolerance; the difference between the first orientation and the second orientation is within a third predetermined tolerance; and the difference between the first number of ridges and the second number of ridges is within a fourth predetermined tolerance; building a step from each of the mated pairs, each step having at least one rung and at least two risers, wherein each rung of the ladder comprises mated search and file minutiae, one of the risers of the ladder comprises paired search minutiae, and another of the risers of the ladder comprises paired file minutiae; placing each step in a ladder table, and linking each step to steps already linked together in the ladder table if the attributes of the steps are compatible, thereby forming a plurality of chained ladder structures; indicating a match if the number of links in any of the chained ladder structures exceeds a predetermined upper threshold value.
Claim 33
Dependent Claim
37 words
The method of claim 29 further comprising the steps of: sorting the plurality of chained ladder structures according to the number of links; and deleting any chained ladder structures that are subsets of larger chained ladder structures.
Claim 34
Dependent Claim
22 words
The method of claim 29 further comprising the step of resolving conflicts between steps if the attributes of the steps are incompatible.
References Cited (Backward Citations)
US3893080A
Cited
US4185270A
Cited
US4135147A
Cited
US4752966A
Cited
US4646352A
Cited
US4525859A
Cited
US4944021A
Cited
US4747147A
Cited
US5187747A
Cited
US5321765A
Cited
US4817183A
Cited
US4790564A
Cited
US4896363A
Cited
US5109428A
Cited
US5105467A
Cited
US5177792A
Cited
US5267324A
Cited
US5239590A
Cited
US5351304A
Cited
US5420937A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-19 | 2000-11-18 | 2001-05-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-19 | 2004-11-18 | 2005-05-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-19 | 2008-11-18 | 2009-05-20 | $7700.00 | Window Closed / Lapsed |