Patent US5841888A successfully refreshed from Google Patents.
← Back to Patent Explorer
US5841888A Expired / Lapsed US ⏱️ 0.0 years remaining

Method for fingerprint indexing and searching

Assignee: Apple Inc
•
Filing: 1996-01-23
•
Granted: 1998-11-24
•
Expires: 2016-01-23
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract A method for indexing and searching a plurality of reference fingerprints to determine if a sample fingerprint matches one of the reference fingerprints includes 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 in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints. The step of determining index values for the reference fingerprints and the sample fingerprint preferably comprises determining same based upon ridge flow curvature of the fingerprints. The step of selecting the first subset of reference fingerprints preferably comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset. Apparatus aspects of the invention are also disclosed.

Inventors

  • 👤 Dale R. Setlak
  • 👤 John C. Schmitt
  • 👤 Mark E. Boss

Bibliographic Details

Application Number —
Jurisdiction US
Data Source google_patents
Last Synchronized 2026-11-09 15:04
CPC Classifications
A; A61; A61B; A61B5/00; A61B5/117; A61B5/1171; A61B5/1172; G; G06; G06V; G06V40/00; G06V40/10; G06V40/12; G06V40/1347; G06V40/1365; G06V40/16; G06V40/168; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936; Y10S707/99937

Claims Analysis

