Method and related apparatus for fingerprint indexing and searching

• US 6,021,211 A
• Filed: 03/02/1998
• Issued: 02/01/2000
• Est. Priority Date: 01/23/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: AuthenTec Incorporated (Apple Inc.)
• Inventors: Setlak, Dale R., Boss, Mark E., Schmitt, John C.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US09/033,437
• Time in Patent Office: 701 Days
• Field of Search: 382/124-127, 382/226, 382/227, 382/116, 382/115, 707/6, 707/2, 707/7, 356/71, 396/15, 340/825.34, 283/68, 283/69, 283/78
• US Class Current: 382/124
• CPC Class Codes: A61B 5/1172 using fingerprinting
• CPC Class Codes: G06V 40/1347 Preprocessing; Feature extraction
• CPC Class Codes: G06V 40/1365 Matching; Classification
• CPC Class Codes: G06V 40/168 Feature extraction; Face representation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

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.

Claims

1. A method for indexing and searching a plurality of data elements of a reference data group from a relatively large, selected population of data to determine if a sample data element matches one of the data elements in the reference data group, the method comprising the steps of:

determining respective full entire index values for each of the plurality of data elements of the reference data group and the sample data element based upon at least one predetermined data element characteristic and with the full entire reference index values being sorted in either a numerically ascending or descending order and substantially evenly distributed over the relatively large population of data;

selecting a first subset having a plurality of data elements of the sorted reference data group, the first subset having index values in a first range relative to the full entire index value of the sample data element, the first subset also having substantially fewer data elements than the reference data group;

comparing the sample data element to each data element of the first subset of the reference data group to thereby determine if there is a match between the sample data element and one of the plurality of data elements of the first subset, of the reference data group; and

selecting a second subset having a plurality of sorted data elements of the reference data group if a match is not found in the step of comparing to the first subset of the reference data group, the second subset having a second expanded range of full entire index values larger than the first range so that the second expanded range extends at least immediately above and below the first range.

2. A method according to claim 1, wherein the step of determining index values for each of the plurality of data elements of the reference data group and the sample data element comprise determining and sorting such index values to be a generally monotonically varying function over the relatively large population of data.

3. A method according to claim 1, wherein the step of determining index values for each of the plurality of data elements of the reference data group and the sample data group comprises determining such index values to be generally continuous over the relatively large population of individuals.

4. A method according to claim 1, wherein the step of determining index values for each of the plurality of data elements of the reference data group and the sample data element comprises determining such index values to be generally stable for repeated data elements of a data group.

5. A method according to claim 1, wherein the step of determining index values for each of the plurality of data elements of the reference data group and the sample data element comprises determining such index values to be generally incrementally changing in relation to degradation in quality of a data element.

6. A method according to claim 1, wherein the step of determining index values for the reference data elements and the sample data element comprises determining such index values to be generally independent of data element orientation, position and scaling.

7. A method according to claim 1, wherein the step of selecting a first subset of the reference data group comprises selecting same based upon an expected confidence value for locating the sample data element in the first subset of the reference data group.

8. A method according to claim 1, wherein the step of comparing the sample data element to each data element of the first subset of the reference data group comprises comparing minutiae of the sample data element to minutiae of each data element of the first subset of the reference data group.

9. A method according to claim 1, wherein the step of determining index values for the reference data elements and the sample data elements comprises determining such index values based upon preselected characteristics of the data elements.

10. A method for searching a plurality of reference data elements to determine if a sample data element matches one of the reference data elements, each of the reference data elements having associated therewith a full entire index value based upon at least one predetermined data element characteristic and with the full entire index values for the reference data elements being sorted in either a numerically ascending or desending order and substantially evenly distributed over a relatively large population of individuals, the method comprising the steps of:

determining a full entire index value for the sample data element based upon the at least one predetermined data element characteristic;

selecting a first subset having a plurality of data elements of the sorted reference data elements, the first subset having full entire index values in a first range relative to the full entire index value of the sample data element, the first subset also having substantially fewer data elements than the plurality of reference data elements;

comparing the sample data element to each data element of the first subset of reference data elements to thereby determine if there is a match between the sample data element and one of the plurality of data elements of the first subset of the reference data elements; and

selecting a second subset having a plurality of data elements of the sorted reference data group if a match is not found in the step of comparing to the first subset of the reference data elements, the second subset having a second expanded range of full entire index values larger than the first range so that the second expanded range extends at least immediately above and below the first range.

11. A method according to claim 10, wherein the step of selecting a first subset of the reference data elements comprises selecting same based upon an expected confidence value for locating the sample data element in the first subset of reference data elements.

12. A method according to claim 10, wherein the step of determining a full entire index value for the sample data element comprises determining such a full entire index value based upon a plurality of preselected characteristics of the sample data element.

13. A method according to claim 10, wherein the step of determining a full entire index value for the sample data element comprises the steps of:

determining a predefined region of the sample data element;

selecting a predetermined portion of the sample data element relative to the predefined region; and

calculating an aggregate of a rate of change of direction vectors for the predetermined portion of the sample data element.