Total Claims: 58
Claim 1
Independent Claim 182 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon ridge flow characteristics of the fingerprints wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the ridge flow fingerprint characteristics of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function within a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints.
Claim 2
Independent Claim 182 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon ridge flow characteristics of the fingerprints wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the ridge flow fingerprint characteristics of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function within a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints and without comparing the sample fingerprint to all of the reference fingerprints.
Claim 3
Dependent Claim 32 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining same based upon ridge flow curvature of the fingerprints.
Claim 4
Dependent Claim 62 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center for each fingerprint; selecting a predetermined portion of each fingerprint relative to a center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 5
Dependent Claim 27 words
A method according to claim 3 wherein the step of selecting a predetermined portion of each fingerprint comprises selecting a generally annularly shaped portion of each fingerprint.
Claim 6
Dependent Claim 38 words
A method according to claim 1 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 7
Dependent Claim 43 words
A method according to claim 1 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 8
Dependent Claim 57 words
A method according to claim 1 further comprising the step of selecting a second subset of reference fingerprints having index values along the generally continuous and generally monotonically varying function within a second range larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 9
Dependent Claim 39 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 10
Dependent Claim 40 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 11
Dependent Claim 36 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 12
Dependent Claim 37 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from fingerprint information developed for the comparing step.
Claim 13
Dependent Claim 31 words
A method according to claim 1 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be at least one-dimensional.
Claim 14
Dependent Claim 33 words
A method according to claim 1 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of ridge flow characteristics.
Claim 15
Independent Claim 203 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith a curliness index value based upon an aggregate of a rate of change of ridge direction vectors, the method comprising the steps of: determining a curliness index value for the sample fingerprint based upon an aggregate of a rate of change of ridge direction vectors of the sample fingerprint wherein the index values are both generally evenly distributed over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the aggregate of a rate of change of ridge direction vectors of fingerprints of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having curliness index values along the generally even distribution in a first range relative to the curliness index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 16
Independent Claim 203 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith a curliness index value based upon an aggregate of a rate of change of ridge direction vectors, the method comprising the steps of: determining a curliness index value for the sample fingerprint based upon an aggregate of a rate of change of ridge direction vectors of the sample fingerprint wherein the index values are both generally evenly distributed over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the aggregate of a rate of change of ridge direction vectors of fingerprints of the selected relatively large population of individuals; selecting a first subset of the reference fingerprints having curliness index values along the generally even distribution in a first range relative to the curliness index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 17
Dependent Claim 63 words
A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises the steps of: determining a center of the sample fingerprint; selecting a predetermined portion of the sample fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.
Claim 18
Dependent Claim 26 words
A method according to claim 15 wherein the step of selecting a predetermined portion of the sample fingerprint comprises selecting a generally annularly shaped portion thereof.
Claim 19
Dependent Claim 38 words
A method according to claim 14 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 20
Dependent Claim 43 words
A method according to claim 14 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 21
Dependent Claim 53 words
A method according to claim 14 further comprising the step of selecting a second subset of reference fingerprints along the generally even distribution having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 22
Dependent Claim 29 words
A method according to claim 14 wherein the step of determining a curliness index value for the sample fingerprint comprises determining such index value to be at least one-dimensional.
Claim 23
Dependent Claim 41 words
A method according to claim 14 wherein the step of comparing comprises comparing the sample fingerprint to the reference fingerprints in the first subset based upon fingerprint characteristics independent of an aggregate of a rate of change of ridge direction vectors.
Claim 24
Independent Claim 171 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 25
Independent Claim 171 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 26
Dependent Claim 39 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 27
Dependent Claim 40 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 28
Dependent Claim 36 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.
Claim 29
Dependent Claim 36 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 30
Dependent Claim 38 words
A method according to claim 22 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 31
Dependent Claim 43 words
A method according to claim 22 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 32
Dependent Claim 57 words
A method according to claim 22 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 33
Dependent Claim 34 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 34
Dependent Claim 62 words
A method according to claim 22 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 35
Independent Claim 129 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals, the method comprising the steps of: determining respective index values for the reference fingerprints and a sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; and selecting for searching a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint.
Claim 36
Independent Claim 129 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals, the method comprising the steps of: determining respective index values for the reference fingerprints and a sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index values to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic of the relatively large population of individuals; and selecting for searching a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint.
Claim 37
Dependent Claim 39 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 38
Dependent Claim 40 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 39
Dependent Claim 36 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 40
Dependent Claim 38 words
A method according to claim 32 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 41
Dependent Claim 34 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 42
Dependent Claim 62 words
A method according to claim 32 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.
Claim 43
Independent Claim 194 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith an index value based upon at least one predetermined fingerprint characteristic wherein the index values for the reference and sample fingerprints are both generally evenly distributed and continuous over the relatively large population of individuals and wherein the reference index values are sorted to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals, the method comprising the steps of: determining the index value for the sample fingerprint based upon the at least one predetermined fingerprint characteristic; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 44
Independent Claim 194 words
A method for searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, each of the reference fingerprints having associated therewith an index value based upon at least one predetermined fingerprint characteristic wherein the index values for the reference and sample fingerprints are both generally evenly distributed and continuous over the relatively large population of individuals and wherein the reference index values are sorted to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals, the method comprising the steps of: determining the index value for the sample fingerprint based upon the at least one predetermined fingerprint characteristic; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 45
Dependent Claim 38 words
A method according to claim 31 wherein the step of selecting a first subset of reference fingerprints comprises selecting same based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints.
Claim 46
Dependent Claim 57 words
A method according to claim 39 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values along the generally continuous and generally monotonically varying function larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 47
Dependent Claim 33 words
A method according to claim 39 wherein the step of determining an index value for the sample fingerprint comprises determining such an index value based upon ridge flow characteristics of the sample fingerprint.
Claim 48
Dependent Claim 62 words
A method according to claim 42 wherein the step of determining an index value for the sample fingerprint comprises the steps of: determining a center of the sample fingerprint; selecting a predetermined portion of the sample fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of the sample fingerprint.
Claim 49
Independent Claim 190 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index value to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint and based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 50
Independent Claim 190 words
A method for indexing and searching a plurality of reference fingerprints from a relatively large, selected population of individuals to determine if a sample fingerprint matches one of the reference fingerprints, the method comprising the steps of: determining respective index values for the reference fingerprints and the sample fingerprint based upon at least one predetermined fingerprint characteristic wherein the index values are both generally evenly distributed and continuous over the relatively large population of individuals; sorting the reference index value to define a generally continuous and generally monotonically varying function of the at least one predetermined fingerprint characteristic over the relatively large population of individuals; selecting a first subset of the reference fingerprints having index values along the generally continuous and generally monotonically varying function in a first range relative to the index value of the sample fingerprint and based upon an expected confidence value for locating the sample fingerprint in the first subset of reference fingerprints; and comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints to thereby determine if there is a match between the sample fingerprint and one of the reference fingerprints.
Claim 51
Dependent Claim 39 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally stable for repeated fingerprints of a finger of an individual.
Claim 52
Dependent Claim 40 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a fingerprint.
Claim 53
Dependent Claim 36 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be calculatable from information developed for the comparing step.
Claim 54
Dependent Claim 36 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values to be generally independent of fingerprint orientation, position and scaling.
Claim 55
Dependent Claim 43 words
A method according to claim 44 wherein the step of comparing the sample fingerprint to each fingerprint of the first subset of reference fingerprints comprises comparing minutiae of the sample fingerprint to minutiae of each fingerprint of the first subset of reference fingerprints.
Claim 56
Dependent Claim 48 words
A method according to claim 44 further comprising the step of selecting a second subset of reference fingerprints having a second range of index values larger than the first range if a match is not found in the step of comparing to the first subset of reference fingerprints.
Claim 57
Dependent Claim 34 words
A method according to claim 44 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises determining such index values based upon ridge flow characteristics of the fingerprints.
Claim 58
Dependent Claim 62 words
A method according to claim 51 wherein the step of determining index values for the reference fingerprints and the sample fingerprint comprises the steps of: determining a center of each fingerprint; selecting a predetermined portion of the fingerprint relative to the center; and calculating an aggregate of a rate of change of ridge direction vectors for the predetermined portion of each fingerprint.

USPTO Annuity & Maintenance Windows

Annuity Stage Window Opens Payment Deadline Surcharge Period Until Estimated Fee Status
3.5 Years (Year 4) 2001-11-23 2002-05-25 2002-11-24 $2000.00 Window Closed / Lapsed
7.5 Years (Year 8) 2005-11-23 2006-05-25 2006-11-24 $3760.00 Window Closed / Lapsed
11.5 Years (Year 12) 2009-11-23 2010-05-25 2010-11-24 $7700.00 Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag